Pythonで〇×ゲームのAIを一から作成する　その153　αβ 法が計算する評価値の意味（fail low と fail high）

# 目次と前回の記事

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

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

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

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

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

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

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

# αβ 法によって計算される評価値の意味

[前回の記事](https://qiita.com/ysgeso/items/dc738bc54c0f837f6dc5#3-%E3%81%A4%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%82%92%E3%82%AD%E3%83%BC%E3%81%A8%E3%81%99%E3%82%8B%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E4%BF%AE%E6%AD%A3%E6%96%B9%E6%B3%95)では、__局面__ と __α 値__ と __β 値の初期値__ をキー とした __dict による置換表__ を利用した αβ 法を紹介しましたが、その方法では置換表による __[枝狩りの効率が悪いという問題](https://qiita.com/ysgeso/items/dc738bc54c0f837f6dc5#3-%E3%81%A4%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%82%92%E3%82%AD%E3%83%BC%E3%81%A8%E3%81%97%E3%81%9F%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)__ があります。置換表によって効率の良い枝狩りを行うためには、__αβ 法によって計算される評価値の意味__ について理解する必要があります。

αβ 法では __正しい評価値を計算したいノード__ を __ルートノードとする部分木__ のノードに対する __評価値の計算を行います__。その際に、__ルートノードの評価値は正しく計算__ されますが、__それ以外のノード__ の評価値は __必ずしも正しく計算されません__。__ルートノード以外のノード__ で __どのような評価値が計算されるか__ については、詳しく説明してきませんでしたので今回の記事ではそのことについて説明します。

## これまでの記事の知識からわかる性質

[以前の記事](https://qiita.com/ysgeso/items/abe910c5067cb7143faa#%CE%B1-%E5%80%A4%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E6%84%8F%E5%91%B3)で説明したように、α 値と β 値は __子ノードの評価値 が α 値以下または β 値以上__ の場合に __ルートノードの評価値に影響を与えない__ ことを表す値です。

αβ 法ではその性質から、__ノードの評価値が α 値の初期値以下__ である場合は、そのノードの評価値を __α 値の初期値以下のどのような値として計算してもかまわない__ ことを利用して枝狩りを行います。同様に __ノードの評価値が β 値の初期値以上__ の場合は、そのノードの評価値を __β 値の初期値以上のどのような値として計算してもかまいません__。

一方、ノードの評価値が __α 値と β 値の初期値の間__ の場合は、その評価値が __ルートノードの評価値に影響を与える__ ことが保証されるため、本当の評価値が __α 値と β 値の初期値の間__ であるということがわかります。なお、子ノードの評価値が正しいという保証がないため、現時点での知識は計算された評価値が __正しい評価値であるという保証はありません__。

上記から、αβ 法で計算した __ルートノード以外の評価値__ とミニマックス法で計算した __本当の評価値の間__ には __下記の表のような関係がある__ ことがわかります。

| αβ 法で計算された評価値 | 本当の評価値 |
|:-:|:-:|
| α 値の初期値以下 | α 値の初期値以下  |
| α 値と β 値の初期値の間  | α 値と β 値の初期値の間  |
| β 値の初期値以上  | β 値の初期値以上  |

上記の表の αβ 法で計算された評価値と本当の評価値の __関係はかなりあいまい__ です。例えば α 値と β 値の初期値が -100 と 100 の場合に、αβ 法でそのノードの評価値が 10 と計算された場合は、そのノードの __本当の評価値__ が -100 ~ 100 という __大きな範囲のいずれかの数値__ であることしか言えません。そこで、今回の記事では αβ 法で計算された評価値と本当の評価値の間に __もっと厳密な関係があることを示す__ ことにします。

## 記号を使ったミニマックス法と αβ 法の処理の説明

言葉だけで説明を行うと説明が長くわかりづらくなるため、今回の記事ではいくつかの記号を使って説明を行うことにします。

__ミニマックス法__ でのノード $N$ の __評価値の計算方法__ は記号を使うと以下のようになります。

* $N$ の __子ノードの評価値__ の __最小値__ を $s_{min}$、__最大値__ を $s_{max}$ と表記する
* ミニマックス法で計算される $N$ の __評価値を $S_N$ と表記__ した場合に
max ノードでは $S_N = s_{max}$、min ノードでは $S_N = s_{min}$ である

__αβ 法__ での __max ノード__ $N$ の __評価値の計算方法__ は記号を使うと以下のようになります。

* $N$ の __α 値と β 値の初期値__ を単に __α、β と表記__ する
* $N$ の $i$ 番の子ノードの評価値を $s_i$ と表記する。ただし $i$ は 0 から数える
* αβ 法で計算された $N$ の __評価値を $S_N'$ と表記__ した場合に $S'_N$ は以下の表のように計算される

| $s_{max}$ の範囲 | $S_N'$ の値 |
|:-:|:-:|
| $s_{max} ≦ α$  | $α$  |
| $α < s_{max} < β$  | $s_{max}$  |
| $β ≦ s_{max}$  | $β ≦ s_{i}$ となる最初の $s_{i}$ |

__min ノード__ では同様の理由で以下の表のようになります。

| $s_{min}$ の範囲 | $S_N'$ の値 |
|:-:|:-:|
| $s_{min} ≦ α$  | $s_{i} ≦ α$ となる最初の $s_{i}$  |
| $α < s_{min} < β$  | $s_{min}$  |
| $β ≦ s_{min}$  | $β$ |

ただし、__ゲームの決着がついた__ 子ノードが存在しない __リーフノード__ では、ミニマックス法も αβ 法もゲームの勝敗に基づいた __正しい評価値が常に計算__ されます。

## 記号を使ったこれまでの記事の知識からわかる性質

先程説明した、これまでの記事の知識からわかる __αβ 法__ で計算された __評価値 $S_N'$__ と、__ミニマックス法__ で計算される __本当の評価値__ である $S_N$ の __関係の表__ を記号を使って表記すると下記のような __簡潔な表__ になります。

| $S_N'$ の範囲 | $S_N$ の範囲 |
|:-:|:-:|
| $S_N' ≦ α$ | $S_N ≦ α$  |
| $α < S_N' < β$  | $α < S_N < β$  |
| $β ≦ S_N'$  | $β ≦ S_N$  |

# 全ての子ノードの評価値が正しく計算される場合の αβ 法の評価値の性質

ノード $N$ の __すべての子ノードの評価値が正しく計算される場合__ は、先程の下記の表から __max ノード__ では __αβ 法__ で計算された __評価値 $S_N'$__ と、__ミニマックス法__ で計算される __本当の評価値__ である $S_N$ との間には __以下の箇条書きのような関係がある__ ことがわかります。

| $s_{max}$ の範囲 | $S_N'$ の値 |
|:-:|:-:|
| $s_{max} ≦ α$  | $α$  |
| $α < s_{max} < β$  | $s_{max}$  |
| $β ≦ s_{max}$  | $β ≦ s_{i}$ となる最初の $s_{i}$ |

* $s_{max} ≦ α$ の場合
__ミニマックス法__ では $s_{max}$ を $N$ の評価値 $S_N$として計算するが、__αβ 法__ では $s_{max}$ __以上の値__ である __α__ が評価値 $S_N'$ として計算される。$S_N = s_{max} ≦ S_N' = α$ であることから $S_N ≦ S_N'$ である
* $α < s_{max} < β$ の場合
ミニマックス法と同じ $s_{max}$ が評価値として計算されるので、$S_N = S'_N$ である
* $β ≦ s_{max}$ の場合
β 狩りによって __評価値の計算が省略された子ノードの中__ に $S_N'$ __以上の評価値__ を持つ子ノードが __存在する可能性がある__ ので、本当の評価値 $S_N$ は $S'_N$ 以上の可能性がある。従って $S'_N ≦ S_N$ である

下記の表の __min ノード__ では同様の理由から下記の箇条書きのようになります。

| $s_{min}$ の範囲 | $S_N'$ の値 |
|:-:|:-:|
| $s_{min} ≦ α$  | $s_{i} ≦ α$ となる最初の $s_{i}$  |
| $α < s_{min} < β$  | $s_{min}$  |
| $β ≦ s_{min}$  | $β$ |

* $s_{min} ≦ α$ の場合
$S_N ≦ S'_N$ である
* $α < s_{min} < β$ の場合
$S_N = S'_N$ である
* $β ≦ s_{min}$ の場合
$β = S'_N ≦ S_N$ である

__上記を先程の表に加える__ と以下の表のようになります。

__max ノード__ の場合。

| $s_{max}$ の範囲 | $S_N'$ の値 | $S_N$ と $S_N'$ の関係 |
|:-:|:-:|:-:|
| $s_{max} ≦ α$  | $α$  | $S_N ≦ S'_N$  | 
| $α < s_{max} < β$  | $s_{max}$  | $S_N = S'_N$  |
| $β ≦ s_{max}$  | $β ≦ s_{i}$ となる最初の $s_{i}$ | $S'_N ≦ S_N$   | 

__min ノード__ の場合。

| $s_{min}$ の範囲 | $S_N'$ の値 | $S_N$ と $S_N'$ の関係 |
|:-:|:-:|:-:|
| $s_{min} ≦ α$  | $s_{i} ≦ α$ となる最初の $s_{i}$  | $S_N ≦ S'_N$  | 
| $α < s_{min} < β$  | $s_{min}$  | $S_N = S'_N$  |
| $β ≦ s_{min}$  | $β$ | $S'_N ≦ S_N$   | 

## αβ 法で求められる評価値と本当の評価値の関係

__αβ 法で $N$ の評価値を計算__ した際に __求められる値__ は $S_N'$ であり、$s_{min}$ や $s_{max}$ を __直接求めることができるとは限りません__[^1]。そこで、上記の表から αβ 法で求められるとは限らない $s_{max}$ と $s_{min}$ を __削除する__ ことで、αβ 法で求められる評価値 $S_N'$ と本当の評価値 $S_N$ の __関係を表す表を作成__ することにします。具体的には上記の表の「$s_{max}$ の範囲」と「$S_N'$ の値」の列を「$S_N'$ の範囲」という __列にまとめます__。

max ノードの場合はそれぞれ以下のようになります。

* $s_{max} ≦ α$ の場合は $S_N'$ の値は α になるので、$S_N'$ の範囲は $S_N' = α$ となる
* $α < s_{max} < β$ の場合は $S_N' = s_{max}$ なので、$S_N'$ の範囲は $α < S_N' < β$ となる
* $β ≦ s_{max}$ の場合は $β ≦ s_i = S_N'$ なので、$S_N'$ の範囲は $β ≦ S_N'$ となる

min ノードの場合も同様の考え方でそれぞれ以下のようになります。

* $s_{min} ≦ α$ の場合は $S_N' ≦ α$ となる
* $α < s_{min} < β$ の場合は $α < S_N' < β$ となる
* $β ≦ s_{min}$ の場合は $β = S_N'$ となる

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

| max ノードでの $S'_N$ の範囲 | min ノードでの $S'_N$ の範囲 | $S_N$ との関係 |
|:-:|:-:|:-:|
| $S'_N = α$  | $S'_N ≦ α$  | $S_N ≦ S'_N$  | 
| $α < S'_N < β$  | $α < S'_N < β$  | $S_N = S'_N$  |
| $β ≦ S'_N$ | $β = S'_N$  | $S'_N ≦ S_N$   | 

なお、$S'_N = α$ は $S'_N ≦ α$、$β = S'_N$ は $β ≦ S'_N$ という __条件に含まれる__ ので、max ノードと min ノードでの $S'_N$ の範囲を下記の表のように __まとめて単純化__ することができます。また、表にそれぞれの行の意味と用語を加えました。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる | fail high |

__下界__（lower bound）と __上界__（upper bound）は数学の用語ですが、意味がわからない人が多いのではないかと思いますので説明します。

__上界と最大値__ は以下のように似ていますが __異なる意味です__。なお、下界は上界の逆です。

* __最大値__ はある値が __実際に取りうる最大の値__ を表す。例えば 1 ~ 6 までの出目が出るサイコロの出目の最大値は 6 であり、サイコロを振った時に __実際に 6 が出る可能性がある__
* __上界__ はある値がとりうる値の __最大値以上であればどのような値でも構わない__。別の言葉で言えば、__実際にその値を取りうるかどうかはわからない__ が、__少なくともその値より大きくなることがない値__ の事を表す。例えば 6 以上の全ての実数はサイコロの出目の上界であるので、10 はサイコロの出目の上界である

上記の表で「本当の評価値の最大値がわかる」と表記しなかったのは、__本当の評価値__ はミニマックス法を用いて __ただ 1 つの値が計算される__ ので __範囲を持たないから__ です。

:::note
似たような数学の用語に上限と下限があります。上限は上界の最小値という意味を持ちます。多くの場合では、上限と最大値は同じ値になりますが、上限は存在するが最大値が存在しない場合があります。例えば 6 未満の実数には 6 は含まれないので最大値はありませんが、上限は 6 となります。

なお、実数のように最大値、上限、上界のいずれも持たないようなものもあります。

本記事でのこれらの用語の説明はわかりやすさを重視したものなので、__数学での正確な用語の定義ではありません__。参考までにこれらの用語の wikipedia のリンクを下記に示します。数学的な用語の定義を知りたい方は参考にして下さい。
:::

https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88#%E4%B8%8A%E9%99%90

上記の表の性質を言葉で説明すると以下のようになります。

:::note warn
__αβ 法__ で求められたノード $N$ の __評価値__ $S_N'$ が __α 値と β 値の初期値の範囲内__ の場合は $S'_N$ には __正しい評価値__ $S_N$ が求められている。なお、一般的にはこのような正確で厳密な値の事を厳密値（exact value）と呼ぶ[^2]。

α 値と β 値の初期値の __範囲外の場合__ は $S_N'$ には __本当の評価値__ $S_N$ の __上界または下界__ が計算される。またそれぞれの場合を __fail low__、__fail high__ と呼ぶ[^3]。
:::

説明を短くするために、以後は __α 値の初期値以下の評価値__（$S'_N ≦ α$）が計算されるノードの事を __fail low__、__α 値と β 値の範囲内の評価値__（$α < S_N' < β$）が計算されるノードの事を __exact value__、__β 値の初期値以上の評価値__（$β ≦ S'_N$）が計算されるノードのことを __fail high__ と表記することにします。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる | fail high |

上記の表と、先程示した下記のこれまでの記事からわかる関係の表を見比べてみてください。上記の表の方が $S_N'$ と$S_N$ の関係を __より厳密に表せている__ ことがわかるはずです。

| $S_N'$ の範囲 | $S_N$ の範囲 |
|:-:|:-:|
| $S_N' ≦ α$ | $S_N ≦ α$  |
| $α < S_N' < β$  | $α < S_N < β$  |
| $β ≦ S_N'$  | $β ≦ S_N$  |

:::note
上記の表の性質を利用した、置換表とは異なる方法で αβ 法の枝狩りの効率を高める方法があります。その方法については今後の記事で紹介する予定です。
:::

## αβ 法での評価値の計算方法のバリエーション

本記事ではこれまでは $N$ が __max ノードで fail low__（$s_{max} ≦ α$）の場合に、$N$ の __評価値を α と計算__ していましたが、その場合のノードの __評価値を__ $s_{max}$ __と計算しても構いません__。そのように計算しても良い理由について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/abe910c5067cb7143faa#%CE%B1-%E5%80%A4%E3%82%84-%CE%B2-%E5%80%A4%E3%82%92%E5%88%9D%E6%9C%9F%E5%80%A4%E3%81%A8%E3%81%97%E3%81%A6%E8%A8%88%E7%AE%97%E3%82%92%E8%A1%8C%E3%81%A3%E3%81%A6%E8%89%AF%E3%81%84%E7%90%86%E7%94%B1)を復習して下さい。

ただし、$N$ の評価値を α と計算した場合と、$s_{max}$ と計算した場合では __max ノードでの fail low の場合__ の $S_N'$ と $S_N$ __との関係がより厳密__ になります。具体的には $S_N' = α$ の場合は $S_N ≦ S_N' = α $ となりますが、$S_N' = s_{max}$ の場合は $s_{max} ≦ α$ なので $S_N ≦ S_N' ≦ α$ となるため、__本当の評価値 $S_N$ の上界__ を表す $S_N'$ が小さくなって $S_N$ の __範囲が狭まる可能性が生じる__ ことになります。

例えば α 値の初期値が 0 で子ノードの評価値が -1、-2、-3 の場合は $s_{max}$ = -1 となるので、本当の評価値の範囲は下記のように $S_N' = s_{max}$ __として計算したほうが狭くなります__。

| $S'_N$ の計算方法 | $S_N$ の範囲 | 意味 |
|:-:|:-:|:--|
| $α = 0$  | $S_N ≦ 0$  | 本当の評価値は 0 以下 | 
| $s_{max} = -1$  | $S_N ≦ -1$  | 本当の評価値は -1 以下 |

同様に、$N$ が __min ノードで fail high__ の場合の評価値を β ではなく $s_{min}$ と計算することで、$S_N$ の __範囲が狭まる可能性__ が生じます。また、そのように計算することで、max ノードの場合でも min ノードの場合でも先程示した __下記の表が厳密に正しくなります__[^4]。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

次回の記事で説明しますが、__本当の評価値の範囲が狭い__ ほうが __置換表を利用したαβ 法__ の __枝狩りを効率よく行うことが出来る__ ので、以後の説明では αβ 法の計算を下記の表のように行うことにします。

__max ノード__ の場合。

| $s_{max}$ の範囲 | $S_N'$ の値 | 用語 | 
|:-:|:-:|:--|
| $s_{max} ≦ α$  | $s_{max}$  | fail low |
| $α < s_{max} < β$  | $s_{max}$  | exact value |
| $β ≦ s_{max}$  | $β ≦ s_{i}$ となる最初の $s_{i}$ | fail high |

__min ノード__ の場合。

| $s_{min}$ の範囲 | $S_N'$ の値 | 用語 | 
|:-:|:-:|:--|
| $s_{min} ≦ α$  | $s_{i} ≦ α$ となる最初の $s_{i}$  | fail low | 
| $α < s_{min} < β$  | $s_{min}$  | exact value | 
| $β ≦ s_{min}$  | $s_{min}$ | fail high |

:::note
これまでに上記の表のように計算していなかったのは、[以前の記事](https://qiita.com/ysgeso/items/abe910c5067cb7143faa#%E3%83%AB%E3%83%BC%E3%83%88%E3%83%8E%E3%83%BC%E3%83%89%E4%BB%A5%E5%A4%96%E3%81%AE%E5%A0%B4%E5%90%88)で説明したようにプログラムを簡潔に記述することが出来るからです。すぐ後で実装を行いますが、上記のような計算を行うためには、α 値 や β 値とは別に子ノードの評価値の最大値（または最小値）を記録するための変数を用意する必要が生じます。

そのため、αβ 法の処理を実装する際には、本記事でこれまでに行ってきた方法で行うことがあります。例えば [wikipedia の αβ 法の疑似コード](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)ではそのような処理が記述されているようです。
:::

:::note
これまでは $N$ が __max ノード__ で __β 値以上の子ノードの評価値が計算された場合__ は、β 狩りを行って __その子ノードの評価値__ をノードの評価値として計算していましたが、__β 値をそのノードの評価値と計算__ するという計算方法もあります。ただし、その場合は __本当の評価値 $S_N$ の下界が小さくなって範囲が広がる可能性が生じます__。

置換表を利用する場合は範囲が狭いほうが良いので、本記事ではこれまで通りの方法で計算しますが、どちらを計算しても __処理の記述の手間は変わらない__ ので __本当の評価値の下界を知る必要がない場合__ は、__どちらを計算しても構わない__ でしょう。
:::

### `ai_abs2` の実装

上記の方法で評価値を計算する AI を定義し、Check_Solved を利用して __強解決の AI であることを確認する__ ことにします。AI の関数の名前は __`ai_abs2`__ とし、αβ 法で着手を選択する AI である `ai_abs` を下記のプログラムのように修正して定義します。

なお、この手法によって __変更される__ のは、19 行目と 29 行目で __返される評価値だけ__ です。18 行目と 28 行目で __α 値や β 値を更新する処理__ は __変更しない__ 点に注意して下さい。

* __6 行目__：関数名を `ai_abs2` にする
* __11 行目__：〇 の手番の max ノードの子ノードの評価値の最大値を計算する変数 `score` を負の無限大で初期化する
* __15 行目__：子ノードの評価値を計算し、組み込み関数 `max` を利用することでこれまに計算した子ノードの評価値の最大値より大きい場合に `score` の値を更新する
* __19 行目__：このノードの評価値として α 値ではなく、子ノードの評価値の最大値である `score` を返すように修正する
* __21、25、29 行目__：× の手番の min ノードでも同様の修正を行う

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

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

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

@ai_by_score
def ai_abs2(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:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, alpha, beta))
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return score
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, alpha, beta))
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return score
                
    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, dprint
