Агниджо Банерджи - Эта странная математика. На краю бесконечности и за ним

Представьте себе невероятно мощный компьютер, способный всегда, при любой ситуации на шахматной доске рассчитать лучший следующий ход. При этом “лучший” значит такой, который позволяет как можно быстрее выиграть или как минимум не проиграть – другими словами, ведет к оптимальному для участника исходу. Теперь вообразите, что этот компьютер играет против другого, идентичного ему во всех отношениях. Который из них победит? Или всегда будет ничья? Мы решили так много монументальных проблем в математике, что, казалось бы, такая древняя игра, как шахматы, с ее несложными правилами не должна представлять никакой трудности для теоретиков, вооруженных передовыми компьютерными технологиями. Но не тут-то было.

Первая машина для игры в шахматы, известная под названием “Турок”, была на самом деле ловким фокусом, бутафорией, хотя на эту мистификацию и клюнуло немало народу в период с 1770 года, когда машина была представлена публике венгерским изобретателем Вольфгангом фон Кемпеленом, по 1854 год, когда она сгорела во время пожара. Среди наблюдавших ее в действии – Наполеон Бонапарт (сам незаурядный математик), Бенджамин Франклин и один из пионеров современной вычислительной техники Чарльз Бэббидж. Машина представляла собой большой деревянный ящик, за которым располагались голова и туловище манекена в натуральную величину в богато украшенном османском одеянии и тюрбане. Через три открывающиеся дверцы на передней стороне ящика можно было рассмотреть различные детали сложного механизма, а когда поочередно открывались дверцы в задней части ящика, зрители могли видеть механизм насквозь. Постоянно скрытой от их взора оставалась лишь одна мелочь – находившийся внутри живой человек, опытный шахматист, передвигавшийся на скользящем сиденье из одной части ящика в другую, пока демонстратор одну за другой открывал смотровые дверцы. Обдумав очередной ответный ход, спрятанный шахматист передвигал фигуры на видимой зрителям доске с помощью механической руки “Турка”, соединенной посредством системы тросиков и шарниров со скрытой внутри ящика второй шахматной доской, с отверстиями для фигур. Оригинальный, превосходной работы автомат фон Кемпелена в игре тем не менее полностью полагался на интеллект управлявшего им человека.

Никакое механическое чудо, никакая самая слаженная система шестеренок, передач, рычагов и тросиков не обладает достаточным быстродействием, чтобы сыграть даже посредственную партию в шахматы – настолько сложна эта игра. Надежда на создание реальной шахматной машины появилась только после окончания Второй мировой войны, когда был разработан электронный компьютер. Пионеров машинных вычислений – таких как Алан Тьюринг, Джон фон Нейман, Клод Шеннон – шахматы интересовали как средство практической проверки своих идей в области искусственного интеллекта. В своей эпохальной статье 1950 года Шеннон пишет: “Хотя никакой практической ценности в этом и нет, вопрос все же представляет определенный теоретический интерес, и есть надежда, что… решение этой проблемы послужит толчком к решению других, более важных задач”. Два года спустя коллега Тьюринга Дитрих Принц написал для нового компьютера Ferranti Mark I в Манчестерском университете первую программу для игры в шахматы. Объем оперативной памяти и производительность машины позволяли ей решать лишь задачи категории “мат в два хода”, то есть она могла рассчитать лучший ход в ситуации, когда до мата оставалось не больше двух ходов. В 1956 году компьютер MANIAC I в Лос-Аламосской национальной лаборатории был запрограммирован на игру в облегченную версию шахмат – без слонов на доске размером 6 × 6 клеток. Всего было сыграно три “бесслоновых” партии: первую компьютер сыграл против самого себя, вторую против сильного шахматиста, исходно отказавшегося от ферзя, дав фору машине (та проиграла), и третью против новичка, только что выучившего правила. Эта заключительная партия, выигранная компьютером, пусть и у очень слабого соперника, знаменовала собой первую победу машины над человеком.

В 1958 году исследователь из IBM Алекс Бернстайн написал первую программу для игры в стандартные шахматы для IBM 704 – компьютера, на котором были разработаны языки программирования Fortran и Lisp и впервые синтезирована человеческая речь. Именно под впечатлением от демонстрации синтеза речи этой машиной Артур Кларк через несколько лет написал сцену для фильма “2001 год: Космическая одиссея”, показывающую, как постепенно угасает сознание компьютера HAL 9000 , когда Дейв Боумен один за другим отключает его модули личности. В одной из предыдущих сцен фильма HAL легко выигрывает у астронавта Фрэнка Пула партию в шахматы. Режиссер Стэнли Кубрик сам был страстным шахматистом, поэтому неудивительно, что ходы HAL и Пула были взяты им из реальной партии между А. Рёшем и В. Шлаге, сыгранной в 1910 году в Гамбурге.

Проблема, стоящая перед любой машиной для состязания в шахматы – невероятная сложность игры, связанная с выработкой стратегии и многообразием возможных ходов. Существует в общей сложности около 10 46возможных позиций, а уникальных партий – не меньше 10 120(это число Шеннона, названное в честь американского математика Клода Шеннона, который описал его вычисление в опубликованной в 1950 году статье “Программирование компьютера для игры в шахматы”). В начале партии все довольно просто: у белых есть только двадцать возможных ходов – шестнадцать пешками (самых популярных всего три) и четыре конями (из них распространен всего один). Но по ходу игры, когда вовлеченными оказываются и другие фигуры – слоны, ладьи, ферзь и король, – количество возможных ходов очень быстро растет. После того как каждый из игроков сделал по одному ходу, на доске может возникнуть 400 различных позиций, после двух ходов – 72 084 позиции, после трех – более 9 миллионов, а после четвертого хода – более 288 миллиардов. Это примерно по одной игровой позиции на каждую из звезд нашей галактики. А общее количество возможных партий во много раз превышает число элементарных частиц во Вселенной.

На заре компьютерных шахмат созданию эффективных программ мешала относительно низкая производительность вычислительных машин. Но основной принцип программирования сильного компьютерного шахматиста был выработан уже в 1950-х годах венгерско-американским математиком Джоном фон Нейманом. Алгоритм “минимакс” был назван так потому, что его цель – свести к минимуму счет противника, максимизируя при этом свой собственный. К концу десятилетия этот алгоритм удалось усовершенствовать с помощью метода, получившего название “альфа-бета-отсечение”. Используя эвристические правила, выведенные на основе игровой стратегии лучших шахматистов мира, он при поиске оптимального хода заранее отсекает возможные неудачные ходы, чтобы компьютер не тратил зря время на проверку заведомо бесплодных ветвей своего дерева поиска. Это не то же самое, что компьютер, который учится на собственных ошибках, – такие появились позже, – а лишь попытка учесть в программе приемы и комбинации ходов, использовавшиеся гроссмейстерами в реальных играх.