你写的:

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

请定义一下“违反比赛精神”和“干扰对手”。

此外，为了简化，我建议你:

禁止在对手的CPU插槽期间使用CPU。 不允许线程并行，而是在单个线程上提供更多的CPU秒。这将简化AI编程，并且不会伤害任何CPU/内存受限的人。

PS -这里有一个CS博士后的问题:这个游戏是可解决的吗(也就是说，是否有一个唯一的最佳策略?)是的，棋盘的大小和步骤数使得minimax等是强制性的，但我仍然想知道……它远没有围棋和国际象棋复杂。

我不能参与，但如果我有时间，我将实现以下算法:

首先，当我发现被击中时，我不会立即追击剩下的船只——我会建立一个船的位置表，并在开始完全击沉它们之前确定我是否至少一次击中了所有五艘船。(注意，这是一个糟糕的策略多镜头变体-见评论)

Hit the center (see final note below - 'center' is just a convenience for description) Hit the spot 4 to the right of the center Hit the spot 1 down and one to the right of the center Hit the spot four to the right of the previous hit Continue in that pattern (should end up with diagonal lines separated by 3 spaces filling the board) This should hit all 4 and 5 length boats, and a statistically large number of 3 and 2 boats. Start randomly hitting spots inbetween the diagonals, this will catch the 2 and 3 length boats that haven't already been noticed.

一旦我检测到5个命中，我将确定这5个命中是否在不同的船上。这是相对容易的，只要在两个命中点在同一水平或垂直线上，并且彼此之间有5个位置(可能是同一条船上的两个命中点)的位置附近多拍几次就可以了。如果他们是分开的船，那么继续击沉所有的船。如果发现它们是同一艘船，继续上面的填充模式，直到所有5艘船都被定位。

该算法是一种简单的填充算法。关键的特点是，它不会浪费时间去击沉它知道的船只，当仍然有它不知道的船只时，它不会使用低效的填充模式(即，完全随机的模式将是浪费的)。

最后指出:

一)“中心”是棋盘上的一个随机起点。这消除了该算法的主要弱点。 B)虽然描述表明从一开始就立即绘制对角线，但理想情况下，算法只是在这些对角线上的“随机”位置射击。这有助于防止竞争对手计算他们的船只被可预测的模式击中的时间。

这描述了一个“完美”的算法，因为它可以让所有船只在(9x9)/2+10次射击之内。

但是，它可以显著改善:

一旦一艘船被击中，在做“内部”对角线之前确定它的大小。你可能已经找到了2号船，在这种情况下，内部对角线可以简化以更快地找到3号船。

确定游戏的各个阶段并采取相应的行动。这种算法可能在游戏的某一点上很好，但其他算法可能会在游戏的最后产生更好的收益。此外，如果其他玩家非常接近击败你，另一个算法可能会更好-例如，一个高风险的算法可能更容易失败，但当它起作用时，它会很快起作用，你可能会击败比你更接近胜利的对手。

识别竞争对手的打法——这可能会给你一些线索，让你知道他们是如何规划船只位置的(比如，他们自己的算法很有可能最快速地识别出他们如何放置自己的船只——如果你唯一的工具是锤子，那么所有的东西看起来都像钉子)

亚当

一秒钟的游戏时间是机器特定的。与比赛机器相比，我的机器上每秒的CPU操作将是不同的。如果我优化Battle Ship算法，让它在1秒内利用最多CPU时间，那么它就会运行在可能较慢的比赛机器上，它总是会输。

我不确定如何绕过框架的这一限制，但它应该得到解决。

...

一个想法是做在这个比赛http://www.bcsstudentcontest.com/

每个回合有最大时间，而不是最大总游戏时间。这样我可以限制算法以适应已知的转弯时间。一款游戏可能会持续50到600多个回合，如果我的算法管理它的总游戏时间，它可能没有足够的时间来发挥最佳效果，或者它可能会花费太多时间而失败。在战舰算法中管理游戏总时间是非常困难的。

我建议修改规则，限制回合时间，而不是总游戏时间。

Edit

如果我写了一个算法，枚举所有可能的镜头，然后对它们进行排名，然后选择排名最高的镜头。生成所有可能的镜头需要很长时间，所以我会让算法运行一段时间，然后停止它。

如果有基于回合的限制，我可以让算法运行0.9秒并返回排名最高的镜头，并且在回合时间限制内很好。

如果我的游戏总时间被限制在1秒，那么就很难确定算法在每个回合中应该运行多长时间。我想要最大化我的CPU时间。如果游戏持续500轮，我可以将每个回合限制在0.002秒，但如果游戏持续100轮，我可以给每个回合0.01秒的CPU时间。

对于一个算法来说，使用半穷举搜索镜头空间来找到当前限制的最佳镜头是不切实际的。

