Pythonで〇×ゲームのAIを一から作成する その107 ゲーム木を利用した強解決のAIの作成とエラーメッセージによるデバッグ

目次と前回の記事

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

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

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
util.py	ユーティリティ関数の定義。現在は gui_play のみ定義されている
tree.py	ゲーム木に関する Node、Mbtree クラスの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

ルールベースの AI の一覧については、下記の記事を参照して下さい。

ゲーム木を利用した強解決の AI の作成

これまでの記事で、全てのノードの評価値が計算された〇×ゲームのゲーム木が作成されたので、それを使って 強解決の AI を 以下の手順で作成 することができます。

1. ゲーム木の中で、現在の局面を表すノードを探す
2. そのノードを使って、その局面の 最善手を調べ、その中から ランダムに着手を選択 する

ノードの評価値 は、最善手を着手した場合の子ノードの評価値 から計算されるので、上記の手順 2 で最善手を探す処理は、ノードの評価値と同じ評価値を持つ子ノードを計算 するという処理になります。

強解決の AI の関数の仕様

ゲーム木を利用した強解決の AI の処理を行う下記のような関数を定義する事にします。

名前：ゲーム木（game tree）を使って処理を行うので ai_gt1 とする
処理：ゲーム木を使って〇×ゲームの局面の最善手の中からランダムに着手を選択する
入力：仮引数 mb に Marubatsu クラスのインスタンスを、仮引数 mbtree に評価値が計算されたゲーム木を代入する
出力：最善手の中の一つ

局面を表すノードの計算

ai_gt1 では、先程説明したように、最初にゲーム木の中で 現在の局面を表すノードを探す 必要があります。どのような方法で探すことができるかについて少し考えてみて下さい。

records 属性を利用した計算

Marubastu クラスには、その局面に至るまでに行われた 棋譜（着手の一覧）を記録した records 属性 があります。また、Node クラスには 着手をキー とし、その 着手が行われた子ノードをそのキーの値 とする children_by_move 属性 があります。この 2 つを利用することで、Marubatsu クラスの局面を表すノードをゲーム木から探すことができます。

忘れた方が多いかもしれないので、Marubatsu クラスのインスタンスを作成し、いくつか着手を行った場合のゲーム盤と records 属性の値を下記のプログラムで表示します。

from marubatsu import Marubatsu

mb = Marubatsu()
mb.move(0, 1)
mb.move(1, 1)
mb.move(1, 0)
print(mb)
print(mb.records)

実行結果

Turn x
.O.
ox.
...

[None, (0, 1), (1, 1), (1, 0)]

records 属性には、n 手目 で行われた着手を n 番のインデックスに代入 するので、実行結果のように、0 番からではなく、1 番のインデックスの要素から 順番に着手が記録される点に注意して下さい。

下記は、mb が表す局面のノードを records 属性を利用して mbtree のルートノードから探して表示するように ai_gt1 を実装したプログラムです。

• 4 行目：mb を表すノードを計算する node を、mbtree のルートノードで初期化する
• 5 行目：スライス表記 を使って、mb の records 属性の 1 番の要素から 順番に着手のデータを取り出して move に代入するという繰り返し処理を行う
• 6 行目：node を、move の着手を行った局面の子ノードの値で更新する
• 7 行目：node にはルートノードから records 属性に記録された着手を順番に行った局面のノードが代入されるので、その値を返り値として返す

1  from tree import Mbtree
2
3  def ai_gt1(mb, mbtree):
4      node = mbtree.root
5      for move in mb.records[1:]:
6          node = node.children_by_move[move]
7      return node

行番号のないプログラム

from tree import Mbtree

def ai_gt1(mb, mbtree):
    node = mbtree.root
    for move in mb.records[1:]:
        node = node.children_by_move[move]
    return node

下記のプログラムで、ai_gt1 を実行すると実行結果のように、ルートノードから (0, 1)、(1, 1)、(1, 0) の順で着手を行った mb の局面を表すノードを、中心かつ選択状態とする部分木が正しく表示されることが確認できます。

• 1 行目：評価値が計算されたゲーム木のデータをファイルから読み込んで mbtree に代入する。幅優先アルゴリズムで計算したゲーム木と、深さ優先アルゴリズムで計算したゲーム木は、ゲーム木の構成は全く同じなのでどちらのデータを読み込んでもかまわない
• 2 行目：mb と mbtree を実引数に記述して ai_gt1 を呼び出し、mb の局面のノードを表す返り値を node に代入する
• 3 行目：node が正しく計算されているかどうかを確認するために、node を中心かつ選択されたノードとし、node より 1 つ深い深さのノードまでの部分木を表示する

