Pythonで〇×ゲームのAIを一から作成する　その108　ゲーム木を利用した AI の処理の改良とプログレスバーの表示

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/321cf89ef5c49b861650

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

以下のリンクから、これまでに作成したモジュールを見ることができます。test.py を入れ忘れていたので今回から入れています。

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

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

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



# プログレスバーによる途中経過の表示

今回の記事では最初に、今後の記事でも何度も利用する `ai_match` を改良します。

__`ai_match`__ は、__結果が出るまで__ のしばらくの間、__何も表示されない状態で待たされる__ という欠点があります。また、[前回の記事](https://qiita.com/ysgeso/items/321cf89ef5c49b861650#%E6%96%B0%E3%81%9F%E3%81%AA%E3%83%90%E3%82%B0%E3%81%AE%E6%A4%9C%E8%A8%BC%E3%81%A8%E3%81%9D%E3%81%AE%E4%BF%AE%E6%AD%A3)のように、`ai_match` の処理にものすごく長い時間がかかるような場合は、__いつまで待てばよいかの見当がつかない__ という問題が発生します。

そのような場合は、処理の __進捗状況__ （progress）を表す __プログレスバー__（progress bar）を表示するという工夫が良く行われます。

python には、__for 文__ による繰り返し処理を行う際に __プログレスバーを表示__ してくれる、__tqdm__[^1] というモジュールがあるので、その使い方を紹介します。また、tqdm によって表示されるプログレスバーには、後述するように、for 文による 1 秒当たりの繰り返しの回数が表示されるので、処理速度の計測を行うことができるという利点もあります。

## tqdm のインストールと使い方

tqdm は組み込みモジュールではないので、[以前の記事](https://qiita.com/ysgeso/items/ab2770693c947c108dd0#matplotlib-%E3%81%AE%E3%82%A4%E3%83%B3%E3%82%B9%E3%83%88%E3%83%BC%E3%83%AB) で `matplotlib` をインストールしたのと同様の方法で、Anaconda Navigator などを利用してインストールして下さい。

tqdm モジュールの利用方法は簡単で、下記のプログラムのように、tqdm から __`tqdm` という関数をインポート__ した後で、__for 文の反復可能オブジェクト__ の部分を、反復可能オブジェクトを実引数とした __`tqdm` の関数呼び出しで置き換えるだけ__ です。

* __1 行目__：tqdm モジュールから `tqdm` という関数をインポートする
* __3、4 行目__：for 文の反復可能オブジェクトに `tqdm(range(10000))` 記述して 10000 回の繰り返し処理を行う。この繰り返し処理では pass を記述しているので何も処理は行わない

```python
from tqdm import tqdm

for i in tqdm(range(10000)):
    pass
```

実行結果（実行結果はコンピューターの性能や状況によって変わります）

```
100%|██████████| 10000/10000 [00:00<00:00, 5895844.81it/s]
```

上記のプログラムを実行すると、実行結果のようなプログレスバーが表示されるようになります。表示される数値の意味は、以下の通りです。残りの時間の予測は、これまでの経過時間から計算した予測なので、正確ではありませんが、 __あとどれくらいで処理が終わるかの目安__ になります。回数/秒の右に表示される it/s は iterations/second [^2]の略です。

```
進捗状況(%) |プログレスバー| 繰り返した回数/繰り返す回数 [経過時間<残り時間の予測, 回数/秒]
```

tqdm モジュールの詳細については、下記のリンク先を参照して下さい。

https://tqdm.github.io/

## `ai_match` の改良

下記は、`ai_match` をプログレスバーを表示するように修正したプログラムです。

* __11 行目__：AI 同士の対戦を行う for 文による繰り返し処理の反復可能オブジェクトの部分を `tqdm` を利用するように修正する


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

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

```python
from marubatsu import Marubatsu
from collections import defaultdict

def ai_match(ai, params=[{}, {}], match_num=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 tqdm(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 marubatsu import Marubatsu
from collections import defaultdict

def ai_match(ai, params=[{}, {}], match_num=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):
+   for _ in tqdm(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
元と同じなので省略
```
</details>

上記の修正後に下記のプログラムで `ai_match` で `ai_gt1` VS `ai2s` の対戦を行うと、実行結果のようにプログレスバーが表示されるようになります。プログレスバーの右の 00:31 から、tqdm を記述した for 文の処理に約 31 秒かかり、315.49it/s から、1 秒間に平均すると約 300 回の繰り返し処理が行われたことが確認できます。

```python
from tree import Mbtree
from ai import ai_gt1, ai2s

mbtree = Mbtree.load("dfscore")
ai_match(ai=[ai_gt1, ai2s], params=[{"mbtree":mbtree}, {}])
```

実行結果

```
ai_gt1 VS ai2s
100%|██████████| 10000/10000 [00:31<00:00, 315.49it/s]
count     win    lose    draw
o        9697       0     303
x        7786       0    2214
total   17483       0    2517

ratio     win    lose    draw
o       97.0%    0.0%    3.0%
x       77.9%    0.0%   22.1%
total   87.4%    0.0%   12.6%
```

# ゲーム木を利用した AI の処理の改良

前回の記事で、ゲーム木を利用した強解決の AI を作成しました。__強解決の AI__ は __全ての局面で最善手を着手する__ AI なので、__これ以上強い AI を作成することは不可能__ です。

ただし、前回の記事で作成した __`ai_gt1`__ は、__プログラムの記述__ や、__処理の効率__ の面では __改良の余地がある__ ので、今回の記事ではその改良を行うことにします。どのような改良を行うことができるかについて少し考えてみて下さい。

## ノードの局面の最善手の記録による改良

[前回の記事](https://qiita.com/ysgeso/items/321cf89ef5c49b861650#%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E5%BC%B7%E8%A7%A3%E6%B1%BA%E3%81%AE-ai-%E3%81%AE%E4%BD%9C%E6%88%90)で説明したように、ゲーム木を利用した強解決の AI は下記のアルゴリズムで着手を選択します。

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

下記は上記の処理を行う `ai_gt1` の定義を表すプログラムです。

```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 choice(bestmoves)
```

ゲーム木のノードの最善手を調べるという、上記の __手順 2 の処理__ は __いつ行っても同じ結果__ になりますが、`ai_gt1` ではその処理を 6 ~ 9 行目のプログラムで __`ai_gt1` が呼び出されるたびに行っている__ 点に __無駄があります__。

そこで、上記の手順 2 の処理を以下の方法で行うように改良することにします。

* __手順 2 の処理__ を、ゲーム木のそれぞれの __ノードの評価値を計算した後__ で行う
* 手順 2 で計算したノードの __最善手の一覧__ を、その __ノードの属性に代入して記録__ する
* AI の処理を行う関数の手順 2 では、__ノードの属性に代入された最善手の一覧を利用__ する

### `calc_bestmoves` の定義

ゲーム木の __すべてのノードの最善手を計算__ する Mbtree クラスの __メソッドを定義__ します。そのメソッドは幅優先アルゴリズムと深さ優先アルゴリズムのどちらを使っても実装できますが、本記事では __より簡潔に記述できる再帰呼び出しによる深さ優先アルゴリズム__ で実装することにします。幅優先アルゴリズムで実装したい人は是非チャレンジしてみて下さい。

そこで、Mbtree クラスに下記のようなメソッドを定義する事にします。なお、本記事では幅優先アルゴリズムで同様の処理を行うメソッドは定義しないので、これまでのようにメソッドの名前の末尾にアルゴリズムの種類を表す `_df` は付けないことにします。

__名前__：ノードの最善手の一覧を計算するので、`calc_bestmoves` とする
__処理__：ゲーム木の全てのノードの最善手の一覧を、再帰呼び出しによる深さ優先アルゴリズムで計算し、それぞれのノードの属性に記録する
__入力__：仮引数 `node` に最善手を計算するノードを代入する
__出力__：なし



`calc_bestmoves` はゲーム木の __全てノードの評価値を計算後に実行する__ ので、__ルートノードから__ 順番に __トップダウン__ にその処理を行うことができます。そのため、下記のプログラムのような、[トップダウンな再帰呼び出し](https://qiita.com/ysgeso/items/38f2c8167a14eb99d86c#%E3%83%88%E3%83%83%E3%83%97%E3%83%80%E3%82%A6%E3%83%B3%E3%81%AA%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AB%E3%82%88%E3%82%8B%E5%AE%9F%E8%A3%85-1)による処理を行う関数として定義できます。

* __1 行目__：最善手を計算するノードを代入する仮引数 `node` を記述する
* __2 ~ 5 行目__：ノードの最善手は __トップダウン__ に計算するので、[以前の記事](https://qiita.com/ysgeso/items/38f2c8167a14eb99d86c#%E3%83%9C%E3%83%88%E3%83%A0%E3%82%A2%E3%83%83%E3%83%97%E3%81%A8%E3%83%88%E3%83%83%E3%83%97%E3%83%80%E3%82%A6%E3%83%B3%E3%81%AA%E5%87%A6%E7%90%86%E3%81%AE%E8%A8%98%E8%BF%B0%E5%A0%B4%E6%89%80)で説明したように、9、10 行目の __再帰呼び出しの処理よりも前に記述__ する。なお、2 ~ 5 行目の処理は、`ai_gt1` の 6 ~ 9 行目の処理と全く同じである
* __6 行目__：計算した最善手の一覧のデータをノードの `bestmoves` 属性に代入する

```python
 1  def calc_bestmoves(self, node):
 2      bestmoves = []
 3      for move, childnode in node.children_by_move.items():
 4          if node.score == childnode.score:
 5              bestmoves.append(move)
 6      node.bestmoves = bestmoves
 7   
 8      for childnode in node.children:
 9          self.calc_bestmoves(childnode)
10        
11  Mbtree.calc_bestmoves = calc_bestmoves       
```

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

```python
def calc_bestmoves(self, node):
    bestmoves = []
    for move, childnode in node.children_by_move.items():
        if node.score == childnode.score:
            bestmoves.append(move)
    node.bestmoves = bestmoves
    
    for childnode in node.children:
        self.calc_bestmoves(childnode)
        
Mbtree.calc_bestmoves = calc_bestmoves       
```
</details>

上記を定義後に、下記のプログラムを実行することで、`mbtree` の全てのノードに対して、最善手の一覧を表す `bestmoves` 属性が計算されます。

```python
mbtree.calc_bestmoves(mbtree.root)
```

[以前の記事](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E8%A6%96%E8%A6%9A%E5%8C%96%E3%81%AE%E7%A2%BA%E8%AA%8D)でゲーム開始時の局面ではすべての着手が最善手であることがわかっています。下記のプログラムを実行すると、ルートノードの`bestmoves` 属性に 9 マスすべてが表示されることから、ルートノードの `bestmoves` 属性が正しく計算されていることが確認できます。

```python
print(mbtree.root.bestmoves)
```

実行結果

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

### `ai_gt2` の定義

次に、最善手をノードの `bestmoves` 属性を使って計算する AI を定義する事にします。その関数の名前は、`ai_gt1` を改良する関数なので __`ai_gt2`__ とします。以後もこの方針でゲーム木を利用した AI の処理を行う関数の名前を付けることにします。

`ai_gt2` は、下記のプログラムのように定義できます。あらかじめ各ノードの最善手を計算しておくことで、__プログラムが `ai_gt1` と比べてシンプル__ になります。

* __8 行目__：最善手の一覧は `mb` の局面を表すノードの `bestmoves` 属性に代入されるようになったので、その値と `choice` を使って着手をランダムに選択する

```python
1  from random import choice
2
3  def ai_gt2(mb, mbtree):
4      node = mbtree.root
5      for move in mb.records[1:]:
6          node = node.children_by_move[move]
7
8      return choice(node.bestmoves)
```

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

```python
from random import choice

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

    return choice(node.bestmoves)
```
</details>

<details><summary><strong><code>ai_gt1</code>からの修正箇所</strong></summary>

```diff_python
from random import choice

-def ai_gt1(mb, mbtree):
+def ai_gt2(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)
+   return choice(node.bestmoves)
```
</details>

下記のプログラムで `ai_match` を使って `ai_gt2` VS `ai2s` の対戦を行うと、実行結果のように `ai_gt1` VS `ai2s` とほぼ同じ対戦成績になることがわかります。

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

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

```
ai_gt2 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 304.67it/s]
count     win    lose    draw
o        9673       0     327
x        7711       0    2289
total   17384       0    2616

ratio     win    lose    draw
o       96.7%    0.0%    3.3%
x       77.1%    0.0%   22.9%
total   86.9%    0.0%   13.1%
```

## ノードを探す処理の効率化

下記はゲーム木を利用した強解決の AI のアルゴリズムの再掲です。

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

上記の手順 1 は、下記の `ai_gt2` の 2 ~ 4 行目の処理で行っていますが、この処理も効率化することができます。どのように効率化できるかについて少し考えてみて下さい。

```python
1  def ai_gt2(mb, mbtree):
2      node = mbtree.root
3      for move in mb.records[1:]:
4          node = node.children_by_move[move]
5
6      return choice(node.bestmoves)
```

### 局面とノードの対応表による効率化

考え方は、先程の手順 2 の効率化の手法と同じで、__あらかじめすべての局面に対して__、「__局面__」と「__対応するノード__」の __対応表__ を表すデータを __計算しておく__ という方法です。

上記の 2 ~ 4 行目では、ルートノードから順番に `mb` の棋譜の順番通りに子ノードを辿っていくことでノードを探す処理を行っていますが、そのような対応表をあらかじめ計算しておけば、その表を利用することで __即座に `mb` に対応するノードを計算__ することができます。

:::note
この手法は、[以前の記事](https://qiita.com/ysgeso/items/9303214ec798a920174e#%E3%83%A1%E3%83%A2%E5%8C%96%E3%81%AB%E3%82%88%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E5%8A%B9%E7%8E%87%E5%8C%96)で説明したメモ化に似ていますが、__メモ化__ は __データを計算した際__ にそのデータを __記録して取っておく__ という手法であるのに対し、こちらは __あらかじめすべてのデータを計算__ して取っておく点が異なります。
:::

具体的には、Mbtree クラスに __`nodelist_by_mb`__ 属性を追加し、その属性にそのような __対応表を表す dict を記録__ することができれば、`mb` の局面に対応するノードを探す処理を、下記のプログラムの 2 行目のように簡潔に定義する事ができまるようになります。2 行目の `mb を表すデータ` をどのように記述すれば良いかについて少し考えてみて下さい。

```python
1  def ai_gt3(mb, mbtree):
2      node = mbtree.nodelist_by_mb[mb を表すデータ]
3      return choice(node.bestmoves)
```

<details><summary><strong><code>ai_gt2</code>からの修正箇所</strong></summary>

```diff_python
-def ai_gt2(mb, mbtree):
+def ai_gt3(mb, mbtree):
-   node = mbtree.root
-   for move in mb.records[1:]:
-       node = node.children_by_move[move]
+   node = mbtree.nodelist_by_mb[mb を表すデータ]
    return choice(node.bestmoves)
```
</details>

### 間違った局面を表すデータの記述方法

[以前の記事](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E5%8F%AF%E8%83%BD%E3%81%AA%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%A8%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E5%80%A4)で説明したように、__dict のキー__ には __ハッシュ可能なオブジェクト__ を利用することができ、[以前の記事](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E5%8F%AF%E8%83%BD%E3%81%AA%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%AE%E7%A8%AE%E9%A1%9E)で説明したように、__自分で定義したクラスのインスタンス__ は __ハッシュ可能なオブジェクト__ なので、dict のキーとして利用できます。

そのため、下記のプログラムのように、局面を表す __Marubatsu クラスのインスタンスをキー__ とし、そのキーの値にその局面を表すノードを代入するという方法を考えた人が多いのではないかと思いますが、このプログラムは __正しく動作しません__[^3]。

:::note alert

```python
def ai_gt3(mb, mbtree):
    node = mbtree.nodelist_by_mb[mb]
    return choice(node.bestmoves)
```
:::

### オブジェクトを dict のキーに記述した場合に行われる処理

上記の `ai_gt3` の 2 行目の `mbtree.nodelist_by_mb[mb]` という処理が、意図通りに動作しない理由は、__同じ局面__ を表す Marubatsu クラスのインスタンスを __複数作成できてしまう__ からです。例えば、下記のプログラムでは、`mb` と `mb2` にゲーム開始時の局面を表すデータが代入しますが、__この 2 つのデータは異なるオブジェクト__ です。

```python
mb = Marubatsu()
mb2 = Marubatsu()
```

そのため、下記のプログラムの 1 行目のように、`mb` をキーとし、そのキーの値にゲーム開始時の局面を表す `mbtree` のルートノードを代入した dict を作成した後で、2 行目のように `mb2` をキーとする値を参照しようとすると、実行結果のようにキーが存在しないことを表す KeyError が発生します。

```python
nodelist_by_mb = { mb: mbtree.root }
print(nodelist_by_mb[mb2])
````

実行結果

```
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[10], line 2
      1 nodelist_by_mb = { mb: mbtree.root }
----> 2 print(nodelist_by_mb[mb2])

KeyError: <marubatsu.Marubatsu object at 0x000001A5A4E0D590>
```

このようなことが起きるのは、自分で定義したクラスのインスタンスを dict のキーにした場合は、__[オブジェクトの id](https://qiita.com/ysgeso/items/911fafe3f80a805165d1#%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%AE-id%E8%AD%98%E5%88%A5%E5%AD%90)__ を使って __キーの区別が行われる__ からです。

上記から、Marubatsu クラスのインスタンスは `nodelist_by_mb` の __キーとして利用できない__ ことがわかります。そのため、__別のデータ__ を __局面を表すデータとして利用__ する必要があります。どのようなデータをキーとすれば良いかについて少し考えてみて下さい。

:::note warn
自分で定義したクラスのインスタンスを dict のキーにした場合は、__同じ意味を表すデータであっても__、__異なるインスタンス__ は、__異なるキー__ であると __認識される__。
:::

:::note
このノートは意味がわからない人は読み飛ばしても全く問題ありません。

特殊メソッドである `__eq__` と `__hash__` を定義することで、`nodelist_by_mb[mb2]` がエラーにならず、 `nodelist_by_mb[mb]` と同じ値を参照するようにすることは可能ですが、そのような手法は Marubatsu クラスのインスタンスのような、着手を行うことで内容を変更することができる __ミュータブルなデータのクラスに対して行ってはいけない__ ことになっています。詳細は下記のリンク先を参照して下さい。
:::

https://docs.python.org/ja/3/reference/datamodel.html#object.__hash_%5f


### dict のキーとして利用可能な局面を表すデータ

__局面を表すデータ__ として、__真っ先に思いつく__ のは __ゲーム盤を表す `board` 属性__ のデータではないでしょうか。確かに、〇×ゲームでは[^4] `board` 属性の値が等しければ同じ局面であることは間違いないのですが、`board` 属性の値を使って対応表を作成しようとした場合は、__ゲーム木の複数のノードが対応してしまう__ という問題があります。

わかりづらいと思いますので、具体例を挙げて説明します。ゲーム開始時の局面から (0, 0)、(1, 1)、(2, 2) の順で着手が行われた場合と、(2, 2)、(1, 1)、(0, 0) の順で着手が行われた場合は、__`board` 属性の値は全く同じ__ になりますが、__それぞれの局面を表すノード__ は、ゲーム木の中の __異なるノードに対応__ します。

__〇×ゲーム__ は、その局面に至るまでの棋譜が異なっていても、__ゲーム盤の状況が同じであれば、最善手は同じになる__[^5] ため、__最善手を求めるだけ__ であれば、__`board` 属性の値を使って対応表を作成__ しても __問題はありません__ が、__局面とゲーム木のノードを正しく対応させる必要がある__ 場合は、__`board` 属性の値だけ__ を使って __対応表を作ることはできません__。

局面とゲーム木のノードを正しく対応させるための __局面を表すデータ__ としては、 __棋譜__ を利用することができます。ゲーム木の作成の手順を考えれば、局面の __棋譜が一致__ していれば、__対応するゲーム木のノードが必ず同じになる__ ことは明らかだからです。棋譜のデータは、Marubatsu クラスの __`records`__ 属性に代入されているので、__`records` 属性の値をキー__ とすることで局面とゲーム木のノードの対応表を作成することができます。

ただし、残念ながら、下記のプログラムのようにキーに __`records`__ 属性の値を __そのまま dict のキーにする__ と実行結果のような __エラーが発生__ します。

```python
nodelist_by_mb = {mb.records: mbtree.root}
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[11], line 1
----> 1 nodelist_by_mb = {mb.records: mbtree.root}

TypeError: unhashable type: 'list'
```

エラーメッセージからわかるようにこのエラーの原因は、__`records`__ 属性の値が、__ハッシュ可能なデータ型ではない__（unhashable）__list であるから__ です。

この問題は、__list を__ ハッシュ可能なデータである __tuple に変換する__ ことで解決することができます。list を tuple に変換する方法は簡単で、下記のプログラムの 2 行目のように、__組み込み関数 `tuple` の実引数に list を記述するだけ__ です。実行結果のように `b` には、`a` と __同じ要素を持つ tuple__ が代入されます。

```python
a = [1, 2, 3]
b = tuple(a)
print(a)
print(b)
```

実行結果

```
[1, 2, 3]
(1, 2, 3)
```

なお、組み込み関数 `tuple` は、下記のプログラムのように、その __要素の値は tuple に変換してくれない__ 点に注意して下さい。実行結果のように、全体は tuple に変換されますが、__1 番の要素の list は変換後も list のまま__ です。

```python
a = [1, [2, 3]]
b = tuple(a)
print(a)
print(b)
```

実行結果

```
[1, [2, 3]]
(1, [2, 3])
```

__ハッシュ可能なデータ__ は、その中に __ハッシュ可能ではないデータが存在してはいけない__ ので、tuple の要素に list が存在する場合はハッシュ可能なデータではありません。__list__ を __`tuple` を使って__ ハッシュ可能なデータに __変換する場合__ は __その点に注意__ して下さい。

なお、__`records`__ 属性の要素は、__ハッシュ可能なデータ__ である __`None` と tuple のみから構成__ されるので、`tuple`を利用することでハッシュ可能なデータに変換することができます。

:::note
逆に、組み込み関数 `list` を使って下記のプログラムのように tuple を list に変換することもできます。なお、要素に tuple があった場合にその要素が list に変換されない点は組み込み関数 `tuple` による変換と同様です。

```python
a = (1, (2, 3))
b = list(a)
print(a)
print(b)
```

実行結果

```
(1, (2, 3))
[1, (2, 3)]
```
:::

### `calc_bestmoves` の修正

__`nodelist_by_mb`__ 属性の計算は、ゲーム木を作成する際に行うことができますが、Mbtree クラスにはゲーム木を作成するメソッドが `create_tree_by_bf` と `create_tree_by_df` の __2 種類がある__ ので、__その両方にその処理を記述するのは面倒__ です。

__`nodelist_by_mb`__ 属性は __`calc_bestmoves` の処理の際にも計算できる__ ので、そちらでその処理を行うことにします。下記は、そのように `calc_bestmoves` を修正したプログラムです。

* __2 行目__：棋譜を表す `node.mb.records` 属性を `tuple` を使って変換したデータをキーとするキーの値に `node` を代入する。__`calc_bestmoves`__ は、ゲーム木の __全てのノードに対して呼び出される__ ので、__全てのノードで `nodelist_by_mb` が計算__ される

```python
1  def calc_bestmoves(self, node):
2      self.nodelist_by_mb[tuple(node.mb.records)] = node
元と同じなので省略
3        
4  Mbtree.calc_bestmoves = calc_bestmoves 
```

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

```python
def calc_bestmoves(self, node):
    self.nodelist_by_mb[tuple(node.mb.records)] = node

    bestmoves = []
    for move, childnode in node.children_by_move.items():
        if node.score == childnode.score:
            bestmoves.append(move)
    node.bestmoves = bestmoves
    
    for childnode in node.children:
        self.calc_bestmoves(childnode)
        
Mbtree.calc_bestmoves = calc_bestmoves       
```
</details>

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

```diff_python
def calc_bestmoves(self, node):
+   self.nodelist_by_mb[tuple(node.mb.records)] = node
元と同じなので省略
        
Mbtree.calc_bestmoves = calc_bestmoves       
```
</details>

上記の修正後に、下記のプログラムを実行して `mbtree` の __全てのノードに対する `nodelist_by_mb` を計算__ します。なお、`calc_bestmoves` メソッドを呼び出す前に、`nodelist_by_mb` 属性に空の dict を代入しておく必要がある点に注意して下さい。

```python
mbtree.nodelist_by_mb = {}
mbtree.calc_bestmoves(mbtree.root)
```

次に、`nodelist_by_mb` が正しく計算されているかどうかを確認します。

下記のプログラムは、ゲーム開始時の局面を表す `mb` の `records` 属性を使って、`nodelist_by_mb` からゲーム開始時の局面を表すルートノードを探すことができることを確認するプログラムです。実行結果から、探すことができたことが確認できます。

* __1 行目__：`mb` の `records` 属性を tuple に変換し、`records` に代入する
* __2 行目__：`nodelist_by_mb` 属性から、`records` のキーの値を参照して `root` に代入する
* __3 行目__：`root` と `mbmtree.root` が同じオブジェクトであることを、同一性（同一のオブジェクトであるかどうか）を判定する [is 演算子](https://qiita.com/ysgeso/items/ea147c436e357281f441#is-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E6%B3%A8%E6%84%8F%E7%82%B9)で計算する


```python
records = tuple(mb.records)
root = mbtree.nodelist_by_mb[tuple(records)]
print(root is mbtree.root)
```

### `ai_gt3` の定義と `ai_match` による対戦

`nodelist_by_mb` が計算されていることが確認できたので、`ai_gt3` を下記のプログラムのように定義します。

```python
def ai_gt3(mb, mbtree):
    node = mbtree.nodelist_by_mb[tuple(mb.records)]
    return choice(node.bestmoves)
```

<details><summary><strong><code>ai_gt2</code>からの修正箇所</strong></summary>

```diff_python
-def ai_gt2(mb, mbtree):
+def ai_gt3(mb, mbtree):
-   node = mbtree.root
-   for move in mb.records[1:]:
-       node = node.children_by_move[move]
+   node = mbtree.nodelist_by_mb[tuple(mb.records)]
    return choice(node.bestmoves)
```
</details>

上記を定義した後で `ai_match` で対戦すると、実行結果のような対戦成績が表示されます。対戦成績は `ai_gt1` VS `ai2s` とほぼ同じなので正しく実装できていることが確認できます。

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

実行結果

```
ai_gt3 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 309.37it/s]
count     win    lose    draw
o        9692       0     308
x        7800       0    2200
total   17492       0    2508

ratio     win    lose    draw
o       96.9%    0.0%    3.1%
x       78.0%    0.0%   22.0%
total   87.5%    0.0%   12.5%
```

## さらなる改良

下記の `ai_gt3` をさらに改良することができます。どのように改良できるかについて少し考えてみて下さい。

```python
def ai_gt3(mb, mbtree):
    node = mbtree.nodelist_by_mb[tuple(mb.records)]
    return choice(node.bestmoves)
```

上記のプログラムでは、局面を表すデータからノードを調べ、そのノードの `bestmoves` 属性を計算するという処理を行っていますが、この処理は __局面と最善手の一覧の対応表を作成__ することで __1 回の処理で行う__ ことができるようになります。具体的には、その __対応表をあらかじめ計算__ して Mbtree クラスの __`bestmoves_by_mb`__ という属性に __代入しておけば__、__`ai_gt4`__ を下記のプログラムのように __1 行で記述__ することができます。

```python
def ai_gt4(mb, mbtree):
    return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])
```

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

```python
def ai_gt4(mb, mbtree):
    return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])
```
</details>

<details><summary><strong><code>ai_gt3</code>からの修正箇所</strong></summary>

```diff_python
-def ai_gt3(mb, mbtree):
+def ai_gt4(mb, mbtree):
-   node = mbtree.nodelist_by_mb[tuple(mb.records)]
-   return choice(node.bestmoves)
+   return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])
```
</details>

### `calc_bestmoves` の修正

__`bestmoves_by_mb`__ 属性は、__最善手の一覧を計算した後__ でなければ計算できないので、下記のプログラムのように __`calc_bestmoves` で計算__ する必要があります。

* __8 行目__：`nodelist_by_mb` と `bestmoves_by_mb` で __キーの意味は共通する__ ので、キーとして用いる棋譜を表すデータを __`key`__ という変数に __代入しておく__
* __9 行目__：この処理は元は 2 行目に記述していたが、10 行目の `bestmoves_by_mb` の処理と同様の処理なので、まとめて処理を行うためにここに移動した
* __10 行目__：`best_moves_by_mb` の `key` の値に `bestmoves` を代入して記録する。なお、この処理は、2 ~ 6 行目で `bestmoves` を計算した後で行う必要がある 

```python
 1  def calc_bestmoves(self, node):
 2      bestmoves = []
 3      for move, childnode in node.children_by_move.items():
 4          if node.score == childnode.score:
 5              bestmoves.append(move)
 6      node.bestmoves = bestmoves
 7
 8      key = tuple(node.mb.records)
 9      self.nodelist_by_mb[key] = node
10      self.bestmoves_by_mb[key] = bestmoves
11   
12      for childnode in node.children:
13          self.calc_bestmoves(childnode)
14        
15  Mbtree.calc_bestmoves = calc_bestmoves        
```

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

```python
def calc_bestmoves(self, node):
    bestmoves = []
    for move, childnode in node.children_by_move.items():
        if node.score == childnode.score:
            bestmoves.append(move)
    node.bestmoves = bestmoves

    key = tuple(node.mb.records)
    self.nodelist_by_mb[key] = node
    self.bestmoves_by_mb[key] = bestmoves
   
    for childnode in node.children:
        self.calc_bestmoves(childnode)
        
Mbtree.calc_bestmoves = calc_bestmoves       
```
</details>

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

```diff_python
def calc_bestmoves(self, node):
-   self.nodelist_by_mb[tuple(node.mb.records)] = node
    bestmoves = []
    for move, childnode in node.children_by_move.items():
        if node.score == childnode.score:
            bestmoves.append(move)
    node.bestmoves = bestmoves

+   key = tuple(node.mb.records)
+   self.nodelist_by_mb[key] = node
+   self.bestmoves_by_mb[key] = bestmoves
   
    for childnode in node.children:
        self.calc_bestmoves(childnode)
        
Mbtree.calc_bestmoves = calc_bestmoves        
```
</details>

上記の修正後に、下記のプログラムを実行して `mbtree` の `bestmoves_by_mb` を計算します。なお、`calc_bestmoves` メソッドを呼び出す前に、`bestmoves_by_mb` 属性に空の dict を代入しておく必要がある点に注意して下さい。

```python
mbtree.nodelist_by_mb = {}
mbtree.bestmoves_by_mb = {}
mbtree.calc_bestmoves(mbtree.root)
```

上記の実行後に `ai_match` で対戦すると、実行結果のような対戦成績が表示されます。対戦成績は `ai_gt1` VS `ai2s` とほぼ同じなので正しく実装できていることが確認できます。

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

実行結果

```
ai_gt4 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 307.99it/s]
count     win    lose    draw
o        9714       0     286
x        7704       0    2296
total   17418       0    2582

