Pythonで〇×ゲームのAIを一から作成する その215 参照テーブルを利用した popcount などの計算

目次と前回の記事

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 の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

参照テーブルを利用した popcount の計算

以前の記事で ビット列の中で 1 のビットの数を数える という popcount の計算方法について紹介しましたが、参照テーブル を利用した方法を紹介するのを忘れていたので紹介することにします。

話を簡単にするため、前回の記事に引き続き今回の記事でも 3 x 3 のサイズ のゲーム盤に対する 実装を行う ことにします。任意の大きさのゲーム盤に対する実装は今後の記事で紹介する予定です。

参照テーブルとは何か

popcount を 高速に計算する手法 の一つに 参照テーブル（lookup table） を利用する方法があります。参照テーブル とは、複雑な計算の計算結果 を あらかじめ計算したものをまとめた表 のことで、これまでの記事では参照テーブルという用語は使ってきませんでしたが 何度も利用 してきました。例えば、以前の記事では 〇× ゲームの すべての局面の評価値を計算したゲーム木を作成 することで最善手を計算するという方法を紹介しましたが、その際に作成した ゲーム木が参照テーブル です。

参照テーブル は list、dict、ゲーム木のような 木構造 などの 様々なデータ構造で表現 することができますが、効率の良い処理を行うためには 記録するデータの性質に適したデータ構造 を選択することが重要です。

参照テーブルは、以前の記事で説明した九九や三角関数などの数表、計算表をコンピューターのプログラムで扱えるようにしたデータのことです。

参照テーブルは、データの対応表であるという点では以前の記事で説明したメモ化や、置換表と似ていますが、以下の点が異なります。

• 参照テーブルはあらかじめ計算して作成された対応表であり、一般的には作成後にその内容が変わることがない静的な表である
• メモ化や置換表は計算の過程で得られた値のうち、再利用できるものを記録する対応表であり、計算の過程でその内容が変化する動的な表である

参考までに Wikipedia の参照テーブルの気にを下記に紹介します。

参照テーブルのサイズ

参照テーブル を作成する際に 問題 となるのは、参照テーブルに 記録するデータのサイズ です。例えば、〇× ゲームのような 局面の種類がそれほど多くない ゲームの場合は、すべての局面を記録したゲーム木 を 作成することは可能 ですが、オセロ、将棋、囲碁のような 局面の数が膨大 なゲームの場合は すべての局面を記録したゲーム木 を 作成することは不可能 です。

参照テーブル が 記録するデータが多い程、多くの種類 のデータに対する計算を 素早く行う ことができますが、その反面コンピューターの メモリが多く必要になる ので 適切な大きさの参照テーブルを作成 することが重要となります。

参照テーブルの一種である九九の表を暗記することで 1 桁の掛け算を素早く行うことができますが、2 桁以上の掛け算を行う場合は 1 桁ごとの掛け算の計算結果を組み合わせて行う必要があります。

一方、インドで行われているという 2 桁の掛け算の表を暗記すれば 28 × 85 のような掛け算を素早く行うことができますが、九九の表の約 100 倍大きさの表を暗記する必要が生じます。

日本の小学校で 1 桁の九九の表を暗記するのは、おそらく小学生が無理なく暗記できるサイズの表だからではないかと思います。

popcount の 参照テーブルの場合も同様 で、あらゆるビット列の popcount の値をあらかじめ計算した 参照テーブル を 作成することは不可能 なので、popcount の参照テーブルが 記録するデータの範囲を決める 必要があります。

用語の定義

説明を簡潔にするために、以後の説明では ビット長 が n のビット列 のことを n ビットのデータ のように表記することにします。3 x 3 の 〇× ゲームの ビットボード を表すビット列のビット長は 9 なので、9 ビットのデータ です。

n ビット のデータは 0 ~ $\boldsymbol{2^n - 1}$ までの範囲の $\boldsymbol{2^n}$ 種類の数値を表現できます。

3 x 3 の 〇× ゲームの場合の参照テーブルの作成

3 x 3 の 〇× ゲームの ビットボード は 9 ビットのデータ なので、0b000000000 ~ 0b111111111 までの範囲の $2^{9}$ = 512 種類 の数値になります。それらの値は 0 からはじまる整数 なので、popcount の参照テーブル は ビット列の値をインデックス とし、そのインデックスの 要素を popcount の値 とする list で表現 できます。

また、それらの範囲のビット列の popcount の値 は 0 ~ 9 の範囲の整数 です。従って、popcount の参照テーブル は int 型の値を要素 とする 要素の数が 512 の list で表現できます。

以前の記事で説明したように、Python の int 型 のデータの データサイズは 28 バイト です。また、512 個の要素を持つ list の データサイズ は下記のプログラムの実行結果から 4152 バイト であることがわかるので、popcount の参照テーブルのデータサイズ は 4152 + 28 × 512 = 18488 バイト になります。18488 バイトは 数ギガバイトのメモリが一般的 になった現在のコンピューターにとっては 非常に小さいサイズ のデータなので、データサイズが問題になることはありません。

import sys

print(sys.getsizeof([0] * 512))

実行結果

4152

以前の記事で説明したように、sys.getsizeof の計算結果はオブジェクトに直接起因するメモリ消費のみを表し、参照するオブジェクトは含みません。そのため、sys.getsizeof([0] * 512) は 512 個の要素を持つ list のデータの入れ物としてのデータサイズを表しますが、その中に記録される 512 個の int 型の要素のデータサイズは含まれません。そのことは、sys.getsizeof([0] * 512) の計算結果である 4152 が 512 個の int 型のデータのデータサイズである 28 × 512 = 14336 より小さいことから明らかでしょう。

