Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Меры сложности игры [ править ]

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

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

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

Размер игрового дерева [ править ]

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

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

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

Деревья решений [ править ]

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

Сложность решения [ править ]

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

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

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

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

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

.

Вычислительная сложность [ править ]

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

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

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

Пример: крестики-нолики (крестики-нолики) [ править ]

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

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

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

Сложности некоторых известных игр [ править ]

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

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

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

(должности)

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

(как лог по базе 10)

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

(как лог по базе 10)

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

( слои )

Фактор ветвленияСсылкаКласс сложности подходящей обобщенной игры
Крестики-нолики93594PSPACE-complete [5]
Сим1538143,7PSPACE-complete [6]
Пентамино6412181075[7] [8]?, но в PSPACE
Калах [9]14131850[7]Обобщение неясно
Подключите четыре421321 год364[1] [10]?, но в PSPACE
Власть (8 × 8)641527308[7]?, но в PSPACE ; в P для определенных размеров [11]
Congkak141533[7]
Английские шашки (8х8) (шашки)3220 или 1831 год702,8[1] [12]EXPTIME-завершено [13]
Авари [14]121232603.5[1]Обобщение неясно
Кубич6430342054,2[1]PSPACE-complete [5]
Двойной фиктивный мост [nb 1](52)<17<40525,6PSPACE-complete [15]
Fanorona4521 год464411[16]?, но в EXPTIME
Девять мужчин моррис2410505010[1]?, но в EXPTIME
Таблут81 год27[17]
Международные шашки (10х10)503054904[1]EXPTIME-завершено [13]
Китайские шашки (2 комплекта)12123180[18]EXPTIME - завершено [19]
Китайские шашки (6 комплектов)12178600[18]EXPTIME - завершено [19]
Реверси (Отелло)6428585810[1]PSPACE-complete [20]
OnTop (базовая игра 2p)72886231 год23,77[21]
Направления действий6423644429[22]?, но в EXPTIME
Гомоку (15х15, вольный стиль)2251057030210[1]PSPACE-complete [5]
Шестигранник (11x11)12157985096[7]PSPACE-complete [5]
Шахматы64471237035 год[23]EXPTIME-complete (без правила жеребьевки на 50 ходов ) [24]
Bejeweled и Candy Crush (8x8)64<5070[25]NP-жесткий
GIPF37251329029,3[26]
Подключить63611721403046000[27]PSPACE-complete [28]
Нарды282014455250[29]Обобщение неясно
Сянци90401509538[1] [30] [31]?, считается завершенным EXPTIME
Морское ушко61251548760[32] [33]PSPACE-хард , а в EXPTIME
Гаванна27112715766240[7] [34]PSPACE-complete [35]
Twixt57214015960452[36]
Джангги904416010040[31]?, считается завершенным EXPTIME
Quoridor81 год421629160[37]?, но в PSPACE
Каркассон (базовая игра 2 очка)72> 401957155[38]Обобщение неясно
Амазонки (10х10)1004021284374 или 299 [39][40] [41]PSPACE-complete [42]
Сёги81 год7122611592[30] [43]EXPTIME-завершено [44]
Турн и Таксис (2 игрока)336624056879[45]
Перейти (19x19)361170360150250[1] [46] [47]EXPTIME-завершено [48]
Аримаа64434029217281[49] [50] [51]?, но в EXPTIME
Stratego9211553538121,739[52]
Бесконечные шахматы [nb 2]бесконечныйбесконечныйбесконечныйбесконечныйбесконечный[55]Неизвестно, но mate-in-n разрешимо [56]
Магия: СборБесконечныйНеограниченныйНеограниченныйбесконечныйбесконечный[57]А-хард [58]

Примечания [ править ]

  1. ^ Двойной фиктивный мост (то есть задачи с двойным фиктивным мостом в контексте контрактного моста ) не является настоящей настольной игрой, но имеет похожее игровое дерево и изучается в компьютерном мосте . Стол бриджа можно рассматривать как имеющий один слот для каждого игрока и трюк для разыгрывания карты, что соответствует размеру доски 52. Сложность игрового дерева - очень слабая верхняя граница: 13! до 4-х игроков вне зависимости от законности. Сложность пространства состояний предназначена для одной сделки; аналогичным образом независимо от законности, но с устранением многих транспозиций. Обратите внимание, что последние 4 слоя всегда являются принудительными перемещениями с коэффициентом ветвления 1.
  2. ^ Бесконечные шахматы - это класс игр, в который вкачестве примероввходят « Шахматы на бесконечной плоскости» и « Траппист-1» . [53] [54]

