最強の戦艦 AI は何ですか?

Question

戦艦！

2003 年 (私が 17 歳のとき)、私はある大会に出場しました。 戦艦AI コーディングコンテスト。そのトーナメントでは負けましたが、とても楽しかったですし、そこから多くのことを学びました。

今、最高の戦艦 AI を求めてこの競争を復活させたいと思います。

ここは このフレームワークは現在 Bitbucket でホストされています.

勝者には+450の評判が与えられます! 大会は から開催されます 2009 年 11 月 17 日. 。17 日の午前 0 時以降のエントリーや編集は受け付けられません。（中央標準時間）エントリを早期に提出してください。そうすれば、機会をお見逃しなく！

これを維持するには 客観的, 、競技の精神に従ってください。

ゲームのルール：

1. ゲームは 10x10 のグリッドでプレイされます。
2. 各競技者は、5 隻の船 (長さ 2、3、3、4、5) をそれぞれのグリッドに配置します。
3. 船が重なり合うことはできませんが、隣接することはできます。
4. その後、競技者は順番に対戦相手に単発の射撃を行います。
   • ゲームのバリエーションでは、ボレーごとに複数のショット (生き残っている船ごとに 1 つ) を発射することができます。
5. ショットが沈んだか、当たったか、外れた場合、対戦相手は競技者に通知します。
6. いずれかのプレイヤーの船がすべて沈没すると、ゲーム プレイは終了します。

コンテストのルール:

1. コンテストの精神は、最高の Battleship アルゴリズムを見つけることです。
2. コンテストの趣旨に反しているとみなされるものは失格となります。
3. 対戦相手への妨害は競技の精神に反します。
4. マルチスレッドは次の制限の下で使用できます。
   • 自分の番ではない間、複数のスレッドを実行することはできません。(ただし、任意の数のスレッドが「一時停止」状態になる可能性があります)。
   • 「通常」以外の優先度でスレッドを実行することはできません。
   • 上記 2 つの制限を考慮すると、自分のターン中に少なくとも 3 つの専用 CPU コアが保証されます。
5. プライマリ スレッドでは、ゲームごとに 1 秒の CPU 時間の制限が各競技者に割り当てられます。
6. 時間がなくなると、現在のゲームに負けます。
7. 処理されない例外があると、現在のゲームに負けます。
8. ネットワーク アクセスとディスク アクセスは許可されていますが、時間制限がかなり厳しいと感じる場合があります。ただし、時間の負担を軽減するために、いくつかのセットアップおよびティアダウン方法が追加されています。
9. コードはスタック オーバーフローに回答として投稿するか、大きすぎる場合はリンクする必要があります。
10. エントリの最大合計サイズ (非圧縮) は 1 MB です。
11. 公式には、.Net 2.0 / 3.5 が唯一のフレームワーク要件です。
12. エントリは IBattleshipOpponent インターフェイスを実装する必要があります。

採点:

1. 101試合中、最も良い51試合が試合の勝者となります。
2. すべての競技者はラウンドロビン形式で互いに対戦します。
3. その後、上位半分の参加者がダブルエリミネーション トーナメントをプレイして勝者を決定します。(実際には半分以上の最小の 2 の累乗。)
4. 私が使用するのは、 トーナメントアピ 大会の枠組み。
5. 結果はここに掲載されます。
6. 複数のエントリーを提出した場合、最高スコアのエントリーのみがダブルエリムの対象となります。

幸運を！楽しむ！

---

編集1:
おかげで フリード, の間違いを発見した人 Ship.IsValid 関数。修正されました。フレームワークの更新バージョンをダウンロードしてください。

編集2:
ディスクなどに統計を永続化することに大きな関心が寄せられているため、必要な機能を提供する、時間制限のないセットアップ イベントと破棄イベントをいくつか追加しました。これは 準破壊的な変更. 。つまり、次のようになります。インターフェースは機能を追加するために変更されていますが、それらの本体は必要ありません。フレームワークの更新バージョンをダウンロードしてください。

編集3:
バグ修正 1: GameWon そして GameLost タイムアウトの場合にのみコールされました。
バグ修正 2:ゲームごとにエンジンがタイムアウトしていたら、競争は決して終わることはありません。
フレームワークの更新バージョンをダウンロードしてください。

編集4:
トーナメント結果:

Answer 1

私は、1試合あたりの試合数をもっと増やすという動議に賛成します。50 ゲームを行うのは、コインを投げるだけです。テスト アルゴリズム間の妥当な区別を得るには、1000 回のゲームを実行する必要がありました。

ダウンロード ドレッドノート 1.2.

戦略:

• ヒット数が 0 を超える船舶の考えられるすべての位置を追跡します。リストは最大 30,000 を超えることはないため、すべての船のすべての可能な位置のリスト (非常に大きい) とは異なり、正確に保持できます。

• GetShotアルゴリズムには2つの部分があります。1つはランダムショットを生成し、もう1つはすでにヒットした船の沈没を終えようとします。ヒットしたすべての船が沈没する可能性のある位置 (上記のリストから) がある場合、ランダムな射撃を行います。それ以外の場合は、可能な限りの位置 (重み付け) を排除する射撃場所を選択して、船を沈め終えることを試みます。

• ランダムな射撃の場合、その位置に重なる不沈船の 1 隻の可能性に基づいて、射撃に最適な位置を計算します。

• 統計的に敵が射撃する可能性が低い場所に船を配置する適応アルゴリズム。

• 統計的に相手が自艦を配置する可能性が高い場所で射撃することを好む適応アルゴリズム。

• 船はほとんど互いに接触しないように配置してください。

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

対戦相手は次のとおりです。

• http://natekohl.net/files/FarnsworthOpponent.cs

固定ジオメトリにインスピレーションを得た戦略を使用する代わりに、次のことを試みることは興味深いだろうと思いました。 基礎となる確率を推定する 特定の未踏の空間には船が停泊しているということです。

これを正しく行うには、現在の世界観に適合する船の可能な構成をすべて調査し、それらの構成に基づいて確率を計算します。木を探索するようなものだと考えることができます。

可能な戦艦の状態の拡大 http://natekohl.net/media/battleship-tree.png

あなたが世界について知っていることと一致するその木のすべての葉を考えた後 （例えば。船は重複できません、ヒットしたすべてのマスは船でなければなりません、など) 未探索の各位置で船が出現する頻度を数えて、そこに船が停泊している可能性を推定できます。

これはヒート マップとして視覚化できます。ホット スポットには船舶が含まれる可能性が高くなります。

未探索の各位置の確率のヒート マップ http://natekohl.net/media/battleship-probs.png

