目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| test.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義 |
| tree.py | ゲーム木に関する Node、Mbtree クラスなどの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
着手の取り消しによる処理の高速化の検証
前回の記事では、deepcopy で局面のデータをコピーする代わりに 着手の取り消し を行うという 高速化の手法 を紹介し、その手法で ai_abs_dls の高速化 を行いました。今回の記事では最初に どのように高速化が行われるかの検証 を行います。
局面のコピーと着手の取り消しの処理時間の検証
下記の表は、子ノードの評価値を計算 する際に、局面のデータをコピー する場合と、着手を取り消す 場合に行われる処理です。
| 局面のデータをコピーする場合 | 着手を取り消す場合 |
|---|---|
|
|
両者の違いは太字の部分 なので、両者の 処理速度の差 は「局面のデータをコピーする処理」と「着手の取り消しを行う処理」の差 によってもたらされるものです。そこで、それぞれの処理時間を計算 してその処理時間の差を 検証する ことにします。
局面のデータをコピーする処理時間の計測
下記は、局面のデータを表す Marubatsu クラスのインスタンスの属性を表す表です。
| 属性 | 意味 |
|---|---|
move_count |
ゲーム開始時の局面からの手数 |
turn |
現在の局面の手番 |
last_turn |
直前の局面の手番。ゲーム開始時の値は None
|
status |
現在の局面の状況 |
board |
ゲーム盤を表す 2 次元の list |
last_move |
直前に行われた着手の座標 ゲーム開始時の局面の場合は直前の着手はないので (-1, -1)とする |
records |
ゲーム開始時から行われた着手を表す list i 番の要素に i 手目の着手が記録される 0 手目の着手は存在しないので 0 番の要素はゲーム開始時の局面の last_move の値である (-1, -1) とする |
この中で records 以外 の属性の データの量は常に同じ ですが、records 属性には list が代入 され、その 要素の数 は 着手を行った回数によって増えます。データの コピーにかかる時間 はコピーする データの量によって増える ので、下記のプログラムで 着手を行った回数ごと に deepcopy でコピーする 処理時間を計測 することにします。
- 5 行目：9 手目までの着手を表す list を変数に代入する。途中でどちらかが勝利しないようなデータにする必要がある点に注意が必要である
-
7 ~ 9 行目：ゲーム開始時の局面に対する
deepcopyの処理時間を %timeit で計測する。9 行目のprint()は、次の結果の間に空行を表示して見やすくするためのものである -
10 ~ 14 行目：9 回の着手を行い、それぞれの場合の
deepcopyの処理時間を表示する
1 from marubatsu import Marubatsu
2 from copy import deepcopy
3
4 mb = Marubatsu()
5 movelist = [(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (1, 1), (1, 2), (2, 2), (0, 2)]
6
7 print(mb)
8 %timeit deepcopy(mb)
9 print()
10 for x, y in movelist:
11 mb.move(x, y)
12 print(mb)
13 %timeit deepcopy(mb)
14 print()
行番号のないプログラム
from marubatsu import Marubatsu
from copy import deepcopy
mb = Marubatsu()
movelist = [(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (1, 1), (1, 2), (2, 2), (0, 2)]
print(mb)
%timeit deepcopy(mb)
print()
for x, y in movelist:
mb.move(x, y)
print(mb)
%timeit deepcopy(mb)
print()
実行結果
Turn o
...
...
...
18.2 µs ± 255 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
Turn x
O..
...
...
20.5 µs ± 312 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
Turn o
oX.
...
...
22.7 µs ± 1.87 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn x
oxO
...
...
24.8 µs ± 1.96 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn o
oxo
X..
...
25.3 µs ± 193 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn x
oxo
x.O
...
27.1 µs ± 354 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn o
oxo
xXo
...
28.8 µs ± 260 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn x
oxo
xxo
.O.
30.6 µs ± 244 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn o
oxo
xxo
.oX
32.3 µs ± 239 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
winner draw
oxo
xxo
Oox
33.9 µs ± 84.1 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
下記は、上記の実行結果と 着手が 1 回増えた際 の 処理時間の増加量 をまとめた表で、表から以下の事がわかります。なお、μs（マイクロ秒）は 100 万分の 1 秒です。
- 着手の回数が多いほど処理時間が増える
- 処理時間の増加量の平均から、着手が 1 回増えると平均で約 1.74 μs 処理時間が増える
- 処理時間は平均が 26.4 μs で、18.2 ~ 33.9 μs の範囲の値になる
なお、計算された処理時間の平均には 誤差がある ので増加量には 多少のばらつき があります。そのため、上記の値は正確な値ではない 目安だと考えて下さい。
| 着手の回数 | 処理時間(μs) | 増加量(μs) |
|---|---|---|
| 0 | 18.2 | |
| 1 | 20.5 | 2.3 |
| 2 | 22.7 | 2.2 |
| 3 | 24.8 | 2.1 |
| 4 | 25.3 | 0.5 |
| 5 | 27.1 | 1.8 |
| 6 | 28.8 | 1.7 |
| 7 | 30.6 | 1.8 |
| 8 | 32.3 | 1.7 |
| 9 | 33.9 | 1.6 |
| 平均 | 26.4 | 1.74 |
着手の取り消し処理の処理時間の計測
着手の取り消し を行うと 局面の状況 が 1 手前の局面に 変化してしまう ので、下記のプログラム で 同じ局面に対する 着手の取り消しの 処理時間を計測 することは 残念ながらできません。着手の取り消し処理の処理時間の計測方法について少し考えてみて下さい。
%% timeit mb.unmove()
deepcopy を利用した計測
着手の取り消し処理 は、同じ局面に対して行う必要 があるので、下記のプログラムのように deepcopy でコピーした局面に対して 着手の取り消しを行うという方法が考えられます。
mbcopy = deepcopy(mb)
mbcopy.unmove()
deepcopy の処理時間は 先ほど計測した ので、上記の 2 つの処理の処理時間を計測 し、先程計測した deepcopy の処理時間を引く ことで 着手の取り消しの処理時間を計測 することができます。下記は、ゲーム開始時から 9 回の着手を行った それぞれの局面に対して上記の処理時間を計測 するプログラムです。なお、%timeit は下記のプログラムのように ; で区切る ことで 複数のプログラムの処理時間を計測 することができます。
- ゲーム開始時の局面に対して着手の取り消しを行うことはないので、1 行目の下にあったゲーム開始時の処理時間を計測する処理は削除した
-
5 行目：
mbをコピーし、コピーした局面に対する着手の取り消し処理の処理時間を計測するように修正した
1 mb = Marubatsu()
2 for x, y in movelist:
3 mb.move(x, y)
4 print(mb)
5 %timeit mbcopy = deepcopy(mb); mbcopy.unmove()
6 print()
行番号のないプログラム
mb = Marubatsu()
for x, y in movelist:
mb.move(x, y)
print(mb)
%timeit mbcopy = deepcopy(mb); mbcopy.unmove()
print()
修正箇所
mb = Marubatsu()
-print(mb)
-%timeit deepcopy(mb)
-print()
for x, y in movelist:
mb.move(x, y)
print(mb)
- %timeit deepcopy(mb)
+ %timeit mbcopy = deepcopy(mb); mbcopy.unmove()
print()
実行結果
Turn x
O..
...
...
21.1 µs ± 1.2 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn o
oX.
...
...
23.6 µs ± 1.31 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn x
oxO
...
...
24.4 µs ± 934 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn o
oxo
X..
...
25.7 µs ± 249 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn x
oxo
x.O
...
27.8 µs ± 1.22 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn o
oxo
xXo
...
29.3 µs ± 223 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn x
oxo
xxo
.O.
30.9 µs ± 266 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
Turn o
oxo
xxo
.oX
33.5 µs ± 1.25 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
winner draw
oxo
xxo
Oox
34.7 µs ± 234 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
下記は 上記の実行結果 と、上記の処理時間と先程の deepcopy の処理時間の差から計算された unmove の処理時間 をまとめた表です。なお、処理時間の単位は μs です。
| 着手の回数 | deepcopy |
deepcopy + unmove
|
unmove |
|---|---|---|---|
| 1 | 20.5 | 21.1 | 0.6 |
| 2 | 22.7 | 23.6 | 0.9 |
| 3 | 24.8 | 24.4 | -0.4 |
| 4 | 25.3 | 25.7 | 0.4 |
| 5 | 27.1 | 27.8 | 0.7 |
| 6 | 28.8 | 29.3 | 0.5 |
| 7 | 30.6 | 30.9 | 0.3 |
| 8 | 32.3 | 33.5 | 1.2 |
| 9 | 33.9 | 34.7 | 0.8 |
| 平均 | 27.3 | 27.9 | 0.56 |
表から、unmove の処理時間の 平均 が -0.4 ~ 1.2 μs の範囲 にあり、その平均が 約 0.56 μs であることがわかりますが、着手の回数ごとに計算された unmove の処理時間にばらつきがあります。また、着手の回数が 3 の場合の unmove の処理時間が 負の値 になっているという問題があります。このようなことが起きる理由について少し考えてみて下さい。
上記のようなことが起きる理由は、上記の表の deepcopy + unmove の平均の数値が 27.9 μs であるのに対し、unmove の平均の数値が 0.56 μs であり、桁が 2 つも異なる からです。
上記の deepcopy + unmove の %timeit の計算結果の中には、下記のように 標準偏差 として 1.87 μs が計算されているものがあります。以前の記事で説明したように、計測された処理時間の 分布が正規分布に従う場合 は、約 68 % のデータが 平均 ± 標準偏差 の範囲内に収まる ことを表します。
22.7 µs ± 1.87 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
deepcopy + unmove の 標準偏差 が unmove の処理時間の 平均の 0.56 μs よりも大きい ということは、計算された 平均時間の誤差 が unmove の処理時間よりも大きくなる可能性が高い ことを意味します。そのため、deepcopy + unmove の処理時間の 平均から、deepcopy の処理時間の 平均を引き算すると、その 誤差によって unmove の処理時間が 正しく計算できなくなります。これが上記の表から計算した unmove の処理時間に ばらつきがあり、負の時間が計算される 場合がある理由です。
このように、誤差のある 2 つの処理 の 処理時間が大きく異なる場合 に、両方の処理時間 から 長いほうの処理時間 を 引き算する ことで 短いほうの処理時間を計測 するという方法は、長いほうの処理時間の誤差 のため うまく計算できない という問題が発生します。
perf_counter を利用した計測方法
上記の問題は、2 つの処理の処理時間から 1 つの処理時間を引く ことで残りの処理時間を計測しようとしたため発生しました。また、そのような方法で処理時間を計測した理由は、処理時間を手軽に計測できる %timeit を利用しようとしたため です。
%timeit は確かに便利ですが、unmove の処理時間のように %timeit で直接処理時間を計測できない場合は別の方法でその 処理時間を直接計測したほうが良い でしょう。具体的には、以前の記事で説明した perf_counter を利用して unmove の処理時間を複数回計測 し、その 平均と標準偏差を自分で計測 するという方法があります。
先程は 同じ局面 に対して 着手の取り消し処理 を行う方法として deepcopy を利用しましたが、deepcopy は処理に時間がかかる という問題があります。別の方法として、着手の取り消しの後 でもう一度取り消した 着手を行う という方法が考えられます。着手を行う move メソッドの処理 は deepcopy よりも おそらく高速に処理を行うことができる ので、より短い時間で unmove の処理時間を計測することができるはずです。
下記は、先程と同様にゲーム開始時の局面から着手を 9 回行ったそれぞれの局面に対して unmove と move の処理を 10 万回 行い、unmove の処理時間を list に記録 してその 平均時間を表示 するプログラムです。また、move の処理時間が deepcopy よりも 短いかどうかを確認 するために move の処理時間も計算 することにします。なお、標準偏差の計算には手間がかかるので後で計算することにします。
-
7、8 行目：
moveとunmoveの処理時間を記録する変数を空の list で初期化する - 9 行目：10 万回の繰り返し処理を行う
-
10 ~ 14 行目：処理の開始時間、
unmoveの処理の終了時間、moveの処理の終了時間をperf_counterで計算する。13 行目では取り消した (x, y) の着手をもう一度行うことで元の局面に戻している -
15、16 行目：
unmoveとmoveの処理時間を計算して list の要素に追加する。追加の際にperf_counterの時間の単位は秒なので、単位を μs にするために 100 万を乗算した - 17 ~ 19 行目：10 万回の繰り返し処理の終了後に、処理時間の合計を 10 万で割ることで処理時間の平均を計算して表示する
1 from time import perf_counter
2
3 mb = Marubatsu()
4 for x, y in movelist:
5 mb.move(x, y)
6 print(mb)
7 movetimelist = []
8 unmovetimelist = []
9 for _ in range(100000):
10 starttime = perf_counter()
11 mb.unmove()
12 unmovetime = perf_counter()
13 mb.move(x, y)
14 movetime = perf_counter()
15 unmovetimelist.append((unmovetime - starttime) * 1000000)
16 movetimelist.append((movetime - unmovetime) * 1000000)
17 print(f"move : {sum(movetimelist)/100000:4.1f} μs")
18 print(f"unmove: {sum(unmovetimelist)/10000:4.1f} μs")
行番号のないプログラム
from time import perf_counter
mb = Marubatsu()
for x, y in movelist:
mb.move(x, y)
print(mb)
movetimelist = []
unmovetimelist = []
for _ in range(100000):
starttime = perf_counter()
mb.unmove()
unmovetime = perf_counter()
mb.move(x, y)
movetime = perf_counter()
unmovetimelist.append((unmovetime - starttime) * 1000000)
movetimelist.append((movetime - unmovetime) * 1000000)
print(f"move : {sum(movetimelist)/100000:4.1f} μs")
print(f"unmove: {sum(unmovetimelist)/10000:4.1f} μs")
print()
実行結果
Turn x
O..
...
...
move : 18.8 μs
unmove: 0.9 μs
Turn o
oX.
...
...
move : 19.2 μs
unmove: 0.8 μs
Turn x
oxO
...
...
move : 19.0 μs
unmove: 0.8 μs
Turn o
oxo
X..
...
move : 19.1 μs
unmove: 0.8 μs
Turn x
oxo
x.O
...
move : 18.8 μs
unmove: 0.8 μs
Turn o
oxo
xXo
...
move : 18.8 μs
unmove: 0.8 μs
Turn x
oxo
xxo
.O.
move : 18.9 μs
unmove: 0.8 μs
Turn o
oxo
xxo
.oX
move : 19.3 μs
unmove: 0.8 μs
winner draw
oxo
xxo
Oox
move : 19.5 μs
unmove: 0.8 μs
実行結果から、着手した回数に関わらず move と unmove の 処理時間の平均は 約 19 μs と 0.8 μs であることがわかりました。
このことから、move の処理時間は deepcopy よりも少し短い ことが確認できました。
unmove に関しては、先ほどの場合 は unmove の処理時間の平均に ばらつきがあった のに対し、上記の unmove の処理時間の平均はすべて 0.8 μs で ばらつきはありません。また、その数値は先ほどの 0.56 μs と異なっていることから、先程の方法で計算 した unmove の処理時間の平均の 0.56 μs には実際に 大きな誤差がある ことが確認できました。
なお、move のほうが unmove よりも 処理時間がかかる のは、unmove では局面の状況が必ずゲーム中を表す Maurbatsu.PLAYING になるのに対し、move では judge メソッドで勝敗判定を行うことで 局面の状況を計算 するなどの、unmove にはない処理 が行われるからです。
平均と標準偏差を計算する statistics モジュールの関数
以前の記事では、確率分布を表すデータから期待値と標準偏差を計算する calc_stval という関数を定義しましたが、この関数は 確率分布を dict で表現 しているので、上記のような list に記録されたデータの 標準偏差を計算することはできません。
list に記録された数値の 平均（mean） と 標準偏差（standard deviation） は、統計に関する関数を集めた statistics モジュールで定義された mean と std1 で計算することができます。下記はそれらを使って平均と標準偏差を計算するように修正したプログラムです。
実行結果から、標準偏差が表示されるようになったことが確認できます。
-
5、6 行目：
meanとstdevで平均と標準偏差を計算して表示するように修正した
1 from statistics import mean, stdev
2
3 mb = Marubatsu()
4 for x, y in movelist:
元と同じなので省略
5 print(f"move : {mean(movetimelist):4.1f} μs ± {stdev(movetimelist):4.1f} μs")
6 print(f"unmove: {mean(unmovetimelist):4.1f} μs ± {stdev(unmovetimelist):4.1f} μs")
7 print()
行番号のないプログラム
from statistics import mean, stdev
mb = Marubatsu()
for x, y in movelist:
mb.move(x, y)
print(mb)
movetimelist = []
unmovetimelist = []
for _ in range(100000):
starttime = perf_counter()
mb.unmove()
unmovetime = perf_counter()
mb.move(x, y)
movetime = perf_counter()
unmovetimelist.append((unmovetime - starttime) * 1000000)
movetimelist.append((movetime - unmovetime) * 1000000)
print(f"move : {mean(movetimelist):4.1f} μs ± {stdev(movetimelist):4.1f} μs")
print(f"unmove: {mean(unmovetimelist):4.1f} μs ± {stdev(unmovetimelist):4.1f} μs")
print()
修正箇所
from statistics import mean, stdev
mb = Marubatsu()
for x, y in movelist:
元と同じなので省略
- print(f"move : {sum(movetimelist)/100000:4.1f} μs")
+ print(f"move : {mean(movetimelist):4.1f} μs ± {stdev(movetimelist):4.1f} μs")
- print(f"unmove: {sum(unmovetimelist)/100000:4.1f} μs")
+ print(f"unmove: {mean(unmovetimelist):4.1f} μs ± {stdev(unmovetimelist):4.1f} μs")
print()
実行結果
Turn x
O..
...
...
move : 18.7 μs ± 7.2 μs
unmove: 0.8 μs ± 0.5 μs
Turn o
oX.
...
...
move : 18.4 μs ± 3.9 μs
unmove: 0.8 μs ± 0.4 μs
Turn x
oxO
...
...
move : 18.9 μs ± 6.2 μs
unmove: 0.8 μs ± 0.4 μs
Turn o
oxo
X..
...
move : 18.7 μs ± 5.9 μs
unmove: 0.8 μs ± 0.4 μs
Turn x
oxo
x.O
...
move : 18.7 μs ± 5.0 μs
unmove: 0.8 μs ± 0.4 μs
Turn o
oxo
xXo
...
move : 18.8 μs ± 5.4 μs
unmove: 0.8 μs ± 0.4 μs
Turn x
oxo
xxo
.O.
move : 18.4 μs ± 4.9 μs
unmove: 0.8 μs ± 0.4 μs
Turn o
oxo
xxo
.oX
move : 18.5 μs ± 4.2 μs
unmove: 0.8 μs ± 0.3 μs
winner draw
oxo
xxo
Oox
move : 18.2 μs ± 4.4 μs
unmove: 0.8 μs ± 0.4 μs
mean と std の詳細については下記のリンク先を参照して下さい。また、statistics には分散など、他にも様々な統計に関する関数が定義されています。
処理時間のまとめ
下記は、上記で検証した処理時間をまとめた表です。この表から、deepcopy と unmove の 処理時間の差 は 平均で比較すると約 25 μs であることがわかります。
| 処理 | 処理時間の平均 |
|---|---|
deepcopy |
18.2 ~ 33.9 μs 平均 26.4 μs |
move |
約 19 μs |
unmove |
0.8 μs |
処理時間の短縮の検証
前回の記事では下記のプログラムを 処理時間のベンチマーク とし、その下の表のような結果が得られました。
ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=9)
| 処理時間の平均 | |
|---|---|
| 修正前 | 68.1 ms |
| 着手の取り消しの適用 | 36.8 ms |
先程の検証から deepcopy よりも unmove のほうが処理時間が短い ことが確認できましたが、その差は約 25 μs（100 万分の 25 秒）という 非常に短い時間 です。それにも関わらず ai_abs_dls の処理時間は 68.1 ms から 36.8 ms に 25 μs の約 1000 倍も減っている点 に疑問を持った方がいるかもしれません。このように減った理由について少し考えてみて下さい。
deepcopy または 着手の取り消し の処理は、子ノードの評価値を計算するたびに行われる ので、着手の取り消しによって 短縮された時間 は、計算したノードの数 に ほぼ比例します。そのことを検証することにします。
この処理で 計算されるノードの数 を、実引数に analyze=True を記述することで下記のプログラムで表示すると、1175 であることがわかります。
from ai import ai_abs_dls, ai14s
mb = Marubatsu()
eval_params = {"minimax": True}
result = ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, analyze=True, maxdepth=9)
print(result["count"])
実行結果
1175
先程の表のベンチマークの結果から両者の 処理時間の差 は 68.1 - 36.8 = 31.3 ms であることがわかるので、それを 計算したノードの数 である 1175 で割る と、31.3 ÷ 1175 = 約 0.0266 ms = 約 26.6 μs となるので、1 回あたり の子ノードの評価値の計算処理で 約 26.6 μs の処理時間が短縮 されたことがわかります。この結果は、先ほどの表から確認した deepcopy と unmove の 処理時間の差がおよそ 25 μs である ことと 一致します。
特定の処理時間を短縮 すると、全体 では「短縮された時間 × その処理が行われた回数」だけ 処理時間が短縮 されます。そのため、短縮された時間が非常に短くても、その処理が 数多く行われる場合 は全体で大きな処理時間の短縮が得られます。
処理時間の短縮とボトルネック
ベンチマークの処理時間の差 である 31.3 ms は、「deepcopy の処理時間 ー unmove の処理時間」を表します。unmove の処理時間 は「0.8 μs × 1175 = 940 μs = 0.94 ms = 約 0.1 ms」なので、deepcopy の処理時間 は「31.3 - 0.1 = 31.2 ms」となります。
修正前の ai_abs_dls の処理時間は 68.1 ms なので、修正前の処理の中で deepcopy の処理が占める 割合 は 31.2 / 68.1 = 約 46 % のように、ほぼ半分である ことがわかります。
このような、プログラムの中で 処理の効率を悪化する原因となる部分 のことを ボトルネック と呼び、ボトルネックの処理の効率を改善 することで、全体の処理の効率を大幅に改善 することができます。逆に言えば、それ以外の部分を改善 しても 全体 の処理の効率は ほとんど改善しません。その具体例については今回の記事の後などで紹介します。
処理の高速化を行う際 には、プログラムの中で どこがボトルネックになっているかを分析 し、その部分に対して処理の効率化を行う ことが非常に重要です。
ボトルネック以外 の部分の処理を時間をかけて頑張って効率化しても、プログラムがわかりづらくバグの原因になる 割には全体の処理の 効率がほとんど変わらないことが多い ので、常に処理の高速化を行えば良いというわけではありません。
ボトルネックは、瓶（bottle）の細い首（neck）の部分のことで、瓶の中身の液体を出す際に、ボトルネックが狭いことが原因で流量が制限されることが由来です。
瓶の流量を増やしたい場合は、最も狭いボトルネックの部分を広くすることが一番重要で、ボトルネック以外の部分の形状を変更してもほとんど効果はありません。
参考までに Wikipedia のボトルネックのリンクを下記に示します。
他の関数に対する着手の取り消しによる処理の高速化
ai.py には 他にも多くの関数 で deepcopy で局面のデータを コピーする処理を行っています が、そのすべてに対して着手の取り消しによる高速化を行うのは大変なので、本記事では下記の関数に対する高速化 を行うことにし、それらの効率について検証 することにします。
-
最近の記事で実装を行った PVS で最善手を計算する
ai_pvs_dls -
多くの静的評価関数をデコレート する
ai_by_score。ai_by_scoreによってデコレートされるai1s~ai14sが高速化の対象 となる -
多くのミニマックス法をベースとした評価関数をデコレート する
ai_by_mmscore。ai_abs_dlsやai_pvs_dlsなどの多数の関数が高速化の対象となる
上記以外の deepcopy を利用する関数は、今後利用することはほとんどないのではないかと思いますので、修正は行わないことにします。余裕がある方は修正してみて下さい。
ai_pvs_dls の高速化
これから行う ai_pvs_dls の修正 による 処理速度を比較 するための ベンチマークを考える 必要があります。〇× ゲームのゲーム木の深さは 9 なので、深さの上限を 9 とした PVS の計算処理 をベンチマークとすることにします。
以前の記事で説明したように、PVS では一般的に 反復深化 によって得られた 直前の深さ上限探索での置換表 を元に move ordering を行う ので、深さの上限を 9 とした PVS の計算を行うため には、深さの上限を 8 とした PVS の計算で 得られた置換表のデータが必要 になります。そのため、そのデータ を下記のプログラムで 計算する必要 があります。
-
5 行目：
analyze=Trueをキーワード引数に記述して PVS の反復深化 を行うai_pvs_iddfsを呼び出し、返り値をresultに代入する -
6 行目：
analyze=Trueを記述した場合は、反復深化で計算した それぞれの深さの上限 でのai_pvs_dlsの 計算結果が記録された list が返り値として返されるので、その中から 深さの上限を 8 とした PVS の置換表 を取り出してttに代入 する。ただし、ai_pvs_dlsの深さの上限 は指定したノードの 子ノードを基準とした深さを表す ので、深さの上限を 8 とした PVS の計算結果は 7 番のインデックスの要素に代入 される点に注意が必要である
1 from ai import ai_pvs_iddfs, ai_pvs_dls, ai14s
2
3 mb = Marubatsu()
4 eval_params = { "minimax": True }
5 result = ai_pvs_iddfs(mb, eval_func=ai14s, eval_params=eval_params, analyze=True)
6 tt = result[7]["tt"]
行番号のないプログラム
from ai import ai_pvs_iddfs, ai_pvs_dls, ai14s
mb = Marubatsu()
eval_params = { "minimax": True }
result = ai_pvs_iddfs(mb, eval_func=ai14s, eval_params=eval_params, analyze=True)
tt = result[7]["tt"]
下記は 上記の tt の置換表 を利用した 深さの上限を 9 とした ai_pvs_dls の処理時間を計測するプログラム2で、これをベンチマークとします。実行結果から 処理時間の平均が 32.4 ms であることが確認できます。下記のプログラムを ai_pvs_dls の処理速度のベンチマーク とすることにします。
%%timeit
ai_pvs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=8, tt_for_mo=tt)
実行結果
32.4 ms ± 171 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
ai_pvs_dls の修正方法その 1
以前の記事 で説明したように、PVS（スカウト法） では 子ノードの評価値の計算結果によって、同じ子ノードに対して 異なるウィンドウ でもう一度 評価値の計算をやり直す場合 があります。そのため、ai_pvs_dls の修正 は、前回の記事で行った ai_abs_dls の修正よりは若干複雑 になります。どのように修正すればよいかについて少し考えてみて下さい。
ai_pvs_dls の 修正方法の一つ に、下記のプログラムのように子ノードの評価値を計算する処理を呼び出す 6 箇所の ab_search のそれぞれに対して、前後に着手と着手の取り消しを行う ように修正するという方法があります。
-
9 ~ 11、16 ~ 18 行目：
deepcopyによるコピーを削除し、子ノードの評価値の計算後に着手を取り消すように修正する - 25 ~ 27 行目：この部分の処理は、17 行目の子ノードに対する評価値の計算処理 を、17 行目とは異なるウィンドウで やり直す処理 という スカウト法 で行われる処理である。修正前のプログラムでは、17 行目の子ノードの評価値の計算処理の後で着手の取り消しを行っていなかったが、18 行目で着手の取り消しを行うように修正したことで、25 行目で もう一度着手を行って 子ノードの局面を計算し直し、子ノードの評価値を計算した後の 27 行目で着手を取り消す処理を行う必要がある 点に注意すること
- 34 行目の min ノードのブロックでも上記と同様の 3 箇所の修正を行う
1 from ai import ai_by_mmscore, dprint
2 from time import perf_counter
3
4 @ai_by_mmscore
5 def ai_pvs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None, eval_params={},
6 tt=None, tt_for_mo=None):
元と同じなので省略
7 if mborig.turn == Marubatsu.CIRCLE:
8 x, y = legal_moves[0]
9 mborig.move(x, y)
10 score = ab_search(mborig, depth + 1, tt, alpha, beta)
11 mborig.unmove()
12 alpha = max(alpha, score)
13 bestmove = (x, y)
14 if score < beta:
15 for x, y in legal_moves[1:]:
16 mborig.move(x, y)
17 abscore = ab_search(mborig, depth + 1, tt, alpha, alpha + 1)
18 mborig.unmove()
19 if abscore > score:
20 bestmove = (x, y)
21 score = max(score, abscore)
22 if score >= beta:
23 break
24 elif score > alpha:
25 mborig.move(x, y)
26 abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
27 mborig.unmove()
28 if abscore > score:
29 bestmove = (x, y)
30 score = max(score, abscore)
31 if score >= beta:
32 break
33 alpha = max(alpha, score)
34 else:
35 min ノードの修正は max ノードの修正と同様なので省略
元と同じなので省略
行番号のないプログラム
from ai import ai_by_mmscore, dprint
from time import perf_counter
@ai_by_mmscore
def ai_pvs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None, eval_params={},
tt=None, tt_for_mo=None):
count = 0
def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
nonlocal count
if timelimit_pc is not None and perf_counter() >= timelimit_pc:
raise RuntimeError("time out")
count += 1
if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
return eval_func(mborig, calc_score=True, **eval_params)
boardtxt = mborig.board_to_str()
if boardtxt in tt:
lower_bound, upper_bound, _ = tt[boardtxt]
if lower_bound == upper_bound:
return lower_bound
elif upper_bound <= alpha:
return upper_bound
elif beta <= lower_bound:
return lower_bound
else:
alpha = max(alpha, lower_bound)
beta = min(beta, upper_bound)
else:
lower_bound = min_score
upper_bound = max_score
alphaorig = alpha
betaorig = beta
legal_moves = mborig.calc_legal_moves()
if tt_for_mo is not None:
if boardtxt in tt_for_mo:
_, _, bestmove = tt_for_mo[boardtxt]
index = legal_moves.index(bestmove)
legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
if mborig.turn == Marubatsu.CIRCLE:
x, y = legal_moves[0]
mborig.move(x, y)
score = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
alpha = max(alpha, score)
bestmove = (x, y)
if score < beta:
for x, y in legal_moves[1:]:
mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, alpha, alpha + 1)
mborig.unmove()
if abscore > score:
bestmove = (x, y)
score = max(score, abscore)
if score >= beta:
break
elif score > alpha:
mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
if abscore > score:
bestmove = (x, y)
score = max(score, abscore)
if score >= beta:
break
alpha = max(alpha, score)
else:
x, y = legal_moves[0]
mborig.move(x, y)
score = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
beta = min(beta, score)
bestmove = (x, y)
if score > alpha:
for x, y in legal_moves[1:]:
mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, beta - 1, beta)
mborig.unmove()
if abscore < score:
bestmove = (x, y)
score = min(score, abscore)
if score <= alpha:
break
elif score < beta:
mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
if abscore < score:
bestmove = (x, y)
score = min(score, abscore)
if score <= alpha:
break
beta = min(beta, score)
from util import calc_same_boardtexts
boardtxtlist = calc_same_boardtexts(mborig, bestmove)
if score <= alphaorig:
upper_bound = score
elif score < betaorig:
lower_bound = score
upper_bound = score
else:
lower_bound = score
for boardtxt, move in boardtxtlist.items():
tt[boardtxt] = (lower_bound, upper_bound, move)
return score
min_score = float("-inf")
max_score = float("inf")
if tt is None:
tt = {}
score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
dprint(debug, "count =", count)
return score, count
修正箇所
from ai import ai_by_mmscore, dprint
from time import perf_counter
@ai_by_mmscore
def ai_pvs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None, eval_params={},
tt=None, tt_for_mo=None):
元と同じなので省略
if mborig.turn == Marubatsu.CIRCLE:
x, y = legal_moves[0]
- mb = deepcopy(mborig)
- mb.move(x, y)
+ mborig.move(x, y)
- score = ab_search(mb, depth + 1, tt, alpha, beta)
+ score = ab_search(mborig, depth + 1, tt, alpha, beta)
+ mborig.unmove()
alpha = max(alpha, score)
bestmove = (x, y)
if score < beta:
for x, y in legal_moves[1:]:
- mb = deepcopy(mborig)
- mb.move(x, y)
+ mborig.move(x, y)
- abscore = ab_search(mb, depth + 1, tt, alpha, alpha + 1)
+ abscore = ab_search(mborig, depth + 1, tt, alpha, alpha + 1)
+ mborig.unmove()
if abscore > score:
bestmove = (x, y)
score = max(score, abscore)
if score >= beta:
break
elif score > alpha:
+ mborig.move(x, y)
- abscore = ab_search(mb, depth + 1, tt, alpha, beta)
+ abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
+ mborig.unmove()
if abscore > score:
bestmove = (x, y)
score = max(score, abscore)
if score >= beta:
break
alpha = max(alpha, score)
else:
x, y = legal_moves[0]
- mb = deepcopy(mborig)
- mb.move(x, y)
+ mborig.move(x, y)
- score = ab_search(mb, depth + 1, tt, alpha, beta)
+ score = ab_search(mborig, depth + 1, tt, alpha, beta)
+ mborig.unmove()
beta = min(beta, score)
bestmove = (x, y)
if score > alpha:
for x, y in legal_moves[1:]:
- mb = deepcopy(mborig)
- mb.move(x, y)
+ mborig.move(x, y)
- abscore = ab_search(mb, depth + 1, tt, beta - 1, beta)
+ abscore = ab_search(mborig, depth + 1, tt, beta - 1, beta)
+ mborig.unmove()
if abscore < score:
bestmove = (x, y)
score = min(score, abscore)
if score <= alpha:
break
elif score < beta:
- mb = deepcopy(mborig)
- mb.move(x, y)
+ mborig.move(x, y)
- abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
+ abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
+ mborig.unmove()
if abscore < score:
bestmove = (x, y)
score = min(score, abscore)
if score <= alpha:
break
beta = min(beta, score)
元と同じなので省略
上記の修正後に下記のプログラムでベンチマークを実行すると、処理時間の平均が 17.0 ms であり、修正前の 32.4 ms から 大幅に処理時間が減った ことが確認できます。
%%timeit
ai_pvs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=8, tt_for_mo=tt)
実行結果
17 ms ± 171 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
下記のプログラムの実行結果から ai_pvs_dls が 強解決の AI である ことが確認できます。
from util import Check_solved
params = {
"eval_func": ai14s,
"eval_params": eval_params,
"maxdepth": 8,
"tt_for_mo": tt,
}
Check_solved.is_strongly_solved(ai_pvs_dls, params)
実行結果
100%|██████████| 431/431 [00:01<00:00, 344.81it/s]
431/431 100.00%
ai_pvs_dls の修正方法その 2
上記の修正方法は、子ノードの評価値を計算する前後 で 着手と着手の取り消しを記述 すれば良いという点が わかりやすく、着手の取り消しのし忘れ による バグが発生しにくい という利点があります。一方で、同じ子ノードに対する繰り返し処理 の中で 2 回評価値を計算 する必要が生じた際に、着手と着手の取り消しを 2 回行う という 無駄 があります。そこで、下記のプログラムのように、同じ子ノードに対する繰り返し処理 の中で 着手と着手の取り消し を 1 回だけ行う ように修正するという方法が考えられます。
- 8 行目の直後の 着手を取り消す処理を削除 し、15 行目の下にあった 2 回目の子ノードの評価値を計算する直前にあった 着手を行う処理を削除 する。また、この子ノードに対する繰り返し処理が終了するまでの間 で、必ず着手の取り消しを行う ように修正する。この後で行われる 12 行目の if 文 の処理では、break 文によって 繰り返しが終了する場合がある ので、if 文の処理の中 で 必ず着手の取り消しが行われる ようにする必要がある
- 13 行目：12 ~ 14 行目のブロックで着手の取り消しを行う
- 17 行目：15 ~ 23 行目のブロックの中で、子ノードの評価値を計算した後 で 着手の取り消しを行う。このブロックの中では 17 行目以降で子ノードの評価値を計算することはないので、着手の取り消しはここで行って良い
- 24、25 行目：このままでは 上記の 2 種類の if 文のブロック が 実行されなかった場合 は 着手の取り消しが行われない ので、else のブロックを追加 して着手の取り消しを行う
- 26 行目の min ノードのブロックでも上記と同様の 3 箇所の修正を行う
1 @ai_by_mmscore
2 def ai_pvs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None, eval_params={},
3 tt=None, tt_for_mo=None):
元と同じなので省略
4 if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
5 if score < beta:
6 for x, y in legal_moves[1:]:
7 mborig.move(x, y)
8 abscore = ab_search(mborig, depth + 1, tt, alpha, alpha + 1)
9 if abscore > score:
10 bestmove = (x, y)
11 score = max(score, abscore)
12 if score >= beta:
13 mborig.unmove()
14 break
15 elif score > alpha:
16 abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
17 mborig.unmove()
18 if abscore > score:
19 bestmove = (x, y)
20 score = max(score, abscore)
21 if score >= beta:
22 break
23 alpha = max(alpha, score)
24 else:
25 mborig.unmove()
26 else:
27 min ノードの修正は max ノードの修正と同様なので省略
元と同じなので省略
行番号のないプログラム
@ai_by_mmscore
def ai_pvs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None, eval_params={},
tt=None, tt_for_mo=None):
count = 0
def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
nonlocal count
if timelimit_pc is not None and perf_counter() >= timelimit_pc:
raise RuntimeError("time out")
count += 1
if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
return eval_func(mborig, calc_score=True, **eval_params)
boardtxt = mborig.board_to_str()
if boardtxt in tt:
lower_bound, upper_bound, _ = tt[boardtxt]
if lower_bound == upper_bound:
return lower_bound
elif upper_bound <= alpha:
return upper_bound
elif beta <= lower_bound:
return lower_bound
else:
alpha = max(alpha, lower_bound)
beta = min(beta, upper_bound)
else:
lower_bound = min_score
upper_bound = max_score
alphaorig = alpha
betaorig = beta
legal_moves = mborig.calc_legal_moves()
if tt_for_mo is not None:
if boardtxt in tt_for_mo:
_, _, bestmove = tt_for_mo[boardtxt]
index = legal_moves.index(bestmove)
legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
if mborig.turn == Marubatsu.CIRCLE:
x, y = legal_moves[0]
mborig.move(x, y)
score = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
alpha = max(alpha, score)
bestmove = (x, y)
if score < beta:
for x, y in legal_moves[1:]:
mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, alpha, alpha + 1)
if abscore > score:
bestmove = (x, y)
score = max(score, abscore)
if score >= beta:
mborig.unmove()
break
elif score > alpha:
abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
if abscore > score:
bestmove = (x, y)
score = max(score, abscore)
if score >= beta:
break
alpha = max(alpha, score)
else:
mborig.unmove()
else:
x, y = legal_moves[0]
mborig.move(x, y)
score = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
beta = min(beta, score)
bestmove = (x, y)
if score > alpha:
for x, y in legal_moves[1:]:
mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, beta - 1, beta)
if abscore < score:
bestmove = (x, y)
score = min(score, abscore)
if score <= alpha:
mborig.unmove()
break
elif score < beta:
abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
if abscore < score:
bestmove = (x, y)
score = min(score, abscore)
if score <= alpha:
break
beta = min(beta, score)
else:
mborig.unmove()
from util import calc_same_boardtexts
boardtxtlist = calc_same_boardtexts(mborig, bestmove)
if score <= alphaorig:
upper_bound = score
elif score < betaorig:
lower_bound = score
upper_bound = score
else:
lower_bound = score
for boardtxt, move in boardtxtlist.items():
tt[boardtxt] = (lower_bound, upper_bound, move)
return score
min_score = float("-inf")
max_score = float("inf")
if tt is None:
tt = {}
score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
dprint(debug, "count =", count)
return score, count
修正箇所
@ai_by_mmscore
def ai_pvs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None, eval_params={},
tt=None, tt_for_mo=None):
元と同じなので省略
if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
if score < beta:
for x, y in legal_moves[1:]:
mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, alpha, alpha + 1)
- mborig.unmove()
if abscore > score:
bestmove = (x, y)
score = max(score, abscore)
if score >= beta:
+ mborig.unmove()
break
elif score > alpha:
- mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
if abscore > score:
bestmove = (x, y)
score = max(score, abscore)
if score >= beta:
break
alpha = max(alpha, score)
+ else:
+ mborig.unmove()
else:
x, y = legal_moves[0]
mborig.move(x, y)
score = ab_search(mborig, depth + 1, tt, alpha, beta)
mborig.unmove()
beta = min(beta, score)
bestmove = (x, y)
if score > alpha:
for x, y in legal_moves[1:]:
mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, beta - 1, beta)
- mborig.unmove()
if abscore < score:
bestmove = (x, y)
score = min(score, abscore)
if score <= alpha:
+ mborig.unmove()
break
elif score < beta:
- mborig.move(x, y)
abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
+ mborig.unmove()
if abscore < score:
bestmove = (x, y)
score = min(score, abscore)
if score <= alpha:
break
beta = min(beta, score)
+ else:
+ mborig.unmove()
元と同じなので省略
上記の修正後に下記のプログラムでベンチマークを実行すると、処理時間の平均が 17.4 ms であり、処理時間が 先程の 17.0 ms より増えている ことが確認できます。ただし その差は 0.4 ms と小さい ので、この差は誤差の範囲 でしょう。何度か下記の処理を実行することで 17.0 ms よりも短い時間が表示される場合が生じるので興味がある方は試してみて下さい。
%%timeit
ai_pvs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=9, tt_for_mo=tt)
実行結果
17.4 ms ± 251 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
下記のプログラムの実行結果から ai_pvs_dls が 強解決の AI である ことが確認できます。
Check_solved.is_strongly_solved(ai_pvs_dls, params)
実行結果
100%|██████████| 431/431 [00:01<00:00, 336.31it/s]
431/431 100.00%
処理時間がほとんど変わらない理由
上記の 2 種類の実装の 処理時間がほとんど変わらない理由 は、PVS では move ordering の精度が高ければ 同じ子ノードに対して 2 回目の子ノードの評価値を計算することがほとんどない からです。その 1 と その 2 の 修正方法の違い は、その 1 の修正方法 のほうの方が同じ子ノードに対して 2 回評価値の計算を行った際 に、move と unmove を 1 回ずつ多く計算している という点です。先ほどの検証結果から move の処理時間は 約 19 μs、unmove の処理時間は 0.8 μs で処理が行われるので、その 合計は約 20 μs という 非常に短い時間 です。
従って、上記の修正によって 数回程度 move と unmove の処理が行われなくなっても、計算時間は 1 ms 以下 の 非常に短い時間しか短くなりません。2 つの処理時間の平均を比較 した際に、誤差によって 処理時間が短いはずの修正方法 2 のほうが 処理時間が長く なる 可能性は充分にあり、実際に先程の実行結果ではそのようになりました。つまり、move と unmove を 1 回ずつ多く計算する処理は、ai_pvs_dls の ボトルネックではない ということです。
どちらの修正方法を採用すべきか
下記は修正方法 1 と 修正方法 2 の利点と欠点を表す表です。
| 利点 | 欠点 | |
|---|---|---|
| 修正方法 1 | プログラムの記述が間違にくい | ほんの少しだけ処理が遅い |
| 修正方法 2 | ほんの少しだけ処理が速い | プログラムが複雑で間違えやすい |
ほとんど変わらないとはいえ、処理時間が短くなることは間違いないので本記事では修正方法 2 を採用することにしますが、処理時間がほとんど変わらない ことを考慮して、わかりやすく間違えにくい修正方法 1 を選んでもかまわない でしょう。
処理時間の短縮の検証
先程行った ai_abs_dls の処理時間の短縮の検証と同様の方法で、ai_pvs_dls の処理時間の短縮を検証 することにします。今回の記事では下記のプログラムを処理時間のベンチマークとし、その下の表のような結果が得られました。このことから、deepcopy の処理は ai_pvs_dls でも ボトルネックとなっていた ことがわかります。
ai_pvs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=8, tt_for_mo=tt)
| 処理時間の平均 | |
|---|---|
| 修正前 | 32.4 ms |
| 修正方法その 1 による修正 | 17.0 ms |
| 修正方法その 2 による修正 | 17.4 ms |
この処理で 計算されるノードの数 を、実引数に analyze=True を記述することで下記のプログラムで表示すると、545 であることがわかります。
result = ai_pvs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=8,
analyze=True, tt_for_mo=tt)
print(result["count"])
実行結果
545
先程の表のベンチマークの結果から修正方法その 2 との 処理時間の差 は 32.4 - 17.4 = 15.0 ms であることがわかるので、それを計算したノードの数である 545 で割る と、15.0 ÷ 545 = 約 0.0275 ms = 約 27.5 μs となるので、1 回あたり の子ノードの評価値の計算処理で 約 27.5 μs の処理時間が短縮 されたことがわかります。この結果は、先ほどの表から確認した deepcopy と unmove の 処理時間の差がおよそ 25 μs である ことと 一致します。
今回の記事のまとめ
今回の記事では 着手の取り消しによる処理の高速化 の検証として、1 回の子ノードの評価値の計算での処理時間の短縮時間 を計算しました。また、その短縮時間と計算したノードの数を掛け算することで 全体の処理時間の短縮時間が計算できる を確認し、deepcopy によるコピーの処理が ボトルネックになっている ことを確認しました。
また、PVS で計算を行う ai_pvs_dls の修正を行い、その検証を行いました。
次回の記事では ai_by_score と ai_by_mmscore の修正とその検証を行うことにします。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| ai.py | 本記事で更新した ai_new.py |
次回の記事