Крестики-нолики решены: при безошибочной игре обеих сторон всегда получается ничья, поэтому выиграть у соперника, который не ошибается, нельзя. Не проиграть можно всегда: выигрывайте, когда можете, блокируйте, когда надо, и не давайте сопернику построить вилку. Выигрывают на ошибках соперника — и первый ход в угол даёт ему больше всего способов ошибиться: семь ответов из восьми проигрывают, держит только центр.
На поле восемь линий: три строки, три столбца и две диагонали. Клетка стоит столько, через сколько линий она проходит. Центр входит в четыре линии, каждый угол — в три, каждый край — только в две.
Именно поэтому борьба идёт за центр и углы, а начинать с края слабее всего. И поэтому два главных защитных ответа ниже звучат как «займите центр» и «займите угол».
Угроза — два ваших знака в линии и пустая третья клетка. Одна угроза ничего не даёт: соперник просто закроет её. Вилка — ход, который создаёт две угрозы сразу. Закрыть можно только одну, вторая выигрывает.
Почти каждая партия, которая не кончилась ничьей, решается вилкой, и почти каждое поражение начинается на ход раньше — с хода, который её допустил. Поэтому защита — не «закрывать угрозы» (их видят все), а «не дать вилке появиться».
Каждым ходом делайте первое доступное действие из этого списка. Такой порядок использовали Аллен Ньюэлл и Герберт Саймон в своей программе для крестиков-ноликов в 1972 году. Мы прогнали его против всех возможных последовательностей ходов соперника: он не проигрывает ни первым, ни вторым — при точной формулировке пункта 4, на которой ошибается большинство пересказов.
Этот порядок гарантирует ничью, а не победу. И он не всегда выбирает самый коварный ход — об этом ниже, в разделе о первом ходе.
Все девять первых ходов при безошибочной игре ведут к ничьей. Разница в том, сколько ответов соперника сразу проигрывают:
| Ваш первый ход | Проигрывающие ответы | Ответы, которые держат |
|---|---|---|
| Угол | 7 из 8 | только центр |
| Центр | 4 из 8 | любой угол; каждый край проигрывает |
| Край | 4 из 8 | центр, два соседних угла, противоположный край |
Поэтому угол — самый сильный на практике первый ход: у соперника ровно один хороший ответ. Если он его нашёл, ставьте в противоположный угол. Это ловушка, о которой ниже, — но против того, кто её знает, всё равно будет ничья.
Если соперник ответил на угол чем угодно, кроме центра, вилка будет не дальше чем через два хода. Типичная линия: он ставит на край рядом с вашим углом; вы занимаете центр и угрожаете по диагонали; он закрывает дальний угол; вы занимаете оставшийся угол со своей стороны — и у вас две угрозы.
Первый ход в центр работает так же, только на ход позже. Если соперник ответил в угол (правильный ответ), ставьте в противоположный угол: теперь любой край для него проигрывает, держит только угол.
Второй игрок при правильной игре соперника не выиграет, и задача у него одна: правильно ответить на первый ход, а потом не попасть в две классические ловушки.
Ловушка первая: два противоположных угла вокруг вашего центра. Соперник начал в углу, вы заняли центр, он — противоположный угол. Естественный на вид ход — ещё один угол — проигрывает: вы создаёте угрозу, он блокирует, и его блок оказывается вилкой. Ставьте на край: так ваша угроза заставит его блокировать в клетке, которая ему ничего не даёт.
Ловушка вторая: его центр, ваш угол, его противоположный угол. Здесь всё наоборот: нужен угол, а край проигрывает.
Числа в этом разделе посчитаны по коду самой игры: все линии игры против всех ходов, которые может выбрать компьютер, включая случайные.
Простой ставит третий знак в ряд, если видит такую возможность, а в остальном ходит куда попало. Он никогда не блокирует. Поставьте два знака в линию и на следующем ходу закончите её. При лучшей игре вы выигрываете 99,5% партий, если ходите первым, и около 92%, если первым ходит он; остальное — случайный ход, который попал в вашу клетку, или линия, которую вы оставили ему открытой.
Сложный выигрывает, когда может, блокирует ваши угрозы, а в остальном занимает центр, потом случайный угол. Если первым ходите вы, победа гарантирована каждый раз: начните в углу — Сложный займёт центр; поставьте в противоположный угол — блокировать ему нечего, и он займёт один из двух свободных углов, создав угрозу; закройте её, и ваш блок окажется вилкой. Если первым ходит Сложный, он всегда начинает в центре, и тогда никакая последовательность ваших ходов его не обыгрывает, даже с удачей: займите угол, и будет ничья.
Эксперт играет безошибочно, обыграть его нельзя: ничья — лучший возможный результат. Из одинаково хороших ходов он выбирает тот, после которого у вас больше всего проигрывающих ответов. На практике: начиная, он всегда ставит в угол, где семь из восьми ваших ответов проигрывают, — отвечайте в центр. Следующим ходом он ставит рядом со своим углом, на край или в угол, и создаёт угрозу: закройте её и дальше держитесь порядка ходов выше. Когда первым ходите вы, на угол он отвечает центром, на центр — углом, на край — соседним с ним углом.
Крестики-нолики — самая маленькая игра в нашем списке решённых игр. Как машина перебирает её клетка за клеткой — первый шаг в рассказе о том, как машины научились играть. А если игра стала слишком простой, её старшая сестра — ультимативные крестики-нолики: девять полей в одном, и вручную их не решить.
Да. При безошибочной игре обеих сторон партия всегда кончается ничьей. Игра достаточно мала — 255 168 возможных партий, 765 существенно разных позиций, — чтобы короткая программа проверила каждую линию.
Нет. Против соперника, который не ошибается, лучший результат — ничья. Выигрывают только на его ошибках; первый ход в угол даёт ему больше всего шансов ошибиться — семь ответов из восьми проигрывают.
В угол. При безошибочной игре любой первый ход ведёт к ничьей, но после угла не проигрывает только один ответ — центр. После хода в центр или на край проигрывают четыре ответа из восьми.
В центр — и только туда: любой другой ответ проигрывает при правильной игре. Если затем соперник займёт противоположный угол, ставьте на край, а не в угол.
Каждым ходом: выиграйте, если можете; заблокируйте, если нужно; поставьте вилку, если можете; не дайте вилку сопернику; дальше — центр, угол напротив угла соперника, любой угол и только потом край. Проверено на всех возможных партиях: такой порядок не проигрывает.
Ход, который создаёт две угрозы сразу — две линии, где не хватает одного знака. Соперник закроет только одну, и вторая выигрывает. Почти каждая партия, которая не кончилась ничьей, кончается вилкой.
Безошибочный — нет: лучшее, что можно получить, — ничья, и именно так играет уровень «Эксперт» на этом сайте. Слабые программы обыгрываются. Здесь «Простой» никогда не блокирует, а «Сложный» каждый раз проигрывает связке «угол, затем противоположный угол», когда первым ходите вы.
Есть, но не выигрывающее. При случайной игре первый выигрывает 58,5% партий, второй — 28,8%. При безошибочной игре преимущество исчезает, и результат — ничья.