また、そのことは下記のプログラムのように int 型のデータとは異なる 42 バイトのデータである "a" を 512 個要素の値として持つ list のデータサイズが 4152 で変わらないことからも確認できます。

print(sys.getsizeof("a"))
print(sys.getsizeof(["a"] * 512))

実行結果

42
4152

下記は 0 以上 $2 ^ 9$ = 1 << 9 未満 の範囲のビット列の popcount の参照テーブル を表す list を、list 内包表記 と bit_count メソッドで作成¹するプログラムです。

ptable = [ i.bit_count() for i in range(1 << 10) ]

下記のプログラムは popcount が 3 である 0b100010010 を ptable と bit_count メソッドで計算 するプログラムで、実行結果から 参照テーブル である ptable を利用 することでも 正しい計算が行われる ことが確認できます。

b = 0b100010010
print(ptable[b])
print(b.bit_count())

実行結果

3
3

下記は それぞれの処理時間を計測 するプログラムです。実行結果から、参照テーブル を利用したほうが 処理速度が高速 になることが確認できます。

%timeit ptable[b]
%timeit b.bit_count()

実行結果

22.7 ns ± 0.13 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
31.4 ns ± 0.141 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Python では上記のように参照テーブルを利用したほうが処理速度が高速になりますが、プログラム言語によっては異なる結果になる場合があります。

以後は n ビットまで のデータの popcount を計算できる popcount の参照テーブル を n ビットの参照テーブル と表記することにします。

参照テーブルのサイズの限界

参照テーブル が記録できる データのサイズには限界 があるので、ある程度以上の 大きなゲーム盤 のビットボードの popcount を 一度で計算 する 参照テーブルを作成 することは 現実的に不可能 です。

例えばオセロと同じ 6 x 6 のゲーム盤の場合は マスの数が 36 なので、$\boldsymbol{2^{36}}$ 種類 のビット列に対する 36 ビットの参照テーブルを作成 する必要があります。以前の記事 で紹介した array を利用して 1 つの要素 を 1 バイトのデータで記録 した場合でも $2^{36} =$ 64 GB²（ギガバイト）もの メモリが必要 となるので、32 GB のメモリを持つ 最近の一般的なパソコンのメモリには収まりません。

popcount の参照テーブル としては、$2 ^ 8 =$ 256 種類 のデータを表現できる 1 バイト = 8 ビット参照テーブル、または $2 ^ {16} =$ 65536 種類 のデータを表現できる 2 バイト = 16 ビットの参照テーブル を作成するのが 一般的 ではないかと思います。

参照テーブルのサイズを超えたビット列の popcount の計算

参照テーブルのビット数を超えたビット列 の popcount は、popcount を計算する ビット列 を 参照テーブルのビット数ごとにわけて popcount を計算し、その 合計を計算する ことで求めることができます。

具体的には popcount を計算する ビット列のビット数を b、popcount の 参照テーブル ptable のビット数を s とした場合に、下記のアルゴリズム で任意のビット列 b の popcount を計算 することができます。

1. b の popcount を計算する変数 count を 0 で初期化する
2. b の 0 ~ s - 1 番の s 個のビットの値を、「b」と「0 ~ s - 1 番のビットを 1 としたビットマスク」との AND 演算で計算する
3. ptable を利用して手順 2 で計算したビット列の popcount を計算し、count に加算する
4. b を s ビット右シフトした値を計算した値で b を更新する
5. b が 0 でない場合は手順 1 に戻る

上記の 手順 3 で b の 0 ~ s - 1 番 のビットの popcount が計算 され、手順 4 で b を s ビット右シフト することで b の 0 ~ s - 1 番のビットが削除 されます。その結果 b から popcount を計算済のビット列が取り除かれる ことになります。b が 0 でない 場合は まだ数えていない 1 のビットが残っている ので 手順 2 に戻って 残りの 1 のビットの数を数える処理を続行 します。

下記は 16 ビットの参照テーブルを作成 した場合に、上記のアルゴリズムで 仮引数 b に代入 された ビット列の popcount を計算 する popcount5³という関数を定義 するプログラムです。

• 1 行目：16 ビットの popcount の参照テーブルをあらかじめ計算する
• 4 行目：popcount を数える変数を 0 で初期化する
• 5 ~ 7 行目：b が 0 になるまで繰り返し処理を行う
• 6 行目：b と 0 ~ 15 番のビットが 1 のビットマスク 0b1111111111111111 との AND 演算を行った値の popcount を ptable を利用して計算し、count に加える
• 7 行目：b を 16 ビット右シフトした値を計算して b を更新する
• 8 行目：繰り返し処理が終了した時点で count に b の popcount が計算されているのでその値を返り値として返す

1  ptable = [ i.bit_count() for i in range(1 << 16) ]
2  
3  def popcount5(b):
4      count = 0
5      while b:
6          count += ptable[b & 0b1111111111111111]
7          b >>= 16
8      return count

行番号のないプログラム

ptable = [ i.bit_count() for i in range(1 << 16) ]

def popcount(b):
    count = 0
    while b:
        count += ptable[b & 0b1111111111111111]
        b >>= 16
    return count

下記は popcount が 10、20、32、50、100、1000 の それぞれのビット列の popcount の計算 を上記の popcount5 と bit_count メソッドで計算 した 結果 と、処理時間を計測 するプログラムです。なお、(1 << x) - 1 という式で 0 ~ x - 1 番のビットが 1 である popcount が x のビット列を計算 しています。実行結果から popcount5 が正しい値を計算 することが確認できます。

for i in [10, 20, 32, 50, 100, 1000]:
    b = (1 << i) - 1
    print(f"i = {i}")
    print(popcount5(b))
    %timeit popcount5(b)
    print(b.bit_count())
    %timeit b.bit_count()

