Futility marginがdepthの線形でいい理由の補足
Hatena Blogで数式が書けるみたいなのでそのテストがしたいだけの記事。
Qhapaqの澤田さんのブログの記事Futility marginがdepthの線形でいい理由 - コンピュータ将棋 Qhapaqの導出から、Futility Pruningが成功する確率は、を定数、を探索深さ、をある定数、を局面の平均分岐数としてと書けるのだった。
この確率をの関数とみてテイラー展開の1次の項までで近似する。
したがって、
ゆえに、
ここでであることから
またであることからであることより、
とすればの1次の係数はとなり、この確率はが十分小さいとき深さによらず一定であることがわかる。