Quando si implementa la ricerca dell'albero di Monte Carlo per TicTacToe, simulare gli stati vincitori?

Question

Quando si implementa la ricerca dell'albero di Monte Carlo per TicTacToe, simulare gli stati vincitori?

#1 da (1 voti)

1

Sto provando a eseguire il debug della mia implementazione MCTS per TicTacToe (non blocca vincite ovvie per l'avversario). Mi chiedevo cosa avrebbe dovuto fare l'algoritmo se si espande su un nodo che è un gioco sopra lo stato. Dovrebbe continuare a "simulare" quel nodo e back-propogare i risultati sull'albero o semplicemente ignorarlo se il nodo è scelto.

algorithms artificial-intelligence simulation games

posta Amja 09.12.2016 - 23:46

fonte

1 risposta

Leggi altre domande sui tag algorithms artificial-intelligence simulation games

Dal database web (PostgreSQL) al mobile (SQLite) Come posso integrare le viste con lo stato del controller in modo trasparente?

score 1 · Accepted Answer

La variante base di MCTS non richiede una gestione speciale per gli stati dei terminali.

Aggiorna solo il punteggio / numero di visite a seconda del risultato (vinci / perdi) e procede con la propagazione del back.

È una sorta di playout / simulazione istantanea e non può essere saltato (consentendo a MCTS di convergere al valore teorico del gioco).

L'algoritmo può essere migliorato (ad esempio, MONTE-CARLO TREE SEARCH SOLVER) utilizzando i punteggi di grandi dimensioni (ad esempio + ∞ / -∞) e ad hoc di backpropagation / selezione:

Aspecialprovisionisthentakenwhenbackingsuchprovenvaluesupthetree.TherearethreecasestoconsiderasshowninFig.(weusethenegamaxformulation,alternatingsignsbetweenlevels).
First,whenasimulationbacksupaprovenloss(−∞)fromachildctoaparentp,theparentnodepbecomes,andislabelledas,aprovenwin(∞),thatis,thepositioniswonfortheplayeratpbecausethemoveplayedleadstoawin(leftbackupdiagraminthefigure).
Whenbackingupaprovenwin(∞)fromctop,onemust,however,alsolookattheotherchildrenofptodeterminep’svalue.Inthesecondcase,whenallchildnodesofparealsoaprovenwin(∞),thenthevalueofpbecomesaprovenloss(-∞),becauseallmovesleadtoapositionlostforp(middlebackupdiagraminthefigure).
However,thethirdcaseoccursifthereexistsatleastonechildwithavaluedifferentvaluefromaprovenwin.Thenwecannotlabelpasaprovenloss.Insteadpgetsupdatesasifasimulationwin(insteadofaprovenwin)werebeingbackedupfromnodec(rightbackupdiagraminthefigure;vanduindicatenon-provenvalues).Non-provenvaluesarebackedupasinregularMCTS.

1)Ulterioridettagliin Ricerca dell'albero Monte-Carlo in Linee di azione di Mark H.M. Winands, Yngvi Bjornsson e Jahn-Takeshi Saito.