Pythonで〇×ゲームのAIを一から作成する　その213　ビット列の pop count の計算によるマークのパターンの計算

Posted at 2026-01-25

目次と前回の記事

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

BitBoard クラスの `count_markpats` の実装

今回の記事では ai14s を実行する際に必要となる、局面のマークのパターンの一覧を計算 する count_markpats メソッドの BitBoard クラスでの実装を行います。

なお、count_linemark が True の場合の処理は他のゲーム盤を表すクラスと同様なので説明を省略します。

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

必要な処理

count_markpats では、各行、列、対角線の 8 つの直線上のマークの数を数える という処理を行います。例えば 0 列 のマークのパターンの計算は、(0, 0)、(0, 1)、(0, 2) のマスに 〇と × のマークがいくつ配置されるかを数える という処理を行います。
他の直線上 のマークのパターンの 計算も同様 で、特定の 3 つのマス に 〇と × のマークがいくつ配置されているかを数える 処理を行います。

また、〇のマークと × のマーク を 数える処理はほぼ同じ なので、今回の記事では最初に 0 列に〇のマークがいくつ配置されているかを数える 方法をいくつか紹介し、その処理速度を比較することにします。

確認のためのビットボードの作成

実装が正しく行えているかどうかを判定 するために、下記のプログラムで 0 列 に マークが 0、1、2、3 個配置 された BitBoard クラスのインスタンスを作成します。また、作成したビットボードを要素として持つ list を bblist に代入 します。

from marubatsu import BitBoard

bb0 = BitBoard()               # 0 列に配置された 〇 の数が 0 個のビットボード
bb1 = BitBoard()               # 0 列に配置された 〇 の数が 1 個のビットボード
bb1.setmark(0, 0, bb1.CIRCLE)
bb2 = BitBoard()               # 0 列に配置された 〇 の数が 2 個のビットボード
bb2.setmark(0, 0, bb2.CIRCLE)
bb2.setmark(0, 1, bb2.CIRCLE)
bb3 = BitBoard()               # 0 列に配置された 〇 の数が 3 個のビットボード
bb3.setmark(0, 0, bb3.CIRCLE)
bb3.setmark(0, 1, bb3.CIRCLE)
bb3.setmark(0, 2, bb3.CIRCLE)

bblist = [bb0, bb1, bb2, bb3]

定義する関数の仕様

今回の記事では、いくつかの方法でビットボードの 0 列の〇のマークを数える 関数を定義しますが、それらの 関数の仕様 は以下のようにします。

関数名 は countmarkx とする。ただし、最後の x には数字 が入る
仮引数 bb に ビットボードを代入 する
bb の 0 列の〇のマークの数 を数えて 返り値として返す

`getmark` を用いた実装

指定した座標のマスのマークを参照 する getmark を利用した下記のプログラムで countmark1 を定義することができます。

2 行目：マークの数を数える変数 count を 0 で初期化する
3 ~ 5 行目：(0, 0)、(0, 1)、(0, 2) の順で getmark で〇が存在する場合に count を 1 増やす処理を行う
6 行目：〇のマークの数を表す count を返り値として返す

1  def countmark1(bb):
2      count = 0
3      for x, y in [(0, 0), (0, 1), (0, 2)]:
4          if bb.getmark(x, y) == bb.CIRCLE:
5              count += 1
6      return count

行番号のないプログラム

def countmark1(bb):
    count = 0
    for x, y in [(0, 0), (0, 1), (0, 2)]:
        if bb.getmark(x, y) == bb.CIRCLE:
            count += 1
    return count

下記のプログラムで countmark1 を呼び出して bblist の各ビットボードの 0 列の〇のマークの数を数える と、実行結果から正しい計算が行われることが確認できます。

for bb in bblist:
    print(countmark1(bb))

実行結果

`countmark1` の性質

getmark を利用した実装方法は わかりやすいという利点 がありますが、前回の記事で説明したのと同様の理由で 処理速度が遅いという欠点 があります。下記は countmark1 の処理速度を計測 するプログラムで、いずれも約 1000 ns = 約 1 μs の処理時間がかかることが確認できます。この結果 をこの後で実装する 別の方法の処理速度と比較 することにします。

for bb in bblist:
    %timeit countmark1(bb)

実行結果

987 ns ± 12.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
966 ns ± 7.81 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
916 ns ± 3.53 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
863 ns ± 4.05 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

上記で〇のマークが配置されている数が多いほど処理時間が若干減る理由は、getmark の処理が下記の手順で行われるからです。

〇のビットボードを調べ、〇が配置されてれば self.CIRCLE を返す
× のビットボードを調べ、× が配置されていれば self.CROSS を返す
上記のいずれでもない場合は self.EMPTY を返す

〇が配置されている場合は上記の手順 1 の処理だけで済みますが、そうでない場合は手順 2 の処理が必要になるため処理時間が多くなります。

popcount の計算による実装

BitBoard クラスの ビットボード では 0 列の (0, 0)、(0, 1)、(0, 2) のマスは 0、1、2 番のビットで表現 されるので、〇のマークの数 は 〇を表すビットボード の 0、1、2 番 のビットの中で 値が 1 であるビットの数を数える という処理で計算できます。

ビット列 の中の 1 のビットの数を数える という処理の事を population count と呼び、略して popcount や popcnt のように 表記することが多い ようです。また、bit count のように表記¹することもあるようです。本記事では popcount と表記 することにします。

以前の記事で説明したように、ビット列 と、そのビット列の中で 調べたいビットのみを 1 としたビットマスク との AND 演算 を行うことで、以下のような値を計算 することができます。

ビットマスクが 1 のビット に対しては、元のビット列と同じ値が計算 される
それ以外のビット に対しては すべて 0 が計算 される

従って、〇のビットボード と、0、1、2 番のビットのみが 1 となる 0b111 との AND 演算 を行うことで、〇のビットボード の 0、1、2 番のビット のうち 1 であるビットのみが 1 となる 値が計算 されるので、その値の popcount を計算 することで 0 列の〇のマークの数を計算 することができます。

まだ定義していませんが、実引数に記述した ビット列の popcount を計算 して返す popcount という 関数を定義 することで、下記のプログラムで bb に代入 された ビットボード の 0 列の〇のマークの数を数える 処理を行うことができます。なお、bb.board[0] は 〇のマークを表すビットボード です。

print(popcount(bb.board[0] & 0b111))

そこで、本記事では popcount を計算するアルゴリズム をいくつか紹介し、それぞれのアルゴリズムの 処理速度を計測して比較 することにします。

定義する関数の仕様

BitBoard クラスのビットボードの 0 列 のデータは 0、1、2 番のビットに記録 されるので、0 列の〇のマークを数える場合 は 0、1、2 番のビットだけに注目 して 1 のビットの数を数えれば十分 です。

ただし、他の直線上のマス を表す ビットの番号 は 上記とは異なる ので、任意のビット列の popcount を計算 する以下のような 関数を定義 することにします。

関数名 は popcountx とする。ただし、最後の x には数字 が入る
仮引数 b に popcount を計算する ビット列を表す整数型のデータを代入 する
b の popcount を計算 して 返り値として返す

なお、以前の記事で説明したように Python では 負の整数のビット列 は 先頭に 1 が無限に続く値 とみなされるので、popcount は無限大になります。そのため、上記の b には 0 以上の整数が代入された場合の計算 を行うことにします。

Python 以外の多くのプログラム言語では負の整数を有限の長さのビット列で表現するので、負の整数のビット列の popcount を計算することができます。

popcount の処理の確認で利用する値の設定

次に、この後で定義する popcount を計算する 関数が正しく動作するかどうかを確認 したり、処理速度を計測 するための ビット列 として、下記の表のビット列 を blist という変数に代入 して利用することにします。

ビット列	popcount	ビット長
`0b0`	0	0
`0b1`	1	1
`0b100000000`	1	9
`0b10000000000000000000000000000000`	1	32
`0b11`	2	2
`0b100000001`	2	9
`0b10000000000000000000000000000001`	2	32
`0b11111`	5	5
`0b101010101`	5	9
`0b10000001000000001000000001000001`	5	32
`0b111111111`	9	9
`0b11111111111111111111111111111111`	32	32

popcount を計算する アルゴリズム は、処理速度 が popcount や ビット長に影響される 場合があるので、上記では popcount が 1、2、5 のビット列 として、異なるビット長 のデータを 3 つずつ用意 しました。また、ビット長が 9、32 のビット列 として、異なる popcount のデータを 4 つずつ用意 しました。

また、3 x 3 の〇× ゲームのゲーム盤の マスの数は 9 なので先頭の 0 を除いたビット列のビット数を表す ビット長が 9 のビット列の popcount が計算できれば十分 ですが、4 x 4 以上 のゲーム盤を表すビット列に対しても popcount の計算を行うことができる ように、上記のビット列では ビット長が 32 のビット列 を含めました。

興味がある方は上記の表以外のビット列を用意して計算を行ってみて下さい。

