GMA0BNでもわかるNarrow window
1
まず、アルファベータ法におけるαβウィンドウの挙動を復習汁、
いま当方手番ノード（●）以下の探索を、αβウィンドウ[α, β)の下で始めたとすると、事態は次のステップで推移せり
- ●が探索の末端（探索木の葉）ならば、局面評価値を計算してそれを返して終わる。[RETURN]
- さもなくば、置換表でも引いてみて、エントリにHitした場合、
- fail-Highだったりfail-lowだったりしたらそれはそれでその値を返して終わる[RETURN]
- どちらでもない場合は、可能な限り置換表に記録されているlower boundとupper boundに従いαβウィンドウを縮小して次に進む
縮小した場合は縮小後のαβウィンドウを改めて[α, β)と置こう - 縮小した結果α=βになった（●のミニマックス値判明）ならαを返して終わる。[RETURN]
- 子ノードを列挙する*1
このときα値を増大方向に更新もする。
α≧βになったら、α値を返す（βカット）[RETURN] - α値を返す*2
で、子ノードはもちろん相手手番（○）であって、それらについて再帰的に上と同様の手順に従う探索ルーチンが再帰的に呼ばれて評価値が返されるわけだが、それら評価値は原則*3シーケンシャルにやってくる。すわなち、第1番目の子ノード以下の探索結果としての評価値v_1、第2番目の子ノード以下の探索結果としての評価値v_2、...が順番に取得され、αを上回ったときその値でαが更新される。つまり、当方手番における子ノードの列挙において、αβウィンドウはαのみが増大する形で縮小する（同じ親の子の列挙中はβは不変）。
2
このことの意味を考えよう。それはすわなち、第i番目の子ノード以下の評価値としてv_iが返され、αが更新されつつあるとして、
- 「Tの葉のうち、評価値α以下であるノードに到達することが明らかな相手の手は、今やっている●の子ノード列挙の中において考える必要ないにょろ」
という意味になる。
なぜか？上記ステップを探索木Tの根において[-∞, +∞)から始め*4、以下上記ステップを再帰的に厳密に適用する限り*5、いかなる時点でも次のことが成立するからだる
- Tの中で相手がいかなる着手をしようとも、当方は今いるノード●から評価値α以上のTの葉ノードに到達できる
ただしαは子ノード列挙中に随時更新されている最新の値。
これに呼応して、アルファベータ法は次の具合に仕事をサボる：
- 相手手番○において、評価値α以下であるノードに到達することが明らかな相手の手を見つけたら、当該手番の子ノードの列挙を打ち切り、そういうのを見つけた旨を呼び出し元に報告する
呼び出し元（当方手番●）では、返ってきた評価値vが呼び出し時に与えたαに対してv≦αであったなら、そういうのを見つけたんだなあ、と了解すると同時に、そのvはv≦αである故に呼び出し元のαを更新し得ないから、探索結果に影響を及ぼさない。
で、探索木Tの根まで呼び出しが戻ったとき、根において[-∞, +∞)から始めていることから、「そういうのを見つけたんだなあ、」で全体の探索が終わることは決して無く、必ず最善手とともにミニマックス値が取得され、もちろんミニマックス法で得られるものと等しい。
3
ここまでは、探索木Tの根においてαβウィンドウ[-∞, +∞)から始めて自然にαβウィンドウ（のα側）が狭まる場合の話であった。
これを、根からいきなり[α, +∞)で始めたら何が起きるか？
上述のように、これは
- 「Tの葉のうち、評価値α以下であるノードに到達することが明らかな相手の手は、今やっている●の子ノード列挙の中において考える必要ないにょろ」
という意味になるわけだが、ここでは●＝根なのだ。だから、相手の指し手のうち、当方に不利なものが不自然に除外されつつ探索がなされることになり、当方にとって甘口な結果が返ってくる。すわなち、そうして得られた評価値がv_0だったとして、それは次のことが照明されたにすぎない：
- ミニマックス値≦v_0 ・・・(1)
この状況からミニマックス値を突き止めるには、次の場合分けに従う必要がある。
- v_0≧αなら、v_0＝ミニマックス値 [Q.E.D.]
- v_0＜αなら、[-∞, v_0)かその部分範囲でさらに探索する。（少なくとも[-∞, v_0)で探索した結果は一発でミニマックス値に等しいことが言える。）
で、根ではなくて中間ノード（ただし当方手番●）において自然なαβウィンドウに対して天下りにα側を狭めたときも同様で、当該中間ノードを根とするTの部分木tについて式(1)が成立汁、というだけの話。tのミニマックス値をつき止める方法もTと同様の場合分けが要る。
4
ここまでは、α側を狭める話であった。ではβ側を狭めたらどうか？
当方手番●の子ノード列挙中にαの値がαであることと同様に、相手手番○の子ノード列挙中にβの値がβであることには、次の意味がある。
- 「Tの葉のうち、評価値β
以下以上であるノードに到達することが明らかな当方の手は、今やっている○の子ノード列挙の中において考える必要ないにょろ」
よって、もしβをわざと狭めてやったら、当方にとって辛口な結果が返ってくる。すわなち、そうして得られた評価値がv_0だったとして、それは次のことが照明されたにすぎない：
- ミニマックス値≧v_0 ・・・(2)
この状況からミニマックス値を突き止めるには、次の場合分けに従う必要がある。
- v_0＜βなら、v_0＝ミニマックス値 [Q.E.D.]
- v_0≧βなら、[v_0, +∞)かその部分範囲でさらに探索する。（少なくとも[v_0, +∞)で探索した結果は一発でミニマックス値に等しいことが言える。）
で、根ではなくて中間ノード（ただし相手手番○）において自然なαβウィンドウに対して天下りにβ側を狭めたときも同様で、当該中間ノードを根とするTの部分木tについて式(2)が成立汁、というだけの話。tのミニマックス値をつき止める方法もTと同様の場合分けが要る。
5
ここまでは、αかβ片方だけを狭める話であった。では両方狭めたらどうか？
これわ、ある意味重ね合わせが成立する。なぜなら、αを制限したとき制限されるのは相手手番の手、βを制限したとき制限されるのは当方手番の手、ということで、作用先が背反だからだる*6。よって式(1)と(2)はどちらも相変わらず成立し、まとめると
- α≦v_0＜βなら、v_0＝ミニマックス値
- v_0＜αなら、少なくとも[-∞, v_0)で探索した結果は一発でミニマックス値に等しいい
- β≦v_0なら、少なくとも[v_0, +∞)で探索した結果は一発でミニマックス値に等しいい
となる
6
ここで伏線を回収せねばならない。
ここまでαβウィンドウを適当にせばめてもおk、みたいな印象をふりまきつつ書いてきたが、実はそうしておkなのにはとある条件をクリアせねばならないのだる、、*7
すわなち、αやβを何に対して狭めることが妥当か、という問題で、
- α側を狭めるときは、自然なαβウィンドウのαに対して狭めねばならない
- β側を狭めるときは、自然なαβウィンドウのβに対して狭めねばならない
ここで、自然なαβウィンドウとは、探索木Tの根においてαβウィンドウ[-∞, +∞)から始めて自然にαβウィンドウ（のα側）が狭まる場合の各ノードでのαβウィンドウのこと。
上記以外（自然なαβウィンドウについて全く未知の状態で、適当なαβウィンドウを勝手に設定する等）だと上述の式(1)、(2)は一般に成立しない。例えば、ミニマックス値が+2000なのに、突然[+2100, +2101)で探索を始めてv_0=+2100を得る、となるケースは実在する。
Scout系の技法が成立するのは、自然なαβウィンドウの中の少なくとも1点の値vがわかっている状態から、vに基づきNallow windowを設定するからなのだる
むすび
以上のことを踏まえれば、適当なヒューリスティクスを入手できたときに、それに合わせて探索ロジックをいかようにでもカスタムできるから検討を祈る*8
いや書いてあることが何か大間違いだったらｽﾏﾝが、(ﾏﾃ;
*1:Killer moveのトライやオーダリング等があるが、その水準の詳細はここでは無視する：
*2:ここでのαは常にα≧ミニマックス値。αの代わりにミニマックス値を返しても良いが、親ノードより上があるときに、そこでのβ値の減少が鈍るから、枝刈の効率が多少低下してしまう。
*3:その列挙操作を分割して並列化しない限り
*4:←重要1
*5:←重要2
*6:とわいえ、双方に対する作用が全く独立というわけではないから重ね合わせの成立を言うには本当はもうちょっと厳密な論証が要りそうだるが
*7:伏線なので上述の本文中にも微妙に書いてある
*8:ミニマックス値をつき止めずに打ち切れば前向き枝刈りだが、つき止めるまできちんとやるならカスタムしても後ろ向き枝刈りだる
