Arbre de busca Monte Carlo
En ciències de la computació el arbre de busca Monte Carlo (en anglés MCTS) és un algoritme de busca heurístic per a alguns tipos de procés de presa de decisions, sobretot els que treballen en jocs. Un eixemple destacat recent és en els programes Go,[1] i també s'ha utilisat en atres jocs de taula, aixina com en videojocs en temps real i jocs no determinista com el pòquer.
Modo d'operació
[editar | editar còdic]L'enfocament de l'arbre de busca Monte Carlo es troba en l'anàlisis dels moviments més prometedors, ampliant l'arbre de busca basat en un mostreig aleatori de l'espai de busca. L'aplicació de busca d'arbre de Mont Carlo en els jocs es basa en molts playoffs. En cada emissió, el joc, es juga d'eixida fins al final per mig de la selecció de moviments a l'encert. El resultat final del joc de cada playout s'utilisa per a ponderar els nodos en l'arbre del joc de manera que els millors nodos són més propensos a ser elegits en futurs playoffs.
La forma més bàsica d'utilisar els playouts és aplicar el mateix número de playouts despuix de cada moviment llegal del jugador actual, a continuació, elegir el moviment que va dur a la major cantitat de victòries.[2] L'eficàcia d'este método cridat Busca Pura de Joc Monte Carlo - a sovint aumenta en el temps a mida que més playouts s'assignen als moviments que han donat lloc en freqüència a la victòria del jugador (en playouts anteriors).Les plena busca d'arbre de Mont Carlo ampren este principi de forma recursiva en moltes profunditats de l'arbre de joc. Cada ronda de busca d'arbre de Mont Carlo consistix en quatre passos:[3]
- Selecció: escomençar des de la raïl R i seleccionar nodos fills successius fins a alcançar un nodo full L. La secció d'avall descriu més d'una manera d'elegir nodos fills, que permeten que l'arbre de joc s'expandixca cap a moviments més prometedors, que és l'essència de l'arbre de busca Monte Carlo .
- Expansió: a menos que L termine el joc en una victòria/pèrdua per a qualsevol dels jugadors, crear un o més nodos fills i elegir entre ells un nodo C. Els nodos fills són qualsevol moviment vàlit des de la posició del joc definida per L.
- Simulació: jugar una reproducció aleatòria des del nodo C.
- Retropropagación: utilisar el resultat de la reproducció per a actualisar l'informació en els nodos en el camí de C a R.
Passos d'eixemple d'una ronda es mostren en la següent figura. Cada nodo de l'arbre almagasena el número de ganados/jugats playouts .
.svg){kind=link}
Vore també
[editar | editar còdic]- AlphaGo, un programa Go equivalent els humans que utilisa tant l'arbre de busca Monte Carlo i l'aprenentage profunt.
Referències
[editar | editar còdic]- ↑ «MCTS.ai: Everything Monte Carlo Tree Search». Consultat el 19 de febrer de 2012.
- ↑ Brügmann, Bernd (1993). Monte Carlo Go, Technical report, Department of Physics, Syracuse University.
- ↑ G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van donen Herik, B. Bouzy(2008).New Mathematics and Natural Computation.4(3)
- 343–359.doi:10.1142/s1793005708001094.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Árbol de búsqueda Monte Carlo» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.