研究成果

(1)研究上の成果
上記(1)、(2)、(3)の研究上の成果について詳細を述べる。

● 共謀数に基づくゲーム木並列探索手法
共謀数: 共謀数とはAND/OR木で与えられた問題を解くために解かね ばならない部分問題数の最小値である。ノードnの 評価関数h(n)は次式のように定義される。

ゲーム木並列探索: 本方式ではホストプロセッサと複数台のセルプロセッサを用いてゲーム 木を並列に探索する。 ホストはセルの稼働状況を常に管理している。ホストは前述の評価関数 を用いてゲーム木のノードの評価値を求め、min-max法に基づいて未探索 ノードの中から展開するノードを選択し、それら以降の探索を待ち状態 セルに依頼する。そして、セルが生成した部分木をセルから受信しゲー ム木全体を構成していく。 セルは前述の評価関数を用いて横型最良優先探索を行なう。セルは評 価値が特定の値を取るまで、もしくは生成した部分木がある一定の大き さに達するまで処理を続ける。処理を終えたセルは探索した部分木をホ ストに送信する。

実行例: 詰将棋を解くプログラムの実行例を図1に示す。

結果および評価: 本方式の有効性を確認するため、解答能力、処理時間について、共謀数 を用いた方式とmin-max値を用いた方式との比較実験を行なった。 問題は「続詰むや詰まざるや」全２００問の中で逃れ図式や、中将棋の 駒が入った問題を除いた１９６問を用い、１問３０分の制限時間を設け、 それを越えた場合は解けないとした。詰手数別の正解率および平均解答 時間を図２,３に示す。なお、実験は並列計算機AP1000を用い、セルは１６ 台使用した。

図2 「続詰むや詰まざるや」 　　詰手数別正解率	図3 「続詰むや詰まざるや」 　　詰手数別平均解答時間

ゲーム木の評価関数にmin-max値を用いた場合と比較して本方式により 平均正解率は１３.３％向上し、処理時間は１６.５％に短縮された。 これは共謀数を用いた評価関数が詰将棋の局面の詰めやすさと合致し 探索すべき空間が縮小されたためと考えられる。しかし合駒を含む問題 でまだ探索空間が広がる傾向があるため、それを改善するのが今後の課 題である。

● 帰納論理プログラミングを使った詰将棋戦略獲得手法
ILPは、与えられた事例を説明する論理プログラムを帰納的に求めること を目的とする。目標とする述語の正しい事例の集合(正事例)、誤った事 例の集合(負事例)、そして背景知識としていくつかの 述語に関するプログラムを与えることにより目標述語の論理プロ グラムを導出する。本研究ではILPの手法の一つトップダウンアルゴリズ ムに基づくILPシステムFOIL-Iを用いた。

詰め将棋を学習するためのILP: 詰め将棋のような大規模な背景知識を含む問題を扱うため、FOIL-I を以下の点で見直す必要が有る。

• 外延的評価から内包的評価へ: FOIL-Iではリテラルが満たす値の組を全て予めリストとして蓄え、評 価時に事例とそのリストとのマッチングを行う。しかし 広範囲の値を取り得る変数を含む場合ではリストが長大となり効率的処 理が行なえない。そこで、内包的評価法に変更した。

• 出力モードの変数の処理: FOIL-Iでは、目標とする述語の変数は全て入力モードとみなしこれらの 変数を背景知識の出力モードの変数として用いることを禁じていた。そ こで、この制約を緩和した。

• 否定リテラルの評価: 一般に否定リテラルは肯定リテラルに比べて多くの事例が満たされるた め良い評価値を得る。このため否定リテラルに関しては不必要な学習を 繰り返すことが多い。そこで、否定リテラルの学習の展 開をおさえるようにした。

• 背景知識のライブラリ化: FOIL-Iを初めとする多くのILPシステムではこれまで小規模の背景知 識のみを想定していたためユーザにとって知識管理の便利な方法が与え られていな かった。そこで、背景知識の定義をライブラリ化した。

将棋知識の帰納実験と評価: 事例は、正/負事例を各５つずつ与えた。

14個中12個の述語が正しく帰納されること が確認できる。 学習が失敗したものについては,メモリオーバーによるもの と(play)、学習結果の述語の定義が正事例を満たさないもの (gote_defend)がある。 正しく帰納された述語の内4つはリテラル数が人の場合よりも減っている。 これは、不要なものが導かれず効率が向上した場合(movable)と、効率のためのリ テラルを落してしまい、逆に効率が下がった場合(checkmate,他)があっ た。それらに関しては、効率のためのリテラルを見つけ出すシステムが 完成している。

● 並列帰納論理プログラミングシステムの構築手法
本研究ではILPシステムとして知られているFOILを取り上げ、 並列計算機AP1000上で動作する 並列ILPシステムPFOIL(Parallel FOIL)を提案し、その効果を確認する。

PFOILアルゴリズム: PFOILは基本的にFOILと同じトップダウン的なアルゴリズムを用いている。 PFOILのアルゴリズムを図４に示す。

負荷分散による高速化: 高速化のため、各リテラル候補に評価値を設け、各セルの処理量がなるべく均一になるように 負荷分散を行った。 リテラル候補LiについてアリティをAi、正事例の数をPiとするとき、 Liの評価値Eval(Li)をEval(Li)=Ai×Pi で表わし、この評価値に応じて各セルへの負荷が均一になるようにした。

実験及び考察: 図５(a)と(b)にセル台数に応じた実行時間と台数効果を示す、 また、図６(a)と(b)に負荷分散前と負荷分散後のセルの稼働状況の変化 を示す。縦軸は稼働セル数であり、横軸は時間である。負荷分散の結果セル稼働率が30.83%から33.53%に上昇し、実行時間が減少した。 例題としては、目標定義にappendを用いた。

図４ PFOILのアルゴリズム

図５ 実行時間と台数効果

図６ セル稼働状況

外部発表論文

1.

北村 太路, 加藤 昇平, 山田 雅之, 世木 博久, 伊藤 英則 : 共謀数に基づく詰将棋ゲーム木の並列探索, 電気関係学会東海 支部連合大会講演論文集, pp.279, 1996.

2.

N.Inuzuka, M.Kamo, N.Ishii, H.Seki and H.Itoh: ``Top-down Induction of Logic Programs from Incomplete Samples" Proc. 6th Int'l Inductive Logic Programming Workshop, pp. 119-136, 1996.

3.

駒沢 寿夫、北村 太路、犬塚 信博、山田 雅之、 加藤 昇平、世木 博久、伊藤 英則: 帰納学習を使った詰め将棋戦略の学習、情報処理学会第54回全国大会 講演論文集掲載予定

4.

松井藤五郎、犬塚 信博、世木 博久、伊藤 英則: 帰納論理プログラミングにおける追加学習及び理論修正の手法、 電気関係学会東海支部連合大会、1996。

(2) ソフトウェアとしての成果

(3) 残された課題
本年度は戦略獲得の基本的な手法とその高速化を検討した。 より高度な戦略を獲得するための手法を確立し、 それをゲーム木探索にとり入れることが残された課題である。