df-pn探索おさらい
df-pnが難しいという声がちらほら見聞されるが、ポイントを正しく押さえればこれはさほど難しくはない。
準備
まず「詰み」(=必至)を自明なものとそうでないものに分けよう。
- 自明な詰み
- そのノードの局面を見るだけで判断がつき、子ノードを見る必要がない形の詰み。
これは通常のゲームのルールの下では勝負がつくことと同義だ。例えば、将棋なら片方(敗者)の玉が取られた(事後の)局面、五目並べなら片方(勝者)の石が5個(以上)並んだ(同じく事後の)局面等。
敗北した側にもはや合法手は残されていないから、そうした局面のノードはそもそも子ノードを持たない(葉ノードである)。子ノードを持つ自明な詰みとしては、局面のハッシュ辞書等にすでに詰み登録がなされているケース等がある。
df-pn探索のねらい
df-pn探索の第一目的は実は次の仮説の検証である(後述するように、必ずしも勝負に勝つことではない)。
- pの手番であるノードnにおいてpによる-pの詰みが成立している
この仮説の「証明」は、ノードnを根とする部分ゲーム木の全ての葉ノードについて、pによる-pの自明な詰みが成立することを示すことで可能だ。
一方「反証」は、反例を1つ挙げることでなされる。すなわち、ノードnを根とする部分ゲーム木の中に、-pによるpの自明な詰み(攻守が反転していることに注意)が存在することをただ1例挙げればいい。
さて、「証明」のための葉ノードの列挙だが、それはnが自明な詰みである場合を除き、ノード数の爆発により現実的には不可能だと思われるかもしれない。しかしノードnで真に詰みが成立するなら、中間ノード総数はともかく、葉ノードの個数は
- 「たかが知れている」
はずなのだ。このことは、将棋で言うなら、詰まされる側の玉が盤上を際限無くは逃げられない(高々数百手で取られる)上に、攻方がそれを取れるマスがさらに限られることから想像がつく。一方、葉ノードを見もせずにそれを自明な詰みか否か言うことは(そうせずに済む数学的定理を見つけたのでもない限り)不可能だから、一般に、詰みを証明するにはやはり全ての葉ノードを列挙して、自明な詰みであることを確かめねばならない。問題はその全数列挙をいかに効率よくやるかだ。
(枝のカットにより到達しない葉ノードが発生しても完全探索になる一般のαβ探索とは趣が異なる。)
証明数と反証数
定義は下記のとおり。
- 証明数
- そのノードが攻方による詰みであることを証明するために、攻方による自明な詰みであることを示す必要がある
葉ノード子ノード以下のノード(子孫)の最小個数- 反証数
- そのノードが攻方による詰みでないことを証明するために、受方による自明な詰みであることを示す必要がある
葉ノード子ノード以下のノードの最小個数
で、攻方pによる受方-pの自明な詰みが生じたノード(必然的に-pの手番)では証明数=0、反証数=∞とする。これは詰みの証明にもはや子ノード以下を見る必要がないことと、反証が不可能なことを表す。
一方、受方-pによる攻方pの自明な詰みが生じたノード(必然的にpの手版)では証明数=∞、反証数=0とする。これは証明が不可能(反証された)ことと、反証にもはや子ノード以下を見る必要がないことを表す。
また、予定した探索深度に達してなお葉ノードに達しなかった場合は、少なくともさらに先のノードを1個以上見なければ証明も反証もできないから、証明数=反証数=1とする(以下不明ノードという)。
df-pn探索の原理
さて手番をよく意識しよう。次のことは明らかだ。
- pの手番のノードの反証数は、さらに1つ先のpの手番のノード(=孫ノード)の反証数の合計である。
- -pの手版のノードの証明数は、さらに1つ先の-pの手版のノード(=孫ノード)の証明数の合計である。
一方、葉ノードまでの最短の手筋を効率よく求めるには、攻方は詰みを証明するノード数が最小となる手を選び、受方は攻方に協力して、詰みを反証するノード数が最小となる手を選ぶのがいい。
詰みを証明するノード数が最小となる手はただちには知りようがないが、証明数最小のノードを選ぶことで推定できると仮定する。同様に、
詰みを反証するノード数が最小となる手はただちには知りようがないが、反証数最小のノードを選ぶことで推定できると仮定する。
総合すると、例の再帰計算規則が導かれる。
- 攻方pの手版のノードにおいて: 証明数=min{子ノードの証明数}, 反証数=Σ{子ノードの反証数}
- 受方-pの手版のノードにおいて: 証明数=Σ{子ノードの証明数}, 反証数=min{子ノードの反証数}
さて天下りに与えた証明数、反証数だが、証明数と反証数それぞれの上限でカットしても、全ての葉ノードと不明ノードが1回以上参照されるという顕著な性質がある(上記再帰計算規則より示せる)。これで、詰み証明または反証に十分な葉ノードの全数列挙を、枝をカットしつつ効率的に実現できる。
この程度の話ならちょっと考えればまともに論文を読まずとも(マテ
df-pn探索によって求めた手筋は強いか？
ノードnが真に攻方による詰みであることが証明された場合、df-pnが示す通りに指して負けるはずはない。よってその場合の強さに問題はない。
一方、証明が成らなかった場合ははっきり言って弱いはず。上記の通り、df-pnで得られる手筋は受方の協力の下に得られるようなものだからだ(探索の目的が違う)。
例えば、ただの一手で受方の必勝ノードに転がり込むような危険なノードを通る手筋が生成されかねない。
トップレベルの思考ルーチンの実態はよく知らんが、df-pnで詰みが証明されなかった場合は明らかに別手段で「勝負強い」最善手を捜さねばならない。
子ノードの反証数＝親ノードの証明数とみなす考え方は微妙に間違い
T/O
多分探索効率の低下という形で影響が出るはず。
