Девятый чемпионат мира по шахматам среди компьютеров
 |
И дело не только в победе специализированной модификации IBM SP2 над Гарри Каспаровым: такой компьютер на сегодня — это единичный, уникальный экземпляр. Дело в том, что уже сегодня шахматные программы играют на уровне мастера и достаточно часто побеждают гроссмейстеров. Даже без усовершенствования уже существующих шахматных программ сам по себе рост производительности процессоров должен привести к победе компьютера над человеком.
 |
| В девятом чемпионат мира по шахматам среди компьютеров приняли участие 30 шахматных программ из 11 стран |
А пока что 20 июня в известном в шахматно-компьютерном мире городе Падерборн (Германия) завершился очередной — девятый — чемпионат мира, организованный международной компьютерной шахматной ассоциацией ICCA. В нем приняли участие 30 шахматных программ из 11 стран. Больше всего участников было из Германии (12) и США (6). Россия была представлена программой Centaur (разработчики — Вихрев и Манякин, Институт атомной энергии им. Курчатова). Попробуем дать «компьютерную» характеристику некоторых участников, основываясь на данных Web-сервера Падерборнского университета (www.uni-paderborn.de).
Гиганты и карлики
При взгляде на состав участников бросается в глаза, что они явно из разных «весовых категорий». С точки зрения аппаратных платформ представлен почти весь диапазон — от ПК до многопроцессорных суперкомпьютеров. Разнообразие шахматных программ тоже под стать этому: от любительских программ, созданных в порядке личной инициативы, до коммерческих продуктов. Не будем вдаваться в подробности применяемых в программах-участницах алгоритмов поиска, оценки позиций и т. п., а остановимся на используемых аппаратно-программных средствах, что также представляет интерес.
Целый ряд специальных методов поиска стал общим достоянием шахматных программ, например aльфа-бета поиск или техника селективного поиска «нулевой ход» и т. д. В последнем случае, например, при анализе одной из сторон разрешается сделать два хода подряд, что позволяет отбросить слабые ходы до начала поиска на полную глубину.
Что касается применяемых аппаратных средств, то прежде всего упомянем на американскую программу CilkChess, которая работает на 256-процессорной ccNUMA-системе SGI Origin 2000. При разработке программы был использован специализированный многонитевой язык программирования Cilk, эффективный для распараллеливания «нерегулярных» программ наподобие шахматных. Только под хранение специальных таблиц здесь отводится свыше 32 Гбайт разделяемой оперативной памяти. В середине игры программа просматривает на глубину 15 полуходов, ее производительность — от 5 до 15 млн. сделанных ходов в секунду.
СilkChess — далеко не единственная распараллеленная программа, представленная на чемпионате. Голландская DIEP также является экспериментальной распараллеленной версией. В немецкой P.ConNerS используется специализированная технология параллельного поиска. Сообщается, что на параллельном компьютере (вероятно, кластере) с 60 процессорами Pentium/300 МГц (вероятно, Pentium II) она достигла производительности около 1,2 млн. узлов в секунду. Немецкая же программа SOS теперь также имеет распараллеленную версию.
Представленная «хозяевами» чемпионата программа Zugzwang разработана в Падерборнском университете в рамках исследований в области эффективных параллельных алгоритмов для задач оптимизации. Первоначально она предназначалась для транспьютеров и была написана на языке Occam. Уже в 1992 году она играла на 1024-процессорной системе. К 1995 году программу переписали на Си, поэтому теперь ее можно эксплуатировать на различных МРР-системах с распределенной памятью, в том числе на SGI/Cray T3E или МРР-cистемах на базе процессоров PowerPC. В чемпионате играла версия на 512-процессорном Cray T3E с 300-мегагерцевыми микропроцессорами Alpha.
К противоположному диапазону производительности аппаратных платформ можно отнести еще одну немецкую программу GromitChess, которая работает на компьютере с процессором AMD K6/200 МГц и написана на C++ в среде ОС Linux. Ее производительность составляет 25-50 тыс. узлов/сек. Низкую производительность (18 тыс. узлов в секунду) имеет и другая программа для ПК — Hiarcs, полностью написанная на Си. Опять-таки немецкая программа IsiChess имеет корни в стартовавшем в 1991 году проекте, базирующемся на применении библиотеки классов для DOS/Windows и средств графического пользовательского интерфейса. Известная датская коммерческая программа Rebel 10.0 также разработана для ПК. Другой пример коммерческой программы для ПК — французская Virtual Chess. Она также написана на Си и 32-разрядном Ассемблере, снабжена графическим пользовательским интерфейсом и может работать в средах Windows 9х/NT.
Выбор языка Си для написания шахматных программ часто диктуется соображениями переносимости в разные аппаратно-программные среды. Конечно, для разработки шахматных программ используется не только C/C++. Так, в одной из ведущих профессиональных шахматных программ Nimzo применен специализированный «шахматный» язык CHe++. Немецкая программа Ikarus, ранее именовавшаяся BasicChess, использует Паскаль. Эта программа ориентирована на применение «стандарта» Winboard. В ближайшее время должна появиться Winboard-версия другого участника чемпионата — лучшей датской любительской программы Arthur.
К нижнему диапазону производительности по сравнению с мощными многопроцессорными системами следует отнести и DarkThought — разработку немецкого Института структур программ и организации данных, написанную на ANSI Си. В ней использованы известные алгоритмы альфа-бета-поиска, технология bitboard и другие. Она работает на компьютере компании KryoTech с разогнанным до 767 МГц микропроцессором Alpha 21164A и 256 Мбайт оперативной памяти. Ее производительность, естественно, выше, чем у ПК-конкурентов: до 350 тыс. узлов в секунду в середине игры, свыше 1 млн. в эндшпиле.
Российская программа Centaur не относится к числу лидеров по формальной производительности: она рассчитывает только 500 позиций в секунду. Однако это уникальная высокоселективная программа. В ней в процессе выбора используются сразу пять значений оценки позиции — одна реалистическая, две пессимистические и две оптимистические. Напомним, что реальная сила игры шахматной программы определяющим образом зависит не только от скорости и соответственно глубины перебора, но и от эффективной оценки позиции и качественного начального отбора ходов.
Иллюстрацией этому — достаточно высокие показатели Centaur. Скажем, на известном «человеко-машинном» турнире в Аегоне в 1997 году ею был достигнут рейтинг 2267.
Спортивно-технические показатели
Из приведенных выше данных ясно, почему так сильно различаются спортивные успехи программ-участниц чемпионата. Любительские программы гордятся победами над профессиональными. Некоторые участники — победители национальных компьютерных чемпионатов (Ruy Lopez — чемпион Испании) или международных компьютерных соревнований (P.ConNerS — победитель компьютерного турнира в Падерборне в текущем 1999 году). Наиболее интересные результаты — это игры с мастерами и гроссмейстерами, а также мировые компьютерные чемпионаты. Некоторые из этих данных приведены ниже.
Наиболее «продвинутые» участники (Fritz, Zugzwang и др.) уже достигали гроссмейстерских результатов. Так, Zugzwang на турнире в Липпштадте (1998 год) играла на гроссмейстерском уровне коэффициента «Эло» — около 2600.
Из правил проведения компьютерного чемпионата
Соревнования проводятся по швейцарской системе в семь туров. Контроль времени — 2 часа на 40 ходов и далее 0,5 часа до конца партии. Оператор программы может дважды за партию обратиться к директору турнира с просьбой остановить часы из-за технических проблем, но не более чем на 15 минут. Если будет доказано, что проблема не в компьютере, а в сетевом соединении, директор турнира может разрешить дополнительную задержку. Терминалы должны быть подсоединены непосредственно к удаленному компьютеру, без «человека в середине».
E2-E4
Некоторые достижения программ-участников
СilkChess: первое (1996) и вторые (1997, 1998) места на открытом чемпионате Дании (1996); второе место на компьютерном чемпионате мира (Гонконг, 1995) (CilkChess, точнее ее предшественница, программа Socrates, уступила Fritz в плей-офф, но выиграла у нее в основной части турнира).Fritz: первое место на компьютерном чемпионате мира (1995); первое место на блицтурнире в Мюнхене (1993) с участием мировой шахматной элиты; лучшее место среди компьютеров на человеко-машинном турнире в Аегоне (1996); лидер шведского шахматного рейтинга в 1998 году; первое место на турнире по активным шахматам (Франкфурт, 1998) c участием 36 гроссмейстеров.
Hiarcs: чемпион среди микрокомпьютеров (Мюнхен, 1993); первая шахматная программа для ПК, победившая мастера ФИДЕ в матче с турнирным контролем времени (1997); обошла ряд маcтеров и гроссмейстеров на открытом турнире в Годесберге.
Shredder: компьютерный чемпион мира (Джакарта, 1996); третье место на компьютерном чемпионате мира (Париж, 1997).
Virtual Сhess: поделила I место на турнире в Аубервиллере (1996), вместе с известными бывшими советскими шахматистами Вайсером и Черниным.
Zugzwang: второе место на гроссмейстерском турнире (Липпштадт, 1998)
В нынешнем чемпионате первое-второе места разделили американские программы Ferret и Shreder — по 5,5 очка из 7, а третье-четвертое места разделили Fritz и CilkChess — по 5 очков. В основной части турнира эти программы сыграли между собой вничью. В партии плей-офф борьба снова завершилась вничью, причем по ходу игры Ferret черными получила позиционное преимущество, но после размена преимущество в эндшпиле оказалось уже на стороне CilkChess. Она смогла даже выиграть качество, но ее король не смог уйти из-под непрерывных шахов, и на 101-м ходу упорная борьба завершилась троекратным повторением позиции. По дополнительным показателям первое место было присуждено программе Shreder. Интересно, что представленные на сервере данные о программе Ferret были весьма скудными — она характеризовалась несколькими строчками как «обычная шахматная программа».
Российская программа Centaur, одержав две победы, набрала 2 очка и оказалась в нижней части турнирной таблицы. Следующий чемпионат мира состоится в 2002 году.