指し手/盤面の定義、着手機能の実装

投稿者: | 2017-02-27

先週、GitHubに連珠解析ライブラリREAL Coreのレポジトリを作成しました。
この1週間では指し手位置(MovePosition)、指し手リスト(MoveListクラス)と盤面(Boardクラス)を実装。

指し手位置(MovePosition)

連珠の公式ルールでは15道盤を使うため15×15=225の着手位置があります。Passや無効な指し手を表す手を入れても1byteで表現可能で指し手位置は

enum MovePosition : std::uint8_t

と定義しています。横方向を[math]x[/math]、縦方向を[math]y[/math]、左上の座標を[math](1, 1)[/math]とした座標系をとり、座標[math](x, y)[/math]のMovePositionを

move_position = 16 * y + x

と定義しています。この定義だとMovePositionから[math](x, y)[/math]座標への変換が

x = move_position % 16
y = move_position / 16

となり16の剰余、除算はAND演算、シフト演算として実装できるため効率良く処理ができます。

指し手リスト(MoveListクラス)

指し手リストは指し手位置(MovePosition)の可変長配列(std::vector)で実装しています。固有機能としては[a-o][a-o]形式での文字列からの変換機能を実装しています。また、初期化時の領域長を

「初期化時に与えられるMoveList長1)コピーコンストラクタの場合。デフォルトコンストラクタでは0 + 16」より大きい最小の8の倍数

として領域の再確保を抑制するようにしています。なお、8の倍数にしているのはMovePosition型が1バイトなので8バイト単位で領域を確保するようにするためです。

盤面(Boardクラス)

着手点は

  • 空点
  • 黒石
  • 白石
  • 盤外

の4通りの状態が考えられるので1カ所につき2bitで表現しています。
具体的には

enum PositionState : BitBoard
{
  kOverBoard,     //!< 盤外(0b00)
  kBlackStone,    //!< 黒石(0b01)
  kWhiteStone,    //!< 白石(0b10)
  kOpenPosition   //!< 空点(0b11)
};

としています。盤外を0と定義したのはシフト演算をした時に盤外フラグをセットする処理を省略するためです。

四連、四、三のチェックは縦、横、斜め2方向の計4方向でチェックする必要があるため盤面全体をrotated bit boardで実装しています。1方向につき64bit変数8個(512bit)を使い全体では64bit変数32個を保持しています。

斜め方向は少し工夫が必要で

  • 各列は変数をまたがないようにする
  • 列の区切りとして列と列の間には「盤外」を少なくとも1つは含める
  • 64bit変数8個に収める
  • MovePositionもしくは[math](x,y)[/math]座標から対応する盤面位置(rotated bit boardの配列indexとbitシフト量)が高速に算出できる

点を考慮して定義しています。(具体的な定義についてはレポジトリのドキュメント(board_definition.xlsx)を参照ください。)

最初、MovePositionから盤面位置への変換をTable変換で実装したのですがキャッシュ効率が落ちるためかあまり速度が出ず現在は[math](x,y)[/math]座標から変換する方式を実装しています。(Table変換と比べ30%程度高速化。)

盤面に石を置く/取り除く操作(SetState関数)と盤面位置の状態を取得する操作(GetState関数)の性能を測定したところ

  • SetState: 1.4億回/秒
  • GetState: 4.6億回/秒

でした。(Core i5-2500K, Ubuntu 16.04, g++ 5.4.0(-O3 -DNDEBUG)で測定。)

GetStateはAND演算1回、シフト演算1回でbit boardの配列indexとbitシフト量を出し、bit boardからデータをとって、シフト演算を1回するだけなのでさすがに高速です。SetStateは[math](x,y)[/math]が盤内かチェックした上で、「盤面位置を出してbitをセット」を4方向分繰り返すので4倍近く遅い結果になっています。以前作っていたライブラリとの比較ではSetStateは17%程度、GetStateは2倍程度速い結果が出ています。

References   [ + ]

1. コピーコンストラクタの場合。デフォルトコンストラクタでは0

スポンサーリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください