Эта странная математика

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

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

С появлением в 1970-х и 1980-х годах более мощных компьютеров поиск оптимального хода стал более глубоким и рациональным. В 1978 году компьютер выиграл партию у международного мастера по шахматам. В том же десятилетии прошел первый чемпионат мира по шахматам среди компьютерных программ. Когда один из авторов этой книги (Дэвид) работал менеджером по прикладному программному обеспечению в компании Cray Research (производителе суперкомпьютеров в Миннеаполисе), ему довелось совместно с Робертом Хайаттом из Университета штата Алабама в Бирмингеме заниматься оптимизацией написанной Хайаттом шахматной программы Blitz для компьютера Cray-1 – самого быстродействующего на тот момент на планете. В 1981 году Cray Blitz стал первым компьютером, получившим мастерский рейтинг после победы в чемпионате штата Миссисипи со счетом 5:0, а в 1983-м он побил своего давнего конкурента, компьютер Belle компании Bell Labs, и стал чемпионом мира по шахматам среди компьютеров.

С того времени компьютерные шахматы сделали огромный шаг вперед. В 1997 году чемпион мира по шахматам Гарри Каспаров в матче из шести партий проиграл компьютеру Deep Blue компании IBM, а последний раз человек одержал победу над сильнейшим в мире компьютерным соперником в 2005 году. Лучшие компьютеры сейчас настолько опережают по рейтингу живых шахматистов, что можно уверенно утверждать: человеку больше никогда не обыграть ни одного из кремниевых гроссмейстеров. На момент написания этой книги наивысший шахматный рейтинг (основанный преимущественно на турнирных победах над достойными соперниками), когда-либо достигнутый углеродной формой жизни, составляет 2882 пункта. Этот рекорд, зафиксированный в мае 2014 года, принадлежит действующему чемпиону мира по шахматам норвежцу Магнусу Карлсену. На сегодняшний день его уже обошли не меньше пятидесяти компьютерных программ, в том числе Stockfish, имеющая самый высокий на планете рейтинг среди людей и машин – 3394 пункта.

Шахматная доска дома у Агниджо. На доске – позиция, возникшая в ходе игры между компьютером Deep Blue (белые) и Гарри Каспаровым (черные) в 1996 году, когда компьютер впервые превзошел чемпиона мира по шахматам.