Pythonで〇×ゲームのAIを一から作成する　その187　ボトルネックと処理の高速化の関係

Last updated at 2025-08-24Posted at 2025-08-20

目次と前回の記事

これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
test.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

ボトルネックと処理の高速化の関係

前回の記事では着手の取り消し処理による高速化の検証を行い、処理の効率の悪化の原因となる ボトルネックを改善 することで、処理の効率を大幅に改善 できることを示しました。

今回の記事では、他の deepcopy によるコピーを行っている部分の処理の高速化とその効率について検証することで、ボトルネックと処理の高速化の関係 について説明します。

`ai_by_score` の高速化

下記のプログラムのように 静的評価関数 をデコレートする ai_by_score の中で deepcopy による局面のコピーが行われているので、この部分を 着手の取り消しに置き換える ことで 処理の高速化 を行うことにします。

    for move in legal_moves:
        dprint(debug, "=" * 20)
        dprint(debug, "move", move)
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        dprint(debug, mb)
        score = eval_func(mb, debug, *args, **kwargs)

ベンチマークの設定と修正前の処理時間の計測

ai_by_score によって デコレートされる AI の関数 には ai1s ~ ai14s があるので、その中で ランダムな着手を行う ai2s と 弱解決の AI である ai14s を ベンチマーク で利用することにします。具体的には ゲーム開始時の局面から 0 ~ 8 回¹の着手 を行ったそれぞれの局面に対する ai2s と ai14s の処理時間の平均 を %timeit で計測 します。

なお、前回の記事では ゲーム開始時の局面から 0 ~ 9 回の着手 を行ったそれぞれの局面に対する deepcopy の処理時間の計測 を 下記のアルゴリズム で行いました。

繰り返し処理の前 に ゲーム開始時の局面 に対する処理時間の計測処理を行う
繰り返し処理の中 で下記の手順で処理を行うことで、1 ~ 9 回 の着手を行った局面に対する計測処理を行う
- 着手を行う
- その局面に対する処理時間の計測処理を行う

今回の記事では下記のように 繰り返し処理の中 で 着手を行う前 に処理時間の計測を行うことで、繰り返し処理の前 にゲーム開始時の局面に対す 処理を行わなくても済むようにする という工夫を行ないました。

繰り返し処理の中 で下記の手順で処理を行うことで、0 ~ 8 回の着手 を行った局面に対する計測処理を行う
- その局面に対する処理時間の計測処理を行う
- 着手を行う

下記は上記のアルゴリズムで処理時間を計測するプログラムです。

