Pythonで〇×ゲームのAIを一から作成する　その120　draw_subtree メソッドで表示する部分木の動的な作成

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/71a02346a63d6de28db4

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

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

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

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

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

# Mbtree_GUI の問題点

[以前の記事](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f)で、必勝の局面で最も早く勝利する着手を選択するような評価値を計算するゲーム木を作成しましたが、__現状の Mbtree_GUI__ は異なる方法で評価値を計算したゲーム木が複数あっても、その中の __1 つのゲーム木しか表示できない__ という問題があります。そこで、__表示するゲーム木のデータを選択できる__ ように Mbtree_GUI を改良することにします。

## ファイルの読み込み時間の問題

上記のような改良を行う際に問題となるのは、__ゲーム木のデータをファイルから読み込む時間__ です。ゲーム木の __部分木の表示__ は、Mbtree クラスの __`draw_subtree`__ メソッドで行いますが、その際には __ゲーム木のデータが必要__ になります。

ゲーム木のデータは、__Mbtree クラスのインスタンスを作成__ するか、下記のプログラムのように、ゲーム木のデータを __ファイルから読み込む必要__ がありますが、筆者のパソコンではインスタンスを作成する場合は約 1 分、下記のプログラムでファイルからデータを読み込む場合は 10 秒以上の時間がかかりました。

```python
from tree import Mbtree, Mbtree_GUI

mbtree = Mbtree.load("../data/aidata")
```

そのため、__複数の種類のゲーム木を Mbtree_GUI クラスで表示する__ ためには、ゲーム木のデータを __ファイルから読み込む処理__ が完了するまでの時間が __これまで以上に長くなってしまう__ という問題が発生します。

そこで、__ゲーム木のデータをファイルから読み込まず__ にゲーム木の __部分木を表示する__ ことができるようにプログラムを改良することにします。どのような方法で改良できるかについて少し考えてみて下さい。

## 部分木を表示するために必要なデータの考察

__`draw_subtree`__ メソッドは、下記のプログラムのように __中心となるノード__ を表すキーワード引数 __`centernode`__ と、表示する __部分木の深さの最大値__ を表す __`maxdepth`__ を記述して呼び出すことで部分木を表示します。例えば下記のプログラムでは実行結果のように、中心となるノードをルートノード、深さの最大値を 1 とした部分木が表示されます。

