C# 什么是最好的战舰 AI？

What is the best Battleship AI?

提问by John Gietzen

Battleship!

战舰！

Back in 2003 (when I was 17), I competed in a Battleship AIcoding competition. Even though I lost that tournament, I had a lot of fun and learned a lot from it.

早在 2003 年（当时我 17 岁），我就参加了Battleship AI编码比赛。尽管我输掉了那场比赛，但我从中获得了很多乐趣并从中学到了很多东西。

Now, I would like to resurrect this competition, in the search of the best battleship AI.

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

Here is the framework, now hosted on Bitbucket.

这是框架，现在托管在 Bitbucket 上。

The winner will be awarded +450 reputation!The competition will be held starting on the 17th of November, 2009. No entries or edits later than zero-hour on the 17th will be accepted. (Central Standard Time) Submit your entries early, so you don't miss your opportunity!

获胜者将获得 +450 声望！比赛将于2009年11月17日开始。不接受晚于 17 日零时的任何条目或编辑。（中部标准时间）尽早提交您的参赛作品，以免错失良机！

To keep this OBJECTIVE, please follow the spirit of the competition.

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

Rules of the game:

游戏规则：

1. The game is be played on a 10x10 grid.
2. Each competitor will place each of 5 ships (of lengths 2, 3, 3, 4, 5) on their grid.
3. No ships may overlap, but they may be adjacent.
4. The competitors then take turns firing single shots at their opponent.
   • A variation on the game allows firing multiple shots per volley, one for each surviving ship.
5. The opponent will notify the competitor if the shot sinks, hits, or misses.
6. Game play ends when all of the ships of any one player are sunk.

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

Rules of the competition:

比赛规则：

1. The spirit of the competition is to find the best Battleship algorithm.
2. Anything that is deemed against the spirit of the competition will be grounds for disqualification.
3. Interfering with an opponent is against the spirit of the competition.
4. 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.
5. A limit of 1 second of CPU time per game is allotted to each competitor on the primary thread.
6. Running out of time results in losing the current game.
7. Any unhandled exception will result in losing the current game.
8. 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.
9. Code should be posted on stack overflow as an answer, or, if too large, linked.
10. Max total size (un-compressed) of an entry is 1 MB.
11. Officially, .Net 2.0 / 3.5 is the only framework requirement.
12. Your entry must implement the IBattleshipOpponent interface.

1. 比赛的精神是寻找最好的战舰算法。
2. 任何违反比赛精神的行为都将被取消资格。
3. 干扰对手是违反比赛精神的。
4. 多线程可以在以下限制下使用：
   • 轮到您时，最多只能有一个线程在运行。（尽管，任何数量的线程都可能处于“暂停”状态）。
   • 任何线程都不能以“正常”以外的优先级运行。
   • 鉴于上述两个限制，您将在轮到您时保证至少有 3 个专用 CPU 内核。
5. 每场比赛的 CPU 时间限制为 1 秒，分配给主线程上的每个参赛者。
6. 用完时间会导致输掉当前的游戏。
7. 任何未处理的异常都将导致输掉当前游戏。
8. 允许网络访问和磁盘访问，但您可能会发现时间限制相当令人望而却步。但是，添加了一些设置和拆卸方法以减轻时间压力。
9. 代码应该作为答案发布在堆栈溢出上，或者如果太大，则链接。
10. 条目的最大总大小（未压缩）为 1 MB。
11. 正式地，.Net 2.0 / 3.5 是唯一的框架要求。
12. 您的条目必须实现 IBattleshipOpponent 接口。

Scoring:

评分：

1. Best 51 games out of 101 games is the winner of a match.
2. All competitors will play matched against each other, round-robin style.
3. 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.)
4. I will be using the TournamentApiframework for the tournament.
5. The results will be posted here.
6. If you submit more than one entry, only your best-scoring entry is eligible for the double-elim.

1. 101 场比赛中最好的 51 场是比赛的获胜者。
2. 所有参赛者将以循环赛的方式相互对抗。
3. 然后，最好的一半参赛者将进行双淘汰赛，以确定获胜者。（实际上，大于或等于一半的 2 的最小幂。）
4. 我将在锦标赛中使用TournamentApi框架。
5. 结果将在此处发布。
6. 如果您提交了多个参赛作品，则只有得分最高的参赛作品才有资格进入双赛。

Good luck! Have fun!

祝你好运！玩得开心！

