Sample evaluation for action selection in Monte Carlo Tree Search

Simple item page
dc.contributor.authorBrand, Dirk
dc.contributor.authorKroon, Steve
dc.date.accessioned2014-10-08T06:25:21Z
dc.date.available2014-10-08T06:25:21Z
dc.date.issued2014
dc.descriptionSAICSIT2014, September 29-October 1 2014, Centurion, South Africaen_ZA
dc.descriptionSouth African Institute of Computer Scientists and Information Technologistsen_ZA
dc.description.abstractENGLISH 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.en_ZA
dc.description.versionPost-printen_ZA
dc.format.extent9 p.
dc.identifier.otherhttp://dx.doi.org/10.1145/2664591.2664612
dc.identifier.urihttp://hdl.handle.net/10019.1/95644
dc.language.isoen_ZA
dc.rights.holderAuthorsen_ZA
dc.subjectAlgorithmsen_ZA
dc.subjectComputer games -- Programmingen_ZA
dc.subjectMonte-Carlo Methoden_ZA
dc.subjectArtificial intelligence -- Computer programsen_ZA
dc.titleSample evaluation for action selection in Monte Carlo Tree Searchen_ZA
dc.typeConference Paperen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
kroon_sample_2014.pdf
Size:
782.49 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.95 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Conference Proceedings (Electrical and Electronic Engineering)