```python
mbtree.draw_subtree(centernode=mbtree.root, maxdepth=1)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c44c5285-ecac-2d51-4417-7e6b9579c83b.png" width="100">

__`draw_subtree`__ が行う処理は、ゲーム木の中から __部分木のデータを取り出して表示を行う__ というものです。そのため、ゲーム木全体のデータが無くても __表示する部分木のノードのデータをその場で作ることができれば__ 上記のような部分木を表示することが可能です。

従って、__`draw_subtree`__ の「作成済のゲーム木を使って部分木を表示する」という処理を「__表示する部分木のデータをその場で新しく作成して表示する__」ように __修正する__ ことで、ゲーム木のデータをあらかじめ作成したり、ファイルから読み込んでおく必要がなくなります。

### 動的なデータと静的なデータ

__プログラムを実行した後__ で必要に応じて __その場で作成するデータ__ の事を __動的なデータ__ と呼びます。また、動的なデータを作成することを、データを __動的に作成する__ と表現します。

動的（dynamic）の反対は静的（static）で、ファイルに保存した aidata.mbtree のように、__プログラムを実行する前__ に __あらかじめ計算__ しておいたデータは __静的なデータ__ です。

__動的なデータ__ は、そのデータが必要になるたびに作成するので、過去に作成したデータが再び必要になった場合であっても __必ず毎回作成しなければならない__ という __欠点__ がありますが、データの __作成時間が短い場合__ はそのことは __大きな問題にはなりません__。

一方、__静的なデータ__ は同じデータを何度も計算し直さなくても良いという利点がありますが、〇×ゲームのゲーム木のデータのように __データサイズが大きい場合__ はファイルから読み込むのに時間がかかる、メモリを大量に消費してしまうなどの __欠点があります__。また、__毎回計算結果が異なる__ ようなデータや、コンピューターが現実的に __扱うことができないような大きさ__ のデータ[^1]は静的なデータでは扱えません。

どちらを使うかは状況によってそれぞれの __利点と欠点を考えて選択する必要があります__。

### 部分木の動的な生成に必要な時間の考察

部分木のデータを動的に作成する処理に __長い時間がかかってしまうと意味がない__ ので、部分木のデータを作成するために __必要な時間を簡単に見積もってみる__ ことにします。

〇×ゲームのゲーム木の __ノードの数__ は[以前の記事](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E6%AD%A3%E3%81%97%E3%81%84%E5%90%84%E6%B7%B1%E3%81%95%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%95%B0%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)で説明したように __50 万以上__ もあるため、__ゲーム木の生成には約 1 分ほどの時間__ がかかります。__ゲーム木はノードを集めたデータで構成される__ ので、ゲーム木の __作成時間__ は、ゲーム木の __ノードの数にほぼ比例する__ と考えられます。そのため、例えばゲーム木の生成に 50 秒かかる場合は、__1 つあたりのノードを作成__ するために必要な時間は、50 / 50 万 = __約 0.0001 秒__ と見積もることができます。

__Marubatsu_GUI__ クラスで表示する __部分木のノードの数__ は、__多くても数十__ しかありません。それより少し多めの __100 個のノード__ から構成される部分木のデータを作成する時間は、0.0001 × 100 = 約 0.01 秒と見積もることができるので、Marubatsu_GUI クラスで部分木を表示する際に、その __部分木のデータを動的に作成__ した場合は __その処理にかかる時間はほぼ無視して良い__ と考えて良いでしょう。

# 部分木の生成処理の実装

いきなり Marubatsu_GUI で表示するための部分木を作成するのは大変なので、少しずつ実装していくことにします。

## `__init__` メソッドの修正

これまでは、__Mbtree__ クラスの __インスタンスを作成__ すると、〇×ゲームのゲーム木全体が作成されましたが、〇×ゲームの __部分木も作成できるように改良する__ ことにします。

そのために、下記のプログラムのように Mbtree クラスの __`__init__`__ メソッドに __`subtree`__ という __仮引数を追加__ し、__`True` が代入__ されていた場合は他の仮引数の値をすべて無視して __部分木（subtree）を作成する__ ように修正します。

なお、部分木を作成する処理を `__init__` メソッド内に直接記述するとプログラムがわかりづらくなるので、その処理はこの後で定義する `create_subtree` という名前のメソッドに記述することにします。

* __3 行目__：デフォルト値を `False` とする仮引数 `subtree` を追加する
* __4 ~ 6 行目__：`subtree` が `True` の場合に、部分木を作成する処理を行う `create_subtree` メソッドを呼び出し、8 行目以降の通常のゲーム木を作成する処理を行わないようにするために return 文で `__init__` メソッドの処理を終了する。

```python
 1  from tree import Mbtree, Node
 2
 3  def __init__(self, algo="bf", shortest_victory=False, subtree=False):
 4      if subtree:
 5          self.create_subtree()
 6          return
 7    
 8      self.algo = algo
元と同じなので省略
 9    
10  Mbtree.__init__ = __init__
```

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

```python
from tree import Mbtree, Node

def __init__(self, algo="bf", shortest_victory=False, subtree=False):
    if subtree:
        self.create_subtree()
        return
    
    self.algo = algo
    self.shortest_victory = shortest_victory
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_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)
        self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
    self.nodelist_by_mb = {}
    self.bestmoves_by_mb = {}
    self.calc_bestmoves(self.root)
    
Mbtree.__init__ = __init__
```
</details>

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

```diff_python
from tree import Mbtree, Node

-def __init__(self, algo="bf", shortest_victory=False):
+def __init__(self, algo="bf", shortest_victory=False, subtree=False):
+   if subtree:
+       self.create_subtree()
+       return
    
    self.algo = algo
元と同じなので省略
    
Mbtree.__init__ = __init__
```
</details>

## ルートノードから深さ 1 までの部分木の生成

まず、先程 __`mbtree.draw_subtree(centernode=mbtree.root, maxdepth=1)`__ というプログラムで表示した、__ルートノードから深さ 1 までの部分木を生成__ する処理を実装することにします。そのような部分木は下記の手順で実装できます。

1. ゲーム開始時の局面を表すノードをルートノードとして作成する
2. ゲーム開始時の局面のそれぞれの合法手を着手した局面を表すノードを作成し、ルートノードの子ノードにする

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

上記の __手順 2__ は、Node クラスの __[`calc_children`](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` などの関数でゲーム木を作成する際に計算していた __`nodelist`__ などの属性は、__`draw_subtree`__ で __部分木を表示する際に必要がない__ ので、下記のプログラムでは __計算していません__[^2]。

* __3 ~ 5 行目__：`create_subtree` を定義する
* __4 行目__：ゲーム開始時の局面を表すルートノードを作成し、`root` 属性に代入する
* __5 行目__：`calc_children` メソッドで、ルートノードの子ノードを作成する

```python
1  from marubatsu import Marubatsu
2
3  def create_subtree(self):
4      self.root = Node(Marubatsu())
5      self.root.calc_children()
6
7  Mbtree.create_subtree = create_subtree
```

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

```python
from marubatsu import Marubatsu

def create_subtree(self):
    self.root = Node(Marubatsu())
    self.root.calc_children()

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

上記を実行後に、下記のプログラムのようにキーワード引数 `subtree=True` を記述して部分木を作成し、__`draw_subtree`__ で __ルートノードから深さ 1 までの部分木を表示__ すると、実行結果の左図が表示されます。__`subtree`__ は、下記の 2 行目で __表示するノードのデータを全て含んでいる__ のでこのプログラムで正しい部分木が表示されます。

右図は先ほどのプログラムで __ゲーム木を全体を表す `mbtree`__ に対して __同じ範囲の部分木を表示__ した場合の図を再掲したものです。__同じ部分木が表示される__ ことを確認して下さい。

```python
subtree = Mbtree(subtree=True)
subtree.draw_subtree(centernode=subtree.root, maxdepth=1)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2cb3aeaa-4d78-7b31-a22b-b7a567f2d7eb.png" width="100">　　　　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c44c5285-ecac-2d51-4417-7e6b9579c83b.png" width="120">

なお、__`create_subtree`__ では、__ノードの評価値の計算を行っていない__ ので __評価値は表示されず__、__ゲーム盤の色は常に白色で表示__ されます。また、__深さ 1 のノードの子ノードを計算していない__ ので、左図ではその右に __子ノードが存在することを表す線は表示されません__。それらの表示ついては後で実装します。

## 部分木の深さの最大値の指定

次に、作成する __部分木の深さの最大値__ を指定できるようにします。そのための方法の一つに、下記のプログラムのように `__init__` メソッドに部分木の深さの最大値を表す仮引数を `maxdepth` を追加するという方法が考えられます。

```python
def __init__(self, algo="bf", shortest_victory=False, subtree=False, maxdepth=1):
略
```

しかし、この方法では部分木を作成する際に必要となるデータを代入する __仮引数を今後増やした場合__ に、__以下のような問題が発生__ します。

* そのような仮引数を追加するたびに __`__init__` メソッドを修正__ する必要がある
* 通常のゲーム木を作成するための仮引数と、__部分木を作成するための仮引数__ の __区別がわかりづらくなる__

そこで、本記事では __部分木を作成する場合__ は、仮引数 __`subtree`__ に代入する部分木の作成に必要なデータを __dict__ の形式で例えば __`{ "maxdepth": 2 }` のように記述する__ ことにします。また、__部分木を作成しない場合__ は仮引数 __`subtree`__ に __`None` を代入する__ ことにします。

### `__init__` メソッドの修正

仮引数 __`subtree`__ の __データ構造を変更__ したので、`__init__` メソッドを下記のプログラムのように修正する必要があります。

* __1 行目__：仮引数 `subtree` のデフォルト値を `None` に修正する
* __2 行目__：条件式を `None` でないことを判定するように修正する
* __3 行目__：仮引数 `subtree` を同名の属性に代入する

