Pythonで〇×ゲームのAIを一から作成する　その121　部分木の動的な作成の続きと潜在的なバグ

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/900d36483538c2745d9a

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

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

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

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

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

# 今回の記事の内容

前回の記事では、__`draw_subtree`__ メソッドで表示する __部分木を動的に作成する処理__ の実装を開始しました。今回の記事ではその実装の続きを行います。

また、今回の記事では、これまでのプログラムに存在していたが、明るみに出ていなかった __潜在的なバグ__ がいくつか発生します。このような潜在的なバグは、プログラムに __新しい機能を実装した際に発生__ し、__しばらくたった後で発覚する__ ことが良くあるので、その実例として紹介します。

# 最善手を着手し続けた場合の局面の表示

Mbtree_GUI クラスで表示する部分木は、下記のプログラムの実行結果のように __最善手を着手し続けた場合の局面__ を灰色の背景の上に表示しますが、__`create_subtree`__ で作成した部分木には最善手を着手し続けた場合の局面のノードは __作成されていない__ ので、 __`draw_subtree`__ で最善手を着手し続けた場合の局面を __描画することはできません__。

```python
from tree import Mbtree, Mbtree_GUI

mbtree = Mbtree.load("../data/aidata")
Mbtree_GUI(mbtree)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/119ed9a3-13f0-fbae-c1b5-ef3780ab74b3.png" width="350">

従って、Mbtree_GUI クラスで表示する部分木のデータを `create_subtree` で作成して表示するためには、__最善手を着手し続けた場合の局面のノードを作成する__ ように `create_subtree` を修正する必要があります。

最善手を着手し続けた場合の局面のノードを作成するためには、__各ノードの最善手の一覧の情報をノードの `bestmoves` 属性に代入するが必要__ があります。[以前の記事](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#board-%E5%B1%9E%E6%80%A7%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E5%B1%80%E9%9D%A2%E3%81%A8%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%AF%BE%E5%BF%9C%E8%A1%A8%E3%81%AE%E4%BD%9C%E6%88%90)で __局面と最善手の対応表を dict で表現したデータを計算してファイルに保存済__ なので、それを使ってノードの最善手の一覧を計算することができます。また、そのデータを保存した bestmoves_by_board.dat や [bestmoves_by_board_shortest_victory.dat](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#ai_gt6-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-ai) などの __ファイルサイズは約 20 KB と小さい__ のでファイルから __読み込む際に時間はほとんどかかりません__。

実際に筆者のパソコンで下記のプログラムで `%%timeit` を使ってファイルから bestmoves_by_board.dat を読み込む処理の時間を計測した所、実行結果のように数ミリ秒で実行できることが確認できました。

```python
%%timeit
from util import load_bestmoves

load_bestmoves("../data/bestmoves_by_board.dat")
```

実行結果

```
5.48 ms ± 327 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
```

## Node クラスの `__init__` メソッドの修正

下記のプログラムのように Node クラスの __`__init__`__ メソッドを修正することで、__ノードの作成時に最善手を計算して `bestmoves` 属性に代入__ することができます。

* __3 行目__：デフォルト値を `None` とする、局面と最善手の対応表のデータを代入する仮引数 `bestmoves_by_board` を追加する
* __4、5 行目__：`bestmoves_by_board` が `None` でない場合に、その値とゲーム盤を文字列に変換した値を利用して最善手の一覧を計算し、`bestmoves` 属性に代入する

```python
1  from tree import Node
2
3  def __init__(self, mb, parent=None, depth=0, bestmoves_by_board=None):
元と同じなので省略
4      if bestmoves_by_board is not None:
5          self.bestmoves = bestmoves_by_board[self.mb.board_to_str()]
6        
7  Node.__init__ = __init__
```

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

```python
from tree import Node

def __init__(self, mb, parent=None, depth=0, bestmoves_by_board=None):
    self.id = Node.count
    Node.count += 1
    self.mb = mb
    self.parent = parent
    self.depth = depth
    self.children = []
    self.children_by_move = {}   
    if bestmoves_by_board is not None:
        self.bestmoves = bestmoves_by_board[self.mb.board_to_str()]
        
Node.__init__ = __init__
```
</details>

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

```diff_python
from tree import Node

-def __init__(self, mb, parent=None, depth=0):
+def __init__(self, mb, parent=None, depth=0, bestmoves_by_board=None):
元と同じなので省略
+   if bestmoves_by_board is not None:
+       self.bestmoves = bestmoves_by_board[self.mb.board_to_str()]
        
Node.__init__ = __init__
```
</details>

## Node クラスの `calc_children` メソッドの修正

Node クラスの `__init__` メソッドの修正にあわせて __Node クラスのインスタンスを作成する処理を修正__ する必要があります。まず、子ノードの一覧を作成する Node クラスの __[`calc_children`](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E5%AD%90%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9)__ メソッドを下記のプログラムのように修正します。

* __3 行目__：デフォルト値を `None` とする仮引数 `bestmoves_by_board` を追加する
* __9 行目__：__`Node` クラスのインスタンスを作成する際__ にキーワード引数 __`bestmoves_by_board=bestmoves_by_board` を記述する__ ように修正する

```python
 1  from copy import deepcopy
 2
 3  def calc_children(self, bestmoves_by_board=None):
 4      self.children = []
 5      for x, y in self.mb.calc_legal_moves():
 6          childmb = deepcopy(self.mb)
 7          childmb.move(x, y)
 8          self.insert(Node(childmb, parent=self, depth=self.depth + 1, 
 9                           bestmoves_by_board=bestmoves_by_board))
10        
11  Node.calc_children = calc_children
```

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

```python
from copy import deepcopy

def calc_children(self, bestmoves_by_board=None):
    self.children = []
    for x, y in self.mb.calc_legal_moves():
        childmb = deepcopy(self.mb)
        childmb.move(x, y)
        self.insert(Node(childmb, parent=self, depth=self.depth + 1,
                         bestmoves_by_board=bestmoves_by_board))
        
Node.calc_children = calc_children
```
</details>

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

```diff_python
from copy import deepcopy

-def calc_children(self):
+def calc_children(self, bestmoves_by_board=None):
    self.children = []
    for x, y in self.mb.calc_legal_moves():
        childmb = deepcopy(self.mb)
        childmb.move(x, y)
-       self.insert(Node(childmb, parent=self, depth=self.depth + 1))
+       self.insert(Node(childmb, parent=self, depth=self.depth + 1, 
+                        bestmoves_by_board=bestmoves_by_board))
        
Node.calc_children = calc_children
```
</details>

## Mbtree クラスの `create_subtree` の修正

次に、Mbtree クラスの `create_subtree` の中で __ノードを作成する処理を修正__ します。

__局面と最善手の対応表__ のデータは、`create_subtree` の仮引数 __`subtree`__ に代入する dict の __`bestmoves_by_board`__ というキーの値に代入することにし、その値を使ってノードを作成するように修正します。

また、これまでは `maxdepth` までの深さのノードを作成しましたが、__`maxdepth` より深いノード__ として、__最善手を着手しつづけた局面を表すノードを作成する__ ように修正する必要があります。

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

* __4 行目__：`bestmoves_by_board` に局面と最善手の対応表のデータを代入する
* __5、8、10 行目__：ノードを作成する際と、子ノードの一覧を作成する際に、キーワード引数 `bestmoves_by_board=bestmoves_by_board` を記述するように修正する
* __6 行目__：繰り返しの条件式から、`depth < maxdepth` の条件を削除する
* __9 行目__：10 行目の処理は、深さが `maxdepth` 未満の場合に行う処理なので、`else` を `elif depth < maxdepth` に修正する
* __11 ~ 20 行目__：`depth` が `maxdepth` 以上の場合の処理を記述する
* __12 行目__：合法手が存在する、ゲーム中の場合のみ処理を行うようにする
* __13 行目__：`node` の局面のデータを複製して `childmb` に代入する
* __14 ~ 16 行目__：`node` の局面を表す文字列を計算し、`bestmoves_by_board` を使って、その局面の最初の最善手を計算して `childmb` に着手を行う
* __17 ~ 19 行目__：最善手を着手した局面のノードを作成し、子ノードに追加する

```python
 1  from marubatsu import Marubatsu
 2
 3  def create_subtree(self):
 4      bestmoves_by_board = self.subtree["bestmoves_by_board"]
 5      self.root = Node(Marubatsu(), bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
 6      while len(nodelist) > 0:
元と同じなので省略
 7                  childnode = Node(childmb, parent=node, depth=depth+1,
 8                                   bestmoves_by_board=bestmoves_by_board)   
元と同じなので省略
 9              elif depth < maxdepth:
10                  node.calc_children(bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
11              else:
12                  if node.mb.status == Marubatsu.PLAYING:
13                      childmb = deepcopy(node.mb)
14                      board_str = node.mb.board_to_str()               
15                      x, y = bestmoves_by_board[board_str][0]
16                      childmb.move(x, y)
17                      childnode = Node(childmb, parent=node, depth=depth+1,
18                                       bestmoves_by_board=bestmoves_by_board)     
19                      node.insert(childnode)
20                      childnodelist.append(childnode)
21          nodelist = childnodelist
22          depth += 1
23
24  Mbtree.create_subtree = create_subtree
```

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

```python
from marubatsu import Marubatsu

def create_subtree(self):
    bestmoves_by_board = self.subtree["bestmoves_by_board"]
    self.root = Node(Marubatsu(), bestmoves_by_board=bestmoves_by_board)
    
    depth = 0
    nodelist = [self.root]
    centermb = self.subtree["centermb"]
    centerdepth = centermb.move_count
    records = centermb.records
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0:
        childnodelist = []
        for node in nodelist:
            if depth < centerdepth - 1:
                childmb = deepcopy(node.mb)
                x, y = records[depth + 1]
                childmb.move(x, y)
                childnode = Node(childmb, parent=node, depth=depth+1, 
                                 bestmoves_by_board=bestmoves_by_board)   
                node.insert(childnode)
                childnodelist.append(childnode)
            elif depth < maxdepth:
                node.calc_children(bestmoves_by_board=bestmoves_by_board)                   
                if depth == centerdepth - 1:
                    for move, childnode in node.children_by_move.items():
                        if move == records[depth + 1]:
                            self.centernode = childnode
                            childnodelist.append(self.centernode)
                        else:
                            if childnode.mb.status == Marubatsu.PLAYING:
                                childnode.children.append(None)
                else:
                    childnodelist += node.children
            else:
                if node.mb.status == Marubatsu.PLAYING:
                    childmb = deepcopy(node.mb)
                    board_str = node.mb.board_to_str()               
                    x, y = bestmoves_by_board[board_str][0]
                    childmb.move(x, y)
                    childnode = Node(childmb, parent=node, depth=depth+1, 
                                     bestmoves_by_board=bestmoves_by_board)   
                    node.insert(childnode)
                    childnodelist.append(childnode)
        nodelist = childnodelist
        depth += 1

Mbtree.create_subtree = create_subtree
```
</details>

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

```diff_python
from marubatsu import Marubatsu

def create_subtree(self):
+   bestmoves_by_board = self.subtree["bestmoves_by_board"]
-   self.root = Node(Marubatsu())
+   self.root = Node(Marubatsu(), bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
    maxdepth = self.subtree["maxdepth"]
-   while len(nodelist) > 0 and depth < maxdepth:
+   while len(nodelist) > 0:
元と同じなので省略
-               childnode = Node(childmb, parent=node, depth=depth+1)   
+               childnode = Node(childmb, parent=node, depth=depth+1, 
+                                bestmoves_by_board=bestmoves_by_board)   
元と同じなので省略
-           else:
+           elif depth < maxdepth:
-               node.calc_children()                   
+               node.calc_children(bestmoves_by_board=bestmoves_by_board)                   
元と同じなので省略
+           else:
+               if node.mb.status == Marubatsu.PLAYING:
+                   childmb = deepcopy(node.mb)
+                   board_str = node.mb.board_to_str()               
+                   x, y = bestmoves_by_board[board_str][0]
+                   childmb.move(x, y)
+                   childnode = Node(childmb, parent=node, depth=depth+1,
+                                    bestmoves_by_board=bestmoves_by_board)   
+                   node.insert(childnode)
+                   childnodelist.append(childnode)
        nodelist = childnodelist
        depth += 1

Mbtree.create_subtree = create_subtree
```
</details>

上記の修正後に、下記のプログラムを実行して以下のような部分木を作成して `draw_subtree` で表示しようとすると、実行結果のような __エラーが発生__ します。このエラーの原因について少し考えてみて下さい。なお、深さが 3 以降のノードに最善手を着手し続けた場合の局面を表示するためには `draw_subtree` を呼び出す際に、キーワード引数 __[`show_bestmove=True`](https://qiita.com/ysgeso/items/6d1430a88e251279d77a#%E6%9C%80%E5%96%84%E6%89%8B%E4%BB%A5%E5%A4%96%E3%81%AE%E5%B1%80%E9%9D%A2%E3%82%92%E6%9A%97%E3%81%8F%E8%A1%A8%E7%A4%BA%E3%81%99%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85) を記述する必要がある__ 点に注意して下さい。


* (0, 0)、(1, 0) の順に着手を行った局面を中心とする部分木
* 深さが 3 以降のノードは最善手を着手し続けた場合の局面を表す

```python
from util import load_bestmoves

mb = Marubatsu()
mb.move(0, 0)
mb.move(1, 0)
maxdepth = 3
bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": maxdepth, 
                          "bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth,
                     show_bestmove=True)
```

実行結果

```
略
File c:\Users\ys\ai\marubatsu\121\marubatsu.py:973, in Marubatsu_GUI.draw_board(ax, mb, show_result, score, bc, bw, darkness, dx, dy, lw)
    971 if score is None and mb.status == Marubatsu.PLAYING:
    972     bgcolor = "white"
--> 973 elif score > 0 or mb.status == Marubatsu.CIRCLE:
    974     bgcolor = "lightcyan"
    975 elif score < 0 or mb.status == Marubatsu.CROSS:

TypeError: '>' not supported between instances of 'NoneType' and 'int'
```

:::note
`%%timeit` が先頭に記述されているセルの中で行ったインポートやローカル変数などの名前は、そのセルの中だけでしか利用できません。そのため、先程 `%%timeit` を先頭に記述したセルの中で `load_bestmoves` をインポートしましたが、上記のプログラムで改めて `load_bestmoves` をインポートする必要があります。
:::

### エラーの原因の検証

エラーメッセージから、このエラーは __Marubatsu_GUI__ クラスの __`draw_board`__ メソッドで発生したことがわかります。また、このエラーメッセージは、「> という演算子は `None` 型と整数型（int）の演算をサポートしていない」という意味です。従って、__`score` に `None` が代入__ された状態で __`score > 0` という式を計算しようとした__ ことが原因でエラーが発生した可能性が高いことがわかります。そこで、__`draw_board`__ の仮引数 __`score` に `None` が代入されるか__ どうかを検証することにします。

`draw_board` メソッドは、Node クラスの `draw_node` メソッド内の下記のプログラムで呼び出されます。

```python
1  def draw_node(略):
略
2      Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
3                               score=getattr(self, "score", None), bc=bc, darkness=darkness, lw=lw, dx=dx, dy=y)
略
```

3 行目の キーワード引数 `score` に記述されている `getattr(self, "score", None)` は[以前の記事](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) で説明したように、以下のような処理を行います。

* Node クラスのインスタンスを表す `self` に `score` 属性が __存在する場合は `score` 属性の値を計算__ する
* `score` 属性が __存在しない場合は `None` を計算__ する

__`calc_subtree`__ メソッドで __部分木を作成する際__ に、__ノードの評価値の計算は行っていない__ ので、ノードの __`score` 属性は存在しません__。そのため、上記の 2 行目で `draw_board` を呼び出すと、__仮引数 `score` には確かに `None` が代入される__ ことが確認できました。

 次に、仮引数 __`score` に `None` が代入された場合__ に `draw_board` で行われる処理を検証します。`draw_board` では下記のプログラムによって __`score`__ と __`mb.status`__ の値に応じてゲーム盤の背景色を変更する処理を行っています。
 
```python
 1  def draw_board(略)
略
 2          # 結果によってゲーム盤の背景色を変更する
 3          if show_result:
 4              if score is None and mb.status == Marubatsu.PLAYING:
 5                  bgcolor = "white"
 6              elif score > 0 or mb.status == Marubatsu.CIRCLE:
 7                  bgcolor = "lightcyan"
 8              elif score < 0 or mb.status == Marubatsu.CROSS:
 9                  bgcolor = "lavenderblush"
10              else:
11                  bgcolor = "lightyellow"
12              rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
13                                      height=mb.BOARD_SIZE, fc=bgcolor)
14              ax.add_patch(rect)
略
```

__`mb.status`__ は、ゲームの状態を表す属性なので、その中には __ゲームの状態を表す 4 種類のデータのいずれかが代入__ されます。下記は、__`score` に `None` が代入__ されている場合に `mb.status` に に代入される可能性がある 4 種類のそれぞれの値に対して 4 行目の条件式を計算したものです。下記の表から、__`score` が `None`__ であり、なおかつ __ゲームの決着がついている場合__ に 4 行目の条件式が `False` になり、その後の 6 行目で `score > 0` が実行されて __エラーが発生する__ ことが確認できました。

| `score` |`mb.status`  | 条件式の値 |
|:-:|:-:|:-:|
| `None`  | `Marubatsu.PLAYING`  | `True`  |
| `None`  | `Marubatsu.CIRCLE`  | `False`  |
| `None`  | `Marubatsu.DRAW`  | `False`  |
| `None`  | `Marubatsu.CROSS`  | `False`  |

このバグは、`score` に `None` が代入されている場合の処理を筆者が __間違って記述してしまった__ ことが原因です。

### 潜在的なバグ

__`draw_board`__ メソッドにこのような __バグが存在するにも関わらず__、このバグが __これまで発生しなかった理由__ は、これまでの記事ではノードの __`score` 属性に評価値を計算済の状態__ で `draw_board` を呼び出していたからです。

このような、バグが存在するにも関わらず、そのバグが発生する条件が満たされないという理由で __見つかっていないようなバグ__ を __潜在的なバグ__ と呼び、これまでの記事でも後から発見された潜在的なバグは数多くありました。

:::note
厳密に言えば見つかってないバグはすべて潜在的なバグですが、すぐに発見できるような単純なバグのことは潜在的なバグとは呼ばないのではないかと思います。
:::

潜在的なバグは、__プログラムの機能を修正した際に良く発生します__。また、潜在的なバグは __長い間発見されない__ ことが多く、今回の記事のように、それまでとは異なる方法でプログラムを実行した際に発覚することが良くあります。

そのため、プログラムの機能を修正した際には、__潜在的なバグが新しく発生していないかどうかを確認する__ ことが重要になります。本記事でも最初の頃はプログラムの修正を行うたびにそのような確認を良く行っていました。特に〇×ゲームの判定を行う `judge` 関数を実装する際には、かなり念入りに __[関数のテスト](https://qiita.com/ysgeso/items/ea147c436e357281f441)__ を行いました。

ただし、最近の記事では以前よりもその確認作業が減っています。その理由は、__プログラムの規模が大きくなる__ とすべての場合で処理が正しく行われるかを __確認することが現実的に困難になる__ からです。そのため、このバグのように潜在的なバグの発生に気づかずに、後になってバグの存在に気が付くことがよくあります。実際に、今回の記事で紹介する潜在的なバグは、潜在的なバグを紹介するために意図的に記述したものではありません。いずれも筆者の不注意で発生したもので、今回の記事を執筆するまでは筆者はその存在に気づいていませんでした。

なお、どれだけ頑張ってテストを行っても __潜在的なバグの発生を 0 にすることはほぼ不可能__ です。__潜在的なバグが存在する可能性が常にある__ ことを忘れないようにして下さい。


:::note
企業などで作成する大規模なプログラムでは、あらかじめ厳密な仕様を作成してからプログラミングを行うため、プログラムを修正するたびに、修正したプログラムが仕様通りに動作するかの厳密なテストを行うのが一般的です。それに対して、〇×ゲームのような個人で作成する、その場の思い付きで仕様をどんどん変えていくような小規模なプログラムでは、厳密な確認を行ってもすぐに仕様が変わる可能性が高いので、確認作業を簡易的に済ませることが多いと思います。
:::

### バグの修正方法

このバグの原因は、__`score` に `None` が代入されている場合に `score > 0` という演算を行っている__ ことなので、下記のプログラムのように、__and 演算子__ を使って __`score` に `None` が代入されていない場合のみ__ `score > 0` の演算を行うようにすることでバグを修正することができます。

* __10、12 行目__：`score > 0` や `score < 0` の前に、`score` が `None` でないという条件を加える。and 演算子のほうが or 演算子よりも [優先順位](https://qiita.com/ysgeso/items/1fdd19037bbf64082a42#%E8%AB%96%E7%90%86%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E5%84%AA%E5%85%88%E9%A0%86%E4%BD%8D) が高いので、 () を記述する必要はないが、わかりづらいので記述した。同様に、is not 演算子のほうが and 演算子よりも優先順位が高いことがわかりづらいと感じた場合は条件式の前半部分を `((score is not None) and score > 0)` のように記述すると良い

```python
 1  from marubatsu import Marubatsu_GUI
 2  import matplotlib.patches as patches
 3
 4  def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
 5      # 結果によってゲーム盤の背景色を変更する
 6      if show_result:
 7          if score is None:
 8              if score is None and mb.status == Marubatsu.PLAYING:
 9                  bgcolor = "white"
