Минимаксный алгоритм: функция стоимости/оценки?
Школьный проект имеет меня пишущий игру Даты в C++ (пример по http://www.cut-the-knot.org/Curriculum/Games/Date.shtml), где компьютерный игрок должен реализовать Минимаксный алгоритм с сокращением альфы - беты. К настоящему времени я понимаю то, что цель находится позади алгоритма с точки зрения максимизации потенциальных усилений при предположении, что противник уменьшит их.
Однако ни один из ресурсов, которые я считал, не помог мне понять, как разработать функцию оценки, минимакс основывает все, о чем это являются решения. Всем примерам присвоили произвольные числа вершинам, однако, я должен на самом деле присвоить значимые значения тем узлам.
Интуиция говорит мне, что это было бы что-то как +1 для вершины победы, и-1 за потерю, но как промежуточные узлы оценивают?
Любая справка больше всего ценилась бы.
3 ответа
Самый простой минимакс оценивает только листовые узлы, отмечая выигрыши, проигрыши и ничьи и поддерживает эти значения вверх по дереву, чтобы определить значения промежуточных узлов. В случае, если игровое дерево трудноразрешимо, вам нужно использовать глубину отсечения в качестве дополнительного параметра к вашим минимаксным функциям. Как только глубина будет достигнута, вам нужно запустить какую-то функцию оценки неполных состояний.
Большинство оценочных функций в минимаксном поиске зависят от предметной области, поэтому поиск помощи для вашей конкретной игры может быть трудным. Просто помните, что оценка должна возвращать какое-то процентное ожидание выигрыша позиции для конкретного игрока (обычно max, но не при использовании реализации Negamax). Практически любая менее исследованная игра будет очень напоминать другую, более исследованную игру. Этот очень тесно связан с игровыми пикапами . Я полагаю, что при использовании только минимаксного и альфа-бета игра легко управляема.
Если вам необходимо создать функцию оценки для нетерминальных позиций, вот небольшая помощь с анализом игры с клюшками, из которой вы можете решить, будет ли она полезна для игры на свидание или нет.
Начните искать способ форсировать результат, глядя на конечную позицию и все ходы, которые могут привести к этой позиции. В игре с клюшками конечная позиция - 3 или меньше клюшек, оставшихся на последнем ходу.Таким образом, позиция, которая немедленно следует за этой конечной позицией, оставляет вашему противнику 4 палки. Теперь цель состоит в том, чтобы оставить у вашего оппонента 4 палки, несмотря ни на что, и это можно сделать, оставив вам 5, 6 или 7 клюшек, и вы хотите заставить своего противника оставить вас в одной из этих позиций. Место, в котором должен находиться ваш оппонент, чтобы вы оказались в 5, 6 или 7, равно 8. Продолжайте эту логику снова и снова, и шаблон станет доступным очень быстро. Всегда оставляйте оппонента с числом, кратным 4, и вы выигрываете, все остальное вы проигрываете.
Это довольно тривиальная игра, но метод определения эвристики важен, потому что его можно напрямую применить к вашему заданию. Поскольку последний ход идет первым, и вы можете изменить только 1 атрибут даты за раз, вы знаете, что для победы должно быть ровно 2 хода ... и так далее.
Удачи, дайте нам знать, чем вы в конечном итоге занимаетесь.
Простейший случай оценочной функции - +1 за выигрыш, -1 за проигрыш и 0 за любую незавершенную позицию. Если ваше дерево достаточно глубокое, то даже эта простая функция даст вам хорошего игрока. Для любых нетривиальных игр, с высоким коэффициентом ветвления, обычно нужна более совершенная функция, с некоторой эвристикой (например, для шахмат можно назначить веса фигур и найти сумму, и т.д.). В случае с игрой "Свидание" я бы просто использовал простейшую функцию оценки, с 0 для всех промежуточных узлов.
В качестве побочного замечания, минимакс не является лучшим алгоритмом для этой конкретной игры; но я думаю, вы уже знаете это.
Из того, что я понимаю об игре Date, с которой вы связались, кажется, что единственные возможные исходы для игрока - это победа или поражение, а не промежуточное (пожалуйста, поправьте меня, если я неправильный).
В этом случае, это только вопрос присвоения значения 1 выигрышной позиции (текущий игрок получает до 31 декабря) и значения -1 для проигравших позиций (другой игрок получает до 31 декабря).
Ваш минимаксный алгоритм (без отсечения альфа-бета) будет выглядеть примерно так:
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