Pythonで〇×ゲームのAIを一から作成する　その146　αβ 法のまとめとMbtree_Anim を利用した αβ 法の処理の確認

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/741c2c18f0bc6fcdba27

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

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

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

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

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

# 今回の記事の内容

__αβ 法__ は __かなりわかりづらい__ アルゴリズムです。[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9)で αβ 法について説明しましたが、Mbtree_Anim の実装がかなり長くなってしまったため、αβ 法について忘れてしまった方が多いのではないかと思いますので __おさらい__ と __まとめ__ をすることにします。また、__ちゃんと説明していない点がある__ 事に気が付きましたのでその説明を行うことにします。

前回までの記事で αβ 法で評価値を計算する手順をアニーメーションで視覚化するための __Mbtree_Anim を改良__ してきたのは、αβ 法で行われる __処理を視覚化__ することで __わかりやすく確認できる__ ようにするためです。今回の記事では αβ 法のおさらいとまとめを行った後で、__Mbtree_Anim__ を使って __αβ 法で行われる処理を視覚的に確認する__ ことにします。

## 用語の定義

__αβ 法__ では __評価値を計算したいノード__ を __ルートノード__ とするゲーム木の __部分木のノードに対する計算__ を行います。そこで、本記事では以後は __αβ 法で評価値を計算したいノード__ の事を単に __ルートノード__ と表記することにします。

# αβ 法のおさらいとまとめ

__αβ 法__ は __ミニマックス法を改良__ したアルゴリズムです。具体的には[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9)で説明した[下記のような処理](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E7%A5%96%E5%85%88%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F-%CE%B1%CE%B2-%E6%B3%95)を行うアルゴリズムで、__枝狩り__ によって __一部のノードの処理を省略する__ ことで __処理時間を短くする__ という改良を行っています。

:::note warn
__αβ__ 法は、__ミニマックス法で評価値を計算する際__ に、下記の手順で __α 狩り__ と __β 狩り__ を行うアルゴリズムである。また、__αβ 法__ で求められる評価値は、__ミニマックス法__ で求められる評価値と __常に同じ__ になるので、__最適解__ の評価値を __ミニマックス法より短い時間__ で __求めることができる__。

* __min ノード__ では、下記の手順で __α 狩り__ を行う
    * __祖先ノード__ の中の __max ノード__ をすべて探す
    * 探した max ノードの中で、__評価値が計算済__ の __子ノードの評価値の最大値を α__ とする
    * 子ノードの中で __α 以下__ の評価値が __計算された時点__ で __残りの子ノードの評価値の計算を省略__ する
* __max ノード__ では、下記の手順で __β 狩り__ を行う
    * __祖先ノード__ の中の __min ノード__ をすべて探す
    * 探した min ノードの中で、__評価値が計算済__ の __子ノードの評価値の最小値を β__ とする
    * 子ノードの中で __β 以上__ の評価値が __計算された時点__ で __残りの子ノードの評価値の計算を省略__ する
:::

また、[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E5%AE%9F%E8%A3%85)で説明したように、上記の __αβ 法を実装__ する __`ai_abs`__ や Mbtree クラスの __`calc_score_by_ab`__ メソッドでは下記のような処理を行っています。

* __min ノード__
    * __親ノードの β 値を初期値__ として子ノードの評価値の __最小値__ の計算を行う
    * __β 値__ を計算した __最小値で更新__ する。その結果 __β 値が min ノードの評価値__ となる
    * __祖先ノードの max ノード__ の中の __α 値の最大値__ を利用して __α 狩り__ を行う
* __max ノード__
    * __親ノードの α 値を初期値__ として、子ノードの評価値の __最大値__ の計算を行う
    * __α 値__ を計算した __最大値で更新__ する。その結果 __α 値が max ノードの評価値__ となる
    * __祖先ノードの min ノード__ の中の __β 値の最小値__ を利用して __β 狩り__ を行う
* __親ノードの α 値と β 値を子ノードの処理に伝える__

## αβ 法とミニマックス法の違い

αβ 法とミニマックス法と __比較するため__ に、下記にミニマックス法で行う処理を示します。

* __min ノード__
    * 子ノードの評価値の最小値の計算を行う
* __max ノード__
    * 子ノードの評価値の最大値の計算を行う

__αβ 法__ は以下の 4 点が __ミニマックス法と異なります__。__この 4 つの処理__ の意味が __直観的にわかりづらい__ ことが αβ 法がわかりづらい理由だと思います。

