В контексте комбинаторной теории игр , которая обычно изучает последовательные игры с полной информацией , игровое дерево — это граф, представляющий все возможные игровые состояния в такой игре. К таким играм относятся такие известные игры, как шахматы , шашки , го и крестики-нолики . Это можно использовать для измерения сложности игры , поскольку оно представляет все возможные способы, которыми игра может быть успешной. Из-за больших игровых деревьев сложных игр, таких как шахматы, алгоритмы, предназначенные для игры в этот класс игр, будут использовать частичные игровые деревья, что делает вычисления осуществимыми на современных компьютерах. Существуют различные методы решения игровых деревьев. Если можно сгенерировать полное игровое дерево, можно использовать детерминированный алгоритм , такой как обратная индукция или ретроградный анализ . Рандомизированные алгоритмы и алгоритмы minmax, такие как MCTS, могут использоваться в случаях, когда полное игровое дерево невозможно.
Чтобы лучше понять игровое дерево, его можно рассматривать как метод анализа состязательных игр, которые определяют действия, которые игрок предпринимает для победы в игре. В теории игр игровое дерево — это направленный граф, узлы которого являются позициями в игре (например, расположение фигур в настольной игре), а ребра — ходами (например, перемещение фигур из одной позиции на доске в другую). [1]
Полное игровое дерево для игры — это игровое дерево, начинающееся с начальной позиции и содержащее все возможные ходы из каждой позиции; полное дерево — это то же самое дерево, которое получено из развернутого представления игры. Если говорить точнее, полная игра — это норма для игры в теории игр. Которая может четко выражать многие важные аспекты. Например, последовательность действий, которые могут предпринять заинтересованные стороны, их выбор в каждой точке принятия решения, информация о действиях, предпринимаемых другими заинтересованными сторонами, когда каждая заинтересованная сторона принимает решение, и выгоды от всех возможных результатов игры. [2]
На схеме показаны первые два уровня, или plies , в дереве игры в крестики-нолики . Повороты и отражения позиций эквивалентны, поэтому у первого игрока есть три варианта хода: в центре, на краю или в углу. У второго игрока есть два варианта ответа, если первый игрок играл в центре, в противном случае — пять вариантов. И так далее.
Число конечных узлов в полном дереве игры — это число возможных различных способов игры. Например, игровое дерево для крестиков-ноликов имеет 255 168 конечных узлов.
Деревья игры важны в искусственном интеллекте, потому что один из способов выбрать лучший ход в игре — это поиск по дереву игры с использованием любого из многочисленных алгоритмов поиска по дереву в сочетании с правилами типа минимакса для обрезки дерева . Дерево игры для крестиков-ноликов легко поддается поиску, но полные деревья игры для более крупных игр, таких как шахматы , слишком велики для поиска. Вместо этого шахматная программа ищет по частичному дереву игры : обычно столько ходов от текущей позиции, сколько она может найти за отведенное время. За исключением случая «патологических» деревьев игры [3] (которые, по-видимому, встречаются довольно редко на практике), увеличение глубины поиска (т. е. количества просмотренных ходов) обычно повышает шанс выбора лучшего хода.
Игры двух игроков также можно представить в виде деревьев и-или . Для того, чтобы первый игрок выиграл игру, должен существовать выигрышный ход для всех ходов второго игрока. Это представлено в дереве и-или с помощью дизъюнкции для представления альтернативных ходов первого игрока и с помощью конъюнкции для представления всех ходов второго игрока.
Имея полное игровое дерево, можно «решить» игру, то есть найти последовательность ходов, которую может выполнить либо первый, либо второй игрок, что гарантирует наилучший возможный результат для этого игрока (обычно победу или ничью). Детерминированный алгоритм (который обычно называют обратной индукцией или ретроградным анализом ) можно рекурсивно описать следующим образом.
На диаграмме показано игровое дерево для произвольной игры, раскрашенное с использованием вышеописанного алгоритма.
Обычно игру можно решить (в техническом смысле слова «решить»), используя только подмножество игрового дерева, поскольку во многих играх ход не нужно анализировать, если есть другой ход, который лучше для того же игрока (например, альфа-бета-отсечение может использоваться во многих детерминированных играх).
Любое поддерево, которое может быть использовано для решения игры, называется деревом решений , а размеры деревьев решений различных форм используются в качестве мер сложности игры . [4]
Рандомизированные алгоритмы могут использоваться при решении игровых деревьев. В этом типе реализации есть два основных преимущества: скорость и практичность. В то время как детерминированная версия решения игровых деревьев может быть выполнена за Ο ( n ) , следующий рандомизированный алгоритм имеет ожидаемое время выполнения θ ( n 0,792 ), если каждый узел в игровом дереве имеет степень 2. Более того, это практично, потому что рандомизированные алгоритмы способны «сбить противника с толку», то есть противник не может победить систему игровых деревьев, зная алгоритм, используемый для решения игрового дерева, потому что порядок решения случаен.
Ниже представлена реализация алгоритма решения рандомизированного дерева игры: [5]
def gt_eval_rand ( u ) -> bool : """Возвращает True, если этот узел оценивается как выигрыш, в противном случае False""" if u . leaf : return u . win else : random_children = ( gt_eval_rand ( child ) for child in random_order ( u . children )) if u . op == "OR" : return any ( random_children ) if u . op == "AND" : return all ( random_children ) Алгоритм использует идею « короткого замыкания »: если корневой узел считается оператором « ИЛИ », то как только будет найдено одно значение True , корень классифицируется как True ; и наоборот, если корневой узел считается оператором « И », то как только будет найдено одно значение False , корень классифицируется как False .
[6]