Рассмотрим связь между стратегиями Теории Игр и LG-стратегиями (в LG-системе из двух взаимодействующих суперагентов). Теория Игр появилась в 1930-х годах, например (Дж. фон Нейман и Моргенштерн, 1944; Оуэн, 1982) и описана в обширной литературе. Хороший обзор сделан в (Льюс и Райфа, 1957). Важный раздел Теории Игр посвящён моделированию экономического поведения. В этом разделе цели игроков сформированы с помощью функции выигрыша и требования максимизировать вознаграждение игрока. Хотя LG использует оценочную функцию, которая является формой вознаграждения, по духу LG всё же ближе к другому разделу Теории Игр, который был основан в работах (Гэйл и Стюарт, 1953) и называется теорией (бесконечных) игр 2-х лиц с полной информацией.

Цели игроков в играх 2-х лиц формулируются посредством множеств желательных вариантов действий, называемых победительными множествами. Выигрышная стратегия для игрока — это такое поведения, которое приводит игрока к победе независимо от того, как ведёт себя противник. Методы построения таких стратегий отличаются от методов Теории Игр, в которых моделируется экономика, тем, что они используют методы логики, алгебры и топологии в отличие от методов математического или функционального анализа и/или вариационного исчисления, применяемых в классической Теории Игр. Методы, подобные вариационному исчислению также используются в другом разделе Теории Игр, который называется Дифференциальными Играми (Айзекс, 1965) — раздел 1.2.

Игры Гэйла-Стьюарта (2-х лиц с полной информацией) были расширены до игр на графах в работах (А.Яхнис и В.Яхнис, 1993; Зейтман, 1994). Самая ранняя ссылка на игры на графах содержится в классических статьях по Теории Игр (Кун, 1953; Берж, 1957). В 1993-94 годах было сделано следующее расширение класса игр на графах, позволившее включить параллельные ходы, а также игры с более чем двумя игроками (В.Яхнис и Б.Штильман, 1995b). Введенный класс игр наиболее близок к абстрактным настольным играм (ABG) или Сложным Системам, которые моделируются LG-системой.

Цели игр на графах и цели в LG не идентичны, так как в рамках LG-подхода класс полезных стратегий шире, чем класс выигрышных стратегий. Интуитивно, специфические LG-стратегии можно рассматривать как стратегии типа "лучшие из возможных", а не как исключительно выигрышные стратегии. Действительно, часто LG-игры не имеют "детерминированной" выигрышной стратегии из-за параллельных ходов. В результате методы LG приводят к новым способам построения выигрышных стратегий. LG генерирует выигрышные стратегии на основе математических конструкций, которые были впервые введены в LG и приспособлены для формализации стратегий экспертов.

Для проведения параллелей нам будет удобно рассматривать LG-систему как игру  2-х лиц, где стороны (или суперагенты) — это игроки. Мы свяжем понятие LG-стратегии для стороны или суперагента со стратегией игрока в игре 2-х лиц. Как обычно, большинство построений для игр 2-х игроков в Теории Игр основано на понятии дерева игры (ДИ). Это дерево состоит из всех возможных ходов игроков и охватывает все возможные варианты розыгрышей в игре. LG связывает с каждым узлом ДИ состояние игры. Состояние игры — это позиция на доске для игр типа шахмат, шашек, крестиков-ноликов и т.д. Для LG-систем (как определено в разделе 2.2) состояние игры — это состояние LG-системы.

Как и в Теории Игр Гэйла-Стюарта, LG занимается поиском стратегии для обеих сторон (игроков), но вводит соответствующие определения на основе состояний LG-системы (или игры), а не на основе ДИ. В фокусе LG, тем не менее, оказываются эффективно вычисляемые стратегии. Это соответствует конструктивному подходу к обнаружению выигрышных стратегий в Теории Игр 2-х игроков Гэйла-Стюарта, впервые введенному Бухи и Ландвебером (1969) и продолженному Гуревичем и Харрингтоном (1982), А.Яхнисом и В.Яхнисом (1990, 1993), Мак-Нотоном (1993) и Зейтманом (1994). Близость целей последнего подхода к LG иногда проявляется в полном совпадении: речь идёт о тех случаях, когда в LG вычисляется доказуемо победная (ничейная) стратегия для игрока (глава 13). В других случаях, LG вычисляет стратегию, которая является хорошей, но может быть сложно или практически невозможно проверить, действительно ли эта стратегия является выигрышной для данного игрока. Алгоритмы Теории Игр, строящие выигрышные стратегии обычно практически неприменимы из-за экспоненциального (или ещё худшего) времени исполнения, в то время как LG-алгоритмы являются практическими и даже полиномиальными по времени (для подклассов задач).

