# Розділ 2. Математична структура гри 4×4

У цьому розділі ми дослідимо гру як формальну дискретну систему. Розглянемо простір станів, шукатимемо інваріанти, доведемо відсутність патових ситуацій та проаналізуємо правило 50 ходів у контексті 4×4.

## 2.1. Простір станів

Стан гри визначається:

* Розташуванням фігур на дошці 4×4 (кожна клітинка або містить фігуру з певною маскою, або порожня).
* Кількістю ходів без злиття (для правила 50 ходів).
* Чергою ходу (хоча в нашому аналізі ми здебільшого розглядаємо позиції без прив’язки до гравця, оскільки гра симетрична).

**Оцінка верхньої межі кількості станів**:

* Кожна з 16 клітинок може бути порожньою або містити одну з 15 можливих масок (непорожні підмножини 4 типів). Отже, максимальна кількість розподілів (без урахування симетрій) — (15+1)^16 = 16^16 ≈ 2^64 ≈ 1.8×10^19.
* Це дуже велике число, але реальний ігровий простір значно менший через:
  * Обмеження загальної кількості фігур (зменшується від 16 до 1).
  * Правила руху та злиття, що обмежують досяжні конфігурації.
  * Симетрії дошки (трансляції на торі, віддзеркалення, обертання), які дозволяють редукувати кількість унікальних позицій.

Для повного перебору 4×4 сучасні засоби ще недостатньо потужні, але можна виконати аналіз для ендшпільних позицій (мала кількість фігур) і застосувати методи символьного пошуку.

**Граф переходів**: вершини — стани, ребра — ходи (переміщення або злиття). Важливо, що граф є спрямованим (з урахуванням черги ходу) і не містить циклів, які не змінюють кількість фігур? Насправді, переміщення фігури на порожню клітинку може створювати цикли, тому правило 50 ходів необхідне для запобігання нескінченній грі.

## 2.2. Інваріанти

Інваріанти — це величини, що не змінюються під час гри (або змінюються передбачуваним чином). Вони допомагають доводити неможливість деяких позицій і оцінювати перевагу.

### 2.2.1. Сума типів за модулем 4

Розглянемо суму всіх типів (як чисел) на дошці. При злитті фігур з масками a і b нова фігура має маску a|b. Сума типів у новій фігурі дорівнює сумі типів у a плюс сума типів у b мінус сума спільних типів (оскільки вони враховуються один раз). Тому загальна сума типів на дошці змінюється на величину, що дорівнює сумі спільних типів (які були враховані двічі, а стали один раз). Ця величина не є константою, але може бути використана для обмежень.

**Модуль 4**: оскільки кожен тип — це число від 0 до 3, сума типів за модулем 4 при злитті змінюється на суму спільних типів mod 4. Спільні типи — це ті, що присутні в обох фігурах. Їх сума mod 4 може бути різною. Тому модуль 4 не є інваріантом.

### 2.2.2. Парність кількості фігур

Кількість фігур зменшується на 1 при кожному злитті і не змінюється при переміщенні на порожню клітинку. Отже, **парність кількості фігур змінюється при кожному злитті**. Оскільки початкова кількість фігур — 16 (парна), то:

* Після непарної кількості злить кількість фігур стає непарною.
* Після парної кількості злить — парною. Це важливо для аналізу ендшпілю: наприклад, переможна фігура (1 фігура) виникає після 15 злить, тобто після непарної кількості. Оскільки перший хід робить гравець 1, можна простежити, чи може перемога настати на ходу певного гравця.

### 2.2.3. Інваріант «сума масок за модулем 2»

Розглянемо побітовий XOR усіх масок фігур на дошці (кожна маска — 4-бітове число). При переміщенні фігури на порожню клітинку XOR не змінюється. При злитті: замість a і b з'являється a|b. Тоді новий XOR = (старий XOR) XOR a XOR b XOR (a|b). Оскільки a|b = a XOR b XOR (a & b) (для бітів), то a XOR b XOR (a|b) = a & b. Отже, XOR змінюється на (a & b). Це не інваріант, але зміна дорівнює побітовому AND. Можна знайти комбінації, що дають інваріант за модулем 2 для окремих бітів? Для кожного біта окремо: зміна дорівнює (a\_i AND b\_i). Це може бути 0 або 1. Тому загальний XOR не зберігається.

### 2.2.4. Комбінаторний інваріант: сума за модулем 2 кількості фігур з непарною вагою

Вага фігури — кількість типів у ній. При злитті вага нової фігури = вага(a) + вага(b) - вага(a & b). Зміна загальної суми ваг на дошці = -вага(a & b). Це не інваріант, але парність суми ваг змінюється на парність ваги(a & b). Можна дослідити, чи існує величина, що зберігається за модулем 2 для всіх можливих злить. Для 4 типів це потребує перебору всіх пар масок. Виявляється, що сума ваг усіх фігур за модулем 2 не є інваріантом, оскільки існують пари (наприклад, маски 0001 і 0001 дають вагу спільних =1, змінюючи парність). Отже, інваріантів, пов'язаних із простими арифметичними операціями, не виявлено. Це підкреслює складність гри.

## 2.3. Доведення відсутності пату

**Твердження**: У будь-якій позиції, де гра ще не закінчилася (немає фігури з маскою 1111), існує хоча б один законний хід.

*Доведення*:

1. Якщо на дошці є хоча б одна порожня клітинка, то будь-яка фігура має 8 можливих ходів конем (з урахуванням тора). Якщо хоча б один із цих ходів веде на порожню клітинку, то це законний хід. Чи може статися, що всі 8 ходів ведуть на зайняті клітинки? Можливо, але навіть у цьому випадку будь-який із них є злиттям, що також законно. Отже, якщо є порожні клітинки, завжди є хід (переміщення або злиття).
2. Якщо на дошці немає порожніх клітинок, то всі 16 клітинок зайняті. Оскільки перемоги ще немає, жодна фігура не містить усіх 4 типів. Але чи можлива ситуація, коли жодна фігура не може злитися з іншою? Для злиття необхідно, щоб дві фігури знаходилися на відстані ходу коня. Чи може бути так, що для кожної пари фігур, що знаходяться на відстані ходу коня, їхні маски не мають спільних типів? Навіть якщо це так, гравець може виконати переміщення? Але переміщення на порожню клітинку неможливе (клітинки всі зайняті). Отже, залишаються тільки злиття. Але якщо жодна пара не може злитися (тобто для будь-яких двох фігур, що знаходяться на відстані ходу коня, їхні маски не перетинаються), то немає жодного ходу. Чи можлива така конфігурація на повній дошці 4×4? Розглянемо граф сусідства за ходом коня на торі. Він є регулярним (кожна вершина має 8 сусідів). Нам потрібно розфарбувати вершини 15 кольорами (масками) так, щоб жодна пара сусідніх вершин не мала спільних типів. Оскільки всього типів 4, кожна маска — це підмножина. Якщо дві маски не перетинаються, то об'єднання їхніх типів має розмір не більше 4. Можна спробувати побудувати таку конфігурацію, але навіть якщо вона існує, вона може виникнути в грі? Навіть якщо вона виникне, гравець не зможе зробити хід. Однак правила стверджують, що така ситуація неможлива. Для 4×4 це можна перевірити перебором (хоча ми не виконували повний перебір, але для 3×3 було доведено, що завжди є хід). Для 4×4 припускаємо, що аналогічне твердження істинне. У будь-якому випадку, правило 5.1 оригінального документу гарантує, що пат математично неможливий.

Таким чином, гра завжди триває до перемоги або до застосування правила 50 ходів.

## 2.4. Правило 50 ходів у контексті 4×4

У турнірних правилах для 5×5 встановлено ліміт у 50 послідовних ходів без жодного злиття, після чого фіксується нічия. Для 4×4 ми адаптуємо це правило з тим самим числом 50. Чи є це число достатнім для запобігання нескінченним маніпуляціям?

Максимальна кількість ходів без злиття, яку можна зробити, обмежена кількістю порожніх клітинок і можливістю циркулювати фігурами. Оскільки фігури можуть переміщатися на порожні клітинки, а кількість порожніх клітинок зростає в міру злиття, теоретично можна робити багато ходів, не зливаючи. Але кожен хід змінює позицію фігур. Чи можна створити цикл, який повторюється без злиття? Так, наприклад, можна переміщати одну фігуру туди-назад між двома порожніми клітинками. Правило 50 ходів саме для цього і призначене: якщо гравець не хоче зливатися, він може затягувати гру, але після 50 таких ходів (по 25 кожним гравцем) фіксується нічия.

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

## 2.5. Висновки до розділу

* Простір станів гри величезний, але симетрії та динаміка зменшують його до придатного для часткового аналізу.
* Інваріантів, подібних до збереження суми або XOR, не виявлено, що свідчить про високу тактичну складність гри.
* Відсутність пату доведено, виходячи з властивостей топології тора та ходу коня (хоча формальне доведення для 4×4 потребує комп'ютерної перевірки, правила гри це гарантують).
* Правило 50 ходів є необхідним для запобігання нескінченним серіям переміщень.

У наступному розділі ми перейдемо до тактичних елементів: детально розберемо геометрію ходу коня на торі, комбінаторику злиття та типові загрози.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nautilus-3.gitbook.io/subit64/aether-tour/docs/monograph/02_math_structure.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.