Pythonで〇×ゲームのAIを一から作成する　その216　任意の大きさのゲーム盤に対応した BitBoard クラスの修正

Last updated at 2026-02-22Posted at 2026-02-15

目次と前回の記事

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 クラスの修正

今回の記事では BitBoard クラスが 任意の大きさ の〇×ゲームの ゲーム盤を扱うことができるようにします。

前回の記事で説明したように、任意の大きさ のゲーム盤を扱う 汎用的な BitBoard クラスは、同じ大きさ の 3 x 3 のゲーム盤であってもゲーム盤の 大きさを限定した BitBoard3x3 よりも 処理速度が遅く なります。そのため、今回の記事の実装では、処理速度を最重視した実装は行わない ことにします。例えば popcount の計算 は前回の記事で紹介した参照テーブルではなく、任意のビット長の popcount を計算 できる bit_count メソッドを利用 することにします。また、count_linemark が True の場合の処理は変更する必要がないので、説明は省略します。

修正する必要がないメソッド

下記のメソッド は ゲーム盤のサイズが変わっても同じプログラムで処理を行える ので 修正する必要はありません。

getmark_by_move
setmark_by_move
xy_to_move
move_to_xy
judge
board_to_hashable
board_to_str

`is_winner` メソッドで利用するビットマスクの一覧の計算

現状の is_winner メソッドでは、直線上にマークが並んでいるかどうかを判定 するために利用する ビットマスク として、あらかじめ計算 しておいた下記の値を変数に代入して 利用しました。

# 各列の対応するマスを 1 とするビットマスク
colmasks = [0b000000111, 0b000111000, 0b111000000] 
# 各行の対応するマスを 1 とするビットマスク
rowmasks = [0b001001001, 0b010010010, 0b100100100] 
diamask1 = 0b100010001   # 対角線 1 の対応するマスを 1 とするビットマスク
diamask2 = 0b001010100   # 対角線 2 の対応するマスを 1 とするビットマスク

だたし、上記のビットマスク は 3 x 3 のサイズ のゲーム盤の場合のものなので、任意の大きさのゲーム盤を扱える ように BitBoard クラスを修正するためには、ゲーム盤の大きさに応じたビットマスクの一覧を計算 する必要があります。どのように計算すればよいかについて少し考えてみて下さい。

ビットマスクの一覧の計算方法

BitBoard の座標 は 対応するマスのビットのみを 1 とした ビット列 なので、上記のビットマスクの一覧 は BitBoard の座標を計算 する xy_to_move と OR 演算 を利用した下記のプログラムで計算することができます。

1、2 行目：各列と各行のビットマスクの一覧を計算する変数を空の list で初期化する
3、4 行目：各対角線のビットマスクを計算する変数を、すべてのビットが 0 である 0 で初期化する
5 ~ 14 行目：ゲーム盤のサイズの数だけ繰り返し処理を行う
6、7 行目：i 列と i 行のビットマスクを計算する変数を 0 で初期化する
8 ~ 10 行目：繰り返し処理によって i 列の各マスに対応するビット列と colmask の OR 演算を行うことで、i 列のビットマスクを計算する。i 行のビットマスクに関しても同様の処理を行う
11、12 行目：i 列と i 行のビットマスクを colmasks と rowmasks の要素に追加する
13、14 行目：各対角線の i 列のマスに対応するビット列を計算し、diamask1 と diamask2 との OR 演算を行うことで各対角線のビットマスクを計算する

 1  colmasks = []
 2  rowmasks = []
 3  diamask1 = 0
 4  diamask2 = 0
 5  for i in range(self.BOARD_SIZE):
 6      colmask = 0
 7      rowmask = 0
 8      for j in range(self.BOARD_SIZE):
 9          colmask |= self.xy_to_move(i, j)
10          rowmask |= self.xy_to_move(j, i)
11      colmasks.append(colmask)
12      rowmasks.append(rowmask)
13      diamask1 |= self.xy_to_move(i, i)
14      diamask2 |= self.xy_to_move(i, self.BOARD_SIZE - i - 1)

行番号のないプログラム

colmasks = []
rowmasks = []
diamask1 = 0
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)
    colmasks.append(colmask)
    rowmasks.append(rowmask)
    diamask1 |= self.xy_to_move(i, i)
    diamask2 |= self.xy_to_move(i, self.BOARD_SIZE - i - 1)

上記のビットマスクをもっと高速に計算する方法がありますが、上記の計算はあらかじめ 1 回だけ行えば良いので処理速度はそれほど重要ではありません。そのため上記では処理速度よりもわかりやすさを重視したプログラムにしました。

ゲーム盤のサイズが変わらない限り、上記で計算した ビットマスクの一覧は常に同じ値 になります。そのため、上記の計算処理 を is_winner メソッドで毎回行う のは明らかに無駄で、処理速度の大幅な低下 につながります。そこで、この ビットマスクの一覧 を前回の記事で説明した 参照テーブルとしてあらかじめ計算 しておくことにします。この参照テーブルをどこで計算しておけば良いかについて少し考えてみて下さい。

ビットマスクの一覧の参照テーブルの記録の方法

前回の記事で定義した BitBoard3x3 クラスでは、3 x 3 の大きさ のゲーム盤の ビットマスクの一覧 を クラス属性に代入 することで 参照テーブルの計算処理を一度だけ行う ようにしましたが、BitBoard クラスは 任意の大きさのゲーム盤を扱う ので、クラス属性 に 特定の大きさ のゲーム盤の ビットマスクの一覧を代入 するという方法は うまくいきません。

そこで、ビットマスクの一覧の 参照テーブルの計算処理 を下記のプログラムのように __init__ メソッドで インスタンス属性に代入 することで、この処理を BitBoard クラスのインスタンスを作成した際 に 一度だけ行う ようすることにします。インスタンスごとにビットマスクの一覧の参照テーブルを記録 するので、異なる大きさのゲーム盤の参照テーブル を インスタンスごとに別々に扱う ことができます。

下記はそのように __init__ メソッドを修正したプログラムです。

8 ~ 21 行目：先程と同様の処理を行う。ただし、ビットマスクの一覧は変数ではなく、同名のインスタンスの属性に代入するようにした

 1  from marubatsu import BitBoard
 2  
 3  def __init__(self, board_size=3, count_linemark=False):
 4      self.BOARD_SIZE = board_size
 5      self.bit_length = self.BOARD_SIZE ** 2
 6      self.count_linemark = count_linemark
 7  
 8      self.colmasks = []
 9      self.rowmasks = []
10      self.diamask1 = 0
11      self.diamask2 = 0
12      for i in range(self.BOARD_SIZE):
13          colmask = 0
14          rowmask = 0
15          for j in range(self.BOARD_SIZE):
16              colmask |= self.xy_to_move(i, j)
17              rowmask |= self.xy_to_move(j, i)
18          self.colmasks.append(colmask)
19          self.rowmasks.append(rowmask)
20          self.diamask1 |= self.xy_to_move(i, i)
21          self.diamask2 |= self.xy_to_move(i, self.BOARD_SIZE - i - 1)
元と同じなので省略
22  
23  BitBoard.__init__ = __init__

行番号のないプログラム

from marubatsu import BitBoard

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.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.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__

修正箇所

from marubatsu import BitBoard

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.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)
元と同じなので省略
        
BitBoard.__init__ = __init__

上記の修正後に、下記のプログラムで 3 x 3 の大きさのゲーム盤の ビットマスクの一覧を表示 して 正しい処理が行われることを確認 することにします。

bb = BitBoard()
print("colmasks")
for colmask in bb.colmasks:
    print(f"0b{colmask:09b}")
print("rowmasks")
for rowmask in bb.rowmasks:
    print(f"0b{rowmask:09b}")
print(f"diamask1 0b{bb.diamask1:09b}")
print(f"diamask2 0b{bb.diamask2:09b}")

実行結果

colmasks
0b000000111
0b000111000
0b111000000
rowmasks
0b001001001
0b010010010
0b100100100
diamask1 0b100010001
diamask2 0b001010100

下記は is_winner メソッド内に記述した ビットマスクの一覧 で、上記の実行結果では下記と同じものが計算される ことから 正しい処理が行われたことが確認 できます。

# 各列の対応するマスを 1 とするビットマスク
colmasks = [0b000000111, 0b000111000, 0b111000000] 
# 各行の対応するマスを 1 とするビットマスク
rowmasks = [0b001001001, 0b010010010, 0b100100100] 
diamask1 = 0b100010001   # 対角線 1 の対応するマスを 1 とするビットマスク
diamask2 = 0b001010100   # 対角線 2 の対応するマスを 1 とするビットマスク

