AND/OR木探索とは、末端の節点がtrue又はfalseの2値を持ち、木の内部節点がAND節点かOR節点で構成されるような木に対して探索を行い、根節点の論理値を求める問題である。AND/OR木で表現できる問題は多数存在する。特に証明数を用いた探索アルゴリズムは詰将棋などのチェス型ゲームの終盤、詰碁、チェッカーの証明などで非常に有効であることが知られている。とりわけ、df-pn(深さ優先証明数探索)は詰将棋、チェッカーの終盤、詰碁などに適用され、大きな成功を収めている。このように、ゲーム中に現れるような複雑なAND/OR木を探索する能力において、今日のコンピュータは人間を上回っていると広く信じられている。

しかしながら、人間には解けるがコンピュータに取っては難しい問題がまだいくつか存在する。代表的な例は、玉が孤立した状態の詰将棋や領域が開いており脱出の可能性のある詰碁である。これらの問題に共通する特徴は、分岐因子が大きく、かつほぼ一様であることである。証明数を用いた探索アルゴリズムは、証明数が一番小さい節点から探索を行おうとする性質がある。証明数とは、ある節点がtrueであると証明するために探索する必要がある節点数の下限である。

ある節点を展開した直後の証明数は、単に分岐因子の数に比例する。そのため、「分岐因子が小さい選択肢ほど見込みがある」という仮定が成り立たない問題に対しては証明数を用いたアルゴリズムは遅くなる。既存のソルバは、それぞれの探索対象に特有の知識を用いてこの問題を解決している。しかし依然として詰将棋は玉が孤立した詰将棋は苦手としており、詰碁は完全に囲われた問題に変換してからソルバに解かせるのが一般的である。

証明数探索には、一番証明が簡単そうな節点から展開するという性質がある。これは多くの問題において有効な性質であるが、例えばalpha-beta探索などの他のアルゴリズムと比較すると、頑固に証明数だけを基準として探索するために他の知識を用いて性能を向上させるのが難しいという面がある。そのために、分岐因子が一様な探索空間、より正確には分岐因子が探索の手がかりにならないような探索空間に対しては、新たな技術を開発する必要がある。

我々は探索空間の性質に依存しない汎用の技術、Dynamic wideningとλdf-pn を提案した。実験の対象となる問題は領域の閉じていない囲碁の問題とした。囲碁を選んだ理由は、これが既存のアルゴリズムに取って最も難しく、また広く知られている問題であるからである。df-pnをdynamic wideningと組み合わせることにより、全合法手を考慮する場合にはdf-pnの性能を25倍程度向上させることが可能であった。しかしながらdynamic wideningは前向き枝狩りと組み合わせると性能向上が見られない。対して λ df-pnは前向き枝狩りの有無に関わらずdf-pnの性能を向上させる。我々はdynamic wideningとλdf-pnを組み合わせて囲碁の問題を解き、性能を測定した。結果として、我々のアルゴリズムは既存のアルゴリズムにとっては難しい分岐因子が一様な問題を解くにあたって有望であると言える。

近年、モンテカルロ木探索をはじめとして、ゲームAIの進展には目を見張るものがあるが、AND/OR木の分岐因子が大きく、ほぼ一様であるような探索問題は、依然としてコンピュータによって解くことが難しい。領域が開いていて脱出の可能性のある詰碁は、その典型例である。証明数探索は、従来のalpha-beta探索とは異なり、探索対象の知識が少ない状況でも十分な性能を発揮し、既存のAND/OR木探索アルゴリズムの中では最も効率がよいと考えられているが、分岐因子が小さい選択肢ほど見込みがあるという仮定に基づいているため、探索対象が一様かつ大きな分岐因子を持つ場合は、やはり有効ではない。したがって、分岐因子が一様な探索空間、より正確には分岐因子が探索の手がかりにならないような探索空間に対しては、新たな技術を開発する必要があった。

本論文では、二つのアプローチに基づいて、分岐因子が大きくかつ一様な探索空間に適した探索アルゴリズムを提案している。一つは、λ探索と証明数探索の融合、もう一つは、dynamic wideningである。具体的な対象としては、領域の開いた囲碁の問題が取り上げられている。これは、囲碁が広く知られている問題であり、また分岐因子が一様かつ大きな問題の中でも最も難しい問題の一つだからである。

本論文は8章から成る。第1章は論文全体の導入であり、第2章では、上述したように、ゲームAIにおける探索アルゴリズムについて広く解説されている。第3章では、本論文のアプローチのもとになっている証明数探索、特にdf-pnについて説明されている。

第4章では、本論文の最初のアプローチについて述べられている。このアプローチは、平坦な探索空間から階層構造を抽出するものであり、特に、既存のアプローチが静的な評価関数を用いて探索の方向を制御するのに対して、実際に探索を行うことによってのみ判明する階層構造を利用する。具体的な階層構造としてはλ探索が用いられ、これをdf-pnに組み込むことによってλdf-pnと呼ばれるアルゴリズムが開発されている。このアルゴリズムは、探索空間をλorderという概念に基づいて分類しながら探索を行う。実際に、分岐因子が大きくかつ一様な探索空間において、既存の最高のアルゴリズムであるdf-pnと比較して、λdf-pnが大幅に速度性能を向上させることが示されている。

第5章では、本論文の第二のアプローチについて述べられている。このアプローチは、有望でない枝を探索中に自動的に無視するものであり、具体的には、dynamic wideningという手法を用いて、証明数探索において有望でない枝を無視する。実際に、df-pnとdynamic wideningを組み合わせることによって、分岐因子が一様かつ大きい探索空間においは、df-pnの速度性能が向上することが示されている。

第6章では、dynamic wideningとλdf-pnを組み合わせ、実際に囲碁の問題を解くことにより、その性能が測定されている。測定の結果は、探索対象に関するヒューリスティックな知識を全く用いない実験であったことを考慮すると、十分に満足すべきものであった。

第7章では、λdf-pnを用いることにより、探索領域を他の領域から孤立化させる手法であるinversionの性能が向上することが示されている。

以上をまとめるに、本論文では、二つのアプローチに基づいて証明数探索の性能を向上させる二つのアルゴリズムが開発された。これらのアルゴリズムは、AND/OR木の分岐因子が大きく、ほぼ一様であるような探索問題に対しても有効であり、したがって、ゲームAI分野のAND/OR木探索問題の中で、人間がコンピュータに対抗し得る一群の問題に対しても適したアルゴリズムとなっている。これらの成果は、ゲームAI分野への貢献として著しいと考えられる。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。