知的ゲームを題材としたプログラムに関する研究は人工知能や計算機科学の初期の頃から行われていた．ゲームには勝ち負けがあるため，技術の進歩がはっきりと表われることや，様々な種類のゲームが存在するため，常に適度な難易度のゲームが存在することなど，様々な理由によりゲームは研究の題材として適切なのであろう．

　多くのゲームでは，物量的な指標を用いてどちらのプレイヤがどれだけ有利・不利かを評価することできる．例えば将棋やチェスのようなゲームでは駒の数などをどちらのプレイヤがどれだけ有利な局面であるかの判断に用いることができる．

　しかし，ゲームによってはこのような物量的な指標とは無関係に勝負が決まるゲームも多い．チェスや将棋も，終盤になれば物量的な面では不利な手が良い手となることも少なくない．従来より，計算機はこのような状況では良い手を見つけることを苦手としてきた．

　このような局面では「手数」を利用した判断をすることが可能なことがある．将棋などでも，中上級者は終盤になると「何手相手の攻めを気にせず攻められるか」「こちらから攻めた場合，相手は何手こちらを無視することができるか」といった情報を利用して局面の有利不利を判断することがある．

　脅威度は，このような手数に関連する概念であり，脅威度の次数とは，その脅威度に対して相手プレイヤが負けるまでに手抜きをすることのできる回数である．次数の小さい手に対しては，相手は早く対応する必要がある一方で，次数の大きい手は無視することができる．例えば将棋における王手は次数が1の手となる．

　脅威度を利用する探索手法にはAllis によるDependency based search やThomsen によるλ-探索，Cazenave によるGeneralized Widening 等がある．また，将棋における詰探索や必至探索も脅威度を利用した探索の一種であり，詰探索はλ1-探索(脅威度一手分の手のみを探索するλ-探索)，必至探索はλ2-探索(脅威度二手分の手のみを探索するλ-探索) に対応する．

　Allis はDependency based search と証明数探索を組み合わせることで五目並べが先手勝ちであることを証明した．またThomsen やCazenave は碁を題材とした研究をしており，碁の部分ゲーム探索で効率の良い探索を実現している．

　脅威度を利用した探索は非常に効率的に探索を行うことができる上に，多くの前向き枝刈りの手法と違い，探索の結果の正しさが保証されている．ただ，ある手に脅威度があるかどうか調べるために探索が必要であり，特に次数の大きい手を含めて探索しようとする場合には計算コストが膨大となる．また，ゲームの部分の探索に特化したアルゴリズムであり，片方のプレイヤによる脅威度のみに注目して探索を行うため，ゲーム全体を対象とした探索を行う場合の性能は保証されていない．

　df-pn 探索アルゴリズムは長井によって提案されたAND/OR 木探索のためのアルゴリズムであり，現在知られているものの中で最も優秀なものである．df-pn 探索は証明数と反証数という二つのしきい値を用いて探索する縦型探索であり，未展開ノードを展開する順番が最良優先探索アルゴリズムである証明数探索と同じであることが知られている．長井はdf-pn 探索アルゴリズムを用いることで今まで知られている詰将棋の問題を全て解くことに成功し注目を集めた．

　本論文では，脅威度を利用した探索手法を二つ提案する．一つはλ-探索をdf-pn 探索を組み合わせたdf-pn 駆動λ-探索であり，もう一つは双方の脅威度に注目した探索を行うdual λ-探索である．

　Df-pn 駆動λ-探索はdf-pn 探索とλ-探索を組み合わせることで，深さ打ち切りのλ-探索で解けなかったような長い手順を含む問題を扱えるようにしたものである．λ-探索では注目している脅威度次数の大きさよって探索の対象となる木の範囲が変化するため，証明数や反証数が変化してしまう．そこで，df-pn 駆動λ-探索では各脅威度ごとに証明数・反証数を別に管理することでこれに対応した．また，OR ノードにおいて証明に適した次数での探索をおこなうために，次数に応じた仮想ノードを設定し，仮想ノードの選択を拡張戦略として整理し複数の戦略を適用可能な形で形式化した．

　Dual λ-探索は双方のプレイヤの脅威度を利用した探索アルゴリズムである．これはAND ノードにおいて，より次数の小さいプレイヤの脅威度に注目して探索ノードを選択する方法である．またdf-pn 駆動dual λ-探索を提案した．これは各プレイヤの脅威度ごとに証明数と反証数を計算し，それに基いて探索ノードを選択する方法である．

　Df-pn 駆動λ-探索及びdf-pn 駆動dual λ-探索の性能を評価するために将棋の終盤の局面を解かせる実験を行った．

　Df-pn 駆動λ-探索を評価するために，反復深化駆動λ-探索との比較の実験を行った．将棋の片玉必至問題149 問を対象とした．その結果，反復深化駆動λ-探索は問題を一問も解くことができなかったが，df-pn 駆動λ-探索は41 問解くことができ，df-pn 駆動λ-探索の性能を示すことができた．また，様々な改良を加えたdf-pn 駆動λ-探索で実験したところ134 問解くことができ，従来の人の手によって調整がなされたプログラムに近い成績を出すことができた．

　次にdf-pn 駆動dual λ-探索の性能を評価するために，Df-pn 駆動λ-探索との比較を行なった．計算機の苦手とする将棋の問題を集めたGrimbergenの将棋問題集のうち，終盤の問題97 問を対象とした．その結果df-pn 駆動λ-探索では6 問解けたところがdf-pn 駆動dual λ-探索では11 問解け， df-pn駆動dual λ-探索の性能を示すことができた．