mbtree = Mbtree.load("dfscore")
node = ai_gt1(mb, mbtree)
mbtree.draw_subtree(centernode=node, selectednode=node, maxdepth=node.depth + 1)

実行結果

また、赤枠の局面は × の手番の局面なので、上図から この局面の最善手 は、黄色の子ノードに至る (0, 0)、(2, 0)、(0, 2) であることがわかります。

最善手の一覧の計算

mb の局面を表すノードが計算できたので、そのノードから最善手の一覧を計算することにします。先ほど説明したように、最善手の一覧は ノードの評価値と同じ評価値を持つ子ノードを計算 することで求められるので、下記のプログラムで実装できます。

• 6 行目：最善手の一覧を計算する bestmoves を空の list で初期化する
• 7 行目：子ノードの一覧を表す children_by_move から、着手を表すキーと子ノードを表すキーの値を取り出して move と childnode に代入するという繰り返し処理を行う
• 8、9 行目：mb の局面を表す node の評価値と、子ノードの評価値が等しい場合は、move が最善手なので、bestmoves に追加する
• 10 行目：bestmoves を返り値として返す

 1  def ai_gt1(mb, mbtree):
 2      node = mbtree.root
 3      for move in mb.records[1:]:
 4          node = node.children_by_move[move]
 5
 6      bestmoves = []
 7      for move, childnode in node.children_by_move.items():
 8          if node.score == childnode.score:
 9              bestmoves.append(move)
10      return bestmoves

行番号のないプログラム

def ai_gt1(mb, mbtree):
    node = mbtree.root
    for move in mb.records[1:]:
        node = node.children_by_move[move]

    bestmoves = []
    for move, childnode in node.children_by_move.items():
        if node.score == childnode.score:
            bestmoves.append(move)
    return bestmoves

修正箇所

def ai_gt1(mb, mbtree):
    node = mbtree.root
    for move in mb.records[1:]:
        node = node.children_by_move[move]

+   bestmove = []
+   for move, childnode in node.children_by_move.items():
+       if node.score == childnode.score:
+           bestmove.append(move)
+   return bestmove

上記の修正後に、下記のプログラムで mb の局面の最善手の一覧を計算して表示すると、実行結果に先程の図で確認した (0, 0)、(2, 0)、(0, 2) が表示されるので、正しい処理が行われることが確認できます。

print(ai_gt1(mb, mbtree))

実行結果

[(0, 0), (2, 0), (0, 2)]

着手の計算

ai_gt1 は最善手の中からランダムな着手を行うので、これまで定義してきた AI と同様の方法で random モジュールの choice を使って、下記のプログラムのように定義できます。

• 7 行目：random モジュールの choice を使って bestmoves の中から 1 つをランダムに選んで返すように修正する

1  from random import choice
2
3  def ai_gt1(mb, mbtree):
元と同じなので省略
4      for move, childnode in node.children_by_move.items():
5          if node.score == childnode.score:
6              bestmoves.append(move)
7      return choice(bestmoves)

行番号のないプログラム

from random import choice

def ai_gt1(mb, mbtree):
    node = mbtree.root
    for move in mb.records[1:]:
        node = node.children_by_move[move]

    bestmoves = []
    for move, childnode in node.children_by_move.items():
        if node.score == childnode.score:
            bestmoves.append(move)
    return choice(bestmoves)

修正箇所

+from random import choice

def ai_gt1(mb, mbtree):
元と同じなので省略
    for move, childnode in node.children_by_move.items():
        if node.score == childnode.score:
            bestmoves.append(move)
-   return bestmoves
+   return choice(bestmoves)

上記の修正後に、下記のプログラムで mb の最善手を 10 回表示すると、実行結果のように最善手である (0, 0)、(2, 0)、(0, 2) の中からランダムに着手が選択されることが確認できます。

for i in range(10):
    print(ai_gt1(mb, mbtree))

実行結果（実行結果はランダムなので下記と異なる場合があります）

(0, 2)
(0, 2)
(0, 2)
(0, 2)
(2, 0)
(2, 0)
(0, 2)
(0, 0)
(2, 0)
(0, 0)

ai_match による対戦

ai_gt1 の実装が完了したので、その性能を確認するために ai_match を使ってランダムな着手を行う ai2s と複数回対戦した結果を表示することにします。

しかし、下記のプログラムを実行すると実行結果のような エラーが発生 します。このエラーが発生する原因について少し考えてみて下さい。

from ai import ai2s, ai_match

ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}])

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[8], line 3
      1 from ai import ai2s, ai_match
----> 3 ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}])

File c:\Users\ys\ai\marubatsu\107\ai.py:47, in ai_match(ai, params, match_num)
     45 count_list = [ defaultdict(int), defaultdict(int)]
     46 for _ in range(match_num):
---> 47     count_list[0][mb.play(ai, params, verbose=False)] += 1
     48     count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1
     50 # ai[0] から見た通算成績を計算する

File c:\Users\ys\ai\marubatsu\107\marubatsu.py:343, in Marubatsu.play(self, ai, ai_dict, params, verbose, seed, gui, size)
    340     mb_gui = None
    342 self.restart()
--> 343 return self.play_loop(mb_gui)

File c:\Users\ys\ai\marubatsu\107\marubatsu.py:381, in Marubatsu.play_loop(self, mb_gui)
    379 # ai が着手を行うかどうかを判定する
    380 if ai[index] is not None:
--> 381     x, y = ai[index](self, **params[index])
    382 else:
    383     # キーボードからの座標の入力
    384     coord = input("x,y の形式で座標を入力して下さい。exit を入力すると終了します")

TypeError: ai_gt1() missing 1 required positional argument: 'mbtree'

ai_match のエラーの検証

結論からいうと、このエラーは筆者の不注意によるバグ原因でした。ただし、このような不注意によるバグは頻繁に発生する ので、このバグの検証方法を紹介することにします。

エラーメッセージの最後の部分の検証

エラーメッセージ には、エラーの原因を検証するための ヒントが数多く含まれています。今回の検証では、エラーメッセージからバグを検証する方法を紹介します。

実際のバグの検証では、エラーメッセージだけから原因を見つけることができない場合が良くあります。下記の方法はうまく見つけることができる例だと考えて下さい。

下記はエラーメッセージの最後の部分のを抜粋したものです。

File c:\Users\ys\ai\marubatsu\107\marubatsu.py:381, in Marubatsu.play_loop(self, mb_gui)

--> 381     x, y = ai[index](self, **params[index])

TypeError: ai_gt1() missing 1 required positional argument: 'mbtree'

上記のメッセージから下記の事がわかります。

• Marubatsu クラスの play_loop メソッドの 実行中 にエラーが発生した
• x, y = ai[index](self, **params[index]) の行でエラーが発生した
• 最後の行から、エラーの原因は ai_gt1 が呼び出された際 に、位置引数（positional argument）mbtree が記述されていなかった（missing）ことである

そこで、エラーが発生した x, y = ai[index](self, **params[index]) の行の処理を検証することにします。この処理によって ai_gt1 が呼び出された際にエラーが発生しているので、ai_gt1 の返り値は計算されていません。従って、この行の処理の中で、返り値を x と y に代入する処理は、エラーとは無関係 なので、代入処理を除いた下記のプログラムを検証することにします。

ai[index](self, **params[index])

変数の検証

上記の処理では、ai、index、self、params の 4 つの変数が使われている ので、それらの変数について検証します。

ai と params は、最初に実行した下記のプログラムの、キーワード引数に代入されたデータである可能性が高い ので、そうであるという前提で検証を行います。

ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}])

先程のプログラムは、Marubatsu クラスの play_loop メソッドの中で実行されたので、self は Marubatsu クラスのインスタンス です。ai_match では、下記のプログラムの 4 行目ように、対戦を行うために Marubatsu クラスのインスタンスを作成しているので、おそらく この mb が self を表している可能性が高い でしょう。

1  def ai_match(ai:list, params:list[dict]=[{}, {}], match_num:int=10000):
2      print(f"{ai[0].__name__} VS {ai[1].__name__}")
3    
4      mb = Marubatsu()
以下省略

エラーメッセージから ai[index](self, **params[index]) の処理によって ai_gt1 が呼び出されたことがわかるので、ai[index] は ai_gt1 を表す ことがわかります。ai には [ai_gt1, ai2s] が代入されているという前提で検証を行っているので、index には 0 が代入されている可能性が高い でしょう。

上記の検証を元に、下記のプログラムのようにローカル変数 ai、params、index に上記で 推定した値を代入 し、self を Marubatsu クラスのインスタンスに 置き換えて エラーが発生したプログラムを実行してみると、実行結果のように エラーは発生せず、着手が計算されることがわかりました。

mb = Marubatsu()
ai=[ai_gt1, ai2s]
params=[{"mbtree": mbtree}, {}]
print(ai[0](mb, **params[0]))

実行結果（実行結果はランダムなので下記と異なる場合があります）

(2, 2)

上記から、ai[index](self, **params[index]) の 処理そのものは間違っておらず、この処理が実行された際の ai、index、self、params のいずれかの値が間違っている可能性が高い ことがわかります。 そのことと「位置引数 mbtree が記述されていない」という内容のエラーメッセージから、おそらく params の値がおかしい可能性が高い ことが推測されます。