from marubatsu import Marubatsu
from copy import deepcopy

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

上記の実行後に下記のプログラムを実行すると、実行結果から __`ai_abs2` が強解決の AI である__ ことが確認できるので、__この方法で αβ 法の計算が正しく行える__ ことが確認できました。

```python
from util import Check_solved
Check_solved.is_strongly_solved(ai_abs2)
```

実行結果

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

(True, [])
```

# αβ 法の評価値の性質が全ての場合で正しいことの証明

先程説明した下記の表の性質は、ノード $N$ の __すべての子ノードの評価値が正しく計算された場合__ のものです。実際には __αβ 法で計算される子ノードの評価値__ は、ミニマックス法で計算される __正しい評価値とは異なる場合__ がありますが、そのような場合でも __αβ 法で計算された評価値__ は __常に下記の表と全く同じ性質を持ちます__。別の言葉でいうと、__任意のノード__ $N$ __で下記の表の性質が成り立ちます__。少々難しいかもしれませんが、余裕のある方はどのように証明すればよいかについて少し考えてみて下さい。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

なお、以下の証明が理解できなくても上記の性質を利用することは可能なので、意味がどうしてもわからないと思った方は、__当面は証明の理解を後回しにしてもかまわないでしょう__。

:::note
このことを証明する方法が記述された文献を見つけられなかったので、以下の証明は筆者が独自に考えたものです。そのため証明が間違っている可能性があります。もっとわかりやすい証明方法をご存じの方や間違いを見つけた方はコメントで教えて頂ければ助かります。
:::

## 証明方法

〇× ゲームのような特定の手数で必ずゲームの決着がつく __有限ゲーム__ のゲーム木に対するミニマックス法や αβ 法の評価値の計算には __以下のような特徴__ があります。

* 評価値を計算したいノードを __ルートノードとする部分木__ の __ノードの評価値を計算する__[^5]
* 有限ゲームのゲーム木には必ず __最大の深さのノードが存在__ する
* __最大の深さのノード__ はすべて決着がついた局面を表す __リーフノード__ である
* __リーフノードの評価値__ は勝敗の結果によって必ず __正しい評価値が計算__ される
* __リーフノード以外__ のノードの評価値は、__子ノードの評価値によって計算__ される

上記の性質のうち、「__最も深いノードの評価値は正しく計算できる__」、「__親ノードの評価値は子ノードの評価値によって計算される__」という特徴から、下記のような __数学的帰納法__ を使ってすべてのノードで下記の表の条件が成り立つことを証明することができます。ただし、枝狩りされたノードは αβ 法の計算には利用されないので除きます。 

1. __最も深いノード__ で下記の表の条件が成り立つことを示す
2. $i > 0$[^6] の __深さが__ $i$ __のノード__ で下記の表の条件が成り立つ場合に、__深さが__ $i-i$ __のノードでも__ 下記の表の条件が __成り立つ__ ことを示す

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

:::note
数学的帰納法とは、__連続する事柄__ が __すべて正しいこと__ を、以下の手順で証明するという手法です[^7]。最初のドミノを倒すと残りのドミノが次々と倒れていく様子に似ているので、ドミノ倒しに良く例えられるようです。

* 最初の事柄が正しいことを証明する
* ある事柄が正しければ次の事柄も正しいことを証明する

なお、数学的帰納法では一般的に無限に連続する事柄がすべて正しいことを証明しますが、今回の場合は最も深いノードから深さ 0 までの有限の事柄がすべて正しいことを証明しています。

参考までに下記に Wikipedeia のリンクを挙げておきます。
:::

https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95

## 最も深いノードで条件が成り立つことの証明

先程説明したように __最も深いノード__ には以下のような性質があります。

* __最大の深さのノード__ はすべて決着がついた局面を表す __リーフノード__ である
* __リーフノードの評価値__ は勝敗の結果によって必ず __正しい評価値が計算__ される

従って、__最も深いノード__ では __正しい評価値が計算される__ ので常に $S_N = S_N'$ となります。$S_N ≦ S_N'$ と $S_N' ≦ S_N$ は $S_N = S_N'$ __を含む__ ので、最も深いノードでは下記の表が成り立ちます。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

## 子ノードで成り立つ場合に親ノードでも成り立つことの証明

$i > 0$ の __深さが__ $i$ __のノード__ で上記の表の条件が成り立つ場合に、その親ノードである __深さが__ $i-1$ __のノードでも__ 成り立つことを証明する方法について少し考えてみて下さい。

αβ 法で評価値を計算する __ゲーム木のノード__ は以下の __8 種類に分類__ することができます。__枝狩りされたノード__ は評価値の計算に使われないので __考慮する必要はない__ ので、下記の __それ以外の 7 種類のそれぞれについて成り立つ__ ことを証明します。

* 枝狩りされたノード（以下の全ての項目は枝狩りされていないノードを表す）
* リーフノード（以下の全ての項目はリーフノード以外のノードを表す）
* max ノードで fail low
* max ノードで exact value
* max ノードで fail high
* min ノードで fail low
* min ノードで exact value
* min ノードで fail high

### リーフノードの場合

リーフノードの場合は、先程正しいことを証明済です。

### max ノードで fail low の場合

$N$ が深さ $i-1$ の __max ノードで fail low__ の場合は、下記の理由から __すべての深さが__ $i$ __の子ノードが fail low__ になります。

* $N$ は fail low なので __全ての子ノードの評価値は $α$ 以下__ である
* __αβ 法__ では __max ノード__ では __α 値__ は子ノードの評価値が __α 値より大きい場合に増加する__
* 従って $N$ の評価値を計算する際に __α 値は__ 初期値である $α$ __のまま変化しない__
* 従って $N$ の __すべての子ノード__ は以下の性質から __fail low の性質を持つ__
    * __α 値の初期値__ は $N$ __の α 値の初期値と同じ__ $α$ になる
    * 計算される __評価値は__ $α$ __以下__ である

上記から、下記の理由で $N$ が深さ $i-1$ の max ノードで fail low の場合は __下記の表の条件が成り立ちます__。

1. 数学的帰納法の証明の前提から、深さが $i$ のノードで下記の表の条件が成り立つ
2. 上記で証明したように、$N$ の __子ノードはすべて fail low__ である
3. $N$ の子ノードの深さは $i$ である
4. 2 と 3 から $N$ の __全ての子ノード評価値__ には __本当の評価値の上界が計算__ される
5. $N$ は max ノードで fail low なので、__子ノードの評価値の最大値が計算__ される
6. 複数の数値の __上界の最大値__ は、それらの __複数の数値の上界を表す__。例えば 3 つの子ノードの本当の評価値がそれぞれ「10 以下」と「20 以下」と「30 以下」と計算された場合は、その 3 つの子ノードの評価値の最大値は「30 以下」となる 
7. 4、5、6 から $N$ の評価値は __本当の評価値の上界が計算__ され下記の表の条件が成り立つ

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

### max ノードで exact value の場合

$N$ が深さ $i-1$ の __max ノードで exact value__ の場合は、$N$ の評価値として子ノードの評価値の最大値である $s_{max}$ が計算されます（$S_N' = s_{max}$）。また __その最大値は α 値の初期値と β の初期値の間__ である $α < s_{max} < β$ になります。

この時、$N$ の __子ノードは__ 以下の理由から __fail low または exact value__ になります。

* 子ノードの評価値の最大値である $s_{max}$ が β 未満なので __β 狩りは行われない__
* 従って __全ての子ノードの評価値の計算が行われる__
* max ノードでは β 値は変化しないので、__β 値は初期値である β のまま変化しない__
* $N$ の子ノードを $C$ と表記し、$C$ の評価値の計算を開始する時点での α 値を $α_C$、β 値を $β_C$、$C$ の評価値を $S_C'$ と表記する。ただし、上記から $β_C = β$ である。このとき以下から $C$ は __fail low または exact value のいずれかである__ ことがわかる
    * $S_C' ≦ α_C$ の場合。$C$ は fail low である
    * $α_C < S_C' < β_C$ の場合。$C$ は exact value である
    * $β_C ≦ S_C'$ の場合。$β_C = β$ で、$S_C' ≦ s_{max} < β$ なのでこのような場合は存在しない 

また、以下の理由から __評価値が__ $s_{max}$ である __最初の子ノードは exact value__ になります。

* __αβ 法__ では __max ノード__ での __α 値__ は、「__それまでに計算された子ノードの評価値の最大値__」と「__そのノードの α 値の初期値__」のうちの __最大値__ である
* $s_{max}$ は __子ノードの評価値の最大値__ なので、__評価値が__ $s_{max}$ である __最初の子ノードを計算する際__ の「__それまでに計算された子ノードの評価値の最大値__」は $s_{max}$ __未満__ である
* $α < s_{max}$ なので、そのノードの __α 値の初期値__ である $α$ は $s_{max}$ __未満__ である
* 従って、評価値が $s_{max}$ である __最初の子ノードを計算する際の α 値__ は $s_{max}$ __未満__ である
* 従って、評価値が $s_{max}$ である最初の子ノードを $C$ と表記すると、$α_C < S_C' < β_C$ となるので $C$ __は exact value__ である

上記から、下記の理由で $N$ が深さ $i-1$ の __max ノードで exact value__ の場合は、$N$ の評価値として計算された $S_N'$ には __必ず正しい評価値が計算されます__。

1. 数学的帰納法の証明の前提から、深さが $i$ のノードで下記の表の条件が成り立つ
2. 上記で証明したように $N$ の __子ノード__ は __fail low または exact value__ である
3. 上記で証明したように $N$ の __評価値が__ $s_{max}$ である __最初の子ノードは exact value__ である
4. $N$ の子ノードの深さは $i$ である
5. 2、3、4 から以下の理由で $N$ の __子ノードの評価値の最大値__ は __正しい値が計算__ される
    1. __評価値が__ $s_{max}$ である $N$ の __最初の子ノードは exact value__ なので、その子ノードの評価値である $s_{max}$ は __正しい評価値__ である
    2. $N$ の __他の子ノードは fail low または exact value__ なので、計算された評価値は「__正しい評価値の上界__」または「__正しい評価値__」である
    3. $N$ の __他の子ノードの評価値__ は $s_{max}$ __以下__[^8]なので、それらのノードによって計算される __評価値の上界の最大値__ は $s_{max}$ __以下__ になる
    4. $s_{max}$ と 上界が $s_{max}$ の数値の __最大値__ は $s_{max}$ である[^9]
    5. 従って、$N$ の __子ノードの評価値の最大値__ は exact value で計算された __正しい評価値__ である $s_{max}$ となる
6. $N$ は __max ノードで exact value__ なので __子ノードの評価値の最大値が計算__ される
7. 5 と 6 から $N$ の評価値 $S_N'$ には __本当の評価値が計算__ され __下記の表の条件が成り立つ__

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

### max ノードで fail high の場合

$N$ が深さ $i-1$ の __max ノードで fail high__ の場合は、$N$ の評価値として __子ノードの中で β 値以上の評価値となる最初の子ノードの評価値が計算__ されます。その子ノードを $C$ と表記した場合は、下記の理由で $C$ __は fail high__ になります。

* max ノードでは β 値は変化しないので、__β 値は初期値である β のまま変化しない__
* 従って、$C$ の評価値を計算する際の __β 値の初期値__ である $β _C$ は $N$ の β 値の初期値である __β と同じ__ になる
* $C$ __の評価値は β 値以上__ なので、$β_C ≦ S_C'$ となるので $C$  __は fail high__ である 

このことから、下記の理由から $N$ が深さ $i-1$ の __max ノードで fail high__ の場合は __下記の表の条件が成り立ちます__。

1. 数学的帰納法の証明の前提から、深さが $i$ のノードで下記の表の条件が成り立つ
2. 上記で証明したように、$N$ の評価値が計算される $C$ __は fail high__ である
3. $N$ の子ノードである $C$ の深さは $i$ である
4. 2 と 3 から $C$ の評価値には __本当の評価値の下界__ が計算される
5. $N$ の評価値には $C$ __の評価値が計算__ されるので、__本当の評価値の下界が計算__ され、__下記の表の条件が成り立つ__

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

### min ノードの場合

__min ノード__ の場合はいずれの場合でも __max ノードと同様の手順で証明を行うことが出来る__ ので、その証明は省略します。興味がある方は証明を行ってみて下さい。

以上から必要な条件がすべて証明されたので、__全ての__ $N$ に対して __下記の表の条件が成り立つ__ ことが示されました。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

## ルートノードで正しい評価値が計算される理由

__ルートノードで正しい評価値が計算される理由__ は、__上記の表__ によっても __説明することが出来ます__。その方法について少し考えてみて下さい。

__ルートノード__ では __α 値と β 値__ として __負の無限大と正の無限大を設定__ して計算を行ないます。これまでの例で計算した __評価値は必ずその範囲に収まる__ ので、__ルートノードは exact value の性質を持ちます__。従ってルートノードでは必ず正しい評価値が計算されます。

また、[以前の記事](https://qiita.com/ysgeso/items/b90305993d682ff16793#%CE%B1-%E5%80%A4%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E5%88%9D%E6%9C%9F%E5%80%A4%E3%81%AE%E5%A4%89%E6%9B%B4%E3%81%AB%E3%82%88%E3%82%8B%E6%9E%9D%E7%8B%A9%E3%82%8A)で紹介した __ルートノード__ で __α 値と β 値の初期値__ として __評価値の最小値と最大値を設定__ する場合も下記の理由で __正しい評価値が計算されます__。

* __fail low__ になった場合は __正しい評価値の上界が計算__ されるが、以下の理由で __評価値の最小値が計算__ され、それは __正しい評価値である__
    * __α 値の初期値__ は __評価値の最小値__ である
    * α 値の初期値未満の評価値が計算された場合は、__正しい評価値__ が __評価値の最小値未満である__ と計算されたことになり __矛盾する__
    * 従って __fail low__ になった場合の評価値は __評価値の最小値が計算__ される
    * 評価値が __評価値の最小値未満になることはない__ ので、計算された評価値は __正しい評価値である__
* __fail high の場合も同様__ に評価値の最大値が正しい評価値として計算される
* 従って、__ルートノードでは必ず正しい評価値が計算される__

__α 値と β 値の初期値__ として __評価値の最小値と最大値を設定__ する場合の `ai_abs3` という AI を下記のプログラムのように定義し、強解決の AI であるかを確認してみることにします。なお、`ai_abs2` では評価値として -1 ~ 1 の範囲の値を計算します。

* __2 行目__：関数の名前を修正する
* __3 行目__：α 値と β 値の初期値を評価値の最小値と最大値である -1 と 1 にする

```python
1  @ai_by_score
2  def ai_abs3(mb, debug=False):   
元と同じなので省略              
3      score = ab_search(mb, -1, 1)
4      dprint(debug, "count =", count)
5      if mb.turn == Marubatsu.CIRCLE:
6          score *= -1
7      return score
```

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

```python
@ai_by_score
def ai_abs3(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:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, alpha, beta))
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return score
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, alpha, beta))
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return score
                
    score = ab_search(mb, -1, 1)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
@ai_by_score
-def ai_abs2(mb, debug=False):   
+def ai_abs3(mb, debug=False):   
元と同じなので省略     
-   score = ab_search(mb)
+   score = ab_search(mb, -1, 1)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

上記の実行後に下記のプログラムを実行すると、実行結果から __`ai_abs2` が強解決の AI である__ ことが確認できるので、__この方法で αβ 法の計算が正しく行える__ ことが確認できました。

```python
Check_solved.is_strongly_solved(ai_abs3)
```

実行結果

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

(True, [])
```

# 今回の記事のまとめ

今回の記事では αβ 法で計算された評価値が下記の表の性質を持つことを証明しました。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | 本当の評価値は $S'_N$ 以下<br>本当の評価値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | 本当の評価値は $S'_N$ 以上<br>本当の評価値の下界がわかる| fail high |

次回の記事ではこの性質を利用した効率の良い置換表を利用した αβ 法の実装を行うことにします。

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

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

# 次回の記事

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

[^1]:$s_{max}$ を直接求めることが出来るのは max ノードで $α < s_{max} < β$ の場合だけです
[^2]:αβ 法でこの場合の事を exact value と表記する例を見つけられなかったので、αβ 法でのこの場合に使われる正式な用語ではないと思います。正式な用語をご存じの方がいればコメントで教えて頂ければ助かります。なお、評価値が確定するので、確定値と呼ぶ場合もあるようです
[^3]:これらは αβ 法で実際に用いられている用語です。fail low と fail high という用語が付けられた由来については、今後の記事で説明する予定です
[^4]:先程では max ノードの場合は本当は $S_N = α$ であるのを $S_N ≦ α$ と表記していました
[^5]:ミニマックス法ではすべてのノードの評価値を計算しますが、αβ 法では枝狩りが行われるため一部のノードの評価値だけを計算します
[^6]:深さが 0 のルートノードには親ノードは存在しないのでこの条件が必要になります
[^7]:数学的帰納法という名前から誤解されがちですが、この手法は問題の証明を問題の前提から論理的に導き出しているので[演繹法](https://qiita.com/ysgeso/items/d7f60ba34f167f77a87e#%E6%BC%94%E7%B9%B9%E6%B3%95)です
[^8]:$s_{max}$ の評価値を持つ子ノードが複数存在する場合があるので、未満ではなく以下になります
[^9]:例えば「10」と「10 以下の数値」の最大値は「10」になります