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

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/7cd67869855550d222f5

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

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

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

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

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

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

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

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

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

# 木構造のデータを作成する 2 つのアルゴリズム

[前回の記事](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E6%9C%A8%E6%A7%8B%E9%80%A0tree-structure)で説明した __ゲーム木を作成する主なアルゴリズム__ には、__幅優先__ と __深さ優先__ という 2 種類があります。今回の記事ではそのうちの幅優先アルゴリズムについて説明します。なお、深さ優先アルゴリズムに関しては今後の記事で紹介します。

:::note
幅優先と深さ優先という用語は、主に木構造などの __グラフ構造のデータを分析__ する際に用いられる「幅優先探索」、「深さ優先探索」という __探索のアルゴリズムの名前__ で使われます。木構造を作成する際のアルゴリズムに「幅優先」、「深さ優先」という用語が使われているのはあまり見たことがないのですが、行う処理は探索のアルゴリズムと同様なので、本記事ではゲーム木を作成する際のアルゴリズムを「幅優先アルゴリズム」のように表記することにします。

なお、ゲーム木を分析する探索のアルゴリズムに関してはこの後で紹介します。
:::

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

__幅優先__（breadth first）アルゴリズムは、ゲーム木のノードに対して、ノードの __深さの浅い順番__ で、__子ノードを作成する__ というものです。

具体的には下記のような手順でゲーム木を作成します。

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

[前回の記事](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E6%9C%A8%E6%A7%8B%E9%80%A0tree-structure)で説明したように、〇×ゲーム木の __ノードの深さ__ は、__局面の手数を表します__。上記のアルゴリズムでは、__0 手目の局面から順番に、子ノードの作成__ を行いますが、〇×ゲームは必ず 9 手目までで決着がつくので、具体的には、以下のような処理が行われます。

1. ゲーム開始時の 0 手目の局面の子ノードを計算する
2. 1 手目のすべての局面の子ノードを計算する
3. 2 手目のすべての局面の子ノードを計算する
4. 3 手目のすべての局面の子ノードを計算する
略 
4. 9 手目のすべての局面の子ノードを計算する

前回の記事では、〇×ゲームのゲーム木のノードを表す __Node__ という __クラスを定義__ し、ノードの __子ノードを計算する `calc_childnode` というメソッドを定義__ しました。__幅優先アルゴリズム__ では、このメソッドを利用することでゲーム木を作成することができます。

:::note
幅優先アルゴリズムでは、ゲーム木のノードを、深さが浅い順に作成します。そのため、ゲーム木のノードを、深さが浅い順に __縦方向に表現した場合__ に、横一列に並んだ同じ深さのノードが上から順番に作成されていくことになります。この様子が、__横幅（breadth）の方向を優先__ してゲーム木が作られるように見えるため、__幅優先__ いう名前が付けられました。

上記の説明でピンとこない人がいるかもしれませんので、幅優先アルゴリズムでゲーム木がどのように作られていくかについては、今後の記事で視覚化する予定です。
:::

## ゲーム木を表すクラスの定義

まず、〇×ゲームのゲーム木を表す __`Mbtree`__[^1] という __クラスを定義__ することにします。ゲーム木はゲーム開始時の局面をルートノードとして持つので、__`root`__ という属性にルートノードを表す Node クラスのインスタンスを代入することにします。

なお、ノードを表すデータを、Node クラスのインスタンスと表記するのは冗長なので、以後は単に、「`root` 属性にノードを代入する」のように表記することにします。


下記は、`Mbtree` クラスの定義を表すプログラムで、インスタンスを作成する際に、`root` 属性にゲームの開始時の局面を表すノードを作成して代入しています。

* __6 行目__：下記の処理で、ゲームの開始時の局面を表すノードを `root` 属性に代入する
    * Marubatsu クラスのインスタンスを作成する
    * Marubatsu クラスのインスタンスを表す Node クラスのインスタンスを作成する

```python
1  from marubatsu import Marubatsu
2  from tree import Node
3
4  class Mbtree:
5      def __init__(self):
6          self.root = Node(Marubatsu())
```

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

```python
from marubatsu import Marubatsu
from tree import Node

class Mbtree:
    def __init__(self):
        self.root = Node(Marubatsu())
```
</details>


下記のプログラムは、`MbTree` のインスタンスを作成し、ルートノードの局面を表示するプログラムで、実行結果のようにゲーム開始時の局面が表示されます。

```python
mbtree = Mbtree()

print(mbtree.root.mb)
```

実行結果

```
Turn o
...
...
...
```

## 幅優先アルゴリズムによるゲーム木を作成するメソッドの定義 その 1

次に、Mbtree クラスに、幅優先アルゴリズムでゲーム木を作成する、下記のようなメソッドを定義します。

__名前__：__`create_tree_by_bf`__[^2] という名前にする
__処理__：幅優先アルゴリズムによってゲーム木を作成する
__入力__：なし
__出力__：なし

今回の記事では、初心者が思いつきそうな幅優先アルゴリズムによるゲーム木を作成する方法を紹介し、__その方法では深いゲーム木を作成する場合はうまくいかない__ ことを示します。深いゲーム木を幅優先アルゴリズムで作成する方法については、次回の記事で説明します。

### 深さ 1 のノードの作成

いきなり深いゲーム木を作成するのは大変なので、__深さ 1 のノードから順番__ に、作成するゲーム木の __ノードの深さを 1 つずつ増やしながら__ ゲーム木を作成していくことにします。

