Шахматы в четырёх измерениях: внутри движка Tesseract

Шахматные варианты обычно добавляют трюк к доске, которую все понимают. Мы хотели обратного: оставить правила узнаваемо шахматными и поменять пространство — с двух измерений на четыре. Получился Tesseract, тринадцатая игра нашей Лаборатории и с большим отрывом самая математически требовательная вещь, которую мы выпускали в браузере.

Четыре измерения звучат как маркетинг ровно до того момента, когда садишься писать генератор ходов. Дальше всё становится очень буквальным: ладья здесь бьёт по восьми лучам, а не по четырём. Слон — по двадцати четырём. Появляются две новые дальнобойные фигуры, потому что в 4D-пространстве есть два новых типа диагонали, и появляются два вида пешек, потому что пешке нужна ось «вперёд», а свободных осей у доски теперь две. Каждое из этих утверждений должно было пережить независимо написанный верификатор, прежде чем мы поверили в него сами.

Доска на 625 клеток

Доска — решётка 5×5×5×5: 625 клеток, координаты (x, y, z, w), каждая идёт от 1 до 5. Внутри клетка это одно целое число: idx = (x−1) + 5(y−1) + 25(z−1) + 125(w−1). Рендерер использует ту же упаковку, поэтому индекс клетки пересекает границу движка и рендерера без перевода — на стыке нет ошибок с координатами, потому что нет и самого стыка.

Классическая движковая беда свалиться с доски в 4D становится только хуже: каждый скользящий луч обязан знать, где край, в восьмидесяти направлениях. Классические 2D-движки решают это через mailbox — доску с полями, у которой пограничные клетки помечены недопустимыми, — и идея, как выяснилось, обобщается прекрасно. Tesseract использует mailbox 9⁴: 6561 32-битная запись, около 26 КБ, где игровая доска 5⁴ лежит на два поля в стороне от каждой границы — ровно на дальность хода коня. Определение выхода за доску превращается в одно обращение к массиву. Альтернатива, таблицы лучей на каждую клетку, стоила бы около 350 КБ и куда большего числа промахов кеша.

Восемьдесят направлений атаки

В n измерениях естественное обобщение шахматного хода — это множество ненулевых векторов направления с компонентами из {−1, 0, 1}. В 4D оно даёт 3⁴ − 1 = 80 направлений, и они делятся по тому, сколько осей меняется разом: 8 направлений меняют одну ось, 24 — две, 32 — три, 16 — все четыре.

Эти четыре класса и есть набор фигур. Ладье достаётся первый класс. Слону второй — привычные диагонали, которых теперь двадцать четыре. Третий принадлежит единорогу, фигуре, позаимствованной из Raumschach, трёхмерного шахматного варианта 1907 года: он скользит по пространственным диагоналям, которых на плоской доске не существует. Четвёртый — дракону, так мы назвали фигуру, ходящую по настоящим 4-агоналям, направлениям, где все четыре координаты меняются одновременно. Ферзю и королю достаются все восемьдесят. Конь тоже обобщается: прыжок (2, 1, 0, 0) в любой паре осей и любой комбинации знаков — 48 различных прыжков.

Интуиция ошибается здесь интересным образом, поэтому мы посчитали. Сумма легальных ходов одной фигуры по всем клеткам пустой доски: ладья набирает 10 000, слон — 18 000. На плоской доске ладья сильнее как дальнобойная фигура; в четырёх измерениях слону просто больше места. Дракон, владыка самого экзотического класса направлений, наскребает лишь 5664 — 4-агонали из большинства клеток коротки и редки, — и поэтому пара драконов стоит в третьем ряду плиты, а не держит угол. Это не ощущения, а замороженные константы в самопроверке движка: сборка падает, если генератор ходов когда-нибудь с ними разойдётся.

Начальная позиция как теорема

Придумать стартовую позицию для доски, на которой никто никогда не играл, — ловушка: откуда вам знать, что белым не мат в четыре и что пешечная стена не делает игру ничейной по построению? Мы сделали позицию не правдоподобной, а доказуемой. Армия чёрных — точное центральное отражение белых: каждая фигура переходит по σ: p → 6−p во всех четырёх координатах. Центральная симметрия гарантирует идеальный материальный и позиционный баланс, и у неё есть более тихое следствие, которое нам нравится даже больше: изначально ничто не атаковано. Если бы на нулевом ходу какая-нибудь белая фигура атаковала чёрную, симметрия породила бы и обратную атаку, и позиция была бы тактической кашей. Она таковой не является, и это проверяемо.

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

Двенадцать старших фигур стоят на плите 5×5 при y=1, w=1 (король в центре первого ряда, пара драконов в третьем), а пешки отвечают на самый странный вопрос дизайна этой доски: где здесь вперёд? В Tesseract есть Y-пешки, идущие вдоль оси y, и W-пешки, идущие вдоль w, и оба вида стоят на двух центральных гиперплоскостях — единственной полосе доски, где белая пешка оказывается ровно напротив своего чёрного зеркального двойника. Размеров армии три (лёгкая, стандартная, плотная), и получаются они расширением пешечной полосы; стандартная — 32 фигуры на сторону, та же перепись, что и в классических шахматах, и это показалось правильным.

Пересчитать каждый ход дважды

Шахматный движок надёжен ровно настолько, насколько надёжен его генератор ходов, а у 4D-генератора есть отказы, которых не заметит на глаз ни один человек: ничья интуиция не подскажет, что потерялась связка единорога вдоль триагонали. Поэтому Tesseract проверяется так, как проверяют серьёзные движки: perft, исчерпывающий подсчёт листовых узлов на заданной глубине, вычисленный дважды двумя генераторами, у которых нет ничего общего.

Быстрый генератор легальный, а не псевдолегальный: он один раз на узел вычисляет шахующие фигуры и связки, сканируя наружу от короля, и выдаёт только те ходы, которые это переживают, — двойной шах оставляет одни лишь ходы королём, одиночный требует взять или закрыться, связанная фигура ходит только вдоль своего луча связки. Наивный генератор нарочно туп и медленен. Они сошлись на 50 618 перекрёстно проверенных узлах при нуле расхождений; полный perft(3) из начальной позиции — 11 661 294 узла. Отдельная пешечная лаборатория — позиция, собранная, чтобы прогонять двойные ходы, обе оси взятия, взятие на проходе и превращение, — добавляет ещё 559 319 согласованных узлов. А поскольку весь движок целочисленный и в игровой логике нет ни одной операции с плавающей точкой, замороженный сценарий на 40 полуходов обязан приходить к одному и тому же хешу Зобриста в любом браузере и в любой сборке. Детерминизм здесь не приятная мелочь: без него онлайн-режим невозможен в принципе.

Как сделать четыре измерения читаемыми

Самым трудным был вовсе не движок. Самым трудным был экран. 4D-позиция должна лечь на 2D-монитор, не соврав про геометрию, а стандартный трюк — нарисовать красивую вращающуюся тень тессеракта — для игры бесполезен. Наш ответ почти неприлично плоский: рисовать решётку 5⁴ как сетку 5×5 из досок 5×5. Оси x и y живут внутри каждой маленькой доски; z и w выбирают доску. Отображение — worldX = (w−3)·PITCH + (x−3)·CELL, и решающее его свойство в том, что оно аффинно по всем четырём координатам: любая 4D-прямая — луч ладьи, триагональ единорога, 4-агональ дракона — проецируется в прямую линию подсвеченных клеток на экране. Именно через прямизну глаз осваивает геометрию.

