Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search

Гра як задача пошуку, дерево гри, мінімакс, альфа-бета відсікання, оцінювальна функція і MCTS — на хрестиках-нуликах, де можна порахувати все, і шлях від Deep Blue до AlphaZero.

14 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 22 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

У лабіринті з попередньої частини чоловічок був сам. Світ не рухався, і кожен хід вів туди, куди мав. А в грі навпроти вас сидить хтось, хто хоче точнісінько протилежного, — і на кожен ваш хід відповість тим, який вам найболючіший. Шукати шлях до мети вже недостатньо: треба шукати стратегію, яка встоїть проти будь-якої відповіді. Шахи, шашки й го десятиліттями були мірилом штучного інтелекту, а алгоритми з цієї частини стоять і за Deep Blue, і за AlphaGo.

Ця частина продовжує частини «Пошук у просторі станів» і «Графи й дерева».

1. Гра як задача пошуку

Означення — гра двох гравців

Гра — це сімка Γ = (S, s₀, player, A, T, K, U), де

• S, s₀, A(s) і T — стани, початковий стан, дії та функція переходів, як у задачі пошуку,
• player : S → {MAX, MIN} каже, хто в цьому стані ходить,
• K ⊆ S — множина кінцевих станів, де гра закінчується,
• U : K → ℝ — корисність кінцевого стану з погляду гравця MAX.

Гра має нульову суму: що MAX виграє, те MIN втрачає, тож корисність MIN дорівнює −U. Гравці ходять по черзі, ходи детерміновані, і обидва бачать увесь стан (повна інформація).

Відмінність від пошуку принципова. Розв’язок — уже не шлях: його ви не оберете, бо кожен другий хід робить суперник. Розв’язок — це стратегія: припис, як відповісти на кожен хід, який суперник може зробити.

2. Дерево гри

Означення — дерево гри

Дерево гри — це кореневе дерево, коренем якого є s₀, а діти вузла s — наступники {T(s, a) : a ∈ A(s)}. Листки — кінцеві стани. Вузли, де ходить MAX, малюємо трикутником вершиною вгору, вузли MIN — вершиною вниз.

Якщо гра має коефіцієнт розгалуження b і триває щонайбільше m ходів, то дерево має до b^m листків.

Хрестики-нулики на полі 3 × 3 — мала гра, і все ж їхнє дерево має 549 946 вузлів і 255 168 листків — стільки різних партій можна зіграти. Різних позицій при цьому лише 5 478: до тієї самої позиції можна дійти багатьма порядками ходів. Шахи мають коефіцієнт розгалуження близько 35, а партія триває десятки ходів; Клод Шеннон 1950 року оцінив їхнє дерево в 10¹²⁰ партій. Го з коефіцієнтом розгалуження близько 250 — ще на багато порядків далі. Тож усе дерево ми пройдемо лише в малих іграх — у великих мусимо навчитися, які гілки пропустити.

3. Мінімакс

Означення — мінімаксна цінність

Мінімаксна цінність стану s — це

• MM(s) = U(s), якщо s ∈ K,
• MM(s) = max_{a ∈ A(s)} MM(T(s, a)), якщо player(s) = MAX,
• MM(s) = min_{a ∈ A(s)} MM(T(s, a)), якщо player(s) = MIN.

Оптимальний хід гравця MAX у стані s — це argmax_a MM(T(s, a)).

Лівий вузол MIN із листків 4, 6 і 9 обере 4, середній із 2, 7 і 8 обере 2, правий із 5, 3 і 9 обере 3. MAX у корені тоді обирає між 4, 2 і 3 та робить лівий хід із цінністю 4. Зверніть увагу, що права гілка ховає дев’ятку, — але до неї MAX ніколи не дістанеться, бо MIN замість неї зіграв би трійку.

Теорема — що гарантує мінімакс

Якщо MAX грає оптимально, він здобуде щонайменше MM(s₀) проти будь-якої стратегії MIN. Якщо оптимально грає й MIN, MAX здобуде рівно MM(s₀).

Мінімакс обходить дерево в глибину: час O(b^m), пам’ять O(b · m).

4. Мінімакс на хрестиках-нуликах

Хрестики-нулики 3 × 3 досить малі, щоб мінімакс пройшов усе дерево. Результат знає кожен, хто грав у них довше кількох хвилин: мінімаксна цінність порожнього поля — 0: коли обидва грають без помилок, це завжди нічия. Цікавіше, що мінімакс скаже про конкретну позицію. Ходить X (MAX), і в кожній вільній клітинці — цінність ходу в неї:

