Сложность игры - 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 разрешима | |
Магия: Сбор | Бесконечный | Неограниченный | Неограниченный | бесконечный | бесконечный | А-хард |
Примечания
использованная литература
Смотрите также
- Иди и математика
- Решенная игра
- Решение шахмат
- Число Шеннона
- список NP-полных игр и головоломок
- список игр и головоломок для PSPACE