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

[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. Но лучше нельзя в начале игры.

[Advertiser]