Pythonで〇×ゲームのAIを一から作成する　その98　ゲーム木の生成過程を表示するアニメーションの改良と処理時間の計測

# 目次と前回の記事

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

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

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

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

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

## ルールベースの AI の一覧

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

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

# ゲーム木の生成の過程のアニメーションの改良

今回の記事では、前回の記事で作成した、ゲーム木の生成の過程を表示するアニメーションの改良を行います。どのような改良の余地があるかについて少し考えてみて下さい。

# ゲーム木に追加予定のノードの表示の改良

前回の記事で作成したアニメーションは、以下のような表示を行います。

* アニメーションの[フレーム](https://qiita.com/ysgeso/items/c82c854c529172f74103#play-%E3%82%A6%E3%82%A3%E3%82%B8%E3%82%A7%E3%83%83%E3%83%88%E3%81%AB%E3%82%88%E3%82%8B%E3%82%A2%E3%83%8B%E3%83%A1%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3)を 0 番から数えることにする
* 0 番のフレームには、ルートノードが中心かつ、選択状態になった部分木を描画する
* n 番のフレームには、ゲーム木に n 番目に追加されたノードが中心かつ、選択状態になった部分木を描画する

このアニメーションでは、__そのフレームで追加されたノード__ を、__赤枠の選択されたノードとして表示__ することで、どのようにゲーム木が生成されたかを表現しています。そのため、__選択されたノードの子ノード__ は、今後のフレームで追加される予定である、__まだゲーム木に追加されていないノード__ を表しますが、__そのことがわかりづらい__ という問題があります。

例えば 0 番のフレームには下図のような部分木が描画されます。0 番のフレームのゲーム木は、ルートノード以外のノードがまだ追加されていない、__ルートノードのみのゲーム木__ を表しますが、下図のように、今後のフレームで追加される予定である、__ルートノードの子ノードがそのまま表示__ されているので、それらのノードが __既にゲーム木に追加されているように見えてしまいます__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b888c6e0-0b6d-f8b6-8926-5fa6e5c0d6f8.png" width="100">

そこで、ゲーム木にまだ追加されていない、今後のフレームで __追加される予定のノード__ を __暗く表示__ することで、それらのノードが __まだ追加されていないことが直観的にわかる__ ように修正することにします。どのように修正すれば良いかについて少し考えてみて下さい。

## ゲーム木に追加予定のノードを暗く表示するアルゴリズム

行いたい処理は、部分木に表示されるノードの中で、現在表示されているフレームより後にゲーム木に __追加する予定であるノードを暗く表示する__ というものです。

また、現状のプログラムでは、以下のようなデータが記録されています。

* 部分木に表示されるそれぞれの __ノードとその表示範囲__ が、Mbtree クラスの __[`nodes_by_rect`](https://qiita.com/ysgeso/items/7b687d25a4ab300f5865#draw_node-%E3%81%AE%E4%BF%AE%E6%AD%A3)__ 属性に dict の形式で記録されている
* Mbtree_Anim クラスの Play ウィジェットの __`value`__ 属性に、現在表示されるアニメーションの __フレームの番号が代入__ されている

上記から、下記のアルゴリズムで追加する予定であるノードを暗く表示できます。

* __それぞれのノード__ が、ゲーム木に __何番目に追加されたか__ を計算する
* その __順番と__ Play ウィジェットの __`value` 属性の値を比較する__ ことで、そのノードが __追加する予定のノードであるか__ どうかを判定できる
* 追加する予定のノードを何らかの方法（具体的な方法は後で説明します）で暗く表示する


## ノードがゲーム木に追加された順番を計算するアルゴリズム

まず、__それぞれのノード__ が、ゲーム木に __何番目に追加されたか__ を計算する必要があるので、その方法を少し考えてみて下さい。

### `index` メソッドによる計算

Mbtree クラスの __`nodelist`__ には、ゲーム木の __ノードの一覧が list の形式で代入__ されています。また、その list の __要素の順番__ は、ゲーム木のノードが __追加された順番に対応__ します。

従って、__`nodelist`__ の __n 番のインデックスの要素__ には、ゲーム木に __n 番目に追加されたノードが代入されている__ ので、list の __`index`__ メソッドを使って、ノードがゲーム木に何番目に追加されたかを計算することができます。

例えば、ルートノードは、下記のプログラムで 0 番目（最初から存在する）に追加されたノードであることが確認できます。

```python
from tree import Mbtree

mbtree = Mbtree()
print(mbtree.nodelist.index(mbtree.root))
```

実行結果

```
ゲーム木の生成時の表示は省略
0
```

ゲーム木に最後に追加されたノードは、`nodelist` の最後の要素に代入されています。従って、下記のプログラムから、最後に追加されたノードは、549445 番目にゲーム木に追加されたノードであることが計算できます。

```python
print(mbtree.nodelist.index(mbtree.nodelist[-1]))
```

実行結果

```
549945
```

### `index` メソッドの欠点と、timeit モジュールによる処理時間の計測

__`index`__ メソッドは、list の __先頭の要素から順番__ に、実引数に記述されたデータを __検索する__ という処理を行うので、list の __大きなインデックスの要素__ を実引数に記述すると、__処理に時間がかかる__ という __問題が生じます__。そのことを実際に示します。

プログラムの __処理時間を計測する方法__ の一つに、__timeit モジュール__ を利用するという方法があります。timeit モジュールは、指定したプログラムを __何度も実行__ し、その __処理時間の平均などを計測__ する処理を行いますが、その際に、何回プログラムを実行するかなどの設定を行う必要がある点が少し面倒です。ただし、__JupyterLab__ には、そのような __設定を自動的に行ってくれる__、__`%%timeit` という[マジックコマンド](https://qiita.com/ysgeso/items/1920c68f5a1e8a998796#ipympl-%E3%81%AE%E5%88%A9%E7%94%A8%E6%96%B9%E6%B3%95)__ が用意されているので、それを使えば簡単にプログラムの処理時間を計測することができます。

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

https://docs.python.org/ja/3/library/timeit.html#module-timeit

具体的には、__セルの先頭に `%%timeit` というマジックコマンドを記述__ することで、セルの中に記述したプログラムを実行した際の __処理時間の平均などを計測__ することができます。

下記は、先程の、ルートノードが追加された順番を計算するプログラムの処理時間を `%%timeit` を使って計測するプログラムです。

```python
%%timeit
mbtree.nodelist.index(mbtree.root)
```

実行結果（表示される内容は、コンピュータの性能によって変わります）

```
45.8 ns ± 0.264 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
```

実行結果は以下のような意味を表し、`mbtree.nodelist.index(mbtree.root)` が平均すると 45.8 ナノ秒（約 1 億分の 4 秒）というかなり短い時間で処理が行われることがわかります。

* セルの中のプログラムを 1000 万回（10,000,000）回繰り返す（loop）という処理が、7 回行われた。__これらの回数は、自動的に適切な値が設定__ される
* セルの中のプログラムの処理時間の __平均__（mean）は __45.8 ns（ナノ秒）__ である
* セルの中のプログラムの処理時間の __標準偏差（std[^1]) は 0.264 ns__ である

表示される時間の単位は以下のようになっています。

| 表記 | 単位 | 意味 |
|:--|:--|:--|
| s  |   | 秒 |
| ms  | ミリ（mili）  | 1/千 秒 |
| μs[^2] | マイクロ（micro）| 1/百万 秒 |
| ns | ナノ（nano）| 1/十億万 秒 |

__標準偏差__ は、統計学で使われる、計測された処理時間の __ばらつきを表す量__ で、上記の実行結果のように、__標準偏差__ が __平均と比べて小さい場合__ は __ほとんどの処理__ が、__平均値とほぼ同じ時間で行われた__ ことを意味します。

従って、__標準偏差の値が平均値よりもかなり小さい場合__ は、平均値だけを注目すれば良いでしょう。本記事でもそのような場合は、標準偏差については特に言及せずに、__平均値だけを注目__ することにします。

:::note
上記の結果の場合は、__かなり大雑把__ に言えば[^3]、__行われた処理の 約 70 %__ が __45.8 ns ± 0.264 ns の範囲におさまっていた__ ということを意味します。
:::

下記は、先程の、ゲーム木に最後に追加されたノードの順番を計算するプログラムの処理時間を `%%timeit` を使って計測するプログラムです。実行結果から __平均すると__ 30.5 ms = __約 0.03 秒__ の時間がかかることがわかります。

```python
%%timeit
mbtree.nodelist.index(mbtree.nodelist[-1])
```

実行結果

```
30.5 ms ± 752 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

:::note
上記では、一見すると平均値の 30.5 よりも標準偏差の 752 の方が多く見えるかもしれませんが、__単位を考慮に入れる__ と、標準偏差は平均値の __約 50 分の 1__ です。
:::

:::note
実行結果からわかるように、処理が繰り返し行われる回数は、処理時間の長さによって自動的に調整されます。先程は処理時間が非常に短かったので、7 * 1000 万 = 7000 万回も処理が行われましたが、上記では 7 * 10 = 70 回しか行われません。
:::

下記は 2 つの処理時間の平均です。なお、1 ns = 1000 ms = 100 万 ms です。

| 処理 | 平均 |
|:--|--:|
| `mbtree.nodelist.index(mbtree.root)`  | 45.8 ns = 4580 万 ms |
| `mbtree.nodelist.index(mbtree.nodelist[-1])`  |  30.5 ms |

上記から、__処理時間の平均が約 150 万倍も異なる__ ことがわかります。最後のノードは、`nodelist` の中の 549945 = 約 50 万番目の要素に代入されているので、`index` が `nodelist` の __先頭の要素から順番に検索する__ ことを考えると、この __処理時間の違いは妥当__ でしょう。

:::note
__`print` が記述されたプログラム__ を `%%timeit` で計測すると、`%%timeit` が繰り返しプログラムを実行した数だけ、__`print` によるメッセージが大量に表示__ されてしまいます。そのため、 %%timeit で計測するプログラムには、__`print` の処理を含めないようにしたほうが良い__ でしょう。

上記の計測で、`print` で `index` の結果を表示しなかったのはそのためです。
:::

### ノードを挿入した順番の記録

上記のように、__要素の数が非常に多い list__ に対して __`index` メソッドを実行すると処理に時間がかかる可能性が高くなる__ ので望ましくありません。そこで、ゲーム木に __ノードを追加する際__ に、追加したノードの __属性__ に、ゲーム木に __追加された順番を代入する__ ことにします。そのようにすれば、ノードの属性を見るだけでそのノードが何番目にゲーム木に追加されたかがわかるようになります。

ノードの属性の名前としては、様々なものが考えられますが、ゲーム木にノードが追加された順番を表す数値は、__すべてのノードで異なる数値になる__ ため、__[識別子](https://qiita.com/ysgeso/items/9efd60c7a28381e6cbf7#%E5%8F%82%E7%85%A7%E3%81%AE%E6%84%8F%E5%91%B3)としての役割を持つ__ こともできます。また、実際に良く使われる識別子は 0（または 1）から順番に整数を割り当てることが多いので、本記事では __識別子__ を表す identifier の略である __`id`__ という名前の属性に、ゲーム木に追加された順番を代入することにします。

この、`id` 属性を計算する処理は、[以前の記事](https://qiita.com/ysgeso/items/ad5e7ddb071653fd2ac5#%E5%80%A4%E3%82%92%E5%A4%89%E6%9B%B4%E3%81%99%E3%82%8B%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE%E5%B1%9E%E6%80%A7%E3%81%AE%E5%88%A9%E7%94%A8%E4%BE%8B)で説明した、「値を変更するクラスの属性の利用例」と同じ方法で、__[クラス属性](https://qiita.com/ysgeso/items/ad5e7ddb071653fd2ac5#%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE%E5%B1%9E%E6%80%A7)を使って行う__ ことができます。

まず、Node クラスを下記のように修正します。

* __8 行目__：ノードを作成した回数を表すクラス属性 `count` を `0` で初期化する
* __11 行目__：インスタンスを作成した際に呼び出される `__init__` メソッドの中で、インスタンスの `id` 属性に、クラス属性 `count` を代入する
* __12 行目__：クラス属性 `count` の値に 1 を足す

```python
 1  from copy import deepcopy
 2  from marubatsu import Marubatsu_GUI
 3  import matplotlib.pyplot as plt
 4  from tree import Rect
 5
 6  class Node:
 7      # ノードを作成した回数を表すクラス属性
 8      count = 0
 9    
10      def __init__(self, mb, parent=None, depth=0):
11          self.id = Node.count
12          Node.count += 1
13          self.mb = mb
14          self.parent = parent
15          self.depth = depth
16          self.children = []
17          self.children_by_move = {}        
元と同じなので省略
```

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

```python
from copy import deepcopy
from marubatsu import Marubatsu_GUI
import matplotlib.pyplot as plt
from tree import Rect

class Node:
    # ノードを作成した回数を表すクラス属性
    count = 0
    
    def __init__(self, mb, parent=None, depth=0):
        self.id = Node.count
        Node.count += 1
        self.mb = mb
        self.parent = parent
        self.depth = depth
        self.children = []
        self.children_by_move = {}        
        
    def insert(self, node):
        self.children.append(node)
        self.children_by_move[node.mb.last_move] = node
        
    def calc_children(self):
        self.children = []
        for x, y in self.mb.calc_legal_moves():
            childmb = deepcopy(self.mb)
            childmb.move(x, y)
            self.insert(Node(childmb, parent=self, depth=self.depth + 1))
        
    def calc_height(self):
        if len(self.children) == 0:
            self.height = 4
        else:
            self.height = 0
            for childnode in self.children:
                self.height += childnode.height

    def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
        width = 8
        if ax is None:
            height = len(self.children) * 4
            fig, ax = plt.subplots(figsize=(width * size, height * size))
            ax.set_xlim(0, width)
            ax.set_ylim(0, height)   
            ax.invert_yaxis()
            ax.axis("off")
            for childnode in self.children:
                childnode.height = 4
            self.height = height
                
        # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
        y = dy + (self.height - 3) / 2
        Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, emphasize=emphasize, lw=lw, dx=dx, dy=y)
        rect = Rect(dx, y, 3, 3)
        # 子ノードが存在する場合に、エッジの線と子ノードを描画する
        if len(self.children) > 0:
            if maxdepth != self.depth:   
                plt.plot([dx + 3.5, dx + 4], [y + 1.5, y + 1.5], c="k", lw=lw)
                prevy = None
                for childnode in self.children:
                    childnodey = dy + (childnode.height - 3) / 2
                    if maxdepth is None:
                        Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True, dx=dx+5, dy=childnodey, lw=lw)
                    edgey = childnodey + 1.5
                    plt.plot([dx + 4 , dx + 4.5], [edgey, edgey], c="k", lw=lw)
                    if prevy is not None:
                        plt.plot([dx + 4 , dx + 4], [prevy, edgey], c="k", lw=lw)
                    prevy = edgey
                    dy += childnode.height
            else:
                plt.plot([dx + 3.5, dx + 4.5], [y + 1.5, y + 1.5], c="k", lw=lw)
                
        return rect
