Quelle est la meilleure IA de Battleship ?

Question

Bataille navale!

En 2003 (quand j'avais 17 ans), j'ai participé à un concours de codage IA de Bataille navale. Même si j'ai perdu ce tournoi, j'ai beaucoup apprécié et beaucoup appris.

Maintenant, j'aimerais faire renaître cette compétition, à la recherche de la meilleure IA de bataille navale.

Voici le cadre, maintenant hébergé sur Bitbucket.

Le vainqueur recevra +450 de réputation! La compétition débutera le 17 novembre 2009. Aucune entrée ou modification postérieure à zéro heure le 17 ne sera acceptée. (Heure normale du centre) Soumettez vos participations tôt, pour ne pas manquer votre opportunité!

Pour rester OBJECTIF, veuillez suivre l'esprit de la compétition.

Règles du jeu:

1. Le jeu se déroule sur une grille de 10x10.
2. Chaque concurrent placera chacun des 5 navires (de longueurs 2, 3, 3, 4, 5) sur leur grille.
3. Aucun navire ne peut se chevaucher, mais ils peuvent être adjacents.
4. Les concurrents se relaient ensuite pour tirer des coups simples sur leur adversaire.
   • Une variation du jeu permet de tirer plusieurs coups par salve, un pour chaque navire survivant.
5. L'adversaire informera le concurrent si le tir coule, touche ou rate.
6. Le jeu se termine lorsque tous les navires d'un joueur sont coulés.

Règles de la compétition:

1. L'esprit de la compétition est de trouver le meilleur algorithme de Bataille navale.
2. Tout ce qui est jugé contraire à l'esprit de la compétition pourra entraîner une disqualification.
3. Interférer avec un adversaire est contraire à l'esprit de la compétition.
4. Le multithreading peut être utilisé sous les restrictions suivantes:
   • Pas plus d'un thread ne peut s'exécuter lorsque ce n'est pas votre tour. (Cependant, plusieurs threads peuvent être dans un état "Suspendu").
   • Aucun thread ne doit s'exécuter à une priorité autre que "Normale".
   • Étant donné les deux restrictions ci-dessus, vous aurez la garantie d'au moins 3 cœurs de CPU dédiés pendant votre tour.
5. Une limite de 1 seconde de temps CPU par jeu est allouée à chaque concurrent sur le thread principal.
6. Le fait de manquer de temps entraîne la perte du jeu en cours.
7. Toute exception non gérée entraînera la perte du jeu en cours.
8. L'accès au réseau et au disque est autorisé, mais vous pourriez trouver les restrictions de temps assez contraignantes. Cependant, quelques méthodes de mise en place et de disparition ont été ajoutées pour soulager la contrainte de temps.
9. Le code doit être posté sur stack overflow en tant que réponse, ou, s'il est trop volumineux, lié.
10. La taille totale maximale (non compressée) d'une entrée est de 1 Mo.
11. Officiellement, .Net 2.0 / 3.5 est la seule exigence de cadre.
12. Votre entrée doit implémenter l'interface IBattleshipOpponent.

Score:

1. Les meilleurs 51 jeux sur 101 jeux remportent une partie.
2. Tous les concurrents joueront des matchs les uns contre les autres, de style round-robin.
3. La meilleure moitié des concurrents joueront ensuite un tournoi à double élimination pour déterminer le vainqueur. (La plus petite puissance de deux qui est supérieure ou égale à la moitié, en fait.)
4. J'utiliserai le cadre TournamentApi pour le tournoi.
5. Les résultats seront publiés ici.
6. Si vous soumettez plus d'une entrée, seule votre meilleure entrée en termes de score est éligible pour la double élimination.

Bonne chance! Amusez-vous!

---

EDIT 1:
Merci à Freed, qui a trouvé une erreur dans la fonction Ship.IsValid. Elle a été corrigée. Veuillez télécharger la version mise à jour du cadre.

EDIT 2:
Comme il y a eu un intérêt important pour la sauvegarde des statistiques sur disque, j'ai ajouté quelques événements de mise en place et de disparition non chronométrés qui devraient fournir la fonctionnalité requise. Il s'agit d'un changement partiellement dérangeant. C'est-à-dire que l'interface a été modifiée pour ajouter des fonctions, mais aucun code n'est requis pour elles. Veuillez télécharger la version mise à jour du cadre.

EDIT 3:
Correction de bug 1: GameWon et GameLost n'étaient appelés que en cas de dépassement de délai.
Correction de bug 2: Si un moteur dépassait le temps à chaque jeu, la compétition ne se terminerait jamais.
Veuillez télécharger la version mise à jour du cadre.

EDIT 4:
Résultats du tournoi:

Answer 1

Je soutiens la motion de faire beaucoup plus de parties par match. Faire 50 parties revient simplement à jouer à pile ou face. Il a fallu que je fasse 1000 parties pour obtenir une distinction raisonnable entre les algorithmes de test.

Téléchargez Dreadnought 1.2.

Stratégies:

• garder une trace de toutes les positions possibles des navires ayant >0 touches. La liste ne dépasse jamais ~30K donc elle peut être conservée exactement, contrairement à la liste de toutes les positions possibles pour tous les navires (qui est très grande).

• L'algorithme GetShot se compose de deux parties, l'une qui génère des tirs aléatoires et l'autre qui tente de terminer de couler un navire déjà touché. Nous faisons des tirs aléatoires s'il existe une position possible (de la liste ci-dessus) dans laquelle tous les navires touchés sont coulés. Sinon, nous essayons de terminer de couler un navire en choisissant un emplacement pour tirer qui élimine le plus de positions possibles (pondéré).

• Pour les tirs aléatoires, calculer le meilleur emplacement pour tirer en fonction de la probabilité qu'un des navires non coulés chevauche l'emplacement.

• algorithme adaptatif qui place des navires dans des endroits où l'adversaire a statistiquement moins de chances de tirer.

• algorithme adaptatif qui préfère tirer sur des emplacements où l'adversaire a statistiquement plus de chances de placer ses navires.

• placer les navires principalement sans se toucher.

Answer 2

Voici mon entrée! (La solution la plus naïve possible)

"Aléatoire 1.1"

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

    public class RandomOpponent : IBattleshipOpponent
    {
        public string Name { get { return "Aléatoire"; } }
        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 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() { }
    }
}

Answer 3

Voici un adversaire contre lequel les gens peuvent jouer :

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

Au lieu d'utiliser une stratégie inspirée par la géométrie fixe, j'ai pensé qu'il serait intéressant d'essayer d'estimer les probabilités sous-jacentes selon lesquelles un espace non exploré particulier contient un navire.

Pour faire cela correctement, vous devriez explorer toutes les configurations possibles de navires qui correspondent à votre vision actuelle du monde, puis calculer les probabilités basées sur ces configurations. Vous pourriez le voir comme l'exploration d'un arbre :

une expansion des états possibles de battleship http://natekohl.net/media/battleship-tree.png

Après avoir pris en compte toutes les feuilles de cet arbre qui concordent avec ce que vous savez sur le monde (par exemple, les navires ne peuvent pas se chevaucher, toutes les cases touchées doivent être des navires, etc.), vous pouvez compter combien de fois les navires se trouvent à chaque position non explorée pour estimer la probabilité qu'un navire soit là.

Ceci peut être visualisé sous forme de carte thermique, où les zones chaudes sont plus susceptibles de contenir des navires :

une carte thermique des probabilités pour chaque position non explorée http://natekohl.net/media/battleship-probs.png

Une chose que j'apprécie dans cette compétition de Battleship est que l'arbre ci-dessus est presque assez petit pour forcer ce type d'algorithme. S'il y a ~150 positions possibles pour chacun des 5 navires, cela fait 1505 = 75 milliards de possibilités. Et ce nombre ne fait que diminuer, surtout si vous pouvez éliminer des navires entiers.

L'adversaire que j'ai lié ci-dessus n'explore pas tout l'arbre ; 75 milliards de possibilités reste encore trop grand pour rentrer en moins d'une seconde. Il essaie cependant d'estimer ces probabilités, avec l'aide de quelques heuristiques.

Answer 4

Pas une véritable réponse, mais il semble y avoir peu de point d'encombrer les vraies réponses avec le code qui est commun. Je présente ainsi certaines extensions/classes générales dans l'esprit de l'open source. Si vous utilisez ces alors s'il vous plaît changer l'espace de noms ou d'essayer de compiler le tout dans un dll n'est pas d'aller travailler.

BoardView vous permet de travailler facilement avec une annoté conseil d'administration.

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
    }
}

Certaines extensions, certaines de ces doublons de fonctionnalité dans le cadre principal mais faut vraiment être fait par vous.

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));
        }
    }
}

Quelque chose je l'aide beaucoup.

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

La randomisation. Sécurisé, mais testable, utile pour les tests.

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!");
        }
    }
}

Answer 5

Je n'ai pas le temps en ce moment d'écrire un algorithme complet, mais voici une pensée : si votre adversaire a placé des navires au hasard, les probabilités de placement seraient une simple distribution centrée sur (5,5), non? Par exemple, les possibilités de placement pour le cuirassé (long de 5 unités) dans la dimension x sont les suivantes :

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

Les mêmes calculs seraient valables pour y. Les autres navires n'auraient pas de distributions aussi abruptes, mais votre meilleur estimation reste le centre. Ensuite, l'approche mathématique consisterait à irradier lentement des diagonales (peut-être avec la longueur du navire moyen, 17/5) hors du centre. Ex :

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

De toute évidence, une certaine part de hasard devrait être ajoutée à l'idée, mais je pense que purement mathématiquement, c'est la voie à suivre.