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

редактировать
понятие в комбинаторной теории игр

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

Содержание

  • 1 Меры сложности игры
    • 1.1 Сложность в пространстве состояний
    • 1.2 Размер дерева игры
    • 1.3 Деревья решений
      • 1.3.1 Сложность решения
      • 1.3.2 Дерево игры сложность
    • 1.4 Вычислительная сложность
  • 2 Пример: крестики-нолики (крестики-нолики)
  • 3 Сложность некоторых известных игр
  • 4 Примечания
  • 5 См. также
  • 6 Ссылки
  • 7 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GTC ≥ bd {\ displaystyle GTC \ geq b ^ {d}}GTC \ geq b ^ {d} .

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

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

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

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

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

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

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

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

.

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

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

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

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

(позиции)

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

(как журнал по основанию 10)

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

(как log по основанию 10)

Средняя длина игры

(слоев )

Коэффициент ветвленияRefКласс сложности подходящей обобщенной игры
Tic-tac-toe 93594PSPACE-complete
Sim 1538143.7PSPACE-complete
Пентамино 6412181075?, Но в PSPACE
Kalah 141318Обобщение неясно
Connect Four 421321364?, Но в PSPACE
Domineering (8 × 8)641527308?, Но в PSPACE ; в P для определенных размеров
Congkak 141533
Английские шашки (8x8) (шашки) 3220 или 1831702,8EXPTIME-complete
Awari 121232603.5Обобщение неясно
Qubic 6430342054,2PSPACE-complete
Двойной фиктивный мост (52)<17<40525.6PSPACE-complete
Fanorona 4521464411?, Но в EXPTIME
Девять мужчин morris 2410505010?, Но в EXPTIME
Таблут 8127
Международные шашки (10x10) 503054904EXPTIME-complete
Китайские шашки (2 набора)12123EXPTIME -завершено
Китайские шашки (6 комплектов)12178EXPTIME -завершено
Реверси (Отелло)6428585810PSPACE-complete
OnTop (базовая игра 2p)7288623123,77
Направления действий 6423644429?, Но в EXPTIME
Гомоку (15x15, вольный стиль)2251057030210PSPACE-complete
Hex (11x11) 12157985096PSPACE- завершено
Шахматы 64471237035EXPTIME-complete (без Правило рисования с 50 ходами )
Bejeweled и Candy Crush (8x8)64<50NP-hard
GIPF 37251329029,3
Connect6 3611721403046000PSPACE-complete
Нарды 282014455250Обобщение неясно
Сянци 90401509538?, Полагают быть EXPTIME-complete
Abalone 61251548760PSPACE-hard, а в EXPTIME
Havannah 27112715766240PSPACE-complete
Twixt 57214015960452
Джангги 904416010040?, Считается EXPTIME-complete
Quoridor 81421629160?, Но в PSPACE
Каркассон (2p основная игра)72>401957155Обобщение неясно
Амазонки (10x10) 1004021284374 или 299PSPACE-complete
Shogi 817122611592EXPTIME-complete
Go (19x19) 361170360150250EXPTIME-complete
Arimaa 64434029217281?, Но в EXPTIME
Stratego 9211553538121.739
Бесконечные шахматы неограниченныйEXPTIME-полный (без правила жеребьевки на 50 ходов)

Примечания

См. Также