上記のビット長が 32 のビット列のように、2 進数で長いビット長のデータを記述すると表記が長くなります。そのため、ビット列を記述する場合は、2 進数を 1/4 の長さで表記できる 16 進数で表記するのが一般的です。例えば上記の最後のビット列は 0xffffffff のように短く表記できます。

ただし、本記事では 16 進数について詳しく説明していない点と、16 進数で表記した場合は popcount がいくつであるかがわかりづらくなるので 2 進数でビット列を表記することにします。

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

下記はそれらのデータを変数に代入するプログラムです。

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

1 つずつビットを数える方法

誰でも思いつくであろう方法として、0 番のビットから一つずつビットが 1 であるかどうかを数える という方法があります。下記はその方法で処理を行う popcount1 の定義を行うプログラムです。

2 行目：1 のビットの数を数える変数 count を 0 で初期化する
3 行目：先頭の 0 を除いたビット列の長さは以前の記事で説明した bit_length メソッドで計算できるので、その数だけ繰り返し処理を行う
4、5 行目：i 番のビットの値は 1 << i で計算できるので、その値と b との AND 演算を行うことで、i 番のビットが 1 であるかどうかを判定し、1 の場合に count を 1 増やす処理を行う
6 行目：〇のマークの数を表す count を返り値として返す

1  def popcount1(b):
2      count = 0
3      for i in range(b.bit_length()):
4          if b & (1 << i):
5              count += 1
6      return count

行番号のないプログラム

def popcount1(b):
    count = 0
    for i in range(b.bit_length()):
        if b & (1 << i):
            count += 1
    return count

下記は blist の各ビット列 に対する popcount1 の 計算結果と処理速度を計測 するプログラムです。4 行目では print の実引数 に end="" を記述 することで、5 行目の 処理速度の表示 を 4 行目の表示と同じ行に表示 するように工夫しました。また、表示が長くなるので 2 進数の先頭の 0b の表示は省略 しました。実行結果から popcount が正しく計算される ことが確認できます。

1  print("                            data | pc | bl | time")
2  for b in blist:
3      popcount = popcount1(b)
4      print(f"{b:32b} | {popcount:2} | {b.bit_length():2} | ", end="")
5      %timeit popcount1(b)

行番号のないプログラム

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

実行結果

                            data | pc | bl | time
                               0 |  0 |  0 | 149 ns ± 1.7 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                               1 |  1 |  1 | 220 ns ± 2.42 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       100000000 |  1 |  9 | 623 ns ± 2.56 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000000000000000000000000000000 |  1 | 32 | 2.76 μs ± 103 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
                              11 |  2 |  2 | 290 ns ± 2.47 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       100000001 |  2 |  9 | 645 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000000000000000000000000000001 |  2 | 32 | 2.76 μs ± 95 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
                           11111 |  5 |  5 | 470 ns ± 2.27 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       101010101 |  5 |  9 | 666 ns ± 4.39 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000001000000001000000001000001 |  5 | 32 | 2.8 μs ± 10.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
                       111111111 |  9 |  9 | 713 ns ± 10.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
11111111111111111111111111111111 | 32 | 32 | 3.1 μs ± 20.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

下記は上記の実行結果を ビット長の小さい順 で並べた表です。列の見出しの pc は popcount、bl はビット長 を表します。

ビット列	pc	bl	処理速度
`0b0`	0	0	149 ns
`0b1`	1	1	220 ns
`0b11`	2	2	290 ns
`0b11111`	5	5	470 ns
`0b100000000`	1	9	623 ns
`0b100000001`	2	9	645 ns
`0b101010101`	5	9	666 ns
`0b111111111`	9	9	713 ns
`0b10000000000000000000000000000000`	1	32	2760 ns
`0b10000000000000000000000000000001`	2	32	2760 ns
`0b10000001000000001000000001000001`	5	32	2800 ns
`0b11111111111111111111111111111111`	32	32	3100 ns

popcount1 では ビット長の数 だけ 繰り返し処理 を行っているので 処理時間 が ビット長にほぼ比例 します、そのことは 上記の表 の 処理時間 が ビット長の約 70 ~ 90 ns 倍 になっていることが確認できます。また、popcount の数 だけ count に 1 を加算 する処理を行うので、同じビット長 の場合は popcount が多い程 処理時間が ほんの少しだけ長くなる ことも確認できます。

従って、1 つずつビットを数える方法 の 処理時間 は以下のようになります。

ビット長にほぼ比例 する
popcount が多くなると処理時間がほんの少し長くなるが、その 影響はビット長と比較すると非常に小さい

RSB を 0 にする計算を利用する方法

前回の記事のノートで a & (a - 1) という演算で、a の RSB（1 である最も番号が低いビット）を 0 にした 値を計算できる ことを説明しました。a に対するこの演算を 1 回行 うと 1 のビットが 1 つずつ減る ので、b &= (b - 1)² という演算を b が（1 のビットが 0 個である）0 になるまで繰り返した数 を計算することで b の popcount を計算 することができます。

下記はそのように popcount2 を定義したプログラムです。

3 行目：b が 0 になるまで繰り返し処理を行う
4、5 行目：count を 1 増やし、b &= (b - 1) によって b の RSB を 0 にする計算を行う

1  def popcount2(b):
2      count = 0
3      while b:
4          count += 1
5          b &= (b - 1)
6      return count

行番号のないプログラム

def popcount2(b):
    count = 0
    while b:
        count += 1
        b &= (b - 1)
    return count

下記は blist の各ビット列 に対する popcount2 の 計算結果と処理速度を計測 するプログラムです。実行結果から popcount が正しく計算されることが確認 できます。

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

実行結果

                            data | pc | bl | time
                               0 |  0 |  0 | 53.4 ns ± 0.389 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                               1 |  1 |  1 | 96.8 ns ± 1 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                       100000000 |  1 |  9 | 96.7 ns ± 0.518 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
10000000000000000000000000000000 |  1 | 32 | 144 ns ± 1.92 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                              11 |  2 |  2 | 142 ns ± 1.41 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                       100000001 |  2 |  9 | 141 ns ± 0.861 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
10000000000000000000000000000001 |  2 | 32 | 244 ns ± 2.43 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                           11111 |  5 |  5 | 277 ns ± 1.24 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       101010101 |  5 |  9 | 394 ns ± 3.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000001000000001000000001000001 |  5 | 32 | 494 ns ± 2.14 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       111111111 |  9 |  9 | 679 ns ± 5.45 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
11111111111111111111111111111111 | 32 | 32 | 2.75 μs ± 97.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

popcount2 では popcount の数だけ繰り返し処理 を行うことから、上記の実行結果では popcount が大きいほど処理時間が長くなる ことが確認できます。

また、popcount が同じ 場合は ビット長が大きいほど処理時間が長くなる ことも確認できます。ただし、popcount2 では popcount が同じ であればビット長が大きくなっても 繰り返しの回数は変わらない ので、このようなことが起きるのは変 です。

そこで、popcount2 の中で行う 処理の処理時間を検証 したところ、Python では int 型 の 加算や減算の処理速度 が、計算結果の値の大きさによって変化する ことが原因であることがわかりました。

下記はそのことを示すプログラムで、いくつかの値 に対して 1 を加算 する処理と、1 を減算 する処理の 処理時間を計測 しています。

for b in [ 0b1, 0b1000, 0b100000, 0b11111111, 0b100000000, 0b100000001]:
    print(f"0b{b - 1:b}")
    %timeit b - 1
    print(f"0b{b + 1:b}")
    %timeit b + 1

実行結果

0b0
22 ns ± 0.557 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b10
21.6 ns ± 0.158 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b111
21.4 ns ± 0.194 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b1001
21.4 ns ± 0.168 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b11111
21.5 ns ± 0.235 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b100001
22 ns ± 1.91 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b11111110
22 ns ± 0.764 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b100000000
22.3 ns ± 1.14 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b11111111
21.7 ns ± 0.149 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b100000001
33.8 ns ± 0.133 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b100000000
21.9 ns ± 0.186 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
0b100000010
34.9 ns ± 0.638 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

実行結果から 計算結果 が 0b0 ~ 0b100000000（=256）の範囲 の値であれば 処理時間は約 22 ns でほぼ同じ ですが、0b100000001 以上 になると 処理時間が約 34 ns のように 約 1.5 倍 になります。また、具体的な数値の検証は行っていませんが、0b100000001 より大きな 特定の値以上 になると さらに処理時間が長くなります 。

Python が内部でどのように加算や減算の処理を行っているかがわからないので確かなことは言えませんが、このようなことが起きるのは、CPU が一度に計算できるデータのビット数が決まっていることが関係しているのではないかと思います。

なお、Python 以外の多くのプログラム言語の場合は、一般的に 64 ビット以下のデータで表現できる整数の加算や減算の処理は、処理速度が変わらないのではないかと思います。

float（浮動小数点数）型の場合は、数値の大きさによって加算や減算の処理速度は変わらないようです。その理由は、Python では表現できる数値の範囲に制限がないためデータサイズが数値の大きさによって変わる int 型と異なり、float 型は常に同じデータサイズである 64 ビットで数値を表現するからです。

