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

[Barmaley_m]

Прежде, чем мы возьмемся вычислять вероятность попадания в корабли,
сделаем небольшое отступление, чтобы рассмотреть игру в "Морской бой"
с другой стороны.

"Морской бой" как задача поиска.

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

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

Разбивание множества возможных решений на две части при каждой итерации напоминает
задачу двоичного поиска, или игру в угадывание чисел. Например, если требуется
угадать число от 1 до 100, задуманное противником, и после каждой попытки
противник сообщает, больше или меньше задуманного им числа является названное
число.

Оптимальный способ решения задачи такого поиска известен. Его называют
"половинное деление", "дихотомия", "бисекция", что в общем-то означает одно
и то же. Сначала нужно разбить интервал на 2 равные части, назвав число 50.
В случае неугадывания становится известно, в какой из половин интервала
находится задуманное число, а размер оставшегося интервала для угадывания
уменьшается в 2 раза. Вторая попытка должна быть произведена в середину
оставшегося интервала, т.е. 25 или 75. В результате второй попытки интервал
для угадывания снова сократится в 2 раза. И так далее. В итоге после максимум
7 попыток (для интервала 1-100) задуманное число будет угадано.

Метод половинного деления приходит к ответу, в худшем случае,
за число попыток, равное log2(N), где N - число элементов множества возможных ответов,
при этом, если значение логарифма оказывается дробным, то его следует округлить
в большую сторону.

При отсутствии какой-либо иной информации об элементах множества, в котором
производится поиск, кроме ответов "больше-меньше", метод половинного деления
является оптимальным, т.е. любой другой метод поиска, хоть в частных случаях
может и приводящий к ответу быстрее, чем за ceil(log2(N)) попыток, в наихудшем
случае будет тратить больше попыток, чем метод половинного деления. В самом деле,
если мы будем разбивать интервал для угадывания на неравные части, то в случае
невезения (задуманное число всякий раз будет оказываться в большей из двух частей)
затратим больше попыток, чем если бы делили интервал пополам.

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

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

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

Ситуации, в которых вероятность попадания может достичь и превысить 50%, возникают
в игре не сразу. При необстрелянном поле размером в 100 клеток у нас имеется 20
клеток, занятых кораблями. При расчете вероятности попадания на необстрелянном поле
исходя из идей, высказанных мной ранее, удается найти клетки с максимальной
вероятностью попадания примерно 25%. До 50% дотянуть не удается. Ну, что ж делать,
приходится довольствоваться тем, что есть. Но чем выше вероятность попадания в
обстреливаемой клетке - независимо от результата выстрела - тем быстрее
мы сужаем круг для дальнейших поисков.

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

Рассмотрим снова игру в угадывание чисел с позиции задумывающего.

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

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

Если мы знаем, что противник, угадывая наши числа, пользуется наилучшим
для общего случая алгоритмом - методом половинного деления - то нам
становится понятно, что противник угадает наше число максимум за 7 попыток,
что бы мы ни делали. Повысить верхнюю границу на число попыток мы не
можем. Но мы можем задумывать такие числа, чтобы при их угадывании методом
половинного деления было затрачено как раз максимальное число попыток.
Например, если мы задумали число 33 - то противник будет угадывать его в
такой последовательности: 50, 25, 37, 31, 34, 32, 33, т.е. затратит
ровно 7 попыток. Таких чисел всего существует 37 штук на промежутке 1-100,
и если мы будем всегда загадывать одно из них - то обеспечим противнику
максимум трудностей. Конечно, только до тех пор, пока противник не
догадается, что мы загадываем только такие числа - тогда он начнет
угадывать их быстрее. Этот же принцип можно распространить на размещение
кораблей в "Морском бое" после того, как мы получим последоватлельность
оптимального (с точки зрения быстрейшего сокращения множества возможных
размещений кораблей) обстрела поля.

[Andrew771]

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

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

[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

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

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

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

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

[GriV]

Долог? Ты что! Метод имеет экспоненциальную сходимость

Для предопределённой функции с поиском экстремума :-) Там лучше вообще метод градиентного спуска использовать :-) А как предопределена функция в случае морского боя? ;-) Там либо попадание либо промах, либо вероятностные кривые, к которым метод половинного деления никакого отношения не имеет :-)

---------- Post added at 17:20 ---------- Previous post was at 17:17 ----------

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

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

[Barmaley_m]

