Arbre de cerca Monte Carlo

Il·lustració de l'estimació de valors mitjançant el mètode de Monte Carlo; els valors de la part alta del gràfic mostren la relació entre el valor de π calculat i el real: com més gran sigui n, més a prop està el valor de π calculat del valor real.

En ciències de la computació l'arbre de cerca Monte Carlo (en anglès MCTS) és un algorisme de cerca heurístic per a alguns tipus de processos de presa de decisions, sobretot els que treballen amb jocs. Un exemple destacat recent és en els programes Go,^[1] i també s'ha utilitzat en altres jocs de taula, així com en videojocs en temps real i jocs no deterministes com el pòquer.

Mode d'operació

L'enfocament de l'arbre de cerca Monte Carlo es troba en l'anàlisi dels moviments més prometedors, ampliant l'arbre de cerca basat en un mostreig aleatori de l'espai de cerca. L'aplicació de cerca d'arbre de Monte Carlo als jocs es basa en molts play-offs. A cada emissió, el joc es juga de sortida fins al final mitjançant la selecció de moviments a l'atzar. El resultat final del joc de cada play-out s'utilitza per ponderar els nodes a l'arbre del joc de manera que els millors nodes són més propensos a ser elegits en futurs playoffs.

La forma més bàsica d'utilitzar els play-outs és aplicar el mateix nombre de play-outs després de cada moviment legal del jugador actual, a continuació, triar el moviment que va portar a la major quantitat de victòries.^[2] L'eficàcia d'aquest mètode anomenat Cerca Pura de Joc Monte Carlo - sovint augmenta amb el temps a mesura que més play-outs s'assignen als moviments que han donat lloc sovint a la victòria del jugador (en play-outs anteriors). La recerca d'arbre de Monte Carlo empren aquest principi de forma recursiva en moltes profunditats de l'arbre de joc. Cada ronda de cerca d'arbre de Monte Carlo consisteix en quatre passos:^[3]

• Selecció : començar des de l'arrel R i seleccionar nodes fills successius fins a assolir un node full L. La secció de sota descriu més d'una manera d'escollir fills nodes, que permeten que l'arbre de joc s'expandeixi cap a moviments més prometedors, que és l'essència de l'arbre de cerca Monte Carlo.
• Expansió : llevat que L acabi el joc amb una victòria/pèrdua per a qualsevol dels jugadors, crear un o més nodes fills i triar entre ells un node C. Els nodes fills són qualsevol moviment vàlid des de la posició del joc definida per L.
• Simulació : jugar una reproducció aleatòria des del node C.
• Retropropagació : utilitzar el resultat de la reproducció per actualitzar la informació als nodes al camí de C a R.

Passos d'exemple d'una ronda es mostren a la figura següent. Cada node de l'arbre emmagatzema el nombre de play-outs guanyats/jugats.

Passos de l'arbre de cerca Monte Carlo.

Referències

1. «MCTS.ai: Everything Monte Carlo Tree Search». [Consulta: 19 febrer 2012].
2. Brügmann, Bernd. Monte Carlo Go. Technical report, Department of Physics, Syracuse University, 1993. 
3. G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik, B. Bouzy «Progressive Strategies for Monte-Carlo Tree Search». New Mathematics and Natural Computation, 4, 3, 2008, pàg. 343–359. DOI: 10.1142/s1793005708001094.

Vegeu també

• AlphaGo, un programa Go equivalent als humans que utilitza tant l'arbre de cerca Monte Carlo com l'aprenentatge profund.
• AlphaGo Zero, un programa Go actualitzat que utilitza la cerca d'arbres de Monte Carlo, aprenentatge per reforç i aprenentatge profund.
• AlphaZero, una versió generalitzada d'AlphaGo Zero utilitzant la cerca d'arbres de Monte Carlo, aprenentatge per reforç i aprenentatge profund.
• Leela Chess Zero, una implementació de programari lliure dels mètodes d'AlphaZero per als escacs, que actualment es troba entre els principals programes de joc d'escacs.