Вот это число: 1,4379232588848906548323625114999e+768



Эксперимент продолжается...

Алексей, какое "это число"? Мы тут несколько разных чисел упоминали. Наверное (361!)? Или кратное его?

Пару дней не заходил на ветку про идеального игрока (недооценил название!) и только сегодня обнаружил, сколько там затронули проблем. Сел вот писать, но даже не знаю с какого конца подступиться - это же родная тема! Дело в том, что в 74-75 годах я принимал участие в создании аналогичного, но только шахматного бога. История интересная (по типу "дела давно минувших дней"), но если покажется длинной, то оправданием будет полная параллель с идеологией создания и использования в реальной игре Гобога. Только я заранее прошу прощения за свойственный мне менторский тон (есть такая слабость), но учитывая тему, а в ней я уже 30 лет, без этого мне придется просто замолчать.
Интересно, что само слово Гобог представляет собой палиндром, т.е. читается с двух сторон, что соответствует принципу симметрии в Го :-)
Начну по хронологии постингов.

melox писал(а):

> Что касается Го-Бога, то есть два понимания этого термина -
> одно из математики, другое уж не знаю откуда, но его
> продемонстрировал orange.
> Так вот, первое исходит из аксиомы теории игр о том, что в
> играх с полной информацией существует некая, недоступная
> игрокам (реальным) АОС - Абсолютно Оптимальная Стратегия.

Доказательство того, что исход игры в любой позиции (это относится и к Го) предопределен было дано в 1913 году итальянским математиком Цермело. Поэтому правильнее будет называть это теоремой. Ее доказательство настолько просто, что доступно пятикласснику. Чтобы не отвлекаться, я не буду его здесь приводить, но готов это сделать по любой единичной заявке – это займет пару абзацев.

Насчет понимания термина Гобог – с этим еще легче и даже не понадобится никаких оптимальных стратегий. Если представить себе полное дерево игры, содержащее все мыслимые партии, то согласно теореме Цермело, на каждый его узел, т.е. позицию, можно повесить бирку с числом, которое будет означать что именно с таким результатом закончится партия, если ее доиграет Бог за обе стороны из этой позиции. При этом диапазон чисел, которые будут встречаться на бирках будет от [+вся доска] до [-вся доска]. Если говорить про аналогичное дерево игры в шахматах, то там на бирках будут появляться всего 3 значения: 0, 1/2, 1.

Возвращаясь к Го, возьмем, к примеру, начальную позицию, чтобы заодно разобраться с понятием коми (которого пока нет). Если Бог разыграет ее до конца, то окажется, что черные выиграют за счет выступки, к примеру 7 очков (это наиболее правдоподобно по нынешним понятиям). Тем самым мы определили размер той компенсации, которую должны получать белые для уравнения шансов. Это – т.н. идеальное коми. Если теперь играть с учетом этого коми, то идеальная партия, естественно, закончится вничью.
На практике мы, не зная идеального коми, вводим т.н. статистическое коми и делаем его дробным, чтобы избежать ничейного результата. В этом есть некий вопрос, и не исключено, что в будущем, когда профи станут еще более внятно ощущать полуочковые колебания, а стрелка статистики укажет на целое, то можно пойти и на это, допуская редкие ничьи, хотя это усложнит матчевую практику (рискую получить за это отступление критику по полной программе :-)).

Будем для удобства, во всех дальнейших построениях считать коми идеальным, равным 7 и что оно входит в подсчет результата партии. Будем также оценивать результат партии в единой шкале, с точки зрения черных (+ в их пользу).
Возьмем для иллюстрации пример, когда черные своим третьим ходом решают, сыграть ли им высокий "китай" или низкий (как стоят белые, пока не важно, где-то в левых углах). Если эту проблему решает игрок, которому разрешено использовать подсказки Гобога, то ситуация может выглядеть так. Сделал условный ход в q9 (высоко), получил ответ +2, сделал ход в r9, получил +1. Значит, высокий "китай" в этой позиции сыграть выгодней, и гарантированный выигрыш составит 2 очка.

Но это еще не все, незашоренный игрок может обратить взгляд на всю доску и обнаружить, что бирки с числами наклеены на все свободные пункты доски – это сделал Гобог (и так же он будет поступать дальше, после совершения каждого хода.) В угловой точке доски, например, будет стоять отрицательное число, поскольку ход туда, практически – пас.
Так вот, взглянув чуть шире, игрок может увидеть, что есть ход (ходы) в другом месте доски, которые гарантируют выигрыш более 2-х очков, (т.е. нечего "китай" городить) и пусть максимальным из них будет 4. Тогда первый шаг в процессе построения идеальной партии (с этого места) будет состоять в выборе хода в одну из точек на доске с наклейкой +4.
После этого ход переходит к белым, а Гобог установит новые наклейки в каждом свободном пункте доски. Как будет выглядеть новая картина? Оказывается, что все числа на бирках будут больше или равны 4. Это, в частности, означает тривиальный, но мало осознаваемый факт, что никаким своим ходом нельзя выиграть проигранную позицию, для этого нужна "помощь" противника.

Продолжим строить идеальную партию. Как теперь играть белым дальше? Ответ – им обязательно нужно поставить камень в одну из точек с наклейкой 4, ведь любой другой ход сделает конечный результат только хуже. Будем считать, что они это сделали, снова меняем наклейки, и теперь картина становится исключительно пестрой. Будут встречаться числа разных знаков, причем диапазон отрицательных значений будет гораздо шире. Конкретнее: положительными будут только 1,2,3,4 (нельзя прыгнуть выше головы), а вот цена ошибки может быть сколь угодно большой (на всю доску). Вопрос – почему это выглядит несимметрично для белых и черных? Дело тут не в цвете, а в том, где расположена точка отсчета, т.е. истинная оценка позиции, в данном случае 4.

Продолжая партию, черным следует опять выбрать ход с оценкой 4 и т.д., дальше процесс будет повторяться. Однако, если бы белыми играл реальный человек, а не Бог, то он бы периодически ошибался (ему не видно, на каком поле стоит 4), а выигрыш черных, в результате этого, монотонно бы возрастал в виде ступенчатой функции.
Если же человек станет играть за черных, т.е. за активную в данном случае сторону, то совершая ошибку (не видя, опять же, 4), он будет каждый раз уменьшать размер выигрыша, а перейдя через ноль, и вовсе проиграет партию.

Самое интересное, что все, что я так долго описывал, происходило реально с гроссмейстером Авербахом, когда он в качестве экзаменатора, играл в 1976 году против шахматного Бога в ВЦ Института проблем управления. Эти свои ощущения беспомощности ученика перед Богом он красочно описал в журнале "Знание - сила" (1976, №8), вырезки из которого хранятся у меня в папке. Осталось уточнить, что Бог был несколько специализирован, а именно – в области ладейного эндшпиля, что нисколько не меняет сути дела, а его экзаменатор – автор 3-х томной монографии по эндшпилю.

Возвращаясь к Го, можно сказать, что прав был Оранж, говоря, что не нужны Гобогу ни дзёсэки, ни фусэки, ни всякие там стратегии, хотя вывод, что на основании именно этого "разница между людьми и го богом должна быть колоссальной" я бы не поддержал.
Постинг получился длинным, поэтому насчет форы, объема данных для божьей памяти (по опыту шахмат) и проч. будет в продолжении, если интересно.



Отправка отредактированного (17/01/05 03:28)

{Го – это роскошь, которую могут позволить себе немногие}

Спасибо, Саша!
Очень интересно. Продолжи, пожалуйста!
Только, пожалуйста, если письма будут такими же длинными, то не части :-)



Виктор aka "Председатель ревизионной комиссии РФГ"

> Будем для удобства, во всех дальнейших построениях считать коми идеальным, равным 7 и что оно входит в подсчет результата партии. Будем также оценивать результат партии в единой шкале, с точки зрения черных (+ в их пользу).
Возьмем для иллюстрации пример, когда черные своим третьим ходом решают, сыграть ли им высокий "китай" или низкий (как стоят белые, пока не важно, где-то в левых углах). Если эту проблему решает игрок, которому разрешено использовать подсказки Гобога, то ситуация может выглядеть так. Сделал условный ход в q9 (высоко), получил ответ +2, сделал ход в r9, получил +1. Значит, высокий "китай" в этой позиции сыграть выгодней, и гарантированный выигрыш составит 2 очка.

То есть первые 2 полухода были без подсказок Гобога , иначе максимальная ценность 3-го хода была бы =0

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

Александр , Вы остановились на самом интересном месте . Какова по-Вашему уравнивающая фора для игры Гобога против современного профи 9д ?

В Хикару Но Го , Сай выиграл у Койо пол-очка . Но Сай - далеко не Гобог , и по его собственным заявлениям , и потому что несколько раз менял оценку хода Хикару .



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

Окружор писал(а):

> То есть первые 2 полухода были без подсказок Гобога , иначе
> максимальная ценность 3-го хода была бы =0
>
Конечно, так. Ситуация, когда подключился Гобог, возникла в момент раздумий черного игрока над 3-им ходом.
Я упомянул вскользь, что белые сыграли где-то, как-то... Полной строгости достичь трудно, но к этому надо стремиться :-)

