¿Cuál es la mejor IA de acorazado?

¡Acorazado!

En 2003 (cuando tenía 17 años), competí en una competencia de codificación de IA de Battleship . Aunque perdí ese torneo, me divertí mucho y aprendí mucho de ello.

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

Aquí está el marco, ahora alojado en Bitbucket .

¡El ganador recibirá +450 de reputación! El concurso se celebrará a partir del 17 de noviembre de 2009 . No se aceptarán entradas ni ediciones posteriores a la hora cero del día 17. (Hora estándar central) ¡Envíe sus trabajos con anticipación para no perder la oportunidad!

Para mantener este OBJETIVO , siga el espíritu del concurso.

Reglas del juego:

1. El juego se juega en una cuadrícula de 10x10.
2. Cada competidor colocará cada uno de los 5 barcos (de esloras 2, 3, 3, 4, 5) en su cuadrícula.
3. Ningún barco podrá superponerse, pero sí podrán estar adyacentes.
4. Luego, los competidores se turnan para disparar tiros individuales a su oponente.
   • Una variación del juego permite realizar múltiples disparos por descarga, uno por cada barco superviviente.
5. El oponente notificará al competidor si el tiro se hunde, acierta o falla.
6. El juego termina cuando todos los barcos de un jugador son hundidos.

Reglas del concurso:

1. El espíritu de la competencia es encontrar el mejor algoritmo de Battleship.
2. Todo lo que se considere contrario al espíritu de la competición será motivo de descalificación.
3. Interferir con un oponente va en contra del espíritu de la competición.
4. Se puede utilizar subprocesos múltiples bajo las siguientes restricciones:
   • No puede haber más de un hilo en ejecución mientras no sea tu turno. (Sin embargo, cualquier número de subprocesos puede estar en estado "Suspendido").
   • Ningún hilo puede ejecutarse con una prioridad distinta de "Normal".
   • Dadas las dos restricciones anteriores, se le garantizarán al menos 3 núcleos de CPU dedicados durante su turno.
5. Se asigna un límite de 1 segundo de tiempo de CPU por juego a cada competidor en el hilo principal.
6. Quedarse sin tiempo resulta en perder el juego actual.
7. Cualquier excepción no controlada resultará en la pérdida del juego actual.
8. Se permite el acceso a la red y al disco, pero es posible que las restricciones de tiempo le resulten bastante prohibitivas. Sin embargo, se han agregado algunos métodos de instalación y desmontaje para aliviar la tensión de tiempo.
9. El código debe publicarse en el desbordamiento de la pila como respuesta o, si es demasiado grande, vincularse.
10. El tamaño total máximo (sin comprimir) de una entrada es 1 MB.
11. Oficialmente, .Net 2.0/3.5 es el único requisito del marco.
12. Su entrada debe implementar la interfaz IBattleshipOpponent.

Puntuación:

1. El mejor 51 juegos de 101 juegos es el ganador de un partido.
2. Todos los competidores jugarán entre sí, al estilo de todos contra todos.
3. La mejor mitad de los competidores jugará un torneo de doble eliminación para determinar el ganador. (La potencia más pequeña de dos que es mayor o igual a la mitad, en realidad).
4. Usaré el marco TournamentApi para el torneo.
5. Los resultados se publicarán aquí.
6. Si envía más de una entrada, solo la entrada con mejor puntuación será elegible para la doble eliminación.

¡Buena suerte! ¡Divertirse!

EDITAR 1:
Gracias a Freed , que encontró un error en la Ship.IsValidfunción. Ha sido arreglado. Descargue la versión actualizada del marco.

EDITAR 2:
Dado que ha habido un gran interés en conservar las estadísticas en el disco y demás, agregué algunos eventos de configuración y desmontaje no programados que deberían proporcionar la funcionalidad requerida. Este es un cambio semi-rompiente . Es decir: se ha modificado la interfaz para añadir funciones, pero no se requiere ningún cuerpo para ellas. Descargue la versión actualizada del marco.

EDITAR 3:
Corrección de error 1: GameWony GameLostsolo nos llamaban en caso de que se agotara el tiempo de espera.
Corrección de error 2: si un motor agotara el tiempo de cada juego, la competencia nunca terminaría.
Descargue la versión actualizada del marco.

EDITAR 4:
Resultados del torneo:

Oct 27 '09 22:10 John Gietzen

¡Aquí está mi entrada! (La solución más ingenua posible)

"Aleatorio 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() { }
    }
}

Oct 27 '2009 15:10 John Gietzen

Aquí hay un oponente contra el cual la gente puede jugar:

• http://natekohl.net/files/FarnsworthOpponent.cs

En lugar de utilizar una estrategia inspirada en la geometría fija, pensé que sería interesante intentar estimar las probabilidades subyacentes de que cualquier espacio inexplorado en particular contenga una nave.

Para hacer esto correctamente, explorarías todas las configuraciones posibles de barcos que se ajusten a tu visión actual del mundo y luego calcularías probabilidades basadas en esas configuraciones. Podrías pensar en ello como explorar un árbol:

una expansión de posibles estados acorazados http://natekohl.net/media/battleship-tree.png

Después de considerar todas las hojas de ese árbol que concuerdan con lo que sabes sobre el mundo (por ejemplo, los barcos no pueden superponerse, todas las casillas de impacto deben ser barcos, etc.), puedes contar con qué frecuencia aparecen barcos en cada posición inexplorada para estimar la probabilidad de que Hay un barco allí.

Esto se puede visualizar como un mapa de calor, donde es más probable que los puntos calientes contengan barcos:

un mapa de calor de probabilidades para cada posición inexplorada http://natekohl.net/media/battleship-probs.png

Una cosa que me gusta de esta competencia Battleship es que el árbol de arriba es casi lo suficientemente pequeño como para aplicar fuerza bruta a este tipo de algoritmo. Si hay ~150 posiciones posibles para cada uno de los 5 barcos, eso es 150 ⁵ = 75 mil millones de posibilidades. Y ese número sólo se reduce, especialmente si puedes eliminar barcos enteros.

El oponente al que me vinculé anteriormente no explora todo el árbol; 75 mil millones es todavía demasiado grande para entrar en menos de un segundo. Sin embargo, intenta estimar estas probabilidades con la ayuda de algunas heurísticas.

Nov 13 '2009 02:11