Сколько вариантов в игре Го?

Автор статьи — Денис Демчук

Посмотрел интернет-версию книги «Мыслить и побеждать. Игра Го для начинающих» www.19×19.ru — действительно занятная книжка. Только у меня есть пара комментариев. Текст

Число возможных вариантов на доске 19х19 приблизительно равно 1740896506590319279071882380705643679466027249
502635411948281187068010516761846498411627928898
871493861209698881632078061375498718135509312951
4803369660572893075468180597603.
Это сопоставимо с числом атомов во Вселенной.

Выглядит несколько некрасиво. Связано это с тем, что писать «приблизительно равно», а потом приводить 175 значащих цифр крайне неверно. Если приблизительно, значит, что вторая-третья цифры уже не верны, а последующие не верны и подавно. С тем же успехом можно было написать 17 и побарабанить по цифровой клавиатуре так, чтобы вышло 170 знаков.

Но я отвлекся. Давно хотелось подсчитать сколько же действительно комбинаций в Го.

Сделаем самую общую оценку: сколько возможно вариантов расстановок камней на доске при условии любого сочетания черных, белых и пустых пунктов? В такой формулировке ответ будет 3^361. Но этот ответ далек от истинного…

Во-первых, доска обладает симметрией. То есть, если некий расклад повернуть на 90 градусов (то есть просто повернуть доску), расклад не изменится (Рис. 1). Аналогично можно повернуть доску на 180 и 270 градусов (Рис. 2). Это происходит от того, что у доски есть ось симметрии, которая проходит через тенген. Ось симметрии четвертого порядка, так как доску можно повернуть на 4 различных угла так, чтобы ее положение совпало с первоначальным.

Рис. 1
Рис. 2

Далее, доска обладает плоскостями симметрии (Рис. 3). И верно, отражение относительно любой из этих плоскостей не меняет позиции (Рис. 4).

Рис. 3		Рис. 4

Так что возможных позиций в 8 раз меньше.

Во-вторых, мы не учли запрещенные расположения камней: на доске не могут находится камни, у которых отсутствуют дамэ.

Рассмотрим самую простую ситуацию из трех камней (Форма 1):

Рис. 5

Здесь три камня жестко заданы, а все остальные пункты могут быть заполнены чем угодно. Таким образом с вероятностью 1/27 (1/3*1/3*1/3) в произвольном раскладе будет присутствовать такая некорректность. Перенесем нашу конструкцию в другой угол (Рис. 6).

Рис. 6

Кресты на первой группе обозначают, что в этом месте должно быть что угодно, кроме указанных трех камней, так как все варианты, когда в левом верхнем углу реализуемся Форма 1 уже были включены в предыдущее рассмотрение. Вероятность того, что в правом верхнем углу реализуется Форма 1, а в левом верхнем не реализуется 1/27 * 26/27. Аналогично рассмотрим один из нижних углов, требуя, чтобы в верхних углах Форма 1 не реализовывалась. Тогда вероятность того, что в нижнем углу возникнет Форма 1, при том, что она не возникнет в правом верхнем и она не возникнет в левом верхнем 1/27 * 26/27 * 26/27.

Итоговая вероятность того, что такая ситуация возникнет хоть в одном углу:

1/27 + 1/27 * 26 / 27 + 1/27 * (26 / 27)^2 + 1/27 * (26 / 27)^3 = 3.8 / 27

Вероятность появления Формы 1 в любом углу около 10%. То есть, если мы вычтем из всех возможных раскладов все расклады, содержащие такие незаконные расклады, то это не уменьшит результат даже на порядок!

Поэтому мы не станем рассматривать больние формы. Но кое что мы рассмотреть должны. Предыдущая форма могла появиться только в углу, а углов всего 4. Рассмотрим далее форму (Форма 2), которая может появиться только на стороне и после перейдем к форме, которая может появиться где угодно.

Рис. 7

Здесь стоит отдельно остановится на тонком моменте. Мы помним, что в трех других углах не должно быть Формы 1, так как все такие варианты мы уже рассмотрели. В левом верхнем углу Формы 1 не может быть в принципе. И теперь, какова вероятность появления Формы 2 как на диаграмме? Вероятность 1/81, но так как у нас не должно быть Форм 1, то итоговая вероятность 1/81 * (26/27)^3.

Рис. 8