1. __α 値や β 値を初期値__ として子ノードの評価値の最小値や最大値の計算を行う
2. α 値や β 値を上記の __1 で計算した値で更新__ し、__そのノードの評価値とする__
3. __α 狩りと β 狩り__ に関する処理を行う
4. __α 値と β 値__ を __子ノードの処理に伝える__

上記のうちの __1、2、4__ については、[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E7%A5%96%E5%85%88%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F-%CE%B1-%E7%8B%A9%E3%82%8A%E3%81%A8%CE%B2-%E7%8B%A9%E3%82%8A%E3%81%AE%E5%AE%9F%E8%A3%85)で説明したように __子ノードに祖先ノードの__ max ノードの子ノードの評価値の最大値と、min ノードの子ノードの評価値の最小値を __伝えるため__ に行っています。簡単にまとめると下記の理由で __子ノードに伝えられた α 値__ には __祖先ノードの max ノード__ で計算された子ノードの __評価値の最大値が代入__ されます。β 値に関しても同様です。

* α 値の初期値は負の無限大である
* __α 値__ は __max ノードでのみ更新__ される
* __max ノード__ では __子ノードの評価値が α 値より大きい場合__ に α 値を __その値で更新__ する
* α 値は子ノードの評価値を計算する際に、__そのままの値__ が子ノードの処理に __伝えられる__
* 従って α 値には __max ノード__ で計算された子ノードの __評価値の中の最大値が記録__ される

上記の 3 の __α 狩りと β 狩り__ を行って良い理由については[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF)で詳しく説明したので忘れた方はそちらを復習して下さい。min ノードで __α 狩りを行って良い理由__ を簡単にまとめると以下のようになります。β 狩りについても同様です。

* __min ノード__ で計算した子ノードの評価値が __α 値以下になった場合__ は、__そのノードの評価値が α 以下__ になることが確定する
* [以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF)で説明した理由から、min ノードの評価値が α 以下の場合は __祖先ノードの max ノードの評価値の計算__ に __影響を与えない__
* αβ 法で __評価値を求めたいノード__ は __最も祖先のノード__ である __ルートノード__ である
* αβ 法では __子ノードの評価値を利用__ して __親ノードの評価値を計算__ するので、min ノードの評価値が α 以下の場合は __ルートノードの評価値に影響を与えない__
* 従って、min ノードで計算した子ノードの評価値が α 値以下になった時点で __残りの子ノードの評価値の計算__ を行う __意味がなくなる__ ので、α 狩りを行っても良い

## α 値や β 値を初期値として計算を行って良い理由

ところで、__α 値や β 値を初期値__ として __子ノードの評価値を計算__ する点に __疑問を感じた人__ はいないでしょうか？

__max ノード__ の子ノードの評価値の __最大値を M__ とした場合に、__α < M__ であれば __α 値は M に更新される__ ため、max ノードの評価値として __ミニマックス法と同様__ に子ノードの評価値の最大値である __M が計算__ されます。なお、__α = M__ の場合は α 値は更新されませんが、ミニマックス法と __同じ値である M が計算__ されます。

一方、そうでない __M < α__ の場合は __α 値は更新されない__ ため、__αβ 法__ で max ノードの評価値として計算された __α 値と__、ミニマックス法の場合に計算される max ノードの子ノードの評価値の最大値である __M が異なる__ ことになってしまいます。

