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

[Barmaley_m]

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

Интернета тогда не было, а где еще можно было найти подобную теорию, я также не представлял. Было решено начать с опроса одногруппников, которые были сильны в этой игре. Но опрос показал, что эти люди либо скрывают, либо не имеют формального метода наилучшей стрельбы. Действуют интуитивно. Сообщили мне пару приемов, но описание было такое, которое трудно поддается алгоритмизации. Оставалось только действовать самому. И я начал думать.

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

Исходный пункт моих размышлений на тот момент - это был один красивый прием, подсказанный спектрумистом Андреем Гетало, во время игры в "Battleships". Там корабли были большие, поэтому этот прием очень хорошо действовал. Например, чтобы найти корабль длиной в 4 клетки, нужно в первую очередь стрелять по открытым длинным линиям, причем с интервалом в 3 клетки, т.е. так, чтобы между выстрелами этот корабль не мог спрятаться. Причем каждый выстрел, в идеале, должен максимально сокращать длинные линии как по горизонтали, так и по вертикали.

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

Сформулировать задачу стрельбы в рамках теорвера - дело непростое, тем более для меня на 2м курсе, когда мы теорвер только начали проходить. Но все же я тогда додумался до следующей идеи, которая оказалась очень близкой к оптимуму. Я начал вычислять для каждой свободной клетки величину, которую я назвал "число возможностей размещения". Что это такое?

Представим себе чистое (необстрелянное) поле противника и какую-нибудь клетку в центре поля. Рассмотрим корабль длиной в 4 клетки. Сколько существует возможностей разместить этот корабль, чтобы он одной из своих частей оказался в этой клетке? Ответ простой. Корабль можно разместить по горизонтали четырьмя способами, чтобы одна из его клеток попала в искомую, и еще четырьмя по вертикали. Всего 8.

Теперь представим ту же ситуацию, но клетка справа от искомой уже обстреляна (там "мимо"). Сколькими способами можно разместить 4-палубный корабль, чтобы одна из его частей попала в рассматриваемую клетку? Очевидно, что никакая часть корабля теперь не может оказаться в той клетке, где "мимо". Следовательно, по горизонтали 4-палубный корабль может быть размещен только одним способом: так, чтобы крайняя правая его клетка была в рассматриваемой, а остальные слева. По вертикали число возможностей размещения остается нетронутым, т.е. 4, а всего 5 возможностей размещения.

Число возможностей размещения связано с вероятностью нахождения корабля в данной клетке. Почему? Ответ можно доказать строго. Корабль длиной в 4 клетки может быть размещен на поле конечным числом способов - назовем это число m. Из них n приходится на рассматриваемую нами клетку. Если все размещения корабля на поле равновероятны (а у нас пока нет причин считать иначе) - то вероятность нахождения корабля в данной клетке будет n/m, где n - число возможностей размещения, как я определил это число выше. Таким образом, вероятность нахождения корабля в клетке пропорциональна числу возможностей его размещения в ней. Важно: вышеприведенное рассуждение справедливо только для случая, когда на поле нет других кораблей. Когда есть другие корабли, ситуация значительно усложняется, и вероятность больше не зависит так явно от числа возможностей размещения.

Получить некое число, соответствующее вероятности, для случая многих кораблей, на 1996г мне не удалось, поэтому я ограничился следующим алгоритмом стрельбы:
1) для каждой свободной клетки вычислить число возможностей размещения в ней самого длинного корабля противника, который еще остается на поле.
2) Найти все клетки, где число возможностей размещения достигает максимума.
3) Выстрелить случайным образом в одну из этих клеток с максимумом.

Например, для чистого (необстрелянного) поля число возможностей размещения 4-палубного корабля выглядит следующим образом для каждой клетки:

2 3 4 5 5 5 5 4 3 2
3 4 5 6 6 6 6 5 4 3
4 5 6 7 7 7 7 6 5 4
5 6 7 8 8 8 8 7 6 5
5 6 7 8 8 8 8 7 6 5
5 6 7 8 8 8 8 7 6 5
5 6 7 8 8 8 8 7 6 5
4 5 6 7 7 7 7 6 5 4
3 4 5 6 6 6 6 5 4 3
2 3 4 5 5 5 5 4 3 2

После выстрела в клетку с максимальным числом возможностей размещения (например, Г-4) карта менялась следующим образом:

2 3 4 4 5 5 5 4 3 2
3 4 5 4 6 6 6 5 4 3
4 5 6 4 7 7 7 6 5 4
4 4 4 0 5 6 7 7 6 5
5 6 7 5 8 8 8 7 6 5
5 6 7 6 8 8 8 7 6 5
5 6 7 7 8 8 8 7 6 5
4 5 6 7 7 7 7 6 5 4
3 4 5 6 6 6 6 5 4 3
2 3 4 5 5 5 5 4 3 2

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

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

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

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

Изложенные выше концепции я сначала реализовал в программе на Паскале - seaboy.pas. Так было проще проводить наладку, у меня был компилятор Turbo Pascal под CP/M. Когда алгоритм на Паскале был налажен, я приступил к его переводу на ассемблер.

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

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

Прилагаю файл seaboy.pas - отладочная версия моего бота 1996-1997г.

[Advertiser]