Pythonで〇×ゲームのAIを一から作成する　その155　置換表付き αβ 法での置換表へのデータの記録方法の修正

# 目次と前回の記事

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

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

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

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

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

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

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

# 置換表付き αβ 法の枝狩りの効率の確認

__αβ 法で用いる置換表__ としては、前回の記事で紹介した __ミニマックス値の下界と上界を記録する手法が一般的__ だと思います。以後はそのような置換表を利用した αβ 法のことを「__置換表付き αβ 法__」と表記することにします。

前回の記事では置換表付き αβ 法の枝狩りの効率の検証を行っていなかったので、その検証を行うことにします。

## 計算したノードの数と枝狩りが行われた数の計算方法

これまでは、ミニマックス法や αβ 法で評価値を計算する際に __計算したノードの数__ や、__枝狩りが行なわれたノードの数__ を Mbtree クラスの __`calc_score_by_ab`__ メソッドを実行して計算していました。同様の方法で置換表付き αβ 法で計算したノードの数や、枝狩りが行なわれたノードの数を確認するためには、__`calc_score_by_ab`__ を置換表付き αβ 法の処理を __行うことができるように修正する必要__ がありますが、実はもっと簡単に計算を行うことができます。その方法について少し考えてみて下さい。

### 計算が行われたノードの数の確認方法とその問題点

__`ai_mmbfs`__、__`ai_abs`__、__`ai_abs_tt2`__ などの、ミニマックス法や αβ 法で評価値を計算する AI の関数では、評価値を計算する際に __計算を行なったノードの数を `count` という変数で数えており__、キーワード引数に __`debug=True`__ を記述して呼び出すことで、__計算を行なったノードの数を表示__ するようになっているので、これを利用することができます。

例えば前回の記事で実装した置換表付き αβ 法で着手を選択する __`ai_abs_tt2`__ の場合は、下記の実行結果の __count = 772__ のように計算を行なったノードの数が表示されます。

```python
from marubatsu import Marubatsu
from ai import ai_abs_tt2

mb = Marubatsu()
ai_abs_tt2(mb, debug=True)
```

実行結果

```
Start ai_by_score
Turn o
...
...
...

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn x
O..
...
...

count = 772
score 0 best score -inf
UPDATE
  best score 0
  best moves [(0, 0)]
====================
move (1, 0)
Turn x
.O.
...
...

count = 786
略
```

ただし、上記の実行結果からわかるように、実際には count = 772、count = 786 のように、__複数の count が表示__ されます。このようなことが起きる理由は、__`ai_abs_tt2`__ などの、__`@ai_by_score`__ という __デコレータ式によって機能を拡張__ した AI の関数が、以下のようなアルゴリズムで着手を選択しているからです。なお、デコレータ式による AI の関数の定義について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/7e1d948c4b9208ab44fb#%E3%83%87%E3%82%B3%E3%83%AC%E3%83%BC%E3%82%BF%E3%83%BC%E5%BC%8F%E3%81%AB%E3%82%88%E3%82%8B-ai-%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)を復習して下さい。

* `@ai_by_score` によってラップされる __機能が拡張される前の関数__ は、__指定した局面の評価値__ を計算して __返り値として返す__ という処理を行う
* `@ai_by_score` は、ラップする関数を利用して __指定された局面の全ての子ノードの評価値を計算__ し、__子ノードの評価値が最も高い合法手__ の中から __ランダムに着手を選択__ するという処理を行う
* 従って、指定したノードの __全ての子ノードに対して__ 置換表付き αβ 法の __処理が行われ__、それぞれの子ノードの評価値を計算する際に __計算したノードの数が順番に表示__ される。上記の実行結果の場合は、以下のように count が表示される
    * 最初の __count = 772__ その上に表示される __(0, 0) を着手した局面__ の評価値を計算した際に __計算されたノードの数__ を表す
    * 次の __count = 786__ はその上に表示される __(1, 0) を着手した局面__ の評価値を計算した際に __計算されたノードの数__ を表す

