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

Крестики-нолики (также известные как «икс-нолики», «икс-нокс», «XO») — логическая игра для двух игроков, относящаяся к классу нулевых игр (математических игр с нулевой суммой). Игроки размещают свои знаки — крестики (X) и нолики (O) — на сетке 3×3 поочерёдно; побеждает тот, кто первым выстроит три своих знака в горизонтальной, вертикальной или диагональной линии. Если все девять клеток заполнены и никто не собрал линию, фиксируется ничья. В кроссвордной и загадочной традиции эта игра известна под названием «крестики-нолики», а её участники в шутливой формулировке иногда именуются «игроками по сторонам света» — из-за того, что выигрышные линии проходят по трём направлениям сетки: горизонтали, вертикали и диагонали.

¶История

Происхождение игры точно не установлено. Археологические находки с сеткой 3×3 и раскопанные в Египте, датируемые приблизительно 1300 годом до н. э., свидетельствуют о том, что подобные схемы были известны ещё в Древнем мире. В Римской империи существовала игра «terni lapilli» — три камня на игральную доску, описанная в числе прочих развлечений античности. В Японии с XVI века была распространена игра «гомоку нарэ» (五目並べ), где целью было собрать пять знаков в линию на расширенном поле; крестики-нолики считаются её упрощённым вариантом.

В англоязычной традиции игра известна как tic-tac-toe (в США) и noughts and crosses (в Великобритании). Термин tic-tac-toe предположительно происходит от староанглийского tic-tac — обозначения ритмичного звука, а noughts and crosses буквально переводится как «ноли и крестики». В Германии игра называется «Tic-Tac-Toe» или «X und O», во Франции — «morpion», в Испании — «tres en raya» («три в ряд»).

¶Правила

Игровое поле представляет собой квадрат, разделённый на девять равных клеток (сетка 3×3). Первый игрок ставит крестик в любую клетку, второй — нолик. Ходы чередуются до тех пор, пока не выполнится одно из условий:

Один из игроков выстроит три одинаковых знака в ряд — по горизонтали, вертикали или диагонали.
Все девять клеток будут заняты, и линия не будет собрана — фиксируется ничья.

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

¶Математический анализ

Крестики-нолики — полностью решённая игра: при правильной игре обеих сторон исход партии всегда один и тот же. Существует 255 168 возможных партий с учётом симметрий и порядка ходов (без учёта симметрий — 26 830). Анализ показывает, что при оптимальной игре обоих участников партия всегда заканчивается вничью. Крестик, ходящий первым, может гарантировать себе ничью, а при ошибках соперника — победу; нолик при правильной игре может рассчитывать только на ничью.

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

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

¶Варианты и производные игры

На основе крестиков-ноликов создано множество усложнённых версий:

Гомоку (рэндзю) — игра на поле 15×15 или 19×19, цель — собрать пять знаков в линию; считается спортивной дисциплиной с международными соревнованиями.
Квантали (Quixo) — кубическая версия с полем 5×5, где знаки сдвигаются, а не просто ставятся.
Тёрти (Tic-Tac-Chew) и супер-крестики-нолики (Ultimate Tic-Tac-Toe) — сетка из девяти полей 3×3, где выигрыш на малом поле даёт право хода на определённом большом поле.
Крестики-нолики на торе — вариант, где края поля соединены, и линии могут «заворачивать» через границу.