Pythonで〇×ゲームのAIを一から作成する その211 BitBoard の座標から (x, y) の座標への変換処理とビット演算を利用した勝敗判定の実装

目次と前回の記事

Python のバージョンとこれまでに作成したモジュール

本記事のプログラムは Python のバージョン 3.13 で実行しています。また、numpy のバージョンは 2.3.5 です。

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
mbtest.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

前回の記事のおさらい

前回の記事では 各マスに特定のマークが存在するかどうか を 1 ビットで表現 するという、ビットボード でゲーム盤を表現する BitBoard クラスの定義を開始しました。下記は定義する必要があるメソッドの一覧です。

抽象メソッド	処理
getmark_by_move(move)	move のマスのマークを返す
setmark_by_move(move, mark)	move のマスに mark を代入する
xy_to_move(x, y)	(x, y) のマスのゲーム盤のクラスの座標を返す
move_to_xy(move)	move のマスの x, y の座標を返す
judge(last_turn, last_move, move_count)	勝敗判定を計算して返す
count_markpats(turn, last_turn)	局面のマークのパターンを返す
calc_legal_moves()	合法手の一覧を表す、ゲーム盤のクラスの座標を要素とする list を返す
calc_same_hashables(move)	同一局面のハッシュ可能な値の一覧と move の同一局面に対応する座標を計算する
board_to_str()	ゲーム盤を表す文字列を返す
board_to_hashable()	ゲーム盤を表すハッシュ可能な値を返す

前回の記事では __init__ メソッドと、上記の中の以下のメソッドを定義しました。

• (x, y) の座標を BitBoard の座標 に変換する xy_to_move
• BitBoard の座標のマスを参照する getmark_by_move
• BitBoard の座標にマークを配置または削除する setmark_by_move

BitBoard の座標から (x, y) の座標への変換

今回の記事では最初に前回の記事で実装を後回しにしていた BitBoard の座標 から (x, y) の座標への変換 を行う move_to_xy メソッドを実装します。

move_to_xy が行う処理は、下記の手順で処理を行う xy_to_move メソッドの逆 です。

1. (x, y) の座標 を x + self.BOARD_SIZE * y によって下図の 数値座標に変換 する
2. 1 << 数値座標 という シフト演算 で 数値座標を BitBoard の座標に変換 する

従って、move_to_xy は 上記の逆 の 下記の手順の処理 を行えば良いことがわかります。

1. BitBoard の座標 を 数値座標に変換 する
2. 数値座標 を (x, y) の座標に変換 する

上記の 手順 2 の処理 は数値座標で座標を表現する List1dBoard クラスの、下記の xy_to_move メソッドと同じ 処理です。忘れた方は以前の記事¹を復習して下さい。

def move_to_xy(self, move):
    return move // self.BOARD_SIZE, move % self.BOARD_SIZE    

対数による計算方法

前回の記事で説明したように 1 << n = 2 ** n なので、上記の手順 1 は BitBoard の座標 を $\boldsymbol{b}$、数値座標 を $\boldsymbol{n}$ とした場合に、$\boldsymbol{b = 2^n}$ となる $\boldsymbol{n}$ を計算 するという処理になります。

このような $\boldsymbol{x}$ を何乗 すれば $\boldsymbol{y}$ になるか という計算を 対数（logarithm） と呼び、数学では $\boldsymbol{log_x{y}}$ のように記述します。また、対数の計算では $\boldsymbol{x}$ を 底（てい） と呼びます。

例えば $\boldsymbol{2^5 = 32}$ なので $\boldsymbol{log_2{32} = 5}$ となります。

参考までに 対数 の Wikipedia のリンクを下記に示します。

Python では下記のプログラムのように、底を 2 とする 対数 $\boldsymbol{log_2{y}}$ を数学に関する 組み込みモジュール math で定義された log2 という関数で計算することができ、実行結果から $\boldsymbol{log_2{32} = 5}$ が 正しく計算されている ことが確認できます。

from math import log2

print(log2(32))

実行結果

5.0

math モジュールの log2 の詳細については下記のリンク先を参照して下さい。

math モジュールには他にもいくつかの対数を計算する関数が定義されており、$x$ を底とする $log_x{y}$ は math モジュールの log という関数で log(y, x) のように記述することで計算できます。

下記は log で $log_2{32}$ を計算するプログラムです。

from math import log

print(log(32, 2))

実行結果

5.0

他にも底を 10 とする常用対数を計算する log10 などが定義されています。

なお、log で底を表す実引数を省略した場合はネイピア数と呼ばれる $e = 約 2.71828$ が底として指定されたものとみなして計算が行われます。ネイピア数は数学では非常に重要な数値で、ネイピア数を底とする対数を自然対数と呼び、自然対数を計算する記号を $log$ と区別して $ln$ のように記述することがあります。

下記は math モジュールの log の詳細と、Wikipedia の ネイピア数 のリンクです。

log2 を利用した move_to_xy の定義

先程の log2(32) の実行結果に 5.0 が表示 されたことからわかるように、log2 の返り値 は整数を表す int 型ではなく、浮動小数点数 を表す float 型 の数値になります。また、下記のプログラムの実行結果のように、シフト演算 で すらず数を表す数値 に float 型 の数値 を記述するとエラーが発生 します。

print(1 << 5.0)

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[3], line 1
----> 1 print(1 << 5.0)

TypeError: unsupported operand type(s) for <<: 'int' and 'float'

エラーメッセージは左シフトを計算する << 演算子（operand）では int 型と float 型 に対する演算を 行うことはできない（unsupported）という意味を表します。

従って、log2 を利用 して計算を行う move_to_xy メソッドを定義する際には、下記のプログラムのように 組み込み関数 int を利用して log2 の計算結果 を int 型に変換する必要がある 点に注意が必要です。

• 4 行目：先程説明した方法で log2 と組み込み関数 int を利用して BitBoard の座標を int 型の数値座標に変換する
• 5 行目：List1dBoard クラスの move_to_xy と同様の方法で数値座標から (x, y) の座標を計算して返り値として返す

1  from marubatsu import BitBoard
2  
3  def move_to_xy(self, move):
4      move = int(log2(move))
5      return move // self.BOARD_SIZE, move % self.BOARD_SIZE    
6  
7  BitBoard.move_to_xy = move_to_xy

