Крестики нолики (3x3...20x20)

Крестики нолики - логическая игра между двумя противниками на квадратном поле 3 на 3 клетки или большего размера (вплоть до "бесконечного поля"). Один из игроков играет "крестиками X" , второй - "ноликами O".

Настройки нашей игры:

Выбор Cетки от 3 до 20 (n)

Выбор линии сплошного ряда от 3 до 10 (s) при условии что n >= s

Уровень сложности 1-2

0 - Простой

1 - Сложый

2 - Эксперт (продумывает на глубину 3 клетки)

3 - Мастер (продумывает на глубину 4 клетки и может долго думать)

4 - Используется только Эвристический анализ. (очень быстро)

Правила игры:

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

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

Анализ:

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

Считается, что игрок всегда соблюдает два правила, имеющие приоритет над всеми остальными:

Правило 1. Если игрок может немедленно выиграть, он это делает.

Правило 2. Если игрок не может немедленно выиграть, но его противник мог бы немедленно выиграть, сделав ход в какую-то клетку, игрок сам делает ход в эту клетку, предотвращая немедленный проигрыш.

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

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

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

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

Можно рассматривать игру, в которой победителем считается игрок, первым построивший n>= 3 одинаковых знаков на достаточно большом для этого прямоугольном поле. При этом можно ограничить поле каким-нибудь размером (начиная с NxN), либо вовсе не ограничивать (в этом случае говорят о "бесконечном" поле)

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

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

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