Pythonで〇×ゲームのAIを一から作成する　その118　最善手の優劣を考慮したゲーム木を利用する AI

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/6d1430a88e251279d77a

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

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

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

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

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

# 今回の記事のテーマ

[以前の記事](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#%E5%BF%85%E5%8B%9D%E3%81%AE%E5%B1%80%E9%9D%A2%E3%81%A7%E3%81%AE%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%84%AA%E5%8A%A3)でルールベースの AI を作成する際に、__人間と対戦を行うという視点で考える__ と、__最善手には優劣が存在する__ という説明をしました。今回の記事では、ゲーム木を利用した AI の場合に __最善手の優劣を考慮する方法__ について紹介します。

# 必勝の局面の最善手の優劣

[以前の記事](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#%E5%BF%85%E5%8B%9D%E3%81%AE%E5%B1%80%E9%9D%A2%E3%81%A7%E3%81%AE%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%84%AA%E5%8A%A3)で、__必勝の局面__ での __最善手__ には、__感情を持つ人間__ にとって __好ましいと思えるかどうか__ という点で __違いが生じる場合がある__ という説明を行いました。忘れてしまった方が多いと思いますので具体例を挙げて説明します。

なお、__感情を持たない弱解決または強解決の AI どうしの対戦__ の場合は、どの最善手を選択しても __試合の結果は変わらない__ ので、必勝の局面に限らず、__あらゆる局面__ で __最善手に優劣は存在しません__。

ゲーム木を利用した __`ai_gt6`__ は強解決の AI ですが、現状の `ai_gt6` は、__次の着手で勝利できる場合__ に、__すぐに勝利しない着手を行う場合があります__。そのことは下記の手順で確認することができます。

```python
from util import gui_play

gui_play()
```

1. 上記のプログラムで `gui_play()` を実行する
2. (1, 1)、(1, 0)、(0, 0) の順で着手を行う（下図）
3. 〇 の担当を `ai_gt6` に変更し、「変更」ボタンをクリックする
4. (2, 0) に着手を行う 

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2e2184a8-983e-a66f-b8cb-896c4a0546cb.png" width="200">

上記の操作を行うと、下図のように、〇を担当する __`ai_gt6`__ が __(2, 2) に着手を行って勝利できる__ 局面であるにも関わらず、__それ以外の着手を行う場合があります__。なお、`ai_gt6` が (2, 2) に着手を行って勝利する場合もあるので、その場合は「待った」ボタンをクリックして `ai_gt6` が勝利する着手を行わなくなるまで (2, 0) に着手し直してください。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9504842c-21e5-344f-3f15-092ef25acfeb.png" width="200">

下図は、上記で「<」ボタンをクリックして表示される __1 手前の局面__ の GUI の部分木を含んだ画面です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0c72b704-dc99-f37b-f7b6-07c7c527ad58.png" width="300">

上図の GUI の部分木から、1 手前の `ai_gt6` の手番の局面では、(2, 2) に着手を行えばすぐに 〇 の勝利になりますが、__(0, 1)、(2, 1)、(0, 2)__ の __いずれかに着手を行った場合__ でも水色で表示される __〇 の必勝の局面になり__、その後でお互いが最善手を着手し続けると 〇 が勝利することがわかるので、__それらも最善手である__ ことが確認できます。

このような、すぐに勝利できる合法手が存在するにも関わらず、AI が別の合法手を着手するという現象は、__ルールベースの AI を作成する際にも発生__ し、そのことについては [以前の記事](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#%E5%BF%85%E5%8B%9D%E3%81%AE%E5%B1%80%E9%9D%A2%E3%81%A7%E3%81%AE%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%84%AA%E5%8A%A3) で説明しました。

勝敗の結果が変わらないという意味では、すぐに勝利しない着手を AI が選択しても強解決の AI であることには変わりませんが、人間がその AI と対戦する場合は、そのような __無駄に試合を長引かせるような着手__ は __気分が良いものではありません__ ので、__すぐに勝利することができる最善手__ のほうが、__人間相手に対戦を行う場合は優れている__ と考えることができます。そこで、__必勝の局面__ では、__できるだけ早く勝利する着手を行う__ ような AI を作成することにします。そのような AI を作成する方法について少し考えてみて下さい。

## 評価値の計算方法の変更

ルールベースの AI の場合は、__着手すると勝利する合法手の評価値__ を、__最も高い評価値に設定する__ ことで最善手に優劣をつけることができました。

ゲーム木を利用した AI では、[以前の記事](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81)で説明した、下記の __ミニマックス法__ というアルゴリズムでゲーム木の各 __ノードの評価値を計算__ します。

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

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

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

ミニマックス法では、上記のように __決着がついている局面の評価値を元に__ 各ノードの __評価値の計算が行われる__ ので、__決着がついている局面の評価値__ を、決着がついた手数を表す __ノードの深さで変える__ ことで AI が __なるべく早く勝利する__ ような合法手を __優先的に選択する__ ようになります。どのように評価値を変えればよいかについて少し考えてみて下さい。

### 〇 の必勝の局面の評価値

必勝の局面には、〇 の必勝の局面と × の必勝の局面の 2 種類があるので、それぞれについて評価値を考えることにします。

ゲーム木を利用した AI は、__〇 の手番__ の局面では、__最も評価値が高い子ノード__ になる __合法手を選択__ します。そのため、これまでは __〇 が勝利__ する局面の __評価値を常に `1`__ と計算しましたが、__〇 の必勝の局面__ で __なるべく早く 〇 が勝利する着手を選択する__ ためには、〇 が勝利する局面の __深さが浅いほど大きな評価値を計算する__ 必要があります。

また、現状では __引き分けの局面__ の評価値を __0__、__× の必勝の局面__ の評価値を __-1__ と計算しているので、__〇 の必勝の局面__ の評価値はそれらより大きな __正の値に設定する必要__ があります。

〇×ゲームは、最低でも 3 回着手を行わなければ勝利できないゲームなので、__〇が勝利する局面__ は、__深さが 5、7、9 のいずれかの局面__ になります。この 3 つの深さに対して、上記の条件を満たす評価値を割り当てる方法は無数にありますが、下記の表のように、__深い順__ に __1、2、3__ という __評価値を割り当てる__ のが最も __自然な割り当て方__ ではないかと思います。

| 局面の深さ | 5 | 7 | 9 |
|:-:|:-:|:-:|:-:|
| __〇が勝利した場合の評価値__  | 3  | 2  | 1  |

次に、__局面の深さから__ 上記の表の __評価値を計算する式を考える__ 必要があります。どのような式で計算できるかについて少し考えてみて下さい。

:::note
上記の条件を満たしていれば、他の割り当て方でもかまわないので、他の評価値を割り当てたい人はそのようにして下さい。
:::

その式は、「（11 - 局面の深さ）÷ 2」という式で計算できます。

### × の必勝の局面の評価値

ゲーム木を利用した AI は、__× の手番__ の局面では、__最も評価値が低い子ノード__ になる __合法手を選択__ します。そのため __× の必勝の局面__ で __なるべく早く × が勝利する着手を選択する__ ためには、× が勝利する局面の __深さが浅いほど大きな評価値を計算する__ 必要があります。

また、先程と同様の理由でその評価値は __負の値にする必要__ があります。

× が勝利する局面は __深さが 6、8__ のいずれかの局面なので、それらの評価値を下記の表のように割り当てることにします。

| 局面の深さ | 6 | 8 | 
|:-:|:-:|:-:|
| __× が勝利した場合の評価値__  | -2  | -1  |

また、上記の評価値を計算する式は「（局面の深さ - 10）÷ 2」となります。

### 評価値のまとめ

下記の表は上記をまとめたものです。なお、引き分けの局面はこれまでと同様に `0` を評価値とします。

| 局面の深さ | 5 | 6 | 7 | 8 | 9 | 評価値の計算式 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| __〇 が勝利した場合の評価値__  | 3  | |  2 | | 1  |（11 - 局面の深さ）÷ 2|
| __× が勝利した場合の評価値__  |   |-2 |   |-1 |   |（局面の深さ - 10）÷ 2|

## Mbtree クラスの修正

ゲーム木の __評価値の計算__ は、Mbtree クラスの __`calc_score_by_bf`__ と __`calc_score_by_df`__ メソッドで行っているので、それらのメソッドで上記の評価値を計算するように修正する必要があります。ただし、__これまでと同様の評価値を計算できる__ ように、`__init__` メソッドに `True` が代入されている場合に最短（shortest）の勝利（victory）を優先した評価値を計算することを表す __`shortest_victory`__ という __仮引数を追加__ することにします。

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

まず、`__init__` メソッドを下記のプログラムのように修正します。

* __4 行目__：デフォルト値を `False` とする仮引数 `shortest_victory` を追加する
* __6 行目__：`shortest_victory` を同名の属性に代入する

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

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

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

def __init__(self, algo="bf", shortest_victory=False):
    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
from marubatsu import Marubatsu

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

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

次に、__`calc_score_by_bf`__ と __`calc_score_by_df`__ メソッドの __両方__ で、__`shortest_victory` が `True` の場合の評価値を計算する処理を記述する__ 必要がありますが、その処理は __両方のメソッドで全く同じ__ です。そこで、ゲームの __決着がついたノードの評価値を計算する__ 下記のメソッドを定義する事にします。

__名前__：ノードの評価値を計算するので `calc_score_of_node` とする
__処理__：決着がついたノードの評価値を計算し、`score` 属性に代入する
__入力__：評価値を計算するノードを仮引数 `node` に代入する
__出力__：なし

下記のプログラムは、`calc_score_of_node` の定義です。なお、このメソッドは決着がついていないノードに対しては何も処理を行いません。

* __1 行目__：評価値を計算するノードを代入する仮引数 `node` を持つ `calc_score_of_node` メソッドを定義する
* __2、3 行目__：〇が勝利した局面の場合の `node` の `score` 属性を、`shortest_victory` 属性の値に応じて計算する
* __4、5 行目__：引き分けの場合は `node` の `score` 属性に `0` を代入する
* __6、7 行目__：×が勝利した局面の場合の `node` の `score` 属性を、`shortest_victory` 属性の値に応じて計算する

```python
1  def calc_score_of_node(self, node):
2      if node.mb.status == Marubatsu.CIRCLE:
3          node.score = (11 - node.depth) / 2 if self.shortest_victory else 1
4      elif node.mb.status == Marubatsu.DRAW:
5          node.score = 0
6      elif node.mb.status == Marubatsu.CROSS:
7          node.score = (node.depth - 10) / 2 if self.shortest_victory else -1
8        
9  Mbtree.calc_score_of_node = calc_score_of_node     
```

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

```python
def calc_score_of_node(self, node):
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = (11 - node.depth) / 2 if self.shortest_victory else 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = (node.depth - 10) / 2 if self.shortest_victory else -1
        
Mbtree.calc_score_of_node = calc_score_of_node 
```
</details>

### `calc_score_by_bf` と `calc_score_by_df` の修正

まず、`calc_score_by_df` を下記のプログラムのように修正します。

* __5、6 行目__：ゲームの決着がついている場合に、先程定義した `calc_score_of_node` メソッドを呼び出して `node` の評価値を計算するように修正する

```python
 1  def calc_score_by_bf(self):
 2      self.nodelist_by_score = self.nodelist[:]
 3      for nodelist in reversed(self.nodelist_by_depth):
 4          for node in nodelist:
 5              if node.mb.status != Marubatsu.PLAYING:
 6                  self.calc_score_of_node(node)
 7              else:
 8                  score_list = [childnode.score for childnode in node.children]
元と同じなので省略
 9
10  Mbtree.calc_score_by_bf = calc_score_by_bf
```

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

```python
def calc_score_by_bf(self):
    self.nodelist_by_score = self.nodelist[:]
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status != Marubatsu.PLAYING:
                self.calc_score_of_node(node)
            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
            self.nodelist_by_score.append(node)
            node.score_index = len(self.nodelist_by_score) - 1  

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

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

```diff_python
def calc_score_by_bf(self):
    self.nodelist_by_score = self.nodelist[:]
    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
+           if node.mb.status != Marubatsu.PLAYING:
+               self.calc_score_of_node(node)
            else:
                score_list = [childnode.score for childnode in node.children]
元と同じなので省略

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

次に、`calc_score_by_df` を下記のプログラムのように修正します。修正内容は `calc_score_by_bf` の場合とほぼ同じです。

* __3、4 行目__：ゲームの決着がついている場合に、先程定義した `calc_score_of_node` メソッドを呼び出して `node` の評価値を計算するように修正する

```python
1  def calc_score_by_df(self, node):
2      self.nodelist_by_score.append(node)
3      if node.mb.status != Marubatsu.PLAYING:
4          self.calc_score_of_node(node)
5      else:
6          score_list = []
元と同じなので省略
7
8  Mbtree.calc_score_by_df = calc_score_by_df
```

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

```python
def calc_score_by_df(self, node):
    self.nodelist_by_score.append(node)
    if node.mb.status != Marubatsu.PLAYING:
        self.calc_score_of_node(node)
    else:
        score_list = []
        for childnode in node.children:
            score_list.append(self.calc_score_by_df(childnode))
            self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score
        
    self.nodelist_by_score.append(node)
    node.score_index = len(self.nodelist_by_score) - 1        
    return node.score      

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

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

```diff_python
def calc_score_by_df(self, node):
    self.nodelist_by_score.append(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
+   if node.mb.status != Marubatsu.PLAYING:
+       self.calc_score_of_node(node)
    else:
        score_list = []
元と同じなので省略

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

## ゲーム木の作成と確認

次に、下記のプログラムで 実引数に `shortest_victory=True` を記述して 〇×ゲームのゲーム木を __幅優先アルゴリズム__ で作成します。

```python
bftree_shortest_victory = Mbtree(shortest_victory=True)
```

実行結果

```
     9 depth 1 node created
    72 depth 2 node created
   504 depth 3 node created
  3024 depth 4 node created
 15120 depth 5 node created
 54720 depth 6 node created
148176 depth 7 node created
200448 depth 8 node created
127872 depth 9 node created
     0 depth 10 node created
total node num = 549946
```

また、下記のプログラムで 〇×ゲームのゲーム木を __深さ優先アルゴリズム__ で作成します。

```python
dftree_shortest_victory = Mbtree(algo="df", shortest_victory=True)
```
作成した __ゲーム木が正しく作成されているかを確認__ するために下記のプログラムで __Mbtree_GUI クラスを使ってゲーム木の部分木を GUI で表示__ すると、実行結果のように、一見すると正しい部分木が表示されるように見えますが、__実際には問題__ があります。どのような問題があるかについて様々なノードをクリックして探してみて下さい。

なお、今回の記事では以降は幅優先アルゴリズムで作成した `bftree_shortest_victory` に対してのみ確認を行います。深さ優先アルゴリズムで作成した `dftree_shortest_victory` に対しても同様の方法で確認を行うことができるので後で確認して下さい。

また、どちらのゲーム木も __ノードの評価値は同じになる__ ので、後で作成する最善手の優劣を考慮した AI では、`bftree_shortest_victory` のほうを利用することにします。


```python
from tree import Mbtree_GUI

Mbtree_GUI(bftree_shortest_victory)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4c549d7a-8134-fd8b-f635-94b000dd88e4.png" width="350">

例えば (1, 1) のみに 〇 が配置された局面のノードをクリックすると、下図のような部分木が表示されます。下図の部分木の中で、[背景が灰色で評されている部分の局面](https://qiita.com/ysgeso/items/6d1430a88e251279d77a#%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E3%81%BF%E3%82%92%E7%9D%80%E6%89%8B%E3%81%97%E3%81%9F%E5%A0%B4%E5%90%88%E3%81%AE%E9%83%A8%E5%88%86%E6%9C%A8%E3%81%AE%E8%A1%A8%E7%A4%BA)は、__最善手を着手し続けた場合の局面__ なので、背景が灰色の部分で __左右につながっている一連の局面__ は __すべて同じ評価値になるはず__ です。それにも関わらず下図では、背景が灰色の部分の中で __一番右のノードだけが水色になる局面がある__ 点が変です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2f8f9dbc-0287-1893-77b2-4eeb960a26c2.png" width="350">

また、下記のプログラムでこれまでに作成したゲーム木をファイルから読み込み、同じ局面を選択すると、実行結果の左図のように __背景が灰色の部分の左右につながっている一連の局面の色がすべて同である__ 正しい部分木が表示されます。上図を下の実行結果の右に並べて表示しましたので比較して下さい。

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

実行結果（左が実行結果です。右は上図の再掲です）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1963b157-b463-e065-831d-4a3946414242.png" width="340">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2f8f9dbc-0287-1893-77b2-4eeb960a26c2.png" width="320">

`bftree_shortest_victory` を Mbtree_GUI で表示すると、上記の左図のように間違った色で局面が表示される理由について少し考えてみて下さい。

## 評価値の表示

間違った色で表示される原因として、__ゲーム木の評価値が正しく計算されていない可能性__ が考えられます。これまでは、評価値が -1、0、1 の 3 種類しかなかったので、__ゲーム盤の色で評価値を簡単に区別する__ ことができましたが、先程の修正で __評価値__ が -2 ~ 3 の __6 種類に増えた__ のでゲーム盤の __色で評価値を区別することが困難__ になりました。そこで、__ゲーム盤の上に評価値を直接表示する__ ことで、評価値が正しく計算されているかどうかを __確認できるようにする__ ことにします。

部分木のノードは Node クラスの __`draw_node`__ メソッドで描画するので、下記のプログラムのように、その中でゲーム盤を表示する際に __上部に評価値を表示する__ ように修正します。

* __8、9 行目__：9 行目でゲーム盤の上部にノードの評価値を表示する。なお、__評価値が計算されていないノード__ には __`score` 属性が存在しない__ ので、組み込み関数 [__`hasattr`__](https://qiita.com/ysgeso/items/b5e388878fef195d8f2c#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-hasattr-%E3%81%AB%E3%82%88%E3%82%8B%E5%B1%9E%E6%80%A7%E3%81%AE%E5%AD%98%E5%9C%A8%E5%88%A4%E5%AE%9A) を使って __`score` 属性が存在する場合のみ評価値を表示する__ ようにした。また、表示位置やフォントサイズは試行錯誤によって決めた値である

```python
 1  import matplotlib.pyplot as plt
 2  from marubatsu import Marubatsu_GUI
 3  from tree import Node, Rect
 4
 5  def draw_node(self, ax=None, maxdepth=None, emphasize=False, darkness=0, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
 6      Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
 7                               score=getattr(self, "score", None), bc=bc, darkness=darkness, lw=lw, dx=dx, dy=y)
 8      if hasattr(self, "score"):
 9          ax.text(dx, y - 0.1, self.score, fontsize=10)       
元と同じなので省略
10
11  Node.draw_node = draw_node
```

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

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

def draw_node(self, ax=None, maxdepth=None, emphasize=False, darkness=0, 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
    bc = "red" if emphasize else None
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
                            score=getattr(self, "score", None), bc=bc, darkness=darkness, lw=lw, dx=dx, dy=y)
    if hasattr(self, "score"):
        ax.text(dx, y - 0.1, self.score, fontsize=10)
    rect = Rect(dx, y, 3, 3)
    # 子ノードが存在する場合に、エッジの線と子ノードを描画する
    if len(self.children) > 0:
        if maxdepth != self.depth:   
            ax.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
                ax.plot([dx + 4 , dx + 4.5], [edgey, edgey], c="k", lw=lw)
                if prevy is not None:
                    ax.plot([dx + 4 , dx + 4], [prevy, edgey], c="k", lw=lw)
                prevy = edgey
                dy += childnode.height
        else:
            ax.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
from marubatsu import Marubatsu_GUI

def draw_node(self, ax=None, maxdepth=None, emphasize=False, darkness=0, size=0.25, lw=0.8, dx=0, dy=0):
元と同じなので省略
    Marubatsu_GUI.draw_board(ax, self.mb, show_result=True, 
                            score=getattr(self, "score", None), bc=bc, darkness=darkness, lw=lw, dx=dx, dy=y)
+   if hasattr(self, "score"):
+       ax.text(dx, y - 0.1, self.score, fontsize=10)       
元と同じなので省略

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

上記の修正後に、下記のプログラムを実行すると、実行結果のようにゲーム盤の上部に評価値が表示されるようになります。

```python
Mbtree_GUI(bftree_shortest_victory)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0f2931fd-96bd-56eb-d189-da4920d1012c.png" width="350">

## 上部の評価値の表示の一部が表示されない問題の修正

上記の実行結果から、__一番上の評価値の一部が表示されない__ という問題があることがわかります。これは、評価値の文字の上部が、部分木を表示する __Figure の上端からはみ出てしまったことが原因__ です。この問題を解決する方法を少し考えてみて下さい。

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

この問題を解決する方法の一つに、Figure に表示する内容を __すべて少しだけ下にずらす__ という方法がありますが、その方法は __プログラムの修正がかなり大変です__。

別の方法として、__Axes の y 座標の表示範囲を少しだけ上部に広げる__ という方法があります。試行錯誤した結果、__表示範囲を 1 だけ上に広げる__ ことで __評価値の表示がはみでなくなる__ ことがわかったので、そのように表示範囲を広げることにします。

Axes の __y 座標__ の __表示範囲を上に 1 つ広げる__ ということは、__表示範囲の高さが 1 増える__ ということなので、下記のプログラムのように Mbtree_GUI クラスの __`__init__`__ メソッドを修正して Figure の高さを表す __`height` 属性の値を 1 増やす__ 必要があります。

* __5 行目__：`height` 属性の値を 64 から 65 に修正する
* __7 行目__：`__init__` メソッドを、クラスの定義の外で修正できるようにするために、`super` の記述を修正する。忘れた方は[以前の記事](https://qiita.com/ysgeso/items/903dc60e865ff56191fc#super-%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E8%AA%AC%E6%98%8E)を復習する事

```python
1  def __init__(self, mbtree, size=0.15):
2      self.mbtree = mbtree
3      self.size = size
4      self.width = 50
5      self.height = 65
6      self.selectednode = self.mbtree.root
7      super(Mbtree_GUI, self).__init__()
8
9  Mbtree_GUI.__init__ = __init__ 
```

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

```python
def __init__(self, mbtree, size=0.15):
    self.mbtree = mbtree
    self.size = size
    self.width = 50
    self.height = 65
    self.selectednode = self.mbtree.root
    super(Mbtree_GUI, self).__init__()

Mbtree_GUI.__init__ = __init__ 
```
</details>

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

```diff_python
def __init__(self, mbtree, size=0.15):
    self.mbtree = mbtree
    self.size = size
    self.width = 50
-   self.height = 64
+   self.height = 65
    self.selectednode = self.mbtree.root
-   super().__init__()
+   super(Mbtree_GUI, self).__init__()

Mbtree_GUI.__init__ = __init__ 
```
</details>

### `update_gui` の修正

次に、__Axes の表示範囲を設定する処理__ を行う __`update_gui`__ を下記のプログラムのように修正します。なお、同様の処理は[以前の記事](https://qiita.com/ysgeso/items/17b0438676f4a41a906c#%E6%B7%B1%E3%81%95%E3%81%8C-0-%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%8C%E4%B8%AD%E5%BF%83%E3%81%A8%E3%81%AA%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AE%E8%A1%A8%E7%A4%BA%E3%81%AE%E5%95%8F%E9%A1%8C%E3%81%AE%E4%BF%AE%E6%AD%A3)で深さが 0 のゲーム盤の枠線が Figure の外にはみ出て表示されるという問題を修正するために、3 行目で x 座標に対しても行っています。

* __4 行目__：Axes の y 座標の表示範囲の最小値と最大値を 1 減らして表示範囲を上にずらす

```python
1  def update_gui(self):
2      self.ax.clear()
3      self.ax.set_xlim(-1, self.width - 1)
4      self.ax.set_ylim(-1, self.height - 1)   
元と同じなので省略
5    
6  Mbtree_GUI.update_gui = update_gui
```

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

```python
def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(-1, self.height - 1)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    if self.selectednode.depth <= 4:
        maxdepth = self.selectednode.depth + 1
    elif self.selectednode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    centernode = self.selectednode
    while centernode.depth > 6:
        centernode = centernode.parent
    self.mbtree.draw_subtree(centernode=centernode, selectednode=self.selectednode,
                            show_bestmove=True, ax=self.ax, maxdepth=maxdepth)
    
    disabled = self.selectednode.parent is None
    self.set_button_status(self.left_button, disabled=disabled)
    disabled = self.selectednode.depth >= 6 or len(self.selectednode.children) == 0
    self.set_button_status(self.right_button, disabled=disabled)
    disabled = self.selectednode.parent is None or self.selectednode.parent.children.index(self.selectednode) == 0
    self.set_button_status(self.up_button, disabled=disabled)
    disabled = self.selectednode.parent is None or self.selectednode.parent.children[-1] is self.selectednode
    self.set_button_status(self.down_button, disabled=disabled)
    
Mbtree_GUI.update_gui = update_gui
```
</details>

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

```diff_python
def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
-   self.ax.set_ylim(0, self.height)   
+   self.ax.set_ylim(-1, self.height - 1)   
元と同じなので省略
    
Mbtree_GUI.update_gui = update_gui
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように評価値がはみ出なくなりますが、灰色の背景の部分が上部に広がらないという問題が生じます。

```python
Mbtree_GUI(bftree_shortest_victory)
```

実行結果（上部のみを表示しています）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dbb2011f-e3fb-00c2-525c-1925363ee25d.png" width="500">

### Mbtree クラスの `draw_subtree` の修正

__背景を灰色で表示する処理__ は、__Mbtree__ クラスの __`draw_subtree`__ メソッド内で行っているので、その処理を下記のプログラムのように修正します。

* __7、8 行目__：灰色の長方形の表示位置の y 座標を -1 に修正し、表示する高さが増えたので高さを `height + 1` に修正する[^1]

```python
 1 import matplotlib.patches as patches
 2
 3  def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None, isscore=False, show_bestmove=False, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
 4      if show_bestmove:
 5          bestx = 5 * maxdepth + 4
 6          bestwidth = 50 - bestx
 7          ax.add_artist(patches.Rectangle(xy=(bestx, -1), width=bestwidth,
 8                                          height=height + 1, fc="lightgray"))
元と同じなので省略
 9                
10  Mbtree.draw_subtree = draw_subtree
```

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

```python
def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None, isscore=False, show_bestmove=False, size=0.25, lw=0.8, maxdepth=2):
    def calc_darkness(node):
        """ノードを表示する暗さを計算して返す."""
        
        if show_bestmove:
            if node.parent is None:
                return 0
            elif node.mb.last_move in node.parent.bestmoves:
                return 0
            else:
                return 0.2
            
        if anim_frame is None:
            return 0
        index = node.score_index if isscore else node.id
        return 0.5 if index > anim_frame else 0
    
    self.nodes_by_rect = {}

    if centernode is None:
        centernode = self.root
    self.calc_node_height(N=centernode, maxdepth=maxdepth)
    width = 5 * (maxdepth + 1)
    height = centernode.height
    parent = centernode.parent
    if parent is not None:
        height += (len(parent.children) - 1) * 4
        parent.height = height
    if ax is None:
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")        
    
    if show_bestmove:
        bestx = 5 * maxdepth + 4
        bestwidth = 50 - bestx
        ax.add_artist(patches.Rectangle(xy=(bestx, -1), width=bestwidth,
                                        height=height + 1, fc="lightgray"))
    
    nodelist = [centernode]
    depth = centernode.depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        if parent is not None:
            dy = parent.children.index(centernode) * 4
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
                childnodelist.append(None)
            else:
                dx = 5 * node.depth
                emphasize = node is selectednode
                darkness = calc_darkness(node)
                rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, darkness=darkness, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = node
                if show_bestmove and depth == maxdepth:
                    bestnode = node
                    while len(bestnode.bestmoves) > 0:
                        bestmove = bestnode.bestmoves[0]
                        bestnode = bestnode.children_by_move[bestmove]
                        dx = 5 * bestnode.depth
                        bestnode.height = 4
                        rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth, emphasize=emphasize, size=size, lw=lw, dx=dx, dy=dy)
                        self.nodes_by_rect[rect] = bestnode                                          
                    
                dy += node.height
                if len(node.children) > 0:  
                    childnodelist += node.children
                else:
                    childnodelist.append(None)
        depth += 1
        nodelist = childnodelist
        
    if parent is not None:
        dy = 0
        for sibling in parent.children:
            if sibling is not centernode:
                sibling.height = 4
                dx = 5 * sibling.depth
                darkness = calc_darkness(sibling)
                rect = sibling.draw_node(ax, maxdepth=sibling.depth, size=size, darkness=darkness, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = sibling
            dy += sibling.height
        dx = 5 * parent.depth
        darkness = calc_darkness(parent)
        rect = parent.draw_node(ax, maxdepth=maxdepth, darkness=darkness, size=size, lw=lw, dx=dx, dy=0)
        self.nodes_by_rect[rect] = parent
    
        node = parent
        while node.parent is not None:
            node = node.parent
            node.height = height
            dx = 5 * node.depth
            darkness = calc_darkness(node)
            rect = node.draw_node(ax, maxdepth=node.depth, darkness=darkness, size=size, lw=lw, dx=dx, dy=0)
            self.nodes_by_rect[rect] = node
                
Mbtree.draw_subtree = draw_subtree
```
</details>

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

```diff_python
import matplotlib.patches as patches
 
def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None, isscore=False, show_bestmove=False, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
    if show_bestmove:
        bestx = 5 * maxdepth + 4
        bestwidth = 50 - bestx
-       ax.add_artist(patches.Rectangle(xy=(bestx, -1), width=bestwidth,
+       ax.add_artist(patches.Rectangle(xy=(bestx, 0), width=bestwidth,
-                                       height=height, fc="lightgray"))
+                                       height=height + 1, fc="lightgray"))
元と同じなので省略
                
Mbtree.draw_subtree = draw_subtree
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように灰色の背景の部分が正しく表示されるようになります。

```python
Mbtree_GUI(bftree_shortest_victory)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9fa94e11-050c-b5ab-02f3-0e9857d9db2b.png" width="500">

## 評価値の確認

上記の修正後に、(1, 1) のみに着手が行われたノードをクリックすると下図のような表示が行われます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e22ecd36-b100-3c61-9341-8b22d06c8896.png" width="500">

図で水色で表示される局面は、__7 手目で〇が勝利する局面__ なので __評価値は 2 になるはず__ です。実際に上図では水色で表示される局面の上部には 2.0 が表示されるので __評価値が正しく計算されていることが確認できます__。また、背景が灰色の部分の __水色の親ノードの評価値も 2.0 と表示される__ ので、__他のノードの評価値の計算結果も正しい__ ことが確認できました。

このことから、一部の __ノードの色が間違って表示される原因__ は、__評価値の計算以外__ である __可能性が高い__ ことがわかります。

## 評価値に局面の背景色を表示する処理の確認

__次に間違っている可能性が高い__ のは、__評価値に合わせて背景色を表示する処理__ なので、その処理を調べることにします。背景色を表示するのは下記の __Marubatsu_GUI__ クラスの __`draw_board`__ メソッドのプログラムの 4 ~ 11 行目の部分です。

```python
 1  @staticmethod
def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2): 
 2      # 結果によってゲーム盤の背景色を変更する
 3      if show_result:
 4          if score is None and mb.status == Marubatsu.PLAYING:
 5              bgcolor = "white"
 6          elif score == 1 or mb.status == Marubatsu.CIRCLE:
 7              bgcolor = "lightcyan"
 8          elif score == -1 or mb.status == Marubatsu.CROSS:
 9              bgcolor = "lavenderblush"
10          else:
11              bgcolor = "lightyellow"
12          rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
13                                  height=mb.BOARD_SIZE, fc=bgcolor)
14          ax.add_patch(rect)
略
```

上記のプログラムから、先程の図で間違った色で表示されている、__ゲーム中__ で __評価値が 2 の局面__ の __背景色がどのように表示されるか__ を以下のように検証します。

* ゲーム中の場合は `mb.status` の値が `Marubatsu.PLAYING` である
* 評価値が 2 の場合は `score` の値が `2` である
* 従って、4、6、8 行目の条件式はいずれも `False` になるので、11 行目が実行され、背景色が黄色（lightyellow）になる

上記からゲーム中で評価値が 2 の局面が __間違った黄色で表示される__ ことが確認できました。

このようなことが起きる原因は、__評価値の範囲__ を -1, 0, 1 から -2 ~ 3 の範囲の整数に __変更したにも関わらず__、__背景色の表示を行うプログラムの処理を変更していない__ ためです。どのようにプログラムを修正すれば良いかについて少し考えてみて下さい。

__評価値が正の場合__ は __〇 の必勝の局面__、__負の場合__ は __× の必勝の局面__、__それ以外 の 0 の場合__ は __引き分けの局面__ と判定するようにすることで、それぞれの状況の局面の背景色を正しく表示することができるようになります。下記はそのように `draw_board` メソッドを修正したプログラムです。

* __7 行目__：評価値が正の場合に背景色を水色にするように修正する
* __9 行目__：評価値が負の場合に背景色を赤色にするように修正する

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

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

```python
@staticmethod
def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2): 
    # 結果によってゲーム盤の背景色を変更する
    if show_result:
        if score is None and mb.status == Marubatsu.PLAYING:
            bgcolor = "white"
        elif score > 0 or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
        elif score < 0 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)

    # ゲーム盤の枠を描画する
    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)

    # darkness 0 より大きい場合は、半透明の黒い正方形を描画して暗くする
    if darkness > 0:
        ax.add_artist(patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                        height=mb.BOARD_SIZE, fc="black", alpha=darkness))

    # bc が None でない場合はその色で bw の太さで外枠を描画する
    if bc is not None:
        frame = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
                                height=mb.BOARD_SIZE, ec=bc, fill=False, lw=bw)
        ax.add_patch(frame)
        
