1歩で±1動く酔歩のひろがりの期待値は√(歩数)

√Nと聞くと↑これを思い出す人が多いと思います。N個のユニットが並列動作したときの効率が酔歩と同じ式で記述されるのは興味深い

これは、船頭が十分に多ければ、たとえ全員酔っ払って統率が全くとれていなくとも船を山に登らせられることすら可能という並列計算パワーのすばらしい可能性を暗示しているのかもしれません(ﾏﾃ

それはさておき、min-max法でNノードを探索する問題がαβ法において平均的に√Nノードのトラバースで済むというのは酔歩運動との対応がつけやすい気がします。αβ法ではα値とβ値が探索の進行とともに一方向に動いていく(αは増大、βは減少)わけですが、いま(どっちでもいいですが)例えばβ値に注目すると、ORノードがβ値を下回ることを+1、上回ることを-1としたとき、評価値の出現系列が十分乱雑なら、それぞれの生起確率は等しく1/2とみなせて酔歩そのものです。で、β値は初期位置を出発して酔歩で到達した遠距離レコードと考えられます。その最大到達点においてβカットされるから、αカットもβカットが起きないままnノードをトラバースした直後のβカットにより、確率的に酔歩が原点に戻っていくときトラバースされるはずだったn-√n個のノードがトラバースされずに済む、というしくみ。これが繰り返され、トータルでN-√Nノード得をする、、

いや知りませんが(ぉ

まあ実際には評価値の出現系列にはランダムさを欠くところがあるはずなので(現にαβ法で着手決定毎に次手を探索するという手段で将棋のゲーム木が現実的なコンパクトさのプログラムサイズに圧縮できているというのが傍証ではなかろうかと)、上の説明は同時にαβ法の能率が√Nより良くなることが多い説明になっちょりますGMA0BNが酔っ払ってなければ