Го и математика

Расчеты сложности игры го

Игра Го — одна из самых популярных игр в мире. Благодаря своим элегантным и простым правилам игра долгое время была источником вдохновения для математических исследований. Шэнь Куо , китайский ученый XI века, в своих «Очерках о пуле снов» подсчитал , что количество возможных позиций на доске составляет около 10 ¹⁷² . В более поздние годы исследования игры Джоном Х. Конвеем привели к развитию сюрреалистических чисел и способствовали развитию комбинаторной теории игр (при этом Go Infinitesimals ^[1] является конкретным примером ее использования в Го).

Сложность вычислений

В обобщенную игру Го играют на досках n × n , и вычислительная сложность определения победителя в заданной позиции обобщенной игры Го в решающей степени зависит от правил ко .

Го «почти» в PSPACE , так как в обычной игре ходы необратимы, и только посредством захвата появляется возможность повторять шаблоны, необходимые для более высокой сложности.

Без ко

Без ko Go является PSPACE-сложным . ^[2] Это доказывается сведением True Quantified Boolean Formula , которая, как известно, является PSPACE-полной, к обобщенной географии , к плоской обобщенной географии, к плоской обобщенной географии с максимальной степенью 3 , и, наконец, к позициям Go.

Го с суперко не известно о наличии в PSPACE. Хотя реальные игры, похоже, никогда не длятся дольше ходов, в целом неизвестно, существует ли полиномиальная граница для длительности игр в Го. Если бы она была, Го был бы PSPACE-полным. В текущем виде он может быть PSPACE-полным, EXPTIME-полным или даже EXPSPACE-полным. ${\displaystyle n^{2}}$

Японское правило ко

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

Согласно японским правилам ко, Го является EXPTIME -завершенным. ^[3]

Правило Суперко

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

Открытой проблемой является то, каков класс сложности Go при правиле superko. Хотя Go с японским правилом ko является EXPTIME-полным, как нижняя, так и верхняя границы доказательства полноты EXPTIME Робсона ^[3] нарушаются при добавлении правила superko.

Известно, что он по крайней мере PSPACE-труден, поскольку доказательство в ^[2] PSPACE-трудности Go не опирается на правило ko или отсутствие правила ko. Также известно, что Go находится в EXPSPACE. ^[4]

Робсон ^[4] показал, что если правило суперко, то есть «никакая предыдущая позиция не может быть воссоздана», добавляется к некоторым играм для двух игроков, которые являются EXPTIME-полными, то новые игры будут EXPSPACE-полными. Интуитивно это происходит потому, что экспоненциальное количество пространства требуется даже для определения допустимых ходов из позиции, поскольку история игры, ведущая к позиции, может быть экспоненциально длинной.

В результате, варианты суперко (ходы, которые повторяют предыдущую позицию на доске, не допускаются) обобщенных шахмат и шашек являются EXPSPACE-полными, поскольку обобщенные шахматы ^[5] и шашки ^[6] являются EXPTIME-полными. Однако этот результат не применим к Го. ^[4]

Сложность некоторых конфигураций Go

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

При таком определении эндшпили в Го являются PSPACE-сложными. ^[7]

Это доказано путем преобразования задачи Quantified Boolean Formula , которая является PSPACE-полной, в сумму небольших (с полиномиальным размером канонических игровых деревьев) подигр Go. Обратите внимание, что в статье не доказывается, что эндшпили Go находятся в PSPACE, поэтому они могут не быть PSPACE-полными.

Определение того, какая сторона выигрывает гонку по захвату лестниц, является PSPACE-полным, независимо от того, применяется ли японское правило ко или правило суперко. ^[8] Это доказано путем моделирования QBF, известного как PSPACE-полный, с лестницами, которые подпрыгивают по доске, как световые лучи.

Правовые позиции

Поскольку каждое место на доске может быть либо пустым, либо черным, либо белым, всего существует 3 ^{n 2} возможных позиций на доске на квадратной доске длиной n ; однако не все из них являются допустимыми. Тромп и Фарнебек вывели рекурсивную формулу для допустимых позиций прямоугольной доски длиной m и n . ^[9] Точное число было получено в 2016 году. ^[10] Они также нашли асимптотическую формулу , где , и . Было подсчитано, что наблюдаемая вселенная содержит около 10 ⁸⁰ атомов, что намного меньше числа возможных допустимых позиций обычного размера доски (m = n = 19). По мере увеличения доски процент допустимых позиций уменьшается. ${\displaystyle L(m,n)}$ ${\displaystyle L(19,19)}$ ${\displaystyle L\approx AB^{m+n}C^{mn}}$ ${\displaystyle A\approx 0.8506399258457145}$ ${\displaystyle B\approx 0.96553505933837387}$ ${\displaystyle C\approx 2.975734192043357249381}$

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

Специалист по информатике Виктор Эллис отмечает, что типичные игры между экспертами длятся около 150 ходов, в среднем около 250 выборов на ход, что предполагает сложность дерева игры 10 ³⁶⁰ . ^[12] Для числа теоретически возможных игр, включая игры, в которые невозможно играть на практике, Тромп и Фарнебек дают нижнюю и верхнюю границы 10 ^{10 48} и 10 ^{10 171} соответственно. ^[9] Нижняя граница была улучшена до гуголплекса Вальретом и Тромпом. ^[13] Наиболее часто цитируемое число для числа возможных игр, 10 ^{700 [14],} получено из простой перестановки 361 хода или 361! = 10 ⁷⁶⁸ . Другой распространенный вывод заключается в предположении N пересечений и L самой длинной игры для N ^L общих игр. Например, 400 ходов, как это бывает в некоторых профессиональных играх, — это один из 361 ⁴⁰⁰ или 1 × 10 ¹⁰²³ возможных игр.

