探索問題の近似ハッシュ法とその応用

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

本研究の目的は,探索問題における近似ハッシュ法の設計と実現法を調べ,具体的なゲームの探索問題に応用してその有用性を実験的に示すことである.ここでは,具体例として詰将棋と対局将棋をとりあげる.近似ハッシュ法は,チェスプログラムで考案された局面表の一般化と考えられるもので,計算状況(局面)の同一であることの探索のほか,類似した近似局面の探索に用いる.本研究での将棋の場合,壁面が同一で持駒の異なるほぼ同一の局面のほかに,一方の局面で有効な着手が他方の局面でも有効でありうるようなものとして近似局面を定義する.本研究では単一のCPUでの逐次探索のほか,多数のCPUでの並列探索も取り上げる.主たる研究成果としては,非常に手数の長い難しい詰将棋問題を解くための逐次プログラムを開発したことである.ここでのいくつかの新しい方法の中には近似局面による候補手の優先的な選択法がある.これによって従来のプログラムより解答能力が向上するとともに,多くの場合解答速度も向上した.その一例としては,研究代表者による旧プログラムで611手詰のある問題をはじめて解いた時に約60時間かかったが,新プログラムでは1時間以下で解けるようになった.そのほか,詰将棋を解く並列プログラム,また対局将棋の逐次プログラムの開発をおこない,いくつかの新しい結果を出した.これらの結果の主なものは論文雑誌や国際会議などで発表した.