Pythonで〇×ゲームのAIを一から作成する　その136　ミニマックス法と引き分けの局面の評価値の再計算の処理の分離

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/86bcfad601e877cfc284

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

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

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

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

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

# バグの原因の検証と修正

[前回の記事](https://qiita.com/ysgeso/items/86bcfad601e877cfc284#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)では、引き分けの局面の最善手に対して、下記のような方法で優劣をつけたゲーム木の評価値を計算しました。

* __× の手番の局面の場合__
    * 相手の着手によって __〇 が 勝利する可能性がある__ 場合は __0.5__
    * そうでない場合は 0
* __〇 の手番の局面の場合__
    * 相手の着手によって __× が 勝利する可能性がある__ 場合は __-0.5__
    * そうでない場合は 0

## 前回の記事のバグのおさらい

しかし、計算した評価値を利用して Marubatsu_GUI クラスでゲーム木を表示すると、下図のように深さが 2、4、6 の __〇 の手番の引き分けの局面__ に __0.5 という評価値が計算__ されていることがわかります。先ほど説明した評価値の計算では、__〇 の手番の引き分けの局面__ の評価値は __0 または -0.5__ のいずれかになるので、__この評価値は間違っています__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e043de6f-1f15-8ca3-10e0-09546021de9d.png" width="500">

また、上図の深さ 5 の × の手番の一番上のノードをクリックすると下図のような部分木が表示されます。図から、__(0, 1)、(2, 1)__ に着手した局面には子孫ノードに __× が勝利するノードが存在__ し、__(0, 2)、(2, 2)__ に着手した場合は × が勝利するノードが __存在しない__ ので、この局面の __最善手は (0, 1) と (2, 1) になるはず__ ですが、図のように合法手の局面の __評価値が全て 0.5__ になっているため、__全ての合法手が最善手__ になるという __間違いが発生__ しています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9915318c-eb67-44e6-e50e-e71b63e962e9.png" width="300">

## バグの原因の検証

__評価値がおかしい__ ので、評価値を計算する処理を行う下記の __`calc_score_by_bf`__ を検証することにします。

```python
 1  def calc_score_by_bf(self):
略
 2              if node.mb.status != Marubatsu.PLAYING:
 3                  self.calc_score_of_node(node)
 4              else:
 5                  score_list = [childnode.score for childnode in node.children]
 6                  if node.mb.move_count % 2 == 0:
 7                      score = max(score_list)
 8                  else:
 9                      score = min(score_list)
10                  node.score = score
11                  node.max_score = max([childnode.max_score for childnode in node.children])
12                  node.min_score = min([childnode.min_score for childnode in node.children])
13              if node.score == 0:
14                  if node.mb.move_count % 2 == 1:
15                      if node.max_score > 0:
16                          node.score = 0.5
17                  else:
18                      if node.min_score < 0:
19                          node.score = -0.5
略
```

上記のプログラムでは、__4 ~ 10 行目__ で __[ミニマックス法](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)__ によって __子ノードの評価値の最大値（または最小値）を計算__ し、それを自身のノードの __評価値（`score` 属性）として計算__ しています。その後の __11、12 行目__ でこのノードの __[最大の評価値](https://qiita.com/ysgeso/items/86bcfad601e877cfc284#%E3%80%87-%E3%81%AE%E5%8B%9D%E5%88%A9%E3%81%AE%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E6%84%8F%E5%91%B3%E3%81%A8%E5%90%8D%E5%89%8D%E3%81%AE%E5%A4%89%E6%9B%B4)（`max_score` 属性）__ と __[最小の評価値](https://qiita.com/ysgeso/items/86bcfad601e877cfc284#%E3%80%87-%E3%81%AE%E6%89%8B%E7%95%AA%E3%81%AE%E5%B1%80%E9%9D%A2%E3%81%A7%E3%81%AE%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)（`min_score` 属性）を計算__ しています。

また、その後の 13 行目で自身のノードの評価値が引き分けの局面を表す `0` の場合に、__14 ~ 19 行目__ で __引き分けの局面に優劣をつける__ ために __評価値（`score` 属性）の値を修正する処理__ を行っています。

下記は、先程の間違った評価値が計算されたゲーム木の一部です。__赤枠__ の 〇 の手番の __引き分けの局面__ ノードの評価値は、__子孫ノードに 〇 が勝利するノードが存在__ するので __本当は -0.5 と計算__ されるはずが、__0.5 と計算されている点が間違っています__。そこで、赤枠のノードの評価値がどのように間違って計算されるかについて検証することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bd58d09e-3728-06f7-d611-067a2a575890.png" width="200">

### 深さが 9 のノードの評価値の計算

__ミニマックス法__ では、ノードの評価値を __子ノードの評価値を使って計算する__ ので、赤枠の深さが 6 のノードの評価値を計算するためには、__深さが 9、8、7__ のノードの評価値を __順に計算する__ 必要があります。

上図の右端の __深さが 9 のノード__ は、すべて __決着がついた局面__ であり、その場合の評価値は[以前の記事](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81)で説明した下記の表のように計算します。この表から上図の __深さ 9 のノード__ に表示される __評価値が正しく計算されている__ ことが確認できます。

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

また、決着がついたノードの最大の評価値と最小の評価値は、__`calc_score_of_node`__ で下記のプログラムのように、そのノードの __評価値と同じ値が計算__ されます。

```python
def calc_score_of_node(self, node:Node):
略
    node.max_score = node.score
    node.min_score = node.score
````

上記から、以下の事が確認できました。

* 上図の __深さが 9 のノードの評価値__ は __正しい値が計算__ されている
* 深さが 9 のノードの __最大の評価値__ と __最小の評価値__ は、__評価値と同じ値が計算__ される

### 深さが 8 のノードの評価値の計算

下図の右から 2 列目の __深さが 8 のノード__ のうち、__上から 3 番目__ と __5 番目__ のノードは __× の勝利で決着がついている局面__ なので、上記と同様の方法で評価値を計算すると __`-1` が計算__ されます。従って、下図ではそれらのノードに対して __評価値が正しく計算されている__ ことが確認できます。また、__最大の評価値__、__最小の評価値__ は、評価値と同じ __`-1` が計算__ されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bd58d09e-3728-06f7-d611-067a2a575890.png" width="200">

次に、深さが 8 のノードの中で、残りの __子ノードを持つノードの評価値__ の計算を検証します。深さが 8 のノードは __〇 の手番__ のノードなので、ミニマックス法では __子ノードの評価値の最大値__ がそのノードの評価値として計算されますが、深さが 8 のノードの中で子ノードが存在するノードには、__子ノードは 1 つしか存在しません__。そのためその評価値は __子ノードの評価値と同じ__ になります。

また、__最大の評価値__ と __最小の評価値__ は、子ノードの評価値の最大値または最小値で計算されますが、__同様の理由__ で __子ノード__ の最大の評価値と最小の評価値 __と同じ__ になります。

上図の深さ 8 のノードの上から 1、2、4、6 番のノードにはそのような評価値が表示されているので、__正しい評価値が計算されている__ ことが確認できます。

__ミニマックス法の後__ で __引き分けの局面の評価値__ が 0.5 や -0.5 に __変更される__ のは、__最大の評価値__ や __最小の評価値__ が __0 でない場合__ ですが、上図の深さ 8 の 2、4 番目の引き分けの局面のノードは __その条件に当てはまらない__ ので __評価値は `0` のまま__ 変更されません。

上記の事から、以下の事が確認できました。

* 上図の __深さが 8 のノードの評価値__ は __正しい値が計算__ されている
* 深さが 8 のノードの __最大の評価値__ と __最小の評価値__ は、__評価値と同じ値__ が計算される

### 深さが 7 のノードの評価値の計算

下図の左から 2 列目の __深さが 7 のノード__ の中に決着がついている局面は存在しません。また、深さが 7 のノードは __× の手番の局面__ なので、__ミニマックス法__ では __子ノードの評価値の最小値__ がそのノードの評価値として計算されます。また、最大の評価値と最小の評価値は、子ノードの評価値の最大値と最小値で計算されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bd58d09e-3728-06f7-d611-067a2a575890.png" width="200">

下記は、深さが 7 のノードの評価値、最大の評価値、最小の評価値の計算結果です。

|  | 評価値 | 最大の評価値 | 最小の評価値 |
|:-:|:-:|:-:|:-:|
| __1 つ目__  | `0`  | `1`  | `0`  |
| __2 つ目__  | `-1`  | `0`  | `-1`  |
| __3 つ目__  | `-1`  | `1`  | `-1`  |

__× の手番__ の __引き分けの局面の評価値__ は、__子孫ノード__ の中に __〇 が勝利する局面が存在する場合__ は  __0.5 と計算する__ 必要があり、その処理は __`calc_score_by_bf`__ の中の下記のプログラムで行われます。上記の表から、深さ 7 の __引き分けの局面__ である 1 つ目のノードの __最大の評価値__（`max_score` 属性）は __`1`__ なので、その __ノードの評価値は `0.5` に修正__ されます。

```python
             if node.score == 0:
                 if node.mb.move_count % 2 == 1:
                     if node.max_score > 0:
                         node.score = 0.5
```

従って、深さ 7 のノードの評価値は下記の表のようになり、__上図の深さが 7 のノード__ の評価値は __正しい値が計算されている__ ことが確認できました。

|  | 評価値 | 最大の評価値 | 最小の評価値 |
|:-:|:-:|:-:|:-:|
| __1 つ目__  | `0.5`  | `1`  | `0`  |
| __2 つ目__  | `-1`  | `0`  | `-1`  |
| __3 つ目__  | `-1`  | `1`  | `-1`  |

### 赤枠の深さが 6 のノードの評価値の計算

下図の赤枠の __深さが 6 のノード__ は決着がついておらず、__〇 の手番__ の局面なので、ミニマックス法では __子ノードの評価値の最大値__ がそのノードの評価値として計算されます。また、最大の評価値と最小の評価値は、子ノードの評価値の最大値と最小値で計算されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bd58d09e-3728-06f7-d611-067a2a575890.png" width="200">

下記は、深さが 6 のノードの評価値、最大の評価値、最小の評価値の計算結果です。

| 評価値 | 最大の評価値 | 最小の評価値 |
|:-:|:-:|:-:|
| `0.5`  | `1`  | `-1`  |

__〇 の手番__ の引き分けの局面の評価値は、__子孫ノード__ の中に __× が勝利する局面が存在する__ 場合は __-0.5 と計算__ する必要があり、その処理は __`calc_score_by_bf`__ の中の下記のプログラムの 6 行目で行われます。

```python
1             if node.score == 0:
2                 if node.mb.move_count % 2 == 1:
3                     略
4                 else:
5                     if node.min_score < 0:
6                         node.score = -0.5
```

上記の __6 行目が実行されるため__ には、下記の条件を __すべて満たす__ 必要があります。

* 評価値（`score` 属性）が引き分けの局面を表す `0` である
* 手番が 〇 の局面（`move_count` 属性が偶数）である
* 最小の評価値（`min_score` 属性）の値が負である

先程の表から上記の 2、3 番目の条件は満たされますが、__評価値の値は `0.5`__ なので __1 番目の条件は満たされません__。そのため、上記の __6 行目は実行されず__、__評価値__ の値は __`0.5` から変化しません__。これが赤枠の局面の評価値が `0.5` という間違った値になる原因です。

この問題を修正する方法を少し考えてみて下さい。

:::note
今気づいたのですが、〇 の手番であることの判定は `mb.turn == Marubatsu.CIRCLE` で行えます。`move_count` が偶数であるかどうかで判定する方法はわかりにくいですが、今から過去のプログラムをさかのぼって修正するのは大変なので、既に記述した部分のプログラムでは引き続きこの方法で判定することにします。
:::

## `calc_score_by_bf` の修正

このプログラムの問題は、__引き分けの局面の評価値__ を `0` だけでなく、__`-0.5`、`0.5` に増やした__ にも関わらず、上記のプログラムの __1 行目__ で __引き分けの局面であること__ を __評価値が `0` であることで判定__ している点です。[前回の記事](https://qiita.com/ysgeso/items/86bcfad601e877cfc284#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E8%89%B2%E3%81%AE%E8%A1%A8%E7%A4%BA%E3%81%AE%E3%83%90%E3%82%B0%E3%81%AE%E6%A4%9C%E8%A8%BC%E3%81%A8%E4%BF%AE%E6%AD%A3)で、ノードの色を計算する際に __-1 < 評価値 < 1__ の場合に __引き分けの局面である事を表すとした__ ので、それに合わせて __`calc_score_by_bf`__ を下記のプログラムの 5 行目のように修正することで、このバグを修正することができます。

```python
 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3
 4  def calc_score_by_bf(self):
元と同じなので省略
 5              if -1 < node.score < 1:
 6                  if node.mb.move_count % 2 == 1:
 7                      if node.max_score > 0:
 8                          node.score = 0.5
元と同じなので省略
 9
10  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):
    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
                node.max_score = max([childnode.max_score for childnode in node.children])
                node.min_score = min([childnode.min_score for childnode in node.children])
            if -1 < node.score < 1:
                if node.mb.move_count % 2 == 1:
                    if node.max_score > 0:
                        node.score = 0.5
                else:
                    if node.min_score < 0:
                        node.score = -0.5
            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
from tree import Mbtree
from marubatsu import Marubatsu

def calc_score_by_bf(self):
元と同じなので省略
-           if node.score == 0:
+           if -1 < node.score < 1:
                if node.mb.move_count % 2 == 1:
                    if node.max_score > 0:
                        node.score = 0.5
                    else:
                        node.score = 0
元と同じなので省略

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

上記の修正後に下記のプログラムを実行すると、実行結果のように __〇 の手番__ の深さが偶数のノードの __引き分けの局面の評価値__ に __`-0.5` という正しい値が計算される__ ようになることが確認できます[^1]。

```python
from tree import Mbtree_GUI

mbtree = Mbtree(shortest_victory=True)
data = mbtree.calc_and_save_bestmoves_and_score_by_board("test.dat")
Mbtree_GUI(scoretable_dict={"test": data})
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9b7c3cc5-3ef1-b751-97c0-7f07921b35a9.png" width="500">

また、先程の __検証で使った局面__ を中心とする部分木を表示すると、__左下図__ のように __正しい評価値__ である __`-0.5` が計算__ されていることが確認できます。先ほどの間違った計算が行われていた右下図と比べてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6ccff385-43e8-2d60-c758-3f92189fba7c.png" width="200">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bd58d09e-3728-06f7-d611-067a2a575890.png" width="200">

これで、バグが修正されたと思った方がいるかもしれませんが、このプログラムには __バグがまだ残っています__。どのようなバグが存在するかについて少し考えてみて下さい。ヒントは、そのバグは 2 つ上の __ルートノードを中心とした部分木の図の中__ にあります。

## バグとその検証

評価値が間違っているノードは 1 つしかないので __この間違いに気づくことはかなり困難__ ですが、問題は下図の __赤丸のノード__ にあります。このノードは __〇 の手番の局面__ ですが評価値として __`0.5` が計算__ されている点が __間違っています__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/81466793-2637-60ba-7848-85af4918cbe8.png" width="500">

下図はこのノードをクリックして表示される、このノードを中心とした部分木です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/43ff1590-262a-1559-2659-8547aa12fe83.png" width="200">

先程と同じ手順で、このノードの子ノードである左から 2 列目の __深さが 7__ のノードの評価値を計算すると、下記の表ようになります。

|  | 評価値 | 最大の評価値 | 最小の評価値 |
|:-:|:-:|:-:|:-:|
| __1 つ目__  | `0.5`  | `1`  | `0`  |
| __2 つ目__  | `0.5`  | `1`  | `0`  |
| __3 つ目__  | `0`  | `0`  | `0`  |

下記の表は上記を元に __〇 の手番__ である __赤枠のノードの評価値__ を __ミニマックス法で計算__ した表です。

| 評価値 | 最大の評価値 | 最小の評価値 |
|:-:|:-:|:-:|
| `0.5`  | `1`  | `0`  |

上記の計算結果に対して、__引き分けの局面__ での __優劣を表す評価値__ を計算する下記のプログラムを実行すると、1 行目の条件式は `True`、2 行目の条件式は `False`、6 行目の条件式は `False` なので、下記のプログラムでは __`score` 属性に対する処理は行われない__ ため、赤枠のノードの __評価値は `0.5` のまま変化しない__ ことになります。これが上記のバグの原因です。このバグを修正する方法について少し考えてみて下さい。

```python
1            if -1 < node.score < 1:
2                if node.mb.move_count % 2 == 1:
3                    if node.max_score > 0:
4                        node.score = 0.5
5                else:
6                    if node.min_score < 0:
7                        node.score = -0.5
```                        

## バグの修正

このバグを修正するためには、__引き分けの局面__ では __〇 の手番__ の場合に __評価値を `0` か `-0.5`__ のいずれかになるようにする必要があります。また、同様に __× の手番__ の場合に __評価値を `0` か `0.5`__  のいずれかになるようにする必要があります。下記は、そのように __`calc_score_by_bf`__ を修正したプログラムです。

* __6、7 行目__：× の手番の局面の場合に、評価値が `0.5` でなければ、`0` にする
* __11、12 行目__：〇 の手番の局面の場合に、評価値が `-0.5` でなければ `0` にする

```python
 1  def calc_score_by_bf(self):
元と同じなので省略
 2              if -1 < node.score < 1:
 3                  if node.mb.move_count % 2 == 1:
 4                      if node.max_score > 0:
 5                          node.score = 0.5
 6                      else:
 7                          node.score = 0
 8                  else:
 9                      if node.min_score < 0:
10                          node.score = -0.5
11                      else:
12                          node.score = 0
元と同じなので省略
13
14  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
                node.max_score = max([childnode.max_score for childnode in node.children])
                node.min_score = min([childnode.min_score for childnode in node.children])
            if -1 < node.score < 1:
                if node.mb.move_count % 2 == 1:
                    if node.max_score > 0:
                        node.score = 0.5
                    else:
                        node.score = 0
                else:
                    if node.min_score < 0:
                        node.score = -0.5
                    else:
                        node.score = 0
            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):