下記はそのことを検証するプログラムで、先程と同じ数値を float 型に変換してから 1 を加算と 1 を減算する処理の処理速度を表示すると、いずれも約 40 ns のように処理速度が変わらない事が確認できます。

for b in [ 0b1, 0b1000, 0b100000, 0b11111111, 0b100000000, 0b100000001]:
    b = float(b)
    print(b - 1)
    %timeit b - 1
    print(b + 1)
    %timeit b + 1

実行結果

0.0
40.2 ns ± 1.29 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
2.0
39.2 ns ± 0.264 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
7.0
39.5 ns ± 0.347 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
9.0
39.5 ns ± 0.258 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
31.0
40.2 ns ± 1.11 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
33.0
39.6 ns ± 0.297 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
254.0
39.4 ns ± 0.106 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
256.0
39.4 ns ± 0.245 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
255.0
39.7 ns ± 0.241 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
257.0
39.6 ns ± 0.247 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
256.0
39.5 ns ± 0.318 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
258.0
39.3 ns ± 0.136 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記は先ほどの実行結果を ビット長の小さい順 で並べた表です。列の見出しの pc1 と pc2 は popcount1 と popcount2 の処理速度 を表します。

ビット列	pc	bl	pc1	pc2
`0b0`	0	0	149 ns	53 ns
`0b1`	1	1	220 ns	97 ns
`0b11`	2	2	290 ns	142 ns
`0b11111`	5	5	470 ns	277 ns
`0b100000000`	1	9	623 ns	97 ns
`0b100000001`	2	9	645 ns	141 ns
`0b101010101`	5	9	666 ns	394 ns
`0b111111111`	9	9	713 ns	679 ns
`0b10000000000000000000000000000000`	1	32	2760 ns	144 ns
`0b10000000000000000000000000000001`	2	32	2760 ns	244 ns
`0b10000001000000001000000001000001`	5	32	2800 ns	494 ns
`0b11111111111111111111111111111111`	32	32	3100 ns	2750 ns

上記の表から下記の事が確認できます。

いずれの場合も popcount2 の方が 処理速度が速い
popcount が 0 に近い程 popcount1 よりも処理速度が 大幅に速くなる
ビット長がある程度以上大きい場合は、popcount が ビット長に近づく と処理速度は ほとんど変わらなくなる

従って、RSB を 0 にする方法 の 処理時間 は以下のようになります。

popcount にほぼ比例 する
ビット長が多くなると、処理の途中で 特定の値を超えるような計算が行われる ため 処理速度が若干遅く なる
popcount1 より常に処理速度が速い が、popcount がビット長に近づく と 処理速度はほとんど変わらなくなる ので、popcount が小さい ことが あらかじめわかっている場合 は popcount1 よりも 大幅に処理速度が速い

ビット演算を利用した別の計算方法

ビット演算をうまく利用 することで、大きなビット長 のビット列に対して popcount を高速に計算するアルゴリズム があるので説明します。

アルゴリズムの説明

そのアルゴリズムは以下の通りです。

popcount を計算する ビット列を b とした場合に、下記の手順で b の popcount を計算することができる。

ビットの範囲 を表す bwidth を 1 とする
以下のような b と同じビット長 の ビット列 c を計算する
- b と c を bwidth の幅のビットで均等に分割 する
- 分割したそれぞれの範囲 の c のビットの 2 進数の値 が、同じ範囲の b のビットの 1 のビットの数になる ようにする
bwidth を 2 倍 にする
bwidth が b のビット長以下 の場合は 手順 2 に戻る
超えている場合 は c に b の popcount が計算 されている

おそらくこのアルゴリズムを知らない方は意味がまったく分からないのではないかと思いますので、上記のアルゴリズムを popcount が 4 である 0b10001101 という 8 ビットのビット列 を具体例に挙げて説明します。

`0b10001101` に対して行われる処理の説明

手順 1 では bwidth が 1 になるので、次の 手順 2 では bwidth が 1 になります。

下図は b と、b と同じビット長 の c を図示 したものです。図の縦棒は b と c を 1 の幅のビット で 均等に分割 することを表します。

c の 分割した各ビット には、同じ番号 の b の 1 のビットの数 を記録します。b のビットが 1 の場合は 1 のビットの数は 1、0 の場合は 1 のビットの数は 0 なので、c の各ビットの値 は b と同じ になります。

次に 手順 3 で bwidth を 1 の 2 倍の 2 に更新 し、手順 4 で bwidth の 2 が b のビット長である 8 以下 なので 手順 2 に戻ります。

下図は b と、b と同じビット長 の c を図示 したものです。図の縦棒は b と c を 2 の幅のビット で 均等に分割 することを表します。

c の 分割した範囲のビット には、同じ範囲 の b の 1 のビットの数 を 2 進数で記録します。b の 4 つに分割 された 各範囲の 1 のビットの数 は 左から 1、0、2、1 なので、c の対応する範囲のビット にはそれぞれを 2 桁の 2 進数で表現 した 0b01、0b00、0b10、0b01 となります。従って、c の値 は上図のように、その 4 つの 2 進数を並べた 0b01001001 になります。

なお、上記の説明では手順 2 の処理を図を見ながら 1 の数を数えて c を計算しましたが、このアルゴリズムでは 各範囲の 1 のビットの数を数えず に 効率よく計算する方法 があり、その方法については この後で説明 します。

次に 手順 3 で bwidth を 2 の 2 倍の 4 に更新 し、手順 4 で bwidth の 4 が b のビット長である 8 以下 なので 手順 2 に戻ります。

下図は b と、b と同じビット長 の c を図示 したものです。図の縦棒は b と c を 4 の幅のビット で 均等に分割 することを表します。

c の 分割した範囲のビット には、同じ範囲 の b の 1 のビットの数 を 2 進数で記録します。b の 2 つに分割 された 各範囲の 1 のビットの数 は 左から 1、3 なので、c の対応する範囲のビット にはそれぞれを 4 桁の 2 進数で表現 した 0b0001、0b0011 となります。従って、c の値 は上図のように、その 2 つの 2 進数を並べた 0b00010011 になります。

次に 手順 3 で bwidth を 4 の 2 倍の 8 に更新 し、手順 4 で bwidth の 8 が b のビット長である 8 以下 なので 手順 2 に戻ります。

下図は b と、b と同じビット長 の c を図示 したものです。手順 2 では b と c を 8 の幅のビット で 均等に分割 しますが、b と c の ビット長は 8 なので 実際には分割は行われません。この場合は 1 つの範囲に分割 されたと考えて下さい。

c の 1 つに分割された範囲のビット には、同じ範囲 の b の 1 のビットの数 を 2 進数で記録します。b の 1 つに分割 された 各範囲の 1 のビットの数 は 4 なので、c の対応する範囲のビット は上図のように 8 桁の 2 進数で表現 した 0b00000100 となります。

次に 手順 3 で bwidth を 8 の 2 倍の 16 に更新 し、手順 4 で bwidth の 8 が b のビット長である 8 を超えている ので 手順 5 へ移動 します。手順 5 で示すように c に b の popcount である 0b1000 = 4 が計算 されていることが確認できます。

以上が 0b10001101 の popcount をこのアルゴリズムで計算する手順 です。

手順 2 の効率的な計算方法

次に、このアルゴリズムの 手順 2 の 効率的な計算方法 について説明します。そのアルゴリズムは以下の通りです。

bwidth が 1 の場合は先ほど説明したように c = b で計算できる。

bwidth が 2 以上 の場合は下記のアルゴリズムで 手順 2 の計算を行う。

一つ前の c で計算した値 を bwidth / 2 の幅のビット で 均等に分割 する
分割した範囲をそれぞれ右から 0、1、2、3・・・のように番号をつける
c から 偶数番の範囲のビットをそのまま取りだし、それ以外の範囲のビットを 0 とする ビット列 c1 を計算 する
c から 奇数番の範囲のビットをそのまま取りだし、それ以外の範囲のビットを 0 とする ビット列 c2 を計算 する
c2 を bwidth / 2 だけ右シフト した c3 を計算 する
c を c1 + c3 の計算結果で更新 する

上記の手順 4、5 は、先に c を bwidth / 2 だけ右シフトした値を計算してから、手順 3 と同様の方法で c3 を計算することもでき、どちらも処理速度は変わりません。

上記のアルゴリズムも意味がわからない人が多いと思いますので、0b10001101 を具体例に説明 します。

`bwidth` が `1` の場合の計算

手順 1 で bwidth が 1 の状態から開始します。手順 2 では下図のように c = b とし、手順 3 で bwidth を 2 に更新 し、手順 4 で bwidth が b のビット長である 8 以下 なので 手順 2 に戻ります。

偶数の番号のビットの計算

手順 2 では c を bwidth / 2 = 1 の幅のビットで均等に分割 し、右から順に 0 から始まる番号 を振ります。上図のようにその番号は ビットの番号と等しく なります。