Пойдем дальше (Рис. 8) и построим рядом Форму 2. Как и прежде крестами отмечена форма, которая не должна реализоваться. Вероятость ее выпадения равна 1/81 * (80/81) * (26/27)^4. Заметьте, у нас появился новый множитиль 80/81, он как раз и отсекает варианты, в которых была бы Форма 2 с Рис. 7. Так как угол теперь свободен, то необходимо ввести условие и на непоявление Формы 1 в левом верхнем углу. Для третьей формы вероятность будет 1/81 * (80/81)^2 * (26/27)^4. В конце концов мы забьем такими формами всю сторону. Три первые формы отмечены на Рис. 9 особыми знаками.

Рис. 9

Не буду писать длинную формулу из 18 слагаемых, приведу сразу вероятность: 5.9/27. Как видим вероятность для данного случая даже больше, чем для предыдущего, несмотря на то, что мы считали в контексте того, что Форма 1 уже невозможна.

Но это еще не все. Мы рассмотрели не все Формы 2, а только каждую третью. На Рис. 10 приведены те белые камни, вокруг которых черные могут построить Форму 2. Мы рассмотрели только те белые камни, которые отмечены треугольником. Осталось рассмотреть еще два набора. Аналогичное рассмотрение дает для них вероятности 4.5/27 и 2.9/27.

Рис. 10

И, в конце концов, переходим к Форме 3. На Рис. 11 показана Форма 3 и множество белых камней, вокруг которых она строится.

Рис. 11

Не будем уже рассуждать о возможные пересечениях этой формы с другими: этими пересечениями можно пренебречь. Итак, для первой Формы 3 вероятность 1/243 * (80/81)^68 * (26/27)^4, для второй 1/243 * (242/243) * (80/81)^68 * (26/27)^4… Всего 17^2 = 289 форм. Итоговая вероятность: 6.3/27.

Здесь небольшое отступление… Мы рассматривали Форму 1, так как множество белых камней там было нольмерно, то есть точки, мы рассматривали Форму 2, так как там множество белых камней было одномерным, то есть линии, мы рассматривали наконец Форму 3, так как там множество белых камней было двумерным, то есть квадрат. И именно из-за того, что у нас повышалась размерность пространства, росли и вероятности. Теперь рост размерности пространства прекратился, так что все последующие вероятности будут резко падать. Приведу пример. Вероятности для форм из двух камней, приведенных на Рис. 12 слева направо 0.12/27, 0.9/27, 0.16/27 Таким образом мы видим, что вероятность очень быстро падает, уже для восьми камней она 0.16/27! Следовательно, рассмотрение больших форм чрезмерно.

Рис. 10

Итоговая вероятность: (3.8 + 5.9 + 4.5 + 2.9 + 6.3 + 1.2)/27 = 24.6/27 = 91%. 91% Всех комбинаций отбраковывается, так как содержит запрещенные элементы. Вы можете подумать, что это много, но на самом деле на итоговую картину это не влияет.

Изначально мы считали, что число комбинаций равно 3^361 = 1.74*10^172.

Посмотрим сколько же теперь. Мы вспомним, что необходимо поделить на 8, из-за наличия симметрии, потом необходимо поделить еще на два, мы ведь считаем, что если все черные камни поменять на белые, позиция не изменится. И в конце концов отбраковать 91% всех раскладов.

Итак, 3^361 * 0.09 / 2^4 = 9.8*10^169! Мы доказали, что раскладов на самом деле на 4 порядка меньше, чем казалось вначале… Но в действительности это настолько огромные числа, что разницу прочувствовать не удасться… Например, по приблизительным оценкам, атомов во Вселнной «всего» 10^80 штук… То есть раскладов в Го феноменально больше, чем число атомов во Вселенной…

Мы можем для любопытсва сравнить количество раскладов в шахматах. Я не буду анализировать невозможные ситуации в шахматах, их все равно достаточно мало. Итак, 64 клетки, 32 фигуры. 32 фигуры можно раставить на 64 клетках 64!/32! = 4.8*10^53 способами. Если фигуры 31, то способов уже 0.15*10^53, если 30 — то 0.004*10^53. То есть всего 5*10^53 способов. Если учесть, что позиция не изменится если поменять цвета, что кони, офицеры и ладьи однаковые и их можно поменять местами, что есть 8 одинаковых пешек… Тогда число способов 5*10^53/(2^7*8!) = 5*10^53/5160960 = 10^47. Это уже получается поменьше, чем атомов во Вселенной, не правда ли? .