Сколько всего существует вариантов размещения камней на доске Го.

Посмотрел 19x19.ru действительно занятная книжка. Только у меня есть пара комментариев. Текст

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

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

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

[denis-silvers.livejournal.com]

В связи с написаным хотелось бы еще отметить, что количество вариантов раскладов на доске ой как несопоставимо с числом атомов во Вселенной :).

Это проигрывать надо достойно, а выигрывать можно как угодно.

А насколько больше "раскладов" атомов в различных конфигурациях даже представить страшно:)

Отличная статья! Буду вам признателен, если позволите разместить ее на нашем блоге ЧаВо по игре Го под вашим авторством.

Это всегда пожалуйста.

И все же число"вариантов" и число "различных расстановок" это разные числа

- - - - - - - - - - - - - - - - - - - - - - - - -
- Не обижайся: способность понять зависит от личного опыта, а не от умственных усилий… (Сэр Джуффин Халли)
Гостинная Шк. "Стожар": [100jar.blogspot.com]
Библиотека Шк. "Стожар": [librarystozhar.blogspot.com]

Цитата:

Это сопоставимо с числом атомов во Вселенной.

В Галактике. Японцы говорят - в трёх. Но с моей точки зрения, одной достаточно )

Стратегия выше цели
[clubgo.ru]

Aragorn Написал:
-------------------------------------------------------
> Это сопоставимо с числом атомов во Вселенной.
>
> В Галактике. Японцы говорят - в трёх. Но с моей
> точки зрения, одной достаточно )

Зато количество вариантов расстановок атомов во Вселенной еще больше :)

Но - все-таки, получается, что принципиально невозможно сохранить полное дерево всех вариантов. Негде хранить данные.

Но - в принципе есть другое число, на которое, как я понял, намекал Present: число осмысленных постановок, вытекающих друг из друга. Эдаких веток дерева развития начальной позиции.

Кроме того, наверняка можно отбраковать из этих веток множество веточек, заведомо ведущих к проигрышу.

И останется, видимо, не так уж и много вариантов... Подозреваю, всяко меньше, чем атомов во Вселенной.

Впрочем, дались нам эти атомы...

Present, без запрета на повтор позиции (не ко, а через несколько постановок), количество вариантов бесконечно.

Если же запрет есть, то считать надо исходя из процесса игры, т.е. сколько вариантов поставить камень первым ходом, умножается на количество вариантов оставить второй камень и т.д. Самый примитивный подсчёт даёт 361!, но это без учёта возможности брать в плен и запрещённых позиций. От приведённого в статье количества возможных расстановок оттолкнуться при подсчёте вариантов вообще не получится, потому что невозможно определить точно все позиции, из которой может получится текущая.

Думаю, можно воспользоваться эвристикой золотого сечения и считать факториал от 225, а это более чем четырёхсотзначное число :)

Чем то все эти подсчёты напоминают рассуждения о количестве ангелов на кончике иглы (сначала опечатался - игры :))

--
Веруй, что есть в природе и кроме этого языки

Present Написал:
-------------------------------------------------------
> И все же число"вариантов" и число "различных
> расстановок" это разные числа

Варианты можно определить по разному. Можно вариантами называть все, что может возникнуть в партии, а можно все, что может возникнуть в партии хорошоиграющих игроков...

Aragorn Написал:
-------------------------------------------------------
> Это сопоставимо с числом атомов во Вселенной.
>
> В Галактике. Японцы говорят - в трёх. Но с моей
> точки зрения, одной достаточно )

Ну зачем же ограничиваться Галактикой, если можно сравнивать со всей Вселенной. Хотя, впрочем, сравнение в любом случае не в пользу атомов...

WinPooh Написал:
-------------------------------------------------------
> Чем то все эти подсчёты напоминают рассуждения о
> количестве ангелов на кончике иглы (сначала
> опечатался - игры :))

Сам процесс весьма интересен.

По поводу статьи. Честно говоря я не понял откуда взялось 2^8 одинаковых позиций из-за отражений вдоль осей симметрии. Любая подобная позиция может быть получена за одно вращение (4 варианта) и отражение 2 варианта. То бишь всего 8 вариантов, а не 256. Самый простой способ проверьте возможные расположения камня 4-3. Несложно увидеть что их всего 8, по два в каждом квадранте.

Второе по поводу вероятности невозможных позиций

Два замечания
1) Наличие двух невозможных позиций не делает позицию возможной. Позиции из трех камней в углу могут существовать независимо поэтому не надо считать ряд, а просто возвести в 4 степень.
2 ) такая позиция возможна для двух цветов.

Поэтому всего для случая из трех камней в углу полная вероятность не получения запрещенной по этому типу (25/27)^4 ~ 0.73

Для четырех камней на стороне. Всего таких позиций на стороне возможно 17 строн 4. + 2 цвета

Не все из них могут быть реализованы совместно с угловой позицией и между собой но подавляющее большинство может ( это достаточно слабо влияет на результат) Для простоты пренебрежем этим тогда
вероятность получения не запрещенной позиции
примерно (79/81)^68 = 0.18

Для понуки таже оценка даст примерно 0.091

Так что несколько порядков там набертся.

Цитата:

если все черные камни поменять на белые, позиция не изменится

Denis Silvers, а как же неодновременность ходов и выступка черных?
Что тогда считать позицией?
Если результат партии взять с противоположным знаком - позиция тоже не изменится?

Цитата:

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

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

За ответственную власть!
СВОИМИ ИМЕНАМИ
Гобелены гобана

Хм...
Принято считать, что для первой постановки существует 361 вариант, хотя если потыкать пальцем и учесть симметрию, то их всего 55.
А для второй? Кто-нибудь из математиков, профессионалов и любителей тыкал ли пальцем? Или всем известно, хвала Аристотелю, что у мухи 8 ног?
Лихо считают, что для второй постановки остается 360 свободных перекрестков, а всего на два "хода" возникает 361х360 комбинаций -вариантов.
Между тем, число возможных постановок 2-го камня - зависти от того, где стоит первый, и в одном из 55 возможных случаев составляет 54 (Тэнген - Стожар), в 18-ти из 55 возможных - по 189 на каждый (оси симметрии), и в остальных 36-ти: по 360 "на брата".
Проверить не трудно, нужно просто "отрывать ноги" :)

Кстати, не стоит забывать, что со 2й постановки существует "пас".
Кроме того, трезвые правила Го / :) / не ограничивают количества черных или белых пасов подряд, а значит 360 черных камней на гобане убиваются одним белым, освобождая пространство... :)

- - - - - - - - - - - - - - - - - - - - - - - - -
- Не обижайся: способность понять зависит от личного опыта, а не от умственных усилий… (Сэр Джуффин Халли)
Гостинная Шк. "Стожар": [100jar.blogspot.com]
Библиотека Шк. "Стожар": [librarystozhar.blogspot.com]

Интересно, как получено число в теме разбора. Случайный набор, или всё-таки по какой-то формуле посчитано

Volody Написал:
-------------------------------------------------------
> По поводу статьи. Честно говоря я не понял откуда
> взялось 2^8 одинаковых позиций из-за отражений
> вдоль осей симметрии. Любая подобная позиция
> может быть получена за одно вращение (4 варианта)
> и отражение 2 варианта. То бишь всего 8
> вариантов, а не 256. Самый простой способ
> проверьте возможные расположения камня 4-3.
> Несложно увидеть что их всего 8, по два в каждом
> квадранте.

Да, вы правы, вечером исправлю.

Volody Написал:
-------------------------------------------------------
> Второе по поводу вероятности невозможных позиций
>
> Два замечания
> 1) Наличие двух невозможных позиций не делает
> позицию возможной. Позиции из трех камней в углу
> могут существовать независимо поэтому не надо
> считать ряд, а просто возвести в 4 степень.
> 2 ) такая позиция возможна для двух цветов.
>
> Поэтому всего для случая из трех камней в углу
> полная вероятность не получения запрещенной по
> этому типу (25/27)^4 ~ 0.73
>
> Для четырех камней на стороне. Всего таких позиций
> на стороне возможно 17 строн 4. + 2 цвета
>
> Не все из них могут быть реализованы совместно с
> угловой позицией и между собой но подавляющее
> большинство может ( это достаточно слабо влияет на
> результат) Для простоты пренебрежем этим тогда
> вероятность получения не запрещенной позиции
> примерно (79/81)^68 = 0.18
>
> Для понуки таже оценка даст примерно 0.091
>
> Так что несколько порядков там набертся.


То есть у вас получилось, что с 27% запрещенная позиция в углу будет, с 82% запрещенная позиция на стороне будет и с 91% запрещенное поннуки будет. Всего 208%. То есть при рассмотрении простейших форму у вас получилось, 208%, то есть как бы мы не расставили камни на доске, запрещенная позиция все равно будет?

Ви Ми Написал:
-------------------------------------------------------
> если все черные камни поменять на белые, позиция
> не изменится
> Denis Silvers, а как же неодновременность ходов и
> выступка черных?
> Что тогда считать позицией?
> Если результат партии взять с противоположным
> знаком - позиция тоже не изменится?
>

Позиция -- это высыпали на доску произвольное число камней. Что получилось то и позиция. Вариантов партий, как уже писали 361!.