Го и шахматы

))))

Не кощунствуй!!!

Го-бог смотрит на нас и ухмыляется.

Свинья, которая не летает, это просто обычная свинья (с) Порко Россо

В шахматах ходы считаются парами, Белых и Чёрных, так что реально эти 332 варианта будут у каждого полухода. Не думаю, что автор имел ввиду, что средняя длина шахматной партия - 25 (шахматных) ходов - это всё-таки маловато. Поэтому надо бы шахматный показатель возвести в квадрат ещё. Всё равно конечно у го остаётся огромное преимущество над шахматами, но главное не это. Не мне (я весьма слабый игрок в го) вам объяснять, что главное препятствие для моделирования го это не количество вариантов, а отсутствие легковычисляемой оценочной функции для позиции. В шахматах в качестве такой функции можно даже использовать лекговычисляемую разницу в материале и при достаточной мощности компьютера программа уже сможет вполне прилично играть, тупо перебирая все ходы - реально же их не 332 будет, а меньше раз в 10 точно. Не думаю, что шахматную партию, в которой в течение 50 ходов у каждого игрока будет по 9 ферзей и все остальные фигуры и ничего не будет сбито можно назвать типичной! С другой стороны кто сказал, что шахматная партия будет продолжаться 50 ходов? Она может очень долго длиться - 50 ходов (полных, то есть 100 полуходов) между очередным взятиеи или ходом пешки. Всего у каждой пешки максимально 6 ходов + ещё 30 взятий (но так как пешкам надо разминуться на пути в ферзи, то 8 взятий придётся потратить на взятия пешками, то есть останется их 22) = (6*16+22)*50 = 118*50 = 5900 ходов или 11800 полуходов. И даже если на каждом ходу будет всего 10 вариантов, то мы получим огромное число, намного превосходящее числа из приведённых примеров. Партия в го тоже конечно может длиться намного дольше, чем 250 ходов. Мне даже трудно оценить это число...

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

Ещё один аргумент в пользу того, что такие формальные методики не являются особо осмысленными - давайте сравним го не с шахматами, а с гомоку (крестики-нолики до 5 в ряд на той же доске 19х19). Формально в гомоку примерно такое же число вариантов как и в го на каждом ходу. По крайнеё мере сначала. Но, конечно, партия заканчивается обычно раньше, чем в го, а самое главное - число разумных ходов весьма мало, несмотря на такую огромную доску (играть на доске 19х19 или на бесконечной доске - разницы фактически нет). И есть более менее простые алгоритмы для оценочной функции, сужающие число рассматриваемых вариантов катастрофически без опасности упустить сильнейшие ходы. Тем не менее гомоку остаётся достаточно содержательной игрой и программы, которая играет лучше сильнейших людей пока не написано (хотя считается доказанным форсированный выигрыш начинающего партию, сейчас играют с дебютным регламентом, несколько выравнивающим шансы сторон).

Прочитал интересное сравнение Го и шахмат от WinPooh:
[www.livejournal.com]

Что есть в Го, чего нет в шахматах?

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

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

а) Правило ко. В двух словах: запрещается повторять позицию, возвращая обратно только что снятый камень и забирая при этом «побивший» его камень противника. Обратное пробитие ко разрешается только после хода в каком-то другом месте. Это на первый взгляд искусственное правило приводит к совершенно сумасшедшей тактической взаимосвязи отдалённых друг от друга участков доски. Можно провести аналогию с классической и квантовой физикой. Если в шахматах «силовые линии» фигур распространяются по прямой (конь – исключение, подтверждающее правило), то в Го возможно магическое взаимодействие «зацепленных» друг с другом конфигураций, а-ля пары частиц в парадоксе Эйнштейна-Подольского-Розена.

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

б) Рейтинг-система и форовый принцип. Шкала мастерства в Го очень сильно растянута, по сравнению с шахматной. Что, впрочем, немудрено, если исходить из числа вариантов в Игре и количества паттернов, которые ученику приходится усваивать в процессе восхождения по бесконечной лестнице... Если в шахматах «разрядов» можно насчитать от силы 7-10 (под разрядом я понимаю ступень, дающую 75%-ю вероятность выигрыша старшего у младшего), то в Го этих ступеней наберётся не меньше 20...30. Как же играть противникам разного класса, результат партии которых в игре на равных предопределён сильнее, чем в партии Каспарова с кмс-ом? Спасает фора. Совершенно удивительным свойством оказывается то, что при корректно выставленной форе в пределах до 9 камней игра сохраняет интерес для обеих сторон – а для стороны, принимающей фору, обычно имеет ещё и ценное учебное значение.

