Pythonで〇×ゲームのAIを一から作成する　その88　ゲーム木、木構造と親ノードと子ノードの関係の視覚化

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/5941cc59c3e0e173c5cf

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

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

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

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

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

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

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

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

# 探索型の AI による最強の AI の作成

今回の記事から、〇×ゲームの __探索型の AI__ を作成することにします。

[以前の記事](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E4%BA%8C%E4%BA%BA%E9%9B%B6%E5%92%8C%E6%9C%89%E9%99%90%E7%A2%BA%E5%AE%9A%E5%AE%8C%E5%85%A8%E6%83%85%E5%A0%B1%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E6%80%A7%E8%B3%AA)で説明したように、〇×ゲームは __二人零和有限確定完全情報ゲーム__ という性質を持つゲームです。この性質の中の、下記の「__有限__」、「__確定__」、「__完全情報__」という性質を持つゲームは、__原理的__ には、ゲーム開始時の局面から、とりうるすべての着手を行った局面を、__ゲーム木__ と呼ばれる __データ構造で列挙__ することができます。

* __有限__：__合法手が有限__ であり、ゲームが __有限の手番で必ず終了する__ という性質。合法手 が無限にあったり、永遠に決着がつかないようなゲームではない
* __確定__：サイコロのような、__ランダムな要素が存在しない__ という性質。着手による __局面の変化が確定する__ 性質を持つゲーム
* __完全情報__：ゲームの __すべての情報が公開__ されているという性質

:::note
〇×ゲームは、局面の数が少ないのでゲーム木を作成することが実際にできますが、オセロ、将棋、囲碁などのゲームでは、__局面の数が多すぎる__ ため、原理的にはゲーム木を作成することはできても、__現実的には作成できません__。


ゲーム木と局面の数の問題については、今後の記事で説明します。
:::