深さ 1 のノードは、[前回の記事](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E5%AD%90%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9) で行った、__ルートノードの子ノードを計算する処理__ によって行えます。そこで、`create_tree_by_bf` にその処理を、下記のプログラムのように記述することにします。なお、この処理は、__1 手目の局面__ のノードをゲーム木に追加する処理で、__深さ 1 のゲーム木を作成__ することができます。

```python
def create_tree_by_bf(self):
    self.root.calc_children()

Mbtree.create_tree_by_bf = create_tree_by_bf
```

また、下記のプログラムの 3 行目のように、`__init__` メソッドの中で `create_tree_by_bf` を呼び出すようにすることで、Mbtree クラスの __インスタンスを作成した際__ に、__深さ 1 のゲーム木を作成__ するようにすることができます。

```python
1  def __init__(self):
2      self.root = Node(Marubatsu())
3      self.create_tree_by_bf()
4
5  Mbtree.__init__ = __init__
```

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

```python
def __init__(self):
    self.root = Node(Marubatsu())
    self.create_tree_by_bf()

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

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

```diff_python
def __init__(self):
    self.root = Node(Marubatsu())
+   self.create_tree_by_bf()

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

上記の修正後に、下記のプログラムを実行することで、実行結果のように、ルートノードの子ノードが計算されたことが確認できます。

```python
mbtree = Mbtree()
mbtree.root.draw_node()
```

実行結果（見やすいように、実際に表示される画像よりも小さく画像を表示しています）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/da49cdf3-6a01-ca95-4b00-fbb735a84b29.png" width="70">

### 深さ 2 のノードの作成

深さ 2 のノードの作成は、深さ 1 の全てのノードに対して `calc_children` を呼び出すことで作成できるので、下記のプログラムの 5、6 行目ように記述できます。

```python
1  def create_tree_by_bf(self):
2      # 深さ 1 のノードの作成
3      self.root.calc_children()
4      # 深さ 2 のノードの作成
5      for childnode in self.root.children:
6          childnode.calc_children()
7
8  Mbtree.create_tree_by_bf = create_tree_by_bf
```

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

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

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

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

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

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

上記の修正後に、下記のプログラムを実行することで、実行結果のように、深さ 1 のノードの最初のノードを表す `mbtree.root.children[0]` の子ノードが計算されたことが確認できます。なお、__ゲーム木を作成する処理を修正__ したので、1 行目のように、Mbtree クラスの __インスタンスを作り直す必要がある__ 点に注意して下さい。

```python
mbtree = Mbtree()
mbtree.root.children[0].draw_node()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/178e88c0-879f-c434-c224-2ccceb2caeaf.png" width="70">

## 深さ 2 のゲーム木の視覚化

上記では、深さ 1 のノードの中の、最初の 1 つのノードだけを視覚化しましたが、これでは __全体像が見えない__ ので、深さ 2 のゲーム木の __全体を視覚化__ することにします。

まず、Mbtree クラスにゲーム木を視覚化する下記のメソッドを定義する事にします。

__名前__：ゲーム木を描画するので `draw_tree` という名前にする
__処理__：ゲーム木のすべてのノードを描画する
__入力__：なし
__出力__：なし

### 深さ 1 のノードまでのゲーム木の描画

まず、ルートノードから深さ 1 までのゲーム木を描画する処理を記述することにします。深さ 1 までのゲーム木の描画は、__ルートノードとその子ノードの関係を描画すればよい__ ので、下記のプログラムの 3 行目のように、ルートノードに対して、[前回の記事](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E6%8F%8F%E7%94%BB%E3%81%99%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85)で定義した `draw_node` メソッドを呼び出すことで描画することができます。

```python
1  def draw_tree(self):
2      # 深さが 0 のノードとその子ノードの関係を描画する
3      self.root.draw_node()
4
5  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self):
    # 深さが 0 のノードとその子ノードの関係を描画する
    self.root.draw_node()

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

上記を実行後に、下記のプログラムを実行することで、実行結果のように、ルートノードと子ノードの関係が描画され、__深さ 1 までのゲーム木が描画されます__。なお、先程と異なり、ゲーム木の作成の処理は変更していないので、Mbtree クラスのインスタンスを作成し直す必要はありません。

```python
mbtree.draw_tree()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/da49cdf3-6a01-ca95-4b00-fbb735a84b29.png" width="70">

### 深さ 2 のノードまでのゲーム木の描画に対する考察

深さ 2 のノードまでのゲーム木を描画するためには、__それぞれのノードをどの位置に描画するか__ を計算する必要があります。その計算方法を考えるためには、前回の記事と同様に、深さ 2 までのゲーム木を __実際にノートなどに書いてみる__ ことをお勧めします。

下記は、筆者が考えた深さ 2 までのゲーム木の視覚化の図です。

<details><summary><strong>深さ 2 までのゲーム木の図（クリックして表示して下さい）</strong></summary>

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/560b7b9e-d307-7203-1a69-7d1e52c03749.png" width="70">

</details>

下図は、上図の一部を拡大したものです。赤丸で示した、深さ 1 の最初のノードと、その子ノードの関係の部分は、__`draw_node`__ で描画される画像と比べると、__描画する位置が異なるだけ__ なので、__`draw_node` とほぼ同じ方法で描画できそう__ です。これは、__他の深さ 1 のノードとその子ノードの関係も同様__ です。そこで、最初に深さ 1 のノードとその子ノードの関係を描画する処理を記述することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/15cac0d1-3b02-e893-ba18-5beffb300b56.png" width="150">

### 任意の座標に描画できるようにするための `draw_node` の修正

まず、`draw_node` に、[前回の記事](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E3%82%B2%E3%83%BC%E3%83%A0%E7%9B%A4%E3%82%92%E4%BB%BB%E6%84%8F%E3%81%AE%E5%A0%B4%E6%89%80%E3%81%AB%E6%8F%8F%E7%94%BB%E3%81%99%E3%82%8B%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9)で `draw_board` を修正した場合と同様の方法で、仮引数 `dx`、`dy` を追加して、__任意の Axes の座標__ にノードとその子ノードの関係を __描画できるように修正__ することにします。下記は `draw_node` を修正したプログラムです。

* __4 行目__：デフォルト値を `0` とするデフォルト引数 `dx`、`dy` を追加する
* __6 ~ 11 行目__：x 座標を表す部分に `dx` を、y 座標を表す部分に `dy` を加算することで、__すべての描画を (dx, dy) の分だけずらして行う__

```python
 1  import matplotlib.pyplot as plt
 2  from marubatsu import Marubatsu_GUI
 3
 4  def draw_node(self, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
 5      # 自分自身のノードを (dx, dy) に描画する
 6      Marubatsu_GUI.draw_board(ax, self.mb, lw=lw, dx=dx, dy=dy)
 7      plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + height - 4], c="k", lw=lw)
 8      # i 番の子ノードを (dx + 5, dy + i * 4) に描画する
 9      for i, childnode in enumerate(self.children):
