Pythonで〇×ゲームのAIを一から作成する　その92　ゲーム木の部分木の表示範囲の改良

# 目次と前回の記事

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

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

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

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

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

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

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

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

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

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

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

# ゲーム木全体の視覚化の方針

〇×ゲームに限った話ではありませんが、多くのゲームのゲーム木は、規模が大きすぎてその __全体を詳細に表示するようなゲーム木の図を描画することは困難__ です。実際に〇×ゲームの場合は、[以前の記事](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E6%AD%A3%E3%81%97%E3%81%84%E5%90%84%E6%B7%B1%E3%81%95%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%95%B0%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)で示したように、最もノードの数が多い深さ 8 のノードの数が約 20 万もあるため、ゲーム木を図示した場合にとんでもない高さの画像が必要になります。

このような場合は、ゲーム木の一部である __部分木を描画__ し、キーボードやマウスなどの操作によって __表示する部分木を移動する__ ことで、__全体像を把握する__ ということが良く行われます。例えば、コンピューターの __ファイルシステム__ は、ゲーム木と同様の __木構造__ になっており、__フォルダ__ が木構造の __ノードに対応__ します。Windows の場合は、エクスプローラというアプリを使って、下記のような方法でハードディスクなどの記憶装置の中に保存されたファイルシステムの一部を表示しています。

* 特定のフォルダの中身を表示することで、全体の一部を表示する
* フォルダのアイコンをダブルクリックすることで、表示するフォルダを移動する
* ↑ ボタンをクリックすることで、親のフォルダに表示を移動する

そこで、本記事では下記のような方法で〇×ゲームのゲーム木を視覚化し、全体像を把握できるようにする処理を実装することにします。

* __特定のノードを中心とした部分木__ を表示する
* ボタンなどの GUI や、カーソルキーなどの操作によって __表示する部分木を移動__ する

# 部分木の描画に関する問題点とその解決方法

前回の記事では、下図のような、__特定のノードから特定の深さまでの部分木__ を表示する処理を実装しましたが、上記のようなゲーム木の視覚化を下図のような部分木で行うと、__部分木の表示範囲__ を原因とするいくつかの問題が発生します。どのような問題があるかについて少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/20efcfa6-d166-cda6-3555-9001c49bfcc7.png" width="200">

## 先祖ノードの局面の表示

ゲーム木を使ってゲームの分析を行う際に、__どのような着手を行った結果、その局面に至ったか__ の情報は重要です。しかし、上図のゲーム木の部分木には、どのような着手を行った結果、一番左の局面に至ったかについての情報が表示されていません。

そこで、`draw_tree` で `startnode` に __特定の局面を指定して部分木を描画__ する際に、__ゲーム開始時の局面から、`startnode` の局面に至るまでの間の局面も表示__ するように修正することにします。そのような、ノードの __親ノードを辿っていく__ ことでたどり着くことができるノードの事を __先祖（ancestor）ノード__ と呼びます。Figure の中で、どのような位置に先祖ノードを表示すればよいかについて少し考えてみて下さい。

例えば、Windows のエクスプローラーでは、下図の赤丸の部分のような方法で、現在表示しているフォルダを表示するまでに開かなければならないフォルダを表示します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/91476721-a035-c704-5781-b2297c84a6c1.png" width="300">

エクスプローラーでは上部に表示しますが、`draw_tree` の場合は `startnode` の左に、下図のような形で先祖ノードを並べて表示するという方法が考えられます。先祖ノードに __子ノードがいくつあっても、エッジは右に 1 本だけ表示__ することにします。本記事ではこの方法を採用しますが、他の方法が良いと思った方は自由に変更して下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a33bc60e-b311-73e9-baa9-d7f721f161b3.png" width="500">

### ノードへの親ノードの情報の記録

上図のような描画を行うためには、__ルートノード__ から `startnode` に至るまでの先祖ノードの情報を知る必要があります。現状の `Node` には子ノードの情報しか記録されていませんが、__親ノードの情報を記録__ するようにすれば、`startnode` から __親ノードを順に辿っていく__ ことで __すべての先祖ノード__ を __深い順に辿る__ ことができます。

:::note
ノードの `mb` 属性に代入されている `Marubatsu` クラスのインスタンスの `record` 属性に、ルートノードからそのノードの局面に至るまでの着手が記録されているので、その情報を使ってルートノードからそのノードに至るまでの先祖ノードを調べて表示する処理を記述することも可能です。
:::

そこで、`Node` クラスを下記のように修正することにします。

* 親ノードを表す `parent` という属性を追加する
* 親ノードが存在しないルートノードの場合は `parent` に `None` を代入する
* 親ノードは、Node クラスのインスタンスを作成する際に実引数で指定する

