2011-10-25

人は駒得のみに生くるにあらずその21

futility pruning(以下、単にfutilityと記す)をやってみました。

iteration回数を増やすためには
・null move pruning
・LMR
・futility pruning
とこの3つらしく(←人聞き)、null move pruningは軽いわりにそこそこiterationが回りました。しかしfutilityは駄目です。

平手の開始局面で比較してみました。

・depth 13にて 10946612 nodes , 3741152nps [null move]
・depth 13にて 5497431 nodes , 2700113nps [null move,探索中に1手詰め,futility]
・depth 13にて 5497068 nodes , 2364330nps [null move,探索中に1手詰め,futility,置換表の手でfutility]

futilityをすると、半分ぐらいのノード数になります。枝刈りできています。しかしnpsも25〜30%ぐらい減っています。探索中に1手詰を呼び出すと5〜10%ぐらい減っていたのですが、誤差程度だったので正確に計測していませんでした。

futilityするコストは大変高いということがわかりました。普通なら評価関数などのコストのほうがはるかに上回るはずなのですが、駒割だけの評価関数ですから、相対的にfutilityのコストが目につきます。

futilityは、自玉に王手がかかっていなくて、次の指し手で敵玉にも王手がかからないときに適用されます。安定したノード、すなわち、そんなに評価値が変動しないだろうという局面で適用されます。

「3手の間に急激に龍一枚分も丸得することはないだろう」だとか、そういう仮定のもとに枝刈りをします。

普通、駒を動かすことで(駒の働きを点数化しているなら)なだらかに点数が変動するのですが、駒割だけの評価関数ですと、駒を取ったときにしか点数はつかず、futilityの前提条件自体が崩れています。

つまり
・(駒割だけの評価関数にとって)futility重すぎる
・(駒割だけの評価関数にとって)futilityの枝刈りが妥当ではない
という理由により、futilityは適用しないほうがマシなのではないかと私は思いました。以前のバージョンと対戦させても、iterationが1回多く回っているのにどうも弱いです。R50ぐらい下がっているように思います。

以上の話は駒割のみの評価関数で、「世界最速の指し手生成ルーチン」を用いていることが前提にあるので、もし指し手生成ルーチンが遅くて、futilityの比重がそんなでもない場合は当てはまらないのかも知れません。かなり特殊な話だと思っておいてください。

あと同様の理由で1手詰め判定も、もしかしたら呼び出さないほうが強いのではないかと少し思います。1手詰め判定を呼び出すことによって30%ぐらいnpsがダウンするなら、その分たくさんのノードを読むほうが強くなるのではないかと思います。

「駒得だけの評価関数で」という縛りはなかなか奥深いです。

明日はLMRを実装してみます。これで駄目なら、もうひよこ将棋は大幅な向上は見込めないと思います。futilityが失敗したことで、意外と早く頭打ちになりそうです。