Рейтинг программ для игры в Го

Кто-нибудь знает, где можно посмотреть текущий рейтинг компьютерных програм для игры в Го?
Заранее благодарю.

Сомневаюсь, что такой существует.

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

Он существует и как-то даже мне попадался (когда я им не интересовался).

Рейтинг одной и той же играющей программы может весьма разниться в зависимости от условий игры. Наглядная иллюстрация - на КГС, где у некоторых Мого обозначено аж 1-2 кю на доске 19*19 (что на 9*9 компьютер играет сильнее - доказывать, думаю, не нужно). Зайдите в комнату Computer Go (она в каталоге "Общение") - и понаблюдайте...
Дело в том, что условия игры на КГС выбирает компьютер, точнее - хозяин программы. И это предоставляет возможность поставить человека в худшие условия. Как? Для начала - ограничим время до 10 мин. Уже эффект - ведь компьютер может тратить на ход доли секунды и отвечать практически сразу. Мало? Убираем байоми, 20, даже 10 мин абсолютного контроля. Человек уже порядком стеснен, программа, едва играющая на 6 кю, начинает обыгрывать "четырехкюшных" биологических противников. Как добить нашего брата окончательно? А мы по китайским правилам, да чуть изменим программку: пора пасовать, а она выставляет камешки на свои территории, пока не останется два пустых поля - для глаз. Подставляет и на чужую - пусть едят, а это секунды и десятки секунд.
Это не мои фантазии, я много играл с ботами на КГС и делал своих. До сих пор вспоминаю первый опыт с ботом на основе Мого. Соорудил бота, запустил, и тут вызов подхватывает японец 4 дана. Бот проигрывает, само собой, но ведь дальше - все, как я описывал выше. Ставит и ставит камешки в абсолютно проигранной позиции. Я чуть со стыда не сгорел, а сделать ничего не могу - бот автономен, за него не сдашься.
Вот вам и высокие кю у программ...

MoGo (по крайней мере, которую можно сейчас качать с официального сайта) как раз имеет привычку сдаваться, если за время обдумывания не наталкивается на выигрышный вариант (тонко регулируется при помощи параметра --minNumberOfSimulationsOfResign).
И лучше всего с ним играть под Linux 64-bit и многоядерным процессором, дав много времени на ход и возможность обдумывания на Вашем ходе (--pondering 1).
И, говоря про рейтинг, я имел ввиду абсолютный рейтинг, т.е. условия должны позволять использовать все возможности программы.

Да, MoGo - програма интересная... У меня тут есть одна программка из 2003 года "Wulu-III" для Виндовоза (японские друзья подарили). Да-да, та самая наследница легендарного Handtalk и Wulu (2 в одном флаконе). Так вот эта программа официально играет на максимальном уровне в силу 9 Кю ( по заявлению самого автора). И она запросто вынессла такие программы как "Go++" версии 5, 6 и 7 (в том числе и делюкс), MFGO (11 версия), Aya (последняя версия с сайта автора) и даже Silver Star (одна из самых сильнейших программ по статистике), правда не последниюю версию а версию 5 из 2001 года. Так вот эта самая MoGo бъет Wulu с перевесом в пол/полтора очка, причем как на доске 9х9, так и на 19х19. А ведь это еще не финальный релиз программы! Я проводил тесты с 3-м релизом. Сам я играю в силу 15/16 Кю (на КГС - 9/10 Кю, на FICGS - 10 Кю, на Oro - 23 Кю). У Wulu я выигрываю в среднем 1 партию из трех (без форы, максимальная сила игры, 19х19). У MoGo из 5-ти сыгранных партий я не выиграл ни одной. Делаем выводы.

takitano, сравните пожалуйста с gnugo последней версии. Мне интересно.

А где взять последнюю версию? У меня есть только 3.6. В следующие выходные попробую сравнить.

[kamakama.s151.xrea.com]

MoGo обыграет любую (даже любую коммерческую, не говоря уж о GnuGo) программу, если:
1. Запустить их на разных комп-ах (или распределить между ними ядра поровну).
2. Использовать для MoGo мощный (лучше всего 8-ядерный) комп. (требования к памяти - ~6ГБ на каждый удерживаемый в памяти 1млн узлов дерева (--collectorLimitTreeSize 1000000)).
3. Использовать MoGo_release3_big64 версию программы для 64-bit Linux.
4. Запустить MoGo c параметрами --19 --time 120 --pondering 1 --nbThreads 8 (для 8-ядерного комп-а) --collectorLimitTreeSize (см. выше).
5. Запустить противостоящую программу на комп-е не лучше MoGo-шного (или см. выше).

