什么是最好的战列舰AI？

战舰！

早在2003年（当时我17岁），我参加了一个战舰AI编码竞赛。 即使我输了那场比赛，我也有很多乐趣，并从中学到很多东西。

现在，我想重振这场比赛，寻找最好的战舰AI。

这里是框架，现在托pipe在Bitbucket上 。

获胜者将被授予+450的声望！ 比赛将于2009年11月17日开始 。 17日之后不得迟于零时间进行或修改。 （中部标准时间）尽早提交你的参赛作品，所以你不要错过机会！

为了保持这一目标 ，请遵循比赛的精神。

游戏规则：

1. 游戏将在10×10格子上播放。
2. 每个参赛者将把5艘（长度为2,3,4,5）的船舶分别放在电网上。
3. 没有船可能重叠，但它们可能相邻。
4. 然后竞争对手轮stream向对手单枪匹马发射。
   • 游戏的变化允许每发射一发射出多发，每发射一发。
5. 如果投篮下沉，命中或失误，对手将通知参赛者。
6. 当任何一个玩家的所有船只都沉没时，游戏结束。

比赛规则：

1. 比赛的精神是find最好的战列舰algorithm。
2. 任何违反比赛精神的行为都将成为取消资格的理由。
3. 干扰对手是违背比赛精神的。
4. multithreading可以在以下限制下使用：
   • 没有超过一个线程可能正在运行，而不是轮到你。 （虽然，任何数量的线程可能处于“暂停”状态）。
   • 没有线程可以以“正常”以外的优先级运行。
   • 鉴于上述两个限制，在您轮到时您将至less保证3个专用CPU内核。
5. 每个游戏CPU时间的限制1秒被分配给主线程上的每个参赛者。
6. 时间不够会导致目前的游戏失败。
7. 任何未处理的exception都将导致当前游戏的丢失。
8. networking访问和磁盘访问是允许的，但您可能会发现时间限制相当严重。 但是，增加了一些设置和拆卸方法来减轻时间压力。
9. 代码应该作为一个答案张贴在堆栈溢出，或者如果太大，链接。
10. 条目的最大总大小（未压缩）为1 MB。
11. .Net 2.0 / 3.5是唯一的框架要求。
12. 您的条目必须实现IBattleshipOpponent接口。

评分：

1. 101场比赛中最好的51场比赛是胜者。
2. 所有的竞争者都会玩互相配对的循环赛模式。
3. 最好的一半的竞争对手将发挥双淘汰赛，以确定赢家。 （实际上大于或等于一半的两个最小的幂）。
4. 我将使用锦标赛的TournamentApi框架。
5. 结果将张贴在这里。
6. 如果您提交了多个条目，则只有您得分最高的条目符合双重条件。

祝你好运！ 玩的开心！

---

编辑1：
感谢Freed ，他在Ship.IsValid函数中发现错误。 它已被修复。 请下载框架的更新版本。

编辑2：
由于对于将数据持久化到磁盘等问题已经有了很大的兴趣，我添加了一些非定时的设置和拆卸事件，以提供所需的function。 这是一个半点变化 。 也就是说：界面已被修改为添加function，但不需要主体。 请下载框架的更新版本。

编辑3：
错误修复1： GameWon和GameLost只是在超时的情况下被调用。
错误修复2：如果一个引擎超时每场比赛，竞争永远不会结束。
请下载框架的更新版本。

编辑4：
锦标赛结果：

Answer 1

我第二个动作是每场比赛做更多的比赛。 做50场比赛只是一个硬币。 我需要做1000场比赛来区分testingalgorithm。

下载Dreadnought 1.2 。

策略：

• 跟踪所有可能的位置，船只有> 0命中。 该列表永远不会比〜30K大，所以它可以保持完全不同，所有船舶（这是非常大的）所有可能的位置列表。

• GetShotalgorithm有两个部分，一个是随机发射，另一个是试图完成沉没的船只。 如果有一个可能的位置（从上面的列表），我们做任意投篮，其中所有命中的船只都沉没。 否则，我们试图通过select一个位置来完成下沉，从而消除最可能的位置（加权）。

• 对于随机拍摄，根据其中一艘不固定的船舶与该地点重叠的可能性计算最佳拍摄地点。

• 自适应algorithm将船舶放置在对手统计上不太可能射击的位置。

• 自适应algorithm，它更喜欢在对手更有可能放置他的船只的地方进行射击。

• 船舶大多不相互接触。

Answer 2

这是我的入口！ （可能是最天真的解决scheme）

“随机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() { } } } 

Answer 3

这是一个反对人对手：

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

我认为试图估计任何特定未开发空间持有船舶的潜在可能性是有趣的，而不是使用固定的几何激励策略。

要做到这一点，你需要探索符合当前世界观的所有可能的船舶configuration，然后根据这些configuration计算概率。 你可以把它想象为探索一棵树：

可能的战列舰状态的扩展media/battleship-tree.png

在考虑了所有与你所了解的世界有关的树叶（例如船只不能重叠，所有命中的方格必须是船只等等）之后，你可以计算在每个未探索的位置上船只出现的频率，以估计一艘船坐在那里。

这可以被视为热图，热点更可能包含船只：

每个未知位置的概率热图media/battleship-probs.png

我喜欢这个战舰竞赛的一件事是，上面的树几乎足以蛮力这种algorithm。 如果这五艘船舶中每一艘都有大约150个可能的位置，那就是150 ⁵ = 750亿个可能性。 而且这个数字只会变小，特别是如果你能消除整船。

我上面链接的对手并没有探索整棵树， 在一秒之内还有大到一百五十亿。 它试图估计这些概率，但是，在一些启发式的帮助下。

Answer 4

这不是一个完全成熟的答案，但似乎没有什么地方用常见的代码混淆真实的答案。 因此我本着开源的精神提出了一些扩展/一般的类。 如果你使用这些，那么请改变命名空间或试图编译一切到一个DLL是不会工作的。

BoardView可让您轻松使用带注释的板子。

 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(pX, pY, true)].Data; } set { this.history[SafeCalc(pX, pY, 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 } } 

一些扩展，其中一些在主框架中重复function，但应该由你来完成。

 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 pX >= 0 && pY >= 0 && pX < size.Width && pY < 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 (aX == bX - 1 || aX == bX + 1) && (aY == bY - 1 || aY == bY + 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)); } } } 

我最终使用了很多东西。

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

随机化。 安全但可testing，对testing有用。

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Drawing; namespace Battleship.ShuggyCoUk { public class Rand { Random r; public Rand() { var rand = System.Security.Cryptography.RandomNumberGenerator.Create(); byte[] b = new byte[4]; rand.GetBytes(b); r = new Random(BitConverter.ToInt32(b, 0)); } public int Next(int maxValue) { return r.Next(maxValue); } public double NextDouble(double maxValue) { return r.NextDouble() * maxValue; } public T Pick<T>(IEnumerable<T> things) { return things.ElementAt(Next(things.Count())); } public T PickBias<T>(Func<T, double> bias, IEnumerable<T> things) { double d = NextDouble(things.Sum(x => bias(x))); foreach (var x in things) { if (d < bias(x)) return x; d -= bias(x); } throw new InvalidOperationException("fell off the end!"); } } } 

Answer 5

现在我没有时间去编写一个完整的algorithm，但是这里有一个想法：如果你的对手随机放置了船，那么放置概率是不是以（5.5,5.5）为中心的简单分布？ 例如，在x维度战列舰（5个单位长）的安置可能性在这里：

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

同样的计算对于y是有效的。 其他船只不会有如此陡峭的分布，但你最好的猜测仍然是中心。 在那之后，math方法将缓慢地放射对angular线（可能是平均船长17/5）。 例如：

 ........... ....xx... .....x..... ....xx... ........... 

很明显，这个想法需要join一些随机性，但是我认为这是一种纯粹的math运算。

Answer 6

没有什么复杂的，只是我想出了什么。 99.9％的时间击败了随机对手。 如果有人有这样的其他小挑战，会感兴趣，这是很好玩。

 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 => sX == pX && sY == pY).Any()); if (pX < 0 | pY<0) InvalidShot = true; if (pX >= gameSize.Width | pY >= gameSize.Height) InvalidShot = true; return InvalidShot; } private Point FireDirectedShot(Direction? direction, Point p) { ShotDirection = (Direction)direction; switch (ShotDirection) { case Direction.Up: pY--; break; case Direction.Down: p.Y++; break; case Direction.Left: pX--; 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() { } } } 

稍微浓缩一下，占用这里最小的空间，仍然可读。

Answer 7

关于比赛引擎的一些评论：

NewGame参数：

如果IbatleshipOpponent :: NewGame用于游戏前设置，并且需要一个大小，它也应该列出船舶及其各自的大小。 允许可变的电路板尺寸而不考虑可变船configuration是没有意义的。

船舶被封印：

我看不出有什么理由说明为什么课堂船被封闭。 在其他基本的东西，我希望船舶有一个名称，所以我可以输出消息，如（“你沉没我的{0}”，ship.Name）; 。 我也有其他的扩展，所以我认为船应该是可inheritance的。

时间限制：

虽然1秒的时间限制对比赛规则是有意义的，但它随着debugging而变得混乱。 BattleshipCompetition应该有一个简单的设置来忽略时间违规，以协助开发/debugging。 我还build议调查System.Diagnostics.Process :: UserProcessorTime /特权ProcessorTime / TotalProcessorTime更准确地查看使用多less时间。

沉船：

目前的API会告诉你什么时候你沉没了一艘oppenent的船只：

 ShotHit(Point shot, bool sunk); 

但不是你沉没的船！ 我认为这是人类战列舰规则的一部分，你需要声明“你沉没了我的战列舰！” （或驱逐舰，或子等）。

当人工智能试图冲出相互碰撞的船舶时，这一点尤为重要。 我想请求API更改为：

 ShotHit(Point shot, Ship ship); 

如果船是非零的，那就意味着这个镜头是一个沉没的镜头，而且你知道你沉没了哪一艘船，这是多久。 如果这个镜头是一个没有下沉的镜头，那么这个镜头就是空的，而且你没有进一步的信息。

Answer 8

CrossFire更新。 我知道它不能和法恩斯沃斯或者无畏之战竞争，但是比后者要快很多，而且在任何人想要尝试的情况下都很简单。 这依赖于我的库的当前状态，包括在这里使其易于使用。

 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(pX, pY, true)].Data; } set { this.history[SafeCalc(pX, pY, 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 pX >= 0 && pY >= 0 && pX < size.Width && pY < 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 (aX == bX - 1 || aX == bX + 1) && (aY == bY - 1 || aY == bY + 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)); } } 

}

Answer 9

This is about the best that I could put together in my free time, which is about non-existent. There is some game and match tallying stats going on, as I set up the main function to loop and continuously run the BattleshipCompetition until I pressed a key.

 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 (pX >= 0 && board[pX, pY] == ShotResult.UNKNOWN) { ctr++; pX--; } // spaces to the right p = new Point(x + 1, y); while (pX < gameSize.Width && board[pX, pY] == ShotResult.UNKNOWN) { ctr++; p.X++; } // spaces to the top p = new Point(x, y - 1); while (pY >= 0 && board[pX, pY] == ShotResult.UNKNOWN) { ctr++; pY--; } // spaces to the bottom p = new Point(x, y + 1); while (pY < gameSize.Height && board[pX, pY] == 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(); } } } 

This logic is the closest that I had to beating Dreadnought, winning about 41% of the individual games. (It actually did win one match by a count of 52 to 49.) Oddly enough, this class does not do as well against FarnsworthOpponent as an earlier version that was much less advanced.

Answer 10