ratio     win    lose    draw
o       97.1%    0.0%    2.9%
x       77.0%    0.0%   23.0%
total   87.1%    0.0%   12.9%
```

## 最善手の計算に必要なデータの分離

下記の `ai_gt4` の 2 行目をよく見ると、__`ai_gt4` の処理に必要なデータ__ は __`bestmoves_by_mb` 属性だけ__ であり、`mbtree` の他のデータは必要がないことがわかります。

```python
def ai_gt4(mb, mbtree):
    return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])
```

そのため、下記のプログラムのように、__仮引数に `bestmoves_by_mb` のデータを代入__ するように `ai_gt5` を定義する事ができます。

```python
def ai_gt5(mb, bestmoves):
    return choice(bestmoves[tuple(mb.records)])
```

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

```python
def ai_gt5(mb, bestmoves):
    return choice(bestmoves[tuple(mb.records)])
```
</details>

<details><summary><strong><code>ai_gt4</code>からの修正箇所</strong></summary>

```diff_python
-def ai_gt4(mb, mbtree):
+def ai_gt5(mb, bestmoves):
-   return choice(mbtree.bestmoves_by_mb[tuple(mb.records)])
+   return choice(bestmoves[tuple(mb.records)])
```
</details>

上記の定義後に `ai_match` で対戦すると、実行結果のような対戦成績が表示されます。対戦成績は `ai_gt1` VS `ai2s` とほぼ同じなので正しく実装できていることが確認できます。

```python
ai_match(ai=[ai_gt5, ai2s], params=[{"bestmoves":mbtree.bestmoves_by_mb}, {}])
```

実行結果

```
ai_gt5 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 308.59it/s]
count     win    lose    draw
o        9632       0     368
x        7774       0    2226
total   17406       0    2594