行番号のないプログラム

from marubatsu import BitBoard

def move_to_xy(self, move):
    move = int(log2(move))
    return move // self.BOARD_SIZE, move % self.BOARD_SIZE    

BitBoard.move_to_xy = move_to_xy

下記は 3 x 3 の〇×ゲームの 各マス に対して (x, y) の座標 を xy_to_move で BitBoard の座標に変換 した値と、その値を move_to_xy で (x, y) の座標に戻した値を表示 するプログラムです。実行結果から いずれの場合も元の (x, y) 座標が表示 されるので、正しい計算が行われることが確認 できます。

bb = BitBoard()
for x in range(3):
    for y in range(3):
        print(f"({x}, {y})")
        move = bb.xy_to_move(x, y)
        print(f"xy_to_move: 0b{move:09b}")
        x2, y2 = bb.move_to_xy(move)
        print(f"move_to_xy: ({x2}, {y2})")
        print()

実行結果

(0, 0)
xy_to_move: 0b000000001
move_to_xy: (0, 0)

(0, 1)
xy_to_move: 0b000000010
move_to_xy: (0, 1)

(0, 2)
xy_to_move: 0b000000100
move_to_xy: (0, 2)

(1, 0)
xy_to_move: 0b000001000
move_to_xy: (1, 0)

(1, 1)
xy_to_move: 0b000010000
move_to_xy: (1, 1)

(1, 2)
xy_to_move: 0b000100000
move_to_xy: (1, 2)

(2, 0)
xy_to_move: 0b001000000
move_to_xy: (2, 0)

(2, 1)
xy_to_move: 0b010000000
move_to_xy: (2, 1)

(2, 2)
xy_to_move: 0b100000000
move_to_xy: (2, 2)

対数を利用した move_to_xy の計算方法は、xy_to_move の逆の計算 を行うという方法なので、対数が何を行う計算であるか を理解できていれば わかりやすい方法 だと思います。

なお、move_to_xy を実装 したことで、前回の記事で実行するとエラーになると説明した count_linemark が True の場合 の setmark_by_move を実行できる ようになっています。

下記は count_linemark が True の BitBoard クラスのインスタンスを作成して 以下の処理を行う プログラムで、実行結果のように 正しい処理が行われる ことが確認できます。なお、count_linemark が False の場合の bb と区別できるように bb2 に代入しました。

• getmark_by_move で (0, 0) のマークを表示すると 空のマスを表す -1 が表示 される
• setmark_by_move で (0, 0) に 〇 のマークを配置 する
• getmark_by_move で (0, 0) のマークを表示すると 〇 を表す 0 が表示 される
• setmark_by_move で (0, 0) から マークを削除 する
• getmark_by_move で (0, 0) のマークを表示すると 空のマスを表す -1 が表示 される
• setmark_by_move で (0, 0) に × のマークを配置 する
• getmark_by_move で (0, 0) のマークを表示すると × を表す 1 が表示 される

bb2 = BitBoard(count_linemark=True)
move = bb2.xy_to_move(0, 0)
print(bb2.getmark_by_move(move))
bb2.setmark_by_move(move, bb2.CIRCLE)
print(bb2.getmark_by_move(move))
bb2.setmark_by_move(move, bb2.EMPTY)
print(bb2.getmark_by_move(move))
bb2.setmark_by_move(move, bb2.CROSS)
print(bb2.getmark_by_move(move))

実行結果

-1
0
-1
1

上記で 〇 を配置した後で、マークを削除してから × を配置するという順番で処理を行っているのには理由があります。

setmark_by_move は既にマークが配置されているかどうかのチェックを行わないので、下記のプログラムのように (0, 0) に 〇 を配置した後でマークを削除せずに × を配置するという、〇× ゲームのルールに違反する処理を行うと、bb.board[0] と bb.board[1] の両方の (0, 0) に対応するビットが 1 になってしまいます。getmark_by_move は最初に bb.board[0] を確認し、BitBoard の座標に対応するビットが 1 の場合は bb.CIRCLE を返す処理を行うので、この場合は 〇 を表す 0 が計算されます。

bb2 = BitBoard(count_linemark=True)
move = bb2.xy_to_move(0, 0)
print(bb2.getmark_by_move(move))
bb2.setmark_by_move(move, bb2.CIRCLE)
print(bb2.getmark_by_move(move))
bb2.setmark_by_move(move, bb2.CROSS)
print(bb2.getmark_by_move(move))

実行結果

-1
0
0

実は、筆者は最初は上記の処理を記述してしまい、× を配置したはずなのに 〇 を表す 0 が表示されてしまったことに対して原因に気づくまで少々混乱しました。

処理速度の計測

この後で説明する 別の方法と処理速度を比較できる ように、下記のプログラムで (0, 0) の座標に対する move_to_xy の処理速度を計測 しておきます。

move = bb.xy_to_move(0, 0)
%timeit bb.move_to_xy(move)

実行結果

178 ns ± 1.5 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

int 型の bit_length メソッドを利用した計算方法

BitBoard の座標 から 数値座標を計算 する 別の方法 として int 型 のデータに対する ビット演算 を行う bit_length メソッド を利用するという方法があります。bit_length を利用する方法は、対数を利用した方法と比較して わかりづらい という 欠点 が生じますが、処理速度が高速 になるという 利点 があります。

bit_length メソッドが行う処理

int 型などの組み込み型のデータ は 組み込みクラス から作成された インスタンス なので、属性やメソッド を持ちます。bit_length は int 型 のデータの メソッド の一つで、任意の整数 に対して bit_length メソッドを呼び出して 計算を行う ことができます。

最初にわかりやすい 正の整数に対する処理 を説明します。

bit_length はその名前の通り int 型のデータの ビットの長さ（length）を意味する ビット長 を計算するメソッドです。具体的には、正の整数 に対する bit_length メソッドは、値を 2 進数で表現 した際の 先頭の 0² を除いた部分 の ビットの長さ を計算します。

例えば 2 進数の 0b1010 は 1010 という 4 ビットの 2 進数で表現 されるので、下記のプログラムのように bit_length メソッドで計算を行うと 4 が計算 されます。

print(0b1010.bit_length())

実行結果

4

