Gli algoritmi tradizionali di intelligenza artificiale sono molto potenti, tuttavia richiedono molta memoria nella loro esecuzione.
Nel 2006 Kocsis e Szepesvari, con l’intento di migliorare gli algoritmi classici, introducono la Ricerca ad Albero Monte Carlo (o Monte Carlo Tree Search, MCTS). Rispetto al Minimax la differenza principale del metodo MCTS è che l’espansione l’albero degli stati non avviene completamente.
Mentre il Minimax espande tutto l’albero e poi sceglie la mossa migliore, la Ricerca ad Albero Monte Carlo effettua una ricerca in profondità, fino a raggiungere uno stato finale. A questo punto valuta lo stato corrente, assegna un valore a quel nodo e lo propaga a tutti quelli percorsi fino alla radice. Questo procedimento viene ripetuto più volte costruendo un albero in maniera incrementale e asimmetrica, scegliendo a ogni iterazione il nodo più urgente da espandere. Tale scelta è fatta in base a una politica mirata a bilanciare l’esplorazione delle parti non ancora visitate e lo sfruttamento dei nodi che sembrano promettenti. La costruzione dell’albero si arresta arbitrariamente a seconda del tempo o della memoria a disposizione.
Un ulteriore vantaggio è di non dovere calcolare i valori degli stati intermedi. Considerare unicamente la situazione negli stati finali richiede una conoscenza minore del dominio. Kocsis e Szepesvari hanno dimostrato che la Ricerca ad Albero Monte Carlo, avendo a disposizione abbastanza tempo e memoria, converge al risultato ottimo del Minimax.
spam fails_task lang_mismatch pii not_appropriate hate_speech sexual_content quality toxicity humor helpfulness creativity violence