战舰!

早在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: 比赛结果:


当前回答

萨里大学的詹姆斯·希瑟博士代表英国计算机学会举办了一次类似的比赛。

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

非常有趣,更多信息请访问:http://www.bcsstudentcontest.com/

也许能给你更多的建议。

其他回答

关于竞争引擎的一些评论:

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为非空,则意味着该射击是一个击沉射击,并且您知道您击沉了哪艘船以及它的长度。如果射击是一个非下沉射击,那么船是空的,你没有进一步的信息。

实际上,我认为这个谜题最大的问题在于它本质上是两个步骤。一个步骤是放置你的船只,另一个步骤是找到敌人的船只(不管第二部分是如何分割的,除了尝试用随机因素打败时间外,它只是“运行你的算法”)。游戏中不存在决定并反击敌人策略的机制,这也是基于连续回合的“石头剪刀布”的类似竞争非常有趣的原因。

此外,我认为如果你将游戏指定为网络协议,然后提供框架以c#实现该协议,而不是规定所有解决方案都应该是c#,这将更酷,但这只是我的观点。

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

这不是极大极小。实际上,在放置船只之后,难道每个玩家都不能自己玩,导致他花了很多回合去击沉所有对手的船只吗?回合少的人赢。

我认为除了击沉被击中的船只和尽量减少射击数量以覆盖剩下的船只可能隐藏的地方之外,没有什么好的总体策略。

当然,对于任何非随机的情况,我们都有对策。但我不认为有什么策略对所有可能的对手都有效。

我在这里没有放入实际的代码,但我将冒险进行一些一般性的观察:

因为所有的飞船都至少有2个细胞大小,你可以使用我在《太空探索V》中看到的一个优化——当它“寻找”一个目标时,只向菱形图案的交替细胞开火。这将消除一半的方格,同时仍然保证你最终会找到所有船只。 在许多游戏中,寻找目标时的随机射击模式从统计上来说会产生最好的结果。

“战舰”是一个经典的计算机科学np完全问题。

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

(寻找战舰-它在那里,在游戏和谜题下)