分散的並列計算によるゲーム木の高速探索法

点击翻译按钮获取中文摘要

本研究の目的は,多数のワークステーションによる分散的な並列計算システムの上で,長時間かかる非常に深いゲーム木を高速探索するためのアルゴリズムを開発することである.まず,ゲーム木の並列探索のための基本操作の組を定義して,それを分散システムの上で実現した.また,この基本操作の基本性能を実験的に評価した.使用したワークステーションの台数は最大で64である.次に,この分散システムの上で,ゲーム木の並列探索のためのマスターとスレーブからなる並列計算モデルを設定した.ゲーム木の事例研究として,詰将棋を解く問題を取り上げ,特に,遂次型アルゴリズムでは長時間かかったり,あるいはすべての問題を完全には解けないというような難しい問題群を選んだ.ここで開発した並列アルゴリズムによって,これまでの遂次型アルゴリズムで非常に長い時間のかかる問題を短い時間で解けることを示した.さらに,これまで解けなかった問題をはじめて解くことができた.特に,深さ優先にもとづく遂次型アルゴリズムで,これまで最も優れた性能をもつものと比較して,問題を解く時間が台数以上の倍率で短くできるような実例を示した.このように分散的並列アルゴリズムによって,ゲーム木の探索を著しく高速化できることを実証したのは本研究の主たる成果である.そのほか,多数のワークステーションが共有できる大域的ハッシュ表の設計と実現を行い.その基本性能を評価した.これはゲーム木の分散的並列探索における新しい研究課題を提起するものである.