次に、c から 偶数の番号のビット を そのまま取り出し、奇数の番号のビット を 0 とする ビット列を計算 します。そのようなビット列は下記のプログラムのように 偶数の番号のビットを 1、奇数の番号のビットを 0 とした 0b01010101 という ビットマスク と AND 演算 を行うことで計算することができます。

b = 0b10001101
c = b
mask1 = 0b01010101
c1 = c & mask1
print(f"b     = {b:08b}")
print(f"c     = {c:08b}")
print(f"mask1 = {mask1:08b}")
print(f"c1    = {c1:08b}")

実行結果

b     = 10001101
c     = 10001101
mask1 = 01010101
c1    = 00000101

下図は 上記の計算を表す図 で、ビットマスク の 1 である 黄色のビット は c のビットと同じ値 が、それ以外のビットは 0 が計算 されることがわかります。なお、下記の表は図の b 以外 の ビットの色 の意味を表します。

色	意味
灰色	AND 演算によって値が 0 になるビット
水色	AND 演算によって値が変わらないビット
白色	必ず 0 となるビット
黄色	ビットマスクの 1 のビット

c の各ビット は、b の同じビットの 1 のビットの個数 です。また、c1 の奇数の番号のビット は 必ず 0 になる ので、上記で計算された c1 の各ビット は 2 つのビットをひとまとめ にして 2 桁の 2 進数 と考えることで、以下のような意味を持つ と考えることができます。

ビットの番号	意味	上図での値
0、1	`b` の 0 番のビットの 1 の個数	0b01 = 1 個
2、3	`b` の 2 番のビットの 1 の個数	0b01 = 1 個
4、5	`b` の 4 番のビットの 1 の個数	0b00 = 0 個
6、7	`b` の 6 番のビットの 1 の個数	0b00 = 0 個

奇数の番号のビットの計算

次に、c から 奇数の番号のビットを取り出し、偶数の番号のビットを 0 とする ビット列 c2 を計算 し、c2 を 右シフト演算 で biwidth / 2 = 1 ビット分ずらした c3 を計算 します。

そのようなビット列は下記の手順で計算を行うことができます。

奇数の番号のビットを 1、偶数の番号のビットを 0 とした 0b10101010 という ビットマスク と AND 演算 を行う
計算した値に対して 右シフト演算 で 1 ビット右にずらす

下記はそのような計算を行うプログラムです。

mask2 = 0b10101010
c2 = c & mask2
c3 = c2 >> 1
print(f"b     = {b:08b}")
print(f"c     = {c:08b}")
print(f"mask2 = {mask2:08b}")
print(f"c2    = {c2:08b}")
print(f"c3    = {c3:08b}")

実行結果

b     = 10001101
c     = 10001101
mask2 = 10101010
c2    = 10001000
c3    = 01000100

下図は 上記の計算を表す図 で、最初の AND 演算 で ビットマスク の 1 である 黄色のビット は 元のビットと同じ値 が、それ以外のビットは 0 が計算 され、その 次の右シフト演算 で 各ビットが 1 つずつ右にずれる ことがわかります。なお、先程の図では AND 演算によって 値が変わらない偶数の番号 のビットを水色で表記しましたが、下図では 値が変わらない奇数の番号 のビットを 緑色で表記 しました。

上図からわかるように c3 の各ビット は、2 つのビットをひとまとめ にして 2 桁の 2 進数 と考えることで、以下のような意味を持つ と考えることができます。

ビットの番号	意味	上図での値
0、1	`b` の 1 番のビットの 1 の個数	0b00 = 0 個
2、3	`b` の 3 番のビットの 1 の個数	0b01 = 1 個
4、5	`b` の 5 番のビットの 1 の個数	0b00 = 0 個
6、7	`b` の 7 番のビットの 1 の個数	0b01 = 1 個

2 ビット毎の 1 の個数の計算

次に、上記で計算した 2 つの値である c1 と c3 を加算 し、c をその値で更新 します。下記はその計算を行うプログラムです。下記では 更新前の c を c before、更新後の c を c after と表示しました。

print(f"b        = {b:08b}")
print(f"c before = {c:08b}")
print(f"c1       = {c1:08b}")
print(f"c3       = {c3:08b}")
c = c1 + c3
print(f"c after  = {c:08b}")

実行結果

b        = 10001101
c before = 10001101
c1       = 00000101
c3       = 01000100
c after  = 01001001

下図は上記の計算を表す図で、c1 以下のデータ では 2 つのビットをひとまとめ にして 2 桁の 2 進数と考える ことを表すために、2 ビットごとに縦棒で区切り ました。

先程の c2 を 1 ビット右にずらして c3 を計算 するという処理は、c1 の分割した各範囲の値 と、c2 の分割した範囲の値 の 2 進数の桁の位置を揃える ことで、上図のような 加算を行うことができるようにする という意味を持ちます。

更新された c のビット列の 各ビット は、2 つのビットをひとまとめ にして 2 桁の 2 進数 と考えることで、以下のような意味を持つ と考えることができます。

ビットの番号	意味	上図での値
0、1	`b` の 0、1 番のビットの 1 の個数	0b01 = 1 個
2、3	`b` の 3、4 番のビットの 1 の個数	0b10 = 2 個
4、5	`b` の 5、6 番のビットの 1 の個数	0b00 = 0 個
6、7	`b` の 7、8 番のビットの 1 の個数	0b01 = 1 個

上記の表から、b の 「0、1 番」、「2、3 番」、「4、5 番」「6、7 番」 のビットの それぞれの 1 のビットの個数 を 1 度の加算処理でまとめて行う ことができることがわかります。上記の計算を別の言葉で説明すると、以下のようになります。

1 つのビット列 を 区切って複数の数値の集まり とみなす
そのようなビット列の加算 を行うことで、複数の数値の加算処理 を 1 度の加算処理でまとめて行う

このような、複数の演算をまとめて行う という処理は、ビットごとに独立した演算 を行う AND 演算 や OR 演算 などの ビット演算 では 良く使われる手法 ですが、上記で行っている 加算や減算などの多くの演算 で同様の処理を行う際には 下記の点に気を付ける必要 があります。

加算処理 はあるビットどうしの加算によって 繰上りが発生 すると、別のビットの計算に影響を与えます³。そのため、1 回の演算 で 複数の演算をまとめて行う場合 は、区切られて表現された数値 どうしの 演算の結果 が、他の区切られて表現された数値の演算の結果 に 影響を与えないようにする 必要があります。

上記の例の場合は、2 ビットのデータ で 2 つのビット の 1 のビットの数を表現 していますが、その数値の範囲 は 0 ~ 2 なので、2 ビットのデータ表現できる 0b00 ~ 0b11（十進数の 0 ~ 3）の 範囲に収まります。そのため 4 つの計算結果 が 他の計算結果に影響を及ぼすことはありません。

c が計算できたので bwidth を 4 に更新 し、bwidth が b のビット長である 8 以下 なので 手順 2 に戻ります。

2 ビットごとに分割したデータの偶数番のデータの計算

最初の c は下図のように 各ビットの値 は b の同じビットの 1 の個数 を表します。

それに対し、上記で 更新した c は、下図のように ビット列 を 2 ビットごとに分割 した場合の、b の 同じ範囲のビットの 1 の個数 を表します。

このように、更新前と更新後 の c の違い は、ビット列 を 1 ビットごとに分割 するか、2 ビットごとに分割 するかだけなので、2 ビットごとに分割 したデータを 右から順番に 0、1、2、3 番目 のデータと表現した場合に、先程と同じ手順 で 0、1 番目 と 2、3 番目 の範囲の b の 1 のビットの数を計算 することができます。

具体的には bwidth / 2 = 2 ビットで分割 した c の 偶数番の範囲のビットを取り出し、奇数番の範囲のビットを 0 とする c1 を計算 します。c1 は下記のプログラムのように 偶数番の範囲のビットを 1、奇数番の範囲のビットを 0 とした 0b00110011 という ビットマスク と c の AND 演算 を行うことで計算できます。

mask1 = 0b00110011
c1 = c & mask1
print(f"b     = {b:08b}")
print(f"c     = {c:08b}")
print(f"mask1 = {mask1:08b}")
print(f"c1    = {c1:08b}")

実行結果

b     = 10001101
c     = 01001001
mask1 = 00110011
c1    = 00000001

下図は上記の計算を表す図で、ビットマスク の 1 である黄色のビット は c のビットと同じ値 が、それ以外のビット は 0 が計算される ことがわかります。

上記で計算された c1 の各ビット は、4 つのビットをひとまとめに して 4 桁の 2 進数 と考えることで、以下のような意味を持つ と考えることができます。

ビットの番号	意味	上図での値
0 ~ 3	`b` の 0、1 番のビットの 1 の個数	0b0001 = 1 個
4 ~ 7	`b` の 4、5 番のビットの 1 の個数	0b0000 = 0 個

2 ビットごとに分割したデータの奇数番のデータの計算

