MiniMax Algorithm: Функция стоимости / оценки?

Question

Школьный проект у меня написал дату игры в C ++ (пример в http://www.cut-the-knot.org/curriculum/games/date.shtml.) Если компьютерный плеер должен реализовать алгоритм MiniMax с помощью Alpha-Beta Creuning. До сих пор я понимаю, какова цель позади алгоритма с точки зрения максимизации потенциальных достижений, при условии, что противника будет их помимо.

Тем не менее, ни один из ресурсов, которые я читал, помог мне понять, как разработать функцию оценки MiniMax Base все это решения. Все примеры имели произвольные номера, присвоенные к узлам листа, однако мне необходимо на самом деле назначать значимые значения тем узлам.

Интуиция говорит мне, что это будет что-то вроде +1 для узела победа, а -1 для потери, но как оценивают промежуточные узлы?

Любая помощь будет наиболее ценится.

Answer 1

Наиболее основным MiniMax оценивает только узлы листьев, маркировку выигрышей, потери и рисунки, а также поддерживают те значения дерева, чтобы определить значения промежуточных узлов. В случае, если дерево игры неразрешимо, вам необходимо использовать глубину среза в качестве дополнительного параметра к вашим функциям MiniMax. Как только глубина будет достигнута, вам необходимо запустить некоторую функцию оценки для неполных состояний.

Большинство функций оценки в MiniMax Search являются конкретными доменом, поэтому нахождение помощи для вашей конкретной игры может быть сложной. Просто помните, что оценка должна вернуть какой-то процентное ожидание позиции, являющейся победой для конкретного игрока (обычно MAX, хотя и не при использовании реализации негамакса). Около почти менее исследованная игра будет близко напоминать еще одну более исследованную игру. Эта однажды связана очень близко с игрой Пикап палочки. Отказ Используя только MiniMax и Alpha Beta, я догадаю, что игра будет проделана.

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

Начните искать способ заставить результат, глядя на положение терминала и все движения, которые могут привести к этой позиции. В игре в палочках терминальная позиция с 3 или меньше палочек, оставшихся в последнем ходу. Положение, которое сразу же вырубается, что положение терминала, следовательно, оставляют 4 палочки к вашему противнику. Цель сейчас покидает своего противника с 4 палками, независимо от того, что, и это можно сделать с 5, 6 или 7 палочек, оставленных вам, и вы хотели бы заставить своего противника оставить вас в одном из этих позиций. Место вашего оппонента должно быть для того, чтобы вы были в 5, 6 или 7, это 8. Продолжить эту логику включения и включенным, и шаблон становится доступным очень быстро. Всегда оставляйте своего противника с номером, делимым на 4, и вы выигрываете, все остальное, вы проиграете.

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

Удачи, дайте нам знать, что вы в конечном итоге делаете.

Answer 2

Самый простой случай функции оценки составляет +1 для выигрыша, -1 для потери и 0 для любой неконфигурированной позиции. Учитывая ваше дерево достаточно глубоко, даже эта простая функция даст вам хороший игрок. Для любых нетривиальных игр с высоким ветвным фактором, как правило, вам нужна лучшая функция, с какой-то эвристикой (например, для шахмат, которые вы можете назначить веса к кускам и найти сумму и т. Д.). В случае игры дата, я бы просто использовал самую простой функцию оценки, с 0 для всех промежуточных узлов.

Как сбоку, MiniMax не является лучшим алгоритмом для этой конкретной игры; Но я думаю, вы это уже знаете.

Answer 3

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

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

Ваш алгоритм MiniMax (без обрезки Alpha-Beta) будет выглядеть что-то подобное:

A_move(day):
   if day==December 31:
       return +1
   else:
       outcome=-1
       for each day obtained by increasing the day or month in cur_date:
           outcome=max(outcome,B_move(day))
       return outcome

B_move(day):
   if day==December 31:
       return -1
   else:
       outcome=+1
       for each day obtained by increasing the day or month in cur_date:
           outcome=min(outcome,A_move(day))
       return outcome