Pythonで〇×ゲームのAIを一から作成する　その143　Mbtree_Anim のアニメーションの各フレームで行われる処理の視覚化

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/1468226fe9a96ae6a55c

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

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

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

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

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

# アニメーションの各フレームで行われる処理の視覚化

前回の記事では、下図のように数直線を使って α 値、β 値、子ノードの評価値の視覚化を行いましたが、[前回の記事](https://qiita.com/ysgeso/items/1468226fe9a96ae6a55c#%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%81%AE%E5%8B%95%E4%BD%9C%E3%81%AE%E7%A2%BA%E8%AA%8D)で説明したように、α 値や β 値の値が更新された際の理由がわかりづらいという問題がありました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a7d6081f-7342-6286-a960-69a0979cbf4d.png" width="500">

今回の記事では __アニメーションの各フレームで行われる処理__ を __わかりやすく表示__ するための改良を行います。

## max ノードと min ノードで行われる処理の分類

[αβ 法](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E7%A5%96%E5%85%88%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F-%CE%B1%CE%B2-%E6%B3%95)では max ノードで子ノードの評価値がが計算された際に、下記の処理を行います。

1. __β 値 ≦ 子ノードの評価値__ の場合
    * α 値を子ノードの評価値に更新する
    * β 狩りによって、残りの子ノードの評価値の計算処理を省略する
2. __α 値 < 子ノードの評価値 < β 値__ の場合
    * α 値を子ノードの評価値に更新する
    * 次の子ノードの評価値の計算処理を行う
3. __子ノードの評価値 ≦ α 値__
    * α 値は更新しない
    * 次の子ノードの評価値の計算処理を行う

上記の 1、2 はいずれも α 値を子ノードの評価値に更新する処理を行うので、__α 値__ を子ノードの評価値に __更新する範囲__ は「__α 値 < 子ノードの評価値__」であることがわかります。

また、min ノードでは下記のようになります。

1. __子ノードの評価値 ≦ α 値__ の場合
    * β 値を子ノードの評価値に更新する
    * α 狩りによって、残りの子ノードの評価値の計算処理を省略する
2. __α 値 < 子ノードの評価値 < β 値__ の場合
    * β 値を子ノードの評価値に更新する
    * 次の子ノードの評価値の計算処理を行う
3. __β 値 ≦ 子ノードの評価値__ の場合
    * β 値は更新しない
    * 次の子ノードの評価値の計算処理を行う

max ノードの場合と同様の理由で __min ノードの場合__ は、__β 値__ を子ノードの評価値に __更新する範囲__ は「__子ノードの評価値 < β 値__」であることがわかります。

## 範囲ごとの色分け

数直線の図で上記の __max ノード__ の場合の __範囲の色を分けて塗る__ と下図のようになります。なお、__水色と黄色の境界線__ は __水色__、__黄色と灰色の境界線__ は __灰色の範囲__ になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e2de0288-a64f-3c00-cda1-b280117f2441.png" width="500">

__水色__ が上記の 1 の __β 狩りを行う範囲__、__黄色__ が上記の 2 の __α 値を更新する範囲__、__灰色__ が上記の 3 の __α 値を更新しない範囲__ を表します。3 種類の処理を行う __範囲を色分けする__ ことで、緑の円の __子ノードの評価値__ が上図のように __どの範囲にあるかが明確__ になり、上記の 3 種類の __どの処理が行われるかが一目でわかる__ ようになります。

min ノードの場合も色分けを行う範囲は変わりませんが、下図のように __枝狩りを行う範囲を水色__、__β 値を更新しない範囲を灰色__ で __色分けを統一__ したほうがわかりやすいでしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/15133076-e46c-6045-76b8-d35d97ca9598.png" width="500">


そこで、本記事では下記の表のように範囲の色分けを行うことにします。

| 色 | 意味 |
|:--|:--|
| __水色__ | 枝狩り（α 狩りまたは β 狩り）が行われる範囲  |
| __黄色__ | α 値または β 値を更新する範囲  |
| __灰色__ | α 値または β 値を更新しない範囲  |

### Marubatsu_GUI クラスの `update_ab` メソッドの修正

上記のような表示が行われるように、__Marubatsu_GUI__ クラス の __`update_ab`__ メソッドを下記のプログラムのように修正します。なお、下記のプログラムでは上記の範囲に色を塗る修正に加えて、[ゲーム木の上部に表示される α 値や β 値と同様](https://qiita.com/ysgeso/items/a206729687dfd28bfa9e#%E8%A8%88%E7%AE%97%E4%B8%AD%E3%81%AE-%CE%B1-%E5%80%A4-%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E6%98%8E%E7%A2%BA%E5%8C%96)に、__更新の対象__ となる α 値または β 値の __注釈の色を赤色で表示__ するという修正も行っています。

* __8 ~ 10 行目__：max ノードであるかどうかの判定は、この後で何度も行う必要があるので、__`maxnode`__ という変数に max ノードである場合に `True`、そうでない場合に `False` を代入し、それを使って `acolor` と `bcolor` の値を代入するように修正する
* __13、14 行目__：__範囲の塗りつぶし__ を行う際には、α 値の値ではなく、__α 値を数直線上に描画する座標の値が必要__ になるので、その値を表す __[`alphacoord` や `betacoord`](https://qiita.com/ysgeso/items/1468226fe9a96ae6a55c#%E3%81%9D%E3%82%8C%E3%81%9E%E3%82%8C%E3%81%AE%E5%80%A4%E3%82%92%E8%A1%A8%E3%81%99%E3%83%9E%E3%83%BC%E3%82%AB%E3%83%BC%E3%81%AE%E6%8F%8F%E7%94%BB)__ の __計算の処理__ を __この場所に移動__ する必要がある
* __16 ~ 19 行目__：負の無限大を表す座標（minus_inf）から α 値を表す座標（alphacoord）までの範囲の長方形の塗りつぶしの色を 16 行目で計算し、17 ~ 19 行目でその色でその範囲を塗りつぶす。塗りつぶす長方形の y 座標の範囲は筆者が試行錯誤して設定した値なので自由に変更しても良い
* __20 ~ 26 行目__：上記と同様の方法で残りの範囲を塗りつぶす。なお、α 値から β 値までの範囲は常に黄色で塗りつぶせばよいので色を計算する必要はない
* 上記の __塗りつぶしの処理__ は、28 行目以降の __数直線などを描画する前に行わないと__、数直線の上に灰色の長方形などが描画されてしまうため、__数直線が見えなくなってしまう__ 点に注意すること
* __32、35 行目__：α 値の注釈の色（β 値の注釈も同様）は、9 行目で計算済なので、キーワード引数 `c=acolor` を記述してその色で α 値の注釈が描画されるように修正する

```python
 1  from marubatsu import Marubatsu
 2  from tree import Mbtree_Anim
 3  import matplotlib.patches as patches
 4
 5  def update_ab(self):
 6      fontsize = 70 * self.size
 7      alpha, beta, score, message = self.mbtree.ablist_by_score[self.play.value]
 8      maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
 9      acolor = "red" if maxnode else "black"
10      bcolor = "black" if maxnode else "red"
元と同じなので省略
11      minus_inf = -3
12      plus_inf = 4   
13      alphacoord = max(minus_inf, alpha)
14      betacoord = min(plus_inf, beta)
15
16      color = "lightgray" if maxnode else "aqua"
17      rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf, 
18                               height=1, fc=color)
19      self.abax.add_patch(rect)
20      rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord, 
21                               height=1, fc="yellow")
22      self.abax.add_patch(rect)
23      color = "aqua" if maxnode else "lightgray"
24      rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
25                               height=1, fc=color)
26      self.abax.add_patch(rect)
27
28      self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
元と同じなので省略
29      arrowprops = { "arrowstyle": "->"}
30      self.abax.plot(alphacoord, 0, "or")
31      self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
32                         arrowprops=arrowprops, ha="center", c=acolor)
33      self.abax.plot(betacoord, 0, "ob")
34      self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
35                         arrowprops=arrowprops, ha="center", c=bcolor)
元と同じなので省略
36        
37  Mbtree_Anim.update_ab = update_ab
```

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

```python
from marubatsu import Marubatsu
from tree import Mbtree_Anim
import matplotlib.patches as patches

def update_ab(self):
    fontsize = 70 * self.size
    alpha, beta, score, message = self.mbtree.ablist_by_score[self.play.value]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    acolor = "red" if maxnode else "black"
    bcolor = "black" if maxnode else "red"
    self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
    self.ax.text(9, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
    self.ax.text(19, -1, message, fontsize=fontsize)             
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 14)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3
    plus_inf = 4   
    alphacoord = max(minus_inf, alpha)
    betacoord = min(plus_inf, beta)
    
    color = "lightgray" if maxnode else "aqua"
    rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf,
                             height=1, fc=color)
    self.abax.add_patch(rect)
    rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord,
                             height=1, fc="yellow")
    self.abax.add_patch(rect)
    color = "aqua" if maxnode else "lightgray"
    rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
                             height=1, fc=color)
    self.abax.add_patch(rect)

    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")
        
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
                       arrowprops=arrowprops, ha="center", c=acolor)
    self.abax.plot(betacoord, 0, "ob")
    self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
                       arrowprops=arrowprops, ha="center", c=bcolor)
    if score is not None:
        self.abax.plot(score, 0, "og")
        self.abax.annotate(f"score = {score}", xy=(score, 0),
                           xytext=((minus_inf + plus_inf) / 2, 1), 
                           arrowprops=arrowprops, ha="center")
        
Mbtree_Anim.update_ab = update_ab
```
</details>

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

```diff_python
from marubatsu import Marubatsu
from tree import Mbtree_Anim
import matplotlib.patches as patches

def update_ab(self):
    fontsize = 70 * self.size
    alpha, beta, score, message = self.mbtree.ablist_by_score[self.play.value]
+   maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
-   acolor = "red" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "black"
+   acolor = "red" if maxnode else "black"
-   bcolor = "black" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "red"
+   bcolor = "black" if maxnode else "red"    
元と同じなので省略
    minus_inf = -3
    plus_inf = 4   
+   alphacoord = max(minus_inf, alpha)
+   betacoord = min(plus_inf, beta)

+   color = "lightgray" if maxnode else "aqua"
+   rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf,
+                            height=1, fc=color)
+   self.abax.add_patch(rect)
+   rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord,
+                            height=1, fc="yellow")
+   self.abax.add_patch(rect)
+   color = "aqua" if maxnode else "lightgray"
+   rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
+                            height=1, fc=color)
+   self.abax.add_patch(rect)

    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
元と同じなので省略
-   alphacoord = max(minus_inf, alpha)
-   betacoord = min(plus_inf, beta)
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
-                      arrowprops=arrowprops, ha="center")
+                      arrowprops=arrowprops, ha="center", c=acolor)
    self.abax.plot(betacoord, 0, "ob")
    self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
-                      arrowprops=arrowprops, ha="center")
+                      arrowprops=arrowprops, ha="center", c=bcolor)
元と同じなので省略
        
Mbtree_Anim.update_ab = update_ab
```
</details>

上記の修正後に下記のプログラムで αβ 法で評価値を計算した mbtree に対して Mbtree_Anim を実行すると、実行結果のように __数直線上の範囲が塗りつぶさ__、__更新の対象__ となる α 値が __赤色で描画される__ ことが確認できます。

```python
from tree import Mbtree

mbtree = Mbtree(algo="df")
mbtree.calc_score_by_ab(mbtree.root)
Mbtree_Anim(mbtree, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/498ba230-35f1-3f25-55bb-e1d96b6379ed.png" width="500">

上図では黄色の範囲しか描画されませんが、下図の 50 フレーム目の __max ノード__ では __3 つの範囲が正しい色で描画__ され、__α 値の注釈が赤色__ で正しく描画されることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/605f69c1-e1f3-52dc-174b-11e4f6506c77.png" width="500">

また、その次の下図の 51 フレーム目の __min ノード__ では 3 つの __範囲の色の順番が max ノードの逆__ になり、__β 値の注釈が赤色__ で正しく描画されることが確認できます。


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6dacb162-7e01-ee87-a332-55148bbd136b.png" width="500">

:::note
塗りつぶしの処理を for 文で下記のプログラムのようにまとめることもできます。

* __1 行目__：3 つの範囲の色を要素として持つ list を変数に代入する
* __2 行目__：負の無限大の座標、α 値の座標、β 値の座標、正の無限大の座標を要素として持つ list を変数に代入する
* __3 行目__：3 つの範囲を描画するために、0 から 2 までの整数の繰り返し処理を行う
* __4 行目__：`i` 番の塗りつぶしの幅を計算する
* __5 行目__：`i` 番の塗りつぶしの色を計算する。なお、× の手番では `i` が `0`、`1`、`2` の場合の色はそれぞれ `color[2]`、`color[1]`、`color[0]` になるので、`color[2 - i]` という式で計算できる
* __6 ~ 8 行目__：`i` 番の長方形を `numlist`、`colorlist` の `i` 番の要素と 4 行目で計算した幅を利用して描画する

```python
1  colorlist = ["lightgray", "yellow", "aqua"]
2  numlist = [minus_inf, alphacoord, betacoord, plus_inf]
3  for i in range(3):
4      width = numlist[i + 1] - numlist[i]
5      color = colorlist[i] if maxnode else colorlist[2 - i]
6      rect = patches.Rectangle(xy=(numlist[i], -0.5), width=width, height=1,
7                               fc=color)
8      self.abax.add_patch(rect)
```

上記のようにまとめることで、プログラムが短くなる、色を変更する際に 1 行目だけを修正すれば良くなるなどの利点が得られますが、プログラムがわかりづらくなるという欠点が生じるので、上記のプログラムは本記事では採用しません。

塗りつぶしの種類がもっと多くなった場合や、それぞれでもっと複雑な処理を行う必要がある場合はこのような方法を採用したほうが良いでしょう。実際に、この後で上記のような方法でプログラムを記述することにします。
:::

## 塗りつぶしの色の説明の描画

それぞれの __塗りつぶしの色が何を意味するか__ が __わかりづらい__ ので、__その説明を表示__ したほうが良いでしょう。また、子ノードの評価値が計算された際に、__どの処理が行われるかを明確にする__ ために、範囲の __説明文の色を赤色で表示__ するとさらにわかりやすくなります。

具体的には、下図のような説明を数直線の右に描画します。もっとわかりやすい表示方法を思いついた人は自由に変更して下さい。

* 1 行目にゲーム木の赤枠の選択中の「__ノードの深さとノードの種類__」を表示する
* 2 ~ 4 行目にそれぞれの範囲の色の説明を表示する
* 下図のように __子ノードの評価値が表示される場合__ は、その __評価値を含む範囲の文字を赤色で表示__ する
* __子ノードの評価値が表示されない場合__ や、子ノードの評価値の __範囲でない__ 文字は __黒色で表示__ する

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2298d91e-38a3-4d97-0936-61160bbbdd93.png" width="500">

下記はそのように __Marubastu_Anim__ クラスの __`update_ab`__ を修正したプログラムです。__`facecolorlist` など__ に代入された __list の要素__ は、__2 ~ 4 行目の表示に関するデータ__ を表します。また、2 ~ 4 行目の描画処理を 1 つずつ別々に記述すると、プログラムがかなり長くなるので、先程のノートで紹介した方法で for 文を使って行うように工夫しました。

* __2 行目__：右に表示する、範囲の色を表す list を変数に代入する
* __3 行目__：右に表示する、範囲の説明文の文字の色を表す list を変数に代入する。__初期値__ として __すべての要素__ を黒色を表す __`"black"`__ とし、__この後で__ 赤く表示する必要がある行に対応する要素を __`"red"` に変更__ する
* __4 ~ 14 行目__：max ノードの場合の処理を行う
* __5 行目__：1 行目に表示する「ノードの深さと種類」を表す文字列を変数に代入する
* __6、7 行目__：右に表示する、範囲の説明文を表す list を変数に代入する
* __8 ~ 14 行目__：子ノードの評価値が `score` に代入されている場合に、__`score` を含む範囲に対応する `textcolorlist` の要素を `"red"` に変更__ する
* __15 ~ 25 行目__：min ノードの場合に上記と同様の処理を行う
* __27 行目__：右の 1 行目の文字列の描画を行う
* __28 ~ 32 行目__：上記で計算したデータを使って、右の 2 ~ 4 行目の描画を行う。29、30 行目で 長方形の __y 座標に `0.3 - i * 0.7` を記述__ することで、__1 行ごとに 0.7 ずつ下にずらして長方形が描画__ される。32 行目で範囲の説明文を描画する y 座標も同様の方法で計算する。なお、色のついた長方形と説明文の描画位置は筆者が試行錯誤して調整したものなので、別のレイアウトで描画を行いたい場合は自由に変更しても良い

```python
 1  def update_ab(self):
元と同じなので省略
 2      facecolorlist = ["aqua", "yellow", "lightgray"]
 3      textcolorlist = ["black", "black", "black"]
 4      if maxnode:
 5          nodetype = f"深さ {self.selectednode.mb.move_count} max node"
 6          textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)",
 7                      "α 値の更新なし (score ≦ α)"]
 8          if score is not None :
 9              if beta <= score:
10                 textcolorlist[0] = "red"
11              elif alpha < score:
12                 textcolorlist[1] = "red"
13              else:
14                 textcolorlist[2] = "red"
15      else:
16          nodetype = f"深さ {self.selectednode.mb.move_count} min node"
17          textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)",
18                      "β 値の更新なし (score ≦ β)"]
19          if score is not None :
20              if score <= alpha:
21                 textcolorlist[0] = "red"
22              elif score < beta:
23                 textcolorlist[1] = "red"
24              else:
25                textcolorlist[2] = "red"
26  
27      self.abax.text(6, 1, nodetype)   
28      for i in range(3):
29          rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5,
30                                   fc=facecolorlist[i])
31          self.abax.add_patch(rect)
32          self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
33         
34  Mbtree_Anim.update_ab = update_ab
```

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

```python
def update_ab(self):
    fontsize = 70 * self.size
    alpha, beta, score, message = self.mbtree.ablist_by_score[self.play.value]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    acolor = "red" if maxnode else "black"
    bcolor = "black" if maxnode else "red"
    self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
    self.ax.text(9, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
    self.ax.text(19, -1, message, fontsize=fontsize)             
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 14)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3
    plus_inf = 4   
    alphacoord = max(minus_inf, alpha)
    betacoord = min(plus_inf, beta)
    
    color = "lightgray" if maxnode else "aqua"
    rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf,
                             height=1, fc=color)
    self.abax.add_patch(rect)
    rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord,
                             height=1, fc="yellow")
    self.abax.add_patch(rect)
    color = "aqua" if maxnode else "lightgray"
    rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
                             height=1, fc=color)
    self.abax.add_patch(rect)

    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")
        
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
                       arrowprops=arrowprops, ha="center", c=acolor)
    self.abax.plot(betacoord, 0, "ob")
    self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
                       arrowprops=arrowprops, ha="center", c=bcolor)
    if score is not None:
        self.abax.plot(score, 0, "og")
        self.abax.annotate(f"score = {score}", xy=(score, 0),
                           xytext=((minus_inf + plus_inf) / 2, 1), 
                           arrowprops=arrowprops, ha="center")
              
    facecolorlist = ["aqua", "yellow", "lightgray"]
    textcolorlist = ["black", "black", "black"]
    if maxnode:
        nodetype = f"深さ {self.selectednode.mb.move_count} max node"
        textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)",
                    "α 値の更新なし (score ≦ α)"]
        if score is not None :
            if beta <= score:
               textcolorlist[0] = "red"
            elif alpha < score:
               textcolorlist[1] = "red"
            else:
               textcolorlist[2] = "red"
    else:
        nodetype = f"深さ {self.selectednode.mb.move_count} min node"
        textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)",
                    "β 値の更新なし (score ≦ β)"]
        if score is not None :
            if score <= alpha:
               textcolorlist[0] = "red"
            elif score < beta:
               textcolorlist[1] = "red"
            else:
               textcolorlist[2] = "red"

    self.abax.text(6, 1, nodetype)   
    for i in range(3):
        rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5, fc=facecolorlist[i])
        self.abax.add_patch(rect)
        self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
        
