2
2

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を一から作成する　その212　ビット演算による合法手の一覧の計算

Posted at

目次と前回の記事

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_legal_moves メソッドの定義を行います。なお、話を簡単にするため、前回の記事に引き続き今回の記事でも 3 x 3 のサイズ のゲーム盤に対する 実装を行う ことにします。任意の大きさのゲーム盤に対する実装は今後の記事で紹介する予定です。

合法手の一覧の計算 は 様々な方法が考えられる ので、それらの方法を紹介して 処理速度を比較 することにします。

getmark を用いた実装

合法手の一覧 は マークが配置されていない マスの BitBoard の座標の一覧 なので、指定したマスの座標のマークを参照する getmark を利用した下記のプログラムで calc_legal_moves を定義することができます。

  • 4 ~ 7 行目：list 内包表記ですべてのマスの座標に対して下記の処理を行う
    • getmark を利用して (x, y) のマスが空のマスであるかを判定する
    • 空のマスの (x, y) の座標を xy_to_move で BitBoard の座標に変換した要素を持つ list を作成するようにする
 1  from marubatsu import BitBoard
 2  
 3  def calc_legal_moves(self):
 4      legal_moves = [self.xy_to_move(x, y) 
 5                          for y in range(self.BOARD_SIZE) 
 6                              for x in range(self.BOARD_SIZE)
 7                                  if self.getmark(x, y) == self.EMPTY]
 8      return legal_moves
 9  
10  BitBoard.calc_legal_moves = calc_legal_moves
行番号のないプログラム 
from marubatsu import BitBoard

def calc_legal_moves(self):
    legal_moves = [self.xy_to_move(x, y) 
                        for y in range(self.BOARD_SIZE) 
                            for x in range(self.BOARD_SIZE)
                                if self.getmark(x, y) == self.EMPTY]
    return legal_moves

BitBoard.calc_legal_moves = calc_legal_moves

上記の定義後に下記のプログラムで ゲーム開始時の局面 の 合法手の一覧を計算 すると、実行結果からすべてのマスが合法手として 正しく計算されることが確認 できます。なお、計算された 合法手の一覧 は BitBoard の座標でわかりづらいため、下記では move_to_xy を利用して (x, y) の座標として表示 しました。

bb = BitBoard()
legal_moves = bb.calc_legal_moves()
for move in legal_moves:
    print(bb.move_to_xy(move))

実行結果

(0, 0)
(1, 0)
(2, 0)
(0, 1)
(1, 1)
(2, 1)
(0, 2)
(1, 2)
(2, 2)

本記事では省略しますが、余裕と興味がある方はいくつかのマスに着手を行った場合の動作の確認を行ってみると良いでしょう。

上記の getmark を利用する方法 は わかりやすいという利点 がありますが、処理速度が遅い という 欠点 があります。下記は ゲーム開始時の局面 に対して List1dBoard と BitBoard クラスのそれぞれのインスタンスに対して calc_legal_moves の 処理時間を計測 するプログラムです。List1dBoard と比較した理由は、List1dBoard がこれまでに作成したゲーム盤のクラスの中で処理が最も高速だからです。

from marubatsu import List1dBoard

lb = List1dBoard()
%timeit lb.calc_legal_moves()
%timeit bb.calc_legal_moves()

実行結果

644 ns ± 6.25 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
4.07 μs ± 105 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

644 ns = 0.644 μs なので、実行結果から BitBoard クラスの calc_legal_moves のほうが 処理速度が約 6 倍も遅い ことがわかります。このような 差が生じる理由 は、以下の通りです。

List1dBoard クラスの calc_legal_moves メソッドは下記のプログラムのように board 属性に代入された list の要素の中 で、その値が self.EMPTY の要素 の インデックスを要素として持つ list を計算 するという、比較的単純な処理 を行います。

    def calc_legal_moves(self):
        legal_moves = [move for move in range(self.BOARD_SIZE ** 2) 
                            if self.board[move] == self.EMPTY]
        return legal_moves

それに対して BitBoard クラスの calc_legal_moves では以下のような、List1dBoard の場合と比較して 複雑な処理 を行うため 処理に時間がかかります。

  • getmark で (x, y) の座標のマークを参照 する
  • getmark では以下のような 多数の処理 が行われる
    • xy_to_move で (x, y) の座標を BitBoard の座標に変換する
    • getmark_by_move で 〇 と × のビットボードに対して指定した座標のマークを計算するという処理を行う
  • 空のマスの (x, y) の座標を xy_to_move で BitBoard の座標に変換 する

マークの配置を表すビットボードを計算する方法

上記のプログラムで呼び出される getmark_by_move では 配置されているマーク が 〇 であるか、× であるかを 区別する必要がある ので、下記のプログラムのように 最大で 〇 と × の 2 つのビットボード に対する AND 演算を行う必要 があります。

def getmark_by_move(self, move):
    if self.board[0] & move:
        return self.CIRCLE
    elif self.board[1] & move:
        return self.CROSS
    else:
        return self.EMPTY

一方、合法手であるかの判定 では、配置されている マークの種類を区別する必要はなく、マスに マークが配置されているかどうか の 判定で十分 です。そこで、マークが配置されているか どうかを 表すビットボードを計算 することで、1 つ の ビットボードに対する AND 演算 で 合法手であるかの判定 を行えるようにします。そのようなビットボードをどのように計算すればよいかについて少し考えてみて下さい。

マークの配置を表すビットボードの計算

その方法は、〇 と × の ビットボード に対して OR 演算 を行うというものです。OR 演算 は 各ビット に対して どちらかまたは両方が 1 の場合に 1 を計算 するという演算です。〇 と × のビットボードはいずれも 1 のビット が対応するマスに そのマークが配置されている ことを表すので、OR 演算 によって 各マス に いずれかのマークが配置されているか どうかを表す ビットボードが計算 されます。

下図は 上部の局面 の 〇 と × のビットボード の OR 演算の処理 を表す図で、OR 演算によって 水色 の 〇 の配置 を表すビットと 黄色 の × の配置 を表すビットが 1、残りのマークが 配置されていないビット が 0 の ビットボードが計算される ことから、マークの配置を表すビットボードが正しく計算 されることが確認できます。

for 文による処理速度の検証

BitBoard クラスの calc_legal_moves ではゲーム盤の各 (x, y) の座標を 2 重の for 文 による 繰り返し処理 で計算していますが、同じ処理 を List1dBoard クラスのように 整数 である 数値座標 を 1 つの for 文 による繰り返し処理で計算したほうが 処理速度が高速 になります。

下記は合計 9 回 の 繰り返し処理 を 1 つの for 文 で行った場合と、2 重の for 文 で行った場合の 処理時間を計測 するプログラムで、実行結果から 1 つの for 文 の方が 処理時間が約 3 倍も高速 になることが確認できます。これは、for 文そのものの処理 に 時間がかかる からです。なお、for 文だけ の 処理時間を計測 するために、for 文のブロック では 何も処理を行わない ことを表す pass を記述 しました。

%%timeit

for i in range(9):
    pass

実行結果

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

%%timeit
for x in range(3):
    for y in range(3):
        pass

実行結果

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

これまでに何度も説明したように、処理速度が重要でない場合はわかりやすさを重視したプログラムを記述することが重要です。2 重の for 文で記述したほうがわかりやすい場合は、無理に 1 つの for 文で記述するようにプログラムを修正しないほうが良いでしょう。

calc_legal_moves の実装

下記は、マークの配置を表すビットボード を計算し、数値座標 を 1 つの for 文 による繰り返し処理によって 計算する ように calc_legal_moves を定義したプログラムです。行う処理は List1dBoard クラスと似ているので、修正箇所は List1dBoard クラスとの違を示しました。

  • 2 行目：〇 と × のビットボードの OR 演算を行うことで、マークの配置を表すビットボードを計算して borad に代入する
  • 3、4 行目：List1dBoard クラスと同様に list 内包表記では 1 つの for 文で数値座標に対する繰り返し処理を行う。list 内包表記の繰り返し処理では下記の処理を行う
    • 数値座標 である i を 1 << i によって BitBoard の座標に変換 する
    • AND 演算 で BitBoard の座標 である 1 << i のビットの値を計算 し、空のマス であることを表す 0 の場合 に 1 << i を要素に追加 するという処理を行う
1  def calc_legal_moves(self):
2      board = self.board[0] | self.board[1]
3      legal_moves = [1 << i for i in range(self.BOARD_SIZE ** 2) 
4                     if board & (1 << i) == 0]
5      return legal_moves
6  
7  BitBoard.calc_legal_moves = calc_legal_moves
行番号のないプログラム 
def calc_legal_moves(self):
    board = self.board[0] | self.board[1]
    legal_moves = [1 << i for i in range(self.BOARD_SIZE ** 2) 
                   if board & (1 << i) == 0]
    return legal_moves

BitBoard.calc_legal_moves = calc_legal_moves
修正箇所 
def calc_legal_moves(self):
    board = self.board[0] | self.board[1]
-   legal_moves = [move for i in range(self.BOARD_SIZE ** 2) 
-                  if self.board[move] == self.EMPTY]
+   legal_moves = [1 << i for i in range(self.BOARD_SIZE ** 2) 
+                  if board & (1 << i) == 0]
    return legal_moves

BitBoard.calc_legal_moves = calc_legal_moves

上記の定義後に先程と同じ下記のプログラムで ゲーム開始時の局面 の 合法手の一覧を計算 すると、実行結果から 正しい計算が行われることが確認 できます。

legal_moves = bb.calc_legal_moves()
for move in legal_moves:
    print(bb.move_to_xy(move))

実行結果

(0, 0)
(1, 0)
(2, 0)
(0, 1)
(1, 1)
(2, 1)
(0, 2)
(1, 2)
(2, 2)

また、下記のプログラムで calc_legal_moves の処理時間を計測 すると、実行結果から修正前の 4.07 μs と比較して 処理速度が約 3 倍 になったことが確認できます。ただし、それでも List1dBoard クラスの場合の 0.644 μs よりは遅い ようです。

%timeit bb.calc_legal_moves()

実行結果

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

BitBoard の座標の計算の重複の解消

先程定義したプログラムでは、list 内包表記の中 に BitBoard の座標を計算 する 1 << i が 2 回記述 されているため、同じ計算処理を 2 回行う という 無駄があります。list 内包表記で記述 する場合は、どうしても このように表記する必要 があります1が、下記のプログラムのように list 内包表記を利用せず に 同様の処理を記述 することで、この 重複する処理 を 1 回だけで済ます ことができます。

下記の 3 ~ 7 行目 のプログラムは 先程の list 内包表記と同じ処理を行う プログラムです。以前の記事で説明したように、list 内包表記 は list の append メソッドで記述したプログラムを 簡潔に記述するための表記 です。また、list 内包表記 で 要素の追加の条件を if 文で記述 する方法について忘れた方は以前の記事を復習して下さい。

先ほどの list 内包表記 で行っていた 処理との違い は、5 行目 で move という変数に BitBoard の座標 である 1 << i を計算して代入 しておき、その値を利用 して 6 行目の AND 演算 と、7 行目の list への要素の追加 を行っている点で、そのようにすることで BitBoard の座標の計算 を 1 回で済ます ことができます。

 1  def calc_legal_moves(self):
 2      board = self.board[0] | self.board[1]
 3      legal_moves = []
 4      for i in range(self.BOARD_SIZE ** 2):
 5          move = 1 << i
 6          if board & move == 0:
 7              legal_moves.append(move)
 8      return legal_moves
 9  
