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

Кре́стики-но́лики — логическая игра между двумя противниками на квадратном поле 3 на 3 клетки или бо́льшего размера (вплоть до «бесконечного поля»). Один из игроков играет «крестиками», второй — «ноликами». В традиционной китайской игре (Гомоку) используются черные и белые камни.

Классический вариант

Правила игры

Выигранная партия в крестики-нолики

Игроки по очереди ставят на свободные клетки поля 3х3 знаки (один всегда крестики, другой всегда нолики). Первый, выстроивший в ряд 3 своих фигуры по вертикали, горизонтали или диагонали, выигрывает. Первый ход делает игрок, ставящий крестики.

Обычно по завершении партии выигравшая сторона зачёркивает чертой свои три знака (нолика или крестика), составляющих сплошной ряд.

Анализ

Классические «крестики-нолики» на поле 3x3 не представляют никакого практического интереса (разве что для маленьких детей, как начальный этап обучения логическим играм, или в качестве несложного задания по программированию для студенческой лабораторной работы) — общеизвестен алгоритм, который при правильной игре гарантирует ничью любой стороне, а при ошибке противника позволяет выиграть. Таким образом, игра находится в состоянии «ничейной смерти».

Некоторые рациональные стратегии:

• За крестики
  • Сделать первый ход в центральное поле.
  • Противник может ответить ходом либо в угол, либо на сторону поля.
    • Если противник ответил ходом в угловое поле — сходить в ответ в противоположный угол.
      • Если противник ответил ходом на сторону — он проиграл. Следует ответить ходом в один из двух несоседних углов.
      • Чтобы не проиграть, противник должен занять один из углов. Дальнейшие ходы делаются так, чтобы блокировать построение тройки противником. — Ничья.
  • Если противник ответил ходом на сторону — он проиграл. Следует ответить ходом в один из двух несоседних углов.
    • Противник будет вынужден пойти в противоположный угол, чтобы на следующем ходу не проиграть.
    • Сходить в оставшийся пустым угол, соседний с первым ходом противника. В результате блокируется построение тройки противником, а крестики образуют треугольник — получится «вилка», позволяющая следующим ходом построить тройку двумя способами.
    • Как бы ни ответил противник, следующим ходом строится одна из троек. — Выигрыш.
• Или:
  • Сделать первый ход в угол.
  • Противник может ответить либо ходом на сторону, либо ходом в угол, либо ходом в центр.
  • Если противник ответил ходом в угол, он вновь проигрывает. Следует ответить ходом в любой из оставшихся углов.
    • Противник будет вынужден блокировать угрозу, следующим ходом нужно занять последний угол, что дает вилку. — Выигрыш.
  • Если противник ответил ходом в центр, то нужно занять угол противоположный первому углу. Противник может ответить либо ходом на сторону, либо ходом в угол.
    • Если противник ответил ходом в угол, он проиграл — следует немедленно занять другой угол, блокируя тройку противника и образуя свою вилку. — Выигрыш.
    • Если противник ответил ходом на сторону, то следующие ходы строятся так, чтобы блокировать тройки соперника — Ничья.

• За нолики.
  • Если противник сходил первым ходом в центр, ответить ходом в любой из углов, затем каждым следующим ходом блокировать возможность построения противником очередной тройки, при возможности выбора предпочитая ходы в углы. — Ничья. Или заканчивая свою тройку при удобном случае. — Выигрыш.
  • Если противник сходит первым ходом в один из углов, ответить ходом в центр. Если ответным ходом противник займёт два противоположных угла, ответить ходом на сторону. Затем каждым следующим ходом блокировать возможность построения противником очередной тройки, при возможности выбора предпочитая ходы в углы. — Ничья.
  • Если противник сходит первым ходом на сторону, ответить ходом в центр. Если противник ответил ходом в один из не соседних, своему первому ходу, углов, ответить ходом на сторону «соседнюю» с ходами противника. Далее блокировать возможность построения противником очередной тройки — Ничья.

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

Дерево игровых ситуаций

Частичное дерево игровых ситуаций для игры крестики-нолики

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

Компьютерное решение

Для решения такого рода игр на компьютере строится дерево игровых ситуаций в соответствии с методом мини-макс. Полное число узлов в таком дереве равно 255168. Это число получается как сумма всех возможных вариантов ходов — 9 вариантов на первом шаге, 8 — для каждого из 9 на втором шаге, 7 — на каждом из 72 вариантов на третьем шаге и т. д., за вычетом ситуаций досрочного окончания игры (выигрыша).

Обобщения

Более длинные линии

Можно рассматривать игру, в которой победителем считается игрок, первым построивший $n\geqslant 3$ одинаковых знаков на достаточно большом для этого прямоугольном поле. При этом можно ограничить поле каким-нибудь размером (начиная с $n\times n$), либо вовсе не ограничивать (в этом случае говорят о «бесконечном» поле)

Игра до 4 одинаковых знаков на бесконечном поле неинтересна, ибо начинающий довольно быстро строит «вилку» и выигрывает. Игра при $n\geqslant 6$ также неинтересна из-за «ничейной смерти». Существуют стратегии, не дающие противнику построить нужную линию никогда. Однако при $n=5$ игра становится намного содержательнее. Такой вариант имеет специальное название — гомоку. Изначально в гомоку играли на доске размером 19х19, позже она была уменьшена до размера в 15х15 клеток.

Основной победной тактикой при игре на бесконечном поле считается построение пересечений («вилок»), которые не дают противнику возможности блокировать все возможные пути построения пятёрки. Чтобы не проиграть, необходимо своевременно прерывать линии противника длиной в три фигуры.

Практика показала, что при равных правилах для игроков тот, кто делает первый ход, имеет преимущество, позволяющее при достаточно квалифицированной игре одержать победу. Для сохранения интереса к игре предлагались различные варианты модификации правил игры. Так, с введением фолов (запрещенных ходов) для игрока, начинающего первым — ему запрещено строить вилки 3х3, 4х4, а также построение «длинного ряда» из своих фигур — получилась новая игра под названием рэндзю, с совершенно иными стратегиями выигрыша.

Модификация поля

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

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

Возможный алгоритм для игры крестики-нолики в кубе 4x4x4:

1. Проверяем наличие своих трёх подряд стоящих фигур, если нашли, то ставим четвёртую и выходим (игра завершается).

2. Проверяем наличие трёх подряд стоящих фигур противника, если нашли, то ставим четвёртую свою и выходим.

3. Проверяем наличие своих двух подряд стоящих фигур, если нашли, то ставим третью на любую позицию в этом ряду и выходим.

4. Проверяем наличие двух подряд стоящих фигур противника, если нашли, то ставим третью свою на любую позицию в этом ряду и выходим.

5. Ищем любой ряд, имеющий три пустых клетки и одну содержащую свою фигуру и ставим на любую позицию в этом ряду свою фигуру, при чём предпочтение отдаётся наличию ряда в пространстве.

Обмен значков

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

Изменение условия выигрыша

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

Также существует вариант крестиков-ноликов Силвермэна. В нём используется игровое поле 4х4 клетки. Крестики выигрывают, если возникает ряд из 4-х одинаковых значков (крестиков или ноликов), иначе выигрывают нолики.

Удлинение хода

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

См. также

• Рэндзю
• Игра с полной информацией
• Ничейная смерть
• Hexapawn (англ.)русск.

Литература

• Гарднер М. Крестики-нолики. —М.: Мир, 1988. ISBN 5-03-001234-6.