Obsessive robot (bluxer) wrote,
Obsessive robot
bluxer

Minesweeper Icon

САПЕР: ПУТЬ ОТ СЛУЧАЙНОГО К НЕОБХОДИМОМУ


В статьях о Сапере обычно пишут в таком духе: если позицию невозможно просчитать, скорее нажимайте наугад и при проигрыше начинайте новую игру, не теряйте время.
Жаль, что умные люди, да еще и склонные к работе с числами, советуют такое. Расположение найденных мин на поле тоже бывает источником данных (пусть и вероятностных). Образно выражаясь, эту мокрую тряпку следует отжать насухо, насколько хватит сил.

Например.
Если у нас стандартное поле из 16*30=480 клеток, а мин на нем 99, то квадратики из 4 мин встречаются довольно часто. Прямоугольнички из 6 тоже встречаются. Прямоугольники из 8 мин хотя и очень редко, но встречаются. Квадраты из 9 мин не встречались в моей практике ни единого раза:

Расклад

На этом примере мы видим, как случайное постепенно превращается в необходимое.

Какова вероятность появления на поле квадрата из k мин? (пусть к нему вплотную стоят еще мины, нас интересует только сам квадрат, неважно на фоне чего).

Насколько я понимаю, эта задача аналогична вот такому типу задач из курса теории вероятностей:

«В лотерее из N билетов K – выигрышные. Куплено n лотерейных билетов. Найти вероятность того, что из них ровно k выигрышных», которые легко решаются в Экселе с помощью формулы гипергеометрического распределения.


Наша «фигура» (квадрат) по сути – тот же набор случайно приобретенных лотерейных билетов. Почему случайно? Потому что это на самом деле никакая не фигура, а только кажется таковой (для сравнения: подлинная «фигура» – это как вот здесь, например, то есть нечто, формируемое по определенным внутреннее присущим ей законам).

Просто визуально для нас это упорядоченный набор, да еще и соответствующий прочно сидящему в сознании понятию («квадрат»), что немаловажно!


Итак, у нас общий «тираж лотерейных билетов» =480, из них "выигрышных" 99:

Если мы "купили" 4 "лотерейных билета", какова вероятность, что все будут выигрышными? 0,001723.

(Тут надо еще учесть, что квадрат 4 на 4 может возникнуть в 15*29=435 местах поля, но нас интересует, как правило, точное расположение).

Если же мы "купили" 9 "билетов", то все они будут выигрышными с ничтожной вероятностью. Эксель показывает 5,01E-07 (я не знаю, как это читается :)

Благодаря такому подходу, во многих случаях можно уверенно предположить, насколько правдоподобна позиция (хотя, увы, не всегда, потому что "колебание правдоподобия" может быть небольшим).
"Раскрываемость" у меня повысилась процентов на 20.
Tags: Околоматематика
Subscribe

  • (no subject)

    Не хотелось ничего писать накануне Дня Победы, а тем более в сам день, но вдруг зачесалось. Кто-то из здешних всезнаек когда-то заметил, что…

  • (no subject)

    Надеюсь, никто из присутствующих никогда не испытывал настоящий голод. Я тоже. Однако время конца 80-х - начала 90х принято называть «голодным».…

  • (no subject)

    К ТЕОРИИ СЛОЖНЫХ СИСТЕМ (а других и не бывает, не так ли? :) В метро СПб есть только один тройной переход между станциями, и тот появился…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments