Pythonで〇×ゲームのAIを一から作成する　その135　引き分けの局面での最善手の優劣と最大と最小の評価値の計算

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/368f00bae5408bac496a

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

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

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

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

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

# 引き分けの局面での最善手の優劣

[以前の記事](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#%E5%BF%85%E5%8B%9D%E3%81%AE%E5%B1%80%E9%9D%A2%E3%81%AE%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%84%AA%E5%8A%A3)で、__必勝の局面の最善手__ に対して「なるべく早く勝利できる着手に高い評価値を計算する」という方法で __優劣をつける__ という方法を紹介し、その評価値で着手を選択する __`ai_gtsv`__ を作成しました。

必勝の局面の最善手に対して優劣をつけても、相手が最善手のみを選択する __最強の AI の場合は勝敗結果は変わりません__ が、無駄に試合を長引かせることが無くなるので、__人間にとってはより好ましい AI__ を作成することができます。

同様に、__引き分けの局面の最善手__ に対しても __何らかの基準で優劣をつける__ ことができます。どのような基準で優劣をつけることができるかを少し考えてみて下さい。

## 引き分けの局面での最善手の優劣の具体例

左下図の局面は引き分けの局面で、右下図はこの局面のゲーム木の部分木です。この部分木が示すように、合法手である __(2, 0)、(0, 2)、(2, 2)__ の __いずれのマスに着手を行っても__ 相手が最善手を着手すれば __引き分けになる__ ので、__3 つの合法手のすべてが最善手__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a01d6633-5bbe-f8ca-b438-20a78bd36fd1.png" width="200">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9c5723c0-910f-ec7c-a0ad-f3ac766e0738.png" width="200">

ただし、部分木からわかるように、__(2, 0) または (0, 2)__ に着手した場合は、相手が最善手を着手しなかった場合に __勝利することができます__。一方 __(2, 2)__ に着手した場合は、相手がどこに着手を行っても __必ず引き分けになります__。

従って、__相手が最善手を着手しない可能性がある場合__ は、__勝利する可能性がある (2, 0) と (0, 2)__ のほうが、(2, 2) よりも __優れた着手である__ と考えることができます。そこで、__引き分けの局面の最善手__ に対して、相手が最善手を着手しない場合に __勝利できる可能性があるか__ どうかによって __優劣をつける__ ことにします。

## 評価値の計算方法

__評価値を利用して着手を選択する AI__ が行う __[ミニマックス法](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95%E3%82%92%E8%A1%8C%E3%81%86%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%81%AE%E5%AE%9F%E8%A3%85)__ では、__〇 の手番__ では着手した局面の __評価値が最も高い合法手が最善手__ となります。そのため、〇 を着手した後の __× の手番での引き分けの局面の評価値__ を下記の式のように設定することで、〇 の手番の引き分けの局面で __〇 が勝利する可能性がある局面になる合法手が最善手となる__[^1]ようになります。

〇 が勝利できる可能性がある場合の評価値 > そうでない場合の評価値

:::note warn
ミニマックス法では __〇 の手番の局面の最善手__ を計算する際に、〇 が着手を行った後の __× の手番__ の局面の評価値を利用する点に注意して下さい。
:::

__× の手番__ では着手した局面の評価値が __最も低い__ 合法手が最善手となるので、× の手番の引き分けの局面で __× が勝利する可能性がある局面になる合法手を最善手とする__ ようにするためには、〇 の手番での引き分けの局面の評価値を下記の式のように設定する必要があります。

× が勝利できる可能性がある場合の評価値 < そうでない場合の評価値

下記は、__引き分けの局面__ に対して __そのような評価値を設定する一例__ です。上記の条件を満たしていれば、どのような評価値を設定してもかまいませんが、本記事ではこれまで __〇 の必勝の局面の評価値を 1 以上__、__× の必勝の局面の評価値を -1 以下__ として計算してきたので、それらの計算の処理を __変更しなくて済む__ ように、__引き分けの局面の評価値__ を __その間の範囲で設定__ することにしました。

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

このような評価値を計算する方法について少し考えてみて下さい。

## × の手番の局面での評価値の計算方法

まず、__× の手番の局面での評価値の計算方法__ を考えることにします。

__引き分けの局面であるか__ どうかの判定は、これまでに計算した __評価値が 0 であるか__ どうかで行うことができるので、__必要な情報__ は __〇 が勝利する可能性があるか__ どうかです。

__〇 が勝利する可能性がある__ ということは、その局面で 〇 が勝利しているか、__[子孫ノード](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%8F%8F%E7%94%BB%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85)に 〇 が勝利する局面が存在する__ ということを意味します。そのことは、以下のようなアルゴリズムで計算できます。

* __〇 が勝利する可能性があるか__ どうかを表す __評価値を計算__ する。その評価値を __〇 の勝利の評価値__ と呼ぶことにする
* __リーフノード__ の __〇 の勝利の評価値__ を、[最初にミニマックス法で評価値の計算を行う際に設定](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E3%83%AA%E3%83%BC%E3%83%95%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97)した以下の表のように計算する

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

* リーフノード以外のノードでは、__子ノードの 〇 の勝利の評価値__ の中の __最大値__ を、__自身の 〇 の勝利の評価値として計算__ する
* 上記の計算によって、自身のノードまたは __子孫ノードに 〇 が勝利する局面__ が __存在する場合__ は 〇 の勝利の評価値の値が __1__、__そうでない場合__ は __0 以下__ になる

### なるべく早く勝利する場合の評価値の計算への対応

__なるべく早く勝利__ する __`ai_gtsv`__ の評価値は、リーフノードの評価値を[以前の記事](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)で説明したように、下記の表で計算されます。ただし、引き分けの場合の評価値は 0 と計算します。

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

先程の表の評価値と、上記の表の __どちらの評価値__ に対しても __対応できるようにする__ ために、先程のアルゴリズムを下記のように修正することにします。

* 〇 が勝利する可能性があるかどうかを表す評価値を計算する。その評価値を 〇 の勝利の評価値と呼ぶことにする
* リーフノードの 〇 の勝利の評価値を以下の表のように計算する

|  | 〇 の勝利の評価値 |
|:-:|:-:|
| __〇 の勝利__ | __正の値__ |
| __引き分け__  | 0 |
| __× の勝利__  | __負の値__ |

* リーフノード以外のノードでは、子ノードの 〇 の勝利の評価値の中の最大値を、自身の 〇 の勝利の評価値として計算する
* 上記の計算によって、自身のノードまたは子孫ノードに 〇 が勝利する局面が存在する場合は 〇 の勝利の評価値の値が __正の値__、そうでない場合は 0 以下の値になる

修正前との違いは上記の（表の見出し以外の）__太字__ になっている部分だけです。

### 〇 の勝利の評価値の意味と名前の変更

__〇 の勝利の評価値__ は、子ノードに〇 が勝利する局面が存在するかどうかを判定するだけでなく、__下記についての判定を行うこともできる__ ので、〇 の勝利の評価値とは __別の名前にしたほうが良い__ でしょう。

| 〇 の勝利の評価値 | 意味 |
|:-:|:-:|
| __正の値__  | 自身または子孫ノードに 〇 の勝利の局面が存在する |
| __0__  | 自身または子孫ノードに 〇 の勝利の局面は存在しないが、<br>引き分けの局面は存在する  |
| __負の値__  | 自身または子孫ノードには × の勝利の局面しか存在しない  |

〇 の勝利の評価値は、子孫ノードの 〇 の勝利の評価値の __最大値を計算__ するので、以後は「__最大の評価値__」と表記することにします[^2]。

上記の表を別の言葉で表現すると下記の表のように、__最大の評価値__ は __〇 にとって最高でどのような結果になるか__ を表します。

| 最大の評価値 | 意味 |
|:-:|:-:|
| __正の値__  | 最高で 〇 が勝利する場合がある |
| __0__  | 最高で引き分けになる場合がある  |
| __負の値__  | 〇 が勝利する可能性はない  |

## 〇 の手番の局面での評価値の計算方法

__〇 の手番の局面での評価値の計算__ に必要な、__× が勝利するかどうかの判定__ は、上記の計算方法と同じ考え方で、下記のアルゴリズムで行うことができます。上記と異なる（表の見出し以外の）部分を太字で表記します。

* __×__ が勝利する可能性があるかどうかを表す評価値を計算する。その評価値を __最小の評価値__ と呼ぶことにする
* リーフノードの __最小の評価値__ を __先程と同じ__ 以下の表のように計算する

|  | 最小の評価値 |
|:-:|:-:|
| __〇 の勝利__  | 正の値  |
| __引き分け__  | 0  |
| __× の勝利__  | 負の値  |

* リーフノード以外のノードでは、子ノードの __最小の評価値__ の __最小値__ を、自身の __最小の評価値__ として計算する
* 上記の計算によって、自身のノードまたは子孫ノードに __×__ が勝利する局面が存在する場合は、__最小の評価値__ が __負の値__ 、そうでない場合は 0 __以上__ の値になる

上記のアルゴリズムと、先程説明した最大の評価値を計算するアルゴリズムの __大きな違い__ は子ノードの最小の評価値の __最小値__ を計算する点と、子ノードの最小の評価値が __負の場合__ に × が勝利する局面が存在する点です。従って、最大の評価値と同様に、__最小の評価値__ から下記の表の内容を判定することができます。

| 最小の評価値 | 意味 |
|:-:|:-:|
| __負の値__  | 自身または子孫ノードに × の勝利の局面が存在する |
| __0__  | 自身または子孫ノードに × の勝利の局面は存在しないが、<br>引き分けの局面は存在する  |
| __正の値__  | 自身または子孫ノードには 〇 の勝利の局面しか存在しない  |

## 最大の評価値と最小の評価値の計算

__最大の評価値__ と __最小の評価値__ は、[以前の記事](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95%E3%82%92%E8%A1%8C%E3%81%86%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%81%AE%E5%AE%9F%E8%A3%85)で説明した __ミニマックス法__ を計算する方法と __同様のアルゴリズム__ で計算できます。

ミニマックス法では各ノードの評価値を計算する方法が、__手番によって__ 子ノードの評価値の __最大値を計算するか__、__最小値を計算するか__ が __変わります__ が、__最大の評価値__ では __常に__ 子ノードの最大の評価値の __最大値を計算する__ 点が異なります。最小の評価値でも同様です。

まず、最大の評価値と最小の評価値を記録する __属性の名前を決める__ 必要があるので、それぞれ __`max_score`__ と __`min_score`__ とすることにします。

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

__リーフノード__ では、最大の評価値と最小の評価値の __計算方法__ は、__通常の評価値の計算方法と同じ__ なので、__リーフノードの評価値を計算__ する Mbtree クラスの __`calc_score_of_node`__ メソッドを下記のプログラムのように修正します。

* __11、12 行目__：`max_score` と `min_score` 属性に、4 ~ 9 行目で計算したリーフノードの評価値を代入する

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

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

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

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
    node.max_score = node.score
    node.min_score = node.score
    
Mbtree.calc_score_of_node = calc_score_of_node
```
</details>

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

```diff_python
from marubatsu import Marubatsu
from tree import Mbtree

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
+   node.max_score = node.score
+   node.min_score = node.score
    
Mbtree.calc_score_of_node = calc_score_of_node
```
</details>

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

Mbtree クラスでは、評価値の計算を幅優先アルゴリズムと深さ優先アルゴリズムの両方で行うことができるようにしているので、その両方のメソッドを修正することにします。

まず、__幅優先アルゴリズム__ で評価値の計算を行う __[`calc_score_by_bf`](https://qiita.com/ysgeso/items/3400391d2637eafc8899#calc_score_by_bf-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ （定義後の修正版のリンクは[こちら](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#calc_score_by_bf-%E3%81%A8-calc_score_by_df-%E3%81%AE%E4%BF%AE%E6%AD%A3)）メソッドを下記のプログラムのように修正します。

* __8 行目__：子ノードの `max_score` 属性を集めた list を作成し、組み込み関数 `max` を利用することで、その最大値を計算して `max_score` 属性に代入する
* __9 行目__：8 行目と同様の方法で、子ノードの `min_score` 属性の最小値を計算して `min_score` 属性に代入する

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

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

:::note
github 上の mbtree.py に記述している `calc_score_by_bf` メソッドの docstring のコメントに「深さ優先探索」という間違った記述がされていることに気が付きましたので、今回の記事から「幅優先探索」に修正します。なお、過去の記事にさかのぼって docstring を修正するのは大変な点と、プログラムのバグではないので過去の記事にさかのぼっての修正は行わないことにします。
:::

上記の修正後に、下記のプログラムを実行して __幅優先アルゴリズム__ でゲーム木の評価値を計算することで、__ルートノード__ に __`max_score`__ と __`min_score`__ 属性が __計算されている__ ことが確認できます。

```python
mbtree = Mbtree(shortest_victory=True)
print("max_score", mbtree.root.max_score)
print("min_score", mbtree.root.min_score)
```

実行結果

```
     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
max_score 3.0
min_score -2.0
```

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

次に、__深さ優先アルゴリズム__ で評価値の計算を行う __[`calc_score_by_df`](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%82%88%E3%82%8B%E5%AE%9F%E8%A3%85)__ （修正版のリンクは[こちら](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#calc_score_by_bf-%E3%81%A8-calc_score_by_df-%E3%81%AE%E4%BF%AE%E6%AD%A3)）メソッドを下記のプログラムのように修正します。

* __20 行目__：関数の返り値に、`max_score` 属性と `min_score` 属性の値を返すようにする
* __3、4 行目__：子ノードの最大の評価値と最小の評価値の一覧を記録する `max_score_list` と `min_score_list` を空の list で初期化する
* __6 ~ 9 行目__：再帰呼び出しの返り値を `score`、`max_score`、`min_score` に代入し、それぞれを `score_list`、`max_score_list`、`min_score_list` の要素に追加する
* __16、17 行目__：`max_score_list` の要素の最大値を計算して `max_score` 属性に代入する。`min_score` 属性に関しても同様の処理を行う

```python
 1  def calc_score_by_df(self, node):          
元と同じなので省略
 2          score_list = []
 3          max_score_list = []
 4          min_score_list = []
 5          for childnode in node.children:
 6              score, max_score, min_score = self.calc_score_by_df(childnode)
 7              score_list.append(score)
 8              max_score_list.append(max_score)
 9              min_score_list.append(min_score)
10              self.nodelist_by_score.append(node)
11          if node.mb.move_count % 2 == 0:
12              score = max(score_list)
13          else:
14              score = min(score_list)
15          node.score = score
16          node.max_score = max(max_score_list)
17          node.min_score = min(min_score_list)
元と同じなので省略
18      return node.score, node.max_score, node.min_score 
19
20  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 = []
        max_score_list = []
        min_score_list = []
        for childnode in node.children:
            score, max_score, min_score = self.calc_score_by_df(childnode)
            score_list.append(score)
            max_score_list.append(max_score)
            min_score_list.append(min_score)
            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
        node.max_score = max(max_score_list)
        node.min_score = min(min_score_list)
        
    self.nodelist_by_score.append(node)
    node.score_index = len(self.nodelist_by_score) - 1        
    return node.score, node.max_score, node.min_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):          
元と同じなので省略
        score_list = []
+       max_score_list = []
+       min_score_list = []
        for childnode in node.children:
-           score_list.append(self.calc_score_by_df(childnode))
+           score, max_score, min_score = self.calc_score_by_df(childnode)
+           score_list.append(score)
+           max_score_list.append(max_score)
+           min_score_list.append(min_score)
            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
+       node.max_score = max(max_score_list)
+       node.min_score = min(min_score_list)
元と同じなので省略
-   return node.score 
+   return node.score, node.max_score, node.min_score 

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

上記の修正後に、下記のプログラムを実行して __深さ優先アルゴリズム__ でゲーム木の評価値を計算することで、実行結果のようにルートノードに __`max_score`__ と __`min_score`__ 属性が計算されていることが確認できます。

```python
mbtree = Mbtree(algo="df", shortest_victory=True)
print("max_score", mbtree.root.max_score)
print("min_score", mbtree.root.min_score)
```

実行結果

```
max_score 3.0
min_score -2.0
```

## 引き分けの局面での最善手の優劣を考慮した評価値の計算

次に、今回の記事の最初で説明した下記の __引き分けの局面での最善手の優劣を考慮した評価値の計算の実装__ を行います。どのように実装すればよいかについて少し考えてみて下さい。

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

