战舰!
早在2003年(当时我17岁)，我参加了一场《战舰》AI编码比赛。尽管我输了那场比赛，但我从中获得了很多乐趣，也学到了很多东西。
现在，我想恢复这个比赛，在搜索最好的战舰AI。
下面是这个框架，现在托管在Bitbucket上。
获胜者将获得+450声望奖励!比赛将于2009年11月17日开始。17号零时之前的投稿和编辑将不被接受。(中央标准时间)
尽早提交你的作品，这样你就不会错过机会!
为了保持这个目标，请遵循比赛的精神。
游戏规则:
游戏在10x10的网格上进行。
每个参赛者将5艘船(长度为2、3、3、4、5)中的每一艘放在他们的网格上。
没有船只可以重叠，但它们可以相邻。
然后选手们轮流向对手射击。
游戏的一个变体允许每次齐射多次，每艘幸存的船一次。
如果击球沉、命中或未命中，对手将通知选手。
当任何一名玩家的所有船只都沉没时，游戏就结束了。
比赛规则:
The spirit of the competition is to find the best Battleship algorithm.
Anything that is deemed against the spirit of the competition will be grounds for disqualification.
Interfering with an opponent is against the spirit of the competition.
Multithreading may be used under the following restrictions:
No more than one thread may be running while it is not your turn. (Though, any number of threads may be in a "Suspended" state).
No thread may run at a priority other than "Normal".
Given the above two restrictions, you will be guaranteed at least 3 dedicated CPU cores during your turn.
A limit of 1 second of CPU time per game is allotted to each competitor on the primary thread.
Running out of time results in losing the current game.
Any unhandled exception will result in losing the current game.
Network access and disk access is allowed, but you may find the time restrictions fairly prohibitive. However, a few set-up and tear-down methods have been added to alleviate the time strain.
Code should be posted on stack overflow as an answer, or, if too large, linked.
Max total size (un-compressed) of an entry is 1 MB.
Officially, .Net 2.0 / 3.5 is the only framework requirement.
Your entry must implement the IBattleshipOpponent interface.
得分:
Best 51 games out of 101 games is the winner of a match.
All competitors will play matched against each other, round-robin style.
The best half of the competitors will then play a double-elimination tournament to determine the winner. (Smallest power of two that is greater than or equal to half, actually.)
I will be using the TournamentApi framework for the tournament.
The results will be posted here.
If you submit more than one entry, only your best-scoring entry is eligible for the double-elim.
好运！玩得开心!
编辑1:
多亏弗里德，他在飞船上发现了一个错误。是否是可用的函数。问题已经解决了。请下载框架的更新版本。
编辑2:
由于人们对将统计数据持久化到磁盘等非常感兴趣，所以我添加了一些非计时设置和删除事件，它们应该能够提供所需的功能。这是一个半突破性的变化。也就是说:修改了接口，添加了功能，但不需要body。请下载框架的更新版本。
编辑3:
错误修复1:GameWon和GameLost只在超时的情况下被调用。
错误修复2:如果引擎在每一款游戏中都暂停计时，那么竞争将永远不会结束。
请下载框架的更新版本。
编辑4:
比赛结果:
我不能参与，但如果我有时间，我将实现以下算法:
首先，当我发现被击中时，我不会立即追击剩下的船只——我会建立一个船的位置表，并在开始完全击沉它们之前确定我是否至少一次击中了所有五艘船。(注意，这是一个糟糕的策略多镜头变体-见评论)
Hit the center (see final note below - 'center' is just a convenience for description)
Hit the spot 4 to the right of the center
Hit the spot 1 down and one to the right of the center
Hit the spot four to the right of the previous hit
Continue in that pattern (should end up with diagonal lines separated by 3 spaces filling the board) This should hit all 4 and 5 length boats, and a statistically large number of 3 and 2 boats.
Start randomly hitting spots inbetween the diagonals, this will catch the 2 and 3 length boats that haven't already been noticed.
一旦我检测到5个命中，我将确定这5个命中是否在不同的船上。这是相对容易的，只要在两个命中点在同一水平或垂直线上，并且彼此之间有5个位置(可能是同一条船上的两个命中点)的位置附近多拍几次就可以了。如果他们是分开的船，那么继续击沉所有的船。如果发现它们是同一艘船，继续上面的填充模式，直到所有5艘船都被定位。
该算法是一种简单的填充算法。关键的特点是，它不会浪费时间去击沉它知道的船只，当仍然有它不知道的船只时，它不会使用低效的填充模式(即，完全随机的模式将是浪费的)。
最后指出:
一)“中心”是棋盘上的一个随机起点。这消除了该算法的主要弱点。
B)虽然描述表明从一开始就立即绘制对角线，但理想情况下，算法只是在这些对角线上的“随机”位置射击。这有助于防止竞争对手计算他们的船只被可预测的模式击中的时间。
这描述了一个“完美”的算法，因为它可以让所有船只在(9x9)/2+10次射击之内。
但是，它可以显著改善:
一旦一艘船被击中，在做“内部”对角线之前确定它的大小。你可能已经找到了2号船，在这种情况下，内部对角线可以简化以更快地找到3号船。
确定游戏的各个阶段并采取相应的行动。这种算法可能在游戏的某一点上很好，但其他算法可能会在游戏的最后产生更好的收益。此外，如果其他玩家非常接近击败你，另一个算法可能会更好-例如，一个高风险的算法可能更容易失败，但当它起作用时，它会很快起作用，你可能会击败比你更接近胜利的对手。
识别竞争对手的打法——这可能会给你一些线索，让你知道他们是如何规划船只位置的(比如，他们自己的算法很有可能最快速地识别出他们如何放置自己的船只——如果你唯一的工具是锤子，那么所有的东西看起来都像钉子)
亚当
这是一个供人们玩的对手:
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亿美元仍然太大，无法在一秒钟内进入。不过，在一些启发式的帮助下，它确实试图估计这些概率。
关于竞争引擎的一些评论:
NewGame参数:
如果IBattleshipOpponent::NewGame用于游戏前设置，并接受一个boardsize，那么它还应该接受一个船的列表及其各自的大小。在不考虑船舶配置变化的情况下，允许可变的船板尺寸是没有意义的。
船舶是密封的:
我看不出为什么船班是封闭的。除了其他基本的东西，我想船有一个名字，所以我可以输出消息(“你沉没了我的{0}”，船.Name);我还考虑了其他扩展，所以我认为Ship应该是可继承的。
时间限制:
虽然1秒的时间限制对比赛规则来说是有意义的，但它完全扰乱了调试。BattleshipCompetition应该有一个容易忽略时间冲突的设置，以帮助开发/调试。我还建议调查System.Diagnostics。Process::UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime用于更准确地查看正在使用的时间。
沉没的船只:
当你击沉对手的船时，当前的API会通知你:
ShotHit(Point shot, bool sunk);
但不是你击沉了哪艘船!我认为这是人类战列舰规则的一部分，你必须宣布“你击沉了我的战列舰!”(或驱逐舰，或潜艇等)。
当AI试图清除相互碰撞的船只时，这一点尤其重要。我想要求API更改为:
ShotHit(Point shot, Ship ship);
如果ship为非空，则意味着该射击是一个击沉射击，并且您知道您击沉了哪艘船以及它的长度。如果射击是一个非下沉射击，那么船是空的，你没有进一步的信息。
这是我在空闲时间能做的最好的东西，几乎不存在。有一些游戏和比赛统计数据正在进行，因为我设置了主函数循环并持续运行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时表现不如一个更不先进的早期版本。
