Правила и происхождение
Хекс — игра с одним из самых коротких сводов правил и одной из самых длинных историй сопротивления компьютерам.
Доска — ромб из шестиугольников, здесь 7×7. Вы играете красными и соединяете верхнюю сторону с нижней; компьютер играет синими и соединяет левую с правой. Ходят по очереди, первый ход всегда ваш. Камень ставится на любую пустую клетку, после этого он не двигается и не снимается. Побеждает тот, кто первым свяжет свои стороны непрерывной цепочкой своих камней; угловые клетки принадлежат обеим сторонам сразу.
Игру изобрели дважды. В 1942 году датчанин Пит Хейн опубликовал её в газете «Политикен» под названием «Полигон»; в 1948-м её независимо переоткрыл Джон Нэш в Принстоне — там её так и звали, «Нэш». С 1952 года Parker Brothers продавала её под именем Hex, которое и прижилось. Классическая доска — 11×11; 7×7 — младший формат, на котором вся механика уже работает в полный рост.
В серьёзной игре применяют «правило пирога»: второй игрок вправе забрать себе первый ход соперника, поэтому первый вынужден начинать нарочно скромно. Здесь этого правила нет — это упрощение, и, как сказано ниже, оно целиком в вашу пользу.
Две теоремы
Ничья невозможна. Как бы ни была заполнена доска, ровно один из игроков оказывается соединён. Звучит очевидно, доказывается — нет: в 1979 году Дэвид Гейл показал, что это утверждение эквивалентно теореме Брауэра о неподвижной точке, одному из центральных фактов топологии. Партия в хекс не может кончиться ничем.
У первого игрока есть выигрышная стратегия. Доказательство Нэша 1949 года называется «кражей стратегии»: если бы выигрывал второй, первый мог бы сделать произвольный ход и дальше играть выигрышной стратегией второго — лишний камень в хексе не мешает никогда. Противоречие, значит, выигрывает первый.
У этого доказательства есть свойство, ради которого страница и построена: оно неконструктивно. Известно, ЧТО выигрыш существует; КАК он выглядит — из доказательства не следует вообще. Явные стратегии найдены компьютерами только для маленьких досок: 7×7 решён, частичные результаты доходят примерно до 10×10. Для турнирных 11×11 и 13×13 выигрышная стратегия по-прежнему неизвестна никому.
Честное признание
Машина на этой странице выигрышной стратегии не знает. Мало того: мы отдали вам первый ход и убрали правило пирога, то есть посадили вас в доказанно выигрышную позицию. По теории вы не должны проигрывать ни одной партии — никогда, ни при какой игре соперника.
И тем не менее машина будет обыгрывать большинство посетителей. Разница между «выигрыш существует» и «вы умеете его найти» — главный сюжет этой страницы. Теорема вручает вам победу; найти её среди десятков тысяч продолжений теорема не помогает.
Статистика под доской из-за этого смещена в вашу пользу сознательно: каждая партия начинается с позиции, в которой вы — на бумаге — уже выиграли. Всё, что вы проигрываете, проиграно не позиции, а поиску.
Как машина ищет ход
Перебором с альфа-бета-отсечением, как в шахматных программах, но с оценкой, устроенной под хекс. Позиция оценивается связностью: для каждой стороны считается кратчайший путь алгоритмом Дейкстры, где свой камень проходится бесплатно, пустая клетка стоит один ход, чужой камень непроходим. Оценка — разность двух путей: чей путь короче, тот ближе к победе. Отдельно учитываются «мосты» — пары своих камней с двумя общими пустыми соседями: такое соединение нельзя разорвать одним ходом, и машина считает его почти готовым.
Уровни различаются глубиной. «Обычный» смотрит на ход вперёд и выбирает случайно из трёх лучших клеток. «Сложный» честно считает два полухода. «Эксперт» углубляется, пока укладывается примерно в секунду с небольшим, и отвечает лучшим ходом последней досчитанной глубины.
В хексе люди дольше, чем почти в любой классической игре, держались против программ на равных: оценка связности плохо раскладывается на слагаемые, которые умеет складывать перебор. Сильные программы появились только в 2000-е, с методом Монте-Карло, а окончательно машины ушли вперёд уже в эпоху нейросетей. То, с чем вы играете здесь, — перебор со связностью: его достаточно, чтобы наказывать неточности, и недостаточно, чтобы знать то, что знает теорема.