最好的战舰人工智能是什么？
https://stackoverflow.com/questions/1631414
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
战舰！
早在 2003 年（当时我 17 岁），我参加了 战舰人工智能 编码竞赛。尽管我输掉了那场比赛，但我从中获得了很多乐趣并学到了很多东西。
现在，我想重启这场比赛，寻找最好的战舰人工智能。
获胜者将获得+450声望！ 比赛将于 2009 年 11 月 17 日. 。17 日零时之后将不接受任何输入或编辑。（中部标准时间） 尽早提交您的参赛作品，这样您就不会错过机会！
为了保持这个 客观的, ，请遵守竞赛精神。
游戏规则：
- 游戏在 10x10 网格上进行。
- 每位参赛者将 5 艘船（长度为 2、3、3、4、5）分别放置在自己的网格上。
- 任何船只都不能重叠，但它们可以相邻。
- 然后，参赛者轮流向对手射击。
- 游戏的一个变体允许每次齐射发射多次射击，每艘幸存的船只射击一次。
- 如果击球落入、击中或未击中，对手将通知参赛者。
- 当任何一位玩家的所有船只都沉没时，游戏结束。
比赛规则：
- 比赛的精神是寻找最好的战舰算法。
- 任何被认为违反比赛精神的行为都将被取消资格。
- 干扰对手是违背比赛精神的。
- 多线程可以在以下限制下使用：
- 当还没有轮到您时，运行的线程不得超过一个。（但是，任意数量的线程都可以处于“挂起”状态）。
- 任何线程都不能以“正常”以外的优先级运行。
- 考虑到上述两个限制，您将保证在轮到您时至少有 3 个专用 CPU 核心。
- 每场比赛在主线程上分配给每个参赛者的 CPU 时间限制为 1 秒。
- 时间用完将导致输掉当前游戏。
- 任何未处理的异常都将导致输掉当前游戏。
- 允许网络访问和磁盘访问，但您可能会发现时间限制相当令人望而却步。然而，添加了一些设置和拆卸方法以减轻时间压力。
- 代码应作为答案发布在堆栈溢出上，或者如果太大，则应链接。
- 条目的最大总大小（未压缩）为 1 MB。
- 官方规定，.Net 2.0 / 3.5 是唯一的框架要求。
- 您的参赛作品必须实现 IBattleshipOpponent 接口。
评分：
- 101 场比赛中最好的 51 场比赛获胜。
- 所有参赛者将以循环赛的方式进行比赛。
- 然后，最好的一半参赛者将进行双败淘汰赛，以确定获胜者。（实际上是大于或等于一半的最小的二的幂。）
- 我将使用 锦标赛API 锦标赛的框架。
- 结果将发布在这里。
- 如果您提交了多个参赛作品，则只有得分最高的参赛作品才有资格参加双淘汰赛。
祝你好运！玩得开心！
编辑1：
谢谢 弗里德, ，谁发现了一个错误 Ship.IsValid 功能。它已被修复。请下载该框架的更新版本。
编辑2：
由于人们对将统计数据保存到磁盘等方面非常感兴趣，因此我添加了一些非定时设置和拆卸事件，以提供所需的功能。这是一个 半破坏性改变. 。也就是说：接口已被修改以添加功能，但它们不需要主体。请下载该框架的更新版本。
编辑3：
错误修复1： GameWon 和 GameLost 只有在暂停的情况下才会被叫到。
错误修复 2：如果引擎每场比赛都超时，比赛将永远不会结束。
请下载该框架的更新版本。
编辑4：
比赛结果：
解决方案
我支持每场比赛进行更多比赛的动议。玩 50 场游戏只是抛一枚硬币。我需要进行 1000 场游戏才能在测试算法之间做出合理的区分。
下载 无畏舰1.2.
策略：
跟踪命中次数 >0 的船舶的所有可能位置。该列表永远不会超过约 30K，因此可以准确保存，这与所有船舶的所有可能位置列表（非常大）不同。
GetShot 算法由两部分组成，一部分用于生成随机镜头，另一部分用于生成随机镜头 试图完成击沉一艘已经被击中的船。如果存在所有被击中的船只都沉没的可能位置（从上面的列表中），我们会进行随机射击。否则，我们会尝试通过选择一个射击位置来消除最可能的位置（加权）来完成击沉一艘船。
对于随机射击，根据其中一艘未沉船与位置重叠的可能性来计算最佳射击位置。
自适应算法将船只放置在统计上对手不太可能射击的位置。
自适应算法更喜欢在统计上对手更有可能放置船只的位置进行射击。
地方船只大多不互相接触。
其他提示
这是我的条目！（可能是最幼稚的解决方案）
“随机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() { }
}
}
这是人们可以对抗的对手：
我认为尝试这样做会很有趣，而不是使用固定的几何启发策略 估计潜在的概率 任何特定的未探索空间都拥有一艘船。
为了正确地做到这一点，您需要探索适合您当前世界观的所有可能的船舶配置，然后根据这些配置计算概率。你可以把它想象成探索一棵树：
可能的战舰状态的扩展 http://natekohl.net/media/battleship-tree.png
在考虑了那棵树上所有与你对世界的了解相一致的叶子之后 （例如。船只不能重叠，所有命中的方格必须是船只，等等） 您可以计算船只出现在每个未探索位置的频率，以估计船只停泊在那里的可能性。
这可以可视化为热图，其中热点更有可能包含船只：
每个未探索位置的概率热图 http://natekohl.net/media/battleship-probs.png
我喜欢这个战舰竞赛的一件事是上面的树几乎小到足以暴力破解这种算法。如果 5 艘船每艘都有大约 150 个可能的位置，那就是 1505 = 750 亿种可能性。而且这个数字只会变得更小，特别是如果你能消灭整艘船的话。
我上面链接到的对手并没有探索整棵树；750 亿美元仍然太大，无法在一秒钟内进入。不过，它确实尝试在一些启发式的帮助下估计这些概率。
这不是一个成熟的答案，但用常见的代码混淆真正的答案似乎没有什么意义。因此，我本着开源的精神提出了一些扩展/通用类。如果您使用这些，请更改命名空间，否则尝试将所有内容编译到一个 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,
}
随机化。安全但可测试，对于测试很有用。
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!");
}
}
}
我现在没有时间编写成熟的算法，但这里有一个想法：如果你的对手随机放置船只，那么放置概率不是以 (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....
...........
显然，这个想法需要添加一些随机性，但我认为纯粹从数学角度来说这就是正确的方法。
没有什么复杂的，但这就是我想出的。它以 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() { }
}
}
稍微压缩一下，以占用最小的空间，并且仍然可读。
关于竞赛引擎的一些评论：
新游戏参数：
如果 IBattleshipOpponent::NewGame 用于赛前设置并采用棋盘尺寸，那么它还应该采用船舶列表及其各自的尺寸。允许可变的板尺寸而不允许可变的船舶配置是没有意义的。
船舶被密封：
我看不出有什么理由为什么“船”级被密封。除其他基本事项外，我希望船舶有一个名称，这样我就可以输出类似的消息 （“你击沉了我的 {0}”，ship.Name）；. 。我也想到了其他扩展，所以我认为 Ship 应该是可继承的。
时间限制：
虽然 1 秒的时间限制对于锦标赛规则来说是有意义的，但它完全扰乱了调试。战舰竞赛应该有一个简单的设置来忽略时间违规，以帮助开发/调试。我还建议调查 System.Diagnostics.Process::UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime 以更准确地了解正在使用的时间。
沉船：
当前的 API 会在您击沉对手的船只时通知您：
ShotHit(Point shot, bool sunk);
但不是 哪个 你的船沉了！我认为这是人类战舰规则的一部分，你必须宣布“你击沉了我的战舰！（或驱逐舰，或潜艇等）。
当人工智能试图冲走相互碰撞的船只时，这一点尤其重要。我想请求将 API 更改为：
ShotHit(Point shot, Ship ship);
如果 船 为非空，这意味着该镜头是沉没镜头，并且您知道沉没的船以及沉没的时间。如果射击是非下沉的射击，则 Ship 为空，并且您没有进一步的信息。
穿越火线更新了。我知道它无法与 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));
}
}
}
这大概是我在空闲时间能整理出来的最好的东西了，但实际上几乎不存在。当我将主函数设置为循环并连续运行战舰竞赛直到我按下某个键时，正在进行一些游戏和比赛统计统计数据。
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 的比分赢得了一场比赛。）奇怪的是，这个级别在对抗 FarnsworthOpponent 时的表现不如早期版本，后者的高级程度要低得多。
我的电脑现在正在由戴尔维修，但这是我上周的情况：
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; }
}
}
如果您强制进行分析，那么您可能会发现所提供的 RandomOpponent 的机制效率非常低。它允许自己重新选择已经目标的位置，并让框架强制它重复，直到它到达尚未触及的位置或每次移动的时间限制到期。
该对手具有类似的行为（有效布局分布相同），它只是自行进行健全性检查，并且每次调用仅消耗一个随机数生成（摊销）。
这使用我的扩展/库答案中的类，我只提供关键方法/状态。
随机播放从 乔恩·斯基特的回答在这里
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
}
我无法参与，但如果有时间，我会实现以下算法：
首先，当我检测到被击中时，我不会立即追击船的其余部分 - 我会建立一个船位置表，并计算出在开始完全击沉它们之前我是否至少击中了所有五个船。（请注意，这对于多次射击变体来说是一个糟糕的策略 - 请参阅评论）
- 击中中心（请参阅下面的最后注释 - “中心”只是为了方便描述）
- 击中中心右侧的 4 号位置
- 击中中心右侧 1 个下方的位置
- 击中前一击右侧第四个位置
继续这种模式（最终应该是由 3 个空格隔开的对角线填充棋盘）这应该击中所有 4 和 5 长度的船，以及统计上大量的 3 和 2 船。
开始随机击中对角线之间的点，这将捕获尚未被注意到的 2 和 3 长的船。
一旦我检测到 5 次命中，我就会确定这 5 次命中是否在不同的船上。通过在两次命中位于同一水平或垂直线上并且彼此相距不超过 5 个位置（可能是在同一条船上两次命中）的位置附近进行更多射击，这相对容易。如果它们是分开的船，那么继续击沉所有的船。如果发现是同一艘船，则继续上面的填充模式，直到找到所有 5 艘船。
该算法是一个简单的填充算法。关键特征是，当仍然有它不知道的船只时，它不会浪费时间沉没它知道的船只，并且它不使用低效的填充模式（即，完全随机的模式会造成浪费）。
最后注意事项：
A) “中心”是棋盘上的一个随机起点。这消除了该算法的主要弱点。B) 虽然描述表明从一开始就立即绘制对角线，但理想情况下，该算法仅在沿着这些对角线的“随机”位置进行拍摄。这有助于防止竞争对手计算他们的船只多久会被可预测的模式击中。
这描述了一个“完美”的算法，因为它可以让所有船只都在 (9x9)/2+10 的射击范围内。
然而，它可以显着改进：
一旦一艘船被击中，在绘制“内部”对角线之前先确定其大小。您可能已经找到了 2 艘船，在这种情况下，可以简化内部对角线以更快地找到 3 号船。
确定游戏的阶段并采取相应的行动。该算法可能在游戏中的某个点上表现良好，但其他算法可能会在最终游戏中产生更好的收益。此外，如果其他玩家非常接近击败你，另一种算法可能会更好 - 例如，高风险算法可能会更频繁地失败，但当它起作用时，它会很快起作用，你可能会击败比你更接近获胜的对手。
确定竞争对手的游戏风格 - 它可能会为您提供有关他们如何计划船舶放置的线索（即，他们自己的算法很可能最快速地识别他们如何放置自己的船舶 - 如果您拥有的唯一工具是锤子，一切看起来都像钉子）
-亚当
我的条目。
没什么特别的，而且我没有时间添加我所有的好想法。
但似乎玩得还不错。我们将看看它在竞争中的表现：
（将其放入文件中 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;
}
}
这不是极小极大。其实放置船只后，不是每个玩家都可以自己玩，导致自己需要经过很多回合才能击沉对方的船只吗？轮数较少的获胜。
我认为除了击沉被击中的船只并尽量减少射击次数以覆盖船只可能隐藏的剩余可能位置之外，没有任何好的通用策略。
当然，对于任何非随机的事情都可能有对策。但我不认为存在适合所有可能玩家的策略。
事实上，我认为这个谜题最大的问题在于它本质上有两个动作。一个动作是放置你的船只，另一个动作是寻找敌方船只（无论第二部分如何分段，除了试图用随机因素打败时钟之外，它只是“运行你的算法”）。没有任何机制可以尝试确定并反击敌人的策略，这使得基于连续几轮“石头剪刀布”的类似比赛变得非常有趣。
另外，我认为如果您将游戏指定为网络协议，然后提供用 C# 实现该协议的框架，而不是规定所有解决方案都应该是 C#，那会更酷，但这只是我的意见。
编辑：我撤销我最初的观点，因为我没有足够仔细地阅读比赛规则。
我总是喜欢从中间开始，然后从那个点螺旋式离开，在任何其他点之间留下不超过 1 个空白，以说明那个该死的子......射击之间的间隔取决于沉没的船只。如果B舰在最后，射击之间只需留出4个空间，以尽量减少浪费的射击
萨里大学的 James Heather 博士代表英国计算机协会举办了类似的竞赛。
对资源进行了限制——即每轮的最大处理器时间、移动之间不能存储状态、施加最大堆大小。为了限制时间，人工智能可以在时隙内的任何点提交移动，并在回合结束时被要求移动。
非常有趣 - 更多内容请参见： http://www.bcsstudentcontest.com/
可能会给你一些更多的想法。
事实上，该解决方案在 ubuntu 9.10 linux 中的 monodevelop 中打开并运行，无需修改
你写了：
- 任何被认为违反比赛精神的行为都将被取消资格。
- 干扰对手是违背比赛精神的。
请定义“违反比赛精神”和“干扰对手”？
另外 - 为了简化，我建议您：
- 在对手的 CPU 槽位期间完全禁止使用 CPU。
- 不允许线程并行，而是在单个线程上给予更多的 CPU 秒数。这将简化人工智能的编程，并且不会伤害任何受 CPU/内存限制的人。
PS - 一个针对潜伏在这里的 CS 博士后的问题：这个游戏是不是可以解决的（即有没有单一的最佳策略？）。是的，棋盘尺寸和步数使得 minimax 等人成为强制性的，但我仍然想知道......它的复杂性与围棋和国际象棋相差甚远。
我预测，成功对对手随机种子和调用模式进行逆向工程的人将会获胜。
但不确定这种可能性有多大。
据推测，也可以在游戏中运行一系列具有变化的游戏。
添加诸如 3D 飞机之类的东西或能够移动一艘船而不是射击转弯可能会稍微改变游戏。
那一秒 全部的 游戏时间因机器而异。与锦标赛机器相比，我的机器上的第二次 CPU 操作将会有所不同。如果我优化战舰算法以在 1 秒内利用最多的 CPU 时间，那么它在可能较慢的比赛机器上运行，它总是会输。
我不确定如何绕过框架的这个限制，但应该解决这个问题。
...
一个想法就是做本次比赛中所做的事情 http://www.bcsstudentcontest.com/
每回合有一个最大时间，而不是最大总游戏时间。这样我就可以限制算法以适应已知的周转时间。一场游戏可能会持续 50 到 600 多个回合，如果我的算法管理其总游戏时间，它可能无法提供足够的时间来完成其最佳工作，或者可能会提供太多时间并失败。在战舰算法中管理总游戏时间非常困难。
我建议更改规则以限制回合时间而不是总游戏时间。
编辑
如果我编写一个算法，枚举所有可能的镜头，然后对它们进行排名，然后拍摄排名最高的镜头。生成所有可能的镜头需要太长时间，因此我会让算法运行一定时间然后停止。
如果有基于回合的限制，我可以让算法运行 0.9 秒并返回排名最高的镜头，并且很好地遵守回合时间限制。
如果我将游戏总时间限制为一秒，则很难确定算法每回合应运行多长时间。我想要最大化我的 CPU 时间。如果游戏持续 500 轮，我可以将每轮限制为 0.002 秒，但如果游戏持续 100 轮，我可以为每轮提供 0.01 秒的 CPU 时间。
在当前限制下，算法使用镜头空间的半穷举搜索来找到最佳镜头是不切实际的。
1 秒的总游戏时间限制了可有效用于在游戏中竞争的算法类型。
我在这里通过不放入实际代码来逃避 - 但我会冒险一些一般性观察：
- 由于所有飞船的大小至少为 2 个单元格，因此您可以使用我在 Space Quest V 中的游戏实现中看到的优化 - 它仅在“寻找”目标时向菱形图案中的替代单元格开火。这消除了一半的方块，同时仍然保证你最终会找到所有的船只。
- 在许多游戏中，寻找目标时的随机射击模式在统计上会产生最佳结果。
![概率密度][1]输入图像描述她
![在此输入图像描述][2]
我尝试比较随机射击与愚蠢狩猎/目标的结果，最后进行复杂的搜索。
最好的解决方案似乎是创建一个概率密度函数，用于计算剩余船只使用任何单个方格的可能性，并瞄准具有最高值的方格。
你可以在这里看到我的结果 在此输入链接描述
“战舰”是所谓的经典计算机科学 NP 完全问题。
http://en.wikipedia.org/wiki/List_of_NP-complete_problems
（寻找战舰 - 它就在那里，在游戏和谜题下面）
不隶属于 StackOverflow