10          Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy+i*4, lw=lw)
11          plt.plot([dx + 4 , dx + 4.5], [dy + 1.5 + i * 4, dy + 1.5 + i * 4], c="k", lw=lw)
12
13 Node.draw_node = draw_node
```

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

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

def draw_node(self, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    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")
    
    # 自分自身のノードを (dx, dy) に描画する
    Marubatsu_GUI.draw_board(ax, self.mb, lw=lw, dx=dx, dy=dy)
    plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + height - 4], c="k", lw=lw)
    # i 番の子ノードを (dx + 5, dy + i * 4) に描画する
    for i, childnode in enumerate(self.children):
        Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy+i*4, lw=lw)
        plt.plot([dx + 4 , dx + 4.5], [dy + 1.5 + i * 4, dy + 1.5 + i * 4], c="k", lw=lw)
        
Node.draw_node = draw_node
```
</details>

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

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

-def draw_node(self, size=0.25, lw=0.8):
+def draw_node(self, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
    # 自分自身のノードを (dx, dy) に描画する
-   Marubatsu_GUI.draw_board(ax, self.mb, lw=lw)
+   Marubatsu_GUI.draw_board(ax, self.mb, lw=lw, dx=dx, dy=dy)
-   plt.plot([3.5, 4, 4], [1.5, 1.5, 1.5 + height - 4], c="k", lw=lw)
+   plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + height - 4], c="k", lw=lw)
    # i 番の子ノードを (dx + 5, dy + i * 4) に描画する
    for i, childnode in enumerate(self.children):
-       Marubatsu_GUI.draw_board(ax, childnode.mb, dx=5, dy=i*4, lw=lw)
+       Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy+i*4, lw=lw)
-       plt.plot([4 , 4.5], [1.5 + i * 4, 1.5 + i * 4], c="k", lw=lw)
+       plt.plot([dx + 4 , dx + 4.5], [dy + 1.5 + i * 4, dy + 1.5 + i * 4], c="k", lw=lw)
        
Node.draw_node = draw_node
```
</details>

### `draw_node` での Figure の作成処理に関する修正

`draw_node` で任意の座標に描画を行うことができるようになりましたが、`draw_node` は __Figure を作成する処理を行っている__ ので、__`draw_node` を実行するたび__ に、__別々の Figure が作成されてしまいます__。そこで、以下のように `draw_node` を修正することにします。

* ゲーム木を描画する Figure、Axes は、ゲーム木を描画する __`draw_tree` メソッドで作成__ し、`draw_node` を呼び出す際に __実引数で Axes の値を指定__ する。そのために、`draw_node` に、描画を行う Axes を代入する __仮引数 `ax` を追加__ する
* ただし、__1 つのノードだけを `draw_node` で描画する場合__ はこれまで通り `draw_node` で __Figure を作成したほうが便利__ なので、仮引数 __`ax`__ をデフォルト値が `None` のデフォルト引数とし、__`None` が代入されている場合のみ `Figure` を作成__ する処理を行うようにする

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

* __1 行目__：デフォルト値を `None` とするデフォルト引数 `ax` を追加する
* __4 ~ 9__：`ax` に `None` が代入されている場合のみ、Figure を作成するように修正する

```python
 1  def draw_node(self, ax=None, size=0.25, lw=0.8, dx=0, dy=0):
 2      width = 8
 3      height = len(self.children) * 4
 4      if ax is None:
 5          fig, ax = plt.subplots(figsize=(width * size, height * size))
 6          ax.set_xlim(0, width)
 7          ax.set_ylim(0, height)   
 8          ax.invert_yaxis()
 9          ax.axis("off")
元と同じなので省略
10
11  Node.draw_node = draw_node
```

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

```python
def draw_node(self, ax=None, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    height = len(self.children) * 4
    if ax is None:
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")
    
    # 自分自身のノードを (dx, dy) に描画する
    Marubatsu_GUI.draw_board(ax, self.mb, lw=lw, dx=dx, dy=dy)
    plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + height - 4], c="k", lw=lw)
    # i 番の子ノードを (dx + 5, dy + i * 4) に描画する
    for i, childnode in enumerate(self.children):
        Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy+i*4, lw=lw)
        plt.plot([dx + 4 , dx + 4.5], [dy + 1.5 + i * 4, dy + 1.5 + i * 4], c="k", lw=lw)
        
Node.draw_node = draw_node
```
</details>

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

```diff_python
-def draw_node(self, size=0.25, lw=0.8, dx=0, dy=0):
+def draw_node(self, ax=None, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    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")
+   if ax is None:
+       fig, ax = plt.subplots(figsize=(width * size, height * size))
+       ax.set_xlim(0, width)
+       ax.set_ylim(0, height)   
+       ax.invert_yaxis()
+       ax.axis("off")
元と同じなので省略
        
Node.draw_node = draw_node
```
</details>

実行結果は先ほどの `mbtree.draw_tree()` と同じなので省略しますが、上記の修正後に、下記のプログラムを実行することで、`draw_board` に __キーワード引数 `ax`、`dx`、`dy` を記述しなかった場合__ に、__これまでと同じ処理が行われる__ ことが確認できます。

```python
mbtree.root.draw_node()
```

### 深さ 1 のノードの描画位置の計算

次に、深さ 1 のそれぞれのノードの描画位置を計算する必要があります。どのように計算すればよいかについて少し考えてみて下さい。

下図は、深さ 1 の上 2 つのノードの左上の点の座標を表したものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/036a0592-c847-2ef7-02c8-c453392f97b0.png" width="150">

深さ 1 のノードの x 座標は、[前回の記事](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E5%90%84%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E3%82%B2%E3%83%BC%E3%83%A0%E7%9B%A4%E3%82%92%E6%8F%8F%E7%94%BB%E3%81%99%E3%82%8B%E5%BA%A7%E6%A8%99%E3%81%AE%E8%A8%88%E7%AE%97)でゲーム盤とゲーム盤の横の間隔を 2 としたので、ゲーム盤の幅である 3 を加えて 3 + 2 = 5 になります。

深さ 1 の 2 番目のノードの y 座標は、図から深さ 1 の 1 番目のノードの __右に 8 つの子ノードを描画する必要がある__ ので、1 番目のノードの __8 つ下に描画__ する必要があります。ゲーム盤とゲーム盤の縦の間隔を 1 としたので、その座標は 8 × (3 + 1) = 8 × 4 = 32 となります。

__深さ 1 のノード__ は、__いずれも 8 つの子ノードを持つ__ ので、それぞれのノードは縦方向に __等間隔に並び__、深さ 1 の __i 番のインデックス__ のノードの座標は __(5, i * 32)__ となります。

### 深さ 1 のノードの描画

Figure を作成する処理は、先程説明したように、ゲーム木を描画する `draw_tree` の中に記述します。その際に、__ゲーム木全体を描画__ することができる __大きさの Figure を作成__ する必要があります。その大きさを計算する方法について少し考えてみて下さい。

Figure の横方向の大きさは、ゲーム盤の横幅が 3 でゲーム盤の間隔が 2 なので __深さが 1 あたり 5__ が必要になります。そのため、深さが 0、1、2 の __3 つの深さ__ のノードを描画する場合は 3 + 2 + 3 + 2 + 3 = 13 であることがわかります。なお、横幅は描画する __深さの数を d__ とすると「__5 * d - 2__」で計算できます。

縦方向の大きさは、「深さ 2 のノードの総数 * (3 + 1)」になります。〇×ゲームは 1 手目で 9 通り、2 手目で 8 通りの着手を行えるので、深さ 2 のノードの数は 9 * 8 = 72 になります。従って、縦幅は 72 * 4 = 288 になります。

上記から、深さ 1 のノードを描画する処理は、下記のプログラムのように記述できます。なお、Figure の大きさと線の太さを調整できるように、`draw_node` と同様の仮引数 `size` と `lw` を追加しました。また、すべての内容が変更されているので修正箇所は省略します。

* __1 行目__：`draw_node` と同じ設定の仮引数 `size` と `lw` を追加する
* __2、3 行目__：Figure の画像の幅と高さを変数に代入する
* __4 ~ 8 行目__：`draw_node` と同じ方法で Figure を作成する
* __10、11 行目__：ルートノードのそれぞれの i 番のインデックスの子ノードに対して、__[`enumerate`](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-enumerate)__ を使って (5, i * 32) の位置に `draw_node` でそのノードと子ノードの関係を描画する

```python
 1  def draw_tree(self, size=0.25, lw=0.8):
 2      width = 13
 3      height = 288
 4      fig, ax = plt.subplots(figsize=(width * size, height * size))
 5      ax.set_xlim(0, width)
 6      ax.set_ylim(0, height)   
 7      ax.invert_yaxis()
 8      ax.axis("off")        
 9       
10      for i, childnode in enumerate(self.root.children):
11          childnode.draw_node(ax=ax, size=size, lw=lw, dx=5, dy=i*32)
12
13  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, size=0.25, lw=0.8):
    width = 13
    height = 288
    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 i, childnode in enumerate(self.root.children):
        childnode.draw_node(ax=ax, size=size, lw=lw, dx=5, dy=i*32)

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

上記の修正後に、下記のプログラムを実行することで、実行結果のように、深さ 1 のノードと子ノードの関係が描画されます。

```python
mbtree.draw_tree()
```

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

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3dbedf10-bbdc-2894-d813-683359bd6a26.png" width="150">

</details>

### 深さ 0 のノードの描画処理を行う際に必要な計算の考察

`draw_node` では、下記のプログラムの 3 行目のように、__i 番の子ノード__ を、__(dx, dy) を基準__ とした座標から、__(5, i * 4)__ の座標に描画しています。これは、4 行目の __エッジを表す横線__ を描画する処理も同様です。

```python
    # 深さ 1 のノードの i 番の子ノードを (dx + 5, dy + i * 4) に描画する
    for i, childnode in enumerate(self.children):
        Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy+i*4, lw=lw)
        plt.plot([dx + 4 , dx + 4.5], [dy + 1.5 + i * 4, dy + 1.5 + i * 4], c="k", lw=lw)
```

