Комбинаторная теория игр имеет несколько способов измерения игра сложность. В этой статье описаны пять из них: сложность в пространстве состояний, размер игрового дерева, сложность решения, сложность игрового дерева и вычислительная сложность.
Сложность игры в пространстве состояний - это количество разрешенных игровых позиций достижима из начальной позиции игры.
Когда это слишком сложно вычислить, верхняя граница часто может быть вычислена также путем подсчета (некоторых) незаконных позиций, то есть позиций, которые никогда не могут возникают в процессе игры.
Размер игрового дерева - это общее количество возможных игр, в которые можно играть: количество конечных узлов в дереве игр базируется на исходной позиции игры.
Дерево игры обычно намного больше, чем пространство состояний, потому что одни и те же позиции могут встречаться во многих играх, делая ходы в другом порядке (например, в крестики-нолики игра с двумя X и одним O на доске, эта позиция могла быть достигнута двумя разными способами в зависимости от того, где был помещен первый X). Верхнюю границу размера игрового дерева иногда можно вычислить, упростив игру таким образом, чтобы размер игрового дерева только увеличивался (например, разрешая незаконные ходы), пока он не станет управляемым.
Для игр, в которых количество ходов не ограничено (например, размером доски или правилом о повторении позиции), дерево игры обычно бесконечно.
Следующие две меры используют идею дерева решений, которое является поддеревом игрового дерева, где каждая позиция помечена как «игрок А выигрывает. "," игрок Б выигрывает "или" ничья ", если можно доказать, что эта позиция имеет такое значение (при условии лучшей игры обеих сторон) путем изучения только других позиций на графике. (Конечные позиции могут быть обозначены напрямую; позиция, в которой должен двигаться игрок A, может быть обозначена как «игрок A выигрывает», если любая последующая позиция является победой для A, или как «игрок B выигрывает», если все последующие позиции являются выигрышными для B, или помечены как "ничья", если все последующие позиции либо ничья, либо выигрыш для B. И, соответственно, для позиций с B для перемещения.)
Сложность решения игры - это количество листьев узлы в наименьшем дереве решений, которое устанавливает значение начальной позиции.
Сложность игрового дерева игры - это количество конечных узлов в самом маленьком дереве решений полной ширины, которое устанавливает значение исходное положение. Полноразмерное дерево включает все узлы на каждой глубине.
Это оценка количества позиций, которые нужно было бы оценить в поиске минимакс, чтобы определить значение начальной позиции.
Трудно даже оценить сложность дерева игр, но для некоторых игр можно дать приближение, возведя средний коэффициент ветвления b игры в степень числа играет d в средней игре, или:
.
вычислительная Сложность игры описывает асимптотическую сложность игры, когда она становится произвольно большой, выраженная в нотации большого O или как принадлежность к классу сложности. Эта концепция не применяется к конкретным играм, а скорее к играм, которые были обобщены, поэтому их можно сделать произвольно большими, обычно играя в них на доске n × n. (С точки зрения вычислительной сложности игра на доске фиксированного размера - это конечная задача, которую можно решить за O (1), например, с помощью таблицы поиска от позиций до лучшего хода в каждой позиции.)
Асимптотическая сложность определяется наиболее эффективным (с точки зрения вычислительных ресурсов рассматриваемых) алгоритмом решения игры; наиболее распространенная мера сложности (время вычисления ) всегда ограничена снизу логарифмом асимптотической сложности в пространстве состояний, так как алгоритм решения должен работать для всех возможных состояний игры. Он будет ограничен сверху сложностью любого конкретного алгоритма, который работает для семейства игр. Аналогичные замечания относятся ко второму наиболее часто используемому показателю сложности - объему пространства или компьютерной памяти, используемого для вычислений. Неочевидно, что существует какая-либо нижняя граница сложности пространства для типичной игры, потому что алгоритм не должен хранить состояния игры; однако известно, что многие интересные игры сложны для PSPACE, и из этого следует, что их пространственная сложность будет также ограничена снизу логарифмом асимптотической сложности в пространстве состояний (технически оценка - это только многочлен от этой величины, но обычно известен как линейный).
Для крестики-нолики простая верхняя граница размера пространства состояний составляет 3 = 19 683. (Есть три состояния для каждой ячейки и девять ячеек.) Этот счет включает множество недопустимых позиций, таких как позиция с пятью крестиками и без нулей или позиция, в которой у обоих игроков есть ряд из трех. Более тщательный подсчет и удаление этих незаконных позиций дает 5 478. А если считать повороты и отражения позиций идентичными, то имеется всего 765 существенно разных позиций.
Чтобы связать дерево игры, есть 9 возможных начальных ходов, 8 возможных ответов и так далее, так что их не более 9! или 362 880 игр всего. Однако для разрешения игры может потребоваться менее 9 ходов, и точное перечисление дает 255 168 возможных игр. Если считать, что повороты и отражения позиций одинаковы, существует только 26 830 возможных игр.
Вычислительная сложность крестиков-ноликов зависит от того, как они обобщены. Естественное обобщение - это m, n, k-игры : игра на доске размером m на n, где победитель становится первым игроком, получившим k подряд. Сразу ясно, что эту игру можно решить в DSPACE (mn) путем поиска по всему дереву игр. Это помещает его в важный класс сложности PSPACE. После некоторой дополнительной работы можно показать, что это PSPACE-complete.
.
Из-за большого размера сложности игр эта таблица дает потолок их логарифм с основанием 10. (Другими словами, количество цифр). Все следующие числа следует рассматривать с осторожностью: кажущиеся незначительными изменения правил игры могут изменить числа (которые в любом случае часто являются приблизительными оценками) в огромных количествах, которые легко могут быть намного больше, чем указанные числа.
Примечание: упорядочено по размеру дерева игр
Игра | Размер доски (позиции) | Сложность в пространстве состояний (как журнал по основанию 10) | Сложность игрового дерева (как log по основанию 10) | Средняя длина игры (слоев ) | Коэффициент ветвления | Ref | Класс сложности подходящей обобщенной игры |
---|---|---|---|---|---|---|---|
Tic-tac-toe | 9 | 3 | 5 | 9 | 4 | PSPACE-complete | |
Sim | 15 | 3 | 8 | 14 | 3.7 | PSPACE-complete | |
Пентамино | 64 | 12 | 18 | 10 | 75 | ?, Но в PSPACE | |
Kalah | 14 | 13 | 18 | Обобщение неясно | |||
Connect Four | 42 | 13 | 21 | 36 | 4 | ?, Но в PSPACE | |
Domineering (8 × 8) | 64 | 15 | 27 | 30 | 8 | ?, Но в PSPACE ; в P для определенных размеров | |
Congkak | 14 | 15 | 33 | ||||
Английские шашки (8x8) (шашки) | 32 | 20 или 18 | 31 | 70 | 2,8 | EXPTIME-complete | |
Awari | 12 | 12 | 32 | 60 | 3.5 | Обобщение неясно | |
Qubic | 64 | 30 | 34 | 20 | 54,2 | PSPACE-complete | |
Двойной фиктивный мост | (52) | <17 | <40 | 52 | 5.6 | PSPACE-complete | |
Fanorona | 45 | 21 | 46 | 44 | 11 | ?, Но в EXPTIME | |
Девять мужчин morris | 24 | 10 | 50 | 50 | 10 | ?, Но в EXPTIME | |
Таблут | 81 | 27 | |||||
Международные шашки (10x10) | 50 | 30 | 54 | 90 | 4 | EXPTIME-complete | |
Китайские шашки (2 набора) | 121 | 23 | EXPTIME -завершено | ||||
Китайские шашки (6 комплектов) | 121 | 78 | EXPTIME -завершено | ||||
Реверси (Отелло) | 64 | 28 | 58 | 58 | 10 | PSPACE-complete | |
OnTop (базовая игра 2p) | 72 | 88 | 62 | 31 | 23,77 | ||
Направления действий | 64 | 23 | 64 | 44 | 29 | ?, Но в EXPTIME | |
Гомоку (15x15, вольный стиль) | 225 | 105 | 70 | 30 | 210 | PSPACE-complete | |
Hex (11x11) | 121 | 57 | 98 | 50 | 96 | PSPACE- завершено | |
Шахматы | 64 | 47 | 123 | 70 | 35 | EXPTIME-complete (без Правило рисования с 50 ходами ) | |
Bejeweled и Candy Crush (8x8) | 64 | <50 | NP-hard | ||||
GIPF | 37 | 25 | 132 | 90 | 29,3 | ||
Connect6 | 361 | 172 | 140 | 30 | 46000 | PSPACE-complete | |
Нарды | 28 | 20 | 144 | 55 | 250 | Обобщение неясно | |
Сянци | 90 | 40 | 150 | 95 | 38 | ?, Полагают быть EXPTIME-complete | |
Abalone | 61 | 25 | 154 | 87 | 60 | PSPACE-hard, а в EXPTIME | |
Havannah | 271 | 127 | 157 | 66 | 240 | PSPACE-complete | |
Twixt | 572 | 140 | 159 | 60 | 452 | ||
Джангги | 90 | 44 | 160 | 100 | 40 | ?, Считается EXPTIME-complete | |
Quoridor | 81 | 42 | 162 | 91 | 60 | ?, Но в PSPACE | |
Каркассон (2p основная игра) | 72 | >40 | 195 | 71 | 55 | Обобщение неясно | |
Амазонки (10x10) | 100 | 40 | 212 | 84 | 374 или 299 | PSPACE-complete | |
Shogi | 81 | 71 | 226 | 115 | 92 | EXPTIME-complete | |
Go (19x19) | 361 | 170 | 360 | 150 | 250 | EXPTIME-complete | |
Arimaa | 64 | 43 | 402 | 92 | 17281 | ?, Но в EXPTIME | |
Stratego | 92 | 115 | 535 | 381 | 21.739 | ||
Бесконечные шахматы | неограниченный | EXPTIME-полный (без правила жеребьевки на 50 ходов) |
| journal =
()| journal =
()| journal =
()| journal =
()