この Battleship コンペティションで私が気に入っている点の 1 つは、上のツリーが、この種のアルゴリズムをブルート フォースするのに十分なほど小さいことです。5 隻の船それぞれに 150 個の可能な位置がある場合、150 個になります。⁵ = 750 億の可能性。そして、特に船全体を排除できた場合、その数はさらに小さくなるばかりです。

上でリンクした対戦相手はツリー全体を探索しません。750 億という数字は、1 秒以内に収めるにはまだ大きすぎます。ただし、いくつかのヒューリスティックを利用して、これらの確率を推定しようとします。

Answer 4

完全に本格的な回答ではありませんが、一般的なコードで実際の回答を乱雑にするのはほとんど意味がないようです。したがって、オープンソースの精神に基づいて、いくつかの拡張機能/一般クラスを紹介します。これらを使用する場合は、名前空間を変更してください。そうしないと、すべてを 1 つの 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!");
        }
    }
}

Answer 5

今は本格的なアルゴリズムを書く時間がありませんが、次のような考えがあります。対戦相手が船をランダムに配置した場合、配置確率は (5.5,5.5) を中心とした単純な分布になるのではありませんか?たとえば、x 次元での戦艦 (長さ 5 ユニット) の配置可能性は次のとおりです。

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....
...........

明らかに、アイデアにランダム性を加える必要がありますが、純粋に数学的にはそれが正しい方法だと思います。

Answer 6

そんなに洗練されたものはありませんが、私が思いついたものはこれです。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() { }
    }
}

ここでは、スペースを最小限に抑えながらも読みやすいように、少し要約されています。

Answer 7

コンペティション エンジンに関するコメントは次のとおりです。

NewGame パラメータ:

IBattleshipOpponent::NewGame がゲーム前のセットアップを目的としており、ボードサイズを取得する場合、船とそのそれぞれのサイズのリストも取得する必要があります。可変のシップ構成を許可せずに、可変の基板サイズを許可するのは意味がありません。

船は密閉されています:

クラスシップが封印されている理由がわかりません。基本的なことの中でも特に、船に名前を付けて、次のようなメッセージを出力できるようにしたいと考えています。 (「あなたは私の {0} を沈めました」、ship.Name);. 。他の拡張機能も念頭に置いているので、Ship は継承可能であるべきだと思います。

制限時間:

1 秒という制限時間はトーナメント ルールとしては理にかなっていますが、デバッグには完全に支障をきたします。BattleshipCompetition には、開発/デバッグを支援するために時間違反を無視する簡単な設定が必要です。また、使用されている時間をより正確に把握するには、System.Diagnostics.Process::UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime を調査することをお勧めします。

沈没船:

現在の API は、敵の船を沈没させたときに通知します。

ShotHit(Point shot, bool sunk);

だがしかし どれの 沈んだ船よ！私は、あなたが「あなたが私の戦艦を沈めた！」と宣言するために必要な人間と争いの規則の一部だと思います。 （または駆逐艦、またはサブなど）。

これは、AI が互いに衝突する船を追い出そうとする場合に特に重要です。API の変更を次のようにリクエストしたいと考えています。

ShotHit(Point shot, Ship ship);

もし 船 が null でない場合は、その砲撃が沈没砲撃であったことを意味し、どの船を沈めたのか、そしてどのくらいの長かったのかがわかります。射撃が非沈没砲撃であった場合、船は無効となり、それ以上の情報はありません。

Answer 8

クロスファイアが更新されました。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));
        }
    }

}

Answer 9

これは私が自由な時間にまとめることができた最高のものであり、存在しないものです。メイン関数をループしてキーを押すまで継続的に BattleshipCompetition を実行するように設定しているため、試合と試合の統計の集計が行われています。

namespace Battleship
{
    using System;
    using System.Collections.Generic;
    using System.Drawing;
    using System.Linq;

    public class BP7 : IBattleshipOpponent
    {
        public string Name { get { return "BP7"; } }
        public Version Version { get { return this.version; } }

        Random rand = new Random();
        Version version = new Version(0, 7);
        Size gameSize;
        List<Point> scanShots;
        List<NextShot> nextShots;
        int wins, losses;
        int totalWins = 0;
        int totalLosses = 0;
        int maxWins = 0;
        int maxLosses = 0;
        int matchWins = 0;
        int matchLosses = 0;

        public enum Direction { VERTICAL = -1, UNKNOWN = 0, HORIZONTAL = 1 };
        Direction hitDirection, lastShotDirection;

        enum ShotResult { UNKNOWN, MISS, HIT };
        ShotResult[,] board;

        public struct NextShot
        {
            public Point point;
            public Direction direction;
            public NextShot(Point p, Direction d)
            {
                point = p;
                direction = d;
            }
        }

        public struct ScanShot
        {
            public Point point;
            public int openSpaces;
            public ScanShot(Point p, int o)
            {
                point = p;
                openSpaces = o;
            }
        }

        public void NewGame(Size size, TimeSpan timeSpan)
        {
            this.gameSize = size;
            scanShots = new List<Point>();
            nextShots = new List<NextShot>();
            fillScanShots();
            hitDirection = Direction.UNKNOWN;
            board = new ShotResult[size.Width, size.Height];
        }

        private void fillScanShots()
        {
            int x;
            for (x = 0; x < gameSize.Width - 1; x++)
            {
                scanShots.Add(new Point(x, x));
            }

            if (gameSize.Width == 10)
            {
                for (x = 0; x < 3; x++)
                {
                    scanShots.Add(new Point(9 - x, x));
                    scanShots.Add(new Point(x, 9 - x));
                }
            }
        }

