Przeszukiwanie drzewa metodą Monte Carlo

Przeszukiwanie drzewa metodą Monte Carlo, w skrócie MCTS, nie próbuje badać każdego wariantu do tej samej głębokości. Stopniowo rozbudowuje drzewo i wykorzystuje zgromadzone wyniki, aby zdecydować, na co przeznaczyć kolejną porcję obliczeń. Ruch odwiedzony wiele razy nie jest automatycznie dobry, lecz jego oszacowanie jest zwykle poparte większym zakresem przeszukiwania.

Jeden cykl MCTS

1. Wybór: rozpoczęcie od pozycji początkowej i podążanie istniejącymi gałęziami przy równoważeniu ruchów, które już wyglądają na silne, z ruchami nadal niepewnymi.
2. Rozszerzenie: dodanie pozycji lub ruchu, których drzewo jeszcze nie rozwinęło.
3. Ocena: oszacowanie wyniku z nowej pozycji. Klasyczne metody mogą dokończyć symulowane partie, a nowoczesne systemy mogą używać sieci neuronowej, czyli wytrenowanego modelu rozpoznającego wzorce, aby ocenić pozycję.
4. Propagacja wsteczna: przeniesienie wyniku wzdłuż odwiedzonej ścieżki i zaktualizowanie liczby odwiedzin oraz oszacowań.

Powtarzanie tego cyklu równoważy eksploatację i eksplorację. Eksploatacja oznacza przeznaczanie większego wysiłku tam, gdzie dowody są już korzystne. Eksploracja oznacza sprawdzanie niepewnych alternatyw, aby zbyt wcześnie nie odrzucić zaskakującej możliwości. Dokładna reguła równoważenia zależy od implementacji.

W odróżnieniu od minimax, MCTS zwykle decyduje, jak dokładnie zbadać gałąź, na podstawie danych zebranych podczas samego przeszukiwania, a nie wyłącznie jednolitej głębokości. W niektórych programach szachowych opartych na sieciach neuronowych sieć dostarcza politykę, która sugeruje prawdopodobne ruchy, oraz wartość, która szacuje wynik. Wartość pełni funkcję powiązaną z funkcją oceny, choć cały proces przeszukiwania jest inny.