игровое дерево - это ориентированный граф, узлы которого являются позициями в игре. Он также используется в AI.
Понимание игрового дерева
Чтобы лучше понять дерево игр, его можно рассматривать как метод анализа состязательных игр, который определяет действия, предпринимаемые игроком для победы в игре. В теории игр игровое дерево - это ориентированный граф, узлами которого являются позиции в игре (например, расположение фигур в настольной игре), а ребрами - движения (например, для перемещения фигур из одной позиции на доске в другую. ). [1]
Полное дерево игры для игры является дерево игры , начиная с начальной позиции и содержащий все возможные ходы от каждой позиции; полное дерево - это то же самое дерево, что и полученное из представления игры в развернутой форме . Чтобы быть более конкретным, полная игра является нормой для игры в теории игр. Которая может ясно выразить многие важные аспекты. Например, последовательность действий, которые могут быть предприняты заинтересованными сторонами, их выбор в каждой точке принятия решения, информация о действиях, предпринятых другими заинтересованными сторонами, когда каждая заинтересованная сторона принимает решение, и преимущества всех возможных результатов игры. [2]
На диаграмме показаны первые два уровня, или слои , в дереве игры в крестики-нолики . Вращения и отражения позиций эквивалентны, поэтому у первого игрока есть три варианта хода: в центре, на краю или в углу. У второго игрока есть два варианта ответа, если первый игрок играл в центре, в противном случае пять вариантов ответа. И так далее.
Количество конечных узлов в полном дереве игры - это количество возможных различных способов ведения игры. Например, дерево игры в крестики-нолики имеет 255 168 листовых узлов.
Деревья игр важны в искусственном интеллекте, потому что один из способов выбрать лучший ход в игре - это поиск в дереве игр с использованием любого из многочисленных алгоритмов поиска по дереву в сочетании с правилами, подобными минимаксу, для сокращения дерева . Дерево игр для крестиков-ноликов легко найти, но полное дерево игр для больших игр, таких как шахматы , слишком велико для поиска. Вместо этого программа, играющая в шахматы, выполняет поиск в частичном дереве игры : обычно столько слоев от текущей позиции, сколько она может выполнить за доступное время. За исключением случая «патологических» игровых деревьев [3] (которые на практике кажутся довольно редкими), увеличение глубины поиска (то есть количества просматриваемых слоев) обычно увеличивает шанс выбора лучшего хода.
Игры для двух человек также можно представить в виде и / или деревьев . Чтобы первый игрок выиграл игру, должен существовать выигрышный ход для всех ходов второго игрока. Это представлено в дереве и / или с помощью дизъюнкции для представления альтернативных ходов первого игрока и использования конъюнкции для представления всех ходов второго игрока.
Решение игровых деревьев
Версия детерминированного алгоритма
Имея полное дерево игры, можно «решить» игру, то есть найти последовательность ходов, которой может следовать первый или второй игрок, которая гарантирует наилучший возможный результат для этого игрока (обычно выигрыш или галстук). Алгоритм (который обычно называют обратной индукцией или ретроградным анализом ) можно рекурсивно описать следующим образом.
- Раскрасьте последний слой игрового дерева так, чтобы все выигрыши игрока 1 были окрашены в один цвет (синий на диаграмме), все выигрыши игрока 2 были окрашены в другой цвет (красный на диаграмме), а все ничьи были окрашены в третий цвет. (Серый на схеме).
- Посмотрите на следующий слой. Если существует узел, противоположный цвету текущего игрока, раскрасьте этот узел и для этого игрока. Если все непосредственно нижние узлы окрашены для одного и того же игрока, раскрасьте и этот узел для того же игрока. В противном случае раскрасьте этот узел галстуком.
- Повторите эти действия для каждого слоя, двигаясь вверх, пока все узлы не будут окрашены. Цвет корневого узла будет определять характер игры.
На диаграмме показано игровое дерево для произвольной игры, раскрашенное с использованием описанного выше алгоритма.
Обычно можно решить игру (в этом техническом смысле «решить»), используя только подмножество игрового дерева, поскольку во многих играх нет необходимости анализировать ход, если есть другой ход, который лучше для того же игрока ( например, отсечение альфа-бета может использоваться во многих детерминированных играх).
Любое поддерево, которое можно использовать для решения игры, называется деревом решений , а размеры деревьев решений различных форм используются в качестве меры сложности игры . [4]
Версия рандомизированных алгоритмов
При решении деревьев игр можно использовать рандомизированные алгоритмы. У такого типа реализации есть два основных преимущества: скорость и практичность. В то время как детерминированная версия решения деревьев игр может быть выполнена в Ο ( n ) , следующий рандомизированный алгоритм имеет ожидаемое время выполнения θ ( n 0,792 ), если каждый узел в дереве игры имеет степень 2. Более того, это практично, потому что рандомизировано алгоритмы способны «помешать врагу», то есть оппонент не может победить систему игровых деревьев, зная алгоритм, используемый для решения игрового дерева, потому что порядок решения является случайным.
Ниже представлена реализация алгоритма решения рандомизированного дерева игр: [5]
def gt_eval_rand ( u ) -> bool : "" "Возвращает True, если этот узел оценивается как выигрыш, иначе False" "", если u . лист : вернуть u . win else : random_children = ( gt_eval_rand ( child ) для ребенка в random_order ( u . children )), если u . op == "OR" : вернуть любое ( random_children ), если u . op == "И" : вернуть все ( random_children )
Алгоритм использует идею « короткого замыкания »: если корневой узел считается оператором « ИЛИ », то один раз Верно найдено, корень классифицируется как Верно ; и наоборот, если корневой узел считается " И "оператор, затем один раз один Обнаружено ложное значение , корень классифицируется как Ложь .
Мини – макс поиск в дереве игр
В этом алгоритме сначала проверяется, что константа MaxDepth. Что представляет собой максимальный уровень поиска по дереву. Текущее состояние доски может быть представлено корневым узлом дерева. Все доступные ходы считаются исходящими из этого узла. Игрок ищет максимальное значение функции стоимости «оценка», а противник вычисляет ее минимум. [6]
Смотрите также
Рекомендации
- ^ Цукерман, Инон; Уилсон, Брэндон; Нау, Дана С. (2018). «Избежание патологии дерева игр в состязательном поиске для двух игроков» . Вычислительный интеллект . 34 (2): 542–561. DOI : 10.1111 / coin.12162 . ISSN 1467-8640 . S2CID 46926187 .
- ^ Хуанг, Цзышо; Ю, Ханг; Чу, Сянъян; Пэн, Чжэньвэй (2018-05-01). «Новая модель оптимизации, основанная на дереве игр для систем преобразования нескольких источников энергии» . Энергия . 150 : 109–121. DOI : 10.1016 / j.energy.2018.02.091 . ISSN 0360-5442 .
- ^ Нау, Дана (1982). «Исследование причин патологии в играх». Искусственный интеллект . 19 (3): 257–278. DOI : 10.1016 / 0004-3702 (82) 90002-9 .
- ^ Виктор Аллис (1994). Поиск решений в играх и искусственном интеллекте (PDF) . Кандидат наук. Диссертация, Лимбургский университет, Маастрихт, Нидерланды. ISBN 90-900748-8-0.
- ^ Даниэль Рош (2013). SI486D: Случайность в вычислениях, Блок игровых деревьев . Военно-морская академия США, факультет компьютерных наук.
- ^ Пекарж, Либор; Матушу, Радек; Андрла, Иржи; Личманнова, Мартина (сентябрь 2020 г.). «Обзор исследований игр Kalah и предложение нового эвристико-детерминированного алгоритма по сравнению с решениями поиска по дереву и принятием решений человеком» . Информатика . 7 (3): 34. DOI : 10.3390 / informatics7030034 .
дальнейшее чтение
- Ху, Те Чан; Шинг, Ман-так (2002). Комбинаторные алгоритмы . Courier Dover Publications. ISBN 0-486-41962-2. Проверено 2 апреля 2007 .
- Judea Pearl , Heuristics , Addison-Wesley, 1984.