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

О дереве игр в том виде, в котором оно используется в теории игр (а не в комбинаторной теории игр ), см. Игра в расширенной форме .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

Рекомендации

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