0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ysgeso

Pythonで〇×ゲームのAIを一から作成する　その214　delta swap を利用した局面の反転、転置による同一局面の計算

0
Last updated at Posted at 2026-02-01

目次と前回の記事

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 クラスのまだ実装していない残りの board_to_hashable と calc_same_hashables の定義を行います。

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

board_to_hashable メソッドの定義

以前の記事 で説明したように、board_to_hashable メソッドは、ゲーム盤を表すハッシュ可能な値を計算 するという処理を行います。

BitBoard クラスのゲーム盤は、2 つの int 型 のビットボードで表現されます。int 型 のデータは ハッシュ可能な値 なので、2 つの int 型 のデータを 1 つの int 型のデータにまとめる ことでゲーム盤を表す ハッシュ可能な値を計算 することができます。

3 × 3 のゲーム盤の ビットボード は 9 ビットのビット列で表現 されるので、2 つのビットボード のデータは 9 × 2 = 18 ビットのビット列で表現 することができます。

具体的には 0 ~ 8 番 のビットを 〇 のゲーム盤の ビットボード のデータ、9 ~ 17 番 のビットを × のゲーム盤の ビットボード のデータとした ビット列を計算 することで、ゲーム盤 を表す ハッシュ可能な int 型のデータを計算 することができます。

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

  • × のビットボード のデータを 左シフト で 9 ビット分左にずらした値を計算 する
  • 上記で計算した値と 〇 のビットボード のデータの OR 演算 を行う

下図の局面を具体例に挙げて説明します。

下図は 上記のデータに対して行われる処理 を表す図です。図の 黄色 の部分は × のビットボード のデータ、水色 の部分は 〇 のビットボード のデータを表します。白色の 部分は 必ず 0 となるビット を表します。

× のビットボード に対して 9 ビットの左シフト演算 を行った結果、0 ~ 8 番 の × のビットボードのデータが 9 ~ 17 番のビットに移動 します。また、左シフト演算 ではずれた結果生じた 空いたビットはすべて 0 で埋められるので図のように 0 ~ 8 番 のビットは すべて 0 になる値が計算されます。

次に、その値と 〇 のビットボード との OR 演算 を行います。〇 のビットボード の 9 番以降のビットはすべて 0 なので、図のように 9 ~ 17 番 のビットは すべて 0 となり、上図のように 0 ~ 8 番 のビットが 〇 のビットボード のデータに、9 ~ 17 番 のビットが × のビットボード のデータになるような ビット列が計算 されます。

board_to_hashable メソッドの定義

下記は board_to_hashable メソッドの定義を行うプログラムです。

  • 4 行目：上記で説明した計算を行った結果を返り値として返す。左シフトを行うビット数はゲーム盤のマスの数なので self.BOARD_SIZE ** 2 で計算できる
1  from marubatsu import BitBoard
2  
3  def board_to_hashable(self):
4      return self.board[0] | (self.board[1] << (self.BOARD_SIZE ** 2)) 
5  
6  BitBoard.board_to_hashable = board_to_hashable
行番号のないプログラム 
from marubatsu import BitBoard

def board_to_hashable(self):
    return self.board[0] | (self.board[1] << (self.BOARD_SIZE ** 2)) 

BitBoard.board_to_hashable = board_to_hashable

下記のプログラムは 先ほどの図の局面 に対する board_to_hashable を計算 するプログラムです。

5 行目の print の表示 は各ビットの 対応する × と 〇 のビットボードでのビットの番号 を表します。実行結果から 正しい計算が行われる ことが確認できました。

1  bb = BitBoard()
2  bb.board[0] = 0b000100111
3  bb.board[1] = 0b001011000
4  
5  print("  876543210876543210")
6  print(f"0b{bb.board_to_hashable():018b}")
行番号のないプログラム 
bb = BitBoard()
bb.board[0] = 0b000100111
bb.board[1] = 0b001011000

print("  876543210876543210")
print(f"0b{bb.board_to_hashable():018b}")

実行結果

  876543210876543210
0b001011000000100111

処理速度の検証

下記のプログラムで ゲーム開始時の局面 に対する List1dBoard クラスの board_to_hashable との 処理速度を比較 することにします。実行結果から BitBoard クラスの方が 処理速度が約 1.5 倍ほど高速 であることが確認できました。

from marubatsu import List1dBoard

bb = BitBoard()
bb2 = List1dBoard()

%timeit bb.board_to_hashable()
%timeit bb2.board_to_hashable()

実行結果

133 ns ± 1 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
208 ns ± 2.84 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

ビットボードのビット長を計算した属性の追加

board_to_hashable メソッドでは ゲーム盤 のビットボードの ビット長 を self.BOARD_SIZE ** 2 という 式で計算 していますが、この値は常に同じ値になる ので、board_to_hashable 内 で 毎回計算するのは無駄 です。そこで、__init__ メソッドでこの値を bit_length という名前の 属性に代入し、board_to_hashable では その属性の値を利用 することにします。

下記は __init__ メソッドの 3 行目にその処理を追加して修正 するプログラムです。

1  def __init__(self, board_size=3, count_linemark=False):
2      self.BOARD_SIZE = board_size
3      self.bit_length = self.BOARD_SIZE ** 2
元と同じなので省略
4  
5  BitBoard.__init__ = __init__
行番号のないプログラム 
def __init__(self, board_size=3, count_linemark=False):
    self.BOARD_SIZE = board_size
    self.bit_length = self.BOARD_SIZE ** 2
    self.count_linemark = count_linemark
    self.board = [0, 0]
    if self.count_linemark:
        self.rowcount = {
            self.CIRCLE: [0] * self.BOARD_SIZE,
            self.CROSS: [0] * self.BOARD_SIZE,
        }
        self.colcount = {
            self.CIRCLE: [0] * self.BOARD_SIZE,
            self.CROSS: [0] * self.BOARD_SIZE,
        }
        self.diacount = {
            self.CIRCLE: [0] * 2,
            self.CROSS: [0] * 2,
        }    
        
BitBoard.__init__ = __init__
修正箇所 
def __init__(self, board_size=3, count_linemark=False):
    self.BOARD_SIZE = board_size
