315 votos

¿Cuál es el mejor acorazado AI?

Battleship!

En el año 2003, (cuando yo tenía 17,), que compitió en un Acorazado de la IA codificación de la competencia. Aunque perdí ese torneo, me divertí mucho y aprendí mucho de él.

Ahora, me gustaría resucitar a esta competición, en la búsqueda de la mejor acorazado de la IA.

Aquí es el marco: Battleship.zip

El ganador será premiado +450 reputación! La competencia se llevará a cabo a partir del 17 de noviembre de 2009. No hay entradas o ediciones más tarde de las cero horas del 17 será aceptado. (Central Standard Time) Envíe sus entradas con anticipación, así que no te pierdas tu oportunidad!

Para mantener este OBJETIVO, por favor siga el espíritu de la competición.

Reglas del juego:

  1. El juego se juega en una cuadrícula de 10x10.
  2. Cada competidor tendrá lugar cada una de las 5 naves (de longitudes de 2, 3, 3, 4, 5) en su cuadrícula.
  3. No hay barcos pueden superponerse, pero pueden ser adyacentes.
  4. Los competidores tomen turnos de disparo único tiros a su oponente.
    • Una variación sobre el juego permite el disparo de varios disparos por volea, uno para cada uno de los supervivientes de la nave.
  5. El oponente va a notificar a el competidor si el tiro se hunde, golpea, o no.
  6. El juego termina cuando todos los buques de cualquier jugador está hundido.

Reglas del concurso:

  1. El espíritu del concurso es encontrar el mejor Acorazado algoritmo.
  2. Cualquier cosa que es contraria al espíritu de la competición será motivo de descalificación.
  3. Interferir a un adversario es contra el espíritu de la competición.
  4. Multithreading puede ser usado bajo las siguientes restricciones:
    • No hay más que un hilo puede estar en ejecución cuando no es tu turno. (Aunque, de cualquier número de hilos puede ser en un "Suspendida").
    • No el hilo se puede ejecutar en una prioridad que no sea "Normal".
    • Teniendo en cuenta las dos restricciones, se le garantiza al menos 3 dedicado núcleos de CPU durante su turno.
  5. Un límite de 1 segundo de tiempo de CPU por juego es asignado a cada competidor en el subproceso principal.
  6. Corriendo fuera de tiempo, los resultados en la pérdida de la partida actual.
  7. Cualquier excepción no controlada se traducirá en la pérdida de la partida actual.
  8. El acceso a la red y el acceso a disco es permitido, pero usted puede encontrar las restricciones de tiempo bastante prohibitivo. Sin embargo, un par de set-up y desbaratar los métodos que se han añadido para aliviar el tiempo de la cepa.
  9. El código debe ser publicado en el desbordamiento de pila como una respuesta, o, si es demasiado grande, vinculado.
  10. Max tamaño total (sin compresión) de una entrada es de 1 MB.
  11. Oficialmente, .Net 2.0 / 3.5 es el único marco requisito.
  12. Su entrada debe implementar la IBattleshipOpponent de la interfaz.

Puntuación:

  1. Mejor 51 juegos de 101 juegos es el ganador de un partido.
  2. Todos los competidores van a jugar igualadas uno contra el otro, por turnos estilo.
  3. Los mejores de la mitad de los competidores luego de jugar un torneo de doble eliminación para determinar el ganador. (Menor potencia de dos, que es mayor que o igual a la mitad, en realidad.)
  4. Me va a utilizar el TournamentApi marco para el torneo.
  5. Los resultados serán publicados aquí.
  6. Si envía más de una entrada, sólo su mejor puntuación de la entrada es elegible para la doble-elim.

Buena suerte! Divertirse!


EDIT 1:
Gracias a los Liberados, que ha encontrado un error en el Ship.IsValid función. Se ha corregido. Por favor descarga la versión actualizada del marco.

EDIT 2:
Desde entonces ha habido un gran interés en la persistencia de las estadísticas a disco y tal, he añadido un par de no-temporizado de set-up y desbaratar los eventos que debe proporcionar la funcionalidad requerida. Este es un semi-cambio de hora. Es decir: la interfaz ha sido modificada para agregar funciones, pero no es necesario para ellos. Por favor descarga la versión actualizada del marco.

EDIT 3:
Corrección de error 1: GameWon y GameLost fueron sólo recibir llamadas en el caso de un tiempo de espera.
Corrección de error 2: Si un motor se agote el tiempo de espera de cada juego, la competencia sería de nunca acabar.
Por favor descarga la versión actualizada del marco.

EDIT 4:
Resultados! Tournament Results

56voto

Keith Randall Puntos 17518

