Pythonで〇×ゲームのAIを一から作成する　その90　幅優先アルゴリズムによる任意の深さのゲーム木の作成と部分木の視覚化

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5

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

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

https://github.com/ysgeso/marubatsu/blob/master/090/marubatsu.py

https://github.com/ysgeso/marubatsu/blob/master/090/ai.py

https://github.com/ysgeso/marubatsu/blob/master/090/util.py

https://github.com/ysgeso/marubatsu/blob/master/090/tree.py

## ルールベースの AI の一覧

ルールベースの AI の一覧については、下記の記事を参照して下さい。

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

# 幅優先アルゴリズムによる任意の深さのゲーム木の作成

前回の記事では、下記の、__幅優先アルゴリズム__ による、深さ 2 までのゲーム木の作成と視覚化を行いましたが、その際に記述した手法でを深さ 3 以上のゲーム木を作成すると、[プログラムの記述が大変である](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E6%B7%B1%E3%81%95-3-%E4%BB%A5%E4%B8%8A%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E4%BD%9C%E6%88%90%E3%81%A8%E5%95%8F%E9%A1%8C%E7%82%B9)という問題があることを示しました。

1. __ゲーム開始時の局面__ を表すノードを __ルートノード__ とする __ゲーム木を作成__ する
2. 子ノードを作成する処理を行う __ノードの深さ d__ を __0 に設定__ する
3. 深さ d のノードが存在しない場合は、ゲーム木が完成しているので処理を終了する
4. 深さ d のノードが存在する場合は、それらの __全てのノードに対して子ノードを作成__ する
5. __深さ d に 1 を足して__ 手順 3 に戻る 

下記は、[前回の記事の最後](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E6%B7%B1%E3%81%95-3-%E4%BB%A5%E4%B8%8A%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E4%BD%9C%E6%88%90%E3%81%A8%E5%95%8F%E9%A1%8C%E7%82%B9)で記述した、深さ 4 のゲーム木を作成するプログラムです。このプログラムの問題点は、深さ d のノードを作成する際に、__for 文を深さの分だけ入れ子にして記述する必要がある__ というものです。

```python
def create_tree_by_bf(self):
    # 深さ 1 のノードの作成
    self.root.calc_children()
    # 深さ 2 のノードの作成
    for childnode in self.root.children:
        childnode.calc_children()
        # 深さ 3 のノードの作成
        for grandchildnode in childnode.children:
            grandchildnode.calc_children()
            # 深さ 4 のノードの作成
            for greatgrandchildnode in grandchildnode.children:
                greatgrandchildnode.calc_children()
```

実は、上記のプログラムでは、深さ 2 のノードを __すべて作成する前__ に、深さ 3 のノードを __作成しはじめている__ ので、上記の __幅優先アルゴリズムの手順でゲーム木を作成していません__。上記のプログラムが行う処理は、今後の記事で説明する深さ優先アルゴリズムと幅優先アルゴリズムを組み合わせたものです。

なお、深さ 2 までのゲーム木を作成する下記のプログラムでは、深さ 1 のノードをすべて作成してから深さ 2 のノードを作成するので、幅優先アルゴリズムのみが使われています。

```python
def create_tree_by_bf(self):
    # 深さ 1 のノードの作成
    self.root.calc_children()
    # 深さ 2 のノードの作成
    for childnode in self.root.children:
        childnode.calc_children()
```        

## 子ノードの一覧の記録

幅優先アルゴリズムで、深さ 3 以上のゲーム木を作成するためには、子ノードを作成する際に、__作成した子ノードの一覧を list などで記録しておく__ 必要があります。具体的には、下記のアルゴリズムの手順 4 で、作成した深さ d + 1 の子ノードの一覧を記録しておくことで、手順 3 に戻った時に、__記録しておいた子ノードの一覧を、次の深さのノードの一覧として利用__ することができます。

1. __ゲーム開始時の局面__ を表すノードを __ルートノード__ とする __ゲーム木を作成__ する
2. 子ノードを作成する処理を行う __ノードの深さ d__ を __0 に設定__ する
3. 深さ d のノードが存在しない場合は、ゲーム木が完成しているので処理を終了する
4. 深さ d のノードが存在する場合は、それらの __全てのノードに対して子ノードを作成__ する
5. __深さ d に 1 を足して__ 手順 3 に戻る 

具体的には、下記のプログラムのように `create_tree_by_bf` を修正します。なお、修正の際に、`create_tree_by_bf` に下記のような工夫を行いました。また、`create_tree_by_bf` は全面的に内容が変化したので、修正箇所は省略します。

* __それぞれの深さ__ の __ノードの一覧の情報__ は、この後でノードの描画や、ノードを描画した際の高さを計算する際に必要となるので、__`nodelist_by_depth`__ という属性に、list の形式で記録する。`nodelist_by_depth` には、深さ 0 のノードの一覧から順番に要素を追加するので、__インデックスの番号がノードのリストの深さに等しくなる__
* __ゲーム木を作成__ する処理には __時間がかかる__ ので、__途中経過の報告__ として、各深さのノードの作成が完了した時点で、作成した __その深さのノードの数を表示__ する
* 作成した __ノードの総数を計算__ して __`nodenum`__ 属性に代入し、その __数を表示する__

下記は、プログラムの説明です。

* それぞれの __ローカル変数__ は以下の意味を持つ
    * __`nodelist`__：手順 4 で子ノードを作成する、__深さ `depth` のノードの一覧__
    * __`depth`__：`nodelist` に記録された __ノードの深さ__
    * __`childlist`__：手順 4 で作成した、__深さ `depth` + 1 のノードの一覧__
* __5、6 行目__：`nodelist` を、深さ 0 のノードの一覧を表す list で初期化し、`nodelist` の深さを表す `depth` を `0` で初期化する
* __11 行目__：`nodelist` の中身が空になるまで繰り返し処理を行う（手順 3）
* __12 行目__：手順 4 で作成する子ノードの一覧を記録する `childnodelist` を空の list で初期化する
* __13 ~ 15 行目__：`nodelist` のそれぞれの子ノードに対して、14 行目で子ノードを作成する処理を行い、15 行目で `childnodelist` に、作成された子ノードの list を `+=` 演算子で[拡張](https://qiita.com/ysgeso/items/59e51d983a32ac4bc5db#-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AB%E3%82%88%E3%82%8B-list-%E3%81%AE%E7%B5%90%E5%90%88)する処理を行う
* __16 行目__：深さ `depth` の全てのノードの子ノードを計算する処理が完了したので、`node_list_by_depth` 属性の要素に、作成した子ノードの list を追加する。この処理によって、`depth` + 1 番の要素に深さ `depth` + 1 のノードの list が代入される
* __17、18 行目__：次の繰り返し処理では、`childnodelist` に代入された、`depth` + 1 の深さのノードに対して処理を行うので、`nodelist` に `childnodelist` を代入し、`depth` に 1 を加算する
* __19 行目__：作成した深さ `depth` の子ノードの数を表示する。なお、各深さのノードの数の最大値は 6 桁の数値になるので、[書式指定](https://qiita.com/ysgeso/items/bf42b7b578bc2d5da949#%E6%9B%B8%E5%BC%8F%E6%8C%87%E5%AE%9A)を表す `:>6` を使って、6 桁の数値を右揃えで表示するように工夫した
* __21 ~ 24 行目__：`nodelist_by_depth` 内の要素の数の合計を計算して `nodenum` 属性に代入し、24 行目でゲーム木のノードの総数を表示する

```python
 1  from tree import Mbtree
 2
 3  def create_tree_by_bf(self):
 4      # 深さ 0 のノードを、子ノードを作成するノードのリストに登録する
 5      nodelist = [self.root]
 6      depth = 0
 7      # 各深さのノードのリストを記録する変数を初期化する
 8      self.nodelist_by_depth = [ nodelist ]
 9   
10      # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
11      while len(nodelist) > 0:
12          childnodelist = [] 
13          for node in nodelist:
14              node.calc_children()
15              childnodelist += node.children
16          self.nodelist_by_depth.append(childnodelist)
17          nodelist = childnodelist
18          depth += 1
19          print(f"{len(nodelist):>6} depth {depth} node created")
20        
21      self.nodenum = 0
22      for nodelist in self.node_list_by_depth:
23          self.nodenum += len(nodelist)
24      print(f"total node num = {self.nodenum}")
25
26  Mbtree.create_tree_by_bf = create_tree_by_bf
```

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

```python
from tree import Mbtree

def create_tree_by_bf(self):
    # 深さ 0 のノードを、子ノードを作成するノードのリストに登録する
    nodelist = [self.root]
    depth = 0
    # 各深さのノードのリストを記録する変数を初期化する
    self.nodelist_by_depth = [ nodelist ]
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            node.calc_children()
            childnodelist += node.children
        self.nodelist_by_depth.append(childnodelist)
        nodelist = childnodelist
        depth += 1
        print(f"{len(nodelist):>6} depth {depth} node created")
        
    self.nodenum = 0
    for nodelist in self.nodelist_by_depth:
        self.nodenum += len(nodelist)
    print(f"total node num = {self.nodenum}")

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

上記の修正後に、下記のプログラムを実行すると、実行結果から下記の事がわかります。

* 深さ 9 までのノードが作成された
* 9 手目の局面を表す __深さ 9 のノード__ が __362880 個__ もある
* 〇×ゲームの __局面の総数__ を表す、ゲーム木の __ノードの総数__ が __986410 個__ もある

ノードを作成する際に、`deepcopy` で `Marubatsu` クラスのインスタンスを複製する処理を行うため、この処理は __約 100 万回もの `deepcopy` による複製の処理__ が行われます。そのため、__上記の処理には時間がかかり__、筆者のパソコンでは __約 60 秒__ の時間がかかりました。

```python
mbtree = Mbtree()
```

実行結果

```
     9 depth 1 node created
    72 depth 2 node created
   504 depth 3 node created
  3024 depth 4 node created
 15120 depth 5 node created
 60480 depth 6 node created
181440 depth 7 node created
362880 depth 8 node created
362880 depth 9 node created
     0 depth 10 node created
total node num = 986410
```

なお、着手の順番によって __異なるノードが完全に同じ局面__ になる[^1]場合がありますが、現時点では __それらは別々のノードとして扱う__ ことにします。また、[以前の記事](https://qiita.com/ysgeso/items/e78980b366e123ca57f1#%E5%90%8C%E4%B8%80%E5%B1%80%E9%9D%A2%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8%E6%89%B1%E3%81%84)で説明した __同一局面__ も __考慮に入れません__。従って、ゲーム木には、数多くの完全に同じ局面や、同一局面のノードが存在しますが、最強の AI を作成する際に、処理の効率の面を除けば、そのことは問題にはなりません。同一局面などについては、今後の記事で考慮に入れる予定です。

## 間違った各深さのノードの数の計算方法

実は、〇×ゲームのゲーム木の __ノードの数__ は __約 100 万 ではありません__。その理由は、`create_tree_by_bf` に一つ大きなバグがあるからです。そのバグが何であるかについて少し考えてみて下さい。

まず、各深さのノードの数を計算する __間違った方法の考え方__ について説明します。

〇×ゲームでは、最初は 9 つのマスが開いているので合法手の数は 9 です。従って 1 手目の着手の種類は 9 通りあります。

〇×ゲームは、__着手を行うたびにゲーム盤のマスが 1 つ埋まる__ ので、2 手目を着手する局面の合法手の数は 8 です。従って、2 手目までの着手の組み合わせは 9 * 8 = 72 通りあります。3 手目も同様で、3 手目までの着手の組み合わせは 9 * 8 * 7 = 504 になります。

下記は、1 ~ 9 手目の着手の組み合わせの数の計算式と計算結果を表にしたものです。__計算結果__ と先程の __実行結果__ に表示された数字が __一致する__ ことを確認して下さい。

| 手数 | 着手の組み合わせの数の計算式 | 計算結果 |
|:-:|:--|--:|
| `1`  |  $9$ |  9 |
| `2`  |  $9 × 8$ | 72  |
| `3`  |  $9 × 8 × 7$ | 504  |
| `4`  |  $9 × 8 × 7 × 6$ | 3024  |
| `5`  |  $9 × 8 × 7 × 6 × 5$ | 15120   |
| `6`  |  $9 × 8 × 7 × 6 × 5 × 4$ |  60480 |
| `7`  |  $9 × 8 × 7 × 6 × 5 × 4 × 3$| 181440  |
| `8`  |  $9 × 8 × 7 × 6 × 5 × 4 × 3 × 2$ | 362880  |
| `9`  |  $9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1$ | 362880  |

:::note
9  手目までの着手の組み合わせの式のように、__1 から特定の整数までの数を掛け算する__ という計算を __階乗__ と呼び、数学では $9!$ のように、! の記号を使って表現します。

上記のそれぞれの式は、下記の表の式のように階乗を使って記述することができるので、d 手目までの着手の組み合わせの数は $\frac{9!}{(9-d)!}$ で計算することができます。なお、9 手目の式には __0 の階乗__ を表す $0!$ がありますが、数学では $0! = 1$ と __定義されている__[^2]のでこの式で正しく計算することができます。

| 手数 | 式 | 階乗を使った式|
|:-:|:--|--:|
| `1`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}$  | $ \frac{9!}{8!}$ | 
| `2`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{7 × 6 × 5 × 4 × 3 × 2 × 1}$  | $ \frac{9!}{7!}$ |
| `3`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{6 × 5 × 4 × 3 × 2 × 1}$  | $ \frac{9!}{6!}$ |
| `4`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{5 × 4 × 3 × 2 × 1}$  | $ \frac{9!}{5!}$ |
| `5`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{4 × 3 × 2 × 1}$  | $ \frac{9!}{4!}$ |
| `6`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{3 × 2 × 1}$  | $ \frac{9!}{3!}$ |
| `7`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{2 × 1}$  | $ \frac{9!}{2!}$ |
| `8`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{1}$  | $ \frac{9!}{1!}$ |
| `9`  |  $\frac{9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1}{1}$  | $ \frac{9!}{0!}$ |
:::

## 正しい各深さのノードの数の計算方法

上記の考え方は一見正しいように見えるかもしれませんが、__決着がついた局面__ には __合法手が存在しない__ ことを考慮していない点が間違っています。

従って、`create_tree_by_bf` の問題点は、__ゲームの決着がついていた場合でも子ノードを計算してしまう__ ことなので、下記のプログラムのように修正する必要があります。

* __8 ~ 10 行目__：`node` の局面が決着がついていない場合のみ子ノードを計算するようにする

```python
 1  from marubatsu import Marubatsu
 2
 3  def create_tree_by_bf(self):
元と同じなので省略
 4      # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
 5      while len(nodelist) > 0:
 6          childnodelist = [] 
 7          for node in nodelist:
 8              if node.mb.status == Marubatsu.PLAYING:
 9                  node.calc_children()
10                  childnodelist += node.children
元と同じなので省略
11
12  Mbtree.create_tree_by_bf = create_tree_by_bf
```

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

```python
from marubatsu import Marubatsu

def create_tree_by_bf(self):
    # 深さ 0 のノードを、子ノードを作成するノードのリストに登録する
    nodelist = [self.root]
    depth = 0
    # 各深さのノードのリストを記録する変数を初期化する
    self.nodelist_by_depth = [ nodelist ]
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            if node.mb.status == Marubatsu.PLAYING:
                node.calc_children()
                childnodelist += node.children
        self.nodelist_by_depth.append(childnodelist)
        nodelist = childnodelist
        depth += 1
        print(f"{len(nodelist):>6} depth {depth} node created")
        
    self.nodenum = 0
    for nodelist in self.nodelist_by_depth:
        self.nodenum += len(nodelist)
    print(f"total node num = {self.nodenum}")

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

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

```diff_python
from marubatsu import Marubatsu

def create_tree_by_bf(self):
元と同じなので省略
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
-           node.calc_children()
-           childnodelist += node.children
+           if node.mb.status == Marubatsu.PLAYING:
+               node.calc_children()
+               childnodelist += node.children
元と同じなので省略

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

:::note
上記以外にも、下記のような修正方法があります。

* `calc_children` のほうで、決着がついた局面の場合は、子ノードを計算しないようにする
* 決着がついた局面で、合法手を返さないように `calc_legal_moves` を修正する
:::

上記の修正後に、下記のプログラムを実行すると正しいゲーム木が作成されます。

```python
mbtree = Mbtree()
```

実行結果

```
     9 depth 1 node created
    72 depth 2 node created
   504 depth 3 node created
  3024 depth 4 node created
 15120 depth 5 node created
 54720 depth 6 node created
148176 depth 7 node created
200448 depth 8 node created
127872 depth 9 node created
     0 depth 10 node created
total node num = 549946
```

また、上記の実行結果から下記の事がわかります。

* __深さ 9 のノード__ は、先程の約 1/3 の __127872 個__ である
* ゲーム木の __ノードの総数__ は先ほどの約半数の __549946 個__ である
* 〇×ゲームは、〇 の 3 回目の着手が行われる 5 手目までは決着がつかないので、深さ 5 までのノードの数は先ほどと変わらない

また、ノードの数が約半数に減少したので、筆者のパソコンでは上記の処理は、先程の約半分の約 35 秒かかりました。


# 表示範囲を限定したゲーム木の部分木の視覚化

上記の実行結果からわかるように、〇×ゲームのゲーム木は、__最もノードの数が多い__ 深さが 8 のノードが __20 万以上__ もあります。これまで行ってきたゲーム木の視覚化では、__ゲーム盤__ を __縦方向に y 座標が 4 おきに描画__ していたので、その方法でゲーム盤を描画すると、__縦方向の画像のサイズ__ が 4 * 約 20 万 = __約 100 万という途方もない大きさ__ になるので、__ゲーム木のすべてを描画__ するのは __現実的ではありません__。

:::note
深さ 8 のノードの数が 20 万以上になるということに驚いている人がいるかもしれませんが、〇×ゲームのゲーム木の規模は、オセロや将棋などの、他の多くのゲームのゲーム木と比較すれば、非常に小さいです。

例えば、将棋のゲーム木の場合は、7 手目までの合法手の組み合わせの数を表す、深さ 7 のノードの数は[こちらのページ](https://yaneuraou.yaneu.com/2015/12/12/%E9%80%A3%E8%BC%89%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%A7%E9%81%8A%E3%81%BC%E3%81%86%EF%BC%816%E6%97%A5%E7%9B%AE/)によると 約 150 億もあるようです。また、同一局面のノードを同じノードとみなした場合の将棋のゲーム木のノードの総数は、[こちらの論文](https://www.nara-wu.ac.jp/math/personal/shinoda/legal.pdf)によると $10^{68}$ ~ $10^{69}$ もあるそうです。
:::

__木構造の一部__ のうち、それ自体が __木構造を持つもの__ のことを __部分木__ と呼びます。例えば、下図左の、ルートノードから深さ 1 までのノードとそれらをつなぐエッジを取り出したものは、木構造を持つのでゲーム木の部分木です。下図右の、(1, 1) に着手を行ったノードから、その子ノードとそれらをつなぐエッジを取り出したものも部分木です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/65214029-3bd8-cb9e-f1b9-3d77fbe74113.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/14d84093-754a-554e-7a74-4d0b85b4e903.png" width="100">

部分木は木の一部なので、__ゲーム木の部分木を描画する処理を実装__ する事で、__表示範囲を限定した、現実的な大きさのゲーム木を描画__ することができるようになります。

## ルートノードからの深さを限定した部分木の描画

__ルートノードから、特定の深さまで__ のノードとそれらをつなぐエッジを __取り出したものは部分木になる__ ので、最初にそのような部分木を描画する処理を実装することにします。

最初に、表示する __木の深さ__ を代入する __`maxdepth`__ という仮引数を `draw_tree` に追加することで、特定の深さまでの、ゲーム木の一部だけを描画する処理を実装することにします。

### 特定の深さまでのノードの高さを計算する処理の実装

`draw_tree` で `maxdepth` までの深さのノードを描画するためには、__`maxdepth` までの深さ__ のそれぞれの __ノードの高さを計算する必要__ があります。そこで、ノードの高さを計算する __`calc_node_height`__ の仮引数に、高さを計算するノードの深さの最大値を代入する __`maxdepth` を追加__ して、__指定した深さまでのノードの高さだけを計算__ するように修正します。なお、元の `calc_node_height` から全面的な修正が行われたので修正箇所は省略します。

* __1 行目__：ノードの深さの最大値を代入する仮引数 `maxdepth` を追加する
* __2 行目__：ノードの高さは、[深い順に計算する必要がある](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E6%9C%A8%E3%81%AE%E3%81%9D%E3%82%8C%E3%81%9E%E3%82%8C%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E9%AB%98%E3%81%95%E3%82%92%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85)ので、[`range` の step に -1 を設定する](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#range-%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9)ことで、__`maxdepth` から 0 まで__、深さを __1 ずつ減らしながら__ ノードの高さを計算する。なお、繰り返し処理で `range` から得られる整数は、`range` の __2 つ目の実引数の値は含まない__ ので、`maxdepth` から `0` まで 1 ずつ数値を減らしながら繰り返しを行いたい場合は、__2 つ目の実引数に `-1` を記述する必要がある__ 点に注意する事
* __3 行目__：深さ `depth` のノードの一覧が代入されている `self.node_list_by_depth[depth]` から順番にノードを取り出す繰り返し処理を行う
* __4、5 行目__：__深さが `maxdepth` のノード__ は、その __子ノードを描画しない__ ので、子ノードが存在しているかどうかに関わらず __高さを表す `height` 属性に `4` を代入__ する
* __6、7 行目__：それ以外の場合は、`calc_height` を使ってノードの高さを計算する

```python
1  def calc_node_height(self, maxdepth):
2      for depth in range(maxdepth, -1, -1):
3          for node in self.nodelist_by_depth[depth]:
4              if depth == maxdepth:
5                  node.height = 4
6              else:
7                  node.calc_height()
8
9  Mbtree.calc_node_height = calc_node_height
```

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

```python
def calc_node_height(self, maxdepth):
    for depth in range(maxdepth, -1, -1):
        for node in self.nodelist_by_depth[depth]:
            if depth == maxdepth:
                node.height = 4
            else:
                node.calc_height()

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように、深さ 2 までの各ノードを描画した際の高さが正しく計算されていることが確認できます。

```python
mbtree.calc_node_height(maxdepth=2)
for depth in range(3):
    for node in mbtree.nodelist_by_depth[depth]:
        print(f"depth {depth} height {node.height}")
```

<details><summary><strong>実行結果（長いのでクリックして表示して下さい）</strong></summary>

```
depth 0 height 288
depth 1 height 32
depth 1 height 32
depth 1 height 32
depth 1 height 32
depth 1 height 32
depth 1 height 32
depth 1 height 32
depth 1 height 32
depth 1 height 32
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
depth 2 height 4
```
</details>

下記は、深さ 9 までの、すべてのノードを描画する場合の高さを計算し、ルートノードの高さのみを表示するプログラムです。実行結果から、ゲーム木全体を描画する場合は、高さが 100 万を超えるようなサイズになることが確認できました。

```python
mbtree.calc_node_height(maxdepth=9)
print(mbtree.root.height)
```

実行結果

```
1020672
```

### 特定の深さまでの部分木を描画する処理の実装

次に、下記のプログラムのように、__ルートノードから特定の深さまでの部分木を描画する__ ように `draw_tree` を修正します。なお、深さ 3 以上の部分木を描画すると高さが非常に長くなるので、深さを表す実引数を省略した場合は深さ 2 の部分木を描画するようにしました。

* __3 行目__：描画する部分木の深さの最大値を代入する仮引数 `maxdepth` を、デフォルト値を `2` とするデフォルト引数として追加する
* __4 行目__：`maxdepth` までの深さのノードの高さを計算する
* __5 行目__：ゲーム盤とゲーム盤の横の間隔を 2 としたので、[前回の記事](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E6%B7%B1%E3%81%95-1-%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%8F%8F%E7%94%BB)で説明したように、Figure の横幅は `5 * (maxdepth + 1) - 2`[^3] で計算できる。ただし、式を簡潔にするために、ここでは `5 * (maxdepth + 1)` とした
* __13 行目__：深さ 0 から `maxdepth - 1` まで順にノードを描画する。なお、__深さ `maxdepth` のノード__ は、深さ `maxdepth - 1` のノードを描画する際に、__子ノードとして描画される__ ので `maxdepth - 1` の深さまでの描画を行えば良い
* __14 行目__：ノードを描画する y 座標を表す `dy` を `0` で初期化する
* __15 ~ 17 行目__：深さ `depth` のノードを順番に描画する。深さ `depth` のノードの座標は (5 * depth, dy) である。また、描画を行うたびに `dy` に描画したノードの高さを加算する[^4]

```python
 1  import matplotlib.pyplot as plt
 2
 3  def draw_tree(self, size=0.25, lw=0.8, maxdepth=2):
 4      self.calc_node_height(maxdepth)
 5      width = 5 * (maxdepth + 1)
 6      height = self.root.height
 7      fig, ax = plt.subplots(figsize=(width * size, height * size))
 8      ax.set_xlim(0, width)
 9      ax.set_ylim(0, height)   
10      ax.invert_yaxis()
11      ax.axis("off")        
12    
13      for depth in range(maxdepth):
14          dy = 0
15          for node in self.nodelist_by_depth[depth]:
16              node.draw_node(ax=ax, size=size, lw=lw, dx=depth*5, dy=dy)
17              dy += node.height
18        
19  Mbtree.draw_tree = draw_tree
```

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

```python
import matplotlib.pyplot as plt

def draw_tree(self, size=0.25, lw=0.8, maxdepth=2):
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth + 1)
    height = self.root.height
    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")        
    
    for depth in range(maxdepth):
        dy = 0
        for node in self.nodelist_by_depth[depth]:
            node.draw_node(ax=ax, size=size, lw=lw, dx=depth*5, dy=dy)
            dy += node.height
        
Mbtree.draw_tree = draw_tree
```
</details>

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

```diff_python
import matplotlib.pyplot as plt

-def draw_tree(self, size=0.25, lw=0.8):
+def draw_tree(self, size=0.25, lw=0.8, maxdepth=2):
-   self.calc_node_height()
+   self.calc_node_height(maxdepth)
-   width = 13
+   width = (maxdepth + 1) * 5
    height = self.root.height
    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")        
    
-   # 深さ 0 のノードの描画
-   self.root.draw_node(ax=ax, size=size, lw=lw)
-   dy = 0
-   # 深さ 1 のノードの描画
-   for childnode in self.root.children:
-       childnode.draw_node(ax=ax, size=size, lw=lw, dx=5, dy=dy)
-       dy += childnode.height
+   for depth in range(maxdepth):
+       dy = 0
+       for node in self.nodelist_by_depth[depth]:
+           node.draw_node(ax=ax, size=size, lw=lw, dx=depth*5, dy=dy)
+           dy += node.height
        
Mbtree.draw_tree = draw_tree
```
</details>

### 描画処理の確認

下記のプログラムを実行すると、実行結果のように、深さ 2 までの部分木が描画されます。なお、実行結果は[前回の記事](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E5%95%8F%E9%A1%8C%E3%81%AE%E6%A4%9C%E8%A8%BC%E3%81%A8%E4%BF%AE%E6%AD%A3)で行った描画と同じ内容になります。

```python
mbtree.draw_tree(maxdepth=2)
```

<details><summary><strong>実行結果（長いのでクリックした表示して下さい）</strong></summary>

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/caf00fe0-44ca-6d50-649c-432e7c42c5b1.png" width="150">

</details>

また、下記のプログラムを実行すると、実行結果のように深さ 3 までの部分木を描画することができます。なお、そのままだと画像が大きくなりすぎるので、`size` と `lw` を使ってゲーム盤を小さく描画しました。

```python
mbtree.draw_tree(size=0.1, lw=0.4, maxdepth=3)
```

<details><summary><strong>実行結果（長いのでクリックした表示して下さい）</strong></summary>

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6c252da8-1ce3-45ac-4f71-fb0916bb9bf6.png" width="150">

</details>

:::note
上図で、深さ 1、2 のノードが濃く描画されるのは目の錯覚ではありません。今回の記事の後半で説明しますが、それらのノードは 2 回描画されるため濃くなります。
:::

下記のプログラムで __深さ 4 まで__ の部分木の描画を行おうとすると、実行結果のようなエラーが発生します。これは、__matplotlib__ では、作成できる __画像のピクセルのサイズの最大値が 65536__[^5] で、それを超えるような 120960 ピクセルの高さの画像を作成しようとしたことが原因です。`size` の値をさらに小さくすれば深さ 4 くらいまでであれば描画することは可能ですが、それ以上の深さのゲーム木を描画しようとすると、ゲーム盤が小さすぎて肉眼で確認できなくなる点と、処理に非常に長い時間がかかるという問題が発生します。

```python
mbtree.draw_tree(size=0.1, lw=0.4, maxdepth=4)
```

実行結果

```
略
     68 self.width = width
     69 self.height = height
---> 70 self._renderer = _RendererAgg(int(width), int(height), dpi)
     71 self._filter_renderers = []
     73 self._update_methods()

ValueError: Image size of 250x120960 pixels is too large. It must be less than 2^16 in each direction.
```

## 特定のノードから特定の深さまでの部分木の描画

上記のように、ルートノードから深いノードまでの部分木を描画しようとすると、画像が大きくなりすぎて表示が困難になるという問題があるため、このままではゲーム木の __深いノードを描画することは困難__ です。そこで、ゲーム木の __特定のノードから、特定の深さまで__ の部分木を描画するように `draw_tree` を修正することにします。

そのために `draw_tree` に、描画を開始（start）する __部分木のルートノード__ を代入する __`startnode`__ という属性を追加します。ただし、`startnode` に対応する実引数を省略した場合は、ルートノードから描画されるようにするようにします。

下記は、修正前の `draw_tree` のプログラムです。このプログラムに修正を加えていきます。

```python
def draw_tree(self, size=0.25, lw=0.8, maxdepth=2):
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth + 1)
    height = self.root.height
    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")        
    
    for depth in range(maxdepth):
        dy = 0
        for node in self.nodelist_by_depth[depth]:
            node.draw_node(ax=ax, size=size, lw=lw, dx=depth*5, dy=dy)
            dy += node.height
```            

### 描画を開始する部分木のルートノードを代入する仮引数の追加

まず、下記のプログラムのように、描画を開始する部分木のルートノードを代入する仮引数 `startnode` に関する処理を追加します。

* __1 行目__：デフォルト値を `None` とする仮引数 `startnode` を追加する
* __2、3 行目__：`startnode` が `None` の場合に、`startnode` にルートノードを代入する

```python
1  def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
2      if startnode is None:
3          startnode = self.root
元と同じなので省略
4        
5  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth + 1)
    height = self.root.height
    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")        
    
    for depth in range(maxdepth):
        dy = 0
        for node in self.nodelist_by_depth[depth]:
            node.draw_node(ax=ax, size=size, lw=lw, dx=depth*5, dy=dy)
            dy += node.height
        
Mbtree.draw_tree = draw_tree
```
</details>

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

```diff_python
-def draw_tree(self, size=0.25, lw=0.8, maxdepth=2):
+def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
+   if startnode is None:
+       startnode = self.root
元と同じなので省略
        
Mbtree.draw_tree = draw_tree
```
</details>


### 描画するノードの高さの計算

`startnode` から、深さ `maxdepth` までの部分木を描画する際には、これまでと同様に、__描画するノードの高さを計算__ する必要がありますが、その高さを計算する __`self.calc_node_height(maxdepth)` を修正する必要はありません__。

例えば深さ 1 の、(0, 0) に 〇 が配置されたノードから、深さ 2 までのノードの部分木を描画する場合のことを考えてみて下さい。そのような部分木は、下図のルートノードから深さ 2 までのノードを描画した場合の画像の中の、赤枠で囲った部分と同じになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a07bc4c8-0be5-ed47-3fd0-aa563cb22fc9.png" width="100">

別の言葉で説明すると、`startnode` から深さ `maxdepth` までのノードまでの部分木は、上図の赤い枠の部分のように、ルートノードから深さ `maxdepth` までのノードの部分木に __必ず含まれ、同じ大きさで描画する__ ので、`self.calc_node_height(maxdepth)` によって、`startnode` から深さ `maxdepth` までのノードの高さを __すべて計算することができます__。

:::note
`self.calc_node_height(maxdepth)` によって、上図の赤い枠の外にある、実際には描画しないノードの高さを計算するという、無駄な処理が行われてしまうという点が気になっている人がいるかもしれません。確かにそのような無駄な処理が行われてしまいますが、〇×ゲームのゲーム木のような小規模なゲーム木の場合は、そのような __無駄な計算__ は人間が知覚できないほど __短い時間で行える__ ので、無駄な処理が行われることを __気にする必要はない__ でしょう。なお、どうしてもそのような無駄な処理が行われることが気になる方は、`cal_node_height` に仮引数 `startnode` を追加し、無駄な処理が行われないように `cal_node_height` を修正して下さい。

オセロや将棋のような大規模なゲーム木の場合はそのような無駄な処理によって、人間が知覚できるほどの処理時間の違いが生じる可能性があります。そのような場合は、無駄な処理が行われないように `calc_node_height` を修正する必要があります。
:::

### ノードの深さを表す Node クラスの `depth` 属性の計算

次に、部分木を描画する __Figure のサイズを計算__ する必要があります。Figure の縦幅は、`startnode` の `height` 属性に代入されているので簡単ですが、__横幅を計算__ するためには、__`startnode`__ の __ノードの深さを知る必要__ があります。

Node クラスには、現時点では深さの情報は記録されていないので、__Node__ クラスに __ノードの深さを表す `depth` という属性を追加__ することにします。

下記は、Node クラスの `__init__` メソッドの修正したプログラムです。__Node__ クラスの __インスタンスを作成する際__ に、__実引数でノードの深さを指定__ するようにしました。

* __1 行目__：作成するノードの深さを表す、デフォルト値が 0 の仮引数 `depth` を追加する
* __5 行目__：`depth` 属性に、仮引数 `depth` を代入する

```python
1  from tree import Node
2
3  def __init__(self, mb, depth=0):       
4      self.mb = mb
5      self.depth = depth
6      self.children = []
7
8  Node.__init__ = __init__
```

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

```python
from tree import Node

def __init__(self, mb, depth=0):       
    self.mb = mb
    self.depth = depth
    self.children = []

Node.__init__ = __init__
```
</details>

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

```diff_python
from tree import Node

-def __init__(self, mb, depth=0):
+def __init__(self, mb):       
    self.mb = mb
+   self.depth = depth
    self.children = []

Node.__init__ = __init__
```
</details>

__ノードの深さ__ は、__親ノードの深さ + 1__ になります。また、子ノードは __`calc_children`__ メソッドを使って作成します。従って、下記のような処理を行うことで、ゲーム木の全てのノードに深さの情報を記録することができます。

* __ルートノード__ を作成する際に __深さ 0 を設定__ する
* __子ノードを作成__ する際に、子ノードの深さを __自身のノードの深さ + 1 に設定__ する

先程、Node クラスの `__init__` メソッドの仮引数 `depth` を、デフォルト値が 0 のデフォルト引数としたので、__ルートノードを作成する処理__ では、__深さ 0 のノードが作成__ されます。そのため、上記の 2 つ目の処理を実装することで、ゲーム木の全てのノードに深さの情報を記録することができます。

下記は、子ノードを作成する `calc_children` を修正するプログラムです。

* __8 行目__：子ノードを作成する際に、`self.depth + 1` を実引数に記述することで、自分よりも 1 つ深いノードとして子ノードを作成する。 

```python
 1  from copy import deepcopy
 2
 3  def calc_children(self):
 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, self.depth + 1))
 9
10  Node.calc_children = calc_children
```

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

```python
from copy import deepcopy

def calc_children(self):
    self.children = []
    for x, y in self.mb.calc_legal_moves():
        childmb = deepcopy(self.mb)
        childmb.move(x, y)
        self.insert(Node(childmb, self.depth + 1))

Node.calc_children = calc_children
```
</details>

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

```diff_python
from copy import deepcopy

def calc_children(self):
    self.children = []
    for x, y in self.mb.calc_legal_moves():
        childmb = deepcopy(self.mb)
        childmb.move(x, y)
-       self.insert(Node(childmb))
+       self.insert(Node(childmb, self.depth + 1))

Node.calc_children = calc_children
```
</details>

Node クラスに __属性を追加した__ ので、下記のプログラムで __`mbtree` を作り直す必要があります__。下記のプログラムの 2、3 行目では、ルートノードと、深さ 9 のノードの `depth` 属性を表示しており、実行結果から `depth` 属性に正しい値が代入されることが確認できます。

```python
mbtree = Mbtree()
print(mbtree.root.depth)
print(mbtree.nodelist_by_depth[9][0].depth)
```

実行結果

```
     9 depth 1 node created
    72 depth 2 node created
   504 depth 3 node created
  3024 depth 4 node created
 15120 depth 5 node created
 54720 depth 6 node created
148176 depth 7 node created
200448 depth 8 node created
127872 depth 9 node created
     0 depth 10 node created
total node num = 549946
0
9
```

:::note
上記のプログラムを記述した後で、__ノードの深さ__ は __手数と同じ__ なので、`Marubatsu` クラスの __`move_count` 属性に代入されている__ ことに気が付きましたが、ノードの __`depth` 属性を追加したほうが__、__プログラムがわかりやすくなる__ と思いましたので、上記のプログラムをそのまま採用することにします。
:::

### Figure のサイズの計算

`startnode` のノードの深さがわかるようになったので、Figure のサイズを計算する処理は、下記のプログラムのように記述できます。

* __5 行目__：Figure の横幅を、`maxdepth` から `startnode` の深さを引いて、1 を足した値[^6]から計算するように修正する
* __6 行目__：Figure の縦幅を、`startnode` の高さに修正する

```python
1  def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
2      if startnode is None:
3          startnode = self.root
4      self.calc_node_height(maxdepth)
5      width = 5 * (maxdepth - startnode.depth + 1)
6      height = startnode.height
元と同じなので省略
7        
8  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth - startnode.depth + 1)
    height = startnode.height
    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")        
    
    for depth in range(maxdepth):
        dy = 0
        for node in self.nodelist_by_depth[depth]:
            node.draw_node(ax=ax, size=size, lw=lw, dx=depth*5, dy=dy)
            dy += node.height
        
Mbtree.draw_tree = draw_tree
```
</details>

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

```diff_python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
-   width = 5 * (maxdepth + 1)
+   width = 5 * (maxdepth - startnode.depth + 1)
-   height = self.root.height
+   height = startnode.height
元と同じなので省略
        
Mbtree.draw_tree = draw_tree
```
</details>

### ノードの描画の処理の実装

元のプログラムは、深さ 0 のノードから、深さの浅い順に、その深さのすべてのノードを順番に描画していましたが、今回は以下の点で描画するノードが異なります。

* __深さ `startnode.depth`__ の __`startnode` から描画__ する
* 描画するのは、__`startnode`__ の __子孫ノードだけ__ である

:::note warn
ノードから __子ノードを辿っていく__ ことでたどり着くことができるノードの事を、__子孫（decendant）ノード__ と呼びます。逆に、__親ノードを辿っていく__ ことでたどり着くことができるノードの事を __先祖（ancestor）ノード__ と呼びます。
:::

`create_node_by_df` では、幅優先アルゴリズムで、ルートノードの子孫ノードを、深さが 0 のノードから、深さが浅い順に作成しました。__`startnode` の子孫ノードの描画__ も同様に、__幅優先アルゴリズム__ で、下記の手順で描画することができます。

1. 次に描画を行う、深さ `startnode.depth` のノードの一覧を `[startnode]` に設定する
2. 次に描画を行うノードの深さ `d` を `startnode.depth` に設定する
3. 描画する深さ `d` のノードが存在しない、または `d` が `maxdepth` 以上の場合は部分木の描画の処理が完了しているので処理を終了する
4. 描画する深さ `d` のノードが存在する場合は、それらの __全てのノードを描画__ し、その子ノードを次に描画を行う深さ `d + 1` のノードの一覧に追加する
5. __深さ `d` に 1 を足して__ 手順 3 に戻る 

`create_node_by_df` との主な違いは、以下の通りです。

* __最初の深さ__ が 0 ではなく、__`startnode.depth`__ である
* __最初__ に処理を行う __ノードの一覧__ が `[self.root]` ではなく、__`[startnode]`__ である
* __深さ `d`__ に対して行う処理が、深さ `d` の全てのノードに対する処理ではなく、__深さ `d` の `startnode` の子孫ノードに対する処理だけ__ である
* __行う処理__ が子ノードの作成ではなく、ノードの __描画処理__ である

下記は、上記のアルゴリズムで `draw_tree` を修正したプログラムです。行っている処理は `creat_node_by_df` とかなり似ているので、興味がある方は比べてみて下さい。なお、`creat_node_by_df` で行っていた、部分木のそれぞれの深さのノードの list を `nodelist_by_depth` 属性に記録する処理は必要がないので行っていません。

* __2 行目__：最初に描画するノードの一覧を `[startnode]` で初期化する
* __3 行目__：最初に描画するノードの深さを `startnode.depth` で初期化する
* __4、9、12 行目__：元の `draw_tree` では、ノードの描画位置を `5 * depth` で計算していたが、その方法では、ノードの描画位置が `5 * (maxdepth - depth)` という式になり、見た目がわかりづらくなる。そこで、ノードの描画位置の y 座標と同様の方法で、__ノードの描画位置の x 座標を `dx` で表し__、以下のような処理を行うように修正した
    * __4 行目__：`startnode` の描画の x 座標を `0` で初期化する
    * __9 行目__：x 座標が `dx` の位置にノードを描画する
    * __12 行目__：次の深さのノードを描画する前に、`dx` に `5` を加算する
* __5 行目__：`nodelist` に要素が存在し、なおかつ `depth` が `maxdepth` 未満の場合に `nodelist` を描画するように修正する
* __7 行目__：描画する次の深さのノードの一覧を表す `childnodelist` を空の list で初期化する
* __8 行目__：`nodelist` 内のすべてのノードを描画する
* __13、14 行目__：次に描画するノードの深さを表す `depth` に 1 を足し、`nodelist` に `childnodelist` を代入する

```python
 1  def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
 2      nodelist = [startnode]
 3      depth = startnode.depth
 4      dx = 0
 5      while len(nodelist) > 0 and depth < maxdepth:        
 6          dy = 0
 7          childnodelist = []
 8          for node in nodelist:
 9              node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
10              dy += node.height
11              childnodelist += node.children
12          dx += 5
13          depth += 1
14          nodelist = childnodelist
15        
16  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth - startnode.depth + 1)
    height = startnode.height
    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")        
    
    nodelist = [startnode]
    depth = startnode.depth
    dx = 0
    while len(nodelist) > 0 and depth < maxdepth:        
        dy = 0
        childnodelist = []
        for node in nodelist:
            node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
            dy += node.height
            childnodelist += node.children
        dx += 5
        depth += 1
        nodelist = childnodelist
        
Mbtree.draw_tree = draw_tree
```
</details>

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

```diff_python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
+   nodelist = [startnode]
+   depth = startnode.depth
+   dx = 0
-   for depth in range(maxdepth):
+   while len(nodelist) > 0 and depth < maxdepth:        
        dy = 0
+       childnodelist = []
-       for node in self.nodelist_by_depth[depth]:
+       for node in nodelist:
-           node.draw_node(ax=ax, size=size, lw=lw, dx=depth*5, dy=dy)
+           node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
            dy += node.height
+           childnodelist += node.children
+       dx += 5
+       depth += 1
+       nodelist = childnodelist
        
Mbtree.draw_tree = draw_tree
```
</details>

## `draw_tree` の処理の確認と修正

上記の修正後に、いくつかのゲーム木の部分木を描画して、`draw_tree` が正しく実装されているかどうかを確認することにします。

下記は、ルートノードから深さ 2 までのノードを描画するプログラムです。実行結果から正しく描画されることが確認できます。

```python
mbtree.draw_tree(maxdepth=2)
```

<details><summary><strong>実行結果（長いのでクリックして表示して下さい）</strong></summary>

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d012f618-9f10-8139-3db5-b35202b262d5.png" width="150">

</details>

下記は、深さ 6 のノードの一覧を表す `mbtree.nodelist_by_depth[6]` の中に記録されている最初のノードから深さ 9 までのノードを描画するプログラムです。実行結果から正しく描画されいそうなことが確認できます。

```python
mbtree.draw_tree(mbtree.nodelist_by_depth[6][0], maxdepth=9)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5c18ec5f-ca00-94c5-f72e-055cee9ceb96.png" width="200">

上記で __正しく描画されていそう__ と記述したのは、__実際には正しく描画されていない__ からです。ただし、そのことを __実行結果を見てすぐに気づくことは非常に難しい__ と思います。どこが間違っているかについては今回の記事の最後で説明しますが、興味がある方は、上図のどこが間違っているかを探してみて下さい。

うまく実装できていそうな気はしますが、__上記だけでは確信が持てない__ ので、深さ 5 のノードの一覧を表す `mbtree.nodelist_by_depth[5]` の中に記録されている最初のノードから深さ 9 までのノードを描画してみることにします。実行結果から、一見するとうまくいっているように見えるかもしれませんが、図を少し眺めれば __明らかに何かがおかしい__ ことがわかります。どこがおかしいかについて少し考えてみて下さい。

```python
mbtree.draw_tree(mbtree.nodelist_by_depth[5][0], maxdepth=9)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/72223058-c4f5-2eae-2ce1-f9efa4e3296c.png" width="200">

### 問題の検証

真っ先に気づく部分としては、下図の __赤い枠__ で囲った部分で、ゲーム盤の (2, 1) と (1, 2) のマスに __〇 と × の両方が描画__ されている点が挙げられるでしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6c7409aa-793a-eca2-c2e4-c8855e384362.png" width="200">

また、下記の局面でも赤枠と同様のおかしな局面が表示されます。

* 赤枠の 1 つ上に表示される局面で、(0, 2) と (2, 0) に赤い × が描画される
* 赤枠の 2 つ下に表示される局面でも赤枠と同様の変な局面が描画される

また、気づきづらい点として、上図の __緑の枠__ で囲った部分が挙げられます。2 つある緑の枠で囲った部分の __左の局面__ は、いずれも 〇が 3 つ並んでいるので、__〇 が勝利している局面で__ す。従って、__その局面に子ノードは存在しない__ はずですが、図の緑の枠の部分のように __右にノードが描画されています__。


緑枠の部分に関しては、そのおかしさに気が付かない可能性があるので、一目でおかしいことがわかる、__赤枠の局面__ に __おかしな描画が行われる原因を推測する__ ことにします。

まず、赤枠の部分では __(2, 1) のマスなどに 〇 と × の両方が描画されている__ ことから、__複数の局面が同じ場所に描画されている__ ことが推測されます。そのため、同じ場所に複数の局面が描画される原因を調べることが、このバグの原因を突き止めるための鍵になりそうです。

### 同じ場所に複数の局面が描画される原因

__`draw_tree`__ では、深さの浅い順に、__`draw_node`__ を使って __ノード__ と __子ノード__ の関係を __描画__ しますが、これはよく考えると、__深さ `d`__ のノードを __描画する際__ に、__深さ `d` と 深さ `d` + 1 のノードを描画する__ ことを意味します。

例えば、深さ 0 から 深さ 3 までのノードを `draw_tree` で描画する場合は、`draw_node` によって下記のような深さの局面が処理が行われます。

| `draw_node` を呼び出すノードの深さ  | 描画する局面のノードの深さ |
|:-:|:-:|
| `0`  | `0` と `1`  |
| `1`  | `1` と `2`  |
| `2`  | `2` と `3`  |

上記の表から、`draw_tree` では、__深さが 1 と 2 のノード__ が、__`draw_node` によって、2 回描画される__ ことがわかります。また、表から __最も浅い__ ノードと __最も深い__ ノードである、深さが 0 と 3 のノードは __1 度だけ描画される__ こともわかります。

従って、先ほどの図の赤枠の部分が変だった原因は、おそらく赤枠がある __深さ 8 の局面のノード__ が、以下の 2 つの場合で __2 度描画__ された際に、__y 座標が異なる位置に描画されたため__ であることが推測されます。

* __深さ 7__ のノードを `draw_node` で描画した際に、そのノードの __子ノードとして描画__ する
* __深さ 8__ のノードを `draw_node` で描画した際に、__そのノードを描画__ する

このうちの、いずれかまたは両方で、間違った位置に深さ 8 のノードが描画された可能性が高いので、次はそのことを検証することにします。

### `draw_node` で子ノードとして描画された 深さ 8 のノードの検証

先程 `draw_tree` では、__最も深いノードが 1 度しか描画されない__ 事がわかったので、下記のプログラムで深さ 5 のノードから __深さ 8 までの部分木を描画__ することで、実行結果のように、深さ 8 のノードを 1 度だけ描画するようにすることができます

```python
mbtree.draw_tree(mbtree.nodelist_by_depth[5][0], maxdepth=8)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e6dd540a-3bb0-4534-df91-c7891145336c.png" width="200">

上図で描画された __深さ 8 のノード__ は、「__深さ 7__ のノードを `draw_node` で描画した際に、そのノードの __子ノードとして描画__」したものです。上図の描画におかしな点は見られないことから、先程のおかしな局面の図は、もう一つの「__深さ 8__ のノードから `draw_node` で描画した際」に行われた可能性が高いことが推測されます。

### 深さ 8 のノードから `draw_node` で描画された深さ 8 のノードの検証

深さ 8 のノードから `draw_node` で描画された深さ 8 のノードの描画の検証は、下記のプログラムのように、子ノードを描画しないように `draw_node` を修正することで行えます。

* 8 行目の下にあった子ノードを描画する処理を削除する。なお、__エッジを描画する処理は必要__ なので削除してはいけない点に注意すること

```python
 1  from marubatsu import Marubatsu_GUI
 2
 3  def draw_node(self, ax, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
 4      # 子ノードが存在する場合に、エッジの線と子ノードを描画する
 5      if len(self.children) > 0:   
 6          plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + edgeheight], c="k", lw=lw)
 7          for childnode in self.children:
 8              # この下にあった子ノードを描画する処理を削除する
 9              plt.plot([dx + 4 , dx + 4.5], [dy + 1.5, dy + 1.5], c="k", lw=lw)
10              dy += childnode.height
11            
11  Node.draw_node = draw_node
```

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

```python
from marubatsu import Marubatsu_GUI

def draw_node(self, ax, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    if ax is None:
        height = len(self.children) * 4
        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")
        for childnode in self.children:
            childnode.height = 4
        if len(self.children) > 0:
            edgeheight = height - 4
    else:
        if len(self.children) > 0:
            edgeheight = self.height - self.children[-1].height
    
    # 自分自身のノードを (dx, dy) に描画する
    Marubatsu_GUI.draw_board(ax, self.mb, lw=lw, dx=dx, dy=dy)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:   
        plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + edgeheight], c="k", lw=lw)
        for childnode in self.children:
            plt.plot([dx + 4 , dx + 4.5], [dy + 1.5, dy + 1.5], c="k", lw=lw)
            dy += childnode.height
            
Node.draw_node = draw_node
```
</details>

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

```diff_python
from marubatsu import Marubatsu_GUI

def draw_node(self, ax, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:   
        plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + edgeheight], c="k", lw=lw)
        for childnode in self.children:
-           Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy, lw=lw)
            plt.plot([dx + 4 , dx + 4.5], [dy + 1.5, dy + 1.5], c="k", lw=lw)
            dy += childnode.height
            
Node.draw_node = draw_node
```
</details>

上記の修正後に下記のプログラムで再び深さ 5 のノードから深さ 9 までの部分木を描画すると、実行結果のような画像が描画されます。`draw_node` で子ノードを描画しなくなったので、深さ 9 のノードが描画されなくなりますが、その点についてはこの後で修正します。

```python
mbtree.draw_tree(mbtree.nodelist_by_depth[5][0], maxdepth=9)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4a6c6ef6-6968-759a-fe8d-a60cadf3c480.png" width="200">

### 比較による原因の検証

下図は、左から下記の方法で深さ 8 のノードを描画した場合の上部を並べたものです。

* 深さ 7 の子ノードとして `draw_node` で描画した場合
* 深さ 8 のノードから `draw_node` で描画した場合
* 上記の両方を描画した場合

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7297989f-67d6-0e14-9ad4-046b96e988bc.png" width="250">

左の __2 つの図を重ね合わせる__ と、確かに __右の図になる__ ので、おかしな図が描画される原因が、__同じ深さの局面を異なる位置に 2 回描画した__ 事であることが確認できました。

### 問題の修正

問題の原因が同じ深さの局面を 2 度描画したことにあるので、どちらか __片方の方法だけで局面を描画する__ ように修正することにします。どちらの方法で局面を描画すべきであるかについて少し考えてみて下さい。

`draw_node` で子ノードとして局面を描画する方法を採用してしまうと、深さ 0 のノードを描画することができなくなってしまうので、そちらの方法は採用することができません。

`draw_node` で子ノードを描画しないようにする修正は先程行いましたが、そのように修正したため、__最も深いノードが描画されなくなった__ ので、その問題を修正することにします。

この問題は、下記のプログラムのように、`draw_tree` で、深さ 0 から `maxdepth` - 1 ではなく、__`maxdepth` まで__ の深さのノードを __`draw_node` で描画する__ ようにすることで解決できます。最も深いノードのエッジが描画されてしまうのではないかと思う人がいるかもしれませんが、[前回の記事](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E5%95%8F%E9%A1%8C%E3%81%AE%E6%A4%9C%E8%A8%BC%E3%81%A8%E4%BF%AE%E6%AD%A3)で、子ノードが存在しない場合は、エッジと子ノードを描画しないように `draw_node` を修正したので、この方法で問題はありません。

