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

Морской бой!

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

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

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

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

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

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

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

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

  1. Дух соревнований – найти лучший алгоритм Битвы.
  2. Все, что считается против духа конкуренции, будет основанием для дисквалификации.
  3. Препятствие противнику противоречит духу соревнования.
  4. Многопоточность может использоваться при следующих ограничениях:
    • Не более одного streamа может работать, пока это не ваша очередь. (Хотя любое количество streamов может находиться в состоянии «приостановлено»).
    • Ни один stream не может работать с приоритетом, отличным от «Нормального».
    • Учитывая вышеуказанные два ограничения, вам гарантируется как минимум 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:
Результаты турнира:

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

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

    Страtagsи:

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

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

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

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

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

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

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

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

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

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

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

    расширение возможных состояний броненосца http://sofru.miximages.com/c%23/battleship-tree.png

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

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

    тепловая карта вероятностей для каждой неизведанной позиции http://sofru.miximages.com/c%23/battleship-probs.png

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

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

    Это не полноценный ответ, но, кажется, мало смысла загромождать реальные ответы с распространенным кодом. Таким образом, я предлагаю некоторые расширения / общие classы в духе 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 { private readonly BoardView view; public readonly int X; public readonly int Y; public T Data; public double Bias { get; set; } public Cell(BoardView 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 FoldAll(U acc, Func, U, U> trip) { return new[] { Compass.North, Compass.East, Compass.South, Compass.West } .Select(x => FoldLine(x, acc, trip)); } public U FoldLine(Compass direction, U acc, Func, 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 North { get { return view.SafeLookup(X, Y - 1); } } public Cell South { get { return view.SafeLookup(X, Y + 1); } } public Cell East { get { return view.SafeLookup(X+1, Y); } } public Cell West { get { return view.SafeLookup(X-1, Y); } } public IEnumerable> 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 : IEnumerable> { public readonly Size Size; private readonly int Columns; private readonly int Rows; private Cell[] history; public BoardView(Size size) { this.Size = size; Columns = size.Width; Rows = size.Height; this.history = new Cell[Columns * Rows]; for (int y = 0; y < Rows; y++) { for (int x = 0; x < Rows; x++) history[x + y * Columns] = new Cell(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(pX, pY, true)].Data; } set { this.history[SafeCalc(pX, pY, 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 SafeLookup(int x, int y) { int index = SafeCalc(x, y, false); if (index < 0) return null; return history[index]; } #region IEnumerable> Members public IEnumerator> GetEnumerator() { foreach (var cell in this.history) yield return cell; } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this.GetEnumerator(); } public BoardView Transform(Func transform) { var result = new BoardView(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,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 pX >= 0 && pY >= 0 && pX < size.Width && pY < size.Height; } public static bool IsLegal(this Ship ship, IEnumerable 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 (aX == bX - 1 || aX == bX + 1) && (aY == bY - 1 || aY == bY + 1); } public static bool IsTouching(this Ship ship, IEnumerable ships, Point location, ShipOrientation direction) { var temp = new Ship(ship.Length); temp.Place(location, direction); var occupied = new HashSet(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 MakeShips(params int[] lengths) { return new System.Collections.ObjectModel.ReadOnlyCollection( lengths.Select(l => new Ship(l)).ToList()); } public static IEnumerable Shuffle(this IEnumerable 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(this IEnumerable 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(IEnumerable things) { return things.ElementAt(Next(things.Count())); } public T PickBias(Func bias, IEnumerable 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!"); } } } 

    У меня нет времени прямо сейчас, чтобы написать полноценный алгоритм, но вот мысль: если ваш противник разместил суды случайно, разве вероятность размещения не была бы простым распределением по центру (5.5.5.5)? Например, возможности размещения линкора (5 единиц в длину) в измерении x находятся здесь:

     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) из центра. Пример:

     ........... ....xx... .....x..... ....xx... ........... 

    Очевидно, что к идее нужно добавить некоторую случайность, но я думаю, что чисто математически это путь.

    Ничего сложного, кроме того, что я придумал. Он бьет случайного противника в 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 HitShots = new LinkedList(); private LinkedList Shots = new LinkedList(); private List PatternShots = new List(); 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 => sX == pX && sY == pY).Any()); if (pX < 0 | pY<0) InvalidShot = true; if (pX >= gameSize.Width | pY >= gameSize.Height) InvalidShot = true; return InvalidShot; } private Point FireDirectedShot(Direction? direction, Point p) { ShotDirection = (Direction)direction; switch (ShotDirection) { case Direction.Up: pY--; break; case Direction.Down: p.Y++; break; case Direction.Left: pX--; 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 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() { } } } 

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

    Некоторые комментарии о двигателе соревнований:

    Параметры NewGame:

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

    Суда закрыты:

    Я не вижу причин, по которым class Ship запечатан. Среди других основных вещей я бы хотел, чтобы у кораблей было имя, поэтому я могу выводить такие сообщения, как («Ты потопил мой {0}», ship.Name); , У меня тоже есть другие расширения, поэтому я думаю, что корабль должен быть наследуемым.

    Ограничения времени:

    Хотя ограничение времени в 1 секунду имеет смысл для правила турнира, оно полностью противоречит отладке. BattleshipCompetition должен иметь легкую настройку, чтобы игнорировать нарушения времени, чтобы помочь с разработкой / отладкой. Я также предложил бы исследовать System.Diagnostics.Process :: UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime для более точного представления о том, сколько времени используется.

    Потолочные суда:

    Текущий API сообщает вам, когда вы потопили корабль oppenent:

     ShotHit(Point shot, bool sunk); 

    но не тот корабль, который вы потонули! Я считаю, что это часть правил человеческих сражений, которые вы обязаны объявлять «Ты потопил мой броненосец!». (или эсминец, или суб и т. д.).

    Это особенно важно, когда ИИ пытается вымыть корабли, которые торчат друг против друга. Я хотел бы запросить изменение API:

     ShotHit(Point shot, Ship ship); 

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

    Обновлено 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 opponentsBoard = new BoardView(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(size); this.gridOddEven = rand.Pick(new[] { 0, 1 }); } public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection ships) { BoardView board = new BoardView(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 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 { private readonly BoardView view; public readonly int X; public readonly int Y; public T Data; public double Bias { get; set; } public Cell(BoardView 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 FoldAll(U acc, Func, U, U> trip) { return new[] { Compass.North, Compass.East, Compass.South, Compass.West } .Select(x => FoldLine(x, acc, trip)); } public U FoldLine(Compass direction, U acc, Func, 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 North { get { return view.SafeLookup(X, Y - 1); } } public Cell South { get { return view.SafeLookup(X, Y + 1); } } public Cell East { get { return view.SafeLookup(X + 1, Y); } } public Cell West { get { return view.SafeLookup(X - 1, Y); } } public IEnumerable> 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 : IEnumerable> { public readonly Size Size; private readonly int Columns; private readonly int Rows; private Cell[] history; public BoardView(Size size) { this.Size = size; Columns = size.Width; Rows = size.Height; this.history = new Cell[Columns * Rows]; for (int y = 0; y < Rows; y++) { for (int x = 0; x < Rows; x++) history[x + y * Columns] = new Cell(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(pX, pY, true)].Data; } set { this.history[SafeCalc(pX, pY, 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 SafeLookup(int x, int y) { int index = SafeCalc(x, y, false); if (index < 0) return null; return history[index]; } #region IEnumerable> Members public IEnumerator> GetEnumerator() { foreach (var cell in this.history) yield return cell; } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this.GetEnumerator(); } public BoardView Transform(Func transform) { var result = new BoardView(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, 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(IEnumerable things) { return things.ElementAt(Next(things.Count())); } public T PickBias(Func bias, IEnumerable 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 pX >= 0 && pY >= 0 && pX < size.Width && pY < size.Height; } public static bool IsLegal(this Ship ship, IEnumerable 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 (aX == bX - 1 || aX == bX + 1) && (aY == bY - 1 || aY == bY + 1); } public static bool IsTouching(this Ship ship, IEnumerable ships, Point location, ShipOrientation direction) { var temp = new Ship(ship.Length); temp.Place(location, direction); var occupied = new HashSet(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 MakeShips(params int[] lengths) { return new System.Collections.ObjectModel.ReadOnlyCollection( lengths.Select(l => new Ship(l)).ToList()); } public static IEnumerable Shuffle(this IEnumerable 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(this IEnumerable things, Battleship.ShuggyCoUk.Simple.Rand rand) { int count = things.Count(); if (count == 0) return default(T); return things.ElementAt(rand.Next(count)); } } 

    }

    This is about the best that I could put together in my free time, which is about non-existent. There is some game and match tallying stats going on, as I set up the main function to loop and continuously run the BattleshipCompetition until I pressed a key.

     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 scanShots; List 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(); nextShots = new List(); 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 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 scanShots = new List(); 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 scanShots2 = new List(); 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 (pX >= 0 && board[pX, pY] == ShotResult.UNKNOWN) { ctr++; pX--; } // spaces to the right p = new Point(x + 1, y); while (pX < gameSize.Width && board[pX, pY] == ShotResult.UNKNOWN) { ctr++; p.X++; } // spaces to the top p = new Point(x, y - 1); while (pY >= 0 && board[pX, pY] == ShotResult.UNKNOWN) { ctr++; pY--; } // spaces to the bottom p = new Point(x, y + 1); while (pY < gameSize.Height && board[pX, pY] == 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(); } } } 

    This logic is the closest that I had to beating Dreadnought, winning about 41% of the individual games. (It actually did win one match by a count of 52 to 49.) Oddly enough, this class does not do as well against FarnsworthOpponent as an earlier version that was much less advanced.

    My computer is being repaired by dell right now, but this is where i was at last week:

     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 nextShots; Queue 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(); this.scanShots = new Queue(); 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 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 possible = new List(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 => pX != shot.X); //} //else //{ // this.nextShots.RemoveAll(p => pY != shot.Y); //} } else { shot = new Point(-1, -1); } return shot; } private void addToNextShots(Point p) { if (!this.nextShots.Contains(p) && pX >= 0 && pX < this.gameSize.Width && pY >= 0 && pY < this.gameSize.Height) { if (this.board[pX, pY] == '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; } } } 

    If you are brute forcing your analysis then you may find the mechanics of the supplied RandomOpponent highly inefficient. It allows itself to reselect already targeted locations and lets the framework force it to repeat till it hits one it hasn’t touched yet or the timelimit per move expires.

    This opponent has similar behaviour (the effective placement distribution is the same) it just does the sanity checking itself and only consumes one random number generation per call (amortized)).

    This uses the classes in my extensions/library answer and I only supply the key methods/state.

    Shuffle is lifted from Jon Skeet’s answer here

     class WellBehavedRandomOpponent : IBattleShipOpponent { Rand rand = new Rand(); List guesses; int nextGuess = 0; public void PlaceShips(IEnumerable ships) { BoardView board = new BoardView(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(size); this.guesses = new List( board.Select(x => x.Location).Shuffle(rand)); nextGuess = 0; } public System.Drawing.Point GetShot() { return guesses[nextGuess++]; } // empty methods left out } 

    I’m not going to be able to participate, but here’s the algorithm I’d implement if I had time:

    First, when I detect a hit I do not pursue the rest of the ship immediately – I build a table of ship locations and figure out whether I’ve hit all five at least once before starting to fully sink them. (Note that this is a bad policy for the multiple shot variant – see comments)

    1. Hit the center (see final note below – ‘center’ is just a convenience for description)
    2. Hit the spot 4 to the right of the center
    3. Hit the spot 1 down and one to the right of the center
    4. Hit the spot four to the right of the previous hit
    5. Continue in that pattern (should end up with diagonal lines separated by 3 spaces filling the board) This should hit all 4 and 5 length boats, and a statistically large number of 3 and 2 boats.

    6. Start randomly hitting spots inbetween the diagonals, this will catch the 2 and 3 length boats that haven’t already been noticed.

    Once I have detected 5 hits, I’d determine if the 5 hits are on separate boats. This is relatively easy by making a few more shots near locations where two hits are on the same horizontal or vertical line and are within 5 locations of each other (might be two hits on the same boat). If they are separate boats then continue to sink all the ships. If they are found to be the same boat, continue the filling patterns above until all 5 boats are located.

    This algorithm is a simple filling algorithm. The key features are that it does not waste time sinking ships it knows about when there are still ships it’s unaware of, and it doesn’t use an inefficient filling pattern (ie, a fully random pattern would be wasteful).

    Заключительные замечания:

    A) “Center” is a random starting point on the board. This eliminates the primary weakness of this algorithm. B) While the description indicates drawing diagonals immediately from the start, ideally the algorithm merely shoots at ‘random’ locations that are along those diagonals. This helps prevent the competitor from timing how long until their ships are hit by predictable patterns.

    This describes a ‘perfect’ algorithm in that it’ll get all the ships in under (9×9)/2+10 shots.

    However, it can be improved significantly:

    Once a ship is hit, identify its size before doing the ‘internal’ diagonal lines. You may have found the 2 ship, in which case the internal diagonals can be simplified to find the 3 size ships more quickly.

    Identify stages in the game and act accordingly. This algorithm may be good up to a certain point in the game, but other algorithms may yield better benefits as part of the endgame. Also, if the other player is very close to defeating you, another algorithm might work better – for instance a high risk algorithm might fail more often, but when it works it works quickly and you may beat your opponent who is closer to winning than you.

    Identify the play style of the competitor – it may give you clues as to how they plan ship placement (ie, chances are good that their own algorithm most quickly identifies how they place their own ships – if the only tool you have is a hammer, everything looks like a nail)

    -Адам

    My entry.

    Nothing terribly special, and I didn’t get time to add all the good ideas I had.

    But it seems to play fairly well. We’ll see how it does in competition:

    (put this in file Missouri.cs and added to project.)

     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(); } // IBattleship::PlaceShips public void PlaceShips(ReadOnlyCollection ships) { HunterBoard board; targetBoards = new List(); 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(pY=0; pY 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 ([email protected])"; private Size size; private List targetBoards; private ShotBoard shotBoard; private Stack 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(pX, pX); vertExtent = new Extent(pY, pY); } 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 == pX) // New hit in the vertical direction { vertExtent.Min = Math.Min(vertExtent.Min, pY); vertExtent.Max = Math.Max(vertExtent.Max, pY); } else if (hit.Y == pY) { horzExtent.Min = Math.Min(horzExtent.Min, pX); horzExtent.Max = Math.Max(horzExtent.Max, pX); } } public Point[] GetNextTargets() { List bors = new List(); Point p; p = new Point(hit.X, vertExtent.Min-1); while (pY >= 0 && Player.theShotBoard[p] == Shot.Hit) { if (Player.theShotBoard[p] == Shot.Miss) { break; // Don't add p to the List 'bors. } --pY; } if (pY >= 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 (pY < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.Hit) { if (Player.theShotBoard[p] == Shot.Miss) { break; // Don't add p to the List 'bors. } ++pY; } if (pY < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.None) { bors.Add(p); } //------------------- p = new Point(horzExtent.Min-1, hit.Y); while (pX >= 0 && Player.theShotBoard[p] == Shot.Hit) { if (Player.theShotBoard[p] == Shot.Miss) { break; // Don't add p to the List 'bors. } --pX; } if (pX >= 0 && Player.theShotBoard[p] == Shot.None) { bors.Add(p); } //------------------- p = new Point(horzExtent.Max+1, hit.Y); while (pX < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.Hit) { if (Player.theShotBoard[p] == Shot.Miss) { break; // Don't add p to the List 'bors. } ++pX; } if (pX < 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[pX, pY]; } set { grid[pX, pY] = 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 max)? grid[x,y] : max; } } for(int y=0; y 0) { return false; } } return true; } public override String ToString() { String output = ""; String horzDiv = " +----+----+----+----+----+----+----+----+----+----+\n"; String disp; int x,y; output += " ABCDEFGHIJ \n" + horzDiv; for(y=0; y 

    This is not minimax. Actually after placing the ships, can’t each player play on its own, resulting in a number of turns it took him to sink every opponent ship? The one that took less turns wins.

    I don’t think that there are any good general strategies beyond sinking hit ships and trying to minimize the number of shots to cover the remaining possible places where ships might hide.

    Of course there might be counter-strategies for anything that’s not random. But I don’t think that there are strategies that are good against all possible players.

    Actually, I think the biggest problem with the puzzle is that its essentially two moves. One move is placing your ships, the other is finding the enemy ships (however segmented that second part might be, aside from trying to beat a clock with a random factor, its just ‘run your algorithm’). There’s no mechanism to try to determine and then counter an enemy strategy, which is what makes similar competitions based around successive rounds of “rock paper scissors” pretty interesting.

    Also, I think it would be cooler if you specified the game as a network protocol and then provided the framework to implement that protocol in C#, rather than dictate that all solutions should be C#, but that’s just my opinion.

    EDIT: I rescind my initial point, since I didn’t read the competition rules carefully enough.

    I always liked starting in the middle and spiraling away from that one point leaving no more than 1 blank space between any other points to account for that goddam sub… the space between shots was dependent on which ships were sunk. if the B-ship was last, the shots only had to leave 4 spaces in between to minimize wasted shots

    There was a similar competition run by Dr James Heather of The University of Surrey on behalf of the British Computer Society.

    Limitations were placed on resources – namely maximum processor time per turn, no state could be stored between moves, maximum heap size imposed. To limit time the AI could submit a move at any point within the time slot and would be asked for a move upon termination of the turn.

    Very interesting – see more at: http://www.bcsstudentcontest.com/

    Might give you some more ideas.

    As it is, the solution opens and runs with no modification in monodevelop in ubuntu 9.10 linux

    Вы написали:

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

    please define “against the spirit of the competition” and “interfering with an opponent”?

    Also – to simplify, I recommend that you:

    • disallow using CPU at all during opponent’s CPU slot.
    • disallow thread parallelism and instead give more CPU seconds on a single thread. This will simplify programming of AI and won’t hurt anyone who is CPU/memory-bound anyway.

    PS – a question for the CS post-docs lurking here: isn’t this game solvable (ie is there a single, best strategy?). yes, the board size and number of steps makes minimax et al mandatory, but still I have to wonder… it’s far from Go and chess in complexity.

    I predict that the person who manages to reverse engineer their opponents random seed and call pattern will win.

    Not sure how likely that is though.

    It would also, presumably, be possible to run a series of these with variations on the game.

    Adding in things like a 3d plane or being able to move a single ship instead of shoot for a turn would probably change the game a fair bit.

    The one second total game time is machine specific. Once second worth of CPU operations will be different on my machine compared to the tournament machine. If I optimize the Battle Ship algorithm to utilize the most CPU time within 1 second, then it is run on a possible slower tournament machine, it will always lose.

    I am not sure how to get around this limitation of the framework, but it should be addressed.

    One idea is to do what was done in this competition http://www.bcsstudentcontest.com /

    And have a maximum time per turn as opposed to maximum total game time. This way I could limit the algorithms to fit within a know turn time. A game might last 50 to 600+ turns, if the my algorithm manages its total game time, it might not give the enough time to do its best job or it could give too much time and lose. It is very hard to manage the total game time within the Battleship algorithm.

    I would suggest changing the rules to limit the turn time not the total game time.

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

    If I wrote an algorithm that enumerates all possible shots and then ranks them, then takes the highest ranking shot. It would take too long to generate all possible shots, so I would let the algorithm run for a certain amount of time then stop it.

    If there was a turn based limit, I could let the algorithm run for 0.9 seconds and return the highest ranking shot, and be well withing the turn time limit.

    If I am limited to total game time of one second, it will be difficult to determine how long the algorithm should run for each turn. I will want to maximum my CPU time. If a game lasted 500 round I could limit each turn to 0.002 seconds, but if a game lasted 100 rounds I could give each turn 0.01 seconds of CPU time.

    It would be impractical for a algorithm to use an semi-exhaustive search of the shot space to find the best shot with the current limitation.

    The 1 second total game time is limiting the type of algorithms that can be effectively used to compete in the game.

    I’m copping out here by not putting actual code in – but I will hazard some general observations:

    • Since all ships are at least 2 cells in size, you can use an optimization I saw on an implementation of the game in Space Quest V – which only fires at alternate cells in a diamond pattern while it is “seeking” a target. This eliminates half the squares, while still guaranteeing that you will find all the ships eventually.
    • A random firing pattern when seeking targets will statistically yield the best results over many games.

    ![Probability Density][1]enter image description her

    ![enter image description here][2]

    I experimented with comparing the results of randon shooting vs a dumb hunt/target and finally a sophisticated search.

    The best solution appears to be to create a probability density function for the how likely any individual square is used by the remaining ships, and aim with the square with the highest value.

    You can see my results here enter link description here

    “Battleship” is what’s known as a classic computer science NP-complete problem.

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

    (look for Battleship – it’s there, under games and puzzles)

    Давайте будем гением компьютера.