探索木の再帰性のひみつ
今日わ絶好の探索日和ので局面を評価する手段について述べるのに適当な気のする、
ただ本当にそうしたときに局面の評価手段を「評価関数」という言葉で代表すると「局面を評価因子に分解して、ほにゃららして、足し合わせる」その他といった計算メカニズムの方に読み手の注意を向かわせかねないからここでは計算手段とはフリーな概念としてあくまで評価値と言うことにするつまりゲーム木のノードの集合をＶとして、Ｖの各元について評価値を定めるＶからＲへの全射fを考ゆる
いやこう書いてしまうとfはマジで自由に好き勝手に取ってよいと思ってしまうので（書いている本人が）、探索条件を適当に固定した下で、次式を満足しないとfは探索に供する評価値への写像として妥当と言えませんよということは自己暗示しておいてみる
- ∀n∈Ｖ: f(n) = (nを根とする探索を行ったときの最良評価値)
また、ここではゲーム木のノードと局面（＋手番）はあくまで区別する。すなわちゲーム木の異なる位置に現れた同一局面（＋手番）は異なるノードとみなす。
再帰性とは
Tree Strap Searchの論文を超訳したときちらと述べたが、探索木に再帰性を満たせしめること自体は、最善手を正しく選択せしめるための必要条件ではない。
ここで再帰性とは、同一局面（＋手番）を表すノードがゲーム木のどこに現れても同一評価値という性質のことだる*1
まず「どこに現れても同一評価値」ということが探索においてどいうう現象を生じるか明らかにしておく
といっても例によって根から固定深さまでの探索しか考えないが(知能の限界的な意味で
固定深さdまでの探索Sをノードnを根として行ったとして、探索木内の、nから深さ2kの位置にnと同局面・同手番のノードn'が現れたとき、再帰性の定義と前出の暗示により、Ｖが再帰性を満たすなら次式が成立する。
v＝v_best＝v_best'＝v'
ここで
v : nの評価値
v_best : 固定深さdまでの探索Sをnを根として行ったときの最良評価値
v_best' : 固定深さd-2kまでの探索S'をn'を根として行ったときの最良評価値
v' : n'の評価値
さて、n'と、v_bestが根nまで上がる経路pとの関係に注目汁、
簡単なケースとして、fが最善手筋の再生性を常に満すとすれば、n'がpに含まれるなら必然的にv'=vではあるが、そうでなければv'は任意にとり得る。・・・(1)
そうでなくて、fが最善手筋の再生性を常には満たさないとすれば、v'が満たすべき制約は、n'とpの関係だけからは出てこない。・・・(2)
まあ実際にはv_best'がn'まで上がる経路p'と前出定義のpとは、合流すれども分岐はしないという関係にあり、合流する場合はたいていv'=vになってしまうわけだが*2、そうでない場合はv'=vである必然性はありませんよという話になるはず
あんまり明らかにならなかったorz
それはそうと、n'とpの関係についてより具体的な例を1つ思いついたので1つ貼っとく。
fが最善手筋の再生性を常に満たし、かつ相手がfに従って指すプレイヤーだったとする*3。このときpにそって指すことが、自己の勝率を最大化せしめる。（まあ相手にしても同じなわけだが。）
で、サイクル手順の選択自体が勝率向上に結びつく状況*4でないなら、n'はp上に来ない*5。この場合は上に述べたケースの(1)の後半に該当するからv'は任意にとり得る。
再生性とは
GMA0BNがたった今作った造語なわけだが(ﾏﾃ;
イメージとしては、1回の探索で直近の未来d手分の最善手筋を決めせしめる（よって棋譜から連続するd-1手が失われても無問題）という性質のこと。ただしd≧2とする。
もちろん1回の探索で直近の未来d手分の最善手筋がガチで決まるためは相手にも引き続くd-1手の範囲内においてf(Ｖ)に基づく最善手を指し続けて貰うことが前提ので、現実に棋譜の欠落の補間が行えはしないしそういう目的の意図でもないのだが、まあ「再生性」と銘打つ根拠ということで、
で、ゲーム終端ノード（勝敗が決まる）の1手前のノードは（d≧2を満足し得ないが）「再生性を有する」と形式的にみなすことにすれば、「ゲーム木のいたるところで再生性を有するf(Ｖ)」という言い方が妥当性を獲得するので*6以下そうする。
再生性を有するf(Ｖ)の実例としては、先手勝利+1、後手勝利-1、引き分け0としてゲーム終端まで読みきる探索で得たf(Ｖ)が挙げられる*7。こいつは特別で、ガチでゲーム木のいたるところで再生性を有する。おまけに最強だる。
さて、ゲーム木のいたるところで再生性を有するf(Ｖ)に基づく探索に水平線は存在しない。これは明らかすぐる。*8
じゃあ逆はどうかすわなち、水平線が存在しない探索を成させしめるf(Ｖ)は必ずゲーム木のいたるところで再生性を有するのだろうか？
これがですねー成立しないんですねー
nを根とする深さdの探索木の葉の集合と、n'を根とする深さdの探索木の葉の集合とでは、通常（ゲーム終端ノードを除外すると）共通部分を持たないので、両探索木内における評価値の根への上昇経路を互いに独立に設定できるから、成立すると思ったとたんそれをいくらでも崩すことができる。
つまり根から固定深さdまでの探索において、水平線が存在しないのに再生性を一般に満たさない、というf(Ｖ)は驚くほどたくさんあるハズ。
しかも水平線が存在しないのに再生性を一般に満たさないf(Ｖ)において、ゲーム木の部分部分を見たときもまた、再生性が満たされない度合いが相当に大きい（∵Yes, I do it. ただし水平線が無いf(Ｖ)の現物を屏風から出してくれた場合に限る。)
まとめ
*1:いや知らんけど多分(ｵｲ
*2:ただしn'がpに含まれず、途中から合流するケースにおいて例外が有り得る。
*3:将棋の神と言えるかどうかはfの内容に拠るが、後述するように、少なくとも再生性を満たしつつ最強を実現するfが存在するから将棋の神とすることも一応妥当。
*4:千日手を選択すれば引き分けに持ち込めるがさもなくば負ける、というような。
*5:n'がp上に来れば、それはサイクル手順の選択が最善だったということで矛盾。
*6:いや知らんけど、
*7:挙げられるといいつつ実際に現物を見たことはないが。
*8:いたるところで再生性があるということは、最善手筋に沿った個々の探索の再生性の及ぶ範囲同士がゲーム木の根から終端ノードまでオーバーラップし続けているということなので、水平線が入り込む余地がない。水平線があるとしたら矛盾を示せる。