* __2 行目__：`depth` が `maxdepth` 未満ではなく、以下を判定するように修正する

```python
1  def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
2      while len(nodelist) > 0 and depth <= maxdepth:        
元と同じなので省略
3        
4  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth - startnode.depth + 1)
    height = startnode.height
    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")        
    
    nodelist = [startnode]
    depth = startnode.depth
    dx = 0
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        childnodelist = []
        for node in nodelist:
            node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
            dy += node.height
            childnodelist += node.children
        dx += 5
        depth += 1
        nodelist = childnodelist
        
Mbtree.draw_tree = draw_tree
```
</details>

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

```diff_python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
-   while len(nodelist) > 0 and depth < maxdepth:        
+   while len(nodelist) > 0 and depth <= maxdepth:        
元と同じなので省略
        
Mbtree.draw_tree = draw_tree
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように、深さ 9 のノードが描画されるようになります。ただし、深さ 8 のノードの描画位置は間違ったままなので、修正する必要があります。

```python
mbtree.draw_tree(mbtree.nodelist_by_depth[5][0], maxdepth=8)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2cae28aa-99e8-5f86-3b80-4ad70be51f00.png" width="200">

### 局面の描画位置の間違いの検証

描画位置の __間違いを検証__ する際には、__正しく描画された図と比較す__ ると良いでしょう。

下図左は、上図の上部を抜粋したもので、下図右は、正しい位置に深さ 8 の局面が描画された場合の図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9c6db312-014c-c091-8e3d-a231e1f06a82.png" width="350">

左右の図を比較すると右図の正しい位置に描画される深さ 8 の局面は、一部で __間を空けて描画される__ ことが分かります。また、その __間が空く部分__ は、左図の赤枠の局面のように、__決着が付いた局面の右__ であることがわかります。

つまり、左図の問題は、__決着がついた局面の右__ に、紫の枠の局面の部分のように、__間を空けずに上から詰めて描画してしまったこと__ が原因で発生したことがわかります。

そのことを踏まえて __`draw_tree`__ のプログラムを検証することにします。`draw_tree` では、下記のプログラムの 7 行目ように、__描画したノードの子ノードを `childnodelist` に追加__ する処理を行います。そして、__次の深さのノードを描画__ する際に、__`childnodelist` に登録されていたノード__ を Figure の __上端から順番に描画する__ という処理を行います。

```python
1  while len(nodelist) > 0 and depth < maxdepth:        
2      dy = 0
3      childnodelist = []
4      for node in nodelist:
5          node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
6          dy += node.height
7          childnodelist += node.children
```            

上記を元に、下図の __深さ 7__ の赤と紫枠のノードを描画した際に行われる処理を検証します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f2c692e9-1ad7-8386-c0e8-0fa18d43d286.png" width="300">