ここまでで説明したように、エラーメッセージから読み取れるのは、一般的には原因そのものではなく、原因を推測するためのヒント です。そのヒントに従って 絞り込んでいくことでバグの原因を検証 を検証します。

エラーメッセージ全体の検証

上記の考察から、params の値がおかしい可能性が高いことはわかりましたが、params の値がおかしくなった 原因まではわかりません。そこでその原因を見つけるために、エラーメッセージ全体を検証することにします。

下記は、エラーメッセージの中の重要な部分を抜粋したものです。

----> 3 ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}])

File c:\Users\ys\ai\marubatsu\107\ai.py:47, in ai_match(ai, params, match_num)

---> 47     count_list[0][mb.play(ai, params, verbose=False)] += 1

File c:\Users\ys\ai\marubatsu\107\marubatsu.py:343, in Marubatsu.play(self, ai, ai_dict, params, verbose, seed, gui, size)

--> 343 return self.play_loop(mb_gui)

File c:\Users\ys\ai\marubatsu\107\marubatsu.py:381, in Marubatsu.play_loop(self, mb_gui)

--> 381     x, y = ai[index](self, **params[index])

TypeError: ai_gt1() missing 1 required positional argument: 'mbtree'

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

• 最初に ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}]) を実行して ai_match を呼び出した
• ai_match の中で count_list[0][mb.play(ai, params, verbose=False)] += 1 を実行して play メソッドを呼び出した
• play メソッドの中で return self.play_loop(mb_gui) を実行して play_loop メソッドを呼び出した
• play_loop メソッドの中で x, y = ai[index](self, **params[index]) を実行してエラーが発生した

そこで、上記の処理を順番に検証することにします。

下記は、ai_match の定義の一部です。

 1  def ai_match(ai, params=[{}, {}], match_num=10000):
 2      print(f"{ai[0].__name__} VS {ai[1].__name__}")
 3   
 4      mb = Marubatsu()
 5
 6      # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
 7      count_list = [ defaultdict(int), defaultdict(int)]
 8      for _ in range(match_num):
 9          count_list[0][mb.play(ai, params, verbose=False)] += 1
10          count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1
以下略

上記のプログラムから以下の事がわかります。

• ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}]) を呼び出した結果、仮引数 ai と params にキーワード引数 ai と params の値が代入される
• 2 ~ 8 行目までの間で、ai と params の値を変更する処理は行われない
• 9 行目でエラーメッセージに表示された、play メソッドを呼び出す処理が行われる
• 9 行目の処理の中で、play メソッドを呼び出す処理を抜き出すと以下のプログラムのようになり、この play メソッドの呼び出しの 実引数 ai と params には、最初に ai_match のキーワード引数に記述されていた値が代入されている

mb.play(ai, params, verbose=False)

そこで、次は play メソッドの処理を検証します。下記の play メソッドの定義から、上記の実引数 ai と params は、play メソッドの仮引数 ai と ai_dict に代入されます。

def play(self, ai, ai_dict=None, params=None, verbose=True, seed=None, gui=False, size=3):
以下省略

ここで、実引数 params の値 が、play メソッドの仮引数 params ではなく、ai_dict に代入される という、おかしな処理が行われていることが判明しました。また、仮引数 params は None をデフォルト値とするデフォルト引数で、play メソッドを呼び出した際に仮引数 params に対応する実引数を記述していないので、仮引数 params には None が代入される ことになります。このことから、最初の検証で判明した params の値が間違っているという推測が正しいこと と、その原因が判明 しました。

従って、このバグは下記のプログラムの 11 行目のように play メソッドを呼び出す際にキーワード引数 param=params を記述するように ai_match を修正することで解決できます。

 1  from collections import defaultdict
 2
 3  def ai_match(ai, params=[{}, {}], match_num=10000):
 4      print(f"{ai[0].__name__} VS {ai[1].__name__}")
 5   
 6      mb = Marubatsu()
 7
 8      # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
 9      count_list = [ defaultdict(int), defaultdict(int)]
10      for _ in range(match_num):
11          count_list[0][mb.play(ai, params=params, verbose=False)] += 1
12          count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1

行番号のないプログラム

from collections import defaultdict

def ai_match(ai, params=[{}, {}], match_num:int=10000):
    print(f"{ai[0].__name__} VS {ai[1].__name__}")
    
    mb = Marubatsu()

    # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
    count_list = [ defaultdict(int), defaultdict(int)]
    for _ in range(match_num):
        count_list[0][mb.play(ai, params=params, verbose=False)] += 1
        count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1

    # ai[0] から見た通算成績を計算する
    count_list_ai0 = [
        # ai[0] VS ai[1] の場合の、ai[0] から見た通算成績
        { 
            "win": count_list[0][Marubatsu.CIRCLE],
            "lose": count_list[0][Marubatsu.CROSS],
            "draw": count_list[0][Marubatsu.DRAW],
        },
        # ai[1] VS ai[0] の場合の、ai[0] から見た通算成績
        { 
            "win": count_list[1][Marubatsu.CROSS],
            "lose": count_list[1][Marubatsu.CIRCLE],
            "draw": count_list[1][Marubatsu.DRAW],
        },
    ]           

    # 両方の対戦の通算成績の合計を計算する
    count_list_ai0.append({})
    for key in count_list_ai0[0]:
        count_list_ai0[2][key] = count_list_ai0[0][key] + count_list_ai0[1][key]

    # それぞれの比率を計算し、ratio_list に代入する
    ratio_list = [ {}, {}, {} ]
    for i in range(3):
        for key in count_list_ai0[i]:
            ratio_list[i][key] = count_list_ai0[i][key] / sum(count_list_ai0[i].values())
            
    # 各行の先頭に表示する文字列のリスト
    item_text_list = [ Marubatsu.CIRCLE, Marubatsu.CROSS, "total" ]    
    
    # 通算成績の回数と比率の表示
    width = max(len(str(match_num * 2)), 7)
    diff_list = [ ("count", count_list_ai0, f"{width}d"),
                  ("ratio", ratio_list, f"{width}.1%") ]
    for title, data, format in diff_list:
        print(title, end="")
        for key in data[0]:
            print(f" {key:>{width}}", end="")
        print()
        for i in range(3):
            print(f"{item_text_list[i]:5}", end="")
            for value in data[i].values():
                print(f" {value:{format}}", end="")
            print()
        print()

修正箇所

from collections import defaultdict

def ai_match(ai, params=[{}, {}], match_num:int=10000):
    print(f"{ai[0].__name__} VS {ai[1].__name__}")
    
    mb = Marubatsu()

    # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
    count_list = [ defaultdict(int), defaultdict(int)]
    for _ in range(match_num):
-       count_list[0][mb.play(ai, params, verbose=False)] += 1
+       count_list[0][mb.play(ai, params=params, verbose=False)] += 1
        count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1
元と同じなので省略

バグが混入された原因

このようなバグがプログラムに混入した原因は play メソッドが 以前の記事では下記のプログラムのように 仮引数 ai の直後に仮引数 params が記述されていた からです。

def play(self, ai, params, verbose=True):
以下省略

その後 で、play メソッドの 仮引数 ai の直後に仮引数 ai_dict 記述するように修正した際に ai_match の中で play メソッドを呼び出す処理を修正し忘れた のがバグの原因です。

また、これまでの記事でこのバグが発生したなかったのは、play メソッドに 仮引数 ai_dict を追加した後で、ai_match の実引数に キーワード引数 params を記述して呼び出すことがなかったから です。このように、バグが存在していても、そのバグに関連する処理が行われるまでの 長い間¹、その バグが明るみに出ないことが良くあります。

下記のプログラムを見ればわかるように、エラーの原因となった次の 3 行目では、play メソッドを呼び出す際にキーワード引数 params を正しく記述していました。このことから、このエラーは筆者の不注意によるものであることがわかります。ただし、このような不注意を完全に無くすことは不可能なので、このようなバグが発生した際に、原因を見つけてバグを修正する能力を身に付けることが重要になります。

1  for _ in range(match_num):
2      count_list[0][mb.play(ai, params=params, verbose=False)] += 1
3      count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1

新たなバグの検証とその修正

上記の修正後に改めて下記のプログラムを実行すると、エラーは発生しなくなりますが、今後は 処理が終わらないという問題が発生 します。筆者のパソコンで 5 分以上待ちましたが、処理は終わりませんでした。このようなことが起きる原因について少し考えてみて下さい。

ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}])

実行結果（下記が表示された後に何も表示されない）

ai_gt1 VS ai2s

この後の検証で判明しますが、上記の処理は無限ループなどによって処理が終わらなくなっているわけではなく、deepcopy による処理に非常に長い時間がかかることが原因です。従って、気長に待てば上記の処理はいつかは終了しますが、処理に時間がかかりすぎるのは大きな問題なので、この問題を修正する必要があります。

中断メッセージによる原因の検証

プログラムの 処理がなかなか終わらない場合 は、以前の記事で紹介した JupyterLab の上部にある「割り込み」ボタンをクリックすることで、プログラムの処理を中断 することができます。割り込みボタンは、再起動ボタンとは異なり 変数に代入されたデータは残っている ので、そのまま続きの処理を行うことができます。