Mbtree_Anim.update_ab = update_ab
```
</details>

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

```diff_python
def update_ab(self):
元と同じなので省略
+   facecolorlist = ["aqua", "yellow", "lightgray"]
+   textcolorlist = ["black", "black", "black"]
+   if maxnode:
+       nodetype = f"深さ {self.selectednode.mb.move_count} max node"
+       textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)",
+                   "α 値の更新なし (score ≦ α)"]
+       if score is not None :
+           if beta <= score:
+              textcolorlist[0] = "red"
+           elif alpha < score:
+              textcolorlist[1] = "red"
+           else:
+              textcolorlist[2] = "red"
+   else:
+       nodetype = f"深さ {self.selectednode.mb.move_count} min node"
+       textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)",
+                   "β 値の更新なし (score ≦ β)"]
+       if score is not None :
+           if score <= alpha:
+              textcolorlist[0] = "red"
+           elif score < beta:
+              textcolorlist[1] = "red"
+           else:
+              textcolorlist[2] = "red"

+   self.abax.text(6, 1, nodetype)   
+   for i in range(3):
+       rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5,
+                                fc=facecolorlist[i])
+       self.abax.add_patch(rect)
+       self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
        
Mbtree_Anim.update_ab = update_ab
```
</details>

## 表示の確認

上記の修正後に下記のプログラムを実行し、__いくつかのフレームを表示__ してプログラムが __正しく動作するかどうかを確認__ します。

具体的には以下のフレームでの処理を確認します。

* ノードの処理が開始されたフレーム
* 枝狩りが行われるフレーム
* 枝狩りが行われなかった場合に α 値または β 値が更新されるフレーム
* α 値または β 値が更新されないフレーム
* ゲームの決着がついた局面の評価値が計算されるフレーム

```python
Mbtree_Anim(mbtree, isscore=True)
```

### ノードの処理が開始されたフレームの表示の確認

下記は最初の 0 フレーム目の __max ノード__ の __処理を開始するフレーム__ の図です。以下のように正しい描画が行われていることが確認できます。なお、実際に描画される内容をすべて表示すると図が大きくなりすぎるので、重要でない部分は図から省略します。

* α 値の注釈が赤色で描画されている
* 右の 1 行目に「深さ 0 max node」が表示されている
* 右の 2 ~ 4 行目に、max ノードの場合の説明が表示されている
* このフレームでは子ノードの評価値が計算されていないので、右の 2 ~ 4 行目の文字の色はすべて黒色で表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/65a4bece-319f-db1e-f8fc-f87cd262b9ab.png" width="350">

下記はその次の 1 フレーム目の __min ノード__ の __処理を開始するフレーム__ の図です。以下のように正しい描画が行われていることが確認できます。

* β 値の注釈が赤色で描画されている
* 右の 1 行目に「深さ 1 min node」が表示されている
* 右の 2 ~ 4 行目に、min ノードの場合の説明が表示されている
* このフレームでは子ノードの評価値が計算されていないので、右の 2 ~ 4 行目の文字の色はすべて黒色で表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f4f75c47-1508-187d-0cd3-7b7c69ea0a8a.png" width="350">

### 枝狩りを行うフレームの表示の確認

下記は 18 フレーム目の __min ノード__ の __α 狩りを行う直前のフレーム__ の図です。以下のように正しい描画が行われていることが確認できます。

* β 値の注釈が赤色で描画されている
* 右の 1 行目に「深さ 7 min node」が表示されている
* 右の 2 ~ 4 行目に、min ノードの場合の説明が表示されている
* このフレームでは子ノードの評価値が計算されており、子ノードの評価値は水色の α 狩りを行う範囲[^1]なので、__2 行目の水色の説明文が赤字で表示__ されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7a0b9f94-3bf1-6f88-7d2a-1b2ccda03394.png" width="500">

下記はその次の 19 フレーム目の図で、__α 狩りが行われた結果__、__β 値__ が上図の __子ノードの評価値の値に更新されている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/490df8cf-2b68-0ac4-6db3-f714974dc46c.png" width="500">

下記はその次の 20 フレーム目の図で、__α 狩りが行われた結果__、赤枠の残りの __子孫ノードの色が暗い__ ことから、__それらのノードの評価値を計算する処理を行わず__ に赤枠のノードの __評価値が確定__ したことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b4a6e385-6bab-5445-2081-703b82b6a023.png" width="500">

説明は上記とほぼ同じなので省略しますが、下記の 97 フレーム目の __max ノード__ の __β 狩りを行う直前のフレーム__ の図と、その後の 2 フレームの図から正しい描画が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/04e6652b-2a72-1b03-40ef-7466a1869331.png" width="500">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ae87d27c-2298-bbea-add5-b8e574278649.png" width="500">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8186457f-2516-9738-1604-6afc4fff9718.png" width="500">

### 枝狩りが行われずに α 値 や β 値が更新されるフレームの表示の確認

下記は 9 フレーム目の __max ノード__ の図です。以下のように正しい描画が行われていることが確認できます。

* α 値の注釈が赤色で描画されている
* 右の 1 行目に「深さ 6 のmax node」が表示されている
* 右の 2 ~ 4 行目に、max ノード の場合の説明が表示されている
* このフレームでは子ノードの評価値が計算されており、子ノードの評価値は黄色の α 値を更新する範囲なので、__3 行目の黄色の説明文が赤字で表示__ されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c54d52cf-b24c-b1a0-0aa7-85826fd2ca24.png" width="500">

下記はその次の 10 フレーム目の図で、__α 値が__ 上図の __子ノードの評価値の値に更新__ されていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bf9e6ff0-8ee7-e11e-502c-cb8ca6dd9276.png" width="500">

説明は上記とほぼ同じなので省略しますが、下記の 28 フレーム目の __min ノード__ の __β 値を更新する直前のフレーム__ の図と、その次の __β 値が更新されるフレーム__ の図から正しい描画が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9ee8eed6-2376-5e35-fef4-74dd0d215d64.png" width="400">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/87938858-bed0-5a23-3d00-632ab14635bf.png" width="400">

### α 値や β 値が更新されないフレームの表示の確認

下記は 15 フレーム目の __max ノード__ の図です。以下のように正しい描画が行われていることが確認できます。

* α 値の注釈が赤色で描画されている
* 右の 1 行目に「深さ 8 max node」が表示されている
* 右の 2 ~ 4 行目に、max ノードの場合の説明が表示されている
* このフレームでは子ノードの評価値が計算されており、子ノードの評価値は灰色の α 値を更新しない範囲[^2]なので、__4 行目の灰色の説明文が赤字で表示__ されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/49422f6c-5697-def8-30d3-0cf875a715c7.png" width="500">

下記はその次の 16 フレーム目の図で、__α 値__ が __変化していない__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/65311e4c-0043-7bd5-d0c4-7730b7700c9d.png" width="500">

説明は上記とほぼ同じなので省略しますが、下記の 38 フレーム目の __min ノード__ の __β 値を更新しない直前のフレーム__ の図と、__その次のフレーム__ の図から正しい描画が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/028bff01-4a50-111e-a35f-61ffb8ea947d.png" width="500">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/10e25975-9fdf-11cc-06bc-36856909d966.png" width="500">

### ゲームの決着がついた局面の評価値が計算されるフレームの確認

下記は 8 フレーム目の __min ノード__ で、__決着がついた局面の評価値が確定したフレーム__ の図です。__min ノード__ では評価値が確定したフレームの __β 値がそのフレームの評価値__ となりますが、__β 値が -inf のまま 1 に更新されない__ という __問題があることが確認__ できました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/33af3884-2db9-7ab1-d8db-9cb6e31f1e5e.png" width="500">

下記は 137 フレーム目の __max ノード__ で、__決着がついた局面の評価値が確定したフレーム__ の図で、上記と同様に __α 値が 1 のまま -1 更新されない__ という __問題があります__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b98c7d2e-007f-8e4e-c39b-b56e286aa654.png" width="500">

この問題については、この後でフレームで行われる処理の明確化を行う際に修正します。

余裕がある方は他のフレームでどのように表示されるかどうかを確認してみて下さい。

## フレームで行われる処理の明確化

上記でかなりわかりやすくなったのではないかと思いますが、__子ノードの評価値が表示されないフレーム__ で行われる __処理の区別__ が下記のように __わかりづらい__ という問題があります。

[以前の記事](https://qiita.com/ysgeso/items/a206729687dfd28bfa9e#%E8%A1%8C%E3%81%86%E5%87%A6%E7%90%86%E3%82%92%E8%A1%A8%E3%81%99%E3%83%A1%E3%83%83%E3%82%BB%E3%83%BC%E3%82%B8%E3%81%AE%E8%A1%A8%E7%A4%BA)では下記の表のように __フレームで行われた処理__ を __9 種類に分類__ しました。

|| 行われた処理 | メッセージの例 |
|:-:|:--|:--|
|①| __ノードの処理が開始__<br>(`calc_ab_score` が呼ばれた直後）  | このノードの処理の開始  |
|②| __子ノードの評価値の計算の直後__ |  child score = 0   |
|③| __max ノードで β 狩りを行う__ | child score = 0 ≧ -1(β 値) による β 狩り  |
|④| __max ノードで α 値を更新する__  | child score = 0 > -inf(α 値) による α 値の更新  |
|⑤| __max ノードで α 値を更新しない__  | child score = 0 ≦ 1(α 値) なので α 値は更新しない |
|⑥| __min ノードで α 狩りを行う__ | child score = 0 ≦ 1(α 値) による α 狩り  |
|⑦| __min ノードで β 値を更新する__  | child score = 0 < inf(β 値) による β 値の更新  |
|⑧| __min ノードで β 値を更新しない__  | child score = 0 ≧ -1(β 値) なので β 値は更新しない |
|⑨| __ノードの処理が終了__ | このノードの評価値が 0 で確定 |

今回の記事ではこの表の __② のフレーム__ に対して、__数直線上に子ノードの評価値を表示__ し、右の 2 ~ 4 行目の __その次のフレームで行う処理の説明文を赤字で表示__ するという工夫を行ないましたが、__それ以外のフレームでの表示__ は __全く同じ__ なので __区別がつきません__[^3]。

上記の表の __③ ~ ⑧ のフレーム__ は、いずれも ② のフレームの __次のフレームで行われる処理__ を表しているので、__それらをまとめて__ 下記の表の __4 種類の状態を区別できるようにする__ ことにします。なお、③ ~ ⑧ に対する説明文は「α 値の処理」のように表記しますが、α 値または β 値を __更新しないという処理も含みます__。

| 行われた処理 | 右の 1 行目の表示例 | 背景色 |
|:--|:--|:--|
| __① ノードの処理が開始__  | 深さ 0 max node 処理の開始  | 白 |
| __② 子ノードの評価値の計算の直後__  |  深さ 0 max node 子ノードの評価値 | 薄黄色 |
| __③ ~ ⑧ α 値または β 値に対する処理__  | 深さ 0 max node α 値の処理  | 薄水色 |
| __⑨ ノードの処理が終了して評価値が確定__  | 深さ 0 max node 評価値の確定 | 薄紫色 |

具体的には数直線の __右の 1 行目__ に __上の表のような表示__ を行います。また、文字の表示だけではわかりづらいので、__Figure の背景色__ を __上の表のように塗りつぶす__ ことで、__現在の状態が一目でわかる__ ようにします。

また、上記の表示を行うことで、__ゲーム木の上に表示していた α 値、β 値、メッセージの表示__ はもう __必要がなくなる__ ので、__それらの表示を削除する__ ことにします。

:::note
③ ~ ⑧ のそれぞれに対して別のメッセージと、別の背景色を設定することもできますが、__色が多すぎる__ と __かえってわかりづらくなる__ という欠点が生じます。
:::

### Mbtree クラスの `calc_node_by_ab` の修正

Mbtree_Anim で上記のような表示を行うためには、それぞれのアニメーションのフレームで __そのフレームが上記のどの状態であるかを記録しておく__ 必要があります。現状では、アニメーションのフレームの情報を表す __`ab_list_by_score`__ 属性の要素には __`(α 値, β 値, 子ノードの評価値, メッセージ)`__ という tuple が代入されていますが、ゲーム木の上に表示していた __メッセージの情報は必要がなくなった__ ので、__`(α 値, β 値, 子ノードの評価値, フレームの状態を表す文字列)`__ という tuple を代入するように修正することにします。また、__フレームの状態を表す文字列__ は、以下のように設定することにします。なお、③ ~ ⑧ の状態を表す文字列を更新を表す `"update"` としましたが、先程説明したように α 値や β 値を変更しない場合も含むので、別のもっと良い文字列を思いついた方は変更して下さい。

| 行われた処理 | 状態を表す文字列 |
|:--|:--|
| __ノードの処理が開始__  | `"start"` |
| __子ノードの評価値の計算の直後__  |  `"score"` |
| __③ ~ ⑧ の α 値または β 値に対する処理__  | `"update"` |
| __ノードの処理が終了して評価値が確定__  | `"end"` |

また、上記とは別に[先程の検証](#ゲームの決着がついた局面の評価値が計算されるフレームの確認)で発見した、__決着がついた局面で評価値が確定したフレーム__ で __α 値または β 値が評価値の値に更新されない__ という __バグを修正する__ ことにします。

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

* __6 行目__：`ablist_by_score` に追加する tuple の最後の要素を `"start"` に修正する
* __10 ~ 13 行目__：決着がついているノードの場合は、α 値または β 値をノードの評価値に更新することで、__α 値または β 値が更新されないバグを修正__ する
* __19、31 行目__：`ablist_by_score` に追加する tuple の最後の要素を `"score"` に修正する
* __20、21 行目__：max ノードで α 値が更新されるのは[今回の記事の最初](#max-ノードと-min-ノードで行われる処理の分類)で説明したように `score > alpha` の場合なので、その条件が満たされる場合に `alpha` を `score` で更新する処理を行うように修正する。なお、メッセージに関する処理は必要がないので削除した
* __22、23 行目__：20、21 行目のように修正することで、`nodelist_by_score` と `ablist_by_score` にフレームの情報を追加する処理を 22、23 行目でまとめて行うことができるようになる。また、その際に `ablist_by_score` に追加する tuple の最後の要素を `"update"` に修正する
* __24、25 行目__：β 狩りが行われる場合に break 文を実行して残りの子ノードの評価値を計算する処理を省略する
* __27 ~ 38 行目__：min ノードに対しても上記と同様の処理を行うように修正する
* __41 行目__：`ablist_by_score` に追加する tuple の最後の要素を `"end"` に修正する

```python
 1  def calc_score_by_ab(self, abroot, debug=False):           
 2      self.count = 0
 3       
 4      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
 5          self.nodelist_by_score.append(node)
 6          self.ablist_by_score.append((alpha, beta, None, "start"))
 7          self.count += 1
 8          if node.mb.status != Marubatsu.PLAYING:
 9              self.calc_score_of_node(node)
10              if node.mb.turn == Marubatsu.CIRCLE:
11                  alpha = node.score
12              else:
13                  beta = node.score
14          else:
15              if node.mb.turn == Marubatsu.CIRCLE:
16                  for childnode in node.children:
17                      score = calc_ab_score(childnode, alpha, beta)
18                      self.nodelist_by_score.append(node)
19                      self.ablist_by_score.append((alpha, beta, score, "score"))
20                      if score > alpha:
21                          alpha = score
22                      self.nodelist_by_score.append(node)
23                      self.ablist_by_score.append((alpha, beta, None, "update"))
24                      if score >= beta:
25                          break
26                  node.score = alpha
27              else:
28                  for childnode in node.children:
29                      score = calc_ab_score(childnode, alpha, beta)
30                      self.nodelist_by_score.append(node)
31                      self.ablist_by_score.append((alpha, beta, score, "score"))
32                      if score < beta:
33                          beta = score
34                      self.nodelist_by_score.append(node)
35                      self.ablist_by_score.append((alpha, beta, None, "update"))
36                      if score <= alpha:
37                          break
38                  node.score = beta
39 
40          self.nodelist_by_score.append(node)
41          self.ablist_by_score.append((alpha, beta, None, "end"))
元と同じなので省略
42     
43 Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

```python
def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
    def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, None, "start"))
        self.count += 1
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            if node.mb.turn == Marubatsu.CIRCLE:
                alpha = node.score
            else:
                beta = node.score
        else:
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score"))
                    if score > alpha:
                        alpha = score
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update"))
                    if score >= beta:
                        break
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score"))
                    if score < beta:
                        beta = score
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update"))
                    if score <= alpha:
                        break
                node.score = beta

        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, None, "end"))
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score

    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    calc_ab_score(abroot)
    dprint(debug, "count =", self.count) 
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

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

```diff_python
def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
    def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
        self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alpha, beta, None, "このノードの処理の開始"))
+       self.ablist_by_score.append((alpha, beta, None, "start"))
        self.count += 1
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
+           if node.mb.turn == Marubatsu.CIRCLE:
+               alpha = node.score
+           else:
+               beta = node.score
        else:
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    self.nodelist_by_score.append(node)
-                   self.ablist_by_score.append((alpha, beta, score, f"child score = {score}"))
+                   self.ablist_by_score.append((alpha, beta, score, "score"))
-                   if score >= beta:
-                       alpha = score
-                       self.nodelist_by_score.append(node)
-                       self.ablist_by_score.append((alpha, beta, None, f"child score = {score} ≧ {beta}(β値) によるβ狩り"))
-                       break
                    if score > alpha:
+                       message = f"child score = {score} > {alpha}(α値)によるα値の更新"
                        alpha = score
-                   else:
-                       message = f"child score = {score} ≦ {alpha}(α値)なのでα値の更新は行わない"
                    self.nodelist_by_score.append(node)
-                   self.ablist_by_score.append((alpha, beta, None, message))
+                   self.ablist_by_score.append((alpha, beta, None, "update"))
+                   if score >= beta:
+                       break
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    self.nodelist_by_score.append(node)
-                   self.ablist_by_score.append((alpha, beta, score, f"child score = {score}"))
+                   self.ablist_by_score.append((alpha, beta, score, "score"))
-                   if score <= alpha:
-                       beta = score
-                       self.nodelist_by_score.append(node)
-                       self.ablist_by_score.append((alpha, beta, None, f"child score = {score} ≦ {alpha}(α値)によるα狩り"))
-                       break
                    if score < beta:
-                       message = f"child score = {score} < {beta}(β値) によるβ値の更新"
                        beta = score
-                   else:
-                       message = f"child score = {score} ≧ {beta}(β値) なのでβ値の更新は行わない"
                    self.nodelist_by_score.append(node)
-                   self.ablist_by_score.append((alpha, beta, None, message))
+                   self.ablist_by_score.append((alpha, beta, None, "update"))
+                   if score <= alpha:
+                       break
                node.score = beta

        self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alpha, beta, None, f"このノードの評価値が {node.score} で確定"))
+       self.ablist_by_score.append((alpha, beta, None, "end"))
元と同じなので省略
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

### Mbtree_Anim クラスの `__init__` メソッドと `update_gui` メソッドの修正

__ゲーム木の上部に α 値などを表示しなくなった__ ので、__`__init__`__ メソッドを下記のプログラムの 6 行目のように __Figure の高さ__ を表す __`height`__ 属性の値を __66 から 65 に修正__ します。

```python
 1  def __init__(self, mbtree:Mbtree, isscore:bool=False, size:float=0.15):
 2      self.mbtree = mbtree
 3      self.isscore = isscore
 4      self.size = size
 5      self.width = 50
 6      self.height = 65
 7      self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
 8      self.nodenum = len(self.nodelist)
 9      super(Mbtree_Anim, self).__init__()
10     
11  Mbtree_Anim.__init__ = __init__
```

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

```python
def __init__(self, mbtree:Mbtree, isscore:bool=False, size:float=0.15):
    self.mbtree = mbtree
    self.isscore = isscore
    self.size = size
    self.width = 50
    self.height = 65
    self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
    self.nodenum = len(self.nodelist)
    super(Mbtree_Anim, self).__init__()
    
Mbtree_Anim.__init__ = __init__
```
</details>

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

```diff_python
def __init__(self, mbtree:Mbtree, isscore:bool=False, size:float=0.15):
    self.mbtree = mbtree
    self.isscore = isscore
    self.size = size
    self.width = 50
-   self.height = 66
+   self.height = 65
    self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
    self.nodenum = len(self.nodelist)
    super(Mbtree_Anim, self).__init__()
    
Mbtree_Anim.__init__ = __init__
```
</details>

同様の理由で __`update_gui`__ メソッドを下記のプログラムの 4 行目のように __Axes の y 座標の表示範囲__ を __`-1` ~ `self.height - 1`__ の範囲 修正します。

```python
 1  def update_gui(self):
 2      self.ax.clear()
 3      self.ax.set_xlim(-1, self.width - 1)
 4      self.ax.set_ylim(-1, self.height - 1)   
元と同じなので省略   
 5  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(-1, self.height - 1)   
    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,
                             anim_frame=self.play.value, isscore=self.isscore, 
                             ax=self.ax, maxdepth=maxdepth, size=self.size)
    if self.abfig is not None:
        self.update_ab()
                            
    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):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
-   self.ax.set_ylim(-2, self.height - 2)   
+   self.ax.set_ylim(-1, self.height - 1)   
元と同じなので省略   
Mbtree_Anim.update_gui = update_gui
```
</details>

### Mbtree_Anim クラスの `update_ab` メソッドの修正

最後に __`update_ab`__ メソッドを下記のプログラムのように修正します。

* 5 行目の下にあった、ゲーム木の Figure の上部に α 値などを表示する処理を削除する
* __8 ~ 22 行目__：それぞれのフレームの状態に応じて、Figure の背景色を `facecolor` に代入し、右の 1 行目に表示する文字列にメッセージを `+=` 演算子を利用して追加する。別の色を設定したい場合は[こちら](https://www.colordic.org/)のリンク先のウェブページなどを参考にするとよい。メッセージに __追加する文字列の先頭を空白文字にしないと__、追加した文字列とその前の文字列が __くっついてしまう__ 点に注意すること
* __23 行目__：Figure の `set_facecolor` メソッドを呼び出して、Figure の背景色を変更する。`set_facecolor` について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/0335cc42055729d0fac3#axes-%E3%81%AE%E9%85%8D%E7%BD%AE%E4%BD%8D%E7%BD%AE%E3%81%AE%E7%A2%BA%E8%AA%8D)を復習すること

```python
 1  def update_ab(self):
 2      alpha, beta, score, status = self.mbtree.ablist_by_score[self.play.value]
 3      maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
 4      acolor = "red" if maxnode else "black"
 5      bcolor = "black" if maxnode else "red"
 6                             
 7      self.abax.clear()
元と同じなので省略
 8      if status == "start":
 9          facecolor = "white"
10          nodetype += " 処理の開始"
11      elif status == "score":
12          facecolor = "lightyellow"
13          nodetype += " 子ノードの評価値"
14      elif status == "update":
15          facecolor = "lightcyan"
16          if maxnode:
17              nodetype += " α 値の処理"
18          else:
19              nodetype += " β 値の処理"
20      else:
21          facecolor = "lavenderblush"
22          nodetype += " 評価値の確定"
23      self.abfig.set_facecolor(facecolor)
24      self.abax.text(6, 1, nodetype)   
元と同じなので省略    
25         
26  Mbtree_Anim.update_ab = update_ab
```

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

```python
def update_ab(self):
    alpha, beta, score, status = self.mbtree.ablist_by_score[self.play.value]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    acolor = "red" if maxnode else "black"
    bcolor = "black" if maxnode else "red"
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 14)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3
    plus_inf = 4   
    alphacoord = max(minus_inf, alpha)
    betacoord = min(plus_inf, beta)
    
    color = "lightgray" if maxnode else "aqua"
    rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf,
                             height=1, fc=color)
    self.abax.add_patch(rect)
    rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord,
                             height=1, fc="yellow")
    self.abax.add_patch(rect)
    color = "aqua" if maxnode else "lightgray"
    rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
                             height=1, fc=color)
    self.abax.add_patch(rect)

    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")
        
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
                       arrowprops=arrowprops, ha="center", c=acolor)
    self.abax.plot(betacoord, 0, "ob")
    self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
                       arrowprops=arrowprops, ha="center", c=bcolor)
    if score is not None:
        self.abax.plot(score, 0, "og")
        self.abax.annotate(f"score = {score}", xy=(score, 0),
                           xytext=((minus_inf + plus_inf) / 2, 1), 
                           arrowprops=arrowprops, ha="center")
              
    facecolorlist = ["aqua", "yellow", "lightgray"]
    textcolorlist = ["black", "black", "black"]
    if maxnode:
        nodetype = f"深さ {self.selectednode.mb.move_count} max node"
        textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)", "α 値の更新なし (score ≦ α)"]
        if score is not None :
            if beta <= score:
               textcolorlist[0] = "red"
            elif alpha < score:
               textcolorlist[1] = "red"
            else:
               textcolorlist[2] = "red"
    else:
        nodetype = f"深さ {self.selectednode.mb.move_count} min node"
        textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)", "β 値の更新なし (score ≦ β)"]
        if score is not None :
            if score <= alpha:
               textcolorlist[0] = "red"
            elif score < beta:
               textcolorlist[1] = "red"
            else:
               textcolorlist[2] = "red"
               
    if status == "start":
        facecolor = "white"
        nodetype += " 処理の開始"
    elif status == "score":
        facecolor = "lightyellow"
        nodetype += " 子ノードの評価値"
    elif status == "update":
        facecolor = "lightcyan"
        if maxnode:
            nodetype += " α 値の処理"
        else:
            nodetype += " β 値の処理"
    else:
        facecolor = "lavenderblush"
        nodetype += " 評価値の確定"
    self.abfig.set_facecolor(facecolor)
    self.abax.text(6, 1, nodetype)   
    for i in range(3):
        rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5, fc=facecolorlist[i])
        self.abax.add_patch(rect)
        self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
        
Mbtree_Anim.update_ab = update_ab
```
</details>

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

```diff_python
def update_ab(self):
    alpha, beta, score, status = self.mbtree.ablist_by_score[self.play.value]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    acolor = "red" if maxnode else "black"
    bcolor = "black" if maxnode else "red"
-   self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
-   self.ax.text(9, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
-   self.ax.text(19, -1, message, fontsize=fontsize)                             

    self.abax.clear()
元と同じなので省略
+   if status == "start":
+       facecolor = "white"
+       nodetype += " 処理の開始"
+   elif status == "score":
+       facecolor = "lightyellow"
+       nodetype += " 子ノードの評価値"
+   elif status == "update":
+       facecolor = "lightcyan"
+       if maxnode:
+           nodetype += " α 値の処理"
+       else:
+           nodetype += " β 値の処理"
+   else:
+       facecolor = "lavenderblush"
+       nodetype += " 評価値の確定"
+   self.abfig.set_facecolor(facecolor)
    self.abax.text(6, 1, nodetype)   
元と同じなので省略    
        
Mbtree_Anim.update_ab = update_ab
```
</details>

## 表示の確認

上記の修正後に下記のプログラムで修正した `calc_score_by_ab` を呼び出して αβ 法で評価値を計算しなおし、Mbtree_Anim で正しく表示が行われるかを確認します。

```python
mbtree.calc_score_by_ab(mbtree.root)
Mbtree_Anim(mbtree, isscore=True)
```

具体的には先程示した __下記の表のように表示される__ かどうかを確認します。

| 行われた処理 | 右の 1 行目の表示例 | 背景色 |
|:--|:--|:--|
| __① ノードの処理が開始__  | 深さ 0 max node 処理の開始  | 白 |
| __② 子ノードの評価値の計算の直後__  |  深さ 0 max node 子ノードの評価値 | 薄黄色 |
| __③ ~ ⑧ α 値または β 値に対する処理__  | 深さ 0 max node α 値の処理  | 薄水色 |
| __⑨ ノードの処理が終了して評価値が確定__  | 深さ 0 max node 評価値の確定 | 薄紫色 |

また、決着がついた局面で評価値が確定したフレームで α 値または β 値が評価値の値に更新されないという __バグが修正されているか__ どうかも確認します。

### ノードの処理が開始されたフレームの表示の確認

下記はノードの処理が開始された 0 フレーム目の図です。「__深さ 0 max node 処理の開始__」という表示と、Figure の __背景色が白色で表示__ されることが確認できます。また、__ゲーム木の Figure の上部に__ 表示されていた α 値などの __メッセージが表示されなくなっている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2b74d35b-b922-92c9-5d26-98e16f52d6a3.png" width="300">

### 子ノードの評価値の計算の直後のフレームの表示の確認

下記は子ノードの評価値の計算の直後の 9 フレーム目の図です。「__深さ 6 max node 子ノードの評価値__」という表示と、Figure の __背景色が薄黄色で表示__ されることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c540db70-d28f-9688-55af-bc7c2fb29ff6.png" width="500">

上図は次のフレームで α 値を更新する評価値が計算された場合の図ですが、下図のように α 狩りを行う評価値が計算された場合も薄黄色で表示されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3607fdce-9827-bdb9-30e1-41ef2b0cff37.png" width="500">

興味がある方は β 狩りや、α 値や β 値を更新しない評価値が計算された場合も薄黄色で表示されることを確認してみて下さい。

### α 値または β 値に対する処理が行われるフレームの表示の確認

下記は先ほどの 9 フレーム目の次の α 値の更新処理が行われたフレームの図です。「__深さ 6 min node α 値の処理__」という表示と、Figure の __背景色が薄水色で表示__ されることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bb3ab7ea-57b2-7e60-aae1-f19a3425e8e3.png" width="500">

興味がある方は β 値が更新されるフレームや、α 値や β 値を更新しないフレームの価値の場合も薄水色で表示されることを確認してみて下さい。

### ノードの処理が終了して評価値が確定したフレームの表示の確認

下記はノードの評価値が確定した 20 フレーム目の図です。「__深さ 7 min node 評価値の確定__」という表示と、Figure の __背景色が薄紫色で表示__ されることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3757beb1-0ffa-ef1a-04b7-e873b41908bb.png" width="500">

下記は __決着がついた局面の max ノードの評価値が確定__ した 8 フレーム目の図です。「深さ 7 min node 評価値の確定」という表示と、Figure の背景色が薄紫色で表示されることが確認できます。また、[先程は β 値が -inf のまま更新されない](#ゲームの決着がついた局面の評価値が計算されるフレームの確認)というバグがありましたが、下図では __β 値が正しく 1 に更新__ されているので、__先程のバグが修正された__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/67df8a87-7eb3-9463-142e-53753b859c79.png" width="500">

下記は __決着がついた局面の min ノードの評価値が確定__ した 137 フレーム目の図です。[先程は α 値が 1 のまま更新されない](#ゲームの決着がついた局面の評価値が計算されるフレームの確認)というバグがありましたが、下図では __α 値が正しく -1 に更新__ されているので、__先程のバグが修正された__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/23daa45e-71fe-6702-5403-73929507c929.png" width="500">

# 今回の記事のまとめ

今回の記事では、αβ 法で行われる評価値の計算手順のアニメーションで、__それぞれのフレームが行う処理を視覚的にわかりやすく表示__ するように改良を行いました。

なお、視覚的にわかりやすくする改良方法は、__本記事の方法以外にも様々な方法が考えられます__。本記事よりも良い改良方法を思いついた方はその実装にチャレンジしてみて下さい。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/289c8067774951433941

[^1]:min ノードで α 狩りを行う範囲は「子ノードの評価値 ≦ α 値」なので、水色と黄色の __境目は水色の範囲に含まれます__
[^2]:max ノードで α 値を更新しない範囲は「子ノードの評価値 ≦ α 値」なので、灰色と黄色の __境目は灰色の範囲に含まれます__
[^3]:実際には、ゲーム木の上部に表示されるメッセージで区別がつくようにしていますが、__文章での区別__ は __直観的ではなく__、__わかりやすいとは言えない__ でしょう