Efficacy of a causal value function in game tree search
Efficacy of a causal value function in game tree search
复制标题
博弈树搜索中因果值函数的功效
DOI：
10.1080/17445760.2015.1064918
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
T.
中科院分区：
文献类型：
--
作者：
Oyo;K.;Takahashi;T.
博弈树上的经典搜索方法是基于静态评估函数（能够对博弈状态进行定量评估）和决策策略（例如极大极小方法）。这些搜索方法在一些游戏中并不总是有效的，如围棋，因为评价函数的构造非常困难，搜索空间非常巨大。最近，蒙特卡洛树搜索方法（特别是UCT算法），使有效的采样的行动已被证明是非常有效的。在这里，我们提出了松散对称（LS）模型应用于树（LST），它利用了一个行动价值函数（LS模型），实现人类的因果直觉。通过调整一个直观的参数，LST使快速搜索的最佳行动与其有效的满足行为。LST实现的令人满意的搜索，使修剪和表现出广度优先和深度优先搜索策略之间的中间属性。
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.