Kaboom: необычный сапёр

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

«Сапёр» (Minesweeper) появился довольно давно по меркам компьютерной игры. Но мне кажется, что большинство людей помнят игры, которые входили в состав ранних версий Windows. Я никогда не был хорош в «Сапёре», но время от времени поигрывал в неё. Некоторые люди играют более серьёзно. А тем, кто хочет поднять себе настроение, рекомендую посмотреть Minesweeper — The Movie.

Идея

Недавно у меня возникла идея: а что если вам придется играть в «Сапёр» против «поумневшего» компьютера?

Обычно расположение мин определяется в начале игры (но тут есть несколько хитростей — например, чтобы вы не могли проиграть с первого клика). Но что, если бы местонахождение мин не было определено заранее и игре можно было бы выбирать место расположения мин после начала игры?

Это было бы довольно жестоко: если вы кликаете на квадрат, который может содержать мину, он всегда будет содержать её! Таким образом, вы должны заранее доказать, что квадрат безопасен.

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

С другой стороны, бывают ситуации, когда вам приходится угадывать:

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

Другими словами:

• Если вы кликаете на гарантированно безопасную клетку, она будет пустой.
• Если вы кликаете на гарантированно заминированную клетку, на ней будет мина, и вы взорвётесь.
• Если вы кликаете на клетку с неопределённостью, то:
  1. Если на доске есть безопасные клетки, вы будете наказаны за игру в угадайку, в этой клетке обязательно будет мина.
  2. Если безопасных клеток нет, то угадывание разрешено, и эта клетка может оказаться пустой.

Мины на границе

Как реализовать такую игру? Я мог бы попытаться вычислить все возможные поля, но это нереально: даже маленькое поле 10х10 означает 2 ^ 100 возможностей. Выбор только тех, которые содержат ровно N мин, не помогает.

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

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

Выше показано два возможных расположения мин на границе. Объединяя их, мы поймём, какие клетки гарантированно будут пустыми или заминированными.

Мне также нужно отслеживать общее количество мин. Таким образом, расположение действительно похоже на «5 мин на границе, 5 мин снаружи». Это важно, потому что иначе я мог бы создать слишком много мин на границе (или слишком мало!)

Итак, у меня есть все варианты. Что происходит, когда игрок решает открыть клетку?

• Выберите случайный вариант (тот, который удовлетворяет «жестоким, но справедливым» правилам). Это определит расположение мин на границе.
• Случайным образом разбросайте оставшиеся вне границы.
• Если в выбранной клетке есть мина, игра окончена.
• В противном случае:
  1. Определить новую метку для выявленной клетки
  2. Выявить дополнительные клетки, если это будет 0
  3. Забудьте про игру в угадайку, которую мы обсудили ранее! Отныне только метки будут подсказывать вам путь.

Это очень неэффективно

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

О, нет!

Каким-то образом мне удалось разблокировать 18 миллионов возможных минных расположений. Мой Firefox пожирает 12 гигабайт памяти, а раскрытие клетки занимает полминуты. Очевидно, мне нужен лучший алгоритм.

Кто-то может заметить, что «Сапёр» является NP-полной игрой, и поэтому не удастся избежать экспоненциально возрастающего времени. И в общем случае это верно – будут позиции, на вычисления которых уйдет много времени. Но для небольшой площади это работает.

Мне не нужно запоминать все комбинации. Мне даже не нужно вычислять все комбинации. Всё что требуется, это способ:

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

Поиск решателя

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

Более мощный класс программного обеспечения — это SMT-решатели, которые работают с более широким набором значений и формул, таких как логика первого порядка (квантификаторы), массивы, целые числа и так далее. Это поможет, по крайней мере, определить некоторые уравнения для целых чисел. Но мне требуется что-то, работающее в браузере. Людям удалось портировать некоторые сложные инструменты вроде Z3Prover, в браузер, но версия WebAssembly весит 17 МБ, и это чересчур.