まず、`__init__` メソッドを下記のプログラムのように修正することで、__`Node` クラスのインスタンスを作成する際に、親ノードを指定__ できるようにします。なお、親ノードを表す実引数を省略した場合は、親ノードが存在しないルートノードが作成されるようにしました。

* __3 行目__：デフォルト値を `None` とするデフォルト引数 `parent` を追加する
* __5 行目__：`parent` 属性に仮引数 `parent` を代入する 

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

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

```python
from tree import Node

def __init__(self, mb, parent=None, depth=0):
    
    self.mb = mb
    self.parent = parent
    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, parent=None, depth=0):
    
    self.mb = mb
+   self.parent = parent
    self.depth = depth
    self.children = []

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

次に、下記のプログラムの 8 行目のように、子ノードを作成する処理を行う `calc_children` を、作成する __子ノードの親ノード__ が __自分のノードを表す `self` になる__ ように修正します。

```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, parent=self, depth=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, parent=self, depth=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.depth + 1))
+       self.insert(Node(childmb, parent=self, depth=self.depth + 1))

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


下記のプログラムの 3 行目のように Mbtree クラスのインスタンスを作成し、4 行目で __ルートノードの子ノードの親ノードの局面__[^1] を表示すると、実行結果のように __ルートノードの局面が表示される__ ので、Node に親ノードを表す属性が追加されたことが確認できます。

```python
from tree import Mbtree

mbtree = Mbtree()
print(mbtree.root.children[0].parent.mb)
```

実行結果
```
     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
Turn o
...
...
...
```

### 先祖ノードの局面の表示

次に、__先祖ノードの局面をどこに描画するか__ を決める必要がありますが、`startnode` の左に並べて描画するのが自然でしょう。

すべての先祖ノードに対して行うという処理は、__ルートノードにたどり着くまで親ノードを順番に辿る__ という手順で行うことができます。この処理は、先祖ノードを __深い順に辿って行う__ という処理であり、下記のプログラムのように記述することができます。

* __1 行目__：`node` に親ノードが存在しない場合はルートノードであることを表すので、親ノードが存在しない間、繰り返しの処理を行う
* __2 行目__：`node` に親ノードである `node.parent` を代入する
* __3 行目__：`node` に関する処理を記述することで、親ノードの処理を行う

```python
while node.parent is not None:
    node = node.parent
    # node に関する処理を行う
```

従って、`startnode` のすべての先祖ノードを `startnode` の左に並べて描画するという処理は、下記のプログラムのように記述できます。