なお、int 型 のデータを 10 進数のリテラルで表記 した場合に bit_length を呼び出す際は、 . のように . の前に半角の空白を 1 つ以上入れる必要 があります。これは、空白を入れることで 小数点を表す . と、属性やメソッドを表す . を 区別できるようにする ためです。なお、2 進数のリテラル や、変数に代入 された int 型 のデータの場合は 直後の . を小数点の意味で利用することはない ので、. の前に空白を入れる必要はありません。

例えば 0b1010 は 10 進数の 10 なので、下記のプログラムのように記述して 10 に対する bit_length メソッドを呼び出すことができ、実行結果は上記と同じ 4 になります。

print(10 .length())

実行結果

4

下記のプログラムのように 10 と . の間に空白を入れずに記述して実行すると SyntaxError: invalid decimal literal というエラーが発生します。decimal とは 10 進数のことで、下記のプログラムでは . が小数点であるとみなされた結果、小数点以下に b などのアルファベットが記述された、不正な（invalid、間違った）10 進数のリテラルが記述されたとみなされてエラーが発生したことがわかります。

print(10.bit_length())

実行結果

  Cell In[11], line 1
    print(10.bit_length())
            ^
SyntaxError: invalid decimal literal

0 は 2 進数では 1 ビットの 0 で表記しますが、先頭の 0 をすべて除くと 0 ビット になるため、0 に対する bit_length は 0 になる点に注意が必要です。

また、負の整数 に対する bit_length は 絶対値に対する bit_length が計算 されます。

下記はそのことを確認するプログラムです。-10 に対する bit_length では、その 絶対値である 10 に対する bit_length の計算結果である 4 が計算 されます。

print(0 .bit_length())
print((-10).bit_length())

実行結果

0
4

-10 などの負の整数のリテラルに対する bit_length を計算する際は、上記の (-10) のように () を記述する必要がある点に注意が必要です。

その理由は符号を表す - 演算子が、属性やメソッドを表す . 演算子よりも優先順位が低いので、下記のプログラムの 1 行目のように記述すると 2 行目の計算が行われた結果 -4 が計算されるからです。

print(-10 .bit_length())
print(-(10 .bit_length()))

実行結果

-4
-4

bit_length メソッドの詳細については下記のリンク先を参照して下さい。

bit_length を利用した数値座標の計算

BitBoard の座標 は 1 << 数値座標 という 左シフト で計算され、その値を 2 進数で表記 すると 下記の表 のようになります。なお、BitBoard の座標の列 では、ビット長がわかりやすくなる ように 先頭の 0b は省略 しました。

(x, y)	数値座標	BitBoard の座標	ビット長
(0, 0)	0	1	1
(0, 1)	1	10	2
(0, 2)	2	100	2
(1, 0)	3	1000	3
(1, 1)	4	10000	4
(1, 2)	5	100000	5
(2, 0)	6	1000000	6
(2, 1)	7	10000000	7
(2, 2)	8	100000000	8

下記はそのことを確認するプログラムです。

bb = BitBoard()
for x in range(3):
    for y in range(3):
        move = bb.xy_to_move(x, y)
        print(f"({x}, {y}) | {y + x * bb.BOARD_SIZE} | {move:9b} | {move.bit_length()}")

実行結果

(0, 0) | 0 |         1 | 1
(0, 1) | 1 |        10 | 2
(0, 2) | 2 |       100 | 3
(1, 0) | 3 |      1000 | 4
(1, 1) | 4 |     10000 | 5
(1, 2) | 5 |    100000 | 6
(2, 0) | 6 |   1000000 | 7
(2, 1) | 7 |  10000000 | 8
(2, 2) | 8 | 100000000 | 9

BitBoard の座標 は上記の表からわかるように 数値座標が n の場合は n 番のビットが 1 でそれ以下の n - 1 ～ 0 番 までの n 個 の ビットが 0 である 2 進数で表現されます。そのため、その ビット長は n + 1 となります。

このことから、BitBoard の座標が move の 数値座標 は move.bit_length() - 1 という式で計算されることがわかります。

bit_length を利用した move_to_xy の定義

下記は bit_length を利用して move_to_xy を定義したプログラムです。

• 3 行目：上記で説明した方法で bit_length メソッドを利用して BitBoard の座標を int 型の数値座標に変換する

1  def move_to_xy(self, move):
2      move = move.bit_length() - 1
3      return move // self.BOARD_SIZE, move % self.BOARD_SIZE    
4
5  BitBoard.move_to_xy = move_to_xy

行番号のないプログラム

def move_to_xy(self, move):
    move = move.bit_length() - 1
    return move // self.BOARD_SIZE, move % self.BOARD_SIZE    

BitBoard.move_to_xy = move_to_xy

修正箇所

def move_to_xy(self, move):
-   move = int(log2(move))
+   move = move.bit_length() - 1
    return move // self.BOARD_SIZE, move % self.BOARD_SIZE    

BitBoard.move_to_xy = move_to_xy

先程と同じ下記のプログラムで move_to_xy が正しく動作するか どうかを検証します。実行結果から 正しい処理が行われることが確認 できます。

for x in range(3):
    for y in range(3):
        print(f"({x}, {y})")
        move = bb.xy_to_move(x, y)
        print(f"xy_to_move: 0b{move:09b}")
        x2, y2 = bb.move_to_xy(move)
        print(f"move_to_xy: ({x2}, {y2})")
        print()

実行結果

(0, 0)
xy_to_move: 0b000000001
move_to_xy: (0, 0)

(0, 1)
xy_to_move: 0b000000010
move_to_xy: (0, 1)

(0, 2)
xy_to_move: 0b000000100
move_to_xy: (0, 2)

(1, 0)
xy_to_move: 0b000001000
move_to_xy: (1, 0)

(1, 1)
xy_to_move: 0b000010000
move_to_xy: (1, 1)

(1, 2)
xy_to_move: 0b000100000
move_to_xy: (1, 2)

(2, 0)
xy_to_move: 0b001000000
move_to_xy: (2, 0)

(2, 1)
xy_to_move: 0b010000000
move_to_xy: (2, 1)

(2, 2)
xy_to_move: 0b100000000
move_to_xy: (2, 2)

下記のプログラムのように、move_to_xy の仮引数 move に 0b1001 のような複数のビットが 1 である BitBoard の座標ではない値を代入して実行しても、実行結果のようにエラーは発生せず、(1, 0) という座標が計算される点に注意が必要です。