次に、2 ビットで分割 した c の 奇数番の範囲のビットを取り出し、偶数番のビットを 0 とする c2 を計算 します。さらに、c2 に対して 右シフト演算 で bwidth / 2 = 2 ビット分ずらした c3 を計算します。データを 2 ビットで分割 しているため、先ほどと異なり 1 ビットではなく 2 ビット分ずらす必要がある点に注意 して下さい。

そのような c3 は 下記の手順で計算 を行うことができます。

奇数番の範囲のビットを 1、偶数番の範囲のビットを 0 とした 0b11001100 という ビットマスク と c の AND 演算 を行う
計算した値に対して 右シフト演算 で 2 ビット分右にずらす

下記はそのような計算を行うプログラムです。

mask2 = 0b11001100
c2 = c & mask2
c3 = c2 >> 2
print(f"b     = {b:08b}")
print(f"c     = {c:08b}")
print(f"mask2 = {mask2:08b}")
print(f"c2    = {c2:08b}")
print(f"c3    = {c3:08b}")

実行結果

b     = 10001101
c     = 01001001
mask2 = 11001100
c2    = 01001000
c3    = 00010010

下図は 上記の計算 を表す図で、最初の AND 演算 で ビットマスク の 1 である黄色のビット は c と同じ値 が、それ以外のビットは 0 である c2 が計算 され、その 次の右シフト演算 で 各ビットが 2 つずつ右にずれる c3 が計算 されます。

上記で計算された c3 の 各ビット は、4 つのビットをひとまとめ にして 4 桁の 2 進数 と考えることで、以下のような意味を持つ と考えることができます。

ビットの番号	意味	上図での値
0 ~ 3	`b` の 2、3 番のビットの 1 の個数	0b0010 = 2 個
4 ~ 7	`b` の 6、7 番のビットの 1 の個数	0b0001 = 1 個

4 ビット毎の 1 の個数の計算

次に、上記で計算した 2 つの値である c1 と c3 を加算 し、c をその値で更新 します。下記はその計算を行うプログラムです。なお、下記のプログラムは先ほどの 2 ビット毎の 1 の個数の計算と同じ です。

print(f"b        = {b:08b}")
print(f"c before = {c:08b}")
print(f"c1       = {c1:08b}")
print(f"c3       = {c3:08b}")
c = c1 + c3
print(f"c after  = {c:08b}")

実行結果

b        = 10001101
c before = 01001001
c1       = 00000001
c3       = 00010010
c after  = 00010011

下図は上記の計算を表す図で、c1 以下のデータ では 4 つのビットをひとまとめ にして 4 桁の 2 進数と考える ことを表すために、4 ビットごとに縦棒で区切り ました。

更新された c のビット列の 各ビット は、4 つのビットをひとまとめ にして 2 桁の 4 進数 と考えることで、以下のような意味を持つ と考えることができます。

ビットの番号	意味	上図での値
0 ~ 3	`b` の 0 ~ 3 番のビットの 1 の個数	0b0011 = 3 個
4 ~ 7	`b` の 4 ~ 7 番のビットの 1 の個数	0b0001 = 1 個

上記の表から先程と同様に b の 「0 ~ 3 番」、「4 ~ 7 番」 の それぞれの 1 のビットの個数 を 1 度の加算処理でまとめて行う ことができることがわかります。

popcount の計算

同じような図になるので図は省略しますが、上記と同様の手順 の処理を もう一度行う ことで b の「0 ~ 7 番」 の 1 のビットの個数 である popcount を計算 することができます。

具体的には 下記の手順 で計算を行います。

c に対して 0 ~ 3 番のビットを 1 とした 0b00001111 という ビットマスク との AND 演算 を行うことで、b の 0 ~ 3 番のビットの個数を計算 できる
c に対して 4 ~ 7 番のビットを 1 とした 0b11110000 という ビットマスク との AND 演算 を行い、右シフト によって 4 ビット右にずらす ことで、4 ~ 7 番のビットの個数を計算 できる
上記で計算した 2 つの値の合計 を計算することで b の popcount が計算 される

下記はその処理を行うプログラムで、実行結果から 0b10001101 の popcount である 4 が 正しく計算されることが確認 できます。

mask1 = 0b00001111
c1 = c & mask1
mask2 = 0b11110000
c2 = c & mask2
c3 = c2 >> 4
print(f"b        = {b:08b}")
print(f"c before = {c:08b}")
print(f"mask1    = {mask1:08b}")
print(f"c1       = {c1:08b}")
print(f"mask2    = {mask2:08b}")
print(f"c2       = {c2:08b}")
print(f"c3       = {c3:08b}")
c = c1 + c3
print(f"c after  = {c:08b} = {c}")

実行結果

b        = 10001101
c before = 00010011
mask1    = 00001111
c1       = 00000011
mask2    = 11110000
c2       = 00010000
c3       = 00000001
c after  = 00000100 = 4

上記の c3 の計算は、下記のプログラムのように c2 の計算を省略することができます。ただし、この省略を行うことができるのはこのアルゴリズムの手順 2 ~ 4 の最後の繰り返し処理の場合だけです。

c3 = c >> 4

その理由は以下の通りです。

c2 は c の 0 ~ 3 番のビットを取り除くという処理を行う
c3 は c2 を右に 4 ビットずらす処理を行うが、その際に c2 の 0 ~ 3 番のビットの値は削除されるので c3 の計算結果に影響しない
従って、c2 の計算を行わずに直接 c を右に 4 ビットずらしても同じ計算が行われる

より具体的なアルゴリズム

上記では 8 ビット のビット列に対する popcount の計算の手順を説明 しましたが、先程説明した 下記のアルゴリズム で 任意のビット長 の ビット列の popcount を計算 することができます。

ビットの範囲 を表す bwidth を 1 とする
以下のような b と同じビット長 の ビット列 c を計算する
- b と c を bwidth の幅のビットで均等に分割 する
- 分割したそれぞれの範囲 の c のビットの 2 進数の値 が、同じ範囲の b のビットの 1 のビットの数になるようにする
bwidth を 2 倍 にする
bwidth が b のビット長以下 の場合は 手順 2 に戻る
超えている場合 は c に b の popcount が計算 されている

ただし、上記のアルゴリズムは 抽象的な部分がある ので上記のアルゴリズムから プログラムを記述するのは困難 です。そこで、下記のように プログラムを記述できる ような 具体的なアルゴリズムに修正 することにします。

なお、while 文 では 繰り返しの条件 を 繰り返し処理の前に記述 するので、下記のように 繰り返し処理の前 に 繰り返しの条件の手順を移動 しました。

また、先程説明した上記の 手順 2 のアルゴリズムでは、途中で bwidth / 2 という計算を行っていますが、割り算の処理には時間がかかる ので、割り算を行わなくても済む ように先程説明した 手順 2 のアルゴリズムの bwidth の値を 1/2 にしたアルゴリズムに修正しました。そのため、先程の説明では c に b を代入した後 の bwidth を 2 としていましたが、下記のアルゴリズムでは bwidth を 1/2 の 1 としました。また、繰り返しの条件を bwidth < blength のようにビット長以下ではなく、ビット長未満 のように修正しました。

popcount を計算する ビット列を b とした場合に、その ビット長である blength を計算 し、c に b を代入 する⁴
ビット列を 分割するビット数 を表す bwidth を 1 とする
bwidth < blength の間、下記の 手順 4 ~ 9 の処理を繰り返す
c を bwidth ビットごと分割 し、右から順番に 0 から始まる番号 をつける
偶数の番号の範囲のビットが 1、奇数の番号の範囲のビットが 0 の ビットマスクを計算 し、c との AND 演算を行った c1 を計算する
偶数の番号の範囲のビットが 0、奇数の番号の範囲のビットが １ の ビットマスクを計算 し、c との AND 演算を行った c2 を計算する
c2 を 右シフト で bwidth ずらした c3 を計算する
c の値を c1 + c3 で更新 する
bwidth を 2 倍 して 手順 3 に戻る
繰り返しが終了した時点で c に b の popcount が計算 される

上記のアルゴリズムでは 手順 4 ~ 9 の処理を 1 回繰り返すたび に bwidth の値が 2 倍 になるので、bl のビット長 の popcount は以前の記事で説明した 対数を表す log でその 繰り返しの回数を表記 すると $\boldsymbol{log_2{bl}}$ （小数点以下切り上げ）回 の 繰り返し処理が必要 になることがわかります。例えば 3 x 3 の〇× ゲーム の場合は マスの数が 9 個 なのでゲーム盤を表す ビットボードのビット長は 9 になります。$log_2{9} = 約 3.16$ なので、手順 4 ~ 9 の処理を 4 回繰り返す必要 があります。

この アルゴリズムの特徴 は、ビット長が 2 倍 になると 手順 4 ~ 9 の処理回数が 1 だけ増える⁵ので、ビット長が大きくなっても 手順 4 ~ 9 の 処理回数が大きく増えない という点にあります。例えば手順 4 ~ 9 の 処理回数 は ビット長が $2^3 = 8$ の場合は 3 回、$2^{10} = 1024$ の場合は 10 回、$2^{20} = 1048576$ の場合は 20 回 となります。