```python
1  def __init__(self, algo="bf", shortest_victory=False, subtree=None):
2      if subtree is not None:
3          self.subtree = subtree
4          self.create_subtree()
5          return
6      
7      self.algo = algo
元と同じなので省略
8    
9  Mbtree.__init__ = __init__
```

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

```python
def __init__(self, algo="bf", shortest_victory=False, subtree=None):
    if subtree is not None:
        self.subtree = subtree
        self.create_subtree()
        return
    
    self.algo = algo
    self.shortest_victory = shortest_victory
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_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)
        self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
    self.nodelist_by_mb = {}
    self.bestmoves_by_mb = {}
    self.calc_bestmoves(self.root)
    
Mbtree.__init__ = __init__
```
</details>

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

```diff_python
-def __init__(self, algo="bf", shortest_victory=False, subtree=False):
+def __init__(self, algo="bf", shortest_victory=False, subtree=None):
-   if subtree:
+   if subtree is not None:
+       self.subtree = subtree
        self.create_subtree()
        return
    
    self.algo = algo
元と同じなので省略
    
Mbtree.__init__ = __init__
```
</details>

### `create_subtree` の修正

次に、__`subtree`__ 属性の __`maxdepth` のキーの値の深さまで部分木を作成する__ ように、`create_subtree` を修正する必要があります。その処理は幅優先アルゴリズムと深さ優先アルゴリズムのどちらを使っても実装できますが、今回の記事では幅優先アルゴリズムで実装することにします。深さ優先アルゴリズムで実装したい方はチャレンジしてみて下さい。

下記は __`create_subtree`__ を修正したプログラムです。行う処理は幅優先アルゴリズムでゲーム木全体を作成する __[`create_tree_by_bf`](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)__ と下記の点を除いて __ほぼ同じ__ なので比較してみて下さい。なお、元の `create_subtree` から大きく修正したので、修正箇所は省略しました。

* `nodelist_by_depth` 属性など、`draw_subtree` で部分木を表示する際に必要がない属性を計算しない
* 計算する部分木の深さを `maxdepth` までとする
* 途中経過や結果を `print` で表示しない

下記は、[`create_tree_by_bf`](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) と異なる部分の説明です。

* __6 行目__：部分木の深さの最大値を表すデータを `subtree` 属性から取り出して `maxdepth` に代入する
* __7 ~ 13 行目__：処理を行う深さが `depth` のノードが存在し、なおかつ __深さが `maxdepth` 未満の間__ 繰り返し処理を行う。この繰り返し処理で __作成されるのは `depth + 1` の深さのノード__ なので、7 行目の条件式は、`maxdepth` 以下ではなく、__`maxdepth` 未満であることを判定する必要がある__ 点に注意する事

```python
 1  def create_subtree(self):
 2      self.root = Node(Marubatsu())
 3   
 4      depth = 0
 5      nodelist = [self.root]
 6      maxdepth = self.subtree["maxdepth"]
 7      while len(nodelist) > 0 and depth < maxdepth:
 8          childnodelist = []
 9          for node in nodelist:
10              node.calc_children()
11              childnodelist += node.children
12          nodelist = childnodelist
13          depth += 1
14
15  Mbtree.create_subtree = create_subtree
```

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

