c# - рекорды - су 57




Каков лучший Истребитель Броненосец? (17)

Вот моя запись! (Самое наивное решение возможно)

«Случайный 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() { }
    }
}

Морской бой!

Еще в 2003 году (когда мне было 17 лет) я участвовал в конкурсе на кодирование искусственного боевого корабля . Несмотря на то, что я проиграл этот турнир, мне было очень весело и многому научилось.

Теперь я хотел бы воскресить этот конкурс, в поисках лучшего линкора AI.

Вот основа, которая теперь размещена на Bitbucket .

Победитель получит +450 репутации! Конкурс состоится 17 ноября 2009 года . Никакие записи или изменения позже нулевого часа 17-го числа не будут приняты. (Центральное стандартное время) Отправьте свои заявки на ранней стадии, так что вы не упустите свою возможность!

Чтобы сохранить эту ЦЕЛЬ , следуйте духу конкурса.

Правила игры:

  1. Игра воспроизводится на сетке 10x10.
  2. Каждый участник будет размещать каждый из 5 кораблей (длиной 2, 3, 3, 4, 5) на своей сетке.
  3. Никакие корабли не могут пересекаться, но они могут быть смежными.
  4. Затем соперники поочередно стреляют в одиночных выстрелов у своего оппонента.
    • Вариант игры позволяет выстрелить несколько выстрелов за залп, по одному на каждый выживший корабль.
  5. Оппонент уведомит участника, если выстрел опускается, попадает или промахивается.
  6. Игра заканчивается, когда все корабли любого игрока потоплены.

Правила конкурса:

  1. Дух соревнований - найти лучший алгоритм Битвы.
  2. Все, что считается против духа конкуренции, будет основанием для дисквалификации.
  3. Препятствие противнику противоречит духу соревнования.
  4. Многопоточность может использоваться при следующих ограничениях:
    • Не более одного потока может работать, пока это не ваша очередь. (Хотя любое количество потоков может находиться в состоянии «приостановлено»).
    • Ни один поток не может работать с приоритетом, отличным от «Нормального».
    • Учитывая вышеуказанные два ограничения, вам гарантируется как минимум 3 выделенных ядра процессора во время вашего хода.
  5. Предел в 1 секунду времени процессора на игру отводится каждому конкуренту в основной нити.
  6. Потеря времени приводит к потере текущей игры.
  7. Любое необработанное исключение приведет к потере текущей игры.
  8. Доступ к сети и доступ к диску разрешены, но ограничения по времени могут быть довольно запретительными. Однако для облегчения временной деформации были добавлены несколько методов настройки и снятия.
  9. Код должен быть опубликован при переполнении стека в качестве ответа или, если он слишком большой, связан.
  10. Максимальный общий размер (без сжатия) записи составляет 1 МБ.
  11. Официально .Net 2.0 / 3.5 - единственное требование к инфраструктуре.
  12. В вашей записи должен быть реализован интерфейс IBattleshipOpponent.

Подсчет очков:

  1. Лучшие 51 игры из 101 игр - победитель матча.
  2. Все соперники будут играть друг против друга, круговым.
  3. Лучшая половина конкурентов будет играть в турнире с двумя исключениями, чтобы определить победителя. (Наименьшая мощность двух, которая больше или равна половине, фактически).
  4. Я буду использовать платформу TournamentApi для турнира.
  5. Результаты будут опубликованы здесь.
  6. Если вы отправляете более одной записи, только ваша запись с наилучшим результатом подходит для двойного исключения.

Удачи! Повеселись!

ИЗМЕНИТЬ 1:
Спасибо Freed , кто нашел ошибку в функции Ship.IsValid . Он исправлен. Загрузите обновленную версию фреймворка.

EDIT 2:
Так как существует значительный интерес к сохраняющейся статистике на диске и тому подобное, я добавил несколько нестандартных событий настройки и разрыва, которые должны обеспечить требуемую функциональность. Это полуразрушающее изменение . То есть: интерфейс был изменен для добавления функций, но для них не требуется тело. Загрузите обновленную версию фреймворка.

ИЗМЕНИТЬ 3:
Исправление GameWon 1: GameWon и GameLost только в случае тайм-аута.
Bug Fix 2: Если двигатель выбрал каждую игру, соревнование никогда не закончится.
Загрузите обновленную версию фреймворка.

EDIT 4:
Результаты турнира:


Вот противник для игры:

Вместо использования фиксированной геометрии, вдохновленной стратегии, я подумал, что было бы интересно попытаться оценить основные вероятности того, что какое-либо конкретное неисследованное пространство удерживает корабль.

Чтобы сделать это правильно, вы должны изучить все возможные конфигурации кораблей, которые соответствуют вашему текущему мировому виду, а затем вычислить вероятности на основе этих конфигураций. Вы могли бы подумать об этом, как исследовать дерево:

расширение возможных состояний броненосца http://natekohl.net/media/battleship-tree.png

Рассмотрев все листья этого дерева, которые оживляют то, что вы знаете о мире (например, корабли не могут пересекаться, все хит-квадраты должны быть кораблями и т. Д.), Вы можете подсчитать, как часто корабли происходят в каждой неизведанной позиции, чтобы оценить вероятность того, что там сидит корабль.

