Pythonで〇×ゲームのAIを一から作成する　その151　置換表によるミニマックス法の枝狩り

# 目次と前回の記事

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

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

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

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

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

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

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

# α 値と β 値の初期値の変更による枝狩り

これまでは、αβ 法で評価値を計算する際に、__α 値と β 値の初期値__ として __負の無限大と正の無限大を設定__ して計算を行いました。αβ 法では __子ノードの評価値を計算__ する際に、__親ノードの α 値と β 値をそのまま引き継いで__ 計算を行うので、下図の深さが 0 ～ 7 の一番上のノードのように、__ルートノードから最初の子ノードを次々に辿ったノード__ の評価値を計算する際の __α 値と β 値の初期値__ はそれぞれ __負の無限大と正の無限大__ となります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/40b66758-8ef4-3679-4e88-10e613872946.png" width="500">

α 狩りは子ノードの評価値が α 以下、β 狩りは子ノードの評価値が β 以上の時に行われるので、上図の __深さが 0 ～ 7 の一番上のノード__ の評価値が計算された際に __α 狩りまたは β 狩りが行われることはありません__。

例えば下図の 9 フレーム目の赤枠の最初の子ノードの評価値が 1 と計算されると、α 値 < 評価値 < β 値なので __β 狩りは行われず__ 、下図の __α 値の更新が赤字で表示__ されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dd6c22f6-20c1-a29d-525e-76fc3baac668.png" width="500">

その結果、上図で下段の > ボタンをクリックすると下図のように実際に __β 狩りが行われず__ にその __次の子ノードの評価値が計算__ されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/843cc2fd-eb5a-ceb5-5412-4304e6b5f375.png" width="500">

__評価値の最小値と最大値がわかっている場合__ は、α 値と β 値の __初期値をその値に設定する__ ことで、上図の __深さが 0 ～ 7 の一番上のノードの評価値が計算された際__ に __α 狩りまたは β 狩りを行うことが出来るようになる__ ので、その実装を行ってみることにします。

なお、評価値の最小値と最大値がいくつになるかがわからないような場合はこの手法を用いることはできません。

## Mbtree クラスの `calc_score_by_ab` メソッドの修正

下記のプログラムのように、αβ 法で評価値の計算を行う __`calc_score_by_ab`__ に、α 値と β 値の初期値を __評価値の最小値と最大値で初期化（initialize）するかどうか__ を代入する __`init_ab` という仮引数を追加__ します。  

* __4 行目__：デフォルト値を `False` とする仮引数 `init_ab` を追加する
* __5 ~ 7 行目__：`init_ab` が `True` の場合の α 値と β 値の初期値を計算する。評価値の最小値と最大値は最短の勝利を目指すかどうかを表す [`shortest_victory`](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#%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%E5%A4%89%E6%9B%B4) 属性が `False` の場合は -1 と 1、`True` の場合は -2 と 3 なのでその値を計算する
* __8 ~ 10 行目__：`init_ab` が `False` の場合の α 値と β 値をこれまで通り負の無限大と正の無限大に設定する
* __11 行目__：上記で計算した α 値と β 値を実引数に記述して `calc_ab_score` を呼び出すように修正する[^1]

```python
 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3  
 4  def calc_score_by_ab(self, abroot, debug=False, init_ab=False):       
元と同じなので省略
 5      if init_ab:
 6          alpha = -2 if self.shortest_victory else -1
 7          beta = 3 if self.shortest_victory else 1
 8      else:
 9          alpha = float("-inf")
10          beta = float("inf")
11      calc_ab_score(abroot, alpha, beta)
元と同じなので省略
12      
13  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

```python
from tree import Mbtree
from marubatsu import Marubatsu

def calc_score_by_ab(self, abroot, debug=False, init_ab=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, alpha=float("-inf"), beta=float("inf")):
        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, 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, 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  
        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, "計算したノードの数",  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
from tree import Mbtree
from marubatsu import Marubatsu

-def calc_score_by_ab(self, abroot, debug=False):       
+def calc_score_by_ab(self, abroot, debug=False, init_ab=False):       
元と同じなので省略
+   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)
+   calc_ab_score(abroot, alpha, beta)
元と同じなので省略
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

下記のプログラムで __評価値の最小値と最大値を -1 と 1__ としてαβ 法で評価値を計算したゲーム木のデータをファイルから読み込み、__実引数に `init_ab=True` を記述__ することで α 値と β 値の初期値を評価値の最小値と最大値に設定して αβ 法で評価値を計算しなおすと、実行結果のように計算したノードの数の __割合が 3.1 % になる__ ことがわかります。

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

実行結果

```
計算したノードの数 16811
枝狩りしたノードの数 533135
合計 549946
割合 3.1%
```

__α 値と β 値の初期値を負の無限大と正の無限大__ とした場合は [以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E7%9B%AE%E7%9A%84%E3%81%AE%E3%81%8A%E3%81%95%E3%82%89%E3%81%84%E3%81%A8%E3%80%87%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%A7%E3%81%AE%E5%8A%B9%E7%8E%87)で示したように __割合は 3.3 %__ となるので、この工夫によって __若干枝狩りを多く行う__ ことが出来るようになったことが確認できました。

また、下記のプログラムを実行して先程の赤枠の子ノードの最初の子ノードの評価値が 1 と計算された 9 フレーム目を表示すると、__β 値の初期値が 1__ であるため 下図のように __β 狩りの文字が赤字__ になります。

```python
from tree import Mbtree_Anim

Mbtree_Anim(mbtree, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/05b687a3-c4f7-36d9-d27d-0f521cb235d6.png" width="500">

その結果、上図で下段の > ボタンをクリックすると下図のように __β 狩りが行われて残りの子ノードが暗く表示__ され、先程よりも __枝狩りがより多く行われる__ ことが確認できました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/11da17c7-bfe2-27d1-a7ba-4f6e488b3174.png" width="500">

本記事では行いませんが、興味がある方は最短の勝利を考慮した評価値を計算する場合についても確認してみて下さい。

なお、この工夫で __新たに枝狩りが行われる可能性が生じるノード__ は __ほんの一部に過ぎない__ ので、それほど多くの枝狩りが新たに行われるようになるわけではありませんが、枝狩りの効率が上がることに間違いはないので __評価値の最小値と最大値がわかっている場合はこの手法を取ったほうが良いでしょう__。

# 置換表を利用したミニマックス法での枝狩り

〇× ゲームでは、ゲーム盤上の __マークの配置が同じ__ であればそれまでに行われた着手の手順に関わらず __局面の状況は同じ__ になります。例えば、下図の局面は (0, 0)、(1, 0)、(2, 0) の順で着手が行われた場合と (2, 0)、(1, 0)、(0, 0) の順で着手が行われた場合の __2 種類の可能性__ がありますが、__どちらの場合でも引き分けの局面__ なので、__評価値は 0__ になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6d0a34a5-e662-a030-814a-d3507357fd7b.png" width="100">

あらかじめ評価値を計算したゲーム木を作成し、そこから作成した __局面と評価値の対応表を使って着手を選択__ する [`ai_gt6`](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#bestmoves_by_board-%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) は __この性質を利用__ しています。

:::note
この性質を満たさないゲームは数多くあります。例えばオセロにはどこにも着手を行えない場合は手番をパスするので、ゲーム盤上の配置だけからどちらの手番であるかを判断できない場合があります。そのため、局面の状況を計算するためにはゲーム盤上の配置だけでなく手番の情報が必要になります。将棋には千日手、囲碁にはコウという特殊なルール[^2]があるため、手番に加えてそれ以前の局面の情報が必要です。
:::

__ミニマックス法__ で評価値を計算する際に、__この性質を利用__ することで __下記の方法で枝狩りを行うことが出来ます__。なお、__αβ 法__ でも同様の方法をで枝狩りを行うことができますが、__下記の方法だけではうまくいかない__ ので、次回の記事で説明することにします。

* それまでに計算した __局面と評価値の対応表を記録__ するようにする
* __ノードの評価値が確定した際__ に、局面と評価値の対応表にそのノードの局面と評価値の情報を __記録する__
* __ノードの評価値を計算を開始する際__ に、局面と評価値の対応表に __そのノードの局面の評価値が記録されている場合__ は、記録されている値をそのノードの評価値とし、__そのノードの子孫ノードの枝狩りを行う__

ミニマックス法などの __ゲーム木の探索で利用する__ このような局面と評価値の対応表のことを、局面を表すデータを評価値に置換することとから、__置換表（transposition table）と呼びます__。〇× ゲームの場合は、下記の __局面と評価値の対応表と全く同じ方法__ で置換表を作成することが出来ます。

* 置換表を __dict で作成__ する
* __局面を表す文字列を計算__ する
* __局面を表す文字列をキー__ とし、__キーの値に評価値を代入__ する

:::note
__〇× ゲーム__ は[以前の記事](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#board-%E5%B1%9E%E6%80%A7%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E5%B1%80%E9%9D%A2%E3%81%A8%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%AF%BE%E5%BF%9C%E8%A1%A8%E3%81%AE%E4%BD%9C%E6%88%90)で説明したように局面の種類は 5478 しかないので、__全ての局面の評価値を置換表に記録することが出来ます__。そのため置換表を dict を利用して簡単に作成することができます。

一方、オセロ、将棋、囲碁などのようにゲーム木の __ノードの数が多すぎる場合__ は、置換表に記録するデータが __コンピューターのメモリに収まりきらなくなる__ という問題が発生します。そのような場合は、__置換表に記録できるデータの量__ をコンピューターの __メモリに収まる量に制限__ し、その量を超えたデータを記録する際には、__古いデータを置換表から削除する__ という工夫を行なう必要があるので、__dict をそのまま利用することはできません__。
:::

## Mbtree クラスの `calc_score_by_ab` メソッドの修正 その 1

Mbtree クラスには、ミニマックス法で評価値を計算する __`calc_score_by_bf`__ メソッドと __`calc_score_by_df`__ メソッドが定義されていますが、これらのメソッドで評価値を計算した場合は、__Mbtree_Anim で枝狩りの様子を表示することができません__。

そこで置換表を使ってミニマックス法で枝狩りを行った際に、__Mbtree_Anim で枝狩りの様子を表示できる__ ように、__`calc_score_by_ab`__ を __ミニマックス法で評価値を計算できるように修正__ することにします。具体的には、ミニマックス法で評価値を計算するかどうかを代入する __`minimax` という名前の仮引数を追加__ することにします。

なお、__`calc_score_by_ab`__ がミニマックス法の評価値の計算を行うように __修正する方法は簡単__ です。どのように修正すれば良いかについて少し考えてみて下さい。

:::note
`calc_score_by_ab` という名前のメソッドで、ミニマックス法で評価値を計算する点に違和感を感じる人は、メソッドの名前を別の名前に変更して下さい。
:::

__αβ 法__ は __ミニマックス法に対して α 値と β 値を導入することで枝狩りを行う__ アルゴリズムです。また、αβ 法はミニマックス法で評価値を計算する際に、__子ノードの評価値が α 値以下または β 値以上の場合__ に枝狩りを行います。従って、__`calc_score_by_ab`__ でノードの評価値を計算する際に、__α 値と β 値の初期値を負の無限大と正の無限大にする__ ことで __枝狩りが行われなくなる__ ので、__ミニマックス法と同じ処理__ が行われるようになります。

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

* __1 行目__：デフォルト値を `False` とする仮引数 `minimax` を追加する
* __9 ~ 11 行目__：`calc_ab_score` でノードの評価値を計算する際に、`minimax` が `True` の場合は α 値と β 値に負の無限大と正の無限大を代入する
* __12 行目__：ミニマックス法で評価値を計算したかどうかを表示するようにした

```python
 1  def calc_score_by_ab(self, abroot, debug=False, init_ab=False, minimax=False):
 2      def assign_pruned_index(node, index):
 3          node.pruned_index = index
 4          self.num_pruned += 1
 5          for childnode in node.children:
 6              assign_pruned_index(childnode, index)
 7          
 8      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
 9          if minimax:
10              alpha = float("-inf")
11              beta = float("inf")
元と同じなので省略
12      dprint(debug, "ミニマックス法で計算したか", minimax)
13      dprint(debug, "計算したノードの数",  self.num_calculated)
14      dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
15      dprint(debug, "合計",  total_nodenum)
16      dprint(debug, f"割合 {ratio:.1f}%")
17      
18  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