Ссылки [ править ]

  1. ^ Б с д е е г ч я J K L Виктора Эллиса (1994). Поиск решений в играх и искусственный интеллект (PDF) (кандидатская диссертация). Лимбургский университет, Маастрихт, Нидерланды. ISBN 90-900748-8-0.
  2. ^ "Комбинаторика - Расчет пространства состояний TicTacToe" . Обмен математическими стеками . Проверено 8 апреля 2020 .
  3. ^ T, Брайан (20.10.2018), Btsan / generate_tictactoe , получено 8 апреля 2020 г.
  4. ^ Стефан Рейш (1980). «Gobang - это PSPACE-vollständig (Gobang является PSPACE-полным)». Acta Informatica . 13 (1): 59–66. DOI : 10.1007 / bf00288536 . S2CID 21455572 . 
  5. ^ а б в г Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex ist PSPACE-complete)». Акта Информ. (15): 167–191.
  6. ^ Slany, Wolfgang (26 октября 2000). Сложность графических игр Рамсея . Springer-Verlag. С. 186–203. ISBN 9783540430803. Проверено 12 апреля 2018 г. - через dl.acm.org.
  7. ^ a b c d e f Х. Й. ван ден Херик; JWHM Uiterwijk; Дж. Ван Рейсвейк (2002). «Игры решены: сейчас и в будущем». Искусственный интеллект . 134 (1–2): 277–311. DOI : 10.1016 / S0004-3702 (01) 00152-7 .
  8. ^ Хилари К. Орман: пентомин: A Первого игрока Win в играх не случайно , MSRI Публикация - Том 29, 1996, стр 339-344. Онлайн: pdf .
  9. ^ См. Ван ден Херик и др. Для правил.
  10. ^ Джон Тромп (2010). «Игровая площадка Джона Connect Four» .
  11. ^ Майкл Лахманн; Кристофер Мур; Иван Рапапорт (июль 2000 г.), Кто побеждает в игре на прямоугольных досках? , ИИГС, семинар по исследованиям комбинаторной теории игр
  12. ^ Джонатан Шеффер; и другие. (6 июля 2007 г.). «Шашки решены». Наука . 317 (5844): 1518–1522. Bibcode : 2007Sci ... 317.1518S . DOI : 10.1126 / science.1144079 . PMID 17641166 . S2CID 10274228 .  
  13. ^ а б Дж. М. Робсон (1984). «N на N шашек - Exptime завершен». SIAM Journal on Computing . 13 (2): 252–267. DOI : 10.1137 / 0213018 .
  14. ↑ См. Правила в Allis 1994.
  15. ^ Бонне, Эдуард; Джамейн, Флориан; Саффидин, Абдалла (3 августа 2013 г.). О сложности карточных игр с фокусами . AAAI Press. С. 482–488. ISBN 9781577356332.
  16. ^ MPD Schadd; MHM Winands; JWHM Uiterwijk; HJ ван ден Херик; MHJ Bergsma (2008). «Лучшая игра в Фанороне приводит к ничьей» (PDF) . Новая математика и естественные вычисления . 4 (3): 369–387. DOI : 10.1142 / S1793005708001124 .
  17. ^ Андреа Галасси (2018). «Верхняя граница сложности таблута» .
  18. ^ а б Г. Белл (2009). «Самая короткая игра в китайские шашки и связанные с ними задачи» . Целые числа . 9 . arXiv : 0803.1245 . Bibcode : 2008arXiv0803.1245B . DOI : 10.1515 / INTEG.2009.003 . S2CID 17141575 . 
  19. ^ a b Такуми Касаи; Акео Адачи; Сигеки Ивата (1979). «Классы камешковых игр и полные задачи». SIAM Journal on Computing . 8 (4): 574–586. DOI : 10.1137 / 0208046 . Доказывает полноту обобщения на произвольные графы.
  20. ^ С. Ивата; Т. Касаи (1994). «Игра« Отелло на н * пной доске »полностью завершена для PSPACE». Теор. Comput. Sci . 123 (2): 329–340. DOI : 10.1016 / 0304-3975 (94) 90131-7 .
  21. ^ Роберт Бриземейстер (2009). Анализ и реализация игры OnTop (PDF) (Диссертация). Маастрихтский университет, кафедра инженерии знаний.
  22. ^ Марк HM Winands (2004). Информированный поиск в сложных играх (PDF) (кандидатская диссертация). Маастрихтский университет, Маастрихт, Нидерланды. ISBN  90-5278-429-9.
  23. ^ Размер пространства состояний и дерева игр для шахмат были впервые оценены Клодом Шенноном (1950). «Программирование компьютера для игры в шахматы» (PDF) . Философский журнал . 41 (314). Архивировано из оригинального (PDF) 06.07.2010. Шеннон дал оценки 10 43 и 10 120 соответственно, что меньше верхней границы в таблице, которая подробно описана в числе Шеннона .
  24. ^ Авиэзри Френкель ; Д. Лихтенштейн (1981), «Вычисление идеальной стратегии для шахмат n × n требует экспоненциального времени по n», J. Combin. Теория Сер. , 31 (2): 199-214, DOI : 10,1016 / 0097-3165 (81) 90016-9
  25. ^ Л. Гуала; С. Леуччи; Э. Натале (2014). "Bejeweled, Candy Crush и другие игры Match-Three (NP-) Hard". arXiv : 1403.5830 [ cs.CC ].
  26. ^ Diederik Wentink (2001). Анализ и реализация игры Gipf (PDF) (Диссертация). Маастрихтский университет.
  27. ^ Чан-Мин Сюй; Ма, ЗМ; Цзюнь-Цзе Тао; Синь-Хэ Сюй (2009). «Улучшения поиска номера проверки в connect6». 2009 китайское управление и принятие решений конференция . п. 4525. DOI : 10,1109 / CCDC.2009.5191963 . ISBN 978-1-4244-2722-2. S2CID  20960281 .
  28. ^ Се, Мин Ю; Цай, Ши-Чун (1 октября 2007 г.). «О справедливости и сложности обобщенных k-подряд игр» . Теоретическая информатика . 385 (1–3): 88–100. DOI : 10.1016 / j.tcs.2007.05.031 . Проверено 12 апреля 2018 г. - через dl.acm.org.
  29. ^ Тесауро, Джеральд (1 мая 1992). «Практические вопросы обучения разнице во времени» . Машинное обучение . 8 (3–4): 257–277. DOI : 10.1007 / BF00992697 .
  30. ^ a b Ши-Джим Йен, младший-Чанг Чен; Тай-Нин Ян; Шунь-Чин Сюй (март 2004 г.). "Компьютерные китайские шахматы" (PDF) . Журнал Международной ассоциации компьютерных игр . 27 (1): 3–18. DOI : 10.3233 / МКГ-2004-27102 . Архивировано из оригинального (PDF) 14 июня 2007 года.
  31. ^ a b Парк Донгви (2015). «Космическая сложность корейских шахмат и китайских шахмат». arXiv : 1507.06401 [ math.GM ].
  32. ↑ Хор, Паскаль. «Реализация компьютерного плеера для морского ушка с использованием поиска Alpha-Beta и Monte-Carlo» (PDF) . Кафедра инженерии знаний Маастрихтского университета . Проверено 29 марта 2012 года .
  33. ^ Kopczynski, Jacob S (2014). Настойчивые вычисления: теория сложности и игровой ушка (тезис). Рид-колледж.
  34. ^ Joosten, B. "Создание агента игры Havannah" (PDF) . Проверено 29 марта 2012 года .
  35. ^ Э. Бонне; Ф. Джамейн; А. Саффидин (25 марта 2014 г.). «Havannah и TwixT созданы для PSPACE». arXiv : 1403.6518 [ cs.CC ].
  36. ^ Кевин Моэскер (2009). TWIXT: ТЕОРИЯ, АНАЛИЗ И РЕАЛИЗАЦИЯ (PDF) (Диссертация). Маастрихтский университет, факультет гуманитарных наук и наук Маастрихтского университета.
  37. ^ Лиза Гленденнинг (май 2005). Освоение Quoridor (PDF) . Компьютерные науки (докторская диссертация). Университет Нью-Мексико . Архивировано из оригинального (PDF) 15 марта 2012 года.
  38. ^ Кэтлин Хейден (2009). Реализация компьютерного плеера для Каркассона (PDF) (Диссертация). Маастрихтский университет, кафедра инженерии знаний.
  39. ^ Меньший коэффициент ветвления - для второго игрока.
  40. ^ Жюльен Клётцер; Хироюки Иида; Бруно Бузи (2007), Подход Монте-Карло в амазонках , CiteSeerX 10.1.1.79.7640 
  41. ^ PPLM Hensgens (2001). «Основанный на знаниях подход к игре амазонок» (PDF) . Маастрихтский университет, Институт знаний и агентских технологий.
  42. ^ RA Херн (2005-02-02). «Амазонки - это PSPACE-полная». arXiv : cs.CC/0502013 .
  43. ^ Хироюки Иида; Макото Сакута; Джефф Ролласон (январь 2002 г.). «Компьютерные сёги». Искусственный интеллект . 134 (1–2): 121–144. DOI : 10.1016 / S0004-3702 (01) 00157-6 .
  44. ^ Х. Адачи; Х. Камекава; С. Ивата (1987). «Сёги на доске n × n завершается за экспоненциальное время». Пер. IEICE . J70-D: 1843–1852.
  45. ^ FC Schadd (2009). Методы поиска Монте-Карло в современной настольной игре «Турн и такси» (PDF) (Диссертация). Маастрихтский университет.
  46. ^ Джон Тромп; Гуннар Фарнебек (2007). «Комбинаторика го» .Эта статья выводит за рамки 48 <журнал (журнала ( N )) <171 от числа возможных игр N .
  47. ^ Джон Тромп (2016). «Количество легальных позиций го» .
  48. ↑ Дж. М. Робсон (1983). «Сложность го». Обработка информации; Материалы Конгресса ИФИП . С. 413–417.
  49. ^ Крист-Ян Кокс (2006). «Анализ и реализация игры Arimaa» (PDF) .
  50. ^ Дэвид Цзянь Ву (2011). «Рейтинг и оценка ходов в игре Аримаа» (PDF) .
  51. ^ Брайан Хаскин (2006). «Взгляд на фактор ветвления Аримаа» .
  52. ^ Искусство AFC (2010). Соревновательная игра в Stratego (PDF) (Диссертация). Маастрихт.
  53. ^ Правила игры в шахматы на бесконечной плоскости
  54. ^ Правила игры Trappist-1
  55. ^ CDA Эванс и Джоэл Дэвид Хэмкинс (2014). «Трансфинитные игровые ценности в бесконечных шахматах». arXiv : 1302,4377 [ math.LO ].
  56. ^ Стефан Райш, Джоэл Дэвид Хэмкинс и Филлипп Шлихт (2012). «Мат-в-п проблема бесконечных шахмат разрешима» (PDF) . Конференция по вычислимости в Европе : 78–88. arXiv : 1201.5597 . CS1 maint: несколько имен: список авторов ( ссылка )
  57. ↑ Алекс Черчилль, Стелла Бидерман и Остин Херрик (2020). «Магия: собрание по Тьюрингу завершено» (PDF) . Развлечение с алгоритмами . arXiv : 1904.09828 . CS1 maint: несколько имен: список авторов ( ссылка )
  58. ^ Стелла Бидерман (2020). «Магия: сбор труднее арифметики» (PDF) . arXiv : 2003.05119 [ cs.AI ].

См. Также [ править ]

  • Иди и математика
  • Решенная игра
  • Решение шахмат
  • Число Шеннона
  • список NP-полных игр и головоломок
  • список игр и головоломок для PSPACE

Внешние ссылки [ править ]

  • Дэвид Эпштайна «s Вычислительная сложность игры и головоломки