Я нашел MiniSat, небольшой SAT-решатель, который был скомпилирован для Javascript Джоэлем Галенсоном. Скомпилированный файл занимает всего 200 килобайт, поэтому я использую его.

Формулы CNF

Решатели SAT работают с формулами конъюнктивной нормальной формы (CNF). Формулой CNF является «an AND of ORs», например:

(a | ~ b | ~ c) & (c | d ~ e) & f

Вы можете преобразовать любую формулу логики высказываний (variables, and, or, not, implication) в CNF, так что это что-то вроде универсального формата.

Как мы это используем? Допустим, у нас есть доска:

? ? 1
2 ? 1

Если я создам переменные для неизвестных клеток (по часовой стрелке: x1, x2, x3), они должны будут удовлетворять следующим уравнениям:

х1 + х2 + х3 = 2
х2 + х3 = 1
х2 + х3 = 1 (как и в предыдущем)

Но как выразить «сумма переменных равна 2» в CNF?

Я нашел способ, который, как я узнал позже, называется «биномиальное кодирование» и является самым простым кодированием. Вы должны рассмотреть все возможные подмножества переменных. Например, для x1 + x2 + x3 = 2 нужны следующие формулы:

• Для каждого подмножества из 2-х переменных, по крайней мере, одна истинна. Это гарантирует, что сумма больше 1.
  (x1 | x2) & (x1 | x3) & (x2 | x3)
• По крайней мере, одна переменная ложна. Это гарантирует, что сумма меньше 3.
  (~ x1 | ~ x2 | ~ x3)

Для x2 + x3 = 1 мне нужен аналогичный набор формул:

• По крайней мере, одна из переменных верна: (x2 | x3)
• По крайней мере, одна из переменных является ложной (~ x2 | ~ x3).

Соединив это, я получу формулу CNF с 6 пунктами (частями). В стандартном формате DIMACS:

p cnf 3 6
1 2 0
1 3 0
2 3 0
-1 -2 -3 0
2 3 0
-2 -3 0

Все строки положения заканчиваются на 0, а отрицание помечается минусом. Если я подключу его к MiniSat (попробуйте сами), я получу:

SAT 1 2 -3

Это означает, что MiniSat нашел решение, где x1 и x2 истинны, а x3 ложны. Вот как будет выглядеть доска:

! ! 1
2 . 1

Вся программа немного сложнее: это всего лишь одно решение, существует и другое. Поэтому, чтобы узнать, может ли x1, x2, x3 быть истинными (или ложными), нужно сделать больше запросов. Мне нужно спросить: «Учитывая приведенную выше формулу, а также x1, выполнимо ли это? Как насчет приведенной выше формулы, а также ~ x1»?

Кодировка означает, что мне нужно найти все возможные комбинации (например, все подмножества из 3) набора переменных. Однако для данного уравнения будет только до 8 переменных, поэтому формула обычно достаточно мала, чтобы MiniSat мог быстро ее решить.

Отслеживание количества мин

К сожалению, это не полное решение! Мне всё ещё нужно отследить, сколько мин осталось. Некоторые комбинации невозможны, так как иначе вы можете создать больше мин, чем разрешено, и победить будет невозможно.

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

Поэтому мне нужно указать в формуле SAT, что «количество мин составляет не менее X и не более Y». Сначала я думал, что смогу использовать трюк со всеми комбинациями. К сожалению, он не слишком хорошо работает с большими числами. Если есть, скажем, 20 клеток и 10 мин, то после подключения чисел к биномиальному коэффициенту мы узнаем, что число комбинаций уже в 6 цифрах!

Так я узнал, что есть много других способов кодирования суммы переменных в формулу SAT. Вам необходимо создать схему, которая будет объединять отдельные переменные. Посмотрите, например, этот ответ на StackExchange или этот.

В итоге я реализовал идею из статьи под названием «Эффективное кодирование CNF с булевыми ограничениями кардинальности», написанную Оливье Байо и Ясином Буфхадом. Мы видим дерево, которое рекурсивно добавляет унарные числа (или сортирует биты так, чтобы все были в начале):

