Коефіцієнт розгалуження та кількість вузлів
Дерево гри моделює кожну можливу послідовність ходів від стартової позиції. Кожен вузол представляє стан дошки. Кожен ребро представляє один допустимий хід. Структура дерева визначає, чи пошук залишається виконаним.
Ключові параметри
Коефіцієнт розгалуження b: кількість допустимих ходів, доступних у типовій позиції.
Глибина d: кількість пільок (половинних ходів) для пошуку вперед.
Кількість вузлів на глибині d: b^d
Загальна кількість вузлів на всіх глибинах: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Для великих b та d загальна кількість ≈ b^d (домінує рівень листків).
4×4×4 Хрестики-нулики
Повне дерево гри: b ≈ 64 (допустимі клітинки), d = 64 (всього ходів). Повна кількість вузлів ≈ 64^64 ≈ 10^115. Спостережуваний Всесвіт містить приблизно 10^80 атомів. Прямий перебір фізично неможливий.
Обчислення розміру дерева
Шахи дають реалістичніші числа. Середній коефіцієнт розгалуження b ≈ 35. Пошук на 6 пільок (3 ходи для кожної сторони) вимагає приблизно 35^6 вузлів.
Обрізання альфа-бета: скорочення показника ступеня
Обрізання альфа-бета усуває піддерева, які не можуть вплинути на результат мінімаксу. Ключове прозріння: якщо ви вже знаєте, що одна гілка дає значення V, ви можете обрізати будь-яку гілку-сестру, чиє значення явно падає нижче V (для гравця, що максимізує) або вище V (для гравця, що мінімізує).
Геометрія найкращого випадку
При оптимальному упорядкуванні ходів (найкращі ходи шукаються першими), альфа-бета скорочує ефективний коефіцієнт розгалуження з b на √b. Глибина пошуку ефективно подвоюється за той же бюджет вузлів:
Повний пошук: b^d вузлів
Альфа-бета найкращий випадок: b^(d/2) вузлів
Приклад: b=35, d=6. Повний: 35^6 ≈ 1.84 × 10^9. Альфа-бета: 35^3 = 42,875. Коефіцієнт скорочення: ~43,000.
На практиці упорядкування ходів неідеальне. Типове скорочення: b^(d×0.75) — еквівалентний коефіцієнт розгалуження ≈ b^0.75.
Дуальність центру та кута
Хеммінг відзначає геометричну дуальність у кубі 4×4×4: існує інверсія, що надсилає 8 кутових позицій на 8 центральних позицій (внутрішній куб 2×2×2) & навпаки, зберігаючи всі 76 виграшних ліній.
Підрахунок ліній через позицію
У кубі 4×4×4 позиції розрізняються кількістю виграшних ліній, які проходять через них:
Кутові позиції: по 7 ліній (4 діагоналі грані, 2 лінії ребра, 1 просторова діагональ)
Центральні позиції ребра: по 4 лінії
Центральні позиції грані: по 6 ліній
Центральні позиції корпусу (внутрішній 2×2×2): по 7 ліній
Дуальність відображає кути (7 ліній) на центри корпусу (7 ліній). Обидва набори утворюють «гарячі місця».
Чому гарячі місця мають геометричне значення
Гравець, який контролює більше позицій з високою кількістю ліній, контролює більше потенційних виграшних ліній. Це прямий геометричний аргумент: максимізація покриття ліній керує вибором ходу без будь-якого пошуку.
Функції оцінювання
Кожна програма гри потребує функції оцінювання: функція, що відображає стани дошки на числові значення (позитивне = добре для гравця, що максимізує, негативне = добре для гравця, що мінімізує). Функція оцінювання забезпечує граничну умову на листках дерева пошуку.
Лінійні функції оцінювання
Лінійна функція оцінювання призначає вагу w_i кожній ознаці f_i позиції:
E(позиція) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Для хрестиків-нуликів 4×4×4: ознаки можуть включати контрольовані відкриті лінії, позиції на клітинках з високою кількістю ліній, загрожені вилки. Для шахів: підрахунок матеріалу, контроль центру, безпека короля, структура пішаків.
Це лінійна функція у просторі ознак — гіперплощина в ℝ^n. Дві позиції з однаковими значеннями ознак отримують однакову оцінку незалежно від усіх інших відмінностей. Геометрія функції оцінювання визначає, що бачить програма.
Програма шашок Семюеля покращилась шляхом налаштування вектора ваги w — градієнтний спуск у просторі лінійних функцій оцінювання.
Геометрія та межа формалізації
Дерево гри має чисту геометричну структуру: експоненціальне зростання на глибині d, скорочується до b^(d/2) за альфа-бета, далі скорочується обмеженням до позицій з високою цінністю (гарячі місця скорочують ефективний b). Функція оцінювання визначає гіперплощину у просторі ознак.
Все це чисто, точно, формально завершено. Це описує центр проблеми гри — регіон, де математична структура забезпечує чітке керівництво.
Межа — де перейти від застосування правил до дослідження, коли обмінювати позиційну перевагу на тактичну можливість, як розпізнати появляючись закономірності поза функцією оцінювання — протистоять цій формалізації. Мовчазне знання Хеммінга живе на цій межі.
Геометрія дозволяє обчислити, скільки пошуку ви можете собі дозволити. Вона не говорить вам, що шукати.