10  BitBoard.calc_legal_moves = calc_legal_moves
行番号のないプログラム 
def calc_legal_moves(self):
    board = self.board[0] | self.board[1]
    legal_moves = []
    for i in range(self.BOARD_SIZE ** 2):
        move = 1 << i
        if board & move == 0:
            legal_moves.append(move)
    return legal_moves

BitBoard.calc_legal_moves = calc_legal_moves

上記の定義後に先程と同じ下記のプログラムで ゲーム開始時の局面 の 合法手の一覧を計算 すると、実行結果から 正しい計算が行われることが確認 できます。

legal_moves = bb.calc_legal_moves()
for move in legal_moves:
    print(bb.move_to_xy(move))

実行結果

(0, 0)
(1, 0)
(2, 0)
(0, 1)
(1, 1)
(2, 1)
(0, 2)
(1, 2)
(2, 2)

また、下記のプログラムで calc_legal_moves の処理時間を計測 すると、実行結果から修正前の 1.23 μs と比較して 処理速度が少し高速 になったことが確認できます。ただし、依然として List1dBoard クラスの場合の 0.644 μs よりは遅い ようです。

%timeit bb.calc_legal_moves()

実行結果

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

list 内包表記の処理速度に関する補足

list 内包表記 は処理を簡潔に記述する以外にも、同じ処理を list の append メソッドで行う場合よりも 処理速度が高速になる という 利点 があります。そのため、そのことを知っている人は上記のようにプログラムを修正したことで処理速度が向上した点に疑問を持つ人がいるかもしれませんので、その点について補足します。

下記は 0 ~ 9 の要素を持つ list の作成 を list 内包表記 と list のappend メソッドで行う場合の 処理速度を計測 するプログラムで、実行結果から list 内包表記 のほうが 処理速度が高速 であることが確認できます。

%timeit [i for i in range(10)]

実行結果

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

%%timeit

a = []
for i in range(10):
    a.append(i)

実行結果

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

ただし、list 内包表記の中 で if を利用 して 追加する要素の条件を記述 した場合は、処理速度に大きな差は生じなくなる ようです。下記は 0 ~ 9 の中の 偶数の要素 を持つ list の作成 を 内部に if を記述した list 内包表記 と list のappend メソッドで行う場合の 処理速度を計測 するプログラムで、実行結果から 処理速度が大きくは変わらない ことが確認できます。

なお、% は 余りを計算する演算子 で、i % 2 == 0 は 2 で割った余りが 0 であることによって 偶数であることを判定 します。

%timeit [i for i in range(10) if i % 2 == 0]

実行結果

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

%%timeit

a = []
for i in range(10):
    if i % 2 == 0:
        a.append(i)

実行結果

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

このことから、先程の修正で list 内包表記をやめて list の append メソッドを利用 するようにしたことによる 処理速度の低下はほとんどおきず、1 << i という処理を 2 回から 1 回に減らすことで処理速度が向上 したことがわかります。

not 演算による高速化

上記では if board & move == 0: という if 文の 条件式 で マークが存在しないことを判定 していましたが、int 型 のデータが 0 であるか どうかの 判定 は、== 演算子よりも not 演算子 を利用したほうが 処理が高速 になります。

int 型のデータに対する not 演算子の処理

not 演算子 は int 型 のデータに対して 0 であれば True を、0 以外の整数 であれば False を計算 する演算子です。

下記は 0、1、2 に対して not 演算子 で計算を行った結果を表示するプログラムで、実行結果から 0 の場合のみ True が計算 されることが確認できます。

print(not 0)
print(not 1)
print(not 2)

実行結果

True
False
False

not 演算子 の詳細については下記のリンク先を参照して下さい。

not 演算子 による演算は ビット演算ではなく、計算結果 は bool 型の True または False になる点に注意して下さい。本記事では ビット演算 の NOT 演算を 大文字 で NOT 演算 のように記述することで not 演算子による演算と区別 しています。また、ビット演算の NOT 演算 は ~ という演算子です。

not 演算子の処理速度の検証

下記は a == 0 と not a の 処理速度を計測 するプログラムで、実行結果から a が 0 であるかどうかの判定 は not 演算子のほうが高速に行える ことが確認できます。

a = 0
%timeit a == 0
%timeit not a

実行結果

23 ns ± 0.125 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
17.5 ns ± 0.0268 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

calc_legal_moves の修正

下記は not 演算子を利用 するように calc_legal_moves の 6 行目を修正 したプログラムです。

 1  def calc_legal_moves(self):
 2      board = self.board[0] | self.board[1]
 3      legal_moves = []
 4      for i in range(self.BOARD_SIZE ** 2):
 5          move = 1 << i
 6          if not (board & move):
 7              legal_moves.append(move)
 8      return legal_moves
 9  
10  BitBoard.calc_legal_moves = calc_legal_moves
行番号のないプログラム 
def calc_legal_moves(self):
    board = self.board[0] | self.board[1]
    legal_moves = []
    for i in range(self.BOARD_SIZE ** 2):
        move = 1 << i
        if not (board & move):
            legal_moves.append(move)
    return legal_moves

BitBoard.calc_legal_moves = calc_legal_moves
修正箇所 
def calc_legal_moves(self):
    board = self.board[0] | self.board[1]
    legal_moves = []
    for i in range(self.BOARD_SIZE ** 2):
        move = 1 << i
-       if board & move == 0:
+       if not (board & move):
            legal_moves.append(move)
    return legal_moves

BitBoard.calc_legal_moves = calc_legal_moves

not (board & move) のように記述すると not が関数のように見えるかもしれませんが、関数ではなく演算子である点に注意して下さい。本記事では関数呼び出しと区別するために not の後に空白を入れています。

not (board & move) の () は関数呼び出しの () ではなく、not 演算子による演算よりも board & move を優先して先に行うことを表します。

上記の修正後に先程と同じ下記のプログラムで ゲーム開始時の局面 の 合法手の一覧を計算 すると、実行結果から 正しい計算が行われることが確認 できます。

legal_moves = bb.calc_legal_moves()
for move in legal_moves:
    print(bb.move_to_xy(move))

実行結果

(0, 0)
(1, 0)
(2, 0)
(0, 1)
(1, 1)
(2, 1)
(0, 2)
(1, 2)
(2, 2)

また、下記のプログラムで calc_legal_moves の処理時間を計測 すると、実行結果から修正前の 0.994 μs と比較して 処理速度が少し高速 になったことが確認できます。ただし、依然として List1dBoard クラスの場合の 0.644 μs よりは遅い ようです。

%timeit bb.calc_legal_moves()

実行結果

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

合法手の数による処理速度の比較

先程処理速度を計測 した calc_legal_moves は、マークが一つも配置されていない ゲーム開始時の 局面での計算 でしたが、合法手 は 着手を行うたびに減る ので、マークが配置された局面 での 処理速度も比較したほうが良い でしょう。下記は List1dBoard と BitBoard のインスタンスに対して、マークを 1 つずつ配置した局面 に対して calc_legal_moves の処理速度を計測 するプログラムです。

  • 3 ~ 9 行目：2 重の for 文によってゲーム盤の各マスについての繰り返し処理を行う。なお、処理が行われるマスの順番は数値座標の 0 ~ 8 の順である
  • 5 行目：(x, y) のマスの 数値座標を表示 することで、マークが配置されたマスの数を表示 する。なお、繰り返し処理の中で、マークを配置する処理 を calc_legal_moves の 処理速度を計測する後 に行うことで、数値座標の数値 が 配置されたマークの数を表す ように工夫した
  • 6、7 行目：BitBoard クラスと List1dBoard クラスの calc_legal_moves の処理速度を計測する
  • 8、9 行目：BitBoard クラスと List1dBoard クラスのインスタンスに対して、(x, y) のマスに 〇 を配置 する。なお、calc_legal_moves が行う処理は、マスに配置されるマークの種類は問わない ので、プログラムを簡潔に記述できる という理由から実際の 〇× ゲームのルールとは異なり どのマスにも 〇 を配置 することにした
1  bb = BitBoard()
2  lb = List1dBoard()
3  for x in range(bb.BOARD_SIZE):
4      for y in range(bb.BOARD_SIZE):
5          print(y + x * bb.BOARD_SIZE)
6          %timeit bb.calc_legal_moves()
7          %timeit lb.calc_legal_moves()
8          bb.setmark(x, y, bb.CIRCLE)
9          lb.setmark(x, y, lb.CIRCLE)
行番号のないプログラム 
bb = BitBoard()
lb = List1dBoard()
for x in range(bb.BOARD_SIZE):
    for y in range(bb.BOARD_SIZE):
        print(y + x * bb.BOARD_SIZE)
        %timeit bb.calc_legal_moves()
        %timeit lb.calc_legal_moves()
        bb.setmark(x, y, bb.CIRCLE)
        lb.setmark(x, y, lb.CIRCLE)

実行結果

0
914 ns ± 7.79 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
653 ns ± 4.84 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1
887 ns ± 1.81 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
602 ns ± 2.43 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
2
881 ns ± 3.57 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
618 ns ± 12 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
3
870 ns ± 2.14 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
616 ns ± 9.93 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
4
844 ns ± 1.72 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
608 ns ± 5.48 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
5
809 ns ± 7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
580 ns ± 1.29 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
6
794 ns ± 1.63 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
577 ns ± 2.87 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
7
775 ns ± 1.38 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
574 ns ± 1.69 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
8
754 ns ± 9.45 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
580 ns ± 10.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は上記の実行結果をまとめた表で、以下の事が確認できました。

  • いずれの場合も List1dBoard クラスの方が 処理速度が速い
  • 合法手の数が少ない ほど、処理速度が速くなる
配置されたマークの数 BitBoard List1dBoard
0 914 ns 653 ns
1 887 ns 602 ns
2 881 ns 618 ns
3 870 ns 616 ns
4 844 ns 608 ns
5 809 ns 580 ns
6 794 ns 577 ns
7 775 ns 574 ns
8 754 ns 580 ns

ビット演算を利用した処理速度の高速化の手法

これまでに紹介した方法 では BitBoard クラスのほうが List1dBoard クラスの場合よりも 処理速度が遅い という残念な結果になりますが、ビット演算を利用 することで List1dBoard クラスより も 高速に処理を行う ことができます。

これまでの calc_legal_moves では 0 番から 8 番までの 9 つのビットが 0 であるか を 1 つずつ判定する という処理を行うため、必ず 9 個すべてのビット について 判定処理を行う必要 がありました。

それに対して、ビット演算を利用 することで 0 であるビットの数だけ 繰り返し処理を行うことで 合法手の一覧を求める ことができます。例えば 合法手が 5 つの局面 では 5 回の繰り返し処理 だけで 合法手の一覧を計算 することができるので、合法手の数が少ない程 これまでの手法と比べて 処理速度が高速 になります。

用語の説明

アルゴリズムの説明を行う前に、説明で用いるいくつかの用語 について説明します。

ビット列の中で、1 である最下位（最も番号が小さい）のビット のことを right most set bit（最も右にある 1 にセットされたビット）2と呼びます。本記事ではその頭文字を取って RSB と表記 することにします。

ビット列 の RSB のビットのみを 1 とする値を lowest one bit3と呼ぶので本記事ではその頭文字を取って LOB と表記 することにします。

例えば 0b110101000 の場合は RSB は 3 番のビット で、LOB は RSB である 3 番のビットのみが 1 である 0b1000 となります。

アルゴリズムの説明

