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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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


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

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

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

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

(должности)

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

(в качестве бревно к базе 10)

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

(в качестве бревно к базе 10)

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

(слои )

Фактор ветвленияСсылкаКласс сложности подходящих обобщенная игра
Крестики-нолики93594PSPACE-полный[5]
Сим1538143.7PSPACE-полный[6]
Пентамино6412181075[7][8]?, но в PSPACE
Калах [9]141318[7]Обобщение неясно
Подключите четыре421321364[1][10]?, но в PSPACE
Властный (8 × 8)641527308[7]?, но в PSPACE; в п для определенных размеров[11]
Congkak141533[7]
Английские шашки (8х8) (шашки)3220 или 1831702.8[1][12]EXPTIME-завершено[13]
Авари[14]121232603.5[1]Обобщение неясно
Кубич6430342054.2[1]PSPACE-полный[5]
Двойной фиктивный мост[nb 1](52)<17<40525.6PSPACE-полный[15]
Fanorona4521464411[16]?, но в EXPTIME
Девять мужчин моррис2410505010[1]?, но в EXPTIME
Таблут8127[17]
Международные шашки (10х10)503054904[1]EXPTIME-завершено[13]
Китайские шашки (2 комплекта)12123[18]EXPTIME -полный [19]
Китайские шашки (6 комплектов)12178[18]EXPTIME -полный [19]
Реверси (Отелло)6428585810[1]PSPACE-полный[20]
OnTop (базовая игра 2p)7288623123.77[21]
Направления действий6423644429[22]?, но в EXPTIME
Гомоку (15х15, вольный стиль)2251057030210[1]PSPACE-полный[5]
Шестигранник (11x11)12157985096[7]PSPACE-полный[5]
Шахматы64471237035[23]EXPTIME-завершено (без Правило жеребьевки из 50 ходов )[24]
Украшенный драгоценностями и Конфеты Crush (8x8)64<50[25]NP-жесткий
GIPF37251329029.3[26]
Подключить63611721403046000[27]PSPACE-полный[28]
Нарды282014455250[29]Обобщение неясно
Сянци90401509538[1][30][31]?, как полагают EXPTIME-завершено
Морское ушко61251548760[32][33]PSPACE-жесткий, И в EXPTIME
Гаванна27112715766240[7][34]PSPACE-полный[35]
Twixt57214015960452[36]
Джангги904416010040[31]?, как полагают EXPTIME-завершено
Quoridor81421629160[37]?, но в PSPACE
Каркассон (2p основная игра)72>401957155[38]Обобщение неясно
Амазонки (10х10)1004021284374 или 299[39][40][41]PSPACE-полный[42]
Сёги817122611592[30][43]EXPTIME-завершено[44]
Перейти (19x19)361170360150250[1][45][46]EXPTIME-завершено[47]
Аримаа64434029217281[48][49][50]?, но в EXPTIME
Stratego9211553538121.739[51]
Бесконечные шахматы[nb 2]бесконечныйбесконечныйбесконечныйбесконечныйбесконечный[54]Неизвестно, но mate-in-n разрешима[55]
Магия: СборБесконечныйНеограниченныйНеограниченныйбесконечныйбесконечный[56]А-хард[57]

Примечания

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

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