赤枠と紫枠のノードを描画する際には、下記の手順で処理が行われます。

1. 赤枠のノードはこの深さの最初のノードなので、このノードを描画する前の `childnodelist` には 空の list が代入される
2. 赤枠のノードは決着がついた局面で、子ノードは存在しないので、`node.children` には空の list が代入されている。従って、赤枠のノードの描画後に、`childnodelist + node.children` を実行しても `childnodelist` の内容は空の list のままである
3. 紫枠のノードは決着がついていないので、子ノードが存在する。そのため、紫枠のノードの描画後に `childnodelist` には、紫枠のノードの子ノードが追加される

上記から、__深さ 7__ のノードが __すべて描画された後__ では、__`childnodelist` の先頭__ には、__紫枠__ のノードの __子ノードが代入__ されることになります。そのため、次の __深さ 8__ のノードを描画する際には、__紫枠__ のノードの __子ノード__ が、Figure の __上から順に描画__ され、上図のように、__間を空ける必要がある場所__ に __詰めてその局面が描画__ されてしまうことになります。

このことから、__子ノードが存在しないノードを描画した場合__ でも、__`childnodelist`__ には、そこに __何も描画しないことを表す何らかのデータを追加する必要がある__ ことがわかります。従って、下記のようにプログラムを修正することで、この問題を解決することができます。

