Решение проблемы "промедления" в минимаксах
Я внедряю минимакс для маленькой игры и замечаю то, что я называю "промедление". Сводится к очень простому примеру:
В игре "захват флага" флаг находится на одну клетку ВВЕРХ от игрока А, а игрок Б - в 50 местах. Это ход А, и он может искать 6 ходов вперед. Я вижу, что все возможные ходы имеют значение "Победа", так как А знает, что он может добраться до флага до В, даже если он не захватывает его немедленно. Так что, если UP является последним ходом в ордере, он просто пойдет ВЛЕВО и ВПРАВО на некоторое время, пока B не окажется в пределах досягаемости, а затем он должен наконец получить флаг.
Поначалу поведение выглядело как ошибка, но, пройдя его, я убедил себя, что каждый ход действительно является "победой", но поведение не очень хорошее. Я мог повлиять на оценку, сделав флаг, захваченный на 4 шага, менее ценным, чем флаг, захваченный сейчас, но мне было интересно, есть ли какой-то аспект в поиске минимакса, чем я пропускаю? Существует ли какая-либо концепция, согласно которой высокий балл раньше был наиболее желательным, чем столь же высокий балл, полученный только позже?
1 ответ
В самом минимаксном поиске нет ничего, что сделало бы выигрыш более предпочтительным. Поскольку все конечные позиции оцениваются с одинаковым счетом, алгоритм эффективно выбирает случайный ход. Сделайте так, чтобы ваша оценочная функция немного уменьшала выигрышный балл для каждого уровня глубже в дереве, где она вызывается, и минимакс выберет выиграть раньше.