Почему в Maharajah именно эти фигуры

Ответ в одной таблице

Шахматы строят свои дальнобойные фигуры из трёх ходов: прямой линии ладьи (R), диагонали слона (B) и прыжка коня (N). Ферзь — это просто ладья и слон в одной фигуре. Три хода можно соединить ровно семью способами, и вот они все.

Ценность: цена фигуры в очках, когда вы собираете армию в Maharajah. Цены установлены в игре, а не выведены из геометрии выше; четыре классические фигуры сохраняют свою обычную шахматную ценность.

Откуда семь: каждый из трёх ходов либо есть в фигуре, либо нет. Это 2 · 2 · 2 = 8 сочетаний, и одно из них, без единого хода, — не фигура, так что 8 − 1 = 7. На рисунке ниже каждая линия означает «добавить ещё один ход».

Почему именно эти три хода

Поверните доску на четверть оборота или посмотрите на неё в зеркало. Ладья всё так же ходит как ладья, а конь как конь: фигуры не замечают, как повёрнута доска. Такой поворот или отражение называют симметрией, и у квадрата их восемь. Кнопки под рис. 2 позволяют попробовать три из них.

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

Значит, ладья, слон и конь — не три случайных изобретения. Каждая из них — простейший ход одной из всего трёх семей, которые есть у квадрата. Математики называют эти семьи орбитами.

Начал ферзь

Около пятисот лет назад шахматы сделали шаг, который теперь каждый игрок считает само собой разумеющимся: дали одной фигуре ходы двух. Ферзь — это ладья и слон вместе. Как только это разрешено, на очереди ещё три сочетания: ладья и конь, слон и конь и все три сразу. Шахматы их так и не сделали. Махараджа делает: Канцлер, Архиепископ и Махараджа.

Здесь нет ни одного нового вида хода. Каждый ход каждой фигуры Махараджи — это ход, который уже делает какая-то классическая фигура.

Математика, в которую вы уже играете

Шахматист занимается математикой на каждом ходу, не называя её так. Вот шесть идей, на которых стоит эта статья: каждая такой, какой вы уже знаете её по доске, и с названием, которое ей дают математики. Вторая часть пользуется этими названиями.

• Ход — это вектор. «Два вверх и один вправо» — тот же прыжок коня с любого поля. Ход — это не пара полей, а сдвиг: насколько вбок и насколько вверх. Записанный как пара чисел, (1, 2), он называется вектором.
• Ходы складываются. Два прыжка подряд приводят на одно и то же поле в любом порядке. Каждый ход отменяется тем же ходом назад, а стоять на месте — это ход «ничего». Ходы с такими правилами образуют то, что математики называют группой.
• Симметрия. Матовую схему на другом фланге вы узнаёте как ту же схему, отражённую. Поворот или отражение доски, не меняющие того, как ходят фигуры, — это симметрия; у квадрата их восемь, и они тоже образуют группу, которую называют D₄.
• Семьи ходов. Если разложить ходы по тому, какие из них поворот или отражение переводит друг в друга, получатся семьи: прямые, диагональные и косые. Математики называют такие семьи орбитами, а правило «из одной семьи» — эквивалентностью.
• Подсчёт сочетаний. Три хода, каждый в фигуре или нет: 2 · 2 · 2 = 8, минус пустое. Все сочетания, каждое соединённое с теми, из которых оно вырастает, дают рисунок на рис. 1, который называют решёткой.
• Чётность. Слон никогда не покидает своего цвета, а конь меняет цвет на каждом прыжке. Это арифметика всего с двумя ответами, чётное и нечётное, которую называют счётом по модулю 2. Она помогает объяснить, почему Архиепископ матует вместе со своим королём, а ни слон, ни конь не могут.

Ничего из этого не ново для шахматиста; оно лишь получает названия. С названиями выбор фигур Махараджи перестаёт быть делом вкуса и становится тем, что можно проверить.

Четыре неожиданных результата

Мы дали компьютеру решить каждое окончание «король и одна фигура против голого короля». Выделяются четыре результата.

1. Слон и конь в одной фигуре матуют. Ни слон, ни конь не могут форсировать мат со своим королём. Архиепископ, который является обоими, матует из любой позиции.
2. Ходы складываются точно. На пустой доске у слона в среднем 8,75 хода, у коня 5,25. У Архиепископа 14,00 — ровно сумма и столько же, сколько у ладьи, потому что конь никогда не прыгает на поле, куда мог бы дойти слон.
3. Махараджа быстр. Вместе со своим королём он матует голого короля не более чем за 4 хода из любой позиции. Ферзю нужно до 10.
4. Цвет решает. Ни одна фигура, у которой каждый ход меняет цвет поля, не смогла заматовать сама, конь в их числе. Это закономерность, замеченная на 18 фигурах, а не доказательство.

