Efficacy of a causal value function in game tree search. Issue 2 (4th March 2017)

• Record Type: Journal Article
• Authors: Oyo, Kuratomo; Takahashi, Tatsuji
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 32:Issue 2(2017)
• Page Start: 206
• Page End: 217
• Publication Date: 2017-03-04
• Subjects: Monte Carlo tree search -- multi-armed bandit problems -- the loosely symmetric model -- cognitively inspired computing -- causal intuition -- satisficing; 07.05.Mh -- 02.70.Uu; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2015.1064918
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : Classical search methods on game trees are based on a static evaluation function (that enable quantitative valuation of game states) and a decision strategy (such as the minimax method). These search methods are not always effective in some games such as the game of Go, as construction of the evaluation function is very hard and the search space is extremely huge. Recently, Monte Carlo tree search methods (especially the UCT algorithms) that enable efficient sampling of actions have been shown to be very effective. Here, we propose the loosely symmetric (LS) model applied to trees (LST), which utilises an action value function (LS model) that implements causal intuition of humans. By tuning a single intuitive parameter, LST enables fast search of the optimal action with its efficient satisficing behaviour. The satisficing search realised by LST enables pruning and exhibits intermediate properties between those of breadth-first and depth-first search strategies.