+   self.bit_length = self.BOARD_SIZE ** 2
元と同じなので省略
        
BitBoard.__init__ = __init__

下記は self.bit_length を利用 するように board_to_hashable の 2 行目を修正 したプログラムです。

1  def board_to_hashable(self):
2      return self.board[0] | (self.board[1] << self.bit_length) 
3  
4  BitBoard.board_to_hashable = board_to_hashable
行番号のないプログラム 
def board_to_hashable(self):
    return self.board[0] | (self.board[1] << self.bit_length) 

BitBoard.board_to_hashable = board_to_hashable
修正箇所 
def board_to_hashable(self):
-   return self.board[0] | (self.board[1] << self.BOARD_SIZE ** 2) 
+   return self.board[0] | (self.board[1] << self.bit_length) 

BitBoard.board_to_hashable = board_to_hashable

上記の修正後に下記のプログラムを実行すると、実行結果から 修正前の 133 ns よりも 処理速度が 高速になることが確認 できました。

bb = BitBoard()

%timeit bb.board_to_hashable()

実行結果

107 ns ± 0.516 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

2026/02/04 修正：4 行目は self.BOARD_SIZE ** 2 ではく、self.BOARD_SIZE * 2 だったので元に戻しました。

self.BOARD_SIZE ** 2 という計算は judge メソッドでも記述 されているので、下記のプログラムの 10 行目のように judge メソッドを修正 することにします。

 1  from marubatsu import Marubatsu
 2
 3  def judge(self, last_turn, last_move, move_count):
 4      if move_count < self.BOARD_SIZE * 2 - 1:
 5          return Marubatsu.PLAYING
 6      # 直前に着手を行ったプレイヤーの勝利の判定
 7      if self.is_winner(last_turn, last_move):
 8          return last_turn
 9      # 引き分けの判定
10      elif move_count == self.bit_length:
11          return Marubatsu.DRAW
12      # 上記のどれでもなければ決着がついていない
13      else:
14          return Marubatsu.PLAYING   
15  
16  BitBoard.judge = judge
行番号のないプログラム 
from marubatsu import Marubatsu

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:
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING   

BitBoard.judge = judge
修正箇所 
from marubatsu import Marubatsu

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

BitBoard.judge = judge

なお、judge メソッドの中から呼び出される is_winner メソッドの処理時間が長い ので、上記の修正を行っても judge メソッドの処理速度はほとんど変わりません。そのため、処理速度の検証は省略します。

calc_same_hashables メソッドの定義方法

calc_same_hashables は 同一局面のハッシュ可能な値を計算 するという処理を行います。以前の記事で説明したように、その処理はゲーム盤を 90 度時計回りに回転 する処理と、ゲーム盤を 左右に反転 する処理を 組み合わせる ことで行えます。

ビットボードでゲーム盤を表現 する場合は、この後で説明する方法で 左右の反転処理 を 高速に行う ことができます。一方、ビットボードのゲーム盤を 90 度時計回りに回転 する処理は 左右の反転処理と比較して時間がかかる ので、ビットボードに対して高速に演算を行うことができる、別の方法を考える ことにします。

その方法は、x 座標と y 座標を入れ替える という処理で、以前の記事で説明したようにそのような処理の事を 転置（transpose）と呼びます。具体的にはゲーム盤の 左右の反転 と 転置 を 交互に 4 回ずつ行う ことで、すべての同一局面を計算 することができます。下図はそのことを表す図1で、左右の反転と転置を交互に 4 回ずつ行うことで、8 種類の同一局面がすべて計算される ことが確認できます。

なお、上図の 奇数番の 1、3、5、7 番の局面だけ をよく見ると、それらが 時計回りに 90 度局面が回転 していることが確認できます。このことから、これまでの同一局面を計算する処理で行ってきた 回転処理 は、転置 と 左右の反転 の 組み合わせで置き換えることができる ということを意味します。また、一番右の局面 に対して 転置 を行うと一番左の 最初の局面に戻る ことも確認できます。

上記から 同一局面の計算 には局面を表す ビットボード に対して 左右の反転 と 転置 の計算を 行うことができれば良い ことがわかります。そこで、3 x 3 のゲーム盤を表す ビットボード に対する 左右の反転 と 転置 の 計算方法 について説明します。

参考までに ビットボード の 反転、回転、転置 などに関する Chess Programming Wiki の記事 のページを下記に記します。また、本記事を執筆するにあたって参考にしたページを紹介します。

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

3 x 3 の ビットボード の 左右の反転 の処理を行う 方法をいくつか紹介 し、その 処理速度を比較 することにします。〇 と × の ビットボードの反転処理 は 同じ処理 を行えば良いので、下記では 〇 のビットボードの 反転処理 について説明します。

確認のためのビットボードの定義

処理が正しく行われているか どうかを 確認 するために、下図の左の 〇 のビットボード を表すデータを b に代入 することにします。 また、下図の右の 左右を反転したビットボード を表すデータを flipb に代入 することにします。

上図から b = 0b001100010、b を左右に 反転した値は 0b010100001 となります。

下記は b に 〇 のビットボード を、flipb に b の左右を反転 したビットボードを代入するプログラムです。

b = 0b001100010
flipb = 0b010100001

定義する関数の仕様

定義する ビットボードの左右を反転 する 関数の仕様 は以下のようにします。

  • 関数名 は fliplrx2 とする。ただし、最後の x には数字 が入る
  • 仮引数 b に 〇 のビットボードを代入 する
  • b の左右を反転したビットボード を計算して 返り値として返す

各ビットを順番に計算する方法

最初に紹介する方法は、左右に反転したビットボード の 0 ~ 8 番 のビットを 順番に計算する という方法です。具体的には下記の手順で計算を行います。

  • 左右を反転したビットボードを計算する変数 result を 0 で初期化する
  • result の 0 ~ 8 番のビットに対して順番に下記の計算を行う
    • result の i 番のビットに対応する b のビットを計算し、1 である場合は result の i 番のビットを 1 にする

result のビットと b のビットの 対応 は、下図から 以下の表のようになる ことがわかります。


result のビットの番号 0 1 2 3 4 5 6 7 8
b のビットの番号 6 7 8 3 4 5 0 1 2

fliplr1 の定義

下記は 上記の手順 で計算を行う fliplr1 の定義です。

  • 1 ~ 11 行目：result の各ビットに対応する b のビットだけを 1 としたビットマスクの一覧を表す list を masktable に代入する。fliplr1 を呼び出すたびにこの処理が行われるのは無駄なので、fliplr1 の外でこの処理を行うようにした
  • 14 行目：result を 0 で初期化する
  • 15 ~ 17 行目：result の 0 ~ 8 番のビットに対する繰り返し処理を行う
  • 16 行目：result の i 目のビットに対応する b のビットが 1 であるかどうかを、対応するビットマスクと b との AND 演算で行う
  • 17 行目：対応する b のビットが 1 の場合は、result と i 番のビットのみが 1 となる 1 << i で計算されるビットマスクとの OR 演算 を行った値で result を更新することで、result の i 番のビットを 1 に更新する
  • 18 行目：result を返り値として返す
 1  masktable = [
 2      0b001000000,
 3      0b010000000,
 4      0b100000000,
 5      0b000001000,
 6      0b000010000,
 7      0b000100000,
 8      0b000000001,
 9      0b000000010,
10      0b000000100,
11  ]
12  
13  def fliplr1(b):
14      result = 0
15      for i in range(9):
16          if b & masktable[i]:
17              result |= 1 << i
18      return result
行番号のないプログラム 
masktable = [
    0b001000000,
    0b010000000,
    0b100000000,
    0b000001000,
    0b000010000,
    0b000100000,
    0b000000001,
    0b000000010,
    0b000000100,
]

def fliplr1(b):
    result = 0
    for i in range(9):
        if b & masktable[i]:
            result |= 1 << i
    return result

下記は b の左右を反転したビットボード を fliplr1 で計算 するプログラムで、fliplr1(b) == flipb が True になることから 正しい計算が行われる ことが確認できます。

print(f"0b{fliplr1(b):09b}")
print(fliplr1(b) == flipb)

実行結果

0b010100001
True

下記は fliplr1 の 処理速度を計測 するプログラムです。

%timeit fliplr1(b)

実行結果

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

列のデータをまとめて計算する方法

左右の反転処理 は、result の下記の表の 各列を表す 3 つのビット に対して、b の列を表す 3 つのビット を計算するという処理を行います。

result 0、1、2 3、4、5 6、7、8
b 6、7、8 3、4、5 0、1、2

上記の表の b の 3 つのビット は、b とその 3 つのビットだけを 1 とした ビットマスクとの AND 演算 で計算することができます。

b のビットの番号 ビットマスク 演算
0、1、2 0b000000111 b & 0b000000111
3、4、5 0b000111000 b & 0b000111000
6、7、8 0b111000000 b & 0b111000000

上記の表で計算した値を元に result を下記の手順で計算することができます。

result の 6、7、8 番 のビットのデータは、b の 0、1、2 番 のビットのデータで、ビットの番号 がそれぞれ 6 だけ増える ので、その処理は b の 0、1、2 番のビット に対する下記の 6 ビットの左シフト で まとめて計算 することができます。

(b & 0b000000111) << 6

下図は上記の式の計算を表す図です。上記の式で 紫色 の 0、1、2 番のビット が 6、7、8 番のビットに移動 した ビット列が計算 されることがわかります。

下記のプログラムのように、先に b を 6 ビット左シフトしてから 6、7、8 のビットのみを 1 とするビットマスクとの AND 演算を行っても同じ結果になります。なお、処理速度は上記の式と変わりません。

(b << 6) & 0b111000000

result の 3、4、5 番 のビットのデータは、b の 3、4、5 番 のビットのデータで ビットの番号は変わらない ので、下記の式で計算 できます。特に難しい点はないと思いますので図は省略します。

b & 0b000111000

result の 0、1、2 番 のビットのデータは、b の 6、7、8 番 のビットのデータで、ビットの番号 がそれぞれ 6 だけ減る ので、その処理は b の 6、7、8 番のビット に対する下記の 6 ビットの右シフト で計算することができます。

(b & 0b111000000) >> 6

ただし、b の 6 ビットの右シフト 演算によって b の 0 ~ 5 番のビット のデータは すべて捨てられる ので、b & 0b111000000 という計算は不要 です。そのため、上記の式は下図の b >> 6 のように簡略化 することができます。

従って、result は上記の 3 つの式の OR 演算 である下記の式で計算できます。

((b & 0b000000111) << 6) | (b & 0b000111000) | (b >> 6)

上記の 3 つの式の計算結果は、同じ番号のビットが 1 になることがないので加算を行った際に繰上りが発生することはありません。従って上記の式は下記の式のように + 演算子による加算でも計算することができますが、OR 演算で計算するほうが一般的だと思います。

((b & 0b000000111) << 6) + (b & 0b000111000) + (b >> 6)

fliplr2 の定義

下記は上記の手順で計算を行う fliplr2 の定義です。

def fliplr2(b):
    return ((b & 0b000000111) << 6) | (b & 0b000111000) | (b >> 6)

下記は b の左右反転 したビットボードを fliplr2 で計算 するプログラムで、fliplr2(b) == flipb が True になることから 正しい計算が行われる ことが確認できます。

print(f"0b{fliplr2(b):09b}")
print(fliplr2(b) == flipb)

実行結果

0b010100001
True

下記は fliplr2 の処理速度を計測 するプログラムです。実行結果から 列のデータをまとめて計算 することによって fliplr1 の処理時間の 620 ns と比較して 処理時間が 1/3 以下 になることが確認できました。

%timeit fliplr2(b)

実行結果

175 ns ± 1.38 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

delta swap を利用した計算方法

ビットマップの 左右を反転 するという処理は、0、1、2 番 のビットと 6、7、8 番 の ビットの内容を入れ替える という処理です。ビット列の中で 同じ間隔で並んだビットの組 を、高速に入れ替える delta swap という ビット演算 があるので紹介します。

参考までに delta swap の Chess Programming Wiki のページを下記に紹介します。

delta swap で利用する XOR 演算

delta swap は 1 ビットの値 である A、B に対して 以下の式が成り立つことを利用 するアルゴリズムです。

  • A ^ B ^ A = B
  • A ^ B ^ B = A

