Сапер — простая игра с простыми правилами, но некоторые ее конфигурации представляют собой интересные задачи. В этой статье мы создадим решатель Сапера с нарастающей сложностью и рассмотрим, как меняется динамика игры по мере постепенного повышения уровня помощи. Наконец, мы разработаем новую версию игры с гораздо более интересным геймплеем.
Локальные рассуждения: ноль соседних мин
В оригинальной игре используется один автоматический механизм: когда игрок открывает ячейку, рядом с которой нет мин, игровой движок открывает все соседние ячейки. Это никоим образом не угрожает игре, поэтому можно смело позволить компьютеру сделать это, а ситуация сразу понятна игроку и никак не мешает игровому процессу.
Это рассуждение полностью локально: для принятия решения о следующем действии учитывается только информация из одной ячейки.
Сложно представить себе ситуацию, в которой игра была бы хуже без этой автоматической подсказки. Попробуйте поиграть в такую игру, чтобы понять, как это происходит без автоматического открытия ячеек [в исходной статье все примеры интерактивные]:
Локальные рассуждения с учётом окружения
Новому игроку не составит труда понять, что если количество соседних мин, т.е. число, указанное в ячейке, равно количеству неоткрытых соседних ячеек, то все эти клетки должны быть минами и, следовательно, должны иметь на себе флажки. . Точно так же, когда количество соседних мин равно количеству соседних флажков, оставшиеся неоткрытыми соседние клетки должны быть пустыми.
Эти правила учитывают как одну ячейку, так и состояние соседних ячеек (открыто/открыто).
Ручная реализация этих политик может быть забавной. Если добавлен таймер, игрок начинает учиться применять их быстро и точно. Это превращает Minesweeper в игру на реакцию. Что произойдет, если мы автоматизируем эти правила?
У этой автоматизации есть интересный побочный эффект — пометка может мгновенно привести к летальному исходу.
В противном случае у нас могут возникнуть ситуации, которые можно разделить на три категории:
- Игры, которые полностью решаются с помощью автоматизированных правил
- Сложные ситуации, требующие большего количества клеток для рассуждения
- Игровые состояния, в которых нет логического решения — игроку нужно только выбрать случайным образом, возможно, с вероятностью.
Ситуация 2 кажется мне очень привлекательной. Мы больше концентрируемся на решении логических условий, тратя меньше времени на точное прицеливание и нажатие соответствующих кнопок. Это делает Minesweeper больше похожей на активную игру-головоломку.
Ситуация 3 полностью портит все удовольствие. Однако я слышал, что некоторым нравятся игры с рандомом.
Можно ли избавиться от ситуации 3?
Полное решение: глобальные рассуждения
Нам нужно выполнить полный перебор всех игровых состояний, чтобы алгоритмически обнаружить все необходимые логические условия для данного игрового состояния. Было доказано, что сапер является NP-полной задачей. Ниже приведен небольшой, но интересный и наглядный пример игрового состояния, которое имеет только одно логическое решение, но чтобы его найти, нам нужно рассмотреть все состояние игры:
Можно ли искать по всему месту сохранения? Сколько всего вариантов состояний?
с
?
в
= ширина поля
час
= жилая площадь
к
= количество мин.
Тогда количество возможных состояний
с
равно
Для стандартных уровней «Начинающий», «Любитель» и «Профессионал» это дает нам:
Мы признаем, что наивный подход здесь совершенно неверен. Давайте посмотрим, как может выглядеть наивный алгоритм, и посмотрим, можно ли его оптимизировать во что-то, что работает.
Наивный алгоритм
Задача алгоритма — найти все логические условия, необходимые для данного состояния поля. Это было бы трудно реализовать путем тщательного принятия решений; компьютер намного лучше справляется с быстрой кучей глупых вещей.
Что мы можем сделать «тупо»: сгенерировать все возможные перестановки позиций min для всех остальных мин. Если эта перестановка соответствует всем явным числам, это будет правильное решение игры. Затем мы исследуем все возможные перестановки, находим все возможные решения, но еще не знаем, какое из них правильное.
Если все возможные решения имеют что-то общее либо среди открытых ячеек, либо среди ячеек, помеченных как мины, мы понимаем, что общее должно быть частью правильного решения для текущего поля. Действительно: невозможно создать правильное решение, не имеющее совпадающих элементов, иначе мы бы их нашли.
Таким образом, мы можем найти все необходимые логические условия для настоящего состояния поля.
Клетки с ограничениями и без ограничений
У приведенного выше алгоритма есть очевидная проблема: количество состояний, которые он должен исследовать. Но не все клетки одинаковы. Неизведанные клетки, примыкающие к числу, очевидно, ограничены этим числом. Будем называть эти клетки ограниченными. Остальные клетки назовем несвязанными.
Если бы мы реализовали описанный выше алгоритм, но искали бы только в ограниченном пространстве состояний и переключались обратно, как только нарушали бы ограничение, мы могли бы решить множество игр за разумное время:
В случае неограниченного количества ячеек у нас нет возможности узнать, где находятся мины, и логически мы знаем это немедленно. Это значит, что мы можем исключить их из расчетов и учитывать только расположение мин рядом с открытыми номерами.
Мы знаем, однако, что ряд мин может войти в множество несвязанных ячеек; если есть 6 минут и 4 связанных ячейки, то в связанных ячейках может быть не более 4 минут, поэтому в несвязанных ячейках должно быть не менее 2 минут. Используя аналогичную логику, мы можем иногда указать, что все неограниченные ячейки должны быть пустыми или все содержат min.
В случае, показанном ниже, мы знаем положения всех мин, поэтому СИ должен быть в состоянии понять, что остальные ячейки свободны:
В следующем случае мы не знаем положения всех мин, но можем понять, что оставшаяся мина должна быть размещена в одной из двух ячеек слева вверху. Это означает, что оставшаяся ячейка в правом нижнем углу свободна:
Версия со случайностью
Если мы запустим глобальный решатель автоматически, мы получим случайно оптимизированную версию Bomb Squad:
Игры в этой версии можно разделить на три категории:
- Игры, в которых игрок делает случайный выбор и выигрывает.
- Игры, в которых игрок делает случайный выбор и проигрывает.
- Игры, в которых ИИ давно работает, и игрок действительно может использовать рассуждения.
Но какая игра со случайностью лучше? Похоже, что в других играх со случайностью дело в том, что существует сложная взаимосвязь между действиями игрока и выигрышем/проигрышем. Сложные машины используются для розыгрыша лотерейных номеров, которым требуется время, чтобы выбрать номер и устроить целое шоу, показывая этот номер.
Возможно, большая коробка, которая решается автоматически, — довольно хорошая игра.
случайным образом, при условии, что игрок наблюдает за постепенным открытием всех квадратов.
Можем ли мы придумать другой тип игры?
Детерминированная версия
Теперь у нас есть ИИ, способный идентифицировать все логические шаги из заданного состояния игры. Иногда вы не сможете найти логические шаги. В таких ситуациях игрок должен угадывать и может проиграть, если ему не повезет.
Что, если мы добавим еще одно правило? Когда у игры нет логического пути развития, мы можем обратиться за помощью. Если ИИ соглашается, что игрок ничего не может с этим поделать, он приходит ему на помощь. В противном случае игрок сразу проигрывает. Это может быть интересно. Какая это может быть помощь? Возможно, следует открыть одну ячейку вне зависимости от наличия в ней мины:
Таким образом, мы полностью исключили ситуации, в которых можно было случайно проиграть.
Однако здесь есть одно исключение: все еще существует вероятность вырожденных ситуаций, когда глобальный решатель не может завершить свои вычисления за разумное время. К сожалению, это неизбежный результат того, что задача о сапе является NP-полной.
Как кнопка «Попросить о помощи» влияет на игровой процесс? Это делает игру более ориентированной на логику; это самая «загадочная» версия Bomb Squad. Вам может показаться, что игра становится проще, но на самом деле она становится сложнее. Теперь нет оправданий ошибкам игрока и кнопка накажет его, если он что-то упустит. Без кнопки легко сделать вывод, что вы исчерпали все логические возможности и единственный вариант — попытаться угадать наугад. Но благодаря наличию кнопки игрок точно будет прав в этой оценке.
В заключение
Благодаря реализации полного Решателя нам удалось создать вариант игры, свободный от его проклятия: теперь проиграть невозможно, потому что приходится выбирать случайным образом, когда все поле уже почти решено. Эта версия отличается от оригинальной игры только в тех моментах, где вам нужно угадывать наугад, поэтому я могу предположить, что она намного более захватывающая, чем оригинальная игра.
Мы также разработали версию игры, которая автоматически решает простые локальные правила. Стоит ли пользоваться такой помощью, решать только вам. Это смещает фокус игры с механического щелчка на более загадочный игровой процесс. Усиление игрового процесса, предоставляемое кнопкой «Попросить о помощи», не нужно использовать.
