Алгоритм Minimax / Alpha Beta - Нахождение движения ИИ в Гомоку

Question

Я понимаю, что дерево решений Minimax - это хороший подход к реализации ИИ для настольной игры.В настоящее время я пытаюсь реализовать игру под названием Gomoku (5 подряд).Но есть одна вещь, которая меня смущает:

Я посмотрел вокруг, и кажется, что почти все алгоритмы Minimax / AlphaBeta возвращают целое число.Специально для меня возвращаемое значение eval (bestGomokuBoard).Как мне найти координату выигрышной доски?

Вот что я сделал до сих пор: у меня есть массив целых чисел 20x20, представляющий пустое пространство (0), компьютер (1)) и игрок (2).Чтобы уменьшить накладные расходы, каждый узел в минимаксном дереве представляет собой массив массива 9x9, представляющий больший массив (меньшую систему отсчета).Моя функция eval возвращает int, а мой алгоритм минимаксного / буквенного алфавита возвращает int.Как мне найти координаты движения ИИ?

И заранее спасибо!

Answer 1

Вы можете сделать две слегка отличающиеся max-функции.Одна, которая возвращает только целое число (оценка), и другая max-функция (например, maxWithBestMove или rootMax ), которая возвращает оценку и лучший ход.Порядок рекурсивного вызова будет следующим:

maxWithBestMove --> min --> max --> min --> max....

Взгляните на Примечание № 2 в Negamax Framework в вики по шахматному программированию.Аналогичный ответ я дал здесь .