Снова «Морской бой». Считаем число возможных расположений кораблей

Раз уж неделя «Морского боя» на Хабре продолжается, добавлю и я свои два цента.
При попытке найти оптимальную стратегию для игры за компьютер довольно быстро приходим к такому приближению:

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

В самом деле. Если возможная конфигурация только одна, то мы заканчиваем игру за один ход, расстреливая его корабли по очереди (ведь конфигурация нам известна!) Если же конфигураций больше, то нам нужно уменьшить их число как можно сильнее, тем самым увеличив имеющееся у нас количество информации. Если мы попадём в корабль, то ничего не потеряем (ведь ход остаётся у нас!), а если промахнёмся — то число оставшихся комбинаций будет минимальным из возможных после этого хода.

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

На первый взгляд, задача кажется неподъёмной. Число конфигураций представляется порядка 10²⁰ (на самом деле их несколько меньше — ближе к 10¹⁵), так что на полный перебор времени уйдёт слишком много. Перебирать раскраски поля и оставлять только допустимые — не лучше: всё равно нам каждую комбинацию придётся просмотреть.

Что же ещё попробовать? Любой олимпиадник тут же ответит — динамическое программирование. Но как его организовать?

Идём сверху вниз. Какая информация нам нужна?

Итак, будем идти сверху вниз. Предположим, что поле у нас разделено на две части — часть A состоит из первых k строк, а часть B — из всех остальных. Заполнением части поля назовём любую раскраску его клеток в два цвета. Заполнение всего поля называется корректным, если чёрные клетки образуют набор кораблей, удовлетворяющий правилам (корабли прямые, не соприкасаются, их длины образуют нужный набор). Два заполнения S1 и S2 части A мы будем называть эквивалентными, если для любого заполнения T части B объединенные заполнения всего поля S1|T и S2|T будут корректными или некорректными одновременно.

Для решения задачи нам достаточно:

• Описать все классы эквивалентности заполнений для части A
• Для каждого класса вычислить число различных заполнений, и для каждой клетки области A указать, в каком числе заполнений она была чёрной (назовём эту информацию картой данного класса)
• Описать пересчёт классов и их карт при добавлении к области A новой строки.

Пусть у нас есть неизвестное заполнение S области A и известное заполнение T области B. Что нам достаточно знать про S?

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

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

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

И всё. Класс эквивалентности целиком определяется этими данными, причём даже не все их комбинации являются допустимыми. Посчитаем, сколько получилось:

• Последняя строчка: 10 бит, причём не все варианты возможны: не может идти более 4 единиц подряд, и не может быть двух групп по 4 единицы (0111101111). Всего получается 909 вариантов.
• Уже выставленные корабли. От 0 до 4 однопалубных, от 0 до 3 двухпалубных, от 0 до 2 трёхпалубных, 0 или 1 четырёхпалубный. Всего 120 вариантов.
• Для каждого изолированного бита строчки — число клеток в соответствующем вертикальном корабле, попавших в A: от 1 до 4. Таких кораблей не более 5, итого не более 1024 вариантов.

Каждый класс, таким образом, описывается 27 битами, а их общее количество — не более 120 миллионов. В действительности, эта оценка сильно завышена, и программа смогла найти 1053612 классов.

Добавляем новую строку

Пусть у нас есть заполнение S, про которое нам известна только описанная выше информация. Мы хотим продлить его ещё на одну строку: перечислить все заполнения, которые можно получить, определить классы для них, и для каждого нового класса построить карту плотности заполнений.

Сначала посмотрим, какие строки мы можем добавлять к нашему заполнению. Основной критерий известен всем: черная клетка новой строчки не может быть соседней по диагонали с чёрной клеткой последней строчки S. Далее, как мы уже знаем, в новой строчке не может быть слишком длинных кораблей. И еще, если один из вертикальных кораблей имеет длину 4, то продолжаться на новую строку он тоже не может. Остальные ограничения связаны с набором кораблей, и их удобнее проверять потом.

Переберём все строки, которые можно добавить. Если в строке есть более одной единицы подряд, то они образуют горизонтальный корабль — его сразу учитываем в счётчиках законченных кораблей. С изолированными единицами есть три ситуации:

