Сложность игры
Понятие в комбинаторной теории игр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложность игрового дерева игры — это количество конечных узлов в наименьшем дереве решений полной ширины , которое устанавливает значение начальной позиции. [1] Дерево полной ширины включает все узлы на каждой глубине.

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

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

Г Т С ≥ б г {\displaystyle GTC\geq b^{d}} .

Сложность вычислений

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

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

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

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

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

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

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

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

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

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

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

(позиции)

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

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

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

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

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

( слои )

Фактор разветвленияСсылкаКласс сложности подходящей обобщенной игры
Крестики-нолики93594PSPACE-полный [5]
Сим1538143.7PSPACE-полный [6]
Пентамино6412181075[7] [8]?, но в PSPACE
Калах [9]14131850[7]Обобщение неясно.
Соедини Четыре421321364[1] [10]?, но в PSPACE
Властный (8 × 8)641527308[7]?, но в PSPACE ; в P для определенных измерений [11]
Конгкак141533[7]
Английские шашки (8x8) (чекерс)3220 или 1840702.8[1] [12] [13]EXPTIME-завершено [14]
Авари [15]121232603.5[1]Обобщение неясно.
Кубик6430342054.2[1]PSPACE-полный [5]
Двойной фиктивный мост [nb 1](52)<17<40525.6PSPACE-полный [16]
Фанорона4521464411[17]?, но в EXPTIME
Девять мужских моррисов2410505010[1]?, но в EXPTIME
Таблут8127[18]
Международные шашки (10x10)503054904[1]EXPTIME-завершено [14]
Китайские шашки (2 комплекта)12123180[19]EXPTIME -полный [20]
Китайские шашки (6 комплектов)12178600[19]EXPTIME -полный [20]
Реверси (Отелло)6428585810[1]PSPACE-полный [21]
OnTop (базовая игра 2 человека)7288623123.77[22]
Линии действия6423644429[23]?, но в EXPTIME
Гомоку (15x15, свободный стиль)2251057030210[1]PSPACE-полный [5]
Шестигранник (11x11)12157985096[7]PSPACE-полный [5]
Шахматы64441237035[24]EXPTIME-complete (без правила розыгрыша в 50 ходов ) [25]
Драгоценности и конфеты Crush (8x8)64<5070[26]NP-трудный
ГИПФ37251329029.3[27]
Подключить63611721403046000[28]PSPACE-полный [29]
Нарды282014455250[30]Обобщение неясно.
Сянци90401509538[1] [31] [32]?, считается EXPTIME-завершенным
Абалон61251548760[33] [34]PSPACE-hard и в EXPTIME
Гаванна27112715766240[7] [35]PSPACE-полный [36]
Твикст57214015960452[37]
Чанги904416010040[32]?, считается EXPTIME-завершенным
Коридор81421629160[38]?, но в PSPACE
Каркассон (базовая игра для 2 игроков)72>401957155[39]Обобщение неясно.
Амазонки (10x10)1004021284374 или 299 [40][41] [42]PSPACE-полный [43]
Сёги817122611592[31] [44]EXPTIME-завершено [45]
Турн и Таксис (2 игрока)336624056879[46]
Перейти (19x19)361170360150250[1] [47] [48]EXPTIME-complete (без правила суперко ) [49]
Аримаа64434029217281[50] [51] [52]?, но в EXPTIME
Стратего9211553538121.739[53]
Бесконечные шахматыбесконечныйбесконечныйбесконечныйбесконечныйбесконечный[54]Неизвестно, но мат-в-n разрешим [55]
Магия: Сбор[56]AH-жесткий [57]
Вордл512,9726[58]NP-трудная , неизвестно, является ли она PSPACE-полной с параметризацией.

Примечания

  1. ^ Двойной фиктивный мост (т. е. проблемы с двойными фиктивными фигурами в контексте контрактного бриджа ) не является полноценной настольной игрой, но имеет похожее игровое дерево и изучается в компьютерном бридже . Таблицу бриджа можно рассматривать как имеющую по одному слоту для каждого игрока и трюка, чтобы разыграть карту, что соответствует размеру доски 52. Сложность игрового дерева — очень слабая верхняя граница: 13! в степени 4 игроков независимо от законности. Сложность пространства состояний — для одной заданной сделки; аналогично независимо от законности, но со многими исключенными перестановками. Последние 4 хода всегда являются вынужденными ходами с фактором ветвления 1.

