什么是最好的战舰AI？

Question

战舰！

早在2003年(当时我17岁)，我参加了一场AI号战舰编码比赛。尽管我输了那场比赛，但我从中得到了很多乐趣和教训。

现在，我想恢复这个竞争，在寻找最好的战舰AI。

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

获奖者将被授予+450声誉！比赛将于2009年11月17日开始举行。在十七号零时以上的参赛作品或编辑将不被接受。(中央标准时间)尽早提交你的参赛作品，这样你就不会错过机会！

为了保持的目标__，请遵循竞赛的精神。

游戏规则：

1. 这个游戏是在10x10的网格上进行的。
2. 每个竞争对手将把5艘船(长度2，3，3，4，5)中的每一艘放在他们的栅格上。
3. 任何船只都不能重叠，但它们可能相邻。
4. 然后，竞争对手轮流向对手射击。
   • 游戏中的一个变体允许每一次截击多发子弹，每艘幸存的船一枪。

​

1. 对手会通知竞争者，如果投篮下沉，击中，或错过。
2. 游戏结束时，任何一个玩家的所有船只被击沉。

竞赛规则：

1. 竞争的精神是寻找最佳的战舰算法。
2. 任何违反比赛精神的行为都将成为取消参赛资格的理由。
3. 干扰对手是违反竞争精神的。
4. 多线程可以在下列限制下使用：
   • 在不轮到您的时候，不可能有多个线程正在运行。(不过，任何数量的线程都可能处于“挂起”状态)。
   • 除“正常”外，任何线程都不能以优先级运行。
   • 鉴于上述两个限制，您将保证至少有3个专用CPU核心在您的轮。

​

1. 每个游戏的CPU时间限制为1秒，分配给主线程上的每个竞争者。
2. 时间的耗尽导致了当前游戏的失败。
3. 任何未处理的异常都将导致当前游戏的失败。
4. 网络访问和磁盘访问是允许的，但您可能会发现时间限制是相当困难的。然而，为了减轻时间压力，增加了一些设置和拆卸的方法。
5. 代码应该张贴在堆栈溢出作为一个答案，或者，如果太大，链接。
6. 一个条目的最大总大小(未压缩)是1MB.
7. 正式而言，.Net 2.0 / 3.5是唯一的框架需求。
8. 您的条目必须实现IBattleshipOpponent接口。

评分：

1. 101场比赛中最好的51场是一场比赛的胜利者。
2. 所有的竞争对手都会互相竞争，像循环赛一样.
3. 然后，最好的一半选手将进行一场双淘汰赛，以确定胜利者。(实际上是大于或等于一半的最小二次方。)
4. 我将在比赛中使用TournamentApi框架。
5. 结果将在这里公布。
6. 如果您提交了多个条目，则只有您的最佳得分项才有资格获得双重奖励。

祝好运!玩得开心!

编辑1:

感谢被释放，他在Ship.IsValid函数中发现了一个错误。已经修好了。请下载该框架的更新版本。

编辑2:

由于对将统计数据持久化到磁盘等方面有很大的兴趣，我添加了一些非定时的设置和拆卸事件，这些事件应该提供所需的功能。这是一个半破变。也就是说:接口已被修改以添加函数，但它们不需要任何主体。请下载该框架的更新版本。

编辑3:

Bug Fix 1：GameWon和GameLost只是在超时的情况下才被调用。

Bug Fix 2:如果每一场比赛都有引擎超时，竞争就永远不会结束。

请下载该框架的更新版本。

编辑4:

比赛结果：

​

​

Answer 1

我第二个动议是每场比赛做更多的比赛。玩50场游戏就是抛硬币。我需要做1000个游戏来得到测试算法之间的任何合理的区别。

下载德雷德1.2。

战略：

• 跟踪所有可能的位置，船舶有超过0的命中。该列表永远不会超过30K，因此它可以保持准确，不像所有船舶的所有可能的位置列表(这是非常大)。
• GetShot算法由两个部分组成，一个部分生成随机射击，另一个部分试图完成一艘已经命中的船的沉没。我们做随机射击，如果有一个可能的位置(从上面的名单)，所有命中的船只是沉没的。否则，我们试图通过选择一个可以射击的位置来完成沉没，从而消除最可能的位置(加权)。
• 对于随机射击，根据其中一艘未沉没船只重叠于该位置的可能性计算最佳射击位置。
• 自适应算法，将船只放置在统计上对手不太可能射门的位置。
• 自适应算法，它更喜欢射击的位置，在统计上对手更有可能放置他的船。
• 把船放在一起，几乎不碰对方。

Answer 2

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

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

Answer 3

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