上記が成り立つことを証明 します。

1 ビットのデータ に対する XOR 演算 は 以下の性質 を持ちます。

  • XOR 演算は 順番を入れ替えても同じ計算結果 になるという 交換則 が成り立つ
  • 同じ値 に対する XOR 演算は 0 になる
  • 0 との XOR 演算 は 値が変わらない

交換則 とは、任意の数値 A、B に対して A + B = B + A のように 順番を入れ替えても計算結果が成り立つ ことを表す法則で、加算、乗算、AND 演算、OR 演算、XOR 演算 などで 成り立ちます が、任意の数値 A、B に対しては A - B = B - A は成り立たないので 減算 や 除算 の場合は 成り立ちません。

0 ^ 0 = 0、1 ^ 1 = 0 なので、同じ値に対する XOR 演算は 0 になります。

0 ^ 0 = 0、0 ^ 1 = 1 なので、0 との XOR 演算 は 値が変わりません。

上記の 2 つの性質から 1 ビットの値 である 任意の A と B に対して A ^ B ^ A = B が 下記の理由から成り立ちます。

　A ^ B ^ A
= A ^ A ^ B 　（交換則より）
= 0 ^ B　　　 （A ^ A = 0 より）
= B 　　　　　（0 ^ B = B より）

A ^ B ^ B = A は 下記の理由から成り立ちます。

　A ^ B ^ B
= B ^ A ^ B 　（交換則より）
= B ^ B ^ A 　（交換則より）
= 0 ^ A　　　 （B ^ B = 0 より）
= A 　　　　　（0 ^ A = A より）

ビット列 に対する XOR 演算 は 各ビットに対して上記の演算 が行われ、各ビットの演算結果 は 他のビットに影響を及ぼさない ので、任意のビット列 A、B に対しても 下記の式が成り立ちます。

  • A ^ B ^ A = B
  • A ^ B ^ B = A

下記はそのことを確認するプログラムです。

A = 7
B = 10

print(A ^ B ^ A)
print(A ^ B ^ B)

実行結果

10
7

また、この性質を利用することで、変数 A と B の値を交換する処理を、別の変数を用意することなく、下記のプログラムで計算することができます。

B = A ^ B  # B に 7 ^ 10 が代入される
A = B ^ A  # A に 7 ^ 10 ^ 7 = 10 が代入される
B = B ^ A  # B に 7 ^ 10 ^ 10 = 7 が代入される
print(A)
print(B)

なお、変数の値を交換する処理には以前の記事で説明したように、別の変数を用意する方法と、tuple の展開を利用する方法があります。

下記はそれぞれの処理速度を計測するプログラムで、実行結果から tuple の展開を利用する方法が最も高速であることが確認できます。なお、上記の方法の処理速度が最も遅い理由は、3 回の代入処理に加えて、3 回の XOR 演算が必要になるからです。従って Python では特別な理由がない限り変数の値を交換する際にこのアルゴリズムを無理に利用する必要はないと思います。

%%timeit
A = 7
B = 10
 
B = A ^ B
A = B ^ A
B = B ^ A

実行結果

73.8 ns ± 1.01 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

%%timeit
A = 7
B = 10
 
tmp = A
A = B
B = tmp

実行結果

25.9 ns ± 0.103 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

%%timeit
A = 7
B = 10
 
A, B = B, A

実行結果

21.9 ns ± 0.24 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

参考までにこのアルゴリズムの Wikipedia のリンクを下記に記します。

delta swap による 1 ビットの交換処理

ある ビット列 a の x 番と y 番 の ビットの値を交換した b の計算は、下記の delta swap のアルゴリズムを実装したプログラム で行うことができます。ただし、x > y であり、y 番のビットのみを 1 とした ビットマスクを mask とします。

delta = x - y
c = (a ^ (a >> delta)) & mask
b = c ^ (c << delta) ^ a

意味がわからない人が多いのではないかと思いますので、具体例 としてこの手順で a = 0b10010110 とし、5 番 のビットの 0 と 2 番 のビットの 1 を 入れ替えた b = 0b10110100 を計算 する場合の処理を説明します。

下記は 上記の手順 で a から b を計算 するプログラムで、実行結果から a の 5 番と 2 番のビットが入れ替わった b が正しく計算される ことが確認できます。なお、実行結果の 最初の行に表示した数値 は ビットの番号 を表します。

a = 0b10010110
x = 5
y = 2
mask = 0b00000100
delta = x - y
c = (a ^ (a >> delta)) & mask
b = c ^ (c << delta) ^ a
print("      76543210")
print(f"a = 0b{a:08b}")
print(f"b = 0b{b:08b}")

実行結果

      76543210
a = 0b10010110
b = 0b10110010

上記で 行われる処理 を 順番に図で解説 します。なお、上記の計算ではわかりやすさを重視して a、x、y に具体的な値を当てはめていますが、この計算手順によって 任意の a の x 番と y 番のビットを入れ替える ことができるので、以下の説明では a の x 番のビットの値を大文字の X、y 番のビットの値を大文字の Y のように表記 して 具体的な値を示さずに説明 することにします。

下図は 最初 の c = (a ^ (a >> delta)) & mask の 計算を表す図 です。図の ビットの色の意味 は 下記の表 の通りです。灰色 のビットの 値を気にする必要がない理由 については この後で説明 します。

色 意味
水色 a の x 番のビットの値である X と同じ になるビット
緑色 a の y 番のビットの値である Y と同じ になるビット
ピンク色 a の x 番と y 番のビットの XOR 演算である
X ^ Y と同じ になるビット
黄色 ビットマスクの y 番の値である 必ず 1 になる ビット
白色 必ず 0 になる ビット
灰色 この計算において 値を気にする必要がない ビット

delta = x - y は上図のように x と y の ビットの 番号の差 を表します。そのため a >> delta によって a の各ビットが delta だけ右シフトした結果、計算結果の y 番のビット の値は、上図のように a の x 番のビットの値 である X になります。

従って、a ^ (a >> delta) の y 番 のビットの値は Y ^ X になります。なお、交換則 から Y ^ X = X ^ Y なので、以下の説明ではこの計算結果の y 番のビットの値 を X ^ Y と表記 することにします。

