战舰!

早在2003年(当时我17岁),我参加了一场《战舰》AI编码比赛。尽管我输了那场比赛,但我从中获得了很多乐趣,也学到了很多东西。

现在,我想恢复这个比赛,在搜索最好的战舰AI。

下面是这个框架,现在托管在Bitbucket上。

获胜者将获得+450声望奖励!比赛将于2009年11月17日开始。17号零时之前的投稿和编辑将不被接受。(中央标准时间) 尽早提交你的作品,这样你就不会错过机会!

为了保持这个目标,请遵循比赛的精神。

游戏规则:

游戏在10x10的网格上进行。 每个参赛者将5艘船(长度为2、3、3、4、5)中的每一艘放在他们的网格上。 没有船只可以重叠,但它们可以相邻。 然后选手们轮流向对手射击。 游戏的一个变体允许每次齐射多次,每艘幸存的船一次。 如果击球沉、命中或未命中,对手将通知选手。 当任何一名玩家的所有船只都沉没时,游戏就结束了。

比赛规则:

The spirit of the competition is to find the best Battleship algorithm. Anything that is deemed against the spirit of the competition will be grounds for disqualification. Interfering with an opponent is against the spirit of the competition. Multithreading may be used under the following restrictions: No more than one thread may be running while it is not your turn. (Though, any number of threads may be in a "Suspended" state). No thread may run at a priority other than "Normal". Given the above two restrictions, you will be guaranteed at least 3 dedicated CPU cores during your turn. A limit of 1 second of CPU time per game is allotted to each competitor on the primary thread. Running out of time results in losing the current game. Any unhandled exception will result in losing the current game. Network access and disk access is allowed, but you may find the time restrictions fairly prohibitive. However, a few set-up and tear-down methods have been added to alleviate the time strain. Code should be posted on stack overflow as an answer, or, if too large, linked. Max total size (un-compressed) of an entry is 1 MB. Officially, .Net 2.0 / 3.5 is the only framework requirement. Your entry must implement the IBattleshipOpponent interface.

得分:

Best 51 games out of 101 games is the winner of a match. All competitors will play matched against each other, round-robin style. The best half of the competitors will then play a double-elimination tournament to determine the winner. (Smallest power of two that is greater than or equal to half, actually.) I will be using the TournamentApi framework for the tournament. The results will be posted here. If you submit more than one entry, only your best-scoring entry is eligible for the double-elim.

好运!玩得开心!


编辑1: 多亏弗里德,他在飞船上发现了一个错误。是否是可用的函数。问题已经解决了。请下载框架的更新版本。

编辑2: 由于人们对将统计数据持久化到磁盘等非常感兴趣,所以我添加了一些非计时设置和删除事件,它们应该能够提供所需的功能。这是一个半突破性的变化。也就是说:修改了接口,添加了功能,但不需要body。请下载框架的更新版本。

编辑3: 错误修复1:GameWon和GameLost只在超时的情况下被调用。 错误修复2:如果引擎在每一款游戏中都暂停计时,那么竞争将永远不会结束。 请下载框架的更新版本。

编辑4: 比赛结果:


当前回答

交火中更新。 我知道它不能与Farnsworth或Dreadnought竞争,但它比后者快得多,而且如果有人想尝试的话,它很简单。 这依赖于我的库的当前状态,包括在这里使它易于使用。

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

namespace Battleship.ShuggyCoUk
{
    public class Simple : IBattleshipOpponent
    {
        BoardView<OpponentsBoardState> opponentsBoard = new BoardView<OpponentsBoardState>(new Size(10,10));
        Rand rand = new Rand();
        int gridOddEven;
        Size size;

        public string Name { get { return "Simple"; } }

        public Version Version { get { return new Version(2, 1); }}

        public void NewMatch(string opponent) {}

        public void NewGame(System.Drawing.Size size, TimeSpan timeSpan)
        {
            this.size = size;
            this.opponentsBoard = new BoardView<OpponentsBoardState>(size);
            this.gridOddEven = rand.Pick(new[] { 0, 1 });
        }