4 行目：9 回分の着手を表す list を movelist に代入する。着手の一覧は前回の記事で局面のコピーの処理時間を計測したプログラムのものと同じ
6 行目：mb にゲーム開始時の局面のデータを代入する
7 行目：movelist に記録された着手に対する繰り返し処理を行う
8 ~ 13 行目：ai2s と ai14s の処理時間を計測して表示する
14 行目：着手を行う。なお、9 回目の着手を行った直後で繰り返し処理が終了するので、9 回目の着手が行われた局面に対する計測処理は行われない

 1  from ai import ai2s, ai14s
 2  from marubatsu import Marubatsu
 3  
 4  movelist = [(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (1, 1), (1, 2), (2, 2), (0, 2)]
 5  
 6  mb = Marubatsu()
 7  for x, y in movelist:
 8      print(mb)
 9      print("ai2s")
10      %timeit ai2s(mb)
11      print("ai14s")
12      %timeit ai14s(mb)
13      print()
14      mb.move(x, y)

行番号のないプログラム

from ai import ai2s, ai14s
from marubatsu import Marubatsu

movelist = [(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (1, 1), (1, 2), (2, 2), (0, 2)]

mb = Marubatsu()
for x, y in movelist:
    print(mb)
    print("ai2s")
    %timeit ai2s(mb)
    print("ai14s")
    %timeit ai14s(mb)
    print()
    mb.move(x, y)

実行結果

Turn o
...
...
...

ai2s
362 µs ± 15.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
ai14s
530 µs ± 8.74 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn x
O..
...
...

ai2s
328 µs ± 1.93 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
ai14s
488 µs ± 2.71 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn o
oX.
...
...

ai2s
306 µs ± 14.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
ai14s
454 µs ± 12.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn x
oxO
...
...

ai2s
277 µs ± 11.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
ai14s
401 µs ± 11.9 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn o
oxo
X..
...

ai2s
236 µs ± 1.93 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
ai14s
333 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn x
oxo
x.O
...

ai2s
213 µs ± 28.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
ai14s
288 µs ± 17 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn o
oxo
xXo
...

ai2s
143 µs ± 1.14 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
187 µs ± 2.54 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Turn x
oxo
xxo
.O.

ai2s
108 µs ± 1.32 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
152 µs ± 2.45 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Turn o
oxo
xxo
.oX

ai2s
57.9 µs ± 246 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
78.2 µs ± 666 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

下記は上記の 実行結果をまとめた表 です。数値の単位は μs で、小数点以下の数値が計測された場合は整数になるように四捨五入しました。表から 着手の回数が増える と ai2s と ai14s はどちらも 処理時間が減る ことが確認できました。着手の回数と処理時間の関係については後で検証します。

着手の回数	`ai2s` の処理時間	`ai14s` の処理時間
0	362	530
1	328	488
2	306	454
3	277	401
4	236	333
5	213	288
6	143	187
7	108	152
8	58	78

また、もう一つ ai_by_score でデコレートされた AI の関数を利用した 実際の対戦での処理時間 を 別のベンチマーク として計測することにします。具体的には、下記のプログラムで ai_match を利用して ai2s VS ai14s の対戦を 10000 回行う と、実行結果のように処理時間が 72 秒かかる ことが確認できました。ai_match は 先手と後手を入れ替えて 10000 回の対戦を行うので、実際には 合計 20000 回の対戦 が行われます。従って 72 ÷ 20000 = 3.6 ms なので、ai2s VS ai14s の対戦が 平均で 3.6 ms で行われることがわかります。

from ai import ai_match, ai2s

ai_match(ai=[ai2s, ai14s])

実行結果

ai2s VS ai14s
100%|██████████| 10000/10000 [01:12<00:00, 138.75it/s]
count     win    lose    draw
o           0    8818    1182
x           0    9914      86
total       0   18732    1268

ratio     win    lose    draw
o        0.0%   88.2%   11.8%
x        0.0%   99.1%    0.9%
total    0.0%   93.7%    6.3%

`ai_by_score` の修正

ai_by_score の修正 は、以前の記事で ai_abs_dls で行った修正と同様 に、deepcopy を削除 し、子ノードの着手を行った後で着手を取り消す 処理を行うというものです。下記はそのように ai_by_score を修正したプログラムです。

11 ~ 15 行目：deepcopy のコピーを削除し、子ノードの計算を行った後で unmove を呼び出すように修正した

 1  from functools import wraps
 2  from random import choice
 3  
 4  def ai_by_score(eval_func):
 5      @wraps(eval_func)
 6      def wrapper(mb_orig, debug=False, *args, rand=True, 
 7                  analyze=False, calc_score=False, minimax=False, **kwargs):
元と同じなので省略
 8          for move in legal_moves:
 9              dprint(debug, "=" * 20)
10              dprint(debug, "move", move)
11              x, y = move
12              mb_orig.move(x, y)
13              dprint(debug, mb_orig)
14              score = eval_func(mb_orig, debug, *args, **kwargs)
15              mb_orig.unmove()
元と同じなので省略

行番号のないプログラム

from functools import wraps
from random import choice

def ai_by_score(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, 
                analyze=False, calc_score=False, minimax=False, **kwargs):
        if calc_score:
            score = eval_func(mb_orig, debug, *args, **kwargs)
            if minimax and mb_orig.turn == Marubatsu.CIRCLE:
                score *= -1
            return score

        dprint(debug, "Start ai_by_score")
        dprint(debug, mb_orig)
        legal_moves = mb_orig.calc_legal_moves()
        dprint(debug, "legal_moves", legal_moves)
        best_score = float("-inf")
        best_moves = []
        if analyze:
            score_by_move = {}
        for move in legal_moves:
            dprint(debug, "=" * 20)
            dprint(debug, "move", move)
            x, y = move
            mb_orig.move(x, y)
            dprint(debug, mb_orig)
            score = eval_func(mb_orig, debug, *args, **kwargs)
            mb_orig.unmove()
            dprint(debug, "score", score, "best score", best_score)
            if analyze:
                score_by_move[move] = score
            
            if best_score < score:
                best_score = score
                best_moves = [move]
                dprint(debug, "UPDATE")
                dprint(debug, "  best score", best_score)
                dprint(debug, "  best moves", best_moves)
            elif best_score == score:
                best_moves.append(move)
                dprint(debug, "APPEND")
                dprint(debug, "  best moves", best_moves)

        dprint(debug, "=" * 20)
        dprint(debug, "Finished")
        dprint(debug, "best score", best_score)
        dprint(debug, "best moves", best_moves)
        if analyze:
            return {
                "candidate": best_moves,
                "score_by_move": score_by_move,
            }
        elif rand:   
            return choice(best_moves)
        else:
            return best_moves[0]
        
    return wrapper

修正箇所

from functools import wraps
from random import choice

def ai_by_score(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, 
                analyze=False, calc_score=False, minimax=False, **kwargs):
元と同じなので省略
        for move in legal_moves:
            dprint(debug, "=" * 20)
            dprint(debug, "move", move)
-           mb = deepcopy(mb_orig)
            x, y = move
-           mb.move(x, y)           
+           mb_orig.move(x, y)
-           dprint(debug, mb)
+           dprint(debug, mb_orig)
-           score = eval_func(mb, debug, *args, **kwargs)
+           score = eval_func(mb_orig, debug, *args, **kwargs)
+           mb_orig.unmove()
元と同じなので省略

`ai2s` と `ai14s` の再定義と処理時間の比較

次に、下記のプログラムで ai2s と ai14s を上記で 修正した ai_by_score を利用 するように 再定義 します。内容は同じなのでプログラムは折りたたみます。

再定義するプログラム

from marubatsu import Markpat

@ai_by_score
def ai2s(mb, debug=False):
    return 0

@ai_by_score
def ai14s(mb, debug=False, score_victory=300, score_sure_victory=200, \
          score_defeat=-100, score_special=100, score_201=2, \
          score_102=0.5, score_012=-1):
    # 評価値の合計を計算する変数を 0 で初期化する
    score = 0        

    # 自分が勝利している場合
    if mb.status == mb.last_turn:
        return score_victory

    markpats = mb.count_markpats()
    if debug:
        pprint(markpats)
    # 相手が勝利できる場合は評価値を加算する
    if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
        score = score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
    # 次の自分の手番で自分が必ず勝利できる場合
    elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
        return score_sure_victory
    
    # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
    if mb.board[1][1] == Marubatsu.CROSS and \
        (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
        mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
        (mb.board[1][0] == Marubatsu.CROSS or \
        mb.board[0][1] == Marubatsu.CROSS or \
        mb.board[2][1] == Marubatsu.CROSS or \
        mb.board[1][2] == Marubatsu.CROSS) and \
        mb.move_count == 4:
        return score_special    

    # 次の自分の手番で自分が勝利できる場合は評価値に score_201 を加算する
    if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
        score += score_201
    # 「自 1 敵 0 空 2」1 つあたり score_102 だけ、評価値を加算する
    score += markpats[Markpat(last_turn=1, turn=0, empty=2)] * score_102
    # 「自 0 敵 1 空 2」1 つあたり score_201 だけ、評価値を減算する
    score += markpats[Markpat(last_turn=0, turn=1, empty=2)] * score_012
    
    # 計算した評価値を返す
    return score

上記の修正後に先程の ベンチマークの処理時間を計測 することにします。

下記は 1 つ目のベンチマーク を実行するプログラムです。

mb = Marubatsu()
for x, y in movelist:
    print(mb)
    print("ai2s")
    %timeit ai2s(mb)
    print("ai14s")
    %timeit ai14s(mb)
    print()
    mb.move(x, y)

実行結果

Turn o
...
...
...

ai2s
179 µs ± 2.42 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
ai14s
335 µs ± 3.06 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn x
O..
...
...

ai2s
160 µs ± 2.55 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
304 µs ± 10.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn o
oX.
...
...

ai2s
139 µs ± 1.66 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
283 µs ± 25.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn x
oxO
...
...

ai2s
120 µs ± 1.58 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
245 µs ± 19.8 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn o
oxo
X..
...

ai2s
104 µs ± 1.99 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
189 µs ± 4.71 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Turn x
oxo
x.O
...

ai2s
81.4 µs ± 1.35 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
154 µs ± 2 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Turn o
oxo
xXo
...

ai2s
52.6 µs ± 1.89 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
88.8 µs ± 1.19 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Turn x
oxo
xxo
.O.

ai2s
42.5 µs ± 272 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
78.7 µs ± 479 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Turn o
oxo
xxo
.oX

ai2s
23.2 µs ± 1.15 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
ai14s
41.6 µs ± 966 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

下記は 修正前と修正後 の 1 つ目のベンチマークの 処理時間をまとめた表 です。数値の単位は μs で、/ の左が修正前、右が修正後の処理時間の平均を表します。また、「差」の列は修正前と修正後の 処理時間の平均の差 を、「割合」の列は 修正前を基準 とした修正後の 処理時間の平均の割合 表します。

着手の回数	`ai2s`	差	割合	修正前の `ai14s`	差	割合
0	362/179	183	49%	530/335	195	63%
1	328/160	168	49%	488/304	184	62%
2	306/139	167	45%	454/283	171	62%
3	277/120	157	43%	401/245	156	61%
4	236/104	132	44%	333/189	144	57%
5	213/81	132	38%	288/154	134	53%
6	143/53	90	37%	187/89	98	48%
7	108/43	65	40%	152/79	73	52%
8	58/23	35	40%	78/42	36	54%

下記の表から、ai_by_score の修正によって以下のようになることがわかりました。

いずれの場合も処理時間が減る
着手の回数が多くなると処理時間の差が小さくなる
処理時間の割合は ai2s が 40 ~ 49 %、ai14s が 48 ~ 63 % となっており、いずれも約半分に減る
着手の回数が多くなると処理時間の割合が少しずつ小さくなる傾向がある

どの条件でも 処理時間が約半分 になることから、修正によって 大幅な高速化が行われる ことが確認できました。従って、deepcopy の処理が ai_by_score によってデコレートされる AI の関数の処理の ボトルネックとなっている ことがわかります。

下記は 2 つ目のベンチマーク を実行するプログラムです。実行結果から処理時間が 72 秒から 36 秒 になり、処理速度が約 2 倍に高速化 したことが確認できます。

ai_match(ai=[ai2s, ai14s])

実行結果

ai2s VS ai14s
100%|██████████| 10000/10000 [00:36<00:00, 273.53it/s]
count     win    lose    draw
o           0    8800    1200
x           0    9897     103
total       0   18697    1303

ratio     win    lose    draw
o        0.0%   88.0%   12.0%
x        0.0%   99.0%    1.0%
total    0.0%   93.5%    6.5%

また、下記は修正前の実行結果と比較すると 対戦成績がほぼ同じ であることから、ai_by_score の修正による バグが発生していない可能性が高い ことも確認できます。

ai2s VS ai14s
100%|██████████| 10000/10000 [01:12<00:00, 138.75it/s]
count     win    lose    draw
o           0    8818    1182
x           0    9914      86
total       0   18732    1268

ratio     win    lose    draw
o        0.0%   88.2%   11.8%
x        0.0%   99.1%    0.9%
total    0.0%   93.7%    6.3%

処理時間の短縮の原因の検証

次に、ai_by_score の修正による 処理時間の短縮の原因を検証 することにします。

下記は修正前の ai_by_score の中で deepcopy による局面のコピーの処理が行われる部分のプログラムです。この中で deepcopy は AI が最善手を計算する 局面の合法手 を表す legal_moves に対する繰り返し処理の中で実行 されています。従って、下記の deepcopy の処理は、最善手を計算する局面の 合法手の数の回数だけ実行 されます。

    for move in legal_moves:
        dprint(debug, "=" * 20)
        dprint(debug, "move", move)
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        dprint(debug, mb)
        score = eval_func(mb, debug, *args, **kwargs)

〇× ゲームの局面の 合法手の数 は 開いているマスの数と等しい ので、$\boldsymbol{n}$ 回の着手 が行われた局面の 合法手の数 は $\boldsymbol{9 - n}$ 個となります。また、前回の記事で 着手が行われた回数ごとの deepcopy の処理時間 は下記の表のようになることを検証しました。

着手の回数	処理時間(μs)
0	18.2
1	20.5
2	22.7
3	24.8
4	25.3
5	27.1
6	28.8
7	30.6
8	32.3
9	33.9

従って、ai_by_score の修正によって 短縮される処理時間 は、着手の回数を $n$ とした場合に 下記の式で計算 することができます。

($n$ 回着手が行われた場合の deepcopy の処理時間 - unmove の処理時間) × (9 - $n$)

前回の記事で unmove の処理時間 は着手の回数に関わらず 0.8 μs であることを検証したので、それを元に 短縮される処理時間を計算 すると 下記の表 のようになります。

着手の回数	処理時間(μs)	1 回あたりの短縮時間(μs)	全体の短縮時間(μs)
0	18.2	17.4	156.6
1	20.5	19.7	157.6
2	22.7	21.9	153.3
3	24.8	24.0	144.0
4	25.3	24.5	122.5
5	27.1	26.3	105.2
6	28.8	28.0	84.0
7	30.6	29.8	59.6
8	32.3	31.5	31.5

下記は先ほどの ai2s と ai14s の処理時間をまとめた表に、上記の計算による 短縮時間を加えた表 です。今回の検証では 差を比較したい ので 割合の列は削除 しました。

着手の回数	`ai2s`	差	修正前の `ai14s`	差	計算による短縮時間
0	362/179	183	530/335	195	157
1	328/160	168	488/304	184	158
2	306/139	167	454/283	171	153
3	277/120	157	401/245	156	144
4	236/104	132	333/189	144	123
5	213/81	132	288/154	134	105
6	143/53	90	187/89	98	84
7	108/43	65	152/79	73	60
8	58/23	35	78/42	36	31

計測には誤差があるため 若干の違い はありますが、太字の ai2s と ai14s の「差」の列が、「計算による短縮時間」とおおむね 似たような値になっている ことが確認できます。

ボトルネックの分析

前回の記事では、処理の高速化を行う際 には どこがボトルネックになっているかを分析 することが重要だと説明しました。その 分析方法の一つ に、行われる処理の中で 工夫を行なうこと で 処理時間の短縮を行うことができそうな ひとまとまりの 処理の処理時間を取り出して計測 するという方法があります。計測の結果、その処理が 全体の処理時間の中で大きな割合を占めている場合 は ボトルネックである ことがわかります。

すべての処理の処理時間を計測するのは大変なので、処理の短縮を行うことができなさそうな、変数の初期化処理や、繰り返し処理の中の for 文が原因となる処理時間を計測する必要はないでしょう。

ai_by_score が行う主な処理²は以下の通りなので、下記の処理時間を計測します。

合法手の一覧を計算する
それぞれの合法手に対して下記の処理を行う
1. deepcopy で局面をコピーする
2. move で着手を行う
3. 静的評価関数で評価値を計算する
4. 計算した評価値から最善手の一覧を計算する
最善手の一覧中からランダムに一つ選んだ合法手を返り値として返す

上記の 手順 2-1 と 2-2 の deepcopy と move の 処理時間は計測済み で、move の処理時間 は前回の記事から着手した回数に関わらず 約 19 μs であることがわかっていますので、それ以外の処理時間を計測 することにします。

手順 1、2-3、3 の処理時間の計測

手順 1 の合法手の一覧は calc_legal_moves から、手順 2-3 の静的評価関数は 実引数に calc_score=True を記述 して ai2s と ai14s を呼び出すことで計算されるので、それらの 処理時間の平均 を先程と同様に ゲーム開始時の局面から 0 ~ 8 回の着手 を行ったそれぞれの局面で計測することにします。

手順 3 の最善手の一覧からランダムに選択する処理は random モジュールの choice を利用して計算されます。合法手の一覧 と 最善手の一覧 は、どちらも list で表現される ので、$n$ 個の 合法手の list から choice で一つを 選択する処理と、$n$ 個の 最善手の list から choice で 一つを選択する処理 では 同じ処理 が行われます。最善手の数 は局面によって 1 ~ 9 個 あり、ゲーム開始時の局面から 0 ~ 8 回の着手 を行った局面の合法手の数は 1 ~ 9 になるので、それぞれの場合の 合法手の一覧を最善手の一覧とみなして choice の処理時間 を計測することで、最善手の数が 1 ~ 9 個 の場合の処理時間を計測することができます。

下記は、ゲーム開始時の局面から 0 ~ 8 回の着手 を行ったそれぞれの局面に対する 合法手の一覧の計算 と、静的評価関数 ai2s と ai14s による評価値の計算と、合法手の一覧に対する choice の計算 の 処理時間を計測して表示 するプログラムです。

from random import choice

mb = Marubatsu()
for x, y in movelist:
    print(mb)
    print("合法手の計算処理")
    %timeit mb.calc_legal_moves()
    print("ai2s での評価値の計算処理")
    %timeit ai2s(mb, calc_score=True)
    print("ai14s での評価値の計算処理")
    %timeit ai14s(mb, calc_score=True)
    print("choice の計算処理")
    legal_moves = mb.calc_legal_moves()
    %timeit choice(legal_moves)
    print()

実行結果

Turn o
...
...
...

合法手の計算処理
1.67 µs ± 20.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
ai2s での評価値の計算処理
274 ns ± 11.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
17.2 µs ± 312 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
294 ns ± 13.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Turn x
O..
...
...

合法手の計算処理
1.66 µs ± 16.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai2s での評価値の計算処理
276 ns ± 11.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
16.9 µs ± 239 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
292 ns ± 1.17 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Turn o
oX.
...
...

合法手の計算処理
1.65 µs ± 24.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai2s での評価値の計算処理
269 ns ± 1.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
16.6 µs ± 145 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
260 ns ± 12.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Turn x
oxO
...
...

合法手の計算処理
1.62 µs ± 22.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai2s での評価値の計算処理
269 ns ± 0.935 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
16.7 µs ± 121 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
271 ns ± 14.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Turn o
oxo
X..
...

合法手の計算処理
1.63 µs ± 36.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai2s での評価値の計算処理
282 ns ± 16.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
17.5 µs ± 503 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
277 ns ± 2.13 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Turn x
oxo
x.O
...

合法手の計算処理
1.55 µs ± 19.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai2s での評価値の計算処理
273 ns ± 8.83 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
16.7 µs ± 141 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
291 ns ± 1.51 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Turn o
oxo
xXo
...

合法手の計算処理
1.51 µs ± 6.81 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai2s での評価値の計算処理
274 ns ± 10.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
17 µs ± 58.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
266 ns ± 12.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Turn x
oxo
xxo
.O.

合法手の計算処理
1.47 µs ± 10.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai2s での評価値の計算処理
281 ns ± 21 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
16.8 µs ± 130 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
293 ns ± 11.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Turn o
oxo
xxo
.oX

合法手の計算処理
1.48 µs ± 16.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai2s での評価値の計算処理
274 ns ± 19.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
ai14s での評価値の計算処理
16.8 µs ± 72.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
choice の計算処理
291 ns ± 1.97 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は上記の 実行結果をまとめた表 です。choice は最善手の数が「9 - 着手の回数」の場合の処理を表します。単位は μs で統一し、小数点以下第 3 位で四捨五入しました

着手の回数	合法手の計算処理	`ai2s`	`ai14s`	`choice`
0	1.67	0.27	17.2	0.29
1	1.66	0.28	16.9	0.29
2	1.65	0.27	16.6	0.26
3	1.62	0.27	16.7	0.27
4	1.63	0.28	17.5	0.28
5	1.55	0.27	16.7	0.29
6	1.51	0.27	17.0	0.27
7	1.47	0.28	16.8	0.29
8	1.48	0.27	16.8	0.29

表から 合法手の計算処理 は、着手の回数が多いほど短くなる ことがわかりました。これは、着手の回数が多いほど合法手の数が少なくなる からです。

一方、他の処理 は着手の回数と関係なく ほぼ同じ処理時間で計算 されることがわかりました。ai2s は常に 0 を返す のでこれは当然です。また、ai14s も ゲームの決着がついていない局面では同じ処理を行う ので処理時間は同じになります。choice が行う $n$ 個の中からランダムに 1 つを選択するという処理は、1 ~ n までサイコロを振って出た値に対応するものを選択する という処理なので、個数に関わらず処理時間は変わりません。

手順 2-4 の処理時間の計測

手順 2-4 の計算した評価値から 最善手の一覧を計算する処理 は以下のプログラムで行われます。なお、dprint による表示は debug が False の場合は行われないので省略しました。

    if (maxnode and best_score < score) or (not maxnode and best_score > score):
        best_score = score
        best_moves = [move]
    elif best_score == score:
        best_moves.append(move)

上記では maxnode、bestscore、score の値 によって 異なる処理 が行われるので、それぞれの場合 について下記のプログラムで 処理時間を計測 します。move の値は (1, 1)、best_moves の値は空の list としました。また、1 行目の条件式が True になる条件と すべての条件式が False になる条件は それぞれ 2 種類 なのでそれらの処理時間を計測しました。

maxnode == True and best_score < score の場合

%%timeit

best_score = 0
score = 1
move = (1, 1)
best_moves = []
maxnode = True
if (maxnode and best_score < score) or (not maxnode and best_score > score):
    best_score = score
    best_moves = [move]
elif best_score == score:
    best_moves.append(move)

実行結果

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

maxnode == False and best_score > score の場合

%%timeit

best_score = 2
score = 1
move = (1, 1)
best_moves = []
maxnode = False
if (maxnode and best_score < score) or (not maxnode and best_score > score):
    best_score = score
    best_moves = [move]
elif best_score == score:
    best_moves.append(move)

実行結果

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

best_score == score の場合

%%timeit

best_score = 1
score = 1
move = (1, 1)
best_moves = []
if best_score < score:
    best_score = score
    best_moves = [move]
elif best_score == score:
    best_moves.append(move)

実行結果

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

maxnode == True and best_score > score の場合

%%timeit

best_score = 2
score = 1
move = (1, 1)
best_moves = []
maxnode = True
if (maxnode and best_score < score) or (not maxnode and best_score > score):
    best_score = score
    best_moves = [move]
elif best_score == score:
    best_moves.append(move)

実行結果

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

maxnode == False and best_score < score の場合

%%timeit

best_score = 0
score = 1
move = (1, 1)
best_moves = []
maxnode = False
if (maxnode and best_score < score) or (not maxnode and best_score > score):
    best_score = score
    best_moves = [move]
elif best_score == score:
    best_moves.append(move)

実行結果

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

なお、上記では if 文の前で 変数の初期化の処理を含めた処理速度を計測 していますが、これらの部分を削除して %%timeit で計測を行うと エラーが発生してしまうから です³。そのため、変数の初期化処理の処理時間を上記の結果から除く 必要があります。そこで、変数の初期化処理の処理時間を下記のプログラムで計測すると、実行結果から 34.1 ns であることがわかりました。

%%timeit

best_score = 2
score = 1
move = (1, 1)
best_moves = []
maxnode = True

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

下記は上記の実行結果をまとめた表です。ns は 10 億分の 1 秒 で、1 μs = 1000 ns です。他の結果と比較できるように 単位を μs 統一して表記 しました。行う処理が異なるのでそれぞれの処理時間は異なりますが、いずれも約 0.05 μs という 非常に短い時間 で処理が行われることが確認できました。

	処理時間
`maxnode == True` and `best_score < score`	0.0767 - 0.0341 = 0.0426 μs
`maxnode == False` and `best_score > score`	0.0832 - 0.0341 = 0.0491 μs
`best_score == score`	0.1070 - 0.0341 = 0.0729 μs
`maxnode == True and best_score > score`	0.0664 - 0.0341 = 0.0323 μs
`maxnode == False and best_score < score`	0.0647 - 0.0341 = 0.0306 μs

`ai_by_score` の処理時間のまとめ

下記は ai_by_score が行う処理の再掲です。

合法手の一覧を計算する
それぞれの合法手に対して下記の処理を行う
1. deepcopy で局面をコピーする
2. move で着手を行う
3. 静的評価関数で評価値を計算する
4. 計算した評価値から最善手の一覧を計算する
最善手の一覧中からランダムに一つ選んだ合法手を返り値として返す

この中で 手順 1 と 3 の処理は 常に 1 回だけ 行われ、手順 2 の 4 つの処理は $n$ 回の着手が行われた局面では $\boldsymbol{9 - n}$ 回行われます。

下記は先ほどの結果から、それぞれの手順で行われる処理時間を計算 してまとめた表です。ただし、手順 2-3 は ai2s の処理時間を元に計算した値です。列の見出しの数値は手順の番号を表します。処理時間の数値の単位は μs で、小数点以下第 2 桁で四捨五入しました。

手順 2-1 ～ 2-3 の数値は deepcopy、move、ai2s に $9 - n$ を乗算したものです。手順 2-4 の 1 回の処理は 0.0306 ～ 0.0729 μs で行われますが、他の処理と比較すると短い ので 0.05 μs として $9 - n$ を乗算して計算したものです。「合計」の列は 手順 1 ~ 3 の処理時間の合計 で、「計測値」は 先ほど計測した ai2s の処理時間 です。なお、合計よりも計測値のほうが大きな値 になる理由は、ai2s は上記の 手順 1 ~ 3 以外の処理も行っている からです。

着手の回数	1	2-1	2-2	2-3	2-4	3	合計	計測値
0	1.7	163.8	1.7	2.4	0.5	0.3	170.4	362
1	1.7	164.0	1.5	2.2	0.4	0.3	170.0	328
2	1.7	158.9	1.3	1.9	0.4	0.3	164.4	306
3	1.6	148.8	1.1	1.6	0.3	0.3	153.8	277
4	1.6	126.5	1.0	1.4	0.3	0.3	131.0	236
5	1.6	108.4	0.8	1.1	0.2	0.3	112.3	213
6	1.5	86.4	0.6	0.8	0.2	0.3	89.7	143
7	1.5	61.2	0.4	0.5	0.1	0.3	64.0	108
8	1.5	32.3	0.2	0.3	0.1	0.3	34.6	58

上記の表からわかるように 手順 2 の処理時間が約 30 ~ 160 μs であり、いずれも 全体の処理の約半分 であることから明らかに deepcopy が大きなボトルネックとなっている ことがわかります。一方、それ以外 の手順の処理時間はいずれも 数 μs 以下 であり、それらを 合計しても 全体からみると ほんの数 % にしかならない ことから、他の手順の処理 はいずれも ほとんどボトルネックにはなっていない ことがわかります。

また、手順 1 ~ 3 の合計 が 計測値の約半分 であることから、計測していない処理 が全体の処理時間の 半分を占めている ことがわかります。筆者がプログラムを今一度眺めたところ、計測していない処理の中で改善の余地がありそうなボトルネックとなる処理は見当たらなかったのですが、もしかすると 計測していない処理の中 に 改善の余地がある別のボトルネックとなる処理があるかもしれません ので、興味がある方は調べてみると良いでしょう。

`ai_by_mmscore` の高速化

次に、ミニマックス法をベースとした ゲーム木の探索によって評価値を計算する評価関数 をデコレートする ai_by_mmscore を同様の方法で高速化することにします。

ベンチマークの設定と修正前の処理時間の計測

ai_by_mmscore によってデコレートされる AI の関数は多数ありますが、その中で 深さ制限探索での αβ 法 で計算を行う ai_by_dls をベンチマークとして利用することにします。具体的には以前の記事でベンチマークとした下記のプログラムをそのまま利用することにします。ただし、以前の記事と異なり、今回の記事では先ほどと同様に ゲーム開始時の局面から 0 ~ 8 回の着手を行ったそれぞれの局面 に対する処理時間を計測することにします。

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=9)

まず、最初に ai_abs_dls で必要となる変数を下記のプログラムで初期化します。

from ai import ai_abs_dls

eval_params = {"minimax": True}

次に下記のプログラムで処理時間を計測します。行う処理は ai_by_score の場合とほぼ同じなので説明は省略します。

mb = Marubatsu()
for x, y in movelist:
    print(mb)
    %timeit ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=9)
    print()
    mb.move(x, y)

実行結果

Turn o
...
...
...

33.7 ms ± 187 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Turn x
O..
...
...

25.7 ms ± 1.37 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Turn o
oX.
...
...

22.7 ms ± 2.37 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Turn x
oxO
...
...

6.67 ms ± 133 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Turn o
oxo
X..
...

3.25 ms ± 117 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Turn x
oxo
x.O
...

1.44 ms ± 17 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn o
oxo
xXo
...

436 µs ± 1.76 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn x
oxo
xxo
.O.

223 µs ± 19.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn o
oxo
xxo
.oX

82.5 µs ± 2.31 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

下記は上記の 実行結果をまとめた表 です。単位は μs で統一 し、小数点以下第 1 桁で四捨五入しました。着手を行った回数が多いほど、その局面をルートノードとする ゲーム木のノードの数が大幅に減る ため、処理時間も大幅に減ります。

着手の回数	処理時間(μs)
0	33700
1	25700
2	22700
3	6670
4	3250
5	1440
6	436
7	223
8	83

`ai_by_mmscore` の修正

ai_by_mmscore では 2 箇所で deepcopy を利用 していますが、そのうちの 最初の deepcopy の修正 は ai_by_score の修正と全く同じ で、下記のプログラムのように修正します。もう一か所の deepcopy についてはこの後で説明します。

10 ~ 14 行目：先程の ai_abs_dls で行った修正と同様に、deepcopy のコピーを削除し、子ノードの計算を行った後で unmove を呼び出すように修正した

 1  from copy import deepcopy
 2
 3  def ai_by_mmscore(eval_func):
 4      @wraps(eval_func)
 5      def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
 6                  analyze=False, calc_score=False, **kwargs):       
