Pythonで〇×ゲームのAIを一から作成する　その159　αβ 法の視覚化の検討と視覚化に必要なデータの記録

# 目次と前回の記事

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

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

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

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

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

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

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

# αβ 法の視覚化の検討と視覚化に必要なデータの記録

[以前の記事](https://qiita.com/ysgeso/items/ddcbd0cb9ab62656173e#%E5%AE%9F%E8%A3%85%E3%81%AE%E6%89%8B%E9%A0%86%E3%81%AE%E6%A4%9C%E8%A8%8E)で、ミニマックス法と αβ 法の視覚化の実装を下記の手順で行うという説明を行いました。手順 1 ~ 3 については前回の記事で完了したので、手順 4 を行うことにします。

1. __ミニマックス法__ での __視覚化の方法を検討__ する
2. 検討した __視覚化を行うために必要なフレームのデータを記録__ するように __`calc_score_for_anim` を修正__ する
3. __Mbtree_Anim を__ 検討した視覚化を行うように __修正する__
4. αβ 法で上記の 1 ~ 3 の手順を行う

具体的には下記の作業を行います。

1. __αβ 法__ での __視覚化の方法を検討__ する
2. 検討した __視覚化を行うために必要なフレームのデータを記録__ するように __`calc_score_for_anim` を修正__ する
3. __Mbtree_Anim を__ 検討した視覚化を行うに __修正する__

今回の記事では上記の手順 1 と 2 を行います。

## 今回の記事で利用する記号

今回の記事では[以前の記事](https://qiita.com/ysgeso/items/bcd2526d5327fd1e72e9#%E4%BB%8A%E5%9B%9E%E3%81%AE%E8%A8%98%E4%BA%8B%E3%81%A7%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B%E8%A8%98%E5%8F%B7)と同様に以下の記号を使って説明を行ないます。また、今回の記事で用いる用語の意味について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#%CE%B1%CE%B2-%E6%B3%95%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E6%84%8F%E5%91%B3%E3%81%AE%E3%81%8A%E3%81%95%E3%82%89%E3%81%84%E3%81%A8%E7%94%A8%E8%AA%9E%E3%81%AE%E4%BF%AE%E6%AD%A3)を復習して下さい。

|記号|意味|
|:-:|:--|
|$l$|ミニマックス値の下界（lower bound）|
|$u$|ミニマックス値の上界（upper bound）|
|$α$|$α$ 値の初期値 |
|$β$|$β$ 値の初期値 |
|$α 値$|現在の $α$ 値 |
|$β 値$|現在の $β$ 値 |
|$s$|ノードの評価値|
|$c$|子ノードの評価値|
|$min(a, b)$|$a$ と $b$ の最小値 |
|$max(a, b)$|$a$ と $b$ の最大値 |

# αβ 法での視覚化の方法の検討

__αβ 法での視覚化__ をどのように行えば良いかについて少し考えてみて下さい。なお、行う作業は[以前の記事](https://qiita.com/ysgeso/items/ddcbd0cb9ab62656173e#%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95%E3%81%AE%E8%A6%96%E8%A6%9A%E5%8C%96%E3%81%AE%E6%A4%9C%E8%A8%8E)でミニマックス法での視覚化の方法の検討で行った作業とよく似ています。

## αβ 法での視覚化の種類と設定された条件の表示

[以前の記事](https://qiita.com/ysgeso/items/ddcbd0cb9ab62656173e#calc_score_for_anim-%E3%81%8C%E8%A1%8C%E3%81%86%E3%81%93%E3%81%A8%E3%81%8C%E3%81%A7%E3%81%8D%E3%82%8B%E8%A8%88%E7%AE%97%E3%81%AE%E7%A8%AE%E9%A1%9E)で説明したように、__`calc_score_for_anim`__ は下記の 4 つの条件で評価値を計算できます。

* アルゴリズムとして __ミニマックス法__ と __αβ 法__ のいずれかを選択できる（仮引数 `minimax`）
* __置換表を利用するか__ どうかを選択できる（仮引数 `use_tt`）
* __最短の勝利を目指す評価値を計算するか__ どうかを選択できる（仮引数 `shortest_victory`）
* __ルートノードの α 値と β 値の初期値__ を評価値の最小値と最大値に設定するかどうかを選択できる（仮引数 `init_ab`）

従って、αβ 法では $2^3 = 8$ 通りの条件の組み合わせがあります。

__設定された条件の表示方法__ については、[以前の記事](https://qiita.com/ysgeso/items/ddcbd0cb9ab62656173e#%E8%A8%AD%E5%AE%9A%E3%81%95%E3%82%8C%E3%81%9F%E6%9D%A1%E4%BB%B6%E3%81%AE%E8%A1%A8%E7%A4%BA)で __考察済__ です。また、考察した内容の表示のうち、__αβ 法で α 値と β 値を表示する以外の処理__ は[前回の記事](https://qiita.com/ysgeso/items/ad85235816fe59350013#%E5%B8%B8%E3%81%AB%E8%A1%A8%E7%A4%BA%E3%81%99%E3%82%8B%E5%86%85%E5%AE%B9%E3%81%AE%E5%AE%9F%E8%A3%85)で __実装済__ です。

## 表示内容の検討の方針

次に、αβ 法での "start"、"tt"、"score"、"update"、"end" の __5 つのそれぞれの状態のフレーム__ に対して、__どのような表示を行うか__ について検討する必要があります。どのように表示すれば良いかについて少し考えてみて下さい。

なお、本記事では先に表示内容を検討してから、表示の実装を行うという流れで説明を行っていますが、今回の場合のようにある程度以上 __表示内容が複雑になる場合__ は、実際には __表示の実装を行う際__ に検討した __表示内容の不備が見つかったり__、__新たに表示したほうが良い内容を思いつく__ ことが __良くあります__。従って、__実際の作業__ では以下のような __作業の繰り返し__ の __試行錯誤__ によって実装を進めるのが一般的だと思います。今回の実装では実際に筆者もそのような作業を行いましたが、行った作業をそのままの順番で説明すると長くなりすぎるので、本記事では __最終的な実装で行う表示内容を元__ に下記の表示の __検討内容を記しました__。

1. 表示内容を検討する
2. 検討した内容に従って実装を行う
3. 検討の不備が見つかった場合は手順 1 に戻って表示内容を修正する

## 共通する表示内容の検討

最初に、すべての場合で __共通する表示内容__ について検討することにします。

[以前の記事](https://qiita.com/ysgeso/items/ddcbd0cb9ab62656173e#%E5%85%B1%E9%80%9A%E3%81%99%E3%82%8B%E8%A1%A8%E7%A4%BA%E5%86%85%E5%AE%B9%E3%81%AE%E6%A4%9C%E8%A8%8E)でミニマックス法での共通する表示内容として検討した下記の表示に関しては、__ミニマックス法と αβ 法で違いは無い__ ので __同じ表示を行う__ ことにします。

* 数直線
* 選択中のノードの深さ
* ノードの種類
* フレームで行われる処理を表す状態
* 右に表示される「計算済」や「枝狩り」などの、__枝狩りが行われたノードの数などの表示__

__αβ 法での共通する表示内容__ としては、下記の内容が挙げられます

* __α 値と β 値の初期値__
* α 値と β 値の初期値によって分けられる fail low、exact value、fail high の __範囲の色分け__。具体的な色分けの方法については実装の際に検討する
* 色分けされた __範囲の説明__

なお、これらの表示内容は、下図の __`calc_score_by_ab`__ で計算されたデータに対して __Mbtree_Anim__ が行っていた __表示と似ています__。ただし、下図では α 値と β 値の初期値ではなく、__現在の α 値と β 値に対する表示__ が行われている点が __異なる__ ので、実装の際にはその点に注意する必要があります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/44619e04-70e4-4b66-9eda-0ad61e9da354.png" width="450">

以後は、上記の情報を常に表示するという前提で説明を行います。

## 条件による表示の違いの検討

先程説明したように、__αβ 法__ では下記の __3 種類の条件__ で評価値を計算することができます。

* __置換表を利用するか__ どうかを選択できる（仮引数 `use_tt`）
* __最短の勝利を目指す評価値を計算するか__ どうかを選択できる（仮引数 `shortest_victory`）
* __ルートノードの α 値と β 値の初期値__ を評価値の最小値と最大値に設定するかどうかを選択できる（仮引数 `init_ab`）

5 つの状態の中で、__置換表を利用するかどうか__ によって __行う処理が変わる__ のは __`"tt"`__ と __`"end"`__ の状態のフレームだけで、以下のように異なります。従って、__`"end"` のフレームの表示のみ__、置換表を利用するかどうかで __表示が変わる場合があります__。

* __`"tt"`__ のフレームの処理は __置換表を利用する場合のみ__ 行なわれる
* __`"end"`__ のフレームの処理では、__置換表を利用する場合のみ__ 計算されたミニマックス値の範囲を __置換表に登録または更新する処理が行われる__ 場合がある[^1]

__最短の勝利を目指す評価値を計算するかどうか__ によって変わるのは、__決着がついたノードの評価値の計算方法だけ__ で、それ以外の処理は全く変わりません。そのため、5 つの状態の表示方法は __数直線の表示範囲を変えるという工夫以外__ では __共通します__。これは、ミニマックス法の場合と同様でその表示は、[前回の記事](https://qiita.com/ysgeso/items/ad85235816fe59350013#%E6%95%B0%E7%9B%B4%E7%B7%9A%E3%81%AE%E6%8F%8F%E7%94%BB)で既に実装済です。

__ルートノードの α 値と β 値の初期値を評価値の最小値と最大値に設定するか__ どうかによって変わるのは以下の通りです。

* 各ノードの評価値を計算する際の __α 値と β 値の初期値__
* 各ノードの __ミニマックス値の下界の最小値__ が負の無限大でく評価値の最小値となる
* 各ノードの __ミニマックス値の上界の最大値__ が正の無限大でく評価値の最大値となる

上記の考察を元に、5 つのそれぞれの状態での表示方法を検討することにします。

### "start" の状態の表示

__ノードの処理の開始__ を表す __"start"__ の状態のフレームでは、常に表示する内容を除いて __特に何かを表示する必要はない__ でしょう。

### "tt" の状態の表示

__置換表に関する処理が行われた__ ことを表す __"tt"__ の状態のフレームでは以下の処理が行われます。

* ノードのミニマックス値の範囲が __置換表に登録されている場合__
    * 置換表に登録されているミニマックス値の __下界__（$l$）__と上界__（$u$）__が等しい__（$l = u$）場合は $l$（または $u$）をそのノードの評価値とする
    * $u ≦ α$（__ミニマックス値の範囲が fail low に完全に含まれている__）の場合は $u$ をそのノードの評価値とする
    * $β ≦ l$（__ミニマックス値の範囲が fail high に完全に含まれている__）の場合は $l$ をそのノードの評価値とする
    * 上記の __どれでもない場合__ は __α 値と β 値の初期値__ を下記のように __更新して__ 子ノードの評価値から __このノードの評価値を計算__ する
* ノードのミニマックス値の範囲が __置換表に登録されていない場合__ は子ノードの評価値から __このノードの評価値を計算__ する

上記の __違いがわかるような表示__ として、下記の表示を行うことにします。

まず、ノードのミニマックス値の範囲が __置換表に登録されているかどうか__ によって、__ミニマックス法の場合と同様__ に下記の表示を行うことにします。

| 置換表の登録 | 表示 |
|:--|:--|
| __あり__  | 赤字で「置換表に登録済」  |
| __なし__  | 黒字で「置換表に未登録」 |


ミニマックス法の場合は置換表にそのノードの評価値が登録されていた場合は数直線上にその評価値を表示していましたが、__αβ 法__ では置換表には __ミニマックス値の範囲が記録__ されるので、下記のような表示を行うことにします。その際に __置換表の登録の有無__ を何らかの方法で __区別してわかるように表示する__ ことにします。また、この __ミニマックス値の範囲__ は __"score"__、__"update"__、__"end" の状態でも表示__ することにします。

| 置換表の登録 | 表示 |
|:--|:--|
| __あり__  | __ミニマックス値の範囲__（下界と上界）を何らかの方法で表示する  |
| __なし__  | 下界を負の無限大または評価値の最小値、上界を正の無限大または評価値の最大値として、__ミニマックス値の範囲__ を何らかの方法で表示する |

また、置換表に登録されている場合は下記の表のような表示を行うことにします。

| 条件 | 表示 |
|:--|:--|
| $l = u$  | 赤字で「置換表による枝狩り（exact value）」  |
| $u ≦ α$  | 赤字で「置換表による枝狩り（fail low）」  |
| $β ≦ l$  | 赤字で「置換表による枝狩り（fail high）」  |
| 上記以外で α 値と β 値の初期値が更新  | 赤字で「α 値または β 値の初期値の更新」  |

### "score" の状態の表示

ミニマックス法では __子ノードの評価値が計算された__ ことを表す __"score"__ の状態のフレームでは、__数直線上に以下の表示__ を行いました。__αβ 法でも同様の表示__ を行うことにします。

* 計算された __子ノードの評価値__
* 子ノードの評価値で更新する前の、__その時点でのノードの評価値__

αβ 法では上記に加えて __そのフレームでの α 値と β 値__ の情報があるので __それらの情報の表示__ も行うことにします。

### "update" の状態の表示

ミニマックス法では子ノードの評価値を使ってこのノードの __評価値を更新する処理__ を行う __"update"__ の状態のフレームでは、以下の表示を行いました。__αβ 法でも同様の表示__ を行うことにします。

* ノードの __評価値が更新__ された場合は __赤字で「評価値の更新」__ と表示する
* __更新されていない__ 場合は __黒字で「評価値の更新なし」__ と表示する
* いずれの場合でも、__数直線上__ にノードの __評価値を表示する__

__αβ 法__ では上記に加えて __そのフレームでの α 値と β 値の情報__ があるので "score" の状態の場合と同様に __それらの情報の表示__ も行うことにします。

また、__αβ 法__ では __α 狩りまたは β 狩り__ による __枝狩りが行われる場合があ__ るので、下記の表示を行うことにします。

* α 狩りが行われた場合は赤字で「α 狩り」と表示する
* β 狩りが行われた場合は赤字で「β 狩り」と表示する

### "end" の状態の表示

ミニマックス法ではノードの __評価値が確定__ したことを表す __"end"__ の状態のフレームでは、以下の表示を行いました。__αβ 法でも同様の表示を行う__ ことにします。

* __数直線上__ に確定した __ノードの評価値を表示__ する

ミニマックス法では置換表に評価値が登録されていた場合は、必ずその評価値をそのノードの評価値として利用し、置換表による子孫ノードの枝狩りが行われましたが、__置換表付き αβ 法__ では __置換表に__ ミニマックス値の範囲が __登録されていた場合でも__ 置換表による __枝狩りが行われない場合__ があります。そこで下記のように表示することにします。

* 置換表を __利用する場合__ は、以下の表示を行う
    * __置換表による枝狩り__ が __行われた場合__ は __黒字で「置換表に登録されていたデータを利用」__ と表示する
    * 置換表による枝狩りが __行われなかった場合__ はこのノードの評価値を元に計算されたミニマックス値の範囲が置換表に登録または更新されるので __赤字で「置換表への登録」__ と表示する
* 置換表を __利用しない場合__ は __何も表示しない__

また、置換表を利用する場合で、__置換表による枝狩りが行われなかった場合__ は、[以前の記事](https://qiita.com/ysgeso/items/20317d7b67518a119382#%E7%BD%AE%E6%8F%9B%E8%A1%A8%E4%BB%98%E3%81%8D-%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E6%9E%9D%E7%8B%A9%E3%82%8A%E3%81%AE%E5%8A%B9%E7%8E%87%E5%8C%96)で説明した方法で置換表に登録するミニマックス値の計算を行います。

* 「__置換表に登録されていたミニマックス値の範囲__」[^2]と子ノードの評価値を計算することで「得られた評価値によって決まるミニマックス値の範囲」の共通部分を計算する
* 計算された共通部分をミニマックス値の範囲として置換表に登録または更新する

なお、本記事では __3 種類のミニマックス値の範囲__ を __区別できるよう__ に、それぞれを以下の表のように短く表記することにします。

| 表記 | 意味 |
|:--|:--|
| __置換表の範囲__  | 置換表に登録されていたミニマックス値の範囲  |
| __計算された範囲__  | 子ノードの評価値から計算されたミニマックス値の範囲  |
| __登録する範囲__  | 置換表に登録する、上記の 2 つの共通する範囲  |

__登録する範囲__ が __どのように計算されたかがわかる__ ように下記の表示を行うことにします。

* 「計算された範囲」を何らかの方法で表示する
* 「登録する範囲」を何らかの方法で表示する

ミニマックス法ではすべてのノードで必ず正しい評価値が計算されますが、__αβ 法__ では __fail low__、__exact value__、__fail high__ の __3 種類の評価値が計算される__ ので、それぞれの場合で __フレームの状態を表す文字列__ として下記の表示を行うことにします。なお、__計算された評価値__ が fail low や fail high の範囲であったとしても、登録する範囲が __範囲を持たない（下界 = 上界）場合__ は正確なミニマックス値が計算されるので __exact value とみなす__ ことにします。

| 評価値の種類 | 表示 |
|:--|:--|
| __fail low__  |  評価値の確定（fail low） |
| __exact value__  | 評価値の確定（exact value）  |
| __fail high__  | 評価値の確定（fail high）  |

# 表示内容と表示に必要な情報の検討

表示する内容が検討できたので、上記で検討した __表示内容を整理__ し、その内容を __表示するために必要な情報を検討__ します。

## 常に表示する内容

常に表示する内容と、表示するために必要な情報は以下の表の通りです。[以前の記事](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）」を表示
    * 置換表を利用する場合
        * 置換表による枝狩りが行われた場合
            * （※）黒字で「置換表に登録されていたデータを利用」を表示
        * 置換表による枝狩りが行われていない場合
            * （※）赤字で「置換表への登録」を表示
            * 計算された範囲
            * 登録する範囲

また、それぞれの状態で必要となる情報は以下の通りです。__そのフレームでの α 値と β 値__ はそれぞれ $max(α, s)$、$min(β, s)$ で __計算できる__ ので、フレームの情報に __記録する必要はありません__。なお、ミニマックス法と共通する内容には先頭に（※）を記述しました。

* __"start"__ の状態
    * なし
* __"tt"__ の状態
    * （※）置換表にノードの評価値が登録されているかどうか
    * 置換表による枝狩りが行われたかどうか
    * ミニマックス値の上界と下界
* __"score"__ の状態
    * （※）そのフレームでのノードの評価値
    * （※）子ノードの評価値
    * ミニマックス値の上界と下界
* __"update"__ の状態
    * （※）そのフレームでのノードの評価値
    * （※）ノードの評価値が更新されたかどうか
    * ミニマックス値の上界と下界
    * α 狩りまたは β 狩りが行われたかどうか 
* __"end"__ の状態
    * （※）そのフレームでのノードの評価値
    * ミニマックス値の上界と下界
    * ノードの評価値の種類
    * 置換表による枝狩りが行われたかどうか
    * 置換表による枝狩りが行われた場合
        * 子ノードの評価値の計算によって計算されたミニマックス値の下界と上界
        * 置換表に登録または更新するミニマックス値の下界と上界

それぞれの状態で __必要となるデータを表にまとめる__ と以下のようになります。データが必要な場合は 〇 を表記しました。ミニマックス法と共通する内容には先頭に（※）を記述しました。なお、__置換表の範囲__[^3] と __置換表に登録されているかどうか__ はミニマックス法でも記録していましたが __"score" と "update" の状態でも記録する__ ようになった点が __異なります__。

|データ|start|tt|score|update|end|
|:--|:-:|:-:|:-:|:-:|:-:|
|α 値と β 値の初期値 |〇|〇|〇|〇|〇|
|置換表に登録されているかどうか|×|〇|〇|〇|〇|
|置換表の範囲|×|〇|〇|〇|〇|
|置換表による枝狩りが行われたかどうか |×|〇|×|×|〇|
|α 値または β 値の初期値が更新されたかどうか|×|〇|×|×|×|
|α 狩りまたは β 狩りが行われたかどうか|×|×|×|〇|×|
|ノードの評価値の種類 |×|×|×|×|〇|
|計算された範囲 |×|×|×|×|〇|
|登録する範囲 |×|×|×|×|〇|
|（※）置換表に登録されていた評価値|×|〇|×|×|×|×|
|（※）そのフレームでのノードの評価値|×|×|〇|〇|〇|
|（※）子ノードの評価値|×|×|〇|×|×|
|（※）ノードの評価値が更新されたかどうか|×|×|×|〇|×|

# `calc_score_for_anim` の修正

表示に必要なデータが整理できたので、__上記のデータを記録する__ ように __`calc_score_for_anim` を修正__ することにします。

## 必要なデータを記録する dict のデータ構造

下記の表は　__`ablist_by_score`__ に記録する __フレームの情報を表す dict__ に __どのように上記の表のデータを記録するか__ を表した表です。（※）はミニマックス法でも記録していましたが、__ミニマックス法とは異なるフレームの状態でも記録する__ という点が異なります。

|キー|キーの値の意味|
|:--|:--|
|__"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"__|登録する範囲の上界|

__ミニマックス法__ では __枝狩りは置換表に登録されている場合のみ行われる__ ので __置換表に登録されているかどうか__ を __`"pruned"`__ というキーの値に代入していました。__αβ 法の場合__ は __枝狩りは__ 置換表に登録されている場合と、α 狩りまたは β 狩りが行われる場合の __2 種類がある__ ので、上記の表のように __置換表（transposition table）によって__ 枝狩りが行われたかどうかを __`"tt_pruned"`__、__α 狩りまたは β 仮によって__ 枝狩りが行われたかどうかを __`"ab_pruned"`__ という名前の __キーで区別する__ ことにします。

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

下記は上記のデータを記録するように Mbtree クラスの __`calc_score_for_anim`__ メソッドを修正したプログラムです。非常に長いように見えるかもしれませんが、行っている修正はそれほど難しいものではありません。

* __6 ~ 12、44 ~ 55、69 ~ 80、98 ~ 110、144 ~ 160 行目__：それぞれの状態で必要な情報を記録するように修正する
* __15 行目__：置換表によって枝狩りが行われたかどうかを表す変数 `tt_pruned` を `False` で初期化する。元のプログラムではこの情報は "tt" のフレームのみで記録していたので 17 行目の後で初期化を行っていたが、"end" のフレームでも記録するようになったので 16 行目の if 文の前に移動した。また、変数の名前を `"tt_pruned"` に修正した
* __26、29、32、41、48、60 行目__：`pruned` を `tt_pruned` に修正した
* __18、34 行目__：18 行目で α 値または β 値の初期値が更新されたかどうかを表す `ab_updated` を `False` で初期化し、34 行目で更新された場合に `True` を代入する
* __56 ~ 58 行目__：`lower_bound` と `upper_bound` を "tt" 以外の状態でも記録するようになったので、置換表を利用しない場合の `lower_bound` と `upper_bound` の値に置換表に登録されていない場合の 38、39 行目と同じ値を代入するように修正した
* __63 行目__：元のプログラムでは `pruned` という 1 つの変数で枝狩りが行われたことを表していたが、枝狩りの区別を行う必要が生じたので α 狩りまたは β 狩りが行われたことを表す `ab_pruned` を `False` で初期化するように修正した
* __86、92、94、111 行目__：`pruned` を `ab_pruned` に修正した
* __114 ~ 133 行目__：元のプログラムでは置換表を利用する場合のみ下界と上界を更新する処理を行っていたが、その処理を常に行うようにし、下記の計算を行うように修正した。なお、置換表を利用しない場合など、下記で計算した値が Mbtree_Anim での表示で利用されない場合があるが、利用しない値を計算して記録してもそれらの記録が無駄になるだけで間違った処理が行われるという問題は発生しない
    * 評価値の種類表す文字列を `score_type` に代入する。ただし、登録する範囲が範囲を持たない場合は 132、133 行目の処理で "exact value" とした
    * 計算された範囲を `clower_bound` と `cupper_bound` に計算するようにした
    * 登録する範囲を `tlower_bound` と `tupper_bound` に計算するようにした
* __140 行目__：`lower_bound` と `upper_bound` を `tlower_bound` と `tupper_bound` に修正した

```python
  1  from marubatsu import Marubatsu
  2  from tree import Mbtree
  3  
  4  def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
元と同じなので省略
  5      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
元と同じなので省略
  6          self.ablist_by_score.append({
  7              "status": "start",
  8              "alphaorig": alphaorig,
  9              "betaorig": betaorig,
 10              "num_calculated": self.num_calculated,
 11              "num_pruned": self.num_pruned,
 12          })
 13          
 14          registered_in_tt = False
 15          tt_pruned = False
 16          if node.mb.status != Marubatsu.PLAYING:
元と同じなので省略
 17          else:
 18              ab_updated = False
 19              if use_tt:
 20                  boardtxt = node.mb.board_to_str()
 21                  if boardtxt in tt:
 22                      registered_in_tt = True
 23                      lower_bound, upper_bound = tt[boardtxt]
 24                      if lower_bound == upper_bound:
 25                          node.score = lower_bound
 26                          tt_pruned = True
 27                      elif upper_bound <= alphaorig:
 28                          node.score = upper_bound
 29                          tt_pruned = True
 30                      elif betaorig <= lower_bound:
 31                          node.score = lower_bound
 32                          tt_pruned = True
 33                      else:
 34                          ab_updated = alphaorig > lower_bound or betaorig < upper_bound
 35                          alphaorig = min(alphaorig, lower_bound)
 36                          betaorig = max(betaorig, upper_bound)
 37                  else:
 38                      lower_bound = min_score
 39                      upper_bound = max_score
 40                  self.nodelist_by_score.append(node)
 41                  if tt_pruned:
 42                      for childnode in node.children:
 43                          assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
 44                  self.ablist_by_score.append({
 45                      "status": "tt",
 46                      "alphaorig": alphaorig,
 47                      "betaorig": betaorig,
 48                      "tt_pruned": tt_pruned,
 49                      "ab_updated": ab_updated,
 50                      "registered_in_tt": registered_in_tt,
 51                      "lower_bound": lower_bound,
 52                      "upper_bound": upper_bound,
 53                      "num_calculated": self.num_calculated,
 54                      "num_pruned": self.num_pruned,
 55                  })   
 56              else:
 57                  lower_bound = min_score
 58                  upper_bound = max_score
 59                          
 60              if not tt_pruned:
 61                  alpha = alphaorig
 62                  beta = betaorig
 63                  ab_pruned = False
 64                  maxnode = node.mb.turn == Marubatsu.CIRCLE
 65                  node.score = min_score if maxnode else max_score
 66                  for childnode in node.children:
 67                      childscore = calc_node_score(childnode, tt, alpha, beta)
 68                      self.nodelist_by_score.append(node)
 69                      self.ablist_by_score.append({
 70                          "status": "score",
 71                          "alphaorig": alphaorig,
 72                          "betaorig": betaorig,
 73                          "score": node.score,
 74                          "childscore": childscore,
 75                          "registered_in_tt": registered_in_tt,
 76                          "lower_bound": lower_bound,
 77                          "upper_bound": upper_bound,
 78                          "num_calculated": self.num_calculated,
 79                          "num_pruned": self.num_pruned,
 80                      })   
 81                      if maxnode:
 82                          updated = node.score < childscore
 83                          node.score = max(node.score, childscore)
 84                          alpha = max(node.score, alpha)
 85                          if node.score >= beta:
 86                              ab_pruned = True
 87                      else:
 88                          updated = node.score > childscore
 89                          node.score = min(node.score, childscore)
 90                          beta = min(node.score, beta)
 91                          if node.score <= alpha:
 92                              ab_pruned = True
 93                      self.nodelist_by_score.append(node)
 94                      if ab_pruned:
 95                          index = node.children.index(childnode)
 96                          for prunednode in node.children[index + 1:]:
 97                              assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
 98                      self.ablist_by_score.append({
 99                          "status": "update",
100                          "alphaorig": alphaorig,
101                          "betaorig": betaorig,
102                          "score": node.score,
103                          "registered_in_tt": registered_in_tt,
104                          "updated": updated,
105                          "ab_pruned": ab_pruned,
106                          "lower_bound": lower_bound,
107                          "upper_bound": upper_bound,
108                          "num_calculated": self.num_calculated,
109                          "num_pruned": self.num_pruned,
110                      })   
111                      if ab_pruned:
112                          break 
113                      
114          if node.score <= alphaorig:
115              score_type = "fail low"
116              clower_bound = min_score
117              cupper_bound = node.score
118              tlower_bound = lower_bound
119              tupper_bound = node.score
120          elif node.score < betaorig:
121              score_type = "exact value"
122              clower_bound = node.score
123              cupper_bound = node.score
124              tlower_bound = node.score
125              tupper_bound = node.score
126          else:
127              score_type = "fail high"
128              clower_bound = node.score
129              cupper_bound = max_score
130              tlower_bound = node.score
131              tupper_bound = upper_bound
132          if tlower_bound == tupper_bound:
133              score_type = "exact value"
134  
135          if use_tt:
136              from util import calc_same_boardtexts
137              
138              boardtxtlist = calc_same_boardtexts(node.mb)
139              for boardtxt in boardtxtlist:
140                  tt[boardtxt] = (tlower_bound, tupper_bound) 
141  
142          self.nodelist_by_score.append(node)
143          self.num_calculated += 1     
144          self.ablist_by_score.append({
145              "status": "end",
146              "alphaorig": alphaorig,
147              "betaorig": betaorig,
148              "score": node.score,
149              "registered_in_tt": registered_in_tt,
150              "tt_pruned": tt_pruned,
151              "score_type": score_type,
152              "lower_bound": lower_bound,
153              "upper_bound": upper_bound,
154              "clower_bound": clower_bound,
155              "cupper_bound": cupper_bound,
156              "tlower_bound": tlower_bound,
157              "tupper_bound": tupper_bound,
158              "num_calculated": self.num_calculated,
159              "num_pruned": self.num_pruned,
160          })   
161          node.score_index = len(self.nodelist_by_score) - 1          
162          return node.score                
163  
元と同じなので省略
164      
165  Mbtree.calc_score_for_anim = calc_score_for_anim
```

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

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

def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
    def assign_pruned_index(node, index):
        node.pruned_index = index
        self.num_pruned += 1
        for childnode in node.children:
            assign_pruned_index(childnode, index)
            
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        if minimax:
            alphaorig = float("-inf")
            betaorig = float("inf")            

        self.nodelist_by_score.append(node)
        self.ablist_by_score.append({
            "status": "start",
            "alphaorig": alphaorig,
            "betaorig": betaorig,
            "num_calculated": self.num_calculated,
            "num_pruned": self.num_pruned,
        })
        
        registered_in_tt = False
        tt_pruned = False
        if node.mb.status != Marubatsu.PLAYING:        
            self.calc_score_of_node(node)
            lower_bound = node.score
            upper_bound = node.score
        else:
            ab_updated = False
            if use_tt:
                boardtxt = node.mb.board_to_str()
                if boardtxt in tt:
                    registered_in_tt = True
                    lower_bound, upper_bound = tt[boardtxt]
                    if lower_bound == upper_bound:
                        node.score = lower_bound
                        tt_pruned = True
                    elif upper_bound <= alphaorig:
                        node.score = upper_bound
                        tt_pruned = True
                    elif betaorig <= lower_bound:
                        node.score = lower_bound
                        tt_pruned = True
                    else:
                        ab_updated = alphaorig > lower_bound or betaorig < upper_bound
                        alphaorig = min(alphaorig, lower_bound)
                        betaorig = max(betaorig, upper_bound)
                else:
                    lower_bound = min_score
                    upper_bound = max_score
                self.nodelist_by_score.append(node)
                if tt_pruned:
                    for childnode in node.children:
                        assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
                self.ablist_by_score.append({
                    "status": "tt",
                    "alphaorig": alphaorig,
                    "betaorig": betaorig,
                    "tt_pruned": tt_pruned,
                    "ab_updated": ab_updated,
                    "registered_in_tt": registered_in_tt,
                    "lower_bound": lower_bound,
                    "upper_bound": upper_bound,
                    "num_calculated": self.num_calculated,
                    "num_pruned": self.num_pruned,
                })
            else:
                lower_bound = min_score
                upper_bound = max_score
        
            if not tt_pruned:
                alpha = alphaorig
                beta = betaorig
                ab_pruned = False
                maxnode = node.mb.turn == Marubatsu.CIRCLE
                node.score = min_score if maxnode else max_score
                for childnode in node.children:
                    childscore = calc_node_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append({
                        "status": "score",
                        "alphaorig": alphaorig,
                        "betaorig": betaorig,
                        "score": node.score,
                        "childscore": childscore,
                        "registered_in_tt": registered_in_tt,
                        "lower_bound": lower_bound,
                        "upper_bound": upper_bound,
                        "num_calculated": self.num_calculated,
                        "num_pruned": self.num_pruned,
                    })   
                    if maxnode:
                        updated = node.score < childscore
                        node.score = max(node.score, childscore)
                        alpha = max(node.score, alpha)
                        if node.score >= beta:
                            ab_pruned = True
                    else:
                        updated = node.score > childscore
                        node.score = min(node.score, childscore)
                        beta = min(node.score, beta)
                        if node.score <= alpha:
                            ab_pruned = True
                    self.nodelist_by_score.append(node)
                    if ab_pruned:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append({
                        "status": "update",
                        "alphaorig": alphaorig,
                        "betaorig": betaorig,
                        "score": node.score,
                        "registered_in_tt": registered_in_tt,
                        "updated": updated,
                        "ab_pruned": ab_pruned,
                        "lower_bound": lower_bound,
                        "upper_bound": upper_bound,
                        "num_calculated": self.num_calculated,
                        "num_pruned": self.num_pruned,
                    })   
                    if ab_pruned:
                        break 
                    
        if node.score <= alphaorig:
            score_type = "fail low"
            clower_bound = min_score
            cupper_bound = node.score
            tlower_bound = lower_bound
            tupper_bound = node.score
        elif node.score < betaorig:
            score_type = "exact value"
            clower_bound = node.score
            cupper_bound = node.score
            tlower_bound = node.score
            tupper_bound = node.score
        else:
            score_type = "fail high"
            clower_bound = node.score
            cupper_bound = max_score
            tlower_bound = node.score
            tupper_bound = upper_bound
        if tlower_bound == tupper_bound:
            score_type = "exact value"

        if use_tt:
            from util import calc_same_boardtexts
            boardtxtlist = calc_same_boardtexts(node.mb)
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (tlower_bound, tupper_bound) 

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append({
            "status": "end",
            "alphaorig": alphaorig,
            "betaorig": betaorig,
            "score": node.score,
            "registered_in_tt": registered_in_tt,
            "tt_pruned": tt_pruned,
            "score_type": score_type,
            "lower_bound": lower_bound,
            "upper_bound": upper_bound,
            "clower_bound": clower_bound,
            "cupper_bound": cupper_bound,
            "tlower_bound": tlower_bound,
            "tupper_bound": tupper_bound,
            "num_calculated": self.num_calculated,
            "num_pruned": self.num_pruned,
        })   
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score   
                                    
    self.calculated_by_calc_score_for_anim = True
    self.minimax = minimax
    self.init_ab = init_ab
    self.use_tt = use_tt
    if shortest_victory is not None:
        self.shortest_victory = shortest_victory

    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
        node.pruned_index = float("inf")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    self.num_calculated = 0
    self.num_pruned = 0
    if init_ab:
        min_score = -2 if self.shortest_victory else -1
        max_score = 3 if self.shortest_victory else 1
    else:
        min_score = float("-inf")
        max_score = float("inf")
    calc_node_score(abroot, {}, min_score, max_score)
    total_nodenum = self.num_pruned + self.num_calculated
    ratio = self.num_calculated / total_nodenum * 100
    dprint(debug, "ミニマックス法で計算したか", minimax)    
    dprint(debug, "計算したノードの数",  self.num_calculated)
    dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
    dprint(debug, "合計",  total_nodenum)
    dprint(debug, f"割合 {ratio:.1f}%") 
    
Mbtree.calc_score_for_anim = calc_score_for_anim
```
</details>

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

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

def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
元と同じなので省略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
元と同じなので省略
        self.ablist_by_score.append({
            "status": "start",
+           "alphaorig": alphaorig,
+           "betaorig": betaorig,
            "num_calculated": self.num_calculated,
            "num_pruned": self.num_pruned,
        })
        
        registered_in_tt = False
+       tt_pruned = False
        if node.mb.status != Marubatsu.PLAYING:
元と同じなので省略
        else:
-           pruned = False
+           ab_updated = False
            if use_tt:
                boardtxt = node.mb.board_to_str()
                if boardtxt in tt:
                    registered_in_tt = True
                    lower_bound, upper_bound = tt[boardtxt]
                    if lower_bound == upper_bound:
                        node.score = lower_bound
-                       pruned = True
+                       tt_pruned = True
                    elif upper_bound <= alphaorig:
                        node.score = upper_bound
-                       pruned = True
+                       tt_pruned = True
                    elif betaorig <= lower_bound:
                        node.score = lower_bound
-                       pruned = True
+                       tt_pruned = True
                    else:
                        ab_updated = alphaorig > lower_bound or betaorig < upper_bound
                        alphaorig = min(alphaorig, lower_bound)
                        betaorig = max(betaorig, upper_bound)
                else:
                    lower_bound = min_score
                    upper_bound = max_score
                self.nodelist_by_score.append(node)
-               if pruned:
+               if tt_pruned:
                    for childnode in node.children:
                        assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
                self.ablist_by_score.append({
                    "status": "tt",
+                   "alphaorig": alphaorig,
+                   "betaorig": betaorig,
+                   "tt_pruned": tt_pruned,
+                   "ab_updated": ab_updated,
+                   "registered_in_tt": registered_in_tt,
                    "lower_bound": lower_bound,
                    "upper_bound": upper_bound,
                    "num_calculated": self.num_calculated,
                    "num_pruned": self.num_pruned,
                })   
+           else:
+               lower_bound = min_score
+               upper_bound = max_score                
        
-           if not pruned:
+           if not tt_pruned:
                alpha = alphaorig
                beta = betaorig
+               ab_pruned = False
                maxnode = node.mb.turn == Marubatsu.CIRCLE
                node.score = min_score if maxnode else max_score
                for childnode in node.children:
                    childscore = calc_node_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append({
                        "status": "score",
+                       "alphaorig": alphaorig,
+                       "betaorig": betaorig,
                        "score": node.score,
                        "childscore": childscore,
+                       "registered_in_tt": registered_in_tt,
+                       "lower_bound": lower_bound,
+                       "upper_bound": upper_bound,
                        "num_calculated": self.num_calculated,
                        "num_pruned": self.num_pruned,
                    })   
                    if maxnode:
                        updated = node.score < childscore
                        node.score = max(node.score, childscore)
                        alpha = max(node.score, alpha)
                        if node.score >= beta:
-                           pruned = True
+                           ab_pruned = True
                    else:
                        updated = node.score > childscore
                        node.score = min(node.score, childscore)
                        beta = min(node.score, beta)
                        if node.score <= alpha:
-                           pruned = True
+                           ab_pruned = True
                    self.nodelist_by_score.append(node)
-                   if pruned:
+                   if ab_pruned:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append({
                        "status": "update",
+                       "alphaorig": alphaorig,
+                       "betaorig": betaorig,
                        "score": node.score,
+                       "registered_in_tt": registered_in_tt,
                        "updated": updated,
+                       "ab_pruned": ab_pruned,
+                       "lower_bound": lower_bound,
+                       "upper_bound": upper_bound,
                        "num_calculated": self.num_calculated,
                        "num_pruned": self.num_pruned,
                    })   
-                   if pruned:
+                   if ab_pruned:
                        break 
                    
+       if node.score <= alphaorig:
+           score_type = "fail low"
+           clower_bound = min_score
+           cupper_bound = node.score
+           tlower_bound = lower_bound
+           tupper_bound = node.score
+       elif node.score < betaorig:
+           score_type = "exact value"
+           clower_bound = node.score
+           cupper_bound = node.score
+           tlower_bound = node.score
+           tupper_bound = node.score
+       else:
+           score_type = "fail high"
+           clower_bound = node.score
+           cupper_bound = max_score
+           tlower_bound = node.score
+           tupper_bound = upper_bound
+       if tlower_bound == tupper_bound:
+           score_type = "exact value"

        if use_tt:
            from util import calc_same_boardtexts
            boardtxtlist = calc_same_boardtexts(node.mb)
-           if node.score <= alphaorig:
-               upper_bound = node.score
-           elif node.score < betaorig:
-               lower_bound = node.score
-               upper_bound = node.score
-           else:
-               lower_bound = node.score
            for boardtxt in boardtxtlist:
-               tt[boardtxt] = (lower_bound, upper_bound) 
+               tt[boardtxt] = (tlower_bound, tupper_bound) 

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append({
            "status": "end",
+           "alphaorig": alphaorig,
+           "betaorig": betaorig,
            "score": node.score,
            "registered_in_tt": registered_in_tt,
+           "tt_pruned": tt_pruned,
+           "score_type": score_type,
+           "lower_bound": lower_bound,
+           "upper_bound": upper_bound,
+           "clower_bound": clower_bound,
+           "cupper_bound": cupper_bound,
+           "tlower_bound": tlower_bound,
+           "tupper_bound": tupper_bound,
            "num_calculated": self.num_calculated,
            "num_pruned": self.num_pruned,
        })   
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score                    
元と同じなので省略
    
Mbtree.calc_score_for_anim = calc_score_for_anim
```
</details>

# これまでの処理が正しく行われることの確認

今回の記事の修正で __これまで行えていた処理が正しく行われる__ ことを確認します。

上記の修正後に下記のプログラムで __[以前の記事](https://qiita.com/ysgeso/items/bcd2526d5327fd1e72e9#calc_score_of_anim-%E3%81%AE%E5%AE%9F%E8%A3%85%E3%81%A8%E7%A2%BA%E8%AA%8D)と同じ計算__ を行うと、実行結果から前回の記事と同じ結果が表示されることが確認できます。

```python
mbtree = Mbtree.load("../data/abtree_root")

print("ai_mmdfs")
mbtree.calc_score_for_anim(mbtree.root, minimax=True, init_ab=False, use_tt=False, debug=True)
print()
print("ai_mmdfs_tt")
mbtree.calc_score_for_anim(mbtree.root, minimax=True, init_ab=False, use_tt=True, debug=True)
print()
print("ai_abs_tt")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=False, use_tt=False, debug=True)
print()
print("ai_abs_tt3")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=False, use_tt=True, debug=True)
print()
print("ai_abs_tt4")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=True, use_tt=True, debug=True)
```

実行結果

```
ai_mmdfs
ミニマックス法で計算したか True
計算したノードの数 549946
枝狩りしたノードの数 0
合計 549946
割合 100.0%

ai_mmdfs_tt
ミニマックス法で計算したか True
計算したノードの数 2271
枝狩りしたノードの数 547675
合計 549946
割合 0.4%

ai_abs_tt
ミニマックス法で計算したか False
計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%

ai_abs_tt3
ミニマックス法で計算したか False
計算したノードの数 1173
枝狩りしたノードの数 548773
合計 549946
割合 0.2%

ai_abs_tt4
ミニマックス法で計算したか False
計算したノードの数 832
枝狩りしたノードの数 549114
合計 549946
割合 0.2%
```

また、実行結果は省略しますが下記のプログラムで `calc_score_for_anim` でミニマックス法で評価値を計算したデータに対して Mbtree_Anim で評価値の計算手順を表示すると、__[前回の記事](https://qiita.com/ysgeso/items/ad85235816fe59350013#%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%82%92%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B%E5%A0%B4%E5%90%88)と同じ表示が行われる__ ことが確認できます。実際に確認してみて下さい。

```python
from tree import Mbtree_Anim

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

# 今回の記事のまとめ

今回の記事では、__`calc_score_for_anim`__ で __αβ 法で評価値を計算したデータ__ を Mbtree_Anim で __視覚化する方法について検討__ し、そのために __必要なデータを記録する__ ように __`calc_score_for_anim` を修正__ しました。

次回の記事では Mbtree_Anim を修正して実際の視覚化を行うことができるようにします。

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

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

# 次回の記事

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

[^1]:ミニマックス法の場合との違いは、置換表に登録だけでなく __更新する処理__ が __行われる場合がある__ という点です
[^2]:置換表にミニマックス値が登録されていない場合はミニマックス値の下界を負の無限大または評価値の最小値、上界を正の無限大または評価値の最大値として計算します
[^3]:ミニマックス法では置換表の範囲の下界（または上界）がミニマックス値となります