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

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

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

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

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

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

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

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

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

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