元と同じなので省略
 7          for move in legal_moves:
 8              dprint(debug, "=" * 20)
 9              dprint(debug, "move", move)
10              x, y = move
11              mb_orig.move(x, y)
12              dprint(debug, mb_orig)
13              score, count = eval_func(mb_orig, debug, tt=tt, *args, **kwargs)
14              mb_orig.unmove()
元と同じなので省略

行番号のないプログラム

from copy import deepcopy

def ai_by_mmscore(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
                analyze=False, calc_score=False, **kwargs):       
        if calc_score:
            score, count = eval_func(mb_orig, debug, *args, **kwargs)
            return score
        
        starttime = perf_counter()
        dprint(debug, "Start ai_by_mmscore")
        dprint(debug, mb_orig)
        legal_moves = mb_orig.calc_legal_moves()
        dprint(debug, "legal_moves", legal_moves)
        maxnode = mb_orig.turn == Marubatsu.CIRCLE
        best_score = float("-inf") if maxnode else float("inf")
        best_moves = []
        tt = {} if share_tt else None
        totalcount = 0
        if analyze:
            score_by_move = {}
        for move in legal_moves:
            dprint(debug, "=" * 20)
            dprint(debug, "move", move)
            x, y = move
            mb_orig.move(x, y)
            dprint(debug, mb_orig)
            score, count = eval_func(mb_orig, debug, tt=tt, *args, **kwargs)
            mb_orig.unmove()
            totalcount += count
            dprint(debug, "score", score, "best score", best_score)
            if analyze:
                score_by_move[move] = score
            
            if (maxnode and best_score < score) or (not maxnode and best_score > score):
                best_score = score
                best_moves = [move]
                dprint(debug, "UPDATE")
                dprint(debug, "  best score", best_score)
                dprint(debug, "  best moves", best_moves)
            elif best_score == score:
                best_moves.append(move)
                dprint(debug, "APPEND")
                dprint(debug, "  best moves", best_moves)

        dprint(debug, "=" * 20)
        dprint(debug, "Finished")
        dprint(debug, "best score", best_score)
        dprint(debug, "best moves", best_moves)
        bestmove = choice(best_moves) if rand else best_moves[0]
        if analyze:
            if share_tt:
                PV = []
                mb = deepcopy(mb_orig)
                while mb.status == Marubatsu.PLAYING:
                    PV.append(bestmove)
                    x, y = bestmove
                    if mb.board[x][y] != Marubatsu.EMPTY:
                        print("そのマスには着手済みです")
                        break
                    mb.move(x, y)
                    boardtxt = mb.board_to_str()
                    if boardtxt in tt:
                        _, _, bestmove = tt[boardtxt]
                    else:
                        break                
            else:
                PV = bestmove
            return {
                "candidate": best_moves,
                "score_by_move": score_by_move,
                "tt": tt,
                "time": perf_counter() - starttime,
                "bestmove": PV[0],
                "score": best_score,
                "count": totalcount,
                "PV": PV,
            }
        else:
            return bestmove
        
    return wrapper

