Адам Кучарски - Идеальная ставка

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

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

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

Последний раз Chinook участвовала в соревнованиях в 1996 году. Но Шеффер и его команда не отправили чемпионку на пенсию. Вместо этого они засадили ее за работу по созданию беспроигрышной шашечной стратегии, свободной от влияния действий противника. Результаты были обнародованы в 2007 году в публикации ученых Университета Альберты, озаглавленной «Тайна шашек раскрыта».

В играх, подобных шашкам, существует три типа решений. «Сильные решения» – наиболее детальные и структурированные; опытный игрок может реализовать их, вступив в игру на любом ее этапе, даже если ранее сделанные ходы были неверными. Это означает, что при сильном решении оптимальная стратегия известна всегда, независимо от стартовой позиции. Несмотря на то что для решений этого типа требуется значительное количество расчетов, для относительно простых игр, таких как крестики-нолики и «четыре в ряд», они уже найдены.

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

Наконец, самый простой тип представлен «ультраслабыми решениями», описывающими исход игры при оптимальных действиях сторон, но не сами эти действия. Например, зная, что для крестиков-ноликов и «четыре в ряд» сильные решения найдены, Джон Нэш в 1949 году доказал: в случае, когда любая игра типа «поставь-сколько-нибудь-в-ряд» разыгрывается идеально, тот, кто ходит вторым, никогда не выигрывает. Даже в отсутствие оптимальной стратегии справедливость этого утверждения может быть доказана, выражаясь языком математики, от противного: допустив, что оно неверно, мы вслед за ошибочными предположениями заходим в логический тупик. Предположим, что при идеальной игре для второго участника существует выигрышная последовательность ходов. Первый игрок может обратить эту ситуацию в свою пользу: он делает первый ход случайным образом, дожидается ответного хода оппонента, а затем «крадет» его выигрышную стратегию. По сути, в этом случае первый игрок превращается во второго, а метод «кражи стратегии» работает потому, что наугад поставленная на игровое поле первая фишка лишь увеличивает шансы первого игрока на победу.

Присвоив выигрышную стратегию второго игрока, первый одержит победу. Но вначале мы предположили, что выигрышной стратегией обладал второй игрок. Получается, что побеждают оба игрока, а это уже явное противоречие. Значит, единственный логически безупречный вывод, который следует из данной посылки, состоит в том, что второй игрок не выигрывает никогда.

Искать ультраслабые решения интересно, однако на практике они не помогают одержать верх над противником. Зато сильные решения, гарантирующие оптимальный путь к победе, найти очень трудно, особенно если игра предполагает наличие множества комбинаций ходов. Поскольку шашки в миллион раз сложнее «четырех в ряд», Шеффер и его коллеги сосредоточили свои усилия на слабых решениях.

Во время игры с Марионом Тинсли Chinook принимала решение одним из двух доступных способов. В начале игры программа делала очередной ход на основе прогноза дальнейшего развития событий. На финальных стадиях игры, когда на игральной доске оставалось меньше фигур и, следовательно, меньше возможностей для анализа, Chinook делала ход на основе анализа идеальных стратегий из своего «архива эндшпилей». Но и Тинсли великолепно разбирался в эндшпилях – не зря он был сильным игроком. Это стало очевидно в одном из его первых поединков с Chinook в 1990 году. Уже на десятом ходу программы Тинсли произнес: «Ты об этом пожалеешь». И 26 ходов спустя Chinook проиграла партию.

Перед учеными из Университета Альберты стояла задача заставить оба способа принятия решений работать сообща. В 1992 году Chinook прогнозировала лишь на 17 ходов вперед, а в ее архиве эндшпилей хранилась информация об игровых ситуациях, при которых на доске оставалось менее шести шашек. Обо всем, что происходило на доске в промежутке между этими двумя стадиями игры, программа не имела понятия.

Благодаря развитию компьютерных технологий в 2007 году Chinook научилась заглядывать далеко в будущее и собрала настолько обширный архив, что смогла вырабатывать идеальную стратегию от начала до конца игры. Это было выдающимся достижением, достойным страниц Science . Однако идеальная стратегия так бы и осталась никому не известной, если бы не матчи с Тинсли. Как позже высказался один из разработчиков Chinook , «проект мог бы умереть в 1990 году, если бы у него не нашлось достойного человека-противника».

Хотя стратегия Chinook была идеальной, Шеффер не рекомендовал использовать ее для игры с менее квалифицированным противником. Ранние матчи Chinook с участием людей показали, что отклонение от оптимальной стратегии часто приносит пользу, заставляя противника делать ошибки. Дело в том, что, в отличие от Chinook, большинство людей не способны заглядывать на несколько десятков ходов вперед. В таких играх, как шахматы и покер, где идеальной стратегии не существует, риск ошибки еще выше. И здесь мы вправе задаться важным вопросом: что происходит, когда мы применяем теорию игр к слишком сложным для полного понимания играм?