Marubatsu_GUI.draw_board = draw_board
```
</details>

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

```diff_python
@staticmethod
def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, 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:
+       elif score > 0 or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
-       elif score == -1 or mb.status == Marubatsu.CROSS:
+       elif score < 0 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>

上記の修正後に下記のプログラムを実行して (1, 1) のみに着手が行われている局面を選択すると、実行結果のように背景色が正しく表示されるようになったことを確認できます。

```python
Mbtree_GUI(bftree_shortest_victory)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5c5fa8a4-2169-8225-f4ba-c9c7de2cf9fe.png" width="500">

また、(1, 1)、(1, 0)、(0, 0)、(2, 0) の順で着手を行った局面を選択すると、下図のように __すぐに勝利できる (2, 2)__ を着手した局面の __評価値 が 3__ で __最も高くなり__、__それ以外の水色__ の最善手を着手した局面の __評価値が 2__ となるため、__(2, 2) 以外__ を着手したの __局面が暗く表示されるよう__ になることが確認できます。そのため、__このゲーム木の評価値を使って着手を行う AI__ は、最善手の中で __最も早く勝利できる合法手を選択する__ ようになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a0cb6f91-cdd2-8f64-f3bb-ff5552410578.png" width="500">

## データの保存

ゲーム木のデータが正しいことが確認できたので、下記のプログラムで作成したゲーム木のデータをファイルに保存することにします。

```python
bftree_shortest_victory.save("../data/bftree_shortest_victory")
dftree_shortest_victory.save("../data/dftree_shortest_victory")
```

実行結果

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

# 必敗の局面での最善手の優劣

[以前の記事](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#%E5%BF%85%E6%95%97%E3%81%AE%E5%B1%80%E9%9D%A2%E3%81%A7%E3%81%AE%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%84%AA%E5%8A%A3)で、必敗の局面でも __人間から見て最善を尽くす__ ように見える着手を行うという観点では、__最善手に優劣が存在する__ ことを説明しました。

例えば、下記の (1, 1)、(1, 0)、(0, 0) の順で着手を行った局面は __× の必敗の局面__ なので、相手が最善手を着手し続けた場合は __どこに着手を行っても最終的には × が敗北します__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d4ab880d-5a1d-7552-49c4-318f412b3c88.png" width="500">

しかし、__人間の立場でこの局面を見る__ と、次の 〇の手番の勝利を阻止しない __(2, 2) 以外に着手を行うのは__、勝負を途中であきらめる __投げやりな着手のように見えてしまいます__。

また、相手が最強の AI でない場合は、__相手がミスをする可能性がある__ ため、__すぐに負けないように粘ることで、勝ちを拾える可能性__ があります。そのため、__必敗の局面__ ではなるべく __敗北を先に延ばすような着手を行ったほうが良い__ と考えることもできます。

実は __必敗の局面__ でなるべく __敗北を先に延ばすような着手__ は、__`bftree_shortest_victory` の評価値を使って計算することが可能__ です。その理由は、敗北を先に延ばすということは、__相手の勝利を遅らせるということと同じ__ であり、先程の評価値の計算方法では、__相手が速く勝利するほど自分にとって評価値が不利になる__ ように計算が行われるからです。

実際に、上図では次の相手の手番での __敗北を阻止する (2, 2) を着手した局面の評価値が 2__、__それ以外の着手を行った局面の評価値は 3__ となっており、__× の手番の局面では評価値が小さいほうが有利__ なので、この評価値に従って着手を行う AI は __(2, 2) のみを選択__ します。


# `bftree_shortest_victory` を利用した AI

__`bftree_shortest_victory`__ を利用した AI は、ゲーム木のデータを利用して着手を選択する [__`ai_gt4`__](https://qiita.com/ysgeso/items/321cf89ef5c49b861650#%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E4%B8%80%E8%A6%A7%E3%81%AE%E8%A8%88%E7%AE%97)[^2]を、キーワード引数に `mbtree=bftree_shortest_victory` を記述して呼び出すことで作成することができます。下記は、`play` メソッドを使って `bftree_shortest_victory` を利用した AI と人間が対戦するプログラムです。

```python
from ai import ai_gt4

