Sample evaluation for action selection in Monte Carlo Tree Search

Brand, Dirk ; Kroon, Steve (2014)

SAICSIT2014, September 29-October 1 2014, Centurion, South Africa

South African Institute of Computer Scientists and Information Technologists

Conference Paper

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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/95644
This item appears in the following collections: