最好的战舰AI是什么?

战舰!

早在2003年(当时我17岁)，我参加了一个战舰的人工智能编码比赛。尽管我输了那场比赛，但我从中获得了很多乐趣，也学到了很多东西。

现在，我想恢复这个比赛，在搜索最好的战舰AI。

这里是这个框架现在托管在Bitbucket上。

获胜者将获得+450声望奖励!比赛从2009年11月17日开始。17号零时之前的投稿和编辑将不被接受。(中央标准时间) 尽早提交你的作品，这样你就不会错过机会!< / p >

为了保持这个<强大的>目标，请遵循比赛的精神。

游戏规则:

  1. 游戏在10x10的网格上进行。
  2. 每个参赛者将5艘船(长度为2、3、3、4、5)中的每一艘放在他们的网格上。
  3. 没有船只可以重叠，但它们可以相邻。
    4. 然后，选手们轮流向对手射击。
    • 游戏的一个变体允许每次齐射多次，每艘幸存的船一次。
      • 李< / ul > < / >
    • 如果击球沉、命中或未命中，对手将通知选手。
    • 当任何一名玩家的所有船只都沉没时，游戏就结束了。

比赛规则:

  1. 竞赛的精神是找出最好的战舰算法。
  2. 任何违反比赛精神的行为都将被取消比赛资格。
  3. 干扰对手是违反比赛精神的。
  4. 多线程可以在以下限制下使用:
    • 当还没有轮到您时，只能有一个线程在运行。(但是，任何数量的线程都可能处于“挂起”状态)。
    • 任何线程都不能以“Normal”以外的优先级运行。
    • 考虑到上述两个限制，你将保证在你的回合中至少有3个专用CPU内核。
      • 李< / ul > < / >
    • 每个游戏的CPU时间限制为1秒，分配给主线程上的每个竞争者。
    • 超时会导致当前游戏的失败。
    • 任何未处理的异常都会导致当前游戏的失败。
    • 允许网络访问和磁盘访问，但您可能会发现时间限制相当令人望而却步。但是，添加了一些设置和拆卸方法来减轻时间压力。
    • 代码应该在堆栈溢出时作为答案发布，如果太大，则链接。
    • 一个条目的最大总大小(未压缩)为1mb。
    • 正式来说，. net 2.0 / 3.5是唯一的框架需求。
    • 您的条目必须实现IBattleshipOpponent接口。

得分:

  1. 在101场比赛中取得最好的51场比赛是比赛的赢家。
  2. 所有参赛者将以循环赛的方式进行比赛。
  3. 然后，表现最好的一半选手将进行双淘汰赛，决出冠军。(实际上是大于或等于1 / 2的2的最小幂。)
  4. 我将在比赛中使用TournamentApi框架。
  5. 考试结果将在这里公布。
  6. 如果你提交了一个以上的作品，只有你得分最高的作品才有资格获得双冠。

好运！玩得开心!

< p > 编辑1: < br / > 感谢释放，他在Ship.IsValid函数中发现了一个错误。问题已经解决了。

.请下载框架的更新版本 < p > 编辑2: < br / > 由于人们对将统计数据持久化到磁盘等非常感兴趣，所以我添加了一些非计时设置和删除事件，它们应该能够提供所需的功能。这是一个semi-breaking变化。也就是说:修改了接口，添加了功能，但不需要body。

.请下载框架的更新版本 < p > 编辑3: < br / > 错误修复1:GameWon和GameLost只在超时的情况下被调用 错误修复2:如果引擎在每一场比赛中都暂停，竞争将永远不会结束

.请下载框架的更新版本 < p > 编辑4: < br / > 比赛结果:< / p >

.

72101 次浏览
小开

这是我的入口!(最天真的解决方案)

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

你写的:

  • 任何违反比赛精神的行为都将被取消比赛资格。
  • 干扰对手是违反比赛精神的。

请定义一下“违反比赛精神”和“干扰对手”。

此外，为了简化，我建议你:

  • 禁止在对手的CPU插槽期间使用CPU。
  • 不允许线程并行，而是在单个线程上提供更多的CPU秒。这将简化AI编程，并且不会伤害任何CPU/内存受限的人。

PS -这里有一个CS博士后的问题:这个游戏是可解决的吗(也就是说，是否有一个唯一的最佳策略?)是的，棋盘的大小和步骤数使得minimax等是强制性的，但我仍然想知道……它远没有围棋和国际象棋复杂。

小开

这不是极大极小。实际上，在放置船只之后，难道每个玩家都不能自己玩，导致他花了很多回合去击沉所有对手的船只吗?回合少的人赢。

