Was ist die beste Battleship AI?
https://stackoverflow.com/questions/1631414
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Battleship!
Bereits im Jahr 2003 (als ich 17 war), konkurrierte ich in einer Battleship AI Codierung Wettbewerb. Auch wenn ich das Turnier verloren, ich hatte viel Spaß und habe viel gelernt von ihm.
Nun, ich mag diesen Wettbewerb wieder zu beleben, in der Suche nach der besten Schlacht AI.
Hier ist der Rahmen, jetzt auf Bitbucket gehostet werden.
Der Gewinner wird +450 Ruf vergeben werden! Der Wettbewerb ab dem 17. November stattfindet, 2009 . Keine Einträge oder Änderungen später als Zero-Hour am 17. werden akzeptiert. (Central Standard Time) Geben Sie Ihre Einträge früh, so dass Sie nicht Ihre Chance verpassen!
halten dieses Ziel , bitte den Geist des Wettbewerbs folgen.
Die Regeln des Spiels:
- Das Spiel wird auf einem 10x10 Raster gespielt werden.
- Jeder Teilnehmer wird jeweils 5 Schiffe (von Längen 2, 3, 3, 4, 5) auf ihrer grid platzieren.
- Keine Schiffe überlappen können, aber sie können benachbart sein.
- Die Teilnehmer dann abwechselnd einzelne Schüsse auf den Gegner feuern.
- Eine Variation auf das Spiel ermöglicht es, mehrere Schüsse pro Salve abfeuern, einen für jeden überlebenden Schiff.
- Der Gegner die Teilnehmer benachrichtigen, wenn der Schuss sinkt, trifft oder verfehlt.
- Der Spielablauf ist beendet, wenn alle Schiffe von einem Spieler versenkt werden.
Die Regeln des Wettbewerbs:
- Der Geist des Wettbewerbs ist es, das beste Battleship Algorithmus zu finden.
- Alles, was gegen den Geist des Wettbewerbs erachtet wird zur Disqualifikation führen.
- mit einem Gegner Störende ist gegen den Geist des Wettbewerbs.
- Multithreading kann unter folgenden Einschränkungen verwendet werden:
- Nicht mehr als ein Thread ausgeführt werden kann, während es nicht an der Reihe ist. (Obwohl eine beliebige Anzahl von Threads in einem "Suspended" Zustand sein kann).
- Kein Gewinde kann an einer Priorität anders als „Normal“. laufen
- die beiden oben genannten Einschränkungen gegeben, werden Sie mindestens 3 dedizierte CPU-Kerne während seines Zuges gewährleistet.
- Eine Grenze von 1 Sekunde der CPU-Zeit pro Spiel wird auf jeden Teilnehmer auf dem primären Thread zugeteilt.
- Zeitergebnisse Running out das aktuelle Spiel zu verlieren.
- Jede Folge wird das aktuelle Spiel zu verlieren. nicht behandelte Ausnahme
- Netzzugang und Festplattenzugriff ist erlaubt, aber Sie können die Zeitbeschränkungen ziemlich unerschwinglich finden. Es wurden jedoch einige Set-up und tear-down Methoden hinzugefügt, um die Zeit Belastung zu lindern.
- -Code sollte auf Stack-Überlauf als Antwort gepostet werden, oder, wenn sie zu groß, verknüpft.
- Max Gesamtgröße (unkomprimiert) ein Eintrag ist 1 MB.
- Offiziell .Net 2.0 / 3.5 ist die einzige Rahmen Anforderung.
- Ihr Eintrag muss die IBattleshipOpponent-Schnittstelle implementieren.
Scoring:
- Best 51 Spiele von 101 Spielen ist der Gewinner eines Spiels.
- wird Alle Teilnehmer gegeneinander, Round-Robin-Stil angepasst spielen.
- Die beste Hälfte der Teilnehmer wird dann ein Double-Elimination-Turnier spielen, um die Gewinner zu ermitteln. (Kleinste Zweierpotenz, die größer oder gleich der Hälfte ist, eigentlich.)
- Ich werde mit dem TournamentApi Rahmen für das Turnier.
- Die Ergebnisse werden hier veröffentlicht.
- Wenn Sie mehr als einen Eintrag einreichen, nur Ihre besten Wertung Eintrag ist berechtigt, für die Doppel elim.
Viel Glück! Viel Spaß!
EDIT 1:
Dank Freed , der einen Fehler in der Ship.IsValid Funktion gefunden hat. Es war fixed. Bitte laden Sie die aktualisierte Version des Frameworks.
EDIT 2:
Da es in persistierenden Statistiken auf der Festplatte und so großes Interesse gewesen ist, hat ich ein paar nicht-timed Rüst- und tear-down Ereignisse hinzugefügt, die die erforderliche Funktionalität bieten sollten. Dies ist eine halb brechen Änderung . Das heißt: Die Schnittstelle modifiziert wurde, Funktionen hinzuzufügen, aber kein Körper ist für sie erforderlich. Bitte laden Sie die aktualisierte Version des Frameworks.
EDIT 3:
Bug Fix 1: GameWon und GameLost wurden nur im Fall einer Auszeit immer genannt
.
Bug Fix 2: Wenn ein Motor wurde jedes Spiel Timing aus, der Wettbewerb würde nie enden
.
Bitte laden Sie die aktualisierte Version des Frameworks.
EDIT 4:
Turnier Ergebnisse:
Lösung
Ich zweite die Bewegung viel mehr Spiele pro Spiel zu tun. 50 Spiele zu tun ist Spiegeln nur eine Münze. Ich brauchte 1000 Spiele zu tun, um jede vernünftige Unterscheidung zwischen Testalgorithmen zu erhalten.
Herunterladen Dreadnought 1.2 .
Strategien:
-
zu verfolgen alle möglichen Positionen für Schiffe, die> 0 Treffer haben. Die Liste wird nie größer als ~ 30K so kann es genau gehalten werden, im Gegensatz zu der Liste aller möglichen Positionen für alle Schiffe (die sehr groß ist).
-
Der GetShot Algorithmus hat zwei Teile, eine, die zufällige Schüsse und die anderen erzeugt die zu beenden versucht, ein bereits getroffen Schiff sinkt. Wir tun zufällige Aufnahmen, wenn es eine mögliche Position (oben in der Liste) ist, in der alle Treffer Schiffe versenkt werden. Ansonsten versuchen wir durch Kommissionierung ein Ort versinkt ein Schiff zu beenden, zu dem schießen die meisten möglichen Positionen eliminiert (gewichtet).
-
Für zufällige Aufnahmen, beste Lage berechnen basierend auf der Wahrscheinlichkeit eines der unsunk Schiffe überlappen sich die Position zu schießen.
-
adaptiven Algorithmus, die Schiffe an Orten platziert, wo der Gegner statistisch weniger wahrscheinlich ist, zu schießen.
-
adaptiver Algorithmus, die an Orten zu schießen vorzieht, wo der Gegner statistisch wahrscheinlicher ist, seine Schiffe zu stellen.
-
Ort Schiffe meist nicht berühren.
Andere Tipps
Hier ist mein Eintrag! (Die naive Lösung möglich)
"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() { }
}
}
Hier ist ein Gegner für Menschen gegen spielen:
Statt eine feste Geometrie inspirierte Strategie zu verwenden, dachte ich, es wäre interessant, zu versuchen, schätzt die zugrunde liegenden Wahrscheinlichkeiten , dass ein bestimmte unerforschter Raum hält ein Schiff.
Um dieses Recht zu tun, dann würden Sie alle möglichen Konfigurationen von Schiffen erkunden, die Ihre aktuelle Sicht auf der Welt passen, und dann Wahrscheinlichkeiten berechnen auf diesen Konfigurationen basieren. Man könnte denken Sie daran, wie ein Baum zu entdecken:
eine Erweiterung der möglichen Schlacht Staaten http://natekohl.net/media/battleship-tree.png
Nachdem alle Blätter des Baumes betrachtet, die mit Jive, was Sie wissen über die Welt (zB Schiffe nicht überlappen können, werden alle Treffer Quadrate Schiffe sein müssen, etc.) können Sie, wie oft Schiffe zählen tritt bei jeder unerforscht Position, um die Wahrscheinlichkeit zu schätzen, die ein Schiff dort sitzt.
Dies kann als eine Heatmap sichtbar gemacht werden, wo Hot Spots sind eher Schiffe enthalten:
Eine Sache, die ich über diesen Battleship Wettbewerb mag, ist, dass der Baum über fast klein genug ist, um diese Art von Algorithmus, um Brute-Force. Wenn ~ 150 mögliche Positionen für jede der fünf Schiffe sind, ist, dass 150 5 = 75 Milliarden Möglichkeiten. Und diese Zahl nur kleiner wird, vor allem, wenn Sie ganze Schiffe beseitigen.
Der Gegner, den ich oben verlinkten nicht den ganzen Baum erkunden; 75 Milliarden ist immer noch zu groß unter einer Sekunde zu bekommen. Es muss versuchen, diese Wahrscheinlichkeiten zu schätzen, aber mit der Hilfe von ein paar Heuristiken.
Nicht eine vollwertiger Antwort, aber es scheint wenig Sinn, die wirklichen Antworten mit Code unübersichtlich, die üblich ist. Ich stelle also einige Erweiterungen / allgemeine Klassen im Geiste der Open Source. Wenn Sie diese dann verwenden Sie bitte den Namensraum ändern oder zu versuchen, alles zu kompilieren in eine DLL wird nicht funktionieren.
BoardView können Sie ganz einfach mit einer kommentierten Board arbeiten.
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
}
}
Einige Erweiterungen, dies einige Funktionen im Hauptrahmen dupliziert aber eigentlich sollte von Ihnen durchgeführt werden.
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));
}
}
}
Etwas, das ich viel am Ende mit.
enum OpponentsBoardState
{
Unknown = 0,
Miss,
MustBeEmpty,
Hit,
}
Die Randomisierung. Sicher aber prüfbar, nützlich für die Prüfung.
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!");
}
}
}
ich die Zeit nicht richtig haben jetzt einen vollwertigen Algorithmus zu schreiben, aber hier ist ein Gedanke: Wenn dein Gegner zufällig Schiffe gesetzt, wäre eine einfache Verteilung nicht die Platzierung Wahrscheinlichkeiten sein, zentriert bei (5.5,5.5)? Zum Beispiel sind die Platzierungsmöglichkeiten für die Schlacht (5 Einheiten lang) in der x-Dimension hier:
x 1 2 3 4 5 6 7 8 9 10
P(x) 2 4 6 8 10 10 8 6 4 2
Die gleichen Berechnungen würden für y gültig. Die anderen Schiffe würden nicht so steil von Verteilungen haben, aber Ihre beste Vermutung ist immer noch das Zentrum. Danach würde der mathematische Ansatz langsam seine Diagonalen strahl (vielleicht mit der Länge des durchschnittlichen Schiffs, 17/5) aus dem Zentrum. Ex:
...........
....x.x....
.....x.....
....x.x....
...........
Offensichtlich einig Zufälligkeit müßte die Idee hinzugefügt werden, aber ich denke, dass rein mathematisch, das ist der Weg zu gehen.
Nichts, das anspruchsvoll, aber here, was ich kam mit. Es schlägt die zufälligen Gegner 99,9% der Zeit. Würde mich interessieren, ob jemand irgendwelche anderen kleinen Herausforderungen wie diese hat, es hat viel Spaß gemacht.
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() { }
}
}
Ein wenig kondensiert auf kleinsten Raum nehmen hier und immer noch lesbar sein.
Einige Bemerkungen über den Wettbewerb Motor:
newgame Parameter:
Wenn IBattleshipOpponent :: newgame für Pre-Game-Setup bestimmt und nimmt einen Board, sollte es nimmt auch eine Liste der Schiffe und ihre jeweiligen Größen. Es macht keinen Sinn für variable Board-Größe zu ermöglichen, ohne für variable Schiffskonfigurationen ermöglicht.
Schiffe sind versiegelt:
Ich sehe keinen Grund, warum Klasse Schiff abgedichtet ist. Unter anderem grundlegende Dinge würde ich Schiffe wie einen Namen haben, so kann ich Ausgabenachrichten wie ( „Sie versenkt mein {0}“, ship.Name); . Ich habe noch andere Erweiterungen im Auge zu, so dass ich denke, Schiff vererbbar sein sollte.
Zeitlimits:
Während die Frist von 1 Sekunde Sinn für ein Turnier der Regel macht es vermasselt völlig mit Debugging. BattleshipCompetition sollte eine einfache Einstellung hat zeitVerletzungen zu ignorieren mit Entwicklung / Debugging zu unterstützen. Ich würde auch vorschlagen System.Diagnostics.Process :: UserProcessorTime / Privilegierte ProcessorTime / TotalProcessorTime für eine genauere Vorstellung davon, wie viel Zeit verwendet wird.
UntersuchungSunk Schiffe:
Die aktuelle API informiert Sie, wenn Sie ein oppenent Schiff versenkt haben:
ShotHit(Point shot, bool sunk);
aber nicht die Schiff Sie versenkt! Ich halte es für einen Teil der Menschen Battleship Regeln, die Sie verpflichtet sind, zu erklären, „Du versenkt mein Battleship!“ (Oder Zerstörer oder Unter, etc).
Dies ist besonders kritisch, wenn eine KI versucht, Schiffe zu spülen, dass stumpf gegeneinander an. Ich möchte eine API Änderung Anfrage an:
ShotHit(Point shot, Ship ship);
Wenn Schiff ist nicht null, es bedeutet, dass der Schuss ein Sinken-Schuss war, und Sie wissen, welches Schiff Sie versenkt, und wie lange war es. Wenn der Schuss ein nicht-Versenkung Schuss war, dann Schiff null ist, und Sie haben keine weiteren Angaben vor.
Crossfire aktualisiert. Ich weiß es nicht mit Farnsworth oder Dreadnought konkurrieren kann, aber es ist viel schneller als die letzteren und einfach zu spielen, falls jemand versuchen will. Dies beruht auf dem aktuellen Stand meiner Bibliotheken, hier eingeschlossen, um es zu machen, einfach zu bedienen.
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));
}
}
}
Hier geht es um das Beste, was ich in meiner Freizeit zusammen könnte, die über nicht existent ist. Es gibt einige Spiele und Spiel Auszählung Statistiken gehen, wie ich die Hauptfunktion Schleife aufgebaut und kontinuierlich die BattleshipCompetition laufen, bis ich eine Taste gedrückt wird.
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();
}
}
}
Diese Logik ist in der Nähe, die ich zu schlagen Dreadnought hatte, etwa 41% der einzelnen Spiele zu gewinnen. (Es hat tatsächlich ein Spiel durch eine Anzahl von 52 bis 49 gewinnen) Seltsamer diese Klasse nicht tut, als auch gegen FarnsworthOpponent als eine frühere Version, die viel weniger weit fortgeschritten war.
Mein Computer von Dell jetzt repariert wird, aber das ist, wo ich in der vergangenen Woche war:
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; }
}
}
Wenn Sie Brute zwingen Ihre Analyse, dann können Sie die Mechanik des mitgelieferten RandomOpponent höchst ineffizient finden. Es erlaubt sich bereits gezielt Standorte erneut auszuwählen und lässt den Rahmen Kraft, sie zu wiederholen, bis es einen trifft es noch nicht berührt hat oder die Frist pro Zug abgelaufen ist.
Dieser Gegner hat ein ähnliches Verhalten (die effektive Platzierung Verteilung ist das gleiche) es tut nur die geistige Gesundheit selbst überprüft und verbraucht nur eine Zufallszahl-Erzeugungs pro Anruf (abgeschrieben)).
Diese verwenden die Klassen in meinen Erweiterungen / Bibliothek Antwort und ich nur den Schlüssel Methoden / Zustand liefern.
Shuffle von Jon Skeet Antwort hier angehoben
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
}
Ich werde in der Lage sein nicht teilnehmen, aber hier ist der Algorithmus Ich würde implementieren, wenn ich Zeit habe:
Zuerst, wenn ich einen Schlag erfassen ich den Rest des Schiffes nicht sofort verfolgen - ich bauen eine Tabelle von Schiffspositionen und herauszufinden, ob ich alle fünf mindestens einmal getroffen haben, bevor sie vollständig zu versenken. (Beachten Sie, dass dies eine schlechte Politik für die Mehrfach Schuss Variante - siehe Kommentare)
- Drücken Sie die Mitte (siehe unten abschließende Bemerkung - ‚Zentrum‘ ist nur eine Bequemlichkeit für Beschreibung)
- Hit the spot 4 rechts von der Mitte
- Hit the spot 1 nach unten und einer nach rechts von der Mitte
- Drücken Sie die Stelle vier rechts von der Seite zurück
-
in diesem Muster weiter (sollte mit diagonalen Linien von 3 Leerzeichen getrennt am Ende die Platte Füllung) Dies sollte alle 4 und 5 Länge Boote schlagen, und eine statistisch große Anzahl von 3 und 2 Booten.
-
Starten Sie zufällig Flecke zwischen den Diagonalen treffen, wird dies die 2 und 3 Länge Boote fängt, die nicht bereits bemerkt worden.
Nachdem ich 5 Treffer gefunden zu haben, würde ich feststellen, ob die 5 Treffer auf separaten Boote sind. Dies ist relativ einfach durch ein paar Schüsse in der Nähe von Orten zu machen, wo zwei Treffer auf der gleichen horizontalen oder vertikalen Linie sind und innerhalb von 5 Standorten voneinander (vielleicht zwei Treffer auf dem gleichen Boot sein). Wenn sie getrennte Boote sind dann weiterhin alle Schiffe versenken. Wenn sie das gleiche Boot befunden werden, weiterhin die Füllmuster oben, bis alle 5 Boote befinden.
Dieser Algorithmus ist eine einfache Füllung Algorithmus. Die wichtigsten Merkmale sind, dass es nicht an der Zeit sinkende Schiffe verschwendet er weiß, wann es gibt immer noch Schiffe es ist nicht bekannt, und es nicht zu einer ineffizienten Füllmuster verwenden (dh ein vollständig zufälliges Muster wäre verschwenderisch sein).
Abschlussnoten:
A) "Center" ist ein zufälliger Ausgangspunkt auf dem Brett. Dadurch entfällt die primäre Schwäche dieses Algorithmus. B) Während die Beschreibung zeigt Diagonalen sofort von Anfang an, idealerweise der Algorithmus lediglich schiesst auf ‚zufällig‘ Stellen Zeichnung, die entlang dieser Diagonalen sind. Dies hilft, den Wettbewerber zu verhindern, Timing, wie lange, bis ihre Schiffe von vorhersagbaren Mustern getroffen werden.
Dies beschreibt einen 'perfekten' Algorithmus, dass sie all Schiffe in unter bekommen (9x9) / 2 + 10 Schüsse.
Es kann jedoch deutlich verbessert werden:
Sobald ein Schiff getroffen wird, identifizieren seine Größe, bevor die ‚interne‘ diagonalen Linien zu tun. Ebenso können Sie das 2 Schiff gefunden haben, wobei in diesem Fall die internen Diagonalen vereinfacht werden, um die Größe 3 Schiffe schneller zu finden.
Identifizieren Phasen im Spiel und entsprechend handeln. Dieser Algorithmus kann bis zu einem bestimmten Punkt im Spiel gut sein, aber auch andere Algorithmen können bessere Leistungen als Teil des Endspiels ergeben. Auch, wenn der andere Spieler zu besiegen Sie ganz in der Nähe ist, kann ein anderer Algorithmus besser funktionieren - zum Beispiel ein hohes Risiko Algorithmus könnte häufiger scheitern, aber wenn es funktioniert es funktioniert schnell und Sie können Ihre Gegner schlagen, die näher zu gewinnen ist, als Sie .
den Spielstil des Teilnehmers identifizieren - es kann Ihnen Hinweise geben, wie sie planen, Schiff Platzierung (dh die Chancen gut, dass ihre eigenen Algorithmus am schnellsten identifiziert, wie sie ihre eigenen Schiffe platzieren - wenn das einzige Werkzeug, das Sie haben, ist ein Hammer sieht alles aus wie ein Nagel)
-Adam
Mein Eintrag.
Nichts schrecklich Besonderes, und ich habe bekommen Zeit nicht alle guten Ideen hinzufügen ich hatte.
Aber es scheint ziemlich gut zu spielen. Wir werden sehen, wie es funktioniert im Wettbewerb:
(fügen Sie dies in der Datei Missouri.cs und zu Projekt.)
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;
}
}
Das ist nicht Minimax. Eigentlich nachdem die Schiffe platzieren, kann nicht jeder Spieler auf seinem eigenen spielen, in einer Reihe von resultierenden verwandelt es ihn nahm jeden Gegner Schiff zu versenken? Die eine, die weniger wechselten sich gewinnt.
Ich glaube nicht, dass es irgendwelche gute allgemeine Strategien jenseits Hit Schiffe versinken und zu versuchen, die Anzahl der Aufnahmen zu minimieren, um die verbleibenden möglichen Stellen abzudecken, in denen Schiffe verstecken könnten.
Natürlich könnte es Gegenstrategien für alles sein, was nicht zufällig ist. Aber ich glaube nicht, dass es Strategien, die gegen alle möglichen Spieler gut sind.
Eigentlich, denke ich das größte Problem mit dem Puzzle ist, dass seine im Wesentlichen zwei Züge. Ein Umzug ist Ihre Schiffe platzieren, das andere ist das Finden der feindlichen Schiffe (jedoch segmentiert, dass der zweite Teil sein könnte, abgesehen von dem Versuch, eine Uhr mit einem Zufallsfaktor zu schlagen, es ist nur ‚Betreiben Sie Ihr Algorithmus‘). Es gibt keinen Mechanismus, um zu versuchen, einen Feind-Strategie zu bestimmen und dann zu begegnen, das ist, was ähnliche Wettbewerbe ist, macht auf Basis aufeinanderfolgende Runden von „Rock Paper Scissors“ ziemlich interessant.
Außerdem glaube ich, es kühler sein würde, wenn man das Spiel als Netzwerkprotokoll angegeben und zur Verfügung gestellt dann den Rahmen dieses Protokoll in C # zu implementieren, anstatt zu diktieren, dass alle Lösungen C # sein sollten, aber das ist nur meine Meinung.
EDIT: ich meinen Anfangspunkt zurücktreten, da ich nicht die Wettbewerbsregeln sorgfältig genug gelesen.
ich in der Mitte immer beginnend gemocht und spiralförmig weg von diesem Punkt eines nicht mehr als 1 Leerzeichen zwischen beliebigen anderen Punkten zu verlassen für das goddam Unter berücksichtigen ... der Raum zwischen den Aufnahmen war abhängig von den Schiffe versenkt wurden. wenn das B-Schiff letzte war, hatten die Schüsse nur 4 Leerzeichen dazwischen lassen verschwendete Aufnahmen zu minimieren,
Es war ein ähnlicher Wettbewerb laufen von Dr. James Heather von der University of Surrey im Namen der British Computer Society.
Einschränkungen wurden auf Ressourcen gesetzt - nämlich maximale Prozessorzeit pro Runde, kann kein Zustand zwischen bewegt, maximale Heap-Größe auferlegt gespeichert werden. Zur Begrenzung der Zeit die KI eine Bewegung an einer beliebigen Stelle innerhalb des Zeitschlitzes einreichen könnte und würde für einen Umzug nach Beendigung der Wende aufgefordert werden.
Sehr interessant - sehen Sie mehr an: http://www.bcsstudentcontest.com/
Könnten Sie ein paar mehr Ideen.
Wie es ist, die Lösung eröffnet und läuft ohne Änderung in monodevelop in Ubuntu 9.10 Linux
Sie schrieb:
- Alles, was gegen den Geist des Wettbewerbs erachtet wird zur Disqualifikation führen.
- mit einem Gegner Störende ist gegen den Geist des Wettbewerbs.
Sie definieren „gegen den Geist des Wettbewerbs“ und „stören einen Gegner“?
Auch - zu vereinfachen, empfehle ich Ihnen:
- nicht zulassen CPU mit überhaupt während des Gegners CPU-Steckplatz.
- Thread Parallelität nicht zuzulassen und stattdessen mehr CPU-Sekunden auf einem einzigen Thread geben. Dies wird die Programmierung der KI vereinfachen und wird nicht weh tun alle, die CPU / Speicher-gebunden sowieso.
PS - eine Frage für die CS Postdocs hier lauert: ist nicht dieses Spiel auflösbar (d gibt es eine einzige, beste Strategie?). ja, die Plattengröße und Anzahl der Schritte macht Minimax et al obligatorisch, aber noch muss ich frage mich ... es ist weit von Go und Schach in der Komplexität.
Ich sage voraus, dass die Person, die ihre Gegner zufällige Samen zu umkehren schafft Ingenieur und Muster gewinnen nennen.
Nicht sicher, wie wahrscheinlich das ist aber.
Es wäre auch vermutlich möglich sein, eine Reihe von diesem mit Variationen über das Spiel zu starten.
in Dingen wie eine 3D-Ebene Hinzufügen oder wahrscheinlich dem Spiel ein gutes Stück ändern würde in der Lage, ein einziges Schiff statt Shooting für eine Wende zu bewegen.
Die 1 Sekunde total Spielzeit ist maschinenspezifisch. Sobald zweite Wert von CPU-Operationen wird auf meinem Rechner unterschiedlich sein im Vergleich zu dem Turnier Maschine. Wenn ich den Battle Ship Algorithmus verwenden, um die meisten CPU-Zeit innerhalb von 1 Sekunde zu optimieren, dann ist es auf einer möglichst langsamen Turnier Maschine ausführen, wird es immer verlieren.
Ich bin nicht sicher, wie diese Einschränkung des Rahmens zu bekommen, aber es sollte angegangen werden.
...
Eine Idee ist, zu tun, was in diesem Wettbewerb durchgeführt wurde http://www.bcsstudentcontest.com /
Und eine maximale Zeit pro Umdrehung hat als auf maximale Gesamtspielzeit gegenüber. So kann ich die Algorithmen begrenzen könnte innerhalb eines Know wiederum Zeit passen. Ein Spiel könnte 50 bis 600+ Umdrehungen dauern, wenn der mein Algorithmus seine Gesamtspielzeit schafft, ist es vielleicht nicht die genug Zeit, um seine beste Arbeit zu tun oder es könnte zu viel Zeit geben und verlieren. Es ist sehr schwer, die Gesamtspielzeit im Battleship Algorithmus zu verwalten.
Ich würde vorschlagen, die Regeln zu ändern, die Wendezeit nicht die gesamte Spielzeit zu begrenzen.
Bearbeiten
Wenn ich einen Algorithmus geschrieben, die alle möglichen Aufnahmen aufzählt und dann ordnet sie, nimmt dann die ranghöchste Schuss. Es würde zu lange dauern, um alle möglichen Aufnahmen zu erzeugen, so würde ich der Algorithmus Lauf für eine gewisse Zeit, dann stoppen sie lassen.
Wenn es ein rundenbasiertes Grenze ist, kann ich den Algorithmus Lauf für 0,9 Sekunden lassen und die ranghöchste Schuss zurückzukehren, und auch die Wende Frist withing werden.
Wenn ich begrenzt bin Gesamtspielzeit von einer Sekunde, wird es schwierig sein, zu bestimmen, wie lange der Algorithmus für jede Umdrehung ausgeführt werden soll. Ich werde möchte meine maximale CPU-Zeit. Wenn ein Spiel 500 Runde dauerte konnte ich jede Runde auf 0,002 Sekunden begrenzen, aber wenn ein Spiel 100 Runden dauerte konnte ich jedes Mal dreht 0,01 Sekunden der CPU geben.
Es wäre unpraktisch für einen Algorithmus, um eine halb-erschöpfende Suche des Schusses Raum zu verwenden, um den besten Schuss mit der Strombegrenzung zu finden.
Die 1 Sekunde Gesamtspielzeit die Art der Algorithmen ist die Begrenzung, die effektiv im Spiel konkurrieren verwendet werden kann.
Ich bin ausklinken hier aus durch nicht unbedingt der Code bei der Umsetzung - aber ich werde einige allgemeine Beobachtungen Gefahr:
- Da alle Schiffe mindestens zwei Zellen in der Größe sind, können Sie eine Optimierung verwenden ich auf einer Implementierung des Spiels in Space Quest V sah - die nur Brände an abwechselnden Zellen in einem Diamantmuster, während es „Suche nach“ ein Ziel . Dadurch entfällt die Hälfte der Plätze, während nach wie vor gewährleistet, dass Sie alle Schiffe finden schließlich.
- Ein Zufall Abfeuerungsmuster bei der Suche nach Zielen werden statistisch die besten Ergebnisse über viele Spiele ergeben.
! [Wahrscheinlichkeitsdichte] [1] eingeben image description sie
! [Enter image description here] [2]
Ich experimentierte mit den Ergebnissen der randon Schießen gegen ein dummes Jagd / Ziel und schließlich ein ausgeklügeltes Such verglichen wird.
Die beste Lösung scheint zu sein, eine Wahrscheinlichkeitsdichtefunktion für die zu schaffen, wie wahrscheinlich jeden einzelnen Platz, der von den übrigen Schiffen verwendet wird, und mit dem höchsten Wert mit dem Quadrat Ziel hat.
Sie können meine Ergebnisse hier sehen Link-Beschreibung geben hier
"Battleship" ist das, was als klassische Informatik bekannt ist NP-vollständiges Problem.
http://en.wikipedia.org/wiki/List_of_NP-complete_problems
(sucht Battleship - es ist da, unter Spiele und Puzzles)
