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

# 目次と前回の記事

https://qiita.com/ysgeso/items/2381dd4e3283cbed49a0

https://qiita.com/ysgeso/items/94c5105c3dbebb445710

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

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.py](https://github.com/ysgeso/marubatsu/blob/master/107/marubatsu.py)  | Marubatsu、Marubatsu_GUI クラスの定義|
| [ai.py](https://github.com/ysgeso/marubatsu/blob/master/107/ai.py)  |  AI に関する関数 |
|  [util.py](https://github.com/ysgeso/marubatsu/blob/master/107/util.py) |  ユーティリティ関数の定義。現在は `gui_play` のみ定義されている |
| [tree.py](https://github.com/ysgeso/marubatsu/blob/master/107/tree.py)  | ゲーム木に関する Node、Mbtree クラスの定義  |
| [gui.py](https://github.com/ysgeso/marubatsu/blob/master/107/gui.py)  |  GUI に関する処理を行う基底クラスとなる GUI クラスの定義  |

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

https://qiita.com/ysgeso/items/10d1d01192c014173e4b

# ゲーム木を利用した強解決の 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` 属性の値を下記のプログラムで表示します。

```python
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 行目__：__[スライス表記](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#%E3%82%B9%E3%83%A9%E3%82%A4%E3%82%B9%E8%A1%A8%E8%A8%98-%E3%81%9D%E3%81%AE-1start-%E3%81%A8-end)__ を使って、`mb` の `records` 属性の __1 番の要素から__ 順番に着手のデータを取り出して `move` に代入するという繰り返し処理を行う
* __6 行目__：`node` を、`move` の着手を行った局面の子ノードの値で更新する
* __7 行目__：`node` にはルートノードから `records` 属性に記録された着手を順番に行った局面のノードが代入されるので、その値を返り値として返す

```python
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
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
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
```
</details>

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

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

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

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2ee33667-389d-38b5-ed26-3f1ccc0bdc24.png" width="200">

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

## 最善手の一覧の計算

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

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

```python
 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
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
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
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
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
```
</details>

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

実行結果

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

## 着手の計算

`ai_gt1` は最善手の中からランダムな着手を行うので、これまで定義してきた AI と同様の方法で random モジュールの [`choice`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#list-%E3%81%8B%E3%82%89%E3%81%AE%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA%E8%A6%81%E7%B4%A0%E3%81%AE%E9%81%B8%E6%8A%9E) を使って、下記のプログラムのように定義できます。

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

```python
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)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
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)
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
+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)
```
</details>

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

```python
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`](https://qiita.com/ysgeso/items/fc19eb2764e0766b59d5#play-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%A8-ai_match-%E3%81%AE%E4%BF%AE%E6%AD%A3)__ を使ってランダムな着手を行う [`ai2s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E9%96%A2%E6%95%B0%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E3%83%AB%E3%83%BC%E3%83%AB-2-%E3%81%A7%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9) と複数回対戦した結果を表示することにします。

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

```python
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` のエラーの検証

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

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

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

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

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

```
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` が呼び出された際__ に、[位置引数](https://qiita.com/ysgeso/items/c5dbe62b329f7936181a#%E4%BD%8D%E7%BD%AE%E5%BC%95%E6%95%B0%E3%81%A8%E3%82%AD%E3%83%BC%E3%83%AF%E3%83%BC%E3%83%89%E5%BC%95%E6%95%B0)（positional argument）__`mbtree` が記述されていなかった__（missing）ことである

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

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

### 変数の検証

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

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

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

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

```python
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 クラスのインスタンスに __置き換えて__ エラーが発生したプログラムを実行してみると、実行結果のように __エラーは発生せず__、着手が計算されることがわかりました。

```python
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` の定義の一部です。

```python
 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` のキーワード引数に記述されていた値が代入されている__

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

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

```python
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` を修正することで解決できます。

```python
 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
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
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()
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
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
元と同じなので省略
```
</details>

### バグが混入された原因

このようなバグがプログラムに混入した原因は `play` メソッドが [以前の記事](https://qiita.com/ysgeso/items/fc19eb2764e0766b59d5#play-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%A8-ai_match-%E3%81%AE%E4%BF%AE%E6%AD%A3)では下記のプログラムのように __仮引数 `ai` の直後に仮引数 `params` が記述されていた__ からです。

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

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

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

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

```python
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 分以上待ちましたが、処理は終わりませんでした。このようなことが起きる原因について少し考えてみて下さい。

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

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

```
ai_gt1 VS ai2s
```

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

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

プログラムの __処理がなかなか終わらない場合__ は、[以前の記事](https://qiita.com/ysgeso/items/1800a353cb609a0fef4e#%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E5%BC%B7%E5%88%B6%E7%B5%82%E4%BA%86)で紹介した 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: 
```

:::note
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)
```

[以前の記事](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E3%82%B3%E3%83%94%E3%83%BC%E8%A4%87%E8%A3%BD%E3%81%A8-copy-%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB)で説明したように、__`deepcopy`__ は __オブジェクトをコピーする__ という処理を行います。従って、コピーする __データのサイズが大きくなると処理時間が増える__ ことになります。また、`mb = deepcopy(mb_orig)` から、__コピーするデータは Marubatsu クラスのインスタンス__ であることがわかります。このことから、__何らかの理由で Marubatsu クラスのインスタンスのデータが大きく増えた__ ことが原因で処理時間が増えたことが推測されます。

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

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

```python
ai_match(ai=[ai2s, ai2s])
```

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

```python
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` を呼び出した際のキーワード引数の値が代入されています。

```python
 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 クラスのインスタンスに__ データサイズが大きい __ゲーム木のデータが代入される__ ことが実際に確認できました。

```python
 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
以下省略
```

### バグが混入された原因

このバグが混入された原因は、[以前の記事](https://qiita.com/ysgeso/items/c2d569b1be171fbe4b31#%E4%BB%96%E3%81%AE-play_loop-%E3%81%AE%E4%BB%AE%E5%BC%95%E6%95%B0%E3%81%AE%E5%89%8A%E9%99%A4) で __`play_loop` を呼び出す際の仮引数を削除するため__ に、`play_loop` の 仮引数 `params` などに代入されていたデータを上記 `play` メソッドの 7 ~ 10 行目で __Marubatsu クラスのインスタンスに代入するように修正__ したことです。

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

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

### バグの修正

__`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` を記述するように修正する

```python
 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
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
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
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
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
```
</details>


下記は、`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` を削除する


```python
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
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
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
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
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
```
</details>

## `ai_match` による対戦

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

```python
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`](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#ai14s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __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` に対して __勝率が高い（相手のミスを誘いやすい）相性の良い着手を選択する__ 局面が多いという違いから生じたものです。

[以前の記事](https://qiita.com/ysgeso/items/5fe28ae6c765a169fd34#%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E8%A7%A3%E6%B1%BA%E3%81%A8%E3%81%9D%E3%81%AE%E7%A8%AE%E9%A1%9E)で説明したように、__弱解決の AI__ とすべての局面で最善手を選択する __強解決の AI が対戦__ すると __通算成績は必ず互角になります__。そのことは、下記のプログラムで `ai_gt1` VS `ai14s` の対戦を行うと、実行結果のように __100 % 引き分けになる__ ことで確認できます。

```python
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 は、下記の記事に追加していくことにします。

https://qiita.com/ysgeso/items/10d1d01192c014173e4b

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

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/107/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [marubatsu_new.py](https://github.com/ysgeso/marubatsu/blob/master/107/marubatsu_new.py)  | 今回の記事で更新した marubatsu.py |
| [ai_new.py](https://github.com/ysgeso/marubatsu/blob/master/107/ai_new.py)  | 今回の記事で更新した ai.py |

# 次回の記事

https://qiita.com/ysgeso/items/d2c309058e2c60d2e476

[^1]:プログラムを作成してから何十年もたってからこのようなバグが明るみに出ることが実際にあります
[^2]:類似する例として、世間を大きく騒がせた 2000 年問題があります。興味がある方は調べてみると良いでしょう