Мне доводилось играть в шахматы с классными игроками, дававшими фору типа «одна минута к пяти» – в подобных партиях не покидает ощущение того, что происходит игра не в шахматы, а в напёрсток. С другой стороны, для корректной материальной форы шкала шахмат слишком крупна – одна пешка в партии двух гроссмейстеров будет уже слишком большой форой, даже если класс игроков существенно различный. В Го же нередки случаи, когда профессиональные игроки дают по 2-3 камня форы высоким любительским данам (уровень, сравнимый с гроссмейстером в шахматах).

И ещё – иногда складывается ощущение, что форовая рейтинг-система знает о нас, игроках, чуть больше, чем мы сами. Даешь, например, или принимаешь, фору в четыре-пять камней – а партия после головоломной борьбы заканчивается с перевесом в пол-очка в ту или другую сторону... Удивительно, как простой математический алгоритм (в линейном приближении: фора в камнях = разность рейтингов в кю/данах), ничего не ведая ни о наших стилях, ни о характере партии – ни о чём, кроме статистики предыдущих игр – умеет настолько точно выявить разницу в силе и уравнять шансы...

в) Чувство свободы. В Го оно проявляется практически с первых шагов в обучении. Уже упомянутое обилие паттернов, приёмов игры, даёт возможность широкого манёвра. Даже начинающий может пробовать разные стратегии, изучать Игру с тех сторон, которые ему на данном этапе больше по душе – причём, рост практических результатов вполне ощутим, вне зависимости от того, в какой последовательности ученик осваивает тактические и стратегические премудрости. Свобода – она и в огромном числе вариантов уже для первого хода в партии, и в отсутствии необходимости запоминать наизусть длинные форсированные варианты (запоминать потом всё равно придётся, но это «потом» вполне откладывается до достижения уровня данов). Свобода в том, что очень редко одна-единственная ошибка может стоить партии – во всяком случае, на уровне средних и даже старших кю. В шахматах я в своё время, школьником, остановился в росте по причине непонимания, куда же двигаться дальше – попал в стандартную ловушку, когда человек считает тормозом своей игры плохой счёт вариантов или незнание наизусть дебютов. В Го же такой иллюзии нет – я ясно вижу, что среди прочего мне недостаёт именно понимания Игры. Но зато теперь есть оптимизм и вера в то, что это понимание можно в себе развивать и улучшать )

shadowjack Написал:
-------------------------------------------------------
> Вот поэто-му у меня и вызывает сомнение разные
> оценки Го-Бога, в частности силы его игры.
>

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

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

Данный парадокс присущ не только Го, но и шахматам и всем другим видам интеллектуальных игр.




ИНСТРУКЦИЯ о порядке учета рейтинговых турниров в РФГ(Б) - [gofederation.ru]



Редактировано 1 раз(а). Последний раз 02/08/2005 07:46 пользователем Serpov.

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

Да, одна фора в сёги - отдание одной фигуры (не помню последовательности). На максимальной форе сильный противник имеет только короля и все пешки.

Тут позвольте не согласиться.
По-вашему получается, что ИИ при игре на форе должен сразу сдаваться. Однако, можно дополнить стратегию игры выбором ходов, не "дающих проигрыш с наименьшим очковым выражением", а "дающих наибольшую вероятность победы". Видя все варианты дерева до самого конца, ИИ будет играть значительно успешнее про-игроков (конечно, ему придется применять
некоторые знания о том, как человек рассчитывает варианты). Партия на форе - это хаметэ по-любому (при коми 0).
Я не верю, что можно сказать - не существует го-бога, который будет выигрывать у сильнейшего про на 4-х камнях с вероятностью 50%. И никакая статистика не убедит меня в этом. Вернее, если бы такой игрок был, статистика его побед - убедила бы. Но асимптотика - увольте. Мы не знаем НИЧЕГО о поведении кривой при приближении к Го-богу (так как топ-про все еще находятся довольно далеко от него, на мой взгляд).
150 ходов - это супертэсудзи для Го-бога.

Heath Написал:
-------------------------------------------------------
> Да, одна фора в сёги - отдание одной фигуры (не
> помню последовательности). На максимальной форе
> сильный противник имеет только короля и все пешки.
>

Хм. Не. На максимальной форе сильные игрок имеет пешки короля и 4 генерала (2 золотых и два серебряных) Дело в том, что пешками выиграть невозможно, ибо они ходят прямо и едят прямо. Так что противник не думает, а пользуется простым алгоритмом. Обычно фора составляет одного или двух драконов (Ладья или Слон в переводе). Самая большая фора будет два дракона, два коня и две пики. В отличие от шахмат размен фигур на форе невыгоден. Так как съеденные фигуры могут быть введены в игру путём вбрасывая, более сильные игрок распорядится ими лучше.

> Тут позвольте не согласиться.

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

Но к игре с ИИ на равных это никакого отношения не имеет. Почти каждый ход (и хаметэ в том числе) будет тут же приводить к потере очков, так как отклоняется от оптимальной стратегии. Поэтому шансов на равных у реальных игроков в партии с ИИ нет. В партии на форе можно говорить о среднестатистическом выигрыше или проигрыше - в зависимости от уровня совершаемых реальным игроком ошибок. Статистика партий профи показывает, что во многих партиях из 120-150 ходов ошибки более одного очка имеют низкую плотность. А сама средняя статистическая ошибка за всю партию - сотые доли очка, т.к. статистика равных партий с нормальным завершением (когда не идет рубка "пан или пропал", а доигрывают до подсчета очков) говорит об очень низкой дисперсии ошибок, ст. отклонение в очковом результате партии составляет всего несколько очков у каждого из сильнейших профи. Даже если учесть что определяющих ходов не 100, а только 30-40 (вариант выбирается, а не отдельный ход), то и тогда на один "ход-вариант" приходится средняя ошибка порядка десятых долей очка или меньше. Куда же еще дальше двигаться в сторону ИИ? Сколько ИИ должен дать фору лучшему профи, чтобы шансы сравнялись? Это ведь глобальная закономерность, что дисперсия ошибок, если их выражать каким-то числовым параметром, монотонно снижается с ростом уровня мастерства в любом виде деятельности, где есть верхний предел совершенства (ИИ - идеальный исполнитель).

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


ИНСТРУКЦИЯ о порядке учета рейтинговых турниров в РФГ(Б) - [gofederation.ru]



Редактировано 1 раз(а). Последний раз 02/08/2005 11:15 пользователем Serpov.

> По-вашему получается, что ИИ при игре на форе должен сразу сдаваться.

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

И еще несколько слов по поводу оценки верхнего предела рейтинга (т.е. предполагаемого расстояния ИИ по рейтингу от ведущих профи). Если у ИИ дисперсия 0, и ст. отклонение ошибки - соответственно тоже, то на каком расстоянии он находится от тех, у кого такая ст. ошибка составляет в среднем за партию 10 очков? Если вспомнить про три сигма или для верности - 4 сигма, т.к. в нашем случае можно принять приближенно нормальность распределения (для целочисленной случайной величины "результат партии в очках"), то можно вычислить тот интервал, где сосредоточена основная масса всех ошибок, за исключением систематических, выпадающих из рассмотрения по критериям статистики: получим что-то между 30 и 40. А сколько это в камнях? Чуть больше 2 или 3. А если ст. ошибка 5 очков? Тогда - 1-2 камня. Так какова, по-вашему, ст. ошибка в партиях профи, если их суммарная ст. ошибка (корень квадратный из суммы дисперсий), формирующая результат партии, всего несколько очков (не более 10)? В самом худшем случае получим для сигма что-то около 7, или 20-25 (3-4 сигма) - расстояние по результату партии в виде суммы ошибок от уровня ИИ. Вот отсюда и взята моя оценка в 1-2 камня. 1 камень = 7-8 очков, 2 камня = 20-22 очка.

ИНСТРУКЦИЯ о порядке учета рейтинговых турниров в РФГ(Б) - [gofederation.ru]



Редактировано 1 раз(а). Последний раз 02/08/2005 11:48 пользователем Serpov.