Quelle est la meilleure AI de cuirassé?
https://stackoverflow.com/questions/1631414
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Cuirassé!
En 2003 (à l'âge de 17 ans), j'ai participé au codage Battleship AI . concurrence. Même si j'ai perdu ce tournoi, je me suis beaucoup amusé et j'ai beaucoup appris de ce tournoi.
Maintenant, je voudrais ressusciter cette compétition, à la recherche du meilleur cuirassé IA.
Voici le cadre, désormais hébergé sur Bitbucket .
Le gagnant se verra attribuer une réputation de +450! Le concours se tiendra à partir du 17 novembre 2009 . Aucune inscription ou modification postérieure à zéro heure le 17 ne sera acceptée. (Heure normale du Centre) Soumettez vos entrées au plus tôt pour ne pas manquer votre chance!
Pour conserver cet OBJECTIF , suivez l'esprit de la compétition.
Règles du jeu:
- Le jeu se joue sur une grille 10x10.
- Chaque concurrent placera chacun des 5 navires (de longueur 2, 3, 3, 4, 5) sur sa grille.
- Aucun navire ne peut se chevaucher, mais il peut être adjacent.
- Les concurrents lancent à tour de rôle des tirs simples sur leur adversaire.
- Une variante du jeu permet de tirer plusieurs coups par volée, un pour chaque navire survivant.
- L'adversaire notifiera le concurrent si le tir coule, touche ou manque.
- La partie se termine lorsque tous les navires d'un joueur sont coulés.
Règlement du concours:
- L’esprit de la compétition est de trouver le meilleur algorithme de cuirassé.
- Tout ce qui est jugé contraire à l'esprit de la compétition sera considéré comme un motif de disqualification.
- Interférer avec un adversaire est contraire à l'esprit de la compétition.
- Le multithreading peut être utilisé avec les restrictions suivantes:
- Vous ne pouvez pas exécuter plus d’un thread alors que ce n’est pas votre tour. (Cependant, un nombre quelconque de threads peuvent être dans un état "suspendu").
- Aucun fil ne peut être exécuté avec une priorité autre que "Normal".
- Étant donné les deux restrictions ci-dessus, vous aurez la garantie de disposer d'au moins 3 cœurs de processeur dédiés pendant votre tour.
- Une limite de 1 seconde de temps processeur par partie est attribuée à chaque concurrent sur le fil principal.
- Le manque de temps entraîne la perte de la partie en cours.
- Toute exception non gérée entraînera la perte de la partie en cours.
- L'accès réseau et l'accès au disque sont autorisés, mais vous pouvez trouver les restrictions de temps assez prohibitives. Quelques méthodes de montage et de démontage ont toutefois été ajoutées pour atténuer les contraintes de temps.
- Le code doit être affiché sur le débordement de la pile en tant que réponse ou, s'il est trop volumineux, lié.
- La taille totale maximale (non compressée) d'une entrée est de 1 Mo.
- Officiellement, .Net 2.0 / 3.5 est la seule exigence du cadre.
- Votre entrée doit implémenter l'interface IBattleshipOpponent.
Score:
- Les 51 meilleurs jeux sur 101 jeux sont les gagnants d'un match.
- Tous les concurrents joueront à égalité les uns contre les autres, à tour de rôle.
- La moitié des concurrents disputera ensuite un tournoi en double élimination pour déterminer le vainqueur. (La plus petite puissance de deux qui soit supérieure ou égale à la moitié, en fait.)
- J'utiliserai le cadre TournamentApi pour le tournoi.
- Les résultats seront affichés ici.
- Si vous soumettez plusieurs entrées, seule l'entrée qui obtient le meilleur score est éligible pour le double-élim.
Bonne chance! Amusez-vous!
EDIT 1:
Merci à Libéré , qui a détecté une erreur dans la fonction Ship.IsValid . Cela a été corrigé. Veuillez télécharger la version mise à jour du framework.
EDIT 2:
Étant donné que la persistance des statistiques sur disque, par exemple, a suscité un vif intérêt, j'ai ajouté quelques événements de configuration et de démontage non chronométrés qui devraient fournir les fonctionnalités requises. Il s’agit d’un changement radical . C'est-à-dire que l'interface a été modifiée pour ajouter des fonctions, mais aucun corps n'est requis pour celles-ci. Veuillez télécharger la version mise à jour du framework.
EDIT 3:
Correctif 1: GameWon et GameLost n'étaient appelés que dans le cas d'une pause.
Bug Fix 2: Si un moteur chronométrait à chaque match, la compétition ne se terminerait jamais.
Veuillez télécharger la version mise à jour du framework.
EDIT 4:
Résultats du tournoi:
La solution
J'appuie la motion pour faire beaucoup plus de jeux par match. Faire 50 jeux, c'est lancer une pièce de monnaie. J'avais besoin de faire 1000 jeux pour obtenir une distinction raisonnable entre les algorithmes de test.
Téléchargez Dreadnought 1.2 .
Stratégies:
-
gardez une trace de toutes les positions possibles pour les navires ayant> 0 hits. La liste ne dépasse jamais ~ 30K, elle peut donc être conservée exactement, contrairement à la liste de toutes les positions possibles pour tous les navires (ce qui est très volumineux).
-
L’algorithme GetShot a deux parties, l’une qui génère des tirs aléatoires et l’autre qui tente de finir de couler un navire déjà touché. Nous faisons des tirs au hasard s’il existe une position possible (parmi la liste ci-dessus) dans laquelle tous les navires touchés sont coulés. Sinon, nous essayons de finir de couler un navire en choisissant un endroit où tirer, ce qui élimine le plus de positions possibles (pondéré).
-
Pour les prises de vues aléatoires, calculez le meilleur emplacement à photographier en fonction du risque de chevauchement de l'un des navires non saturés.
-
algorithme adaptatif qui place les navires dans des endroits où l'adversaire est statistiquement moins susceptible de tirer.
-
algorithme adaptatif préférant tirer dans des endroits où l'adversaire est statistiquement plus susceptible de placer ses navires.
-
place les navires pour la plupart ne se touchant pas.
Autres conseils
Voici mon entrée! (La solution la plus naïve possible)
"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() { }
}
}
Voici un adversaire contre lequel jouer:
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 que tout espace non exploré particulier retienne un navire.
Pour ce faire, vous explorerez toutes les configurations possibles de navires qui correspondent à votre vision actuelle du monde, puis calculerez des probabilités en fonction de ces configurations. Vous pourriez penser à cela comme explorer un arbre:
extension des états de cuirassés possibles http://natekohl.net/media/battleship-tree.png
Après avoir examiné toutes les feuilles de cet arbre qui concordent avec ce que vous savez du monde (par exemple, les navires ne peuvent pas se chevaucher, tous les grands carrés doivent être des navires, etc.). vous pouvez compter le nombre de navires se produire à chaque position inexplorée pour estimer la probabilité qu’un navire soit assis à cet endroit.
Ceci peut être visualisé comme une carte thermique, où les points chauds sont plus susceptibles de contenir des navires:
Ce que j'aime dans cette compétition Battleship, c’est que l’arbre ci-dessus est presque assez petit pour forcer ce type d’algorithme. S'il y a environ 150 positions possibles pour chacun des 5 navires, cela équivaut à 150 5 = 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 est encore trop gros pour entrer en moins d'une seconde. Il tente cependant d’estimer ces probabilités à l’aide de quelques heuristiques.
Ce n’est pas une réponse à part entière, mais il semble inutile d’encombrer les vraies réponses avec du code commun. Je présente donc quelques extensions / classes générales dans l’esprit open source. Si vous les utilisez, veuillez modifier l’espace de nom ou essayer de tout compiler dans une dll ne fonctionnera pas.
BoardView vous permet de travailler facilement avec un tableau annoté.
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 celles-ci dupliquent des fonctionnalités dans le cadre principal, mais devraient être réalisées par vous-même.
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 que je finis par utiliser beaucoup.
enum OpponentsBoardState
{
Unknown = 0,
Miss,
MustBeEmpty,
Hit,
}
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!");
}
}
}
Je n'ai pas encore le temps d'écrire un algorithme complet, mais voici une pensée: si votre adversaire place des vaisseaux de manière aléatoire, les probabilités de placement ne seraient-elles pas une simple distribution centrée à (5.5.5.5)? Par exemple, les possibilités de placement du cuirassé (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 une distribution aussi importante, mais votre meilleure hypothèse reste le centre. Après cela, l’approche mathématique émettrait lentement des diagonales (peut-être avec la longueur du navire moyen, 17/5) hors du centre. Ex:
...........
....x.x....
.....x.....
....x.x....
...........
Évidemment, il faudrait ajouter un peu de hasard à l'idée, mais je pense que c'est purement mathématique que c'est la voie à suivre.
Rien d’aussi sophistiqué que ce que j’ai imaginé. Il bat l'adversaire au hasard 99,9% du temps. Serait intéressé si quelqu'un a d'autres petits défis comme celui-ci, c'était bien amusant.
namespace Battleship
{
using System;
using System.Collections.ObjectModel;
using System.Drawing;
using System.Collections.Generic;
using System.Linq;
public class AgentSmith : IBattleshipOpponent
{
public string Name { get { return "Agent Smith"; } }
public Version Version { get { return this.version; } }
private Random rand = new Random();
private Version version = new Version(2, 1);
private Size gameSize;
private enum Direction { Up, Down, Left, Right }
private int MissCount;
private Point?[] EndPoints = new Point?[2];
private LinkedList<Point> HitShots = new LinkedList<Point>();
private LinkedList<Point> Shots = new LinkedList<Point>();
private List<Point> PatternShots = new List<Point>();
private Direction ShotDirection = Direction.Up;
private void NullOutTarget()
{
EndPoints = new Point?[2];
MissCount = 0;
}
private void SetupPattern()
{
for (int y = 0; y < gameSize.Height; y++)
for (int x = 0; x < gameSize.Width; x++)
if ((x + y) % 2 == 0) PatternShots.Add(new Point(x, y));
}
private bool InvalidShot(Point p)
{
bool InvalidShot = (Shots.Where(s => s.X == p.X && s.Y == p.Y).Any());
if (p.X < 0 | p.Y<0) InvalidShot = true;
if (p.X >= gameSize.Width | p.Y >= gameSize.Height) InvalidShot = true;
return InvalidShot;
}
private Point FireDirectedShot(Direction? direction, Point p)
{
ShotDirection = (Direction)direction;
switch (ShotDirection)
{
case Direction.Up: p.Y--; break;
case Direction.Down: p.Y++; break;
case Direction.Left: p.X--; break;
case Direction.Right: p.X++; break;
}
return p;
}
private Point FireAroundPoint(Point p)
{
if (!InvalidShot(FireDirectedShot(ShotDirection,p)))
return FireDirectedShot(ShotDirection, p);
Point testShot = FireDirectedShot(Direction.Left, p);
if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Right, p); }
if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Up, p); }
if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Down, p); }
return testShot;
}
private Point FireRandomShot()
{
Point p;
do
{
if (PatternShots.Count > 0)
PatternShots.Remove(p = PatternShots[rand.Next(PatternShots.Count)]);
else do
{
p = FireAroundPoint(HitShots.First());
if (InvalidShot(p)) HitShots.RemoveFirst();
} while (InvalidShot(p) & HitShots.Count > 0);
}
while (InvalidShot(p));
return p;
}
private Point FireTargettedShot()
{
Point p;
do
{
p = FireAroundPoint(new Point(EndPoints[1].Value.X, EndPoints[1].Value.Y));
if (InvalidShot(p) & EndPoints[1] != EndPoints[0])
EndPoints[1] = EndPoints[0];
else if (InvalidShot(p)) NullOutTarget();
} while (InvalidShot(p) & EndPoints[1] != null);
if (InvalidShot(p)) p = FireRandomShot();
return p;
}
private void ResetVars()
{
Shots.Clear();
HitShots.Clear();
PatternShots.Clear();
MissCount = 0;
}
public void NewGame(Size size, TimeSpan timeSpan)
{
gameSize = size;
ResetVars();
SetupPattern();
}
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()
{
if (EndPoints[1] != null) Shots.AddLast(FireTargettedShot());
else Shots.AddLast(FireRandomShot());
return Shots.Last();
}
public void ShotHit(Point shot, bool sunk)
{
HitShots.AddLast(shot);
MissCount = 0;
EndPoints[1] = shot;
if (EndPoints[0] == null) EndPoints[0] = shot;
if (sunk) NullOutTarget();
}
public void ShotMiss(Point shot)
{
if (++MissCount == 6) NullOutTarget();
}
public void GameWon() { }
public void GameLost() { }
public void NewMatch(string opponent) { }
public void OpponentShot(Point shot) { }
public void MatchOver() { }
}
}
Légèrement condensé pour occuper un minimum de place ici tout en restant lisible.
Quelques commentaires sur le moteur de compétition:
Paramètres NewGame:
Si IBattleshipOpponent :: NewGame est conçu pour une configuration d’avant-match et prend une taille de plateau, il doit également afficher une liste des navires et leurs tailles respectives. Cela n’a aucun sens de permettre une taille de carte variable sans permettre une configuration de navire variable.
Les navires sont scellés:
Je ne vois aucune raison pour laquelle la classe Ship est scellée. Entre autres choses de base, j'aimerais que Ships ait un nom pour pouvoir envoyer des messages tels que ("Vous avez coulé mon {0}", ship.Name); . J'ai aussi d'autres extensions en tête, alors je pense que Ship devrait être héritable.
Limites de temps:
Bien que la limite de temps d'une seconde soit logique pour une règle de tournoi, elle gâche totalement le débogage. BattleshipCompetition devrait avoir un paramètre facile pour ignorer les violations de temps afin d'aider au développement / débogage. Je suggérerais également d’enquêter sur System.Diagnostics.Process :: UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime pour obtenir une vue plus précise du temps utilisé.
Navires coulés:
L'API actuelle vous informe lorsque vous avez coulé le navire d'un oppenent:
ShotHit(Point shot, bool sunk);
mais pas le navire que vous avez coulé! Je considère comme faisant partie des règles relatives au cuirassé humain que vous devez déclarer "Vous avez coulé mon cuirassé!" (ou destroyer, ou sous, etc.).
Cela est particulièrement critique lorsqu'une IA tente de débusquer des navires qui s'affrontent. J'aimerais demander un changement d'API en:
ShotHit(Point shot, Ship ship);
Si navire n'est pas nul, cela signifie que le tir était un tir au ras du sol, et vous savez quel navire vous avez coulé et combien de temps il a été. Si le tir était un tir non-sombrant, le navire est nul et vous n’avez aucune autre information.
CrossFire mis à jour. Je sais qu'il ne peut rivaliser avec Farnsworth ou Dreadnought, mais il est beaucoup plus rapide que ce dernier et simple à jouer au cas où quelqu'un voudrait essayer. Cela dépend de l'état actuel de mes bibliothèques, inclus ici pour faciliter l'utilisation.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.IO;
using System.Collections.ObjectModel;
namespace Battleship.ShuggyCoUk
{
public class Simple : IBattleshipOpponent
{
BoardView<OpponentsBoardState> opponentsBoard = new BoardView<OpponentsBoardState>(new Size(10,10));
Rand rand = new Rand();
int gridOddEven;
Size size;
public string Name { get { return "Simple"; } }
public Version Version { get { return new Version(2, 1); }}
public void NewMatch(string opponent) {}
public void NewGame(System.Drawing.Size size, TimeSpan timeSpan)
{
this.size = size;
this.opponentsBoard = new BoardView<OpponentsBoardState>(size);
this.gridOddEven = rand.Pick(new[] { 0, 1 });
}
public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection<Ship> ships)
{
BoardView<bool> board = new BoardView<bool>(size);
var AllOrientations = new[] {
ShipOrientation.Horizontal,
ShipOrientation.Vertical };
foreach (var ship in ships)
{
int avoidTouching = 3;
while (!ship.IsPlaced)
{
var l = rand.Pick(board.Select(c => c.Location));
var o = rand.Pick(AllOrientations);
if (ship.IsLegal(ships, size, l, o))
{
if (ship.IsTouching(ships, l, o)&& --avoidTouching > 0)
continue;
ship.Place(l, o);
}
}
}
}
protected virtual Point PickWhenNoTargets()
{
return rand.PickBias(x => x.Bias,
opponentsBoard
// nothing 1 in size
.Where(c => (c.Location.X + c.Location.Y) % 2 == gridOddEven)
.Where(c => c.Data == OpponentsBoardState.Unknown))
.Location;
}
private int SumLine(Cell<OpponentsBoardState> c, int acc)
{
if (acc >= 0)
return acc;
if (c.Data == OpponentsBoardState.Hit)
return acc - 1;
return -acc;
}
public System.Drawing.Point GetShot()
{
var targets = opponentsBoard
.Where(c => c.Data == OpponentsBoardState.Hit)
.SelectMany(c => c.Neighbours())
.Where(c => c.Data == OpponentsBoardState.Unknown)
.ToList();
if (targets.Count > 1)
{
var lines = targets.Where(
x => x.FoldAll(-1, SumLine).Select(r => Math.Abs(r) - 1).Max() > 1).ToList();
if (lines.Count > 0)
targets = lines;
}
var target = targets.RandomOrDefault(rand);
if (target == null)
return PickWhenNoTargets();
return target.Location;
}
public void OpponentShot(System.Drawing.Point shot)
{
}
public void ShotHit(Point shot, bool sunk)
{
opponentsBoard[shot] = OpponentsBoardState.Hit;
Debug(shot, sunk);
}
public void ShotMiss(Point shot)
{
opponentsBoard[shot] = OpponentsBoardState.Miss;
Debug(shot, false);
}
public const bool DebugEnabled = false;
public void Debug(Point shot, bool sunk)
{
if (!DebugEnabled)
return;
opponentsBoard.WriteAsGrid(
Console.Out,
x =>
{
string t;
switch (x.Data)
{
case OpponentsBoardState.Unknown:
return " ";
case OpponentsBoardState.Miss:
t = "m";
break;
case OpponentsBoardState.MustBeEmpty:
t = "/";
break;
case OpponentsBoardState.Hit:
t = "x";
break;
default:
t = "?";
break;
}
if (x.Location == shot)
t = t.ToUpper();
return t;
});
if (sunk)
Console.WriteLine("sunk!");
Console.ReadLine();
}
public void GameWon()
{
}
public void GameLost()
{
}
public void MatchOver()
{
}
#region Library code
enum OpponentsBoardState
{
Unknown = 0,
Miss,
MustBeEmpty,
Hit,
}
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
}
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!");
}
}
#endregion
}
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, Battleship.ShuggyCoUk.Simple.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, Battleship.ShuggyCoUk.Simple.Rand rand)
{
int count = things.Count();
if (count == 0)
return default(T);
return things.ElementAt(rand.Next(count));
}
}
}
C’est à peu près tout ce que je pourrais faire de mieux pendant mon temps libre, ce qui est à peu près inexistant. Il y a des statistiques de pointage et de match en cours, alors que je configure la fonction principale pour qu'elle exécute en boucle et continue la bataille de bataille jusqu'à ce que j'appuie sur une touche.
namespace Battleship
{
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
public class BP7 : IBattleshipOpponent
{
public string Name { get { return "BP7"; } }
public Version Version { get { return this.version; } }
Random rand = new Random();
Version version = new Version(0, 7);
Size gameSize;
List<Point> scanShots;
List<NextShot> nextShots;
int wins, losses;
int totalWins = 0;
int totalLosses = 0;
int maxWins = 0;
int maxLosses = 0;
int matchWins = 0;
int matchLosses = 0;
public enum Direction { VERTICAL = -1, UNKNOWN = 0, HORIZONTAL = 1 };
Direction hitDirection, lastShotDirection;
enum ShotResult { UNKNOWN, MISS, HIT };
ShotResult[,] board;
public struct NextShot
{
public Point point;
public Direction direction;
public NextShot(Point p, Direction d)
{
point = p;
direction = d;
}
}
public struct ScanShot
{
public Point point;
public int openSpaces;
public ScanShot(Point p, int o)
{
point = p;
openSpaces = o;
}
}
public void NewGame(Size size, TimeSpan timeSpan)
{
this.gameSize = size;
scanShots = new List<Point>();
nextShots = new List<NextShot>();
fillScanShots();
hitDirection = Direction.UNKNOWN;
board = new ShotResult[size.Width, size.Height];
}
private void fillScanShots()
{
int x;
for (x = 0; x < gameSize.Width - 1; x++)
{
scanShots.Add(new Point(x, x));
}
if (gameSize.Width == 10)
{
for (x = 0; x < 3; x++)
{
scanShots.Add(new Point(9 - x, x));
scanShots.Add(new Point(x, 9 - x));
}
}
}
public void PlaceShips(System.Collections.ObjectModel.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()
{
Point shot;
if (this.nextShots.Count > 0)
{
if (hitDirection != Direction.UNKNOWN)
{
if (hitDirection == Direction.HORIZONTAL)
{
this.nextShots = this.nextShots.OrderByDescending(x => x.direction).ToList();
}
else
{
this.nextShots = this.nextShots.OrderBy(x => x.direction).ToList();
}
}
shot = this.nextShots.First().point;
lastShotDirection = this.nextShots.First().direction;
this.nextShots.RemoveAt(0);
return shot;
}
List<ScanShot> scanShots = new List<ScanShot>();
for (int x = 0; x < gameSize.Width; x++)
{
for (int y = 0; y < gameSize.Height; y++)
{
if (board[x, y] == ShotResult.UNKNOWN)
{
scanShots.Add(new ScanShot(new Point(x, y), OpenSpaces(x, y)));
}
}
}
scanShots = scanShots.OrderByDescending(x => x.openSpaces).ToList();
int maxOpenSpaces = scanShots.FirstOrDefault().openSpaces;
List<ScanShot> scanShots2 = new List<ScanShot>();
scanShots2 = scanShots.Where(x => x.openSpaces == maxOpenSpaces).ToList();
shot = scanShots2[rand.Next(scanShots2.Count())].point;
return shot;
}
int OpenSpaces(int x, int y)
{
int ctr = 0;
Point p;
// spaces to the left
p = new Point(x - 1, y);
while (p.X >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.X--;
}
// spaces to the right
p = new Point(x + 1, y);
while (p.X < gameSize.Width && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.X++;
}
// spaces to the top
p = new Point(x, y - 1);
while (p.Y >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.Y--;
}
// spaces to the bottom
p = new Point(x, y + 1);
while (p.Y < gameSize.Height && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.Y++;
}
return ctr;
}
public void NewMatch(string opponenet)
{
wins = 0;
losses = 0;
}
public void OpponentShot(Point shot) { }
public void ShotHit(Point shot, bool sunk)
{
board[shot.X, shot.Y] = ShotResult.HIT;
if (!sunk)
{
hitDirection = lastShotDirection;
if (shot.X != 0)
{
this.nextShots.Add(new NextShot(new Point(shot.X - 1, shot.Y), Direction.HORIZONTAL));
}
if (shot.Y != 0)
{
this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y - 1), Direction.VERTICAL));
}
if (shot.X != this.gameSize.Width - 1)
{
this.nextShots.Add(new NextShot(new Point(shot.X + 1, shot.Y), Direction.HORIZONTAL));
}
if (shot.Y != this.gameSize.Height - 1)
{
this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y + 1), Direction.VERTICAL));
}
}
else
{
hitDirection = Direction.UNKNOWN;
this.nextShots.Clear(); // so now this works like gangbusters ?!?!?!?!?!?!?!?!?
}
}
public void ShotMiss(Point shot)
{
board[shot.X, shot.Y] = ShotResult.MISS;
}
public void GameWon()
{
wins++;
}
public void GameLost()
{
losses++;
}
public void MatchOver()
{
if (wins > maxWins)
{
maxWins = wins;
}
if (losses > maxLosses)
{
maxLosses = losses;
}
totalWins += wins;
totalLosses += losses;
if (wins >= 51)
{
matchWins++;
}
else
{
matchLosses++;
}
}
public void FinalStats()
{
Console.WriteLine("Games won: " + totalWins.ToString());
Console.WriteLine("Games lost: " + totalLosses.ToString());
Console.WriteLine("Game winning percentage: " + (totalWins * 1.0 / (totalWins + totalLosses)).ToString("P"));
Console.WriteLine("Game losing percentage: " + (totalLosses * 1.0 / (totalWins + totalLosses)).ToString("P"));
Console.WriteLine();
Console.WriteLine("Matches won: " + matchWins.ToString());
Console.WriteLine("Matches lost: " + matchLosses.ToString());
Console.WriteLine("Match winning percentage: " + (matchWins * 1.0 / (matchWins + matchLosses)).ToString("P"));
Console.WriteLine("Match losing percentage: " + (matchLosses * 1.0 / (matchWins + matchLosses)).ToString("P"));
Console.WriteLine("Match games won high: " + maxWins.ToString());
Console.WriteLine("Match games lost high: " + maxLosses.ToString());
Console.WriteLine();
}
}
}
Cette logique est la plus proche de ma victoire sur Dreadnought, remportant environ 41% des matchs individuels. (En réalité, il a remporté un match sur un compte de 52 à 49.) Curieusement, cette classe ne réussit pas aussi bien contre FarnsworthOpponent qu'une version antérieure beaucoup moins avancée.
dell est en train de réparer mon ordinateur, mais c’est là où j’étais la semaine dernière:
namespace Battleship
{
using System;
using System.Collections.ObjectModel;
using System.Drawing;
using System.Collections.Generic;
using System.Linq;
public class BSKiller4 : OpponentExtended, IBattleshipOpponent
{
public string Name { get { return "BSKiller4"; } }
public Version Version { get { return this.version; } }
public bool showBoard = false;
Random rand = new Random();
Version version = new Version(0, 4);
Size gameSize;
List<Point> nextShots;
Queue<Point> scanShots;
char[,] board;
private void printBoard()
{
Console.WriteLine();
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
Console.Write(this.board[x, y]);
}
Console.WriteLine();
}
Console.ReadKey();
}
public void NewGame(Size size, TimeSpan timeSpan)
{
this.gameSize = size;
board = new char[size.Width, size.Height];
this.nextShots = new List<Point>();
this.scanShots = new Queue<Point>();
fillScanShots();
initializeBoard();
}
private void initializeBoard()
{
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
this.board[x, y] = 'O';
}
}
}
private void fillScanShots()
{
int x, y;
int num = gameSize.Width * gameSize.Height;
for (int j = 0; j < 3; j++)
{
for (int i = j; i < num; i += 3)
{
x = i % gameSize.Width;
y = i / gameSize.Height;
scanShots.Enqueue(new Point(x, y));
}
}
}
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()
{
if (showBoard) printBoard();
Point shot;
shot = findShotRun();
if (shot.X != -1)
{
return shot;
}
if (this.nextShots.Count > 0)
{
shot = this.nextShots[0];
this.nextShots.RemoveAt(0);
}
else
{
shot = this.scanShots.Dequeue();
}
return shot;
}
public void ShotHit(Point shot, bool sunk)
{
this.board[shot.X, shot.Y] = 'H';
if (!sunk)
{
addToNextShots(new Point(shot.X - 1, shot.Y));
addToNextShots(new Point(shot.X, shot.Y + 1));
addToNextShots(new Point(shot.X + 1, shot.Y));
addToNextShots(new Point(shot.X, shot.Y - 1));
}
else
{
this.nextShots.Clear();
}
}
private Point findShotRun()
{
int run_forward_horizontal = 0;
int run_backward_horizontal = 0;
int run_forward_vertical = 0;
int run_backward_vertical = 0;
List<shotPossibilities> possible = new List<shotPossibilities>(5);
// this only works if width = height for the board;
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
// forward horiz
if (this.board[x, y] == 'M')
{
run_forward_horizontal = 0;
}
else if (this.board[x, y] == 'O')
{
if (run_forward_horizontal >= 2)
{
possible.Add(
new shotPossibilities(
run_forward_horizontal,
new Point(x, y),
true));
}
else
{
run_forward_horizontal = 0;
}
}
else
{
run_forward_horizontal++;
}
// forward vertical
if (this.board[y, x] == 'M')
{
run_forward_vertical = 0;
}
else if (this.board[y, x] == 'O')
{
if (run_forward_vertical >= 2)
{
possible.Add(
new shotPossibilities(
run_forward_vertical,
new Point(y, x),
false));
}
else
{
run_forward_vertical = 0;
}
}
else
{
run_forward_vertical++;
}
// backward horiz
if (this.board[this.gameSize.Width - x - 1, y] == 'M')
{
run_backward_horizontal = 0;
}
else if (this.board[this.gameSize.Width - x - 1, y] == 'O')
{
if (run_backward_horizontal >= 2)
{
possible.Add(
new shotPossibilities(
run_backward_horizontal,
new Point(this.gameSize.Width - x - 1, y),
true));
}
else
{
run_backward_horizontal = 0;
}
}
else
{
run_backward_horizontal++;
}
// backward vertical
if (this.board[y, this.gameSize.Height - x - 1] == 'M')
{
run_backward_vertical = 0;
}
else if (this.board[y, this.gameSize.Height - x - 1] == 'O')
{
if (run_backward_vertical >= 2)
{
possible.Add(
new shotPossibilities(
run_backward_vertical,
new Point(y, this.gameSize.Height - x - 1),
false));
}
else
{
run_backward_vertical = 0;
}
}
else
{
run_backward_vertical++;
}
}
run_forward_horizontal = 0;
run_backward_horizontal = 0;
run_forward_vertical = 0;
run_backward_vertical = 0;
}
Point shot;
if (possible.Count > 0)
{
shotPossibilities shotp = possible.OrderByDescending(a => a.run).First();
//this.nextShots.Clear();
shot = shotp.shot;
//if (shotp.isHorizontal)
//{
// this.nextShots.RemoveAll(p => p.X != shot.X);
//}
//else
//{
// this.nextShots.RemoveAll(p => p.Y != shot.Y);
//}
}
else
{
shot = new Point(-1, -1);
}
return shot;
}
private void addToNextShots(Point p)
{
if (!this.nextShots.Contains(p) &&
p.X >= 0 &&
p.X < this.gameSize.Width &&
p.Y >= 0 &&
p.Y < this.gameSize.Height)
{
if (this.board[p.X, p.Y] == 'O')
{
this.nextShots.Add(p);
}
}
}
public void GameWon()
{
this.GameWins++;
}
public void NewMatch(string opponent)
{
System.Threading.Thread.Sleep(5);
this.rand = new Random(System.Environment.TickCount);
}
public void OpponentShot(Point shot) { }
public void ShotMiss(Point shot)
{
this.board[shot.X, shot.Y] = 'M';
}
public void GameLost()
{
if (showBoard) Console.WriteLine("-----Game Over-----");
}
public void MatchOver() { }
}
public class OpponentExtended
{
public int GameWins { get; set; }
public int MatchWins { get; set; }
public OpponentExtended() { }
}
public class shotPossibilities
{
public shotPossibilities(int r, Point s, bool h)
{
this.run = r;
this.shot = s;
this.isHorizontal = h;
}
public int run { get; set; }
public Point shot { get; set; }
public bool isHorizontal { get; set; }
}
}
Si vous forcez brutalement votre analyse, le mécanisme de RandomOpponent fourni peut s'avérer extrêmement inefficace. Il se permet de resélectionner des emplacements déjà ciblés et permet au framework de le forcer à se répéter jusqu’à atteindre un emplacement qu’il n’a pas encore touché ou la limite de temps par déplacement expire.
Cet adversaire a un comportement similaire (la distribution de placement effective est identique), il vérifie simplement l'intégrité et ne consomme qu'une génération de nombre aléatoire par appel (amorti)).
Ceci utilise les classes de ma réponse extensions / library et je ne fournis que les méthodes / états clés.
La lecture aléatoire est extraite de la réponse de Jon Skeet ici
class WellBehavedRandomOpponent : IBattleShipOpponent
{
Rand rand = new Rand();
List<Point> guesses;
int nextGuess = 0;
public void PlaceShips(IEnumerable<Ship> ships)
{
BoardView<bool> board = new BoardView<bool>(BoardSize);
var AllOrientations = new[] {
ShipOrientation.Horizontal,
ShipOrientation.Vertical };
foreach (var ship in ships)
{
while (!ship.IsPlaced)
{
var l = rand.Pick(board.Select(c => c.Location));
var o = rand.Pick(AllOrientations);
if (ship.IsLegal(ships, BoardSize, l, o))
ship.Place(l, o);
}
}
}
public void NewGame(Size size, TimeSpan timeSpan)
{
var board = new BoardView<bool>(size);
this.guesses = new List<Point>(
board.Select(x => x.Location).Shuffle(rand));
nextGuess = 0;
}
public System.Drawing.Point GetShot()
{
return guesses[nextGuess++];
}
// empty methods left out
}
Je ne pourrai pas participer, mais voici l'algorithme que je mettrais en œuvre si j'avais le temps:
Tout d'abord, lorsque je détecte un impact, je ne poursuis pas le reste du navire. Je construis un tableau des emplacements des navires et je détermine si j'ai touché les cinq au moins une fois avant de commencer à les couler complètement. (Notez qu'il s'agit d'une mauvaise politique pour la variante à prises multiples - voir les commentaires.)
- Touchez le centre (voir la note finale ci-dessous - "centre" est simplement une commodité pour la description)
- Appuyez sur le point 4 à droite du centre
- Appuyez sur les points 1 et 1 à la droite du centre
- Appuyez à l'endroit quatre à droite du précédent hit
-
Continuez dans cette configuration (devrait se terminer par des lignes diagonales séparées par 3 espaces remplissant la planche) Cela devrait toucher tous les bateaux de 4 et 5 longueurs, et un nombre statistiquement important de 3 et 2 bateaux.
-
Commencez à frapper au hasard des points entre les diagonales. Les bateaux de 2 et 3 longueurs qui n’ont pas déjà été remarqués seront capturés.
Une fois que j'ai détecté 5 coups sûrs, je déterminerais s'ils sont sur des bateaux séparés. Ceci est relativement facile en effectuant quelques coups de plus près des emplacements où deux hits sont sur la même ligne horizontale ou verticale et se trouvent à 5 emplacements l'un de l'autre (il peut s'agir de deux hits sur le même bateau). S'il s'agit de bateaux séparés, continuez à couler tous les navires. S'il s'avère qu'il s'agit du même bateau, poursuivez les opérations de remplissage ci-dessus jusqu'à ce que les 5 bateaux soient localisés.
Cet algorithme est un algorithme de remplissage simple. La principale caractéristique est que le système ne perd pas de temps à couler des navires dont il a connaissance lorsqu'il ignore encore certains navires, et qu'il n'utilise pas un schéma de remplissage inefficace (un schéma totalement aléatoire constituerait un gaspillage).
Notes finales:
A) " Centre " est un point de départ aléatoire sur le tableau. Cela élimine la principale faiblesse de cet algorithme. B) Bien que la description indique que les diagonales sont dessinées immédiatement dès le début, l’algorithme tire simplement sur des emplacements «aléatoires» situés le long de ces diagonales. Cela permet d’empêcher le concurrent de déterminer le temps qu’il faudra avant que ses navires soient touchés par des tendances prévisibles.
Ceci décrit un algorithme "parfait" dans le sens où il obtiendra tous les navires sous (9x9) / 2 + 10 coups.
Toutefois, cela peut être amélioré de manière significative:
Une fois qu'un navire est touché, identifiez sa taille avant de faire les lignes diagonales "internes". Vous avez peut-être trouvé le navire 2, auquel cas les diagonales internes peuvent être simplifiées pour trouver les navires de taille 3 plus rapidement.
Identifiez les étapes du jeu et agissez en conséquence. Cet algorithme peut être utile jusqu’à un certain point dans le jeu, mais d’autres algorithmes peuvent offrir de meilleurs avantages dans le cadre de la phase finale. En outre, si l'autre joueur est sur le point de vous vaincre, un autre algorithme pourrait fonctionner mieux - par exemple, un algorithme à haut risque pourrait échouer plus souvent, mais si cela fonctionne, il fonctionne rapidement et vous pouvez battre votre adversaire qui est plus proche de gagner que vous. .
Identifiez le style de jeu du compétiteur - cela peut vous donner des indices sur la manière dont il planifie le placement des navires (c’est-à-dire qu'il est probable que leur propre algorithme identifie plus rapidement la manière dont ils placent leurs propres navires - si le seul outil dont vous disposez est un marteau, tout ressemble à un clou)
-Adam
Mon entrée.
Rien de très spécial, et je n’ai pas eu le temps d’ajouter toutes les bonnes idées que j’avais.
Mais cela semble plutôt bien jouer. Nous verrons comment ça se passe en compétition:
(mettez ceci dans le fichier Missouri.cs et ajouté au projet.)
using System;
using System.Collections.ObjectModel;
using System.Drawing;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace Battleship
{
// The Empire of Japan surrendered on the deck of the USS Missouri on Sept. 2, 1945
public class USSMissouri : IBattleshipOpponent
{
public String Name { get { return name; } }
public Version Version { get { return ver; } }
#region IBattleship Interface
// IBattleship::NewGame
public void NewGame(Size gameSize, TimeSpan timeSpan)
{
size = gameSize;
shotBoard = new ShotBoard(size);
attackVector = new Stack<Attack>();
}
// IBattleship::PlaceShips
public void PlaceShips(ReadOnlyCollection<Ship> ships)
{
HunterBoard board;
targetBoards = new List<HunterBoard>();
shotBoard = new ShotBoard(size);
foreach (Ship s in ships)
{
board = new HunterBoard(this, size, s);
targetBoards.Add(board);
// REWRITE: to ensure valid board placement.
s.Place(
new Point(
rand.Next(size.Width),
rand.Next(size.Height)),
(ShipOrientation)rand.Next(2));
}
}
// IBattleship::GetShot
public Point GetShot()
{
Point p = new Point();
if (attackVector.Count() > 0)
{
p = ExtendShot();
return p;
}
// Contemplate a shot at every-single point, and measure how effective it would be.
Board potential = new Board(size);
for(p.Y=0; p.Y<size.Height; ++p.Y)
{
for(p.X=0; p.X<size.Width; ++p.X)
{
if (shotBoard.ShotAt(p))
{
potential[p] = 0;
continue;
}
foreach(HunterBoard b in targetBoards)
{
potential[p] += b.GetWeightAt(p);
}
}
}
// Okay, we have the shot potential of the board.
// Lets pick a weighted-random spot.
Point shot;
shot = potential.GetWeightedRandom(rand.NextDouble());
shotBoard[shot] = Shot.Unresolved;
return shot;
}
public Point ExtendShot()
{
// Lets consider North, South, East, and West of the current shot.
// and measure the potential of each
Attack attack = attackVector.Peek();
Board potential = new Board(size);
Point[] points = attack.GetNextTargets();
foreach(Point p in points)
{
if (shotBoard.ShotAt(p))
{
potential[p] = 0;
continue;
}
foreach(HunterBoard b in targetBoards)
{
potential[p] += b.GetWeightAt(p);
}
}
Point shot = potential.GetBestShot();
shotBoard[shot] = Shot.Unresolved;
return shot;
}
// IBattleship::NewMatch
public void NewMatch(string opponent)
{
}
public void OpponentShot(Point shot)
{
}
public void ShotHit(Point shot, bool sunk)
{
shotBoard[shot] = Shot.Hit;
if (!sunk)
{
if (attackVector.Count == 0) // This is a first hit, open an attackVector
{
attackVector.Push(new Attack(this, shot));
}
else
{
attackVector.Peek().AddHit(shot); // Add a hit to our current attack.
}
}
// What if it is sunk? Close the top attack, which we've been pursuing.
if (sunk)
{
if (attackVector.Count > 0)
{
attackVector.Pop();
}
}
}
public void ShotMiss(Point shot)
{
shotBoard[shot] = Shot.Miss;
foreach(HunterBoard b in targetBoards)
{
b.ShotMiss(shot); // Update the potential map.
}
}
public void GameWon()
{
Trace.WriteLine ("I won the game!");
}
public void GameLost()
{
Trace.WriteLine ("I lost the game!");
}
public void MatchOver()
{
Trace.WriteLine("This match is over.");
}
#endregion
public ShotBoard theShotBoard
{
get { return shotBoard; }
}
public Size theBoardSize
{
get { return size; }
}
private Random rand = new Random();
private Version ver = new Version(6, 3); // USS Missouri is BB-63, hence version 6.3
private String name = "USS Missouri (abelenky@alum.mit.edu)";
private Size size;
private List<HunterBoard> targetBoards;
private ShotBoard shotBoard;
private Stack<Attack> attackVector;
}
// An Attack is the data on the ship we are currently working on sinking.
// It consists of a set of points, horizontal and vertical, from a central point.
// And can be extended in any direction.
public class Attack
{
public Attack(USSMissouri root, Point p)
{
Player = root;
hit = p;
horzExtent = new Extent(p.X, p.X);
vertExtent = new Extent(p.Y, p.Y);
}
public Extent HorizontalExtent
{
get { return horzExtent; }
}
public Extent VerticalExtent
{
get { return vertExtent; }
}
public Point FirstHit
{
get { return hit; }
}
public void AddHit(Point p)
{
if (hit.X == p.X) // New hit in the vertical direction
{
vertExtent.Min = Math.Min(vertExtent.Min, p.Y);
vertExtent.Max = Math.Max(vertExtent.Max, p.Y);
}
else if (hit.Y == p.Y)
{
horzExtent.Min = Math.Min(horzExtent.Min, p.X);
horzExtent.Max = Math.Max(horzExtent.Max, p.X);
}
}
public Point[] GetNextTargets()
{
List<Point> bors = new List<Point>();
Point p;
p = new Point(hit.X, vertExtent.Min-1);
while (p.Y >= 0 && Player.theShotBoard[p] == Shot.Hit)
{
if (Player.theShotBoard[p] == Shot.Miss)
{
break; // Don't add p to the List 'bors.
}
--p.Y;
}
if (p.Y >= 0 && Player.theShotBoard[p] == Shot.None) // Add next-target only if there is no shot here yet.
{
bors.Add(p);
}
//-------------------
p = new Point(hit.X, vertExtent.Max+1);
while (p.Y < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.Hit)
{
if (Player.theShotBoard[p] == Shot.Miss)
{
break; // Don't add p to the List 'bors.
}
++p.Y;
}
if (p.Y < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.None)
{
bors.Add(p);
}
//-------------------
p = new Point(horzExtent.Min-1, hit.Y);
while (p.X >= 0 && Player.theShotBoard[p] == Shot.Hit)
{
if (Player.theShotBoard[p] == Shot.Miss)
{
break; // Don't add p to the List 'bors.
}
--p.X;
}
if (p.X >= 0 && Player.theShotBoard[p] == Shot.None)
{
bors.Add(p);
}
//-------------------
p = new Point(horzExtent.Max+1, hit.Y);
while (p.X < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.Hit)
{
if (Player.theShotBoard[p] == Shot.Miss)
{
break; // Don't add p to the List 'bors.
}
++p.X;
}
if (p.X < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.None)
{
bors.Add(p);
}
return bors.ToArray();
}
private Point hit;
private Extent horzExtent;
private Extent vertExtent;
private USSMissouri Player;
}
public struct Extent
{
public Extent(Int32 min, Int32 max)
{
Min = min;
Max = max;
}
public Int32 Min;
public Int32 Max;
}
public class Board // The potential-Board, which measures the full potential of each square.
{
// A Board is the status of many things.
public Board(Size boardsize)
{
size = boardsize;
grid = new int[size.Width , size.Height];
Array.Clear(grid,0,size.Width*size.Height);
}
public int this[int c,int r]
{
get { return grid[c,r]; }
set { grid[c,r] = value; }
}
public int this[Point p]
{
get { return grid[p.X, p.Y]; }
set { grid[p.X, p.Y] = value; }
}
public Point GetWeightedRandom(double r)
{
Int32 sum = 0;
foreach(Int32 i in grid)
{
sum += i;
}
Int32 index = (Int32)(r*sum);
Int32 x=0, y=0;
for(y=0; y<size.Height; ++y)
{
for(x=0; x<size.Width; ++x)
{
if (grid[x,y] == 0) continue; // Skip any zero-cells
index -= grid[x,y];
if (index < 0) break;
}
if (index < 0) break;
}
if (x == 10 || y == 10)
throw new Exception("WTF");
return new Point(x,y);
}
public Point GetBestShot()
{
int max=grid[0,0];
for(int y=0; y<size.Height; ++y)
{
for (int x=0; x<size.Width; ++x)
{
max = (grid[x,y] > max)? grid[x,y] : max;
}
}
for(int y=0; y<size.Height; ++y)
{
for (int x=0; x<size.Width; ++x)
{
if (grid[x,y] == max)
{
return new Point(x,y);
}
}
}
return new Point(0,0);
}
public bool IsZero()
{
foreach(Int32 p in grid)
{
if (p > 0)
{
return false;
}
}
return true;
}
public override String ToString()
{
String output = "";
String horzDiv = " +----+----+----+----+----+----+----+----+----+----+\n";
String disp;
int x,y;
output += " A B C D E F G H I J \n" + horzDiv;
for(y=0; y<size.Height; ++y)
{
output += String.Format("{0} ", y+1).PadLeft(3);
for(x=0; x<size.Width; ++x)
{
switch(grid[x,y])
{
case (int)Shot.None: disp = ""; break;
case (int)Shot.Hit: disp = "#"; break;
case (int)Shot.Miss: disp = "."; break;
case (int)Shot.Unresolved: disp = "?"; break;
default: disp = "!"; break;
}
output += String.Format("| {0} ", disp.PadLeft(2));
}
output += "|\n" + horzDiv;
}
return output;
}
protected Int32[,] grid;
protected Size size;
}
public class HunterBoard
{
public HunterBoard(USSMissouri root, Size boardsize, Ship target)
{
size = boardsize;
grid = new int[size.Width , size.Height];
Array.Clear(grid,0,size.Width*size.Height);
Player = root;
Target = target;
Initialize();
}
public void Initialize()
{
int x, y, i;
for(y=0; y<size.Height; ++y)
{
for(x=0; x<size.Width - Target.Length+1; ++x)
{
for(i=0; i<Target.Length; ++i)
{
grid[x+i,y]++;
}
}
}
for(y=0; y<size.Height-Target.Length+1; ++y)
{
for(x=0; x<size.Width; ++x)
{
for(i=0; i<Target.Length; ++i)
{
grid[x,y+i]++;
}
}
}
}
public int this[int c,int r]
{
get { return grid[c,r]; }
set { grid[c,r] = value; }
}
public int this[Point p]
{
get { return grid[p.X, p.Y]; }
set { grid[p.X, p.Y] = value; }
}
public void ShotMiss(Point p)
{
int x,y;
int min, max;
min = Math.Max(p.X-Target.Length+1, 0);
max = Math.Min(p.X, size.Width-Target.Length);
for(x=min; x<=max; ++x)
{
DecrementRow(p.Y, x, x+Target.Length-1);
}
min = Math.Max(p.Y-Target.Length+1, 0);
max = Math.Min(p.Y, size.Height-Target.Length);
for(y=min; y<=max; ++y)
{
DecrementColumn(p.X, y, y+Target.Length-1);
}
grid[p.X, p.Y] = 0;
}
public void ShotHit(Point p)
{
}
public override String ToString()
{
String output = String.Format("Target size is {0}\n", Target.Length);
String horzDiv = " +----+----+----+----+----+----+----+----+----+----+\n";
int x,y;
output += " A B C D E F G H I J \n" + horzDiv;
for(y=0; y<size.Height; ++y)
{
output += String.Format("{0} ", y+1).PadLeft(3);
for(x=0; x<size.Width; ++x)
{
output += String.Format("| {0} ", grid[x,y].ToString().PadLeft(2));
}
output += "|\n" + horzDiv;
}
return output;
}
// If we shoot at point P, how does that affect the potential of the board?
public Int32 GetWeightAt(Point p)
{
int x,y;
int potential = 0;
int min, max;
min = Math.Max(p.X-Target.Length+1, 0);
max = Math.Min(p.X, size.Width-Target.Length);
for(x=min; x<=max; ++x)
{
if (Player.theShotBoard.isMissInRow(p.Y, x, x+Target.Length-1) == false)
{
++potential;
}
}
min = Math.Max(p.Y-Target.Length+1, 0);
max = Math.Min(p.Y, size.Height-Target.Length);
for(y=min; y<=max; ++y)
{
if (Player.theShotBoard.isMissInColumn(p.X, y, y+Target.Length-1) == false)
{
++potential;
}
}
return potential;
}
public void DecrementRow(int row, int rangeA, int rangeB)
{
int x;
for(x=rangeA; x<=rangeB; ++x)
{
grid[x,row] = (grid[x,row]==0)? 0 : grid[x,row]-1;
}
}
public void DecrementColumn(int col, int rangeA, int rangeB)
{
int y;
for(y=rangeA; y<=rangeB; ++y)
{
grid[col,y] = (grid[col,y]==0)? 0 : grid[col,y]-1;
}
}
private Ship Target = null;
private USSMissouri Player;
private Int32[,] grid;
private Size size;
}
public enum Shot
{
None = 0,
Hit = 1,
Miss = 2,
Unresolved = 3
};
public class ShotBoard
{
public ShotBoard(Size boardsize)
{
size = boardsize;
grid = new Shot[size.Width , size.Height];
for(int y=0; y<size.Height; ++y)
{
for(int x=0; x<size.Width; ++x)
{
grid[x,y] = Shot.None;
}
}
}
public Shot this[int c,int r]
{
get { return grid[c,r]; }
set { grid[c,r] = value; }
}
public Shot this[Point p]
{
get { return grid[p.X, p.Y]; }
set { grid[p.X, p.Y] = value; }
}
public override String ToString()
{
String output = "";
String horzDiv = " +----+----+----+----+----+----+----+----+----+----+\n";
String disp;
int x,y;
output += " A B C D E F G H I J \n" + horzDiv;
for(y=0; y<size.Height; ++y)
{
output += String.Format("{0} ", y+1).PadLeft(3);
for(x=0; x<size.Width; ++x)
{
switch(grid[x,y])
{
case Shot.None: disp = ""; break;
case Shot.Hit: disp = "#"; break;
case Shot.Miss: disp = "."; break;
case Shot.Unresolved: disp = "?"; break;
default: disp = "!"; break;
}
output += String.Format("| {0} ", disp.PadLeft(2));
}
output += "|\n" + horzDiv;
}
return output;
}
// Functions to find shots on the board, at a specific point, or in a row or column, within a range
public bool ShotAt(Point p)
{
return !(this[p]==Shot.None);
}
public bool isMissInColumn(int col, int rangeA, int rangeB)
{
for(int y=rangeA; y<=rangeB; ++y)
{
if (grid[col,y] == Shot.Miss)
{
return true;
}
}
return false;
}
public bool isMissInRow(int row, int rangeA, int rangeB)
{
for(int x=rangeA; x<=rangeB; ++x)
{
if (grid[x,row] == Shot.Miss)
{
return true;
}
}
return false;
}
protected Shot[,] grid;
protected Size size;
}
}
Ce n'est pas minimax. En fait, après avoir placé les navires, chaque joueur ne peut-il jouer seul, ce qui lui a pris plusieurs tours pour couler tous les navires adverses? Celui qui a pris moins de tours gagne.
Je ne pense pas qu'il existe de bonnes stratégies générales allant au-delà de la réduction du nombre de tirs de navires et de la réduction du nombre de tirs afin de couvrir les derniers endroits où les navires pourraient se cacher.
Bien sûr, il peut y avoir des contre-stratégies pour tout ce qui n'est pas aléatoire. Mais je ne pense pas qu’il existe des stratégies efficaces contre tous les joueurs possibles.
En fait, je pense que le plus gros problème du puzzle est qu’il s’agit essentiellement de deux coups. Un mouvement consiste à placer vos navires, l'autre à trouver les navires ennemis (aussi segmenté que puisse être cette seconde partie, en plus d'essayer de battre une horloge avec un facteur aléatoire, il s'agit simplement de "lancer votre algorithme"). Il n’existe aucun mécanisme permettant d’essayer de déterminer puis de contrer une stratégie ennemie, c’est ce qui fait que des compétitions similaires reposent sur des séries successives de "ciseaux à papier caillou". assez intéressant.
De plus, je pense qu'il serait plus cool de spécifier le jeu en tant que protocole réseau, puis de fournir le cadre pour l'implémenter en C #, plutôt que d'imposer que toutes les solutions soient en C #, mais ce n'est que mon opinion.
EDIT: J'annule mon point de départ, car je n'ai pas lu assez attentivement les règles du concours.
J'ai toujours aimé commencer au milieu et s'éloigner de ce point, ne laissant qu'un espace vide entre les autres points pour rendre compte de ce putain de sous… l'espace entre les tirs dépendait du navire coulé. si le navire B était le dernier, les tirs ne devaient laisser que 4 espaces entre eux pour minimiser les tirs perdus
Il y avait un concours similaire organisé par le Dr James Heather de l'Université de Surrey pour le compte de la British Computer Society.
Des limites ont été imposées aux ressources: temps de traitement maximal par tour, aucun état ne pouvait être stocké entre les déplacements, taille de segment de mémoire maximale imposée. Pour limiter le temps, l'IA pourrait soumettre un coup à n'importe quel moment de la plage horaire et serait priée de le faire à la fin du tour.
Très intéressant - consultez http://www.bcsstudentcontest.com/
Peut vous donner quelques idées supplémentaires.
Dans l’état actuel, la solution s’ouvre et s’exécute sans modification dans monodevelop sous Ubuntu 9.10 linux
Vous avez écrit:
- Tout ce qui est jugé contraire à l'esprit de la compétition sera considéré comme un motif de disqualification.
- Interférer avec un adversaire est contraire à l'esprit de la compétition.
merci de définir "contre l’esprit du concours" et "interférer avec un adversaire"?
Aussi - pour simplifier, je vous recommande de:
- n'autorise pas l'utilisation du processeur pendant la fente de l'ordinateur de l'adversaire.
- interdit le parallélisme des threads et donne à la place plus de secondes CPU sur un seul thread. Cela simplifiera la programmation de l’intelligence artificielle et ne blessera de toute façon pas les personnes affectées par la CPU / la mémoire.
PS - une question pour les post-doctorants CS qui se cache ici: ce jeu ne peut-il pas être résolu (c’est-à-dire, existe-t-il une seule, la meilleure stratégie?). oui, la taille de la planche et le nombre de marches rendent minimax et al obligatoires, mais je dois quand même me demander ... c’est loin d’être un jeu de cartes et de complexité.
Je prédis que la personne qui réussira à faire de l'ingénierie inverse de ses adversaires gagnera au hasard.
Je ne sais pas quelle est la probabilité que cela se produise.
Il serait vraisemblablement possible d’en exécuter une série avec des variantes du jeu.
Ajouter des choses comme un avion 3D ou être capable de déplacer un seul navire au lieu de tirer pendant un tour changerait probablement le jeu un peu.
Le temps de jeu total d'une seconde est spécifique à la machine. Une seconde d'opération du processeur sera différente sur ma machine par rapport à la machine du tournoi. Si j'optimise l'algorithme Battle Ship pour qu'il utilise le plus de temps processeur en une seconde, il est exécuté sur une machine de tournoi éventuellement plus lente, il perdra toujours.
Je ne suis pas sûr de savoir comment contourner cette limitation du cadre, mais il faut y remédier.
...
Une idée est de faire ce qui a été fait dans ce concours http://www.bcsstudentcontest.com /
Et ayez un temps maximum par tour par opposition au temps total maximum de jeu. De cette façon, je pouvais limiter les algorithmes pour qu'ils tiennent dans un délai de rotation connu. Un jeu peut durer plus de 50 à 600 tours. Si l’algorithme my gère son temps de jeu total, il risque de ne pas lui laisser le temps nécessaire pour faire de son mieux, ou de perdre trop de temps. Il est très difficile de gérer le temps total de jeu dans l'algorithme Battleship.
Je suggérerais de modifier les règles pour limiter le temps de tour et non le temps total de jeu.
Modifier
Si j’écris un algorithme qui énumère tous les plans possibles, puis les classe, prend le plan le plus élevé. Cela prendrait trop de temps pour générer tous les plans possibles, alors je laisserais l'algorithme fonctionner pendant un certain temps puis l'arrêterais.
S'il y avait une limite basée sur les virages, je pouvais laisser l'algorithme s'exécuter pendant 0,9 seconde et renvoyer le tir le plus élevé, tout en respectant le temps imparti.
Si je suis limité au temps de jeu total d'une seconde, il sera difficile de déterminer la durée pendant laquelle l'algorithme doit s'exécuter à chaque tour. Je voudrai maximiser mon temps de calcul. Si une partie durait 500 tours, je pouvais limiter chaque tour à 0,002 seconde, mais si une partie durait 100 tours, je pouvais attribuer à chaque tour 0,01 seconde de temps CPU.
Il serait peu pratique pour un algorithme d’utiliser une recherche semi-exhaustive de l’espace de prise de vue pour trouver la meilleure prise avec la limitation actuelle.
Le temps total de jeu d'une seconde limite le type d'algorithmes pouvant être utilisés efficacement pour rivaliser dans le jeu.
Je m'arrête ici en n'introduisant pas le code réel - mais je vais hasarder quelques observations générales:
- Etant donné que tous les vaisseaux ont au moins 2 cellules, vous pouvez utiliser une optimisation que j'ai constatée dans une implémentation du jeu dans Space Quest V - qui ne déclenche que les cellules en alternance dans un motif en losange pendant qu'elle "recherche". une cible. Ceci élimine la moitié des carrés, tout en garantissant que vous retrouverez tous les navires à terme.
- Un modèle de tir aléatoire lors de la recherche de cibles produira statistiquement les meilleurs résultats sur de nombreux jeux.
! [Densité de probabilité] [1] entrez une description de l'image
! [entrez la description de l'image ici] [2]
J'ai essayé de comparer les résultats du tir au randon avec une chasse / cible stupide et enfin une recherche sophistiquée.
La meilleure solution semble être de créer une fonction de densité de probabilité pour déterminer la probabilité d'utilisation d'un carré individuel par les navires restants, et de viser avec le carré ayant la valeur la plus élevée.
Vous pouvez voir mes résultats ici saisir la description du lien ici
" Battleship " est ce qu'on appelle un problème NP-complet en informatique classique.
http://en.wikipedia.org/wiki/List_of_NP-complete_problems
(cherchez Battleship - c'est là, sous jeux et puzzles)