```
</details>

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

```diff_python
from copy import deepcopy
from marubatsu import Marubatsu_GUI
import matplotlib.pyplot as plt
from tree import Rect

class Node:
    # ノードを作成した回数を表すクラス属性
+   count = 0
    
    def __init__(self, mb, parent=None, depth=0):
+       self.id = Node.count
+       Node.count += 1
        self.mb = mb
        self.parent = parent
        self.depth = depth
        self.children = []
        self.children_by_move = {}        
元と同じなので省略
```
</details>

次に、Mbtree クラスの `__init__` メソッドを下記のように修正します。この修正を行わないと、複数の Mbtree クラスのインスタンスを作成した際に、Node クラスの __`count` 属性の値__ が `0` ではなく、__その前に作成した Mbtree クラスのノードの数になってしまう__ からです。

* __5 行目__：Node クラスの `count` 属性の値を `0` で初期化する

```python
1  from marubatsu import Marubatsu
2  from tree import Mbtree
3
4  def __init__(self):
5      Node.count = 0
6      self.root = Node(Marubatsu())
7      self.create_tree_by_bf()
8    
9  Mbtree.__init__ = __init__
```

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

```python
from marubatsu import Marubatsu
from tree import Mbtree

def __init__(self):
    Node.count = 0
    self.root = Node(Marubatsu())
    self.create_tree_by_bf()
    
Mbtree.__init__ = __init__
```
</details>

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

```diff_python
from marubatsu import Marubatsu
from tree import Mbtree

def __init__(self):
+   Node.count = 0
    self.root = Node(Marubatsu())
    self.create_tree_by_bf()
    
Mbtree.__init__ = __init__
```
</details>

上記の修正後に下記のプログラムで、Mbtree クラスのインスタンスを作成し直した後で、ルートノードと、最後に追加されたノードの `id` 属性を表示すると、実行結果のようにそれぞれのノードがゲーム木に追加された順番が正しく表示されます。

```python
mbtree = Mbtree()
print(mbtree.root.id)
print(mbtree.nodelist[-1].id)
```

実行結果

```
ゲーム木の生成時の表示は省略
0
549945
```

また、下記のプログラムで `mbtree.nodelist[-1].id` の処理時間を計測すると、実行結果の平均 42.9 ns のように、非常に短い時間で計算できることが確認できました。

```python
%%timeit
mbtree.nodelist[-1].id
```

実行結果

```
42.9 ns ± 0.237 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
```

## ノードを暗く表示する方法

ノードがゲーム木に追加された順番がわかるようになったので、次は現在表示されているフレームより後にゲーム木に追加された __ノードを暗く表示する__ という処理を実装します。ノードを暗く表示する方法について少し考えてみて下さい。

### 背景色を変える方法とその問題点

これまでに紹介した方法を利用する場合は、__ゲーム盤の背景色を灰色で表示する__ という方法が考えられますが、その方法では __決着がついた局面のゲーム盤の背景色までもが灰色で表示される__ ようになってしまうため、__決着がついた局面であるかどうかがわからなくなってしまう__ という問題が生じます。

背景色を変える方法でこの問題を解決するためには、決着がついていない局面と 3 種類ある決着がついた局面の __4 種類の暗い色の背景色を考える必要__ がありますが、それは面倒です。

### 半透明の黒い図形を重ねる方法

別の方法として、ゲーム盤の画像の上に、__半透明の黒い図形を重ねて表示する__ という方法があり、この方法であれば、__背景色を新しく考える必要はありません__。

ipywidgets の Rectangle などの __Artist を作成する関数__ には、__塗りつぶしの透明度__ を表す __仮引数 `alpha`__[^4] があります。`alpha` には __0 ~ 1 の範囲__ の数値を代入し、__0 が完全な透明__、__1 が完全に透明でない__ ことを表します。

下記は、左下に赤い正方形を、右上に __透明度が 0.5 の半透明な黒い正方形__ を、__一部が重なるように表示__ するプログラムです。実行結果のように、赤い正方形の上に半透明な黒い正方形が表示され、__重なった部分が暗く表示される__ ようになります。

```python
import matplotlib.patches as patches

fig, ax = plt.subplots(figsize=(3, 3))
rect1 = patches.Rectangle(xy=(0, 0), width=0.75, height=0.75, fc="red")
rect2 = patches.Rectangle(xy=(0.25, 0.25), width=0.75, height=0.75, fc="black", alpha=0.5)
ax.add_artist(rect1)
ax.add_artist(rect2)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6cacc3d6-9d22-6708-eaa2-dbf9007bcabc.png" width="200">

:::note
透明度を表す `alpha` に 0.5 よりも大きな（1 以下の）数値を代入すると、表示される黒い正方形の色が濃くなります。興味がある方は試してみて下さい。
:::

### ノードを暗く表示する処理の実装

[以前の記事](https://qiita.com/ysgeso/items/17b0438676f4a41a906c#draw_board-%E3%81%AE%E4%BF%AE%E6%AD%A3)では、ノードに赤枠を表示して強調する処理を実装する際に、ゲーム盤を表示する処理を行う __`draw_board` を修正__ しました。同様の方法で、ゲーム盤を暗く表示することができるように `draw_board` を修正するという方法が考えられます。

ただし、そのような方法で `draw_board` を修正するということを続けていくと、__`draw_board` の定義が複雑になる__[^5] という問題が発生します。そこで、今回の記事では `draw_board` ではなく、Mbtree_Anim の __`update_gui` メソッド内で、その処理を行う__ ことにします。

具体的には下記のように `update_gui` を修正します。

* `draw_subtree` で部分木を描画する
* Mbtree クラスの `nodes_by_rect` の中で、現在表示されているフレームより後にゲーム木に追加されたノードの表示範囲に、半透明の黒色の正方形を重ねて描画する

下記は、そのように `update_gui` を修正したプログラムです。

* __5 行目__：`nodes_by_rect` の全てのキーとキーの値に対する繰り返し処理を行う
* __6 行目__：ノードが追加された順番を表す `node.id` が、アニメーションのフレームの番号を表す `self.play.value` よりも大きいかどうかを判定する
* __7、8 行目__：大きい場合は、ノードの表示範囲に半透明の黒い正方形を重ねて描画する

```python
 1  from tree import Mbtree_Anim
 2
 3  def update_gui(self):
元と同じなので省略    
 4      self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
 5      for rect, node in self.mbtree.nodes_by_rect.items():
 6          if node.id > self.play.value:
 7              self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
 8                                              height=rect.height, fc="black", alpha=0.5))
 9
10  Mbtree_Anim.update_gui = update_gui
```

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

```python
from tree import Mbtree_Anim

def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(0, self.height)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    self.selectednode = self.mbtree.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.selectednode.depth <= 4:
        maxdepth = self.selectednode.depth + 1
    elif self.selectednode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
    for rect, node in self.mbtree.nodes_by_rect.items():
        if node.id > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
                                                 height=rect.height, fc="black", alpha=0.5))

Mbtree_Anim.update_gui = update_gui
```
</details>

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

```diff_python
from tree import Mbtree_Anim

def update_gui(self):
元と同じなので省略    
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
+   for rect, node in self.mbtree.nodes_by_rect.items():
+       if node.id > self.play.value:
+           self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
+                                                height=rect.height, fc="black", alpha=0.5))

Mbtree_Anim.update_gui = update_gui
```
</details>

上記の修正後に、下記のプログラムを実行して三角形のボタンをクリックすると、実行結果の左図のように、表示されたフレーム以降に追加される予定のノードが暗く表示されるようになります。修正前の右図と比較して、そのフレームでゲーム木にまだ追加されていないノードが明確になったことを確認して下さい。

```python
mbtree_anim = Mbtree_Anim(mbtree)
```

実行結果（右図は 0 ~ 19 フレームまでのアニメーションの繰り返しです。なお、左図と右図は連動していないので、表示されるフレームがずれる場合があります）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c703bb0b-73df-b44b-5ab8-d326fc5679e8.gif" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3c28e4bc-c113-084b-fbfc-35b80a81b221.gif" width="300">

# 中心となるノードの改良

上記のアニメーションを見て、何かがわかりづらいと思った人はいないでしょうか？そう思った方は、その理由について少し考えてみて下さい。

## わかりづらさの原因の検証

下図は、アニメーションの中の 17 番と 18 番のフレームを並べたものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/45af83ef-1fea-682d-280c-21ea28c9e1f0.png" width="150">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/06fbba5e-d50d-ab46-45e3-b485edfbc861.png" width="150">

17 番のフレームは <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a502dd96-b3d3-4b67-746f-d29cd1377eae.png" width="30"> の最後の子ノードである <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/61d906cd-edec-004a-b6e2-454eef1c16aa.png" width="30"> が選択された部分木です。次の兄弟ノードが存在しないので 18 番のフレームは <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a502dd96-b3d3-4b67-746f-d29cd1377eae.png" width="30"> の次の兄弟ノードの <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/af883417-4ab2-0797-a9a3-b509b06049c8.png" width="30"> の最初の子ノードである <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dfc764d5-957d-ffbe-0bdf-d81503a6daaa.png" width="30"> が選択された部分木です。

上図のように、静止画をじっくり見比べた場合はそのことを理解できるのではないかと思いますが、アニメーションでは上の __2 つの画像が短い間に切り替わる__ ので、そのことをアニメーションを見ながら __理解することは困難でしょう__。

また、選択されたノードの __親ノード__ である <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a502dd96-b3d3-4b67-746f-d29cd1377eae.png" width="30"> と <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/af883417-4ab2-0797-a9a3-b509b06049c8.png" width="30"> は、__2 つのフレームで全く同じ場所に表示__ されますが、アニメーションでは表示が短い間に切り替わるので、17 番と 18 番のフレームで __親ノードが変化したことを実感するのは困難でしょう__。

この問題を解決する方法を少し考えてみて下さい。

## 中心となるノードの変更

一つの方法として、部分木の __中心となるノード__ を、__選択されたノードの親ノードに修正__ するという方法が考えられます。そのようにすることで、選択されたノードの __親ノードの兄弟ノード__ が部分木に __表示されるようになる__ ので、アニメーションで選択されたノードの __親ノードが変化したことが実感できる__ ようになります。おそらく言葉の説明だけではわかりづらいと思いますので、この後の修正後と修正前の処理を比較してみて下さい。



__中心となるノードの深さを一つ減らした場合__ は、部分木に表示するノードの数が多くなりすぎないようにするために、__部分木に表示するノードの深さも同時に減らす__ 必要が生じますが、下記の理由から減らしても問題は発生しません。

下図の青枠の中にある、選択されたノードの __子ノード__ は、__すべて__ が今後のフレームで追加される予定の __暗く表示されるノード__ なので、表示しなくても大きな問題は発生しません。そのため、中心となるノードの深さにあわせて、部分木に表示する __ノードの深さを__ 一つ減らして、__選択されたノードの深さと同じ__ にしても　__問題は発生しません__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6895e22d-5832-dd7c-3198-c455d7c21a62.png" width="200">

下記は、そのように `update_gui` を修正したプログラムです。

* __4、5 行目__：中心となるノードを、親ノードに変更する。ただし、__ルートノードには親ノードは存在しない__ ので __深さが 0 以上の場合のみ行う__ 必要がある点に注意すること
* __6 ~ 8 行目__：元のプログラムは、`selectednode` と `centernode` が同じだったので、`selectednode` を使って部分木の深さを計算していたのを、`centernode` を使って部分木の深さを計算するように修正する

```python
 1  def update_gui(self):
元と同じなので省略
 2      self.selectednode = self.mbtree.nodelist[self.play.value]
 3      self.centernode = self.selectednode
 4      if self.centernode.depth > 0:
 5          self.centernode = self.centernode.parent
 6      if self.centernode.depth <= 4:
 7          maxdepth = self.centernode.depth + 1
 8      elif self.centernode.depth == 5:
 9          maxdepth = 7
10      else:
11          maxdepth = 9
元と同じなので省略
12
13  Mbtree_Anim.update_gui = update_gui
```

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

```python
def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(0, self.height)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    self.selectednode = self.mbtree.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.centernode.depth > 0:
        self.centernode = self.centernode.parent
    if self.centernode.depth <= 4:
        maxdepth = self.centernode.depth + 1
    elif self.centernode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
    for rect, node in self.mbtree.nodes_by_rect.items():
        if node.id > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))

Mbtree_Anim.update_gui = update_gui
```
</details>

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

```diff_python
def update_gui(self):
元と同じなので省略
    self.selectednode = self.mbtree.nodelist[self.play.value]
    self.centernode = self.selectednode
+   if self.centernode.depth > 0:
+       self.centernode = self.centernode.parent
-   if self.selectednode.depth <= 4:
+   if self.centernode.depth <= 4:
-       maxdepth = self.selectednode.depth + 1
+       maxdepth = self.centernode.depth + 1
-   elif self.selectednode.depth == 5:
+   elif self.centernode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
元と同じなので省略

Mbtree_Anim.update_gui = update_gui
```
</details>

上記の修正後に、下記のプログラムを実行して三角形のボタンをクリックすると、実行結果の左図のように、中心となるノードが選択されたノードの親ノードになります。修正前の右図と比較して、わかりやすく表示されるようになったことを確認して下さい。

```python
mbtree_anim = Mbtree_Anim(mbtree)
```

実行結果（右図は 0 ~ 19 フレームまでのアニメーションの繰り返しです。なお、左図と右図は連動していないので、表示されるフレームがずれる場合があります）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/184d6603-d0d3-77d8-a423-18d887bee636.gif" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c703bb0b-73df-b44b-5ab8-d326fc5679e8.gif" width="300">

下図は、アニメーションの中の 17 番と 18 番のフレームを並べたものです。修正前と比べて、以下のような点がわかりやすくなっています。

* 表示する必要がない、選択されたノードの __子ノードが表示されなくなった__
* 親ノードが中心となったため、__親ノードの兄弟ノードが表示される__ ようになった
* 親ノードが変化した際に、__親ノードが表示される位置が異なる__ ようになったので、__親ノードの変化がわかりやすくなった__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b19aee2b-1f0b-f568-1520-887564db589c.png" width="150">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/076421e7-8b65-7099-8192-184f560b95da.png" width="150">

## 深いノードの表示の改良

上記の修正を行っても、まだ改良する余地は残っています。それは、例えば __深さが 9 のノードが追加__ されるフレームのアニメーションを見ることで確認できます。

下図は、深さが 9 のノードが選択されたフレームとなる、500000 ~ 500019 フレームのアニメーションです。__深さ 8__ のノードが __中心となるノードになっている__ ため、表示される __ノードの数が少なく__、__変化がわかりづらい__ アニメーションになっています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/98b9eac0-27e2-19a8-79d6-0ae155849831.gif" width="300">

この問題を解決するためには、[前回の記事](https://qiita.com/ysgeso/items/c82c854c529172f74103#%E5%95%8F%E9%A1%8C%E3%81%AE%E4%BF%AE%E6%AD%A3%E6%96%B9%E6%B3%95)と同様に、__中心となるノードがの深さが 6 以下__ の場合は、その親ノードを辿った、__深さが 6 の親ノードを中心とする部分木を描画する__ という方法が考えられます。

下記は、そのように `update_gui` を修正したプログラムです。

* __5、6 行目__：深さが 6 になるまで `centernode` の親ノードを辿るようにする

```python
1  def update_gui(self):
元と同じなので省略
2      self.centernode = self.selectednode
3      if self.centernode.depth > 0:
4          self.centernode = self.centernode.parent
5      while self.centernode.depth > 6:
6          self.centernode = self.centernode.parent
元と同じなので省略
7
8  Mbtree_Anim.update_gui = update_gui
```

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

```python
def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(0, self.height)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    self.selectednode = self.mbtree.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.centernode.depth > 0:
        self.centernode = self.centernode.parent
    while self.centernode.depth > 6:
        self.centernode = self.centernode.parent
    if self.centernode.depth <= 4:
        maxdepth = self.centernode.depth + 1
    elif self.centernode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
    for rect, node in self.mbtree.nodes_by_rect.items():
        if node.id > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))

Mbtree_Anim.update_gui = update_gui
```
</details>

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

```diff_python
def update_gui(self):
元と同じなので省略
    self.centernode = self.selectednode
    if self.centernode.depth > 0:
        self.centernode = self.centernode.parent
+   while self.centernode.depth > 6:
+       self.centernode = self.centernode.parent
元と同じなので省略

Mbtree_Anim.update_gui = update_gui
```
</details>

上記の修正後に、下記のプログラムを実行して IntSlider の数値の部分をクリックして 500000 を入力した後で三角形のボタンをクリックすると、実行結果のような、中心となるノードが 6 になった部分木のアニメーションが表示されるようになります。

```python
mbtree_anim = Mbtree_Anim(mbtree)
```

実行結果（右図は 500000 ~ 500019 フレームまでのアニメーションの繰り返しです）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/50b3602c-976c-3292-7486-1f72578c0837.gif" width="300">

興味がある方は、他の様々なフレームでアニメーションを行ってみて下さい。

# アニメーションの速度の調整

現状では、Play ウィジェットの __[`interval` 属性](https://qiita.com/ysgeso/items/c82c854c529172f74103#play-%E3%82%A6%E3%82%A3%E3%82%B8%E3%82%A7%E3%83%83%E3%83%88%E3%81%AE%E5%B1%9E%E6%80%A7)__ に __`500` を代入__ したので、1 秒間に 1000 / 200 = 2 回フレームを表示するという、__2 fps__ でアニメーションが行われますが、アニメーションの __速度を調整できるようになると便利__ でしょう。

そこで、この __`interval` 属性を変更__ するための __IntSlider をもう一つ用意__ し、__[`jslink`](https://qiita.com/ysgeso/items/c82c854c529172f74103#play-%E3%82%A6%E3%82%A3%E3%82%B8%E3%82%A7%E3%83%83%E3%83%88%E3%81%A8-intslider-%E3%82%A6%E3%82%A3%E3%82%B8%E3%82%A7%E3%83%83%E3%83%88%E3%81%AE%E3%83%AA%E3%83%B3%E3%82%AF) を使って連動__ することで、アニメーションの __速度を調整できるようにする__ ことにします。

## `create_widgets` の修正

まず、Mbtree_Anim クラスの `create_widgets` メソッドを下記のように修正します。

* __5 行目__：IntSlider が 2 つに増えたので、フレームの番号を表す IntSlider を代入する属性の名前を `frame_slider` に修正した
* __6 行目__：アニメーションの表示の間隔を表す IntSlider を、初期値を 500、最小値を 1、最大値を 2000、左に interval という文字列を表示するように設定して作成し、`interval_slider` 属性に代入する。最小値と最大値を変更したい人は自由に変更すること
* __8 行目__：Play ウィジェットの `interval` 属性と、`interval_slider` の `value` 属性をリンクして、連動するようにする

```python
 1  import ipywidgets as widgets
 2
 3   def create_widgets(self):
 4       self.play = widgets.Play(max=self.mbtree.nodenum - 1, interval=500)
 5       self.frame_slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
 6       self.interval_slider = widgets.IntSlider(value=500, min=1, max=2000, description="interval")
 7       widgets.jslink((self.play, "value"), (self.frame_slider, "value"))    
 8       widgets.jslink((self.play, "interval"), (self.interval_slider, "value"))
元と同じなので省略
 9    
10   Mbtree_Anim.create_widgets = create_widgets
```

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

```python
import ipywidgets as widgets

def create_widgets(self):
    self.play = widgets.Play(max=self.mbtree.nodenum - 1, interval=500)
    self.frame_slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
    self.interval_slider = widgets.IntSlider(value=500, min=1, max=2000, description="interval")
    widgets.jslink((self.play, "value"), (self.frame_slider, "value"))    
    widgets.jslink((self.play, "interval"), (self.interval_slider, "value"))

    with plt.ioff():
        self.fig = plt.figure(figsize=[self.width * self.size,
                                        self.height * self.size])
        self.ax = self.fig.add_axes([0, 0, 1, 1])
    self.fig.canvas.toolbar_visible = False
    self.fig.canvas.header_visible = False
    self.fig.canvas.footer_visible = False
    self.fig.canvas.resizable = False     
    
Mbtree_Anim.create_widgets = create_widgets
```
</details>

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

```diff_python
import ipywidgets as widgets

def create_widgets(self):
    self.play = widgets.Play(max=self.mbtree.nodenum - 1, interval=500)
-   self.slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
+   self.frame_slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
+   self.interval_slider = widgets.IntSlider(value=500, min=1, max=2000, description="interval")
-   widgets.jslink((self.play, "value"), (self.slider, "value"))    
+   widgets.jslink((self.play, "value"), (self.frame_slider, "value"))    
+   widgets.jslink((self.play, "interval"), (self.interval_slider, "value"))
元と同じなので省略
    
Mbtree_Anim.create_widgets = create_widgets
```
</details>

## `display_widgets` の修正

次に、`display_widgets` メソッドを下記のプログラムように修正します。

* __2 行目__：`interval_slider` を `frame_slider` の右に並べて配置するようにする

```python
1  def display_widgets(self):
2      hbox = widgets.HBox([self.play, self.frame_slider, self.interval_slider])
3      display(widgets.VBox([hbox, self.fig.canvas]))
4      
5  Mbtree_Anim.display_widgets = display_widgets
```

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

```python
def display_widgets(self):
    hbox = widgets.HBox([self.play, self.frame_slider, self.interval_slider])
    display(widgets.VBox([hbox, self.fig.canvas]))
    
Mbtree_Anim.display_widgets = display_widgets
```
</details>

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

```diff_python
def display_widgets(self):
    hbox = widgets.HBox([self.play, self.frame_slider, self.interval_slider])
    display(widgets.VBox([hbox, self.fig.canvas]))
    
Mbtree_Anim.display_widgets = display_widgets
```
</details>

## 動作の確認

上記の修正後に、下記のプログラムを実行すると、実行結果のようにアニメーションの表示間隔を調整する IntSlider が表示されるようになります。実際に三角形のボタンをクリックした後で IntSlider を操作して __アニメーションの速度が変更される__ ことを確認して下さい。

```python
mbtree_anim = Mbtree_Anim(mbtree)
```

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/fc1f6d95-7556-42bb-8d38-b8e748d45862.png" width="500">

:::note
Play ウィジェットの `value` 属性は、`interval` 属性に代入されたミリ秒の間隔で増えると説明しましたが、__`interval` の値が一定以下__ の場合は __その値が正しく適用されない__ ようです。筆者のパソコンで調べた所、__`interval` 属性の値が 4 以下__ の場合は、`interval` 属性に __4 が代入されたものとして処理が行われる__ ようでした。なお、この値はパソコンや OS の種類によって異なるかもしれません。

`mbtree_anim = Mbtree_Anim(mbtree)` を実行してアニメーションを行った際に、interval の IntSlider を　1 ~ 4 の間の様々な値に変更してみて下さい。frame の数字が増える速度が変化しないことがわかるのではないかと思います。

従って `interval` 属性には 4 以下の数値を設定しても意味がないのですが、この 4 という数値がすべてのコンピューターで共通する数値であるかが良くわからないので、本記事では `interval_slider` の最小値を 1 のままにすることにします。
:::

## `interval` 属性と実際の `value` 属性の増加の間隔の違い

Play ウィジェットの __`value` 属性を増やす処理__ は、[以前の記事](https://qiita.com/ysgeso/items/1920c68f5a1e8a998796#%E3%82%A4%E3%83%99%E3%83%B3%E3%83%88%E9%A7%86%E5%8B%95%E5%9E%8B%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF)で説明した __[イベントループ](https://qiita.com/ysgeso/items/1920c68f5a1e8a998796#%E3%82%A4%E3%83%99%E3%83%B3%E3%83%88%E9%A7%86%E5%8B%95%E5%9E%8B%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF)の仕組み__ によって行われ、イベントループには、__イベントループから呼び出した処理が終了するまでは、次のイベントを処理できない__ という性質があります。そのため、`value` 属性の値が変更する間隔は実際には __`interval` 属性の値とは異なる場合があります__。

具体例として、Play ウィジェットの `value` 属性が増加した際に呼び出された __イベントハンドラが行う処理__ が __`interval` 属性で指定した時間よりも長くかかる場合__ は、`value` 属性の値は、`interval` 属性よりも __長い間隔で増加__ します。Mbtree_Anim クラスを使ってアニメーションを行った際に、interval の __IntSlider の値を小さくする__ と、__間を飛ばしながらアニメーションが行われる__ のは、上記のような理由からです。

`value` 属性の値が変更する間隔が、`interval` 属性の値よりも長くなった場合は、__`value` 属性の値__ は時間経過の分だけ、__まとめてその値が増加します__。

わかりづらいと思いますので具体例を挙げます。`interval` 属性の値に `5` を設定した場合に、`value` 属性の値が 30 ミリ秒後に変更された場合は、30 / 5 = 6 回分の `value` 属性の増加の処理がまとめて行われるので、 6 増えることになります。

下記のプログラムは、そのことを確認するプログラムです。

* __1、2 行目__：`interval` 属性に 5 を設定した Play ウィジェットを作成して、表示する
* __4、5 行目__：Play ウィジェットの `value` 属性の値が変更された場合に呼び出されるイベントハンドラを定義する。このイベントハンドラは `value` 属性の値を表示する
* __7 行目__：イベントハンドラと Play ウィジェットを結び付ける

```python
1  play = widgets.Play(interval=5)
2  display(play)
3
4  def on_play_changed(changed):
5      print(play.value)
6
7  play.observe(on_play_changed, names="value")
```

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

```python
play = widgets.Play(interval=5)
display(play)

def on_play_changed(changed):
    print(play.value)

play.observe(on_play_changed, names="value")
```
</details>

実行結果（表示される数字の間隔は、コンピュータの性能によって異なります）

```
1
10
21
31
42
50
59
67
75
82
87
94
100
```

上記のプログラムを実行して三角形のボタンをクリックすると、実行結果のように __`value` 属性の値が変更された際の値が表示__ されますが、その値は __とびとびの値__ になっています。上記の実行結果から、__`value`__ 属性は __平均すると 約 8 ずつ増えながら表示される__ ので、__実際の値の増加__ は 5 * 8 = __約 40 ミリ秒おきに行われた__ ことがわかります。

上記のように、`interval` 属性の値を小さくしても、__1 秒間に `value` 属性の値が変更される回数には限度がある__ ようです。おそらく 60 回が限度になっているので、Play ウィジェットを使った場合のアニメーションの __fps の最大値は 約 60 fps だと思われます__。ただし、この最大値はパソコンによって異なるかもしれません。

## アニメーションが遅くなる理由

`mbtree_anim = Mbtree_Anim(mbtree)` でアニメーションを行った際に、__interval__ を 10 のように __かなり小さく__ し、__frame を 500000 のように大きくする__ と、同じ interval でも表示されるアニメーションの __フレームの更新の間隔が伸びるように感じられる__ と思いますが、これは __錯覚ではありません__。そのようなことが起きる原因について少し考えてみて下さい。

その理由は、部分木を描画する __`draw_subtree`__ の中で呼び出されている、ゲーム木の __各ノードの高さを計算する `calc_node_height(maxdepth)` が原因__ です。`calc_node_height` は、ルートノードから `maxdepth` で指定した深さのノードまでの部分木を描画する際の、それぞれのノードの高さを計算する処理を行います。__`draw_subtree`__ で描画する部分木の __深さが浅い場合__ は、`maxdepth` の値が小さくなるので、__高さを計算する必要があるノードの数は多くありません__。しかし、`maxdepth` の値が例えば最大の 9 の場合は、__50 万以上のノードのすべてのノードの高さを計算する__ ことになるので、__処理に時間がかかります__。

そのことは、下記のプログラムで確認することができます。

下記は __深さ 1 まで__ のゲーム木の各ノードの高さの計算の処理時間を計測するプログラムで、実行結果から平均すると __約 1.14 μs（約百万分の 1 秒）__ かかることがわかります。

```python
%%timeit 
mbtree.calc_node_height(maxdepth=1)
```

実行結果

```
1.14 µs ± 3.07 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
```

下記は深さ 9 までのゲーム木の各ノードの高さの計算の処理時間を計測するプログラムで、実行結果から平均すると __約 212 ms（約 0.21 秒）__ もの時間がかかることがわかります。高さを計算するだけで 0.21 秒もかかるということは、1000 / 213 = 約 5 なので、__約 5 fps 以上のアニメーションを行うことはできない__ ことがわかります。

```python
%%timeit 
mbtree.calc_node_height(maxdepth=9)
```

実行結果

```
212 ms ± 3.21 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

下図の __深さが 9 の部分木__ を描画する際に __高さを計算する必要があるノード__ は、下図の __赤枠の中のたった 16 個のノードだけ__ です。それにもかかわらず 50 万以上のノードの高さを計算するのは、__かなりの無駄な処理を行っている__ ということです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ac189491-24c5-8e11-8dd6-c028e2cdddd1.png" width="400">

アニメーションを行わない場合は、ノードの高さの計算に 約 0.2 秒かかってもほとんど気になりませんでしたが、アニメーションのように __描画を高速に行わなければならない場合__ は、このような __無駄な処理が__ アニメーションの __fps の大きな低下につながります__。そこで、__必要なノードの高さだけを計算する__ ように __`calc_node_height`__ を修正することにします。

## `calc_node_height` の修正

現状の `calc_node_height` は、必ずルートノードから `maxdepth` までの部分木の各ノードの高さを計算していましたが、必要となる計算は、__中心となるノードから `maxdepth` まで__ の部分木の各ノードの高さです。そこで、__`calc_node_height`__ に、中心となるノードを代入する __`centernode` という仮引数を追加する__ ことにします。

次に `centernode` から `maxdepth` までの部分木のノードの一覧を計算する必要がありますが、その方法は、ゲーム木を作成する `create_tree_by_bf` とほぼ同じ、__[幅優先アルゴリズム](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E5%B9%85%E5%84%AA%E5%85%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%82%88%E3%82%8B%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%82%92%E4%BD%9C%E6%88%90%E3%81%99%E3%82%8B%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9-%E3%81%9D%E3%81%AE-1)で計算__ することができます。`create_tree_by_bf` との具体的な違いは、以下の通りです。

* __最初に `nodelist` に登録__ するノードを、ルートノードから __`centernode` に変更__ する
* __ノードの深さ__ を表す __`depth`__ を `0` ではなく、__`centernode.depth`__ で初期化する
* `create_tree_by_bf` では、各ノードの子ノードを作成する必要があったが、`calc_node_height` では __ノードはすべて作成済__ である
* `create_tree_by_bf` では、__ゲーム木全体__ の各深さのノードの一覧を __後で利用できるようにする__ ために、その情報を __`nodelist_by_depth` という属性__ に代入していたが、`calc_node_height` で計算するのは __部分木__ の各深さのノードの一覧である。また、その情報は、__`calc_node_height` の処理が終わった後で利用することはない__ ので、同じ名前の __ローカル変数に代入する__ ことにする
* `create_tree_by_bf` では、__深さ 0 のルートノードから `nodelist_by_depth` にデータを記録__ したが、`calc_node_height` では __`centernode` の深さからデータを記録する__
* `print` などの処理は必要がないので削除する

`nodelist_by_depth` の計算後は、元の `calc_node_height` と同様の方法で、 `maxdepth` から `centernode` の深さの順で、各ノードの高さを計算することができます。

下記は、そのように `calc_node_height` を修正したプログラムです。

* __全体__：`self.node_list_by_depth` をローカル変数 `node_list_by_depth` に修正する
* __1 行目__：仮引数 `centernode` を追加する
* __2 行目__：`nodelist` を、`centernode` を要素とする list で初期化するようにする
* __3 行目__：`depth` に `centernode` の深さを代入するように修正する
* __5 行目__：`depth` より浅いノードの高さは計算しないが、`node_list_by_depth` の 0 ~ depth - 1 番の要素には何らかの値を代入しておく必要があるので、`None` で初期化する
* __6 行目__：`node_list_by_depth` の `depth` の深さのデータとして、`nodelist` を追加する
* __10 ~ 12 行目__：深さが `depth` のノードの子ノードの一覧を計算する。`create_tree_by_bf` と異なり、子ノードは計算済なので、`node.children` を順次追加するだけで良い
* __17 行目__：`maxdepth` の深さから、`centernode` の深さまで、深い順に各ノードの高さを計算するように修正する。計算方法は元のプログラムと同じ

```python
 1  def calc_node_height(self, centernode, maxdepth):
 2      nodelist = [centernode]
 3      depth = centernode.depth
 4      # 各深さのノードのリストを記録する変数を初期化する
 5      nodelist_by_depth = [None] * centernode.depth
 6      nodelist_by_depth.append(nodelist)
 7   
 8      # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
 9      while len(nodelist) > 0:
10          childnodelist = [] 
11          for node in nodelist:
12              childnodelist += node.children
13          nodelist_by_depth.append(childnodelist)
14          nodelist = childnodelist
15          depth += 1
16    
17      for depth in range(maxdepth, centernode.depth - 1, -1):
18          for node in nodelist_by_depth[depth]:
19              if depth == maxdepth:
20                  node.height = 4
21              else:
22                  node.calc_height()                  
23                
24  Mbtree.calc_node_height = calc_node_height
```

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

```python
def calc_node_height(self, centernode, maxdepth):
    nodelist = [centernode]
    depth = centernode.depth
    # 各深さのノードのリストを記録する変数を初期化する
    nodelist_by_depth = [None] * centernode.depth
    nodelist_by_depth.append(nodelist)
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            childnodelist += node.children
        nodelist_by_depth.append(childnodelist)
        nodelist = childnodelist
        depth += 1
    
    for depth in range(maxdepth, centernode.depth - 1, -1):
        for node in nodelist_by_depth[depth]:
            if depth == maxdepth:
                node.height = 4
            else:
                node.calc_height()                  
                
Mbtree.calc_node_height = calc_node_height
```
</details>

<details><summary><strong>修正箇所（前半部分は <code>create_tree_by_bf</code> との違い、<code>for depth in・・・</code> 以降の後半部分は元の <code>calc_node_height</code> との違いです）</strong></summary>

```diff_python
-def calc_node_height(self, maxdepth):
+def calc_node_height(self, centernode, maxdepth):
-   nodelist = [self.root]
+   nodelist = [centernode]
-   depth = 0
+   depth = centernode.depth
    # 各深さのノードのリストを記録する変数を初期化する
-   self.nodelist_by_depth = [ nodelist ]
+   nodelist_by_depth = [None] * centernode.depth
+   nodelist_by_depth.append(nodelist)
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
-           if node.mb.status == Marubatsu.PLAYING:
-               node.calc_children()
            childnodelist += node.children
-       self.nodelist_by_depth.append(childnodelist)
+       nodelist_by_depth.append(childnodelist)
        nodelist = childnodelist
        depth += 1
-       print(f"{len(nodelist):>6} depth {depth} node created")
    
-   for depth in range(maxdepth, -1, -1):
+   for depth in range(maxdepth, centernode.depth - 1, -1):
-       for node in self.nodelist_by_depth[depth]:
+       for node in nodelist_by_depth[depth]:
            if depth == maxdepth:
                node.height = 4
            else:
                node.calc_height()                  
                
Mbtree.calc_node_height = calc_node_height
```
</details>

上記の修正後に、下記のプログラムで深さ 6 のノードを中心とする深さ 9 までのノードの処理時間を計測すると、実行結果のように処理時間が大幅に短くなったことが確認できます。

```python
%%timeit 
mbtree.calc_node_height(mbtree.nodelist_by_depth[6][0], maxdepth=9)
```

実行結果

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

## `draw_subtree` の修正

`draw_subtree` の修正は、下記のプログラムの 6 行目のように、`calc_node_height` にキーワード引数 `centernode=centernode` を追加するだけです。

```python
1  def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):
2      self.nodes_by_rect = {}
3
4      if centernode is None:
5          centernode = self.root
6      self.calc_node_height(centernode=centernode, maxdepth=maxdepth)
元と同じなので省略
7            
8  Mbtree.draw_subtree = draw_subtree
```

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

```python
def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):
    self.nodes_by_rect = {}

    if centernode is None:
        centernode = self.root
    self.calc_node_height(centernode=centernode, maxdepth=maxdepth)
    width = 5 * (maxdepth + 1)
    height = centernode.height
    parent = centernode.parent
    if parent is not None:
        height += (len(parent.children) - 1) * 4
        parent.height = height
    if ax is None:
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")        
    
    nodelist = [centernode]
    depth = centernode.depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        if parent is not None:
            dy = parent.children.index(centernode) * 4
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
                childnodelist.append(None)
            else:
                dx = 5 * node.depth
                emphasize = node is selectednode
                rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = node
                dy += node.height
                if len(node.children) > 0:  
                    childnodelist += node.children
                else:
                    childnodelist.append(None)
        depth += 1
        nodelist = childnodelist
        
    if parent is not None:
        dy = 0
        for sibling in parent.children:
            if sibling is not centernode:
                sibling.height = 4
                dx = 5 * sibling.depth
                rect = sibling.draw_node(ax, maxdepth=sibling.depth, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = sibling
            dy += sibling.height
        dx = 5 * parent.depth
        rect = parent.draw_node(ax, maxdepth=maxdepth, size=size, lw=lw, dx=dx, dy=0)
        self.nodes_by_rect[rect] = parent
    
        node = parent
        while node.parent is not None:
            node = node.parent
            node.height = height
            dx = 5 * node.depth
            rect = node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
            self.nodes_by_rect[rect] = node
            
Mbtree.draw_subtree = draw_subtree
```
</details>

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

```diff_python
def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):
    self.nodes_by_rect = {}

    if centernode is None:
        centernode = self.root
-   self.calc_node_height(maxdepth)
+   self.calc_node_height(centernode=centernode, maxdepth=maxdepth)
元と同じなので省略
            
Mbtree.draw_subtree = draw_subtree
```
</details>

実行結果は省略しますが、上記の修正後に、下記のプログラムを実行し、interval を小さくしてアニメーションを行うと、frame を変更してもアニメーションの fps がほとんど変わらないようになったことを確認して下さい。

```python
mbtree_anim = Mbtree_Anim(mbtree)
```

# 今回の記事のまとめ

今回の記事では、ゲーム木の生成の過程のアニメーションの改良を行いました。

次回の記事では、ゲーム木を生成するもう一つのアルゴリズムである、__深さ優先アルゴリズム__ について説明する予定です。

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

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

# 次回の記事

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

[^1]:std は標準偏差を表す standard deviation の略です
[^2]:マイクロはギリシャ文字で μ と表記します。micro の頭文字である m と表記しない理由は mili と micro の頭文字が被っているからです
[^3]:正確には、計測された処理時間が __正規分布に従う場合は__ という条件がつきます。また、プログラムを何度も実行した際の処理時間の分布は、多くの場合はほぼ正規分布に従うことが知られています。正規分布は統計学で出てくる用語で、本記事でも必要があればこの後の記事で紹介するかもしれません。興味がある方は勉強してみて下さい
[^4]:色を表すデジタルデータの中で、透明度を表すデータの事を α（アルファ）値と呼びます。なお、透明度を表す英単語は opacity です
[^5]:具体的には、仮引数が増えて複雑になる、`draw_board` の中で行う処理が複雑になるなどです