calc_legal_moves が行いたい処理は、マークの配置を表すビットボード の中の、0 のビットの一覧を計算 する処理です。例えば、0b001010110 というビットボードの場合は、0 であるビット は 0、3、5、7、8 番のビットで、それらのビットだけを 1 とした下記の表の BitBoard の座標を計算 することが目的となります。

0 のビットの番号 対応する BitBoard の座標
0 0b000000001
3 0b000001000
5 0b000100000
7 0b010000000
8 0b100000000

上記の処理は、元のビットボード の 0 と 1 を反転 した 0b110101001 というビットボードに対して、1 のビットの一覧を計算 する 処理と同じ です。

下記は比較できるように 2 つのビットボードを並べた表 で、0、3、5、7、8 番の ビットが 1 になる ことが確認できます。

ビットボード
元のビットボード 0b001010110
0 と 1 を反転したビットボード 0b110101001

0 と 1 を反転したビットボードを計算した理由は、ビット演算を利用 することで、ビットの LOB（1 である最下位ビットのみを 1 とする値）を 高速に計算 できるからです。LOB の計算方法は後述しますが、LOB を計算 することで下記のアルゴリズムで 合法手の一覧 を、合法手の数だけの繰り返し処理で計算 することができます。

  1. ビットボードの 0 と 1 を反転 した値を計算し、board という変数に代入する。board は 1 であるビット が対応するマスの座標が、マークが配置されていない合法手 であることを表す
  2. board の LOB を計算 する。計算した LOB は マークが配置されていない BitBoard の座標 を表すので 合法手の一覧に加える
  3. board の RSB4のビットを 0 にすることで、board から 合法手の一覧に加えた BitBoard の座標 を表す データを取り除く
  4. board が 0 になった時点で、すべての合法手を登録した ことになるので 処理を終了 する
  5. board が 0 でない 場合は 手順 2 に戻って 次の合法手を計算 する

下記は上記のアルゴリズムで 0b01010110 の ビットボードの合法手を計算 した場合に 行われる処理を表した表 です。最後の手順 3 で board の値が 0 になる ことで 処理が終了 し、新たに計算した合法手の一覧の列 から、5 つの合法手が正しく計算された ことが確認できます。また、下記の処理では 手順 2 と 3 の処理 が、合法手の数である 5 回だけ繰り返された ことも確認できます。

手順 board の値 新たに計算した合法手
1 0b110101001
2 0b110101001 0b00000001
3 0b110101000
2 0b110101000 0b00001000
3 0b110100000
2 0b110100000 0b00100000
3 0b110000000
2 0b110000000 0b01000000
3 0b100000000
2 0b100000000 0b10000000
3 0b000000000

上記の表が示す処理の手順からわかるように、このアルゴリズムは LOB を計算 することで マークが配置されているビット の計算を 飛ばし、マークが配置されていないビットだけを計算 するという処理が行われています。

次に、手順 1、2、3 の処理を行う方法について説明します。

ビットボードの 0 と 1 を反転するビット演算

手順 1 の ビットボードの 0 と 1 を反転 する処理は、~ 演算子による NOT 演算を行えば良いと思うかもしれませんが、そのような計算を 0b01010110 に対して行うと 9 番以降のビットがすべて 1 となる 0b・・・11110101001 という、・・・の部分に無限に 1 が続く ような値5が計算されてしまうので、先程のアルゴリズムの 手順 3 の処理を行った後で board が 0 になることがない ため、無限ループが発生してしまう という問題があります。

そこで、本記事ではビットボードの ゲーム盤の マスの座標を表す 0 ~ 8 番 のビットだけ に対して 0 と 1 を反転する 処理を行い、ゲーム盤の マスの座標を表さない 9 番以降のビットがすべて 0 となるような 値を計算 することにします。具体的には先ほどの例のように、0b01010110 に対して 0b110101001 を計算 します。

そのような処理は、ビットボードを bb、ゲーム盤の マスの座標を表す 0 から 8 番までのビットが 1 である 0b111111111 を mask と表記した場合に、以下の いずれかの方法 で行うことができます。なお、0b111111111 を mask と表記した理由 は、その値が 前回の記事で説明した、0 ~ 8 番というマスの座標を表す 特定のビットだけに注目 して 計算を行うため に用いられる マスクデータ だからです。

  • bb ^ mask という XOR 演算 を行う。以下の理由から ビットボードの 0 から 8 番までの 0 と 1 が反転 し、9 番以降のビットが 0 である値が計算される
    • 0 と 1 の XOR 演算は 1 に、1 と 1 の XOR 演算は 0 になるので 0 から 8 番 までの ビットボードの 0 と 1 が反転 する
    • 9 番以降のビット は 両方とも 0 であり、0 と 0 の XOR 演算は 0 になるので、9 番以降のビットはすべて 0 になる
  • mask - bb という 引き算（減算） を行う。以下の理由から ビットボードの 0 から 8 番までの 0 と 1 が反転 し、9 番以降のビットが 0 である値が計算される
    • 1 - 0 = 1、1 - 1 = 0 なので、0 から 8 番 までの ビットボードの 0 と 1 が反転 する
    • 9 番以降のビット は 両方とも 0 であり、0 - 0 = 0 なので 9 番以降のビットはすべて 0 になる

下記はそのことを示すプログラムで、どちらも正しい値が計算される ことが確認できます。なお、bin は整数を 2 進数のリテラルで表示するための組み込み関数です。

bb = 0b01010110
mask = 0b111111111
print(bin(bb ^ mask))
print(bin(mask - bb))

実行結果

0b110101001
0b110101001

下記は 両者の処理時間を計測 するプログラムで、実行結果から 引き算 のほうが 少しだけ処理速度が高速 であることが確認できます。また、おそらく多くの方にとっては 引き算のほうがわかりやすい のではないかと思いますので、本記事では 引き算の方を採用 することにします。

