Иди и математика

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

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

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

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

Без ко

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

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

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

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

По японским правилам ко игра Go является EXPTIME -завершенной. ^[3]

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

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

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

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

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

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

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

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

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

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

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

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

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

Размер платы n×n	3 ^{н ²}	Процент легальности	$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 ³⁸	23.44%	1.03919148791 × 10 ³⁸
13 × 13	4.30023359390 × 10 ⁸⁰	8.66%	3.72497923077 × 10 ⁷⁹
19 × 19	1.74089650659 × 10 ¹⁷²	1.20%	2.08168199382 × 10 ¹⁷⁰

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

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

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

Размер игры	Размер платы 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.9 × 10 ⁴
4 × 4	16	2.1 × 10 ¹³	9	6.9 × 10 ¹⁰
5 × 5	25	1.6 × 10 ²⁵	15	9.3 × 10 ²⁰
9 × 9	81	5.8 × 10 ¹²⁰	45	7.6 × 10 ⁸⁵
13 × 13	169	4.3 × 10 ³⁰⁴	90	3.2 × 10 ²⁰⁰
19 × 19	361	1.0 × 10 ⁷⁶⁸	200	3 × 10 ⁵¹¹	10 ⁴⁸	10 ^{10 ⁴⁸}	10 ^{10 ¹⁷¹}
21 × 21	441	2.5 × 10 ⁹⁷⁶	250	1.3 × 10 ⁶⁶¹

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

Самая длинная игра L (19 × 19)	( Н ) _Л	Нижний лимит игр	Верхний предел игр	Примечания
1	361	361	361	Белые сдаются после первого хода, 361 игнорируя всю симметрию, включая y = x else (расстояния от угла) 10×10−10=90 90/2=45 +10 (добавление обратно x = y точек симметрии ) = 55.
2	722		721	Черные сдаются после первого хода белых, 721 игнорируя всю симметрию, включая y=x else 19×19−19=342 342/2=171 +19 = 190 − 1 = 189.
50	2.1 × 10 ¹²⁶		7.5 × 10 ¹²⁷
100	1.4 × 10 ²⁴⁹		5.6 × 10 ²⁵⁵
150	6.4 × 10 ³⁶⁷		4.2 × 10 ³⁸³
200	1.9 × 10 ⁴⁸¹		3.2 × 10 ⁵¹¹
250	8.2 × 10 ⁵⁸⁷		2.4 × 10 ⁶³⁹
300	2.8 × 10 ⁶⁸⁴		7.8 × 10 ⁷⁶⁶
350	3.6 × 10 ⁷⁶⁰		1.3 × 10 ⁸⁹⁵
361	1.4 × 10 ⁷⁶⁸		1.8 × 10 ⁹²³	Самая длинная игра с использованием 181 черного и 180 белых камней.
411	н/д		1.3 × 10 ¹⁰⁵¹	Самая длинная профессиональная игра ^[16]
500	н/д		5.7 × 10 ¹²⁷⁸
1000	н/д		3.2 × 10 ²⁵⁵⁷
47 миллионов	н/д		10 ^{10 ⁸}	361 ³ движется
10 ⁴⁸	н/д	10 ^{10 ⁴⁸}	10 ^{10 ¹⁷¹}	Самая длинная игра

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

См. также

Примечания

