目次と前回の記事

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

NpBoard クラスの改良

前回の記事では numpy モジュールが提供する ndarray という配列で表現されたデータを利用してゲーム盤を表す NpBoard クラスを定義しました。ndarray は list と同様 に 添字を利用して要素の参照と代入 を行うことができるので、NpBoard クラスの処理は ゲーム盤を表すデータを ndarray で表現する以外 の部分は ListBoard クラスと完全に同じ です。

前回の記事で検証したように、残念ながら 要素の参照と代入処理 は ndarray のほうが list よりも遅い ため、NpBoard クラスの 処理速度 は ListBoard クラスの処理速度よりも かなり遅い ことが確認されました。

NpBoard の処理速度を改善するための改良を色々試してみたのですが、残念ながら大きな改善を行うことはできませんでした。ただし、ndarray を利用 することで プログラムをわかりやすく記述 することができるので、今回の記事では ndarray を利用した場合の 処理速度の改善方法 と、プログラムを わかりやすく記述する方法 について紹介することにします。

`np.full` を利用した ndarray の生成

NpBoard では下記のプログラムのように、ゲーム開始時の局面を表す 2 次元の list を np.array の実引数に記述 することで ndarray を生成 します。

self.board = np.array([[Marubatsu.EMPTY] * self.BOARD_SIZE for y in range(self.BOARD_SIZE)])

ゲーム開始時の局面のように、同じ値（Marubatsu.EMPTY）を要素として持つ ndarray は numpy モジュールで定義された full という関数に 下記の実引数を記述することで作成 することができます。なお、以後は numpy で定義された関数を np.full のように記述 することにします。

第一引数 には ndarray の 形状（shape）を表す tuple を記述する
第二引数 には作成する ndarray の 要素を記述 する

〇× ゲームの ゲーム盤のサイズは 3 × 3 なので、ndarray の形状 は (3, 3) という tuple で表現されます。従って、ゲーム開始時の局面を表す ndarray は下記のプログラムで作成することができます。

from marubatsu import Marubatsu
import numpy as np

board = np.full((3, 3), Marubatsu.EMPTY)
print(board)

実行結果

[['.' '.' '.']
 ['.' '.' '.']
 ['.' '.' '.']]

下記は ゲーム開始時のゲーム盤を表す ndarray を list から作成 する場合と np.full で作成 する場合の 処理時間を計測 するプログラムです。実行結果から np.full のほうが 処理時間が約半分 になることが確認できます。

%timeit np.array([[Marubatsu.EMPTY] * 3 for y in range(3)])
%timeit np.full((3, 3), Marubatsu.EMPTY)

実行結果

2.71 μs ± 28.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
1.39 μs ± 31 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

np.full の詳細については下記のリンク先を参照して下さい。

同様の関数に すべての要素を 0 とする ndarray を作成する np.zeros、すべての要素を 1 とする ndarray を作成する np.ones があり、良く使われているようです。下記は すべての要素が 0 の 3 x 3 の 2 次元の ndarray を作成するプログラムです。

print(np.zeros((3, 3)))

実行結果

[[0. 0. 0.]
 [0. 0. 0.]
 [0. 0. 0.]]

np.zeros と np.ones の詳細については下記のリンク先を参照して下さい。

`init` メソッドの修正

下記のプログラムの 6 行目のように np.full を利用して ゲーム盤の開始時の局面を表す ndarray を作成 するように __init__ メソッドを修正します。

1  from marubatsu import NpBoard
2  
3  def __init__(self, board_size=3, count_linemark=False):
4      self.BOARD_SIZE = board_size
5      self.count_linemark = count_linemark
6      self.board = np.full((self.BOARD_SIZE, self.BOARD_SIZE), Marubatsu.EMPTY)
元と同じなので省略
7          
8  NpBoard.__init__ = __init__

行番号のないプログラム

from marubatsu import NpBoard

def __init__(self, board_size=3, count_linemark=False):
    self.BOARD_SIZE = board_size
    self.count_linemark = count_linemark
    self.board = np.full((self.BOARD_SIZE, self.BOARD_SIZE), Marubatsu.EMPTY)
    if self.count_linemark:
        self.rowcount = {
            Marubatsu.CIRCLE: [0] * self.BOARD_SIZE,
            Marubatsu.CROSS: [0] * self.BOARD_SIZE,
        }
        self.colcount = {
            Marubatsu.CIRCLE: [0] * self.BOARD_SIZE,
            Marubatsu.CROSS: [0] * self.BOARD_SIZE,
        }
        self.diacount = {
            Marubatsu.CIRCLE: [0] * 2,
            Marubatsu.CROSS: [0] * 2,
        }
        