下記のプログラムは 4 x 4 のサイズ のゲーム盤の場合の ビットマスクの一覧を表示 するプログラムです。各自で 4 x 4 のゲーム盤の図などを書いて、実行結果の計算結果が正しいことを確認 してみて下さい。また、興味がある方 は もっと大きなサイズのゲーム盤 でも 正しい計算が行われることを確認 してみて下さい。

bb = BitBoard(board_size=4)
print("colmasks")
for colmask in bb.colmasks:
    print(f"0b{colmask:016b}")
print("rowmasks")
for rowmask in bb.rowmasks:
    print(f"0b{rowmask:016b}")
print(f"diamask1 0b{bb.diamask1:016b}")
print(f"diamask2 0b{bb.diamask2:016b}")

実行結果

colmasks
0b0000000000001111
0b0000000011110000
0b0000111100000000
0b1111000000000000
rowmasks
0b0001000100010001
0b0010001000100010
0b0100010001000100
0b1000100010001000
diamask1 0b1000010000100001
diamask2 0b0001001001001000

Marubatsu クラスの処理が原因となる問題点

上記の修正では、ビットマスクの一覧 を表す 参照テーブルの計算 を __init__ メソッドで行う ことにしたので、参照テーブル は BitBoard クラスの インスタンスを作成するたびに行われる ことになります。現状の Marubatsu クラスでは ゲームを新しく開始する際 に 下記の処理を行う ため、ゲームを新しく開始するたび に 参照テーブルを作り直す という 無駄な処理 が行われてしまうという問題があります。

restart メソッドを呼び出す
restart メソッド内から呼び出される initialize_board メソッドで下記のプログラムのように ゲーム盤を表すクラスのインスタンスを作成 する処理を行う
ゲーム盤を表すクラスの __init__ メソッドが呼び出され、BitBoard クラスを利用していた場合は 参照テーブルを計算 する 処理が行われる

def initialize_board(self):
    self.board = self.boardclass(self.BOARD_SIZE, *self.args, **self.kwargs)
    self.EMPTY = self.board.EMPTY
    self.CIRCLE = self.board.CIRCLE
    self.CROSS = self.board.CROSS

この問題を解決する方法について少し考えてみて下さい。

プログラムの修正方法

上記の問題は、Marubatsu クラスが ゲームを開始するたび に ゲーム盤を表すクラス の インスタンスを作成しなおす ことが原因です。従って、この問題を解決するため には Marubatsu クラスが ゲーム盤を表すクラスのインスタンス を 1 回だけ作成する ように修正する必要があります。

そのために BitBoard クラスを含めた すべてのゲーム盤を表すクラス を 下記のように修正 することにします。

__init__ メソッドには 一度計算すればよい処理だけを記述 する
新しくゲームを開始 する際に行う必要がある、ゲーム盤を初期化（initialize）する処理を記述 した initialize メソッドを追加 する

また、Marubatsu クラス を 下記のように修正する ことにします。

initialize_board メソッドで行っていた ゲーム盤を表すクラスのインスタンスを作成する処理など は一度だけ行えば良いので __init__ メソッドで行う ように修正し、initialize_board メソッドを廃止 する
restart メソッドで initialize_borad メソッドを呼び出す処理 を、ゲーム盤を表すクラスの initialize メソッドを呼び出す ように 修正する

BitBoard クラスの `init` メソッドの修正

下記は BitBoard クラスの __init__ メソッドを修正するプログラムです。なお、他のゲーム盤を表すクラスの修正は後で行うことにします。

19 行目以降にあったゲーム盤のビットボードを初期化する処理と count_linemark が True の場合の処理はゲームを開始するたびに行う必要があるので削除する
21 行目：この後で定義する initialize メソッドを呼び出すようにする

 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      self.count_linemark = count_linemark
 5  
 6      self.colmasks = []
 7      self.rowmasks = []
 8      self.diamask1 = 0
 9      self.diamask2 = 0
10      for i in range(self.BOARD_SIZE):
11          colmask = 0
12          rowmask = 0
13          for j in range(self.BOARD_SIZE):
14              colmask |= self.xy_to_move(i, j)
15              rowmask |= self.xy_to_move(j, i)
16          self.colmasks.append(colmask)
17          self.rowmasks.append(rowmask)
18          self.diamask1 |= self.xy_to_move(i, i)
19          self.diamask2 |= self.xy_to_move(i, self.BOARD_SIZE - i - 1)
20  
21      self.initialize()
22  
23  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.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.initialize()
        
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.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.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,
-       }    
+   self.initialize()
        
BitBoard.__init__ = __init__

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

下記は initialize メソッドの定義で __init__ メソッドから削除 した、ゲーム開始時に必要となる初期化処理 を行うように定義しました。

 1  def initialize(self):
 2      self.board = [0, 0]
 3      if self.count_linemark:
 4          self.rowcount = {
 5              self.CIRCLE: [0] * self.BOARD_SIZE,
 6              self.CROSS: [0] * self.BOARD_SIZE,
 7          }
 8          self.colcount = {
 9              self.CIRCLE: [0] * self.BOARD_SIZE,
10              self.CROSS: [0] * self.BOARD_SIZE,
11          }
12          self.diacount = {
13              self.CIRCLE: [0] * 2,
14              self.CROSS: [0] * 2,
15          }  
16  
17  BitBoard.initialize = initialize

行番号のないプログラム

def initialize(self):
    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.initialize = initialize

Marubatsu クラスの `init` メソッドの修正

下記は Marubatsu クラスの __init__ メソッドを修正するプログラムです

4 ~ 7 行目：initialize_board メソッドに記述されていた board 属性にゲーム盤を表すクラスのインスタンスを代入し、各マークを表す属性に値を代入する処理を行うように修正した

 1  from marubatsu import Marubatsu
 2  
 3  def __init__(self, boardclass=None, board_size=3, *args, **kwargs):
元と同じなので省略
 4      self.board = self.boardclass(self.BOARD_SIZE, *self.args, **self.kwargs)
 5      self.EMPTY = self.board.EMPTY
 6      self.CIRCLE = self.board.CIRCLE
 7      self.CROSS = self.board.CROSS
 8      # 〇×ゲーム盤を再起動するメソッドを呼び出す
 9      self.restart()
10  
11  Marubatsu.__init__ = __init__

行番号のないプログラム

from marubatsu import Marubatsu

def __init__(self, boardclass=None, board_size=3, *args, **kwargs):
    if boardclass is None:
        boardclass = ListBoard
    # ゲーム盤のデータ構造を定義するクラス
    self.boardclass = boardclass
    # ゲーム盤の縦横のサイズ
    self.BOARD_SIZE = board_size
    # boardclass のパラメータ
    self.args = args
    self.kwargs = kwargs
    self.board = self.boardclass(self.BOARD_SIZE, *self.args, **self.kwargs)
    self.EMPTY = self.board.EMPTY
    self.CIRCLE = self.board.CIRCLE
    self.CROSS = self.board.CROSS
    # 〇×ゲーム盤を再起動するメソッドを呼び出す
    self.restart()
    
Marubatsu.__init__ = __init__

修正箇所

from marubatsu import Marubatsu

def __init__(self, boardclass=None, board_size=3, *args, **kwargs):
元と同じなので省略
+   self.board = self.boardclass(self.BOARD_SIZE, *self.args, **self.kwargs)
+   self.EMPTY = self.board.EMPTY
+   self.CIRCLE = self.board.CIRCLE
+   self.CROSS = self.board.CROSS
    # 〇×ゲーム盤を再起動するメソッドを呼び出す
    self.restart()
    
Marubatsu.__init__ = __init__

Marubatsu クラスの `restart` メソッドの修正

下記は Marubatsu クラスの retart メソッドを修正するプログラムです

2 行目：board 属性の initialize メソッドを呼び出すように修正した

 1  def restart(self):
 2      self.board.initialize()
 3      self.turn = self.CIRCLE     
 4      self.move_count = 0
 5      self.status = self.PLAYING
 6      self.last_move = -1, -1          
 7      self.last_turn = self.CROSS
 8      self.records = [self.last_move]
 9  
10  Marubatsu.restart = restart

行番号のないプログラム

def restart(self):
    self.board.initialize()
    self.turn = self.CIRCLE     
    self.move_count = 0
    self.status = self.PLAYING
    self.last_move = -1, -1          
    self.last_turn = self.CROSS
    self.records = [self.last_move]
    
Marubatsu.restart = restart

修正箇所

def restart(self):
-   self.board = self.boardclass(self.BOARD_SIZE, *self.args, **self.kwargs)
+   self.board.initialize()
    self.turn = self.CIRCLE     
    self.move_count = 0
    self.status = self.PLAYING
    self.last_move = -1, -1          
    self.last_turn = self.CROSS
    self.records = [self.last_move]
    
Marubatsu.restart = restart

BitBoard クラスの `is_winner` メソッドの修正

is_winner メソッドで必要となる ビットマスクの一覧の参照テーブル が計算されて 属性に代入 たので、is_winner メソッドを下記のプログラムのようにその 参照テーブルを利用して処理を行う ように修正します。

4 行目の下にあったビットマスクの一覧を変数に代入する処理を削除する
5、6、11、14 行目：__init__ メソッドで計算したビットマスクの参照テーブルが代入された属性を利用するように修正する

 1  def is_winner(self, player, last_move):
 2      x, y = self.move_to_xy(last_move)
 3      if self.count_linemark:
元と同じなので省略
 4      else:
 5          colmask = self.colmasks[x]
 6          rowmask = self.rowmasks[y]
 7          board = self.board[player]
 8          if board & colmask == colmask or board & rowmask == rowmask:
 9              return True
10          # 左上から右下方向の判定
11          if x == y and board & self.diamask1 == self.diamask1:
12              return True
13          # 右上から左下方向の判定
14          if x + y == self.BOARD_SIZE - 1 and board & self.diamask2 == self.diamask2:
15              return True
16  
17      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
18      return False     
19  
20  BitBoard.is_winner = is_winner

行番号のないプログラム

def is_winner(self, player, last_move):
    x, y = self.move_to_xy(last_move)
    if self.count_linemark:
        if self.rowcount[player][y] == self.BOARD_SIZE or \
        self.colcount[player][x] == self.BOARD_SIZE:
            return True
        # 左上から右下方向の判定
        if x == y and self.diacount[player][0] == self.BOARD_SIZE:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            self.diacount[player][1] == self.BOARD_SIZE:
            return True
    else:
        colmask = self.colmasks[x]
        rowmask = self.rowmasks[y]
        board = self.board[player]
        if board & colmask == colmask or board & rowmask == rowmask:
            return True
        # 左上から右下方向の判定
        if x == y and board & self.diamask1 == self.diamask1:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and board & self.diamask2 == self.diamask2:
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False     

BitBoard.is_winner = is_winner

修正箇所

def is_winner(self, player, last_move):
    x, y = self.move_to_xy(last_move)
    if self.count_linemark:
元と同じなので省略
    else:
-       colmasks = [0b000000111, 0b000111000, 0b111000000]
-       rowmasks = [0b001001001, 0b010010010, 0b100100100]
-       diamask1 = 0b100010001
-       diamask2 = 0b001010100
-       colmask = colmasks[x]
+       colmask = self.colmasks[x]
-       rowmask = rowmasks[y]
+       rowmask = self.rowmasks[y]
        board = self.board[player]
        if board & colmask == colmask or board & rowmask == rowmask:
            return True
        # 左上から右下方向の判定
-       if x == y and board & diamask1 == diamask1:
+       if x == y and board & self.diamask1 == self.diamask1:
            return True
        # 右上から左下方向の判定
-       if x + y == self.BOARD_SIZE - 1 and board & diamask2 == diamask2:
+       if x + y == self.BOARD_SIZE - 1 and board & self.diamask2 == self.diamask2:
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False     

BitBoard.is_winner = is_winner

`judge` メソッドの処理の確認

修正した is_winner メソッドが 正しい処理を行うかどうか を is_winner メソッド呼び出す judge メソッドのテスト を行う test_judge を利用して確認 することにします。下記のプログラムの実行結果から 正しい処理を行うことが確認 できました。

from mbtest import test_judge

test_judge(mbparams={"boardclass": BitBoard})

実行結果

Start
test winner = playing
oooooooooo
test winner = 0
ooooooooo
test winner = 1
oooooooo
test winner = draw
o
Finished

test_judge は 3 x 3 のサイズ のゲーム盤の場合の テストしか行えません。そこで、4 x 4 のサイズ での処理が正しく行われるかどうかを「列方向〇の勝利」、「行方向の × の勝利」、「対角線方向の〇の勝利」になるような 着手を行った局面を表示 することで確認することにします。下記はそのプログラムで、それぞれの局面の表示の上部 に 勝者が正しく表示される ことから これらの局面に対して正しい処理が行われることが確認 できました。なお、下記の確認は 一部の局面でしか行っていない ので 興味がある方 は 他の局面 や、もっと大きなサイズのゲーム盤でも確認 してみて下さい。

# 列方向の 〇 の勝利
movelist = [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0)]
mb = Marubatsu(boardclass=BitBoard, board_size=4)
for x, y in movelist:
    mb.cmove(x, y)
print(mb)

# 行方向の × の勝利
movelist = [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (0, 2), (3, 1)]
mb = Marubatsu(boardclass=BitBoard, board_size=4)
for x, y in movelist:
    mb.cmove(x, y)
print(mb)

# 対角線方向の 〇 の勝利
movelist = [(0, 0), (0, 1), (1, 1), (1, 0), (2, 2), (2, 0), (3, 3)]
mb = Marubatsu(boardclass=BitBoard, board_size=4)
for x, y in movelist:
    mb.cmove(x, y)
print(mb)

実行結果

winner o
oooO
xxx.
....
....

winner x
ooo.
xxxX
o...
....

winner o
oxx.
xo..
..o.
...O

合法手の一覧の計算に必要なビットマスクの計算

合法手の一覧を計算 する calc_legal_moves では以前の記事で説明したように、空のマスのビットが 1 になる ビットボードを計算するため に、すべてのマスのビットが 1 になる ビット列を計算 する必要があります。

下記は、現状の calc_legal_moves 内で行っている 3 x 3 の大きさ のゲーム盤の場合の計算を行うプログラムで、ゲーム盤の 9 つのすべてのマスのビットが 1 となる 0b111111111 という ビット列 からゲーム盤を表すビットマスクを引き算することで計算しています。

# 空のマスのビットが 1 になるビットボードを計算する
board = 0b111111111 - board

ゲーム盤の すべてのマスのビットが 1 となる ビット列 は LSB（0 番のビット）から ゲーム盤のマスの数と同じ数 だけ 1 のビットが並んだ値 です。そのようなビット列は、ゲーム盤の マスの数が n の場合は $2^n - 1$ = 1 << n - 1 という式で計算することができます。その理由は $2 ^n$ が 1 の後に n 個の 0 が並んだビット列 で表現されるので、そこから 1 を引く と 繰り下がり によって n 個の 1 が並んだビット列が計算 されるからです。

下記は $\boldsymbol{2 ^ {8} - 1}$ の計算を表しており、1 が 8 個並んだビット列が計算 されます。

  0b100000000   # 2 の 8 乗
- 0b000000001
-------------
  0b011111111

上記の計算は 10 進数の $10 ^ 8 - 1$ = 100000000 - 1 が繰り下がりによって 8 個の 9 が並ぶ 99999999 になるのと似ています。

  100000000   # 10 の 8 乗
- 000000001
-----------
  099999999

`init` メソッドの修正

下記のプログラムの 7 行目 のように __init__ メソッドで ゲーム盤のマスの数だけ 1 が並んだビット列 を fullmask という 属性に代入 しておくことにします。1 つしかデータがありませんが、あらかじめ計算したデータを後で利用する のでこれも 参照テーブルの一種 です。属性の名前 は すべて（full） のマスのビットが 1 になる ビットマスク であることから命名しました。

 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      self.count_linemark = count_linemark
 5  
 6      # 参照テーブルの計算
 7      self.fullmask = (1 << (self.BOARD_SIZE ** 2)) - 1
 8      self.colmasks = []
元と同じなので省略
 9  
10  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.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.initialize()
        
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.fullmask = (1 << (self.BOARD_SIZE ** 2)) - 1
    self.colmasks = []
元と同じなので省略
        
BitBoard.__init__ = __init__

下記は 3 x 3 と 4 x 4 のサイズ のゲーム盤の場合の fullmask 属性の値を表示 するプログラムで、1 が 9 個 と 16 個並んだ ビット列が 正しく計算されることが確認 できます。

bb = BitBoard()
print(bin(bb.fullmask))
bb = BitBoard(board_size=4)
print(bin(bb.fullmask))

実行結果

0b111111111
0b1111111111111111

`calc_legal_moves` メソッドの修正

次に、下記のプログラムの 5 行目 のように 上記で計算した値を利用して計算 するように calc_legal_moves を修正 します。

1  def calc_legal_moves(self):
2      # マークが配置されているマスのビットが 1 になるビットボードを計算する
3      board = self.board[0] | self.board[1]
4      # 空のマスのビットが 1 になるビットボードを計算する
5      board = self.fullmask - board
元と同じなので省略
6  
7  BitBoard.calc_legal_moves = calc_legal_moves

行番号のないプログラム

def calc_legal_moves(self):
    # マークが配置されているマスのビットが 1 になるビットボードを計算する
    board = self.board[0] | self.board[1]
    # 空のマスのビットが 1 になるビットボードを計算する
    board = self.fullmask - 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

