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



Отсутствие закона не освобождает от ответственности (c) народное
Новые турнирные схемы

Есть еще одна похожая задачка: подсчет числа магических квадратов, т.е. тех, где суммы по горизонтали, вертикали и двум диагоналям совпадают. А числа в клетках - последовательные натуральные от 1 до NхN. В данном случае 19х19. Общее число возможных размещений чисел того же порядка, что и число партий в го. А магических квадратов (МК) значительно меньше.

Для 3х3 - с точностью до симметрий только 1 МК.
Для 4х4 - 880, а 16! ~ 2e+12.

Интересное замечание про предел рейтинга и шкалу про-данов. Профи отказались от шкалы 1 дан/1 камень форы, а использовали (в турнире Оотэаи) вероятностные нормы повышения ранга 1 р/75% побед (для верхних про-данов). Это означает, что если продолжать в этой нелиненой шкале увеличивать даны, то предел становится (по про-данам) неограничен. В самом деле, 9р выигрывает у своих одного с ним уровня соседей 75% партий, если его превышение рейтинга в линейной шкале пунктов примерно 25 пунктов (грубо: d/100 = (2925-2900)/100 = 0.25 добавить к 0.5 - это и есть 75%). Если наберется некоторое количество игроков нового уровня - 10 про-дан, то выигрывающий 75% партий (11 про-дан) приблизится к ИИ еще на 0.25х75 = 19 пунктов, и так будет продолжаться бесконечно - прибавки будут все меньше при сохранении процента побед. Предел поправок равен нулю, а сумма стремится к рейтингу ИИ = 3000.

Поэтому можно было бы поставить вопрос и так: на сколько про-данов ИИ превосходит лучших профи? Ответ: на неограниченное число, если иметь ввиду нелинейную шкалу, основанную на проценте побед - 75%.

Это объясняет практическую невозможность приблизиться к ИИ по рейтингу реальным игрокам.

Красиво . Даешь 20-й дан !

И катарсис перестает быть мрачным . Получается , что суперпрофи будут с первого хода бороться за единственное очко . Практически их Го перестанет быть игрой с выигрышем по очкам , а станет игрой с 2 исходами (или с 3 , если коми станет целым) . Нормалек ! Спасибо , Сергей !



Отсутствие закона не освобождает от ответственности (c) народное
Новые турнирные схемы

Да, именно так. Приблизится "ничейная смерть Го" (надеюсь, что реально никода до этого не дойдет), в то время как эта проблема в шахматах уже актуальна.

А если принять, что в шкале про-данов только целое смещение рейтинга (с округлением в меньшую сторону к ближайшему целому числу), то каков предельный рейтинг и максимальный дан?

Сегодня случайно наткнулся:

It is commonly said that no game has ever been played twice. This may be true: On a 19×19 board, there are about 3^361×0.012 = 2.1×10^170 possible positions, most of which are the end result of about (120!)2 = 4.5×10^397 different (no-capture) games, for a total of about 9.3×10567 games. Allowing captures gives as many as 10^{7.49 * 10^{48}}

possible games (http://senseis.xmp.net/?NumberOfPossibleOutcomesOfAGame), most of which last for over 1.6×10^49 moves! (For two comparisons: the number of legal positions in chess is estimated to be between 10^43 and 10^50; and physicists estimate that there are not more than 10^90 protons in the entire visible universe.)

Содрано с [en.wikipedia.org])

Немного верну эту тему в русло ее исходной темы, противостояния человека против ИИ.
Вспоминается, как Каспаров описывал свои ощущения во время розыгрыша одно из окончаний против компа. С точки зрения людей, эндпшиль был ничейний, однако комп узрел выигрыш ходов примерно через 60.
Во время розыгрыша этого эндшпиля Каспаров просто не понимал, что происходит на доске, не улавливал изменений позиции, и, уж, тем более не видел разумного пути развития ситуации на доске. Первые подозрения, о том, что опасность где-то затаилась, возникла, когда до мата, с точки зрения компа, было рукой подать - ходов 20.
Если примерно такое существо будет играть в го, то не исключаю, что даже Ли Седол проиграет ему и на большей, чем 4 камня, форе.
В одной из методичек, написанных для ЦТ "Марьино" я написал, что расчет варианта и его оценка есть два взаимно противополжных направления в го, и принцип неопределенности применительно к го звучит так: Нельзя одновременно просчитать длинный вариант, и оценить его последствия.
Я слышал, что профи могут просчитать (увидеть камни) варианты на любую глубину. Кто-то писал о ста ходах. В анализе партий профи я вижу, что профи редко считают варианты более 12 ходов, а ошибки на 4 - 5 ходу это почти норма даже для очень сильных игроков.
(Однажды Ма Сяочун просчитал вариант против Коити Кобаяси примерно на 18 ходов, это выглядело как вгляд в бездну... Для Алекса.
Этот ход, по номеру примерно 119, в районе L9, Ма (черными) пытался разрезать практически бамбу в центре, но стандартная защита за белых не проходила из-за длинного квазисичо слева снизу к разрезающему камню. Там даже профи не поняли ни задумки Ма, ни ответа Кобаяси, выясняли после партии...)
Мне думается, что против ИИ все ходы даже профи будут ошибочными...