mb = Marubatsu()
mb.play(ai=[ai_gt4, None], params=[{"mbtree": bftree_shortest_victory}, {}], gui=True)
```

上記を実行し、リセットボタンと待ったボタンを利用して、下図のように (0, 0)、(1, 0)、(0, 0) の順で着手が行われた局面を作ってください。この局面で __(2, 0) に着手を行う__ と、__`ai_gt4` は必ず (2, 2) を着手して勝利__ します。実際に確認して下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8d0932aa-3df0-7f55-c23a-86a60cbec644.png" width="300">

なお、下部に表示される __GUI の部分木__ は、今回の記事で作成した `bftree_shortest_victory` ではなく、__`aidata.mbtree`__ に保存されているゲーム木のデータを使って表示しているので、__評価値には -1, 0, 1 のみが計算されます__。GUI の部分木を `bftree_shortest_victory` を使って表示できるようにする改良は、次回の記事で行うことにします。

また、上図をよく見ると __評価値の文字__ が __上のゲーム盤少しに重なって表示されてしまう__ という問題があることがわかります。このような表示が行われる原因と修正方法についても次回の記事で説明することにします。

## `ai_gt6` を利用した AI

__`bftree_shortest_victory`__ はデータサイズが大きいので、[以前の記事](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#board-%E5%B1%9E%E6%80%A7%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E5%B1%80%E9%9D%A2%E3%81%A8%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%AF%BE%E5%BF%9C%E8%A1%A8%E3%81%AE%E4%BD%9C%E6%88%90)で行ったように、データサイズの小さい __`board` 属性を利用した局面と最善手の対応表を作成__ し、[__`ai_gt6`__](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#bestmoves_by_board-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9) を使って `bftree_shortest_victory` で計算した評価値を使った AI を実行したほうが良いでしょう。

下記は、[以前の記事](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#board-%E5%B1%9E%E6%80%A7%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E5%B1%80%E9%9D%A2%E3%81%A8%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%AF%BE%E5%BF%9C%E8%A1%A8%E3%81%AE%E4%BD%9C%E6%88%90)で記述した、ゲーム木のデータから __`bestmoves_by_board` を計算するプログラム__ です。また、計算した `bestmoves_by_board` を今後も利用できるようにするためには、このデータを __ファイルに保存する必要があります__。

```python
bestmoves_by_board = {}
for node in tqdm(mbtree.nodelist):
    txt = node.mb.board_to_str()
    if not txt in bestmoves_by_board.keys():
        bestmoves_by_board[txt] = node.bestmoves
```

ゲーム木から `bestmoves_by_board` を計算してファイルに保存する処理は、今後の記事で別の方法で評価値を計算するゲーム木を作成した際にも行う予定なので、下記の関数を定義することにします。

__名前__：`calc_and_save_bestmoves_by_board` とする
__処理__：ゲーム木から board 属性を利用した局面と最善手の対応表のデータを計算してファイルに保存し、返り値として返す
__入力__：ゲーム木のデータを仮引数 `mbtree` に、計算したデータを保存するファイルのパスを `path` に代入する
__出力__：計算した対応表のデータ

下記は、`calc_and_save_bestmoves_by_board` の定義です。また、この関数は `util.py` に保存することにします。

```python
from tqdm import tqdm
import pickle
import gzip

def calc_and_save_bestmoves_by_board(mbtree, path):
    bestmoves_by_board = {}
    for node in tqdm(mbtree.nodelist):
        txt = node.mb.board_to_str()
        if not txt in bestmoves_by_board.keys():
            bestmoves_by_board[txt] = node.bestmoves

    with gzip.open(path, "wb") as f:
        pickle.dump(bestmoves_by_board, f)
    
    return bestmoves_by_board
```

次に、下記のプログラムで `bftree_shortest_victory` から `bestmoves_by_board` を計算し、bestmoves_by_board_shortest_victory.dat というファイルに保存します。

```python
bestmoves_by_board = calc_and_save_bestmoves_by_board(bftree_shortest_victory,
                            "../data/bestmoves_by_board_shortest_victory.dat")
