前々から勉強しようと思っていた、ビットボードについて勉強しました。
参考にしたのはこの記事
https://qiita.com/sensuikan1973/items/459b3e11d91f3cb37e43
勉強がてらpythonでコードを書いてみたので、今回はそのコードの公開と参考にした記事（ほぼ丸コピ）との変更点などを書いていきます。
この記事の目的は相変わらず以下の三つ。
- 詳しい方に添削して欲しい
- 気になる方へのコードの開示
- 自分の理解を深める
想定読者はpythonがある程度できて、オセロのビットボード実装に興味がある方です。
ビットボードとは
ビットボードとは「盤面をビットで表したもの」です。
盤面:
ビットボード:
黒:1111110000111000000000001000000011000100110000001111110000000000
白:0000001111000111111111110111111100111011001111110000001111111111
左上から右下に、64マスの情報を64bitに
コンピューターは0と1の情報（bit）で動くので、ビットボードで実装するのが効率がいいのです。
詳しい解説は参考にした記事を見てください。（丸投げ）
どんなプログラムを作ったん？
棋譜（F5D6形式）を受け取って、終局までの「盤面」と終局時の「結果（石数、勝者）」を返すプログラムです。
基本的に棋譜は「正しい棋譜」を想定しています。
このプログラムは何かに役立つものというよりは、実際に動いていることを確認するものです。
作った目的
先述の通り、勉強がてら。
参考にした記事ではSwift4でコードが書かれていたので、ほぼ丸コピでpythonで書きました。
コード
早速、書いたコード紹介。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 |
#ビットボードでオセロ(Python version) #グローバル変数 BLACK_TURN = 100 WHITE_TURN = -100 #board class class Board: def __init__(self): #BLACK_TURN = 100 #WHITE_TURN = -100 #MARK: Properties #var nowTurn : Int # 現在の手番 #var nowIndex : Int # 現在何手目か #var playerBoard : UInt64 # player側ビットボード #var opponentBoard : UInt64 # opponent側ビットボード self.nowTurn = BLACK_TURN self.nowIndex = 1 #一般的な初期配置を指定 self.playerBoard = 0x0000000810000000 self.opponentBoard = 0x0000001008000000 #@brief 着手可否の判定 #@param put 置いた位置のみにフラグが立っている64ビット #@return 着手可能ならtrue def canPut(self,put): #着手可能なマスにフラグが立っている合法手ボードを生成 legalBoard = makeLegalBoard(self) #今回の着手が、その合法手ボードに含まれれば着手可能 return (put & legalBoard) == put #@brief 着手し,反転処理を行う #@param put: 着手した場所のみにフラグが立つ64ビット def reverse(self,put): #着手した場合のボードを生成 rev = 0 for k in range(8): rev_ = 0 mask = transfer(put,k) while (mask != 0) and ((mask & self.opponentBoard) != 0): rev_ |= mask mask = transfer(mask,k) if (mask & self.playerBoard) != 0: rev |= rev_ #反転する self.playerBoard ^= put | rev self.opponentBoard ^= rev #現在何手目かを更新 self.nowIndex = self.nowIndex + 1 #@brief パス判定 (= プレイヤーのみが置けない時) #@return パスならtrue def isPass(self): #手番側の合法手ボードを生成 playerLegalBoard = makeLegalBoard(self) #相手側の合法手ボードを生成 tmpBoard = Board() tmpBoard.nowTurn = self.nowTurn tmpBoard.nowIndex = self.nowIndex tmpBoard.playerBoard = self.opponentBoard tmpBoard.opponentBoard = self.playerBoard opponentLegalBoard = makeLegalBoard(tmpBoard) #手番側だけがパスの場合 return playerLegalBoard == 0x0000000000000000 and opponentLegalBoard != 0x0000000000000000 #@brief 終局判定 (= 二人ともが置けない時) #@return 終局ならtrue def isGameFinished(self): playerLegalBoard = makeLegalBoard(self) tmpBoard = Board() tmpBoard.nowTurn = self.nowTurn tmpBoard.nowIndex = self.nowIndex tmpBoard.playerBoard = self.opponentBoard tmpBoard.opponentBoard = self.playerBoard opponentLegalBoard = makeLegalBoard(tmpBoard) # 両手番とも置く場所がない場合 return playerLegalBoard == 0x0000000000000000 and opponentLegalBoard == 0x0000000000000000 #@brief 手番の入れ替え def swapBoard(self): #ボードの入れ替え tmp = self.playerBoard self.playerBoard = self.opponentBoard self.opponentBoard = tmp #色の入れ替え self.nowTurn = self.nowTurn * -1 #@brief 結果を取得する #@return blackScore 黒石の数 #@return whiteScore 白石の数 #@return winner 勝ち手番 def getResult(self): #石数を取得 blackScore = bitCount(self.playerBoard) whiteScore = bitCount(self.opponentBoard) if self.nowTurn == WHITE_TURN : tmp = blackScore blackScore = whiteScore whiteScore = tmp # 勝敗情報を取得 winner = "黒番" isWhiteWin = whiteScore >= blackScore if isWhiteWin : winner = "白番" return (blackScore, whiteScore, winner) #@brief ビットボードを視覚的に表示 def BitTOBoard(self): playerBoard = self.playerBoard opponentBoard = self.opponentBoard digits = 64 #ケタ数 #定数4がplayer側,7がopponent側の石 #ビットボード(64ビット)->64の要素を持つリスト l_player = [4 * int(i) for i in format(playerBoard,'b').zfill(digits)] l_opponent = [7 * int(i) for i in format(opponentBoard,'b').zfill(digits)] #両者を足す l_board = list(map(lambda x,y: x+y, l_player, l_opponent)) ll_board = [] #2次元リスト size = 8 for n in range(size): #１列ごとll_boardに格納 ll_board.append(l_board[size * n: size * n + size]) for n in range(8): str_board = '' for i in ll_board[n]: str_board += str(i) print(str_board) #board class 終了 #@brief 反転箇所を求める #@param put 着手した場所のビット値 #@param k 反転方向(8つ) #@return 反転箇所にフラグが立っている64ビット def transfer(put,k): if k == 0: #上 return (put << 8) & 0xffffffffffffff00 elif k == 1: #右上 return (put << 7) & 0x7f7f7f7f7f7f7f00 elif k == 2: #右 return (put >> 1) & 0x7f7f7f7f7f7f7f7f elif k == 3: #右下 return (put >> 9) & 0x007f7f7f7f7f7f7f elif k == 4: #下 return (put >> 8) & 0x00ffffffffffffff elif k == 5: #左下 return (put >> 7) & 0x00fefefefefefefe elif k == 6: #左 return (put << 1) & 0xfefefefefefefefe elif k == 7: #左上 return (put << 9) & 0xfefefefefefefe00 else: return 0 #@brief 手番側の合法手ボードを生成 #@param board Boardインスタンス #@return Uint64 playerから見て、置けるマスのみにフラグが立っている64ビット def makeLegalBoard(board): #左右端の番人 horizontalWatchBoard = board.opponentBoard & 0x7e7e7e7e7e7e7e7e #上下端の番人 verticalWatchBoard = board.opponentBoard & 0x00FFFFFFFFFFFF00 #全辺の番人 allSideWatchBoard = board.opponentBoard & 0x007e7e7e7e7e7e00 #空きマスのみにビットが立っているボード blankBoard = ~(board.playerBoard | board.opponentBoard) #隣に相手の色があるかを一時保存する #var tmp : UInt64 #返り値 #legalBoard : UInt64 #8方向チェック #・一度に返せる石は最大6つ ・高速化のためにforを展開(ほぼ意味ないけどw) #左 tmp = horizontalWatchBoard & (board.playerBoard << 1) tmp |= horizontalWatchBoard & (tmp << 1) tmp |= horizontalWatchBoard & (tmp << 1) tmp |= horizontalWatchBoard & (tmp << 1) tmp |= horizontalWatchBoard & (tmp << 1) tmp |= horizontalWatchBoard & (tmp << 1) legalBoard = blankBoard & (tmp << 1) #右 tmp = horizontalWatchBoard & (board.playerBoard >> 1) tmp |= horizontalWatchBoard & (tmp >> 1) tmp |= horizontalWatchBoard & (tmp >> 1) tmp |= horizontalWatchBoard & (tmp >> 1) tmp |= horizontalWatchBoard & (tmp >> 1) tmp |= horizontalWatchBoard & (tmp >> 1) legalBoard |= blankBoard & (tmp >> 1) #上 tmp = verticalWatchBoard & (board.playerBoard << 8) tmp |= verticalWatchBoard & (tmp << 8) tmp |= verticalWatchBoard & (tmp << 8) tmp |= verticalWatchBoard & (tmp << 8) tmp |= verticalWatchBoard & (tmp << 8) tmp |= verticalWatchBoard & (tmp << 8) legalBoard |= blankBoard & (tmp << 8) #下 tmp = verticalWatchBoard & (board.playerBoard >> 8) tmp |= verticalWatchBoard & (tmp >> 8) tmp |= verticalWatchBoard & (tmp >> 8) tmp |= verticalWatchBoard & (tmp >> 8) tmp |= verticalWatchBoard & (tmp >> 8) tmp |= verticalWatchBoard & (tmp >> 8) legalBoard |= blankBoard & (tmp >> 8) #右斜め上 tmp = allSideWatchBoard & (board.playerBoard << 7) tmp |= allSideWatchBoard & (tmp << 7) tmp |= allSideWatchBoard & (tmp << 7) tmp |= allSideWatchBoard & (tmp << 7) tmp |= allSideWatchBoard & (tmp << 7) tmp |= allSideWatchBoard & (tmp << 7) legalBoard |= blankBoard & (tmp << 7) #左斜め上 tmp = allSideWatchBoard & (board.playerBoard << 9) tmp |= allSideWatchBoard & (tmp << 9) tmp |= allSideWatchBoard & (tmp << 9) tmp |= allSideWatchBoard & (tmp << 9) tmp |= allSideWatchBoard & (tmp << 9) tmp |= allSideWatchBoard & (tmp << 9) legalBoard |= blankBoard & (tmp << 9) #右斜め下 tmp = allSideWatchBoard & (board.playerBoard >> 9) tmp |= allSideWatchBoard & (tmp >> 9) tmp |= allSideWatchBoard & (tmp >> 9) tmp |= allSideWatchBoard & (tmp >> 9) tmp |= allSideWatchBoard & (tmp >> 9) tmp |= allSideWatchBoard & (tmp >> 9) legalBoard |= blankBoard & (tmp >> 9) #左斜め下 tmp = allSideWatchBoard & (board.playerBoard >> 7) tmp |= allSideWatchBoard & (tmp >> 7) tmp |= allSideWatchBoard & (tmp >> 7) tmp |= allSideWatchBoard & (tmp >> 7) tmp |= allSideWatchBoard & (tmp >> 7) tmp |= allSideWatchBoard & (tmp >> 7) legalBoard |= blankBoard & (tmp >> 7) return legalBoard #bit.swift #@brief 座標をbitに変換する #@param x 横座標(A~H) #@param y 縦座標(1~8) #@return 着手箇所のみにフラグが立っている64ビット def coordinateToBit(x, y): mask = 0x8000000000000000 #X方向へのシフト if x == "A": pass elif x == "B": mask = mask >> 1 elif x == "C": mask = mask >> 2 elif x == "D": mask = mask >> 3 elif x == "E": mask = mask >> 4 elif x == "F": mask = mask >> 5 elif x == "G": mask = mask >> 6 elif x == "H": mask = mask >> 7 else: pass #Y方向へのシフト intY = int(y) mask = mask >> ( (intY - 1) * 8) return mask #@brief ビットカウント #@param num 64ビット #@return 立ってるフラグの数[Int] def bitCount(num): BOARDSIZE = 64 mask = 0x8000000000000000 count = 0 for _ in range(BOARDSIZE) : if mask & num != 0 : count += 1 mask = mask >> 1 return count ################ ##### main ##### ################ def main(): """ メインルーチン """ kifu = input('棋譜:') board = Board() for n in range(int(len(kifu)/2)): put = coordinateToBit(kifu[2*n],kifu[2*n + 1]) #canPutなら打つ if board.canPut(put) : print('canPut') board.reverse(put) #isPassなら手番を入れ替えて打つ elif board.isPass(): print('isPass') board.swapBoard() board.reverse(put) board.BitTOBoard() #盤面を表示 #GameFinishedなら終了、違うなら手番を入れ替えて継続 if board.isGameFinished() : print('isGameFinished') result = board.getResult() print(result) else: board.swapBoard() if __name__ == '__main__': main() |
主な変更点、追記箇所
変更点
プログラミング言語の違いがあるので細かい部分を変更しました。
- var,Uint64などの定義は不要なので消去
- 関数の定義の仕方（func→def）
- pythonにはswitch関数がないのでif,elifで代用
- グローバル変数とローカル変数の扱いが違う（理解しきれてない）
- クラスの扱いも微妙に違う(63〜67行目の右辺にselfを追加)
追記箇所
正常に動くか視覚的に確認できるようコードを追記しました。
実際に動かした様子がこちら。
棋譜を入力すると、石を返していきます。
（0は空きマス、4は打った側の石、7は打たれた側の石）
パスになると、ちゃんと「isPass」と表示されていました。
実際の棋譜と終局図、石差、勝者全て一致しています。
このように動かすために以下のように追記しました。
- BitTOBoardメソッドで盤面を表示
- main関数を定義
BitTOBoardメソッド
コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def BitTOBoard(self): playerBoard = self.playerBoard opponentBoard = self.opponentBoard digits = 64 #ケタ数 #定数4がplayer側,7がopponent側の石 #ビットボード(64ビット)->64の要素を持つリスト l_player = [4 * int(i) for i in format(playerBoard,'b').zfill(digits)] l_opponent = [7 * int(i) for i in format(opponentBoard,'b').zfill(digits)] #両者を足す l_board = list(map(lambda x,y: x+y, l_player, l_opponent)) ll_board = [] #2次元リスト size = 8 for n in range(size): #１列ごとll_boardに格納 ll_board.append(l_board[size * n: size * n + size]) for n in range(8): str_board = '' for i in ll_board[n]: str_board += str(i) print(str_board) |
Boardクラスのメソッドです。
ごちゃごちゃと変換していきビットボードを盤面情報に変換してprintで表示します。
次のように変換していきます。（気になる方は表示をクリック）
表示
main関数
コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
def main(): """ メインルーチン """ kifu = input('棋譜:') board = Board() for n in range(int(len(kifu)/2)): put = coordinateToBit(kifu[2*n],kifu[2*n + 1]) #canPutなら打つ if board.canPut(put) : print('canPut') board.reverse(put) #isPassなら手番を入れ替えて打つ elif board.isPass(): print('isPass') board.swapBoard() board.reverse(put) board.BitTOBoard() #盤面を表示 #GameFinishedなら終了、違うなら手番を入れ替えて継続 if board.isGameFinished() : print('isGameFinished') result = board.getResult() print(result) else: board.swapBoard() |
Boardクラスのメソッドや関数をうまく使って動かします。
順番を考えるのに多少頭を使いました。
感想
あまりビットボードに関わる部分は変更しませんでしたが、pythonの勉強にはなりました。
ちゃんとコード全体を理解するように努めたので、ビットボードのおおよその使い方は理解できました。
合法手ボードの生成（makeLegalBoard関数）を理解するのが一番難しかったですが、なんとか理解できました。
実は棋譜を受け取って盤面を表示させるのは以前完全自作プログラムを作りました。(pythonで棋譜変換プログラムを自作しました)
しかし、ビットボードで実装した方がより直感的に、シンプルに書けて、また様々な応用が効きやすいと感じました。
今後機会があれば、ビットボードを使用して何かオセロのプログラムを作っていきたいです。
では、今回はつらつらと書きたいことだけ書く自己中記事でしたが、これで終わりにします。
またね！