並列ゲーム木探索のための分散共有ハッシュ法の評価

• Item type: SIG Technical Reports(1)
• 公開日: 2000-03-07
• タイトル: 並列ゲーム木探索のための分散共有ハッシュ法の評価
• タイトル / 言語: en
• タイトル: Some Experiments on the Distributed Shared - Hashing Method for Searching Game - Trees in Parallel
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学電気通信学部情報工学科
• 著者所属: 電気通信大学電気通信学部情報工学科
• 著者所属: 電気通信大学電気通信学部情報工学科
• 著者所属: 電気通信大学電気通信学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro - Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro - Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro - Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro - Communications
• 著者名: 佐藤, 信弘; 新藤, 雅也; 野下浩平; 中山, 泰一
• 著者名(英): Sato, Nobuhiro; Shindo, Masaya; Kohei, Noshita; Yasuichi, Nakayama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ゲーム木探索における局面表（トランスポジション表）は，局面の探索結果を表に登録し，同一局面の探索を表の参照ですませる技法である．本論文では，並列的なゲーム木探索のために計算機間で共有する局面表を実現し，その有効性を実験的に評価する．実験対象として並列選択の比較回数を決定する探索問題をとりあげる．通信速度の遅いネットワークで結合された並列計算環境において，分散的に共有するハッシュ法による共有局面表の実現方法を2種類比較する．代表的な並列アルゴリズムを2つ選び，実行時間や各種オーバーヘッドを測定し，共有局面表の効果を調べる．著しい結果として8台の計算機により逐次計算の7倍以上の速度向上をえた．また逐次計算では時間がかかりすぎ解けなかった問題が共有局面表による並列計算で解くことができた．本論文の分散共有ハッシュ法により，並列計算の性能向上の目標である十分良い台数効果が実現できることを実証した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In game-tree searching, transposition tables are used for eliminating repetitions of the identical computation for reappeared positions. For parallel searching on a distributed parallel computer-cluster, two types of the shared-hashing method are presented for implementing the global transposition table. For evaluating our method in terms of various overheads as well as the computation time, a certain selection problem is used and two parallel algorithms are implemented to solve it. As one of our experimental results, more than seven-fold speedups have been achieved on eight processors. By our method, several instances of the problem have been solved, which could not be solved on a single computer. The experiments have proved that our distributed shared-hashing method is efficient enough to show a good performance near the maximum on a distributed parallel environment with slow interprocessor communication.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11362144
• 書誌情報: 情報処理学会研究報告ゲーム情報学（GI）; 巻 2000, 号 27(1999-GI-002), p. 63-70, 発行日 2000-03-07
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会