Это можно представить в виде карты тепла, где горячие точки, скорее всего, содержат корабли:

тепловая карта вероятностей для каждой неизведанной позиции http://natekohl.net/media/battleship-probs.png

Одна вещь, которая мне нравится в этом соревновании «Броненосец», заключается в том, что вышедшее дерево почти достаточно мало, чтобы использовать этот алгоритм. Если есть 150 возможных позиций для каждого из 5 кораблей, это 150 5 = 75 миллиардов возможностей. И это число становится меньше, особенно если вы можете уничтожить целые корабли.

Противник, с которым я связан выше, не исследует все дерево; 75 миллиардов до сих пор остаются большими, чтобы занять второе место. Он пытается оценить эти вероятности, хотя, с помощью нескольких эвристик.


Ничего сложного, кроме того, что я придумал. Он бьет случайного противника в 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() { }
    }
}

Немного сжаты, чтобы заняться минимальным пространством здесь и все еще быть читаемым.


Обновлено CrossFire. Я знаю, что он не может конкурировать с 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));
        }
    }

}


Это не полноценный ответ, но, кажется, мало смысла загромождать реальные ответы с распространенным кодом. Таким образом, я предлагаю некоторые расширения / общие классы в духе open source. Если вы используете их, то, пожалуйста, измените пространство имен или попытайтесь скомпилировать все в одну dll, это не сработает.

BoardView позволяет вам легко работать с аннотированной доской.

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

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

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

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

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

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

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

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

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

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

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

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

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

        private Cell<T>[] history;

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

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

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

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

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

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

        #region IEnumerable<Cell<T>> Members

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

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

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

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

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

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

        #endregion
    }
}

Некоторые расширения, некоторые из которых дублируют функциональность в основной структуре, но должны действительно выполняться вами.

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

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

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

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

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

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

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

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

Что-то я в конечном итоге использую много.

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

Рандомизации. Безопасный, но проверяемый, полезный для тестирования.

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

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

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

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

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

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

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

Я второй, чтобы сделать намного больше игр за матч. Выполнение 50 игр - это просто переворачивание монетки. Мне нужно было сделать 1000 игр, чтобы получить разумное различие между тестовыми алгоритмами.

Загрузите Dreadnought 1.2 .

Стратегии:

  • следить за всеми возможными позициями для кораблей, которые имеют> 0 ударов. Список никогда не становится больше ~ 30K, поэтому его можно сохранить точно, в отличие от списка всех возможных позиций для всех кораблей (что очень велико).

  • Алгоритм GetShot состоит из двух частей, один из которых генерирует случайные снимки, а другой - для того, чтобы завершить погружение уже атакуемого корабля. Мы делаем случайные снимки, если есть возможная позиция (из приведенного выше списка), в которой все попавшие корабли затонуты. В противном случае мы пытаемся закончить погружение корабля, выбрав место для стрельбы, на котором устраняются самые возможные позиции (взвешенные).

  • Для случайных снимков выведите лучшее место для съемки, исходя из вероятности того, что один из неактивных кораблей перекрывает местоположение.

  • адаптивный алгоритм, который размещает корабли в местах, где противник статистически менее вероятен для стрельбы.

  • адаптивный алгоритм, который предпочитает стрелять в местах, где противник статистически чаще размещает свои корабли.

  • размещать корабли в основном не касаясь друг друга.


«Броненосец» - это так называемая классическая компьютерная наука NP-полная проблема.

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

(ищите Броненосец - это там, под играми и головоломками)


Аналогичный конкурс проводил д-р Джеймс Хизер из Университета Суррея от имени Британского компьютерного общества.

Ограничения были распределены по ресурсам, а именно максимальному времени процессора за ход, никакое состояние не могло быть сохранено между перемещениями, наложенным максимальным размером кучи. Чтобы ограничить время, AI мог отправить ход в любую точку в пределах временного интервала, и ему будет предложено двигаться по окончании хода.

Очень интересно - см. Больше на: http://www.bcsstudentcontest.com/

Могу дать вам еще несколько идей.


Вы написали:

  • Все, что считается против духа конкуренции, будет основанием для дисквалификации.
  • Препятствие противнику противоречит духу соревнования.

определите «против духа конкуренции» и «вмешиваетесь в противника»?

Также - для упрощения, я рекомендую вам:

  • запретить использование процессора вообще в слоте CPU соперника.
  • запретить параллелизм потоков и вместо этого дать больше процессорных секунд в одном потоке. Это упростит программирование ИИ и не повредит никому, кто в любом случае связан с ЦП / памятью.

PS - вопрос для CS post-docs, скрывающийся здесь: разве эта игра не разрешима (т. Е. Есть ли одна лучшая стратегия?). да, размер доски и количество шагов делают minimax и другие обязательными, но все же мне нужно задаться вопросом ... это далеко от Go и шахматы по сложности.


Как бы то ни было, решение открывается и запускается без изменений в monodevelop в ubuntu 9.10 linux


