それはそうと、さらにその前のエントリでGMA0BNが得意になってさかんに言いたてていた「精度∞の評価関数構成法」について思ったより重篤な間違いがあったので修正してみた↓↓↓orz

「精度∞の評価関数構成法」の評価値操作で満たされるべき条件は約こんな感じ。

• 条件1：ゲーム木の根r0から葉まで読み切るmin-max探索S0の主経路上のORノードnから固定深さまでのmin-max探索Sを行うとき、探索Sの末端ノードのうち、nの子（ANDノード）dから到達可能な全ての評価値にΔv（＞0）を加算しても、r0からnまでのS0の主経路に変化を及ぼさないこと。
• 条件2：ゲーム木の根r0から葉まで読み切るmin-max探索S0の主経路上のANDノードn'から固定深さまでのmin-max探索S'において、探索S'の末端ノードのうち、n'の子（ORノード）d'から到達可能な全ての評価値にΔv'（＜0）を加算しても、r0からn'までのS0の主経路に変化を及ぼさないこと。

ところが、あるノードの評価値の変更がそのまま根ノード付近のレベルまで伝わってしまうハイウェイみたいなものがどうしても存在し得て、それがどこにあってどういう通過条件かは具体的にゲーム木の詳細を見ないと否定できない的な意味で上記条件1,2は一般には成立困難なように見える。
今日わそこらの交通事情がどうなっているのかじっくりほじくり返してみようと思う

いまあるノードnの子ノードdの評価値を変化させるとして、d以外のnの子ノード評価値の集合をDとする。

補題1

min-max探索の評価値がxであるANDノードnについて、末端から入ってくる評価値の1つをv→v'に変更（ただしv'＞v）したとき、変更後のnの評価値x'は次のようになる。

　i) v≠xならx'=x=min{D}（非変化）
　ii) さもなくばx＜x'≦v'、等号成立条件はv'≦min{D}、等号非成立時x'=min{D} （結局x'≦min{D}でもある)

照明

これはv→v'によってnの評価値x=min{v, min{D}}がx'=min{v', min{D}}に変わるという話。

v≠xならv＞min{D}かつx=min{D}という可能性しか残らない。このときv'＞vよりx'=min{v', min{D}}=min{D}、よってx=x'。
v=xかつv'≦min{D}のときx'=v'。よってv=x＜x'=v'。
v=xかつv'＞min{D}のときx'=min{D}。よってv=x＜x'=min{D}＜v'。

補題1'

min-max探索の評価値がxであるORノードnについて、末端から入ってくる評価値の1つをv→v'に変更（ただしv'＜v）したとき、変更後のnの評価値x'は次のようになる。

　i) v≠xならx'=x=max{D}（非変化）
　ii) さもなくばx＞x'≧v'、等号成立条件はv'≧max{D}、等号非成立時x'=max{D} （結局x'≧max{D}でもある）

照明

補題1の双対ってことでおk(多分

補題2

min-max探索の評価値がxであるORノードnについて、末端から入ってくる評価値の1つをv→v'に変更（ただしv'＞v）したとき、変更後のnの評価値x'は次のようになる。

　i) v'≦max{D}ならx'=x=max{D}（非変化）
　ii) さもなくばx'=v'

照明

これはv→v'によってnの評価値x=max{v, max{D}}がx'=max{v', max{D}}に変わるという話。

v≠xならv＜max{D}かつx=max{D}という可能性しか残らない。
このとき
i) v＜v'≦max{D}（=x）ならx'=max{v', max{D}}=max{D}。よってx=x'＞v'。
ii) v'＞max{D}（=x）ならx'=max{v', max{D}}=v'。よってx＜v'=x'。
まとめるとx≦x'で、等号成立条件はv'≦max{D}。
v=xならv≧max{D}。このときx'=max{v', max{D}}=v'。よってx＜x'=v'。

補題2'

min-max探索の評価値がxであるANDノードnについて、末端から入ってくる評価値の1つをv→v'に変更（ただしv'＜v）したとき、変更後のnの評価値x'は次のようになる。

　i) v'≧min{D}ならx'=x=min{D}（非変化）
　ii) さもなくばx'=v'

照明

補題2の双対ってことでおk(多分

補題3

将棋に周期3手以下のサイクル手順は存在しない。

照明

1回の手番で1つの駒しか動かせず、かつ1回の手番で盤→盤移動か駒台→盤移動できるのは自駒のみだから、

置駒を動かしたとき、空いた場所を再び埋めるには少なくとも次の自己の手番まで待たねばならない。
持駒を打ったとき、減った持駒を再び補充するには少なくとも次の自己の手番まで待たねばならない。
将棋にパスはない（置駒を動かすか、持駒を打つかのどちらかを自己と相手交互に必ず行う）。
以上を合わせると言える。

補題3’

将棋のゲーム木において、p→q→r→sという経路と、p→q' (q≠q')という経路があるとき、q'から葉に向かう経路はrには合流しない

sに合流することはあり得るが、そのときp→q→r→sとp→q'→r'→sのmin-max法的価値は等しい。

照明

p,qにおいて手番であるプレイヤーをそれぞれA,Bとする。

q≠q'という仮定より、pから次のノードに向かう際のA駒移動（指すor打つ）によって生じたA駒の空き（盤上or駒台上）の位置がqとq'では異なるから、rでの合流はあり得ない。
次に、もしq'固有の空きを埋めねば局面がsに一致し得ないなら、それを埋めた後さらにp→qで生じたq固有の空きを作る必要があるからsでの合流はあり得ない。
q'固有の空きを埋めなくとも良いケース（r→sにおいて同じ場所が空く）とする場合sで合流し得るが、このとき相手がq→rで出す手とq'→r'で出す手は同じ手でなければならない。

さて、2つ以上のノードからなるQという経路を考え、探索Sの下でのQの先端ノード評価値vがv→v+Δv（＞0）と変化したときのQの根ノード評価値xの変化x→x'を考えると、補題1,2より一般に次式が成立する。
　x≦x'≦v+?vかつx'≦min{経路Q内ANDノードのmin{D}}
等号成立条件は次の通り。
　i) x=x'についてはx≠v
　ii) x=v+?vについてはx=vかつv+?v≦min{経路Q内ANDノードのmin{D}}
　iii) x=min{経路Q内ANDノードのmin{D}}についてはv+?v≧min{経路Q内ANDノードのmin{D}}
i)より、経路Qが探索Sの主経路（またはその部分）になり得ない（そうできるような探索の根が存在しない）ときx=x'となり、vの変化はxに現れない（ブロックされる）。
さもなくば、ii), iii)より、x'は最大min{経路Q内ANDノードのmin{D}}に達し得る。（もとの値xより小さくなることはない。）
（これらを規定するのはS0（の評価関数や主経路）でなくS（の評価関数や主経路）であることに注意。）

一方、r0からnに至る探索S0の主経路P（r0→...→n）について考えると、主経路という仮定より探索S0の下でi)の可能性は排除されて、nの評価値を上げればr0の評価値がmin{経路P内ANDノードのmin{D}}までの範囲で上がる。
このときnの評価値をどこまで上げられるかというと、やはりmin{経路P内ANDノードのmin{D}}が上限となる（さもなくば評価値の伝播がANDノードでブロックされ、PはS0の主経路でなくなる）。
（これらを規定するのはS（の評価関数や主経路）でなくS0（の評価関数や主経路）であることに注意。）

ややこしいorz

全体をもう一度スケッチし直すと、
(1) ORノードnを根とする探索Sの探索木のうち、nのある子ノードdから到達可能な末端ノードの評価値を一斉に＋Δvだけかさ上げしたとき、dの評価値は正確に＋Δvされる。
(2) 補題3'により、(1)の影響は2ノード以上の経路Qを経てS0の主経路Pに伝わる。その過程で評価値は最大で(元の値)+min{経路Q内ANDノードのmin{D}}に成り得る。
(3) Pを根方向に伝搬する評価値は、(元の値)＋min{経路P内ANDノードのmin{D}}を超えられない（さもなくばPはS0の主経路でなくなる）

、、、帰っていいですか？（´∀`;）