Чому в 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 є замиканням шахового набору щодо об'єднання його власних ходів: нічого нового не додано, лише завершено те, що почав ферзь.

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

Зібрати армію з цими фігурами можна в конструкторі армії, а як ходить кожна — подивитися в розділі Навчання.