Multiple-Paths Search with Concurrent Thread Scheduling for Fast AND/OR Tree Search
Multiple-Paths Search with Concurrent Thread Scheduling for Fast AND/OR Tree Search
复制标题
DOI：
10.1109/cisis.2009.65
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
Fumiyo Takano;Y. Maekawa;H. Kasahara
中科院分区：
文献类型：
--
作者：
Fumiyo Takano;Y. Maekawa;H. Kasahara
本文提出了一种多路径并行搜索的快速AND/OR树搜索算法。传统的启发式AND/OR树搜索算法仅以启发式评估值的降序扩展节点。然而，由于评估值是启发式的，解节点组中有时会包含评价值较低的节点，而传统算法求解包含评价值较低的节点的解节点组的树需要很长时间。该算法允许同时搜索包含评价值较低的节点的路径和包含评价值较高的节点的路径。对于搜索各种不同的路径，该算法可以同时搜索包含评价值较低的节点的路径和包含评价值较高的节点的路径。该算法使用伪线程和由用户程序管理的伪线程调度器，与操作系统线程管理相比开销小，能够对每条路径上的搜索量进行加权，并对伪线程进行调度，能够快速求解包含评价值较低的节点的解的树。将该算法应用于一个日本象棋问题的求解中，作为一个典型的AND/OR树搜索问题，在该问题中，棋手可以重复使用捕获的棋子，对385个问题的性能评估结果表明，该算法的平均速度是原算法df-pn的1.67倍.
This paper proposes a fast AND/OR tree search algorithm using a multiple-paths concurrent search method. Conventional heuristic AND/OR tree search algorithms expand nodes in only a descending order of heuristic evaluation values. However, since the evaluation values are heuristic, a solution node group sometimes includes nodes with lower evaluation values.The tree which has a solution node group including nodes with lower evaluation values requires a long time to be solved by the conventional algorithms.The proposed algorithm allows us to search paths including nodes with lower evaluation values and paths including nodes with higher evaluation values concurrently.For searching various paths concurrently, the proposed algorithm uses pseudo-threads and a pseudo-thread scheduler managed by a user program with low overhead compared with the OS thread management.The pseudo-thread scheduler can weight the amount of search on each path and schedule the pseudo-threads.The proposed algorithm can solve trees which have solutions including nodes with lower evaluation values also quickly.For performance evaluation, the proposed algorithm was applied to a tsume-shogi (Japanese chess problem) solver as a typical AND/OR tree search problem.In tsume-shogi, players can reuse captured pieces.Performance evaluation results on 385 problems show that the proposed algorithm is 1.67 times faster on the average than the previous algorithm df-pn.