Проверено (лично мной - SmartGo в Shareware'ный период с настройками работы с базами данных игр, выбора тактики и т.п. по умолчанию, а настройка времени - как у MoGo - 120с на ход и коми 6,5; при этом, если мне не изменяет память, возможностей использования многоядерности и обдумывания на ходе противника у неё нет).

P.S. В этом случае и у Вас (если Вы не обладатель дана и играете без возвращения ходов) не будет шансов (практически - всё-таки метод Монте-Карло).

Как и обещал, проверил игру Мого против Гнуго (3.7.12). Мoго играла белыми, коми - 0 очков, обдумывание хода - 30 секунд, обдумывание хода во время игры противника - включено. ГнуГо играла черными на 10 (максимальном) уровне игры. Правила - китайские. Игра велась на одном и том же компе.

Результат - МоГо выигрыла с перевесом в 3 очка.

Пока что преимущество Mogo не представляется мне подавляющим. Было бы интересно набрать статистику.

Мого запрограммировано таким образом, что выигрывает всегда с преимуществом в пол-полтора очка ( по сведению разработчиков программы). Чтобы этого добиться она часто делает "глупые" ходы на своей территории или отдает группы камней. Я не знаю, нафиг они это сделали - программа играет сильно, но норовит самое позднее на 5-6 ходу сыграть в центре. В общем, люди так не играют и таких как я "кюшников" эта манера игры сбивает с толку. Это не "космический стиль" Такемии, это не Го Сейген, и не Чо. Это черт знает что, но программа все равно выигрывает.

Я бы всё-таки сказал, что она делает не "глупые ходы", а сверхконсервативные. У движка нет цели выиграть игру с максимальным перевесом, у нее стоит цель ее просто выиграть (а для этого, как известно, достаточно 0,5 очка). Как только программа понимает, что она в стабильном перевесе, у нее тут же пропадает желание бороться и она делает защитные ходы, которые делают все поползновения противника изменить счет в свою пользу бесполезными. Всё это, опять-таки, по методу папы Карло.

Кстати, GnuGo на 10 уровне сложности с настройками по умолчанию играет на любом железе одинаково (просто на слабом делает ходы дольше).

На КГС, если кто не в курсе, 3.7.12 играет на 6 кю, а 3.7.10 - на 7 кю.

А вот уровень игры МоГо напрямую зависит как от железа, так и времени, затраченного на ход.

Автор программы даже шутил, что если давать ей 0 секунд на ход - то она будет делать случайные ходы, а если бесконечно много - она будет играть "рукой бога" (kami no itte). Пока что ее уровень - где-то между :)

Inego Написал:
-------------------------------------------------------
> ...А вот уровень игры МоГо напрямую зависит как от
> железа, так и времени, затраченного на ход.
>
> Автор программы даже шутил, что если давать ей 0
> секунд на ход - то она будет делать случайные
> ходы, а если бесконечно много - она будет играть
> "рукой бога" (kami no itte). Пока что ее уровень -
> где-то между :)


Проверял на MoGo_release3_old_proc и MoGo_release3 для Windows (запускал играть саму с собой с коми 6,5 и с включённым --pondering 1).
Максимальное время на ход - не более 50мин (точнее - 2999,5с). При этом old_proc реально затрачивала на, как правило, ~10мин меньше (белыми - ещё меньше), а у виндовозовской программы (которая работает только с одним ядром) время можно увеличить за счёт --nbThreads (до 400мин) независимо от количества ядер у комп-а. У old_proc же уже при --nbThreads 2 комп. (естественно, 1-ядерный) начинает так тормозить, что MoGo не успевает вовремя делать "cut tree", в результате чего постепенно забивается память, что заставляет комп. ещё больше тормозить и в итоге - зависнуть.
Также мне не удалось на 2ГБ комп-ах повысить использование памяти виндовозовской программой выше ~940МБ (--collectorLimitTreeSize 210000) - вылетала с ошибками: "mogo 2420_cygtls::handle_exceptions:Exception: STATUS_ACCESS_VIOLATION. Error while dumping state (probably corrupted stack)" (на консоли и в файле mogo.exe.stackdump). При этом при меньших значениях collectorLimitTreeSize и даже без задания параметра --pondering 1 программа зависает через ~80мин (время ЦП) независимо от задания времени (главное, чтобы до перезагрузки программы она успела бы потратить не менее 80мин на обдумывание независимо от количества сыгранных игр), зачастую с ошибкой на консоли: "mogo 3220 sig_send: wait for sig_complete event failed, signal -34, rc -1, Win32 error 6".
Ещё проверю MoGo_release3_big64 (но не скоро, так что кому интересно - можете пока сами проверить хотя бы MoGo_release3_big на 32-битной Linux).

В некоторых странах логические игры возводятся в ранг религии. Так, в Японии древнейшая игра Го приносит своим чемпионам поистине божественное поклонение. Можно с уверенностью сказать, что человек, способный создать сильную программу в Го, на уровне лучших японских мастеров, обессмертит свое имя в Стране Восходящего Солнца и получит миллионные доходы. Уже официально объявлен приз в один миллион долларов для программы, играющей в силу 1-го дана. Но игра Го отличается от других игр подобного плана именно сложностью эффективной реализации на компьютерах, поэтому появление сильнейшей программы в Го предсказывается к 2050-му году (для примера, в шахматы - к 2010-му).

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

