Browsing by Author "Van Niekerk, Francois"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Decision forests for computer Go feature learning
    (Stellenbosch : Stellenbosch University, 2014-04) Van Niekerk, Francois; Kroon, R. S. (Steve); Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
    ENGLISH ABSTRACT: In computer Go, moves are typically selected with the aid of a tree search algorithm. Monte-Carlo tree search (MCTS) is currently the dominant algorithm in computer Go. It has been shown that the inclusion of domain knowledge in MCTS is able to vastly improve the strength of MCTS engines. A successful approach to representing domain knowledge in computer Go is the use of appropriately weighted tactical features and pattern features, which are comprised of a number of hand-crafted heuristics and a collection of patterns respectively. However, tactical features are hand-crafted specifically for Go, and pattern features are Go-specific, making it unclear how they can be easily transferred to other domains. As such, this work proposes a new approach to representing domain knowledge, decision tree features. These features evaluate a state-action pair by descending a decision tree, with queries recursively partitioning the state-action pair input space, and returning a weight corresponding to the partition element represented by the resultant leaf node. In this work, decision tree features are applied to computer Go, in order to determine their feasibility in comparison to state-of-the-art use of tactical and pattern features. In this application of decision tree features, each query in the decision tree descent path refines information about the board position surrounding a candidate move. The results of this work showed that a feature instance with decision tree features is a feasible alternative to the state-of-the-art use of tactical and pattern features in computer Go, in terms of move prediction and playing strength, even though computer Go is a relatively well-developed research area. A move prediction rate of 35.9% was achieved with tactical and decision tree features, and they showed comparable performance to the state of the art when integrated into an MCTS engine with progressive widening. We conclude that the decision tree feature approach shows potential as a method for automatically extracting domain knowledge in new domains. These features can be used to evaluate state-action pairs for guiding searchbased techniques, such as MCTS, or for action-prediction tasks.
  • Thumbnail Image
    Item
    Monte-Carlo Tree Search Parallelisation for Computer Go
    (ACM Publishers, NY, USA, 2012) Van Niekerk, Francois; Kroon, R. Steve; van Rooyen, Gert-Jan; Inggs, Cornelia P.
    ENGLISH ABSTRACT: Parallelisation of computationally expensive algorithms, such as Monte-Carlo Tree Search (MCTS), has become increasingly important in order to increase algorithm performance by making use of commonplace parallel hardware. Oakfoam, an MCTS-based Computer Go player, was extended to support parallel processing on multi-core and cluster systems. This was done using tree parallelisation for multi-core systems and root parallelisation for cluster systems. Multi-core parallelisation scaled linearly on the tested hardware on 9x9 and 19x19 boards when using the virtual loss modi cation. Cluster parallelisation showed poor results on 9x9 boards, but scaled well on 19x19 boards, where it achieved a four-node ideal strength increase on eight nodes. Due to this work, Oakfoam is currently one of only two open-source MCTS-based Computer Go players with cluster parallelisation, and the only one using the Message Passing Interface (MPI) standard.