My computer is being repaired by dell right now, but this is where i was at last week:

 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 => pX != shot.X); //} //else //{ // this.nextShots.RemoveAll(p => pY != shot.Y); //} } else { shot = new Point(-1, -1); } return shot; } private void addToNextShots(Point p) { if (!this.nextShots.Contains(p) && pX >= 0 && pX < this.gameSize.Width && pY >= 0 && pY < this.gameSize.Height) { if (this.board[pX, pY] == '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; } } } 

Answer 11

If you are brute forcing your analysis then you may find the mechanics of the supplied RandomOpponent highly inefficient. It allows itself to reselect already targeted locations and lets the framework force it to repeat till it hits one it hasn't touched yet or the timelimit per move expires.

This opponent has similar behaviour (the effective placement distribution is the same) it just does the sanity checking itself and only consumes one random number generation per call (amortized)).

This uses the classes in my extensions/library answer and I only supply the key methods/state.

Shuffle is lifted from Jon Skeet's answer here

 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 } 

Answer 12

I'm not going to be able to participate, but here's the algorithm I'd implement if I had time:

First, when I detect a hit I do not pursue the rest of the ship immediately – I build a table of ship locations and figure out whether I've hit all five at least once before starting to fully sink them. (Note that this is a bad policy for the multiple shot variant – see comments)

1. Hit the center (see final note below – 'center' is just a convenience for description)
2. Hit the spot 4 to the right of the center
3. Hit the spot 1 down and one to the right of the center
4. Hit the spot four to the right of the previous hit

5. Continue in that pattern (should end up with diagonal lines separated by 3 spaces filling the board) This should hit all 4 and 5 length boats, and a statistically large number of 3 and 2 boats.

6. Start randomly hitting spots inbetween the diagonals, this will catch the 2 and 3 length boats that haven't already been noticed.

Once I have detected 5 hits, I'd determine if the 5 hits are on separate boats. This is relatively easy by making a few more shots near locations where two hits are on the same horizontal or vertical line and are within 5 locations of each other (might be two hits on the same boat). If they are separate boats then continue to sink all the ships. If they are found to be the same boat, continue the filling patterns above until all 5 boats are located.

This algorithm is a simple filling algorithm. The key features are that it does not waste time sinking ships it knows about when there are still ships it's unaware of, and it doesn't use an inefficient filling pattern (ie, a fully random pattern would be wasteful).

Final notes:

A) "Center" is a random starting point on the board. This eliminates the primary weakness of this algorithm. B) While the description indicates drawing diagonals immediately from the start, ideally the algorithm merely shoots at 'random' locations that are along those diagonals. This helps prevent the competitor from timing how long until their ships are hit by predictable patterns.

This describes a 'perfect' algorithm in that it'll get all the ships in under (9×9)/2+10 shots.

However, it can be improved significantly:

Once a ship is hit, identify its size before doing the 'internal' diagonal lines. You may have found the 2 ship, in which case the internal diagonals can be simplified to find the 3 size ships more quickly.

Identify stages in the game and act accordingly. This algorithm may be good up to a certain point in the game, but other algorithms may yield better benefits as part of the endgame. Also, if the other player is very close to defeating you, another algorithm might work better – for instance a high risk algorithm might fail more often, but when it works it works quickly and you may beat your opponent who is closer to winning than you.

Identify the play style of the competitor – it may give you clues as to how they plan ship placement (ie, chances are good that their own algorithm most quickly identifies how they place their own ships – if the only tool you have is a hammer, everything looks like a nail)

-Adam

Answer 13

My entry.

Nothing terribly special, and I didn't get time to add all the good ideas I had.

But it seems to play fairly well. We'll see how it does in competition:

