Pythonで〇×ゲームのAIを一から作成する　その170　ミニマックス値の推定値の精度による MTD(f) 法の効率の検証

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/8bd4935a8ce670cebba0

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

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

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

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

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

# ミニマックス値の推定値の精度と MTD(f) 法の効率の関係の検証

前回の記事ではすべての局面でミニマックス値を 0 と推定した状態での MTD(f) 法の効率を検証しました。

[以前の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#mtdf-%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)で __MTD(f) 法__ では __推定したミニマックス値の精度が高いことが重要__ であると説明しましたので、今回の記事では最初にそのことを検証することにします。

具体的には __ミニマックス値の推定値の精度と MTD(F) 法の効率の関係__ について、以下の条件で検証します。

* 最短の勝利を目指さない場合の評価値の範囲が -1 ~ 1 と狭いため、より広い -2 ~ 3 を評価値として計算する __最短の勝利を目指す場合__ で計算を行う
* MTD(f) 法は置換表の利用を前提とするアルゴリズムなので置換表を利用する
* 初期設定のミニマックス値の範囲が最も広くなるように、α 値と β 値の初期値を負の無限大と正の無限大とする
* ゲーム開始時の局面に対して、__-2 ~ 3 の範囲の整数の値を__ ミニマックス値として __推定__ して MTD(f) 法で計算を行ない、__それらの結果を比較__ する

## 検証を行うプログラムの実行と問題点

下記は、その計算を行うプログラムですが、実行結果のようにウィンドウや αβ 値などで小数点以下の数値が表示されたりされなかったりする場合があり、__表示が縦に揃わないという問題がある__ ことが判明しました。

* __5 行目__：-2 ~ 3 の範囲の整数でミニマックス値の推定値である `f` を増加しながら繰り返し処理を行う
* __7、8 行目__：上記の設定で MTD(f) 法の計算を行ない、評価値が計算された数などのデバッグ表示を行う
* __9 行目__：空行を表示することで、それぞれの結果の間を開けて見やすいようにした

```python
1  from ai import ai_mtdf
2  from marubatsu import Marubatsu
3  
4  mb = Marubatsu()
5  for f in range(-2, 4):
6      print(f"f = {f}")
7      ai_mtdf(mb, f=f, shortest_victory=True, use_tt=True,  calc_score=True, 
8              calc_count=True, debug=True)
9      print()
```

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

```python
from ai import ai_mtdf
from marubatsu import Marubatsu

mb = Marubatsu()
for f in range(-2, 4):
    print(f"f = {f}")
    ai_mtdf(mb, f=f, shortest_victory=True, use_tt=True,  calc_score=True,
            calc_count=True, debug=True)
    print()
```

</details>

実行結果

```
f = -2
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  171/  171 |  (-3, -2) |    -2.0 | fail high | [-2.0,  inf]
  171/  342 |  (-2.0, -1.0) |    -1.0 | fail high | [-1.0,  inf]
  206/  548 |  (-1.0, 0.0) |     0 | fail high | [   0,  inf]
  520/ 1068 |  ( 0,  1) |     0 | fail low  | [   0,    0]
略
```

## `ai_mtdf` のデバッグ表示の修正

__評価値は整数のみが計算される__ ので、下記のプログラムのように `ai_mtdf` のデバッグ表示で __小数点以下の数値が表示されないように修正__ することにします。

* __10 行目__：__[書式指定](https://qiita.com/ysgeso/items/bf42b7b578bc2d5da949#%E6%9B%B8%E5%BC%8F%E6%8C%87%E5%AE%9A)__ に 2.0f や 4.0f を指定することで、小数点以下の数値を表示しないように修正した

```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          dprint(debug, f"{count - prevcount:5.0f}/{count:5.0f} |  ({beta - 1:2.0f}, {beta:2.0f}) |    {f:2.0f} | {type} | [{lbound:4.0f}, {ubound:4.0f}]")
元と同じなので省略
```

<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.0f}/{count:5.0f} |  ({beta - 1:2.0f}, {beta:2.0f}) |    {f:2.0f} | {type} | [{lbound:4.0f}, {ubound:4.0f}]")
 
    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:
元と同じなので省略
-       dprint(debug, f"{count - prevcount:5}/{count:5} |  ({beta - 1:2}, {beta:2}) |    {f:2} | {type} | [{lbound:4}, {ubound:4}]")
+       dprint(debug, f"{count - prevcount:5.0f}/{count:5.0f} |  ({beta - 1:2.0f}, {beta:2.0f}) |    {f:2.0f} | {type} | [{lbound:4.0f}, {ubound:4.0f}]")
元と同じなので省略
```
</details>

## 検証の再実行

上記の修正後に改めて下記のプログラムを実行すると、下記のような実行結果が表示されます。[以前の記事](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]、最後には __下界と上界がミニマックス値に等しくなる__ ことが確認できます。

```python
for f in range(-2, 4):
    print(f"f = {f}")
    ai_mtdf(mb, f=f, shortest_victory=True, use_tt=True,  calc_score=True,
            calc_count=True, debug=True)
    print()
```

実行結果

```
f = -2
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  171/  171 |  (-3, -2) |    -2 | fail high | [  -2,  inf]
  171/  342 |  (-2, -1) |    -1 | fail high | [  -1,  inf]
  206/  548 |  (-1,  0) |     0 | fail high | [   0,  inf]
  520/ 1068 |  ( 0,  1) |     0 | fail low  | [   0,    0]

f = -1
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  261/  261 |  (-2, -1) |    -1 | fail high | [  -1,  inf]
  206/  467 |  (-1,  0) |     0 | fail high | [   0,  inf]
  520/  987 |  ( 0,  1) |     0 | fail low  | [   0,    0]

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

f = 1
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  700/  700 |  ( 0,  1) |     0 | fail low  | [-inf,    0]
  118/  818 |  (-1,  0) |     0 | fail high | [   0,    0]

f = 2
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  661/  661 |  ( 1,  2) |     1 | fail low  | [-inf,    1]
  236/  897 |  ( 0,  1) |     0 | fail low  | [-inf,    0]
  124/ 1021 |  (-1,  0) |     0 | fail high | [   0,    0]

f = 3
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  517/  517 |  ( 2,  3) |     2 | fail low  | [-inf,    2]
  493/ 1010 |  ( 1,  2) |     1 | fail low  | [-inf,    1]
  256/ 1266 |  ( 0,  1) |     0 | fail low  | [-inf,    0]
  125/ 1391 |  (-1,  0) |     0 | fail high | [   0,    0]
```

下記は上記の実行結果をまとめた表です。__ノードの数__ の列は __評価値が計算されたノードの数__、__nw の回数__ は __null window search を行なった回数__ を表します。それ以外の列の意味についてはこの後で説明します。

|f|絶対誤差|ノードの数| nw の回数|`f` の推移|
|:-:|:-:|--:|--:|:--|
|__-2__|2|1068|4| -2 → -2 → -1 → 0 → 0 |
|__-1__|1|987|3| -1 → -1 → 0 → 0 |
|__0__|0|877|2| 0 → 0 → 0 |
|__1__|1|818|2| 1 → 0 → 0 |
|__2__|2|1021|3| 2 → 1 → 0 → 0 |
|__3__|3|1391|4| 3 → 2 → 1 → 0 → 0 |

__精度を表す指標の一つ__ に正確な値との差を計算する __誤差__（error）があります。__誤差が 0 の場合が正確な値__ なので __精度が最も高く__、__0 から離れるほど精度が低い__ ことを表します。

誤差は正の値と負の値があるので、その __絶対値__（absolute value）を計算した __絶対誤差__（absolute error）を精度の指標とする場合があります。絶対誤差の場合は __0 が精度が最も高く__、__大きい程精度が低い__ という性質があり、__符号を気にすることなく精度を表すことができる__ ので実際に良く使われます。そこで、上記の表には絶対誤差の列を作りました。

〇×ゲームの __ゲーム開始時の局面__ は引き分けの局面なので、その __ミニマックス値は 0__ です。そのため絶対誤差は `f - 0 = f` の絶対値で計算されるので、 __絶対誤差の列__ には __`f` の絶対値と同じ値を表記__ しました。

:::note
日本語で __誤差と表記__ した場合は __絶対誤差を表す場合が多い__ のではないかと思います。例えば誤差が -1 から -10 になった場合は、__数値としては減っていますが、精度が減っている__ ので __誤差は増えていると説明される__ ことがあります。この「誤差が増えている」という表記の誤差は絶対誤差を表します。
:::

MTD(f) 法は __最初にミニマックス値として推定した `f`__ を、null window search で計算した __αβ 値で更新__ していくことで __最終的に `f` にミニマックス値が計算される__ というアルゴリズムです。そこで、`f` の推移の列には __`f`__ がミニマックス値に向けて __更新されていく様子__ を表記することにしました。__最初に推定した数値を表記する__ ので `f` の推移には __null window search の回数 + 1 個__ の数値が表記されます。

## 検証結果の考察

下記は先ほどの表の再掲です。

|f|絶対誤差|ノードの数| nw の回数|`f` の推移|
|:-:|:-:|--:|--:|:--|
|__-2__|2|1068|4| -2 → -2 → -1 → 0 → 0 |
|__-1__|1|987|3| -1 → -1 → 0 → 0 |
|__0__|0|877|2| 0 → 0 → 0 |
|__1__|1|818|2| 1 → 0 → 0 |
|__2__|2|1021|3| 2 → 1 → 0 → 0 |
|__3__|3|1391|4| 3 → 2 → 1 → 0 → 0 |

上記の表と先程の実行結果から、[以前の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4)で説明した下記のように __`f` とミニマックス値の範囲が実際に推移__ していくことが確認できます。

* `f` の推移の列の値は __いずれもミニマックス値である 0 に向かって__ 値の更新が行われ、ミニマックス値の範囲の __下界または上界が `f` の値で更新__ される
* 最後から 2 番目の null window search で __`f` がミニマックス値で更新__ され、ミニマックス値の範囲の __下界または上界がミニマックス値に更新__ される
* 最後の null window search によって __もう片方のミニマックス値の下界と上界がミニマックス値に更新__ されることで __下界と上界が等しくなり__、ミニマックス値が計算される

細かい話になりますが、ミニマックス値の推定値を $f$、ミニマックス値を $s$ と表記した場合に下記のような計算が実際に行われることが確認できます。

* $f < s$ の場合は [以前の記事](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)で説明したように、最後から 2 番目までの null window search で __`f` の値が増える__ 方向で __`s` に向かって更新__ される。ただし、__初回__ の null window search __のみ `f` が変化しない場合がある__
* $f = s$ の場合は [以前の記事](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)で説明したように、__2 回__ の null window search が行なわれる
* $f > s$ の場合は [以前の記事](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-2)で説明したように、初回も含めて最後から 2 番目までの null window search で __`f` の値が減る__ 方向で __`s` に向かって更新__ される

また、[以前の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#mtdf-%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)で説明したように、null window search の回数と、$f$、$s$ の間には下記の表のような関係があります。

|条件|最小回数|最大回数|
|:-:|:-:|:-:|
|$\boldsymbol{f < s}$|$2$|$s - f + 2$|
|$\boldsymbol{f = s}$ |$2$|$2$|
|$\boldsymbol{f > s}$|$2$|$f - s + 1$|

上記の表の最大回数を絶対誤差を利用して表すと下記の表のようになります。

|条件|最小回数|最大回数|
|:-:|:-:|:-:|
|$\boldsymbol{f < s}$|$2$|絶対誤差 + 2|
|$\boldsymbol{f = s}$ |$2$|$2$|
|$\boldsymbol{f > s}$|$2$|絶対誤差 + 1|

上記の表から、__絶対誤差が大きい程__ null window search の __最大回数が増える__ ことがわかります。また、__最も精度が高い絶対誤差が 0__ の場合は __常に最小回数である 2 回__ の null window search が行なわれます。従って、MTD(f) 法では __ミニマックス値の精度が高いほど__、null window search の __回数が少なくなる__ という __傾向がある__ ことがわかります。

下記は先ほどの表から、__絶対誤差__ と __null window search の回数__ を抜き出してまとめたものです。平均の列から、実際に __精度が高い__（絶対誤差が少ない）ほうが null window search の __回数が少なくなるという傾向がある__ ことが確認できます。

|絶対誤差| nw の回数| nw の回数の平均|
|:-:|:-:|--:|
|__0__|2|2.0|
|__1__|2、3|2.5|
|__2__|3、4|3.5|
|__3__|4|4.0|

また、null window search の __回数が少ない程__、一般的に __評価値を計算するノードの数__ が __減ります__。下記は先ほどの表から、null window search と評価値を計算したノードの数を抜き出してまとめたものです。平均の列から実際に __null window search が少ないほう__ が計算された __ノードの数が少なくなるという傾向がある__ 事が確認できます。

|nw の回数|ノードの数|ノードの数の平均|
|--:|--:|--:|
|__2__|877<br>818|847.5|
|__3__|987<br>1021|1004.0|
|__4__|1068<br>1391|1229.5|

下記は __絶対誤差と評価値が計算されたノードの数__ をまとめた表です。平均の列から実際に __精度が高い__（絶対誤差が少ない）ほうが計算された __ノードの数が少なくなるという傾向がある__ ことが確認できます。

|絶対誤差|ノードの数|ノードの数の平均|
|--:|--:|--:|
|__0__|877|877.0|
|__1__|987<br>818|902.5|
|__2__|1068<br>1021|1044.5|
|__3__|1391|1391.0|

これらのことから、MTD(f) には以下の性質があり、〇× ゲームではゲーム開始時の局面でその性質が正しいことが確認できました。

:::note warn
__MTD(f) 法__ では、推定したミニマックス値の __精度が高い程__ null window search の回数が減り、その結果評価値を計算するノードの数が減るため、__効率が高くなる傾向がある__。
:::

## 別の局面での検証

念のため、__他の局面__ でも同様の検証を行うことにします。

ゲーム開始時の局面では 'f' はミニマックス値に向かって 1 つずつ変化していますが、__2 つ以上変化__ する場合もあります。下記はゲーム開始時の局面から __(1, 1)、(0, 0) に着手を行った局面__ に対して __先程と同じ検証__ を行うプログラムです。

```python
mb.move(1, 1)
mb.move(0, 0)
for f in range(-2, 4):
    print(f"f = {f}")
    ai_mtdf(mb, f=f, shortest_victory=True, use_tt=True,  calc_score=True, calc_count=True, debug=True)
    print()
```

実行結果

```
f = -2
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
   71/   71 |  (-3, -2) |    -2 | fail high | [  -2,  inf]
   30/  101 |  (-2, -1) |    -1 | fail high | [  -1,  inf]
   58/  159 |  (-1,  0) |     0 | fail high | [   0,  inf]
  136/  295 |  ( 0,  1) |     0 | fail low  | [   0,    0]

f = -1
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
   83/   83 |  (-2, -1) |    -1 | fail high | [  -1,  inf]
   58/  141 |  (-1,  0) |     0 | fail high | [   0,  inf]
  136/  277 |  ( 0,  1) |     0 | fail low  | [   0,    0]

f = 0
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
   99/   99 |  (-1,  0) |     0 | fail high | [   0,  inf]
  136/  235 |  ( 0,  1) |     0 | fail low  | [   0,    0]

f = 1
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  174/  174 |  ( 0,  1) |     0 | fail low  | [-inf,    0]
   47/  221 |  (-1,  0) |     0 | fail high | [   0,    0]

f = 2
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  172/  172 |  ( 1,  2) |     0 | fail low  | [-inf,    0]
   49/  221 |  (-1,  0) |     0 | fail high | [   0,    0]

f = 3
      count | ウィンドウ | αβ 値 |      type |    MM の範囲
  163/  163 |  ( 2,  3) |     2 | fail low  | [-inf,    2]
   99/  262 |  ( 1,  2) |     1 | fail low  | [-inf,    1]
   34/  296 |  ( 0,  1) |     0 | fail low  | [-inf,    0]
   50/  346 |  (-1,  0) |     0 | fail high | [   0,    0]
```

下記は上記の実行結果をまとめた表です。__この局面のミニマックス値は 0__ なので、__絶対誤差は先ほどと同じ__ になります。下記の表から、ミニマックス値として __2 を推定した場合__ は `2 → 0 → 0` のように __2 以上変化して推移する__ ことが確認できます。

|f|絶対誤差|回数| nw の回数| αβ 値の推移|
|:-:|--:|--:|--:|:--|
|__-2__|2|295|4| -2 → -2 → -1 → 0 → 0 |
|__-1__|1|277|3| -1 → -1 → 0 → 0 |
|__0__|0|235|2| 0 → 0 → 0 |
|__1__|1|221|2| 1 → 0 → 0 |
|__2__|2|221|2| 2 → 0 → 0 |
|__3__|3|346|4| 3 → 2 → 1 → 0 → 0 |

__先程の__ ゲーム開始時の局面での MTD(f) 法で行なった __考察は__、__上記の局面でもそのまま当てはまります__。下記は __絶対誤差__ と __null window search の回数__ を抜き出してまとめたものです。実際に __精度が高い__（絶対誤差が少ない）ほうが null window search の __回数が少なくなるという傾向がある__ ことが確認できます。

|絶対誤差| nw の回数|nw の回数の平均|
|:-:|:-:|--:|
|__0__|2|2.0|
|__1__|2、3|2.5|
|__2__|2、4|3.0|
|__3__|4|4.0|

:::note
これまで「傾向がある」のように表記したのは、上記の表で「絶対誤差が 1 の場合に nw の回数が 3」、「絶対誤差が 2 の場合に nw の回数が 2」という、絶対誤差が多いほうが nw の回数が少ない場合がたまに存在するからです。
:::

下記は __null window search の回数__ と __計算したノードの数__ を抜き出してまとめた表で、この局面でも __null window search の回数が少ないほうが計算したノードの数が少なくなる傾向がある__ ことが確認できます。

|nw の回数|ノードの数|ノードの数の平均|
|--:|--:|--:|
|__2__|235<br>221<br>221|225.7|
|__3__|277|277.0|
|__4__|295<br>346|320.5|

下記は __絶対誤差と評価値が計算されたノードの数__ をまとめた表です。平均の列から実際に __精度が高い__（絶対誤差が少ない）ほうが計算された __ノードの数が少なくなるという傾向がある__ ことが確認できます。

|絶対誤差|ノードの数|ノードの数の平均|
|--:|--:|--:|
|__0__|235|235.0|
|__1__|277<br>221|249.0|
|__2__|295<br>221|258.0|
|__3__|346|346.0|

ここまでで、2 つの局面で検証を行いましたが、いずれも推定した __ミニマックス値の精度が高い__（ミニマックス値に近い）ほど __効率が高くなる傾向がある__ ことが __確認できました__。余裕がある方は、他の局面でも同様の傾向があることを確認してみて下さい。

# スカウト法との比較による MTD(f) 法と 効率の検証

前回の記事では move ordering を行なわない αβ 法と比較しましたが、今回の記事では __move ordering を行うスカウト法__ との __効率の比較__ を以下の条件で行うことにします。

* 最短の勝利を目指す場合と目指さない場合の両方で行う
* 置換表を利用する
* 初期設定のミニマックス値の範囲が最も広くなるように、α 値と β 値の初期値を負の無限大と正の無限大とする
* __move ordering__ と __ミニマックス値の推定__ を __精度の低い順__ に、弱解決ではない __`ai10s`__、弱解決の __`ai14s`__、強解決の __`ai_gt6`__ の __3 種類の AI を利用__ して行う
* __スカウト法__、__move ordering を行なわない MTD(f) 法__、__move ordering を行う MTD(f) 法__ の __3 種類の効率の比較__ を行う
* 同一局面を除いた __すべての局面__ に対して計算を行ない、評価値が計算された __ノードの数の合計を計算__ する。その後で、__スカウト法を 1 とした場合の比率__ を計算することで __効率を比較__ する

上記では、__同じくらいの精度__ で __move ordering__ と __ミニマックス値の推定__ を行った場合の効率の __比較を行うことができるようにする__ ために、__同じ AI の関数__ を利用して __move ordering__ と __ミニマックス値の推定を行う__ ことにしました。なお、__`ai10s`__ と __`ai14s`__ が __計算する評価値__ は、__ミニマックス法__ で計算するノードの __評価値とは異なる__ ので、__ミニマックス値ではありません__。例えば、__`ai10s`__ は[以前の記事](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E7%AF%84%E5%9B%B2%E3%81%AE%E8%A8%88%E7%AE%97)で説明したように、__-1 ~ 12 の評価値を計算__ します。また、__`ai_gt6`__ は局面と最善手の対応表のデータを使って最善手を計算するので、__局面の評価値を計算することはありません__。そのため、__ミニマックス値の推定値__ を __`ai10s`__ などを利用して __直接計算することはできない__ 点に注意が必要です。それらの関数でミニマックス値の推定値をどのように計算すればよいかについて少し考えてみて下さい。

## ミニマックス値の推定値の計算方法とその実装

__ミニマックス値__ と __異なる評価値を計算__ する AI の関数で、__ミニマックス値の推定値を計算する方法__ は以下の通りで、AI の関数で計算した評価値を利用するのではなく、__AI の関数で計算した最善手を利用__ します。この方法を思いつくのは少し難しいかもしれませんが、行う処理は単純です。

* `ai10s` などの AI で __最善手を計算__ する
* 上記で計算した __最善手を着手した局面のミニマックス値__ を、`ai_scout` などの __ミニマックス値を計算する関数で計算__ し、__その値を__ ミニマックス値の __推定値とする__

下記は上記の手法でスカウト法との比較を行う行うプログラムです。

* __4、5 行目__：`ai_gt6` で必要となる、局面と最善手の対応表のデータをファイルから読み込み、`ai_gt6` のキーワード引数 `params` に代入するデータを `gt6_params` に代入する
* __6 行目__：[前回の記事](https://qiita.com/ysgeso/items/8bd4935a8ce670cebba0#%E6%A4%9C%E8%A8%BC%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E4%BD%9C%E6%88%90)で作成した、同一局面を除いた決着がついていない局面のデータの一覧をファイルから読み込む
* __7 行目__：`ai10s`、`ai14s`、`ai_gt6` のそれぞれの AI に対する繰り返し処理を行う。for 文の list の要素には、AI の関数とその AI が必要とするパラメータを表す tuple を代入した
* __8 行目__：最短の勝利を目指さない場合と目指す場合の繰り返し処理を行う
* __9 行目__：計算の条件を表示する
* __10 行目__：計算結果の表の見出しを表示する。move ordering を行う MTD(f) 法は __mtdf(mo)__ と表記した
* __11 ~ 13 行目__：スカウト法、move ordering を行わない MTD(f) 法、move ordering を行う MTD(f) 法のそれぞれで評価値を計算したノードの数を数える変数を 0 で初期化する
* __14 ~ 26 行目__：それぞれの局面に対する繰り返し処理を行う
* __15 ~ 17 行目__：スカウト法の処理を行う
* __18 ~ 21 行目__：`ai_for_mo` に代入された AI の関数で最善手を計算し、その最善手を着手した局面に対するミニマックス値を `ai_scout` で計算する。なお、`mb` は 22 行目以降で利用する必要があるので、最善手を着手した局面は `mb` をコピーした `mbcopy` に対して行う必要がある点に注意する事
* __22、23 行目__：21 行目で計算した `f` をミニマックス値として推定した move ordering を行なわない MDT(f) 法による処理を行う
* __24、25 行目__：move ordrering を行う MTD(f) による処理を行う
* __28、29 行目__：最初の行にそれぞれの場合の回数を、次の行にスカウト法との比率を表示する

```python
 1  from util import load_mblist, load_bestmoves
 2  from ai import ai10s, ai14s, ai_gt6, ai_scout
 3  
 4  bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
 5  gt6_params = {"bestmoves_by_board": bestmoves_by_board}
 6  mblist = load_mblist("../data/mblist_by_board_min2.dat")
 7  for ai_for_mo, params in [(ai10s, {}), (ai14s, {}), (ai_gt6, gt6_params)]:
 8      for shortest_victory in [False, True]:
 9          print(f"ai_for_mo: {ai_for_mo} shortest_victory: {shortest_victory}")
10          print("      | scout |  mtdf | mtdf(mo)")
11          count = 0
12          count2 = 0
13          count3 = 0
14          for mb in mblist:
15              count += ai_scout(mb, ai_for_mo=ai_for_mo, params=params, 
16                                  shortest_victory=shortest_victory, use_tt=True,
17                                  calc_score=True, calc_count=True)
18              x, y = ai_for_mo(mb, **params)
19              mbcopy = deepcopy(mb)
20              mbcopy.move(x, y)
21              f = ai_scout(mbcopy, shortest_victory=shortest_victory, use_tt=True, calc_score=True)
22              count2 += ai_mtdf(mb, shortest_victory=shortest_victory, f=f, 
23                                use_tt=True, calc_score=True, calc_count=True)
24              count3 += ai_mtdf(mb, shortest_victory=shortest_victory, f=f, 
25                                ai_for_mo=ai_for_mo, params=params, use_tt=True,
26                                calc_score=True, calc_count=True)
27          
28          print(f"count | {count:5} | {count2:5} |    {count3:5}")
29          print(f"ratio |       |  {count2 / count * 100:3.0f}% |     {count3 / count * 100:3.0f}%")
30  
```

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

```python
from util import load_mblist, load_bestmoves
from ai import ai10s, ai14s, ai_gt6, ai_scout

bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
gt6_params = {"bestmoves_by_board": bestmoves_by_board}
mblist = load_mblist("../data/mblist_by_board_min2.dat")
for ai_for_mo, params in [(ai10s, {}), (ai14s, {}), (ai_gt6, gt6_params)]:
    for shortest_victory in [False, True]:
        print(f"ai_for_mo: {ai_for_mo} shortest_victory: {shortest_victory}")
        print("      | scout |  mtdf | mtdf(mo)")
        count = 0
        count2 = 0
        count3 = 0
        for mb in mblist:
            count += ai_scout(mb, ai_for_mo=ai_for_mo, params=params, 
                                shortest_victory=shortest_victory, use_tt=True,
                                calc_score=True, calc_count=True)
            x, y = ai_for_mo(mb, **params)
            mbcopy = deepcopy(mb)
            mbcopy.move(x, y)
            f = ai_scout(mbcopy, shortest_victory=shortest_victory, use_tt=True, calc_score=True)
            count2 += ai_mtdf(mb, shortest_victory=shortest_victory, f=f, 
                              use_tt=True, calc_score=True, calc_count=True)
            count3 += ai_mtdf(mb, shortest_victory=shortest_victory, f=f, 
                              ai_for_mo=ai_for_mo, params=params, use_tt=True,
                              calc_score=True, calc_count=True)
        
        print(f"count | {count:5} | {count2:5} |    {count3:5}")
        print(f"ratio |       |  {count2 / count * 100:3.0f}% |     {count3 / count * 100:3.0f}%")
```
</details>

実行結果

```
ai_for_mo: <function ai10s at 0x00000213B5BE51C0> shortest_victory: False
      | scout |  mtdf | mtdf(mo)
count | 13562 | 20420 |    11188
ratio |       |  151% |      82%
ai_for_mo: <function ai10s at 0x00000213B5BE51C0> shortest_victory: True
      | scout |  mtdf | mtdf(mo)
count | 14508 | 25239 |    15115
ratio |       |  174% |     104%
ai_for_mo: <function ai14s at 0x00000213B5BE56C0> shortest_victory: False
      | scout |  mtdf | mtdf(mo)
count | 11609 | 19727 |     8323
ratio |       |  170% |      72%
ai_for_mo: <function ai14s at 0x00000213B5BE56C0> shortest_victory: True
      | scout |  mtdf | mtdf(mo)
count | 11698 | 24275 |    11974
ratio |       |  208% |     102%
ai_for_mo: <function ai_gt6 at 0x00000213B5BE5E40> shortest_victory: False
      | scout |  mtdf | mtdf(mo)
count | 13383 | 19644 |     9947
ratio |       |  147% |      74%
ai_for_mo: <function ai_gt6 at 0x00000213B5BE5E40> shortest_victory: True
      | scout |  mtdf | mtdf(mo)
count | 14419 | 24471 |    15564
ratio |       |  170% |     108%
```

下記は実行結果の中の回数の部分をまとめた表です。__より精度が高い `ai14s`__ のほうが `ai10s` と比べて __いずれの場合でも効率が高くなる__ ことが確認できます。

__最も精度が高い__ 強解決の __`ai_gt6`__ が `ai14s` よりもほどんとの場合で __効率が悪くなる理由__ は、`ai10s` や `ai14s` と `ai_gt6` が __選択する最善手が異なる__ からです。例えば __`ai10s` と `ai14s`__ はゲーム開始時の局面で必ず真ん中の __(1, 1) のみを最善手として選択__ しますが、ゲーム開始時の局面は 9 種類のすべての合法手が最善手なので __`ai_gt6`__ はその中から __ランダムで最善手を選択__ します。__最善手が複数存在__ する場合は、その中の __どの最善手を先頭に移動するか__ によって __枝狩りが行われるノードが変わる__ ので、その __効率が異なります__。`ai10s` と `ai14s` が選択する最善手を先頭に移動する move ordering のほうが、`ai_gt6` が選択する選択する最善手を先頭に移動する move ordering よりも効率が高くなるため、下記のような一見すると矛盾したように見える結果になります。

__最短の勝利を目指さない場合__

| | Scout | MTD(f) | MTD(f) mo |
|:--|--:|--:|--:|
|__`ai10s`__| 13562 | 20420 | 11188 |
|__`ai14s`__| 11609 | 19727 | 8323 |
|__`ai_gt6`__| 13383 | 19644 | 9947 |

__最短の勝利を目指す場合__

|| Scout | MTD(f) | MTD(f) mo |
|:--|--:|--:|--:|
|__`ai10s`__| 14508 | 25239 | 15115 |
|__`ai14s`__| 11698 | 24275 | 11974 |
|__`ai_gt6`__| 14419 | 24471 | 15564 |

下記は実行結果の中の __スカウト法を基準とした比率__ の部分をまとめた表です。

__最短の勝利を目指さない場合__

|| MTD(f) | MTD(f) mo |
|:--|--:|--:|
|__`ai10s`__| 151 % | 82 % |
|__`ai14s`__| 170 % | 72 % |
|__`ai_gt6`__| 147 % | 74 % |

__最短の勝利を目指す場合__

| | MTD(f) | MTD(f) mo |
|:--|--|--|
|__`ai10s`__| 174 % | 104 % |
|__`ai14s`__| 208 % | 102 % |
|__`ai_gt6`__| 170 % | 108 % |


〇× ゲームでは残念ながら最短の勝利を目指す場合の MTD(f) 法は常にスカウト法よりも効率が悪くなりますが、__最短の勝利を目指さない場合__ は、__move ordering を行う MTD(f) 法__ の方がいずれも __スカウト法よりも効率が良くなる__ ことがわかりました。最短の勝利を目指す場合に関しては、おそらく 〇× ゲームの __ゲーム木の深さが浅い__ ため、__null window search の効率が高くならない__ からではないかと思いますが、__最短の勝利を目指す場合__ でも、スカウト法と move ordering を行う MTD(f) 法の効率は __ほぼ同じ__ になります。

また、上記の結果から __move ordering は MTD(f) 法でも効率を高めるために有効である__ ことが確認できました。

[前回の記事](https://qiita.com/ysgeso/items/8bd4935a8ce670cebba0#%E6%9E%9D%E7%8B%A9%E3%82%8A%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%A8%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E6%B7%B1%E3%81%95%E3%81%AE%E9%96%A2%E4%BF%82%E3%81%AE%E8%80%83%E5%AF%9F)で説明したように、一般的に __ゲーム木がより深くなれば null window search の効率がより高くなります__。そのため、__チェスなど__ のより深いゲーム木の場合は、__move ordering を行なわない MTD(f) の効率がスカウト法よりも高くなるという事例がある__ ようです。例えば [An Algorithm Faster than NegaScout and SSS* in Practice](https://liacs.leidenuniv.nl/~plaata1/papers/hk.pdf) という論文では __チェスでは MTD(f) 法によってスカウト法に分類されるアルゴリズムよりも約 10 % 程効率が高くなった__ ことが確認されたとの報告があります。

なお、[Wikipedia の MTD(f) 法の記事](https://ja.wikipedia.org/wiki/MTD-f) では「しかし置換表に強く依存する事や、探索の非安定性などの問題が存在するので、 現在のチェスプログラムでは NegaScout 法もいまだに広く使われている」とあるので、スカウト法と MTD(f) 法のどちらが良いかについては意見が分かれているようです。

:::note
__探索の非安定性__（search instability）とは、同じノードに対して異なるウィンドウで αβ 値を計算した際に、矛盾した計算結果が得られることを表します。探索の非安定性は、本記事でこれまでに行なってきた、正確な評価値を計算できる __リーフノードの評価値を使って〇×ゲームのミニマックス値を計算する手法では発生しません__。

探索の非安定性は、それが発生する条件が満たされれば MTD(f) 法だけでなく、スカウト法でも発生するような気がします。そのため、探索の非安定性を理由に MTD(f) 法ではなくスカウト法を利用する場合があるという上記の Wikipedia の説明については、筆者はあまり納得できませんでした。この点については筆者はまだ勉強不足なので、詳しい方がいればコメントなどで補足していただけると大変助かります。

参考までに探索の非安定性の Chess Programming wiki のリンクを下記に示します。
:::

https://www.chessprogramming.org/Search_Instability

MTD(f) 法に限らず、__枝狩りを行うアルゴリズム__ は、__ゲーム木の性質によって効率が大きく変わります__。〇×ゲーム以外のゲーム木では、本記事の検証と異なる結果になる場合があるので、他のゲームで実装を行う場合は、__様々な枝狩りのアルゴリズムを実際に試して比較を行うことが重要__ となります。

# 今回の記事のまとめ

今回の記事では __推定したミニマックス値の精度と MTD(f) 法の効率の関係__ について説明しました。また、__スカウト 法と MTD(f) 法の比較による効率の検証__ を行ないました。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/248c2dcfc35f4a231dcc

[^1]:表には記載されていませんが、ミニマックス値の範囲の初期値は [$-∞$, $∞$] なので、最初の null window search では下界または上界の値が更新されてミニマックス値の範囲が必ず狭くなります