* 子ノードが存在しない場合は、`childnodelist` にそこに何も描画しないことを表す __`None` を追加__ する
* ノードを描画する際に __`nodelist` の要素に `None` が代入__ されていた場合は、何も描画せず、__次のノードを一つ下に描画する__ ために、__`dy` の座標を 4 増やす__ 処理を行う

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

* __6 行目__：`nodelist` から取り出した `node` の値が `None` の場合は、何も描画せずに、`dy` を `4` 増やす処理だけを行う
* __11 ~ 14 行目__：子ノードが存在する場合はこれまでと同じ処理を行うが、子ノードが存在しない場合は `childnodelist` に `None` を追加するように修正する

```python
 1  def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
 2      while len(nodelist) > 0 and depth <= maxdepth:        
 3          dy = 0
 4          childnodelist = []
 5          for node in nodelist:
 6              if node is None:
 7                  dy += 4
 8              else:
 9                  node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
10                  dy += node.height
11                  if len(node.children) > 0:  
12                      childnodelist += node.children
13                  else:
14                      childnodelist.append(None)
元と同じなので省略
15        
16  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth - startnode.depth + 1)
    height = startnode.height
    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")        
    
    nodelist = [startnode]
    depth = startnode.depth
    dx = 0
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
            else:
                node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
                dy += node.height
                if len(node.children) > 0:  
                    childnodelist += node.children
                else:
                    childnodelist.append(None)
        dx += 5
        depth += 1
        nodelist = childnodelist
        
Mbtree.draw_tree = draw_tree
```
</details>

<details><summary><strong>修正箇所（else のインデントの修正は省略します）</strong></summary>

```diff_python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        childnodelist = []
        for node in nodelist:
+           if node is None:
+               dy += 4
+           else:
                node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
                dy += node.height
-               childnodelist += node.children
+               if len(node.children) > 0:  
+                   childnodelist += node.children
+               else:
+                   childnodelist.append(None)
元と同じなので省略
        
Mbtree.draw_tree = draw_tree
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果から深さ 8 のノードが正しい位置に描画されるようになることが確認できますが、深さ 9 のノードの描画位置が正しく描画されないという問題があることがわかります。この問題の原因と修正方法について少し考えてみて下さい。

```python
mbtree.draw_tree(mbtree.nodelist_by_depth[5][0], maxdepth=9)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/203d4cf1-5f1e-1622-53cc-47006c6e6717.png" width="200">

### 深さ 9 のノードの描画位置のバグの検証

深さ 9 のノードの描画位置の問題点は、上図から先程と同様に、__決着がついた局面の右に詰めて局面が描画される__ ことであることがわかります。

このようなことが起きる原因は、下記のプログラムのように、__`node` が `None` だった場合__ に、次のノードを描画する座標を __下にずらす処理しか行っていない__ からです。

```python
            if node is None:
                dy += 4
```

従って、下記のプログラムの 8 行目のように、`node` が `None` の場合は、`childnodelist` に `None` を追加することで、一つ下の深さの同じ場所に何も表示されないようになります。

また、この処理は __その下のすべての深さでも行われる__ ようになるので、__決着がついた局面の右__ には、どの深さでも __局面が描画されなくなります__。

```python
 1  def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
 2      while len(nodelist) > 0 and depth <= maxdepth:        
 3          dy = 0
 4          childnodelist = []
 5          for node in nodelist:
 6              if node is None:
 7                  dy += 4
 8                  childnodelist.append(None)
元と同じなので省略
 9        
10  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth - startnode.depth + 1)
    height = startnode.height
    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")        
    
    nodelist = [startnode]
    depth = startnode.depth
    dx = 0
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
                childnodelist.append(None)
            else:
                node.draw_node(ax=ax, size=size, lw=lw, dx=dx, dy=dy)
                dy += node.height
                if len(node.children) > 0:  
                    childnodelist += node.children
                else:
                    childnodelist.append(None)
        dx += 5
        depth += 1
        nodelist = childnodelist
        
Mbtree.draw_tree = draw_tree
```
</details>

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

```diff_python
def draw_tree(self, startnode=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
+               childnodelist.append(None)
元と同じなので省略
        
Mbtree.draw_tree = draw_tree
```
</details>

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

```python
mbtree.draw_tree(mbtree.nodelist_by_depth[5][0], maxdepth=9)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ba6b04cd-16c6-690a-d9e2-472962c8ef68.png" width="200">

### 深さが 6 のノードからの部分木の描画の確認

さきほど、深さ 6 のノードからの部分木の描画が間違っていると説明しましたので、下記のプログラムで修正後にその部分木を描画してみることにします。実行結果の左図が修正後のもの、右図修正前のものです。

```python
mbtree.draw_tree(mbtree.nodelist_by_depth[6][0], maxdepth=9)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e52a2bea-5b37-cdd7-9e8d-7a766b4d4b09.png" width="200">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4d8b6682-c74d-6ae8-8e42-51375cb49674.png" width="200">

右図では、決着が付いた局面の右に局面が描画されますが、左図では正しく描画されることが確認できます。ただし、右図を一目見て間違っていることを認識することは簡単ではないでしょう。このように、プログラムが __正しく実装されているかどうかを確認__ する際には、__間違っていることが簡単にはわからないような場合が良くあります__。そのため、確認の作業を行う際は、__様々な状況で確認を行う__ 必要があることを覚えて解いてください。

# 今回の記事のまとめ

今回の記事では、幅優先アルゴリズムで任意の深さのゲーム木を作成し、ゲーム木の部分木を描画する処理を実装しました。

部分木を描画する処理では、見つけづらく、初心者には修正が難しそうなバグが発生しましたが、このような見つけづらく修正しづらいバグは、実際に良く発生するので、今回のバグの修正方法が参考なれば幸いです。

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

以下のリンクから、本記事で入力して実行した JupyterLab のファイルを見ることができます。

https://github.com/ysgeso/marubatsu/blob/master/090/marubatsu.ipynb

以下のリンクは、今回の記事で更新した tree.py です。

https://github.com/ysgeso/marubatsu/blob/master/090/tree_new.py

# 次回の記事

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

[^1]:例えば、(0, 0)、(1, 1)、(2, 2) の順で着手を行った場合と、(2, 2)、(1, 1)、(0, 0) の順で着手を行った場合は、完全に同じ局面になります
[^2]:0 の階乗は直観的に 0 であると思う人が多いかもしれませんが、数学で 0 の階乗が 1 に定義されている理由は、そのように定義すると都合が良いからです。実際に 0 の階乗が 1 であれば、n 手目までの着手の組み合わせが 1 つの式で表現できます
[^3]:深さ 0 のノードも含むので、深さの数は `maxdepth + 1` になります
[^4]:`dy` に関する処理の意味を忘れた方は、[前回の記事](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E9%AB%98%E3%81%95%E3%81%AE%E6%83%85%E5%A0%B1%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-draw_node-%E3%81%AE%E4%BF%AE%E6%AD%A3)を復習して下さい
[^5]:キリの悪い数字に見えるかもしれませんが、これは __2 進数__ では $2^{16}$ という __キリの良い数字__ です
[^6]:1 を足す理由は、例えば、`startnode` の深さと `maxdepth` が等しい場合は、__1 を足さないと Figure の幅が 0 になってしまう__ からです