        public void PlaceShips(System.Collections.ObjectModel.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()
        {
            Point shot;

            if (this.nextShots.Count > 0)
            {
                if (hitDirection != Direction.UNKNOWN)
                {
                    if (hitDirection == Direction.HORIZONTAL)
                    {
                        this.nextShots = this.nextShots.OrderByDescending(x => x.direction).ToList();
                    }
                    else
                    {
                        this.nextShots = this.nextShots.OrderBy(x => x.direction).ToList();
                    }
                }

                shot = this.nextShots.First().point;
                lastShotDirection = this.nextShots.First().direction;
                this.nextShots.RemoveAt(0);
                return shot;
            }

            List<ScanShot> scanShots = new List<ScanShot>();
            for (int x = 0; x < gameSize.Width; x++)
            {
                for (int y = 0; y < gameSize.Height; y++)
                {
                    if (board[x, y] == ShotResult.UNKNOWN)
                    {
                        scanShots.Add(new ScanShot(new Point(x, y), OpenSpaces(x, y)));
                    }
                }
            }
            scanShots = scanShots.OrderByDescending(x => x.openSpaces).ToList();
            int maxOpenSpaces = scanShots.FirstOrDefault().openSpaces;

            List<ScanShot> scanShots2 = new List<ScanShot>();
            scanShots2 = scanShots.Where(x => x.openSpaces == maxOpenSpaces).ToList();
            shot = scanShots2[rand.Next(scanShots2.Count())].point;

            return shot;
        }

        int OpenSpaces(int x, int y)
        {
            int ctr = 0;
            Point p;

            // spaces to the left
            p = new Point(x - 1, y);
            while (p.X >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
            {
                ctr++;
                p.X--;
            }

            // spaces to the right
            p = new Point(x + 1, y);
            while (p.X < gameSize.Width && board[p.X, p.Y] == ShotResult.UNKNOWN)
            {
                ctr++;
                p.X++;
            }

            // spaces to the top
            p = new Point(x, y - 1);
            while (p.Y >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
            {
                ctr++;
                p.Y--;
            }

            // spaces to the bottom
            p = new Point(x, y + 1);
            while (p.Y < gameSize.Height && board[p.X, p.Y] == ShotResult.UNKNOWN)
            {
                ctr++;
                p.Y++;
            }

            return ctr;
        }

        public void NewMatch(string opponenet)
        {
            wins = 0;
            losses = 0;
        }

        public void OpponentShot(Point shot) { }

        public void ShotHit(Point shot, bool sunk)
        {
            board[shot.X, shot.Y] = ShotResult.HIT;

            if (!sunk)
            {
                hitDirection = lastShotDirection;
                if (shot.X != 0)
                {
                    this.nextShots.Add(new NextShot(new Point(shot.X - 1, shot.Y), Direction.HORIZONTAL));
                }

                if (shot.Y != 0)
                {
                    this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y - 1), Direction.VERTICAL));
                }

                if (shot.X != this.gameSize.Width - 1)
                {
                    this.nextShots.Add(new NextShot(new Point(shot.X + 1, shot.Y), Direction.HORIZONTAL));
                }

                if (shot.Y != this.gameSize.Height - 1)
                {
                    this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y + 1), Direction.VERTICAL));
                }
            }
            else
            {
                hitDirection = Direction.UNKNOWN;
                this.nextShots.Clear();     // so now this works like gangbusters ?!?!?!?!?!?!?!?!?
            }
        }

        public void ShotMiss(Point shot)
        {
            board[shot.X, shot.Y] = ShotResult.MISS;
        }

        public void GameWon()
        {
            wins++;
        }

        public void GameLost()
        {
            losses++;
        }

        public void MatchOver()
        {
            if (wins > maxWins)
            {
                maxWins = wins;
            }

            if (losses > maxLosses)
            {
                maxLosses = losses;
            }

            totalWins += wins;
            totalLosses += losses;

            if (wins >= 51)
            {
                matchWins++;
            }
            else
            {
                matchLosses++;
            }
        }

        public void FinalStats()
        {
            Console.WriteLine("Games won: " + totalWins.ToString());
            Console.WriteLine("Games lost: " + totalLosses.ToString());
            Console.WriteLine("Game winning percentage: " + (totalWins * 1.0 / (totalWins + totalLosses)).ToString("P"));
            Console.WriteLine("Game losing percentage: " + (totalLosses * 1.0 / (totalWins + totalLosses)).ToString("P"));
            Console.WriteLine();
            Console.WriteLine("Matches won: " + matchWins.ToString());
            Console.WriteLine("Matches lost: " + matchLosses.ToString());
            Console.WriteLine("Match winning percentage: " + (matchWins * 1.0 / (matchWins + matchLosses)).ToString("P"));
            Console.WriteLine("Match losing percentage: " + (matchLosses * 1.0 / (matchWins + matchLosses)).ToString("P"));
            Console.WriteLine("Match games won high: " + maxWins.ToString());
            Console.WriteLine("Match games lost high: " + maxLosses.ToString());
            Console.WriteLine();
        }
    }
}

このロジックは、私がドレッドノートに勝つために必要なロジックに最も近く、個々のゲームの約 41% で勝利しました。(実際には 52 対 49 のカウントで 1 つの試合に勝利しました。) 奇妙なことに、このクラスはファーンズワース相手に対して、はるかに進歩していない以前のバージョンほどうまくいきません。

Answer 10

私のコンピューターは現在デルで修理中ですが、先週の状況は次のとおりです。

namespace Battleship
{
    using System;
    using System.Collections.ObjectModel;
    using System.Drawing;
    using System.Collections.Generic;
    using System.Linq;

    public class BSKiller4 : OpponentExtended, IBattleshipOpponent
    {
        public string Name { get { return "BSKiller4"; } }
        public Version Version { get { return this.version; } }

        public bool showBoard = false;

        Random rand = new Random();
        Version version = new Version(0, 4);
        Size gameSize;

        List<Point> nextShots;
        Queue<Point> scanShots;

        char[,] board;

        private void printBoard()
        {
            Console.WriteLine();
            for (int y = 0; y < this.gameSize.Height; y++)
            {
                for (int x = 0; x < this.gameSize.Width; x++)
                {
                    Console.Write(this.board[x, y]);
                }
                Console.WriteLine();
            }
            Console.ReadKey();
        }

        public void NewGame(Size size, TimeSpan timeSpan)
        {
            this.gameSize = size;
            board = new char[size.Width, size.Height];
            this.nextShots = new List<Point>();
            this.scanShots = new Queue<Point>();
            fillScanShots();
            initializeBoard();
        }

        private void initializeBoard()
        {
            for (int y = 0; y < this.gameSize.Height; y++)
            {
                for (int x = 0; x < this.gameSize.Width; x++)
                {
                    this.board[x, y] = 'O';
                }
            }
        }

        private void fillScanShots()
        {
            int x, y;
            int num = gameSize.Width * gameSize.Height;
            for (int j = 0; j < 3; j++)
            {
                for (int i = j; i < num; i += 3)
                {
                    x = i % gameSize.Width;
                    y = i / gameSize.Height;
                    scanShots.Enqueue(new Point(x, y));
                }
            }
        }

        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 (showBoard) printBoard();
            Point shot;

            shot = findShotRun();
            if (shot.X != -1)
            {
                return shot;
            }

            if (this.nextShots.Count > 0)
            {
                shot = this.nextShots[0];
                this.nextShots.RemoveAt(0);
            }
            else
            {
                shot = this.scanShots.Dequeue();
            }

            return shot;
        }

