Multiple-paths search with concurrent thread scheduling for fast AND/OR tree search

Fumiyo Takano*, Yoshitaka Maekawa, Hironori Kasahara

*この研究の対応する著者

研究成果: Conference contribution

2 被引用数 (Scopus)

抄録

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.

本文言語English
ホスト出版物のタイトルProceedings of the International Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2009
ページ51-58
ページ数8
DOI
出版ステータスPublished - 2009
イベントInternational Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2009 - Fukuoka, Japan
継続期間: 2009 3月 162009 3月 19

出版物シリーズ

名前Proceedings of the International Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2009

Conference

ConferenceInternational Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2009
国/地域Japan
CityFukuoka
Period09/3/1609/3/19

ASJC Scopus subject areas

  • ハードウェアとアーキテクチャ
  • ソフトウェア
  • 制御およびシステム工学

フィンガープリント

「Multiple-paths search with concurrent thread scheduling for fast AND/OR tree search」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル