Дерево игры

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

Понимание дерева игры

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

Полное дерево игры — это дерево игры, начинающееся с начальной позиции и содержащее все возможные ходы из каждой позиции; полное дерево — это то же дерево, что и полученное из представления игры в развернутой форме . Точнее, полная игра — это норма игры в теории игр. Который может ясно выразить многие важные аспекты. Например, последовательность действий, которые могут предпринять заинтересованные стороны, их выбор в каждой точке принятия решения, информация о действиях, предпринимаемых другими заинтересованными сторонами, когда каждая заинтересованная сторона принимает решение, а также преимущества всех возможных результатов игры. ^[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

def gt_eval_rand(u) -> bool:
    """Returns True if this node evaluates to a win, otherwise 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)

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

^[6]

См. также

Ссылки

^ Цукерман, Инон; Уилсон, Брэндон; Нау, Дана С. (2018). «Как избежать патологии дерева игры при состязательном поиске для двух игроков» . Вычислительный интеллект . 34 (2): 542–561. дои : 10.1111/монета.12162 . ISSN 1467-8640 . S2CID 46926187 .
^ Хуан, Цзишуо; Ю, Ханг; Чу, Сянъян; Пэн, Чжэньвэй (01 мая 2018 г.). «Новая модель оптимизации, основанная на дереве игры для систем преобразования нескольких энергий» . Энергия . 150 : 109–121. дои : 10.1016/j.energy.2018.02.091 . ISSN 0360-5442 .
^ Нау, Дана (1982). «Исследование причин патологии в играх». Искусственный интеллект . 19 (3): 257–278. дои : 10.1016/0004-3702(82)90002-9 .
^ Виктор Эллис (1994). В поисках решений в играх и искусственном интеллекте (PDF) . доктор философии Диссертация, Лимбургский университет, Маастрихт, Нидерланды. ISBN 90-900748-8-0 .
^ Дэниел Рош (2013). SI486D: Случайность в вычислениях, Блок игровых деревьев . Военно-морская академия США, факультет компьютерных наук. Архивировано из оригинала 08 мая 2021 г. Проверено 29 апреля 2013 г.
^ Пекарж, Либор; Матуш, Радек; Андрела, Иржи; Личманнова, Мартина (сентябрь 2020 г.). «Обзор исследований игр Калаха и предложение нового эвристически-детерминированного алгоритма по сравнению с решениями поиска по дереву и принятием решений человеком» . Информатика . 7 (3): 34. doi : 10.3390/informatics7030034 . hdl : 10084/142398 .

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

Ху, Те Чан; Шинг, Ман-так (2002). Комбинаторные алгоритмы . Публикации Курьера Дувра. ISBN 0-486-41962-2 . Проверено 2 апреля 2007 г.
Джудея Перл , Эвристика , Аддисон-Уэсли, 1984 г.

[1] Цукерман, Инон; Уилсон, Брэндон; Нау, Дана С. (2018). «Как избежать патологии дерева игры при состязательном поиске для двух игроков» . Вычислительный интеллект . 34 (2): 542–561. дои : 10.1111/монета.12162 . ISSN 1467-8640 . S2CID 46926187 .

[2] Хуан, Цзишуо; Ю, Ханг; Чу, Сянъян; Пэн, Чжэньвэй (01 мая 2018 г.). «Новая модель оптимизации, основанная на дереве игры для систем преобразования нескольких энергий» . Энергия . 150 : 109–121. дои : 10.1016/j.energy.2018.02.091 . ISSN 0360-5442 .

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

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

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

[6] Пекарж, Либор; Матуш, Радек; Андрела, Иржи; Личманнова, Мартина (сентябрь 2020 г.). «Обзор исследований игр Калаха и предложение нового эвристически-детерминированного алгоритма по сравнению с решениями поиска по дереву и принятием решений человеком» . Информатика . 7 (3): 34. doi : 10.3390/informatics7030034 . hdl : 10084/142398 .

[1]

[2]

[3]

[4]

[5]

[6]