### Mbtree クラスの `calc_score_by_bf` の中で実装する方法

簡単に思いつく方法として、__評価値を計算する `calc_score_by_bf`__ や __`calc_score_by_df` の中__ で __上記の処理を行う__ という方法があるでしょう。その方法でも実装することは可能ですが、__いくつかの工夫を行わないとうまく実装できない__ という問題があります。ただし、思いつきやすい方法なので、実際に実装してどのような工夫が必要になるかを説明し、その後で別の方法で実装する方法を紹介することにします。

__`calc_score_by_bf`__ の場合は、下記のプログラムのように実装します。

* __5 ~ 11 行目__：引き分けの局面の場合の処理を記述する
* __6 ~ 8 行目__：× の手番で `max_score` の値が正の場合は、子ノードに 〇 が勝利する局面が存在するので、評価値を 0.5 に修正する
* __9 ~ 11 行目__：〇 の手番で `min_score` の値が負の場合は、子ノードに × が勝利する局面が存在するので、評価値を -0.5 に修正する

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

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

### 実装の確認

上記の修正後に下記のプログラムを実行すると、実行結果のように __ルートノード__ の __`score` 属性の値が 0.5__ である事が表示されます。__ルートノード__ は __引き分けの局面__ で、__子ノードに 〇 が勝利する局面は明らかに存在する__ ので、__正しい処理が行われているように見えます__。