print(bb.move_to_xy(0b1001))

実行結果

(1, 0)

これは、0b1001 が 4 ビットの 2 進数で表現されるので、bit_length によって 4 が計算されるからです。

move に代入された値が、1 のビットが一つだけである BitBoard の座標であるかどうかを判定する処理を記述することで、BitBoard の座標ではない値が move に代入された場合にエラーを発生させるようにプログラムを修正することもできますが、その判定処理の分だけ処理速度が遅くなるという欠点が生じます。

また、move_to_xy の move に代入する値を、「xy_to_move で計算した値」または、まだ実装していない「calc_legal_moves で計算した値」に限定することで、BitBoard の座標ではない値が move に代入されることが無いようにすることができるので、本記事ではそのような修正は行わないことにします。

処理速度の比較

下記のプログラムで (0, 0) の座標に対する上記の move_to_xy の 処理速度を計測 します。実行結果から 対数を利用 して計算する場合の 178 ns と比較 して 処理速度が高速化 することが確認できました。処理速度が高速化する理由は 対数の計算が複雑 であるのに対して bit_length による ビット長の計算が単純 なためです。

move = bb.xy_to_move(0, 0)
%timeit bb.move_to_xy(move)

実行結果

148 ns ± 1.38 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

前回の記事 で説明した特定のビットを 0 にするビット演算と同様に、上記の ビット長を計算 するという ビット演算を利用した処理 は 意味がわかりづらい という 欠点 が生じますが、処理速度が高速化 するという 利点 が得られます。〇× ゲームのプログラムでは 処理速度が非常に重要 なので、bit_length による move_to_xy の実装を採用 することにします。

勝敗判定の実装

次に、勝敗判定 を行う judge メソッドを実装します。judge メソッドでは ビットボードに対する処理が行われない ので、他のゲーム盤のクラスと同様 の 下記のプログラムで実装 することにし、judge メソッドの中から呼び出されている is_winner メソッドを ビットボードに対する処理を行うように実装 することにします。

from marubatsu import Marubatsu

def judge(self, last_turn, last_move, move_count):
    if move_count < self.BOARD_SIZE * 2 - 1:
        return Marubatsu.PLAYING
    # 直前に着手を行ったプレイヤーの勝利の判定
    if self.is_winner(last_turn, last_move):
        return last_turn
    # 引き分けの判定
    elif move_count == self.BOARD_SIZE ** 2:
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING  

BitBoard.judge = judge

is_winner メソッドが行う処理

is_winner メソッドでは、直前に行った着手の座標から決まる 行、列、対角線 のそれぞれに 直前の手番のプレイヤーのマークが並んでいるかどうか という判定を行います。

なお、count_linemark が True の場合の is_winner メソッドの処理は ListBoard クラスなどの 他のクラスと同じ なので 説明は省略 します。

count_linemark が False の場合の 直線上に特定のマークが並んでいるか どうかを判定する処理は、下記の表 のような方法で行ってきました。

クラス	処理の方法
ListBoard List1dBoard ArrayBoard	"".join で直線上のマークを 結合した文字列を計算 して判定する
NpBoard NpIntBoard	counter モジュールの Counter で 各マークの要素の数を数える
NpBoolBoard	np.count_nonzero で True の要素の数を数える

上記では、複数の文字列を結合 する処理や、複数の要素の数を数える という処理を行う必要がありますが、ビット演算 を利用することで 特定のマークが並んでいるか どうかの 判定処理 を 1 つの条件式だけで行う ことができるので、高速に処理を行う ことができます。

また、上記の方法ではいずれも ゲーム盤のサイズが大きくなる と、結合や数を数える 要素の数が増える ため 処理速度が遅く なりますが、ビット演算 で判定する場合は 1 回の条件式で判定 を行うのでゲーム盤のサイズが大きくなっても 処理速度は遅くなりません³。

具体例として取り上げる局面

言葉だけでの説明ではわかりづらいので、下図の局面を具体例 に挙げて説明します。

また、以下の説明での プログラムを簡潔に記述できる ように、〇 と × のビットボード を下記のプログラムのように 変数に代入しておく ことにします。

circlebb = 0b000100111
crossbb = 0b001011000

1 のビットの数を数える方法

最初に NpBoard クラスなどと同様に、1 のビットの数を数える方法 で実装して その処理速度を計測 し、この後で説明する ビット演算による処理速度と比較 することにします。

以下では (0, 0) のマスに 着手を行った場合の判定処理 について説明します。(0, 0) に着手を行った場合は is_winner は 0 列、0 行、左上から右下の対角線 の判定を行います。

下記のゲーム盤の数値座標を表す図から 0 列の数値座標は 0、1、2 であることがわかります。従って、0 列に 〇 のマークが並んでいるかどうか は、〇 のマークのビットボードの値 である 2 進数 0b000100111 の 0、1、2 番 のビットの中で 1 であるビットの数を数え、それがゲーム盤のサイズである 3 と等しいかどうか で判定することができます。

同様の理由で 0 行 の場合は 0, 3, 6、左上から右下の対角線 の場合は 0, 4, 7 の番号のビットの中で 1 であるビットの数を数えれば良い ことがわかります。

そこで、下記のような 仮引数 bitboard に代入された ビットボード に対して、仮引数 numlist に代入された list の要素の番号 の ビットが 1 である数を数える、count_bits という関数を定義 することにします。

• 1 行目：仮引数 bb と numlist を持つ count_bits という名前の関数を定義する
• 2 行目：1 のビットの数を数える変数を 0 で初期化する
• 3 ~ 5 行目：numlist の各要素に対する繰り返し処理を行う
• 4、5 行目：前回の記事で説明した方法で numlist から取り出した数値座標を表す num の BitBoard の座標を計算し、そのビットが 1 であるかどうかを判定し、1 の場合は count を 1 増やす
• 6 行目：計算した 1 のビットの数を返り値として返す

1  def count_bits(bb, numlist):
2      count = 0
3      for num in numlist:
4          if bb & (1 << num):
5              count += 1
6      return count

行番号のないプログラム

def count_bits(bb, numlist):
    count = 0
    for num in numlist:
        if bb & (1 << num):
            count += 1
    return count