• В последней строке S изолированная единица была, а в новой строке в этом месте её нет. Значит, корабль закончен, и его длина добавляется к счётчику.
• В новой строке изолированная единица есть, а в последней строке S в этом месте её не было. Значит, появился новый вертикальный корабль, и его длина сейчас равна 1.
• Изолированная единица есть и в последней строке S, и в новой строке. Значит, вертикальный корабль продолжается, и его длина увеличивается на 1.

Теперь проверим, допустим ли набор длин. Пусть s1, s2, s3, s4 — число законченных кораблей длины 1,2,3,4 соответственно, а n1, n2, n3, n4 — число незаконченных кораблей с соответствующими длинами. Чтобы набор не противоречил условиям, необходимо следующее:

s1<=4 && s2<=3 && s3<=2 && s4+n4<=1 && (s3+s4+n3+n4)<=3 && (s2+s3+s4+n2+n3+n4)<=6 && (s1+s2+s3+s4+n1+n2+n3+n4)<=10 

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

Концовка

После того, как мы добавили к исходной пустой конфигурации 10 строк, у нас получился список из 1053612 классов, каждый — со своей картой. Чтобы получить карту всех конфигураций поля, нам надо пройтись по всем этим классам,«закончить» незаконченные корабли, посчитать число получившихся кораблей каждого размера, и если оно правильное — то прибавить карту класса к общей сумме.

Для пустого поля 10×10 получилось 1855545978831780 конфигураций, а карта заполнения выглядит так (все числа поделены на 10⁹):

 438487 418064 475795 466986 459000 459000 466986 475795 418064 438487 418064 273993 311381 287231 287065 287065 287231 311381 273993 418064 475795 311381 378334 357367 361127 361127 357367 378334 311381 475795 466986 287231 357367 330652 334756 334756 330652 357367 287231 466986 459000 287065 361127 334756 338709 338709 334756 361127 287065 459000 459000 287065 361127 334756 338709 338709 334756 361127 287065 459000 466986 287231 357367 330652 334756 334756 330652 357367 287231 466986 475795 311381 378334 357367 361127 361127 357367 378334 311381 475795 418064 273993 311381 287231 287065 287065 287231 311381 273993 418064 438487 418064 475795 466986 459000 459000 466986 475795 418064 438487 

То, что она симметрична, косвенно подтверждает, что грубых ошибок в программе нет 🙂 Самая заполненная клетка — С1, самая незаполненная — B2.
После хода в С1 карта примет такой вид:

 334039 316782 362205 354834 348680 348723 354859 362278 316825 334105 316847 204441 234170 214857 214919 214952 214721 234125 204338 316830 362174 234066 286949 270246 273421 273609 270199 287338 234109 362286 354993 215372 270082 249099 252049 252445 248433 270251 214694 354875 347443 215675 272189 252807 255040 256554 252272 273744 214941 348764 344351 216423 272030 253365 252114 255722 251441 273431 214746 348625 351029 226597 265572 262005 251178 255339 249502 271093 215027 354867 347356 238783 245635 276238 258889 268837 266947 286297 234182 362174 342552 273993 227511 287231 237138 226857 216325 233431 204620 316794 292453 231475      0 269650 316361 349490 359545 360275 316193 333632 

Последовательность «лучших ходов» при постоянных промахах выглядит так (см. рисунок):
C1, J8, A8, H1, A4, J4, D10, G10, E1, D2, B3, A2, C9, B10, H9, I10, I7, J6, I5, H6, J2, I3, H4, G5, G2, F3, E4, B7, A6, B5, C6, C3, D4, D5, F6.
Видно, что программа не торопится ловить линкоры. К 24-му ходу, когда «диагональному» алгоритму остаётся последний ход до гарантированного попадания, число оставшихся расположений кораблей составляет примерно 240*10⁹, а у «диагонального» алгоритма оно составляет 260*10⁹. Разница невелика. Надо будет устроить турнир между этими алгоритмами, чтобы выяснить, насколько она существенна.

Неделя Морского Боя

Оптимальный алгоритм игры в морской бой GORKOFF
Алгоритм игры в «морской бой»: обстрел противника impersonalis

И более старые публикации:
Теория и практика игры «Морской бой» — по-честному born2fly
Морской бой с искусственным интеллектом — по-честному michurin