Pythonで〇×ゲームのAIを一から作成する　その219　分割統治法を利用したビットボードの左右の反転処理を行うアルゴリズム

Last updated at 2026-03-15Posted at 2026-03-08

目次と前回の記事

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

ビット列の反転アルゴリズムの続き

今回の記事では最初に ビット列の反転処理 を行う他のアルゴリズムについて説明し、その後で ビットボードの左右の反転処理 について説明します。

用語の定義

これまでの記事では、「分割統治法による delta swap を利用したビット列の反転処理」のような表記を行ってきましたが、表記が長くて冗長なので以後は「delta swap によるビット列の反転」のように短く表記することにします。「分割統治法による全ビットの交換アルゴリズムを利用したビット列の反転処理」の場合も同様に「全ビットの交換によるビット列の反転」と表記することにします。また、これらの分割統治法を利用 したアルゴリズムのことを「分割統治法によるアルゴリズム」と表記することにします。

なお、以前の記事で紹介した delta swap で 1 ビットずつ交換 することでビット列の反転を行うアルゴリズムは 処理速度が遅いので今後は扱いません。

参照テーブルを利用するアルゴリム

以前の記事で紹介した 参照テーブル をビット列の反転処理にも利用することができます。参照テーブルを利用する場合 は、参照テーブルに 記録するデータの量を決める必要 があるので、本記事では以前の記事と同様に ビット長が 16 の すべてのビット列を反転した値を計算 した 参照テーブルを作成 することにします。ビット長が 8 の参照テーブルも良く使われているのではないかと思いますので、興味がある方は実装してみて下さい。

下記はそのような参照テーブルを利用した reverse9 を定義するプログラムです¹。reverse9 のアルゴリズムは以前の記事で紹介した、元のビット列 のビットを 下位のビットから 1 つずつ順番に取り出し て、計算結果を記録する変数 の 下位ビットに加える という処理を行う reverse4 と似ています。reverse4 との違い は 一度に複数のビットを取り出す 点です。下記の説明では reverse4 との違い について説明します。

1 ~ 6 行目：参照テーブルを作成する際に利用する、以前の記事で定義したビット列を反転する reverse1² を定義する
8 行目：reverse8 を利用して 0 ~ $2^{16} - 1$ までのそれぞれの値に対する、ビット長を 16 としたビット列を反転した値を計算した参照テーブルを作成する
13 行目：reverse4 では b から 1 ビットずつ値を取り出して retval の末尾の 1 ビットに追加するという処理を行うが、reverse9 では以下の処理を行う
- b & 0b1111111111111111 によって b の下位 16 ビット分のビット列を取り出す
- 取り出したビット列を参照テーブルを利用して反転する
- retval の末尾の 16 ビットに反転した値を追加する
14、15 行目：b から 16 ビット分のデータを取り出したので、b を 16 ビット右シフトしてそれらの値を削除し、まだ retval に追加していないビット長を表す length から 16 を減らす
16 ~ 19 行目：b の中の まだ取り出していない残りのビット長 が 16 未満 の場合に 13 ~ 15 行目の処理が行われると length から 16 が引かれて負の値になる場合 がある。例えば length の値が 10 の場合 は 15 行目の処理によって length が -6 になる。そのため、下記のように length の値によって行う処理を変える必要がある
- length が正の値 の場合は reverse4 と同様 に retval を length ビット左シフト した値を返す
- length が 負の値 の場合は -length ビット余分に左シフト しているので、-length ビット右シフト した値を返すことで 余分に左シフトした分を戻す 必要がある³

 1  def reverse1(b, length):
 2      result = 0
 3      for i in range(length):
 4          if b & (1 << i):
 5              result |= 1 << (length - i - 1)
 6      return result
 7  
 8  rtable = [reverse1(i, 16) for i in range(1 << 16)]
 9  
10  def reverse9(b, length):
11      retval = 0
12      while b:
13          retval = (retval << 16) | (rtable[b & 0b1111111111111111])
14          b >>= 16
15          length -= 16
16      if length > 0:
17          return retval << length
18      else:
19          return retval >> (-length)

行番号のないプログラム

def reverse1(b, length):
    result = 0
    for i in range(length):
        if b & (1 << i):
            result |= 1 << (length - i - 1)
    return result

rtable = [reverse1(i, 16) for i in range(1 << 16)]

def reverse9(b, length):
    retval = 0
    while b:
        retval = (retval << 16) | (rtable[b & 0b1111111111111111])
        b >>= 16
        length -= 16
    if length > 0:
        return retval << length
    else:
        return retval >> (-length)

下記は前回の記事と同じ反転処理を reverse9 で行い、reverse1 の結果と比較 することで 正しい処理が行われることを確認 するプログラムです。実行結果から reverse9 が正しい処理を行う ことが確認できました。

b = 0b01001101
for length in range(8, 18):
    print(f"bit length = {length}")
    print(f"0b{b:0{length}b}")
    print(f"0b{reverse9(b, length):0{length}b}")
    print(reverse9(b, length) == reverse1(b, length))

実行結果

bit length = 8
0b01001101
0b10110010
True
bit length = 9
0b001001101
0b101100100
True
bit length = 10
0b0001001101
0b1011001000
True
bit length = 11
0b00001001101
0b10110010000
True
bit length = 12
0b000001001101
0b101100100000
True
bit length = 13
0b0000001001101
0b1011001000000
True
bit length = 14
0b00000001001101
0b10110010000000
True
bit length = 15
0b000000001001101
0b101100100000000
True
bit length = 16
0b0000000001001101
0b1011001000000000
True
bit length = 17
0b00000000001001101
0b10110010000000000
True

処理時間の計測

下記は以前の記事と同様の方法で reverse9 の 処理時間を計測 するプログラムです。ただし、reverse9 は 1 である最も大きなビットの番号が小さい場合 は 繰り返し処理が少なくなる ので、すべてのビットが 1 である ビット列の反転処理 の処理時間も計測しました。

for length in [10, 100, 1000, 10000, 100000, 1000000]:
    print(f"bit length = {length}")
    b2 = (1 << length) - 1
    %timeit reverse9(b, length)
    %timeit reverse9(b2, length)

実行結果

bit length = 10
236 ns ± 1.07 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
254 ns ± 5.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
232 ns ± 11.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.46 μs ± 37.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 1000
239 ns ± 1.94 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
16.1 μs ± 84.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 10000
295 ns ± 1.39 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
363 μs ± 4.38 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 100000
441 ns ± 2.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
17.8 ms ± 221 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
bit length = 1000000
1.95 μs ± 35.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
1.6 s ± 1.03 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

下記は delta swap によるビット列の反転 を行う reverse6 と 全ビットの交換によるビット列の反転 を行う reverse8 と上記の実行結果をまとめた表です。reverse9 の下段以外 は 0b01001101、reverse9 の下段 は ビット長のすべてのビットが 1 のビット列 の反転の処理時間を表します。処理時間の単位は μs で、小数点以下第 2 桁で四捨五入しました。

ビット長	`reverse6`	倍率	`reverse8`	倍率	`reverse9`	倍率
10	1.6		1.4		0.2 0.3
100	4.6	2.9	2.9	2.0	0.2 1.5	1.0 5.7
1,000	10.1	2.2	5.6	1.9	0.2 16.1	1.0 11.0
10,000	39.7	3.9	43.9	7.8	0.3 363.0	1.2 22.5
100,000	239.0	6.0	351.0	8.0	0.4 17,800.0	1.5 49.0
1,000,000	2,590.0	13.7	3,570.0	10.2	2.0 1,600,000.0	4.4 90.0

0b01001101 は 1 である最も大きなビットの番号 が 6 で小さい ので、reverse9 の繰り返し処理は 1 回 しか行われません。そのため、すべての場合 で reverse6 と reverse8 よりも 大幅に処理時間が短い ことが確認できます。

一方 すべてのビットが 1 であるビット列の場合は、ビット長が 100 まで は 参照テーブルの処理の効率の良さ から reverse9 の処理速度が最速 になりますが、ビット長が大きくなる と 処理時間が非常に遅く なることが確認できます。なお、ビット長が大きくなると 処理時間が非常に遅くなる理由 は、以下の通りです。

reverse9 の 繰り返し処理の回数 は ビット長 ÷ 16 回（小数点以下切り上げ）なので、ビット長にほぼ比例 する
以前の記事で説明したように、Python では ビット長が大きくなる と ビット列の演算の処理時間 が ビット長にほぼ比例する ようになる
上記から ビット長が大きくなる と ビット列の 2 乗に比例 した 処理時間 になる

上記が正しいことは、ビット長 が 100,000 から 1,000,000 のように 10 倍 になった場合に 処理時間が 90 倍 という、10 の 2 乗 = 100 に近い値 になっていることから確認することができます。

上記から、参照テーブルを利用したアルゴリズム は 以下のような性質 があります。

