Comments 18
У меня было несколько идей в том же направлении, что и у автора:
- в случае захода в логические тупики (случай 3), вычислять для клеток вероятность выигрыша, если открыть именно ее
- посчитать вероятность подорваться на мине на кратчайшем наибезопаснейшем пути между двумя точками. В идеале нужно найти безопасный путь, но если солвер захотит в тупик (случай 3), то нужно найти наиболее безопасный
- найти этот путь
Мне кажется, что поле надо просто подбирать таким образом, чтобы оно было решаемо.
Потому что когда в финале такая картинка (утрирую, поле 3х3):
___
121
???То скучно играть в рулетку.
000
121
*2*
получится, по-другому никак. При условии, что верхние прочерки — это нули или не важные нам в данном случае цифры.
1?
А если так?
Конечно такие моменты бывают. Но приведенный выше пример — не в их числе)
Цель игры — определить, где расположены мины, а не открыть все поля. В таком случае перебор всех возможных вариантов предсталяет собой единственный 100% беспроигрышный вариант прохождения.
А, пардон. Трудно в обратную сторону придумывать, но вы поняли. Такие моменты бывают — когда вероятности для двух клеток одинаковы и нет никаких других подсказок.
Хех, сапер :)
Когда то писал подобный, тока не с автоматизацией открытия, а с подсказками — поля с гарантированными/отсутствующими минами помечались. Дальше уж как игрок стилусом в кпк ткнет.
Новому игроку несложно будет понять, что если количество соседних мин, то есть число, показанное в клетке, равно количеству неоткрытых соседних клеток, то все эти клетки должны быть минами, поэтому на них надо поставить флажки. Аналогично, когда количество соседних мин равно количеству соседних флагов, то оставшиеся неоткрытыми соседние клетки должны быть пусты.
Собственно пока игрок с этим разбирается ему интересно, после происходит одно из трёх:
- Игрок теряет интерес к сапёру
- Игрок играет на скорость, выполняя тот же самый несложный алгоритм
- Игрок программист и начинает выдумывать решалки и ИИ для сапёра.
Несмотря на то что в статье даже упомянута NP-полнота, главная проблема статьи — решение локальной проблемы без математического взгляда на неё.
На самом деле решение сапёра не надо выводить из перебора и локальных правил, а наоборот, проще сформулировать и проанализировать саму задачу. В каждый момент времени игровое поле (открытые клетки с числами мин вокруг, закрытые и помеченные) представляет собой достаточно простую систему линейных уравнений (СЛАУ).
- Каждая закрытая клетка — переменная x[i], которая может принимать значение 0 — нет мины, или 1 — есть мина.
- Общее количество мин известно — N — вот у нас первое уравнение sum(x[i])=N
- Каждая открытая клетка с нераскрытыми и непомеченными — ещё одно уравнение. Если в такой клетке указано, что вокруг a[j] мин, то для соседних x[i(j)] будет уравнение sum(x[i(j)])=a[j]
- Помеченные клетки проще всего вычитать из соседних открытых.
- Общее количество переменных не превышает количества клеток поля. Посмотрел сейчас — это всего 16*30=480 в режиме "Эксперт". Ну право же — даже банальным Гауссом можно чуть ли не на порядок большие СЛАУ решать. Но тут Гаусс почти не нужен, потому что...
- … СЛАУ разреженная. В ней только одно уравнение со всеми переменными с коэффициентами 1. Все остальные — не более 8 переменных с коэффициентами 1.
- А еще упрощает, что нам не нужно искать пространство решений, а достаточно найти точное значение только одной из переменных x[i]: если в этой переменной 0, то у нас появляется новое уравнение, а если 1, то одно уравнение становится проще.
- А если даже ни одно точное решение переменных не найдено, то из коэффициентов СЛАУ можно достаточно легко можно получить значения для сравнения вероятности того, что там бомба.
Реально даже в середине игры будет получаться СЛАУ не более чем из 50 уравнений. Причем с кучей возможности оптимизаций (разреженная, коэффициенты 0 или 1, значения переменных допустимы только 0 и 1, свободные члены все кроме одного в 1..8, все уравнения, кроме одного — не более 8 переменных, часто матрица разваливается на отдельные кластеры).
Да, есть ситуации (как приведённая в статье 6х6 на 4-м рисунке), что в действительных числах решений много, а в {0, 1} только одно. Но такие ситуации легко диагностируются (неупрощаемая часть СЛАУ с большим количеством переменных), для небольших ситуаций можно использовать перебор. Кстати, в той картинке на 8 мин и 20 закрытых ячеек полный перебор — всего лишь 125970 вариантов.
Так что, NP-полнота на этих объёмах не делает ни жарко, ни холодно. Упомянутых ситуаций, в которых глобальный солвер не может закончить вычисления за разумный промежуток времени тут практически не может быть.
Я писал такое решение Сапёра очень-очень давно (году в 2001).
Как решить «Сапёра» (и сделать его лучше)