元と同じなので省略
            if -1 < node.score < 1:
                if node.mb.move_count % 2 == 1:
                    if node.max_score > 0:
                        node.score = 0.5
+                   else:
+                       node.score = 0
                else:
                    if node.min_score < 0:
                        node.score = -0.5
+                   else:
+                       node.score = 0
元と同じなので省略

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

上記の修正後に下記のプログラムを実行すると、実行結果のように __赤丸__ の 〇 の手番の引き分けの局面の __評価値に `0` という正しい値が計算される__ ようになることが確認できます。

```python
mbtree = Mbtree(shortest_victory=True)
data = mbtree.calc_and_save_bestmoves_and_score_by_board("test.dat")
Mbtree_GUI(scoretable_dict={"test": data})
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/fd54a41e-87a7-3cb1-1447-8812370a07ec.png" width="500">

# ミニマックス法と引き分けの局面の評価値の計算の分離

評価値を計算する __`calc_score_by_bf` の中__ に引き分けの局面の最善手に優劣をつける __評価値を計算する処理を記述した際__ に、今回の記事で紹介したような __2 つのバグが発生した理由__ は、__ミニマックス法__ で評価値を計算する処理と、__ミニマックス法と異なる方法__ で評価値を計算する __処理を混ぜてしまったから__ です。

このように __性質が異なる処理__ を __無理にまとめて行おうとする__ と、__正しい計算が行われない可能性が高くなる__ ので、特別な理由[^2]がない限りは __避けたほうが無難__ です。実際に、今回の記事で行った修正のように、正しい計算が行われるようにするために __別の処理を記述する必要__ が生じたり、その分だけ __プログラムがわかりづらくなる__ という欠点が生じます。また、今回の記事で紹介した 2 つ目のバグのように、__見つけることが非常に困難なバグが発生する__ ことがあります。

__引き分けの局面の最善手に優劣をつけるため__ の評価値の __計算の処理__ を、__ミニマックス法__ による評価値の __計算が完全に終わった後__ で行えばそのような __問題は発生しない__ ので、Mbtree クラスに下記のようなメソッドを定義する事にします。

__処理__：引き分けの局面の最善手に優劣をつけるための評価値を計算する
__名前__：__評価値__（score）を __再計算__（recalculate）するので __`recalculate_score`__ とする
__入力__：なし
__出力__：なし

:::note
今回の記事の最後で簡単に説明しますが、必敗の局面の最善手の優劣をつけたい場合は、必敗の局面の評価値を再計算する必要があります。そのような計算を行うことができるようにするために、メソッドの名前の中に `draw` を入れないようにしました。
:::

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

まず、下記のプログラムのように、__`calc_score_by_bf`__ から __引き分けの局面の評価値を修正する処理を削除__ する必要があります。

```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
                node.max_score = max([childnode.max_score for childnode in node.children])
                node.min_score = min([childnode.min_score for childnode in node.children])
            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><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.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
                node.max_score = max([childnode.max_score for childnode in node.children])
                node.min_score = min([childnode.min_score for childnode in node.children])
