Pythonで〇×ゲームのAIを一から作成する　その105　ミニマックス法によるゲーム木の全てのノードの評価値の計算

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/38f2c8167a14eb99d86c

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

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

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

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

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

# ゲーム木を用いた最強の AI の作成

これまでの記事で作成した __ゲーム木を利用__ することで、__全ての局面__ で __局面の状況__ と、__最善手を調べる__ ことができます。それによって、[以前の記事](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 を作成__ することができます。

そこで、今回の記事ではゲーム木を利用して、全ての局面での局面の状況と、最善手を調べる方法について説明します。

## 局面の状況の意味

まず、いくつかの用語のおさらいをします。

__[最善手](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E6%84%8F%E5%91%B3%E3%81%A8%E3%83%91%E3%83%A9%E3%83%89%E3%83%83%E3%82%AF%E3%82%B9%E3%81%8C%E8%B5%B7%E3%81%8D%E3%82%8B%E7%90%86%E7%94%B1)__ とは、__お互いが最善手を選択し続けた場合__ に、自分にとって __最も有利となる合法手__ のことです。

__[最強の AI](https://qiita.com/ysgeso/items/d7f60ba34f167f77a87e#%E3%80%87%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E6%9C%80%E5%BC%B7%E3%81%AE-ai-%E3%81%AE%E5%86%8D%E5%AE%9A%E7%BE%A9)__ とは、__全ての局面で最善手を選択する AI__ のことです。以前の記事で作成したルールベースの [`ai14`](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#ai14s-%E3%81%AE%E5%AE%9A%E7%BE%A9) は、その AI が着手を行った場合に出現しない局面では、最善手を選択するかどうかが保証されないので、__弱解決の AI__ です。

また、[以前の記事](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E6%9C%80%E5%BC%B7%E3%81%AE-ai-%E3%81%A9%E3%81%86%E3%81%97%E3%81%AE%E5%AF%BE%E6%88%A6)で説明したように、〇×ゲームのような __[二人零和有限確定完全情報ゲーム](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E6%80%A7%E8%B3%AA%E3%81%AE%E5%88%B6%E9%99%90)__ で、ゲームの結果 が、勝利、敗北、引き分け の 3 種類に分類される場合は、__全ての局面__ は、その局面から __最強の AI どうしが対戦した結果__ によって、「__先手の必勝の局面__」、「__引き分けの局面__」、「__後手の必勝の局面__」 の __3 つの状況に分類__ することができます。

つまり、ゲーム木の __全てのノードに対して__、そのノードの局面の状況が、この __3 つのどれに分類されるかが判明すれば__、その情報を元に最善手を選択できるようになり、その結果、__最強の AI を作成することができる__ ようになります。

## 局面の状況を表すデータの定義

プログラムで局面の状況を扱うためには、__3 つの局面の状況__ を __どのようなデータで表現するかを決める__ 必要があります。どのようなデータを割り当てるかについては、様々な方法が考えられますが、__最善手を選択する際に比較を行う必要がある__ ので、大小の比較を行うことができる __数値で表すのが良い__ でしょう。また、その数値はいずれかのプレイヤーの立場から見て __有利な局面の状況のほうが大きな値__ にします。そうすることによって、__もう片方__ のプレイヤーの立場から見ると、__小さな値の方が有利な局面__ を意味するようになります。

本記事では、上記の条件を満たす値として、下記の表のようなデータを割り当てることにしますが、他のデータを割り当てたり、× のプレイヤーが有利になる局面の状況のほうを大きな値に設定してもかまいませんので、別の値を割り当てたい人は自由に変更して下さい。

なお、〇×ゲームでは、先手は 〇 のプレイヤー、後手は × のプレイヤーなので、局面の状況を「〇の必勝の局面」、「引き分けの局面」、「×の必勝の局面」と言い換えました。

| 局面の今日今日 | データ |
|:--|:-:|
| __〇の必勝の局面__  | 1  |
| __引き分けの局面__  | 0  |
| __×の必勝の局面__  |  -1  |

上記のように、〇 のプレイヤーから見て有利な状態に、より大きな数値を割り当てることで、このデータを〇 のプレイヤーの立場から見た局面の __[評価値](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)__ として考えることができるようになるので、以後は __局面の状況のことを評価値と呼ぶ__ ことにします。

全てのゲーム木のノードに対して、この評価値がわかれば、以下の方法で __全ての局面の最善手を計算__ することができるようになります。

* __〇 のプレイヤーの手番__ のノードの場合は、子ノードの中で __最も評価値が高い__ ノードへの着手を選択する
* __× のプレイヤーの手番__ のノードの場合は、子ノードの中で、__最も評価値が低い__ ノードへの着手を選択する

## 評価値を計算するアルゴリズム

次に、ゲーム木の全てのノードの評価値を計算する方法を紹介します。どのような方法で計算できるかについて少し考えてみて下さい。

### リーフノードの評価値の計算

ゲーム木のノードの中で、__評価値が確定しているノード__ があります。それは、__ゲームの決着が付いた__、子ノードが存在しないゲーム木の末端の __リーフノード__ です。〇 の勝利の局面は、〇 の必勝の局面でもあるので、それらのノードに下記の表の評価値を割り当てます。

| 状態 | 評価値 |
|:--|:-:|
| __〇 の勝利（〇 の必勝の局面）__  | 1  |
| __引き分け（引き分けの局面）__  | 0  |
| __× の勝利（× の必勝の局面）__  |  -1  |

### 全ての子ノードの評価値が求められているノードの評価値の計算

次に、__全ての子ノードの評価値が求められている__ ノードを探し、その評価値を以下の方法で計算します。これは、「自分にとって __最も有利となる着手を選択__ する」という __最善手の定義から明らか__ でしょう。

* ノードが __〇 の手番__ の場合は、子ノードの評価値の中で __最も高い__ 評価値とする
* ノードが __× の手番__ の場合は、子ノードの評価値の中で __最も低い__ 評価値とする

上記の方法で評価値を計算する計算を繰り返すことで、全てのノードの評価値が計算できます。なお、そのことの証明は後で行います。

### 評価値を計算するアルゴリズムのまとめ

__評価値の計算を行うアルゴリズム__ をまとめると以下のようになります。

:::note warn
1. ゲームの決着がついている __リーフノードの評価値を全て計算__ する
2. __全ての子ノードの評価値が求められている__ ノードの評価値を計算する
3. 手順 2 を、全ての子ノードの評価値が求められているノードが __なくなるまで__ 繰り返す

ただし、手順 2 では、以下の方法で評価値を計算する。

* ノードが 〇 の手番の場合は、子ノードの評価値の中で最も高い評価値とする
* ノードが × の手番の場合は、子ノードの評価値の中で最も低い評価値とする
:::

## アルゴリズムの処理の流れの具体例

具体例として、上記のアルゴリズムで、下図の〇×ゲームの部分木の全てのノードの評価値を計算する処理の流れを紹介します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7eb40c0c-28bd-6940-c581-a6bf5915216b.png" width="200">

### リーフノードの評価値の計算

上図の水色、黄色、ピンク色の局面が、決着がついているリーフノードの局面です。それぞれの色のノードの評価値は以下の表のようになります。


| 局面の色 | 局面の状態 | 評価値 |
|:--|:--|:-:|
| __水色__ | 〇 の勝利（〇 の必勝の局面）  | 1  |
| __黄色__ | 引き分け（引き分けの局面）  | 0  |
| __ピンク__| × の勝利（× の必勝の局面）  |  -1  |

色では具体的な評価値がわかりづらいので、下図のように具体的な評価値をゲーム盤の左上に表示します。また、新しく計算された評価値は赤色の文字で表示することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3ec5710e-c5a5-e444-6e9e-9265eb0dc172.png" width="200">

### 全ての子ノードの評価値が求められているノードの評価値の計算

上図で、全ての子ノードの評価値が求められているノードは、いずれも子ノードが 1 つしかないので、合法手は 1 つしかありません。そのため、それらのノードの評価値は、子ノードの評価値と等しくなります。下図は新しく計算したノードの評価値を加えたものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dcadf224-91a3-79bc-3f54-32270788383d.png" width="200">

上図で、全ての子ノードの評価値が求められている 3 つのノードは、いずれも __× の手番__ のノードで、子ノードが 2 つずつあります。そのため、それらのノードの評価値は、子ノードの評価値の中で __最も低い評価値__ になります。例えば、上のノードの子ノードの評価値は -1 と 1 なので、その評価値は -1 になります。実際に上のノードで (0, 2) に着手を行うと × が勝利するので、(0, 2) が × にとって最善手であることは明らかです。

下図は新しく計算したノードの評価値を加えたものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2a3ca617-6072-c70b-b321-9a81568ca63c.png" width="200">

上図で、全ての子ノードが求められているノードは、赤枠のノードだけです。赤枠のノードは __〇 の手番__ のノードなので、3 つの子ノードの評価値の中で __最も高い評価値__ である 0 になります。下図は新しく計算したノードの評価値を加えたものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/734808d1-1dfa-86b1-ddad-29678072a960.png" width="200">

これで全てのノードの評価値が計算できました。図から、赤枠のノードは、引き分けの局面であることがわかります。

## アルゴリズムの証明

下記のアルゴリズムの手順 1 と 2 が間違っていないことは明らかですが、このアルゴリズムで __全てのノードの評価値を計算できるか__ どうかに疑問を持つ人がいるのではないかと思います。そこで、このアルゴリズムで全てのノードの評価値を __計算できることを証明__ します。

1. ゲームの決着がついている __リーフノードの評価値を全て計算__ する
2. __全ての子ノードの評価値が求められている__ ノードの評価値を計算する
3. 手順 2 を、全ての子ノードの評価値が求められているノードが __なくなるまで__ 繰り返す

### 最も深いノードの性質

ゲーム木の __最も深いノードの深さを d__ とすると、__深さが d のノード__ は子ノードを持たないので __必ずリーフノードになります__。従って、手順 1 で全てのリーフノードの評価値が計算されると、__深さが d__ のノードは __全て評価値が計算される__ ことになります。

### 深さが d - 1 のノードの性質

次に、__深さが d - 1 のノード__ の性質を、__子ノードを持つ__ ノードと、__子ノードを持たない__ リーフノードで分けて考えます。

深さ d - 1 のノードが __子ノードを持つ__ 場合は、その __子ノードの深さは d__ になります。上記で説明したように、深さ d のノードは __全て評価値が計算されている__ ので、それらを元に __評価値を計算することができます__。

深さ d - 1 のノードが __リーフノード__ の場合は、手順 1 で __評価値は計算済__ です。

上記から、__深さ d - 1 のノード__ は __全て評価値を計算できる__ ことがわかります。

### 任意の深さのノードの性質

上記では、d はゲーム木の最も深いノードの深さを表していましたが、上記で説明したのと同じ理由で、__任意の深さ d__[^1] に対して下記の性質があることがわかります。

:::note warn
二人零和有限確定完全情報ゲームのゲーム木では、深さ d の全てのノードの評価値が計算されている場合は、深さ d - 1 の全てのノードの評価値を計算できる。
:::

従って、先程の __手順 2 の計算を繰り返すたび__ に、深さが d - 1、d - 2、・・・、1、0 の順で __全ての深さ__ のノードの __評価値を計算__ することができます。

# ミニマックス法を行うプログラムの実装

二人零和有限確定完全情報ゲームは、2 人のプレイヤーが交互に着手を行うので、そのゲーム木は深さが __偶数のノード__ が __先手の手番__ を、__奇数のノード__ が __後手の手番__ を表します。

また、評価値を計算するアルゴリズムでは、__先手のノード__ では子ノードの評価値の __最大値__（maximum）を、__後手__ のノードでは子ノードの評価値の __最小値__（minimam）を計算するので、深さの浅い順に、__最大値と最小値を交互に計算__ することになります。そのため、

そのため、二人零和有限確定完全情報ゲームの __評価値を表すゲーム木__ のことを __ミニマックス木（Mini-Max tree）__、__評価値を計算するアルゴリズム__ を __ミニマックス法__ と呼びます。

__ミニマックス法__ は先程の証明で説明したように、__最も深いノードから__ 順番に評価値を計算するので、ルートノードから始まる __トップダウンな繰り返し処理__ で実装できます。

ゲーム木の最も深いノードから順番に計算するトップダウンな繰り返し処理は、ゲーム木の部分木を描画した際の各ノードの高さを計算する Mbtree クラスの `calc_node_height` で実装済です。そのためミニマックス法は、__`calc_node_height` と同様の方法__ で実装することができるので、`calc_node_height` と比較しながら実装することにします。

## 幅優先アルゴリズムによる実装

ミニマックス法は __幅優先アルゴリズム__ と __深さ優先アルゴリズム__ の __どちらでも実装__ することができます。[前回の記事](https://qiita.com/ysgeso/items/38f2c8167a14eb99d86c#%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%82%92%E7%B0%A1%E6%BD%94%E3%81%AB%E8%A8%98%E8%BF%B0%E3%81%A7%E3%81%8D%E3%82%8B%E7%90%86%E7%94%B1-1)で説明したように、木構造に対するトップダウンな繰り返し処理は、__再帰呼び出しを使った深さ優先アルゴリズム__ で実装したほうが __簡単__ です。

その理由は、__幅優先アルゴリズム__ では __各ノードの深さの一覧を計算する必要がある__ 点ですが、Mbtree クラスではゲーム木の作成の際に、各ノードの深さの一覧を __`nodelist_by_depth` 属性に代入済__ なので、幅優先アルゴリズムでも __簡単に実装__ することができます。そこで、ミニマックス法を、幅優先と深さ優先アルゴリズムの両方で実装することにします。

### アルゴリズムの修正

__トップダウンな幅優先アルゴリズム__ では、下記のミニマックス法のアルゴリズムの処理を __そのまま行うことはできない__ ので __少しだけ修正__ する必要があります。

1. ゲームの決着がついている __リーフノードの評価値を全て計算__ する
2. __全ての子ノードの評価値が求められている__ ノードの評価値を計算する
3. 手順 2 を、全ての子ノードの評価値が求められているノードが __なくなるまで__ 繰り返す

具体的には、下記のように修正します。ただし、次に処理を行うゲーム木の深さを d と表記することにします。

1. 最も深いノードから、深さが 0 のノードの順に、下記の手順 2 の処理を行う
2. その深さの全てのノードに対して評価値を計算する

上記がミニマックス法と同じ処理を行うことは、先程の証明から明らかでしょう。

幅優先アルゴリズムでミニマックス法を実装する際に、for 文で実装する方法と、再帰呼び出しで実装する方法がありますが、for 文のほうが簡単なので、for 文で下記のようなメソッドを実装することにします。再帰呼び出しで実装したい人はチャレンジしてみて下さい。

なお、計算した __評価値をどこに記録するか__ を決める必要がありますが、本記事ではノードを表す __Node__ クラスの __`score` 属性__ にその値を代入することにします。

__名前__：幅優先アルゴリズムで評価値（score）を計算するので、`calc_score_by_bf` とする
__処理__：全てのノードの評価値を計算し、ノードの `score` 属性に代入する
__入力__：なし
__出力__：なし

### 組み込み関数 `reversed` の説明

`calc_score_by_bf` では、`nodelist_by_depth` 属性に代入された各深さのノードの一覧のデータを、__深さの深い順で取り出す__ 必要があります。そのためには、`nodelist_by_depth` の要素を、__後ろから順番に取り出す__ という __繰り返し処理__ が必要になります。

そのような処理は、list や dict などの、[シーケンス型](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#%E3%82%B7%E3%83%BC%E3%82%B1%E3%83%B3%E3%82%B9%E5%9E%8B%E3%81%A8%E3%81%AF%E4%BD%95%E3%81%8B) の要素を __逆順に取り出す__ ことができる __反復可能オブジェクトを作成__ する、組み込み関数 __`reversed`__ を利用することができます。

下記のプログラムは、`reversed` の使用例です。実行結果のように、for 文に `reversed(a)` を記述することで、`a` の要素が後ろから順番に取り出されて表示されます。

```python
a = [1, 2, 3]
for num in reversed(a):
    print(num)
```

実行結果

```
3
2
1
```

なお、`reversed` を実行しても、`reversed` の 実引数に記述した __データの要素が逆順になるわけではありません__。実際に、上記を実行後に下記のプログラムで `a` を表示すると、__要素の順番が変化していない__ ことが確認できます。

```python
print(a)
```

実行結果

```
[1, 2, 3]
```

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

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

:::note
list などの __シーケンス型__ のデータは、__`reverse` メソッド__ を利用することで、下記のプログラムのように __その list の要素を逆順に入れ替える__ ことができます。組み込み関数 `reversed` と似ていますが、__意味が大きく異なる__ 点に注意して下さい。

```python
a.reverse()
print(a)
```

実行結果

```
[3, 2, 1]
```

シーケンス型の `reverse` メソッドの詳細については、下記のリンク先を参照して下さい。
:::

https://docs.python.org/ja/3/library/stdtypes.html#mutable-sequence-types

### `calc_score_by_bf` の定義

下記は、`calc_score_by_bf` で実装するアルゴリズムの再掲です。

1. 最も深いノードから、深さが 0 のノードの順に、下記の手順 2 の処理を行う
2. その深さの全てのノードに対して評価値を計算する

下記は、`calc_score_by_bf` の定義です。5 行目の for 文が手順 1 を、6 ~ 19 行目の for 文が手順 2 の処理を行います。

* __5 行目__：`nodelist_by_depth` 属性に代入されている各深さのノードの一覧のデータを `reversed` を使って深さの深い順に取り出して `nodelist` に代入する繰り返し処理を行う
* __6 行目__：`nodelist` から順番にノードのデータを取り出して `node` に代入する繰り返し処理を行う
* __7 ~ 12 行目__：`node` の局面が決着がついている場合は、決着の状態に応じた評価値を `score` 属性に代入する
* __14 行目__：決着がついていない場合は、list 内包表記を使って、`node` の子ノードの評価値を要素として持つ list を作成し、`score_list` に代入する
* __15、16 行目__：局面の手数を表す `move_count` 属性が偶数（2 で割った余りが 0 になる）の場合はの場合は 〇 の手番なので、`score_list` の最大値を計算する
* __17、18 行目__：奇数の場合は × の手番なので、`score_list` の最小値を計算する
* __19 行目__：計算した評価値を `node` の `score` 属性に代入する

```python
 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3
 4  def calc_score_by_bf(self):
 5      for nodelist in reversed(self.nodelist_by_depth):
 6          for node in nodelist:
 7              if node.mb.status == Marubatsu.CIRCLE:
 8                  node.score = 1
 9              elif node.mb.status == Marubatsu.DRAW:
10                  node.score = 0
11              elif node.mb.status == Marubatsu.CROSS:
12                  node.score = -1
13              else:
14                  score_list = [childnode.score for childnode in node.children]
15                  if node.mb.move_count % 2 == 0:
16                      score = max(score_list)
17                  else:
18                      score = min(score_list)
19                  node.score = score
20
21  Mbtree.calc_score_by_bf = calc_score_by_bf             
```

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

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

def calc_score_by_bf(self):
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
                score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように、ルートノードの評価値として、引き分けの局面であることを表す 0 が表示されます。〇×ゲームは、ゲーム開始時の局面は引き分けの局面なのでこれは正しい値です。

* __1 行目__：Mbtree クラスの [`load`](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#load-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9)メソッドを使って[以前の記事](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#save-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9F%E8%A3%85)で保存した、幅優先アルゴリズムで作成した Mbtree のインスタンスをファイルから読み込む
* __2 行目__：`calc_score_by_bf` を実行して、ゲーム木の全てのノードの評価値を計算する
* __3 行目__：ルートノードの評価値を表示する

```python
mbtree_bf = Mbtree.load("bftree")
mbtree_bf.calc_score_by_bf()
print(mbtree_bf.root.score)
```

実行結果

```
0
```

:::note
上記では、幅優先アルゴリズムでゲーム木を作成したインスタンスのファイルを読み込みましたが、__深さ優先アルゴリズムでゲーム木を作成__ したインスタンスを読み込んでも、__ゲーム木の構成は全く同じ__ なので同じ結果になります。
:::

## 評価値の視覚化

上記でルートノードの評価値が正しく計算されたことが確認できましたが、このままでは他のノードの評価値がどのように計算されているかを確認するのが大変です。そこで、__ゲーム木を GUI で視覚化__ する __Mbtree_GUI__ クラスを改良して、__ゲーム盤の背景色に評価値を表す色を付けて表示__ することで __評価値を視覚化__ することにします。その際に、それぞれの評価値に対しては、決着が付いた際のゲーム盤と同じ色でゲーム盤を表示することにします。

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

ゲームの __決着がついた局面__ のゲーム盤の背景色は、Marubatsu_GUI クラスの `draw_board` 内の下記のプログラムで描画していますが、__ノードの評価値の情報__ は、__Marubatsu__ クラスには __記録されていない__ ので、このままでは `draw_board` で __決着がついていない局面__ に対して、評価値に応じた __背景色を描画することはできません__。

```python
@staticmethod
def draw_board(ax, mb, show_result=False, emphasize=False, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
        elif mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
        elif mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"
        rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, fc=bgcolor)
        ax.add_patch(rect)
略
```

そこで、`draw_board` に __評価値を代入__ する __`score` という仮引数と追加__ し、__`score` の値に応じて背景色を変更する__ ように修正することにします。

ただし、__互換性を考慮__ して、`score` をデフォルト値を `None` としたデフォルト引数とし、__`score` が `None` の場合__ は、__これまでと同じ方法でゲーム盤を表示__ することにします。

行いたい処理は、__ゲーム盤の背景色__ を以下のようにする処理です。

* `score` が `None` でなければ、`score` の評価値に応じた色にする
* `score` が `None` の場合は、ゲームの状態に応じた色にする

そのため、プログラムでは、それぞれの色を描画する条件式を記述する必要があります。

評価値は、「〇 の必勝の局面」、「引き分けの局面」、「× の必勝の局面」の 3 種類しかないので、__`score` が `None` でない場合__ は、ゲーム盤の背景色がゲーム中であることを表す __`"white"` になることは決してありません__。

従って、ゲーム盤の背景色が __`"white"` になる__ のは __「`score` が `None`」 なおかつ「ゲームの状態がゲーム中」__ という条件が満たされた場合であることがわかります。

背景色が __`"lightcyan"`__ になる条件は、__「`score` が `1`」または「ゲームの状態が 〇 の勝利の場合」__ です。__残りの 2 色に関しても同様__ です。

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

* __5 行目__：デフォルト値を `None` とする仮引数 `score` を追加する
* __8 行目__：「`score` が `None`」なおかつ「ゲーム中状態がゲーム中」の場合に背景色を白色で描画するように修正する
* __10 行目__：〇 の必勝の局面を表す `score` が 1 の場合を条件に加える
* __12 行目__：× の必勝の局面を表す `score` が -1 の場合を条件に加える
* __14 行目__：引き分けの局面を表す `score` が 0 の場合は、どの条件式も `True` にならないので、`else` のブロックが実行されるので、この部分は修正する必要はない

```python
 1  from marubatsu import Marubatsu_GUI
 2  import matplotlib.patches as patches
 3
 4  @staticmethod
 5  def draw_board(ax, mb, show_result=False, score=None, emphasize=False, dx=0, dy=0, lw=2):
 6      # 結果によってゲーム盤の背景色を変更する
 7      if show_result:
 8          if score is None and mb.status == Marubatsu.PLAYING:
 9              bgcolor = "white"
10          elif score == 1 or mb.status == Marubatsu.CIRCLE:
11              bgcolor = "lightcyan"
12          elif score == -1 or mb.status == Marubatsu.CROSS:
13              bgcolor = "lavenderblush"
14          else:
15              bgcolor = "lightyellow"
16          rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
17                                  height=mb.BOARD_SIZE, fc=bgcolor)
18          ax.add_patch(rect)
元と同じなので省略
19            
20  Marubatsu_GUI.draw_board = draw_board
```

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

```python
from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches

@staticmethod
def draw_board(ax, mb, show_result=False, score=None, emphasize=False, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
        elif score == 1 or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
        elif score == -1 or mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"
        rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, fc=bgcolor)
        ax.add_patch(rect)

    # emphasize が True の場合は赤色の外枠を描画する
    if emphasize:
        frame = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, ec="red", fill=False, lw=lw)
        ax.add_patch(frame)
    
    # ゲーム盤の枠を描画する
    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
from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches

@staticmethod
-def draw_board(ax, mb, show_result=False, emphasize=False, dx=0, dy=0, lw=2):
+def draw_board(ax, mb, show_result=False, score=None, emphasize=False, dx=0, dy=0, lw=2):
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
-       if mb.status == Marubatsu.PLAYING:
+       if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
-       elif mb.status == Marubatsu.CIRCLE:
+       elif score == 1 or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
-       elif mb.status == Marubatsu.CROSS:
+       elif score == -1 or mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"
        rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, fc=bgcolor)
        ax.add_patch(rect)
元と同じなので省略
            
Marubatsu_GUI.draw_board = draw_board
```
</details>

### `draw_node` の修正

次に、`draw_board` を呼び出す、Node クラスの `draw_node` メソッドを以下のプログラムのように修正します。

* __6 行目__：`draw_board` の実引数に `score=self.score` を追加する
* __11 行目__：`draw_board` の実引数に `score=childnode.score` を追加する。この行では、__子ノードを描画__ しているので、__`childnode.score` とする必要がある__ 点に注意する事

```python
 1  from tree import Node, Rect
 2  import matplotlib.pyplot as plt
 3
def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
 4      # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
 5      y = dy + (self.height - 3) / 2
 6      Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
 7      rect = Rect(dx, y, 3, 3)
 8      # 子ノードが存在する場合に、エッジの線と子ノードを描画する
 9      if len(self.children) > 0:
元と同じなので省略
10                  if maxdepth is None:
11                       Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
12                                                score=childnode.score, dx=dx+5, dy=childnodey, lw=lw)
元と同じなので省略
13
14  Node.draw_node = draw_node
```

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

```python
from tree import Node, Rect
import matplotlib.pyplot as plt

def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    if ax is None:
        height = len(self.children) * 4
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")
        for childnode in self.children:
            childnode.height = 4
        self.height = height         
        
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
        if maxdepth != self.depth:   
            plt.plot([dx + 3.5, dx + 4], [y + 1.5, y + 1.5], c="k", lw=lw)
            prevy = None
            for childnode in self.children:
                childnodey = dy + (childnode.height - 3) / 2
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True, score=childnode.score, dx=dx+5, dy=childnodey, lw=lw)
                edgey = childnodey + 1.5
                plt.plot([dx + 4 , dx + 4.5], [edgey, edgey], c="k", lw=lw)
                if prevy is not None:
                    plt.plot([dx + 4 , dx + 4], [prevy, edgey], c="k", lw=lw)
                prevy = edgey
                dy += childnode.height
        else:
            plt.plot([dx + 3.5, dx + 4.5], [y + 1.5, y + 1.5], c="k", lw=lw)
            
    return rect

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

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

```diff_python
from tree import Node, Rect
import matplotlib.pyplot as plt

def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
-   Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, emphasize=emphasize, lw=lw, dx=dx, dy=y)
+   Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
元と同じなので省略
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
-                                            dx=dx+5, dy=childnodey,     
+                                            score=childnode.score, dx=dx+5, dy=childnodey, lw=lw)
元と同じなので省略

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

### 視覚化の確認

上記の修正後に、下記のプログラムで視覚化を行うと、実行結果のように各ノードのゲーム盤に評価値に応じた背景色の色がつくようになります。黄色は引き分けの局面を表しているので、1 手目を着手した後の局面は全て引き分けの局面であることがわかります。

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

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b7477be6-3225-0ba2-ec54-8609dcb5d2af.png" width="150">

下図は、1 手目で真ん中の (1, 1) に着手したノードを中心とした部分木の図です。図から、その局面が以下の性質を持つ事がわかります。

* × が四隅に着手を行うと引き分けの局面になる
* × が辺に着手を行うと 〇 の必勝の局面になる

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/cd8dab2c-98fd-aa7c-6f14-d1a3d23bc736.png" width="150">

実際に × が (1, 0) に着手した場合は、下図のように (0, 0)、(2, 2)、(0, 1) の順で着手することで、〇 がその次に (0, 2) と (2, 1) のどちらかに着手すれば勝利するので、× が辺に着手を行うと 〇 の必勝の局面になることが正しいことがわかります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e8bd35ea-d36b-11dc-7aa4-3d81640cadd9.png" width="250">

下図は、別の局面を中心とした部分木です。下図をじっくりと見て、赤枠で囲われたノードとそのノードから辿れる子ノードの評価値が全て正しく計算されていることを確認して下さい。また、下記以外の様々な部分木を表示して確認してみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/338ea563-c477-6934-3889-d5db4f77e754.png" width="450">

### プログラムのバグとその検証

実は、上記の `draw_node` にはバグがあります。具体的には、下記のプログラムのように、__新しくファイルから__ Mbtree クラスのインスタンスを __読み込んだデータを使って__ Mbtree_GUI で __ゲーム木を表示__ しようとすると実行結果のような __エラーが発生__ します。このエラーの原因について少し考えてみて下さい。


```python
mbtree_bf2 = Mbtree.load("bftree")
mbtree_gui = Mbtree_GUI(mbtree_bf2)
```

実行結果

```
略
Cell In[7], line 19
     17 # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
     18 y = dy + (self.height - 3) / 2
---> 19 Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
     20 rect = Rect(dx, y, 3, 3)
     21 # 子ノードが存在する場合に、エッジの線と子ノードを描画する

AttributeError: 'Node' object has no attribute 'score'
```

エラーメッセージから __Node__ クラスのインスタンスに __`score` 属性が存在しない__ ことが原因であることがわかります。Node クラスの __`score` 属性__ は、先程定義した __`calc_score_by_bf` によって計算される__ ので、__`calc_score_by_bf` を定義する前に作成__ した Mbtree クラスのインスタンスを保存したファイルのデータの中の Node には __`score` 属性は存在しません__。

### 組み込み関数 `getattr` を利用した修正

過去に作成した Mbtree クラスのインスタンスを二度と使わないのであれば、このエラーは無視しても構わないでしょう。そうではなく、__`score` 属性が存在しない__ Mbtree クラスのインスタンスに対しても __Mbtree_GUI クラスで表示を行いたい__ 場合は、この __エラーが発生しないよう__ にプログラムを修正する必要があります。

この問題は、[以前の記事](https://qiita.com/ysgeso/items/085fd15fbd91d5cdf770#%E5%A4%89%E6%95%B0%E3%81%AE%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E8%A6%81%E7%B4%A0%E3%81%AE%E5%8F%82%E7%85%A7)や、[以前の記事](https://qiita.com/ysgeso/items/51842efc6193ed456ebc#getattr-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-ai-%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%AE%E5%8F%96%E5%BE%97%E6%96%B9%E6%B3%95)で利用した、組み込み関数 `getattr` を利用することで解決することができます。

`getattr` は、__1 つ目の実引数__ に __オブジェクト__ を、__2 つ目の実引数__ に __属性の名前__ を記述することで、__指定した属性の値__ を __返り値として返す__ 処理を行いますが、その際に、存在しない属性を記述すると下記のプログラムのようにエラーが発生します。

一方、`getattr` に __3 つ目の実引数を記述__ することで、オブジェクトに __存在しない属性を指定した場合__ に、__3 つ目の実引数の値を返す__ 処理を行います。

例えば、上記の __`mbtree_bf2`__ の __ルートノード__ には __`score` 属性は存在しない__ ので、下記のプログラムを実行するとエラーが発生します。

```python
print(getattr(mbtree_bf2.root, "score"))
```

実行結果

```
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[10], line 1
----> 1 print(getattr(mbtree_bf2.root, "score"))

AttributeError: 'Node' object has no attribute 'score'
```

一方、下記のプログラムのように、`getattr` の 3 つ目の実引数に `None` を記述すると、実行結果のように、__`score` 属性が存在する__ `mbtree_bf.root` の場合は __`score` 属性の値__ が、__`score` 属性が存在しない__ `mbtree_bf2.root` の場合は __`None`__ が表示されます。

```python
print(getattr(mbtree_bf.root, "score", None))
print(getattr(mbtree_bf2.root, "score", None))
```

実行結果

```
0
None
```

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

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

### `draw_node` のバグの修正

先程 `draw_node` を __`score` に `None` が代入された場合__ は、__以前と同じ処理を行う__ ように修正したので、下記のプログラムのように `draw_node` を修正することで、先程の問題を解決することができます。

* __5、11 行目__：キーワード引数 `score` の値を、`getattr` を利用してノードに `score` 属性が存在しない場合は `None` が計算されるように修正する

```python
 1  def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
 2      # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
 3      y = dy + (self.height - 3) / 2
 4      Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
 5                               score=getattr(self, "score", None), emphasize=emphasize, lw=lw, dx=dx, dy=y)
 6      rect = Rect(dx, y, 3, 3)
 7      # 子ノードが存在する場合に、エッジの線と子ノードを描画する
 8      if len(self.children) > 0:
元と同じなので省略
 9                  if maxdepth is None:
10                      Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
11                                               score=getattr(childnode, "score", None), dx=dx+5, dy=childnodey, lw=lw)
元と同じなので省略
12
13  Node.draw_node = draw_node
```

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

```python
def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
    width = 8
    if ax is None:
        height = len(self.children) * 4
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")
        for childnode in self.children:
            childnode.height = 4
        self.height = height         
        
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
                             score=getattr(self, "score", None), emphasize=emphasize, lw=lw, dx=dx, dy=y)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
        if maxdepth != self.depth:   
            plt.plot([dx + 3.5, dx + 4], [y + 1.5, y + 1.5], c="k", lw=lw)
            prevy = None
            for childnode in self.children:
                childnodey = dy + (childnode.height - 3) / 2
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
                                             score=getattr(childnode, "score", None), dx=dx+5, dy=childnodey, lw=lw)
                edgey = childnodey + 1.5
                plt.plot([dx + 4 , dx + 4.5], [edgey, edgey], c="k", lw=lw)
                if prevy is not None:
                    plt.plot([dx + 4 , dx + 4], [prevy, edgey], c="k", lw=lw)
                prevy = edgey
                dy += childnode.height
        else:
            plt.plot([dx + 3.5, dx + 4.5], [y + 1.5, y + 1.5], c="k", lw=lw)
            
    return rect

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

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

```diff_python
def draw_node(self, ax=None, maxdepth=None, emphasize=False, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
    # 自分自身のノードを真ん中の位置になるように (dx, dy) からずらして描画する
    y = dy + (self.height - 3) / 2
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
-                            score=self.score, emphasize=emphasize, lw=lw, dx=dx, dy=y)
+                            score=getattr(self, "score", None), emphasize=emphasize, lw=lw, dx=dx, dy=y)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
元と同じなので省略
                if maxdepth is None:
                    Marubatsu_GUI.draw_board(ax, childnode.mb, show_result=True,
-                                            score=childnode.score, dx=dx+5, dy=childnodey, lw=lw)
+                                            score=getattr(childnode, "score", None), dx=dx+5, dy=childnodey, lw=lw)
元と同じなので省略

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

上記の修正後に、下記のプログラムを実行することで、`mbtree_bf2` でもエラーが発生しないようになることが確認できます。また、`mbtree_bf2` では Node に `score` 属性が存在しないので、実行結果のように決着がついていないゲーム盤の背景に色が表示されません。

```python
mbtree_gui = Mbtree_GUI(mbtree_bf2)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/52d0ff13-972d-daf9-562b-aea7aecab05d.png" width="150">

## 深さ優先アルゴリズムによる実装

Mbtree クラスでは、ゲーム木を作成する際に各深さのノードの一覧を `nodelist_by_depth` 属性に記録していたので、幅優先アルゴリズムで各ノードの評価値を簡単に記述できましたが、__一般的__ には __木構造のデータ__ に対して __トップダウンな繰り返し処理__ を行う場合は、__深さ優先アルゴリズムを再帰呼び出し__ で記述するのが __簡単__ です。

そこで、ゲーム木の全てのノードの評価値をミニマックス法で、深さ優先アルゴリズムと再帰呼び出しを使って計算する下記のようなメソッドを定義する事にします。

__名前__：深さ優先アルゴリズムで評価値を計算するので、`calc_score_by_df` とする
__処理__：仮引数に代入されたノードの評価値を計算する
__入力__：仮引数 `node` に評価値を計算するノードを代入する
__出力__：計算したノード `node` の評価値

なお、[前回の記事](https://qiita.com/ysgeso/items/38f2c8167a14eb99d86c#%E5%86%8D%E5%B8%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%81%AB%E3%82%88%E3%82%8B%E5%AE%9F%E8%A3%85-1)ではトップダウンな再帰呼び出しでノードを代入する仮引数の名前を `N` としましたが、後で `calc_score_by_bf` と比較するために __`node`__ という名前にしました。

`calc_score_by_df` は下記のプログラムで実装することができます。

* __2 ~ 7 行目__：node の局面が決着がついている場合は、決着の状態に応じた評価値を `node` の `score` 属性に代入する
* __9 行目__：決着がついていない場合は、list 内包表記を使って __子ノードの評価値__ を要素として持つ __list を作成__ し、`score_list` に代入する。その際に、子ノードの評価値は __再帰呼び出しによって計算を行い__、その __返り値を要素の値とする__
* __10、11 行目__：局面の手数を表す `move_count` 属性の値が偶数の場合は 〇 の手番なので、`score_list` の最大値を計算する
* __12、13 行目__：奇数の場合は × の手番なので、`score_list` の最小値を計算する
* __14 行目__：計算した評価値を `node` の `score` 属性に代入する
* __16 行目__：`node` の評価値を返り値として返す。なお、この処理は、決着がついている場合と、ついていない場合に __共通する処理__ なので、__最後の行でまとめて行うことができる__

```python
 1  def calc_score_by_df(self, node):
 2      if node.mb.status == Marubatsu.CIRCLE:
 3          node.score = 1
 4      elif node.mb.status == Marubatsu.DRAW:
 5          node.score = 0
 6      elif node.mb.status == Marubatsu.CROSS:
 7          node.score = -1
 8      else:
 9          score_list = [self.calc_score_by_df(childnode) for childnode in node.children]
10          if node.mb.move_count % 2 == 0:
11              score = max(score_list)
12          else:
13              score = min(score_list)
14          node.score = score
15
16      return node.score
17
18  Mbtree.calc_score_by_df = calc_score_by_df  
```

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

```python
def calc_score_by_df(self, node):
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = -1
    else:
        score_list = [self.calc_score_by_df(childnode) for childnode in node.children]
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score

    return node.score

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

上記のプログラムを、先程定義した下記の `calc_score_by_bf` と比較してみて下さい。`nodelist_by_depth` が計算済であれば、プログラムの見た目にそれほど大きな違いはないことがわかると思います。ただし、__プログラムは似ていても、処理の流れは全く異なります__。

```python
def calc_score_by_bf(self):
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
                score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score
```

<details><summary><strong><code>calc_score_by_df</code> との違い（ただし、インデントの違いは無視しました）</strong></summary>

```diff_python
-def calc_score_by_df(self, node):
+def calc_score_by_bf(self):
+   for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
-               score_list = [self.calc_score_by_df(childnode) for childnode in node.children]
+               score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score

-    return node.score                
```
</details>


実行結果は同じなので省略しますが、上記の修正後に、下記のプログラムを実行すると、`calc_score_by_df` で評価値を計算した `mbtree_by_df` を Mbtree_GUI で正しく表示できることが確認できます。実際に様々な操作を行って、正しく表示できることを確認して下さい。

```python
mbtree_by_df = Mbtree.load("dftree")
mbtree_by_df.calc_score_by_df(mbtree_by_df.root)
mbtree_gui = Mbtree_GUI(mbtree_by_df)
```

:::note
上記の 1 行目では、`calc_score_by_df` のアルゴリズムに合わせて、深さ優先アルゴリズムで作成したデータをファイルから読み込んでいますが、幅優先アルゴリズムで作成したデータを読み込んでも結果は変わりません。
:::

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

評価値を計算できるようになったので、下記のプログラムのように Mbtree クラスの `__init__` 属性を修正して、Mbtree クラスのインスタンスを作成した際に、評価値も計算するようにします。その際に、せっかくなので、ゲーム木の作成と同じアルゴリズムで評価値を計算することにしましたが、どちらのアルゴリズムで評価値を計算してもかまいません。

* __7、14 行目__：ゲーム木の作成後に評価値を計算する関数を呼び出す

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

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

```python
def __init__(self, algo:str="bf"):   
    self.algo = algo
    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.calc_score_by_df(self.root)
        
Mbtree.__init__ = __init__
```
</details>

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

```diff_python
def __init__(self, algo:str="bf"):   
    self.algo = algo
    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.calc_score_by_df(self.root)
        
Mbtree.__init__ = __init__
```
</details>

実行結果は同じなので省略しますが、上記の修正後に下記のプログラムを実行することで、修正したプログラムが正しく動作することが確認できます。

```python
mbtree_by_bf3 = Mbtree()
mbtree_gui = Mbtree_GUI(mbtree_by_bf3)
mbtree_by_df2 = Mbtree(algo="df")
mbtree_gui = Mbtree_GUI(mbtree_by_df2)
```

## データの保存

評価値入りのゲーム木を作成したので、下記のプログラムでファイルに保存します。その際に、ファイル名を `"bfscore"` と `"dfscore"` としました。

```python
mbtree_by_bf3.save("bfscore")
mbtree_by_df2.save("dfscore")
```

実行結果

```
save completed.
save completed.
```

# 今回の記事のまとめ

今回の記事では、ゲーム木の評価値を計算する方法として、ミニマックス法を紹介し、ミニマックス法でゲーム木の評価値を計算するメソッドを、幅優先アルゴリズムと深さ優先アルゴリズムの両方で実装しました。次回の記事では、評価値を計算したゲーム木を使って、最強の AI を作成する方法を紹介する予定です。

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

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

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

# 次回の記事

https://qiita.com/ysgeso/items/94c5105c3dbebb445710

[^1]:ただし、深さ 0 のルートノードは親ノードを持たないので、d は 0 を除きます