Pythonで〇×ゲームのAIを一から作成する　その106　深さ優先アルゴリズムと幅優先アルゴリズムでのゲーム木の評価値の計算の過程の視覚化

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/3400391d2637eafc8899

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

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

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

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

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

# 深さ優先アルゴリズムによる評価値の計算の過程の視覚化

[前回の記事](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E6%B7%B1%E3%81%95%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%E5%AE%9F%E8%A3%85)では、__深さ優先アルゴリズム__ でゲーム木の評価値を計算する `calc_score_by_df` を実装しましたが、__評価値の計算の過程が直観的にわかりづらい__ と思いましたので、今回の記事ではその処理の過程を視覚化することにします。

最強の AI の作成は次回の記事で行います。

## 視覚化に必要なデータの計算

[以前の記事](https://qiita.com/ysgeso/items/c82c854c529172f74103)でゲーム木の作成の過程のアニメーションを行う Mbtree_Anim クラスを定義しましたが、__評価値の計算の過程の視覚化__ も同様に __アニメーションで行う__ ことにします。どのようなアニメーションにすれば良いかについて少し考えてみて下さい。

### 視覚化の方針

本記事では下記のような方針のアニメーションで計算の過程を視覚化することにします。もっと良い視覚化の方法を思いついた方はその方針での実装にチャレンジしてみて下さい。

* 計算の過程で `calc_score_by_df` が __処理を行うノードの移り変わりがわかる__ ようにする
* __評価値を計算__ する __タイミングがわかる__ ようにする

上記の方針でアニメーションを行うためには、`calc_score_by_df` による、__別のノードへの処理の移り変わりを記録する__ 必要があります。また、__評価値が計算されるタイミングを記録__ する必要があります。

### `nodelist_by_score` の記録

まず、__別のノードへの処理の移り変わりを記録__ する処理を実装することにします。本記事ではそのデータを、Mbtree クラスの __`nodelist_by_score`__ という名前の属性に __list で記録する__ ことにします。次に、別のノードへの処理の移り変わりが __どのタイミングで行われるか__ を考える必要があります。どのようなタイミングであるかについて少し考えてみて下さい。

__`calc_score_by_df`__ は、__仮引数 `node` に代入されたノードの処理を行う__ 関数で、評価値を計算する処理は、この関数に対する __再帰呼び出し__ で行います。従って、別のノードへの処理の移り変わりは、以下のタイミングで行われます。

* `calc_score_by_df` が __呼び出された時__
* `calc_score_by_df` の中で呼び出された __再帰呼び出しの処理が終了した時__

従って、`calc_score_by_df` を下記のプログラムのように修正することで、`nodelist_by_score` に別のノードへの処理の移り変わりを記録することができます。

* __5 行目__：`calc_score_by_df` が __呼び出された直後__ に、`nodelist_by_score` の要素に `node` を追加して記録する
* __14、15 行目__：`node` のそれぞれの子ノードの評価値を計算するための再帰呼び出しの処理が終了するたびに　`nodelist_by_score` に要素を追加する処理は、__list 内包表記では記述できない__ ので、list 内包表記を __for 文を使った記述に修正する__
* __16 行目__：子ノードの評価値を計算するための __再帰呼び出しの処理の終了後__ に、`nodelist_by_score` の要素に `node` を追加して記録する

```python
 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3
 4  def calc_score_by_df(self, node):
 5      self.nodelist_by_score.append(node)
 6      if node.mb.status == Marubatsu.CIRCLE:
 7          node.score = 1
 8      elif node.mb.status == Marubatsu.DRAW:
 9          node.score = 0
10      elif node.mb.status == Marubatsu.CROSS:
11          node.score = -1
12      else:
13          score_list = []
14          for childnode in node.children:
15              score_list.append(self.calc_score_by_df(childnode))
16              self.nodelist_by_score.append(node)
17          if node.mb.move_count % 2 == 0:
18              score = max(score_list)
19          else:
20              score = min(score_list)
21          node.score = score
22
23      return node.score                
24
25  Mbtree.calc_score_by_df = calc_score_by_df
```

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

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

def calc_score_by_df(self, node):
    self.nodelist_by_score.append(node)
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = -1
    else:
        score_list = []
        for childnode in node.children:
            score_list.append(self.calc_score_by_df(childnode))
            self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score

    return node.score                

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

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

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

def calc_score_by_df(self, node):
+   self.nodelist_by_score.append(node)
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = -1
    else:
        score_list = []
-       score_list = [self.calc_score_by_df(childnode) for childnode in node.children]
+       for childnode in node.children:
+           score_list.append(self.calc_score_by_df(childnode))
+           self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score

    return node.score                

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

上記の修正を行った後で、下記のプログラムを実行すると、実行結果から `calc_score_by_df` によって __`nodelist_by_score`__ のデータが __計算できていそうなことが確認__ できます。なお、本当に計算できているかどうかについてはもっとデータを見る必要がありますが、その確認はこの後で作成するアニメーションで行うことにします。

* __1 行目__：[前回の記事](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E4%BF%9D%E5%AD%98)で保存した `dfscore.mbtree` から Mbtree のデータを読み込む
* __2 行目__：`nodelist_by_score` 属性を空の list で初期化する
* __3 行目__：`calc_score_by_df` を呼び出して、評価値と `nodelist_by_score` を計算する
* __4、5 行目__：`nodelist_by_score` の最初の 5 つのノードの局面を表示する

```python
1  mbtree_df = Mbtree.load("dfscore")
2  mbtree_df.nodelist_by_score = []
3  mbtree_df.calc_score_by_df(mbtree_df.root)
4  for i in range(5):
5      print(mbtree_df.nodelist_by_score[i].mb)
```

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

```python
mbtree_df = Mbtree.load("dfscore")
mbtree_df.nodelist_by_score = []
mbtree_df.calc_score_by_df(mbtree_df.root)
for i in range(5):
    print(mbtree_df.nodelist_by_score[i].mb)
```
</details>

実行結果

```
Turn o
...
...
...

Turn x
O..
...
...

Turn o
oX.
...
...

Turn x
oxO
...
...

Turn o
oxo
X..
...
```

### 評価値が計算されたタイミングの記録

次にノードの __評価値が計算されたタイミングを記録__ する処理を実装します。どのように実装すればよいかについて少し考えてみて下さい。

まず、ノードの評価値が計算されたタイミングを __どのように表現するか__ を考える必要があります。先程 __`nodelist_by_score`__ には別のノードへの処理の移り変わりを表すデータ記録しましたが、__その中にノードの評価値が計算されたことを表すデータを記録__ することによって、ノードの評価値が計算されたタイミングを、__`nodelist_by_score` の要素のインデックスで表現__ することができるようになります。

ノード評価値が計算されたタイミングを表すデータは、そのノードの属性に記録するのが自然なので、__`score_index`__ という属性に代入することにします。

言葉の説明ではわかりづらいと思いますので、具体例として、評価値を計算する過程で、再起呼びしで __`calc_score_by_df`__ が下図の __ノード A__ を実引数に記述して __呼び出された場合__ に行われる処理について説明します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/549213da-af7f-0245-a92a-faa7fbcc645c.png" width="450">

この場合は、以下の手順で処理が行われます。

* ノード A が実引数に記述されて `calc_score_by_df` が呼び出される
* 呼び出された `calc_score_by_df` の最初で `nodelist_by_score` にノード A が登録される
* ノード B が実引数に記述されて `calc_score_by_df` が呼び出される
* 呼び出された `calc_score_by_df` の最初で `nodelist_by_score` にノード B が登録される
* ノード C が実引数に記述されて `calc_score_by_df` が呼び出される
* 呼び出された `calc_score_by_df` の最初で `nodelist_by_score` にノード C が登録される
* __ノード C__ の __評価値が計算__ され `nodelist_by_score` に図の __赤字のノード C が登録__ される
* __ノード C__ の __`score_index`__ 属性に、図の __赤字のノード C が代入__ されている __`nodelist_by_score` の要素のインデックス__ を代入する
* ノード C の処理を行う `calc_score_by_df` の処理が終了する
* ノード B の処理を行う `calc_score_by_df` の中で、`nodelist_by_score` にノード B が登録される
* 以下処理が続いていく

下記は、評価値が計算されたタイミングを記録するように `calc_score_by_df` を修正したプログラムです。

* __3 行目__：`node` の評価値が計算され、返り値を返す前に、`nodelist_by_score` に `node` を追加する
* __4 行目__：追加した `node` のインデックスは、`nodelist_by_score` の要素の数 - 1 なので、その値を `node` の `score_index` 属性に代入する

```python
1  def calc_score_by_df(self, node):
元と同じなので省略
2
3      self.nodelist_by_score.append(node)
4      node.score_index = len(self.nodelist_by_score) - 1        
5      return node.score                
6
7  Mbtree.calc_score_by_df = calc_score_by_df
```

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

```python
def calc_score_by_df(self, node):
    self.nodelist_by_score.append(node)
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = -1
    else:
        score_list = []
        for childnode in node.children:
            score_list.append(self.calc_score_by_df(childnode))
            self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score
        
    self.nodelist_by_score.append(node)
    node.score_index = len(self.nodelist_by_score) - 1        
    return node.score                

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

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

```diff_python
def calc_score_by_df(self, node):
元と同じなので省略

+   self.nodelist_by_score.append(node)
+   node.score_index = len(self.nodelist_by_score) - 1        
    return node.score                

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

深さ優先アルゴリズムの場合は、__ルートノードの評価値は最後に計算される__ ので、__ルートノードの `score_index` 属性__ は、__`nodelist_by_score` の最後の要素__ のインデックスである`nodelist_by_score` の要素の数 - 1 になります。上記の修正後に、下記のプログラムで `calc_score_by_df` を実行し直し、`nodelist_by_score` の要素の数とルートノードの `score_index` 属性を表示すると、実行結果からそのようになっていることが確認できます。

```python
mbtree_df.nodelist_by_score = []
mbtree_df.calc_score_by_df(mbtree_df.root)
print(len(mbtree_df.nodelist_by_score), mbtree_df.root.score_index)
```

実行結果

```
1649837 1649836
```

### `__init__` メソッドの修正

修正した `calc_score_by_df` で評価値を計算する際には、上記のプログラムのように `nodelst_by_score` を空の list で初期化する処理が必要になりますが、その処理は Mbtree クラスの __`__init__` メソッドには記述されていない__ ので、下記のプログラム 5 行目のように `__init__` メソッドを修正する必要があります。

```python
1  from tree import Node
2
3  def __init__(self, algo:str="bf"):   
元と同じなので省略
4          self.create_tree_by_df(self.root)
5          self.nodelist_by_score = []
6          self.calc_score_by_df(self.root)
7        
8  Mbtree.__init__ = __init__
```

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

```python
from tree import Node

def __init__(self, algo:str="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)
        
Mbtree.__init__ = __init__
```
</details>

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

```diff_python
from tree import Node

def __init__(self, algo:str="bf"):   
元と同じなので省略
        self.create_tree_by_df(self.root)
+       self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
        
Mbtree.__init__ = __init__
```
</details>

上記の修正後に、下記のプログラムを実行することで、深さ優先アルゴリズムで Mbtree クラスのインスタンスを作成した際に、`nodelist_by_score` とルートノードの `score_index` 属性が計算されることが確認できます。

```python
mbtree_df = Mbtree(algo="df")
print(len(mbtree_df.nodelist_by_score), mbtree_df.root.score_index)
```

実行結果

```
1649837 1649836
```

## アニメーション処理の実装

実は、上記の視覚化の処理の方針は、アニメーションを行う __Mbtree_Anim を使って__ 深さ優先アルゴリズムによる評価値の計算の過程の __視覚化を行えるように考えて作った__ ものです。

Mbtree_Anim は、__ゲーム木のノードの作成の経過__ を以下のアニメーションで行います。

* Mbtree の __`nodelist`__ 属性は、ゲーム木に __ノードが登録された順番__ でノードを記録する
* __`nodelist`__ に記録されたノードの順番で、ゲーム木の部分木の選択されたノードが移り変わるアニメーションを行う
* アニメーションでは、選択されたノードよりも __後に作成されたノード__ を暗く表示する
* その判定は、__`nodelist`__ の中で選択されたノードが代入された要素のインデックスと、描画するノードが __ゲーム木に登録された順番__ を表す __`id` 属性を比較__ することで行える

一方、これから実装する __深さ優先アルゴリズムによる評価値の計算の過程__ のアニメーションは、以下のように行います。

* Mbtree の __`nodelist_by_score`__ 属性は、評価値の計算の過程で処理が __別のノードに移り変わった場合__ と、__評価値が計算された場合__ のノードを順番に記録する
* __`nodelist_by_score`__ に記録されたノードの順番で、ゲーム木の部分木の選択されたノードが移り変わるアニメーションを行う
* アニメーションのでは、選択されたノードよりも __後に評価値の計算が行われたノード__ を暗く表示する
* その判定は、__`nodelist_by_score`__ の中で選択されたノードが代入された要素のインデックスと、描画するノードの __評価値が計算された順番__ を表す __`score_index` 属性を比較__ することで行える

上記の 2 つの違いは以下の通りです。

|  | ノードの作成の過程 | 評価値の計算の過程 | 
|:--|:--|:--|
| __ノードのリストの属性__  | `nodelist`  | `nodelist_by_score` |
| __選択されたノードの__<br>__インデックスの比較対象__  | ノードの `id` 属性  | ノードの `score_index` 属性 |

__上記以外の処理は共通する__ ので、深さ優先アルゴリズムによる評価値の計算の過程の視覚化の処理を、__Mbtree_Anim クラスを修正することで実装__ することができます。

### `__init__` 属性の修正

__Mbtree_Anim__ クラスで __両方のアニメーション処理__ を行うことができるようにするためには、Mbtree_Anim クラスの __インスタンスを作成する際__ に、__どちらのアニメーションで処理を行うかを指定__ できるようにする必要があります。そこで、下記のプログラムのように、__`__init__`__ メソッドに下記のような __仮引数 `isscore` を追加__ することにします。

* `False` が代入されている場合は、ゲーム木の生成の過程のアニメーションを、`True` が代入されている場合は、評価値の計算の過程のアニメーションを行う
* 互換性を考慮して、デフォルト値が `False` のデフォルト引数とする

下記はそのように `__init__` メソッドを修正したプログラムです。なお、`__init__` メソッドでは `super()` を呼び出しているので、[クラスを定義し直す](https://qiita.com/ysgeso/items/2acd8c5ceb8e9cda7233#%E3%82%AA%E3%83%BC%E3%83%90%E3%83%BC%E3%83%A9%E3%82%A4%E3%83%89%E3%81%AE%E7%9B%AE%E7%9A%84%E3%81%A8%E5%9F%BA%E5%BA%95%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97)必要があります。

* __8 行目__：デフォルト値を `False` とする仮引数 `isscore` を追加する
* __10 行目__：`isscore` を同名の属性に代入する
* __14 行目__：__アニメーション処理を行うノードの一覧__ が代入された Mbtree クラスの属性を __`isscore` の値に応じて計算__ し、__`nodelist` 属性に代入__ する。この処理によって `isscore` 属性の値に関わらず、__共通の記述でアニメーションを行うことができる__ ようになる
* __15 行目__：`self.nodelist` の __要素の数__ を計算し、__`nodenum` 属性に代入__ しておく。この処理も、共通の記述でアニメーションを行うことができるようにするためのものである

```python
 1  from tree import Mbtree_Anim
 2  from gui import GUI
 3  import matplotlib.pyplot as plt
 4  import matplotlib.patches as patches
 5  from ipywidgets import widgets
 6
 7  class Mbtree_Anim(GUI):
 8      def __init__(self, mbtree, isscore=False, size=0.15):
 9          self.mbtree = mbtree
10          self.isscore = isscore
11          self.size = size
12          self.width = 50
13          self.height = 64
14          self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
15          self.nodenum = len(self.nodelist)
16          super().__init__()
元と同じなので省略
```

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

```python
from tree import Mbtree_Anim
from gui import GUI
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from ipywidgets import widgets

class Mbtree_Anim(GUI):
    def __init__(self, mbtree, isscore=False, size=0.15):
        self.mbtree = mbtree
        self.isscore = isscore
        self.size = size
        self.width = 50
        self.height = 64
        self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
        self.nodenum = len(self.nodelist)
        super().__init__()
        
    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 
        
    def display_widgets(self):
        """ウィジェットを配置して表示する."""
        
        hbox = widgets.HBox([self.play, self.frame_slider, self.interval_slider])
        display(widgets.VBox([hbox, self.fig.canvas]))
        
    def create_event_handler(self):
        """イベントハンドラを登録する."""

        def on_play_changed(changed):
            self.update_gui()
            
        self.play.observe(on_play_changed, names="value")
    
    def update_gui(self):
        """GUI の表示を更新する."""
        
        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.mbtree.algo == "bf":
            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))
```
</details>

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

```diff_python
from tree import Mbtree_Anim
from gui import GUI
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from ipywidgets import widgets

class Mbtree_Anim(GUI):
-   def __init__(self, mbtree, size=0.15):
+   def __init__(self, mbtree, isscore=False, size=0.15):
        self.mbtree = mbtree
+       self.isscore = isscore
        self.size = size
        self.width = 50
        self.height = 64
+       self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
+       self.nodenum = len(self.nodelist)
        super().__init__()
元と同じなので省略
```
</details>

### `create_widgets` の修正

`isscore` 属性などの追加に合わせて、他のメソッドを修正する必要があります。

まず、`create_widgets` を下記のプログラムのように修正します。

* __2、3 行目__：元のプログラムでは、Play と IntSlider ウィジェットの __`value` 属性の最大値__ を `self.mbtree.nodelist - 1` という式で計算して設定していたが、`__init__` メソッドででアニメーションを行うノードの一覧を表す list の __要素の数を`nodenum` 属性 に代入__ したので、それを使うように修正する

```python
1  def create_widgets(self):
2      self.play = widgets.Play(max=self.nodenum - 1, interval=500)
3      self.frame_slider = widgets.IntSlider(max=self.nodenum - 1, description="frame")
元と同じなので省略
4
5  Mbtree_Anim.create_widgets = create_widgets
```

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

```python
def create_widgets(self):
    self.play = widgets.Play(max=self.nodenum - 1, interval=500)
    self.frame_slider = widgets.IntSlider(max=self.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
def create_widgets(self):
-   self.play = widgets.Play(max=self.mbtree.nodenum - 1, interval=500)
+   self.play = widgets.Play(max=self.nodenum - 1, interval=500)
-   self.frame_slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
+   self.frame_slider = widgets.IntSlider(max=self.nodenum - 1, description="frame")
元と同じなので省略

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

### `update_gui` の修正

次に、`update_gui` を下記のプログラムのように修正します。

* __8 行目__：__選択されたのノード__ を、__`self.nodelist` から選択する__ ように修正する
* __10 行目__：暗い色で表示するかどうかを判定するために用いるノードの属性を __`self.isscore` の値に応じて計算__ し、`index` に代入する
* __11 行目__：選択されたのノードのインデックスを表す `self.play.value` と `index` と比較することで、ノードを暗く表示するかを判定するように修正する

```python
 1  def update_gui(self):
 2      self.ax.clear()
 3      self.ax.set_xlim(-1, self.width - 1)
 4      self.ax.set_ylim(0, self.height)   
 5      self.ax.invert_yaxis()
 6      self.ax.axis("off")   
 7   
 8      self.selectednode = self.nodelist[self.play.value]
元と同じなので省略
 9      for rect, node in self.mbtree.nodes_by_rect.items():
10          index = node.score_index if self.isscore else node.id
11          if index > self.play.value:
12              self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))
13
14  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.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.mbtree.algo == "bf":
        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():
        index = node.score_index if self.isscore else node.id
        if index > 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.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.selectednode = self.nodelist[self.play.value]