* __8 行目__：Figure の左端にルートノードを描画することになったので、__描画するノードの深さは 0 ~ `maxdepth` になる__。従って、__Figure の幅__ は __`5 * (maxdepth + 1)`__ で計算できる
* __11 行目__：左端に描画するノードが `startnode` からルートノードに変わったので、__`startnode`__ の描画位置の __x 座標__ はその __深さ * 5 だけ右にずれる__ ことになる。そのため `startnode` の描画位置の x 座標表す `dx` を、`0` から __`startnode.depth * 5`__ に修正する
* __15 ~ 21 行目__：`startnode` の先祖ノードを深い順に、先程示した方法で繰り返しを使ってゲーム盤を描画する処理を行う
* __16 行目__：最初に表示する先祖ノードは、`startnode` の親ノードなので、その深さである `startnode.depth - 1` を使って描画位置の x 座標を計算して `dx` に代入する
* __17 行目__：`startnode` の __先祖ノード__ は、__いずれも `startnode` と同じ y 座標に描画__ する。また、その座標は `startnode` と同様に、Figure の上下のちょうど真ん中に描画するので、[前回の記事](https://qiita.com/ysgeso/items/ae8a782334350cb9c95b#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%8F%8F%E7%94%BB%E4%BD%8D%E7%BD%AE%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)で説明したように、`(startnode.height - 3) / 2` という式で計算できる
* __20 行目__：(dx, dy) の位置に、`draw_board` を使って `node` のノードの局面を描画する
* __21 行目__：`node` の親ノードの局面は、一つ左に描画するので `dx` から `5` を引く

```python
 1  from marubatsu import Marubatsu_GUI
 2  import matplotlib.pyplot as plt
 3
 4  def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
 5      if startnode is None:
 6          startnode = self.root
 7      self.calc_node_height(maxdepth)
 8      width = 5 * (maxdepth + 1)
 9      height = startnode.height
10      fig, ax = plt.subplots(figsize=(width * size, height * size))
元と同じなので省略
11      dx = 5 * depth
12      while len(nodelist) > 0 and depth <= maxdepth:        
13          dy = 0
元と同じなので省略
14        
15      node = startnode
16      dx = 5 * (node.depth - 1)
17      dy = (startnode.height - 3) / 2
18      while node.parent is not None:
19          node = node.parent
20          Marubatsu_GUI.draw_board(ax, node.mb, show_result=True, dx=dx, dy=dy, lw=lw)
21          dx -= 5
22    
23  Mbtree.draw_tree = draw_tree
```

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

```python
from marubatsu import Marubatsu_GUI
import matplotlib.pyplot as plt

def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth + 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 = 5 * depth
    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, maxdepth=maxdepth, 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
        
    node = startnode
    dx = 5 * (node.depth - 1)
    dy = startnode.height / 2 - 1.5
    while node.parent is not None:
        node = node.parent
        Marubatsu_GUI.draw_board(ax, node.mb, show_result=True, dx=dx, dy=dy, lw=lw)
        dx -= 5
    
Mbtree.draw_tree = draw_tree
```
</details>

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

```diff_python
from marubatsu import Marubatsu_GUI
import matplotlib.pyplot as plt

def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
-   width = 5 * (maxdepth - startnode.depth + 1)
+   width = 5 * (maxdepth + 1)
    height = startnode.height
    fig, ax = plt.subplots(figsize=(width * size, height * size))
元と同じなので省略
-   dx = 0
+   dx = 5 * depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
元と同じなので省略
        
+   node = startnode
+   dx = 5 * (node.depth - 1)
+   dy = startnode.height / 2 - 1.5
+   while node.parent is not None:
+       node = node.parent
+       Marubatsu_GUI.draw_board(ax, node.mb, show_result=True, dx=dx, dy=dy, lw=lw)
+       dx -= 5
    
Mbtree.draw_tree = draw_tree
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果のように `startnode` の左にルートノードから `startnode` に至るまでの祖先ノードの局面が描画されるようになります。

```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/b5358e8f-631d-1f06-c113-db30f15023d7.png" width="500">

### 先祖ノードのエッジの描画

上記のプログラムでは、`startnode` の __先祖ノードにエッジが描画されない__ という問題があります。この問題は、`draw_node` 内で行っていたノードのエッジを描画する処理を `draw_tree` 内の先祖ノードを描画する処理にも記述すれば解決できますが、__同じような処理を `draw_node` と `draw_tree` の両方で記述するのはあまりよい方法であるとは言えません__。

__先祖ノードの描画__ で行いたい処理は、__ノードの描画とその右に伸びる 1 本だけのエッジ__ です。また、そのようなノードとエッジの描画の処理は、[前回の記事](https://qiita.com/ysgeso/items/ae8a782334350cb9c95b#%E9%83%A8%E5%88%86%E6%9C%A8%E3%81%AE%E6%9C%80%E3%82%82%E6%B7%B1%E3%81%84%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AB%E5%AD%90%E3%83%8E%E3%83%BC%E3%83%89%E3%81%8C%E5%AD%98%E5%9C%A8%E3%81%99%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AE%E8%A1%A8%E7%A4%BA)で、「部分木の最も深いノードに子ノードが存在する場合の表示」として __実装済__ です。従って、__その処理をうまく利用する__ ことで、先祖ノードとそのエッジの描画を __簡潔に記述__ することができます。どのように記述すれば良いかについて少し考えてみて下さい。

「部分木の最も深いノードに子ノードが存在する場合の表示」の処理は、`draw_node` に対して、下記のような実引数を記述した場合に行われます。

* `draw_node` で描画する __ノードの深さと `maxdepth` が等しい__
* `draw_node` で描画するノードが __子ノードを持つ__

`startnode` の __先祖ノード__ は、先祖であることから __必ず子ノードを持つ__ ので、上記の __2 つ目の条件は必ず満たします__。従って、`draw_node` を呼び出す際に、キーワード引数 __`maxdepth` にそのノードの深さを代入__ するようにすれば、その __ノードとその右に伸びる 1 本だけのエッジを描画__ することができます。

その処理の実装は、下記のプログラムのように `draw_node` を修正すれば良いと思った方がいるかもしれませんが、このプログラムではうまくいきません。

* __4 行目の下__ にあった `dy` を計算する処理は必要が無くなったので削除する
* __7 行目__：`draw_node` の __キーワード引数 `maxdepth`__ に、__描画するノードの深さを代入__ することで、そのノードと右に伸びる 1 本のエッジを描画するように修正する。なお、先祖ノードは __Figure の上下方向の真ん中に描画__ するので、__ノードを描画する y 座標の基準__ となる __`dy`__ には Figure の __上端を表す `0` で初期化する__ 必要がある点に注意する事

```python
 1  def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
 2      node = startnode
 3      dx = 5 * (node.depth - 1)
 4      # この下にあった dy を計算する処理は必要が無くなったので削除する
 5      while node.parent is not None:
 6          node = node.parent
 7          node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
 8          dx -= 5
 9    
10  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth + 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 = 5 * depth
    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, maxdepth=maxdepth, 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
        
    node = startnode
    dx = 5 * (node.depth - 1)
    while node.parent is not None:
        node = node.parent
        node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
        dx -= 5
    
Mbtree.draw_tree = draw_tree
```
</details>

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

```diff_python
def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
    node = startnode
    dx = 5 * (node.depth - 1)
-   dy = (startnode.height - 3) / 2
    while node.parent is not None:
        node = node.parent
-       Marubatsu_GUI.draw_board(ax, node.mb, show_result=True, dx=dx, dy=dy, lw=lw)
+       node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
        dx -= 5
    
Mbtree.draw_tree = draw_tree
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果のように `startnode` の先祖ノードが描画されなくなります。その理由について少し考えてみて下さい。

```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/8626a42a-c28f-66c8-65de-0e786afae900.png" width="500">

### バグの原因の検証と修正

ノードが描画されなくなったので、`draw_node` 内で __ノードの描画__ を行う下記のプログラムを __検証する__ ことにします。

```python
# 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
y = dy + (self.height - 3) / 2
Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, lw=lw, dx=dx, dy=y)
```

上記のプログラムでは、__`dy + (self.height - 3) / 2`__ という式でノードのゲーム盤を描画する __y 座標を計算__ しています。このうち __`dy`__ には `node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)` によって `draw_node` を呼び出していることから __`0` が代入されている__ ので、__`self.height` の値がおかしい可能性が高い__ でしょう。

そこで、下記のプログラムのように、__ルートノードの `height` 属性を表示__ してみると、実行結果から __約 100 万という値が代入されている__ ことがわかります。従って、ルートノードは、Figure の __表示の範囲外に描画__ されたため、表示されないように見えてしまいます。

```python
print(mbtree.root.height)
```

実行結果

```
1020672
```

__`startnode` と同じ y 座標__ に先祖ノードを描画するためには、__先祖ノードの `height` 属性の値を `startnode` の `height` 属性と同じ値にする__ 必要があります。従って、下記のプログラムのように `draw_tree` を修正することで、この問題を解決することができます。

* __7 行目__：先祖ノードの `height` 属性に `startnode` の `height` 属性を代入する

```python
 1  def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
 2      node = startnode
 3      dx = 5 * (node.depth - 1)
 4      # この下にあった dy を計算する処理は必要が無くなったので削除する
 5      while node.parent is not None:
 6          node = node.parent
 7          node.height = startnode.height
 8          node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
 9          dx -= 5
10    
11  Mbtree.draw_tree = draw_tree
```

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

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

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

```diff_python
def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
    node = startnode
    dx = 5 * (node.depth - 1)
    while node.parent is not None:
        node = node.parent
+       node.height = startnode.height
        node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
        dx -= 5
    
Mbtree.draw_tree = draw_tree
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果のように `startnode` の先祖ノードとその右に 1 本のエッジだけが描画されるようになります。

```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/5d772a9c-d873-52e5-9598-a1ba2a2f43a7.png" width="500">

### `dx` の計算方法の改良

上記のプログラムでは、最初のノードを描画する __x 座標__ を __`dx` という変数に代入__ し、ノードを描画する度に __`dx` の値から `5` を引く__ ことで __次のノードの描画位置を計算__ しています。このように記述した理由は、`dx` を一つの計算式で計算する場合は、その計算式の見た目が少し複雑になりプログラムがわかりづらくなってしまうためでした。

しかし、今回の修正によって、必ず __ルートノードから__ ゲーム木の部分木を __描画するようになった__ ことで、ノードの描画の __x 座標__ は、__`ノードの深さ * 5`__ というシンプルで __わかりやすい式で計算できる__ ようになります。そこで、下記のプログラムのように `dx` の計算をその式で行うようにすることにします。

* 4、18 行目の下にあった、`dx` を初期化する処理を削除する
* 13 行目の下にあった、`dx` に 5 を加算する処理を削除する
* 24 行目の下にあった、`dx` に 5 を減算する処理を削除する
* __6、22 行目__：`dx` を、描画するノードの深さを使った式で計算するように修正する

```python
 1  def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
 2      nodelist = [startnode]
 3      depth = startnode.depth
 4      # この下にあった `dx` の初期化処理を削除する
 5      while len(nodelist) > 0 and depth <= maxdepth:      
元と同じなので省略
 6                  dx = 5 * node.depth
 7                  node.draw_node(ax=ax, maxdepth=maxdepth, size=size, lw=lw, dx=dx, dy=dy)
 8                  dy += node.height
 9                  if len(node.children) > 0:  
10                      childnodelist += node.children
11                  else:
12                      childnodelist.append(None)
13          # この下にあった `dx` に 5 を加算する処理を削除する
14          depth += 1
15          nodelist = childnodelist
16        
17      node = startnode
18      # この下にあった `dx` の初期化処理を削除する
19      while node.parent is not None:
20          node = node.parent
21          node.height = startnode.height
22          dx = 5 * node.depth
23          node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
24          # この下にあった `dx` に 5 を減算する処理を削除する
25    
26  Mbtree.draw_tree = draw_tree
```

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

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

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

```diff_python
def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
    nodelist = [startnode]
    depth = startnode.depth
-   dx = 5 * depth
    while len(nodelist) > 0 and depth <= maxdepth:      
元と同じなので省略
+               dx = 5 * node.depth
                node.draw_node(ax=ax, maxdepth=maxdepth, 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
        
    node = startnode
-   dx = 5 * (node.depth - 1)
    while node.parent is not None:
        node = node.parent
        node.height = startnode.height
+       dx = 5 * node.depth
        node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
-       dx -= 5
    
Mbtree.draw_tree = draw_tree
```
</details>

実行結果は先ほどと同じなので省略しますが、上記の修正後に、下記のプログラムを実行して正しい描画が行われることを確認して下さい。

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

## 兄弟ノードの描画

上記の修正で、先祖ノードの描画を行うことができるようになりましたが、ゲーム木を使ってゲームの分析を行う際には、`startnode` の __親ノードの局面で合法手を着手した局面__、すなわち __親ノードの子ノードの一覧__ の情報も重要になります。

木構造で、__同じノードの子ノード__ のことを __兄弟（sibling）ノード__ と呼びます。従って、上記の、親ノードの局面の合法手を着手した局面は、__`startnode` の兄弟ノードを表します__。

ただし、`draw_tree` を __`startnode` の親のノードから `maxdepth` までの深さの部分木を描画__ するようにしてしまうと、描画する __ノードの数が大幅に増えてしまう__ 場合があるという問題が発生します。

例えば、先程は深さ 6 のノードから深さ 9 までの部分木を描画しましたが、下記のプログラムのように、__その親のノードから深さ 9 までの部分木を描画__ すると実行結果からわかるように、__画像の縦幅が大幅に増えてしまいます__。

この問題をうまく解決する方法について少し考えてみて下さい。

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

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

```diff_python
-mbtree.draw_tree(mbtree.nodelist_by_depth[6][0], maxdepth=9)
+mbtree.draw_tree(mbtree.nodelist_by_depth[6][0].parent, maxdepth=9)
```
</details>

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4d6e5444-a0d8-9d30-0c18-9c3a0e5ef420.png" width="350">

### 描画するノードの絞り込み

この問題は、`startnode` の __兄弟ノードに対してまで、深さ 9 までのノードを描画__ しているためにおきるので、__兄弟ノードの場合はその子ノードを描画しない__ という工夫をすることで、描画する Figure の画像の縦幅を大幅に削減することができます。例えば、深さ 6 のノードから深さ 9 までの部分木を `draw_tree` で描画する場合は、下図のように描画します。

図の赤い丸が `startnode` で、水色の枠のノードが `startnode` の兄弟ノードです。先ほどの画像と比べて Figure の縦幅は __水色の兄弟ノードの分だけしか増えない__ ので、Figure の縦幅が大幅に短くなります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/54aaaa70-8ec1-0d7c-90a7-67ec4e2e5395.png" width="300">

:::note
このような工夫で Figure の縦幅が大幅に減るのは、__縦幅を計算する式__ が、__掛け算__ で行われるのと __足し算__ で行われることによる違いが原因です。

わかりづらいと思いますので、具体例を挙げて説明します。

__深さ 2 のノードから深さ 3 まで__ の部分木を描画する場合は、深さ 2 のノードには合法手が 7 つ存在するので、Figure には __縦に 7 つ分__ のゲーム盤が描画されます。

深さ 2 のノードの親ノードである、__深さ 1 のノードから深さ 3 まで__ の部分木を描画する場合は、下記から Figure には __縦に 8 * 7 = 56 個分__ のゲーム盤が描画されます。

* 深さ 1 のノードはそれぞれ合法手を 8 つ持つ
* 深さ 2 のノードはそれぞれ合法手を 7 つ持つ

深さ 2 のノードの __兄弟ノードだけを追加して描画__ する場合は、兄弟ノードの数である __7 個分のゲーム盤を縦に追加して描画__ する必要があるので、Figure には __縦に 7 + 7 = 14 個分__ のゲーム盤が描画されます。

下記の性質から、特に浅いノードを `draw_tree` で描画する場合は Figure の縦幅に大幅な差が生じることになります。

* 深さが浅いほど合法手の数が増える
* 足し算と掛け算では数が大きい程、計算結果に大きな差が生じる
:::

### Figure の縦幅の計算

この方針で Figure を描画するためには、__Figure の縦幅のサイズを計算__ する必要があります。どのようにして計算すればよいかについて少し考えてみて下さい。

下図の __赤枠の部分__ は、__元々描画されていた部分木__ で、この部分の __縦幅は `startnode` の `height` 属性に代入__ されています。また、__水色の矢印の長さ__ は __`兄弟ノードの数 * 4`__ で計算できます。兄弟ノードの数は、「`startnode` の親ノードの子ノードの数 - 1」なので、`len(startnode.parent.children) - 1` という式で計算することができます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c1daf62c-4557-ebf5-c7e4-5c6926085f20.png" width="300">

従って、Figure の縦幅の計算は下記のプログラムで計算することができます。ただし、このプログラムには一つ重要な問題があります。それが何かについて少し考えてみて下さい。

```python
height = startnode.height + (len(startnode.parent.children) - 1) * 4
```

問題は __`startnode` がルートノードの場合__ に発生します。その場合は、__`startnode.parent` に `None` が代入__ されているので、__`startnode.parent.children`__ を計算しようとすると __エラーが発生__ します。従って、高さの計算は下記のプログラムのように、__`startnode.height` を基準__ とし、__親ノードが存在する場合だけ増やす__ ように記述する必要があります。

```python
height = startnode.height
parent = startnode.parent
if parent is not None:
    height += (len(parent.children) - 1) * 4
```

下記は、そのように `draw_tree` を修正するプログラムです。なお、下記のプログラムでは、`parent` という変数に `startnode` の親ノードを代入しました。そこで、以後は __`startnode` の親ノードの事を `parent` と表記する__ ことにします。

* __7 ~ 9 行目__：親ノードが存在する場合だけ、高さを増やす

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

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

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

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

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように Figure の縦幅が、`startnode` の兄弟ノードの分だけ増えることが確認できます。

```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/6e5292ce-c147-39e5-f239-b36497ed5af9.png" width="400">

### 親ノードの描画処理の修正

次に、`startnode` の親ノードである __`parent`__ と、`parent` の子ノードへの __エッジの描画__ を行う処理を実装することにします。`parent` に対しては、__その子ノードへのエッジをすべて描画__ する必要があり、その処理は __`draw_node`__ で行うことができます。

ただし、その際に __`startnode` の兄弟ノード__ は子ノードが存在しているかどうかに関わらず、__高さを 4 で描画する必要がある__ 点を忘れないようにして下さい。また、__`parent` の高さ__ は、`startnode.height` ではなく、`startnode.height` に __兄弟ノードの高さを加えた値にする__ 必要がある点にも注意が必要です。

これらを忘れると、先程の __先祖ノードの描画の高さと `height` 属性の値が異なっていた__ ため、__先祖ノードが描画されなかったバグ__ と同じ理由で `parent`が Figure の表示範囲内に描画されなくなったり、エッジがおかしな位置に描画されるようになります。

兄弟ノードの `height` 属性に 4 を代入する処理は、`parent` の __`children` 属性に対する繰り替えし処理__ で行いますが、その際に `children` 属性の要素に含まれる __`startnode` の `height` 属性を `4` に変更してはいけない__ 点に注意が必要です。Python では __同一のオブジェクトであるかの判定__ は `==` 演算子ではなく、__`is` 演算子__ を使って行う必要があります。同様にオブジェクトが __同一でない事の判定__ は `!=` 演算子ではなく __`is not` 演算子__ を使って行います。これらの違いについては[以前の記事](https://qiita.com/ysgeso/items/ea147c436e357281f441#none-%E3%81%AE%E5%88%A4%E5%AE%9A%E3%81%A8isis-not-%E6%BC%94%E7%AE%97%E5%AD%90)を参照して下さい。

上記から、`parent` のエッジの描画処理は、下記のプログラムのように `draw_tree` を修正することで実装することができます。

* __10 行目__：親ノードが存在する場合は、親ノードの高さを Figure と同じサイズにする
* __12 ~ 17 行目__：親ノードが存在する場合に、親ノードを描画する処理を行う
* __13 ~ 15 行目__：`startnode` のそれぞれの兄弟（sibling）ノードの高さを `4` にする。ただし、`startnode` の高さを変えてはいけないので、14 行目でその判定を行う
* __16、17 行目__：親ノードの描画を行う。`startnode` の兄弟ノードへのエッジをすべて描画する必要があるので、キーワード引数 `maxdepth` を省略したり、`parent.depth` を代入してはいけない点に注意すること。なお、`maxdepth` には `startnode` の深さよりも大きな値が代入されているはずなので、 `maxdepth=maxdepth` を記述することで、`startnode` の深さと異なる値を設定することができる 
* __19 ~ 24 行目__：親ノードの先祖ノードを描画する。__親ノードは描画済__ なので、親ノードの親ノードから描画を行うようにするために19 行目では __`node`__ に `startnode` ではなく、__`parent` を代入__ するように修正した

```python
 1  def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
 2      if startnode is None:
 3          startnode = self.root
 4      self.calc_node_height(maxdepth)
 5      width = 5 * (maxdepth + 1)
 6      height = startnode.height
 7      parent = startnode.parent
 8      if parent is not None:
 9          height += (len(parent.children) - 1) * 4
10          parent.height = height
11      fig, ax = plt.subplots(figsize=(width * size, height * size))
元と同じなので省略      
12      if parent is not None:
13          for sibling in parent.children:
14              if sibling is not startnode:
15                  sibling.height = 4
16          dx = 5 * parent.depth
17          parent.draw_node(ax, maxdepth=maxdepth, size=size, lw=lw, dx=dx, dy=0)
18       
19          node = parent
20          while node.parent is not None:
21              node = node.parent
22              node.height = startnode.height
23              dx = 5 * node.depth
24              node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
25    
26  Mbtree.draw_tree = draw_tree
```

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

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

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

```diff_python
def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
    if startnode is None:
        startnode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth + 1)
    height = startnode.height
    parent = startnode.parent
    if parent is not None:
        height += (len(parent.children) - 1) * 4
+       parent.height = height
    fig, ax = plt.subplots(figsize=(width * size, height * size))
元と同じなので省略
+   if parent is not None:
+       for sibling in parent.children:
+           if sibling is not startnode:
+               sibling.height = 4
+       dx = 5 * parent.depth
+       parent.draw_node(ax, maxdepth=maxdepth, size=size, lw=lw, dx=dx, dy=0)
       
-   node = startnode
+       node = parent
-   while node.parent is not None:
-           node = node.parent
-           node.height = startnode.height
-           dx = 5 * node.depth
-           node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
+       while node.parent is not None:
+           node = node.parent
+           node.height = startnode.height
+           dx = 5 * node.depth
+           node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
    
Mbtree.draw_tree = draw_tree
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果のように `parent` が Figure の上下の真ん中に描画され、`parent` のエッジが描画されるようになります。

```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/c3680bb4-f972-48af-db42-674ef5dc789a.png" width="400">

### 親ノードの先祖ノードの描画位置の修正と、兄弟ノードの描画

先程のプログラムには、上図のように、__親ノードの先祖ノードの描画位置__ と、__兄弟ノードが描画されない__ という問題があります。

親ノードの先祖ノードの描画位置がおかしいのは、__Figure の高さが変化した__ にも関わらす、それらのノードの __`height` 属性に `startnode` の `height` 属性を代入__ しているからなので、__Figure の高さを表す `height` を代入__ することで修正することができます。

兄弟ノードの描画は、__兄弟ノードの高さに `4` を代入する際__ に、__`draw_node` を使って描画__ すると良いでしょう。兄弟ノードに子ノードが存在する場合は __1 本だけエッジを描画する__ 必要があるので、キーワード引数 __`maxdepth` に兄弟ノードの深さを代入__ して呼び出します。

なお、その際に __`startnode` を描画__ してしまうと、`startnode` を __2 回描画する__ ことになる点に注意して下さい。ただし、9 行目の、__次の兄弟ノードの描画位置の y 座標を計算する処理__ は、__`startnode` に対しても行う必要がある__ 点にも注意が必要です。

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

* __3 行目__：兄弟ノードの描画位置の y 座標を表す `dy` を `0` で初期化する
* __7 行目__：兄弟ノードの描画位置の x 座標を計算する
* __8 行目__：キーワード引数 __`maxdepth` に兄弟ノードの深さを代入__ して呼び出すことで、子ノードが存在した場合に __エッジを 1 本だけ描画する__ ように兄弟ノードを描画する
* __9 行目__：__次の兄弟ノードの描画位置__ を __`sibling.height` だけ下にずらす__。なお、この処理は `sibling` に __`startnode` が代入されている場合でも行う必要がある__ ため、5 行目の __if 文のブロックの外に記述__ する必要がある点に注意すること
* __16 行目__：親ノードの先祖ノードの高さに Figure の高さを代入するように修正する

```python
 1  def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
 2      if parent is not None:
 3          dy = 0
 4          for sibling in parent.children:
 5              if sibling is not startnode:
 6                  sibling.height = 4
 7                  dx = 5 * sibling.depth
 8                  sibling.draw_node(ax, maxdepth=sibling.depth, size=size, lw=lw, dx=dx, dy=dy)
 9              dy += sibling.height
10          dx = 5 * parent.depth
11          parent.draw_node(ax, maxdepth=maxdepth, size=size, lw=lw, dx=dx, dy=0)
12       
13          node = parent
14          while node.parent is not None:
15              node = node.parent
16              node.height = height
17              dx = 5 * node.depth
18              node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
19    
20  Mbtree.draw_tree = draw_tree
```

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

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

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

```diff_python
def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
    if parent is not None:
+       dy = 0
        for sibling in parent.children:
            if sibling is not startnode:
                sibling.height = 4
+               dx = 5 * sibling.depth
+               sibling.draw_node(ax, maxdepth=sibling.depth, size=size, lw=lw, dx=dx, dy=dy)
+           dy += sibling.height
        dx = 5 * parent.depth
        parent.draw_node(ax, maxdepth=maxdepth, size=size, lw=lw, dx=dx, dy=0)
       
        node = parent
        while node.parent is not None:
            node = node.parent
-           node.height = startnode.height
+           node.height = height
            dx = 5 * node.depth
            node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
    
Mbtree.draw_tree = draw_tree
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果のように親ノードの先祖ノードと、兄弟ノードが正しく描画されることが確認できます。なお、このプログラムには重大なバグがあります。それが何かについて少し考えてみて下さい。

```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/562f315d-ccfa-14bc-bb87-f1f70f67260b.png" width="400">

### `startnode` の描画位置のバグの検証と修正

そのバグは、下記のプログラムの実行結果ように、__`startnode`__ が、親ノードの子ノードの __先頭のノードでない場合__ は、__`startnode` の描画位置がおかしくなる__ というものです。具体的には、下記の場合は `startnode` とその子孫の部分木が上にずれて描画されています。このようなことが起きる原因について少し考えてみて下さい。

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

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

```diff_python
-mbtree.draw_tree(mbtree.nodelist_by_depth[6][0], maxdepth=9)
+mbtree.draw_tree(mbtree.nodelist_by_depth[6][1], maxdepth=9)
```
</details>

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8a35d5ec-fd12-3a01-301b-5555db362fb6.png" width="400">

このバグの原因は、下記のプログラムの 4 行目のように、`startnode` とその子孫の部分木を描画する y 座標の基準を表す `dy` に、Figure の上端を表す `0` に設定しているからです。

```python
    nodelist = [startnode]
    depth = startnode.depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
```

__`startnode` とその子孫の部分木__ は、`startnode` が親ノードの __何番目の子ノードであるか__ によって、__下にずらして描画する必要があります__。具体的には __`startnode` より前に兄弟ノードが存在する場合__ は、__その数 * 4 だけ下にずらして描画__ する必要があります。上図の場合は、`startnode` の前に一つ兄弟ノードが存在するので 4 だけずらす必要があります。

ずらす量は、`startnode` が `parent` の `children` 属性の __`i` 番のインデックスの要素に代入__ されている場合は、__`i * 4`__ という式で計算できます。例えば `0` 番のインデックスの要素に代入されている場合は、`startnode` より前に兄弟ノードは存在しないので `0 * 4 = 0` で、ずらす必要はありません。2 番のインデックスの要素に代入されている場合は、`startnode` より前に 2 つ兄弟ノードが存在するので `2 * 4 = 8` だけずらす必要があります。

list などの[シーケンス型](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#%E3%82%B7%E3%83%BC%E3%82%B1%E3%83%B3%E3%82%B9%E5%9E%8B%E3%81%A8%E3%81%AF%E4%BD%95%E3%81%8B)には、実引数で指定したオブジェクトが、__list の何番のインデックスの要素に代入されているか__ を計算する、__`index`__ というメソッドがあるので、それを利用することで、下記のプログラムのように `draw_tree` を修正することができます。

* __6、7 行目__：親ノードが存在する場合、`dy` に `startnode` が代入されている `parent.children` のインデックス * 4 を計算して代入する

```python
1  def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
2      nodelist = [startnode]
3      depth = startnode.depth
4      while len(nodelist) > 0 and depth <= maxdepth:        
5          dy = 0
6          if parent is not None:
7              dy = parent.children.index(startnode) * 4
元と同じなので省略
8    
9  Mbtree.draw_tree = draw_tree
```

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

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

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

```diff_python
def draw_tree(self, startnode=None, size:float=0.25, lw:float=0.8, maxdepth=2):
元と同じなので省略
    nodelist = [startnode]
    depth = startnode.depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        if parent is not None:
            dy = parent.children.index(startnode) * 4
元と同じなので省略
    
Mbtree.draw_tree = draw_tree
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果のように `startnode` とその子孫の部分木が正しい位置に描画されるようになることが確認できます。

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

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/16201b73-04f1-efcf-c2cb-c527cf4e7cbf.png" width="400">

シーケンス型の `index` メソッドの詳細に関しては、下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/library/stdtypes.html#common-sequence-operations

# 今回の記事のまとめ

今回の記事では、ゲーム木全体の視覚化を行うために必要となる、ゲーム木の部分木の表示範囲の改良を行いました。次回の記事で、ゲーム木全体の視覚化の処理を実装する予定です。

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

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

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

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

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

# 次回の記事

https://qiita.com/ysgeso/items/2acd8c5ceb8e9cda7233

[^1]:ややこしいですが、親の子なので、自分自身、すなわちルートノードの事を表します