コンピュータ将棋動画勢!

観るコン将(コンピュータ将棋観戦オンリー勢)から見たコンピュータ将棋の記述

Futility marginがdepthの線形でいい理由の補足

Hatena Blogで数式が書けるみたいなのでそのテストがしたいだけの記事。


Qhapaqの澤田さんのブログの記事Futility marginがdepthの線形でいい理由 - コンピュータ将棋 Qhapaqの導出から、Futility Pruningが成功する確率は、 Zを定数、 dを探索深さ、 \alphaをある定数、 Aを局面の平均分岐数として f(d) = (1 - Ze^{-\alpha^2 d})^{A^d}と書けるのだった。


この確率を dの関数とみてテイラー展開の1次の項までで近似する。

\displaystyle
\begin{align}
f'(d) &= \frac{\partial}{\partial d} \exp(A^d \log(1 - Z e^{-\alpha^2 d})) \\
&= \exp(A^d \log(1 - Z e^{-\alpha^2 d})) (\frac{Z \alpha^2 e^{-\alpha^2 d}}{1 - Z e^{-\alpha^2 d}} A^d + A^d \log(1 - Z e^{-\alpha^2 d}) \log A)
\end{align}
したがって、

\displaystyle
\begin{align}
f'(0) &= (1 - Z)(\frac{Z \alpha^2}{1 - Z} + \log(1 - Z) \log A) \\
&= (Z \alpha^2 + (1 - Z) \log(1 - Z) \log A)
\end{align}


ゆえに、

\displaystyle
\begin{align}
f(d) &\fallingdotseq f(0) + f'(0)d \\
&= (1-Z) + (Z\alpha^2 + (1 - Z) \log(1 - Z) \log A)d
\end{align}
ここで 0 \lt Z \lt 1であることから \log(1 - Z) \lt 0
また A \gt 1であることから \log A \gt 0であることより、
 \displaystyle \alpha = \sqrt{-\frac{(1 - Z) \log(1 - Z) \log A}{Z}}
とすれば dの1次の係数は 0となり、この確率は dが十分小さいとき深さによらず一定であることがわかる。

感想

全体をはてな記法にする必要があるのでやや慣れない。

てか微分しておいてなんだけど、そもそも澤田さんの導出って合ってるのだろうか。
 \displaystyle \int_0^{\alpha d} e^{-x^2 / d}dx = \frac{\sqrt{\pi d}}{2} \mathrm{erfi}(\sqrt{\alpha} d)だけどこれが 1 - Ze^{-\alpha^2 d}の形にはならんやろ。ダウト。
(更にこれを A^d乗した式のテイラー展開の1次の項は kxの形になって k \alpha, Aから決まる定数なのでゼロにはできない。)