ПРАВИЛО ГО, КОТОРОЕ МЕНЯЕТ ОТВЕТ

Решить игру — значит знать её исход, когда обе стороны играют идеально. На доске го этот исход — ценность: число очков, с которым чёрные выигрывают при идеальной игре; 28 на доске 4×7 означает, что чёрным принадлежат все 28 пересечений. Шашки были решены в 2007 году, гекс на маленьких досках — тоже. Для го существуют компьютерные доказательства для многих досок размером до 30 пересечений, в основном полученные программой MIGOS (2003 и 2009 годы).

Но есть подвох. В этих классических результатах используется упрощённое правило для повторяющихся позиций — базовое правило «ко»: игрок не может сразу взять обратно одиночный камень, который только что взял один из его камней, иначе одни и те же два хода повторялись бы вечно, — плюс особые соглашения: пас снимает запрет ко, партия останавливается на повторившейся позиции и так далее. Эти соглашения придуманы для того, чтобы ценность позиции не зависела от того, как к ней пришли.

Правило, по которому играют на самом деле

Китайские правила в их письменном виде и компьютерное го используют позиционное суперко: ни один ход не может воссоздать любую позицию всей доски, уже встречавшуюся в партии. Решать игру по такому правилу гораздо труднее, потому что допустимость хода теперь зависит от всей истории партии. Это ломает три инструмента, которые делают решение осуществимым:

повторное использование результатов для той же позиции, достигнутой другим путём, — два пути могут запрещать разные ходы;
распознавание безопасных групп и территории без перебора, которое предполагает, что владелец всегда может съесть вторгшиеся камни, — а при суперко такое взятие может быть запрещено;
отсечение (pruning) ходов, которые никогда не помогают, например заполнения собственного глаза — одного из пустых пересечений, которые нужны группе, чтобы остаться живой, — при суперко такой ход может оказаться решающим.

Цена была огромной: с одним из вариантов суперко MIGOS понадобилось 1,1 часа на доску 4×4 против 3,3 секунды при базовом ко. Первое решение 5×5 при суперко в 2024 году заняло 5,25 часа на шести процессах. За пределами 5×5 ни одна доска, имеющая хотя бы две линии, при суперко решена не была.

Сокращение, которое остаётся корректным

Сами Харма и Флориан Шинтке из Института Цузе в Берлине (Zuse Institute Berlin) создали Sanko. В его основе — простая теорема о переносе доказательства (proof-transfer theorem): сохранённое доказательство того, что игрок выигрывает, остаётся верным на новом пути, если только позиция, которую победитель должен создать, уже не встречалась. Важны только позиции победителя: если проигравший больше не может воссоздать какую-то позицию, он просто теряет один вариант. Проверка занимает время, пропорциональное длине пути, а не размеру доказательства. На доске 3×7 одно лишь это сокращение уменьшает объём работы с 664 миллиардов шагов до 112 миллионов.

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

Новые значения

5×5 за 15,7 минуты на шести потоках — примерно в 20 раз быстрее, чем прежде, отчасти благодаря более мощному оборудованию; на одном потоке 4×4 решается в 58 раз быстрее. На одной машине со 192 потоками 5×5 занимает около полутора минут.
Первые значения при суперко для ещё 23 досок; 11 из них не были решены ни по каким правилам. 3×10 стоит для чёрных 8 очков — MIGOS доказал лишь не меньше 6, а два месяца поиска так и не дали верхней границы.
На однорядных досках значения от 1×9 до 1×15 повторяются как 0, 1, 2, 2 — но 1×16 нарушает закономерность: она стоит 1, а не 2.

Сюрприз 4×7

По старым правилам 4×7 — победа на всю доску: чёрные съедают всё, 28:0. При суперко она стоит 12. Авторы воспроизвели опубликованную для MIGOS оптимальную линию из 31 хода: все ходы допустимы, и чёрные всё равно забирают всю доску. Решая линию в обратном направлении, они нашли точку излома сразу после 25-го хода: в позиции после 25-го хода, сделанного чёрными, белым следует сыграть G2 (или C1) вместо A2.

Дальше возникает странное ко. Белые съедают; ответное взятие чёрных воссоздало бы прежнюю позицию — запрещено. Любой другой ход чёрных ставит под угрозу их собственную группу. Чёрные вынуждены пасовать, белые пасуют, и партия заканчивается тем, что группа белых жива: авторы MIGOS уже называли это «жизнью при лунном свете» (moonshine life). По старым правилам пас снял бы запрет, и чёрные отыграли бы камни и выиграли всё. При суперко лучшее, чего чёрные добиваются в этой линии, — общая жизнь (сэки) стоимостью всего 3 очка, поэтому идеальная игра сходит с опубликованной линии раньше — и лучшее, что чёрные могут обеспечить себе с пустой доски, — это 12.

Ни один из поисков не ошибся. Разница возникает из-за правил, которые имеют значение только в самом конце партии. Совет авторов: значения, вычисленные по соглашениям, делающим повторения безвредными, не следует без проверки приводить как значения го с суперко.

Проверить может каждый

Каждое значение опирается на два независимых доказательства, а решатель прошёл десятки тысяч перекрёстных проверок без единого расхождения. В отличие от прежних решений пустых досок го, исходный код решателя и точная команда, стоящая за каждым результатом, открыты; цепочка доказательств для 4×7 воспроизводится менее чем за двадцать секунд. Доказательства пока не являются сертификатами, которые посторонний мог бы проверить независимо, а 6×6 остаётся недосягаемой: по экстраполяции авторов, это около 50 дней на одной из их машин, а то и больше.