Pythonで〇×ゲームのAIを一から作成する　その161　αβ 法の視覚化のための Mbtree_Anim の修正 その 2

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/0511dcf319b9f49f52e9

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

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

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

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

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

# αβ 法の視覚化のための Mbtree_Anim の修正の続き

前回の記事では αβ 法の視覚化 のための Mbtree_Anim の修正のうち、常に表示する内容の表示の実装を行いました。今回の記事はその続きです。

## 視覚化の検討のおさらい

[以前の記事](https://qiita.com/ysgeso/items/42c2140766dd59906a02#%E8%A1%A8%E7%A4%BA%E5%86%85%E5%AE%B9%E3%81%A8%E8%A1%A8%E7%A4%BA%E3%81%AB%E5%BF%85%E8%A6%81%E3%81%AA%E6%83%85%E5%A0%B1%E3%81%AE%E6%A4%9C%E8%A8%8E)で行った αβ 法の視覚化と、フレームに記録するデータの検討結果は以下の通りです。

### 常に表示する内容

常に表示する内容と、表示するために必要な情報は以下の表の通りです。[以前の記事](https://qiita.com/ysgeso/items/ddcbd0cb9ab62656173e#%E5%B8%B8%E3%81%AB%E8%A1%A8%E7%A4%BA%E3%81%99%E3%82%8B%E5%86%85%E5%AE%B9)で検討したミニマックス法での表示と共通する内容は省略しました。

なお、この部分は前回の記事で実装しました。

|表示内容|必要な情報|
|:--|:--|
|__α 値と β 値の初期値__<br>__範囲の色分け__<br>__範囲の説明__|  α 値と β 値の初期値 |

### "start" 以外の状態で表示する内容

__"start" 以外__ の状態で表示する内容と、表示するために必要な情報は以下の通りです。

|表示内容|必要な情報|
|:--|:--|
|__置換表の範囲__| 置換表の範囲の下界と上界|
|__置換表の登録の区別__| 置換表に登録されているかどうか|

### フレームの状態ごとに表示する内容

それぞれのフレームの状態で表示する内容は以下の通りです。上記の "start" 以外の状態で表示する内容は省略しました。なお、ミニマックス法と共通する内容には先頭に（※）を記述しました。

* __"start"__ の状態
なし
* __"tt"__ の状態
    * 置換表にノードの評価値が登録されている場合
        * （※）赤字で「置換表に登録済」を表示
        * ミニマックス法で表示した置換表に登録されていた評価値は __表示しない__
        * 置換表による枝狩りが行われている場合
            * $l=u$ の場合は赤字で「置換表による枝狩り（exact value）」を表示
            * $u≦α$ の場合は赤字で「置換表による枝狩り（fail low）」を表示
            * $β≦l$ の場合は赤字で「置換表による枝狩り（fail high）」を表示
        * 置換表による枝狩りが行われていない場合
            * α 値と β 値の初期値が更新される場合は赤字で「α 値または β 値の初期値の更新」を表示
    * 登録されていない場合
        * （※）黒字で「置換表に未登録」を表示
* __"score"__ の状態
    * （※）数直線上にそのフレームでのノードの評価値を表示
    * （※）数直線上に子ノードの評価値を表示
    * そのフレームでの α 値と β 値
* __"update"__ の状態
    * （※）数直線上にそのフレームでのノードの評価値を表示
    * ノードの評価値が更新された場合
        * （※）赤字で「評価値の更新」を表示
    * 更新されていない場合  
        * （※）黒字で「評価値の更新なし」を表示
    * そのフレームでの α 値と β 値
    * α 狩りが行われた場合は赤字で「α 狩り」と表示
    * β 狩りが行われた場合は赤字で「β 狩り」と表示
* __"end"__ の状態
    * （※）数直線上にそのフレームでのノードの評価値を表示
    * このノードの評価値の種類によってフレームの状態を以下のように表示する
        * fail low の場合は「評価値の確定（fail low）」を表示
        * exact value の場合は「評価値の確定（exact value）」を表示
        * fail high の場合は「評価値の確定（fail high）」を表示
    * 置換表を利用する場合
        * 置換表による枝狩りが行われた場合
            * （※）黒字で「置換表に登録されていたデータを利用」を表示
        * 置換表による枝狩りが行われていない場合
            * （※）赤字で「置換表への登録」を表示
            * 計算された範囲
            * 登録する範囲

### フレームに記録するデータ

`calc_score_for_anim` が記録する [フレームのデータを表す dict の内容](https://qiita.com/ysgeso/items/42c2140766dd59906a02#%E5%BF%85%E8%A6%81%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF%E3%82%92%E8%A8%98%E9%8C%B2%E3%81%99%E3%82%8B-dict-%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0) は以下の通りです。

|キー|キーの値の意味|
|:--|:--|
|__"alphaorig"__|α 値の初期値|
|__"betaorig"__|β 値の初期値|
|__"registered_in_tt"__|（※）置換表にノードの評価値が登録されていたかどうか|
|__"lower_bound"__|（※）置換表の範囲の下界|
|__"upper_bound"__|（※）置換表の範囲の上界|
|__"tt_pruned"__|置換表による枝狩りが行われたかどうか |
|__"ab_updated"__|α 値または β 値の初期値が更新されたかどうか|
|__"ab_pruned"__|α 狩りまたは β 狩りが行われたかどうか |
|__"score_type"__|ノードの評価値の種類 |
|__"clower_bound"__|計算された範囲の下界|
|__"cupper_bound"__|計算された範囲の上界|
|__"tlower_bound"__|登録する範囲の下界|
|__"tupper_bound"__|登録する範囲の上界|

## "start" 以外の状態で表示する内容の実装

__"start" 以外__ の状態では __置換表の範囲__ を表示する必要がありますが、「置換表の範囲」は本記事独自の用語で意味を忘れた方が多いと思いますので先にその復習を行います。

### 3 種類のミニマックス値の範囲を表す用語

[以前の記事](https://qiita.com/ysgeso/items/42c2140766dd59906a02#end-%E3%81%AE%E7%8A%B6%E6%85%8B%E3%81%AE%E8%A1%A8%E7%A4%BA)で説明したように、本記事では __3 種類のミニマックス値の範囲__ を __区別できるよう__ に、それぞれを以下の表のように短く表記することにします。

| 表記 | 意味 | そのデータが記録されている dict のキー |
|:--|:--|:--|
| __置換表の範囲__  | 置換表に登録されていたミニマックス値の範囲  | `lower_bound`、`upper_bound` |
| __計算された範囲__  | 子ノードの評価値から計算されたミニマックス値の範囲  | `clower_bound`、`cupper_bound` |
| __登録する範囲__  | 置換表に登録する、上記の 2 つの共通する範囲  | `ltower_bound`、`tupper_bound` |

ただし、置換表に __ミニマックス値が登録されていない場合__ は、置換表の範囲として __下界を負の無限大または評価値の最小値__、__上界を正の無限大または評価値の最大値__ とします[^1]。

### 置換表の範囲の表示方法の検討

置換表の範囲をどのように表示すればよいかについて少し考えてみて下さい。

__置換表の範囲__ は下記の表の __2 通りの場合__ があり、本記事ではそれぞれについて下記のような図形で表示することにします。また、下記とは別に __下界と上界の値__ を __文字でも表示__ することにします。

|条件|表示方法|
|:--|:--|
|__下界と上界が等しい場合__|色のついた丸で表示する|
|__下界と上界が等しくない場合__|下界と上界を両端とする矢印で表示する|

また、__置換表__ にそのノードのミニマックス値の範囲が __登録されていたか__ どうかを __区別できる__ ように、置換表に __登録されていた場合__ は __図形を赤__ で、__登録されていない場合__ は __黒で表示__ し、そのことを __文字でも表示する__ ことにします。

置換表の範囲を表すの __図形の表示場所__ としては、数直線上に表示するという方法も考えられますが、数直線上には α 値や β 値の初期値なども表示されるので、置換表の範囲を表す図形を __数直線上に表示するとわかりづらくなります__。そこで、本記事では __数直線の下に表示__ することにします。また、その __図形のすぐ上に下界と上界の値__ を、__すぐ右に置換表に登録されていたかどうか__ を表す文字を表示することにします。言葉で説明だけではわかりづらいと思いますので、下記に実際の表示の図を示します。置換表の表示範囲の表示方法を検討する際は、このような図をノートなどに書きながら行うと良いでしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/999a9bf8-cf0e-417a-9041-c0c9ba49a8de.png" width="350">

前回の記事でも説明しましたが、今回の記事で実装する視覚化の方法は筆者が思いついた方法に過ぎないので、もっと良い視覚化の方法を思いついた方はぜひ実装してみて下さい。

### 両端の矢印が付いた線の描画方法

__matplotlib__ には、片方の端または、両方の端に __矢印が付いた線を描画する方法がいくつかあります__。そのうちの 1 つは Axes の `arrow` というメソッドを利用するという方法です。ただし、__`arrow` メソッド__ は下記の公式のドキュメントでうまく矢印が描画されない場合があるので __利用しないほうが良い（discouraged）と記述されている__ ので本記事では利用しません。

https://matplotlib.org/stable/api/_as_gen/matplotlib.axes.Axes.arrow.html

もう一つの方法はこれまでに注釈を表示する際に利用していた Axes の __[`annotate` メソッド](https://matplotlib.org/stable/api/_as_gen/matplotlib.axes.Axes.annotate.html#matplotlib.axes.Axes.annotate)__ を下記のように利用するという方法で、上記のドキュメントで紹介されていました。

* __注釈の文字列__ に __`""`（空文字）を指定__ して注釈の文字を描画しないようにする
* 矢印の __両端の座標__ をキーワード引数 __`xy` と `xytext` で指定__ する
* __両端の矢印を描画__ する場合はキーワード引数 __`arrowprops` に [`{ "arrowstyle": "<->" }`](https://matplotlib.org/stable/api/_as_gen/matplotlib.patches.FancyArrowPatch.html#matplotlib.patches.FancyArrowPatch)` というキーの値を持つ dict を代入__ する

なお、矢印の __線の色__ はキーワード引数 __`arrowprops`__ に代入する dict の __`color` というキーの値で指定__ することができます。

ミニマックス値の範囲は、置換表の範囲だけでなく __計算された範囲__ や __登録する範囲__ を __"end" のフレームで表示__ する必要があるので、下記のような __ミニマックス値の範囲を描画__ する __`update_frameinfo` のローカル関数を定義__ する事にします。

__名前__：範囲（bound）を描画（draw）するので `draw_bound` とする
__処理__：指定した範囲を表す図形を指定した色で描画する
__入力__：仮引数 `lower` に下界を、`upper` に上界を、`y` に図形を描画する y 座標を、`color` に図形の色を代入する
__出力__：なし

下記は `draw_bound` の定義です。

* __1 行目__：上記の仮引数を持つ `draw_bound` を定義する
* __2、3 行目__：下界と上界の x 座標をローカル関数 [`calc_coord`](https://qiita.com/ysgeso/items/ad85235816fe59350013#update_frameinfo-%E3%81%AE%E4%BF%AE%E6%AD%A3) を使って計算する
* __4、5 行目__：下界と上界が等しい場合は指定した色で (下界の x 座標, `y`) の座標に `color` の色の丸（[`marker="o"`](https://qiita.com/ysgeso/items/1468226fe9a96ae6a55c#plot-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AB%E3%82%88%E3%82%8B%E3%83%9E%E3%83%BC%E3%82%AB%E3%83%BC%E3%81%AE%E6%8F%8F%E7%94%BB)）を描画する
* __6 ~ 8 行目__：下界と上界が等しくない場合は `annotate` メソッドを利用して (下界の x 座標, `y`) と (上界の x 座標, `y`) を結ぶ両端に矢印が付いた`color` の色の線を描画する

```python
1  def draw_bound(lower, upper, y, color):
2      lower_coord = calc_coord(lower)
3      upper_coord = calc_coord(upper)
4      if lower == upper:
5          self.abax.plot(lower_coord, y, color=color, marker="o")        
6      else:
7          self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
8                             arrowprops={ "arrowstyle": "<->", "color": color }) 
```

### `update_frameinfo` の修正

下記は `draw_bound` を利用して __置換表の範囲を表示__ するように __`update_frameinfo`__ を修正したプログラムです。なお、__図形やメッセージの描画位置__ は[前回の記事](https://qiita.com/ysgeso/items/0511dcf319b9f49f52e9#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E8%A6%96%E8%A6%9A%E5%8C%96%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE-mbtree_anim-%E3%81%AE%E4%BF%AE%E6%AD%A3)で説明したように筆者が __試行錯誤の結果決めた__ ものです。

* __15 ~ 22 行目__：`draw_bound` をローカル関数として定義する
* __25 ~ 39 行目__：αβ 法で計算されており "start" 以外のフレームで置換表の範囲を描画する
* __27、28 行目__：置換表の範囲の下界と上界の値を変数に代入する
* __29 ~ 31 行目__：置換表に登録されていた場合の図形の色を赤とし、真ん中の 7 行目を表す `textlist[6]` に置換表に登録されていたことを表す文字列を代入する
* __32 ~ 34 行目__：置換表に登録されていない場合の図形の色を黒とし、真ん中の 7 行目を表す `textlist[6]` に置換表に登録されていないことを表す文字列を代入する
* __35 行目__：`draw_bound` を呼び出して置換表の範囲の図形を描画する
* __36 ~ 39 行目__：置換表の範囲の図形の左上に下界の値を、右上に上界の値を表示する

```python
 1  from tree import Mbtree_Anim
 2  from marubatsu import Marubatsu
 3  import matplotlib.patches as patches
 4  
 5  def update_frameinfo(self):
元と同じなので省略
 6      # 置換表に登録したかどうかの表示
 7      elif status == "end":
 8          if self.mbtree.use_tt:
 9              if framedata["registered_in_tt"]:
10                  textlist[3] = "置換表に登録されていたデータを利用"
11              else:
12                  textlist[3] = "置換表への登録"
13                  textcolorlist[3] = "red"
14                  
15      def draw_bound(lower, upper, y, color):
16          lower_coord = calc_coord(lower)
17          upper_coord = calc_coord(upper)
18          if lower == upper:
19              self.abax.plot(lower_coord, y, color=color, marker="o")        
20          else:
21              self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
22                                 arrowprops={ "arrowstyle": "<->", "color": color })
23              
24      # ミニマックス値の範囲に関する表示
25      if not minimax:
26          if status != "start":
27              lower_bound = framedata["lower_bound"]
28              upper_bound = framedata["upper_bound"]
29              if framedata["registered_in_tt"]:
30                  color = "red"
31                  textlist[6] = "置換表のミニマックス値の範囲"
32              else:
33                  color = "black"
34                  textlist[6] = "ミニマックス値は置換表に未登録"
35              draw_bound(lower_bound, upper_bound, -2.3, color)
36              lower_text = f"下界 = {lower_bound}"
37              upper_text = f"上界 = {upper_bound}"
38              self.abax.text(leftx, -1.8, lower_text, ha="left")   
39              self.abax.text(rightx, -1.8, upper_text, ha="right")                   
40  
41      self.abfig.set_facecolor(facecolor)
42      for i in range(linenum):
43          self.abax.text(5, linetop - i * 0.7, textlist[i], c=textcolorlist[i])
元と同じなので省略
44           
45  Mbtree_Anim.update_frameinfo = update_frameinfo
```

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

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

def update_frameinfo(self):
    def calc_coord(score):
        return min(max(minus_inf, score), plus_inf)
        
    framedata = self.mbtree.ablist_by_score[self.play.value]
    status = framedata["status"]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    minimax = self.mbtree.minimax
    
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    if minimax:
        self.abax.set_ylim(-1.5, 1.5)
    else:
        self.abax.set_ylim(-4.3, 2.3)
    self.abax.axis("off")

    minus_inf = -3 if self.mbtree.shortest_victory else -2
    plus_inf = 4 if self.mbtree.shortest_victory else 2

    # 範囲の色分け
    if not minimax:
        alphaorig = framedata["alphaorig"]
        betaorig = framedata["betaorig"]
        alphaorig_coord = calc_coord(alphaorig)
        betaorig_coord = calc_coord(betaorig)
        color = "lightgray" if maxnode else "aqua"
        rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphaorig_coord-minus_inf,
                                 height=1, fc=color)
        self.abax.add_patch(rect)
        rect = patches.Rectangle(xy=(alphaorig_coord, -0.5), width=betaorig_coord-alphaorig_coord,
                                 height=1, fc="yellow")
        self.abax.add_patch(rect)
        color = "aqua" if maxnode else "lightgray"
        rect = patches.Rectangle(xy=(betaorig_coord, -0.5), width=plus_inf-betaorig_coord,
                                 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 = "" if self.mbtree.init_ab else "-∞"
        elif num == plus_inf:
            numtext = "" if self.mbtree.init_ab else "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

    # メッセージの表示
    if minimax:
        linenum = 4
        linetop = 1
    else:
        linenum = 9
        linetop = 1.7
    textlist = [""] * linenum
    textcolorlist = ["black"] * linenum

    algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
    use_tt = "〇" if self.mbtree.use_tt else "×"
    shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
    init_ab = "〇" if self.mbtree.init_ab else "×"
    textlist[0] = f"{algorithm}　置換表 {use_tt}　最短 {shortest_victory}"
    if not self.mbtree.minimax:
        textlist[0] += f"　初期値 {init_ab}"
    
    textlist[1] = f"深さ {self.selectednode.mb.move_count} "
    if maxnode:
        textlist[1] += "max node"
    else:
        textlist[1] += "min node"
    
    statusdata = {
        "start": {
            "text": "処理の開始",
            "color": "white"
        },
        "tt": {
            "text": "置換表の処理",
            "color": "honeydew"
        },
        "score": {
            "text": "子ノードの評価値",
            "color": "lightyellow"
        },
        "update": {
            "text": "更新処理",
            "color": "lightcyan"
        },
        "end": {
            "text": "評価値の確定",
            "color": "lavenderblush"
        },
    }
    textlist[2] = statusdata[status]["text"]
    facecolor = statusdata[status]["color"]
    
    arrowprops = { "arrowstyle": "->"}
    leftx = -3
    rightx = 4
    centerx = (leftx + rightx) / 2
    # α 値 と β 値の初期値の表示
    if not minimax:
        if status == "start" or status == "tt":
            self.abax.plot(alphaorig_coord, 0, "or")
            self.abax.annotate(f"α = {alphaorig}", xy=(alphaorig_coord, 0),
                           xytext=(leftx, 1.7), arrowprops=arrowprops, ha="left")        
            self.abax.plot(betaorig_coord, 0, "ob")
            self.abax.annotate(f"β = {betaorig}", xy=(betaorig_coord, 0),
                           xytext=(rightx, 1.7), arrowprops=arrowprops, ha="right")        
        else:
            self.abax.text(leftx, 1.7, f"α = {alphaorig}", ha="left")   
            self.abax.text(rightx, 1.7, f"β = {betaorig}", ha="right")       
    # そのフレームでのノードの評価値の表示
    if status in ["score", "update", "end"]:
        score = framedata["score"]
        score_coord = calc_coord(score)
        text_coord = leftx if maxnode else rightx
        ha = "left" if maxnode else "right"
        self.abax.plot(score_coord, 0, "ok")
        self.abax.annotate(f"score = {score}", xy=(score_coord, 0),
                           xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)        
    # 子ノードの評価値の表示
    if status == "score":
        childscore = framedata["childscore"]
        childscore_coord = calc_coord(childscore)
        text_coord = rightx if maxnode else leftx
        ha = "right" if maxnode else "left"
        self.abax.plot(childscore_coord, 0, "og")
        self.abax.annotate(f"cscore = {childscore}", xy=(childscore_coord, 0),
                           xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)        
    # 置換表にデータが登録されていたかどうかの表示
    elif status =="tt":
        if framedata["registered_in_tt"]:
            textlist[3] = "置換表に登録済"
            textcolorlist[3] = "red"
            score = framedata["lower_bound"]
            score_coord = calc_coord(score)
            self.abax.plot(score_coord, 0, "om")
            self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
                            xytext=(centerx, 1), arrowprops=arrowprops, ha="center")        
        else:
            textlist[3] = "置換表に未登録"
    # ノードの評価値が更新されたかどうかの表示
    elif status == "update":
        if framedata["updated"]:
            textlist[3] = "評価値の更新"
            textcolorlist[3] = "red"
        else:
            textlist[3] = "評価値の更新なし"
    # 置換表に登録したかどうかの表示
    elif status == "end":
        if self.mbtree.use_tt:
            if framedata["registered_in_tt"]:
                textlist[3] = "置換表に登録されていたデータを利用"
            else:
                textlist[3] = "置換表への登録"
                textcolorlist[3] = "red"
                
    def draw_bound(lower, upper, y, color):
        lower_coord = calc_coord(lower)
        upper_coord = calc_coord(upper)
        if lower == upper:
            self.abax.plot(lower_coord, y, color=color, marker="o")        
        else:
            self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
                               arrowprops={ "arrowstyle": "<->", "color": color })
            
    # ミニマックス値の範囲に関する表示
    if not minimax:
        if status != "start":
            lower_bound = framedata["lower_bound"]
            upper_bound = framedata["upper_bound"]
            if framedata["registered_in_tt"]:
                color = "red"
                textlist[6] = "置換表のミニマックス値の範囲"
            else:
                color = "black"
                textlist[6] = "ミニマックス値は置換表に未登録"
            draw_bound(lower_bound, upper_bound, -2.3, color)
            lower_text = f"下界 = {lower_bound}"
            upper_text = f"上界 = {upper_bound}"
            self.abax.text(leftx, -1.8, lower_text, ha="left")   
            self.abax.text(rightx, -1.8, upper_text, ha="right")                   

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, linetop - i * 0.7, textlist[i], c=textcolorlist[i])

    num_calculated = framedata["num_calculated"]
    num_pruned = framedata["num_pruned"]
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total if num_total != 0 else 0
    prev_framedata = self.mbtree.ablist_by_score[self.prev_frame]
    prev_num_calculated = prev_framedata["num_calculated"]
    prev_num_pruned = prev_framedata["num_pruned"]
    prev_num_total = prev_num_calculated + prev_num_pruned
    diff_num_calculated = num_calculated - prev_num_calculated
    diff_num_pruned = num_pruned - prev_num_pruned
    diff_num_total = num_total - prev_num_total
    diff_num_ratio = diff_num_calculated / diff_num_total if diff_num_total != 0 else 0

    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
    diff_datalist = [ f"{diff_num_calculated:+d}", f"{diff_num_pruned:+d}", 
                    f"{diff_num_total:+d}", f"{diff_num_ratio * 100:.1f}%"]
    for i in range(4):
        self.abax.text(15, linetop - i * 0.7, textlist[i])
        self.abax.text(19.5, linetop - i * 0.7, datalist[i], ha="right")
        self.abax.text(22.5, linetop - i * 0.7, diff_datalist[i], ha="right")
        
    # 範囲の説明の表示
    if not minimax:
        facecolorlist = [
            "lightgray" if maxnode else "aqua", 
            "yellow",
            "aqua" if maxnode else "lightgray", 
        ]
        textlist = ["fail low", "exact value", "fail high"]
        textcolorlist = ["black", "black", "black"]
        for i in range(3):
            rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7), 
                                     width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
            self.abax.add_patch(rect)
            self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])  
         
Mbtree_Anim.update_frameinfo = update_frameinfo
```
</details>

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

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

def update_frameinfo(self):
元と同じなので省略
    # 置換表に登録したかどうかの表示
    elif status == "end":
        if self.mbtree.use_tt:
            if framedata["registered_in_tt"]:
                textlist[3] = "置換表に登録されていたデータを利用"
            else:
                textlist[3] = "置換表への登録"
                textcolorlist[3] = "red"
                
+   def draw_bound(lower, upper, y, color):
+       lower_coord = calc_coord(lower)
+       upper_coord = calc_coord(upper)
+       if lower == upper:
+           self.abax.plot(lower_coord, y, color=color, marker="o")        
+       else:
+           self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
+                              arrowprops={ "arrowstyle": "<->", "color": color })
            
    # ミニマックス値の範囲に関する表示
+   if not minimax:
+       if status != "start":
+           lower_bound = framedata["lower_bound"]
+           upper_bound = framedata["upper_bound"]
+           if framedata["registered_in_tt"]:
+               color = "red"
+               textlist[6] = "置換表のミニマックス値の範囲"
+           else:
+               color = "black"
+               textlist[6] = "ミニマックス値は置換表に未登録"
+           draw_bound(lower_bound, upper_bound, -2.3, color)
+           lower_text = f"下界 = {lower_bound}"
+           upper_text = f"上界 = {upper_bound}"
+           self.abax.text(leftx, -1.8, lower_text, ha="left")   
+           self.abax.text(rightx, -1.8, upper_text, ha="right")                   

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, linetop - i * 0.7, textlist[i], c=textcolorlist[i])
元と同じなので省略
         
Mbtree_Anim.update_frameinfo = update_frameinfo
```
</details>

### 表示の確認

上記の修正後に下記のプログラムを実行して下記の条件で計算したデータを Mbtree_Anim で表示すると、実行結果のように __"start" のフレームでは置換表の範囲は表示されない__ ことが確認できます。余裕がある方は、他の条件でも確認してみて下さい。

* αβ 法で計算する
* 置換表を利用する
* 最短の勝利を目指す評価値を計算する
* ルートノードの α 値と β 値を評価値の最小値と最大値で初期化する

```python
from tree import Mbtree

mbtree = Mbtree.load("../data/abtree_root")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, use_tt=True,
                           shortest_victory=True, init_ab=True)
Mbtree_Anim(mbtree, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/067471bb-1c95-489f-b817-bc6fcdb0c8fa.png" width="500">

次に、__置換表に__ ミニマックス値の範囲が __登録されていない場合の表示を確認__ します。

当然ですが、__ルートノード__ のミニマックス値の範囲は __置換表に登録されていません__。従って、__下段の >__  をクリックして表示される下図の __ルートノードの "tt" のフレーム__ では、 __置換表の範囲__ が __評価値の最小値と最大値の範囲である -2 ~ 3__ となります。そのことが図では下記のように描画されます。

* 数直線の下に -2 ~ 3 の範囲が __両端に矢印がついた線で描画__ されている
* __置換表に登録されていなかった__ ので矢印が __黒色で描画__ されている
* 矢印の右に「ミニマックス値は置換表に未登録」と表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/966bb735-c39f-4a4a-94e9-71cd7954b32d.png" width="500">

:::note
ルートノードの α 値と β 値を評価値の最小値と最大値で __初期化しない場合__ は下記のプログラムの実行結果のように __置換表の範囲が負の無限大 ~ 正の無限大__ のように正しく表示されます。

```python
mbtree2 = Mbtree.load("../data/abtree_root")
mbtree2.calc_score_for_anim(mbtree.root, minimax=False, use_tt=True,
                            shortest_victory=True, init_ab=False)
Mbtree_Anim(mbtree2, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/56607c58-39a3-40a9-b82b-f705d9f530ec.png" width="500">
:::

下図は > をクリックして __"score"、"update"、"end" のフレーム__ を表示した図です。いずれの場合でも __置換表の範囲が同様の方法で正しく表示される__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/14c6dc19-0684-4b1d-844b-2761430f7d40.png" width="500">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/59d1e654-160d-4d3d-a112-927dd5216025.png" width="500">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/86218d07-8f3c-432e-a3ce-e3d42ad5e3dd.png" width="500">

次に、__置換表に__ ミニマックス値の範囲が __登録されていた場合の表示を確認__ します。

下図は赤枠の __ルートノードの最初の子ノード__ の評価値が確定した __"end" のフレームの図__ です。ルートノードの最初の子ノードの __ミニマックス値の範囲は置換表に登録されていない__ ので __評価値の範囲は上図と同じ内容が表示__ されます。また、__計算された評価値である 0__ は __exact value の範囲__ なので __置換表には__ ミニマックス値の範囲として __下界と上界が 0 というデータが登録__ されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c9e18aae-d708-4ae4-8a03-75a647ecfa56.png" width="500">

下図は __上図の赤枠のノードの__ 局面を時計回りに 90 度回転させた __同一局面のノード__ が選択されたフレームの図なので、下図の赤枠のノードの局面の __ミニマックス値の範囲__ は __置換表に下界と上界が共に 0 として登録__ されています。また、__下図は "tt" のフレーム__ の図ではそのことが下記のように __正しく描画されています__。

* 置換表の範囲の __下界と上界が等しい__ ので、数直線の下の __0 の位置に丸が描画__ されている
* __置換表に登録されていた__ ので丸が __赤色で描画__ されている
* 赤い丸の右に「置換表のミニマックス値の範囲」と表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/517175a4-3f40-4fd8-aa90-d40fc2ac3d38.png" width="500">

なお、上図で数直線の上に表示される「__置換表の評価値＝０__」と __矢印が重なって表示__ されていますが、__この表示はミニマックス法の場合で行う表示__ なので、__この後__ の "tt" の状態で表示する内容の実装で __表示しないように修正します__。

__置換表の範囲__ の __下界と上界が等しい__ ので置換表の範囲の下界（または上界）である __0 がこのノードの評価値として計算__ されて __置換表による枝狩り__ が行われます。従って __下段の >__ をクリックして __次に表示__ されるのは下図の __"end" のフレーム__ で、__置換表の範囲が上図と同様の方法で正しく表示__ されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6e3f63ca-942a-4c27-a395-45083a78248e.png" width="500">

下図は __置換表に登録__ されており、置換表の範囲の __下界と上界が等しくない場合__ の 67 フレーム目の図で、そのことが図では下記のように正しく描画されています。

* 置換表の範囲の __下界と上界が等くない__ ので、数直線の下に __下界と上界の範囲を表す矢印が表示__ されている
* __置換表に登録されていた__ ので矢印が __赤色で描画__ されている
* 矢印の右に「置換表のミニマックス値の範囲」と表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/31a75152-3220-4e90-a790-cc9b33f170df.png" width="500">

上図のフレームでは置換表の範囲が fail low または fail high に完全に含まれていないので置換表による枝狩りは行われません。図は省略しますが下段の > をクリックして "score"、"update"、"end" のフレームでも置換表の範囲が上図同様の方法で表示されることを確認して下さい。

:::note
置換表に登録されており、置換表の下界と上界が等しくない "tt" のフレームを Mbtree_Anim の __> ボタンなどを使って探すのは大変__ なので、上記の 67 フレーム目は、__下記のプログラムを実行して求めました__。

* __1 行目__：組み込み関数 [`enumerate`](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-enumerate) を利用してフレームの情報の一覧を表す list から順番にインデックスとフレームのデータを取り出すという繰り返し処理を行う
* __2 ~ 8 行目__：状態が "tt"、置換表に登録されている、置換表の範囲の下界と上界が等しくないという 3 つの条件がすべて満たされている場合に 7 行目でインデックスを表示し、8 行目の break 文で繰り返し処理を終了する

```python
1  for i, framedata in enumerate(mbtree.ablist_by_score):
2      if framedata["status"] == "tt":
3          registered_in_tt = framedata["registered_in_tt"]
4          lower_bound = framedata["lower_bound"]
5          upper_bound = framedata["upper_bound"]
6          if registered_in_tt and lower_bound != upper_bound:
7              print(i)
8              break
```

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

```python
for i, framedata in enumerate(mbtree.ablist_by_score):
    if framedata["status"] == "tt":
        registered_in_tt = framedata["registered_in_tt"]
        lower_bound = framedata["lower_bound"]
        upper_bound = framedata["upper_bound"]
        if registered_in_tt and lower_bound != upper_bound:
            print(i)
            break
```
</details>

実行結果

```
67
```
:::

## "tt" の状態で表示する内容の実装

下記は __"tt" の状態のフレーム__ で表示する内容の再掲です。（※）の部分は実装済なので、それ以外の場合の表示を実装する必要があります。
* 置換表にノードの評価値が登録されている場合
    * （※）赤字で「置換表に登録済」を表示
    * ミニマックス法で表示した置換表に登録されていた評価値は __表示しない__
    * 置換表による枝狩りが行われている場合
        * $l=u$ の場合は赤字で「置換表による枝狩り（exact value）」を表示
        * $u≦α$ の場合は赤字で「置換表による枝狩り（fail low）」を表示
        * $β≦l$ の場合は赤字で「置換表による枝狩り（fail high）」を表示
    * 置換表による枝狩りが行われていない場合
        * α 値と β 値の初期値が更新される場合は赤字で「α 値または β 値の初期値の更新」を表示
* 登録されていない場合
    * （※）黒字で「置換表に未登録」を表示

上記に加えて __右下に表示する範囲の説明の表示__ を以下のように修正することにします。

* __置換表による枝狩りが行われている場合__ は、__対応する範囲の文字を赤字で表示__ する

どのように実装すればよいかについて少し考えてみて下さい。

### `update_frameinfo` の修正

下記は上記を表示するように __`update_frameinfo`__ を修正したプログラムです。

* __7 ~ 12 行目__：__ミニマックス法で計算されていた場合のみ__ 数直線上に置換表に __登録されていた評価値とその注釈を表示__ するようにする
* __13 ~ 28 行目__：αβ 法で計算されていた場合の表示を行う
* __14 ~ 24 行目__：置換表による枝狩りが行われていた場合に __`pruned_type`__ という変数に行なわれた __枝狩りの種類を表す文字列を計算__ し、23 行目で真ん中の 5 行目に表示する文字列を計算し、24 行目でその文字列の色を赤色にする
* __25 ~ 28 行目__：置換表に登録されていた場合で、置換表による枝狩りが行われず、__α 値または β 値の初期値が更新されている場合__ は真ん中の 5 行目に赤字で「α 値または β 値の初期値の更新」を表示するようにする
* __40 ~ 46 行目__："tt" の状態で置換表による枝狩りが行われていた場合は、14 ~ 22 行目の処理で `pruend_type` という変数に枝狩りの種類を表す文字列が代入されているので、その値に応じて __対応する範囲の説明の文字を赤色にする__

```python
 1  def update_frameinfo(self):
元と同じなので省略
 2      # 置換表にデータが登録されていたかどうかの表示
 3      elif status =="tt":
 4          if framedata["registered_in_tt"]:
 5              textlist[3] = "置換表に登録済"
 6              textcolorlist[3] = "red"
 7              if minimax:
 8                  score = framedata["lower_bound"]
 9                  score_coord = calc_coord(score)
10                  self.abax.plot(score_coord, 0, "om")
11                  self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
12                                     xytext=(centerx, 1), arrowprops=arrowprops, ha="center")
13              else:
14                  if framedata["tt_pruned"]:
15                      lower_bound = framedata["lower_bound"]
16                      upper_bound = framedata["upper_bound"]
17                      if lower_bound == upper_bound:
18                          pruned_type = "exact value"
19                      elif upper_bound <= alphaorig:
20                          pruned_type = "fail low"
21                      elif betaorig <= lower_bound:
22                          pruned_type = "fail high"
23                      textlist[4] = f"置換表による枝狩り ({pruned_type})"
24                      textcolorlist[4] = "red"
25                  else:
26                      if framedata["ab_updated"]:
27                          textlist[4] = "α 値または β 値の初期値の更新"
28                          textcolorlist[4] = "red"            
29          else:
30              textlist[3] = "置換表に未登録"
元と同じなので省略
31      # 範囲の説明の表示
32      if not minimax:
33          facecolorlist = [
34              "lightgray" if maxnode else "aqua", 
35              "yellow",
36              "aqua" if maxnode else "lightgray", 
37          ]
38          textlist = ["fail low", "exact value", "fail high"]
39          textcolorlist = ["black", "black", "black"]
40          if status == "tt" and framedata["tt_pruned"]:
41              if pruned_type == "fail low":
42                  textcolorlist[0] = "red"
43              elif pruned_type == "exact value":
44                  textcolorlist[1] = "red"
45              elif pruned_type == "fail high":
46                  textcolorlist[2] = "red"
47          for i in range(3):
48              rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7), 
49                                       width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
50              self.abax.add_patch(rect)
51              self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])  
52           
53  Mbtree_Anim.update_frameinfo = update_frameinfo
```

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

```python
def update_frameinfo(self):
    def calc_coord(score):
        return min(max(minus_inf, score), plus_inf)
        
    framedata = self.mbtree.ablist_by_score[self.play.value]
    status = framedata["status"]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    minimax = self.mbtree.minimax
    
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    if minimax:
        self.abax.set_ylim(-1.5, 1.5)
    else:
        self.abax.set_ylim(-4.3, 2.3)
    self.abax.axis("off")

    minus_inf = -3 if self.mbtree.shortest_victory else -2
    plus_inf = 4 if self.mbtree.shortest_victory else 2

    # 範囲の色分け
    if not minimax:
        alphaorig = framedata["alphaorig"]
        betaorig = framedata["betaorig"]
        alphaorig_coord = calc_coord(alphaorig)
        betaorig_coord = calc_coord(betaorig)
        color = "lightgray" if maxnode else "aqua"
        rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphaorig_coord-minus_inf,
                                 height=1, fc=color)
        self.abax.add_patch(rect)
        rect = patches.Rectangle(xy=(alphaorig_coord, -0.5), width=betaorig_coord-alphaorig_coord,
                                height=1, fc="yellow")
        self.abax.add_patch(rect)
        color = "aqua" if maxnode else "lightgray"
        rect = patches.Rectangle(xy=(betaorig_coord, -0.5), width=plus_inf-betaorig_coord,
                                 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 = "" if self.mbtree.init_ab else "-∞"
        elif num == plus_inf:
            numtext = "" if self.mbtree.init_ab else "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

    # メッセージの表示
    if minimax:
        linenum = 4
        linetop = 1
    else:
        linenum = 9
        linetop = 1.7
    textlist = [""] * linenum
    textcolorlist = ["black"] * linenum

    algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
    use_tt = "〇" if self.mbtree.use_tt else "×"
    shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
    init_ab = "〇" if self.mbtree.init_ab else "×"
    textlist[0] = f"{algorithm}　置換表 {use_tt}　最短 {shortest_victory}"
    if not self.mbtree.minimax:
        textlist[0] += f"　初期値 {init_ab}"
    
    textlist[1] = f"深さ {self.selectednode.mb.move_count} "
    if maxnode:
        textlist[1] += "max node"
    else:
        textlist[1] += "min node"
    
    statusdata = {
        "start": {
            "text": "処理の開始",
            "color": "white"
        },
        "tt": {
            "text": "置換表の処理",
            "color": "honeydew"
        },
        "score": {
            "text": "子ノードの評価値",
            "color": "lightyellow"
        },
        "update": {
            "text": "更新処理",
            "color": "lightcyan"
        },
        "end": {
            "text": "評価値の確定",
            "color": "lavenderblush"
        },
    }
    textlist[2] = statusdata[status]["text"]
    facecolor = statusdata[status]["color"]
    
    arrowprops = { "arrowstyle": "->"}
    leftx = -3
    rightx = 4
    centerx = (leftx + rightx) / 2
    # α 値 と β 値の初期値の表示
    if not minimax:
        if status == "start" or status == "tt":
            self.abax.plot(alphaorig_coord, 0, "or")
            self.abax.annotate(f"α = {alphaorig}", xy=(alphaorig_coord, 0),
                               xytext=(leftx, 1.7), arrowprops=arrowprops, ha="left")        
            self.abax.plot(betaorig_coord, 0, "ob")
            self.abax.annotate(f"β = {betaorig}", xy=(betaorig_coord, 0),
                               xytext=(rightx, 1.7), arrowprops=arrowprops, ha="right")        
        else:
            self.abax.text(leftx, 1.7, f"α = {alphaorig}", ha="left")   
            self.abax.text(rightx, 1.7, f"β = {betaorig}", ha="right")       
    # そのフレームでのノードの評価値の表示
    if status in ["score", "update", "end"]:
        score = framedata["score"]
        score_coord = calc_coord(score)
        text_coord = leftx if maxnode else rightx
        ha = "left" if maxnode else "right"
        self.abax.plot(score_coord, 0, "ok")
        self.abax.annotate(f"score = {score}", xy=(score_coord, 0),
                           xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)        
    # 子ノードの評価値の表示
    if status == "score":
        childscore = framedata["childscore"]
        childscore_coord = calc_coord(childscore)
        text_coord = rightx if maxnode else leftx
        ha = "right" if maxnode else "left"
        self.abax.plot(childscore_coord, 0, "og")
        self.abax.annotate(f"cscore = {childscore}", xy=(childscore_coord, 0),
                           xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)        
    # 置換表にデータが登録されていたかどうかの表示
    elif status =="tt":
        if framedata["registered_in_tt"]:
            textlist[3] = "置換表に登録済"
            textcolorlist[3] = "red"
            if minimax:
                score = framedata["lower_bound"]
                score_coord = calc_coord(score)
                self.abax.plot(score_coord, 0, "om")
                self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
                                   xytext=(centerx, 1), arrowprops=arrowprops, ha="center")
            else:
                if framedata["tt_pruned"]:
                    lower_bound = framedata["lower_bound"]
                    upper_bound = framedata["upper_bound"]
                    if lower_bound == upper_bound:
                        pruned_type = "exact value"
                    elif upper_bound <= alphaorig:
                        pruned_type = "fail low"
                    elif betaorig <= lower_bound:
                        pruned_type = "fail high"
                    textlist[4] = f"置換表による枝狩り ({pruned_type})"
                    textcolorlist[4] = "red"
                else:
                    if framedata["ab_updated"]:
                        textlist[4] = "α 値または β 値の初期値の更新"
                        textcolorlist[4] = "red"            
        else:
            textlist[3] = "置換表に未登録"
    # ノードの評価値が更新されたかどうかの表示
    elif status == "update":
        if framedata["updated"]:
            textlist[3] = "評価値の更新"
            textcolorlist[3] = "red"
        else:
            textlist[3] = "評価値の更新なし"
    # 置換表に登録したかどうかの表示
    elif status == "end":
        if self.mbtree.use_tt:
            if framedata["registered_in_tt"]:
                textlist[3] = "置換表に登録されていたデータを利用"
            else:
                textlist[3] = "置換表への登録"
                textcolorlist[3] = "red"
                
    def draw_bound(lower, upper, y, color):
        lower_coord = calc_coord(lower)
        upper_coord = calc_coord(upper)
        if lower == upper:
            self.abax.plot(lower_coord, y, color=color, marker="o")        
        else:
            self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
                               arrowprops={ "arrowstyle": "<->", "color": color })
            
    # 下界と上界に関する表示
    if not minimax:
        lower_text = ""
        upper_text = ""
        if status != "start":
            lower_bound = framedata["lower_bound"]
            upper_bound = framedata["upper_bound"]
            if framedata["registered_in_tt"]:
                color = "red"
                textlist[6] = "置換表のミニマックス値の範囲"
            else:
                color = "black"
                textlist[6] = "ミニマックス値は置換表に未登録"
            draw_bound(lower_bound, upper_bound, -2.3, color)
            lower_text = f"下界 = {lower_bound}"
            upper_text = f"上界 = {upper_bound}"
            self.abax.text(leftx, -1.8, lower_text, ha="left")   
            self.abax.text(rightx, -1.8, upper_text, ha="right")                   

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, linetop - i * 0.7, textlist[i], c=textcolorlist[i])

    num_calculated = framedata["num_calculated"]
    num_pruned = framedata["num_pruned"]
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total if num_total != 0 else 0
    prev_framedata = self.mbtree.ablist_by_score[self.prev_frame]
    prev_num_calculated = prev_framedata["num_calculated"]
    prev_num_pruned = prev_framedata["num_pruned"]
    prev_num_total = prev_num_calculated + prev_num_pruned
    diff_num_calculated = num_calculated - prev_num_calculated
    diff_num_pruned = num_pruned - prev_num_pruned
    diff_num_total = num_total - prev_num_total
    diff_num_ratio = diff_num_calculated / diff_num_total if diff_num_total != 0 else 0

    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
    diff_datalist = [ f"{diff_num_calculated:+d}", f"{diff_num_pruned:+d}", 
                    f"{diff_num_total:+d}", f"{diff_num_ratio * 100:.1f}%"]
    for i in range(4):
        self.abax.text(15, linetop - i * 0.7, textlist[i])
        self.abax.text(19.5, linetop - i * 0.7, datalist[i], ha="right")
        self.abax.text(22.5, linetop - i * 0.7, diff_datalist[i], ha="right")
        
    # 範囲の説明の表示
    if not minimax:
        facecolorlist = [
            "lightgray" if maxnode else "aqua", 
            "yellow",
            "aqua" if maxnode else "lightgray", 
        ]
        textlist = ["fail low", "exact value", "fail high"]
        textcolorlist = ["black", "black", "black"]
        if status == "tt" and framedata["tt_pruned"]:
            if pruned_type == "fail low":
                textcolorlist[0] = "red"
            elif pruned_type == "exact value":
                textcolorlist[1] = "red"
            elif pruned_type == "fail high":
                textcolorlist[2] = "red"
        for i in range(3):
            rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7), 
                                     width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
            self.abax.add_patch(rect)
            self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])  
         
Mbtree_Anim.update_frameinfo = update_frameinfo
```
</details>

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

```diff_python
def update_frameinfo(self):
元と同じなので省略
    # 置換表にデータが登録されていたかどうかの表示
    elif status =="tt":
        if framedata["registered_in_tt"]:
            textlist[3] = "置換表に登録済"
            textcolorlist[3] = "red"
-           score = framedata["lower_bound"]
-           score_coord = calc_coord(score)
-           self.abax.plot(score_coord, 0, "om")
-           self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
-                              xytext=(centerx, 1), arrowprops=arrowprops, ha="center")
+           if minimax:
+               score = framedata["lower_bound"]
+               score_coord = calc_coord(score)
+               self.abax.plot(score_coord, 0, "om")
+               self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
+                                  xytext=(centerx, 1), arrowprops=arrowprops, ha="center")
+           else:
+               if framedata["tt_pruned"]:
+                   lower_bound = framedata["lower_bound"]
+                   upper_bound = framedata["upper_bound"]
+                   if lower_bound == upper_bound:
+                       pruned_type = "exact value"
+                   elif upper_bound <= alphaorig:
+                       pruned_type = "fail low"
+                   elif betaorig <= lower_bound:
+                       pruned_type = "fail high"
+                   textlist[4] = f"置換表による枝狩り ({pruned_type})"
+                   textcolorlist[4] = "red"
+               else:
+                   if framedata["ab_updated"]:
+                       textlist[4] = "α 値または β 値の初期値の更新"
+                       textcolorlist[4] = "red"            
        else:
            textlist[3] = "置換表に未登録"
元と同じなので省略
    # 範囲の説明の表示
    if not minimax:
        facecolorlist = [
            "lightgray" if maxnode else "aqua", 
            "yellow",
            "aqua" if maxnode else "lightgray", 
        ]
        textlist = ["fail low", "exact value", "fail high"]
        textcolorlist = ["black", "black", "black"]
+       if status == "tt" and framedata["tt_pruned"]:
+           if pruned_type == "fail low":
+               textcolorlist[0] = "red"
+           elif pruned_type == "exact value":
+               textcolorlist[1] = "red"
+           elif pruned_type == "fail high":
+                textcolorlist[2] = "red"
        for i in range(3):
            rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7), 
                                     width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
            self.abax.add_patch(rect)
            self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])  
         
Mbtree_Anim.update_frameinfo = update_frameinfo
```
</details>

### 表示の確認方法

上記の修正後に下記のプログラムを実行して正しく表示されることを確認します。

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

下記のそれぞれの場合について表示を確認することにします。

* 置換表に登録されていない場合（条件 1）
* 置換表に登録されている場合
    * 置換表による枝狩りが行われる場合
        * 置換表の範囲が exact value である[^2]（条件 2）
        * 置換表の範囲が fail low に完全に含まれる（条件 3）
        * 置換表の範囲が fail high に完全に含まれる（条件 4）
    * 置換表による枝狩りが行われない場合
        * α 値または β 値の 初期値が更新される（条件 5）
        * α 値または β 値の 初期値が更新されない（条件 6）

### 条件 1 の表示の確認

下図は __ルートノードの "tt" の状態のフレーム__ で、修正前と同じ表示が行われるので __条件 1 の置換表に登録されていない場合__ に __正しく表示されることが確認__ できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/966bb735-c39f-4a4a-94e9-71cd7954b32d.png" width="500">

### 条件 2 ~ 6 を満たすフレームを探すプログラムの作成

上記の条件 2 から 6 を満たす "tt" のフレームを __手動で探すのは困難__ なので、下記のような __関数を定義__ することにします。

__名前__：条件にあった "tt" のフレームを探すので `search_tt_frame` とする
__処理__：指定した番号の条件を満たす最初のフレームの番号を計算して返す
__入力__：仮引数 `type` に条件の番号を代入する
__出力__：指定した番号の条件を満たす最初のフレームの番号を返り値として返す

下記は __`search_frame`__ の定義です。なお、この関数は __今後の記事で利用することはない__ ので ai.py などの __ファイルには保存しない__ ことにします。

* __2 行目__：組み込み関数 [`enumerate`](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-enumerate) を利用してフレームの情報の一覧を表す list から順番にインデックスとフレームのデータを取り出すという繰り返し処理を行う
* __3 ~ 25 行目__：`type` のそれぞれの条件を満たす場合にフレームの番号を返す処理を行う

```python
 1  def search_tt_frame(type):
 2      for i, framedata in enumerate(mbtree.ablist_by_score):
 3          if framedata["status"] == "tt":
 4              if framedata["registered_in_tt"]:
 5                  if framedata["tt_pruned"]:
 6                      lower_bound = framedata["lower_bound"]
 7                      upper_bound = framedata["upper_bound"]
 8                      alphaorig = framedata["alphaorig"]
 9                      betaorig = framedata["betaorig"]
10                      if lower_bound == upper_bound:
11                          if type == 2:
12                              return i
13                      elif upper_bound <= alphaorig:
14                          if type == 3:
15                              return i
16                      elif betaorig <= lower_bound:
17                          if type == 4:
18                              return i
19                  else:
20                      if framedata["ab_updated"]:
21                          if type == 5:
22                              return i
23                      else:
24                          if type == 6:
25                              return i
```

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

```python
def search_tt_frame(type):
    for i, framedata in enumerate(mbtree.ablist_by_score):
        if framedata["status"] == "tt":
            if framedata["registered_in_tt"]:
                if framedata["tt_pruned"]:
                    lower_bound = framedata["lower_bound"]
                    upper_bound = framedata["upper_bound"]
                    alphaorig = framedata["alphaorig"]
                    betaorig = framedata["betaorig"]
                    if lower_bound == upper_bound:
                        if type == 2:
                            return i
                    elif upper_bound <= alphaorig:
                        if type == 3:
                            return i
                    elif betaorig <= lower_bound:
                        if type == 4:
                            return i
                else:
                    if framedata["ab_updated"]:
                        if type == 5:
                            return i
                    else:
                        if type == 6:
                            return i
```

</details>

### 条件 2 の表示の確認

下記のプログラムを実行して __条件 2 を満たすフレームを計算__ すると、実行結果から __99 フレーム目が計算__ されます。

```python
print(search_tt_frame(2))
```

実行結果

```
99
```

下図は 99 フレーム目の図で、下記のように __正しく描画されていることが確認__ できます。

* 数直線上に置換表の評価値とその注釈が表示されなくなっている
* 真ん中の 5 行目に赤字で「置換表による枝狩り（exact value）」が表示されている
* 右下の範囲の説明の exact value が赤字で表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0569a102-5254-4165-9322-3f9cde1ca7e7.png" width="500">

### 条件 3 の表示の確認

下記のプログラムを実行して __条件 3 を満たすフレームを計算__ すると、実行結果から __191 フレーム目が計算__ されます。

```python
print(search_tt_frame(3))
```

実行結果

```
191
```

下図は 191 フレーム目の図で、下記のように __正しく描画されていることが確認__ できます。

* ミニマックス法の場合と異なり、数直線に置換表の評価値が表示されなくなっている
* 真ん中の 5 行目に赤字で「置換表による枝狩り（fail low）」が表示されている
* 右下の範囲の説明の fail low が赤字で表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d125227b-0989-45a1-b80e-118a516a0ce8.png" width="500">

### 条件 4 の表示の確認

下記のプログラムを実行して __条件 4 を満たすフレームを計算__ すると、実行結果から __132 フレーム目が計算__ されます。

```python
print(search_tt_frame(4))
```

実行結果

```
132
```

下図は 132 フレーム目の図で、下記のように __正しく描画されていることが確認__ できます。

* ミニマックス法の場合と異なり、数直線に置換表の評価値が表示されなくなっている
* 真ん中の 5 行目に赤字で「置換表による枝狩り（fail high）」が表示されている
* 右下の範囲の説明の fail high が赤字で表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/62bfc456-8c02-406b-9cc9-025be42eb612.png" width="500">

### 条件 5 の表示の確認

下記のプログラムを実行して __条件 5 を満たすフレームを計算__ すると、実行結果から __67 フレーム目が計算__ されます。

```python
print(search_tt_frame(5))
```

実行結果

```
67
```

下図は 67 フレーム目の図で、下記の点では __正しく描画されていることが確認__ できます。

* ミニマックス法の場合と異なり、数直線に置換表の評価値が表示されなくなっている
* 真ん中の 5 行目に赤字で「α 値または β 値の初期値の更新」が表示されている
* 右下の範囲の説明はすべて黒字で表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/84847c67-638f-4a27-9b49-800735edab60.png" width="500">

見逃してしまう方が多いのではないかと思いますが、上図には　__α 値または β 値の初期値の更新に関係__ する __おかしな点があります__。どのような問題があるかについて少し考えてみて下さい。なお、おかしな点については先に条件 6 の表示の確認を行ってから説明します。

### 条件 6 の表示の確認

下記のプログラムを実行して __条件 6 を満たすフレームを計算__ すると、実行結果から __276 フレーム目が計算__ されます。

```python
print(search_tt_frame(6))
```

実行結果

```
276
```

下図は 276 フレーム目の図で、下記のように __正しく描画されていることが確認__ できます。

* ミニマックス法の場合と異なり、数直線に置換表の評価値が表示されなくなっている
* 真ん中の 5 行目に何も表示されない
* 右下の範囲の説明はすべて黒字で表示されている

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/781c5cbf-275d-47da-9e99-d24eca112e75.png" width="500">

ここまでの確認作業で、__条件 5 以外では正しく描画される__ ことが確認できました。

## 条件 5 の表示の問題点

下図は下記の条件 5 を満たす先程の "tt" のフレームの図の再掲です。

* 置換表に登録されている
* 置換表による枝狩りが行われない
* α 値または β 値の初期値が更新される

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/84847c67-638f-4a27-9b49-800735edab60.png" width="500">

[以前の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#l--%CE%B1--%CE%B2-%E3%81%AE%E5%A0%B4%E5%90%88)で説明したように、条件 5 で行われる __α 値または β 値の初期値の更新__ は、α 値と β 値の初期値の範囲を __置換表の範囲外の値が含まれない__ ように __範囲を狭める方向で更新する__ ことで、__枝狩りの効率を上げる__ という目的で行います。

しかし、上図では黄色で塗りつぶされた __α 値と β 値の初期値の範囲__ のうち __1 ~ 2 の範囲__ が、__赤い矢印の置換表の範囲外__ になっているという問題があります。

実はこのようなことが起きる原因は今回の記事で記述した `update_frameinfo` にはありません。問題の原因は __筆者がうっかり `calc_score_for_anim`__ で __α 値と β 値の初期値を更新する処理を間違えて記述__ してしまったからです。

記事が長くなったので間違いの修正は次回の記事で行うことにします。また、残りの状態の表示の実装も次回の記事で行います。余裕がある方は筆者がどのようなうっかりミスをしたかを探してみて下さい。

# 今回の記事のまとめ

今回の記事では、__αβ 法の視覚化__ のための __Mbtree_Anim の修正__ のうち、__"start" 以外の状態で表示する内容__ の実装と、__"tt" の状態で表示する内容__ の実装を行いました。ただし、現時点では "tt" の状態で表示する内容の一部にバグが存在します。

次回の記事ではバグの修正と残りの表示の実装を行います。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/094fc04eb693b208fa02

[^1]:どちらになるかは、ルートノードの α 値と β 値の初期値を、評価値の最小値と最大値に設定するかどうかで決まります
[^2]:ミニマックス値の範囲の下界と上界が等しい場合も含みます