---

---

EDIT 1:
Thanks to Freed, who has found an error in the Ship.IsValidfunction. It has been fixed. Please download the updated version of the framework.

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

EDIT 2:
Since there has been significant interest in persisting stats to disk and such, I have added a few non-timed set-up and tear-down events that should provide the required functionality. This is a semi-breaking change. That is to say: the interface has been modified to add functions, but no body is required for them. Please download the updated version of the framework.

编辑 2：
由于人们对将统计信息持久化到磁盘等方面有着浓厚的兴趣，因此我添加了一些应提供所需功能的非定时设置和拆卸事件。这是一个半破坏性的变化。也就是说：修改了接口，增加了功能，但是不需要body。请下载框架的更新版本。

EDIT 3:
Bug Fix 1: GameWonand GameLostwere only getting called in the case of a time out.
Bug Fix 2: If an engine was timing out every game, the competition would never end.
Please download the updated version of the framework.

编辑 3：
错误修复 1：GameWon并且GameLost只有在超时的情况下才会被调用。
错误修复 2：如果引擎在每场比赛中都超时，那么比赛将永远不会结束。
请下载框架的更新版本。

EDIT 4:
Tournament Results:

编辑 4：
锦标赛结果：

采纳答案by Keith Randall

I second the motion to do a lot more games per match. Doing 50 games is just flipping a coin. I needed to do 1000 games to get any reasonable distinction between test algorithms.

我支持每场比赛做更多比赛的动议。玩 50 场比赛只是抛硬币。我需要做 1000 场比赛才能在测试算法之间做出合理的区分。

Download Dreadnought 1.2.

下载无畏 1.2。

Strategies:

策略：

• keep track of all possible positions for ships that have >0 hits. The list never gets bigger than ~30K so it can be kept exactly, unlike the list of all possible positions for all ships (which is very large).

• The GetShot algorithm has two parts, one which generates random shots and the other which tries to finish sinking an already hit ship. We do random shots if there is a possible position (from the list above) in which all hit ships are sunk. Otherwise, we try to finish sinking a ship by picking a location to shoot at which eliminates the most possible positions (weighted).

• For random shots, compute best location to shoot based on the likelihood of one of the unsunk ships overlapping the location.

• adaptive algorithm which places ships in locations where the opponent is statistically less likely to shoot.

• adaptive algorithm which prefers to shoot at locations where the opponent is statistically more likely to place his ships.

• place ships mostly not touching each other.

• 跟踪命中 >0 的船舶的所有可能位置。该列表永远不会超过~30K，因此可以准确地保留它，这与所有船舶的所有可能位置的列表（非常大）不同。

• GetShot 算法有两部分，一部分生成随机射击，另一部分尝试完成击沉已击中的船只。如果有一个可能的位置（来自上面的列表）所有被击中的船只都沉没，我们会进行随机射击。否则，我们会尝试通过选择一个位置来完成沉船，以消除最可能的位置（加权）。

• 对于随机射击，根据其中一艘未沉没的船只与该位置重叠的可能性计算最佳射击位置。

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

• 自适应算法更喜欢在对手在统计上更有可能放置他的船只的位置射击。

• 放置船只大多不相互接触。

回答by John Gietzen

Here is my entry! (The most naive solution possible)

这是我的条目！（最简单的解决方案）

"Random 1.1"

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

回答by Shachar

You wrote:

你写了：

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

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

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

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

Also - to simplify, I recommend that you:

另外 - 为简化起见，我建议您：

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

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

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

PS - 潜伏在这里的 CS 博士后的一个问题：这个游戏是不是可以解决的（即是否有一个单一的最佳策略？）。是的，棋盘大小和步数使 minimax 等人成为强制性的，但我仍然想知道......它的复杂性远非围棋和国际象棋。

回答by ziggystar

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

这不是极小极大。实际上在放置船只之后，不能每个玩家都自己玩，导致他需要数个回合才能沉没对手的船只吗？轮数少者获胜。

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

我认为除了击沉被击中的船只并尽量减少射击次数以覆盖船只可能隐藏的剩余可能位置之外，没有任何好的通用策略。

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

当然，对于任何不是随机的事情，可能会有反策略。但我不认为有适合所有可能的玩家的策略。

回答by Triston Attridge

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

我预测，设法对对手随机种子和跟注模式进行逆向工程的人将获胜。

Not sure how likely that is though.

不确定这有多大可能。