А как предопределена функция в случае морского боя? ;-) Там либо попадание либо промах, либо вероятностные кривые, к которым метод половинного деления никакого отношения не имеет :-)

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

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

Если под методом сетки ты имеешь в виду что-то типа метода Эйлера для решения дифуров - то нет, аналогии здесь не просматривается.

[Advertiser]

[Barmaley_m]

Теперь перейдем к практике: вычисление вероятности попадания для каждой клетки.

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

Каким образом можно рассмотреть все возможные размещения кораблей на поле? Задача имеет тривиальное решение, приводимое ниже.

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

Примем также, что вместо традиционного выражения координат "Морского боя" (буква-число) у нас будут два числа, как в декартовой системе координат, причем первое будет означать горизонтальную координату (номер столбца) начиная слева, а второе - вертикальную координату (номер строки) начиная сверху. Таким образом традиционная координата клетки "Г-2" будет в принятой нами системе выражаться как (4,2).

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

Мы будем перебирать все допустимые координаты при обоих ориентациях сначала четырехпалубного корабля. Для каждой пары координат проверяем, может ли четырехпалубный корабль быть размещен на поле противника, учитывая недопустимость пересечения корабля с уже обстрелянными клетками. Если корабль может быть размещен - временно отмечаем на поле, как будто он там размещен, и проделываем ту же операцию для трехпалубного корабля. Временно разместив его где-нибудь, рассматриваем возможности размещения второго трехпалубного корабля в оставшихся клетках, и так далее. Когда очередь дойдет до последнего из оставшихся вражеских кораблей, при переборе клеток, где он может быть
размещен, учитывая уже "временно размещенные" другие корабли противника, мы начнем получать полные комбинации возможного размещения вражеского флота. Для каждой такой комбинации можно составить двоичную карту поля противника, в которой "0" будет означать отсутствие корабля, а "1" - его наличие. Будем складывать эти двоичные карты, полученные для каждой комбинации размещения флота противника. В результате получится матрица чисел, по размерности равная полю противника, каждый элемент которой будет равен числу таких комбинаций размещения вражеского флота, при которых в данной клетке имеется корабль или
его часть. Поделив это число на общее количество допустимых размещений вражеского флота (которое легко получается в ходе выполнения этого алгоритма), получим искомую вероятность.

Прикинем вычислительную сложность алгоритма. Сколько всего комбинаций размещения вражеского флота нам придется рассмотреть?

Для четырех однопалубных кораблей будет рассмотрено по 100 возможностей, так что общее число рассмотренных комбинаций будет составлять N1 = 100^4=100000000. Это уже очень большое число, и составлять цикл с таким числом повторений на Спектруме мало смысла: его завершения придется ждать очень долго. И это только для четырехпалубных кораблей!

Для двухпалубных кораблей есть ограничения на координаты, но имеется две ориентации, так что каждый корабль может быть размещен 90+90=180 способами. Всего кораблей три, так что число комбинаций будет N2 = 180^3=5832000.

Для трехпалубных кораблей имеем 80+80=160 возможных размещений для каждого из них, всего 2 корабля, число комбинаций = N3 = 160^2=25600.

И, наконец, для четырехпалубного корабля, число всех рассматриваемых возможностей размещения будет N4 = 70+70=140

А всего для вражеского флота в полном составе будет рассмотрено N = N1*N2*N3*N4 ~= 2E+21 комбинаций. Это огромное число, которое не под силу не только Спектруму, но и современным компьютерам, по крайней мере, в рамках минуты - приемлемого времени "размышления" компьютера при выполнении очередного выстрела.

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

[GriV]

Если под методом сетки ты имеешь в виду что-то типа метода Эйлера для решения дифуров - то нет, аналогии здесь не просматривается.

Метод сетки - это метод поиска значения любой (не обязательно гладкой) функции. Заключается в разбиении на части и сканирование гребёнкой. Чем выше частота предполагаемых пульсаций функции, тем чаще гребёнка. Для случая морского боя (естественно) частота гребёнки равна 1 клетке (к чему всё в конечном итоге и сводится?).

---------- Post added at 23:48 ---------- Previous post was at 23:45 ----------

Прикинем вычислительную сложность алгоритма. Сколько всего комбинаций размещения вражеского флота нам придется рассмотреть?

Имеется в виду, что каждый раз после промаха надо перерасчитывать эту матрицу, верно?