        public void ShotHit(Point shot, bool sunk)
        {
            this.board[shot.X, shot.Y] = 'H';
            if (!sunk)
            {
                addToNextShots(new Point(shot.X - 1, shot.Y));
                addToNextShots(new Point(shot.X, shot.Y + 1));
                addToNextShots(new Point(shot.X + 1, shot.Y));
                addToNextShots(new Point(shot.X, shot.Y - 1));
            }
            else
            {
                this.nextShots.Clear();
            }
        }



        private Point findShotRun()
        {
            int run_forward_horizontal = 0;
            int run_backward_horizontal = 0;
            int run_forward_vertical = 0;
            int run_backward_vertical = 0;

            List<shotPossibilities> possible = new List<shotPossibilities>(5);

            // this only works if width = height for the board;
            for (int y = 0; y < this.gameSize.Height; y++)
            {
                for (int x = 0; x < this.gameSize.Width; x++)
                {
                    // forward horiz
                    if (this.board[x, y] == 'M')
                    {
                        run_forward_horizontal = 0;
                    }
                    else if (this.board[x, y] == 'O')
                    {
                        if (run_forward_horizontal >= 2)
                        {
                            possible.Add(
                                new shotPossibilities(
                                    run_forward_horizontal,
                                    new Point(x, y),
                                    true));
                        }
                        else
                        {
                            run_forward_horizontal = 0;
                        }
                    }
                    else
                    {
                        run_forward_horizontal++;
                    }

                    // forward vertical
                    if (this.board[y, x] == 'M')
                    {
                        run_forward_vertical = 0;
                    }
                    else if (this.board[y, x] == 'O')
                    {
                        if (run_forward_vertical >= 2)
                        {
                            possible.Add(
                                new shotPossibilities(
                                    run_forward_vertical,
                                    new Point(y, x),
                                    false));
                        }
                        else
                        {
                            run_forward_vertical = 0;
                        }
                    }
                    else
                    {
                        run_forward_vertical++;
                    }


                    // backward horiz
                    if (this.board[this.gameSize.Width - x - 1, y] == 'M')
                    {
                        run_backward_horizontal = 0;
                    }
                    else if (this.board[this.gameSize.Width - x - 1, y] == 'O')
                    {
                        if (run_backward_horizontal >= 2)
                        {
                            possible.Add(
                                new shotPossibilities(
                                    run_backward_horizontal,
                                    new Point(this.gameSize.Width - x - 1, y),
                                    true));
                        }
                        else
                        {
                            run_backward_horizontal = 0;
                        }
                    }
                    else
                    {
                        run_backward_horizontal++;
                    }


                    // backward vertical
                    if (this.board[y, this.gameSize.Height - x - 1] == 'M')
                    {
                        run_backward_vertical = 0;
                    }
                    else if (this.board[y, this.gameSize.Height - x - 1] == 'O')
                    {
                        if (run_backward_vertical >= 2)
                        {
                            possible.Add(
                                new shotPossibilities(
                                    run_backward_vertical,
                                    new Point(y, this.gameSize.Height - x - 1),
                                    false));
                        }
                        else
                        {
                            run_backward_vertical = 0;
                        }
                    }
                    else
                    {
                        run_backward_vertical++;
                    }

                }

                run_forward_horizontal = 0;
                run_backward_horizontal = 0;
                run_forward_vertical = 0;
                run_backward_vertical = 0;
            }
            Point shot;

            if (possible.Count > 0)
            {
                shotPossibilities shotp = possible.OrderByDescending(a => a.run).First();
                //this.nextShots.Clear();
                shot = shotp.shot;
                //if (shotp.isHorizontal)
                //{
                //    this.nextShots.RemoveAll(p => p.X != shot.X);
                //}
                //else
                //{
                //    this.nextShots.RemoveAll(p => p.Y != shot.Y);
                //}
            }
            else
            {
                shot = new Point(-1, -1);
            }

            return shot;
        }

        private void addToNextShots(Point p)
        {
            if (!this.nextShots.Contains(p) &&
                p.X >= 0 &&
                p.X < this.gameSize.Width &&
                p.Y >= 0 &&
                p.Y < this.gameSize.Height)
            {
                if (this.board[p.X, p.Y] == 'O')
                {
                    this.nextShots.Add(p);
                }
            }
        }

        public void GameWon()
        {
            this.GameWins++;
        }

        public void NewMatch(string opponent)
        {
            System.Threading.Thread.Sleep(5);
            this.rand = new Random(System.Environment.TickCount);
        }
        public void OpponentShot(Point shot) { }
        public void ShotMiss(Point shot)
        {
            this.board[shot.X, shot.Y] = 'M';
        }
        public void GameLost()
        {
            if (showBoard) Console.WriteLine("-----Game Over-----");
        }
        public void MatchOver() { }
    }


    public class OpponentExtended
    {
        public int GameWins { get; set; }
        public int MatchWins { get; set; }
        public OpponentExtended() { }
    }

    public class shotPossibilities
    {
        public shotPossibilities(int r, Point s, bool h)
        {
            this.run = r;
            this.shot = s;
            this.isHorizontal = h;
        }
        public int run { get; set; }
        public Point shot { get; set; }
        public bool isHorizontal { get; set; }
    }
}

Answer 11

分析をブルート フォースで行う場合、提供されている RandomOpponent の仕組みが非常に非効率的であることがわかるかもしれません。これにより、すでにターゲットにされた場所を再選択することができ、フレームワークはまだ触れていない場所に到達するか、移動ごとの制限時間が経過するまで、それを強制的に繰り返すことができます。

この対戦相手も同様の動作をします (効果的な配置分布は同じです)。健全性チェック自体を行うだけで、呼び出しごとに乱数生成を 1 つだけ消費します (償却)。

これは、拡張機能/ライブラリの回答のクラスを使用し、キーのメソッド/状態のみを提供します。

シャッフルが解除されました ジョン・スキートの答えはこちら

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 
}

Answer 12

私は参加できませんが、時間があれば実装したいアルゴリズムを以下に示します。

まず、攻撃を感知しても、すぐには船の残りの部分を追跡しません。船の位置のテーブルを作成し、完全に沈め始める前に、5 つすべてに少なくとも 1 回命中したかどうかを確認します。(これはマルチショットバリアントにとっては悪いポリシーであることに注意してください - コメントを参照してください)

1. 中心をヒットします (以下の最後の注記を参照してください - 「中心」は説明のための便宜にすぎません)
2. センター右4番のスポットを打ちます。
3. 中心から 1 つ下と 1 つ右のスポットをヒットします。
4. 前のヒットの 4 つ右のスポットをヒットします。

5. そのパターンを続けます (ボードを埋める 3 つのスペースで区切られた対角線が最終的に表示されるはずです) これは、長さ 4 および 5 のボートすべてにヒットし、統計的に多数の 3 および 2 ボートにヒットするはずです。