```

実行結果

```
100%|██████████| 549946/549946 [00:00<00:00, 562598.73it/s]
```

実行結果は省略しますが、人間とこの AI との対戦は下記のプログラムで行えます。

```python
from ai import ai_gt6

mb.play(ai=[None, ai_gt6], params=[{}, {"bestmoves_by_board": bestmoves_by_board}], gui=True)
```

先ほどと同様に (0, 0)、(1, 0)、(0, 0) の順で着手が行われた局面で AI が (2, 2) のみを着手することを確認して下さい。

## `gui_play` への AI の登録

次に、__`gui_play` でこの AI との対戦を行えるようにします__ が、その際に既に __`ai_gt6` を利用した別の AI が Dropdown に登録されている__ ので、Dropdown に登録する __AI の名前を考える必要があります__。そこでこの AI の Dropdown の項目名を shortest victory の頭文字を取って __`ai_gtsv`__ とすることにします。

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

* __7 行目__：ファイルから今回の記事で作成した AI に必要なパラメータのデータを読み込む
* __8 行目__：`ai_dict` の __`ai_gtsv`__ のキーの値に今回の記事で作成した AI のデータを登録する

```python
1  import ai as ai_module
2  from util import load_bestmoves
3
4  def gui_play(ai=None, params=None, ai_dict=None, seed=None):
元と同じなので省略
5          bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
6          ai_dict["ai_gt6"] = (ai_gt6, {"bestmoves_by_board": bestmoves_by_board})
7          bestmoves_by_board_sv = load_bestmoves("../data/bestmoves_by_board_shortest_victory.dat")
8          ai_dict["ai_gtsv"] = (ai_gt6, {"bestmoves_by_board": bestmoves_by_board_sv})
元と同じなので省略
```

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

```python
import ai as ai_module
from util import load_bestmoves

