Что касается Го-Бога, то есть два понимания этого термина - одно из математики, другое уж не знаю откуда, но его продемонстрировал orange.

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

Вторая трактовка (orange) мне, честно говоря, больше по душе. Здесь интересно то, что Ли Седоль высказал т.з. на проблему, совпадающую с т.з. теории игр и матстатистики, а вот Го Сейгэн, помнится, сформулировал это несколько по-другому, хотя и близко - он сказал: "Я всего лишь человек, если бы я играл с Го-Богом, то у него уже к 50 ходу было бы преимущество на доске".

А что касается прорывов, Илья, тебе такое предложение - изучи партии Ямаситы Кейго, там есть на что посмотреть по части нестандартной игры.

А ещё интересны партии Го Сейгэна и Досаку...



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

Вначале представлюсь - меня зовут Игорь, родом из Киева (Аркадий, привет!)

Когда-то я играл в го в районе 1 кю/1 дан, но в последнее время переключился с го на нарды... да, вот такая странная метаморфоза.

По поводу игры с Богом - действительно, есть вероятность, что тот метод игры, которым играют сейчас все профессионалы - не оптимален. Просто все привыкли играть таким образом. Типа, это локальный максимум, который за сотни лет отточен до 1-2 камней, но где-то рядом, возможно, есть глобальный максимум, которого никто пока на нашел. Не то, чтобы я был уверен, но просто в качестве гипотезы.

Тут приведу 2 примера из нард:

1) Я насколько раз играл с мастерами из наших южных республик. Они там - местные чемпионы, играют с детства. Поэтому идея о том, что я могу их обыграть, вызывала здоровый смех (перед игрой :)). Во время игры мои ходы часто вызывали реакцию - "так не играют!" То есть у них в стиле есть какие-то аксиомы, которые поколениями вошли в подкорку, и никто их даже не думает оспорить.

(Естественно, их мир нард был сильно ограничен географически. Но то же самое, теоретически, возможно и с го, но в мировых масштабах)

2) До 90-х годов, компьютеры играли в нарды гораздо слабее человека. А потом произошел прорыв - программы на основе самообучаемых нейронных сетей стали играть в силу чемпионов мира (или почти чемпионов - чемпионы все еще ведут в рейтинге где-то 50-100 очков по системе Эло). И тут оказалось, что 90% книг по нардам, написанных в 70-80х годах, можно выбрость на свалку. Компьютеры подсказали совершенно другие варианты, и привели к переосмыслению всей игры. Нарды-2000 и нарды-1980 - это две большие разницы.

***

Будет очень интересно посмотреть на сильные го программы, и насколько их стиль будет отличаться от "человеческого". Только долго ждать придется, боюсь :)

Игорь, переходите на ветку offtopic, вот сюда:
[forum.weiqi.ru]

поговорим про нарды. :))
Я из тех самых, которые с детства.



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

В моем понимании быть Го-Богом - это возможность просчитать все возможные варианты развития конкретной позиции до конца партии. Предположим, что это сделано, т.е. мы получили ключ к этой самой АОС. Что же мы тогда получим?

Ну во-первых станет окончательно очевидно, кто из игроков имеет преимущество. Вообще-то считается, что черный, и особых причин не верить этому нет, но с другой стороны ничего пока не доказано, а вдруг при *полном* анализе всех вариантов окажется, что при игре двух Го-богов у черного нет никаких шансов :)

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

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

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

И вообще, игра между двумя Гобогами будет неитересной. В зависимости от размера коми один из них сдастся на первом же ходу, так как они уже будут знать результат партии :)

А я первым делом спросил бы, какой камень сильнее. Хоси или Комоку?



Александр Динерштейн,
Go lessons [breakfast.go4go.net]
Разобранные партии [www.go4go.net]
Журнал "Гоама" [gogame.info]
Новости с серверов Го [GoSensations.com]

>А я первым делом спросил бы, какой камень сильнее. Хоси или Комоку?

А Го-Бог первый ход в тенген сразу :)

ОС и ИИ

О хамэтэ со стороны идеального игрока (будем обозначать его через ИИ - как-то не хочется употреблять "божественных" названий; также
обозначается обычно и "искусственный интеллект", что в общем близко по сути). Есть общая теорема теории антагонистических игр двух лиц с полной информацией, в соответствии с которой в го (вернее, в формализованной игре двух лиц, моделирующей реальное го) существует оптимальная стратегия (ОС; тут я не знаю, что имел ввиду Алексей под АОС? Оптимальная стратегия либо существует, либо нет, но причем здесь "абсолютность"?).

Надо определить, что такое ИИ. Будем понимать под ИИ алгоритм (может реализованный в виде программы даже), реализующий ОС в игре го (не важно, за какую из сторон и с какой начальной позицией; если ОС есть, то ее можно применять не обязательно с первого хода - игра однородна и нет оснований подозревать исключительность начальной позиции - пустой доски - в смысле существования ОС).

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

ПРЕДЕЛ РЕЙТИНГА

Теперь несколько слов о пределе по рейтингу - рейтинге ИИ и пр.

Да, правильно: внутри системы со свободным параметром - точкой отсчета и внутренним свойством линейности и однородности (обычные рейтиги типа ЭЛО), если нет специальных стабилизаторов, препятствующих дрейфу, невозможно определить, плывет система куда-то или нет. Так, в системе ЭЛО заложено правило сохранения суммы рейтинга в отдельных партиях. Это - внутренний стабилизатор системы ЭЛО и она не может куда-то существенно уплыть в принципе, хотя отдельные игроки могуть существенно менять свои границы колебаний рейтинга. В системе ЭЛО рейтинг может только "рождаться" при вводе новых игроков или "утекать" при выбывании. Внутри же системы происходит только перераспределение рейтинга, а на каждом интервале времени, где нет притоков-оттоков, суммарный рейтинг в системе сохраняется. Но не сохраняется суммарная сила игры - она растет (мы оптимисты). По крайней мере, изменяется.

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

Теперь вернемся к ИИ и задумаемся, что означает само существование ОС и ИИ?

Во многих сферах деятельности существуют физические ограничения, а для спорта - физиологические: никто не сможет прыгать выше 5 м без перерождения генетического или еще какого, бегать быстрее звука и т.д. То есть, существуют верхние пределы совершенствования практически во всех сферах, где можно установить количественные параметры, отвечающие за эту самую "степень совершенства", т.е. приближения к идеальному спортсмену, исполнителю и т.п. Что означает это в применении к го с его ИИ? Высшая степень совершенства - отсутствие ошибок в игре, которые приводят к потерям очков результата. Это и реализуется в ИИ. Поскольку действия любого человека "далеки от совершенства", он совершает ошибки (в отличие от ИИ), которые носят случайный характер и мы можем изучать свойства распределений таких случайных величин. Этим занимается прикладная математическая статистика (не только в го или других играх). По сути определения ошибки в игре - эта величина почти всегда больше нуля (будем считать именно потерянные очки), кроме случая ИИ, который не ошибается. Отсюда вывод: степень совершенства можно определять по среднему уровню ошибок, совершаемых тем или иным игроком. Свойства распределений ошибок можно изучать методами мат. статистики, на этом основаны в том числе почти все рейтинг-системы. Что такое проигрыш? Это тоже проявление свойств тех же самых распределений. Здесь естественно предположить, что распределения если и не точно соответствуют нормальному закону, но близки к нему, т.к. сладываются из множества факторов, каждый из которых не имеет доминирующего влияния на результаты. Да и в партиях результат складывается из множества ходов, при каждом из которых делаются сравнительно небольшие ошибки (не рассматриваем сейчас случаи грубых ошибок - они выпадают из рассмотрения в статистике). В турнирах реализуются схемы Бернулли, имеющие асимптотически тоже нормальные свойства. В общем, Гаусс всюду нас обложил... В этих условиях предел возможностей ассоциируется со снижением дисперсии неких нормальных распределений и это естественно. Для го - это ошибки в партии, и тот, у кого дисперсия ошибок меньше, имеет и более низкую среднюю величину ошибки при каждом ходе. Отсюда и возникает та самая верхняя граница, "предел совершенствования в силе игры в го", вопрос лишь в том, где назначить точку отсчета? Естественно, в рейтинге, соответствующем ИИ. Мы задали его в новом проекте РС равным 3000, что было обосновано существующими реально на сегодня соотношениями в статистических данных по результатам партий в Европе. Хотя в принципе это не так важно - можно задать любое число, но как оно будет связано с существующими классификациями? И какие могут быть гарантии, что РС не уплывет, или еще хуже - не перепрыгнет вдруг через этот потолок?

И здесь вступает в силу то, что дисперсия ошибок монотонно снижается с ростом уровня игры. Это проявляется статистически в том, что частоты побед более сильных игроков в партиях без форы при какой-то одной фиксировнной разнице в рейтинге (ранге) монотонно растут при приближении к отметке в 3000 пунктов (10 ама-дан или 13 про-дан). Обработка статистики ЕГФ вообще дала с очень высокой степенью достоверности формулу зависимости вероятности побед от рейтингов соперников в виде линейно-гиперболической функции (см. стр. Рейтинг в ГБ). Если предполагать существование предела, то он должен проявляться в этой зависисмости в виде асимптоты, для каждого значения разницы рейтингов одной и той же. Именно это и проявилось при обработке статистики ЕГФ! Все гиперболы имеют примерно (статистически) одну и ту же асимптоту (или прямые - при инверсии по зависимой переменной - одну и ту же точку пересечения с горизонтальной осью).

Это значение рейтинга было вычислено и оказалось равным 3000 - для сегодняшней статистики ЕГФ (может через 10 лет оно станет другим?). Но факт остается фактом. Если взять и зафиксировать точку отсчета 3000 пунктов, и далее применять формулу с линейно-гиперболической зависимостью вероятности от рейтингов (их разницы и среднего расстояния до 3000 - см. описание проекта РС в ГБ), то система не будет никуда ползти в принципе (почему?). Вот вам ответ про относительность, скорость поезда и планет, дрейф рейтинг-систем и прочее. И отсюда же следует невозможность скачков, о которых говорил Илья и пр., так как дисперсия может только снижаться с ростом уровня в целом всех игроков, лучшего понимания игры, развития теории и т.д. А зазор между сегодняшними профи и ИИ конечен и известен (примерно). Выше этого зазора скачков быть не может.



Отправка отредактированного (14/01/05 10:58)

> Энтропия растёт, но жизнь существует...

Жизнь - это способ противодействия энтропийной смерти Вселенной (с) я. А игро го - часть жизни.

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

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

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

Если же игрок отступит от ОС (читай человек совершит ошибку), то разрыв сократится. Чем больше ошибок совершит человек, тем ближе будет ИИ к победе. Но если сильный игрок не совершит достаточного количества ошибок, то он просто не даст ИИ отыграть гандикап и таким образом выиграет партию.

Это конечно же очевидные факты.

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

>Если же игрок отступит от ОС (читай человек совершит ошибку), то разрыв сократится. Чем больше ошибок совершит человек, тем ближе будет ИИ к победе. Но если сильный игрок не совершит достаточного количества ошибок, то он просто не даст ИИ отыграть гандикап и таким образом выиграет партию.

Это конечно же очевидные факты.

- А как быть с этим?
"Вселенная ограничена и бесконечна" А. Эйнштейн

> Но есть и теоретический результат . В пределе нулевой разброс результатов соответствует очевидно Гобогу , который никогда даже на пол-очка не ошибался , ну разве что пока еще не был Гобогом . И предел этот оказывается рядышком , всего-то 10д . То есть мрачный получился катарсис . Одна надежда на революционные прорывы ...
>.........................................

Замечу, что предел не так близко, как визуально это кажется, когда мы рассматриваем 100 пунктов рейтинга вблизи рейтинга ИИ. Дело в нелинейности шкалы совершенства, т.е. зависимости дисперсии ошибок от уровня или еще как сказать - не знаю. Другими словами, 100 пунктов рейтинга для нас с вами - пусть где-то в среднем 1 кю (никого не хочу обижать и себя тем более) - не совсем то же самое, что 100 пунктов для 9р. Даже совсем не то же самое. Хотя разница в набираемых очках в партии при 9р и при 1кю для этой разницы рейтингов одна и та же. Дисперсия разная. В результате вероятность победы более сильного в районе 9р при такой разнице равна 100%, а для 1 кю - только 60%.

Не зря профи свою шкалу данов ввели - жизнь заставила. Перейти для 9р (=9 ама-дан) на еще один уровень любительской шкалы, которая вчетверо примерно крупнее, оказалось не по силам (неудивительно - это же уже рейтинг ИИ должен быть). Вот и измельчили шкалу. Однако и сейчас переход на один уровень выше по шкале про-данов (около 25 пунктов рейтинга) соответствует примерно 75% побед над старыми соседями по ступени, что эквивалентно по процентам побед переходу с 6-го на 7-ой ама-дан примерно (т.е. на 100 пунктов рейтинга).

Поэтому рейтинг ИИ в 3000 пунктов = 13 продан. И это такой же большой отрыв от ведущих профи (даже больше, учитывая гиперболическую зависимость), как сейчас у нас 400 пунктов рейтинга в районе 5-6 данов.



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

.......тут я не знаю, что имел ввиду Алексей под АОС?.......

Это была штука - есть такое очистительное средство.

.......Жизнь - это способ противодействия энтропийной смерти Вселенной (с) я.......

Копирайт на формулировку или на идею? А то идея-то далеко не нова...



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

Дамиру:
Прочитайте еще раз то, что я написал по поводу ОС и ИИ в разделе о специальной ОС для игры против человека при дополнительной информации о его особенностях.

Это разные модели игры. Поэтому разные ОС. Пожалуйста, если вы сделаете такую ОС и заложите доп. инф. - как говорится, флаг в руки! Но не проще ли реализовать чистую ОС?

Алексей, копирайт, конечно же, на текст (но не на дизайн!)...
:))

Сергей Павлов писал(а):

> > Энтропия растёт, но жизнь существует...
>
> Жизнь - это способ противодействия энтропийной смерти Вселенной
> (с) я. А игро го - часть жизни.
>

Господь не допустит собственной смерти!



Все в мире относительно.Даже го.

А на каких носителях вы будете хранить иформацию, полученную при расчете вариантов по АОС во время партии? И на каких приципах это запоминание будет строиться?

Цифры для размышления:
1. Число вариантов в го где-то 10 в 750
2. Если упаковать плотно ( как в ядре) весь "видимый объём Вселенной" (известный астрономам) то их число будет где-то 10 в 90.

Физики, подскажите, может я чего-то не понимаю.



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

Существуют еще более плотные упаковки (говорят). И можно ссылки на источники инф-ии по числам?

Запоминать все не обязательно, если быстро считать... и информация, может быть, допускает еще более плотную упаковку? Ведь физические носители информации в зависимости от упорядочивания только в одномерном пространстве дают тоже факториальные числа.

Моя прикидка (навскидку :) дала верхнюю оценку числа вариантов партий в го несколько больше приведенной (но я грубо оценивал).

Для интересующихся дам примерную асимптотику на основе формулы Стирлинга:

n! ~ 1/12 х (...) х n**n,

где коэффициент в скобках (его я не помню, что-то с корнем квадратным, кажется) тоже зависит от n, но уже не так сильно, а 361**361 ~ 10**1000. Нужно учесть симметрии (1/8 примерно), хотя существенного влияния по порядкам величин это не дает.

Если говоритьоб "объмах" го, то эта цифра меньше, чем 3 в степени 361. Или 9 в 180 степени. Именно таким числом оценивается число всевозможных позиций. Число вариантов не имеет значение, ибо математически понятие вариант не определяется.
Впрочем, эта цифра больше всех известных физических цифр.
Я допускаю мысль, что Всевышний может обыграть Ли Седола на 9 камнях. Никому не ведомо, в какую силу можно играть в го, если уметь просчитывать позицию до конца партии!



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

Насчет 3**361 - это вопрос спорный. Факториальный характер числа позиций (точнее, возможных вариантов розырыша корректных последовательностей ходов - партий) никем не оспаривался и не опровергался. Если есть другие данные, то прошу ссылку.

Число перестановок (последовательностей) из 361 - это 361! (факториал). Конечно, не все последовательности корректны и имеют смысл. Но порядок-то указывается на основе этой суперверхней оценки. И тут число 10**750 у меня вызывает больше доверия. А это совсем не 3**361, а на много-много порядков больше (число с 750-ю цифрами или только около 150-ти - две большие разницы, первое в привычной записи в пять раз длиннее).