-           if -1 < node.score < 1:
-               if node.mb.move_count % 2 == 1:
-                   if node.max_score > 0:
-                       node.score = 0.5
-                   else:
-                       node.score = 0
-               else:
-                   if node.min_score < 0:
-                       node.score = -0.5
-                   else:
-                       node.score = 0
            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>

## Mbtree クラスの `recalculate_score` の定義

下記は __`recalculate_score`__ の定義です。__引き分けの局面の評価値の再計算__ を行う際に、計算を行う __局面の順番__ は __どのような順番でも構わない__ ので、幅優先アルゴリズムや、深さ優先アルゴリズムを利用する必要はなく、下記のプログラムの __2 行目__ のように、ゲーム木の __ノードの一覧が記録__ されている __`nodelist` 属性__ の中から順番のノードを取り出して評価値の再計算を行うことができます。

* __2 行目__：ゲーム木を作成する際に、ゲーム木のノードの一覧は `nodelist` 属性に代入されるので、それを使って全てのノードに対する繰り返し処理を行う
* __3 行目__：引き分けの局面であることを `score` 属性が `0` であることで判定する。ミニマックス法では引き分けの局面の評価値を `0` として計算したので、先程のように -1 以上 1 以下という条件で判定する必要はない
* __4 ~ 13 行目__：先程 `calc_score_by_bf` から削除した、引き分けの局面の評価値を修正する処理と同じ処理を記述する

```python
 1  def recalculate_score(self):
 2      for node in self.nodelist:
 3          if node.score == 0:
 4              if node.mb.move_count % 2 == 1:
 5                  if node.max_score > 0:
 6                      node.score = 0.5
 7                  else:
 8                      node.score = 0
 9              else:
10                  if node.min_score < 0:
11                      node.score = -0.5
12                  else:
13                      node.score = 0
14
15  Mbtree.recalculate_score = recalculate_score
```

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

```python
def recalculate_score(self):
    for node in self.nodelist:
        if node.score == 0:
            if node.mb.move_count % 2 == 1:
                if node.max_score > 0:
                    node.score = 0.5
                else:
                    node.score = 0
            else:
                if node.min_score < 0:
                    node.score = -0.5
                else:
                    node.score = 0

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

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

__ゲーム木を作成する際__ に、__引き分けの局面の評価値を再計算するか__ どうかを __`recalculate_draw_score`__ という __仮引数で区別__ できるように、Mbtree クラスの __`__init__`__ メソッドを下記のプログラムのように修正します。

* __3 行目__：デフォルト値を `False` をとする仮引数 `recalculate_draw_score` を追加する
* __5 行目__：`recalculate_draw_score` を同名の属性に代入する
* __6、7 行目__：`recalculate_draw_score` 属性が `True` の場合のみ `recalculate_score` メソッドを呼び出して、引き分けの局面の評価値を再計算する

```python
 1  from tree import Node
 2
 3  def __init__(self, algo="bf", shortest_victory=False, recalculate_draw_score=False, subtree=None):
