Monte Carlo Tree Search

Monte Carlo Tree Search, afgekort MCTS, probeert niet elke variant tot dezelfde diepte te onderzoeken. De methode bouwt geleidelijk een boom op en gebruikt de verzamelde resultaten om te bepalen waar het volgende deel van de rekenkracht naartoe gaat. Een vaak bezochte zet is niet automatisch goed, maar haar schatting wordt gewoonlijk door meer zoekwerk ondersteund.

Eén MCTS-cyclus

1. Selectie: begin bij de uitgangsstelling en volg bestaande takken, waarbij zetten die al sterk lijken worden afgewogen tegen zetten waarover nog onzekerheid bestaat.
2. Uitbreiding: voeg een stelling of zet toe die de boom nog niet heeft uitgewerkt.
3. Evaluatie: schat het resultaat vanuit de nieuwe stelling. Klassieke methoden kunnen gesimuleerde partijen uitspelen, terwijl moderne systemen ook een neuraal netwerk kunnen gebruiken, een getraind model dat patronen herkent, om de stelling te beoordelen.
4. Terugpropagatie: voer het resultaat terug langs het bezochte pad en werk de aantallen bezoeken en schattingen bij.

Door deze cyclus te herhalen worden exploitatie en exploratie in evenwicht gebracht. Exploitatie betekent meer inspanning besteden waar de aanwijzingen al gunstig zijn. Exploratie betekent onzekere alternatieven testen, zodat een verrassing niet te vroeg wordt verworpen. De precieze regel om beide af te wegen hangt van de implementatie af.

Anders dan minimax bepaalt MCTS meestal hoeveel een tak wordt onderzocht op basis van bewijs dat tijdens de zoekactie zelf is verzameld, en niet alleen op basis van een uniforme diepte. In sommige schaakprogramma's die op neurale netwerken zijn gebaseerd, levert een netwerk een beleid, dat waarschijnlijke zetten voorstelt, en een waarde, die het resultaat schat. Die waarde vervult een rol die verwant is aan een evaluatiefunctie, hoewel het volledige zoekproces anders is.