`@ai_by_score` によって __機能が拡張される前__ の `ai_abs_tt2` を __呼び出すことができれば__、__指定した局面の__ 評価値を置換表付き αβ 法で計算した際に __計算されたノードの数だけを表示__ することができますが、残念ながら[以前の記事](https://qiita.com/ysgeso/items/bd63433b7491d8a07ff5#%E3%83%A9%E3%83%83%E3%83%97%E3%81%99%E3%82%8B%E9%96%A2%E6%95%B0%E3%82%92%E5%88%A9%E7%94%A8%E3%81%A7%E3%81%8D%E3%81%AA%E3%81%8F%E3%81%AA%E3%82%8B)で説明したように、__デコレータ式が適用された関数__ は、デコレータ式によって __機能が拡張される前のラップされた関数を呼び出すことができなくなります__。この問題を解決する方法について少し考えてみて下さい。

## `ai_by_score` の修正

この問題を解決する方法の一つに、__`ai_by_score`__ 内で定義された __ラッパー関数__ に、`True` を代入した場合に __ラップする関数を呼び出す処理__ を行うという __仮引数を追加する__ という方法があります。具体的には、__仮引数 `calc_score` を追加__ し、`True` が代入されいてた場合は __指定された局面（`mborig`）の評価値を計算（calculate score）して返す__ ように修正します。下記は、そのように __`ai_by_score`__ を修正したプログラムです。

* __7 行目__：ラッパー関数の仮引数にデフォルト値が `False` に設定されたデフォルト引数 `calc_score` を追加する
* __8、9 行目__：関数のブロックの最初で `calc_score` が `True` の場合に `mb_orig` の局面の評価値を計算して返すように修正する

```python
1  from ai import dprint
2  from copy import deepcopy
3  from functools import wraps
4
5  def ai_by_score(eval_func):
6      @wraps(eval_func)
7      def wrapper(mb_orig, debug=False, *args, rand=True, analyze=False, calc_score=False, **kwargs):
8          if calc_score:
9              return eval_func(mb_orig, debug, *args, **kwargs)
元と同じなので省略
```

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

```python
from ai import dprint
from copy import deepcopy
from functools import wraps

def ai_by_score(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, analyze=False, calc_score=False, **kwargs):
        if calc_score:
            return eval_func(mb_orig, debug, *args, **kwargs)
        
        dprint(debug, "Start ai_by_score")
        dprint(debug, mb_orig)
        legal_moves = mb_orig.calc_legal_moves()
        dprint(debug, "legal_moves", legal_moves)
        best_score = float("-inf")
        best_moves = []
        if analyze:
            score_by_move = {}
        for move in legal_moves:
            dprint(debug, "=" * 20)
            dprint(debug, "move", move)
            mb = deepcopy(mb_orig)
            x, y = move
            mb.move(x, y)
            dprint(debug, mb)
            
            score = eval_func(mb, debug, *args, **kwargs)
            dprint(debug, "score", score, "best score", best_score)
            if analyze:
                score_by_move[move] = score
            
            if best_score < score:
                best_score = score
                best_moves = [move]
                dprint(debug, "UPDATE")
                dprint(debug, "  best score", best_score)
                dprint(debug, "  best moves", best_moves)
            elif best_score == score:
                best_moves.append(move)
                dprint(debug, "APPEND")
                dprint(debug, "  best moves", best_moves)

        dprint(debug, "=" * 20)
        dprint(debug, "Finished")
        dprint(debug, "best score", best_score)
        dprint(debug, "best moves", best_moves)
        if analyze:
            return {
                "candidate": best_moves,
                "score_by_move": score_by_move,
            }
        elif rand:   
            return choice(best_moves)
        else:
            return best_moves[0]
        
    return wrapper
```
</details>

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

```diff_python
from ai import dprint
from copy import deepcopy
from functools import wraps

def ai_by_score(eval_func):
    @wraps(eval_func)
-   def wrapper(mb_orig, debug=False, *args, rand=True, analyze=False, **kwargs):
+   def wrapper(mb_orig, debug=False, *args, rand=True, analyze=False, calc_score=False, **kwargs):
+       if calc_score:
+           return eval_func(mb_orig, debug, *args, **kwargs)
元と同じなので省略
```
</details>

## 様々な AI での計算したノード数の確認

次に、上記で修正した __`ai_by_score` が正しく動作するか__ どうかを、__様々な 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%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)で __`calc_score_by_ab` で計算した値と等しくなるか__ どうかで __確認する__ ことにします。