```python
def create_subtree(self):
    self.root = Node(Marubatsu())
    
    depth = 0
    nodelist = [self.root]
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0 and depth < maxdepth:
        childnodelist = []
        for node in nodelist:
            node.calc_children()
            childnodelist += node.children
        nodelist = childnodelist
        depth += 1

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

実行結果は同じなので省略しますが、上記の修正後に下記のプログラムを実行すると、先程と同じルートノードから深さ 1 までの部分木が表示されます。

```python
subtree = Mbtree(subtree={"maxdepth": 1})
subtree.draw_subtree(centernode=subtree.root, maxdepth=1)
```

また、図がかなり大きいので実行結果は省略しますが、下記のプログラムを実行すると、深さ 2 までの部分木が表示されます。

```python
subtree = Mbtree(subtree={"maxdepth": 2})
subtree.draw_subtree(centernode=subtree.root, maxdepth=2)
```

## 中心となるノードの指定

次に、__中心となるノードを指定した部分木__ を作成できるようにします。その際に、__中心となるノードを指定する方法を決める__ 必要がありますが、本記事では中心となるノードを表す __局面のデータ__ を、仮引数 __`subtree`__ に代入する dict の __`centermb` というキーに代入する__ ことにします。具体的には、(1, 1) に〇を着手した局面を表すノードを中心とする深さ 2 までの部分木を、下記のプログラムのように記述して作成します。

```python
mb = Marubatsu()
mb.move(1, 1)
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": 2})
```

:::note
`draw_subtree` メソッドと同様に、`centernode` というキーに中心となるノードのデータを代入すれば良いと思った人がいるかもしれませんが、これから作成する部分木の中心となるノードを、__部分木を作成する前に指定することは不可能__ なので、ノードのデータではなく、ノードが表す局面のデータを代入する必要があります。
:::

### 作成する部分木の検証

次に、どのように部分木を作成するかを考える必要があります。__`draw_subtree`__ でゲーム木の __部分木をどのように表示するか__ について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/0bad81b51c0ccbdbc3c7)を復習して下さい。また、どうしてもイメージがわかない人は、下記のプログラムのように実際に `draw_subtree` で部分木を表示してみると良いでしょう。下記は、深さが 2 のノードを中心とする深さ 3 までの部分木を表示するプログラムです。なお、中心となるノードがどれであるかがわかるように、赤い枠が表示される選択されたノードを中心となるノードと同じにしました。

```python
centernode = mbtree.nodelist_by_depth[2][0]
maxdepth = 3
mbtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/995800b6-d6ad-e64d-d718-9cf0e4465539.png" width="200">

`draw_subtree` で表示する部分木は、__中心となるノードの深さを d__、部分木の __深さの最大値を maxdepth__ とすると、以下のようなノードを持つ部分木です。

* 深さが __0 ~ d - 1__ のノードは、中心となるノードの __[先祖ノード](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%8F%8F%E7%94%BB%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85)__ である
* 深さが __d__ のノードは、__中心となるノードとその兄弟ノード__（中心となるノードの親ノードの子ノード）である
* 深さが __d + 1 ~ maxdepth__ のノードは、中心となるノードのすべての __[子孫ノード](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%8F%8F%E7%94%BB%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85)__ である

このような部分木を作成するためには、__`calc_subtree`__ メソッド内で __子ノードを作成する処理を行う際__ に、__ノードの深さによって__ 下記のような __異なる処理を行う必要__ があります。

| 深さ | 行う処理 |
|:-:|:--|
| __0 ~ d - 2__  | その局面から、__中心となるノードに至るために行う必要がある着手__ を行った子ノードを作成する  |
| __d - 1__ | その局面のすべての合法手に対応する子ノードを作成する<br>ただし、次の深さの子ノードの一覧には、中心となるノードのみを登録する  |
| __d ~ maxdepth - 1__  | その局面のすべての合法手に対応する子ノードを作成する  |

深さ 0 ~ d - 2 では、その局面から __中心となるノードに至るための着手__ を行う必要がありますが、その着手は、中心となるノードの局面を表す Marubatsu クラスのインスタンスの、__棋譜を表す `records` 属性に代入されています__。

### `draw_subtree` の修正

下記は、上記の方針に従って、`calc_subtree` を修正したプログラムです。

* __8 行目__：中心となるノードを表す局面を `centermb` に代入する
* __9 行目__：中心となるノードの深さは、局面の手数を表す `move_count` 属性に代入されているので、それを `centerdepth` に代入する
* __10 行目__：中心となるノードの局面に至るまでの棋譜が代入されている `records` 属性を `records` に代入する
* __15 ~ 28 行目__：深さ `depth` のそれぞれのノードの子ノードを作成する処理を、ノードの深さに応じた処理を行うように修正する
* __15 ~ 21 行目__：深さが `centerdepth - 2` 以下の場合の処理を行う
* __16 行目__：ノードの局面を表すデータを `deepcopy` でコピーする
* __17 行目__：そのノードから中心となるノードに至るための着手を `records` から取り出す。深さが `depth` の局面に対して行われた着手は、`records` の `depth + 1` 番の要素に代入されている点に注意すること
* __18 ~ 20 行目__：着手を行った局面を表す子ノードを作成し、ノードの子ノードに挿入する
* __21 行目__：部分木の次の深さのノードの一覧に上記で作成した子ノードを追加する
* __23 行目__：深さが `centerdepth - 2` より大きい場合は、その局面の全ての合法手に対応する子ノードを作成する点は共通するのでその処理を行う
* __24 ~ 26 行目__：深さが `centerdepth - 1` の場合は、次の深さのノードの一覧には、中心となるノードのみを追加する必要がある。その子ノードは `records` の `depth + 1` 番の要素に代入されている着手を行った場合のノードなので、Node の `children_by_move` 属性を利用して中心となるノードを計算することができる。中心となるノードを `centernode` 属性に代入し、26 行目でその子ノードのみを次の深さのノードの一覧に追加する
* __27、28 行目__：深さが `centerdepth` 以上の場合は、作成した全ての子ノードを、次の深さのノードの一覧に追加する

なお、25 行目で、中心となるノードを `centernode` 属性に代入した理由については、このすぐ後で説明します。

```python
 1  from copy import deepcopy
 2
 3  def create_subtree(self):
 4      self.root = Node(Marubatsu())
 5   
 6      depth = 0
 7      nodelist = [self.root]
 8      centermb = self.subtree["centermb"]
 9      centerdepth = centermb.move_count
10      records = centermb.records
11      maxdepth = self.subtree["maxdepth"]
12      while len(nodelist) > 0 and depth < maxdepth:
13          childnodelist = []
14          for node in nodelist:
15              if depth <= centerdepth - 2:
16                  childmb = deepcopy(node.mb)
17                  x, y = records[depth + 1]
18                  childmb.move(x, y)
19                  childnode = Node(childmb, parent=node, depth=depth+1)   
20                  node.insert(childnode)
21                  childnodelist.append(childnode)
22              else:
23                  node.calc_children()
24                  if depth == centerdepth - 1:
25                      self.centernode = node.children_by_move[records[depth + 1]]
26                      childnodelist.append(self.centernode)
27                  else:
28                      childnodelist += node.children
29          nodelist = childnodelist
30          depth += 1
31
32  Mbtree.create_subtree = create_subtree
```

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

```python
from copy import deepcopy

def create_subtree(self):
    self.root = Node(Marubatsu())
    
    depth = 0
    nodelist = [self.root]
    centermb = self.subtree["centermb"]
    centerdepth = centermb.move_count
    records = centermb.records
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0 and depth < maxdepth:
        childnodelist = []
        for node in nodelist:
            if depth <= centerdepth - 2:
                childmb = deepcopy(node.mb)
                x, y = records[depth + 1]
                childmb.move(x, y)
                childnode = Node(childmb, parent=node, depth=depth+1)   
                node.insert(childnode)
                childnodelist.append(childnode)
            else:
                node.calc_children()
                if depth == centerdepth - 1:
                    self.centernode = node.children_by_move[records[depth + 1]]
                    childnodelist.append(self.centernode)
                else:
                    childnodelist += node.children
        nodelist = childnodelist
        depth += 1

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

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

```diff_python
from copy import deepcopy

def create_subtree(self):
    self.root = Node(Marubatsu())
    
    depth = 0
    nodelist = [self.root]
+   centermb = self.subtree["centermb"]
+   centerdepth = centermb.move_count
+   records = centermb.records
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0 and depth < maxdepth:
        childnodelist = []
        for node in nodelist:
-           node.calc_children()
-           childnodelist += node.children
+           if depth <= centerdepth - 2:
+               childmb = deepcopy(node.mb)
+               x, y = records[depth + 1]
+               childmb.move(x, y)
+               childnode = Node(childmb, parent=node, depth=depth+1)   
+               node.insert(childnode)
+               childnodelist.append(childnode)
+           else:
+               node.calc_children()
+               if depth == centerdepth - 1:
+                   self.centernode = node.children_by_move[records[depth + 1]]
+                   childnodelist.append(self.centernode)
+               else:
+                   childnodelist += node.children
        nodelist = childnodelist
        depth += 1

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

