Ricerca ad albero Monte Carlo
| Ricerca ad albero Monte Carlo | |
|---|---|
 | |
| Classe | algoritmo di ordinamento |
| Struttura dati | Grafo |
La ricerca ad albero Monte Carlo (nota anche come MCTS, acronimo dell'inglese Monte Carlo tree search) è un algoritmo di ricerca euristica sviluppato per la ricerca in alberi di decisione, che ha applicazione nella soluzione di giochi da tavolo.
L'algoritmo venne introdotto nel 2006 per il gioco del go[1] ed è stato in seguito applicato ad altri giochi ad informazione perfetta come scacchi e Shōgi,[2] a giochi ad informazione incompleta come bridge[3] e poker,[4] e a videogiochi di strategia a turni come Total War: Rome II.[5]
MCTS opera espandendo l'albero di ricerca delle mosse più promettenti tramite campionamento casuale dello spazio di ricerca usando il metodo Monte Carlo. La ricerca si basa sull'esecuzione di numerosi playout (o rollout), dove ogni playout consiste nell'esecuzione di un'intera partita a partire dalla posizione corrente, selezionando le mosse a caso. Il risultato della partita è poi usato per pesare le mosse eseguite e il peso determina la probabilità di eseguire la stessa mossa in successivi playout.[Troppa sintesi e quindi poca chiarezza. Uso di termini inglesi non può essere evitato?]
Note
[modifica | modifica wikitesto]- ^ David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel e Demis Hassabis, Mastering the game of Go with deep neural networks and tree search, in Nature, vol. 529, n. 7587, 28 gennaio 2016, pp. 484–489, Bibcode:2016Natur.529..484S, DOI:10.1038/nature16961, ISSN 0028-0836, PMID 26819042.
- ^ (EN) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis, A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play, in Science, vol. 362, n. 6419, 7 dicembre 2018, pp. 1140-1144, DOI:10.1126/science.aar6404.
- ^ Stuart J. Russell, Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd, Prentice Hall, 2009.
- ^ Jonathan Rubin e Ian Watson, Computer poker: A review (PDF), in Artificial Intelligence, vol. 175, 5–6, aprile 2011, pp. 958–987, DOI:10.1016/j.artint.2010.12.005 (archiviato dall'url originale il 13 agosto 2012).
- ^ Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI, su AI Game Dev. URL consultato il 25 febbraio 2017 (archiviato dall'url originale il 13 marzo 2017).
Bibliografia
[modifica | modifica wikitesto]- Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis e Simon Colton, A Survey of Monte Carlo Tree Search Methods, in IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, n. 1, marzo 2012, pp. 1–43, DOI:10.1109/tciaig.2012.2186810.