最後に y 番のビットだけが 1 となる ビットマスクとの AND 演算 を行うことで、図のように c には y 番のビットに X ^ Y が、それ以外のビットに 0 が計算された値になります。図の 灰色のビットの値を気にする必要がない と説明した理由は、最後にこのビットマスクとの AND 演算を行った結果、灰色のビットの値 が c の値に影響を及ぼさないから です。

c = (a ^ (a >> delta)) & mask によって、y 番のビットが X ^ Y、それ以外のビットが 0 となるビット列 c が計算 される。

上図の例では c の y 番のビットが 1 となっているので常に X ^ Y = 1 になると思う人がいるかもしれませんが、X と Y の値によっては 0 になる場合がある点に注意して下さい。

下図は次の b = c ^ (c << delta) ^ a の 計算を表す図 です。

c << delta では c を delta だけ左シフト することで、上図のように x 番のビットだけ が紫色の X ^ Y に、それ以外のビットが 0 となる ビット列が計算 されます。

c ^ (c << delta) では 各ビット に対して 以下の表の XOR 演算 が行われます。

ビットの番号 c c << delta c ^ (c << delta)
x 0 X ^ Y 0 ^ X ^ Y = X ^ Y
y X ^ Y 0 X ^ Y ^ 0 = X ^ Y
それ以外 0 0 0 ^ 0 = 0

上記の表から下記の事がわかります。

c ^ (c << delta) によって、c の x 番と y 番のビットが X ^ Y、それ以外のビットが 0 となる ビット列が計算 される。

従って、b = c ^ (c << delta) ^ a では 各ビット に対して 以下の表の計算 が行われます。表から、b には a の x 番と y 番のビットの値が入れ替わったビット列が計算 されることがわかります。

ビットの番号 c ^ (c << delta) a b
x X ^ Y X X ^ Y ^ X = Y
y X ^ Y Y X ^ Y ^ Y = X
それ以外 0 a のビット 0 ^ a のビット
= a のビット

delta swap のアルゴリズムを言葉で説明すると以下のようになります。

  • x 番と y 番 のビットが X ^ Y、それ以外のビットが 0 となる ビット列を計算 する
  • その値と a の XOR 演算 を行うことで、X ^ Y ^ X = Y、X ^ Y ^ Y = X、0 ^ A = A という XOR 演算の性質 から a の x 番と y 番のビットが入れ替わったビット列が計算 される

delta swap の名前の由来は、delta が数学で差分を表す用語として良く使われており、delta swap が delta のだけ離れた（delta の差分の）ビットを入れ替える（swap）するという計算を行うことだと思います。

delta swap による複数のビットの交換処理

下記の条件を満たす場合 に、delta swap のアルゴリズム によって 複数のビットを交換したビット列を計算 することができます。

  1. 交換するビットの組の数 を $\boldsymbol{n}$（$n ≧ 1$）とする
  2. 交換するビットの組 を $\boldsymbol{x_i}$、$\boldsymbol{y_i}$（$\boldsymbol{0 ≦ i < n}$、$\boldsymbol{x_i > y_i}$）とする。ただし、交換するビットの番号 を表す $\boldsymbol{x_i}$ と $\boldsymbol{y_i}$ がすべて異なる ものとする
  3. すべての $\boldsymbol{i}$ に対して $\boldsymbol{x_i - y_i = delta}$ となる 整数 $\boldsymbol{delta}$ が存在する

条件 2 は、例えば「0 番と 2 番」、「2 番と 4 番」のような、交換するビットが被る ということが 起こらない という意味を表します。

条件 3 は、交換するビットどうしの間隔 が すべて等しい という意味を表します。

上記の条件が満たされている場合は、任意のビット列 a に対して上記の 条件 2 のビットの値を交換した b の計算 は、すべての $\boldsymbol{y_i}$ 番のビットを 1、それ以外のビットを 0 とした ビットマスク mask を計算 することで、先程の 1 ビットの delta swap による交換処理とまったく同じ下記の手順 で行うことができます。

c = (a ^ (a >> delta)) & mask
b = c ^ (c << delta) ^ a

$n = 1$ の場合は、先程説明した 1 ビットの delta swap のアルゴリズムと同じになることを確認して下さい。

具体例 として この手順で a = 0b10010110 に対して「7 番 と 3 番」、「5 番と 1 番」のビットを入れ替えた b = 0b00111100 を計算 する場合の処理で説明します。

delta swap の計算で必要となる delta と mask の値は以下のようになります。

  • $x_0 = 7$、$y_0 = 3$、$x_1 = 5$、$y_1 = 1$ である
  • 交換するビットどうしの間隔 である $\boldsymbol{delta} = x_0 - y_0 = x_1 - y_1 = \boldsymbol{4}$ である
  • mask は $y_0 = 3$、$y_1 = 1$ 番のビットのみが 1 となる 0b00001010 である

下記は delta swap のアルゴリズムで b を計算 するプログラムで、実行結果から 正しい値が計算される ことが確認できます。

a = 0b10010110
delta = 4
mask = 0b00001010
c = (a ^ (a >> delta)) & mask
b = c ^ (c << delta) ^ a
print("      76543210")
print(f"a = 0b{a:08b}")
print(f"b = 0b{b:08b}")

実行結果

      76543210
a = 0b10010110
b = 0b00111100

以下の説明では先程と同様に具体的な値ではなく、a の $\boldsymbol{x_0}$、$\boldsymbol{x_1}$、$\boldsymbol{y_0}$、$\boldsymbol{y_1}$ 番のビット の値をそれぞれ $\boldsymbol{X_0}$、$\boldsymbol{X_1}$、$\boldsymbol{Y_0}$、$\boldsymbol{Y_1}$ と表記 することにします。なお、先ほどの 条件 2 から $\boldsymbol{x_0}$、$\boldsymbol{x_1}$、$\boldsymbol{y_0}$、$\boldsymbol{y_1}$ の番号が 被ることはありません。

下図は最初の c = (a ^ (a >> delta)) & mask の計算を表す図です。図の ビットの色の意味は先ほどと同様 ですが、$\boldsymbol{X_1}$ の ビットの色 を $X_0$ のビットよりも 濃く塗りつぶす ことにしました。$\boldsymbol{Y_1}$、$\boldsymbol{X_1 \text{^} Y_1}$ のビットの 色についても同様 です。

