2 соревновательных ИИ с минимаксом - PullRequest
Новая
       72

2 соревновательных ИИ с минимаксом

1 голос
/ 03 ноября 2019

Упрощенные правила игры:

  • Пешки могут двигаться один раз за ход.
  • Пешки могут двигаться в 4 направлениях. (вверх, вниз, влево, вправо)
  • Пешки движутся по сетке, как шахматная доска.
  • Пешка, достигающая выигрыша другого ряда.
  • Другие правила можно игнорировать дляпростота.

Функция оценки:

  • Если reached to the target, return 100.
  • Остальное: return Opponent Distance From Target - Own Distance From Target

Я реализовал minimax с alpha-beta pruning и указал max-depth. Я сравнил свою реализацию с несколькими сторонними реализациями, и она выглядит одинаково. Итак, вместо вставки моей реализации, я хочу задать свой вопрос напрямую:

Когда 2 ИИ конкурируют друг с другом. Они становятся неспособными выбрать осмысленное направление, как только обнаруживают, что кто-либо из них выигрывает матч, потому что счет становится одинаковым для более чем 1 выбора. Выбор любого из этих вариантов случайным образом не улучшит его, поскольку он движется бессмысленно навсегда.

Является ли это (тупик) ожидаемой вещью? Если нет, в чем может быть проблема? Если так, как я могу это исправить?

1 Ответ

0 голосов
/ 04 ноября 2019

Да, это может легко произойти с простой реализацией альфа-бета / минимакс.

Лучшее решение для этого, вероятно, - итеративное углубление - итеративный поиск в слое 1 ... макс. Это хорошо работает по нескольким причинам:

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

  2. Когда вы получаете выигрыш для себя на данной итерации, вы немедленно завершаете работу (например, не продолжаете искать более крупные итерации) и делаете ход победы. Это позволяет избежать проблемы поиска длинных выигрышных последовательностей и не брать самые короткие. (Решение вашей проблемы.)

  3. Вы можете использовать что-то вроде эвристики истории на ранних итерациях, чтобы улучшить порядок на последующих итерациях и повысить эффективность альфа-бета. (Что не имеет значения, если вы ограничиваете максимальную глубину, но если вы вместо этого ограничиваете время, это может быть полезно.)

...