Значение коми должно быть пересмотрено!

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

Поэтому говорить о 4-х или еще каком-то количестве камней - субъективная и не обоснованная ничем оценка. Единственный критерий в таких случаях - косвенные оценки через дисперсию. Но об этом я уже писал. Аналогия из чистой математики - теория рядов, последовательности Коши и т.п. - там не всегда можно легко найти предел, но есть косвенные критерии определения сходимости. В частности, критерий Коши. В го вообще очень близкая аналогия со знакопеременными рядами. А тогда сумма (для монотонного по модулю ряда) сравнима с первым членом, деленным пополам (коми).



Отправка отредактированного (19/01/05 08:39)

Это шахматы-то не ограничены по числу ходов? А как же правило 50-ти ходов (если за это время не было взятий, превращений и движений пешек - фиксируется ничья) и правило троекратного повторения позиции (тоже ничья)?

Кажется, в книжках Гика была приведена оценка сверху максимальной длины шахматной партии. Точно не помню, но по порядку величины это было 5...10 тысяч ходов.

Ну, даже воспроизвести можно быстро: 50 * 14 съеденных фигур + 50 * 16 пешек * 6 ходов до превращения каждой + 50 * 16 съедений превращённых фигур. Получается 6300 ходов. Порядок вспомнил, кажется, верно.



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

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

Кстати тот же IgoWin например двойное ко не распознает, так что иногда приходится сдаваться в выигранной партии, а то он ведь гад пасовать не хочет :)

p.s. Наверняка сейчас меня начнут уличать в незнании правил как го так и шахмат

Правило 50-ти ходов или аналогичные вещи и возникли из-за конечности времени на игшру, а не из-за конечности правил самой игры. С ко и вечной жизнью - другое дело. Это не до конца доведенная формализация правил.

В любом случае ценность хода в го к концу партии падает, становясь в пределе равной 0 за конечное и достаточно привычное для нас число ходов. А в шахматах таких пределов нет, формально - только из правил игры, а не правил соревнований. И сейчас анйдено множество эндшпилей, где выигрыш доказан, но противоречит правилу 50-ти ходов. Это уже актуальная проблема.

Дамиру .

Здравомыслящее понимание "вечной жизни" и вообще проблемы повтора позиции заключается в суперко . Насчет искусственности - сравните формулировку суперко (нельзя повторять бывшую когда-либо ранее позицию) и японского ко (нельзя брать одиночный камень противника в ответ на его взятие вашего одиночного камня ; можно повторять более длинный цикл , но при этом партия закончится "без результата" ; нельзя использовать ко-угрозы при послеигровом доказательстве статуса группы ; и т.д.) . Которая из них более искусственная ? Японская традиция замалчивать сложность правил не снижает их сложность и искуственность .

Источник "полубесконечности" партий в Го другой - можно сдать группу в 360 камней , затем снова 360 (с другой последней точкой , чтобы обойти суперко) и т.д. 361 раз , затем группу в 359 камней и т.д. . Так можно развлекаться существенно дольше , чем в шахматах .

Но практическая проблема - длительность партии , когда только один из игроков старается растянуть ее , например в цейтноте при абсолютном контроле времени . Здесь шахматы хуже : все оценки ВинниПуха верны при одностороннем затягивании игры . А в Го максимум , чего можно добиться в этом неблагородном деле - сдать все живые и мертвые группы и вынудить противника построить "китайскую сетку" , в которую нельзя вбросить ни одного чужого камня .



Отсутствие закона не освобождает от ответственности (c) народное
Новые турнирные схемы

Можно и заставить сдаться - так делают на серверах (в смысле сдаются), когда соперник откровенно "валяет дурака", отнимая время на бессмысленную партию.