Pythonで〇×ゲームのAIを一から作成する　その138　αβ（アルファベータ）法の仕組みと実装

# 目次と前回の記事

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

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

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

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

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

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

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

# ミニマックス法の問題点

前回の記事で、ミニマックス法を使って特定のノードの評価値を動的に計算する方法を紹介しましたが、その際にルートノードの評価値を計算するためには、50 万以上もある 〇×ゲームの __ゲーム木のノードの評価値をすべて計算する必要がある__ ため、__評価値の計算に約 30 秒も時間がかかる__ という問題があります。

この問題を解決する方法として、[前回の記事](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#%E6%8E%A2%E7%B4%A2%E7%A9%BA%E9%96%93%E3%82%92%E7%8B%AD%E3%82%81%E3%82%8B)で説明した、__探索空間を狭める__ という方法があります。具体的には、ミニマックス法で評価値を計算する際に、__何らかの方法で計算を行うノードの数を減らす__ というものです。ミニマックス法を行う際に __計算するノードを減らした上__ で、ミニマックス法と同じ __[最適解](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E5%8B%95%E7%9A%84%E3%81%AB%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E5%AE%9F%E8%A3%85%E6%96%B9%E6%B3%95)を得る__ ことができる __αβ（アルファベータ）法__ というアルゴリズムがあるので、今回の記事ではその説明を行います。

# αβ 法の仕組み

αβ 法は __直観的にわかりづらく__、αβ法を実装する __プログラムもわかりづらい__ ので、本記事ではその仕組みを説明し、順を追ってプログラムを実装することにします。

ミニマックス法では、〇×ゲームのゲーム木に対して、下記のような計算を行います。

* 〇 の手番のノードの評価値として、子ノードの評価値の最大値を計算する
* × の手番のノードの評価値として、子ノードの評価値の最小値を計算する

ゲーム木の __ノードのうち__、子ノードの評価値の __最大値を計算__ するノードのことを __max ノード__、__最小値を計算__ するノードのことを __min ノード__ と呼びます。

ゲーム木のノードは、必ず __max ノードと min ノードのいずれかに分類__ され、__ゲーム木の深さ__ によって __max ノードと min ノードが交互に現れる__ という性質があります。

## 子ノードの評価値の計算の性質を利用した枝狩り

具体例として、下図の赤枠の 〇 の手番の局面である __max ノードの評価値を計算する場合__ について説明します。以後はこの赤枠のノードのことを $N$ と表記することにします。また、$N$ の 3 つの子（child）ノードを上から順に $C_1$、$C_2$、$C_3$ と表記することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/74246298-330f-d646-c448-058d233c0d98.png" width=200">

ミニマックス法では、__max ノード__ の __子ノードの評価値__ を順番に計算し、その __最大値を求める__ 処理を行うので、最初に $N$ の最初の子ノードの $C_1$ の評価値を計算します。

下図の赤枠の $C_1$ のノードは 〇 が勝利している局面なので、__評価値が 1 として計算__ され、下図のようになります。以後の図では、__直前に処理を行ったノードの枠を赤色__ で、__評価値が計算されていないノードを暗く表示__ することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b8d74237-d1ef-cf2c-9ea5-c8f140e7b578.png" width=200">

次に、下図の赤枠の $C_2$ の評価値を計算する必要がありますが、$C_2$ には __2 つの子ノードが存在する__ ので、それらの評価値を計算する必要があります。$C_2$ の 2 つの子ノードは $N$ の孫（grandchild）ノードなので、$G_{21}$、$G_{22}$ と表記することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8af9d3db-cf93-d016-6b84-be9e597381cb.png" width=200">

下図の赤枠の $G_{21}$ には 1 つだけ子ノードが存在し、その __子ノード__ は引き分けなので __評価値は 0__ となります。子ノードが 1 つしか存在しない場合は、max ノードでも min ノードでも子ノードの評価値を計算すればよいので、$G_{21}$ の __評価値は下図のように 0__ になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/80ea695f-e67d-16c2-97d9-f6d2272f0c8c.png" width=200">

実は、この時点で次の $G_{22}$ の __評価値を計算する必要がない__ ことが __確定__ します。その理由について少し考えてみて下さい。

### min ノードでの枝狩り（α 狩り）

$C_2$ は __× の手番__ なので、子ノードの評価値の最小値を計算する __min ノード__ です。従って、上図のように $C_2$ の子ノードである $G_{21}$ の __評価値が 0 と計算された時点__ で $G_{22}$ の __評価値を計算しなくても__ $C_2$ の __評価値__ は下図のように __0 以下__ であることが __確定__ します。

なお、下図では $C_2$ は 2 つしか子ノードを持ちませんが、$C_2$ が __3 つ以上__ の子ノードを持つ場合でも、$G_{21}$ の __評価値が 0 と計算された時点__ で残りの子ノードの評価値の値に関わらず $C_2$ の __評価値__ が __0 以下__ であることが __確定__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2d01b7b3-00ba-38c9-1bee-97afbd26a24a.png" width=200">

また、$C_2$ の親ノードである $N$ は子ノードの評価値の最大値を計算する __max ノード__ なので、$C_1$ の __評価値が 1 と計算された時点__ で、下図のように $N$ の __評価値は 1 以上__ であることが __確定__ します。

これらのことから、下図の青枠の $G_{22}$ の __評価値がどのような値であっても__ 親ノードの $C_2$ の __評価値は 0 以下__ になり、$N$ の __評価値に影響を与えることはありません__。従って、$C_2$ の __残りの子ノード__ である $G_{22}$ 及び __その子孫ノード__ の評価値を __計算する必要はありません__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a6152ea6-d393-4932-8e61-16ba0bc18b28.png" width=200">

上記から、__min ノードの評価値を計算__ する際に、以下の性質があることがわかります。

* それまでに計算された __兄弟ノード__ の __評価値の最大値を α__ とする
* __子ノードの中__ で、__α 以下の評価値が計算された時点__ で評価値が __α 以下になることが確定__ するため、__そのノードの評価値__ が max ノードである __親ノードの評価値に影響を与えないことが確定__ する
* 従って、その時点で __残りの子ノードの評価値を計算する必要がないことが確定__ する

[以前の記事](https://qiita.com/ysgeso/items/847598556d7e49fe2d87#%E7%9B%B8%E6%89%8B%E3%81%8C%E5%8B%9D%E5%88%A9%E3%81%97%E3%81%9F%E5%B1%80%E9%9D%A2%E3%82%92%E7%99%BA%E8%A6%8B%E3%81%97%E3%81%9F%E5%A0%B4%E5%90%88%E3%81%AE%E6%9E%9D%E7%8B%A9%E3%82%8A)で説明したように、__木構造__ のデータを __探索する際__ に、探索を行う必要がない __ノードとその子孫ノードの探索を行わない__ ようにすることを、__枝狩り__（pruning）と呼ぶと説明しました。枝狩りは __探索空間を狭める__ 処理です。

__αβ 法__ では、上記の手順で __min ノードの子ノードの枝狩り__ を行い、その際に上記の __α という値__ を用いて枝狩りを行うので、この枝狩りのことを __α 狩り__（alpha pruning）や __α カット__ などと呼びます。また、__α の値__ のことを __α 値__ と呼びます。

α 狩りの手順をまとめると以下のようになります。

:::note warn
αβ 法では、以下の手順で __min ノード__ の __子孫ノード__ に対する __α 狩り__ を行う。

* それまでに計算された __兄弟ノード__ の __評価値の最大値を α__ とする
* __子ノードの中__ で __α 以下__ の評価値が __計算された時点__ で __残りの子ノードの評価値の計算を省略__ する
:::

### max ノードでの枝狩り（β 狩り）

__ゲーム木__ では、深さごとに __max ノードと min ノードが交互__ に現れます。また、max ノードと min ノードの性質は __正反対の性質__ なので、__max ノード__ においても、__min ノードと同様の考え方__ で __枝狩りを行う__ ことができます。

具体的には、__max ノード の評価値を計算__ する際に以下の性質があります。__min ノードとの違い__ は下記の太字で表記した __最大値が最小値__ に、__以下が以上__ に、__α が β__ に、__max が min__ になった点だけです。

* それまでに計算された兄弟ノードの評価値の __最小値を β__ とする
* 子ノードの中で、__β 以上__ の評価値が計算された時点で評価値が __β 以上__ になることが確定するため、そのノードの評価値が __min ノード__ である親ノードの評価値に影響を与えないことが確定する
* 従って、その時点で残りの子ノードの評価値を計算する必要がないことが確定する

__αβ 法__ では、上記の手順で __max ノードの子ノードの枝狩り__ を行い、その際に上記の __β という値__ を用いて枝狩りを行うので、その枝狩りのことを __β 狩り__（beta pruning）や __β カット__ などと呼びます。また、__β の値__ のことを __β値__ と呼びます。

β 狩りの手順をまとめると以下のようになります。

:::note warn
αβ 法では、以下の手順で __max ノード__ の __子孫ノード__ に対する __β 狩り__ を行う。

* それまでに計算された __兄弟ノード__ の __評価値の最小値を β__ とする
* __子ノードの中__ で __β 以上__ の評価値が __計算された時点__ で __残りの子ノードの評価値の計算を省略__ する
:::

## 祖先ノードを考慮した min ノードでの α 狩り

上記では、兄弟ノードの評価値を利用した枝狩りを行いましたが、αβ 法では __祖先ノード__ で計算されている __評価値を利用__ することで、__さらなる枝狩り__ を行うことができます。

その方法は、先ほどと同様に __min ノードと max ノードで異なる__ ので、順に説明します。

min ノードでは、以下の方法で α 狩りを行うことができます。

* __祖先ノード__ の中の __max ノード__ をすべて探す
* 探した max ノードの中で、__評価値が計算済__ の __子ノードの評価値の最大値を α__ とする
* 子ノードの中で __α 以下__ の評価値が __計算された時点__ で __残りの子ノードの評価値の計算を省略__ する

__先程との違い__ は、__α 値__ を「__親ノード__ の子ノード（兄弟ノード）で計算された評価値の最大値」で計算していたのを、「__祖先ノードの中のすべての max ノード__ の子ノードで計算された評価値の最大値」で計算するようにした点です。__親ノード__ は __祖先ノードの一種__ なので、__α 値を計算する範囲__ を親ノードから __祖先ノードに広げた__ アルゴリズムです。

### α 狩りの計算の具体例

具体例として、先程の例と同じようなゲーム木での評価値の計算を説明します。なお、実際の 〇×ゲームのゲーム木では、下図の赤枠のノードは決着がついた局面なので子ノードは存在しませんが、下図のようにこのノードが __決着がついておらず、子ノードが存在する場合__ の __評価値の計算の処理__ を考えてみることにします。以後は赤枠のノードを min ノードであることから $M$ と表記します

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0a0bcd26-adf1-6f30-dc39-10fc7bb73532.png" width=250">

上図の $M$ は __min ノード__ です。また、$M$ の __祖先ノード__ の中で、__max ノード__ は下図の __青枠の__ $N$ と __紫枠の__ $G_{21}$ です。$N$ と $G_{21}$ の __子ノード__ の中で __評価値が計算されている__ のは $C_1$ __だけ__ なので、__α は 1__ と計算されます。

$M$ の __子ノードの中__ で、__1 以下__ の評価値が __計算された時点__ で、$M$ の __残りの子ノード__ の評価値を __計算する必要がないことが確定__ します。その理由について少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/27c01881-c5a5-70de-9c62-4cf2acfcfbc2.png" width=250">

$M$ は __min ノード__ なので、__子ノードの中に 1 以下の評価値が存在__ した場合は、$M$ の __評価値__ は下図のように __1 以下__ になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b4c708f3-6a98-5f36-cd8e-0c3730bc30e9.png" width=300">

上図の $M$ の __親ノード__ である $G_{21}$ は、__max ノード__ です。上図の $G_{21}$ には子ノードは 1 つしか存在しませんが、__一般的な評価値の計算例になるように__、下図のように $G_{21}$ に __複数の子ノードが存在する場合__ のことを考えます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b5eddf0a-9078-9e6c-5d8d-a59a210e86b9.png" width=300">

$G_{21}$ に __複数の子ノードが存在__ する場合は、下記の 2 種類の状況が考えられます。

* $G_{21}$ の $M$ 以外の子ノードに __評価値が 1 より大きい__ ノードが __存在する__
* $G_{21}$ の $M$ 以外の子ノードに __評価値が 1 より大きい__ ノードが __存在しない__

__上記の両方の場合__ で先程の方法で __α 狩りを行うことができる__ ことを __示すことで__、__常に__ 先ほどの方法で __α 狩りを行うことができる__ ことが __証明できます__。

### 子ノードに評価値が 1 より大きいノードが存在する場合

$G_{21}$ は __max ノード__ なので、$G_{21}$ の子ノードの中に下図のように __1 より大きい評価値の子ノードが存在__ する場合は、$G_{21}$ の __評価値は 1 より大きな値__ となります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/95e7b9ff-015c-411d-95d0-43253f699ab8.png" width=300">

この場合は $M$ の評価値は $G_{21}$ の評価値に __影響を及ぼしません__。ミニマックス法では、__子ノードの評価値__ を元に __親ノードの評価値を計算する手法な__ ので、$G_{21}$ の評価値に影響を与えないということは、その __祖先の $N$ の評価値にも影響を与えない__ ことになります。従って、$M$ の __子ノード__ の中で __1 つでも 1 以下の評価値が計算された時点__ で残りの子ノードの評価値を __計算しなくても良い__ ことが確認できました。

### 子ノードに評価値が 1 より大きいノードが存在しない場合

$G_{21}$ の子ノードの中に 1 より大きい評価値が __存在しない場合__ は、以下の手順で計算が行われて下図のように $G_{21}$ と $C_2$ の評価値が計算されます。

* $G_{21}$ の全ての子ノードの評価値が 1 以下なので $G_{21}$ の __評価値は 1 以下__ となる
* $G_{21}$ の __親ノード__ である $C_2$ は __min ノード__ なので $C_2$の __評価値は 1 以下__ となる

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/fbac2ca6-d39f-dbd5-f109-97f4b46b550b.png" width=300">

上記から、以下の理由で $M$ の __子ノード__ の中で __1 つでも 1 以下の評価値が計算された時点__ で残りの子ノードの評価値を __計算しなくても良い__ ことが確認できます。

* $C_2$ の __親ノード__ である $N$ は __max ノード__ で、$N$ には __評価値が 1__ の子ノード $C_1$ が __存在する__ ので、$C_2$ の評価値は $N$ の __評価値に影響を及ぼさない__
* 従って、$C_2$ の評価値を計算する際に必要となる、$C_2$ の __子孫ノードの評価値__ はいずれも $N$ の __評価値に影響を及ぼさない__

$G_{21}$ の __他の子ノードの評価値の値に関わらず__、先程の __α 狩りの手順が正しい__ ことが確認できたので、__全ての場合で先程の α 狩りの手順が正しいことが証明できました__。

## 祖先ノードを考慮した αβ 法

上記の例では、__min ノード__ である $N$ の親ノードと、曾祖父ノードに max ノードが存在した場合の例ですが、__もっと遠い祖先ノードに max ノードが存在する場合も同様__ です。

また、__max ノード__ でも __同様の方法で β 狩り__ を行うことができます。

以下は、祖先ノードを考慮した __αβ 法__ のアルゴリズムで、一般的にはこのアルゴリズムを αβ 法と呼びます。

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

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

## α 値と β 値の意味

αβ 法で行う枝狩りは、評価値を計算しても、__最終的に計算する評価値__ に __影響を及ぼさない__ ノードに対して行います。このことから __α 値と β 値__ は、ミニマックス法でそれぞれのノードの評価値を計算する際に、そのノードの評価値が __最終的に求める評価値__ に __影響を与える可能性がない__ ことを表す __子ノードの評価値の範囲__ と考えることができます。

:::note warn
αβ 法が行っているのは、__探索の途中__ で __絶対に探索する必要がないことが判明したノードの枝狩り__ であり、__α 値と β 値__ は枝狩りを行う __評価値の範囲を表す値__ である。

:::

# αβ 法の実装

αβ 法のアルゴリズムがわかったので、__αβ 法__ に従ってゲーム木のノードの __評価値を動的に計算__ する __`ai_abs`__[^1] を定義する事にします。αβ 法の __基本はミニマックス法__ なので、まずは __[`ai_mmdfs`](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#ai-%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE-ai_mmdfs-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ と __同じ処理を行う関数__ として下記のプログラムのように __`ai_abs` を定義__ します。なお、`ai_mmdfs` との違いは、__関数の名前__ と、中で定義する __ローカル関数の名前を `ab_search`__ とした点です。また、`@ai_by_score` のデコレーター式を記述すると、`ai_abs` の処理の確認が行いづらくなってしまうので、デコレーター式は現時点では削除しました。

```python
from marubatsu import Marubatsu
from ai import dprint
from copy import deepcopy

def ai_abs(mb, debug=False):   
    count = 0
    def ab_search(mborig):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = mborig.calc_legal_moves()
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(mborig)
            mb.move(x, y)
            score_list.append(ab_search(mb))
        if mborig.turn == Marubatsu.CIRCLE:
            return max(score_list)
        else:
            return min(score_list)
    
    score = ab_search(mb)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```

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

```diff_python
from marubatsu import Marubatsu
from ai import dprint
from copy import deepcopy

-@ai_by_score
-def ai_mmdfs(mb, debug=False):   
+def ai_abs(mb, debug=False):   
    count = 0
-   def mm_search(mborig):
+   def ab_search(mborig):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = mborig.calc_legal_moves()
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(mborig)
            mb.move(x, y)
-           score_list.append(mm_search(mb))
+           score_list.append(ab_search(mb))
        if mborig.turn == Marubatsu.CIRCLE:
            return max(score_list)
        else:
            return min(score_list)
    
-   score = mm_search(mb)
+   score = ab_search(mb)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

## 兄弟ノード評価値のみを考慮した α 狩りと β 狩りの実装

いきなり祖先ノードの評価値を考慮した αβ 法の実装を行うのは大変なので、本記事の最初に説明した、__兄弟ノードの評価値のみを考慮__ した下記の処理を実装することにします。

以下の手順で min ノードの子孫ノードの α 狩りを行う。

* それまでに計算された兄弟ノードの評価値の最大値を α とする
* 子ノードの中で α 以下の評価値が計算された時点で残りの子ノードの計算を終了する

以下の手順で max ノードの子孫ノードの β 狩りを行う。

* それまでに計算された兄弟ノードの評価値の最小値を β とする
* 子ノードの中で β 以上の評価値が計算された時点で残りの子ノードの計算を終了する

### α 値と β 値の計算処理の実装

まず、上記の処理の中の __α 値と β 値 を計算する処理__ を実装します。上記では、__α 値__ を min ノードの __兄弟ノード__ の評価値の最大値と表記しましたが、min ノードの __兄弟ノードの評価値__ を順番に __計算する処理を行う__ のは、min ノードの __親ノードである max ノード__ です。

:::note warn
従って、__α 値を利用__ して枝狩りを行うのは __min ノード__ ですが、その __α 値を計算__ するのはその __親ノードである max ノード__ です。 

同様に、__β 値を利用__ して枝狩りを行うのは __max ノード__ ですが、その __β 値を計算__ するのはその __親ノードである min ノード__ です。

このように、__α 値と β 値__ は、その値を __計算するノード__ とその値を __利用するノード__ が __異なる__ 点がわかりづらく、__間違えやすい__ ので注意が必要です。
:::

__`ai_mmdfs`__ では下記のプログラムのように、__子ノードの評価値__ を __`score_list`__ という list の要素に記録し、__すべての子ノードの評価値を計算した後__ で `max` または `min` 関数でその最大値または最小値を __まとめて計算__ していました。

```python
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(mborig)
            mb.move(x, y)
            score_list.append(ab_search(mb))
        if mborig.turn == Marubatsu.CIRCLE:
            return max(score_list)
        else:
            return min(score_list)
```

αβ 法では __子ノードの評価値を順番に計算する際__ に、__それまでの子ノードの評価値の最大値__（または最小値）を __計算しておく__ 必要があるので、__まとめて計算__ することは __できません__。

そのため、下記のプログラムのように __`ai_abs`__ を修正する必要があります。


* 4 行目の前で行っている、__決着がついた局面の評価値の計算__ では枝狩りを行うことはできないので、__`ai_mmdfs` から修正する必要はない__
* __5 ~ 12 行目__：〇 の手番の __max ノード__ の場合の処理を行う
* __6 行目__：__max ノード__ では、子ノードの評価値の __最大値__ である __α 値を計算__ する必要があるので、その値を計算する __`alpha` を負の無限大で初期化__ する。__負の無限大を利用した最大値の計算の方法__ について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E8%B2%A0%E3%81%AE%E7%84%A1%E9%99%90%E5%A4%A7%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9Fnone-%E3%82%92%E4%BD%BF%E3%82%8F%E3%81%AA%E3%81%84%E8%A8%98%E8%BF%B0%E6%96%B9%E6%B3%95)を復習すること
* __10 行目__：`ab_search(mb)` によって計算された子ノードの評価値を `score` に代入する
* __11 行目__：max ノードの場合は `max` 関数を利用して `score` と `alpha` の最大値を `alpha` に代入することで、`alpha` にそれまでに計算した子ノードの評価値の最大値を代入する
* __12 行目__：合法手に対する繰り返し処理の終了後では、`alpha` に子ノードの評価値の最大値が計算されて代入されるので、`alpha` を返り値として返すように修正する
* __13 ~ 20 行目__：上記と同様の方法で × の手番の __min ノード__ の場合の子ノードの最小値を表す β 値 を計算し、返り値として返すように修正する

```python
 1  def ai_abs(mb, debug=False):   
 2      count = 0
 3      def ab_search(mborig):
元と同じなので省略
 4          legal_moves = mborig.calc_legal_moves()
 5          if mborig.turn == Marubatsu.CIRCLE:
 6              alpha = float("-inf")
 7              for x, y in legal_moves:
 8                  mb = deepcopy(mborig)
 9                  mb.move(x, y)
10                  score = ab_search(mb)
11                  alpha = max(alpha, score)
12              return alpha
13          else:
14              beta = float("inf")
15              for x, y in legal_moves:
16                  mb = deepcopy(mborig)
17                  mb.move(x, y)
18                  score = ab_search(mb)
19                  beta = min(beta, score)   
20              return beta
元と同じなので省略
```

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

```python
def ai_abs(mb, debug=False):   
    count = 0
    def ab_search(mborig):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            alpha = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb)
                alpha = max(alpha, score)
            return alpha
        else:
            beta = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb)
                beta = min(beta, score)   
            return beta
                
    score = ab_search(mb)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
def ai_abs(mb, debug=False):   
    count = 0
    def ab_search(mborig):
元と同じなので省略
        legal_moves = mborig.calc_legal_moves()
-       score_list = []
-       for x, y in legal_moves:
-           mb = deepcopy(mborig)
-           mb.move(x, y)
-           score_list.append(ab_search(mb))
-       if mborig.turn == Marubatsu.CIRCLE:
-           return max(score_list)
-       else:
-           return min(score_list)        
+       if mborig.turn == Marubatsu.CIRCLE:
+           alpha = float("-inf")
+           for x, y in legal_moves:
+               mb = deepcopy(mborig)
+               mb.move(x, y)
+               score = ab_search(mb)
+               alpha = max(alpha, score)
+           return alpha
+       else:
+           beta = float("inf")
+           for x, y in legal_moves:
+               mb = deepcopy(mborig)
+               mb.move(x, y)
+               score = ab_search(mb)
+               beta = min(beta, score)   
+           return beta
元と同じなので省略
```
</details>

上記から、max ノードでは全ての子ノードの評価値を計算した後の α 値に子ノードの評価値の最大値が計算されるので、__α 値__ は  __max ノードの評価値を計算__ していることがわかります。同様に、__β 値__ は __min ノードの評価値を計算__ しています。

:::note
上記のプログラムの 7 ~ 10 行目と 15 ~ 18 行目は全く同じプログラムなので、その部分をまとめることもできますが、ただでさえわかりづらい αβ 法のプログラムがさらにわかりづらくなるのでまとめないことにします。なお、まとめる方法については、[今回の記事の最後](#ネガマックス法とネガアルファ法)で紹介しましたのでそちらを参照して下さい。
:::

上記の修正は、α 値と β 値を計算する処理を行っているだけで、__枝狩りの処理はまだ実装していない__ ので、__`ai_abs`__ は __`ai_mmdfs` と同じ処理__ を行います。実際に下記のプログラムを実行すると、実行結果のように __[`ai_mmdfs` と同じ結果](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#%E6%8E%A2%E7%B4%A2%E7%AF%84%E5%9B%B2%E3%81%AE%E7%B5%9E%E3%82%8A%E8%BE%BC%E3%81%BF%E3%81%AE%E7%A2%BA%E8%AA%8D)が表示される__ ことが確認できます。

なお、`count` の表示は[前回の記事](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#%E6%8E%A2%E7%B4%A2%E7%AF%84%E5%9B%B2%E3%81%AE%E7%B5%9E%E3%82%8A%E8%BE%BC%E3%81%BF%E3%81%AE%E7%A2%BA%E8%AA%8D) で実装した、`debug=True` を実引数に記述した際に表示される、__探索を行ったノードの数__（ノードの評価値を計算するために `ab_search` を呼び出した回数）を表します。

```python
mb = Marubatsu()
print(ai_abs(mb, debug=True))
```

実行結果

```
count = 549946
0
```

### α 狩りと β 狩りの実装

__α 狩り__ を行うためには、__min ノードの子ノードの評価値を計算する際__ に、その __親ノードで計算した α 値の情報が必要__ になります。そのため、仮引数 __`mmorig`__ に代入された __min ノードの評価値を計算__ する処理で __α 狩りを行う__ ためには __`ab_search`__ に __α 値を代入する仮引数を追加__ する必要があります。これは __β 狩りを行う際も同様__ なので、`ab_search` に α 値と β 値を代入するための __仮引数 `alpha`、`beta` を追加__ することにします。下記は __追加した仮引数を利用__ して __α 狩りと β 狩りを行う__ ように `ai_abs` を修正したプログラムです。

* __3 行目__：`ab_search` に仮引数 `alpha` と `beta` を追加する
* __10 行目__：〇 の手番の max ノードの __子ノードは min ノード__ なので、その __min ノード__ の評価値を計算する際に __α 狩りを行うためには α 値が必要__ になる。そのため、__子ノードの評価値を計算__ する処理を行う __`ab_search`__ を呼び出す際に __α 値に対応する実引数 `alpha` を記述__ する。また、__β 値は必要がない__ ので対応する実引数に __`None` を記述する__[^2] 
* __11、12 行目__：__max ノードの子ノードの評価値__ が __β 値以上の場合__ は、残りの子ノードの評価値を計算する必要がないので、__計算した評価値__ をこのノードの評価値として __return 文で返す__ 処理を行う。return 文が実行されると `ab_search` の処理が終了し、__残りの子ノード__ の評価値を計算する __処理が行われなくなる__ ため、__β 狩りが行われた__ ことになる
* __20 ~ 22 行目__：min ノードの場合の子ノードの評価値の計算や、α 狩りの処理を、上記と同様の方法で行う
* __26 ~ 28 行目__：__`ai_abs`__ が評価値を計算するノードは、__兄弟ノードの評価値が計算されることはない__。そのため、そのノードが __max ノード__ の場合は __β 値__ として __正の無限大を設定__ する。__α 値__ は子ノードの評価値を計算する際に __必要がないので `None` を設定__ する
* __29 ~ 31 行目__：min ノードの場合に上記と同様の処理を行う
* __32 行目__：`ai_abs` の実引数に `alpha` と `beta` を記述するように修正する
 
```python
 1  def ai_abs(mb, debug=False):   
 2      count = 0
 3      def ab_search(mborig, alpha, beta):
元と同じなので省略
 4          legal_moves = mborig.calc_legal_moves()
 5          if mborig.turn == Marubatsu.CIRCLE:
 6              alpha = float("-inf")
 7              for x, y in legal_moves:
 8                  mb = deepcopy(mborig)
 9                  mb.move(x, y)
10                  score = ab_search(mb, alpha, None)
11                  if score >= beta:
12                      return score
13                  alpha = max(alpha, score)
14              return alpha
15          else:
16              beta = float("inf")
17              for x, y in legal_moves:
18                  mb = deepcopy(mborig)
19                  mb.move(x, y)
20                  score = ab_search(mb, None, beta)
21                  if score <= alpha:
22                      return score
23                  beta = min(beta, score)   
24              return beta
25                
26      if mb.turn == Marubatsu.CIRCLE:
27          alpha = None
28          beta = float("inf")    
29      else:
30          alpha = float("-inf")
31          beta = None
32      score = ab_search(mb, alpha, beta)
元と同じなので省略
```

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

```python
def ai_abs(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha, beta):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            alpha = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, alpha, None)
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return alpha
        else:
            beta = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, None, beta)
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return beta
                
    if mb.turn == Marubatsu.CIRCLE:
        alpha = None
        beta = float("inf")    
    else:
        alpha = float("-inf")
        beta = None
    score = ab_search(mb, alpha, beta)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
def ai_abs(mb, debug=False):   
    count = 0
-   def ab_search(mborig):
+   def ab_search(mborig, alpha, beta):
元と同じなので省略
        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            alpha = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = ab_search(mb, alpha, None)
+               score = ab_search(mb, alpha, None)
+               if score >= beta:
+                   return score
+               alpha = max(alpha, score)
            return alpha
        else:
            beta = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = ab_search(mb)
+               score = ab_search(mb, None, beta)
+               if score <= alpha:
+                   return score
                beta = min(beta, score)   
            return beta               
元と同じなので省略                
+   if mb.turn == Marubatsu.CIRCLE:
+       alpha = None
+       beta = float("inf")    
+   else:
+       alpha = float("-inf")
+       beta = None
-   score = ab_search(mb)
+   score = ab_search(mb, alpha, beta)
元と同じなので省略
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果からゲーム開始時の局面の評価値を計算するために __`ab_search` で評価値の計算を行ったノードの数__ が約 55 万から __約 3 万に大幅に減った__ ことが確認でき、αβ 法による枝狩りが実際に行われたことが確認できます。また、枝狩りが行われた結果、下記のプログラムの __処理時間__ が約 30 秒から __約 1 秒に大幅に短縮__ されるため __αβ 法が大きな効果を持つ__ ことが確認できました。