元と同じなので省略
 4      self.shortest_victory = shortest_victory
 5      self.recalculate_draw_score = recalculate_draw_score
元と同じなので省略
 6      if self.recalculate_draw_score:
 7          self.recalculate_score()
 8      self.nodelist_by_mb = {}
 9      self.bestmoves_by_mb = {}
10      self.calc_bestmoves(self.root)
11      
12  Mbtree.__init__ = __init__
```

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

```python
from tree import Node

def __init__(self, algo="bf", shortest_victory=False, recalculate_draw_score=False, subtree=None):
    if subtree is not None:
        self.subtree = subtree
        self.create_subtree()
        return

    self.algo = algo
    self.shortest_victory = shortest_victory
    self.recalculate_draw_score = recalculate_draw_score
    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)
    if self.recalculate_draw_score:
        self.recalculate_score()
    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 Node

-def __init__(self, algo="bf", shortest_victory=False, subtree=None):
+def __init__(self, algo="bf", shortest_victory=False, recalculate_draw_score=False, subtree=None):
元と同じなので省略
    self.algo = algo
    self.shortest_victory = shortest_victory
+   self.recalculate_draw_score = recalculate_draw_score
元と同じなので省略
+   if self.recalculate_draw_score:
+       self.recalculate_score()
    self.nodelist_by_mb = {}
    self.bestmoves_by_mb = {}
    self.calc_bestmoves(self.root)
    
Mbtree.__init__ = __init__
```
</details>

実行結果は同じなので省略しますが、上記の修正後に下記のプログラムを実行すると、正しい評価値が計算されることが確認できます。なお、局面と最善手・評価値の対応表のデータを保存する __ファイルの名前__ をこれまで通りの方法でつけると長くなりすぎるので __bestmoves_and_score_by_board_sv_rd.dat__ としました。

```python
mbtree = Mbtree(shortest_victory=True, recalculate_draw_score=True)
data = mbtree.calc_and_save_bestmoves_and_score_by_board("../data/bestmoves_and_score_by_board_sv_rd.dat")
Mbtree_GUI(scoretable_dict={"test": data})
```

# 新しい AI に関する処理

上記で新しい評価値を計算したゲーム木を利用した AI の名前を ゲーム木（game tree）を利用した AI、最短の勝利（shortest victory）を目指す AI、引き分けの局面の評価値を再計算（recalculate draw score）AI であることからそれらの頭文字を取って __`ai_gtsvrd`__ と表記することにし、この AI に関するいくつかの処理を行うことにします。

## `ai2s` との対戦

下記のプログラムで __`ai_gtsrvd`__ とランダムな着手を行う __`ai2s` で対戦__ を行うことで、その __性能を評価__ することにします。

```python
from ai import ai_match, ai2, ai_gt7