%timeit bb ^ mask
%timeit mask - bb

実行結果

40.4 ns ± 0.137 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
34.2 ns ± 0.145 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

LOB を計算するビット演算

手順 2 の a の LOB の計算は、a & (-a) という AND 演算 によって計算できます。例えば、下記のプログラムのように a = 0b110100000 の LOB は a & (-a) によって 0b000100000 が正しく計算される ことが確認できます。

a = 0b110100000
print(f"a        = {a:09b}")
print(f"a & (-a) = {a & (-a):09b}")

実行結果

a        = 110100000
a & (-a) = 000100000

& 演算子よりも負の符号を表す - 演算子のほうが優先順位が高いので () を省略してa & -a のように記述しても同じ処理が行われますが、本記事ではわかりやすさを重視して a & (-a) のように記述することにします。

a & (-a) という式で a の LOB が計算できる ということは、ほとんどの人には意味不明 だと思いますので、その 理由について説明 します。

以前の記事で説明したように、0 と 1 のビットを反転 する ~ 演算子 による NOT 演算 によって ~a = -(a + 1) という計算が行われます。この式から、~a = -a - 1 となるので、-a = ~a + 1 という 式で計算できる ことがわかります。

そのことを踏まえて、a = 0b110100000 に対する a & (-a) の計算 を 図で説明 します。なお、上記の場合 は a の RSB（1 である最下位のビット）の 番号は 5 ですが、下記の説明は RSB の番号 が 0 ~ 8 の任意の番号でも成り立ちます。

下図は -a = ~a + 1 によって 行われる計算 を説明する図で 上部に a のビット列を図示 しています。・・・0 は 9 番以降のビット に 0 が無限に並ぶ ことを表します。・・・1 についても同様です。

a の RSB のビット はその定義から 必ず 1 になり、RSB より小さい番号 のビットは 必ず 0 になります。また、a がビットボードを表す場合 は、ゲーム盤の数値座標は 0 ~ 8 までなので 9 番以降のビットはすべて 0 になります。

そこで、図では a の RSB のビット の性質 から 必ず 1 となるビット を 黄色 で、必ず 0 となるビット を 白色 で塗りつぶすことにしました。なお、8 番まで の a の RSB より大きい ビット のように、0 と 1 のどちらでもかまわない ビットは 0 を緑色 で、1 を水色 で塗りつぶすことにしました。

下記は それぞれの色の意味 を表す表です。

色 意味
白 a の RSB の性質から 必ず 0 となるビット
黄色 a の RSB の性質から 必ず 1 となるビット
緑色 a の RSB の性質から 0 と 1 のどちらでも良い が、図では 0 としたビット
水色 a の RSB の性質から 0 と 1 のどちらでも良い が、図では 1 としたビット

下図は先ほどの図の再掲です。a の下 には ~a と 整数の 1 を表す 2 進数のビット列 を図示しました。~a は a のすべてのビットの 0 と 1 を反転 したものです。

その下には ~a + 1 の 各ビットの計算式 と、計算結果 を表す 2 進数のビット列 を図示しました。各ビットの計算式の ビットを表す数字の背景色 は、計算する ビットの色と対応 しています。また、繰上りを表す 1 を 赤色 で表示しました。

以下では a の RSB のビットの番号 を rsb と表記 することにします。また、下記は図と同じ rsb > 0 の場合 の説明です。rsb = 0 の場合については後述 します。

rsb > 0 の場合は、図からわかるように、~a と 整数の 1 の 0 番のビット は 両方とも 1 になるので、~a + 1 の 0 番のビット に対しては 2 進数の 1 + 1 = 10 が計算され、~a + 1 の 0 番のビット は 必ず 0 になります。また、繰上り6 によって 次の 1 番のビットを計算 する際には 1 が追加で加算 されます。

1 ~ rsb - 1 番のビット は 必ず 1 と 0 になり、繰上りが発生 しているため 2 進数の 1 + 0 + 1 = 10 が計算 されます。従って、~a + 1 のそれらのビット は 必ず 0 になり、繰上りが発生 します。

rsb 番のビット は 必ず 0 と 0 になり、繰上りが発生 しているため 2 進数の 0 + 0 + 1 = 1 が計算 されます。従って、~a + 1 の RSB のビット は 必ず 1 になり、繰上りは発生しません。

rsb + 1 ~ 8 番のビット は ~a のビットの値 と 0 になり、繰上りは発生していない ため ~a のビット + 0 = ~a のビット が計算されます。従って、~a + 1 それらのビット は ~a のビットと同じ になり、繰上りは発生しません。

9 番以降のビット は 必ず 1 と 0 になり、繰上りは発生していない ため 2 進数の 1 + 0 = 1 が計算 されます。従って、~a + 1 の 9 番以降のビット は すべて ~a のビットの値と同じ 1 になります。

なお、rsb = 0 の場合 は、RSB である 0 番のビットは 0 と 1 となり、繰上りは発生していない ので 2 進数の 0 + 1 = 1 が計算 されるので、上記で説明した rsb 番のビットと同じ計算 が行われます。

下記は 上記を表にまとめ たものです。

ビットの番号 -a = ~a + 1 のビットの値
rsb 未満 0
rsb 1
rsb + 1 以上 ~a のビットと同じ

下記は上記の表に a のビットと a & (-a) の 計算結果を加えた ものです。AND 演算 は 両方とも 1 の場合のみ 1 を計算 する ビット演算 なので、rsb 未満のビット は 0 & 0 = 0、rsb のビット は 1 & 1 = 1 が計算 されます。rsb + 1 以上 のビットは a のビット と ~a のビット の AND 演算 が行われますが、~a のビット は a のビットの 0 と 1 を反転 した値なので、0 & 1 = 0 または 1 & 0 = 0 の いずれかが計算 されるため、必ず 0 が計算 されます。

ビットの番号 -a a a & (-a)
rsb 未満 0 0 0
rsb 1 1 1
rsb + 1 以上 ~a のビット a のビット 0

上記の表から a & (-a) の計算結果は、a の RSB のビットのみが 1 となる a の LOB が計算 されることが確認できました。

以前の記事で説明した、b の特定のビットのみを 0 にする b &= ~0 ^ (1 << x) というビット演算と 同様 に、LOB を計算するビット演算 も 一見しただけでは何を計算しているかがまったくわからない式 になるので、間違えやすい点に注意 して下さい。

a の RSB のビットを 0 にする計算

手順 3 の a の RSB のビットを 0 にする処理 は、a の LOB を lob と表記 した場合に、先程説明した ビットボードの 0 と 1 を反転する処理と同様の理由 で 以下のいずれかの方法で計算 を行うことができます。ピンとこない方は図を描いてみると良いでしょう。本記事では先ほどと同様に 引き算の方を採用 することにします。

  • a ^ lob という XOR 演算 で計算する
  • a - lob という 引き算 で計算する

lob = a & (-a) なので、上記の式は a ^ (a & (-a)) という式 になりますが、LOB の値が必要でない場合 は、a & (a - 1) という より簡潔なビット演算 で a の RSB のビットを 0 にする計算 を行うことができます。その理由についてはこの後で簡単に説明します。

なお、先程のアルゴリズムでは 合法手を表す LOB を計算する必要 があり、LOB を計算した場合 は XOR 演算 または 引き算 で計算したほうが 処理が高速 なので、本記事では a & (a - 1) という式は 利用しません。

a & (a - 1) というビット演算で a の RSB のビットを 0 にする計算 が 行われる理由 について簡単に説明します。

10 進数の 10000 - 1 で 繰り下がり によって 9999 が計算される のと同様に、2 進数の 10000 - 1 でも 繰り下がり によって 1111 が計算 されます。そのため、2 進数から 1 を引く と RSB のビットが 0、RSB 未満の番号のビットが 1 になります。また、RSB より大きな番号のビット は繰り下がりの影響を受けないので元のまま 変化しない という計算が行われます。わかりづらいと思った方は図を描いて確かめて下さい。

従って、a - 1 によって下記の表の a - 1 の列の計算が行われます。また、a の列から a & (a - 1) を計算すると、計算結果は下記の表のように RSB 未満の番号のビットは変化せず、RSB のビットだけが 0 になります。AND 演算では 0 & 0 = 0、1 & 1 = 1 のように同じ値に対する計算結果は変化しないので、RSB より大きな番号のビット は a のビットと同じ になります。

ビットの番号 a - 1 a a & (a - 1)
rsb 未満 1 0 a のビットと同じ 0
rsb 0 1 0
rsb + 1 以上 a のビット a のビット a のビット

筆者が参考にしたビット演算やビットボードに関するページをいくつか下記に紹介します。上記の式の説明も載っているので、興味がある方は参考にしてみて下さい。また、その中のいくつは今後の記事で説明する予定です。

calc_legal_moves の修正

先程説明した 下記の手順 で処理を行うように calc_legal_moves を修正します。

  1. ビットボードの 0 と 1 を反転 した値を計算し、board という変数に代入する。board は 1 であるビット が対応するマスの座標が マークが配置されていない合法手 であることを表す
  2. board の LOB を計算 する。計算した LOB は マークが配置されていない BitBoard の座標 を表すので 合法手の一覧に加える
  3. board の RSB のビットを 0 にすることで、board から 合法手の一覧に加えた BitBoard の座標 を表す データを取り除く
  4. board が 0 になった時点で、すべての合法手を登録した ことになるので 処理を終了 する
  5. board が 0 でない 場合は 手順 2 に戻って 次の合法手を計算 する

下記は calc_legal_moves を修正 したプログラムです。行う ビット演算は非常にわかりにくい ので、プログラムの中に説明のコメント を入れました。また、下記の説明では （）の中に上記の手順 を示しました

  • 5 行目：空のマスのビットが 1 になるビットボードを計算する（手順 1）
  • 8 ~ 13 行目：board から合法手を順番に取り出すという繰り返し処理を行う。board からすべての合法手を取り出すと board が 0 になり、while board: によって board が 0 でない間繰り返し処理が行われるので、そのような繰り返し処理を行うことができる（手順 4、5）
  • 10、11 行目：合法手である LOB を計算して合法手の一覧に登録する（手順 2）
  • 13 行目：board から合法手の情報を削除する（手順 3）
 1  def calc_legal_moves(self):
 2      # マークが配置されているマスのビットが 1 になるビットボードを計算する
 3      board = self.board[0] | self.board[1]
 4      # 空のマスのビットが 1 になるビットボードを計算する
 5      board = 0b111111111 - board
 6      legal_moves = []
 7      # board が 0 になるまで繰り返し処理を行う
 8      while board:
 9          # 次の合法手である LOB を計算する
10          move = board & (-board)
11          legal_moves.append(move)
12          # board の RSB を 0 にして move のデータを削除する
13          board -= move
14  
15      return legal_moves
16  
17  BitBoard.calc_legal_moves = calc_legal_moves
行番号のないプログラム 
def calc_legal_moves(self):
    # マークが配置されているマスのビットが 1 になるビットボードを計算する
    board = self.board[0] | self.board[1]
    # 空のマスのビットが 1 になるビットボードを計算する
    board = 0b111111111 - board
    legal_moves = []
    # board が 0 になるまで繰り返し処理を行う
    while board:
        # 次の合法手である LOB を計算する
        move = board & (-board)
        legal_moves.append(move)
        # board の RSB を 0 にして move のデータを削除する
        board -= move

    return legal_moves
    
BitBoard.calc_legal_moves = calc_legal_moves

