Эта странная математика. На краю бесконечности и за ним - [48]

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

Проблема, стоящая перед любой машиной для состязания в шахматы – невероятная сложность игры, связанная с выработкой стратегии и многообразием возможных ходов. Существует в общей сложности около 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 году, когда компьютер впервые превзошел чемпиона мира по шахматам.

Но рейтинг рейтингом, и все же, несмотря на высочайшую квалификацию сегодняшних быстродействующих компьютеров, вопрос остается открытым: считать ли шахматы разрешимой игрой? Другими словами, возможно ли просчитать исход партии заранее, еще до ее начала? Есть множество игр попроще, где ответ на этот вопрос будет утвердительным. Одна из самых простых и популярных – крестики-нолики. Ее довольно легко проанализировать, ведь самая длинная партия продолжается не дольше девяти ходов и в большинстве случаев игрок вынужден занимать определенную клетку, чтобы не дать противнику победить. Если оба соперника знакомы с беспроигрышной стратегией, всегда все заканчивается вничью. Тот факт, что поле для крестиков-ноликов мало – всего 3 × 3 клетки, – облегчает задачу просчитывания. Впрочем, малый размер поля далеко не всегда означает, что игра проста. Многим из нас доводилось коротать время за игрой “точки и квадраты”: поле для нее представляет собой квадратную сетку с точками, а участники по очереди соединяют соседние точки отрезками. Если игрок выгораживает целую клетку, дорисовав ее четвертую сторону, клетка достается ему, он ставит в ней свой символ и получает еще один ход. Если при этом он образует еще один квадрат, то снова делает ход, и так далее. Минимальное поле для такой игры – 3 × 3. И хотя его размер такой же, как у крестиков-ноликов, стратегия здесь не в пример сложнее. Известно, что на поле 3 × 3 у второго игрока есть преимущество и он может побеждать всегда, однако мало кто знает выигрышную стратегию – а стратегия эта на удивление сложна. Большинство же из нас, по сути, полагаются на случай: мы просто стараемся сначала не отдавать противнику клетки, а потом сами стремимся занять как можно больше клеток с минимальными жертвами. А вот если поле значительно больше, чем 3 × 3, теоретики бессильны: в начале игры они не имеют ни малейшего представления о том, кто победит. Есть позиции (они довольно часто возникают в партиях между опытными соперниками) заведомо проигрышные для ходящего игрока – любой его ход гарантированно ведет к провалу. Непонятно лишь,