Efficacy of a causal value function in game tree search

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.

Keywords::

• Monte Carlo tree search
• multi-armed bandit problems
• the loosely symmetric model
• cognitively inspired computing
• causal intuition
• satisficing

2000 Mathematics Subject Classification::

• 07.05.Mh
• 02.70.Uu

Acknowledgements

The authors would like to thank Mr Naoto Noguchi for assistance in programming.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Part of this work was carried out with the support of the Cooperative Research Project Program H25/A12 of the Research Institute of Electrical Communication, Tohoku University and JSPS KAKENHI Grant Number 25730150.