¿Cuál es la mejor IA de acorazado?
https://stackoverflow.com/questions/1631414
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¡Acorazado!
En 2003 (cuando tenía 17 años), competí en una codificación Battleship AI competencia. Aunque perdí ese torneo, me divertí mucho y aprendí mucho de él.
Ahora, me gustaría resucitar esta competencia, en busca de la mejor IA de acorazado.
Aquí está el marco, ahora alojado en Bitbucket .
¡El ganador recibirá una reputación de +450! La competencia se llevará a cabo a partir del 17 de noviembre de 2009 . No se aceptarán entradas o ediciones posteriores a la hora cero del día 17. (Hora estándar central) ¡Envíe sus entradas temprano, para que no pierda su oportunidad!
Para mantener este OBJETIVO , siga el espíritu de la competencia.
Reglas del juego:
- El juego se juega en una cuadrícula de 10x10.
- Cada competidor colocará cada uno de los 5 barcos (de esloras 2, 3, 3, 4, 5) en su cuadrícula.
- Ningún barco puede superponerse, pero puede ser adyacente.
- Los competidores luego se turnan para disparar disparos individuales a su oponente.
- Una variación en el juego permite disparar múltiples disparos por volea, uno para cada barco superviviente.
- El oponente notificará al competidor si el tiro se hunde, golpea o falla.
- El juego termina cuando se hunden todas las naves de cualquier jugador.
Reglas de la competencia:
- El espíritu de la competencia es encontrar el mejor algoritmo de Battleship.
- Cualquier cosa que se considere contra el espíritu de la competencia será motivo de descalificación.
- Interferir con un oponente va en contra del espíritu de la competencia.
- El subprocesamiento múltiple se puede usar bajo las siguientes restricciones:
- No se puede ejecutar más de un hilo mientras no sea tu turno. (Sin embargo, cualquier cantidad de subprocesos puede estar en estado "Suspendido").
- Ningún subproceso puede ejecutarse con una prioridad que no sea "Normal".
- Dadas las dos restricciones anteriores, se le garantizará al menos 3 núcleos de CPU dedicados durante su turno.
- Se asigna un límite de 1 segundo de tiempo de CPU por juego a cada competidor en el hilo primario.
- Quedarse sin tiempo resulta en perder el juego actual.
- Cualquier excepción no controlada resultará en la pérdida del juego actual.
- Se permite el acceso a la red y el acceso al disco, pero es posible que las restricciones de tiempo sean bastante prohibitivas. Sin embargo, se han agregado algunos métodos de configuración y desmontaje para aliviar la tensión del tiempo.
- El código debe publicarse en el desbordamiento de pila como respuesta o, si es demasiado grande, vinculado.
- El tamaño total máximo (sin comprimir) de una entrada es de 1 MB.
- Oficialmente, .Net 2.0 / 3.5 es el único requisito de marco.
- Su entrada debe implementar la interfaz IBattleshipOpponent.
Puntaje :
- Los mejores 51 juegos de 101 juegos son los ganadores de un partido.
- Todos los competidores jugarán enfrentados entre sí, al estilo round-robin.
- La mejor mitad de los competidores jugará un torneo de doble eliminación para determinar el ganador. (El poder más pequeño de dos que es mayor o igual a la mitad, en realidad.)
- Usaré el marco TournamentApi para el torneo.
- Los resultados se publicarán aquí.
- Si envía más de una entrada, solo su entrada con la mejor puntuación es elegible para la doble eliminación.
¡Buena suerte! ¡Diviértete!
EDITAR 1:
Gracias a Freed , que ha encontrado un error en la función Ship.IsValid . Ha sido arreglado. Descargue la versión actualizada del marco.
EDITAR 2:
Dado que ha habido un interés significativo en las estadísticas persistentes en el disco y demás, he agregado algunos eventos de configuración y desmontaje no programados que deberían proporcionar la funcionalidad requerida. Este es un cambio semi-rompedor . Es decir: la interfaz se ha modificado para agregar funciones, pero no se requiere ningún cuerpo para ellas. Descargue la versión actualizada del marco.
EDITAR 3:
Corrección de errores 1: GameWon y GameLost solo se llamaban en caso de un tiempo de espera.
Corrección de errores 2: si un motor estuviera agotando cada juego, la competencia nunca terminaría.
Descargue la versión actualizada del marco.
EDITAR 4:
Resultados del torneo:
Solución
Secundo la moción para hacer muchos más juegos por partido. Hacer 50 juegos es solo lanzar una moneda. Necesitaba hacer 1000 juegos para obtener una distinción razonable entre los algoritmos de prueba.
Descargar Dreadnought 1.2 .
Estrategias:
-
realiza un seguimiento de todas las posiciones posibles para barcos que tienen > 0 golpes. La lista nunca se hace más grande que ~ 30K, por lo que puede mantenerse exactamente, a diferencia de la lista de todas las posiciones posibles para todos los barcos (que es muy grande).
-
El algoritmo GetShot tiene dos partes, una que genera disparos aleatorios y la otra que intenta terminar de hundir un barco que ya ha sido golpeado. Hacemos disparos aleatorios si hay una posible posición (de la lista anterior) en la que todos los barcos golpeados están hundidos. De lo contrario, intentamos terminar de hundir un barco eligiendo un lugar para disparar que elimine la mayor cantidad de posiciones posibles (ponderado).
-
Para disparos aleatorios, calcule la mejor ubicación para disparar en función de la probabilidad de que uno de los barcos no hundidos se superponga con la ubicación.
-
algoritmo adaptativo que coloca las naves en lugares donde el oponente es estadísticamente menos propenso a disparar.
-
algoritmo adaptativo que prefiere disparar en lugares donde el oponente es estadísticamente más probable que coloque sus naves.
-
colocar naves en su mayoría sin tocarse.
Otros consejos
¡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() { }
}
}
Aquí hay un oponente para que la gente juegue contra:
En lugar de utilizar una estrategia fija inspirada en la geometría, pensé que sería interesante intentar estimar las probabilidades subyacentes de que un espacio inexplorado en particular contiene una nave.
Para hacer esto bien, exploraría todas las configuraciones posibles de naves que se ajustan a su visión actual del mundo, y luego calcularía las probabilidades basadas en esas configuraciones. Podrías pensar en ello como explorar un árbol:
una expansión de posibles estados de acorazados http://natekohl.net/media/battleship-tree.png
Después de considerar todas las hojas de ese árbol que coinciden con lo que sabes sobre el mundo (por ejemplo, los barcos no pueden superponerse, todos los cuadrados de impacto deben ser barcos, etc.) puedes contar con qué frecuencia los barcos ocurrir en cada posición inexplorada para estimar la probabilidad de que un barco esté sentado allí.
Esto se puede visualizar como un mapa de calor, donde es más probable que los puntos calientes contengan barcos:
Una cosa que me gusta de esta competencia de acorazado es que el árbol de arriba es casi lo suficientemente pequeño como para utilizar este tipo de algoritmo con fuerza bruta. Si hay ~ 150 posiciones posibles para cada una de las 5 naves, eso es 150 5 = 75 mil millones de posibilidades. Y ese número solo se reduce, especialmente si puedes eliminar barcos enteros.
El oponente al que he vinculado anteriormente no explora todo el árbol; 75 mil millones todavía son demasiado grandes para entrar en menos de un segundo. Sin embargo, intenta estimar estas probabilidades con la ayuda de algunas heurísticas.
No es una respuesta completa, pero parece poco útil saturar las respuestas reales con un código común. Por lo tanto, presento algunas extensiones / clases generales en el espíritu del código abierto. Si los usa, cambie el espacio de nombres o intentar compilar todo en un dll no funcionará.
BoardView le permite trabajar fácilmente con un tablero anotado.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.IO;
namespace Battleship.ShuggyCoUk
{
public enum Compass
{
North,East,South,West
}
class Cell<T>
{
private readonly BoardView<T> view;
public readonly int X;
public readonly int Y;
public T Data;
public double Bias { get; set; }
public Cell(BoardView<T> view, int x, int y)
{
this.view = view; this.X = x; this.Y = y; this.Bias = 1.0;
}
public Point Location
{
get { return new Point(X, Y); }
}
public IEnumerable<U> FoldAll<U>(U acc, Func<Cell<T>, U, U> trip)
{
return new[] { Compass.North, Compass.East, Compass.South, Compass.West }
.Select(x => FoldLine(x, acc, trip));
}
public U FoldLine<U>(Compass direction, U acc, Func<Cell<T>, U, U> trip)
{
var cell = this;
while (true)
{
switch (direction)
{
case Compass.North:
cell = cell.North; break;
case Compass.East:
cell = cell.East; break;
case Compass.South:
cell = cell.South; break;
case Compass.West:
cell = cell.West; break;
}
if (cell == null)
return acc;
acc = trip(cell, acc);
}
}
public Cell<T> North
{
get { return view.SafeLookup(X, Y - 1); }
}
public Cell<T> South
{
get { return view.SafeLookup(X, Y + 1); }
}
public Cell<T> East
{
get { return view.SafeLookup(X+1, Y); }
}
public Cell<T> West
{
get { return view.SafeLookup(X-1, Y); }
}
public IEnumerable<Cell<T>> Neighbours()
{
if (North != null)
yield return North;
if (South != null)
yield return South;
if (East != null)
yield return East;
if (West != null)
yield return West;
}
}
class BoardView<T> : IEnumerable<Cell<T>>
{
public readonly Size Size;
private readonly int Columns;
private readonly int Rows;
private Cell<T>[] history;
public BoardView(Size size)
{
this.Size = size;
Columns = size.Width;
Rows = size.Height;
this.history = new Cell<T>[Columns * Rows];
for (int y = 0; y < Rows; y++)
{
for (int x = 0; x < Rows; x++)
history[x + y * Columns] = new Cell<T>(this, x, y);
}
}
public T this[int x, int y]
{
get { return history[x + y * Columns].Data; }
set { history[x + y * Columns].Data = value; }
}
public T this[Point p]
{
get { return history[SafeCalc(p.X, p.Y, true)].Data; }
set { this.history[SafeCalc(p.X, p.Y, true)].Data = value; }
}
private int SafeCalc(int x, int y, bool throwIfIllegal)
{
if (x < 0 || y < 0 || x >= Columns || y >= Rows)
{ if (throwIfIllegal)
throw new ArgumentOutOfRangeException("["+x+","+y+"]");
else
return -1;
}
return x + y * Columns;
}
public void Set(T data)
{
foreach (var cell in this.history)
cell.Data = data;
}
public Cell<T> SafeLookup(int x, int y)
{
int index = SafeCalc(x, y, false);
if (index < 0)
return null;
return history[index];
}
#region IEnumerable<Cell<T>> Members
public IEnumerator<Cell<T>> GetEnumerator()
{
foreach (var cell in this.history)
yield return cell;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public BoardView<U> Transform<U>(Func<T, U> transform)
{
var result = new BoardView<U>(new Size(Columns, Rows));
for (int y = 0; y < Rows; y++)
{
for (int x = 0; x < Columns; x++)
{
result[x,y] = transform(this[x, y]);
}
}
return result;
}
public void WriteAsGrid(TextWriter w)
{
WriteAsGrid(w, "{0}");
}
public void WriteAsGrid(TextWriter w, string format)
{
WriteAsGrid(w, x => string.Format(format, x.Data));
}
public void WriteAsGrid(TextWriter w, Func<Cell<T>,string> perCell)
{
for (int y = 0; y < Rows; y++)
{
for (int x = 0; x < Columns; x++)
{
if (x != 0)
w.Write(",");
w.Write(perCell(this.SafeLookup(x, y)));
}
w.WriteLine();
}
}
#endregion
}
}
Algunas extensiones, algunas de estas funciones duplicadas en el marco principal, pero realmente debería hacerlo usted.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Collections.ObjectModel;
namespace Battleship.ShuggyCoUk
{
public static class Extensions
{
public static bool IsIn(this Point p, Size size)
{
return p.X >= 0 && p.Y >= 0 && p.X < size.Width && p.Y < size.Height;
}
public static bool IsLegal(this Ship ship,
IEnumerable<Ship> ships,
Size board,
Point location,
ShipOrientation direction)
{
var temp = new Ship(ship.Length);
temp.Place(location, direction);
if (!temp.GetAllLocations().All(p => p.IsIn(board)))
return false;
return ships.Where(s => s.IsPlaced).All(s => !s.ConflictsWith(temp));
}
public static bool IsTouching(this Point a, Point b)
{
return (a.X == b.X - 1 || a.X == b.X + 1) &&
(a.Y == b.Y - 1 || a.Y == b.Y + 1);
}
public static bool IsTouching(this Ship ship,
IEnumerable<Ship> ships,
Point location,
ShipOrientation direction)
{
var temp = new Ship(ship.Length);
temp.Place(location, direction);
var occupied = new HashSet<Point>(ships
.Where(s => s.IsPlaced)
.SelectMany(s => s.GetAllLocations()));
if (temp.GetAllLocations().Any(p => occupied.Any(b => b.IsTouching(p))))
return true;
return false;
}
public static ReadOnlyCollection<Ship> MakeShips(params int[] lengths)
{
return new System.Collections.ObjectModel.ReadOnlyCollection<Ship>(
lengths.Select(l => new Ship(l)).ToList());
}
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Rand rand)
{
T[] elements = source.ToArray();
// Note i > 0 to avoid final pointless iteration
for (int i = elements.Length - 1; i > 0; i--)
{
// Swap element "i" with a random earlier element it (or itself)
int swapIndex = rand.Next(i + 1);
T tmp = elements[i];
elements[i] = elements[swapIndex];
elements[swapIndex] = tmp;
}
// Lazily yield (avoiding aliasing issues etc)
foreach (T element in elements)
{
yield return element;
}
}
public static T RandomOrDefault<T>(this IEnumerable<T> things, Rand rand)
{
int count = things.Count();
if (count == 0)
return default(T);
return things.ElementAt(rand.Next(count));
}
}
}
Algo que termino usando mucho.
enum OpponentsBoardState
{
Unknown = 0,
Miss,
MustBeEmpty,
Hit,
}
Aleatorización. Seguro pero comprobable, útil para pruebas.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
namespace Battleship.ShuggyCoUk
{
public class Rand
{
Random r;
public Rand()
{
var rand = System.Security.Cryptography.RandomNumberGenerator.Create();
byte[] b = new byte[4];
rand.GetBytes(b);
r = new Random(BitConverter.ToInt32(b, 0));
}
public int Next(int maxValue)
{
return r.Next(maxValue);
}
public double NextDouble(double maxValue)
{
return r.NextDouble() * maxValue;
}
public T Pick<T>(IEnumerable<T> things)
{
return things.ElementAt(Next(things.Count()));
}
public T PickBias<T>(Func<T, double> bias, IEnumerable<T> things)
{
double d = NextDouble(things.Sum(x => bias(x)));
foreach (var x in things)
{
if (d < bias(x))
return x;
d -= bias(x);
}
throw new InvalidOperationException("fell off the end!");
}
}
}
No tengo tiempo en este momento para escribir un algoritmo completo, pero aquí hay un pensamiento: si su oponente coloca naves al azar, ¿no serían las probabilidades de colocación una distribución simple centrada en (5.5,5.5)? Por ejemplo, las posibilidades de colocación para el acorazado (5 unidades de largo) en la dimensión x están aquí:
x 1 2 3 4 5 6 7 8 9 10
P(x) 2 4 6 8 10 10 8 6 4 2
Los mismos cálculos serían válidos para y. Las otras naves no tendrían una distribución tan pronunciada, pero su mejor suposición sigue siendo el centro. Después de eso, el enfoque matemático estaría irradiando lentamente diagonales (quizás con la longitud del barco promedio, 17/5) fuera del centro. Ej:
...........
....x.x....
.....x.....
....x.x....
...........
Obviamente, habría que agregar algo de aleatoriedad a la idea, pero creo que ese es el camino a seguir puramente matemáticamente.
Nada tan sofisticado pero aquí está lo que se me ocurrió. Le gana al oponente aleatorio el 99.9% del tiempo. Me interesaría si alguien tiene otros pequeños desafíos como este, fue muy divertido.
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() { }
}
}
Ligeramente condensado para ocupar un espacio mínimo aquí y aún ser legible.
Algunos comentarios sobre el motor de competencia:
Parámetros de NewGame:
Si IBattleshipOpponent :: NewGame está destinado a la configuración previa al juego y toma un tamaño de tabla, también debe tomar una lista de barcos y sus respectivos tamaños. No tiene sentido permitir un tamaño de tabla variable sin permitir configuraciones de nave variables.
Las naves están selladas:
No veo ninguna razón por la cual la nave de clase esté sellada. Entre otras cosas básicas, me gustaría que Ships tenga un Nombre, para que pueda enviar mensajes como (" Usted hundió mi {0} " ;, ship.Name); . También tengo otras extensiones en mente, así que creo que Ship debería ser heredable.
Límites de tiempo:
Si bien el límite de tiempo de 1 segundo tiene sentido para una regla de torneo, se mete totalmente con la depuración. BattleshipCompetition debe tener una configuración fácil para ignorar las violaciones de tiempo para ayudar con el desarrollo / depuración. También sugeriría investigar System.Diagnostics.Process :: UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime para obtener una vista más precisa de cuánto tiempo se está utilizando.
Barcos hundidos:
La API actual te informa cuando has hundido el barco de un oponente:
ShotHit(Point shot, bool sunk);
pero no que te envían hundido! Considero que es parte de las reglas del acorazado humano que debes declarar "¡Hundiste mi acorazado!" (o destructor, o sub, etc.).
Esto es especialmente crítico cuando una IA está tratando de eliminar las naves que se unen entre sí. Me gustaría solicitar un cambio de API a:
ShotHit(Point shot, Ship ship);
Si ship no es nulo, implica que el disparo fue un hundimiento, y usted sabe qué barco hundió y cuánto tiempo fue. Si el disparo no se hundió, el barco es nulo y no tiene más información.
CrossFire actualizado. Sé que no puede competir con Farnsworth o Dreadnought, pero es mucho más rápido que este último y fácil de jugar en caso de que alguien quiera probar. Esto se basa en el estado actual de mis bibliotecas, incluidas aquí para facilitar su uso.
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));
}
}
}
Esto es lo mejor que pude reunir en mi tiempo libre, que es casi inexistente. Hay algunas estadísticas de recuento de juegos y partidos en curso, ya que configuré la función principal para hacer un bucle y ejecutar continuamente BattleshipCompetition hasta que presioné una tecla.
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();
}
}
}
Esta lógica es lo más cerca que tuve de vencer a Dreadnought, ganando aproximadamente el 41% de los juegos individuales. (En realidad ganó un partido por un conteo de 52 a 49). Por extraño que parezca, esta clase no funciona tan bien contra FarnsworthOpponent como una versión anterior que era mucho menos avanzada.
Dell está reparando mi computadora en este momento, pero aquí es donde estaba la semana pasada:
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 es un bruto que fuerza su análisis, entonces puede encontrar que la mecánica del RandomOpponent suministrado es altamente ineficiente. Se permite volver a seleccionar ubicaciones ya seleccionadas y permite que el marco lo obligue a repetir hasta que toque una que aún no ha tocado o el límite de tiempo por movimiento caduque.
Este oponente tiene un comportamiento similar (la distribución de colocación efectiva es la misma), solo realiza la comprobación de la cordura y solo consume una generación de números aleatorios por llamada (amortizada).
Esto usa las clases en mis extensiones / respuesta de biblioteca y solo proporciono los métodos / estado clave.
Shuffle se levanta de la respuesta de Jon Skeet aquí
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
}
No voy a poder participar, pero aquí está el algoritmo que implementaría si tuviera tiempo:
Primero, cuando detecto un golpe, no persigo al resto de la nave de inmediato: construyo una tabla de ubicaciones de naves y descubro si he golpeado los cinco al menos una vez antes de comenzar a hundirlos por completo. (Tenga en cuenta que esta es una mala política para la variante de disparos múltiples: vea los comentarios)
- Pulse el centro (vea la nota final a continuación: 'centro' es solo una conveniencia para la descripción)
- Golpea el punto 4 a la derecha del centro
- Golpea el punto 1 hacia abajo y uno a la derecha del centro
- Golpea el punto cuatro a la derecha del golpe anterior
-
Continúe en ese patrón (debería terminar con líneas diagonales separadas por 3 espacios que llenen el tablero) Esto debería golpear a todos los botes de 4 y 5 esloras, y un número estadísticamente grande de 3 y 2 botes.
-
Comience a golpear aleatoriamente puntos entre las diagonales, esto capturará los barcos de 2 y 3 esloras que aún no se han notado.
Una vez que he detectado 5 golpes, determinaría si los 5 golpes están en botes separados. Esto es relativamente fácil haciendo algunos disparos más cerca de ubicaciones donde dos golpes están en la misma línea horizontal o vertical y están dentro de 5 ubicaciones entre sí (podrían ser dos golpes en el mismo barco). Si son botes separados, continúe hundiendo todos los barcos. Si se encuentra que son el mismo barco, continúe con los patrones de llenado anteriores hasta que se encuentren los 5 barcos.
Este algoritmo es un algoritmo de relleno simple. Las características clave son que no pierde el tiempo hundiendo barcos que conoce cuando todavía hay barcos que desconoce, y no utiliza un patrón de llenado ineficiente (es decir, un patrón completamente aleatorio sería un desperdicio).
Notas finales:
A) " Centro " es un punto de partida aleatorio en el tablero. Esto elimina la debilidad principal de este algoritmo. B) Si bien la descripción indica el dibujo de diagonales inmediatamente desde el comienzo, idealmente el algoritmo simplemente dispara en ubicaciones 'aleatorias' que se encuentran a lo largo de esas diagonales. Esto ayuda a evitar que el competidor mida cuánto tiempo hasta que sus barcos sean golpeados por patrones predecibles.
Esto describe un algoritmo 'perfecto' en el que obtendrá todas las naves en menos de (9x9) / 2 + 10 disparos.
Sin embargo, se puede mejorar significativamente:
Una vez que se golpea un barco, identifica su tamaño antes de hacer las líneas diagonales 'internas'. Es posible que haya encontrado la nave 2, en cuyo caso las diagonales internas se pueden simplificar para encontrar las naves de 3 tamaños más rápidamente.
Identificar etapas en el juego y actuar en consecuencia. Este algoritmo puede ser bueno hasta cierto punto en el juego, pero otros algoritmos pueden producir mejores beneficios como parte del juego final. Además, si el otro jugador está muy cerca de derrotarlo, otro algoritmo podría funcionar mejor; por ejemplo, un algoritmo de alto riesgo podría fallar con más frecuencia, pero cuando funciona funciona rápidamente y puede vencer a su oponente que está más cerca de ganar que usted .
Identifique el estilo de juego del competidor; puede darle pistas sobre cómo planean la colocación de la nave (es decir, es muy probable que su propio algoritmo identifique más rápidamente cómo colocan sus propias naves, si la única herramienta que tiene es un martillo, todo parece un clavo)
-Adam
Mi entrada.
Nada terriblemente especial, y no tuve tiempo de agregar todas las buenas ideas que tenía.
Pero parece jugar bastante bien. Veremos cómo funciona en competencia:
(ponga esto en el archivo Missouri.cs y agregue al proyecto.)
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;
}
}
Esto no es minimax. En realidad, después de colocar las naves, ¿no puede cada jugador jugar solo, lo que resulta en una serie de turnos que le llevó a hundir cada nave oponente? El que tomó menos turnos gana.
No creo que haya buenas estrategias generales más allá de hundir barcos de impacto y tratar de minimizar el número de disparos para cubrir los posibles lugares restantes donde los barcos podrían esconderse.
Por supuesto, puede haber contra-estrategias para cualquier cosa que no sea aleatoria. Pero no creo que haya estrategias que sean buenas contra todos los jugadores posibles.
En realidad, creo que el mayor problema con el rompecabezas es que son esencialmente dos movimientos. Un movimiento es colocar tus naves, el otro es encontrar las naves enemigas (por más segmentada que pueda estar la segunda parte, aparte de tratar de vencer a un reloj con un factor aleatorio, es solo "ejecutar tu algoritmo"). No hay ningún mecanismo para tratar de determinar y luego contrarrestar una estrategia enemiga, que es lo que hace que las competiciones similares se basen en rondas sucesivas de "piedra, papel o tijera". bastante interesante.
Además, creo que sería mejor si especificaras el juego como un protocolo de red y luego proporcionaras el marco para implementar ese protocolo en C #, en lugar de dictar que todas las soluciones deberían ser C #, pero esa es solo mi opinión.
EDITAR: rescindir mi punto inicial, ya que no leí las reglas de la competencia con suficiente cuidado.
Siempre me gustó comenzar en el medio y alejarse en espiral de ese punto, dejando no más de 1 espacio en blanco entre cualquier otro punto para dar cuenta de ese maldito submarino ... el espacio entre disparos dependía de qué barcos se hundieran. si el barco B fue el último, los disparos solo tuvieron que dejar 4 espacios en el medio para minimizar los disparos desperdiciados
Hubo una competencia similar organizada por el Dr. James Heather de la Universidad de Surrey en nombre de la British Computer Society.
Se colocaron limitaciones en los recursos, es decir, el tiempo máximo de procesador por turno, no se pudo almacenar ningún estado entre movimientos, se impuso el tamaño máximo de almacenamiento dinámico. Para limitar el tiempo, la IA podría enviar un movimiento en cualquier punto dentro del intervalo de tiempo y se le solicitaría un movimiento al finalizar el turno.
Muy interesante: vea más en: http://www.bcsstudentcontest.com/
Podría darle algunas ideas más.
Tal como está, la solución se abre y se ejecuta sin modificación en monodevelop en ubuntu 9.10 linux
Escribiste:
- Cualquier cosa que se considere contra el espíritu de la competencia será motivo de descalificación.
- Interferir con un oponente va en contra del espíritu de la competencia.
defina " contra el espíritu de la competencia " e "interfiriendo con un oponente"
Además, para simplificar, le recomiendo que:
- no se permite usar la CPU durante la ranura de CPU del oponente.
- no permite el paralelismo de subprocesos y en su lugar da más segundos de CPU en un solo subproceso. Esto simplificará la programación de la IA y no dañará a nadie que esté vinculado a la CPU / memoria de todos modos.
PD: una pregunta para los post-docs de CS que acechan aquí: ¿no se puede resolver este juego (es decir, ¿hay una única y mejor estrategia?). sí, el tamaño del tablero y la cantidad de pasos hacen que minimax et al sean obligatorios, pero aún así me tengo que preguntar ... está lejos de ser Go y ajedrez en complejidad.
Predigo que la persona que logre aplicar ingeniería inversa al patrón inicial y inicial de sus oponentes ganará.
No estoy seguro de qué tan probable es eso.
También, presumiblemente, sería posible ejecutar una serie de estos con variaciones en el juego.
Agregar cosas como un avión en 3D o poder mover una sola nave en lugar de disparar por un turno probablemente cambiaría un poco el juego.
El tiempo de juego total de un segundo es específico de la máquina. Una vez que el segundo valor de las operaciones de la CPU sea diferente en mi máquina en comparación con la máquina del torneo. Si optimizo el algoritmo Battle Ship para utilizar la mayor cantidad de tiempo de CPU en 1 segundo, entonces se ejecuta en una posible máquina de torneo más lenta, siempre perderá.
No estoy seguro de cómo sortear esta limitación del marco, pero debería abordarse.
...
Una idea es hacer lo que se hizo en esta competencia http://www.bcsstudentcontest.com /
Y tenga un tiempo máximo por turno en lugar del tiempo total máximo de juego. De esta manera, podría limitar los algoritmos para que quepan dentro de un tiempo de giro conocido. Un juego puede durar más de 50 a 600 turnos, si el algoritmo my maneja su tiempo total de juego, podría no dar el tiempo suficiente para hacer su mejor trabajo o podría dar demasiado tiempo y perder. Es muy difícil administrar el tiempo total del juego dentro del algoritmo de Battleship.
Sugeriría cambiar las reglas para limitar el tiempo de turno, no el tiempo total del juego.
Editar
Si escribí un algoritmo que enumera todos los disparos posibles y luego los clasifica, toma el tiro de mayor clasificación. Llevaría demasiado tiempo generar todas las tomas posibles, por lo que dejaría que el algoritmo se ejecute durante un cierto tiempo y luego lo detenga.
Si hubiera un límite basado en turnos, podría dejar que el algoritmo se ejecute durante 0.9 segundos y devolver el tiro de mayor rango, y estar bien dentro del límite de tiempo de giro.
Si estoy limitado al tiempo total de juego de un segundo, será difícil determinar cuánto tiempo debe ejecutarse el algoritmo para cada turno. Querré maximizar el tiempo de mi CPU. Si un juego duró 500 rondas, podría limitar cada turno a 0.002 segundos, pero si un juego duró 100 rondas, podría dar a cada turno 0.01 segundos de tiempo de CPU.
No sería práctico para un algoritmo utilizar una búsqueda semi exhaustiva del espacio de disparo para encontrar el mejor disparo con la limitación actual.
El tiempo total de juego de 1 segundo está limitando el tipo de algoritmos que se pueden usar efectivamente para competir en el juego.
Estoy haciendo frente aquí al no poner el código real, pero me arriesgaré a algunas observaciones generales:
- Dado que todas las naves tienen un tamaño de al menos 2 celdas, puedes usar una optimización que vi en una implementación del juego en Space Quest V, que solo dispara a celdas alternativas en un patrón de diamante mientras está "buscando". Un objetivo. Esto elimina la mitad de los cuadrados, al tiempo que garantiza que finalmente encontrará todas las naves.
- Un patrón de disparo aleatorio cuando se buscan objetivos estadísticamente producirá los mejores resultados en muchos juegos.
! [Densidad de probabilidad] [1] ingrese la descripción de la imagen ella
! [ingrese la descripción de la imagen aquí] [2]
Experimenté comparando los resultados de disparos de randon contra una cacería / objetivo tonto y finalmente una búsqueda sofisticada.
La mejor solución parece ser crear una función de densidad de probabilidad para la probabilidad de que las naves restantes usen un cuadrado individual y apuntar con el cuadrado con el valor más alto.
Puede ver mis resultados aquí ingrese la descripción del enlace aquí
" Acorazado " es lo que se conoce como un problema clásico de NP de informática completa.
http://en.wikipedia.org/wiki/List_of_NP-complete_problems
(busque Battleship: está allí, debajo de juegos y rompecabezas)