ビット長が 100 以下 のように短く、繰り返し処理の回数が少ない場合 は最速である
ビット長が大きくなる と、反転するビット列 の 1 である最大のビットの番号 が 小さい場合は非常に高速 であるが、1 である最大のビットの番号が 大きくなると分割統治法によるアルゴリズムよりも大幅に遅く なる
そのため、平均的 に見ると ビット長が大きくなる と処理速度は 分割統治法によるアルゴリズムよりも大幅に遅く なる

str 型のデータに変換する方法

他のプログラミング言語ではあまり見かけませんが、Python での ビット列の反転のアルゴリズム として よく見かける のが str 型のデータに変換 する下記のアルゴリズムです。

ビット列を表す int 型のデータ を f 文字列などで 2 進数 を表す 先頭を 0 で埋めた length 文字 の str 型のデータに変換する
str 型のデータは list と同様に [] を記述して文字を参照できるので、以前の記事で説明した [::-1] というスライス表記 で文字列の 文字の順番を反転できる
組み込み関数 int を利用して 2 進数を表す文字列 を int 型のデータに変換 する

下記は str 型 のデータの後ろに [::-1] を記述 して 文字列を反転 するプログラムです。

print("abcdef"[::-1])

実行結果

fedcba

組み込み関数 int は、1 つ目の実引数 に 整数を表す文字列 を、2 つ目の実引数 に記述した 文字列の進数を表す数値 を記述⁴することで、任意の進数 で表現された 文字列 を int 型のデータに変換 することができます。例えば、下記のプログラムの 1 行目 では 0b1001 という 2 進数を表す文字列 を int 型 の 同じ数値を表すデータに変換 します。また、2 行目のように 2 進数を表す文字列 の 先頭の 0b を省略 することができます。

print(f"0b{int('0b1001', 2):b}")
print(f"0b{int('1001', 2):b}")

実行結果

0b1001
0b1001

組み込み関数 int の詳細については下記のリンク先を参照して下さい。

`reverse10` の定義

下記は 上記のアルゴリズム で ビット列の反転処理 を行う reverse10 を定義するプログラムで、2 行目では下記の処理を行っています。

f 文字列 の 書式指定 の 文字幅 の部分を {式} のように記述することで 式の計算結果の文字幅を指定 することができるので、0{length}b と記述することで b の値 を 先頭を 0 で埋めた length 文字 の 2 進数を表す str 型のデータに変換 する
その後ろに [::-1] を記述することで変換した 2 進数の文字列を反転する
反転した 2 進数の文字列を組み込み関数 int で int 型のデータに変換する

def reverse10(b, length):
    return int(f"{b:0{length}b}"[::-1], 2)

下記は先ほどと同じ反転処理を reverse10 で行うプログラムです。実行結果は先ほどと同じなので省略しますが、reverse10 が正しい処理を行う ことが確認できす。

for length in range(8, 18):
    print(f"bit length = {length}")
    print(f"0b{b:0{length}b}")
    print(f"0b{reverse10(b, length):0{length}b}")
    print(reverse10(b, length) == reverse1(b, length))

下記は reverse10 の 処理時間を計測 するプログラムです。reverse10 は ビット列の値によって処理時間は変わらない ので b = 0b01001101 の値だけ に対する 処理時間を計測 しました。

for length in [10, 100, 1000, 10000, 100000, 1000000]:
    print(f"bit length = {length}")
    %timeit reverse10(b, length)

実行結果

bit length = 10
598 ns ± 12.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
890 ns ± 3.01 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 1000
3.64 μs ± 18.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 10000
29.5 μs ± 65.1 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
bit length = 100000
287 μs ± 3.23 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 1000000
3.35 ms ± 33.6 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

下記は先ほどの表に上記の 実行結果をまとめた表です。処理時間の単位は μs で、小数点以下第 2 桁で四捨五入しました。また、表が横に長くなるので reverse10 以外の倍率の列は省略しました。

なお、reverse9 で 0b01001101 を反転する場合の処理時間 は reverse9 が特に高速に処理を行うことができる特殊なケース なので省略しました。そのため、reverse9 以外は 0b01001101、reverse9 はすべてのビットが 1 となるビット列 という、異なるデータに対する処理時間 が表記されているので、それぞれの関数の 処理時間の厳密な比較にはなっていません が、大まかな傾向を見ることはできる のではないかと思います。

ビット長	`reverse6`	`reverse8`	`reverse9`	`reverse10`	倍率
10	1.6	1.4	0.3	0.6
100	4.6	2.9	1.5	0.9	1.5
1,000	10.1	5.6	16.1	3.6	4.1
10,000	39.7	43.9	363.0	29.5	8.1
100,000	239.0	351.0	17,800.0	287.0	9.7
1,000,000	2,590.0	3,570.0	1,600,000.0	3,350.0	11.7

実行結果から以下のことがわかりました。

reverse10 は ビット長が 100 ~ 10,000 の範囲 では 最速である
reverse6 や reverse8 と同様に、ビット長が大きくなる と 処理時間がビット長にほぼ比例する ようになる
ビット長が 100,000 以降 は reverse6 が最速 になるが、reverse10 との処理速度の差はそれほどは大きくない

なお、Python の int 型のデータ は ビット長によって処理時間が変わる ので、これまでに紹介したすべてのビット列を反転する処理を行う関数は 同じビット長 であっても 反転するビット列の値 によって 処理時間が若干変わる可能性があります。そのことの具体例は今回の記事の最後で紹介します。本記事ではそれぞれの関数の 大まかな傾向を調べるだけにとどめます が、それぞれの関数の 厳密な性能 を知りたい方は、様々なビット列で処理時間を計測 してその 性質を調べてみると良い でしょう。

`zfill` メソッドを利用した str 型への変換方法

上記では f 文字列の書式指定の文字幅を利用してビット列を length 文字の 2 進数を表す str 型のデータに変換しましたが、指定した長さ で 先頭を 0（zero）で埋めた（fill）文字列を計算 するという str 型の zfill というメソッドを利用して変換することもできます。

下記は b = 0b01001101 を、f 文字列 と zfill メソッドを利用して下記の手順で 先頭を 0 で埋めた 16 文字の 2 進数を表す str 型のデータに変換 するプログラムです。

1 行目：f 文字列で 2 進数を表す文字列に変換する
2 行目：zfill メソッドの実引数に 16 を記述することで、上記の文字列の先頭を 0（zero）で埋めた 16 文字の文字列が計算される

print(f"{b:b}")
print(f"{b:b}".zfill(16))

実行結果

1001101
0000000001001101

下記は zfill を 利用しない場合 と する場合 の、b を先頭を 0 で埋めた 16 文字の 2 進数を表す str 型のデータに変換する処理の 処理時間を計測 するプログラムです。実行結果から zfill メソッドを利用したほうが処理速度が約 1.5 倍高速 になることが確認できました。

length = 16
%timeit f"{b:0{length}b}"
%timeit f"{b:b}".zfill(length)

実行結果

373 ns ± 4.54 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
229 ns ± 6.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

f"{b:0{length}b}" の処理速度が遅い理由は、文字列の長さを {式} という方法で指定しているからのようです。下記のプログラムのように直接文字列の長さを数値で記述した場合は zfill メソッドとほぼ同じ処理時間になるようです。

%timeit f"{b:016b}"

実行結果

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

str 型 のデータの zfill メソッドの詳細 については下記のリンク先を参照して下さい。

`reverse11` の定義

下記は zfill メソッドを利用 した ビット列の反転処理 を行う reverse11 の定義です。zfill を利用して length 文字の 2 進数の str 型のデータに変換 した値に対して [::-1] を記述して 文字列を反転 している点を除けば reverser10 と同様 です。

def reverse11(b, length):
    return int(f"{b:b}".zfill(length)[::-1], 2)

下記は 先ほどと同じ反転処理 を reverse11 で行うプログラムです。実行結果は先ほどと同じなので省略しますが、reverse11 が正しい処理を行う ことが確認できす。

for length in range(8, 18):
    print(f"bit length = {length}")
    print(f"0b{b:0{length}b}")
    print(f"0b{reverse11(b, length):0{length}b}")
    print(reverse11(b, length) == reverse1(b, length))

下記は reverse11 の 処理時間を計測 するプログラムです。

for length in [10, 100, 1000, 10000, 100000, 1000000]:
    print(f"bit length = {length}")
    %timeit reverse11(b, length)

実行結果

bit length = 10
449 ns ± 6.79 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
728 ns ± 1.49 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 1000
3.46 μs ± 11.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 10000
29 μs ± 181 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
bit length = 100000
284 μs ± 5.02 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 1000000
3.36 ms ± 40.4 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

下記は先ほどの表に上記の 実行結果をまとめた表です。処理時間の単位は μs で、小数点以下第 2 桁で四捨五入しました。また、表が横に長くなるので reverse11 以外の倍率の列は省略しました。

