Можно ли выполнить обрезку в алгоритме expectiminimax?
Я использую алгоритм expectiminimax, который отлично работает в моей текущей ситуации:
max -> min -> chance -> max -> min -> chance -> (repeat)
Я никак не могу сделать
max/min -> Chance -> (repeat)
благодаря тому, как игра работает.
Я чувствую, как будто альфа будет неточной, если я продолжу преобразовывать мой алгоритм.
Есть ли какие-либо побочные эффекты для реализации обрезки (кроме эффекта горизонта) с моей текущей настройкой, или я просто обдумываю это?
2 ответа
Похоже, что обрезка все еще держится в этой среде, у меня были серьезные сомнения, но пока все проверено. Иными словами, все тестовые случаи в алгоритме отсутствия отсечения и алгоритме отсечения обеспечивали одинаковое перемещение с одинаковой эвристикой только в меньшем количестве узлов.
Я также обнаружил, что в моем случае я бы отказался от контроля над случайными узлами для пользователя (они могут определить приемлемые потери, если таковые имеются для определенных событий). Если у способности есть 95% -й шанс попасть, а 5% -ый шанс пропустить пользователя может посчитать, что эти 5% пренебрежимо малы и игнорировать шанс промаха, это не означает, что эвристика рассматривается как 100% ее значения. сохраняет свои 95%. У меня были редкие ситуации, в которых 16 возможных результатов могли быть получены при использовании 1 способности с учетом условий, и я хотел гибкости в такой ситуации.
Что касается игры, то она будет похожа на покемонов по крайней мере с точки зрения стиля игры.
Я не уверен, какую игру вы пытаетесь реализовать, но она звучит интересно. Очень трудно придумать хороший ответ, когда мы ничего не знаем о факторе ветвления любого из узлов или о том, как проходит игра. Я думаю, что это действительно зависит от вашей игры.
Я пробовал разные методы сокращения в игре в нарды, и, основываясь на этом опыте, я действительно думаю, что результат вашего алгоритма поиска зависит от того, насколько случайный узел влияет на ожидание игры по сравнению с тем, насколько минимальный и максимальный узлы изменяют ожидание.,
Если случайный узел может кардинально изменить ожидание игры (высокая дисперсия для каждого броска костей), но выбор из пяти-шести ходов не сильно меняет ситуацию, тогда я не думаю, что вам следует сильно волноваться.
Однако, если все наоборот, случайные узлы в основном просто движут игру вперед, не влияя на ожидание результата игры, и ходы (или действия) игры действительно важны, я думаю, вы можете получить много, получив хороший алгоритм поиска.
Проверьте также *-минимаксный алгоритм. (Брюс Баллард, 1983)
То же самое относится к Expectiminimax и *-minimax как обычный минимакс. Попробуйте сначала предположить лучшие ходы (из некоторой эвристики), чтобы создать отсечки, но вы также должны попытаться эвристически упорядочить случайные результаты в случайных узлах.
На самом деле это действительно интересно, когда вы начинаете тестировать это, но единственный способ получить хорошие ответы - это испачкать пальцы и попробовать.
Удачи!