В мае человечество получило весьма поучительный урок. Гроссмейстер М. Адамс, входящий в мировую шахматную элиту (в рейтинге он среди десяти лучших), проиграл программе «Гидра» матч из шести партий практически с сухим счетом — 5,5 : 0,5. С разными программами уже сыграли многие ведущие шахматисты, но такого подавляющего преимущества не демонстрировала еще ни одна из них. Так в чем же дело?
Отвечая на этот вопрос, оставим в стороне влияние выбора компьютера для игры, программных технологий, использованных в «Гидре», а также психологические аспекты и поговорим об алгоритмических особенностях или о связи математики и шахмат. Во время недавнего интервью с В.Л. Арлазаровым, членом-корреспондентом РАН, пришлось от него услышать, что «если будет социальный заказ на разработку шахматной программы, то в течение пары лет можно создать такую, которая будет обыгрывать любого шахматиста-практика». Похоже, что, опираясь на бизнес-проект «Гидра», в этом направлении уже удалось серьезно продвинуться.
Отметим основные вехи пути, приведшие к созданию и машинной реализации столь эффективного алгоритма. Профессиональный интерес математиков к шахматам проявился довольно давно и был связан с двумя направлениями: математической логикой и комбинаторикой. Первое — рассмотрение игры с точки зрения построения ее формальной модели, удобной для логического анализа на основе действующих соревновательных правил. Второе — исследование конкретных позиций или их классов в игре для достижения определенных результатов, например матовой позиции за определенное число ходов. Последнее направление породило множество изящных логико-вычислительных проблем. Некоторые из них и по сей день предлагаются на различных математических и программистских олимпиадах, а также для развлечения на досуге. Сошлемся на посвященные этим вопросам книги Л.Я. Окунева «Комбинаторные задачи на шахматной доске» (1935) и Е.Я. Гика «Математика на шахматной доске» (1976). Нужно упомянуть еще работы Мартина Гарднера, вышедшие под общим названием «Математические развлечения». В них содержатся материалы, посвященные шахматным задачам. Вот несколько примеров. Определение размера награды создателю шахматной игры потребовало от «администрации» легендарного индийского царя вычисления количества пшеничных зерен, равного числу с 20 значащими цифрами.
Задачи о шахматной доске, на которой не все поля принимаются во внимание, представляют собой алгоритмический интерес в игре, поскольку они определяют, в частности, поля внимания играющего при принятии решения о ходе, который он намерен сделать. Кроме того, вследствие изменения количества полей и формы шахматной доски появляются новые разновидности игры, например шахматы, предложенные Робертом Фишером.
Исследование геометрии шахматной доски приводит к разработке алгоритмов для известных и широко применяемых на практике интуитивных правил «квадрата», «треугольника» или «линии Троицкого», позволяющих оценить качество позиции не только на много ходов вперед, но и окончательно, как в приведенных случаях. Более того, при геометрическом анализе позиции в шахматной партии могут возникать и так называемые экстремальные задачи. Их решение помогает отыскивать мат за наименьшее количество ходов.
Если теперь обратить внимание на шахматную доску с расположенными на ней фигурами, то возникающие задачи уже будут носить явно выраженный игровой характер. Особенно тогда, когда это задачи с достаточно интересным набором фигур. К ним относятся не только случаи вроде такого, как обойти конем все поля шахматной доски, занимая каждое поле лишь один раз, но и знаменитые коллекции многофигурных эндшпилей, например упоминавшиеся в «Мире ПК», №8/05, с. 73, собрания К. Томсона и В. Налимова.
Значительная часть комбинаторных задач связана с определением числа возможных расстановок фигур на доске, что очень важно при поиске однотипных позиций, приводящих к одинаковому результату в дальнейшем течении партии.
Как известно, основной способ поиска наилучшего хода заключается в переборе возможных ходов, рассмотрении движения по дереву последовательных позиций и оценке возникающих в результате них состояний игры. Но это весьма дорогостоящий путь в том смысле, что при его прохождении играющему предъявляются непомерные требования по времени даже в случае использования компьютера. Поэтому при поиске наиболее эффективных алгоритмов в компьютерных шахматах принято учитывать как можно больше ограничений (условий), упорядочивающих перебор, т.е. позволяющих отбрасывать те позиции, которые при выборе хода рассматривать не нужно. Эти задачи представляют, как правило, трудности и для математиков, из-за чего получили распространение так называемые эвристические методы их решения. В разработку эффективных методов перебора внесли большой вклад советские математики А. Брудно и В. Арлазаров, предложившие альфа-бета процедуру и форсированный вариант, реализованные еще в шахматной программе «Каисса».
Так как борьба за уменьшение времени на «обдумывание» хода всей программой является принципиальным фактором, то математики затрачивают массу усилий на создание входящих в нее приложений (задач, решаемых при поиске нужного хода), работающих наиболее быстро, а также требующих по минимуму оперативной памяти. Так, в свое время один из авторов «Каиссы» придумал изящную реализацию нахождения сочетаний для m фигур и n мест, которые они могут занимать, что весьма важно для эффективной работы подобной программы.
Завершить короткий рассказ о связи математики и шахмат следует упоминанием имен Клода Шеннона и Михаила Ботвинника, которые внесли огромный вклад в создание математической модели шахматной игры и способствовали прогрессу в интеллектуализации программ для нее.
По существу компьютерные шахматы — едва ли не самый убедительный пример за полвека развития ИТ, когда именно в интеллектуальной деятельности автомат успешно соперничает с человеком.