ビット長	`reverse6`	`reverse8`	`reverse9`	`reverse10`	`reverse11`	倍率
10	1.6	1.4	0.3	0.6	0.4
100	4.6	2.9	1.5	0.9	0.7	1.6
1,000	10.1	5.6	16.1	3.6	3.5	4.8
10,000	39.7	43.9	363.0	29.5	29.0	8.4
100,000	239.0	351.0	17,800.0	287.0	284.0	9.8
1,000,000	2,590.0	3,570.0	1,600,000.0	3,350.0	3,360.0	11.8

上記の表から、zfill を利用して str 型のデータに変換するアルゴリズム は ビット長が 100 まで は reverse10 と比較 して 処理時間の比率が低く なりますが、それより大きなビット長 の場合は 比率がほぼ変わらない ことが確認できました。これはおそらく ビット長が大きくなる と zfill を利用することによる処理時間の削減よりも、ビット長が大きくなることによる処理時間の増加の影響の方が大きいから ではないかと思います。

プログラムを短く記述 でき、ビット長が 10000 以下 の場合は 処理速度も最速 であることから、Python で ビット長が 10000 以下 の ビット列の反転処理 を行う場合は このアルゴリズムを利用すると良い のではないかと思います。

Google のサイトでビット列の反転について検索した際に、AI モードでは str 型のデータに変換するアルゴリズムは遅いという説明が表示されましたが、実際に計測してみるとビット長が短い場合は分割統治法によるアルゴリズムよりも速いことがわかったのは意外でした。

Python の int 型の演算処理がそれほど高速ではないのに対し、int 型のデータを str 型のデータに変換する処理や、str 型のデータをスライス表記で反転する処理が高速に行われるためこのようなことが起きるのではないかと思います。

他の方法として、int 型のデータを先頭に 0b がついた 2 進数の文字列に変換する組み込み関数 bin を利用するという方法があります。その場合は下記のプログラムのように先頭の 0b を削除するために、[2:] というスライス表記利用してから zfill メソッドを利用します。

print(bin(b))
print(bin(b)[2:])
print(bin(b)[2:].zfill(16))

実行結果

0b1001101
1001101
0000000001001101

下記はこの方法の処理時間を計測するプログラムで、"f{b:b}".zfill(16) の処理時間である 229 ns とほとんど変わらないことが確認できました。

%timeit bin(b)[2:].zfill(16)

実行結果

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

その他のアルゴリズム

他のアルゴリズム としては、Python では直接利用することはできません が、特定のビット長のビット列を反転 する CPU の命令を利用 するという方法が考えられ、そのビット長であればおそらく最も高速に処理を行えるのではないかと思います。

筆者が思いついた範囲のアルゴリズムを紹介しましたが、他にも有効なアルゴリズムがあるかもしれません ので、興味がある方は調べてみると良いでしょう。本記事で紹介したよりも高速な Python でのビット列の反転アルゴリズムをご存じの方はコメントなどで教えて頂けると助かります。

なお、本記事で紹介したアルゴリズムは、プログラム言語が異なると処理時間の性質が異なる場合がある 点に注意して下さい。そのため、他のプログラミング言語でビット列の反転処理を実装する場合は、改めてそれぞれのアルゴリズムの処理時間を計測し直して下さい。

ビットボードの左右の反転処理

ここまで ビット列の反転処理 の 様々なアルゴリズムを説明 してきたのは、ビット列の反転処理 が BitBoard クラスの calc_same_hashabels メソッドで行うゲーム盤を表す ビットボードの左右の反転処理 と 似ているから です。なお、以後は「ビットボードの左右の反転処理」を「ビットボードの反転処理」のように表記 することにします。

具体例として 3 x 3 のサイズのゲーム盤の ビットボードの反転処理 で説明します。下図左は 3 x 3 のサイズの ゲーム盤を表す図 で、マスの中の番号 はそのマスに対応する ビットボードのビットの番号 を表します。

このゲーム盤の 反転処理 は上図のように 0、1、2 番の順番 で並んだ 列の順番を反転 するという処理です。これに対して ビット長を 3 とした ビット列の反転処理 は、0、1、2 番の順番 で並んだ ビットの順番を反転 するという処理で、異なる点 は 反転するもの がゲーム盤の 列の番号 であるかと ビットの番号 であるかだけです。

このことから、ビット長を n とした ビット列の反転処理 と、n x n のサイズ の ビットボードの反転処理 は以下のように 同様の処理を行う ことがわかります。ただし、$\boldsymbol{i}$ は $\boldsymbol{0 ≦ i < n - i - 1}$ を満たす すべての整数 とします。交換する番号の式の意味 について忘れた方は以前の記事を復習して下さい。

ビット列の反転 は $\boldsymbol{i}$ 番と $\boldsymbol{n - i - 1}$ 番の ビットを交換 する
ビットボードの反転 は $\boldsymbol{i}$ 列と $\boldsymbol{n - i - 1}$ 列の ビットをまとめて交換 する

このことから、ビットボードの反転処理 でも、ビット列の反転処理 のように delta swap や 全ビットの交換アルゴリズム を利用した 分割統治法 で 計算できそう であることが推測でき、実際に分割統治法によるアルゴリズムで計算できます。最初に delta swap によるビットボードの反転処理 のアルゴリズムを紹介します。

delta swap によるビットボードの反転

n x n のサイズ のゲーム盤の ビットボード には 以下のような性質 があります。

列のマスの数 は すべて n 個 である
$\boldsymbol{i}$ 列の 各マスのビットの番号 は $i\ ×\ n$、$i\ ×\ n + 1$、・・・、$i\ ×\ n + n - 1$ である
従って $\boldsymbol{i}$ 列と $\boldsymbol{n - i - 1}$ 列のビットを交換する際の各ビットの間隔はすべて $(n - i - 1)\ ×\ n - i\ ×\ n = \boldsymbol{(n - 2\ ×\ i - 1)\ ×\ n}$ で等しいので、delta swap を利用して まとめて交換 することができる

上記から、ビットボードの反転処理 の場合でも delta swap を利用できる ことと、ビット列の反転処理と比較 すると、交換するビットの間隔 を表す delta がゲーム盤のサイズを表す n 倍 になることがわかります。

delta swap によるビットボードの反転処理を行うアルゴリズム

下記は前回の記事で説明した、ビット列 $\boldsymbol{b}$ を ビット長が $\boldsymbol{l}$ のビット列として 分割統治法による delta swap を利用した 反転処理 を行う アルゴリズムをまとめた ものです。

$n_0 = l$、$i = 0$ とする
$n_i = 1$ になるまで下記の処理を繰り返す
1. $i$ に 1 を足す
2. $n_i = n_{i - 1}\ //\ 2$ を計算する
3. $d_i = (n_{i - 1} + 1)\ //\ 2$ を計算する
4. $m_i$ を下記の手順で計算する
  - $i = 1$ の場合は $m_i = (1 << n_i) - 1$
  - そうでない場合は $m = m_{i-1}\ \text{&}\ (m_{i - 1} >> d_i)$、$m_i = m\ | \ (m << d_{i - 1})$
5. $b$ を $d_i$ と $m_i$ を利用して delta swap を行う

上記と ほぼ同じ下記のアルゴリズム で $\boldsymbol{l\ ×\ l}$⁵ のサイズの ビットボード $\boldsymbol{b}$ の反転処理 を行うことができます。下記のアルゴリズムの手順 2 では、上記の ビット列の反転処理の手順 2 で 交換するビットと同じ番号 の 列の交換 が行われます。

上記のアルゴリズムと異なる部分 は 手順 2-3 と 2-4 の 2 か所だけ で、その違いを（）内に説明 にしました。なお、$\boldsymbol{n_i}$ の計算式 は 上記のアルゴリズムと同じ なので、$\boldsymbol{n_i}$ には 上記のアルゴリズムと同じ値が計算 されます。そのため $\boldsymbol{n_i}$ は 上記のアルゴリズムと同じ表記 にしましたが、delta と ビットマスク は上記のアルゴリズムと 異なる値が計算される ので、違いがわかるように 記号を大文字 の $\boldsymbol{D_i}$ と $\boldsymbol{M_i}$ としました。

$n_0 = l$、$i = 0$ とする
$n_i = 1$ になるまで下記の処理を繰り返す
1. $i$ に 1 を足す
2. $n_i = n_{i - 1}\ //\ 2$ を計算する
3. $D_i = ((n_{i - 1} + 1)\ //\ 2)\ ×\ l$ を計算する（$\boldsymbol{d_i}$ の計算式の $\boldsymbol{l}$ 倍）
4. $M_i$ を下記の手順で計算する（左シフトと右シフト⁶のビット数が $\boldsymbol{l}$ 倍）
  - $i = 1$ の場合は $M_1 = (1 << (n_1 ×\ l)) - 1$
  - そうでない場合は $M = M_{i-1}\ \text{&}\ (M_{i - 1} >> D_i))$、$M_i = M\ | \ (M << D_{i - 1})$