修正箇所

from copy import deepcopy

def ai_by_mmscore(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
                analyze=False, calc_score=False, **kwargs):       
元と同じなので省略
        for move in legal_moves:
            dprint(debug, "=" * 20)
            dprint(debug, "move", move)
-           mb = deepcopy(mb_orig)
            x, y = move
-           mb.move(x, y)           
+           mb_orig.move(x, y)
-           dprint(debug, mb)
+           dprint(debug, mb_orig)
-           score = eval_func(mb, debug, *args, **kwargs)
+           score = eval_func(mb_orig, debug, *args, **kwargs)
+           mb_orig.unmove()
元と同じなので省略

`ai_abs_dls` の再定義と処理時間の比較

次に、下記のプログラムで ai_abs_dls を上記で 修正した ai_by_score を利用 するように 再定義 します。内容は同じなのでプログラムは折りたたみます。

再定義するプログラム

from time import perf_counter

@ai_by_mmscore
def ai_abs_dls(mb:Marubatsu, debug:bool=False, timelimit_pc:float|None=None, maxdepth:int=1,
               eval_func=None, eval_params:dict={}, use_tt:bool=False,
               tt:dict|None=None, tt_for_mo:dict|None=None) -> tuple[float, int]:
   
    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)
        
        if use_tt:
            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 not use_tt:            
                boardtxt = mborig.board_to_str()
            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:
            score = float("-inf")
            for x, y in legal_moves:
                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:
            score = float("inf")
            for x, y in legal_moves:
                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

        if use_tt:
            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_abs_dls が 強解決の AI である ことが確認できます。