Apruebo la moción de hacer mucho más de los juegos por partido. Haciendo de 50 juegos, que se acaba de lanzar una moneda. Necesitaba hacer 1000 juegos para obtener cualquier distinción razonable entre la prueba de los algoritmos.

Descargar Dreadnought 1.2.

Estrategias:

  • mantener un seguimiento de todas las posiciones posibles para los buques que han >0 hits. La lista no hace más que ~30K por lo que puede ser mantenido exactamente, a diferencia de la lista de todas las posiciones posibles para todos los barcos (que es muy grande).

  • El GetShot algoritmo tiene dos partes, una que genera al azar disparos y el otro que intenta terminar el hundimiento de una exitosa nave. Softonic azar tiros si es posible una posición (de la lista de arriba) en la que todo el éxito barcos se hundieron. De lo contrario, trataremos de terminar el hundimiento de un barco mediante la selección de una ubicación para disparar a lo que elimina la mayoría de las posiciones posibles (ponderada).

  • Para disparos al azar, calcular la mejor ubicación para disparar se basan en la probabilidad de que uno de los unsunk buques de la superposición de la ubicación.

  • algoritmo adaptativo que coloca a los buques en lugares en donde el oponente es estadísticamente menos probable para disparar.

  • algoritmo adaptativo que prefiere filmar en lugares donde el oponente es estadísticamente más probable que el lugar de sus barcos.

  • colocar los barcos en su mayoría no se toquen.

35voto

John Gietzen Puntos 23645

Aquí está mi entrada! (La mayoría solución de ingenua posible)

"Random 1.1"

namespace Battleship
{
    using System;
    using System.Collections.ObjectModel;
    using System.Drawing;

    public class RandomOpponent : IBattleshipOpponent
    {
        public string Name { get { return "Random"; } }
        public Version Version { get { return this.version; } }

        Random rand = new Random();
        Version version = new Version(1, 1);
        Size gameSize;

        public void NewGame(Size size, TimeSpan timeSpan)
        {
            this.gameSize = size;
        }

        public void PlaceShips(ReadOnlyCollection<Ship> ships)
        {
            foreach (Ship s in ships)
            {
                s.Place(
                    new Point(
                        rand.Next(this.gameSize.Width),
                        rand.Next(this.gameSize.Height)),
                    (ShipOrientation)rand.Next(2));
            }
        }

        public Point GetShot()
        {
            return new Point(
                rand.Next(this.gameSize.Width),
                rand.Next(this.gameSize.Height));
        }

        public void NewMatch(string opponent) { }
        public void OpponentShot(Point shot) { }
        public void ShotHit(Point shot, bool sunk) { }
        public void ShotMiss(Point shot) { }
        public void GameWon() { }
        public void GameLost() { }
        public void MatchOver() { }
    }
}

22voto

Nate Kohl Puntos 11240

He aquí un oponente para que la gente juegue en contra:

En lugar de utilizar una geometría fija-estrategia inspirada, pensé que sería interesante intentar estimar el subyacente probabilidades de que cualquier particular inexplorado espacio tiene un barco.

Para hacer esto bien, tendría que explorar todas las posibles configuraciones de los buques que se ajustan a su visión actual del mundo, y, a continuación, calcular las probabilidades basándose en las configuraciones. Usted podría pensar en él como la exploración de un árbol:

an expansion of possible battleship states

Después de considerar todas las hojas de ese árbol que concuerdan con lo que sabemos sobre el mundo (por ej. los barcos no pueden superponerse, todo el éxito cuadrados deben ser buques, etc.) usted puede contar cómo a menudo los barcos se producen en cada inexplorado posición para estimar la probabilidad de que un buque que está sentado allí.

Esto puede ser visualizado como un mapa de calor, donde los puntos calientes son más propensos a contener barcos:

a heat map of probabilities for each unexplored position

Una cosa que me gusta de este Buque de guerra de la competencia es que el árbol de arriba es casi lo suficientemente pequeño como para fuerza bruta de este tipo de algoritmo. Si hay ~150 posiciones posibles para cada una de las 5 naves, de los que 1505 = 75 millones de posibilidades. Y ese número sólo se hace más pequeño, especialmente si usted puede eliminar la totalidad de los buques.

El rival que he enlazado más arriba no explorar el árbol entero; 75 millones de dólares es todavía grande para conseguir en menos de un segundo. Se hace el intento de estimar estas probabilidades, aunque, con la ayuda de un par de heurística.

12voto

ShuggyCoUk Puntos 24204