行う計算は先ほどの 1 ビットの delta swapと同様 なので説明は省略しますが、上図から c には $\boldsymbol{y_0}$ 番 のビットが $\boldsymbol{X_0 \text{^} Y_0}$、$\boldsymbol{y_1}$ 番 のビットが $\boldsymbol{X_1 \text{^} Y_1}$、それ以外のビットが 0 となる ビット列が計算 されます。このことから、上記で行われる計算では 2 つの $\boldsymbol{y_0}$ と $\boldsymbol{y_1}$ 番のビット に対する 1 ビットの delta swap の 計算をまとめて行っている ことがわかります。

下図は次の b = c ^ (c << delta) ^ a の計算を表す図です。

行う計算は先ほどの 1 ビットの delta swap の場合と同様 なので説明は省略しますが、上図から b には「$x_0$ 番と $y_0$ 番」と「$x_1$ 番と $y_1$ 番」の ビットをまとめて入れ替える演算が行われる ことが確認できます。

また、上記の例では 2 組のビットの入れ替えの計算を行いましたが、3 組以上のビットの入れ替え の演算も同様の理由から 上記の手順で行うことができます。

fliplr3 の定義

3 x 3 のゲーム盤のビットボードの 左右の反転処理 は、下記の表から 0、1、2 番 と 6、7、8 番 のビットを 入れ替える という計算で行うことができます。なお、3、4、5 番 のビットは変化しないので 入れ替える必要はありません。

result 0、1、2 3、4、5 6、7、8
b 6、7、8 3、4、5 0、1、2

delta swap のアルゴリズムに必要となる delta と mask は以下のようになります。

  • $x_0 = 6$、$x_1 = 7$、$x_2 = 8$、$y_0 = 0$、$y_1 = 1$、$y_2 = 2$
  • $\boldsymbol{delta} = x_0 - y_0 = x_1 - y_1 = x_2 - y_2 = \boldsymbol{6}$
  • mask は $y_0、y_1、y_2$ のビットのみが 1 である 0b000000111

従って、fliplr3 は delta swap のアルゴリズムを利用した下記のプログラムで定義3することができます。

def fliplr3(b):
    c = (b ^ (b >> 6)) & 0b111
    return c ^ (c << 6) ^ b

下記は b の左右反転 したビットボードを fliplr3 で計算 するプログラムで fliplr3(b) == flipb が True になることから 正しい計算が行われる ことが確認できます。なお、先程 b に別の値を代入してしまったので、1 行目で b に 0b001100010 を代入しなおしました。

b = 0b001100010
print(f"0b{fliplr3(b):09b}")
print(fliplr3(b) == flipb)

実行結果

0b010100001
True

下記は fliplr3 の 処理速度を計測 するプログラムで、実行結果から fliplr2 の 約 175 ns よりも 処理速度が若干速くなる ことが確認できたので、本記事では delta swap を利用した左右反転の処理を採用 することにします。

%timeit fliplr3(b)

実行結果

162 ns ± 0.733 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

3 x 3 のビットボードの 転置処理

下図は 3 x 3 のビットボードの x 座標と y 座標を入れ替えて 転置 した図です。

上図から 左下の 〇 のビットボード である 0b010001100 を 転置 したビットボードが 0b001100010 になることがわかります。

この図から b = 0b010001100 のビットボードと、b を転置 した result の 各ビットの対応 は以下の表のようになることがわかります。

result 0 1 2 3 4 5 6 7 8
b 0 3 6 1 4 7 5 5 8

左右の反転の場合と同様 に 1 つずつビットを計算する方法 は 効率が悪く、列ごとに複数のビットをまとめて計算することもできない ので、delta swap を利用した処理方法を考える ことにします。その方法について少し考えてみて下さい。

delta swap は 間隔が等しい 場合は 複数のビットの組をまとめて入れ替える ことができます。そこで下記の表のように 入れ替えるビットの組 を 間隔ごとにまとめる ことにします。

間隔 入れ替えるビット
0（入れ替えない） 0、4、7
2 1 と 3、5 と 7
4 2 と 6

上記から下記の 2 種類の delta swap を行うことで ビットボードの転置 を計算することができることがわかります。

  • 「1 番 と 3 番」、「5 番と 7 番」のビットをまとめて入れ替える
    • $x_0 = 7$、$y_0 = 5$、$x_1 = 3$、$y_1 = 1$
    • $\boldsymbol{delta} = 7 - 5 = 3 - 1 = \boldsymbol{2}$
    • mask = 0b00100010
  • 「2 番 と 6 番」を入れ替える
    • $x= 6$、$y = 2$
    • $\boldsymbol{delta} = 6 - 2 = \boldsymbol{4}$
    • mask = 0b00000100

下記は 仮引数 b に代入された ビットボードの転置（transpose）を計算して返り値として返す 関数 transpose の定義 で、上記のパラメータ で 2 回の delta swap を行っています。

def transpose(b):
    # 「1 番 と 3 番」、「5 番と 7 番」の入れ替え
    c = (b ^ (b >> 2)) & 0b000100010
    b = c ^ (c << 2) ^ b
    # 「2 番 と 6 番」の入れ替え
    c = (b ^ (b >> 4)) & 0b000000100
    return c ^ (c << 4) ^ b

下記は先ほどの図の b = 0b010001100 のビットボードを 転置 したビットボードを transpose で計算 するプログラムで、実行結果から 0b001100010 が正しく計算される ことが確認できます。

b = 0b010001100
print("  876543210")
print(f"0b{b:09b}")
print(f"0b{transpose(b):09b}")

実行結果

  876543210
0b010001100
0b001100010

calc_same_hashables メソッドの定義

ビットボードの 左右の反転 と 転置 の計算ができるようになったので、calc_same_hashabels メソッドを定義 することにします。

関数呼び出しの処理時間

左右の反転 と 転置 の処理は 〇 と × の両方のビットボード に対して行う必要があるので、その処理を行う 関数を定義 したほうが プログラムの記述が簡潔 になりますが、関数呼び出しは処理時間がかかる という 欠点 があります。

