🎯 Пошук за деревом Монте-Карло
Ігровий ШІ: вибір за UCB1, розіграш, зворотне поширення
Nim: береш 1, 2 або 3 камені з купи в 15 — хто взяв останній, той переміг
Керування
Статистика
Всього симуляцій
0
Відвідування кореня
0
Найкращий хід
—
Розмір купи
15
Інформація та теорія

Пошук за деревом Монте-Карло (MCTS) будує дерево пошуку поступово, повторюючи чотири фази, використовуючи рандомізовані симуляції замість вручну створеної функції оцінювання.

Чотири фази

  • Вибір — починаючи з кореня, спускаємося деревом, обираючи дочірній вузол, що максимізує UCB1, доки не досягнемо вузла з невипробуваними ходами або без дочірніх вузлів.
  • Розширення — додаємо один новий дочірній вузол для невипробуваного ходу.
  • Розіграш (симуляція) — граємо рівномірно випадкові допустимі ходи з нового вузла до кінця гри.
  • Зворотне поширення — повертаємося до кореня, оновлюючи лічильники відвідувань і перемог на кожному вузлі вздовж шляху.

UCB1: баланс дослідження та використання

Верхня довірча межа, застосована до дерев, обирає дочірній вузол, що максимізує winRate + C·√(ln(parentVisits) / childVisits). Перший доданок надає перевагу ходам, які часто перемагали (використання); другий доданок зростає для рідко відвіданих дочірніх вузлів (дослідження), тож пошук продовжує перевіряти перспективні, але недостатньо досліджені гілки, замість того щоб зациклюватися на ранніх результатах. C = √2 ≈ 1,41 — теоретично обґрунтована константа для винагород у діапазоні [0,1].

Не потрібна евристична оцінка

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

Збіжність і застосування в реальному світі

Зі зростанням кількості симуляцій лічильники відвідувань концентруються на найсильніших ходах, а оцінки частки перемог сходяться до справжніх значень гри. MCTS добре масштабується за великих коефіцієнтів розгалуження, тому саме він живив AlphaGo і AlphaZero, де його поєднали з глибокими нейронними мережами, що замінили випадкові розіграші навченими оцінками цінності та стратегії.

Про Пошук за деревом Монте-Карло

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Оновлено: 11 липня 2026 р.

Пошук за деревом Монте-Карло (MCTS) — це алгоритм для пошуку сильних ходів у послідовних задачах прийняття рішень, таких як настільні ігри, шляхом поступової побудови дерева пошуку через повторюване випадкове семплювання. Кожна ітерація виконує чотири фази: вибір, який спускається деревом від кореня, використовуючи формулу UCB1 — winRate + C·√(ln(parentVisits)/childVisits) — щоб збалансувати використання відомо хороших ходів із дослідженням недостатньо відвіданих; розширення, яке додає один новий вузол для невипробуваного ходу; розіграш, який грає рівномірно випадкові ходи до термінального стану; та зворотне поширення, яке оновлює статистику відвідувань і перемог уздовж шляху назад до кореня. Оскільки MCTS оцінює цінності позицій за результатами симуляцій, а не за вручну створеною евристикою, він добре масштабується для ігор з величезними коефіцієнтами розгалуження, таких як Го, де вичерпний мінімаксний пошук обчислювально неможливий. Ця властивість зробила MCTS основою AlphaGo та, у поєднанні з глибокими нейронними мережами, що замінили випадкові розіграші, AlphaZero від DeepMind — систем, які перевершили людську майстерність у Го, шахах та сьогі.

Часті запитання

Що таке чотири фази пошуку за деревом Монте-Карло?

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

Що таке UCB1 і як він балансує дослідження та використання?

UCB1 (Верхня довірча межа 1) оцінює кожен дочірній вузол за формулою winRate + C·√(ln(parentVisits)/childVisits). Доданок частки перемог надає перевагу ходам, які показали хороші результати (використання), тоді як доданок квадратного кореня зростає для дочірніх вузлів з небагатьма відвідуваннями (дослідження), повертаючи пошук до недостатньо семплованих гілок. Константа C = √2 балансує ці два доданки для винагород, масштабованих від 0 до 1.

Чому випадкового розіграшу достатньо без вручну створеної функції оцінювання?

Окремий випадковий розіграш зашумлений, але усереднений за багатьма симуляціями, результати розіграшів дають незміщену статистичну оцінку справжньої ймовірності перемоги позиції. Це дозволяє MCTS оцінювати позиції в іграх, де розробка точної евристичної функції оцінювання — як цього вимагає мінімакс — була б складною чи неможливою, як-от величезні й залежні від патернів позиції на дошці Го.

Де MCTS використовується в реальному ігровому ШІ?

MCTS — це основний алгоритм пошуку, що лежить в основі AlphaGo від DeepMind, який переміг найкращих людських гравців у Го в 2016 році, та його наступника AlphaZero, який опанував Го, шахи й сьогі через самонавчання. У цих системах випадкові розіграші MCTS замінили оцінками цінності та стратегії навченої нейронної мережі, але структура вибору-розширення-зворотного поширення пошуку деревом лишилася.