Войти
Игра Го - одна из самых популярных игр в мире. Благодаря своим элегантным и простым правилам, игра долгое время служила источником математических исследований. Шэнь Куо, китайский ученый XI века, подсчитал, что количество возможных позиций на доске составляет около 10 в Очерки прудов снов. В более поздние годы исследование игры Джоном Х. Конвеем привело к изобретению сюрреалистических чисел и внесло свой вклад в развитие комбинаторной теории игр (с Go Infinitesimals является конкретным примером его использования в Go).
Generalized Go воспроизводится на платах nxn, а вычислительная сложность определения победителя в данной позиции обобщенного го в решающей степени зависит от правил ко.
Го «почти» в PSPACE, поскольку в обычной игре ходы необратимы, и только через захват есть возможность повторяющихся шаблонов, необходимых для более сложной сложности.
Без Ко, Го PSPACE-hard. Это подтверждается сведением логической формулы True Quantified Boolean, которая, как известно, является полной PSPACE, до обобщенной географии, планарной обобщенной географии, до планарной обобщенной географии с максимальной степенью 3, наконец, позиции Go.
Go with superko неизвестно в PSPACE. Хотя в реальных играх, кажется, никогда не бывает больше 
Японское правило ко гласит, что запрещается только базовое ко, то есть ход, который возвращает доску в положение, в котором была сделана предыдущая операция. Допускаются более продолжительные повторяющиеся ситуации, что потенциально позволяет игре зацикливаться навсегда, например, тройное ко, где одновременно используются три кош, что позволяет выполнить цикл из 12 ходов.
Согласно японским правилам ко, Go является EXPTIME - завершенным.
Правило superko (также называемое Правило позиционного суперко) гласит, что повторение любой позиции на доске, которая произошла ранее, запрещено. Это правило ко используется в большинстве наборов правил Китая и США.
Это открытый вопрос, каков класс сложности Go по правилу superko. Хотя Go с японским правилом ко является полным EXPTIME, как нижняя, так и верхняя границы доказательства полноты EXPTIME Робсона нарушаются при добавлении правила суперко.
Известно, что это как минимум PSPACE-сложно, поскольку доказательство PSPACE-твердости Go не опирается на правило ко или отсутствие правила ко. Также известно, что Го находится в EXPSPACE.
Робсон показал, что если правило суперко, то есть «никакая предыдущая позиция не может быть воссоздана», добавляется к некоторым играм для двух игроков, которые завершаются EXPTIME., то новые игры будут EXPSPACE-complete. Интуитивно это связано с тем, что даже для определения допустимых ходов из позиции требуется экспоненциальный объем пространства, поскольку история игры, ведущая к позиции, может быть экспоненциально длинной.
В результате варианты суперко (ходы, повторяющие предыдущую позицию на доске, не допускаются) обобщенных шахмат и шашек являются EXPSPACE-полными, поскольку обобщенные шахматы и шашки заполнены EXPTIME. Однако этот результат не относится к го.
Эндшпиль го начинается, когда доска разделена на области, изолированные от всех других локальных областей живыми камнями, такое, что каждая локальная область имеет каноническое дерево игры полиномиального размера. На языке комбинаторной теории игр это происходит, когда игра Го раскладывается на сумму подигр с каноническими деревьями игры полиномиального размера.
С таким определением эндшпиль го является сложным для PSPACE.
Это доказывается путем преобразования задачи Quantified Boolean Formula, которая является полной PSPACE, в сумму маленькие (с каноническими деревьями игры полиномиального размера) Подигры го. Обратите внимание, что в документе не доказывается, что эндшпиль Go находится в PSPACE, поэтому они могут быть неполными для PSPACE.
Определение того, какая сторона выиграет гонку за захват лестницы, полностью зависит от PSPACE, независимо от того, действует ли японское правило ко или правило суперко. Это доказано моделированием QBF, известного как PSPACE-complete, с лестницами, которые подпрыгивают по доске, как световые лучи.
Так как каждое место на доске может быть пустым, черным или белым, на квадратной доске длиной n имеется всего 3 возможных положения; однако только часть из них является законной. Тромп и Фарнебек вывели рекурсивную формулу для допустимых положений 
| Размер платы n × n | 3 | Законный процент |  (допустимые позиции) (A094777 ) |
|---|---|---|---|
| 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. Для количества теоретически возможных игр, включая игры, в которые невозможно играть на практике, Тромп и Фарнебек дают нижнюю и верхнюю границы 10 и 10 соответственно.. Нижний граница была улучшена до Googolplex Walraet и Tromp. Наиболее часто упоминаемое число возможных игр, 10, получается путем простой перестановки 361 хода или 361! = 10. Другой распространенный вывод - предположить, что N пересечений и L самая длинная игра для N ^ L игр. Например, 400 ходов, как это видно в некоторых профессиональных играх, будут одним из 361 или 1 × 10 возможных игр.
Общее количество возможных игр зависит как от размера доски, так и от количества сделанных ходов. Хотя в большинстве игр длятся менее 400 или даже 200 ходов, возможно гораздо больше.
| Размер игры | Размер доски N (пересечения) | N! | Средняя продолжительность игры L | N | Максимальная продолжительность игры (количество ходов) | Нижний предел игр | Верхний предел игр |
|---|---|---|---|---|---|---|---|
| 2 × 2 | 4 | 24 | 3 | 64 | 386,356,909,593 | 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 |
| 21 × 21 | 441 | 2,5 × 10 | 250 | 1,3 × 10 |
Общее количество возможных игр можно оценить по размеру доски несколькими способами, некоторые из которых более точны, чем другие. Самая простая, перестановка размера доски (N) L, не включает недопустимые захваты и позиции. Принимая N как размер доски (19 × 19 = 361) и L как самую длинную игру, N образует верхний предел. Более точный предел представлен в статье Тромпа / Фарнебека.
| Самая длинная игра 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 | 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 | Самая длинная профессиональная игра | |
| 500 | н / д | 5,7 × 10 | ||
| 1000 | н / д | 3,2 × 10 | ||
| 47 миллионов | нет данных | 10 | 361 ^ 3 хода | |
| 10 | нет данных | 10 | 10 | самый длинный игра |
10, таким образом, является завышенной оценкой количества возможных игр, которые можно сыграть за 200 ходов, и заниженной оценкой количества игр, которые можно сыграть за 361 ход. Поскольку в году около 31 миллиона секунд, потребуется около 2¼ лет, играя по 16 часов в день с одним ходом в секунду, чтобы сыграть 47 миллионов ходов.
