如果你强迫自己进行分析，那么你可能会发现随机对手的机制非常低效。它允许自己重新选择已经目标的位置，并让框架强制它重复，直到它击中它还没有触及的位置，或者每次移动的时间限制到期。

这个对手有类似的行为(有效的位置分布是相同的)，它只是自己进行完整性检查，每次调用只消耗一个随机数生成(平摊)。

这使用了我的扩展/库答案中的类，我只提供关键方法/状态。

Shuffle源自Jon Skeet的回答

class WellBehavedRandomOpponent : IBattleShipOpponent
{
    Rand rand = new Rand();
    List<Point> guesses;
    int nextGuess = 0;

    public void PlaceShips(IEnumerable<Ship> ships)
    {
        BoardView<bool> board = new BoardView<bool>(BoardSize);
        var AllOrientations = new[] {
            ShipOrientation.Horizontal,
            ShipOrientation.Vertical };

        foreach (var ship in ships)
        {
            while (!ship.IsPlaced)
            {
                var l = rand.Pick(board.Select(c => c.Location));
                var o = rand.Pick(AllOrientations);
                if (ship.IsLegal(ships, BoardSize, l, o))
                    ship.Place(l, o);
            }
        }
    }

    public void NewGame(Size size, TimeSpan timeSpan)
    {
        var board = new BoardView<bool>(size);
        this.guesses = new List<Point>(
            board.Select(x => x.Location).Shuffle(rand));
        nextGuess = 0;
    }

    public System.Drawing.Point GetShot()
    {
        return guesses[nextGuess++];
    }

    // empty methods left out 
}

事实上，这个解决方案在ubuntu 9.10 linux的monodevelop中无需修改就可以打开和运行

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

我赞成每场比赛多打几场比赛。制作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.

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

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

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

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