割り込みボタンをクリックすると、下記のような 中断メッセージ が表示されます。このメッセージには、割り込みボタンが押された際に実行されていた処理の流れ が、エラーメッセージと同様の方法で表示 されます。

略
File c:\Users\ys\Anaconda3\envs\marubatsu\Lib\copy.py:219, in _deepcopy_tuple(x, memo, deepcopy)
    217     pass
    218 for k, j in zip(x, y):
--> 219     if k is not j:
    220         y = tuple(y)
    221         break

KeyboardInterrupt: 

JupyterLab では割り込みボタンでプログラムの処理を中断しますが、JupyterLab 以外で Python のプログラムを実行する場合は、一般的に Ctrl + C キーによって処理を中断（interrupt）するので、最後に KeyboardInterrupt が表示されます。

メッセージから、_deepcopy_tuple という名前の関数の 処理中に処理が中断された ことがわかります。関数の名前から おそらく、copy モジュールの deepcopy に関連する処理 であることが推測されます。そのことは、メッセージの全体を見る ことで確認できます。

下記は、メッセージの前半に記述されている内容で、この内容から ai2s から呼び出された ai_by_score の中 で、確かに mb = deepcopy(mb_orig) によって deepcopy が呼び出されている ことが確認できます。

File c:\Users\ys\ai\marubatsu\107\ai.py:253, in ai2s(mb, debug)
    250 def eval_func(mb):
    251     return 0
--> 253 return ai_by_score(mb, eval_func, debug=debug)

File c:\Users\ys\ai\marubatsu\107\ai.py:130, in ai_by_score(mb_orig, eval_func, debug, rand)
    128 dprint(debug, "=" * 20)
    129 dprint(debug, "move", move)
--> 130 mb = deepcopy(mb_orig)
    131 x, y = move
    132 mb.move(x, y)

以前の記事で説明したように、deepcopy は オブジェクトをコピーする という処理を行います。従って、コピーする データのサイズが大きくなると処理時間が増える ことになります。また、mb = deepcopy(mb_orig) から、コピーするデータは Marubatsu クラスのインスタンス であることがわかります。このことから、何らかの理由で Marubatsu クラスのインスタンスのデータが大きく増えた ことが原因で処理時間が増えたことが推測されます。

Marubatsu クラスのインスタンスのデータサイズが増える原因の検証

ai_gt1 を実装する前は、ai_match の処理にはそれほど長い時間がかかりませんでした。そこで、念のために下記のプログラムで ai_match を使って ai2s どうしの対戦を行ってみることにします。実行結果は省略しますが、筆者のパソコンでは約 1 分で処理が終わったので、やはり ai_gt1 が対戦したことが原因である可能性が高い でしょう。

ai_match(ai=[ai2s, ai2s])

上記と、下記の処理が終わらないプログラムを比べると、params に〇×ゲームのゲーム木のデータが記述されている点が異なる ことがわかります。

ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}])

〇×ゲームの ゲーム木のデータ は、そのデータを保存した dfscore.mbtree の ファイルサイズが約 15 MB バイトもある 事から、その データサイズが大きい ことがわかります。そのため、ai_gt1 と対戦を行う場合に、何らかの理由で Marubatsu クラスのインスタンスに ゲーム木のデータが含まれるようになったことが推測されます。

そのことを確認するために、上記の ai_match の処理で行われる処理を検証 することにします。先ほど説明したように、上記のプログラムを実行すると、下記の ai_match の 9 行目が実行されます。その際に仮引数 ai と params には、ai_match を呼び出した際のキーワード引数の値が代入されています。

 1  def ai_match(ai, params=[{}, {}], match_num=10000):
 2      print(f"{ai[0].__name__} VS {ai[1].__name__}")
 3   
 4      mb = Marubatsu()
 5
 6      # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
 7      count_list = [ defaultdict(int), defaultdict(int)]
 8      for _ in range(match_num):
 9          count_list[0][mb.play(ai, params=params, verbose=False)] += 1
10          count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1

下記は、play メソッドの一部です。8 行目で、Marubastu クラスのインスタンスを表す self の params 属性に、仮引数 params を代入 していることがわかります。ai_match で ai_gt1 と対戦する場合は、この params に [{"mbtree": mbtree}, {}] が代入されているので、この処理で Marubatsu クラスのインスタンスに データサイズが大きい ゲーム木のデータが代入される ことが実際に確認できました。

 1  def play(self, ai, ai_dict=None, params=None, verbose=True, seed=None, gui=False, size=3):
 2      # params が None の場合のデフォルト値を設定する
 3      if params is None:
 4          params = [{}, {}]
 5            
 6      # 一部の仮引数をインスタンスの属性に代入する
 7      self.ai = ai
 8      self.params = params
 9      self.verbose = verbose
