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

Автор оригинала: Paweł Marczewski
  • Перевод


В детстве я три раза в неделю по часу-полтора сидел на работе у отца. Меня пускали за компьютер, где из развлечений был лишь сапёр и 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
#1 Корпоративный облачный провайдер

Комментарии 35

    +5
    Всё это прикольно, вот только никакого влияния на игру не оказывает. Игрок, если он действительно играет, а не балуется, и так сначала открывает все понятные клетки, а только потом приступает к неопределённым.
      +5
      Если явная неопределенность выскакивает в середине игры, то какой смысл откладывать испытание удачи?
        +13
        Вы правы, в таких случаях добавленное правило не усложняет игру, а просто делает её более занудной.
          +5
          Хмм, а почему в случае отсутствие безопасных клеток сделать так, что любая открытая небезопасная клетка не взрывалась?
            +10
            Вот сам хотел это написать — самый лучший вариант для игрока, т.к. в случае появления угадайки всегда первым делом её кликаю, ибо как и сказали выше — нет смысла разгребать все поле, чтоб в конце угадывать и проиграть, просто потеря времени. Но если гарантированно в угадайке (в случае отсутствия гарантированно безопасных клеток) не будет мины — то тогда только появится смысл зачищать все поле перед угадыванием.

            И да, я старпер и очень люблю сапер :)
              0

              Очень интересно, все результаты относятся к 13..14 году — что произошло после? Перестали играть?

                +7
                Перестал выигрывать быстрее, чем за 84 секунды
                  0
                  Нет, играть продолжаю :)

                  Сохранял скрины (когда не забывал об этом) при переустановке системы, а когда перешел на десятку грохнул магазин приложений до того, как заметил что сапера нет — лень замарачиваться было чтоб вернуть его, перешел в онлайн (сейчас на World of Minesweeper захожу поиграть).
                  Мой рекорд в 72 секунды на работе остался :)
          +5
          Мне вот что стало интересно, если сапер это NP-полная задача, а мы знаем что все NP-полные задачи эквивалентны друг-другу, то нельзя-ли первести какую-нибудь полезную задачу в поле сапера и играя ее решить? ;)
            +4
            Майнер еще не прикручивали?
              0

              Скорее всего, размер поля потребуется 100500 на 100500 для сколько-нибудь полезной задачи.

              +1
              Сапер сам по себе не может быть какие-то другим. Там по сути две ситуации — либо ты точно знаешь что в клетке, либо угадайка.
              Если не будет угадаек проиграть, считай, невозможно. А если будут — то от игрока особо ничего не зависит.
                +6
                Интересная реализация, спасибо за перевод!

                Жаль не упомянут режим без угадывания в World of Minesweeper. Я думал что знаю все возможные паттерны, пока не попробовал «Злой» уровень. Там встречаются настолько сложные комбинации, что над ними приходится размышлять по несколько минут. Что-то вроде такого:

                image
                  0
                  А тут разве есть гарантированный ход, без угадайки?
                    +2
                    Конечно, на то он и режим без угадывания) Зеленым выделены клетки, которые можно открыть. Но чтобы прийти к этому решению, нужно проанализировать все клетки, которые выделены голубым. Ну и в совершенстве знать все основные паттерны.
                      0
                      Даже если так, для меня важнее открыть за минимальное время (вроде это показатель успешности игры), а такие анализы сводят на нет получение хорошего результата :(

                        0

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

                          +1
                          Ну тут каждый выбирает то что ему ближе: кто-то играет только на скорость, кто-то ценит только логику и играет на мастерство, а кто-то вообще играет только сверхсложные карты с вероятностью победы вроде 0.0024% :) Вообще, о возможных стилях игры в сапере можно целую статью написать…
                        0
                        Главный паттерн — первыми четырьмя ходами открывать углы. В углах почти всегда угадайка.

                    +3
                    А возможен сапер в котором нет неопределенных ситуаций? Будет ли сапер детерминированным, если «замкнуть» границы пространства, т.е. состыковать правую сторону с левой, а верхнюю с нижней?
                      0
                      Вот это был бы интересный вариант
                        +1

                        Нет. Всегда можно составить ситуацию из 7 мин
                        ХХХ
                        3-3
                        3-3
                        ХХХ
                        в которой в середине угадайка.

                        +1
                        усложнили и так нелегкую игру, не совсем понятно зачем, но стоит заметить, что читать было интересно
                          0

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

                            0
                            Я как-то писал свою версию сапёра, которая автоматически открывает все клетки вокруг цифры 1, если рядом с ней отмечена одна бомба (или вокруг «2», если отмечено 2 бомбы, и т.д.). Смысл в том, чтобы не тратить время на рутинные, очевидные ситуации, а решать либо сложные комбинации, либо приходить к состоянию «угадайки» и пытаться открыть на удачу.
                              +2

                              В обычном сапёре двойным кликом по 1 (равно как и по любой другой цифре) открываются все непомеченные поля вокруг неё.

                                0
                                Знаю, но это надо кликать (и не двойной клик, а одновременно левый+правый). А в моей версии, отгадал какую-нибудь сложную задачку — открылось довольно много полей, от неё зависящих.
                          0
                          Даёшь режим Crossed Squares!
                            0
                            2. Если безопасных клеток нет, то угадывание разрешено, и эта клетка может оказаться пустой.

                            Мне кажется было бы более справедливо, если безопасных клеток не осталось и игрок вынужден угадывать — тогда делать так, чтобы там всегда не было мины.
                            И игра тогда становится полностью детерменированной.
                                +3
                                Сапёр уже давно превратился из обычной игры в часть масс-культуры
                                image
                                  0

                                  Эта задача не кажется вычислительно сложной, если отталкиваться от мин, маркируя все клетки вокруг них.
                                  Все те же 3 типа клеток + новый тип — скрытая клетка. Если вокруг мины все клетки скрыты, то она как бы у нас в резерве и мы можем использовать ее для наказания игрока.

                                    –1
                                    Ну теперь осталось сапер 3Д замутить :)
                                    И в VR его закинуть еще :)

                                    В свое время меня подкололи такой картинкой еще —
                                    image
                                      0
                                      Интересно, почему кому-то не понравилась идея.
                                      Я бы с удовольствием поиграл в 3Д сапера, вот только когда думал об этом не мог придумать удобный интерфейс для версии на мониторе, поэтому про VR и было сказано.
                                      0
                                      Всегда мечтал реализовать именно это, когда играл в эту игру. Спасибо. =)

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое