Число вариантов в Го

Хотелось бы узнать, чему же всё-таки равен (360!). Месяца 2 назад этот вопрос обсуждался на главном форуме. К примеру, Melox указал следующее число 1,4379232588848906548323625114999e+768. Но можно ли это как-то проверить. Exel пока считать отказывается. Может быть есть в инете какие-то проги, позволяющие считать такие большие цифры? Подскажите плз!



Помощник Президента Федерации Го

Новости Го: [news.weiqi.ru]
ClasGo: [tuan.weiqi.ru]

Вариант 1. При вычислении в лоб (в т.ч. в том же Excel) по мере превышения текущим значением например величины 1е10 делить его на эту величину и учитывать "срезанную" степень 10 где-то в стороне.

Вариант 2. В формуле Стирлинга (см. например здесь - [ru.wikipedia.org]) в критичном для лобового вычисления месте - (N/e)^N - вместо N=360 подставить N=3.6, а потом уже в уме домножить на 1е720. Точность полной формулы для N=360 - не менее 10 знаков после запятой, но для оценки вполне сойдет и упрощенная.

точный ответ получен при помощи калькулятора WINDOWS : 1,4379232588848906548323625114999e+768



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi

Спасибо. тоже только что зашел в виндовый калькулятор и сам нашел



Отправка отредактированного (05/04/05 12:20)

Помощник Президента Федерации Го

Новости Го: [news.weiqi.ru]
ClasGo: [tuan.weiqi.ru]

А у нас именно 361! или 360! ?



Помощник Президента Федерации Го

Новости Го: [news.weiqi.ru]
ClasGo: [tuan.weiqi.ru]

факториал 361:
14379232588848906548323625114998633547549075386447558761272827652992\
27795534389618856841908003141196071413794434890585968383968233304321\
60771380883705655787966919248618270978003589902110057945010733305079\
26277717227504122680867752813688505752654181204350215062346630264344\
26736326270927646433025577722695595343233942204301825548143785112222\
18683448796987126719420560953330641393571063519720072147337873382698\
03085351043174203653673779887217565513450041291061650506154496265581\
10282424142840662705458556231015637528928999248573883166476871652120\
01536218913733713768261861456295440900774337589490771443991729993713\
36807284590000344964203370664408533370012842864126543944950507739545\
60000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000

факториал 360:
39831669221188106782059903365647184342241206056641437011836087681419\
05250787782877719783678679061484962365081537093035923501297045164325\
78314074470098769495753238915840085811644293357645589875375992534845\
60326086502781503271101808348167605963030972865236052804284294361064\
45252981359910377930818774855112452474332249873412259136132368731917\
41505398329604229139669143915043327960030646869030670768248956738775\
70873548596050425633445373648802120535872690556957480626466748658119\
39840510090971364835065252717494840800357338638708817635670004576509\
73784539927240204344215682704419503880261322962578314249284570619704\
62070040415513420953471940898638596592833359734422559404295035289600\
00000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000

только сдается мне вариантов больше. ибо камни снятые с доски добавляют еще некоторое пространство для хода. другое дело что в эту зону (откуда сняли камни) далеко не всегда играют.



Отправка отредактированного (05/04/05 13:05)

Учитывая симметрию вариантов на самом деле меньше.

конечно
возможность ко-борьбы увеличивает кол-во вариантов неимоверно :)

Да... круто....



Помощник Президента Федерации Го

Новости Го: [news.weiqi.ru]
ClasGo: [tuan.weiqi.ru]

То что ВЫ написали - 361! - ЭТО РАЗМЕЩЕНИЕ ЭЛЕМЕНТОВ БЕЗ ПОВТОРЕНИЙ,
Вы же хотите узнать число вариантов игровых ситуаций возможных на доске.

Применяем след. формулу Сочетания- С (k,n) = n!/k!(n-k)! где n -общее число элементов множества = 361, к - число элементов = 2,
тогда получим число , после подстановок =1,9521719561800908201366362304225e+254,
но учитывая, что игровая доска симметрична относительно четырех осей - вертикаль , горизонталь, две диоганали , итого 4,
дополняем данную формулу, разделив результат на число возможных сочетаний по этим осям координат ( 4! = 24), и тогда окончательный результат получается = 8,1340498174170450839026509600917e+252



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi

Спасибо, Олег, очень интересно. Я сам бы в этом не смог разобраться, всё-таки не математическое образование...



Помощник Президента Федерации Го

Новости Го: [news.weiqi.ru]
ClasGo: [tuan.weiqi.ru]

Давайте определимся, что считать "вариантом". Можно дать оценку сверху по количеству позиций (всех, включая симметричные) - 3^361 = 17408965065903192790718823807056436794660272495026354119482811870680105167618464984116279288988714938612096988816320780613754987181355093129514803369660572893075468180597603 ~= 1.74*10^172 (что существенно меньше, чем оценка Олега). Из этих позиций какое-то количество будет противоречить правилам го (будут группы без дамэ).

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

Оценки сверху - это хорошо, но было бы здорово получить хорошую оценку снизу для количества разрешенных позиций.

Но все эти "экстремальные" оценки на практике малоприменимы, потому что даже игрок 20кю может отбросить огромное количество вариантов, в которых одни из игроков получает явное преимущество. Если же определить на каждом ходу 10 возможных вариантов продолжения, то получится 10^200 (или что-то около того) вариантов партий. Одноко, даже это число, если мне не изменяет память, превышает количество элементарных частиц в видимой части вселенной.

А при чём здесь симметрия? Ведь это же разные фусэки - ходить вправо или влево и т.д.



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

Да, Дима, я с тобой согласен, но применять к игре правила.................
А КАКИЕ?.................

Если пойти ещё строже - то получиться , что в любых ситуациях нельзя повторять позиции, которые были когда-то сделаны, тогда и эта цифра, которую , ты привёл, уменьшаеться на 0,4%.

Давай попробуем вывести окончательную формулу подсчёта,
если ты огласен.



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi

Я согласен ^_^

Ви Ми ! Объясни мне, не разумному, как это может быть разная форма?
Если суть позиции не меняется. И играется ПОЛНОСТЬЮ ЗЕРКАЛЬНОЕ ОТРАЖЕНИЕ !



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi

kit144 !
Давай разбираться в предмете без ярлыков «разумности» - «неразумности» :)
Я ещё не нашёл истину, так что результат поиска мне неведом, но желанен.
Это не софизм, а любознательность.

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

1) Я ещё могу понять непризнание за отдельный вариант ПОВОРОТА доски на 90, 180 и 270 градусов.

Действительно, вот в шахматах продольная и поперечная асимметрия обеспечены необратимостью движения пешек в разных направлениях и асимметричностью «августейшей четы». Так что, верти – не верти шахматную доску: белый король всегда начинает с е1, а чёрный – с е8 , и это словно два магнитных полюса партии, привлекающих «магнитные стрелки» цареубийственных ударов противника.

А раз в го нет направления движения («динамическая невесомость»), кроме направления на тэнгэн («статическое тяготение»: № линии как глубина «зарывания в недра» гобана), то в любой момент игры можно для удобства развернуть доску или самим покружиться вокруг гобана (?).
Но не всё здесь для меня бесспорно...

Представь, что играешь чёрными. Сколько у тебя вариантов первого хода на «19-й» доске?
Я считаю, что 361 (любая из 19 строк, любой из 19 столбцов). Если я правильно тебя понял, то у тебя таких вариантов 91 [ (361-1)/4 , исключив асимметричный тэнгэн ]. Деление на 4 здесь считаю «четвертованием» степеней свободы, и вот почему.
Здесь за бортом оказывается явление психологической асимметрии: ход в угол своей или чужой стороны (демонстрация разной степени агрессии), под правую или левую руку («хук слева»-«хук справа» :), особо про право-лево см. ниже.


2) А ещё труднее мне принять непризнание за отдельный вариант ЗЕРКАЛЬНОГО ОТРАЖЕНИЯ доски.
Ведь «право» и «лево» не одинаковы, известен эффект неодинаковости зрительного восприятия: поднеси «Сикстинскую мадонну» к зеркалу, и она потеряет равновесие, и дело тут не только в привычке, а в разном ощущении массы объектов слева и справа от взора.


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

Но если мы подсчитываем варианты, измеряя богатство ходов го и сложность его просчёта для компьютера, то почему мы сбрасываем со счетов необходимость перебора машиной и держания ею в своём уме дополнительных наборов «повёрнутых» и симметричных последовательностей ходов? Ведь это же дополнительное машинное время! И это ещё надо догадаться о сходстве, произведя сравнение...


Виталий Мищенко
[vimi.weiqi.ru]



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

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

По моим подсчетам, если плотно набить весь объем "видимой части Вселенной" протонами, то получится число порядка 10^80.

Тоесть получается, что если после этого каждый из протонов заменить суперкомпьтером, который держит в памяти 10^ 80 вариантов, то все еще будет только 10^ 160. Спекуляция, конечно, но забавная.

(Информацию о размерах "видимой части Вселенной" брал из справочника 15-летней давности)
Может я ошибаюсь?



"You see, dear Watson, but You don’t observe"

Тут все не так просто. Сейчас быстродействие определяется суммой элементарных процессоров, но если удатся построить квантовый компьютер, то сумма заменится произведением. И тогда вполне можно будет перебрать все варианты. Вряд ли это случится скоро, хотя кто знает, все меняется так быстро...

Ё моё, робята, попробуйте сыграть handtalk'ом на форе в три камня.
Если стандартное расположение камней во многих прогах - это правый верх, правый низ, левый низ
то в Handtalk- правй верх, левый верх, левый низ.
И убедитесь сами, что эта позиция соответствует, как зеркальной, так и осевой симметрии!!!



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi