詰将棋のようなパズルにおいて,勝ち敗けやその手順を知るための探索はAND/OR木探索として一般化できる.AND/OR木探索において重要な2つの概念に,証明数と反証数がある.証明数は勝ちを知るための探索に重要な役割を果たし,反証数は負けを知るための探索に重要な役割を果たす.AO*はAND/OR木を探索して,勝ちを知るための代表的アルゴリズムである.逆に言うと,負けを知るのは苦手である.これはAO*が証明数のみを用いているためである.またAllisは証明数と反証数の両方を用いた,pn-searchという探索法を提案している.AO*もpn-searchも共に最良優先探索法である.深さ優先探索法としては,脊尾により独特な探索法が提案された.脊尾のアルゴリズムは証明数のみを用いた深さ優先探索法である.この論文ではdf-pnという,証明数と反証数の両方を用いた新たな深さ優先探索法を提案する.df-pnの最大の特長は,常にmost-proving nodeという節点を展開するという意味で,最良優先探索法であるpn-searchと同等の振る舞いをすることである.このことも証明する.

　df-pnの実際の応用として,詰将棋の問題を解くプログラムを作成した.詰将棋を解くプログラムの研究は,証明数や反証数の導入により,この10年の間に大きく進歩した.詰将棋に適用すると,直感的に言うと,証明数は玉の逃げ方の総数を,反証数は攻め方の王手の総数を表す.前者は攻め方にとって,後者は玉方にとって非常に重要な値である.この論文では,df-pnアルゴリズムを用いて詰将棋を解く強力なプログラムを作成する過程で導入した様々な技法を提案する.これらの技法をdf-pnの上に実装することにより,我々のプログラムでは300手以上の詰将棋のすべてを解くことに初めて成功した.しかもそれは,シングルプロセッサのワークステーションで解くなど,解答能力と解答時間の両面で優れた結果を出すことができた.

　詰将棋の用語に,余詰と変別解がある.詰将棋において,作者の作意手順中では,詰ますための攻め方の王手は原則として唯一でなくてはならない.作意以外の王手でも詰ますことが出来るなら,その解を余詰と呼び,その作品は不完全作として扱われしまう.従って余詰の発見は重要である.余詰を発見するための探索を余詰探索という.また,余詰は作意手順中にあってはならないが,作意手順以外の枝葉の部分にはあっても良い.そのせいで,詰将棋の手順を答えるとき,枝葉の部分で,より手数の短い詰みを発見出来ないばかりに,作意手順の途中から玉方の受けの違う解を答えてしまうことがある.このような解は変別解と呼ばれ,間違いではないが不満が残る.人間の場合は,詰将棋の作者の意図を読み取って,自分の暫定解を正すことができるが,コンピューターの場合はそうはいかない.これを解消するには,普通に詰むことを調べた後,変別を除去するような処理をしなくてはならない.この論文では,証明数・反証数のみを使った探索法を用いながら,余詰探索と変別除去を同時に行える手法を提案する.

　変別除去を行っても,時間的な制約上必ずしも作意手順を発見できるとは限らない.そのような場合,作意手順も与えた上で,余詰があるかどうか探索するのが,詰将棋作家にとって,また作品の評価にあたって,重要になる.この論文では,作意手順も与えた上での余詰探索の結果を提示する.

　詰将棋より一段難しい問題に,必至問題というジャンルの問題がある.指将棋の終盤戦では,必至問題を解く能力は,詰将棋を解く能力と並んで重要になってくる.近年.必至問題を解くアルゴリズムの研究も注目されるようになってきている.しかしながら,まだ実用として使うには様々な問題を抱えている.そこで,df-pnアルゴリズムを用いて必至問題を解くプログラムを作成した.我々のプログラムは構造上は従来のプログラムに比べると単純な作りになっているが,非常に高速に必至問題を解くことができる.

　思考ゲームのプログラムを実装するにあたって,探索アルゴリズムと共に重要な役割を果たすのはハッシュの実装である.ハッシュは最良優先探索法におけるリストに相当し,それまでの探索によって得られた情報を蓄えておくデータベースのような役目を果たす.証明数や反証数を用いた深さ優先探索法の場合は特にハッシュの実装の重みが増す.しかし,ハッシュの実際の実装法については殆んど論じられることはなかった.そこで,我々のプログラムで実装したハッシュについて,既存の方法と比較しながら説明する.

本論文では詰将棋のようなパズルにおいて勝ち敗けやその手順を知るため,AND/OR木の効率的な探索方法を提案しており,従来解くことが困難だった問題でさえも,小さな資源(主記憶)の計算機を使って解くための道筋を開いている.

AND/OR木探索において重要な2つの概念に,証明数と反証数がある.証明数は勝ちを知るための探索に重要な役割を果たし,反証数は負けを知るための探索に重要な役割を果たす.例えば,AO*はAND/OR木を探索して,勝ちを知るための代表的アルゴリズムであるが,負けを知るのは苦手である.なぜならAO*が証明数のみを用いているためである.またAllisは証明数と反証数の両方を用いた,pn-searchという探索法を提案している.AO*やpn-searchが共に最良優先探索法であるのに対して,これらと対峙するアプローチとして深さ優先探索法があり,脊尾により改良が試みられている.脊尾のアルゴリズムは証明数のみを用いた深さ優先探索法である.これら過去に提案された有効な方法を組み合わせることにより,この論文ではdf-pnという,証明数と反証数の両方を用いた新たな深さ優先探索法を提案している.df-pnの最大の特長は,常にmost-proving nodeという節点を展開するという意味で,最良優先探索法であるpn-searchと同等の振る舞いをすることであり,本論文ではこの性質が証明されている.

df-pnの実際の応用例として詰将棋が取り上げられている.詰将棋を解くプログラムの研究は,証明数や反証数の導入により,この10年の間に大きく進歩してきている.詰将棋に適用すると,直感的に言うと,証明数は玉の逃げ方の総数を,反証数は攻め方の王手の総数を表す.前者は攻め方にとって,後者は玉方にとって非常に重要な値である.本論文では,df-pnアルゴリズムを用いて詰将棋を解く強力なプログラムを開発しており,300手以上の詰将棋のすべてを解くことに初めて成功している点が特筆に価する.従来,将棋に似た例でいえば,世界チャンピオンに勝ったチェスのプログラムなどは,IBM社の巨大な並列計算機の計算パワーに依存していた面もあった.しかし本論文が提案する方法では,シングルプロセッサのワークステーションで解くなど,標準的な計算資源をもつ計算機を利用しても,解答能力と解答時間の両面で優れた結果を出すことができている.平たく言えば家庭のPCでも難解な詰将棋を解くことを可能にする方法論を確立したといえる.

さらに本論文では詰将棋の周辺にある様々な問題に対する解法も提示している.詰将棋においては,作者の作意手順中では,詰ますための攻め方の王手は原則として唯一でなくてはならない.しかし,作意以外の王手でも詰ますことが出来てしまう場合には,その解を余詰と呼び,その作品は不完全作として扱われしまう.従って余詰の発見は作品評価の上でも重要であるが,その発見は困難を伴う.余詰を発見するための探索を余詰探索という.また,余詰は作意手順中にあってはならないが,作意手順以外の枝葉の部分にはあっても良い.そのせいで,詰将棋の手順を答えるとき,枝葉の部分で,より手数の短い詰みを発見出来ないばかりに,作意手順の途中から玉方の受けの違う解を答えてしまうことがある.このような解は変別解と呼ばれ,間違いではないが不満が残る.人間の場合は,詰将棋の作者の意図を読み取って,自分の暫定解を正すことができるが,コンピューターの場合はそうはいかない.これを解消するには,普通に詰むことを調べた後,変別を除去するような処理をしなくてはならない.本論文では,証明数・反証数のみを使った探索法を用いながら,余詰探索と変別除去を同時に行える手法を提案している.変別除去を行っても,時間的な制約上必ずしも作意手順を発見できるとは限らない.そのような場合,作意手順も与えた上で,余詰があるかどうか探索するのが,詰将棋作家にとって,また作品の評価にあたって,重要になる.本論文では,作意手順も与えた上での余詰探索の結果を提示している.

もう1つ詰将棋周辺の問題として必至問題というジャンルがあり,より難しい問題とされている.指将棋の終盤戦では,必至問題を解く能力は,詰将棋を解く能力と並んで重要になってくる.近年.必至問題を解くアルゴリズムの研究も注目されるようになってきている.しかしながら,まだ実用として使うには様々な問題を抱えている.本論文では,df-pnアルゴリズムを用いて必至問題を解くプログラムを作成している.本論文が提案するプログラムは,構造上は従来のプログラムに比べると単純な作りになっていながら,非常に高速に必至問題を解くことができることが確認されている.

最後に,実行中の主記憶消費量を低減させる工夫も提案している.思考ゲームのプログラムを実装するにあたって,探索アルゴリズムと共に重要な役割を果たすのはハッシュの実装である.ハッシュは最良優先探索法におけるリストに相当し,それまでの探索によって得られた情報を蓄えておくデータベースのような役目を果たす.証明数や反証数を用いた深さ優先探索法の場合は特にハッシュの実装の重みが増す.しかし,ハッシュの実際の実装法については殆んど論じられることはなかった.本論文では,限られた主記憶の資源の中で重要な局面を残すためのハッシュ実装を提案し,詰将棋を例題にその有効性を確認している.

尚,本論文は今井浩との共同研究であるが,論文提出者が主体となってアルゴリズムを考案し,有効性を実証しており,論文提出者の寄与が十分であると判断する.従って,博士(理学)の学位を授与できると認める.