Haskellで将棋 - Small update - 探索を劇的に高速化させる方法

もしくは探索を劇的に低速化させる方法。

バックグラウンド

遅延評価パワーとか言って指し手生成部分を手前のマイクロベンチマークで2倍以上低速化させた前々回。

Haskellで将棋 - 指し手生成部を少しずつ改良していく - euphonictechnologies’s diary

さて、犠牲を払ってまで指し手生成部分を変更した理由は指し手の生成をいくつかの部分に分けて不必要な指し手生成を抑制することにあった。指し手生成自体を抑制できる上に、盤面評価もスキップできる、遅延評価万歳である。 本家Bonanzaではコルーチンを使っているが、Haskellなら遅延処理でそのまま素直に書けば良い、というHaskell将棋ならではの利点が前回のこのエントリではざっくりとぶち殺されていた。

Haskellで将棋 - 探索を遅延評価を駆使した形に置き換える - euphonictechnologies’s diary

で、実際の探索を劇的に高速化させる方法

前回のこの部分が余計だった。

highfirst :: Ord a => Tree a -> Tree a
highfirst Node {node = n, childNodes = c} = Node n (sortBy (comparing node) (map lowfirst c))
lowfirst :: Ord a => Tree a -> Tree a
lowfirst Node {node = n, childNodes = c} = Node n (sortBy (flip $ comparing node) (map highfirst c))

alphabeta = maximum . maximize' . highfirst . maptree (Eval.eval . fst) . (prune 3) . gametree

highfirstとlowfirstは指し手のオーダリングをする関数であるが、当然この関数の呼び出しは指し手をすべて生成してしまう。指し手生成部は以下のように遅延が考慮されているので

mvGenFullN :: Board.Bd -> [Move.Mv]
mvGenFullN bd =
    (allInNoCheckN bd mvAddCaptures) ++
    (allInNoCheckN bd mvAddNoCaptures) ++
    dropMvs bd

指し手のオーダリングなんかをナイーブにするべきではない。

highfirstを外したバージョンと昔のバージョンで比較してみると

古いバージョン

real 3m32.497s
user    3m26.250s
sys 0m4.276s

新しいバージョン

real 0m17.568s
user    0m16.756s
sys 0m0.572s

というわけで、10倍の高速化ができた。なんてこったい。