ratio     win    lose    draw
o       96.3%    0.0%    3.7%
x       77.7%    0.0%   22.3%
total   87.0%    0.0%   13.0%
```

### データのファイルサイズの比較

このように __`ai_gt5`__ を定義する事の __利点__ は、AI の処理を行う際に必要なデータを保存した際の __ファイルの大きさ__ にあります。

下記のプログラムで、`mbtree` と `mbtree.bestmoves_by_mb` のデータをファイルに保存し、__ファイルサイズを比較__ すると以下の表のようになります。なお、`mbtree` のファイル名は、`ai_gt1` ~ `ai_gt4` に必要なデータがすべて含まれているので aidata.mbtree とし、`mbtree.bestmoves_by_mb` のファイル名は bestmoves.dat としました。

```python
import pickle
import gzip
mbtree.save("aidata")
with gzip.open("bestmoves.dat", "wb") as f:
    pickle.dump(mbtree.bestmoves_by_mb, f)
```

| ファイル名 | データサイズ | 読み込み時間 | 
|:--|--:|--:|
| aidata.mbtree  | 約 21.8 MB  | 16.6 秒 | 
| bestmoves.dat  | 約 2.8 MB  | 0.7 秒 |

__`bestmoves.dat`__ には、__ゲーム木に関するデータが含まれていない__ ので、表のように __ファイルサイズが約 1/8 になる__ という利点があります。そのため、下記のプログラムでファイルからデータを読み込むとそれぞれの処理にかかる時間は表のように __大きな差__ がでます。AI と対戦する前にファイルの読み込みで 15 秒も待たされるのは苦痛なので、この差は大きな利点と言えるでしょう。

```python
mbtree.load("aidata")
```

```python
with gzip.open("bestmoves.dat", "rb") as f:
    bestmoves = pickle.load(f)
