Poniższe laboratorium jest kontynuacją laboratorium o klasycznych algorytmach działających na drzewie gry i zakłada zrozumienie przedstawionych na nim treści. W ramach laboratorium zaprezentowany będzie sławny algorytm Monte Carlo Tree Search (MCTS). O ile algorytm MiniMax z cięciami Alpha-Beta reprezentuje podejście branch and bound do wyczerpującego przeszukiwania drzewa gry, o tyle w przypadku gier o dużym współczynniku rozgałęzienia jest to niemożliwe, np. w przypadku sławnej gry Go.
Algorytm MCTS należy do dużej rodziny algorytmów próbkujących, często używanych w przypadku rozumowań probabilistycznych.
Powiązane materiały:
Nazwa Monte Carlo pochodzi od sławnych kasyn, w których znaleźć można automaty typu „jednoręki bandyta”. W przypadku drzewa gier mamy w danej turze to wyboru kilka ruchów, które mogą (lecz nie muszą) zapewnić nam zwycięstwa. Każdy możliwy ruch możemy potraktować jako automat do gry z nieznanym prawdopodobieństwem wygranej, a wybór ruchu to po prostu wybór automatu, na którym przepuścimy kolejny żeton. Na początku nie wiemy, który automat daje większą szansę na zwycięstwo - dlatego też wybieramy dowolny (losowy) z nich. Następnie zapisujemy wynik z gry i ponawiamy grę losując automat. Robimy to tak długo jak tylko jesteśmy w stanie - cały czas zapisując wyniki gier. Następnie wybieramy ten automat, który dał nam najwięcej zwycięstw. W przełożeniu na język drzewa gry - wykonujemy możliwie dużo losowych symulacji gier i wybieramy ten ruch, który średnio najczęściej doprowadzał do zwycięstwa.
dopóki starczy czasu: pierwszy_ruch = wybierz_losowy_ruch() wynik = losowa_symulacja(pierwszy_ruch) zapisz_wynik(pierwszy_ruch) policz_średnie_wyniki_dla_każdego_ruchu() wybierz_ruch_o_największym_średnim_wyniku()
SampleMonteCarloGamer.java
Bardziej ambitnym rozszerzeniem algorytmu Monte Carlo jest inteligentne próbkowanie automatów do gry. Zamiast losowo wybierać automat do gry, faworyzujemy automaty, które sprawowały się najlepiej, tj. z początku gramy zupełnie losowo, z czasem coraz bardziej przekonując się do wybierania automatów, z którymi dotychczas najczęściej wygrywaliśmy. Matematycznie, można to wyrazić za pomocą formuły:
gdzie:
Formuła UCT z jednej strony faworyzuje ruchy, które mają duży średni wynik; z drugiej strony druga część formuły zwraca większe wartości dla ruchów mniej sprawdzonych.
W przypadku przeszukiwania drzewa gry podobny problem należy rozwiązać w każdym przeszukiwanym węźle. Dla wszystkich możliwych do wykonania ruchów prowadzimy statystykę liczby zwycięstw i wszystkich symulacji danego ruchu. Z początku ruchy są losowe, później jednak zaczynają faworyzować tę część drzewa gry, która zawiera obiecujące ruchy.
Algorytm można podzielić na cztery fazy:
Szare kółka (ruchy wroga) minimalizują liczbę naszych zwycięstw.
Powyższe fazy powtarzają się tak długo, jak jest to możliwe. Na końcu wybieramy ten ruch, który został zasymulowany największą ilość razy. Jego jakość jest zapewniona poprzez fakt, że algorytm z natury skupia przeszukiwanie wokół najlepszych możliwości.
SampleMonteCarloGamer.java
, proszę zaimplementować gracza SampleMCTSGamer.java
SampleMCTSGamer.java
vs SampleMonteCarloGamer.java
w warcaby normalnych rozmiarów lub inną grę o dużej przestrzeni przeszukiwania, czy widać różnicę między wynikami tych botów?