Conference Proceedings (Electrical and Electronic Engineering)
Permanent URI for this collection
Browse
Browsing Conference Proceedings (Electrical and Electronic Engineering) by Author "Brand, Dirk"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- ItemSample evaluation for action selection in Monte Carlo Tree Search(2014) Brand, Dirk; Kroon, SteveENGLISH 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.