def gui_play(ai=None, params=None, ai_dict=None, seed=None):
    # ai が None の場合は、人間どうしの対戦を行う
    if ai is None:
        ai = [None, None]
    if params is None:
        params = [{}, {}]
    # ai_dict が None の場合は、ai1s ~ ai14s の Dropdown を作成するためのデータを計算する
    if ai_dict is None:
        ai_dict = { "人間": ( None, {} ) }
        for i in range(1, 15):
            ai_name = f"ai{i}s"  
            ai_dict[ai_name] = (getattr(ai_module, ai_name), {})
        bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
        ai_dict["ai_gt6"] = (ai_gt6, {"bestmoves_by_board": bestmoves_by_board})
        bestmoves_by_board_sv = load_bestmoves("../data/bestmoves_by_board_shortest_victory.dat")
        ai_dict["ai_gtsv"] = (ai_gt6, {"bestmoves_by_board": bestmoves_by_board_sv})
    
    mb = Marubatsu()
    mb.play(ai=ai, params=params, ai_dict=ai_dict, seed=seed, gui=True)
```
</details>

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

```diff_python
import ai as ai_module
from util import load_bestmoves

def gui_play(ai=None, params=None, ai_dict=None, seed=None):
元と同じなので省略
        bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
        ai_dict["ai_gt6"] = (ai_gt6, {"bestmoves_by_board": bestmoves_by_board})
        bestmoves_by_board_sv = load_bestmoves("../data/bestmoves_by_board_shortest_victory.dat")
        ai_dict["ai_gtsv"] = (ai_gt6, {"bestmoves_by_board": bestmoves_by_board_sv})
