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)

    Дверь как предостережение... ... о грядущей катастрофе. Лет 7 назад через дорогу вдоль моего дома шла активная стройка с забиванием свай. С тех пор…

  • (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