Monte-Carlo Tree Search in one page

MCTS algorithm

Input: a state S

Output: a decision D

Global variable: a tree T, each node having nbSims

    initiliazed at a single node with state S and nbSims=0 and totalReward=0

While (I have time)

{

    Do one simulation from state S until a game is over 

            ==> we get a sequence s(0), s(1), s(2), s(3),..., s(k)     (with s(0)=S and s(k) a final state)

            ==> we get a reward r

    Consider i minimal such that s(i) is not in T

    If such an i exists, then add s(i) in T, with an edge from s(i-1) to s(i)

    For each i such that s(i) is in T:

                 s(i).nbSims++

                 s(i).totalReward+=r

}

Procedure for doing one simulation from state S until a game is over:

s=S

while (s it not terminal)

{

    choose child s' of s such that UCB(s') is maximum

    s=s'

}

Procedure for computing the UCB score of a node s':

{

    meanReward=s'.totalReward / s'.nbSims

    fatherSims=s'.father.nbSims

    UCB = meanReward + sqrt( log(fatherSims) / s'.nbSims)   

}

Based on research in the TAO team

Comments

[ewe]

Voir Blog(fermaton.over-blog.com)No.22- THÉORÈME ÉTAT. - La base des mathématiques de l'Esprit.