Căutare în arbore Monte Carlo

Căutarea în arbore Monte Carlo, abreviată MCTS, nu încearcă să examineze fiecare variantă la aceeași adâncime. Ea dezvoltă treptat un arbore și folosește rezultatele acumulate pentru a alege unde să aloce următoarea porțiune de calcul. O mutare vizitată de multe ori nu este automat bună, dar estimarea ei este de obicei susținută de mai multă căutare.

Un ciclu MCTS

1. Selecție: pornește din poziția inițială și urmează ramurile existente, echilibrând mutările care par deja puternice cu cele care rămân incerte.
2. Extindere: adaugă o poziție sau o mutare pe care arborele nu a dezvoltat-o încă.
3. Evaluare: estimează rezultatul din noua poziție. Metodele clasice pot încheia partide simulate, iar sistemele moderne pot folosi o rețea neuronală, adică un model antrenat să recunoască tipare, pentru a o aprecia.
4. Retropropagare: transmite rezultatul înapoi de-a lungul traseului vizitat și îi actualizează numărul de vizite și estimările.

Repetarea ciclului echilibrează exploatarea și explorarea. Exploatarea înseamnă alocarea unui efort mai mare acolo unde dovezile sunt deja favorabile. Explorarea înseamnă testarea alternativelor incerte, pentru ca o surpriză să nu fie respinsă prea devreme. Regula exactă de echilibrare depinde de implementare.

Spre deosebire de minimax, MCTS decide de obicei cât să investigheze o ramură pe baza dovezilor colectate în timpul căutării, nu doar a unei adâncimi uniforme. În unele programe de șah bazate pe rețele neuronale, o rețea furnizează o politică, ce sugerează mutări probabile, și o valoare, ce estimează rezultatul. Valoarea are un rol apropiat de cel al unei funcții de evaluare, deși procesul general de căutare este diferit.