stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

Вычислительная сложность игры «крестики-нолики» зависит от того, как она обобщается . Естественным обобщением является m , n , k -игры : игра ведется на доске m x 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» . Математический обмен стеками . Проверено 8 апреля 2020 г.
  3. ↑ Т, Брайан (20 октября 2018 г.). "Бцан/generate_tictactoe". Гитхаб . Проверено 8 апреля 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. ^ Слани, Вольфганг (2000). «Сложность графовых игр Рэмзи». В Марсленде Т. Энтони; Фрэнк, Ян (ред.). Компьютеры и игры, Вторая международная конференция, CG 2000, Хамамацу, Япония, 26-28 октября 2000 г., Пересмотренные статьи . Конспекты лекций по информатике. Том. 2063. Спрингер. стр. 186–203. дои : 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) . В Новаковски, Ричард Дж. (ред.). Игры без шансов: материалы семинара по комбинаторным играм, проходившего в Беркли, Калифорния, 11–21 июля 1994 г. Публикации НИИ математических наук. Том. 29. Издательство Кембриджского университета. стр. 339–344. ISBN 0-521-57411-0. МР  1427975.
  9. ^ Правила см. у ван ден Херика и др.
  10. ^ Джон Тромп (2010). «Игровая площадка John's Connect Four».
  11. ^ Лахманн, Майкл; Мур, Кристофер; Рапапорт, Иван (2002). «Кто победит в Доминировании на прямоугольных досках?». В Новаковски, Ричард (ред.). Еще игры без шансов: материалы 2-го семинара по теории комбинаторных игр, проходившего в Беркли, Калифорния, 24–28 июля 2000 г. Публикации НИИ математических наук. Том. 42. Издательство Кембриджского университета. стр. 307–315. ISBN 0-521-80832-4. МР  1973019.
  12. ^ Джонатан Шеффер; и другие. (6 июля 2007 г.). «Шашки решены». Наука . 317 (5844): 1518–1522. Бибкод : 2007Sci...317.1518S. дои : 10.1126/science.1144079 . PMID  17641166. S2CID  10274228.
  13. ^ Шеффер, Джонатан (2007). «Игра окончена: черные играют и берут шашки» (PDF) . Журнал ICGA . 30 (4): 187–197. doi : 10.3233/ICG-2007-30402. Архивировано из оригинала (PDF) 3 апреля 2016 г.
  14. ^ аб Дж. М. Робсон (1984). «N на N шашек завершено». SIAM Journal по вычислительной технике . 13 (2): 252–267. дои : 10.1137/0213018.
  15. ^ Правила см. в Allis 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 . Бибкод : 2008arXiv0803.1245B. дои :10.1515/INTEG.2009.003. S2CID  17141575.
  20. ^ Аб Касаи, Такуми; Адачи, Акео; Ивата, Сигеки (1979). «Классы игр с камушками и полные задачи». SIAM Journal по вычислительной технике . 8 (4): 574–586. дои : 10.1137/0208046. МР  0573848.Доказывает полноту обобщения на произвольные графы.
  21. ^ Ивата, Сигеки; Касаи, Такуми (1994). «Игра Отелло на доске n × n {\displaystyle n\times n} является PSPACE-полной». Теоретическая информатика . 123 (2): 329–340. дои : 10.1016/0304-3975(94)90131-7 . МР  1256205.
  22. ^ Роберт Бриземайстер (2009). Анализ и реализация игры OnTop (PDF) (Диссертация). Маастрихтский университет, факультет инженерии знаний.
  23. ^ Марк Х. М. Винандс (2004). Информированный поиск в сложных играх (PDF) (кандидатская диссертация). Маастрихтский университет, Маастрихт, Нидерланды. ISBN 90-5278-429-9.
  24. ^ Размер пространства состояний и дерева игры в шахматы впервые был оценен Клодом Шенноном (1950). «Программирование компьютера для игры в шахматы» (PDF) . Философский журнал . 41 (314). Архивировано из оригинала (PDF) 6 июля 2010 г.Шеннон дал оценки 10 43 и 10 120 соответственно, что меньше верхней границы таблицы, которая подробно выражена в числе Шеннона .
  25. ^ Френкель, Авиезри С .; Лихтенштейн, Дэвид (1981). «Для расчета идеальной стратегии в шахматах требуется n × n {\displaystyle n\times n}, экспонента времени в n {\displaystyle n}». Журнал комбинаторной теории, серия А. 31 (2): 199–214. дои : 10.1016/0097-3165(81)90016-9 . МР  0629595.
  26. ^ Гуала, Лучано; Леуччи, Стефано; Натале, Эмануэле (2014). «Bejeweled, Candy Crush и другие игры в жанре «три в ряд» (NP-) сложны». Конференция IEEE 2014 по вычислительному интеллекту и играм, CIG 2014, Дортмунд, Германия, 26–29 августа 2014 г. IEEE. стр. 1–8. arXiv : 1403.5830 . дои : 10.1109/CIG.2014.6932866.
  27. ^ Дидерик Вентинк (2001). Анализ и реализация игры Gipf (PDF) (Диссертация). Маастрихтский университет.
  28. ^ Чан-Мин Сюй; Ма, ЗМ; Цзюнь-Цзе Тао; Синь-Хе Сюй (2009). «Улучшения поиска по номеру подтверждения в Connect6». 2009 Китайская конференция по контролю и принятию решений . п. 4525. дои :10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2. S2CID  20960281.
  29. ^ Се, Мин Ю; Цай, Ши-Чун (1 октября 2007 г.). «О справедливости и сложности обобщенных игр k-в-ряд». Теоретическая информатика . 385 (1–3): 88–100. дои : 10.1016/j.tcs.2007.05.031 . Получено 12 апреля 2018 г. - через dl.acm.org.
  30. ↑ Тезауро, Джеральд (1 мая 1992 г.). «Практические вопросы обучения временным разницам». Машинное обучение . 8 (3–4): 257–277. дои : 10.1007/BF00992697 .
  31. ^ аб Ши-Джим Йен-младший-Чан Чен; Тай-Нин Ян; Шун-Чин Сюй (март 2004 г.). «Компьютерные китайские шахматы» (PDF) . Журнал Международной ассоциации компьютерных игр . 27 (1): 3–18. doi : 10.3233/ICG-2004-27102. S2CID  10336286. Архивировано из оригинала (PDF) 14 июня 2007 г.
  32. ^ Аб Донхви Парк (2015). «Пространственно-государственная сложность корейских шахмат и китайских шахмат». arXiv : 1507.06401 [math.GM].
  33. ^ Припев, Паскаль. «Реализация компьютерного проигрывателя для морских ушек с использованием альфа-бета-поиска и поиска Монте-Карло» (PDF) . Кафедра инженерии знаний, Маастрихтский университет . Проверено 29 марта 2012 г.
  34. ^ Копчински, Джейкоб С. (2014). Настойчивые вычисления: теория сложности и игра «Ушко» (Диссертация). Ридский колледж.
  35. ^ Йостен, Б. «Создание игрового агента Гаванны» (PDF) . Проверено 29 марта 2012 г.
  36. ^ Э. Бонне; Ф. Джамейн; А. Саффидин (25 марта 2014 г.). «Havannah и TwixT являются PSPACE-полными». arXiv : 1403.6518 [cs.CC].
  37. ^ Кевин Моескер (2009). Txixt: Теория, анализ и реализация (PDF) (Диссертация). Факультет гуманитарных наук и наук Маастрихтского университета.
  38. ^ Лиза Гленденнинг (май 2005 г.). Освоение Коридора (PDF) . Информатика (бакалаврская диссертация). Университет Нью-Мексико . Архивировано из оригинала (PDF) 15 марта 2012 г.
  39. ^ Кэтлин Хейден (2009). Реализация компьютерного плеера для Каркассона (PDF) (Диссертация). Маастрихтский университет, факультет инженерии знаний.
  40. ^ Меньший коэффициент ветвления предназначен для второго игрока.
  41. ^ Клетцер, Жюльен; Иида, Хироюки; Бузи, Бруно (2007). «Подход Монте-Карло в амазонках» (PDF) . Семинар по компьютерным играм, Амстердам, Нидерланды, 15-17 июня 2007 г. стр. 185–192.
  42. ^ НПДМ Хенсгенс (2001). «Подход к игре амазонок, основанный на знаниях» (PDF) . Университет Маастрихта, Институт знаний и агентных технологий.
  43. ^ Р. А. Хирн (2 февраля 2005 г.). «Amazons полностью поддерживает PSPACE». arXiv : cs.CC/0502013 .
  44. ^ Хироюки Иида; Макото Сакута; Джефф Ролласон (январь 2002 г.). «Компьютерные сёги». Искусственный интеллект . 134 (1–2): 121–144. дои : 10.1016/S0004-3702(01)00157-6 .
  45. ^ Х. Адачи; Х. Камекава; С. Ивата (1987). «Сёги на доске n × n завершаются за экспоненциальное время». Пер. IEICE . J70-D: 1843–1852.
  46. ^ ФК Шадд (2009). Методы поиска Монте-Карло в современной настольной игре «Турн и Таксис» (PDF) (Диссертация). Маастрихтский университет. Архивировано из оригинала (PDF) 14 января 2021 г.
  47. ^ Джон Тромп; Гуннар Фарнебек (2007). «Комбинаторика Го».В этой статье выводятся границы 48<log(log( N ))<171 числа возможных игр N .
  48. ^ Джон Тромп (2016). «Количество легальных позиций Го».
  49. ^ Дж. М. Робсон (1983). «Сложность Го». Обработка информации; Материалы Конгресса ИФИП . стр. 413–417.
  50. ^ Христос-Ян Кокс (2006). «Анализ и реализация игры Аримаа» (PDF) .
  51. ^ Дэвид Цзянь Ву (2011). «Рейтинг и оценка ходов в игре Аримаа» (PDF) .
  52. ^ Брайан Хаскин (2006). «Взгляд на фактор ветвления Аримаа».
  53. ^ AFC Arts (2010). Соревновательная игра в Stratego (PDF) (Диссертация). Маастрихт.
  54. ^ CDA Эванс и Джоэл Дэвид Хэмкинс (2014). «Трансфинитные игровые значения в бесконечных шахматах». arXiv : 1302.4377 [math.LO].
  55. ^ Стефан Райш, Джоэл Дэвид Хэмкинс и Филипп Шлихт (2012). «Проблема мата в бесконечных шахматах разрешима». Конференция по вычислимости в Европе : 78–88. arXiv : 1201.5597 .{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  56. ^ Алекс Черчилль, Стелла Бидерман и Остин Херрик (2020). «Магия: Сбор завершен по Тьюрингу». arXiv : 1904.09828 [cs.AI].{{cite arXiv}}: CS1 maint: несколько имен: список авторов ( ссылка )
  57. ^ Стелла Бидерман (2020). «Магия: Сбор так же сложен, как арифметика». arXiv : 2003.05119 [cs.AI].
  58. ^ Локштанов, Даниэль; Суберказо, Бернардо (14 мая 2022 г.). «Слово NP-сложно». arXiv : 2203.16713 [cs.CC].

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

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