Pythonで〇×ゲームのAIを一から作成する　その144　枝狩りが行われたノードの表示の明確化

# 目次と前回の記事

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

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

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

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

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

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

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

# 枝狩りが行われたノードの表示の明確化

前回の記事で αβ 法で評価値を計算する手順のアニメーションを改良しましたが、まだ改良の余地がいくつかあるので今回の記事でも引き続き改良を行うことにします。

現状の問題点は、__枝狩りが行われたノード__ と、__評価値の計算がまだ行われていないノード__ が同じ暗い色で描画されるため __区別が付けづらい__ 点です。例えば下図の 18 フレーム目では、計算された子ノードの評価値が α 値以下なので、__次のフレームで α 狩りが行われます__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bdb36a00-fa67-828d-f94c-dfc8f3291a57.png" width="500">

実際に下図の次の 19 フレーム目で α 狩りによって __紫色の枠内[^1]のノードの評価値の計算が省略__ されて、β 値が 1 に更新されますが、下図では __枝狩りされた紫色の枠内のノード__ と、__評価値が計算されていないノード__ が __どちらも灰色で描画__ されるため、__区別がつきません__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0e491904-4e09-193b-03e3-0cc5d0c24e10.png" width="500">

そこで、__枝狩りが行われたノード__ を評価値が計算されていないノード __より暗い色で描画__ することで、評価値が計算されていないノードと __区別ができるようにする__ という改良を行います。どのように修正を行えば良いかについて少し考えてみて下さい。

以下の説明では、枝狩りが行われたノードの色を、__より暗い色__ と表記することにします。

## 枝狩りが行われたフレームの記録

現状では以下の方法で評価値が計算されていないノードを暗く表示しています。忘れた方は[以前の記事](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`__ という属性に代入する
* Mbtree クラスの __`draw_subtree`__ メソッドでノードを描画する際に、__アニメーションのフレーム__ とノードの __`score_index` 属性を比較__ し、アニメーションのフレームが __`score_index`__ 属性 __未満__ の場合に __暗く描画__ する
* 評価値が計算されない、__枝狩りが行われたノードを暗く表示する__ ために、__[あらかじめすべてのノードの `score_index` 属性に正の無限大を表す数値を代入](https://qiita.com/ysgeso/items/3de5d3316b78d4925351#%E3%83%90%E3%82%B0%E3%81%AE%E4%BF%AE%E6%AD%A3)__ する

上記と同様に枝狩りが行われたノードに対して __枝狩りが行われたアニメーションのフレームを記録__ し、ノードを描画する際に __アニメーションのフレームと比較__ することで枝狩りが行われたノードをより暗く描画することができるようになります。具体的には以下のようなアルゴリズムで枝狩りが行われたノードをより暗く描画します。

* それぞれのノードに対して __枝狩り（prune）が行われたフレーム__ を __`pruned_index`__ という属性に代入する
* `draw_subtree` ノードを描画する際に、アニメーションのフレームとノードの `pruned_index` 属性を比較し、アニメーションのフレームが __`pruned_index`__ 属性 __以上__ の場合により暗く描画する。__`score_index` の場合と異なり「以上」である__ 点に注意する事
* 枝狩りが __行われていない__ ノードが __より暗く描画されないようにする__ ために、__あらかじめすべてのノードの`pruned_index` 属性に正の無限大を表す数値を代入__ する

__`pruned_index`__ 属性の計算は、`score_index` と同様に __`calc_score_by_ab` メソッド内で計算__ します。どのように計算すればよいかについて少し考えてみて下さい。

## `pruned_index` 属性を計算するアルゴリズム

現状の __`calc_score_by_ab`__ は、__α 狩りまたは β 狩り__ が行われる条件が満たされると、__枝狩りが行われるノードに対する処理が省略__ されてしまうため、枝狩りが行われたノードの __`pruned_index` 属性を計算することはできません__。この問題を解決する方法の一つに、指定したノードとその子孫ノードの __`pruned_index`__ 属性に枝狩りが行われた __アニメーションのフレームを代入__ する __関数を定義__ し、枝狩りが行われた場合に __その関数を利用して枝狩りを行うノードの `pruned_index` 属性を計算__ するという方法があります。

なお、参考までに、別の方法について今回の記事の最後で紹介します。

### `pruned_index` 属性を計算する関数の定義

まず、Mbtree クラスの __`calc_score_by_ab`__ の中に下記のような __ローカル関数を定義__ します。この関数は幅優先アルゴリズムと深さ優先アルゴリズムのどちらの方法でも定義できますが、本記事では __より簡潔に記述__ できる __深さ優先アルゴリズム__ で定義する事にします。

__名前__：`pruned_index` 属性に値を代入（assign）するので、__`assign_pruned_index`__ とする
__処理__：指定したノードと、その子孫ノードの `pruned_index` 属性に、指定した値を代入する処理を、深さ優先アルゴリズムで行う
__入力__：仮引数 __`node`__ に __処理を行うノード__ を、仮引数 __`index`__ に __`pruned_index` 属性に代入する値__ を代入する
__出力__：なし

下記は __`assign_pruned_index`__ の定義です。行っている処理は 2 行目で `node` の __`pruned_index` 属性に `index` を代入__ し、3、4 行目で `node` の __それぞれの子ノード__ に対して `index` を実引数に記述して __`assign_pruned_index`__ を __再帰呼び出し__ するというものです。この処理によって深さ優先アルゴリズムで、指定したノードとそのすべての子孫ノードの `pruned_index` 属性に `index` を代入することができます。

```python
1  def assign_pruned_index(node, index):
2      node.pruned_index = index
3      for childnode in node.children:
4          assign_pruned_index(childnode, index)
```

次に、__`calc_score_by_ab`__ の中で __枝狩りが行われた際__ に、枝狩りによって評価値の計算を省略する __残りの子ノードに対して `assign_pruned_index` を呼び出す__ ように修正します。また、__あらかじめ__ すべてのノードの __`pruned_index` 属性に正の無限大を代入__ する処理を記述します。下記はそのように __`calc_score_by_ab`__ を修正したプログラムです。

* __7 ~ 10 行目__：上記の `assign_pruned_index` をローカル関数として定義する
* __16 ~ 18 行目__：15 行目の条件式で max ノードで β 狩りを行うことが判定された場合に、下記の手順で __残りの子ノード__ に対して __`calc_score_by_ab` を呼び出す__ ことで、__枝狩りが行われたすべてのノード__ の __`pruned_index`__ 属性に __アニメーションのフレームを代入__ する
* __16 行目__：残りの子ノードは、子ノードの一覧を表す __`node.children`__ の中で __`childnode` より後の要素__ である。そこで、`node.children` の中で __`childnode`__ が代入されている __要素のインデックス__ を list の __[`index` メソッド](https://qiita.com/ysgeso/items/51c2eba867aa560808c6#excel_to_xy-%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%9D%E3%81%AE-5%E6%96%87%E5%AD%97%E5%88%97%E3%81%AE%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB%E3%82%92%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B)__ を利用して計算する
* __17 行目__：__`childnode` より後の要素の一覧__ は、list の __[スライス表記](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#%E3%82%B9%E3%83%A9%E3%82%A4%E3%82%B9%E8%A1%A8%E8%A8%98-%E3%81%9D%E3%81%AE-4start-%E3%81%A8-end-%E3%81%AE%E7%9C%81%E7%95%A5)__ を利用して __`node.children[index + 1:]`__ と記述できるので、それに対する繰り返し処理を行う
* __18 行目__：`assign_pruned_index` を呼び出して残りの子ノードとその子孫ノードの `pruned_index` 属性に枝狩りが行われたアニメーションのフレームを代入する。枝狩りが行われた __アニメーションのフレームのデータ__ は __`nodelist_by_score`__ の __最後の要素に代入__ されているので、そのインデックスは __`len(self.nodelist_by_score) - 1)`__ で計算できる
* __24 ~ 26 行目__：min ノードの α 狩りが行われた場合も同様の処理を行う
* __32 行目__：αβ 法で評価値を計算する前に、すべてのノードの `pruned_index` 属性に正の無限大を表す `float("inf")` を代入しておく

```python
 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3
 4  def calc_score_by_ab(self, abroot, debug=False):           
 5      self.count = 0
 6       
 7      def assign_pruned_index(node, index):
 8          node.pruned_index = index
 9          for childnode in node.children:
10              assign_pruned_index(childnode, index)
11         
12      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
13              if node.mb.turn == Marubatsu.CIRCLE:
14                  for childnode in node.children:
元と同じなので省略                
15                      if score >= beta:
16                          index = node.children.index(childnode)
17                          for prunednode in node.children[index + 1:]:
18                              assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
19                          break
20                  node.score = alpha
21              else:
22                  for childnode in node.children:
元と同じなので省略
23                      if score <= alpha:
24                          index = node.children.index(childnode)
25                          for prunednode in node.children[index + 1:]:
26                              assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
27                          break
28                  node.score = beta
元と同じなので省略
29      from ai import dprint       
30      for node in self.nodelist:
31          node.score_index = float("inf")
32          node.pruned_index = float("inf")
元と同じなので省略        
33     
34  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

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

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

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

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

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

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

def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
+   def assign_pruned_index(node, index):
+       node.pruned_index = index
+       for childnode in node.children:
+           assign_pruned_index(childnode, index)
        
    def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
元と同じなので省略                
                    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)
                        break
                node.score = alpha
            else:
                for childnode in node.children:
元と同じなので省略
                    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)
                        break
                node.score = beta
元と同じなので省略
    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
+       node.pruned_index = float("inf")
元と同じなので省略        
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

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

次に、ゲーム木の部分木を描画する Mbtree クラスの __`draw_subtree`__ メソッドを、__枝狩りが行われたノードがより暗く描画__ されるように修正します。どのように修正すれば良いかについて少し考えてみて下さい。

__ノードの表示の暗さ__ は、__`draw_subtree`__ 内の下記のローカル関数 __[`calc_darkness`](https://qiita.com/ysgeso/items/ff32ebabb69a4754dd4a#calc_darkness-%E3%81%AE%E5%BE%A9%E7%BF%92) で計算__ しています。この中で、__Mbtree_Anim によるアニメーション__ が行われている場合の処理は __12、13 行目に記述__ されています。

```python
 1  def calc_darkness(node):
 2      if show_bestmove:
 3          if node.parent is None:
 4              return 0, show_score
 5          elif node.mb.last_move in node.parent.bestmoves:
 6              return 0, show_score
 7          else:
 8              return 0.2, show_score
 9         
10      if anim_frame is None:
11          return 0, show_score
12      index = node.score_index if isscore else node.id
13      return (0.5, False) if index > anim_frame else (0, isscore)
```

Mbtree_Anim で評価値を計算する手順を描画する場合は `isscore` に `True` が代入されているので、12、13 行目では以下の処理が行われます。

* __評価値が計算されるより前のアニメーションのフレーム__ の場合は __暗い色（0.5)で評価値を描画しない（False）__ という意味を表す __` (0.5, False)`__ を返す
* そうでない場合は __明るい色で評価値を描画する__ という意味を表す __`(0, True)`__ を返す

__枝狩りが行われたノード__ は __評価値が計算されることはない__ ので、12、13 行目が実行されるとそのノードが __暗い色で描画される__ ことになります。そのため、枝狩りが行われたノードを、__枝狩りが行われたフレーム以降__ で __より暗く描画__ するためには、__その処理を 12 行目よりも前に記述__ する必要があります。

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

* __9 行目__：__`pruned_index`__ 属性は、`calc_score_by_ab` を実行しない限り作られないので __存在しない場合がある__。そこで、組み込み関数 __`get_attr`__ を利用して、__`pruned_index` 属性が存在する場合はその値__ を、__存在しない場合は `None`__ をローカル変数 `pruned_index` に代入する処理を行う。`get_attr` について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-getattr-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E4%BF%AE%E6%AD%A3)を復習すること
* __10、11 行目__：`pruned_index` が `None` ではなく、アニメーションのフレーム __以下の場合__ にノードを __より暗い色で評価値を表示しない__ ことを表す __`(0.8, False)`__ を返すように修正する。なお、もっと暗くしたい場合は 0.8 を 1 以下のより大きな値に修正すれば良い

```python
 1  import matplotlib.patches as patches
 2 
 3  def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
 4                   isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):   
 5                     
 6      def calc_darkness(node):
元と同じなので省略
 7          if anim_frame is None:
 8              return 0, show_score
 9          pruned_index = getattr(node, "pruned_index", None)
10          if pruned_index is not None and anim_frame >= pruned_index:
11              return (0.8, False)
12          index = node.score_index if isscore else node.id
13          return (0.5, False) if index > anim_frame else (0, isscore)
元と同じなので省略
14             
15  Mbtree.draw_subtree = draw_subtree
```

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

```python
import matplotlib.patches as patches

def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
                    isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):   
                    
    def calc_darkness(node):
        if show_bestmove:
            if node.parent is None:
                return 0, show_score
            elif node.mb.last_move in node.parent.bestmoves:
                return 0, show_score
            else:
                return 0.2, show_score
            
        if anim_frame is None:
            return 0, show_score
        pruned_index = getattr(node, "pruned_index", None)
        if pruned_index is not None and anim_frame >= pruned_index:
            return (0.8, False)
        index = node.score_index if isscore else node.id
        return (0.5, False) if index > anim_frame else (0, isscore)
    
    self.nodes_by_rect = {}

    if centernode is None:
        centernode = self.root
    self.calc_node_height(N=centernode, maxdepth=maxdepth)
    if show_bestmove:
        width = 5 * 10
    else:
        width = 5 * (maxdepth + 1)
    height = centernode.height
    parent = centernode.parent
    if parent is not None:
        height += (len(parent.children) - 1) * 4
        parent.height = height
    if ax is None:
        fig, ax = plt.subplots(figsize=(width * size, (height + 1) * size))
        ax.set_xlim(0, width)
        ax.set_ylim(-1, height)   
        ax.invert_yaxis()
        ax.axis("off")        
    
    bottom, top = ax.get_ylim()
    top = -1
    for depth in range(1, 10, 2):
        ax.add_artist(patches.Rectangle(xy=(depth * 5 - 1, top), width=5,
                                        height=bottom - top, fc="whitesmoke"))               

    if show_bestmove:
        bestx = 5 * maxdepth + 4
        bestwidth = 50 - bestx
        ax.add_artist(patches.Rectangle(xy=(bestx, -1), width=bestwidth,
                                        height=height + 1, fc="lightgray"))
    
    nodelist = [centernode]
    depth = centernode.depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        if parent is not None:
            dy = parent.children.index(centernode) * 4
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
                childnodelist.append(None)
            else:
                dx = 5 * node.depth
                emphasize = node is selectednode
                darkness, show_score = calc_darkness(node)
                rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, darkness=darkness,
                                    show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = node
                if show_bestmove and depth == maxdepth:
                    bestnode = node
                    while len(bestnode.bestmoves) > 0:
                        bestmove = bestnode.bestmoves[0]
                        bestnode = bestnode.children_by_move[bestmove]
                        dx = 5 * bestnode.depth
                        bestnode.height = 4
                        emphasize = bestnode is selectednode
                        rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth, emphasize=emphasize,
                                                show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
                        self.nodes_by_rect[rect] = bestnode                                          
                    
                dy += node.height
                if len(node.children) > 0:  
                    childnodelist += node.children
                else:
                    childnodelist.append(None)
        depth += 1
        nodelist = childnodelist
        
    if parent is not None:
        dy = 0
        for sibling in parent.children:
            if sibling is not centernode:
                sibling.height = 4
                dx = 5 * sibling.depth
                darkness, show_score  = calc_darkness(sibling)
                rect = sibling.draw_node(ax, maxdepth=sibling.depth, size=size, darkness=darkness,
                                        show_score=show_score, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = sibling
            dy += sibling.height
        dx = 5 * parent.depth
        darkness, show_score  = calc_darkness(parent)
        rect = parent.draw_node(ax, maxdepth=maxdepth, darkness=darkness, 
                                show_score=show_score, size=size, lw=lw, dx=dx, dy=0)
        self.nodes_by_rect[rect] = parent
    
        node = parent
        while node.parent is not None:
            node = node.parent
            node.height = height
            dx = 5 * node.depth
            darkness, show_score  = calc_darkness(node)
            rect = node.draw_node(ax, maxdepth=node.depth, darkness=darkness,
                                show_score=show_score, size=size, lw=lw, dx=dx, dy=0)
            self.nodes_by_rect[rect] = node
            
Mbtree.draw_subtree = draw_subtree
```
</details>

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

