Pythonで〇×ゲームのAIを一から作成する　その168　MTD(f) 法の仕組みと実装

# 目次と前回の記事

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

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

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

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

util.py の説明に「現在は `gui_play` のみ定義されている」という間違いが説明されていたので修正しました。なお、過去の記事に遡って修正するのは大変すぎるので、そのままにしています。

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

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

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

# MTD(f) 法

今回の記事では __null window search__ を利用した、__スカウト法よりも効率が高い__ と言われている __MTD(f) 法__ というアルゴリズムを紹介します。

## 利用する記号

今回の記事では下記の記号を利用します。なお、[以前の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#%CE%B1%CE%B2-%E6%B3%95%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E6%84%8F%E5%91%B3%E3%81%AE%E3%81%8A%E3%81%95%E3%82%89%E3%81%84%E3%81%A8%E7%94%A8%E8%AA%9E%E3%81%AE%E4%BF%AE%E6%AD%A3) で __ミニマックス法__ で求めることができる __正確な評価値__ を __ミニマックス値__、__αβ 法__ で計算したミニマックス値の __範囲を表す可能性がある評価値__ の事を __αβ 値__ のように区別して表記すると説明しましたが、最近の記事ではそのことを忘れて αβ 値のことを評価値と記述していたようです。わかりづらいので改めて αβ 値という用語を利用したいと思います（余裕があれば過去の記事も修正したいと思います）。

|記号|意味|
|:--|:--|
|$\boldsymbol{N}$|MTD(f) 法でミニマックス値を計算するノード|
|$\boldsymbol{α}$|$N$ の αβ 値を計算する際の α 値の初期値 |
|$\boldsymbol{β}$|$N$ の αβ 値を計算する際の β 値の初期値 |
|($\boldsymbol{α}$, $\boldsymbol{β}$)| $N$ の αβ 値を計算する際のウィンドウ |
|__[下界, 上界]__| $N$ のミニマックス値の範囲 |

:::note
[以前の記事](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e#%E4%BB%8A%E5%9B%9E%E3%81%AE%E8%A8%98%E4%BA%8B%E3%81%A7%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B%E8%A8%98%E5%8F%B7)のノートで説明したように、数学では [1, 2] は 1 以上 2 以下のように、 端を含む範囲を [] の記号で囲って表記します。
:::

## MTD(f) 法の特徴

MTD(f) は Memory-enhanced Test Driver with node n and value f の略で、以下のような特徴を持ちます。

* αβ 法やスカウト法と異なり、__null window search のみ__ で __ミニマックス値を計算__ する
* __move ordering を行わない__ かわりに[^1]__$\boldsymbol{N}$ のミニマックス値を推定__ してから計算を行う
* __置換表の利用を前提__ とする

このアルゴリズムで効率が高くなる理由については後で説明します。

:::note
MTD(f) は MT を利用したアルゴリズムの一つで、MT という名前は [An Algorithm Faster than NegaScout and SSS* in Practice](https://liacs.leidenuniv.nl/~plaata1/papers/hk.pdf) という論文で以下のような理由から命名されたようです。

null window search などによってミニマックス値が特定の値よりも大きいかどうかを判定することをテスト（test）と呼びます。また、置換表が過去の結果を記録（memory）することから、置換表によって効率を高めた（enhance）テストのことを MT(memory enhanced test)と命名したとのことです。

MTD(f) はノード n の ミニマックス値を f と推定して MT を行うアルゴリズムなのでそのように命名されたようです。なお、MTD の D はドライバ（driver）の略で、コンピューターでは何かを動作させるシステムのことドライバと呼びます。
:::

参考までに MTD(f) 法の Wikipedia、Chess Programming wiki、論文のリンクを示します。

https://ja.wikipedia.org/wiki/MTD-f

https://www.chessprogramming.org/MTD(f)

https://arxiv.org/abs/1404.1511

## MTD(f) 法の考え方とアルゴリズム

MTD(f) は以下のような考え方で __null window search を複数回行う__ ことで $N$ のミニマックス値を計算する手法です。ただし、__評価値として整数のみが計算__ されるものとします。

* __最初はミニマックス値は不明__ なので、__ミニマックス値の範囲__ を [$\boldsymbol{-∞}$, $\boldsymbol{∞}$]（下界と上界を負の無限大と正の無限大）とする
* __ミニマックス値の範囲を狭める__ ことができる __null window search__ を行う
* 1 回の null window search で __ミニマックス値の範囲が狭まる__ ので、null window search を __複数回繰り返す__ ことでいつかは __下界と上界が等しくなり__、__正確なミニマックス値を計算__ することができる

MTD(f) の __具体的なアルゴリズム__ は以下の通りです。このアルゴリズムでミニマックス値を求めることができる理由について少し考えてみて下さい。

1. 何らかの方法で $\boldsymbol{N}$ の __ミニマックス値の近似値を推定__ し、その値を $\boldsymbol{f}$ とする。ただし、$\boldsymbol{f}$ __は整数__ とする
2. $\boldsymbol{N}$ の __ミニマックス値の範囲__ を [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] とする
3. ミニマックス値の __下界と上界が等しくなる__（ミニマックス値の範囲が 1 つの値になる）__まで__ 下記の __処理を繰り返す__
    1. $\boldsymbol{β}$ を __下記のように設定__ する
        * $\boldsymbol{f}$ が __下界と等しい場合__ は $\boldsymbol{β = f + 1}$ とする
        * $\boldsymbol{f}$ が __下界と等しくない場合__ は $\boldsymbol{β = f}$ とする
    2. $\boldsymbol{α = β - 1}$ とした ($\boldsymbol{β - 1}$, $\boldsymbol{β}$) という、__ウィンドウ幅が 1 の null window search__ で $N$ の __αβ 値を計算__ し、その値を $\boldsymbol{g}$ とする
    3. 上記で計算した $\boldsymbol{g}$ __の値__ に応じて __下界または上界__ を下記のように __更新する__
        * $\boldsymbol{β ≦ g}$ の場合は __fail high__ なので __下界を $\boldsymbol{g}$ で更新__ する
        * それ以外（$\boldsymbol{g < β}$）の場合は __fail low__ なので __上界を $\boldsymbol{g}$ で更新__ する
    4. $\boldsymbol{f}$ __を__ $\boldsymbol{g}$ __で更新__ する
4. $\boldsymbol{f}$ が $N$ の __ミニマックス値として計算__ される

:::note
上記の __手順 1__ で $\boldsymbol{f}$ __を整数とした理由__ は以下の通りです。

* $N$ のミニマックス値として負の無限大や正の無限大を推定するのは明らかに変
* $f$ が整数でない場合は、手順 3-2 の ($β - 1$, $β$) というウィンドウの中に評価値として計算される可能性がある整数の値が含まれてしまうため、[以前の記事](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc#null-window-search-%E3%81%AE%E6%9D%A1%E4%BB%B6)で説明したように null window search ではなくなる
* 下記のノートで説明するが、($β - 1$, $β$) というウィンドウの中に評価値として計算される可能性がある値が含まれてしまうと、手順 3-3 で $\boldsymbol{g < β}$ __の場合__ に __exact value となる可能性が生じてしまう__
:::

:::note
上記の手順 3-3 で、$\boldsymbol{g < β}$ の場合は fail low となる理由は以下の通りです。

* 評価値として整数のみが計算されるので $g$ は整数である
* 手順 1 の $f$ は整数で、手順 3-4 で $f$ は $g$ で更新されるので $f$ は常に整数である
* 従って、手順 3-1 で計算される $β$ も常に整数である
* ($β - 1$, $β$) というウィンドウの範囲に評価値として計算される整数の値は存在しないので、$g$ が exact value の範囲になることはない
* 従って $g$ が fail high でない $\boldsymbol{g < β}$ の場合は fail low となる
:::

:::note
$N$ のミニマックス値を推定する手法としては、まだ本記事で紹介していない反復深化を利用するのが一般的だと思います。
:::

## MTD(f) 法で行なわれる計算の分類

上記のアルゴリズムの __手順 3-2 の null window search__ の __ウィンドウ__ は、$\boldsymbol{f}$ とミニマックス値の __上界__、__下界__ の値 __によって決まります__。そこで、[前回の記事](https://qiita.com/ysgeso/items/d444cd3b3336e5786882#%E8%AA%AC%E6%98%8E%E3%81%A7%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B%E8%A8%98%E5%8F%B7%E7%AD%89%E3%81%AE%E8%AA%AC%E6%98%8E)と同様に、__手順 3 で行なわれる処理__ を、$f$ の分類、ミニマックス値の上界、下界の __3 種類の情報の組み合わせで分類__ して説明します。その際に __3 種類の情報を下記のように記述__ します。

$f$ の分類, [下界, 上界]

## 最初の null window search の分類

MTD(f) 法では最初は __ミニマックス値の範囲__ を [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] __として処理を始めます__。また、$\boldsymbol{N}$ の __ミニマックス値が__ $\boldsymbol{s}$ の場合に、__手順 1__ で $N$ の __ミニマックス値として推定した__ $\boldsymbol{f}$ は __以下の 3 通りの場合__ があります。

* $f < s$
* $f = s$
* $f > s$

従って、__最初の null window search__ で行われる処理は下記の __3 種類に分類__ されます。

* $f < s$, [$-∞$, $∞$]
* $f = s$, [$-∞$, $∞$]
* $f > s$, [$-∞$, $∞$]

それぞれの場合で行われる処理について検証します。

## f < s, [-∞, ∞] の場合に行なわれる処理

この分類の場合は、__手順 3__ で下記のような処理が行われます。

* $\boldsymbol{f}$ は __下界の値__ である負の無限大と __等しくない__ ので、__手順 3-1__ で $\boldsymbol{β = f}$ となる
* __手順 3-2__ で ($β - 1$, $β$)、すなわち ($\boldsymbol{f - 1}$, $\boldsymbol{f}$) __をウィンドウ__ とした null window search で $N$ の αβ 値である $\boldsymbol{g}$ __を計算する__

$\boldsymbol{β = f < s}$ なので $\boldsymbol{g}$ は __fail high の範囲__ となります。従って $\boldsymbol{β = f ≦ g}$ となります。

また、$g$ が __fail high の範囲の場合__ は、__ミニマックス値 $\boldsymbol{s}$ は__ $\boldsymbol{g}$ __以上__ であるという意味になるので、$\boldsymbol{g ≦ s}$ となります。

上記から、$\boldsymbol{g}$ は $\boldsymbol{f ≦ g ≦ s}$ __を満たす整数__ となります。

次の __手順 3-3__ では $g$ は __fail high の範囲__（$\boldsymbol{β ≦ g}$）なので、__下界が__ $\boldsymbol{g}$ __で更新__ されます。

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

:::note warn
$\boldsymbol{f < s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合は __null window search の結果、以下の処理__ が行われる。

* $\boldsymbol{f}$ が $\boldsymbol{f ≦ g ≦ s}$ を __満たす整数__ $\boldsymbol{g}$ __で更新__ される
* 従って、__更新後の__ $\boldsymbol{f}$ は __更新前の__ $\boldsymbol{f}$ __以上の値__ になる 
* __ミニマックス値の範囲__ が [$―∞$, $∞$] から [$\boldsymbol{f}$, $\boldsymbol{∞}$] になり、__必ず狭くなる__
:::

記号だけの説明ではわかりづらいと思いますので、具体例を挙げて説明します。

$f = 0$、$s = 5$ の場合は、手順 3-1 で $β = 0$ となり、手順 3-2 で行なわれる null window search のウィンドウは下図のように (-1, 0) となります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6cef9905-5b2c-46e9-a860-d3e05623b7cf.png" width="500">

上記の null window search の計算結果である $g$ は $f ≦ g ≦ s$ を満たす整数、すなわち __0 以上 5 以下の整数__ が計算されます。例えば 2 が計算された場合は $\boldsymbol{f}$ と __下界__ は __2 で更新される__ ので、下図のようになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a2b46352-9022-4106-a166-39aff63854fc.png" width="500">

手順 3-3 を計算した結果、__ミニマックス値の範囲__ は  [$\boldsymbol{f}$, $\boldsymbol{∞}$] となりますが、__上界と下界は等しくない__ ので、__次の null window search が行なわれます__。その際に、__更新された__ $\boldsymbol{f}$ __の値__ によって下記の __2 通りに分類する__ ことができるので、それぞれの場合について検証します。

* $f < s$, [$f$, $∞$]
* $f = s$, [$f$, $∞$]

### f < s, [f, ∞] の場合

この分類の場合は、手順 3 で下記のような処理が行われます。

* $\boldsymbol{f =}$ __下界__ なので、手順 3-1 で $\boldsymbol{β = f + 1}$ となる
* 手順 3-2 で ($β - 1$, $β$)、すなわち ($\boldsymbol{f}$, $\boldsymbol{f + 1}$) __をウィンドウ__ とした null window search で $N$ の αβ 値である $\boldsymbol{g}$ を計算する

下記の理由から $\boldsymbol{g}$ が __fail low や exact value となることはない__ ので、$\boldsymbol{g}$ は必ず __fail high の範囲__ となります。従って $\boldsymbol{β = f + 1 ≦ g}$ となります。

* 以下の理由から $\boldsymbol{g}$ が __fail low の範囲になることはない__
    * $\boldsymbol{g}$ __が fail low__ の場合は $g ≦ α$、すなわち $\boldsymbol{g ≦ f}$ である
    * $\boldsymbol{g}$ __が fail low__ の場合は __ミニマックス値 $\boldsymbol{s}$ が $\boldsymbol{g}$ 以下__ であることを意味するので $\boldsymbol{s ≦ g}$ である
    * 上記から $\boldsymbol{g}$ __が fail low__ の場合は $\boldsymbol{s ≦ g ≦ f}$ となるが、これは $\boldsymbol{f < s}$ __という前提に反する__
* 以下の理由から $\boldsymbol{g}$ __が exact value の範囲になることはない__
    * $\boldsymbol{f}$ __は整数__ なので、($f$, $f + 1$) という __ウィンドウの範囲内__ に __評価値がとりうる整数の値は存在しない__
    * 従って exact value となる $f < g < f + 1$ を満たす $g$ が計算されることはない

また、先程検証した $f < s$, [$-∞$, $∞$] の場合と同じ理由で $\boldsymbol{g ≦ s}$ となるので、$\boldsymbol{g}$ は $\boldsymbol{f + 1 ≦ g ≦ s}$ __を満たす整数__ となります。

次の __手順 3-3__ では $g$ は __fail high の範囲__（$\boldsymbol{β ≦ g}$）なので、__下界が__ $\boldsymbol{g}$ __で更新__ されます。その結果、__ミニマックス値の範囲__ は [$f$, $∞$] から [$\boldsymbol{g}$, $\boldsymbol{∞}$] __に更新__ されますが、$f < f + 1 ≦ g$ なので、$\boldsymbol{f < g}$ となるため、更新後の __ミニマックス値の範囲は必ず狭くなります__。

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

:::note warn
$\boldsymbol{f < s}$, [$\boldsymbol{f}$, $\boldsymbol{∞}$] の場合は __null window search の結果、以下の処理__ が行われる。

* $\boldsymbol{f}$ が $\boldsymbol{f < g ≦ s}$ を __満たす整数__ $\boldsymbol{g}$ __で更新__ される
* 従って、__更新後の__ $\boldsymbol{f}$ は __更新前の__ $\boldsymbol{f}$ __よりも大きく__ なる 
* __ミニマックス値の範囲__ が [$f$, $∞$] から [$\boldsymbol{g}$, $\boldsymbol{∞}$] になり、__必ず狭くなる__
:::

具体例を挙げます。$f = 2 < s = 5$, [$2$, $∞$] の場合は、手順 3-1 で $β = 3$ となり、手順 3-2 で行なわれる null window search のウィンドウは下図のように (2, 3) となります。

なお、下記の図から __手順 3-1__ で $\boldsymbol{f =}$ __下界__ の場合に $\boldsymbol{β = f + 1}$ __とした理由__ が、__ウィンドウ__ をミニマックス値の範囲内の __左端に合わせるため__ であることがわかります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/eca0c116-75c3-4b40-9f21-00dc404aa367.png" width="500">

上記の null window search の計算結果は $f + 1 ≦ g ≦ s$ を満たす整数、すなわち __3 以上 5 以下の整数が計算__ されます。例えば 3 が計算された場合は $\boldsymbol{f}$ と __下界__ は __3 で更新される__ ので、下図のようになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/37373120-ac0b-44a4-a939-5bbe602df2bd.png" width="500">

上記を計算した結果、__ミニマックス値の範囲__ は  [$\boldsymbol{f}$, $\boldsymbol{∞}$] となりますが、__上界と下界は等しくない__ ので、__次の null window search が行なわれます__。その際に、__更新された__ $\boldsymbol{f}$ __の値__ によって下記の __2 通りに分類する__ ことができます。

* $f < s$, [$f$, $∞$]
* $f = s$, [$f$, $∞$]

__前者__ は今回行った null window search と __同じ分類__ になります。そのため、$\boldsymbol{f < s}$, [$\boldsymbol{f}$, $\boldsymbol{∞}$] という分類の null window search が無限に繰り返される可能性があると思う人がいるかもしれませんが、上記で示したように __更新後の__ $\boldsymbol{f}$ は必ず __更新前の値よりも大きく__ なります。また、更新後の $f$ の __最大値は__ $\boldsymbol{s}$ なので無限に繰り返されることはなく、__いつかは__ $\boldsymbol{f = s}$, [$\boldsymbol{f}$, $\boldsymbol{∞}$] という __後者の分類の null window search が行なわれます__。

:::note
上記で検証したように、$f < s$, [$f$, $∞$] の分類の null window search では、__ミニマックス値の範囲が必ず狭くなる__ ため、__無限に繰り返すことはできない__ と説明することもできます。
:::

__後者__ は先程検証した $\boldsymbol{f < s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の次で行なわれる null window search の __2 つ目の分類と同じ__ です。そこで、次はこの後者の分類を検証することにします。 

### f = s, [f, ∞] の場合

この分類の場合は、手順 3 で下記のような処理が行われます。

* $\boldsymbol{f =}$ __下界__ で $\boldsymbol{f = s}$ なので、手順 3-1 で $\boldsymbol{β = f + 1 = s + 1}$ となる
* 手順 3-2 で ($β - 1$, $β$)、すなわち ($\boldsymbol{s}$, $\boldsymbol{s + 1}$) __をウィンドウ__ とした null window search で $N$ の αβ 値である $\boldsymbol{g}$ を計算する

$\boldsymbol{α = s}$ なので $\boldsymbol{g}$ は必ず __fail low の範囲__ となります。従って $\boldsymbol{g ≦ α = s}$ となります。

また、$g$ が __fail low の範囲の場合__ は、__ミニマックス値 $\boldsymbol{s}$ は__ $\boldsymbol{g}$ __以下__ であるという意味になるので、$\boldsymbol{s ≦ g}$ となります。

$\boldsymbol{g ≦ s}$ と $\boldsymbol{s ≦ g}$ を同時に満たす $g$ は $s$ しかないので、$\boldsymbol{g = s}$ となります。

次の __手順 3-3__ では $g$ は __fail low の範囲__（$\boldsymbol{g < β}$）なので、__上界が__ $\boldsymbol{g}$ __で更新__ されます。その結果、__ミニマックス値の範囲__ は [$s$, $∞$] から [$\boldsymbol{s}$, $\boldsymbol{s}$] __に更新__ されて __上界と下界が等しくなりまる__。従って、手順 3 の __繰り返し処理が終了__ し、手順 4 で $\boldsymbol{f}$ に $N$ の __ミニマックス値が計算__ されます。

具体例を挙げます。$f = s = 5$, [$5$, $∞$] の場合は、手順 3-1 で $β = 6$ となり、手順 3-2 で行なわれる null window search のウィンドウは下図のように (5, 6) となります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/02e84f11-2bef-4fd1-b639-104fcf4b7912.png" width="500">

上記の null window search の計算結果は下図のように $f = s = 5$ のまま変化しませんが、下界と上界が等しくなり、$\boldsymbol{f}$ __に正しいミニマックス値__ である __5 が計算__ されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9f989c3c-06f2-4755-bdc7-8b9bc6812ef6.png" width="500">

### 手順 1 で f < s の場合に行われる処理のまとめ

上記から、__手順 1__ で $\boldsymbol{f < s}$ の場合に行なわれる処理は、以下の表のようになります。

下記の表では $\boldsymbol{n}$ __回の null window search__ が行なわれた場合の例で、__手順 1__ で計算された $\boldsymbol{f}$ を $\boldsymbol{f_0}$、$\boldsymbol{i}$ __回目の null window search__ によって更新された $\boldsymbol{f}$ を $\boldsymbol{f_i}$ と表記します。また、「MM の範囲」の列は αβ 値の計算後に更新された __ミニマックス値の範囲__ を表します。

|回数|分類|ウィンドウ|αβ 値|αβ の範囲|MM の範囲|
|:-:|:--|:--|:--|:--|:--|
|1|$f < s$, [$-∞$, $∞$]|($f_0 - 1$, $f_0$)| $f_1$|fail high|[$f_1$, $∞$]|
|2|$f < s$, [$f$, $∞$]|($f_1$, $f_1 + 1$)|$f_2$|fail high|[$f_2$, $∞$]|
|3|$f < s$, [$f$, $∞$]|($f_2$, $f_2 + 1$)|$f_3$|fail high|[$f_3$, $∞$]|
|4|$f < s$, [$f$, $∞$]|($f_3$, $f_3 + 1$)|$f_4$|fail high|[$f_4$, $∞$]|
|・・・|・・・|・・・|・・・|・・・|・・・|
|$n-1$|$f < s$, [$f$, $∞$]|($f_{n-2}$, $f_{n-2} + 1$)|$f_{n-1}=s$|fail high|[$f_{n-1}$, $∞$]<br>= [$s$, $∞$]|
|$n$|$f = s$, [$f$, $∞$]|($f_{n-1}$, $f_{n-1} + 1$)|$f_n=s$|fail low|[$f_{n-1}$, $f_n$] <br>= [$s$, $s$]|

ただし、$\boldsymbol{f = f_0 ≦ f_1 < f_2 < f_3 < ・・・ < f_{n-1} = f_{n} = s}$ となります。

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

:::note warn
__手順 1__ で計算される $f$ が $\boldsymbol{f < s}$ の場合に、$\boldsymbol{n}$ __回の null window search__ が行なわれた場合は、以下の処理が行われる。

* __null window search が行われるたび__ に下記のように __ミニマックス値の範囲が狭まっていく__ ことでミニマックス値を求めることができる
* $\boldsymbol{n - 1}$ __回目まで__ の null window search では、$\boldsymbol{f}$ と __ミニマックス値の下界__ が $\boldsymbol{s}$ __に向かって増えていく__ ことでミニマックス値の範囲が狭まる
* ただし、__初回のみ__ $f$ が __変化しない場合__ があるが、その場合でも下界が $-∞$ から $f$ に更新されるので __ミニマックス値の範囲は狭まる__
* $\boldsymbol{n - 1}$ __回目__ の null window search によって $\boldsymbol{f}$ がミニマックス値である $\boldsymbol{s}$ __に更新される__ が、その時点ではミニマックス値の __上界が__ $\boldsymbol{∞}$ なので __もう一回 null window search を行う必要がある__
* __最後の null window search__ では下界は変化せず、__上界が__ $\boldsymbol{s}$ __に更新__ されることで __ミニマックス値が計算される__
:::

### 手順 1 で f < s の場合の処理の効率

__手順 1__ で $\boldsymbol{f < s}$ の場合に行なわれる __処理の効率__ は、__何回目の null window search__ で αβ 値に $\boldsymbol{s}$ __が計算されるか__ によって異なります。

__最も効率が良い__ のが __初回の null window search で__ $\boldsymbol{s}$ __が計算された場合__ で、__2 回目__ の null window search で __ミニマックス値が計算される__ ので、__最低 2 回の null window search が必要__ となります。

例えば $f_0 = 0$, $s = 5$ の場合に、初回の null window search で 5 が計算された場合は以下のようになります。

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

また、__2 回目から__ $\boldsymbol{n - 1}$ __回目まで__ の null window search では 必ず $\boldsymbol{f}$ __が最低でも 1 ずつ増える__ ため、初回と $n$ 回目で $f$ が増えない場合を加えると、最大で $\boldsymbol{s - f + 2}$ __回__ の null window search 行なわれます。

例えば $f_0 = 0$, $s = 5$ の場合で最悪の場合は以下のように、$5 - 0 + 2 = 7$ 回の null window search が必要になります。

|回数|分類|ウィンドウ|αβ 値|αβ の範囲|MM の範囲|
|:-:|:--|:--|:--|:--|:--|
|1|$f < s$, [$-∞$, $∞$]| ($-1$, $0$)|$f_1 = 0$|fail high|[$0$, $∞$]|
|2|$f < s$, [$0$, $∞$]|($-1$, $0$)| $f_2 = 1$|fail high|[$1$, $∞$]|
|3|$f < s$, [$0$, $∞$]|($-1$, $0$)| $f_3 = 2$|fail high|[$2$, $∞$]|
|4|$f < s$, [$0$, $∞$]|($-1$, $0$)| $f_4 = 3$|fail high|[$3$, $∞$]|
|5|$f < s$, [$0$, $∞$]|($-1$, $0$)| $f_5 = 4$|fail high|[$4$, $∞$]|
|6|$f < s$, [$0$, $∞$]|($-1$, $0$)| $f_6 = s = 5$|fail high|[$5$, $∞$]|
|7|$f = s$, [$0$, $∞$]|($-1$, $0$)| $f_7 = s = 5$|fail low|[$5$, $5$]|

上記から __以下の順で null window search が行われる__ ことがわかります。

* $f < s$, [$-∞$, $∞$] の分類が __1 回__
* $f < s$, [$f$, $∞$] の分類が __0 ～__ $\boldsymbol{s - f}$ __回__。$f_i$ が $s$ に向けて毎回増えていく
* $f = s$, [$f$, $∞$] の分類が __1 回__

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

:::note warn
手順 1 で計算される $f$ が $f < s$ の場合に行なわれる処理は以下のようになる。

* __最善で 2 回__ の null window search が必要となる
* __最悪で__ $\boldsymbol{s - f + 2}$ __回__ の null window search が必要となる
* 従って、$N$ のミニマックス値の推定値 $\boldsymbol{f}$ __の精度が高い程__ MTD(f) の __処理の効率が高くなる__ ことが期待できる
:::

具体例として $\boldsymbol{f_0 = 0, f_1=2, f_2=3, f_3=5, f_4=5、s = 5}$ の場合の処理を下図に並べます。$f$ と下界が 5 に向かって増えていき、最後に上界が 5 となる様子をして下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/09b8b024-134f-4354-9c39-d2f9dc33240c.png" width="500">

## f = s, [-∞, ∞] の場合に行なわれる処理

__最初の null window search の分類__ が $\boldsymbol{f = s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合の処理を検証します。

この場合は、下記のような処理が行われます。

* $\boldsymbol{f}$ は __下界の値__ である負の無限大と __等しくない__ ので、__手順 3-1__ で $\boldsymbol{β = f = s}$ となる
* __手順 3-2__ で ($β - 1$, $β$)、すなわち ($\boldsymbol{s - 1}$, $\boldsymbol{s}$) __をウィンドウ__ とした null window search で $N$ の αβ 値である $\boldsymbol{g}$ __を計算する__

$\boldsymbol{β = s}$ なので $\boldsymbol{g}$ は必ず __fail high の範囲__ となります。従って $\boldsymbol{β = s ≦ g}$ となります。

また、$g$ が __fail high の範囲の場合__ は、__ミニマックス値 $\boldsymbol{s}$ は__ $\boldsymbol{g}$ __以上__ であるという意味になるので、$\boldsymbol{g ≦ s}$ となります。

$\boldsymbol{s ≦ g}$ と $\boldsymbol{g ≦ s}$ を同時に満たす $g$ は $s$ しかないので、$\boldsymbol{g = s}$ となります。

次の __手順 3-3__ では $g$ は __fail high 範囲__（$\boldsymbol{β ≦ g}$）なので、__下界が__ $\boldsymbol{g = s}$ __で更新__ されます。その結果、__ミニマックス値の範囲__ は [$-∞$, $∞$] から [$\boldsymbol{s}$, $\boldsymbol{∞}$] __に更新__ されます。

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

:::note warn
$\boldsymbol{f = s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合は __null window search の結果、以下の処理__ が行われる。

* $\boldsymbol{f}$ が $\boldsymbol{s}$ __で更新__ される
* __ミニマックス値の範囲__ が [$-∞$, $∞$] から [$\boldsymbol{s}$, $\boldsymbol{∞}$] になり、__必ず狭くなる__
:::

__次の null window search__ の分類は $\boldsymbol{f=s}$, [$\boldsymbol{f}$, $\boldsymbol{∞}$] となりますが、__この分類は先程検証済み__ です。従って、$\boldsymbol{f = s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合は下記の表のように、__必ず 2 回の null window search__ が行なわれます。

|回数|分類|ウィンドウ|αβ 値|αβ の範囲|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$]|

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

:::note warn
手順 1 で計算される $f$ が $\boldsymbol{f = s}$ の場合に行なわれる処理は以下のようになる。

* 1 回目の null window search でミニマックス値の範囲が [$s$, $∞$] になる
* 2 回目の null window search でミニマックス値の範囲が [$s$, $s$] になる
* 従って __必ず 2 回__ の null window search が行われる
:::

## f > s, [-∞, ∞] の場合に行なわれる処理

__最初の null window search の分類__ が $\boldsymbol{f > s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合の __処理の検証__ は、$\boldsymbol{f < s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合の __処理の検証とほぼ同じ__ ですが、__少しだけ異なる__ 点があります。

この分類の場合は、__手順 3__ で下記のような処理が行われます。

* $\boldsymbol{f}$ は __下界の値__ である負の無限大と __等しくない__ ので、__手順 3-1__ で $\boldsymbol{β = f}$ となる
* __手順 3-2__ で ($β - 1$, $β$)、すなわち ($\boldsymbol{f - 1}$, $\boldsymbol{f}$) __をウィンドウ__ とした null window search で $N$ の αβ 値である $\boldsymbol{g}$ __を計算する__

$\boldsymbol{f}$ と $\boldsymbol{s}$ は __整数__ で $f > s$ なので、$\boldsymbol{f - 1 ≧ s}$ となります。$α = f - 1$ なので $\boldsymbol{s ≦ α}$ となるので、$\boldsymbol{g}$ は必ず __fail low の範囲__ となります。従って $\boldsymbol{g ≦ α = f - 1}$ となります。

また、$g$ が __fail low の範囲の場合__ は、__ミニマックス値 $\boldsymbol{s}$ は__ $\boldsymbol{g}$ __以下__ であるという意味になるので、$\boldsymbol{s ≦ g}$ となります。

上記から、$\boldsymbol{g}$ は $\boldsymbol{s ≦ g ≦ f - 1}$ __を満たす整数__ となります。

:::note
$\boldsymbol{f < s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合では、$\boldsymbol{f ≦ g ≦ s}$ だったので、こちらの場合は $\boldsymbol{s ≦ g ≦ f}$ となると思った人がいるかもしれませんが、実際には $\boldsymbol{s ≦ g ≦ f - 1}$ となる点に注意して下さい。
::: 

次の __手順 3-3__ では $g$ は __fail low の範囲__（$\boldsymbol{g < β}$）なので、__上界が__ $\boldsymbol{g}$ __で更新__ されます。

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

:::note warn
$\boldsymbol{f > s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合は __null window search の結果、以下の処理__ が行われる。

* $\boldsymbol{f}$ が $\boldsymbol{s ≦ g ≦ f - 1}$ を __満たす整数__ $\boldsymbol{g}$ __で更新__ される
* 従って、__更新後の__ $\boldsymbol{f}$ は __更新前の__ $\boldsymbol{f}$ __より小さな値__ になる 
* __ミニマックス値の範囲__ が [$―∞$, $∞$] から [$\boldsymbol{-∞}$, $\boldsymbol{f}$] になり、__必ず狭くなる__
:::

:::note
$f &lt; s$, [$-∞$, $∞$] の場合は更新後の $f$ は更新前の $f$ __以上の値__ になりますが、$f > s$, [$-∞$, $∞$] の場合は __更新前の__ $\boldsymbol{f}$ は更新前の $f$ 以下ではなく、$\boldsymbol{f}$ __より小さな値になる点が異なります__。
:::

次の null window search は、更新された $f$ の値によって下記の 2 通りに分類することができます。

* $f > s$, [$-∞$, $f$]
* $f = s$, [$-∞$, $f$]

### 手順 1 で f > s の場合に行われる処理のまとめ

上記のそれぞれの場合で行なわれる処理は、先程検証した「$f < s$, [$f$, $∞$]」、「$f = s$, [$f$, $∞$]」と __同様__ なので、その検証は省略し、結果だけをまとめることにします。余裕がある方は実際に検証してみて下さい。

__手順 1__ で $\boldsymbol{f < s}$ の場合に行なわれる処理は以下の表のようになります。

|回数|分類|ウィンドウ|αβ 値|αβ 範囲|MM の範囲|
|:-:|:--|:--|:--|:--|:--|
|1|$f > s$, [$-∞$, $∞$]|($f_0 - 1$, $f_0$)| $f_1$|fail low|[$-∞$, $f_1$]|
|2|$f > s$, [$-∞$, $f$]|($f_1 - 1$, $f_1$)|$f_2$|fail low|[$-∞$, $f_2$]|
|3|$f > s$, [$-∞$, $f$]|($f_2 - 1$, $f_2$)|$f_3$|fail low|[$-∞$, $f_3$]|
|4|$f > s$, [$-∞$, $f$]|($f_3 - 1$, $f_3$)|$f_4$|fail low|[$-∞$, $f_4$]|
|・・・|・・・|・・・|・・・|・・・|・・・|
|$n-1$|$f > s$, [$-∞$, $f$]|($f_{n-2} - 1$, $f_{n-2}$)|$f_{n-1}=s$|fail low|[$-∞$, $f_{n-1}$] <br>= [$-∞$, $s$]|
|$n$|$f = s$, [$-∞$, $f$]|($f_{n-1} - 1$, $f_1$)|$f_n=s$|fail high|[$f_{n}$, $f_{n-1}$] <br>= [$s$, $s$]|

ただし、$\boldsymbol{f = f_0 > f_1 > f_2 > f_3 > ・・・ > f_{n-1} = f_{n} = s}$ となります。

:::note
$\boldsymbol{f < s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合は $f = f_0 ≦ f_1$ でしたが、こちらでは $f = f_0 > f_1$ のように $≧$ ではなく $>$ となっている点が異なります。
:::

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

:::note warn
__手順 1__ で計算される $f$ が $\boldsymbol{f > s}$ の場合に、$\boldsymbol{n}$ __回の null window search__ が行なわれた場合は、以下の処理が行われる。

* __null window search が行われるたび__ に下記のように __ミニマックス値の範囲が狭まっていく__ ことでミニマックス値を求めることができる
* $\boldsymbol{n - 1}$ __回目まで__ の null window search では、$\boldsymbol{f}$ と __ミニマックス値の上界__ が $\boldsymbol{s}$ __に向かって減っていく__ ことでミニマックス値の範囲が狭まる
* $\boldsymbol{n - 1}$ __回目__ の null window search によって $\boldsymbol{f}$ がミニマックス値である $\boldsymbol{s}$ __に更新される__ が、その時点ではミニマックス値の __下界が__ $\boldsymbol{∞}$ なので __もう一回 null window search を行う必要がある__
* __最後の null window search のみ__ 上界は変化せず、__下界が__ $\boldsymbol{s}$ __に更新__ されることで __ミニマックス値が計算される__
:::

また、以下の順で null window search が行われます。

* $f > s$, [$-∞$, $∞$] の分類が 1 回
* $f > s$, [$―∞$, $f$] の分類が __0 ～__ $\boldsymbol{f - s - 1}$ __回__。$f_i$ が $s$ に向けて毎回減って行く
* $f = s$, [$-∞$, $f$] の分類が 1 回

:::note
$\boldsymbol{f < s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] の場合と異なり、最初の null window search の αβ 値は $f$ 未満になるので、$f > s$, [$―∞$, $f$] の分類の回数は 0 ~ $f - s$ 回ではなく、__0 ～__ $\boldsymbol{f - s - 1}$ 回となります。
:::

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

:::note warn
手順 1 で計算される $f$ が $\boldsymbol{f > s}$ の場合に行なわれる処理は以下のようになる。

* __最善で 2 回__ の null window search が必要となる
* __最悪で__ $\boldsymbol{f - s + 1}$ __回__ の null window search が必要となる
* 従って、$N$ のミニマックス値の推定値 $\boldsymbol{f}$ __の精度が高い程__ MTD(f) の __処理の効率が高くなる__ ことが期待できる
:::

:::note
細かい話になりますが、手順 1 で計算される $f$ が $f > s$ の場合は、$f = s + 1$ が計算された場合でも常に最も効率が良い 2 回の null window search が行なわれます。
:::

## MTD(f) 法の効率

__null window search__ は ($-∞$, $∞$) のウィンドウで計算する αβ 法よりも __枝狩りの効率が大幅に高い__ ので、__少ない回数の null window search__ であれば、__複数回行っても__ ($-∞$, $∞$) のウィンドウの __αβ 法よりも短い時間で計算__ を行うことができる __可能性が高くなります__。

MTD(f) 法では __手順 1__ で計算される $\boldsymbol{f}$ __の値__ によって __以下の表の回数__ の null window search が行なわれます。

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

上記の表から __正確なミニマックス値を計算できた場合__ は、MTD(f) 法で __最も効率が高い 2 回の null window search__ でミニマックス値を計算することができ、そうでない場合は $|\boldsymbol{f - s}|$[^2]が大きいほど null window search の __回数が増える可能性が高くなる__ ことがわかります。従って、MTD(f) 法では手順 1 で計算される $\boldsymbol{f}$ __の精度が高いことが非常に重要__ となります。

また、MTD(f) 法では、__同じ__ $\boldsymbol{N}$ に対して __異なるウィンドウで複数回の αβ 値を計算__ するので、__同じ子孫ノードに対して何度も αβ 値を計算__ することになります。そのため、__置換表を利用__ することで __効率を大幅に向上させることが期待できます__。

上記に関する MTD(f) 法の効率の検証については、次回の記事で行います。

## `ai_mtdf` の実装

MTD(f) のアルゴリズムで着手を選択する __`ai_mtdf`__ という __関数を定義__ する事にします。MTD(f) で行う null window search は __`ai_abs_all` 内で定義__ されているローカル関数 __`ab_search` をそのまま利用できる__ ので、`ai_abs_all` を下記のプログラムのように修正して `ai_mtdf` を定義することにします。

なお、MTD(f) 法は置換表を利用することが前提のアルゴリズムですが、置換表を利用しない場合と比較できるように、置換表の利用の有無を `ai_abs_all` と同様に選択できるようにします。また、[MTD(f) 法の論文](https://arxiv.org/abs/1404.1511)では move ordering を行っていませんが move ordering を行なった場合と比較できるように move ordering の有無も選択できるようにします。

* __6 行目__：関数名を `ai_mtdf` に修正する
* __7 行目__：手順 1 の $N$ の推定値である $f$ を代入するための仮引数 `f` を、デフォルト値を 0 とするデフォルト引数として追加する
* __10、11 行目__：ミニマックス値の下界と上界を表すローカル変数 `lbound` と `ubound` を初期化する。先程のアルゴリズムの説明ではそれぞれの初期値を負の無限大と正の無限大としたが、`init_ab` が `True` の場合は評価値の最小値と最大値を設定する。なお、`lower_bound` と `upper_bound` という変数はローカル関数 `ab_search` 内で別の用途で利用しているのでそれらとは異なる名前とした
* __13 行目__：これから行う複数回の null window search で利用する置換表を表す `tt` を空の dict で初期化する
* __14 行目__：下界と上界が等しくなるまで 15 ~ 20 行目の処理を繰り返す
* __15 行目__：手順 3-1 の $β$ を計算する
* __16 行目__：手順 3-2 の null window search を行う。手順 3-2 では更新前の $f$ と更新後の $f$ を区別できるように計算した αβ 値を $g$ と表記したが、手順 3-4 で $f$ を $g$ で更新するので、16 行目では `f` の値を計算した αβ 値で更新した
* __17 ~ 20 行目__：手順 3-3 の下界または上界を更新する処理を行う
* __21 行目__：繰り返しの終了後に `f` にミニマックス値が計算されるので、`score` に `f` を代入する

```python
 1  from ai import ai_by_score, dprint
 2  from marubatsu import Marubatsu
 3  from copy import deepcopy
 4  
 5  @ai_by_score
 6  def ai_mtdf(mb, debug=False, shortest_victory=False, init_ab=False, use_tt=False, 
 7                 f=0, ai_for_mo=None, params={}, sort_allnodes=False, calc_count=False):  
元と同じなので省略         
 8      min_score = -2 if shortest_victory else -1
 9      max_score = 3 if shortest_victory else 1
10      lbound = min_score if init_ab else float("-inf")
11      ubound = max_score if init_ab else float("inf")
12  
13      tt = {}
14      while lbound != ubound:
15          beta = f + 1 if lbound == f else f
16          f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
17          if f >= beta:
18              lbound = f
19          else:
20              ubound = f
21      score = f
22              
23      dprint(debug, "count =", count)
24      if calc_count:
25          return count
26      if mb.turn == Marubatsu.CIRCLE:
27          score *= -1
28      return score
```

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

```python
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
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 = {}
    while lbound != ubound:
        beta = f + 1 if lbound == f else f
        f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
        if f >= beta:
            lbound = f
        else:
            ubound = f
    score = f
            
    dprint(debug, "count =", count)
    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 marubatsu import Marubatsu
from copy import deepcopy

@ai_by_score
-def ai_abs_all(mb, debug=False, shortest_victory=False, init_ab=False, use_tt=False, 
-               ai_for_mo=None, params={}, sort_allnodes=False, calc_count=False):  
+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):  
元と同じなので省略         
    min_score = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
-   alpha = min_score if init_ab else float("-inf")
-   beta = max_score if init_ab else float("inf")
+   lbound = min_score if init_ab else float("-inf")
+   ubound = max_score if init_ab else float("inf")

-   score = ab_search(mb, {}, alpha=alpha, beta=beta)
+   tt = {}
+   while lbound != ubound:
+       beta = f + 1 if lbound == f else f
+       f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
+       if f >= beta:
+           lbound = f
+       else:
+           ubound = f
+   f = score        
    
    dprint(debug, "count =", count)
    if calc_count:
        return count
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

上記の定義後に、[以前の記事](https://qiita.com/ysgeso/items/97c293d8876190849ec8#%E6%9E%9D%E7%8B%A9%E3%82%8A%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E6%AF%94%E8%BC%83%E3%81%AB%E3%82%88%E3%82%8B%E6%A4%9C%E8%A8%BC)で `ai_abs_all` が __強解決であるかどうか__ を確認したのと同様の方法で __`ai_mtdf` が強解決の AI であるか__ どうかを確認すると、実行結果から __いずれの設定の場合でも強解決の AI であることが確認できます__。

なお、MTD(f) はもともと move ordering を前提としないアルゴリズムなので、__move ordering を行わない場合で検証__ を行いました。

```python
from util import Check_solved

for shortest_victory in [False, True]:
    for use_tt in [False, True]:
        for init_ab in [False, True]:
            for sort_allnodes in [False, True]:
                print(f"sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab}")
                params = {
                    "shortest_victory": shortest_victory,
                    "init_ab": init_ab,
                    "use_tt": use_tt,
                }
                Check_solved.is_strongly_solved(ai_mtdf, params=params)
```

実行結果

```
sv: False, use_tt: False, init_ab: False
100%|██████████| 431/431 [00:04<00:00, 87.39it/s] 
431/431 100.00%
sv: False, use_tt: False, init_ab: True
100%|██████████| 431/431 [00:03<00:00, 124.23it/s]
431/431 100.00%
sv: False, use_tt: True, init_ab: False
100%|██████████| 431/431 [00:03<00:00, 127.08it/s]
431/431 100.00%
sv: False, use_tt: True, init_ab: True
100%|██████████| 431/431 [00:02<00:00, 149.80it/s]
431/431 100.00%
sv: True, use_tt: False, init_ab: False
100%|██████████| 431/431 [00:04<00:00, 88.04it/s] 
431/431 100.00%
sv: True, use_tt: False, init_ab: True
100%|██████████| 431/431 [00:05<00:00, 80.79it/s] 
431/431 100.00%
sv: True, use_tt: True, init_ab: False
100%|██████████| 431/431 [00:03<00:00, 123.87it/s]
431/431 100.00%
sv: True, use_tt: True, init_ab: True
100%|██████████| 431/431 [00:03<00:00, 113.19it/s]
431/431 100.00%
```

# 今回の記事のまとめ

今回の記事では MTD(f) 法について説明し、MTD(f) 法で着手を選択する `ai_mtdf` の定義を行いました。次回の記事では実装した `ai_mtdf` を利用して MTD(f) の効率を検証します。

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

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

# 次回の記事

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

[^1]:MTD(f) を紹介した論文では move ordering を行なっていませんが、move ordering を行ってもかまいません
[^2]:$|x|$ は $x$ の絶対値（符号を正にした値）を表す記号です