```python
print(ai_abs(mb, debug=True))
```

実行結果

```
count = 29257
0
```

:::note
__`mborig`__ が __max ノード__ の場合は、仮引数 __`alpha` に `None`__ が、__`beta` に β 値__ が代入された状態で __`ab_search`__ が呼び出されますが、そのうちの __`alpha`__ は __`ab_search`__ の中の下記のプログラムで負の無限大が代入され、その後の繰り返し処理で __評価値の最大値が代入__ されるので、__`alpha` に最初に代入された `None` が使われることはありません__。一方、__`beta`__ は仮引数に代入された値が __そのまま利用__ され、`ab_search` の処理の中で __その値が変更されることはありません__。

```python
        if mborig.turn == Marubatsu.CIRCLE:
            alpha = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, alpha, None)
                if score >= beta:
                    return score
                alpha = max(alpha, score)
```

`mborig` が min ノードの場合は、上記の `alpha` と `beta` の説明が逆になります。
:::

## 祖先ノードを考慮した α 狩りとβ 狩りの実装

次に、下記の __祖先ノードを考慮__ した α 狩りと β 狩りの実装することにします。

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

先程は、__max ノード子ノードの計算__ を行う際に、下記のプログラムのように __α 値のみ__ を子ノードの処理を行う __`ab_search` に伝えました__ が、__祖先ノードの評価値を考慮__ するためには、__`ab_search` に α 値と β 値の両方を伝える必要__ があります。どのように伝えればよいかについて少し考えてみて下さい。

```python
            if mborig.turn == Marubatsu.CIRCLE:
                score = ab_search(mb, alpha, None)
```

先程のプログラムでは、__max ノードの α 値を計算__ する際に、__兄弟ノードの評価値のみを考慮__ して計算を行っていたため、`ab_search` の中で __α 値を計算する変数__ を __負の無限大で初期化__ してから計算を行いました。

max ノードで計算する __α 値__ は子ノードの評価値が計算された際に、それまでの α 値と子ノードの __最大値で更新されます__。そのため、__祖先ノードの max ノードの α 値__ を __子ノードに伝え__、max ノードで __α 値__ を計算する際に負の無限大ではなく、__伝えられた α 値から__ 計算することで、α 値の値は __祖先ノードの max ノードの α 値の最大値__ になります。



例えば、下図の __赤枠の max ノードの α 値を計算__ する際には、負の無限大からではなく、__祖先ノードの青枠 max ノードの α 値__ である __1 を α 値の初期値__ として計算します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/32030ad6-d38d-fe2a-a514-0bf291fd6809.png" width="250">

  


上図のような処理を行うためには、__min ノード__ では、親ノードから受け取った __`alpha` の値__ を、__子ノードの評価値を計算する処理に受け渡す__ 必要があります。現状では α 値は max ノードから子ノードに実引数で伝わりますが、__min ノード__ では下記のプログラムのように __`alpha` の実引数に `None` が代入__ されて `ab_search` が呼び出されるので __伝わりません__。

