Дерево игры

Дерево игры — развёрнутая форма игры: позиции — вершины дерева, ходы — ветви, в листьях записаны выигрыши $(u_1,\dots ,u_n)$. Корень — начальная позиция; у внутренней вершины помечено, чей ход и какие альтернативы доступны. Вершины, неразличимые для ходящего игрока из-за скрытой информации, объединяют в информационные множества; одиночное множество — полная информация. Шахматы, крестики-нолики и пошаговые переговоры — деревья; базовая структура — тот же граф.

Метод решения — обратная индукция: от листьев к корню каждый игрок выбирает лучшую для себя ветвь, зная, что дальше поступят разумно. Пример: A выбирает L или R; после L B выбирает между $(3,1)$ и $(0,0)$, после R — между $(1,2)$ и $(2,3)$. B берёт $(3,1)$ слева ($1>0$) и $(2,3)$ справа ($3>2$); A сравнивает $3$ и $2$ — играет R, исход $(2,3)$. Теорема Зермело: конечные игры с полной информацией решаются в чистых стратегиях. Матричная и развёрнутая формы рядом — в уроке введение в теорию игр.