^ «Идите к бесконечно малым в библиотеке сэнсэя» . Senseis.xmp.net . Проверено 10 февраля 2022 г.
^ Jump up to: Перейти обратно: ^а ^б Лихтенштейн, Дэвид; Сипсер, Майкл (апрель 1980 г.). «Go — это сложно в полиномиальном пространстве» (PDF) . Журнал АКМ . 27 (2): 393–401. дои : 10.1145/322186.322201 . S2CID 29498352 .
^ Jump up to: Перейти обратно: ^а ^б Робсон, Джон (1983). «Сложность Го». Материалы 9-го Всемирного компьютерного конгресса ИФИП по обработке информации : 413–417.
^ Jump up to: Перейти обратно: ^а ^б ^с Робсон, Дж (1984). «Комбинаторные игры с экспоненциальным пространством, задачи полного решения». Математические основы информатики 1984 . Конспекты лекций по информатике. Том. 176. стр. 498–506. дои : 10.1007/BFb0030333 . ISBN 978-3-540-13372-8 . {{cite book}}: |journal= игнорируется ( помогите )
^ Авиезри Френкель и Д. Лихтенштейн (1981). «Для расчета идеальной стратегии для шахмат n × n требуется экспонента времени от n» . Дж. Комб. Теория А. 31 (2): 199–214. дои : 10.1016/0097-3165(81)90016-9 .
^ Дж. М. Робсон (1984). «N на N шашек завершено». SIAM Journal по вычислительной технике . 13 (2): 252–267. дои : 10.1137/0213018 .
^ Вулф, Дэвид (2002). Новаковски, Ричард Дж. (ред.). «Эндшпили в го сложны для PSPACE» (PDF) . Дополнительные игры без шансов, Публикации Научно-исследовательского института математических наук 42 : 125–136. Архивировано из оригинала (PDF) 10 августа 2017 г. Проверено 9 июля 2016 г.
^ Крашмару, Марсель; Тромп, Джон (2000). «Лестницы укомплектованы PSPACE». Компьютеры и игры . Конспекты лекций по информатике. Том. 2063. Спрингер. стр. 241–249. CiteSeerX 10.1.1.24.4665 . дои : 10.1007/3-540-45579-5_16 . ISBN 978-3-540-43080-3 .
^ Jump up to: Перейти обратно: ^а ^б Тромп, Дж .; Фарнебек, Г. (2007), «Комбинаторика го», Компьютеры и игры , Конспекты лекций по информатике, том. 4630, Springer, Берлин, Гейдельберг, стр. 84–99, doi : 10.1007/978-3-540-75538-8_8 , ISBN. 978-3-540-75537-1
^ 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
^ «Комбинаторика Го» (PDF) . github.io . Проверено 17 июня 2023 г.
^ Эллис 1994
^ Уолрат, М; Тромп, Дж. (2016), «Гуголплекс игр в го», Компьютеры и игры , Конспекты лекций по информатике, том. 10068, Springer, Берлин, Гейдельберг, стр. 191–201, doi : 10.1007/978-3-319-50935-8_18 , ISBN. 978-3-319-50934-1
^ «Дом — Американская ассоциация го» . www.usgo.org . Проверено 17 июня 2023 г.
^ Тромп 1999
^ «Статистика продолжительности игры го» .

Ссылки

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

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

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

[1] «Идите к бесконечно малым в библиотеке сэнсэя» . Senseis.xmp.net . Проверено 10 февраля 2022 г.

[sipser1980-2] Jump up to: Перейти обратно: ^а ^б Лихтенштейн, Дэвид; Сипсер, Майкл (апрель 1980 г.). «Go — это сложно в полиномиальном пространстве» (PDF) . Журнал АКМ . 27 (2): 393–401. дои : 10.1145/322186.322201 . S2CID 29498352 .

[robson1983-3] Jump up to: Перейти обратно: ^а ^б Робсон, Джон (1983). «Сложность Го». Материалы 9-го Всемирного компьютерного конгресса ИФИП по обработке информации : 413–417.

[robson1984-4] Jump up to: Перейти обратно: ^а ^б ^с Робсон, Дж (1984). «Комбинаторные игры с экспоненциальным пространством, задачи полного решения». Математические основы информатики 1984 . Конспекты лекций по информатике. Том. 176. стр. 498–506. дои : 10.1007/BFb0030333 . ISBN 978-3-540-13372-8 . {{cite book}}: |journal= игнорируется ( помогите )

[Fraenkel1981-5] Авиезри Френкель и Д. Лихтенштейн (1981). «Для расчета идеальной стратегии для шахмат n × n требуется экспонента времени от n» . Дж. Комб. Теория А. 31 (2): 199–214. дои : 10.1016/0097-3165(81)90016-9 .

[robson1984checkers-6] Дж. М. Робсон (1984). «N на N шашек завершено». SIAM Journal по вычислительной технике . 13 (2): 252–267. дои : 10.1137/0213018 .

[7] Вулф, Дэвид (2002). Новаковски, Ричард Дж. (ред.). «Эндшпили в го сложны для PSPACE» (PDF) . Дополнительные игры без шансов, Публикации Научно-исследовательского института математических наук 42 : 125–136. Архивировано из оригинала (PDF) 10 августа 2017 г. Проверено 9 июля 2016 г.