下記は 128 までの ビット長と手順 4 ~ 9 の処理回数 の関係を表す表です。

ビット長	1	2	3 ~ 4	5 ~ 8	9 ~ 16	17 ~ 32	33 ~ 64	65 ~ 128
回数	0	1	2	3	4	5	6	7

`popcount3` の定義

上記の 手順 5 と 6 で必要となる ビットマスクをプログラムで計算 するのは 少々面倒 なので、今回の記事 では 32 ビットまでのビット列で必要 となる ビットマスクをあらかじめ計算 しておくことにします。そのため、下記で定義する popcount3 は 32 ビットより長いビット列 に対する popcount を 計算することはできません。

任意のビット長の popcount をこのアルゴリズムで計算する方法については次回以降の記事で説明します。

下記は popcount3 を定義するプログラムです。

2 ~ 15 行目：手順 5、6 で必要となるビットマスクを表すデータを dict で記録したものを変数に代入する。dict のキーが bwidth を、キーの値がその bwidth で利用するビットマスクを表す。なお、dict を代入する変数の名前の even は偶数、odd は奇数を表す英単語である
16、17 行目：b のビット長を計算し、c に b を代入する（手順 1）
18 行目：bwidth を 1 で初期化する（手順 2）
19 行目：bwidth < bit_length の間繰り返し処理を行う（手順 3）
20 行目：手順 4 ~ 8 の計算を行い c の値を更新する。なお、1 つの式でまとめて計算を行うようにした
21 行目：bwidth を 2 倍する（手順 9）
22 行目：c に popcount が計算されているので返り値として返す（手順 10）

 1  def popcount3(b):
 2      masktable_even = {
 3          1: 0b01010101010101010101010101010101,
 4          2: 0b00110011001100110011001100110011,
 5          4: 0b00001111000011110000111100001111,
 6          8: 0b00000000111111110000000011111111,
 7          16: 0b00000000000000001111111111111111,
 8      }
 9      masktable_odd = {
10          1: 0b10101010101010101010101010101010,
11          2: 0b11001100110011001100110011001100,
12          4: 0b11110000111100001111000011110000,
13          8: 0b11111111000000001111111100000000,
14          16: 0b11111111111111110000000000000000,       
15      }
16      blength = b.bit_length()
17      c = b
18      bwidth = 1
19      while bwidth <= blength:
20          c = (c & masktable_even[bwidth]) + \
21              ((c & masktable_odd[bwidth]) >> bwidth)
22          bwidth *= 2
23      return c

行番号のないプログラム

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

下記は blist の各ビット列 に対する popcount3 の 計算結果と処理速度を計測 するプログラムです。実行結果から popcount が正しく計算されることが確認 できます。

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)

実行結果

                            data | pc | bl | time
                               0 |  0 |  0 | 443 ns ± 3.79 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                               1 |  1 |  1 | 446 ns ± 2.45 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       100000000 |  1 |  9 | 1.06 μs ± 11.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000000000000000000000000000000 |  1 | 32 | 1.41 μs ± 8.04 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                              11 |  2 |  2 | 633 ns ± 9.59 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       100000001 |  2 |  9 | 1.12 μs ± 6.18 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000000000000000000000000000001 |  2 | 32 | 1.42 μs ± 9.35 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                           11111 |  5 |  5 | 919 ns ± 7.99 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       101010101 |  5 |  9 | 1.13 μs ± 8.06 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10000001000000001000000001000001 |  5 | 32 | 1.47 μs ± 21.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
                       111111111 |  9 |  9 | 1.16 μs ± 14.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
11111111111111111111111111111111 | 32 | 32 | 1.5 μs ± 14.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は上記の実行結果を ビット長の小さい順で並べた 表です。回数は 手順 4 ~ 9 の繰り返し回数 です。

ビット列	pc	bl	処理速度	回数
`0b0`	0	0	443 ns	0
`0b1`	1	1	446 ns	0
`0b11`	2	2	633 ns	1
`0b11111`	5	5	919 ns	3
`0b100000000`	1	9	1060 ns	4
`0b100000001`	2	9	1120 ns	4
`0b101010101`	5	9	1130 ns	4
`0b111111111`	9	9	1160 ns	4
`0b10000000000000000000000000000000`	1	32	1410 ns	5
`0b10000000000000000000000000000001`	2	32	1420 ns	5
`0b10000001000000001000000001000001`	5	32	1470 ns	5
`0b11111111111111111111111111111111`	32	32	1500 ns	5

popcount3 はビット列の ビット長 によって 手順 4 ~ 9 の繰り返し回数が変化 し、上記の表から 処理時間 がその 繰り返し回数にほぼ比例する ことが確認できました。

まあ、同じビット長 であれば、popcount が異なっていても 処理速度が変わらない 事が確認できます。

下記は popcount1、popcount2、popcount3 の 処理時間をまとめた表 です。処理時間の単位は ns です。

ビット列	pc	bl	pc1	pc2	pc3
`0b0`	0	0	149	53	443
`0b1`	1	1	220	97	446
`0b11`	2	2	290	142	633
`0b11111`	5	5	470	277	919
`0b100000000`	1	9	623	97	1060
`0b100000001`	2	9	645	141	1120
`0b101010101`	5	9	666	394	1130
`0b111111111`	9	9	713	679	1160
`0b10000000000000000000000000000000`	1	32	2760	144	1410
`0b10000000000000000000000000000001`	2	32	2760	244	1420
`0b10000001000000001000000001000001`	5	32	2800	494	1470
`0b11111111111111111111111111111111`	32	32	3100	2750	1500

残念ながら popcount3 のアルゴリズムは 手順 4 ~ 9 の 1 回の繰り返しで行う処理 が popcount1 や popcount2 よりも 複雑で時間がかかる ため、ビット長が 9 以下 の場合は popcount1 や popcount2 よりも 処理速度が遅く なります。一方で、ビット長が 32 の場合は popcount1 よりも処理速度が速く、popcount が多い場合 は popcount2 よりも処理速度が速く なります。

従って、このアルゴリズムは ビット長がある程度以上長い場合 に 効率が良い アルゴリズムであると言えます。

`bit_count` メソッドを利用した計算方法

ここまで紹介 した popcount を計算する方法 は、いずれも 様々なアルゴリズムで 1 のビットの数を計算 する処理を行っていますが、最近の CPU は 一般的に特定のビット長のビット列 の popcount を直接計算 する ビット演算を行う命令 を持っており、その命令を利用 することで 高速に popcount を計算 することができます。

Python の int 型 のデータには popcount を計算 する bit_count⁶ というメソッド が用意されており、おそらく CPU の popcount を計算する命令を利用 しているため 高速に popcount を計算 することができます。

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

上記のリンク先で説明されているように、bit_count メソッドは実引数に記述された整数の絶対値の popcount を計算するので、負の値に対しても計算を行うことができます。

下記は bit_count メソッドを利用して popcount を計算 する popcount4 を定 義するプログラムです。bit_count メソッドを呼び出して返り値として返しているだけなので、特に説明は必要ないでしょう。

def popcount4(b):
    return b.bit_count()

下記は blist の各ビット列 に対する popcount4 の 計算結果と処理速度を計測 するプログラムです。実行結果から popcount が正しく計算されることが確認 できます。

for b in blist:
    popcount = popcount4(b)
    print(f"{b:32b} | {popcount:2} | {b.bit_length():2} | ", end="")
    %timeit popcount4(b)

実行結果

                               0 |  0 |  0 | 58.2 ns ± 0.39 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                               1 |  1 |  1 | 59.5 ns ± 1.08 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                       100000000 |  1 |  9 | 60.1 ns ± 1.48 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
10000000000000000000000000000000 |  1 | 32 | 60.8 ns ± 0.362 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                              11 |  2 |  2 | 59.5 ns ± 0.347 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                       100000001 |  2 |  9 | 59.9 ns ± 0.336 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
10000000000000000000000000000001 |  2 | 32 | 60.8 ns ± 0.367 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                           11111 |  5 |  5 | 59.8 ns ± 1.11 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                       101010101 |  5 |  9 | 59.9 ns ± 0.431 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
10000001000000001000000001000001 |  5 | 32 | 61 ns ± 0.428 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
                       111111111 |  9 |  9 | 59.9 ns ± 0.423 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
11111111111111111111111111111111 | 32 | 32 | 61.2 ns ± 1.17 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

上記の実行結果から bit_count メソッドを利用した場合は ビット長 や popcount の数に関わらず ほぼ 同じ処理速度 で計算が行われることが確認できました。

CPU が一度に計算できる popcount のビット列の長さは決まっているので、それを超えるような長さのビット列の popcount を bit_count で計算すると処理時間が長くなります。

実際に下記のプログラムでビット長が 100 と 1000 のビット列の popcount を bit_count メソッドで計算する処理時間を計測した所、ビット長が 1000 の場合の処理時間が長くなることが確認できました。

b100 = 1 << 100
b1000 = 1 << 1000
%timeit b100.bit_count()
%timeit b1000.bit_count()

実行結果

35.4 ns ± 0.222 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
76.5 ns ± 0.869 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

