Pythonで〇×ゲームのAIを一から作成する　その156　置換表付き αβ 法の視覚化を行うための関数の定義

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/20317d7b67518a119382

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

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

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

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

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

# 置換表付き αβ 法の視覚化を行うための関数の定義

置換表付き αβ 法での評価値の計算手順は複雑なので、これまでと同様に __Mbtree_Anim__ を利用して __視覚化する__ ことにします。現状では Mbtree_Anim でアニメーションを行うために __必要なデータを作成する `calc_score_by_ab`__ は置換表付き αβ 法の計算を行うことができないので、`calc_score_by_ab` を以下のように __修正する必要__ があります。

* __置換表付き αβ 法の計算を行うことができる__ ようにする
* 適切な視覚化を行うことができるように、アニメーションの __フレームに記録するデータを修正__ する

今回の記事では前者の `calc_score_by_ab` が置換表付き αβ 法の計算を行うことができるようにするための修正を行います。後者のフレームに記録するデータの修正は次回の記事で行うことにします。

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

今回の記事では以下の記号を使って説明を行ないます。また、今回の記事で用いる用語の意味について忘れた方は[以前の記事](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$ の最大値 |

## 現状の `calc_score_by_ab` のおさらい

これまでの __[`calc_score_by_ab`](https://qiita.com/ysgeso/items/09a2909f6b44561bd2bf#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3)__ では評価値の計算の際に、__行なわれた処理の種類に応じて__ アニメーションのフレームの情報として __下記の表の状態の情報を記録__ しました。"tt" 以外の状態に関しては[以前の記事](https://qiita.com/ysgeso/items/741c2c18f0bc6fcdba27#%E9%81%B8%E6%8A%9E%E4%B8%AD%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E5%87%A6%E7%90%86%E3%81%8C%E9%96%8B%E5%A7%8B%E3%81%95%E3%82%8C%E3%81%9F%E3%83%95%E3%83%AC%E3%83%BC%E3%83%A0%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)を、"tt" の状態に関しては[以前の記事](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3-%E3%81%9D%E3%81%AE-2)を参照して下さい。

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

下記に現状の `calc_score_by_ab` のプログラムを折りたたんで示します。

<details><summary><strong><code>calc_score_by_ab</code>のプログラム</strong></summary>

```python
def calc_score_by_ab(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False):
    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_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
        if minimax:
            alpha = float("-inf")
            beta = float("inf")
        if use_tt:
            boardtxt = node.mb.board_to_str()
            key = (boardtxt, alpha, beta)
            if key in tt:
                node.score = tt[key]
                if node.mb.turn == Marubatsu.CIRCLE:
                    alpha = node.score
                else:
                    beta = node.score
                self.nodelist_by_score.append(node)
                self.num_calculated += 1     
                for childnode in node.children:
                    assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
                self.ablist_by_score.append((alpha, beta, None, "tt",
                                            self.num_calculated, self.num_pruned))
                node.score_index = len(self.nodelist_by_score) - 1  
                return node.score
                
        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, None, "start",
                                    self.num_calculated, self.num_pruned))
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            if node.mb.turn == Marubatsu.CIRCLE:
                alpha = node.score
            else:
                beta = node.score
        else:
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score",
                                                self.num_calculated, self.num_pruned))
                    if score > alpha:
                        alpha = score
                    self.nodelist_by_score.append(node)
                    if score >= beta:
                        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((alpha, beta, None, "update",
                                                self.num_calculated, self.num_pruned))
                    if score >= beta:
                        break
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score",
                                                self.num_calculated, self.num_pruned))
                    if score < beta:
                        beta = score
                    self.nodelist_by_score.append(node)
                    if score <= alpha:
                        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((alpha, beta, None, "update",
                                                self.num_calculated, self.num_pruned))
                    if score <= alpha:
                        break
                node.score = beta

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append((alpha, beta, None, "end",
                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1  
        if use_tt:
            from util import calc_same_boardtexts   
            
            boardtxtlist = calc_same_boardtexts(node.mb)
            _, alpha, beta = key
            for boardtxt in boardtxtlist:
                tt[(boardtxt, alpha, beta)] = node.score            
        return node.score

    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:
        alpha = -2 if self.shortest_victory else -1
        beta = 3 if self.shortest_victory else 1
    else:
        alpha = float("-inf")
        beta = float("inf")
    calc_ab_score(abroot, {}, alpha, beta)
    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}%")

```
</details>

また、`calc_score_by_ab` 内で定義された、__指定したノードの評価値の計算を行う__ ローカル関数 __`calc_ab_score`__ では下記のアルゴリズムで処理を行っています。なお、下記ではアニメーションの __フレームを記録する処理を太字__ にしました。

1. ミニマックス法の場合は [α 値と β 値をそれぞれ負の無限大と正の無限大にする](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3-%E3%81%9D%E3%81%AE-1)[^1]
2. 置換表を利用する場合で、置換表に[「ノード、α 値と β 値」に対する評価値が記録](https://qiita.com/ysgeso/items/dc738bc54c0f837f6dc5#3-%E3%81%A4%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%82%92%E3%82%AD%E3%83%BC%E3%81%A8%E3%81%99%E3%82%8B%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E4%BF%AE%E6%AD%A3%E6%96%B9%E6%B3%95)されている場合は以下の処理を行う
    1. そのノードの子孫ノードの数を数え、枝狩りが行なわれた数に加える
    2. __"tt" の状態のフレームを記録__ する
    3. 置換表に登録された評価値を返り値として返して処理を終了する
3. ノードの計算の処理を開始する際に __"start" の状態のフレームを記録__ する
4. ゲームの決着がついたリーフノードの場合はゲームの勝敗から評価値を計算し、手順 7 へ移動する
5. max ノードの場合はすべての子ノードに対して以下の処理を行い、α 値をこのノードの評価値として手順 7 へ移動する
    1. 子ノードの評価値 $c$ を計算する
    2. __"score" の状態のフレームを記録__ する
    3. $α 値 = max(α 値, c)$ を計算する（子ノードの評価値が α 値を超えている場合は α 値を子ノードの評価値に更新する）
    4. $β < c$（子ノードの評価値が β 値を超えている）の場合は β 狩りが行なわれるので、残りの子ノードの子孫ノードの数を数えて枝狩りが行われた数に加える
    5. __"update" の状態のフレームを記録__ する
    6. $β < c$（β 狩りが行なわれている）の場合は、残りの子ノードの処理を省略する
6. min ノードの場合はすべての子ノードに対して以下の処理を行い、β 値をこのノードの評価値として手順 7 へ移動する
    1. 子ノードの評価値 $c$ を計算する
    2. __"score" の状態のフレームを記録__ する
    3. $β 値 = min(β 値, c)$ を計算する
    4. $c < α$ の場合は α 狩りが行なわれるので、残りの子ノードの子孫ノードの数を数えて枝狩りが行われた数に加える
    5. __"update" の状態のフレームを記録__ する
    6. α 狩りが行なわれている場合は、残りの子ノードの処理を省略する
7. __"end" の状態のフレームを記録__ する
8. 置換表を利用する場合は置換表に「ノード、α 値と β 値」に対する評価値を記録する
9. 計算した評価値を返り値として返す

## アルゴリズムの修正

上記のアルゴリズムは __置換表付き αβ 法の処理には対応していない__ ので、`calc_score_by_ab` で __置換表付き αβ 法の処理を行えるようにする__ ためには、上記のアルゴリズムを修正する必要があります。また、その際に上記のアルゴリズムにはいくつか __わかりづらい点がある__ のでそれらの点についても修正することにします。どのように修正すればよいかについて少し考えてみて下さい。

### 記録するフレームの状態の共通化

上記のアルゴリズムでは、__置換表を利用する場合と利用しない場合__ で __記録するフレームの状態が大きく異なる__ 場合があります。

具体的には __置換表を利用する場合__ で __置換表に評価値が登録されている場合__ は __手順 2__ で「__"tt" の状態のフレームのみを記録__」 して __処理を終了__ します。

一方で、__それ以外の場合__ は __下記のような順番でフレームが記録__ されます。

1. "start" の状態のフレームを記録する
2. 子ノードの数だけ "start" と "score" の状態のフレームを記録する。ただし、枝狩りが行われた場合は残りの子ノードの記録は省略する
3. "end" の状態のフレームを記録する

このように、状況に応じて __全く異なるアニメーションのフレームが記録__ されるのは __わかりづらい__ という問題があるので、__置換表を利用する場合__ は __下記のような順番__ でフレームを記録することにします。

なお、元のアルゴリズムでは置換表に評価値が登録されていた場合は必ずその評価値が採用されていましたが、置換表付き αβ 法では __置換表に登録されたデータ__ が __必ず評価値として採用されるとは限らない__ ので、下記の手順 2 ではその点を考慮しています。

1. "start" の状態のフレームを記録する
2. __置換表に関する処理を行ったことを表す "tt"__ の状態のフレームを記録する。置換表に記録されたデータからこのノードの評価値が計算される場合は手順 3 を飛ばして手順 4 に移動する
3. 子ノードの数だけ "score" と "update" の状態のフレームを記録する。ただし、枝狩りが行われた場合は残りの子ノードの記録は省略する
4. "end" の状態のフレームを記録する

上記のように変更することで、置換表を利用するかどうかに関わらず __フレームの記録の方法__ が下記のように __共通化されます__。

* ノードの処理に対するフレームの記録が __常に "start" の状態ではじまり__、__"end" の状態で終了する__ ようになる
* __ノードの評価値__ が __必ず "end" の状態のフレームで確定__ する
* 子ノードの評価値を計算する場合は、計算した子ノードの数だけ "score" と "update" の状態のフレームを記録する

また、__置換表を利用する場合__ は __"start" の直後に "tt" の状態__ のフレームが記録されるようになり、__"tt" の状態のフレームの意味__ が下のように __変わります__。

* 変更前：ノードの評価値が確定し、置換表による枝狩りが行われた
* 変更後：置換表に関する処理が行われた（ノードの評価値はこの時点では確定しない）

### max ノードと min ノードの処理の統合

これまでは __わかりやすさを重視__ して __max ノード__ の場合と __min ノード__ の場合の処理を先程のアルゴリズムの __手順 5 と 手順 6 のように分けていました__。__`ai_abs_tt3`__ などの __AI の関数__ では max ノードと min ノードで分けた場合に __それぞれで行う処理が少ない__ ので __問題はありませんでした__ が、__`calc_score_by_ab`__ の場合は __フレームに情報を記録する処理__ や、__枝狩りが行われたノードの数を計算する処理__ が必要となるため、それらの処理を分けて記述すると __プログラムがかなり長くなる__ ためかえって __わかりづらくなる__ という問題があります。また、先程のアルゴリズムの __手順 5 と 手順 6__ で行う処理の __多くは共通している__ ので下記のように __統合する__ ことにします。

:::note
子ノードの評価値の符号を反転させ、α 値と β 値入れ替えて符号を反転させるという、[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E3%83%8D%E3%82%AC%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95%E3%81%A8%E3%83%8D%E3%82%AC%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E6%B3%95)で簡単に言及した __ネガアルファ法__ でまとめるという方法もありますが、α 値と β 値が入れ替わるなど、__プログラムの意味が見た目からかなりわかりづらくなる__ ので本記事では採用しません。ただし、αβ 法をネガアルファ法で実装することは実際によくあるので興味がある方は実装してみて下さい。なお、ネガアルファ法による実装例については下記の Wikipedia などを参考にするとよいでしょう。
:::

https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E3%83%BB%E3%83%99%E3%83%BC%E3%82%BF%E6%B3%95

なお、__`calc_score_by_ab`__ では max ノードでは __α 値がそのノードの評価値となるように計算__ していましたが、[以前の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#ai_abs_tt2-%E3%81%AE%E5%AE%9A%E7%BE%A9)で __ノードの評価値を α 値とは別に計算することにした__ ので、その修正も行ないます。min ノードでも同様です。

1. ノードの評価値 $s$ を max ノードの場合は負の無限大（または評価値の最小値でも良い）、min ノードの場合は正の無限大（または評価値の最大値でも良い）で初期化する
2. すべての子ノードに対して以下の処理を行う
    1. 子ノードの評価値 $c$ を計算する
    2. __"score" の状態のフレームを記録__ する
    3. max ノードの場合は下記の処理を行う
        1. ノードの評価値 $s$ を $s = max(s, c)$ とする
        2. α 値を $α 値 = max(α 値, s)$ とする
        3. $β < s$ の場合は β 狩りが行なわれるので、残りの子ノードの子孫ノードの数を数えて枝狩りが行われた数に加える
    4. min ノードの場合は下記の処理を行う
        1. ノードの評価値 $s$ を $s = min(s, c)$ とする
        2. β 値を $β 値 = min(β 値, s)$ とする
        3. $s < α$ の場合は α 狩りが行なわれるので、残りの子ノードの子孫ノードの数を数えて枝狩りが行われた数に加える
    5. __"update" の状態のフレームを記録__ する
    6. α 狩りまたは β 狩りが行われた場合は残りの子ノードの処理を省略する

### 置換表付き αβ 法への対応

最後に、__置換表を利用する場合__ のアルゴリズムを[前回の記事](https://qiita.com/ysgeso/items/20317d7b67518a119382#ai_abs_tt3-%E3%81%AE%E5%AE%9A%E7%BE%A9)で説明した __置換表付き αβ 法が行う処理に修正__ する必要があります。

また、フレームにノードの情報を記録する処理に関する以下のような修正も行いました。

* 置換表付き αβ 法では、決着がついた __リーフノードの評価値の計算__ に __置換表は利用しない__ ので、その処理を行う下記の __手順 3__ を、置換表の処理を行う __手順 4 の前に移動__ した
* __リーフノードの場合__ でも __"end" の状態のフレームを記録する必要がある__ ので、リーフノードの場合は __手順 3 の実行後__ に処理を終了せずに __手順 6 へ移動__ するようにした
* __"end" のフレームに置換表の更新の情報を記録__ できるようにするために、置換表に情報を記録する __手順 7 を__ フレームに "end" の状態の情報を記録する __手順 8 の前に移動__ した

下記はそのように修正したアルゴリズムです。

1. ミニマックス法の場合は [α 値と β 値をそれぞれ負の無限大と正の無限大にする](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3-%E3%81%9D%E3%81%AE-1)
2. ノードの計算の処理を開始する際に __"start" の状態のフレームを記録__ する
3. ゲームの決着がついたリーフノードの場合はゲームの勝敗から評価値を計算し、手順 6 へ移動する
4. 置換表を利用する場合は以下の処理を行う
    1. 置換表にノードの評価値の範囲の情報が記録されている場合は以下の処理を行う
        1. 置換表から $l$（下界）と $u$ （上界）を取り出す
        2. $l = u$ の場合は $l$ をそのノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
        3. $u < α$ の場合は fail low なので $u$ をそノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
        4. $β < l$ の場合は fail high なので $l$ をそノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
        5. それ以外の場合は $α = min(α, l)$、$β = max(β, u)$ とする
    2. 置換表にノードの情報が記録されていない場合は $l$ と $u$ を以下のように設定する
        * ルートノードの α 値と β 値を評価値の最小値と最大値とする場合は、評価値の最小値と評価値の最大値とする
        * そうでない場合は負の無限大と正の無限大とする
    3. 子孫ノードの枝狩りが行なわれたことが記録されていた場合は、子孫ノードの数を数えて枝狩りが行われた数に加える
    4. __"tt" の状態のフレームを記録__ する
    5. 子孫ノードの枝狩りが行なわれたことが記録されていた場合は手順 6 へ移動する
5. ノードの評価値 $s$ を max ノードの場合は負の無限大（または評価値の最小値でも良い）、min ノードの場合は正の無限大（または評価値の最大値でも良い）で初期化し、すべての子ノードに対して以下の処理を行う
    1. 子ノードの評価値 $c$ を計算する
    2. __"score" の状態のフレームを記録__ する
    3. max ノードの場合は下記の処理を行う
        1. ノードの評価値 $s$ を $s = max(s, c)$ とする
        2. α 値を $α 値 = max(α 値, s)$ とする
        3. $β < s$ の場合は β 狩りが行われるので枝狩りが行われたことを記録する
    4. min ノードの場合は下記の処理を行う
        1. ノードの評価値 $s$ を $s = min(s, c)$ とする
        2. β 値を $β 値 = min(β 値, s)$ とする
        3. $s < α$ の場合は α 狩りが行われるので枝狩りが行われたことを記録する
    5. 枝狩りが行われたことが記録されている場合は残りの子ノードの子孫ノードの数を数え、枝狩りが行われた数に加える
    6. __"update" の状態のフレームを記録__ する
    7. 枝狩りが行われたことが記録されている場合は、残りの子ノードの処理を省略する
6. 置換表を利用する場合は以下の処理を行う
    1. $s ≦ α$ の場合は fail low なので $u = s$ とする
    2. そうでなく $s < β$ の場合は exact value なので $l = s$、$u = s$ とする
    3. そうでない場合は fail high なので $l = s$ とする
    4. 置換表の同一局面に対してミニマックス値の下界と上界である $s$ と $l$ を記録する
7. __"end" の状態のフレームを記録__ する
8. 計算した評価値を返り値として返す

## `calc_score_for_anim` の定義

上記のアルゴリズムは __`calc_score_by_ab`__ のアルゴリズムを __かなり修正している__ ので、`calc_score_by_ab` を修正するのではなく、Mbtree クラスに上記のアルゴリズムの処理を行う別の __新しいメソッドを定義する__ 事にします。なお、メソッドの名前は __視覚化（アニメーション）を行うためのデータを計算する__ ことから __`calc_score_for_anim`__ という名前にしました。

`calc_score_for_anim` の実装手順として、__上記のアルゴリズムの手順を順番__ に __`calc_score_by_ab` のプログラムを参考にしながら__ 実装することにします。

:::note
`calc_score_by_ab` は元々は置換表を利用しない αβ 法のみの計算を行うプログラムでしたが、後からミニマックス法の計算や、置換表による計算処理を追加しました。このように、__関数に後から機能をどんどん追加していくと__、プログラムの構造が __わかりづらくなったり__、__効率が悪くなったりする__ ことがよくあります。そのような場合に機能を追加するとプログラムがさらにわかりづらくなるので、今回の記事で行ったように __アルゴリズムから設計しなおして__、__新しい関数として定義し直す__ ということがよくあります。
:::

## 上記のアルゴリズム以外の部分の実装

上記のアルゴリズムは、`calc_score_for_anim` 内で定義するローカル関数で行なわれる処理です。最初に __それ以外の部分__ を `calc_score_by_ab` を参考に下記のプログラムのように __定義する__ ことにします。以降の説明では `calc_score_by_ab` との違いについて説明します。

なお、`calc_score_by_ab` では、__[最短の勝利目指す評価値](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95%E3%81%AE%E5%A4%89%E6%9B%B4)を計算するかどうか__ を __指定することができない点が不便__[^2] なので、この機会に __仮引数 `shortest_victory` を追加する__ ことにしました。なお、`shortest_victory` という属性は Mbtree クラスからインスタンスを作成した際に作られているので、仮引数 `shortest_victory` はデフォルト値を `None` とするデフォルト引数とし、`None` 以外の値が代入されていた場合に `shortest_victory` 属性の値をその値で更新することにします。

なお、下記は `calc_score_for_anim` の一部であるため、実行しても意味がないため行番号のないプログラムは省略します。`calc_score_for_anim` のプログラム全体は、すべての手順の実装の説明後に示します。

* __1、2 行目__：メソッドの名前を `calc_score_for_anim` に修正し、デフォルト引数値を `None` とするデフォルト引数 `shortest_victory` を追加する
* __9 ~ 11 行目__：「ミニマックス法で計算するか」、「α 値と β 値の初期値を設定するか」、「置換表を利用するか」という情報は、__Mbtree_Anim でアニメーションを行う際に利用できる__ と __状況に合わせた表示を行うことができるようになる__ ので、それらを同じ名前の属性に代入するように修正した
* __12、13 行目__：`shortest_victory` が `None` でない場合に、同名の属性をその値で更新する
* __23 ~ 25 行目__：`init_ab` が `True` の場合は[前回の記事](https://qiita.com/ysgeso/items/20317d7b67518a119382#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E6%9C%80%E5%B0%8F%E5%80%A4%E3%81%AE%E6%9C%80%E5%A4%A7%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E6%94%B9%E8%89%AF)の `ai_abs_tt4` と同様の考え方で `min_score` と `max_score` に評価値の最小値と最大値を変数に代入し、それを 29 行目でルートノードの α 値と β 値の初期値として設定するように修正した。また、ここで変数に代入した評価値の最小値と最大値はこの後の手順 4-2 の実装で `ai_abs_tt4` と同様に置換表にデータが登録されていなかった場合の下界と上界の値に代入する
* __26 ~ 28 行目__：`init_ab` が `False` の場合は `min_score` と `max_score` に負の無限大と正の無限大を代入することで、ルートノードの α 値と β 値の初期値を負の無限大と正の無限大とする [`ai_abs_tt3`](https://qiita.com/ysgeso/items/20317d7b67518a119382#ai_abs_tt3-%E3%81%AE%E5%AE%9A%E7%BE%A9) と同様の処理が行われるようになる
* __29 行目__：ルートノードを計算する処理を呼び出す際に、α 値と β 値の初期値として `min_score` と `max_score` を設定するように修正した。また、ノードの評価値を計算するローカル関数の名前をこの後で `calc_node_score` という名前に変更するので、それに合わせて呼び出す関数の名前を修正した

```python
 1  def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False,
 2                          use_tt=False, shortest_victory=None):
 3      def assign_pruned_index(node, index):
 4          node.pruned_index = index
 5          self.num_pruned += 1
 6          for childnode in node.children:
 7              assign_pruned_index(childnode, index)
 8  
 9      self.minimax = minimax
10      self.init_ab = init_ab
11      self.use_tt = use_tt
12      if shortest_victory is not None:
13          self.shortest_victory = shortest_victory
14
15      from ai import dprint       
16      for node in self.nodelist:
17          node.score_index = float("inf")
18          node.pruned_index = float("inf")
19      self.nodelist_by_score = []
20      self.ablist_by_score = []
21      self.num_calculated = 0
22      self.num_pruned = 0
23      if init_ab:
24          min_score = -2 if self.shortest_victory else -1
25          max_score = 3 if self.shortest_victory else 1
26      else:
27          min_score = float("-inf")
28          max_score = float("inf")
29      calc_node_score(abroot, {}, min_score, max_score)
30      total_nodenum = self.num_pruned + self.num_calculated
31      ratio = self.num_calculated / total_nodenum * 100
32      dprint(debug, "ミニマックス法で計算したか", minimax)    
33      dprint(debug, "計算したノードの数",  self.num_calculated)
34      dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
35      dprint(debug, "合計",  total_nodenum)
36      dprint(debug, f"割合 {ratio:.1f}%") 
```

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

```diff_python
-def calc_score_by_ab(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False):
+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)

+   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:
-       alpha = -2 if self.shortest_victory else -1
+       min_score = -2 if self.shortest_victory else -1
-       beta = 3 if self.shortest_victory else 1
+       max_score = 3 if self.shortest_victory else 1
    else:
-       alpha = float("-inf")
+       min_score = float("-inf")
-       beta = float("inf")
+       max_score = float("inf")
-   calc_node_score(abroot, {}, alpha, beta)
+   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}%") 
```
</details>

## `calc_node_score` の定義

`calc_score_by_ab` ではノードの評価値を計算するローカル関数の名前を `calc_ab_score` としていましたが、`calc_score_for_anim` でその名前をそのまま使うのは変なので __`calc_node_score` という名前に変更__ することにします。

また、__置換表付き αβ 法__ では __α 値と β 値の初期値を記録しておく__ 必要があります。[`ai_abs_tt2`](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#ai_abs_tt2-%E3%81%AE%E5%AE%9A%E7%BE%A9) ではその処理を `calc_ab_score` のブロックの中（リンク先の `ai_abs_tt2` の 13、14 行目）で行っていましたが、よく考えると __仮引数の名前を `alphaorig`、`betaorig` に修正したほうが良い__ 気がしましたので、2 行目をそのように修正しました。

* __2 行目__：関数の名前を `calc_node_score` に、仮引数の名前を `alphaorig` と `betaorig` に修正した

```python
1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
略
```
</details>

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

```diff_python
def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
-   def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
+   def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
略
```
</details>

## 手順 1 の実装

__手順 1__ の __ミニマックス法で評価値を計算する場合の処理__ は下記のプログラムのように元の __`calc_score_by_ab` とほぼ同じ__ ですが、4、5 行目で負の無限大と正の無限大を代入する __変数の名前を `alphaorig` と `betaorig` に修正__ した点が異なります。

```python
1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
3          if minimax:
4              alphaorig = float("-inf")
5              betaorig = float("inf")
略
```
</details>

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

```diff_python
def calc_score_of_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")):
        if minimax:
-           alpha = float("-inf")
+           alphaorig = float("-inf")
-           beta = float("inf")
+           betaorig = float("inf")
略

```
</details>

## 手順 2 の実装

__手順 2__ の __"start" のフレームを記録する処理__ は下記のプログラムのように、元の __`calc_score_by_ab`__ の中で __"start" のフレームを記録する処理の位置が変わっただけ__ です。なお、[本記事の最初](#%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%E8%A6%96%E8%A6%9A%E5%8C%96%E3%82%92%E8%A1%8C%E3%81%86%E3%81%9F%E3%82%81%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)で説明したように、6、7 行目の __フレームに記録する情報に関する修正は次回の記事で行う__ 予定なので、今回の記事では __フレームに情報を記録する処理の内容は修正しません__。ただし、先程仮引数の名前を `alphaorig` と `betaorig` に変更したせいで、__使われなくなった `alpha` と `beta`__ をそのまま記述するとエラーが発生するので、__`alphaorig` と `betaorig` に変えるという修正を行う必要があります__。

```python
1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
3          手順 1 のプログラム
4
5          self.nodelist_by_score.append(node)
6          self.ablist_by_score.append((alphaorig, betaorig, None, "start",
7                                       self.num_calculated, self.num_pruned))
略
```

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

```diff_python
def calc_score_of_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")):
        手順 1 のプログラム

        self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alpha, beta, None, "start",
+       self.ablist_by_score.append((alphaorig, betaorig, None, "start",
                                     self.num_calculated, self.num_pruned))
略
```
</details>

## 手順 3 の実装

__手順 3__ の __リーフノードに関する処理__ は下記のプログラムのように記述します。

* __7, 8 行目__：__リーフノード__ では __必ず正確なミニマックス値が計算される__ ので、__上界と下界__ を __計算した評価値で更新する__ ように修正した
* 元の `calc_score_by_ab` では α 値または β 値にノードの評価値を計算していたが、[以前の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#ai_abs_tt2-%E3%81%AE%E5%AE%9A%E7%BE%A9)で __ノードの評価値 を α 値や β 値とは別に計算することにした__ ので、__α 値または β 値に評価値を代入する処理は削除__ した

```python
1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
3          手順 1、2 のプログラム
4
5          if node.mb.status != Marubatsu.PLAYING:
6              self.calc_score_of_node(node)
7              lower_bound = node.score
8              upper_bound = node.score
略
```

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

```diff_python
def calc_score_of_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")):
        手順 1、2 のプログラム

        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
+           lower_bound = node.score
+           upper_bound = node.score
-           if node.mb.turn == Marubatsu.CIRCLE:
-               alpha = node.score
-           else:
-               beta = node.score
略
```
</details>

:::note
実際にはリーフノードに対して置換表を利用することはないので、リーフノードの評価値の範囲を置換表に記録する必要はありません。ただし、リーフノードの場合に置換表にデータを記録しないという処理を記述すると、プログラムが長く、少しだけわかりづらくなるため、本記事ではリーフノードの評価値の範囲も置換表に記録することにします[^3]。

リーフノードの評価値の範囲を置換表に記録すると、その分だけコンピューターのメモリを消費してしまうという欠点が生じるので、その点が気になる方は置換表にデータを記録する処理を行う 手順 6 を、リーフノードの場合は行わないようにすると良いでしょう。また、その場合は上記の 7、8 行目を記述する必要はありません。
:::

## 手順 4 の実装

__手順 4__ は少々長いので以下に再掲します。

置換表を利用する場合は以下の処理を行う。
1. 置換表にノードの評価値の範囲の情報が記録されている場合は以下の処理を行う
    1. 置換表から $l$（下界）と $u$ （上界）を取り出す
    2. $l = u$ の場合は $l$ をそのノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
    3. $u < α$ の場合は fail low なので $u$ をそノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
    4. $β < l$ の場合は fail high なので $l$ をそノードの評価値とし、子孫ノードの枝狩りが行なわれたことを記録する
    5. それ以外の場合は $α = min(α, l)$、$β = max(β, u)$ とする
2. 置換表にノードの情報が記録されていない場合は $l$ と $u$ を以下のように設定する
    * ルートノードの α 値と β 値を評価値の最小値と最大値とする場合は、評価値の最小値と評価値の最大値とする
    * そうでない場合は負の無限大と正の無限大とする
3. 子孫ノードの枝狩りが行なわれたことが記録されていた場合は、子孫ノードの数を数えて枝狩りが行われた数に加える
4. __"tt" の状態のフレームを記録__ する

下記は手順 4 を実装したプログラムです。

* __6 行目__：__手順 3 の処理が行なわれた場合__ は __手順 6 に移動する必要がある__ ので、手順 4、5 の処理は手順 3 の if 文に対する __else のブロックの中に記述する必要__ がある
* __7 行目__：__手順 4-1-2 ~ 4-1-4__ で、__枝狩りが行われたことを記録できるようにする__ ために、枝狩りが行われたことを表すローカル変数 __`pruned` を `False` で初期化__ する
* __8 ~ 23 行目__：手順 4-1 の処理を行う。[`ai_abs_tt2`](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#ai_abs_tt2-%E3%81%AE%E5%AE%9A%E7%BE%A9)とほぼ同じだが、`alpha` と `beta` を `alphaorig` と `betaorig` に修正する点と、置換表に記録されていたデータをこのノードの評価値とする際に __評価値を返り値として返すのではなく__、__`node.score` に評価値を代入__ し、__`pruned` に `True` を代入__ する点が __異なる__
* __24 ~ 26 行目__：手順 4-2 の処理を行う。$l$ と $u$ に代入する値は[先程の処理](#上記のアルゴリズム以外の部分の実装)で `min_score` と `max_score` に代入済なので、それらの変数の値をそのまま代入すればよい
* __27 ~ 29 行目__：手順 4-3 の処理を行う
* __30 ~ 32 行目__：手順 4-4 の処理を行う。`alpha` と `beta` という仮引数の名前を変えたので、31 行目では `alphaorig` と `betaorig` に修正した。また、__元の `calc_score_by_ab`__ ではこの時点で __ノードの評価値が確定して処理を終了していた__ ので `self.num_calculated += 1` と `node.score_index = len(self.nodelist_by_score) - 1` という処理を行っていたが、先程 __[記録するフレームの状態を共通化](#記録するフレームの状態の共通化)__ したことで __ノードの評価値の確定は常に "end" のフレームで記録することにした__、__それらの処理を削除した__
* __33、34 行目__：子孫ノードの __枝狩りが行われたことが記録されていた場合__ は __手順 6 へ移動するため__ に、__手順 5 の処理__ を __`pruned` が `False` の場合のみ行うようにした__

```python
 1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
 2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
 3          手順 1、2 のプログラム
 4          if node.mb.status != Marubatsu.PLAYING:
 5              手順 3 のプログラム
 6          else:
 7              pruned = False
 8              if use_tt:
 9                  boardtxt = node.mb.board_to_str()
10                  if boardtxt in tt:
11                      lower_bound, upper_bound = tt[boardtxt]
12                      if lower_bound == upper_bound:
13                          node.score = lower_bound
14                          pruned = True
15                      elif upper_bound <= alphaorig:
16                          node.score = upper_bound
17                          pruned = True
18                      elif betaorig <= lower_bound:
19                          node.score = lower_bound
20                          pruned = True
21                      else:
22                          alphaorig = min(alphaorig, lower_bound)
23                          betaorig = max(betaorig, upper_bound)
24                  else:
25                      lower_bound = min_score
26                      upper_bound = max_score
27              if pruned:
28                  for childnode in node.children:
29                      assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
30              self.nodelist_by_score.append(node)
31              self.ablist_by_score.append((alphaorig, betaorig, None, "tt",
32                                           self.num_calculated, self.num_pruned))
33              if not pruned:
34                  手順 5 のプログラム
略
```

<details><summary><strong>修正箇所（一部<code>ai_abs_tt2</code>からの修正箇所があります）</strong></summary>

```diff_python
def calc_score_of_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")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
+           pruned = False
            if use_tt:  # このブロックの中は ai_abs_tt2 からの修正箇所です
                boardtxt = node.mb.board_to_str()
                if boardtxt in tt:
                    lower_bound, upper_bound = tt[boardtxt]
                    if lower_bound == upper_bound:
-                       return lower_bound
+                       node.score = lower_bound
+                       pruned = True
-                   elif upper_bound <= alpha:
+                   elif upper_bound <= alphaorig:
-                       return upper_bound
+                       node.score = upper_bound
+                       pruned = True
-                   elif beta <= lower_bound:
+                   elif betaorig <= lower_bound:
-                       return lower_bound
+                       node.score = lower_bound
+                       pruned = True
                    else:
-                       alpha = min(alpha, lower_bound)
+                       alphaorig = min(alphaorig, lower_bound)
-                       beta = max(beta, upper_bound)
+                       betaorig = max(betaorig, upper_bound)
                else:
                    lower_bound = min_score
                    upper_bound = max_score
                if pruned:
                    for childnode in node.children:
                        assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
            self.nodelist_by_score.append(node)
-           self.num_calculated += 1     
-           self.ablist_by_score.append((alpha, beta, None, "tt",
+           self.ablist_by_score.append((alphaorig, betaorig, None, "tt",
                                         self.num_calculated, self.num_pruned))
-           node.score_index = len(self.nodelist_by_score) - 1  
+           if not pruned:
                手順 5 のプログラム
略
```
</details>

## 手順 5 の実装

__手順 5__ も少々長いので再掲します。

ノードの評価値 $s$ を max ノードの場合は負の無限大（または評価値の最小値でも良い）、min ノードの場合は正の無限大（または評価値の最大値でも良い）で初期化し、すべての子ノードに対して以下の処理を行う
1. 子ノードの評価値 $c$ を計算する
2. __"score" の状態のフレームを記録__ する
3. max ノードの場合は下記の処理を行う
    1. ノードの評価値 $s$ を $s = max(s, c)$ とする
    2. α 値を $α 値 = max(α 値, s)$ とする
    3. $β < s$ の場合は β 狩りが行われるので枝狩りが行われたことを記録する
4. min ノードの場合は下記の処理を行う
    1. ノードの評価値 $s$ を $s = min(s, c)$ とする
    2. β 値を $β 値 = min(β 値, s)$ とする
    3. $s < α$ の場合は α 狩りが行われるので枝狩りが行われたことを記録する
5. 枝狩りが行われたことが記録されている場合は残りの子ノードの子孫ノードの数を数え、枝狩りが行われた数に加える
6. __"update" の状態のフレームを記録__ する
7. 枝狩りが行われたことが記録されている場合は、残りの子ノードの処理を省略する

下記は手順 5 を実装したプログラムです。下記ではノードの評価値 $s$ を評価値の最小値または最大値で初期化しました。なお、元のプログラムから大幅に変わっているので修正箇所は省略します。

* __9、10 行目__：現在の α 値と β 値を表す変数 `alpha`、`beta` を α 値と β 値の初期値で初期化する
* __11 行目__：この後で __max ノードであるかどうかを何度も判定する必要がある__ ので、__`maxnode`__ というローカル変数に __max ノードであるかどうかを計算して代入__ する
* __12 行目__：ノードの評価値を評価値の最小値または最大値で初期化する処理を行う
* __13 行目__：すべての子ノードに対する繰り返し処理を行う
* __14 行目__：手順 5-1 の処理を行う。再帰呼び出しを行う関数呼び出しの名前を __`calc_node_score`__ に修正した
* __15 ~ 17 行目__：手順 5-2 の処理を行う。`score` を `node.score` に修正した
* __18 ~ 22 行目__：手順 5-3 の処理を行う
* __23 ~ 27 行目__：手順 5-4 の処理を行う
* __28 ~ 31 行目__：手順 5-5 の処理を行う
* __32 ~ 34 行目__：手順 5-6 の処理を行う
* __35、36 行目__：手順 5-7 の処理を行う

```python
 1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
 2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
 3          手順 1、2 のプログラム
 4          if node.mb.status != Marubatsu.PLAYING:
 5              手順 3 のプログラム
 6          else:
 7              手順 4 のプログラム
 8              if not pruned:
 9                  alpha = alphaorig
10                  beta = betaorig
11                  maxnode = node.mb.turn == Marubatsu.CIRCLE
12                  node.score = min_score if maxnode else max_score
13                  for childnode in node.children:
14                      childscore = calc_node_score(childnode, tt, alpha, beta)
15                      self.nodelist_by_score.append(node)
16                      self.ablist_by_score.append((alpha, beta, node.score, "score",
17                                                   self.num_calculated, self.num_pruned))
18                      if maxnode:
19                          node.score = max(node.score, childscore)
20                          alpha = max(node.score, alpha)
21                          if node.score >= beta:
22                              pruned = True
23                      else:
24                          node.score = min(node.score, childscore)
25                          beta = min(node.score, beta)
26                          if node.score <= alpha:
27                              pruned = True
28                      if pruned:
29                          index = node.children.index(childnode)
30                          for prunednode in node.children[index + 1:]:
31                              assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
32                      self.nodelist_by_score.append(node)
33                      self.ablist_by_score.append((alpha, beta, None, "update",
34                                                    self.num_calculated, self.num_pruned))
35                      if pruned:
36                          break    
略   
```

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

```diff_python
def calc_score_of_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")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
            手順 4 のプログラム
            if not pruned:
                alpha = alphaorig
                beta = betaorig
                maxnode = node.mb.turn == Marubatsu.CIRCLE
                node.score = min_score if maxnode else max_score
                for childnode in node.children:
                    childscore = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, node.score, "score",
                                                 self.num_calculated, self.num_pruned))
                    if maxnode:
                        node.score = max(node.score, childscore)
                        alpha = max(node.score, alpha)
                        if node.score >= beta:
                            pruned = True
                    else:
                        node.score = min(node.score, childscore)
                        beta = min(node.score, beta)
                        if node.score <= alpha:
                            pruned = True
                    if pruned:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                  self.num_calculated, self.num_pruned))
                    if pruned:
                        break 
略      
```
</details>

:::note
21、22 行目の __手順 5-3-3__ の処理では、手順 4 で利用した __`pruned` という変数を使いまわしています__。その際に 8 行目の処理から __この時点では `pruned` に必ず `False` が代入されている__ ので、手順 4 の場合のように `pruned` を `False` で __初期化する必要はありません__。

わかりづらいと思った方は、`pruned` を `False` で初期化する処理を記述するか、`pruned` とは別の変数で枝狩りが行われたことを記録して下さい。ただしその場合はその変数を `False` で初期化する処理を記述するのを忘れないようにして下さい。
:::

## 手順 6 の実装

__手順 6__ の __評価値の範囲を置換表に記録する処理__ は __[`ai_abs_tt3`](https://qiita.com/ysgeso/items/20317d7b67518a119382#ai_abs_tt3-%E3%81%AE%E5%AE%9A%E7%BE%A9) とほぼ同じ__ で、下記のプログラムのように記述できます。異なる点は置換表を利用するかどうかの判定を行う部分と、`score` が `node.score` になった点などです。

```python
def calc_score_of_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")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
            手順 4 のプログラム
            if not pruned:
                手順 5 のプログラム
        
        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)     
略  
```

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

```diff_python
def calc_score_of_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")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
            手順 4 のプログラム
            if not pruned:
                手順 5 のプログラム
        
+       if use_tt:
+           from util import calc_same_boardtexts
            
            boardtxtlist = calc_same_boardtexts(node.mb)  
            if node.score <= alphaorig:
-               upper_bound = score
+               upper_bound = node.score
            elif node.score < betaorig:
-               lower_bound = score
+               lower_bound = node.score
-               upper_bound = score
+               upper_bound = node.score
            else:
-               lower_bound = score
+               lower_bound = node.score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)     
略   
```
</details>

## 手順 7、8 の実装

__手順 7、8__ の __"end" の状態のフレームを記録__ し、__計算した評価値を返り値として返す処理__ は下記のプログラムのように 14 行目で `alpha` と `beta` を `alphaorig` と `betaorig` に修正した以外は元の `calc_score_by_ab` と同じです。

```python
 1  def calc_score_of_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
略
 2      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
 3          手順 1、2 のプログラム
 4          if node.mb.status != Marubatsu.PLAYING:
 5              手順 3 のプログラム
 6          else:
 7              手順 4 のプログラム
 8              if not pruned:
 9                  手順 5 のプログラム
10  
11          手順 6 のプログラム
12          self.nodelist_by_score.append(node)
13          self.num_calculated += 1     
14          self.ablist_by_score.append((alphaorig, betaorig, None, "end",
15                                      self.num_calculated, self.num_pruned))
16          node.score_index = len(self.nodelist_by_score) - 1          
17          return node.score
```

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

```diff_python
def calc_score_of_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")):
        手順 1、2 のプログラム
        if node.mb.status != Marubatsu.PLAYING:
            手順 3 のプログラム
        else:
            手順 4 のプログラム
            if not pruned:
                手順 5 のプログラム

        手順 6 のプログラム
        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
-       self.ablist_by_score.append((alpha, beta, None, "end",
+       self.ablist_by_score.append((alphaorig, betaorig, None, "end",
                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score
```
</details>

## `calc_score_of_anim` の実装と確認

下記は `calc_score_of_anim` を定義するプログラムです。

```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((alphaorig, betaorig, None, "start",
                                     self.num_calculated, self.num_pruned))

        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            lower_bound = node.score
            upper_bound = node.score
        else:
            pruned = False
            if use_tt:
                boardtxt = node.mb.board_to_str()
                if boardtxt in tt:
                    lower_bound, upper_bound = tt[boardtxt]
                    if lower_bound == upper_bound:
                        node.score = lower_bound
                        pruned = True
                    elif upper_bound <= alphaorig:
                        node.score = upper_bound
                        pruned = True
                    elif betaorig <= lower_bound:
                        node.score = lower_bound
                        pruned = True
                    else:
                        alphaorig = min(alphaorig, lower_bound)
                        betaorig = max(betaorig, upper_bound)
                else:
                    lower_bound = min_score
                    upper_bound = max_score
                if pruned:
                    for childnode in node.children:
                        assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
            self.nodelist_by_score.append(node)
            self.ablist_by_score.append((alphaorig, betaorig, None, "tt",
                                         self.num_calculated, self.num_pruned))
            if not pruned:
                alpha = alphaorig
                beta = betaorig
                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((alpha, beta, node.score, "score",
                                                 self.num_calculated, self.num_pruned))
                    if maxnode:
                        node.score = max(node.score, childscore)
                        alpha = max(node.score, alpha)
                        if node.score >= beta:
                            pruned = True
                    else:
                        node.score = min(node.score, childscore)
                        beta = min(node.score, beta)
                        if node.score <= alpha:
                            pruned = True
                    if pruned:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                  self.num_calculated, self.num_pruned))
                    if pruned:
                        break 
                    
        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) 

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append((alphaorig, betaorig, None, "end",
                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score                
                                    
    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
```

上記のプログラムを実行後に、下記のプログラムで、以下のそれぞれの場合で __ルートノードの評価値を計算した際に計算されるノード数などの情報を表示__ します。__実行結果__ に表示される「__計算したノードの数__」が[前回の記事](https://qiita.com/ysgeso/items/20317d7b67518a119382#%E6%A7%98%E3%80%85%E3%81%AA-ai-%E3%81%A7%E3%81%AE%E8%A8%88%E7%AE%97%E3%81%97%E3%81%9F%E3%83%8E%E3%83%BC%E3%83%89%E6%95%B0%E3%81%AE%E7%A2%BA%E8%AA%8D)（`ai_mmdfs`、`ai_mmdfs_tt`、`ai_abs`）と[前回の記事](https://qiita.com/ysgeso/items/20317d7b67518a119382#%E6%9E%9D%E7%8B%A9%E3%82%8A%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E7%A2%BA%E8%AA%8D)（`ai_abs_tt3`）と[前回の記事](https://qiita.com/ysgeso/items/20317d7b67518a119382#%E6%9E%9D%E7%8B%A9%E3%82%8A%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E7%A2%BA%E8%AA%8D-1)（`ai_abs_tt4`）の結果と同じであることから、__`calc_score_for_anim` が正しい処理を行うことができる__ ことが確認できました。

* 置換表を利用しないミニマックス法（`ai_mmdfs` と同じ）
* 置換表を利用したミニマックス法（`ai_mmdfs_tt` と同じ）
* 置換表を利用しない αβ 法（`ai_abs` と同じ）
* 置換表付き αβ 法（`ai_abs_tt3` と同じ）
* 置換表付き αβ 法で α 値と β 値の初期値を評価値の最小値と最大値に設定する（`ai_abs_tt4` と同じ）

```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`__ を定義しました。次回の記事では今回の記事で作成したデータを利用して、置換表付き αβ 法の計算手順の視覚化の処理を実装します。

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

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

# 次回の記事
https://qiita.com/ysgeso/items/ddcbd0cb9ab62656173e

[^1]:そうすることで、計算された評価値が必ず exact value の範囲に収まり、正確な評価値（ミニマックス値）を計算できるようになります
[^2]:現状では、`calc_score_by_ab` で最短の勝利を目指すような評価値を計算するためには、ゲーム木を作成する際の実引数に `shortest_victory=True` を記述する必要があります
[^3]:リーフノードの場合は置換表を利用しないということは、でたらめな評価値の範囲を置換表に登録しても構わないということなので、7、8 行目を省略してもプログラムは正しく動作します。ただし、その内容を利用しないからと言って、間違った内容をプログラムに記述すると、後でそのプログラムを見た際にそれが正しいと勘違いしてしまう可能性があるため、実際には利用しない値であったとしても 7、8 行目は記述しておいたほうが良いと思います