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