这是我的入口!(最天真的解决方案)

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

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

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

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

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

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

我赞成每场比赛多打几场比赛。制作50款游戏只是抛硬币。我需要做1000个游戏，才能在测试算法之间找到合理的区别。

下载无畏1.2。

策略:

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.

我预测，能够逆向设计对手随机种子和呼叫模式的人将获胜。

但不确定这种可能性有多大。

这是一个供人们玩的对手:

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

与其使用固定的几何启发策略，我认为尝试估计任何特定的未探索空间拥有一艘船的潜在概率会很有趣。

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

扩大可能的战列舰国家http://natekohl.net/media/battleship-tree.png

在考虑了所有与你所了解的世界相冲突的树叶后(游戏邦注:例如，船只不能重叠，所有被击中的方块都必须是船只等)，你可以计算船只在每个未探索位置出现的频率，从而估算船只位于那里的可能性。

这可以可视化为热图，其中热点更有可能包含船只:

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

我喜欢这个战列舰比赛的一个原因是上面的树几乎小到可以强制使用这种算法。如果这5艘船每艘都有150个可能的位置，那就是1505 = 750亿种可能性。这个数字只会越来越小，特别是如果你可以排除整艘船。

我上面链接的对手并没有探索整棵树;750亿美元仍然太大，无法在一秒钟内进入。不过，在一些启发式的帮助下，它确实试图估计这些概率。