Введение

Понятие в комбинаторной теории игр

Комбинаторная теория игр измеряет сложность игры несколькими способами:

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

Сложность пространства состояний

Сложность пространства состояний игры — это количество допустимых игровых позиций, достижимых из начальной позиции игры. И если вращения и отражения позиций считаются одинаковыми, то существует лишь 765 принципиально различных позиций. Для ограничения дерева игры существует 9 возможных начальных ходов, 8 возможных ответов и так далее, что дает максимум 9! или 362 880 возможных партий. Однако для завершения партий может потребоваться менее 9 ходов, а точный перебор дает 255 168 возможных партий. Если вращения и отражения позиций считаются эквивалентными, то существует только 26 830 возможных партий. Вычислительная сложность крестиков-ноликов зависит от способа её обобщения. Естественным обобщением являются игры m, n, k: игра на поле m x n, где победителем является первый игрок, собравший k символов в ряд. Очевидно, что эту игру можно решить в DSPACE(mn) путем поиска по всему дереву игры. Это относит её к важному классу сложности PSPACE. При дополнительных усилиях можно доказать, что она является PSPACE-полной.