No es un pleno derecho de responder, pero parece que hay poca punto de abarrotar el real respuestas con el código que es común. Por lo tanto, presentar algunas de las extensiones/clases generales en el espíritu del open source. Si el uso de estas, por favor cambiar el espacio de nombres o tratando de compilar todo en un solo archivo dll no va a funcionar.

BoardView le permite trabajar fácilmente con una anotada de la junta.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.IO;

namespace Battleship.ShuggyCoUk
{
    public enum Compass
    {
        North,East,South,West
    }

    class Cell<T>
    {
        private readonly BoardView<T> view;
        public readonly int X;
        public readonly int Y;
        public T Data;
        public double Bias { get; set; }

        public Cell(BoardView<T> view, int x, int y) 
        { 
            this.view = view; this.X = x; this.Y = y; this.Bias = 1.0;  
        }

        public Point Location
        {
            get { return new Point(X, Y); }
        }

        public IEnumerable<U> FoldAll<U>(U acc, Func<Cell<T>, U, U> trip)
        {
            return new[] { Compass.North, Compass.East, Compass.South, Compass.West }
                .Select(x => FoldLine(x, acc, trip));
        }

        public U FoldLine<U>(Compass direction, U acc, Func<Cell<T>, U, U> trip)
        {
            var cell = this;
            while (true)
            {
                switch (direction)
                {
                    case Compass.North:
                        cell = cell.North; break;
                    case Compass.East:
                        cell = cell.East; break;
                    case Compass.South:
                        cell = cell.South; break;
                    case Compass.West:
                        cell = cell.West; break;
                }
                if (cell == null)
                    return acc;
                acc = trip(cell, acc);
            }
        }

        public Cell<T> North
        {
            get { return view.SafeLookup(X, Y - 1); }
        }

        public Cell<T> South
        {
            get { return view.SafeLookup(X, Y + 1); }
        }

        public Cell<T> East
        {
            get { return view.SafeLookup(X+1, Y); }
        }

        public Cell<T> West
        {
            get { return view.SafeLookup(X-1, Y); }
        }

        public IEnumerable<Cell<T>> Neighbours()
        {
            if (North != null)
                yield return North;
            if (South != null)
                yield return South;
            if (East != null)
                yield return East;
            if (West != null)
                yield return West;
        }
    }

    class BoardView<T>  : IEnumerable<Cell<T>>
    {
        public readonly Size Size;
        private readonly int Columns;
        private readonly int Rows;

        private Cell<T>[] history;

        public BoardView(Size size)
        {
            this.Size = size;
            Columns = size.Width;
            Rows = size.Height;
            this.history = new Cell<T>[Columns * Rows];
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Rows; x++)
                    history[x + y * Columns] = new Cell<T>(this, x, y);
            }
        }

        public T this[int x, int y]
        {
            get { return history[x + y * Columns].Data; }
            set { history[x + y * Columns].Data = value; }
        }

        public T this[Point p]
        {
            get { return history[SafeCalc(p.X, p.Y, true)].Data; }
            set { this.history[SafeCalc(p.X, p.Y, true)].Data = value; }
        }

        private int SafeCalc(int x, int y, bool throwIfIllegal)
        {
            if (x < 0 || y < 0 || x >= Columns || y >= Rows)
            {    if (throwIfIllegal)
                    throw new ArgumentOutOfRangeException("["+x+","+y+"]");
                 else
                    return -1;
            }
            return x + y * Columns;
        }

        public void Set(T data)
        {
            foreach (var cell in this.history)
                cell.Data = data;
        }

        public Cell<T> SafeLookup(int x, int y)
        {
            int index = SafeCalc(x, y, false);
            if (index < 0)
                return null;
            return history[index];
        }

        #region IEnumerable<Cell<T>> Members

        public IEnumerator<Cell<T>> GetEnumerator()
        {
            foreach (var cell in this.history)
                yield return cell;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public BoardView<U> Transform<U>(Func<T, U> transform)
        {
            var result = new BoardView<U>(new Size(Columns, Rows));
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Columns; x++)
                {
                    result[x,y] = transform(this[x, y]);
                }
            }
            return result;
        }

        public void WriteAsGrid(TextWriter w)
        {
            WriteAsGrid(w, "{0}");
        }

        public void WriteAsGrid(TextWriter w, string format)
        {
            WriteAsGrid(w, x => string.Format(format, x.Data));
        }

        public void WriteAsGrid(TextWriter w, Func<Cell<T>,string> perCell)
        {
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Columns; x++)
                {
                    if (x != 0)
                        w.Write(",");
                    w.Write(perCell(this.SafeLookup(x, y)));
                }
                w.WriteLine();
            }
        }

        #endregion
    }
}

Algunas de las extensiones, algo de esto duplica la funcionalidad en el marco principal, pero realmente debe ser hecho por usted.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Collections.ObjectModel;

