Pythonで〇×ゲームのAIを一から作成する　その152　置換表による αβ 法の枝狩り

# 目次と前回の記事

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

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

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

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

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

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

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

# 置換表を利用した αβ 法の実装

前回の記事では __`calc_score_by_ab`__ に仮引数 __[`minimax`](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3-%E3%81%9D%E3%81%AE-1)__ を追加して __ミニマックス法でも評価値を計算できる__ ようにしました。また、仮引数 __[`use_tt`](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3-%E3%81%9D%E3%81%AE-2)__ を追加して __置換表（transposition table）を利用してミニマックス法で評価値を計算__ できるようにしました。

具体的には、置換表を利用したミニマックス法では以下の処理を行います。

* ミニマックス法でノードの評価値を計算した際に、__その局面の評価値を置換表に登録する__
* ノードの評価値を計算する際に、__その局面の評価値が置換表に登録されている場合__ は __子孫ノードの評価値の計算__ を __枝狩りして省略__ し、置換表に登録された評価値をそのノードの評価値とする

ただし、上記の __置換表の処理__ は、ミニマックス法では利用できますが、__αβ 法ではそのままでは利用することはできません__。

:::note alert
下記のプログラムのように __`calc_score_by_ab`__ を呼び出す際に、キーワード引数 __`minimax=False`__[^1] と __`use_tt=True`__ を記述することで、__置換表を利用した αβ 法__ で評価値を計算できると思った人がいるかもしれません[^2]が、実際には __正しく評価値を計算できていません__。今回の記事ではその理由と、修正方法について説明します。

```python
from tree import Mbtree

mbtree = Mbtree.load("../data/abtree_root")
mbtree.calc_score_by_ab(mbtree.root, use_tt=True, debug=True)
```

実行結果

```
ミニマックス法で計算したか False
計算したノードの数 999
枝狩りしたノードの数 548947
合計 549946
割合 0.2%
```
:::

## 評価値が正しく計算できていないことの検証