ai_match(ai=[ai_gt7, ai2], params=[{"bestmoves_and_score_by_board": data}, {}])
```

実行結果（実行結果はランダムなので下記と異なる場合があります）

```
ai_gt7 VS ai2
100%|██████████| 10000/10000 [00:03<00:00, 2800.99it/s]
count     win    lose    draw
o        9714       0     286
x        8110       0    1890
total   17824       0    2176

ratio     win    lose    draw
o       97.1%    0.0%    2.9%
x       81.1%    0.0%   18.9%
total   89.1%    0.0%   10.9%
```

下記は、ルールベースの AI の中で最後に作成した __`ai14s`__、ゲーム木を利用した最初の AI である __`ai_gt1`__、__`ai_gtsvrd`__ のそれぞれが __`ai2s`__ と対戦した結果をまとめた表です。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __[`ai14s`](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#ai14s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __99.0__ | __0.0__ | 1.0 | __88.8__ | __0.0__ | 11.2 | __93.9__ | __0.0__ | 6.1 |
| __[`ai_gt1`](https://qiita.com/ysgeso/items/321cf89ef5c49b861650#%E7%9D%80%E6%89%8B%E3%81%AE%E8%A8%88%E7%AE%97)__  | __96.9__ | __0.0__ | 3.1 | __78.0__ | __0.0__ | 22.1 | __87.4__ | __0.0__ | 12.6 |
| __[`ai_gtsvrd`](https://qiita.com/ysgeso/items/321cf89ef5c49b861650#%E7%9D%80%E6%89%8B%E3%81%AE%E8%A8%88%E7%AE%97)__  | __97.1__ | __0.0__ | 2.9 | __81.1__ | __0.0__ | 18.9 | __89.1__ | __0.0__ | 10.9 |

上記の表から、__引き分けの評価値を再計算しない `ai_gt1`__ と比較して、__`ai_gtsvrd`__ は特に × を担当した場合の勝率が向上していることが確認できます。

### `ai14s` よりも勝率が劣る理由

残念ながら __`ai14s`__ と比較すると __`ai_gtsvrd` の勝率は劣ります__ が、その理由はランダムな着手を行う AI と対戦した際に、引き分けの局面の最善手の中で、__相手が最善手を着手しなかった場合に勝利できる合法手__ にも __優劣が存在する__ からです。

わかりづらいと思いますので具体例を挙げて説明します。下図の赤枠の 〇 の手番の局面の __合法手のうち (1, 0)、(2, 0)、(1, 2)、(2, 2)__ は評価値が 0.5 と表示されているので、その __子孫ノードに 〇 が勝利する局面が存在__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3b1ed52b-bb0a-709f-7785-616161c1a3a3.png" width="250">

下図は __(1, 0) に着手__ した場合の局面を中心とする __部分木__ です。図からこの局面の __4 つある合法手のうち 3 つ__ は __最善手ではない__ ため、相手がそれらを選択すると常に最善手を選択する __強解決の AI__ である __`ai_svgtrd`__ は __100 % 勝利__ することができます。従って、__`ai2s`__ がこの局面で __ランダムに着手を選択__ すると 3/4 = __75 % の確率__ で __`ai_gtsvrd` は勝利__ することができます。`ai2s` が (1, 2) に着手を行った場合の `ai_gtsvrd` が勝利する確率は、その子孫ノードを見て確率を計算する必要がありますが、上図の局面で __`ai_gtsvrd` が (1, 0) に着手__ を行った場合に __勝利する確率__ は __少なくとも 75 % 以上__ であることは間違いありません。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c3574291-e95f-1682-a497-2b606e01ce5c.png" width="250">

:::note warn
このように、常に最善手を選択する __強解決の AI__ が __ランダムな着手を行う `ai2s` と対戦__ する場合は、__`ai2s` の手番__ の局面の合法手の中の、__最善手でない合法手__ の __割合が高い程勝率が高くなる__ という傾向があります[^3]。
:::

一方、下図は __(2, 2) に着手__ した場合の局面を中心とする __部分木__ です。図からこの局面は __全ての合法手__ が __引き分けの局面になる最善手__ なので、`ai2s` がどの着手を行っても、次の 〇 の手番の局面で __〇 が勝利が確定しない__ ことがわかります。正確な 〇 の勝利の確率は下図の子孫ノードを調べなければ確認できませんが、先程の局面で __`ai_gtsvrd` が (1, 0) に着手__ を行った場合に __勝利する確率__ よりも __低い可能性が非常に高い__ でしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/68a9f2cc-41cb-2b64-c464-61d100685f9c.png" width="250">

このことから、__相手がランダムな着手を行う AI__ の場合は、引き分けの局面の最善手の中で __相手が最善手を着手しなかった場合に勝利できる合法手__ に実際に __優劣が存在する__ ことが確認できました。`ai14s` のほうが `ai_gtsvrd` よりも `ai2s` に対する勝率が高いのは、__`ai14s`__ が __最善手の割合が少ない局面になる合法手__ を __`ai_gtsvrd` よりも選択する__ からです。

なお、相手が __人間の場合__ は上記の (1, 0) のほうが (2, 2) よりも __優れているとは限りません__。それは、__人間が__ 合法手の中から __着手を選択する際__ に、一般的に __ランダムに選択することはない__ からです。そのため、合法手の中で __人間が選択しやすい__ ものと、__そうでないものが存在__ します。人間の手番の合法手の中で、人間が最善手を選択しやすい __簡単な局面の場合__ は __最善手の割合がどれだけ少なくても__ AI が有利になることはありません。そのため、引き分けの局面で __人間に勝ちやすい AI を作成する__ ためには、最善手の中で __人間が間違えやすいような難しい局面になる__ ような着手を行うことが重要になります。

ただし、__人間にとって難しい局面__ がどのような局面であるかを __判断する方法は簡単ではありません__。そのためには、ミニマックス法や、最善手の割合以外の __別の評価値を計算する方法を考える__ 必要があり、どのようなゲームでもそのような判断を行うための __統一的な方法はまだ見つかっていない__ と思います。

:::note
将棋などでは、__不利な局面__ で最善手を着手するのではなく、__相手が間違えやすい難しい局面になる__ ような __あえて最善手ではない着手__ を選択することで、__逆転を狙う__ ということが良く行われます。そのような着手は __相手が最善手を着手した場合はさらに不利になる__ ので相手が AI の場合は基本的には通用しませんが、人間が相手の場合は逆転につながることが実際にあります。

余談ですが、将棋の AI が現在と比べてまだ弱かった頃に行われた AI とプロ棋士の対戦で、[AI の弱点をついた最善手ではない着手を選択することで AI に勝利するという試合](https://weekly.ascii.jp/elem/000/002/632/2632599/)が実際に行われたことがあります。

なお、__現在の将棋などの AI__ では、原則として __最善手を着手することを目指__ すように作られているので、そのような着手を行うことはありません。

逆に __初心者__ のように、__相手が弱い__ ことがわかっている場合は、あえて最善手を選択しないことで、__手加減をすることが重要になる__ ことがあります。例えば、初心者に圧勝してしまうと、そのゲームが嫌になってしまう可能性が高いからです。本記事では紹介しませんが、__相手のレベルに合わせて手加減をうまく行う__ ような AI を作成するためには、ミニマックス法以外の __別の工夫が必要__ になります。
:::

## 強解決の AI であるかどうかの確認

念のため、__`ai_gtsvrd`__ が __[強解決の AI であるか](https://qiita.com/ysgeso/items/80f19df519a6a856bbf8#%E5%BC%B7%E8%A7%A3%E6%B1%BA%E3%81%A7%E3%81%82%E3%82%8B%E3%81%8B%E3%82%92%E5%88%A4%E5%AE%9A%E3%81%99%E3%82%8B%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)__ を下記のプログラムで確認することにします。実行結果から強解決の AI であることが確認できました。

```python
from util import Check_solved

