[Пятничный перевод статьи 1999 года одного из авторов движка игры Thief Шона Барретта]

Неприятное положение в «Сапёре»

В этом положении я знаю, что вокруг меня есть куча мин, но не могу определить, где они находятся. Несколько мин может быть в одном из двух мест (розовые или голубые), группа мин может быть расположена в одной из двух комбинаций (светло-/тёмно-зелёные). Кроме того, есть ещё сложная ситуация с «5» и «6» в левом верхнем углу, которую я никак не выделил.


Голубые/розовые — взаимоисключающие пары, светло-/тёмно-зелёные — взаимоисключающие группы

«Сапёр»: логика или вероятность

В «Сапёра» можно играть двумя способами: как в логическую или в вероятностную игру.

Технически, вероятность подразумевает логику. Если вы можете логически доказать, что мина должна находиться в определённом месте, то вероятность равна 100%. Если можете доказать, что её в этом месте нет, то вероятность равна 0%. То есть в каком-то смысле для нас важны только вероятности. Тем не менее, игрок для распознавания таких стопроцентных ситуаций игрок использует логическую дедукцию. Иногда, особенно на низких уровнях сложности, её достаточно для прохождения уровня, никакого подсчёта вероятностей не требуется.

Но бывают такие ситуации, когда вся логика мира не может вас спасти. Простой пример — ситуация с «T», которую видно внизу по центру. Она немного осложняется дополнительными соседними минами. (В простейшем случае «2» заменяется на «1», а «5» — на «3», чтобы ситуация была симметричной.)

Нет никакого способа получить больше информации о вероятном положении одной мины, оставшейся в одной из этих клеток. Шансы пятьдесят на пятьдесят — можете бросать монетку. Когда у вас получается что-то подобное, лучше сразу же сделать выбор и не откладывать на потом. Если догадка будет неверной, то вы хотя бы сэкономите время на решение остальной части поля. (Но лично я стремлюсь к завершённости, поэтому оставляю такие случаи на потом. И не вините себя за то, что не угадали. Когда победа или проигрыш зависят от броска монеты — это плохой гейм-дизайн.)

Тактика в конце игры

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


Возможные конфигурации мин в правом нижнем углу

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

Если счётчик говорит, что осталось три мины, то это необязательно конфигурация A. Это может быть схема B с оставшейся миной в одной из правых нижних групп клеток 3x3.

На самом деле, шансы в пользу конфигурации B.

Локальные вероятности

Если вы исследуете вероятности только «локально», вы видите, что каждая из клеток в отмеченных взаимоисключающих группах имеет шанс 50-50 быть миной. Говоря «локально», я подразумеваю, что если рядом с двумя неизвестными клетками есть «1», то вероятность спрятанной мины у каждой из них равна 50%.

Именно такая ситуация сложилась внизу в центре: каждая из соседних клеток, соседних к неизвестной паре, содержит в точности одну мину, то есть каждый из соседних фрагментов данных предполагает 50-процентную вероятность. В самом левом верхнем углу похожая ситуация:


С абсолютной точностью в каждом из розовых овалов есть по одной мине, то есть всего осталось 7 мин

Ситуация в правом нижнем углу тоже чем-то похожа: рядом с каждым из чисел на «границе» есть одна мина и две клетки, в которых она может быть.

Если рядом с клеткой есть одна скрытая мина, но три закрытых клетки, то вероятность мины в каждой из клеток составляет 33%; каждая из четырёх закрытых клеток имеет вероятность 25%. Если у нас две скрытые мины и три закрытых клетки, то каждая клетка имеет вероятность 66%.

Вот ситуация с «локальной вероятностью» для всего поля:



Как вы видите, несколько клеток в верхней левой области имеют несколько вероятностей; закрытая клетка рядом с «2» и «6» и одна рядом с «3» и «5». (Клетка рядом с «5» и «6» благодаря им всё равно имеет вероятность 66%, поэтому нет видимого несоответствия.)

Разрешение конфликтов локальной вероятности