```python
def calc_score_by_ab(self, abroot, debug=False, init_ab=False, minimax=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, alpha=float("-inf"), beta=float("inf")):
        if minimax:
            alpha = float("-inf")
            beta = float("inf")
                
        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, 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, 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  
        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, init_ab=False, minimax=False):
+def calc_score_by_ab(self, abroot, debug=False, init_ab=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, alpha=float("-inf"), beta=float("inf")):
+       if minimax:
+           alpha = float("-inf")
+           beta = float("inf")
元と同じなので省略
+   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>

上記の修正後に下記のプログラムのように __キーワード引数 `minimax=True` を記述__ して __`calc_score_by_ab`__ を呼び出すと、実行結果のように __枝狩りしたノードの数が 0 と表示され__、__枝狩りが行われないミニマックス法で評価値の計算が行われた__ ことが確認できます。

```python
mbtree.calc_score_by_ab(mbtree.root, minimax=True, debug=True)
```

実行結果

```
ミニマックス法で計算したか True
計算したノードの数 549946
枝狩りしたノードの数 0
合計 549946
割合 100.0%
```

## Mbtree クラスの `calc_score_by_ab` メソッドの修正 その 2

次に、__`calc_score_by_ab`__ に置換表（transposition table）を利用するかどうかを代入する __`use_tt` という名前の仮引数を追加__ し、下記のプログラムのように __置換表を利用したミニマックス法で評価値を計算できる__ ように __`calc_score_by_ab`__ を修正します。

なお、__Mbtree_Anim で置換表による枝狩りが行われたことを表示できる__ ように、置換表による枝狩りが行われた場合の __[アニメーションのフレームの状態](https://qiita.com/ysgeso/items/741c2c18f0bc6fcdba27#%E9%81%B8%E6%8A%9E%E4%B8%AD%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E5%87%A6%E7%90%86%E3%81%8C%E9%96%8B%E5%A7%8B%E3%81%95%E3%82%8C%E3%81%9F%E3%83%95%E3%83%AC%E3%83%BC%E3%83%A0%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)を `"tt"` という文字列で表す__ ことにします。

* __1 行目__：デフォルト値を `False` とする仮引数 `use_tt` を追加する
* __2 行目__：ノードの評価値を計算するローカル関数 `calc_ab_score` に __置換表（transposition table）を表す dict を代入する仮引数 `tt` を追加__ する。[以前の記事](https://qiita.com/ysgeso/items/1dbfec99a08b8996f53c#%E3%83%90%E3%82%B0%E3%81%9D%E3%81%AE-2%E5%89%8D%E3%81%AB%E8%A1%A8%E7%A4%BA%E3%81%95%E3%82%8C%E3%81%9F%E9%A0%85%E7%9B%AE%E3%81%AE%E5%86%85%E5%AE%B9%E3%81%8C%E6%AE%8B%E3%82%8B)で説明したようにデフォルト引数のデフォルト値に dict のようなミュータブルなデータを代入するとバグの原因になりやすいので、__通常の仮引数として `tt` を追加__ する。なお、[通常の仮引数はデフォルト引数よりも前に記述する必要がある](https://qiita.com/ysgeso/items/c5dbe62b329f7936181a#%E3%83%87%E3%83%95%E3%82%A9%E3%83%AB%E3%83%88%E5%BC%95%E6%95%B0%E3%81%A8%E3%83%87%E3%83%95%E3%82%A9%E3%83%AB%E3%83%88%E5%BC%95%E6%95%B0%E5%80%A4)点に注意すること
* __3 ~ 14、26、27 行目__：置換表を利用する `use_tt` が `True` の場合の処理を行う
* __4、5 行目__：__[`board_to_str`](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#board-%E3%82%92%E6%96%87%E5%AD%97%E5%88%97%E3%81%AB%E5%A4%89%E6%8F%9B%E3%81%99%E3%82%8B%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9)__ メソッドを呼び出して __ゲーム盤を表す文字列を計算し__、その文字列のキーが置換表の dict に存在するかどうかを判定する
* __6 行目__：置換表に存在する場合は、そのキーの値をそのノードの評価値とする
* __7、8、11 ~ 13 行目__：評価値が計算されたので、このノードの情報を `nodelist_by_score` と `ab_list_by_score` の要素に記録する。この部分の処理はこのノードの評価値が確定した際に行う 21 ~ 25 行目とほぼ同じだが、__Mbtree_Anim での表示を区別できるように__、11 行目で `ablist_by_score` に記録する __このノードの状態を `"tt"` とした点が異なる__
* __9、10 行目__：置換表にこのノードの評価値が記録されている場合は、このノードの __全ての子ノードの枝狩りが行われる__ ので、__[`assign_pruned_index`](https://qiita.com/ysgeso/items/289c8067774951433941#pruned_index-%E5%B1%9E%E6%80%A7%E3%82%92%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)__ を呼び出して __枝狩りが行われたノードの数__ と、__子ノードとその子孫ノードが枝狩りが行われたことを記録__ する。この処理は、11 行目の __`ablist_by_score`__ の要素に __枝狩りが行われた数を登録する前__ に __計算する必要がある__ 点に注意すること
* __14 行目__：評価値を返り値として返して __`calc_ab_score` の処理を終了す__ る
* __17、20 行目__：子ノードの評価値を計算するために __`calc_ab_score`__ を再帰呼び出しする際に、__実引数 `tt` を記述する__ ように修正する
* __27、28 行目__：このノードの __評価値が確定した際__ に、__このノードの評価値の情報を置換表に記録__ する
* __30 行目__：__評価値の計算を開始する際__ は __置換表の中身は空__ なので、置換表のデータとして __実引数に空の dict を記述__ して __`calc_ab_score`__ を呼び出すように修正する

```python
 1  def calc_score_by_ab(self, abroot, debug=False, init_ab=False, minimax=False, use_tt=False):
元と同じなので省略
 2      def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
 3          if use_tt:
 4              boardtxt = node.mb.board_to_str()
 5              if boardtxt in tt:
 6                  node.score = tt[boardtxt]
 7                  self.nodelist_by_score.append(node)
 8                  self.num_calculated += 1     
 9                  for childnode in node.children:
10                      assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
11                  self.ablist_by_score.append((alpha, beta, None, "tt",
12                                               self.num_calculated, self.num_pruned))
13                  node.score_index = len(self.nodelist_by_score) - 1  
14                  return node.score
元と同じなので省略
15              if node.mb.turn == Marubatsu.CIRCLE:
16                  for childnode in node.children:
17                      score = calc_ab_score(childnode, tt, alpha, beta)
元と同じなので省略
18              else:
19                  for childnode in node.children:
20                      score = calc_ab_score(childnode, tt, alpha, beta)
元と同じなので省略
21          self.nodelist_by_score.append(node)
22          self.num_calculated += 1     
23          self.ablist_by_score.append((alpha, beta, None, "end",
24                                       self.num_calculated, self.num_pruned))
25          node.score_index = len(self.nodelist_by_score) - 1  
26          if use_tt:
27              tt[boardtxt] = node.score        
28          return node.score
29  
元と同じなので省略
30      calc_ab_score(abroot, {}, alpha, beta)
元と同じなので省略
31      
32  Mbtree.calc_score_by_ab = calc_score_by_ab
```

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

```python
def calc_score_by_ab(self, abroot, debug=False, init_ab=False, minimax=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 use_tt:
            boardtxt = node.mb.board_to_str()
            if boardtxt in tt:
                node.score = tt[boardtxt]
                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

        if minimax:
            alpha = float("-inf")
            beta = float("inf")
                
        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:
            tt[boardtxt] = 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, init_ab=False, minimax=False):