NpBoard.__init__ = __init__

修正箇所

from marubatsu import NpBoard

def __init__(self, board_size=3, count_linemark=False):
    self.BOARD_SIZE = board_size
    self.count_linemark = count_linemark
-   self.board = np.array([[Marubatsu.EMPTY] * self.BOARD_SIZE for y in range(self.BOARD_SIZE)])
+   self.board = np.full((self.BOARD_SIZE, self.BOARD_SIZE), Marubatsu.EMPTY)
元と同じなので省略
        
NpBoard.__init__ = __init__

上記の修正後に下記のプログラムで ベンチマークのプログラムを実行 します。

from util import benchmark

boardclass = NpBoard
for count_linemark in [False, True]:
    print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
    benchmark(mbparams={"boardclass": boardclass, "count_linemark": count_linemark})
    print()

実行結果

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

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

ai14s VS ai2
100%|██████████| 50000/50000 [01:18<00:00, 639.81it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

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

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

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

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

ai14s VS ai2
100%|██████████| 50000/50000 [00:32<00:00, 1540.64it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

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

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

下記は前回の記事での 上記の修正を行う前の NpBoard を利用した場合のベンチマークの結果に 上記の実行結果を加えた表 です。上段が前回の記事、下段が np.full を利用 した場合の値を表します。

`count_linemark`	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
`False`	5924.49 回/秒 6050.94 回/秒	633.71 回/秒 639.81 回/秒	42.9 ms 43.9 ms
`True`	6832.91 回/秒 7087.24 回/秒	1475.99 回/秒 1540.64 回/秒	43.2 ms 42.7 ms

上記から、いずれの場合も処理速度がほとんど変わらない ことが確認できます。これは、__init__ メソッドが ゲームの開始時に 1 回しか呼び出されない ため 1 回の対戦の中で占める処理時間の割合が非常に小さい からです。そのことを 計算で示します。

上記の結果から count_linemark が False の場合の ai2 VS ai2 の対戦の場合は、先手と後手を入れ替えて 1 秒間に約 5000 回実行 されるので、1 回あたりの対戦の処理時間 は 1 ÷ 10000 = 約 0.0001 秒 = 約 0.1 ms です。一方、先程の計測結果から np.full を利用した場合に短縮される処理時間 は 2.71 - 1.39 = 約 1.32 μs = 約 0.00132 ms なので、全体の処理時間の約 100 分の 1 に過ぎない ことがわかります。

残念ならが np.full によって処理時間の違いはほとんど生じませんでしたが、プログラムを わかりやすく簡潔に記述できる のでこのまま np.full を採用 することにします。

tuple による要素の参照と代入

2 次元の ndarray は下記のプログラムのように 2 つの要素を持つ tuple を添字に記述 することで 要素の参照と代入を行う ことができます。なお、3 行目のように tuple の () を省略するのが一般的 だと思いますので、以後はそのようにプログラムを記述することにします。

print(board[(1, 0)])
board[(1, 0)]= Marubatsu.CIRCLE
print(board[1, 0])
print(board)

実行結果

.
o
[['.' '.' '.']
 ['o' '.' '.']
 ['.' '.' '.']]

2 次元以上の ndarray の要素の 参照や代入 を行う際に、添字を複数記述するよりも 1 つの tuple で記述したほうが処理速度が速く なります。下記はそのことを検証するプログラムです。実行結果から 参照と代入のいずれの場合 も 添字に 1 つの tuple を記述 したほうが 処理速度が速くなる ことが確認できます。

%timeit board[1][0]
%timeit board[1, 0]
%timeit board[1][0] = Marubatsu.CIRCLE
%timeit board[1, 0] = Marubatsu.CIRCLE

実行結果

342 ns ± 12.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
229 ns ± 2.34 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
255 ns ± 2.07 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
148 ns ± 2.59 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

上記のようなことが起きる理由は、ndarray が 内部では 1 次元の配列でデータを記録 しているからです。そのため、2 次元以上の ndarray に対して 2 つ以上の添字で要素の参照や代入を行う際に、以前の記事で行っていたように __getitem__ メソッドで別のクラスのインスタンス作成__ して返すという処理を行っているからです。

そのことは下記の numpy のドキュメント内で以下のように説明されています。

So note that x[0, 2] == x[0][2] though the second case is more inefficient as a new temporary array is created after the first index that is subsequently indexed by 2.

筆者意訳：x[0, 2] と x[0][2] は等しいが、x[0][2] は x[0] の処理を行う際に新しい配列を一時的に作成するため x[0, 2] のほうが効率が良い。

添字の tuple への修正

要素の参照と代入処理 を行う際に tuple を添字に記述 するようにプログラムを修正します。

下記はそのような修正を行うプログラムです。修正の説明と修正箇所 は NpBoard クラスの継承元の ListBoard クラスのメソッドとの違い です。

4 行目の下にあった x, y = move を削除した
16 行目：15 行目の前にあった x, y = move は count_linemark が True の場合のみ行う必要があるので 16 行目に移動した
5、17、18 行目：[x][y] を [move] に修正した
10、25、31、41 行目：2 つの添字の記述を tuple による 1 つの添字の記述に修正した

 1  from marubatsu import Markpat
 2  from collections import defaultdict
 3  
 4  def getmark_by_move(self, move):
 5      return self.board[move]    
 6  
 7  NpBoard.getmark_by_move = getmark_by_move
 8  
 9  def getmark(self, x, y):
10      return self.board[x, y]
11  
12  NpBoard.getmark = getmark
13  
14  def setmark_by_move(self, move, mark):
15      if self.count_linemark:
16          x, y = move
元と同じなので省略
17              changedmark = self.board[move]
元と同じなので省略
18      self.board[move] = mark
19      
20  NpBoard.setmark_by_move = setmark_by_move
21  
22  def calc_legal_moves(self):
23      legal_moves = [(x, y) for y in range(self.BOARD_SIZE) 
24                          for x in range(self.BOARD_SIZE)
25                          if self.board[x, y] == Marubatsu.EMPTY]
26      return legal_moves    
27      
28  NpBoard.calc_legal_moves = calc_legal_moves
29  
30  def is_same(self, mark, x, y, dx, dy):
31      text_list = [self.board[x + i * dx, y + i * dy] 
32                      for i in range(self.BOARD_SIZE)]
33      line_text = "".join(text_list)
34      return line_text == mark * self.BOARD_SIZE
35      
36  NpBoard.is_same = is_same  
37  
38  def count_marks(self, turn, last_turn, x, y, dx, dy, datatype):
39      count = defaultdict(int)
40      for _ in range(self.BOARD_SIZE):
41          count[self.board[x, y]] += 1
元と同じなので省略
42      
43  NpBoard.count_marks = count_marks

行番号のないプログラム

from marubatsu import Markpat
from collections import defaultdict

def getmark_by_move(self, move):
    return self.board[move]    

NpBoard.getmark_by_move = getmark_by_move

def getmark(self, x, y):
    return self.board[x, y]

NpBoard.getmark = getmark

def setmark_by_move(self, move, mark):
    if self.count_linemark:
        x, y = move
        if mark != Marubatsu.EMPTY:
            diff = 1
            changedmark = mark
        else:
            diff = -1
            changedmark = self.board[move]
        self.colcount[changedmark][x] += diff
        self.rowcount[changedmark][y] += diff
        if x == y:
            self.diacount[changedmark][0] += diff
        if x + y == self.BOARD_SIZE - 1:
            self.diacount[changedmark][1] += diff
    self.board[move] = mark
    
NpBoard.setmark_by_move = setmark_by_move

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

def is_same(self, mark, x, y, dx, dy):
    text_list = [self.board[x + i * dx, y + i * dy] 
                    for i in range(self.BOARD_SIZE)]
    line_text = "".join(text_list)
    return line_text == mark * self.BOARD_SIZE
    
NpBoard.is_same = is_same  

def count_marks(self, turn, last_turn, x, y, dx, dy, datatype):
    count = defaultdict(int)
    for _ in range(self.BOARD_SIZE):
        count[self.board[x, y]] += 1
        x += dx
        y += dy

    if datatype == "dict":
        return count
    else:
        return Markpat(count[last_turn], count[turn], count[Marubatsu.EMPTY])
    
NpBoard.count_marks = count_marks

修正箇所

from marubatsu import Markpat
from collections import defaultdict

def getmark_by_move(self, move):
-   x, y = move
-   return self.board[x][y]    
+   return self.board[move]    

NpBoard.getmark_by_move = getmark_by_move

def getmark(self, x, y):
-   return self.board[x][y]
+   return self.board[x, y]

NpBoard.getmark = getmark

def setmark_by_move(self, move, mark):
-   x, y = move
    if self.count_linemark:
+       x, y = move
元と同じなので省略
-           changedmark = self.board[x][y]
+           changedmark = self.board[move]
元と同じなので省略
-   self.board[x][y] = mark
+   self.board[move] = mark
    
NpBoard.setmark_by_move = setmark_by_move

def calc_legal_moves(self):
    legal_moves = [(x, y) for y in range(self.BOARD_SIZE) 
                        for x in range(self.BOARD_SIZE)
-                       if self.board[x][y] == Marubatsu.EMPTY]
+                       if self.board[x, y] == Marubatsu.EMPTY]
    return legal_moves    
    
NpBoard.calc_legal_moves = calc_legal_moves

def is_same(self, mark, x, y, dx, dy):
-   text_list = [self.board[x + i * dx][y + i * dy] 
+   text_list = [self.board[x + i * dx, y + i * dy] 
                    for i in range(self.BOARD_SIZE)]
    line_text = "".join(text_list)
    return line_text == mark * self.BOARD_SIZE
    
NpBoard.is_same = is_same  

def count_marks(self, turn, last_turn, x, y, dx, dy, datatype):
    count = defaultdict(int)
    for _ in range(self.BOARD_SIZE):
-       count[self.board[x][y]] += 1
+       count[self.board[x, y]] += 1
元と同じなので省略
    
NpBoard.count_marks = count_marks

上記の修正後に下記のプログラムでベンチマークのプログラムを実行します。

for count_linemark in [False, True]:
    print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
    benchmark(mbparams={"boardclass": boardclass, "count_linemark": count_linemark})
    print()

実行結果

boardclass: NpBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:06<00:00, 7252.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%

ai14s VS ai2
100%|██████████| 50000/50000 [01:08<00:00, 726.09it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

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

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

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

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

ai14s VS ai2
100%|██████████| 50000/50000 [00:30<00:00, 1657.19it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

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

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

下記は先ほどの表に上記の実行結果を加えた表です。

`count_linemark`	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
`False`	5924.49 回/秒 6050.94 回/秒 7252.75 回/秒	633.71 回/秒 639.81 回/秒 726.09 回/秒	42.9 ms 43.9 ms 39.5 ms
`True`	6832.91 回/秒 7087.24 回/秒 8313.93 回/秒	1475.99 回/秒 1540.64 回/秒 1657.19 回/秒	43.2 ms 42.7 ms 38.8 ms

実行結果から いずれの場合も処理速度が若干向上 したことが確認できます。これは、一回の対戦 で 要素の参照と代入処理が何度も行われる ためです。

`is_same` の処理の改良

count_linemark が False の場合の 勝敗判定の処理 では、下記の is_same というメソッドを利用して縦、横、斜め方向の 直線上に同じマークが並んでいるかどうかを判定 します。

def is_same(self, mark, x, y, dx, dy):
    text_list = [self.board[x + i * dx, y + i * dy] 
                    for i in range(self.BOARD_SIZE)]
    line_text = "".join(text_list)
    return line_text == mark * self.BOARD_SIZE

この処理では直線上の 最初のマスの座標 を仮引数 x と y、直線上の 次のマス x, y 座標の差分 を仮引数 dx と dy に代入することで直線上の各マスの座標を計算するという処理を行っています。ndarray を利用する場合 はこの処理を 簡潔に記述 することができます。

2 次元の list に対するスライス表記の利用

最初に is_same メソッドが上記のような処理を記述している理由について説明します。

〇×ゲームのゲーム盤を表す 2 次元の list の x 列のマスの一覧を表す list は、下記のプログラムのように board[x] で参照することができます

1 行目：2 次元の list でゲーム盤を表す ListBoard クラスを利用した Marubatsu クラスのインスタンスを作成する
2 ~ 4 行目：各列の値が異なるようにいくつかの着手を行う
5 行目：確認のためゲーム盤を表示する
6 ~ 8 行目：0 ~ 2 列を表す list を表示する

1  mb = Marubatsu()
2  mb.cmove(0, 0)
3  mb.cmove(1, 0)
4  mb.cmove(0, 1)
5  print(mb)
6  print(mb.board.board[0])
7  print(mb.board.board[1])
8  print(mb.board.board[2])

行番号のないプログラム

mb = Marubatsu()
mb.cmove(0, 0)
mb.cmove(1, 0)
mb.cmove(0, 1)
print(mb)
print(mb.board.board[0])
print(mb.board.board[1])
print(mb.board.board[2])

実行結果

Turn x
ox.
O..
...

['o', 'o', '.']
['x', '.', '.']
['.', '.', '.']

以前の記事で説明したように、添字に : という スライス表記を記述 することで すべての要素を表す ことができるので、上記のプログラムは下記のプログラムのように記述することができ、実行結果から 上記と同じ表示が行われる ことが確認できます。

print(mb.board.board[0][:])
print(mb.board.board[1][:])
print(mb.board.board[2][:])

実行結果

['o', 'o', '.']
['x', '.', '.']
['.', '.', '.']

このことから、下記のプログラムのように x 座標 を表す 最初の添字に : を記述 することで y 行のデータを表示できると思った人がいるかもしれませんが、実行結果のように上記と同じ 列のデータが表示 されてしまいます。

print(mb.board.board[:][0])
print(mb.board.board[:][1])
print(mb.board.board[:][2])

実行結果

['o', 'o', '.']
['x', '.', '.']
['.', '.', '.']

上記のような処理が行われる理由は、mb.board.board[:] によって参照されるデータが、mb.board.board のすべての要素 であるため、下記のプログラムのように mb.board.board と同じデータが参照 されるからです。

print(mb.board.board[:])
print(mb.board.board)

実行結果

[['o', 'o', '.'], ['x', '.', '.'], ['.', '.', '.']]
[['o', 'o', '.'], ['x', '.', '.'], ['.', '.', '.']]

上記から 2 次元の list でゲーム盤のデータを表現した場合は、x 列のデータは board[x][:] で参照 できますが、y 行のデータ は そのようなスライス表記を利用して参照することはできません。また、斜め方向 の直線上のマスを スライス表記で参照することはできない ので、is_same を先ほどのように定義しました。

2 次元の ndarray に対するスライス表記の利用

ndarray に対しても下記のプログラムのように x 列のデータ は mbnp.board[x] や mbnp.board[x][:] で参照することができます。また、先程説明したように mbnp.board[x, :] という 1 つの tuple を添字に記述して参照 することもできます。

mbnp = Marubatsu(boardclass=NpBoard)
mbnp.cmove(0, 0)
mbnp.cmove(1, 0)
mbnp.cmove(0, 1)
print(mbnp)
print(mbnp.board.board[0])
print(mbnp.board.board[1])
print(mbnp.board.board[2])
print(mbnp.board.board[0][:])
print(mbnp.board.board[1][:])
print(mbnp.board.board[2][:])
print(mbnp.board.board[0, :])
print(mbnp.board.board[1, :])
print(mbnp.board.board[2, :])

実行結果

Turn x
ox.
O..
...

['o' 'o' '.']
['x' '.' '.']
['.' '.' '.']
['o' 'o' '.']
['x' '.' '.']
['.' '.' '.']
['o' 'o' '.']
['x' '.' '.']
['.' '.' '.']

また、ndarray は list とは異なる方法で添字の処理を行う ので、y 行のデータ は下記のプログラムのように mbnp.board[:, y] で参照 することができます。これが、2 次元の list と 2 次元の ndarray の大きな違い です。

print(mbnp.board.board[:, 0])
print(mbnp.board.board[:, 1])
print(mbnp.board.board[:, 2])

実行結果

['o' 'x' '.']
['o' '.' '.']
['.' '.' '.']

また、1 次元の ndarray に対して "".join を利用することで 要素の文字列を連結 したデータを計算することができます。下記は 0 列と 0 行 の 文字列を連結 するプログラムです。

print("".join(mbnp.board.board[0, :]))
print("".join(mbnp.board.board[:, 0]))

実行結果

oo.
ox.

従って、x 列 と y 行 に 同じマークが並んでいるかを判定 する処理を下記のプログラムのように is_same を利用せずに簡潔に記述 することができます。

# x 列に `player` のマークが並んでいるかを表す条件式
"".join(self.board[x, :]) == player * self.BOARD_SIZE
# y 行に `player` のマークが並んでいるかを表す条件式
"".join(self.board[:, y]) == player * self.BOARD_SIZE

下記のプログラムで 0 列と 0 行 に対する上記と is_same の 処理速度を計測 すると、実行結果から スライス表記を利用したほうが処理速度が若干遅くなる ことが確認できます。

player = Marubatsu.CIRCLE
print("0 列の計算")
%timeit mbnp.board.is_same(player, x=0, y=0, dx=1, dy=0)
%timeit "".join(mbnp.board.board[0, :]) == player * mb.BOARD_SIZE
print("0 行の計算")
%timeit mbnp.board.is_same(player, x=0, y=0, dx=0, dy=1)
%timeit "".join(mbnp.board.board[:, 0]) == player * mb.BOARD_SIZE

実行結果

0 列の計算
1.32 μs ± 23.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.63 μs ± 29.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
0 行の計算
1.3 μs ± 23.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.73 μs ± 40.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

ndarray に対する `"".join` による結合処理の改善

上記から、スライス表記を利用しないほうが良いと思った方がいるかもしれませんが、下記のプログラムの実行結果から 1.34 μs = 1340 ns なので 直線上のマスを表すデータの計算 に関しては スライス表記を利用 したほうが 処理速度が約 7 倍ほど速くなります。

1 ~ 4 行目：mbnp.board.is_same(player, x=0, y=0, dx=1, dy=0) の処理を行う際に必要となる変数に値を代入する
5 行目：is_same 内と同じ方法で 0 列のマスを表す list の計算の処理時間を計測する
6 行目：スライス表記で 0 列のマスを表す ndarray の計算の処理時間を計測する

1  x = 0
2  y = 0
3  dx = 1
4  dy = 0
5  %timeit [mbnp.board.board[x + i * dx][y + i * dy]  for i in range(mbnp.BOARD_SIZE)]
6  %timeit mbnp.board.board[0, :]

行番号のないプログラム

x = 0
y = 0
dx = 1
dy = 0
%timeit [mbnp.board.board[x + i * dx][y + i * dy]  for i in range(mbnp.BOARD_SIZE)]
%timeit mbnp.board.board[0, :]

実行結果

1.34 μs ± 56.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
190 ns ± 12.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

上記の結果に反してスライス表記を利用したほうが先程の処理時間が長くなる理由は、"".join による 文字列の連結処理 が原因です。is_same を利用する場合は list の要素 に対する文字列の連結処理を行うのに対し、スライス表記 を利用する場合は ndarray の要素 に対する文字列の連結処理を行う点が異なります。以前の記事で説明したように、連結処理の際に行われる 要素の参照 の処理は list のほうが高速に行われる ため、文字列の連結処理を含める と スライス表記 を利用した場合の方が 処理速度が遅くなります。

この問題は、ndarray を list に変換 してから文字列の連結処理を行うことで解決できます。ndarray にはデータを list に変換する tolist というメソッドがあり、下記のプログラムで 0 列のマークを連結 した ndarray を list に変換する処理 を記述することができます。実行結果の 要素が , で区切られている ことから list に変換されていることが確認 できます。

print(mbnp.board.board[0, :].tolist())

実行結果

['o', 'o', '.']

下記は 上記で計算した list を利用して 0 列に〇が並んでいるかを判定 する処理の 処理時間を計測 するプログラムです。先ほどの list に変換しない場合 の 1.63 μs よりも 処理時間が約 1/4 になり、is_same を利用した場合の 1.32 μs よりも高速になった ことが確認できます。

%timeit "".join(mbnp.board.board[0, :].tolist()) == "ooo"

実行結果

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

list の実引数に ndarray を記述することで ndarray を list に変換することもできますが、下記のプログラムの実行結果のように tolist を利用したほうが高速 です。

%timeit list(mbnp.board.board[0, :])
%timeit mbnp.board.board[0, :].tolist()

実行結果

1.47 μs ± 40 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
284 ns ± 5.28 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

`np.diag` と `np.flip` を利用した斜め方向の計算

残念ながら 斜め方向 の直線上に同じマークが並んでいるかどうかを スライス表記を利用して判定することはできません が、別の方法で効率よく判定 することができます。

numpy には 2 次元の ndarray の 対角線（diagonal line）上の要素 を表す 1 次元の ndarray を計算 する np.diag という関数があります。ここでいう対角線は x と y 座標が同一の、左上から右下方向の対角線 です。そのことは下記のプログラムの実行結果から確認できます。

mbnp = Marubatsu(boardclass=NpBoard)
mbnp.cmove(0, 0)
mbnp.cmove(1, 1)
mbnp.cmove(2, 2)
print(mbnp)
print(np.diag(mbnp.board.board))

実行結果

Turn x
o..
.x.
..O

['o' 'x' 'o']

従って、左上から右下 の直線上のマークは np.diag(mbnp.board.board) で計算できます。

numpy には 2 次元の ndarray の 左右（left と right）を反転 する np.fliplr という関数があります。下記の 2 行目は mbnp.board.board の左右を反転するプログラムです。

print(mbnp.board.board)
print(np.fliplr(mbnp.board.board))

実行結果

[['o' '.' '.']
 ['.' 'x' '.']
 ['.' '.' 'o']]
[['.' '.' 'o']
 ['.' 'x' '.']
 ['o' '.' '.']]

従って、左上から右下 の直線上のマークは、下記のプログラムのように np.fliplr で左右を反転したデータに対して np.diag を計算 することで求めることができます。

print(np.diag(np.fliplr(mbnp.board.board)))

実行結果

['.' 'x' '.']

他にも上下を反転する np.flipud、上下と左右の両方を反転する np.filp があります。詳細は下記のリンク先を参照して下さい。なお、左上から右下の直線状のマークは np.flipud を利用して計算することもできます。

`is_winner` メソッドの修正

上記から、is_winner メソッドを下記のプログラムのように is_same メソッドの代わりに スライス表記などを利用 するように修正することができます。

5 行目：player が勝利していることを表す文字列を計算する
6、7 行目：スライス表記と tolist を利用して x 列と y 行の直線上のマークを連結した文字列を計算し、winstr と等しいかどうかを判定する
10、14 行目：先程説明した方法で斜め方向の直線上の判定を行うように修正する

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

行番号のないプログラム

def is_winner(self, player, last_move):
    x, y = 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:
        winstr = player * self.BOARD_SIZE
        if "".join(self.board[x, :].tolist()) == winstr  or \
        "".join(self.board[:, y].tolist()) == winstr:
            return True
        # 左上から右下方向の判定
        if x == y and "".join(np.diag(self.board).tolist()) == winstr:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            "".join(np.diag(np.fliplr(self.board)).tolist()) == winstr:
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

NpBoard.is_winner = is_winner

修正箇所

def is_winner(self, player, last_move):
    x, y = last_move
    if self.count_linemark:
元と同じなので省略
    else:
+       winstr = player * self.BOARD_SIZE
-       if self.is_same(player, x=0, y=y, dx=1, dy=0) or \
-       self.is_same(player, x=x, y=0, dx=0, dy=1):
+       if "".join(self.board[x, :].tolist()) == winstr  or \
+       "".join(self.board[:, y].tolist()) == winstr:
            return True
        # 左上から右下方向の判定
-       if x == y and self.is_same(player, x=0, y=0, dx=1, dy=1):
+       if x == y and "".join(np.diag(self.board).tolist()) == winstr:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
-           self.is_same(player, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1):
+           "".join(np.diag(np.fliplr(self.board)).tolist()) == winstr:
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

NpBoard.is_winner = is_winner

上記の修正後に下記のプログラムでベンチマークのプログラムを実行します。

for count_linemark in [False, True]:
    print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
    benchmark(mbparams={"boardclass": boardclass, "count_linemark": count_linemark})
    print()

実行結果

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

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

ai14s VS ai2
100%|██████████| 50000/50000 [01:08<00:00, 732.36it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

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

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

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

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

ai14s VS ai2
100%|██████████| 50000/50000 [00:30<00:00, 1659.97it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

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

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

下記は先ほどの表に上記の実行結果を加えた表です。

`count_linemark`	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
`False`	5924.49 回/秒 6050.94 回/秒 7252.75 回/秒 7778.06 回/秒	633.71 回/秒 639.81 回/秒 726.09 回/秒 732.36 回/秒	42.9 ms 43.9 ms 39.5 ms 39.2 ms
`True`	6832.91 回/秒 7087.24 回/秒 8313.93 回/秒 8005.89 回/秒	1475.99 回/秒 1540.64 回/秒 1657.19 回/秒 1659.97 回/秒	43.2 ms 42.7 ms 38.8 ms 38.8 ms

実行結果から count_linemark が False の場合は 処理速度が若干向上 したことが確認できます。なお、count_linemark が True の場合に 行われる処理は変わっていない ので、そちらの場合の 処理速度はほとんど変化しません。

numpy が得意とする処理

今回の記事の修正によって NpBoard クラスの処理速度が若干改善しましたが、前回の記事で行った下記の表のベンチマークからわかるように、NpBoard クラスの処理速度 は List1dBoard クラスよりもかなり遅く になってしまいます。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
ListBoard	`False`	14916.51 回/秒	1116.53 回/秒	17.4 ms
ListBoard	`True`	15463.39 回/秒	2030.27 回/秒	17.4 ms
List1dBoard	`False`	17404.27 回/秒	1145.23 回/秒	16.7 ms
List1dBoard	`True`	17176.56 回/秒	2152.38 回/秒	17.3 ms

このことから numpy を利用すると処理速度が低下すると思った人がいるかもしれませんが、NpBoard の処理速度が遅い のは NpBoard クラスでは numpy が不得意 とする個々の 要素の参照と代入処理を多く行っている 点と、numpy が得意 とする 大量の要素に対する計算処理を行っていない ことが原因です。

numpy が大量の要素に対する計算処理が得意 であることを実際に示します。下記は 1 万個の要素 を持つ 1 次元の list と ndarray の要素の合計を計算 するプログラムです。numpy には ndarray の要素の合計を高速に計算 することができる np.sum という関数が定義されているので、それを利用して ndarray の合計を計算しています。実行結果からどちらも正しい計算が行われることが確認できます。

l = [i for i in range(10000)]
print(sum(l))
a = np.array(l)
print(np.sum(a))

実行結果

49995000
49995000

np.sum の詳細については下記のリンク先を参照して下さい。

下記は、それぞれの処理時間を計測 するプログラムです。

print("sum(l)")
%timeit sum(l)
print("np.sum(a)")
%timeit np.sum(a)

実行結果

sum(l)
51.2 μs ± 113 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
np.sum(a)
5.37 μs ± 170 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

実行結果から np.sum で ndarray を計算 する場合の 処理速度 が、sum で list を計算する処理速度の 約 10 倍 になることが確認できます。

このように、大量の要素をまとめて計算 するような処理を行う場合は、list よりも ndarray を利用したほうが高速に処理 を行うことができます。残念ながら NpBoard では 大量の要素をまとめて計算する処理を行っていない ので numpy の強みを活かすことができません。

深層学習（ディープラーニング）を行う場合は データを配列で記録する必要がある ので、そのような場合は numpy が良く利用されます。深層学習については、先になると思いますが今後の記事で扱う予定なので、その際は numpy を利用することになります。

なお、スライス表記や numpy の関数を利用することで、プログラムを簡潔にわかりやすく記述できる という利点は重要だと思いますので、そのことが理由で ndarray を利用する事も多いのではないかと思います。残念ながら ndarray を利用する NpBoard は、今後の改良を行っても List1dBoard よりも処理速度は速くなることはないと思いますが、numpy は非常に良く使われるモジュールなので、numpy を利用したプログラムの記述例を紹介 するという目的で引き続き NpBoard クラスの改良を行うことにします。

np.sum が ndarray の要素の合計を sum よりも高速に計測できる理由は、np.sum が ndarray 内に 連続したメモリに記録された配列 のデータを 効率よく計算する処理 を行うからです。そのため、下記のプログラムのように 連続したメモリに要素を記録しない list に対して np.sum で合計を計算すると実行結果のように sum(l) よりもかなり遅く なります。また、逆に下記のプログラムのように list の要素の合計 を np.sum で計算しても処理速度は sum(l) よりもかなり遅く なります。

print("np.sum(l)")
%timeit np.sum(l)
print("sum(a)")
%timeit sum(a)

実行結果

np.sum(l)
416 μs ± 10.8 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sum(a)
583 μs ± 15 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

従って list の要素の合計は sum、ndarray の要素の合計は np.sum を利用すべきです。これは、合計以外の他の ndarray の要素の計算を行う numpy の関数も同様で、numpy で定義された関数は ndarray に対して利用したほうが良いでしょう。

今回の記事のまとめ

今回の記事では ndarray に対するスライス表記 や numpy が提供する関数 などを利用することで ndarray を利用した NpBoard クラスの 処理速度の改善方法 と、プログラムを わかりやすく記述する方法 について紹介しました。他にも改善できる部分があるので、次回の記事でも引き続き NpBoard クラスの改善を行う予定です。

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

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

次回の記事