上記の修正後に、下記のプログラムで (0, 0)、(1, 1) の順で着手を行った局面を中心とする深さが 3 の部分木を表示すると、実行結果の左のように部分木が正しく表示されるようになることが確認できます。先ほどのゲーム木全体のデータを使って同じ部分木を表示した結果を表す右図と比較して下さい。

なお、`calc_subtree` の 25 行目で __中心となるノードを `centernode` 属性に代入した理由__ は、__`draw_subtree`__ メソッドのキーワード引数 __`centernode` に中心となるノードを記述する必要がある__ からです。25 行目の処理を行わない場合は、部分木を作成した後で、作成した部分木のノードの中から __中心となるノードを探す処理を記述する必要__ がある点が面倒です。

```python
mb = Marubatsu()
mb.move(0, 0)
mb.move(1, 0)
maxdepth = 3
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": maxdepth})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bfe9c410-484e-3851-f805-2cea7588999f.png" width="191">　　　　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/995800b6-d6ad-e64d-d718-9cf0e4465539.png" width="200">

## 兄弟ノードの子ノードを表す線の表示

上記の図を見比べるとわかると思いますが、左図では中心となるノードの __兄弟ノード__ に、__子ノードが存在することを表す線が表示されない__ という問題があります。これは、現状では __兄弟ノードの子ノードを計算していないことが原因__ なので、兄弟ノードに合法手が存在する場合は子ノードを計算するようにプログラムを修正することで、右図のような表示が行われるようになります。

なお、右上に並んでいる、中心となるノードの子ノードも同様に、子ノードが存在することを表す線が存在しませんが、そちらに関しては次回の記事で修正します。

### 子ノードが存在することを表す線が表示される条件の検証

上記では、兄弟ノードの子ノードを計算するという方法を説明しましたが、実際にはもっと簡単な方法でこの問題を解決することができます。__子ノードが存在することを表す線__ は __Node__ クラスの __`draw_node`__ メソッドで表示されますが、その処理は下記のプログラムのコメントが示すように、__子ノードを表す `children` 属性に要素が 1 つ以上存在する場合__ に表示するようになっています。

```python
def draw_node(略):
略
        # 子ノードが存在する場合に、エッジの線と子ノードを描画する
        if len(self.children) > 0:
略
```

そのため、兄弟ノードの右に線を表示するために、兄弟ノードの __子ノードを実際に計算する必要はなく__、__何らかの要素を持つ list を `children` 属性に代入する__ だけでかまいません。

下記のプログラムはそのように `calc_subtree` を修正したプログラムです。この処理は見た目の意味がわかりづらい処理なので、コメントを詳しく記しました。

* __2 ~ 13 行目__：中心となるノードの親ノードに対するの処理を記述する
* __3 行目__：中心となるノードの親ノードの `children_by_move` 属性を利用して、中心となるノードとその兄弟ノードに対する繰り返し処理を行う。なお、`children_by_move` に代入された dict のキーは行った着手を、キーの値はその着手を行った子ノードを表す
* __4 行目__：`childnode` が中心となるノードであるかを、`children_by_move` から取り出したキーと、中心となるノードの局面が `depth` 手目に行った着手を表す `records[depth + 1]` が一致するかどうかで判定する
* __5、6 行目__：`childnode` が中心となるノードであると判定された場合は、`centernode` 属性に代入し、`childnodelist` に追加する（元のプログラムと同じ処理を行う）
* __7 ~ 13 行目__：`childnode` が兄弟ノードであると判定された場合は、合法手が存在するかどうかをゲーム中であるかどうかで判定し、合法手が存在する場合は `children` 属性に要素を追加する。ここでは `None` を追加しているが、どのような値を追加してもかまわない

```python
 1  def create_subtree(self):