　本論文は, ゲームプログラミングにおいて広く用いられるAND/OR 木の探索を扱っている．チェスや将棋のような二人完全情報零和ゲームをプレイするプログラムを作成する場合は，ミニマックス法などのゲーム木探索に基づくアルゴリズムが有効であることが知られている．ゲーム木のうちでも末端における評価値が2 値であるものは特にAND/OR木と呼ばれている．ゲームの終盤等の探索はAND/OR木としてモデル化が可能である．本論文は，AND/OR 木の探索を対象としたdf-pn 駆動λ-探索，df-pn 駆動dual λ-探索という二つの新たな探索アルゴリズムを提案し，実験によって有効性を確かめたものである．

　本論文は6 章から成る．第1 章では研究の背景として，ゲーム木探索とAND/OR木の関係，脅威度に基づいた探索，実験対象として扱った将棋のゲームとしての性質について述べている．

　第2 章では本論文と関連の深い二つの研究について紹介している．一つは証明数に基づく探索で、一つは脅威度に基づく探索である．証明数に基づく探索は，展開途中の木の形から導き出される予想コストを使った最良優先探索であり，中でもdf-pn探索というアルゴリズムが，詰将棋問題を解くプログラムなどで使われて成功を収めている．脅威度に基づく探索は，ゴールとの距離を用いた最良優先探索である．中でも脅威度をゲーム固有の性質を用いずに片方のプレイヤーが何回パス可能かを示すλ-次数で表現し，λ-次数を探索によって求めるλ-探索が，多くのゲームに適用可能だという点で有望だと考えられている．ただ，λ-探索は深さベースの反復深化を用いているので，手数の長い解を見つけにくいという弱点がある．

　第3 章ではλ-探索とdf-pn 探索を組み合わせたdf-pn 駆動λ-探索アルゴリズムを提案している．これはノードの証明数，反証数をスカラー値ではなくλ-次数ごとのベクトル値とすることにより，この二つのアルゴリズムの自然な融合を実現したものである．また，OR ノードにおいて証明に適した次数での探索をおこなうために，次数に応じた仮想ノードを設定し，仮想ノードの選択を拡幅戦略として整理し複数の戦略を適用可能な形で形式化した．この拡幅戦略として，λ-探索で使われていた反復拡幅戦略と，必至問題ソルバで使われていた固定順序戦略以外に，証明数拡幅戦略という新たな戦略を提案している．また，詰将棋ソルバなどで使われていたNull手優先，証明木トレース，df-pn+ 探索等のアルゴリズムをλ-探索に関する強化として一般化し，形式化をおこなっている．ゲーム固有の性質を用いないというλ-探索の特徴を生かしつつ，カスタマイズが可能なアルゴリズムを提案している点を本審査委員会は高く評価する．

　第4 章では敵味方がそれぞれ別のゴールを目指している状況で効率的な探索をおこなうアルゴリズムとして，df-pn 駆動dual λ-探索アルゴリズムを提案している．ゲームの実戦では片方のプレイヤーがゴールに近づこうとする手が，他方のプレイヤーもゴールに近づけてしまうということが良くある．df-pn 駆動dual λ-探索アルゴリズムは双方のプレイヤーのλ- 次数ごとの証明数，反証数のベクトル値を保持して，それに基づいた探索ノードの選択をおこなうことで，安全に勝つ手を優先的に探索するものになっている．この提案はλ-探索の自然な拡張であり，効果も期待できる点で評価できる．

　第5 章では将棋の終盤問題を題材にした実験をおこない，提案する探索アルゴリズムの有効性を確認している．本論文で扱うアルゴリズムは，無限のリソースを使うとどれも同じ解を返すものなので，消費するリソースの量で評価するのが望ましい．ただ，現状ではリソースの制限により解けない問題もあるので，記憶するノード数を100 万に制限するという条件のもとで，どれだけの問題を解けるか，解ける場合はどれだけのノード数を要したかで比較して評価をおこなう．まず，λ-探索とdf-pn 駆動λ-探索の比較を将棋の必至問題の問題集を対象におこない，λ-探索では制限内に1 問も解けなかったのに対して，df-pn 駆動λ-探索では同じ制限で3 割弱の問題が解けるようになったことを確認した．また，Null 手優先と証明木トレースの二つの強化を加えると6 割弱の問題が解けるようになることを示した．それに加えて，詰将棋問題ソルバで用いられている将棋特有の強化についても個別に評価し，それらを組み合わせることで8 割以上の問題が解けるようになることを示した．これらの強化を入れたプログラム上で拡幅戦略の評価をおこなった．その結果，必至問題に限れば固定順序戦略が，詰将棋問題に限れば反復拡幅戦略が適しているが，総合すると証明数拡幅戦略が一番優れていることを示した．df-pn 駆動dual λ-探索アルゴリズムに関しては，実戦で生じた局面と，難しい問題集の両方を対象に，df-pn 駆動λ-探索アルゴリズムと比較をおこない，どちらに関しても解ける問題数の向上が見られることを確かめた．現在ゲームプログラム研究で一番注目されている将棋を対象に実用的な実験をおこない，良い結果を出している点が評価できる．第6 章では，以上の結果を元に，結論と今後の課題について述べている．

　以上のように本論文はゲームプログラミングにおいて広く用いられるAND/OR木探索において新たなアルゴリズムを提案し，その有効性を確かめたという点で，ゲームプログラミング研究に対する大きな学術的貢献が認められる．したがって，本審査委員会は博士(学術) の学位を授与するにふさわしいものと認定する．