例えば 1 に 1 を足す という処理を 1 + 1 で計算 する場合と、plus1 という 実引数に 1 を足した値を返す関数 を定義して計算する場合の 処理時間 を下記のプログラムで 比較する と 関数呼び出し のほうが 処理時間が長くなる ことが確認できます。

%timeit 1 + 1

実行結果

9.87 ns ± 0.0336 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

def plus1(a):
    return a + 1

%timeit plus1(1)

実行結果

50.5 ns ± 1.03 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

このようなことが起きる理由は、関数呼び出しでは実引数の値を仮引数に代入するなどの処理を行う必要があるからです。

そこで、calc_same_hashabels では delta swap の処理を行う関数を定義せずに、delta swap の処理をそのまま記述 することにします。

原則として同じ処理を行うプログラムを複数個所に記述しないほうが良いので、処理速度が重要でない場合は関数を定義することを強く勧めます。

calc_same_hashables メソッドの定義

List1dBoard クラスなどの calc_same_hashables のプログラムでは、下記のような処理 を行っていました。

  • 同一局面の一覧を記録 する hashables の初期化処理 で、最初の局面のハッシュ可能な値を記録 する
  • 最初の局面のデータ を boardorig に代入 して取っておき、同一局面の計算後に 最初の局面に戻す
  • その後で 3 回の回転、1 回の左右の反転、3 回の回転の 計 7 回の処理の結果 を hashables に記録 する

それに対し、BitBoard クラスの calc_same_hashabels の定義では下記のような工夫を行ないました。

  • hashables を 空の set（または dict）で初期化 する
  • board 属性の list の要素に代入 された 〇 と × のビットボード を circlebb と crossbb という 変数に代入 し、その変数に対して同一局面のビットボードを計算 することで以下のような利点が得られる
    • ゲーム盤のビットボードのデータを直接変更しない ので、最初の局面のデータ を boardorig を記録して後で戻す 処理を 削除することができる
    • list の要素 の 参照と代入 処理は、変数の参照と代入 処理 よりも遅いの で、list の要素に代入されたビットボードのデータに対して計算を行うよりも 処理速度が速くなる
  • 左右の反転と転置の処理を 4 回行い、それぞれの 計 8 回の処理の結果 を hashables に記録 する

下記は calc_same_hashabels の定義を行うプログラムです。

2 ~ 6 行目：同一局面のハッシュ可能な値を計算する hashables を空の set（または dict）で初期化する
8、9 行目：〇 と × のビットボードを circlebb と crossbb に代入する
10 ~ 37 行目：左右の反転と転置処理を繰り返し処理で 4 回行う
12 ~ 15 行目：〇 と × のビットボードが代入された circlebb と crossbb に対して左右の反転処理を delta_swap を利用して行う
16 行目：左右を反転した局面のハッシュ可能な値を計算する。board_to_hashabe を呼び出すと処理時間が長くなるので、ここで直接その計算を行うようにした
20 行目：左右の反転によって変化する x 座標の値を計算する。y 座標は変化しないので計算する必要はない
24 ~ 31 行目：〇 と × のビットボードに対して転置処理を 2 回の delta_swap で行う
36 行目：転置によって x 座標と y 座標が入れ替わるのでその処理を行う

 1  def calc_same_hashables(self, move=None):
 2      if move is None:
 3          hashables = set()
 4      else:
 5          hashables = {}
 6      if move is not None:
 7          x, y = self.move_to_xy(move)
 8      circlebb = self.board[0]
 9      crossbb = self.board[1]
10      for _ in range(4):
11          # 左右の反転処理
12          c = (circlebb ^ (circlebb >> 6)) & 0b111
13          circlebb = c ^ (c << 6) ^ circlebb        
14          c = (crossbb ^ (crossbb >> 6)) & 0b111
15          crossbb = c ^ (c << 6) ^ crossbb        
16          hashable = circlebb | (crossbb << self.bit_length) 
17          if move is None:
18              hashables.add(hashable)
19          else:
20              x = self.BOARD_SIZE - x - 1
21              hashables[hashable] = self.xy_to_move(x, y)
22  
23          # 転置処理
24          c = (circlebb ^ (circlebb >> 2)) & 0b100010
25          circlebb = c ^ (c << 2) ^ circlebb 
26          c = (circlebb ^ (circlebb >> 4)) & 0b100
27          circlebb = c ^ (c << 4) ^ circlebb 
28          c = (crossbb ^ (crossbb >> 2)) & 0b100010
29          crossbb = c ^ (c << 2) ^ crossbb 
30          c = (crossbb ^ (crossbb >> 4)) & 0b100
31          crossbb = c ^ (c << 4) ^ crossbb 
32          hashable = circlebb | (crossbb << self.bit_length) 
33          if move is None:
34              hashables.add(hashable)
35          else:
36              x, y = y, x
37              hashables[hashable] = self.xy_to_move(x, y)
38      return hashables
39  
40  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)
    circlebb = self.board[0]
    crossbb = self.board[1]
    for _ in range(4):
        # 左右の反転処理
        c = (circlebb ^ (circlebb >> 6)) & 0b111
        circlebb = c ^ (c << 6) ^ circlebb        
        c = (crossbb ^ (crossbb >> 6)) & 0b111
        crossbb = c ^ (c << 6) ^ crossbb        
        hashable = circlebb | (crossbb << self.bit_length) 
        if move is None:
            hashables.add(hashable)
        else:
            x = self.BOARD_SIZE - x - 1
            hashables[hashable] = self.xy_to_move(x, y)
            
        # 転置処理
        c = (circlebb ^ (circlebb >> 2)) & 0b100010
        circlebb = c ^ (c << 2) ^ circlebb 
        c = (circlebb ^ (circlebb >> 4)) & 0b100
        circlebb = c ^ (c << 4) ^ circlebb 
        c = (crossbb ^ (crossbb >> 2)) & 0b100010
        crossbb = c ^ (c << 2) ^ crossbb 
        c = (crossbb ^ (crossbb >> 4)) & 0b100
        crossbb = c ^ (c << 4) ^ crossbb 
        hashable = circlebb | (crossbb << self.bit_length) 
        if move is None:
            hashables.add(hashable)
        else:
            x, y = y, x
            hashables[hashable] = self.xy_to_move(x, y)
    return hashables