namespace Battleship.ShuggyCoUk
{
    public static class Extensions
    {        
        public static bool IsIn(this Point p, Size size)
        {
            return p.X >= 0 && p.Y >= 0 && p.X < size.Width && p.Y < size.Height;
        }

        public static bool IsLegal(this Ship ship,
            IEnumerable<Ship> ships, 
            Size board,
            Point location, 
            ShipOrientation direction)
        {
            var temp = new Ship(ship.Length);
            temp.Place(location, direction);
            if (!temp.GetAllLocations().All(p => p.IsIn(board)))
                return false;
            return ships.Where(s => s.IsPlaced).All(s => !s.ConflictsWith(temp));
        }

        public static bool IsTouching(this Point a, Point b)
        {
            return (a.X == b.X - 1 || a.X == b.X + 1) &&
                (a.Y == b.Y - 1 || a.Y == b.Y + 1);
        }

        public static bool IsTouching(this Ship ship,
            IEnumerable<Ship> ships,
            Point location,
            ShipOrientation direction)
        {
            var temp = new Ship(ship.Length);
            temp.Place(location, direction);
            var occupied = new HashSet<Point>(ships
                .Where(s => s.IsPlaced)
                .SelectMany(s => s.GetAllLocations()));
            if (temp.GetAllLocations().Any(p => occupied.Any(b => b.IsTouching(p))))
                return true;
            return false;
        }

        public static ReadOnlyCollection<Ship> MakeShips(params int[] lengths)
        {
            return new System.Collections.ObjectModel.ReadOnlyCollection<Ship>(
                lengths.Select(l => new Ship(l)).ToList());       
        }

        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Rand rand)
        {
            T[] elements = source.ToArray();
            // Note i > 0 to avoid final pointless iteration
            for (int i = elements.Length - 1; i > 0; i--)
            {
                // Swap element "i" with a random earlier element it (or itself)
                int swapIndex = rand.Next(i + 1);
                T tmp = elements[i];
                elements[i] = elements[swapIndex];
                elements[swapIndex] = tmp;
            }
            // Lazily yield (avoiding aliasing issues etc)
            foreach (T element in elements)
            {
                yield return element;
            }
        }

        public static T RandomOrDefault<T>(this IEnumerable<T> things, Rand rand)
        {
            int count = things.Count();
            if (count == 0)
                return default(T);
            return things.ElementAt(rand.Next(count));
        }
    }
}

Algo me terminan usando mucho.

enum OpponentsBoardState
{
    Unknown = 0,
    Miss,
    MustBeEmpty,        
    Hit,
}

La aleatorización. Seguro, pero comprobables, útil para las pruebas.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace Battleship.ShuggyCoUk
{
    public class Rand
    {
        Random r;

        public Rand()
        {
            var rand = System.Security.Cryptography.RandomNumberGenerator.Create();
            byte[] b = new byte[4];
            rand.GetBytes(b);
            r = new Random(BitConverter.ToInt32(b, 0));
        }

        public int Next(int maxValue)
        {
            return r.Next(maxValue);
        }

        public double NextDouble(double maxValue)
        {
            return r.NextDouble() * maxValue;
        }

        public T Pick<T>(IEnumerable<T> things)
        {
            return things.ElementAt(Next(things.Count()));
        }

        public T PickBias<T>(Func<T, double> bias, IEnumerable<T> things)
        {
            double d = NextDouble(things.Sum(x => bias(x)));
            foreach (var x in things)
            {
                if (d < bias(x))
                    return x;
                d -= bias(x);                
            }
            throw new InvalidOperationException("fell off the end!");
        }
    }
}

10voto

ine Puntos 10065

No tengo tiempo ahora para escribir un completo algoritmo, pero he aquí una idea: si su oponente coloca naves al azar, no la colocación de probabilidades de ser una simple distribución centrada en (5.5,5.5)? Por ejemplo, la colocación de posibilidades para el acorazado (5 unidades) en la dimensión x está aquí:

x    1 2 3 4 5  6  7 8 9 10
P(x) 2 4 6 8 10 10 8 6 4 2

Los mismos cálculos, sería válido para y. Los otros barcos que no tendría empinadas de las distribuciones, pero su mejor conjetura es todavía el centro. Después de eso, el enfoque matemático sería lentamente irradiando diagonales (tal vez con la longitud de la media de la nave, 17/5) fuera del centro. Ex:

...........
....x.x....
.....x.....
....x.x....
...........

Obviamente algo de aleatoriedad sería necesario añadir a la idea, pero creo que puramente matemáticamente que es el camino a seguir.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X