そのゲームで出現するすべての局面を表す __ゲーム木を調べる__ ことで、そのゲームの __任意の局面の最善手を計算__ することができます。ゲーム木を調べて、最善手を見つけることを、ゲーム木の __探索__ と呼びます。ゲーム木を作成し、探索を行うことで、[以前の記事](https://qiita.com/ysgeso/items/5fe28ae6c765a169fd34#%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E8%A7%A3%E6%B1%BA%E3%81%A8%E3%81%9D%E3%81%AE%E7%A8%AE%E9%A1%9E)で説明した、「すべての局面で、局面の状況と、最善手が判明している」という、__ゲームを強解決することができる__ ので、__最強の AI を作成__ することができます。

# 木構造（tree structure）

ゲーム木は、__木構造__ と呼ばれる __データ構造の一種__ なので、木構造について説明します。

下図は、〇×ゲームの __ゲーム開始時の局面__ から、__2 手目まで__ のとりうる局面の組み合わせを表したものです。〇×ゲームは、1 手目で 9 通り、2 手目で 8 通りの合法手があるので、図では 9 × 8 = 72 通りの 2 手目の局面が表示されています。なお、図がかなり縦に長いので、折りたたんで表示しました。

</details>

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

![556.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9759d189-59a3-e742-975e-adb4d3ef1fac.png)

</details>

2 手目で 72 もの局面があることからわかるように、__ゲーム終了時までのとりうる局面の数__ は __膨大なものになる__ ので画像では示しませんが、ゲーム開始時の局面から終了時までの、とりうる __すべての局面__ を上図のような方法で表現することができます。

このようなデータ構造を、__木構造__（tree structure）と呼びます。〇×ゲームのゲーム木には、下記のような性質があります。

* __大元となる局面__（ゲーム開始時の局面のこと）が __1 つだけある__
* __それぞれの局面__ から、その局面の合法手の数だけ __次の局面が存在__ し、次の局面を __線で結んで表現__ する
* 図の __線には__、左の局面から右の局面に移行するという、__方向がある__
* ただし、ゲームの決着がついた局面は次の局面が存在しない
* __有限ゲーム__ であるため、局面を辿っていくことで、__必ず決着がついた局面にたどり着く__（局面を辿っていくと、元の局面に戻るという、__ループが存在しない__）

また、木構造では、その名の通り、__木（tree）に由来__ する以下のような用語が使われます。

* __枝分かれする__ それぞれの局面のデータを、__木の節点__ に例えて __ノード__（node[^1]）と呼ぶ
* ノードとノードを __つなぐ線__ のことを、__木の枝__ に例えて __エッジ__（edge[^2]）と呼び、それぞれのノードは __0 個以上のエッジを持つ__
* エッジは __方向を持ち__、ノード A から ノード B にエッジでつながれている場合、ノード A を __親ノード__（parent node）、ノード B を __子ノード__（child node） と呼ぶ
* 大元となる、__親ノードを持たないノード__ の事を、__木の根__（root）に例えて __ルートノード__（root node） と呼ぶ
* 子ノードを持たない、エッジの無い __末端のノード__ の事を、__木の葉__（leaf）に例えて __リーフノード__（leaf node）と呼ぶ
* それぞれのノードに対して、__ルートノードから__ エッジを __何回辿る__ ことでたどり着けるかを表す数値の事を、ノードの __深さ__（depth）と呼ぶ。__ルートノードの深さは 0__ であり、〇×ゲームの場合は、__n 手目の局面__ のノードの __深さは n__ となる

先程の図では、木構造を左から右に図示しましたが、__下から上に図示__ した場合、__ルートノードを根__ とし、__リーフノードを葉__ とした __木のように見える__ ことから、__木構造__ と名付けられました。なお、ゲーム木を図示する際に、上から下に図示することが多いようですが、上から下に図示すると横幅が広がりすぎて、横にスクロールしないと全体が見えなくなるので、本記事では左から右に図示します。

:::note
木構造にはノードに子ノードが 2 つしかない二分木など、様々な種類があります。
:::

:::note
木構造のように、__頂点__（ノードの事）と __辺__（エッジの事）で構成されるデータ構造のことを、__グラフ構造__ と呼びます。また、グラフ構造の中で、__辺に方向が存在する__ ものを __有向グラフ__ と呼びます。

__木構造__ は、__グラフ構造の一種__ で、有向グラフで、頂点から辺の方向に従って辿ることで元の頂点に戻ることがないという性質を持ちます。
:::

# 〇×ゲームのゲーム木のルートノードの作成

〇×ゲームのゲーム木をいきなり作成するのは大変なので、今回の記事では、__ゲーム開始時の局面__ を表すゲーム木の __ルートノード__ のデータを Python のプログラムで作成します。

## ノードを表す `Node` クラスの定義

__ゲーム木__ は、__大量のノードから構成される__ ので、〇×ゲームのノードを表す __Node__ という __クラスを定義__ し、そのインスタンスを作成して __組み合わせる__ ことで、〇×ゲームのゲーム木を作成することにします。

ノードは __局面のデータを持つ__ ので、__`mb`__ という属性に局面のデータを表す __Marubatsu クラスのインスタンスを代入__ することにします。

下記は、Node クラスの定義です。__`__init__`__ メソッドの __仮引数 `mb`__ に __局面のデータを代入__ することで、特定の局面の Node クラスのインスタンスを作成できるようにしています。

```python
class Node:
    def __init__(self, mb):
        self.mb = mb
```

例えば、〇×ゲームの開始時の局面を表す、ゲーム木の __ルートノード__ は、下記のプログラムで作成し、ノードが表す局面を表示することができます。

* __4 行目__：ゲーム開始時の局面を表す Marubatsu クラスのインスタンスを実引数に記述して Node クラスのインスタンスを作成する
* __5 行目__：Node クラスのインスタンスの `mb` 属性にそのノードの局面の情報が代入されているので、それを `print` で表示することでゲーム盤を表示する

```python
1  from marubatsu import Marubatsu
2
3  mb = Marubatsu()
4  rootnode = Node(mb)
5  print(rootnode.mb)
```

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

```python
from marubatsu import Marubatsu

mb = Marubatsu()
rootnode = Node(mb)
print(rootnode.mb)
```
</details>

実行結果

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

## 属性によるエッジの表現

ゲーム木は、大量のエッジからも構成されるので、エッジを表すクラスを定義する必要があるのではないかと思う人がいるかもしれません。実際に、エッジを表すクラスを定義してゲーム木を作成することも可能ですが、__エッジ__ は __親ノードから子ノードへの参照__ とみなすことができるので、__変数（属性）を使ってエッジを表現__ することができます。[以前の記事](https://qiita.com/ysgeso/items/9b00b35d9901a9793a30#python-%E3%81%AE%E5%A4%89%E6%95%B0%E3%81%A8%E4%BB%A3%E5%85%A5%E5%87%A6%E7%90%86)で説明したように、__変数への代入処理__ は、オブジェクトの id を格納することで、__オブジェクトを参照する処理__ を行っていることを思い出してください。

具体的には、`Node` クラスのインスタンスに、__子ノードを表す属性__ を用意し、その属性に __子ノード__ を表す `Node` クラスのインスタンスを __代入__ することで、クラスを定義することなくエッジを表現することができます。

ノードは __0 個以上の子ノード__ を持つので、子ノードを表すデータは、__list で表現する__ ことができます。そこで、子ノードのデータを __`children`__ という属性に、list の形式で代入することにします。

子ノードのデータをいきなり作成するのは大変なので、下記のプログラムのように、`__init__` メソッド内では `children` 属性に __空の list を代入__ し、後から子ノードのデータを追加する処理を記述することにします。

下記は、`Node` クラスの定義です。

```python
class Node:
    def __init__(self, mb):
        self.mb = mb
        self.children = []
```

## 子ノードを挿入する `insert` メソッドの定義

作成したばかりの Node クラスのインスタンスには、子ノードは一つも登録されていないので、__子ノードを追加する処理__ を記述する必要があります。そこで、ノードに子ノードを追加する下記のようなメソッドを定義する事にします。なお、木構造のデータにノードを追加する処理の事を __ノードの挿入__（insert）と呼ぶので、メソッドの名前は __`insert`__ にしました。

__名前__：子ノードを挿入（insert）するので `insert` という名前にする
__処理__：実引数に記述したノードを子ノードに挿入する
__入力__：仮引数 `node` に、子ノードに挿入するノードを代入する
__出力__：なし

下記は、`insert` メソッドの定義です。

```python
def insert(self, node):
    self.children.append(node)

Node.append_child = append_child
```

:::note
`insert` が行う処理は、`self.children.append(node)` だけなので、このようなメソッドを定義しなくても、例えば、`rootnode.children.append(node)` のように、`Node` クラスの `children` 属性に対して直接 `append` メソッドを使って子ノードを挿入すればよいのではないかと思った人がいるかもしれません。

しかし、`rootnode.children.append(node)` というプログラムは、子ノードを表すデータが `children` という属性に、list の形式で代入されていることを __知っていなければ記述することはできない__ という問題があります。

また、__子ノードのデータを記録するデータ構造__ は、__list だけではありません__。後から __list 以外の形式__ で子ノードを記録するように `Node` クラスの __定義を修正した場合__ は、`rootnode.children.append(node)` の処理が __動作しなくなる__ ため、そのような記述が行われている部分のプログラムを __すべて修正する必要が生じます__。

その点、`insert` というメソッドの中で子ノードの追加を行う処理を記述するようにしておけば、後から子ノードのデータ構造を変更した場合でも、__`insert` の中の処理を変更__ するという __修正だけで済みます__。

なお、実際に今後の記事で、子ノードを list ではない形式で記録するように `Node` クラスの定義を変更する予定です。
:::

## 子ノードを計算するメソッドの定義

次に、子ノードを計算する、下記のようなメソッドを定義することにします。

__名前__：子ノードを計算（calculate）するので __`calc_children`__ という名前にする
__処理__：子ノードを計算し、`children` 属性に挿入する
__入力__：なし
__出力__：なし

子ノードの局面は、親ノードの局面に対して、それぞれの合法手を着手した局面です。従って、`calc_children` は、下記のプログラムのように定義できます。なお、下記の 4 行目の処理を記述しない場合は、`calc_children` メソッドを __2 度以上呼び出してしまう__ と、`children` 属性に同じ子ノードが __重複して登録されてしまう__ という問題が発生します。

* __4 行目__：このメソッドを __呼び出す前__ に、`children` 属性に __ノードが登録されていた場合のことを考慮__ して、`children` 属性の値を __空の list で初期化する__
* __5 行目__：合法手を計算し、それぞれの合法手に対する繰り返し処理を行う
* __6 行目__：`self.mb` に対して `move` メソッドで着手を行うと、__自分自身のノードの局面が変化してしまう__ ことになるので、子ノードの局面を計算する際は、`deepcopy` で `self.mb` に対して __[深いコピー](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E6%B7%B1%E3%81%84%E3%82%B3%E3%83%94%E3%83%BC)__ を行う必要がある
* __7、8 行目__：コピーした `childmb` に対して合法手の着手を行い、`Node(childmb)` で着手を行ったノードを作成し、`insert` メソッドで子ノードに挿入する

```python
 1  from copy import deepcopy
 2
 3  def calc_children(self):
 4      self.children = []
 5      for x, y in self.mb.calc_legal_moves():
 6          childmb = deepcopy(self.mb)
 7          childmb.move(x, y)
 8          self.insert(Node(childmb))
 9
10  Node.calc_children = calc_children
```

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

```python
from copy import deepcopy

def calc_children(self):
    self.children = []
    for x, y in self.mb.calc_legal_moves():
        childmb = deepcopy(self.mb)
        childmb.move(x, y)
        self.insert(Node(childmb))

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

子ノードが正しく登録されているかどうかを確認するために、下記のプログラムで、ルートノードの子ノードの計算を行い、子ノードの局面を表示することにします。実行結果から、9 つの合法手が着手された局面が子ノードとして正しく登録されていることが確認できます。

* __1 行目__：`calc_children` で、`rootnode` の子ノードを計算する
* __2 行目__：繰り返し処理を使って、`rootnode` の子ノードの局面を `print` で表示する

```python
rootnode.calc_children()
for node in rootnode.children:
    print(node.mb)
```

実行結果

```
Turn x
O..
...
...

Turn x
.O.
...
...

Turn x
..O
...
...

Turn x
...
O..
...

Turn x
...
.O.
...

Turn x
...
..O
...

Turn x
...
...
O..

Turn x
...
...
.O.

Turn x
...
...
..O
```

下記のプログラムは、__`rootnode`__ の __最初の子ノード__ である、(0, 0) に着手を行った `rootnode.children[0]` に対して `calc_children` を実行し、__その子ノードを表示__ するプログラムです。実行結果から、この場合でも正しく子ノードが計算できることが確認できます。

```python
childnode = rootnode.children[0]
childnode.calc_children()
for node in childnode.children:
    print(node.mb)
```

実行結果

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

Turn o
o.X
...
...

Turn o
o..
X..
...

Turn o
o..
.X.
...

Turn o
o..
..X
...

Turn o
o..
...
X..

Turn o
o..
...
.X.

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

上記から、ゲーム木の __すべてのノードを指定__ して __`calc_children` を実行__ すれば〇×ゲームのゲーム木を作成することができそうですが、その方法はそれほど簡単ではありません。今回の記事では、ゲーム木の作成の話はここまでにしますので、余裕がある方は次回の記事までに、どのような方法でゲーム木を作成できるかについて考えてみて下さい。

# 画像による親ノードと子ノード関係の視覚化

木構造に限った話ではありませんが、__複雑なデータ構造__ を、__頭の中だけで理解することは困難です__。そのような場合は、__データを図示して視覚化する__ ことで __理解しやすくなります__。

上記では、文字列で 9 つの子ノードの局面を表示して視覚化しましたが、文字列での表現は、あまりわかりやすいとは言えないでしょう。

そこで、本記事では、親ノードと子ノードの関係を __画像で視覚化__ することにします。

## 視覚化の方針の決定

データの視覚化を行うためには、__どのようにデータを視覚化するか__ を決める必要があります。親ノードと子ノードの場合は、下記のような方法で視覚化すること良く行われます。

* __親ノードを上__ に描画し、その下に子ノードを __横に並べて描画__ する
* 親ノードと子ノードを __線で結ぶ__

ただし、上記のような視覚化を行うと、子ノードの数が多くなると、画像の横幅が大きくなりすぎて 1 画面に収まらなくなるので、本記事では下記のように視覚化することにします。

* __親ノードを左__ に描画し、その右に子ノードを __縦に並べて描画__ する
* 親ノードと子ノードを線で結ぶ

次に、上記の方針で __具体的にどのように描画を行うか__ を決める必要があります。その際には、ノートなどに、__手書き__ でどのように描画を行うかを __試行錯誤すると良い__ でしょう。

下記は、筆者が考えた視覚化です。本記事では、この視覚化を行う方法を紹介しますが、__視覚化の方法__ は __1 つではありません__。別の視覚化を行いたい人は自由に変更して下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/021ab2bf-e5aa-c63c-c60e-ef68a5c8d730.png" width="150">

## ゲーム盤を任意の場所に描画するメソッドの定義

上図の視覚化では、それぞれのノードが表す __ゲーム盤__ を、__さまざまな位置に描画__ しています。ゲーム盤を Figure に描画する処理は、`Marubatsu_GUI` クラスの `draw_board` メソッドで行うことができますが、`draw_board` は、以下のような問題があるため、上記のような画像を描画することはできません。

* Axes の __特定の座標にしか__ ゲーム盤を __描画できない__
* 手番や、対戦カードなど、上図では表示しない __文字列を描画してしまう__

そこで、`Marubatsu_GUI` に対して、下記のような修正を行うことにします。

* これまでの `draw_board` は、ゲーム盤の描画だけでなく、手番の文字列や、GUI のボタンの設定の変更などの GUI に関する様々な処理を行うので、__`draw_board`__ メソッドの __名前__ を __`update_gui` に変更__ する
* 元の `draw_board` が行う処理の中から、__ゲーム盤を描画する処理を抜き出して修正__ し、下記のようなメソッドを定義する。

__名前__：ゲーム盤を描画するので、`draw_board` という名前をそのまま利用する
__処理__：指定した Axes の、指定した座標に、指定した局面の画像を描画する
__入力__：仮引数 `ax` に Axes を、`mb` に Marubatsu クラスのインスタンスを、__`dx`__、__`dy`__[^3] に描画するゲーム盤の __左上の点の座標__ を代入する
__出力__：なし

上記の `draw_board` は、`Marubatsu_GUI` クラスのインスタンスの情報は __利用しない__ ので、__静的メソッドとして定義__ する事にします。また、[静的メソッド](https://qiita.com/ysgeso/items/8ac83f1b50b2706b8319#%E9%9D%99%E7%9A%84%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE-draw_mark-%E3%81%AE%E5%AE%9A%E7%BE%A9)として定義する事によって、`Marubatsu_GUI` の __インスタンスを作成しなくても__、__任意の場所から利用できる__ ようになるので、親ノードと子ノードの関係を描画する処理で利用することができます。

修正前の `draw_board` では、ゲーム盤の __左上の点__ を Axes の __(0, 0) の座標に描画__ していました。従って、ゲーム盤の __左上の点__ を Axes の __(dx, dy) の座標に描画__ するためには、描画を行う際の __x 座標と y 座標にそれぞれ `dx` と `dy` を加算すればよい__ ことがわかります。

下記は、そのように `draw_board` メソッドを修正したプログラムです。

* __3 行目__：静的メソッドとして定義する
* __4 行目__：静的メソッドなので、仮引数 `self` を削除し、仮引数 `ax`、`mb`、`dx`、`dy` を追加する。また、通常の場所にゲーム盤を描画する場合に省略できるように、仮引数 `dx`、`dy` はデフォルト値が `0` のデフォルト引数とする
* 5 行目の下にあった、ゲーム盤の描画とは関係ない処理を削除する
* `self.mb` を `mb` に修正する。なお、`ax` に関しては、元のプログラムでは最初に `ax = self.ax` のように、`ax` に値を代入してから処理を行っていたので修正する必要はない
* `plot` と `draw_mark` で枠やマークを描画する際に指定する __x 座標と y 座標__ に、それぞれ __`dx` と `dy` を加算__ して、ゲーム盤を __描画する位置を (dx, dy) だけずらす__
* __15 行目__：`draw_board` を __静的メソッドとして定義__ したため、__`self` を利用できなくなった__ ので、`self.draw_mark` を __`Marubatsu_GUI.draw_mark` に修正__ する。なお、`draw_mark` は静的メソッドとして定義されているので、インスタンスから呼び出す必要はない

なお、14 行目と 15 行目の `(x, y)` と `mb.board[x][y]` の __`x`__ と __`y`__ は、Axes の座標ではなく、__ゲーム盤のマスの座標__ なので `dx` と `dy` を __加算してはいけない__ 点に注意して下さい。

```python
 1  from marubatsu import Marubatsu_GUI
 2
 3  @staticmethod
 4  def draw_board(ax, mb, dx=0, dy=0):
 5      # この下にあったゲーム盤の描画と関係ない処理を削除する
 6      # ゲーム盤の枠を描画する
 7      for i in range(1, mb.BOARD_SIZE):
 8          ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k") # 横方向の枠線
 9          ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k") # 縦方向の枠線   
10
11      # ゲーム盤のマークを描画する
12      for y in range(mb.BOARD_SIZE):
13          for x in range(mb.BOARD_SIZE):
14              color = "red" if (x, y) == mb.last_move else "black"
15              Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color)
16
17  Marubatsu_GUI.draw_board = draw_board
```

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

```python
from marubatsu import Marubatsu_GUI

@staticmethod
def draw_board(ax, mb, dx=0, dy=0):
    # ゲーム盤の枠を描画する
    for i in range(1, mb.BOARD_SIZE):
        ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k") # 横方向の枠線
        ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k") # 縦方向の枠線   

    # ゲーム盤のマークを描画する
    for y in range(mb.BOARD_SIZE):
        for x in range(mb.BOARD_SIZE):
            color = "red" if (x, y) == mb.last_move else "black"
            Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color)           
            
