Какой ИИ линкора лучший?
https://stackoverflow.com/questions/1631414
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Линкор!
Еще в 2003 году (когда мне было 17) я участвовал в соревнованиях по ИИ линкора соревнование по кодированию.Несмотря на то, что я проиграл тот турнир, я получил массу удовольствия и многому научился.
Теперь я хотел бы возродить это соревнование в поисках лучшего ИИ линкора.
Вот фреймворк, теперь размещенный на Bitbucket.
Победитель получит +450 репутации! Соревнования пройдут начиная с 17 ноября 2009 г..Никакие записи или изменения позднее 0 часов 17 числа не принимаются.(Центральное стандартное время) Отправьте свои записи рано, чтобы вы не упустили свою возможность!
Чтобы сохранить это ЦЕЛЬ, пожалуйста, следуйте духу конкурса.
Правила игры:
- Игра ведется на сетке 10x10.
- Каждый участник разместит на своей сетке каждый из 5 кораблей (длиной 2, 3, 3, 4, 5).
- Никакие корабли не могут перекрываться, но они могут находиться рядом.
- Затем участники по очереди стреляют по противнику одиночными выстрелами.
- Вариант игры позволяет производить несколько выстрелов за залп, по одному на каждый выживший корабль.
- Противник уведомит участника, если выстрел попадет в цель, попадет в цель или промахнется.
- Игра заканчивается, когда все корабли любого игрока потоплены.
Правила конкурса:
- Суть конкурса — найти лучший алгоритм «Морской бой».
- Все, что будет сочтено противоречащим духу соревнования, будет основанием для дисквалификации.
- Вмешательство в дела соперника противоречит духу соревнования.
- Многопоточность может использоваться при следующих ограничениях:
- Пока не ваша очередь, может выполняться не более одного потока.(Однако любое количество потоков может находиться в состоянии «Приостановлено»).
- Ни один поток не может выполняться с приоритетом, отличным от «Нормальный».
- Учитывая два вышеуказанных ограничения, вам будет гарантировано как минимум 3 выделенных ядра ЦП во время вашего хода.
- Каждому участнику в основном потоке выделяется ограничение в 1 секунду процессорного времени на игру.
- Истечение времени приводит к проигрышу текущей игры.
- Любое необработанное исключение приведет к проигрышу текущей игры.
- Доступ к сети и доступ к диску разрешены, но ограничения по времени могут показаться вам слишком непомерными.Однако было добавлено несколько методов установки и демонтажа, чтобы уменьшить временные затраты.
- Код должен быть размещен при переполнении стека в качестве ответа или, если он слишком велик, связан с ним.
- Максимальный общий размер (несжатый) записи — 1 МБ.
- Официально .Net 2.0/3.5 — единственное требование фреймворка.
- Ваша запись должна реализовывать интерфейс IBattleshipOpComponent.
Оценка:
- Лучшая 51 игра из 101 – победитель матча.
- Все участники будут играть друг против друга по круговой системе.
- Затем лучшая половина участников сыграет турнир с двойным выбыванием, чтобы определить победителя.(На самом деле наименьшая степень двойки, которая больше или равна половине.)
- Я буду использовать ТурнирАпи рамки турнира.
- Результаты будут опубликованы здесь.
- Если вы подадите более одной заявки, только ваша работа с лучшим результатом будет иметь право на получение двойного балла.
Удачи!Веселиться!
РЕДАКТИРОВАТЬ 1:
Благодаря Фрид, кто нашел ошибку в Ship.IsValid функция.Это исправлено.Загрузите обновленную версию фреймворка.
РЕДАКТИРОВАТЬ 2:
Поскольку существует значительный интерес к сохранению статистики на диске и тому подобному, я добавил несколько несинхронизированных событий установки и отключения, которые должны обеспечить необходимую функциональность.Это полуразрушающее изменение.То есть:интерфейс был изменен для добавления функций, но для них не требуется тело.Загрузите обновленную версию фреймворка.
РЕДАКТИРОВАТЬ 3:
Исправление ошибки 1: GameWon и GameLost вызывали только в случае тайм-аута.
Исправление ошибки 2:Если бы движок останавливал каждую игру, соревнование никогда бы не закончилось.
Загрузите обновленную версию фреймворка.
РЕДАКТИРОВАТЬ 4:
Результаты турнира:
Решение
Я поддерживаю предложение проводить больше игр за матч.Провести 50 игр — это просто подбросить монетку.Мне нужно было провести 1000 игр, чтобы получить хоть какое-то разумное различие между алгоритмами тестирования.
Скачать Дредноут 1.2.
Стратегии:
отслеживайте все возможные позиции кораблей, имеющих >0 попаданий.Список никогда не превышает ~30 тысяч, поэтому его можно хранить точно, в отличие от списка всех возможных позиций для всех кораблей (который очень велик).
Алгоритм 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<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() { }
}
}
Вот противник, против которого можно играть:
Вместо использования стратегии, основанной на фиксированной геометрии, я подумал, что было бы интересно попытаться оценить основные вероятности что в любом конкретном неисследованном пространстве находится корабль.
Чтобы сделать это правильно, вы должны изучить все возможные конфигурации кораблей, которые соответствуют вашему текущему взгляду на мир, а затем вычислить вероятности на основе этих конфигураций.Вы можете думать об этом как об исследовании дерева:
расширение возможных состояний линкоров http://natekohl.net/media/battleship-tree.png
Рассмотрев все листья этого дерева, которые совпадают с тем, что вы знаете о мире. (например.корабли не могут перекрываться, все пораженные клетки должны быть кораблями и т. д.) вы можете подсчитать, как часто корабли появляются в каждой неисследованной позиции, чтобы оценить вероятность того, что корабль там находится.
Это можно представить в виде тепловой карты, где в горячих точках с большей вероятностью могут находиться корабли:
Что мне нравится в этом соревновании по линкору, так это то, что дерево выше почти достаточно маленькое, чтобы перебрать такой алгоритм.Если для каждого из 5 кораблей существует ~150 возможных позиций, это 150.5 = 75 миллиардов возможностей.И это число становится только меньше, особенно если вы можете уничтожать целые корабли.
Противник, о котором я говорил выше, не исследует все дерево;75 миллиардов по-прежнему слишком велики, чтобы уместиться менее чем за секунду.Однако он пытается оценить эти вероятности с помощью нескольких эвристик.
Это не полноценный ответ, но, похоже, нет смысла загромождать реальные ответы общим кодом.Поэтому я представляю некоторые расширения/общие классы в духе открытого исходного кода.Если вы их используете, измените пространство имен, иначе попытка скомпилировать все в одну 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!");
}
}
}
У меня сейчас нет времени писать полноценный алгоритм, но есть мысль:если бы ваш противник разместил корабли случайным образом, не была бы вероятность размещения простым распределением с центром в (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) из центра.Бывший:
...........
....x.x....
.....x.....
....x.x....
...........
Очевидно, к этой идее необходимо добавить некоторую случайность, но я думаю, что чисто математически это правильный путь.
Ничего сложного, но вот что я придумал.Он побеждает случайного противника в 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() { }
}
}
Немного сжато, чтобы занимать минимум места и при этом оставаться читабельным.
Несколько комментариев о конкурсном движке:
Параметры новой игры:
Если IBattleshipOppent::NewGame предназначен для настройки перед игрой и принимает размер доски, он также должен принять список кораблей и их соответствующие размеры.Нет смысла допускать переменный размер борта без учета изменяющихся конфигураций корабля.
Корабли опломбированы:
Я не вижу причин, по которым класс Корабль запечатан.Помимо прочего, я хотел бы, чтобы у кораблей было имя, чтобы я мог выводить такие сообщения, как («Вы потопили мой {0}», Ship.Name);.Я имею в виду и другие расширения, поэтому считаю, что Ship должен передаваться по наследству.
Ограничения по времени:
Хотя ограничение по времени в 1 секунду имеет смысл для правил турнира, оно полностью мешает отладке.BattleshipCompetition должен иметь простую настройку, позволяющую игнорировать нарушения времени, чтобы облегчить разработку/отладку.Я бы также предложил изучить System.Diagnostics.Process::UserProcessorTime/Privileged ProcessorTime/TotalProcessorTime для более точного представления о том, сколько времени используется.
Затонувшие корабли:
Текущий API сообщает вам, когда вы потопили корабль противника:
ShotHit(Point shot, bool sunk);
но нет который корабль, ты затонул!Я считаю это частью правил человеческого батлиста, которые вы должны объявить: «Вы потопили мой линкор!» (или разрушитель, или саб и т. Д.).
Это особенно важно, когда ИИ пытается спугнуть корабли, которые сталкиваются друг с другом.Я хотел бы запросить изменение API на:
ShotHit(Point shot, Ship ship);
Если корабль не равно нулю, это означает, что выстрел был тонущим, и вы знаете, какой корабль вы потопили и как долго это продолжалось.Если выстрел был непотопляющим, то корабль равен нулю, и у вас нет дополнительной информации.
Кроссфаер обновлен.Я знаю, что он не может конкурировать с Фарнсвортом или Дредноутом, но он намного быстрее, чем последний, и с ним легко играть, если кто-то захочет попробовать.Это зависит от текущего состояния моих библиотек, включенных сюда для упрощения использования.
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));
}
}
}
Это лучшее, что я мог собрать в свободное время, которого практически нет.Происходит некоторая статистика игр и матчей, поскольку я настроил основную функцию на циклическое и непрерывное выполнение BattleshipCompetition, пока я не нажму клавишу.
namespace Battleship
{
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
public class BP7 : IBattleshipOpponent
{
public string Name { get { return "BP7"; } }
public Version Version { get { return this.version; } }
Random rand = new Random();
Version version = new Version(0, 7);
Size gameSize;
List<Point> scanShots;
List<NextShot> nextShots;
int wins, losses;
int totalWins = 0;
int totalLosses = 0;
int maxWins = 0;
int maxLosses = 0;
int matchWins = 0;
int matchLosses = 0;
public enum Direction { VERTICAL = -1, UNKNOWN = 0, HORIZONTAL = 1 };
Direction hitDirection, lastShotDirection;
enum ShotResult { UNKNOWN, MISS, HIT };
ShotResult[,] board;
public struct NextShot
{
public Point point;
public Direction direction;
public NextShot(Point p, Direction d)
{
point = p;
direction = d;
}
}
public struct ScanShot
{
public Point point;
public int openSpaces;
public ScanShot(Point p, int o)
{
point = p;
openSpaces = o;
}
}
public void NewGame(Size size, TimeSpan timeSpan)
{
this.gameSize = size;
scanShots = new List<Point>();
nextShots = new List<NextShot>();
fillScanShots();
hitDirection = Direction.UNKNOWN;
board = new ShotResult[size.Width, size.Height];
}
private void fillScanShots()
{
int x;
for (x = 0; x < gameSize.Width - 1; x++)
{
scanShots.Add(new Point(x, x));
}
if (gameSize.Width == 10)
{
for (x = 0; x < 3; x++)
{
scanShots.Add(new Point(9 - x, x));
scanShots.Add(new Point(x, 9 - x));
}
}
}
public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection<Ship> ships)
{
foreach (Ship s in ships)
{
s.Place(
new Point(
rand.Next(this.gameSize.Width),
rand.Next(this.gameSize.Height)),
(ShipOrientation)rand.Next(2));
}
}
public Point GetShot()
{
Point shot;
if (this.nextShots.Count > 0)
{
if (hitDirection != Direction.UNKNOWN)
{
if (hitDirection == Direction.HORIZONTAL)
{
this.nextShots = this.nextShots.OrderByDescending(x => x.direction).ToList();
}
else
{
this.nextShots = this.nextShots.OrderBy(x => x.direction).ToList();
}
}
shot = this.nextShots.First().point;
lastShotDirection = this.nextShots.First().direction;
this.nextShots.RemoveAt(0);
return shot;
}
List<ScanShot> scanShots = new List<ScanShot>();
for (int x = 0; x < gameSize.Width; x++)
{
for (int y = 0; y < gameSize.Height; y++)
{
if (board[x, y] == ShotResult.UNKNOWN)
{
scanShots.Add(new ScanShot(new Point(x, y), OpenSpaces(x, y)));
}
}
}
scanShots = scanShots.OrderByDescending(x => x.openSpaces).ToList();
int maxOpenSpaces = scanShots.FirstOrDefault().openSpaces;
List<ScanShot> scanShots2 = new List<ScanShot>();
scanShots2 = scanShots.Where(x => x.openSpaces == maxOpenSpaces).ToList();
shot = scanShots2[rand.Next(scanShots2.Count())].point;
return shot;
}
int OpenSpaces(int x, int y)
{
int ctr = 0;
Point p;
// spaces to the left
p = new Point(x - 1, y);
while (p.X >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.X--;
}
// spaces to the right
p = new Point(x + 1, y);
while (p.X < gameSize.Width && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.X++;
}
// spaces to the top
p = new Point(x, y - 1);
while (p.Y >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.Y--;
}
// spaces to the bottom
p = new Point(x, y + 1);
while (p.Y < gameSize.Height && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.Y++;
}
return ctr;
}
public void NewMatch(string opponenet)
{
wins = 0;
losses = 0;
}
public void OpponentShot(Point shot) { }
public void ShotHit(Point shot, bool sunk)
{
board[shot.X, shot.Y] = ShotResult.HIT;
if (!sunk)
{
hitDirection = lastShotDirection;
if (shot.X != 0)
{
this.nextShots.Add(new NextShot(new Point(shot.X - 1, shot.Y), Direction.HORIZONTAL));
}
if (shot.Y != 0)
{
this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y - 1), Direction.VERTICAL));
}
if (shot.X != this.gameSize.Width - 1)
{
this.nextShots.Add(new NextShot(new Point(shot.X + 1, shot.Y), Direction.HORIZONTAL));
}
if (shot.Y != this.gameSize.Height - 1)
{
this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y + 1), Direction.VERTICAL));
}
}
else
{
hitDirection = Direction.UNKNOWN;
this.nextShots.Clear(); // so now this works like gangbusters ?!?!?!?!?!?!?!?!?
}
}
public void ShotMiss(Point shot)
{
board[shot.X, shot.Y] = ShotResult.MISS;
}
public void GameWon()
{
wins++;
}
public void GameLost()
{
losses++;
}
public void MatchOver()
{
if (wins > maxWins)
{
maxWins = wins;
}
if (losses > maxLosses)
{
maxLosses = losses;
}
totalWins += wins;
totalLosses += losses;
if (wins >= 51)
{
matchWins++;
}
else
{
matchLosses++;
}
}
public void FinalStats()
{
Console.WriteLine("Games won: " + totalWins.ToString());
Console.WriteLine("Games lost: " + totalLosses.ToString());
Console.WriteLine("Game winning percentage: " + (totalWins * 1.0 / (totalWins + totalLosses)).ToString("P"));
Console.WriteLine("Game losing percentage: " + (totalLosses * 1.0 / (totalWins + totalLosses)).ToString("P"));
Console.WriteLine();
Console.WriteLine("Matches won: " + matchWins.ToString());
Console.WriteLine("Matches lost: " + matchLosses.ToString());
Console.WriteLine("Match winning percentage: " + (matchWins * 1.0 / (matchWins + matchLosses)).ToString("P"));
Console.WriteLine("Match losing percentage: " + (matchLosses * 1.0 / (matchWins + matchLosses)).ToString("P"));
Console.WriteLine("Match games won high: " + maxWins.ToString());
Console.WriteLine("Match games lost high: " + maxLosses.ToString());
Console.WriteLine();
}
}
}
Эта логика наиболее близка к победе над Дредноутом, выиграв около 41% отдельных игр.(Он действительно выиграл один матч со счетом 52 к 49.) Как ни странно, этот класс не так эффективен против FarnsworthOppond, как более ранняя версия, которая была гораздо менее продвинутой.
Мой компьютер сейчас ремонтируется в 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; }
}
}
Если вы проводите анализ грубо, то механика предоставленного RandomOpComponent может оказаться крайне неэффективной.Он позволяет себе повторно выбирать уже намеченные местоположения и позволяет системе заставлять его повторяться до тех пор, пока не достигнет того, которого еще не коснулся, или пока не истечет лимит времени на ход.
Этот оппонент имеет аналогичное поведение (эффективное распределение мест такое же), он просто выполняет проверку работоспособности сам и потребляет только одну генерацию случайных чисел за вызов (амортизировано)).
При этом используются классы из моего ответа на расширения/библиотеку, и я предоставляю только ключевые методы/состояние.
Перетасовка снята с Ответ Джона Скита здесь
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
}
Я не смогу участвовать, но вот алгоритм, который я бы реализовал, если бы у меня было время:
Во-первых, когда я обнаруживаю попадание, я не преследую сразу остальную часть корабля — я строю таблицу местоположений кораблей и выясняю, поразил ли я все пять хотя бы один раз, прежде чем начать их полностью топить.(Обратите внимание, что это плохая политика для варианта с несколькими выстрелами - см. комментарии)
- Нажмите на центр (см. последнее примечание ниже — «центр» — это просто удобство описания)
- Попадите в точку 4 справа от центра.
- Попадите в точку 1 вниз и одну справа от центра.
- Попадите в точку на четыре правее предыдущего удара.
Продолжайте в том же порядке (должны получиться диагональные линии, разделенные тремя пробелами, заполняющими доску). Это должно затронуть все лодки длиной 4 и 5, а также статистически большое количество лодок 3 и 2.
Начните случайным образом попадать в точки между диагоналями, это позволит поймать лодки длиной 2 и 3, которые еще не были замечены.
Как только я обнаружил 5 попаданий, я бы определил, происходят ли эти 5 попаданий на отдельных лодках.Это относительно легко сделать, сделав еще несколько выстрелов рядом с местами, где два попадания находятся на одной горизонтальной или вертикальной линии и находятся в пределах 5 мест друг от друга (это могут быть два попадания в одну лодку).Если это отдельные лодки, то продолжайте топить все корабли.Если окажется, что это одна и та же лодка, продолжайте выполнять указанные выше схемы заполнения, пока не будут найдены все 5 лодок.
Этот алгоритм представляет собой простой алгоритм заполнения.Ключевые особенности заключаются в том, что он не тратит время на затопление известных ему кораблей, когда еще есть корабли, о которых он не знает, и не использует неэффективный шаблон заполнения (т. е. полностью случайный шаблон был бы расточительным).
Заключительные замечания:
А) «Центр» — случайная начальная точка на доске.Это устраняет основной недостаток данного алгоритма.Б) Хотя в описании указано рисование диагоналей сразу с самого начала, в идеале алгоритм просто стреляет в «случайные» места, расположенные вдоль этих диагоналей.Это помогает не дать конкуренту определить, сколько времени пройдет до того, как его корабли столкнутся с предсказуемыми ситуациями.
Это описывает «идеальный» алгоритм, позволяющий поразить все корабли менее чем (9x9)/2+10 выстрелами.
Однако его можно значительно улучшить:
Как только корабль будет поражен, определите его размер, прежде чем проводить «внутренние» диагональные линии.Возможно, вы нашли корабль 2-го размера, и в этом случае внутренние диагонали можно упростить, чтобы быстрее найти корабли 3-го размера.
Определите этапы игры и действуйте соответственно.Этот алгоритм может быть хорош до определенного момента в игре, но другие алгоритмы могут принести больше преимуществ в финале.Кроме того, если другой игрок очень близок к победе над вами, другой алгоритм может работать лучше - например, алгоритм с высоким риском может давать сбой чаще, но когда он работает, он работает быстро, и вы можете победить своего противника, который ближе к победе, чем вы. .
Определите стиль игры соперника — это может дать вам подсказку о том, как он планирует размещение кораблей (т. е. велика вероятность, что его собственный алгоритм быстрее всего определит, как он размещает свои корабли — если единственный инструмент, который у вас есть, — это молоток, все похоже на гвоздь)
-Адам
Моя запись.
Ничего особенного, и у меня не было времени добавить все хорошие идеи, которые у меня были.
Но, кажется, играет довольно хорошо.Посмотрим, как оно поведет себя на соревнованиях:
(поместите это в файл Missouri.cs и добавлен в проект.)
using System;
using System.Collections.ObjectModel;
using System.Drawing;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace Battleship
{
// The Empire of Japan surrendered on the deck of the USS Missouri on Sept. 2, 1945
public class USSMissouri : IBattleshipOpponent
{
public String Name { get { return name; } }
public Version Version { get { return ver; } }
#region IBattleship Interface
// IBattleship::NewGame
public void NewGame(Size gameSize, TimeSpan timeSpan)
{
size = gameSize;
shotBoard = new ShotBoard(size);
attackVector = new Stack<Attack>();
}
// IBattleship::PlaceShips
public void PlaceShips(ReadOnlyCollection<Ship> ships)
{
HunterBoard board;
targetBoards = new List<HunterBoard>();
shotBoard = new ShotBoard(size);
foreach (Ship s in ships)
{
board = new HunterBoard(this, size, s);
targetBoards.Add(board);
// REWRITE: to ensure valid board placement.
s.Place(
new Point(
rand.Next(size.Width),
rand.Next(size.Height)),
(ShipOrientation)rand.Next(2));
}
}
// IBattleship::GetShot
public Point GetShot()
{
Point p = new Point();
if (attackVector.Count() > 0)
{
p = ExtendShot();
return p;
}
// Contemplate a shot at every-single point, and measure how effective it would be.
Board potential = new Board(size);
for(p.Y=0; p.Y<size.Height; ++p.Y)
{
for(p.X=0; p.X<size.Width; ++p.X)
{
if (shotBoard.ShotAt(p))
{
potential[p] = 0;
continue;
}
foreach(HunterBoard b in targetBoards)
{
potential[p] += b.GetWeightAt(p);
}
}
}
// Okay, we have the shot potential of the board.
// Lets pick a weighted-random spot.
Point shot;
shot = potential.GetWeightedRandom(rand.NextDouble());
shotBoard[shot] = Shot.Unresolved;
return shot;
}
public Point ExtendShot()
{
// Lets consider North, South, East, and West of the current shot.
// and measure the potential of each
Attack attack = attackVector.Peek();
Board potential = new Board(size);
Point[] points = attack.GetNextTargets();
foreach(Point p in points)
{
if (shotBoard.ShotAt(p))
{
potential[p] = 0;
continue;
}
foreach(HunterBoard b in targetBoards)
{
potential[p] += b.GetWeightAt(p);
}
}
Point shot = potential.GetBestShot();
shotBoard[shot] = Shot.Unresolved;
return shot;
}
// IBattleship::NewMatch
public void NewMatch(string opponent)
{
}
public void OpponentShot(Point shot)
{
}
public void ShotHit(Point shot, bool sunk)
{
shotBoard[shot] = Shot.Hit;
if (!sunk)
{
if (attackVector.Count == 0) // This is a first hit, open an attackVector
{
attackVector.Push(new Attack(this, shot));
}
else
{
attackVector.Peek().AddHit(shot); // Add a hit to our current attack.
}
}
// What if it is sunk? Close the top attack, which we've been pursuing.
if (sunk)
{
if (attackVector.Count > 0)
{
attackVector.Pop();
}
}
}
public void ShotMiss(Point shot)
{
shotBoard[shot] = Shot.Miss;
foreach(HunterBoard b in targetBoards)
{
b.ShotMiss(shot); // Update the potential map.
}
}
public void GameWon()
{
Trace.WriteLine ("I won the game!");
}
public void GameLost()
{
Trace.WriteLine ("I lost the game!");
}
public void MatchOver()
{
Trace.WriteLine("This match is over.");
}
#endregion
public ShotBoard theShotBoard
{
get { return shotBoard; }
}
public Size theBoardSize
{
get { return size; }
}
private Random rand = new Random();
private Version ver = new Version(6, 3); // USS Missouri is BB-63, hence version 6.3
private String name = "USS Missouri (abelenky@alum.mit.edu)";
private Size size;
private List<HunterBoard> targetBoards;
private ShotBoard shotBoard;
private Stack<Attack> attackVector;
}
// An Attack is the data on the ship we are currently working on sinking.
// It consists of a set of points, horizontal and vertical, from a central point.
// And can be extended in any direction.
public class Attack
{
public Attack(USSMissouri root, Point p)
{
Player = root;
hit = p;
horzExtent = new Extent(p.X, p.X);
vertExtent = new Extent(p.Y, p.Y);
}
public Extent HorizontalExtent
{
get { return horzExtent; }
}
public Extent VerticalExtent
{
get { return vertExtent; }
}
public Point FirstHit
{
get { return hit; }
}
public void AddHit(Point p)
{
if (hit.X == p.X) // New hit in the vertical direction
{
vertExtent.Min = Math.Min(vertExtent.Min, p.Y);
vertExtent.Max = Math.Max(vertExtent.Max, p.Y);
}
else if (hit.Y == p.Y)
{
horzExtent.Min = Math.Min(horzExtent.Min, p.X);
horzExtent.Max = Math.Max(horzExtent.Max, p.X);
}
}
public Point[] GetNextTargets()
{
List<Point> bors = new List<Point>();
Point p;
p = new Point(hit.X, vertExtent.Min-1);
while (p.Y >= 0 && Player.theShotBoard[p] == Shot.Hit)
{
if (Player.theShotBoard[p] == Shot.Miss)
{
break; // Don't add p to the List 'bors.
}
--p.Y;
}
if (p.Y >= 0 && Player.theShotBoard[p] == Shot.None) // Add next-target only if there is no shot here yet.
{
bors.Add(p);
}
//-------------------
p = new Point(hit.X, vertExtent.Max+1);
while (p.Y < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.Hit)
{
if (Player.theShotBoard[p] == Shot.Miss)
{
break; // Don't add p to the List 'bors.
}
++p.Y;
}
if (p.Y < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.None)
{
bors.Add(p);
}
//-------------------
p = new Point(horzExtent.Min-1, hit.Y);
while (p.X >= 0 && Player.theShotBoard[p] == Shot.Hit)
{
if (Player.theShotBoard[p] == Shot.Miss)
{
break; // Don't add p to the List 'bors.
}
--p.X;
}
if (p.X >= 0 && Player.theShotBoard[p] == Shot.None)
{
bors.Add(p);
}
//-------------------
p = new Point(horzExtent.Max+1, hit.Y);
while (p.X < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.Hit)
{
if (Player.theShotBoard[p] == Shot.Miss)
{
break; // Don't add p to the List 'bors.
}
++p.X;
}
if (p.X < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.None)
{
bors.Add(p);
}
return bors.ToArray();
}
private Point hit;
private Extent horzExtent;
private Extent vertExtent;
private USSMissouri Player;
}
public struct Extent
{
public Extent(Int32 min, Int32 max)
{
Min = min;
Max = max;
}
public Int32 Min;
public Int32 Max;
}
public class Board // The potential-Board, which measures the full potential of each square.
{
// A Board is the status of many things.
public Board(Size boardsize)
{
size = boardsize;
grid = new int[size.Width , size.Height];
Array.Clear(grid,0,size.Width*size.Height);
}
public int this[int c,int r]
{
get { return grid[c,r]; }
set { grid[c,r] = value; }
}
public int this[Point p]
{
get { return grid[p.X, p.Y]; }
set { grid[p.X, p.Y] = value; }
}
public Point GetWeightedRandom(double r)
{
Int32 sum = 0;
foreach(Int32 i in grid)
{
sum += i;
}
Int32 index = (Int32)(r*sum);
Int32 x=0, y=0;
for(y=0; y<size.Height; ++y)
{
for(x=0; x<size.Width; ++x)
{
if (grid[x,y] == 0) continue; // Skip any zero-cells
index -= grid[x,y];
if (index < 0) break;
}
if (index < 0) break;
}
if (x == 10 || y == 10)
throw new Exception("WTF");
return new Point(x,y);
}
public Point GetBestShot()
{
int max=grid[0,0];
for(int y=0; y<size.Height; ++y)
{
for (int x=0; x<size.Width; ++x)
{
max = (grid[x,y] > max)? grid[x,y] : max;
}
}
for(int y=0; y<size.Height; ++y)
{
for (int x=0; x<size.Width; ++x)
{
if (grid[x,y] == max)
{
return new Point(x,y);
}
}
}
return new Point(0,0);
}
public bool IsZero()
{
foreach(Int32 p in grid)
{
if (p > 0)
{
return false;
}
}
return true;
}
public override String ToString()
{
String output = "";
String horzDiv = " +----+----+----+----+----+----+----+----+----+----+\n";
String disp;
int x,y;
output += " A B C D E F G H I J \n" + horzDiv;
for(y=0; y<size.Height; ++y)
{
output += String.Format("{0} ", y+1).PadLeft(3);
for(x=0; x<size.Width; ++x)
{
switch(grid[x,y])
{
case (int)Shot.None: disp = ""; break;
case (int)Shot.Hit: disp = "#"; break;
case (int)Shot.Miss: disp = "."; break;
case (int)Shot.Unresolved: disp = "?"; break;
default: disp = "!"; break;
}
output += String.Format("| {0} ", disp.PadLeft(2));
}
output += "|\n" + horzDiv;
}
return output;
}
protected Int32[,] grid;
protected Size size;
}
public class HunterBoard
{
public HunterBoard(USSMissouri root, Size boardsize, Ship target)
{
size = boardsize;
grid = new int[size.Width , size.Height];
Array.Clear(grid,0,size.Width*size.Height);
Player = root;
Target = target;
Initialize();
}
public void Initialize()
{
int x, y, i;
for(y=0; y<size.Height; ++y)
{
for(x=0; x<size.Width - Target.Length+1; ++x)
{
for(i=0; i<Target.Length; ++i)
{
grid[x+i,y]++;
}
}
}
for(y=0; y<size.Height-Target.Length+1; ++y)
{
for(x=0; x<size.Width; ++x)
{
for(i=0; i<Target.Length; ++i)
{
grid[x,y+i]++;
}
}
}
}
public int this[int c,int r]
{
get { return grid[c,r]; }
set { grid[c,r] = value; }
}
public int this[Point p]
{
get { return grid[p.X, p.Y]; }
set { grid[p.X, p.Y] = value; }
}
public void ShotMiss(Point p)
{
int x,y;
int min, max;
min = Math.Max(p.X-Target.Length+1, 0);
max = Math.Min(p.X, size.Width-Target.Length);
for(x=min; x<=max; ++x)
{
DecrementRow(p.Y, x, x+Target.Length-1);
}
min = Math.Max(p.Y-Target.Length+1, 0);
max = Math.Min(p.Y, size.Height-Target.Length);
for(y=min; y<=max; ++y)
{
DecrementColumn(p.X, y, y+Target.Length-1);
}
grid[p.X, p.Y] = 0;
}
public void ShotHit(Point p)
{
}
public override String ToString()
{
String output = String.Format("Target size is {0}\n", Target.Length);
String horzDiv = " +----+----+----+----+----+----+----+----+----+----+\n";
int x,y;
output += " A B C D E F G H I J \n" + horzDiv;
for(y=0; y<size.Height; ++y)
{
output += String.Format("{0} ", y+1).PadLeft(3);
for(x=0; x<size.Width; ++x)
{
output += String.Format("| {0} ", grid[x,y].ToString().PadLeft(2));
}
output += "|\n" + horzDiv;
}
return output;
}
// If we shoot at point P, how does that affect the potential of the board?
public Int32 GetWeightAt(Point p)
{
int x,y;
int potential = 0;
int min, max;
min = Math.Max(p.X-Target.Length+1, 0);
max = Math.Min(p.X, size.Width-Target.Length);
for(x=min; x<=max; ++x)
{
if (Player.theShotBoard.isMissInRow(p.Y, x, x+Target.Length-1) == false)
{
++potential;
}
}
min = Math.Max(p.Y-Target.Length+1, 0);
max = Math.Min(p.Y, size.Height-Target.Length);
for(y=min; y<=max; ++y)
{
if (Player.theShotBoard.isMissInColumn(p.X, y, y+Target.Length-1) == false)
{
++potential;
}
}
return potential;
}
public void DecrementRow(int row, int rangeA, int rangeB)
{
int x;
for(x=rangeA; x<=rangeB; ++x)
{
grid[x,row] = (grid[x,row]==0)? 0 : grid[x,row]-1;
}
}
public void DecrementColumn(int col, int rangeA, int rangeB)
{
int y;
for(y=rangeA; y<=rangeB; ++y)
{
grid[col,y] = (grid[col,y]==0)? 0 : grid[col,y]-1;
}
}
private Ship Target = null;
private USSMissouri Player;
private Int32[,] grid;
private Size size;
}
public enum Shot
{
None = 0,
Hit = 1,
Miss = 2,
Unresolved = 3
};
public class ShotBoard
{
public ShotBoard(Size boardsize)
{
size = boardsize;
grid = new Shot[size.Width , size.Height];
for(int y=0; y<size.Height; ++y)
{
for(int x=0; x<size.Width; ++x)
{
grid[x,y] = Shot.None;
}
}
}
public Shot this[int c,int r]
{
get { return grid[c,r]; }
set { grid[c,r] = value; }
}
public Shot this[Point p]
{
get { return grid[p.X, p.Y]; }
set { grid[p.X, p.Y] = value; }
}
public override String ToString()
{
String output = "";
String horzDiv = " +----+----+----+----+----+----+----+----+----+----+\n";
String disp;
int x,y;
output += " A B C D E F G H I J \n" + horzDiv;
for(y=0; y<size.Height; ++y)
{
output += String.Format("{0} ", y+1).PadLeft(3);
for(x=0; x<size.Width; ++x)
{
switch(grid[x,y])
{
case Shot.None: disp = ""; break;
case Shot.Hit: disp = "#"; break;
case Shot.Miss: disp = "."; break;
case Shot.Unresolved: disp = "?"; break;
default: disp = "!"; break;
}
output += String.Format("| {0} ", disp.PadLeft(2));
}
output += "|\n" + horzDiv;
}
return output;
}
// Functions to find shots on the board, at a specific point, or in a row or column, within a range
public bool ShotAt(Point p)
{
return !(this[p]==Shot.None);
}
public bool isMissInColumn(int col, int rangeA, int rangeB)
{
for(int y=rangeA; y<=rangeB; ++y)
{
if (grid[col,y] == Shot.Miss)
{
return true;
}
}
return false;
}
public bool isMissInRow(int row, int rangeA, int rangeB)
{
for(int x=rangeA; x<=rangeB; ++x)
{
if (grid[x,row] == Shot.Miss)
{
return true;
}
}
return false;
}
protected Shot[,] grid;
protected Size size;
}
}
Это не минимакс.На самом деле, после размещения кораблей, разве каждый игрок не может играть самостоятельно, в результате чего ему потребовалось несколько ходов, чтобы потопить каждый корабль противника?Выигрывает тот, кто сделал меньше ходов.
Я не думаю, что есть какие-то хорошие общие стратегии, кроме как топить пораженные корабли и пытаться минимизировать количество выстрелов, чтобы прикрыть оставшиеся возможные места, где корабли могут спрятаться.
Конечно, для всего, что не является случайным, могут быть контрстратегии.Но я не думаю, что существуют стратегии, которые хороши против всех возможных игроков.
На самом деле, я думаю, что самая большая проблема с головоломкой заключается в том, что по сути она состоит из двух ходов.Один ход — это размещение ваших кораблей, другой — поиск вражеских кораблей (каким бы сегментом ни была вторая часть, помимо попытки побить время со случайным фактором, это просто «запустить ваш алгоритм»).Не существует механизма, позволяющего определить стратегию противника, а затем противостоять ей, что делает подобные соревнования, основанные на последовательных раундах «камень-ножницы-бумага», довольно интересными.
Кроме того, я думаю, было бы круче, если бы вы указали в игре сетевой протокол, а затем предоставили структуру для реализации этого протокола на C#, а не требовали, чтобы все решения были на C#, но это всего лишь мое мнение.
РЕДАКТИРОВАТЬ:Отменяю свою первоначальную точку зрения, так как недостаточно внимательно прочитал правила конкурса.
Мне всегда нравилось начинать с середины и двигаться по спирали от этой точки, оставляя не более 1 пустого пространства между любыми другими точками, чтобы учесть эту чертову субстанцию...Промежуток между выстрелами зависел от того, какие корабли были потоплены.если B-корабль был последним, между выстрелами должно было оставаться только 4 промежутка, чтобы свести к минимуму бесполезные выстрелы.
Аналогичный конкурс проводил доктор Джеймс Хизер из Университета Суррея от имени Британского компьютерного общества.
Были наложены ограничения на ресурсы, а именно максимальное время процессора за ход, невозможность сохранения состояния между ходами, установлен максимальный размер кучи.Чтобы ограничить время, ИИ мог отправить ход в любой момент временного интервала, и ему будет предложено сделать ход по завершении хода.
Очень интересно, подробнее: http://www.bcsstudentcontest.com/
Возможно, подскажу вам еще несколько идей.
В нынешнем виде решение открывается и запускается без изменений в monodevelop в Ubuntu 9.10 Linux.
Вы написали:
- Все, что будет сочтено противоречащим духу соревнования, будет основанием для дисквалификации.
- Вмешательство в дела соперника противоречит духу соревнования.
пожалуйста, дайте определения "против духа соревнования" и "вмешательство в дела оппонента"?
Также для упрощения я рекомендую вам:
- вообще запретить использование ЦП во время использования слота ЦП противника.
- запретить параллелизм потоков и вместо этого предоставить больше процессорных секунд для одного потока.Это упростит программирование ИИ и в любом случае не повредит никому, кто ограничен процессором/памятью.
PS - здесь скрывается вопрос к постдокам по CS:разве эта игра не разрешима (т.существует ли единственная, лучшая стратегия?).да, размер доски и количество шагов делают минимакс и др. обязательными, но мне все же есть над чем задуматься...по сложности это далеко от го и шахмат.
Я предсказываю, что победит тот, кому удастся перепроектировать случайные начальные числа и шаблоны коллов своего оппонента.
Хотя не уверен, насколько это вероятно.
Также, по-видимому, можно было бы запустить серию таких игр с вариациями.
Добавление таких вещей, как трехмерный самолет или возможность перемещать один корабль вместо того, чтобы стрелять на ходу, вероятно, немного изменило бы игру.
Одна секунда общий время игры зависит от машины.Когда-то секунда операций ЦП на моей машине будет отличаться от турнирной машины.Если я оптимизирую алгоритм Battle Ship так, чтобы он использовал максимальное время процессора в течение 1 секунды, а затем, возможно, на более медленной турнирной машине, он всегда будет проигрывать.
Я не знаю, как обойти это ограничение платформы, но его следует устранить.
...
Одна из идей — сделать то, что было сделано на этом конкурсе. http://www.bcsstudentcontest.com/
И иметь максимальное время за ход, а не максимальное общее время игры.Таким образом, я мог ограничить алгоритмы, чтобы они соответствовали времени выполнения операции.Игра может длиться от 50 до 600+ ходов, но если мой алгоритм управляет общим игровым временем, он может не дать достаточно времени, чтобы выполнить свою работу наилучшим образом, или он может потратить слишком много времени и проиграть.В алгоритме «Морской бой» очень сложно управлять общим временем игры.
Я бы предложил изменить правила, чтобы ограничить время хода, а не общее время игры.
Редактировать
Если бы я написал алгоритм, который перебирает все возможные кадры, а затем ранжирует их, то выбирается кадр с самым высоким рейтингом.Создание всех возможных снимков заняло бы слишком много времени, поэтому я давал алгоритму поработать определенное время, а затем останавливал его.
Если бы существовало ограничение по шагам, я мог бы позволить алгоритму работать в течение 0,9 секунды и вернуть выстрел с самым высоким рейтингом, и при этом уложиться в ограничение по времени хода.
Если общее время игры будет ограничено одной секундой, будет сложно определить, как долго алгоритм должен работать на каждом ходу.Я хочу максимально увеличить время процессора.Если игра длилась 500 раундов, я мог ограничить каждый ход 0,002 секунды, но если игра длилась 100 раундов, я мог уделять каждому ходу 0,01 секунды процессорного времени.
Для алгоритма было бы непрактично использовать полуисчерпывающий поиск пространства кадров, чтобы найти лучший кадр с текущим ограничением.
Общее время игры в 1 секунду ограничивает тип алгоритмов, которые можно эффективно использовать для конкуренции в игре.
Я справляюсь с этим, не добавляя реальный код, но рискну сделать некоторые общие наблюдения:
- Поскольку все корабли имеют размер не менее 2 ячеек, вы можете использовать оптимизацию, которую я видел в реализации игры в Space Quest V, которая стреляет только по альтернативным ячейкам в виде ромба во время «искания» цели.Это устранит половину квадратов, но при этом гарантирует, что в конечном итоге вы найдете все корабли.
- Случайная схема стрельбы при поиске целей статистически даст наилучшие результаты во многих играх.
![Плотность вероятности][1]введите описание изображения
![введите описание изображения][2]
Я экспериментировал, сравнивая результаты случайной стрельбы с тупой охотой/мишенью и, наконец, сложным поиском.
Лучшим решением, по-видимому, является создание функции плотности вероятности того, насколько вероятно, что какой-либо отдельный квадрат используется оставшимися кораблями, и нацеливание на квадрат с наибольшим значением.
Вы можете увидеть мои результаты здесь введите описание ссылки здесь
«Морской бой» — это так называемая классическая NP-полная задача информатики.
http://en.wikipedia.org/wiki/List_of_NP-complete_problems
(ищите «Морской бой» — он там, в разделе «Игры и головоломки»)
