Pythonで〇×ゲームのAIを一から作成する その220 ビットボードの転置アルゴリズム

目次と前回の記事

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

今回の記事の内容

前回までの記事で calc_same_hashables メソッドで必要となる ビットボードの反転処理の実装 を行いましたが、今回の記事ではもう一つの必要となる処理である x 座標と y 座標を反転 させるという、ビットボードの転置処理 を実装します。

以前の記事では 3 x 3 のサイズ のゲーム盤の ビットボードの転置処理 について説明しました。3 x 3 のサイズ のゲーム盤の場合は、下図のように 1、5 番と 3、7 番 のビットの交換と、2 番と 6 番 の ビットの交換 によって 転置処理を行う ことができます。

一方、BitBoard クラスは 任意のサイズのゲーム盤を扱う ことができるので、任意のサイズ のゲーム盤の場合の 転置処理を行う必要 があります。そのアルゴリズムとして 分割統治法 を 利用しない アルゴリズムと 利用する アルゴリズムを紹介します。

なお、ビットボードの転置処理 では上図からもわかるように (0, 0) などの x 座標と y 座標が同じマス は 移動しません。そのため、ビットボードの転置処理でビットを交換する際は以前の記事で説明した 全ビットの交換アルゴリズムを利用することはできない ので、delta swap で ビットの交換処理を行う必要 があります。

分割統治法を利用しないビットボードの転置処理

最初に比較的誰でも思いつきそうな、分割統治法を利用しない ビットボードの 転置処理のアルゴリズム について説明します。そのアルゴリズムについて少し考えてみて下さい。

4 x 4 のサイズのゲーム盤の転置処理の性質

下図は 4 x 4 のサイズ のゲーム盤の ビットボードの転置処理 の図です。delta swap で 複数のビットをまとめて交換 する際は、交換するビットの間隔が同じ である必要があるので、交換するビットの間隔が同じビット を 同じ系統の薄い色と濃い色 で塗りつぶしました。具体的には、茶色、青色、赤色 の 薄い色と濃い色 の ビットを交換 します。

上図のそれぞれの色の交換するビットの 番号と間隔 は下記の表のようになります。

色	交換するビット	交換するビットの間隔
茶色	1、6、11 番と 4、9、14 番	3
青色	2、7 番と 8、13 番	6
赤色	3 番と 12 番	9

また、図からそれぞれの色のビットは以下のような性質を持つことがわかります。

色	薄い色のマス	濃い色のマス
茶色	(0, 1) から右下方向の直線上のマス	(1, 0) から右下方向の直線上のマス
青色	(0, 2) から右下方向の直線上のマス	(2, 0) から右下方向の直線上のマス
赤色	(0, 3) から右下方向の直線上のマス	(3, 0) から右下方向の直線上のマス

n x n のサイズのゲーム盤の転置処理の性質

上記から、n x n のサイズ のゲーム盤の ビットボードの転置処理 は $\boldsymbol{1 ≦ i < n}$ を満たす 全ての整数 $\boldsymbol{i}$ に対して 下記のビットをまとめて delta swap で交換 することで行うことができることがわかります。

• (0, $\boldsymbol{i}$) のマスから 右下方向の直線上のマス に対応するビット
• ($\boldsymbol{i}$, 0) のマスから 右下方向の直線上のマス に対応するビット

また、交換する具体的なマスの座標 は以下のようになります。

• (0, $i$)、(1, $i$ + 1)、・・・（$n$ - 1 - $i$, $n$ - 1)
• ($i$, 0)、($i$ + 1, 1)、・・・（$n$ - 1, $n$ - 1 - $i$)

上記は $\boldsymbol{0 ≦ j < n - i}$ を満たす 全ての整数 $\boldsymbol{j}$ に対して 下記のマスのビットを交換する と 言い換える ことができます。

• ($\boldsymbol{j}$, $\boldsymbol{i}$ + $\boldsymbol{j}$) のマス
• ($\boldsymbol{i}$ + $\boldsymbol{j}$, $\boldsymbol{j}$) のマス

n x n のサイズ のゲーム盤を表すビットボードの ($\boldsymbol{x}$, $\boldsymbol{y}$) のマスに対応する ビットの番号 は 下記の式で計算 することができます。

$\boldsymbol{x}$ × $\boldsymbol{n}$ + $\boldsymbol{y}$

従って、上記は $\boldsymbol{0 ≦ j < n - i}$ を満たす 全ての整数 $\boldsymbol{j}$ に対して 下記のビットを交換する と 言い換える ことができます。

• ($\boldsymbol{j}$, $\boldsymbol{i}$ + $\boldsymbol{j}$) のマスに対応する $\boldsymbol{i + (n + 1)\ ×\ j}$ 番のビット
• ($\boldsymbol{i}$ + $\boldsymbol{j}$, $\boldsymbol{j}$) のマスに対応する $\boldsymbol{i\ ×\ n + (n + 1)\ ×\ j}$ 番のビット

従って delta swap で まとめて交換するビットの間隔 を表す delta は下記の式から $\boldsymbol{(n - 1)\ ×\ i}$ となります。

$(i\ ×\ n + (n + 1)\ ×\ j) - (i + (n + 1)\ ×\ j) = (n - 1)\ ×\ i$

下記は 4 x 4 のサイズ のゲーム盤の場合に まとめて交換するビットの表の再掲 です。$\boldsymbol{n = 4}$ とし、$\boldsymbol{i}$ を 1、2、3 とした場合に 上記の式から下記の表の値が計算できる ことを確認して下さい。

色	交換するビット	交換するビットの間隔
茶色	1、6、11 番と 4、9、14 番	3
青色	2、7 番と 8、13 番	6
赤色	3 番と 12 番	9

上記から delta swap の計算に必要な ビットマスク は交換する 小さいほうのビットの番号 である $\boldsymbol{i + (n + 1)\ ×\ j}$ 番 の ビットを 1 とした ビット列 であることがわかります。

分割統治法を利用できない理由

上記のアルゴリズムで実装を行う前に、このアルゴリズムでは 分割統治法を利用できない理由 について説明します。4 x 4 のサイズ のゲーム盤を下図のように 45 度時計回りに回転 し、それぞれのマスを縦方向に並べた ものを 列と考える と、赤色 のマスは 0 列と 6 列、青色 のマスは 1 列と 5 列、茶色 のマスは 2 列 と 4 列 となります。

従って、ビットボードの転置処理 は上図の 0 ~ 6 列を反転する処理 を行うと 考えることができる ので、以前の記事で説明したビットボードの反転処理と同様に分割統治法を利用できるのではないかと考えた人がいるかもしれませんが、残念ながら 下記の理由から分割統治法を利用することはできません。

7 列 の ビットボードの反転処理 を 分割統治法で行う場合 は 以前の記事で説明したように、最初に 7 列 を 0、1、2 列 と 4、5、6 列 に 均等に分割 してそれらの列を まとめて交換する処理 を行う必要がありますが、先程の表で示したように上図の 3 つの列のビットの間隔 は 3、6、9 のように 同じではありません。そのため delta swap でまとめてこれらの列を交換することはできない ので 分割統治法を利用することはできません。これは、4 × 4 以外のサイズ のゲーム盤を表す ビットボードでも同様 です。
　