例えば __max ノード__ で親ノードから伝えられた __α 値が 0 の場合__ で、__全ての子ノードの評価値が -1__ の場合は、__そのノードの評価値__ は __ミニマックス法__ では __-1 が計算__ されますが、__αβ 法では__  α 値を初期値として計算するため __0 が計算__ されます。具体例についてはこの後で Mbtree_Anim を利用して図で示すので[こちらのリンク先](#max-ノードですべての子ノードの評価値が-α-未満の場合)を見て下さい。

このことから、__αβ 法__ ではすべてのノードで正しい評価値を計算するミニマックス法と異なり、__正しくない評価値が計算__ される __ノードが存在する可能性がある__ ことがわかります。

従って、__αβ 法__ を利用する際には __下記の性質がある点に注意する必要__ があります。

:::note warn
__αβ 法__ で評価値を求めた際に、__ルートノード以外のノード__ では __正しい評価値が計算されない場合がある__。
:::

正しくない評価値が計算されるノードが存在するにも関わらず、αβ 法では __ルートノードの評価値は常に正しい値が計算__ されます。その理由について少し考えてみて下さい。

__α 値と β 値の性質は正反対__ です。従って、α 値を初期値としても良い理由と、β 値を初期値としても良い __理由はほぼ同じ__ なので max ノードで α 値を初期値としても良い理由についてのみ説明することにします。

### ルートノードの場合

評価値を計算するルートノードでは、[__α 値は負の無限大__、__β 値は正の無限大__](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1-%E5%80%A4%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85)になります。従って、__ルートノード__ が max ノードの場合は __ミニマックス法と同様__ に必ず子ノードの評価値の最大値が計算されるので、ルートノードの評価値は __ミニマックス法の評価値と同じになります__。ルートノードが min ノードの場合も同様です。

### ルートノード以外の場合

__max ノード__ の子ノードの評価値の __本当の最大値を M__ と表記した場合に、__max ノードの評価値__ が αβ 法とミニマックス法で __異なる__ のは、先程説明したように __M < α__ の場合です。

その場合は、__max ノードの評価値__ として __α 値__ と __M__ の __どちらをを計算しても__ 以下の理由から __ルートノードの評価値の計算に影響を与えません__。これが α 値を初期値として max ノードの子ノードの評価値の最大値を計算しても __問題がない理由__ です。

* max ノードの __親ノード__ は子ノードの評価値の __最小値を計算する min ノード__ である
* 従って、__max ノードの評価値の計算結果__ が親ノードから伝えられた __α 値以下__ の場合は、__親ノードである min ノードの評価値__ が必ず __α 値以下__ になる
* その場合は、__親ノードで α 狩りが行われる__ ため __ルートノードの評価値に影響を与えない__
* __M < α__ なので、max ノードの評価値として __α 値 と M の どちらをを計算しても__ ルートノードの評価値に __影響を与えない__

また、max ノードの評価値として α 値と M のどちらを計算しても構わないにも関わらず、実際には __α 値を初期値として評価値を計算する理由__ は以下の通りです。

* max ノードの子ノードの評価値の最大値である __M を求めるため__ には __初期値を負の無限大__ とする、α 値を記録する変数とは __別の変数を用意する必要__ がある
* max ノードの子ノードの評価値を求める際に、子ノードに伝えるのはそれまでに計算した __その max ノードだけ__ の子ノードの評価値の __最大値ではなく__、__祖先ノードの max ノードも含めた__ max ノードの子ノードの評価値の最大値である __α 値__ のほうである
* 従って __α 値を初期値として計算する必要がある__ 
* 一方、max ノードの評価しとして α 値と M のどちらを計算しても __ルートノードの評価値の計算結果は変わらない__ ので、わざわざ __M を計算する必要なない__

## α 値と β 値の意味

[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1-%E5%80%A4%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E6%84%8F%E5%91%B3)で α 値と β 値の意味を下記のように説明しました。

α 値と β 値 は、ミニマックス法でそれぞれのノードの評価値を計算する際に、そのノードの評価値が __最終的に求める評価値__ に __影響を与える可能性がない__ ことを表す __子ノードの評価値の範囲__ を表す。

今回の記事の内容を踏まえて __もう少し詳しく説明__ すると以下のようになります。

:::note warn
* α 値と β 値は、__子ノードの評価値__ が __α 値以下または β 値以上__ の場合に __ルートノードの評価値に影響を与えない__ ことを表す値である。従って、子ノードの評価値がその範囲で計算された場合は、その子ノードの評価値は __無視しても構わない__
* 逆に言えば、子ノードの評価値が __α 値と β 値の間__ にある場合は、__ルートノードの評価値に影響を与える可能性がある__ ため __無視することができない__ ことを意味する。ただし、__必ず影響を与えるとは限らない__[^1]点に注意が必要である
* __α 値以下__ と、__β 値以上__ はいずれもルートノードの評価値に __影響を与えない範囲__ であるが、以下の点で __その意味が異なる__
* __max ノード__ では子ノードの評価値の __最大値を求める__ ため、子ノードの評価値が __α 値以下__ になった場合に __無視して良いのはその子ノードの評価値だけ__ である。従って、残りの子ノードの評価値の計算を __省略することはできない__
* 一方 max ノードで子ノードの評価値が __β 以上__ になった場合はそのノードの評価値が __β 以上になることが確定__ するので、残りの子ノードの評価値の __計算を省略__ するという __β 狩りを行うことができる__
* min ノードでは α 値と β 値が逆になる点を除いて同様である
:::

# Mbtree_Anim を利用した αβ 法の処理の確認

上記のような __言葉での説明だけではわかりづらい__ と思いますので、__Mbtree_Anim__ を利用して αβ 法が行う処理を __視覚化して確認する__ ことにします。

αβ 法は __深さ優先アルゴリズム__ で処理を行うため、行う処理は下記の __3 種類に分類__ されるので、それぞれで行われる処理について、__Mbtree_Anim__ を利用して確認します。

* 次の子ノードの評価値を計算する処理を開始する
* 子ノードの評価値が得られた際に、その評価値の値に応じて α 値または β 値の更新、枝狩り、評価値の確定などの処理を行う
* 自身のノードの評価値が確定した際に、その評価値を親ノードに伝える

## 次の子ノードの評価値を計算する処理の開始の確認

αβ 法では、__子ノードの評価値を計算する処理__ を開始する際に、それまでに計算した __α 値と β 値を子ノードの処理に伝える__ 必要があります。そこで、__その処理が行われていること__ を __Mbtree_Anim で確認__ することにします。

なお、前回の記事までは __決着がついた局面の評価値__ として __-1 ~ 1 の範囲を計算__ していましたが、__評価値の範囲を広げたほうがわかりやすくなる__ と思いましたので、今回の記事では[以前の記事](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f)で紹介した __できるだけ早く勝利する着手を行う__ 以下の表のように __[-2 ~ 3 の範囲](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95%E3%81%AE%E5%A4%89%E6%9B%B4)__ で決着がついた局面の評価値を計算することにします。

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

αβ 法で評価値を計算する __`calc_score_by_ab`__ では、__決着がついた局面の評価値__ を下記の __[`calc_score_of_node`](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#calc_score_of_node-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9)__ メソッドで計算しており、このメソッドでは 3、7 行目のように、__`shortest_victory` 属性が `True`__ の場合に上記の表の評価値を計算します。

```python
 1  def calc_score_of_node(self, node: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      node.max_score = node.score
 9      node.min_score = node.score
```

従って、下記のプログラムを実行することで、上記の表の評価値で αβ 法による評価値を計算することができます。

```python
from tree import Mbtree, Mbtree_Anim

mbtree = Mbtree(algo="df", shortest_victory=True)
mbtree.calc_score_by_ab(mbtree.root)
Mbtree_Anim(mbtree, isscore=True)
```

### ルートノードからの処理の確認

まず、__ルートノードの最初の子ノード__ の評価値を計算する処理を開始する際の __α 値と β 値を確認__ します。

下図左は __ルートノードの処理が開始__ された 0 フレーム目、下図右はその __最初の子ノードの処理が開始__ された 1 フレーム目の図です。__αβ 法の処理が開始__ された時点では __α 値は負の無限大__、__β 値は正の無限大__ で、子ノードの処理が開始された際に __α 値と β 値が変化せずにそのまま伝わっている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/524d14e8-51fe-5dfc-5891-32712039be1d.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ffd1b386-b2f3-124b-9d1d-377cf65f9fee.png" width="300">　

下図はその後の 2 フレーム目、3 フレーム目の図です。αβ 法は __深さ優先アルゴリズム__ なので、__次々に最初の子ノードの処理が開始__ されていますが、その際にいずれも __α 値と β 値がが変化せずにそのまま伝わっている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d732187c-8c04-d6e4-7987-e8b57a47e56d.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a2d70bf4-e3d6-901a-3227-5cc224cd2e2b.png" width="300">　

### 他のノードでの確認

下図は赤枠の最初の子ノードの評価値を計算した結果 __α 値が 2 に更新__ された 10 フレーム目の図と、赤枠の __次の子ノードの処理が開始__ された 11 フレーム目の図です。この場合でも、__α 値と β 値がが変化せずにそのまま伝わっている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6aa16e2b-e29a-8c57-a89b-5d150cd4cddd.png" width="500">
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/96581713-d4de-29ba-be36-30b1c18903a4.png" width="500">

下図は赤枠のノードの __α 値が 0、β 値が 2__ の場合の 50 フレーム目の図と、赤枠の __次の子ノードの処理が開始__ された 51 フレーム目の図です。この場合でも、__α 値と β 値がが変化せずにそのまま伝わっている__ ことが確認できます。

なお、上図と下図の両方で共通しますが、min ノードと max ノードで __枝狩りを行う範囲__ が α 値以下と、β 値以上で __異なる__ ので、__水色と灰色の部分が前後の図で入れ替わります__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e87ac9cc-4a45-b5b9-e59f-1594c13ed2a5.png" width="500">
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/619750e2-ac09-6c85-ba12-b7cdadf3777e.png" width="500">

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

:::note warn
αβ 法で、__次の子ノードの評価値を計算する処理を開始__ する際には、__α 値と β 値__ は変化せずに __そのまま子ノードの処理に伝えられる__。
:::

## 評価値を親ノードに伝える処理の確認

先に比較的簡単に説明できる、自身のノードの評価値が確定した際にその __評価値を親ノードに伝える処理の確認__ を行います。

下図左は赤枠のノードの __評価値が確定__ した 11150 フレーム目、下図右はその __評価値が親ノードに伝わった__ 11151 フレーム目の図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8d20f0f9-2154-19f0-5f5d-56c8a1adccfc.png" width="314">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ab9cc9e4-1807-8afc-75ad-8b36dee41250.png" width="300">

__左図の β 値__ が __右図では score__ になり、__β 値が負の無限大に変化__ しています。α 値と β 値は、親ノードから子ノードにそのまま受け継がれるので、お互いのノードが __α 値と β 値を共有しているように見えるため__、上記のように __β 値が変化する点に戸惑う__ 人がいるかもしれませんが、以下のような理由で β 値が変化します。

* __α 値と β 値__ は __それぞれのノードが独自に持つ値__ であり、特定のノードの α 値や β 値を変更しても、__他のノードの α 値や β 値が変更されることはない__
* 従って、子ノードの処理によって __子ノードの α 値や β 値を変更__ しても、__親ノードの α 値や β 値の値__ は __変更されない__

左図の β 値は赤枠のノードの評価値を計算した結果 0 に更新された値で、その更新によって __親ノードの β 値が直接更新されることはありません__[^2]。右図の β 値は左図の赤枠のノードの評価値を計算する処理が行われる前の値です。

:::note warn
__α 値と β 値__ の値は、それぞれのノードで __独立して記録__ されている。そのため、子ノードの α 値や β 値の更新は、親ノードの α 値や β 値に __直接影響を与えない__。
:::

## 子ノードの評価値が得られた場合の処理の確認

__max ノード__ で子ノードの評価値が得られた場合に行われる処理は「__β 狩り__ が行われる」、「β 狩りが行われずに __α 値が更新される__」、「__α 値が更新されない__」の 3 種類なので、それぞれの処理確認することにします。なお、max ノードと min ノードで行われる処理は良く似ているので、max ノードでの処理の説明を詳しく行います。

### max ノードで枝狩りが行われずに α 値が更新される場合

まず、max ノードの評価値を計算する際に、__枝狩りが行われず__ に __α 値が更新される__ 場合の処理を確認します。下図の 2 フレーム目の __赤枠のノードは max ノード__ です。この時点では赤枠の __祖先ノード__ の max ノードと min ノードの中で __評価値が計算されている子ノードは存在しない__ ので [__α 値は負の無限大__、__β 値は正の無限大__](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1-%E5%80%A4%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85) になっています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/082c54f5-2db3-a925-a5c9-d392716894bf.png" width="300">

[前回の記事](https://qiita.com/ysgeso/items/741c2c18f0bc6fcdba27#mbtree_anim-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-create_widgets-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3)で作成した > ボタンなどで赤枠のノードに対する処理が行われたフレームを表示し、__それぞれのフレームの α 値と β 値の図__ を __順に並べる__ と以下の表ようになります。

|  | α 値と β 値の図 |
|:-:|:--|
| 開始時  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7414b51e-4482-ad04-8269-d75dd7f33b5e.png" width="350"> |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/128a93c1-6b44-a0dc-ecea-21c3e8faaa5d.png" width="50">  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/10ce14e5-3266-8fa0-53f4-cc7cd6465f60.png" width="350">  |
| α 値の更新[^3]  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ce8728f6-0c33-2bcb-2343-e7a6c579b3bf.png" width="350">  |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a8cdc1f2-31a3-378d-bbf3-84c6a86326ca.png" width="50">  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/feba2d35-bc2a-c17d-9867-41172790b07f.png" width="350">  |
| α 値の更新  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0f11ef44-009d-5319-7ce0-851b1b128bb9.png" width="350">  |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/aa5d30e5-0ac4-4a11-dd2e-fd913d409f97.png" width="50">  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/549f8d61-7dc9-c37d-50f1-7f4149f023a5.png" width="350">  |
| α 値の更新なし  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1eedbdeb-fd47-6d4b-a434-c3a31138dd78.png" width="350">  |
| | 4 ~ 7 番目の子ノードの評価値はいずれも 2 で<br>上記と同じで α 値の更新は行われないので省略 |
| 評価値の確定 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4dab9fa2-0f7c-ee05-4211-d25066c305a9.png" width="350">  |

__max ノード__ の評価値を計算する際に、__β 狩りが行われず__ に __α 値が更新される__ 場合は、上記の表から以下のような計算が行われることがわかります。

* __α 値__ には __子ノードの評価値__ のうちの __最大値が計算__ されるので、__α 値__ にはミニマックス法と同様に __max ノードの評価値が計算__ される
* __β 値__ は __変更されない__

そのことは上図で __α 値__ が __左から右に更新されていく様子__ から確認することができます。

:::note
図は省略しますが、__min ノード__ では __β 値が更新される場合__ は、必ず __右から左に更新__ されます。興味がある方は Mbtree_Anim で実際に確認してみて下さい。
:::

なお、上記では処理を開始する際の α 値と β 値の初期値はそれぞれ負の無限大と正の無限大ですが、__α 値と β 値の初期値が別の値__ であっても、__上記と同じ__ ことが言えます。

さらに、__α 値の更新が行われない場合__ でも、__α 値と同じ値の評価値__ の子ノードが __存在した場合__ は、__α 値__ が子ノードの評価値の __最大値となる__ ので __上記と同じ__ ことが言えます。

上記をまとめると以下のようになります。

:::note warn
__max ノード__ では以下の条件が満たされる場合は、αβ 法によって計算される __α 値__ はミニマックス法が計算する子ノードの __評価値の最大値と同じ値__ になる。

* __子ノードの評価値の最大値__ が __α 以上 β 未満__ である
:::

### max ノードですべての子ノードの評価値が α 未満の場合

下図は赤枠のノードの評価値の計算を開始するフレームの図で、__α 値の初期値は 0__、__β 値の初期値は正の無限大__ になっています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d9fdccc8-fc34-617f-2e51-4570ce1a5060.png" width="500">

上図の赤枠のノードに対する処理が行われたそれぞれのフレームの α 値と β 値の図を順に並べると以下の表のようになります。

|  | α 値と β 値の図 |
|:-:|:--|
| 開始時  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5b74e358-251e-520e-28e2-3edb209b6c27.png" width="350"> |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3dda4232-a61e-266e-6cbd-7d569ecc762a.png" width="50">  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/34a953a3-c7cd-914b-b36d-36c84c122ab5.png" width="350">  |
| α 値の更新なし  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4d24c0b2-e28f-3318-1cbc-b512b806f565.png" width="350">  |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d2cfa025-2804-83d5-67ce-9ceca6f9d693.png" width="50"><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c0feae4b-bf5e-991a-0f8c-6d3adc61f212.png" width="52">| 2、3 番目の子ノードの評価値はいずれも -1 で<br> 上記と同じ図になるので省略 |
| 評価値の確定 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/22d48888-3c08-2f65-f1ed-6bb2357bb1be.png" width="350">  |

上記の場合は、子ノードの __評価値の最大値は -1__ になるため、__ミニマックス法__ では赤枠のノードの __評価値は -1__ になりますが、__αβ 法__ では __α 値が max ノードの評価値として計算__ されるので赤枠のノードの __評価値は 0__ になります。[先程説明](#α-値や-β-値を初期値として計算を行って良い理由)したように、__max ノード__ の __すべての子ノードの評価値__ が __α 値よりも小さい場合__ は、__αβ 法で計算した評価値 α__ はそのノードの __本当の評価値より大きな、異なる値__ になることが実際に確認できました。

このような場合でも __ルートノードの評価値が正しく計算される理由__ については、[先程説明](#α-値や-β-値を初期値として計算を行って良い理由)した通りです。

### β 狩りが行われる場合

下図は赤枠のノードの評価値の計算を開始するフレームの図で、__α 値の初期値__ は __負の無限大__、__β 値の初期値__ は __2__ になっています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/10d832a8-48e2-5e91-540c-81d100401e60.png" width="500">

上図の赤枠のノードに対する処理が行われたそれぞれのフレームの α 値と β 値の図を順に並べると以下のようになります。

|  | α 値と β 値の図 |
|:-:|:--|
| 開始時  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6dbd7e7e-e9bb-5049-b130-25fec11b89f2.png" width="350"> |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5801c9e8-591f-2414-03f8-d7a1fe73d458.png" width="50">  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7d6e682e-e078-6398-cd1f-75f19c131a66.png" width="350">  |
| α 値の更新  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3ae7a74c-57c7-fb30-94b6-d583069add44.png" width="350">  |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d8294b41-da5b-22ab-0667-ddfe30124404.png" width="50">|  <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6b7bd6ff-2f23-200f-a766-1f448376db4c.png" width="350">  |
| β 狩り | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1fcb8699-a182-08e2-87f1-3d5e6fbd9b4d.png" width="350">  |
| 評価値の確定 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6536ad2a-ba5f-6b43-522a-d7c1e0023589.png" width="350">  |

下図は β 狩りが行われた結果、枝狩りが行われたノードが暗い色で描画されるようになった図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b18d7837-c860-e065-0a26-29e089af83e3.png" width="500">

max ノードの __親ノードは min__ ノードで、min ノードでは __子ノードの評価値が β 値よりも小さい場合に更新する__ ので、__β 値以上である α 値__ を max ノードの __評価値として計算しても__、親ノードである min ノードではその値は __β 値の更新には使われません__。

β 狩りを行っても良い理由についてのより詳しい説明は、[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF)を復習して下さい。

## max ノードと min ノードで行われる処理のまとめ

max ノードで行われる処理は、__大きくなるという条件__ で __α 値__ を __子ノードの評価値の値で更新__ し、__β 値以上__ になった時点で __β 狩りを行う__ というものです。

また、α 値と β 値の図で __色分けされた評価値の範囲の性質__ は以下のようになります

* __灰色の範囲__ は __祖先ノードの max ノード__ の評価値である __α 値の計算__ に __影響を与えない__ ため、ルートノードの評価値に影響を与えないので __無視して良い__ 範囲
* __黄色の部分__ は祖先ノードの max ノードの評価値の計算に __影響を与える可能性がある範囲__
* __水色の部分__ は __親ノードの min ノード__ の評価値である β 値の計算に __影響を与えないことが確定__ するため、__それ以降__ の子ノードの評価値の計算を __省略して良い範囲__

__min ノード__ は max ノードと __正反対の性質を持つ__ ため、行われる処理も __max での処理の反対__ です。そのため、図を用いた説明は省略し、処理のまとめのみを以下に説明します。興味がある方は、Mbtree_Anim を利用して min ノードで行われる処理を確認してみて下さい。

min ノードで行われる処理は、__β 値が小さくなる__ ように子ノードの評価値の値で __更新__ し、__α 値以上__ になった時点で __α 狩りを行う__ というものです。

また、α 値と β 値の図で __色分けされた評価値の範囲の性質__ は __max ノードと同様__ です。

## αβ 法で行われる処理のまとめ

__Mbtree_Anim__ で行われる処理を __観察する__ ことで、αβ 法では、__子ノードの評価値を計算するたび__ に、__α 値と β 値の図の範囲__ によって以下の処理を行うことが確認できます。また、この表から、__α 値と β 値__ は __ルートノード__ の評価値に対して __3 種類の影響__ を与える子ノードの評価値の __範囲の境目__ を表していることがわかります。

| 範囲 | 意味 |
|:--|:--|
| __灰色__  | その子ノードの評価値が、__ルートノードの評価値の計算__ に __影響を与えない範囲__。__残りの__ 子ノードの評価値の __計算は続行__ する |
| __黄色__  | その子ノードの評価値が、ルートノードの評価値の計算に __影響を与える可能性がある範囲__。α 値または β 値を更新して __黄色の範囲を狭め__、__残り__ の子ノードの評価値の __計算を続行__ する|
| __水色__  | __その子ノードと残りの子ノード__ の評価値が、ルートノードの評価値の計算に __影響を与えない範囲__。__枝狩りを行って__ 残りの子ノードの評価値の __計算を省略する__  | 

また、__上記の範囲に注目__ することで、α 値と β 値が以下のような性質を持つことが観察できました。

* α 値と β 値は __子ノードの評価値を計算する際__ に、__そのまま受け継がれる__
* __α 値__ は __max ノード__ では __黄色い範囲を狭める__ ように図では __右方向に増加__ するか、__変化しない__ という性質がある
* __α 値が増える__ と、__子孫ノードの min ノードで α 狩り__ を行う __水色の範囲が増える__
* __α 値__ は __min ノード__ では __変化しない__
* __β 値__ は __min ノード__ では __黄色い範囲を狭める__ ように図では __左方向に減少__ するか、__変化しない__ という性質がある
* __β 値が減る__ と、__子孫ノードの max ノードで β 狩り__ を行う __水色の範囲が増える__
* __β 値__ は __max ノード__ では __変化しない__

このことから、__祖先ノード__ で __子ノードの評価値が多く計算されるほど__、その __評価値の情報によって__ 枝狩りを行う __水色の範囲が広がっていく__ ことになるため、__枝狩りが行われやすくなる__ ことがわかります。

例えば、今回の記事の最初で行った、[ルートノードからの処理の確認](#ルートノードからの処理の確認)では、__子ノードの評価値が全く計算されない__ ため、__α 値と β 値は変化しません__。

一方、__子ノードの評価値が計算__ されると __α 値と β 値が更新__ され、__黄色の範囲が狭まる__ ことで、__子ノードでの枝狩りが行われやすく__ なります。例えば、今回の記事の [max ノードで枝狩りが行われずに α 値が更新される場合](#max-%E3%83%8E%E3%83%BC%E3%83%89%E3%81%A7%E6%9E%9D%E7%8B%A9%E3%82%8A%E3%81%8C%E8%A1%8C%E3%82%8F%E3%82%8C%E3%81%9A%E3%81%AB-%CE%B1-%E5%80%A4%E3%81%8C%E6%9B%B4%E6%96%B0%E3%81%95%E3%82%8C%E3%82%8B%E5%A0%B4%E5%90%88)では、下記の表のように 1 つ目と 2 つ目の子ノードの評価値が計算されると __α 値が右方向に更新__ されて __黄色の範囲が狭くなります__。

|  | α 値と β 値の図 |
|:-:|:--|
| 開始時  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7414b51e-4482-ad04-8269-d75dd7f33b5e.png" width="350"> |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/128a93c1-6b44-a0dc-ecea-21c3e8faaa5d.png" width="50">  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/10ce14e5-3266-8fa0-53f4-cc7cd6465f60.png" width="350">  |
| α 値の更新  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ce8728f6-0c33-2bcb-2343-e7a6c579b3bf.png" width="350">  |
| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a8cdc1f2-31a3-378d-bbf3-84c6a86326ca.png" width="50">  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/feba2d35-bc2a-c17d-9867-41172790b07f.png" width="350">  |
| α 値の更新  | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0f11ef44-009d-5319-7ce0-851b1b128bb9.png" width="350">  |

下図左は上記の 2 つ目の子ノードの評価値の計算を開始するフレームで、下図右は 3 つ目の子ノードの評価値の計算を開始するフレームです。図から __右図の方が α 狩りを行う水色の範囲が広がっている__ ため __枝狩りが行われやすくなっている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f1b0c9bc-5f1d-ad6c-60ba-e5fbb8ac4444.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/588cd0f9-1937-26a8-890b-2be14b554179.png" width="300">

下図左は、上図右の最初の子ノードの評価値が計算されたフレームで、その右は 2 つ目の子ノードの評価値の計算を開始するフレームです。図からわかるように __β 値が計算__ されたことによって、__黄色の範囲がさらに狭く__ なり、__max ノードでの水色の範囲が増えている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e4929ec3-3c32-cc5e-e57a-9385a96c8573.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c370cb8d-f32d-414f-3471-33ea844bfb3c.png" width="300">

# 今回の記事のまとめ

今回の記事では、__αβ 法についてのおさらいとまとめ__ を行い、__Mbtree_Anim__ を利用して、__αβ 法が行う処理の確認と説明__ を行いました。今回の説明でもまだピンとこない人がいるかもしれませんが、Mbtree_Anim によって αβ 法の理解につながるのであれば幸いです。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/09a2909f6b44561bd2bf

[^1]:例えば、__親ノード__ である min ノードに __α 値以下の評価値を持つ子ノードが存在__ する場合は、親ノードの評価値が α 以下になるため __影響を与えません__
[^2]:子ノードの評価値を元に、__親ノードの処理__ で __後から α 値や β 値が更新される__ 場合はあります。ただし、max ノードの __子ノードの評価値である α 値__ によって __更新される可能性がある__ のは、__親ノードの β 値__ です。min ノードの場合は α 値と β 値が逆になります
[^3]:右図は 上図の次のフレームの図です