создать компьютеру проблемы».
Понедельник, 15 августа. Утром перед первой партией Шеффер с Тинсли встретились и вместе отправились к месту проведения чемпионата, находившемуся в четверти часа ходьбы, – точно два идущих в салун враждующих ковбоя, готовых выстрелить друг в друга в любой момент. По дороге они разговаривали. Тинсли рассказал Шефферу, что с ним произошло накануне ночью.
«Прошлой ночью мне приснился сон, – сказал Тинсли. – Господь сказал мне, что тебя он тоже любит».
Шеффер в растерянности молчал.
«Так вот, – сказал Тинсли, – меня это очень волнует».
Они вошли в музей и направились в игровой зал, в котором почти никого не было, кроме кучки журналистов и зрителей. Здесь они уселись на офисные стулья за небольшим столом у неоштукатуренной кирпичной стены. Игровую зону обрамляли баннеры с брендом Silicon Graphics и надписью «Чемпионат мира по шашкам». Монитор, за которым работал Шеффер, угрожающе громоздился на столе. Игра началась, однако до золотых заготовок дело не дошло. Первая и вторая партии были сыграны вничью. Третья и четвертая оказались «легкими ничьими». Пятая – «скучной ничьей». Шестая партия – ничья. День закончился, а кровь так и не пролилась.
Следующий день соревнований выпал на среду 17 августа. Проекту Chinook было уже почти пять с половиной лет. Тинсли снова занял свое место на офисном стуле за маленьким столом, посмотрел в сторону Шеффера и сказал, что у него что-то с желудком. А также спросил, нельзя ли поручить кому-нибудь другому сыграть остаток матча за него. Удивленный Шеффер не мог понять, почему проблема с желудком должна нарушить ход чемпионата. Он предложил проконсультироваться у врача. В итоге они отправились в Массачусетскую больницу. Тинсли сказал, что если его дела плохи – как говорится, действительно плохи, – то пусть Шеффер свяжется с его сестрой Мэри, той самой, из-за которой он когда-то страдал, считая ее любимицей родителей. Тинсли добавил, что «готов уйти». Доктор дал ему маалокс и тайленол и направил на рентген. Результаты должны были сообщить утром.
В четверг 18 августа Шеффер проснулся рано и позвонил Тинсли – узнать, не смогут ли они снова пойти на чемпионат вместе, и заодно спросить, как у того дела с желудком.
«Я снимаюсь с матча и уступаю титул Chinook», – ответил Тинсли. Шеффер уронил голову на гостиничную подушку и заплакал.
Рентген выявил у Тинсли опухоль поджелудочной железы. Проведенная через несколько дней биопсия показала, что это рак. Тинсли уехал из Бостона и начал химиотерапию. Chinook осталась и закончила матч против Дона Лафферти, срочно заменившего Тинсли. 25 августа 1994 года перед группой зрителей, включавшей менее 20 человек, Шеффер и команда Chinook получили приз как представители машины-победителя чемпионата мира по шашкам между человеком и машиной.
Тинсли умер 3 апреля 1995 года. Его похоронили в Колумбусе, штат Огайо, а на надгробии выгравировали шашечную доску с позициями из его партии с Chinook. А еще на нем выгравировали слова из Послания к Евреям (13:1): «Братолюбие между вами да пребывает»[10].
Шеффер после смерти Тинсли утратил интерес к турнирам. Во время последней соревновательной партии Chinook, проводившейся в ноябре 1996 года, ее оператором была жена Шеффера Стеф. Собирая Ребекку в школу полвосьмого утра, она отправляла по сети из своего дома в Эдмонтоне ходы на турнир по шашкам в Вирджинии.
Слово «решение» имеет специфический смысл, когда речь идет о математике игр. По существу, оно означает, что вы можете играть как бог – знать (и уметь математически доказать, что знаете) оптимальные ходы, оптимальные ответные ходы, оптимальные ответные ходы на эти ответные ходы и так далее – до конца партии. К тому же, если вы решили игру, то знаете, причем с математической достоверностью, как завершится конкретный матч.
Например, крестики-нолики – решенная игра. Можно задать любой вариант на поле и довольно легко доказать, что определенный ход является наилучшим. Разумеется, при оптимальной игре партия в крестики-нолики гарантированно заканчивается ничьей. Игра четыре в ряд была решена двумя исследователями (независимо друг от друга) в 1988 году, один из которых работал в Маастрихтском университете на том же этаже, что и Шеффер. При оптимальной игре партия четыре в ряд заканчивается гарантированной победой того, кто ходит первым. Иными словами, вы можете обыграть бога, если пойдете первым. Оваре, игра из семейства манкала, а также «мельница», старинная стратегическая игра, тоже решены – обе дают гарантированную ничью.
А вот шахматы не решены. Хотя лучшие современные шахматные программы несравнимо сильнее мастеров, даже самая продвинутая из них не может гарантировать победу или хотя бы ничью в партии с богом. Поэтому мы не знаем, какой результат принесет идеально разыгранная шахматная партия, хотя многие полагают, что это должна быть ничья. Взять верх над богом – трудная задача. В 1967 году математик Ханс-Йоахим Бремерманн утверждал, что «ни один компьютер, как бы он ни был сконструирован, никогда не сможет исследовать все дерево возможных последовательностей ходов игры в шахматы».
Хотя Шеффер после смерти Тинсли отошел от соревнований, он не отключил свои машины, которые продолжали работать в поисках окончательного решения шашек. Кое-чего на этом пути он уже добился – у него была полная база эндшпилей. Если на доске оставалось не более восьми шашек, Chinook всегда с математической достоверностью знала, какие ходы являются оптимальными и как закончится игра. Однако расширение этих баз данных для девяти, 10 и, в конечном итоге, для исходных 24 шашек за счет простого наращивания ресурсов было невозможно. По прикидкам Шеффера, при оптимистичных уровнях сжатия данных объем полной базы всех позиций в шашках составил бы один миллиард гигабайт. В то время стоимость хранилища такого размера превышала миллиард долларов. (Даже сегодня, при куда более совершенном оборудовании, хранилище обошлось бы примерно в $20 млн.)
Решение для шашек нужно было искать другим, сравнительно недорогим креативным способом, позволяющим сокращать необходимый объем исходных данных. Представьте себе партию в шашки – то есть любую возможную партию в шашки – как гигантский рожок мороженого. На дне находится одна точка – количество возможных позиций при полном отсутствии шашек на доске, равное нулю. Вверху – широкая горловина, где количество возможных позиций, когда по краям доски располагаются по 12 шашек, равно