+def calc_score_by_ab(self, abroot, debug=False, init_ab=False, minimax=False, use_tt=False):
元と同じなので省略
-   def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
+   def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
+       if use_tt:
+           boardtxt = node.mb.board_to_str()
+           if boardtxt in tt:
+               node.score = tt[boardtxt]
+               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
元と同じなので省略
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta)
+                   score = calc_ab_score(childnode, tt, alpha, beta)
元と同じなので省略
            else:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta)
+                   score = calc_ab_score(childnode, tt, alpha, 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:
+           tt[boardtxt] = node.score        
        return node.score

元と同じなので省略
-   calc_ab_score(abroot, alpha, beta)
+   calc_ab_score(abroot, {}, alpha, beta)
元と同じなので省略
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように __置換表を使ってミニマックス法で評価値を計算__ した際の __割合が 2.9 %__ になることが確認できます。これは、__αβ 法__ を使って評価値を計算した際の __3.3 % よりも低い数値__ です。

```python
mbtree.calc_score_by_ab(mbtree.root, minimax=True, use_tt=True, debug=True)
```

実行結果

```
ミニマックス法で計算したか True
計算したノードの数 16168
枝狩りしたノードの数 533778
合計 549946
割合 2.9%
```

このことから、__〇× ゲームの場合__ は __置換表を使ってミニマックス法__ で __ルートノードの評価値を計算__ すると、__αβ 法と同程度の計算速度の向上が見込める__ ことがわかりました。

## Mbtree_Anim のクラスの `update_ab` メソッドの修正

上記で __置換表による枝狩りが行われた際__ に、__ノードの状態__ として __`"tt"` という文字列を記録する__ ようにしたので、それに合わせて __置換表による枝狩りが行われたことがわかるように Mbtree_Anim を修正する__ ことにします。具体的には置換表による枝狩りが行われて評価値が確定した場合は __背景色を薄緑色で表示__ し、__1 行目の説明文を赤色で「置換表による置換」と表示する__ ことにします。

下記はそのように __`update_ab`__ メソッドを修正したプログラムです。

* __8 行目__：そのフレームの状態が置換表による評価値の確定であるかどうかを判定する
* __9、10 行目__：1 行目の説明文を「置換表による置換」にし、文字の色を赤色にする
* __11 行目__：背景色を薄緑色に設定する

```python
 1  from tree import Mbtree_Anim
 2  import matplotlib.patches as patches
 3  
 4  def update_ab(self):
元と同じなので省略
 5      if status == "start":
 6          facecolor = "white"
 7          nodetype += " 処理の開始"
元と同じなので省略
 8      elif status == "tt":
 9          textlist[0] = "置換表による置換"
10          textcolorlist[0] = "red"
11          facecolor = "honeydew"
元と同じなので省略
12  
13  Mbtree_Anim.update_ab = update_ab
```

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

```python
from tree import Mbtree_Anim
import matplotlib.patches as patches

def update_ab(self):
    alpha, beta, score, status, num_calculated, num_pruned = self.mbtree.ablist_by_score[self.play.value]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    acolor = "red" if maxnode else "black"
    bcolor = "black" if maxnode else "red"
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3
    plus_inf = 4   
    alphacoord = max(minus_inf, alpha)
    betacoord = min(plus_inf, beta)
    
    color = "lightgray" if maxnode else "aqua"
    rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf,
                            height=1, fc=color)
    self.abax.add_patch(rect)
    rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord,
                            height=1, fc="yellow")
    self.abax.add_patch(rect)
    color = "aqua" if maxnode else "lightgray"
    rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
                            height=1, fc=color)
    self.abax.add_patch(rect)

    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")
        
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
                    arrowprops=arrowprops, ha="center", c=acolor)
    self.abax.plot(betacoord, 0, "ob")
    self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
                    arrowprops=arrowprops, ha="center", c=bcolor)
    if score is not None:
        self.abax.plot(score, 0, "og")
        self.abax.annotate(f"score = {score}", xy=(score, 0),
                        xytext=((minus_inf + plus_inf) / 2, 1), 
                        arrowprops=arrowprops, ha="center")
            
    facecolorlist = ["aqua", "yellow", "lightgray"]
    textcolorlist = ["black", "black", "black"]
    if maxnode:
        nodetype = f"深さ {self.selectednode.mb.move_count} max node"
        textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)", "α 値の更新なし (score ≦ α)"]
        if score is not None:
            if beta <= score:
                textcolorlist[0] = "red"
            elif alpha < score:
                textcolorlist[1] = "red"
            else:
                textcolorlist[2] = "red"
    else:
        nodetype = f"深さ {self.selectednode.mb.move_count} min node"
        textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)", "β 値の更新なし (score ≦ β)"]
        if score is not None :
            if score <= alpha:
                textcolorlist[0] = "red"
            elif score < beta:
                textcolorlist[1] = "red"
            else:
                textcolorlist[2] = "red"
            
    if status == "start":
        facecolor = "white"
        nodetype += " 処理の開始"
    elif status == "score":
        facecolor = "lightyellow"
        nodetype += " 子ノードの評価値"
    elif status == "update":
        facecolor = "lightcyan"
        if maxnode:
            nodetype += " α 値の処理"
        else:
            nodetype += " β 値の処理"
    elif status == "tt":
        textlist[0] = "置換表による置換"
        textcolorlist[0] = "red"
        facecolor = "honeydew"
    else:
        facecolor = "lavenderblush"
        nodetype += " 評価値の確定"
    self.abfig.set_facecolor(facecolor)
    self.abax.text(6, 1, nodetype)   
    for i in range(3):
        rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5, fc=facecolorlist[i])
        self.abax.add_patch(rect)
        self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
    
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total if num_total != 0 else 0
    _, _, _, _, prev_num_calculated, prev_num_pruned = self.mbtree.ablist_by_score[self.prev_frame]
    prev_num_total = prev_num_calculated + prev_num_pruned
    diff_num_calculated = num_calculated - prev_num_calculated
    diff_num_pruned = num_pruned - prev_num_pruned
    diff_num_total = num_total - prev_num_total
    diff_num_ratio = diff_num_calculated / diff_num_total if diff_num_total != 0 else 0

    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
    diff_datalist = [ f"{diff_num_calculated:+d}", f"{diff_num_pruned:+d}", 
                    f"{diff_num_total:+d}", f"{diff_num_ratio * 100:.1f}%"]
    for i in range(4):
        self.abax.text(15, 1 - i * 0.7, textlist[i])
        self.abax.text(19.5, 1 - i * 0.7, datalist[i], ha="right")
        self.abax.text(22.5, 1 - i * 0.7, diff_datalist[i], ha="right")

Mbtree_Anim.update_ab = update_ab
```
</details>

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

```diff_python
from tree import Mbtree_Anim
import matplotlib.patches as patches

def update_ab(self):
元と同じなので省略
    if status == "start":
        facecolor = "white"
        nodetype += " 処理の開始"
元と同じなので省略
+   elif status == "tt":
+       textlist[0] = "置換表による置換"
+       textcolorlist[0] = "red"
+       facecolor = "honeydew"
元と同じなので省略

Mbtree_Anim.update_ab = update_ab
```
</details>

上記の修正後に下記のプログラムを実行し、__(0, 0)、(1, 0)、(2, 0)__ の順で着手が行われた局面の __評価値が計算された__ 1676 フレーム目を表示すると、実行結果のように __赤枠のノードの子ノードが明るく表示される__ ので、赤枠の局面の __子ノードの評価値がすべて計算された__ ことが確認できます。

```python
Mbtree_Anim(mbtree, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ec20192a-32f6-2098-7d28-20d3979dd749.png" width="500">

次に、その後のフレームで __同じ局面になる (2, 0)、(1, 0)、(0, 0)__ の順で着手が行われた局面の __評価値が計算された__ 32690 フレーム目を表示すると実行結果のような図が表示されます。

なお、下図では __枝狩りが行われた数がわかる__ ように、直前の 32689 フレーム目を表示した後で上段の > をクリックして 32690 フレーム目を表示した場合の図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a166d0af-f26d-fc32-de91-30d72688e97d.png" width="500">

上図は __以下のように表示される__ ことから、__置換表によって評価値が計算され__、その __子孫ノードが枝狩りされたことがわかる__ ように表示されています。また、枝狩りの右に __+1348__ と表示されるので __置換表による枝狩り__ によって __1348 個のノードの枝狩りが行われた__ ことがわかります。興味がある方は、他の置換表に登録されたノードでも同様の表示が行われることを確認してみて下さい。

* __背景色が薄緑色で表示__ される
* 数直線の右に __赤字で「置換表による置換」と表示__ される
* 赤枠の __全ての子孫ノード__ が枝狩りが行われたことを表す __さらに暗い色で表示__ される

筆者も最初は気が付かなかったのですが、__上図には一つ大きな問題__ があります。どのような問題があるかについて少し考えてみて下さい。

## 問題の検証

__置換表によって評価値が計算されるノード__ は、他のノードが `"start"` の状態のフレームから始まり、`"end"` の状態のフレームで終わるのと異なり、__`"tt"` 状態のフレームしか存在しません__。そのため、下段の <<、<、>、>> による __選択中のノード内の移動の操作を行うことはできません__ が、それにも関わらず上図ではそれらの __4 つのボタンが緑色で表示__ されて __クリックできる__ ようになっています。

また、4 つのボタンをクリックした際に[行われる処理](https://qiita.com/ysgeso/items/741c2c18f0bc6fcdba27#%E3%83%95%E3%83%AC%E3%83%BC%E3%83%A0%E3%82%92%E6%8E%A2%E3%81%97%E3%81%A6%E7%A7%BB%E5%8B%95%E3%81%99%E3%82%8B%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)は、__このノードの `"start"` や `"end"` などの状態のフレームを探す__ という処理ですが、__そのような状態のフレームが存在しない__ ので __いずれは list の範囲外のインデックスの要素を参照__ しようとするため __エラーが発生__ します。下記は 32690 フレーム目で下段の << ボタンをクリックした際に表示されるエラーメッセージで、実際に __list の範囲外（out of range）のインデックスを参照した__ という意味のメッセージが表示されています。この問題を修正する方法について少し考えてみて下さい。

```
略
File c:\Users\ys\ai\marubatsu\151\tree.py:1244, in Mbtree_Anim.create_event_handler.<locals>.change_frame(edge_status, diff, status_list)
   1242 while True:
   1243     frame += diff
-> 1244     node = self.mbtree.nodelist_by_score[frame]
   1245     status = self.mbtree.ablist_by_score[frame][3]
   1246     if node == selectednode and status in status_list:

IndexError: list index out of range
```

## Mbtree_Anim のクラスの `update_gui` メソッドの修正

この問題は __フレームの状態が `"tt"` の場合__ に __下段の 4 つのボタンをクリックできないようにする__ ことで修正できます。__ボタンの状態の設定__ は __`update_gui`__ メソッド内で行っているので下記のプログラムのように `update_gui` メソッドを修正します。

* __5、8 行目__：4 つのボタンが操作できないようするに条件に「フレームの状態が `"tt"` である」という条件を追加する

```python
 1  def update_gui(self):
元と同じなので省略
 2      if self.abfig is not None:
 3          self.update_ab()
 4          status = self.mbtree.ablist_by_score[self.play.value][3]
 5          disabled = status == "start" or status == "tt"
 6          self.set_button_status(self.node_first_button, disabled=disabled)
 7          self.set_button_status(self.node_prev_button, disabled=disabled)
 8          disabled = status == "end" or status == "tt"
 9          self.set_button_status(self.node_next_button, disabled=disabled)
10          self.set_button_status(self.node_last_button, disabled=disabled)
元と同じなので省略
11      
12  Mbtree_Anim.update_gui = update_gui
```
<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(-1, self.height - 1)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    self.selectednode = self.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.mbtree.algo == "bf":
        if self.centernode.depth > 0:
            self.centernode = self.centernode.parent
    while self.centernode.depth > 6:
        self.centernode = self.centernode.parent
    if self.centernode.depth <= 4:
        maxdepth = self.centernode.depth + 1
    elif self.centernode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode,
                             anim_frame=self.play.value, isscore=self.isscore, 
                             ax=self.ax, maxdepth=maxdepth, size=self.size)
    if self.abfig is not None:
        self.update_ab()
        status = self.mbtree.ablist_by_score[self.play.value][3]
        disabled = status == "start" or status == "tt"
        self.set_button_status(self.node_first_button, disabled=disabled)
        self.set_button_status(self.node_prev_button, disabled=disabled)
        disabled = status == "end" or status == "tt"
        self.set_button_status(self.node_next_button, disabled=disabled)
        self.set_button_status(self.node_last_button, disabled=disabled)

    disabled = self.play.value == 0
    self.set_button_status(self.prev_button, disabled=disabled)
    disabled = self.play.value == self.nodenum - 1
    self.set_button_status(self.next_button, disabled=disabled)
    
Mbtree_Anim.update_gui = update_gui
```
</details>

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

```diff_python
def update_gui(self):
元と同じなので省略
    if self.abfig is not None:
        self.update_ab()
        status = self.mbtree.ablist_by_score[self.play.value][3]
-       disabled = status == "start"
+       disabled = status == "start" or status == "tt"
        self.set_button_status(self.node_first_button, disabled=disabled)   
        self.set_button_status(self.node_prev_button, disabled=disabled)
-       disabled = status == "end"
+       disabled = status == "end" or status == "tt"
        self.set_button_status(self.node_next_button, disabled=disabled)                       
        self.set_button_status(self.node_last_button, disabled=disabled)
元と同じなので省略
    
Mbtree_Anim.update_gui = update_gui
```
</details>

上記の修正後に下記のプログラムを実行して 32690 フレーム目を表示すると、実行結果のように __下段の 4 つのボタンが灰色で表示されて操作できなくなった__ ことが確認できます。

```python
Mbtree_Anim(mbtree, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/878fe33f-98fd-1aff-1f53-c35989671923.png" width="500">

## 同一局面を考慮した置換表による枝狩り

[以前の記事](https://qiita.com/ysgeso/items/e78980b366e123ca57f1#%E5%90%8C%E4%B8%80%E5%B1%80%E9%9D%A2%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8%E6%89%B1%E3%81%84)で、〇×ゲームには回転による同一局面と、線対称な __同一局面が存在する__ ことを説明しました。__〇× ゲームの性質__ から __同一局面の評価値は同じになる__ ので、評価値が計算されたノードの情報を __置換表に登録する際__ に、__同一局面に対しても同じ評価値を置換表に登録する__ ことで、__より多くの枝狩り__ を行うことが出来るようになります。

__同一局面の計算__ は、[以前の記事](https://qiita.com/ysgeso/items/7cb0c709f6d5884d925e#%E5%85%A8%E3%81%A6%E3%81%AE%E5%90%8C%E4%B8%80%E5%B1%80%E9%9D%A2%E3%82%92%E8%A1%A8%E3%81%99%E6%96%87%E5%AD%97%E5%88%97%E3%81%AE%E8%A8%88%E7%AE%97)で定義した __`calc_same_boardtexts`__ で行うことができるので、下記のプログラムのように __`calc_score_by_ab`__ を修正します。

* __2 ~ 7 行目__：`calc_same_boardtexts` を使って、__ノードの同一局面の文字列の list を計算__ し、__全ての同一局面の評価値を置換表に登録する__ ように修正する。[循環参照を避けるため](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)に、3 行目の `calc_same_boardtext` のインポートは `calc_score_by_ab` の中に記述した

```python
 1  def calc_score_by_ab(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False):
元と同じなので省略
 2          if use_tt:
 3              from util import calc_same_boardtexts
 4
 5              boardtxtlist = calc_same_boardtexts(node.mb)
 6              for boardtxt in boardtxtlist:
 7                  tt[boardtxt] = node.score
 8          return node.score
元と同じなので省略
 9      
10  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()
            if boardtxt in tt:
                node.score = tt[boardtxt]
                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)
            for boardtxt in boardtxtlist:
                tt[boardtxt] = 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):
