LoginSignup
6
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@watergreat31

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

Last updated at Posted at 2020-12-18

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

Bitboardとは

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

2進数で盤面を表現するには

本記事の題にもある通り、本記事全体を通してオセロを例にして説明してこうと思います。

通常オセロのプログラムを書く際、どのように盤面を表現する事が多いでしょうか？
スクリーンショット 2020-12-17 21.07.23.png
ぱっと思いつくのだと、こんな感じで盤面の大きさ分の2次元配列に黒石・白石・置いてないという状態を数字などに置き換えて代入して表現するものが多いと思います。

スクリーンショット 2020-12-17 21.47.44.png

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

スクリーンショット 2020-12-17 21.50.43.png　　スクリーンショット 2020-12-17 21.52.30.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++で書いていました。

石を置く

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 + ")には置けません")
    }
}

置ける場所を列挙する

// 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
}

ひっくり返す処理

// 実際にひっくり返す処理
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なるものが存在しています。調べてみると面白いかもしれません。

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

6
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?