popcount の処理時間のまとめ

今回の記事で実装した 4 種類 の popcount を計算する関数の 処理時間 を popcount の小さい順 と ビット長の小さい順 に並べた表にまとめます。

下記は popcount の小さい順 で並べた表です。処理速度の単位は ns です。

ビット列	pc	bl	pc1	pc2	pc3	pc4
`0b0`	0	0	149	53	443	58
`0b1`	1	1	220	97	446	60
`0b100000000`	1	9	623	97	1060	60
`0b10000000000000000000000000000000`	1	32	2760	144	1410	61
`0b11`	2	2	290	142	633	60
`0b100000001`	2	9	645	141	1120	60
`0b10000000000000000000000000000001`	2	32	2760	244	1420	61
`0b11111`	5	5	470	277	919	60
`0b101010101`	5	9	666	394	1130	60
`0b111111111`	9	9	713	679	1160	60
`0b10000001000000001000000001000001`	5	32	2800	494	1470	61
`0b11111111111111111111111111111111`	32	32	3100	2750	1500	61

下記は ビット長の小さい順 で並べた表です。

ビット列	pc	bl	pc1	pc2	pc3	pc4
`0b0`	0	0	149	53	443	58
`0b1`	1	1	220	97	446	60
`0b11`	2	2	290	142	633	60
`0b11111`	5	5	470	277	919	60
`0b100000000`	1	9	623	97	1060	60
`0b100000001`	2	9	645	141	1120	60
`0b101010101`	5	9	666	394	1130	60
`0b111111111`	9	9	713	679	1160	60
`0b10000000000000000000000000000000`	1	32	2760	144	1410	61
`0b10000000000000000000000000000001`	2	32	2760	244	1420	61
`0b10000001000000001000000001000001`	5	32	2800	494	1470	61
`0b11111111111111111111111111111111`	32	32	3100	2750	1500	61

上記の表とそれぞれのアルゴリズムで行う処理から、それぞれのアルゴリズム には 下記のような性質がある ことがわかります。

アルゴリズム	性質
`popcount1`	ビット長に比例した処理速度になる。popcount の数には処理速度はほんど影響されない
`popcount2`	popcount に比例した処理速度になる。popcount が同じであればビット長によって処理速度は基本的には影響しないが、ビット長が特定の値を超えるとと処理速度が若干遅くなる
`popcount3`	ビット長の対数に比例した処理速度になるのでビット長が大きい場合は `popcount1` や `popcount2` よりも処理速度が高速になるが、ビット長が小さい場合は処理速度が遅くなる。
`popcount4`	ビット長が 100 程度であまり大きくない場合は処理速度はビット長に関わらず同じである。popcount の数は処理速度に影響しない。他のアルゴリズムよりも大幅に処理速度が高速である

今回の記事で紹介したアルゴリズムの中では bit_length メソッドが最も高速であるので、今回の記事 では bit_length メソッドを利用 することにします。

bit_length メソッドを利用した方法は 実装も簡単 なので、それ以外のアルゴリズムを紹介した理由について疑問に思う方がいるかもしれません。それ以外のアルゴリズムを紹介した理由 は、プログラミング言語 によっては CPU の popcount を計算する命令を利用できない場合がある からです。そのような場合は今回の記事で紹介したアルゴリズムや、別のアルゴリズムで popcount を計算する必要があります。

`countmark2` の実装

下記は bit_length メソッドを利用して 0 列 の 〇のマークを数える countmark2 の定義を行うプログラムです。0 列 の (0, 0)、(0, 1)、(0, 2) のマスは ビットボード の 0、1、2 番のビットに対応 するので、それらのビットだけを 1 とした 0b000000111 という ビットマスク と 〇のビットボード の AND 演算 を計算することで、0 列の〇のマークだけを表すビット列を計算 することができます。そのビット列 に対して bit_length メソッドで popcount を計算 することで 0 列の〇のマークの数を計算 しています。

def countmark2(bb):
    return (bb.board[0] & 0b000000111).bit_length()

下記は blist の 各要素のビットボード に対して countmark2 で 0 列のマークの数を数える プログラムで、実行結果から 正しい計算が行われることが確認 できます。

for bb in bblist:
    print(countmark2(bb))

実行結果

下記は countmark2 の 処理速度を計測 するプログラムで、いずれも約 85 ns = 0.085 μs の処理時間がかかることが確認できます。countmark1 の約 1 μs と比較 して 処理速度が 10 倍以上になる ことが確認できました。

for bb in bblist:
    %timeit countmark2(bb)

実行結果

85.4 ns ± 0.646 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
86.2 ns ± 0.533 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
86.5 ns ± 0.895 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
86.1 ns ± 0.648 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

`count_markpats` の実装

ビット列の popcount を計算 することができるようになったので、BitBoard クラスの count_markpats を下記の方法で実装することができます。

各行と列、2 つの対角線の それぞれの直前上 のマスに 対応するビットだけを 1 とする 8 つのビットマスクを用意 する
〇と × のビットボード に対して 8 つのビットマスクとの AND 演算 を行うことで、それぞれの直線上 の 〇と × のマークを表すビット列を計算 する
上記で計算したビット列 に対して popcount を計算 することで 〇と × のマークの数を数える

下記は上記の方法で count_markpats を実装するプログラムです。

8 ~ 17 行目：8 種類の直線上のマスに対応するビットのみを 1 とするビットマスクの一覧を要素として持つ list を変数に代入する
18 ~ 22 行目：繰り返し処理によって turn と last_turn の手番のビットボードと各直線上のマスクデータの AND 演算を行った値の popcount を bit_count メソッドで計算することで、それぞれのマークの数を計算し、その直線上のマークのパターンを markpats で数える

 1  from collections import defaultdict
 2  
 3  def count_markpats(self, turn, last_turn):
 4      markpats = defaultdict(int)
 5  
 6      if self.count_linemark:
元と同じなので省略
 7      else:
 8          masklist = [
 9              0b000000111, # 0 列のビットマスク
10              0b000111000, # 1 列のビットマスク
11              0b111000000, # 2 列のビットマスク
12              0b001001001, # 0 行のビットマスク
13              0b010010010, # 1 行のビットマスク
14              0b100100100, # 2 行のビットマスク
15              0b100010001, # 対角線 1 のビットマスク
16              0b001010100, # 対角線 2 のビットマスク
17          ]
18          for mask in masklist:
19              turncount = (self.board[turn] & mask).bit_count()
20              lastturncount = (self.board[last_turn] & mask).bit_count()
21              emptycount = self.BOARD_SIZE - turncount - lastturncount
22              markpats[(lastturncount, turncount, emptycount)] += 1
23  
24      return markpats    
25  
26  BitBoard.count_markpats = count_markpats

行番号のないプログラム

from collections import defaultdict

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)

    if self.count_linemark:
        for countdict in [self.rowcount, self.colcount, self.diacount]:
            for circlecount, crosscount in zip(countdict[self.CIRCLE], countdict[self.CROSS]):
                emptycount = self.BOARD_SIZE - circlecount - crosscount
                if last_turn == self.CIRCLE:
                    markpats[(circlecount, crosscount, emptycount)] += 1
                else:
                    markpats[(crosscount, circlecount, emptycount)] += 1
    else:
        masklist = [
            0b000000111, # 0 列のビットマスク
            0b000111000, # 1 列のビットマスク
            0b111000000, # 2 列のビットマスク
            0b001001001, # 0 行のビットマスク
            0b010010010, # 1 行のビットマスク
            0b100100100, # 2 行のビットマスク
            0b100010001, # 対角線 1 のビットマスク
            0b001010100, # 対角線 2 のビットマスク
        ]
        for mask in masklist:
            turncount = (self.board[turn] & mask).bit_count()
            lastturncount = (self.board[last_turn] & mask).bit_count()
            emptycount = self.BOARD_SIZE - turncount - lastturncount
            markpats[(lastturncount, turncount, emptycount)] += 1

    return markpats    

BitBoard.count_markpats = count_markpats

上記の定義後に 下記の処理 を行う下記のプログラムで、実装した calc_markpats が正しく動作するか どうかを確認します。

ゲーム開始時の局面と (0, 0)、(1, 0) に着手を行った局面に対して、BitBoard と ListBoard クラスを利用した Marubatsu クラスのインスタンスの count_markpats メソッドを呼び出してその結果を表示する
count_markpats の返り値は defaultdict なので、== 演算子でその内容が同じであるかどうかを確認する

from marubatsu import Marubatsu

mb = Marubatsu(boardclass=BitBoard)
mb2 = Marubatsu()  # 実引数を記述しない場合は ListBoard クラスを利用
print(mb.count_markpats())
print(mb2.count_markpats())
print(mb.count_markpats() == mb2.count_markpats())

mb.cmove(0, 0)
mb.cmove(1, 0)
mb2.cmove(0, 0)
mb2.cmove(1, 0)
print(mb.count_markpats())
print(mb2.count_markpats())
print(mb.count_markpats() == mb2.count_markpats())

実行結果

