Pythonで〇×ゲームのAIを一から作成する　その104　木構造のデータに対する幅優先と深さ優先アルゴリズムによる繰り返し処理

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/9303214ec798a920174e

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

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

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

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

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

# 木構造のデータに対する繰り返し処理

前回の記事では分岐する繰り返し処理の例として、複数の項で表される漸化式をトップダウンな再帰呼び出しで記述する場合を説明しました。

今回の記事では、__分岐が必須__ となる繰り返し処理の例として、[木構造](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E6%9C%A8%E6%A7%8B%E9%80%A0tree-structure)のデータに対する繰り返し処理について説明します。

その前に、木構造についていくつかの補足説明をします。

## 木構造の例

これまでの記事では木構造の具体例として〇×ゲームのゲーム木を取り上げてきましたが、__木構造__ で表されるデータは __世の中で広く使われています__。

例えば、学校の生徒は下記のような木構造で表現することができます。

* ルートノードは学校そのものを表し、その子ノードは学年を表す
* 学年を表すノードの子ノードはその学年のクラスを表す
* クラスを表すノードの子ノードは、そのクラスの生徒を表す

この木構造を図で表すと以下のようになります。なお、図が大きくなりすぎるので、2 年の子ノードや、2 組の兄弟ノードなどは省略しています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/19851ff4-9d51-851a-f3a8-1e0100746a24.png" width="450">

他にも、家の住所、本の章や節など、様々なデータが木構造で表現できます。

木構造では、データを学年、クラス、クラスの生徒のように、大きな分類から少しずつ細かい分類にわけてデータを __階層的に表現__ します。そのため、木構造は __階層構造__ を表します。

実は、〇×ゲームのゲーム木よりはるか前に、この記事では木構造で表現されるデータを扱ってきました。その一つが、〇×ゲームのゲーム盤のデータです。

下図のように〇×ゲームのゲーム盤を表すと、木構造には見えないかもしれません。どのようにすれば木構造で表現できるかについて少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9813a553-aed6-d027-a1c9-60f8f2ca6a2f.png" width="200">

〇×ゲームのゲーム盤は、下記のような木構造で表現することができます。

* ルートノードはゲーム盤そのものを表し、その子ノードは列のデータを表す
* 列のノードの子ノードは、その列のマスを表す

この木構造を図で表すと以下のようになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f635853b-ea3e-415f-5c3c-8684056f92d0.png" width="350">

## 木構造の表現方法

〇×ゲームのゲーム盤は、`Marubatsu` クラスのインスタンスの `board` 属性に代入されています。`mb` に `Marubatsu` クラスのインスタンスが代入されている場合は、それぞれの深さのノードは下記の表のように表現されます。

|  | 対応するノード |
|:--|:--|
| `mb.board`  | 深さ 0 のルートノード  |
| `mb.board[x]`  | 深さ 1 のノード  |
| `mb.board[x][y]`  | 深さ 2 のノード  |

上記の表から、先頭から __i 番目の添え字__ が、木構造の __ノードの深さに対応__ します。

`board` には 2 次元配列を表す list が代入されていますが、複数のデータを扱うことができる dict も同様の性質を持つので、__list や dict__ で表されるデータは、__インデックスやキー__ をノードが表す __データ__ とし、その __要素を子ノード__ とする __木構造のノード__ と考えることができます。従って、__list と dict を組み合わせる__ ことで __木構造を表現__ することができます。

__インデックスやキー以外__ のデータを、__ノードのデータ__ とした木構造を表現する場合は、Mbtree クラスのように、__ノードをオブジェクトで表し__、その __属性__ に __ノードのデータ__ と、__子ノードの一覧を代入__ する必要があります。

## ネットワーク構造との違い

木構造は、以下のような性質を持つデータ構造です。

* ノードとノードの間に、親ノードと子ノードという、__方向の関係__ がある
* __ルートノードが 1 つだけ存在__ する。別の言い方で言うと、ルートノード以外のノードの親ノードを辿っていくと、必ず一つのルートノードにたどり着く
* ノードの __子ノードを辿って行く__ と、必ず子ノードが存在しない __リーフノード__ にたどり着く。別の言い方で言うと、ノードの子ノードを辿った際に、元のノードにたどり着くような、__ループが存在しない__

上記の性質を満たさないような場合は、木構造ではなく、ネットワーク構造やグラフ構造と呼びます[^1]。ネットワーク構造に対する繰り返し処理では、__ループがある場合__ は __無限ループが発生しないように注意__ してプログラムを記述する必要がありますが、__木構造にはループは存在しない__ のでそのことを注意しなくても良いという利点があります。なお、ネットワーク構造に対する繰り返し処理は複雑になるので、今回の記事では取り上げません。

# 分岐する繰り返し処理を行うアルゴリズム

__分岐する繰り返し処理__ を行うアルゴリズムには、__幅優先アルゴリズム__ と __深さ優先アルゴリズム__ があります。またそれぞれのアルゴリズムは __ボトムアップ__ な繰り返し処理と、__トップダウン__ な繰り返し処理に分類することができます。

これまでの記事では〇×ゲームのゲーム木の作成などで、既に木構造に対する繰り返し処理を記述しましたが、その性質までは説明していませんでした。そこで、今回の記事では、これまで記述してきたプログラムを踏まえながら、それぞれの性質について説明します。

なお、今回の記事の説明はすべて木構造のデータに対する繰り返し処理です。

# 幅優先アルゴリズムによる繰り返し処理

## ボトムアップな繰り返し処理による実装

木構造に対する __幅優先アルゴリズム__ による __ボトムアップ__ な繰り返し処理は、以下のようなアルゴリズムで行います。ただし、次に処理を行う木の深さを d で表すことにします。

1. d を 0 とする
2. 深さ d の全てのノードに対する処理を行う。ノードが存在しない場合は処理を終了する
3. d に 1 を足して手順 2 へ戻る

### while 文による実装

これまでの記事では、〇×ゲームのゲーム木を幅優先アルゴリズムで作成する Mbtree クラスの下記の `create_tree_by_bf` で while 文を使ってその処理を記述しました。

```python
 1  def create_tree_by_bf(self):
 2      # 深さ 0 のノードを、子ノードを作成するノードのリストに登録する
 3      nodelist = [self.root]
 4      depth = 0
 5      # 各深さのノードのリストを記録する変数を初期化する
 6      self.nodelist_by_depth = [ nodelist ]
 7    
 8      # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
 9      while len(nodelist) > 0:
10           childnodelist = [] 
11           for node in nodelist:
12               if node.mb.status == Marubatsu.PLAYING:
13                   node.calc_children()
14                   childnodelist += node.children
15           self.nodelist_by_depth.append(childnodelist)
16           nodelist = childnodelist
17           depth += 1
略
```

上記のアルゴリズムで処理を行うためには、以下のデータを記録する必要があります。

* 深さ d の値
* 深さ d のノードの一覧
* 次の深さのノードの一覧

また、上記のデータに対して、下記の処理を記述する必要があります。（）の中に記述した内容は、上記のプログラムで対応する値を記録する変数と、処理が記述されている行数です

* __深さ d の値__（`depth`）
    * __初期化処理__：0 で初期化する（4 行目）
    * __更新処理__：深さ d のノードの一覧に対する処理の最後で、次に処理を行うノードの深さを表すように 1 を加算する（17 行目）
* __深さ d のノードの一覧__（`nodelist`）
    * __初期化処理__：ルートノードを要素とする list で初期化する（3 行目）
    * __データの利用__：while 文で要素を一つずつ取り出し、深さ d のノードの一覧に対する処理を行う（9 ~ 17 行目）
    * __更新処理__：深さ d のノードの一覧に対する処理の最後で、次に処理を行う、次の深さのノードの一覧を代入する（16 行目）
* __次の深さのノードの一覧__（`childnodelist`）
    * __初期化処理__：深さ d のノードの一覧に対する処理を開始する際に空の list で初期化する（10 行目）
    * __更新処理__：深さ d のノードの処理を行った後で、そのノードの子ノードの一覧を追加する（14 行目）