Ссылки

  1. ^ abcdefghijkl Виктор Эллис (1994). Поиск решений в играх и искусственном интеллекте (PDF) (диссертация). Университет Лимбурга, Маастрихт, Нидерланды. ISBN 90-900748-8-0.
  2. ^ "комбинаторика - TicTacToe State Space Choose Calculation". Mathematics Stack Exchange . Получено 2020-04-08 .
  3. ^ T, Брайан (20 октября 2018 г.). "Btsan/generate_tictactoe". GitHub . Получено 08.04.2020 .
  4. ^ Стефан Райш (1980). «Gobang ist PSPACE-vollständig (Gobang является PSPACE-полным)». Акта Информатика . 13 (1): 59–66. дои : 10.1007/bf00288536. S2CID  21455572.
  5. ^ abcd Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex является PSPACE-полным)». Акта Информ (15): 167–191.
  6. ^ Slany, Wolfgang (2000). «Сложность графовых игр Рамсея». В Marsland, T. Anthony; Frank, Ian (ред.). Computers and Games, Вторая международная конференция, CG 2000, Хамамацу, Япония, 26-28 октября 2000 г., пересмотренные статьи . Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 186–203. doi :10.1007/3-540-45579-5_12.
  7. ^ abcdef HJ ван ден Херик; JWHM Уитервейк; Дж. ван Рейсвейк (2002). «Игры решены: сейчас и в будущем». Искусственный интеллект . 134 (1–2): 277–311. дои : 10.1016/S0004-3702(01)00152-7 .
  8. ^ Орман, Хилари К. (1996). «Пентомино: победа первого игрока» (PDF) . В Nowakowski, Ричард Дж. (ред.). Игры без шансов: доклады семинара по комбинаторным играм, состоявшегося в Беркли, Калифорния, 11–21 июля 1994 г. . Издательство научно-исследовательского института математических наук. Том 29. Cambridge University Press. С. 339–344. ISBN 0-521-57411-0. МР  1427975.
  9. ^ Правила см. у ван ден Херика и др.
  10. ^ Джон Тромп (2010). «Игровая площадка Джона Соедини Четыре».
  11. ^ Лахманн, Майкл; Мур, Кристофер; Рапапорт, Иван (2002). «Кто выигрывает в доминировании на прямоугольных досках?». В Nowakowski, Ричард (ред.). Еще больше игр без шансов: Труды 2-го семинара по теории комбинаторных игр, состоявшегося в Беркли, Калифорния, 24–28 июля 2000 г. Публикации Научно-исследовательского института математических наук. Том 42. Cambridge University Press. С. 307–315. ISBN 0-521-80832-4. МР  1973019.
  12. ^ Джонатан Шеффер и др. (6 июля 2007 г.). «Checkers is Solved». Science . 317 (5844): 1518–1522. Bibcode :2007Sci...317.1518S. doi : 10.1126/science.1144079 . PMID  17641166. S2CID  10274228.
  13. ^ Шеффер, Джонатан (2007). «Игра окончена: черные играют и делают ничью в шашках» (PDF) . Журнал ICGA . 30 (4): 187–197. doi :10.3233/ICG-2007-30402. Архивировано из оригинала (PDF) 2016-04-03.
  14. ^ ab JM Robson (1984). "N на N чекеров — это Exptime complete". SIAM Journal on Computing . 13 (2): 252–267. doi :10.1137/0213018.
  15. ^ См. правила у Эллиса 1994 г.
  16. ^ Бонне, Эдуард; Жамейн, Флориан; Саффидин, Абдалла (2013). «О сложности карточных игр с взятками». В Росси, Франческа (ред.). IJCAI 2013, Труды 23-й Международной совместной конференции по искусственному интеллекту, Пекин, Китай, 3–9 августа 2013 г. IJCAI/AAAI. стр. 482–488.
  17. ^ MPD Шадд; МХМ Винандс; JWHM Уитервейк; Х.Дж. ван ден Херик; MHJ Бергсма (2008). «Лучшая игра в Фанороне приводит к ничьей» (PDF) . Новая математика и естественные вычисления . 4 (3): 369–387. дои : 10.1142/S1793005708001124.
  18. ^ Андреа Галасси (2018). «Верхняя граница сложности Таблута».
  19. ^ ab GI Bell (2009). "Самая короткая игра в китайские шашки и связанные с ней задачи". Целые числа . 9 . arXiv : 0803.1245 . Bibcode :2008arXiv0803.1245B. doi :10.1515/INTEG.2009.003. S2CID  17141575.
  20. ^ ab Касаи, Такуми; Адачи, Акео; Ивата, Шигеки (1979). «Классы игр с камешками и полные проблемы». SIAM Journal on Computing . 8 (4): 574–586. doi :10.1137/0208046. MR  0573848.Доказывает полноту обобщения на произвольные графы.
  21. ^ Ивата, Шигеки; Касаи, Такуми (1994). «Игра «Отелло» на доске n × n {\displaystyle n\times n} является PSPACE-полной». Теоретическая информатика . 123 (2): 329–340. doi : 10.1016/0304-3975(94)90131-7 . MR  1256205.
  22. ^ Роберт Бриземейстер (2009). Анализ и реализация игры OnTop (PDF) (диссертация). Университет Маастрихта, кафедра инженерии знаний.
  23. ^ Марк Х. М. Винандс (2004). Информированный поиск в сложных играх (PDF) (диссертация). Маастрихтский университет, Маастрихт, Нидерланды. ISBN 90-5278-429-9.
  24. ^ Размер пространства состояний и игрового дерева для шахмат впервые был оценен в работе Клода Шеннона (1950). "Программирование компьютера для игры в шахматы" (PDF) . Philosophical Magazine . 41 (314). Архивировано из оригинала (PDF) 2010-07-06.Шеннон дал оценки 1043 и 10120 соответственно , что меньше верхней границы в таблице, которая подробно описана в числе Шеннона .
  25. ^ Френкель, Авиезри С .; Лихтенштейн, Дэвид (1981). «Вычисление идеальной стратегии для шахмат n × n {\displaystyle n\times n} требует времени, экспоненциального по n {\displaystyle n}». Журнал комбинаторной теории, серия A. 31 ( 2): 199–214. doi : 10.1016/0097-3165(81)90016-9 . MR  0629595.
  26. ^ Gualà, Luciano; Leucci, Stefano; Natale, Emanuele (2014). «Bejeweled, Candy Crush и другие игры «три в ряд» (NP-)сложны». Конференция IEEE 2014 по вычислительному интеллекту и играм, CIG 2014, Дортмунд, Германия, 26-29 августа 2014 г. IEEE. стр. 1–8. arXiv : 1403.5830 . doi :10.1109/CIG.2014.6932866.
  27. ^ Дидерик Вентинк (2001). Анализ и реализация игры Gipf (PDF) (Диссертация). Университет Маастрихта.
  28. ^ Чан-Мин Сюй; Ма, ZM; Цзюнь-Цзе Тао; Синь-Хе Сюй (2009). "Улучшения поиска числа доказательств в connect6". Китайская конференция по контролю и принятию решений 2009 г. стр. 4525. doi :10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2. S2CID  20960281.
  29. ^ Hsieh, Ming Yu; Tsai, Shi-Chun (1 октября 2007 г.). «О справедливости и сложности обобщенных игр «k-в-ряд». Теоретическая информатика . 385 (1–3): 88–100. doi : 10.1016/j.tcs.2007.05.031 . Получено 12 апреля 2018 г. – через dl.acm.org.
  30. ^ Тезауро, Джеральд (1 мая 1992 г.). «Практические вопросы обучения временным различиям». Машинное обучение . 8 (3–4): 257–277. doi : 10.1007/BF00992697 .
  31. ^ ab Shi-Jim Yen, Jr-Chang Chen; Tai-Ning Yang; Shun-Chin Hsu (март 2004 г.). "Computer Chinese Chess" (PDF) . Журнал Международной ассоциации компьютерных игр . 27 (1): 3–18. doi :10.3233/ICG-2004-27102. S2CID  10336286. Архивировано из оригинала (PDF) 2007-06-14.
  32. ^ ab Donghwi Park (2015). «Пространственно-состоянная сложность корейских шахмат и китайских шахмат». arXiv : 1507.06401 [math.GM].
  33. ^ Хор, Паскаль. "Реализация компьютерного проигрывателя для Abalone с использованием поиска Alpha-Beta и Monte-Carlo" (PDF) . Кафедра инженерии знаний, Маастрихтский университет . Получено 29.03.2012 .
  34. ^ Копчинский, Джейкоб С. (2014). Pushy Computing: Complexity Theory and the Game Abalone (диссертация). Колледж Рида.
  35. ^ Йостен, Б. «Создание игрового агента Havannah» (PDF) . Получено 29.03.2012 .
  36. ^ E. Bonnet; F. Jamain; A. Saffidine (25 марта 2014 г.). «Havannah и TwixT являются PSPACE-полными». arXiv : 1403.6518 [cs.CC].
  37. ^ Кевин Мёскер (2009). Txixt: Теория, анализ и реализация (PDF) (Диссертация). Факультет гуманитарных и естественных наук Маастрихтского университета.
  38. ^ Лиза Гленденнинг (май 2005 г.). Освоение Quoridor (PDF) . Компьютерные науки (бакалаврская диссертация). Университет Нью-Мексико . Архивировано из оригинала (PDF) 2012-03-15.
  39. ^ Кэтлин Хейден (2009). Реализация компьютерного проигрывателя для Каркассона (PDF) (диссертация). Университет Маастрихта, кафедра инженерии знаний.
  40. ^ Меньший коэффициент ветвления — для второго игрока.
  41. ^ Клетцер, Жюльен; Иида, Хироюки; Бузи, Бруно (2007). «Подход Монте-Карло в Amazons» (PDF) . Computer Games Workshop, Амстердам, Нидерланды, 15–17 июня 2007 г. стр. 185–192.
  42. ^ PPLM Hensgens (2001). «Подход к игре амазонок, основанный на знаниях» (PDF) . Университет Маастрихта, Институт знаний и агентных технологий.
  43. ^ RA Hearn (2 февраля 2005 г.). «Amazons — это PSPACE-complete». arXiv : cs.CC/0502013 .
  44. ^ Хироюки Иида; Макото Сакута; Джефф Ролласон (январь 2002 г.). «Компьютерные сёги». Искусственный интеллект . 134 (1–2): 121–144. дои : 10.1016/S0004-3702(01)00157-6 .
  45. ^ Х. Адачи; Х. Камекава; С. Ивата (1987). «Сёги на доске n × n завершаются за экспоненциальное время». Trans. IEICE . J70-D: 1843–1852.
  46. ^ FC Schadd (2009). Методы поиска Монте-Карло в современной настольной игре Thurn and Taxis (PDF) (диссертация). Университет Маастрихта. Архивировано из оригинала (PDF) 2021-01-14.
  47. ^ Джон Тромп; Гуннар Фарнебек (2007). «Комбинаторика Го».В данной статье выводятся границы 48<log(log( N ))<171 для числа возможных игр N .
  48. ^ Джон Тромп (2016). «Количество допустимых позиций в Го».
  49. ^ JM Robson (1983). «Сложность игры в го». Обработка информации; Труды Конгресса IFIP . С. 413–417.
  50. ^ Christ-Jan Cox (2006). «Анализ и реализация игры Аримаа» (PDF) .
  51. ^ Дэвид Цзянь Ву (2011). «Рейтинг и оценка ходов в игре Аримаа» (PDF) .
  52. ^ Брайан Хаскин (2006). «Взгляд на фактор ветвления Аримаа».
  53. ^ AFC Arts (2010). Соревновательная игра в Stratego (PDF) (Диссертация). Маастрихт.
  54. ^ CDA Evans и Joel David Hamkins (2014). «Трансфинитные игровые значения в бесконечных шахматах». arXiv : 1302.4377 [math.LO].
  55. ^ Стефан Райш, Джоэл Дэвид Хэмкинс и Филипп Шлихт (2012). «Проблема мата в бесконечных шахматах разрешима». Конференция по вычислимости в Европе : 78–88. arXiv : 1201.5597 .{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  56. ^ Алекс Черчилль, Стелла Бидерман и Остин Херрик (2020). «Magic: the Gathering is Turing Complete». arXiv : 1904.09828 [cs.AI].{{cite arXiv}}: CS1 maint: несколько имен: список авторов ( ссылка )
  57. ^ Стелла Бидерман (2020). «Магия: Сбор так же сложен, как арифметика». arXiv : 2003.05119 [cs.AI].
  58. ^ Локштанов, Даниэль; Суберкасо, Бернардо (14 мая 2022 г.). «Wordle is NP-hard». arXiv : 2203.16713 [cs.CC].

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

Взято с "https://en.wikipedia.org/w/index.php?title=Game_complexity&oldid=1246673284"