これは、深さ 1 のノードを描画する際は正しいのですが、__深さ 0__ のノードの __i 番のインデックスの子ノード__ の __y 座標__ は、先程説明したように、dy を基準とした座標から __i * 32__ の座標になります。そのため、`draw_node` の中の処理で、深さが 0 の子ノードを描画する際には、下記のプログラムの 3 行目のように、y 座標を `dy + i * 4` ではなく、__`dy + i * 32`__ にする必要があります。これは、4 行目のエッジを表す横線を描画する処理も同様です。

```python
    # 深さ 0 のノードの i 番の子ノードを (dx + 5, dy + i * 32) に描画する
    for i, childnode in enumerate(self.children):
        Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy+i*32, lw=lw)
        plt.plot([dx + 4 , dx + 4.5], [dy + 1.5 + i * 32, dy + 1.5 + i * 32], c="k", lw=lw)
```

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

```diff_python
    # 深さ 0 のノードの i 番の子ノードを (dx + 5, dy + i * 32) に描画する
    for i, childnode in enumerate(self.children):
+       Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy+i*4, lw=lw)
+       Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy+i*32, lw=lw)
-       plt.plot([dx + 4 , dx + 4.5], [dy + 1.5 + i * 4, dy + 1.5 + i * 4], c="k", lw=lw)
+       plt.plot([dx + 4 , dx + 4.5], [dy + 1.5 + i * 32, dy + 1.5 + i * 32], c="k", lw=lw)
```
</details>

上記の問題に対して、ノードの深さを調べ、その深さによってそのノードを描画する座標を計算する式を変えるようなプログラムを記述すれば良いのではないかと思った人がいるかもしれませんが、その方法は、下記のような理由でうまくいきません。

* __ゲーム木全体のノードの深さが変わる__ と __計算式が変わってしまう__。例えば、深さが 0 のノードの i 番の子ノードの y 座標は、ゲーム木の深さによって以下のように変化する
    * 深さが 1 までのゲーム木の場合は i * 4
    * 深さが 2 までのゲーム木の場合は i * 32
* ゲームの __決着がついたノード__ には __子ノードは存在しない__ ので、同じ深さのノードでも、__子ノードが存在する__ ノードと __存在しない__ ノードによって __計算式が変わってしまう__

それぞれの __ノードの y 座標__ は、同じ深さの __一つ前のインデックス__ のノードの __高さ__ がわかれば __計算することができます__。例えば、下図の赤枠内の深さが 2 のノードの y 座標は、その上の赤線のノードの高さがわかれば計算することができます。下図の緑枠内の深さが 1 のノードの y 座標は、その上の緑線のノードの高さがわかれば計算することができます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ab5052c8-7c38-c0fb-2020-7691881309bb.png" width="150">

そこで、__各ノードを描画した際の高さを計算__ することにします。なお、以後はこの高さのことを単に「ノードの高さ」と表記します。

それぞれのノードの高さをどのように計算すればよいかについて少し考えてみて下さい。

### ノードの高さを計算する処理の実装

それぞれのノードの高さは、下記のように計算することができます。

* __子ノードがあるノード__ の場合は、__子のノードの高さの合計__
* __子ノードがないノード__ の場合でも、__自分自身のノードの高さの分__ だけ次のノードを __下に描画する必要がある__ ので、ゲーム盤の高さ + ゲーム盤の縦の間隔 = 3 + 1 = __4__

そこで、Node クラスに、ノードの高さを計算する下記のようなメソッドを定義する事にします。

__名前__：ノードの高さ（height）を計算するので、`calc_height` という名前にする
__処理__：ノードを描画した際の高さを計算する
__入力__：なし
__出力__：なし

計算したノードの高さはどこかに記録する必要があるので、`height` 属性に記録することにします。下記は `calc_height` の定義です。

* __2、3 行目__：子ノードが存在しない場合は `height` 属性に 4 を代入する
* __5 ~ 7 行目__：子ノードが存在する場合は、子ノードの `height` 属性の合計を計算して `height` 属性に代入する

```python
1  def calc_height(self):
2      if len(self.children) == 0:
3          self.height = 4
4      else:
5          self.height = 0
6          for childnode in self.children:
7              self.height += childnode.height
8
9  Node.calc_height = calc_height
```

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

```python
def calc_height(self):
    if len(self.children) == 0:
        self.height = 4
    else:
        self.height = 0
        for childnode in self.children:
            self.height += childnode.height

Node.calc_height = calc_height

```
</details>


### 木のそれぞれのノードの高さを計算する処理の実装

次に、Mbtree クラスに、ゲーム木の __各ノードの高さを計算__ する下記のようなメソッドを定義する事にします。どのように定義すればよいかについて少し考えてみて下さい。

__名前__：ゲーム木の各ノードの高さを計算するので、`calc_node_height` という名前にする
__処理__：ゲーム木のそれぞれのノードの高さを計算する
__入力__：なし
__出力__：なし

下記は、ノードの高さを計算する方法を再掲したものです。

* __子ノードがあるノード__ の場合は、__子のノードの高さの合計__
* __子ノードがないノード__ の場合でも、__自分自身のノードの高さの分__ だけ次のノードを __下に描画する必要がある__ ので、ゲーム盤の高さ + ゲーム盤の縦の間隔 = 3 + 1 = __4__

上記から、子ノードが存在するノードの高さを計算するためには、__子のノードの高さが必要になる__ ことがわかります。また、木の __一番深いノードには子ノードは存在しません__。

このことから、ゲーム木のノードの高さを計算するためには、__深い順にノードの高さを計算する必要がある__ ということがわかるので、`calc_node_height` は下記のプログラムのように定義することができます。なお、ノードの子ノードの子ノードである、2 つ下の深さのノードのことを孫（grandchild）ノードと呼びます

* __2 行目__：ルートノードの子ノードである、深さ 1 のノードに対する繰り返し処理を行う
* __4、5 行目__：深さ 1 のノードである `childnode` の子ノードである、深さ 2 のノードに対して、繰り返し処理でその高さを計算する
* __7 行目__：4、5 行目の処理で、`childnode` の全ての子ノードの高さが計算できるので、`childnode` の高さを計算する
* __9 行目__：2 ~ 7 行目の処理で、ルートノードの全ての子ノードの高さが計算できるので、ルートノードの高さを計算する

```python
 1  def calc_node_height(self):
 2      for childnode in self.root.children:
 3          # 深さ 2 のノードの高さの計算
 4          for grandchildnode in childnode.children:
 5              grandchildnode.calc_height()
 6          # 深さ 1 のノードの高さの計算
 7          childnode.calc_height()
 8      # 深さ 0 のノードの高さの計算
 9      self.root.calc_height()
10
11  Mbtree.calc_node_height = calc_node_height
```

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

```python
def calc_node_height(self):
    for childnode in self.root.children:
        # 深さ 2 のノードの高さの計算
        for grandchildnode in childnode.children:
            grandchildnode.calc_height()
        # 深さ 1 のノードの高さの計算
        childnode.calc_height()
    # 深さ 0 のノードの高さの計算
    self.root.calc_height()

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

下記のプログラムは、`calc_height` を呼び出してそれぞれのノードの高さを計算し、深さ 0 のノード、深さ 1 のノード、深さ 2 の最初のノードの高さを表示するプログラムです。それぞれ 288、32、4 という正しい値が計算されていることが確認できます。なお、深さ 2 のノードは数が非常に多いので、最初のノードの高さみを表示しました。

```python
mbtree.calc_node_height()
print("root height", mbtree.root.height)
for childnode in mbtree.root.children:
    print("child height", childnode.height)
print("grandchild height", mbtree.root.children[0].children[0].height)
```

実行結果

```
root height 288
child height 32
child height 32
child height 32
child height 32
child height 32
child height 32
child height 32
child height 32
child height 32
grandchild height 4
```

ゲーム木のそれぞれのノードの高さを計算する処理は、ゲーム木の __それぞれのノード__ に対して __何らかの分析__ を行う処理です。そのような処理の事をゲーム木の __探索__ と呼び、ノードをどのような順番で探索するかによって、幅優先探索と深さ優先探索の 2 種類のアルゴリズムがあります。上記の `calc_node_height` のように、ゲーム木の深さの（浅い、または深い）順でノードの探索を行うアルゴリズムの事を __幅優先探索__ アルゴリズムと呼びます。


### ノードの高さの情報を利用した `draw_node` の修正

次に、ノードの高さの情報を利用するように `draw_node` を修正する必要がありますが、その際に `draw_node` を以下の条件で利用するように修正することにします。

* __個別のノードだけを描画__ するために、キーワード引数 `ax` を記述せずに `draw_node` を呼び出す場合は、（子ノードに子ノードが存在するかどうかに関わらず）__常に子ノードを縦に 4 の間隔で描画すれば良い__ ので、ノードの高さをあらかじめ計算しておく必要はない
* __ゲーム木を描画__ する際に、キーワード引数 `ax` を記述して `draw_tree` から呼び出す場合は、__`calc_node_height`__ によって、__すべてのノードの高さが計算済__ である必要がある

また、それぞれの子ノードは、以下の座標に描画します。

* __最初の子ノード__ は __(dx + 5, dy)__ の位置に描画する
* すべての子ノードを描画する __x 座標は `dx + 5`__ である
* 次の子ノードノードを描画する __y 座標__ は、現在の子ノードを描画した __y 座標__ に、現在の __子ノードの高さを加算__ することで計算できる

従って、それぞれの子ノードを描画する座標は、下記の方法で計算できます

* __(dx + 5, dy)__ の座標に描画する
* ただし、子ノードを描画するたびに、__`dy` の値にその子ノードの高さを加算する__

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

* __2 ~ 11 行目__：`ax` が `None` の場合は、`draw_node` で、自分自身のノードとその子ノードの関係だけを描画する。その場合の処理を、下記のように修正する
    * __3 行目__：`width` の値は、このブロックの中でしか利用しないので、`width` に値を代入する処理はこのブロックの中に移動した
    * __4 行目__：この場合は、子ノードの高さは常に 4 になるので、自分自身のノードの高さを表す `height` の値は元と同じ「子ノードの数 * 4」という式で計算できる
    * __10、11 行目__：子ノードの高さは、この後で子ノードを描画する処理で必要になるので、すべての子ノードの高さを 4 に設定する
* __12、13 行目__： `ax` が `None` でない場合は、ゲーム木を描画する `draw_tree` から、個別のノードを描画するために呼び出される。その場合は、このノードの高さは既に計算されているので `height` には `self.height` を代入する
* __19 行目__：繰り返し処理の中で、インデックスの番号の情報は不要になったので、`i` と `enumerate` は削除した
* __20、21 行目__：子ノードを描画する際に、y 座標として `dy` の位置に描画するように修正する。エッジの描画の処理も同様である
* __22 行目__：`dy` の値を、21 行目で描画した子ノードの高さだけ増やすことで、次のノードの描画位置を計算する

```python
 1  def draw_node(self, ax=None, size=0.25, lw=0.8, dx=0, dy=0):
 2      if ax is None:
 3          width = 8
 4          height = len(self.children) * 4
 5          fig, ax = plt.subplots(figsize=(width * size, height * size))
 6          ax.set_xlim(0, width)
 7          ax.set_ylim(0, height)   
 8          ax.invert_yaxis()
 9          ax.axis("off")
