123

Спросите у знакомого шахматиста, кто выигрывает в шахматах — белые или чёрные. «Что за глупый вопрос, — ответит он вам — смотря кто играет за белых и за чёрных и как сложится игра.» Ну а если оба играют наилучшим образом, что тогда? Оказывается, что поставленный таким образом вопрос имеет вполне точный смысл. Правда, ответ на него неизвестен. Но можно доказать, что имеет место ровно одна из трёх возможностей: • у белых есть способ, позволяющий им гарантированно выиграть, как бы ни играли чёрные; • у чёрных есть способ, позволяющий им гарантированно выиграть, как бы ни играли белые; • у белых есть способ, позволяющий им гарантированно не проиграть (=выиграть или свести игру вничью), и одновременно у чёрных есть способ, позволяющий им гарантированно не проиграть. Чтобы доказать это, даже не надо быть шахматистом. Как мы увидим, подобные утверждения верны для большого класса игр, называемого «конечные игры с полной информацией». Мы разберём много примеров таких игр; в некоторых случаях нам удастся выяснить, какой из случаев имеет место, и даже указать наилучший способ игры (или, как говорят, стратегию)

Несколько простых примеров

Мы разобрали несколько примеров игр. В каждом из них мы указали, кто из игроков может гарантировать себе выигрыш и как для этого он должен играть. Но как до этого догадаться? Иногда это удаётся сделать, проанализировав игру «с конца». Для примера рассмотрим самую первую игру, но немного изменим условие. 11 На столе лежит 25 спичек. Играющие по очереди могут взять 1, 2 или 4 спички. Кто не может сделать ход (спичек не осталось), проигрывает. Разница в том, что брать три спички нельзя, так что правило «дополнять ход противника до пяти спичек» теперь не годится (если противник взял две). Чтобы проанализировать игру, изобразим возможные варианты (сколько осталось спичек) кружочками, а возможные ходы — стрелками. (На рисунке 1 поместились лишь небольшие количества спичек, но картинку можно продолжить влево.)

Из каждого кружочка идут три стрелки, соответствующие трём возможным ходам (прямая стрелка — взять одну спичку, кривые — взять две или четыре спички). Скажем, если у нас 9 спичек (левый кружочек), то после нашего хода может остаться 8, 7 или 5 спичек, и это изображено стрелками. Такие картинки математики называют ориентированными графами; кружочки называются вершинами графа, а стрелки — рёбрами (или дугами) графа. Будем анализировать ситуацию справа налево, глядя на картинку.

• Если к нашему ходу спичек не осталось, то мы проиграли.

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

• То же самое, если осталось две или четыре спички — мы выигрываем в один ход.

• А что будет, если нам осталось три спички? Взять все три по правилам мы не можем. Можно взять одну или две. В этом случае противнику останется две или одна, и он выиграет (взяв их на своём ходу). Поэтому три спички — проигрышная позиция (для того, чей сейчас ход).

• Про четыре спички мы уже говорили. Если осталось пять спичек, то мы можем взять две и оставить противнику три, передав ему ход в проигрышной позиции. Значит, пять спичек — выигрышная позиция.

• Если осталось шесть спичек, то можно взять одну, две или четыре. Тогда у противника будет 5, 4 или 2 спички. Все эти позиции для него выигрышные, так что шесть спичек — проигрышная позиция.

• Раз шесть спичек — проигрышная позиция, то 7, 8 и 10 — выигрышные. В самом деле, взяв 1, 2 или 4 спички, мы оставим противнику 6.

• Девять спичек — проигрышная позиция: при любом ходе противник оказывается в выигрышной позиции с 8, 7 или 5 спичками. Всё это показано на рисунке 2.

Легко сообразить, что дальше всё будет повторяться с периодом 3: позиции, где число спичек делится на 3, будут проигрышными (для того, кто в них оказался), а где не делится — выигрышными. В частности, в игре с 25 спичками, с которой мы начинали, выигрывает первый игрок. Как он должен при этом играть? Он должен ставить противника в проигрышную позицию, то есть брать столько спичек, чтобы осталось кратное трём количество. (Заметим, что при этом он может никогда не брать четыре спички, достаточно брать одну или две.)

В одной из клеток шахматной доски стоит «односторонняя ладья», которая может двигаться влево или вниз. Двое игроков ходят по очереди, сдвигая ладью влево или вниз на любое число клеток (но не менее одной); кто не может сделать ход, проигрывает. 7 Здесь удобно записывать буквы В и П (для выигрышных и проигрышных позиций) прямо на доске. Позиция в левом нижнем углу проигрышная (наша очередь хода, а ходить некуда). Остальные позиции на первой горизонтали и первой вертикали выигрышные, так как из них можно подвинуть ладью в угол и поставить противника в проигрышную позицию (рис. 3).

Далее замечаем, что позиция b2 (вторая вертикаль, вторая горизонталь) проигрышная, поскольку любой ход из неё (вниз или влево) даёт противнику выигрышную позицию. А другие позиции на этой горизонтали и этой вертикали выигрышные, так как из них можно перевести ладью на b2 (рис. 4).

Далее всё повторяется: позиция c3 (третья вертикаль, третья горизонталь) проигрышная, так как любой ход (вниз или влево) ведёт к выигрышной для противника позиции. Остальные позиции на этой горизонтали и этой вертикали выигрышные. Позиция d4 снова проигрышная, остальные выигрышные, и так далее (рис. 5).

Приходим к следующему результату. Если ладья стоит на диагонали, то выигрывает второй. Для этого он должен возвращать ладью на диагональ, когда первый её сдвигает с диагонали. Если же ладья не стоит на диагонали, то выигрывает первый — для этого первым ходом он должен поставить ладью на диагональ, а потом возвращать её туда. Наверно, вы уже заметили, что эта игра по существу совпадает с одной из уже рассмотренных — а именно, игрой с двумя кучками спичек. Позиция (𝑚, 𝑛) (в одной кучке 𝑚 спичек, а в другой 𝑛) соответствует клетке в 𝑚-ой вертикали и 𝑛-ой горизонтали (если начинать счёт с нуля), см. рис. 6. Математики сказали бы, что эти две игры изоморфны

Взятие спичек из одной кучи уменьшает первую координату и сдвигает ладью влево; взятие спичек из другой кучи сдвигает ладью вниз. В угловой клетке (0, 0) ладья не может сделать хода (спичек не осталось ни в одной из кучек). Чтобы выиграть, надо возвращать ладью на диагональ; на языке спичек — уравнивать число спичек в обеих кучках (как мы и говорили).

Переходя обратно к спичкам, можно сказать так: если перед нашим ходом в обеих кучках по чётному числу спичек, то позиция проигрышная, 10 а если хотя бы в одной позиции нечётное — то выигрышная, и ходить надо так, чтобы противнику остались две чётные кучки