В инструкции к известной шахматной программе Fritz 8, в 2003 году сыгравшей вничью матч с Гарри Каспаровым, написано, что при использовании достаточно быстрого компьютера она обыгрывает 99,99% людей. Означает ли это, что искусственный интеллект в данной области уже стал сильнее человеческого? Если судить по результатам — то, казалось бы, да

Широко освещавшиеся шахматные поединки человека и машины в последние несколько лет приносили успех компьютерам. Последним известным достижением компьютерных систем стал трехкруговой матч-турнир трех известных гроссмейстеров против трех известных шахматных программ осенью 2004 года. Играли Руслан Пономарев (чемпион мира 2003 года; однако сегодня по рейтингу ЭЛО он лишь 15-й), чемпион мира среди юношей 12-14 лет Сергей Карякин и болгарин Веселин Топалов, третий в мировом шахматном рейтинге. Компьютеры представляли действующий чемпион мира, израильская программа Deep Junior 9.0, программа Fritz, а также Hydra. Компьютеры выиграли с перевесом в три очка.

Нельзя утверждать, что это самые сильные на сегодня шахматные программы: в матче не участвовали серебряный и бронзовый призеры последнего компьютерного чемпионата мира по шахматам — немецкая программа Schredder 8.5 и Diep3d 7.5 соответственно. (Российские программы, увы, в этом чемпионате не участвовали.)

Большинство компьютеров, использовавшихся программами-участниками этого чемпионата мира, работали с 64-разрядными микропроцессорами AMD — Opteron и Athlon64. Вероятно, это связано с их высокой целочисленной производительностью. Остальные программы работали с микропроцессорами Intel с ядром Pentium 4.

Кстати, все три призера чемпионата были распараллелены и работали на 4-процессорных системах SMP-архитектуры на базе Opteron. Тенденция распараллеливания шахматных программ ныне должна еще более усилиться: закону Мура, возможно, приходит конец (в части, относящейся к росту тактовой частоты микропроцессоров и их производительности для нераспараллеленных программ), а потому пути повышения производительности, кроме распараллеливания, не остается.

«Шейх» — сильнейший игрок мира

Распараллеливание шахматных программ — очень сложная задача. Конечно, для них уже давно начали применяться средства обмена сообщениями типа MPI. Можно упомянуть, например, программу Zugzwang, а также Cilkchess, разработку Массачусетского технологического института, которая на чемпионате мира 1995 года работала на 1800, а в 1999-м — на 512 процессорах. Однако сами по себе эти программы по сравнению с современными были малоэффективны, да и процессоры за последние годы стали гораздо быстрее.

Интересные данные о распараллеливании современных шахматных программ на недавней телеконференции по высокопроизводительным кластерам представил Винсент Дипэвен, автор Diep3d. По его словам, эффективные шахматные алгоритмы используют общую таблицу хеширования (своеобразный кэш в оперативной памяти, чем он больше, тем, теоретически, лучше; на практике Diep3d использует кэш емкостью несколько сот мегабайт).

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

Отказ от общей таблицы хеширования очень сильно ослабляет работу шахматной программы, что не может быть скомпенсировано распараллеливанием даже на большом числе процессоров. Поэтому эффективны компьютерные архитектуры с общим полем памяти (SMP, ccNUMA) и кластеры — если их межсоединение поддерживает распределенную общую память. Это справедливо, например, для межсоединения Quadrics.

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

Знаменитый шахматный суперкомпьютер Deep Blue обрабатывал, как известно, 100 миллионов позиций в секунду, но из-за ограничений при работе с хеш-таблицей осуществлял поиск на глубину 10-12 полуходов. Сегодня такую глубину поиска можно получить на высокопроизводительных ПК. По оценке Дипэвена, глубина поиска современной шахматной программы на современном компьютере составляет до 20 полуходов (если не считать эндшпиля). Сегодня сильнейшие программы оценивают от 150 тысяч позиций в секунду (однопроцессорная версия Diep) до 1,5 миллионов позиций в секунду (Fritz) при работе на одном процессоре.

Михаил Ботвинник

Последователем Deep Blue с аппаратной точки зрения можно считать программу Hydra. Она работает на Myrinet-кластере с 16 двухпроцессорными узлами, оснащенными процессорами Intel Xeon и программируемыми процессорами, реализованными в виде плат FPGA (именно аппаратной поддержкой «шахматной игры» отличалась, как известно, и Deep Blue).

В будущем, как сообщил Дипэвен, нас ожидает знакомство с настоящим шахматным монстром, — программой Sheikh, которая также будет работать с FPGA и включать 1024 процессора. Создание такого суперкомпьютера сложно и дорого, его финансирует один из принцев их Арабских Эмиратов.

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

Другой проблемой разработки шахматных программ является отладка. Еще в старые времена, когда в СССР велась разработка программы «Пионер» (руководил этим коллективом многолетний чемпион мира Михаил Ботвинник), программисты жало?вались на проблемы отладки. И сегодня далеко не все версии шахматных программ достаточно хорошо отлажены, поэтому они могут допускать ошибки. Однако не надо забывать, что человек также склонен к ошибкам — скажем, по причине усталости. Такого источника ошибок у компьютера быть не может (сбой теоретически может быть, но даже если забыть о его низкой вероятности, можно ведь устроить и отказоустойчивую конфигурацию).

А что же искусственный интеллект? Да, игра в шахматы — классическая область приложения методов искусственного интеллекта, в которой применяется много эвристических алгоритмов для организации эффективного поиска наилучшего хода. Это реализуется, большей частью, с помощью метода «грубой силы», используя высокую производительность компьютеров и распараллеливание при эффективной организации переборной задачи. Возможно, в широких массах ждали несколько иной реализации искусственного интеллекта — с процессом принятия решения, напоминающим человеческий подход, самообучение и проч. Да, некоторые программы действительно являются более простыми — например, та же Hydra, играющая в атакующем стиле и не имеющая «человеческого» понимания позиционной игры. Но Fritz 8, например, может комментировать выбор хода вполне человеческими терминами, например, «занятие открытой линии».