10          for childnode in self.children:
11              childnode.height = 4
12      else:
13          height = self.height
14    
15      # 自分自身のノードを (dx, dy) に描画する
16      Marubatsu_GUI.draw_board(ax, self.mb, lw=lw, dx=dx, dy=dy)
17      plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + height - 4], c="k", lw=lw)
18      # 子ノードとエッジの線を描画する
19      for childnode in self.children:
20          Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy, lw=lw)
21          plt.plot([dx + 4 , dx + 4.5], [dy + 1.5, dy + 1.5], c="k", lw=lw)
22          dy += childnode.height
23        
24  Node.draw_node = draw_node
```

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

```python
def draw_node(self, ax=None, 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
    else:
        height = self.height
    
    # 自分自身のノードを (dx, dy) に描画する
    Marubatsu_GUI.draw_board(ax, self.mb, lw=lw, dx=dx, dy=dy)
    plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + height - 4], 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>

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

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

次に、`draw_tree` を修正します。深さ 1 の一番上のノードは、(5, 0) の位置に描画します。また、その下のノードは先程と同様に、下記の方法で描画する座標を計算できます。

* 最初に `dy` に `0` を代入する
* 深さ 1 のノードを __(5, dy)__ の座標に描画する
* ただし、ノードを描画するたびに、__`dy` の値にそのノードの高さを加算する__

従って、`draw_tree` は、下記のプログラムのように修正できます。

* __2 行目__：ゲーム木の各ノードの高さを計算する
* __4 行目__：Figure の高さは、ルートノードの高さに等しく、その高さは 2 行目で計算済なので、その値を `height` に代入する
* __5 行目__：深さ 0 のルートノードを (0, 0) の位置に描画する
* __7 行目__：深さ 1 のノードを描画する y 座標を表す `dy` を 0 で初期化する
* __9 ~ 10 行目__：繰り返し処理で深さ 1 のノードを (5, dy) の位置に描画し、描画するたびに `dy` にそのノードの高さを加算する。なお、繰り返し処理の中でインデックスの番号の情報は不要になったので、`i` と `enumerate` は削除した

```python
 1  def draw_tree(self, size=0.25, lw=0.8):
 2      self.calc_node_height()   
 3      width = 13
 4      height = self.root.height
元と同じなので省略       
 5      # 深さ 0 のノードの描画
 6      self.root.draw_node(ax=ax, size=size, lw=lw)
 7      dy = 0
 8      # 深さ 1 のノードの描画
 9      for childnode in self.root.children:
10          childnode.draw_node(ax=ax, size=size, lw=lw, dx=5, dy=dy)
11          dy += childnode.height
12
13  Mbtree.draw_tree = draw_tree
```

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

```python
def draw_tree(self, size=0.25, lw=0.8):
    self.calc_node_height()   
    width = 13
    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

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

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

```diff_python
def draw_tree(self, size=0.25, lw=0.8):
+   self.calc_node_height()   
    width = 13
-   height = 288
+   height = self.root.height
元と同じなので省略       
    # 深さ 0 のノードの描画
+   self.root.draw_node(ax=ax, size=size, lw=lw)
+   dy = 0
    # 深さ 1 のノードの描画
-   for i, childnode in enumerate(self.root.children):
+   for childnode in self.root.children:
-       childnode.draw_node(ax=ax, size=size, lw=lw, dx=5, dy=i*32)
+       childnode.draw_node(ax=ax, size=size, lw=lw, dx=5, dy=dy)
+       dy += node.height

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


上記の修正後に、下記のプログラムを実行することで、実行結果のように、__深さ 2 までのゲーム木が描画__ されるようになります。ただし、一見すると正しく描画されているように見えるかもしれませんが、1 つだけおかしな点があります。どこがおかしいかと、何故そのようなことが起きるかについて少し考えてみて下さい。

```python
mbtree.draw_tree()
```

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

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/35ba7021-ecdd-2362-387f-febbd0bdc6d2.png" width="150">

</details>

### 問題の検証と修正

おかしな点は、深さ 0 のノードから深さ 1 のノードへの __エッジを表す線__ が、下図の赤い矢印の部分のように、最後の子ノードの下まで __突き出てしまう__ 点です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/04df3632-6ff0-5d36-52c9-66094442fe04.png" width="150">

深さ 1 のノードから深さ 2 のノードへのエッジを表す線が突き出ないのは、`draw_node` の中で、エッジのその部分の描画を行う下記のプログラムの `dy + 1.5 + height - 4` という式の `- 4` によって、エッジの下の y 座標を __ゲーム盤 1 つ分だけ引いて短くしている__ からです。

```python
plt.plot([dx + 3.5, dx + 4, dx + 4], 
         [dy + 1.5, dy + 1.5, dy + 1.5 + height - 4], c="k", lw=lw)
```

深さ 1 のノードからのエッジの場合はそれでかまいませんが、深さ 0 のノードからのエッジの場合は、4 ではなく、子ノードの __最後のノードの高さの分だけ減らす__ 必要があります。

そこで、`draw_node` の中で、下記のプログラムのように、__エッジの高さ__ を表す __`edgeheight` を計算__ し、それを使ってエッジを描画することにします。なお、このプログラムを書いていて気づいたのですが、__ノードに子供が存在しない場合__ は、__エッジを描画してはいけない__ ので、その処理も追加しています。