元と同じなので省略
        if use_tt:
+           from util import calc_same_boardtexts

-           tt[boardtxt] = node.score           
+           boardtxtlist = calc_same_boardtexts(node.mb)
+           for boardtxt in boardtxtlist:
+               tt[boardtxt] = node.score
        return node.score
元と同じなので省略
    
Mbtree.calc_score_by_ab = calc_score_by_ab
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように[前回の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-move_bestmove_to_head-%E3%81%AE%E5%AE%9A%E7%BE%A9) __で最善手を着手した子ノードを最初に計算した場合の αβ 法__ の計算したノードの数と割合である 2312、0.4 % と __ほぼ同じ効率で枝狩りを行える__ ことが確認できました。

```python
mbtree.calc_score_by_ab(mbtree.root, use_tt=True, minimax=True, debug=True)
```

実行結果

```
ミニマックス法で計算したか True
計算したノードの数 2271
枝狩りしたノードの数 547675
合計 549946
割合 0.4%
```

また、下記のプログラムを実行し、__(0, 0) だけに着手__ した局面の __同一局面__ である __(2, 0) だけに着手__ した局面のノードが計算された 7485 フレーム目を表示すると、実行結果のように薄緑色で表示され、赤枠の子ノードがすべて暗い色で表示されるため、__置換表による置換が行われた__ ことが確認できます。また、直前の 7484 フレーム目を表示した後で上段の > をクリックして 7485 フレーム目を表示すると、下図のように __59704 個の枝狩りを行われた__ ことが確認できます。