```python
mbtree = Mbtree(shortest_victory=True)
print(mbtree.root.score)
```

実行結果

```
略
0.5
```

次に、__それぞれのノードでどのような評価値が計算されているか__ を __Mbtree_GUI__ クラスを利用して __視覚的に確認する__ ことにします。そのためには、__[局面と最善手・評価値の対応表のデータを作成](https://qiita.com/ysgeso/items/c4150416c994571b2803#calc_and_save_bestmoves_and_score_by_board-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9)__ する必要があるので、下記のプログラムの 1 行目のように作成し、Mbtree_GUI クラスで表示すると、実行結果のような __エラーが発生__ します。

なお、1 行目で作成されるデータは間違ったデータなので、作成したデータを保存したファイルを今後利用することはありません。そのため、ファイルの名前には適当な名前（test.dat）としました。また、2 行目で Marubatsu_GUI が作成する Dropdown の項目のラベルも適当な名前（test）としました。

```python
from tree import Mbtree_GUI

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

実行結果

```
略
File c:\Users\ys\ai\marubatsu\135\tree.py:495, in Mbtree.create_subtree(self)
    493 childmb = deepcopy(node.mb)
    494 board_str = node.mb.board_to_str()               
--> 495 x, y = bestmoves_and_score_by_board[board_str]["bestmoves"][0]
    496 childmb.move(x, y)
    497 childnode = Node(childmb, parent=node, depth=depth+1, 
    498                 bestmoves_and_score_by_board=bestmoves_and_score_by_board)   

IndexError: list index out of range
```

### エラーの原因の検証

エラーメッセージから、__`bestmoves_and_score_by_board[board_str]["bestmoves"][0]`__ の処理を行う際に、__list の範囲外（out of range）のインデックスの要素を参照__ したことがわかります。

__`bestmoves_and_score_by_board[board_str]["bestmoves"]`__ には、__`board_str`__ の局面の __最善手の一覧を表す list__ が代入されており、その中の __0 番の要素を参照__ した際にエラーが発生しているので、最善手の一覧を表す list が __空の list になっていることが推測__ されます。

そこで、__最善手の一覧を計算__ する処理を行う Mbtree クラスの __`calc_bestmove` の処理を検証__ することにします。下記は、`calc_bestmove` の定義です。__この中にバグの原因がある__ ので、どこにバグがあるかについて少し考えてみて下さい。

```python
 1  def calc_bestmoves(self, node):
 2      bestmoves = []
 3      for move, childnode in node.children_by_move.items():
 4          if node.score == childnode.score:
 5              bestmoves.append(move)
 6      node.bestmoves = bestmoves
 7
 8      key = tuple(node.mb.records)
 9      self.nodelist_by_mb[key] = node
10      self.bestmoves_by_mb[key] = bestmoves
11
12      for childnode in node.children:
13          self.calc_bestmoves(childnode)                    
```

上記の中で、__最善手の一覧を計算__ する処理は、__2 ~ 5 行目__ のプログラムで行っています。この中で、__最善手であるか__ どうかの判定は、4 行目で __自身のノード評価値__ と __子ノードの評価値__ が __等しいかどうか__ で行っています。__この判定__ がバグが発生する __原因__ です。

引き分けの局面の評価値の計算方法を修正する前では確かにこの判定方法で最善手を判定することができましたが、__修正後__ は引き分けの局面の __ノードの評価値__ が __0 から 0.5 または -0.5 に変更__ される場合があるので、自身のノードの評価値と最善手の子ノードの __評価値が一致しなくなる場合が発生します__。そのため、__この方法では正しく判定できません__。

この部分を下記のプログラムのように、__〇 の手番__ の場合は __子ノードの評価値の最大値__ を、__× の手番__ の場合は子ノードの評価値の __最小値__ を計算し、__その値と比較する__ ように修正する必要があります。

なお、__3 行目__ で __子ノードが存在する場合のみ処理を行う__ ように修正しているのは、__空の list__ を実引数に記述して __`max` または `min`__ を呼び出すと __エラーが発生する__ からです。__リーフノード__ には __子ノードが存在しない__ ので、下記のプログラムの 3 行目を記述しなかった場合は、4 行目の __`score_list` の値が空の list になる場合__ があり、6、8 行目で __エラーが発生__ します。

* __3 行目__：子ノードが存在する場合のみ処理を行うように修正する
* __4 行目__：子ノードの評価値の一覧を表す list を計算する
* __5 ～ 8 行目__：最善手の評価値として、〇 の手番の場合は子ノードの評価値の最大値を、× の手番の場合は最小値を計算する
* __10 行目__：最善手であるかどうかの判定を、上記で計算した最善手の評価値と比較することで行うように修正する

```python
 1  def calc_bestmoves(self, node):
 2      bestmoves = []
 3      if len(node.children) > 0:
 4          score_list = [childnode.score for childnode in node.children]
 5          if node.mb.move_count % 2 == 0:
 6              bestscore = max(score_list)
 7          else:
 8              bestscore = min(score_list)
 9          for move, childnode in node.children_by_move.items():
10              if bestscore == childnode.score:
11                  bestmoves.append(move)
12      node.bestmoves = bestmoves
元と同じなので省略
13               
14  Mbtree.calc_bestmoves = calc_bestmoves
```

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

```python
def calc_bestmoves(self, node):
    bestmoves = []
    if len(node.children) > 0:
        score_list = [childnode.score for childnode in node.children]
        if node.mb.move_count % 2 == 0:
            bestscore = max(score_list)
        else:
            bestscore = min(score_list)
        for move, childnode in node.children_by_move.items():
            if bestscore == childnode.score:
                bestmoves.append(move)
    node.bestmoves = bestmoves

    key = tuple(node.mb.records)
    self.nodelist_by_mb[key] = node
    self.bestmoves_by_mb[key] = bestmoves

    for childnode in node.children:
        self.calc_bestmoves(childnode)                    
                
Mbtree.calc_bestmoves = calc_bestmoves
```
</details>

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

```diff_python
def calc_bestmoves(self, node):
    bestmoves = []
-   for move, childnode in node.children_by_move.items():
-       if node.score == childnode.score:
-           bestmoves.append(move)
+   if len(node.children) > 0:
+       score_list = [childnode.score for childnode in node.children]
+       if node.mb.move_count % 2 == 0:
+           bestscore = max(score_list)
+       else:
+           bestscore = min(score_list)
+       for move, childnode in node.children_by_move.items():
+           if bestscore == childnode.score:
+               bestmoves.append(move)
    node.bestmoves = bestmoves
元と同じなので省略
                
Mbtree.calc_bestmoves = calc_bestmoves
```
</details>

上記の修正後に下記のプログラムでゲーム木を計算しなおして、Mbtree_GUI を実行すると、実行結果のように評価値として 0.5 が計算される __引き分けの局面のノードの色__ が、__〇 の必勝の局面を表す水色で表示__ されるという __問題が発生している__ ことがわかります。このようなことが起きる原因について少し考えてみて下さい。

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

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/77e1d29e-e075-20ef-cde9-451f9a4d6e41.png" width="500">

### ノードの色の表示のバグの検証と修正

この問題は、__ノードを表示__ する __Marubatsu_GUI__ クラスの __`draw_board`__ メソッドの中で、下記のプログラムの 7 ~ 12 行目のように __ゲーム盤の背景色の計算__ を __評価値が正、0、負を判定する条件式__ で行っているからです。

```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 is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
 8              bgcolor = "lightcyan"
 9          elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
10              bgcolor = "lavenderblush"
11          else:
12              bgcolor = "lightyellow"  
略
```

__引き分けの局面__ の評価値に __優劣をつける__ 場合は、引き分けの局面の評価値が __範囲を持つようにする__ 必要があります。そこで、本記事では、現状の評価値の計算方法にあわせて、__-1 < 評価値 < 1__ の場合に、引き分けの局面である事を表すようにすることにします。下記はそのように __`draw_board`__ メソッドを修正したプログラムです。

* __10 行目__：評価値が 1 以上の場合に 〇 の必勝の局面であることを判定するように修正する
* __12 行目__：評価値が -1 以下の場合に × の必勝の局面であることを判定するように修正する

```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, bc=None, bw=1, darkness=0, 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 is not None and score >= 1) or mb.status == Marubatsu.CIRCLE:
11              bgcolor = "lightcyan"
12          elif (score is not None and score <= -1) or mb.status == Marubatsu.CROSS:
13              bgcolor = "lavenderblush"
14          else:
15              bgcolor = "lightyellow"      
元と同じなので省略
16
17  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, 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 is not None and score >= 1) or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
        elif (score is not None and 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)

    # ゲーム盤の枠を描画する
    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