10          elif (score is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
11              bgcolor = "lightcyan"
12          elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
13              bgcolor = "lavenderblush"
14          else:
15              bgcolor = "lightyellow"          
元と同じなので省略
16
17  Marubatsu_GUI.draw_board = draw_board
```

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

```python
from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches

def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
        elif (score is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
        elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"      
            
        rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, fc=bgcolor)
        ax.add_patch(rect)

    # ゲーム盤の枠を描画する
    for i in range(1, mb.BOARD_SIZE):
        ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k", lw=lw) # 横方向の枠線
        ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k", lw=lw) # 縦方向の枠線

    # ゲーム盤のマークを描画する
    for y in range(mb.BOARD_SIZE):
        for x in range(mb.BOARD_SIZE):
            color = "red" if (x, y) == mb.last_move else "black"
            Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)

    # darkness 0 より大きい場合は、半透明の黒い正方形を描画して暗くする
    if darkness > 0:
        ax.add_artist(patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                        height=mb.BOARD_SIZE, fc="black", alpha=darkness))

    # bc が None でない場合はその色で bw の太さで外枠を描画する
    if bc is not None:
        frame = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, ec=bc, fill=False, lw=bw)
        ax.add_patch(frame)

Marubatsu_GUI.draw_board = draw_board
```
</details>

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

```diff_python
from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches

def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
-       elif score > 0 or mb.status == Marubatsu.CIRCLE:
+       elif (score is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
-       elif score < 0 or mb.status == Marubatsu.CROSS:
+       elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"     
元と同じなので省略

Marubatsu_GUI.draw_board = draw_board
```
</details>

:::note
忘れている方がいるかもしれないので補足しますが、[以前の記事](https://qiita.com/ysgeso/items/1fdd19037bbf64082a42#and-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%A8-or-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E7%9F%AD%E7%B5%A1%E8%A9%95%E4%BE%A1)で説明した __短絡評価__ が行われるため、`score is not None and score > 0` という式は、`score` が `None` の場合は and の後ろの `score > 0` という式は実行されません。

また、`score > 0 and score is not None` のように、and の前後の式を入れ替えると、`score > 0` が必ず実行されるようになるので `score` が `None` の場合はエラーが発生してしまう点に注意して下さい。
:::

上記の修正後に下記のプログラムを実行すると、実行結果のように中心となるノードの子ノードの右に __子ノードが存在することを表す線が表示__ されるようになります。また、それぞれのノードに最善手を表すデータが記録されるようになったので、__最善手を着手していないノードが灰色で表示__ されるようになりますが、__最善手を着手し続けた局面のノードが表示されない__ という問題が発生しています。その理由について少し考えてみて下さい。

```python
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": maxdepth, 
                          "bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth,
                     show_bestmove=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4be917f5-aec3-f3de-1175-04a1f8881165.png" width="200">

## 最善手を着手し続けた局面が表示されない原因の検証

上記で表示された部分木をよく見ると、__画像の横幅が狭い__ ことが確認できるので、原因としては __Figure の横幅が狭い__ ため、__表示されるはずのノードが表示されていない__ 可能性が高いことがわかります。そこで、__`draw_subtree`__ メソッドの中で __Figure がどのように作成されるか__ を確認することにします。

下記は、`draw_subtree` メソッドで Figure を作成する処理を行うプログラムです。

```python
1  def draw_subtree(self, 略, ax=None, 略):
略
2          width = 5 * (maxdepth + 1)
略
3          if ax is None:
4              fig, ax = plt.subplots(figsize=(width * size, height * size))
5              ax.set_xlim(0, width)
6              ax.set_ylim(0, height)   
7              ax.invert_yaxis()
8              ax.axis("off")   
略
```

上記のプログラムから、`draw_subtree` では __Figure__ と __Axes__ に対して以下のような処理が行われることがわかります。

* __仮引数 `ax` に `None` が代入されている場合__ は以下の処理を行う
    * 2 行目で __`width`__ に仮引数 __`maxdepth + 1` に比例した値を計算__ する
    * 4 行目で `width` に比例したサイズの Figure を作成する
    * 5 行目で Axes の __x 軸方向の表示範囲__ を __深さが `maxdepth` までのノードを表示__ するように設定する
* __`ax` が `None` でない場合__ は `draw_subtree` では __Figure を作成せず__、__別の所で作成された__ Figure の Axes が代入された __仮引数 `ax` に対して描画を行う__


先程のプログラムでは、`draw_subtree` を呼び出す際に __キーワード引数 `ax` を記述していない__ ので、`maxdepth + 1` に比例するサイズの Figure が作成され、Axes の表示範囲として __深さが `maxdepth` までのノードを表示する Axes が作成される__ ことになります。そのため、__最善手を着手し続けた場合の局面__ を表す __`maxdepth` よりも深いノードは表示されません__。これがバグの原因です。

### バグの修正方法

__`show_bestmove` に `True` が代入されている場合__ は、__最大で__ 〇×ゲームの __ゲーム木の深さの最大値である 9 までの深さの部分木が作成__ される可能性があります。そのため、その場合は下記のプログラムのように、__`width`__ に `maxdepth + 1` ではなく、__`9 + 1 = 10`__ に比例する値を計算する必要があります。なお、最善手を着手し続けた場合のノードを表示しても Figure の高さは変わらないので `height` に代入する値は変更する必要はありません。

```python
 1  import matplotlib.pyplot as plt
 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      if show_bestmove:
 6          width = 5 * 10
 7      else:
 8          width = 5 * (maxdepth + 1)
 9      height = centernode.height 
元と同じなので省略
10    
11  Mbtree.draw_subtree = draw_subtree
```

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

```python
import matplotlib.pyplot as plt

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
            elif node.mb.last_move in node.parent.bestmoves:
                return 0
            else:
                return 0.2
            
        if anim_frame is None:
            return 0
        index = node.score_index if isscore else node.id
        return 0.5 if index > anim_frame else 0
    
    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 * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")        
    
    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 = 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
                        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 = 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 = 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 = 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.pyplot as plt

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):
元と同じなので省略                    
-   width = 5 * (maxdepth + 1)
+   if show_bestmove:
+       width = 5 * 10
+   else:
+       width = 5 * (maxdepth + 1)
    height = centernode.height 
元と同じなので省略
    
Mbtree.draw_subtree = draw_subtree
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように最善手を着手し続けた局面のノードが正しく表示されるようになったことが確認できます。なお、ノードの __評価値は計算されていない__ ので、__決着がついたノードのみ色が表示__ されます。

```python
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": maxdepth, 
                          "bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth,
                     show_bestmove=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f1ba0942-7e0f-722b-2c07-ee27a5655b11.png" width="450">

### バグが発生した原因

このバグは先ほど説明した潜在的なバグで、`draw_subtree` に仮引数 __`show_bestmove` を追加した際に上記の修正を行うのを忘れてしまったこと__ が原因で発生しました。また、このバグがこれまで生じなかった原因は、__Marubatsu_GUI__ クラスの __`update_gui`__ メソッドから __`draw_subtree`__ を呼び出す際は、先に __深さが 9 までのゲーム木を表示できるように Figure と Axes を作成__ した後で、下記のプログラムの 4 行目のように __キーワード引数 `ax=ax` を記述__ して呼び出しているからです。

```python
1  def update_gui(略):
略
2          self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode,
3                                   anim_frame=self.play.value, isscore=self.isscore,
4                                   ax=self.ax, maxdepth=maxdepth)
略
```

# 選択されたノードの計算

`draw_subtree` では、中心となるノードと、赤い枠で表示される __選択されたノード__ を `centernode` と __`selectednode`__ という別々の仮引数に代入します。そのため、__`create_subtree` で作成した部分木を `draw_subtree` で表示__ する際には、中心となるノードと __選択されたノード__ を作成した __部分木から探す必要__ があります。

この問題に対処するために、[前回の記事](https://qiita.com/ysgeso/items/900d36483538c2745d9a#draw_subtree-%E3%81%AE%E4%BF%AE%E6%AD%A3)では __`create_subtree` の処理の中__ で、__中心となるノードを `centernode` という属性に代入__ するという工夫を行いましたので、__選択されたノード__ に対しても同様に __`selectednode` という属性に代入__ することにします。

__選択されたノードの指定__ は、[前回の記事](https://qiita.com/ysgeso/items/900d36483538c2745d9a#%E4%B8%AD%E5%BF%83%E3%81%A8%E3%81%AA%E3%82%8B%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%8C%87%E5%AE%9A)の中心となるノードの指定と同様に、__その局面のデータ__ を、仮引数 `subtree` に代入する dict の __`selectedmb` というキーの値に代入__ することにします。選択されたノードは、部分木を作成した後で __ルートノードから__ 選択されたノードの局面の __棋譜に従って子ノードを辿る__ ことで探すことができます。

下記はそのように `create_subtree` を修正したプログラムです。なお、この処理は部分木の作成の処理がすべて終わった後で行っています。

* __2 行目__：選択されたノードを表す局面を `selectedmb` に代入する
* __3 行目__：選択されたノードを代入する `selectednode` 属性を、作成した部分木のルートノードで初期化する
* __4、5 行目__：選択されたノードの局面の棋譜を表す `records` 属性から着手を順番に取り出して、その着手を行った子ノードで `selectednode` 属性を更新する処理を行う

```python
1  def create_subtree(self):
元と同じなので省略
2      selectedmb = self.subtree["selectedmb"]
3      self.selectednode = self.root
4      for move in selectedmb.records[1:]:
5          self.selectednode = self.selectednode.children_by_move[move]
6
7  Mbtree.create_subtree = create_subtree
```

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

```python
def create_subtree(self):
    bestmoves_by_board = self.subtree["bestmoves_by_board"]
    self.root = Node(Marubatsu(), bestmoves_by_board=bestmoves_by_board)
    
    depth = 0
    nodelist = [self.root]
    centermb = self.subtree["centermb"]
    centerdepth = centermb.move_count
    records = centermb.records
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0:
        childnodelist = []
        for node in nodelist:
            if depth < centerdepth - 1:
                childmb = deepcopy(node.mb)
                x, y = records[depth + 1]
                childmb.move(x, y)
                childnode = Node(childmb, parent=node, depth=depth+1, 
                                 bestmoves_by_board=bestmoves_by_board)   
                node.insert(childnode)
                childnodelist.append(childnode)
            elif depth < maxdepth:
                node.calc_children(bestmoves_by_board=bestmoves_by_board)                   
                if depth == centerdepth - 1:
                    for move, childnode in node.children_by_move.items():
                        if move == records[depth + 1]:
                            self.centernode = childnode
                            childnodelist.append(self.centernode)
                        else:
                            if childnode.mb.status == Marubatsu.PLAYING:
                                childnode.children.append(None)
                else:
                    childnodelist += node.children
            else:
                if node.mb.status == Marubatsu.PLAYING:
                    childmb = deepcopy(node.mb)
                    board_str = node.mb.board_to_str()               
                    x, y = bestmoves_by_board[board_str][0]
                    childmb.move(x, y)
                    childnode = Node(childmb, parent=node, depth=depth+1, 
                                     bestmoves_by_board=bestmoves_by_board)   
                    node.insert(childnode)
                    childnodelist.append(childnode)
        nodelist = childnodelist
        depth += 1
        
    selectedmb = self.subtree["selectedmb"]
    self.selectednode = self.root
    for move in selectedmb.records[1:]:
        self.selectednode = self.selectednode.children_by_move[move]

Mbtree.create_subtree = create_subtree
```
</details>

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

```diff_python
def create_subtree(self):
元と同じなので省略
+   selectedmb = self.subtree["selectedmb"]
+   self.selectednode = self.root
+   for move in selectedmb.records[1:]:
+       self.selectednode = self.selectednode.children_by_move[move]

Mbtree.create_subtree = create_subtree
```
</details>

上記の修正後に下記のプログラムで以下のような部分木を表示するプログラムを実行すると、実行結果のように最善手を着手し続けた局面のノードが表示されるようになりますが、__選択されたノードの子孫ノードがすべて赤い枠で表示される__ という問題が発生します。この問題の理由について少し考えてみて下さい。

* 中心となるノードは先ほどと同様に (0, 0) と (1, 0) に着手を行った局面のノード
* 選択されたノードは、さらに (2, 0) に着手を行った局面のノード
* それ以外は先ほどと同様の部分木を表示する

```python
mb2 = Marubatsu()
mb2.move(0, 0)
mb2.move(1, 0)
mb2.move(2, 0)
subtree = Mbtree(subtree={"centermb": mb, "selectedmb": mb2, "maxdepth": maxdepth, 
                          "bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
selectednode = subtree.selectednode
subtree.draw_subtree(centernode=centernode, selectednode=selectednode, maxdepth=maxdepth,
                     show_bestmove=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/64080a9d-cf49-c3bb-07e3-448f73e880d4.png" width="450">

## 問題の考察と修正

部分木を作成する際に、__選択された局面のデータ__ は下記のプログラムのように __1 つしか記述していない__ ので、__複数のノードが赤い枠で描画される原因__ は、最善手を着手し続けた局面の __ノードを描画するプログラムのほうにある__ 可能性が高そうです。

```python
subtree = Mbtree(subtree={"centermb": mb, "selectedmb": mb2, "maxdepth": maxdepth, 
                          "bestmoves_by_board": bestmoves_by_board})
```                          

下記は、`draw_subtree` の中で、__最善手を着手し続けた局面のノードを描画__ する処理を行う __付近のプログラム__ です。

```python
 1  def draw_subtree(略)
略
 2          emphasize = node is selectednode
 3          darkness = calc_darkness(node)
 4          rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, darkness=darkness,
 5                                show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
 6          self.nodes_by_rect[rect] = node
 7          if show_bestmove and depth == maxdepth:
 8              bestnode = node
 9              while len(bestnode.bestmoves) > 0:
10                  bestmove = bestnode.bestmoves[0]
11                  bestnode = bestnode.children_by_move[bestmove]
12                  dx = 5 * bestnode.depth
13                  bestnode.height = 4
14                  rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth,
15                                            emphasize=emphasize, show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
略
```

2 ~ 4 行目では、__`node` に代入されたノードを描画__ する処理を下記の手順で行います。

* __2 行目__：`node` に代入されたノードが選択されたノードであるかを計算して `emphasize` というローカル変数にその結果を代入する
* __4 行目__：キーワード引数 `emphasize=emphasize` を記述して `draw_node` を呼び出すことで、`node` が選択されたノードである場合に赤い枠のノードを描画する

その次の 7 ~ 15 行目では、`node` の深さが `maxdepth` の場合に、最善手を着手し続けた場合の子ノードを描画する処理を行っていますが、その際に __ノードを描画する処理__ を行う 14、15 行目では、__キーワード引数 `emphasize=emphasize` を記述して `draw_node` を呼び出しています__。

__2 行目以降の処理__ でローカル変数 __`emphasize` に対する代入処理は行われない__ ので、__14 行目__ で `draw_node` を呼び出した際の __`empasize` の値__ は、__2 行目__ で `emphasize` に代入した値と __同じ値が代入されたまま__ になっています。そのため、14 行目で描画される `node` の子孫ノードの枠は、4 行目で描画される `node` の枠と同じものが表示されることになります。これが、先程の実行結果のように、選択されたノードの子孫ノードがすべて赤枠で描画されてしまう理由です。

### `draw_subtree` の修正

従って、このバグは下記のプログラムの 10 行目のように、最善手を着手し続けた場合の子ノードを描画する直前で、その __子ノードが選択されたノードであるかを計算し直す__ ようにすることで修正することができます。

```python
 1  def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
 2                   isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
 3                  if show_bestmove and depth == maxdepth:
 4                      bestnode = node
 5                      while len(bestnode.bestmoves) > 0:
 6                          bestmove = bestnode.bestmoves[0]
 7                          bestnode = bestnode.children_by_move[bestmove]
 8                          dx = 5 * bestnode.depth
 9                          bestnode.height = 4
10                          emphasize = bestnode is selectednode
11                          rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth, emphasize=emphasize,
12                                                    show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
13                        self.nodes_by_rect[rect] = bestnode
元と同じなので省略
14            
15  Mbtree.draw_subtree = draw_subtree
```

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

```python
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
            elif node.mb.last_move in node.parent.bestmoves:
                return 0
            else:
                return 0.2
            
        if anim_frame is None:
            return 0
        index = node.score_index if isscore else node.id
        return 0.5 if index > anim_frame else 0
    
    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 * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")        
    
    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 = 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 = 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 = 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 = 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
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):
元と同じなので省略
                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                           元と同じなので省略
            
Mbtree.draw_subtree = draw_subtree
```
</details>

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

```python
subtree = Mbtree(subtree={"centermb": mb, "selectedmb": mb2, "maxdepth": maxdepth, 
                          "bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
selectednode = subtree.selectednode
subtree.draw_subtree(centernode=centernode, selectednode=selectednode, maxdepth=maxdepth,
                     show_bestmove=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f83a004e-3d76-bb73-035b-49278c9d9d01.png" width="450">

### バグが発生した原因

このバグもは先ほど説明した潜在的なバグで、`draw_subtree` を最善手を着手し続けた局面のノードを表示するように修正した際に、上記の修正を行うのを忘れてしまったことが原因で発生しました。このバグがこれまで生じなかった原因を下記に記しますが、少々ややこしいの意味がわからない人は無視しても構いません。

このバグは、下記の __修正前__ のプログラムの __14 行目が実行された際に発生するバグです__。

```python
 1  def draw_subtree(略)
略
 2          emphasize = node is selectednode
 3          darkness = calc_darkness(node)
 4          rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, darkness=darkness,
 5                                show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
 6          self.nodes_by_rect[rect] = node
 7          if show_bestmove and depth == maxdepth:
 8              bestnode = node
 9              while len(bestnode.bestmoves) > 0:
10                  bestmove = bestnode.bestmoves[0]
11                  bestnode = bestnode.children_by_move[bestmove]
12                  dx = 5 * bestnode.depth
13                  bestnode.height = 4
14                  rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth,
15                                            emphasize=emphasize, show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
略
```

14 行目の処理は、下記の条件を __すべて満たす場合でのみ__ 行われます。先ほどの例では、__`node` が選択されたノードの場合__ は、__この条件をすべて満たす__ のでバグが発生しました。

* `node` が選択されたノードである
* `node` の深さが `maxdepth` である
* `node` に子ノードが存在する

一方、__Marubatsu_GUI クラスで部分木を表示__ する際には、__`update_gui`__ メソッドの下記のプログラムで、選択されたノードから __`maxdepth` が計算__ されます。下記のプログラムでは、選択されたノードの深さが、__子ノードが存在しない深さが 9 でない場合__ は、__必ず `maxdepth` の深さが選択されたノードよりも深くなります__。そのため、__`node` が選択されたノードの場合__ に上記の条件を __すべて満たすことはない__ ので、このバグは発生しません。

```python
def update_gui(略):
略
        if self.selectednode.depth <= 4:
            maxdepth = self.selectednode.depth + 1
        elif self.selectednode.depth == 5:
            maxdepth = 7
        else:
            maxdepth = 9
略
```
# `draw_subtree` の計算時間

下記のプログラムで `draw_subtree` の処理時間を計測した所、実行結果のように平均で __約 2.5 ミリ秒__ であることがわかりましたので、今回の記事の最初で見積もったように、__部分木を動的に作成する処理にはほとんど時間がかからない__ ことが確認できました。

```python
%%timeit
Mbtree(subtree={"centermb": mb, "selectedmb": mb2, "maxdepth": maxdepth, 
                "bestmoves_by_board": bestmoves_by_board})
```

実行結果

```
2.51 ms ± 84.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
```

今回の記事はここまでにします。評価値をゲーム盤の上に表示する処理がまだ残っていますが、その処理は次回の記事で実装することにします。また、次回の記事では Mbtree_GUI クラスで `create_subtree` を利用して部分木を表示する処理を実装します。

# 今回の記事のまとめ

今回の記事では、最善手を着手し続けた場合のノードを作成するように `create_subtree` を修正しました。また、潜在的なバグをいくつか紹介し、その性質と修正方法について説明しました。

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

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

# 次回の記事

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