Сложность игры - Game complexity

Комбинаторная теория игр имеет несколько способов измерения сложности игры . В этой статье описаны пять из них: сложность в пространстве состояний, размер игрового дерева, сложность решения, сложность игрового дерева и вычислительная сложность.

Меры сложности игры

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

Пространство состояний сложность в игре есть ряд правовых позиций игры , достижимых из начального положения игры.

Когда это слишком сложно вычислить, верхнюю границу часто можно вычислить также путем подсчета (некоторых) незаконных позиций, то есть позиций, которые никогда не могут возникнуть в ходе игры.

Размер игрового дерева

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

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

Для игр, в которых количество ходов не ограничено (например, размером доски или правилом о повторении позиции), дерево игр обычно бесконечно.

Деревья решений

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

Сложность решения

Сложность принятия решения в игре - это количество конечных узлов в наименьшем дереве решений, которое устанавливает значение начальной позиции.

Сложность игрового дерева

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

Это оценка количества позиций, которые нужно было бы оценить при минимаксном поиске, чтобы определить значение начальной позиции.

Трудно даже оценить сложность игрового дерева, но для некоторых игр можно дать приближение, возведя средний коэффициент ветвления игры b в степень числа слоев d в средней игре, или:

.

Вычислительная сложность

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

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

  • Глубины первой стратегия минимакса будет использовать время вычисления пропорциональных игры дерево сложность, так как он должен исследовать все дерево, и количество полинома памяти в логарифме дерева сложности, так как алгоритм должен всегда сохранять один узел дерево на каждой возможной глубине хода, а количество узлов на самой высокой глубине хода и есть сложность дерева.
  • Обратная индукция будет использовать как память, так и время, пропорциональные сложности пространства состояний, поскольку она должна вычислять и записывать правильное перемещение для каждой возможной позиции.

Пример: крестики-нолики (крестики-нолики)

Для крестиков-ноликов , простой верхняя границы для размера пространства состояний составляет 3 9 = 19683. (Есть три состояния для каждой ячейки и девять ячеек.) Этот счет включает множество недопустимых позиций, таких как позиция с пятью крестиками и без нулей или позиция, в которой у обоих игроков есть ряд из трех. Более тщательный подсчет, удаление этих незаконных позиций, дает 5 478. А если считать повороты и отражения позиций идентичными, то имеется всего 765 существенно разных позиций.

Чтобы связать дерево игры, есть 9 возможных начальных ходов, 8 возможных ответов и так далее, так что их не более 9! или 362 880 игр. Однако для разрешения игры может потребоваться менее 9 ходов, и точное перечисление дает 255 168 возможных игр. Если считать, что вращения и отражения позиций одинаковы, существует только 26 830 возможных игр.

Вычислительная сложность крестиков-ноликов зависит от того, как они обобщаются . Естественное обобщение - это m , n , k -игры : игра ведется на доске m на n, где победитель становится первым игроком, получившим k подряд. Сразу видно, что эту игру можно решить в DSPACE ( mn ) путем поиска по всему дереву игр. Это помещает его в важный класс сложности PSPACE . После некоторой дополнительной работы можно показать, что он завершен для PSPACE .

Сложности некоторых известных игр

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

Примечание: упорядочено по размеру дерева игры

Игра Размер доски

(должности)

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

(как логарифм по основанию 10)

Сложность игрового дерева

(как логарифм по основанию 10)

Средняя продолжительность игры

( слои )

Фактор ветвления Ссылка Класс сложности подходящей обобщенной игры
Крестики-нолики 9 3 5 9 4 PSPACE-полный
Сим 15 3 8 14 3,7 PSPACE-полный
Пентамино 64 12 18 10 75 ?, но в PSPACE
Калах 14 13 18 50 Обобщение неясно
Подключите четыре 42 13 21 год 36 4 ?, но в PSPACE
Власть (8 × 8) 64 15 27 30 8 ?, но в PSPACE ; в P для определенных размеров
Congkak 14 15 33
Английские шашки (8х8) (шашки) 32 20 или 18 40 70 2,8 EXPTIME-завершено
Авари 12 12 32 60 3.5 Обобщение неясно
Кубич 64 30 34 20 54,2 PSPACE-полный
Двойной фиктивный мост (52) <17 <40 52 5,6 PSPACE-полный
Fanorona 45 21 год 46 44 год 11 ?, но в EXPTIME
Девять мужчин моррис 24 10 50 50 10 ?, но в EXPTIME
Таблут 81 год 27
Международные шашки (10х10) 50 30 54 90 4 EXPTIME-завершено
Китайские шашки (2 комплекта) 121 23 180 EXPTIME - завершено
Китайские шашки (6 комплектов) 121 78 600 EXPTIME - завершено
Реверси (Отелло) 64 28 год 58 58 10 PSPACE-полный
OnTop (базовая игра 2p) 72 88 62 31 год 23,77
Направления действий 64 23 64 44 год 29 ?, но в EXPTIME
Гомоку (15х15, вольный стиль) 225 105 70 30 210 PSPACE-полный
Шестигранник (11x11) 121 57 98 50 96 PSPACE-полный
Шахматы 64 44 год 123 70 35 год EXPTIME-complete (без правила жеребьевки на 50 ходов )
Bejeweled и Candy Crush (8x8) 64 <50 70 NP-жесткий
GIPF 37 25 132 90 29,3
Подключить6 361 172 140 30 46000 PSPACE-полный
Нарды 28 год 20 144 55 250 Обобщение неясно
Сянци 90 40 150 95 38 ?, считается завершенным EXPTIME
Морское ушко 61 25 154 87 60 PSPACE-хард , а в EXPTIME
Гаванна 271 127 157 66 240 PSPACE-полный
Twixt 572 140 159 60 452
Джангги 90 44 год 160 100 40 ?, считается завершенным EXPTIME
Quoridor 81 год 42 162 91 60 ?, но в PSPACE
Каркассон (базовая игра 2 очка) 72 > 40 195 71 55 Обобщение неясно
Амазонки (10х10) 100 40 212 84 374 или 299 PSPACE-полный
Сёги 81 год 71 226 115 92 EXPTIME-завершено
Турн и Таксис (2 игрока) 33 66 240 56 879
Перейти (19x19) 361 170 360 150 250 EXPTIME-завершено
Аримаа 64 43 год 402 92 17281 ?, но в EXPTIME
Stratego 92 115 535 381 21,739
Бесконечные шахматы бесконечный бесконечный бесконечный бесконечный бесконечный Неизвестно, но mate-in-n разрешима
Магия: Сбор Бесконечный Неограниченный Неограниченный бесконечный бесконечный А-хард

Примечания

использованная литература

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

внешние ссылки