Сапер

[RobinGood]

Собственно, у меня вопрос по расположению мин в горизонтальном прямоугольнике 4*1, над которым сверху флаг 3 1 2
Высчитал байесовскую вероятность данного неудачного сценария (второй сценарий это одна мина во второй или третьей ячейки)
Вероятность однаружения мины в ячейке равна $\frac{99}^{16\cdot 30}$$\approx 0.2$
Тогда вероятность сценария из двух мин выше будет равна $\frac{0.2^2 \cdot 0.8^2}{0.2^2 \cdot 0.8^2+2\cdot 0.2\cdot 0.8^3}=\frac{1}{9}$, но она сработала.
Собственно вопрос, нет ли ошибки в оценке вероятности?
И точно ли мины распределены равномерно? Смущают частые горизонтальные и вертикальные кластеры из мин

[dgwuqtj]

RobinGood в сообщении #1653283 писал(а):

И точно ли мины распределены равномерно?

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

[sergey zhukov]

dgwuqtj
А что, можно расставить так, чтобы нельзя было пройти? Иногда приходится и гадать, точного алгоритма прохождения нет (не гарантирован).

[RobinGood]

dgwuqtj в сообщении #1653285 писал(а):

смысле равномерно и независимо друг от друга? Так не бывает, мины обязаны не накладываться друг на друга.

Всевозможные расстановки мин равновероятны. Я это не учитывал, но это дает вклад еще меньше, чем мое округление вероятности

-- 05.09.2024, 11:03 --

dgwuqtj в сообщении #1653285 писал(а):

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

Да ладно

[B@R5uk]

Я так понимаю, у вас поле 16х30 с 99 минами. Вы открыли прямоугольник 5х7 с 8-ю или 9-ю минами в нём (до того, как игра показала вам где они, и игнорируя 2-ку справа от верхнего флага). Это даёт вероятность нарваться на мину в оставшемся поле

$$\frac{99-8}{16\cdot 30-5\cdot 7}\approx 0.2045$$

Более того, шанс попасть на пустую клетку (без цифры) раскрывающую значительную область и дающую много полезной информации значительно выше, чем в тех трёх клетках, что вы рассматривали.

И если даже делать выбор только по вероятности нарваться на мину, то всё таки посмотрите на двойку справа от верхнего флага: У неё одна из 8-ми ячеек уже содержит мину, одна уже открыта, две имеют мину с вероятностью 1/2 каждая, если рассматривать их независимо, и остальные 4-ре так и поросятся быть кликнутыми.

[dgwuqtj]

RobinGood в сообщении #1653287 писал(а):

Да ладно

Ну, это было так на моём старом компьютере с Виндой. Сейчас эту игру кто только не переписал, и кто знает, какие там алгоритмы...

[B@R5uk]

RobinGood в сообщении #1653283 писал(а):

Собственно вопрос, нет ли ошибки в оценке вероятности?

Я бы рассуждал так: у нас есть цифры 3 и 1 и четыре неоткрытых ячейки под ними. Какие возможны варианты? Очевидно, что эти три:

• вариант
  F312
  M--M
• вариант
  F312
  -M--
• вариант
  F312
  --M-

Вероятность нарваться на мину, в ячейке, что вы кликнули одна третья. Слишком велико, на мой взгляд.

-- 05.09.2024, 11:17 --

RobinGood в сообщении #1653283 писал(а):

И точно ли мины распределены равномерно?

Зависит от версии сапёра. В винде ХР мины раставлялись совершенно случайно, до того, как игрок начинал кликать по полю. В винде 7 мины расставляются после первого клика вне некоторой области вокруг этого клика. Но совершенно случайно.

dgwuqtj в сообщении #1653285 писал(а):

К тому же они всегда расставляются так, что игру можно пройти...

Сапёр был бы куда более интересным пазлом, если бы это было верно. Но это не так. Увы и ах. Во всяком случае я не встречал версий, которые бы гарантировали бы прохождение.

-- 05.09.2024, 11:27 --

RobinGood, для двойки справа от флага возможны вот эти 6 вариантов:

• вариант
  ___1M
  __12-M
  112F2-
  -M2---
• вариант
  ___1M
  __12--
  112F2M
  -M2---
• вариант
  ___1M
  __12--
  112F2-
  -M2--M
• вариант
  ___1M
  __12--
  112F2-
  -M2-M-
• вариант
  ___1-
  __12M-
  112F2-
  -M2---
• вариант
  ___1M
  __12--
  112F2-
  M-2M--

Отсюда, кликая на упомянутые мной четыре ячейки, шанс нарваться будет 1/6, что значительно лучше, где бы то ни было ещё. Вообще говоря, любые шесть ячеек вокруг двойки дают этот шанс, но наиболее правые ячейки имеют больший шанс оказаться пустыми и дать больше полезной информации будучи открытыми.

[Mihr]

B@R5uk в сообщении #1653290 писал(а):

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

Я встречал. Довольно давно, точно год не назову. Как ориентир: тогда ещё использовались ОС Win98, Win2000. Игра называлась "Сапёр с подсказкой". Погуглите, может, где-то игра и сохранилась до сегодняшнего дня.

[B@R5uk]