回答by Jherico

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

实际上，我认为这个谜题最大的问题在于它本质上是两个动作。一个动作是放置你的船只，另一个是找到敌方船只（无论第二部分可能如何分段，除了试图用随机因素击败时钟之外，它只是“运行你的算法”）。没有任何机制可以尝试确定然后反击敌人的策略，这使得基于连续几轮“石头剪刀布”的类似比赛变得非常有趣。

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

此外，我认为如果您将游戏指定为网络协议，然后提供框架以在 C# 中实现该协议，而不是规定所有解决方案都应该是 C#，那会更酷，但这只是我的意见。

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

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

回答by CheeseConQueso

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

我总是喜欢从中间开始，然后从那个点开始旋转，在任何其他点之间留下不超过 1 个空白空间来解释那个该死的潜艇……镜头之间的空间取决于沉没的船只。如果 B-ship 是最后一个，镜头之间只需要留出 4 个空格，以尽量减少浪费的镜头

回答by Tom Duckering

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

萨里大学的 James Heather 博士代表英国计算机协会举办了一场类似的比赛。

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

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

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

非常有趣 - 查看更多：http: //www.bcsstudentcontest.com/

Might give you some more ideas.

可能会给你更多的想法。

回答by Glenn

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

据推测，也可以在游戏中运行一系列这些变化。

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

添加诸如 3d 飞机之类的东西或能够移动一艘船而不是转弯射击可能会改变游戏。

回答by inked

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

“战舰”是所谓的经典计算机科学 NP 完全问题。

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

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

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

（寻找战舰 - 它就在那里，在游戏和谜题下）

回答by abelenky

Some comments about the Competition Engine:

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

NewGame parameters:

新游戏参数：

If IBattleshipOpponent::NewGame is intended for pre-game setup and takes a boardsize, it should also take a list of ships and their respective sizes. It makes no sense to allow for variable board-size without allowing for variable ship configurations.

如果 IBattleshipOpponent::NewGame 用于赛前设置并采用棋盘尺寸，则还应采用船舶及其各自尺寸的列表。在不考虑可变船舶配置的情况下允许可变板尺寸是没有意义的。

Ships are sealed:

船舶被密封：

I don't see any reason why class Ship is sealed. Among other basic things, I would like Ships to have a Name, so I can output messages like ("You sunk my {0}", ship.Name);. I have other extensions in mind too, so I think Ship should be inheritable.

我看不出有任何理由将 Ship 班级密封。除其他基本内容外，我希望 Ships 有一个名称，以便我可以输出诸如("You sunk my {0}", ship.Name); 之类的消息。. 我也有其他扩展，所以我认为 Ship 应该是可继承的。

Time Limits:

时间限制：

While the time limit of 1 second makes sense for a tournament rule, it totally messes with debugging. BattleshipCompetition should have an easy setting to ignore time-violations to aid with development/debugging. I would also suggest investigating System.Diagnostics.Process::UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime for a more accurate view of how much time is being used.

虽然 1 秒的时间限制对于锦标赛规则来说是有意义的，但它完全与调试混乱。BattleshipCompetition 应该有一个简单的设置来忽略时间违规以帮助开发/调试。我还建议调查 System.Diagnostics.Process::UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime 以更准确地了解使用了多少时间。

Sunk Ships:

沉船：

The current API informs you when you've sunk an oppenent's ship:

当前 API 会在您击沉对手的船只时通知您：

ShotHit(Point shot, bool sunk);

but not whichship you sunk! I consider it part of the human-Battleship rules that you are required to declare "You sunk my Battleship!" (or destroyer, or sub, etc).

但不是你击沉了哪艘船！我认为这是人类战舰规则的一部分，你必须声明“你击沉了我的战舰！” （或驱逐舰，或潜艇等）。

This is especially critical when an AI is trying to flush out ships that butt-up against each other. I'd like to request an API change to:

当 AI 试图冲出相互对接的船只时，这一点尤其重要。我想请求将 API 更改为：

ShotHit(Point shot, Ship ship);

If shipis non-null, it implies that the shot was a sinking-shot, and you know which ship you sunk, and how long it was. If the shot was a non-sinking shot, then ship is null, and you have no further information.

如果ship为非空值，则表示该射击是沉没射击，并且您知道您击沉了哪艘船，以及沉没了多长时间。如果该射击是非下沉射击，则 ship 为空，并且您没有更多信息。