Эта странная математика. На краю бесконечности и за ним - Дэвид Дарлинг

С появлением в 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, теоретики бессильны: в начале игры они не имеют ни малейшего представления о том, кто победит. Есть позиции (они довольно часто возникают в партиях между опытными соперниками) заведомо проигрышные для ходящего игрока – любой его ход гарантированно ведет к провалу. Непонятно лишь, как именно должен в такой ситуации действовать второй участник, чтобы победить, – хотя то, что победить он может, известно точно. Это пример того, что в математике называется “неконструктивным доказательством”: оно доказывает, что нечто (например, выигрышная стратегия) существует, а вот как конкретно это нечто получить, совершенно не подсказывает. Кажется нелогичным: как же так, наверняка знаем, что что-то существует, но привести пример не в силах? И тем не менее в подобных играх это случается часто. Такой вот парадокс: доказать, что в определенной ситуации игрок может победить, бывает проще простого, а вот показать, как именно достичь этой победы, невозможно.

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

Пожалуй, еще удивительнее успехи, которых компьютерам удалось достичь в другой древней игре, стратегически еще более сложной, – го. Распространена она в основном в Китае, Японии и Южной Корее, а корни ее уходят глубже чем на две с половиной тысячи лет в прошлое – она считается самой старой из существующих сегодня настольных игр. В Древнем Китае игра в го входила в число четырех искусств, которыми должен был владеть благородный муж, наряду с живописью, каллиграфией и игрой на струнном музыкальном инструменте цине. На доске размером 19 × 19 соперники, играющие белыми и черными камнями, ходят по очереди, но, в отличие от шахмат, начинают черные. Делая ход, каждый из участников ставит на доску камень своего цвета, стараясь своими камнями окружить вражеские – тогда те считаются захваченными и удаляются с поля (название “го” происходит от китайского слова, означающего “игра в окружение”). Кроме этих основных правил есть и множество других, но главная особенность игры в том, что ее тактика и стратегия дьявольски сложны. Тактика – это то, что происходит в отдельно взятой части доски, где между группами камней разворачивается противоборство: выжить или погибнуть, спастись или сдаться в плен. А стратегия – это выстраивание игры с учетом общей ситуации на доске. Го превышает шахматы и по размеру поля, и по количеству возможных ходов в каждой позиции, да и партия обычно длится дольше. Метод перебора, дающий компьютерам преимущество в шахматах, к го неприменим, поскольку на просчитывание всех вариантов ушло бы слишком много времени. А в состязании с мастером го перебор просто бесполезен, ведь искусный игрок способен выбрать из множества ходов лучший, используя навыки высшего уровня, такие как распознавание образов – умение, которое приобретается с опытом и к которому человеческий мозг приспособлен гораздо лучше, чем компьютер. Распознать в расположении камней на доске определенный общий рисунок, который в различных ситуациях может выглядеть совершенно по-разному, – задача для компьютера куда более сложная, чем просто считать с молниеносной быстротой. Даже когда компьютеры стали обыгрывать сильнейших шахматистов, мастера го оставались уверенными, что в их игре компьютерам еще долго, очень долго не достичь даже скромного любительского уровня.