Минимаксный алгоритм: функция стоимости / оценки?

Question

В школьном проекте я пишу игру Date на C ++ (пример: http://www.cut -the-knot.org / Curriculum / Games / Date.shtml ), где компьютерный игрок должен реализовать алгоритм Minimax. с альфа-бета-обрезкой. До сих пор я понимаю, какова цель алгоритма с точки зрения максимизации потенциальных выгод, при условии, что противник минимизирует их.

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Как примечание: минимакс не лучший алгоритм для этой конкретной игры; но я думаю, ты уже знаешь это.

Answer 3

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

В этом случае это только вопрос присвоения выигрышной позиции значения 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