前々から勉強しようと思っていた、ビットボードについて勉強しました。
参考にしたのはこの記事
https://qiita.com/sensuikan1973/items/459b3e11d91f3cb37e43
勉強がてらpythonでコードを書いてみたので、今回はそのコードの公開と参考にした記事（ほぼ丸コピ）との変更点などを書いていきます。
この記事の目的は相変わらず以下の三つ。
- 詳しい方に添削して欲しい
- 気になる方へのコードの開示
- 自分の理解を深める
想定読者はpythonがある程度できて、オセロのビットボード実装に興味がある方です。
ビットボードとは
ビットボードとは「盤面をビットで表したもの」です。
盤面:
ビットボード:
黒:1111110000111000000000001000000011000100110000001111110000000000
白:0000001111000111111111110111111100111011001111110000001111111111
左上から右下に、64マスの情報を64bitに
コンピューターは0と1の情報（bit）で動くので、ビットボードで実装するのが効率がいいのです。
詳しい解説は参考にした記事を見てください。（丸投げ）
どんなプログラムを作ったん？
棋譜（F5D6形式）を受け取って、終局までの「盤面」と終局時の「結果（石数、勝者）」を返すプログラムです。
基本的に棋譜は「正しい棋譜」を想定しています。
このプログラムは何かに役立つものというよりは、実際に動いていることを確認するものです。
作った目的
先述の通り、勉強がてら。
参考にした記事ではSwift4でコードが書かれていたので、ほぼ丸コピでpythonで書きました。
コード
早速、書いたコード紹介。
#ビットボードでオセロ(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メソッド
コード
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関数
コード
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で棋譜変換プログラムを自作しました)
しかし、ビットボードで実装した方がより直感的に、シンプルに書けて、また様々な応用が効きやすいと感じました。
今後機会があれば、ビットボードを使用して何かオセロのプログラムを作っていきたいです。
では、今回はつらつらと書きたいことだけ書く自己中記事でしたが、これで終わりにします。
またね！