Futility marginがdepthの線形でいい理由 - コンピュータ将棋 Qhapaq

定跡研究の知見をまとめつつある裏で、WCSCに備えて探索部の改造にも手を出しています。

評価関数は億単位の局面を使って億単位のパラメタを最適化するという人間の直感に反するものである一方、探索部は「まずは取る手から考える」とか「この局面は仮に盛り返しても、今考えるベストな展開に及ばないだろうから探索を打ち切る」とか「ある程度考えたらそれ以上考えても仕方ないので指して相手の手を見てから考えよう」とか、割と人間的にも納得の行く理念で作られています。

しかし、その理念をコンピュータの思考に焼きなおすには、幾分かの数理的な小技が必要となります。昨今のコンピュータ将棋の探索部はstockfishから引っ張ってきたルーチンが多く、よもすれば、式の意味を解らずに枝狩りをしている人、いるのではないでしょうか？

今回はstockfishの数あるルーチンの中からfutility marginについて考察していきます。

１．futility margin/pruningってなんぞ

futility pruningはn手以内に今考えてる最善手のスコアを追い抜けそうにない手を枝狩りする探索ルーチンの一つです。例えば、横歩取りで横歩を取る手の暫定評価値が+100だったとします。

暫定評価値は所詮は暫定であるので、他の手（例えば飛車を引いて相掛かり風味にするなど）に抜かれる可能性があります。故に、他の手を今の点数が低いからと枝狩りするわけには行きません。しかし、見込みのない手（飛車をただで捨てる手とか）はさっさと枝狩りしてしまったほうが、有力な手に費やせる時間が増えて、レートが上昇します。

２８飛車は読むとして。９６歩や９８香はどうだろう。どこから枝狩りすればよいのだろう。こうした判断をするときに使うのが、futility marginです。

具体的には、其の局面の浅く読んだ時の点数(score)が

bestscore - score > margin * depth *const

となった時に枝狩りを発動させます。depthは残り探索深さで、仮に読むとしたらdepth手先ぐらいまで読むということを意味します。

marginがdepthに比例するのは、将棋の局面は深く読めば読むほど評価値が変わりうるからなのですが、さて此処で問題。なぜdepthに比例なのでしょうか。やねうら王も読み太も線形にしていますが本当にこの形でいいのでしょうか？

２．点数の変化度はdepthではなくdepthのルートに比例する

まず、depthが１の時について考えます。１手深く読むことで評価値はずれますが、概ね（99%ぐらい？）X点以下に収まるとしましょう。

depthが2の時はどうでしょう。2手先の手の点数のブレは「１手先の点数のブレ」＋「１手先の局面から見た１手先の点数のブレ」で表されます。futility margin的にはブレは概ね2X点以下に収まるとのことですが、実際に2Xが出る確率はもっと低いはずです。というのも、2手連続でめったに出ないX点を出さねばならないからです。１手深く読むことでX点点数がずれる確率が1%だとすれば、２手深く読むことで2X点点数がずれる確率は0.01%です。

細かい導出はおまけに任せますが、stockfishさん、深く読むときにビビり過ぎなのではないでしょうか？

３．枝狩りする局面の数を考えると釣り合う

ある局面からd手離れた局面の評価値がxずれる確率は

$e^{-x^{2}/d}$