下記は 以下の表の条件 で ビットボードの 1 のビットの数 を数え、ゲーム盤のサイズである 3 と等しいかどうかを計算 することで その条件の直線上にマークが並ぶかどうかを判定 するプログラムです。実行結果から 正しい計算が行われることが確認 できます。

条件	マスの数値座標	配置されているマーク	マークの数
0 列 の 〇 のマーク	0, 1, 2	〇〇〇	3
0 列 の × のマーク	0, 1, 2	〇〇〇	0
0 行 の 〇 のマーク	0, 3, 6	〇××	1
0 行 の × のマーク	0, 3, 6	〇××	2
対角線 の 〇 のマーク	0, 4, 8	〇×－	1
対角線 の × のマーク	0, 4, 8	〇×－	1

print("0 列の 〇 のマーク")
count = count_bits(circlebb, [0, 1, 2])
print(count)
print(count == 3)
print()
print("0 列の × のマーク")
count = count_bits(crossbb, [0, 1, 2])
print(count)
print(count == 3)
print()
print("0 行の 〇 のマーク")
count = count_bits(circlebb, [0, 3, 6])
print(count)
print(count == 3)
print()
print("0 行の × のマーク")
count = count_bits(crossbb, [0, 3, 6])
print(count)
print(count == 3)
print()
print("対角線 1 の 〇 のマーク")
count = count_bits(circlebb, [0, 4, 8])
print(count)
print(count == 3)
print()
print("対角線 1 の × のマーク")
count = count_bits(crossbb, [0, 4, 8])
print(count)
print(count == 3)

実行結果

0 列の 〇 のマーク
3
True

0 列の × のマーク
0
False

0 行の 〇 のマーク
1
False

0 行の × のマーク
2
False

対角線 1 の 〇 のマーク
1
False

対角線 1 の × のマーク
1
False

for 文を利用して上記のプログラムを簡潔にまとめることもできますが、わかりやすさを重視して for 文を使わないプログラムにしました。

処理速度の計測

下記は 0 列 に 〇 のマークが並んでいるかの判定 の 処理時間を計測 するプログラムです。

%%timeit 

count = count_bits(circlebb, [0, 1, 2])
count == 3

実行結果

336 ns ± 3.17 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

複数のビットをまとめて判定する方法

下記の ビット演算 を行うことで 複数のビットがすべて 1 であるかどうか を 1 回の AND 演算で判定 することができます。

• 複数のビットがすべて 1 であるか どうかを 判定したい数値を a とする
• 判定したいビットだけが 1、他のすべてのビットが 0 の 数値を mask とする
• a & mask == mask という AND 演算 による条件式が True であるかどうかで判定できる

上記の mask のような、ビット演算 において 特定のビットだけに注目 して 計算を行うために用いられるのデータ の事を、注目するビット 以外のビット を顔につけるマスクのように 覆い隠して計算の対象外とする 計算を行うことから マスク（mask）、マスクデータ、ビットマスク などと呼びます。本記事では ビットマスク と表記することにします。

参考までに Wikipedia の マスク の項目のリンクを下記に示します。

前回の記事では 調べたいビットが 1 つ の場合の AND 演算 の説明を行いましたが、その場合に用いられる 調べたい 1 つのビットだけが 1 の数値 も ビットマスク です。また、調べたいビットが複数の場合でも同様 に、調べたいビットのみを 1、残りのすべてのビットを 0 とした ビットマスク と AND 演算 を行うと、以下のような計算結果 になります。

• 調べたいビット以外 のビットは すべて 0 が計算 される
• 調べたいビット に対しては、そのビットが 1 の場合は 1 が、0 の場合 は 0 が計算 される

従って、調べたいビットがすべて 1 の場合 に a & mask によって 計算されるデータ は ビットマスクと等しく なりますが、1 つでも調べたいビットが 0 である場合はそのビットの値が 0 になるため ビットマスクと異なる ようになります。

前回の記事で説明したように、調べたいビット が 1 つだけの場合 は a & mask の値が 0 にならない という条件で 判定を行うことができる ので、if 文に記述する 条件式 を a & mask == mask ではなく a & mask のように == mask の記述を省略 することができます。一方、調べたいビットが複数 の場合は == mask を省略することはできない 点に注意が必要です。

なお、複数のビットを調べたい場合 に条件式に a & mask のように記述した場合は、調べたいビットのうち 1 つ以上のビットが 1 である場合に 0 以外の値が計算される ので、少なくとも 1 つ以上のビットが 1 であることを判定 します。

0 列 に 〇 が並んでいるか どうかは、下記のプログラムのように ビットマスク を表す変数 mask に 0、1、2 番のビットだけを 1 とした 0b000000111 を代入 し、circlebb & mask == mask が True かどうかで 判定を行う ことができます。実行結果のように、True が計算される ことから 正しい計算が行われることが確認 できます。

mask = 0b000000111
print(circlebb & mask == mask)

実行結果

True

下記は 先程と同じ条件 で マークが並ぶかどうかを判定 するプログラムです。わかりやすいよう に「ビットボード」、「ビットマスク」、「ビットボード & ビットマスク」の 計算結果を縦に並べて表示 しました。なお、先程と異なり マークの数を数えていない ので その表示は行われません。実行結果から 正しい判定が行われることが確認 できます。

mask = 0b000000111 # 0、1、2 番のビットを 1 とするビットマスク
print("0 列の 〇 のマーク")
print(f"bb        = {circlebb:09b}")
print(f"mask      = {mask:09b}")
print(f"bb & mask = {circlebb & mask:09b}")
print(circlebb & mask == mask)
print()
print("0 列の × のマーク")
print(f"bb        = {crossbb:09b}")
print(f"mask      = {mask:09b}")
print(f"bb & mask = {crossbb & mask:09b}")
print(crossbb & mask == mask)
print()

mask = 0b001001001 # 0、3、6 番のビットを 1 とするビットマスク
print("0 行の 〇 のマーク")
print(f"bb        = {circlebb:09b}")
print(f"mask      = {mask:09b}")
print(f"bb & mask = {circlebb & mask:09b}")
print(circlebb & mask == mask)
print()
print("0 行の × のマーク")
print(f"bb        = {crossbb:09b}")
print(f"mask      = {mask:09b}")
print(f"bb & mask = {crossbb & mask:09b}")
print(crossbb & mask == mask)
print()