6. 対角線の間のスポットをランダムに打ち始めます。これにより、まだ気付かれていない2レングスと3レングスのボートを捕まえることができます。

5 つのヒットを検出したら、その 5 つのヒットが別のボートにあるかどうかを判断します。これは、2 つのヒットが同じ水平または垂直線上にあり、互いに 5 つの位置以内にある場所 (同じボートで 2 つのヒットがある可能性があります) の近くでさらに数ショットを行うことで比較的簡単です。それらが別々の船である場合は、すべての船を沈め続けます。それらが同じボートであることが判明した場合は、5 つのボートすべてが見つかるまで上記の充填パターンを続けます。

このアルゴリズムは単純な充填アルゴリズムです。主な特徴は、まだ認識していない船があるにもかかわらず、知っている船を沈めるのに時間を無駄にしないことと、非効率な充填パターンを使用しないことです (つまり、完全にランダムなパターンは無駄になります)。

最終メモ:

A) 「センター」はボード上のランダムな開始点です。これにより、このアルゴリズムの主な弱点が解消されます。B) 説明では最初から対角線を描画するように示されていますが、理想的には、アルゴリズムは単にそれらの対角線に沿った「ランダムな」位置を射撃するだけです。これは、競合他社が、自分の船が予測可能なパターンに遭遇するまでの時間を計るのを防ぐのに役立ちます。

これは、すべての船を (9x9)/2+10 発以内に収めるという点で「完璧な」アルゴリズムを表しています。

ただし、大幅に改善できる可能性があります。

船が攻撃されたら、「内部」の対角線を引く前にそのサイズを確認します。2 つの船を見つけた可能性があります。その場合、内部の対角線を単純化して 3 サイズの船をより早く見つけることができます。

ゲームの段階を特定し、それに応じて行動します。このアルゴリズムは、ゲームの特定の時点までは優れている可能性がありますが、ゲームの終盤では他のアルゴリズムの方が優れた利点が得られる可能性があります。また、他のプレイヤーがあなたに負けそうになっている場合は、別のアルゴリズムの方がうまく機能する可能性があります。たとえば、リスクの高いアルゴリズムはより頻繁に失敗する可能性がありますが、うまく機能するときはすぐに機能し、自分より勝利に近づいている対戦相手に勝つ可能性があります。 。

