Monte-Carlo Tree Reductions for Stochastic Games - Technologies and Applications of Artificial Intelligence - page 232

input : T the current tree
output :( q , m )where q ∈T and q to expand by applying a move m
q ₐ root ;
while true do
if q is a chance-node then q ₐ q + dice () ;
else
if no move from q then break ;
if q∈T then
insert q in T ;
return ( q , first move from q );
else
q best ₐ {∅} ;
foreach move m from q do
if ( q + m ) /∈T then return ( q , m );
q best ₐ best ( q best ,( q + m ));
q ₐ q best ;

return ( q , {∅} );
Algorithm 4. Select function with chance-nodes

input : T the current tree
output :( q , m )where q ∈T and q to expand by applying a move m
q ₐ root ;
while true do
if no move from q then break ;
if only 1 move-group g exists from q then
q best ₐ {∅} ;
foreach move m of g from q do
if ( q + m ) /∈T then return ( q , m );
q best ₐ best ( q best ,( q + m ));
q ₐ q best ;
else
M best ₐ {∅} ;

foreach move-group M from q do
if M∩T = ∅ then
add one-move of M in T

;

return ( q , m );
M best ₐ best ( M , M best );
m ₐ one-move of M best ;
if ( q + m ) /∈T then return ( q , m );
q ₐ q + m ;

return ( q , {∅} );
Algorithm 5. Select function with move-groups