実行結果

i = 10
10
139 ns ± 0.289 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
10
31.9 ns ± 0.89 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
i = 20
20
211 ns ± 1.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
20
31.4 ns ± 0.199 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
i = 32
32
253 ns ± 1.18 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
32
33 ns ± 0.135 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
i = 50
50
439 ns ± 1.78 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
50
32.7 ns ± 0.278 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
i = 100
100
791 ns ± 6.27 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
100
35.8 ns ± 0.134 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
i = 1000
1000
8.99 μs ± 133 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
1000
92.6 ns ± 0.275 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記は上記の 実行結果をまとめた表 です。16 ビットの参照テーブルを利用する popcount5 は popcount が大きくなる と 処理時間が大幅に増える のに対し、bit_count メソッドを利用する場合は それほど処理時間が増えない ことが確認できます。なお、popcount が 20 と 32 の場合は popcount5 内の 繰り返し処理が 2 回行われる 点は変わらないので 処理時間はほぼ同じ になります。

popcount	popcount5	bit_count
10	139 ns	31.9 ns
20	211 ns	31.4 ns
32	253 ns	33.0 ns
50	439 ns	32.7 ns
100	791 ns	35.8 ns
1000	8990 ns	92.6 ns

ビット長を限定した popcount の計算

上記の popcount5 は 任意のビット長 のビット列の popcount を計算できるようにするため に、popcount を数える count という変数 や、繰り返し処理が必要 となります。それに対して、popcount を計算できる ビット列の ビット長を限定 することで 余分な処理を削除 して 処理速度を高速化 することができます。

下記は 32 ビットまで のビット長のビット列の popcount を計算する popcount32⁴ の定義 で、先程のアルゴリズムの 2 回分の繰り返し処理 を 1 つの式で計算 することで count や繰り返し処理を必要としない 分だけ 処理速度が高速 になります。

def popcount32(b):
    return ptable[b & 0b1111111111111111] + ptable[b >> 16]

下記は popcount が 10、20、32 のそれぞれのビット列の popcount の計算を上記の popcount32 で計算した結果 と、処理時間を計測 するプログラムです。実行結果から popcount32 が正しい値を計算 することが確認できます。

for i in [10, 20, 32]:
    b = (1 << i) - 1
    print(f"i = {i}")
    print(popcount32(b))
    %timeit popcount32(b)

実行結果

i = 10
10
120 ns ± 0.246 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
i = 20
20
120 ns ± 1.06 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
i = 32
32
143 ns ± 0.882 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記は 先ほどの表 に 上記の計算結果を加えた表 です。余分な処理をう必要がない ので 32 ビット以下のビット列に限定 した popcount32 のほうが 汎用の popcount よりも処理時間が短い ことが確認できます。一方、ビットマスクとの AND 演算 や 右シフト演算が必要 となるため bit_count メソッドよりも 処理速度が遅く なります。

popcount	popcount	popcount32	bit_count
10	139 ns	120 ns	31.9 ns
20	211 ns	120 ns	31.4 ns
32	253 ns	143 ns	32.0 ns

上記から Python での popcount の計算処理は、ビット列の長さを 参照テーブルのビット数以下に限定する場合 は 参照テーブルを利用 したアルゴリズムが 処理速度が最も速く、そうでない場合 は bit_count メソッド の処理速度が 最も速くなる ことが確認できました。

上記から 3 x 3 の 〇× ゲームの場合は 9 ビットの参照テーブル を利用したほうが 処理速度が速くなる ので 参照テーブルを利用するように修正 することにします。

BitBoard3x3 クラスの定義

上記の例からわかるように、一般的に 汎用的な処理 を行うプログラムよりも、特定の状況に限定 した処理を行うプログラムの方が、汎用的な処理に対応する処理を行わなくても済む分だけ 処理速度が高速 になります。

そこで、3 x 3 のサイズ の 〇× ゲームのゲーム盤に 限定した BitBoard3x3 というクラスを定義 することにします。また、前回の記事で検証したように、ビットボードを利用した場合 は count_linemark が False の場合の処理速度が常に True の場合よりも 速くなる ので count_linemark が True の処理を削除 することにします。

BitBoard3x3 クラスは下記のプログラムのように BitBoard クラスを継承 して定義し、BitBoard クラスと異なる処理を行うメソッドだけを定義 することにします。

from marubatsu import BitBoard

class BitBoard3x3(BitBoard):
   pass

なお、現状では BitBoard クラスは 3 x 3 のサイズのゲーム盤の処理を行うように実装していますが、今後の記事 で 任意のサイズのゲーム盤の処理を行えるように修正 する予定です。

修正する必要がないメソッド

下記のメソッド は count_linemark が True の場合の 処理を行わず、ゲーム盤のサイズが変わっても同じプログラムで処理を行えます。そのため BitBoard クラスのメソッドと同じ処理 を行えばよいので BitBoard クラスのメソッドを そのまま継承して利用 することができます。従って下記のメソッドを BitBoard3x3 クラスに 定義する必要はありません。

• getmark_by_move
• xy_to_move
• move_to_xy
• board_to_hashable
• board_to_str

ゲーム盤の大きさによって処理が異なるメソッド

下記のメソッドは、ゲーム盤のサイズによって行う処理が異なります。そこで、現状では 3 x 3 のサイズ の処理を行っている BitBoard クラスと同じ定義 を行い、今後の記事で BitBoard クラスを 任意のサイズのゲーム盤 に対して処理を行うことができるようにする際に BitBoard クラスの それらのメソッドを修正 することにします。

• count_legal_moves：空のマスのビットが 1 になるビットボードを計算する処理に必要となるビットマスクがゲーム盤の大きさによって異なる
• calc_same_hashables：反転と転置の処理がゲーム番の大きさによって異なる

下記は BitBoard3x3 クラスでのそれらのメソッドの定義です。内容は BitBoard クラスと同じなので折りたたみます。

プログラム

def calc_legal_moves(self):
    # マークが配置されているマスのビットが 1 になるビットボードを計算する
    board = self.board[0] | self.board[1]
    # 空のマスのビットが 1 になるビットボードを計算する
    board = 0b111111111 - board
    legal_moves = []
    # board が 0 になるまで繰り返し処理を行う
    while board:
        # 次の合法手である LOB を計算する
        move = board & (-board)
        legal_moves.append(move)
        # board の RSB を 0 にして move のデータを削除する
        board -= move

    return legal_moves

BitBoard3x3.calc_legal_moves = calc_legal_moves

def calc_same_hashables(self, move=None):
    if move is None:
        hashables = set()
    else:
        hashables = {}
    if move is not None:
        x, y = self.move_to_xy(move)
    circlebb = self.board[0]
    crossbb = self.board[1]
    for _ in range(4):
        # 左右の反転処理
        c = (circlebb ^ (circlebb >> 6)) & 0b111
        circlebb = c ^ (c << 6) ^ circlebb        
        c = (crossbb ^ (crossbb >> 6)) & 0b111
        crossbb = c ^ (c << 6) ^ crossbb        
        hashable = circlebb | (crossbb << self.bit_length) 
        if move is None:
            hashables.add(hashable)
        else:
            x = self.BOARD_SIZE - x - 1
            hashables[hashable] = self.xy_to_move(x, y)
            
        # 転地処理
        c = (circlebb ^ (circlebb >> 2)) & 0b100010
        circlebb = c ^ (c << 2) ^ circlebb 
        c = (circlebb ^ (circlebb >> 4)) & 0b100
        circlebb = c ^ (c << 4) ^ circlebb 
        c = (crossbb ^ (crossbb >> 2)) & 0b100010
        crossbb = c ^ (c << 2) ^ crossbb 
        c = (crossbb ^ (crossbb >> 4)) & 0b100
        crossbb = c ^ (c << 4) ^ crossbb 
        hashable = circlebb | (crossbb << self.bit_length) 
        if move is None:
            hashables.add(hashable)
        else:
            x, y = y, x
            hashables[hashable] = self.xy_to_move(x, y)
    return hashables  

BitBoard3x3.calc_legcalc_same_hashables = calc_same_hashables

count_linemark が True の処理を削除するメソッド

__init__、setmark_by_move、is_winner メソッドは count_linemark の値によって異なる処理を行う ので、下記のプログラムのように count_linemark が True の処理を削除 します。なお、__init__ メソッドに関しては 下記のような修正 も行ないました。count_linemark が True の場合の処理の削除については難しい点はないと思いますので説明や修正箇所は省略します。

• 1 行目：3 x 3 のサイズに限定し、count_linemark が True の場合の処理は削除することにしたので、仮引数 board_size と count_linemark を削除した。ただし、Marubatsu クラスの initialize_board メソッドで BitBoard3x3 クラスのインスタンスを作成する際 に 実引数にゲーム盤のサイズを記述する ので、それらの仮引数を削除すると エラーが発生する。そこで、以前の記事で説明した 可変長引数 *args と **kwargs を追加 して エラーが発生しないようにした
• 2、3 行目：BOARD_SIZE と bit_length 属性に直接 3 と 9 を代入するようにした

 1  def __init__(self, *args, **kwargs):
 2      self.BOARD_SIZE = 3
 3      self.bit_length = 9
 4      self.board = [0, 0]
 5  
 6  BitBoard3x3.__init__ = __init__
 7  
 8  def setmark_by_move(self, move, mark):
 9      if mark == self.EMPTY:
10          self.board[self.CIRCLE] &= ~0 ^ move
11          self.board[self.CROSS] &= ~0 ^ move
12      else:
13          self.board[mark] |= move
14  
15  BitBoard3x3.setmark_by_move = setmark_by_move
16  
17  def is_winner(self, player, last_move):
18      x, y = self.move_to_xy(last_move)
19      colmasks = [0b000000111, 0b000111000, 0b111000000]
20      rowmasks = [0b001001001, 0b010010010, 0b100100100]
21      diamask1 = 0b100010001
22      diamask2 = 0b001010100
23      colmask = colmasks[x]
24      rowmask = rowmasks[y]
25      board = self.board[player]
26      if board & colmask == colmask or board & rowmask == rowmask:
27          return True
28      # 左上から右下方向の判定
29      if x == y and board & diamask1 == diamask1:
30          return True
31      # 右上から左下方向の判定
32      if x + y == self.BOARD_SIZE - 1 and board & diamask2 == diamask2:
33          return True
34  
35      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
36      return False    
37  
38  BitBoard3x3.is_winner = is_winner

行番号のないプログラム

def __init__(self, *args, **kwargs):
    self.BOARD_SIZE = 3
    self.bit_length = 9
    self.board = [0, 0]
        
BitBoard3x3.__init__ = __init__

def setmark_by_move(self, move, mark):
    if mark == self.EMPTY:
        self.board[self.CIRCLE] &= ~0 ^ move
        self.board[self.CROSS] &= ~0 ^ move
    else:
        self.board[mark] |= move
        
BitBoard3x3.setmark_by_move = setmark_by_move

def is_winner(self, player, last_move):
    x, y = self.move_to_xy(last_move)
    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    

BitBoard3x3.is_winner = is_winner

修正箇所

-def __init__(self, board_size=3, count_linemark=False):
+def __init__(self, *args, **kwargs):
-   self.BOARD_SIZE = board_size
+   self.BOARD_SIZE = 3
-   self.bit_length = self.BOARD_SIZE ** 2
+   self.bit_length = 9
    self.board = [0, 0]
        
BitBoard3x3.__init__ = __init__

def setmark_by_move(self, move, mark):
    if mark == self.EMPTY:
        self.board[self.CIRCLE] &= ~0 ^ move
        self.board[self.CROSS] &= ~0 ^ move
    else:
        self.board[mark] |= move
        
BitBoard3x3.setmark_by_move = setmark_by_move

def is_winner(self, player, last_move):
    x, y = self.move_to_xy(last_move)
    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    

BitBoard3x3.is_winner = is_winner

参照テーブルの計算と利用

BitBoard3x3 クラスで 利用している参照テーブル は popcount の参照テーブル だけではありません。count_markpats メソッドでは下記の masklist に代入した 各直線のビットマスクの一覧 を利用した計算を行いますが、このビットマスクの一覧は あらかじめ計算した値を毎回利用 するのでこれも 参照テーブル です。

    masklist = [
        0b000000111, # 0 列のビットマスク
        0b000111000, # 1 列のビットマスク
        0b111000000, # 2 列のビットマスク
        0b001001001, # 0 行のビットマスク
        0b010010010, # 1 行のビットマスク
        0b100100100, # 2 行のビットマスク
        0b100010001, # 対角線 1 のビットマスク
        0b001010100, # 対角線 2 のビットマスク
    ]

現状では上記の masklist への参照テーブルの代入処理 を count_markpats の中 で行っていますが、毎回この代入処理を行うのは無駄 なので、別の所で代入することにします。これらの 参照テーブルの計算と代入 処理を どこに記述すれば良いか について少し考えてみて下さい。

参照テーブルの記録の方法

__init__ メソッド内で 参照テーブル を 特定の属性に代入 するという方法を考えた人がいるかもしれませんが、その方法では実装しないほうが良い でしょう。その理由は、現状の Marubatsu クラスでは ゲームを新しく開始する際 に 下記の処理を行う ため、ゲームを新しく開始するたび に 参照テーブルを作り直す という 無駄な処理 が行われてしまうからです。

• restart メソッドを呼び出す
• restart メソッド内から呼び出される initialize_board メソッドで下記のプログラムのように ゲーム盤を表すクラスのインスタンスを作成 するという処理を行う
• BitBoard3x3 クラスの __init__ メソッドが呼び出され、その中で 参照テーブルを計算 するという処理が行われる

def initialize_board(self):
    self.board = self.boardclass(self.BOARD_SIZE, *self.args, **self.kwargs)
略

別の方法として、参照テーブルを以前の記事で説明した クラス属性に代入 するという方法があります。クラス属性への代入処理 は クラスの定義を実行した際に一度だけ行われる ため、何度も実行されるという問題は発生しません。

具体的には下記のプログラムのように ptable というクラス属性に popcount の参照テーブル を計算して代入し、marklist というクラス属性に 各直線のビットマスクの参照テーブル を代入することにします。

class BitBoard3x3(BitBoard):
    ptable = [i.bit_count() for i in range(1 << 9)]
    masklist = [
        0b000000111, # 0 列のビットマスク
        0b000111000, # 1 列のビットマスク
        0b111000000, # 2 列のビットマスク
        0b001001001, # 0 行のビットマスク
        0b010010010, # 1 行のビットマスク
        0b100100100, # 2 行のビットマスク
        0b100010001, # 対角線 1 のビットマスク
        0b001010100, # 対角線 2 のビットマスク
    ]

ただし、本記事では既に BitBoard3x3 クラスのメソッドをいくつか定義済 なので、上記のプログラムを BitBoard3x3 クラスを再定義 すると 先程定義したメソッドが無効 になってしまうので、今回の記事では下記のプログラムで BitBoard3x3 クラスの ptable と masklist 属性に 参照テーブルを代入 することにします。

BitBoard3x3.ptable = [i.bit_count() for i in range(1 << 9)]
BitBoard3x3.masklist = [
    0b000000111, # 0 列のビットマスク
    0b000111000, # 1 列のビットマスク
    0b111000000, # 2 列のビットマスク
    0b001001001, # 0 行のビットマスク
    0b010010010, # 1 行のビットマスク
    0b100100100, # 2 行のビットマスク
    0b100010001, # 対角線 1 のビットマスク
    0b001010100, # 対角線 2 のビットマスク
]

count_markpats メソッドの定義

次に、上記の参照テーブルを利用 する count_markpats メソッドを下記のプログラムのように定義します。BitBoard クラスからの修正箇所 は多いですが、難しくはないので count_linemark が True の場合の処理の削除の修正箇所は省略 しました。

• count_linemarks が True の場合の処理をすべて削除する
• 5 行目の前にあったビットマスクの一覧を masklist に代入する処理はクラス属性に代入済なので削除する
• 5 行目：masklist を self.masklist に修正する
• 6、7 行目：popcount の計算を self.ptable に代入された参照テーブルを利用して計算するように修正する

 1  from collections import defaultdict
 2  
 3  def count_markpats(self, turn, last_turn):
 4      markpats = defaultdict(int)
 5      for mask in self.masklist:
 6          turncount = self.ptable[self.board[turn] & mask]
 7          lastturncount = self.ptable[self.board[last_turn] & mask]
 8          emptycount = self.BOARD_SIZE - turncount - lastturncount
 9          markpats[(lastturncount, turncount, emptycount)] += 1
10  
11      return markpats    
12  
13  BitBoard3x3.count_markpats = count_markpats

行番号のないプログラム

from collections import defaultdict

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)
    for mask in self.masklist:
        turncount = self.ptable[self.board[turn] & mask]
        lastturncount = self.ptable[self.board[last_turn] & mask]
        emptycount = self.BOARD_SIZE - turncount - lastturncount
        markpats[(lastturncount, turncount, emptycount)] += 1

    return markpats    

BitBoard3x3.count_markpats = count_markpats

修正箇所

from collections import defaultdict

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)
-   masklist = [
-       0b000000111, # 0 列のビットマスク
-       0b000111000, # 1 列のビットマスク
-       0b111000000, # 2 列のビットマスク
-       0b001001001, # 0 行のビットマスク
-       0b010010010, # 1 行のビットマスク
-       0b100100100, # 2 行のビットマスク
-       0b100010001, # 対角線 1 のビットマスク
-       0b001010100, # 対角線 2 のビットマスク
-   ]
-   for mask in masklist:
+   for mask in self.masklist:
-       turncount = (self.board[turn] & mask).bit_count()
+       turncount = self.ptable[self.board[turn] & mask]
-       lastturncount = (self.board[last_turn] & mask).bit_count()
+       lastturncount = self.ptable[self.board[last_turn] & mask]
        emptycount = self.BOARD_SIZE - turncount - lastturncount
        markpats[(lastturncount, turncount, emptycount)] += 1

    return markpats    

BitBoard3x3.count_markpats = count_markpats

処理速度の比較

参照テーブルを利用した count_markpats の処理速度 を、下記のプログラムで 参照テーブルを利用しない BitBoard クラスの場合と 比較してみる ことにします。

bb1 = BitBoard()
bb2 = BitBoard3x3()

%timeit bb1.count_markpats(bb1.CIRCLE, bb1.CROSS)
%timeit bb2.count_markpats(bb2.CIRCLE, bb2.CROSS)

実行結果

2.73 μs ± 11 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.62 μs ± 17.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

実行結果から、参照テーブルを利用する BitBoard3x3 クラスの方が 少しだけ処理速度が速くなる ことが確認できました。ただし、その差はほとんどない ので、この後で行う benchmark の結果はほとんど変わらないでしょう。

下記のプログラムで BitBoard3x3 を利用した場合の処理速度を benchmark で計測することにします。なお、仮引数 count_linemark を削除 したのでこれまでと異なり count_linemark に関する処理は行いません。

from util import benchmark

boardclass = BitBoard3x3
print(f"boardclass: {boardclass.__name__}")
benchmark(mbparams={"boardclass": boardclass})

実行結果

boardclass: BitBoard3x3
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 21890.19it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