元と同じなので省略
    for rect, node in self.mbtree.nodes_by_rect.items():
-       if node.id > self.play.value:
+       index = node.score_index if self.isscore else node.id
+       if index > 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_df, isscore=True)
```

実行結果（0 ~ 30 フレームまでのアニメーションの繰り返しです）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/387e593b-0a57-d43d-f3cf-66d133388118.gif" width="500">

## Mbtree_Anim の改良

Mbtree_Anim にはいくつかの欠点があるので、改良することにします。どのような欠点があるかについて少し考えてみて下さい。

### コマ送りとコマ戻しの機能の実装

ゲーム木の生成の過程のアニメーションの場合は、処理の流れを実感することが大事だと思ったので、アニメーションの ON/OFF と、アニメーションの速度の調整の機能のみを実装しましたが、__自分でアニメーションのフレームを前後に移動__ することができれば、__処理の流れをより確認しやすくなります__。

そこで、Mbtree_Anim に、__フレームを前後に移動__ する、いわゆる __コマ送りとコマ戻し__ の機能を実装することにします。具体的には一つ前のフレームに戻るボタンと、一つ後のフレームに進むボタンを追加します。

それぞれのボタンに表示する文字は、〇×ゲームの GUI と同様に < と > にし、Play ウィジェットの右に配置することにします。

### `create_widgets` の修正

まず、`create_widgets` を下記のプログラムのように修正します。

* __2、3 行目__：[`create_button`](https://qiita.com/ysgeso/items/aa8654c3b5f55a9e08b7#%E3%83%9C%E3%82%BF%E3%83%B3%E3%82%92%E4%BD%9C%E6%88%90%E3%81%99%E3%82%8B%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9) メソッドを使って、2 つのボタンを作成する

```python
1  def create_widgets(self):
2      self.play = widgets.Play(max=self.nodenum - 1, interval=500)
3      self.prev_button = self.create_button("<", width=30)
4      self.next_button = self.create_button(">", width=30)
元と同じなので省略
5
6  Mbtree_Anim.create_widgets = create_widgets    
```

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

```python
def create_widgets(self):
    self.play = widgets.Play(max=self.nodenum - 1, interval=500)
    self.prev_button = self.create_button("<", width=30)
    self.next_button = self.create_button(">", width=30)
    self.frame_slider = widgets.IntSlider(max=self.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
def create_widgets(self):
    self.play = widgets.Play(max=self.nodenum - 1, interval=500)
+   self.prev_button = self.create_button("<", width=30)
+   self.next_button = self.create_button(">", width=30)
元と同じなので省略

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

### `display_widgets` の修正

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

* __2 行目__：Play ウィジェットの右に、< ボタン と > ボタンを並べて配置する

```python
1  def display_widgets(self):
2      hbox = widgets.HBox([self.play, self.prev_button, self.next_button, 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.prev_button, self.next_button, 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])
+   hbox = widgets.HBox([self.play, self.prev_button, self.next_button, self.frame_slider, self.interval_slider])
    display(widgets.VBox([hbox, self.fig.canvas])) 

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

### `create_event_handler` の修正

次に、`create_event_handler` を下記のプログラムのように修正します。なお、キー入力による操作や、ヘルプボタンは省略しました。必要だと思った方は実装して下さい。

* __5 ~ 7 行目__：< ボタンをクリックした際に実行するイベントハンドラを定義する。行う処理は、Play ウィジェットの `value` 属性を 1 減らし、`update_gui` で表示を更新する
* __9 ~ 11 行目__：> ボタンをクリックした際に実行するイベントハンドラを定義する。行う処理は、Play ウィジェットの `value` 属性を 1 f増やし、`update_gui` で表示を更新する
* __13、14 行目__：ボタンとイベントハンドラを結び付ける

```python
 1  def create_event_handler(self):
 2      def on_play_changed(changed):
 3          self.update_gui()
 4       
 5      def on_prev_button_clicked(b=None):
 6          self.play.value -= 1
 7          self.update_gui()
 8       
 9      def on_next_button_clicked(b=None):
10          self.play.value += 1
11          self.update_gui()
12
13      self.prev_button.on_click(on_prev_button_clicked)
14      self.next_button.on_click(on_next_button_clicked)
15
16      self.play.observe(on_play_changed, names="value")
17    
18  Mbtree_Anim.create_event_handler = create_event_handler 
```

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

```python
def create_event_handler(self):
    def on_play_changed(changed):
        self.update_gui()
        
    def on_prev_button_clicked(b=None):
        self.play.value -= 1
        self.update_gui()
        
    def on_next_button_clicked(b=None):
        self.play.value += 1
        self.update_gui()

    self.prev_button.on_click(on_prev_button_clicked)
    self.next_button.on_click(on_next_button_clicked)

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

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

```diff_python
def create_event_handler(self):
    def on_play_changed(changed):
        self.update_gui()
        
+   def on_prev_button_clicked(b=None):
+       self.play.value -= 1
+       self.update_gui()
        
+   def on_next_button_clicked(b=None):
+       self.play.value += 1
+       self.update_gui()

+   self.prev_button.on_click(on_prev_button_clicked)
+   self.next_button.on_click(on_next_button_clicked)

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

### `update_gui` の修正

最後に、`update_gui` を下記のプログラムのように修正します。

__2、3 行目__：[`set_button_status`](https://qiita.com/ysgeso/items/c2d569b1be171fbe4b31#set_button_status-%E3%81%A8-update_widgets_status-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9) メソッドを使って、最初のフレームで < ボタンを灰色にして押せないようにする
__4、5 行目__：最後のフレームで > ボタンを灰色にして押せないようにする

```python
1  def update_gui(self):
元と同じなので省略
2      disabled = self.play.value == 0
3      self.set_button_status(self.prev_button, disabled=disabled)
4      disabled = self.play.value == self.nodenum - 1
5      self.set_button_status(self.next_button, disabled=disabled)
6
7  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.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.mbtree.algo == "bf":
        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():
        index = node.score_index if self.isscore else node.id
        if index > 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))

    disabled = self.play.value == 0
    self.set_button_status(self.prev_button, disabled=disabled)
    disabled = self.play.value == self.nodenum - 1
    self.set_button_status(self.next_button, disabled=disabled)

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

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