Полные таблицы — во второй части, в разделе Что показывают вычисления.

Что утверждается, а что нет

Утверждается: три новые фигуры Махараджи — это ровно те сочетания ходов ладьи, слона и коня, которые шахматы пропустили.

Не утверждается: что это единственные возможные новые фигуры (доска допускает больше триллиона симметричных), или что геометрия решает, насколько фигура сильна в игре. Вторая часть даёт доказательства и границы полностью.

Вопрос

В Maharajah к шести шахматным фигурам добавлены три: Махараджа ходит как ферзь и конь, Канцлер — как ладья и конь, Архиепископ — как слон и конь. Естественный вопрос: почему именно эти три? Выбор так же произволен, как в сотнях вариантов сказочных шахмат, или он чем-то определён?

Чтобы ответить не по вкусу, а строго, мы описываем ходы на языке математики: как векторы на решётке, упорядоченные группой симметрий квадрата. Тогда вопрос «каких фигур не хватает» становится вопросом о конечном множестве, а конечное множество можно проверить полным перебором.

Ход как вектор

Пусть фигура стоит на поле (x, y). Ход переводит её на поле (x + dx, y + dy). Пару (dx, dy) назовём вектором хода. Фигура может использовать вектор двумя способами:

• прыжок: один шаг на вектор, промежуточные поля не важны (так ходит конь);
• скольжение: повторять тот же шаг, пока поле свободно (так ходят ладья и слон).

На доске 8×8 каждая из координат dx и dy лежит от −7 до 7, так что ненулевых векторов 15 × 15 − 1 = 224. Это все ходы, которые допускает доска. На рисунке 3 показан каждый из них: центр — поле фигуры, каждая клетка — один вектор. Нажмите на любую клетку, чтобы увидеть её направление и фигуры, которые им пользуются.

Почему 15, а не 8: вектор не зависит от того, где стоит фигура. С вертикали a фигура может уйти не дальше чем на 7 вертикалей вправо, dx = +7 (a → h); с вертикали h — не дальше чем на 7 влево, dx = −7 (h → a). Возможно и любое значение между ними, и 0 тоже, так что dx принимает 7 + 1 + 7 = 15 значений, и dy так же. Отсюда сетка 15 × 15 с фигурой в центре; отбрасываем только вектор (0, 0) — стоять на месте. С любого одного поля на доске остаются лишь 63 из этих векторов (по одному на каждое другое поле), но какие именно 63 — зависит от поля: в углу все они смотрят в одну сторону, в центре — во все стороны.

Ходы складываются: два хода подряд — это один ход, (dx₁, dy₁) + (dx₂, dy₂) = (dx₁ + dx₂, dy₁ + dy₂). С таким сложением векторы образуют аддитивную группу ℤ²: сумма двух векторов — снова вектор, порядок не важен (v + w = w + v), (0, 0) — нуль, и у каждого вектора v есть противоположный −v, для которого v + (−v) = 0. Сетка 15 × 15 — это окно в эту группу, а не отдельная группа: (7, 0) + (7, 0) = (14, 0) на доску уже не помещается.

Простыми словами: «два вверх, потом один вправо» и «один вправо, потом два вверх» заканчиваются на одном и том же поле; стоять на месте — это нулевой ход; и любой ход отменяется тем же ходом назад.

Симметрия квадрата

Поверните доску на 90° или отразите её — ладья останется ладьёй, конь конём. У квадрата восемь таких преобразований: четыре поворота и четыре отражения. Вместе они образуют группу диэдра D₄, группу симметрий квадрата. Фигура, правила которой не зависят от того, как повёрнута доска (все классические, кроме пешки), вместе с каждым вектором содержит и все его образы под действием D₄.

Каждая симметрия — это целочисленная матрица, действующая на векторы ходов: поворот на четверть оборота переводит (x, y) в (−y, x), отражение относительно диагонали переводит (x, y) в (y, x). Поэтому симметрии сохраняют сложение, g(v + w) = g(v) + g(w): повернуть доску после двух ходов — то же самое, что повернуть каждый ход и сложить их. На языке групп D₄ действует на ℤ², и каждая симметрия — автоморфизм ℤ². Поворот на пол-оборота переводит каждый v в −v, поэтому у симметричной фигуры вместе с каждым ходом всегда есть и ход назад.

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

Множество образов одного вектора называется его орбитой, и орбиты — это и есть эти классы. Размер орбиты даёт теорема об орбите и стабилизаторе: |орбита| = 8 / |стабилизатор|, где стабилизатор — симметрии, оставляющие вектор на месте. Вектор на линии или диагонали сохраняется одним отражением, поэтому в его орбите 4 направления. Косой вектор, как у коня, не сохраняет ни одна симметрия, поэтому направлений 8.

Простыми словами: возьмём шаг ладьи (1, 0). Поворот доски на 90° даёт (0, 1), (−1, 0) и (0, −1), но если перевернуть доску сверху вниз, (1, 0) остаётся на месте, так что восемь симметрий дают каждое из четырёх направлений дважды. У шага коня (2, 1) такой симметрии нет: все восемь дают разные векторы, они перечислены ниже.

Откуда 7, 7 и 21. Орбиту задают две длины шага, взятые без знака. Линейная орбита — это (a, 0), где a от 1 до 7: 7 орбит по 4 вектора, (±a, 0) и (0, ±a). Диагональная орбита — это (a, a): тоже 7 орбит по 4, (±a, ±a).

Косая орбита — это пара двух разных чисел от 1 до 7, и порядок в паре не важен: (2, 1) и (1, 2) лежат в одной орбите. Таких пар 7 · 6 / 2 = 21: {2, 1}, {3, 1}, {3, 2}, {4, 1} … {7, 6}, и в каждой орбите 8 векторов: 2 порядка × 4 комбинации знаков. Например, орбита коня — это (2, 1) (1, 2) (−1, 2) (−2, 1) (−2, −1) (−1, −2) (1, −2) (2, −1). Проверка: 28 + 28 + 168 = 224 вектора в 7 + 7 + 21 = 35 орбитах. Проще говоря, 35 — это число разных ходов без учёта направления: 7 длин для ладьи, 7 для слона и 21 «конская» форма.

Тот же итог получается, не перечисляя ни одной орбиты. Лемма Бернсайда говорит, что число орбит равно среднему числу векторов, которые симметрия оставляет на месте. Возьмём всю сетку 15 × 15 вместе с нулём: тождественная симметрия оставляет на месте все 225 векторов, каждый из трёх поворотов — только (0, 0), а каждое из четырёх отражений — 15 векторов на своей оси. Итак, число орбит (225 + 3 · 1 + 4 · 15) / 8 = 288 / 8 = 36: 35 направлений и нулевой вектор, который один образует отдельную орбиту.

Почему базовых ходов ровно три. Ненулевой вектор остаётся на месте либо при отражении относительно оси, проходящей через стороны квадрата (векторы на линии), либо при отражении относительно диагонали (диагональные векторы), либо только при тождественной симметрии (косые векторы). Значит, типов направлений три, и не больше. Кратчайший вектор каждого типа — (1, 0), (1, 1) и (2, 1): шаг ладьи, шаг слона и прыжок коня. Шахматы строят свои дальнобойные фигуры из наименьшего представителя каждого типа, поэтому эти три выделяет геометрия, а не вкус.

Теорема о замыкании

Обозначим три дальнобойных хода шахмат: R — скольжение по линии, B — скольжение по диагонали, N — прыжок коня. Объединение X ∨ Y двух фигур — это фигура, которая может ходить как X или как Y. Ферзь — первый пример: Q = R ∨ B. Объединение ассоциативно, коммутативно и идемпотентно, поэтому фигуры из этих трёх ходов образуют булеву решётку подмножеств {R, B, N}.

Простыми словами: порядок в объединении не важен (R ∨ N — та же фигура, что и N ∨ R), а добавление хода, который у фигуры уже есть, ничего не меняет (R ∨ R = R). Поэтому фигуру, составленную из R, B и N, полностью описывает то, какие из трёх ходов у неё есть.

Объединение — не групповая операция. Ходы складываются в группу, но у объединения фигур нет обратного: ход, однажды добавленный, никакое другое объединение уже не уберёт. Поэтому фигуры образуют решётку, а не группу. Группа решает, из чего строятся фигуры, а объединение — как они сочетаются.

То же без символов: каждый из R, B и N либо есть в фигуре, либо нет, это даёт 2 · 2 · 2 = 8 комбинаций. Одна из них не содержит ничего и фигурой не является, остаётся 7. Рис. 1 и таблица в первой части показывают все семь.

Два следствия. Первое: Maharajah не вводит ни одного нового направления — все её фигуры пользуются теми же тремя орбитами из 35, что и классические шахматы. Второе: набор минимален. Без любой из трёх новых фигур он перестаёт быть замкнутым, а любая другая добавленная фигура принесла бы новый ход.

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

Сколько всего фигур возможно

Симметричная фигура определяется тем, что она делает с каждой из 35 орбит: не использует, прыгает или скользит. Скольжение отличается от прыжка, только если на доске помещается хотя бы два шага, то есть когда 2·max(|dx|, |dy|) ≤ 7. Это ровно 9 орбит длиной до 3; у остальных 26 только два варианта.

Почему для скольжения нужно 2·max(|dx|, |dy|) ≤ 7: скользящая фигура делает один и тот же шаг снова и снова, так что второй шаг заканчивается вдвое дальше. Вдоль (3, 0) фигура с вертикали a достаёт d, а затем g: два шага помещаются. Вдоль (4, 0) для второго шага нужно 8 вертикалей, а доска даёт не больше 7, так что «скользить вдоль (4, 0)» и «прыгать вдоль (4, 0)» — одна и та же фигура. Столбец длины считает орбиты по большей координате: у длины L L + 1 орбит, (L, 0), (L, 1) … (L, L). Поэтому длины от 1 до 3 дают 2 + 3 + 4 = 9 орбит, а длины от 4 до 7 — 5 + 6 + 7 + 8 = 26.

Выборы независимы, поэтому они перемножаются. Уже две орбиты по три варианта дают 3 · 3 = 9 комбинаций. Для всех 35: 3⁹ = 19 683 для коротких орбит умножить на 2²⁶ = 67 108 864 для длинных. Одна комбинация не использует ни одной орбиты: «фигура», которая вообще не ходит. Поэтому и вычитаем 1.

Итак, симметричных фигур на доске 8×8 ровно 3⁹ · 2²⁶ − 1 = 1 320 903 770 111, больше 1,3 триллиона. И это без фигур, которые ходят только вперёд (пешка, фигуры сёги), без фигур, перепрыгивающих через другие (кузнечик, пушка сянци), и без фигур, которым можно преградить путь (конь сянци). Вывод простой: ни один набор фигур не может быть «полным» среди всех возможных. Полнота имеет смысл только относительно выбранной базы.

Более широкая база: 17 фигур

А если включить в базу короткие шаги? По линии у фигуры может не быть хода, быть шаг W или скольжение R; по диагонали — ничего, шаг F или скольжение B; плюс конь или нет. Получается 3 · 3 · 2 − 1 = 17 фигур. В классических шахматах их 5 (король — только как королевская фигура), в Maharajah — 8. Остальные девять известны из других традиций: ферзь шатранджа, драконы сёги, сказочные фигуры.

Считаем так же, как в разделе «Сколько всего фигур возможно»: 3 варианта вдоль линий × 3 вдоль диагоналей × 2 для коня = 18, а одна комбинация, где нет ничего, фигурой не является.

Атлас известных фигур

Ниже 31 фигура из шахмат, Maharajah, шатранджа (старинной персидской игры, от которой происходят шахматы), сянци (китайских шахмат), сёги (японских шахмат) и сказочных шахмат. Каждая миниатюра показывает ходы с поля d4 на пустой доске. Нажмите на фигуру, чтобы открыть её на большой доске. Там её можно переставлять нажатием на поле и включать тепловую карту — сколько ходов у неё с каждого поля.

Что показывают вычисления

Для каждой фигуры мы посчитали подвижность на пустой доске и решили эндшпиль «король и фигура против голого короля» полным перебором всех позиций (около 262 тысяч для каждой очерёдности хода). Решатель проверен на известных результатах: самый длинный мат ферзём вышел 10 ходов, ладьёй — 16, как в эндшпильных таблицах.

Откуда 262 тысячи: белый король, чёрный король и белая фигура могут стоять каждый на любом из 64 полей, и 64 · 64 · 64 = 262 144. Расстановки, где двое стоят на одном поле или короли стоят рядом, нелегальны и пропускаются.

Среднее: среднее число ходов по 64 полям. Угол и центр: наименьшее и наибольшее число ходов с одного поля. Диаметр: наибольшее число ходов между двумя полями. Форсированный выигрыш: доля позиций (ход белых), где мат форсирован. Самый длинный мат: в ходах, при лучшей игре обеих сторон. Фигуры Maharajah выделены.

Betza — стандартная короткая запись ходов сказочных фигур. W — один шаг по линии, F — один шаг по диагонали, N — прыжок коня, K = W + F — шаг короля; R, B и Q скользят, и удвоенная буква тоже скользит (NN, ночной всадник). Буквы сочетаются: RN ходит как ладья и как конь. В записи пешки mfWcfF m значит только ход, c — только взятие, f — вперёд.

Четыре вывода, которые следуют из одной лишь геометрии:

1. Подвижность складывается точно. Вектор коня не кратен ни одному вектору линии или диагонали, поэтому поля коня никогда не совпадают с полями скольжения: A = B + N = 8,75 + 5,25 = 14,00, ровно как у ладьи.
2. Объединение умеет то, чего не умеет ни одна часть. Ни слон, ни конь не ставят мат в одиночку, а Архиепископ матует из любой позиции. Причина — в цвете полей (рис. 6).
3. Махараджа матует не более чем за 4 хода из любой позиции; ферзю нужно до 10.
4. Чётность. Ни одна фигура, у которой каждый ход меняет цвет поля (W, N, W+N, ночной всадник), не матует в одиночку. Это закономерность на 18 фигурах, а не доказательство.

Простыми словами: пронумеруйте вертикали и горизонтали от 1 до 8 и сложите два числа. У тёмных полей сумма чётная, у светлых — нечётная. Ход слона меняет сумму на чётное число, поэтому слон никогда не меняет цвет. Ход коня меняет её на 1 или 3, нечётное число, поэтому конь меняет цвет на каждом ходу. У архиепископа есть оба хода, и он может попасть на любое поле, поэтому он ставит мат, а слон и конь поодиночке — нет.

Границы утверждения

Чтобы вывод не прочитали шире, чем он доказан:

• Не все возможные фигуры. В Maharajah 7 из более чем 1,3 триллиона симметричных фигур. Полна она относительно объединения на базе {R, B, N}, то есть относительно собственных дальнобойных ходов шахмат.
• Скольжение конём. Для линии и диагонали в шахматах есть и шаг (король), и скольжение (ладья, слон), а для коня — только прыжок. Ночного всадника, скользящего по вектору коня, нет ни в шахматах, ни в Maharajah.
• Другие классы фигур — ходящие только вперёд, перепрыгивающие через другие фигуры или те, которым можно преградить путь, — лежат вне этой модели.
• Сила и ценность. Геометрия не определяет, сколько фигура стоит в игре. Это вопрос для измерений движком, а не для этой статьи.

История идеи

Набор шахматных фигур всегда достраивался. В шатрандже на месте ферзя был ферз — шаг по диагонали, а на месте слона — альфил, прыжок на (2, 2). В конце XV века в Европе их заменили современные ферзь (R ∨ B) и слон, и именно тогда объединение ходов вошло в шахматы.

Объединять ладью и слона с конём предлагали много раз: Пьетро Каррера (1617) на доске 10 × 8, Генри Бёрд (1874), Хосе Рауль Капабланка (1920-е) с Канцлером и Архиепископом, Кристиан Фрилинг в Grand Chess (1984) на 10 × 10, Яссер Сейраван и Брюс Харпер в Seirawan Chess (2007) на 8 × 8. Ферзь с конём (амазонка) встречается в региональных и сказочных шахматах. Исторические даты приведены по общеизвестным источникам, без проверки первоисточников.

Новое в Maharajah — не сами фигуры, а то, что все семь объединений собраны на обычной доске 8 × 8, а игроки строят армии из одинакового бюджета.

Методы и воспроизводимость

Все числа посчитаны программами, а не взяты из литературы. kxk.c (язык C, около 3 секунд) считает подвижность, привязку к цвету и диаметр и решает эндшпиль K + X против K ретроградным анализом: от позиций мата назад, по полхода, пока множество выигранных позиций не перестанет расти. Легальные позиции: короли не рядом, фигура не на поле короля; пат — ничья; чёрный король может взять незащищённую фигуру. Миниатюры на этой странице рисуются из тех же определений ходов. Исходный код kxk.c открывается в браузере по ссылке выше: скомпилируйте его командой cc -O2 kxk.c -o kxk и запустите ./kxk.

Вывод

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

А математика всё время была на доске. Каждый игрок, который знает, что слон держится своего цвета, что прыжок коня можно отменить или что схема работает так же на другом фланге, пользовался векторами, симметрией и чётностью, не зная их названий.

Собрать армию из этих фигур можно в конструкторе армии, а как ходит каждая — посмотреть в разделе Обучение.