Marubatsu_GUI.draw_board = draw_board
```
</details>

<details><summary><strong>修正箇所（前半のゲーム盤の描画とは関係ない処理は省略しています）</strong></summary>

```diff_python
from marubatsu import Marubatsu_GUI

+@staticmethod
-def draw_board(self):
def draw_board(ax, mb, dx=0, dy=0):
    # ゲーム盤の枠を描画する
-   for i in range(1, self.mb.BOARD_SIZE):
+   for i in range(1, mb.BOARD_SIZE):
-       ax.plot([0, self.mb.BOARD_SIZE], [i, i], c="k") # 横方向の枠線
+       ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k") # 横方向の枠線
-       ax.plot([i, i], [0, self.mb.BOARD_SIZE], c="k") # 縦方向の枠線   
+       ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k") # 縦方向の枠線   

    # ゲーム盤のマークを描画する
-   for y in range(self.mb.BOARD_SIZE):
+   for y in range(mb.BOARD_SIZE):
-       for x in range(self.mb.BOARD_SIZE):
+       for x in range(mb.BOARD_SIZE):
-           color = "red" if (x, y) == self.mb.last_move else "black"
+           color = "red" if (x, y) == mb.last_move else "black"
-           self.draw_mark(ax, x, y, self.mb.board[x][y], color)
+           Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color)

Marubatsu_GUI.draw_board = draw_board
```
</details>

なお、上記の修正によって、`Marubatsu_GUI` の `draw_board` の定義が変更されたので、それに合わせて __`Marubatsu_GUI` などの定義を変更する必要があります__ が、その修正は、親ノードと子ノードの関係の画像を表示するプログラムを記述した後で行うことにします。

### `draw_board` を利用したゲーム盤の描画の確認

`draw_board` の仮引数 `dx`、`dy` は、描画するゲーム盤の左上の点の Axes の座標を表しますが、毎回「ゲーム盤の左上の点の Axes の座標」と表記するのは冗長なので、以後は単に「__ゲーム盤の座標__」と表記することにします。

`draw_board` が正しく実装できているかを確認するために、__2 つの異なる局面の画像__ を __横に並べて描画する__ ことにします。そのためには、__Figure の大きさ__ と、2 つの局面の画像を、具体的に __どの座標に描画するか_ を決める必要があります。

Figure の大きさは、2 つの局面の画像をどこに描画するかを決めないと決まらないので、先に 2 つの画像の描画位置を決めることにします。

まず、__1 つ目のゲーム盤__ を、通常の場合と同様に __(0, 0) の座標に描画__ することにします。横に並べて描画するので、__2 つ目のゲーム盤の y 座標は 0__ になります。

〇×ゲームのゲーム盤は、__縦横 3 x 3 のサイズで描画__ されます。そのため、〇×ゲームのゲーム盤を横に 2 つ並べて描画するためには、2 つ目のゲーム盤の __x 座標を 3 より大きな数値に設定__ する必要があります。そこで、2 つ目のゲーム盤の __x 座標に 4 を設定__ することで、2 つのゲーム盤の __間を 1 だけ開けて描画__ することにします。

:::note
座標に関する説明が分かりづらいと思った方は、グラフ用紙などの座標がわかる用紙に実際にゲーム盤を書いて確認すると良いでしょう。
:::

上記から、2 つのゲーム盤を描画する Figure のサイズは、横幅が 3 + 1 + 3 = 7、縦幅が 3 になることが分かります。

下記は、2 つのゲーム盤を並べて描画するプログラムです。`draw_board` では、Axes の __[y 座標の上下を反転する必要がある](https://qiita.com/ysgeso/items/442db53b5b7e22c1000c#%E8%BB%B8%E3%81%AE%E5%8F%8D%E8%BB%A2)__ 点に注意して下さい。なお、下記のプログラムでは、ゲーム盤の描画位置のわかりやすさを重視して、Axes の目盛りを表示しています。

* __3 行目__：サイズが 7 x 3 の Figure を作成する
* __4 行目__：Axes の y 軸の上下を反転させる
* __6、7 行目__：Marubatsu クラスのインスタンスを作成し、`draw_board` で (0, 0) の座標にゲーム開始時の局面を描画する
* __8、9 行目__：(1, 1) のマスに着手を行い、`draw_board` で (4, 0) の座標にゲーム開始時の局面を描画する

```python
1  import matplotlib.pyplot as plt
2
3  fig, ax = plt.subplots(figsize=(7, 3))
4  ax.invert_yaxis()
5
6  mb = Marubatsu()
7  Marubatsu_GUI.draw_board(ax, mb)
8  mb.move(1, 1)
9  Marubatsu_GUI.draw_board(ax, mb, dx=4, dy=0)
```

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

```python
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(7, 3))
ax.invert_yaxis()

mb = Marubatsu()
Marubatsu_GUI.draw_board(ax, mb)
mb.move(1, 1)
Marubatsu_GUI.draw_board(ax, mb, 4, 0)
```
</details>


実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1b583d11-579e-47e0-c5c6-5ab9ae53ff09.png" width="300">

## 各ノードのゲーム盤を描画する座標の計算

親ノードと子ノードの関係を表す先程の画像を描画するためには、上記と同様に下記の内容を具体的に決める必要があります。

* 親ノードと子ノードの関係の画像を描画する __Figure のサイズ__
* それぞれのノードの __ゲーム盤を表示する座標__
* 親ノードと子ノードを結ぶ __線の両端の座標__

まず、それぞれのノードのゲーム盤を描画する座標を決めます。

下図は、先程の親ノードと子ノードの関係の図に座標の目盛りをつけたものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/924a3449-ebcc-76bb-97c8-6e99c9f97ca7.png" width="150">

上図では、ルートノードと子ノードの左上の座標は以下のようになっています。

|  | x 座標 | y 座標 |
|:--|:-:|:--|
| ルートノード  | 0  | 0  |
| 子ノード  | 5  | 0 からはじまり、4 ずつ増える  |

親ノードと子ノードの __横の間隔は 2__ になっているので、__子ノード__ のゲーム盤の __x 座標は 3 + 2 = 5__ になります。

子ノードと子ノードの __上下の間隔は 1__ になっているので、__子ノード__ のゲーム盤の __y 座標__ は 3 + 1 = __4 ずつ増える__ ことになります。従って、`children` 属性の __`i` 番の要素__ の子ノードの局面の画像は __(5, i * 4) の座標に描画__ すればよいことが分かります。

また、上図から、Figure のサイズは、横が 8、縦が 35 になることがわかります。横のサイズは 3 + 2 + 3 = 8 で計算できます。縦のサイズは、子ノードの数を num とすると、num × 4 - 1 で計算できます。1 を引くのは、__最後の子ノードの後の間隔は必要がない__ からですが、その間隔があっても大きな違いはないので、__計算式を簡単にするため__ に、Figure のサイズは、横を 8、縦を num × 4 とすることにします。ゲーム盤がぴったりと収まる大きさの画像にしたい人は、縦幅を num × 4 - 1 にして下さい。

## ノードを描画する処理の実装

次に、Node クラスに、インスタンスのノードと、その子ノードの関係を描画する下記のようなメソッドを定義する事にします。

__名前__：インスタンスのノードに関する内容を描画するので `draw_node` とする
__処理__：インスタンスのノードと、子ノードの関係を描画する
__入力__：なし
__出力__：なし

インスタンスのノードの局面は、`draw_board` を使って `self.mb` を (0, 0) の座標に描画すればよいので簡単に描画することができます。

__子ノード__ のデータは、__list で記録__ されているので、for 文による繰り返し処理を使って、子ノードを描画することができます。子ノードを描画する __(5, i * 4)__ という座標を計算するためには、__繰り返し処理の中__ で、__何番の要素に対する処理を行っているか__ を知る必要があり、その情報は組み込み関数 __`enumerate`__ を使って得ることができます。

### 組み込み関数 `enumerate`

組み込み関数 __`enumerate`__ は、下記のプログラムのように、__for 文__ の中で、list や dict などの、__[反復可能オブジェクト](https://qiita.com/ysgeso/items/0d64d1ddba1982b5a5d3#%E5%8F%8D%E5%BE%A9%E5%8F%AF%E8%83%BD%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88)__ を __実引数として記述__ します。このように記述することで、繰り返し処理が行われるたびに、反復可能オブジェクトの先頭の要素から順に、__(0 から数えた繰り返しの回数, 要素)__ という __tuple が取り出される__ ので、下記のプログラムでは、実行結果のように list の各要素の値が、そのインデックスの値と共に表示されます。

```python
for i, data in enumerate(["a", "b", "c"]):
    print(i, data)
```    

実行結果

```
0 a
1 b
2 c
```

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

https://docs.python.org/ja/3/library/functions.html#enumerate

### 各ノードのゲーム盤の描画の実装

`enumerate` を利用することで、`draw_node` は、下記のプログラムのように定義できます。

* __2 ~ 4 行目__：Figure を作成し、y 軸の上下を反転し、軸の目盛りを表示しないようにする
* __7 行目__：インスタンスが表すノードの局面を `draw_board` を使って (0, 0) に描画する
* __9、10 行目__：for 文と `enumerate`、`draw_board` を使って、`i` 番の要素の子ノードの局面を (5, i * 4) に描画する

```python
 1  def draw_node(self):
 2      fig, ax = plt.subplots(figsize=(8, len(self.children) * 4))
 3      ax.invert_yaxis()
 4      ax.axis("off")
 5   
 6      # 自分自身のノードを (0, 0) に描画する
 7      Marubatsu_GUI.draw_board(ax, self.mb)
 8      # i 番の子ノードを (5, i * 4) に描画する
 9      for i, childnode in enumerate(self.children):
10          Marubatsu_GUI.draw_board(ax, childnode.mb, dx=5, dy=i*4)
11        
12  Node.draw_node = draw_node
```

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

```python
def draw_node(self):
    fig, ax = plt.subplots(figsize=(8, len(self.children) * 4))
    ax.invert_yaxis()
    ax.axis("off")
    
    # 自分自身のノードを (0, 0) に描画する
    Marubatsu_GUI.draw_board(ax, self.mb)
    # i 番の子ノードを (5, i * 4) に描画する
    for i, childnode in enumerate(self.children):
        Marubatsu_GUI.draw_board(ax, childnode.mb, dx=5, dy=i*4)
        
