Pythonで〇×ゲームのAIを一から作成する　その154　ミニマックス値の下界と上界を記録する置換表を利用した αβ 法

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/523e03ff877cb033889b

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

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

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

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

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

# αβ 法が計算する評価値の意味のおさらいと用語の修正

前回の記事では、__αβ 法が計算する評価値__ が下記の表の意味を持つことを示しました。

なお、前回の記事では __ミニマックス法で計算された評価値__ のことを __本当の評価値と表記していました__ が、その表記はわかりづらい点と __ミニマックス値という用語が使われる場合がある__ ようなので、今回の記事からは __ミニマックス値__ と表記することにします。また、__αβ 法で計算された評価値__ のことを __αβ 値__ と表記することにします。

| $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 |

なお、上記の表の記号や用語の意味は以下の通りです。下界と上界の詳細については[前回の記事](https://qiita.com/ysgeso/items/523e03ff877cb033889b#%CE%B1%CE%B2-%E6%B3%95%E3%81%A7%E6%B1%82%E3%82%81%E3%82%89%E3%82%8C%E3%82%8B%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%A8%E6%9C%AC%E5%BD%93%E3%81%AE%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E9%96%A2%E4%BF%82)を参照して下さい。

| 記号、用語 | 意味 |
|:--|:--|
| $N$ | αβ 法で評価値を計算するノード  |
| α、β  | $N$ の評価値を計算する際の α 値と β 値の初期値  |
| $S_N$  |  ミニマックス法で計算した $N$ の本当の評価値である __ミニマックス値__  |
| $S_N'$  | αβ 法で計算した $N$ の __αβ 値__。ミニマックス値とは異なる場合がある  |
| 下界  |  ある値がとりうる値の最小値以下の値。英語では __lower bound__<br>ある値が __少なくとも下界以上の値__ であることを意味する<br>最小値と異なり、ある値が下界の値を実際に取るとは限らない|
| 上界  |  ある値がとりうる値の最大値以上の値。英語では __upper bound__<br>ある値が __少なくとも上界以下の値__ であることを意味する<br>最大値と異なり、ある値が上界の値を実際に取るとは限らない<br>下界と上界によって __ある値が少なくともその範囲内にある__ ことがわかる |
| fail low | αβ 法で計算された値が __α 値の初期値以下__ の場合で、__ミニマックス値の上界が計算された__ ことを表す用語[^1] |
| exact value | αβ 法で計算された値が __α 値と β 値の初期値の間__ の場合で、__ミニマックス値が計算された__ ことを表す用語[^2] |
| fail high | αβ 法で計算された値が __α 値の初期値以上__ の場合で、__ミニマックス値の下界が計算された__ ことを表す用語[^1] |

:::note
下界と上界は最小値、最大値と __混同されやすい__ ので改めて補足します。

上界は、ある値が __少なくともその値以下である__ を意味し、最大値と異なり上界以下の値で、__実際に取ることはない値が存在する可能性があります__。

上界は現実の世界では何らかの値の __正確な最大値や上限がわからない場合__ に、少なくともその値以下であるということを示す値として良く使われます。例えば __人間の年齢__ の __正確な最大値わかりません__ が、__実際にはあり得ない__ 200 才のような __年齢を上界__ として、__少なくとも 200 才以下であると表現する__ ことがあります[^3]。
:::

## α 値と β 値の関係に関する補足

前回の記事で説明し忘れたことがあったことに気づいたので補足します。

上記の表では __exact value__ の範囲を $α < S'_N < β$ と記述していますが、この式は $α < β$ であるという意味を表しているので、この表は $α < β$ __という条件が成り立つことを前提__ に作られています。__α 値と β 値の初期値が等しい場合について考えなくても良いのだろうか__ と思った人がいるかもしれませんが、下記のような理由から、__α 値と β 値の初期値が等しくなることは通常はありません__。

* __ルートノード__ の __α 値と β 値の初期値__ は __通常は__ $α < β$ __という関係がある__。その理由についてはこの後で説明する
* max ノードでは α 値は子ノードの評価値が α 値を超えた場合に更新されるが、子ノードの評価値が β 値以上になった時点で β 狩りが行われるので、__α 値が β 値以上になった状態で子ノードの評価値が計算されることはない__
* min ノードでも同様の理由で、β 値が α 値以下になった状態で子ノードの評価値が計算されることはない
* 従って、__ルートノード以外__ のノードでも $α < β$ __という関係がある__

__ルートノード__ の __α 値と β 値の初期値__ が __通常は__ $α < β$ __となる理由__ は以下の通りです。

* αβ 法でルートノードの本当の評価値である __ミニマックス値を計算する__ ためには、評価値の範囲が __exact value の範囲に含まれる__ 必要がある。従って、ルートノードの __α 値と β 値の初期値の範囲__ は __評価値の最小値から最大値の範囲を含む__ 必要がある
* ルートノードの __α 値と β 値の初期値が等しい場合__ は、__評価値の範囲が特定の値である__ ことが __あらかじめわかっている__ ということなので、そのような場合はそもそも __αβ 法で評価値を計算する必要がない__
* 従って、ルートノードでミニマックス値を計算する場合は __通常は α 値と β 値の初期値は異なる値になる__ ので、$α < β$ である

:::note warn
今回の記事では __α 値と β 値の初期値__ の間に $α < β$ __という関係が成り立つことを前提__ に説明を行います。
:::

:::note
上記は __ルートノードのミニマックス値を計算する__ という前提での話なので、ルートノードの __ミニマックス値を計算する必要がない場合__ は、α 値と β 値の初期値を __等しく設定してもかまいません__。実際に α 値と β 値の初期値を等しく設定して αβ 法で評価値を計算することがあり、そのような場合のことを null window search と呼びます。null window search の意味や使い方については今後の記事で紹介します。
:::

# ミニマックス値の下界と上界を記録する置換表

[以前の記事](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 のキーを __局面__ と __α 値の初期値__ と __β 値の初期値__ を表す tuple とし、そのキーの値にその場合に αβ 法で計算された評価値を記録しましたが、その方法では __[置換表による枝狩りの効率が悪い](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)__ という問題がありました。

枝狩りを効率よく行うため方法として、置換表を表す dict の キーを __局面だけ__ のデータに戻し、キーの値には αβ 法で計算された __ミニマックス値がとりうる範囲を記録__ するという方法があります。具体的には置換表のキーの値には αβ 法で計算された評価値 $S_N'$ の値の __分類に応じて__、ミニマックス値の __下界__ と __上界__ を下記の表のように記録します。

| 分類 | 下界 | 上界 | 意味 |
|:--|:--|:--|:--|
| fail low | 負の無限大  | $S_N'$  |  ミニマックス値は $S_N'$ 以下  |
| exact value  | $S_N'$  | $S_N'$  | ミニマックス値は $S_N'$  |
| fali high  | $S_N'$  | 正の無限大  | ミニマックス値は $S_N'$ 以上  |

下界と上界の用語の意味から、__ミニマックス値__ は少なくとも __下界以上__ かつ __上界以下__ の __範囲の値__ になります。そこで、__fail low__ の場合は __下界に負の無限大__ を設定することで、ミニマックス値は __上界に記録した__ $S_N'$ __以下__ であるという意味になります。fail high の場合も同様です。__exact value__ の場合は __下界と上界に__ $S_N'$ __を記録する__ ことで、__ミニマックス値__ は $S_N'$ 以上 $S_N'$ 以下、すなわち $S_N'$ __である__ ことを表すことになります。

:::note
__fail low__ ではミニマックス値がとりうる範囲は少なくとも $S_N'$ 以下なので __数学的__ には __下界は存在しません__。従って、上記の表のように __負の無限大を下界に設定__ するのは __数学的には正しい表現ではありません__。

ただし、__下界を負の無限大と考える__ ことで $S_N'$ __以下の範囲__ を __プログラムでうまく表現できる__ ので数学的には正しくはありませんが、__プログラム__ ではこのような場合に __下界として負の無限大を設定する__ ことが良くあります。

なお、評価値の最小値がわかっている場合は下界を負の無限大ではなく、評価値の最小値と設定することもできます。

余談ですが、数学では下界が存在することを、下に有界と表現します。
:::

## `ai_abs_tt2` の定義

置換表に記録するデータがわかったので、__ミニマックス値の下界と上界を範囲を記録する置換表__ を利用した __αβ 法__ で着手を選択する __`ai_abs_tt2`__ という __AI の関数を定義__ を、[以前の記事](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)で定義した 3 つのデータをキーとする置換表を利用した αβ 法で着手を選択する AI である __`ai_abs_tt`__ を修正して定義することにします。

まず、ノードの評価値が確定した際に __置換表にミニマックス値の下界と上界を記録する処理__ から実装します。また、`ai_abs_tt` では __max ノードで fail low 場合__ の評価値を α 値として計算していましたが、[前回の記事](https://qiita.com/ysgeso/items/523e03ff877cb033889b#%CE%B1%CE%B2-%E6%B3%95%E3%81%A7%E3%81%AE%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95%E3%81%AE%E3%83%90%E3%83%AA%E3%82%A8%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3)で説明したように __子ノードの評価値の最大値__ を計算したほうがミニマックス値の上界が小さくなって __範囲が狭くなる__ ので、そのように修正します。min ノードで fail heigh の場合も同様です。

* __6 行目__：関数の名前を `ai_abs_tt2` に修正する
* __10 ~ 12 行目__：置換表に局面のデータが登録されていた場合の処理についてはまだ解説していないので、この部分をコメントにして後から修正することにする
* __13、14 行目__：置換表に登録するミニマックス値の下界と上界を計算するためには __α 値と β 値の初期値が必要__ となるので、それらの値を変数に記録する
* __18、22 行目__：元のプログラムでは max ノードの場合は α 値を評価値として計算していたが、__子ノードの評価値の最大値を評価値として計算する__ ように修正するために、18 行目で `score` という変数を負の無限大で初期化し、22 行目で組み込み関数 `max` を利用して `score` の値をこれまでに計算した子ノードの評価値の最大値に更新する。なお、25 行目の __α 値を更新する所に変更はない__ が、23 行目と 25 行目の下にあった __`score` に α 値を代入する処理は削除する必要がある__ 点に注意すること
* __27、31 行目__：min ノードでも同様の修正を行う
* __39 ~ 47 行目__：__このノードの評価値と α 値と β 値の初期値を比較__ し、__ミニマックス値__ の __下界__（lower bound）と __上界__ （upper bound）を __先程の表に従って計算__ する
* __49、50 行目__：置換表の __同一局面を表すキーの値__ に __`(下界, 上界)`__ という __ミニマックス値の下界と上界を表す tuple__ を代入する

```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_abs_tt2(mb, debug=False, shortest_victory=False):   
 7      count = 0
 8      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 9          boardtxt = mborig.board_to_str()
10          # key = (boardtxt, alpha, beta)
11          # if key in tt:
12          #     return tt[key]
13          alphaorig = alpha
14          betaorig = beta
15  
16          legal_moves = mborig.calc_legal_moves()
17          if mborig.turn == Marubatsu.CIRCLE:
18              score = float("-inf")
19              for x, y in legal_moves:
20                  mb = deepcopy(mborig)
21                  mb.move(x, y)
22                  score = max(score, ab_search(mb, tt, alpha, beta))
23                  if score >= beta:
24                      break
25                  alpha = max(alpha, score)
26          else:
27              score = float("inf")
28              for x, y in legal_moves:
29                  mb = deepcopy(mborig)
30                  mb.move(x, y)
31                  score = min(score, ab_search(mb, tt, alpha, beta))
32                  if score <= alpha:
33                      break
34                  beta = min(beta, score)   
35              
36          from util import calc_same_boardtexts
37  
38          boardtxtlist = calc_same_boardtexts(mborig)
39          if score <= alphaorig:
40              lower_bound = float("-inf")
41              upper_bound = score
42          elif score < betaorig:
43              lower_bound = score
44              upper_bound = score
45          else:
46              lower_bound = score
47              upper_bound = float("inf")
48          for boardtxt in boardtxtlist:
49              tt[boardtxt] = (lower_bound, upper_bound)
50          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_abs_tt2(mb, debug=False, shortest_victory=False):   
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        boardtxt = mborig.board_to_str()
        # key = (boardtxt, alpha, beta)
        # if key in tt:
        #     return tt[key]
        alphaorig = alpha
        betaorig = beta

        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, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        boardtxtlist = calc_same_boardtexts(mborig)
        if score <= alphaorig:
            lower_bound = float("-inf")
            upper_bound = score
        elif score < betaorig:
            lower_bound = score
            upper_bound = score
        else:
            lower_bound = score
            upper_bound = float("inf")
        for boardtxt in boardtxtlist:
            tt[boardtxt] = (lower_bound, upper_bound)
        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_tt(mb, debug=False, shortest_victory=False):   
+def ai_abs_tt2(mb, debug=False, shortest_victory=False):   
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        boardtxt = mborig.board_to_str()
-       key = (boardtxt, alpha, beta)
-       if key in tt:
-           return tt[key]
+       # key = (boardtxt, alpha, beta)
+       # if key in tt:
+       #     return tt[key]
+       alphaorig = alpha
+       betaorig = beta

        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, tt, alpha, beta)
+               score = max(score, ab_search(mb, tt, alpha, beta))
                if score >= beta:
-                   alpha = score
                    break
                alpha = max(alpha, score)
-           score = alpha
        else:
+           score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = ab_search(mb, tt, alpha, beta)
+               score = min(score, ab_search(mb, tt, alpha, beta))
                if score <= alpha:
-                   beta = score
                    break
                beta = min(beta, score)   
-           score = beta
            
        from util import calc_same_boardtexts

        boardtxtlist = calc_same_boardtexts(mborig)
+       if score <= alphaorig:
+           lower_bound = float("-inf")
+           upper_bound = score
+       elif score < betaorig:
+           lower_bound = score
+           upper_bound = score
+       else:
+           lower_bound = score
+           upper_bound = float("inf")
-       _, alpha, beta = key
        for boardtxt in boardtxtlist:
-           tt[(boardtxt, alpha, beta)] = score
+           tt[boardtxt] = (lower_bound, upper_bound)
        return score
元と同じなので省略                
```
</details>

:::note 
これまでの記事では下界と上界という用語を使って説明を行っていませんでしたが、プログラムでは __様々なアルゴリズム__ でを __下界と上界を計算しています__。

例えば、`ai_abs_tt2` で子ノードの評価値の __最大値を計算__ する際に行う下記のアルゴリズムでは、実は __途中の計算__ では少なくとも最大値はその値以上であるという __最大値の下界を計算__ しており、下界の値を __最大値に近づけていくように更新していく__ という方法で最大値を計算しています。

* 最大値を計算する変数の __初期値に負の無限大を代入__ する
* 子ノードの評価値が __その変数より大きい場合__ に __変数の値を更新する__
:::

## 局面の情報が置換表に登録されている場合の処理

次に、局面のミニマックス値の下界と上界が __置換表に登録されている場合__ の __ノードの処理を記述__ する必要があります。なお、「局面のミニマックス値の下界と上界」という表記は長いので以後は「__評価値の範囲__」と表記することにします。また、「ミニマックス値の上界」と「ミニマックス値の下界」を単に「__上界__」や「__下界__」と表記することにします。

具体的には、下記のプログラムの 5 行目の if 文のブロックの部分を記述します。

```python
1  @ai_by_score
2  def ai_abs_tt2(mb, debug=False, shortest_victory=False):  
省略
3          boardtxt = mborig.board_to_str()
4          if boardtxt in tt:
5              置換表にこのノードの評価値の範囲が登録されている場合の処理
省略
```

## 下界と上界が等しい場合

__下界と上界が等しい場合__ は、その局面の __ミニマックス値そのもの__ が置換表に記録されているという意味を表すので、その場合は下記のプログラムのように __下界__（上界でも良い）の値をそのノードの __評価値として返す__ という処理を行います。

具体的には下記のプログラムのように記述します。

* __2 行目__：置換表からその局面の下界と上界のデータを取り出す
* __3、4 行目__：下界と上界が等しい場合は下界を評価値として返す

```python
1  if boardtxt in tt:
2      lower_bound, upper_bound = tt[boardtxt]
3      if lower_bound == upper_bound:
4          return lower_bound
```

## 下界と上界が等しくない場合の考え方

下界と上界が __等しくない場合__ は、__下界__、__上界__、そのノードの __α 値の初期値__、__β 値の初期値__ という __4 つの値の大小関係__ によって __行う処理が変化する__ ので、その __大小関係の場合分け__ を行い、__それぞれの場合について行う処理を検討__ する必要があります。どのような場合分けがあるかについて少し考えてみて下さい。

:::note
このような場合分けの計算に慣れている人は、本記事で行うような詳細な場合分けを行なわなくても、どのような処理を記述すれば良いかを頭の中だけで考えることができるかもしれませんが、慣れないうちは難しいと思います。頭の中だけで考えることが難しいと思った方はこの後で説明するような __場合分けを紙などに書いて整理することで行う処理を検討する__ ことをお勧めします。
:::

表記を簡潔にするために __下界（lower bound）を頭文字を取って__ $l$、__上界（upper bound）を__ $u$、__α 値の初期値を__ $α$、__β 値の初期値を__ $β$ と表記することにします。

## 検討の前提条件

場合分けを行う際の __前提__ として[先程説明](#%CE%B1-%E5%80%A4%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E9%96%A2%E4%BF%82%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E8%A3%9C%E8%B6%B3)したように __α 値と β 値の間__ には $α < β$ __という関係__ があります。また、__下界と上界の間__ には $l ≦ u$ という関係がありますが、__下界と上界が等しい場合については既に検討済__ なので、$l < u$ __の場合について考える__ 必要があります。

:::note warn
検討の __前提条件__ として __下記の 2 つの式が成り立つ__

* $α < β$
* $l < u$
:::

### α、β、l の関係の場合分け

$α$、$β$、$l$、$u$ の __4 つの値の場合分けをいきなり行う__ のは慣れていても __難しい__ と思いますので、最初に $α$、$β$、$l$ の __3 つの値の関係の場合分けを行い__、その後で $u$ __を追加__ するという手順で場合分けを行うと良いでしょう。

$α < β$ という条件が成り立つので、$α$、$β$、$l$ の関係は以下の __5 通りの場合分け__ を行うことができます。

1. $l < α < β$
2. $l = α < β$
3. $α < l < β$
4. $α < β = l$
5. $α < β < l$

:::note
頭の中だけで上記の場合分けの式を思い浮かべるのが難しいと思った方は、下図のような図を書いて __緑色の__ $l$ __を表す点__ を __左から右にずらしていく__ と、以下のような 5 つの場合に分けられることがわかると思います。それを数式で表したのが 上の 5 つの場合分けの式です。なお、$α$ の点が $β$ の点より左にあるのは $α < β$ という前提条件があるからです

* 緑色の点が赤い点より左にある
* 緑色の点が赤い点と重なる
* 緑色の点が赤い点と青い点の間にある
* 緑色の点が青い点と重なる
* 緑色の点が青色の点の右にある

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9162963d-a7c1-4230-a02b-93564203f1e8.png" width="300">
:::

## α、β、l、u の関係の場合分け

次に、上記のそれぞれの場合について、$u$ __を加えた関係の場合分け__ を行ない、__それぞれの場合__ について __行う処理を考える__ ことにします。

:::note
この時点で場合分けが多くて大変だと思っている人がいるかもしれませんが、作業を行っているうちに __法則が見えてくる__ 場合が良くあります。そのような場合は、__途中で残りの場合分けの検討を省略する__ ことできます。
:::

### l < α < β の場合

$l < u$ であることから $l < α < β$ の場合に $u$ を加えると、以下の __5 通りに場合分けを行う__ ことができます。

1. $l < u < α < β$
2. $l < u = α < β$
3. $l < α < u < β$
4. $l < α < β = u$
5. $l < α < β < u$

下図は最初の $l < u < α < β$ の場合を図にしたものです。下図では __赤い矢印の範囲__ が __評価値の範囲__、__灰色__ で塗りつぶされた範囲が __fail low__、__薄黄色__ で塗りつぶされた範囲が __exact value__、__水色__ で塗りつぶされた範囲が __fail high__ を表します。ただし、__赤い矢印の範囲は両端の値を含み__、__fail low__ の範囲は α __を含み__、__fail high__ の範囲は β を __含みます__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7b7d56a3-f949-46de-8940-9ce7d87274cd.png" width="300">

上図では、__赤い矢印__ の __評価値の範囲__ が __すべて fail low の範囲に含まれる__ ことから、このノードの評価値は __fail low になることが確定__ します。__αβ 法__ では __fail low__ の場合は __α 値以下のどのような評価値を計算__ しても __ルートノードの評価値の計算に影響を与えない__ ので、このノードの評価値として __fail low になる値を返してもかまいません__。また、fail low で計算される評価値は、__ミニマックス値の上界__ を意味するので、この場合は置換表に記録されていた __ミニマックス値の上界を表す__ $u$ __を返り値として返せば良い__ ことになります。

:::note
置換表に記録されていない値を利用せずに、通常の場合と同様に __子ノードの評価値からノードの評価値を計算した場合__ は、fail low の評価値として $u$ __以下の値が計算__ されます。従って、__置換表を利用__ した場合は __枝狩りの効率が高くなる__ という利点がある反面、利用しない場合と比較して fail low で計算される __ミニマックス値の範囲が広く、精度が低くなる場合がある__ という欠点が生じます。ただし、このような欠点があっても、__ルートノードの評価値は正しく計算される__ のでこの欠点は大きな問題ではありません。
:::

$l < u = α < β$ の場合は上図で $u$ __と__ $α$ __が重なる__ ことになりますが、__fail low の範囲に__ $α$ __は含まれる__ ので、その場合でも __このノードは fail low__ になることが __確定します__。従ってこの場合も上記と同様に、上界を表す $u$ __を返り値として返せば良い__ ことになります。

$l < α < u < β$ の場合は下図のように __赤い矢印の範囲__ は、__fail low__ と __exact value__ の __両方の範囲に重なっています__。従って、このノードの __ミニマックス値__ は fail low と exact value の __いずれかの値__ になりますが、__exact value__ の評価値は __必ず正しく計算する必要がある__ ため、置換表に記録されている __範囲がある評価値__ から、__このノードの評価値を計算することはできません__。従って、通常の場合と同様に __子ノードの評価値からこのノードの評価値を計算する必要__ があります。その際に __枝狩りが行われやすくなるような工夫__ を行なうことができます。どのような工夫を行なうことができるかについて少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1178c8ab-7863-4123-9160-ac1709bc2de3.png" width="300">

具体的には下記のような理由から、下図のように __β 値の初期値を $u$ に変更して exact value の範囲を縮小__ することが出来ます。αβ 法では、ノードの種類によって α 値以下または β 値以上の評価値が計算された場合に枝狩りを行うので、__exact value の範囲__ を下図のように __縮小する__ ことで、__枝狩りの効率を上げる__ ことが出来ます。

* 上図の __赤い矢印__ は、このノードの __ミニマックス値のとりうる範囲__ を表している
* 従って、__exact value の範囲の中__ で、__赤い矢印の範囲に含まれていない__ $u$ __から__ $β$ __の範囲__ の値が、このノードの評価値として __計算されることは決してない__
* そのため、下図のように __β 値を__ $u$ __に変更__ して __exact value の範囲を縮小__ しても αβ 法の評価値を __正しく計算することができる__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8c9157cc-6cfc-41de-93e9-5c5be3a6f628.png" width="300">

:::note
上記の説明の中の下記の点について疑問に思った方はいないでしょうか？

* $β$ を $u$ に変更する前の __2 つ上の図__ では $u$ __は exact value の範囲内__ にある
* __fail high は__ $β$ __を含む__ ので、$β$ を $u$ に変更した後の __上図__ では $u$ __が fail high の範囲に変化__ している
* $u$ __は赤い矢印の範囲に含まれる__ ので、このノードでは $u$ __が評価値として計算される可能性がある__
* その場合は __計算された評価値の意味__ が、$β$ を $u$ に __変更する前と後で__ は以下のように __変化してしまう__ という問題が発生する
    * __変更する前__ は $u$ は exact value なので __ミニマックス値が計算__ される
    * __変更した後__ は $u$ は fail high なので __ミニマックス値の下界が計算__ される
 
一見すると __修正前と後で異なる意味の評価値が計算される__ ので問題があるように見えるかもしれませんが、実際にはこのことは問題ではありません。その理由は、以下の通りです。

* β 値を $u$ に変更するという処理は、__このノードの評価値の計算を行う際に行う処理__ である
* 従って、__親ノード__ でこのノードの評価値の計算を開始する際の __α 値と β 値は変更されない__
* そのため、このノードの評価値として $u$ が __fail high として計算されても__、その評価値を受け取った __親ノードでは__ $l < α < u < β$ のまま __変化していない__ ので $β$ を $u$ に変更しない場合と同様に __exact value とみなされる__
:::

$l < α < β = u$（図は省略します） と $l < α < β < u$ の場合は、下図のように赤い矢印の __評価値の範囲__ は、__fail low__、__exact value__、__fail high__ の __全ての範囲にまたがっています__。この場合は __工夫のしようがない__ ので、__α 値と β 値を変更せずに__ 通常の場合と同様の方法で子ノードの評価値からこのノードの評価値を計算する必要があります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b212d17b-bbf6-433e-b34a-9539e79a017f.png" width="300">

上記をまとめると以下の表のようになります。それぞれの列の意味は以下の通りです。

* __fl、ev、fh__：__評価値の範囲__ がそれぞれ、fail low、exact value、fail high の範囲を __含む場合は 〇__、__含まない場合は ×__ と表記する
* __評価値__：このノードの評価値
* __α 値、β 値__：このノードの評価値を子ノードの評価値から計算する際に __α 値または β 値の初期値を変更する場合の値__。空欄の場合は変更しないことを表す

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $l < u < α < β$  | 〇 | × | × | $u$  |   |  |
| $l < u = α < β$  | 〇 | × | × | $u$  |   |   |
| $l < α < u < β$  | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更  |
| $l < α < β = u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |   |
| $l < α < β < u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |   |

上記の 1、2 行目と 4、5 行目の __関係より右の列の内容はすべて同じ__ なので、上記の表を下記の表のように __まとめることができます__。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $l < u ≦ α < β$  | 〇 | × | × | $u$  |   |  |
| $l < α < u < β$  | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更  |
| $l < α < β ≦ u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |   |

:::note
上記は A、B、C を条件式とした場合に、and 演算と or 演算に対して下記の __分配法則__ が成り立つことを利用しています。

(A and C) or (B and C)

という条件が成り立つときに下記の条件が成り立つ。逆に、下記の条件が成り立つときにも上記の条件が成り立つ。

(A or B) and C


なお、分配法則は下記のように、足し算と掛け算でも成り立ちます。

$(x + y) × z$ という式は常には $x × z + y × z$ と同じである

ピンとこない人がいるかもしれませんので、少し長くなりますが参考までに先程の表の 1 行目と 2 行目がまとめられることを分配法則を使って示します。既にピンと来ている人は下記の説明を読むとかえってわからなくなるかもしれないので、下記のような式の羅列を見るのがうんざりする人は読み飛ばしても構いません。

先程の表では 下記の 2 つの __いずれかの関係が成り立つ__ ときに同じ結果になります。

* $l < u < α < β$　
* $l < u = α < β$

そのことを 1 つの式で表すと下記のようになります。

($l$ < $u$ < $α$ < $β$) or ($l$ < $u$ = $α$ < $β$) 

上記の式は下記のように書き換えることができます。

(($l$ < $u$) and ($u$ < $α$) and ($α$ < $β$)) or (($l$ < $u$) and ($u$ = $α$) and ($α$ < $β$))

and でつなげた式は順番を入れ替えることができる（[交換法則](https://ja.wikipedia.org/wiki/%E4%BA%A4%E6%8F%9B%E6%B3%95%E5%89%87)と呼びます）ので上記の式は下記のように書き換えることができます。

(($u$ < $α$) and ($l$ < $u$) and ($α$ < $β$)) or (($u$ = $α$) and ($l$ < $u$) and ($α$ < $β$))

上記の式を下記の表の記号で置き換えると以下のようになります。

(A and C) or (B and C)

| 記号 | 式 |
|:-:|:-:|
| A  | $u$ < $α$ |
| B  | $u$ = $α$ |
| C  | ($l$ < $u$) and ($α$ < $β$)  |

分配法則から上記の式は下記の式に書き換えることができます。

(A or B) and C

A と B を元に戻すと以下の式になります。

(($u$ < $α$) or ($u$ = $α$)) and C

上記の式は以下のように書き換えることができます。

($u$ ≦ $α$) and C

C を元の式に戻し、and の順番を入れ替える以下のようになります。

($l$ < $u$) and ($u$ ≦ $α$) and ($α$ < $β$)

and を取り払うと先程まとめた下記の式になります。

$l < u ≦ α < β$

参考までに分配法則の wikipedia のリンクを下記に示します。
:::

https://ja.wikipedia.org/wiki/%E5%88%86%E9%85%8D%E6%B3%95%E5%89%87

### 評価値の範囲が置換表に記録されている場合に行う処理の考察

上記では評価値の範囲が fail low に完全に含まれる場合の処理を考察しましたが、__評価値の範囲が fail high に完全に含まれる場合__ も __同様の考察__ を行うことができます。また、先程の図から、__評価値の範囲が exact value に含まれる場合__ は、評価値の範囲と exact value の範囲のうち、__共通する範囲__ を __α 値と β 値の初期値として更新__ して、__子ノードから評価値を計算__ すれば良いことがわかります。

上記をまとめると、ノードの __評価値の範囲が置換表に記録されている場合に行う処理__ は、以下のようになります。

:::note warn
* 評価値の範囲が __fail low のみ__ の場合は置換表に記録された __ミニマックス値の上界__ である $u$ __を評価値として返す__
* 評価値の範囲が __fail high のみ__ の場合は置換表に記録された __ミニマックス値の下界__ である $l$ __を評価値として返す__
* 上記のいずれでもない場合は、評価値の範囲が __正確な評価値を計算する__ 必要がある __exact value の範囲を含む__ ので、__置換表に記録__ された評価値の範囲を __そのまま利用することはできない__。評価値の範囲と exact value の範囲のうち、__共通する範囲__ を __α 値と β 値の初期値として更新__ して、__子ノードから評価値を計算__ する
:::

本記事では上記をもとに、__残りの場合で行う処理を検証__ することで、$α$、$β$、$l$、$u$ の関係から、どのような処理を行えば良いかを調べることにします。

:::note
数学が得意な方は、上記から $α$、$β$、$l$、$u$ __の関係を表す式__ を使って下記のような処理を行えば良いのではないかと考えた人がいるかもしれません。

1. $u ≦ α$ の場合に fail low になり、$u$ を評価値として返す
2. $β ≦ l$ の場合に fail high になり、$l$ を評価値として返す
3. 上記以外の場合では exact value が含まれるので $α$ と $β$ を以下のように変更して子ノードから評価値を計算する
    1. $α < l$ の場合は $α$ を $l$ に変更する
    2. $u < β$ の場合は $β$ を $u$ に変更する

上記は正しいですが、一見すると正しそうに見える __思いついた法則が実際には正しくない場合が良くある__ ので __思いついた法則が正しいかどうか__ を何らかの方法で __検証することを怠らないで下さい__。検証を怠ったせいで、__プログラムに思わぬバグが発生__ することは __良くある事__ です。

本記事では行ないませんが、上記が正しいことを証明するのはそれほど難しくはないので興味がある方は証明にチャレンジしてみて下さい。なお、本記事で行うように、__地道にすべての場合を確認する__ ことで行う処理を求めるのも、__数学的な証明方法の一つ__ です。
:::

### l = α < β の場合

$l = α < β$ の場合に $u$ を加えると、以下の __3 通りに場合分けを行う__ ことができます。

1. $l = α < u < β$
2. $l = α < β = u$
3. $l = α < β < u$

先程と同じ要領で上記を表にまとめると下記の表のようになります。$α$ は fail low、$β$ は fail high に __含まれる点に注意__ して下さい。わかりづらいと思った方はまとめる際に先ほどのような図を書くと良いでしょう。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $l = α < u < β$ | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更 |
| $l = α < β = u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |  |
| $l = α < β < u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |  |

先程と同様に、上記の表は下記の表のようにまとめることができます。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $l = α < u < β$ | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更 |
| $l = α < β ≦ u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |  |

### α < l < β の場合

$α < l < β$ の場合に $u$ を加えると、以下の __3 通りに場合分けを行う__ ことができます。

1. $α < l < u < β$
2. $α < l < β = u$
3. $α < l < β < u$

先程と同じ要領で上記を表にまとめると下記の表のようになります。$α < l < u < β$ の場合は __評価値の範囲__ は __exact value の範囲内に完全に収まります__ が、exact value は __ミニマックス値を計算する必要がある__ ので子ノードから評価値を計算する必要があります。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $α < l < u < β$  | × | 〇 | × | 子ノードから計算  | $l$ に変更  | $u$ に変更  |
| $α < l < β ≦ u$ | × | 〇 | 〇 | 子ノードから計算  | $l$ に変更  |   |

### α < β = l の場合

$α < β = l$ の場合に $u$ を加えると、$l < u$ なので下記の __1 つの場合のみが存在__ します。

1. $α < β = l < u$

先程と同じ要領で上記を表にまとめると下記の表のようになります。__評価値の範囲が β 値以上になる__ ので、このノードは __fail high__ になります。従ってこのノードの __評価値は__ $l$ __と計算すればよい__ ことがわかります。 

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $α < β = l < u$ | × | × | 〇 | $l$  |   |   |

### α < β < l の場合

$α < β < l$ の場合に $u$ を加えると、$l < u$ なので下記の __1 つの場合のみが存在__ します。

1. $α < β < l < u$

先程と同じ要領で上記を表にまとめると下記の表のようになります。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $α < β < l < u$ | × | × | 〇 | $l$  |   |   |

## 評価値の範囲が置換表に登録されている場合の処理のまとめ

すべての場合で行う処理がわかったので、評価値の範囲が置換表に登録されている場合に __行う処理をまとめる__ ことにします。

### 表の整理

現状ではそれぞれの場合の表がばらばらになっているので __一つの表にまとめる__ 必要があります。下記は、上記の表をまとめた表ですが、__行数が多くてわかりづらい__ ので __整理する__ ことにします。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $l < u ≦ α < β$  | 〇 | × | × | $u$  |   |  |
| $l < α < u < β$  | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更  |
| $l < α < β ≦ u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |   |
| $l = α < u < β$ | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更 |
| $l = α < β ≦ u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |  |
| $α < l < u < β$  | × | 〇 | × | 子ノードから計算  | $l$ に変更  | $u$ に変更  |
| $α < l < β ≦ u$ | × | 〇 | 〇 | 子ノードから計算  | $l$ に変更  |   |
| $α < β = l < u$ | × | × | 〇 | $l$  |   |   |
| $α < β < l < u$ | × | × | 〇 | $l$  |   |   |

まず、__関係より右の列が同じ行__ を __まとめて整理する__ ことにします。そのために、上記の表で関係より右の列が __同じ行が並ぶように並べ替える__ と下記の表のようになります。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $l < u ≦ α < β$  | 〇 | × | × | $u$  |   |  |
| $l < α < u < β$  | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更  |
| $l = α < u < β$ | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更 |
| $l < α < β ≦ u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |   |   |
| $l = α < β ≦ u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |  |
| $α < l < u < β$  | × | 〇 | × | 子ノードから計算  | $l$ に変更  | $u$ に変更  |
| $α < l < β ≦ u$ | × | 〇 | 〇 | 子ノードから計算  | $l$ に変更  |   |
| $α < β = l < u$ | × | × | 〇 | $l$  |   |   |
| $α < β < l < u$ | × | × | 〇 | $l$  |   |   |

上記の表で、__関係より右の列が同じ行をまとめる__ と下記の表のようになります。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $l < u ≦ α < β$  | 〇 | × | × | $u$  |   |  |
| $l ≦ α < u < β$  | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更  |
| $l ≦ α < β ≦ u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |   |   |
| $α < l < u < β$  | × | 〇 | × | 子ノードから計算  | $l$ に変更  | $u$ に変更  |
| $α < l < β ≦ u$ | × | 〇 | 〇 | 子ノードから計算  | $l$ に変更  |   |
| $α < β ≦ l < u$ | × | × | 〇 | $l$  |   |   |

$l < u ≦ α < β$ は「$l < u$ __なおかつ__ $u ≦ α$ __なおかつ__ $α < β$」という意味の式です。この 3 つの式の中で $l < u$ と $α < β$ は __必ず成り立つ__ という前提があるため __取り除くことができる__ ので、この式は $u ≦ α$ __という式で置き換えるこ__ とができます。__他の関係の式__ も同様に $l < u$ と $α < β$ __という条件を取り除く__ と上記の表は下記の表のようになります。

| 関係 | fl | ev | fh | 評価値 | α 値 | β 値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $u ≦ α$  | 〇 | × | × | $u$  |   |  |
| $l ≦ α < u < β$  | 〇 | 〇 | × | 子ノードから計算  |   | $u$ に変更  |
| $l ≦ α$ なおかつ $β ≦ u$  | 〇 | 〇 | 〇 | 子ノードから計算  |   |   |   |
| $α < l$ なおかつ $u < β$  | × | 〇 | × | 子ノードから計算  | $l$ に変更  | $u$ に変更  |
| $α < l < β ≦ u$ | × | 〇 | 〇 | 子ノードから計算  | $l$ に変更  |   |
| $β ≦ l$ | × | × | 〇 | $l$  |   |   |

### fail low、fail high の場合の処理の記述

上記の表から、以下の事がわかります。

* $u ≦ α$ の場合に __fail low__ になり、$u$ __を評価値として返す__
* $β ≦ l$ の場合に __fail high__ になり、$l$ __を評価値として返す__
* 上記以外の場合では __exact value が含まれる__ ので $α$ と $β$ を __必要に応じて変更__ して __子ノードから評価値を計算__ する

上記の処理を __プログラムで記述__ すると下記のようになります。

* __3、4 行目__：$u ≦ α$ の場合に評価値として $u$ を計算する
* __5、6 行目__：$β ≦ l$ の場合に評価値として $l$ を計算する
* __7、8 行目__：上記のいずれでもない場合に α 値と β 値を更新する処理を記述する。また、8 行目の処理の中で __return 文を記述しない__ ようにすることで、__この後__ で __更新された α 値と β 値を使って__ 子ノードの評価値からこのノードの評価値を計算する処理が行われる

```python
1  if boardtxt in tt:
2      lower_bound, upper_bound = tt[boardtxt]
3      if upper_bound <= alpha:
4          return upper_bound
5      elif beta <= lower_bound:
6          return lower_bound
7      else:
8          必要に応じて α 値と β 値を更新する処理を記述する
```

### exact value が含まれる場合の処理の記述

上記の __8 行目で行う処理を記述するため__ には、__どのような場合に α 値と β 値をどのように更新すればよいかを明確にする__ 必要があります。そこで、まず、__α 値の更新に関して検証する__ ことにします。

上記の 8 行目は子ノードの評価値を計算する場合の処理なので、先程の表から「__子ノードから計算__」が表記された行を __取り出す必要__ があります。また、__α 値を更新する条件について知りたい__ ので、「__関係__」、「__評価値__」、「__α 値__」の __列のみを取り出した表を作る__ と下記の表のようになります。

| 関係 | 評価値 | α 値 |
|:-:|:-:|:-:|
| $l ≦ α < u < β$  | 子ノードから計算  |   |
| $l ≦ α$ なおかつ $β ≦ u$  | 子ノードから計算  |   |
| $α < l$ なおかつ $u < β$  | 子ノードから計算  | $l$ に変更  |
| $α < l < β ≦ u$ | 子ノードから計算  | $l$ に変更  |

上記の 8 行目は $u ≦ α$ __でも__、$β ≦ l$ __でもない場合に実行される__ ので、$u > α$、$β > l$ __という条件は必ず満たされます__。従って、上記の表の __「関係」の式からそれらの条件を取り除く__ と下記の表のようになります。

| 関係 | 評価値 | α 値 |
|:-:|:-:|:-:|
| $l ≦ α$ なおかつ $u < β$  | 子ノードから計算  |   |
| $l ≦ α$ なおかつ $β ≦ u$  | 子ノードから計算  |   |
| $α < l$ なおかつ $u < β$  | 子ノードから計算  | $l$ に変更  |
| $α < l$ なおかつ $β ≦ u$ | 子ノードから計算  | $l$ に変更  |

$u < β$ __または__ $β ≦ u$ という条件は __常に成り立つ__ ので、上記の表は以下の表のようにまとめることができます。

| 関係 | 評価値 | α 値 |
|:-:|:-:|:-:|
| $l ≦ α$ | 子ノードから計算  |   |
| $α < l$  | 子ノードから計算  | $l$ に変更  |

従って、α 値は $α < l$ __の場合に__ $l$ __に更新する必要がある__ ことがわかりました。この処理は組み込み関数 __`max`__ を利用して下記のプログラムのように記述することができます。

```python
alpha = max(alpha, lower_bound)
```

上記と同様の手順で「関係」、「評価値」、「β 値」の列のみを取り出した表を作ってまとめると下記の表のようになります。

| 関係 | 評価値 | β 値 |
|:-:|:-:|:-:|
| $β ≦ u$ | 子ノードから計算  |   |
| $u < β$  | 子ノードから計算  | $u$ に変更  |

従って、β 値は $u < β$ __の場合に__ $u$ __に更新する必要がある__ ことがわかりました。この処理は組み込み関数 __`min`__ を利用して下記のプログラムのように記述することができます。

```python
beta = min(beta, upper_bound)
```

### `ai_abs_tt2` の修正

上記から、評価値の範囲が置換表に登録されている場合のノードの処理が下記のようになることがわかります。これは[先程のノート](#評価値の範囲が置換表に記録されている場合に行う処理の考察)で推測した処理と同じです。

:::note warn
1. $u ≦ α$ の場合に __fail low__ になり、$u$ __を評価値として返す__
2. $β ≦ l$ の場合に __fail high__ になり、$l$ __を評価値として返す__
3. 上記以外の場合では __exact value が含まれる__ ので $α$ と $β$ __を以下のように変更__ して __子ノードから評価値を計算する__
    1. $α < l$ の場合は $α$ を $l$ に変更する
    2. $u < β$ の場合は $β$ を $u$ に変更する
::: 

下記は、上記の処理を行うように __`ai_abs_tt2`__ を修正したプログラムです。

* __4、5 行目__：ノードの局面の情報が置換表に登録されているかどうかをチェックする
* __6 行目__：置換表からその局面のミニマックス値の下界と上界を取り出す
* __7 ~ 12 行目__：上記の 1、2 の場合の評価値を返す
* __13 ~ 15 行目__：上記の 3 の場合に組み込み関数 `min` と `max` を利用して α 値と β 値を変更する。この場合は 17、18 行目で変数に記録する __α 値と β 値の初期値はここで変更された値になる__

```python
 1  @ai_by_score
 2  def ai_abs_tt2(mb, debug=False, shortest_victory=False):   
元と同じなので省略
 3      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 4          boardtxt = mborig.board_to_str()
 5          if boardtxt in tt:
 6              lower_bound, upper_bound = tt[boardtxt]
 7              if lower_bound == upper_bound:
 8                  return lower_bound
 9              elif upper_bound <= alpha:
10                  return upper_bound
11              elif beta <= lower_bound:
12                  return lower_bound
13              else:
14                  alpha = min(alpha, lower_bound)
15                  beta = max(beta, upper_bound)
16          
17          alphaorig = alpha
18          betaorig = beta
元と同じなので省略   
```

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

```python
@ai_by_score
def ai_abs_tt2(mb, debug=False, shortest_victory=False):   
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        boardtxt = mborig.board_to_str()
        if boardtxt in tt:
            lower_bound, upper_bound = tt[boardtxt]
            if lower_bound == upper_bound:
                return lower_bound
            elif upper_bound <= alpha:
                return upper_bound
            elif beta <= lower_bound:
                return lower_bound
            else:
                alpha = min(alpha, lower_bound)
                beta = max(beta, upper_bound)
        
        alphaorig = alpha
        betaorig = beta

        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, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        boardtxtlist = calc_same_boardtexts(mborig)
        if score <= alphaorig:
            lower_bound = float("-inf")
            upper_bound = score
        elif score < betaorig:
            lower_bound = score
            upper_bound = score
        else:
            lower_bound = score
            upper_bound = float("inf")
        for boardtxt in boardtxtlist:
            tt[boardtxt] = (lower_bound, upper_bound)
        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
@ai_by_score
def ai_abs_tt2(mb, debug=False, shortest_victory=False):   
元と同じなので省略
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        boardtxt = mborig.board_to_str()
-       # key = (boardtxt, alpha, beta)
-       # if key in tt:
-       #     return tt[key]
+       if boardtxt in tt:
+           lower_bound, upper_bound = tt[boardtxt]
+           if lower_bound == upper_bound:
+               return lower_bound
+           elif upper_bound <= alpha:
+               return upper_bound
+           elif beta <= lower_bound:
+               return lower_bound
+           else:
+               alpha = min(alpha, lower_bound)
+               beta = max(beta, upper_bound)
        
        alphaorig = alpha
        betaorig = beta
元と同じなので省略   
```
</details>

:::note
わかりやすさを重視して本記事では修正しませんが、上記の 7、8 行目と 11、12 行目はどちらも lower_bound を返り値として返すので、下記のプログラムの 1、2 行目のようにまとめることができます。

```python
1  if lower_bound == upper_bound or beta <= lower_bound:
2      return lower_bound
3  elif upper_bound <= alpha:
4      return upper_bound
5  else:
6      alpha = min(alpha, lower_bound)
7      beta = max(beta, upper_bound)
```

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

```diff_python
-   if lower_bound == upper_bound:
+   if lower_bound == upper_bound or beta <= lower_bound:
        return lower_bound
    elif upper_bound <= alpha:
        return upper_bound
+   elif beta <= lower_bound:
+       return lower_bound
    else:
       alpha = min(alpha, lower_bound)
       beta = max(beta, upper_bound)
```
</details>
:::

## `ai_abs_tt2` が強解決の AI であることの確認

__`ai_abs_tt2`__ が強解決の AI であることを、Check_Solved を利用して下記のプログラムで確認すると、実行結果から __強解決の AI であることが確認できました__。

```python
from util import Check_solved

Check_solved.is_strongly_solved(ai_abs_tt2)
```

実行結果

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

(True, [])
```

記事が長くなったので、`ai_abs_tt2` による __枝狩りの効率__ については __次回の記事で確認する__ ことにします。

# 今回の記事のまとめ

今回の記事では、ノードの __ミニマックス値の下界と上界を記録する置換表__ を利用した __αβ 法の実装__ を行い、その方法で作成した AI が __強解決の AI である__ ことを示しました。次回の記事でこの方法によって枝狩りの効率が改善されたことを確認します。

実は __今回の記事で実装した `ai_abs_tt2`__ には __効率が悪い点__ が 1 つあり、その問題を修正することで枝狩りの効率をさらに向上することができます。どのような問題があるかについて余裕がある方は考えてみて下さい。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/20317d7b67518a119382

[^1]:この用語は αβ 法で一般的に使われる用語です
[^2]:この用語は筆者が勝手につけた用語で、αβ 法で一般的には使われないと思います
[^3]:もしかすると医学の発達によって今後 200 才を超える人が現れることがあるかもしれないので、現実の世界で設定された上界は、実際には本当の上界ではない場合が良くあります。なお、fail low の場合の αβ 値など、数学的に正しいことが証明されている上界は正しいので、fail low の場合にミニマックス値が αβ 値より大きな値になることは決してありません