mask = 0b100010001 # 0、4、8 番のビットを 1 とするビットマスク
print("対角線 1 の 〇 のマーク")
print(f"bb        = {circlebb:09b}")
print(f"mask      = {mask:09b}")
print(f"bb & mask = {circlebb & mask:09b}")
print(circlebb & mask == mask)
print()
print("対角線 1 の × のマーク")
print(f"bb        = {crossbb:09b}")
print(f"mask      = {mask:09b}")
print(f"bb & mask = {crossbb & mask:09b}")
print(crossbb & mask == mask)
print()

実行結果

0 列の 〇 のマーク
bb        = 000100111
mask      = 000000111
bb & mask = 000000111
True

0 列の × のマーク
bb        = 001011000
mask      = 000000111
bb & mask = 000000000
False

0 行の 〇 のマーク
bb        = 000100111
mask      = 001001001
bb & mask = 000000001
False

0 行の × のマーク
bb        = 001011000
mask      = 001001001
bb & mask = 001001000
False

対角線 1 の 〇 のマーク
bb        = 000100111
mask      = 100010001
bb & mask = 000000001
False

対角線 1 の × のマーク
bb        = 001011000
mask      = 100010001
bb & mask = 000010000
False

上記の bb & mask の計算結果の 1 のビットの数 が 直線上のマークの数 を表すので、(bb & mask).bit_count() で 直線上のマークの数を数える ことができます。

図での説明

下図は上記の 0 列の 〇 のマークに対する処理 を図示したものです。ビットボード の 緑色の 0、1、2 番以外 のビットに対しては 白色の 0 と AND 演算 が行われるので 計算結果はすべて 0 となります。一方、0、1、2 番のビット は 黄色の 1 と AND 演算 が行われた結果、計算結果はビットはビットボードと同じ値 が計算されます。その結果、0 列に 〇 が並んだ下記の計算 では ビットマスクと同じデータが計算 されることになります。

下図は上記の 0 行の 〇 のマークに対する処理 を図示したもので、ビットマスク の 1 のビットが 0、3、6 番 のビットである点が 異なります。計算結果の 0、3、6 番 のビットは ビットボードと同じ値が計算 され、それ以外のビットは 0 が計算 されます。ビットボードの 3 番と 6 番 のビットは 対応するマスに 〇 が配置されていない ため 0 となる ので ビットマスクと異なるデータが計算 されることになります。

処理速度の計測

下記は 0 列 の 〇 のマーク に対する 処理時間を計測 するプログラムです。実行結果から、先程計測した 1 のビットの数を数えた場合 の 336 ns と比較して 約 8 倍もの処理速度 で計算を行うことができることが確認できました。

%%timeit

mask = 0b001001001 
circlebb & mask == mask

実行結果

39.9 ns ± 0.149 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

このように、ビット演算を利用 することで 直線上にマークが並んでいるかどうか の判定処理の 処理速度を大幅に高速化 することができます。

is_winner メソッドの定義

今回の記事では 3 x 3 の 〇× ゲームのゲーム盤 での is_winner の処理を実装 することにします。任意の大きさ のゲーム盤の場合の処理は 次回の記事で実装 します。

ビットマスクの計算

is_winner メソッドを実装するためには、x 行、y 列、2 つの対角線 の判定を行う際の ビットマスクが必要 となります。3 x 3 のゲーム盤の場合は 直線が 8 種類 しかなく、それぞれの直線に対するビットマスク は下記の数値座標の図から 下記の表 のようになります。

　

	1 となるビットの番号	ビットマスク
0 列	0、1、2	0b000000111
1 列	3、4、5	0b000111000
2 列	6、7、8	0b111000000
0 行	0、3、6	0b001001001
1 行	1、4、7	0b010010010
2 行	2、5、8	0b100100100
対角線 1	0、4、8	0b100010001
対角線 2	2、4、6	0b001010100

is_winner メソッドの定義

下記は is_winner メソッドの定義です。

• 2 行目：直前の着手の (x, y) の座標を move_to_xy メソッドで計算する
• 5 ~ 8 行目：上記の 各列、各行、対角線 の ビットマスクを変数に代入 する。各行と各列 のビットマスクは list の要素にそれぞれ代入 した
• 9、10 行目：x 列と y 行 のビットマスクを 変数に代入 する
• 12 ~ 18 行目：上記で変数に代入したビットマスクを利用して x 列、y 行、2 つの対角線にマークが並んでいるかどうかを判定する

 1  def is_winner(self, player, last_move):
 2      x, y = self.move_to_xy(last_move)
 3      if self.count_linemark:
他の `is_winner` メソッドと同じなので省略 
 4      else:
 5          colmasks = [0b000000111, 0b000111000, 0b111000000]
 6          rowmasks = [0b001001001, 0b010010010, 0b100100100]
 7          diamask1 = 0b100010001
 8          diamask2 = 0b001010100
 9          colmask = colmasks[x]
10          rowmask = rowmasks[y]
11          board = self.board[player]
12          if board & colmask == colmask or board & rowmask == rowmask:
13              return True
14          # 左上から右下方向の判定
15          if x == y and board & diamask1 == diamask1:
16              return True
17          # 右上から左下方向の判定
18          if x + y == self.BOARD_SIZE - 1 and board & diamask2 == diamask2:
19              return True
20  
21      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
22      return False    
23  
24  BitBoard.is_winner = is_winner

行番号のないプログラム

def is_winner(self, player, last_move):
    x, y = self.move_to_xy(last_move)
    if self.count_linemark:
        if self.rowcount[player][y] == self.BOARD_SIZE or \
        self.colcount[player][x] == self.BOARD_SIZE:
            return True
        # 左上から右下方向の判定
        if x == y and self.diacount[player][0] == self.BOARD_SIZE:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            self.diacount[player][1] == self.BOARD_SIZE:
            return True
    else:
        colmasks = [0b000000111, 0b000111000, 0b111000000]
        rowmasks = [0b001001001, 0b010010010, 0b100100100]
        diamask1 = 0b100010001
        diamask2 = 0b001010100
        colmask = colmasks[x]
        rowmask = rowmasks[y]
        board = self.board[player]
        if board & colmask == colmask or board & rowmask == rowmask:
            return True
        # 左上から右下方向の判定
        if x == y and board & diamask1 == diamask1:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and board & diamask2 == diamask2:
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False    

