Что это за игра
Крестики-нолики — самая известная игра на бумаге в клетку и, пожалуй, первая, в которую каждый из нас играл против кого-то, кто считает лучше.
Поле три на три, два знака, одна цель — три в ряд. Правила объясняются за десять секунд, и именно поэтому игра стала классическим учебным примером: на ней показывают, как машина перебирает варианты, как устроено дерево игры и что значит «игра решена».
Ответ давно известен: при безошибочной игре обеих сторон крестики-нолики всегда кончаются ничьей. Против экспертного уровня выиграть нельзя — но и проиграть не обязательно. Вопрос в том, удержите ли вы ничью.
Правила
- Поле три на три. Вы ставите крестики (X, красные), компьютер — нолики (O, синие).
- Ходят по очереди; за ход ставится один знак в любую пустую клетку.
- Кто ходит первым, меняется от партии к партии: одну начинаете вы, следующую — компьютер.
- Побеждает тот, кто первым поставит три своих знака в ряд — по горизонтали, вертикали или диагонали. Выигрышная линия подсвечивается жёлтым.
- Если все девять клеток заняты, а трёх в ряд нет, — ничья. Ничья не добавляется ни в один счёт под доской.
Как играть лучше
- Центр входит в четыре линии из восьми — больше, чем любая другая клетка. Угол — в три, край — только в две.
- Если ходите первым, начинайте с угла или центра. Ход в угол сложнее всего парировать: единственный надёжный ответ на него — центр.
- Главное оружие — вилка: ход, после которого у вас две угрозы сразу. Одну соперник закроет, вторую — уже нет.
- Прежде чем строить своё, проверьте, нет ли у соперника двух знаков в линии с пустой третьей клеткой. Пропущенный блок — самая частая причина поражения.
- Если ходите вторым и соперник занял угол, ставьте в центр. Ответ в край или в соседний угол проигрывает.
- Против простого уровня работает почти всё, против сложного — вилка. Против эксперта цель одна — не ошибиться: он выбирает ходы, после которых у вас больше всего способов проиграть.
Немного истории
Игры с тремя знаками в ряд на маленькой доске известны с давних времён, а название «крестики-нолики» и привычная запись на бумаге устоялись в девятнадцатом веке. По-английски игру называют tic-tac-toe или noughts and crosses.
В 1952 году Александр Дуглас написал в Кембридже программу OXO для компьютера EDSAC: человек играл против машины, а позиция выводилась на маленький экран. Её часто называют одной из первых компьютерных игр. В 1961 году Дональд Мичи построил MENACE — «машину», которая училась играть в крестики-нолики из спичечных коробков с бусинами: после каждой партии бусины удачных ходов добавлялись, неудачных — изымались. Это один из первых примеров обучения с подкреплением.
Перебрать всю игру — задача для начинающего программиста: различных партий 255 168, а позиций с точностью до поворотов и отражений — всего 765. Результат известен: ничья. Это самая маленькая из решённых игр в нашем справочнике решённых игр, а её большая сестра — ультимативные крестики-нолики, где девять полей в одном.
Об уровнях
Простой замечает только собственную победу: если может поставить третий знак в ряд, ставит. В остальном ходит куда попало и чужих угроз не видит.
Сложный ещё и блокирует ваши угрозы, а свободным ходом занимает центр, потом углы. Его обыгрывает вилка: две угрозы сразу он не закроет.
Эксперт знает цену каждой из нескольких тысяч позиций и не ошибается. Из ходов, которые сохраняют лучший результат, он выбирает тот, после которого у вас больше всего проигрывающих ответов. Обыграть его нельзя; ничья с ним — максимум.