Крестики-нолики

Итак, самая простая игра - крестики-нолики на доске 3*3. Партнеры гто очереди ставят на поля квадрата (доски) крестики и нолики, и выигрывает тот, кто первым выстроит три своих знака в ряд. Разумеется, игра длится не более девяти ходов. Если никому из игроков не удается добиться цели, партия заканчивается вничью.

Интересно, что даже на таком простом примере можно проиллюстрировать многие важные понятия математической теории игр. Игра "3 в ряд" относится к категории конечных, детерминированных, переборных, стратегических игр двух лиц с полной информацией. Будем обозначать вершинами (точками) возникающие в процессе игры "позиции" (расположения крестиков и ноликов). Пусть начинают крестики. Соединим начальную вершину (пустая доска) с теми девятью, которые отвечают первому ходу крестиков. Каждую из них соединим с восемью вершинами, отвечающими ходам ноликов, и т. д. В результате мы получаем дерево игры (дерево перебора). Начальная вершина - корень дерева, максимальная длина ветви (глубина перебора) в данном случае равна девяти. Проанализировав дерево при помощи так называемой минимаксной процедуры, мы математически точно определим, как должна закончиться партия при наилучших действиях обеих сторон.

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

Рис. 60

Конечно, для анализа крестиков-ноликов "3 в ряд" можно обойтись без специальных методов, больше часа он не займет. Легко обнаружить, что при правильной игре обоих партнеров партия заканчивается вничью. Ее исход решается уже на первом ходу. У крестиков три принципиальных начала - занять угол, центр или боковую клетку доски. Самый опасный дебют крестиков - в угловую клетку (a1 на рис. 60). Из восьми возможных ответов правильным для ноликов является лишь ход в центр доски. После этого ничья достигается без труда. Предположим, что нолики сыграли иначе: на a1 ответили b1. Тогда следует а3, единственный ответ а2, на что решает с3 с вилкой, то есть с двойной угрозой b2 или b3 (рис. 60 а). Следующим ходом крестики ставят третий знак и выигрывают. Вилкой заканчивается партия и в других вариантах.

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

Читатель может удивиться, почему мы вдруг снова вернулись к словесным играм, ведь их место совсем в другой главе? Но в том-то и дело, что данная словесная игра принципиально не отличается от обычных крестиков-ноликов! Составим следующую таблицу:

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

Таким образом, как говорят математики, две рассмотренные игры - крестики-нолики й словесная - изоморфны, то есть между их правилами можйо установить такое соответствие, что игры ничем не будут отличаться друг от друга. Изоморфизм - очень важное математическое понятие, позволяющее при изучении одних объектов переходить к другим, уже исследованным.

Добавим теперь к обычной доске 3*3 всего одно поле - d1 (рис. 60 б). Чем завершится игра в этом случае? На такой доске крестики быстро одерживают победу. Решает ход c1. Если нолики не играют b2, то, как мы знаем, они проигрывают на обычной доске 3*3 (дело обойдется без дополнительного поля). Если же они займут поле b2, то после b1 неизбежен следующий ход крестиков на a1 или d1 (рис. 60 б).

Итак, существует доска из 10 полей, на которой крестики форсированно одерживают победу. Но это не рекорд.

На доске из семи клеток, представляющей собой два ряда 4*1, пересекающиеся в одной из своих внутренних клеток (рис. 60 в), выигрыш достигается уже на третьем ходу. Первый крестик ставится на пересечении рядов, второй - на одно из соседних внутренних полей, после чего нолики беззащитны. Нетрудно убедиться, что, какова бы ни была доска с числом клеток, меньшим семи, результат игры будет ничейный.

Вернемся к крестикам-ноликам на доске 3*3. Кажется забавным, но на ней можно играть в поддавки! Тому, кто первым выставит ряд из трех своих знаков, засчитывается поражение. В отличие от "прямой" игры в "обратной" инициатива принадлежит ноликам. Впрочем, у крестиков имеется надежная ничейная стратегия на первом ходу они должны занять центр и далее симметрично повторять ходы партнера.

Следующий вариант крестиков-ноликов свидетельствует о том, что даже такая маленькая доска, как 3X3, может служить неиссякаемым источником для изобретателей игр. От обычных правил отличие только в том, что каждый игрок при своем ходе может по желанию поставить либо крестик, либо нолик. Побеждает тот, кто первым закончит ряд из трех одинаковых знаков, причем безразлично каких.

Рис. 61

В обычной игре, да и в поддавках, если партнеры не делают грубых ошибок, партия заканчивается вничью. В данном же варианте побеждает начинающий. Первым ходом он занимает центр, поле b2, например, как обычно, ставит на нем крестик (рис. 61а). Второй игрок может занять либо угловое поле, либо лежащее на стороне доски, и, чтобы не проиграть сразу, он должен поставить нолик. Если выбрано угловое поле a1, то первый игрок рисует нолик в противоположной вершине с3, и куда бы теперь противник ни поставил крестик или нолик, он своим следующим ходом заканчивает соответственно ряд из крестиков или ноликов. Если второй игрок занимает первым ходом боковое поле а2, то первый ставит нолик на одной линии с двумя имеющимися знаками, то есть на поле с2. У второго игрока нет ничего лучшего, чем поставить еще один нолик на b1, и после ответного, четвертого нолика на b3 он вынужден сдаться (рис. 61 а).

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

Как и в предыдущей игре, право первого хода является здесь решающим. Начинающий должен поставить свой крестик в центр доски. Если теперь нолик поставлен в углу, например, на поле а3, то первый игрок ставит крестик на b1. Ответ вынужден - b3. На это следует с3, ответ опять единственный - а1. Дебют партии закончен (рис.61 б). Двумя следующими ходами первый игрок переставляет крестики с b2 на с2 и с b1 на c1 и выигрывает партию. Если на первом ходу второй игрок займет боковое поле, например b3, то первый играет a1, второй отвечает с3, тогда первый идет а3, а противник а2. Все знаки выставлены, теперь первый игрок переставляет крестик с a1 сначала на b1, а затем на c1 и берет верх.

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

Конечно, в последней игре вместо крестиков и ноликов удобнее пользоваться белыми и черными шашками. Эту игру можно рассматривать как вступление в класс игр, представляющих собой гибрид крестиков-ноликов и шашек. На доске 4*4 такая игра называется так-тикль. Здесь каждая сторона имеет по четыре шашки (рис. 61 в). Игроки по очереди передвигают их на одну клетку по вертикали и горизонтали, и кто первым расположит три шашки в ряд, тот и выигрывает.

Вот примерная партия в так-тикль: 1. с1-с2 d1 - с1. 2 b4-b3 b1-b2 3. b3-а3 (грозило 3... а4-а3) 3... а4-b4 4. a1-b1 с выигрышем, так как черные не могут воспрепятствовать маневру 5. d4-d3. С помощью ЭВМ доказано, что игра так-тикль ничейная, то есть при точной игре ни одному из партнеров не удается поставить три шашки в ряд.

Рис. 62

Дальнейшим обобщением двух последних игр является "мельница", одна из самых древних в истории человечества игр. На рис. 62 изображено несколько "мельниц". Первоначальная форма доски (а) до сих пор остается самой популярной. В этом варианте, называемом простой мельницей, у каждой стороны по девять шашек. В мельнице-улитке (б) число шашек увеличивается до 12, а в шестиугольной (в) у противников по 13 шашек.

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

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

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

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

Игра болотуду, несколько напоминающая мельницу, ведется на прямоугольной доске 6*5. У каждого из партнеров 12 шашек. Они по очереди выставляют их на доску (за один ход ставятся сразу две шашки). В отличие от мельницы здесь запрещается ставить три в ряд, и дебют развивается более спокойно. Второй этап тот же, что и в мельнице. Шашки передвигаются по вертикалям и горизонталям, и при построении трех в ряд снимается одна шашка противника - та, которая примыкает к этой тройке слева или справа. Одной и той же тройкой разрешается пользоваться сколько угодно раз. Если у игрока осталось две шашки, партия в болотуду заканчивается его поражением. Третий "мельничный" этап в игре отсутствует. При повторении ходов партия признается ничейной.

В классических крестиках-ноликах, как только один из партнеров завершит ряд из трех знаков, партия сразу кончается. И в других вариантах игры доска часто используется, так сказать, с маленьким КПД. Для тех, кто сочтет это слишком скучным, придумана иная игра. На доске 6*6 партнеры по-прежнему по очереди ставят свои знаки (или шашки) и за образование тройки по вертикали или горизонтали всякий раз получают по очку. Каждое поле доски учитывается лишь дважды - по вертикали и по горизонтали. Выигрывает тот, кто наберет больше очков. В данном случае игра завершается при полном заполнении доски.

До сих пор рассматривались крестики-нолики на плоских досках, однако известно немало вариантов и трехмерных игр. Простейшим обобщением служит игра на кубе 3*3*3. Игроки по очереди отмечают по одному кубику 1*1, и выигрывает снова тот, кто первым поставит три своих знака вдоль одной прямой. Стоит ли говорить, что начинающий побеждает здесь без всякого труда. Любопытно, что в объемной игре в отличие от плоской ничьей вообще не может быть, даже если обе стороны стремятся к этому. Действительно, если в кубе 3*3*3 отметить 14 любых единичных кубиков (именно столько ходов имеется у крестиков в процессе игры), то хотя бы один вертикальный, горизонтальный или диагональный ряд будет состоять целиком из крестиков.

Намного интереснее игра на кубической доске 3*3*3, в которой выигрывает тот, кто первым занимает два пересекающихся ряда. Кубик, стоящий на пересечении двух таких рядов, разрешается отмечать лишь в последнюю очередь. Поскольку занятие центра куба приводит к простой победе, этот ход можно делать только в двух случаях: если он победно завершает игру или мешает противнику выиграть следующим ходом.