ビットボード
これまで盤面の状態を表現するのに5×5の2次元配列を使ってきましたが、ビット演算で扱うように変更します。石の有無を1ビットで表せば彼我の石の位置は各々25ビットの整数で表現できます。実際にはUInt32型の変数を2個使うことになります。局面の探索において配列を生成を繰り返さなくて済むので高速化でき、またメモリ使用量も減ります。
Span
これまで合法手列挙の関数では、関数内で合法手のListを生成していました。これは前述の配列の生成と同様に、何万回も繰り返すとコストが大きいです。形四の場合、任意の局面での合法手は高々32通りなので、あらかじめ 32×探索の深さ ぶん確保しておいた配列から探索の階層ごとに32個ずつSpanで切り出して使えば高速化できます。またそもそも、Listより配列のほうが高速です。
ビット演算
合法手列挙、正方形判定、静的評価関数にビット演算を活用した工夫をほどこして高速化しました。また、無駄なオブジェクト生成や関数呼び出しを極力なくすように修正しました。
KCSharp ver 0.5
変更
- 盤面を2次元配列ではなくビットボード(整数)で持つように変更 (高速化・省メモリ)
- 合法手列挙に用いるListをSpanに変更 (高速化)
- 正方形判定をビット演算に変更 (高速化)
- 合法手列挙および静的評価関数をビット演算を用いて高速化
ソースはこちら
