Pythonで〇×ゲームのAIを一から作成する　その99　深さ優先アルゴリズムによるゲーム木の生成

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1

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

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

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

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

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

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

# Mbtree のインスタンスの保存と読込

今回の記事では、ゲーム木を深さ優先アルゴリズムで作成する方法を紹介しますが、その前に Mbtree クラスのインスタンスをファイルに保存できるようにします。

Mbtree クラスのインスタンスの作成には 30 秒ほど時間がかかります。これまでの記事では、毎回 Mbtree クラスのインスタンスの作成を作成していたため、毎回 30 秒ほど待たされることになっていましたが、__Mbtree クラスのインスタンスをファイルに保存__ し、ファイルから読み込むことができるようにすれば、__待たされる時間を減らす__ ことができます。

## `save` メソッドの実装

Mbtree クラスのインスタンスのファイルへの保存は、[以前の記事](https://qiita.com/ysgeso/items/5e5b2fdaf9eda23a9230#pickle-%E3%81%AB%E3%82%88%E3%82%8B%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E4%BF%9D%E5%AD%98)で説明した pickle モジュールを使って行うことができるので、下記のようなメソッドを定義する事にします。

__名前__：保存（save）を行うので、`save` という名前にする
__処理__：Mbtree クラスのインスタンスをファイルに保存する
__入力__：保存するファイルのパスを仮引数 `fname` に代入する。ただし、ファイルのパスに拡張子は含めないものとする
__出力__：なし

下記は、`save` メソッドの定義です。セーブファイルの拡張子は、__他の pickle で保存したデータと区別ができる__ ように __.mbtree__ としました。

* __5 行目__：[`with`](https://qiita.com/ysgeso/items/5e5b2fdaf9eda23a9230#with-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E3%81%AE%E5%87%A6%E7%90%86) を使って、`fname` の末尾に拡張子である .mbtree を加えたファイルを、[書き込みとバイナリモード](https://qiita.com/ysgeso/items/5e5b2fdaf9eda23a9230#%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E3%81%AE%E3%82%AA%E3%83%BC%E3%83%97%E3%83%B3)で開く
* __6 行目__：自分自身のインスタンスを `pickle.dump` を使ってファイルに保存する
* __7 行目__：保存が完了したことを表すメッセージを表示する

```python
1  from tree import Mbtree 
2  import pickle
3
4  def save(self, fname):
5      with open(f"{fname}.mbtree", "wb") as f:
6          pickle.dump(self.root, f)
7          print("save completed.")
8        
9  Mbtree.save = save 
```

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

```python
from tree import Mbtree 
import pickle

def save(self, fname):
    with open(f"{fname}.mbtree", "wb") as f:
        pickle.dump(self, f)
        print("save completed.")
        
Mbtree.save = save 
```
</details>

上記の実行後に、下記のプログラムを実行することで、Mbtree クラスのインスタンスをファイルに保存することができます。幅優先（breadth first）アルゴリズムで作成したゲーム木を保存するので、ファイルの名前は bftree としました。

```python
mbtree = Mbtree()
mbtree.save("bftree")
```

実行結果

```
ゲーム木の生成時の表示は省略
save completed
```

上記の実行後に、プログラムが記述されている marubatsu.ipynb が保存されているフォルダの中に、__bftree.mbtree__ という名前のファイルが保存されていることを確認して下さい。

## `load` メソッドの定義

次に、保存したファイルを読み込む下記のようなメソッドを定義します。

__名前__：読み込み（load）を行うので、`load` という名前にする
__処理__：ファイルから Mbtree クラスのインスタンスを読み込む
__入力__：読み込むファイルのパスを仮引数 `fname` に代入する。ただし、ファイルのパスに拡張子は含めないものとする
__出力__：ファイルから読み込まれた Mbtree クラスのインスタンス

下記は `load` メソッドの定義です。ファイルから Mbtree クラスのインスタンスを読み込む処理に __必要な情報は `fname` だけ__ なので、このメソッドを __静的メソッド__ としました。

* __1 行目__：静的メソッドとして定義する
* __3 行目__：`with` を使って `fname` の末尾に拡張子である .mbtree を加えたファイルを、読み込みとバイナリモードで開く
* __4 行目__：`pickle.load` でファイルを読み込み、得られた Mbtree クラスのインスタンスを return 文で返り値として返す

```python
1  @staticmethod
2  def load(fname):
3      with open(f"{fname}.mbtree", "rb") as f:
4          return pickle.load(f)
5
6  Mbtree.load = load
```

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

```python
@staticmethod
def load(fname):
    with open(f"{fname}.mbtree", "rb") as f:
        return pickle.load(f)

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

上記の実行後に、下記のプログラムの 2 行目を実行することで、Mbtree クラスのインスタンスをファイルから読み込むことができます。実行結果は省略しますが、ファイルが正しく読み込まれているかどうかを確認するために、3 行目でアニメーションを行いましたので、アニメーションが正しく行われることを確認して下さい。

```python
from tree import Mbtree_Anim
mbtree_bf = Mbtree.load(fname="bftree")
mbtree_anim = Mbtree_Anim(mbtree_bf)
```

:::note alert
load メソッドを定義するのではなく、下記のように `__init__` メソッドを修正することで、`Mbtree(fname="bftree")` のように Mbtree のインスタンスの作成時にファイルを読み込むことができるようにすれば良いと思った人がいるかもしれません。

* `__init__` メソッドの仮引数に、デフォルト値が `None` のデフォルト引数 `fname` を追加する
* `fname` が `None` の場合はファイルからデータを読み込んで、その返り値を返す

具体的には下記のようなプログラムですが、このプログラムは正しく動作しません。

```python
def __init__(self, fname=None):
    if fname is None:
        Node.count = 0
        self.root = Node(Marubatsu())
        self.create_tree_by_bf()
    else:
        with open(f"{fname}.mbtree", "rb") as f:
            return pickle.load(f)  

Mbtree.__init__ = __init__
```

上記の修正後に、下記のプログラムを実行すると、実行結果のようなエラーが発生します。エラーが発生する理由は、__`__init__` メソッド__ では、return 文で __None 以外のデータを返すとエラーが発生する__ ようになっているからです。そのことは、`__init__` は None を返す（return）べき（should）であるという意味のエラーメッセージにも表記されています。

```python
mbtree = Mbtree("bftree")
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[6], line 1
----> 1 mbtree_bf = Mbtree("bftree")

TypeError: __init__() should return None, not 'Mbtree'
:::


## ファイルの圧縮

bftree.mbtree には、__50 万以上のノードの情報が記録される__ ので、__ファイルのサイズは約 100 MB__ の大きさになります。そのことを実際に確認してみて下さい。下図は、Windows のエクスプローラで bftree.mbtree を表示したものです[^1]。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a3eaa197-ecb6-fbb0-0ba4-0b3410bed279.png" width="600">

このような大きなファイルには以下のような問題があります。

* __保存や読み込みに時間がかかる__。筆者のパソコンでは bftree.mbtree の保存と読み込みにそれぞれ約 10 秒かかった
* 大きなファイルを数多く作成すると、ハードディスクなどの __記憶装置の容量を圧迫する__

デジタルデータを、その内容を変更せず[^2]に __小さくする処理__ のことを __圧縮__ と呼びます。また、圧縮されたデジタルデータを __元に戻す処理__ のことを __展開__ や、__解凍__ と呼びます。上記のような大きなデータをファイルに保存する際は、圧縮して保存することで上記の問題に対処するのが一般的です。

Python には、__ファイルを圧縮__ して保存したり、圧縮された __ファイルを展開__ して読み込むための __gzip__ というモジュールが用意されています。gzip の使い方は簡単で、__gzip モジュールをインポートした後__ で、ファイルを開く際に `open` の代わりに __`gzip.open` を記述する__ だけで行えます。

gzip の詳細については、下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/library/gzip.html

下記は、ファイルを圧縮するように `save` と `load` メソッドを修正したプログラムです。

* __4、12 行目__：`open` を `gzip.open` に修正する

```python
 1  import gzip
 2
 3  def save(self, fname):
 4      with gzip.open(f"{fname}.mbtree", "wb") as f:
 5          pickle.dump(self, f)
 6          print("save completed.")
 7       
 8  Mbtree.save = save 
 9
10  @staticmethod
11  def load(fname):
12      with gzip.open(f"{fname}.mbtree", "rb") as f:
13          return pickle.load(f)
14
15  Mbtree.load = load   
```

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

```python
import gzip

def save(self, fname):
    with gzip.open(f"{fname}.mbtree", "wb") as f:
        pickle.dump(self, f)
        print("save completed.")
        
Mbtree.save = save 

@staticmethod
def load(fname):
    with gzip.open(f"{fname}.mbtree", "rb") as f:
        return pickle.load(f)

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

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

```diff_python
import gzip

def save(self, fname):
-   with open(f"{fname}.mbtree", "wb") as f:
+   with gzip.open(f"{fname}.mbtree", "wb") as f:
        pickle.dump(self, f)
        print("save completed.")
        
Mbtree.save = save 

@staticmethod
def load(fname):
-   with open(f"{fname}.mbtree", "rb") as f:
+   with gzip.open(f"{fname}.mbtree", "rb") as f:
        return pickle.load(f)

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

上記の修正後に、下記のプログラムでファイルを保存し、作成された bftree.mbtree のファイルのサイズを確認すると、ファイルのサイズが下図の 12077 KB のように、__約 1/10 に減った__ ことが確認できます。なお、上記の修正により、__元の bftree.mbtree のファイルは利用できなくなる__ ので、下記では __同じ名前のファイルにデータを上書き__ しました。

```python
mbtree.save("bftree")
```

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/188e5204-49f8-4407-a900-8d98f37d0c83.png" width="600">

下記は、新しい bftree.mbtree を `load` メソッドで読み込み、正しく読み込めていることを確認するためにアニメーションを表示するプログラムです。実行結果は省略しますが、正しく読み込めていることを確認してみて下さい。

```python
mbtree_bf = Mbtree.load("bftree")
mbtree_anim = Mbtree_Anim(mbtree_bf)
```

:::note
ファイルが gzip で圧縮されていることを明確にしたい場合は、ファイルの拡張子として .gz が良く使われます。本記事で保存するファイルが gzip で圧縮されていることを明確にする必要はないと思いましたので、拡張子は .mbtree のままにしました
:::

:::note
__大きなファイルを圧縮、展開__ すると、__処理に時間がかかります__。上記でファイルを約 1/10 に圧縮したにもかかわらず、__保存、読み込みの時間が 1/10 にならない__ のはそのためです。

ファイルの __サイズが大きくない場合__ は、保存の際に __圧縮する必要はない__ でしょう。
:::

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

[幅優先（breadth first）アルゴリズム](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E5%B9%85%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)は、以下の手順で、ノードの __深さの浅い順番__ で、子ノードを作成する というものでした。

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

一方、__深さ優先（depth first）アルゴリズム__ は、以下の手順で、__次のノードを作成する際__ に、深いノードから __優先的__ にノードを作成します。わかりづらいかもしれませんが、深さの深い順に作成するわけではない点に注意して下さい。

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

おそらく、この説明では意味がわからないと思いますので、具体例を挙げて説明します。

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

上記では、ゲーム開始時の局面をルートノードとするゲーム木を作成しますが、深さ優先アルゴリズムで、__任意のノードをルートノード__ とする __部分木を作成__ することもできます。

具体的には上記の __手順 1__ を下記のように修正します。

1. 任意の局面を表すノードを、ルートノードとするゲーム木を作成 する

これは、[前回の記事](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#calc_node_height-%E3%81%AE%E4%BF%AE%E6%AD%A3)で、__ゲーム開始時以外の局面をルートノード__ とする __部分木の各ノードの高さ__ を、__幅優先アルゴリズムで計算__ したのと似ています。

そこで、下図の左のノードをルートノードとする部分木を、深さ優先アルゴリズムで作成する手順を説明します。なお、以降の図ではノードを下記のように表記します。

* __赤枠で表示__ されたノードが、先程のアルゴリズムの中の、子ノードを作成する処理を行う __ノード N を表す__
* __暗い色のノード__ が、__今後追加される予定のノード__ を表す

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bf16ee9e-d7e9-5f9f-1649-d2b3f65ab833.png" width="150">

__上図__ は、下記の深さ優先アルゴリズムの __手順 1、2 を行った状態__ なので、上図に対して手順 3 の処理を行っていくことにします。

### 1 回目の手順 3 の処理

手順 3 では「N にまだ作成していない子ノードが存在するか」を判定します。下図左の赤枠の N には作成していない子ノードが 3 つ存在します。

存在する場合は手順 3-1 の「作成していない子ノードが存在する場合は、その子ノードを作成し、作成した子ノードを N として手順 3 に戻る」という作業を行うので、下図右のように __赤枠の子ノードを作成__ し、__そのノードを N として手順 3 に戻ります__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bf16ee9e-d7e9-5f9f-1649-d2b3f65ab833.png" width="150">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f082c897-311e-60f0-07bf-fd372f785fea.png" width="150">

### 2、3 回目の手順 3 の処理

上図右の赤枠の N には作成していない子ノードが存在するので、__上記と同様の手順__ で左下図の赤枠の子ノードが作成され、そのノードを N とします。同様の手順で右下図の赤枠の子ノードが作成され、そのノードを N とします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9c3a336b-25ac-ad66-f389-f119f13d32a7.png" width="150">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0749f2c0-b806-0dc7-f7f8-b8899f236310.png" width="150">

### 4、5 回目の手順 3 の処理

上図右の赤枠の N には作成していない子ノードが __存在しない__ ので、左下図のようにその __親ノードが N__ になります。左下図の赤枠の N にも作成していない子ノードが存在しないので、右下図のようにその親ノードが N になります。__4、5 回目の手順 3__ の処理では __子ノードは作成されず__、__N が親ノードへ移動するだけの処理__ が行われます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/eca576f5-254f-29cc-493f-a2d725a948f2.png" width="150">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/57d02061-3bef-5700-db6f-e57f55c38e7b.png" width="150">

### 6、7 回目の手順 3 の処理

上図右の赤枠の N には作成していない子ノードが存在するので、先程と同様の手順で左下図の赤枠の子ノードが作成され、そのノードを N とします。同様の手順で右下図の赤枠の子ノードが作成され、そのノードを N とします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dc7ac7df-6572-b1f4-cc74-9aeec646a055.png" width="150">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/165390bf-8694-1c51-9d07-e8995c01c360.png" width="150">

### ノードが作成される順番

__以後は同様__ なので、それぞれの回の手順 3 で行われる処理の説明は省略し、__ノードが作成される順番__ を、画像を並べて示すことにします。右下の画像で __すべてのノードが追加された後__ で、__N がルートノード__ になり、ルートノードには作成していない子ノードが存在せず、親ノードも存在しないので __部分木が完成して処理が終了__ します。


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bf16ee9e-d7e9-5f9f-1649-d2b3f65ab833.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f082c897-311e-60f0-07bf-fd372f785fea.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9c3a336b-25ac-ad66-f389-f119f13d32a7.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0749f2c0-b806-0dc7-f7f8-b8899f236310.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dc7ac7df-6572-b1f4-cc74-9aeec646a055.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/165390bf-8694-1c51-9d07-e8995c01c360.png" width="100">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/08400f77-0c8f-b387-8011-6abe1683d4bc.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/93e8e95b-840c-34d6-92c2-ac2bc5b149dc.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f1b948e2-46cd-a111-b28a-48a64fa5e32f.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b4bf6313-4ade-b293-11b8-2641b4c17efa.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/91bd0e92-157a-cfca-f3db-27fcca9ca2e1.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/eb80aaae-1ed0-71f2-41c7-93fce15d11ff.png" width="100">　

下図は、__N が移動する順番__ を表しています。__赤い矢印__ は __子ノードを作成__ した後で N が移動する場合、__紫の矢印__ は __ノードを作成せず__ に親ノードへ N が移動する場合を表します。

図からわかるように、深さ優先アルゴリズムでは、__深いノードが優先__ してノードが作成されるので、__深さ優先__ アルゴリズムと名付けられました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8a3deb3a-1514-7593-a51a-a9ff793eb11f.png" width="350">

下図は、__幅優先アルゴリズム__ でノードを __作成する順番__ を矢印で表したものです。本記事ではゲーム木の表示幅が横に広がりすぎるため、ゲーム木のノードを左から右に浅い順に表示してきましたが、木構造は __一般的__ に __上から下に深さが浅い順にノードを表示__ するので、下図ではそのようにしました。

図からわかるように、幅優先アルゴリズムでは、__横幅を優先__ しながらゲーム木を作成するように見えるので、__幅優先__ アルゴリズムと名付けられました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/792ca55b-9cc8-1c84-f521-e45560ab55e2.png" width="350">

## 2 つのアルゴリズムの違いと使い分け

〇×ゲームの __ゲーム木を作成する場合__ は、幅優先と深さ優先の __どちらのアルゴリズムを使っても__、問題なくゲーム木を __作成することができます__。この 2 つのアルゴリズムの違いは、ゲーム木を使って評価値を計算する、__探索と呼ばれる処理__ を行う際などで __違いが生じます__。また、どちらのアルゴリズムにも __長所と短所がある__ ため、適切に __使い分ける必要があります__。それらに関しては、今後の記事で具体例を挙げて紹介する予定です。

深さ優先アルゴリズムによるプログラムの記述は、今後の記事で様々な場面で利用することになるので、深さ優先アルゴリズムを用いたゲーム木の作成を行うことにします。

# 再起呼び出しを使用しない深さ優先アルゴリズムを用いたゲーム木の作成

深さ優先アルゴリズムをプログラムで記述する際には、次回の記事で説明する __再起呼び出し__ という方法を使うのが一般的ですが、再起呼び出しは説明が必要なので、先に __再起呼び出しを使わず__ に深さ優先アルゴリズムでゲーム木を作成する方法を紹介します。

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

現状の Mbtree クラスは、幅優先アルゴリズムでゲーム木を作成するようになっているので、`__init__` メソッドを下記のプログラムのように、ゲーム木を __作成するアルゴリズム__ を __インスタンスの作成時に選択できる__ ように修正します。

* __4 行目__：デフォルト値を、幅優先（breadth first）アルゴリズムを表す `"bf"` とする、アルゴリズム（algorithm）の略である仮引数 __`algo`__ を追加する
* __5 行目__：`algo` を同名の属性に代入する
* __8、9 行目__：__`self.algo` が `"bf"`__ の場合は、`create_tree_by_bf` を呼び出して __幅優先アルゴリズム__ でゲーム木を作成する
* __8、9 行目__：`self.algo` が `"bf"` __以外の場合__ は、__`create_tree_by_df`__ を呼び出して __深さ優先アルゴリズム__ でゲーム木を作成する。なお、このメソッドはこの後で定義する

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

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

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

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()
        
Mbtree.__init__ = __init__
```
</details>

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

```diff_python
from tree import Node, Mbtree
from marubatsu import Marubatsu

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

:::note
上記のプログラムでは、`algo` に `"bf"` 以外が代入されていた場合は深さ優先アルゴリズムにしましたが、`algo` に __`"df"` が代入されていた場合のみ__ 深さ優先アルゴリズムにするという実装も考えられます。ただし、その場合は、`algo` に __`"bf"` と `"df"` 以外の値が代入__ された場合は、__エラーが発生する__ ようにプログラムを記述する必要がある点に注意して下さい。
:::

## `create_tree_by_df` の定義

次に、深さ優先アルゴリズムでゲーム木を作成する `create_tree_by_df` を定義します。なお、このメソッドの名前の df は、深さ優先を表す depth first の頭文字です。

行う処理は、先程説明した下記のアルゴリズムです。

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

また、その際に、`create_tree_by_bf` で計算した、下記のデータも計算するようにします。

| 属性名 | 意味 |
|:--|:--|
| __`nodelist`__  | ゲーム木に登録された順番で、ノードを要素に持つ list  |
| __`nodelist_by_depth`__ | それぞれの深さのノードの一覧を表す list  |
| __`nodenum`__   | ゲーム木のノードの総数  |

### 手順 1 の実装

手順 1 のルートノードの作成は `__init__` メソッド内の下記のプログラムで実装済なので、特に何も記述する必要はありません。

```python
self.root = Node(Marubatsu())
```    

### `nodelist` 属性の初期化

次に、上記の表の 3 つの属性の値を初期化する処理を記述します。

まず、`nodelist` の初期化処理について説明します。

幅優先アルゴリズムでは、ゲーム木のノードを __深さが浅い順で作成__ したので、`create_tree_by_df` では下記のプログラムのように、__`nodelist`__ をゲーム木の __作成が完了した後__ で、__各深さのノードの一覧を結合__ することで計算することができましたが、深さ優先アルゴリズムでは、ノードは __深さが浅い順に作成されない__ ので、下記の方法で `nodelist` を計算することはできません。

```python
self.nodenum = 0
self.nodelist = []
for nodelist in self.nodelist_by_depth:
    self.nodenum += len(nodelist)
    self.nodelist += nodelist
```

深さ優先アルゴリズムの場合は、__ノードを登録するたび__ に `nodelist` に __`append`__ メソッドで登録した __ノードを追加__ する必要があります。従って、下記のプログラムの 2 行目のように、__最初に `nodelist` を__、既にゲーム木に追加されている __ルートノードを要素とする list で初期化__ する必要があります。

```python
def create_tree_by_df(self):
    self.nodelist = [self.root]

Mbtree.create_tree_by_df = create_tree_by_df    
```

### `nodelist_by_depth` 属性の初期化

幅優先アルゴリズムでは、__`nodelist_by_depth`__ の各要素は、[下記のプログラム](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E5%AD%90%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E4%B8%80%E8%A6%A7%E3%81%AE%E8%A8%98%E9%8C%B2)のように、__各深さのノードの一覧を計算した後__ で、__`append`__ メソッドで __追加する__ ことで計算できましたが、深さ優先アルゴリズムでは __異なる深さのノードが次々に追加される__ ので、この方法では計算することはできません。どのように計算できるかについて少し考えてみて下さい。

```python
while len(nodelist) > 0:
    # 深さが depth の子ノードの一覧を計算する
    childnodelist = [] 
    for node in nodelist:
        if node.mb.status == Marubatsu.PLAYING:
            node.calc_children()
            childnodelist += node.children
    # 深さが depth の子ノードの一覧を nodelist_by_depth に追加する
    self.nodelist_by_depth.append(childnodelist)
    nodelist = childnodelist
    depth += 1
```

`nodelist_by_depth` は下記の方法で計算することができます。

* `nodelist_by_depth` の __各深さの要素__ に __空の list を代入__ しておく
* ゲーム木に __ノードを追加するたび__ に、`nodelist_by_depth` の __対応する深さのノードの要素__ に、その __ノードを追加__ する

下記は、そのように `create_tree_by_df` を修正したプログラムです。__ルートノードはゲーム木に追加済__ なので 4 行目の処理を記述し忘れないように注意して下さい。

* __3 行目__：`nodelist_by_depth` には、深さが 0 ~ 9 まで __10 種類__ の深さに対応するノードの一覧の情報を記録するので、リスト内包表記を利用して、__10 個の空の list__ を要素として持つ list として初期化する。なお、[`[[]] * 10` と記述してはいけない](https://qiita.com/ysgeso/items/2a436b3819bef9a6a2b4#-%E6%BC%94%E7%AE%97%E5%AD%90%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%9F-list-%E3%81%AE%E4%BD%9C%E6%88%90)点に注意すること
* __4 行目__：`nodelist_by_depth` の __深さ 0 のノードの一覧__ に、__ルートノードを追加__ する

```python
1  def create_tree_by_df(self):
2      self.nodelist = [self.root]
3      self.nodelist_by_depth = [[] for _ in range(10)]
4      self.nodelist_by_depth[0].append(self.root)
5    
6  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```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)
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_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)
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

### `nodenum` 属性の初期化


`nodenum` は、`create_tree_by_bf` では、ゲーム木の完成後に `nodelist_by_depth` から `nodelist` を計算する処理の中でその計算を行いましたが、`nodelist_by_depth` から `nodelist` を計算する処理が無くなったので、以下のような方法で計算することにします。

* ルートノードは登録済なので、最初に `nodenum` を 1 で初期化する
* ゲーム木にノードを追加する度に `nodenum` に 1 を足す

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

* __5 行目__：`nodenum` 属性を `1` で初期化する

```python
1  def create_tree_by_df(self):
2      self.nodelist = [self.root]
3      self.nodelist_by_depth = [[] for _ in range(10)]
4      self.nodelist_by_depth[0].append(self.root)
5      self.nodenum = 1
6    
7  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```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 = 1
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_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 = 1
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

なお、`create_tree_by_bf` と同様の方法で `nodenum` を計算することもできるので、そちらが良いと思った方はその方法を採用して下さい。

### 手順 2 の実装

下記の手順 2 は、下記のプログラムのように記述できます。

2\. 子ノードを作成する処理を行うノードを N と表記し、N を ルートノードで初期化する

* __2 行目__：ローカル変数 `N` にルートノードを代入する。変数の名前がわかりづらいと思った方は、`N` を別の名前に変更しても良い

```python
def create_tree_by_df(self):
元と同じなので省略
    N = self.root
    
Mbtree.create_tree_by_df = create_tree_by_df
```

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

```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
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_python
def create_tree_by_df(self):
元と同じなので省略
+   N = self.root
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

### 手順 3 の実装

下記の手順 3 を判定する方法について少し考えてみて下さい。

3\. N にまだ作成していない子ノードが存在するかを判定する

完成したゲーム木では、ゲームの __決着がついていない__ ノードには、__合法手の数だけ子ノードが存在__ します。従って、上記の手順 3 は、以下の方法で判定することができます。

* ゲームの __決着がついている場合__ は、そもそも子ノードは存在しないので、まだ作成していない子ノードは __存在しない__
* 決着が __ついていない場合__ で、N の __子ノードの数__ が __合法手の数よりも少ない場合__ は、まだ作成していない子ノードは存在し、そうでなければ存在しない

下記は、`create_tree_by_df` に手順 3 の判定を追加したプログラムです。

* __2 行目__：N の局面の合法手の一覧を計算する
* __3 行目__：N の子ノードの数を計算する
* __4 行目__：ゲーム中であり、N の子ノードの数が合法手の数より小さいことを判定する
* __5 行目__：ここに手順 3.1 の処理を記述する
* __7 行目__：ここに手順 3.2 の処理を記述する

```python
1  def create_tree_by_df(self):
元と同じなので省略
2      legal_moves = N.mb.calc_legal_moves()
3      childnum = len(N.children)
4      if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
5          pass
6      else:
7          pass
8    
9  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```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
    
    legal_moves = N.mb.calc_legal_moves()
    childnum = len(N.children)
    if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
        pass
    else:
        pass
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_python
def create_tree_by_df(self):
元と同じなので省略
+   legal_moves = N.mb.calc_legal_moves()
+   childnum = len(N.children)
+   if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
+       pass
+   else:
+       pass
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

### 手順 3.1 の実装

下記の手順 3.1 の処理を実装する方法について少し考えてみて下さい。

3.1. 作成していない子ノードが存在する場合は、その子ノードを作成し、作成した子ノードを N として手順 3 に戻る

手順 3.1 の処理を行った後で __手順 3 に戻る必要がある__ ので、__繰り返し処理__ を記述する必要があります。また、手順 3.1 では __必ず手順 3 に戻る__ という処理を行うので、while 文による __[無限ループ](https://qiita.com/ysgeso/items/d2cce68c7a32bf3790ef#%E6%89%8B%E9%A0%86-5-%E3%81%AE%E5%AE%9F%E8%A3%85%E3%81%A8-while-%E6%96%87)__ を記述することにします。なお、手順 3.2 の中に、ゲーム木の完成による __無限ループの終了の条件がある__ ので、無限ループを記述しても問題はありません。

N の子ノードは、合法手の一覧である `legal_moves` の __要素の順で作成する__ ことにします。その場合は、N の __作成済の子ノードの数を childnum__ とすると、`legal_moves` の中で、__0 ~ childnum 未満__ のインデックスの合法手を着手した __子ノードが作成済である__ ことを意味します。従って、次は __`legal_move[childnum]`__ の合法手の着手を行った局面を表す __ノードを作成__ して N の __子ノードに追加__ すればよいことがわかります。

子ノードの作成と追加の処理は `Node` クラスのインスタンスを作成し、`insert` メソッドを使って N の子ノードに作成したノードを追加する処理を行います。

その後、`nodelist`、`nodelist_by_depth`、`nodenum` の値を更新する処理を行う必要がある点を忘れないように注意して下さい。

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

* __4 行目__：`while True:` のブロックの中に手順 3.1、3.2 の処理を記述することで、無限ループを行うように修正する
* __8 行目__：追加する子ノードに対応する合法手の座標を計算する
* __9、10 行目__：N のノードの `Marubatsu` クラスのインスタンスの深いコピーを行い、それに対して合法手を着手して、子ノードの局面を表すデータを作成する
* __11、12 行目__：`mb` を局面、`N` を親ノード、深さを `N` のノードの深さ + 1 とするノードを作成し、N の子ノードに追加する
* __13 ~ 15 行目__：`nodelist`、`nodelist_by_depth`、`nodenum` の値を更新する
* __16 行目__：`N` を、作成した子ノードである `node` で更新する

```python
 1  from copy import deepcopy
 2
 3  def create_tree_by_df(self):
元と同じなので省略
 4      while True:
 5          legal_moves = N.mb.calc_legal_moves()
 6          childnum = len(N.children)
 7          if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
 8              x, y = legal_moves[childnum]
 9              mb = deepcopy(N.mb)
10              mb.move(x, y)
11              node = Node(mb, parent=N, depth=N.depth + 1)
12              N.insert(node)
13              self.nodelist.append(node)
14              self.nodelist_by_depth[N.depth + 1].append(node)
15              self.nodenum += 1
16              N = node
17          else:
18              pass
19    
20  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```python
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 True:
        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:
            pass
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

<details><summary><strong>修正箇所（while True によるインデントの修正は省略します）</strong></summary>

```diff_python
from copy import deepcopy

def create_tree_by_df(self):
元と同じなので省略
+   while True:
        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:
            pass
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

:::note
子ノードを作成する処理は、Node クラスの `calc_children` メソッドで行うことができるのではないかと思った人がいるかもしれませんが、このメソッドは名前が `children` のように複数形になっていることからわかるように、ノードの __全ての子ノードを作成する処理を行う__ ので、__深さ優先アルゴリズムでは利用できません__。
:::

### 手順 3.2 の実装

下記は手順 3.2 を再掲したものです。

3.2. 作成していない子ノードが存在しない場合は、親ノードが存在するかを判定する
3.2.1. 親ノードが存在する場合は、親ノードを N として手順 3 に戻る
3.2.2. 親ノードが存在しない場合は、ゲーム木が完成しているので処理を終了する

手順 3.2 下記のプログラムのように実装できます。なお、幅優先アルゴリズムでは、作成したノードの深さを表示することで途中経過を表現しましたが、__深さ優先アルゴリズムでは途中経過をうまく表示することができない__ ので、最後に作成したノードの数だけを表示するようにしました。



* __4、5 行目__：親ノードが存在しない場合は、break 文で無限ループを抜ける
* __6、7 行目__：そうでなければ、`N` に親ノードである `N.parent` を代入する
* __9 行目__：ゲーム木の作成が完了したので、作成したノードの数を表示する

```python
 1  def create_tree_by_df(self):
元と同じなので省略
 2          if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
元と同じなので省略
 3          else:
 4              if N.parent is None:
 5                  break
 6              else:
 7                  N = N.parent
 8
 9      print(f"total node num = {self.nodenum}")
10
11  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```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 True:
        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:
            if N.parent is None:
                break
            else:
                N = N.parent

    print(f"total node num = {self.nodenum}")
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_python
def create_tree_by_df(self):
元と同じなので省略
        if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
元と同じなので省略
        else:
-           pass
+           if N.parent is None:
+               break
+           else:
+               N = N.parent

+   print(f"total node num = {self.nodenum}")
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

### プログラムの改良

上記のような __`while True:`__ による無限ループのプログラムは、無限ループから __抜ける条件かがわかりづらい__ という __欠点__ があります。`create_tree_by_df` の無限ループから抜ける条件は、手順 3.2 で __`N.parent` が `None` になる場合__ ですが、以下の事から、__while 文の条件式__ を __`N` が `None` ではない__ という条件式に修正することができます。

* 最初は `N` にはルートノードが代入されるので、`None` ではない
* 手順 3.1 では `N` に作成した子ノードが代入されるので `N` は `None` にはならない
* 手順 3.2 では、`N` に親ノードが存在する場合だけ `N` に親ノードを代入するので、N は `None` にはならない
* 上記から、現状のプログラムでは `N` に `None` が代入されることはない
* 手順 3.2 で N の親ノードが `None` の場合に無限ループから抜けるが、__無限ループから抜ける代わりに `N` に `N.parent` を代入__ すると、__`N` に `None` が代入__ される。従って、そのように修正し、`while` 文の __条件式を `N is not None` に修正__ することでも、ゲーム木が完成した際に無限ループから抜けることができる

下記は、そのように `create_tree_by_df` を修正したプログラムです。先ほどと比べて、while 文の __繰り返しが終了する条件がわかりやすくなった__ ことを確認して下さい。

* __2 行目__：while 文の条件式を、`N` が `None` ではないという条件に修正する
* __7 行目__：手順 3.2 の処理を、常に `N` に親ノードを代入する処理に修正する

```python
 1  def create_tree_by_df(self):
元と同じなので省略
 2      while N is not None:
 3          legal_moves = N.mb.calc_legal_moves()
 4          childnum = len(N.children)
 5          if N.mb.status == Marubatsu.PLAYING and childnum < len(legal_moves):
元と同じなので省略
 6          else:
 7              N = N.parent
 8               
 9      print(f"total node num = {self.nodenum}")
10    
11  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```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
                
    print(f"total node num = {self.nodenum}")
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_python
def create_tree_by_df(self):
元と同じなので省略
    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):
元と同じなので省略
        else:
            N = N.parent
                
    print(f"total node num = {self.nodenum}")
    
Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

:::note
この修正を行わなくても、`create_tree_by_df` は正しく動作しますが、プログラムはわかりやすく記述したほうが良いと思いましたので修正しました。
:::

## 動作の確認

上記の修正後に、下記のプログラムで深さ優先アルゴリズムでゲーム木を作成すると、実行結果から __幅優先アルゴリズムと同じ 549945 個のノードが作成された__ ことが確認できます。

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

実行結果

```
total node num = 549945
```

:::note
実際には `algo="bf"` 以外を記述すれば深さ優先アルゴリズムでゲーム木が作成されますが、わかりやすさを重視して `algo="df"` を記述しました。
:::

次に、下記のプログラムで作成したゲーム木を視覚化します。実行結果は幅優先アルゴリズムで作成したゲーム木を視覚化した場合と同じなので省略しますが、様々な操作を行い、正しく視覚化できることを確認して下さい。

```python
from tree import Mbtree_GUI
mbtree_gui = Mbtree_GUI(mbtree_df)
```

## ゲーム木の生成の過程のアニメーションの修正

次に、下記のプログラムで深さ優先アルゴリズムで作成したゲーム木の生成過程のアニメーションを表示してみることにします。実際にアニメーションを確認してみて下さい。

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

実行結果（右図は 0 ~ 19 フレームまでのアニメーションの繰り返しです）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/55de96bc-a795-8287-d160-f51aec4f1e7c.gif" width="350">

実行結果から、深さ優先アルゴリズムでのゲーム木の生成過程がうまくアニメーションで表示されるように見えますが、__少しわかりづらい__ と思った人はいないでしょうか？そう思った方は、どこがわかりづらいかを少し考えてみて下さい。

その原因の一つは、__選択されたノード__ の __子ノードが表示されない__ 点にあります。

__幅優先アルゴリズム__ の場合は、選択されたノードの __子ノード__ がゲーム木に __追加されるのは一般的にかなり先のフレーム__ になります。そのため、選択されたノードの子ノードが表示されていなくてもわかりづらくはありませんし、子ノードを表示してしまうと親ノードの兄弟ノードが表示されなくなってしまうので、[表示しないほうがわかりやすくなります](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#%E4%B8%AD%E5%BF%83%E3%81%A8%E3%81%AA%E3%82%8B%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%94%B9%E8%89%AF)。

一方、__深さ優先アルゴリズム__ の場合は、選択されたノードの __子ノード__ は、__次のフレームで作成__ されますが、上記のアニメーションでは、__表示されていなかった子ノード__ が __次のフレームで表示されて選択される__ 点がわかりづらさの原因になっています。

そこで、深さ優先アルゴリズムの場合は、__中心となるノード__ と __選択されたノード__ を __同じノードに修正__ することにします。ただし、深さが 7 以上のノードが選択状態になった場合は、深さ 6 のノードを中心となるノードにする点は変更しません。

:::note
選択されたノードの深さが浅い場合は、アニメーションのゲーム木の表示がフレームごとに大きく変化するので、どうしてもアニメーションがわかりにくくなると思いますが、これは現状のアニメーションの方法ではどうしようもないと思います。

深さが 6 以上のノードが選択されたノードになった場合は、アニメーションのゲーム木の表示がフレームごとにほとんど変化しなくなるので、わかりやすくなると思います。深さ優先アルゴリズムの生成の過程を理解するためには、そのようなノードが選択されたフレームの挙動を見ると良いでしょう。
:::

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

* __5 ~ 7 行目__：ゲーム木を作成したアルゴリズムが幅優先アルゴリズムを表す `"bf"` の場合のみ、中心となるノードを選択されたノードの親ノードにするように修正する

```python
1  import matplotlib.patches as patches
2
3  def update_gui(self):
元と同じなので省略
4      self.centernode = self.selectednode
5      if self.mbtree.algo == "bf":
6          if self.centernode.depth > 0:
7              self.centernode = self.centernode.parent
元と同じなので省略
8
9  Mbtree_Anim.update_gui = update_gui
```

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

```python
import matplotlib.patches as patches

def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(0, self.height)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    self.selectednode = self.mbtree.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.mbtree.algo == "bf":
        if self.centernode.depth > 0:
            self.centernode = self.centernode.parent
    while self.centernode.depth > 6:
        self.centernode = self.centernode.parent
    if self.centernode.depth <= 4:
        maxdepth = self.centernode.depth + 1
    elif self.centernode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
    for rect, node in self.mbtree.nodes_by_rect.items():
        if node.id > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))

Mbtree_Anim.update_gui = update_gui
```
</details>

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

```diff_python
import matplotlib.patches as patches

def update_gui(self):
元と同じなので省略
    self.centernode = self.selectednode
-   if self.centernode.depth > 0:
-      self.centernode = self.centernode.parent
+   if self.mbtree.algo == "bf":
+       if self.centernode.depth > 0:
+           self.centernode = self.centernode.parent
元と同じなので省略

Mbtree_Anim.update_gui = update_gui
```
</details>

上記の修正後に、下記のプログラムでアニメーションを実行すると、実行結果の左図のように、修正前の右図と比較してアニメーションが少しわかりやすくなったことを確認して下さい。ただし、今回の修正で劇的にわかりやすさがかわることはありません。修正前の方がわかりやすいと思う人がいれば、元に戻して下さい。

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

実行結果（0 ~ 19 フレームまでのアニメーションの繰り返しです。なお、左図と右図は連動していないので、表示されるフレームがずれる場合があります）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4bea65ce-4465-cf20-2b0a-5da02600f16f.gif" width="300">
　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/55de96bc-a795-8287-d160-f51aec4f1e7c.gif" width="300">

# データの保存

下記のプログラムで深さ優先アルゴリズムで作成されたゲーム木をファイルに保存します。

```python
mbtree_df.save("dftree")
```

また、先程 Mbtree に __`algo` という属性を加えた__ ので、下記のプログラムのように、幅優先アルゴリズムで作成したゲーム木のアニメーションを行おうとすると、実行結果のように `algo` という属性がないという意味のエラーが発生します。

```python
Mbtree_Anim(mbtree_bf)
```

実行結果

```
略
Cell In[22], line 12
     10 self.selectednode = self.mbtree.nodelist[self.play.value]
     11 self.centernode = self.selectednode
---> 12 if self.mbtree.algo == "bf":
     13     if self.centernode.depth > 0:
     14         self.centernode = self.centernode.parent

AttributeError: 'Mbtree' object has no attribute 'algo'
```

そのため、実行結果は省略しますが、下記のプログラムで幅優先探索アルゴリズムでゲーム木を作成し直し、ファイルに保存し直す必要があります。

```python
mbtree_bf = Mbtree()
mbtree_bf.save("bftree")
```

なお、bftree.mbtree や dftree.mbtree は、__ファイルのサイズが大きい__ ので、それらを __利用しない回__ では、__github にそれらのファイルをアップロードしない__ ことにします。

# 今回の記事のまとめ

今回の記事では、最初にゲーム木をファイルに保存するようにしました。

次に、深さ優先アルゴリズムによるゲーム木の生成方法について説明し、これまでに学んだ方法で深さ優先アルゴリズムでゲーム木を作成するプログラムを実装しました。

次回の記事では、深さ優先アルゴリズムを実装する際に一般的に使われる、再起呼び出しについて説明します。

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


| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/099/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [tree_new.py](https://github.com/ysgeso/marubatsu/blob/master/099/tree_new.py)  |  今回の記事で更新した tree.py |
| [bftree.mbtree](https://github.com/ysgeso/marubatsu/blob/master/099/bftree.mbtree)  | 幅優先探索アルゴリズムで作成したゲーム木の保存ファイル |
| [dftree.mbtree](https://github.com/ysgeso/marubatsu/blob/master/099/dftree.mbtree)  | 深さ優先探索アルゴリズムで作成したゲーム木の保存ファイル |

# 次回の記事

https://qiita.com/ysgeso/items/9d5e9a56f5fe004dafee
 
[^1]:1 MB = 1000 KB です
[^2]:圧縮には、データを完全に元に戻すことができる可逆圧縮と、データが完全に戻らない非可逆圧縮があります。非可逆圧縮は、可逆圧縮に比べてデータをより小さくすることができるので、画像や動画など、完全に元に戻らなくても大きな問題が発生しない場合に良く使われます
[^3]:手順 1 の、ゲーム開始時の局面をルートノードとするゲーム木から作成を開始するという点だけは、幅優先アルゴリズムと同じです