stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Трудно даже оценить сложность игрового дерева, но для некоторых игр можно дать приближение, возведя средний коэффициент ветвления игры 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. (Другими словами, количество цифр). Все следующие числа следует рассматривать с осторожностью: кажущиеся незначительными изменения в правилах игры могут изменить числа (которые в любом случае часто являются грубыми оценками) в огромных масштабах, которые могут легко оказаться намного больше, чем показанные числа.

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

Примечания

  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 Уитервейк; Х.Дж. ван ден Херик; МХДж Бергсма (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. doi : 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].

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

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