5. $b$ を $D_i$ と $M_i$ を利用して delta swap を行う

なお、$\boldsymbol{D_i}$ はビット列の反転のアルゴリズムと同じ $\boldsymbol{n_i}$ の値から計算される ので、$\boldsymbol{D_i = d_i\ ×\ l}$ が成り立ちます。

5 x 5 でのビットボードの場合の処理

具体例として 5 x 5 のサイズの ビットボードの反転処理を 上記のアルゴリズムで行う場合の処理の流れを示すことで、上記のアルゴリズムで正しい計算が行われることを示します。

最初の 手順 1 では $\boldsymbol{n_0 = 5、i = 0}$ となります。

1 回目 の 手順 2 の繰り返し処理では下図のように ビット列の反転処理 で 交換するビットの番号 と 同じ番号 の 水色の 0、1 列 と 緑色の 3、4 列 のビットを まとめて交換 します。上記のアルゴリズム で そのような計算が行われる ことを示します。

1 回目 の 手順 2-1 ~ 2-3 では 下記の値が計算 されます。

$\boldsymbol{i = 1}$
$\boldsymbol{n_1 = 5\ //\ 2 = 2}$
$\boldsymbol{D_1 = ((5 + 1)\ //\ 2)\ ×\ 5 = 10}$

$\boldsymbol{n_1}$ の計算式 は ビット列の反転処理のアルゴリズムと同じ なので、$\boldsymbol{n_1}$ には ビット列の反転処理の場合と同様 に、幅がが $\boldsymbol{n_{0} = 5}$ の ビットボードの列を均等に分割 した場合の 列の長さが計算 されます。上図では 緑色の 0、1 列 の 2 列分 を表す 2 が計算 されます。

ビット列の反転処理 の場合の $\boldsymbol{d_1}$ は 0、1 番 と 3、4 番 のビットを まとめて交換する際 の ビットの間隔 を表します。ビットボードの反転処理 の場合の $\boldsymbol{D_1}$は 0、1 列 と 3、4 列 のビットを まとめて交換する際 の ビットの間隔 を表しますが、1 列には $\boldsymbol{l}$ 個のマスがある ので その数 は $\boldsymbol{D_1 = d_1\ ×\ l}$ 個となり、先程のアルゴリズムの式で計算 できます。

ビット列の反転処理 の場合の $\boldsymbol{m_1}$ は 0 番から $\boldsymbol{n_1}$ 個の 1 が並ぶビット列を計算 するために $\boldsymbol{m_1 = (1 << n_1) - 1}$ という式で計算していましたが、ビットボードの反転処理 の場合の $\boldsymbol{M_1}$は 0 番から $\boldsymbol{n_1}$ 列分のマスの数 だけ 1 が並ぶビット列を計算 する必要があります。マスの数 は $\boldsymbol{n_1\ ×\ l}$ なので先程のアルゴリズムで示した $\boldsymbol{M_1 = (1 << (n_\ ×\ l)) - 1}$ という式で計算することができます。

上記で計算した $\boldsymbol{D_1}$ と $\boldsymbol{M_1}$ を利用した delta swap で 水色の 0、1 列 と 緑色の 3、4 列 のビットを まとめて交換 することができます。

2 回目 の 手順 2 の繰り返し処理では下図のように ビット列の反転処理 で 交換するビットの番号 と 同じ番号 の 濃い色の 0、3 列 と 薄い色の 1、4 列 のビットを まとめて交換 します。上記のアルゴリズム で そのような計算が行われる ことを示します。

2 回目 の 手順 2-1 ~ 2-3 では 下記の値が計算 されます。

$\boldsymbol{i = 2}$
$\boldsymbol{n_2 = 2\ //\ 2 = 1}$
$\boldsymbol{D_1 = ((2 + 1)\ //\ 2)\ ×\ 5 = 5}$

$\boldsymbol{n_2}$ の計算式 は ビット列の反転処理のアルゴリズムと同じ なので、$\boldsymbol{n_2}$ には ビット列の反転処理の場合と同様 に、幅がが $\boldsymbol{n_1}$ の ビットボードの列を均等に分割 した場合の 列の長さが計算 されます。上図では 濃い色の 0 列及び 3 列 の 1 列分 を表す 1 が計算 されます。

先程と同様の理由から delta swap で交換する列の間隔 は $\boldsymbol{d_2}$ の $\boldsymbol{l}$ 倍なので $\boldsymbol{D_2 = d_2\ ×\ l}$ 表すアルゴリズムの式で計算 することができます。

下記は ビット列の反転処理 の場合の $\boldsymbol{m_2}$ を計算する式で、$\boldsymbol{d_2}$ ビットの右シフト演算 と $\boldsymbol{d_1}$ ビットの左シフト演算 を行うことで、0 番と 3 番のビットだけが 1 となる ビットマスクを計算 しています

$m = m_1\ \text{&}\ (m_1 >> d_2))$
$m_2 = m\ | \ (m << d_1)$

同様に ビットボードの反転処理 のビットマスクである $\boldsymbol{M_2}$ では、0 列と 3 列のマスのビットだけが 1 となる ビットマスクを計算する必要 があります。1 つの列 には $\boldsymbol{l}$ 個のマスが存在 するので、上記の式 の 右シフト演算と左シフト演算 で ずらずビットの数を $\boldsymbol{l}$ 倍にする必要があります。先ほど $\boldsymbol{D_i = d_i\ ×\ l}$ であることを示したので、$\boldsymbol{M_2}$ は先ほどのアルゴリズムで示した 下記の式で計算 することができます。

$M = M_1\ \text{&}\ (M_1 >> D_2))$
$M_2 = M\ | \ (M << D_1)$

上記が正しいことを図で確認 します。なお、ビット列の反転処理 での $\boldsymbol{m_2}$ の計算方法 について忘れた方は前回の記事を復習して下さい。

下図は $\boldsymbol{M}$ を計算する処理 を表す図です。ビット列の反転処理 の場合の $\boldsymbol{m}$ では、0 番と 1 番だけが 1 のビット列である $\boldsymbol{m_1}$ を $\boldsymbol{d_2 = 1}$ ビット右シフト した値と $\boldsymbol{m_1}$ との AND 演算 を行うことで、0 番だけが 1 のビット列 である $\boldsymbol{m}$ を計算します。ビットボードの反転処理 の場合は、下図の黄色の 0 列と 1 列 のマスに対応する ビットだけが 1 のビット列である $\boldsymbol{M_1}$ を $\boldsymbol{D_2 = 1\ ×\ 5 = 5}$ ビット右シフト した値と $\boldsymbol{M_1}$ との AND 演算 を行うことで、0 列に対応するマスだけが 1 のビット列 である $\boldsymbol{M}$ を計算することができます。このことから、$\boldsymbol{M}$ では $\boldsymbol{d_2}$ の $\boldsymbol{l}$ 倍である $\boldsymbol{D_2}$ ビットの左シフト演算を行う必要 があることがわかります。なお、ビット列 では 0 番のビットを右端に図示 してきましたが、ゲーム盤のビットボード では 0 列を左端に図示 するので、下図では 右シフト演算 によって 1 のビット が 逆の左にずれるように見える 点に注意して下さい。

下図は $\boldsymbol{M_2}$ を計算する処理 を表す図です。上図と 考え方は同様 なので説明は省略しますが、$\boldsymbol{m_2}$ を計算する際の $\boldsymbol{d_1}$ の $\boldsymbol{l}$ 倍である $\boldsymbol{D_1}$ ビットの右シフト演算 を行うことで、0 行と 3 行 に対応するマスのビットが 1 の $\boldsymbol{M_2}$ のビットマスクを計算 することができます。

上記では 5 x 5 のサイズのゲーム盤のビットボードで説明しましたが、同様の理由で 任意の大きさのサイズ のゲーム盤のビットボードでもこのアルゴリズムで ビットマスクである $\boldsymbol{M_i}$ を計算 することができます。

BitBoard クラスの `fliplr_ds` メソッドの定義

下記は上記のアルゴリズムで delta swap によるビットボードの反転 を行う BitBoard クラスの fliplr_ds メソッドを定義したプログラムです。この後で ビットボードの反転処理 を 全ビットの交換アルゴリズムを利用して実装 するので、そのメソッドと区別できる ように 名前に delta swap を表す ds を入れました。また、以前の記事で定義した ビット列の反転処理を同様のアルゴリズム で行う reverse7 を修正 して定義したので、説明と修正箇所は reverse7 からの修正を表します。

3 行目：fliplr_ds という名前でメソッドを定義する。reverse7 ではビット列とビット長を代入する仮引数 b と length があったが、それらの値は self.board とゲーム盤のサイズを表す self.BOARD_SIZE に代入されているのでそれらの仮引数は削除した
4 ~ 6 行目：delta swap を行う関数をメソッドとして定義しても構わないが、他のメソッドでは利用しないので今回はローカル関数として定義した
9 行目：仮引数 length を削除したので、その代わりにここで length にゲーム盤のサイズを表す self.BOARD_SIZE を代入する
11 行目：delta の計算式を reverse7 の場合の self.BOARD_SIZE 倍に修正した
14 行目：$M_1$ の計算式のシフト演算でずらす量を self.BOARD_SIZE 倍に修正した
18、19 行目：〇と × のビットボードに対して delta swap の計算を行うように修正した
ビットボードを左右に反転した値は self.board に計算されるので、返り値を返す必要がない。そのため最後に返り値を返さないように修正した

 1  from marubatsu import BitBoard
 2  
 3  def fliplr_ds(self):
 4      def delta_swap(b, mask, delta):
 5          c = (b ^ (b >> delta)) & mask
 6          return c ^ (c << delta) ^ b 
 7  
 8      mask = None
 9      length = self.BOARD_SIZE
10      while length > 1:
11          delta = (length + 1) // 2 * self.BOARD_SIZE
12          length //= 2
13          if mask is None:
14              mask = (1 << (length * self.BOARD_SIZE)) - 1
15          else:
16              m = mask & (mask >> delta)
17              mask = m | (m << prevdelta)
18          self.board[0] = delta_swap(self.board[0], mask, delta)
19          self.board[1] = delta_swap(self.board[1], mask, delta)
20          prevdelta = delta
21  
22  BitBoard.fliplr_ds = fliplr_ds

行番号のないプログラム

from marubatsu import BitBoard

def fliplr_ds(self):
    def delta_swap(b, mask, delta):
        c = (b ^ (b >> delta)) & mask
        return c ^ (c << delta) ^ b 

    mask = None
    length = self.BOARD_SIZE
    while length > 1:
        delta = (length + 1) // 2 * self.BOARD_SIZE
        length //= 2
        if mask is None:
            mask = (1 << (length * self.BOARD_SIZE)) - 1
        else:
            m = mask & (mask >> delta)
            mask = m | (m << prevdelta)
        self.board[0] = delta_swap(self.board[0], mask, delta)
        self.board[1] = delta_swap(self.board[1], mask, delta)
        prevdelta = delta

BitBoard.fliplr_ds = fliplr_ds

修正箇所

from marubatsu import BitBoard

-def reverse7(b, length)
+def fliplr_ds(self):
+   def delta_swap(b, mask, delta):
+       c = (b ^ (b >> delta)) & mask
+       return c ^ (c << delta) ^ b 
    
    mask = None
+   length = self.BOARD_SIZE
    while length > 1:
-       delta = (length + 1) // 2
+       delta = (length + 1) // 2 * self.BOARD_SIZE
        length //= 2
        if mask is None:
-           mask = (1 << length) - 1
+           mask = (1 << (length * self.BOARD_SIZE)) - 1
        else:
            m = mask & (mask >> delta)
            mask = m | (m << prevdelta)
-       b = delta_swap(b, mask, delta)
+       self.board[0] = delta_swap(self.board[0], mask, delta)
+       self.board[1] = delta_swap(self.board[1], mask, delta)
        prevdelta = delta
-   return b

BitBoard.fliplr = fliplr

上記の定義後に、下記のプログラムで いくつかのマスに配置 を行ってから fliplr_ds メソッドを実行して 局面を表示 することで 正しい反転処理が行われるかどうかを確認 します。また、2 回 fliplr_ds を行う ことで 元の局面に戻るかどうかも確認 しています。なお、変数名 は 3 x 3 のサイズ のゲーム盤なので mb3 としました。実行結果から 正しい処理が行われることが確認 できました。興味がある方は他の局面でも確認してみて下さい。

from marubatsu import Marubatsu

mb3 = Marubatsu(boardclass=BitBoard)
mb3.cmove(0, 0)
mb3.cmove(1, 0)
mb3.cmove(0, 1)
mb3.cmove(0, 2)
print(mb3)
mb3.board.fliplr_ds()
print(mb3)
mb3.board.fliplr_ds()
print(mb3)

実行結果

Turn o
ox.
o..
X..

Turn o
.xo
..o
..x

Turn o
ox.
o..
X..

下記は 5 x 5 のサイズのゲーム盤での確認を行うプログラムで、実行結果から 正しい処理が行われることが確認 できました。興味がある方は他の局面や他のサイズのゲーム盤でも確認してみて下さい。

mb5 = Marubatsu(boardclass=BitBoard, board_size=5)
mb5.cmove(0, 0)
mb5.cmove(1, 0)
mb5.cmove(2, 0)
mb5.cmove(0, 1)
mb5.cmove(3, 0)
mb5.cmove(1, 1)
mb5.cmove(0, 2)
mb5.cmove(1, 2)
mb5.cmove(2, 1)
mb5.cmove(1, 3)
mb5.cmove(2, 4)
print(mb5)
mb5.board.fliplr_ds()
print(mb5)
mb5.board.fliplr_ds()
print(mb5)

実行結果

Turn x
oxoo.
xxo..
ox...
.x...
..O..

Turn x
.ooxo
..oxx
...xo
...x.
..O..

Turn x
oxoo.
xxo..
ox...
.x...
..O..

処理時間の計測

下記は mb5 に対する fliplr_ds の処理時間を計測 するプログラムです。

%timeit mb5.board.fliplr_ds()

実行結果

1.46 μs ± 33.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

参照テーブルを利用した処理速度の改善

上記の fliplr_ds では 毎回 delta swap で利用 する delta とビットマスクの計算 を行っていますが、Marubatsu クラスのインスタンス は、作成した後でゲーム盤のサイズを変更しないことが前提 なので、あらかじめ fliplr_ds で計算する delta とビットマスクの一覧を計算 しておいた 参照テーブル を __init__ メソッドで作成 することで、処理速度を改善 することができます。

`init` メソッドの修正

下記は __init__ メソッドを fliplr_ds メソッドで利用する 参照テーブルを計算 するように修正したプログラムです。参照テーブル は fliplr_ds メソッドで利用する delta とビットマスクを要素とする tuple を 記録する list とし、fliplr_ds_table という名前の 属性に代入する ことにしました。また、7 ~ 19 行目を追加しただけなので、修正箇所は省略します。

7 行目：参照テーブルを計算する fliplr_ds_table 属性を空の list で初期化する
10 ~ 19 行目：fliplr_ds 内で行っていた delta とビットマスクを計算する処理を記述する。fliplr_ds との違いは 18 行目で fliplr_ds_table の要素に計算した delta と mask を要素とする tuple を追加する点と、delta swap の処理を削除した点である

 1  def __init__(self, board_size:int=3, count_linemark:bool=False):
 2      self.BOARD_SIZE = board_size
 3      self.bit_length = self.BOARD_SIZE ** 2
 4      self.count_linemark = count_linemark
 5  
 6      # 参照テーブルの計算
元と同じなので省略
 7      self.fliplr_ds_table = []
 8      mask = None
 9      length = self.BOARD_SIZE
10      while length > 1:
11          delta = (length + 1) // 2 * self.BOARD_SIZE
12          length //= 2
13          if mask is None:
14              mask = (1 << (length * self.BOARD_SIZE)) - 1
15          else:
16              m = mask & (mask >> delta)
17              mask = m | (m << prevdelta)
18          self.fliplr_ds_table.append((delta, mask))
19          prevdelta = delta
20  
21      self.initialize()    
22  
23  BitBoard.__init__ = __init__

行番号のないプログラム

def __init__(self, board_size:int=3, count_linemark:bool=False):
    self.BOARD_SIZE = board_size
    self.bit_length = self.BOARD_SIZE ** 2
    self.count_linemark = count_linemark

    # 参照テーブルの計算
    self.fullmask = (1 << self.BOARD_SIZE ** 2) - 1
    self.colmasks = []
    self.rowmasks = []
    self.diamask1 = 0
    self.diamask2 = 0
    for i in range(self.BOARD_SIZE):
        colmask = 0
        rowmask = 0
        for j in range(self.BOARD_SIZE):
            colmask |= self.xy_to_move(i, j)
            rowmask |= self.xy_to_move(j, i)
        self.colmasks.append(colmask)
        self.rowmasks.append(rowmask)
        self.diamask1 |= self.xy_to_move(i, i)
        self.diamask2 |= self.xy_to_move(i, self.BOARD_SIZE - i - 1)
    self.masklist = self.colmasks + self.rowmasks + [self.diamask1, self.diamask2]
    
    self.fliplr_ds_table = []
    mask = None
    length = self.BOARD_SIZE
    while length > 1:
        delta = (length + 1) // 2 * self.BOARD_SIZE
        length //= 2
        if mask is None:
            mask = (1 << (length * self.BOARD_SIZE)) - 1
        else:
            m = mask & (mask >> delta)
            mask = m | (m << prevdelta)
        self.fliplr_ds_table.append((delta, mask))
        prevdelta = delta
            
    self.initialize()    
    
BitBoard.__init__ = __init__

`fliplr_ds` メソッドの修正

下記は 参照テーブルを利用 するように fliplr_ds メソッドを修正 したプログラムで、fliplr_ds_table から順番 に delta とビットマスクを取り出し て、〇と × のビットボード に対して delta swap を行う ように修正しました。元のプログラムから大幅に変更 したので 修正箇所は省略 します。

def fliplr_ds(self):
    for delta, mask in self.fliplr_ds_table:
        self.board[0] = delta_swap(self.board[0], mask, delta)
        self.board[1] = delta_swap(self.board[1], mask, delta)

BitBoard.fliplr_ds = fliplr_ds

動作の検証と処理時間の計測

下記のプログラムで先程と同じ方法で fliplr_ds が正しく動作するかどうかを確認 すると、実行結果から 正しく動作することが確認 できました。なお、__init__ メソッドで新しい属性に値を代入 したので、mb3 と mb5 は作成し直す必要 があります。

mb3 = Marubatsu(boardclass=BitBoard)
mb3.cmove(0, 0)
mb3.cmove(1, 0)
mb3.cmove(0, 1)
mb3.cmove(0, 2)
print(mb3)
mb3.board.fliplr_ds()
print(mb3)
mb3.board.fliplr_ds()
print(mb3)
print()
mb5 = Marubatsu(boardclass=BitBoard, board_size=5)
mb5.cmove(0, 0)
mb5.cmove(1, 0)
mb5.cmove(2, 0)
mb5.cmove(0, 1)
mb5.cmove(3, 0)
mb5.cmove(1, 1)
mb5.cmove(0, 2)
mb5.cmove(1, 2)
mb5.cmove(2, 1)
mb5.cmove(1, 3)
mb5.cmove(2, 4)
print(mb5)
mb5.board.fliplr_ds()
print(mb5)
mb5.board.fliplr_ds()
print(mb5)

実行結果

Turn o
ox.
o..
X..

Turn o
.xo
..o
..x

Turn o
ox.
o..
X..

Turn x
oxoo.
xxo..
ox...
.x...
..O..

Turn x
.ooxo
..oxx
...xo
...x.
..O..

Turn x
oxoo.
xxo..
ox...
.x...
..O..

下記のプログラムで 修正した fliplr_ds メソッドの 処理時間を計測 すると、実行結果から 修正前の 1.46 μs と比較して約 1.3 倍に処理速度が改善 されたことが確認できました。

%timeit mb5.board.fliplr_ds()

実行結果

1.11 μs ± 19.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

全ビットの交換によるビットボードの反転

ビット列の反転のアルゴリズムと同様に、ビットボードの反転 の場合も前回の記事で説明した 分割統治法による全ビットの交換アルゴリズムを利用 することができます。具体的には、ゲーム盤の 列の数を $\boldsymbol{n}$ とした場合に、$\boldsymbol{n ≦ 2^m}$ となる最小の整数 $\boldsymbol{m}$ を計算 し、$\boldsymbol{2^m}$ 列 × n 行 のサイズのゲーム盤として 全ビットの交換アルゴリズム を利用します。

下図は 3 x 3 のサイズ のゲーム盤の場合の処理を行う図で、$\boldsymbol{3 < 2 ^ 2 = 4}$ なので、4 列 × 3 行のサイズ のゲーム盤として 反転処理 を行います。そのようにすることで 分割統治法 での繰り返し処理で行われる 列の交換処理 が 常にすべてのビットの交換 を行うため、全ビットの交換アルゴリズムを利用 することができます。

ただし、上図のように 反転処理を行う と、$\boldsymbol{2 ^ 2 - 3 = 1}$ 列分だけずれた状態 で反転が行われた ビットボードが計算される ので、上図のように その 1 列分 の $\boldsymbol{1 × 3 = 3}$ ビットの右シフト演算 を行うことで ビットボードの反転処理を行う ことができます。

上記から、$\boldsymbol{l\ ×\ l}$ のサイズのゲーム盤に対する 全ビットの交換によるビットボードの反転 は 下記のアルゴリズム で行うことができます。

$l ≦ 2^m$ となる最小の整数 $m$ を計算し、$n_0 = 2^m$、$i = 0$ とする
$n_i = 1$ になるまで下記の処理を繰り返す
1. $i$ に 1 を足す
2. $n_i = n_{i - 1}\ //\ 2$ を計算する
3. $D_i = n_i\ ×\ l$ を計算する
4. $M_i$ を下記の手順で計算する
  - $i = 1$ の場合は $<M_1 = (1 << D_1) - 1$
  - そうでない場合は $M = M_{i-1}\ \text{&}\ (M_{i - 1} >> D_i)$、$M_i = M\ | \ (M << D_{i - 1})$
5. $b = ((b >> D_i)\ \text{&}\ M_i)\ |\ ((b\ \text{&}\ M_i) << D_i)$ によって全列の交換を行う
$b = b >> (2^m - l)\ ×\ l$ を計算する

先程の delta swap を利用した場合との違い は以下の通りです。

手順 1 で $\boldsymbol{n_0}$ を計算する方法 が異なる
手順 2-3 での $\boldsymbol{n_{i-1}}$ は常に偶数になるので、$\boldsymbol{D_i}$ の計算式 を以下のようにした
$\boldsymbol{D_i} = ((n_{i - 1} + 1)\ //\ 2)\ ×\ l = (n_{i - 1}\ //\ 2)\ ×\ l = \boldsymbol{n_i\ ×\ l}$
手順 2-4 の 左シフト演算でずらすビット数 である $\boldsymbol{n_1\ × \ l = D_1}$ なので、$\boldsymbol{n_1\ × \ l}$ を $\boldsymbol{D_1}$ に置き換えた
手順 2-5 で全ビットの交換アルゴリズムで全列の交換を行う
$\boldsymbol{2^m - l}$ 列だけ ずれたビットボードが計算 されるので、手順 3 で 右シフト演算 で $\boldsymbol{(2^m - l)\ ×\ l}$ ビットずらす ことで ずれを戻す

`init` メソッドの修正

先程と同様に、上記のアルゴリズムで利用 する delta と ビットマスクの一覧を記録 した 参照テーブル を __init__ メソッドで計算 し、fliplr_sa_table という 属性に代入 することにします。なお、全（all）ビットを交換（swap）する ので 名前に swap all の略である sa を入れました。

7 行目：前回の記事で説明した方法で、self.BOARD_SIZE 以上で最も小さな 2 のべき乗を計算し、BB_SIZE という属性に代入する
8 行目：上記の手順 3 で最後に右シフトする $(2^m - l)\ ×\ l$ の値を計算して delta という属性に代入する
9 行目：参照テーブルを代入する fliplr_sa_table を空の list で初期化する
11 行目：length に self.BB_SIZE を代入するように修正した
14 行目：$D_i = n_i\ ×\ l$ なので、delta に $n_i$ の値が代入された length の self.BOARD_SIZE 倍の値を計算する
20 行目：fliplr_sa_table 属性の要素に、上記で計算した delta と mask を要素とする tuple を追加する

 1  def __init__(self, board_size:int=3, count_linemark:bool=False):
 2      self.BOARD_SIZE = board_size
 3      self.bit_length = self.BOARD_SIZE ** 2
 4      self.count_linemark = count_linemark
 5  
 6      # 参照テーブルの計算
元と同じなので省略
 7      self.BB_SIZE = 1 << (self.BOARD_SIZE - 1).bit_length()
 8      self.delta = (self.BB_SIZE - self.BOARD_SIZE) * self.BOARD_SIZE
 9      self.fliplr_sa_table = []
10      mask = None
11      length = self.BB_SIZE
12      while length > 1:
13          length //= 2
14          delta = length * self.BOARD_SIZE
15          if mask is None:
16              mask = (1 << (length * self.BOARD_SIZE)) - 1
17          else:
18              m = mask & (mask >> delta)
19              mask = m | (m << prevdelta)
20          self.fliplr_sa_table.append((delta, mask))
21          prevdelta = delta
22  
23      self.initialize()    
24  
25  BitBoard.__init__ = __init__

行番号のないプログラム

def __init__(self, board_size:int=3, count_linemark:bool=False):
    self.BOARD_SIZE = board_size
    self.bit_length = self.BOARD_SIZE ** 2
    self.count_linemark = count_linemark

    # 参照テーブルの計算
    self.fullmask = (1 << self.BOARD_SIZE ** 2) - 1
    self.colmasks = []
    self.rowmasks = []
    self.diamask1 = 0
    self.diamask2 = 0
    for i in range(self.BOARD_SIZE):
        colmask = 0
        rowmask = 0
        for j in range(self.BOARD_SIZE):
            colmask |= self.xy_to_move(i, j)
            rowmask |= self.xy_to_move(j, i)
        self.colmasks.append(colmask)
        self.rowmasks.append(rowmask)
        self.diamask1 |= self.xy_to_move(i, i)
        self.diamask2 |= self.xy_to_move(i, self.BOARD_SIZE - i - 1)
    self.masklist = self.colmasks + self.rowmasks + [self.diamask1, self.diamask2]
    
    self.fliplr_ds_table = []
    mask = None
    length = self.BOARD_SIZE
    while length > 1:
        delta = (length + 1) // 2 * self.BOARD_SIZE
        length //= 2
        if mask is None:
            mask = (1 << (length * self.BOARD_SIZE)) - 1
        else:
            m = mask & (mask >> delta)
            mask = m | (m << prevdelta)
        self.fliplr_ds_table.append((delta, mask))
        prevdelta = delta
        
    self.BB_SIZE = 1 << (self.BOARD_SIZE - 1).bit_length()
    self.delta = (self.BB_SIZE - self.BOARD_SIZE) * self.BOARD_SIZE
    self.fliplr_sa_table = []
    mask = None
    length = self.BB_SIZE
    while length > 1:
        length //= 2
        delta = length * self.BOARD_SIZE
        if mask is None:
            mask = (1 << (length * self.BOARD_SIZE)) - 1
        else:
            m = mask & (mask >> delta)
            mask = m | (m << prevdelta)
        self.fliplr_sa_table.append((delta, mask))
        prevdelta = delta
            
    self.initialize()    
    
BitBoard.__init__ = __init__

`fliplr_sa` メソッドの定義

下記は 参照テーブルを利用 して 全ビットの交換によるビットボードの反転 を行う fliplr_sa メソッドを定義するプログラムです。

3、4 行目：全ビットの交換アルゴリズムで、参照テーブルの値を利用して〇と × のビットボードの全列を交換する
5、6 行目：計算したビットボードは self.delta ビットだけずれているので、右シフト演算でずれを戻す

1  def fliplr_sa(self):
2      for delta, mask in self.fliplr_sa_table:
3          self.board[0] = (((self.board[0] >> delta) & mask) | ((self.board[0] & mask) << delta))
4          self.board[1] = (((self.board[1] >> delta) & mask) | ((self.board[1] & mask) << delta))
5      self.board[0] >>= self.delta
6      self.board[1] >>= self.delta
7  
8  BitBoard.fliplr_sa = fliplr_sa

行番号のないプログラム

def fliplr_sa(self):
    for delta, mask in self.fliplr_sa_table:
        self.board[0] = (((self.board[0] >> delta) & mask) | ((self.board[0] & mask) << delta))
        self.board[1] = (((self.board[1] >> delta) & mask) | ((self.board[1] & mask) << delta))
    self.board[0] >>= self.delta
    self.board[1] >>= self.delta

BitBoard.fliplr_sa = fliplr_sa

先程と同様の下記のプログラムで fliplr_sa が正しく動作するかどうかを確認 すると、実行結果から 正しく動作することが確認 できました。

mb3 = Marubatsu(boardclass=BitBoard)
mb3.cmove(0, 0)
mb3.cmove(1, 0)
mb3.cmove(0, 1)
mb3.cmove(0, 2)
print(mb3)
mb3.board.fliplr_sa()
print(mb3)
mb3.board.fliplr_sa()
print(mb3)
print()
mb5 = Marubatsu(boardclass=BitBoard, board_size=5)
mb5.cmove(0, 0)
mb5.cmove(1, 0)
mb5.cmove(2, 0)
mb5.cmove(0, 1)
mb5.cmove(3, 0)
mb5.cmove(1, 1)
mb5.cmove(0, 2)
mb5.cmove(1, 2)
mb5.cmove(2, 1)
mb5.cmove(1, 3)
mb5.cmove(2, 4)
print(mb5)
mb5.board.fliplr_sa()
print(mb5)
mb5.board.fliplr_sa()
print(mb5)

実行結果

Turn o
ox.
o..
X..

Turn o
.xo
..o
..x

Turn o
ox.
o..
X..

Turn x
oxoo.
xxo..
ox...
.x...
..O..

Turn x
.ooxo
..oxx
...xo
...x.
..O..

Turn x
oxoo.
xxo..
ox...
.x...
..O..

処理時間の検証

fliplr_ds と fliplr_sa の 処理時間 を 下記の条件の全ての組み合わせで計測 してみることにします。

ゲーム盤のサイズ が 3、4、8、16、32、64、128、129 の場合
ビットボードの値 が 0、1、すべてのビットが 1 の場合

ゲーム盤のサイズ としては、〇× ゲームと同じ 3、2 のべき乗 である値を 4 ~ 128 まで 、$\boldsymbol{2^7 = 128 < 129 < 2^8 = 256}$ なので 全ビットの交換アルゴリズムを利用する場合 に 実際に計算するゲーム盤のサイズ が 129 から 256 に大きく増える 129 を選択しました。ゲーム盤の サイズの最大値を 129 としたのは、このサイズより大きな ゲーム盤の ゲームはほとんどないのではないか と思ったからです。

ビットボードの値 としては、fliplr_ds と fliplr_sa の 処理時間の大小が変化 するような値を調べてみたところ、0、1、すべてのビットが 1 の場合 に 処理時間の大小が変化することがわかった のでそれらを選択しました。

なお、実際の〇× ゲーム では同じマスに〇と × が同時に配置されることはないので 〇と × のビットボードの値 が 0 以外で同じになることはありません が、下記ではプログラムの 記述のしやすさを考慮 して 〇と × のビットボードに同じ値を代入 しました。

for board_size in [3, 4, 8, 16, 32, 64, 128, 129]:
    print(f"board size = {board_size}")
    mb = Marubatsu(boardclass=BitBoard, board_size=board_size)
    print("ビットボードが 0 の場合")
    %timeit mb.board.fliplr_ds()
    %timeit mb.board.fliplr_sa()
    print("0 番のビットだけが 1 の場合")
    mb.board.board[0] = 1
    mb.board.board[1] = 1
    %timeit mb.board.fliplr_ds()
    %timeit mb.board.fliplr_sa()
    print("全ビットが 1 の場合")
    mb.board.board[0] = (1 << mb.board.bit_length) - 1
    mb.board.board[1] = (1 << mb.board.bit_length) - 1
    %timeit mb.board.fliplr_ds()
    %timeit mb.board.fliplr_sa()
    print()

実行結果

board size = 3
ビットボードが 0 の場合
454 ns ± 1.17 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
815 ns ± 1.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
0 番のビットだけが 1 の場合
491 ns ± 11.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
899 ns ± 13.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
全ビットが 1 の場合
503 ns ± 2.23 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.05 μs ± 5.04 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

board size = 4
ビットボードが 0 の場合
799 ns ± 1.63 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
825 ns ± 13.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
0 番のビットだけが 1 の場合
991 ns ± 9.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
886 ns ± 0.998 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
全ビットが 1 の場合
973 ns ± 16.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.03 μs ± 13.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

board size = 8
ビットボードが 0 の場合
1.23 μs ± 11.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.3 μs ± 10.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
0 番のビットだけが 1 の場合
1.84 μs ± 13.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.6 μs ± 23.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
全ビットが 1 の場合
1.84 μs ± 20.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.76 μs ± 14.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

board size = 16
ビットボードが 0 の場合
1.6 μs ± 4.46 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.64 μs ± 7.23 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
0 番のビットだけが 1 の場合
2.74 μs ± 60.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.15 μs ± 45 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
全ビットが 1 の場合
2.41 μs ± 71.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.44 μs ± 8.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 32
ビットボードが 0 の場合
2 μs ± 11.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
2.07 μs ± 54 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
0 番のビットだけが 1 の場合
3.89 μs ± 24.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
3.12 μs ± 12.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
全ビットが 1 の場合
3.65 μs ± 12.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
3.6 μs ± 14 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 64
ビットボードが 0 の場合
2.42 μs ± 16.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.52 μs ± 10.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
0 番のビットだけが 1 の場合
7.98 μs ± 27.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
6.12 μs ± 93.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
全ビットが 1 の場合
8.44 μs ± 10.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
9.61 μs ± 12.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 128
ビットボードが 0 の場合
2.79 μs ± 18.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.94 μs ± 27.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
0 番のビットだけが 1 の場合
18.9 μs ± 92.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
15.2 μs ± 56 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
全ビットが 1 の場合
21.1 μs ± 148 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
24.5 μs ± 106 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 129
ビットボードが 0 の場合
2.73 μs ± 13.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
3.41 μs ± 15.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
0 番のビットだけが 1 の場合
19 μs ± 110 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
34.4 μs ± 88.1 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
全ビットが 1 の場合
21.4 μs ± 392 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
45.6 μs ± 127 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

下記は上記の実行結果をまとめた表です。2 列目以降の 列の見出し は ビットボードの値 を表します。処理時間の単位は μs で、小数点以下第 3 桁で四捨五入しました。また、上段が fliplr_ds、下段が fliplr_sa の処理時間を表します。

ゲーム盤のサイズ	`0`	`1`	すべてのビットが `1`
3	0.45 0.81	0.49 0.90	0.50 1.05
4	0.80 0.83	0.99 0.89	0.97 1.03
8	1.23 1.30	1.84 1.60	1.84 1.76
16	1.60 1.64	2.74 2.15	2.41 2.44
32	2.00 2.07	3.89 3.12	3.65 3.60
64	2.42 2.52	7.98 6.12	8.44 9.61
128	2.79 2.94	18.90 15.20	21.10 24.50
129	2.73 3.41	19.00 34.40	21.40 45.60

ゲーム盤を表す ビットボードのビット長 はゲーム盤の マスの数と同じ です。従って ゲーム盤のサイズが 2 倍 になると ビットボードのビット長 は 2 × 2 = 4 倍 になりますが、上記の表から ゲーム盤のサイズが 2 倍 になっても 処理時間 はいずれも 4 倍ではなく、約 1.2 ~ 2.5 倍 程度にしかなっていません。このことから ゲーム盤のサイズが 128 まで では、処理時間 はゲーム盤の マスの数の比例よりも大幅に少なく増える ことがわかるので、これらの 分割統治法を利用したアルゴリズム で 十分に高速な処理を行える ことが確認できました。

また、上記の結果から以下の事が考察できます。

ゲーム盤のサイズが 3 の場合は 常に fliplr_ds の方が 処理速度が速い。これは、ゲーム盤のサイズが 3 の場合は 繰り返し処理の回数がどちらも 1 回 であるのに対し、fliplr_sa では 最後に右シフト演算を行う必要がある からではないかと思われる
ゲーム盤のサイズが 129 の場合も 常に fliplr_ds の方が 処理速度が速い。これは、先程説明したように、fliplr_sa では 実際に計算するゲーム盤のサイズ が 129 から 256 に大きく増える ため、計算する ビットボードのビット長 が計算途中で dfliplr_ds の場合よりも大きく増えて処理時間が長くなるから である

以下は ゲーム盤のサイズが 2 のべき乗 の場合の考察です

ビットボードが 0 の場合は 両者の処理時間はほぼ同じ であり、処理時間は 他のビットボードの場合よりも短い。これは、ビットボードが 0 の場合は途中の計算で列のデータを入れ替えても ビットボードの値が常に 0 になる ことが原因である。ゲーム盤のサイズが大きくなっても ビットボードの値は 常に 0 でビット長が短い ので 処理時間 は他のビットボードの場合よりも 短くなる
ビットボードが 1 の場合は fliplr_sa の方が 処理時間が短く なる
ビットボードのすべてのビットが 1 の場合は fliplr_ds の方がほとんどの場合で 処理時間が少し短く なるが その差は大きくはない

ビットボードが 1 と すべてのビットが 1 で上記のような結果になる理由を説明するとかなり複雑で長くなるので説明は省略します。上記からおそらく以下の事が言えるのではないかと思われます。

ゲーム盤のサイズ が 2 のべき乗 の場合は 基本的 には 全ビットの交換 を利用した fliplr_sa の方が処理速度が若干速くなる が、ビットボードの値によっては遅くなる 場合がある
fliplr_sa は ゲーム盤のサイズ と 実際に計算するゲーム盤のサイズの差が大きい程 fliplr_ds よりも 処理速度が遅くなる

なお、上記の組み合わせはほんの一部に過ぎないので、上記のプログラムの結果だけ で fliplr_ds と fliplr_sa の本当の性能を検証 するには 不十分 です。たとえば もっと大きなサイズのゲーム盤 では 上記の考察とは異なる結果になる可能性 があります。両者の性質をより深く知りたい 方は、もっと 様々な状況で検証 してみて下さい。

その他のビットボードを反転するアルゴリズム

これまでの記事で紹介 した、ビット列の反転を行うアルゴリズム を利用して ビットボードの反転を行うことができます が、本記事では下記の理由から それらは採用しません。興味がある方は実際に実装して処理時間を計測してみて下さい。

各列を順番に計算するアルゴリズム

以前の記事で紹介した、各ビットを順番に計算 するアルゴリズムと同様に、各列を順番に計算 することもできますが、以前の記事で処理速度を検証したように ビット列の場合 は 分割統治法を利用したアルゴリズムよりも 明らかに 処理速度が遅く なります。同様の理由 から ビットボードの反転処理の場合 も分割統治法を利用したアルゴリズムよりも 処理速度が遅くなるので採用しません。

以前の記事で紹介した delta swap を利用 して 1 ビットずつビットを交換 するアルゴリズムと同様に、delta swap を利用して 1 列ずつビット列を交換 することもできますが、こちらも分割統治法を利用したアルゴリズムより 処理速度が遅くなるので採用しません。

参照テーブルを利用するアルゴリズム

今回の記事で紹介した、参照テーブルを利用するアルゴリズム は、ゲーム盤が小さい場合 はおそらく 高速に計算を行うことができる と思いますが、先程検証したように ビット長が長くなると処理時間が非常に遅くなる ので、任意のサイズ のゲーム盤を扱う BitBoard クラスでの利用には向いていない と思いましたので 採用しません。

str 型のデータに変換する方法

今回の記事で紹介した str 型のデータに変換するアルゴリズム は、ビット列の反転処理を行う場合は有効ですが、列ごとに反転処理 を行うという ビットボードの反転処理の場合はうまく利用することができません。そのため、残念ながら 採用することはできません。

今回の記事の内容

今回の記事では、ビット列の反転処理 を行う他のアルゴリズムと、分割統治法を利用したビットボードの反転処理 を行う アルゴリズムを紹介 し、一般的なサイズのゲーム盤 ではそれらのアルゴリズムで 高速に計算を行うことができる ことを確認しました。

次回の記事では ビットボードの転置処理 を行うアルゴリズムを紹介する予定です。

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

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

次回の記事

関数の名前の 9 は前回の記事で定義した reverse8 の次の番号です ↩
これまでに定義した reverse1 ~ reverse8 のどれを定義してもかまいません。本記事では記述が短い reverse1 を定義しました ↩
length が 0 の場合に行われる 0 ビットの右シフト演算では値は変化しません。なお、左シフト演算でずらすビット数に負の値を指定すると右シフト演算が行われると思う人がいるかもしれませんが、残念ながら左シフトや右シフト演算でずらすビット数に負の値を指定するとエラーが発生します ↩
2 つ目の実引数を省略すると、10 進数を表す文字列が記述されたとみなします ↩
ビット列の反転アルゴリズムの記号にあわせて、ゲーム盤のサイズを n × n ではなく、$l$ × $l$ としました ↩
手順 2-4 の $D_i$ と $D_{i-1}$ は $d_i$ と $d_{i-1}$ の $l$ 倍です ↩

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を一から作成する その219 分割統治法を利用したビットボードの左右の反転処理を行うアルゴリズム

目次と前回の記事

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

ビット列の反転アルゴリズムの続き

用語の定義

参照テーブルを利用するアルゴリム

処理時間の計測

str 型のデータに変換する方法

reverse10 の定義

zfill メソッドを利用した str 型への変換方法

reverse11 の定義

その他のアルゴリズム

ビットボードの左右の反転処理

delta swap によるビットボードの反転

delta swap によるビットボードの反転処理を行うアルゴリズム

5 x 5 でのビットボードの場合の処理

BitBoard クラスの fliplr_ds メソッドの定義

処理時間の計測

参照テーブルを利用した処理速度の改善

__init__ メソッドの修正

fliplr_ds メソッドの修正

動作の検証と処理時間の計測

全ビットの交換によるビットボードの反転

__init__ メソッドの修正

fliplr_sa メソッドの定義

処理時間の検証

その他のビットボードを反転するアルゴリズム

各列を順番に計算するアルゴリズム

参照テーブルを利用するアルゴリズム

str 型のデータに変換する方法

今回の記事の内容

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その219　分割統治法を利用したビットボードの左右の反転処理を行うアルゴリズム

`reverse10` の定義

`zfill` メソッドを利用した str 型への変換方法

`reverse11` の定義

BitBoard クラスの `fliplr_ds` メソッドの定義

`init` メソッドの修正

`fliplr_ds` メソッドの修正

`init` メソッドの修正

`fliplr_sa` メソッドの定義