先月、コンピュータ将棋や囲碁の掲示板でも書いた話なのだが。局面更新処理[*1]の高速化が探索レートに大きく影響することは、恐らく計算機将棋開発者の殆ど全員が気付かれているのではないかと思う。一度でもプロファイラを使ったことがあれば必ず気付く筈だからである。私も例外でなく、10年以上前にプロファイルを取った時は、局面更新が全体の４割前後を占めて極めて重いことを知り、その対策が最大のテーマになったことが何年にも渡って続いた。
もともと謎電は、486DX2を使っていた時代に（置換表なしで）ノード当たりの詰探索コストが約4,000[clocks]程度であることは判っていた。その後、初代Pentium時代（この時も置換表なし）で2,500[clocks]位、その時に初めてプロファイラを使い、局面更新が1,000[clocks]（40%）前後喰うことを知った。この部分を速く出来れば数割は高速化可能だと踏み、今日までに５回、局面更新処理のデータ表現・構造も含めてコードを書き直している。
その間に置換表の実装や探索する手のオーダの強化によって一時的に（探索効率は上がっても）探索レートが落ちたりもしたが、結果現時点では、Barton(AthlonXP)でノード当たり1,450[clocks]、内局面更新が平均220[clocks]まで軽減。こう書く局面更新だけ見て約４～５倍速くなったことになるが、CPUのアーキテクチャが異なるので実際には３倍程度ではないかと思う。
結論を書けば、やはりデータ表現の工夫がポイントで、高速化のコツは、「条件分岐命令を極力減らす」ところにあると感じている。486以降のCPU[*2]は、内部処理のパイプライン化によって高速動作させるアーキテクチャになっている。条件分岐命令の実行時に、その分岐予測が外れるとパイプラインの段数にほぼ比例したストールを起こしIPC値が悪化する。従って、分岐予測がヒットし易いようにするか、あるいは条件分岐命令そのものが極力生成されないようにコーディングすることを心掛けるだけでも相当の高速化が可能になる。つまりは条件分岐命令を減らす為のデータ表現が重要になってくるわけだ。勿論、処理量そのものを減らすアルゴリズムを見つけ出すことも大切だが、ここで言っているのはプロセッサの特性を考慮することも重要だということである。
最近の謎電では、局面更新より寧ろ指手生成の高速化にテーマが移りつつある。特に詰探索の指手生成は、指将棋のように他のノードから手を借りてくるような融通が利き難いし、手の優先付けまで考慮すればかなり重い処理になってしまう。因みに現謎電の「王手＋応手生成コストの合計」は40%前後（ノード当たり約600[clocks]）に達している。これはオーダリングと打歩詰を除く指手の合法性（主に自爆）判定処理を含めているせいもあるが、とりあえずこの部分で２割の削減を目標にして、今月はソースを読み返して改良を検討してみようと思っている[*3]。
[*1] ここで言う局面更新処理は、駒の利きの更新を含んだ移動処理を指している。置換表実装後は、盤面のハッシュキー演算処理や、（置換表への）メモリプリフェッチ処理なども含む。
[*2] 因みに、i486と初代Pentiumは５段、MMXPentiumで６段、Prescott(Pentium4)に至っては31段パイプラインである。９段と言えば名人の段位だが、プロセッサにおいては節操がない。
[*3] 謎電の序中盤力がなかなか改善しない原因は、このように作者が詰探索に異様に手を入れ過ぎているためである。それ以上に、GUIや足廻り系に拘っているのも大問題なのだが。