from util import Check_solved

Check_solved.is_strongly_solved(ai_abs_dls, params={"eval_func": ai14s, "eval_params": eval_params, "use_tt": True, "maxdepth": 8})

実行結果

100%|██████████| 431/431 [00:01<00:00, 304.20it/s]
431/431 100.00%

次に、先程の ベンチマークの処理時間を計測 することにします。

mb = Marubatsu()
for x, y in movelist:
    print(mb)
    %timeit ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=9)
    print()
    mb.move(x, y)

実行結果

Turn o
...
...
...

32.7 ms ± 561 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Turn x
O..
...
...

25.5 ms ± 2.51 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Turn o
oX.
...
...

22.7 ms ± 3.34 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Turn x
oxO
...
...

6.21 ms ± 103 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Turn o
oxo
X..
...

2.95 ms ± 17.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Turn x
oxo
x.O
...

1.28 ms ± 25.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn o
oxo
xXo
...

338 µs ± 14 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Turn x
oxo
xxo
.O.

145 µs ± 2.44 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Turn o
oxo
xxo
.oX

44.2 µs ± 936 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

下記は修正前と修正後の 結果をまとめた表 です。表には下記の値を計算して載せました。

修正前と修正後の 処理時間の差
修正前を基準 とする修正後の 処理時間の比率
ai_by_score の検証で計算した、計算による短縮時間。この列については次で説明する

着手の回数	修正前(μs)	修正後(μs)	差	比率	計算による短縮時間
0	33700	32700	1000	97%	157
1	25700	25500	200	99%	158
2	22700	22700	0	100%	153
3	6670	6210	460	93%	144
4	3250	2950	300	91%	123
5	1440	1280	160	89%	105
6	436	338	98	78%	84
7	223	145	78	65%	60
8	83	44	39	53%	31

先程の ai_by_score の修正の場合と同様 に、修正によって 処理時間が短縮される ことが確認できます。参考までに下記に先程の結果を再掲するので比較してみて下さい。なお、着手の回数が 2 の場合は処理時間が短縮されていません が、これは 誤差による ものです。

一方、短縮される割合のほうは、ai_by_score の場合と異なり 着手の回数が小さいとほぼ 100 % に近い値 になることから、ほとんど短縮されない ことがわかります。

下記は先程の ai_by_score の修正 の結果をまとめた表の再掲です。

着手の回数	`ai2s`	差	割合	修正前の `ai14s`	差	割合
0	362/179	183	49%	530/335	195	63%
1	328/160	168	49%	488/304	184	62%
2	306/139	167	45%	454/283	171	62%
3	277/120	157	43%	401/245	156	61%
4	236/104	132	44%	333/189	144	57%
5	213/81	132	38%	288/154	134	53%
6	143/53	90	37%	187/89	98	48%
7	108/43	65	40%	152/79	73	52%
8	58/23	35	40%	78/42	36	54%