__init__ メソッドの修正

上記の delta swap を利用 したアルゴリズムで ビットボードの転置（transpose）処理を行う transpose_ds メソッドを定義することにします。その際に、前回の記事 て定義した fliplr_ds と同様 に delta swap で 必要となるビットマスクと delta の値を計算 した 参照テーブルを __init__ メソッドで計算 しておくことにします。

下記はそのように __init__ メソッドを修正 したプログラムです。参照テーブルに代入する値 は前回の記事の fliplr_ds と同様に transpose_ds メソッドで利用する delta とビットマスクを要素とする tuple を順番に 記録する list とし、transpose_ds_table という名前の 属性に代入する ことにしました。また、10 ~ 15 行目を追加しただけなので修正箇所は省略します。なお、もしかするとビット列の反転処理の場合のようにビットマスクを効率よく計算する方法があるのかもしれませんが、良い方法が思いつかなかったので 対応するマスのビットを一つずつ 1 にする方法で計算 しました。

• 9 行目：参照テーブルを計算する transpose_ds_table 属性を空の list で初期化する
• 10 ~ 14 行目：1 ≦ i < self.BOARD_SIZE の範囲の整数に対する繰り返し処理を行う
• 11 行目：i の値に対応するビットマスクを計算する変数を 0 で初期化する
• 12、13 行目：i ≦ j < self.BOARD_SIZE - 1 の範囲の整数に対する繰り返し処理を行い、mask に代入された値の (j, i + j) のマスに対応するビットを 1 にすることでビットマスクを計算する
• 14 行目：delta の値として (self.BOARD_SIZE - 1) * i を計算し、transpose_ds_table の要素に delta と mask を要素とする tuple を追加する

 1  from marubatsu import BitBoard
 2  
 3  def __init__(self, board_size:int=3, count_linemark:bool=False):
 4      self.BOARD_SIZE = board_size
 5      self.bit_length = self.BOARD_SIZE ** 2
 6      self.count_linemark = count_linemark
 7  
 8      # 参照テーブルの計算
元と同じなので省略
 9      self.transpose_ds_table = []
10      for i in range(1, self.BOARD_SIZE):
11          mask = 0
12          for j in range(self.BOARD_SIZE - i):
13              mask |= self.xy_to_move(j, i + j)
14          self.transpose_ds_table.append(((self.BOARD_SIZE - 1) * i, mask))
15  
16      self.initialize()    
17  
18  BitBoard.__init__ = __init__

行番号のないプログラム

from marubatsu import BitBoard

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.transpose_ds_table = []
    for i in range(1, self.BOARD_SIZE):
        mask = 0
        for j in range(self.BOARD_SIZE - i):
            mask |= self.xy_to_move(j, i + j)
        self.transpose_ds_table.append(((self.BOARD_SIZE - 1) * i, mask))
            
    self.initialize()    
    
BitBoard.__init__ = __init__

delta_swap と transpose_ds メソッドの定義

下記は 参照テーブルを利用 して先程のアルゴリズムで ビットボードの転置処理 を行う transpose_ds メソッドを定義するプログラムです。なお、delta swap の処理を行う関数 はこの後で定義する 別のメソッドでも必要になる ので グローバル関数として定義 し、marubatsu.py に記述 することにします。

• 2 ~ 4 行目：delta swap を行う関数をローカル関数として定義する
• 6、8 行目：参照テーブルの値を利用して 〇 と × のビットボードのビットを delta swap でまとめて交換する

 1  def delta_swap(b, mask, delta):
 2      c = (b ^ (b >> delta)) & mask
 3      return c ^ (c << delta) ^ b 
 4
 5  def transpose_ds(self):
 6      for delta, mask in self.transpose_ds_table:
 7          self.board[0] = delta_swap(self.board[0], mask, delta)
 8          self.board[1] = delta_swap(self.board[1], mask, delta)
 9  
10  BitBoard.transpose_ds = transpose_ds

行番号のないプログラム

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

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

BitBoard.transpose_ds = transpose_ds

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

from marubatsu import Marubatsu

