(18) 詰将棋における戦略の獲得方法に関する研究

［目次］

1. 研究の背景
2. 研究の目的
3. 研究内容
4. 研究体制／研究方法
5. 想定されるソフトウェア成果

［研究の背景］

人工知能研究の一分野にゲームプログラミングがある。これまてゲーム として、チェスや将棋、囲碁が取り上げられ、それぞれの特徴や難易度 にあわせて、計算機で解くためのさまざまな方法が研究されてきた。近 年では、コンピュータアーキテクチャの技術革新により、大きな処理能 力をもつ並列計算機を用いることができ、従来とは違ったアプローチで このゲームを解く可能性がでてきた。チェスでは、チェス専用並列マシ ンが開発されている。また、ICOT公開ソフトウェアの一つ「碁世代」は 囲碁の大規模知識処理システムに並列処理をとりいれている。

本研究では問題を詰将棋に限定する。詰将棋を解くプログラムはこの 20年来数多く作られてきたが、1991年はじめには、13手詰くらいの問題 がやっと解ける程度であった。しかし、最近、伊藤、野下、脊尾らはワ ークステーション上でかなり優れたプログラムを作成し、100手詰め以 上の問題もかなりとけるようになった。しかしながら、依然として（人 間は解けるが）解けない問題も多い。

計算機の解答能力を人間レベルに到達させるための一つのアプローチ として、並列処理を用いることが考えられる。詰将棋では、ある局面に おいて評価値の最大となる手が正解であるとは限らず、2番目や3番目の 評価値を持つ手が正解となる場合がある。並列探索の場合は、これら2番 目、3番目の手を評価値最大の手とほぼ同等に探索できる。我々はこの点 に注目し、詰将棋のゲーム木を並列に探索するプログラムを作成した。 これまでに得られている結果を以下に示す。

・高速解答

内藤国雄問題集の全180問を79秒で解いた（下記文献 1)2)参照）。

・長詰め手数問題に対する高解答率

共謀数の概念を取り入れプログラムを改良した結果、長詰め手数問 題集「続・詰むや詰まざるや」全200問の約7割を解いた（下記文献 3)参照）。

＜参考文献＞
1) 詰将棋におけるゲーム木の並列探索とその評価、情報処理学会論文誌 、Vol.36、No.11。
2) 詰将棋におけるプロセッサ稼働率を考慮したゲーム木並列探索、情報 処理学会論文誌、Vol.37、No.9 掲載決定。
3) 詰将棋におけるゲーム木並列探索のプロセッサ稼働率に基づく効率化 方法と共謀数に基づく並列優先探索による解答能力の改善、第１０回 人工知能学会全国大会予稿集 H8.6.26。

しかしながら、玉の自由度などの単純な評価関数を用いたこれまでの探索 では限界がある。そこで本研究では、大量にある詰将棋問題から専門家の 戦略を獲得し、その戦略に基づき並列探索する方法について研究する。

［研究の目的］

本研究の目的を以下に示す。

（１）詰将棋問題集からの戦略の獲得方法の確立

従来は玉の自由度などを基にした単純な評価関数を使って探索を行な っていた。しかしながら、単純な評価関数に基づく探索では解けない 問題も多い。詰将棋問題集から戦略を獲得する方法を確立し、得られ た戦略を探索に反映させることにより解答能力の向上を狙う。

（２）戦略獲得処理の並列化による高速化

上記（１）の戦略獲得では、大量の問題（事例）を取り扱う必要があ る。本研究では戦略獲得に並列処理を取り入れ、高速化を狙う。

（３）獲得した戦略に基づいた並列探索方法の確立

獲得した戦略に基づいた効率の良い並列探索方法を確立する。

（４）長詰め手数問題を高速に解くプログラムの作成

