Идеальная ставка

Чтобы не потеряться в этом бескрайнем море возможностей, разработчики Chinook последовали правилу минимакса и принялись искать наименее затратные стратегии. В каждый момент игры у Chinook было несколько вариантов возможных ходов. Выбор любого из них, в свою очередь, давал новый набор вариантов. По мере продолжения игры программа «обрезала» древо решений, удаляя слабые ветви, которые вели к проигрышу, и детально анализируя более сильные, потенциально выигрышные ходы.

Программа содержала в себе несколько скрытых трюков, предназначенных специально для игры с людьми. Когда Chinook распознавала стратегию, которая с идеальным компьютерным соперником вела к ничьей, она не всегда ее игнорировала. Если ничья располагалась в конце длинного, разветвленного древа решений, существовал шанс, что человек где-то ошибется. В отличие от многих других подобных программ, Chinook часто выбирала стратегии «с защитой от человека», предпочитая их стратегиям, более подходящим с точки зрения теории игр.

Chinook пришла в большой спорт в 1990 году, заняв второе место на Национальном чемпионате США по шашкам. Это означало, что программа получала доступ к участию в мировом первенстве, однако Американская федерация шашек и Английская ассоциация шашек были против того, чтобы компьютер соревновался с людьми. К счастью, Тинсли не разделял их взглядов. После нескольких проведенных в 1990 году неофициальных игр он понял, что ему импонирует агрессивный стиль Chinook. Соперники-люди пытались добиться от Тинсли ничьей, но программа не боялась рисковать и стремилась к победе. Тинсли так хотелось сразиться с ней на официальных соревнованиях, что он отказался от чемпионского титула, и организаторам пришлось скрепя сердце допустить компьютер до участия в турнире. В 1992 году Chinook сыграл против Тинсли в мировом чемпионате «Человек против машины». Из 39 игр Тинсли выиграл четыре, программа – две, остальные партии окончились ничьей.

Несмотря на достойное сопротивление, которое Chinook оказала Тинсли, Шеффер и его команда не собирались останавливаться на достигнутом. Они мечтали сделать Chinook непобедимой. Эффективность программы зависела от детального прогнозирования, что делало ее игроком сильным, но по-прежнему уязвимым перед лицом случайности. Сумев убрать из программы элемент удачи, разработчики получили бы идеального шашиста.

Может показаться странным, что в шашках требуется удача. Если в каждой партии делать одни и те же ходы, она будет заканчиваться одним и тем же результатом. Говоря математическим языком, это детерминированная игра, и, в отличие от покера, фактор случайности не имеет в ней значения. Тем не менее результат матча зависел только от действий Chinook, а это означало, что программу можно обыграть. Теоретически ее мог победить даже неопытный противник.

Чтобы понять почему, снова обратимся к исследованиям Эмиля Бореля. Помимо теории игр, он изучал крайне маловероятные события. Чтобы показать, что даже почти невозможные события обязательно произойдут, если подождать достаточно долго, он сформулировал теорему о бесконечных обезьянах. Основывалась она на простом предположении: допустим, обезьяна случайным образом ударяет по клавишам пишущей машинки (но не ломая ее, как это случилось в Университете Плимута в 2003 году, когда команда ученых решила проверить теорему на практике), и занимается этим бесконечно долгое время. Рано или поздно она напечатает собрание сочинений Шекспира. Согласно теореме, в какой-то момент волей чистого случая последовательность букв, возникающих на бумаге благодаря стараниям обезьяны, сложится в 37 пьес великого английского драматурга.

Разумеется, никакая обезьяна не может жить вечно, да еще безвылазно сидя за пишущей машинкой. Так что лучше рассматривать ее как метафору случайного генератора, выдающего произвольную последовательность знаков. Так как буквы расположены хаотично, существует вероятность – хотя и очень маленькая, – что обезьяна сразу же напечатает: «Кто здесь?» – реплику, с которой начинается «Гамлет». А потом у нее случится полоса везения, и она будет нажимать на нужные буквы, пока не наберет все шекспировские пьесы. Это крайне маловероятно, но возможно. Или же обезьяна будет печатать бессмыслицу, пока ей не удастся попасть пальцем в правильные клавиши в правильном порядке. Возможно, перед этим ей придется выдавать абракадабру в течение нескольких миллиардов лет.

По отдельности взятые, все эти события почти невозможны. Но поскольку существует огромное – фактически бесконечное – множество способов, какими обезьяна может напечатать собрание сочинений Шекспира, вероятность того, что это в итоге произойдет, чрезвычайно высока. По сути, она составляет чуть ли не 100 %.