```diff_python
import matplotlib.patches as patches

def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
                    isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):   
                    
    def calc_darkness(node):
元と同じなので省略
        if anim_frame is None:
            return 0, show_score
+       pruned_index = getattr(node, "pruned_index", None)
+       if pruned_index is not None and anim_frame >= pruned_index:
+           return (0.8, False)
        index = node.score_index if isscore else node.id
        return (0.5, False) if index > anim_frame else (0, isscore)
元と同じなので省略
            
Mbtree.draw_subtree = draw_subtree
```
</details>

## 動作の確認

上記の修正後に下記のプログラムで `calc_score_by_ab` によって αβ 法で評価値を計算した `mbtree` に対して Mbtree_Anim を実行して __正しく表示されるかどうかを確認します__。

```python
from tree import Mbtree_Anim

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

下記は __α 狩りが行われる直前__ の 18 フレーム目[^2]と α 狩りが行われた 19 フレーム目の画像です。19 フレーム目の画像では、__2 つのノード__ の枝狩りが行われて __より暗い色で描画される__ ようになったことが確認できます。なお、下図を見てまだ区別がつきづらいと思った方は、先程の `calc_darkness` の 13 行目の評価値が計算されていないノードの暗さを表す 0.5 より小さくしてもう少し明るく描画するようにすると良いでしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b2078ed1-3932-b450-d3c0-6bd19106ae45.png" width="500">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c399a04c-65a0-e03d-79bf-604b7493b7f6.png" width="500">

下記は __β 狩りが行われる直前__ の 125 フレーム目と β 狩りが行われた 126 フレーム目の画像です。126 フレーム目の画像から __5 つのノード__ が枝狩りが行われて __より暗い色で描画される__ ようになったことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a240ac82-e86f-3024-6ae5-ee0fb577b752.png" width="500">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8221a61b-4260-48a0-326b-8c16e657490d.png" width="500">

__かなり多くのノードの枝狩りが行われる例__ として下図の 14324 フレーム目とその次のフレームを紹介します。14325 フレーム目では、赤枠の __2 つ目以降の子ノードとその子孫ノード__ が __すべて枝狩りの対象となる__ ため、図にはそれらのノードが全て描画されてはいませんが、かなり多くの数のノードの枝狩りが行われます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ccd9909d-daa8-fe3e-253c-5a74926a868c.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6e38472b-686c-388f-12f9-4f85fcd8b76e.png" width="300">

## 別の実装方法

上記では __`assign_pruned_index`__ という __関数を定義__ して枝狩りが行われたノードの `pruned_index` 属性の値を計算しましたが、__そのような関数を定義せず__ に、__`calc_score_by_ab` の中で `pruned_index` 属性の値を計算__ することもできます。

なお、__その実装方法__ は `assign_pruned_index` という関数を定義する実装方法と比べると、__プログラムがわかりづらい__ と思いますので __本記事では採用しません__。ただし、どちらがわかりやすいかは人それぞれだと思います。また、__場合によってはこちらの実装方法のほうがわかりやすくなることもある__ と思いますので紹介します。

### 実装方法の考え方

この実装方法の考え方は以下の通りです。

* `calc_score_by_ab` 内で定義されたローカル関数 __`calc_ab_score`__ に、__処理を行うノード__ が __枝狩りが行われているかどうかを表す仮引数 `pruned`__ を追加する
* __仮引数 `pruned` が `True`__ の場合は、その __子ノードも枝狩りが行われる__ ので `calc_ab_score` 内で __`calc_ab_score`__ を __再帰呼び出し__ して __子ノードの処理を行う際__ に、仮引数 `pruned` に対応する __実引数に `pruned` を記述__ して呼び出すことで、子ノードでも枝狩りが行われたノードとして処理が行われるようになる
* __仮引数 `pruned` が `False`__ の場合は場合は、__α 狩りまたは β 狩りが行われるまでの間__ は、__子ノードの枝狩りは行われない__。そこで、以下のような処理を行うことで、適切な処理が行われるようにする
    * __`calc_ab_score`__ を __再帰呼び出し__ する際に、上記の場合と同様に仮引数 `pruned` に対応する __実引数に `pruned` を記述__ する
    * __枝狩りが行われた時点で `pruned` に `True` を代入する__ ことで、枝狩りが行われるまでの間は子ノードが枝狩りが行われていないノードとして処理が行われ、枝狩りが行われた後は子ノードが枝狩りが行われたノードとして処理が行われるようになる
* __`calc_score_by_ab` から `calc_ab_score` を呼び出す際__ には、αβ 法の計算を行う前で __枝狩りは行われていない__ ので、仮引数 __`pruned` に `False` が代入__ されるように呼び出す

具体的には、__`calc_ab_score`__ 内で、仮引数 __`pruned` の値に応じて__ 以下のような処理を行うようにプログラムを修正します。ただし、何れの場合も __`calc_ab_score` を再帰呼び出し__ する際には、仮引数 `pruned` に対応する __実引数に `pruned` を記述__  して呼び出します。

* __`pruned`__ に __`True` が代入__ されている場合
    * 最初に __`pruned_index`__ 属性に __現在のアニメーションのフレームを代入__ する
    * 枝狩りがされたノードは __評価値の計算の処理が行われない__ ので、__`nodelist_by_score`__ 属性や、__`ablist_by_score`__ 属性に要素を追加する __処理を行わないようにする__
    * 繰り返し処理の中で __子ノードに対する `calc_ab_score` の再帰呼び出しは行う__ が、子ノードの __評価値に関する__ 枝狩りや α 値、β 値の更新の __処理は行わない__
* __`pruned`__ に __`False` が代入__ されている場合
    * 枝狩りが行われていないことを意味するので __これまでと同様の処理__ を行う
    * ただし、__α 狩りまたは β 狩り__ が行われた場合は __`pruned` に `True`__ を代入し、__break 文を削除__ して繰り返し処理を __中断しないよう__ にする。そのようにすることで、__残りの子ノード__ に対する繰り返し __処理が続行__ し、__`calc_ab_score`__ の再帰呼び出しで仮引数 `pruned` に対応する __実引数に `True`__ が記述されて呼び出されるようになる


### `calc_score_by_ab` の修正

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

* __4 行目__：仮引数 `pruned` を追加する。また、__`pruned`__ を __デフォルト値が `False`__ の __デフォルト引数とする__ ことで、__`calc_score_by_ab` から `calc_ab_score` を呼び出す際に__ 仮引数 `pruned` に対応する実引数を記述するように __修正しなくても良いようにする__
* __5、6 行目__：`pruned` が `True` の場合に `pruned_index` に現在のアニメーションのフレームを代入するようにする
* __7 ~ 9、37 ~ 40 行目__：__`pruned`__ が __`False` の場合のみ__ `nodelist_by_score` 属性や、`ablist_by_score` 属性に __要素を追加する処理を行う__ ようにする
* __12、25 行目__：__`calc_ab_score`__ の __再帰呼び出し__ で仮引数 `pruned` に対応する __実引数に `pruned` を記述__ して呼び出すように修正する
* __13 ~ 21 行目__：子ノードの評価値に関する枝狩りなどの処理を、`pruned` が `False` の場合のみ行うように修正する
* __21 行目__：__β 狩り__ が行われる場合に __`pruned` に `True` を代入__ し、__break 文を削除__ して残りの枝狩りがされたノードに対する __繰り返し処理が続行される__ ように修正する
* __26 ~ 34 行目__：min ノードに対して上記と同様の修正を行う

```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"), pruned=False):
 5          if pruned:
 6              node.pruned_index = len(self.nodelist_by_score) - 1
 7          else:
 8              self.nodelist_by_score.append(node)
 9              self.ablist_by_score.append((alpha, beta, None, "start"))
元と同じなので省略
10              if node.mb.turn == Marubatsu.CIRCLE:
11                  for childnode in node.children:
12                      score = calc_ab_score(childnode, alpha, beta, pruned)
13                      if not pruned:
14                          self.nodelist_by_score.append(node)
15                          self.ablist_by_score.append((alpha, beta, score, "score"))
16                          if score > alpha:
17                              alpha = score
18                          self.nodelist_by_score.append(node)
19                          self.ablist_by_score.append((alpha, beta, None, "update"))
20                          if score >= beta:
21                              pruned = True
22                  node.score = alpha
23              else:
24                  for childnode in node.children:
25                      score = calc_ab_score(childnode, alpha, beta, pruned)
26                      if not pruned:
27                          self.nodelist_by_score.append(node)
28                          self.ablist_by_score.append((alpha, beta, score, "score"))
29                          if score < beta:
30                              beta = score
31                          self.nodelist_by_score.append(node)
32                          self.ablist_by_score.append((alpha, beta, None, "update"))
33                          if score <= alpha:
34                              pruned = True
35                  node.score = beta
36 
37          if not pruned:
38              self.nodelist_by_score.append(node)
39              self.ablist_by_score.append((alpha, beta, None, "end"))
40              node.score_index = len(self.nodelist_by_score) - 1          
41          return node.score
元と同じなので省略
42     
43  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

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

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

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

<details><summary><strong>修正箇所（3 箇所ある <code>if not pruned:</code> のブロックのインデントの修正は省略しました）</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")):
+   def calc_ab_score(node, alpha=float("-inf"), beta=float("inf"), pruned=False):
-       self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alpha, beta, None, "start"))
+       if pruned:
+           node.pruned_index = len(self.nodelist_by_score) - 1
+       else:
+           self.nodelist_by_score.append(node)
+           self.ablist_by_score.append((alpha, beta, None, "start"))
元と同じなので省略
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta)
+                   score = calc_ab_score(childnode, alpha, beta, pruned)
+                   if not pruned:
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, score, "score"))
                        if score > alpha:
                            alpha = score
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, None, "update"))
                        if score >= beta:
+                           pruned = True
-                           break                            
                node.score = alpha
            else:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta)
+                   score = calc_ab_score(childnode, alpha, beta, pruned)
+                   if not pruned:
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, score, "score"))
                        if score < beta:
                            beta = score
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, None, "update"))
                        if score <= alpha:
+                           pruned = True
-                           break
                node.score = beta

+       if not pruned:
            self.nodelist_by_score.append(node)
            self.ablist_by_score.append((alpha, beta, None, "end"))
            node.score_index = len(self.nodelist_by_score) - 1          
        return node.score
元と同じなので省略
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```

</details>

### 動作の確認

上記の修正後に下記のプログラムを実行して `calc_score_by_ab` で計算し直した `mbtree` に対する Mbtree_Anim の動作を確認します。

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

__次のフレームでα 狩り__ が行われる下図の 18 フレーム目は __先ほどと同じ表示__ が行われることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bdb36a00-fa67-828d-f94c-dfc8f3291a57.png" width="500">

その次の __α 狩りが行われた__ 下図の 19 フレーム目も先ほどと同様に __枝狩りが行われたノードがより暗く表示される__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c399a04c-65a0-e03d-79bf-604b7493b7f6.png" width="500">

しかし、その次の下図の 20 フレーム目では、__評価値が確定するフレームが飛ばされて__、親ノードのフレームの処理が表示されるという __バグが発生__ していることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/60f6b2c6-60bf-68b3-041b-ae36c1a938f6.png" width="500">

このようなバグが発生する原因について少し考えてみて下さい。

### バグの検証

上記のバグは、__α 狩りが発生した際に生じている__ ので、その場合の __`calc_ab_score`__ の __処理を検証__ することにします。

18 フレームの赤枠のノードに対して `calc_ab_score` が呼ばれると、下記のような手順で処理が行われるため評価値が確定されたフレームが記録されなくなります。

* __枝狩りがされていない__ ので、仮引数 __`pruned`__ には __`False` が代入__ されている
* 2 つ目の子ノードの評価値が計算された時点で __α 狩り__ が行われて __`pruned`__ に __`True` が代入__ される
* その結果、__繰り返し処理が終了した時点__ の __`pruned` の値は `True`__ なので、`calc_ab_score` の最後の下記の __評価値が確定したフレームを記録する処理__ が __実行されなくなる__

```python
        if not pruned:
            self.nodelist_by_score.append(node)
            self.ablist_by_score.append((alpha, beta, None, "end"))
            node.score_index = len(self.nodelist_by_score) - 1          
        return node.score
