Возможное решение алгоритма ИИ для кратчайшего пути

Мне нужен совет по эвристике для игры "Сапер". Если найдено 10 полей без моего, мне любопытно, как оценить, какое поле должно открываться следующим? Я думал о том, чтобы найти возможность для мин вокруг каждого поля с номером, и в конце вычислений выбрать поле с наименьшей вероятностью, но я не думаю, что это даст мне хорошие результаты, потому что мне нужно открыть уже безопасное поле и что Мне нужно открыть поле, которое откроет самую большую область на доске. Хотелось бы читать хорошие идеи, но только без алгоритмов накрутки.


algorithm path-finding minesweeper heuristics
person user1973035    schedule 20.04.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете попробовать поиск A * с моделированием Монте-Карло. То есть определить стоимость/вознаграждение для каждого типа открываемой ячейки (каждого типа действия).

Предположим, у вас есть K различных действий, которые вы можете выполнить (a_1,a_2,a_3...) на текущем временном шаге.

  1. Для каждого действия (откройте ячейку X) и используйте игровую модель, чтобы смоделировать, что произойдет дальше. Сохраняйте награду за последовательность действий и накапливайте награду за исходное действие. Вы можете добавить вес вероятности к действиям и последствиям, чтобы сделать оценку более точной.

  2. Возьмите среднее значение смоделированных вознаграждений за каждое действие и последовательность действий. После M симуляций на глубине D (где M и D — это просто заранее определенные значения, чтобы гарантировать, что алгоритм не займет слишком много времени), выберите одно действие из (a_1,a_2,a_3...) с наивысшим симулируемым вознаграждением. Обрезка необходима, чтобы сделать этот метод эффективным (то есть, чтобы не тратить время на действия, которые точно не приведут к высокому вознаграждению после нескольких шагов моделирования)

person aaronqli    schedule 20.04.2013