defaultdict(<class 'int'>, {(0, 0, 3): 8})
defaultdict(<class 'int'>, {(0, 0, 3): 8})
True
defaultdict(<class 'int'>, {(0, 1, 2): 2, (1, 0, 2): 1, (0, 0, 3): 4, (1, 1, 1): 1})
defaultdict(<class 'int'>, {(1, 1, 1): 1, (0, 1, 2): 2, (0, 0, 3): 4, (1, 0, 2): 1})
True

実行結果から 両者が同じ計算結果を返す ので、BitBoard クラスの count_markpats メソッドが 正しく実装できている可能性が高い ことが確認できます。

`setmark_by_move` メソッドのバグの修正

処理速度の検証を行う際に、BitBoard クラスの setmark_by_move メソッドに バグがある ことが判明したので修正します。具体的には calc_linemark が True の場合の下記の move のマスから マークを削除 する際の 9 行目の処理 が List1dBoard の処理と同じ である点が 間違っています。

1  def setmark_by_move(self, move, mark):
2      if self.count_linemark:
3          x, y = self.move_to_xy(move)
4          if mark != self.EMPTY:
5              diff = 1
6              changedmark = mark
7          else:
8              diff = -1
9              changedmark = self.board[move]
略

上記の 9 行目 は下記のプログラムのように 〇のビットボード と move の AND 演算 を行うことで move のマスに〇が配置されているか どうかを判定し、配置されている場合 は self.CIRCLE を、配置されていない場合 は self.CROSS を計算するように修正する必要があります⁷。

              changedmark = self.CIRCLE if self.board[0] & move else self.CROSS

下記はそのように setmark_by_move を修正 したプログラムで、上記以外は修正箇所はないので折りたたみました。

setmark_by_move の修正版

def setmark_by_move(self, move, mark):
    if self.count_linemark:
        x, y = self.move_to_xy(move)
        if mark != self.EMPTY:
            diff = 1
            changedmark = mark
        else:
            diff = -1
            changedmark = self.CIRCLE if self.board[0] & move else self.CROSS
            
        self.colcount[changedmark][x] += diff
        self.rowcount[changedmark][y] += diff
        if x == y:
            self.diacount[changedmark][0] += diff
        if x + y == self.BOARD_SIZE - 1:
            self.diacount[changedmark][1] += diff
    if mark == self.EMPTY:
        self.board[self.CIRCLE] &= ~0 ^ move
        self.board[self.CROSS] &= ~0 ^ move
    else:
        self.board[mark] |= move
        
BitBoard.setmark_by_move = setmark_by_move

処理速度の検証

count_markpats が実装 されたので、ai14s VS ai2 の対戦 を行うことができるようになりました。そこで これまでで最も処理速度が速い List1dBoard クラスと BitBoard クラスを利用した場合の 処理速度 を下記のプログラムで比較することにします。また、前回の記事の ai2 VS ai2 の対戦の 処理速度を計測 するプログラムが 間違っていた ので、下記で 改めてその処理速度を計測 することにします。

BitBoard クラスと ListBoard クラスを利用した場合の ai14s VS ai2 の対戦結果が変わらない ことからも、calc_markpats が正しく動作することが確認 できます。

from ai import ai2, ai14s, ai_match
from marubatsu import List1dBoard
import random

for boardclass in [BitBoard, List1dBoard]:
    for ai in [[ai2, ai2], [ai14s, ai2]]:
        for count_linemark in [False, True]:
            print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
            random.seed(0)
            ai_match(ai=ai, match_num=50000, mbparams={"boardclass": boardclass, "count_linemark": count_linemark})

実行結果

boardclass: BitBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 21704.15it/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%

boardclass: BitBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 16380.29it/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%

boardclass: BitBoard, count_linemark False
ai14s VS ai2
100%|██████████| 50000/50000 [00:16<00:00, 3086.52it/s]
count     win    lose    draw
o       49490       0     510
x       44103       0    5897
total   93593       0    6407

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.2%    0.0%   11.8%
total   93.6%    0.0%    6.4%

boardclass: BitBoard, count_linemark True
ai14s VS ai2
100%|██████████| 50000/50000 [00:22<00:00, 2272.21it/s]
count     win    lose    draw
o       49490       0     510
x       44103       0    5897
total   93593       0    6407

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.2%    0.0%   11.8%
total   93.6%    0.0%    6.4%

boardclass: List1dBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 21093.20it/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%

boardclass: List1dBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 16659.79it/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%

boardclass: List1dBoard, count_linemark False
ai14s VS ai2
100%|██████████| 50000/50000 [00:30<00:00, 1615.04it/s]
count     win    lose    draw
o       49490       0     510
x       44103       0    5897
total   93593       0    6407

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.2%    0.0%   11.8%
total   93.6%    0.0%    6.4%

boardclass: List1dBoard, count_linemark True
ai14s VS ai2
100%|██████████| 50000/50000 [00:19<00:00, 2615.95it/s]
count     win    lose    draw
o       49490       0     510
x       44103       0    5897
total   93593       0    6407

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.2%    0.0%   11.8%
total   93.6%    0.0%    6.4%

下記は上記の 実行結果をまとめた表 で、いずれの場合 でも BitBoard クラスを利用した count_linemark が False の場合の 処理速度が最も高速になる ことがわかります。また、このことから他のゲーム盤を表現するクラスでは count_linemark が False の場合よりも 高速になる場合がある count_linemark が True の場合の処理 が ビットボードを利用 ことで 不要になる ことがわかります。

`boardclass`	`count_linemark`	`ai2` VS `ai2`	`ai14s` VS `ai2`
BitBoard	`False`	21704.15 回/秒	3086.52 回/秒
List1dBoard	`False`	21093.20 回/秒	1615.04 回/秒
BitBoard	`True`	16380.29 回/秒	2272.21 回/秒
List1dBoard	`True`	16659.79 回/秒	2615.95 回/秒

今回の記事のまとめ

今回の記事では ビット列 の popcount の 様々な計算方法 について紹介し、その中で 最も高速 な bit_count メソッドを利用した count_markpats メソッドの実装 を行いました。その結果、ビットボードを利用 することで ai2 VS ai2 と ai14s VS ai2 の 処理速度がこれまでの実装よりも高速 になり、count_linemark が True の場合の処理が不要になることが確認できました。

今後の実装で比較を行うために BitBoard クラスの count_linemark が True の場合の処理は残しておく ことにします。

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

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

次回の記事

近日公開予定です

後述しますが、Python の int 型のデータには popcount を計算する bit_count というメソッドが定義されています ↩
a = a & (a - 1) と同じ処理です ↩
減算や乗算などの他の多くの演算でも同様です ↩
実際には b の popcount を計算する際に最初の b の値を取っておく必要はないので、c は必要はありません。このアルゴリズムの c をすべて b に置き換えても popcount は計算できるので、このアルゴリズムではそのようにプログラムを記述するのが一般的だと思います ↩
ビット長が約 1000 倍になった場合でも $log_2{1000}= 約 10$ なので繰り返し回数は 10 回しか増えません ↩
今回の記事の最初で説明したように、pop count のことを bit count と表記する場合があります ↩
move のマスにどちらのマークも配置されていない場合は正しい処理は行われませんが、setmark_by_move でマークを削除する処理は Marubatsu クラスの中で直前の着手を取り消す unmove メソッドからのみ呼び出されているので、そのような状況は現状では発生しないはずです ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Pythonで〇×ゲームのAIを一から作成する その213 ビット列の pop count の計算によるマークのパターンの計算

目次と前回の記事

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

BitBoard クラスの count_markpats の実装

必要な処理

確認のためのビットボードの作成

定義する関数の仕様

getmark を用いた実装

countmark1 の性質

popcount の計算による実装

定義する関数の仕様

popcount の処理の確認で利用する値の設定

1 つずつビットを数える方法

RSB を 0 にする計算を利用する方法

ビット演算を利用した別の計算方法

アルゴリズムの説明

0b10001101 に対して行われる処理の説明

手順 2 の効率的な計算方法

bwidth が 1 の場合の計算

偶数の番号のビットの計算

奇数の番号のビットの計算

2 ビット毎の 1 の個数の計算

2 ビットごとに分割したデータの偶数番のデータの計算

2 ビットごとに分割したデータの奇数番のデータの計算

4 ビット毎の 1 の個数の計算

popcount の計算

より具体的なアルゴリズム

popcount3 の定義

bit_count メソッドを利用した計算方法

popcount の処理時間のまとめ

countmark2 の実装

count_markpats の実装

setmark_by_move メソッドのバグの修正

処理速度の検証

今回の記事のまとめ

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その213　ビット列の pop count の計算によるマークのパターンの計算

BitBoard クラスの `count_markpats` の実装

`getmark` を用いた実装

`countmark1` の性質

`0b10001101` に対して行われる処理の説明

`bwidth` が `1` の場合の計算

`popcount3` の定義

`bit_count` メソッドを利用した計算方法

`countmark2` の実装

`count_markpats` の実装

`setmark_by_move` メソッドのバグの修正