Node.draw_node = draw_node
```
</details>

下記のプログラムを実行すると、実行結果のように、ゲーム開始時の局面を表す、ルートノードと子ノードが描画されます。

```python
rootnode.draw_node()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c015b11f-d80d-d132-a2c0-698e33d8b835.png" width="400">

### 描画の範囲と画像の大きさの調整

上記の画像では、画像の __上下左右に余白__ があります。これは、matplotlib が画像などを描画する際に、__自動的に Axes の表示範囲を調整__ して __上下左右に余白を入れる__ ようになっているからです。この余白は、グラフを描画する場合はグラフが見やすくなるという利点がありますが、今回の場合はこの __余白は邪魔__ です。Axes の描画範囲は、[`set_xlim` と `set_ylim`](https://qiita.com/ysgeso/items/ab2770693c947c108dd0#plot-%E3%81%AB%E6%8F%8F%E7%94%BB%E3%81%99%E3%82%8B%E8%A1%A8%E7%A4%BA%E7%AF%84%E5%9B%B2%E3%81%AE%E7%AE%A1%E7%90%86) メソッドを使って調整できるので、余白を表示しないようにします。

また、上記の __画像が大きすぎる__ と感じる人が多いのではないかと思います。そこで、`draw_node` に、描画する __画像の大きさの倍率__ を表す __`size`__ という属性と追加し、__画像の大きさを調整できる__ ようにすることにします。

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

* __1 行目__：仮引数 `size` を追加する
* __2、3 行目__：画像の幅と高さを計算する
* __4 行目__：`figsize` で、画像の幅と高さに `size` を乗算することで、画像の大きさを `size` 倍に調整する
* __5、6 行目__：`set_xlim` と `set_ylim` を利用して、Axes の表示範囲を、余白が無くなるように調整する

```python
1  def draw_node(self, size):
2      width = 8
3      height = len(self.children) * 4
4      fig, ax = plt.subplots(figsize=(width * size, height * size))
5      ax.set_xlim(0, width)
6      ax.set_ylim(0, height)   
7      ax.invert_yaxis()
元と同じなので省略 
8
9  Node.draw_node = draw_node
```

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

```python
def draw_node(self, size):
    width = 8
    height = len(self.children) * 4
    fig, ax = plt.subplots(figsize=(width * size, height * size))
    ax.set_xlim(0, width)
    ax.set_ylim(0, height)   
    ax.invert_yaxis()
    ax.axis("off")
    
    # 自分自身のノードを (0, 0) に描画する
    Marubatsu_GUI.draw_board(ax, self.mb)
    # i 番の子ノードを (5, i * 4) に描画する
    for i, childnode in enumerate(self.children):
        Marubatsu_GUI.draw_board(ax, childnode.mb, dx=5, dy=i*4)
        
Node.draw_node = draw_node
```
</details>

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

```diff_python
-def draw_node(self):
+def draw_node(self, size):
+   width = 8
+   height = len(self.children) * 4
-   fig, ax = plt.subplots(figsize=(8, len(self.children) * 4))
+   fig, ax = plt.subplots(figsize=(width * size, height * size))
+   ax.set_xlim(0, width)
+   ax.set_ylim(0, height)   
    ax.invert_yaxis()
元と同じなので省略 

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように、余白がなくなり、画像のサイズが小さくなります。

```python
rootnode.draw_node(size=0.25)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a4db746d-902a-2908-2442-8135e0bf6a48.png" width="100">

筆者は、上記の画像の大きさがちょうど良いと感じましたので、この後の修正で `draw_node` の仮引数 `size` をデフォルト値が 0.25 のデフォルト引数に修正することにします。どのくらいの画像の大きさがちょうどよいかは人によって異なるので、別の大きさが良いと感じた人は自由に変更して下さい。

### 枠線の太さの調整

`draw_board` や `draw_mark` では、ゲーム盤の枠線や図形の __線の太さを 2 に設定__ して描画を行っていましたが、上図のように、matplotlib では、__画像を小さく描画__ すると、__線の太さが相対的に太くなる__ という現象が発生するようです。上記の画像は __線が太くて見づらい__ 気がしますので、__`draw_node`__、__`draw_board`__、__`draw_mark`__ に、線の太さを設定する __仮引数 `lw` を追加__ することにします。

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

__4 行目__：互換性を考慮して、デフォルト値に `2` を設定した仮引数 `lw` を追加する
__6、9、10 行目__：キーワード引数 `lw=lw` に修正することで、太さが `lw` の線を描画する

```python
 1  import matplotlib.patches as patches
 2
 3  @staticmethod
 4  def draw_mark(ax, x, y, mark, color="black", lw=2):
 5      if mark == Marubatsu.CIRCLE:
 6          circle = patches.Circle([x + 0.5, y + 0.5], 0.35, ec=color, fill=False, lw=lw)
 7          ax.add_artist(circle)
 8      elif mark == Marubatsu.CROSS:
 9          ax.plot([x + 0.15, x + 0.85], [y + 0.15, y + 0.85], c=color, lw=lw)
10          ax.plot([x + 0.15, x + 0.85], [y + 0.85, y + 0.15], c=color, lw=lw)
11
12  Marubatsu_GUI.draw_mark = draw_mark
```

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

```python
import matplotlib.patches as patches

@staticmethod
def draw_mark(ax, x, y, mark, color="black", lw=2):
    if mark == Marubatsu.CIRCLE:
        circle = patches.Circle([x + 0.5, y + 0.5], 0.35, ec=color, fill=False, lw=lw)
        ax.add_artist(circle)
    elif mark == Marubatsu.CROSS:
        ax.plot([x + 0.15, x + 0.85], [y + 0.15, y + 0.85], c=color, lw=lw)
        ax.plot([x + 0.15, x + 0.85], [y + 0.85, y + 0.15], c=color, lw=lw)

Marubatsu_GUI.draw_mark = draw_mark
```
</details>

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

```diff_python
import matplotlib.patches as patches

@staticmethod
-def draw_mark(ax, x, y, mark, color="black"):
+def draw_mark(ax, x, y, mark, color="black", lw=2):
    if mark == Marubatsu.CIRCLE:
-       circle = patches.Circle([x + 0.5, y + 0.5], 0.35, ec=color, fill=False, lw=2)
+       circle = patches.Circle([x + 0.5, y + 0.5], 0.35, ec=color, fill=False, lw=lw)
        ax.add_artist(circle)
    elif mark == Marubatsu.CROSS:
-       ax.plot([x + 0.15, x + 0.85], [y + 0.15, y + 0.85], c=color, lw="2")
+       ax.plot([x + 0.15, x + 0.85], [y + 0.15, y + 0.85], c=color, lw=lw)
-       ax.plot([x + 0.15, x + 0.85], [y + 0.85, y + 0.15], c=color, lw="2")
+       ax.plot([x + 0.15, x + 0.85], [y + 0.85, y + 0.15], c=color, lw=lw)

Marubatsu_GUI.draw_mark = draw_mark
```
</details>

:::note
元のプログラムでは、間違って 9、10 行目に `lw="2"` のように、線の太さに文字列を指定していましたが、線の太さの設定は文字列でも問題はないようです。
:::

下記は、`draw_board` を修正したプログラムです。

__2 行目__：互換性を考慮して、デフォルト値に `2` を設定した仮引数 `lw` を追加する
__5、6、12 行目__：キーワード引数 `lw=lw` を追加することで、太さが `lw` の線を描画する

```python
 1  @staticmethod
 2  def draw_board(ax, mb, dx=0, dy=0, lw=2):
 3      # ゲーム盤の枠を描画する
 4      for i in range(1, mb.BOARD_SIZE):
 5          ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k", lw=lw) # 横方向の枠線
 6          ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k", lw=lw) # 縦方向の枠線
 7
 8      # ゲーム盤のマークを描画する
 9      for y in range(mb.BOARD_SIZE):
10          for x in range(mb.BOARD_SIZE):
11              color = "red" if (x, y) == mb.last_move else "black"
12              Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
13            
14  Marubatsu_GUI.draw_board = draw_board
```

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

```python
@staticmethod
def draw_board(ax, mb, dx=0, dy=0, lw=2):
    # ゲーム盤の枠を描画する
    for i in range(1, mb.BOARD_SIZE):
        ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k", lw=lw) # 横方向の枠線
        ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k", lw=lw) # 縦方向の枠線   

    # ゲーム盤のマークを描画する
    for y in range(mb.BOARD_SIZE):
        for x in range(mb.BOARD_SIZE):
            color = "red" if (x, y) == mb.last_move else "black"
            Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
            
Marubatsu_GUI.draw_board = draw_board
```
</details>

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

```diff_python
@staticmethod
-def draw_board(ax, mb, dx=0, dy=0):
+def draw_board(ax, mb, dx=0, dy=0, lw=2):
    # ゲーム盤の枠を描画する
    for i in range(1, mb.BOARD_SIZE):
-       ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k") # 横方向の枠線
+       ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k", lw=lw) # 横方向の枠線
-       ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k") # 縦方向の枠線 
+       ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k", lw=lw) # 縦方向の枠線 

    # ゲーム盤のマークを描画する
    for y in range(mb.BOARD_SIZE):
        for x in range(mb.BOARD_SIZE):
            color = "red" if (x, y) == mb.last_move else "black"
-           Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=2)
+           Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
            
Marubatsu_GUI.draw_board = draw_board
```
</details>

下記は、`draw_node` を修正したプログラムです。

__2 行目__：デフォルト値に `0.8` を設定した仮引数 `lw` を追加する。なお、この 0.8 は、試行錯誤した結果、`size` が `0.25` の場合に見やすいと筆者が感じた値である
__3、6 行目__：キーワード引数 `lw=lw` を追加することで、太さが `lw` の線を描画する

```python
1  def draw_node(self, size=0.25, lw=0.8):
元と同じなので省略    
2      # 自分自身のノードを (0, 0) に描画する
3      Marubatsu_GUI.draw_board(ax, self.mb, lw=lw)
4      # i 番の子ノードを (5, i * 4) に描画する
5      for i, childnode in enumerate(self.children):
6          Marubatsu_GUI.draw_board(ax, childnode.mb, dx=5, dy=i*4, lw=lw)
7        
8  Node.draw_node = draw_node
```

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

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

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

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように枠線の太さを調整できるようになったことが確認できます。なお、上記のプログラムでは、下記の値をデフォルト値に設定しましたが、他の値が良いと思った方は自由に変更して下さい。

```python
draw_node(rootnode, size=0.25, lw=0.8)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e4281a77-8ffe-127e-11bc-ec6acb2c082d.png" width="100">

## エッジを描画する処理の実装 その 1

エッジを描画する方法の一つに、下図のように、__親ノードの右から子ノードの左に直線を引く__ という方法があります。最初にこのエッジを描画する方法を紹介します。どのように下図のエッジを描画すればよいかについて少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b5124cc2-fc5e-3860-47aa-cde2c465b6e8.png" width="100">

### エッジの両端の座標の計算方法

上図のエッジを描画するためには、エッジの線の __両端の座標を計算する__ 必要があります。

下図は、親ノードと、上 2 つの子ノードを結ぶ線の両端の座標を表したものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/18ba74aa-7d94-3de8-8b91-dc014e1654c9.png" width="150">

上図から、親ノードと子ノードを結ぶ線の両端の座標は以下のようになることがわかります。なお、この座標の計算は先ほどのゲーム盤の座標と __考え方はほぼ同じ__ です。

|  | x 座標 | y 座標 |
|:--|:-:|:--|
| 親ノードの右  | 3.5  | 1.5  |
| 子ノード  | 4.5  | 1.5 からはじまり、4 ずつ増える  |

親ノードと子ノードの __ゲーム盤の左右の間隔は 2__ なので、エッジの __左右の点の x 座標の間隔を 2 以下__ にする必要があります。x 座標の間隔を 1 にした場合は、エッジの左の点の x 座標は 3.5、右の点の x 座標は 4.5 になります。

エッジの左の点の y 座標は、親ノードのゲーム盤の __ちょうど真ん中にする__ と見栄えが良いでしょう。ゲーム盤の縦幅は 3 なので、真ん中の y 座標はその半分の 1.5 になります。従って、親ノードの右のエッジの端の座標は __(3.5, 1.5)__ になります。

同様の理由で、一番上の子ノードの左のエッジの端の座標は __(4.5, 1.5)__ になります。

子ノードの左のエッジの端の y 座標は、子ノードの座標と同じ間隔にすれば良いので、i 番のインデックスの子ノードの左のエッジの端の座標は __(4.5, 1.5 + i * 4)__ で計算できます。

従って、下記のプログラムの 5 行目のように、子ノードを描画した後で（描画する前でもかまいません）、親ノードの右と子ノードの左を結ぶ線を `plot` メソッドで描画することで、エッジを描画することができます。

```python
1  def draw_node(self, size=0.25, lw=0.8):
元と同じなので省略
2      # i 番の子ノードを (5, i * 4) に描画する
3      for i, childnode in enumerate(self.children):
4          Marubatsu_GUI.draw_board(ax, childnode.mb, dx=5, dy=i*4, lw=lw)
5          plt.plot([3.5, 4.5], [1.5, 1.5 + i * 4], c="k", lw=lw)
6                
7  Node.draw_node = draw_node
```

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

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

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

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように、親ノードと子ノードを結ぶエッジが描画されるようになります。

```python
rootnode.draw_node()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b5124cc2-fc5e-3860-47aa-cde2c465b6e8.png" width="100">

## エッジを描画する処理の実装 その 2

上記の方法でエッジを描画すると、上図のようになりますが、下の方の子ノードのエッジは、他のエッジどうしが重なりあうため、__わかりにくい図__ になっています。そこで、本記事では、下図のようにエッジを描画することで、__エッジどうしが重ならない__ ようにします。下図のエッジをどのように描画すればよいかについて少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/788c712a-107c-d2a4-2ef9-bd3932602b2b.png" width="100">

### エッジの構成要素と座標の計算方法

下図は、親ノードと、上 2 つと最後の子ノードを結ぶエッジを表したものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9e8a9ae4-f929-f8ee-df20-ba71f343ddb8.png" width="200">

図から、エッジは、下記の 2 種類の線から構成されることがわかります。

* 親ノードから右にまっすぐ伸びた後に、真下に伸びる緑色の線
* 緑色の線から真横に子ノードに伸びる線

また、図から、それぞれの線の頂点の座標は下記のようになることがわかります。緑の折れ線の一番下の点の __y 座標は 1.5 + 子ノードの数 * 4 ではない__ 点に注意して下さい。

|  | 頂点の座標 |
|:--|:--|
| 緑色の折れ線  | (3.5, 1.5)、(4.0,1.5)、(4.0, 1.5 + (子ノードの数 - 1) * 4) |
| 子ノードの線  | i 番の要素のノードは (4.0, 1.5 + i * 4)、(4.5, 1.5 + i * 4) |

従って、下記のプログラムのように、親ノードを描画した後で上図の緑色の折れ線を描画し（実際の描画は黒色で行います）、子ノードを描画した後で子ノードの線を描画することで、先程の図のエッジを描画することができます。

* __4 行目__：上図の緑の折れ線と同じ形の線を、黒色で描画する
* __8 行目__：子ノードの線を描画する

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

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

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

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

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように、親ノードと子ノードを結ぶエッジが描画されるようになります。

```python
draw_node(rootnode, size=0.25, lw=0.8)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/788c712a-107c-d2a4-2ef9-bd3932602b2b.png" width="100">

## 他のノードと子ノードの描画

先程、`rootnode` の最初の子ノードに対して `calc_children` を実行して子ノードを計算したので、下記のプログラムで、rootnode の最初の子ノードを代入した `childnode` に対して `draw_node` を実行してみることにします。実行結果から、ルートノード以外のノードでも、`draw_node` で正しくノードと子ノードが描画されることが確認できます。

```python
childnode.draw_node()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/abb8fbba-72b0-584b-c931-6bd2d463e01b.png" width="100">

なお、現時点では `rootnode` の他の子ノードに対して `calc_children` を実行していないので、`draw_node` を実行しても子ノードは描画されません。

# `Marubatsu`、`Marubatsu_GUI` クラスのメソッドの修正

今回の記事では、`Marubatsu_GUI` クラスの __`draw_board` メソッドを修正__ したので、このままでは __`gui_play`__ を実行するとエラーが発生します。そこで、`draw_board` の修正に合わせて、`Marubatsu_GUI` クラスなどの定義を修正することにします。

今回の記事の最初のほうで、元の `draw_board` の名前を `update_gui` に修正することにしたので、`update_gui` を下記のプログラムのように定義します。

* __1 行目__：メソッドの名前を `draw_board` から `update_gui` に修正する
* __2、3 行目__：2 行目の下にあったゲーム盤を描画する処理を削除し、3 行目の `draw_board` の呼び出しに置き換える

```python
1  def update_gui(self):
元と同じなので省略   
2      # この下にあったゲーム盤を描画する処理を削除する
3      self.draw_board(ax, self.mb)
4    
5      self.update_widgets_status()   
6    
7  Marubatsu_GUI.update_gui = update_gui
```        

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

```python
def update_gui(self):
    ax = self.ax
    ai = self.mb.ai
    
    # Axes の内容をクリアして、これまでの描画内容を削除する
    ax.clear()
    
    # y 軸を反転させる
    ax.invert_yaxis()
    
    # 枠と目盛りを表示しないようにする
    ax.axis("off")   
    
    # リプレイ中、ゲームの決着がついていた場合は背景色を変更する
    is_replay =  self.mb.move_count < len(self.mb.records) - 1 
    if self.mb.status == Marubatsu.PLAYING:
        facecolor = "lightcyan" if is_replay else "white"
    else:
        facecolor = "lightyellow"

    ax.figure.set_facecolor(facecolor)
        
    # 上部のメッセージを描画する
    # 対戦カードの文字列を計算する
    names = []
    for i in range(2):
        names.append("人間" if ai[i] is None else ai[i].__name__)
    ax.text(0, 3.5, f"{names[0]}　VS　{names[1]}", fontsize=20)   
    
    # ゲームの決着がついていない場合は、手番を表示する
    if self.mb.status == Marubatsu.PLAYING:
        text = "Turn " + self.mb.turn
    # 引き分けの場合
    elif self.mb.status == Marubatsu.DRAW:
        text = "Draw game"
    # 決着がついていれば勝者を表示する
    else:
        text = "Winner " + self.mb.status
    # リプレイ中の場合は "Replay" を表示する
    if is_replay:
        text += " Replay"
    ax.text(0, -0.2, text, fontsize=20)
    
    self.draw_board(ax, self.mb)
    
    self.update_widgets_status()   
    
Marubatsu_GUI.update_gui = update_gui
```
</details>

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

```diff_python
-def draw_board(self):
+def update_gui(self):
元と同じなので省略   
    # ゲーム盤の枠を描画する
-   for i in range(1, self.mb.BOARD_SIZE):
-       ax.plot([0, self.mb.BOARD_SIZE], [i, i], c="k") # 横方向の枠線
-       ax.plot([i, i], [0, self.mb.BOARD_SIZE], c="k") # 縦方向の枠線   

    # ゲーム盤のマークを描画する
-   for y in range(self.mb.BOARD_SIZE):
-       for x in range(self.mb.BOARD_SIZE):
-           color = "red" if (x, y) == self.mb.last_move else "black"
-           self.draw_mark(ax, x, y, self.mb.board[x][y], color)       
+   self.draw_board(ax, self.mb)
    
    self.update_widgets_status()   
    
Marubatsu_GUI.update_gui = update_gui
```
</details>

`draw_board` の名前を `update_gui` に変更したので、`draw_board` を利用していたプログラムを修正する必要があります。

下記は、`play_loop` メソッドの修正です。

* __7、11 行目__：`draw_board` を `update_gui` に修正する

```python
 1  def play_loop(self, mb_gui):   
元と同じなので省略
 2          # ゲーム盤の表示
 3          if verbose:
 4              if gui:
 5                  # AI どうしの対戦の場合は画面を描画しない
 6                  if ai[0] is None or ai[1] is None:
 7                      mb_gui.update_gui()
元と同じなので省略
 8      # 決着がついたので、ゲーム盤を表示する
 9      if verbose:
10          if gui:
11              mb_gui.update_gui()
元と同じなので省略
12
13  Marubatsu.play_loop = play_loop
```

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

```python
def play_loop(self, mb_gui):   
    ai = self.ai
    params = self.params
    verbose = self.verbose
    gui = self.gui
    
    # ゲームの決着がついていない間繰り返す
    while self.status == Marubatsu.PLAYING:
        # 現在の手番を表す ai のインデックスを計算する
        index = 0 if self.turn == Marubatsu.CIRCLE else 1
        # ゲーム盤の表示
        if verbose:
            if gui:
                # AI どうしの対戦の場合は画面を描画しない
                if ai[0] is None or ai[1] is None:
                    mb_gui.update_gui()
                # 手番を人間が担当する場合は、play メソッドを終了する
                if ai[index] is None:
                    return
            else:
                print(self)
                
        # ai が着手を行うかどうかを判定する
        if ai[index] is not None:
            x, y = ai[index](self, **params[index])
        else:
            # キーボードからの座標の入力
            coord = input("x,y の形式で座標を入力して下さい。exit を入力すると終了します")
            # "exit" が入力されていればメッセージを表示して関数を終了する
            if coord == "exit":
                print("ゲームを終了します")
                return       
            # x 座標と y 座標を要素として持つ list を計算する
            xylist = coord.split(",")
            # xylist の要素の数が 2 ではない場合
            if len(xylist) != 2:
                # エラーメッセージを表示する
                print("x, y の形式ではありません")
                # 残りの while 文のブロックを実行せずに、次の繰り返し処理を行う
                continue
            x, y = xylist
        # (x, y) に着手を行う
        try:
            self.move(int(x), int(y))
        except:
            print("整数の座標を入力して下さい")

    # 決着がついたので、ゲーム盤を表示する
    if verbose:
        if gui:
            mb_gui.update_gui()
        else:
            print(self)
            
    return self.status

Marubatsu.play_loop = play_loop
```
</details>

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

```diff_python
def play_loop(self, mb_gui):   
元と同じなので省略
        # ゲーム盤の表示
        if verbose:
            if gui:
                # AI どうしの対戦の場合は画面を描画しない
                if ai[0] is None or ai[1] is None:
-                   mb_gui.draw_board()
+                   mb_gui.update_gui()
元と同じなので省略
    # 決着がついたので、ゲーム盤を表示する
    if verbose:
        if gui:
-           mb_gui.draw_board()
+           mb_gui.update_gui()
元と同じなので省略

Marubatsu.play_loop = play_loop
```
</details>

下記は、`create_event_handler` を修正したプログラムです。

* __13、18 行目__：`draw_board` を `update_gui` に修正する

```python
 1  import math
 2  from datetime import datetime
 3  from tkinter import Tk, filedialog
 4  import pickle
 5
 6  def create_event_handler(self):
元と同じなので省略
 7      # 待ったボタンのイベントハンドラを定義する
 8      def on_undo_button_clicked(b=None):
 9          if self.mb.move_count >= 2 and self.mb.move_count == len(self.mb.records) - 1:
10              self.mb.move_count -= 2
11              self.mb.records = self.mb.records[0:self.mb.move_count+1]
12              self.mb.change_step(self.mb.move_count)
13              self.update_gui()
元と同じなので省略
14      # step 手目の局面に移動する
15      def change_step(step):
16          self.mb.change_step(step)
17          # 描画を更新する
18          self.update_gui()        
元と同じなので省略
19    
20  Marubatsu_GUI.create_event_handler = create_event_handler
```

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

```python
import math
from datetime import datetime
from tkinter import Tk, filedialog
import pickle

def create_event_handler(self):
    # 乱数の種のチェックボックスのイベントハンドラを定義する
    def on_checkbox_changed(changed):
        self.update_widgets_status()
        
    self.checkbox.observe(on_checkbox_changed, names="value")

    # 開く、保存ボタンのイベントハンドラを定義する
    def on_load_button_clicked(b=None):
        path = filedialog.askopenfilename(filetypes=[("〇×ゲーム", "*.mbsav")],
                                        initialdir="save")
        if path != "":
            with open(path, "rb") as f:
                data = pickle.load(f)
                self.mb.records = data["records"]
                self.mb.ai = data["ai"]
                change_step(data["move_count"])
                for i in range(2):
                    value = "人間" if self.mb.ai[i] is None else self.mb.ai[i]
                    self.dropdown_list[i].value = value               
                if data["seed"] is not None:                   
                    self.checkbox.value = True
                    self.inttext.value = data["seed"]
                else:
                    self.checkbox.value = False
                    
    def on_save_button_clicked(b=None):
        name = ["人間" if self.mb.ai[i] is None else self.mb.ai[i].__name__
                for i in range(2)]
        timestr = datetime.now().strftime("%Y年%m月%d日 %H時%M分%S秒")
        fname = f"{name[0]} VS {name[1]} {timestr}"
        path = filedialog.asksaveasfilename(filetypes=[("〇×ゲーム", "*.mbsav")],
                                            initialdir="save", initialfile=fname,
                                            defaultextension="mbsav")
        if path != "":
            with open(path, "wb") as f:
                data = {
                    "records": self.mb.records,
                    "move_count": self.mb.move_count,
                    "ai": self.mb.ai,
                    "seed": self.inttext.value if self.checkbox.value else None
                }
                pickle.dump(data, f)
                
    def on_help_button_clicked(b=None):
        self.output.clear_output()
        with self.output:
            print("""操作説明

マスの上でクリックすることで着手を行う。
下記の GUI で操作を行うことができる。
()が記載されているものは、キー入力で同じ操作を行うことができることを意味する。
なお、キー入力の操作は、ゲーム盤をクリックして選択状態にする必要がある。

乱数の種\tチェックボックスを ON にすると、右のテキストボックスの乱数の種が適用される
開く(-,L)\tファイルから対戦データを読み込む
保存(+,S)\tファイルに対戦データを保存する
？(*,H)\t\tこの操作説明を表示する
手番の担当\tメニューからそれぞれの手番の担当を選択する
\t\tメニューから選択しただけでは担当は変更されず、変更またはリセットボタンによって担当が変更される
変更\t\tゲームの途中で手番の担当を変更する
リセット\t手番の担当を変更してゲームをリセットする
待った(0)\t1つ前の自分の着手をキャンセルする
<<(↑)\t\t最初の局面に移動する
<(←)\t\t1手前の局面に移動する
>(→)\t\t1手後の局面に移動する
>>(↓)\t\t最後の着手が行われた局面に移動する
スライダー\t現在の手数を表す。ドラッグすることで任意の手数へ移動する

手数を移動した場合に、最後の着手が行われた局面でなければ、リプレイモードになる。
リプレイモード中に着手を行うと、リプレイモードが解除され、その着手が最後の着手になる。""")
            
    self.load_button.on_click(on_load_button_clicked)
    self.save_button.on_click(on_save_button_clicked)
    self.help_button.on_click(on_help_button_clicked)
    
    # 変更ボタンのイベントハンドラを定義する
    def on_change_button_clicked(b):
        for i in range(2):
            self.mb.ai[i] = None if self.dropdown_list[i].value == "人間" else self.dropdown_list[i].value
        self.mb.play_loop(self)

    # リセットボタンのイベントハンドラを定義する
    def on_reset_button_clicked(b=None):
        # 乱数の種のチェックボックスが ON の場合に、乱数の種の処理を行う
        if self.checkbox.value:
            random.seed(self.inttext.value)
        self.mb.restart()
        self.output.clear_output()
        on_change_button_clicked(b)

    # 待ったボタンのイベントハンドラを定義する
    def on_undo_button_clicked(b=None):
        if self.mb.move_count >= 2 and self.mb.move_count == len(self.mb.records) - 1:
            self.mb.move_count -= 2
            self.mb.records = self.mb.records[0:self.mb.move_count+1]
            self.mb.change_step(self.mb.move_count)
            self.update_gui()
        
    # イベントハンドラをボタンに結びつける
    self.change_button.on_click(on_change_button_clicked)
    self.reset_button.on_click(on_reset_button_clicked)   
    self.undo_button.on_click(on_undo_button_clicked)   
    
    # step 手目の局面に移動する
    def change_step(step):
        self.mb.change_step(step)
        # 描画を更新する
        self.update_gui()        

    def on_first_button_clicked(b=None):
        change_step(0)

    def on_prev_button_clicked(b=None):
        change_step(self.mb.move_count - 1)

    def on_next_button_clicked(b=None):
        change_step(self.mb.move_count + 1)
        
    def on_last_button_clicked(b=None):
        change_step(len(self.mb.records) - 1)

    def on_slider_changed(changed):
        if self.mb.move_count != changed["new"]:
            change_step(changed["new"])
            
    self.first_button.on_click(on_first_button_clicked)
    self.prev_button.on_click(on_prev_button_clicked)
    self.next_button.on_click(on_next_button_clicked)
    self.last_button.on_click(on_last_button_clicked)
    self.slider.observe(on_slider_changed, names="value")
    
    # ゲーム盤の上でマウスを押した場合のイベントハンドラ
    def on_mouse_down(event):
        # Axes の上でマウスを押していた場合のみ処理を行う
        if event.inaxes and self.mb.status == Marubatsu.PLAYING:
            x = math.floor(event.xdata)
            y = math.floor(event.ydata)
            with self.output:
                self.mb.move(x, y)                
            # 次の手番の処理を行うメソッドを呼び出す
            self.mb.play_loop(self)

    # ゲーム盤を選択した状態でキーを押した場合のイベントハンドラ
    def on_key_press(event):
        keymap = {
            "up": on_first_button_clicked,
            "left": on_prev_button_clicked,
            "right": on_next_button_clicked,
            "down": on_last_button_clicked,
            "0": on_undo_button_clicked,
            "enter": on_reset_button_clicked,            
            "-": on_load_button_clicked,            
            "l": on_load_button_clicked,            
            "+": on_save_button_clicked,            
            "s": on_save_button_clicked,            
            "*": on_help_button_clicked,            
            "h": on_help_button_clicked,            
        }
        if event.key in keymap:
            keymap[event.key]()
        else:
            try:
                num = int(event.key) - 1
                event.inaxes = True
                event.xdata = num % 3
                event.ydata = 2 - (num // 3)
                on_mouse_down(event)
            except:
                pass
            
    # fig の画像イベントハンドラを結び付ける
    self.fig.canvas.mpl_connect("button_press_event", on_mouse_down)     
    self.fig.canvas.mpl_connect("key_press_event", on_key_press)    
    
Marubatsu_GUI.create_event_handler = create_event_handler
```
</details>

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

```diff_python
import math
from datetime import datetime
from tkinter import Tk, filedialog
import pickle

def create_event_handler(self):
元と同じなので省略
    # 待ったボタンのイベントハンドラを定義する
    def on_undo_button_clicked(b=None):
        if self.mb.move_count >= 2 and self.mb.move_count == len(self.mb.records) - 1:
            self.mb.move_count -= 2
            self.mb.records = self.mb.records[0:self.mb.move_count+1]
            self.mb.change_step(self.mb.move_count)
-           self.draw_board()
+           self.update_gui()
元と同じなので省略
    # step 手目の局面に移動する
    def change_step(step):
        self.mb.change_step(step)
        # 描画を更新する
-       self.draw_board()
+       self.update_gui()
元と同じなので省略
    
Marubatsu_GUI.create_event_handler = create_event_handler
```
</details>

実行結果は省略しますが、上記の修正後に、下記のプログラムで `gui_play` を実行し、プログラムが正しく動作することを確認して下さい。

```python
from util import gui_play

gui_play()
```

# 今回の記事のまとめ

今回の記事では、ゲーム木と木構造の説明をし、ノードの作成と子ノードの計算、親ノードと子ノードの関係を視覚化するプログラムを実装しました。

なお、ノードなどの、ゲーム木に関連するプログラムは、tree.py というファイルに保存することにします。

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/088/marubatsu_new.py

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

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

# 次回の記事

https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5

[^1]:node は、数学では 2 つの線が接する縁（ふち）を表す用語です
[^2]:edge は、数学では図形や線の辺を表す用語です
[^3]:`x`、`y` という名前の変数は、`draw_board` の中で別の用途で使用されているので、Axes の原点からの差分（difference）を表すことから `dx`、`dy` という名前の変数にしました