Алгоритмы логики бота для игры «Сапёр» / Хабрахабр. Наверное каждый из нас когда- нибудь играл, или по крайней мере пробовал играть в «Сапёр» («Mine. Sweeper»). Логика игры проста, но в свое время за алгоритм ее прохождения даже обещали вознаграждение. В моем боте логика имеет три алгоритма, которые используются в зависимости от ситуации на поле. Основной алгоритм позволяет находить все ячейки со 1. Используя только этот алгоритм и открывая наугад произвольные ячейки при отсутствии достоверного решения в стандартном сапере на уровне «Эксперт» можно достичь 3. Однако некоторые дополнительные алгоритмы позволяют поднять это значение до 4.
Алгоритмы логики бота для игры «Сапёр». Во-вторых большое спасибо за предложения, попробую внедрить их в программу. Программы "Умный сапер" и "Помощник сапёра" являются вспомогательными для игроков в сапёра. Они будут самостоятельно ставить за игрока флаги .
Windows 7). Основной алгоритм. Основной алгоритм состоит в следующем. Неизвестные ячейки (класс Cell), прилегающие к одной открытой ячейке формируются в группу (класс Group), в которую записывается также значение ячейки, к которой она прилегает. Обозначим (1. 23,1) — группа состоит из ячеек 1,2 и 3, и при этом в них находится 1 мина.
Для этого: Сравниваем каждую группу с каждой последующей группой. Если группы одинаковые, то вторую удаляем.
Если одна группа содержит другую, то вычитаем из большей меньшую. То есть было две группы (5. Метод создания и преобразования групп/**. Создает список групп ячеек, связанных одним значением открытого поля, а также разбивает их на более мелкие, удаляет повторяющиеся.
В этом суть основного алгоритма. Если нет достоверного решения. Но часто встречаются ситуации, когда нет достоверного решения ситуации.
Тогда на помощь приходит следующий алгоритм. Его суть состоит в использовании теории вероятности. Алгоритм работает в два этапа: Определение вероятности в отдельных ячейках, учитывая влияние нескольких открытых ячеек Корректировка вероятностей, учитывая взаимное влияние групп с общими ячейками друг на друга. Рассмотрим как работает этот метод на примере ситуации, когда открыты всего две соседние ячейки со значениями 4 и 2.
Вероятности нахождения мин от ячеек 4 и 2 по отдельности равны 4/7=0,5. А=1- (1- A1)*(1- A2)*..*(1- An) В смежных ячейках после применения этой формулы результат равен 1- (1- 0,5. Поэтому все значения в каждой группе нужно домножить так, чтобы в итоге их сумма была равна числу мин. Это число равно количеству мин в группе, деленое на текущую сумму вероятностей ячеек группы: 4/(0,5. Теперь те ячейки, что имели вероятность 0,5. Зная это количество можно перебором подставлять их в неизвестные ячейки, и отмечать подходящие варианты.
В процессе перебора подходящих вариантов для каждой ячейки считаем количество пометок. Разделив получившиеся значения на общее число пометок получаем вероятность нахождения мин для каждой ячейки.
Например в этой ситуации, имеющей, казалось бы только одно достоверное решение последний метод (Last. Turns) нашел 3 ячейки с 0% вероятности нахождения мины. Можно использовать только если количество неизвестных ячеек не больше 3. Array. List< Point> get.
Last. Turns() . В следующей таблице приведены результаты работы бота на «Сапер» под Windows XP в течение одной ночи, где Расчетный % Общее кол- во открываний ячеек с расчетным % Кол- во попаданий на мину Фактический %1. Презентация Развивающие Игры 6-7 Лет. Большое расхождение в области 2. Сапер» подстраивался под игрока, иногда убирая из- под открываемой ячейки мину. Алгоритм работы был реализован на java и опробован на стандартном сапере Windows (7 и ХР), приложении в VK и на игруне.
К слову сказать, после нескольких дней «технических неполадок» при доступе на мой аккаунт с моего IP игрун изменил правила вознаграждения за открытие части поля: изначально возвращал 1.