Камера ортографическая намеренно: перспектива сломала бы эту аффинность, а заодно и попадание по клетке, которое здесь считается замкнутой формулой обратного проецирования, а не рейкастом на GPU. Всё поле рендерится одним текстурированным квадом (все 25 шахматных досок запечены в одну canvas-текстуру), шестнадцать инстансированных мешей на армии, пять на подсветку: около 24 вызовов отрисовки в худшем случае, на канвасе с frameloop="demand", который, пока вы думаете, рисует ровно ноль кадров. Для моментов, когда хочется увидеть честную форму этой штуки, второй вид рисует настоящий тессеракт — внутренний куб при w=1, внешний при w=5, вращающийся изоклинным поворотом — и возвращает урок геометрии вашим глазам.

Соперник, помещающийся в Web Worker

В начальной позиции 226 легальных ходов против двадцати в классических шахматах — вот измеренный коэффициент ветвления, с которым поиску приходится жить. Поиск такой ширины обязан быть скромным и обязан работать не в главном потоке: мастерский уровень думает до 3,5 секунд, и это заморозило бы вкладку, работай он там, где живёт React. Поэтому движок гоняет fail-soft негамакс с итеративным углублением в Web Worker, тяжело опираясь на отсечение нулевым ходом, поздние редукции ходов и futility pruning, чтобы пережить ширину. Уровней сложности четыре — от мгновенного соперника на 60 мс с намеренно зашумлённой оценкой до мастера с таблицей на 16 МБ, доходящего до шестой глубины. Даже случайность ИИ детерминирована: дрожание корневых ходов даёт генератор с сидом, привязанным к записи партии, так что переигранная партия воспроизводится в точности.

Задачи с решениями, проверенными машиной

Задачи есть в каждом шахматном приложении; в большинстве несколько из них сломаны. В четырёх измерениях сломанную задачу нельзя починить по жалобе пользователя — опровержение 4D-мата в три никто не увидит на глаз. Поэтому ни одна задача не выходит под наше честное слово. Каждый из двенадцати этюдов набора обязан пройти три машинные проверки: точность (поиск на удвоенную заявленную глубину находит мат ровно в N, начиная с указанного ключевого хода), единственность (никакой другой первый ход не матует так же быстро) и форсированность (любой ответ защиты всё равно проигрывает). Обучение проходит ту же процедуру: его восемь уроков доказываются проходимыми прогоном всех легальных ходов нужной фигуры через настоящий движок. Если урок можно провалить, сначала падает сборка.

Четырёхмерные шахматы по недоверенному каналу

Онлайн-партии идут по realtime-каналу вещания, и мы относимся к нему ровно как к тому, чем он является: недоверенному ретранслятору. Пиры договариваются о ключе через ECDH, и каждый ход пересекает провод аутентифицированным — HMAC поверх канонической сериализации, куда входят версия протокола, идентификатор матча, привязанная 128-битная личность отправителя и порядковый номер полухода. А дальше идёт проверка, после которой всё остальное почти декоративно: принимающий клиент заново проверяет каждый входящий ход собственным генератором легальных ходов. С подделанным или испорченным ходом не спорят — он просто нелегален, а детерминированный движок означает, что обе доски либо совпадают идеально, либо ловят рассинхрон по хешу Зобриста уже на следующем ходу.

// A move on the wire: eight digits (from-xyzw, to-xyzw) + optional promotion.
const WIRE_MOVE = /^[1-5]{8}[QRBNUD]?$/;

"22132313";  // Y-pawn at (2,2,1,3) steps forward along y to (2,3,1,3)
"24132513Q"; // the same pawn reaching y=5 promotes: Q R B N U or D

Tesseract взял платформу, которую мы построили за тринадцать игр — общие уровни качества, аудиосинтез, контракт полноэкранного режима, правило одного канваса — и направил всё это на один вопрос: может ли браузер научить человека видеть в четырёх измерениях? После недели поражений от собственного новичкового уровня честный ответ, кажется, такой: медленно, и в этом всё удовольствие.