上記の修正後に先程と同じ下記のプログラムで ゲーム開始時の局面 の 合法手の一覧を計算 すると、実行結果から 正しい計算が行われることが確認 できます。

bb = BitBoard()
legal_moves = bb.calc_legal_moves()
for move in legal_moves:
    print(bb.move_to_xy(move))

実行結果

(0, 0)
(1, 0)
(2, 0)
(0, 1)
(1, 1)
(2, 1)
(0, 2)
(1, 2)
(2, 2)

処理速度の比較

先程と同様の下記のプログラムで、マークが 0 ~ 8 個まで配置 された各局面に対する calc_legal_moves の処理時間を計測 します。

bb = BitBoard()
for x in range(bb.BOARD_SIZE):
    for y in range(bb.BOARD_SIZE):
        print(y + x * bb.BOARD_SIZE)
        %timeit bb.calc_legal_moves()
        bb.setmark(x, y, bb.CIRCLE)

実行結果

0
901 ns ± 18.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1
801 ns ± 8.29 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
2
714 ns ± 0.803 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
3
634 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
4
558 ns ± 1.74 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
5
457 ns ± 5.66 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
6
377 ns ± 1.88 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
7
299 ns ± 1.43 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
8
224 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は 先ほどの実行結果 に 上記の実行結果を加えた表 です。全体を比較できるように平均を計算 して加えました。表から以下の事が確認できます。

  • 修正後の BitBoad では、合法手の数が少なくなる と 処理速度が大きく向上 する
  • 配置されたマークの数が 4 以上 になると 修正後の BitBoard のほうが List1dBoard クラスよりも 処理速度が速くなる
  • 処理速度の平均 は 修正後の BitBoard が最も速い
  • 修正後の BitBoard の処理時間 が 合法手の数にほぼ比例する ことから、合法手の数の回数だけしか繰り返し処理が行われない ことが確認できる
配置されたマークの数 BitBoard
（修正前）		 List1dBoard BitBoard
（修正後）
0 914 ns 653 ns 901 ns
1 887 ns 602 ns 801 ns
2 881 ns 618 ns 714 ns
3 870 ns 616 ns 634 ns
4 844 ns 608 ns 558 ns
5 809 ns 580 ns 457 ns
6 794 ns 577 ns 377 ns
7 775 ns 574 ns 299 ns
8 754 ns 580 ns 224 ns
平均 836 ns 600 ns 551 ns

calc_legal_moves を実装 したので、ai2 VS ai2 の対戦 を行うことが 可能になりました。そこで、下記のプログラムで BitBoard と List1dBoard を利用した場合の 処理速度を計測 してみることにします。実行結果の BitBoard を利用した場合の 対戦成績 が List1dBoard を利用した場合と同じ なので、calc_legal_moves がが正しく動作する ことが確認できました。なお、ai14s を実行するため には count_markpats を実装する必要がある ので ai14s VS ai2 の対戦を行うことはまだできません。

from ai import ai2, ai_match
import random

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

実行結果

boardclass: BitBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 21777.38it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

boardclass: BitBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 16858.75it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

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

boardclass: List1dBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 16950.29it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

下記は上記の実行結果をまとめた表で、両者の 処理速度がほとんど変わらない ことが確認できました。また、ai2 VS ai2 の処理では List1dBoard クラスの場合と同様に count_linemark が False のほうが処理速度が速い ことが確認できました。

boardclass count_linemark ai2 VS ai2
BitBoard False 21777.38 回/秒
List1dBoard False 22700.83 回/秒
BitBoard True 16858.75 回/秒
List1dBoard True 16950.29 回/秒

両者の 処理速度がほとんど変わらない理由 は、以前の記事で検証したように マークの参照と配置 を行う getmark_by_move と setmark_by_move の処理が、BitBoard クラスのほうが List1dBoard クラスよりも 遅いから です。そのため、前回の記事で実装した 勝敗判定 や、今回の記事で実装した 合法手の一覧 の 処理速度が List1dBoard クラスよりも 高速であっても、全体の処理速度はほぼ同じになる ようです。

ビット演算 を利用することで、複数のマスに対する処理をまとめて行うことができる ことが 処理速度の向上につながります7。そのため、〇× ゲーム のような 小さいゲーム盤 では ビットボードによる処理速度の向上が大きく見込めない ようです。この後の記事で検証する予定ですが、ゲーム盤のサイズが大きくなる と ビットボードによる処理速度の向上が大きく見込めるのではないか と思います。

今回の記事のまとめ

今回の記事では、ビットボード でゲーム盤を表現した場合の 合法手の一覧の計算の方法 をいくつか説明してその 処理速度を比較 し、ビット演算を利用 することで 合法手の一覧のを高速に計算できる ことを示しました。

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

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

次回の記事

近日公開予定です

  1. もしかすると list 内包表記でもこのように重複しないように記述する方法があるかもしれませんが、筆者はすぐには思いつきませんでした ↩

  2. LSB と呼ぶ場合もあるようですが、LSB は以前の記事で説明したように、一般的 にはビット列の中で最も小さい値である 0 番のビットを表す ので その表現は正確ではない ような気がします。また、他にも、Least Significant Set Bit のように表記する場合もあるようです ↩

  3. Java というプログラミング言語では、そのような値を計算する lowestOneBit という名前のメソッドが定義されているようです ↩

  4. RSB は LOB の 1 のビットを表します ↩

  5. 以前の記事で説明したように、そのような値 は 負の整数 とみなされます ↩

  6. 2 進数の加算でも、10 進数の加算と同様に繰上りの計算が行われます ↩

  7. 複数のデータの処理をまとめて行うという点では ndarray と似ており、以前の記事で検証したように、ndarray もゲーム盤のサイズが大きくなると list を利用した場合と比較して処理速度が高速になります ↩

2
2
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
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?