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

У попередніх розділах ми розглянули математичні основи, тактику та стратегію гри Aether Neutral 4×4. Тепер звернемося до комп’ютерного аналізу: які обчислення можливі для 4×4, які алгоритми можна застосувати для гри проти ШІ, і які проблеми залишаються відкритими для 5×5 та загалом для гри.

## 7.1. Повний перебір для 4×4

### 7.1.1. Оцінка складності

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

### 7.1.2. Можливі підходи до повного аналізу

* **Ретроспективний аналіз (retrograde analysis)**: починаючи з переможних позицій (фігура з маскою 1111), можна обчислити всі позиції, з яких гравець може виграти за певну кількість ходів. Це потребує зберігання великої кількості станів, але для 4×4 це потенційно реалізовано.
* **Симетрії**: зменшення кількості унікальних позицій за рахунок симетрій дошки (група D4 × трансляції) дає зменшення приблизно в 16 разів (для тора – група симетрій більша, але точно оцінити складно).
* **Бітове стиснення**: кожен стан можна закодувати в 128 біт (16 клітинок × 4 біти на маску + додаткова інформація). Це дозволяє зберігати великі бази даних.

Наразі невідомо, чи було виконано повний аналіз 4×4. Однак на основі результатів для 3×3 (який був розв’язаний) можна припустити, що 4×4 також може бути розв’язана, але потребує значних обчислювальних ресурсів.

### 7.1.3. Результати часткового аналізу

Для ендшпільних позицій (з малою кількістю фігур) можна виконати повний перебір. Наприклад, для 2 фігур аналіз є тривіальним: перемога можлива лише якщо їхні маски в об’єднанні дають 1111 і вони на відстані ходу коня. Для 3 фігур вже існує кілька десятків типів позицій, які можна класифікувати. Такий аналіз допомагає створити ендшпільну таблицю для ШІ.

## 7.2. Штучний інтелект для гри

### 7.2.1. Алгоритми

Для створення AI, здатного грати на рівні людини або вище, можна використовувати:

* **Випадковий AI (Random)**: базовий рівень, робить випадковий хід серед усіх можливих. Використовується для тестування.
* **Мінімакс з альфа-бета відсіченням**: класичний алгоритм для ігор з повною інформацією. Глибина пошуку обмежена через велике розгалуження (у 4×4 середня кількість можливих ходів – десятки). З евристичною оцінкою позиції можна досягти глибини 4–5.
* **MCTS (Monte Carlo Tree Search)**: особливо ефективний для ігор з великим простором станів. MCTS дозволяє зосередитись на перспективних гілках без повного перебору. Для 4×4 MCTS може грати на рівні, близькому до оптимального, особливо з використанням симетричних політик.
* **Навчання з підкріпленням (Reinforcement Learning)**: можна навчити нейронну мережу оцінювати позиції, граючи саму з собою. Це вимагає багато ігрового досвіду, але потенційно може досягти суперлюдського рівня.

### 7.2.2. Евристична оцінка позиції

Якісна оціночна функція є ключем до сильного AI. Ми пропонуємо наступну евристику, яку можна використовувати як у мінімаксі, так і для керування MCTS:

```
E = sum_i (w_i^2) + sum_i (p_i * w_i) - penalty_overlap
```

де:

* `w_i` – вага (кількість типів) i-ї фігури.
* `p_i` – потенціал загрози: кількість фігур, які містять типи, відсутні в i, і знаходяться на відстані ходу коня.
* `penalty_overlap` – штраф, якщо дві сильні фігури (вага >= 3) знаходяться близько, оскільки це дає супернику можливість використати їх.

Коефіцієнти можна підібрати експериментально.

### 7.2.3. Використання симетрій

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

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

### 7.3.1. Повний розв’язок 4×4

Чи має перший гравець виграшну стратегію? Якщо так, то за скільки ходів? Чи можлива нічия при ідеальній грі? Ці питання залишаються відкритими до виконання повного аналізу.

### 7.3.2. Повний розв’язок 5×5

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

### 7.3.3. Вплив топології

Як зміниться гра, якщо використовувати плоску дошку (без тора)? Це додасть крайові ефекти, зменшить кількість ходів для крайових фігур і змінить стратегію. Порівняльний аналіз може показати, наскільки важливою є топологія тора для динаміки.

### 7.3.4. Варіації з іншими n

Дослідження гри для n×n з n типами для різних n може виявити загальні закономірності. Наприклад, чи завжди перший гравець має виграшну стратегію? Чи існує асимптотична поведінка тривалості гри?

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

* Комп’ютерний аналіз 4×4 є складною, але потенційно здійсненною задачею.
* Алгоритми MCTS та навчання з підкріпленням дозволяють створити сильний AI для практичної гри.
* Для 5×5 повний аналіз неможливий, але евристичні методи можуть дати хороші результати.
* Залишається низка відкритих математичних проблем, які роблять гру цікавою для дослідників.

Наступний розділ підсумовує основні результати монографії та надає рекомендації для гравців і організаторів турнірів.


---

# 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/07_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.