* __4、5 行目__：`ax` が `None` の場合の、`edgeheight` を計算する。ただし、エッジは子ノードが存在する場合のみ表示するので、子ノードが存在する場合のみ計算を行う
* __7、8 行目__：`ax` が `None` でない場合の `edgeheight` を計算する。最後の子ノードは、インデックスに __[-1 を記述する](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#%E8%B2%A0%E3%81%AE%E6%95%B4%E6%95%B0%E3%81%AE%E3%82%A4%E3%83%B3%E3%83%87%E3%83%83%E3%82%AF%E3%82%B9)__ ことで参照することができる。なお、`height` は、この後のプログラムで利用しないので、`height` に `self.height` を代入する処理は削除した
* __13 行目__：エッジと子ノードの描画処理を、子ノードが存在する場合だけ行うようにした
* __14 行目__：エッジの縦線の下端の y 座標を `dy + 1.5 + edgeheight` に修正する

```python
 1  def draw_node(self, ax=None, size=0.25, lw=0.8, dx=0, dy=0):
 2      width = 8
 3      if ax is None:
元と同じなので省略
 4          if len(self.children) > 0:
 5              edgeheight = height - 4
 6      else:
 7          if len(self.children) > 0:
 8              edgeheight = self.height - self.children[-1].height
 9
10      # 自分自身のノードを (dx, dy) に描画する
11      Marubatsu_GUI.draw_board(ax, self.mb, lw=lw, dx=dx, dy=dy)
12      # 子ノードが存在する場合に、エッジの線と子ノードを描画する
13      if len(self.children) > 0:   
14          plt.plot([dx + 3.5, dx + 4, dx + 4], [dy + 1.5, dy + 1.5, dy + 1.5 + edgeheight], c="k", lw=lw)
15          for childnode in self.children:
16              Marubatsu_GUI.draw_board(ax, childnode.mb, dx=dx+5, dy=dy, lw=lw)
17              plt.plot([dx + 4 , dx + 4.5], [dy + 1.5, dy + 1.5], c="k", lw=lw)
18              dy += childnode.height
19        
20  Node.draw_node = draw_node
```

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

```python
def draw_node(self, ax=None, 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:
            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>

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

```diff_python
def draw_node(self, ax=None, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    if ax is None:
元と同じなので省略
        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:
            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>

上記の修正後に、下記のプログラムを実行することで、実行結果のように、深さ 2 までのゲーム木が正しく描画されるようになります。

```python
mbtree.draw_tree()
```

<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 以上のノードの作成と問題点

深さ 3 のノードの作成は、深さ 2 のノードの作成と同様の方法で、下記のプログラムのように記述できます。

* __8、9 行目__：深さ 2 のノードを作成する __ブロックの中__ で、__同様の繰り返し処理を記述__ することで、深さ 3 のノードを作成する

```python
 1  def create_tree_by_bf(self):
 2      # 深さ 1 のノードの作成
 3      self.root.calc_children()
 4      # 深さ 2 のノードの作成
 5      for childnode in self.root.children:
 6          childnode.calc_children()
 7          # 深さ 3 のノードの作成
 8          for grandchildnode in childnode.children:
 9              grandchildnode.calc_children()
10
11  Mbtree.create_tree_by_bf = create_tree_by_bf
```

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

```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()

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

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

```diff_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()

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

上記の修正後に下記のプログラムを実行すると、実行結果のように深さ 2 の最初のノードが正しく描画されます。

```python
mbtree = Mbtree()
mbtree.root.children[0].children[0].draw_node()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/443306c0-a7b3-f0db-6dbf-1da4028fa7ae.png" width="150">

同様に、深さ 4 のノードは下記のプログラムで作成できます[^3]。なお、先程とほぼ同様の修正なので、プログラムの修正の説明と修正箇所は省略します。

```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()

Mbtree.create_tree_by_bf = create_tree_by_bf
```

上記の修正後に下記のプログラムを実行すると、実行結果のように深さ 3 の最初のノードが正しく描画されます。

```python
mbtree = Mbtree()
mbtree.root.children[0].children[0].children[0].draw_node()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d0c419da-7ef5-39d2-6cba-3910290ffaa4.png" width="150">

上記のプログラムの記述方法は、おそらく初心者でも思いつくことができる方法ですが、__深さを 1 つ増やすたび__ に、増やした深さのノードを計算する __繰り返しのブロックを記述する必要があります__。そのため、このようなプログラムを、〇×ゲームのゲーム木を作成する際に必要な、__深さ 9 のノードまで記述__ することは __かなり面倒__ です。

また、〇×ゲームの場合は、深さが 9 までしかないので記述しようと思えば記述できるかもしれませんが、オセロ、囲碁、将棋のような、決着するまでに数十手以上かかるゲームの場合は、__そのようなプログラムを記述する__ のは __現実的にはほぼ不可能__ になります。

次回の記事では、幅優先アルゴリズムで、任意の深さのゲーム木を作成する方法について紹介します。余裕がある方は、その方法について少し考えてみて下さい。

# 今回の記事のまとめ

今回の記事では、幅優先アルゴリズムで深さ 2 のゲーム木を作成し、視覚化する処理を実装しました。

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

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

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

今回の記事では marubatsu.py は更新していません。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/949d18e60939d510c931

[^1]:木構造には様々な種類があります。`Tree` という名前ではどのような種類の木構造のデータなのかがわからないので、〇×ゲームのゲーム木であるこをと明確にするために `Mbtree` と名付けました
[^2]:bf は幅優先を表す breadth first の略です
[^3]:greatgrandchild は、ひ孫を表す英単語です