什么是最好的战列舰AI？

战舰！

早在2003年（当时我17岁），我参加了战舰AI编码竞赛。 尽管我输掉了比赛，但我有很多乐趣，并从中学到很多东西。

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

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

获胜者将被授予+450声望！ 比赛将于2009年11月17日举行 。 17日之后的任何输入或修改都不会超过零小时。 （中部标准时间）尽早提交参赛作品，以免错过机会！

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

游戏规则：

该游戏将以10x10格子进行。

每个参赛者将把5艘（长度为2,3,4,5）的船舶分别放在他们的电网上。

没有船可能重叠，但它们可能相邻。

然后竞争对手轮流向对手单枪毙。

游戏中的变化允许每个凌空发射多个镜头，每个幸存的船只发射一个镜头。

如果击球，击中或未命中，对手将通知参赛者。

当任何一名球员的所有船只都沉没时，游戏结束。

比赛规则：

竞争的精神是找到最好的战列舰算法。

任何违反比赛精神的行为都将成为取消比赛资格的理由。

与对手干扰违反了比赛的精神。

多线程可以在以下限制下使用：

没有超过一个线程可能正在运行，而不是轮到你。 （但是，任何数量的线程可能处于“暂停”状态）。

没有线程可以以“普通”以外的优先级运行。

鉴于上述两个限制，您在轮到您时将至少保证3个专用CPU内核。

每个游戏CPU时间的限制为1秒，分配给主线程上的每个竞争对手。

耗尽时间会导致失去当前的游戏。

任何未处理的异常都会导致当前游戏丢失。

网络访问和磁盘访问是允许的，但您可能会发现时间限制相当严格。 然而，增加了一些设置和拆卸方法来减轻时间压力。

代码应该作为答案张贴在堆栈溢出上，或者如果太大，则链接。

条目的最大总大小（未压缩）为1 MB。

正式的.Net 2.0 / 3.5是唯一的框架要求。

您的条目必须实现IBattleshipOpponent接口。

评分：

101场比赛中最好的51场比赛是比赛的胜者。

所有的竞争者都会玩互相配对的循环赛。

最好的一半竞争对手将会参加一场双淘汰赛，以确定赢家。 （实际上大于或等于一半的两个最小功率。）

我将在锦标赛中使用TournamentApi框架。

结果将张贴在这里。

如果您提交了多个条目，则只有您的得分最高的条目才符合双elim的条件。

祝你好运！ 玩的开心！

---

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

编辑2：
由于对将数据持久存储到磁盘等方面有很大兴趣，我添加了一些非定时设置和拆卸事件，以提供所需的功能。 这是一个半决定性的变化 。 也就是说：界面已被修改为添加功能，但不需要主体。 请下载该框架的更新版本。

编辑3：
错误修复1： GameWon和GameLost只在超时的情况下被调用。
错误修复2：如果一个引擎每场比赛都超时，竞争将永远不会结束。
请下载该框架的更新版本。

编辑4：
比赛结果：

---

我第二个动作是为每场比赛做更多的比赛。 做50场比赛只是在掷硬币。 我需要做1000场比赛才能区分测试算法。

下载Dreadnought 1.2。

策略：

跟踪所有可能的位置，船只有0次命中。 该列表永远不会比〜30K大，因此它可以保持完全一致，不同于所有船舶（非常大）所有可能位置的列表。

GetShot算法有两部分，一部分可以产生随机镜头，另一部分可以完成沉没的船只沉没。 如果有一个可能的位置（从上面的列表中），我们会进行随机拍摄，其中所有命中的船只都会沉没。 否则，我们尝试通过选择一个拍摄位置来完成下沉，这样可以消除最可能的位置（加权）。

对于随机拍摄，根据其中一艘不固定的船舶与该地点重叠的可能性计算拍摄的最佳位置。

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

自适应算法，它更喜欢在对手在统计上更可能放置其船只的位置进行拍摄。

将船舶大多不相互接触。

---

这是我的入口！ （可能是最天真的解决方案）

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

---

这是一个让对手反对的对手：

http://natekohl.net/files/FarnsworthOpponent.cs

我认为尝试估计任何特定未开发空间拥有船舶的潜在可能性会很有趣，而不是使用固定的几何启发战略。

要做到这一点，您需要探索符合当前世界观的所有可能的船舶配置，然后根据这些配置计算概率。 你可以把它想象为探索一棵树：

可能的战列舰状态的扩展http://natekohl.net/media/battleship-tree.png

在考虑了那棵与你所了解的世界有关的所有树叶（例如船只不能重叠，所有命中的方格必须是船只等）之后，你可以计算在每个未探索的位置上船只出现的频率以估计一艘船正坐在那里。

这可以被视为热图，热点更可能包含船只：

每个未开发位置的概率热图http://natekohl.net/media/battleship-probs.png

我喜欢这个战舰竞赛的一件事是，上面的树几乎足以蛮力这种算法。 如果这五艘船舶中的每一艘都有大约150个可能的位置，那么1505 = 750亿个可能性。 而且这个数字只会变小，特别是如果你可以消除整艘船。

我上面链接的对手不会探索整棵树; 在一秒之内，750亿美元仍然很难进入。 它确实试图估计这些概率，但是在几个启发式的帮助下。

链接地址: http://www.djcxy.com/p/6773.html

上一篇: What is the best Battleship AI?

下一篇: Why is it important to override GetHashCode when Equals method is overridden?