Улучшение алгоритма решения Minesweeper

Я реализовал в Python алгоритм для решения игры "Minesweeper". Программа работает следующим образом:

Скажите, что решатель нажимает квадрат с именем 'a'. Для примера пусть число, показанное таким образом, равно 2. Соседи квадрата, которые еще не отброшены, являются (опять же в качестве примера) с именем "b" и "c". Затем программа связывает квадрат с выражением [2, {'b', 'c'}] и вырезает 'a' из всех других выражений. Вычисление тех квадратов, которые являются минами и которые не исчисляются путем простого упрощения таких выражений при двух обстоятельствах.

Если квадраты в одном выражении являются подмножеством квадратов другого выражения:
```
[2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}]
```
Если все квадраты в одном выражении установлены как мины:
```
[2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}]
```

Затем для некоторого выражения X, если X[0] == 0, мы можем щелкнуть все квадраты, названные в X[1], и если X[0] == len(X[1]), тогда мы можем их обозначить.

Я, однако, изо всех сил пытаюсь определить, какие пары выражений пытаются упростить. Мой текущий подход состоит в том, чтобы поддерживать стек квадратов; всякий раз, когда щелкнут квадрат или его выражение успешно упрощено, оно добавляется в стек (если его еще нет). Когда квадрат выталкивается из стека, делается попытка упрощения между его выражением (X) и любыми другими выражениями Y такими, что X[1] & Y[1] != set(). Алгоритм завершается, когда стек исчерпан. В настоящее время, однако, хотя это работает достаточно хорошо, оно не способно правильно решать все однозначные конфигурации и насколько хорошо оно выполняется на данной доске, значительно меняется, если я заменяю стек очередью или использую какой-то алгоритм, чтобы определить, какой квадрат для pop

Я был бы очень благодарен за любые примеры прецедента моего подхода или возможности потенциального исследования.

Ответ 1

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

Я считаю, что этот алгоритм был более способным, чем алгоритм, с которым вы работаете. Ваш подход может "решить" условие, если он полностью заполнен или пуст минами, или если он является подмножеством другого условия. Тем не менее, есть некоторые выводы, которые это не будет обрабатывать. Например, рассмотрите эту небольшую плату размером 7x2, где плитки a через h неизвестны:

a 2 1 2 1 2 i
b c d e f g h

Ваши условия будут:

[2, {a, b, c, d}],
[1, {c, d, e}],
[2, {d, e, f}],
[1, {e, f, g}],
[2, {f, g, h, i}]

Если я правильно понял, ваш алгоритм не может делать никаких выводов об этом. Однако, если вы опытный игрок Minesweeper, вы поймете, что шаблон 1 2 1 в центре имеет только одно решение с минами ниже 1 s:

a 2 1 2 1 2 i
b 2 * 2 * 2 h

До сих пор неизвестные, с миной под a или b, а другая - под h или i, но если это было частью более крупной головоломки, вы могли бы увидеть их позже ( или вам, возможно, придется догадаться).

Я считаю, что мой подход к минам работал следующим образом:

Для каждого фрагмента, который был расширен, соберите один набор всех его нерасширенных соседей ("area") и список, содержащий все наборы мины, которые могут встречаться в этой области. Так, например, 5 известных фрагментов в приведенном выше примере генерируют (слева направо):

 ({a, b, c, d}, [{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}])
 ({c, d, e}, [{c}, {d}, {e}])
 ({d, e, f}, [{d, e}, {d, f}, {e, f}])
 ({e, f, g}, [{e}, {f}, {g}])
 ({f, g, h, i}, [{f, g}, {f, h}, {f, i}, {g, h}, {g, i}, {h, i}])

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

Если бы произошло перекрытие, новое условие охватывало бы объединение их областей. Что касается наборов мины, я бы сделал декартово произведение внешних множеств, чтобы получить пары внутренних множеств, а затем проверить, было ли противоречие. Противоречие было бы, если бы в пределах пересечения областей два набора не имели ровно одинаковых шахт. Если бы не было никакого противоречия, новый союзный набор был бы сформирован из союза шахт. Здесь как первые две строки выше будут объединяться:

 Intersection of areas: {a, b, c, d} & {c, d, e} = {c, d}
 New combined area: {a, b, c, d} | {c, d, e} = {a, b, c, d, e}
 Cartesian product of mine sets (with X marking contradictions):
    |   {a, b}  {a, c}  {a, d}  {b, c}  {b, d}  {c, d}
 ---+-------------------------------------------------
 {c}|     X     {a, c}    X     {b, c}    X       X
 {d}|     X       X     {a, d}    X     {b, d}    X
 {e}| {a, b, e}   X       X       X       X       X

 New condition: ({a, b, c, d, e}, [{a, b, e}, {a, c}, {b, c}, {a, d}, {b, d}])

Вы можете рассчитать шансы любой плитки в области условий, являющейся мином, просто подсчитав, сколько из наборов она является частью, относительно того, сколько наборов есть общее. Поэтому, учитывая комбинированное условие выше, вы можете понять, что a является миной 3/5-й секунды, тогда как e - только 1/5 раз. Эта информация важна, когда программа должна угадывать местоположение, которое нужно развернуть, когда нет никаких безопасных плиток. Я думаю, что я также сделал некоторые сложные комбинаторики, чтобы учесть количество используемых мин (так что вышеприведенный случай {a, b, e} был бы взвешен немного иначе, чем другие случаи, поскольку он использует три мины, а не два), но я боюсь, что не помню подробностей.

Minesweeper - довольно сложная игра. Я считаю, что моя программа смогла разрешить доски, эквивалентные "трудным" трудностям примерно в 50-60% случаев, причем большая часть потерь происходит либо в начале (когда вы должны угадывать с небольшим количеством информации для работы), либо конец (когда часто есть несколько неразрешимых областей, которые необходимо угадать). Обычно это было довольно быстро, хотя изредка существовал узор плиток, который заставлял его болеть в течение 10 или 15 секунд, прежде чем сделать следующий шаг. (Minesweeper NP-complete, поэтому неудивительно, что некоторые входы не могут быть решены быстро!)

Ответ 2

Это то, что напомнило мне, я не смог полностью понять, каким был ваш метод.
Я надеюсь, что представление моей в графической форме поможет вам сэкономить ваши усилия.

Изображения идут в "порядке чтения".

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

Я чувствую себя немного слепым, потому что не видел этого раньше.

Все, что имеет значение, которое нормализуется до 100%, во всех случаях я могу найти, шахта.