最好的战舰人工智能是什么?

314

战舰游戏!

回到2003年(当时我17岁),我参加了一场战舰AI编程比赛。尽管我输掉了那场比赛,但我从中得到了很多乐趣和收获。

现在,我想重新启动这项竞赛,寻找最佳的战舰AI。

这里是框架,现在托管在Bitbucket上

获胜者将被授予+450声望!比赛将于2009年11月17日开始举行。不接受任何晚于17日零点提交的条目或编辑。(中央标准时间) 提早提交您的条目,以免错过机会!

为保持客观性,请遵循比赛精神。

游戏规则:

  1. 游戏在一个10x10的网格上进行。
  2. 每个竞争者将在他们的网格上放置5艘船(长度为2、3、3、4、5)。
  3. 没有船只可以重叠,但它们可以相邻。
  4. 然后,竞争者轮流向对手开火。
    • 游戏的变种允许每次发射多枚子弹,每枚子弹针对一艘存活的船只。
  5. 对手将通知竞争者子弹是否击沉、命中或未命中。
  6. 当任何一名玩家的所有船只被击沉时,游戏结束。

比赛规则:

  1. 比赛的目的是寻找最佳的战舰算法。
  2. 任何被认为违反比赛精神的行为都将成为取消资格的理由。
  3. 干扰对手是违背比赛精神的行为。
  4. 多线程可以在以下限制下使用:
    • 当轮到你时,不能有多于一个线程正在运行。(尽管,任意数量的线程可能处于"Suspended"状态)。
    • 没有线程可以以除"Normal"之外的优先级运行。
    • 在以上两个限制下,你将保证在你的回合期间至少有3个专用CPU核心。
  5. 每个竞争者在线程上分配了1秒钟的CPU时间。
  6. 时间用完会导致当前游戏失败。
  7. 任何未处理的异常都会导致当前游戏失败。
  8. 网络访问和磁盘访问是允许的,但您可能会发现时间限制相当禁止。 然而,已添加了一些设置和拆卸方法以缓解时间压力。
  9. 代码应作为答案发布在stack overflow上,或者如果太大,则链接到其他位置。
  10. 条目的最大总大小(未压缩)为1 MB。
  11. 正式来说,.Net 2.0 / 3.5是唯一的框架要求。
  12. 您的条目必须实现IBattleshipOpponent接口。

评分:

  1. 101场比赛中获胜51场的选手将成为比赛的获胜者。
  2. 所有参赛选手将以循环赛的方式相互比赛。
  3. 最好的一半选手将进行双败淘汰赛,以确定获胜者。(实际上是大于或等于一半的最小2的幂次方。)
  4. 我将使用TournamentApi框架进行比赛。
  5. 比赛结果将在这里发布。
  6. 如果您提交了多个条目,则只有得分最高的条目有资格参加双败淘汰赛。

祝你好运!玩得开心!


编辑1:
感谢Freed发现了Ship.IsValid函数中的错误。已经修复,请下载更新版本的框架。

编辑2:
由于对将统计信息持久化到磁盘等方面产生了重大兴趣,我添加了一些非定时的设置和拆卸事件,应该提供所需的功能。这是一个半破坏性更改。也就是说:接口已被修改以添加函数,但不需要为其编写主体。请下载更新版本的框架。

编辑3:
错误修复1:GameWonGameLost仅在超时情况下才会被调用。
错误修复2:如果引擎每场比赛都超时,则比赛永远不会结束。
请下载更新版本的框架。

编辑4:
锦标赛结果:


如果该条目需要大型数据库,它能否通过网络连接到它?即,该条目能否进行Web服务调用? - Remus Rusanu
条目的大小有限制吗? - Jherico
8
@Steven:此外,我咨询了 Jeff Atwood,只是为了确认这是否合适。以下是他的回答链接:http://twitter.com/codinghorror/status/5203185621 - John Gietzen
1
此外,我想补充一点,考虑到这50个游戏中不可避免的随机因素,将无法准确区分非常好的实现。我认为需要501个或更多才能得出一个合理的观点,以确定哪个更好。 - ShuggyCoUk
1
一个“和平”的对手拒绝放置船只,导致比赛陷入僵局。不确定你是否在意人们做这样的傻事。 :) - Joe
显示剩余16条评论
25个回答

1

您写道:

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

请定义“违反比赛精神”和“干扰对手”是什么?

另外,为了简化,我建议您:

  • 在对手的CPU时间段内不允许使用CPU。
  • 禁止线程并行,改为在单个线程上增加CPU秒数。这将简化AI编程,并且不会伤害那些已经受到CPU/内存限制的人。

附:给在此潜伏的计算机博士后的问题:这个游戏可解吗(即是否存在唯一的最佳策略)? 是的,棋盘大小和步数使得必须使用极小化等算法,但我仍然想知道...它远非围棋和国际象棋复杂。


当我说“干涉”时,我考虑到了反射问题。我不希望竞争对手因为操纵另一个引擎而获胜。 - John Gietzen
8
我建议间谍活动是现代战争的重要组成部分,因此反思寻找目标将是理想的——毕竟,在第二次世界大战期间就曾使用过这种方法。 - Rowland Shaw
我有一个框架,可以将引擎隔离到不同的计算机上,通过TCP/IP进行通信,使反射变得毫无意义。然而,由于我的预估条目数量,这将使竞赛需要花费过长时间。 - John Gietzen
6
那时候我不知道他们有反射功能! - Markus Nigbur

1

我预测,那个成功反向工程对手的随机种子和调用模式的人将获胜。

不过,这可能性有多大我也不确定。


对手可以选择使用CSPRNG。 - John Gietzen
好的观点,尽管我承认反向工程这样的种子超出了我的专业知识。我猜最脆弱的方面可能是火力模式选择算法,但即使如此,你也不一定会从中获得太多好处,因为一旦游戏开始,你就没有办法移动你的船只。 - Triston Attridge
当我申请研究实习时,我们编写了战舰程序并进行了比赛。通过设置随机种子,这正是我获胜的原因 X) - P Shved
1
假设有一个相对简单的船只放置算法,我想象一旦在不同的船只上得到几次命中后,可以开始利用大部分回合时间循环遍历所有可能的随机种子(可能从当前时间附近开始,向前/向后移动一步左右),并观察哪些种子生成与观察到的命中兼容的船只放置位置。 - Domenic

1

假设可以运行一系列游戏变体,这也可能成为可能。

添加3D平面或允许在一个回合内移动单个船只而不是射击可能会相当改变游戏。


2
有一种名为“齐射”的变体。在这种变体中,您可以每回合射击与您剩余的船只数量相同的炮弹数。 - John Gietzen
还有一个有趣的变化。我记得玩过一款电脑版,它也有一架飞机。它会在对方的棋盘上随机开火。 - Glenn
另一种变化:棋盘大小加上船只数量。 - russau

1

![概率密度][1]输入图像说明

![输入图像说明][2]

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

最佳解决方案似乎是为任何个体方格创建一个概率密度函数,该函数表示剩余船只使用该方格的可能性有多大,并瞄准价值最高的方格。

您可以在这里查看我的结果 输入链接说明


你能否修复你的回答,特别是你的图片和链接? - Bart

-2

4
这是一道战舰谜题(http://en.wikipedia.org/wiki/Battleship_(puzzle)),而非战舰游戏(http://en.wikipedia.org/wiki/Battleship_(game))。 - Jason Berkan
是的,正如Jason所说,这完全是一种不同的东西。 - John Gietzen
3
下次我在工作中拿到任务,我会说它是NP完全问题,然后去吃个长午餐。 :-) - Bork Blatt

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接