オーダリング3
オーダリングって考えれば考えるほど悩ましい。
理想的なアルファベータ探索なら探索木の大きさは 2b^(d/2)、mini-max なら b^d 。 全てのノードで初手でβカットが行われている場合はいいんだけど、平均βカット位置が x のときは、どれぐらいになるんだろうか? (x≒1なら O*1
sakurapyonで PV/All/Cutの比率を実測すると 大半のノードは Cut node であった。たぶんPVS使ってるとそうなるのだろう。大半を占める Cut node を早く beta cut させることが重要。PVノードは極めて少ないので、手間隙かけて精度を高めてもいい。だから、PVではハッシュの手だけ使って非PVでは値も使うのは理に適っている。
さて、chessprogramming - Move Orderingには、こう書いてある。
A typical move ordering consists as follows:
- PV-move of the principal variation from the previous iteration of an iterative deepening framework for the leftmost path, often implicitly done by 2.
- Hash move from hash tables
- Winning captures/promotions
- Equal captures/promotions
- Killer moves (non capture), often with mate killers first
- Non-captures sorted by history heuristic and that like
- Losing captures (* but see below
これは良くわかる。HistoryやKiller Movesが絡まなければ。
チェスの指し手の中では、Winning capturesやpromotionsは少ない。だから、これを優先しても全体のオーダリングにあまり悪影響はない（と思う)。
ところが将棋の場合は、中盤の指し手(200手ぐらい?)のうち、Winning capturesは少ないけど、Promotionsはそこそこの数になる。さらに打つ手があって、打つ手は(禁則を除けば)空所の数*持ち駒の種類なので、かなり多くなる。ここも悩ましい。
*1:b*x)^d/2)ぐらいかな? とは思っているんだけど)。 強いソフトの平均βカット位置はどれぐらいなんだろうね。1.1以下かなー?((http://d.hatena.ne.jp/ak11/20110816#p1