競合他社のプレイ スタイルを特定します。これにより、彼らが船の配置をどのように計画しているかについての手がかりが得られる可能性があります (つまり、競合他社のアルゴリズムが最も早く自分の船を配置する方法を特定する可能性が高くなります。手持ちのツールがハンマーしかない場合、すべてが釘のように見えます）

-アダム

Answer 13

私のエントリーです。

特別なことは何もありませんでした。私が持っていたすべての良いアイデアを追加する時間がありませんでした。

でも、かなり上手に弾けているようです。それが競争でどうなるか見てみましょう:

(これをファイルに入れてください Missouri.cs そしてプロジェクトに追加されました。)

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

namespace Battleship
{
    // The Empire of Japan surrendered on the deck of the USS Missouri on Sept. 2, 1945
    public class USSMissouri : IBattleshipOpponent
    {
        public String  Name    { get { return name; } }
        public Version Version { get { return ver;  } }

#region IBattleship Interface
        // IBattleship::NewGame
        public void NewGame(Size gameSize, TimeSpan timeSpan)
        {
            size      = gameSize;
            shotBoard = new ShotBoard(size);
            attackVector = new Stack<Attack>();
        }

        // IBattleship::PlaceShips
        public void PlaceShips(ReadOnlyCollection<Ship> ships)
        {
            HunterBoard board;
            targetBoards = new List<HunterBoard>();
            shotBoard    = new ShotBoard(size);
            foreach (Ship s in ships)
            {
                board = new HunterBoard(this, size, s);
                targetBoards.Add(board);

                // REWRITE: to ensure valid board placement.
                s.Place(
                    new Point(
                        rand.Next(size.Width),
                        rand.Next(size.Height)),
                    (ShipOrientation)rand.Next(2));
            }
        }

        // IBattleship::GetShot
        public Point GetShot()
        {
            Point p = new Point();

            if (attackVector.Count() > 0)
            {
                p = ExtendShot();
                return p;
            }

            // Contemplate a shot at every-single point, and measure how effective it would be.
            Board potential = new Board(size);
            for(p.Y=0; p.Y<size.Height; ++p.Y)
            {
                for(p.X=0; p.X<size.Width; ++p.X)
                {
                    if (shotBoard.ShotAt(p))
                    {
                        potential[p] = 0;
                        continue;
                    }

                    foreach(HunterBoard b in targetBoards)
                    {
                        potential[p] += b.GetWeightAt(p);
                    }
                }
            }

            // Okay, we have the shot potential of the board.
            // Lets pick a weighted-random spot.
            Point shot;
            shot = potential.GetWeightedRandom(rand.NextDouble());

            shotBoard[shot] = Shot.Unresolved;

            return shot;
        }

        public Point ExtendShot()
        {
            // Lets consider North, South, East, and West of the current shot.
            // and measure the potential of each
            Attack attack = attackVector.Peek();

            Board potential = new Board(size);

            Point[] points = attack.GetNextTargets();
            foreach(Point p in points)
            {
                if (shotBoard.ShotAt(p))
                {
                    potential[p] = 0;
                    continue;
                }

                foreach(HunterBoard b in targetBoards)
                {
                    potential[p] += b.GetWeightAt(p);
                }
            }

            Point shot = potential.GetBestShot();
            shotBoard[shot] = Shot.Unresolved;
            return shot;
        }

        // IBattleship::NewMatch
        public void NewMatch(string opponent)
        {
        }
        public void OpponentShot(Point shot)
        {
        }
        public void ShotHit(Point shot, bool sunk)
        {
            shotBoard[shot] = Shot.Hit;

            if (!sunk)
            {
                if (attackVector.Count == 0) // This is a first hit, open an attackVector
                {   
                    attackVector.Push(new Attack(this, shot));
                }
                else
                {
                    attackVector.Peek().AddHit(shot);    // Add a hit to our current attack.
                }
            }

            // What if it is sunk?  Close the top attack, which we've been pursuing.
            if (sunk)
            {
                if (attackVector.Count > 0)
                {
                    attackVector.Pop();
                }
            }
        }
        public void ShotMiss(Point shot)
        {
            shotBoard[shot] = Shot.Miss;

            foreach(HunterBoard b in targetBoards)
            {
                b.ShotMiss(shot);  // Update the potential map.
            }
        }
        public void GameWon()
        {
            Trace.WriteLine  ("I won the game!");
        }
        public void GameLost()
        {
            Trace.WriteLine  ("I lost the game!");
        }
        public void MatchOver()
        {
            Trace.WriteLine("This match is over.");
        }

#endregion 

        public ShotBoard theShotBoard
        {
            get { return shotBoard; }
        }
        public Size theBoardSize
        {
            get { return size; }
        }

        private Random rand = new Random();
        private Version ver = new Version(6, 3); // USS Missouri is BB-63, hence version 6.3
        private String name = "USS Missouri (abelenky@alum.mit.edu)";
        private Size size;
        private List<HunterBoard> targetBoards;
        private ShotBoard shotBoard;
        private Stack<Attack> attackVector;
    }

    // An Attack is the data on the ship we are currently working on sinking.
    // It consists of a set of points, horizontal and vertical, from a central point.
    // And can be extended in any direction.
    public class Attack
    {
        public Attack(USSMissouri root, Point p)
        {
            Player = root;
            hit = p;
            horzExtent = new Extent(p.X, p.X);
            vertExtent = new Extent(p.Y, p.Y);
        }

        public Extent HorizontalExtent
        {
            get { return horzExtent; }
        }
        public Extent VerticalExtent
        {
            get { return vertExtent; }
        }
        public Point  FirstHit
        {
            get { return hit; }
        }

        public void AddHit(Point p)
        {
            if (hit.X == p.X) // New hit in the vertical direction
            {
                vertExtent.Min = Math.Min(vertExtent.Min, p.Y);
                vertExtent.Max = Math.Max(vertExtent.Max, p.Y);
            }
            else if (hit.Y == p.Y)
            {
                horzExtent.Min = Math.Min(horzExtent.Min, p.X);
                horzExtent.Max = Math.Max(horzExtent.Max, p.X);
            }
        }
        public Point[] GetNextTargets() 
        {
            List<Point> bors = new List<Point>();

            Point p;

            p = new Point(hit.X, vertExtent.Min-1);
            while (p.Y >= 0 && Player.theShotBoard[p] == Shot.Hit)
            {
                if (Player.theShotBoard[p] == Shot.Miss)
                {
                    break; // Don't add p to the List 'bors.  
                }
                --p.Y;
            }
            if (p.Y >= 0 && Player.theShotBoard[p] == Shot.None) // Add next-target only if there is no shot here yet.
            {
                bors.Add(p);
            }

            //-------------------

            p = new Point(hit.X, vertExtent.Max+1);
            while (p.Y < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.Hit)
            {
                if (Player.theShotBoard[p] == Shot.Miss)
                {
                    break; // Don't add p to the List 'bors.  
                }
                ++p.Y;
            }
            if (p.Y < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.None)
            {
                bors.Add(p);
            }

            //-------------------

            p = new Point(horzExtent.Min-1, hit.Y);
            while (p.X >= 0 && Player.theShotBoard[p] == Shot.Hit)
            {
                if (Player.theShotBoard[p] == Shot.Miss)
                {
                    break; // Don't add p to the List 'bors.  
                }
                --p.X;
            }
            if (p.X >= 0 && Player.theShotBoard[p] == Shot.None)
            {
                bors.Add(p);
            }

            //-------------------

            p = new Point(horzExtent.Max+1, hit.Y);
            while (p.X < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.Hit)
            {
                if (Player.theShotBoard[p] == Shot.Miss)
                {
                    break; // Don't add p to the List 'bors.  
                }
                ++p.X;
            }
            if (p.X < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.None)
            {
                bors.Add(p);
            }

            return bors.ToArray();
        }

        private Point hit; 
        private Extent horzExtent;
        private Extent vertExtent;
        private USSMissouri Player;
    }

    public struct Extent
    {
        public Extent(Int32 min, Int32 max)
        {
            Min = min;
            Max = max;
        }
        public Int32 Min;
        public Int32 Max;
    }

    public class Board  // The potential-Board, which measures the full potential of each square.
    {
        // A Board is the status of many things.
        public Board(Size boardsize)
        {
            size = boardsize;
            grid = new int[size.Width , size.Height];
            Array.Clear(grid,0,size.Width*size.Height);
        }

        public int this[int c,int r]
        {
            get { return grid[c,r];  }
            set { grid[c,r] = value; }
        }
        public int this[Point p]
        {
            get { return grid[p.X, p.Y];  }
            set { grid[p.X, p.Y] = value; }
        }

        public Point GetWeightedRandom(double r)
        {
            Int32 sum = 0;
            foreach(Int32 i in grid)
            {
                sum += i;
            }

            Int32 index = (Int32)(r*sum);

            Int32 x=0, y=0;
            for(y=0; y<size.Height; ++y)
            {
                for(x=0; x<size.Width; ++x)
                {
                    if (grid[x,y] == 0) continue; // Skip any zero-cells
                    index -= grid[x,y];
                    if (index < 0) break;
                }
                if (index < 0) break;
            }

            if (x == 10 || y == 10)
                throw new Exception("WTF");

            return new Point(x,y);
        }

        public Point GetBestShot()
        {
            int max=grid[0,0];
            for(int y=0; y<size.Height; ++y)
            {
                for (int x=0; x<size.Width; ++x)
                {
                    max = (grid[x,y] > max)? grid[x,y] : max;
                }
            }

            for(int y=0; y<size.Height; ++y)
            {
                for (int x=0; x<size.Width; ++x)
                {
                    if (grid[x,y] == max)
                    {
                        return new Point(x,y);
                    }
                }
            }
            return new Point(0,0);
        }

        public bool IsZero()
        {
            foreach(Int32 p in grid)
            {
                if (p > 0)
                {
                    return false;
                }
            }
            return true;
        }

        public override String ToString()
        {
            String output = "";
            String horzDiv = "   +----+----+----+----+----+----+----+----+----+----+\n";
            String disp;
            int x,y;

            output += "      A    B    C    D    E    F    G    H    I    J    \n" + horzDiv;

            for(y=0; y<size.Height; ++y)
            {
                output += String.Format("{0} ", y+1).PadLeft(3);
                for(x=0; x<size.Width; ++x)
                {
                    switch(grid[x,y])
                    {
                        case (int)Shot.None:       disp = "";  break;
                        case (int)Shot.Hit:        disp = "#"; break;
                        case (int)Shot.Miss:       disp = "."; break;
                        case (int)Shot.Unresolved: disp = "?"; break;
                        default:                   disp = "!"; break;
                    }

                    output += String.Format("| {0} ", disp.PadLeft(2));
                }
                output += "|\n" + horzDiv;
            }

            return output;
        }

        protected Int32[,] grid;
        protected Size     size;
    }

    public class HunterBoard
    {
        public HunterBoard(USSMissouri root, Size boardsize, Ship target)
        {
            size = boardsize;
            grid = new int[size.Width , size.Height];
            Array.Clear(grid,0,size.Width*size.Height);

            Player = root;
            Target = target;
            Initialize();
        }

        public void Initialize()
        {
            int x, y, i;

            for(y=0; y<size.Height; ++y)
            {
                for(x=0; x<size.Width - Target.Length+1; ++x)
                {
                    for(i=0; i<Target.Length; ++i)
                    {
                        grid[x+i,y]++;
                    }
                }
            }

            for(y=0; y<size.Height-Target.Length+1; ++y)
            {
                for(x=0; x<size.Width; ++x)
                {
                    for(i=0; i<Target.Length; ++i)
                    {
                        grid[x,y+i]++;
                    }
                }
            }
        }

        public int this[int c,int r]
        {
            get { return grid[c,r];  }
            set { grid[c,r] = value; }
        }
        public int this[Point p]
        {
            get { return grid[p.X, p.Y];  }
            set { grid[p.X, p.Y] = value; }
        }

        public void ShotMiss(Point p)
        {
            int x,y;
            int min, max;

            min = Math.Max(p.X-Target.Length+1, 0);
            max = Math.Min(p.X, size.Width-Target.Length);
            for(x=min; x<=max; ++x)
            {
                DecrementRow(p.Y, x, x+Target.Length-1);
            }

            min = Math.Max(p.Y-Target.Length+1, 0);
            max = Math.Min(p.Y, size.Height-Target.Length);
            for(y=min; y<=max; ++y)
            {
                DecrementColumn(p.X, y, y+Target.Length-1);
            } 

            grid[p.X, p.Y] = 0;
        }

        public void ShotHit(Point p)
        {
        }

        public override String ToString()
        {
            String output = String.Format("Target size is {0}\n", Target.Length);
            String horzDiv = "   +----+----+----+----+----+----+----+----+----+----+\n";
            int x,y;

            output += "      A    B    C    D    E    F    G    H    I    J    \n" + horzDiv;
            for(y=0; y<size.Height; ++y)
            {
                output += String.Format("{0} ", y+1).PadLeft(3);
                for(x=0; x<size.Width; ++x)
                {
                    output += String.Format("| {0} ", grid[x,y].ToString().PadLeft(2));
                }
                output += "|\n" + horzDiv;
            }
            return output;
        }

        // If we shoot at point P, how does that affect the potential of the board?
        public Int32 GetWeightAt(Point p)
        {
            int x,y;
            int potential = 0;
            int min, max;

            min = Math.Max(p.X-Target.Length+1, 0);
            max = Math.Min(p.X, size.Width-Target.Length);
            for(x=min; x<=max; ++x)
            {
                if (Player.theShotBoard.isMissInRow(p.Y, x, x+Target.Length-1) == false)
                {
                    ++potential;
                }
            }

            min = Math.Max(p.Y-Target.Length+1, 0);
            max = Math.Min(p.Y, size.Height-Target.Length);
            for(y=min; y<=max; ++y)
            {
                if (Player.theShotBoard.isMissInColumn(p.X, y, y+Target.Length-1) == false)
                {
                    ++potential;
                }
            } 

            return potential;
        }

        public void DecrementRow(int row, int rangeA, int rangeB)
        {
            int x;
            for(x=rangeA; x<=rangeB; ++x)
            {
                grid[x,row] = (grid[x,row]==0)? 0 : grid[x,row]-1;
            }
        }
        public void DecrementColumn(int col, int rangeA, int rangeB)
        {
            int y;
            for(y=rangeA; y<=rangeB; ++y)
            {
                grid[col,y] = (grid[col,y]==0)? 0 : grid[col,y]-1;
            }
        }

        private Ship Target = null;
        private USSMissouri Player;
        private Int32[,] grid;
        private Size     size;
    }

    public enum Shot
    {
        None = 0,
        Hit = 1,
        Miss = 2,
        Unresolved = 3
    };

    public class ShotBoard
    {
        public ShotBoard(Size boardsize)
        {
            size = boardsize;
            grid = new Shot[size.Width , size.Height];

            for(int y=0; y<size.Height; ++y)
            {
                for(int x=0; x<size.Width; ++x)
                {
                    grid[x,y] = Shot.None;
                }
            }
        }

        public Shot this[int c,int r]
        {
            get { return grid[c,r];  }
            set { grid[c,r] = value; }
        }
        public Shot this[Point p]
        {
            get { return grid[p.X, p.Y];  }
            set { grid[p.X, p.Y] = value; }
        }

        public override String ToString()
        {
            String output = "";
            String horzDiv = "   +----+----+----+----+----+----+----+----+----+----+\n";
            String disp;
            int x,y;

            output += "      A    B    C    D    E    F    G    H    I    J    \n" + horzDiv;

            for(y=0; y<size.Height; ++y)
            {
                output += String.Format("{0} ", y+1).PadLeft(3);
                for(x=0; x<size.Width; ++x)
                {
                    switch(grid[x,y])
                    {
                        case Shot.None:       disp = "";  break;
                        case Shot.Hit:        disp = "#"; break;
                        case Shot.Miss:       disp = "."; break;
                        case Shot.Unresolved: disp = "?"; break;
                        default:              disp = "!"; break;
                    }

                    output += String.Format("| {0} ", disp.PadLeft(2));
                }
                output += "|\n" + horzDiv;
            }
            return output;
        }

        // Functions to find shots on the board, at a specific point, or in a row or column, within a range
        public bool ShotAt(Point p)
        {
            return !(this[p]==Shot.None);
        }
        public bool isMissInColumn(int col, int rangeA, int rangeB)
        {
            for(int y=rangeA; y<=rangeB; ++y)
            {
                if (grid[col,y] == Shot.Miss)
                {
                    return true;
                }
            }
            return false;
        }
        public bool isMissInRow(int row, int rangeA, int rangeB)
        {
            for(int x=rangeA; x<=rangeB; ++x)
            {
                if (grid[x,row] == Shot.Miss)
                {
                    return true;
                }
            }
            return false;
        }
        protected Shot[,] grid;
        protected Size     size;
    }
}

Answer 14

これはミニマックスではありません。実際、船を配置した後、各プレイヤーは自分でプレイすることができず、その結果、敵の船をすべて沈めるのに何ターンもかかったのでしょうか?ターン数が少ない方が勝ちです。

私は、被弾した船を沈め、船が隠れる可能性のある残りの場所をカバーするために砲撃数を最小限に抑える以外に、優れた一般的な戦略はないと思います。

もちろん、ランダムでないものには対抗戦略があるかもしれません。しかし、すべてのプレイヤーに対して有効な戦略があるとは思いません。

Answer 15

実際、このパズルの最大の問題は、基本的に 2 つの動きが必要なことだと思います。1 つは自分の船を配置することであり、もう 1 つは敵の船を見つけることです (2 番目の部分がどんなに分割されていても、ランダムな要素で時計を破ろうとすることを除けば、単に「アルゴリズムを実行する」だけです)。敵の戦略を判断してそれに対抗する仕組みがないため、連続ラウンドの「ジャンケン」をベースにした同様の競技が非常に興味深いものになっています。

また、すべてのソリューションを C# にする必要があると規定するよりも、ゲームをネットワーク プロトコルとして指定し、そのプロトコルを C# で実装するためのフレームワークを提供した方がクールだと思いますが、これは単なる私の意見です。

編集：競技規則を十分に注意深く読んでいなかったため、最初の指摘を取り消します。

Answer 16

私はいつも真ん中からスタートして、その一点からスパイラル状に遠ざかっていくのが好きだった。あのクソサブを考慮して、他のポイントの間には 1 つ以上の空白を残さないようにするんだ…砲撃間の間隔はどの船が沈没したかによって決まりました。B シップが最後であれば、無駄なショットを最小限に抑えるために、ショット間に 4 つのスペースを残すだけで済みます。

Answer 17

英国コンピュータ協会を代表してサリー大学のジェームス・ヘザー博士が主催した同様のコンテストがあった。

リソースには制限が設けられました。つまり、ターンごとの最大プロセッサ時間、移動の間に状態を保存できないこと、最大ヒープ サイズが課されました。時間を制限するために、AI はタイムスロット内の任意の時点で移動を送信でき、ターンの終了時に移動を要求されます。

非常に興味深い - 詳細については、次を参照してください。 http://www.bcsstudentcontest.com/

さらにアイデアが得られるかもしれません。

Answer 18

このままでは、ubuntu 9.10 linux の monodevelop で変更を加えることなく、ソリューションが開き、実行されます。

Answer 19

あなたが書いた：

• コンテストの趣旨に反しているとみなされるものは失格となります。
• 対戦相手への妨害は競技の精神に反します。

「競争の精神に反する」と「対戦相手への妨害」の定義を教えてください。

また、簡単にするために、次のことをお勧めします。

• 相手のCPUスロット中はCPUの使用を一切禁止します。
• スレッドの並列処理を禁止し、代わりに単一スレッドでより多くの CPU 秒数を与えます。これにより、AI のプログラミングが簡素化され、CPU やメモリに制約のある人には何の害もありません。

PS - ここに潜んでいる CS ポスドクへの質問:このゲームは解決可能ではないでしょうか (つまり、唯一の最良の戦略はありますか?)。はい、ボードのサイズとステップ数により、minimax などが必須になりますが、それでも疑問に思うことがあります...複雑さの点では囲碁やチェスとは程遠い。

Answer 20

私は、相手のランダムシードとコールパターンをリバースエンジニアリングできた人が勝つと予想します。

ただし、それがどの程度の可能性があるかはわかりません。

Answer 21

おそらく、ゲームにバリエーションを加えてこれらのシリーズを実行することも可能でしょう。

3D 飛行機などを追加したり、1 ターン射撃する代わりに 1 隻の船を移動できるようにすると、おそらくゲームがかなり変わるでしょう。

Answer 22

1秒 合計 ゲーム時間はマシンによって異なります。トーナメント マシンと比較すると、私のマシンでは 1 秒分の CPU 操作が異なります。1 秒以内に CPU 時間を最大限に活用するように Battle Ship アルゴリズムを最適化した場合、低速の可能性があるトーナメント マシンで実行すると、必ず負けてしまいます。

このフレームワークの制限を回避する方法はわかりませんが、対処する必要があります。

...

一つのアイデアは、このコンテストで行われたことを行うことです http://www.bcsstudentcontest.com/

また、合計ゲーム時間の最大値ではなく、ターンあたりの最大時間を設定します。このようにして、既知のターンタイム内に収まるようにアルゴリズムを制限できます。ゲームは 50 ～ 600 ターン以上続く可能性がありますが、アルゴリズムが総ゲーム時間を管理している場合、最善の仕事をするのに十分な時間が与えられないか、時間がかかりすぎて負ける可能性があります。Battleship アルゴリズム内で合計ゲーム時間を管理するのは非常に困難です。

総ゲーム時間ではなくターン時間を制限するようにルールを変更することをお勧めします。

編集

考えられるすべてのショットを列挙してランク付けし、最も高いランクのショットを撮影するアルゴリズムを作成したとします。考えられるすべてのショットを生成するには時間がかかりすぎるため、アルゴリズムを一定時間実行させてから停止します。

ターンベースの制限がある場合は、アルゴリズムを 0.9 秒間実行して最高ランクのショットを返し、ターン時間制限を十分に守ることができます。

合計ゲーム時間を 1 秒に制限すると、各ターンでアルゴリズムをどれくらいの時間実行する必要があるかを決定するのが難しくなります。CPU 時間を最大限に活用したいと考えています。ゲームが 500 ラウンド続いた場合、各ターンを 0.002 秒に制限できますが、ゲームが 100 ラウンド続いた場合、各ターンに 0.01 秒の CPU 時間を与えることができます。

現在の制限では、アルゴリズムがショット空間の半網羅的な検索を使用してベスト ショットを見つけることは非現実的です。

合計ゲーム時間が 1 秒であるため、ゲームで競争するために効果的に使用できるアルゴリズムの種類が制限されています。

Answer 23

ここでは実際のコードを入れずに対処していますが、一般的な観察をいくつか危険にさらしておきます。

• すべての船のサイズは少なくとも 2 セルであるため、Space Quest V のゲームの実装で見た最適化を使用できます。これは、ターゲットを「探索」している間、ダイヤモンド パターンで交互のセルにのみ発砲します。これにより、マス目の半分が削除されますが、最終的にはすべての船が見つかることが保証されます。
• ターゲットを探すときにランダムな発砲パターンを使用すると、多くのゲームで統計的に最良の結果が得られます。

Answer 24

![確率密度][1]画像の説明を入力してください

![ここに画像の説明を入力][2]

私はランドン射撃と愚かな狩り/標的の結果を比較して実験し、最後に洗練された検索を行いました。

最良の解決策は、残りの船が個々の正方形を使用する可能性を表す確率密度関数を作成し、最も高い値を持つ正方形を狙うことであると思われます。

私の結果はここで見ることができます ここにリンクの説明を入力してください

Answer 25

「Battleship」は、古典的なコンピューター サイエンスの NP 完全問題として知られています。

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

(戦艦を探してください - ゲームとパズルの下にあります)