```python
Mbtree_Anim(mbtree, isscore=True)
```

実行結果
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/cc087797-6126-7ec7-469f-4bcef60f0971.png" width="500">

## 置換表を利用した AI の定義と確認

__置換表を利用したミニマックス法__ によって __強解決の AI を作成できるか__ どうかを __確認するため__ に、__`ai_mmdfs_tt` という名前の AI を定義__ する事にします。この関数は、以前に作成した __ミニマックス法で計算した評価値を使って着手を選択する AI__ である __[`ai_mmdfs`](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#ai-%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE-ai_mmdfs-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ を下記のプログラムのように __修正して定義__ します。また、その際に __最短の勝利を考慮した評価値で計算できる__ ように __`shortest_victory` という仮引数を追加__ することにします。

* __5 行目__：デフォルト値を `False` とする仮引数 `shortest_victory` を追加する
* __7 行目__：ゲーム盤の評価値を計算するローカル関数 `mm_search` に、置換表を代入する仮引数 `tt` を追加する
* __11 ~ 16 行目__：決着がついた局面の評価値を `shortest_victory` の値を考慮して計算する。なお、この部分で計算した評価値を置換表に登録してもかまわないが、__この計算はすぐに行うことができる__ ので置換表に登録しても __処理の効率が向上しない__ 点と、__プログラムの記述が少しだけ長くなる__ 点を考慮して __置換表には登録しないことにした__。置換表に登録したい方はそのように実装してもかまわないが、その場合は 18 ~ 20 行目の処理をこの処理の前に記述する必要がある点に注意すること
* __18 ~ 20 行目__：局面を表す文字列を計算し、置換表に登録されている場合はその評価値を返すように修正する
* __27 行目__：`mm_search` を再帰呼び出しする際に実引数 `tt` を記述するように修正する
* __28 ~ 35 行目__：元のプログラムでは子ノードの評価値の最大値または最小値を計算して返り値として返していたが、__評価値を同一局面の置換表に登録する必要がある__ ので `score` という変数に評価値を代入し、__32 ~ 34 行目で同一局面の評価値を置換表に登録__ した後で __35 行目で返り値として返す__ ように修正する[^3]
* __37 行目__：最初に `mm_search` を呼び出す際に、__置換表として空の dict を実引数に記述する__ ように修正する

```python
 1  from ai import ai_by_score, dprint
 2  from copy import deepcopy
 3  
 4  @ai_by_score
 5  def ai_mmdfs_tt(mb, debug=False, shortest_victory=False):
 6      count = 0
 7      def mm_search(mborig, tt):
 8          nonlocal count
 9          count += 1
10  
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          score_list = []
24          for x, y in legal_moves:
25              mb = deepcopy(mborig)
26              mb.move(x, y)
27              score_list.append(mm_search(mb, tt))
28          if mborig.turn == Marubatsu.CIRCLE:
29              score = max(score_list)
30          else:
31              score = min(score_list)
32      boardtxtlist = calc_same_boardtexts(mborig)
33      for boardtxt in boardtxtlist:
34          tt[boardtxt] = score
35      return score
36      
37      score = mm_search(mb, {})
38      dprint(debug, "count =", count)
39      if mb.turn == Marubatsu.CIRCLE:
40          score *= -1
41      return score
```

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

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

@ai_by_score
def ai_mmdfs_tt(mb, debug=False, shortest_victory=False):
    count = 0
    def mm_search(mborig, tt):
        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()
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(mborig)
            mb.move(x, y)
            score_list.append(mm_search(mb, tt))
        if mborig.turn == Marubatsu.CIRCLE:
            score = max(score_list)
        else:
            score = min(score_list)
        boardtxtlist = calc_same_boardtexts(mborig)
        for boardtxt in boardtxtlist:
            tt[boardtxt] = score
        return score
    
    score = mm_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 copy import deepcopy

@ai_by_score
-def ai_mmdfs(mb, debug=False):
+def ai_mmdfs_tt(mb, debug=False, shortest_victory=False):
    count = 0
-   def mm_search(mborig):
+   def mm_search(mborig, tt):
        nonlocal count
        count += 1

        if mborig.status == Marubatsu.CIRCLE:
-           return 1
+           return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
-           return -1
+           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()
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(mborig)
            mb.move(x, y)
-           score_list.append(mm_search(mb))
+           score_list.append(mm_search(mb, tt))
        if mborig.turn == Marubatsu.CIRCLE:
-           return max(score_list)        
+           score = max(score_list)
        else:
-           return min(score_list)
+           score = min(score_list)
+       boardtxtlist = calc_same_boardtexts(mborig)
+       for boardtxt in boardtxtlist:
+           tt[boardtxt] = score
+       return score
    
-   score = mm_search(mb)
+   score = mm_search(mb, {})
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

上記の定義後に 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 であることが確認できました__。

```python
from util import Check_solved

Check_solved.is_strongly_solved(ai_mmdfs_tt)
Check_solved.is_strongly_solved(ai_mmdfs_tt, params={"shortest_victory": True})
```

実行結果

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

このことから、__置換表を利用したミニマックス法で正しい計算を行うことが出来る__ ことが確認できました。

## 置換表の効率

上記で __〇× ゲーム__ の __ルートノードの評価値__ を、__置換表を使ったミニマックス法で計算__ すると __αβ 法より高い効率で枝狩りを行うことが出来る__ ことが確認できたので、置換表を利用したミニマックス法の効率が αβ 法の効率より高いと __思った方がいるかもしれません__ が、__常にそのようになるわけではありません__。

__置換表__ は __同一局面の子孫ノードの枝狩りを行う__ という手法なので、__評価値を計算するノード__ をルートノードとする __部分木の中__ に、__同一局面が多く存在しない場合__ は __多くの枝狩りを行うことはできません__。

__〇×ゲーム__ は、全体的にみると __着手が少ない程同一局面の数が多くなる__ という性質があります。例えば、__1 手目の局面__ には __9 種類の局面__ がありますが、その中で __隅への着手__ が行われた __4 つの局面は同一局面__ です。同様に、__辺への着手__ が行われた __4 つの局面は同一局面__ です。従って、ゲーム開始時の __ルートノードの評価値を計算する際__ に、その子ノードである __深さ 1 の 9 個の子ノード__ のうち __3 + 3 = 6 つのノード__ で __置換表による枝狩りを行うことが出来ます__。そのため、__ルートノードの評価値__ を計算する際に、先程の実行結果のように __非常に多くの割合の枝狩りを行うことができます__。

一方、__〇× ゲーム__ では __着手を行えば行うほど__、__子孫ノードの中の同一局面の割合が減る__ という傾向があるので、__深いノードの評価値を計算__ する際の __置換表による枝狩りの効率は落ちていく__ ことになります。

そのことを確認するために、下記のプログラムで __深さ 0 ~ 8 の最初のノード__ に対して、__置換表を利用したミニマックス法で評価値の計算__ を行ってみることにします。

```python
for depth in range(9):
    print("depth", depth)
    mbtree.calc_score_by_ab(mbtree.nodelist_by_depth[depth][0], minimax=True, use_tt=True, debug=True)
```

実行結果

```
depth 0
ミニマックス法で計算したか True
計算したノードの数 2271
枝狩りしたノードの数 547675
合計 549946
割合 0.4%
depth 1
ミニマックス法で計算したか True
計算したノードの数 1820
枝狩りしたノードの数 57885
合計 59705
割合 3.0%
depth 2
ミニマックス法で計算したか True
計算したノードの数 1056
枝狩りしたノードの数 7176
合計 8232
割合 12.8%
depth 3
ミニマックス法で計算したか True
計算したノードの数 250
枝狩りしたノードの数 1099
合計 1349
割合 18.5%
depth 4
ミニマックス法で計算したか True
計算したノードの数 124
枝狩りしたノードの数 110
合計 234
割合 53.0%
depth 5
ミニマックス法で計算したか True
計算したノードの数 34
枝狩りしたノードの数 7
合計 41
割合 82.9%
depth 6
ミニマックス法で計算したか True
計算したノードの数 7
枝狩りしたノードの数 1
合計 8
割合 87.5%
depth 7
ミニマックス法で計算したか True
計算したノードの数 1
枝狩りしたノードの数 0
合計 1
割合 100.0%
depth 8
ミニマックス法で計算したか True
計算したノードの数 2
枝狩りしたノードの数 0
合計 2
割合 100.0%
```

次に下記のプログラムで __深さ 0 ~ 8 の最初のノード__ に対して、__αβ 法で評価値の計算__ を行ってみることにします。なお、置換表は利用しないので `use_tt=True` は記述しません。

```python
for depth in range(9):
    print("depth", depth)
    mbtree.calc_score_by_ab(mbtree.nodelist_by_depth[depth][0], debug=True)
```

実行結果

```
depth 0
ミニマックス法で計算したか False
計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%
depth 1
ミニマックス法で計算したか False
計算したノードの数 2338
枝狩りしたノードの数 57367
合計 59705
割合 3.9%
depth 2
ミニマックス法で計算したか False
計算したノードの数 749
枝狩りしたノードの数 7483
合計 8232
割合 9.1%
depth 3
ミニマックス法で計算したか False
計算したノードの数 336
枝狩りしたノードの数 1013
合計 1349
割合 24.9%
depth 4
ミニマックス法で計算したか False
計算したノードの数 65
枝狩りしたノードの数 169
合計 234
割合 27.8%
depth 5
ミニマックス法で計算したか False
計算したノードの数 32
枝狩りしたノードの数 9
合計 41
割合 78.0%
depth 6
ミニマックス法で計算したか False
計算したノードの数 6
枝狩りしたノードの数 2
合計 8
割合 75.0%
depth 7
ミニマックス法で計算したか False
計算したノードの数 1
枝狩りしたノードの数 0
合計 1
割合 100.0%
depth 8
ミニマックス法で計算したか False
計算したノードの数 2
枝狩りしたノードの数 0
合計 2
割合 100.0%
```

下記は上記の結果を表にしたものです。__左に置換表を利用したミニマックス法のデータを__ 表記し、__αβ 法の結果__ は比較のために __割合のみを右端の列に表記__ します。

表から評価値を利用したミニマックス法では __深さが深くなるほど割合が大きく増えていく__ ことから、__枝狩りの効率が大きく減る__ ことが確認できます。ただし、__深さが深い程部分木のノードの数が急激に減る__ ため、__割合が増えても計算したノードの数は減少する__ ことも確認できました。

αβ 法も同様の傾向はありますが、深さが 0 の場合は割合が高い、深さが 1、5 ~ 8 の場合はほぼ同じ、深さが 2 ~ 4 の場合は割合が低くなっているので、__どちらがより枝狩りを効率よく行えるかは一概には言えない__ ことが確認できました。

| 深さ | 計算したノードの数 | 合計 | 割合 | αβ 法の割合 | 
|:-:|--:|--:|--:|--:|
| __0__  | 2271 | 549946  | 0.4 % | 3.3 % |
| __1__  | 1820 | 59705  | 3.0 % | 3.9 % |
| __2__  | 1056 |  8232 | 12.8 % | 9.1 % |
| __3__  | 250  | 1349 | 18.5 % | 24.9 % |
| __4__  | 124  | 234 | 53.0 % | 27.8 % |
| __5__  | 34  | 41 | 82.9 % | 78.0 %| 
| __6__  | 7  | 8 | 87.5 % | 75.0 % |
| __7__  | 1  | 1 | 100.0 % | 100.0 % |
| __8__  |  2 | 2 | 100.0 %  | 100.0 % |

なお、__置換表を利用したミニマックス法の効率__ は __ゲームによって大きく性質が異なります__。例えば、〇× ゲーム、オセロ、囲碁のような、__着手を行うたびにゲーム盤が埋まっていく__ ようなゲームの場合は、手数が増えると子孫ノードの同一局面の割合が減って __置換表の効率が落ちていきます__ が、将棋やチェスのような __盤面上のコマを移動する__ ようなゲームの場合は、__手数が増えても子孫ノードの同一局面の割合は大きく減らない__ ので __手数と置換表の効率には大きな関係はない__ という性質があります。

このように __置換表による枝狩りの効率__ は __局面によってばらつきがあります__ が、ほとんどの場合は置換表を利用したほうが効率が上がるので __一般的には利用したほうが良いでしょう__。

# 今回の記事のまとめ

今回の記事では、αβ 法で α 値と β 値の初期値を評価値の最小値と最大値に設定することで枝狩りの効率を少しだけ上げることが出来ることを示しました。

また、ミニマックス法で置換表を利用した枝狩りを行う方法について紹介しました。

ところで、今回修正した __`calc_score_by_ab`__ を利用して下記のプログラムのように __置換表を利用した αβ 法の計算を行える__ と思った人はいないでしょうか？下記のプログラムの実行結果から __割合が 0.2 %__ と置換表を利用しない αβ 法の場合の 3.3 % から __大きく減っている__ のでうまく計算が出来ているように思えるかもしれませんが、実際には今回修正した `calc_score_by_ab` では置換表を利用して __αβ 法の計算を正しく行うことはできません__。その理由については次回の記事で説明しますが、余裕がある方は考えてみて下さい。


```python
mbtree.calc_score_by_ab(mbtree.root, use_tt=True, debug=True)
```

実行結果

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

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

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

# 次回の記事

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

[^1]:本記事ではそのような修正は行いませんが、この修正によって `calc_ab_score` を呼び出す際に必ず実引数に α 値と β 値が記述されるようになるので、`calc_ab_score` の仮引数 `alpha` と `beta` を通常の仮引数に変更することができます
[^2]:長くなるので本記事では説明しません。興味がある方は調べてみて下さい
[^3]:ai.py に `ai_mmdfs_tt` の定義を記述する際には、循環参照を避けるために `from util import calc_same_boardtexts` を `ai_mmdfs_tt` の定義の中に記述する必要があります