Виграє єдиний хід — центр. X цим створює вилку: загрожує заповнити середній рядок і діагональ, а O не може заблокувати обидва. Хід униз посередині тримає нічию. Решта трьох ходів виглядають невинно, але програють: O відповість на них власною вилкою. Людина мусила б це обміркувати; мінімакс це просто обчислює.

def minimax(board):
    end = winner(board)                 # "X", "O", "draw" або None
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    values = [minimax(play(board, move)) for move in empty_squares(board)]
    return max(values) if to_move(board) == "X" else min(values)

5. Альфа-бета відсікання

Мінімакс проходить усе дерево, навіть коли половина його зайва. Погляньте ще раз на середню гілку: перший листок показав 2. Отже, MIN у цій гілці досягне 2 або менше, — а MAX уже має ліву гілку з цінністю 4 напевно. Хоч якими були б решта двох листків, MAX у середню гілку не піде. Йому навіть не треба на них дивитися.

Означення — альфа-бета

Пошук у глибину несе із собою дві межі:

• α — найвища цінність, яку MAX уже забезпечив собі десь на шляху від кореня (спочатку −∞),
• β — найнижча цінність, яку забезпечив собі MIN (спочатку +∞).

У вузлі MAX після кожної дитини встановлюємо v ← max(v, цінність дитини) і α ← max(α, v); у вузлі MIN аналогічно v ← min(…) і β ← min(β, v). Щойно α ≥ β, решту дітей вузла відсікаємо — їх не досліджують.

Теорема. Альфа-бета повертає в корені ту саму цінність, що й мінімакс. За найкращого можливого порядку ходів вона досліджує лише O(b^m/2) вузлів.

Альфа-бета дійшла того самого результату — MAX ходить ліворуч і здобуває 4, — але оцінила лише 6 листків із 9. У середній гілці вона відсікла два листки одразу після двійки, у правій — один після трійки. Тому у відсіченого вузла MIN є лише межа «≤ 2» і «≤ 3»: точної цінності ми не знаємо, і вона нам не потрібна.

На хрестиках-нуликах різниця разючіша. Повний мінімакс із порожнього поля відвідує 549 946 позицій, альфа-бета з тим самим порядком ходів — лише 18 297, приблизно втридцятеро менше, — і повертає той самий нуль. Показник m/2 у теоремі означає, що за той самий час ви зазирнете удвічі глибше. Тому порядок ходів такий важливий: шахові програми першими пробують взяття і ходи, які були добрими минулого разу.

def alphabeta(board, alpha=-inf, beta=inf):
    end = winner(board)
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    maximizing = to_move(board) == "X"
    v = -inf if maximizing else inf
    for move in empty_squares(board):
        h = alphabeta(play(board, move), alpha, beta)
        if maximizing:
            v = max(v, h); alpha = max(alpha, v)
        else:
            v = min(v, h); beta = min(beta, v)
        if alpha >= beta:
            break                          # відсікання: решта гілки нічого не змінить
    return v

6. Обмежена глибина та оцінювальна функція

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

Означення — мінімакс з обмеженою глибиною

Оцінювальна функція E : S → ℝ оцінює MM(s) і для кінцевих станів збігається з U. Зазвичай це зважена сума ознак позиції: E(s) = w₁f₁(s) + … + w_nf_n(s).

Мінімакс до глибини d: MM_d(s) = E(s), якщо s ∈ K або d = 0; інакше max чи відповідно min з MM_d−1 наступників.

Обмежена глибина має свою пастку: ефект горизонту. Коли пошук закінчиться посеред розміну фігур — ви щойно взяли ферзя, а суперник за хід забере його назад, — оцінювальна функція бачить лише першу половину й переоцінює позицію. Програми захищаються тим, що «неспокійні» позиції досліджують далі, доки ті не заспокояться. А оскільки ніколи не знають, скільки мають часу, шукають ітеративним поглибленням із попередньої частини: глибина 1, 2, 3, … доки не скінчиться час. Результати мілких проходів до того ж слугують порядком ходів для глибших — і альфа-бета тоді відсікає набагато більше.

7. Monte Carlo tree search

Оцінювальну функцію для шахів люди налаштовували десятиліттями. Для го написати її не вдавалося: позиція, яка виглядає спокійно, може за двадцять ходів виявитися програною. Monte Carlo tree search (MCTS) від оцінювальної функції повністю відмовляється. Замість оцінки він позицію дограває: випадково, багато разів, і дивиться, як часто це закінчилося добре.

Означення — одна ітерація MCTS

Дерево росте від кореня s₀. Кожен вузол i пам’ятає кількість відвідувань n_i і суму результатів w_i з погляду гравця, який зробив хід у цей вузол (виграш 1, нічия ½, програш 0). Ітерація має чотири кроки:

1. Вибір — від кореня раз у раз переходь до дитини з найвищою цінністю UCT, доки не натрапиш на вузол, який ще не має всіх дітей.
2. Розширення — додай йому одну дитину за ще не випробуваний хід.
3. Симуляція — з нового вузла дограй партію випадковими ходами аж до кінцевого стану.
4. Зворотне поширення — усім вузлам на шляху назад до кореня додай n ← n + 1, а до w — результат партії.

Коли час вичерпано, робиться хід із кореня з найбільшим n.

Означення — UCT

Під час вибору з дітей вузла з N відвідуваннями обирають дитину i з найбільшою цінністю

UCT(i) = w_i / n_i + c · √(ln N / n_i),

де c > 0 — константа дослідження, зазвичай √2. Зі зростанням кількості ітерацій рекомендований хід наближається до мінімаксного.

Запустімо MCTS на позиції, яку мінімакс розгадав вище. Числа в клітинках — відвідування після 100, 300 і 1000 ітерацій, під ними — середній результат для X:

Після 100 ітерацій центр має 47 відвідувань, а решта ходів разом — більше. Після тисячі він має 856 відвідувань і середній результат 0,94; нічийний хід унизу посередині отримав 52 відвідування, програшні ходи — ще менше. MCTS при цьому не знає ні поняття вилки, ні жодної оцінювальної функції — лише правила й випадок. І все ж знайшов той самий хід, що й мінімакс, якому довелося пройти всю решту дерева.

8. Від Deep Blue до AlphaZero

• Deep Blue (1997) переміг чемпіона світу Гаррі Каспарова. Усередині була альфа-бета з написаною вручну оцінювальною функцією і спеціалізоване апаратне забезпечення, яке обробляло близько 200 мільйонів позицій за секунду.
• Chinook грав у шашки проти чемпіонів світу вже в 90-х роках, а 2007 року його автори гру розв’язали: перебрали стільки позицій, що довели: бездоганна партія закінчується нічиєю — так само як хрестики-нулики 3 × 3.
• AlphaGo (2016) переміг Лі Седоля 4 : 1. Він поєднав MCTS із нейронними мережами: одна мережа пропонувала перспективні ходи (замість випадкового вибору), друга оцінювала цінність позиції (замість цілого випадкового догравання).
• AlphaZero (2017) відкинув навіть людські партії. Він навчився шахів, сьогі та го лише граючи сам із собою — навчанням з підкріпленням — і в кожній із цих ігор переміг найкращу дотеперішню програму.
• Ігри з випадковістю та прихованою інформацією потребують більшого. У нардах вирішує кубик, тож до дерева додають вузли випадку із середнім значенням (expectiminimax). У покері ви не бачите карт суперника; програма Libratus (2017) все ж перемогла професіоналів у покері для двох гравців.

Ідея «подивися вперед, перш ніж щось зробити» з шахівниць не зникла. Мовні агенти, що планують, пробують кілька варіантів дій, оцінюють їх і продовжують найперспективнішим — тільки замість ходів фігур обирають кроки розв’язку.

9. Підсумок

• Гра двох гравців із нульовою сумою — це задача пошуку, у якій ви ділите ходи із суперником; розв’язок — стратегія, а не шлях.
• Мінімакс обчислює цінність із кінця: MAX бере максимум, MIN — мінімум. Результат гарантований проти будь-якого суперника.
• Альфа-бета повертає ту саму цінність, але відсікає гілки, які не можуть змінити результат; за доброго порядку ходів вона зазирає вдвічі глибше.
• Великі ігри досліджують до обмеженої глибини з оцінювальною функцією — і стережіться ефекту горизонту.
• MCTS замість оцінки багато разів випадково дограває позицію і розвиває дерево там, де це перспективно; разом із нейронними мережами з нього виріс AlphaGo.

Хочете спробувати самі? Попросіть ШІ-агента написати хрестики-нулики з мінімаксом, а тоді порахуйте, скільки позицій заощадить альфа-бета, якщо впорядкувати ходи від центру до країв.

Маєте іншу думку? Напишіть на support@coden-app.com.