Сейчас мой компьютер ремонтируется dell, но на этом я был на прошлой неделе:

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; }
    }
}

Я выхожу сюда, не вставляя фактический код, но я буду подвергать опасности некоторые общие наблюдения:

  • Поскольку у всех кораблей размером не менее 2 ячеек, вы можете использовать оптимизацию, которую я видел при реализации игры в Space Quest V - которая срабатывает только в альтернативных ячейках в алмазном узоре, когда она «ищет» цель. Это устраняет половину квадратов, все еще гарантируя, что вы все время найдете все корабли.
  • Случайная схема стрельбы при поиске целей будет статистически давать лучшие результаты во многих играх.

Я предсказываю, что человек, которому удастся перепроектировать своих противников случайное семя и шаблон призыва, победит.

Не уверен, насколько это возможно.


Если вы грубо заставляете свой анализ, вы можете обнаружить, что механика поставляемого RandomOpponent очень неэффективна. Он позволяет себе повторно выбирать уже настроенные местоположения и позволяет рамке заставлять его повторять до тех пор, пока он не достигнет того, к которому он еще не прикоснулся, или истекает время на один ход.

Этот противник имеет схожее поведение (эффективное распределение размещения одинаково), он просто проверяет работоспособность и потребляет только одно генерирование случайных чисел за один вызов (амортизируется)).

Это использует классы в ответе на расширение / библиотеку, и я предоставляю только ключевые методы / состояние.

Shuffle снят с ответа Джона Скита здесь

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 
}

На самом деле, я думаю, что самая большая проблема с головоломкой состоит в том, что ее по существу два движения. Один шаг - это размещение ваших кораблей, а другой - вражеские корабли (однако сегментированная эта вторая часть может быть, кроме попытки бить часы случайным фактором, просто «запустить ваш алгоритм»). Нет никакого механизма, чтобы попытаться определить, а затем противостоять вражеской стратегии, что делает подобные конкурсы, основанные на последовательных раундах «ножниц для каменной бумаги», довольно интересными.

Кроме того, я думаю, что было бы круче, если бы вы указали игру как сетевой протокол, а затем предоставили фреймворк для реализации этого протокола на C #, а не диктовали, что все решения должны быть C #, но это только мое мнение.

EDIT: Я отменяю свой первоначальный момент, так как я недостаточно читал правила соревнований.


Одно секундное общее время игры зависит от машины. Как только вторая стоимость операций ЦП будет отличаться на моей машине по сравнению с турнирной машиной. Если я оптимизирую алгоритм Battle Ship, чтобы использовать наибольшее время процессора в течение 1 секунды, тогда он запускается на более медленной турнирной машине, он всегда будет проигрывать.

Я не уверен, как обойти это ограничение рамки, но его нужно решить.

...

Одна идея состоит в том, чтобы делать то , что было сделано в этом конкурсе http://www.bcsstudentcontest.com/ /

И иметь максимальное время за ход, а не максимальное общее игровое время. Таким образом, я мог бы ограничить алгоритмы, чтобы они соответствовали знанию времени поворота. Игра может длиться от 50 до 600 + оборотов, если мой алгоритм управляет своим полным игровым временем, он может не дать достаточно времени, чтобы сделать свою лучшую работу, или это может дать слишком много времени и проиграть. Очень сложно управлять общим временем игры в рамках алгоритма Battleship.

Я бы предложил изменить правила, чтобы ограничить время поворота, а не общее игровое время.

редактировать

Если бы я написал алгоритм, который перечисляет все возможные снимки, а затем оценивает их, то снимает высший рейтинг. Для создания всех возможных снимков потребуется слишком много времени, поэтому я позволю алгоритму работать некоторое время, а затем останавливать его.

Если бы существовал поворот на основе лимита, я мог бы позволить алгоритму работать в течение 0,9 секунд и вернуть самый высокий рейтинг выстрела, и хорошо иметь время поворота.

Если мне ограничено общее игровое время в одну секунду, будет сложно определить, как долго алгоритм должен работать на каждый ход. Я хочу максимально увеличить время моего процессора. Если игра длилась 500 раундов, я мог бы ограничить каждый ход до 0,002 секунды, но если игра длилась 100 раундов, я мог бы дать каждому обороту 0.01 секунды времени процессора.

Было бы непрактично, если бы алгоритм использовал полу-исчерпывающий поиск пространства выстрела, чтобы найти лучший снимок с текущим ограничением.

1 секунда общего игрового времени ограничивает тип алгоритмов, которые можно эффективно использовать для участия в игре.


Это о лучшем, что я мог бы собрать в свободное время, а это не существует. Существует определенная статистика по игре и совпадению, так как я настраивал основную функцию на цикл и непрерывно запускал 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();
        }
    }
}

Эта логика ближе всего к тому, что мне пришлось бить Dreadnought, выиграв около 41% отдельных игр. (На самом деле он выиграл одно совпадение со счетом от 52 до 49.) Как ни странно, этот класс не работает также с FarnsworthOpponent как более ранняя версия, которая была намного менее продвинута.





artificial-intelligence