Pythonで〇×ゲームのAIを一から作成する　その169　αβ 法との比較による MTD(f) 法の効率の検証

# 目次と前回の記事

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

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

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

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

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

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

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

# αβ 法との比較による MTD(f) 法と 効率の検証

今回の記事では、前回の記事で実装した __MTD(f) 法の効率__ を __αβ 法と比較__ することで検証します。スカウト法との比較は次回の記事で行います。最初に[以前の記事](https://qiita.com/ysgeso/items/70f58152e629be63390d#%E3%82%B9%E3%82%AB%E3%82%A6%E3%83%88%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E7%A2%BA%E8%AA%8D)で行った下記の方法で、__αβ 法と MTD(f) 法の効率を比較__ することにします。

* 同一局面を除いた 〇×ゲームのすべての局面に対して、同一の設定で αβ 法と MTD(f) 法で計算を行う
* それぞれの場合で、計算されたノードの数の合計を比較することで処理の効率を比較する

なお、以前の記事では move ordering に関する比較を行っていましたが、__[MTD(f) 法を紹介した論文](https://arxiv.org/abs/1404.1511)では move ordering を行なっていない__ ので、αβ 法との比較では move ordering を行なわないことにします。また、[前回の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#mtdf-%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)で説明したように、MTD(f) 法では局面の __ミニマックス値の推定値の精度が高い程効率が高くなる__ ことが期待できますが、__move ordering を行なわない αβ 法と比較することを考慮__ して今回の比較ではあえて精度が高くない、__すべての局面のミニマックス値を 0 と推定した場合の比較__ を行うことにしました。

ミニマックス値の推定値の精度を高くした場合の MTD(f) 法の検証は、次回の記事で move ordering を行うスカウト法との比較の際に行うことにします。

:::note
最短の勝利を考慮しない場合の評価値は -1、0、1 のいずれかなので、ミニマックス値として 0 を推定した場合の誤差は最大でも ± 1 しかありません。従ってその場合の精度は実はかなり高いと言えると思います。
:::

下記はその比較を行うプログラムです。なお、実は __下記のプログラムの検証には問題がある__ ことが __検証を行った後で判明__ しました。__問題の発見と修正の経緯が参考になるのではないか__ と思いましたので、__あえて問題があるまま検証を進める__ ことにします。

```python
from ai import ai_abs_all, ai_mtdf
from util import load_mblist

mblist = load_mblist("../data/mblist_by_board_min.dat")
for shortest_victory in [False, True]:
    for use_tt in [False, True]:
        for init_ab in [False, True]:
            print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
            count = 0
            count2 = 0
            for mb in mblist:
                count += ai_abs_all(mb, shortest_victory=shortest_victory,
                                    init_ab=init_ab, use_tt=use_tt,
                                    calc_score=True, calc_count=True)
                count2 += ai_mtdf(mb, shortest_victory=shortest_victory,
                                    init_ab=init_ab, use_tt=use_tt,
                                    calc_score=True, calc_count=True)
            print("abs count=", count)
            print("mtdf count=", count2)
```

実行結果

```
sv: False, init_ab: False, use_tt: False
abs count= 32020
mtdf count= 35728
sv: False, init_ab: True, use_tt: False
abs count= 23850
mtdf count= 28803
sv: False, init_ab: False, use_tt: True
abs count= 17582
mtdf count= 14362
sv: False, init_ab: True, use_tt: True
abs count= 12576
mtdf count= 14042
sv: True, init_ab: False, use_tt: False
abs count= 36423
mtdf count= 39740
sv: True, init_ab: True, use_tt: False
abs count= 33947
mtdf count= 37643
sv: True, init_ab: False, use_tt: True
abs count= 19459
mtdf count= 18546
sv: True, init_ab: True, use_tt: True
abs count= 18191
mtdf count= 18447
```

下記は実行結果をまとめた表です。一番上の行の ab は init_ab、tt は use_tt の値で 〇 は True、× は False を表します。各セルの __上段が `ai_abs_all`__、__下段が `ai_mtdf`__ の結果です。

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __最短の勝利を目指さない場合__ | 32020<br>35728 | 23850<br>28803 | 17582<br>14362 | 12576<br>14042 | 
| __最短の勝利を目指さす場合__ | 36423<br>39740| 33947<br>37643 | 19459<br>18546 | 18191<br>18447 |

実行結果から、`init_ab=False`、`use_tt=True` の場合のみ MTD(f) 法のほうが効率が良くなることが確認できました。

__MTD(f) 法は置換表の利用を前提__ とするアルゴリズムです。その理由を説明するために、__置換表を利用する場合と利用しない場合にわけて検証を行う__ ことに会います。

# 置換表を利用しない場合の検証

上記の結果では、__置換表を利用しない場合__ はいずれも __αβ 法よりも効率が悪くなります__。その理由についていくつかの考察と検証を行います。

## 枝狩りの効率とゲーム木の深さの関係の考察

[前回の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#mtdf-%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)で説明したように、MTD(f) 法は、__null window search の効率の高さを利用__ することで、__複数回（2 回以上）の null window search__ の計算のほうが、αβ 法による __広いウィンドウでの 1 回の αβ 値の計算よりも効率が高くなる__ ことを期待するという手法です。そのため、__置換表を利用しない場合__ は、__null window search__ による __枝狩りの効率が高いことが非常に重要__ となります。

null window search に限らず、下記のような理由から αβ 値を計算する場合はその __子孫ノードの部分木__ の __深さが浅い場合__ は一般的に __枝狩りの効率が低くなります__。

* __枝狩り__ は、枝狩りを行ったノードの __すべての子孫ノードの処理を省略する__ ので、__子孫ノードの数が多い程__ 枝狩りの __効率が良くなる__
* リーフノードを除くゲーム木のほとんどのノードには複数の子ノードが存在するので、__ゲーム木のノードの数__ は __深さが増えるごとに爆発的に増えていく__。このような毎回数倍に増えていくような増え方を __指数関数的に増えていく__ と呼ぶ[^1]
* 従って、子孫ノードの部分木の __深さが浅いほど__ 一般的に __枝狩りの効率が低くなる__

__〇× ゲーム__ のゲーム木の __各深さの具体的なノードの数__ は[以前の記事](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E6%AD%A3%E3%81%97%E3%81%84%E5%90%84%E6%B7%B1%E3%81%95%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%95%B0%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)で __下記のように計算済__ です。下記からノードの総数は 549946 で、深さが 7 以上のノードの数は 148176 + 200448 + 127872 = 476496 です。476496 ÷ 549946 = 約 0.866 なので、__85 % 以上のほとんどのノードが深さ 7 以上のノード__ であることが確認できます。

〇× ゲームのゲーム木の深さは 9 なので、深さが $n$ のノードをルートノードとする部分木の深さは $9 - n$ 以下になります。従って、〇× ゲームの __ほとんどのノードをルートノードとする部分木の深さ__ は __2 以下__ と、__実際にかなり浅い__ ことが確認できました。

```
     9 depth 1 node created
    72 depth 2 node created
   504 depth 3 node created
  3024 depth 4 node created
 15120 depth 5 node created
 54720 depth 6 node created
148176 depth 7 node created
200448 depth 8 node created
127872 depth 9 node created
     0 depth 10 node created
total node num = 549946
```

このことから、先程行った検証では、__ほとんどのノードでの null window search の効率が低く__ なるため、すべてのノードの __合計を比較した場合__ に __MTD(f) 法のほうが__ αβ 法よりも __効率が低くなった__ ことが推測されます。

なお、__mblist_by_board_min.dat__ は __同一局面を削除__ しているので、__先程の検証で上記と同じ数のノードが計算されるわけではありません__。それぞれの深さでいくつの局面を計算しているかについてはこの後で示すことにします。

## 〇× ゲームのゲーム木特有の性質の考察

他の理由としては、__〇× ゲーム特有の性質__ として、〇× ゲームの合法手は開いているマスの数に等しいので __局面のノードの深さが深い程、子ノードの数が減る__ というものがあります。__αβ 法__ では __枝狩りは 2 番目以降の子ノード__ に対して行なわれるので、__子ノードの数が多いほうが枝狩りが行なわれやすくなる__ という性質があります。そのため 〇× ゲームのゲーム木のように、深さが __深い程子ノードの数が減るようなゲーム木__ では、ノードが __深い程枝狩りの効率が悪くなります__。

実際に __〇× ゲームの場合__ は下記の理由から __深さが 8 のノード__ のミニマックス値を計算すると、__MTD(f) 法の方__ が αβ 法よりも __必ず効率が悪くなります__。

* __深さが 8__ のノードの __αβ　値を計算する際__ は、下記の理由から __ウィンドウの範囲に関わらず枝狩りは行なわれない__
    * __深さが 8 のノード__ の __子ノードの数は 1 つ__ である
    * __深さが 9 のノード__ は決着がついた __子ノードが存在しないリーフノード__ である
    * α 狩りや β 狩りは子ノードが 2 つ以上存在する場合に行なわれる
* 従って、__深さ 8__ のノードの αβ 値を計算する際には、__ウィンドウ幅に関わらず__ そのノードと子ノードの __2 つのノード__ の評価値の __計算が必ず行われる__
* __MTD(f) 法__ では必ず __2 回以上__ の null window search が行なわれるので、2 × 2 = __4 個以上__ のノードの計算が行われる
* __αβ 法__ では __1 回__ の αβ 値の計算を行うので __2 個__ のノードの計算が行なわれる

## ノードの深さごとの効率の差の確認

上記の考察が正しいことを検証するために、〇× ゲームの __ノードの深さごと__ に __αβ 法と MTD(f) 法の効率を比較__ することにします。

具体的には、先程のプログラムを下記のように修正して実行します。

* __5、6 行目__：__深さごとの回数を数える__ ことができるようにするために、回数を数える変数を __9 つの 0 を要素として持つ list__ で初期化するように修正した。list の __インデックスの番号__ が __ゲーム木の深さを表す__ ものとする
* __8、11 行目__：__ノードの深さは着手した回数に等しい__ ので、着手した回数を表す __`mb.move_count`__ のインデックスの要素を増やすように修正する
* __15、16 行目__：深さごとの αβ 法、MTD(f) 法、__両者の差__（difference）を表示するように修正する。diff の後に表示される両者の差は __負の値が表示された場合__ に __MTD(f) 法の方が効率が良い__ ことを表す。また、上下の数字の表示位置が揃うように[書式指定](https://qiita.com/ysgeso/items/bf42b7b578bc2d5da949#%E6%9B%B8%E5%BC%8F%E6%8C%87%E5%AE%9A) を利用して 5 桁で表示するようにした
* __17 行目__：深さごとの合計を表示するように修正する。合計は組み込み関数 `sum` を利用して計算した

```python
 1  for shortest_victory in [False, True]:
 2      for use_tt in [False, True]:
 3          for init_ab in [False, True]:
 4              print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
 5              count = [0] * 9
 6              count2 = [0] * 9
 7              for mb in mblist:
 8                  count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
 9                                                     init_ab=init_ab, use_tt=use_tt,
10                                                     calc_score=True, calc_count=True)
11                  count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
12                                                   init_ab=init_ab, use_tt=use_tt,
13                                                   calc_score=True, calc_count=True)
14
15              for depth in range(9):
16                  print(f"depth = {depth} abs = {count[depth]:5} mtdf = {count2[depth]:5} diff = {count2[depth] - count[depth]:5}")
17              print(f"total     abs = {sum(count):5} mtdf = {sum(count2):5} diff = {sum(count2) - sum(count):5}")
```

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

```python
for shortest_victory in [False, True]:
    for use_tt in [False, True]:
        for init_ab in [False, True]:
            print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
            count = [0] * 9
            count2 = [0] * 9
            for mb in mblist:
                count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
                count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
            for depth in range(9):
                print(f"depth = {depth} abs = {count[depth]:5} mtdf = {count2[depth]:5} diff = {count2[depth] - count[depth]:5}")
            print(f"total     abs = {sum(count):5} mtdf = {sum(count2):5} diff = {sum(count2) - sum(count):5}")
```
</details>

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

```diff_python
for shortest_victory in [False, True]:
    for use_tt in [False, True]:
        for init_ab in [False, True]:
            print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
-           count = 0
+           count = [0] * 9
-           count2 = 0
+           count2 = [0] * 9
            for mb in mblist:
-               count += ai_abs_all(mb, shortest_victory=shortest_victory,
+               count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
-               count2 += ai_mtdf(mb, shortest_victory=shortest_victory,
+               count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)

-           print("abs count=", count)
-           print("mtdf count=", count2)
+           for depth in range(9):
+               print(f"depth = {depth} abs = {count[depth]:5} mtdf = {count2[depth]:5} diff = {count2[depth] - count[depth]:5}")
+           print(f"total     abs = {sum(count):5} mtdf = {sum(count2):5} diff = {sum(count2) - sum(count):5}")
```
</details>

実行結果

```
sv: False, init_ab: False, use_tt: False
depth = 0 abs =     0 mtdf =     0 diff =     0
depth = 1 abs =  7523 mtdf =  7024 diff =  -499
depth = 2 abs =  5423 mtdf =  5636 diff =   213
depth = 3 abs =  8369 mtdf =  9188 diff =   819
depth = 4 abs =  6515 mtdf =  8109 diff =  1594
depth = 5 abs =  2715 mtdf =  3397 diff =   682
depth = 6 abs =  1193 mtdf =  1866 diff =   673
depth = 7 abs =   282 mtdf =   508 diff =   226
depth = 8 abs =     0 mtdf =     0 diff =     0
total     abs = 32020 mtdf = 35728 diff =  3708
略
```

実行結果を見ると __深さが 0 と 8 のノードが 1 つも計算されていない__ ことがわかります。これが先程言及した検証の __問題点__ です。何故このようなことが起きたかについて少し考えてみて下さい。

## 検証データの作成

上記のようなことがおきるのは、検証するためにファイルから読み込んだ __[mblist_by_board_min.dat](https://qiita.com/ysgeso/items/7cb0c709f6d5884d925e#%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E4%BF%9D%E5%AD%98%E3%81%A8-is_strongly_soved-%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%A8%E7%A2%BA%E8%AA%8D-1)__ というファイルにあります。このデータは、Check_solved で AI が __強解決の AI であるかを検証するために作成__ したデータですが、その際に強解決であるかどうかを __判定する必要がない__、__すべての合法手が最善手である局面を削除__ しています。

実際にゲーム開始時の __深さが 0 の局面__ は __すべての合法手が最善手__ です。また、__深さが 8 の局面__ は __子ノードが 1 つしか存在しない__ ので __すべての合法手が最善手__ です。従って、__それらの局面のデータ__ は mblist_by_board_min.dat には __含まれていません__。

そこで、__それらのデータを含むデータを作成__ し、__そのデータを使って検証し直す__ ことにします。下記のプログラムはそのデータを作成するプログラムで、[以前の記事](https://qiita.com/ysgeso/items/7cb0c709f6d5884d925e#%E5%90%8C%E4%B8%80%E5%B1%80%E9%9D%A2%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AB%E3%82%88%E3%82%8B%E5%BC%B7%E8%A7%A3%E6%B1%BA%E3%81%AE-ai-%E3%81%A7%E3%81%82%E3%82%8B%E3%81%8B%E3%81%A9%E3%81%86%E3%81%8B%E3%81%AE%E5%88%A4%E5%AE%9A)での mblist_by_board_min.dat のデータを作成するプログラムを修正したものです。下記では __mblist_by_board_min2.dat__ という名前のファイルに作成したデータを保存していますが、わかりづらいと思った方は別のもっとわかりやすい名前で保存してくさだい

* __6 行目__：ゲーム木のデータをファイルから読み込む
* __7、14 行目__：作成したデータをこの後ですぐに利用できるようにするために、`mblist_by_board` ではなく、`mblist` という名前の変数に計算したデータを記録するように修正した
* __13 行目__：ゲーム中のデータであればすべて登録するように条件式を修正する
* __15、16 行目__：作成したデータを mblist_by_board_min2.dat というファイルに保存する

```python
 1  import gzip, pickle
 2  from util import calc_same_boardtexts
 3  from tree import Mbtree
 4  from marubatsu import Marubatsu
 5
 6  mbtree = Mbtree.load("../data/aidata")
 7  registered_boards = set()
 8  mblist = []
 9  for node in mbtree.nodelist:
10      txt = node.mb.board_to_str()
11      if not txt in registered_boards:
12          registered_boards |= calc_same_boardtexts(node.mb)
13          if node.mb.status == Marubatsu.PLAYING:
14              mblist.append(node.mb)
15  with gzip.open("../data/mblist_by_board_min2.dat", "wb") as f:
16      pickle.dump(mblist, f)
```

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

```python
import gzip, pickle
from util import calc_same_boardtexts
from tree import Mbtree
from marubatsu import Marubatsu

mbtree = Mbtree.load("../data/aidata")
registered_boards = set()
mblist = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards |= calc_same_boardtexts(node.mb)
        if node.mb.status == Marubatsu.PLAYING:
            mblist.append(node.mb)
with gzip.open("../data/mblist_by_board_min2.dat", "wb") as f:
    pickle.dump(mblist, f)
```
</details>

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

```diff_python
import gzip, pickle
from util import calc_same_boardtexts
from tree import Mbtree
from marubatsu import Marubatsu

mbtree = Mbtree.load("../data/aidata")
registered_boards = set()
-mblist_by_board = []
+mblist = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards |= calc_same_boardtexts(node.mb)
        if node.mb.status == Marubatsu.PLAYING:
-           mblist_by_board.append(node.mb)
+           mblist.append(node.mb)
+with gzip.open("../data/mblist_by_board_min2.dat", "wb") as f:
+   pickle.dump(mblist, f)
```
</details>

:::note
[以前の記事](https://qiita.com/ysgeso/items/97c293d8876190849ec8#%E3%81%99%E3%81%B9%E3%81%A6%E3%81%AE%E5%B1%80%E9%9D%A2%E3%81%A7%E3%81%AE%E5%90%88%E8%A8%88%E3%81%A7%E3%81%AE%E6%AF%94%E8%BC%83) と [以前の記事](https://qiita.com/ysgeso/items/70f58152e629be63390d#%E3%82%B9%E3%82%AB%E3%82%A6%E3%83%88%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E7%A2%BA%E8%AA%8D) の検証では、今回の記事と同様に深さ 0 と 8 などのノードの計算を行っていなかったので mblist_by_board_min2.dat のデータを使ってやり直してみました。その結果、計算結果の傾向は mblist_by_board_min.dat の場合とほとんど変わらなかったので、その後の記事の説明の内容を変える必要はないことがわかりましたので、以前の記事の内容は修正しないことします。
:::

## 深さごとの効率の差の再確認

プログラムは省略しますが、__先程と同じプログラム__ で __深さごとの効率の差を再検証__ すると、以下のような実行結果が表示されます。

実行結果

```
sv: False, init_ab: False, use_tt: False
depth = 0 abs = 18297 mtdf = 17125 diff = -1172
depth = 1 abs =  7523 mtdf =  7024 diff =  -499
depth = 2 abs =  7653 mtdf =  7726 diff =    73
depth = 3 abs = 10465 mtdf = 11928 diff =  1463
depth = 4 abs =  7671 mtdf =  9290 diff =  1619
depth = 5 abs =  3943 mtdf =  5084 diff =  1141
depth = 6 abs =  1660 mtdf =  2492 diff =   832
depth = 7 abs =   406 mtdf =   709 diff =   303
depth = 8 abs =    68 mtdf =   136 diff =    68
total     abs = 57686 mtdf = 61514 diff =  3828
略
```

下記は実行結果の __合計をまとめた表__ です。一番上の行の ab は init_ab、tt は use_tt の値で 〇 は True、× は False を表します。各セルの __上段が `ai_abs_all`__、__中段が `ai_mtdf`__、__下段がその差__ です。

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __最短の勝利を目指さない場合__ | 57686<br>61514<br>3828 | 46467<br>53105<br>6638 | 23172<br>19403<br>-3769 | 16291<br>18924<br>2003 | 
| __最短の勝利を目指さす場合__ | 65583<br>67861<br>2278| 62147<br>65402<br>3255 | 25711<br>25134<br>-577 | 24087<br>25022<br>935 |

合計の結果は修正前と同様に `init_ab=False`、`use_tt=True` の場合のみ MTD(f) 法のほうが効率が悪くなります。__全体の傾向は大きく変わりません__。

__置換表を利用しない場合__ で、__深さごとの結果の差をまとめる__ と以下の表のようになります。sv は最短の勝利を目指すかどうかを表します。

|深さ| sv × ab × | sv × ab 〇 | sv 〇 ab × | sv 〇 ab 〇 |
|:--|--:|--:|--:|--:|
|__0__| -1172 | 314 |-3741|-3359|
|__1__| -499|531|-1410|-1032|
|__2__| 73|698|-39|541|
|__3__| 1463|2605|1873|2649|
|__4__| 1619|1334|2820|2170|
|__5__| 1141|762|1513|1024|
|__6__| 832|261|891|891|
|__7__| 303|111|303|303|
|__8__| 68|22|68|68|
|__合計__| 3828|6638|2278|3255|

表から __α 値と β 値の初期値を負の無限大と正の無限大とする場合（ab ×）__ はいずれも __深さが 0 と 1 のノードで MTD(f) 法の方が効率が高くなる__ ことがわかります。

上記では __深さごとの合計__ を計算していますが、__深さごとにノードの数が異なる__ ので __深さごとの平均__ を比較したほうが適切しょう。そこで、上記のプログラムを下記のように修正して __深さごとの平均__、__平均の差__、__平均の割合（ratio）__ を表示することにします。割合は __100 % よりも小さい場合__ に __MTD(f) 法のほうが効率が高い__ ことを表します。


* __7、8 行目__：深さごとのノードの数を数える変数を初期化する
* __13、17 行目__：計算したノードの深さの数を増やす
* __19 ~ 20 行目__：深さごとのノードの数、平均、平均の差、平均の割合などを計算して表示する。最後にあった全体の合計に関する表示は削除した

```python
 1  for shortest_victory in [False, True]:
 2      for use_tt in [False, True]:
 3          for init_ab in [False, True]:
 4              print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
 5              count = [0] * 9
 6              count2 = [0] * 9
 7              num = [0] * 9
 8              num2 = [0] * 9
 9              for mb in mblist:
10                  count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
11                                          init_ab=init_ab, use_tt=use_tt,
12                                          calc_score=True, calc_count=True)
13                  num[mb.move_count] += 1
14                  count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
15                                          init_ab=init_ab, use_tt=use_tt,
16                                          calc_score=True, calc_count=True)
17                  num2[mb.move_count] += 1
18              for depth in range(9):
19                  ave1 = count[depth] / num[depth]
20                  ave2 = count2[depth] / num2[depth]
21                  print(f"depth = {depth} num = {num[depth]:3} abs = {ave1:7.1f} mtdf = {ave2:7.1f} diff = {ave2 - ave1:7.1f} ratio = {ave2 / ave1 * 100:3.0f}%")
```

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

```python
for shortest_victory in [False, True]:
    for use_tt in [False, True]:
        for init_ab in [False, True]:
            print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
            count = [0] * 9
            count2 = [0] * 9
            num = [0] * 9
            num2 = [0] * 9
            for mb in mblist:
                count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
                num[mb.move_count] += 1
                count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
                num2[mb.move_count] += 1
            for depth in range(9):
                ave1 = count[depth] / num[depth]
                ave2 = count2[depth] / num2[depth]
                print(f"depth = {depth} num = {num[depth]:3} abs = {ave1:7.1f} mtdf = {ave2:7.1f} diff = {ave2 - ave1:7.1f} ratio = {ave2 / ave1 * 100:3.0f}%")
```
</details>

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

```diff_python
for shortest_victory in [False, True]:
    for use_tt in [False, True]:
        for init_ab in [False, True]:
            print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
            count = [0] * 9
            count2 = [0] * 9
+           num = [0] * 9
+           num2 = [0] * 9
            for mb in mblist:
                count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
+               num[mb.move_count] += 1
                count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
+               num2[mb.move_count] += 1
            for depth in range(9):
-               print(f"depth = {depth} abs = {count[depth]:5} mtdf = {count2[depth]:5} diff = {count2[depth] - count[depth]:5}")
+               ave1 = count[depth] / num[depth]
+               ave2 = count2[depth] / num2[depth]
+               print(f"depth = {depth} num = {num[depth]:3} abs = {ave1:7.1f} mtdf = {ave2:7.1f} diff = {ave2 - ave1:7.1f} ratio = {ave2 / ave1 * 100:3.0f}%")
-           print(f"total     abs = {sum(count):5} mtdf = {sum(count2):5} diff = {sum(count2) - sum(count):5}")
```
</details>

実行結果

```
sv: False, init_ab: False, use_tt: False
depth = 0 num =   1 abs = 18297.0 mtdf = 17125.0 diff = -1172.0 ratio =  94%
depth = 1 num =   3 abs =  2507.7 mtdf =  2341.3 diff =  -166.3 ratio =  93%
depth = 2 num =  12 abs =   637.8 mtdf =   643.8 diff =     6.1 ratio = 101%
depth = 3 num =  38 abs =   275.4 mtdf =   313.9 diff =    38.5 ratio = 114%
depth = 4 num = 108 abs =    71.0 mtdf =    86.0 diff =    15.0 ratio = 121%
depth = 5 num = 153 abs =    25.8 mtdf =    33.2 diff =     7.5 ratio = 129%
depth = 6 num = 183 abs =     9.1 mtdf =    13.6 diff =     4.5 ratio = 150%
depth = 7 num =  95 abs =     4.3 mtdf =     7.5 diff =     3.2 ratio = 175%
depth = 8 num =  34 abs =     2.0 mtdf =     4.0 diff =     2.0 ratio = 200%
略
```

置換表を利用しない場合で、深さごとの __平均の差__ をまとめると以下の表のようになります。

|深さ| ノードの数 |  sv × ab × | sv × ab 〇 | sv 〇 ab × | sv 〇 ab 〇 |
|:--|--:|--:|--:|--:|--:|
|__0__| 1 | -1172.0 | 314.0 |-3741.0|-3359.0|
|__1__| 3 | -166.3|177.0|-470.0|-344.0|
|__2__| 12 | 6.1|58.2|-3.2|45.1|
|__3__| 38 | 38.5|68.6|49.3|69.7|
|__4__| 108 | 15.0|12.4|26.1|20.1|
|__5__| 153 | 7.5|5.0|9.9|6.7|
|__6__| 183 | 4.5|1.4|4.9|4.9|
|__7__| 95 | 3.2|1.2|3.2|3.0|
|__8__| 34 | 2.0|0.6|2.0|2.0|

__平均の差__ の表では __深さが 3 以下__ の場合は先ほどの考察通りに深さが __浅いほうが小さくなる__ ので __MTD(f) 法のほうが効率が良い__ ことがわかります。一方 __深さが 4 以上__ の場合は逆に深さが __深いほうが小さくなる__ ため、__先程の考察に反して__ 深さが __深いほうが効率が高くなるように見えるかもしれません__。実際にはそれは __錯覚__ で、深さが __深い程子孫ノードの数が少なくなる__ ため、__枝狩りの数に大きな差が生まれなくなってしまう__ からです。

:::note
他にも上記の表から、同一局面を考慮した場合は深さが 6 のノードが最も多く、深さが 4 ~ 7 のノードの数が多いことがわかります。
:::


一方、下記の __平均の割合__（MTD(f) 法 / αβ 法）をまとめた表では、先程の説明通りに深さが __深いほうがほぼすべての場合で__ MTD(f) 法のほうが __効率が悪くなる__ ことが確認できます。このように、__2 つの数値の比較__ を行う際には __差と割合のどちらが適切であるか__ を考える必要がある点に注意して下さい。

|深さ| sv × ab × | sv × ab 〇 | sv 〇 ab × | sv 〇 ab 〇 |
|:--|--:|--:|--:|--:|
|__0__| 94 % | 102 % | 82 % | 84 % |
|__1__| 93 % | 108 % | 83 % | 87 % |
|__2__| 101 % | 113 % | 100 % | 106 % |
|__3__| 114 % | 131 % | 115 % | 123 % | 
|__4__| 121 % | 127 % | 135 % | 131 % |
|__5__| 129 % | 126 % | 138 % | 128 % |
|__6__| 150 % | 122 % | 154 % | 154 % |
|__7__| 175 % | 132 % | 175 % | 175 % |
|__8__| 200 % | 132 % | 200 % | 200 % |

:::note
先程深さが 8 のノードの場合は MTD(f) 法では 4 個以上、αβ 法では 2 個のノードの計算が行なわれると説明しましたが、sv × ab × の場合に下記のように abs = 2.0、mtdf = 4.0 と表示されることからそのことが正しいことが確認できます。

```
depth = 8 num =  34 abs =     2.0 mtdf =     4.0 diff =     2.0 ratio = 200%
```
:::

:::note
sv × ab 〇 の場合は下記のように abs = 2.0 となりますが、mtdf のほうが mtdf = 2.6 のように 4 以上とならない点がおかしいと思った人はいないでしょうか？

```
depth = 8 num =  34 abs =     2.0 mtdf =     2.6 diff =     0.6 ratio = 132%
```

その理由はこの場合に [MTD(f) 法のアルゴリズム](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#mtdf-%E6%B3%95%E3%81%AE%E8%80%83%E3%81%88%E6%96%B9%E3%81%A8%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0) に従って計算を行うと、__最初の null window search__ で αβ 値として __1 が計算された場合に__ 下記の理由から次の null window search が行われず、__1 回の null window search しか行われない__ からです。

* 最初のミニマックス値の範囲（下界と上界）は [-1, 1] である
* 最初のウィンドウが (0, 1) の null window search で αβ 値が 1 と計算された場合は fail high なので、ミニマックス値の範囲の下界が 1 で更新される
* その結果ミニマックス値の範囲が [1, 1] となり、下界と上界が等しくなるため次の null window search は行われない

このように、MTD(f) 法では例外的に 1 回の null window search しか行われない場合がありますが、一般的にはそのような状況はまず起きないので 2 回以上の null window search を行うと考えて良いと思います。
:::

## sv と ab の違いに対する考察

上記の表から、以下の事がわかりますが、いずれも αβ 法の場合のウィンドウ幅と null window search の場合の __ウィンドウ幅の差が小さくなるため__、両者の __枝狩りの効率の差が小さくなるから__ です。

* sv が × のほうが MTD(f) の効率が悪い
* ab が 〇 のほうが効率が悪い

下記は αβ 法 で $N$ のミニマックス値を計算する際の $N$、$N$ の子ノード、$N$ の孫以降の子孫ノードでの __ウィンドウの最大幅__ です。ただし、$N$ は max ノードであるとします。min ノードの場合も同様なので余裕がある方は表を作ってみて下さい。表のように __sv が × のほうが__ 〇 よりも、__ab が 〇 のほうが__ × よりも __ウィンドウ幅が同じか狭く__ なります。

| | $N$|$N$ の子ノード|$N$ の孫ノード以降のノード |
|:-:|:-:|:-:|:-:|
| __sv × ab ×__ |(-∞, ∞)|(-1, ∞)|(-1, 1)|
| __sv × ab 〇__ |(-1, 1)|(-1, 1)|(-1, 1)|
| __sv 〇 ab ×__ |(-∞, ∞)|(-2, ∞)|(-2, 3)|
| __sv 〇 ab 〇__ |(-2, 3)|(-2, 3)|(-2, 3)|

特に __sv × ab 〇__ の場合は、αβ 法では __ウィンドウ幅の最大値が常に 2__ であるため、MTD(f) 法での null window search のウィンドウ幅である 1 と比べて __ウィンドウ幅が最大でもたったの 1 しか変わりません__。そのため __両者の効率の差が小さくなり__、この場合は __常に null window search を複数回行う MTD(f) の効率が αβ 法よりも悪化する__ ようです。

# 置換表を利用する場合の効率の比較

次に __置換表を利用する場合__ の効率の比較を行います。

先程の結果から、置換表を利用する場合の __深さごとの平均の割合__（MTD(f) 法 / αβ 法）をまとめた表です。

|深さ| sv × ab × | sv × ab 〇 | sv 〇 ab × | sv 〇 ab 〇 |
|:--|--:|--:|--:|--:|
|__0__| 83 % | 105 % | 69 % | 71 % |
|__1__| 86 % | 108 % | 72 % | 75 % |
|__2__| 71 % | 107 % | 94 % | 98 % |
|__3__| 88 % | 111 % | 92 % | 98 % | 
|__4__| 75 % | 111 % | 98 % | 110 % |
|__5__| 90 % | 116 % | 107 % | 114 % |
|__6__| 95 % | 118 % | 140 % | 140 % |
|__7__| 127 % | 128 % | 166 % | 166 % |
|__8__| 166 % | 132 % | 200 % | 200 % |

sv × ab 〇 では残念ながら相変わらずすべての場合で MTD(f) 法のほうが効率が悪いですが、__それ以外の場合__ では置換表を利用しない場合と比べて __先程よりも深いノードまで MTD(f) のほうが効率が良く__ なっています。なお、__深さが浅いほうが MTD(f) 法の方が効率が良い__ 点は __置換表を利用しない場合と同様__ です。

## 置換表を利用した場合に効率が上昇する理由

αβ 法と比較した場合に、__置換表を利用したほうがより効率が高くなる理由__ は、[前回の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#mtdf-%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)でも説明しましたが、__MTD(f) 法__ では __同じノードに対して__ 異なるウィンドウで __複数回の αβ 値を計算__ するので、__同じ子孫ノードに対して何度も αβ 値を計算__ することになるからです。

そのことを確認するために、__毎回の null window search__ で __計算されたノードの数などを表示__ するように __`ai_mtdf`__ を修正することにします。その際に回数を「__その回の null window search での回数/回数の合計__」のように表示することにします。また、[前回の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#%E6%89%8B%E9%A0%86-1-%E3%81%A7-f--s-%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AB%E8%A1%8C%E3%82%8F%E3%82%8C%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81)で示した __下記の表の情報の表示__ を行うことにします。ただし、回数と分類の列の表示はあまり重要ではないので省略しました。

|回数|分類|ウィンドウ|αβ 値|αβ の範囲|MM の範囲|
|:-:|:--|:--|:--|:--|:--|
|1|$f < s$, [$-∞$, $∞$]|($f_0 - 1$, $f_0$)| $f_1$|fail high|[$f_1$, $∞$]|

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

* __8 行目__：結果の表の見出しの行を表示する
* __11 行目__：`count` にはそれまでに行なった null window search で評価値を計算したノードの合計が計算されている。この回での null window search の合計を計算するために、null window search を行う直前の `count` を `prevcount` に代入して記録しておく
* __15、17 行目__：計算した αβ の範囲の種類表す文字列を `type` に代入する
* __19 行目__：その回の null window search に対する情報を表示する
* 23 行目の前にあった `couht` を表示する処理はもう必要がないので削除した

```python
 1  from ai import ai_by_score, dprint
 2  from copy import deepcopy
 3  
 4  @ai_by_score
 5  def ai_mtdf(mb, debug=False, shortest_victory=False, init_ab=False, use_tt=False, 
 6              f=0, ai_for_mo=None, params={}, sort_allnodes=False, calc_count=False):           
元と同じなので省略
 7      tt = {}
 8      dprint(debug, "      count | ウィンドウ | αβ 値 |      type |    MM の範囲")
 9      while lbound != ubound:
10          beta = f + 1 if lbound == f else f
11          prevcount = count
12          f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
13          if f >= beta:
14              lbound = f
15              type = "fail high"
16          else:
17              ubound = f
18              type = "fail low "
19          dprint(debug, f"{count - prevcount:5}/{count:5} |  ({beta - 1:2}, {beta:2}) |    {f:2} | {type} | [{lbound:4}, {ubound:4}]")
20   
21      score = f
22              
23      if calc_count:
24          return count
25      if mb.turn == Marubatsu.CIRCLE:
26          score *= -1
27      return score
```

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

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

@ai_by_score
def ai_mtdf(mb, debug=False, shortest_victory=False, init_ab=False, use_tt=False, 
            f=0, ai_for_mo=None, params={}, sort_allnodes=False, calc_count=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
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if ai_for_mo is not None:
            if sort_allnodes:
                score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
                score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
                legal_moves = [x[0] for x in score_by_move_list]
            else:
                legal_moves = mborig.calc_legal_moves()
                bestmove = ai_for_mo(mborig, rand=False, **params)
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
    lbound = min_score if init_ab else float("-inf")
    ubound = max_score if init_ab else float("inf")

    tt = {}
    dprint(debug, "      count | ウィンドウ | αβ 値 |      type |    MM の範囲")
    while lbound != ubound:
        beta = f + 1 if lbound == f else f
        prevcount = count
        f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
        if f >= beta:
            lbound = f
            type = "fail high"
        else:
            ubound = f
            type = "fail low "
        dprint(debug, f"{count - prevcount:5}/{count:5} |  ({beta - 1:2}, {beta:2}) |    {f:2} | {type} | [{lbound:4}, {ubound:4}]")
 
    score = f
            
    if calc_count:
        return 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_mtdf(mb, debug=False, shortest_victory=False, init_ab=False, use_tt=False, 
            f=0, ai_for_mo=None, params={}, sort_allnodes=False, calc_count=False):           
元と同じなので省略
    tt = {}
+   dprint(debug, "      count | ウィンドウ | αβ 値 |      type |    MM の範囲")
    while lbound != ubound:
        beta = f + 1 if lbound == f else f
+       prevcount = count
        f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
        if f >= beta:
            lbound = f
+           type = "fail high"
        else:
            ubound = f
+           type = "fail low "
+       dprint(debug, f"{count - prevcount:5}/{count:5} |  ({beta - 1:2}, {beta:2}) |    {f:2} | {type} | [{lbound:4}, {ubound:4}]")
 
    score = f
            
-   dprint(debug, "count =", count)
    if calc_count:
        return count
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

上記の修正後に下記のプログラムで __置換表を利用しない場合__ の __ゲーム開始時の局面__ のミニマックス値を計算すると、実行結果のように __1 回目__ の null window search で __966 個__、__2 回目__ で __16159 個__ のノードの評価値が計算されたことがわかります。また、__それぞれの null window search__ での __ウィンドウ__、__計算された αβ 値__、__ミニマックス値の範囲__ がどのように変化したかを __確認することができます__。

```python
mb = Marubatsu()
ai_mtdf(mb, calc_score=True, calc_count=True, debug=True)
```

実行結果

```
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  966/  966 |  (-1,  0) |     0 | fail high | [   0,  inf]
16159/17125 |  ( 0,  1) |     0 | fail low  | [   0,    0]
```

なお、__ゲーム開始時の局面__ は __引き分けの局面__ なのでその __ミニマックス値は 0__ です。上記のプログラムでは __`f = 0`__ という __正しいミニマックス値を推定__ したので、[前回の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#f--s----%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AB%E8%A1%8C%E3%81%AA%E3%82%8F%E3%82%8C%E3%82%8B%E5%87%A6%E7%90%86-1)で検証した $\boldsymbol{f = s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] という分類で行なわれる __下記の表と同じ計算__ が行なわれることが確認できます。

|回数|分類|ウィンドウ|αβ 値|αβ の範囲|MM の範囲|
|:-:|:--|:--|:--|:--|:--|
|1|$f = s$, [$-∞$, $∞$]|($s - 1$, $s$)| $f_1 = s$|fail high|[$f_1$, $∞$] = [$s$, $∞$]|
|2|$f = s$, [$f$, $∞$]|($s$, $s + 1$)|$f_2=s$|fail low|[$f_1$, $f_2$] = [$s$, $s$]|

次に、下記のプログラムで __置換表を利用する場合__ の __ゲーム開始時の局面__ のミニマックス値を計算すると、実行結果のように __1 回目__ の null window search で __356 個__、__2 回目__ で __521 個__ のノードの評価値が計算されたことから、置換表を利用する事で __2 回目__ の null window search で評価値が計算されたノードの数が __大幅に減ったことが確認__ できます。なお、ウィンドウや αβ 値など、それ以外の部分の表示は置換表を利用する場合とそうでない場合で同じになります。

```python
ai_mtdf(mb, use_tt=True, calc_score=True, calc_count=True, debug=True)
```

実行結果

```
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  356/  356 |  (-1,  0) |     0 | fail high | [   0,  inf]
  521/  877 |  ( 0,  1) |     0 | fail low  | [   0,    0]
```

次に、下記のプログラムで __ゲーム開始後に (0, 0) に着手__ を行った局面で比較を行うと、実行結果のように __1 回目__ の null window search の __回数が 965 から 355__ に __約 1/3 に減っている__ のに対し、__2 回目__ の null window search の __回数が 1251 から 209__ に __約 1/6__ に __さらに大幅に減っている__ ことが確認できます。

```python
mb.move(0, 0)
ai_mtdf(mb, calc_score=True, calc_count=True, debug=True)
ai_mtdf(mb, use_tt=True, calc_score=True, calc_count=True, debug=True)
```

実行結果

```
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  965/  965 |  (-1,  0) |     0 | fail high | [   0,  inf]
 1251/ 2216 |  ( 0,  1) |     0 | fail low  | [   0,    0]
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  355/  355 |  (-1,  0) |     0 | fail high | [   0,  inf]
  209/  564 |  ( 0,  1) |     0 | fail low  | [   0,    0]
  ```

このように、__MTD(f) 法__ では __置換表を利用することが重要__ であることが確認できました。

余裕がある方は他の局面でも比較してみて下さい。

# 今回の記事のまとめ

今回の記事では __αβ 法と比較__ することで __MTD(f) 法の効率について検証__ しました。また、ゲーム木の __部分木の深さと枝狩りの関係について検証__  し、__部分木の深さが浅すぎる__ と __MTD(f) 法 は αβ 法よりも効率が悪くなる場合がある__ ことを示しました。

次に、__MTD(f) で置換表を利用することの重要性について検証__ しました。

今回の記事の MTD(f) 法での計算では、__すべてのノードでミニマックス値を 0 と推定__ して行なったため、ミニマックス値の __推定の精度はあまり高くありません__。それでも 〇× ゲームでは、浅いノードの局面であれば MTD(f) のほうが αβ 法よりも効率が高くなります。

次回の記事では推定したミニマックス値の精度と MTD(f) 法の効率の関係と、スカウト法と MTD(f) 法を比較することで MTD(f) 法の効率の検証を行うことにします。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/3cb0369dc4b3014e1e13

[^1]:指数関数は $n^d$ のような関数で、$n^d$ の場合は $d$ が 1 増えるごとに $n$ 倍になります。ただし、爆発的に増えるのは $n > 1$ の場合です