目次と前回の記事
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 |
次回の記事