Общее количество возможных игр зависит как от размера доски, так и от количества сыгранных ходов. Хотя большинство игр длятся менее 400 или даже 200 ходов, возможно гораздо больше.

Общее количество возможных игр можно оценить по размеру доски несколькими способами, некоторые из которых более строгие, чем другие. Самый простой, перестановка размера доски, ( N ) _L , не учитывает нелегальные захваты и позиции. Принимая N за размер доски (19 × 19 = 361) и L за самую длинную игру, N ^L образует верхний предел. Более точный предел представлен в статье Тромпа/Фарнебека.

Таким образом, 10 ⁷⁰⁰ — это завышенная оценка количества возможных игр, которые можно сыграть за 200 ходов, и заниженная оценка количества игр, которые можно сыграть за 361 ход. Поскольку в году около 31 миллиона секунд, это займет около 2+Четверть года игры по 16 часов в день со скоростью один ход в секунду, чтобы сделать 47 миллионов ходов.

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

• Перейти портал

• Сложность игры
• Алгоритм Бога
• Число Шеннона (Шахматы)

Примечания

1. "Go Infinitesimals в библиотеке сэнсэя". senseis.xmp.net . Получено 2022-02-10 .
2. Лихтенштейн, Дэвид; Сипсер, Майкл (апрель 1980 г.). "Go Is Polynomial-Space Hard" (PDF) . Журнал ACM . 27 (2): 393–401. doi :10.1145/322186.322201. S2CID  29498352.
3. Robson, John (1983). «Сложность Go». Труды 9-го Всемирного компьютерного конгресса IFIP по обработке информации : 413–417.
4. Robson, J (1984). "Комбинаторные игры с экспоненциальным пространством полных задач принятия решений". Математические основы информатики 1984. Конспект лекций по информатике. Том 176. С. 498–506. doi :10.1007/BFb0030333. ISBN 978-3-540-13372-8. {{cite book}}: |journal=проигнорировано ( помощь )
5. Авиезри Френкель и Д. Лихтенштейн (1981). «Вычисление идеальной стратегии для шахмат n×n требует времени, экспоненциального по n». J. Comb. Theory A. 31 ( 2): 199–214. doi : 10.1016/0097-3165(81)90016-9 .
6. JM Robson (1984). «N на N чекеров — это Exptime complete». SIAM Journal on Computing . 13 (2): 252–267. doi :10.1137/0213018.
7. Вулф, Дэвид (2002). Новаковски, Ричард Дж. (ред.). «Go endgames are PSPACE-hard» (PDF) . Еще больше игр без шансов, Mathematical Sciences Research Institute Publications 42 : 125–136. Архивировано из оригинала (PDF) 2017-08-10 . Получено 2016-07-09 .
8. Crâşmaru, Marcel; Tromp, John (2000). «Ladders Are PSPACE-Complete». Computers and Games . Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 241–249. CiteSeerX 10.1.1.24.4665 . doi :10.1007/3-540-45579-5_16. ISBN  978-3-540-43080-3.
9. Tromp, J ; Farnebäck, G (2007), "Комбинаторика игры в го", Компьютеры и игры , Lecture Notes in Computer Science, т. 4630, Springer, Берлин, Гейдельберг, стр. 84–99, doi :10.1007/978-3-540-75538-8_8, ISBN 978-3-540-75537-1
10. https://tromp.github.io/go/legal.html 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935
11. "Комбинаторика Go" (PDF) . github.io . Получено 17 июня 2023 г. .
12. Эллис 1994
13. Walraet, M; Tromp, J (2016), «Гуголплекс игр в го», Компьютеры и игры , Конспект лекций по информатике, т. 10068, Springer, Берлин, Гейдельберг, стр. 191–201, doi :10.1007/978-3-319-50935-8_18, ISBN 978-3-319-50934-1
14. "Главная - Американская ассоциация го". www.usgo.org . Получено 17 июня 2023 г. .
15. Тромп 1999
16. «Статистика продолжительности игры в го».

Ссылки

• AGA. «Десять главных причин играть в го».
• Эллис, Виктор (1994). Поиск решений в играх и искусственном интеллекте (PDF) . Кандидатская диссертация, Университет Лимбурга, Маастрихт, Нидерланды. ISBN 978-90-900748-8-7.
• Хирн, Роберт А. (2006). «Игры, головоломки и вычисления» (PDF) .[Докторская диссертация, Массачусетский технологический институт.]
• Джонсон, Джордж (29 июля 1997 г.). «Чтобы проверить мощный компьютер, сыграйте в древнюю игру». New York Times .
• Пападимитриу, Христос (1994), Вычислительная сложность , Эддисон Уэсли.
• Тромп, Джон (1999). «Количество игр 2×2 с позиционным суперко».
• Тромп, Джон (2016). «Количество допустимых позиций в го (до 19×19)».
• Тромп, Джон ; Фарнебек, Гуннар (2007). «Комбинаторика Го».

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

• Го и математика
• Количество возможных результатов игры - статья в библиотеке сэнсэя