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

Пошук у дереві Монте-Карло, скорочено MCTS, не намагається дослідити кожен варіант до однакової глибини. Він поступово розбудовує дерево й використовує накопичені результати, щоб вирішити, куди спрямувати наступну частину обчислень. Хід із великою кількістю відвідувань не є автоматично добрим, але його оцінка зазвичай спирається на більший обсяг пошуку.

Один цикл MCTS

1. Вибір: почати з початкової позиції й рухатися наявними гілками, урівноважуючи ходи, які вже здаються сильними, з ходами, що залишаються невизначеними.
2. Розширення: додати позицію або хід, які дерево ще не розвинуло.
3. Оцінювання: приблизно визначити результат із нової позиції. Класичні методи можуть завершувати симульовані партії, а сучасні системи можуть використовувати нейронну мережу, навчену модель для розпізнавання шаблонів, щоб оцінити позицію.
4. Зворотне поширення: перенести результат назад уздовж відвіданого шляху й оновити кількість відвідувань та оцінки.

Повторення цього циклу врівноважує використання та дослідження. Використання означає витрачати більше зусиль там, де наявні дані вже сприятливі. Дослідження означає перевіряти невизначені альтернативи, щоб не відкинути несподіванку надто рано. Точне правило рівноваги залежить від реалізації.

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