Рекомендации

  1. ^ а б c d е ж грамм час я j k л Виктор Аллис (1994). Поиск решений в играх и искусственном интеллекте (PDF) (Кандидатская диссертация). Лимбургский университет, Маастрихт, Нидерланды. ISBN  90-900748-8-0.
  2. ^ «Комбинаторика - Расчет выбора пространства состояний TicTacToe». Обмен стеками математики. Получено 2020-04-08.
  3. ^ Т, Брайан (2018-10-20), Btsan / generate_tictactoe, получено 2020-04-08
  4. ^ Стефан Райш (1980). «Gobang - это PSPACE-vollständig (Gobang - это PSPACE-полный)». Acta Informatica. 13 (1): 59–66. Дои:10.1007 / bf00288536. S2CID  21455572.
  5. ^ а б c d Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex ist PSPACE-complete)». Акта Информ. (15): 167–191.
  6. ^ Слани, Вольфганг (26 октября 2000 г.). Сложность графических игр Рамсея. Springer-Verlag. С. 186–203. ISBN  9783540430803. Получено 12 апреля 2018 - через dl.acm.org.
  7. ^ а б c d е ж Х. Й. ван ден Херик; Дж. У. Х. М. Уйервейк; Дж. Ван Рейсвейк (2002). «Игры решены: сейчас и в будущем». Искусственный интеллект. 134 (1–2): 277–311. Дои:10.1016 / S0004-3702 (01) 00152-7.
  8. ^ Хилари К. Орман: Пентамино: победа первого игрока в Игры без шансов, Публикации ИИГС - Том 29, 1996 г., стр. 339-344. В сети: pdf.
  9. ^ См. Правила у ван ден Херика и др.
  10. ^ Джон Тромп (2010). "Игровая площадка John's Connect Four".
  11. ^ Майкл Лахманн; Кристофер Мур; Иван Рапапорт (июль 2000 г.), Кто побеждает в игре на прямоугольных досках?, ИИГС, семинар по исследованиям комбинаторной теории игр
  12. ^ Джонатан Шеффер; и другие. (6 июля 2007 г.). «Шашки решены». Наука. 317 (5844): 1518–1522. Bibcode:2007Научный ... 317.1518S. Дои:10.1126 / science.1144079. PMID  17641166. S2CID  10274228.
  13. ^ а б Дж. М. Робсон (1984). «N на N шашек - Exptime завершен». SIAM Журнал по вычислениям. 13 (2): 252–267. Дои:10.1137/0213018.
  14. ^ См. Правила в Allis 1994
  15. ^ Бонне, Эдуард; Джамейн, Флориан; Саффидин, Абдалла (3 августа 2013 г.). О сложности карточных игр с фокусами. AAAI Press. С. 482–488. ISBN  9781577356332.
  16. ^ M.P.D. Шадд; М.Х.М. Winands; J.W.H.M. Uiterwijk; Х. Дж. Ван ден Херик; M.H.J. Бергсма (2008). «Лучшая игра в Фанороне приводит к ничьей» (PDF). Новая математика и естественные вычисления. 4 (3): 369–387. Дои:10.1142 / S1793005708001124.
  17. ^ Андреа Галасси (2018). «Верхняя граница сложности таблута» (PDF).
  18. ^ а б Г.И. Белл (2009). «Самая короткая игра в китайские шашки и связанные с ними задачи». Целые числа. 9. arXiv:0803.1245. Bibcode:2008arXiv0803.1245B. Дои:10.1515 / INTEG.2009.003. S2CID  17141575.
  19. ^ а б Такуми Касаи; Акео Адачи; Сигеки Ивата (1979). «Классы камешковых игр и полные задачи». SIAM Журнал по вычислениям. 8 (4): 574–586. Дои:10.1137/0208046. Доказывает полноту обобщения на произвольные графы.
  20. ^ С. Ивата; Т. Касаи (1994). «Игра« Отелло на н * пной доске »- полная для PSPACE». Теор. Comput. Наука. 123 (2): 329–340. Дои:10.1016/0304-3975(94)90131-7.
  21. ^ Роберт Бриземейстер (2009). Анализ и реализация игры OnTop (PDF) (Тезис). Маастрихтский университет, кафедра инженерии знаний.
  22. ^ Марк Х. Винандс (2004). Информированный поиск в сложных играх (PDF) (Кандидатская диссертация). Маастрихтский университет, Маастрихт, Нидерланды. ISBN  90-5278-429-9.
  23. ^ Размер пространства состояний и дерева игр для шахмат были впервые оценены в Клод Шеннон (1950). «Программирование компьютера для игры в шахматы» (PDF). Философский журнал. 41 (314). Архивировано из оригинал (PDF) на 2010-07-06. Шеннон дал оценку 1043 и 10120 соответственно, меньше, чем верхняя граница в таблице, которая подробно описана в Число Шеннона.
  24. ^ Авиезри Френкель; Д. Лихтенштейн (1981), «Вычисление идеальной стратегии для шахмат n × n требует экспоненциального времени от n», J. Combin. Теория Сер. А, 31 (2): 199–214, Дои:10.1016/0097-3165(81)90016-9
  25. ^ Л. Гуала; С. Леуччи; Э. Натале (2014). "Bejeweled, Candy Crush и другие игры Match-Three (NP-) Hard". arXiv:1403.5830 [cs.CC ].
  26. ^ Дидерик Вентинк (2001). Анализ и реализация игры Gipf (PDF) (Тезис). Маастрихтский университет.
  27. ^ Чан-Мин Сюй; Ma, Z.M .; Цзюнь-Цзе Тао; Синь-Хэ Сюй (2009). «Улучшения поиска номера проверки в connect6». Китайская конференция по контролю и принятию решений, 2009 г.. п. 4525. Дои:10.1109 / CCDC.2009.5191963. ISBN  978-1-4244-2722-2. S2CID  20960281.
  28. ^ Се, Мин Ю; Цай, Ши-Чун (1 октября 2007 г.). «О справедливости и сложности обобщенных k-подряд игр». Теоретическая информатика. 385 (1–3): 88–100. Дои:10.1016 / j.tcs.2007.05.031. Получено 12 апреля 2018 - через dl.acm.org.
  29. ^ Тесауро, Джеральд (1 мая 1992 г.). «Практические вопросы обучения разнице во времени». Машинное обучение. 8 (3–4): 257–277. Дои:10.1007 / BF00992697.
  30. ^ а б Ши-Джим Йен, младший Чанг Чен; Тай-Нин Ян; Шунь-Чин Сюй (март 2004 г.). "Компьютерные китайские шахматы" (PDF). Журнал Международной ассоциации компьютерных игр. 27 (1): 3–18. Дои:10.3233 / ICG-2004-27102. Архивировано из оригинал (PDF) на 2007-06-14.
  31. ^ а б Парк Донхви (2015). «Космическая сложность корейских шахмат и китайских шахмат». arXiv:1507.06401 [math.GM ].
  32. ^ Хор, Паскаль. «Реализация компьютерного плеера для Abalone с использованием поиска Alpha-Beta и Monte-Carlo» (PDF). Кафедра инженерии знаний Маастрихтского университета. Получено 29 марта 2012.
  33. ^ Копчинский, Якоб С (2014). Настойчивые вычисления: теория сложности и игровой ушка (Тезис). Рид-колледж.
  34. ^ Йостен, Б. "Создание агента-исполнителя 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. ^ П. П. Л. М. Хенсгенс (2001). «Основанный на знаниях подход к игре амазонок» (PDF). Маастрихтский университет, Институт знаний и агентских технологий.
  42. ^ Р. А. Хирн (2 февраля 2005 г.). «Амазонки - это PSPACE-полная». arXiv:cs.CC/0502013.
  43. ^ Хироюки Иида; Макото Сакута; Джефф Ролласон (январь 2002 г.). «Компьютерные сёги». Искусственный интеллект. 134 (1–2): 121–144. Дои:10.1016 / S0004-3702 (01) 00157-6.
  44. ^ Х. Адачи; Х. Камекава; С. Ивата (1987). «Сёги на доске n × n завершается за экспоненциальное время». Пер. IEICE. J70-D: 1843–1852.
  45. ^ Джон Тромп; Гуннар Фарнебек (2007). «Комбинаторика го». В данной статье получены оценки 48 N)) <171 от количества возможных игр N.
  46. ^ Джон Тромп (2016). «Количество легальных позиций го».
  47. ^ Дж. М. Робсон (1983). «Сложность Го». Обработка информации; Материалы Конгресса ИФИП. С. 413–417.
  48. ^ Христос-Ян Кокс (2006). «Анализ и реализация игры Arimaa» (PDF).
  49. ^ Дэвид Цзянь Ву (2011). «Рейтинг и оценка ходов в игре Аримаа» (PDF).
  50. ^ Брайан Хаскин (2006). "Взгляд на фактор ветвления Аримаа".
  51. ^ A.F.C. Искусство (2010). Соревновательная игра в Stratego (PDF) (Тезис). Маастрихт.
  52. ^ Шахматы на бесконечной плоскости правила игры
  53. ^ Траппист-1 правила игры
  54. ^ CDA Эванс и Джоэл Дэвид Хэмкинс (2014). «Трансфинитные игровые ценности в бесконечных шахматах» (PDF). ArXiv: 1302,4377. arXiv:1302.4377.
  55. ^ Стефан Райш, Джоэл Дэвид Хэмкинс и Филлипп Шлихт (2012). «Проблема мата в бесконечных шахматах разрешима» (PDF). Конференция по вычислимости в Европе: 78–88. arXiv:1201.5597.CS1 maint: несколько имен: список авторов (связь)
  56. ^ Алекс Черчилль, Стелла Бидерман и Остин Херрик (2020). "Magic: the Gathering is Turing Complete" (PDF). Развлечение с алгоритмами. arXiv:1904.09828.CS1 maint: несколько имен: список авторов (связь)
  57. ^ Стелла Бидерман (2012). «Magic: the Gathering труднее арифметики» (PDF). Arxiv: 2003.05119: 78–88. arXiv:2003.05119.

внешняя ссылка