mb4 = Marubatsu(boardclass=BitBoard, board_size=4)
movelist = [(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
for x, y in movelist:
    mb4.cmove(x, y)
print(mb4)
mb4.board.transpose_ds()
print(mb4)
mb4.board.transpose_ds()
print(mb4)

実行結果

Turn o
o...
xo..
oxx.
xooX

Turn o
oxox
.oxo
..xo
...X

Turn o
o...
xo..
oxx.
xooX

なお、処理時間 については分割統治法を利用した実装を行ってから 後でまとめて検証する ことにします。

分割統治法によるビットボードの転置処理

上記で説明したアルゴリズム は 分割統治法を利用できない ので n x n のサイズ のゲーム盤に対して n - 1 回 の delta swap の処理を行う必要があります。

それに対し、上記のアルゴリズムと 異なるビット列の交換 を行うことで、分割統治法を利用 した場合より 少ない 2 を底とした n の対数 で計算される $\boldsymbol{log_2 n}$ 回 の delta swap で ビットボードの転置処理 を行うことができるのでその方法を紹介します。

説明するのを忘れてたことに気が付きましたのでここで説明しますが、下図のグラフが示すように $\boldsymbol{x ≧ 1}$ の範囲では $\boldsymbol{x}$ が増加した際 に、$\boldsymbol{log_2 x}$ は $\boldsymbol{x}$ よりも大幅に緩やかに増加する という性質があるので、ゲーム盤のサイズが大きくなるほど分割統治法を利用したアルゴリズムのほうが処理速度が大幅に高速 になります。

アルゴリズムの処理にかかる時間 のことを 計算量¹ と呼び、計算量を表す記法 として O 記法 が使わます。今回までの記事の説明を読んで 計算量や O 記法の説明がない 点について疑問に思った方がいるのではないかと思いますので補足します。

O 記法 は簡単にいうと、例えばゲーム盤のサイズなどの 特定のパラメータを $\boldsymbol{n}$ と表記 した際に、アルゴリズムの 計算量 が $\boldsymbol{n}$ が大きくなった場合 に $\boldsymbol{n}$ を用いた式にほぼ比例する ことを表す記法です。例えば $\boldsymbol{O(n)}$ の場合はアルゴリズムの 計算量が $\boldsymbol{n}$ にほぼ比例 し、$\boldsymbol{O(n^2)}$ の場合 $\boldsymbol{n^2}$ にほぼ比例 することを表します。

ただし、上記で説明したように $\boldsymbol{n}$ が小さい場合 は 必ずしも 計算量が () の中に記述した式に 比例するとは限りません。先ほど紹介したビットボードの転置処理 のアルゴリズムは n - 1 回の delta swap を行うので、筆者も最初は 計算量 は $\boldsymbol{n}$ に比例 することを表す $\boldsymbol{O(n)}$ になるのではないか と思っていました。実際には Python の int 型 のデータは ビット長が大きくなる と 処理時間がビット長に比例する²ようになり、n x n のサイズ のゲーム盤のビットボードの ビット長は $\boldsymbol{n^2}$ なので、おそらく 計算量は $\boldsymbol{O(n^3)}$ になるのではないかと思われます。ただし、現実的なサイズ の 〇× ゲームの ゲーム盤 のビットボードのように ビット長が小さい場合 は 計算量は $\boldsymbol{n}$ にほぼ比例 するので、O 記法と実際の計算量が一致しなくなります。例えば前回の記事で検証した ビット列の反転処理 の 処理時間の計測結果 がそのことを表しています。これが、これまでの記事で O 記法を紹介しなかった理由です。

なお、一般的なアルゴリズム では、ビットボードのように 非常に長いビット長の int 型の計算を行うことはほとんどない と思いますので、int 型のデータの演算の処理時間は一定だと考えて良い のではないかと思います。これは、最近の CPU が 64 ビットの整数の計算を一度で行う ことができる 機能を持っている ため、64 以下のビット長の整数の演算 であれば 同じ処理時間 で計算を行うことができるからです。例えば 1 兆 のような 非常に大きな整数でもビット長は 40 にしかなりません。

また、Python の float 型 のデータや、他の多くのプログラミング言語の整数型や浮動小数点型 のデータは ビット長が決まっている ので 数値の値によって 計算の 処理時間が変化することはありません。

計算量と O 記法については今後の記事で機会があれば説明したいと思います。今回の記事では参考までに Wikipedia の計算量と O 記法に関する記事を下記に示します。

分割統治法による画像の転置処理のアルゴリズム

以前の記事で説明したように、分割統治法 は 大きな規模の処理 を 処理の規模を小さくした複数の処理に変換 することで計算を行うアルゴリズムです。1 次元 のデータである ビット列の反転処理 の場合は ビット列を均等に分割 し、ビットボードの 次元の 1 つ である 列の反転だけ を行う ビットボードの反転処理 の場合は ビットボードの列を左右に均等に分割 して処理を行いました。一方、行と列 の 2 つの次元 を入れ替える ビットボードの転置処理 の場合は、ビットボードを 行と列 のそれぞれに対して 均等に分割 します。

ビットボード だと図の見た目がわかりづらいと思いますので、最初に下図の 正方形の画像の転置処理 を例に説明します。なお、画像を正方形 とした理由は本記事が扱う 〇× ゲームのゲーム盤が正方形だから です。また、画像が正方形でない 場合は 4 つに 分割した部分を転置 すると 形が変わってしまう ため 下記のアルゴリズムは利用できません。

画像の転置処理 は、下図左のように 画像の左上から右下の対角線 を引き、その 対角線を軸に画像を 180 度回転 させて右図のように ひっくり返す という処理です。

　

分割統治法 による画像の転置処理では、この画像を下図のように 縦と横をそれぞれ均等に分割 した線を引いて 4 つの正方形の画像に分割 します。

ただし、この 4 分割した それぞれの画像 に下図左のように 対角線をひいて 下図中央のように ひっくり返 すと、元の画像を転置 した 下図右の画像と少し異なる画像 になります。

　　

上図右の 正しい転置画像 と上図 中央の画像を見比べる と、左上と右下 の画像は 正しく転置 されており、左下と右上 の 画像を入れ替える と 正しい転置画像 になることがわかります。

従って、下図右 のように下図左の元の画像を 4 分割した 左下と右上の画像を入れ替える ことによって、元の画像を転置 するという処理が、元の画像の 縦横のサイズを半分にした 4 つの画像を転置 するという、複数の小さな画像の転置処理に変換 することができます。

　

ピンとこない人は、正方形の折り紙などの紙を用意し、最初に上図の青線で折り曲げて折り目を付け、その後で左上から右下の対角線を軸にひっくり返してみて下さい。ひっくり返すことで以下のようなことが起きることがわかるはずです。

• 左上と右下の部分の正方形の位置は変わらない
• 左下と右上の部分の正方形の位置が入れ替わる
• 4 つの正方形は、それぞれを左上から右下の対角線でひっくり返したものになる

また、分割した 4 つのそれぞれの画像 に対しても 同様の分割と入れ替え を行うことで、さらに小さな複数の画像の転置処理に変換 することができます。この作業 を 分割した画像のサイズ が転置する必要がない 1 x 1 のサイズになるまで行う ことで、元の画像を転置 することができます。これが、分割統治法による画像の転置処理のアルゴリズム です。

上記では画像で説明しましたが、ビットボード でも 同様のアルゴリズムで転置処理を行う ことができるので、以下では ビットボードの場合で説明 します。

ビットボードの縦横のサイズの条件

上記では説明していませんでしたが、このアルゴリズムを利用する場合 は、ビットボードの 縦横のサイズが $\boldsymbol{2^m}$ で表される 2 のべき乗でなければならない という 条件があります。

ビットボードの 縦横のサイズが 2 のべき乗でない場合 は、このアルゴリズムの処理の最中で 分割したビットボードのサイズが奇数になる 場合が生じます。例えば、下図のような 5 x 5 のサイズ のビットボードの場合は、下図のように 行と列を均等に 2 つに分割することができない ので 行と列を 2、1、2 の幅 に 3 つに分割 する必要があります。

この場合に 左下と右上の緑の正方形の部分を交換 することで、4 つの 2 x 2 の正方形の部分 に関しては それぞれを転置する処理に変換 することができますが、青色と茶色の部分 は 正方形ではない ので先ほどのアルゴリズムとは 別の方法で交換 する必要があります。

この後で説明しますが、このアルゴリズム では delta swap を利用 することで 分割したすべての正方形の左下と右上のビットをまとめて交換できる ことによって delta swap を行う回数を少なく しています。上図の 水色と茶色の部分の交換処理 は それとは別の delta swap を行う必要がある ので、delta swap を行う回数 がその分だけ 大きく増えてしまいます。これが、ビットボードの縦横のサイズ が 2 のべき乗でなければならない理由 です。

ビット列の反転処理 の場合は、ビット長が奇数 のビット列を分割した際の 真ん中の 1 ビットは反転する必要がない という性質があったため、任意のビット長 のビット列に対して delta swap による 分割統治法で反転処理を行う ことができました。一方、ビットボードの転置処理 の場合は分割した 真ん中の列と行 のうち、上図の 青色と茶色の部分のビットを交換する必要がある 点が異なります。

分割統治法を利用したビットボードの転置処理のアルゴリズム

下記は、分割統治法 を利用した ビットボードの転置処理 のアルゴリズムです。

1. ビットボードのサイズが 1 x 1 であれば、転置する必要がないので 処理を終了 する
2. ビットボードを 縦横 1/2 のサイズに 4 分割 する
3. 分割した 左下と右上のビットボードのビットを交換 する
4. 4 分割したそれぞれのビットボードを転置 すると 分割前 のビットボードを 転置したビットボードになる ので、4 分割した ビットボードのサイズが 1 x 1 のサイズになるまで それぞれのビットボードに対して 上記の手順 2、3 を処理 を行う

このアルゴリズムでは 繰り返し処理のたび に分割した ビットボードのサイズが半分 になります。また ビットの交換を delta swap で行う ので、n x n のサイズ のビットボードの場合は先ほど言及したように $\boldsymbol{log_2 n}$ 回の delta swap の処理 が行われます。

具体例としてこのアルゴリズムで 下図左の 8 x 8 のサイズ のゲーム盤の ビットボードの転置処理 を 説明します。以後の図の マスの中の番号 は特に説明がない場合は 転置する前のビットボードのビットの番号 を表します。従って、転置処理 によって 下図右 のように 番号が左から右に増える ように 並べ変わります。

　

1 回目の手順 2 と 3 の処理

下図左 は 1 回目の手順 2 の処理を表す図で、8 x 8 のサイズのビットボードを 赤枠で 4 つの 4 x 4 のサイズのビットボードに 4 分割 しています。

下図右 は 1 回目の手順 3 の処理を表す図で、薄い緑色と濃い緑色 の 左下と右上 の 4 x 4 のサイズの ビットボードを入れ替え ています。

上図からわかるように、薄い緑色と濃い緑色 の部分の 交換するビット は 右に 4 列、上に 4 行ずれて います。1 列右にずれる と ビットの番号が行の数である 8 増え、1 行上にずれる と ビットの番号が 1 減る ので、ビットの番号の 間隔 は 4 × 8 - 4 = 28 になります。

交換する ビットの間隔 は すべて 28 なので delta を 28、ビットの番号が小さいほうの 薄い緑色のビットを 1 とする ビットマスク とした delta swap で 1 回目の手順 3 の処理を行う ことができます。

下記は 対角線を含む左下半分の範囲のマス に 順番にマークを配置 した 8 x 8 のサイズ のビットマップに対して 1 回目の手順 3 の処理 を行うプログラムです。実行結果から 上図のビットの交換処理が正しく行われることが確認 できます。

• 2 ~ 5 行目：2 重の繰り返し処理で、対角線上を含む左下半分のマスに順番に着手を行い、ゲーム盤表示する
• 7、8 行目：薄い緑色のビットを 1 とするビットマスクを mask に代入する。なお、ビットマスクはこれまでと同様に 2 進数で記述したが、非常に長いので 8 行目のコメントでは参考までに 16 進数で短く記述する方法を記した
• 10 ~ 12 行目：delta swap で 〇 と × のビットボードの上図の緑色の部分のビットを交換してゲーム盤を表示する

 1  mb8 = Marubatsu(boardclass=BitBoard, board_size=8)
 2  for x in range(8):
 3      for y in range(x, 8):
 4          mb8.cmove(x, y)
 5  print(mb8)
 6  
 7  mask = 0b0000000000000000000000000000000011110000111100001111000011110000
 8  # mask = 0x00000000f0f0f0f0
 9  delta = 28
10  mb8.board.board[0] = delta_swap(mb8.board.board[0], mask, delta)
11  mb8.board.board[1] = delta_swap(mb8.board.board[1], mask, delta)
12  print(mb8)

行番号のないプログラム

mb8 = Marubatsu(boardclass=BitBoard, board_size=8)
for x in range(8):
    for y in range(x, 8):
        mb8.cmove(x, y)
print(mb8)

mask = 0b0000000000000000000000000000000011110000111100001111000011110000
# mask = 0x00000000f0f0f0f0
delta = 28
mb8.board.board[0] = delta_swap(mb8.board.board[0], mask, delta)
mb8.board.board[1] = delta_swap(mb8.board.board[1], mask, delta)
print(mb8)

実行結果

Turn o
o.......
xo......
oxx.....
xoox....
oxxoo...
xooxxo..
oxxooxx.
xooxxooX

Turn o
o...oxxo
xo..xoox
oxx.oxxo
xooxxoox
....o...
....xo..
....oxx.
....xooX

2 回目の手順 2 と 3 の処理

下図左 は 2 回目の手順 2 の処理を表す図で、4 つの黒枠 で囲まれた 4 x 4 のサイズ の それぞれのビットボード を 赤枠で 4 つの 2 x 2 のサイズ のビットボードに 4 分割 しています。その結果、全体として 16 個 の 2 x 2 のサイズ のビットボードに 分割 されます。

下図右 は 2 回目の手順 3 の処理を表す図で、4 つの 4 x 4 のサイズ のそれぞれのビットボードの、左下の薄い色と右上の濃い色 の 2 x 2 のサイズの ビットボードを入れ替え ています。

上図からわかるように、薄い色と濃い色 の 交換するマス は 右に 2 列、上に 2 行ずれて います。1 列右にずれるとビットの番号が行の数である 8 増え、1 行上にずれるとビットの番号が 1 減るので、その 間隔 を表す delta は 2 × 8 - 2 = 14 になります³。

また、ビットマスク は下図の 緑色のマスのビットを 1 とする ビット列 になります。なお、以後の ビットマスクを表す図 では、上図と異なり マスの中の番号 は転置する前のビットの番号ではなく、ビットマスクの 1 のビットの番号 を表します。

下記は 先ほどのビットボード に対して 2 回目の手順 3 の処理を行う プログラムです。行う処理は先ほどと同様なので説明は省略します。少々わかりにくいですが、実行結果から 上図のビットの交換処理が正しく行われることが確認 できます。

print(mb8)
mask = 0b0000000000000000110011001100110000000000000000001100110011001100
# mask = 0x0000cccc0000cccc
delta = 14
mb8.board.board[0] = delta_swap(mb8.board.board[0], mask, delta)
mb8.board.board[1] = delta_swap(mb8.board.board[1], mask, delta)
print(mb8)

実行結果

Turn o
o...oxxo
xo..xoox
oxx.oxxo
xooxxoox
....o...
....xo..
....oxx.
....xooX

Turn o
o.oxoxox
xoxoxoxo
..x.xoxo
..oxoxox
....o.ox
....xoxo
......x.
......oX

3 回目の手順 2 と 3 の処理

下図左 は 3 回目の手順 2 の処理を表す図で、16 個の黒枠 で囲まれた 2 x 2 のサイズ の それぞれのビットボード を 赤枠で 4 つの 1 x 1 のサイズ のビットボードに 4 分割 しています。その結果、全体として 64 個 の 1 x 1 のサイズ のビットボードに 分割 されます。

下図右 は 3 回目の手順 3 の処理を表す図で、16 個の 2 x 2 のサイズ のそれぞれのビットボードの、左下の薄い青と右上の濃い青 の 1 x 1 のサイズの ビットボードを入れ替え ています。なお、色が足りないので下図では 入れ替えるマスの色をすべて同じ色で統一 しました。

分割したビットボードのサイズ が 1 x 1 になった のでアルゴリズムの 処理はここで終了 し、右上図 に元のビットボードを 転置したビットボードが正しく計算 されていることがわかります。

上図からわかるように、薄い青色と濃い青色 の部分の 交換するマス はいずれも 右に 1 列、上に 1 行ずれて いるので、その 間隔 を表す delta は 1 × 8 - 1 = 7 になります。

また、ビットマスク は下図の 緑色のマスのビットを 1 とする ビット列 になります。

下記は 先ほどのビットボード に対して 3 回目の手順 3 の処理 を行うプログラムです。行う処理は先ほどと同様なので説明は省略します。実行結果 と その下に表記した元のゲーム盤を比較 することで、ビットボードの 転置処理が正しく行われることが確認 できます。

print(mb8)
mask = 0b0000000010101010000000001010101000000000101010100000000010101010
# mask = 0x00aa00aa00aa00aa
delta = 7
mb8.board.board[0] = delta_swap(mb8.board.board[0], mask, delta)
mb8.board.board[1] = delta_swap(mb8.board.board[1], mask, delta)
print(mb8)

実行結果

Turn o
o.oxoxox
xoxoxoxo
..x.xoxo
..oxoxox
....o.ox
....xoxo
......x.
......oX

Turn o
oxoxoxox
.oxoxoxo
..xoxoxo
...xoxox
....oxox
.....oxo
......xo
.......X

最初のゲーム盤

Turn o
o.......
xo......
oxx.....
xoox....
oxxoo...
xooxxo..
oxxooxx.
xooxxooX

ビットマスクと delta の計算方法

上記では 図からビットマスクと delta を求めましたが、実際には プログラムでそれらの値を計算する必要がある ので、2 のべき乗 である n × n のサイズ の ビットボードの転置処理 で 必要となるビットマスクと delta の計算方法 について説明します。

記号の定義

下記は、分割統治法を利用したビットボードの転置処理のアルゴリズムの再掲です。

1. ビットボードのサイズが 1 x 1 であれば、転置する必要がないので処理を終了する
2. ビットボードを 1/2 のサイズに 4 分割する
3. 分割した左下と右下のビットボードの位置を入れ替える
4. 4 分割したそれぞれのビットボードを転置すると求めるビットボードになるので、4 分割したビットボードのサイズが 1 x 1 のサイズになるまでそれぞれのビットボードに対して上記の手順 2、3 を処理を行う

この後の 説明をしやすいよう に、以下の 記号を定義 することにします。ただし、転置するゲーム盤のサイズ を n × n とし、n は 2 のべき乗である ものとします。

記号	意味
$\boldsymbol{n_i}$	$i$ 回目の手順 2 で分割されたビットボードのサイズ ただし、$n_0 = n$ とする
$\boldsymbol{d_i}$	$i$ 回目の手順 3 の delta swap で利用する delta
$\boldsymbol{m_i}$	$i$ 回目の手順 3 の delta swap で利用するビットマスク

上記の 手順 2 では ビットボードのサイズを半分にする ので、下記の式が成り立ちます。

$\boldsymbol{n_i = \frac{n_{i - 1}}{2}}$

i 回目の手順 3 の delta の計算式

下図は i 回目の手順 2 の処理の結果を表す図で、黒枠 で囲まれた $\boldsymbol{n_{i-1}}$ x $\boldsymbol{n_{i-1}}$ のサイズ の それぞれのビットボード を 赤枠 で 4 つの $\boldsymbol{n_{i}}$ x $\boldsymbol{n_{i}}$ のサイズ のビットボードに 4 分割 します。また、i 回目の手順 3 の処理では下図の 薄い緑色の範囲 のビットをその 右上の濃い緑色の範囲 のビットと 交換 します。

上図からわかるように、薄い緑色と濃い緑色 の 交換するマス は 右に $\boldsymbol{n_{i}}$ 列、上に $\boldsymbol{n_{i}}$ 行ずれて います。1 列右にずれる とビットの番号が 行の数である $\boldsymbol{n}$ 増え、1 行上にずれる とビットの番号が 1 減る ので、その 間隔 を表す $\boldsymbol{d_i}$ は 下記の式で計算 できます。

$\boldsymbol{d_i} = n_i\ ×\ n - n_i = \boldsymbol{(n - 1)\ ×\ n_i}$

下記に、上記の式 で先程の 8 x 8 のサイズ ビットボードの場合の 1、2、3 回目 の手順 3 の delta の値 である 28、14、7 が計算できる ことを示します。

$n = n_0 = 8$
$n_1 = \frac{n_0}{2} = 4$
$d_1 = (n - 1)\ ×\ n_1 = 7\ × \ 4 = 28$
$n_2 = \frac{n_1}{2} = 2$
$d_2 = (n - 1)\ ×\ n_2 = 7\ × \ 2 = 14$
$n_3 = \frac{n_2}{2} = 1$
$d_3 = (n - 1)\ ×\ n_3 = 7\ × \ 1 = 7$

i 回目の手順 3 のビットマスクの方法

下図は i 回目の手順 3 の ビットマスク である $\boldsymbol{m_i}$ を表す図で、緑色の範囲のビットを 1 とした ビット列が $\boldsymbol{m_i}$ の値 になります。

図からわかるように $\boldsymbol{m_i}$ は 規則正しく並んだ複数個の正方形の範囲 から 構成される ので、一つ一つの正方形の範囲のビットを 1 にする処理 を 繰り返し処理で行う ことができますが、上図からわかるように 緑色の部分の面積 は 全体の面積の 1/4 なので、1 のビットの数 は ビットボードのビット長の 1/4 になります。そのため、その処理は 繰り返し処理の回数 が $\boldsymbol{n^2}$ に比例する ため $n$ が大きくなると処理時間が非常に長く なります。そこで、別の もっと効率の良い方法 で ビットマスクを計算する ことにします。

その方法は 下図の順番 で 図の黄色の部分が 1 のビット列を計算 するという方法です。なお、以後は上図の ビットマスク の ビットの値が 1 となる 緑色の正方形 のことを単に 正方形と表記 することにします。

1. 複数の正方形の範囲のうちの、左上の正方形 の 一番左の列 の ビットが 1 であるビット列 $\boldsymbol{M_1}$ を計算 する（左上図の黄色の範囲）
2. $\boldsymbol{M_1}$ を利用 して、左上の正方形の範囲 の ビットが 1 であるビット列 $\boldsymbol{M_2}$ を計算 する（右上図の黄色の範囲）
3. $\boldsymbol{M_2}$ を利用 して、左端の一列の正方形の範囲 の ビットが 1 であるビット列 $\boldsymbol{M_3}$ を計算 する（左下図の黄色の範囲）
4. $\boldsymbol{M_3}$ を利用 して、全ての正方形の範囲 の ビットが 1 である ビットマスク $\boldsymbol{m_i}$ を計算 する（右下図の黄色の範囲）

それぞれの計算方法を説明します。

左上の正方形の左の列の範囲が 1 となるビット列の計算方法

下図は $\boldsymbol{n_i = 4}$ の場合の $\boldsymbol{M_1}$ の図で、マスの中の値 はそのマスに対応する ビットの値 を表します。$\boldsymbol{M_1}$ の ビットの番号 は 左上のマスを 0 として 下方向に 1 ずつ増える ので、$\boldsymbol{M_1}$ は 0 番から 0 が $\boldsymbol{n_i}$ 個続き、その後に 1 が $\boldsymbol{n_i}$ 個続く ビット列であることがわかります。

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

1. (1 << $\boldsymbol{n_i}$) - 1 によって 0 番から $\boldsymbol{n_i}$ 個の 1 が並ぶビット列を計算 する
2. 上記で計算したビット列を $\boldsymbol{n_i}$ ビット左シフト した 値を計算 する

従って $\boldsymbol{M_1}$ は下記の式で計算 できます。

$\boldsymbol{M_1}$ = (1 << $\boldsymbol{n_i}$) - 1) << $\boldsymbol{n_i}$

下記は $\boldsymbol{n_i = 4}$ の場合の 上図のビット列 $\boldsymbol{M_1}$ を計算 するプログラムです。正しい計算が行われることを確認するために、先程作成した 8 x 8 のサイズ のゲーム盤を表す mb8 を ゲーム開始時の局面に戻した後 で 〇 のビットボード に $\boldsymbol{M_1}$ を代入してゲーム盤を表示 することで、1 のビットのマスに 〇 が配置されたゲーム盤を表示 しました。実行結果から 正しい値が計算されることが確認 できます。

• 1 ~ 3 行目：上記の式で $M_1$ を計算し、その値を表示する
• 4 ~ 6 行目：mb8 の restart メソッドを呼び出してゲーム開始時の局面にした後で 〇 のビットボードに M1 を代入してゲーム盤を表示することで、M1 の 1 のビットに対応するマスに 〇 が配置されたゲーム盤が表示される

1  ni = 4
2  M1 = ((1 << ni) - 1) << ni
3  print(f"0b{M1:b}")
4  mb8.restart()
5  mb8.board.board[0] = M1
6  print(mb8)

行番号のないプログラム

ni = 4
M1 = ((1 << ni) - 1) << ni
print(f"0b{M1:08b}")
mb8.restart()
mb8.board.board[0] = M1
print(mb8)

実行結果

0b11110000
Turn o
........
........
........
........
o.......
o.......
o.......
o.......

左上の正方形の範囲が 1 となるビット列の計算方法

左上の正方形の範囲が 1 となる $\boldsymbol{M_2}$ は下記のアルゴリズムで計算することができます。

1. $\boldsymbol{M_2 = M_1}$ とし、このアルゴリズムによって $M_2$ に計算された ビットが 1 の列の幅（width）を表す $\boldsymbol{w}$ を 1 とする
2. $\boldsymbol{w}$ が 正方形の列の幅 である $\boldsymbol{n_i}$ になるまで 下記の計算を行う
   1. $\boldsymbol{M_2}$ を $\boldsymbol{w}$ 列分右にずらしたビット列を計算 して $\boldsymbol{M_2}$ との OR 演算 を計算することで、$\boldsymbol{w}$ 列分 の 1 のビットが その右に $\boldsymbol{w}$ 列分コピー されて、$\boldsymbol{w\ ×\ 2}$ 列分のビットが 1 となる $\boldsymbol{M_2}$ が計算 される
   2. ビットが 1 の列の幅が 2 倍になったので $\boldsymbol{w}$ を 2 倍 する

下図は上記の 1 回目の繰り返し処理の結果を表す図 です。上記の 手順 1 では先程計算した 黄色の部分のビットが 1 となる $\boldsymbol{M_1}$ を $\boldsymbol{M_2}$ に代入 します。また、黄色の部分の列の幅は 1 なので $\boldsymbol{w = 1}$ とします。

$\boldsymbol{w = 1 < n_i = 4}$ なので 手順 2 の計算 を行います。手順 2-1 では、黄色のビット列 を $\boldsymbol{w = 1}$ 列分右にずらした、青色の部分が 1 となるビット列を計算 します。1 列右のビットの番号 はゲーム盤の行の数を表す $\boldsymbol{n}$ だけ増える ので、青色の部分が 1 となるビット列 は $\boldsymbol{M_2 << (w\ ×\ n)}$ という 左シフト演算で計算 することができます。従って、手順 2-1 で行う計算式 は下記のようになり、$\boldsymbol{M_2}$ には上図の 黄色と青色の 2 列分が 1 となった ビット列が計算 されます。手順 2-2 で $\boldsymbol{w}$ を 2 倍して 2 にします。

$\boldsymbol{M_2 = M_2\ |\ (M_2 << (w\ ×\ n))}$

下図は上記の 2 回目の繰り返し処理の結果を表す図 です。$\boldsymbol{w = 2 < n_i = 4}$ なので 手順 2 の計算 を行います。

手順 2-1 では、黄色のビット列 を $\boldsymbol{w = 2}$ 列分右にずらした、青色の部分が 1 となるビット列を計算 します。先ほどと同様の理由から $\boldsymbol{w}$ 列右のビットの番号 は $\boldsymbol{w\ ×\ n}$ 増える ので、青色の部分が 1 となるビット列 は 先ほどと同じ $\boldsymbol{M_2 << (w\ ×\ n)}$ という 左シフト演算で計算 することができ、$\boldsymbol{M_2}$ には上図の 黄色と青色の 4 列分が 1 となった ビット列が計算 されます。これは、3 回目以降 の手順 2 の繰り返し処理の場合でも 同様 なので、手順 2-1 は常に下記の式で計算できる ことがわかります。

$\boldsymbol{M_2 = M_2\ |\ (M_2 << n)}$

手順 2-2 で $\boldsymbol{w}$ を 2 倍 した結果 $\boldsymbol{w = 4 = n_i}$ になる ので 処理は終了 し、上図のように 左上の正方形の範囲が 1 となるビット列が $\boldsymbol{M_2}$ に計算されます。

下記は先ほどのプログラムで計算した $\boldsymbol{M_1}$ に対して 上記のアルゴリズムで $\boldsymbol{M_2}$ を計算 するプログラムです。実行結果から 正しい値が計算されることが確認 できます。

• 1 行目：$n$ が必要になるのでゲーム盤のサイズを表す 8 を代入した
• 2 ~ 6 行目：上記で説明したアルゴリズムで $M_2$ を計算する

1  n = 8
2  M2 = M1
3  w = 1
4  while w < ni:
5      M2 |= M2 << (w * n)
6      w *= 2
7  print(f"0b{M2:b}")
8  mb8.board.board[0] = M2
9  print(mb8)

行番号のないプログラム

n = 8
M2 = M1
w = 1
while w < ni:
    M2 |= M2 << (w * n)
    w *= 2
print(f"0b{M2:b}")
mb8.board.board[0] = M2
print(mb8)

実行結果

0b11110000111100001111000011110000
Turn o
........
........
........
........
oooo....
oooo....
oooo....
oooo....

このアルゴリズムでは、手順 2 の処理を行うたび に $\boldsymbol{M_2}$ に計算される 1 のビットの列の幅が 2 倍 になります。また、$\boldsymbol{n_i}$ は 2 のべき乗 なので、手順 2 の処理を何度か行う と 必ず 1 のビットの列の幅が $\boldsymbol{n_i}$ となる $\boldsymbol{M_2}$ が計算されます。

左端の一列の正方形の範囲が 1 となるビット列の計算方法

左端の一列の正方形の範囲が 1 となる $\boldsymbol{M_3}$ は、$\boldsymbol{M_2}$ を計算するアルゴリズムと 同じ考え方 の下記のアルゴリズムで計算することができます。

1. $\boldsymbol{M_3 = M_2}$ とし、$M_3$ に計算された ビット列の行の高さ（height）を表す $\boldsymbol{h}$ を $\boldsymbol{n_{i-1}}$ とする。なお、$\boldsymbol{M_1}$ に計算したビット列 は $\boldsymbol{n_i}$ 個の 0 と $\boldsymbol{n_i}$ 個の 1 が並んだ ビット列なので、$\boldsymbol{M_3}$ に計算された ビット列の高さ は $n_i$ ではなく $\boldsymbol{n_{i-1}}$ とする必要がある
2. $\boldsymbol{h}$ が ゲーム盤の高さ である $\boldsymbol{n}$ になるまで 下記の計算を行う
   1. $\boldsymbol{M_3}$ を $\boldsymbol{h}$ 行分下にずらしたビット列を計算 して $\boldsymbol{M_3}$ との OR 演算 を計算することで、0 行から $\boldsymbol{h}$ 行分 の $M_3$ のビットが その下に $\boldsymbol{h}$ 行分コピー されて、$\boldsymbol{h\ ×\ 2}$ 行分のビット列 が $\boldsymbol{M_3}$ に計算 される
   2. 計算したビット列の行の高さが 2 倍になったので $\boldsymbol{h}$ を 2 倍 する

下図は上記の 1 回目の繰り返し処理の結果を表す図 です。上記の 手順 1 では先程計算した 黄色の部分のビットが 1 となる $\boldsymbol{M_2}$ を $\boldsymbol{M_3}$ に代入 します。また、$\boldsymbol{h = n_{i-1}}$ とします。

手順 2-1 では、黄色のビット列 を $\boldsymbol{h}$ 行分下にずらした、青色の部分が 1 となるビット列を計算 します。1 行下のビットの番号 は 1 増える ので、青色の部分が 1 となるビット列 は $\boldsymbol{M_3 << h}$ という 左シフト演算で計算 することができます。従って、手順 2-1 で行う計算式 は下記のようになり、$\boldsymbol{M_3}$ には上図の 黄色と青色の範囲が 1 となった ビット列が計算 されます。

$\boldsymbol{M_3 = M_3\ |\ (M_3 << h)}$

先程と同様の理由から、上記の 手順 2 の処理を行うたび に 2 倍の数 の 正方形が縦に並ぶの範囲が 1 となる ビット列が計算 されます。また、左端の一列の正方形の数 は、ビットボードを 2 つに分割するたびに 2 倍 になるので その個数は 2 のべき乗 になります。従って、先程と同様の理由から 手順 2 の処理を何度か行う と必ず 左端の一列の正方形の範囲が 1 となる $\boldsymbol{M_3}$ が計算されます。

下記は上記のアルゴリズムで $\boldsymbol{M_3}$ を計算 するプログラムです。$n_i = 4$ の場合は左端の一列の正方形の数が 1 になってしまうので、下記では $\boldsymbol{n_i = 2}$ として 左端の一列の正方形の数が 2 になる ようにし、$\boldsymbol{M_1}$ と $\boldsymbol{M_2}$ を計算しなおしてから $\boldsymbol{M_3}$ の計算 を行いました。なお、$n_i = \frac{n_{i-1}}{2}$ から $\boldsymbol{n_{i-1} = n_{i}\ ×\ 2}$ で計算できるので、$\boldsymbol{h}$ は h = ni * 2 で計算 しました。実行結果から正しい計算が行われることが確認できます。

n = 8
ni = 2

M1 = ((1 << ni) - 1) << ni
print(f"0b{M1:b}")
mb8.restart()
mb8.board.board[0] = M1
print("M1")
print(mb8)

M2 = M1
w = 1
while w < ni:
    M2 |= M2 << (w * n)
    w *= 2
print(f"0b{M2:b}")
mb8.board.board[0] = M2
print("M2")
print(mb8)

M3 = M2
h = ni * 2
while h < n:
    M3 |= M3 << h
    h *= 2
print(f"0b{M3:b}")
mb8.board.board[0] = M3
print("M3")
print(mb8)

実行結果

0b1100
M1
Turn o
........
........
o.......
o.......
........
........
........
........

0b110000001100
M2
Turn o
........
........
oo......
oo......
........
........
........
........

0b1100110011001100
M3
Turn o
........
........
oo......
oo......
........
........
oo......
oo......

ビットマスクの計算方法

最終的に求めたい ビットマスク である $\boldsymbol{m_i}$ も　上記と同じ考え方 の下記のアルゴリズムで計算することができます。

1. $\boldsymbol{m_i = M_3}$ とし、$m_i$ に計算された ビット列の幅（width）を表す $\boldsymbol{w}$ を $\boldsymbol{n_{i-1}}$ とする
2. $\boldsymbol{w}$ が ゲーム盤の幅 である $\boldsymbol{n}$ になるまで 下記の計算を行う
   1. $\boldsymbol{m_i}$ を $\boldsymbol{w}$ 列分右にずらしたビット列を計算 して $\boldsymbol{m_i}$ との OR 演算 を計算することで、0 列から $\boldsymbol{w}$ 列分 の $m_i$ のビットが その右に $\boldsymbol{w}$ 列分コピー されて、$\boldsymbol{w\ ×\ 2}$ 列分のビット列 が $\boldsymbol{m_i}$ に計算 される
   2. 計算したビット列の幅が 2 倍になったので $\boldsymbol{w}$ を 2 倍 する

下図は上記の 1 回目の繰り返し処理の結果を表す図 です。上記の 手順 1 では先程計算した 黄色の部分のビットが 1 となる $\boldsymbol{M_3}$ を $\boldsymbol{m_i}$ に代入 します。また、$\boldsymbol{w = n_{i-1}}$ とします。

手順 2-1 では、黄色のビット列 を $\boldsymbol{w}$ 列右にずらした、青色の部分が 1 となるビット列を計算 します。1 行右のビットの番号 は $\boldsymbol{n}$ 増える ので、青色の部分が 1 となるビット列 は $\boldsymbol{m_i << (w\ ×\ n)}$ という 左シフト演算で計算 することができます。従って、手順 2-1 で行う計算式 は下記のようになり、$\boldsymbol{m_i}$ には上図の 黄色と青色の範囲が 1 となった ビット列が計算 されます。

$\boldsymbol{m_i = M_3\ |\ (M_3 << (w\ ×\ n))}$

先程と同様なので説明は省略しますが、上記の 手順 2 の処理を繰り返し行う ことによって、求めたいビットマスク である $\boldsymbol{m_i}$ が計算 されます。

下記は 上記のアルゴリズム で先程計算した $\boldsymbol{M_3}$ から $\boldsymbol{m_i}$ を計算 するプログラムです。実行結果から下図の緑色のビットが 1 となる 正しい計算が行われることが確認 できます。

Mi = M3
w = ni * 2
while w < n:
    Mi |= Mi << (w * n)
    w *= 2
print(f"0b{Mi:b}")
mb8.board.board[0] = Mi
print("Mi")
print(mb8)

実行結果

0b110011001100110000000000000000001100110011001100
Mi
Turn o
........
........
oo..oo..
oo..oo..
........
........
oo..oo..
oo..oo..

__init__ メソッドの修正

先程と同様に 分割統治法（divide and conquer method） を利用したアルゴリズムで 必要となる delta とビットマスク を計算した 参照テーブル を __init__ メソッドで計算 して transpose_dc_table という属性に代入することします。

下記はそのように __init__ メソッドを修正したプログラムです。先程のアルゴリズムではわかりやすさを重視して ビットマスクを $M_1$、$M_2$、$M_3$ という異なる変数に代入しながら計算しましたが、変数を分ける必要はないので下記では mask という変数だけで計算 を行いました。行う処理は先ほど説明したアルゴリズムの通りのままなので説明は省略します。

 1  from marubatsu import BitBoard
 2  
 3  def __init__(self, board_size:int=3, count_linemark:bool=False):
 4      self.BOARD_SIZE = board_size
 5      self.bit_length = self.BOARD_SIZE ** 2
 6      self.count_linemark = count_linemark
 7  
 8      # 参照テーブルの計算
元と同じなので省略           
 9      self.transpose_dc_table = []
10      n = self.BOARD_SIZE
11      ni = n
12      while ni > 1:
13          ni //= 2
14          delta = (n - 1) * ni
15          # M1 を計算する
16          mask = ((1 << ni) - 1) << ni
17          # M2 を計算する
18          w = 1
19          while w < ni:
20              mask |= mask << (w * n)
21              w *= 2
22          # M3 を計算する
23          h = ni * 2
24          while h < n:
25              mask |= mask << h
26              h *= 2
27          # mi を計算する
28          w = ni * 2
29          while w < n:
30              mask |= mask << (w * n)
31              w *= 2
32          self.transpose_dc_table.append((delta, mask))
33  
34      self.initialize()    
35  
36  BitBoard.__init__ = __init__

行番号のないプログラム

from marubatsu import BitBoard

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.transpose_ds_table = []
    for i in range(1, self.BOARD_SIZE):
        mask = 0
        for j in range(self.BOARD_SIZE - i):
            mask |= self.xy_to_move(j, i + j)
        self.transpose_ds_table.append(((self.BOARD_SIZE - 1) * i, mask))
            
    self.transpose_dc_table = []
    n = self.BOARD_SIZE
    ni = n
    while ni > 1:
        ni //= 2
        delta = (n - 1) * ni
        # M1 を計算する
        mask = ((1 << ni) - 1) << ni
        # M2 を計算する
        w = 1
        while w < ni:
            mask |= mask << (w * n)
            w *= 2
        # M3 を計算する
        h = ni * 2
        while h < n:
            mask |= mask << h
            h *= 2
        # mi を計算する
        w = ni * 2
        while w < n:
            mask |= mask << (w * n)
            w *= 2
        self.transpose_dc_table.append((delta, mask))
            
    self.initialize()    
    
BitBoard.__init__ = __init__

transpose_dc メソッドの修正

下記は 分割統治法 を利用したアルゴリズムで ビットボードの転置処理 を行う transpose_dc メソッドの定義です。行う処理は参照テーブルから delta とビットマスクを取り出して delta swap を行うだけなので説明は省略します。

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

BitBoard.transpose_dc = transpose_dc

下記は 対角線を含む左下半分の範囲のマス に 順番にマークを配置 した 8 x 8 のサイズ のビットマップに対して transpose_dc で 2 回ビットボードの転置処理を行うプログラムです。実行結果から 正しい処理が行われることが確認 できます。

mb8 = Marubatsu(boardclass=BitBoard, board_size=8)
for x in range(8):
    for y in range(x, 8):
        mb8.cmove(x, y)
print(mb8)
mb8.board.transpose_dc()
print(mb8)
mb8.board.transpose_dc()
print(mb8)

実行結果

Turn o
o.......
xo......
oxx.....
xoox....
oxxoo...
xooxxo..
oxxooxx.
xooxxooX

Turn o
oxoxoxox
.oxoxoxo
..xoxoxo
...xoxox
....oxox
.....oxo
......xo
.......X

Turn o
o.......
xo......
oxx.....
xoox....
oxxoo...
xooxxo..
oxxooxx.
xooxxooX

処理時間の検証

下記は ゲーム盤のサイズ が 4, 8, 16, 32, 64, 128 のそれぞれの場合の transpose_ds と transpose_dc の 処理時間を計測 するプログラムです。先ほどと同様に左下半分に着手を行ったビットボードの転置を行いました。ゲーム盤のサイズを 2 のべき乗としたのは transpose_dc は 2 のべき乗のサイズのゲーム盤しか転置できないからです。

for board_size in [4, 8, 16, 32, 64, 128, 256]:
    mb = Marubatsu(boardclass=BitBoard, board_size=board_size)
    print(f"board_size = {board_size}")
    for x in range(board_size):
        for y in range(x, board_size):
            mb.cmove(x, y)
    %timeit mb.board.transpose_ds()
    %timeit mb.board.transpose_dc()

実行結果

board_size = 4
1.6 μs ± 13.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.12 μs ± 39.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
board_size = 8
4.62 μs ± 45.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.01 μs ± 35 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
board_size = 16
10.5 μs ± 56.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.93 μs ± 57.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
board_size = 32
27.9 μs ± 266 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
4.36 μs ± 11.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
board_size = 64
106 μs ± 399 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
11.9 μs ± 16 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
board_size = 128
416 μs ± 1.66 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
30.3 μs ± 83.1 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
board_size = 256
2.46 ms ± 8.16 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
109 μs ± 249 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

下記は上記の実行結果をまとめた表です。表の処理時間の数値の単位は μs で小数点以下第 2 桁で四捨五入しました。表から 分割統治法 を利用した transpose_dc のほうが 処理速度が常に速い ことが確認できました。また、ゲーム盤の サイズが大きくなるほど その 差が大きくなる ことも確認できます。

サイズ	transpose_ds	transpose_dc
4	1.6	1.1
8	4.6	2.0
16	10.5	2.9
32	27.9	4.4
64	106.0	11.9
128	416.0	30.3
256	2,460.0	109.0

今回の記事のまとめ

今回の記事では ビットボードの転置処理 のアルゴリズムとして 分割統治法を利用しない ものと 利用するもの を紹介し、分割統治法を利用したほうが高速 であることを示しました。

ただし、今回の記事で紹介した分割統治法を利用したアルゴリズム は ゲーム盤のサイズが 2 のべき乗である必要がある という制限があるので、次回の記事では その制限を無くす方法 について紹介し、BitBoard クラスの実装を完了する予定です。

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

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

次回の記事

1. 厳密には、計算量はアルゴリズムの処理に必要な時間と空間の 2 種類があり、空間とはアルゴリズムが必要とするコンピューターのメモリなどの記憶の容量を表します。本記事では時間の計算量を表す時間計算量の意味で計算量という用語を用いています ↩

2. Python の int 型のデータの加算や AND などの演算の計算量は、おそらくビット長を $n$ とした場合は $O(n)$ だと思います ↩

3. 図のマスの番号は転置処理を行う前のビットの番号を表すので、図の番号を引き算して間隔を計算するという方法は（計算結果は偶然正しくなりますが）間違っている点に注意して下さい ↩