元と同じなので省略
```
</details>

下記のプログラムで `gui_play()` を実行した後で、下記の手順で操作を行うと、__`ai_gtsv` が必ず (2, 2) に着手を行って勝利する__ ことを確認して下さい。

```python
gui_play()
```

1. `gui_play()` を実行する
2. (1, 1)、(1, 0)、(0, 0) の順で着手を行う
3. 〇 の担当を `ai_gtsv` に変更し、「変更」ボタンをクリックする（下図）
4. (2, 0) に着手を行う 

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/11a496f8-28ea-66e1-9a59-21aaca4575fb.png" width="300">

また、下記の手順によって、× の必敗の局面で __`ai_gt6`__ が __開いているすべてのマスに着手を行う場合がある__ のに対し、__`ai_gtsv`__ は __必ず (2, 2) に着手を行って敗北を引き延ばす着手を行う__ ことを確認して下さい。

1. 手番の担当を両方とも人間にし、リセットボタンをクリックする
2. (1, 1)、(1, 0) の順で着手を行う
3. × の担当を `ai_gt6` に変更し、「変更」ボタンをクリックする
4. (0, 0) に着手を行い、AI がどこに着手を行うかを確認する
5. 待ったボタンをクリックして (0, 0) に着手を行う操作を何度か繰り返す
6. 待ったボタンをクリックし、× の担当を `ai_gtsv` に変更し、「変更」ボタンをクリックする
7. (0, 0) に着手を行い、AI がどこに着手を行うかを確認する
8. 待ったボタンをクリックして (0, 0) に着手を行う操作を何度か繰り返す

# 今回の記事のまとめ

今回の記事では、ゲーム木を利用した AI が、最善手の優劣を考慮して着手を行うようにする方法を紹介しました。

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/118/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [marubatsu_new.py](https://github.com/ysgeso/marubatsu/blob/master/118/marubatsu_new.py)  | 今回の記事で更新した marubatsu.py |
| [tree_new.py](https://github.com/ysgeso/marubatsu/blob/master/118/tree_new.py)  | 今回の記事で更新した tree.py |
| [util_new.py](https://github.com/ysgeso/marubatsu/blob/master/118/util_new.py)  | 今回の記事で更新した util.py |
| [bftree_shortest_victory.mbtree](https://github.com/ysgeso/marubatsu/blob/master/data/bftree_shortest_victory.mbtree)  | 今回の記事で作成した bftree_shortest_victory.mbtree |
| [dftree_shortest_victory.mbtree](https://github.com/ysgeso/marubatsu/blob/master/data/dftree_shortest_victory.mbtree)  | 今回の記事で作成した dftree_shortest_victory.mbtree |
| [bestmoves_by_board_shortest_victory.dat](https://github.com/ysgeso/marubatsu/blob/master/data/bestmoves_by_board_shortest_victory.dat)  | 今回の記事で作成した bestmoves_by_board_shortest_victory.dat |

# 次回の記事

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

[^1]:この `height` は、Mbtree_GUI クラスの `height` 属性ではなく、`draw_subtree` メソッドで計算した中心となるノードの表示の高さ（`centernode.height`）のことなので、ゲーム盤の上部に表示する評価値を表示する部分は含まれません
[^2]:ゲーム木を表すデータをキーワード引数 `mbtree` に記述して呼び出す `ai_gt1`、`ai_gt2`、`ai_gt3` を利用しても構いません