(57)【要約】【課題】  ＡＮＤ／ＯＲグラフ構造の解析アルゴリズムにおいて、証明数、反証数を用いることによって生じる不具合を解決する新たな概念を取り入れたグラフ探索アルゴリズム及びグラフ探索装置を提供する。【解決手段】  この発明に係るアルゴリズムは、少なくとも１つ以上の解に至る分枝を含むＯＲ節点と、全てが解に至る分枝であるＡＮＤ節点とが交互に現れるグラフについて始点から解までの経路を探索するグラフ探索アルゴリズムにおいて、少なくとも始点から任意の節点に至る経路に付随するＡＮＤ節点又はＯＲ節点での該経路以外の分枝数を演算する演算ステップを具備することにある。【選択図】  図１
2007066125.tif 000002
【特許請求の範囲】
【請求項１】
始点から解まで、少なくとも１つ以上の解が望まれる選択肢を有するＯＲ接点と、全ての選択肢に足して解に至る必要があるＡＮＤ接点とが交互に現れる有向グラフについて始点から解までの経路を探索するグラフ探索アルゴリズムにおいて、
少なくとも始点から任意の接点に至る経路に付随するＡＮＤ接点又はＯＲ接点での該経路以外の分枝数を演算する演算ステップを具備することを特徴とするグラフ探索アルゴリズム。
【請求項２】
前記分枝数が、所定の閾値以下である全ての経路を生成する経路生成ステップと、
前記経路生成ステップにおいて生成された経路が解に至るか否かを確認する
判定ステップと、
前記判定ステップによって解に至らないと判定された場合に、前記所定の閾値の値を所定値大きく設定する閾値更新ステップとを具備することを特徴とする請求項記載のグラフ探索アルゴリズム。
【請求項３】
前記演算ステップは、前記始点から任意の接点に至る経路に付随するＯＲ接点での該経路以外の未解決分枝数をＯＲ分枝数として演算し、且つ前記始点から前記任意の接点に至る経路に付随するＡＮＤ接点での該経路以外の未解決分枝数をＡＮＤ分枝数として演算することを特徴とする請求項１又は２記載のグラフ探索アルゴリズム。
【請求項４】
前記請求項１から４のいずれか一つに記載されたグラフ探索アルゴリズムを用いたグラフ探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータによって実行されるＡＮＤ／ＯＲ木からなるグラフの探索アルゴリズム及びそれを用いたグラフ探索装置に関する。
【背景技術】
【０００２】
例えば、ＡＮＤ／ＯＲ木によって代表されるグラフ探索の一例として、例えば詰め将棋の解析が上げられる。このような最終的な評価が２つ（例えば、「詰み（ｔｒｕｅ）」と「不詰み（ｆａｌｓｅ）」）存在するような二人ゲームの探索は、人工知能の分野では、ＡＮＤ／ＯＲ木の探索として一般化される。ＡＮＤ／ＯＲ木には、ＡＮＤノード（ＡＮＤ接点）及びＯＲノード（ＯＲ接点）という２種類のノードが存在する。ＡＮＤ接点とは、詰将棋では、玉方手番の局面に相当し、その子ノードのすべてが詰んで初めて詰むようなノードのことで、ＯＲノードとは、詰将棋では攻め方手番の局面に相当し、その子ノードのどれかが詰めば詰むようなノードである。
【０００３】
非特許文献１は、各ノードに対して証明数と反証数とを設定する。証明数とは、そのノードの最終的な評価値を「ｔｒｕｅ」にするために、「ｔｒｕｅ」となることを示さなければならない先端ノードの個数の最小値であり、反証数とは、そのノードの最終的な評価値を「ｆａｌｓｅ」にするために、「ｆａｌｓｅ」となることを示さなければならない先端ノードの個数の最小値である。
【０００４】
具体的な証明数・反証数の計算法は、以下のように、再帰的行われる。
【０００５】
１．ノードｎが先端ノード
（ａ）最終的な評価が「ｔｒｕｅ」
ｎ．ｐｎ＝０
ｎ．ｄｎ＝∞
（ｂ）最終的な評価値が「ｆａｌｓｅ」
ｎ．ｐｎ＝∞
ｎ．ｄｎ＝０
（ｃ）最終的な評価値が不明
ｎ．ｐｎ＝１
ｎ．ｄｎ＝１
２．ノードｎが内部ノード
（ａ）ｎがＯＲノード
ｎ．ｐｎ＝子ノードのｐｎの最小
ｎ．ｄｎ＝子ノードのｄｎの和
（ｂ）ｎがＡＮＤノード
ｎ．ｐｎ＝子ノードのｐｎの和
ｎ．ｄｎ＝子ノードのｄｎの最小
【０００６】
以上のことにより、ＯＲノードでは、証明数の最小のノードを選択することが望まれ、ＡＮＤノードでは、反証数が最小のノードを選択することが望まれる。詰将棋の例を挙げると、証明数が大きくなるほど、詰まそうとする時の難易度が高くなるために、ＯＲノードでは、詰ませ易そうな手を選ぶ必要があるので、証明数が最小の手（ノード）を選ぶことが重要になってくる。反対に、ＡＮＤノードでは、より不詰になりやすそうな手を選ぶ必要があるので、反証数が最小の手（ノード）を選ぶことが重要になってくるものである。
【０００７】
また、特許文献１は、最適化問題を解決する最適化問題解決処理方法であって、決定論的な手法によって解の一部を発見する第１の過程と、前記第１の過程の実行後、前記第１の過程で発見された解を除外した解空間を対象として遺伝的アルゴリズムを適用し残りの解を発見する第２の過程とを有する方法を開示する。
【非特許文献１】アルゴリズム７５−２「ｄｆ−ｐｎアルゴリズムの詰将棋解答プログラムへの応用」２０００年１１月１０日
【特許文献１】特開平７−２１９９２０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献１に開示されるような構造は、一般的にＡＮＤ／ＯＲ木構造だけではなくＤＡＧ（Directed A cycled Graph）や閉路（Cycle）を有する有向グラフとして一般化される。一般的なＤＡＧを含むグラフ構造について探索を考えた場合、複数の経路より同一接点に至ることが可能となるため、証明数、反証数を用いた探索の場合、証明数、反証数が多重にカウントされてしまう。そのため、解に至るまでの探索量が少量であるにも関わらず後回しにされてしまうという不具合が生じる。現実的には、証明数、反証数の２重カウントを別途検出する仕組みを作り、補正を加える手法が知られているが、処理が複雑になるため、一般的な解決に至っていないのが現状である。
【０００９】
したがって、本発明は、ＡＮＤ／ＯＲ木構造の解析アルゴリズムにおいて、証明数、反証数を用いることによって生じる不具合を解決する新たな概念を取り入れたグラフ探索アルゴリズム及びグラフ探索装置を提供することにある。
【課題を解決するための手段】
【００１０】
このため、この発明に係るアルゴリズムは、始点から解まで、少なくとも１つ以上の解を含む選択肢を有するＯＲ接点と、全ての選択肢に対して解に至るＡＮＤ接点とが交互に現れるグラフについて始点から解までの経路を探索するグラフ探索アルゴリズムにおいて、少なくとも始点から任意の接点に至る経路に付随するＡＮＤ接点又はＯＲ接点での該経路以外の分枝数を演算する演算ステップを具備することにある。
【００１１】
また、前記グラフ探索アルゴリズムは、前記分枝数が、所定の閾値以下である全ての経路を生成する経路生成ステップと、前記経路生成ステップにおいて生成された経路が解に至るか否かを確認する判定ステップと、前記判定ステップによって解に至らないと判定された場合に、前記所定の閾値の値を所定値大きく設定する閾値更新ステップとを具備することが望ましい。
【００１２】
さらに、前記演算ステップは、前記始点から任意の接点に至る経路に付随するＯＲ接点での該経路以外の未解決分枝数をＯＲ分枝数として演算し、且つ前記始点から前記任意の接点に至る経路に付随するＡＮＤ接点での該経路以外の未解決分枝数をＡＮＤ分枝数として演算することが望ましい。
【００１３】
さらにまた、上述したグラフ探索アルゴリズムは、所定のグラフ探索装置に用いられることが望ましい。
【００１４】
さらに具体的には、この発明に係るアルゴリズムは、始点から解まで、少なくとも１つ以上の解を含む選択肢を有するＯＲ接点と、全ての選択肢に対して解に至るＡＮＤ接点とが交互に現れるグラフについて始点から解までの経路を探索するグラフ探索アルゴリズムにおいて、少なくとも前記始点から任意の接点に至る経路に付随するＯＲ接点での該経路以外の未解決分枝数をＯＲ分枝数として演算するステップか、前記始点から前記任意の接点に至る経路に付随するＡＮＤ接点での該経路以外の未解決分枝数をＡＮＤ分枝数として演算する演算ステップの一方もしくは両方と、前記ＯＲ分枝数及び前記ＡＮＤ分枝数の一方もしくは両方が所定の閾値以下である全ての経路を生成する経路生成ステップと、前記経路生成ステップにおいて生成された経路が解に至るか否かを確認する判定ステップと、該判定ステップによって解に至らないと判定された場合に、前記所定の閾値の値を再度大きく設定する閾値更新ステップとを具備することにある。
【発明の効果】
【００１５】
したがって、本発明によれば、ＯＲ分枝数及びＡＮＤ分枝数の一方又は両方を経路選択の判定基準とすることから、ＡＮＤ／ＯＲ木構造のみならず、ＤＡＧを多数含むグラフ構造を有する場合においても、少ない探索コストで解を見いだすことができるという効果を奏するものである。
【発明を実施するための最良の形態】
【００１６】
以下、この発明の実施例について説明する。ここで、ＯＲ分枝数ｏｂｎ及びＡＮＤ分枝数ａｂｎは以下のように定義される。
【００１７】
（末端ノード）
不明：ｏｂｎ＝１，ａｂｎ＝１
ｔｒｕｅ：ａｂｎ＝０，ｏｂｎ＝∞
ｆａｌｓｅ：ａｂｎ＝∞，ｏｂｎ＝０
（中間ノード）
ＯＲノード：ａｂｎ＝ｍｉｎ（子のａｂｎ）
ｏｂｎ＝（選択ｏｂｎ）＋（非選択の未解決数）
ＡＮＤノード：ａｂｎ＝（選択ａｂｎ）＋（非選択の未解決数）
ｏｂｎ＝ｍｉｎ（子のｏｂｎ）
【００１８】
尚、本発明における分枝数の概念は、図２に示すものである。この図２において、１〜５は探索ノード、Ａ〜Ｈは探索ノード１〜５に付随する選択肢である。したがって、ＡはＯＲノード１における未解決分枝であり、ＢはＡＮＤノード２における未解決分枝である。同様に、ＣはＯＲノード３における未解決分枝、ＤはＡＮＤノード４における解決済み分枝、ＥはＡＮＤノード４における未解決分枝、Ｆ，ＧはＯＲノード５の未解決分枝、ＨはＯＲノード５の解決済み分枝である。したがって、ＯＲノード５におけるＯＲ分枝数は、Ａ，Ｃ，Ｆ，Ｇの４つであり、ＡＮＤ分枝数はＢ，Ｅの２つである。また、解決済みノードＨ，Ｄには、閾値外となるように、大きい数が付加される。したがって、ａｂｎ及びｏｂｎが最も小さいものが順次選択されることになるものである。尚、図２で示す例において、それぞれの探索点での分枝数は、以下のようになる。
【００１９】
【表１】
2007066125.tif 000003
【実施例】
【００２０】
この実施例では、ルート局面において、十分におおきな値ＲＢＮをＯＲ分枝数及びＡＮＤ分枝数の閾値ＯＢＮ，ＡＢＮとして設定する。このルート局面を探索起点として以下の定義及び規則にしたがって、図１に示すフローチャートにより、各グラフ接点の探索を繰り返す。尚、本発明による反復深化条件は、下記のものである。
【００２１】
（定義）
ｎ：探索接点
ｏｂｎ（ｎ）：ＯＲ分枝数
ａｂｎ（ｎ）：ＡＮＤ分枝数
ｃ１，．．．，ｃｋ，ｃｎ，．．．，ｃｕ：子ノード
ＯＲノードの場合：
ａｂｎ（ｃ１）≦．．．≦ａｂｎ（ｃｋ），ａｂｎ（ｃｎ）＝，．．．，＝ａｂｎ（ｃｕ）＝∞
ＡＮＤノードの場合：
ｏｂｎ（ｃ１）≦．．．≦ｏｂｎ（ｃｋ），ｏｂｎ（ｃｎ）＝，．．．，＝ｏｂｎ（ｃｕ）＝∞
ＯＢＮ：ＯＲ分枝数閾値
ＡＢＮ：ＡＮＤ分枝数閾値
（着手選択）  常にｃ１
（閾値の更新）
ＯＲ接点：ＡＢＮ’＝ｍｉｎ（ａｂｎ（ｃ２）＋１，ＡＢＮ）
ＯＢＮ’＝ＯＢＮ−ｋ＋１
ＡＮＤ接点：ＡＢＮ’＝ＡＢＮ−ｋ＋１
ＯＢＮ’＝ｍｉｎ（ｏｂｎ（ｃ２）＋１，ＯＢＮ）
（戻り条件）
ＯＢＮ≦ｏｂｎ（ｎ）  ｏｒ  ＡＢＮ≦ａｂｎ（ｎ）
（反復深化条件）
ＯＢＮ＞ｏｂｎ（ｎ）  ａｎｄ  ＡＢＮ＞ａｂｎ（ｎ）
【００２２】
ここで、例えば図３を用いて、図１に示されるフローチャートを説明すると、まずステップ１００において探索ノード００と閾値ＯＢＮ、ＡＢＮを与えられる。ここでは００が未探索ノードの場合、ｏｂｎ（００）＝１、ａｂｎ（００）＝１を与えておく。次にステップ１１０において、ノード１１〜１５を生成し、それぞれに初期値として、ｏｂｎ（１１）＝１、ａｂｎ（１１）＝１、・・・、ｏｂｎ（１５）＝１、ａｂｎ（１５）＝１が与えられる。次にステップ１２０において、最適ノードを選択する。この場合、前記ノード００はすべてａｂｎ＝１の子ノードをもつＯＲノードであるので選択は任意となる。ここでは、ノード１１が選択される。次のステップ１３０において、ノード１１に与える閾値ＡＢＮ’、ＯＢＮ’が決定されることとなり、上述した定義に従って、ＡＢＮ’＝２、ＯＢＮ’＝ＲＢＮ−４が与えられる形となる。次にステップ１４０において、選択したノード１１に局面をすすめ、ステップ１５０において、前記閾値ＡＢＮ’，ＯＢＮ’をもって本アルゴリズムの再帰呼び出しを行う。ここで戻り値として前記ＡＢＮ’あるいはＯＢＮ’のいずれかの閾値以上の分枝数ａｂｎ（１１）、ｏｂｎ（１１）をえる。次にステップ１６０において、ノードを００に戻し、前記ａｂｎ（１１）、ｏｂｎ（１１）の結果をふまえ、ノード００の分枝数ｏｂｎ（００）、ａｂｎ（００）を算出する。次にステップ１８０において、前記分枝数ｏｂｎ（００）、ａｂｎ（００）と閾値ＯＢＮ，ＡＢＮとの比較を行い、それぞれが閾値未満であればステップ１２０に戻って探索を続け、いずれかが閾値以上となった場合にステップ１９０に移り、探索を終了する。ここで探索ノードがルートノードの場合、閾値に十分大きな値があたえられていれば、原則ｔｒｕｅ：ａｂｎ＝０，ｏｂｎ＝∞、ｆａｌｓｅ：ａｂｎ＝∞，ｏｂｎ＝０のいずれかの結論をもって探索を終了することとなる。
【００２３】
次に、図３から図７を用いて本アルゴリズムにより解を導く過程を、段階を追って説明する。まず図３において、ルートのＯＲノード００より子ノードとしてノード１１〜ノード１５を生成する。これらのノード１１〜１５は未解決であるのですべての子ノードに対し、ｏｂｎ＝１、ａｂｎ＝１が付与され、最適子ノードとして仮にノード１１が選択され、閾値としてＯＢＮ’＝ＲＢＮ−４、ＡＢＮ’＝２が与えられ、ノード１１に処理が移る。次に図４においてノード１１の下にＯＲノードが生成され、該ＯＲノードがｆａｌｓｅであったとする。するとノード１１にｏｂｎ＝０、ａｂｎ＝∞が与えられる。次に再度ノード００に処理がもどり、ｏｂｎ（００）＝４、ａｂｎ（００）＝１と算出され、図５に示すようにノード１１〜１５より最適ノードの再選択が行われる。ここではノード１１以外のａｂｎはすべて１であるのでここでは仮にノード１２を選択するものとする。また選択ノード１２に与えられる閾値としてはノード１１が解決済みであることよりＡＢＮ’＝２、ＯＢＮ’＝ＲＢＮ−３となる。
【００２４】
図６は、このＡＮＤノード１２からの探索において、ＯＲノード２１、ＡＮＤノード３１、ＯＲノード４１は、それぞれの局面において選択肢が一つである例を示している。この場合、ＯＲノード００の閾値はそのまま子ノードに承継される。
【００２５】
次に、図７に示すように、ＯＲノード４１での探索において、２つのＡＮＤノード５１，５２が存在し、またＡＮＤノード５１には一つのＯＲノード６１が、またＡＮＤノード５２には２つのＯＲノード６２，６３が存在し、さらにＯＲノード６１には３つのＡＮＤノード７１，７２，７３が存在し、その一つが「ｔｒｕｅ」であることが探索され、作業が完遂するものである。
【産業上の利用可能性】
【００２６】
この発明は、人工知能を構成する種々のアルゴリズムの１つとしてコンピュータに搭載することによって、ＡＮＤ／ＯＲ木構造の解析を円滑に且つ短時間に処理して解に到達することができるようになるので、人工知能の能力を高めると共に、より人間に近い発想を構築することが可能である。
【図面の簡単な説明】
【００２７】
【図１】本発明に係るグラフ探索アルゴリズムのフローチャート図である。
【図２】本発明のおけるＡＮＤ分枝数、ＯＲ分枝数の概念を示す説明図である。
【図３】本発明のアルゴリズムによる解図の例を示した説明図である。
【図４】本発明のアルゴリズムによる解図の例を示した説明図である。
【図５】本発明のアルゴリズムによる解図の例を示した説明図である。
【図６】本発明のアルゴリズムによる解図の例を示した説明図である。
【図７】本発明のアルゴリズムによる解図の例を示した説明図である。
【符号の説明】
【００２８】
１，２，３，４，５  探索接点
Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ  選択肢
００，２１，４１，６１，６２，６３  ＯＲノード
１１，１２，１３，１４，１５，３１，５１，５２，７１，７２，７３  ＡＮＤノード
【図１】
2007066125.tif 000004
【図２】
2007066125.tif 000005
【図３】
2007066125.tif 000006
【図４】
2007066125.tif 000007
【図５】
2007066125.tif 000008
【図６】
2007066125.tif 000009
【図７】
2007066125.tif 000010
【手続補正書】
【提出日】平成18年6月30日(2006.6.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
始点から解まで、少なくとも１つ以上の解に至ることが望まれる選択肢を有するＯＲ節点と、全ての選択肢に対して解に至る必要があるＡＮＤ節点とが交互に現れる有向グラフを探索するグラフ探索アルゴリズムにおいて、
少なくとも始点から任意の接点に至る経路に付随するＡＮＤ節点又はＯＲ節点での該経路以外の分枝数を演算する演算ステップを具備することを特徴とするグラフ探索アルゴリズム。
【請求項２】
前記分枝数が、所定の閾値以下である全ての経路を生成する経路生成ステップと、
前記経路生成ステップにおいて生成された経路が解に至るか否かを確認する判定ステップと、
前記判定ステップによって解に至らないと判定された場合に、前記所定の閾値の値を所定値より大きく設定する閾値更新ステップとを具備することを特徴とする請求項記載のグラフ探索アルゴリズム。
【請求項３】
前記演算ステップは、前記始点から任意の節点に至る経路に付随するＯＲ節点での該経路以外の未解決分枝数をＯＲ分枝数として演算し、且つ前記始点から前記任意の節点に至る経路に付随するＡＮＤ節点での該経路以外の未解決分枝数をＡＮＤ分枝数として演算することを特徴とする請求項１又は２記載のグラフ探索アルゴリズム。
【請求項４】
前記請求項１から３のいずれか一つに記載されたグラフ探索アルゴリズムを用いたグラフ探索装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータによって実行されるＡＮＤ／ＯＲグラフの探索アルゴリズム及びそれを用いたグラフ探索装置に関する。
【背景技術】
【０００２】
これまで、詰将棋のように最終的な評価が２つ（「詰み（ｔｒｕｅ）」と「不詰み（ｆａｌｓｅ）」あるいは「勝ち」と「負け」など）存在するようなゲーム又はパズルの探索は、人工知能の分野では、ＡＮＤ／ＯＲグラフの探索として一般化されていた。ＡＮＤ／ＯＲグラフには、ＡＮＤ節点及びＯＲ節点という２種類の節点が存在する。ＡＮＤ節点とは、詰将棋では、玉方手番の局面に相当し、その節点での分枝すべてが詰みとして収束することが要求される節点で、ＯＲ節点とは、詰将棋では攻め方手番の局面に相当し、その節点での分枝のいずれかが詰むことを期待される節点である。一般的に詰将棋を解くということは問題の局面を根節点とし、所望の末端節点である詰み局面を「解」とした場合、ＯＲ節点では少なくともひとつ以上の分枝を選択され、ＡＮＤ節点ではすべての分枝が選択され、かつすべての末端節点が詰み局面で構成されるＡＮＤ/ＯＲグラフ（解グラフ）を特定し、確認する行為である。一般的にこのようなＡＮＤ/ＯＲグラフに含まれる解グラフを少ない探索量で求めることを考えた場合、各ＯＲ節点において最終的に詰みとして収束する分枝を、またＡＮＤ節点においては最終的に不詰みとして収束する節点をいかに優先的に探索するかが鍵となる。近年各節点における分枝選択の優先度の指標として証明数、反証数の概念が導入された。
【０００３】
非特許文献１は、各節点に対して証明数と反証数とが設定されている。証明数とは、その節点の最終的な評価値を「ｔｒｕｅ」にするために、「ｔｒｕｅ」となることを示さなければならない先端節点の個数の最小値であり、反証数とは、その節点の最終的な評価値を「ｆａｌｓｅ」にするために、「ｆａｌｓｅ」となることを示さなければならない先端節点の個数の最小値である。
【０００４】
具体的な証明数・反証数の計算法は、以下のように、再帰的行われる。
【０００５】
１．節点ｎが先端節点
（ａ）最終的な評価が「ｔｒｕｅ」
ｎ．ｐｎ＝０
ｎ．ｄｎ＝∞
（ｂ）最終的な評価値が「ｆａｌｓｅ」
ｎ．ｐｎ＝∞
ｎ．ｄｎ＝０
（ｃ）最終的な評価値が不明
ｎ．ｐｎ＝１
ｎ．ｄｎ＝１
２．節点ｎが内部節点
（ａ）ｎがＯＲ節点
ｎ．ｐｎ＝子節点のｐｎの最小
ｎ．ｄｎ＝子節点のｄｎの和
（ｂ）ｎがＡＮＤ節点
ｎ．ｐｎ＝子節点のｐｎの和
ｎ．ｄｎ＝子節点のｄｎの最小
【０００６】
以上のことにより、ＯＲ節点では、証明数の最小の節点を選択することが望まれ、ＡＮＤ節点では、反証数が最小の節点を選択することが望まれる。詰将棋の例を挙げると、証明数が大きくなるほど、詰まそうとする時の難易度が高くなるために、ＯＲ節点では、詰ませ易そうな手を選ぶ必要があるので、証明数が最小の手（節点）を選ぶことが重要になってくる。反対に、ＡＮＤ節点では、より不詰になりやすそうな手を選ぶ必要があるので、反証数が最小の手（節点）を選ぶことが重要になってくるものである。
【０００７】
また、特許文献１は、最適化問題を解決する最適化問題解決処理方法であって、決定論的な手法によって解の一部を発見する第１の過程と、前記第１の過程の実行後、前記第１の過程で発見された解を除外した解空間を対象として遺伝的アルゴリズムを適用し残りの解を発見する第２の過程とを有する方法を開示する。
【非特許文献１】アルゴリズム７５−２「ｄｆ−ｐｎアルゴリズムの詰将棋解答プログラムへの応用」２０００年１１月１０日
【特許文献１】特開平７−２１９９２０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献１に開示されるような詰将棋の場合は、ＤＡＧ（Directed A cycled Graph）や閉路（Cycle）を有するＡＮＤ／ＯＲ有向グラフとして一般化される。ＤＡＧを含むグラフ構造について探索を考えた場合、複数の経路より同一節点に至ることが可能となるため、証明数、反証数が多重にカウントされてしまう。そのため、解に至るまでの探索量が少量であるにも関わらず後回しにされてしまうという不具合が生じる。現実的には、証明数、反証数の２重カウントを別途検出する仕組みを作り、補正を加える手法が知られているが、処理が複雑になるため、一般的な解決に至っていないのが現状である。
【０００９】
したがって、本発明は、ＡＮＤ／ＯＲグラフ構造の解析アルゴリズムにおいて、証明数、反証数を用いることによって生じる不具合を解決する新たな概念を取り入れたグラフ探索アルゴリズム及びグラフ探索装置を提供することにある。
【課題を解決するための手段】
【００１０】
このため、本発明は、少なくとも１つ以上の解に至る分枝を含むＯＲ節点と、全てが解に至る分枝であるＡＮＤ節点とが交互に現れるグラフについて始点から解までの経路を探索するグラフ探索アルゴリズムにおいて、少なくとも始点から任意の節点に至る経路に付随するＡＮＤ節点又はＯＲ節点での該経路以外の分枝数を演算する演算ステップを具備することにある。
【００１１】
また、前記グラフ探索アルゴリズムは、前記分枝数が、所定の閾値以下である全ての経路を探索する経路生成ステップと、前記経路生成ステップにおいて選択された経路が解に至るか否かを確認する判定ステップと、前記判定ステップによって解に至らないと判定された場合に、前記所定の閾値の値を更に大きく設定する閾値更新ステップとを具備することが望ましい。
【００１２】
さらに、前記演算ステップは、前記始点から任意の節点に至る経路に付随するＯＲ節点での該経路以外の未解決分枝数をＯＲ分枝数として演算し、且つ前記始点から前記任意の節点に至る経路に付随するＡＮＤ節点での該経路以外の未解決分枝数をＡＮＤ分枝数として演算することが望ましい。
【００１３】
さらにまた、上述したグラフ探索アルゴリズムは、所定のグラフ探索装置に用いられることが望ましい。
【００１４】
さらに具体的には、この発明に係るアルゴリズムは、始点から解まで、少なくとも１つ以上の解に至る分枝を含むＯＲ節点と、全てが解に至る分枝であるＡＮＤ節点とが交互に現れるグラフについて、始点から解までの経路を探索するグラフ探索アルゴリズムにおいて、少なくとも前記始点から任意の節点に至る経路に付随するＯＲ節点での該経路以外の未解決分枝数をＯＲ分枝数として演算するステップか、前記始点から前記任意の節点に至る経路に付随するＡＮＤ節点での該経路以外の未解決分枝数をＡＮＤ分枝数として演算する演算ステップの一方もしくは両方と、前記ＯＲ分枝数及び前記ＡＮＤ分枝数の一方もしくは両方が所定の閾値以下である全ての経路を選択する経路生成ステップと、前記経路生成ステップにおいて選択された経路が解に至るか否かを確認する判定ステップと、該判定ステップによって解に至らないと判定された場合に、前記所定の閾値の値を再度大きく設定する閾値更新ステップとを具備することにある。
【発明の効果】
【００１５】
したがって、本発明によれば、ＯＲ分枝数及びＡＮＤ分枝数の一方又は両方を経路選択の判定基準とすることから、ＡＮＤ／ＯＲグラフ構造のみならず、ＤＡＧを多数含むグラフ構造を有する場合においても、少ない探索コストで解を見いだすことができるという効果を奏するものである。
【発明を実施するための最良の形態】
【００１６】
以下、この発明の実施例について説明する。ここで、ＯＲ分枝数ｏｂｎ及びＡＮＤ分枝数ａｂｎは以下のように定義される。
【００１７】
（末端節点）
不明：ｏｂｎ＝１，ａｂｎ＝１
ｔｒｕｅ：ａｂｎ＝０，ｏｂｎ＝∞
ｆａｌｓｅ：ａｂｎ＝∞，ｏｂｎ＝０
（中間節点）
ＯＲ節点：ａｂｎ＝ｍｉｎ（子のａｂｎ）
ｏｂｎ＝（選択ｏｂｎ）＋（非選択の未解決数）
ＡＮＤ節点：ａｂｎ＝（選択ａｂｎ）＋（非選択の未解決数）
ｏｂｎ＝ｍｉｎ（子のｏｂｎ）
【００１８】
尚、本発明における分枝数の概念は、図２に示すものである。この図２において、１〜５は探索節点、Ａ〜Ｈは探索節点１〜５に付随する選択肢である。したがって、ＡはＯＲ節点１における未解決分枝であり、ＢはＡＮＤ節点２における未解決分枝である。同様に、ＣはＯＲ節点３における未解決分枝、ＤはＡＮＤ節点４における解決済み分枝、ＥはＡＮＤ節点４における未解決分枝、Ｆ，ＧはＯＲ節点５の未解決分枝、ＨはＯＲ節点５の解決済み分枝である。したがって、ＯＲ節点５におけるＯＲ分枝数は、Ａ，Ｃ，Ｆ，Ｇの４つであり、ＡＮＤ分枝数はＢ，Ｅの２つである。また、解決済み節点Ｈ，Ｄには、閾値外となるように、大きい数が付加される。したがって、ａｂｎ及びｏｂｎが最も小さいものが順次選択されることになるものである。尚、図２で示す例において、それぞれの探索点での分枝数は、以下のようになる。
【００１９】
【表１】
2007066125.tif 000011
【実施例】
【００２０】
この実施例では、ルート局面において、十分におおきな値ＲＢＮをＯＲ分枝数及びＡＮＤ分枝数の閾値ＯＢＮ，ＡＢＮとして設定する。このルート局面を探索起点として以下の定義及び規則にしたがって、図１に示すフローチャートにより、各グラフ節点の探索を繰り返す。尚、本発明による反復深化条件は、下記のものである。
【００２１】
（定義）
ｎ：探索節点
ｏｂｎ（ｎ）：ＯＲ分枝数
ａｂｎ（ｎ）：ＡＮＤ分枝数
ｃ１，．．．，ｃｋ，ｃｎ，．．．，ｃｕ：子ノード
ＯＲ節点の場合：
ａｂｎ（ｃ１）≦．．．≦ａｂｎ（ｃｋ），ａｂｎ（ｃｎ）＝，．．．，＝ａｂｎ（ｃｕ）＝∞
ＡＮＤ節点の場合：
ｏｂｎ（ｃ１）≦．．．≦ｏｂｎ（ｃｋ），ｏｂｎ（ｃｎ）＝，．．．，＝ｏｂｎ（ｃｕ）＝∞
ＯＢＮ：ＯＲ分枝数閾値
ＡＢＮ：ＡＮＤ分枝数閾値
（着手選択）  常にｃ１
（閾値の更新）
ＯＲ節点：ＡＢＮ’＝ｍｉｎ（ａｂｎ（ｃ２）＋１，ＡＢＮ）
ＯＢＮ’＝ＯＢＮ−ｋ＋１
ＡＮＤ節点：ＡＢＮ’＝ＡＢＮ−ｋ＋１
ＯＢＮ’＝ｍｉｎ（ｏｂｎ（ｃ２）＋１，ＯＢＮ）
（戻り条件）
ＯＢＮ≦ｏｂｎ（ｎ）  ｏｒ  ＡＢＮ≦ａｂｎ（ｎ）
（反復深化条件）
ＯＢＮ＞ｏｂｎ（ｎ）  ａｎｄ  ＡＢＮ＞ａｂｎ（ｎ）
【００２２】
ここで、例えば図３を用いて、図１に示されるフローチャートを説明すると、まずステップ１００において探索節点００と閾値ＯＢＮ、ＡＢＮを与えられる。ここでは００が未探索節点の場合、ｏｂｎ（００）＝１、ａｂｎ（００）＝１を与えておく。次にステップ１１０において、節点１１〜１５を生成し、それぞれに初期値として、ｏｂｎ（１１）＝１、ａｂｎ（１１）＝１、・・・、ｏｂｎ（１５）＝１、ａｂｎ（１５）＝１が与えられる。次にステップ１２０において、最適節点を選択する。この場合、前記節点００はすべてａｂｎ＝１の子節点をもつＯＲ節点であるので選択は任意となる。ここでは、節点１１が選択される。次のステップ１３０において、節点１１に与える閾値ＡＢＮ’、ＯＢＮ’が決定されることとなり、上述した定義に従って、ＡＢＮ’＝２、ＯＢＮ’＝ＲＢＮ−４が与えられる形となる。次にステップ１４０において、選択した節点１１に局面をすすめ、ステップ１５０において、前記閾値ＡＢＮ’，ＯＢＮ’をもって本アルゴリズムの再帰呼び出しを行う。ここで戻り値として前記ＡＢＮ’あるいはＯＢＮ’のいずれかの閾値以上の分枝数ａｂｎ（１１）、ｏｂｎ（１１）をえる。次にステップ１６０において、節点を００に戻し、前記ａｂｎ（１１）、ｏｂｎ（１１）の結果をふまえ、節点００の分枝数ｏｂｎ（００）、ａｂｎ（００）を算出する。次にステップ１８０において、前記分枝数ｏｂｎ（００）、ａｂｎ（００）と閾値ＯＢＮ，ＡＢＮとの比較を行い、それぞれが閾値未満であればステップ１２０に戻って探索を続け、いずれかが閾値以上となった場合にステップ１９０に移り、探索を終了する。ここで探索節点がルート節点の場合、閾値に十分大きな値があたえられていれば、原則ｔｒｕｅ：ａｂｎ＝０，ｏｂｎ＝∞、ｆａｌｓｅ：ａｂｎ＝∞，ｏｂｎ＝０のいずれかの結論をもって探索を終了することとなる。
【００２３】
次に、図３から図７を用いて本アルゴリズムにより解を導く過程を、段階を追って説明する。まず図３において、ルートのＯＲ節点００より子節点として節点１１〜節点１５を生成する。これらの節点１１〜１５は未解決であるのですべての子節点に対し、ｏｂｎ＝１、ａｂｎ＝１が付与され、最適子節点として仮に節点１１が選択され、閾値としてＯＢＮ’＝ＲＢＮ−４、ＡＢＮ’＝２が与えられ、節点１１に処理が移る。次に図４において節点１１の下にＯＲ節点が生成され、該ＯＲ節点がｆａｌｓｅであったとする。すると節点１１にｏｂｎ＝０、ａｂｎ＝∞が与えられる。次に再度ノード００に処理がもどり、ｏｂｎ（００）＝４、ａｂｎ（００）＝１と算出され、図５に示すように節点１１〜１５より最適ノードの再選択が行われる。ここでは節点１１以外のａｂｎはすべて１であるのでここでは仮に節点１２を選択するものとする。また選択節点１２に与えられる閾値としては節点１１が解決済みであることよりＡＢＮ’＝２、ＯＢＮ’＝ＲＢＮ−３となる。
【００２４】
図６は、このＡＮＤ節点１２からの探索において、ＯＲ節点２１、ＡＮＤ節点３１、ＯＲ節点４１は、それぞれの局面において選択肢が一つである例を示している。この場合、ＯＲ節点００の閾値はそのまま子節点に承継される。
【００２５】
次に、図７に示すように、ＯＲ節点４１での探索において、２つのＡＮＤ節点５１，５２が存在し、またＡＮＤ節点５１には一つのＯＲ節点６１が、またＡＮＤ節点５２には２つのＯＲ節点６２，６３が存在し、さらにＯＲ節点６１には３つのＡＮＤ節点７１，７２，７３が存在し、その一つが「ｔｒｕｅ」であることが探索され、作業が完遂するものである。
【産業上の利用可能性】
【００２６】
この発明は、人工知能を構成する種々のアルゴリズムの１つとしてコンピュータに搭載することによって、ＡＮＤ／ＯＲグラフ構造の解析を円滑に且つ短時間に処理して解に到達することができるようになるので、人工知能の能力を高めると共に、より人間に近い発想を構築することが可能である。
【図面の簡単な説明】
【００２７】
【図１】本発明に係るグラフ探索アルゴリズムのフローチャート図である。
【図２】本発明のおけるＡＮＤ分枝数、ＯＲ分枝数の概念を示す説明図である。
【図３】本発明のアルゴリズムによる解図の例を示した説明図である。
【図４】本発明のアルゴリズムによる解図の例を示した説明図である。
【図５】本発明のアルゴリズムによる解図の例を示した説明図である。
【図６】本発明のアルゴリズムによる解図の例を示した説明図である。
【図７】本発明のアルゴリズムによる解図の例を示した説明図である。
【符号の説明】
【００２８】
１，２，３，４，５  探索節点
Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ  選択肢
００，２１，４１，６１，６２，６３  ＯＲ節点
１１，１２，１３，１４，１５，３１，５１，５２，７１，７２，７３  ＡＮＤ節点
【手続補正書】
【提出日】平成18年7月6日(2006.7.6)
【手続補正１】
【補正対象書類名】手続補正書
【補正対象項目名】手続補正１
【補正方法】変更
【補正の内容】
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
始点から解まで、少なくとも１つ以上の解に至ることが望まれる選択肢を有するＯＲ節点と、全ての選択肢に対して解に至る必要があるＡＮＤ節点とが交互に現れる有向グラフを探索するグラフ探索アルゴリズムにおいて、
少なくとも始点から任意の節点に至る経路に付随するＡＮＤ節点又はＯＲ節点での該経路以外の分枝数を演算する演算ステップを具備することを特徴とするグラフ探索アルゴリズム。
【請求項２】
前記分枝数が、所定の閾値以下である全ての経路を生成する経路生成ステップと、
前記経路生成ステップにおいて生成された経路が解に至るか否かを確認する判定ステップと、
前記判定ステップによって解に至らないと判定された場合に、前記所定の閾値の値を所定値より大きく設定する閾値更新ステップとを具備することを特徴とする請求項記載のグラフ探索アルゴリズム。
【請求項３】
前記演算ステップは、前記始点から任意の節点に至る経路に付随するＯＲ節点での該経路以外の未解決分枝数をＯＲ分枝数として演算し、且つ前記始点から前記任意の節点に至る経路に付随するＡＮＤ節点での該経路以外の未解決分枝数をＡＮＤ分枝数として演算することを特徴とする請求項１又は２記載のグラフ探索アルゴリズム。
【請求項４】
前記請求項１から３のいずれか一つに記載されたグラフ探索アルゴリズムを用いたグラフ探索装置。