上記（１）（２）（３）の方法を用いて長詰め手数問題を高速に解く プログラムを作成する。従来は１００手以上の詰将棋を解くことが困 難であったが、本研究は「寿」（６１１手詰め）や「新扇詰」（８７ ３手詰め）を高速に解くプログラムを作成することを目的とする。

（５）詰将棋システムの作成

上記（４）のプログラムを基に詰将棋システムを作成する。ソフトウ ェア公開にむけ、詰め過程のグラフィカルな表示、評価関数のユーザ による調節機能などを備えたインターフェースを作成する．

［研究内容］

上記目的のため、まず、以下３つの課題を検討する。
（１）詰将棋問題集からの戦略の獲得方法
（２）戦略獲得処理の並列化方式
（３）獲得した戦略に基づいた並列探索方法

（１）詰将棋問題集からの戦略の獲得方法

従来は玉の自由度（玉が逃げれるマス目の総数）や共謀数（玉方の可能な 手の総数）に基づく単純な評価関数を用いて探索を行なった。しかしなが ら解答能力向上のためには専門家レベルの戦略知識を探索に反映させる必 要がある。そこで、詰将棋問題集からの戦略の獲得を試みる。

本研究では問題集にみられるさまざまな手を一般化し、それを戦略とみ なす。手の一般化には帰納学習と遺伝的アルゴリズムを用いる方法を検討 する。戦略獲得のための作業手順を以下に示す。

1. 詰将棋問題集における問題とその解法から、 局面とその局面における正解手の組み（下記）をつくる。

（Ｓ、Ａs）、Ｓ：ある局面（番面）

Ａs：正解手＝Ｓから詰みに至るための次の一手

2. この組み（事例）は問題集より大量に得られる。
事例を一般化して次のような戦略を獲得する。

C1,C2,...,Cn ⇒ D1,D2,...,Dm　

ここでCiは局面の満たすべき条件を、Diは正解手が満たすべき条件 （制約）を表す。すなわち、この戦略はC1,C2,...,Cnを満たす局面 ではD1,D2,...,Dm を満たす手を打つことを意味する。詰将棋では 王手となる手を打たなければならないことより、D1〜Dmのうちの一 つは「王手である」という制約である。

（２）戦略の獲得の並列処理方法

戦略獲得では大量データを取り扱うことから、並列処理を用いて処理速度の 高速化をはかる。これには帰納学習による処理と遺伝的アルゴリズムによる 処理を各々並列化する。プログラミング言語にはKL1を用いる。

（３）獲得した戦略に基づいた並列探索方法の確立

獲得した戦略に基づいた並列探索方法の確立するため、以下の作業を行なう。

1.　ある局面が戦略 C1,C2,...,Cn ⇒ D1,D2,...,Dm の条件部 C1,C2,.. .,Cn を満たすか否かの判定アルゴリズムを確立する。

2.　制約 D1,D2,...,Dm を満足たす手を生成する方法を確立する。

3. 　2において複数の手が生成された場合、各々の手の場合を並列に探索 する方法を確立する。

なお、並列探索については、(3)研究の背景で述べたように、これまでいくつ かの方法を提案したが、負荷分散方式やプロセッサ間通信方式等を改善する 必要がある。ここでは並列探索プログラミングにKL1言語を用い、負荷分散方 式やプロセッサ間通信方式の改善について検討する。

上記（１）、（２）、（３）の方法に基づき下記（４）と（５）と行なう。

（４）詰将棋を解くプログラムの試作
詰将棋を解くプログラムを試作し、様々な問題をとかせ、各種パラメータを調 節し、最適値に近付けるとともに、その処理速度と解答能力を評価する。また 、単純な評価関数を用いて探索する従来プログラムとの比較も行なう。この時 点で当初の目標である長詰め手数問題（「寿」６１１手詰め や「新扇詰」８７ ３手詰め）における高速解答が可能か否かを調べ、期待した性能が得らねなけ れば、再度、（１）、（２）、（３）における問題点を調査し、この解決策を 検討する。

（５）詰将棋システムの作成