```

# Mbtree クラスの `__init__` メソッドの修正

Mtree クラスに新しく `calc_bestmoves` メソッドを追加したので、下記のプログラムのように `__init__` メソッドで `calc_bestmoves` を呼び出すように修正することにします。

* __4 ~ 8 行目__：評価値を計算した後で、`calc_bestmoves` を呼び出すように修正する

```python
1  from tree import Node
2
3  def __init__(self, algo="bf"):
元と同じなので省略
4      self.nodelist_by_mb = {}
5      self.bestmoves_by_mb = {}
6      self.calc_bestmoves(self.root)
7
8  Mbtree.__init__ = __init__
```

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

```python
from tree import Node

def __init__(self, algo="bf"):
    self.algo = algo
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
        self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
    self.nodelist_by_mb = {}
    self.bestmoves_by_mb = {}
    self.calc_bestmoves(self.root)

Mbtree.__init__ = __init__
```
</details>

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

```diff_python
from tree import Node

def __init__(self, algo="bf"):
元と同じなので省略
+   self.nodelist_by_mb = {}
+   self.bestmoves_by_mb = {}
+   self.calc_bestmoves(self.root)

Mbtree.__init__ = __init__
```
</details>

実行結果は省略しますが、上記の修正後に下記のプログラムで Mbtree クラスのインスタンスを作成し、それを使って `ai_gt4` の対戦を行うことで、Mbtree のインスタンスの作成時に `nodelist_by_mb` 属性と `bestmoves_by_mb` 属性が正しく計算されたことが確認できます。

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

# AI 処理時間の差の計測

下記は、`ai_match` で `ai_gt1` ~ `ai_gt5` までが対戦を行った際のプログレスバーの部分を抜粋して並べたものです。この中で __00:31__<00:00 の __前の数字が処理時間__ を表します。処理が効率的になっているにも関わらず、__それぞれの処理時間に差がほとんど変わらない__ 点が気になっている人がいるかもしれませんが、その理由は __`ai_gt1` ~ `ai_gt5` の処理時間__ は、__`ai_match`__ で行われる __他の処理にかかる時間と比べて非常に短い__ からです。

```
ai_gt1 VS ai2s
100%|██████████| 10000/10000 [00:31<00:00, 315.49it/s]
ai_gt2 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 304.67it/s]
ai_gt3 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 309.37it/s]
ai_gt4 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 307.99it/s]
ai_gt5 VS ai2s
100%|██████████| 10000/10000 [00:32<00:00, 308.59it/s]
```

そのため、`ai_gt1` ~ `ai_gt5` の処理時間を調べるためには、__それぞれの関数のみの処理時間__ を `%%timeit` などで __計測する必要があります__。その際に、下記のプログラムのように __1 つの局面で処理時間を測る__ のはあまり __よいやり方ではない__ でしょう。その理由は、__局面によって__ それぞれの AI が行う __処理時間が変わる場合がある__ からです。例えば、`ai_gt1` は `mb` に対応するノードを探す際に __ルートノードから順番に子ノードを辿って探す__ ので、__ルートノード__ の局面と __深さが深いノード__ の局面では、__計算時間に差が生じます__。

```python
%%timeit
ai_gt1(mb, mbtree)
```

そこで、__ランダムな局面に対する処理時間を計測__ することにします。〇×ゲームの __全局面__ のノードは Mbtree クラスの __`nodelist` 属性に代入__ されているので、下記のプログラムのように __`choice`__ を使うことでランダムな局面に対する処理が行われるようになるはずなのですが、実行結果のようなエラーが発生します。このエラーの原因を少し考えてみて下さい。

* __2 行目__：`choice(mbtree.nodelist)` によって、ゲーム木の中からランダムにノードを一つ選択し、その `mb` 属性を最初の引数に記述する
 
```python
%%timeit
ai_gt1(choice(mbtree.nodelist).mb, mbtree)
```

実行結果

```
略
File c:\Users\ys\ai\marubatsu\108\ai.py:1023, in ai_gt1(mb, mbtree)
   1021     if node.score == childnode.score:
   1022         bestmoves.append(move)
