Иди и математика - Go and mathematics

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

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

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

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

Без ко

Без ко, Go - это PSPACE-жесткий.^[2] Это доказывается сокращением Истинная количественная логическая формула, который известен как PSPACE-complete, обобщенная география, планарной обобщенной географии, планарная обобщенная география с максимальной степенью 3, наконец, перейти на позиции.

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

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

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

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

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

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

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

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

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

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

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

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

С таким определением эндшпиль Го сложен для PSPACE.^[7]

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

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

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

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

Размер платы n × n	3^п^2	Процент юридических	${displaystyle L}$ (правовые позиции) (A094777 )[11]
1×1	3	33.33%	1
2×2	81	70.37%	57
3×3	19,683	64.40%	12,675
4×4	43,046,721	56.49%	24,318,165
5×5	847,288,609,443	48.90%	414,295,148,741
9×9	4.43426488243×10^38	23.44%	1.03919148791×10^38
13×13	4.30023359390×10^80	8.66%	3.72497923077×10^79
19×19	1.74089650659×10^172	1.20%	2.08168199382×10^170

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

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

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

Размер игры	Размер доски N (пересечения)	N!	Средняя продолжительность игры L	N^L	Максимальная продолжительность игры (количество ходов)	Нижний предел игр	Верхний предел игр
2×2	4	24	3	64		386,356,909,593[15]	386,356,909,593
3×3	9	3.6×10^5	5	5.9×10^4
4×4	16	2.1×10^13	9	6.9×10^10
5×5	25	1.6×10^25	15	9.3×10^20
9×9	81	5.8×10^120	45	7.6×10^85
13×13	169	4.3×10^304	90	3.2×10^200
19×19	361	1.0×10^768	200	3×10^511	10^48	10^10^48	10^10^171
21×21	441	2.5×10^976	250	1.3×10^661

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

Самая длинная игра L (19 × 19)	(N)L	Нижний предел игр	Верхний предел игр	Примечания
1	361	361	361	Белые сдаются после первого хода, 361 игнорируя всю симметрию, включая y = x else (расстояния от угла) 10x10-10 = 90 90/2 = 45 +10 (прибавляя x = y точек симметрии) = 55.
2	722		721	Черные сдаются после первого хода белых, 721 игнорируя всю симметрию, включая y = x, иначе 19x19-19 = 342 342/2 = 171 +19 = 190 - 1 = 189.
50	2.1×10^126		7.5×10^127
100	1.4×10^249		5.6×10^255
150	6.4×10^367		4.2×10^383
200	1.9×10^481		3.2×10^511
250	8.2×10^587		2.4×10^639
300	2.8×10^684		7.8×10^766
350	3.6×10^760		1.3×10^895
361	1.4×10^768		1.8×10^923	Самая длинная игра с использованием 181 черного и 180 белых камней
411	н / д		1.3×10^1051	Самая длинная профессиональная игра[16]
500	н / д		5.7×10^1278
1000	н / д		3.2×10^2557
47 миллионов	н / д		10^10^8	361 ^ 3 ходов
10^48	н / д	10^10^48	10^10^171	Самая длинная игра

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

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

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

Примечания

1. Бесконечно малые
2. Лихтенштейн, Дэвид; Сипсер, Майкл (апрель 1980 г.). «Go Is Polynomial-Space Hard» (PDF). Журнал ACM. 27 (2): 393–401. Дои:10.1145/322186.322201.
3. Робсон, Джон (1983). «Сложность Го». Материалы 9-го Всемирного компьютерного конгресса ИФИП по обработке информации: 413–417.
4. Робсон, Дж (1984). Комбинаторные игры с задачами полных решений в экспоненциальном пространстве. Труды математических основ информатики. Конспект лекций по информатике. 176. С. 498–506. Дои:10.1007 / BFb0030333. ISBN  978-3-540-13372-8.
5. Авиезри Френкель и Д. Лихтенштейн (1981). «Вычисление идеальной стратегии для шахмат размера n × n требует экспоненциального времени от n». J. Comb. Чт. А. 31 (31): 199–214. Дои:10.1016/0097-3165(81)90016-9.
6. Дж. М. Робсон (1984). «N на N шашек - Exptime завершен». SIAM Журнал по вычислениям. 13 (2): 252–267. Дои:10.1137/0213018.
7. Вулф, Дэвид (2002). Новаковски, Ричард Дж. (Ред.). "Го-эндшпиль тяжелый для PSPACE" (PDF). Другие игры без шанса, Публикации Института математических наук 42: 125–136.
8. Крашмару, Марсель; Тромп, Джон (2000). Лестницы PSPACE-Complete. Компьютеры и игры. Конспект лекций по информатике. 2063. Springer. С. 241–249. CiteSeerX  10.1.1.24.4665. Дои:10.1007/3-540-45579-5_16. ISBN  978-3-540-43080-3.
9. Тромп, Дж; Фарнебек, Г. (2007), Комбинаторика го, Шпрингер, Берлин, Гейдельберг, Дои: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 738 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. https://tromp.github.io/go/gostate.pdf
12. Эллис 1994
13. Walraet, M; Тромп, Дж (2016), Гуголплекс игр го, Шпрингер, Берлин, Гейдельберг, Дои:10.1007/978-3-319-50935-8_18, ISBN  978-3-319-50934-1
14. AGA - десять главных причин играть в го
15. Тромп 1999
16. https://homepages.cwi.nl/~aeb/go/misc/gostat.html

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

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

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

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