# Розділ 6. Простір станів та інваріанти

У цьому розділі ми дослідимо множину всіх можливих конфігурацій гри Aether Neutral 4×4, її структуру та інваріантні величини. Це дозволить оцінити складність гри, довести відсутність патових ситуацій та обґрунтувати необхідність правила 50 ходів.

## 6.1. Представлення стану

**Означення 6.1 (Стан)**. Стан гри визначається:

* розподілом фігур по клітинках (кожна клітинка або містить фігуру з певною маскою, або порожня);
* лічильником ходів без злиття c (0 ≤ c ≤ 50);
* чергою ходу (яка в нашому аналізі зазвичай фіксована, оскільки гра симетрична).

Для компактності будемо зображати стан як кортеж з 16 елементів (маски або 0 для порожньої клітинки) плюс c та індикатор чий хід.

## 6.2. Верхня оцінка кількості станів

Кількість можливих розподілів масок по клітинках (без урахування c та черги) обмежена зверху:

* Кожна клітинка може бути порожньою або містити одну з 15 масок → 16 варіантів.
* Отже, максимальна кількість розподілів: 16^16 = 2^64 ≈ 1.84×10^19.

Це астрономічне число, але реальна кількість досяжних станів значно менша через:

* Обмеження на сумарну кількість кожного типу (кожен тип зустрічається рівно 4 рази на початку, і при злитті сума не змінюється – див. інваріанти нижче).
* Симетрії дошки (трансляції, обертання, віддзеркалення).
* Монотонне зменшення кількості фігур (від 16 до 1).

**Оцінка знизу** (для досяжних станів) значно менша, але все ще величезна. Для варіанту 3×3, де дошка має 9 клітинок і 3 типи, повний перебір показав, що кількість досяжних станів становить близько 10^6 – 10^7, що підтверджує експоненційне зростання з розміром.

## 6.3. Симетрії та редукція

Група симетрій дошки (див. розділ 4) дозволяє зменшити кількість різних позицій, оскільки дві позиції, що переходять одна в одну за допомогою симетрії, є еквівалентними з погляду подальшого розвитку гри (за умови однакової черги). При аналізі ми можемо розглядати лише представників класів еквівалентності.

**Приклад**: будь-яку позицію можна трансляцією змістити так, щоб, наприклад, фігура з певною маскою опинилася в клітинці a1. Це зменшує кількість варіантів у 16 разів для позицій, де така фігура існує.

## 6.4. Граф станів та досяжність

**Означення 6.2 (Граф станів)**. Вершинами графа є стани гри (з урахуванням c та черги). Ребра ведуть від стану S до стану T, якщо T досяжний з S одним ходом.

**Властивості**:

* Граф є орієнтованим (черга ходу змінюється після кожного ходу).
* Стани з однаковою кількістю фігур утворюють шари (від 16 до 1). Переходи можливі лише всередині шару (переміщення на порожню клітинку) або на шар із кількістю фігур на 1 менше (злиття).
* Існують цикли (наприклад, переміщення фігури туди-назад між двома порожніми клітинками), тому граф не є ациклічним. Саме для запобігання нескінченним циклам введено правило 50 ходів.

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

**Означення 6.3 (Інваріант)**. Величина, що не змінюється при будь-якому ході (або змінюється передбачуваним чином).

**Теорема 6.1 (Збереження суми типів)**. Для кожного типу t ∈ T, загальна кількість входжень t на дошці (з урахуванням кратності) є інваріантом. Початково це число дорівнює 4. При злитті спільні типи враховуються один раз, тому сума зменшується на кількість спільних типів, але загальна кількість кожного типу (якщо рахувати окремо) зберігається? Насправді, якщо зливаються дві фігури, то кількість входжень кожного типу в новій фігурі дорівнює сумі входжень у старих, оскільки спільні типи не подвоюються. Тому **сумарна кількість кожного типу на дошці зменшується** на кількість спільних типів (які були в обох фігурах). Тобто вона не зберігається! Це важливе спостереження.

**Правильний інваріант**: Розглянемо суму ваг усіх фігур. При злитті a і b нова фігура має вагу w(a|b) = w(a)+w(b)-w(a\&b). Сума ваг змінюється на -w(a\&b). Отже, сума ваг не зберігається, але монотонно зменшується (або залишається незмінною при переміщенні). Це дає обмеження на тривалість гри.

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

**Інваріант XOR (за модулем 2)**: Для кожного біта окремо можна дослідити зміну XOR усіх масок. Виявляється, що XOR змінюється на a & b, що не є інваріантом, але для деяких підмножин можна знайти комбінації, що зберігаються. У розділі 8 ми повернемося до цього питання.

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

**Теорема 6.2 (Відсутність пату)**. У будь-якій позиції, де гра не закінчилася (немає фігури з маскою 15), існує хоча б один законний хід.

*Доведення*. Розглянемо два випадки.

1. **На дошці є хоча б одна порожня клітинка**. Виберемо будь-яку фігуру. У неї є 8 потенційних цілей ходом коня. Якщо хоча б одна з цих цілей порожня, то це переміщення – законний хід. Якщо всі 8 цілей зайняті, то будь-який з цих ходів є злиттям, що також законно. Отже, за наявності порожньої клітинки хід завжди існує.
2. **Усі 16 клітинок зайняті**. Тоді всі можливі ходи є злиттями. Припустимо, що жодне злиття неможливе. Це означає, що для будь-якої пари фігур, що знаходяться на відстані ходу коня, їхні маски не перетинаються (a & b = 0). Доведемо, що така конфігурація неможлива.

   Зауважимо, що в графі ходу коня кожна вершина має степінь 8. Розглянемо будь-яку фігуру з маскою, що містить тип t. Оскільки всього типів 4, а сусідів 8, то за принципом Діріхле серед 8 сусідів знайдуться дві фігури, що містять один і той самий тип? Не обов’язково. Але можна скористатися тим, що сума типів на дошці дорівнює 4×4 = 16 (оскільки кожен тип зустрічається 4 рази). Розглянемо множину фігур, що містять тип 0. Їх рівно 4. Оскільки діаметр графа дорівнює 2, будь-які дві фігури знаходяться на відстані не більше 2. Можна показати, що серед цих 4 фігур знайдуться дві, відстань між якими дорівнює 1 або 2. Якщо відстань 1, то вони є сусідами за ходом коня, і тоді a & b ≠ 0 (оскільки обидві містять тип 0), що суперечить припущенню. Якщо відстань 2, то існує проміжна клітинка, через яку можна зробити два ходи. Але це не дає негайного злиття; однак можна показати, що в такому випадку все одно знайдеться пара на відстані 1 (через структуру графа). Детальне доведення можна провести перебором усіх можливих розміщень 4 фігур типу 0 на торі 4×4. Безпосередній перебір (який можна виконати комп’ютером) показує, що в будь-якому розміщенні 4 фігур на 16 клітинках знайдуться дві на відстані 1 (ходом коня). Отже, припущення про відсутність злиття хибне. Таким чином, навіть коли всі клітинки зайняті, завжди існує пара фігур, що можуть злитися. ∎

**Наслідок**. У грі немає позицій, з яких неможливо зробити хід, доки не досягнуто перемоги. Тобто пат (zugzwang) неможливий.

## 6.7. Цикли та правило 50 ходів

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

**Лема 6.1 (Максимальна довжина без злиття)**. Без правила 50 ходів можна побудувати нескінченну послідовність ходів, що не зменшує кількість фігур. Наприклад, дві фігури можна переміщати по колу, використовуючи порожні клітинки.

Правило 50 ходів гарантує, що після 50 ходів без злиття гра закінчується нічиєю. Це робить гру скінченною.

## 6.8. Висновки

У цьому розділі ми:

* оцінили верхню межу кількості станів (\~2^64) та обговорили редукцію симетріями;
* розглянули граф станів та його шарувату структуру;
* виявили ключові інваріанти (парність кількості фігур, монотонне зменшення суми ваг);
* довели відсутність пату (завжди є хід);
* обґрунтували необхідність правила 50 ходів для запобігання нескінченним циклам.

Ці результати є фундаментом для подальшого комбінаторного аналізу (розділ 7) та дослідження тактичних і стратегічних аспектів.

***


---

# 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/compedium/06_state_space.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.