```python
        score = ab_search(mb, None, beta)
```                

そこで、__min ノード__ で __`ab_search`__ を呼び出す際に、下記のプログラムのように親ノードから受け取った __`alpha` に代入された α 値__ を __そのまま__ 子ノードの評価値を計算する処理に __受け渡す__ ように修正します。

```python
        score = ab_search(mb, alpha, beta)
```                

また、__max ノードでも同様__ に __β 値をそのまま__ 子ノードの評価値を計算する処理に __受け渡す__ ように修正します。

__α 値と β 値__ の値が、親ノードから仮引数 `alpha` と `beta` で __受け渡されるようになった__ ので、それらを正または負の無限大で __初期化する処理を削除する__ 必要があります。

`ai_abs` で `mb` の評価値を計算する局面を計算するために __最初に `ab_search` を呼び出す際__ には、__α 値 と β 値の両方に適切な値を受け渡す__ 必要があります。α 値は祖先ノードの α 値の最大値、β 値は祖先ノードの β 値の最小値を表し、その場合に __祖先ノードは存在しない__ ため、それぞれに負の無限大と正の無限大を設定します。

下記は、そのように `ab_search` を修正したプログラムです。

* 6、14 行目の後にあった、`alpha` または `beta` を正の無限大または負の無限大で初期化する処理を削除する
* __9、18 行目__：max ノードでも、min ノードでも子ノードの評価値を計算する際に __α 値と β 値の両方を実引数に記述__ して `ab_search` を呼び出すように修正する
* 24 行目の前の `alpha` と `beta` を計算する処理を削除する
* __24 行目__：`ai_abs` で `mb` のノードの評価値を計算するために `ab_search` を呼び出す際に、α 値と β 値にそれぞれの負の無限大と正の無限大を記述して呼び出すように修正する

