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

Идти
Часть серии по

Особенности игры
Правила Инвалиды Пословицы Список терминов Стратегия и тактика Дебют ( теория ; стратегия ) Фусеки (отверстия во всю доску) Джосеки (угловые проемы) Жизнь и смерть Цумего (Пазлы)
История и культура
История Оборудование Варианты Четыре дома Список игр
Игроки и организации
Игроки Европейский женский Звания и рейтинги Профессионалов Организации Соревнования
Компьютеры и математика
Иди и математика Computer Go Программное обеспечение Go Серверы Internet Go AlphaGo против Ли Седола
v т е

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

Вычислительная сложность [ править ]

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

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

Без ко [ править ]

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

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

Японское правило ко [ править ]

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

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

Правило суперко [ править ]

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

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

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

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

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

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

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

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

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

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

Правовые позиции [ править ]

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

Размер платы n × n	3 ^{п ²}	Процент юридических	${\ 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 ³⁸	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 ¹⁷⁰

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

На компьютер ученый Виктор Allis отмечает , что типичные игры между экспертами длятся около 150 ходов, при среднем около 250 вариантов на каждый ход, предлагая игру-дерева сложности из 10 ³⁶⁰ . ^[12] Для числа теоретически возможных игр, включая игры, в которые невозможно играть на практике, Тромп и Фарнебек дают нижнюю и верхнюю границы 10 ^{10 ⁴⁸} и 10 ^{10 ¹⁷¹} соответственно. ^[9] Нижняя граница была улучшена до гуголплекс по Walraet и Тромпом. ^[13] Наиболее часто цитируемое число возможных игр - 10 ⁷⁰⁰^[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,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 образует верхний предел. Более точный предел представлен в статье Тромпа / Фарнебека.

Самая длинная игра L (19 × 19)	( N ) _L	Нижний предел игр	Верхний предел игр	Примечания
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, иначе 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 ¹ ⁄ ₄ года, играя по 16 часов в день с одним ходом в секунду, чтобы сыграть 47 миллионов ходов.

См. Также [ править ]

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

Примечания [ править ]

^ Перейти к бесконечно малым
^ a b Лихтенштейн, Дэвид; Сипсер, Майкл (апрель 1980 г.). "Go - это сложно в полиномиальном пространстве" (PDF) . Журнал ACM . 27 (2): 393–401. DOI : 10.1145 / 322186.322201 .
^ a b Робсон, Джон (1983). «Сложность го». Труды 9-го Всемирного компьютерного конгресса по обработке информации IFIP: 413–417.
^ a b c Робсон, J (1984). Комбинаторные игры с задачами полных решений в экспоненциальном пространстве . Труды по математическим основам информатики . Конспект лекций по информатике. 176 . С. 498–506. DOI : 10.1007 / BFb0030333 . ISBN 978-3-540-13372-8.
^ Авиэзри Френкель и Д. Lichtenstein (1981). «Вычисление идеальной стратегии для шахмат размера n × n требует экспоненциального времени по n» . J. Comb. Чт. . 31 (31): 199–214. DOI : 10.1016 / 0097-3165 (81) 90016-9 .
↑ Дж. М. Робсон (1984). «N на N шашек - Exptime завершен». SIAM Journal on Computing . 13 (2): 252–267. DOI : 10.1137 / 0213018 .
Перейти ↑ Wolfe, David (2002). Новаковски, Ричард Дж. (Ред.). «Го-эндшпиль сложен для PSPACE» (PDF) . Подробнее Игры без шанса, Публикации НИИ математических наук 42 : 125–136.
^ Crâşmaru, Марсель; Тромп, Джон (2000). Лестницы являются PSPACE-Complete . Компьютеры и игры . Конспект лекций по информатике. 2063 . Springer. С. 241–249. CiteSeerX 10.1.1.24.4665 . DOI : 10.1007 / 3-540-45579-5_16 . ISBN 978-3-540-43080-3.
^ a b Тромп, Дж ; Фарнебек, G (2007), Комбинаторика го , Springer, Берлин, Гейдельберг, 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 738 015 378525 648 451 698519 643 907 259 916 015 628 128 546 089 888 314 427 12 9 715 319 317 557 736 620 397 247 064 840 935
^ https://tromp.github.io/go/gostate.pdf
^ Аллис 1994
^ Walraet, M; Тромп, J (2016), Googolplex of Go Games , Springer, Berlin, Heidelberg, doi : 10.1007 / 978-3-319-50935-8_18 , ISBN 978-3-319-50934-1
^ AGA - десять главных причин играть в го
^ Тромп 1999
^ 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). «Комбинаторика го» .

Внешние ссылки [ править ]

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

[1] Перейти к бесконечно малым

[sipser1980-2] Лихтенштейн, Дэвид; Сипсер, Майкл (апрель 1980 г.). "Go - это сложно в полиномиальном пространстве" (PDF) . Журнал ACM . 27 (2): 393–401. DOI : 10.1145 / 322186.322201 .

[robson1983-3] Робсон, Джон (1983). «Сложность го». Труды 9-го Всемирного компьютерного конгресса по обработке информации IFIP: 413–417.

[robson1984-4] Робсон, J (1984). Комбинаторные игры с задачами полных решений в экспоненциальном пространстве . Труды по математическим основам информатики . Конспект лекций по информатике. 176 . С. 498–506. DOI : 10.1007 / BFb0030333 . ISBN 978-3-540-13372-8.

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

[robson1984checkers-6] Дж. М. Робсон (1984). «N на N шашек - Exptime завершен». SIAM Journal on Computing . 13 (2): 252–267. DOI : 10.1137 / 0213018 .

[7] Перейти ↑ Wolfe, David (2002). Новаковски, Ричард Дж. (Ред.). «Го-эндшпиль сложен для PSPACE» (PDF) . Подробнее Игры без шанса, Публикации НИИ математических наук 42 : 125–136.

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

[Tromp_and_Farnebäck_2007-9] Тромп, Дж ; Фарнебек, G (2007), Комбинаторика го , Springer, Берлин, Гейдельберг, 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 738 015 378525 648 451 698519 643 907 259 916 015 628 128 546 089 888 314 427 12 9 715 319 317 557 736 620 397 247 064 840 935

[11] ttps://tromp.github.io/go/gostate.pdf

[12] Аллис 1994

[13] Walraet, M; Тромп, J (2016), Googolplex of Go Games , Springer, Berlin, Heidelberg, doi : 10.1007 / 978-3-319-50935-8_18 , ISBN 978-3-319-50934-1

[top_ten-14] AGA - десять главных причин играть в го

[15] Тромп 1999

[16] ttps://homepages.cwi.nl/~aeb/go/misc/gostat.html

[1]