Что значит, что игра решена
Игра решена, когда известен результат, получаемый при идеальной игре обоих игроков из начальной позиции. Обычно различают три степени. При «ультраслабом» решении известно только, кто выигрывает или будет ли ничья, но не известна стратегия. При «слабом» дополнительно известна стратегия, гарантирующая этот результат с самого начала. При «сильном» известен лучший результат из любой возможной позиции.
В случае «Четыре в ряд» на классическом поле из 7 столбцов и 6 рядов результат ясен: при идеальной игре выигрывает игрок, который начинает. Это не значит, что он всегда выигрывает на практике, потому что для этого нужно находить верный ход на каждом шаге, а партии между людьми полны ошибок.
Кто решил игру и когда
У этой истории два героя, которые независимо друг от друга пришли к одному выводу в октябре 1988 года. Первым был Джеймс Доу Аллен, объявивший о своём решении 1 октября 1988 года в сообщении в группе обсуждений rec.games.programmer. Спустя пятнадцать дней, 16 октября, нидерландский исследователь Виктор Аллис представил собственное решение, описанное в его работе «A Knowledge-based Approach of Connect-Four» в Свободном университете Амстердама.
Метод Аллиса был «основан на знаниях»: вместо того чтобы перебирать все позиции, он сформулировал стратегические правила, например какие клетки выгодно контролировать и какие угрозы важны, и объединил их с поиском, чтобы доказать, что первый игрок может принудительно выиграть. Позднее тот же результат получили грубой силой, с базами данных позиций и мощными компьютерами; программист Джон Тромп, например, создал базу всех позиций из 8 фишек, которая послужила отправной точкой. Оба пути сходятся.
Ключ к дебюту: центральный столбец
Подходит не любой первый ход. Результат зависит от столбца, в котором начинает первый игрок:
| Первый ход | Результат при идеальной игре |
|---|---|
| Центральный столбец (4-й) | Выигрывает начинающий |
| Столбцы рядом с центром (3-й и 5-й) | Ничья |
| Крайние столбцы (1, 2, 6 и 7) | Выигрывает второй игрок |
Что значит «выигрывает начинающий» на практике
То, что теория говорит, будто первый выигрывает, ничего не гарантирует, если соперник играет хорошо: преимущество реально, но требует точности. И всё же первый ход даёт две конкретные вещи. Первая — инициатива: вы ходите первым, и сопернику обычно приходится отвечать на ваши угрозы. Вторая — чётность, очень распространённое среди игроков практическое правило: поскольку в поле 6 рядов, чётное число, и ходы делаются по очереди, клетки нечётных рядов (1, 3 и 5, считая снизу) чаще достаются тому, кто начал, а клетки чётных рядов — второму. Поэтому угроза в нечётном ряду обычно ценнее для первого игрока.
Почему центр так важен
Фишки центрального столбца участвуют в большем числе возможных линий, чем фишки любого другого столбца. Из центра можно собрать четыре в ряд по горизонтали, по вертикали и по двум диагоналям многими разными способами; фишка у края пригодна почти лишь для одного-двух направлений. Поэтому сильные программы упорядочивают ходы от центра к краям, и поэтому дебютные книги начинаются со столбца 4.
Для вас практическое правило простое: когда нет явно лучшего хода, выбирайте столбец ближе к центру. А если соперник занял центр первым, не отчаивайтесь: соседние столбцы по-прежнему очень хороши.
Советы, как выигрывать чаще у людей
- Если вы начинаете, ходите в центральный столбец. Это единственный дебют, который при идеальной игре выигрывает.
- Ищите двойные угрозы: две линии из трёх фишек с доступной замыкающей клеткой одновременно. Соперник может заблокировать только одну. Это самый распространённый способ выиграть у людей.
- Думайте об угрозах «в воздухе»: линия из трёх, замыкающая клетка которой пока недоступна, потому что не хватает фишки под ней. Если эта клетка стоит в ряду, выгодном вам по чётности, сопернику рано или поздно придётся сыграть под неё и подарить её вам.
- Прежде чем бросить фишку, посмотрите, какая клетка освобождается прямо над ней. Если вы дарите сопернику клетку, которой он замыкает линию, вы проиграли.
- Блокируйте линии из трёх, открытые с обеих сторон, до того как они сформируются: это верное поражение. Предвидьте на ход вперёд.
- В концовке важно, у кого кончаются безопасные ходы: берегите столбцы, в которые ещё можно играть без опасности.
- Если вы второй, стремитесь к клеткам чётных рядов и без спешки блокируйте каждую угрозу в нечётных рядах: это ваш лучший путь к ничьей или к ошибке соперника.
Значит, компьютер не может проиграть?
Программа, которая играла бы идеально с самого начала и ходила первой, никогда бы не проигрывала, но это утверждение о теоретическом решении игры, а не о любой программе. Решить всю партию из начальной позиции требует огромного объёма вычислений, и в браузере, при полутора секундах на ход, это не удаётся.
Поэтому уровень «Непобедимый» в нашей игре «Четыре в ряд» представлен как то, что он есть: самый сильный уровень. Он использует альфа-бета-поиск с итеративным углублением, таблицу, запоминающую уже виденные позиции, порядок столбцов от центра и очень короткую книгу дебютов. Он просчитывает много ходов вперёд и почти не пропускает ошибок, но мы не обещаем, что его невозможно победить. Если вы его обыграли, вы действительно выиграли.
Как тренироваться
Хороший способ совершенствоваться — играть против компьютера на уровне «Сложно», а затем против «Непобедимого», чередуя, кто начинает. Когда проигрываете, разберите партию и определите, на каком ходу появилась двойная угроза: почти всегда её можно проследить до более раннего тихого хода. Полезно также попробовать варианты, например поле побольше или режим PopOut, которые заставляют думать иначе и тренируют видение доски.
Часто задаваемые вопросы
Кто доказал, что «Четыре в ряд» решена?
Джеймс Доу Аллен объявил об этом 1 октября 1988 года, а независимо от него Виктор Аллис представил своё решение 16 октября 1988 года. Затем появились подтверждения методом грубой силы.
Кто выигрывает в «Четыре в ряд» при идеальной игре?
Игрок, который начинает, при условии что его первая фишка идёт в центральный столбец классического поля 7×6. Если он начинает в столбце рядом с центром, партия теоретически заканчивается ничьей, а если в одном из четырёх крайних столбцов, выигрывает второй игрок.
Значит ли это, что начинающий всегда выигрывает?
Нет. Это результат при отсутствии ошибок. На практике нужно продолжать находить верные ходы на каждом шаге, а люди ошибаются. Первый ход — преимущество, а не гарантия.
Решены ли и другие размеры поля?
Многие решены, но результат меняется в зависимости от размера. Например, Джон Тромп сообщил, что на поле 8×8 выигрывает второй игрок. Это руководство относится только к классическому полю из 7 столбцов и 6 рядов.
Правда ли, что уровень «Непобедимый» никогда не проигрывает?
Мы этого не обещаем. Это самый сильный уровень, который мы предлагаем, с глубоким поиском и большим объёмом вычислений на ход, но он не решает всю партию за отведённое время. Он есть только на классическом поле 7×6.
Сколько позиций в «Четыре в ряд»?
На поле 7×6 подсчитано 4 531 985 219 092 допустимые позиции; эта цифра была независимо подтверждена в 2008 году Стефаном Эделькампом и Петером Киссманном.