なお、上記のプログラムの 6 行目と 15 行目で __`nodelist_by_depth`__ に __深さ d のノードの一覧を記録__ する処理は、ゲーム木を作成する際に __必要のない処理__ で、そのデータがあると、ゲーム木を作成した後で便利だという理由で用意したものです。また、上記のプログラムの「略」以降では、__各深さのノードの数を数える処理など__ を行っていますが、それらの処理も、ゲーム木を作成する際に __必要となる処理ではありません__。

実は、幅優先アルゴリズムによるボトムアップな繰り返し処理の最中に、__ノードの深さを表す情報が必要ない場合__ は、__深さ d を記録する必要はありません__。上記のプログラムでも、`depth` は 4 行目と 11 行目以外では使われていないので、4 行目と 11 行目を削除してもプログラムは正しく動作します。

### 再帰呼び出しによる実装

[以前の記事](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#%E3%83%9C%E3%83%88%E3%83%A0%E3%82%A2%E3%83%83%E3%83%97%E3%81%AA%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E6%B5%81%E3%82%8C)で説明したように、ボトムアップな再帰呼び出しでは、__処理に必要なデータを仮引数で受け取り__ ます。`create_tree_by_bf` の場合は、処理を行う深さの __ノードの一覧のデータが必要になる__ ので、そのデータを代入する仮引数 __`nodelist`__ を追加することにします。また、そのデフォルト値を `None` し、`None` の場合はルートノードを要素とする list を代入する処理を記述することで、最初に `create_tree_by_bf` を呼び出した際に、`nodelist` に対応する実引数を記述しなくても良いように工夫します。

それ以降の処理の修正の基本的な考え方は[以前の記事](https://qiita.com/ysgeso/items/8432194829a4c6cc95f0#%E3%83%9C%E3%83%88%E3%83%A0%E3%82%A2%E3%83%83%E3%83%97%E3%81%AA%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%82%92%E8%A1%8C%E3%81%86%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)で説明した、for 文で定義した `fib_by_f` を `fib_by_br` に修正した方法と同じです。なお、このプログラムでは、`depth` や `node_list_by_depth` などの、ゲーム木の作成に必要のない処理は削除しました。

* __4 行目__：仮引数 `depth` を削除し、デフォルト値を `None` とする 仮引数 `nodelist` を追加
* __5、6 行目__：`nodelist` が `None` の場合に、`nodelist` をルートノードを要素とする list で初期化する
* __8 行目__：繰り返し処理は再帰呼び出しで行うので、while 文を if 文に修正する
* __14 行目__：次の深さのノードの一覧を表す `childnode` を実引数として再帰呼び出しを行うことで、繰り返し処理を行う

```python
 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3
 4  def create_tree_by_bf(self, nodelist=None):
 5      if nodelist is None:
 6          nodelist = [self.root]
 7 
 8      if len(nodelist) > 0:
 9          childnodelist = [] 
10          for node in nodelist:
11              if node.mb.status == Marubatsu.PLAYING:
12                  node.calc_children()
13                  childnodelist += node.children
14          self.create_tree_by_bf(childnodelist)
15               
16  Mbtree.create_tree_by_bf = create_tree_by_bf
```

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

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

def create_tree_by_bf(self, nodelist=None):
    if nodelist is None:
        nodelist = [self.root]
  
    if len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            if node.mb.status == Marubatsu.PLAYING:
                node.calc_children()
                childnodelist += node.children
        self.create_tree_by_bf(childnodelist)
               
Mbtree.create_tree_by_bf = create_tree_by_bf
```
</details>

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

```diff_python
-def create_tree_by_bf(self):
+def create_tree_by_bf(self, nodelist=None):
-   nodelist = [self.root]
+   if nodelist is None:
+       nodelist = [self.root]
-   depth = 0
-   self.nodelist_by_depth = [ nodelist ]

+   while len(nodelist) > 0:
-   if 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                   
+       self.create_tree_by_bf(childnodelist)
               
Mbtree.create_tree_by_bf = create_tree_by_bf
```
</details>

ゲーム木を GUI で表示する Mbtree_GUI クラスでは、`nodelist_by_depth` などの、上記の修正で削除した情報は使用していないので、下記のプログラムで `create_tree_by_bf` でゲーム木を作成した Mbtree クラスのインスタンスを GUI で表示することができます。

```python
from tree import Mbtree_GUI

mbtree_bf = Mbtree()
mbtree_gui = Mbtree_GUI(mbtree_bf)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/138d5bb7-d0ec-036a-e50a-48885cc1c327.png" width="150">

:::note
Mbtree_Anim クラスでは、上記で削除した `nodenum` や `nodelist_by_depth` 属性などの情報が必要になるので、Mbtree_Anim でアニメーションを行うことはできません。
:::

### return 文を記述しない理由

ボトムアップな再帰呼び出しを行う `fib_by_br` では、下記のプログラムのように return 文が記述されていますが、`create_tree_by_bf` には __return 文が記述されていない__ 点が気になっている人がいるかもしれません。

```python
def fib_by_br(n, i=2, fib_p1=1, fib_p2=0):
    if n == 0:
        return 0
    elif n == 1:
        return 1
        
    if i <= n:
        fib = fib_p1 + fib_p2
        fib_p2 = fib_p1
        fib_p1 = fib
        i += 1
        return fib_by_br(n, i, fib_p1, fib_p2)
    else:
        return fib_p1
```

return 文が必要ない理由は、[以前の記事](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#return-%E6%96%87%E3%82%92%E4%BD%BF%E3%82%8F%E3%81%AA%E3%81%84%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%81%AE%E4%BE%8B)で説明した return 文を使わない再帰呼び出しの例と同様です。ただし、以前の記事の例では、仮引数に代入したミュータブルなデータに対して処理を行っていましたが、`create_tree_by_bf` の場合は、`root` 属性に代入したミュータブルなデータに対して処理を行っています。

## トップダウンな繰り返し処理による実装

木構造に対する __幅優先アルゴリズム__ による __トップダウン__ な繰り返し処理は、以下のようなアルゴリズムで行います。ただし、次に処理を行う木の深さを d で表すことにします。

1. ルートノードから順に各深さのノードの一覧を幅優先アルゴリズムで計算する
2. d を最も深いノードの深さとする
3. 深さ d の全てのノードに対する処理を行う
4. d から 1 を引いて手順 3 へ戻る。ただし、d が負になった場合は処理を終了する

上記の __手順 1__ は先ほど説明した __ボトムアップな繰り返し処理と基本的には同じ__ ですが、__各深さのノードの一覧を記録しておく必要がある__ 点が異なります。その後、記録しておいた各深さのノードの一覧の情報を使って、手順 2 ~ 4 の処理を行います。

これまでの記事では、Mbtree クラスで __ゲーム木の部分木を描画__ する際に必要となる、__各ノードの高さを計算__ する、下記の __`calc_node_height`__ でその処理を記述しました。各ノードの高さを計算するためには、__ルートノードから計算することはできず__、__最も深いノードから計算する必要がある__ ので、この処理は __トップダウン__ な繰り返し処理に分類されます。

なお、`calc_node_height` では、__`centernode` をルートノード__ とし、__深さが `maxdepth` までの部分木__ に対する処理を行いますが、__部分木は木構造の一種__ なので、__上記と同じアルゴリズム__ で処理を行うことができます。

`calc_node_height` の処理を忘れた方は、[以前の記事](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#calc_node_height-%E3%81%AE%E4%BF%AE%E6%AD%A3)を復習して下さい。


```python
 1  def calc_node_height(self, centernode, maxdepth):
 2      nodelist = [centernode]
 3      depth = centernode.depth
 4      # 各深さのノードのリストを記録する変数を初期化する
 5      nodelist_by_depth = [None] * centernode.depth
 6      nodelist_by_depth.append(nodelist)
 7   
 8      # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
 9      while len(nodelist) > 0:
10          childnodelist = [] 
11          for node in nodelist:
12              childnodelist += node.children
13          nodelist_by_depth.append(childnodelist)
14          nodelist = childnodelist
15          depth += 1
16      
17      for depth in range(maxdepth, centernode.depth - 1, -1):
18          for node in nodelist_by_depth[depth]:
19              if depth == maxdepth:
20                  node.height = 4
21              else:
22                  node.calc_height()    
```

上記のアルゴリズムで処理を行うためには、先程説明したボトムアップな処理で必要なデータに __加え__、以下のデータを記録し、処理を行う必要があります。（）の中に記述した内容は、上記のプログラムで対応する値を記録する変数と、処理が記述されている行数です。

* __各深さのノードの一覧__（`nodelist_by_depth`）
    * __初期化処理__：空の list で初期化する。ただし、部分木の場合は、部分木のルートノードより浅い深さのノードは利用しないので、上記のプログラムではそれらの深さに対応する要素は `None` としている（5、6 行目）
    * __更新処理__：ルートノードを要素とする list を要素に追加する（6 行目）。各深さのノードの一覧の情報を追加する（13 行目）
    * __データの利用__：最も深い深さから順にノードのリストを取り出し、取り出したノードのリストから要素を取り出して処理を行う（18 ~ 23 行目）

このプログラムを、再帰呼び出しで記述する場合は、手順 1 を行う再帰呼び出しの関数と、手順 2 ~ 4 を行う再帰呼び出しの関数を __別々に定義する必要があります__。そのため、わざわざ再帰呼び出しで記述する必要はあまりないと思いますので、本記事では記述しませんが、プログラミングの練習にはなると思いますので、興味がある方は記述してみて下さい。

### `calc_node_height` のバグ

今回の記事を執筆中に、`calc_node_height` にはバグがあることが判明しましたので、そのバグの修正方法を説明します。

〇×ゲームでは、どのような着手を行っても __8 手目以内で決着がつく__ ような局面が存在します。例えば、下記の局面では、7 手目でどのマスに〇が着手を行っても〇が勝利するので __7 手目で必ず決着がつきます__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4448daba-f91b-f74b-eb57-3dbb61c16840.png" width="100">

このような局面のノードを `centernode` に代入し、__`maxdepth` に `9` を代入__ して `calc_node_height` を呼び出すと、__`nodelist_by_depth`__ には、__深さが 7 まで__ のノードの一覧しか __代入されません__。その状態で、`calc_node_height` の下記のプログラムを実行すると、`depth` に `maxdepth` に代入された `9` が代入された状態で、18 行目のプログラムが実行されるので、18 行目では「IndexError: list index out of range」というエラーが発生します。実際に先程実行した GUI で上記の局面を選択するとエラーが発生することを確認して下さい。

```python
17      for depth in range(maxdepth, centernode.depth - 1, -1):
18          for node in nodelist_by_depth[depth]:
```

このエラーを修正する方法の一つは、17 行目で __`depth`__ に `nodelist_by_depth` の要素の数以上の値が __代入されないようにする__ といものです。具体的には下記のプログラムのように、最小値を計算する組み込み関数 `min` を利用して 2 行目の range を下記のように修正します。

```python
1  def calc_node_height(self, centernode, maxdepth):
元と同じなので省略
2      for depth in range(min(maxdepth, len(nodelist_by_depth) - 1), centernode.depth - 1, -1):
3          for node in nodelist_by_depth[depth]:
元と同じなので省略
                
Mbtree.calc_node_height = calc_node_height
```

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

```python
def calc_node_height(self, centernode, maxdepth):
    nodelist = [centernode]
    depth = centernode.depth
    # 各深さのノードのリストを記録する変数を初期化する
    nodelist_by_depth = [None] * centernode.depth
    nodelist_by_depth.append(nodelist)
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            childnodelist += node.children
        nodelist_by_depth.append(childnodelist)
        nodelist = childnodelist
        depth += 1
    
    for depth in range(min(maxdepth, len(nodelist_by_depth) - 1), centernode.depth - 1, -1):
        for node in nodelist_by_depth[depth]:
            if depth == maxdepth:
                node.height = 4
            else:
                node.calc_height()    
                
Mbtree.calc_node_height = calc_node_height
```
</details>

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

```diff_python
def calc_node_height(self, centernode, maxdepth):
元と同じなので省略
    for depth in range(min(maxdepth, len(nodelist_by_depth) - 1), centernode.depth - 1, -1):
        for node in nodelist_by_depth[depth]:
元と同じなので省略
                
Mbtree.calc_node_height = calc_node_height
```
</details>

実行結果は省略しますが、上記の修正後に、下記のプログラムを実行し、上記の局面を選択してもエラーが発生しなくなることを確認して下さい。

```python
mbtree_gui = Mbtree_GUI(mbtree_bf)
```

:::note
他にも以下のような修正方法などの、様々な修正方法が考えられます。

* __5 行目__：`nodelist_by_depth` の初期化処理を、空の list を要素とする、__要素の数が 11__ の list で初期化するようする。この修正で、18 行目でエラーが発生しなくなる。なお、13 行目の処理で、深さが 9 のノードに対して __`nodelist_by_depth[10]` に代入処理が行われる__ ので、要素の数は 11 にする必要がある点に注意すること
* __6 行目__：`centernode` の深さのノードの一覧を `nodelisst_by_depth` に記録する
* __13 行目__：深さが `depth` の子ノードの一覧を `nodelist_by_depth` に記録する。その際に、子ノードの深さは `depth + 1` である点に注意すること
* __17 行目__：`range` の実引数を元に戻す


```python
 1  def calc_node_height(self, centernode, maxdepth):
 2      nodelist = [centernode]
 3      depth = centernode.depth
 4      # 各深さのノードのリストを記録する変数を初期化する
 5      nodelist_by_depth = [[] for i in range(11)]
 6      nodelist_by_depth[centernode.depth] = nodelist
 7   
 8      # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
 9      while len(nodelist) > 0:
10          childnodelist = [] 
11          for node in nodelist:
12              childnodelist += node.children
13          nodelist_by_depth[depth + 1] = childnodelist
14          nodelist = childnodelist
15          depth += 1
16      
17      for depth in range(maxdepth, centernode.depth - 1, -1):
18          for node in nodelist_by_depth[depth]:
19              if depth == maxdepth:
20                  node.height = 4
21              else:
22                  node.calc_height()    
23                
24  Mbtree.calc_node_height = calc_node_height
```

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

```python
def calc_node_height(self, centernode, maxdepth):
    nodelist = [centernode]
    depth = centernode.depth
    # 各深さのノードのリストを記録する変数を初期化する
    nodelist_by_depth = [[] for i in range(11)]
    nodelist_by_depth[centernode.depth] = nodelist
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            childnodelist += node.children
        nodelist_by_depth[depth + 1] = childnodelist
        nodelist = childnodelist
        depth += 1
    
    for depth in range(maxdepth, centernode.depth - 1, -1):
        for node in nodelist_by_depth[depth]:
            if depth == maxdepth:
                node.height = 4
            else:
                node.calc_height()    
                
Mbtree.calc_node_height = calc_node_height
```
</details>

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

```diff_python
def calc_node_height(self, centernode, maxdepth):
    nodelist = [centernode]
    depth = centernode.depth
    # 各深さのノードのリストを記録する変数を初期化する
-   nodelist_by_depth = [None] * centernode.depth
+   nodelist_by_depth = [[] for i in range(11)]
-   nodelist_by_depth.append(nodelist)
+   nodelist_by_depth[centernode.depth] = nodelist
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            childnodelist += node.children
-       nodelist_by_depth.append(childnodelist)
+       nodelist_by_depth[depth + 1] = childnodelist
        nodelist = childnodelist
        depth += 1
    
-   for depth in range(min(maxdepth, len(nodelist_by_depth) - 1), centernode.depth - 1, -1):
+   for depth in range(min(maxdepth, centernode.depth - 1, -1):
        for node in nodelist_by_depth[depth]:
            if depth == maxdepth:
                node.height = 4
            else:
                node.calc_height()    
                
Mbtree.calc_node_height = calc_node_height
```

</details>

実行結果は省略しますが、上記の修正後に、下記のプログラムを実行し、上記の局面を選択してもエラーが発生しなくなることを確認して下さい。

```python
mbtree_gui = Mbtree_GUI(mbtree_bf)
```
:::

## 幅優先アルゴリズムの性質

__幅優先アルゴリズム__ は、深さの順で処理を行うという __処理の流れがわかりやすい__ という利点はありますが、処理を行う際に、__次の深さのノードの一覧を記録する処理__ を記述する必要があるため、__プログラムが複雑__ になります。また、__トップダウン__ な繰り返し処理の場合は、__すべての深さのノードの一覧を記録__ する必要が生じます。

[前回の記事](https://qiita.com/ysgeso/items/9303214ec798a920174e#%E5%88%86%E5%B2%90%E3%81%99%E3%82%8B%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AE%E5%87%A6%E7%90%86%E6%99%82%E9%96%93)で説明したように、__木構造__ のデータに対する繰り返し処理のような、繰り返しの回数が増えると __指数関数的__ に処理の数が増えるという性質があります。そのため、木構造の深さが深くなると  に __ノードの数が急激に増加する__ ので、__深い木構造__ のデータに対して __幅優先アルゴリズム__ で処理を行うと、__ノードを記録するためのメモリが大量に必要になる__ という欠点があります。

なお、今回の記事では説明しませんが、__幅優先アルゴリズム__ には __利点もあります__。また、幅優先アルゴリズムで __行う必要がある__ 繰り返し処理もあるので、幅優先アルゴリズムが良くないアルゴリズムであるとは言えません。__状況に応じて__ 幅優先アルゴリズムと深さ優先アルゴリズムを __使い分ける必要があります__。

### 分岐しない再帰呼び出しと多重再帰

幅優先アルゴリズムを再帰呼び出しで記述した場合のプログラムの特徴として、再帰呼び出しの関数の中で、__再帰呼び出しが 1 回しか行われない__ という点が挙げられます。これは、__幅優先アルゴリズム__ が、0、1、2・・・のように表現される、__深さの順__ という __分岐しない__ 繰り返し処理を行うからです。__木構造__ は、ノードが __複数の子ノードを持つ__ ので __分岐します__ が、その __分岐の情報__ は再帰呼び出しの __仮引数に代入__ されるため、__再帰呼び出し__ の処理は __分岐しません__。`create_tree_by_bf` の場合は、再帰呼び出しを行うたびに、`nodelist` に代入された list の要素の数は急激に増えていきますが、__再帰呼び出し__ そのものは、__分岐しません__。

一方、再帰呼び出しの関数の中で、__複数の再帰呼び出し__ が行われて __分岐する__ ようなものを __多重再帰__ と呼びます。この後で説明する、深さ優先アルゴリズムを再帰呼び出しで実装する場合は、再帰呼び出しは多重再帰になります。

# 深さ優先アルゴリズムによる繰り返し処理

## ボトムアップな繰り返し処理による実装

木構造に対する __深さ優先アルゴリズム__ による __ボトムアップ__ な繰り返し処理は、以下のようなアルゴリズムで行います。ただし、次に処理を行うノードを N とします。

1. N を ルートノードとする
2. __N に対する処理__ を行う
3. N の子ノードのうち、__まだ処理を行っていない子ノードが存在するか__ を判定する
    1. 処理を行っていない子ノードが __存在する場合__ は、その中から 1 つを選び、__そのノードを N__ として __手順 2 に戻る__
    2. 処理を行っていない子ノードが __存在しない場合__ は、__親ノードが存在するか__ を判定する
        1. 親ノードが __存在する場合__ は、__親ノードを N__ として __手順 2 に戻る__
        2. 親ノードが __存在しない場合__ は、__処理を終了する__

### while 文による実装

これまでの記事では、[以前の記事](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%82%88%E3%82%8B%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E4%BD%9C%E6%88%90)で説明したように、〇×ゲームのゲーム木を以下のようなアルゴリズムで作成しました。下記のアルゴリズムは、上記のアルゴリズムに、N に対して行う具体的な処理として、子ノードを作成するという処理を記述したものです。

1. ゲーム開始時の局面を表すノードを、ルートノードとするゲーム木を作成する
2. __子ノードを作成する__ 処理を行う __ノードを N と表記__ し、__N を ルートノードで初期化__ する
3. __N__ にまだ __作成していない子ノードが存在するか__ を判定する
    1. 作成していない子ノードが __存在する場合__ は、__その子ノードを作成__ し、__作成した子ノードを N として手順 3 に戻る__
    2. 作成していない子ノードが __存在しない場合__ は、__親ノードが存在するか__ を判定する
        1. 親ノードが __存在する場合__ は、__親ノードを N として手順 3 に戻る__
        2. 親ノードが __存在しない場合__ は、ゲーム木が完成しているので __処理を終了する__

また、上記の処理は Mbtree クラスの下記の __`create_tree_by_df`__ で記述しました。このプログラムの意味については、[以前の記事](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#create_tree_by_df-%E3%81%AE%E5%AE%9A%E7%BE%A9)で詳しく説明したので忘れた方は復習して下さい。

```python
def create_tree_by_df(self):
    self.nodelist = [self.root]
    self.nodelist_by_depth = [[] for _ in range(10)]
    self.nodelist_by_depth[0].append(self.root)
    self.nodenum = 0
  
    N = self.root
  
    while N is not None:
        legal_moves = N.mb.calc_legal_moves()
        childnum = len(N.children)
        if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
            x, y = legal_moves[childnum]
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
            self.nodelist.append(node)
            self.nodelist_by_depth[N.depth + 1].append(node)
            self.nodenum += 1
            N = node
        else:
            N = N.parent
```

上記のプログラムの中で、ノードの数やノードの一覧を記録する `nodenum`、`nodelist`、`nodelist_by_depth` は、ゲーム木を作成する処理では __必要はありません__。そこで、下記のプログラムのように、ゲーム木を作成するために必要のない処理を削除したプログラムで説明することにします。

```python
 1  from tree import Node
 2  from copy import deepcopy
 3
 4  def create_tree_by_df(self):
 5      N = self.root
 6   
 7      while N is not None:
 8          legal_moves = N.mb.calc_legal_moves()
 9          childnum = len(N.children)
10          if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
11              x, y = legal_moves[childnum]
12              mb = deepcopy(N.mb)
13              mb.move(x, y)
14              node = Node(mb, parent=N, depth=N.depth + 1)
15              N.insert(node)
16              N = node
17          else:
18              N = N.parent
19            
20  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```python
from tree import Node
from copy import deepcopy

def create_tree_by_df(self):
    N = self.root
    
    while N is not None:
        legal_moves = N.mb.calc_legal_moves()
        childnum = len(N.children)
        if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
            x, y = legal_moves[childnum]
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
            N = node
        else:
            N = N.parent
            
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_python
from tree import Node
from copy import deepcopy

def create_tree_by_df(self):
-   self.nodelist = [self.root]
-   self.nodelist_by_depth = [[] for _ in range(10)]
-   self.nodelist_by_depth[0].append(self.root)
-   self.nodenum = 0

    N = self.root
    
    while N is not None:
        legal_moves = N.mb.calc_legal_moves()
        childnum = len(N.children)
        if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
            x, y = legal_moves[childnum]
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
-           self.nodelist.append(node)
-           self.nodelist_by_depth[N.depth + 1].append(node)
-           self.nodenum += 1
            N = node
        else:
            N = N.parent
            
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

実行結果は先ほどと同じなので省略しますが、下記のプログラムで `create_tree_by_df` でゲーム木を作成した Mbtree クラスのインスタンスを GUI で表示することができます。

```python
mbtree_df = Mbtree(algo="df")
mbtree_gui = Mbtree_GUI(mbtree_df)
```

### while 文による実装が複雑になる理由

上記のプログラムでは、__while 文__ を使って __深さ優先アルゴリズム__ によるゲーム木を作成していますが、while 文を使ったプログラムでは、下記のアルゴリズムの中の __手順 3__ の処理の __記述が複雑__ になります。

1. N を ルートノードとする
2. __N に対する処理__ を行う
3. N の子ノードのうち、__まだ処理を行っていない子ノードが存在するか__ を判定する
    1. 処理を行っていない子ノードが __存在する場合__ は、その中から 1 つを選び、__そのノードを N__ として __手順 2 に戻る__
    2. 処理を行っていない子ノードが __存在しない場合__ は、__親ノードが存在するか__ を判定する
        1. 親ノードが __存在する場合__ は、__親ノードを N__ として __手順 2 に戻る__
        2. 親ノードが __存在しない場合__ は、__処理を終了する__

1 つ目の複雑な処理の記述として、手順 3 では、N の子ノードのうち、__まだ処理を行っていない子ノードを探す__ 処理があります。そのような処理を行うためには、__処理を行った子ノードとそうでない子ノードを区別する必要__ があります。〇×ゲームのゲーム木を作成する処理の場合は、作成済の子ノードの数と、合法手の数を比較することでその判定を行うことができましたが、`calc_node_height` のような、__既に作成済のゲーム木__ に対して処理を行う場合は、そのような判定を行うことは __それほど簡単ではありません__[^2]。

2 つ目の複雑な処理の記述として、手順 3-2 では、__親ノードを辿る処理が必要__ となります。〇×ゲームのノードを表す Node クラスには、親ノードを表す `parent` 属性があるので親ノードを辿る処理は簡単に記述できますが、__`parent` 属性がない場合__ は、__繰り返し処理の中__ で、__親ノードの情報を記録しておく必要が生じます__。

### 再帰呼び出しによる実装

__再帰呼び出し__ でボトムアップな深さ優先アルゴリズムを記述する場合は、上記で説明した while 文で記述する場合の __問題は生じません__。その理由について説明します。

下図は、[前回の記事](https://qiita.com/ysgeso/items/9303214ec798a920174e#fib_by_tr-%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E6%B5%81%E3%82%8C)で紹介した、再帰呼び出しで計算を行う `fib_by_tr` を使って $F_4$ を計算した際の処理の流れを表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0102a76a-1c82-6457-6f36-bd01f8367ab1.png" width="350">

下図は、[以前の記事](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%8C%E4%BD%9C%E6%88%90%E3%81%95%E3%82%8C%E3%82%8B%E9%A0%86%E7%95%AA)で紹介したゲーム木の一部を再帰呼び出しで作成した場合にノードが作成される順番を表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3b5a59ac-cfbd-b7ef-2927-d534fa012542.png" width="250">

両者を見比べるとわかると思いますが、どちらも同じ順番で木のノードの処理を行っています。`fib_by_tr` は、その関数の中で __複数回__ の `fib_by_br` を __再帰呼び出し__ しているので、先程説明した __多重再帰__ です。このように、__多重再帰__ では、__深さ優先アルゴリズム__ で処理が行われるので、ゲーム木の作成の処理も、多重再帰によって、深さ優先アルゴリズムで作成することができます。

そこで、多重再帰でゲーム木を作成するように `create_tree_by_df` を修正することにします。再帰呼び出しでは、ゲーム木を作成する処理の中の、__特定のノードに対する処理のみを記述__ するので、__そのノード__ を代入する __仮引数を用意__ する必要があります。そこで、その仮引数の名前を __`N`__ とします。

多重再帰を使った `create_tree_by_df` は、下記のように定義することができます。

* __1 行目__：処理を行うノードを代入する `N` を追加する
* __2 行目__：ゲームの決着がついてない場合のみ、子ノードが存在するので、そのことを判定する。なお、ゲームの決着がついていない場合は何もする必要はないので、else を記述する必要はない
* __3、4 行目__：合法手の一覧を計算し、合法手を順番に取り出す繰り返し処理を行う
* __5 ~ 7 行目__：`N` のゲーム盤を表す `N.mb` をコピーし、取り出した合法手を着手し、その局面を表すノードを作成する
* __8 行目__：作成したノードを `N` の子ノードに追加する
* __9 行目__：作成したノードを実引数に記述して、`create_tree_by_df` を再帰呼び出しすることで、そのノードに対する処理を行う。この再帰呼び出しは、__子ノードの数だけ行われる__ ので、`create_tree_by_df` は __多重再帰__ である

```python
 1  def create_tree_by_df(self, N):
 2      if N.mb.status == Marubatsu.PLAYING:
 3          legal_moves = N.mb.calc_legal_moves()
 4          for x, y in legal_moves:
 5              mb = deepcopy(N.mb)
 6              mb.move(x, y)
 7              node = Node(mb, parent=N, depth=N.depth + 1)
 8              N.insert(node)
 9              self.create_tree_by_df(node)
10            
11  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```python
def create_tree_by_df(self, N):
    if N.mb.status == Marubatsu.PLAYING:
        legal_moves = N.mb.calc_legal_moves()
        for x, y in legal_moves:
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
            self.create_tree_by_df(node)
            
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

`create_tree_by_df` を修正したので、それにあわせて、`create_tree_by_df` を呼び出す `__init__` メソッドを下記のプログラムのように修正する必要があります。

* __8 行目__：実引数にルートノードを記述するように修正する

```python
 1  def __init__(self, algo="bf"):
 2      self.algo = algo
 3      Node.count = 0
 4      self.root = Node(Marubatsu())
 5      if self.algo == "bf":  
 6          self.create_tree_by_bf()
 7      else:
 8          self.create_tree_by_df(self.root)
 9        
10  Mbtree.__init__ = __init__
```

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

```python
def __init__(self, algo="bf"):
    self.algo = algo
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
    else:
        self.create_tree_by_df(self.root)
        
Mbtree.__init__ = __init__
```
</details>

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

```diff_python
def __init__(self, algo="bf"):
    self.algo = algo
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
    else:
-       self.create_tree_by_df()
+       self.create_tree_by_df(self.root)
        
Mbtree.__init__ = __init__
```
</details>

実行結果は先ほどと同じなので省略しますが、下記のプログラムで `create_tree_by_df` でゲーム木を作成した Mbtree クラスのインスタンスを GUI で表示することができます。

```python
mbtree_df = Mbtree(algo="df")
mbtree_gui = Mbtree_GUI(mbtree_df)
```

### プログラムを簡潔に記述できる理由

下記は修正前と修正後の `create_tree_by_df` のプログラムです。再帰呼び出しによるプログラムのほうが、プログラムを簡潔に記述できていることを確認して下さい。

```python
# while 文による実装
def create_tree_by_df(self):
    N = self.root
    
    while N is not None:
        legal_moves = N.mb.calc_legal_moves()
        childnum = len(N.children)
        if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
            x, y = legal_moves[childnum]
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
            N = node
        else:
            N = N.parent

# 再帰呼び出しによる実装
def create_tree_by_df(self, N):
    if N.mb.status == Marubatsu.PLAYING:
        legal_moves = N.mb.calc_legal_moves()
        for x, y in legal_moves:
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
            self.create_tree_by_df(node)
            
Mbtree.create_tree_by_df = create_tree_by_df            
```

再帰呼び出しによってプログラムを簡潔に記述できる理由は以下の通りです。

1 つ目の理由は、下記のように、__まだ処理を行っていない子ノードを探す処理__ が __for 文で簡潔に記述できる__ というものです。なお、上記の while 文による実装では、比較的簡潔にまだ処理を行っていない子ノードを探す処理を記述できていますが、多くの場合はこのように簡潔にその処理を記述できるとは限らないので、__この性質はかなり大きな利点です__。

* 再帰呼び出しでは、for 文によって子ノードに対する処理を順番に行う
* for 文のブロックの処理では、子ノードを実引数として再帰呼び出しを行う
* 再帰呼び出しの処理が終了すると、for 文によって次の子ノードに対する処理が行われる

2 つ目の理由は、下記のように、__親ノードを辿る処理を記述する必要がない__ 点です。

* `create_tree_by_df` の再帰呼び出しは、親ノードを処理する `create_tree_by_df` から呼び出される
* 従って、`create_tree_by_df` の処理が終了すると、親ノードを処理する `create_tree_by_df` に処理が戻る
* そのため、親ノードを辿る処理をプログラムで記述する必要はない

下記の修正版の `create_tree_by_df` プログラムに、まだ処理が行われていない子ノードを探す処理や、親ノードを辿る処理が記述されていないことを確認して下さい。また、下記のプログラムでは、Node クラスの __`parent` 属性は記述されていません__。そのため、__Node__ クラスに __`parent` 属性が存在しなくても正しく動作__ します。


```python
def create_tree_by_df(self, N):
    if N.mb.status == Marubatsu.PLAYING:
        legal_moves = N.mb.calc_legal_moves()
        for x, y in legal_moves:
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
            self.create_tree_by_df(node)
            
Mbtree.create_tree_by_df = create_tree_by_df
```

:::note warn
* 深さ優先アルゴリズムでは、__子ノードの処理が完了した後__ で、__親ノードの処理へ戻る__ 処理を行う必要があるが、その処理は、__子ノードの処理を行う関数呼び出し__ によって __自動的に行われる__
* 子ノードの処理が完了した後で、__次の子ノードの処理を行う__ 処理は、__親ノードを処理する関数の中__ で、__for 文や while 文__ を使って行われる
:::

### `nodelist` などの計算

Mbtree_Anim クラスなどで必要になる、元の `create_tree_by_df` で計算していた `nodelist` などを計算するように修正します。元の `create_tree_by_df` では、その関数のブロックの中でそれらの変数の初期化を行っていましたが、再帰呼び出しの場合は、最初に `create_tree_by_df` を呼び出す前にその処理を行う必要があります。下記は、そのように `__init__` メソッドを修正したプログラムです。

* __8 ~ 12 行目__：それぞれの変数を初期化する処理を記述する。この部分は、修正前の `create_tree_by_df` の最初に記述されていた内容と同じである

```python
 1  def __init__(self, algo="bf"):
 2      self.algo = algo
 3      Node.count = 0
 4      self.root = Node(Marubatsu())
 5      if self.algo == "bf":  
 6          self.create_tree_by_bf()
 7      else:
 8          self.nodelist = [self.root]
 9          self.nodelist_by_depth = [[] for _ in range(10)]
10          self.nodelist_by_depth[0].append(self.root)
11          self.nodenum = 0
12          self.create_tree_by_df(self.root)
13        
14  Mbtree.__init__ = __init__
```

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

```python
def __init__(self, algo="bf"):
    self.algo = algo
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
        
Mbtree.__init__ = __init__
```
</details>

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

```diff_python
def __init__(self, algo="bf"):
    self.algo = algo
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
    else:
+       self.nodelist = [self.root]
+       self.nodelist_by_depth = [[] for _ in range(10)]
+       self.nodelist_by_depth[0].append(self.root)
+       self.nodenum = 0
        self.create_tree_by_df(self.root)
        
Mbtree.__init__ = __init__
```
</details>

次に、`create_tree_by_df` を以下のように修正します。

* __9 ~ 11 行目__：それぞれの属性の値を更新する。この部分も、修正前の `create_tree_by_df` に記述されていた内容と同じである

```python
 1  def create_tree_by_df(self, N):
 2      if N.mb.status == Marubatsu.PLAYING:
 3          legal_moves = N.mb.calc_legal_moves()
 4          for x, y in legal_moves:
 5              mb = deepcopy(N.mb)
 6              mb.move(x, y)
 7              node = Node(mb, parent=N, depth=N.depth + 1)
 8              N.insert(node)
 9              self.nodelist.append(node)
10              self.nodelist_by_depth[node.depth].append(node)
11              self.nodenum += 1
12              self.create_tree_by_df(node)
13            
14  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```python
def create_tree_by_df(self, N):
    if N.mb.status == Marubatsu.PLAYING:
        legal_moves = N.mb.calc_legal_moves()
        for x, y in legal_moves:
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
            self.nodelist.append(node)
            self.nodelist_by_depth[node.depth].append(node)
            self.nodenum += 1
            self.create_tree_by_df(node)
            
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_python
def create_tree_by_df(self, N):
    if N.mb.status == Marubatsu.PLAYING:
        legal_moves = N.mb.calc_legal_moves()
        for x, y in legal_moves:
            mb = deepcopy(N.mb)
            mb.move(x, y)
            node = Node(mb, parent=N, depth=N.depth + 1)
            N.insert(node)
+           self.nodelist.append(node)
+           self.nodelist_by_depth[node.depth].append(node)
+           self.nodenum += 1
            self.create_tree_by_df(node)
            
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

上記の修正後に、下記のプログラムで `create_tree_by_df` でゲーム木を作成した Mbtree クラスのインスタンスを使って、Mbtree_Anim でアニメーションを表示することができます。


```python
from tree import Mbtree_Anim
mbtree_df = Mbtree(algo="df")
mbtree_anim = Mbtree_Anim(mbtree_df)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1eeefb5b-1f56-878d-69ed-78f69e89ccb0.png" width="300">

## トップダウンな繰り返し処理による実装

木構造に対する __深さ優先アルゴリズム__ による __トップダウン__ な繰り返し処理は、以下のようなアルゴリズムで行います。ただし、次に処理を行うノードを N とします。

__ボトムアップ__ な繰り返し処理との __違い__ は、ノードに対する処理は、__子ノードの処理を行った後で行う__ 点です。

1. N をルートノードとする
2. N の子ノードが存在しない場合は、そのノードの処理を行い、手順 4 へ移動する
3. N の子ノードが存在する場合は、子ノードのうち、まだ処理を行っていない子ノードが存在するかどうかを判定する
    1. 処理を行っていない子ノードが存在する場合は、その中から 1 つを選び、そのノードを N として手順 2 に戻る
    2. 処理を行っていない子ノードが存在しない場合は、__子ノードが行なった処理の結果に対する処理を行う__
4. 親ノードが存在するかを判定する
    1. 親ノードが存在する場合は、親ノードを N として手順 2 に戻る
    2. 親ノードが存在しない場合は、処理を終了する

そこで、トップダウンな再帰呼び出しを使って計算を行うように `calc_node_height` を修正することにします。

先程の while 文を使ってボトムアップな手順で記述した `calc_node_height` では、部分木の __ルートノード__ を __`centernode`__ という仮引数に代入していました。一方、再帰呼び出しでは、__特定のノードに対する処理のみを記述__ するので、__そのノードを代入する仮引数__ を用意する必要があります。そこで、仮引数の名前を `centernode` から __`N` に変更__ することにします。

なお、部分木の深さを代入する仮引数 `maxdepth` は、再帰呼び出しの処理でも必要となるので、そのまま利用することにします。

次に、再帰呼び出しでの `calc_node_height` 行う処理について説明します。

__`N`__ に __子ノードが存在しない__ 場合か、__`maxdepth` と同じ深さ__ の場合は、__子ノードを描画しない__ ので __高さは 4__ になります。

`N` に __子ノードが存在する__ 場合の __高さ__ は、以下のような考え方で計算できます。

* ノードの高さは __子ノードの高さの合計__ で計算できる
* トップダウンな繰り返し処理では、上記の手順 3-2 からわかるように、__子ノードの処理の結果に対して__ 処理を行う
* 子ノードの処理は、再帰呼び出しによって行う
* 従って、`calc_node_height` が、処理を行った __ノードの高さ__ を __返り値として返す__ ようにすれば、`N` の子ノードの処理を行うために再帰呼び出しを行った `calc_node_height` の返り値が __子ノードの高さを表す__ ようになる
* __その合計を計算__ すれば、__`N` の高さを計算できる__

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

* __1 行目__：仮引数 `centernode` の名前を `N` に修正する
* __2 ~ 4 行目__：`N` の子ノードが存在しない場合か、`N` の深さが `maxdepth` の場合は子ノードを描画しないので、ノードの高さを表す `height` 属性に 4 を代入し、4 を返す
* __6 行目__：子ノードの高さの合計を計算するための `height` を `0` で初期化する
* __7 行目__：子ノードに対して for 文で繰り返し処理を行う
* __8 行目__：子ノードを実引数として再帰呼び出しを行う。その返り値は、子ノードの高さを表すので、`height` に返り値の値を加算する
* __9 行目__：子ノードに対する繰り返し処理が終了した時点で、`height` に子ノードの高さの合計が代入されているので、`N` の `height` 属性にその値を代入する
* __10 行目__：`height` を返り値として返す

```python
 1  def calc_node_height(self, N, maxdepth):
 2      if len(N.children) == 0 or N.depth == maxdepth:
 3          N.height = 4
 4          return 4
 5   
 6      height = 0
 7      for childnode in N.children:
 8          height += self.calc_node_height(childnode, maxdepth)
 9      N.height = height
10      return height
11
12  Mbtree.calc_node_height = calc_node_height
```

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

```python
def calc_node_height(self, N, maxdepth):
    if len(N.children) == 0 or N.depth == maxdepth:
        N.height = 4
        return 4
    
    height = 0
    for childnode in N.children:
        height += self.calc_node_height(childnode, maxdepth)
    N.height = height
    return height

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

`calc_node_height` の仮引数の名前を変更したので、`calc_node_height` を呼び出す `draw_subtree` を下記のプログラムのように修正する必要があります。

* __6 行目__：キーワード引数 `centernode=centernode` を `N=centernode` に修正する

```python
1  def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):
2      self.nodes_by_rect = {}
3
4      if centernode is None:
5          centernode = self.root
6      self.calc_node_height(N=centernode, maxdepth=maxdepth)
元と同じなので省略
7
8  Mbtree.draw_subtree = draw_subtree
```

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

```python
def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):
    self.nodes_by_rect = {}

    if centernode is None:
        centernode = self.root
    self.calc_node_height(N=centernode, maxdepth=maxdepth)
    width = 5 * (maxdepth + 1)
    height = centernode.height
    parent = centernode.parent
    if parent is not None:
        height += (len(parent.children) - 1) * 4
        parent.height = height
    if ax is None:
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")        
    
    nodelist = [centernode]
    depth = centernode.depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        if parent is not None:
            dy = parent.children.index(centernode) * 4
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
                childnodelist.append(None)
            else:
                dx = 5 * node.depth
                emphasize = node is selectednode
                rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = node
                dy += node.height
                if len(node.children) > 0:  
                    childnodelist += node.children
                else:
                    childnodelist.append(None)
        depth += 1
        nodelist = childnodelist
        
    if parent is not None:
        dy = 0
        for sibling in parent.children:
            if sibling is not centernode:
                sibling.height = 4
                dx = 5 * sibling.depth
                rect = sibling.draw_node(ax, maxdepth=sibling.depth, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = sibling
            dy += sibling.height
        dx = 5 * parent.depth
        rect = parent.draw_node(ax, maxdepth=maxdepth, size=size, lw=lw, dx=dx, dy=0)
        self.nodes_by_rect[rect] = parent
    
        node = parent
        while node.parent is not None:
            node = node.parent
            node.height = height
            dx = 5 * node.depth
            rect = node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
            self.nodes_by_rect[rect] = node

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

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

```diff_python
def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):
    self.nodes_by_rect = {}

    if centernode is None:
        centernode = self.root
-   self.calc_node_height(centernode=centernode, maxdepth=maxdepth)
+   self.calc_node_height(N=centernode, maxdepth=maxdepth)
元と同じなので省略

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

実行結果は同じなので省略しますが、上記の修正後に、下記のプログラムでアニメーションを正しく表示できることが確認できます。

```python
mbtree_anim = Mbtree_Anim(mbtree_df)
```

### プログラムを簡潔に記述できる理由

下記は修正前と修正後の `calc_node_height` のプログラムを並べたものです。修正後のほうが、__かなり簡潔に記述できている__ ことを確認して下さい。

```python
# 修正前
def calc_node_height(self, centernode, maxdepth):
    nodelist = [centernode]
    depth = centernode.depth
    # 各深さのノードのリストを記録する変数を初期化する
    nodelist_by_depth = [None] * centernode.depth
    nodelist_by_depth.append(nodelist)
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            childnodelist += node.children
        nodelist_by_depth.append(childnodelist)
        nodelist = childnodelist
        depth += 1
    
    for depth in range(maxdepth, centernode.depth - 1, -1):
        for node in nodelist_by_depth[depth]:
            if depth == maxdepth:
                node.height = 4
            else:
                node.calc_height()   
                
# 修正後
def calc_node_height(self, N, maxdepth):
    if len(N.children) == 0 or N.depth == maxdepth:
        N.height = 4
        return 4
    
    height = 0
    for childnode in N.children:
        height += self.calc_node_height(childnode, maxdepth)
    N.height = height
    return height
```

再帰呼び出しによってプログラムを簡潔に記述できる理由は、先程の `create_tree_by_df` で説明した理由に加えて、__各深さのノードの一覧を計算しておく必要がない__ 点です。また、各深さのノードの一覧を計算しておく必要がないので、先程説明した __`node_list_by_depth` が原因__ となるような __バグが発生することもありません__。

## ボトムアップとトップダウンな処理の記述場所

深さ優先アルゴリズムを再帰呼び出しで記述する場合は、__ボトムアップ__ な処理は、__再帰呼び出しが行われた順番__ に処理を行う必要があるため、その処理は再帰呼び出しの関数の中で、__再帰呼び出しを行う処理の前__ に記述する必要があります。実際に `create_tree_by_df` では、再帰呼び出しを行う処理の前で、子ノードを作成する処理を記述しています。

一方、__トップダウン__ な処理の場合は、__末端の再帰呼び出しから逆の順番__ で処理を行う必要があるため、その処理は再帰呼び出しの関数の中で、__再帰呼び出しを行った後__ で記述する必要があります。実際に `calc_node_height` では、子ノードの高さを計算する再帰呼び出しが __終了した際に得られる返り値を使って__ 高さの計算を行っています。

なお、トップダウンな再帰呼び出しを行う `fib_by_tr` では、下記のプログラムのように __return の後__ に `fib_by_tr(n - 1) + fib_by_tr(n - 2)` という __再帰呼び出しが記述されている__ ので再帰呼び出しの前に処理が行われているように見えるかもしれません。しかし、この式は実際には `fib_by_tr(n - 1)` と `fib_by_tr(n - 2)` の再帰呼び出しが行われた結果得られた __返り値を使って計算している__ ので、再帰呼び出しを行った後で行われた処理です。

```python
return fib_by_tr(n - 1) + fib_by_tr(n - 2)
```

:::note warn
再帰呼び出しでは、ボトムアップな処理は再帰呼び出しの処理の前に記述し、トップダウンな処理は再帰呼び出しの処理の後で記述する。
:::

## 深さ優先アルゴリズムの性質

__深さ優先アルゴリズム__ は、__処理の流れがわかりづらい__ という利点はありますが、プログラムの記述を幅優先アルゴリズムよりは __簡潔に記述できる__ という利点があります。

また、深さ優先アルゴリズムでは、幅優先アルゴリズムのように、大量のノードを記憶しておく必要がないので、__メモリの消費が大幅に少なくて済む__ という利点もあります。

具体的には、深さ優先アルゴリズムでは、__繰り返しのたびに一つ深い深さのノードの計算を行います__。また、ノードの処理が終了した時点で、__親ノードへ処理が戻る__ ので、__記憶しておく必要があるデータ__ は、最大でも __ルートノードから、最も深いノードまでのデータ__ だけで済むので、幅優先アルゴリズムよりは圧倒的に少ないメモリ消費で済みます。なお、__データの記憶__ は、関数が呼び出された際に作成される、__[ローカルな名前空間](https://qiita.com/ysgeso/items/cd3e1c0731b859bf5e2c#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E5%90%8D%E5%89%8D%E7%A9%BA%E9%96%93)__ によって行われます。以前の記事で説明したように、ローカルな名前空間は、__関数が作られてからその関数の処理が終了するまでの間存在する__ ので、再帰呼び出しで呼び出された関数の処理が終了するまでの間は、__呼び出し元の関数だけでなく__、最初に呼び出された再帰呼び出しの関数までさかのぼった、__すべての関数の名前空間が残り続けます__。

なお、同じ木構造のデータに対して計算を行うノードの数は、幅優先アルゴリズムでも、深さ優先アルゴリズムでも変わらないので、__計算時間はどちらもほぼ同じ__ です。

# 木構造のデータに対する繰り返し処理に関する補足

木構造のデータに対する繰り返し処理に関するいくつかの補足説明を行います。

## 幅優先と深さ優先アルゴリズムのどちらを使うべきか

今回の記事で説明したように、木構造のデータに対する繰り返し処理は、__深さ優先アルゴリズムのほうが__、プログラムの記述のしやすさや、消費メモリが少ないなど、__多くの利点__ があります。そのため、__どちらのアルゴリズムを利用しても構わない__ ような場合は、__深さ優先アルゴリズムを再帰呼び出しを使って記述する__ と良いでしょう。

ただし、幅優先アルゴリズムが必要な場合もあるので、__常に深さ優先アルゴリズムを使えば良いというわけではない__ 点に注意が必要です。

## 再帰呼び出しの欠点に関する補足

上記で再帰呼び出しを使って記述すると良いと説明しましたが、以前の記事で説明した、再帰呼び出しには __[繰り返しの回数に制限がある](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%81%AB%E3%82%88%E3%82%8B%E7%84%A1%E9%99%90%E3%83%AB%E3%83%BC%E3%83%97%E3%81%8C%E3%82%A8%E3%83%A9%E3%83%BC%E3%81%AB%E3%81%AA%E3%82%8B%E7%90%86%E7%94%B1)__ という欠点と、__[処理時間が for 文や while 文よりも若干長くなる](https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee#%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E9%81%95%E3%81%84)__ という欠点がある点が気になっている人がいるかもしれません。

__木構造のデータ__ に対する繰り返し処理に関して言えば、__それらの欠点はあまり問題にはなりません__。その理由について説明します。

[前回の記事](https://qiita.com/ysgeso/items/9303214ec798a920174e#%E5%88%86%E5%B2%90%E3%81%99%E3%82%8B%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97%E5%87%A6%E7%90%86%E3%81%AE%E5%87%A6%E7%90%86%E6%99%82%E9%96%93)で説明したように、__分岐する繰り返し処理__ は、繰り返しの __回数が増える__ と __処理の数が爆発的に増える__ という性質があります。実際に木構造のデータは、__深さが深くなると__ ノードの数が大きくなりすぎるため、時間がかかりすぎるという理由で __計算を行うことが実質的に不可能__ になります。そのため、木構造に対して再帰呼び出しを使う際に、繰り返しの回数が __問題になることはほとんどありません__。

処理時間が長くなる原因は、関数呼び出しの処理に時間がかかることですが、木構造のデータに対して for 文や while 文を使って繰り返し処理を記述する場合は、再帰呼び出しで記述する際には必要のない、ノードの一覧を記録する処理などが必要になります。それらの処理にかかる時間を考慮すると、多くの場合で両者の間で処理時間に大きな違いは生じません。なお、再帰呼び出しでは、それらの処理は関数のローカルな名前空間によって行われます。

## ボトムアップとトップダウンの両方を行う繰り返し処理

これまでの例は、繰り返し処理をボトムアップとトップダウンのいずれかの方法で行うものばかりでしたが、__ボトムアップとトップダウンの両方を行う__ 繰り返し処理も存在します。例えば、ゲーム木の作成と、ノードの高さの計算を __同時に行う場合__ などです。

そのような処理を再帰呼び出しで行う場合は、ボトムアップな処理を再帰呼び出しの前に記述し、トップダウンな処理を再帰呼び出しの後に記述します。

## 深さによって異なる処理を行う場合

〇×ゲームのゲーム木は、__どのノードも__ 〇×ゲームの局面という、__同一の種類の情報__ を表す木構造ですが、__そうではない木構造のデータも多数存在__ します。

その例が、今回の記事の最初で紹介した〇×ゲームのゲーム盤や、学校の生徒を表す木構造で、以下のように __深さによって__ ノードが表す __データが異なります__。

| 深さ | ゲーム盤 | 学校の生徒 |
|:-:|:--|:--|
| 0  | ゲーム盤全体  | 学校  |
| 1  | 行のデータ  | 学年  |
| 2  | セルのデータ  | クラス  |
| 3  |  | 生徒  |

__再帰呼び出し__ による繰り返し処理は、対象となるデータの種類がすべて同じ場合は向いていますが、上記のような __異なるデータ__ に対して行う場合は __あまり向いていません__。このような場合は、再帰呼び出しではなく、__for 文や while 文__ による繰り返し処理を __入れ子にして記述__ するのが一般的です。例えば、〇×ゲームのゲーム盤の場合は、以下のような for 文を入れ子にしたプログラムを記述しました。

```python
# ここにゲーム盤全体に対するボトムアップな処理を記述する
for x in range(3):
    # ここに x 列に対するボトムアップな処理を記述する
    for y in range(3):
        # ここに (x, y) のマスに対する処理を記述する
    # ここに x 列に対するトップダウンな処理を記述する
# ここにゲーム盤全体に対するトップダウンな処理を記述する
```

これまでの記事では説明していませんでしたが、上記の処理は下記の順番で繰り返し処理が行われるので、__深さ優先アルゴリズム__ による繰り返し処理です。

* x を 0 として、y を 0 から 2 まで計算する
* x を 1 として、y を 0 から 2 まで計算する
* x を 2 として、y を 0 から 2 まで計算する

また、上記のコメントに記述したように、for 文の __前後のどこにプログラムを記述するか__ によって、__どのノードに対する処理__ であるかと、__ボトムアップとトップダウン__ の __どちらの処理であるか__ が決まります。

## 今回の記事のまとめ

今回の記事では、木構造で表現できるデータに対する分岐する繰り返し処理について、以下の分類で記述する方法とその性質を説明しました。

* 幅優先アルゴリズムと深さ優先アルゴリズムで記述する場合
* ボトムアップな手順で記述する場合と、トップダウンな手順で記述する場合
* for 文や while 文で記述する場合と、再帰呼び出しで記述する場合

繰り返し処理は、木構造以外の様々なデータに対して行うことができますが、〇×ゲームの AI に必要な繰り返し処理は当面の間はゲーム木を表す木構造のデータなので、繰り返し処理に関する説明は今回の記事で一旦終了し、次回の記事からは、〇×ゲームのゲーム木を使った AI の作成に話を戻します。

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

今回の記事で作成した `mbtree_bf` と `mbtree_df` の中身は、以前にファイルに保存したデータと全く同じなので、改めてファイルに保存することはしません。

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

# 次回の記事

https://qiita.com/ysgeso/items/3400391d2637eafc8899

[^1]:木構造は、グラフ構造の一種です
[^2]:例えば、それぞれのノードに、処理が行われたかどうかを表す属性を追加するという方法などが考えられるでしょう