元と同じなので省略      
 2              if depth == centerdepth - 1:
 3                  for move, childnode in node.children_by_move.items():
 4                      if move == records[depth + 1]:
 5                          self.centernode = childnode
 6                          childnodelist.append(self.centernode)
 7                      else:
 8                          if childnode.mb.status == Marubatsu.PLAYING:
 9                              # draw_subtree でこの部分木を表示する際に、中心となるノードの
10                              # 兄弟ノードの右に子ノードが存在することを表す線を描画したい
11                              # その線は Node クラスの draw_node で children 属性に 1 つ以上の
12                              # 要素が存在する場合に描画されるので None を要素として追加する
13                              childnode.children.append(None)
元と同じなので省略

Mbtree.create_subtree = create_subtree
```

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

```python
def create_subtree(self):
    self.root = Node(Marubatsu())
    
    depth = 0
    nodelist = [self.root]
    centermb = self.subtree["centermb"]
    centerdepth = centermb.move_count
    records = centermb.records
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0 and depth < maxdepth:
        childnodelist = []
        for node in nodelist:
            if depth < centerdepth - 1:
                childmb = deepcopy(node.mb)
                x, y = records[depth + 1]
                childmb.move(x, y)
                childnode = Node(childmb, parent=node, depth=depth+1)   
                node.insert(childnode)
                childnodelist.append(childnode)
            else:
                node.calc_children()                   
                if depth == centerdepth - 1:
                    for move, childnode in node.children_by_move.items():
                        if move == records[depth + 1]:
                            self.centernode = childnode
                            childnodelist.append(self.centernode)
                        else:
                            if childnode.mb.status == Marubatsu.PLAYING:
                                # draw_subtree でこの部分木を表示する際に、中心となるノードの
                                # 兄弟ノードの右に子ノードが存在することを表す線を描画したい
                                # その線は Node クラスの draw_node で children 属性に 1 つ以上の
                                # 要素が存在する場合に描画されるので None を要素として追加する
                                childnode.children.append(None)
                else:
                    childnodelist += node.children
        nodelist = childnodelist
        depth += 1

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

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

```diff_python
def create_subtree(self):
元と同じなので省略      
                if depth == centerdepth - 1:
-                   self.centernode = node.children_by_move[records[depth + 1]]
-                   childnodelist.append(self.centernode)
+                   for move, childnode in node.children_by_move.items():
+                       if move == records[depth + 1]:
+                           self.centernode = childnode
+                           childnodelist.append(self.centernode)
+                       else:
+                           if childnode.mb.status == Marubatsu.PLAYING:
                                # draw_subtree でこの部分木を表示する際に、中心となるノードの
                                # 兄弟ノードの右に子ノードが存在することを表す線を描画したい
                                # その線は Node クラスの draw_node で children 属性に 1 つ以上の
                                # 要素が存在する場合に描画されるので None を要素として追加する
+                               childnode.children.append(None)
元と同じなので省略

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

上記の修正後に下記のプログラムを実行すると、実行結果の左のように、兄弟ノードの右に子ノードが存在することを表す線が表示されるようになったことが確認できます。修正前の右図と比較して下さい。

```python
mb = Marubatsu()
mb.move(0, 0)
mb.move(1, 0)
maxdepth = 3
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": 3})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/db536fa8-90e1-929d-f758-4859c22ce12b.png" width="198">　　　　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c0ad8076-fba1-3220-eb76-c0e9ad51f0b2.png" width="200">

今回の記事はいつもより少し短いですがここまでにします。しばらくの間は筆者の都合により記事が短くなると思いますが、引き続き連載は続けていく予定です。

# 今回の記事のまとめ

今回の記事では `draw_subtree` で部分木を表示する際に、あらかじめゲーム木全体を作成しておくのではなく、必要な __部分木を動的に作成__ して表示するという修正を始めました。

まだ修正は完了していないので、修正の続きは次回の記事で行います。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/7689cffcd53b4319ae5f

[^1]:例えば、将棋や囲碁のゲーム木はノードの数が多すぎるため、静的なデータとしてあらかじめ計算しておくことは不可能です
[^2]:`draw_subtree` で表示する以外の目的で部分木を作成する場合は、必要に応じてそれらの属性を計算する必要があります