```diff_python
def update_gui(self):
元と同じなので省略
+   disabled = self.play.value == 0
+   self.set_button_status(self.prev_button, disabled=disabled)
+   disabled = self.play.value == self.nodenum - 1
+   self.set_button_status(self.next_button, disabled=disabled)

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように < と > ボタンが表示されるようになります。また、< と > ボタンが正しく動作することを確認して下さい。

```python
mbtree_anim = Mbtree_Anim(mbtree_df, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f8d38ca2-f7b1-28f4-c902-6000dd6d13a0.png" width="500">

### 選択されたのノードの表示の改良

評価値の経過を表示するアニメーションでは、上図のように、選択されたノードの __赤い枠が暗く表示されてしまう__ ため、あまり __目立たなくなってしまう__ という問題があります。これは、選択されたノードを暗く表示する際に、ゲーム盤の上に [半透明の黒い図形を重ねて表示](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#%E5%8D%8A%E9%80%8F%E6%98%8E%E3%81%AE%E9%BB%92%E3%81%84%E5%9B%B3%E5%BD%A2%E3%82%92%E9%87%8D%E3%81%AD%E3%82%8B%E6%96%B9%E6%B3%95)したため、選択されたノードの __赤い枠も暗く表示されてしまう__ からです。

:::note
この問題はゲーム木の作成の過程を表示するアニメーションでは、選択されたノードは暗く表示されることがないのでこのような現象は発生しません。
:::

本記事では、`update_gui` で選択されたノードに対して暗く表示する処理を行った後で、__改めて赤い枠を表示する__ ことでこの問題に対処することにします。また、その際に以下のような工夫を行いました。他にも様々な対処法があると思いますので、もっと良い方法を思いついた人は、その方法を実装してみて下さい。

* 元と同じ太さで赤枠を表示してもあまり目立たないので、__赤枠の太さを太くして表示する__
* 暗く表示しない場合の赤枠の太さを元のままにすると、__見た目が不自然__ だったので、赤枠の太さは __常に太くして表示する__

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

* __7 ~ 9 行目__：選択されたノードに対して太さが 2 の赤枠を表示する

```python
 1  def update_gui(self):
元と同じなので省略
 2      for rect, node in self.mbtree.nodes_by_rect.items():
 3          index = node.score_index if self.isscore else node.id
 4          if index > self.play.value:
 5              self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
 6                                                   height=rect.height, fc="black", alpha=0.5))
 7         if node is self.selectednode:
 8             self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
 9                                height=rect.height, ec="red", fill=False, lw=2))
元と同じなので省略
10
11   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.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.mbtree.algo == "bf":
        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():
        index = node.score_index if self.isscore else node.id
        if index > 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))
        if node is self.selectednode:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
                                                     height=rect.height, ec="red", fill=False, lw=2))

    disabled = self.play.value == 0
    self.set_button_status(self.prev_button, disabled=disabled)
    disabled = self.play.value == self.nodenum - 1
    self.set_button_status(self.next_button, disabled=disabled)

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

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

```diff_python
def update_gui(self):
元と同じなので省略
    for rect, node in self.mbtree.nodes_by_rect.items():
        index = node.score_index if self.isscore else node.id
        if index > 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))
+       if node is self.selectednode:
+           self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
+                                                height=rect.height, ec="red", fill=False, lw=2))
元と同じなので省略

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように赤枠が明るい色で太く表示されるようになります。

```python
mbtree_anim = Mbtree_Anim(mbtree_df, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/cda02104-44e9-c1e4-299b-c2f9b64d306f.png" width="500">

# 幅優先アルゴリズムによる評価値の計算の過程の視覚化

せっかくなので、__幅優先アルゴリズム__ による評価値の計算の過程の視覚化も行うことにします。幅優先アルゴリズムでの評価値の計算は、以下の手順で行われます。

* 深さの浅い順に各深さのノードの一覧を計算する
* 深さの深い順に各深さのノードの評価値を計算する

__前者の処理は、`create_tree_by_bf` で行われている__ ので、__`calc_score_by_bf`__ では __後者の処理のみ__ を行っていますが、幅優先アルゴリズムによる評価値の過程の視覚化では、__前者の処理も視覚化を行う必要があります__。

__前者の処理__ で処理が行われる __ノードの順番__ は、幅優先アルゴリズムでゲーム木の __ノードを作成する順番と全く同じ__ なので、その順番は幅優先アルゴリズムで作成した Mbtree の __`nodelist` 属性に代入されています__。従って、前者の処理で行われるノードに対する処理の順番の計算は、__`nodelist_by_score`__ に __`nodelist` の値をコピーすれば良い__ ことがわかります。

__後者の処理__ では、ノードの処理を行う際に __必ずそのノードの評価値が計算__ されます。そのため、後者の処理で __`nodelist_by_score`__ に登録するノードは __すべて評価値が計算されたことを表すノード__ になります。

上記から、`calc_score_by_bf` は下記のプログラムのように修正します。

* __2 行目__：`nodelist` 属性の list を、[スライス表記](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%AB%E3%82%88%E3%82%8B%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E8%A4%87%E8%A3%BD)で `nodelist_by_score` にコピーする
* __18 行目__：ノードの評価値を計算した後で、`nodelist_by_score` にそのノードを追加する
* __19 行目__：追加したノードのインデックスをノードの `score_index` 属性に代入する

```python
 1  def calc_score_by_bf(self):
 2      self.nodelist_by_score = self.nodelist[:]
 3      for nodelist in reversed(self.nodelist_by_depth):
 4          for node in nodelist:
 5              if node.mb.status == Marubatsu.CIRCLE:
 6                  node.score = 1
 7              elif node.mb.status == Marubatsu.DRAW:
 8                  node.score = 0
 9              elif node.mb.status == Marubatsu.CROSS:
10                  node.score = -1
11              else:
12                  score_list = [childnode.score for childnode in node.children]
13                  if node.mb.move_count % 2 == 0:
14                      score = max(score_list)
15                  else:
16                      score = min(score_list)
17                  node.score = score
18              self.nodelist_by_score.append(node)
19              node.score_index = len(self.nodelist_by_score) - 1
20    
21  Mbtree.calc_score_by_bf = calc_score_by_bf
```

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

```python
def calc_score_by_bf(self):
    self.nodelist_by_score = self.nodelist[:]
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
                score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score
            self.nodelist_by_score.append(node)
            node.score_index = len(self.nodelist_by_score) - 1
    
Mbtree.calc_score_by_bf = calc_score_by_bf
```
</details>

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

```diff_python
def calc_score_by_bf(self):
+   self.nodelist_by_score = self.nodelist[:]
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
                score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score
+           self.nodelist_by_score.append(node)
+           node.score_index = len(self.nodelist_by_score) - 1
    
Mbtree.calc_score_by_bf = calc_score_by_bf
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果のように幅優先アルゴリズムによる評価値の計算の過程のアニメーションが表示されるようになります。

```python
mbtree_bf = Mbtree.load("bfscore")
mbtree_bf.calc_score_by_bf()
mbtree_anim = Mbtree_Anim(mbtree_bf, isscore=True)
```

前半の 0 ~ 549945 フレームでは下図のように、深さの浅い順にノードの処理が行われます。また、その際に評価値が計算されることはありません。

実行結果（0 ~ 30 フレームまでのアニメーションの繰り返しです）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4bcaa1e2-cabb-0c4b-3b8e-3b51d6384fed.gif" width="500">

後半の 549946 フレーム以降では、深さの深い順に、評価値の計算を行いながらノードの処理が行われます。なお、フレームを表す IntSlider の値をクリックすることで、キーボードから IntSlider の値を直接編集することができるので、実際に 549946 フレームの前後のフレームを表示して確認してみて下さい。

実行結果（549946 ~ 549976 フレームまでのアニメーションの繰り返しです）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/32fbb0e0-bf1d-decd-cebb-d0d1aa927038.gif" width="500">

# ファイルの保存

最後に、下記のプログラムで `mbtree_bf` と `mbtree_df` のデータをファイルに保存します。なお、下記では、今回の marubatsu.ipynb のプログラムを実行する際に必要となるので、`"bfscore_new"` という名前で保存しましたが、古い `"bfscore.mbtree"` と `"dfscore.mbtree"` のファイルはもう必要がないので、次回以降の記事では、今回保存した `"bfscore_new.mbtree"` のファイル名を `"bfscore.mbtree"` に変更することにします。


```python
mbtree_bf.save("bfscore_new")
mbtree_df.save("dfscore_new")
```

実行結果

```
save completed.
save completed.
```

# 互換性の確認

今回の Mbtree_Anim の修正によって、ゲーム木の生成の過程のアニメーションが正しく動作しなくなっている可能性があるので、下記のプログラムで確認します。実行結果は省略しますが、正しく動作することが確認できます。

```python
mbtree_anim = Mbtree_Anim(mbtree_bf)
mbtree_anim = Mbtree_Anim(mbtree_df)
```

# 今回の記事のまとめ

今回の記事では、深さ優先アルゴリズムと、幅優先アルゴリズムの両方で、ゲーム木の評価値を計算する過程をアニメーションで視覚化しました。

次回の記事では、

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

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/106/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [tree_new.py](https://github.com/ysgeso/marubatsu/blob/master/106/tree_new.py)  | 今回の記事で更新した tree.py |
| [bfscore_new.mbtree](https://github.com/ysgeso/marubatsu/blob/master/106/bfscore_new.mbtree)  | 幅優先探索アルゴリズムで作成した、評価値を含むゲーム木の保存ファイル |
| [dfscore_new.mbtree](https://github.com/ysgeso/marubatsu/blob/master/106/dfscore_new.mbtree)  | 深さ優先探索アルゴリズムで作成した、評価値を含むゲーム木の保存ファイル |

# 次回の記事

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