В конце этой схемы вы получите отсортированный набор «выходных» переменных. Чтобы подтвердить, что сумма не меньше X, проверьте, что первые X получающихся переменных равны 1. Чтобы утверждать, что сумма не более Y, проверьте, что последние N — Y получающихся переменных равны 0.

Это намного лучше, чем использование всех возможных комбинаций, однако эта схема всё ещё нерациональна, поскольку генерирует предложения Ө (N ^ 2). Когда количество открытых клеток составляет около 100, игра становится вялой. Мы можем оптимизировать игру дальше.
Сокращение количества запросов

В ходе изучения вопроса я заметил, что могу сократить количество запросов к решателю. Я хотел определить статус всех клеток (то есть проверить, гарантированно ли они опасны, безопасны или нет). Я сделал это, используя простой цикл. Допустим, доска описывается формулой F:

• Решите для F & ~ x1, чтобы проверить, может ли x1 быть 0
• Решите для F & x1, чтобы проверить, может ли x1 быть 1
• Решите для F & ~ x2 , чтобы проверить, может ли x2 быть 0
• Решите для F & x2, чтобы проверить, может ли x2 быть 1
• И так далее.

Что я заметил? Если я получу решение для F & ~ x1, оно также будет содержать значения всех других переменных. Это уже отвечает на многие другие вопросы: если решение содержит x2 = 0, мне не нужно спрашивать, может ли x2 быть 0, потому что я это уже знаю. Это позволяет мне сократить количество запросов примерно в 2-5 раз.

Кэширование

Это не решает проблему огромной формулы, сгенерированной «счетной» схемой. Как я уже говорил, количество предложений в порядке N ^ 2. На большой доске формула может составлять до 10 000 предположений.

К счастью, большую часть времени мы знаем точное значение многих клеток. Если клетка гарантированно пустая или гарантировано заполненная, значение никогда не изменится! Это означает, что мы можем кэшировать его и не включать в формулу SAT. Как только мы определим состояние клетки, нам больше не нужно будет снова включать его в расчет. Клетки будут использоваться до тех пор, пока они являются неопределенными.

Эта оптимизация слегка опасна: у нас больше нет формулы, подтверждающей правильность всей доски. Если всё остальное работает как запланировано, это не проблема, но может усложнить отслеживание ошибок.

Другой случай: игра за границей

Разрешено ли вам нажимать в любом месте карты за пределами границы между открытой и неоткрытой зоной поля?

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

Поэтому я изменил игру так, что клик за пределами границы всегда наказывается. За исключением начала игры, конечно, потому что тогда вся доска «снаружи».

Но оказывается, есть еще один вариант развития событий: что, если все пограничные поля смертельны?

3 . .
. . .
. . .

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

• Поле не открыто
• Заминированные клетки могут находится на границе (щелчок снаружи должен быть безопасным), или
• Во всех клетках на границе обязательно должны быть бомбы (вы вынуждены кликать снаружи).

Обновление: изменение оказалось спорным, так как ограничение является несколько искусственным. Я добавил переключатель, который позволит/запретит играть с этими условиями.

Это всё

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

Исходный код на Github. Он не очень красивый.

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

Играйте с умом!

Что ещё полезного можно почитать в блоге Cloud4Y

→ Как «сломался» банк
→ Неприкосновенность личной жизни? Нет, не слышали
→ Великая теория снежинок
→ Диагностика сетевых соединений на виртуальном роутере EDGE
→ Устойчивые к CRISPR вирусы строят «убежища» для защиты геномов от ДНК-проникающих ферментов

Подписывайтесь на наш Telegram-канал, чтобы не пропустить очередную статью! Пишем не чаще двух раз в неделю и только по делу. Напоминаем, что стартапы могут получить 1 000 000 р. от Cloud4Y. Условия и анкета для желающих — на нашем сайте: bit.ly/2sj6dPK

Автор: Cloud4Y

Источник