from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches

@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 is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
+       elif (score is not None and score >= 1) or mb.status == Marubatsu.CIRCLE:
            bgcolor = "lightcyan"
-       elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
+       elif (score is not None and score <= -1) or mb.status == Marubatsu.CROSS:
            bgcolor = "lavenderblush"
        else:
            bgcolor = "lightyellow"      
元と同じなので省略

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

上記の修正後に下記のプログラムを実行すると、実行結果のように引き分けの局面の色が正しく表示されるようになりますが、深さが 2、4、6 の __〇 の手番の引き分けの局面__ に __0.5 という評価値が計算__ されていることがわかります。先ほど説明した評価値の計算では、__〇 の手番の引き分けの局面__ の評価値は __0 または -0.5__ のいずれかになるので、__この評価値は間違っています__。

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

実行結果

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

また、上図の深さ 5 の × の手番の一番上のノードをクリックすると下図のような部分木が表示されます[^3]。図から、__(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">

次回の記事では、このバグを修正することにします。何がバグの原因かについて余裕がある方は考えてみて下さい。

# 今回の記事のまとめ

今回の記事では、__引き分けの局面__ での __最善手の優劣__ について説明し、そのような評価値を計算するために必要な __最大の評価値と最小の評価値の計算__ を実装しました。

また、それらの値を利用して __引き分けの局面__ で __勝利できる可能性がある合法手__ を __最善手として計算する__ ための実装を開始しました。ただし、現状の実装にはバグが存在するので、次回の記事でそのバグを修正します。

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

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

# 次回の記事

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

[^1]:もちろん、〇 が勝利する可能性が存在しない場合は除きます
[^2]:評価値の最大値という表現は、子ノードの評価値の最大値のように別の意味で利用しているので、「最大の評価値」という表現にしました
[^3]:部分木全体を表示すると画像が大きくなるので、そのノードとそのノードの子ノードの範囲の図としました