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

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

这不是一个完全成熟的答案，但用常见的代码来混淆真实的答案似乎没有什么意义。 因此，我将本着开放源码的精神介绍一些扩展/通用类。 如果你使用这些，那么请更改名称空间或试图将所有内容编译到一个dll中是行不通的。

BoardView可以让您轻松地使用带注释的板。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.IO;

namespace Battleship.ShuggyCoUk
{
    public enum Compass
    {
        North,East,South,West
    }

    class Cell<T>
    {
        private readonly BoardView<T> view;
        public readonly int X;
        public readonly int Y;
        public T Data;
        public double Bias { get; set; }

        public Cell(BoardView<T> view, int x, int y) 
        { 
            this.view = view; this.X = x; this.Y = y; this.Bias = 1.0;  
        }

        public Point Location
        {
            get { return new Point(X, Y); }
        }

        public IEnumerable<U> FoldAll<U>(U acc, Func<Cell<T>, U, U> trip)
        {
            return new[] { Compass.North, Compass.East, Compass.South, Compass.West }
                .Select(x => FoldLine(x, acc, trip));
        }

        public U FoldLine<U>(Compass direction, U acc, Func<Cell<T>, U, U> trip)
        {
            var cell = this;
            while (true)
            {
                switch (direction)
                {
                    case Compass.North:
                        cell = cell.North; break;
                    case Compass.East:
                        cell = cell.East; break;
                    case Compass.South:
                        cell = cell.South; break;
                    case Compass.West:
                        cell = cell.West; break;
                }
                if (cell == null)
                    return acc;
                acc = trip(cell, acc);
            }
        }

        public Cell<T> North
        {
            get { return view.SafeLookup(X, Y - 1); }
        }

        public Cell<T> South
        {
            get { return view.SafeLookup(X, Y + 1); }
        }

        public Cell<T> East
        {
            get { return view.SafeLookup(X+1, Y); }
        }

        public Cell<T> West
        {
            get { return view.SafeLookup(X-1, Y); }
        }

        public IEnumerable<Cell<T>> Neighbours()
        {
            if (North != null)
                yield return North;
            if (South != null)
                yield return South;
            if (East != null)
                yield return East;
            if (West != null)
                yield return West;
        }
    }

    class BoardView<T>  : IEnumerable<Cell<T>>
    {
        public readonly Size Size;
        private readonly int Columns;
        private readonly int Rows;

        private Cell<T>[] history;

        public BoardView(Size size)
        {
            this.Size = size;
            Columns = size.Width;
            Rows = size.Height;
            this.history = new Cell<T>[Columns * Rows];
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Rows; x++)
                    history[x + y * Columns] = new Cell<T>(this, x, y);
            }
        }

        public T this[int x, int y]
        {
            get { return history[x + y * Columns].Data; }
            set { history[x + y * Columns].Data = value; }
        }

        public T this[Point p]
        {
            get { return history[SafeCalc(p.X, p.Y, true)].Data; }
            set { this.history[SafeCalc(p.X, p.Y, true)].Data = value; }
        }

        private int SafeCalc(int x, int y, bool throwIfIllegal)
        {
            if (x < 0 || y < 0 || x >= Columns || y >= Rows)
            {    if (throwIfIllegal)
                    throw new ArgumentOutOfRangeException("["+x+","+y+"]");
                 else
                    return -1;
            }
            return x + y * Columns;
        }

        public void Set(T data)
        {
            foreach (var cell in this.history)
                cell.Data = data;
        }

        public Cell<T> SafeLookup(int x, int y)
        {
            int index = SafeCalc(x, y, false);
            if (index < 0)
                return null;
            return history[index];
        }

        #region IEnumerable<Cell<T>> Members

        public IEnumerator<Cell<T>> GetEnumerator()
        {
            foreach (var cell in this.history)
                yield return cell;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public BoardView<U> Transform<U>(Func<T, U> transform)
        {
            var result = new BoardView<U>(new Size(Columns, Rows));
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Columns; x++)
                {
                    result[x,y] = transform(this[x, y]);
                }
            }
            return result;
        }

        public void WriteAsGrid(TextWriter w)
        {
            WriteAsGrid(w, "{0}");
        }

        public void WriteAsGrid(TextWriter w, string format)
        {
            WriteAsGrid(w, x => string.Format(format, x.Data));
        }

        public void WriteAsGrid(TextWriter w, Func<Cell<T>,string> perCell)
        {
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Columns; x++)
                {
                    if (x != 0)
                        w.Write(",");
                    w.Write(perCell(this.SafeLookup(x, y)));
                }
                w.WriteLine();
            }
        }

        #endregion
    }
}