BitBoard.is_winner = is_winner

動作の確認

以前の記事で定義した test_judge を利用して judge メソッドが正しく動作するかを検証 することにします。下記のプログラムの実行結果から count_linemark が False と True の場合の両方で 正しい判定が行われることが確認 できました。

from mbtest import test_judge

print("count_linemark = False")
test_judge(mbparams={"boardclass": BitBoard, "count_linemark": False})
print()
print("count_linemark = True")
test_judge(mbparams={"boardclass": BitBoard, "count_linemark": True})

実行結果

count_linemark = False
Start
test winner = playing
oooooooooo
test winner = 0
ooooooooo
test winner = 1
oooooooo
test winner = draw
o
Finished

count_linemark = True
Start
test winner = playing
oooooooooo
test winner = 0
ooooooooo
test winner = 1
oooooooo
test winner = draw
o
Finished

Marubatsu クラスの restart メソッドの修正

上記で move_to_xy メソッドと judge メソッドの 定義が完成 しました。Marubatsu クラスのインスタンスを print で表示 する際に呼び出される __str__ メソッド は move_to_xy を呼び出し、judge メソッドで計算した ゲームの状態を表示 するので、これらのメソッドを定義したことで BitBoard を利用 して作成した Marubatsu クラスのインスタンス に対して print で局面を表示できる ように なるはず なのですが、下記のプログラムの実行結果のように エラーが発生する ことが判明しましたので、このエラーを修正することにします。

mb = Marubatsu(boardclass=BitBoard)
print(mb)

実行結果

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[29], line 2
      1 mb = Marubatsu(boardclass=BitBoard)
----> 2 print(mb)

File c:\Users\ys\ai\marubatsu\211\marubatsu.py:253, in Marubatsu.__str__(self)
    251 for y in range(self.BOARD_SIZE):
    252     for x in range(self.BOARD_SIZE):
--> 253         lastx, lasty = self.board.move_to_xy(self.last_move)
    254         mark = self.board.MARK_TABLE[self.board.getmark(x, y)]
    255         if x == lastx and y == lasty:

Cell In[15], line 2
      1 def move_to_xy(self, move):
----> 2     move = move.bit_length() - 1
      3     return move // self.BOARD_SIZE, move % self.BOARD_SIZE

AttributeError: 'tuple' object has no attribute 'bit_length'

エラーの原因の検証と修正方法

エラーメッセージ から、move_to_xy メソッドの中で move.bit_length() を実行しようとした際に、move の中に tuple が代入 されており、tuple には bit_length メソッドが定義されていない ことが エラーの原因 であることが確認できます。

また、その上のエラーメッセージ から、move_to_xy メソッドが self.board.move_to_xy(self.last_move) によって呼び出されている ことが確認できます。

上記の処理はゲーム開始時の局面に対して行っており、ゲーム開始時の局面 の self.last_move には、Marubatsu クラスの下記の restart メソッドによって (-1, -1) という tuple が代入 されているので、これがエラーの原因 であることがわかりました。

    def restart(self):
略
        self.last_move = -1, -1          

Marubatsu クラスを定義し始めた頃 は ゲーム盤の座標 を tuple だけで表現 していたのでこのプログラムでも問題はなかったのですが、様々なデータ構造 で ゲーム盤の座標を表現 するようになった 現在では、last_move には ゲーム盤が扱うデータ構造 で 座標を代入する必要 があります。そのため、この部分は self.last_move = self.board.xy_to_move(-1, -1) のように ゲーム盤が扱うデータ構造 で 座標を代入するように修正 する必要があります。

ゲーム開始時の last_move 属性に代入する座標に関するエラー

ただし、下記のプログラムのように BitBoard のインスタンスに対して xy_to_move(-1, -1) を記述して呼び出すと、実行結果のように 別のエラーが発生 してしまいます。

print(bb.xy_to_move(-1, -1))

実行結果

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[31], line 1
----> 1 print(bb.xy_to_move(-1, -1))

File c:\Users\ys\ai\marubatsu\211\marubatsu.py:2153, in BitBoard.xy_to_move(self, x, y)
   2152 def xy_to_move(self, x, y):
-> 2153    return 1 << (y + self.BOARD_SIZE * x)

ValueError: negative shift count

エラーメッセージ の negative shift count は、シフト演算 では ずらす量（count）に 負（negative）の値を設定できない ことを意味します。

従って、この問題を解決 するためには、ゲーム開始時 の last_move 属性に、xy_to_move メソッドによって エラーが絶対に発生しない座標 を代入する必要があることがわかります。

ゲーム開始時の last_move 属性に代入する座標の検討

ゲーム開始時 の last_move 属性に どのような座標を代入すればよいか について検討するためには、これまでのプログラムが ゲーム開始時 の last_move 属性に (-1, -1) の座標を 代入した理由 を検証する必要があります。そのような処理を記述したのはかなり前の事なので、おそらくほとんどの方がその理由を忘れているのではないかと思います。筆者もおぼろげにしか覚えていなかったので 過去の記事を調べた 所その理由は以下の通りでした。

• 直前の着手を表す last_move 属性は、以前の記事で説明したように、__str__ メソッドの中で 直前の着手を表すマーク を 大文字で表示 するために利用している
• 以前の記事では、ゲーム開始時 の last_move 属性に ゲーム盤の外 の (-1, -1) の座標を代入する理由として、直前の着手が存在しない ゲーム開始時の局面を表示する際に、マークが誤って大文字で表示されないようにする ためと説明していた

上記の理由を踏まえて検討した結果、以下の理由から ゲーム開始時の last_move 属性には ゲーム盤の上のどの座標を代入しても構わない ことが判明しました。

• マークの大文字への変換処理 は以前の記事で説明した 文字列型 のデータを 大文字に変換 する upper メソッドを利用して行っている
• 空のマス は .（ピリオド） の文字で表示する
• . には 大文字と小文字の区別は存在しない
• 大文字のと小文字 の 区別が存在しない文字列 に対して upper メソッドを呼び出した場合は、元の文字列がそのまま計算 される
• ゲーム開始時 の時点では マークは一つも配置されていない ので すべて空のマス である
• 従って、ゲーム開始時 の last_move 属性に ゲーム盤上のどの座標が代入 されていても、その座標の . が upper メソッドによって 別の文字に変換されることはない ので、ゲーム盤の表示 に 影響を及ぼさない

