前回作成した囲碁プログラムにパターンを適用すると余りにも遅かったので、以下のようにボードの構成を変更して高速化を行った。
前回
- ボードを各目の石の色で構成
高速化版
- ボードを連の集合で構成
- 各連ごとの呼吸点の位置の情報(ビットボード)を保持
- 各目が属する連のIDを保持
前回のボードの構成では、石を置くたびに隣接する石のつながりと呼吸点を調べる必要があったが、そのために4方向を再帰的に調べる必要があった。
一方、高速化版の構成では石を置いた位置に呼吸点がある連について調べればよい。
呼吸点の位置はビットボードになっているので、組み込み関数の_bittestを使うことで高速に処理できる。
連をつなげる処理で呼吸点をマージする際も論理和で処理できる。
他にもビット操作が必要になる箇所で組み込み関数の_bittestandsetや_bittestandreset、_BitScanForward、__popcntも使用した。
移植性を考慮するとこれらのビット操作をCPUの命令を使わずに演算で処理すべきだが、ビットボードのメリットがなくなってしまうので移植性は考慮しないことにした。
実際に実行速度を測定したところ、19路盤で枝狩りなしの10000回のランダムプレイアウトの1手目の処理時間が、
| 前回 | 31407 ms |
| 高速化版 | 7562 ms |
という結果で、約4.2倍高速になった。
他にも、疑似乱数の関数をC言語の標準ライブラリのrand()から、最新のStockfishでも使われているxorshift*にしてみたが、こちらは15ms差があったが誤差の範囲で速度の違いはなかった。
Visual C++のrand()の実装は速度面では問題ないようだ。
Stockfishがxorshift*を使っているのは、疑似乱数の質が理由なのかもしれない。
rand()は周期がRAND_MAX (32767)であまり質がよいとは言えない。
前回から、メモリ管理はヒープから動的に取得しないですべて固定サイズで
グローバルかスタック上で使用するようにしている。
今回、連の情報でメモリ使用が増えたので、19路だとスタックサイズがデフォルトだと溢れてしまった。
スタックサイズはコンパイラオプションで増やせるのでそれほど気にする必要はないが、
ボードのコピー時間も考慮して座標の型をintからshortに変更した。
型の変更で速度に違いはなかった。
32bitと64bitそれぞれでビルドしたもので速度を比較すると、
| 32bit | 7875 ms |
| 64bit | 7562 ms |
で、1.04倍ほど64bitが速かった。
ボードの構成を変えたことで、各連の呼吸点の数がわかるようになったので、
プレイアウト時にアタリを助ける手を高速に選択できるようになる。
次は、それでどれだけ強くなるのか試してみたい。
また、呼吸点の数を含めたパターンも高速に処理できるようになったので、
パターンを使ってまともな速度で処理できるか確認したい。
連と呼吸点を正しく保持する処理の実装は、バグとりに結構時間がかかった。
自分で作りたかったということがあるが、オープンソースのプログラムの実装を調べてから方がよかったかもしれない。