我认为除了击沉被击中的船只和尽量减少射击数量以覆盖剩下的船只可能隐藏的地方之外，没有什么好的总体策略。

当然，对于任何非随机的情况，我们都有对策。但我不认为有什么策略对所有可能的对手都有效。

小开

我预测，能够逆向设计对手随机种子和呼叫模式的人将获胜。

但不确定这种可能性有多大。

小开

实际上，我认为这个谜题最大的问题在于它本质上是两个步骤。一个步骤是放置你的船只，另一个步骤是找到敌人的船只(不管第二部分是如何分割的，除了尝试用随机因素打败时间外，它只是“运行你的算法”)。游戏中不存在决定并反击敌人策略的机制，这也是基于连续回合的“石头剪刀布”的类似竞争非常有趣的原因。

此外，我认为如果你将游戏指定为网络协议，然后提供框架以c#实现该协议，而不是规定所有解决方案都应该是c#，这将更酷，但这只是我的观点。

编辑:我取消我最初的观点，因为我没有足够仔细地阅读比赛规则。

小开

我总是喜欢从中间开始，从那个点螺旋离开，在任何其他点之间留下不超过1个空白，以解释那个该死的子…射击间隔取决于哪艘船被击沉。如果b舰是最后一艘，射击之间只需要留出4个空间来减少浪费

小开

萨里大学的詹姆斯·希瑟博士代表英国计算机学会举办了一次类似的比赛。

对资源的限制——即每回合的最大处理器时间，移动之间不能存储状态，最大堆大小。为了限制时间，AI可以在时间段内的任何时间点提交移动，并在回合结束时被要求移动。

非常有趣——更多信息请访问:http://www.bcsstudentcontest.com/

也许能给你更多的建议。

小开

当然，我们也有可能在游戏的基础上运行一系列类似的游戏。

添加3d飞机或能够移动一艘船而不是射击回合等内容可能会改变游戏。

小开

“战舰”是一个经典的计算机科学np完全问题。

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

(寻找战舰-它在那里，在游戏和谜题下)

小开

关于竞争引擎的一些评论:

NewGame参数:

如果IBattleshipOpponent::NewGame用于游戏前设置，并接受一个boardsize，那么它还应该接受一个船的列表及其各自的大小。在不考虑船舶配置变化的情况下，允许可变的船板尺寸是没有意义的。

船舶是密封的:

我看不出为什么船班是封闭的。在其他基本的东西中，我希望船舶有一个名称，这样我就可以输出像("You sink my {0}"， ship.Name);这样的消息。我还考虑了其他扩展，所以我认为Ship应该是可继承的。

时间限制:

虽然1秒的时间限制对比赛规则来说是有意义的，但它完全扰乱了调试。BattleshipCompetition应该有一个容易忽略时间冲突的设置，以帮助开发/调试。我还建议调查System.Diagnostics。Process::UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime用于更准确地查看正在使用的时间。

沉没的船只:

当你击沉对手的船时，当前的API会通知你:

ShotHit(Point shot, bool sunk);

而不是你击沉的哪一个船!我认为这是人类战列舰规则的一部分，你必须宣布“你击沉了我的战列舰!”(或驱逐舰，或潜艇等)。

当AI试图清除相互碰撞的船只时，这一点尤其重要。我想要求API更改为:

ShotHit(Point shot, Ship ship);

如果船为非空，它意味着射击是击沉射击，并且你知道你击沉了哪艘船，以及它是多长时间。如果射击是一个非下沉射击，那么船是空的，你没有进一步的信息。

小开

我现在没有时间写一个完整的算法，但我有一个想法:如果你的对手随机放置船只，放置概率不会是一个以(5.5,5.5)为中心的简单分布吗?例如，战列舰(5个单位长)在x维度的放置可能性如下:

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

同样的计算也适用于y。其他船只的分布不会那么陡峭，但你最好的猜测仍然是中心。在此之后，数学方法将慢慢地向中心外辐射对角线(可能是平均船的长度，17/5)。例:

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

显然，这个想法需要添加一些随机性，但我认为从纯粹的数学角度来看，这是可行的。

小开

事实上，这个解决方案在ubuntu 9.10 linux的monodevelop中无需修改就可以打开和运行

小开

1秒总计游戏时间是特定于机器的。与比赛机器相比，我的机器上每秒的CPU操作将是不同的。如果我优化Battle Ship算法，让它在1秒内利用最多CPU时间，那么它就会运行在可能较慢的比赛机器上，它总是会输。

我不确定如何绕过框架的这一限制，但它应该得到解决。

.．.

一个想法是做在这个比赛中所做的事情

每个回合有最大时间，而不是最大总游戏时间。这样我可以限制算法以适应已知的转弯时间。一款游戏可能会持续50到600多个回合，如果我的算法管理它的总游戏时间，它可能没有足够的时间来发挥最佳效果，或者它可能会花费太多时间而失败。在战舰算法中管理游戏总时间是非常困难的。

我建议修改规则，限制回合时间，而不是总游戏时间。

编辑

如果我写了一个算法，枚举所有可能的镜头，然后对它们进行排名，然后选择排名最高的镜头。生成所有可能的镜头需要很长时间，所以我会让算法运行一段时间，然后停止它。

如果有基于回合的限制，我可以让算法运行0.9秒并返回排名最高的镜头，并且在回合时间限制内很好。

如果我的游戏总时间被限制在1秒，那么就很难确定算法在每个回合中应该运行多长时间。我想要最大化我的CPU时间。如果游戏持续500轮，我可以将每个回合限制在0.002秒，但如果游戏持续100轮，我可以给每个回合0.01秒的CPU时间。

对于一个算法来说，使用半穷举搜索镜头空间来找到当前限制的最佳镜头是不切实际的。

1秒的游戏总时间限制了可以有效用于游戏竞争的算法类型。

小开
这不是一个完全成熟的答案，但用常见的代码来混淆真实的答案似乎没有什么意义。 因此，我将本着开放源码的精神介绍一些扩展/通用类。 如果你使用这些，那么请更改名称空间或试图将所有内容编译到一个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(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
}
}

有些扩展，有些复制了主框架中的功能，但应该由你自己完成。

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

我经常用的东西。

enum OpponentsBoardState
{
Unknown = 0,
Miss,
MustBeEmpty,
Hit,
}
< p >随机化。 安全但可测试，对测试有用。< / p > 
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!");
}
}
}
小开

如果你强迫自己进行分析，那么你可能会发现随机对手的机制非常低效。它允许自己重新选择已经目标的位置，并让框架强制它重复，直到它击中它还没有触及的位置，或者每次移动的时间限制到期。

这个对手有类似的行为(有效的位置分布是相同的)，它只是自己进行完整性检查，每次调用只消耗一个随机数生成(平摊)。

这使用了我的扩展/库答案中的类，我只提供关键方法/状态。

Shuffle派生自乔恩·斯基特的答案

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
}
小开
< p >交火中更新。 我知道它不能与Farnsworth或Dreadnought竞争，但它比后者快得多，而且如果有人想尝试的话，它很简单。 这依赖于我的库的当前状态，包括在这里使它易于使用 
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));
}
}

｝

小开

我在这里没有放入实际的代码，但我将冒险进行一些一般性的观察:

  • 因为所有的飞船都至少有2个细胞大小，你可以使用我在《太空探索V》中看到的一个优化——当它“寻找”一个目标时，只向菱形图案的交替细胞开火。这将消除一半的方格，同时仍然保证你最终会找到所有船只。
  • 在许多游戏中，寻找目标时的随机射击模式从统计上来说会产生最好的结果。
小开

我不能参与，但如果我有时间，我将实现以下算法:

首先，当我发现被击中时，我不会立即追击剩下的船只——我会建立一个船的位置表，并在开始完全击沉它们之前确定我是否至少一次击中了所有五艘船。(注意，这是一个糟糕的策略多镜头变体-见评论)

  1. 点击中心(请参阅下面的最后说明-“中心”只是为了方便描述)
  2. 打中间右边的点
  3. 击中第一个向下的点和中间右边的点
  4. 击中上一个击球点右边的第四个点

  5. 继续这种模式(应该以3个空格分隔的对角线结束)，这应该会击中所有4和5长的船，以及统计上大量的3和2长的船。

  6. 开始随机地击中对角线之间的点，这将抓住2和3长度的船还没有被注意到。

一旦我检测到5个命中，我将确定这5个命中是否在不同的船上。这是相对容易的，只要在两个命中点在同一水平或垂直线上，并且彼此之间有5个位置(可能是同一条船上的两个命中点)的位置附近多拍几次就可以了。如果他们是分开的船，那么继续击沉所有的船。如果发现它们是同一艘船，继续上面的填充模式，直到所有5艘船都被定位。

该算法是一种简单的填充算法。关键的特点是，它不会浪费时间去击沉它知道的船只，当仍然有它不知道的船只时，它不会使用低效的填充模式(即，完全随机的模式将是浪费的)。

最后指出:

< p >)“中心”是棋盘上的一个随机起点。这消除了该算法的主要弱点。 B)虽然描述表明从一开始就立即绘制对角线，但理想情况下，算法只是在这些对角线上的“随机”位置射击。这有助于防止竞争对手计算他们的船被可预测的模式击中的时间

这描述了一个“完美”的算法，因为它可以让所有船只在(9x9)/2+10次射击之内。

但是，它可以显著改善:

一旦一艘船被击中，在做“内部”对角线之前确定它的大小。你可能已经找到了2号船，在这种情况下，内部对角线可以简化以更快地找到3号船。

确定游戏的各个阶段并采取相应的行动。这种算法可能在游戏的某一点上很好，但其他算法可能会在游戏的最后产生更好的收益。此外，如果其他玩家非常接近击败你，另一个算法可能会更好-例如，一个高风险的算法可能更容易失败，但当它起作用时，它会很快起作用，你可能会击败比你更接近胜利的对手。

识别竞争对手的打法——这可能会给你一些线索，让你知道他们是如何规划船只位置的(比如，他们自己的算法很有可能最快速地识别出他们如何放置自己的船只——如果你唯一的工具是锤子，那么所有的东西看起来都像钉子)

亚当

小开

没有那么复杂，但这是我想到的。它有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 => 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() { }
}
}

稍微压缩，以占用最小的空间在这里，仍然是可读的。

小开

这是一个供人们玩的对手:

  • http://natekohl.net/files/FarnsworthOpponent.cs < a href = " http://natekohl.net/files/FarnsworthOpponent.cs " > < / >

而不是使用一个固定的几何启发策略，我认为这将是有趣的尝试估计潜在的可能性，任何特定的未探索的空间持有一艘船。

为了做到这一点，你需要探索所有符合你当前世界观的船的可能配置，然后基于这些配置计算概率。你可以把它想象成探索一棵树:

一个可能的战列舰国家的扩展http://natekohl.net/media/battleship-tree.png

在考虑了所有与你所知道的世界(例如船不能重叠，所有击中的方块必须是船等)相吻合的树的叶子之后，你可以计算出船只在每个未探索的位置出现的频率，以估计船只坐在那里的可能性。

这可以可视化为热图，其中热点更有可能包含船只:

每个未开发位置的概率热图http://natekohl.net/media/battleship-probs.png .

我喜欢这个战列舰比赛的一个原因是上面的树几乎小到可以强制使用这种算法。如果这5艘船中的每一艘都有大约150个可能的位置，那么1505 = 750亿种可能性。这个数字只会越来越小，特别是如果你可以排除整艘船。

我上面链接的对手并没有探索整棵树;750亿美元仍然太大，无法在一秒钟内进入。不过，在一些启发式的帮助下，它确实试图估计这些概率。

小开
最佳答案

我赞成每场比赛多打几场比赛。制作50款游戏只是抛硬币。我需要做1000个游戏，才能在测试算法之间找到合理的区别。

下载无畏1.2。

策略:

  • 跟踪所有有>0命中的船的可能位置。这个列表永远不会超过30K，所以它可以精确地保存，不像所有船只的所有可能位置的列表(非常大)。

    • GetShot算法有两部分，一部分生成随机镜头，另一部分生成随机镜头 试图击沉一艘已经被击沉的船。如果存在一个所有被击中的船只都被击沉的位置，我们就会随机射击。除此之外，我们将通过选择射击地点(即排除所有可能的位置)去完成一艘船的沉没

  • 对于随机拍摄，根据未沉没船只重叠位置的可能性计算最佳拍摄位置。

  • 自适应算法，将船只放置在对手统计上不太可能射击的位置。

  • 自适应算法，它倾向于在统计上对手更有可能放置他的船的位置射击。

  • 船只之间基本不接触。

小开

这是我在空闲时间能做的最好的东西，几乎不存在。有一些游戏和比赛统计数据正在进行，因为我设置了主函数循环并持续运行BattleshipCompetition，直到我按下一个键。

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

这是我最接近于击败Dreadnought的逻辑，赢得了41%的单人游戏。(事实上，它确实以52比49赢得了一场比赛。)奇怪的是，这个职业在对抗farnsworthrival时表现不如一个更不先进的早期版本。

小开

我的电脑现在正在戴尔维修，但这是我上周在哪里:

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; }
}
}
小开

我的条目。

没有什么特别的，我也没有时间把我所有的好主意都加上去。

但它似乎玩得相当不错。我们将看到它在竞争中的表现:

(将此放在Missouri.cs文件中并添加到项目中。)

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;
}
}
小开

![概率密度][1]输入图像描述她

![此处输入图像描述][2]

我尝试着比较随机射击和愚蠢的狩猎/目标以及复杂搜索的结果。

最好的解决方案似乎是创建一个概率密度函数，计算剩余船只使用任何方块的可能性，并以值最高的方块为目标。

你可以在这里看到我的结果在这里输入链接描述


提交答案