-> 1023 return choice(bestmoves)

File c:\Users\ys\Anaconda3\envs\marubatsu\Lib\random.py:373, in Random.choice(self, seq)
    370 # As an accommodation for NumPy, we don't use "if not seq"
    371 # because bool(numpy.array()) raises a ValueError.
    372 if not len(seq):
--> 373     raise IndexError('Cannot choose from an empty sequence')
    374 return seq[self._randbelow(len(seq))]

IndexError: Cannot choose from an empty sequence
```

エラーメッセージは「空（empty）の[シーケンス型](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#%E3%82%B7%E3%83%BC%E3%82%B1%E3%83%B3%E3%82%B9%E5%9E%8B%E3%81%A8%E3%81%AF%E4%BD%95%E3%81%8B)のデータから（from）選択（choose）することはできない（can not）」という意味で、`ai_gt1` の `return choice(bestmoves)` によってエラーが発生していることがわかります。従って、__`bestmoves` に空の list が代入__ された状態で __`choice(bestmoves)` が呼び出された__ ことが推測されます。

:::note
Python のバージョン 3.10 では「IndexError: list index out of range」という別のエラーメッセージが表示されるようです。このように、__Python のバージョンによっては、エラーの表記が異なる場合があるようです__。なお、本記事では Python のバージョン 3.11 でプログラムを実行しています。
:::

実際に __`mbtree.nodelist`__ に記録されたノードの中には __ゲームの決着がついた局面のノードも含まれており__、そのようなノードには __合法手が存在しない__ ので、__`bestmoves` 属性には空の list が代入__ されます。エラーの原因が判明したので、下記のプログラムで、`mbtree.nodelist` から、__ゲームの決着がついていないノード の `mb` 属性を抜き出して `mblist` に代入__ することにします。

* __1 行目__：`mblist` を空の list で初期化する
* __2 行目__：`mbtree.nodelist` の全ての要素に対する繰り返し処理を行う
* __3、4 行目__：ノードの局面がゲーム中の場合に、`mblist` に `node.mb` を追加する

```python
1  mblist = []
2  for node in mbtree.nodelist:
3      if node.mb.status == Marubatsu.PLAYING:
4          mblist.append(node.mb)
```

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

```python
mblist = []
for node in mbtree.nodelist:
    if node.mb.status == Marubatsu.PLAYING:
        mblist.append(node.mb)