```python
 1  def ai_abs(mb, debug=False):   
 2      count = 0
 3      def ab_search(mborig, alpha, beta):
元と同じなので省略
 4          legal_moves = mborig.calc_legal_moves()
 5          if mborig.turn == Marubatsu.CIRCLE:
 6              for x, y in legal_moves:
 7                  mb = deepcopy(mborig)
 8                  mb.move(x, y)
 9                  score = ab_search(mb, alpha, beta)
10                  if score >= beta:
11                      return score
12                  alpha = max(alpha, score)
13              return alpha
14          else:
15              for x, y in legal_moves:
16                  mb = deepcopy(mborig)
17                  mb.move(x, y)
18                  score = ab_search(mb, alpha, beta)
19                  if score <= alpha:
20                      return score
21                  beta = min(beta, score)   
22              return beta
23                
24      score = ab_search(mb, float("-inf") , float("inf"))
元と同じなので省略
```

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

```python
def ai_abs(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha, beta):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, alpha, beta)
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return alpha
        else:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, alpha, beta)
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return beta
                
    score = ab_search(mb, float("-inf") , float("inf"))
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
def ai_abs(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha, beta):
元と同じなので省略
        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
-           alpha = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = ab_search(mb, alpha, None)
+               score = ab_search(mb, alpha, beta)
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return alpha
        else:
-           beta = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = ab_search(mb, None, beta)
+               score = ab_search(mb, alpha, beta)
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return beta
                
-   if mb.turn == Marubatsu.CIRCLE:
-       alpha = None
-       beta = float("inf")    
-   else:
-       alpha = float("-inf")
-       beta = None
-   score = ab_search(mb, alpha, beta)
+   score = ab_search(mb, float("-inf") , float("inf"))
元と同じなので省略
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果からゲーム開始時の局面の評価値を計算するために探索したノードの数が約 3 万から __約 2 万に減った__ ことが確認できます。

```python
print(ai_abs(mb, debug=True))
```

実行結果

```
count = 18297
0
```

## AI の関数としての `ai_abs` の定義

先程のプログラムでは 24 行目で __最初に `ab_search` を呼び出す際__ に __α 値と β 値の実引数を記述__ しましたが、その代わりに __`ab_search`__ の __仮引数 `alpha` と `beta`__ をそれぞれ __負の無限大と正の無限大をデフォルト値とする仮引数__ として定義できます。

`ai_abs` は、仮引数として局面を表すデータを代入する `mb` と、デバッグ表示を行うかどうかを表す `debug` を持ち、局面の評価値を返す関数として定義したので、__`@ai_by_score` のデコレーター式を記述__ することで __AI の関数として定義__ することができます。

下記は、そのように `ai_abs` を修正したプログラムです。

* __3 行目__：`@ai_by_score` のデコレータ式を記述する
* __6 行目__：`alpha` と `beta` をデフォルト引数に修正する
* __7 行目__：最初に `ab_search` を呼び出す際に、α 値とβ 値の実引数を省略する

```diff_python
1  from ai import ai_by_score
2
3  @ai_by_score
4  def ai_abs(mb, debug=False):   
5      count = 0
6      def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
7      score = ab_search(mb)
元と同じなので省略
```

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

```python
from ai import ai_by_score