ai14s VS ai2
100%|██████████| 50000/50000 [00:15<00:00, 3215.41it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.1%    0.0%   11.9%
total   93.5%    0.0%    6.5%

ai_abs_dls
  8.1 ms ±   0.6 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は 前回記事の benchmark の結果との比較 です。表からわかるように、処理速度 は先ほど推測したように ほとんど変わらない ことが確認できます。なお、下記の結果では若干遅くなっていますが、もう一度実行した所処理速度が若干速くなったので、誤差の範囲 だと思います。

	ai2 VS ai2	ai14s VS ai2	ai_abs_dls
前回の結果	22457.83 回/秒	3129.02 回/秒	7.9 ms
修正後の結果	21890.19 回/秒	3215.41 回/秒	8.1 ms

参照テーブルを利用した judge メソッドの改良

現状の BitBoard クラスの judge メソッドから呼び出される is_winner メソッドでは、以下の手順で判定 を行っています。

• 直前に着手した (x, y) のマスの座標を move_to_xy メソッドで計算 する
• (x, y) の座標 から x 列と y 行のマスのマークを計算 するための ビットマスクを計算 し、x 列 と y 列にマークが並んでいるかの判定を行う
• 対角線上のマスに着手したどうかを判定 し、着手していた場合は対角線のビットマスクを利用して判定を行う

def is_winner(self, player, last_move):
    x, y = self.move_to_xy(last_move)
    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

上記の手順では move_to_xy メソッド で (x, y) の座標を計算 する処理と、x == y や x + y == self.BOARD_SIZE - 1 の条件式で 対角線上のマスに着手が行われたかどうかを判定 する 処理が必要 になります。

これらの処理を行わないようにする工夫 として、合法手ごと に 必要となるビットマスクの一覧 を記録した 参照テーブルを計算しておく という方法が考えられるので、その方法でプログラムを改良することにします。

合法手ごとのビットマスクの一覧の参照テーブルの仕様

合法手ごと の ビットマスクの一覧 の 参照テーブル は、下記のような dict として move_to_masklist という クラス変数に代入 することにします

• dict の キー を 合法手を表す BitBoard の座標 とする
• キーの値 を、その合法手を着手した際に 必要となるビットマスクの一覧 を表す list とする

下記はその move_to_masklist 属性 に 参照テーブル計算して代入 するプログラムです。この処理は 1 度だけ行う ので 処理速度は重視せず、わかりやすさを重視 したプログラムにしました。

• 1 ~ 4 行目：各列、各行、対角線のビットマスクのデータを変数に代入する。is_winner メソッド内に記述していたものと同じ
• 5 行目：参照テーブルを代入する move_to_masklist を空の dict で初期化する
• 6 ~ 13 行目：2 重の for 文で 3 x 3 のすべての合法手に対する繰り返し処理を行う
• 8 行目：(x, y) の BitBoard の座標を計算する⁵
• 9 行目：move_to_masklist の (x, y) の座標に対するキーの値に、x 列と y 行のビットマスクを要素とする list を代入する
• 10 ~ 13 行目：(x, y) が対角線上のマスであるかどうかを判定し、対角線上のマスである場合はその対角線のビットマスクを参照テーブルに追加する
• 15 行目：計算した参照テーブルを BitBoard3x3 クラスのクラス属性に代入する

 1  colmasks = [0b000000111, 0b000111000, 0b111000000]
 2  rowmasks = [0b001001001, 0b010010010, 0b100100100]
 3  diamask1 = 0b100010001
 4  diamask2 = 0b001010100
 5  move_to_masklist = {}
 6  for x in range(3):
 7      for y in range(3):
 8          move = 1 << (y + 3 * x)
 9          move_to_masklist[move] = [colmasks[x], rowmasks[y]]
10          if x == y:
11              move_to_masklist[move].append(diamask1)
12          if x + y == 2:
13              move_to_masklist[move].append(diamask2)
14  
15  BitBoard3x3.move_to_masklist = move_to_masklist

行番号のないプログラム

colmasks = [0b000000111, 0b000111000, 0b111000000]
rowmasks = [0b001001001, 0b010010010, 0b100100100]
diamask1 = 0b100010001
diamask2 = 0b001010100
move_to_masklist = {}
for x in range(3):
    for y in range(3):
        move = 1 << (y + 3 * x)
        move_to_masklist[move] = [colmasks[x], rowmasks[y]]
        if x == y:
            move_to_masklist[move].append(diamask1)
        if x + y == 2:
            move_to_masklist[move].append(diamask2)

BitBoard3x3.move_to_masklist = move_to_masklist

judge メソッドの修正

参照テーブルを利用した判定処理 は 簡潔に記述できる ので、is_winner メソッドを廃止 し、その処理を下記のプログラムのように judge メソッド内に直接記述 することにします。

• 4 行目：毎回 move_count < self.BOARD_SIZE * 2 - 1 を計算するのは無駄なので、move_count < 5 に修正した
• 7 行目：直前に着手を行ったプレイヤーのビットボードを board に代入する
• 8 ~ 10 行目：参照テーブルから last_move の着手に対する勝敗判定に必要なビットマスクの一覧を計算して繰り返し処理を行う
• 9、10 行目：以前の記事で説明した方法でビットマスクが表す直線上に last_turn のマークが並んでいるかどうかを判定し、並んでいる場合は lats_turn を返すことで last_turn の手番が勝利したことを計算する

 1  from marubatsu import Marubatsu
 2  
 3  def judge(self, last_turn, last_move, move_count):
 4      if move_count < 5:
 5          return Marubatsu.PLAYING
 6      # 直前に着手を行ったプレイヤーの勝利の判定
 7      board = self.board[last_turn]
 8      for bitmask in self.move_to_masklist[last_move]:
 9          if board & bitmask == bitmask:
10              return last_turn
11      # 引き分けの判定
12      if move_count == self.bit_length:
13          return Marubatsu.DRAW
14      # 上記のどれでもなければ決着がついていない
15      else:
16          return Marubatsu.PLAYING    
17  
18  BitBoard3x3.judge = judge

行番号のないプログラム

from marubatsu import Marubatsu

def judge(self, last_turn, last_move, move_count):
    if move_count < 5:
        return Marubatsu.PLAYING
    # 直前に着手を行ったプレイヤーの勝利の判定
    board = self.board[last_turn]
    for bitmask in self.move_to_masklist[last_move]:
        if board & bitmask == bitmask:
            return last_turn
    # 引き分けの判定
    if move_count == self.bit_length:
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING    
    
BitBoard3x3.judge = judge

修正箇所

from marubatsu import Marubatsu

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

処理速度の計測

下記のプログラムで 修正後の処理速度を benchmark で計測 することにします。

print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
benchmark(mbparams={"boardclass": boardclass, "count_linemark": count_linemark})

実行結果

boardclass: BitBoard3x3
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 24220.47it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

ai14s VS ai2
100%|██████████| 50000/50000 [00:15<00:00, 3238.18it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.1%    0.0%   11.9%
total   93.5%    0.0%    6.5%

ai_abs_dls
  7.9 ms ±   1.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は先ほどの結果に 上記の実行結果を加えた表 です。表からわかるように、この修正によって 処理速度が若干高速化 することが確認できました。

	ai2 VS ai2	ai14s VS ai2	ai_abs_dls
前回の結果	22457.83 回/秒	3129.02 回/秒	7.9 ms
最初の修正後の結果	21890.19 回/秒	3215.41 回/秒	8.1 ms
上記の修正の結果	24220.47 回/秒	3238.18 回/秒	7.9 ms

ビット演算を利用した popcount の補足

下記の内容は以前の記事の補足です。興味がない方は読み飛ばしても構いません。

以前の記事で紹介した下記の ビット演算を利用した popcount の計算 は 改良を行うことができる ようです。

def popcount3(b):
    masktable_even = {
        1: 0b01010101010101010101010101010101,
        2: 0b00110011001100110011001100110011,
        4: 0b00001111000011110000111100001111,
        8: 0b00000000111111110000000011111111,
        16: 0b00000000000000001111111111111111,
    }
    masktable_odd = {
        1: 0b10101010101010101010101010101010,
        2: 0b11001100110011001100110011001100,
        4: 0b11110000111100001111000011110000,
        8: 0b11111111000000001111111100000000,
        16: 0b11111111111111110000000000000000,       
    }
    blength = b.bit_length()
    c = b
    bwidth = 1
    while bwidth <= blength:
        c = (c & masktable_even[bwidth]) + \
            ((c & masktable_odd[bwidth]) >> bwidth)
        bwidth *= 2
    return c

下記のプログラムは 改良版と比較できる ように、上記のプログラムを 変数 c を利用しない ようにし、while 文による繰り返し処理を行わない ように修正したプログラムです。また、2 進数の表記は長いので、下記のプログラムでは ビットマスクを 16 進数で表記 しました。16 進数については下記のリンク先を参照して下さい。

def popcount3(b):
    b = (b & 0x55555555) + ((b & 0xaaaaaaaa) >> 1)
    b = (b & 0x33333333) + ((b & 0xcccccccc) >> 2)
    b = (b & 0x0f0f0f0f) + ((b & 0xf0f0f0f0) >> 4)
    b = (b & 0x00ff00ff) + ((b & 0xff00ff00) >> 8)
    return (b & 0x0000ffff) + ((b & 0x0000ffff) >> 16)

下記は上記の改良版で、関数名を popcount6 としました。上記と比較して、明らかに ビットマスクとの AND 演算が大幅に減っている ので 処理速度が高速 になります。

def popcount6(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x3333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    return x & 0x0000007f

なお、この改良方法で正しい計算が行われる理由については長くなるので下記の解説ページを参照して下さい。

下記のプログラムは 以前の記事と同じ方法でいくつかのビット列の popcount を popcount3 と popcount6 で計算し、その処理速度を計測するプログラムです。

blist = [
  0b0,
  0b1,
  0b100000000,
  0b10000000000000000000000000000000,
  0b11,
  0b100000001,
  0b10000000000000000000000000000001,
  0b11111,
  0b101010101,
  0b10000001000000001000000001000001,
  0b111111111,
  0b11111111111111111111111111111111,
]

print("popcount3")
print("                            data | pc | bl | time")
for b in blist:
    popcount = popcount3(b)
    print(f"{b:32b} | {popcount:2} | {b.bit_length():2} | ", end="")
    %timeit popcount3(b)
    
print("popcount6")
print("                            data | pc | bl | time")
for b in blist:
    popcount = popcount6(b)
    print(f"{b:32b} | {popcount:2} | {b.bit_length():2} | ", end="")
    %timeit popcount6(b)

実行結果

popcount3
                            data | pc | bl | time
                               0 |  0 |  0 | 441 ns ± 4.05 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                               1 |  1 |  1 | 440 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       100000000 |  1 |  9 | 492 ns ± 14.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000000000000000000000000000000 |  0 | 32 | 619 ns ± 19.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                              11 |  2 |  2 | 481 ns ± 6.46 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       100000001 |  2 |  9 | 550 ns ± 1.91 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000000000000000000000000000001 |  1 | 32 | 614 ns ± 1.84 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                           11111 |  5 |  5 | 474 ns ± 1.04 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       101010101 |  5 |  9 | 561 ns ± 4.84 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000001000000001000000001000001 |  3 | 32 | 636 ns ± 13.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       111111111 |  9 |  9 | 574 ns ± 2.35 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
11111111111111111111111111111111 | 16 | 32 | 668 ns ± 6.93 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
popcount6
                            data | pc | bl | time
                               0 |  0 |  0 | 335 ns ± 12.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                               1 |  1 |  1 | 364 ns ± 6.02 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       100000000 |  1 |  9 | 390 ns ± 1.42 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000000000000000000000000000000 |  0 | 32 | 376 ns ± 3.66 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                              11 |  2 |  2 | 363 ns ± 3.12 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       100000001 |  2 |  9 | 424 ns ± 4.29 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000000000000000000000000000001 |  1 | 32 | 395 ns ± 2.48 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                           11111 |  5 |  5 | 363 ns ± 0.689 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       101010101 |  5 |  9 | 433 ns ± 9.82 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000001000000001000000001000001 |  4 | 32 | 515 ns ± 3.76 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       111111111 |  9 |  9 | 425 ns ± 3.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
11111111111111111111111111111111 | 30 | 32 | 515 ns ± 2.18 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は上記の実行結果をまとめた表で、すべての場合で popcount6 のほうが処理速度が高速 になることが確認できます。

ビット列	pc3	pc6
0b0	441 ns	335 ns
0b1	440 ns	364 ns
0b100000000	492 ns	390 ns
0b10000000000000000000000000000000	619 ns	376 ns
0b11	481 ns	363 ns
0b100000001	550 ns	424 ns
0b10000000000000000000000000000001	614 ns	395 ns
0b11111	474 ns	363 ns
0b101010101	561 ns	433 ns
0b111111111	636 ns	515 ns
0b10000001000000001000000001000001	574 ns	425 ns
0b11111111111111111111111111111111	668 ns	515 ns

ただし popcount6 は、参照テーブル を利用した方法や、bit_count メソッド を利用した方法よりも 処理速度が速くなることはない ので、本記事ではこの改良方法は利用しないことにします。

今回の記事のまとめ

今回の記事では 参照テーブルを利用 した popcount の計算 について説明しました。また、3 x 3 の大きさに限定 し、いくつかの参照テーブルを利用 した BitBoard3x3 クラスの定義を行い、処理速度が若干向上 することを示しました。

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

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

次回の記事

1. 作成した参照テーブルを代入する変数名は popcount table から命名しました ↩

2. コンピューターのデータの単位は、1 KB = $2^{10}$ バイト、1 MB = $2^{20}$ バイト、1 GB = $2^{30}$ のように、単位が一つ大きくなるごとに $2^{10} = 1024$ 倍になります ↩

3. 以前の記事で popcount4 までの関数を作成しましたので popcount5 と命名しました ↩

4. 名前の 32 は 32 ビットまでの popcount を計算できるという意味です ↩

5. xy_to_move メソッドを利用していないのは、xy_to_move は BitBoard3x3 クラスのインスタンスからでないと呼び出せないためです。xy_to_move メソッドを利用して計算したい場合は、xy_to_move をクラスメソッドとして定義し直すと良いでしょう ↩