目次と前回の記事
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 クラスの __init__ メソッドで 1 回だけ行う ので、処理速度はそれほど重要ではありません。前回の記事で紹介したアルゴリズムでも処理速度は充分速い のではないかと思いますので、わかりづらいと思った方は無理にこのアルゴリズムを利用する必要はないと思います。
アルゴリズムの考え方
下図は前回の記事で説明したビットボードの転置処理のアルゴリズムの中の、i 回目の手順 3 のビットマスク $\boldsymbol{m_i}$ を表す図で、$\boldsymbol{m_i}$ は図の 緑の部分のビットが 1 となるビット列 です
前回の記事 では 下記の手順 で $\boldsymbol{m_i}$ を計算 するアルゴリズムを紹介しました。また、下記の 手順 2、3、4 では 繰り返し処理 によって計算を行いました。
- 複数の正方形の範囲のうちの、左上の正方形 の 一番左の列 の ビットが
1であるビット列 $\boldsymbol{M_1}$ を計算 する（左上図の黄色の範囲） - $\boldsymbol{M_1}$ を利用 して、左上の正方形の範囲 の ビットが
1であるビット列 $\boldsymbol{M_2}$ を計算 する（右上図の黄色の範囲） - $\boldsymbol{M_2}$ を利用 して、左端の一列の正方形の範囲 の ビットが
1であるビット列 $\boldsymbol{M_3}$ を計算 する（左下図の黄色の範囲） - $\boldsymbol{M_3}$ を利用 して、全ての正方形の範囲 の ビットが
1である ビットマスク $\boldsymbol{m_i}$ を計算 する（右下図の黄色の範囲）
一方、今回紹介するアルゴリズム は下記の手順で $\boldsymbol{m_i}$ を計算します。また、その際に 繰り返し処理を行わない ことによって上記のアルゴリズムよりも 処理速度が速くなります。
- $\boldsymbol{M_1}$ を計算 する
- $\boldsymbol{M_1}$ を利用 して $M_3$ を計算する
- $\boldsymbol{M_3}$ を利用 して $m_i$ を計算する
手順 1 の計算方法
手順 1 の $\boldsymbol{M_1}$ は 前回の記事と同様 に、下記の計算式で 0 番のビットから $\boldsymbol{n_i}$ 個の 0 が、その後に $\boldsymbol{n_i}$ 個の 1 が並ぶ ビット列 $\boldsymbol{M_1}$ を計算します。
$\boldsymbol{M_1}$ = (1 << $\boldsymbol{n_i}$) - 1) << $\boldsymbol{n_i}$
手順 2 の計算方法
下図は $\boldsymbol{n_i = 4}$ の場合の ビットマスク を表す図で、黄色の範囲 が $\boldsymbol{M_1}$ を表します。
上図から $\boldsymbol{M_1}$ のすぐ下の青色の部分 の $\boldsymbol{n_{i-1}}$ 個のビットの並び は $\boldsymbol{M_1}$ と全く同じ であることがわかります。その下のビット列の並びも同様 なので、上図のビットマスクの 一番左端の列のビットの並び は、$\boldsymbol{M_1}$ が $\boldsymbol{\frac{n}{n_{i-i}}}$ 回繰り返されて並んだ ビット列になります。
また、上図から 左端から $\boldsymbol{n_{i}}$ 列 の 各列のビットの並びはすべて同じ であることがわかります。$\boldsymbol{n_i = \frac{n_{i-1}}{2}}$ から、上図のビットボードの 0 列から $\boldsymbol{n_i}$ 列分 の ビットの並び は $\boldsymbol{M_1}$ が $\frac{n}{n_{i-i}} × n_i = \boldsymbol{\frac{n}{2}}$ 回繰り返されて並んだ ビット列になります。
また、その ビット列 は下図の 黄色の範囲のビットが 1 となる $\boldsymbol{M_3}$ になります。
なお、ビット列を繰り返した値を計算 する際は ビット長を指定する必要 があります。例えば 0b10 というビット列を 3 回繰り返した値 は、ビット長が異なると 下記のように 異なる値が計算されるから です。
-
ビット長を 2 とした場合は
0b101010となる -
ビット長を 3 とした場合は
0b010を繰り返す ので0b010010010となる
表記が長くなるので、ビット長が $\boldsymbol{l}$ の ビット列 $\boldsymbol{b}$ を $\boldsymbol{n}$ 回繰り返し（repeat）た値を 計算する関数 を以後は $\boldsymbol{R(b, l, n)}$ と表記することにします。
上記から $\boldsymbol{M_3}$ は 下記の式で計算される ことがわかりました。
$\boldsymbol{M_3 = R(M_1, n_{i-1}, \frac{n}{2})}$
手順 3 の計算方法
下図は先ほどの図の再掲です。
上図から $\boldsymbol{m_i}$ は 左端から $\boldsymbol{n_{i-1}}$ 列分 のビットの並びを $\boldsymbol{\frac{n}{n_{i-1}}}$ 回繰り返したビット列 であることがわかります。また、図の白色の範囲のビットの値はすべて 0 なので、左端から $\boldsymbol{n_{i-1}}$ 列分 の ビットの値 は $\boldsymbol{M_3}$ と等しく なります。左端から $\boldsymbol{n_{i-1}}$ 列分 の ビットの数 は $\boldsymbol{n\ ×\ n_{i-1}}$ なので、$\boldsymbol{m_i}$ は 下記の式で計算 することができます。
$\boldsymbol{m_i = R(M_3, n\ ×\ n_{i-1}, \frac{n}{n_{n-i}})}$
上記から $\boldsymbol{m_i}$ を計算する式 は以下のようになります。従って、任意の $\boldsymbol{b}$、$\boldsymbol{l}$、$\boldsymbol{n}$ に対して $\boldsymbol{R(b, l, n)}$ を計算する方法 がわかれば $\boldsymbol{m_i}$ を計算できる ことがわかりました。
$\boldsymbol{M_1}$ = (1 << $\boldsymbol{n_i}$) - 1) << $\boldsymbol{n_i}$
$\boldsymbol{M_3 = R(M_1, n_{i-1}, \frac{n}{2})}$
$\boldsymbol{m_i = R(M_3, n\ ×\ n_{i-1}, \frac{n}{n_{n-i}})}$
ビット列を繰り返した値の計算方法
$\boldsymbol{R(b, l, n)}$ を計算するアルゴリズム をいくつか紹介します。また、以下ではそれぞれのアルゴリズムで ビット列（bit sequence） を 繰り返し（repeat）た値 である $\boldsymbol{R(b, l, n)}$ を計算 する repeat_bit_sequencex という関数を定義 することにします。ただし、関数名の最後の x には 1 からはじまる整数を順番につける ことにします。
繰り返し処理で計算を行うアルゴリズム
具体例として b = 0b11001、l = 5、n = 5 の場合で説明します。この場合は 0b11001 が 5 回繰り返された 下記のビット列が計算されます。
0b1100111001110011100111001
上記のビット列 を b の繰り返されたビットごとに分ける と以下のようになります。また、下記のビット列 に対して OR 演算を行う ことで $\boldsymbol{R(b, l, n)}$ を計算 することができます。
1 回目の繰り返し 0b0000000000000000000011001 = b << (5 * 0) = b
2 回目の繰り返し 0b0000000000000001100100000 = b << (5 * 1)
3 回目の繰り返し 0b0000000000110010000000000 = b << (5 * 2)
4 回目の繰り返し 0b0000011001000000000000000 = b << (5 * 3)
5 回目の繰り返し 0b1100100000000000000000000 = b << (5 * 4)
上記の 最初のビット列は b で、2 つ目以降のビット列 は b を l = 5 ビットずつ左シフトした値 になるので、repeat_bit_sequence1 は 繰り返し処理 を利用した下記のプログラムで定義することができます。
- 2 行目：計算結果を計算する変数を 0 で初期化する
-
3 ~ 5 行目：
n回の繰り返し処理 を行う -
4 行目：
resultとbの OR 演算 を行うことで、resultにi回目1のbの値を計算 する -
5 行目：
bをlビット左シフト演算 することで 次のbの繰り返しの値を計算 する -
6 行目：
resultを返り値として返す
1 def repeat_bit_sequence1(b, l, n):
2 result = 0
3 for i in range(n):
4 result |= b
5 b <<= l
6 return result
行番号のないプログラム
def repeat_bit_sequence1(b, l, n):
result = 0
for i in range(n):
result |= b
b <<= l
return result
下記は repeat_bit_sequence1 で b = 0b11001、l = 5、n = 5 の場合の計算 を行うプログラムで、実行結果から 正しい値が計算されることが確認 できました。
print(bin(repeat_bit_sequence1(b=0b11001, l=5, n=5)))
実行結果
0b1100111001110011100111001
str 型に変換するアルゴリズム
以前の記事で ビット列の反転処理 を行う際に 紹介したアルゴリズムと同様 に、下記の手順で b を str 型のデータに変換 し、* 演算子 で変換された文字列を l 回繰り返した値を計算 した後で int 型のデータに戻す というアルゴリズムがあります。
-
f"{b:0{l}b}"でbを 先頭を0で埋めたl文字 の 2 進数を表す str 型に変換 する -
*演算子 で上記で計算した str 型のデータをn回繰り返した 文字列を計算する -
組み込み関数
intで上記で計算した str 型のデータを int 型のデータに変換 する
下記は上記の計算を行う repeat_bit_sequence2 の定義です。
def repeat_bit_sequence2(b, l, n):
return int(f"{b:0{l}b}" * n, 2)
下記は repeat_bit_sequence2 で b = 0b11001、l = 5、n = 5 の場合の計算 を行うプログラムで、実行結果から 正しい値が計算されることが確認 できました。
print(bin(repeat_bit_sequence2(b=0b11001, l=5, n=5)))
実行結果
0b1100111001110011100111001
等比数列の和の公式を利用したアルゴリズム
等比数列の和の公式 を利用することで、$\boldsymbol{R(b, l, n)}$ を 繰り返し処理を利用せず に 1 つの式で計算することができる のでその方法について紹介します。
数列 とは 数字を並べたもの のことで、等比数列 とは 1、2、4、8、16・・・ のように数列の 次の数値が特定の値の倍数 になる数列のことを表します。
等比数列 は 数列の最初の値 を $\boldsymbol{a}$（ただし $a ≠ 0$)、倍率 を $\boldsymbol{r}$（ただし $r ≠ 0$) とすると、$\boldsymbol{a}$ × $\boldsymbol{r^0}$、$\boldsymbol{a}$ × $\boldsymbol{r^1}$、$\boldsymbol{a}$ × $\boldsymbol{r^2}$、$\boldsymbol{a}$ × $\boldsymbol{r^3}$・・・のように表記されます。
等比数列の和の公式 とは、$\boldsymbol{r ≠ 1}$ の場合2に上記の 等比数列の先頭から n 個の和 が 下記の式で計算される ことを表す公式です。
$\boldsymbol{\sum_{i=0}^{n-1}{a\ ×\ r^i} = a\ ×\ \frac{1 - r^n}{1 - r}}$
この公式が成り立つ理由については下記の wikipedia の記事を参照して下さい。
次に $\boldsymbol{R(b, l, n)}$ が 等比数列の公式で計算できる ことを示します。
最初に紹介した 繰り返し処理で計算を行うアルゴリズム の例で 行われる計算 を 一つの式で表す と下記の式のようになります。
$b$ | ($b$ << $l$) | ($b$ << ($l$ × 2)) | ($b$ << ($l$ × 3)) | ($b$ << ($l$ × 4))
また、$\boldsymbol{b}$ = ( $\boldsymbol{b}$ << ( $\boldsymbol{l}$ × 0))、 $\boldsymbol{b}$ << $\boldsymbol{l}$ = ( $\boldsymbol{b}$ << ( $\boldsymbol{l}$ × 1)) が成り立つ ので、上記の式は下記のようになります。
($b$ << ($l$ × 0)) | ($b$ << ($l$ × 1)) | ($b$ << ($l$ × 2)) | ($b$ << ($l$ × 3)) | ($b$ << ($l$ × 4))
上記の OR 演算 で計算する それぞれのビット列 は、$\boldsymbol{b}$ をビットの値が重ならないようにずらしたもの なので、OR 演算を行う際 に 同じ番号の複数のビットが 1 になることはありません。繰上りが起きない場合の加算 と OR 演算 は 同じ値が計算される ので、そのような場合は OR 演算を加算に変更 しても 同じ値が計算 されます。従って 下記の式 で 上記の式と同じ値が計算 されます。
($b$ << ($l$ × 0)) + ($b$ << ($l$ × 1)) + ($b$ << ($l$ × 2)) + ($b$ << ($l$ × 3)) + ($b$ << ($l$ × 4))
ビット列に対する 1 ビットの左シフト演算 は 値を 2 倍 するという計算が行われます3。従って $\boldsymbol{x}$ ビットの左シフト演算 は 値を $\boldsymbol{2^x}$ 倍 するため、$\boldsymbol{b}$ << $\boldsymbol{x}$ = $\boldsymbol{b}$ × $\boldsymbol{2^x}$ という式で置き換える ことができるので、$\boldsymbol{n=5}$ とすると 上記の式は下記のようになります。
$b$ × $2^{l × 0}$ + $b$ × $2^{l × 1}$ + $b$ × $2^{l × 2}$ + $b$ × $2^{l × 3}$ + $b$ × $2^{l × 4}$
$= \boldsymbol{b}\ ×\ \boldsymbol{\sum_{i=0}^{n-1}2^{l\ ×\ i}}$
$\boldsymbol{l}$ が正の整数 の場合は $\boldsymbol{2^{l × 2} = 2^{l + l} = 2^l × 2^l = 2^{l^2}}$ となります。同様の理由 から $\boldsymbol{i}$ が 0 以上の整数 の場合は $\boldsymbol{2^{l × i} = 2^{l^i}}$ となるので 上記の式は下記のようになります。
$\boldsymbol{b\ ×\ \sum_{i=0}^{n-1}2^{l^i}}$
$\boldsymbol{2^l}$ は定数 なので、式をわかりやすくするために $\boldsymbol{r = 2^l}$ とする と 上記の式は下記のようになります。
$\boldsymbol{b\ ×\ \sum_{i=0}^{n-1}r^i}$
これは先ほど説明した 等比数列の和を計算 しており、ビット長を表す $\boldsymbol{l}$ は $\boldsymbol{l > 0}$ なので $\boldsymbol{r = 2^l> 1}$ となり $\boldsymbol{r ≠ 1}$ という 等比級数の公式を利用する際の条件 を満たします。従って、等比数列の和の公式 から 上記の式は下記の式で計算できます。
$\boldsymbol{b\ ×\ \frac{1 - r^n}{1 - r}}$
下記は 上記の式で計算を行う repeat_bit_sequence3 の定義です。ビットマスクは int 型 のデータなので、int 型の値を計算するため に / ではなく 商を計算する // 演算子を利用する必要がある 点に注意して下さい。
def repeat_bit_sequence3(b, l, n):
r = 1 << l
return b * ((1 - (r ** n)) // (1 - r))
下記は repeat_bit_sequence3 で b = 0b11001、l = 5、n = 5 の場合の計算 を行うプログラムで、実行結果から 正しい値が計算されることが確認 できました。
print(bin(repeat_bit_sequence3(b=0b11001, l=5, n=5)))
実行結果
0b1100111001110011100111001
処理時間の比較
下記のプログラムで、b = 0b11001、l = 5 に対して n を 10、100、1,000、10,000, 100,000 とした場合の repeat_bit_sequence1、repeat_bit_sequence2、repeat_bit_sequence3 の それぞれの処理時間を計測 します。
for n in [10, 100, 1000, 10000, 100000]:
print(f"n = {n}")
%timeit repeat_bit_sequence1(b=0b11001, l=5, n=n)
%timeit repeat_bit_sequence2(b=0b11001, l=5, n=n)
%timeit repeat_bit_sequence3(b=0b11001, l=5, n=n)
実行結果
n = 10
1.03 μs ± 13.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
674 ns ± 9.33 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
345 ns ± 1.89 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
n = 100
10.5 μs ± 71.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
1.5 μs ± 2.41 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
737 ns ± 3.74 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
n = 1000
231 μs ± 9.9 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
9.54 μs ± 34.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
6.99 μs ± 68.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
n = 10000
10.9 ms ± 21.7 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
81.2 μs ± 117 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
105 μs ± 250 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
n = 100000
955 ms ± 4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
811 μs ± 10.3 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
1.38 ms ± 2.15 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
下記は 上記の実行結果をまとめた表 です。関数名が長いので rbs1 のように略し ました。
n |
rbs1 |
rbs2 |
rbs3 |
|---|---|---|---|
| 10 | 1.0 | 0.7 | 0.3 |
| 100 | 10.5 | 1.5 | 0.7 |
| 1,000 | 231.0 | 9.5 | 7.0 |
| 10,000 | 10,900.0 | 81.2 | 105.0 |
| 100,000 | 955,000 | 811.0 | 1,380.0 |
上記の表から 繰り返しの回数が 1000 以下 の場合は repeat_bit_sequence3 が最速 ですが、それを超えるとrepeat_bit_sequence2 が最速 になることがわかりました。そのような結果になる原因の詳細は不明ですが、先程説明したように ビットマスクの計算は __init__ メソッド内で 1 回だけ行う処理 なので、どちらを利用しても大きな違いは無い のではないかと思います。
また、繰り返し処理で計算 する repeat_bit_sequence1 は常に最も遅く、特に 繰り返し回数が大きくなると他と比べて非常に遅くなる ことがわかりました。
BitBoard クラスの __init__ メソッドの修正
折角なので、上記の 等比数列の公式を利用 した repeat_bit_sequence3 でビットマスクを計算 するように BitBoard クラスの __init__ メソッド を下記のプログラのように 修正することにします。
-
9 ~ 11 行目：
repeat_bit_sequenceをローカル関数として定義する -
21 ~ 24 行目：先程説明した計算式で
repeat_bit_sequenceを利用してビットマスクを計算する
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 def repeat_bit_sequence(b, l, n):
10 r = 1 << l
11 return b * ((1 - (r ** n)) // (1 - r))
12
13 self.transpose_dc_table = []
14 n = self.BOARD_SIZE
15 ni = n
16 while ni > 1:
17 ni //= 2
18 delta = (n - 1) * ni
19 # M1 を計算する
20 mask = ((1 << ni) - 1) << ni
21 # M3 を計算する
22 mask = repeat_bit_sequence(mask, ni * 2, self.BOARD_SIZE // 2)
23 # ビットマスクを計算する
24 mask = repeat_bit_sequence(mask, self.BOARD_SIZE * ni * 2, self.BOARD_SIZE // (ni * 2))
25 self.transpose_dc_table.append((delta, mask))
26
27 self.initialize()
28
29 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))
def repeat_bit_sequence(b, l, n):
r = 1 << l
return b * ((1 - (r ** n)) // (1 - r))
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
# M3 を計算する
mask = repeat_bit_sequence(mask, ni * 2, self.BOARD_SIZE // 2)
# ビットマスクを計算する
mask = repeat_bit_sequence(mask, self.BOARD_SIZE * ni * 2, self.BOARD_SIZE // (ni * 2))
self.transpose_dc_table.append((delta, mask))
self.initialize()
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
# 参照テーブルの計算
元と同じなので省略
+ def repeat_bit_sequence(b, l, n):
+ r = 1 << l
+ return b * ((1 - (r ** n)) // (1 - r))
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
+ mask = repeat_bit_sequence(mask, ni * 2, self.BOARD_SIZE // 2)
# ビットマスクを計算する
- w = ni * 2
- while w < n:
- mask |= mask << (w * n)
- w *= 2
+ mask = repeat_bit_sequence(mask, self.BOARD_SIZE * ni * 2, self.BOARD_SIZE // (ni * 2))
self.transpose_dc_table.append((delta, mask))
self.initialize()
BitBoard.__init__ = __init__
前回の記事と同じ下記のプログラムで 上記のビットマスクを利用した transpose_dc の処理を行うと、実行結果から 正しい処理が行われることが 確認できました。
from marubatsu import Marubatsu
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
任意の大きさのビットボードの転置処理
前回の記事ではゲーム盤を表す ビットボードのサイズが 2 のべき乗 の場合の 転置処理 を紹介しました。残念ながら 2 のべき乗でないサイズ のビットボードの 転置処理を効率よく行うことは難しい ので、以前の記事で 全ビットの交換 による ビットボードの反転処理 を行った場合と同様に、ビットボードのサイズ を実際の ゲーム盤のサイズ以上 の 最も小さな 2 のべき乗として処理を行う ことにします。例えば 3 × 3 のサイズ の場合は 3 以上の最も小さい 2 のべき乗は 4 なので、4 x 4 のサイズのビットボードとして転置処理 を行います。
ビットボードの反転処理 の場合は ビットボードの行の数を変える必要はない ので、下図のように 3 列 3 行 のビットボードの 列だけを 4 列 にした 4 列 3 行 のビットボードに対する 反転処理 を行いました。また、下図のようにビットボードの列のサイズを増やしても 水色の部分のゲーム盤の部分のビットの番号は変化せず、増えた 3 列のビットは全て 0 なので、列を増やしても ビットボードの値を変更する必要はありませんでした。
一方、ビットボードの転置処理 の場合は列だけでなく、行のサイズも変更する必要 があります。その結果、下図のように 水色の部分のゲーム盤の部分のビットの番号が変化してしまう ことになるため、ビットボードの値を計算し直す必要がある という問題が発生します。一方で、ビットボードの反転処理の場合と異なり、転置したビットボード の 水色のビットの範囲は変化しない ので、最後にビットをシフトして移動する必要はありません。
ビットボードのサイズを変更 した際に、ビットボードの値が変化する という 問題を解決する方法 としては、最初から 2 のべき乗のサイズ として ビットボードを作成する という方法があるので、本記事では そのように BitBoard クラスを修正 することにします。
なお、そのように修正することで、実際の ゲーム盤よりも大きなサイズのビットボードが作成される ため、ビットボードのビット長が長く なって 処理時間が長くなる という 問題が発生する ことになります。ただし、ビット長の増加による処理時間の増加より も ビットボードの転置アルゴリズムの効率の良さ の メリットの方が上回る のではないかと思います。本記事では検証しませんが、興味がある方はその点について検証してみて下さい。
BitBoard クラスの修正
ビットボードのサイズ を ゲーム盤のサイズ以上 の 最も小さな 2 のべき乗とする ための BitBoard クラスの修正 を行います。
__init__ メソッドの修正
最初に __init__ メソッドの修正を行います。修正箇所が多いので順番に説明します。
下記は __init__ メソッドの 先頭の部分を修正 したプログラムです。下記でも説明しますが、ビットボードのサイズ は BB_SIZE という 属性に計算して代入 し、BOARD_SIZE 属性 には引き続き ゲーム盤のサイズを代入 することにしました。
また、ゲーム盤のマスの数を代入していた bit_length を ビットボードのビット長 を代入する属性に変更し、ゲーム盤のマス（square）の数（number） を square_num という属性に代入 することにしました。
-
3 行目：ゲーム盤のサイズ以上 の 最も小さな 2 のべき乗の計算 は、以前の記事で全ビットの交換によるビットボードの反転処理を実装した際に
BB_SIZEという属性にその値を計算して代入 していたが、BB_SIZE属性の値 は__init__メソッドの先頭の 4 行目の処理で必要となる ため、その処理を 3 行目に移動 した -
4 行目：ビットボードのビット長 を表す
bit_length属性をself.BB_SIZEで計算 するように修正した -
5 行目：ゲーム盤のマスの数 は 引き分けの判定の際に利用する ので、マスの数 を
square_numという属性に代入 するようにした
1 def __init__(self, board_size=3, count_linemark=False):
2 self.BOARD_SIZE = board_size
3 self.BB_SIZE = 1 << (self.BOARD_SIZE - 1).bit_length()
4 self.bit_length = self.BB_SIZE ** 2
5 self.square_num = self.BOARD_SIZE ** 2
6 self.count_linemark = count_linemark
行番号のないプログラム
def __init__(self, board_size=3, count_linemark=False):
self.BOARD_SIZE = board_size
self.BB_SIZE = 1 << (self.BOARD_SIZE - 1).bit_length()
self.bit_length = self.BB_SIZE ** 2
self.square_num = self.BOARD_SIZE ** 2
self.count_linemark = count_linemark
修正箇所
def __init__(self, board_size=3, count_linemark=False):
self.BOARD_SIZE = board_size
+ self.BB_SIZE = 1 << (self.BOARD_SIZE - 1).bit_length()
- self.bit_length = self.BOARD_SIZE ** 2
+ self.bit_length = self.BB_SIZE ** 2
+ self.square_num = self.BOARD_SIZE ** 2
self.count_linemark = count_linemark
以後の 主な修正 は BOARD_SIZE を BB_SIZE に修正する というものですが、すべての BOARD_SIZE を BB_SIZE に修正してはいけない 点に注意が必要です。そのため、以後の修正では BOARD_SIZE の意味を考えながら 修正する必要があります。
下記は __init__ メソッドの中で 以前の記事で説明した is_winner メソッドで利用するビットマスクなど を計算する部分を修正したプログラムです。
-
2、13 行目：
fullmask属性 は以前の記事で説明したように、合法手の一覧を計算する際に必要 となる ゲーム盤のすべてのマスに対応するビットを1とした ビット列 である。ゲーム盤とビットボードのサイズが同じ場合は(1 << self.BOARD_SIZE ** 2) - 1という式で計算できたが、ゲーム盤とビットボードのサイズが異なる場合はその式では計算できない。そこで、2 行目 ではfullmaskを0で初期化 し、ゲーム盤のすべてのマスに対する繰り返し処理 の中の 13 行目 でfullmask属性のその マスに対応するビットを1にする という方法で計算するように修正した -
7 ~ 13 行目の繰り返し処理 は、ゲーム盤の範囲内のマス に対する繰り返し処理なので
BOARD_SIZEをBB_SIZEに 修正してはいけない 点に注意すること -
17 行目 の右上から左下方向の 対角線の座標の計算 は ゲーム盤のサイズから計算する必要 があるので
BOARD_SIZEをBB_SIZEに 修正してはいけない 点に注意すること
1 # 参照テーブルの計算
2 self.fullmask = 0
3 self.colmasks = []
4 self.rowmasks = []
5 self.diamask1 = 0
6 self.diamask2 = 0
7 for i in range(self.BOARD_SIZE):
8 colmask = 0
9 rowmask = 0
10 for j in range(self.BOARD_SIZE):
11 colmask |= self.xy_to_move(i, j)
12 rowmask |= self.xy_to_move(j, i)
13 self.fullmask |= self.xy_to_move(i, j)
14 self.colmasks.append(colmask)
15 self.rowmasks.append(rowmask)
16 self.diamask1 |= self.xy_to_move(i, i)
17 self.diamask2 |= self.xy_to_move(i, self.BOARD_SIZE - i - 1)
18 self.masklist = self.colmasks + self.rowmasks + [self.diamask1, self.diamask2]
行番号のないプログラム
# 参照テーブルの計算
self.fullmask = 0
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.fullmask |= self.xy_to_move(i, j)
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.fullmask = (1 << self.BOARD_SIZE ** 2) - 1
+ self.fullmask = 0
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.fullmask |= self.xy_to_move(i, j)
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]
下記は __init__ メソッドの中で ビットボードの反転処理で利用 する fliplr_ds_table と fliplr_sa_table を計算 する部分を 修正したプログラム です。
-
fliplr_ds_tableの計算では、ビットボードの中で ゲーム盤を表す部分の列を分割して交換 するという処理を行うので、3 行目 のlengthには ゲーム盤の幅を代入する必要 があるためBB_SIZEに 修正してはいけない -
5、8 行目：これらの行に記述されていた
BOARD_SIZEは ビットボードの行の高さを表す のでBB_SIZEに修正する必要 がある - 15 行目の前にあった
BB_SIZEを計算する処理 は先ほど__init__メソッドの先頭で行うようにしたので削除 した -
15 行目：全ビットの交換によるビットボードの反転処理 で、最後に右シフト演算で列をずらす ための ビット数 を表す
deltaには ずらす列分のマスの数を計算 する。ビットボードでは 1 列にBB_SIZE個のマスが並ぶ ので、ずらす列の数 を表すself.BB_SIZE - self.BOARD_SIZEにBB_SIZEを乗算するように修正 する必要がある -
18、21、23 行目：
fliplr_sa_tableでは ビットボード全体を分割して交換 する処理を行うので、3 行目とは異なりlengthに代入する値も含めてBOARD_SIZEをBB_SIZEに修正する必要 がある
1 self.fliplr_ds_table = []
2 mask = None
3 length = self.BOARD_SIZE
4 while length > 1:
5 delta = (length + 1) // 2 * self.BB_SIZE
6 length //= 2
7 if mask is None:
8 mask = (1 << (length * self.BB_SIZE)) - 1
9 else:
10 m = mask & (mask >> delta)
11 mask = m | (m << prevdelta)
12 self.fliplr_ds_table.append((delta, mask))
13 prevdelta = delta
14
15 self.delta = (self.BB_SIZE - self.BOARD_SIZE) * self.BB_SIZE
16 self.fliplr_sa_table = []
17 mask = None
18 length = self.BB_SIZE
19 while length > 1:
20 length //= 2
21 delta = length * self.BB_SIZE
22 if mask is None:
23 mask = (1 << (length * self.BB_SIZE)) - 1
24 else:
25 m = mask & (mask >> delta)
26 mask = m | (m << prevdelta)
27 self.fliplr_sa_table.append((delta, mask))
28 prevdelta = delta
行番号のないプログラム
self.fliplr_ds_table = []
mask = None
length = self.BOARD_SIZE
while length > 1:
delta = (length + 1) // 2 * self.BB_SIZE
length //= 2
if mask is None:
mask = (1 << (length * self.BB_SIZE)) - 1
else:
m = mask & (mask >> delta)
mask = m | (m << prevdelta)
self.fliplr_ds_table.append((delta, mask))
prevdelta = delta
self.delta = (self.BB_SIZE - self.BOARD_SIZE) * self.BB_SIZE
self.fliplr_sa_table = []
mask = None
length = self.BB_SIZE
while length > 1:
length //= 2
delta = length * self.BB_SIZE
if mask is None:
mask = (1 << (length * self.BB_SIZE)) - 1
else:
m = mask & (mask >> delta)
mask = m | (m << prevdelta)
self.fliplr_sa_table.append((delta, mask))
prevdelta = delta
修正箇所
self.fliplr_ds_table = []
mask = None
length = self.BOARD_SIZE
while length > 1:
- delta = (length + 1) // 2 * self.BOARD_SIZE
+ delta = (length + 1) // 2 * self.BB_SIZE
length //= 2
if mask is None:
- mask = (1 << (length * self.BOARD_SIZE)) - 1
+ mask = (1 << (length * self.BB_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.delta = (self.BB_SIZE - self.BOARD_SIZE) * self.BB_SIZE
self.fliplr_sa_table = []
mask = None
- length = self.BOARD_SIZE
+ length = self.BB_SIZE
while length > 1:
length //= 2
- delta = length * self.BOARD_SIZE
+ delta = length * self.BB_SIZE
if mask is None:
- mask = (1 << (length * self.BOARD_SIZE)) - 1
+ mask = (1 << (length * self.BB_SIZE)) - 1
else:
m = mask & (mask >> delta)
mask = m | (m << prevdelta)
self.fliplr_sa_table.append((delta, mask))
prevdelta = delta
下記は __init__ メソッドの中で ビットボードの転置処理で利用 する transpose_ds_table と transpose_dc_table を計算 する部分を 修正したプログラム です。
-
2、4 行目：
transpose_ds_tableで計算するビットマスクの中で1となるビット は ゲーム盤内の交換するマス に対応するビットなので、BOARD_SIZEをBB_SIZEに 修正してはいけない -
6 行目：交換するビットの間隔 を表す
deltaは 前回の記事で説明したように $\boldsymbol{(n - 1)}$ × $\boldsymbol{i}$ という式で計算 するが、この $\boldsymbol{n}$ は ビットボードの行の高さを表す のでBOARD_SIZEをBB_SIZEに修正する必要 がある -
13、21、23 行目：
transpose_dc_tableで計算するビットマスクは ビットボード全体に対するもの なので、BOARD_SIZEをBB_SIZEに修正する
1 self.transpose_ds_table = []
2 for i in range(1, self.BOARD_SIZE):
3 mask = 0
4 for j in range(self.BOARD_SIZE - i):
5 mask |= self.xy_to_move(j, i + j)
6 self.transpose_ds_table.append(((self.BB_SIZE - 1) * i, mask))
7
8 def repeat_bit_sequence(b, l, n):
9 r = 1 << l
10 return b * ((1 - (r ** n)) // (1 - r))
11
12 self.transpose_dc_table = []
13 n = self.BB_SIZE
14 ni = n
15 while ni > 1:
16 ni //= 2
17 delta = (n - 1) * ni
18 # M1 を計算する
19 mask = ((1 << ni) - 1) << ni
20 # M3 を計算する
21 mask = repeat_bit_sequence(mask, ni * 2, self.BB_SIZE // 2)
22 # ビットマスクを計算する
23 mask = repeat_bit_sequence(mask, self.BB_SIZE * ni * 2, self.BB_SIZE // (ni * 2))
24 self.transpose_dc_table.append((delta, mask))
行番号のないプログラム
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.BB_SIZE - 1) * i, mask))
def repeat_bit_sequence(b, l, n):
r = 1 << l
return b * ((1 - (r ** n)) // (1 - r))
self.transpose_dc_table = []
n = self.BB_SIZE
ni = n
while ni > 1:
ni //= 2
delta = (n - 1) * ni
# M1 を計算する
mask = ((1 << ni) - 1) << ni
# M3 を計算する
mask = repeat_bit_sequence(mask, ni * 2, self.BB_SIZE // 2)
# ビットマスクを計算する
mask = repeat_bit_sequence(mask, self.BB_SIZE * ni * 2, self.BB_SIZE // (ni * 2))
self.transpose_dc_table.append((delta, mask))
修正箇所
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_ds_table.append(((self.BB_SIZE - 1) * i, mask))
def repeat_bit_sequence(b, l, n):
r = 1 << l
return b * ((1 - (r ** n)) // (1 - r))
self.transpose_dc_table = []
- n = self.BOARD_SIZE
+ n = self.BB_SIZE
ni = n
while ni > 1:
ni //= 2
delta = (n - 1) * ni
# M1 を計算する
mask = ((1 << ni) - 1) << ni
# M3 を計算する
- mask = repeat_bit_sequence(mask, ni * 2, self.BOARD_SIZE // 2)
+ mask = repeat_bit_sequence(mask, ni * 2, self.BB_SIZE // 2)
# ビットマスクを計算する
- mask = repeat_bit_sequence(mask, self.BOARD_SIZE * ni * 2, self.BOARD_SIZE // (ni * 2))
+ mask = repeat_bit_sequence(mask, self.BB_SIZE * ni * 2, self.BB_SIZE // (ni * 2))
self.transpose_dc_table.append((delta, mask))
下記は修正した __init__ メソッドの全体 のプログラムです。長いので折りたたみました。
__init__メソッドの定義
def __init__(self, board_size=3, count_linemark=False):
self.BOARD_SIZE = board_size
self.BB_SIZE = 1 << (self.BOARD_SIZE - 1).bit_length()
self.bit_length = self.BB_SIZE ** 2
self.square_num = self.BOARD_SIZE ** 2
self.count_linemark = count_linemark
# 参照テーブルの計算
self.fullmask = 0
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.fullmask |= self.xy_to_move(i, j)
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.BB_SIZE
length //= 2
if mask is None:
mask = (1 << (length * self.BB_SIZE)) - 1
else:
m = mask & (mask >> delta)
mask = m | (m << prevdelta)
self.fliplr_ds_table.append((delta, mask))
prevdelta = delta
self.delta = (self.BB_SIZE - self.BOARD_SIZE) * self.BB_SIZE
self.fliplr_sa_table = []
mask = None
length = self.BB_SIZE
while length > 1:
length //= 2
delta = length * self.BB_SIZE
if mask is None:
mask = (1 << (length * self.BB_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.BB_SIZE - 1) * i, mask))
def repeat_bit_sequence(b, l, n):
r = 1 << l
return b * ((1 - (r ** n)) // (1 - r))
self.transpose_dc_table = []
n = self.BB_SIZE
ni = n
while ni > 1:
ni //= 2
delta = (n - 1) * ni
# M1 を計算する
mask = ((1 << ni) - 1) << ni
# M3 を計算する
mask = repeat_bit_sequence(mask, ni * 2, self.BB_SIZE // 2)
# ビットマスクを計算する
mask = repeat_bit_sequence(mask, self.BB_SIZE * ni * 2, self.BB_SIZE // (ni * 2))
self.transpose_dc_table.append((delta, mask))
self.initialize()
BitBoard.__init__ = __init__
修正する必要がないメソッド
BOARD_SIZE を利用 するメソッドの中で 下記のメソッド は、ビットボードのサイズではなく ゲーム盤のサイズを利用した処理を行っている ので BB_SIZE に修正してはいけません。
-
initializeメソッド。ゲーム盤のサイズの数だけ0を要素とする list を計算するためにBOARD_SIZEを利用する -
setmark_by_moveメソッド。右上から左下方向の対角線上のマスであることを判定するためにBOARD_SIZEを利用する -
is_winnerメソッド。直線上に同じマスがゲーム盤のサイズの数だけ並んでいることや、右上から左下方向の対角線上のマスであることを判定するためにBOARD_SIZEを利用する -
count_markpatsメソッド。直線上の空のマスの数を計算するためにBOARD_SIZEを利用する -
board_to_strメソッド。ゲーム盤上のマスを文字列に変換する処理を計算するためにBOARD_SIZEを利用する
また、bit_length 属性 の値がゲーム盤と同じ大きさのビットボードのビット長から、実際のビットボードのビット長に修正 されたので、bit_length 属性を利用するメソッド を 修正するかどうかを検討する必要 があります。board_to_hashables メソッドの場合は、〇 と × のビットボードを並べて 1 つの値にするため に、ビットボードのビット長である bit_length を利用する必要がある ので 修正する必要はありません。
bit_length 属性の 利用を修正する必要 がある judge メソッドについては後述します。
xy_to_move と move_to_xy メソッドの修正
ビットボードのサイズが変わった ので ビットボードの座標の計算式が変化 します。そのため、下記のプログラムの 2、8 行目 のように xy_to_move と move_to_xy メソッドの BOARD_SIZE を BB_SIZE に修正 する必要があります。
1 def xy_to_move(self, x, y):
2 return 1 << (y + self.BB_SIZE * x)
3
4 BitBoard.xy_to_move = xy_to_move
5
6 def move_to_xy(self, move):
7 move = move.bit_length() - 1
8 return move // self.BB_SIZE, move % self.BB_SIZE
9
10 BitBoard.move_to_xy = move_to_xy
行番号のないプログラム
def xy_to_move(self, x, y):
return 1 << (y + self.BB_SIZE * x)
BitBoard.xy_to_move = xy_to_move
def move_to_xy(self, move):
move = move.bit_length() - 1
return move // self.BB_SIZE, move % self.BB_SIZE
BitBoard.move_to_xy = move_to_xy
修正箇所
def xy_to_move(self, x, y):
- return 1 << (y + self.BOARD_SIZE * x)
+ return 1 << (y + self.BB_SIZE * x)
BitBoard.xy_to_move = xy_to_move
def move_to_xy(self, move):
move = move.bit_length() - 1
- return move // self.BOARD_SIZE, move % self.BOARD_SIZE
+ return move // self.BB_SIZE, move % self.BB_SIZE
BitBoard.move_to_xy = move_to_xy
judge メソッドの修正
judge メソッドでは 引き分けの判定 を行うために ゲーム盤のマスの数を利用 していますが、bit_length 属性には ビットボードのビット長が代入されるようになった ので、下記のプログラムの 8 行目 のように ゲーム盤のマスの数を表す square_num 属性に修正する必要 があります。なお、決着がついていないことを判定 する 2 行目 の処理では ゲーム盤のサイズを利用する必要がある ので BOARD_SIZE を修正してはいけません。
1 def judge(self, last_turn, last_move, move_count):
2 if move_count < self.BOARD_SIZE * 2 - 1:
3 return Marubatsu.PLAYING
4 # 直前に着手を行ったプレイヤーの勝利の判定
5 if self.is_winner(last_turn, last_move):
6 return last_turn
7 # 引き分けの判定
8 elif move_count == self.square_num:
9 return Marubatsu.DRAW
10 # 上記のどれでもなければ決着がついていない
11 else:
12 return Marubatsu.PLAYING
13
14 BitBoard.judge = judge
行番号のないプログラム
def judge(self, last_turn, last_move, move_count):
if move_count < self.BOARD_SIZE * 2 - 1:
return Marubatsu.PLAYING
# 直前に着手を行ったプレイヤーの勝利の判定
if self.is_winner(last_turn, last_move):
return last_turn
# 引き分けの判定
elif move_count == self.square_num:
return Marubatsu.DRAW
# 上記のどれでもなければ決着がついていない
else:
return Marubatsu.PLAYING
BitBoard.judge = judge
修正箇所
def judge(self, last_turn, last_move, move_count):
if move_count < self.BOARD_SIZE * 2 - 1:
return Marubatsu.PLAYING
# 直前に着手を行ったプレイヤーの勝利の判定
if self.is_winner(last_turn, last_move):
return last_turn
# 引き分けの判定
- elif move_count == self.bit_length:
+ elif move_count == self.square_num:
return Marubatsu.DRAW
# 上記のどれでもなければ決着がついていない
else:
return Marubatsu.PLAYING
BitBoard.judge = judge
calc_same_hashables の修正
下記は 前回までの記事で定義した fliplr_sa と transpose_dc メソッドで ビットボードの反転と転置処理を行う ように calc_samehashables を修正 したプログラムです。
-
修正前 のプログラムでは 2 行目の前 で ビットボードを
circlebbとcrossbbという変数に代入して処理を行っていた が、fliplr_saとtranspose_dcメソッドではboard属性に代入されたビットボードに対する処理を行う ので それらの変数を削除 した -
4、13 行目：
fliplr_saとtranspose_dcメソッドで ビットボードの反転と転置処理を行う ように修正した -
5、14 行目：
circlebbとcrossbbを廃止したのでboard_to_hashableでhashableを計算 するように修正した
1 def calc_same_hashables(self, move=None):
元と同じなので省略
2 for _ in range(4):
3 # 左右の反転処理
4 self.fliplr_sa()
5 hashable = self.board_to_hashable()
6 if move is None:
7 hashables.add(hashable)
8 else:
9 x = self.BOARD_SIZE - x - 1
10 hashables[hashable] = self.xy_to_move(x, y)
11
12 # 転置処理
13 self.transpose_dc()
14 hashable = self.board_to_hashable()
15 if move is None:
16 hashables.add(hashable)
17 else:
18 x, y = y, x
19 hashables[hashable] = self.xy_to_move(x, y)
20
21 return hashables
22
23 BitBoard.calc_same_hashables = calc_same_hashables
行番号のないプログラム
def calc_same_hashables(self, move=None):
if move is None:
hashables = set()
else:
hashables = {}
if move is not None:
x, y = self.move_to_xy(move)
for _ in range(4):
# 左右の反転処理
self.fliplr_sa()
hashable = self.board_to_hashable()
if move is None:
hashables.add(hashable)
else:
x = self.BOARD_SIZE - x - 1
hashables[hashable] = self.xy_to_move(x, y)
# 転置処理
self.transpose_dc()
hashable = self.board_to_hashable()
if move is None:
hashables.add(hashable)
else:
x, y = y, x
hashables[hashable] = self.xy_to_move(x, y)
return hashables
BitBoard.calc_same_hashables = calc_same_hashables
修正箇所
def calc_same_hashables(self, move=None):
元と同じなので省略
- circlebb = self.board[0]
- crossbb = self.board[1]
for _ in range(4):
# 左右の反転処理
- c = (circlebb ^ (circlebb >> 6)) & 0b111
- circlebb = c ^ (c << 6) ^ circlebb
- c = (crossbb ^ (crossbb >> 6)) & 0b111
- crossbb = c ^ (c << 6) ^ crossbb
+ self.fliplr_sa()
- hashable = circlebb | (crossbb << self.bit_length)
+ hashable = self.board_to_hashable()
if move is None:
hashables.add(hashable)
else:
x = self.BOARD_SIZE - x - 1
hashables[hashable] = self.xy_to_move(x, y)
# 転置処理
- c = (circlebb ^ (circlebb >> 2)) & 0b100010
- circlebb = c ^ (c << 2) ^ circlebb
- c = (circlebb ^ (circlebb >> 4)) & 0b100
- circlebb = c ^ (c << 4) ^ circlebb
- c = (crossbb ^ (crossbb >> 2)) & 0b100010
- crossbb = c ^ (c << 2) ^ crossbb
- c = (crossbb ^ (crossbb >> 4)) & 0b100
- crossbb = c ^ (c << 4) ^ crossbb
+ self.transpose_dc()
- hashable = circlebb | (crossbb << self.bit_length)
+ hashable = self.board_to_hashable()
if move is None:
hashables.add(hashable)
else:
x, y = y, x
hashables[hashable] = self.xy_to_move(x, y)
return hashables
BitBoard.calc_same_hashables = calc_same_hashables
動作の確認と処理時間の計測
修正した BitBoard クラスが正しく動作するかどうかを確認 することにします。
反転処理と転置処理を行うメソッドの動作の確認
今回の記事で BitBoard クラスが 任意のサイズのゲーム盤の反転処理と転置処理 を行えるようになったので、2 のべき乗でない 5 x 5 のサイズ のゲーム盤に対する fliplr_ds、fliplr_sa、transpose_ds、transpose_dc メソッドの処理 を下記のプログラムで行いました。局面は前回の記事と同様に 対角線を含む左下半分の範囲のマスに着手を行った局面 とし、2 回同じメソッドを呼び出すことで元の局面に戻るかどうかも確認 しています。実行結果から 正しい処理が行われることが確認 できました。
mb = Marubatsu(boardclass=BitBoard, board_size=5)
for x in range(5):
for y in range(x, 5):
mb.cmove(x, y)
print(mb)
print()
print("fliplr_ds")
mb.board.fliplr_ds()
print(mb)
mb.board.fliplr_ds()
print(mb)
print()
print("fliplr_sa")
mb.board.fliplr_sa()
print(mb)
mb.board.fliplr_sa()
print(mb)
print()
print("transpose_ds")
mb.board.transpose_ds()
print(mb)
mb.board.transpose_ds()
print(mb)
print()
print("transpose_dc")
mb.board.transpose_dc()
print(mb)
mb.board.transpose_dc()
print(mb)
print()
実行結果
Turn x
o....
xx...
oox..
xxoo.
ooxxO
fliplr_ds
Turn x
....o
...xx
..xoo
.ooxx
oxxoO
Turn x
o....
xx...
oox..
xxoo.
ooxxO
fliplr_sa
Turn x
....o
...xx
..xoo
.ooxx
oxxoO
Turn x
o....
xx...
oox..
xxoo.
ooxxO
transpose_ds
Turn x
oxoxo
.xoxo
..xox
...ox
....O
Turn x
o....
xx...
oox..
xxoo.
ooxxO
transpose_dc
Turn x
oxoxo
.xoxo
..xox
...ox
....O
Turn x
o....
xx...
oox..
xxoo.
ooxxO
calc_same_hashables の動作の確認
下記は 以前の記事 で説明した calc_same_hashables の動作を確認 するプログラムです。ただし、ビットボードのサイズが変化 しているので 8 行目のゲーム盤のすべてのマスに対応するビットを 1 としたビット列 を表す 0b111111111 を mb.fullmask に、9 行目のビットボードのビット長 を表す 9 を mb.bit_length に修正 しました。
実行結果が以前の記事と同じであることから正しく動作することが確認できました。
1 mb = Marubatsu(boardclass=BitBoard)
2 mb.cmove(1, 1)
3 mb.cmove(0, 0)
4 mb.cmove(1, 0)
5 move = mb.board.xy_to_move(1, 0)
6 hashables = mb.board.calc_same_hashables(move)
7 for hashable, move in hashables.items():
8 mb.board.board[0] = hashable & mb.board.fullmask
9 mb.board.board[1] = hashable >> mb.board.bit_length
10 print(mb.board.move_to_xy(move))
11 print(mb)
12 print()
行番号のないプログラム
mb = Marubatsu(boardclass=BitBoard)
mb.cmove(1, 1)
mb.cmove(0, 0)
mb.cmove(1, 0)
move = mb.board.xy_to_move(1, 0)
hashables = mb.board.calc_same_hashables(move)
for hashable, move in hashables.items():
mb.board.board[0] = hashable & mb.board.fullmask
mb.board.board[1] = hashable >> mb.board.bit_length
print(mb.board.move_to_xy(move))
print(mb)
print()
修正箇所
mb = Marubatsu(boardclass=BitBoard)
mb.cmove(1, 1)
mb.cmove(0, 0)
mb.cmove(1, 0)
move = mb.board.xy_to_move(1, 0)
hashables = mb.board.calc_same_hashables(move)
for hashable, move in hashables.items():
- mb.board.board[0] = hashable & 0b111111111
+ mb.board.board[0] = hashable & mb.board.fullmask
- mb.board.board[1] = hashable >> 9
+ mb.board.board[1] = hashable >> mb.board.bit_length
print(mb.board.move_to_xy(move))
print(mb)
print()
実行結果
(1, 0)
Turn x
.Ox
.o.
...
(0, 1)
Turn x
...
oo.
x..
(2, 1)
Turn x
...
.oo
..x
(1, 2)
Turn x
...
.o.
.ox
(1, 2)
Turn x
...
.o.
xo.
(2, 1)
Turn x
..x
.oo
...
(0, 1)
Turn x
x..
oo.
...
(1, 0)
Turn x
xO.
.o.
...
benchmark による動作と処理時間の確認
benchmark で行う ai2 VS ai2 と ai14s VS ai2 の対戦 は、calc_same_hashabels 以外のメソッドを呼び出す ので、その 対戦成績がこれまでの benchmark と同じであるか どうかで 正しい処理が行われることが確認 できます。下記のプログラムの 実行結果の対戦成績 が、以前の記事の benchmark と同じである ことから、BitBoard クラスが 正しい動作を行うことが確認 できました。なお、count_linemark が True の場合の処理は変更していないので False の場合のみで実行しました。
from util import benchmark
benchmark(mbparams={"boardclass": BitBoard})
実行結果
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 22846.27it/s]
count win lose draw
o 29454 14352 6194
x 14208 29592 6200
total 43662 43944 12394
ratio win lose draw
o 58.9% 28.7% 12.4%
x 28.4% 59.2% 12.4%
total 43.7% 43.9% 12.4%
ai14s VS ai2
100%|██████████| 50000/50000 [00:15<00:00, 3168.89it/s]
count win lose draw
o 49446 0 554
x 44043 0 5957
total 93489 0 6511
ratio win lose draw
o 98.9% 0.0% 1.1%
x 88.1% 0.0% 11.9%
total 93.5% 0.0% 6.5%
ai_abs_dls
12.4 ms ± 1.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
下記の表は 修正前 と 上記の修正後 の BitBoard クラスと、3 x 3 のサイズに特化 した BitBoard3x3 クラスの ベンチマークの結果との比較 です。
ai2 VS ai2
|
ai14s VS ai2
|
ai_abs_dls |
|
|---|---|---|---|
| 修正前 | 22457.83 回/秒 | 3129.02 回/秒 | 7.9 ms |
| 修正後 | 22846.27 回/秒 | 3168.89 回/秒 | 12.4 ms |
| BitBoard3x3 | 24220.47 回/秒 | 3238.18 回/秒 | 7.9 ms |
calc_same_hashables 以外 の処理は 修正前とほぼ同じ なので、ai2 VS ai2 と ai14s VS ai2 の修正前と修正後の 処理時間はほぼ同じ になります。一方、calc_same_hashables を利用する ai_abs_dls の処理速度 は 3 x 3 のサイズのゲーム盤に特化 した処理を行っていた 修正前の BitBoard クラス や BitBoard3x3 クラスより遅く なります。以前の記事でも説明しましたが、一般的に 汎用的な処理 は 特化した処理よりも遅くなる のでこれは仕方のないことでしょう。
NpBoolBoard クラスの修正
次の calc_same_hashables の処理時間の比較を行った際に、NpBoolBoard クラスの定義が間違っていた ことに気が付きましたので修正することにします。
具体的には marubatsu.py の NpBoolBoard クラスの定義 が下記のプログラムのように Board クラスを継承している点が間違っていました。
class NpBoolBoard(Board):
略
正しくは 下記のプログラムのように NpBoard クラスを継承する 必要があります。第 216 回以降の marubatsu.py が間違っていたのでそれらを修正しました。
class NpBoolBoard(NpBoard):
略
BitBoard3x3 クラスの修正
今回の記事で BitBoard クラスを修正した結果、BitBoard クラスを継承した BitBoard3x3 クラスが 正しく動作しなくなる ため、下記のプログラムのように 今回の記事で修正した BitBoard クラスのメソッド のうち BitBoard3x3 クラスで定義されていない xy_to_move と move_to_xy メソッドを 修正前の内容で再定義 する必要があります。
from marubatsu import BitBoard3x3
def xy_to_move(self, x:int, y:int) -> int:
return 1 << (y + self.BOARD_SIZE * x)
BitBoard3x3.xy_to_move = xy_to_move
def move_to_xy(self, move:int) -> tuple[int, int]:
move = move.bit_length() - 1
return move // self.BOARD_SIZE, move % self.BOARD_SIZE
BitBoard3x3.move_to_xy = move_to_xy
calc_same_hashables の処理時間の比較
下記のすべての条件の組み合わせ で、calc_same_hashable の処理時間を計測して比較 することにします。ただし、BitBoard3x3 クラスは 3 x 3 のサイズのゲーム盤しか扱えないので 3 x 3 のサイズのゲーム盤でのみ処理速度を計測します。
- これまでに定義したゲーム盤を表すクラス
- ゲーム盤のサイズが 3、5、10、50、100 の場合
下記はその処理を行うプログラムです。
from marubatsu import ListBoard, List1dBoard, ArrayBoard, NpBoard, \
NpIntBoard, NpBoolBoard
for board_size in [3, 5, 10, 50, 100]:
print(f"board size = {board_size}")
for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard,
NpBoolBoard, BitBoard]:
if board_size != 3 and boardclass == BitBoard3x3:
continue
print(f"boardclass: {boardclass.__name__}")
mb = Marubatsu(boardclass=boardclass, board_size=board_size)
for i in range(board_size - 1):
mb.cmove(i, 0)
mb.cmove(i, 1)
%timeit mb.board.calc_same_hashables()
print()
実行結果
board size = 3
boardclass: ListBoard
21.1 μs ± 1.48 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: List1dBoard
7.39 μs ± 31.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: ArrayBoard
7.98 μs ± 109 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: NpBoard
50.9 μs ± 112 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpIntBoard
51.1 μs ± 1.04 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpBoolBoard
55.7 μs ± 931 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: BitBoard
10.6 μs ± 75.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: BitBoard3x3
4.31 μs ± 20.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
board size = 5
boardclass: ListBoard
46.9 μs ± 944 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: List1dBoard
11.1 μs ± 18.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: ArrayBoard
12.1 μs ± 25 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
boardclass: NpBoard
51.2 μs ± 245 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpIntBoard
51 μs ± 373 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpBoolBoard
55.7 μs ± 364 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: BitBoard
17.3 μs ± 25.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
board size = 10
boardclass: ListBoard
167 μs ± 1.01 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: List1dBoard
24.1 μs ± 213 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: ArrayBoard
26 μs ± 137 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpBoard
53.7 μs ± 915 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpIntBoard
55.3 μs ± 342 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpBoolBoard
60.7 μs ± 169 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: BitBoard
25.2 μs ± 235 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
board size = 50
boardclass: ListBoard
5.22 ms ± 30.1 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
boardclass: List1dBoard
274 μs ± 2.65 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: ArrayBoard
304 μs ± 1.98 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: NpBoard
129 μs ± 899 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpIntBoard
149 μs ± 764 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
boardclass: NpBoolBoard
241 μs ± 1 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: BitBoard
74.2 μs ± 203 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
board size = 100
boardclass: ListBoard
27.1 ms ± 115 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
boardclass: List1dBoard
950 μs ± 19.5 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: ArrayBoard
1.02 ms ± 1.87 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: NpBoard
356 μs ± 2.23 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: NpIntBoard
431 μs ± 12.7 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: NpBoolBoard
721 μs ± 16 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: BitBoard
191 μs ± 974 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
下記は上記の実行結果をまとめた表です。処理時間の単位は μs で、小数点以下第 2 桁で四捨五入しました。
| ゲーム盤のクラス | 3 | 5 | 10 | 50 | 100 |
|---|---|---|---|---|---|
ListBoard |
21.1 | 46.9 | 167.0 | 5,220.0 | 27,100.0 |
List1dBoard |
7.4 | 11.1 | 24.1 | 274.0 | 950.0 |
ArrayBoard |
8.0 | 12.1 | 26.0 | 304.0 | 1,020.0 |
NpBoard |
50.9 | 51.2 | 53.7 | 129.0 | 356.0 |
NpIntBoard |
51.1 | 51.0 | 55.3 | 149.0 | 431.0 |
NpBoolBoard |
55.7 | 55.7 | 60.7 | 241.0 | 721.0 |
BitBoard |
10.6 | 17.3 | 25.2 | 74.2 | 191.0 |
BitBoard3x3 |
4.3 |
上記の表から ゲーム盤のサイズが 10 以下のように小さい場合 は、ゲーム盤のサイズが 3 の場合に特化した BitBoard3x3 クラスを除くと List1dBoard クラスが最速 になりますが、ゲーム盤の サイズがさらに大きくなる と BitBoard クラスが最速 になり、numpy を利用したクラス の方が List1dBoard クラスよりも高速 になることが確認できました。これは、ゲーム盤のサイズが大きくなった場合 の 分割統治法を利用したアルゴリズムの処理の効率の良さが原因 です。
今回の記事のまとめ
今回の記事では 任意のサイズ のゲーム盤に対して 分割統治法 で ビットボードの転置処理 を行えるように BitBoard クラスを修正 し、BitBoard クラスの定義を完成 させました。また、BitBoard クラスの ゲーム盤の転置処理 がゲーム盤の サイズが大きくなると最速になる ことを示しました。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| marubatsu.py | 本記事で更新した marubatsu_new.py |
次回の記事