ビットボード
これまで盤面の状態を表現するのに8×8の2次元配列を使ってきましたが、無駄にメモリを食うので、ビット演算で扱うように変更します。オセロの盤面は8×8=64マスなので、64ビット整数(C#ではulong型)を使えばちょうと盤面上の石の有無を表現できます。これがビットボード(Bit Board)と呼ばれる手法です。ただし、石には黒(先手)と白(後手)があるので、盤面の状態を表現するには64ビット整数が2個必要です。それでも、バイト型の2次元配列を使うのに比べればメモリは1/4で済みます。
ビットボードは、ビット演算を駆使すれば合法手の列挙やひっくり返しなどの処理を高速化することができますが、それは次回にやりたいと思います。
小手先のテクニック
今回は、小手先のテクニックによる高速化をいくつか試してみました。しかし結論から言うと、さしたる効果は得られませんでした。コードの可読性を損なうデメリットと比べてペイするほどのメリットとも思えなかったので、けっきょくほとんどの変更はコミットせずに捨てることになりました。C#のコンパイラは、よほど高度な最適化をしているものと思われます。
- 盤面データと着手データをclassからstructへ変更
- サイズが小さく、寿命の短いものはstructのほうが有利
- サイズが大きいと、代入や関数への値渡しをすると余計に遅くなる
- unsafeにして配列のループ処理をポインタで処理する
- クラスの継承、仮想関数のオーバーロードはしない
今回は、classからstructへの変更のみコミットしました。
今回のソースのスナップショット
今回のTIPS
関数への引数の渡し方には、値型の値渡し、参照型の値渡し、値型の参照渡し、参照型の参照渡しの4通りがあって、言語によって対応と扱いが異なります。ここらへん、わりと混乱があって、「参照型の値渡し」のことを「参照渡し」と呼ぶ人もいるので要注意です。
| C | Java | C# | |
|---|---|---|---|
| 値型の値渡し | ふつうに渡す | プリミティブ型を渡す場合 | structなど値型をふつうに渡す |
| 参照型の値渡し | ポインタ渡し ※1 | クラスを渡す場合 | classなど参照型をふつうに渡す |
| 値型の参照渡し | ポインタ渡し ※1 | × ※2 | structなど値型をrefで渡す |
| 参照型の参照渡し | ダブルポインタ渡し | × ※2 | classなど参照型をrefで渡す |