[Barmaley_m]

Метод сетки - это метод поиска значения любой (не обязательно гладкой) функции. Заключается в разбиении на части и сканирование гребёнкой.

Понятно. Нет, стрельба в "Морской бой" с точки зрения поиска по множеству размещения кораблей противника, не является аналогичной методу сетки. Даже неоптимальная стрельба наобум сходится экспоненциально, ведь прикинь порядок величины количества всех возможных размещений флота - 1E20! А даже в самом худшем случае, самой неудачной стрельбе, максимально за 100 выстрелов мы находим нужный элемент в этом множестве. Иначе, как экспонентой, такое множество нельзя победить за человеческое время

Имеется в виду, что каждый раз после промаха надо перерасчитывать эту матрицу, верно?

Да, надо пересчитывать, как в случае промаха, так и в случае попадания.

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

Ну и еще один метод есть для составления базы данных первых ходов и для расчетов в промежуточных ситуациях, который я собираюсь описать в следующих сообщениях. Это метод Монте-Карло. Он дает приближенный, не точный результат. А полный перебор всех 1E20 комбинаций - это задача неподъемная даже для современных компьютеров. Если представить себе, что в секунду мы рассматриваем миллиард размещений кораблей (1E9) - то для полного перебора потребуется 1E11 секунд - это около 3000 лет. Даже взлом 56-битного шифра DES является более легкой задачей (там меньше комбинаций).

[GriV]

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

В общем то количество состояний никакого отношения к методике решения задачи не имеет.
Вот метод сетки - http://ru.wikipedia.org/wiki/Метод_перебора

то для полного перебора потребуется 1E11 секунд

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

И ещё, можно хранить уже рассчитанные матрицы для первых 2-3 выстрелов (матрицы вероятности расположения). Можно сэкономить около 3e11 секунд :-)

Иначе, как экспонентой, такое множество нельзя победить за человеческое время

Оно побеждается правилами игры - расположением кораблей, их ориентацией и т.д.. При потоплении 4хпалубника сразу куча клеток улетает (мин 10, макс 18, коэффициент освобождения - min 250%, max 450%), а для однопалубника коэффициант освобождения даже выше (min 400% max 900%) :-) А методика поиска просто сокращает количество выстрелов до победы. При самом неудачном расположении кораблей и неудачном расположении промахов, это будет чуть меньше количество выстрелов, т.к. каждый корабль закрывает собой минимум ещё такое же количество клеток, сколько он сам занимает, т.е. 4+2*3+3*2+4*1 = 20, т.е. максимальное количество выстрелов будет 80.

А всего для вражеского флота в полном составе будет рассмотрено N = N1*N2*N3*N4 ~= 2E+21 комбинаций

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

После установки 1нопалубников (если начинать с них), будет занято минимум 16 клеток, максимум - 36 клеток. Установка двухпалубников займёт минимум 18 максимум 36 клеток, установка трёхпалубников - мин 16, макс 30 клеток, 4хпалубный - мин 10, макс 18 клеток.

Если начинать сверху вниз (от больших кораблей к малым, что в общем то логичнее), то установка 4хпалубника (с вариантами = N4 = 140) cокращает для оставшихся кораблей число свободных клеток минимум на 10. Тогда для оставшихся трёхпалубников остаётся максимум 90 клеток.

Движок форума меня подвёл уже два раза :-( По привычке нажимаю "ответить" из окна правки сообщения... ну и текст сообщения теряется, хотя полдня набирал и считал.

Результаты расчётов получились такие:

N4 = 140
N43 = 17440 (установка 1го 4 и 1го 3хпалубного)
N433 = 1958320
N4332 = 228234080
N43322 = 23919593920
N433222 = 2,22688E+12
N4332221 = 1,1295E+14
N43322211 = 5,2956E+15
N433222111 = 2,28058E+17
N4332221111 = 8,95513E+18
У меня получилось около 280 лет на 1 млрд операций пересчёта в секунду, так что хоть и изменились сильно порядки (как у тебя 3000 лет получилось???), но задача пока далека от обозримого пересчёта.
Учёт заслоняемости кораблей может немного (я думаю около 20%) снизить количество вариантов, но там всё равно больше 2х веков.

Сама задача легко распараллеливается на суперкомпьютере.

Эй, есть тут у кого суперкомпьютер? :-) Нам для морского боя не хватает ;-)