[8] Крашмару, Марсель; Тромп, Джон (2000). «Лестницы укомплектованы PSPACE». Компьютеры и игры . Конспекты лекций по информатике. Том. 2063. Спрингер. стр. 241–249. CiteSeerX 10.1.1.24.4665 . дои : 10.1007/3-540-45579-5_16 . ISBN 978-3-540-43080-3 .

[Tromp_and_Farnebäck_2007-9] Jump up to: Перейти обратно: ^а ^б Тромп, Дж .; Фарнебек, Г. (2007), «Комбинаторика го», Компьютеры и игры , Конспекты лекций по информатике, том. 4630, Springer, Берлин, Гейдельберг, стр. 84–99, doi : 10.1007/978-3-540-75538-8_8 , ISBN. 978-3-540-75537-1

[10] ttps://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] «Комбинаторика Го» (PDF) . github.io . Проверено 17 июня 2023 г.

[12] Эллис 1994

[13] Уолрат, М; Тромп, Дж. (2016), «Гуголплекс игр в го», Компьютеры и игры , Конспекты лекций по информатике, том. 10068, Springer, Берлин, Гейдельберг, стр. 191–201, doi : 10.1007/978-3-319-50935-8_18 , ISBN. 978-3-319-50934-1

[top_ten-14] «Дом — Американская ассоциация го» . www.usgo.org . Проверено 17 июня 2023 г.

[15] Тромп 1999

[16] «Статистика продолжительности игры го» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

v т и Идти
Overview	Handicaps Komi Rules
Equipment	Bowls Goban Katsura Kaya Stones Clamshell Slate Yunzi
Terms	Aji Atari Board positions Dame Divine move Double hane Eyes Gote, sente and tenuki Hane Hayago Jigo Joseki Kakari Keima Kiai Kikashi Ko Komi Korigatachi Kosumi Ladder Liberty Miai Monkey jump Moyo Myoushu Nakade Nerai Myoushu Peep Pincer Probe Sabaki Seki Sente Shape Shoulder hit Tesuji Thickness Yose
Strategy and tactics	Capturing race Fuseki Chinese Kobayashi Shinfuseki Shusaku Jōseki Nadare Taisha Ko fight Ladder Life and death Mirror Go Opening theory Proverbs Shape Empty triangle Ponnuki Tenuki Tsumego
History	Classic of Arts Dunhuang Go Manual Emperor Yao Four Go houses Four arts Hoensha 9 Pin Zhi Oskar Korschelt Oshirogo Players European players Female players Nihon Ki-in Hall of Fame Professional handicaps
Competition	Go professional Ranks and ratings Dan Kyū Honorary titles Jubango Title holders Tournaments
Games and matches	AlphaGo vs. Fan Hui AlphaGo vs. Ke Jie AlphaGo vs. Lee Sedol Atomic bomb game Blood-vomiting game Ear-reddening game The Game of the Century Kamakura jubango Lee's broken ladder game
Art and media	AlphaGo The Divine Move The Girl Who Played Go The Go Master The Go Player Go World Hikaru no Go Igo Hatsuyōron Long Ode to Watching Weiqi The MANIAC The Master of Go Ranka Sensei's Library Shibumi The Surrounding Game The Weiqi Devil
Computers	Computer Go UEC Cup Engines AlphaGo AlphaGo Master AlphaGo Zero AlphaZero Crazy Stone Darkforest Fine Art GNU Go KataGo Leela Leela Zero Zen Future of Go Summit Monte Carlo tree search Smart Game Format Servers KGS Go Server Pandanet Tygem
Organizations	American Go Association Australian Go Association British Go Association China China Qiyuan Chinese Weiqi Association Hong Kong Go Association European Go Federation French Federation of Go International Go Federation Irish Go Association Japan All Japan Student Go Federation Kansai Ki-in Nihon Ki-in Korea Korea Baduk Association Myongji University Mind Sports Organisation New Zealand Go Society Singapore Weiqi Association Taiwan Chi Yuan Culture Foundation
Other	Benson's algorithm Game record (kifu) Games played with Go equipment Go and mathematics Variants Batoo Capture go Sygo
Go portal Category