Najprymitywniejszy sposób użycia symulacji to wykonanie, po każdym ruchu dopuszczalnym dla bieżącego gracza, tej samej liczby symulacji, a następnie wybór tego ruchu, po którym najwięcej symulacji zakończyło się wygraną tego gracza. Wydajność tej metody rośnie, gdy z biegiem czasu przydziela się więcej symulacji tym ruchom, po których poprzednie symulacje częściej prowadziły do wygranej danego gracza. Pełna metoda MCTS polega na rekurencyjnym zastosowaniu tego pomysłu nie na jednym, lecz na wielu poziomach głębokości drzewa wariantów. Każda tura tej metody składa się z czterech kroków: Wybór (ang. selection): zaczynając od korzenia drzewa wybieraj kolejne węzły potomne, aż dotrzesz do liścia drzewa Poniżej więcej o takim sposobie wyboru węzłów potomnych, dzięki któremu drzewo wariantów rozrasta się w kierunku najbardziej obiecujących ruchów, co stanowi clou metody MCTS. Rozrost (ang. expansion): o ile nie kończy gry, utwórz w nim jeden lub więcej węzłów potomnych i wybierz z nich jeden węzeł Symulacja (ang. playout): rozegraj losową symulację z węzła Propagacja wstecz (ang. backpropagation): na podstawie wyniku rozegranej symulacji uaktualnij informacje w węzłach na ścieżce prowadzącej od do Przykładowe kroki jednej tury przedstawiono na poniższym rysunku.
Źródło i licencja
Fragment artykułu Wikipedia — Monte-Carlo Tree Search · historia autorów.
Tekst: CC BY-SA 4.0. Wydzielono fragment z dłuższego artykułu.