概要

最近Rubyの勉強を進めてまして，その一環としてRubyでオセロを作成することにしました．

ただ，2次元配列を使って盤の状態を管理するのが主流だとは思うのですが，先輩がBitBoardというものを用いてC++でオセロを実装していたのを思い出したので，僕もBitBoardを用いて実装することにしました．

BitBoardとは

まずは普通の2次元配列を用いたオセロ盤の実装方法ですが，

board[10][10]

みたいな感じで，壁を含めた2次元配列を用いるのが主流だと思います．初期値は以下のようになっていることが多いです(多分)．

BLACK_STONE =  1
WHITE_STONE = -1
EMPTY       =  0
WALL        =  2
board = [
          [ 2,  2,  2,  2,  2,  2,  2,  2,  2,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0, -1,  1,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  1, -1,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  2,  2,  2,  2,  2,  2,  2,  2,  2]
        ]

しかし，今回使ったBitBoardは以下のようにして実装しています．

white = 0x1008000000
black = 0x810000000

なにこれって感じになるかと思います．上記のwhiteとblackはオセロの盤の初期状態を表しています．

このように2つの変数を用いて盤を管理するのがBitBoardで実装したオセロになります．

whiteとblack変数はそれぞれ白石の場所，黒石の場所を表しています．

どのように表しているかというと，以下の図を見ていただくと理解しやすいかと思います．

	A	B	C	D	E	F	G	H
1	1	2	3	4	5	6	7	8
2	9	10	11	12	13	14	15	16
3	17	18	19	20	21	22	23	24
4	25	26	27	28	29	30	31	32
5	33	34	35	36	37	38	39	40
6	41	42	43	44	45	46	47	48
7	49	50	51	52	53	54	55	56
8	57	58	59	60	61	62	63	64

表の1行目と1列目は座標を表す文字数字となってます．内部の数字はその座標に割り当てられたbitの桁で，例えばA1であればbitの1桁目で表すことになります．

ちなみにこの2つの変数にはルールがありましてどちらも1となるbit位置が存在してはいけないというものです．同じ場所に2つの色を石が存在する状態はありえないので禁止状態になります．

BitBoardで反転処理

BitBoardを用いると高速に反転処理が行えるようになります．

def create_reverse_bit(player, enemy, pos)
  rev = 0
    
  # 既に石がある場合は0を返し，終了する
  if ((player | enemy) & pos) != 0
    return rev
  end
    
  # 右
  tmp = 0
  mask = (pos << 1) & 0xfefefefefefefefe
  while mask != 0 && (mask & enemy) != 0
    tmp |= mask
    mask = (mask << 1) & 0xfefefefefefefefe
  end
  if mask & player != 0
    rev |= tmp
  end
  ... 以下省略
end

このメソッドでは現在プレイヤーのbitboard変数とそうでないプレイヤーのbitboard変数，そして置かれた場所のbitを表すposを受け取ります．

このメソッドは最終的にrevというひっくり返る場所のbitを表すrevを返します．

既に石が置かれているときはひっくり返せないので0を返します．

# 既に石がある場合は0を返し，終了する
if ((player | enemy) & pos) != 0
  return rev
end

次に8方向に対してひっくり返る場所を探索します．ここでは右方向だけを紹介しますが，他も同じような方法で行います．

まず

tmp = 0

を用意します．ここにその方向でひっくり返る場所のbitを表す数値を格納します．

その後，mask変数というものがあるのが確認できると思います．

mask = (pos << 1) & 0xfefefefefefefefe

これはBitBoard特有の問題を解決するために使用されます． BitBoardでは以下の表のように管理されると紹介しましたが，連続した値が盤上では繋がっていないというのがわかるかと思います．

	A	B	C	D	E	F	G	H
1	1	2	3	4	5	6	7	8
2	9	10	11	12	13	14	15	16
3	17	18	19	20	21	22	23	24
4	25	26	27	28	29	30	31	32
5	33	34	35	36	37	38	39	40
6	41	42	43	44	45	46	47	48
7	49	50	51	52	53	54	55	56
8	57	58	59	60	61	62	63	64

これをmaskなしでbitをずらしていくと，繋がっていないはずの場所が，繋がっているように処理されてしまうのです．

0xfefefefefefefefeはA列だけに0にしたbit列です．これを使うことにより，探索ポイントを右にズラし続けたあとA列に入ってしまったときに強制的に0とすることで探索を打ち切らせることができるのです．

while mask != 0 && (mask & enemy) != 0
  tmp |= mask
  mask = (mask << 1) & 0xfefefefefefefefe
end

最終的に得られたtmpをrevに|=演算子で結合します．

if mask & player != 0
  rev |= tmp
end

上記の方法を全方向で繰り返すと反転するbitを作成することができます．

(説明が雑すぎる気がするので時間があれば編集します)

BitBoardで著手可能位置の生成

BitBoardで著手可能位置の生成を行うのは容易です．これも同じく右方向だけを紹介します．

def create_movable_pos(player, enemy)
  blank = ~(player | enemy)
  mobility = 0

  # 右
  masked_enemy = enemy & 0x7e7e7e7e7e7e7e7e
  t = masked_enemy & (player << 1)
  ## 5回繰り返す
  5.times{t |= masked_enemy & (t << 1)}
  mobility |= blank & (t << 1)
  ... 以下省略
end

(詳しい説明はまた追記します…)