10      self.gui = gui
以下省略

バグが混入された原因

このバグが混入された原因は、以前の記事 で play_loop を呼び出す際の仮引数を削除するため に、play_loop の 仮引数 params などに代入されていたデータを上記 play メソッドの 7 ~ 10 行目で Marubatsu クラスのインスタンスに代入するように修正 したことです。

上記の修正を行った時点では params には大きなデータが代入されることはなかったので deepcopy の処理時間に影響はほとんど与えませんでしたが、ai_gt1 のように params に大きなデータが代入されるようになった今では、この修正によって問題が発生します。

このように、良かれと思って行った修正や仕様 が、後で状況が変わった際に 思わぬバグや不具合の原因となる ことが良くあります²。

バグの修正

params の値 は、play_loop メソッドの中でしか利用しない ので、params をインスタンスの属性にはせずに、実引数で play_loop に渡す ようにすることで、この問題を解決することができます。なお、上記の 7 ~ 10 行目の ai、verbose、gui 等の仮引数をインスタンスの属性に代入したままで良いかが気になっている人がいるかもしれませんが、ai に代入される 関数オブジェクトは、コピーしても処理に長い時間がかかることはありません。また、verbose、gui に代入される bool 型のデータは、データサイズが小さい のでこのままでも問題はありません。

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

• 6 行目の下にあった self.params = params を削除する
• 9 行目：play_loop を呼び出す際に、params=params を記述するように修正する

 1  from marubatsu import Marubatsu_GUI
 2  import random
 3
 4  def play(self, ai, ai_dict=None, params=None, verbose=True, seed=None, gui=False, size=3):
元と同じなので省略    
 5      # 一部の仮引数をインスタンスの属性に代入する
 6      self.ai = ai
 7      self.verbose = verbose
 8      self.gui = gui
元と同じなので省略    
 9      return self.play_loop(mb_gui, params=params)
10
11  Marubatsu.play = play

行番号のないプログラム

from marubatsu import Marubatsu_GUI
import random

def play(self, ai, ai_dict=None, params=None, verbose=True, seed=None, gui=False, size=3):
    # params が None の場合のデフォルト値を設定する
    if params is None:
        params = [{}, {}]
        
    # 一部の仮引数をインスタンスの属性に代入する
    self.ai = ai
    self.verbose = verbose
    self.gui = gui
    
    # seed が None でない場合は、seed を乱数の種として設定する
    if seed is not None:
        random.seed(seed)

    # gui が True の場合に、GUI の処理を行う Marubatsu_GUI のインスタンスを作成する
    if gui:
        mb_gui = Marubatsu_GUI(self, ai_dict=ai_dict, seed=seed, size=size)  
    else:
        mb_gui = None
        
    self.restart()
    return self.play_loop(mb_gui, params=params)

Marubatsu.play = play

修正箇所

from marubatsu import Marubatsu_GUI
import random

def play(self, ai, ai_dict=None, params=None, verbose=True, seed=None, gui=False, size=3):
元と同じなので省略    
    # 一部の仮引数をインスタンスの属性に代入する
    self.ai = ai
-   self.params = params
    self.verbose = verbose
    self.gui = gui
元と同じなので省略    
-   return self.play_loop(mb_gui)
+   return self.play_loop(mb_gui, params=params)

Marubatsu.play = play

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

• 1 行目：デフォルト値を None とする仮引数 params を追加する
• 2、3 行目：params が None の場合は [{}, {}] を代入する。この処理は play_loop が play メソッド以外では Marubatsu_GUI から呼び出されている ので、その互換性を保つために行う必要がある。なお、Marubatsu_GUI を利用して ai_gt1 で対戦を行う場合は Marubatsu_GUI 内で行う play_loop の呼び出しの処理の修正を行う必要があるが、その修正は今後の記事で行う
• 5 行目の下にあった params = self.params を削除する

1  def play_loop(self, mb_gui, params=None):
2      if params is None:
3          params = [{}, {}]
4
5      ai = self.ai
6      verbose = self.verbose
7      gui = self.gui
元と同じなので省略    
8
9  Marubatsu.play_loop = play_loop

行番号のないプログラム

def play_loop(self, mb_gui, params=None):
    if params is None:
        params = [{}, {}]

    ai = self.ai
    verbose = self.verbose
    gui = self.gui
    
    # ゲームの決着がついていない間繰り返す
    while self.status == Marubatsu.PLAYING:
        # 現在の手番を表す ai のインデックスを計算する
        index = 0 if self.turn == Marubatsu.CIRCLE else 1
        # ゲーム盤の表示
        if verbose:
            if gui:
                # AI どうしの対戦の場合は画面を描画しない
                if ai[0] is None or ai[1] is None:
                    mb_gui.update_gui()
                # 手番を人間が担当する場合は、play メソッドを終了する
                if ai[index] is None:
                    return
            else:
                print(self)
                
        # ai が着手を行うかどうかを判定する
        if ai[index] is not None:
            x, y = ai[index](self, **params[index])
        else:
            # キーボードからの座標の入力
            coord = input("x,y の形式で座標を入力して下さい。exit を入力すると終了します")
            # "exit" が入力されていればメッセージを表示して関数を終了する
            if coord == "exit":
                print("ゲームを終了します")
                return       
            # x 座標と y 座標を要素として持つ list を計算する
            xylist = coord.split(",")
            # xylist の要素の数が 2 ではない場合
            if len(xylist) != 2:
                # エラーメッセージを表示する
                print("x, y の形式ではありません")
                # 残りの while 文のブロックを実行せずに、次の繰り返し処理を行う
                continue
            x, y = xylist
        # (x, y) に着手を行う
        try:
            self.move(int(x), int(y))
        except:
            print("整数の座標を入力して下さい")

    # 決着がついたので、ゲーム盤を表示する
    if verbose:
        if gui:
            mb_gui.update_gui()
        else:
            print(self)
            
    return self.status

Marubatsu.play_loop = play_loop

修正箇所

def play_loop(self, mb_gui, params=None):
    if params is None:
        params = [{}, {}]

    ai = self.ai
-   params = self.params
    verbose = self.verbose
    gui = self.gui
元と同じなので省略    

Marubatsu.play_loop = play_loop

ai_match による対戦

上記の修正後に、下記のプログラムで ai_match による対戦を行うと、筆者のパソコンでは約 20 秒で実行結果が表示されたので、問題は解決されたことが確認できました。

ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree": mbtree}, {}])

実行結果

ai_gt1 VS ai2s
count     win    lose    draw
o        9690       0     310
x        7795       0    2205
total   17485       0    2515

ratio     win    lose    draw
o       96.9%    0.0%    3.1%
x       78.0%    0.0%   22.1%
total   87.4%    0.0%   12.6%

下記は、上記の結果をルールベースで作成した中で最強の AI である ai14s VS ai2s の ai_match による対戦結果と比較したものです。

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分
ai14s	99.0	0.0	1.0	88.8	0.0	11.2	93.9	0.0	6.1
ai_gt1	96.9	0.0	3.1	78.0	0.0	22.1	87.4	0.0	12.6

この比較を見ると、強解決の AI であるはずの ai_gt1 よりも 弱解決の ai14s の方が強そうに見えるかもしれませんが、そうではありません。勝率の違い は ai_gt1 が全ての最善手の中からランダムに着手を選択する のに対し、ai14s は ai2s に対して 勝率が高い（相手のミスを誘いやすい）相性の良い着手を選択する 局面が多いという違いから生じたものです。

以前の記事で説明したように、弱解決の AI とすべての局面で最善手を選択する 強解決の AI が対戦 すると 通算成績は必ず互角になります。そのことは、下記のプログラムで ai_gt1 VS ai14s の対戦を行うと、実行結果のように 100 % 引き分けになる ことで確認できます。

from ai import ai14s

ai_match(ai=[ai_gt1, ai14s], params=[{"mbtree": mbtree}, {}])

実行結果

ai_gt1 VS ai14s
count     win    lose    draw
o           0       0   10000
x           0       0   10000
total       0       0   20000

ratio     win    lose    draw
o        0.0%    0.0%  100.0%
x        0.0%    0.0%  100.0%
total    0.0%    0.0%  100.0%

今回の記事のまとめ

今回の記事では、評価値が計算されたゲーム木 を使って、強解決の AI を作成 しました。また、その際にエラーメッセージからバグの原因を検証し、修正する方法を紹介しました。

なお、今後新しく作成した AI は、下記の記事に追加していくことにします。

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

今回の記事で作成した mbtree_bf と mbtree_df の中身は、以前にファイルに保存したデータと全く同じなので、改めてファイルに保存することはしません。

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

次回の記事

1. プログラムを作成してから何十年もたってからこのようなバグが明るみに出ることが実際にあります ↩

2. 類似する例として、世間を大きく騒がせた 2000 年問題があります。興味がある方は調べてみると良いでしょう ↩