```

__枝狩り__ が行われた際に __評価値の計算の処理が省略される__ のは、__残りの子ノードとその子孫ノード__ で、__そのノードの評価値を計算する処理が省略されるわけではない__ ので、__`calc_ab_score`__ の処理の途中で __`pruned` の値を変更してはいけません__。それも関わらず枝狩りが行われた際に __`pruned` の値を変更してしまっている__ のがこの __エラーの原因__ です。

### バグの修正

仮引数 __`pruned` を変更しないようにする__ 方法の一つに、__子ノードに対する繰り返し処理を行う前__ に __別の変数に `pruend` を代入__ し、枝狩りが行われた際に __その変数の値を `True` に変更する__ という方法があります。

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

* __5 行目__：子ノードの評価値を計算する前に、`child_pruned` に `pruned` を代入する
* __8、9、17、21、22、30 行目__：`pruned` を `child_pruned` に修正する

```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"), pruned=False):
元と同じなので省略
 5              child_pruned = pruned
 6              if node.mb.turn == Marubatsu.CIRCLE:
 7                  for childnode in node.children:
 8                      score = calc_ab_score(childnode, alpha, beta, child_pruned)
 9                      if not child_pruned:
10                          self.nodelist_by_score.append(node)
11                          self.ablist_by_score.append((alpha, beta, score, "score"))
12                          if score > alpha:
13                              alpha = score
14                          self.nodelist_by_score.append(node)
15                          self.ablist_by_score.append((alpha, beta, None, "update"))
16                          if score >= beta:
17                              child_pruned = True
18                  node.score = alpha
19              else:
20                  for childnode in node.children:
21                      score = calc_ab_score(childnode, alpha, beta, child_pruned)
22                      if not child_pruned:
23                          self.nodelist_by_score.append(node)
24                          self.ablist_by_score.append((alpha, beta, score, "score"))
25                          if score < beta:
26                              beta = score
27                          self.nodelist_by_score.append(node)
28                          self.ablist_by_score.append((alpha, beta, None, "update"))
29                          if score <= alpha:
30                              child_pruned = True
31                  node.score = beta
元と同じなので省略
32    
33  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"), pruned=False):
        if pruned:
            node.pruned_index = len(self.nodelist_by_score) - 1
        else:
            self.nodelist_by_score.append(node)
            self.ablist_by_score.append((alpha, beta, None, "start"))
        self.count += 1
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            if node.mb.turn == Marubatsu.CIRCLE:
                alpha = node.score
            else:
                beta = node.score
        else:
            child_pruned = pruned
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta, child_pruned)
                    if not child_pruned:
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, score, "score"))
                        if score > alpha:
                            alpha = score
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, None, "update"))
                        if score >= beta:
                            child_pruned = True
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta, child_pruned)
                    if not child_pruned:
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, score, "score"))
                        if score < beta:
                            beta = score
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, None, "update"))
                        if score <= alpha:
                            child_pruned = True
                node.score = beta

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

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

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

```diff_python
def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
    def calc_ab_score(node, alpha=float("-inf"), beta=float("inf"), pruned=False):
元と同じなので省略
+           child_pruned = pruned
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta, pruned)
+                   score = calc_ab_score(childnode, alpha, beta, child_pruned)
-                   if not pruned:
+                   if not child_pruned:
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, score, "score"))
                        if score > alpha:
                            alpha = score
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, None, "update"))
                        if score >= beta:
-                           pruned = True
+                           child_pruned = True
                node.score = alpha
            else:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta, pruned)
+                   score = calc_ab_score(childnode, alpha, beta, child_pruned)
-                   if not pruned:
+                   if not child_pruned:
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, score, "score"))
                        if score < beta:
                            beta = score
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, None, "update"))
                        if score <= alpha:
-                           pruned = True
+                           child_pruned = True
                node.score = beta
元と同じなので省略
   
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

上記の修正後に下記のプログラムを実行して `calc_score_by_ab` で計算し直した `mbtree` に対する Mbtree_Anim の動作を確認すると、実行結果のように __20 フレーム目__ に赤枠のノードの評価値が確定した図が __正しく描画される__ ことが確認できます。

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

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/fe570d03-f50b-25a5-c0ef-54771ac18024.png" width="500">

なお、先程も説明しましたが、この方法はプログラムがわかりづらくなる点と、上記のようなバグが発生する可能性があるので本記事では採用しません。

# 今回の記事のまとめ

今回の記事では枝狩りされたノードをより暗い色で描画して区別できるようにする改良を行いました。また、その改良を行う 2 種類の方法を紹介しました。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/741c2c18f0bc6fcdba27

[^1]:この紫色の枠は説明のために表記したものなので、実際には描画されません
[^2]:18 フレーム目の画像は先ほどと同じです