26.11.2008

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

Естественно, общественность давно волнует вопрос - в чем
секрет успеха Рыбки? За счет чего она достигла такого уровня игры?
Было бы закономерно задать этот вопрос автору - Васику Райлиху.
Но этот странный человек очень любит прятать свои секреты от публики.

Более откровенен соавтор Рыбки - Ларри Кауфман. Но он занимался только
одним аспектом алгоритма - оценочной функцией (ОФ). Причем он не занимался
программированием - эта область была целиком в руках Васика.
Ларри занимался только разработкой алгоритмов, и он поведал широкой
публике идеи, заложенные в ОФ, но только в самых общих чертах.

Итак, загадка оставалась загадкой.

Но вдруг произошло нечто невероятное! У меня в руках оказались исходные
тексты Рыбки 3. Не ожидал такой щедрости от людей, которые до сих пор
относились ко мне без большой симпатии. Впрочем, за последние полтора года
со мной произошло много странных событий, которым я перестал удивляться.

Итак, вот оно - сокровище, из которого можно узнать все секреты Рыбки!
Но с чего начать?

Обсуждение Рыбки на шахматных форумах, в которых принимал активное участие
и Ларри Кауфман, определило пожалуй наиболее важный вопрос: что важнее
для Рыбки - более эффективный поиск с хитрыми условиями сокращения перебора
или продлениями в сложных позициях, или так называемые шахматные знания,
реализованные Ларри Кауфманом в оценочной функции.

Я решил начать свои исследования с оценочной функции - просто надо же
с чего-то начинать. Идея сформировалась довольно простая - взять последнюю
версию Стрелки 2.0, и ничего не меняя в алгоритме перебора, заменить в ней
ОФ из Рыбки. И посмотреть, как это повлияет на игру Стрелки.

Работа оказалась непростой. Сначала пришлось многое изменить в ОФ Рыбки,
чтобы она легче вписалась в Стрелку. Прежде всего пришлось убрать из ОФ
так называемую "ленивую" оценку. Это дополнительные условия,
позволяющие не вычислять оценку полностью, ограничивая расчет оценкой материала.
Условия, которые использует для этого Рыбка, поставляет алгоритм перебора,
и для их правильного использования пришлось бы многое переписывать в Стрелке.
Последующий анализ показал, что результаты перебора Рыбки после отключения
условий ленивости практически не изменились, однако скорость перебора
упала примерно на 30%.

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

В итоге операция по пересадке ОФ Рыбки в Стрелку завершилась успешно.
Полученный гибрид был назван Стрелка 3R.

Конечно, пришлось все хорошенько проверить. Для этого был взят набор
позиций из реальных партий (несколько сотен тысяч позиций), и для каждой
такой позиции вызвана ОФ Рыбки 3 и Стрелки 3R. Оценки в точности совпали.
Затем Рыбке и Стрелке было предложено несколько сотен тысяч позиций,
получаемых из начальной позиции после выполнения серии ходов. Это было
необходимо для проверки правильности функции move_do() Стрелки, в которой
вычисляются важные для ОФ параметры. Результаты также оказались идентичными.

Был проведен также тест на корреляцию Стрелки 3R с Рыбкой 3. Для этого
из некоторого множества партий были выгружены несколько тысяч позиций,
и было предложено выполнить перебор из этих позиций трем участникам
событий - Рыбке 3, Стрелке 2.0 и Стрелке 3R. Затем был посчитан процент
совпадений предлагаемых ходов. У Стрелки 2.0 процент совпадений с Рыбкой 3
получился равным 63%, а у Стрелки 3R - 72%.

После этого можно было начинать тестирование Стрелки 3R. В качестве
соперника для тестов была взята Стрелка 2.0, поскольку хотелось выяснить,
что изменилось в игре именно Стрелки. Итак, был запущен турнир из 200 партий
между этими двумя Стрелками на контроле 2 минуты на 40 ходов.

Начало турнира было обнадеживающим - после 30 партий Стрелка 3R вела
со счетом +13 -5 =12. Я уже готовился к тому, чтобы поблагодарить Ларри
Кауфмана за его великолепную работу. Однако стартовый результат оказался
очередной шуткой теории вероятностей. Постепенно результат начал выравниваться,
и итог 200 партий оказался почти равным: +59 -54 =87 в пользу Стрелки 3R.

Казалось бы, такой результат говорит о том, что ОФ Рыбки 3 не может
рассматриваться как решающий элемент, влияющий на ее силу игры.
Однако анализ сыгранных партий позволил сделать еще некоторые выводы:

1) Оценка Стрелки 3R в играх оказалась более стабильной, чем у Стрелки 2.0,
т.е. она не так резко изменялась от хода к ходу. В целом число таких скачков
оценки (более чем на 0.5) у Стрелки 3R оказалось на 40% меньше,
чем у ее соперницы. Правда, эта "стабильность" ОФ у Стрелки 3R
может быть связана просто с меньшей средней глубиной перебора (см. ниже).

2) За счет более плавного изменения оценки Стрелка 3R тратила в среднем
меньше времени на обдумывание своих ходов. Это обусловлено тем, что
в алгоритме Стрелки при отсутствии резких колебаний оценки перебор завершается
быстрее.

3) Стрелка 3R в среднем допустила меньше тактических просчетов. И это
несмотря на то, что Стрелка 3R выполняла перебор гораздо медленнее,
чем Стрелка 2.0. Сложная ОФ Рыбки 3 замедлила скорость перебора примерно
вдвое. Из-за этого Стрелка 3R выполняла расчет на меньшую глубину, чем ее
соперница (примерно на 1 уровень).

4) Та же медленная ОФ и меньшая глубина перебора часто приводила к тому,
что Стрелка 3R не находила выигрыша даже в тех позициях, в которых ее
соперница такой выигрыш (т.е. проигрыш для себя) уже видела. Это привело
к большой серии "беззубых" ничейных партий, в которых Стрелка 3R получала
ощутимое преимущество, но не смогла его реализовать. Стрелка 2.0 просто
"пересчитывала" свою соперницу.

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

Вывод получился следующим: несмотря на меньшую скорость перебора
(в узлах в секунду) примерно на 70% по сравнению со Стрелкой 2.0,
Рыбка за то же время, а значит и за меньшее число узлов, достигает
глубины в среднем на 3 уровня больше! Это означает, что сильные
шахматные знания Рыбки 3, реализованные в ОФ, гармонично соединяются
с эффективным перебором.

Рыбка и лучше понимает позиции, и при этом "пересчитывает" своих
оппонентов.

Стрелку 3 R можно скачать здесь

Hosted by uCoz