Дерево игры - Game tree

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

Первые два слоя игрового дерева для крестиков-ноликов.

На схеме показаны первые два уровня, или слои, в дереве игры для крестики-нолики. Вращения и отражения позиций эквивалентны, поэтому у первого игрока есть три варианта хода: в центре, на краю или в углу. У второго игрока есть два варианта ответа, если первый игрок играл в центре, в противном случае - пять вариантов. И так далее.

Количество листовые узлы в полном дереве игры указано количество возможных различных способов ведения игры. Например, дерево игры в крестики-нолики имеет 255 168 листовых узлов.

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

Игры для двух человек также можно представить в виде и / или деревья. Чтобы первый игрок выиграл игру, должен существовать выигрышный ход для всех ходов второго игрока. Это представлено в дереве и / или с помощью дизъюнкции для представления альтернативных ходов первого игрока и использования конъюнкции для представления всех ходов второго игрока.

Решение игровых деревьев

Версия детерминированного алгоритма

Произвольное полностью раскрашенное дерево игры.

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

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

На диаграмме показано игровое дерево для произвольной игры, раскрашенное с помощью описанного выше алгоритма.

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

Любое поддерево, которое можно использовать для решения игры, называется Древо решений, а размеры деревьев решений различной формы используются как меры сложность игры.^[2]

Версия рандомизированных алгоритмов

При решении деревьев игр можно использовать рандомизированные алгоритмы. У такого типа реализации есть два основных преимущества: скорость и практичность. В то время как детерминированная версия решения деревьев игр может быть выполнена в $Ο (п)$ , следующий рандомизированный алгоритм имеет ожидаемое время выполнения $θ (п 0.792)$ . Более того, это практично, потому что рандомизированные алгоритмы способны «помешать врагу», то есть оппонент не может победить систему игровых деревьев, зная алгоритм, используемый для решения игрового дерева, потому что порядок решения является случайным.

Ниже представлена реализация алгоритма решения рандомизированного дерева игр:^[3]

def gt_eval_rand(ты) -> bool:    "" "Возвращает True, если этот узел оценивается как выигрыш, иначе False" ""    если ты.лист:        возвращаться ты.победить    еще:        random_children = (gt_eval_rand(ребенок) за ребенок в случайный порядок(ты.дети))        если ты.op == "ИЛИ ЖЕ":            возвращаться любой(random_children)        если ты.op == "И":            возвращаться все(random_children)

Алгоритм использует идею "короткое замыкание ": если корневой узел считается"ИЛИ ЖЕ"оператор, затем один раз Истинный найден, корень классифицируется как Истинный; и наоборот, если корневой узел считается "И"оператор тогда один раз Ложь найден, корень классифицируется как Ложь.

Смотрите также

дальнейшее чтение

Ху, Те Чан; Шинг, Ман-так (2002). Комбинаторные алгоритмы. Courier Dover Publications. ISBN 0-486-41962-2. Получено 2007-04-02.
Жемчужина Иудеи, Эвристика, Эддисон-Уэсли, 1984

[1] Нау, Дана (1982). «Исследование причин патологии в играх». Искусственный интеллект. 19: 257–278. Дои:10.1016/0004-3702(82)90002-9.

[Allis1994-2] Виктор Аллис (1994). Поиск решений в играх и искусственном интеллекте (PDF). Кандидат наук. Диссертация, Лимбургский университет, Маастрихт, Нидерланды. ISBN 90-900748-8-0.

[Roche2013-3] Даниэль Рош (2013). SI486D: случайность в вычислениях, блок игровых деревьев. Военно-морская академия США, факультет компьютерных наук.

[1]

[2]

[3]