修正箇所

def calc_legal_moves(self):
    # マークが配置されているマスのビットが 1 になるビットボードを計算する
    board = self.board[0] | self.board[1]
    # 空のマスのビットが 1 になるビットボードを計算する
-   board = 0b111111111 - board
+   board = self.fullmask - board
元と同じなので省略

BitBoard.calc_legal_moves = calc_legal_moves

下記は ゲーム盤のサイズ が 3 x 3 と 4 x 4 の それぞれの場合に対して (0, 0)、(0, 1)、(1, 1)、(2, 1) の 4 つのマスに着手を行った局面 の合法手の一覧を calc_legal_moves で計算して表示 するプログラムです。実行結果から 合法手の一覧が正しく計算される ことが確認できます。興味がある方は他の着手を行った場合や、もっと大きなサイズのゲーム盤でも確認してみて下さい。

movelist = [(0, 0), (0, 1), (1, 1), (2, 1)]
# 3 x 3 のゲーム盤の場合
print("3 x 3")
mb = Marubatsu(boardclass=BitBoard)
for x, y in movelist:
    mb.cmove(x, y)
print(mb)
legal_moves = mb.calc_legal_moves()
for move in legal_moves:
    x, y = mb.board.move_to_xy(move)
    print(x, y)
print()

# 4 x 4 のゲーム盤の場合
print("4 x 4")
mb = Marubatsu(boardclass=BitBoard, board_size=4)
for x, y in movelist:
    mb.cmove(x, y)
print(mb)
legal_moves = mb.calc_legal_moves()
for move in legal_moves:
    x, y = mb.board.move_to_xy(move)
    print(x, y)

実行結果

3 x 3
Turn o
o..
xoX
...

0 2
1 0
1 2
2 0
2 2

4 x 4
Turn o
o...
xoX.
....
....

0 2
0 3
1 0
1 2
1 3
2 0
2 2
2 3
3 0
3 1
3 2
3 3

`ai2` VS `ai2` の処理速度の確認

ai2 の処理を行うために 必要なメソッドが定義 できたので、下記のプログラムで ai2 VS ai2 の対戦の 処理速度を計測 します。実行結果の対戦成績がこれまでと同じ なので 正しい処理が行われる ことが確認できました。

from ai import ai2, ai_match
import random

boardclass = BitBoard
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": boardclass, "count_linemark": count_linemark})

実行結果

boardclass: BitBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 21328.21it/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:03<00:00, 15904.61it/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%

下記は以前の記事で計測した BitBoard クラスの ai2 VS ai2 の処理速度の計測結果に上記の実行結果を加えた表です。今回の修正の行っても処理速度がほぼ変わらない ことが確認できました。行う計算処理そのものは変わらない のでこの結果は 当然でしょう。

	`count_linemark`	`ai2` VS `ai2`
修正前	`False`	21704.15 回/秒
修正後	`False`	21328.21 回/秒
修正前	`True`	16380.29 回/秒
修正後	`True`	15904.61 回/秒

なお、ai2 は 3 x 3 のサイズ のゲーム盤の〇× ゲーム にしか対応していない ので、他のサイズ のゲーム盤の〇× ゲームの 最善手を計算することはできません。3 x 3 以外のサイズ のゲーム盤に対する 処理速度の検証 は 別の方法で後で行う ことにします。

`count_markpats` で利用するビットマスクの計算

各直線上の マークのパターの一覧を計算 する 現状の count_markpats では、下記のプログラムのように 3 x 3 のサイズ のゲーム盤に対する各直線上のマスを表す ビットマスクの一覧を変数に代入 して利用しています。

masklist = [
    0b000000111, # 0 列のビットマスク
    0b000111000, # 1 列のビットマスク
    0b111000000, # 2 列のビットマスク
    0b001001001, # 0 行のビットマスク
    0b010010010, # 1 行のビットマスク
    0b100100100, # 2 行のビットマスク
    0b100010001, # 対角線 1 のビットマスク
    0b001010100, # 対角線 2 のビットマスク
]

先程と同様に 任意の大きさのゲーム盤 に対して 上記と同様のビットマスクの一覧を計算 する必要があるので、その処理を __init__ メソッドで行う ことにします。

`init` メソッドの修正

上記の ビットマスクの一覧 は、先程 __init__ メソッドで計算 した 各列、各行、対角線 に対する ビットマスクの一覧を集めたもの なので、それらのデータから以前の記事で説明した + 演算子 による list の結合 によって計算することができます。

下記は __init__ メソッドを修正したプログラムです。

7 行目：+ 演算子 で 各列、各行、各対角線 を表す list を結合 することで、それらのすべての要素を持つ list を計算 して masklist 属性に代入 する。ただし、self.diamask1 と self.diamask2 は list ではない ので + 演算子 で list と結合することはできない 点に注意が必要である。そのため、[self.diamask1, self.diamask2] のように 対角線のビットマスクを要素として持つ list としてから結合 した

 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      self.count_linemark = count_linemark
 5  
 6      # 参照テーブルの計算
元と同じなので省略
 7      self.masklist = self.colmasks + self.rowmasks + [self.diamask1, self.diamask2]
 8  
 9      self.initialize()
10  
11  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.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.initialize()
        
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.masklist = self.colmasks + self.rowmasks + [self.diamask1, self.diamask2]
            
    self.initialize()
        
BitBoard.__init__ = __init__

`count_markpats` メソッドの修正

下記は上記で計算した 参照テーブルを利用 するように count_markpats メソッドを修正 したプログラムです。

7 行目の下にあった各直線のビットマスクの一覧を marklist に代入する処理は __init__ メソッドで行うようにしたので削除した
8 行目：marklist を self.marklist に修正した

 1  from collections import defaultdict
 2
 3  def count_markpats(self, turn, last_turn):
 4      markpats = defaultdict(int)
 5  
 6      if self.count_linemark:
元と同じなので省略
 7      else:
 8          for mask in self.masklist:
元と同じなので省略
 9      return markpats    
10    
11  BitBoard.count_markpats = count_markpats

行番号のないプログラム

from collections import defaultdict

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)

    if self.count_linemark:
        for countdict in [self.rowcount, self.colcount, self.diacount]:
            for circlecount, crosscount in zip(countdict[self.CIRCLE], countdict[self.CROSS]):
                emptycount = self.BOARD_SIZE - circlecount - crosscount
                if last_turn == self.CIRCLE:
                    markpats[(circlecount, crosscount, emptycount)] += 1
                else:
                    markpats[(crosscount, circlecount, emptycount)] += 1
    else:
        for mask in self.masklist:
            turncount = (self.board[turn] & mask).bit_count()
            lastturncount = (self.board[last_turn] & mask).bit_count()
            emptycount = self.BOARD_SIZE - turncount - lastturncount
            markpats[(lastturncount, turncount, emptycount)] += 1

    return markpats    

BitBoard.count_markpats = count_markpats

修正箇所

from collections import defaultdict

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)

    if self.count_linemark:
元と同じなので省略
    else:
-       masklist = [
-           0b000000111, # 0 列のビットマスク
-           0b000111000, # 1 列のビットマスク
-           0b111000000, # 2 列のビットマスク
-           0b001001001, # 0 行のビットマスク
-           0b010010010, # 1 行のビットマスク
-           0b100100100, # 2 行のビットマスク
-           0b100010001, # 対角線 1 のビットマスク
-           0b001010100, # 対角線 2 のビットマスク
-       ]
-       for mask in masklist:
+       for mask in self.masklist:
元と同じなので省略
    return markpats    

BitBoard.count_markpats = count_markpats

下記は ゲーム盤のサイズ が 3 x 3 と 4 x 4 の それぞれの場合に対して (0, 0)、(0, 1)、(1, 1)、(2, 1) の 4 つのマスに着手を行った局面 のマークのパターンの一覧を calc_markpats で計算して表示 するプログラムです。実行結果と局面を見比べ て 正しい計算が行われていることを確認 して下さい。なお、〇の手番の局面 なので、マークのパターンを表す tuple の要素は (× のマークの数,〇のマークの数, 空のマスの数) の順になる 注意して下さい。また、興味がある方はもっと大きなサイズのゲーム盤でも確認してみて下さい。

from pprint import pprint

movelist = [(0, 0), (0, 1), (1, 1), (2, 1)]
# 3 x 3 のゲーム盤の場合
print("3 x 3")
mb = Marubatsu(boardclass=BitBoard)
for x, y in movelist:
    mb.cmove(x, y)
print(mb)
pprint(mb.count_markpats())
print()

# 4 x 4 のゲーム盤の場合
print("4 x 4")
mb = Marubatsu(boardclass=BitBoard, board_size=4)
for x, y in movelist:
    mb.cmove(x, y)
print(mb)
pprint(mb.count_markpats())

実行結果

3 x 3
Turn o
o..
xoX
...

defaultdict(<class 'int'>,
            {(0, 0, 3): 1,
             (0, 1, 2): 3,
             (0, 2, 1): 1,
             (1, 0, 2): 1,
             (1, 1, 1): 1,
             (2, 1, 0): 1})

4 x 4
Turn o
o...
xoX.
....
....

defaultdict(<class 'int'>,
            {(0, 0, 4): 3,
             (0, 1, 3): 2,
             (0, 2, 2): 1,
             (1, 0, 3): 2,
             (1, 1, 2): 1,
             (2, 1, 1): 1})

`ai14s` VS `ai2` の処理速度の確認

ai14s の処理を行うために 必要なメソッドが定義 できたので、下記のプログラムで ai14s VS ai2 の対戦の 処理速度を計測 します。実行結果の 対戦成績がこれまでと同じ なので 正しい処理が行われることが確認 できました。

from ai import ai14s
import random

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

実行結果

boardclass: BitBoard, count_linemark False
ai14s VS ai2
100%|██████████| 50000/50000 [00:17<00:00, 2820.79it/s]
count     win    lose    draw
o       49490       0     510
x       44103       0    5897
total   93593       0    6407

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.2%    0.0%   11.8%
total   93.6%    0.0%    6.4%

boardclass: BitBoard, count_linemark True
ai14s VS ai2
100%|██████████| 50000/50000 [00:23<00:00, 2157.09it/s]
count     win    lose    draw
o       49490       0     510
x       44103       0    5897
total   93593       0    6407

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.2%    0.0%   11.8%
total   93.6%    0.0%    6.4%

下記は以前の記事で計測した BitBoard クラスの ai14s VS ai2 の処理速度の計測結果に上記の実行結果を加えた表です。先ほど同様に今回の修正の行っても 処理速度がほぼ変わらない ことが確認できました¹。

	`count_linemark`	`ai2` VS `ai2`	`ai14s` VS `ai2`
修正前	`False`	21704.15 回/秒	3086.52 回/秒
修正後	`False`	21328.21 回/秒	2820.79 回/秒
修正前	`True`	16380.29 回/秒	2272.21 回/秒
修正後	`True`	15904.61 回/秒	2157.09 回/秒

記事が長くなりましたので、残りの BitBoard クラスのメソッドについては次回の記事で実装することにします。

処理速度の比較

様々な大きさのゲーム盤 に対して、これまでに実装したゲーム盤を表すクラス の 下記のメソッドの処理速度を比較 することで、それぞれのクラス の ゲーム盤の大きさと処理速度の関係について検証 することにします。なお、今回の記事でまだ 任意のサイズのゲーム盤 の処理を行えるように 修正していない BitBoard クラスのメソッド の処理速度については 次回の記事で検証 することにします。

マークを配置する setmark_by_move
マークを参照する getmark_by_move
合法手の一覧を計算する calc_legal_moves
判定を行う judge
マークのパターンの一覧を計算する count_markpats

ゲーム盤を表すクラスの修正

今回の記事で行った修正 から、BitBoard 以外の他のゲーム盤を表す ListBoard、List1dBoard、ArrayBoard, NpBoard、NpIntBoard、NpBoolBoard、BitBoard3x3 クラスに initialize メソッドを定義 し、__init__ メソッドから initialize メソッドを呼び出すように修正 する必要があります。下記は 各クラスの __init__ メソッドの修正 と initialize メソッドを定義 するプログラムです。その際に、initialize メソッド をゲーム盤を表すクラスの 基底クラスである Board クラスの 抽象メソッドとして定義 することにしました。

下記はプログラムの説明で、プログラムは長いので折りたたみました。

BitBoard と BitBoard3x3 以外 の __init__ メソッドで行う処理は共通なので、同じ関数を定義 すればよい。なお、ListBoard と BitBoard3x3 以外 のクラスは ListBoard クラスを継承して定義 しているので marubatsu.py の方では ListBoard と BitBoard3x3 以外 のクラスの __init__ メソッドを削除 することにする
initialize メソッドは board 属性にゲーム開始時の局面を表すデータを代入 する部分 だけが異なる
NpBoard と NpIntBoard クラスの initialize メソッドは同じ であり、NpIntBoard クラスは NpBoard クラスを継承して定義 しているので NpIntBoard クラスの initialize メソッドを定義する必要はない

プログラム

from abc import abstractmethod
from array import array
import numpy as np
from marubatsu import Board, ListBoard, List1dBoard, ArrayBoard, NpBoard, \
                      NpIntBoard, NpBoolBoard, BitBoard3x3

@abstractmethod
def initialize(self):
    pass

Board.initialize = initialize

def __init__(self, board_size=3, count_linemark=False):
    self.BOARD_SIZE = board_size
    self.count_linemark = count_linemark
    self.initialize()
    
ListBoard.__init__ = __init__
List1dBoard.__init__ = __init__
ArrayBoard.__init__ = __init__
NpBoard.__init__ = __init__
NpIntBoard.__init__ = __init__
NpBoolBoard.__init__ = __init__

def __init__(self, *args, **kwargs):
    self.BOARD_SIZE = 3
    self.bit_length = 9
    self.initialize()
    
BitBoard3x3.__init__ = __init__

def initialize(self):
    self.board = [[self.EMPTY] * self.BOARD_SIZE for y in range(self.BOARD_SIZE)]
    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,
        }
        
ListBoard.initialize = initialize

def initialize(self):
    self.board = [self.EMPTY] * (self.BOARD_SIZE ** 2)
    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,
        }
        
List1dBoard.initialize = initialize

def initialize(self):
    self.board = array("w", [self.EMPTY] * (self.BOARD_SIZE ** 2))
    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,
        }
        
ArrayBoard.initialize = initialize

def initialize(self):
    self.board = np.full((self.BOARD_SIZE, self.BOARD_SIZE), self.EMPTY)
    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,
        }
        
NpBoard.initialize = initialize

def initialize(self):
    self.board = np.full((2, self.BOARD_SIZE, self.BOARD_SIZE), False)
    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,
        }
        
NpBoolBoard.initialize = initialize

def initialize(self):
    self.board = [0, 0]

BitBoard3x3.initialize = initialize

処理速度の比較と検証

下記のプログラムで これまでに定義したすべてのゲーム盤を表すクラス に対して、 ゲーム盤のサイズ が 3, 5, 10, 50, 100 のそれぞれの場合の 下記のメソッドの処理速度を計測 することにします。なお、judge メソッドは 0 列と 1 列に〇と × がゲーム盤のサイズ - 1 個並んだ、決着がついていない局面 に対して行うことにしました。BitBoard3x3 クラスは 3 x 3 のゲーム盤 にしか対応しない ので、それ以外のサイズゲーム盤での計測は行いません。なお、conunt_linemark が True の場合に行われる処理はどのクラスも同じなので計測しません。また、実行結果は長いので全体は折りたたみました。

setmark_by_move で (0, 0) に〇を着手する
getmark_by_move で (0, 0) のマークを計算する
calc_legal_moves
judge
count_markpats

