ゲーム木の高速探索と求解法

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

ゲーム木の高速探索ならびに求解のための新しいアルゴリズムをいくつか開発し,詰将棋を解くプログラムに応用した.プログラムT1とT2に実現した新しい技法の主なものは次のとおりである.1.探索木の各節点における先読みを動的に調整する方法.2.一種の学習による候補手生成順序の動的な変更法.3.乱数とハッシュ法を利用した同一(および類似)局面再現の判定法.4.下降型の解探索によるある型の解を厳密に求める求解法.そのほか,詰将棋の問題特有の高速技法をいくつか考案した.このような技法を応用して開発した詰将棋プログラムは次のような特徴をもつ.1.人間のエキスパートの能力に匹敵するはじめてのプログラムである.2.短篇問題はすべて解くことができ,そのうち大部分のものについて人間より速く解く.ほかのどのプログラムより圧倒的に速い.3.従来コンピュータで解けなかった中篇問題もある程度解ける.4.実用的な余詰検査プログラムに応用するとともに,歴史的な作品の中に余詰のある問題を数多く発見した.本研究のT1により詰将棋システム作成の技術水準は著しく向上した.その後改良版T2と伊藤琢巳(NTT)のItoが開発され,この2つが現在最も進んだシステムとされる.これらは互いに得意な問題領域をもち相補的な解答能力をもつ.なお,T2などの詰将棋システムは既に次のものなどいくつかの記事で解説されている.1.野下,詰将棋プログラムの最近の進歩,詰棋めいと,14(1993),77-80.2.小谷,松原,大沢,情報処理最前線:コンピュータは人間に勝てるか,情報処理,34,3(1993),274-285.