> > Возвращаясь к Го, можно сказать, что прав был Оранж, говоря,
> что не нужны Гобогу ни дзёсэки, ни фусэки, ни всякие там
> стратегии, хотя вывод, что на основании этого "разница между
> людьми и го богом должна быть колоссальной" я бы не поддержал.
>
> Александр , Вы остановились на самом интересном месте . Какова
> по-Вашему уравнивающая фора для игры Гобога против современного
> профи 9д ?

Илья, вопрос несколько странный, хотя может показаться лестным :-)
Я всего лишь написал про Гобога, но сам очень далек от него...

P.S. Понял. Уточняю акценты.
... хотя вывод, что на основании именно этого....



Отправка отредактированного (17/01/05 00:09)

{Го – это роскошь, которую могут позволить себе немногие}

... насчет числа позиций - на каждом поле может стоять только черный камень, белый камень, или пустое поле = 3, всего количество полей - 361...
Я в чем-то не прав?



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

> ... насчет числа позиций

Мне нравится . Только вот число запрещенных позиций надо бы оценить . Когда камней мало - запрещенных позиций пренебрежимо мало , когда камней много - большинство позиций запрещены . Впрочем , оценка вроде 3 ** 240 может быть достаточно хороша . Все зависит от точности сравниваемых чисел , вроде мифического количества атомов во вселенной .



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

Число позиций равно факториалу от числа полей, насколько я понимаю...
Именно это число я и привёл.

Александр, очень интересно! А можно всё-таки потратить время на доказательство теоремы Цермело? Очень любопытно...



Эксперимент продолжается...

> ... насчет числа позиций

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



{Го – это роскошь, которую могут позволить себе немногие}

> Число позиций равно факториалу от числа полей

Почему ? Если , например , переставить камни 1-го и 3-го полуходов , получится та же позиция .

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

P.S: Теорему Цермело я бы доказал по индукции от последнего хода к первому



Отправка отредактированного (17/01/05 02:55)

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

Окружор писал(а):


> То есть первые 2 полухода были без подсказок Гобога , иначе
> максимальная ценность 3-го хода была бы =0
>
Илья, перечитывая текст, нашел ответ:
Тогда первый шаг в процессе построения идеальной партии (с этого места) будет состоять ...



{Го – это роскошь, которую могут позволить себе немногие}

melox писал(а):

> Александр, очень интересно! А можно всё-таки потратить время на
> доказательство теоремы Цермело? Очень любопытно...
>

Окружор ему(ей) ответил(а):

> P.S: Теорему Цермело я бы доказал по индукции от последнего
> хода к первому

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



{Го – это роскошь, которую могут позволить себе немногие}

И получилось описание минимакса , только без оптимизирующего альфа-бета отсечения



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

Александр, очень интересно!
А г-ну Сахабутдинову надо бы в школу...
Партия в го - это не просто расстановка камней (три варианта для пункта), а еще и порядок, В КАКОМ ИХ расставляли. Вот откуда факториалы (слышали про выборки с возвращениями и сочетания из "эн" по "ка"?). Ко, симметрии, учет неоднозначностей пути и т.п. - мелочь по сравнению с величием числел типа 10 в 750-той степени...

Зет , здесь все слышали про все . От факториалов через суммирование комбинаторных функций - длинный ряд к числу партий , а величие чисел 10 ** 750 и 10 ** 75 практически неразличимо . Поэтому Рустам Мизхатович очень прав , что взялся за более реальную задачу - число позиций . Там осталось только оценить число запрещенных позиций , а для вычисления числа партий нужно кроме этого начать и закончить вычисление основного приближения .



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

Нет, нет Илья. Zet прав. Сравните числа 3**N и N! - это совершенно разного уровня роста функции. Наример, 3**N - число путей при троичном поиске (вспомните задачу про число зерен на шахматной доске - там 2**N), а N! - число перестановок в N-ке. Это формулой Стирлинга и показывается. И числа 10**75 и 10**750 не пренебрежимо различаются, второе - десятая (!) степень первого.

Сергей , я знаю , какое число больше и насколько , я говоорю об их "величии" . Какой вообще смысл сравнивать число партий и число атомов ? Чтобы была впечатляющая и не слишком ложная реклама . В таком вот разрезе .

Кроме того , главный вопрос - что считать , партии или позиции . Позиции лучше - технологичнее при той же "величественности" результатов .



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

>>>А г-ну Сахабутдинову надо бы в школу...

Да и вам господин Zet следовало бы. Посетить урок вежливости, который вы когда то проболели. Ведь можно было обойтись без этого замечания. Приятно конечно что вы что то знаете, что Сахабутдинов упустил, но зачем же подкалывать ?

Для сравнения: число партий в шахматах и в го - величие этих чисел "неразличимо"? А ведь там, как я помню, меньшая разница "в величии".