Бот для игры в "Морской бой": история, теория, практика

[GriV]

Когда подбивался какой-нибудь корабль, алгоритм стрельбы переходил в режим добивания корабля. Здесь я не смог на тот момент найти каких-либо критериев повышения вероятности поражения, поэтому стрелял в любую из клеток вокруг той, которая подбита, если по этой линии мог быть размещен корабль противника минимальной длины из оставшихся. После подбития второй клетки корабля противника стрельба проводилась только вдоль линии, в которой расположен этот корабль. Добивание корабля противника всеми игроками, в том числе моим алгоритмом, считается приоритетным перед поиском оставшихся кораблей. Обоснование простое: подбитие корабля исключает из игры не только обстрелянные клетки, но и клетки вокруг подбитого корабля, тем самым существенно уменьшая возможности размещения остальных кораблей, а также меняя картину максимумов числа возможностей этого размещения.

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

X-попадание
_-промах

0000000
0000000
000X000
000_000
0000000

0000000
0000000
000X000
0000000
000_000


вэтих схемах более правильным будет горизонтальное продолжение атаки,

0000000
0000000
000X0_0
000_000
0000000

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

0000000
0000000
000X_00
000_000
0000000

Такая схема не даёт вероятностно лучший исход в одном из направлений, можно атаковать рандомом вверх или влево.

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

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

[Advertiser]

[Barmaley_m]

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

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

Этот метод крайне долог (с точки зрения сходимости и соотвественно достижения решения).

Долог? Ты что! Метод имеет экспоненциальную сходимость. С каждой итерацией интервал, в котором находится решение, уменьшается в 2 раза. Угадать число от 1 до 100 за 7 попыток - это, я бы сказал, довольно-таки неплохо. Для угадывания числа от 1 до 1000 тем же методом требуется всего 10 попыток! Разве это не впечатляет?

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

При численном решении уравнений имеются методы, сходящиеся быстрее, чем метод половинного деления, однако эти более быстрые методы пользуются тем, что искомая функция является гладкой, ее аппроксимируют какими-нибудь полиномами, а в нашем случае "Морского боя" как ты что-то здесь аппроксимируешь?

Хотя метод золотого сечения возможно тоже будет применим?

Метод золотого сечения применяется для поиска экстремумов, и по сути он имеет такую же экспоненциальную сходимость, как и метод половинного деления. Сходится чуть медленнее: интервал уменьшается не в 2 раза за каждую итерацию, а в 1.6 раза. Связано это с тем, что для локализации экстремума требуется 3 точки, тогда как для локализации корня - только 2.

А чтобы человек, играющий против бота не использовал слабость какой-то конкретной методики - тогда рандомом выбирать одну из них на старте?

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

Скажем, если построить карту вероятностей размещения кораблей в каждой клетке на необстрелянном поле - то такая карта должна быть симметричной относительно поворотов и зеркального отражения, поэтому клеток с максимальной вероятностью попадания должно быть не менее 4.

---------- Post added at 20:14 ---------- Previous post was at 20:05 ----------

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

Нет, все сложнее.

Выстрелы в середину поля, как будет показано далее (когда я опубликую результаты расчетов), вообще говоря, не делят все множество допустимых размещений кораблей на равные части. Связность множества размещений кораблей не является такой простой, как связность клеток на поле. Поэтому первые выстрелы бота будут в клетки типа В-1 или А-3. Именно они имеют на необстрелянном поле максимальную вероятность попасть в корабль - около 25%. Выстрелы в эти клетки делят множество допустимых размещений кораблей в пропорции примерно 1:3. Но лучше нельзя в начале игры.