Pythonで〇×ゲームのAIを一から作成する　その140　αβ 法による評価値の計算手順の視覚化

# 目次と前回の記事

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

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

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

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

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

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

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

# 用語の定義

最初に、今回の記事で扱う __αβ 法__ に関するいくつかの用語の定義を行うことにします。

__αβ 法__ ではゲーム木の中の __特定の局面のノードを指定__ してその評価値の計算を行います。また、そのノードの評価値を計算するために、その __子孫ノードの評価値の計算を行う__ 必要があります[^1]。例えば、下図の __赤枠のノードの評価値を αβ 法で計算__ するためには、__紫枠で囲われたノードの評価値を計算__ する必要があります[^2]。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0fa0dd09-24b7-a75b-8400-a9780b838d5d.png" width="5500">

上図の __紫枠のノード__ は、__赤枠のノード__ を __ルートノード__ とする 〇× ゲームのゲーム木の __部分木__ です。αβ 法で評価値を計算するノードの深さが __深いほど__ 計算にかかる __時間が減る__ のは、__部分木に含まれるノードの数__ がノードの深さが __深いほど減るから__ です。

そこで、本記事では __αβ 法に関する説明を行う際__ に、αβ 法で評価値を計算する上図の赤枠のノードのことを __αβ のルートノード__、αβ のルートノードの評価値を計算するために評価値の計算を行う必要があるノードのことを __αβ の子孫ノード__ と表記することにします。また、上図の紫枠の部分木のことを __αβ の部分木__ と表記することにします。αβ のルートノードは、αβ の部分木のルートノードです。

# αβ 法の評価値の計算の手順の視覚化

今回の記事では、__Mbtree_Anim__ クラスを利用して、__αβ 法の評価値の計算の手順の視覚化__ を行います。そのためには、__Mbtree__ クラスで幅優先アルゴリズムで評価値を計算する __`calc_score_by_bf`__ メソッドや、深さ優先アルゴリズムで評価値を計算する __`calc_score_by_df` と同様の方法__ で、Mbtree_Anim クラスで __評価値の計算の手順を表示するために必要なデータを計算__ する必要があります。

## 視覚化に必要なデータの計算方法の復習

__視覚化に必要なデータの計算方法__ について忘れた方が多いと思いますので、復習します。[以前の記事](https://qiita.com/ysgeso/items/94c5105c3dbebb445710#%E8%A6%96%E8%A6%9A%E5%8C%96%E3%81%AE%E6%96%B9%E9%87%9D)で説明したように、__Mbtree_Anim__ では以下のような方法で視覚化を行います。

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

__[処理を行うノードの処理の移り変わり](https://qiita.com/ysgeso/items/94c5105c3dbebb445710#nodelist_by_score-%E3%81%AE%E8%A8%98%E9%8C%B2)__ については、Mbtree クラスの __`nodelist_by_score`__ という名前の属性にノードのデータを __list で記録__ します。__[評価値を計算するタイミング](https://qiita.com/ysgeso/items/94c5105c3dbebb445710#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%95%E3%82%8C%E3%81%9F%E3%82%BF%E3%82%A4%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E8%A8%98%E9%8C%B2)__ についてはノードの __`score_index`__ 属性に、__そのノードの評価値が計算されたタイミング__ を表す __`nodelist_by_score`__ の要素の __インデックスを記録__ します。

### `calc_score_by_df` の処理の復習

具体例として、__[`calc_score_by_df`](https://qiita.com/ysgeso/items/94c5105c3dbebb445710#%E8%A6%96%E8%A6%9A%E5%8C%96%E3%81%AB%E5%BF%85%E8%A6%81%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E8%A8%88%E7%AE%97)__ での上記の処理を復習することにします。なお、`calc_score_by_df` の方を復習するのは、__αβ 法が深さ優先アルゴリズムの一種__ だからです。

__`calc_score_by_df`__ は、実引数に __`algo="df"`__ を記述して __Mbtree クラスのインスタンスを作成__ した場合に、__`__init__`__ メソッド内の下記のプログラムで __呼び出されます__。この中の __3 行目__ で __`nodelist_by_score` の初期化処理__ を行っています。

* __2 行目__：深さ優先アルゴリズムでゲーム木を作成する `create_tree_by_df` を呼び出す
* __3 行目__：評価値を計算する際に辿ったノードの一覧を表す `nodelist_by_score` 属性を空の list で初期化する
* __4 行目__：実引数にゲーム木のルートノードを記述して `calc_score_by_df` を呼び出す

```python
1  def __init__(self, algo="bf", 略):
略
2              self.create_tree_by_df(self.root)
3              self.nodelist_by_score = []
4              self.calc_score_by_df(self.root)
略
```

下記は、__`calc_score_by_df`__ の定義です。このプログラムでは、__深さ優先アルゴリズム__ で __各ノードの評価値__、最大の評価値、最小の評価値[^3]を __計算しています__ が、その際に __`nodelist_by_score`__ と __`scorelist`__ 属性に対して以下のような処理を行っています。

* __2 行目__：__`calc_score_by_df`__ の処理が __開始された時点で処理が__ 仮引数 `node` に代入された __ノードに移り変わる__ ので `nodelist_by_score` の要素に `node` を 追加する
* __14 行目__：子ノードに対する評価値の計算処理を行うための 10 行目の __`calc_score_by_df` の処理が終了した時点__ で、子ノードの処理から __`node` のノードの処理に移り変わる__ ので `nodelist_by_score` の要素に `node` を 追加する
* __23、24 行目__：全ての子ノードの評価値を計算する処理が終了した時点で、__`node` の評価値が確定する__ ので `nodelist_by_score` の要素に `node` を 追加し、`node` の __`score_index` 属性に追加した `nodelist_by_score` のインデックスを代入__ する

```python
 1  def calc_score_by_df(self, node):
 2      self.nodelist_by_score.append(node)
 3      if node.mb.status != Marubatsu.PLAYING:
 4          self.calc_score_of_node(node)
 5      else:
 6          score_list = []
 7          max_score_list = []
 8          min_score_list = []
 9          for childnode in node.children:
10              score, max_score, min_score = self.calc_score_by_df(childnode)
11              score_list.append(score)
12              max_score_list.append(max_score)
13              min_score_list.append(min_score)
14              self.nodelist_by_score.append(node)
15          if node.mb.move_count % 2 == 0:
16              score = max(score_list)
17          else:
18              score = min(score_list)
19          node.score = score
20          node.max_score = max(max_score_list)
21          node.min_score = min(min_score_list)
22          
23      self.nodelist_by_score.append(node)
24      node.score_index = len(self.nodelist_by_score) - 1        
25      return node.score, node.max_score, node.min_score  
```

## `calc_score_by_ab` の定義

下記は、__αβ 法__ で評価値の計算を行う __[`ai_by_abs`](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E7%A5%96%E5%85%88%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F-%CE%B1-%E7%8B%A9%E3%82%8A%E3%81%A8%CE%B2-%E7%8B%A9%E3%82%8A%E3%81%AE%E5%AE%9F%E8%A3%85) の定義__ です[^4]。__この関数__ を上記の __`calc_score_by_df` を参考にしながら修正していく__ ことで、αβ 法での評価値の計算の手順の __視覚化に必要なデータを計算しながら__ ゲーム木のノードの評価値を計算する __`calc_score_by_ab`__ という __Mbtree クラスのメソッドを定義__ する事にします。

```python
def ai_abs(mb, debug=False):          
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, alpha, beta)
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return alpha
        else:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, alpha, beta)
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return beta
                
    score = ab_search(mb)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```

### 関数名と仮引数の変更

まず、__`calc_score_by_ab`__ は __Mbtree__ クラスの __メソッドとして定義__ するので、`calc_score_by_ab` には __仮引数 `self` を追加__ する必要があります。

__`ai_abs`__ はゲーム木の __[ノードを作成せず](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E4%BD%9C%E6%88%90%E3%81%97%E3%81%AA%E3%81%84%E5%AE%9F%E8%A3%85%E6%96%B9%E6%B3%95)__ に処理を行うので、仮引数 __`mb`__ に αβ のルートノードの __局面を表すデータを代入__ して評価値の計算を行います。一方、__`calc_score_by_ab`__ では、評価値の計算の手順を記録するために、__αβ の部分木のノード__ に αβ 法の __計算過程で計算した評価値__ を __`score` 属性に代入して記録__ する必要があるため、__αβ のルートノード__ を表すデータを __代入する仮引数が必要__ になります。そこで、__`ai_abs`__ の仮引数 __`mb`__ を、__αβ のルートノードを代入__ する __`abroot`__[^5]という名前の仮引数に変更することにします。。

`ai_abs` 内で定義されている __ローカル関数 `ab_search`__ に対しては、下記のような修正を行う必要があります。

* ノードの評価値を計算して `score` 属性に代入する処理を行うため、__関数の名前を `calc_ab_score` に修正__ する
* ノードのデータが必要となるので __仮引数 `mborig` を `node` に変更__ する。`nodeorig` に変更しない理由はこの後で説明する
* 局面を表すデータは、ノードを表す `node` の `mb` 属性に代入されているので、プログラム内の __`mborig` を `node.mb` に変更__ する
* 元のプログラムではゲーム木を作成せずに計算を行っているため、子ノードの局面の計算を行う際に、「合法手の一覧の計算」、「`mborig` のコピー」、「コピーした `mb` に対する合法手の着手」という処理を行う必要がある。一方、__`calc_score_by_ab`__ では `calc_score_by_df` と同様に __ゲーム木の全てのノードは計算済__ なので、ノードのコピーの処理を行う __必要はない__。`mborig` を `nodeorig` に変更しないのはそのためである

下記は上記のように `calc_score_by_ab` を定義したプログラムです。

* __5 行目__：メソッドの名前を `calc_score_by_ab` に修正し、仮引数 `self` を追加し、仮引数 `mb` を `abroot` に修正する
* __6、9、34 行目__：元のプログラムでは、__ローカル変数 `count`__ を利用してローカル関数 `ab_search` を呼び出した回数を数えていたため、ローカル関数 __`ab_search` 内__ でクロージャー変数 __`count` の値を変更するため__ に __[`nonlocal count` を記述する必要](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#%E6%8E%A2%E7%B4%A2%E7%AF%84%E5%9B%B2%E3%81%AE%E7%B5%9E%E3%82%8A%E8%BE%BC%E3%81%BF%E3%81%AE%E7%A2%BA%E8%AA%8D)__ があった。__`count`__ を Mbtree クラスの __インスタンスの属性である `self.count` に修正する__ ことで、`nonlocal` という __わかりづらい記述を行う必要がなくなる__
* __8 行目__：ローカル関数の名前を `calc_ab_score` に、仮引数 `mborig` を `node` に修正する
* __10、11 行目__：元のプログラムでは、__決着がついている局面の評価値__ を if 文で計算していたが、その処理は Mbtree クラスの __`calc_score_of_node` メソッドで定義__ されているので、決着がついている場合は `calc_score_of_node` を呼び出す処理に修正する。この部分は先ほどの [`calc_score_by_df`](#calc_score_by_df-の処理の復習) の 3、4 行目に相当する
* __12 行目__：__`calc_score_of_node`__ では、計算した __評価値__ をノードの __`score` 属性に代入__ する処理を行うので、__`node.score` を返り値として返す__ ように修正する
* __14 行目__：`mborig` を `node.mb` に修正する
* __15 行目__：`node` の子ノードの一覧のデータは、`children` 属性に代入されているので、`children` 属性に対する繰り返し処理を行う。元のプログラムのように それぞれの合法手に対して `mborig` をコピーしてその合法手を着手するという処理を行う必要はない。先ほどの [`calc_score_by_df`](#calc_score_by_df-の処理の復習) の 9 行目に相当する
* __16 行目__：`childnode` を実引数に記述して `calc_ab_score` を再帰呼び出しすることで、子ノードの評価値を計算する処理を行う。先ほどの [`calc_score_by_df`](#calc_score_by_df-の処理の復習) の 10 行目に相当
* __18 行目__：β 枝狩りによって、評価値が `score` と計算されたので、ノードの `score` 属性に `score` を代入する
* __21 行目__：全ての子ノードの評価値が計算されたことで、ノードの評価値が `alpha` と計算されたので、ノードの `score` 属性に `alpha` を代入する
* __23 ~ 31 行目__：14 ~ 22 行目と同様の修正を行う
* __33 行目__：`calc_score_by_ab` が行う処理として、`abroot` を実引数に記述して `calc_ab_score` を呼び出して、`abroot` の評価値を計算する
* 35 行目の後に記述していた、〇 の手番の場合に評価値の正負を反転させる処理は、評価値の計算過程を表示する際には必要がない処理なので削除した

```python
 1  from marubatsu import Marubatsu
 2  from tree import Mbtree
 3  from ai import dprint
 4
 5  def calc_score_by_ab(self, abroot, debug=False):
 6      self.count = 0
 7 
 8      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
 9          self.count += 1
10          if node.mb.status != Marubatsu.PLAYING:
11              self.calc_score_of_node(node)
12              return node.score
13          else:
14              if node.mb.turn == Marubatsu.CIRCLE:
15                  for childnode in node.children:
16                      score = calc_ab_score(childnode, alpha, beta)
17                      if score >= beta:
18                          node.score = score
19                          return score
20                      alpha = max(alpha, score)
21                  node.score = alpha
22                  return alpha
23              else:
24                  for childnode in node.children:
25                      score = calc_ab_score(childnode, alpha, beta)
26                      if score <= alpha:
27                          node.score = score
28                          return score
29                      beta = min(beta, score)
30                  node.score = beta
31                  return beta
32
33      calc_ab_score(abroot)
34      dprint(debug, "count =", self.count)
35    
36  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

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

def calc_score_by_ab(self, abroot, debug=False):
    self.count = 0

    def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
        self.count += 1
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            return node.score
        else:
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    if score >= beta:
                        node.score = score
                        return score
                    alpha = max(alpha, score)
                node.score = alpha
                return alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    if score <= alpha:
                        node.score = score
                        return score
                    beta = min(beta, score)
                node.score = beta
                return beta

    calc_ab_score(abroot)
    dprint(debug, "count =", self.count)
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

<details><summary><strong>修正箇所（14 ~ 32 行目のインデントに関する修正の表示は省略しました）</strong></summary>

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

-def ai_abs(mb, debug=False):   
+def calc_score_by_ab(self, abroot, debug=False):
-   count = 0
+   self.count = 0

-   def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
+   def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
-       nonlocal count
-       count += 1
+       self.count += 1
-       if mborig.status == Marubatsu.CIRCLE:
-           return 1
-       elif mborig.status == Marubatsu.CROSS:
-           return -1
-       elif mborig.status == Marubatsu.DRAW:
-           return 0
+       if node.mb.status != Marubatsu.PLAYING:
+           self.calc_score_of_node(node)
+           return node.score
+       else:
-           legal_moves = mborig.calc_legal_moves()
-           if mborig.turn == Marubatsu.CIRCLE:
+           if node.mb.turn == Marubatsu.CIRCLE:
-               for x, y in legal_moves:
+               for childnode in node.children:
-                   mb = deepcopy(mborig)
-                   mb.move(x, y)
-                   score = ab_search(mb, alpha, beta)
+                   score = calc_ab_score(childnode, alpha, beta)
                    if score >= beta:
+                       node.score = score
                        return score
                    alpha = max(alpha, score)
+               node.score = alpha
                return alpha
            else:
-               for x, y in legal_moves:
+               for childnode in node.children:
-                   mb = deepcopy(mborig)
-                   mb.move(x, y)
-                   score = ab_search(mb, alpha, beta)
+                   score = calc_ab_score(childnode, alpha, beta)
                    if score <= alpha:
+                       node.score = score
                        return score
                    beta = min(beta, score)
+               node.score = beta
                return beta

-   score = ab_search(mb)
+   calc_ab_score(abroot)
-   dprint(debug, "count =", count)
+   dprint(debug, "count =", self.count)
-   if mb.turn == Marubatsu.CIRCLE:
-       score *= -1
-   return score 
    
Mbtree.calc_score_by_ab = calc_score_by_ab       
```
</details>

上記のプログラムが正しく動作するかを確認するために、下記のプログラムの 1 行目で __深さ優先アルゴリズムで Mbtree クラスのインスタンスを作成__ し、それに対してキーワード引数 __`debug=True`__ を記述して __`calc_score_by_ab`__ メソッドを呼び出して __ルートノードの評価値__ を __αβ 法で計算__ すると、実行結果のように __評価値を計算したノードの数__ を表す、ローカル関数 `calc_ab_score` が呼び出された回数として __18297__ が表示されます。これは、[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E7%A5%96%E5%85%88%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F-%CE%B1-%E7%8B%A9%E3%82%8A%E3%81%A8%CE%B2-%E7%8B%A9%E3%82%8A%E3%81%AE%E5%AE%9F%E8%A3%85)で __`ai_abs(mb, debug=True)`__ を実行した場合と __同じ__ であることが確認できます。また、3 行目で __ルートノードの評価値を表示__ すると、__正しい 0 が計算されている__ ことが確認できます。


```python
mbtree = Mbtree(algo="df")
mbtree.calc_score_by_ab(mbtree.root, debug=True)
print(mbtree.root.score)
```

実行結果

```
count = 18297
0
```

:::note
上記の 1 行目でゲーム木を新しく作成するのではなく、下記のプログラムのように深さ優先アルゴリズムで評価値を計算したゲーム木のデータが保存されている `dfscore.mbtree` をファイルから読み込めばよいのではないかと思った人がいるかもしれません。筆者も最初はそのようにしたのですが、下記のプログラムを実行すると、実行結果のようにエラーが発生します。

```python
mbtree2 = Mbtree.load("../data/dfscore")
mbtree2.calc_score_by_ab(mbtree.root, debug=True)
```

実行結果

```
略
--> 355     node.score = (11 - node.depth) / 2 if self.shortest_victory else 1
    356 elif node.mb.status == Marubatsu.DRAW:
    357     node.score = 0

AttributeError: 'Mbtree' object has no attribute 'shortest_victory'
```

このエラーは、以下のような理由で発生します。そのため、ゲーム木を新しく作成する必要があります。

* __[`dfscore.mbtree`](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E4%BF%9D%E5%AD%98)__ は 105 回目の記事でファイルに保存したデータである
* Mbtree クラスの __[`shortest_victory`](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE%E4%BF%AE%E6%AD%A3)__ 属性は、118 回目の記事で追加したので、dftree.mbtree から読み込んだゲーム木のデータには __`shortest_victory` 属性は存在しない__
* __`calc_score_of_node`__ メソッド内で __`shortest_victory` 属性を参照する処理が記述されている__ ので、`dfscore.mbtree` から読み込んだゲーム木のデータに対して `calc_score_by_ab` を呼び出すと __`shortest_victory` 属性が存在しない__ というエラーが発生する
:::

## `nodelist_by_score` と `score_index` に関する処理の記述

次に、__`nodelist_by_by_score`__ と __`score_index`__ に関する処理を記述します。その際に行う処理は、下記の __`calc_score_by_df` とほぼ同様__ です。

```python
 1  def calc_score_by_df(self, node):
 2      self.nodelist_by_score.append(node)
 3      if node.mb.status != Marubatsu.PLAYING:
 4          self.calc_score_of_node(node)
 5      else:
 6          score_list = []
 7          max_score_list = []
 8          min_score_list = []
 9          for childnode in node.children:
10              score, max_score, min_score = self.calc_score_by_df(childnode)
11              score_list.append(score)
12              max_score_list.append(max_score)
13              min_score_list.append(min_score)
14              self.nodelist_by_score.append(node)
15          if node.mb.move_count % 2 == 0:
16              score = max(score_list)
17          else:
18              score = min(score_list)
19          node.score = score
20          node.max_score = max(max_score_list)
21          node.min_score = min(min_score_list)
22          
23      self.nodelist_by_score.append(node)
24      node.score_index = len(self.nodelist_by_score) - 1        
25      return node.score, node.max_score, node.min_score  
```

下記は、__上記のプログラムを参考__ にして __`calc_score_by_ab` を修正__ したプログラムです。元のプログラムでは、__ノードの評価値が確定__ した下記の 8 行目の後、15 行目の後、18 行目の後、24 行目の後、27 行目の後で return 文を記述して __ノードの評価値を返す処理__ を行っていましたが、上記のプログラムの 23、24 行目のように __評価値の確定後__ に __`nodelist_by_score`__ の要素に __`node` を追加__ し、__`score_index`__ 属性に __値を代入__ する処理を行う必要があります。そこで __return 文を削除__ し、__評価値の確定後の処理__ を下記のプログラムの __29、30 行目でまとめて行う__ ように修正しました。

* __5 行目__：`calc_ab_score` を呼び出した直後に、`nodelist_by_score` の要素に `node` を追加する。上記の 2 行目と対応する
* __13、22 行目__：`calc_ab_score` を呼び出して子ノードの評価値の計算の処理が終了した直後に、`nodelist_by_score` の要素に `node` を追加する。上記の 14 行目と対応する
* 8 行目で呼び出された `calc_score_of_node` の処理によって評価値が `node` の `score` 属性に代入される。その後の return 文を削除し、次に 29 行目の処理が行われるようにする
* __15、16 行目__：β 狩りが行われた際に `alpha` に `node` の評価値である `score` を代入し、break 文によって子ノードに対する繰り返し処理を終了する。その結果、次に 18 行目の `node.score = alpha` によって `node` の `score` 属性に評価値が代入され、次に 29 行目の処理が行われるようになる
* 18 行目で評価値を `score` 属性に代入した後の return 文を削除し、次に 29 行目の処理が行われるようにする。26 行目の次の return 文も同様の理由で削除する
* __24、25 行目__：α 狩りが行われた際に、上記の 15、16 行目と同様の処理を行う
* __29、30 行目__：ノードの評価値が計算されたので `nodelist_by_score` の要素に `node` を追加し、`score_index` 属性にそのインデックスを代入する。上記の 23、24 行目に対応する
* __31 行目__：`node` の評価値を表す `node.score` を返り値として返すようにする
* __33 行目__：__`calc_score_by_ab`__ が行う処理として、`nodelist_by_score` を空の list で初期化する処理を追加する

```python
 1  def calc_score_by_ab(self, abroot, debug=False):
 2      self.count = 0
 3
 4      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
 5          self.nodelist_by_score.append(node)
 6          self.count += 1
 7          if node.mb.status != Marubatsu.PLAYING:
 8              self.calc_score_of_node(node)
 9          else:
10              if node.mb.turn == Marubatsu.CIRCLE:
11                  for childnode in node.children:
12                      score = calc_ab_score(childnode, alpha, beta)
13                      self.nodelist_by_score.append(node)
14                      if score >= beta:
15                          alpha = score
16                          break
17                      alpha = max(alpha, score)
18                  node.score = alpha
19              else:
20                  for childnode in node.children:
21                      score = calc_ab_score(childnode, alpha, beta)
22                      self.nodelist_by_score.append(node)
23                      if score <= alpha:
24                          beta = score
25                          break
26                      beta = min(beta, score)
27                  node.score = beta
28
29          self.nodelist_by_score.append(node)
30          node.score_index = len(self.nodelist_by_score) - 1          
31          return node.score
32
33      self.nodelist_by_score = []
34      calc_ab_score(abroot)
35      dprint(debug, "count =", self.count)
36    
37  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

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

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

    self.nodelist_by_score = []
    calc_ab_score(abroot)
    dprint(debug, "count =", self.count)
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

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

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

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

+   self.nodelist_by_score = []
    calc_ab_score(abroot)
    dprint(debug, "count =", self.count)
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

:::note
上記のプログラムでは `calc_score_by_ab` で行われる処理が、2 行目、33 ~ 35 行目の順で行われます。そのことがわかりづらいと思った方は `self.count = 0` を 33 行目の前に移動して下さい。
:::

上記の修正後に下記のプログラムを実行すると、実行結果のように先程と同じ表示が行われることが確認できます。

```python
mbtree.calc_score_by_ab(mbtree.root, debug=True)
print(mbtree.root.score)
```

実行結果

```
count = 18297
0
```

また、下記のプログラムを実行する事で、__`nodelist_by_score`__ の __要素の数が 54890__ であることが確認できます。また、αβ 法では __αβ のルートノードの評価値__ は __最後に計算される__ ので、ルートノードの __`score_index`__ 属性の値が __`nodelist_by_score`__ の __最後の要素のインデックス__ である __54889__ に __正しく計算されている__ ことが確認できます。

```python
print(len(mbtree.nodelist_by_score))
print(mbtree.root.score_index)
```

実行結果

```
54890
54889
```

## Mbtree_Anim でのアニメーションの確認

次に、下記のプログラムで αβ 法で評価値が計算された `mbtree` の __評価値の計算の手順__ を Mbtree_Anim で表示して __確認する__ ことにします。

```python
from tree import Mbtree_Anim

Mbtree_Anim(mbtree, isscore=True)
```

下図はアニメーションの 15 フレーム目の部分木の図です。このフレームで __赤枠の局面の評価値が 1__ であることが __計算されました__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/10deac0e-ee11-71af-6098-d753f3a1392e.png" width="500">

下図はその次の 16 フレーム目の部分木の図で、上図の赤枠のノードから __下図の赤枠の子ノードに処理が移動__ したことを表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ea707efe-a536-7ee6-1107-7811bc99fc6e.png" width="500">

上図の __赤枠のノード__ は __× の手番__ のノードなので __[min ノード](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF)__ です。[前回の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#min-%E3%83%8E%E3%83%BC%E3%83%89%E3%81%A7%E3%81%AE%E6%9E%9D%E7%8B%A9%E3%82%8A%CE%B1-%E7%8B%A9%E3%82%8A)で説明したように、min ノードでは下記の条件が満たされた場合に __α 狩り__ を行います。

* それまでに計算された __兄弟ノード__ の __評価値の最大値を α__ とする
* __子ノードの中__ で __α 以下__ の評価値が __計算された時点__ で __残りの子ノードの評価値の計算を省略__ する

上図では赤枠の __兄弟ノードの評価値の最大値は 1__ なので __α は 1__ です、__子ノードの中__ で __α 以下の 1__ という評価値が __計算された__ ので、__α 狩り__ を行って __残りの子ノード__ の評価値の __計算が省略__ され、__赤枠のノードの評価値が 1 で確定__ します。そのことは、その次の下図の 17 フレーム目の部分木の図で、__上図の赤枠の次の子ノードが赤枠のノードにならず__ に、__上図の赤枠のノードの評価値が 1 と表示__ されたことで __確認できます__。下図の __紫枠の中のノード__ が、__α 狩り__ によって評価値の __計算が省略されたノード__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/06cd558d-929e-7510-40d8-69440a4b3a23.png" width="500">

ここまでで、__α 狩り__ の計算の手順が __正しく表示__ されることが確認できました。

### `calc_score_by_ab` で評価値を計算した mbtree のデータのバグ

上記から、αβ 法の評価値の計算の手順の表示がうまく行われるように見えるかもしれませんが、__実際には `mbtree` のデータにはバグが存在__ します。そのことは上記の後のフレームを見ることで確認することができます。

下図は次の 18 フレームの図で、17 フレームの __上図の赤枠のノードの評価値が確定__ したので、下図のようにその __親ノードが赤枠のノード__ になります。この図には問題はありません。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/82829e6c-e050-dee3-06f6-cc697a818971.png" width="500">

下図は、その次の 19 フレームの図です。下図の __赤枠のノード__ は上図の赤枠のノードの __次の子ノード__ になっているので __正しい__ ですが、図の __赤丸のノードの評価値が表示されてしまう__ というおかしな現象が発生しています。このバグの原因について少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a90cb367-10f7-5248-eb32-2956124e8fa5.png" width="500">

### バグの原因の検証

__`mbtree`__ は最初は __`Mbtree(algo="df")`__ によって、__幅優先アルゴリズム__ で __ゲーム木の作成__ と __ノードの評価値を計算__ したデータです。その後で __`calc_score_by_ab`__ を呼び出して __ゲーム木のルートノードの評価値__ を __αβ 法で計算__ する処理を行っています。

__αβ 法__ では __α 狩りと β 狩り__ によって、__一部のノードに対する処理が省略__ されてしまうため、それらの __省略されたノードの `score_index` 属性の値__ は、`calc_score_by_ab` の処理によって __変化しません__。そのため、それらのノードの __`score_index` 属性の値__ は、__`calc_score_by_df` で計算された値__ が `calc_score_by_ab` の処理によって上書きされずに __そのまま代入されて残っている__ ことになります。

__上図の赤丸のノード__ は、__α 狩り__ によって `calc_score_by_ab` での __計算が省略されたノード__ なので、__`score_index`__ 属性には __`calc_score_by_df`__ によって計算された値が代入されています。また、上図では __19 フレーム目__ で赤丸のノードの __評価値が表示された__ ことから、赤丸のノードの __`score_index` 属性には 19 が代入されている__ ことがわかります。

そのことは、下図のプログラムで __`calc_score_by_df`__ によって __評価値を計算したゲーム木__ のデータに対して Mbtree_Anim で __19 フレーム目を表示__ すると、実行結果のように __19 フレーム目で上図の赤丸のノードの評価値が表示される__ ことから確認できます。

```python
mbtree_df = Mbtree(algo="df")
Mbtree_Anim(mbtree_df, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/574f8054-ba7b-05fa-401c-487ca1158aff.png" width="500">

バグの原因がわかったので、バグを修正する方法について少し考えてみて下さい。

### バグの修正

バグの原因は、`calc_score_by_ab` の処理によって __`score_index`__ 属性の値が __計算されないノードが存在する__ 事なので、`calc_score_by_ab` の処理の中で、αβ 法の処理を行う前に __全てのノードの `score_index`__ 属性の値を __何らかの値で初期化する__ という方法が考えられます。どのような値で初期化すればよいかについて少し考えてみて下さい。

Mbtree_Anim では、アニメーションの __フレームが `score_index` 属性の値以上__ になった場合に、その __ノードを明るく表示して上に評価値を表示__ します。αβ 法で __枝狩りされるノード__ は __評価値が計算されることがない__ ので、__正の無限大__ を表す `float("inf")` を __全ての `score_index` 属性に最初に代入する__ ことでフレームが `score_index` 属性の値以上に __絶対にならなくなる__ ので、__枝狩りされたノードの評価値__ が __表示されることが無くなります__。

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

* __2、3 行目__：ゲーム木のノードの一覧は、`nodelist` 属性に代入されているので、それを利用して全てのノードの `score_index` 属性を正の無限大で初期化する

```python
1  def calc_score_by_ab(self, abroot, debug=False):
元と同じなので省略
2      for node in self.nodelist:
3          node.score_index = float("inf")
4      self.nodelist_by_score = []
5      calc_ab_score(abroot)
6      dprint(debug, "count =", self.count)
7    
8  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

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

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

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

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

```diff_python
def calc_score_by_ab(self, abroot, debug=False):
元と同じなので省略
+   for node in self.nodelist:
+       node.score_index = float("inf")
    self.nodelist_by_score = []
    calc_ab_score(abroot)
    dprint(debug, "count =", self.count)
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

上記の修正後に、下記のプログラムで `calc_score_by_ab` で評価値を計算し直してから Mbtree_Anim を実行すると、実行結果のように 19 フレームのゲーム木の部分木の表示が、正しく行われるようになったことが確認できます。

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

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/614ee508-a924-2652-a817-b0e81acbc0a0.png" width="500">

## ルートノード以外のノードの αβ 法での計算手順の表示

`calc_score_by_ab` では、任意のノードに対して αβ 法で評価値を計算することができます。そこで、念のため __ルートノード以外のノード__ の αβ 法での評価値の計算手順の表示が __正しく行われるか__ どうかを確認することにします。

下記のプログラムは、__深さ 6 のノードの評価値__ を αβ 法で計算しています。実行結果から __6 つのノードの評価値が計算__ された結果、ノードの __評価値が 1 である__ ことがわかります。

```python
mbtree.calc_score_by_ab(mbtree.nodelist_by_depth[6][0], debug=True)
print(mbtree.nodelist_by_depth[6][0].score)
```

実行結果

```
count = 6
1
```

この `mbtree` に対して下記のプログラムで Mbtree_Anim で評価値の計算の手順を表示すると、実行結果のように __最初のフレーム__ では、__深さ 6 のノードが赤枠で表示される__ ことが確認できます。

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

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/73e40bb2-5034-d555-9196-4c65a7b0dce6.png" width="500">

また、途中経過のフレームは省略しますが、__最後のフレーム__ は下図のように表示されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a0596447-6de4-2bad-8db7-00571f45a59d.png" width="500">

上図から、下記の事が確認でき、ルートノード以外のノードに対する αβ 法による評価値の計算手順が正しく表示されることが確認できます。

* 赤枠の __αβ のルートノード__ の __評価値が 1 と計算__ された
* 明るい色の __評価値が計算__ された __ノードの数は 6__ である
* 赤枠の αβ の子孫ノードの中の __暗く表示される 2 つのノード__ は __枝狩り__ が行われて __計算されなかったノード__ である

下図は、上記の 0 ~ 16フレームまでのアニメーションの繰り返しです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/06c1a259-b794-45a9-0283-4bc1335130f1.gif" width="500">

# `dprint` をインポートする場所の修正

上記の `calc_score_by_ab` をそのまま mbtree.py に記述し、__`from ai import dprint` を mbtree.py の先頭に記述__ すると、__[循環インポート](https://qiita.com/ysgeso/items/64de676735836b963712#%E5%BE%AA%E7%92%B0%E3%82%A4%E3%83%B3%E3%83%9D%E3%83%BC%E3%83%88%E3%81%AE%E3%82%A8%E3%83%A9%E3%83%BC%E3%81%AE%E6%84%8F%E5%91%B3%E3%81%A8%E3%81%9D%E3%81%AE%E5%AF%BE%E5%87%A6%E6%96%B9%E6%B3%95)__ のエラーが発生することがわかりました。そこで、下記のプログラムの 2 行目のように `from ai import dprint` を `calc_score_by_ab` の中に記述して __[ローカルなインポート](https://qiita.com/ysgeso/items/6d1430a88e251279d77a#%E5%BE%AA%E7%92%B0%E5%8F%82%E7%85%A7%E3%81%AE%E5%95%8F%E9%A1%8C%E3%81%AE%E4%BF%AE%E6%AD%A3)__ を行うようにすることで循環参照が発生しないように修正することにします。

```python
1  def calc_score_by_ab(self, abroot, debug=False):
元と同じなので省略
2      from ai import dprint
3      for node in self.nodelist:
4          node.score_index = float("inf")
5      self.nodelist_by_score = []
6      calc_ab_score(abroot)
7      dprint(debug, "count =", self.count)
8    
9  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

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

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

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

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

```diff_python
def calc_score_by_ab(self, abroot, debug=False):
元と同じなので省略
+   from ai import dprint
    for node in self.nodelist:
        node.score_index = float("inf")
    self.nodelist_by_score = []
    calc_ab_score(abroot)
    dprint(debug, "count =", self.count)
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

# 今回の記事のまとめ

今回の記事では、__αβ 法__ での __評価値の計算の手順を表示__ するために Mbtree クラスに `calc_score_by_ab` メソッドを定義しました。また、`calc_score_by_ab` によって計算されたゲーム木のデータを __Mbtree_Anim クラスで表示__ する事で、αβ 法での評価値の計算の手順の __アニメーションが正しく表示される__ ことが確認できました。

ただし、現状での Mbtree_Anim での αβ 法の計算の手順の表示には __いくつかわかりづらい__ 点があるので、次回の記事で __改良する__ ことにします。どのように改良すればよいかについて考えてみて下さい。

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

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

# 次回の記事

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

[^1]:[α 狩りと β 狩り](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E7%A5%96%E5%85%88%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F-%CE%B1%CE%B2-%E6%B3%95)による枝狩りが行われる場合があるので、全ての子孫ノードの評価値の計算が行われるとは限りません
[^2]:ミニマックス法の場合も同様の性質を持ちます
[^3]:__最大の評価値__ と __最小の評価値__ は __αβ 法では計算しない__ ので、今回の記事では __以後は言及しません__
[^4]:評価値を計算する関数として `ai_by_abs` を参考にしたいので、`@ai_by_score` のデコレータ式は記述していません
[^5]:`node` ではなく `abroot` という名前にしたのは、`calc_score_by_ab` の中で定義するローカル関数 `calc_ab_score` の仮引数 `node` と区別できるようにするためです。`calc_score_by_ab` と `calc_ab_score` の両方に同じ `node` という名前の仮引数を定義しても、両者は異なる名前空間で管理されるため、異なる仮引数として区別されるのでプログラムは正しく動作します。ただし、そのように仮引数の名前を定義すると、両者が同じ仮引数であると混同されてしまう可能性が高いので、異なる名前にしました