ビットボードの紹介～少しのオセロ実装を添えて～

こんにちは。Qiita初投稿となります。お気軽にご覧いただければと思います。

##Bitboardとは
みなさんはBitboardというデータ構造について聞きいたことはありますでしょうか？私はプロコンに関わるまで知りませんでした(笑)
名前から察しがついている方も多いとは思いますが、Bitboardは盤面をBit、つまり**0・1の2進数で表現する**ことで処理の高速化を図るデータ構造です。
以降では具体的な例を交えながらご紹介していこうと思います。

##2進数で盤面を表現するには
本記事の題にもある通り、本記事全体を通してオセロを例にして説明してこうと思います。

通常オセロのプログラムを書く際、どのように盤面を表現する事が多いでしょうか？
<img width="400" alt="スクリーンショット 2020-12-17 21.07.23.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/857399/e84a2671-9600-e5a2-7e78-22854f957751.png">
ぱっと思いつくのだと、こんな感じで盤面の大きさ分の2次元配列に黒石・白石・置いてないという状態を数字などに置き換えて代入して表現するものが多いと思います。

<img width="400" alt="スクリーンショット 2020-12-17 21.47.44.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/857399/f8bafb05-6f14-1812-ed3f-840178490c5e.png">

Bitboardでは石が置いてある場所が1、置いていない場所が0と考えて2進数で表現します。盤面の大きさは8×8、つまり64マスあるので64bitで表現できることがわかると思います。
また、2進数では白石と黒石の区別をすることができないので、**白石の盤面の状態と黒石の盤面の状態の2種類を保持**します。図にするとこんな感じです。

<img width="400" alt="スクリーンショット 2020-12-17 21.50.43.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/857399/6705999a-ae5c-55e1-0d81-3275f78e42bf.png">　　<img width="400" alt="スクリーンショット 2020-12-17 21.52.30.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/857399/8f403951-642d-8f57-5931-226897e95e10.png">

単純と言えば単純なのですが、プログラムに落とすととってもわかりずらくなりますので気をつけてください。

##盤面の操作について
では今度は実際に盤面を操作してみましょう。

Bitboardでは配列とは違い、盤面が2進数で表現されているのでANDやORなどの論理演算やbitをずらすビットシフトをすることができます。
Bitboardではこの論理演算やビットシフトを駆使することで盤面の操作を行います。

盤面の座標は**0スタート**として考えてください。
ここからはちょっと図を作るのが大変なので文字で盤面を表現します笑

###石を置く
「石を置く」ための手順は至って単純です。(5, 3)の場所に置いてみましょう。因みに表現としては、(x, y)になります。
まず上位1bitが1で、残りの63bitが0の変数を用意します。

```
1000000000000000...0000000
```

これを8bitごとに区切って改行して表示してみます。

```
10000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
```

こんな感じになりますね。これが先ほどまで図で表現していた盤面になります。

では、これを置きたいマスまでビットシフトし、1を移動させます。
この時シフトさせる数は`y×8+x`で計算する事ができます。今回の例で言えば`3×8+5=29`回ビットシフトさせます。

すると以下のような状態になります。正しく場所が移動できていることがわかると思います。

```
00000000
00000000
00000000
00000100
00000000
00000000
00000000
00000000
```

あとはこの置きたい場所にビットが立っている盤面を置きたい色の盤面にOR演算することで追加することができます。

```
00000000      00000000    00000000
00000000      00000000    00000000
00000000      00000000    00000000
00000100  OR  00010000 =  00010100
00000000      00001000    00001000
00000000      00000000    00000000
00000000      00000000    00000000
00000000      00000000    00000000
```

###置ける場所を列挙する
オセロにおいて重要な処理についてです。少し処理が複雑になります。
初期状態の置ける場所を列挙する処理を例にとってみます。

具体的な処理を説明する前に、盤面の端を示すマスクを紹介しようと思います。

```
horizontal mask  vertical mask  allside mask
   01111110        00000000       00000000
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        00000000       00000000
```

盤面はあくまで2進数のため、プログラム側から見るとどこが**盤面の端なのかわかりません。**(本記事では2進数を盤面の大きさで改行してわかりやすくしています)
そこで、盤面の端を示す上記のマスクを使うことでその問題を解消しています。

では、具体的な処理の説明に入っていきます。今回の例では初期状態で置ける場所を一部列挙してみます。
まず初期状態の盤面を用意します。

```
player board  enemy board
  00000000     00000000
  00000000     00000000
  00000000     00000000
  00010000     00001000
  00001000     00010000
  00000000     00000000
  00000000     00000000
  00000000     00000000
```

次に`enemy board`に対し、`horizontal mask`をANDして、マスクを適用します。

```
enemy board  horizontal mask  masked board
 00000000       01111110        00000000
 00000000       01111110        00000000
 00000000       01111110        00000000
 00001000  AND  01111110   =    00001000
 00010000       01111110        00010000
 00000000       01111110        00000000
 00000000       01111110        00000000
 00000000       01111110        00000000
```

そしてひっくり返せる石があるか見るために、`player board`を左へビットシフトさせ、`masked board`とANDします。

```
player board     masked board       tmp
  00000000         00000000       00000000
  00000000         00000000       00000000
  00000000         00000000       00000000
  00100000   AND   00001000   =   00000000
  00010000         00010000       00010000
  00000000         00000000       00000000
  00000000         00000000       00000000
  00000000         00000000       00000000
```

この上記処理をすることでplayerの石に隣接している敵の石の場所にのみbitが立っている状態になります。つまりひっくり返すことができる可能性のある石の場所にのみbitが立っている状態です。

次からは`tmp`をビットシフトして`masked board`とANDを行い、ビットシフト前の`tmp`にORをして更新していきます。
この処理はひっくり返すことができる最大の数である6回行います(端と端に置いた場合が最大)。

```
    tmp          masked board          tmp
  00000000         00000000         00000000
  00000000         00000000         00000000
  00000000         00000000         00000000
  00000000   AND   00001000   OR=   00000000
  00100000         00010000         00010000
  00000000         00000000         00000000
  00000000         00000000         00000000
  00000000         00000000         00000000
```

最終的には以下のようになります。
この状態では**playerの石の左側にあるひっくり返すことができる可能性のある石が列挙されているのみ**になります。

```
    tmp   
  00000000
  00000000
  00000000
  00000000
  00010000
  00000000
  00000000
  00000000
```

最後に置ける場所のみにbitを立ってる状態にしていきます。
まず、`player board`と`enemy board`をORをしてどちらの石も置いてある盤面を用意します。

```
player board    enemy board   current board
  00000000       00000000       00000000
  00000000       00000000       00000000
  00000000  OR   00000000   =   00000000
  00010000       00001000       00011000
  00001000       00010000       00011000
  00000000       00000000       00000000
  00000000       00000000       00000000
  00000000       00000000       00000000
```

次に`current board`をNOTして現状の盤面で何も石が置かれいていない場所のみにbitが立っている`empty board`を作成します。

```
current board    empty board
  00000000        11111111
  00000000        11111111
  00000000  NOT=  11111111
  00011000        11100111
  00011000        11100111
  00000000        11111111
  00000000        11111111
  00000000        11111111
```

`tmp`を左にビットシフトしてひっくり返すことができる石の左側に移動させます。これが挟める可能性のある場所にのみbitが立っている状態です。
そして、ビットシフトさせた盤面に対して、`empty board`をANDすることで石を置ける場所のみにbitが立っている状態が完成します。

```
    tmp          empty board    legal board
  00000000         11111111       00000000
  00000000         11111111       00000000
  00000000         11111111       00000000
  00000000   AND   11100111   =   00000000
  00100000         11100111       00100000
  00000000         11111111       00000000
  00000000         11111111       00000000
  00000000         11111111       00000000
```
これを8方向全てに行うことで列挙が完了します。
左右であれば`horizontal mask`、上下であれば`vertical mask`、斜めであれば`allside mask`を使って処理をしてください。

###ひっくり返す処理
次はひっくり返す処理についてです。

まず、石を置きたい場所にのみbitが立っている盤面を用意します。例では(5,3)に置く想定とします。

```
puted mask
 00000000
 00000000
 00000000
 00000100
 00000000
 00000000
 00000000
 00000000
```

次に左へ1ビットシフトさせ、`horizontal mask`とANDをします。

```
puted mask  horizontal mask     tmp
 00000000      01111110       00000000
 00000000      01111110       00000000
 00000000      01111110       00000000
 00001000 AND  01111110   =   00001000
 00000000      01111110       00000000
 00000000      01111110       00000000
 00000000      01111110       00000000
 00000000      01111110       00000000
```

`tmp`に対して敵の盤面をANDします。

```
    tmp       empty board   reverse tmp
 00000000      00000000       00000000
 00000000      00000000       00000000
 00000000      00000000       00000000
 00001000 AND  00001000   =   00001000
 00000000      00010000       00000000
 00000000      00000000       00000000
 00000000      00000000       00000000
 00000000      00000000       00000000
```

これ以降は`tmp`をさらにビットシフトさせ`empty board`とANDし、結果を`reverse tmp`にORして更新する処理を`tmp AND empty board`が0になるまで繰り返します。`tmp AND empty board`が0になるということは連続した敵の石が無くなったことを意味します。

最後に繰り返し処理を抜けたタイミングで、`player board`と`tmp`をANDします。

```
player board       tmp          reverse tmp
  00000000       00000000        00000000
  00000000       00000000        00000000
  00000000       00000000        00000000
  00010000  AND  00010000  =     00010000
  00001000       00000000        00000000
  00000000       00000000        00000000
  00000000       00000000        00000000
  00000000       00000000        00000000
```
もしこの結果が0以外であれば敵の石を自分の石で挟んでいるということなので最終的なひっくり返す石として確定させます。今回は0以外なので`reverse`にORをして更新して確定させます。`reverse`はひっくり返せる場所にのみビットが立っている変数です。

```
reverse tmp     reverse
 00000000       00000000
 00000000       00000000
 00000000       00000000
 00010000  OR=  00010000
 00000000       00000000
 00000000       00000000
 00000000       00000000
 00000000       00000000
```

1方向が終了したら他の方向にも行います。

この`reverse`の部分ができてしまえばあとは下記の論理演算のみでひっくり返すことができます。`^`はNOT、`|`はORという意味です。
`player board ^= puted mask | reverse`
`enemy board ^= reverse`

説明は以上となります。これ以外にもパスの処理・置けるかどうかのチェックなどがありますが、今までにご紹介した処理を応用すれば実装できます。

##実践
ここからは実際にプログラムに落とし込んだ物をご紹介します。
実装自体は私が比較的慣れているSwiftで書いていますが、速さを求めるならAVXを使うことで高速化ができるC++で書くのが最適だと思います。実際に競プロで使おうとした際は、C++で書いていました。

###石を置く
```swift
func put(x: String, y: String) {
    guard let xInt = Int(x) else { return }
    guard let yInt = Int(y) else { return }
    var putedMask: UInt64 = 0x8000000000000000
        
    putedMask = putedMask >> xInt
    putedMask = putedMask >> (yInt * 8)
        
    if isCanPut(putedMask: putedMask) {
        doReverse(putedMask: putedMask)
        nextTurn()
            
        if shouldPass {
            print("置けるマスがないためパスされます")
            nextTurn()
        }
    } else {
        print("(" + x + ", " + y + ")には置けません")
    }
}
```

###置ける場所を列挙する
```swift
// 8方向分の置ける場所を列挙して返す
func makeLegalBoard(playerBoard: UInt64, enemyBoard: UInt64) -> UInt64 {
    var legalBoard = getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP)
    legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP_RIGHT)
    legalBoard |= getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .RIGHT)
    legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM_RIGHT)
    legalBoard |= getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM)
    legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM_LEFT)
    legalBoard |= getCanPutPoint(mask: horizontalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .LEFT)
    legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP_LEFT)
        
    return legalBoard
}

// direction方向の置ける場所にビットが立っている盤面を返す
func getCanPutPoint(mask: UInt64, playerBoard: UInt64, enemyBoard: UInt64, direction: DIRECTION) -> UInt64 {
    let masked = mask & enemyBoard
    var tmp: UInt64 = masked & getStridedBoard(target: playerBoard, direction: direction)
    for _ in 0..<5 {
        tmp |= masked & getStridedBoard(target: tmp, direction: direction)
    }
    return ~(playerBoard | enemyBoard) & getStridedBoard(target: tmp, direction: direction)
}

// targetをdirectionの方向にビットシフトさせる
func getStridedBoard(target: UInt64, direction: DIRECTION) -> UInt64 {
    return direction.stride.isNegativeNumber ? target << direction.stride.absValue : target >> direction.stride.absValue
}
```

###ひっくり返す処理

```swift
// 実際にひっくり返す処理
func doReverse(putedMask: UInt64) {
    var reversed: UInt64 = 0
    for i in 0..<8 {
        var revTmp: UInt64 = 0
        var tmp: UInt64 = moveTo(target: putedMask, direction: DIRECTION(rawValue: i)!)
        while (tmp != 0) && ((tmp & enemyCell) != 0) {
            revTmp |= tmp
            tmp = moveTo(target: tmp, direction: DIRECTION(rawValue: i)!)
        }
            
        if (tmp & playerCell) != 0 {
            reversed |= revTmp
        }
    }
    playerCell ^= putedMask | reversed
    enemyCell ^= reversed
}

// targetをDIRECTION方向に移動させた上でマスクする
func moveTo(target: UInt64, direction: DIRECTION) -> UInt64 {
    let stridedBoard = getStridedBoard(target: target, direction: direction)
    return stridedBoard & direction.sideMask.rawValue
}
```

##終わりに
いかがだったでしょうか？
今回は通常の実装との性能比較は行っていませんでしたが、なんだか速くなりそうな気がしますよね笑

Bitを使うことによる利点は**並列で求めることができる点**だと思っています。
オセロでいうのであれば、置ける場所を列挙するという処理はBitboardを使うと全ての石に対して同時に求めることができますが、配列ではそうもいきません。

実際にプロコンでプログラムを書いていたときは、陣取りゲームだったのですがBitboardで表現するようにしたところ100倍くらい処理速度が速くなりました笑(C++でAVXで最適化した上での処理速度です)
そのときはちょっと感動してしまったのを覚えています。

今回はその感動を少し思い出したので書いてみました。
Bitboardの発展系としてMagic Bitboardなるものが存在しています。調べてみると面白いかもしれません。

以上となります。ご閲覧ありがとうございました。