Вы наверно, задаётесь вопросом, что значит наличие конфликтующих локальных вероятностей. Интуиция может подсказать, что наибольшая вероятность должна выиграть. Например, клетка между «6» и «2» должна на самом деле иметь 66%. Это будет значить, что у крайней левой клетки с вероятностью 50% она на самом деле равна 33%. Или можно попробовать как-то комбинировать приоритеты: возможно, вероятность будет 5/6 или средним значением.

Но ничто из этого на самом деле неверно. Данные, из которых получены вероятности, не независимы друг от друга, поэтому никакие прямолинейные математические расчёты не будут верными. Причина правильности локальной догадки о 50% внизу в центре в том, что она действительно независима ни от чего другого. Если случайным образом воссоздавать поле по уже имеющимся у нас данным, то ровно в половине из моделей мина будет в одной из двух клеток. (Вероятность иногда запутывает людей, которые не могут разобраться, какие правила расчёта вероятностей применимы в конкретной ситуации. Такой подход — это гарантировано верный путь, потому что он основан на определении вероятности в статистическом прогнозировании: вычисление выполняется измерением во всех возможных конфигурациях, которые могли привести к текущей ситуации, при этом все они считаются одинаково вероятными.)

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

Непосредственный подсчёт потребовал бы много времени. К счастью, существуют и другие способы.

Подсчёт конфигураций

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

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


Возможные конфигурации для левого верхнего угла

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

Теперь есть искушение воскликнуть: «ага, вот пять случаев, так что мы можем подсчитать количество случаев для каждой из возможных позиций мины». Например, мина находится в четвёртом ряду (рядом с левой нижней «1») находится слева в двух верхних случаях, и справа в трёх нижних случаях. Поэтому можно решить, что она имеет вероятность в 60% находиться справа, рядом с «6». (Это позиция с конфликтующими локальными вероятностями 50% и 66%.)

Однако мы упускаем одну тонкость — количество мин в некоторых случаях разное: в A1 шесть мин, в B2 — четыре, и по пять во всех остальных случаях.

Считаем ненайденные мины

Для подробного изучения этой тонкости давайте вернёмся к более простой ситуации в правом нижнем углу.


Возможные конфигурации с правом нижнем углу

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

Есть искушение предположить, что наиболее вероятна конфигурация A ровно с тремя минами. Но это неверно.

Ещё одно искушение — вспомнить, сколько всего было мин и сколько всего клеток, и сказать: «каковы шансы того, что нижняя область 3x3 будет пустой». Это тоже неверно. Очень сложно объяснить, почему это ошибка, наверно, её можно сравнить с парадоксом Монти Холла. Однако достаточно сказать, что в действительности шансы в этой ситуации не зависят от общего количества мин и размера поля.

Правильный ответ таков: сколько возможных конфигураций из трёх мин соответствуют нашим знаниям о поле? Из рисунка мы видим, что две: конфигурации A и B. Но в B всего две мины. Третья мина может быть в любой из клеток нижней области 3x3, о которой мы пока не собрали никаких данных. То есть всего есть девять вариантов конфигураций B, я просто не стал изображать их все.

Следовательно, существует всего десять возможных конфигураций. Каждая из десяти конфигураций равновероятна. (Как я упоминал ранее, это критически важно для понимания вероятности. Шансы того, что компьютер сгенерировал любой из этих вариантов малы, но они равно малы, потому что компьютер [насколько мы знаем] давал каждой конфигурации равные шансы. Вы с равной вероятностью можете выбросить конфигурацию из десяти «орлов» подряд и последовательность два «орла», одна «решка», один «орёл», три «решки», один «орёл», одна «решка» и один «орёл». Вероятнее выбросить в сумме пять «орлов» и пять «решек», но не никакую конкретную последовательность «орлов» и «решек». В «Сапёре» мы имеем дело с конфигурациями мин, которые похожи на последовательности бросков монеты.)

Поскольку каждая из десяти конфигураций (девять для B, одна для A) равновероятны, конфигурация B в данном случае имеет вероятность 90%!

Если бы на этом этапе было четыре мины, то у конфигурации A имелось бы девять вариантов. Конфигурация B имела бы по одному варианту для каждого варианта расположения двух мин в левом нижнем углу; это C(9,2), то есть 9!/((9-2)! * 2!) или 9*8/2, равное 36. В этом случае конфигурация B имела бы вероятность только 75%.

С пятью минами конфигурация A имела бы 36 вариантов, а конфигурация B — 9*8*7/6 = 84 варианта; то есть шансы B были бы чуть больше 66%.

В случае шести мин B имела бы вероятность 60%. С семью минами у B было бы всего 50%. С восемью минами B была бы менее вероятна, чем A; в этом случае с таким количеством мин в оставшихся позициях конфигураций становится меньше. Рассмотрим наихудший случай, когда осталось 11 мин. (Шанс этого чрезвычайно мал, но если такая ситуация возникнет, то применимы эти вероятности.) В конфигурации B, во всех закрытых клетках будут мины, в конфигурации A во всех, кроме одной. То есть существует 9 вариантов для A и всего один для B.

Окончательное решение

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

Может сложиться любая комбинация из левой верхней и правой нижней конфигураций, за исключением одной из них (A1 + A), для которой потребуется девять мин. Поэтому мы должны перечислить каждую из этих возможных конфигураций и сосчитать оставшиеся мины и закрытые клетки.

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

Вверху слева	Внизу справа	Количество мин	Осталось мин	Закрытые варианты
A1	B	8	0	1
B1	A	8	0	1
B1	B	7	1	12
A2	A	8	0	1
A2	B	7	1	12
B2	A	7	1	12
B2	B	6	2	66
C2	A	8	0	1
C2	B	7	1	12

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

Конфигурация	Варианты	Процент
A1	1	1
B1	13	11
A2	13	11
B2	78	66
C2	13	11
A	15	13
B	103	87

Далее я обошёл каждую клетку на поле и вычислил её вероятность, суммировав количество вероятностей, в которых она появляется, и поделив на 118. (На самом деле, просто сложив указанные выше проценты.) Кроме того, в среднем в каждой из закрытых клеток есть мина в 15 из 118 вариантов (то есть шансы на то, что по крайней мере в одной закрытой клетке есть мина, очень высоки). [Это можно вычислить умножением количества оставшихся мин на закрытые варианты, что даёт нам среднее количество мин в закрытых клетках.]


Вероятности наличия мины

(Следует сказать, что это не показывает всей доступной информации. Например, мы знаем, что вероятности двух тёмно-зелёных клеток с 87% связаны — если одна верна, то другая тоже. И голубые 13-процентные клетки, в которых есть мины по конфигурации A, тоже связаны. Остальные голубые 13-процентные клетки не связаны. Если в одной из них есть мина, вероятность того, что в любой из оставшихся есть мина, уменьшаются.)

Играем в игру

Скорее всего, играя в «Сапёра», вы не захотите корпеть над всеми этими вычислениями.

И я тоже.

Но я действительно перечислил все возможные конфигурации в левом верхнем и правом нижнем углах. Я заметил, что в одной конфигурации (B2-B) используется на одну мину меньше, чем во всех остальных, и применил проверенное временем правило «меньше мин — значит, больше закрытых вариантов» (которое действует приблизительно пока количество закрытых клеток меньше чем удвоенное количество ненайденных мин). Это означает, что намного вероятнее конфигурации с меньшим количеством мин.

Поскольку в левом верхнем углу было множество конфигураций, определение шансов для любой клетки довольно сложно. Поэтому я просто выяснил, что конфигурация B в правом нижнем углу намного более вероятна, и случайно выбрал одну из подходящих клеток. (Я надеялся, что она позволит мне закончить правый нижний угол, а потом, вооружённый большей информацией о количестве оставшихся мин, я смогу завершить левый верхний угол, после чего мне придётся бросить монетку для выбора внизу в центре. Разумеется, в идеале нужно было выбрать клетку, максимизирующую вероятность получения полезной информации, но любая из этих догадок позволила бы мне «войти» в правый нижний угол для дальнейшего сбора данных.) Шансы были выше у конфигурации B, поэтому я выбрал клетку, в которой была мина в конфигурации A.



Восемь раз из девяти я был бы прав.