ただし、__現状の ai.py__ は __`ai_by_score` の内容が更新されていない__ ので、__`from ai import ai_abs_tt2`__ のように __ai.py から AI の関数をインポートした場合__ は、__修正前の `ai_by_score` が適用されてしまう__ のでうまくいきません。そこで、本記事では __`ai.py`__ の中で、__`ai_by_score` の部分だけを今回の記事で修正した内容に更新__ した __[ai2.py](https://github.com/ysgeso/marubatsu/blob/master/155/ai2.py)__ というファイルを用意し、__ai2.py から AI の関数をインポートする__ ことにします。なお、`ai_by_score` の修正は次回の記事以降の ai.py には反映するので、ai2.py を用意するのは今回の記事のみです。

下記のプログラムで、以下のそれぞれの場合でルートノードの評価値を計算した際に計算されるノード数を表示します。

* 置換表を利用しないミニマックス法（`ai_mmdfs`）
* 置換表を利用したミニマックス法（`ai_mmdfs_tt`）
* 置換表を利用しない αβ 法（`ai_abs`）
* 局面と α 値と β 値の初期値をキーとした置換表を利用する αβ 法（`ai_abs_tt`）
* 置換表付き αβ 法（`ai_abs_tt2`）

```python
from ai2 import ai_mmdfs, ai_mmdfs_tt, ai_abs, ai_abs_tt, ai_abs_tt2

ai_mmdfs(mb, calc_score=True, debug=True)
ai_mmdfs_tt(mb, calc_score=True, debug=True)
ai_abs(mb, calc_score=True, debug=True)
ai_abs_tt(mb, calc_score=True, debug=True)
ai_abs_tt2(mb, calc_score=True, debug=True)
```

実行結果

```
count = 549946
count = 2271
count = 18297
count = 1718
count = 1208
0
```

実行結果から、__最初の 4 つの場合__ で計算されたノードの数が、[以前の記事](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)で __`calc_score_by_ab`__ で計算した値と __同じであることが確認__ できました[^1]。


また、今回の記事で実装した __置換表付き αβ 法__ の __`ai_abs_tt2`__ は、下記のように __枝狩りの効率が向上__ していることが確認できます。

* 置換表を利用したミニマックス法の __`ai_mmdfs_tt` と比べて__ 計算するノードの数が __約半分になっている__
* 局面と α 値と β 値の初期値をキーとした置換表を利用する αβ 法の __`ai_abs_tt` と比べて__ 計算するノードの数が __約 2/3 になっている__

### 枝狩りが行われた数などの確認

上記の count は計算されたノードの数を表しており、__`calc_score_by_ab`__ のように __枝狩りが行なわれたノードの数__ や、__計算が行われたノードの割合__ は __計算されていません__。ただし、以下の理由から `ai_by_score` を修正して、枝狩りが行なわれた数や計算が行われたノードの割合を __計算するようにするべきではありません__。また、__`ai_by_score` を修正しなくても__、枝狩りが行われたノードの数などを __計算することは可能__ です。どのようにして計算すればよいかについて少し考えてみて下さい。

* __枝狩りの処理__ は必要のない処理を省略することで、評価値を計算する __処理を高速化することが目的__ である
* 枝狩りが行われたノードの数を数えるという処理は、__評価値の計算を行う際には必要のない処理__ であり、その処理を行うことで __その分だけ処理に時間がかかってしまう__ ため、__枝狩りの目的に反する__

枝狩りが行われた数と計算が行われたノードの割合は、下記の方法で簡単に計算することができます。

* __置換表を利用しないミニマックス法__ では __枝狩りは行なわれない__ ので、__`ai_mmdfs`__ で評価値の計算を行うことで __ノードの総数がわかる__
* ノードの総数から、計算されたノードの数を __引き算する__ ことで __枝狩りされたノードの数を計算できる__
* __例えば置換表付き αβ 法__ の場合は、`ai_abs_tt2` で count = 1208 と表示されるので __枝狩りされたノードの数__ は __549946 - 1208 = 548738__ であり、__計算されたノードの割合__ は __1208 / 548738 = 約 0.2 %__ であることが計算できる

なお、今回の記事では `calc_score_by_ab` を修正しませんでしたが、__`calc_score_by_ab`__ は __評価値を計算する手順を Mbtree_Anim で視覚化するためのデータを計算する__ という目的があるので、次回の記事で `calc_score_by_ab` が置換表付き αβ 法で評価値を計算できるように修正する予定です。

# 置換表付き αβ 法の枝狩りの効率化

前回の記事の最後で言及しましたが、__現状の `ai_abs_tt2`__ には __効率が悪い点__ があります。問題は __置換表に__ 計算した __ミニマックス値の下界と上界のデータを記録する処理__ にあるので、どのような問題があるかについて少し考えてみて下さい。

## 置換表へのデータの記録の処理の問題点

__`ai_abs_tt2`__ では、以下のような手順で処理が行われます。なお、[前回の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#%E5%B1%80%E9%9D%A2%E3%81%AE%E6%83%85%E5%A0%B1%E3%81%8C%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%81%AB%E7%99%BB%E9%8C%B2%E3%81%95%E3%82%8C%E3%81%A6%E3%81%84%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AE%E5%87%A6%E7%90%86)と同様に、ノードの局面の __ミニマックス値が取りうる範囲__ のことを「__評価値の範囲__」、ミニマックス値の __下界__ と __上界__ のことを単に「__下界__」と「__上界__」と表記することにします。また、下記の処理について忘れた方は[前回の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394)を復習して下さい。

1. リーフノードの場合は勝敗結果から __評価値を計算して返す__
2. 置換表にノードの評価値の範囲が記録されていた場合は下記の処理を行う
    1. 下界と上界が等しい場合は正確なミニマックス値が記録されているのでその値をこのノードの __評価値として返す__
    2. 評価値の範囲がこのノードの fail low の範囲に完全に含まれる場合は上界をこのノードの __評価値として返す__
    3. 評価値の範囲がこのノードの fail high の範囲に完全に含まれる場合は下界をこのノードの __評価値として返す__
    4. そうでない場合は評価値の範囲と exact value の範囲（α 値と β 値の初期値の範囲）のうち重なる部分が範囲となるように α 値と β 値の初期値を更新し、3 の処理を行う
3. 子ノードの評価値を計算することで、このノードの評価値を計算する
4. 計算した評価値から求められたこのノードの評価値の範囲を置換表に記録する

__上記の太字の部分__ が、__`ai_abs_tt2` の処理の途中で__ return 文によって __評価値を返り値として返す__ という処理を意味しています。従って、上記の __手順 4__ で評価値の範囲を __置換表に記録する処理__ は、以下の __2 種類の場合で実行__ されます。

* そのノードの評価値の範囲が __置換表に記録されていなかった場合__
* そのノードの評価値の範囲が __置換表に記録されているが__、上記の __手順 2-1 ~ 2-3 の条件を満たさなかった場合__

前者の、そのノードの情報が __置換表に記録されていなかった場合__ は 手順 4 の処理を行っても特に __問題はありません__ が、後者の場合には __置換表に記録する評価値の範囲__ が、__計算によって求められた評価値の範囲よりも広くなる__ 可能性あります。

### 問題が発生する具体例

わかりづらいと思いますので、そのようなことが起きる具体例を挙げて説明します。

あるノード $N$ の評価値を置換表付き αβ 法で計算する際に、__置換表に記録されていた__ ミニマックス値の __下界が 負の無限大__、__上界が 3__、__α 値と β 値の初期値__ が __-1 と 1__ であったとします。下図はそのことを図にしたもので、__赤い矢印__ が置換表に記録されていたノード $N$ の __評価値の範囲__ を表しています。なお、図の記号は[前回の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#%E4%B8%8B%E7%95%8C%E3%81%A8%E4%B8%8A%E7%95%8C%E3%81%8C%E7%AD%89%E3%81%97%E3%81%8F%E3%81%AA%E3%81%84%E5%A0%B4%E5%90%88%E3%81%AE%E8%80%83%E3%81%88%E6%96%B9)と同様に、下界（lower bound）を頭文字を取って $l$、上界（upper bound）を $u$、α 値と β 値の初期値をそれぞれ $α$、$β$ と表記することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ed9d1d84-ac3f-4529-825c-204ffd7f0112.png" width="350">

上図からわかるように赤い矢印の __評価値の範囲__ は先程の __手順 2-1 ~ 2-3 のいずれも満たさない__ ので、__手順 3 で__ 子ノードの評価値から __このノードの評価値を計算する必要__ があります。なお、__手順 2-4__ では、__評価値の範囲が exact value の範囲をすべて含んでいる__ ので、__α 値と β 値の初期値__ は -1 と 1 のまま __変更しません__。

その後 __手順 3__ で __このノードの評価値として 2 が計算された場合__ のことを考えることにします。また、以後は __手順 3 で計算された評価値__（score）のことを $s$ __という記号で表記__ することにします。

$s = 2$ は 下図のように __fail high の範囲内__ なので $N$ の局面の __評価値の範囲__ は下図の __緑の矢印の範囲__ である __2 以上__ となります。従って、__手順 4__ では置換表にこのノードのミニマックス値の __下界と上界__ として __2__ と __正の無限大__ が記録されることになりますが、これはおかしくないでしょうか？何がおかしいかについて少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a5826d05-b9d8-467e-828a-0b8d1e851710.png" width="350">

おかしな点は以下の通りです。

* __置換表に記録されていた__ このノードの __評価値の範囲__ は上図の __赤い矢印の範囲__ である
* このノードの評価値を計算した結果、このノードの __評価値の範囲__ が上図の __緑色の範囲であることがわかった__
* 従って、__このノードの評価値の範囲__ は __赤い矢印と緑の矢印__ の __両方の範囲を含む__ 必要があり、その範囲は下図の __紫の矢印の範囲__ である __2 以上 3 以下__ であることがわかる
* それにも関わらず、手順 4 では置換表に 2 以上 3 以下の __紫の矢印の範囲よりも広い範囲__ である、__緑の矢印の範囲が記録されてしまう__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1dca6c4d-fad7-4d24-8938-7e863c551f5c.png" width="350">

__置換表に記録する下界と上界__ は、上図の紫の矢印の範囲を見れば 2 と 3 であることがわかりますが、それらを __計算によって求める必要__ があります。どのような計算を行えば良いかについて少し考えてみて下さい。

### 置換表に記録する下界と上界の計算方法

__置換表に記録する下界と上界__ は、赤い矢印と緑の矢印の範囲で __共通する範囲の下界と上界__ です。上図から、その __下界__ は __赤い矢印の範囲の下界__ と、__緑の矢印の範囲の下界__ のうち __大きいほう__ であることがわかります。同様に上界は赤い矢印の範囲の上界と、緑の矢印の範囲の上界のうち小さいほうになります。従って、__置換表に記録する下界と上界__ は下記のように計算することができます。

* __下界__ を以下の __最大値__ とする。上図の場合は負の無限大と 2 の最大値なので 2 となる
    * 置換表に記録されていた下界（上図の赤い矢印の左端の値）である $l$
    * このノードの評価値の計算によって求められた下界（上図の緑の矢印の左端の値）
* __上界__ を以下の __最小値__ とする。上図の場合は 3 と正の無限大の最小値なので 3 となる
    * 置換表に記録されていた上界（上図の赤い矢印の右端の値）である $u$
    * このノードの評価値の計算によって求められた上界（上図の緑の矢印の右端の値）

従って、$s$ __によって計算される__ 評価値の範囲の __下界と上界がわかれば__ 置換表に記録する下界と上界を計算することができます。慣れている人はこの時点で置換表に記録する下界と上界を計算する処理を行うプログラムを記述できるかもしれませんが、__慣れていない人__ は[前回の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#%E4%B8%8B%E7%95%8C%E3%81%A8%E4%B8%8A%E7%95%8C%E3%81%8C%E7%AD%89%E3%81%97%E3%81%8F%E3%81%AA%E3%81%84%E5%A0%B4%E5%90%88%E3%81%AE%E8%80%83%E3%81%88%E6%96%B9)と同様に __場合分けを行う__ と良いでしょう。具体的には $s$ が __fail low__、__exact value__、__fail high__ の __それぞれの場合__ について考えます。

### fail low の場合

__fail low__ の場合は、$s$ によって計算される緑の矢印の評価値の範囲の __下界は負の無限大__、__上界は__ $s$ と計算されます。従って、__置換表に記録する下界と上界__ は下記のように計算することができます。

* __下界__ は $l$ と負の無限大の __最大値__ となるので、下記の理由から $l$ __を記録すればよい__
    * $l$ が負の無限大の場合は __どちらも負の無限大__ になるので、最大値は $l$ __と同じ負の無限大__ になる
    * $l$ が負の無限大でなければ、__最大値は__ $l$ になる
* __上界__ は $u$ と $s$ の __最小値__ を記録すればよい。ただし、下記の理由から $s < u$ __という性質が満たされる__ ので、$s$ __を記録すればよい__
    * $u ≦ α$ __という条件が満たされる__ と先程の「置換表に記録されていた評価値の範囲がこのノードの fail low の範囲に完全に含まれる場合は上界をこのノードの評価値として返す」という手順 2-2 によって処理が終了してしまうので __手順 4 の処理が行われなくなる__ ため、$u ≦ α$ __という条件は満たされない__。従って $α < u$ __である__
    * $s$ は __fail low__ なので $s ≦ α$ という条件が満たされる
    * $s ≦ α$ と $α < u$ から、$s < u$ である

### exact value の場合

__exact value__ の場合は $s$ には __正確なミニマックス値__ が求められます。特定の値と、範囲のある値の __共通する範囲__ は __特定の値になる__ ので、__置換表の下界と上界__ には $s$ __を記録__ します。

### fail high の場合

__fail high__ の場合は、__下界は__ $s$、__上界は正の無限大__ と計算されます。__fail low の場合と同様の理由__ から、置換表に記録する下界と上界は以下のようになります。

* __下界__ は $l$ と $s$ の最大値である。fail low と同様の理由から $l < s$ が満たされるので、$s$ __を記録すればよい__
* __上界__ は $u$ と 正の無限大の最小値となる。fail low と同様の理由で $u$ __を記録すればよい__

### 上記をまとめた表

上記の説明を表にまとめると以下のようになります。下記の表では $a$ と $b$ の最小値を $min(a, b)$、最大値を $max(a, b)$ と表記しています。

|  | fail low | exact value | fail high |
|:--|:-:|:-:|:-:|
| 置換表に記録されていた下界  | $l$  |  $l$ |  $l$ |
| $s$ によって求められた下界  | $-∞$  | $s$  | $s$ |
| 置換表に記録する下界  | $max(l, -∞) = l$  | $s$  | $max(l, s) = s$  |
| 置換表に記録されていた上界  | $u$  |  $u$ |  $u$ |
| $s$ によって求められた上界  | $s$  | $s$  | $∞$ |
| 置換表に記録する上界  | $min(u, s) = s$  | $s$  | $min(u, ∞) = u$  |

上記の表から __置換表に記録する下界と上界__ のみを取り出すと以下の表のようになります。

|  | fail low | exact value | fail high |
|:--|:-:|:-:|:-:|
| 置換表に記録する下界  | $l$  | $s$  | $s$  |
| 置換表に記録する上界  | $s$  | $s$  | $u$  |

## 置換表にノードの情報が記録されていない場合の処理との統合

上記の表は、__置換表に評価値の範囲が記録されている場合__ に行う処理です。置換表に評価値の範囲が __記録されていない場合__ は、[前回の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E5%80%A4%E3%81%AE%E4%B8%8B%E7%95%8C%E3%81%A8%E4%B8%8A%E7%95%8C%E3%82%92%E8%A8%98%E9%8C%B2%E3%81%99%E3%82%8B%E7%BD%AE%E6%8F%9B%E8%A1%A8)で説明したように __下記の表の処理を行う__ ので、置換表にノードの情報が __記録されている場合とされていない場合__ で __異なる処理を行う__ ようなプログラムを記述する必要があると思った人がいるかもしれません。しかし、__工夫をすること__ で上記の表と、下記の表の処理を __うまく統合することができます__。どのようにすれば良いかについて少し考えてみて下さい。

|  | fail low | exact value | fail high |
|:--|:-:|:-:|:-:|
| 置換表に記録する下界  | $-∞$  | $s$  | $s$  |
| 置換表に記録する上界  | $s$  | $s$  | $∞$  |

先程の表と上記の表の __違い__ は、$l$ が $-∞$ である点と、$u$ が $∞$ である __点だけです__。従って、置換表に評価値の範囲が __記録されていない場合__ は $l = -∞$、$u = ∞$ __とする__ ことで置換表に評価値の範囲が __記録されている場合と同じ方法__ で計算を行うことができます。

このことは言葉で説明することもできます。置換表に __評価値の範囲が記録されていない__ ということは、そのノードの評価値の範囲が __全くわかっていない__ という事を意味するので、評価値の範囲は __負の無限大から正の無限大まで__ のすべての実数の範囲と __考えることができます__。従って、そのような場合は評価値の範囲として __下界を負の無限大__、__上界を正の無限大__ とみなすことができます。

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

:::note warn
置換表付き αβ 法では、置換表を更新する処理は以下のように行う。

* 置換表に評価値の範囲が __記録されている場合__ は $l$ と $u$ を __置換表に記録されていた下界と上界の値__ とする
* 置換表に評価値の範囲が __記録されていない場合__ は $l$ と $u$ を __負の無限大と正の無限大__ とする
* 置換表に記録する上界と下界を下記の表のように計算する

|  | fail low | exact value | fail high |
|:--|:-:|:-:|:-:|
| __置換表に記録する下界__  | $l$  | $s$  | $s$  |
| __置換表に記録する上界__  | $s$  | $s$  | $u$  |
:::

## `ai_abs_tt3` の定義

上記のように置換表にデータを記録する処理を行う __`ai_abs_tt3`__ は、`ai_abs_tt2` を修正して下記のプログラムのように定義することができます。

* __2 行目__：関数名を `ai_abs_tt3` に修正した
* __8 ~ 10 行目__：置換表に評価値の範囲が __記録されていない場合__ に下界と上界を記録する変数に __負の無限大と正の無限大を代入__ するように修正する
* __12 ~ 18 行目__：先程の表に従って置換表に記録する下界と上界の値を計算する。修正前のプログラムでは fail low の場合に `lower_bound` に負の無限大を 12 行目の下で代入していたが、置換表に評価値の範囲が記録されている場合は 7 行目で、記録されていない場合は 9 行目で `lower_bound` に下界の値を代入する処理が行なわれるようになるので 12 行目の下にあった `lower_bound` に値を代入する処理は削除した。18 行目の下にあった fail high の場合の `upper_bound` に正の無限大を代入する処理も同様の理由で削除した

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

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

```python
@ai_by_score
def ai_abs_tt3(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)
        else:
            lower_bound = float("-inf")
            upper_bound = float("inf")
        
        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:
            upper_bound = score
        elif score < betaorig:
            lower_bound = score
            upper_bound = score
        else:
            lower_bound = score
        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 ai_abs_tt3(mb, debug=False, shortest_victory=False):   
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        boardtxt = mborig.board_to_str()
        if boardtxt in tt:
            lower_bound, upper_bound = tt[boardtxt]
元と同じなので省略
+       else:
+           lower_bound = float("-inf")
+           upper_bound = float("inf")
元と同じなので省略 
        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
元と同じなので省略 
```
</details>

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

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

```python
from util import Check_solved

Check_solved.is_strongly_solved(ai_abs_tt3)
```

実行結果

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

(True, [])
```

### 枝狩りの効率の確認

下記のプログラムで __`ai_abs_tt3`__ でルートノードの評価値を計算した際に __計算されたノードの数を表示__ すると、`ai_abs_tt2` の場合の 1208 と比べて __約 3 %__ ほど減っており、__より多くの枝狩りを行うことができるようになった__ ことが確認できます。

__〇× ゲームのゲーム木の場合__ は __枝狩りの効率はほとんど上昇しません__ が、__他のゲーム__ のゲーム木の場合では __もっと枝狩りの効率が上がる場合がある__ ようです。

```python
ai_abs_tt3(mb, calc_score=True, debug=True)
```

実行結果

```
count = 1173
0
```

# 評価値の最小値の最大値を利用した改良

[以前の記事](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)と[以前の記事](https://qiita.com/ysgeso/items/523e03ff877cb033889b#%E3%83%AB%E3%83%BC%E3%83%88%E3%83%8E%E3%83%BC%E3%83%89%E3%81%A7%E6%AD%A3%E3%81%97%E3%81%84%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%95%E3%82%8C%E3%82%8B%E7%90%86%E7%94%B1)で __ルートノードの α 値と β 値の初期値__ を __評価値の最小値と最大値に設定__ することで __枝狩りの効率を上げる__ という方法を説明したので、その方法で置換表付き αβ 法による着手を行う __`ai_abs_tt4`__ を下記のプログラムのように定義する事にします。

その際に、評価値の範囲が置換表に __記録されていなかった場合__ の __下界と上界__ を __評価値の最小値と最大値に設定__ することができます。

* __10、11 行目__：評価値の最小値と最大値を計算して変数に代入する
* __13 行目__：α 値と β 値の初期値を評価値の最小値と最大値に設定してルートノードの評価値を計算するように修正する
* __8、9 行目__：ノードの情報が置換表に __記録されていない場合の下界と上界__ を __評価値の最小値と最大値__ に修正する

```python
 1  @ai_by_score
 2  def ai_abs_tt4(mb, debug=False, shortest_victory=False):   
 3      count = 0
 4      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 5          if boardtxt in tt:
 6              lower_bound, upper_bound = tt[boardtxt]
元と同じなので省略
 7          else:
 8              lower_bound = min_score
 9              upper_bound = max_score
元と同じなので省略              
10      min_score = -2 if shortest_victory else -1
11      max_score = 3 if shortest_victory else 1
12  
13      score = ab_search(mb, {}, alpha=min_score, beta=max_score)
14      dprint(debug, "count =", count)
15      if mb.turn == Marubatsu.CIRCLE:
16          score *= -1
17      return score
```

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

```python
@ai_by_score
def ai_abs_tt4(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)
        else:
            lower_bound = min_score
            upper_bound = max_score
        
        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:
            upper_bound = score
        elif score < betaorig:
            lower_bound = score
            upper_bound = score
        else:
            lower_bound = score
        for boardtxt in boardtxtlist:
            tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1

    score = ab_search(mb, {}, alpha=min_score, beta=max_score)
    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_tt4(mb, debug=False, shortest_victory=False):   
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        if boardtxt in tt:
            lower_bound, upper_bound = tt[boardtxt]
元と同じなので省略
        else:
            lower_bound = min_score
            upper_bound = max_score
元と同じなので省略              
    min_score = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1

    score = ab_search(mb, {}, alpha=min_score, beta=max_score)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

:::note
max node の場合に評価値を計算する変数 `score` の初期値を下記のプログラムのように評価値の最小値に変更することもできます[^2]が、変更してもしなくても __計算される結果は変わらない__ ので本記事では変更しないことにします。変更したい人は自由に変更して下さい。

```python
        if mborig.turn == Marubatsu.CIRCLE:
            score = min_score
```

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

```diff_python
        if mborig.turn == Marubatsu.CIRCLE:
-           score = float("-inf")
+           score = min_score
```
</details>
:::

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

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

```python
Check_solved.is_strongly_solved(ai_abs_tt4)
```

実行結果

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

(True, [])
```

### 枝狩りの効率の確認

下記のプログラムで __`ai_abs_tt4`__ でルートノードの評価値を計算した際に __計算されたノードの数__ を表示すると、`ai_abs_tt3` の場合の 1173 の __約 70 %__ となっていることから、__枝狩りの効率がかなり上昇する__ ことが確認できました。

```python
ai_abs_tt4(mb, calc_score=True, debug=True)
```

実行結果

```
count = 832
0
```

# 今回の記事のまとめ

今回の記事では、__置換表付き αβ 法__ での __置換表への下界と上界の記録処理を改良__ しました。また、置換表付き αβ 法でも __α 値と β 値の初期値__ を __評価値の最小値と最大値とする__ ことで、__枝狩りの効率を上げることができる__ ことを確認しました。

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

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

# 次回の記事

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

[^1]:実行結果の最後に表示される 0 は、最後の行の `ai_abs_tt2` で計算されたルートノードの評価値を表す返り値です
[^2]:min node の場合も同様です