Mihr, я больше думал в сторону составления пазла таким образом, чтобы нужно было для каждой очередной открываемой ячейки делать как можно больше логических заключений, при этом никогда не заходя в тупик. Обычно сапёр решается применением очень небольшого набора правил практически до посинения. Периодически натыкаясь при этом на выбор 50-50 в квадрате 2 на 2 или просто для двух ячеек. Лишь изредка бывают ситуации, когда очередная ячейка без мины может быть вычислена из имеющихся на экране данных, но в несколько логических шагов. Если бы процедура составления пазла имела базу таких случаев и сплетала их воедино в одну большую головоломку — вот это было бы здорово!

А ещё я тут начал сомневаться, что приведённые мною выше случаи в группах равновероятны внутри каждой группы. Кто-нибудь может что-нибудь сказать по этому поводу? Есть ли доказательство?

[Anton_Peplov]

B@R5uk в сообщении #1653290 писал(а):

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

Вот здесь https://minesweeper.online/ru/ на панели слева выберите "Режим без угадывания".

[Mihr]

B@R5uk в сообщении #1653294 писал(а):

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

Игра, о которой я говорю, именно такова. Возможно, у неё неудачное название. Объясняется просто: в старых версиях Windows можно было потерпеть фиаско на первом же ходу, не открыв ни одной клетки, сразу же попав (случайно) на поле с миной. А в игре "Сапёр с подсказкой" уже в самом начале игры было открыто несколько рядом расположенных полей с цифрами (в этом и "подсказка", других подсказок там нет). Дальше оставалось лишь рассуждать и открывать поле за полем, расставляя, где нужно, флажки. Прохождение игры гарантировано, если игрок не допустил логических ошибок. Никаких случайных выборов "с подбрасыванием монеты" нет.

[mihaild]

B@R5uk в сообщении #1653294 писал(а):

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

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

[RobinGood]

B@R5uk в сообщении #1653290 писал(а):

Очевидно, что эти три:

вариант
F312
M--M
вариант
F312
-M--
вариант
F312
--M-
Вероятность нарваться на мину, в ячейке, что вы кликнули одна третья.

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

[B@R5uk]

RobinGood в сообщении #1653381 писал(а):

Они же не равновероятны

Почему? Вы можете это наглядно продемонстрировать?

[B@R5uk]

Хорошо. Пусть есть вот такое поле 4 на n+1, где n — количество нераскрытых строк по 4 ячейки:
.____.
|F22F|
|????|
|????|
...
|????|
'----'
Пусть в этих нераскрытых ячейках (помеченных знаком "вопрос") имеется m мин. Количество возможных размещений будет

$$N=C_{4n}^m=\frac{(4n)!}{(4n-m)!m!}$$

Будем считать, что все эти варианты равновероятны.

Три варианта размещений мин во второй строчке и количество способов разместить мины в оставшихся ячейках будут такими:

• вариант 1:
  |F22F|
  |M--M|
  
  $$N_1=C_{4n-4}^{m-2}=\frac{(4n-4)!}{(4n-m-2)!(m-2)!}$$
  
  
• вариант 2:
  |F22F|
  |-M--|
  
  $$N_2=C_{4n-4}^{m-1}=\frac{(4n-4)!}{(4n-m-3)!(m-1)!}$$
  
  
• вариант 3:
  |F22F|
  |--M-|
  
  $$N_3=N_2$$

Убедимся, что

$$N=N_1+N_2+N_3$$

$$N_1+N_2+N_3=\frac{(4n-4)!}{(4n-m-2)!(m-2)!}+\frac{2(4n-4)!}{(4n-m-3)!(m-1)!}=$$

$$=\frac{\left(\,m-1+2(4n-m-2)\,\right)(4n-4)!}{(4n-m-2)!(m-1)!}=\frac{(8n-m-5)(4n-4)!}{(4n-m-2)!(m-1)!}$$

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

$$N'=N_1+N_2+N_3=\frac{(8n-m-5)(4n-4)!}{(4n-m-2)!(m-1)!}$$

И вероятности первого, второго и третьего вариантов будут:

$$p_1=\frac{N_1}{N'}=\frac{m-1}{8n-m-5}$$

$$p_2=p_3=\frac{N_2}{N'}=\frac{4n-m-2}{8n-m-5}$$

Их сумма равна единице, как и должно быть. Теперь конкретные цифры. Из картинки



можно прикинуть, что

$$4n=16\cdot 30-5\cdot 7+4=449,\quad m=93$$

вероятности для этих значений:

$$p_1=\frac{m-1}{8n-m-5}=\frac{93-1}{2\cdot 449-93-5}=\frac{92}{800}=0.115$$

$$p_2=p_3=\frac{4n-m-2}{8n-m-5}=\frac{449-93-2}{2\cdot 449-93-5}=\frac{354}{800}=0.4425$$

ОК, вы правы. Встретить две мины в четырёх ячейках значительно менее вероятно (почти в 4 раза), чем одну. Всё потому, что средняя плотность мин на поле мала. Если бы выполнялось

$$4n-m\approx m$$

то есть плотность мин была бы

$$\frac{m}{4n}\approx\frac{1}{2}$$

то вероятности вариантов выше были бы почти равны.

Спасибо за указание интересного факта! TIL.