上記の `calc_score_ab` の処理で __評価値が正しく計算できているかどうかを検証__ するために、__`calc_score_by_ab` と同じ方法__ で __置換表を利用した αβ 法__ によって着手を選択する __AI の関数を定義__ し、__Check_solved__ クラスの __[`is_strongly_solved`](https://qiita.com/ysgeso/items/80f19df519a6a856bbf8#is_strongly_solved-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ メソッドを利用してその AI が __強解決であるかどうかを確認__ することにします。

AI の名前は __`ai_abs_tt`__ とし、αβ 法によって着手を選択する __[`ai_abs`](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#ai-%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE-ai_abs-%E3%81%AE%E5%AE%9A%E7%BE%A9) を修正__ して下記のプログラムのように定義します。なお、__修正の方法__ は前回の記事でミニマックス法で着手を選択する `ai_mmdfs` を置換表を利用したミニマックス法で着手を選択する __[`ai_mmdfs_tt`](https://qiita.com/ysgeso/items/b90305993d682ff16793#%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8%E7%A2%BA%E8%AA%8D)__ に修正した方法と __ほぼ同じ__ です。

* __6 行目__：最短の勝利を優先する評価値を計算できるように、デフォルト値を `False` とする仮引数 `shortest_victory` を追加する
* __8、27、37 行目__：ノードの評価値を計算する `ab_search` に、置換表のデータを代入する仮引数 `tt` を追加し、子ノードの評価値を計算するために `ab_search` を再帰呼び出しする際の実引数に置換表のデータを表す `tt` を記述する
* __11 ~ 16 行目__：ゲームの決着がついた場合の評価値を計算する。[前回の記事](https://qiita.com/ysgeso/items/b90305993d682ff16793#%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8%E7%A2%BA%E8%AA%8D) で定義した `ai_mmdfs_tt` の 11 ~ 16 行目と同じ
* __18 ~ 20 行目__：局面を表す文字列を計算し、置換表に登録されている場合はその評価値を返すように修正する。これも `ai_mmdfs_tt` の 18 ~ 20 行目と同じ
* __29、30、39、40 行目__：元のプログラムでは α 狩りや β 狩りを計算した際に return 文で評価値をすぐに返していたが、__置換表に評価値を登録する処理を 46 ~ 48 行目でまとめて行う__ ことが出来るようにするために、__評価値を α 値または β 値に代入__ して __break 文で繰り返し処理を抜ける__ ようにする。なお、`calc_score_by_ab` でも同様の処理を行っている
* __32、42行目__：元のプログラムではノードの評価値が確定した際に return 文で評価値を返していたが、__置換表に評価値を登録する処理__ を 46 ~ 48 行目で __まとめて行うことが出来るようにする__ ために __ローカル変数 `score` に評価値を代入__ し、__return 文を削除__ する
* __44 行目__：tree.py にプログラムを記述した際に [循環インポートによるエラーを避ける](https://qiita.com/ysgeso/items/6d1430a88e251279d77a#%E5%BE%AA%E7%92%B0%E5%8F%82%E7%85%A7%E3%81%AE%E5%95%8F%E9%A1%8C%E3%81%AE%E4%BF%AE%E6%AD%A3) ため、`calc_same_boardtext` のインポートをここに記述する
* __46 ~ 48 行目__：この局面のすべての同一局面の評価値を置換表に登録する。 `ai_mmdfs_tt` の 32 ~ 34 行目と同じ
* __49 行目__：評価値を返り値として返すように修正する
* __51 行目__：最初に `ab_search` を呼び出す際に、置換表として空の dict を実引数に記述する ように修正する

```python
 1  from ai import dprint, ai_by_score
 2  from marubatsu import Marubatsu
 3  from copy import deepcopy
 4  
 5  @ai_by_score
 6  def ai_abs_tt(mb, debug=False, shortest_victory=False):            
 7      count = 0
 8      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
 9          nonlocal count
10          count += 1
11          if mborig.status == Marubatsu.CIRCLE:
12              return (11 - mborig.move_count) / 2 if shortest_victory else 1
13          elif mborig.status == Marubatsu.CROSS:
14              return (mborig.move_count - 10) / 2 if shortest_victory else -1
15          elif mborig.status == Marubatsu.DRAW:
16              return 0
17          
18          boardtxt = mborig.board_to_str()
19          if boardtxt in tt:
20              return tt[boardtxt]
21  
22          legal_moves = mborig.calc_legal_moves()
23          if mborig.turn == Marubatsu.CIRCLE:
24              for x, y in legal_moves:
25                  mb = deepcopy(mborig)
26                  mb.move(x, y)
27                  score = ab_search(mb, tt, alpha, beta)
28                  if score >= beta:
29                      alpha = score
30                      break
31                  alpha = max(alpha, score)
32              score = alpha
33          else:
34              for x, y in legal_moves:
35                  mb = deepcopy(mborig)
36                  mb.move(x, y)
37                  score = ab_search(mb, tt, alpha, beta)
38                  if score <= alpha:
39                      beta = score
40                      break
41                  beta = min(beta, score)   
42              score = beta
43              
44          from util import calc_same_boardtexts
45  
46          boardtxtlist = calc_same_boardtexts(mborig)
47          for boardtxt in boardtxtlist:
48              tt[boardtxt] = score
49          return score
50                  
51      score = ab_search(mb, {})
52      dprint(debug, "count =", count)
53      if mb.turn == Marubatsu.CIRCLE:
54          score *= -1
55      return score
```

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

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

@ai_by_score
def ai_abs_tt(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:
            return tt[boardtxt]

        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, tt, alpha, beta)
                if score >= beta:
                    alpha = score
                    break
                alpha = max(alpha, score)
            score = alpha
        else:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                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)
        for boardtxt in boardtxtlist:
            tt[boardtxt] = 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 dprint, ai_by_score
from marubatsu import Marubatsu
from copy import deepcopy

@ai_by_score
-def ai_abs_tt(mb, debug=False):
+def ai_abs_tt(mb, debug=False, shortest_victory=False):
    count = 0
-   def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
+   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:
+           return tt[boardtxt]

        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = ab_search(mb, alpha, beta)
+               score = ab_search(mb, tt, alpha, beta)
                if score >= beta:
-                   return score
+                   alpha = score
+                   break
                alpha = max(alpha, score)
-           return alpha
+           score = alpha
        else:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = ab_search(mb, alpha, beta)
+               score = ab_search(mb, tt, alpha, beta)
                if score <= alpha:
-                   return score
+                   beta = score
+                   break
                beta = min(beta, score)   
-           return score
+           score = beta
            
+       from util import calc_same_boardtexts

+       boardtxtlist = calc_same_boardtexts(mborig)
+       for boardtxt in boardtxtlist:
+           tt[boardtxt] = score
+       return score
                
-   score = ab_search(mb)
+   score = ab_search(mb, {})
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

上記のプログラムを定義後に、下記のプログラムで __`ai_abs_tt` が強解決の AI であるかを確認__ すると、実行結果のように __最後に `False` が表示__ されることから __`ai_abs_tt`__ が __強解決の AI ではない__ ことが確認できます。また、__最善手を着手する局面__ の割合が __95.82%__、__最善手を着手しない局面__ が 431 - 413 = __18 ある__ 事がわかります。

従って、__αβ 法で置換表を利用する際__ に、__ミニマックス法と同じ方法で処理を行うことができない__ ことが確認できました。

実行結果

```python
from util import Check_solved

result, incorrectlist = Check_solved.is_strongly_solved(ai_abs_tt)
```

実行結果

```
100%|██████████| 431/431 [00:03<00:00, 132.59it/s]
413/431 95.82%
False
```

## `ai_abs_tt` が強解決の AI でない原因の検証

__`ai_abs_tt`__ が __強解決の AI でない原因__ を[以前の記事](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#ai14s-%E3%81%8C%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E9%81%B8%E6%8A%9E%E3%81%97%E3%81%AA%E3%81%84%E5%B1%80%E9%9D%A2%E3%81%AE%E6%A4%9C%E8%A8%BC)と同様の方法で検証することにします。

まず、下記のプログラムで `ai_abs_tt` が __最善手を着手しない局面__ について、その __局面__、__候補手の一覧__、__最善手の一覧__ を表示します。下記のプログラムの意味について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E7%9D%80%E6%89%8B%E3%81%97%E3%81%AA%E3%81%84%E5%B1%80%E9%9D%A2%E3%81%AE%E8%A1%A8%E7%A4%BA)を復習して下さい。なお、以前の記事では最善手を着手しない局面の一覧の中の最初の局面のみ表示しましたが、下記のプログラムではすべての局面を表示しています。また、下記の実行結果には 18 種類の局面の中の最初の 3 つのみを表記しました。

```python
for mb, candidate, bestmoves in incorrectlist:
    print(mb)
    print("candidate", candidate)
    print("bestmoves", bestmoves)
```

実行結果

```
Turn x
O..
...
...

candidate {(0, 1), (1, 2), (2, 1), (1, 1), (2, 0), (0, 2), (2, 2), (1, 0)}
bestmoves {(1, 1)}
Turn x
oxO
...
...

candidate {(0, 1), (1, 2), (2, 1), (1, 1), (0, 2), (2, 2)}
bestmoves {(1, 1)}
Turn o
ox.
o.X
...

candidate {(2, 2), (1, 1), (2, 0), (0, 2)}
bestmoves {(1, 1), (2, 2), (0, 2)}
略
```

### 検証する局面の選択と最善手でない着手が選択されることの確認

上記の最初の 2 つの局面は、候補手の一覧と最善手の一覧が大きく異なっているため __検証しづらい__ ので、候補手の一覧と最善手の一覧が 1 つだけ異なる下記の __3 つ目の局面に対して検証を行う__ ことにします。次の 〇 の手番で __(2, 0)__ に 〇 が着手を行うと __〇 の勝利になる__ ので、この局面は __〇 の必勝の局面__ です。

```
Turn o
ox.
o.X
...
```

この局面での __`ai_abs_tt` の候補手の一覧と最善手の一覧__ は下記のようになっているので、__`ai_abs_tt`__ はこの局面に対して __(2, 0)__ という __間違った着手を選択する可能性がある__ ことが確認できます。

* 候補手の一覧：(2, 2)、(1, 1)、(2, 0)、(0, 2)
* 最善手の一覧：(1, 1)、(2, 2)、(0, 2)

まず、__(2, 0) が最善手でないことを検証__ することにします。

(0, 2) に 〇 が着手を行うと下記の局面になります。

```
Turn x
oxO
o.x
...
```

この局面では × は (0, 2) に着手を行わないと次の 〇 の手番で敗北するので、__× の最善手は (0, 2)__ になります。下記は (0, 2) に × が着手を行った局面です。

```
Turn o
oxo
o.x
X..
```

特に難しくはないので詳細は省略しますが、この局面で __〇 と × が最善手を着手し続ける__ と __引き分け__ になります。__必勝の局面であるにもかかわらず__ 先程の局面で (2, 0) に着手を行うと __引き分けの局面になる__ ことから、__(2, 0) は最善手ではない__ ことが確認できました。

:::note
先程の局面で __すぐに勝利しない (1, 1)__  などが __最善手__ の中に入っているのは、先程 Check_solved で `ai_abs_tt` を検証した際に仮引数 __`shortest_victory` にデフォルト値である `False` が代入されたから__ です。その場合は、__最短の勝利を考慮しない__ ので、__すぐに勝利しない合法手も最善手として計算されます__。(1, 1) に着手を行うとすぐに勝利することはできませんが、下記のように (2, 0) と (2, 2) の 2 箇所に勝利できるマスがあり、次の × の着手で × が勝利できないので (1, 1) は最善手です。

```
Turn x
ox.
oOx
...
```

詳細は省略しますが、最善手の一覧のにある (2, 2) も最善手です。
:::


### 検証する局面を表すノードの計算

局面を表す Node クラスのインスタンスには __合法手をキー__ とし、キーの値にその __合法手を着手した局面__ を表す dict が代入された __[`chilnode_by_move`](https://qiita.com/ysgeso/items/7b687d25a4ab300f5865#node-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE%E4%BF%AE%E6%AD%A3)__ 属性があります。__検証する局面__ は (0, 0)、(1, 0)、(0, 1)、(2, 1) の順で着手が行われた局面なので、下記のプログラムで __ルートノードからこの局面のノードを計算__ することができます[^3]。また、実行結果から検証する局面を表すノードが計算されたことが確認できます。

```python
node = mbtree.root.children_by_move[(0, 0)].children_by_move[(1, 0)].children_by_move[(0, 1)].children_by_move[(2, 1)]
print(node.mb)
```

実行結果

```
Turn o
ox.
o.X
...
```

### `ai_abs_tt` が選択する着手の確認

次に、下記のプログラムで __`ai_abs_tt`__ がこの局面に対して選択する __合法手の一覧__ を表示します。実行結果から、確かに __`ai_abs_tt`__ はこの局面に対して、__(2, 0)、(1, 1)、(0, 2)、(2, 2) の 4 つの合法手を選択__ することが確認できました。また、`ai_abs_tt` がこの 4 つの合法手を着手した局面に 1 という評価値を、残りの (1, 2) に着手した局面に 0 という評価値を計算したことも確認できます。

```python
ai_abs_tt(node.mb, analyze=True)
```

実行結果

```
{'candidate': [(2, 0), (1, 1), (0, 2), (2, 2)],
 'score_by_move': {(2, 0): 1, (1, 1): 1, (0, 2): 1, (1, 2): 0, (2, 2): 1}}
```

### `ai_abs_tt` が最善手でない合法手を選択する原因の検証

次に、__`ai_abs_tt`__ がこの局面でが __最善手でない (2, 0) という合法手を選択する原因__ について検証することにします。どのように検証すればよいかについて少し考えてみて下さい。

その検証は、置換表を利用した αβ 法でこの局面の __評価値を計算する過程を Mbtree_Anim で確認__ することで行うことが出来ます。まず、下記のプログラムで先程計算した __このノードに対して `calc_score_by_ab`__ を実行して __置換表を利用した αβ 法で評価値を計算__ する処理を行い、__Mbtree_Anim__ を利用してその __計算の過程を確認__ します。実行結果のように、最初のフレームに __このノードが赤い枠で囲まれたゲーム木の部分木__ が表示されます。

以後は、__検証する赤枠のノードを $N$ と表記__ することにします。また、実際の Mbtree_Anim の実行結果には表示されませんが、わかりやすさを重視して実行結果の図のように __部分木の図に $N$ などの表記を行う__ ことにします。

```python
from tree import Mbtree_Anim

mbtree.calc_score_by_ab(node, use_tt=True)
Mbtree_Anim(mbtree, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/36575c1d-c89b-bac9-a40e-b854cb37c414.png" width="500">

上図では $N$ の __最初の子ノード__ がこの AI が選択する可能性がある __最善手ではない (2, 0)__ に着手を行った子ノードです。__この子（child）ノードを以後は $C$ と表記__ することにします。

下段の > をクリックして __$C$ の評価値が確定__ した 123 フレーム目を表示すると、下図のように __$C$ の評価値が 1 と計算された__ ことが確認できます。先程検証したように $N$ の局面で __(2, 0) に着手を行うと引き分けの局面になる__ ので __正しくは 0 と計算される必要があります__。従って、下図から __$C$ の評価値の計算が間違っている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4211dba1-1b13-c08b-ecd4-89bda28bd4fb.png" width="500">

$C$ の評価値の計算が間違って行われる理由を検証するために、以下の操作を行って __$C$ の評価値がどのように計算されるか__ を確認します。Mbtree_Anim で様々な情報を確認するための操作方法について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/ffa55bf637e6810b0330#%E6%A7%98%E3%80%85%E3%81%AA%E6%83%85%E5%A0%B1%E3%81%AE%E7%A2%BA%E8%AA%8D%E6%96%B9%E6%B3%95)を復習して下さい。

* 下段の < をクリックして __最初のフレームに戻る__
* 上段の > をクリックして __$C$ の計算を開始するフレームに移動__ する
* 下段の >> をクリックして __$C$__ の __すべての子ノードの評価値が計算__ されて $C$ の評価値が確定した __フレームに移動__ する

下図は上記の操作を行った結果表示される 122 フレーム目の図です。なお、$C$ の局面で __× が (0, 2) に着手__ を行った __$C$ の 2 つ目の子ノード__ の事を、$N$ の孫（grandchild）ノードであることから __$G$ と表記__ することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/66e74313-6560-c917-ad62-5f004fa1bd09.png" width="500">

上図から以下の事がわかります。

* $C$ の 4 つの子ノードのうち、× が (0, 2) に着手を行った __$G$ 以外の子ノード__ は、その次に 〇 が (2, 0) に着手を行えば __〇 が勝利する__ ので __評価値は 1 である__
* 上図ではそれらの子ノードの評価値に 1 が表示されているので、__それらの子ノードの評価値は正しく計算されている__ ことが確認できる
* __$G$ の局面__ は先程検証したように __引き分けの局面__ であるので __評価値は 0 である__ が、上図では評価値として __間違った 1 が計算されている__

__$G$ の評価値が正しく 0 と計算__ されれば、$C$ は min ノードなので __$C$ の評価値も正しく 0 と計算される__ ようになります。従って、__$C$ の評価値が間違って計算される理由__ は __$G$ の評価値が間違って計算されることである__ ことがわかりました。

$G$ の評価値が間違って計算が行われる理由を検証するために、以下の操作を行って __$G$ の評価値がどのように計算されるか__ を確認します。

* 下段の << をクリックして __$C$ の計算を開始するフレームに移動__ する
* 下段の > をクリックして __$G$ の 前の子ノードの評価値が計算されたフレームに移動__ する
* 上段の > を 2 回クリックして __$G$ の計算を開始するフレームに移動__ する
* 下段の >> をクリックして __$G$__ の __すべての子ノードの評価値が計算__ されて $G$ の評価値が確定した __フレームに移動__ する

下図は上記の操作を行った結果表示される 82 フレーム目の図です。なお、$G$ の局面で __〇 が (2, 2) に着手__ を行った __$G$ の 3 つ目の子ノード__ の事を、$G$ の次のアルファベットを使って __$H$ と表記__ することにします[^4]。また、$H$ の最初の子ノードを $H$ の次のアルファベットを使って $I$ と表記することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/56ff6cf8-ab34-979c-0e9b-20ad1c090908.png" width="500">

上図から以下の事がわかります。

* $G$ は max ノードで、3 つの子ノードの評価値が 0、0、1 と計算されている。従って、__$H$ の評価値が 1 と計算されたことによって $G$ の評価値が 1 と計算される__
* $H$ は min ノードで、2 つの子ノードの評価値が 1、1 と計算されているため評価値が 1 と計算される
* $I$ の局面は次の 〇 の (1, 2) への着手で __引き分けになる__ ので __評価値は 0 になるはず__ であるが、__評価値として 1 が計算__ されている点が __間違っている__
* __$H$ の 2 つ目の子ノード__ は次の 〇 の (1, 1) への着手で 〇 の勝利になるので、__評価値が 1 と計算されるのは正しい__
* __$I$ の評価値が正しく 0 と計算されれば__、その祖先ノードの $H$、$G$、__$C$ の評価値が正しく 0 と計算される__ ようになる。従って、__$C$ の評価値が間違って 1 と計算される原因__ は __$I$ の評価値が間違って計算されること__ である

$I$ の評価値が間違って計算が行われる理由を検証するために、以下の操作を行って __$I$ の評価値がどのように計算されるか__ を確認します。

* 下段の << をクリックして __$G$ の計算を開始するフレームに移動__ する
* 下段の > を 2 回クリックして __$H$ の 前の子ノードの評価値が計算されたフレームに移動__ する
* 上段の > を 2 回クリックして __$H$ の計算を開始するフレームに移動__ する
* 上段の > を 1 回クリックして __$I$ の計算を開始するフレームに移動__ する

下図は上記の操作を行った結果表示される 69 フレーム目の図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c6c8c91b-2650-e1eb-30db-2c387832af0d.png" width="500">

上図は __[薄緑色で表示](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree_anim-%E3%81%AE%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-update_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3)__ され、__赤字で「置換表による置換」と表示__ されることから、__$I$ の局面の評価値が置換表に登録__ されており、__その評価値が 1 である__ ことが確認できます。このことから、__$I$ の評価値が間違って 1 と計算される原因__ が __置換表に $I$ の局面の評価値が 1 と登録されている__ ことであることが確認できました。

### 置換表に間違った評価値が登録される原因の確認

上図で __$I$ の局面の評価値が置換表に登録されている__ ということは、上図の __69 フレーム目よりも前__ に、__$I$ と同じ局面の評価値が計算された__ ことを意味します。そこで、下記の操作を行うことで、__$I$ と同じ局面が計算されたフレームを探す__ ことにします。

* IntSlider をドラッグして最初の 0 フレーム目に移動する
* 上段の > ボタンをクリックして __1 フレームずつ表示を確認__ して探す[^5]

下図は上記の操作で __$I$ と同じ局面のノード__ の __子ノードの評価値の計算__ が行われた 22 フレーム目を表示した際の図です。以後は下図の赤枠の __$I$ と同じ局面のノードを $I'$__、__その子ノードを $J$ と表記__ することにします。

__$J$ は引き分けの局面__ なので __評価値が 0 と計算__ されていますが、__$I'$ は max ノード__ でこのフレームでの __α 値が 1__ であるため __赤字で「α 値の更新なし」が表示__ され、__このノードの評価値を表す α 値は 1 のまま更新されない__ ことになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f5442a0e-b365-90b4-6c06-829ce7c14315.png" width="500">

実際にこの 2 フレーム後の下図では __$I'$ の評価値が α 値である 1 と計算__ され、__その評価値が置換表に登録__ された結果 $I'$ と同じ局面の __$I$ の評価値が 1 と計算される__ ことになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/348ec974-43da-bb86-9b52-7c2dcd171d59.png" width="500">

## バグの原因と修正

[以前の記事](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)で説明したように、__αβ 法__ では __ルートノード以外のノードの評価値が正しく計算されない場合__ があります。具体的には __max ノード__ では __下記の場合に評価値が正しく計算されません__[^6]。min ノードの場合の説明は同様なので省略します。

* __全ての子ノードの評価値__ がこのノードの評価値を計算する際の __α 値の初期値より小さい場合__ は、__実際の評価値よりも大きな α 値__ が評価値として計算される
* __β 値より大きな評価値__ の __子ノードが見つかった時点__ で β 狩りを行い、__残りの子ノードの評価値の計算を省略する__ ので、省略された子ノードの中にそれよりも大きな評価値を持つノードが存在する場合は __本当の評価値より小さな評価値__ が計算される 

上記のように、__αβ 法__ で計算される __ノードの評価値__ はそのノードの評価値を計算する際の __α 値と β 値の初期値によって影響を受けます__。そのため、__同じ局面であっても α 値と β 値の初期値が異なっている場合__ は __異なる評価値が計算される場合があります__。

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

:::note warn
__αβ 法__ では __α 値と β 値の初期値が異なる場合__ は、__同じ局面であっても異なる評価値が計算される場合がある__。そのため、αβ 法では __局面と評価値を対応させた置換表__ を __利用することはできない__。
:::

実際に同じ局面である $I$ と $I'$ の評価値を計算する際の α 値 と β 値の初期値を比べてみると、下図の __$I$ の計算を開始する直前__ の 68 フレーム目[^7]から __$I$ を計算する際の α 値の初期値は 0、β 値の初期値は 1__ であることがわかります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/49378ab4-1774-6e0f-3a66-a9634885e7fa.png" width="500">

一方、下図の __$I'$ の計算を開始する__ の 22 フレーム目から __α 値の初期値は 1、β 値の初期値は 正の無限大__ となっており、$I$` と $I'$ では __α 値と β 値の初期値が異なる__ ことがわかります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f5442a0e-b365-90b4-6c06-829ce7c14315.png" width="500">

__$I$ と $I'$ は同じ局面__ なので、__同じ子ノードを持ちます__。また、子ノードとしてはどちらも __引き分け__ になる __評価値が 0 の子ノードを一つだけ持ちます__。

__$I'$ の評価値__ は __α 値が 1 の状態で計算__ されたので __子ノードの評価値が 0 であっても 1 と計算__ されましたが、__$I$ の評価値__ は __α 値が 0 の状態で計算__ するため、__子ノードの評価値が 0 の場合__ に $I'$ のように __1 と計算することはできません__。

上記から、バグの原因が __α 値と β 値の初期値が異なる同じ局面のノード__ に対して、__局面と評価値を対応させた置換表__ を使って __評価値を計算した__ ことであることがわかりました。

このバグを修正する方法について少し考えてみて下さい。

## 3 つのデータをキーとする置換表を利用した修正方法

__αβ 法__ での評価値の計算方法から、__局面__ と __α 値の初期値__ と __β 値の初期値__ の __3 つがすべて等しい場合__ は __同じ評価値が計算される__ ことがわかります。従って、__置換表の dict のキー__ を局面だけのデータから __局面__ と __α 値の初期値__ と __β 値の初期値__ に変更し、__その 3 つが全て一致する場合に置換表を利用__ するように修正するという方法が考えられるでしょう。

:::note
実はこの方法は __効率が悪い方法__ なので、置換表を利用した αβ 法の処理で実際に利用されることはまずありません。ただし、この方法は __直観的にわかりやすい__ ので今回の記事ではこの方法でバグを修正することにします。より効率的な方法については次回の記事で説明します。
:::

下記はそのように __`ai_abs_tt`__ を修正したプログラムです。なお、__置換表の dict のキー__ としては、__`(局面の情報, α 値の初期値, β 値の初期値)`__ という __tuple を採用__ しました。

* __4 ~ 6 行目__：__このノードを表すキー__ として __`(局面の情報, α 値の初期値, β 値の初期値)` を表す tuple を計算__ して __ローカル変数 `key` に代入__ する。そのキーが置換表に登録されている場合に置換表に登録された評価値をこのノードの評価値として返すように修正する
* __8 ~ 10 行目__：__α 値と β 値__ はこのノードの評価値を計算する際に __更新されている可能性がある__。__それらの初期値__ は 4 行目で __`key` に代入した__ ので 8 行目で __それらを取り出し__、10 行目で __同一局面のキーを計算__ して __同一局面の評価値を置換表に登録__ するように修正する

```python
 1  @ai_by_score
 2  def ai_abs_tt(mb, debug=False, shortest_victory=False):            
元と同じなので省略
 3          boardtxt = mborig.board_to_str()
 4          key = (boardtxt, alpha, beta)
 5          if key in tt:
 6              return tt[key]
元と同じなので省略
 7          boardtxtlist = calc_same_boardtexts(mborig)
 8          _, alpha, beta = key
 9          for boardtxt in boardtxtlist:
10              tt[(boardtxt, alpha, beta)] = score
11          return score
元と同じなので省略
```

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

```python
@ai_by_score
def ai_abs_tt(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]

        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = ab_search(mb, tt, alpha, beta)
                if score >= beta:
                    alpha = score
                    break
                alpha = max(alpha, score)
            score = alpha
        else:
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                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)
        _, alpha, beta = key
        for boardtxt in boardtxtlist:
            tt[(boardtxt, alpha, 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
@ai_by_score
def ai_abs_tt(mb, debug=False, shortest_victory=False):            
元と同じなので省略
        boardtxt = mborig.board_to_str()
-       if boardtxt in tt:
+       key = (boardtxt, alpha, beta)
+       if key in tt:
-           return tt[boardtxt]
+           return tt[key]
元と同じなので省略
        boardtxtlist = calc_same_boardtexts(mborig)
+       _, alpha, beta = key
        for boardtxt in boardtxtlist:
-           tt[boardtxt] = score
+           tt[(boardtxt, alpha, beta)] = score
        return score
元と同じなので省略
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果から __`ai_abs_tt` が強解決の AI になった__ ことが確認できます。

```python
result, incorrectlist = Check_solved.is_strongly_solved(ai_abs_tt)
print(result)
```

実行結果

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

また、下記のプログラムで __最短の勝利を優先する評価値を計算する場合__ も `ai_abs_tt` が強解決の AI であることが確認できます。

```python
result, incorrectlist = Check_solved.is_strongly_solved(ai_abs_tt, 
                                                        params={"shortest_victory": True})
print(result)
```

実行結果

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

## Mbtree クラスの `calc_score_by_ab` の修正

__置換表を利用した αβ 法の効率を確認__ するために、__`calc_score_by_ab`__ の処理を下記のプログラムのように修正します。修正内容は上記の __`ai_abs_tt` の修正とほぼ同じ__ です。

なお、__`calc_score_by_ab`__ で __ミニマックス法で評価値を計算する際__ には、__[α 値と β 値の初期値を必ず負の無限大と正の無限大にしてから計算を行っている](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3-%E3%81%9D%E3%81%AE-1)__ ので、置換表に登録する際の __キーはどの局面でも `(局面の情報, 負の無限大, 正の無限大)`__  という tuple になります。従って上記の修正を行っても __置換表を利用したミニマックス法の評価値を正しく計算できます__。

* __8 ~ 10 行目__：返り値を返さずに評価値を `node.score` に代入する点を除くと `ai_abs_tt` の 4 ~ 6 行目の修正と同じ
* __15 ~ 17 行目__：`score` が `node.score` になっている点を除くと `ai_abs_tt` の 8 ~ 10 行目の修正と同じ

```python
 1  def calc_score_by_ab(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False):
元と同じなので省略
 2      def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
 3          if minimax:
 4              alpha = float("-inf")
 5              beta = float("inf")
 6          if use_tt:
 7              boardtxt = node.mb.board_to_str()
 8              key = (boardtxt, alpha, beta)
 9              if key in tt:
10                  node.score = tt[key]
元と同じなので省略
11          if use_tt:
12              from util import calc_same_boardtexts   
13              
14              boardtxtlist = calc_same_boardtexts(node.mb)
15              _, alpha, beta = key
16              for boardtxt in boardtxtlist:
17                  tt[(boardtxt, alpha, beta)] = node.score            
18          return node.score
元と同じなので省略
19      
20  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

```python
def calc_score_by_ab(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False):
    def assign_pruned_index(node, index):
        node.pruned_index = index
        self.num_pruned += 1
        for childnode in node.children:
            assign_pruned_index(childnode, index)
        
    def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
        if minimax:
            alpha = float("-inf")
            beta = float("inf")
        if use_tt:
            boardtxt = node.mb.board_to_str()
            key = (boardtxt, alpha, beta)
            if key in tt:
                node.score = tt[key]
                if node.mb.turn == Marubatsu.CIRCLE:
                    alpha = node.score
                else:
                    beta = node.score
                self.nodelist_by_score.append(node)
                self.num_calculated += 1     
                for childnode in node.children:
                    assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
                self.ablist_by_score.append((alpha, beta, None, "tt",
                                             self.num_calculated, self.num_pruned))
                node.score_index = len(self.nodelist_by_score) - 1  
                return node.score
                
        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, None, "start",
                                    self.num_calculated, self.num_pruned))
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            if node.mb.turn == Marubatsu.CIRCLE:
                alpha = node.score
            else:
                beta = node.score
        else:
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score",
                                                self.num_calculated, self.num_pruned))
                    if score > alpha:
                        alpha = score
                    self.nodelist_by_score.append(node)
                    if score >= beta:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                self.num_calculated, self.num_pruned))
                    if score >= beta:
                        break
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score",
                                                self.num_calculated, self.num_pruned))
                    if score < beta:
                        beta = score
                    self.nodelist_by_score.append(node)
                    if score <= alpha:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                self.num_calculated, self.num_pruned))
                    if score <= alpha:
                        break
                node.score = beta

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append((alpha, beta, None, "end",
                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1  
        if use_tt:
            from util import calc_same_boardtexts   
            
            boardtxtlist = calc_same_boardtexts(node.mb)
            _, alpha, beta = key
            for boardtxt in boardtxtlist:
                tt[(boardtxt, alpha, beta)] = node.score            
        return node.score

    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
        node.pruned_index = float("inf")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    self.num_calculated = 0
    self.num_pruned = 0
    if init_ab:
        alpha = -2 if self.shortest_victory else -1
        beta = 3 if self.shortest_victory else 1
    else:
        alpha = float("-inf")
        beta = float("inf")
    calc_ab_score(abroot, {}, alpha, beta)
    total_nodenum = self.num_pruned + self.num_calculated
    ratio = self.num_calculated / total_nodenum * 100
    dprint(debug, "ミニマックス法で計算したか", minimax)    
    dprint(debug, "計算したノードの数",  self.num_calculated)
    dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
    dprint(debug, "合計",  total_nodenum)
    dprint(debug, f"割合 {ratio:.1f}%")
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

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

```diff_python
def calc_score_by_ab(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False):
元と同じなので省略
    def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
        if minimax:
            alpha = float("-inf")
            beta = float("inf")
        if use_tt:
            boardtxt = node.mb.board_to_str()
-           if boardtxt in tt:
+           key = (boardtxt, alpha, beta)
+           if key in tt:
-               node.score = tt[boardtxt]
+               node.score = tt[key]
元と同じなので省略
        if use_tt:
            from util import calc_same_boardtexts   
            
            boardtxtlist = calc_same_boardtexts(node.mb)
+           _, alpha, beta = key
            for boardtxt in boardtxtlist:
-               tt[boardtxt] = node.score            
+               tt[(boardtxt, alpha, beta)] = node.score            
        return node.score
元と同じなので省略
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

上記の修正後に下記のプログラムを実行して、先程のノード $N$ の評価値を計算し、Mbtree_Anim で表示することにします。

```python
mbtree.calc_score_by_ab(node, use_tt=True)
Mbtree_Anim(mbtree, isscore=True)
```

実行後に下段の >> ボタンをクリックすると、下図のように __$C$ のノードの評価値が正しく 0 と計算される__ ようになったことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/be7a328e-cf7c-f6b9-e1f9-91892c36a87b.png" width="500">

また、__$I$ のノードの評価値の計算が開始__ された下図の 67 フレーム目は __背景が白色で表示__ されており、__置換表が利用されなくなった__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3c26bbc8-b06c-343b-a382-eb7543296826.png" width="500">

また、__$I$ のノードの評価値が確定__ した下図の 71 フレーム目では __$I$ の評価値が正しく 0 と計算されるようになった__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9ba9c5a6-36c4-cc79-3b19-04342db7d95d.png" width="500">

一方、__α 値と β 値の初期値が同じ同一局面__ を探したところ、下図の 132 フレーム目と 241 フレーム目の赤枠の同一局面のノードが見つかりました。 2 つのノードの __α 値と β 値の初期値はどちらも α 値が 1、β 値が正の無限大__ となっており、__241 フレーム目の図の背景色が薄緑色__ になっていることから、__実際に置換表による枝狩りが行われた__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ff9747c9-1692-cd9e-4c11-7c9647cfb6e0.png" width="500">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b124845e-ffa2-ecb2-61b1-aa8294b49101.png" width="500">

## 3 つのデータをキーとした置換表を利用した αβ 法の効率

__局面と α 値と β 値の初期値をキー__ とした置換表を利用した αβ 法の __効率を確認する__ ために、下記のプログラムで __ミニマックス法と αβ 法の両方__ で __置換表を利用する場合としない場合__ の評価値の計算を __`calc_score_by_ab`__ で計算して __比較します__。なお、見やすいようにそれぞれの結果の間に `print()` で空行を表示するという工夫を行ないました。

```python
print("ミニマックス法で置換表を利用しない")
mbtree.calc_score_by_ab(mbtree.root, minimax=True, debug=True)
print()
print("ミニマックス法で置換表を利用する")
mbtree.calc_score_by_ab(mbtree.root, minimax=True, use_tt=True, debug=True)
print()
print("αβ 法で置換表を利用しない")
mbtree.calc_score_by_ab(mbtree.root, debug=True)
print()
print("αβ 法で置換表を利用する")
mbtree.calc_score_by_ab(mbtree.root, use_tt=True, debug=True)
```

実行結果

```
ミニマックス法で置換表を利用しない
ミニマックス法で計算したか True
計算したノードの数 549946
枝狩りしたノードの数 0
合計 549946
割合 100.0%

ミニマックス法で置換表を利用する
ミニマックス法で計算したか True
計算したノードの数 2271
枝狩りしたノードの数 547675
合計 549946
割合 0.4%

αβ 法で置換表を利用しない
ミニマックス法で計算したか False
計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%

αβ 法で置換表を利用する
ミニマックス法で計算したか False
計算したノードの数 1718
枝狩りしたノードの数 548228
合計 549946
割合 0.3%
```

下記は上記の結果を表にまとめたものです。上段が計算したノードの数、下段が割合を表します。この結果の内、今回の記事で新しく実装した __置換表を利用した αβ 法以外の結果__ は、__これまでの記事での結果と同じ値が表示__ されているので、__今回の修正を行ってもそれらの計算を正しく行うことが出来る__ ことが確認できました。

|  | ミニマックス法 | αβ 法 |
|:-:|--:|--:|
| __置換表の利用なし__ | 549946<br>100.0 %|  18297<br>3.3 % |
| __置換表の利用あり__  |  2271<br>0.4% | 1718<br>0.3 %   |

上記の表から、__αβ 法__ の場合は __置換表を利用してもあまり大きな効果が得られていない__ ことがわかります。その理由は、__同一局面で α 値と β 値の初期値が一致するノードの数があまり多くない__ ことが原因です。

そのことは、下記のプログラムで最短の勝利を優先する評価値を計算した場合で上記と同じ処理を実行することで確認することが出来ます。

```python
mbtree_sv = Mbtree.load("../data/abtree_sv_root")

print("ミニマックス法で置換表を利用しない")
mbtree_sv.calc_score_by_ab(mbtree_sv.root, minimax=True, debug=True)
print()
print("ミニマックス法で置換表を利用する")
mbtree_sv.calc_score_by_ab(mbtree_sv.root, minimax=True, use_tt=True, debug=True)
print()
print("αβ 法で置換表を利用しない")
mbtree_sv.calc_score_by_ab(mbtree_sv.root, debug=True)
print()
print("αβ 法で置換表を利用する")
mbtree_sv.calc_score_by_ab(mbtree_sv.root, use_tt=True, debug=True)
```

実行結果

```
ミニマックス法で置換表を利用しない
ミニマックス法で計算したか True
計算したノードの数 549946
枝狩りしたノードの数 0
合計 549946
割合 100.0%

ミニマックス法で置換表を利用する
ミニマックス法で計算したか True
計算したノードの数 2271
枝狩りしたノードの数 547675
合計 549946
割合 0.4%

αβ 法で置換表を利用しない
ミニマックス法で計算したか False
計算したノードの数 20866
枝狩りしたノードの数 529080
合計 549946
割合 3.8%

αβ 法で置換表を利用する
ミニマックス法で計算したか False
計算したノードの数 2583
枝狩りしたノードの数 547363
合計 549946
割合 0.5%
```

下記は上記の結果を表にまとめたものです。この結果から、__置換表を利用した場合__ はミニマックス法より、__αβ 法のほうが効率が悪くなってしまう__ ことがわかります。

|  | ミニマックス法 | αβ 法 |
|:-:|--:|--:|
| __置換表の利用なし__ | 549946<br>100.0 %|  20866<br>3.8 % |
| __置換表の利用あり__  |  2271<br>0.4% | 2583<br>0.3 %   |

このようなことが起きる理由は以下の通りです。

* __最短の勝利を優先しない場合__
    * __評価値の種類__ が -1、0、1 の __3 種類しかない__
    * そのため、__α 値と β 値の初期値の組み合わせが少ない__
    * そのため、__同一局面で α 値と β 値の初期値が同じノード__ が __比較的多く存在__ する
* __最短の勝利を優先する場合__
    * __評価値の種類__ が -2 ~ 3 の __6 種類もある__
    * そのため、__α 値と β 値の初期値の組み合わせが多い__
    * そのため、__同一局面で α 値と β 値の初期値が同じノード__ が __あまり多く存在しない__

このように、__局面と α 値と β 値の初期値をキー__ とした置換表では、__α 値と β 値の組み合わせが多くなる__ と置換表を利用できるノードの数が少なくなるため、__置換表による枝狩りの効率が悪くなる__ という問題があります。また、これまでの例では評価値を整数の値として計算しましたが、__評価値を実数で計算__ するような場合は __α 値と β 値の組み合わせが無数になり__、置換表による __枝狩りがほとんど行われなくなる__ こともあります。

従って、置換表を利用した αβ 法の処理を行う場合は、次回の記事で説明する __もっと効率のよい方法__ を取る必要があります。余裕がある方はその方法について考えてみて下さい。

# 今回の記事のまとめ

今回の記事では置換表を利用した αβ 法の処理のバグの検証と、局面 と α 値の初期値 と β 値の初期値という 3 つの値をキーとした置換表の実装方法について紹介しました。

ただし、この実装方法は枝狩りの効率が良くないので、次回の記事ではもっと効率の良い置換表の実装方法について説明します。

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

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

次回の記事

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

[^1]:仮引数 `minimax` はデフォルト値が `False` のデフォルト引数なのでこのキーワード引数を記述する必要はありませんが、ミニマックス法を利用していないことを明確にするために記述しています。以後の記事では `minimax=False` は省略することにします
[^2]:実は恥ずかしながら筆者も昔 αβ 法をしっかりと理解していなかったため、置換表を利用した αβ 法のプログラムを、この間違った方法で記述してしまったことがあります
[^3]:別の順でこの局面になるように着手を行っても構いません
[^4]:ひ孫は英語で great grandchild ですが、$GG$ という表記は長いので 1 文字の $H$ としました 
[^5]:$I$ の評価値を計算したフレームが 69 と小さいので先頭から順番に探していますが、$I$ のフレームが大きい場合は $N$ から $I$ と同じ局面になるような着手を辿って探したほうが良いでしょう
[^6]:そのように計算しても良い理由を忘れた方は[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF)と[以前の記事](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)を復習して下さい
[^7]:__置換表で評価値が計算されるノード__ は、__[最初のフレームで α 値または β 値が更新されるようにした](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3-%E3%81%9D%E3%81%AE-2)__ ため、__α 値と β 値の初期値を知るため__ には、__その直前のフレームを表示する必要__ があります。この点はわかりづらいので次回の記事で修正することにします