什么是最好的战舰AI？ [英] What is the best Battleship AI?

问题描述

战舰！

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

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

现在，我想复活这种竞争，在搜索最好的战舰AI的。

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

下面是框架： Battleship.zip

Here is the framework: Battleship.zip

获胜者将被授予名誉+ 450！比赛将开始于2009年11月，在 17日举行即可。 17日无条目或编辑晚于零时将被接受。 （中央标准时间）
提交你的作品早，所以你千万不要错过你的机会！

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!

的为了保持的目标后，请按照竞争的精神。的

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

游戏规则：

1. 本场比赛是被一个10×10格播放。


2. 每个参赛者将以每个5艘在他们的网格。
（长度2，3，3，4，5）的

3. 无船可重叠，但它们可能是相邻的。


4. 的竞争对手，然后轮流向对手射击单杆。
   
   
   
   • 在游戏中的变化让每个射击齐射，一是多个镜头每个幸存的船。
   
   

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.

比赛规则：

1. 本次比赛的精神是找到最好的战舰算法。


2. ，针对竞争的精神，认为会回避任何理由。


3. 与对手干扰，这是对竞争的精神。


4. 多线程，可以根据以下限制使用：
   
   
   
   • 不超过一个线程可以运行，而它不是轮到你了。 （虽然，任意数量的线程可能会处于悬浮状态）。
   
   
   • 没有线程可能以比正常以外的优先级运行。
   
   
   • 鉴于上述两个限制，你会被你的回合中保证至少3个专用的CPU核心。
   
   

评分：

1. 最好的51场比赛出的101场比赛是比赛的胜者。


2. 所有的竞争对手会互相反对，循环式打法相匹配。


3. 竞争对手的最佳一半将再打一个双败淘汰制决出胜负。 （两大于或等于一半，实际上最小功率。）


4. 我将使用 TournamentApi 为巡回赛的框架。


5. 的结果将被张贴在这里。


6. 如果您提交多个条目，只有你最好的得分项​​是符合双小琳。

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 TournamentApi framework 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：

由于弗里德，谁发现了 Ship.IsValid 功能。它已得到修复。请下载该框架的更新版本。

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

编辑2：

由于出现了显著的兴趣持续统计数据到磁盘和这样的，我已经增加了一些非定时设置和拆除事件应提供所需的功能。这是一个半破更改。这就是说：接口已被修改为增加功能，但需要对他们没有身体。请下载该框架的更新版本。

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.

修改3：

错误修正1： GameWon 和 GameLost 只获取调用在超时的情况下

错误修正2：如果发动机每场比赛超时，比赛永远不会结束
。
请下载该框架的更新版本。

EDIT 3:
Bug Fix 1: GameWon and GameLost were 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.

修改4：

结果！

EDIT 4:
Results!

推荐答案

我第二个做的每场比赛有更多的游戏运动。做了50场比赛仅仅是扔硬币。我需要做的1000场比赛拿到测试算法之间的任何合理的区别。

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.

无畏1.2 。

策略：

• 追踪所有可能的位置，为有> 0命中船舶。该列表永远不会超过30K〜更大，所以它可以保持准确，不象所有船舶所有可能位置的列表（这是非常大）。

• 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).

该GetShot算法有两个部分，一是生成随机拍摄，另一种
试图完成那颗已经打到船上。我们做随机的镜头，如果有可能的位置（从上面的列表），其中全部命中船舶沉没。否则，我们试图完成靠捡的地点拍摄的，它消除了最可能的位置（加权）下沉的船。

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).

对于随机的镜头，计算出最佳的位置拍摄基础上，unsunk船舶重叠的位置之一的可能性。

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.

自适应算法，prefers在地点拍摄，其中的对手是统计学上更容易把他的船。

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.

这篇关于什么是最好的战舰AI？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！