for board_size in [3, 5, 10, 50, 100]:
    for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, 
                       NpBoolBoard, BitBoard, BitBoard3x3]:
        if board_size != 3 and boardclass == BitBoard3x3:
            continue
        print(f"board size = {board_size} 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)
        move = mb.board.xy_to_move(0, 0)
        print("setmark_by_move")
        %timeit mb.board.setmark_by_move(move, mb.CIRCLE)
        print("getmark_by_move")
        %timeit mb.board.getmark_by_move(move)
        print("calc_legal_moves")
        %timeit mb.calc_legal_moves()
        print("judge")
        %timeit mb.judge()
        print("count_markpats")
        %timeit mb.count_markpats()
        print()

実行結果

board size = 3 boardclass: ListBoard
setmark_by_move
111 ns ± 0.169 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
85.7 ns ± 0.11 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
1.16 μs ± 2.28 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
146 ns ± 0.273 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
10.1 μs ± 25.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 3 boardclass: List1dBoard
setmark_by_move
93.6 ns ± 0.58 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
70.7 ns ± 0.369 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
701 ns ± 2.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
160 ns ± 1.14 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
10.4 μs ± 31.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
略

全体の実行結果

board size = 3 boardclass: ListBoard
setmark_by_move
111 ns ± 0.169 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
85.7 ns ± 0.11 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
1.16 μs ± 2.28 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
146 ns ± 0.273 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
10.1 μs ± 25.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 3 boardclass: List1dBoard
setmark_by_move
93.6 ns ± 0.58 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
70.7 ns ± 0.369 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
701 ns ± 2.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
160 ns ± 1.14 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
10.4 μs ± 31.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 3 boardclass: ArrayBoard
setmark_by_move
131 ns ± 1.37 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
85.5 ns ± 1.03 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
824 ns ± 2.03 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
160 ns ± 0.939 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
10.6 μs ± 53.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 3 boardclass: NpBoard
setmark_by_move
227 ns ± 1.23 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
298 ns ± 1.12 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
3.47 μs ± 17.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
147 ns ± 1.1 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
20 μs ± 203 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 3 boardclass: NpIntBoard
setmark_by_move
161 ns ± 0.9 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
140 ns ± 0.916 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
2.26 μs ± 89.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
146 ns ± 0.563 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
20 μs ± 195 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 3 boardclass: NpBoolBoard
setmark_by_move
235 ns ± 11.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
208 ns ± 1.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
3.34 μs ± 8.57 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
146 ns ± 0.328 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
17.8 μs ± 226 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 3 boardclass: BitBoard
setmark_by_move
207 ns ± 10.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
152 ns ± 0.268 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
660 ns ± 3.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
188 ns ± 0.985 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
3.08 μs ± 19 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 3 boardclass: BitBoard3x3
setmark_by_move
126 ns ± 0.258 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
98.7 ns ± 1.05 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
611 ns ± 4.91 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
139 ns ± 0.964 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
2.87 μs ± 8.38 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 5 boardclass: ListBoard
setmark_by_move
109 ns ± 0.172 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
83.9 ns ± 0.0825 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
2.38 μs ± 15 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
144 ns ± 0.986 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
17 μs ± 48 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 5 boardclass: List1dBoard
setmark_by_move
91.5 ns ± 0.224 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
69.3 ns ± 0.113 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
1.41 μs ± 2.43 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
157 ns ± 1.57 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
18.3 μs ± 242 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 5 boardclass: ArrayBoard
setmark_by_move
132 ns ± 1.41 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
87 ns ± 1.26 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
1.78 μs ± 11.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
159 ns ± 0.848 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
19.1 μs ± 136 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 5 boardclass: NpBoard
setmark_by_move
224 ns ± 1.66 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
298 ns ± 1.41 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
8.75 μs ± 97.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
148 ns ± 3.4 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
28.8 μs ± 243 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 5 boardclass: NpIntBoard
setmark_by_move
159 ns ± 0.837 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
138 ns ± 0.935 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
5.18 μs ± 23 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
146 ns ± 1.17 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
28.6 μs ± 173 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 5 boardclass: NpBoolBoard
setmark_by_move
223 ns ± 1.43 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
207 ns ± 0.92 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
8.63 μs ± 103 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
146 ns ± 1.29 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
24.3 μs ± 191 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 5 boardclass: BitBoard
setmark_by_move
233 ns ± 3.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
152 ns ± 0.24 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
1.87 μs ± 9.26 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
judge
179 ns ± 0.839 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
4.33 μs ± 13.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 10 boardclass: ListBoard
setmark_by_move
110 ns ± 0.336 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
86.1 ns ± 0.145 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
7.84 μs ± 116 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
146 ns ± 0.267 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
42.3 μs ± 76.8 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 10 boardclass: List1dBoard
setmark_by_move
93 ns ± 0.567 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
70.5 ns ± 1.02 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
4.87 μs ± 17.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
160 ns ± 1.4 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
45.8 μs ± 1.92 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 10 boardclass: ArrayBoard
setmark_by_move
129 ns ± 1.57 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
84.5 ns ± 0.215 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
6.42 μs ± 60.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
164 ns ± 3.72 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
48.9 μs ± 1.1 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 10 boardclass: NpBoard
setmark_by_move
232 ns ± 1.67 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
319 ns ± 20.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
34.6 μs ± 2.38 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
judge
146 ns ± 0.851 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
53.8 μs ± 469 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 10 boardclass: NpIntBoard
setmark_by_move
160 ns ± 0.991 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
138 ns ± 1.23 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
18.7 μs ± 107 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
145 ns ± 1.03 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
53.4 μs ± 177 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 10 boardclass: NpBoolBoard
setmark_by_move
224 ns ± 2.93 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
207 ns ± 1.11 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
33.7 μs ± 140 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
judge
147 ns ± 2.44 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
39.9 μs ± 151 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 10 boardclass: BitBoard
setmark_by_move
232 ns ± 5.25 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
177 ns ± 0.798 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
11.3 μs ± 59.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
judge
180 ns ± 1.69 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
8.21 μs ± 119 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

board size = 50 boardclass: ListBoard
setmark_by_move
108 ns ± 0.136 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
85.2 ns ± 0.377 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
168 μs ± 1.25 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
judge
144 ns ± 0.369 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
589 μs ± 2.57 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

board size = 50 boardclass: List1dBoard
setmark_by_move
92.2 ns ± 0.165 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
68.3 ns ± 0.498 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
132 μs ± 604 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
judge
147 ns ± 1.11 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
754 μs ± 2.12 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

board size = 50 boardclass: ArrayBoard
setmark_by_move
129 ns ± 0.773 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
84.9 ns ± 1.32 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
165 μs ± 2.5 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
judge
145 ns ± 0.841 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
828 μs ± 5.19 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

board size = 50 boardclass: NpBoard
setmark_by_move
226 ns ± 2.72 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
300 ns ± 3.11 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
789 μs ± 1.52 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
judge
146 ns ± 1.35 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
400 μs ± 8.81 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

board size = 50 boardclass: NpIntBoard
setmark_by_move
160 ns ± 2.31 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
141 ns ± 0.733 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
435 μs ± 11.2 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
judge
146 ns ± 1.26 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
403 μs ± 5.48 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

board size = 50 boardclass: NpBoolBoard
setmark_by_move
227 ns ± 10.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
208 ns ± 1.65 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
844 μs ± 9.35 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
judge
145 ns ± 1.43 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
170 μs ± 3.42 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 50 boardclass: BitBoard
setmark_by_move
234 ns ± 1.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
179 ns ± 1.69 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
732 μs ± 1.1 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
judge
178 ns ± 1.26 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
51.5 μs ± 57.9 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

board size = 100 boardclass: ListBoard
setmark_by_move
108 ns ± 0.121 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
84.7 ns ± 0.177 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
743 μs ± 1.63 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
judge
147 ns ± 2.16 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
2.17 ms ± 14.3 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

board size = 100 boardclass: List1dBoard
setmark_by_move
92.7 ns ± 0.211 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
67.7 ns ± 0.111 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
526 μs ± 1.89 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
judge
146 ns ± 1.58 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
2.83 ms ± 18.4 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

board size = 100 boardclass: ArrayBoard
setmark_by_move
128 ns ± 0.873 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
84.1 ns ± 0.107 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
649 μs ± 1.45 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
judge
145 ns ± 0.482 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
3.3 ms ± 117 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

board size = 100 boardclass: NpBoard
setmark_by_move
238 ns ± 13.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
298 ns ± 2.12 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
3.28 ms ± 15.5 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
judge
145 ns ± 0.359 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
1.27 ms ± 3.7 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

board size = 100 boardclass: NpIntBoard
setmark_by_move
161 ns ± 1.17 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
138 ns ± 0.167 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
1.82 ms ± 16.2 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
judge
146 ns ± 1.18 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
1.28 ms ± 22 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

board size = 100 boardclass: NpBoolBoard
setmark_by_move
226 ns ± 8.47 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
217 ns ± 17.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
calc_legal_moves
3.48 ms ± 19.4 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
judge
146 ns ± 1.48 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
350 μs ± 14.2 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

board size = 100 boardclass: BitBoard
setmark_by_move
287 ns ± 0.962 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
getmark_by_move
176 ns ± 0.752 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
calc_legal_moves
13.7 ms ± 1.53 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
judge
179 ns ± 0.839 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
count_markpats
214 μs ± 916 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

以下、それぞれのメソッドについて上記の 実行結果を表にまとめて考察 します。

`setmark_by_move` と `getmark_by_move` メソッドの処理速度の検証

下記は setmark_by_move の処理時間をまとめた表です。表の数値の単位は ns で、桁数が揃うようにに四捨五入しました。

ゲーム盤のサイズ	3	5	10	50	100
`ListBoard`	111	109	110	108	108
`List1dBoard`	94	92	93	92	93
`ArrayBoard`	131	132	129	129	128
`NpBoard`	227	224	232	226	238
`NpIntBoard`	161	159	160	160	161
`NpBoolBoard`	235	223	224	227	226
`BitBoard`	207	233	232	234	287
`BitBoard3x3`	126

下記は getmark_by_move の処理時間をまとめた表です。表の数値の単位は ns で、桁数が揃うようにに四捨五入しました。

ゲーム盤のサイズ	3	5	10	50	100
`ListBoard`	86	84	86	85	85
`List1dBoard`	71	69	71	68	68
`ArrayBoard`	86	87	85	85	84
`NpBoard`	298	298	319	300	298
`NpIntBoard`	140	138	138	141	138
`NpBoolBoard`	208	207	207	208	217
`BitBoard`	152	152	177	179	176
`BitBoard3x3`	99

両者は数値は若干異なりますが、下記のような 似たような性質を持つ 事がわかりました。

BitBoard クラス以外は処理速度はゲーム盤のサイズに影響されない
List1dBoard クラスが最も処理速度が速いが、BitBoard3x3 クラスとの差は大きくない

BitBoard クラス以外 の処理速度が ゲーム盤のサイズに影響されない理由 は、list、array、ndarray の 要素の参照や代入 の 処理速度 が、要素の数に影響されない からです

一方、BitBoard クラスの場合の場合は ゲーム盤のサイズが大きくなる と、ビットボード が表す ビット列のビット長が長く なります。コンピューターの CPU が一度に行うことができるビット演算のビット数が限られている ため、大きな数値のビット演算 を行うと 処理に時間がかかる ようになります。とはいえ、上記の表からわかるように、ゲーム盤のサイズが大きくなっても処理時間は大きくは変わらない ようです。

`calc_legal_moves` メソッドの処理速度の検証

下記は calc_legal_moves の処理時間をまとめた表です。表の数値の単位は μs で、桁数が揃うようにに四捨五入しました。

ゲーム盤のサイズ	3	5	10	50	100
`ListBoard`	1.2	2.4	7.8	168	743
`List1dBoard`	0.7	1.4	4.9	132	526
`ArrayBoard`	0.8	1.8	6.4	165	649
`NpBoard`	3.5	8.8	34.6	789	3280
`NpIntBoard`	2.3	5.2	18.7	435	1820
`NpBoolBoard`	3.3	8.6	33.7	844	3480
`BitBoard`	0.7	1.9	11.3	732	1370
`BitBoard3x3`	0.6

ゲーム盤の大きさが小さい場合 は、全体の処理の中 で関数呼び出しや、変数の初期化処理などの、ゲーム盤の各マス に対する 以外の処理 の 割合が大きくなる ので、処理速度とゲーム盤マスの数の関係 が 明確ではなくなります。そこで、以下ではゲーム盤の マスの数が 100 以上 になる、ゲーム盤のサイズが 10 以上 場合の検証を行います。

ゲーム盤の マスの数 は ゲーム盤のサイズの 2 乗に比例 します。いくつかのマスに着手を行った局面 に対して合法手を計算しているので上記のプログラムで 計算される合法手 は ゲーム盤のサイズの 2 乗にほぼ比例 します。そのため、ゲーム盤のサイズ が 10 と 100 の場合は マスの数が 100 倍 になり、上記の表のいずれの場合も ゲーム盤のサイズ が 10 と 100 の場合で 処理時間が約 10 倍 になっている²ので、上記の結果から 処理時間はゲーム盤のマスの数にほぼ比例する ことがわかります。

ゲーム盤のサイズが 3 の場合は BitBoard3x3 の処理速度が最速 であるのに対し、ゲーム盤のサイズが大きくなると List1dBoard クラスのほうが 処理速度が速くなる のは、先程と同様に ビット数が増えるとビット演算の処理速度が遅くなるから です。

ただし、以前の記事で説明したように、BitBoard クラスの calc_legal_moves はゲーム盤のマスの数ではなく、合法手の数だけ繰り返し処理を行う ので 合法手が少ないほど処理時間が高速 になります。下記はそのことを確認するプログラムで、以下の条件で 合法手が上記よりも大幅に少ない局面 に対する List1dBoard と BitBoard クラスの calc_legal_moves の処理時間を計測 します。実行結果からこの場合は BitBoard クラスのほうが List1dBoard クラスよりも 処理速度が約 2 倍になる ことが確認できます。また、List1dBoard クラス場合の 処理時間 は 上記の 526 μs とほとんど変わらない ので、合法手の数によって処理時間がほとんど影響されない ことも確認できました。

ゲーム盤のサイズを 100 とする
どちらも勝利しないようにするために、一番右の列と、一番下の 2 つの行を除いた、偶数行に〇を、奇数行に × を配置する。

board_size = 100
for boardclass in [List1dBoard, BitBoard]:
    print(f"boardclass: {boardclass.__name__}")
    mb = Marubatsu(boardclass=boardclass, board_size=board_size)
    for i in range(board_size - 1):
        for j in range(int(board_size / 2) - 1):
            mb.cmove(i, j * 2)
            mb.cmove(i, j * 2 + 1)
    print("calc_legal_moves")
    %timeit mb.calc_legal_moves()

実行結果

boardclass: List1dBoard
calc_legal_moves
512 μs ± 10.3 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
boardclass: BitBoard
calc_legal_moves
290 μs ± 1.53 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

このことから、BitBoard クラスの calc_legal_moves は 合法手の数が少ない場合は最速 になるため、平均的に見ると List1dBoard とあまり変わらない ことがわかりました。

`judge` メソッドの処理速度の検証

下記は judge の処理時間をまとめた表です。表の数値の単位は ns で、桁数が揃うようにに四捨五入しました。

ゲーム盤のサイズ	3	5	10	50	100
`ListBoard`	146	144	146	144	147
`List1dBoard`	160	157	160	147	146
`ArrayBoard`	160	159	164	145	145
`NpBoard`	147	148	146	146	145
`NpIntBoard`	146	146	145	146	146
`NpBoolBoard`	146	146	147	145	146
`BitBoard`	188	179	180	178	179
`BitBoard3x3`	139

上記の表から以下の事がわかりました。

いずれの場合も処理速度はゲーム盤のサイズに影響されない
3 x 3 サイズに特化した BitBoard3x3 クラスが最速であるので、他のサイズの場合もそのサイズに特化したビットボードのクラスを作成すればほぼ最速になる可能性が高い

`count_markpats` メソッドの処理速度の検証

下記は count_markpats の処理時間をまとめた表です。表の数値の単位は μs で、桁数が揃うようにに四捨五入しました。

ゲーム盤のサイズ	3	5	10	50	100
`ListBoard`	10.1	17	42.3	589	2170
`List1dBoard`	10.4	18.3	45.8	754	2830
`ArrayBoard`	10.6	19.1	48.9	828	3300
`NpBoard`	20.0	28.8	53.8	400	1270
`NpIntBoard`	20.0	28.6	53.4	403	1280
`NpBoolBoard`	17.8	24.3	39.9	170	350
`BitBoard`	3.1	4.3	8.2	52	214
`BitBoard3x3`	2.9

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

一定以上要素の数が多くなると list よりも ndarray の方が処理速度が速い
ビットボードを利用した場合が常に最速である

ゲーム盤のサイズが n の場合は count_markpats は n 列、n 行、2 つの対角線 の n 個 のマスの マークの数を数える ので、$n^2 + n^2 + 2n = \boldsymbol{2n^{2} + 2{n}}$ 個のマスの マークの数を数える という計算を行います。n が大きい場合は と $\boldsymbol{2n}$ は $\boldsymbol{2n^2}$ と 比較して小さな値になる³ ので、数えるマスの数 を約 $\boldsymbol{2n^2}$ 個と 考えても良い でしょう。そのため、処理時間 は マスの数にほぼ比例 することが 予想されます。

そこで、マスの数が多い ゲーム盤の サイズが 50 と 100 の場合の処理時間 でそのことを 検証してみる ことにします。下記は ゲーム盤のサイズが 100 の場合の 処理時間 を ゲーム盤のサイズが 50 の場合の 処理時間 で 割った値を計算 した表です。ゲーム盤の サイズが 50 と 100 では マスの数が 4 倍 になり、実際に下記の表では numpy を利用した場合を除いて 処理時間もほぼ 4 倍 になっていることが確認できます。

	100 の処理時間 ÷ 50 の処理時間
`ListBoard`	3.7
`List1dBoard`	3.8
`ArrayBoard`	4.0
`NpBoard`	3.2
`NpIntBoard`	3.2
`NpBoolBoard`	2.1
`BitBoard`	4.1

numpy の関数の性質

numpy を利用 したクラスの count_markpats の 処理時間 が マスの数に比例しないように見える理由 について説明します。

以前の記事で 様々なデータ型 と 様々な要素数 の np.sum の処理速度を検証 しましたが、その際に計測した ndarray の 要素の数 は 10、100、1000、10000、100000 のような たった 5 つの間の離れた値 だったので、今回の記事では count_markpats 内で利用 している np.count_nonzero の処理速度と要素数の関係 について より詳しく検証 することにします。

下記は、10 刻みで 10 ~ 1000 までの要素 を持つ ndarray に対して np.count_nonzero の処理時間の平均 を timeit モジュールの関数 を利用して計測して グラフで表示 するプログラムです。timeit モジュール の関数の利用方法を忘れた方は以前の記事を復習して下さい。

7、8 行目：timeit モジュールで計算を行う回数の設定。全体の処理が 10 分くらいで終了する値を設定した
9、10 行目：要素の数と、処理時間を記録する変数を空の list で初期化する
11 ~ 17 行目：10 ~ 1000 まで 10 刻みで繰り返し処理を行う
12 行目：要素が size ですべての要素が 0 の ndarray を作成する
13 ~ 15 行目：np.count_nonzero(ndarray) の処理時間を timeit.repeat を利用して計測する。計測された処理時間の単位は秒なので、15 行目では処理時間の単位を μs にするために 1000000 を乗算した
16、17 行目：ndarray の要素の数と、処理時間の平均を mean で計算して記録する
19 ~ 22 行目：計算した結果をグラフで表示する

 1  import japanize_matplotlib
 2  import numpy as np
 3  import timeit
 4  from statistics import mean
 5  import matplotlib.pyplot as plt
 6  
 7  number = 1000000
 8  repeat = 7
 9  sizelist = []
10  timelist = []
11  for size in range(10, 1001, 10):
12      ndarray = np.zeros((size, ))
13      stmt = "np.count_nonzero(ndarray)"
14      result = timeit.repeat(stmt=stmt, number=number, repeat=repeat, globals=locals())
15      result = [time / number * 1000000 for time in result]
16      sizelist.append(size)
17      timelist.append(mean(result))
18  
19  plt.ylabel("処理時間(μs)")
20  plt.xlabel("要素の数")
21  plt.ylim(0, 1.5)
22  plt.plot(sizelist, timelist)

行番号のないプログラム

import japanize_matplotlib
import numpy as np
import timeit
from statistics import mean
import matplotlib.pyplot as plt

number = 1000000
repeat = 7
sizelist = []
timelist = []
for size in range(10, 1001, 10):
    ndarray = np.zeros((size, ))
    stmt = "np.count_nonzero(ndarray)"
    result = timeit.repeat(stmt=stmt, number=number, repeat=repeat, globals=locals())
    result = [time / number * 1000000 for time in result]
    sizelist.append(size)
    timelist.append(mean(result))
    
plt.ylabel("処理時間(μs)")
plt.xlabel("要素の数")
plt.ylim(0, 1.5)
plt.plot(sizelist, timelist)

実行結果

実行結果のグラフはほぼ 直線のグラフ になっているので、要素の数を $\boldsymbol{n}$ とした場合の np.count_nonzero の 処理時間 は $\boldsymbol{an + b}$ という式 で表されます。

グラフから $\boldsymbol{n=10}$ の場合は 約 0.35 μs、$\boldsymbol{n=1000}$ の場合は 約 1.2 μs なので、この式は $\boldsymbol{0.00085n + 0.35}$ μs という式で 近似される ことがわかります。

この式から以下の事がわかります。

要素の数に関わらず 0.35 μs の 処理時間がかかる
0.35 μs の 処理時間を除く と 要素の数に比例した処理時間 がかかる

そのため、要素の数が小さい場合 はこの 0.35 μs があるため に 要素の数に比例しない ようになりますが、要素の数が大きくなる と 要素の数にほぼ比例 するようになります。

下記は いくつかの要素の数 とその 処理時間 を 上記の式で計算 した表です。要素の数 が 10、100 のように 小さい場合 は 要素の数が 10 倍 になっても 処理時間は数倍 にしかなりませんが、要素の数 が 10000 以上のように 大きくなる と処理時間が ほぼ 10 倍 になります。

要素の数	10	100	1000	10000	100000	1000000
処理時間（μs）	0.3585	0.435	1.20	8.85	85.35	850.35
左隣との倍率		1.21	2.76	7.38	9.64	9.96

先程示したように ndarray を利用したクラスの count_markpats の 50 と 100 のサイズ のゲーム盤の 処理時間が 4 倍にならない理由 は、要素の数が少ない からです。

このような性質は 他の numpy の多くの関数も同様 で、要素の数に関わらず一定の処理時間が必要 になるため、要素の数が小さい場合 は 要素当たりの処理時間が長くなります。

一般的 に numpy の関数 の 処理の効率 が 要素の数が多い程高くなる と言われる理由は この性質があるから ではないかと思います。ただし、すべての numpy の関数 が 同様の性質を持つとは限らない 点に注意して下さい。

numpy を利用したクラスの calc_legal_moves メソッドが行う計算は、要素の数 によって 処理速度が変わらない ndarray の要素の参照 による計算を マスの数だけ行います。そのため、マスの数にほぼ比例した処理時間 がかかります。

検証結果のまとめ

上記の検証から、以下の事がわかりました。

ゲーム盤を表すクラスのメソッドの 処理速度 には以下の性質を持つものがある
- 処理速度がゲーム盤の 大きさに関係しない
- 処理速度がゲーム盤の マスの数 または 合法手 の数に ほぼ比例 する。ただし、ndarray の場合は マスの数が小さい場合 は 比例よりも緩やかに上昇する
ビットボード を利用した場合の処理は以下の性質を持つ
- すべての場合で最速になるわけではないが、最速でない場合でも ほぼ最速に近い
- 合法手の一覧の計算 は 合法手の数が少ない場合 は 他よりも大幅に高速 になる
- count_markpats の処理速度は 最速である

また、setmark_by_move や getmark_by_move のような 単純な処理 は ビットボード を利用しても 処理速度は大幅に向上しません が、count_markpats のような 複雑な処理をビット演算で高速に行うことができる場合 は 処理速度が大幅に向上する ことが確認できました。

今回の記事のまとめ

今回の記事では 任意の大きさのゲーム盤に対応 するように修正しました。また、修正した各メソッドの処理速度 を 他のゲーム盤を表すクラス と 比較して検証 を行いました。

次回の記事では残りのメソッドの修正を行います。

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

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

次回の記事

ai14s VS ai2 のほうは若干遅くなっているようですが、行っている計算処理は変わっていないのでおそらく誤差の範囲ではないかと思います ↩
ゲーム盤のサイズが 10 と 50 の場合はマスの数が 25 倍になりますが、100 倍と比べて処理時間が 25 倍であることは見た目からはわかりづらいので 10 と 100 の場合の説明をしました。興味がある方は 10 と 50 の場合で処理時間が約 25 倍になっていることを確認してみて下さい ↩
例えば $n = 100$ の場合は $2n = 200$、$2n^2 = 20000$ のように 1/100 になります ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Pythonで〇×ゲームのAIを一から作成する その216 任意の大きさのゲーム盤に対応した BitBoard クラスの修正

目次と前回の記事

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

任意の大きさのゲーム盤に対応した BitBoard クラスの修正

修正する必要がないメソッド

is_winner メソッドで利用するビットマスクの一覧の計算

ビットマスクの一覧の計算方法

ビットマスクの一覧の参照テーブルの記録の方法

Marubatsu クラスの処理が原因となる問題点

プログラムの修正方法

BitBoard クラスの __init__ メソッドの修正

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

Marubatsu クラスの __init__ メソッドの修正

Marubatsu クラスの __restart__ メソッドの修正

BitBoard クラスの is_winner メソッドの修正

judge メソッドの処理の確認

合法手の一覧の計算に必要なビットマスクの計算

__init__ メソッドの修正

calc_legal_moves メソッドの修正

ai2 VS ai2 の処理速度の確認

count_markpats で利用するビットマスクの計算

__init__ メソッドの修正

count_markpats メソッドの修正

ai14s VS ai2 の処理速度の確認

処理速度の比較

ゲーム盤を表すクラスの修正

処理速度の比較と検証

setmark_by_move と getmark_by_move メソッドの処理速度の検証

calc_legal_moves メソッドの処理速度の検証

judge メソッドの処理速度の検証

count_markpats メソッドの処理速度の検証

numpy の関数の性質

検証結果のまとめ

今回の記事のまとめ

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その216　任意の大きさのゲーム盤に対応した BitBoard クラスの修正

`is_winner` メソッドで利用するビットマスクの一覧の計算

BitBoard クラスの `init` メソッドの修正

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

Marubatsu クラスの `init` メソッドの修正

Marubatsu クラスの `restart` メソッドの修正

BitBoard クラスの `is_winner` メソッドの修正

`judge` メソッドの処理の確認

`init` メソッドの修正

`calc_legal_moves` メソッドの修正

`ai2` VS `ai2` の処理速度の確認

`count_markpats` で利用するビットマスクの計算

`init` メソッドの修正

`count_markpats` メソッドの修正

`ai14s` VS `ai2` の処理速度の確認

`setmark_by_move` と `getmark_by_move` メソッドの処理速度の検証

`calc_legal_moves` メソッドの処理速度の検証

`judge` メソッドの処理速度の検証

`count_markpats` メソッドの処理速度の検証