Check_solved.is_strongly_solved(ai_gt7, {"bestmoves_and_score_by_board": data})
```

実行結果

```
100%|██████████| 431/431 [00:00<00:00, 3905.72it/s]
431/431 100.00%

(True, [])
```

## ゲーム木のデータの保存

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

```python
mbtree.save("../data/bftree_svrd")
```

実行結果

```
save completed.
```

## `gui_play` への組み込み

__`gui_play`__ を下記のプログラムのように修正して、__`ai_gtsvrd`__ を __Dropdown で選択できる__ ようにします。

* __5、6 行目__：ファイルからデータを読み込んで Dropdown に `ai_gtsvrd` の項目を追加する

```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_and_score_by_board_svrd = load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat")
6       ai_dict["ai_gtsvrd"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board_svrd})
元と同じなので省略
```

<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_and_score_by_board = load_bestmoves("../data/bestmoves_and_score_by_board.dat")
        ai_dict["ai_gt7"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board})
        bestmoves_and_score_by_board_sv = load_bestmoves("../data/bestmoves_and_score_by_board_shortest_victory.dat")
        ai_dict["ai_gtsv"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board_sv})
        bestmoves_and_score_by_board_svrd = load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat")
        ai_dict["ai_gtsvrd"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board_svrd})

    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_and_score_by_board_svrd = load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat")
+       ai_dict["ai_gtsvrd"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board_svrd})

元と同じなので省略
```
</details>

上記の修正後に下記のプログラムを実行し、先程の局面になるように着手を行った後で「状況」ボタンをクリックし、の右の Dropdown に __`ai_gtsvrd` を選択__ すると、実行結果の左下図のように相手が間違えた場合に __勝利できる可能性がある (0, 2) と (2, 0) の評価値は 0.5__、__絶対に勝利できない (2, 2) の評価値は 0__ が計算されることが確認できます。また、Dropdown に __`ai_gtsv`__ を選択すると右下図のように __すべての合法手の評価値が 0__ で __赤字で表示される__ ため、__(2, 2) に着手してしまう可能性がある__ 事が確認できます。