```
</details>

上記を実行すると、下記のプログラムでランダムな局面に対して `ai_gt1` が行う処理時間の平均を計測することができるようになります。

```python
%%timeit
ai_gt1(choice(mblist), mbtree)
```

実行結果

```
6.41 µs ± 221 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

続けて `ai_gt2` ~ `ai_gt5` の計測を行います。なお、`ai_gt5` では、先程ファイルからデータを読み込んだ `bestmoves` を実引数に記述しました。

```python
%%timeit
ai_gt2(choice(mblist), mbtree)
```

実行結果

```
5.66 µs ± 104 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

```python
%%timeit
ai_gt3(choice(mblist), mbtree)
```

実行結果

```
3.59 µs ± 54.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

```python
%%timeit
ai_gt4(choice(mblist), mbtree)
```

実行結果

```
2.81 µs ± 27.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

```python
%%timeit
ai_gt5(choice(mblist), bestmoves)
```

実行結果

```
3.18 µs ± 39 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

下記はそれぞれの処理の平均時間をまとめた表です。`ai_gt1` から `ai_gt4` まで、__処理の効率化が行われるたびに、平均時間が減っている__ ことが確認でき、`ai_gt1` と `ai_gt4` では 2 倍以上の差が生じることがわかりました。なお、`ai_gt4` と `ai_gt5` は実質的に同じ処理を行っているので同じ所要時間になるはずなのですが、結果は若干 `ai_gt5` のほうが所要時間がかかるようです。これが誤差なのか、それとも何か理由があるのかはよくわかりません。

| AI | 平均時間 |
|:--|--:|
| `ai_gt1`  | 6.41 μs  |
| `ai_gt2`  | 5.66 μs  |
| `ai_gt3`  | 3.59 μs  |
| `ai_gt4`  | 2.98 μs  |
| `ai_gt5`  | 3.29 μs  |

:::note
__上記の計測__ では、`ai_gt1` などの処理とは __関係のない__、ランダムにノードを選択する __`choice(mblist)` の処理が含まれています__。従って、`ai_gt1` などの処理時間は __厳密には `choice(mblist)` の処理時間を引く__ 必要があります。

下記のプログラムで `choice(mblist)` の処理時間を計測した所、実行結果から処理時間の平均は 599 ns = 約 0.6 μs であることがわかりました。これは、上記の表の計測時間と比べると 1/50 以下であるため、ほとんど気にする必要はないでしょう。

```python
%%timeit
choice(mblist)
```

実行結果

```
599 ns ± 24.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
```
:::

# 今回の記事のまとめ

今回の記事では、for 文の処理に対してプログレスバーを表示する方法を紹介し、その後でゲーム木を利用する AI の処理の効率化を行いました。

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/108/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [tree_new.py](https://github.com/ysgeso/marubatsu/blob/master/108/tree_new.py)  | 今回の記事で更新した tree.py |
| [ai_new.py](https://github.com/ysgeso/marubatsu/blob/master/108/ai_new.py)  | 今回の記事で更新した ai.py |
| [aidata.mbtree](https://github.com/ysgeso/marubatsu/blob/master/108/aidata.mbtree)  | ゲーム木を利用する AI で必要となるデータが計算されたゲーム木のデータを保存するファイル |
| [bestmoves.dat](https://github.com/ysgeso/marubatsu/blob/master/108/bestmoves.dat)  | 局面と最善手の一覧の対応表のデータを保存するファイル |

今回の記事からデータファイルを下記の記事にまとめることにしました。

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

# 次回の記事

https://qiita.com/ysgeso/items/80f19df519a6a856bbf8

[^1]:tqdm の[公式のドキュメント](https://tqdm.github.io/)によると、tqdm はアラビア語では progress、スペイン語の I love you の頭文字という意味を持つそうです
[^2]:iterations は繰り返しの回数を表す単語の複数形です
[^3]:本記事では赤色の背景の警告のノートは、間違ったプログラムが記述されていることを表します
[^4]:点数があるゲームや、将棋の持ち駒のように、ゲーム盤以外のデータが存在するゲームは、それらのデータも含める必要があります
[^5]:将棋の場合は千日手というルールが、以後の場合はコウというルールがあるので、ゲーム盤の状況が全く同じであっても、過去の局面の状況が異なると最善手が同じであるとは限りません