xy_to_move は ゲーム盤上の座標 に対して エラーを発生することは絶対にありません。そこで、下記のプログラムの 4 行目のように restart メソッドで last_move 属性にどのようなサイズのゲーム盤でも 必ず存在する (0, 0) の座標を代入するように修正しました。

1  def restart(self):
元と同じなので省略
2      self.last_move = self.board.xy_to_move(0, 0)
元と同じなので省略
3  
4  Marubatsu.restart = restart

行番号のないプログラム

def restart(self):
    self.initialize_board()
    self.turn = self.CIRCLE     
    self.move_count = 0
    self.status = self.PLAYING
    self.last_move = self.board.xy_to_move(0, 0)
    self.last_turn = self.CROSS
    self.records = [self.last_move]
    
Marubatsu.restart = restart

修正箇所

def restart(self):
元と同じなので省略
-   self.last_move = -1, -1
+   self.last_move = self.board.xy_to_move(0, 0)
元と同じなので省略
    
Marubatsu.restart = restart

上記の修正後に先程の下記のプログラムを実行すると、エラーが発生しなくなったことが確認 できます。

mb = Marubatsu(boardclass=BitBoard)
print(mb)

実行結果

Turn o
...
...
...

処理速度の比較

次に、これまでに作成してきた ゲーム盤を表すクラス の judge メソッドの処理速度を比較 することにします。その際に、列、行、2 つの対角線 の すべての判定が行われる ように下記のような 真ん中の (1, 1) に着手を行った局面 に対する判定を行うことにします。なお、5 手目の局面の判定 を行っている 理由 は、〇× ゲームは 4 手目以下の局面では決着がつかない ため judge メソッドでは すぐに Marubatsu.PLAYING を返す処理を行う からです。

mb.restart()
mb.cmove(0, 0)
mb.cmove(1, 0)
mb.cmove(2, 0)
mb.cmove(0, 1)
mb.cmove(1, 1)
print(mb)

実行結果

Turn x
oxo
xO.
...

下記のプログラムで、上記の局面 に対して これまでに作成してきたゲーム盤を表すクラス を利用した Marubatsu クラスのインスタンスの judge メソッドの処理時間を計測 して比較することにします。

なお、count_linemark が True の場合の 処理はどのクラスも同じ なので count_linemark が False の場合の処理時間を計測します。

• 3 行目：上記の順番の着手を表す list を変数に代入する
• 4 行目：これまでに定義したゲーム盤を表すクラスを表す list を変数に代入する
• 6 ~ 11 行目：それぞれのゲーム盤を表すクラスを利用した Marubatsu クラスのインスタンスを作成し、上記の着手を行った後で judge メソッドの処理時間を計測する

 1  from marubatsu import ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard
 2  
 3  movelist = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1)]
 4  boardclasslist = [ ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard]
 5  
 6  for boardclass in boardclasslist:
 7      print(f"boardclass: {boardclass.__name__}")
 8      mb = Marubatsu(boardclass=boardclass)
 9      for x, y in movelist:
10          mb.cmove(x, y)
11      %timeit mb.judge()

行番号のないプログラム

from marubatsu import ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard

movelist = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1)]
boardclasslist = [ ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard]

for boardclass in boardclasslist:
    print(f"boardclass: {boardclass.__name__}")
    mb = Marubatsu(boardclass=boardclass)
    for x, y in movelist:
        mb.cmove(x, y)
    %timeit mb.judge()

実行結果

boardclass: ListBoard
2.74 μs ± 37.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: List1dBoard
1.33 μs ± 19.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
boardclass: ArrayBoard
1.86 μs ± 20.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
boardclass: NpBoard
11.1 μs ± 173 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: NpIntBoard
10.6 μs ± 250 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: NpBoolBoard
6.28 μs ± 91.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: BitBoard
737 ns ± 7.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は上記の 実行結果をまとめた表 で、小数点以下第一位で四捨五入しました。

boardclass	処理時間の平均
ListBoard	2.7 μs
List1dBoard	1.3 μs
ArrayBoard	1.9 μs
NpBoard	11.1 μs
NpIntBoard	10.6 μs
NpBoolBoard	6.3 μs
BitBoard	0.7 μs

上記から ビットボード でゲーム盤を表現した BitBoard クラスの 処理速度が最も高速 であることが確認できました。また、2 番目に高速 な List1dBoard クラスと比較しても 約 2 倍の処理速度 であることが確認できました。

なお、今回の記事で実装 した BitBoard クラスの judge メソッドは 3 x 3 のゲーム盤のみに対応 していますが、もっと大きなゲーム盤 に対する BitBoard クラスの judge メソッドを実装して 処理速度を比較 すると その差はもっと大きくなる はずです。そのことは 次回の記事で確認 する予定です。

今回の記事のまとめ

今回の記事では、BitBoard の座標 を (x, y) の座標に変換 する move_to_xy メソッドと、勝敗判定 を行う judge メソッドを 実装しました。また、勝敗判定 の処理は、ビットボードに対する ビット演算 を行うことで他のゲーム盤を表すデータ構造よりも 処理速度が高速になることが確認 できました。

なお、ai2 VS ai2 の処理時間を 計測していない のは、ai2 の処理に必要となる calc_legal_moves をまだ実装していない からです。それらの残りのメソッドについては次回以降の記事で実装する予定です。

本記事で入力したプログラム

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
marubatsu.py	本記事で更新した marubatsu_new.py

次回の記事

1. List1dBoard や BitBoard クラスのゲーム盤の数値座標は以前の記事の説明とは異なり縦方向に数えるので、x 座標と y 座標の計算式は以前の記事の説明とは逆になります ↩

2. 前回の記事で説明したように、正の整数は 0 （最も左の）最上位の 1 のビットよりも上位のビット に 0 が無限に並んだ 2 進数であると考えることができます ↩

3. CPU が 1 度に行えるビット演算のビット数には上限があるので、それを超えるようなビット数のビット演算を行う場合は処理が遅くなります。最近のほとんどの CPU は 64 ビット以上のビット演算を行うことができます。これはゲーム盤のサイズが 64 x 64 以下の場合はこれから説明する方法での判定処理の処理速度が変わらないということを意味します ↩