Крестики-нолики
Кре́стики-но́лики[1] — логическая игра между двумя противниками на квадратном поле 3 на 3 клетки или бо́льшего размера (вплоть до «бесконечного поля»). Один из игроков играет «крестиками», второй — «ноликами». В традиционной китайской игре Гомоку используются чёрные и белые камни.
Классический вариант
[править | править код]Правила игры
[править | править код]![](http://upload.wikimedia.org/wikipedia/ru/thumb/9/99/Xo_game.svg/220px-Xo_game.svg.png)
Игроки по очереди ставят на свободные клетки поля 3×3 знаки (один всегда крестики, другой всегда нолики). Первый, выстроивший в ряд 3 своих фигуры по вертикали, горизонтали или большой диагонали, выигрывает. Если игроки заполнили все 9 ячеек и оказалось, что ни в одной вертикали, горизонтали или большой диагонали нет трёх одинаковых знаков, партия считается закончившейся вничью. Первый ход делает игрок, ставящий крестики.
Обычно по завершении партии выигравшая сторона зачёркивает чертой свои три знака (нолика или крестика), составляющих сплошной ряд.
Анализ
[править | править код]Общее количество комбинаций 362 880 (чтобы удалить дубликаты комбинации, поделите на 4)
153 792 ничейных позиций 42.38%
131 184 побед первого игрока 36.15%
77 904 побед второго игрока 21.468%
Общее количество финишных позиций 958 (выигрышных, проигрышных, ничейные позиции доигрываются пока не останется свободных клеток). Без удаления дубликатов при вращении игрового поля
626 побед первого игрока 65.34%
316 побед второго игрока 32.98%
16 ничейных позиций 1.67%
Количество комбинаций с алгоритмом который на половину играет как человек. Если компьютер видит два крестика или нолика третий не даст поставить.
Общее количество 23 488
16 064 ничейных позиций 68.39%
5536 побед первого игрока 23.57%
1888 побед второго игрока 8.038%
Для каждой из сторон общеизвестны алгоритмы, которые гарантируют ничью при любой игре противника, а при его ошибке позволяют выиграть. Таким образом, игра находится в состоянии «ничейной смерти».
Ниже приведены некоторые из таких стратегий. Считается, что игрок всегда соблюдает два правила, имеющие приоритет над всеми остальными:
- Правило 1. Если игрок может немедленно выиграть, он это делает.
- Правило 2. Если игрок не может немедленно выиграть, но его противник мог бы немедленно выиграть, сделав ход в какую-то клетку, игрок сам делает ход в эту клетку, предотвращая немедленный проигрыш.
За крестики
[править | править код]Первый ход сделать в центр. Остальные ходы, если неприменимы правила 1—2, делаются в тот из свободных углов, который дальше всего от предыдущего хода ноликов, а если и это невозможно — в любую клетку.
Х | ||
O |
Докажем, что эта стратегия приводит к победе или ничьей. Если нолик пойдёт на сторону, то позиция (с точностью до симметрии) окажется такова:
О | ||
Х | ||
Х |
После чего правила 1 и 2 приведут к позиции:
Х | О | О |
Х | ||
Х |
Выигрыш.
Если же нолик пойдёт в угол, позиция (с точностью до симметрии) будет следующая:
О | ||
Х | ||
Х |
В зависимости от следующего хода нолика, возникнет одна из трёх позиций:
О | О | |
Х | ||
Х |
О | ||
Х | О | |
Х |
О | О | |
Х | ||
Х |
В первых двух позициях побеждают крестики. В третьей — ничья.
За нолики
[править | править код]Вcпоминаем, что правила 1-2, если они применимы, имеют приоритет над всем, написанным ниже.
- Если крестики сделали первый ход в центр, до конца игры ходить в любой угол, а если это невозможно — в любую клетку.
О | ||
Х | ||
- Если крестики сделали первый ход в угол, ответить ходом в центр. Следующим ходом занять угол, противоположный первому ходу крестиков, а если это невозможно — пойти на сторону. Далее, если правила 1-2 неприменимы, делать любые ходы. При такой игре после первого хода возникает позиция:
Х | ||
О | ||
- Если крестики сделали первый ход на сторону (не в центр и не в угол), ответить ходом в центр. Далее отвечать в зависимости от второго хода крестиков:
- Если следующий ход крестиков — в угол, занять противоположный угол.
- Если следующий ход крестиков — на противоположную сторону, пойти в любой угол.
- Если следующий ход крестиков — на сторону рядом с их первым ходом, пойти в угол рядом с обоими крестиками.
Возможные позиции после двух ходов показаны на диаграммах.
Х | О | |
О | ||
Х |
О | Х | |
О | ||
Х |
О | Х | |
Х | О | |
Дерево игровых ситуаций
[править | править код]![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Tic-tac-toe-full-game-tree-x-rational.png/220px-Tic-tac-toe-full-game-tree-x-rational.png)
Дерево игровых ситуаций для игры крестики-нолики, где игрок за «крестики» ходит первым и поступает по приведённому выше алгоритму, а игрок за «нолики» может поступать как угодно (причём приведено по одной вершине для рационального и для нерационального поступка, то есть любого другого), состоит из 50-ти узлов.
Компьютерное решение
[править | править код]Для решения такого рода игр на компьютере строится дерево игровых ситуаций в соответствии с методом минимакс. Полное число узлов в таком дереве равно 255168[2]. Это число получается как сумма всех возможных вариантов ходов — 9 вариантов на первом шаге, 8 — для каждого из 9 на втором шаге, 7 — на каждом из 72 вариантов на третьем шаге и т. д., за вычетом ситуаций досрочного окончания игры (выигрыша).
Пример более простой реализации поиска выигравшего игрока: https://github.com/evgnor86/XO_game.git
Обобщения
[править | править код]Более длинные линии
[править | править код]Можно рассматривать игру, в которой победит игрок, первый построивший одинаковых знаков на достаточно большом для этого прямоугольном поле. При этом можно ограничить поле каким-нибудь размером (начиная с ), либо вовсе не ограничивать (в этом случае говорят о «бесконечном» поле)
Игра до 4 одинаковых знаков на бесконечном поле неинтересна, ибо начинающий довольно быстро строит «вилку» и выигрывает. Игра при также неинтересна из-за «ничейной смерти». Существуют стратегии, не дающие противнику построить нужную линию никогда. Однако при игра становится намного содержательнее. Такой вариант имеет специальное название — гомоку. Изначально в гомоку играли на доске размером 19×19, позже она была уменьшена до размера в 15×15 клеток.
Основной победной тактикой при игре на бесконечном поле считается построение пересечений («вилок»), которые не дают противнику возможности блокировать все возможные пути построения пятёрки. Чтобы не проиграть, необходимо своевременно прерывать линии противника длиной в три фигуры и больше.
Практика показала, что при равных правилах для игроков тот, кто делает первый ход, имеет преимущество, позволяющее при достаточно квалифицированной игре одержать победу, что впоследствии было доказано строго[3][4]. Для сохранения интереса к игре предлагались различные варианты модификации правил игры.
Так, с введением фолов (запрещённых ходов) для игрока, начинающего первым — ему запрещено строить вилки 3×3, 4×4, а также выстраивать «длинный ряд» из своих фигур — получилась новая игра под названием рэндзю, с большим разнообразием стратегий игры и равными шансами игроков.
Модификация поля
[править | править код]Увеличение размера поля уже обсуждалось выше. Самым простым, но увеличивающим тактическое богатство игры, является добавление одной клетки вдоль одной из сторон поля 3×3.
Другим вариантом является изменение топологии поля. Например, можно считать противоположные стороны поля склеенными, образуя при этом либо поверхность цилиндра или тора, либо проективную плоскость. Также можно увеличивать размерность, например, играть в кубе 4×4×4, в гиперкубе и так далее.
Обмен значков
[править | править код]Можно отменить правило, указывающее игрокам ставить только свой вид значков.
Например, вариантом игры может быть: игроки ставят крестик или нолик (что захотят); первый выигрывает, если построит линию нужной длины из одинаковых значков, второй — если до заполнения поля этого не произойдёт.
Другой вариант: «свой» значок меняется с каждым ходом.
Изменение условия выигрыша
[править | править код]Вместо того, чтобы заканчивать игру построением первой линии нужной длины, можно на этом не останавливаться и продолжить до полного заполнения поля. Например, на любом поле можно играть на то, кто больше построит «четвёрок» из своих знаков.
Также существует вариант крестиков-ноликов Силвермэна. В нём используется игровое поле 4×4 клетки. Крестики выигрывают, если возникает ряд из 4-х одинаковых значков (крестиков или ноликов), иначе выигрывают нолики.
Ещё существует вариант игры с классическим полем 3×3, в котором необходимо для выигрыша составить два ряда, в то время как противоборствующему алгоритму достаточно и одного.[5][6]
Удлинение хода
[править | править код]Ещё один вариант модификации игры — выставлять на каждом ходе не один свой знак, а два или более. Такова игра Connect6, в которой чёрные делают первый ход, выставляя один знак, после чего игроки поочерёдно выставляют по два знака, побеждает первый, построивший линию из 6 или более своих знаков.
Супер крестики-нолики
[править | править код]Игра идёт на поле 9x9, разделённом на 9 малых досок (3x3). Игроки по очереди играют на малых полях, каждым ходом «отправляя» соперника на другую доску. Когда один из игроков выигрывает на локальном поле, он отмечает его своим знаком (X или O). Так происходит, пока один из них не выиграет на большой доске. По сравнению с традиционными крестиками-ноликами, стратегия в этой игре концептуально сложнее и оказалась более сложной для компьютеров.
Крестики-нолики в культуре
[править | править код]Песен, посвящённых этой игре, три.
- Песня «Крестики-нолики» композитора Вениамина Баснера на стихи Михаила Матусовского в исполнении Таисии Калинченко стала лауреатом «Песни-74»[7]. В дальнейшем её спел Эдуард Хиль[8]
- Другую песню с таким же названием спела Катя Лель[9]
- Третью песню спели дуэтом Виктор Рыбин и Наталья Сенчукова[10].
Игра «Крестики-нолики» фигурирует в качестве сюжетного приёма в кинофильме «Военные игры».
Примечания
[править | править код]- ↑ В XIX веке, наряду с названием «крестики-нолики» (см. Н. А. Лейкин, «Учебный день в немецкой школе», 1871), также использовались «херики-оники» или «херики» — по старому названию букв русского алфавита «Х» — «хер» и «О» — «оно» («Хер» в словаре Даля Архивная копия от 14 июня 2011 на Wayback Machine), «нолики» (Н. П. Гиляров-Платонов, «Из пережитого», 1886
- ↑ How many Tic-Tac-Toe (noughts and crosses) games? www.se16.info. Дата обращения: 16 августа 2019. Архивировано 15 февраля 2020 года.
- ↑ Allis, L. V. (1994). Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht.
- ↑ Allis, L. V., Herik, H. J. van den, and Huntjens, M. P. H. (1996). Go-Moku Solved by New Search Techniques. Computational Intelligence, Vol. 12.
- ↑ Twice crosses-circles | Video Game | VideoGameGeek . Дата обращения: 7 сентября 2022. Архивировано 7 сентября 2022 года.
- ↑ Twice crosses-circles - MobyGames . Дата обращения: 12 марта 2023. Архивировано 12 марта 2023 года.
- ↑ Таисия Калинченко "Крестики-нолики" (1974) . Дата обращения: 17 января 2022. Архивировано 17 января 2022 года.
- ↑ Эдуард Хиль, - Крестики нолики . Дата обращения: 17 января 2022. Архивировано 17 января 2022 года.
- ↑ Катя Лель - Крестики-нолики . Дата обращения: 17 января 2022. Архивировано 17 января 2022 года.
- ↑ Виктор Рыбин и Наталья Сенчукова — «Крестики-нолики» . Дата обращения: 17 января 2022. Архивировано 17 января 2022 года.
Литература
[править | править код]- Гарднер М. Крестики-нолики. —М.: Мир, 1988. ISBN 5-03-001234-6.
В статье есть список источников, но не хватает сносок. |