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

Question

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

Answer 1

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

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

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

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