Немного перефразируя, данное в Теории Игр, определение стратегии для игрока на ДИ, мы получим определение LG-стратегии, основанной на состояниях игры. Стратегия — это частичная функция на состояниях игры, которая генерирует ходы для этого игрока. Выигрышная стратегия игрока — это такая стратегия, которая удовлетворяет двум свойствам. Во-первых, стратегия определена в каждом состоянии, в которое игрок должен попасть, следуя ей, а также в состояниях, которые уже были сгенерированы с использованием этой стратегии, включая начальное состояние. Во-вторых, любые конечные последовательности ходов обеих сторон, сгенерированные выигрышной стратегией, приведут систему из начального состояния в целевые состояния для данного игрока, в то время как противоположная сторона может делать любые ходы, разрешённые правилами игры. Дальнейшие подробности об LG-стратегиях приведены в главе 13.

Мы определили стратегию, используя ДИ, включающее все возможные ходы обеих сторон. Однако LG-алгоритм не генерирует это ДИ. Процедура LG-перебора формирует очень маленькое поддерево полного ДИ путём генерации маленького подмножества всех состояний системы. В разделе 1.4 и далее в этой книге, это поддерево названо LG-деревом (или сокращённым деревом перебора) в противоположность полному ДИ при поиске решения методом «брут форс». Доказано, что для некоторых классов задач LG-дерево включает ветви, которые содержат последовательности ходов, сгенерированные выигрышной (или ничейной) стратегией (глава 13). Для других классов задач это сокращённое дерево включает ветви, соответствующие последовательностям ходов, которые сгенерированны с использованием лучшей стратегии, известной экспертам (в то время как никакая (абсолютно) выигрышная стратегия вообще неизвестна). Также, далее в этой книге, мы пишем "деревья ходов", "ветви (или последовательности) ходов" и "варианты" (виртуальные розыгрыши), опуская формулировки о взаимно однозначном соответствии между рёбрами деревьев и ходами игроков.

LG-алгоритм вычисляет стратегию игрока, выбирая ветви, полученные при применении МиниМаксного алгоритма на LG-дереве для обоих игроков. Практически генерация LG-дерева и МиниМакс объединены в одной процедуре. В некоторых случаях LG-дерево является настолько маленьким, что во всех вариантах (игры) выигрывает один и тот же игрок. Другими словами, это LG-дерево представляет выигрышную стратегию (глава 13) для данного игрока. Возможно (хотя это и не гарантировано), что найденная LG-стратегия будет выигрышной также и для полного ДИ.

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

Важно различать два случая использования LG-алгоритма, касающиеся развития LG-системы. Один случай, когда LG-стратегия одного игрока применена против LG-стратегии другого игрока. Другой случай, когда противник делает ходы не по LG-стратегии. Во всех случаях LG-стратегия представлена тем же самым LG-алгоритмом, в котором игрок, ход которого ищется, является входным параметром алгоритма.

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

LG-стратегия должна заново построить LG-дерево в каждом состоянии, для которого вычисляется ход игрока. Если LG-стратегия вычисляет ход для игрока в состоянии S1, а следующий ход противника ведёт в состояние S2, то оба состояния будут содержать много общих структурных компонентов, потому что они отделены только двумя ходами: ход игрока и ответный ход противника, если мы рассматриваем последовательные игры. Для параллельных игр эти состояния разделены одним (параллельным) ходом. Таким образом, LG-алгоритм пытается построить LG-дерево для состояния S2, преобразовывая его из LG-дерева для состояния S1.

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

В действительности, LG-алгоритм генерирует перечисление подмножеств этого графа, тем самым, фиксируя порядок ходов во всех вариантах. Это перечисление порождает поддерево ДИ, которое простирается настолько, насколько продолжаются варианты, вычисленные LG-алгоритмом. Поддерево соответствует розыгрышам игры, начинающимся в состоянии S. Обычно, LG-дерево — это "очень узкое и глубокое" конечное поддерево полного ДИ, которое соответствует розыгрышам игры, начиная из состояния S. Существует взаимно однозначное соответствие между поддеревом ходов, охватывающим все LG-варианты, с одной стороны, и перечислением подмножеств графа переходов LG-системы, соответствующих ходам во всех LG-вариантах, с другой стороны.

Программная система, реализующая LG, поддерживает уже разыгранный вариант игры и его возможные продолжения — поддерево игры, которое представляет все найденные LG-варианты для последнего состояния игры (текущей позиции). LG-алгоритм также поддерживает обширные структуры данных (разд.1.5), связанные с состояниями и предназначенные для сокращения множества вычисляемых вариантов.