処理時間の短縮の原因検証

処理時間の短縮が、先程の表のような結果になる 原因について検証 します。下記は先ほどの表の再掲です。

着手の回数	修正前(μs)	修正後(μs)	差	比率	計算による短縮時間
0	33700	32700	1000	97%	157
1	25700	25500	200	99%	158
2	22700	22700	0	100%	153
3	6670	6210	460	93%	144
4	3250	2950	300	91%	123
5	1440	1280	160	89%	105
6	436	338	98	78%	84
7	223	145	78	65%	60
8	83	44	39	53%	31

ai_by_score と ai_by_mmscore は、合法手に対する繰り返しの処理はほぼ同じ なので、修正による短縮時間 は ai_by_score とほぼ同じになるはず です。処理時間が多いと誤差が大きくなる ため、上記の表の太字の「差」と「計算による短縮時間」は あまり一致しません が、処理時間が短くなる 着手の回数が 5 を超えたあたりから 誤差が小さくなるのでほぼ一致する ようになることが確認できます。このことから、実際に ai_by_mmscore でも ai_by_score と同じだけ処理時間が短縮 されることが確認できます。

一方、ai_by_score の場合は着手の回数に関わらず比率でみると 処理時間は約半分 になっていましたが、ai_by_mmscore の場合は 着手の回数が少ない場合の比率 は ほとんど減らない という結果になります。このようなことが起きる原因は、着手の回数が少ないほど 全体の処理時間の中で αβ 法によって評価値を計算する処理の割合が大きく増える ため、deepcopy の処理時間 の全体の処理時間に対する 割合が小さくなる からです。

処理時間の高速化 を行う際は、一般的に 短縮された時間の 量よりも 短縮された 比率のほうが重要 となります。つまり、全体の処理の中で 処理時間が多くの割合を占めるほど、大きなボトルネックになる ということです。

量ではなく 割合が重要となる具体例 として、スポーツでの時間の計測 があります。

完走に 約 10 秒 かかる 100 m 走では、全体の約 0.1 % を表す 0.01 秒単位で時間が記録 され、0.01 秒の時間の短縮が重要視 されます。

一方、完走に 2 時間以上（7000 秒以上）かかるようなマラソンの競技では、全体の約 0.01 % を表す 秒単位で時間が記録 され、1 秒の時間の短縮が重要視 されますが、その 100 分の 1 の 0.01 秒 は全く 考慮にいれられず、計測すらされません。

このように、時間を計測するスポーツの競技では、全体の時間に対する 特定の割合を重視して時間が計測 されます。

ai_by_mmscore の修正 は 着手の回数が多ければ 時間の 短縮の割合が大きくなる 点と、修正しても プログラムがわかりづらくなることはない ため 行う価値は充分にある と思いますが、まだ修正していないもう一つの deepcopy は、この後で説明するようにほとんと効果が得られないので修正する必要はほとんどないでしょう。

もう一つの `ai_by_mmscore` の `deepcopy`

ai_by_mmscore には、もう一か所下記の 置換表から PV を計算 する処理を行うプログラムで deepcopy を利用 しています。

 1      if analyze:
 2          if share_tt:
 3              PV = []
 4              mb = deepcopy(mb_orig)
 5              while mb.status == Marubatsu.PLAYING:
 6                  PV.append(bestmove)
 7                  x, y = bestmove
 8                  if mb.board[x][y] != Marubatsu.EMPTY:
 9                      print("そのマスには着手済みです")
10                      break
11                  mb.move(x, y)
12                  boardtxt = mb.board_to_str()
13                  if boardtxt in tt:
14                      _, _, bestmove = tt[boardtxt]
15                  else:
16                      break

この処理は、analyze が True の場合 に最善手の計算後に 1 回だけ行われる 処理なので、analyze が False の場合は実行されません。また、analyze が True の場合でも、2 行目の deepcopy を行わないようにしても 1 回分の deepcopy の処理しか短縮できません。全体の処理時間に対して この deepcopy の 処理時間は明らかに短い ので、この deepcopy はボトルネックにはなっていません。

また、この処理の中では PV の一覧を計算するために 何度も move で着手を行う処理を行っている ので、mg_orig をコピーせずに PV の計算後に unmove を利用 して mb_orig の局面に戻す場合 は、PV に記録した 最善手の数だけ unmove を実行する必要 があり、その分だけ unmove の処理時間が必要 になる点と、その処理を記述すると プログラムが複雑になってわかりづらくなる という欠点が生じます。