BitBoard.calc_same_hashables = calc_same_hashables

動作の確認

calc_same_hashabels は 下図の順で同一局面を計算 するので、下図の 左下の局面に対する calc_same_hashabels の 計算結果が下図のようになる ことを確認することにします。また、仮引数 move に (1, 0) の座標を代入 して計算を行うことにします。

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

1 ~ 5 行目：上図の左下の局面になるような着手を行い、move に BitBoard の (1, 0) の座標を計算する
6 行目：calc_same_hashabels を呼び出し、hashables に返り値を代入する
7 行目：hashabels には mb の同一局面のハッシュ可能な値をキーとし、キーの値にその同一局面の move に対応する値が代入された dict が代入されるので、それらを順番に取り出すという繰り返し処理を行う
8、9 行目：今回の記事で定義したboard_to_hashableでは、局面のハッシュ可能な値の 0 ~ 8 番のビットが 〇 の局面のビットボードの値を、9 ~ 17 番のビットが × の局面のビットボードを表すので、〇 の局面のビットボードは 0 ~ 8 番のビットを 1 とするビットマスクとの AND 演算で計算できる。また、× の局面のビットボードはハッシュ可能な値を右に 9 ビットシフトすることで計算できるので、その値を mb の board.board 属性に代入することで mb の局面をハッシュ可能な値の局面に変更する
10、11 行目：move を (x, y) の座標に変換した値と、mb の局面を表示することで、同一局面に対応する move の座標と同一局面を表示する

 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 & 0b111111111
 9      mb.board.board[1] = hashable >> 9
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 & 0b111111111
    mb.board.board[1] = hashable >> 9
    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.
...

上記の実行結果 に 下図の順番 で 同一局面の(1,　0) に対応する座標 と 同一局面が表示 され、最後に (1, 0) と左下の局面が表示 されることから、calc_same_hashables が正しい処理を行う ことが確認できました。

処理速度の比較

下記のプログラムで ListBoard、List1dBoard クラスの calc_same_hashabels メソッドの 処理速度と比較 することにします。

from marubatsu import ListBoard, List1dBoard

%timeit mb.board.calc_same_hashables(move)

mb2 = Marubatsu(boardclass=ListBoard)
mb2.cmove(0, 0)
mb2.cmove(1, 0)
mb2.cmove(2, 0)
mb2.cmove(0, 1)
move2 = mb2.board.xy_to_move(1, 0)

%timeit mb2.board.calc_same_hashables(move2)

mb3 = Marubatsu(boardclass=List1dBoard)
mb3.cmove(0, 0)
mb3.cmove(1, 0)
mb3.cmove(2, 0)
mb3.cmove(0, 1)
move3 = mb3.board.xy_to_move(1, 0)

%timeit mb3.board.calc_same_hashables(move3)

実行結果

5.33 μs ± 25.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
21.2 μs ± 226 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
8.16 μs ± 33.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

実行結果から、BitBoard クラスの calc_same_hashabels が 最も高速になる ことが確認できました。

benchmark の処理速度の比較

BitBoard クラスの 必要なメソッドがすべて実装 されたので、ai_abs_dls を実行できる ようになりました。そこで、下記のプログラムで benchmark を利用して List1dBoard クラスと BitBoard クラスの 処理速度を比較 することにします。

from util import benchmark

for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard]:
    for count_linemark in [False, True]:
        print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
        benchmark(mbparams={"boardclass": boardclass, "count_linemark": count_linemark})
        print()

実行結果

boardclass: List1dBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 21015.72it/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:31<00:00, 1597.11it/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
  9.0 ms ±   0.6 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

boardclass: List1dBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 16596.72it/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:18<00:00, 2637.44it/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
 10.2 ms ±   0.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

boardclass: BitBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 22457.83it/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, 3129.02it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

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

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

boardclass: BitBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 15449.72it/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:22<00:00, 2247.15it/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
  9.8 ms ±   0.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は 上記の実行結果をまとめた表 です。cl の列は count_linemark の値 を表します。表から BitBoard クラスで count_linemark が False の場合が、いずれの場合でも 処理速度が最も速い ことが確認できました。

boardclass cl ai2 VS ai2 ai14s VS ai2 ai_abs_dls
BitBoard False 22457.83 回/秒 3129.02 回/秒 7.9 ms
List1dBoard False 21015.20 回/秒 1597.04 回/秒 9.0 ms
BitBoard True 15449.72 回/秒 2247.15 回/秒 9.8 ms
List1dBoard True 19596.72 回/秒 2637.44 回/秒 10.2 ms

board_to_str メソッドの定義

board_to_str の定義を忘れていた ので、下記のプログラムのように定義することにします。board_to_str メソッドは AI の関数では利用されない ので 処理速度を気にする必要はありません。そのため、NpBoolBoard クラスの board_to_str と同じ定義 としました。

def board_to_str(self):
    txt = ""
    for x in range(self.BOARD_SIZE):
        for y in range(self.BOARD_SIZE):
            txt += self.MARK_TABLE[self.getmark(x, y)]
    return txt

BitBoard.board_to_str = board_to_str

今回の記事のまとめ

今回の記事では ビットボードで表現 されたゲーム盤の ハッシュ可能な値の計算方法 と、同一局面の一覧を計算 する様々な方法を紹介しました。また、その中で delta swap を利用した 高速な局面の反転と転置 を行う方法について紹介しました。

なお、今回の記事では紹介しませんでしたが、もっと大きなゲーム盤の場合は delta swap を利用したさらに効率の良いゲーム盤の反転と転置の処理方法があります。その方法については今後の記事で紹介する予定です。

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

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

次回の記事

更新日時 更新内容
2026/02/04 judge メソッドの修正方法の一部が間違っていたので修正しました

  1. 以前の同一局面を表す図ではマスに 1 ~ 9 までの数値を表記しましたが、今回の図では 0 ~ 8 までの数値座標を表記することにしました ↩

  2. numpy の同様の処理を行う np.fliplr と同じにしました ↩

  3. 0b000000111 は長いので 0b111 としました ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?