```python
gui_play()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9f7218af-8301-9ffb-b157-b0803a18639c.png" width="250">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/069ad1b1-1641-7299-6d31-877cfde15162.png" width="250">

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

最後に。__Mbtree_GUI__ クラスの __`__init__`__ メソッドに下記のプログラムの __5 行目を追加__ することで、ゲーム木を表示する GUI の Dropdown に Recalculate Draw というラベルで __`ai_gtsvrd` のデータを選択できる__ ように修正します。なお、前回の記事で `ai_gt7` を作成したので、それに合わせて __3 行目__ の Dropdown の項目の __ラベルを `ai_gt6` から `ai_gt7` に修正__ しました。


```python
1  def __init__(self, scoretable_dict=None, show_score=True, size=0.15):
元と同じなので省略
2          scoretable_dict = {
3              "Standard (ai_gt7)": load_bestmoves("../data/bestmoves_and_score_by_board.dat"),
4              "Shortest victory (ai_gtsv)": load_bestmoves("../data/bestmoves_and_score_by_board_shortest_victory.dat"),
5              "Recalculate draw (ai_gtsvrd)": load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat"),
6          }
元と同じなので省略
7    
8  Mbtree_GUI.__init__ = __init__
```

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

```python
def __init__(self, scoretable_dict=None, show_score=True, size=0.15):
    if scoretable_dict is None:
        from util import load_bestmoves
        
        scoretable_dict = {
            "Standard (ai_gt7)": load_bestmoves("../data/bestmoves_and_score_by_board.dat"),
            "Shortest victory (ai_gtsv)": load_bestmoves("../data/bestmoves_and_score_by_board_shortest_victory.dat"),
            "Recalculate draw (ai_gtsvrd)": load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat"),
        }
    self.scoretable_dict = scoretable_dict
    self.show_score = show_score
    self.size = size
    self.width = 50
    self.height = 65
    self.selectednode = Node(Marubatsu())
    super(Mbtree_GUI, self).__init__()
    
Mbtree_GUI.__init__ = __init__
```
</details>

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

```diff_python
def __init__(self, scoretable_dict=None, show_score=True, size=0.15):
元と同じなので省略
        scoretable_dict = {
-           "Standard (ai_gt6)": load_bestmoves("../data/bestmoves_and_score_by_board.dat"),
+           "Standard (ai_gt7)": load_bestmoves("../data/bestmoves_and_score_by_board.dat"),
            "Shortest victory (ai_gtsv)": load_bestmoves("../data/bestmoves_and_score_by_board_shortest_victory.dat"),
+           "Recalculate draw (ai_gtsvrd)": load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat"),
        }
元と同じなので省略
    
Mbtree_GUI.__init__ = __init__
```
</details>

上記の修正後に下記のプログラムを実行し、Dropdown に Recaluculate draw を選択してから先程の局面を選択すると、下図のように __`ai_gtsvrd`__ のデータで部分木のノードの上に __再計算された評価値が表示__ されるようになったことが確認できます。

```python
gui_play()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1ca29898-9d23-3e69-c534-ba375e9c877a.png" width="350">

# 必敗の局面での合法手の優劣

__必敗の局面__ では、すべての合法手が最善手になりますが、その場合の合法手に対しても __何らかの方法で優劣をつける__ ことが可能です。

例えば、__〇 が着手を行った 〇 の必敗の局面__ に対して下記のような評価値を計算することで、__〇 の手番の必敗の局面__ に対して「__勝利する可能性がある合法手 > 引き分けになる可能性がある合法手 > 絶対に敗北する合法手__」という優劣をつけることができます。

* 〇 の必敗の局面なので、__負の評価値を計算__ する
* __子孫ノード__ に __〇 が勝利するノードが存在__ する場合は __-1__ の評価値を計算する
* そうではなく、子孫ノードに __引き分けのノードが存在__ する場合は __-2__ の評価値を計算する
* そうではなく、__敗北するノードしか存在しない__ 場合は __-2 未満の評価値__ を計算する

× の手番の × の必敗の局面に対しても同様です。

なお、本記事ではそのような評価値を計算する処理は実装しません。その理由はゲーム開始時の局面が引き分けの局面である __〇×ゲーム__ では、__強解決の AI__ が対戦を行った場合に、その AI が __必敗になる局面が生じることはない__ からです。そのため、そのような AI を作成して __`ai2s` と対戦__ しても、__勝率が良くなることはありません__。

なお、__最善手を着手しない可能性がある AI__ や __人間__ が __着手を行った局面__ に対して、__評価値を計算したい場合__ は、そのような AI を作成する __意味が生じます__ ので、興味と余裕がある方は実装してみて下さい。

# 今回の記事のまとめ

今回の記事では、前回の記事で実装したプログラムのバグの検証と修正を行いました。また、__ミニマックス法による評価値の計算__ と、__引き分けの局面の評価値の再計算__ の処理を __分離して実装する__ 方法を紹介しました。

最後に、作成した AI を `gui_play` などで選択できるようにしました。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82

[^1]:この後で説明しますが、__実際には正しく確認できていません__
[^2]:例えば、処理速度が非常に重要で、まとめて処理を行うことで処理が速く行える場合などです
[^3]:正確な勝率の計算には子ノードだけでなく、子孫ノードについての確率も計算する必要があります