ENGLISH ABSTRACT; Building sophisticated computer players for games has been
of interest since the advent of artificial intelligence research.
Monte Carlo tree search (MCTS) techniques have led to recent
advances in the performance of computer players in a
variety of games. Without any refinements, the commonly used
upper confidence bounds applied to trees (UCT) selection
policy for MCTS performs poorly on games with high
branching factors, because an inordinate amount of time is
spent performing simulations from each sibling of a node before
that node can be further investigated. Move-ordering
heuristics are usually proposed to address this issue, but
when the branching factor is large, it can be costly to order
candidate actions. We propose a technique combining sampling
from the action space with a naive evaluation function
for identifying nodes to add to the tree when using MCTS
in cases where the branching factor is large. The approach
is evaluated on a restricted version of the board game Risk
with promising results.