        public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection<Ship> ships)
        {
            BoardView<bool> board = new BoardView<bool>(size);
            var AllOrientations = new[] {
                ShipOrientation.Horizontal,
                ShipOrientation.Vertical };

            foreach (var ship in ships)
            {
                int avoidTouching = 3;
                while (!ship.IsPlaced)
                {
                    var l = rand.Pick(board.Select(c => c.Location));
                    var o = rand.Pick(AllOrientations);
                    if (ship.IsLegal(ships, size, l, o))
                    {
                        if (ship.IsTouching(ships, l, o)&& --avoidTouching > 0)
                            continue;
                        ship.Place(l, o);
                    }
                }
            }
        }
        protected virtual Point PickWhenNoTargets()
        {
            return rand.PickBias(x => x.Bias,
                opponentsBoard
                // nothing 1 in size
                .Where(c => (c.Location.X + c.Location.Y) % 2 == gridOddEven)
                .Where(c => c.Data == OpponentsBoardState.Unknown))
                .Location;
        }

        private int SumLine(Cell<OpponentsBoardState> c, int acc)
        {
            if (acc >= 0)
                return acc;
            if (c.Data == OpponentsBoardState.Hit)
                return acc - 1;
            return -acc;
        }

        public System.Drawing.Point GetShot()
        {
            var targets = opponentsBoard
                .Where(c => c.Data == OpponentsBoardState.Hit)
                .SelectMany(c => c.Neighbours())
                .Where(c => c.Data == OpponentsBoardState.Unknown)
                .ToList();
            if (targets.Count > 1)
            {
                var lines = targets.Where(
                    x => x.FoldAll(-1, SumLine).Select(r => Math.Abs(r) - 1).Max() > 1).ToList();
                if (lines.Count > 0)
                    targets = lines;
            }
            var target = targets.RandomOrDefault(rand);
            if (target == null)
                return PickWhenNoTargets();
            return target.Location;
        }

        public void OpponentShot(System.Drawing.Point shot)
        {
        }

        public void ShotHit(Point shot, bool sunk)
        {
            opponentsBoard[shot] = OpponentsBoardState.Hit;
            Debug(shot, sunk);
        }

        public void ShotMiss(Point shot)
        {
            opponentsBoard[shot] = OpponentsBoardState.Miss;
            Debug(shot, false);
        }

        public const bool DebugEnabled = false;

        public void Debug(Point shot, bool sunk)
        {
            if (!DebugEnabled)
                return;
            opponentsBoard.WriteAsGrid(
                Console.Out,
                x =>
                {
                    string t;
                    switch (x.Data)
                    {
                        case OpponentsBoardState.Unknown:
                            return " ";
                        case OpponentsBoardState.Miss:
                            t = "m";
                            break;
                        case OpponentsBoardState.MustBeEmpty:
                            t = "/";
                            break;
                        case OpponentsBoardState.Hit:
                            t = "x";
                            break;
                        default:
                            t = "?";
                            break;
                    }
                    if (x.Location == shot)
                        t = t.ToUpper();
                    return t;
                });
            if (sunk)
                Console.WriteLine("sunk!");
            Console.ReadLine();
        }

        public void GameWon()
        {
        }

        public void GameLost()
        {
        }

        public void MatchOver()
        {
        }

        #region Library code
        enum OpponentsBoardState
        {
            Unknown = 0,
            Miss,
            MustBeEmpty,
            Hit,
        }

        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
        }

        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!");
            }
        }
        #endregion
    }

    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, Battleship.ShuggyCoUk.Simple.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, Battleship.ShuggyCoUk.Simple.Rand rand)
        {
            int count = things.Count();
            if (count == 0)
                return default(T);
            return things.ElementAt(rand.Next(count));
        }
    }

}

其他回答

当然,我们也有可能在游戏的基础上运行一系列类似的游戏。

添加3d飞机或能够移动一艘船而不是射击回合等内容可能会改变游戏。

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

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

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

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 
}

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

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

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

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

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

亚当

我总是喜欢从中间开始,从那个点螺旋离开,在任何其他点之间留下不超过1个空白,以解释那个该死的子…射击间隔取决于哪艘船被击沉。如果b舰是最后一艘,射击之间只需要留出4个空间来减少浪费

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

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

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