(put this in file Missouri.cs and added to project.)

 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(pY=0; pY<size.Height; ++pY) { for(pX=0; pX<size.Width; ++pX) { 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 ([e-mail])"; 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(pX, pX); vertExtent = new Extent(pY, pY); } 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 == pX) // New hit in the vertical direction { vertExtent.Min = Math.Min(vertExtent.Min, pY); vertExtent.Max = Math.Max(vertExtent.Max, pY); } else if (hit.Y == pY) { horzExtent.Min = Math.Min(horzExtent.Min, pX); horzExtent.Max = Math.Max(horzExtent.Max, pX); } } public Point[] GetNextTargets() { List<Point> bors = new List<Point>(); Point p; p = new Point(hit.X, vertExtent.Min-1); while (pY >= 0 && Player.theShotBoard[p] == Shot.Hit) { if (Player.theShotBoard[p] == Shot.Miss) { break; // Don't add p to the List 'bors. } --pY; } if (pY >= 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 (pY < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.Hit) { if (Player.theShotBoard[p] == Shot.Miss) { break; // Don't add p to the List 'bors. } ++pY; } if (pY < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.None) { bors.Add(p); } //------------------- p = new Point(horzExtent.Min-1, hit.Y); while (pX >= 0 && Player.theShotBoard[p] == Shot.Hit) { if (Player.theShotBoard[p] == Shot.Miss) { break; // Don't add p to the List 'bors. } --pX; } if (pX >= 0 && Player.theShotBoard[p] == Shot.None) { bors.Add(p); } //------------------- p = new Point(horzExtent.Max+1, hit.Y); while (pX < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.Hit) { if (Player.theShotBoard[p] == Shot.Miss) { break; // Don't add p to the List 'bors. } ++pX; } if (pX < 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[pX, pY]; } set { grid[pX, pY] = 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 += " ABCDEFGHIJ \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[pX, pY]; } set { grid[pX, pY] = value; } } public void ShotMiss(Point p) { int x,y; int min, max; min = Math.Max(pX-Target.Length+1, 0); max = Math.Min(pX, size.Width-Target.Length); for(x=min; x<=max; ++x) { DecrementRow(pY, x, x+Target.Length-1); } min = Math.Max(pY-Target.Length+1, 0); max = Math.Min(pY, size.Height-Target.Length); for(y=min; y<=max; ++y) { DecrementColumn(pX, y, y+Target.Length-1); } grid[pX, pY] = 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 += " ABCDEFGHIJ \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(pX-Target.Length+1, 0); max = Math.Min(pX, size.Width-Target.Length); for(x=min; x<=max; ++x) { if (Player.theShotBoard.isMissInRow(pY, x, x+Target.Length-1) == false) { ++potential; } } min = Math.Max(pY-Target.Length+1, 0); max = Math.Min(pY, size.Height-Target.Length); for(y=min; y<=max; ++y) { if (Player.theShotBoard.isMissInColumn(pX, 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[pX, pY]; } set { grid[pX, pY] = value; } } public override String ToString() { String output = ""; String horzDiv = " +----+----+----+----+----+----+----+----+----+----+\n"; String disp; int x,y; output += " ABCDEFGHIJ \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; } } 

Answer 14

This is not minimax. Actually after placing the ships, can't each player play on its own, resulting in a number of turns it took him to sink every opponent ship? The one that took less turns wins.

I don't think that there are any good general strategies beyond sinking hit ships and trying to minimize the number of shots to cover the remaining possible places where ships might hide.

Of course there might be counter-strategies for anything that's not random. But I don't think that there are strategies that are good against all possible players.

Answer 15

Actually, I think the biggest problem with the puzzle is that its essentially two moves. One move is placing your ships, the other is finding the enemy ships (however segmented that second part might be, aside from trying to beat a clock with a random factor, its just 'run your algorithm'). There's no mechanism to try to determine and then counter an enemy strategy, which is what makes similar competitions based around successive rounds of "rock paper scissors" pretty interesting.

Also, I think it would be cooler if you specified the game as a network protocol and then provided the framework to implement that protocol in C#, rather than dictate that all solutions should be C#, but that's just my opinion.

EDIT: I rescind my initial point, since I didn't read the competition rules carefully enough.

Answer 16

I always liked starting in the middle and spiraling away from that one point leaving no more than 1 blank space between any other points to account for that goddam sub… the space between shots was dependent on which ships were sunk. if the B-ship was last, the shots only had to leave 4 spaces in between to minimize wasted shots

Answer 17

