Выиграть, не зная как.

В главе 2 мы говорили об играх, в которых участники делают свои ходы поочередно и которые заканчиваются через определенное число ходов. Теоретически можно проанализировать все возможные последовательности ходов и найти оптимальную стратегию. Это сравнительно легко, когда играешь в крестики-нолики, и невозможно (во всяком случае пока) в шахматах. В игре, о которой пойдет речь, оптимальная стратегия неизвестна. Тем не менее, даже не зная, к чему сводится оптимальная стратегия, можно утверждать: эта стратегия обеспечит победу игроку, сделавшему первый ход.

ZECK – игра в точки с участием двух игроков. Цель каждого игрока – заставить соперника удалить последнюю точку. Игра начинается с расположения точек в форме прямоугольника любого размера, скажем 7 × 4:

Когда наступает очередь одного из игроков делать ход, он удаляет одну точку, а вместе с ней и все остальные точки в правой верхней части прямоугольника. Если первый игрок выберет четвертую точку во втором ряду, его сопернику останутся следующие точки:

Во время каждого раунда должна быть удалена минимум одна точка. Проигрывает тот, кто удаляет последнюю точку.

В случае прямоугольника любого размера, в котором есть хотя бы две точки, у первого игрока должна быть выигрышная стратегия. Однако в текущий момент она неизвестна. Можно проанализировать все возможные ходы и найти такую стратегию для любой конкретной игры, скажем для игры с прямоугольником 7 × 4. Тем не менее оптимальная стратегия для всех возможных размеров прямоугольника с точками остается неизвестной. Как можно доказать, у кого из игроков есть выигрышная стратегия, даже зная, в чем именно она состоит?

Анализ примера.

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

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