このように、処理時間の短縮がほとんど得られない割 には、プログラムが複雑になる という欠点があるので、わざわざこの deepcopy を unmove に置き換える修正を行う必要はほとんどない と思います。本記事でもこのプログラムは修正しないことにします。興味がある方は実際に修正してみて、処理時間を計測して比較してみて下さい。

この例のように、deepcopy で局面のデータをコピーする処理が 常にボトルネックになるわけではなく、常に unmove に置き換えたほうが良いとは限らない 点に注意が必要です。

その他の `deepcopy` に対する修正の必要性

これまでに記述したプログラムを一通り調べたところ、marubatsu.py と tree.py で局面のデータをコピーするために deepcopy が使われている ことがわかりましたので、それらの deepcopy の 修正の必要性 について説明します。

marubatsu.py の `deepcopy`

marubatsu.py の Marubatsu_GUI クラスの update_gui メソッドの中に、下記のプログラムのように deepcopy を利用する部分がありました。Marubatsu_GUI クラスは、GUI で〇×ゲームを遊ぶための gui_play で利用されるクラスです。

    mb = deepcopy(self.mb)
    mb.move(x, y)
    score = self.score_table[mb.board_to_str()]["score"]

この部分を下記のプログラムのように修正しても構わないのですが、そのような修正を行っても 人間が知覚できない数十 μs ほどの処理時間 しか短縮できません。GUI で〇×ゲームを遊ぶ際にそのような時間の短縮に 人間が気づくことはできない と思いますので、本記事では下記の修正は行わないことにします。修正を行いたい人は行ってみて下さい。

    self.mb.move(x, y)
    score = self.score_table[self.mb.board_to_str()]["score"]
    self.mb.unmove()

tree.py の `deepcopy`

tree.py を調べたところ、下記のプログラムのようにいくつかの場所で deepcopy が使われている ことが確認できました。

1  def calc_children(self, bestmoves_and_score_by_board=None):
2      self.children = []
3      for x, y in self.mb.calc_legal_moves():
4          childmb = deepcopy(self.mb)
5          childmb.move(x, y)
6          self.insert(Node(childmb, parent=self, depth=self.depth + 1,
7                           bestmoves_and_score_by_board=bestmoves_and_score_by_board))

上記の calc_children は、ゲーム木の ノードを表す Node クラス の メソッド で、ノードの 子ノードのデータを作成して登録 するという処理を行います。子ノードの作成は 6 行目で Node の最初の実引数にその 子ノードの局面を表すデータを記述 することで行い、その 局面のデータ は作成した Node クラスのインスタンスの mb 属性に代入 されます。

上記のプログラムを 4 行目の deepcopy を削除 し、6 行目で子ノードを作成した後で unmove を呼び出して 5 行目で行った 着手を取り消すように修正 してしまうと、6 行目で作成した 子ノードの mb の局面 が 親ノードの局目のデータに変化 してしまうという バグが発生 します。Node クラスのインスタンスの mb 属性 に記録する 局面のデータ は、ノードごとにそれぞれ別々のデータを記録する必要 があるので、このプログラムから deepcopy を削除して unmove に置き換えることはできません。

このように、子ノードの計算を行う際 に、常に着手の取り消しを行えるわけではありません。局面のデータの コピーが必須となる場合がある 点に注意して下さい。

今回の記事のまとめ

今回の記事では ボトルネックと処理の高速化についての関係 について説明し、ai_by_score のボトルネックを検証して実際に deepcopy が ai_by_score のボトルネックになっていることを示しました。また、ai_by_mmscore の高速化と検証を行うことで、ai_by_score の deepcopy は大きなボトルネックになっている が、ai_by_mmscore の deepcopy はそれほど大きなボトルネックにはなっていない ことを説明しました。

他にも、ai_by_mmscore の中で PV を計算する際の deepcopy のように、ボトルネックになっていないものは修正する必要がない ことや、unmove に置き換えることができない deepcopy がある ことなど説明しました。

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

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

〇× ゲームは 9 回の着手を行うと必ず決着がついた局面になります。AI の関数は決着がついていない局面に対する最善手を計算するので、9 回の着手を行った局面は除外しました ↩
仮引数 analyze が True、random が False、debug が True の場合は異なる処理が行われますが、通常は analyze には False、random には True、debug には False が代入されて実行されるので、その場合の処理を考えることにしました ↩
エラーの原因はよくわかりませんでした。ご存じの方がいればコメントで教えて頂ければ大変助かります ↩

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

着手の回数	`ai2s` の処理時間	`ai14s` の処理時間
0	362	530
1	328	488
2	306	454
3	277	401
4	236	333
5	213	288
6	143	187
7	108	152
8	58	78

着手の回数	`ai2s` の処理時間	`ai14s` の処理時間
0	362	530
1	328	488
2	306	454
3	277	401
4	236	333
5	213	288
6	143	187
7	108	152
8	58	78

Pythonで〇×ゲームのAIを一から作成する その187 ボトルネックと処理の高速化の関係

目次と前回の記事

これまでに作成したモジュール

ボトルネックと処理の高速化の関係

ai_by_score の高速化

ベンチマークの設定と修正前の処理時間の計測

ai_by_score の修正

ai2s と ai14s の再定義と処理時間の比較

処理時間の短縮の原因の検証

ボトルネックの分析

手順 1、2-3、3 の処理時間の計測

手順 2-4 の処理時間の計測

ai_by_score の処理時間のまとめ

ai_by_mmscore の高速化

ベンチマークの設定と修正前の処理時間の計測

ai_by_mmscore の修正

ai_abs_dls の再定義と処理時間の比較

処理時間の短縮の原因検証

もう一つの ai_by_mmscore の deepcopy

その他の deepcopy に対する修正の必要性

marubatsu.py の deepcopy

tree.py の deepcopy

今回の記事のまとめ

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

Pythonで〇×ゲームのAIを一から作成する　その187　ボトルネックと処理の高速化の関係

`ai_by_score` の高速化

`ai_by_score` の修正

`ai2s` と `ai14s` の再定義と処理時間の比較

`ai_by_score` の処理時間のまとめ

`ai_by_mmscore` の高速化

`ai_by_mmscore` の修正

`ai_abs_dls` の再定義と処理時間の比較

もう一つの `ai_by_mmscore` の `deepcopy`

その他の `deepcopy` に対する修正の必要性

marubatsu.py の `deepcopy`

tree.py の `deepcopy`

着手の回数	`ai2s` の処理時間	`ai14s` の処理時間
0	362	530
1	328	488
2	306	454
3	277	401
4	236	333
5	213	288
6	143	187
7	108	152
8	58	78