1秒的游戏总时间限制了可以有效用于游戏竞争的算法类型。

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

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亿美元仍然太大，无法在一秒钟内进入。不过，在一些启发式的帮助下，它确实试图估计这些概率。

没有那么复杂，但这是我想到的。它有99.9%的几率击败随机对手。如果有人有其他类似的小挑战，我会感兴趣的，这很有趣。

namespace Battleship
{
    using System;
    using System.Collections.ObjectModel;
    using System.Drawing;
    using System.Collections.Generic;
    using System.Linq;
    public class AgentSmith : IBattleshipOpponent
    {        
        public string Name { get { return "Agent Smith"; } }
        public Version Version { get { return this.version; } }
        private Random rand = new Random();
        private Version version = new Version(2, 1);
        private Size gameSize;
        private enum Direction { Up, Down, Left, Right }
        private int MissCount;
        private Point?[] EndPoints = new Point?[2];
        private LinkedList<Point> HitShots = new LinkedList<Point>();
        private LinkedList<Point> Shots = new LinkedList<Point>();
        private List<Point> PatternShots = new List<Point>();
        private Direction ShotDirection = Direction.Up;
        private void NullOutTarget()
        {
            EndPoints = new Point?[2];
            MissCount = 0;
        }
        private void SetupPattern()
        {
            for (int y = 0; y < gameSize.Height; y++)
                for (int x = 0; x < gameSize.Width; x++)
                    if ((x + y) % 2 == 0) PatternShots.Add(new Point(x, y));
        }
        private bool InvalidShot(Point p)
        {
            bool InvalidShot = (Shots.Where(s => s.X == p.X && s.Y == p.Y).Any());
            if (p.X < 0 | p.Y<0) InvalidShot = true;
            if (p.X >= gameSize.Width | p.Y >= gameSize.Height) InvalidShot = true;
            return InvalidShot;
        }
        private Point FireDirectedShot(Direction? direction, Point p)
        {
            ShotDirection = (Direction)direction;
            switch (ShotDirection)
            {
                case Direction.Up: p.Y--; break;
                case Direction.Down: p.Y++; break;
                case Direction.Left: p.X--; break;
                case Direction.Right: p.X++; break;
            }
            return p;
        }
        private Point FireAroundPoint(Point p)
        {
            if (!InvalidShot(FireDirectedShot(ShotDirection,p)))
                return FireDirectedShot(ShotDirection, p);
            Point testShot = FireDirectedShot(Direction.Left, p);
            if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Right, p); }
            if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Up, p); }
            if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Down, p); }
            return testShot;
        }
        private Point FireRandomShot()
        {
            Point p;
            do
            {
                if (PatternShots.Count > 0)
                    PatternShots.Remove(p = PatternShots[rand.Next(PatternShots.Count)]);
                else do
                    {
                        p = FireAroundPoint(HitShots.First());
                        if (InvalidShot(p)) HitShots.RemoveFirst();
                    } while (InvalidShot(p) & HitShots.Count > 0);
            }
            while (InvalidShot(p));
            return p;
        }
        private Point FireTargettedShot()
        {
            Point p;
            do
            {
                p = FireAroundPoint(new Point(EndPoints[1].Value.X, EndPoints[1].Value.Y));
                if (InvalidShot(p) & EndPoints[1] != EndPoints[0])
                    EndPoints[1] = EndPoints[0];
                else if (InvalidShot(p)) NullOutTarget();
            } while (InvalidShot(p) & EndPoints[1] != null);
            if (InvalidShot(p)) p = FireRandomShot();
            return p;
        }
        private void ResetVars()
        {
            Shots.Clear();
            HitShots.Clear();
            PatternShots.Clear();
            MissCount = 0;
        }
        public void NewGame(Size size, TimeSpan timeSpan)
        {
            gameSize = size;
            ResetVars();
            SetupPattern();
        }
        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()
        {
            if (EndPoints[1] != null) Shots.AddLast(FireTargettedShot());
            else Shots.AddLast(FireRandomShot());
            return Shots.Last();
        }
        public void ShotHit(Point shot, bool sunk)
        {            
            HitShots.AddLast(shot);
            MissCount = 0;
            EndPoints[1] = shot;
            if (EndPoints[0] == null) EndPoints[0] = shot;
            if (sunk) NullOutTarget();
        }
        public void ShotMiss(Point shot)
        {
            if (++MissCount == 6) NullOutTarget();
        }
        public void GameWon() { }
        public void GameLost() { }
        public void NewMatch(string opponent) { }
        public void OpponentShot(Point shot) { }
        public void MatchOver() { }
    }
}

稍微压缩，以占用最小的空间在这里，仍然是可读的。

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

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