有些扩展，有些复制了主框架中的功能，但应该由你自己完成。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Collections.ObjectModel;

namespace Battleship.ShuggyCoUk
{
    public static class Extensions
    {        
        public static bool IsIn(this Point p, Size size)
        {
            return p.X >= 0 && p.Y >= 0 && p.X < size.Width && p.Y < size.Height;
        }

        public static bool IsLegal(this Ship ship,
            IEnumerable<Ship> ships, 
            Size board,
            Point location, 
            ShipOrientation direction)
        {
            var temp = new Ship(ship.Length);
            temp.Place(location, direction);
            if (!temp.GetAllLocations().All(p => p.IsIn(board)))
                return false;
            return ships.Where(s => s.IsPlaced).All(s => !s.ConflictsWith(temp));
        }

        public static bool IsTouching(this Point a, Point b)
        {
            return (a.X == b.X - 1 || a.X == b.X + 1) &&
                (a.Y == b.Y - 1 || a.Y == b.Y + 1);
        }

        public static bool IsTouching(this Ship ship,
            IEnumerable<Ship> ships,
            Point location,
            ShipOrientation direction)
        {
            var temp = new Ship(ship.Length);
            temp.Place(location, direction);
            var occupied = new HashSet<Point>(ships
                .Where(s => s.IsPlaced)
                .SelectMany(s => s.GetAllLocations()));
            if (temp.GetAllLocations().Any(p => occupied.Any(b => b.IsTouching(p))))
                return true;
            return false;
        }

        public static ReadOnlyCollection<Ship> MakeShips(params int[] lengths)
        {
            return new System.Collections.ObjectModel.ReadOnlyCollection<Ship>(
                lengths.Select(l => new Ship(l)).ToList());       
        }

        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Rand rand)
        {
            T[] elements = source.ToArray();
            // Note i > 0 to avoid final pointless iteration
            for (int i = elements.Length - 1; i > 0; i--)
            {
                // Swap element "i" with a random earlier element it (or itself)
                int swapIndex = rand.Next(i + 1);
                T tmp = elements[i];
                elements[i] = elements[swapIndex];
                elements[swapIndex] = tmp;
            }
            // Lazily yield (avoiding aliasing issues etc)
            foreach (T element in elements)
            {
                yield return element;
            }
        }

        public static T RandomOrDefault<T>(this IEnumerable<T> things, Rand rand)
        {
            int count = things.Count();
            if (count == 0)
                return default(T);
            return things.ElementAt(rand.Next(count));
        }
    }
}

我经常用的东西。

enum OpponentsBoardState
{
    Unknown = 0,
    Miss,
    MustBeEmpty,        
    Hit,
}

随机化。 安全但可测试，对测试有用。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace Battleship.ShuggyCoUk
{
    public class Rand
    {
        Random r;

        public Rand()
        {
            var rand = System.Security.Cryptography.RandomNumberGenerator.Create();
            byte[] b = new byte[4];
            rand.GetBytes(b);
            r = new Random(BitConverter.ToInt32(b, 0));
        }

        public int Next(int maxValue)
        {
            return r.Next(maxValue);
        }

        public double NextDouble(double maxValue)
        {
            return r.NextDouble() * maxValue;
        }

        public T Pick<T>(IEnumerable<T> things)
        {
            return things.ElementAt(Next(things.Count()));
        }

        public T PickBias<T>(Func<T, double> bias, IEnumerable<T> things)
        {
            double d = NextDouble(things.Sum(x => bias(x)));
            foreach (var x in things)
            {
                if (d < bias(x))
                    return x;
                d -= bias(x);                
            }
            throw new InvalidOperationException("fell off the end!");
        }
    }
}

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

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

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号船。

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

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

亚当

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

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

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

我现在没有时间写一个完整的算法，但我有一个想法:如果你的对手随机放置船只，放置概率不会是一个以(5.5,5.5)为中心的简单分布吗?例如，战列舰(5个单位长)在x维度的放置可能性如下:

x    1 2 3 4 5  6  7 8 9 10
P(x) 2 4 6 8 10 10 8 6 4 2

同样的计算也适用于y。其他船只的分布不会那么陡峭，但你最好的猜测仍然是中心。在此之后，数学方法将慢慢地向中心外辐射对角线(可能是平均船的长度，17/5)。例:

...........
....x.x....
.....x.....
....x.x....
...........

显然，这个想法需要添加一些随机性，但我认为从纯粹的数学角度来看，这是可行的。

你写的:

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

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

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

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

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