Список литературы

  1. ^ Виктор Аллис (1994). Поиск решений в играх и искусственный интеллект (PDF) (кандидатская диссертация). Лимбургский университет, Маастрихт, Нидерланды. ISBN 90-900748-8-0.
  2. ^«Комбинаторика - Пространство состояний TicTacToe Выберите расчет». Обмен математическими стеками. Проверено 8 апреля 2020 г.
  3. ^Т, Брайан (20 октября 2018 г.), Btsan / generate_tictactoe, получено 8 апреля 2020 г.
  4. ^ Стефан Райш (1980). «Gobang - это PSPACE-vollständig (Gobang является PSPACE-полным)». Acta Informatica. 13 (1): 59–66. doi : 10.1007 / bf00288536.
  5. ^Слэни, Вольфганг (26 октября 2000 г.). Сложность графических игр Рэмси. Springer-Verlag. С. 186–203. ISBN 9783540430803. Проверено 12 апреля 2018 г. - через dl.acm.org.
  6. ^ H. Я. ван ден Херик; Дж. У. Х. М. Уйервейк; Дж. Ван Рейсвейк (2002). «Игры решены: сейчас и в будущем». Искуственный интеллект. 134 (1–2): 277–311. doi : 10.1016 / S0004-3702 (01) 00152-7.
  7. ^Хилари К. Орман: Пентамино: победа первого игрока в играх без шанса, публикации ИИГС - Том 29, 1996 г., страницы 339-344. Онлайн: pdf.
  8. ^См. Правила van den Herik et al.
  9. ^Джон Тромп (2010). "Игровая площадка Джона Коннект Четыре".
  10. ^Майкл Лахманн; Кристофер Мур; Иван Рапапорт (июль 2000 г.). «Кто побеждает на прямоугольных досках?». Исследовательский семинар по комбинаторной теории игр ИИГС. Для цитирования журнала требуется | journal =()
  11. ^Джонатан Шеффер; и др. (6 июля 2007 г.). «Шашки решены». Наука. 317 (5844): 1518–1522. Bibcode : 2007Sci... 317.1518S. doi : 10.1126 / science.1144079. PMID 17641166.
  12. ^ JM Robson (1984). «N by N checkers завершено Exptime». SIAM Journal on Computing. 13(2) : 252–267. doi : 10.1137 / 0213018.
  13. ^Правила см. В Allis 1994
  14. ^Бонне, Эдуард; Джамейн, Флориан; Саффидин, Абдалла (2013-08-03). О сложности карточных игр с обманом. AAAI Press. Pp. 482–488. ISBN 9781577356332.
  15. ^MPD Schadd; MHM Winands; JWHM Uiterwijk; HJ van den Херик; MHJ Bergsma (2008). «Лучшая игра в Фанороне приводит к ничьей» (PDF). Новая математика и естественные вычисления. 4(3): 369–387. doi : 10.1142 / S1793005708001124.
  16. ^Андреа Галасси (2018). «Верхняя граница on the Complexity of Tablut » (PDF). Для цитирования журнала требуется | journal =()
  17. ^ G.I. Белл (2009). «Самая короткая игра в китайские шашки и смежные задачи». Целые числа. arXiv : 0803.1245. Bibcode : 2008arXiv0803.1245B.
  18. ^ Такуми Касаи; Акео Адачи; Сигеки Ивата (1979). «Классы камешковых игр и полные задачи». SIAM Journal on Computing. 8 (4): 574–586. doi : 10.1137 / 0208046.Доказывает полноту обобщения на произвольные графы.
  19. ^С. Ивата; Т. Касаи (1994). «Игра« Отелло на н * пной доске »- полная для PSPACE». Теор. Comput. Sci. 123 (2): 329–340. doi : 10.1016 / 0304-3975 (94) 90131-7.
  20. ^Роберт Бриземейстер (2009). Анализ и реализация игры OnTop (PDF) (Диссертация). Маастрихтский университет, кафедра инженерии знаний.
  21. ^Марк Х.М. Винандс (2004). Информированный поиск в сложных играх (PDF) (кандидатская диссертация). Маастрихтский университет, Маастрихт, Нидерланды. ISBN 90-5278-429-9.
  22. ^Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex ist PSPACE-complete)». Акта Информ. (15): 167–191.
  23. ^Размер пространства состояний и дерева игр для шахмат были впервые оценены в Клод Шеннон (1950). «Программирование компьютера для игры в шахматы» (PDF). Философский журнал. 41 (314). Архивировано из оригинального (PDF) 06.07.2010. Шеннон дал оценки 10 и 10 соответственно, что меньше верхней границы в таблице, которая подробно описана в Номер Шеннона.
  24. ^ Авиезри Френкель ; Д. Лихтенштейн (1981), «Вычисление идеальной стратегии для шахмат n × n требует экспоненциального времени по n», J. Combin. Теория Сер. A, 31 (2): 199–214, doi : 10.1016 / 0097-3165 (81) 90016-9
  25. ^L. Гуала; С. Леуччи; Э. Натале (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. DOI : 10.1109 / CCDC.2009.5191963. ISBN 978-1-4244-2722-2.
  28. ^Се, Мин Ю; Цай, Ши-Чун (1 октября 2007 г.). «О справедливости и сложности обобщенных игр k-in-a-row». Теоретическая информатика. 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. дои : 10.1007 / BF00992697.
  30. ^ Ши-Джим Йен, младший Чанг Чен; Тай-Нин Ян; Шунь-Чин Сюй (март 2004 г.). «Компьютерные китайские шахматы» (PDF). Журнал Международной ассоциации компьютерных игр. 27 (1): 3–18. DOI : 10.3233 / ICG-2004-27102. Архивировано из оригинального (PDF) 14 июня 2007 г.
  31. ^ Парк Донгви (2015). «Космическая сложность корейских шахмат и китайских шахмат». arXiv : 1507.06401 [math.GM ].
  32. ^Хор, Паскаль. «Реализация компьютерного проигрывателя для Abalone с использованием поиска Alpha-Beta и Monte-Carlo» (PDF). Кафедра инженерии знаний Маастрихтского университета. Проверено 29 марта 2012 г.
  33. ^Kopczynski, Jacob S (2014). Настойчивые вычисления: теория сложности и игровой ушка (тезис). Колледж Рида.
  34. ^Йустен, Б. «Создание агента, играющего в Хаванну» (PDF). Проверено 29 марта 2012 г.
  35. ^E. Капот; Ф. Джамейн; А. Саффидин (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. Журнал цитирования требует | journal =()
  41. ^PPLM Hensgens (2001). «Основанный на знаниях подход к игре амазонок» (PDF). Маастрихтский университет, Институт знаний и агентских технологий. Для цитирования журнала требуется | journal =()
  42. ^Р.А. Хирн (02.02.2005). «Амазонки полностью соответствуют 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. ^Джон Тромп; Гуннар Фарнебек (2007). «Комбинаторика го».В этой статье выводятся границы 48
  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 правила игры

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

Последняя правка сделана 2021-05-21 11:11:20
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте