logo
 
?

бот для игруна

Наверное каждый из нас когда-нибудь играл, или по крайней мере пробовал играть в «Сапёр» («Mine Sweeper»).

Логика игры проста, но в свое время за алгоритм ее прохождения даже обещали вознаграждение.

В моем боте логика имеет три алгоритма, которые используются в зависимости от ситуации на поле.

Основной алгоритм позволяет находить все ячейки со 100- и 0-процентной вероятностью нахождения мины.

Используя только этот алгоритм и открывая наугад произвольные ячейки при отсутствии достоверного решения в стандартном сапере на уровне «Эксперт» можно достичь 33% выигрышей.

Однако некоторые дополнительные алгоритмы позволяют поднять это значение до 44% (Windows 7). Неизвестные ячейки (класс Cell), прилегающие к одной открытой ячейке формируются в группу (класс Group), в которую записывается также значение ячейки, к которой она прилегает.

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

Обозначим (123,1) — группа состоит из ячеек 1,2 и 3, и при этом в них находится 1 мина. Алгоритм работает в два этапа: Рассмотрим как работает этот метод на примере ситуации, когда открыты всего две соседние ячейки со значениями 4 и 2.

Вероятности нахождения мин от ячеек 4 и 2 по отдельности равны 4/7=0,57 и 2/7=0,28 соответственно.

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

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

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