Подавляющее большинство программ построено на так называемом методе “грубой силы” - “brute force” (полный перебор). Из текущей позиции определяются все возможные ходы - в шахматах их в среднем бывает около 50, в Го - 100-300, в калах - до 6. Они запоминаются в массиве Moves[][], где первым измерением является глубина перебора (исходно 0), а вторым - список ходов из позиции на i-м уровне. Затем выбирается очередной ход из нерассмотренных на данном уровне, совершается, опять определяются все возможные ходы (уже за другую сторону), снова выбирается очередной ход, и так происходит до достижения некоторой заданной глубины. В конце варианта происходит оценка возникшей позиции с помощью экспертных оценок (например, значения фигур плюс позиционная составляющая - конь в центре-хорошо, король открыт-плохо), и из всех позиций, перебирающихся на заданной глубине, выбирается одна с максимальной оценкой, и первый ход, ведущий по ветке в эту позицию, объявляется лучшим.

Эта методика стандартна, она описана во множестве статей и учебников по игровому программированию. Но посмотрим, а на какую-же реальную глубину сможем мы рассчитать варианты? Ведь количество ходов в дереве вариантов явно подчиняется геометрической прогрессии. В шахматы для игры на мастерском уровне требуется считать не менее чем на четыре-пять ходов (или 8-10 полуходов - ходов одной стороны) плюс форсированные продолжения - взятия, шахи и превращения. Тогда программе за две минуты стандартного контроля времени в официальных партиях потребуется просмотреть минимально 50 в десятой степени ходов, что составляет 10 в пятнадцатой степени позиций (миллион миллиардов). Лучшие программы на 486-м процессоре в секунду анализируют не более тысячи позиций. За две минуты это составит 120000 позиций. Для расчета на глубину 10 полуходов программе потребовалось бы 10 миллиардов секунд или около сорока лет!

Но, к счастью, умные люди придумали специальные эвристики, позволяющие существенно сократить объем перебора. Это, в первую очередь, алгоритм ветвей и границ, затем служба лучших ходов, хэш-таблицы и еще несколько других. Таких эвристик в мире известно немного, около десятка, и за каждую новую математики всех ведущих научных центров мира готовы платить огромные суммы - ведь большое количество прикладных задач решается именно методом перебора. Более подробно интересующиеся методами программирования переборных задач могут почитать статью о программировании игры в калах с исходными текстами алгоритмов на языке Си в одном из номеров PC-Review.

Отсюда становится понятной проблема программирования игры в Го. Если в шахматах коэффициент геометрической прогрессии 50 позволяет лучшим программам быстро рассчитывать варианты на пять-шесть ходов, то в Го количество ходов в начале партии составляет 19*19 = 361 ход, а в середине, когда начинается основная борьба - около двухсот. Понятно, что в лучшем случае программа сможет сделать расчет на четыре, максимум пять полуходов, что совсем недостаточно для сильнейшей игры. Го игра во многом позиционная, но, к сожалению, проблема обучения программ позиционной игре остается пока открытой.

Так же и с MoGo. выше головы не прыгнуть.....

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

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

kit144, статья пятнадцатилетней давности? :)

kit144 Написал:
-------------------------------------------------------
> Подавляющее большинство программ построено на так
> называемом методе “грубой силы” - “brute force”
> (полный перебор).

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

> Лучшие программы на 486-м процессоре в секунду
> анализируют не более тысячи позиций. За две минуты
> это составит 120000 позиций. Для расчета на
> глубину 10 полуходов программе потребовалось бы 10
> миллиардов секунд или около сорока лет!

> Так же и с MoGo. выше головы не прыгнуть.....
--------------------------------------------------------

MoGo использует метод Монте-Карло (т.е., насколько я понимаю, не полный, а случайный перебор с, естественно, определёнными алгоритмами оптимизации выбора).

MoGo использует не фиксированную глубину анализа, а фиксированное время.

Современные программы на современных комп-ах производят ~10^5 симуляций ("...from a given Go board position, a fast random player plays the game until the end. Then the score can be calculated quicly and precisely directly from the Go rules. We call that a simulation.") в секунду (у меня на домашнем 4-х ядерном х86 проц-е в MoGo_big64 получалось около 50тыс. при --nbTreads 10).

Запустите MoGo на 8 ядрах с 50мин на ход и --pondering 1 и подрубите её в качестве бота на каком-нибудь online сервере го с обычными настройками (для человека, - т.е. с максимальным временем - сутки на ход). Если из каждых 10 откликнувшихся хоть 1 выиграет, то Вам ещё повезёт (повысить вероятность можно ограничив снизу уровень игроков, например, 1 даном).