@ai_by_score
def ai_abs(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, alpha, beta)
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return alpha
        else:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, alpha, beta)
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return beta
                
    score = ab_search(mb)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
+from ai import ai_by_score

+@ai_by_score
def ai_abs(mb, debug=False):   
    count = 0
-   def ab_search(mborig, alpha, beta):
+   def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
-   score = ab_search(mb, float("-inf") , float("inf"))
+   score = ab_search(mb)
元と同じなので省略
```
</details>

上記の修正後に、下記のプログラムで __`ai_abs`__ が __強解決の AI であるか__ どうかを確認すると、実行結果のように __強解決の AI であることが確認できました__。

```python
from util import Check_solved
print(Check_solved.is_strongly_solved(ai_abs))
```

実行結果

```
100%|██████████| 431/431 [00:03<00:00, 114.97it/s]
431/431 100.00%
(True, [])
```

# αβ 法による枝狩りの効率

__αβ 法__ によって __どれだけの枝狩りを行うことができるか__ については、__ゲーム木の内容によって大きく異なります__。__最も多く枝帰りを行うことができる__ のは、それぞれのノードの __子ノードが評価値の高い順（min ノードの場合は低い順）に並んでいる場合__ で、その場合は基本的に各ノードの __最初の子ノードの評価値を計算した時点で枝狩りを行うことができる__ ため、最も枝狩りを多く行うことができます。具体的な計算方法は長くなるので示しませんが、最高で元のノードの数が n の場合は探索するノードの数を $\sqrt{n}$ まで減らすことができます。

〇×ゲームの __ゲーム開始時の局面__ の場合は、ミニマックス法で 549946、αβ 法で 18297 個のノードの評価値を計算する必要があります。$\sqrt{549946} = 約 740$ なので、理想的ではありませんが、それでも __約 1/30 に減っている__ ので __αβ 法は確かに大きな効果__ があります。

# ネガマックス法とネガアルファ法

ミニマックス法と、αβ 法では max ノードと min ノードで行う処理で __同じような処理を 2 回記述__ する必要があります。__max ノードと min ノードは交互に現れる__ ので、評価値を計算する __関数の返り値の符号などを反転させる__ ことで、__常に__ 子ノードの評価値の __最大値を計算するように__、max ノードと min ノードの処理を __1 つにまとめる__ という手法があります。__符号を反転（negative）する__ ことから、そのようなアルゴリズムの事をそれぞれ __ネガマックス法__ と __ネガアルファ法__ と呼びます。

ネガマックス法とネガアルファ法は確かに処理を短く記述できますが、ただでさえわかりづらいミニマックス法や αβ 法の __プログラムの意味がさらにわかりづらくなる__[^3]という欠点があるので、本記事では採用しません。具体的なプログラムの記述方法について興味がある方は、下記の Wikipedia のリンク先を参照して下さい。

https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95

https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E3%83%BB%E3%83%99%E3%83%BC%E3%82%BF%E6%B3%95

# 今回の記事のまとめ

今回の記事では αβ 法の仕組みの説明と、その実装を行いました。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/ff32ebabb69a4754dd4a

[^1]:abs は alpha beta search の略です
[^2]:この後のノートで説明しますが、`beta` に対応する実引数の値は `ab_search` の中で利用されないのでどのような値を記述してもかまいません
[^3]:ネガアルファ法では、関数の返り値の符号だけでなく、実引数に記述する α 値と β 値の符号と順序を逆にする必要があるため、プログラムの意味がさらに分かりづらくなります。詳しくは上記の Wikipedia のリンク先のプログラムを参照して下さい