There was a similar competition run by Dr James Heather of The University of Surrey on behalf of the British Computer Society.

Limitations were placed on resources – namely maximum processor time per turn, no state could be stored between moves, maximum heap size imposed. To limit time the AI could submit a move at any point within the time slot and would be asked for a move upon termination of the turn.

Very interesting – see more at: http://www.bcsstudentcontest.com/

Might give you some more ideas.

Answer 18

As it is, the solution opens and runs with no modification in monodevelop in ubuntu 9.10 linux

Answer 19

You wrote:

• Anything that is deemed against the spirit of the competition will be grounds for disqualification.
• Interfering with an opponent is against the spirit of the competition.

please define "against the spirit of the competition" and "interfering with an opponent"?

Also – to simplify, I recommend that you:

• disallow using CPU at all during opponent's CPU slot.
• disallow thread parallelism and instead give more CPU seconds on a single thread. This will simplify programming of AI and won't hurt anyone who is CPU/memory-bound anyway.

PS – a question for the CS post-docs lurking here: isn't this game solvable (ie is there a single, best strategy?). yes, the board size and number of steps makes minimax et al mandatory, but still I have to wonder… it's far from Go and chess in complexity.

Answer 20

I predict that the person who manages to reverse engineer their opponents random seed and call pattern will win.

Not sure how likely that is though.

Answer 21

It would also, presumably, be possible to run a series of these with variations on the game.

Adding in things like a 3d plane or being able to move a single ship instead of shoot for a turn would probably change the game a fair bit.

Answer 22

The one second total game time is machine specific. Once second worth of CPU operations will be different on my machine compared to the tournament machine. If I optimize the Battle Ship algorithm to utilize the most CPU time within 1 second, then it is run on a possible slower tournament machine, it will always lose.

I am not sure how to get around this limitation of the framework, but it should be addressed.

…

One idea is to do what was done in this competition http://www.bcsstudentcontest.com /

And have a maximum time per turn as opposed to maximum total game time. This way I could limit the algorithms to fit within a know turn time. A game might last 50 to 600+ turns, if the my algorithm manages its total game time, it might not give the enough time to do its best job or it could give too much time and lose. It is very hard to manage the total game time within the Battleship algorithm.

I would suggest changing the rules to limit the turn time not the total game time.

编辑

If I wrote an algorithm that enumerates all possible shots and then ranks them, then takes the highest ranking shot. It would take too long to generate all possible shots, so I would let the algorithm run for a certain amount of time then stop it.

If there was a turn based limit, I could let the algorithm run for 0.9 seconds and return the highest ranking shot, and be well withing the turn time limit.

If I am limited to total game time of one second, it will be difficult to determine how long the algorithm should run for each turn. I will want to maximum my CPU time. If a game lasted 500 round I could limit each turn to 0.002 seconds, but if a game lasted 100 rounds I could give each turn 0.01 seconds of CPU time.

It would be impractical for a algorithm to use an semi-exhaustive search of the shot space to find the best shot with the current limitation.

The 1 second total game time is limiting the type of algorithms that can be effectively used to compete in the game.

Answer 23

I'm copping out here by not putting actual code in – but I will hazard some general observations:

• Since all ships are at least 2 cells in size, you can use an optimization I saw on an implementation of the game in Space Quest V – which only fires at alternate cells in a diamond pattern while it is "seeking" a target. This eliminates half the squares, while still guaranteeing that you will find all the ships eventually.
• A random firing pattern when seeking targets will statistically yield the best results over many games.

Answer 24

![Probability Density][1]enter image description her

![enter image description here][2]

I experimented with comparing the results of randon shooting vs a dumb hunt/target and finally a sophisticated search.

The best solution appears to be to create a probability density function for the how likely any individual square is used by the remaining ships, and aim with the square with the highest value.

You can see my results here enter link description here

Answer 25

"Battleship" is what's known as a classic computer science NP-complete problem.

http://en.wikipedia.org/wiki/List_of_NP-complete_problems

(look for Battleship – it's there, under games and puzzles)