# Розділ 17. Комп’ютерний аналіз

Комп’ютерний аналіз Aether Neutral 4×4 дозволяє оцінити складність гри, перевірити гіпотези, побудувати ендшпільні таблиці та створити штучний інтелект, здатний грати на високому рівні. У цьому розділі ми розглянемо основні алгоритми, оцінку складності, результати повного перебору для 3×3 та відкриті проблеми для 4×4.

## 17.1. Представлення стану для комп’ютера

Для ефективного аналізу необхідно компактно кодувати позицію. У 4×4 дошка має 16 клітинок. Кожна клітинка може бути порожньою або містити одну з 15 масок. Отже, стан можна закодувати як 16 чисел (від 0 до 15), що займає 16×4 = 64 біти (якщо використовувати 4 біти на клітинку). Додатково потрібно зберігати лічильник ходів без злиття (6 біт, оскільки 0–50) та чергу ходу (1 біт). Загалом \~71 біт. Це дозволяє зберігати велику кількість позицій у пам’яті.

Для прискорення пошуку використовуються хеш-таблиці (Zobrist hashing) для зберігання вже обчислених позицій. Симетрії дошки можна використовувати для редукції: зберігати лише канонічне представлення позиції (наприклад, трансляцією змістити так, щоб фігура з певною маскою опинилася в куті).

## 17.2. Алгоритми та ШІ

### 17.2.1. Випадковий AI

Найпростіший AI вибирає випадковий хід серед усіх можливих. Такий гравець слугує базовим рівнем для тестування.

### 17.2.2. Мінімакс з альфа-бета відсіченням

Класичний алгоритм для ігор з повною інформацією. Для Aether 4×4 фактор розгалуження становить у середньому \~100. При глибині пошуку 4 ходи (що дає \~10⁸ листів) це вже вимагає значних ресурсів. Використання альфа-бета відсічення та впорядкування ходів (наприклад, спочатку перевіряти злиття, потім ходи фігур ваги 3 тощо) може збільшити глибину до 5–6.

Оціночна функція (евристика) має вирішальне значення. Для Aether ми пропонуємо:

```
E = sum_i (w_i^2) + sum_i threat_potential(P_i) - penalty
```

де:

* `w_i` – вага i-ї фігури;
* `threat_potential(P)` – кількість фігур з відсутнім для P типом на відстані 1;
* `penalty` – штраф за фігуру ваги 3, яка атакує фігуру з відсутнім типом (оскільки це може дати супернику виграш).

Така евристика дозволяє AI оцінювати позицію навіть на невеликій глибині.

### 17.2.3. MCTS (Monte Carlo Tree Search)

MCTS особливо ефективний для ігор з високим розгалуженням і складними оцінками позицій. Алгоритм складається з чотирьох етапів: вибір, розширення, симуляція, зворотне поширення. Для Aether MCTS може досягати високого рівня гри без явної евристики, покладаючись на велику кількість симуляцій. Експерименти показують, що MCTS з кількістю ітерацій 10⁵–10⁶ грає на рівні сильного любителя.

### 17.2.4. Навчання з підкріпленням (Reinforcement Learning)

Можна навчити нейронну мережу оцінювати позиції, граючи саму з собою (self-play). Такий підхід використовувався для шахів (AlphaZero) і го. Для Aether 4×4 це цілком реалізовано. Мережа може навчитися оцінювати позиції без явної евристики. Результати можуть перевершити MCTS за швидкістю та якістю гри.

## 17.3. Результати повного перебору для 3×3

Варіант 3×3 з 3 типами був повністю проаналізований за допомогою ретроспективного аналізу (retrograde analysis). Основні результати:

* Перший гравець має виграшну стратегію.
* Мінімальна кількість ходів до перемоги за оптимальної гри – 2.
* Кількість досяжних станів (з урахуванням симетрій) становить близько 1.2×10⁶.
* Жодна позиція не потребує більше 10 ходів до перемоги за оптимальної гри.

Ці результати підтверджують, що для 3×3 гра є відносно простою, але вже демонструє основні тактичні принципи.

## 17.4. Оцінка складності для 4×4

Повний перебір для 4×4, хоча теоретично можливий, потребує величезних ресурсів. Оцінка простору станів (з урахуванням симетрій) становить \~10³⁰–10³⁵. Зберігання такої кількості позицій неможливе навіть з використанням сучасних суперкомп’ютерів. Однак можна виконати аналіз ендшпільних позицій (з малою кількістю фігур) та використовувати символьні методи.

Для позицій з 2–3 фігурами можна побудувати повні ендшпільні таблиці. Наприклад, для 2 фігур кількість можливих конфігурацій (розташування + маски) становить C(16,2) × 15 × 15 ≈ 120 × 225 = 27 000, що з урахуванням симетрій зводиться до кількох сотень. Це дозволяє обчислити виграшність для всіх таких позицій.

## 17.5. Відкриті проблеми

1. **Повний розв’язок 4×4**. Чи має перший гравець виграшну стратегію? Якщо так, то за скільки ходів? Чи можливі нічиї (окрім правила 50 ходів)? Відповіді на ці питання потребують або повного перебору, або аналітичного доведення.
2. **Існування інваріантів вищого порядку**. Чи існують інваріанти, що дозволяють передбачити результат без повного перебору? Наприклад, деякі комбінації XOR можуть бути інваріантними за модулем 2.
3. **Складність гри (PSPACE-повнота)**. Чи є Aether Neutral PSPACE-повною (тобто чи можна змоделювати будь-яку гру з обмеженою пам’яттю)? Це питання потребує дослідження.
4. **Оптимальна стратегія для 5×5**. Якщо 4×4 не розв’язана, то для 5×5 проблема ще складніша. Чи можна знайти евристики, які гарантують перемогу?

## 17.6. Практичні рекомендації для розробників ШІ

* Використовуйте бітове представлення та Zobrist hashing для прискорення.
* Застосовуйте MCTS з великою кількістю симуляцій (≥10⁵) для досягнення хорошого рівня.
* Для навчання з підкріпленням використовуйте self-play та зберігайте досвід у replay buffer.
* Впровадьте симетрії для збільшення різноманітності навчальних даних.
* Експериментуйте з евристиками: вага фігур, загрози, відстані.

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

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

* описали компактне представлення стану для комп’ютера;
* розглянули основні алгоритми: випадковий AI, мінімакс, MCTS, навчання з підкріпленням;
* навели результати повного перебору для 3×3;
* оцінили складність 4×4 та окреслили можливість ендшпільних таблиць;
* сформулювали відкриті проблеми;
* надали практичні рекомендації для розробників ШІ.

Комп’ютерний аналіз Aether Neutral 4×4 відкриває широке поле для досліджень, від створення сильного AI до доведення теоретичних властивостей гри.

***


---

# 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/17_computer_analysis.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.