Pythonで〇×ゲームのAIを一から作成する　その174　深さ制限探索の性質

# 目次と前回の記事

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

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

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

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

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

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

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

# 深さ制限探索の性質

下記は[以前の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#%E6%B7%B1%E3%81%95%E5%88%B6%E9%99%90%E6%8E%A2%E7%B4%A2)で説明した深さ制限探索の性質の再掲です。

__深さ制限探索__ はベースとなるアルゴリズムでゲーム木の探索を行う際に、探索するノードの __深さの上限を制限__ することで __処理時間を短くする代わりに__、__計算結果__ としてが正確な値ではない __近似値__ を求める __[ヒューリスティック](https://qiita.com/ysgeso/items/d7f60ba34f167f77a87e#%E3%83%92%E3%83%A5%E3%83%BC%E3%83%AA%E3%82%B9%E3%83%86%E3%82%A3%E3%83%83%E3%82%AF)__ なアルゴリズムです。

深さ制限探索は __一般的に下記のような性質__ があります。

* 深さの上限が大きくなるほど __処理時間が増える__
* 深さの上限が大きくなるほど近似値の __精度が高くなる__

上記の性質から __処理時間__ と __近似値の精度__ は両立しない __トレードオフの関係__ になるため、__適切な深さの上限を決めることが重要__ になります。処理時間が長すぎることが大きな問題となることが多いので、一般的には制限時間の制約から深さの上限を決めることが多いのではないかと思います。

今回の記事では前回の記事で実装した、__αβ 法をベースとした深さ制限探索__ 処理を行う __`ai_abs_dls`__ を利用して __上記の性質を確認__ することにします。

:::note
ミニマックス法をベースとした深さ制限探索を行う関数を実装し、それを使って確認することもできますが、ゲーム木の探索では効率の悪いミニマックス法はあまり使われないので αβ をベースとした深さ制限探索で確認することにしました。
:::

# 深さの上限と処理時間の関係の確認

下記は、αβ 法をベースとした深さ制限探索を行う __`ai_abs_dls`__ を利用して、下記の条件で __深さの上限を 0 ~ 9__ とした場合に __計算されるノードの数を表示__ するプログラムです。

* __`ai14s`__ を静的評価関数とする
* ゲーム開始時の局面のミニマックス値を計算する
* 置換表を利用する場合としない場合の両方の計算を行う

```python
from ai import ai_abs_dls, ai14s
from marubatsu import Marubatsu

mb = Marubatsu()
for use_tt in [False, True]:
    print(f"use_tt: {use_tt}")
    for maxdepth in range(10):
        count = ai_abs_dls(mb, maxdepth=maxdepth, eval_func=ai14s, eval_params={"minimax": True},
                           use_tt=use_tt, calc_score=True, calc_count=True)
        print(f"maxdepth: {maxdepth}  count {count}")
```

実行結果

```
use_tt: False
maxdepth: 0  count 1
maxdepth: 1  count 10
maxdepth: 2  count 36
maxdepth: 3  count 171
maxdepth: 4  count 658
maxdepth: 5  count 2648
maxdepth: 6  count 7202
maxdepth: 7  count 12762
maxdepth: 8  count 15640
maxdepth: 9  count 18297
use_tt: True
maxdepth: 0  count 1
maxdepth: 1  count 10
maxdepth: 2  count 27
maxdepth: 3  count 76
maxdepth: 4  count 189
maxdepth: 5  count 413
maxdepth: 6  count 831
maxdepth: 7  count 978
maxdepth: 8  count 1049
maxdepth: 9  count 1069
```

実行結果から、__深さの上限が増える__ と __深さが 6 まで__ は計算するノードの数が 2 倍以上の __指数関数的に増えていく__ ことが確認できます。また、__置換表を利用__ することで __効率を高めることができる__ ことが確認できました。なお、〇× ゲームは __着手を行うたびに合法手の数が減る__ ので、深さが __深くなるにつれて__ ノードの数の __増え方の割合が減っていきます__。

次に、上記のそれぞれの場合の平均処理時間を timeit の前に __% を一つだけ記述__ した __`%timeit`__ を利用して計測することにします。[以前の記事](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#index-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E6%AC%A0%E7%82%B9%E3%81%A8timeit-%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB%E3%81%AB%E3%82%88%E3%82%8B%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E8%A8%88%E6%B8%AC)で紹介した timeit の前に % を __二つ記述__ する __`%%timeit`__ は、JupyterLab の __セルの中に記述__ されたプログラム全体の __処理時間の平均と標準偏差を計測__ しますが、__%time__ は __その後に記述__ した __1 つの文__ の処理時間の平均と標準偏差を計測します。

下記はそのプログラムで、先程のプログラムとの大きな違いは __`ai_abs_dls`__ を呼び出す処理の __前に %timeit を記述__ する点です。なお、%timeit で計測する処理の記述の途中で __改行したい場合__ は __文の途中で改行する場合と同様__ に __改行の直前に \ を記述__ する必要があります。他の違いとしては、処理時間とは関係のない表示を行う処理は削除しました。

```python
for use_tt in [False, True]:
    print(f"use_tt: {use_tt}")
    for maxdepth in range(10):
        print(f"maxdepth {maxdepth}")
        %timeit ai_abs_dls(mb, maxdepth=maxdepth, eval_func=ai14s, \
                           eval_params={"minimax": True}, use_tt=use_tt, \
                           calc_score=True, calc_count=True)
```

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

```diff_python
for use_tt in [False, True]:
    print(f"use_tt: {use_tt}")
    for maxdepth in range(10):
+       print(f"maxdepth {maxdepth}")
-       count = ai_abs_dls(mb, maxdepth=maxdepth, eval_func=ai14s,
-                          eval_params={"minimax": True}, use_tt=use_tt,
-                          calc_score=True, calc_count=True)
-       print(f"maxdepth: {maxdepth}  count {count}")
+       %timeit ai_abs_dls(mb, maxdepth=maxdepth, eval_func=ai14s, \
+                          eval_params={"minimax": True}, use_tt=use_tt, \
+                          calc_score=True, calc_count=True)
```
</details>

実行結果

```
use_tt: False
maxdepth 0
21.8 µs ± 854 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
maxdepth 1
524 µs ± 3.4 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
maxdepth 2
1.97 ms ± 96.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
maxdepth 3
9.74 ms ± 12.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
maxdepth 4
38.6 ms ± 98 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
maxdepth 5
152 ms ± 612 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
maxdepth 6
412 ms ± 1.57 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
maxdepth 7
691 ms ± 2.14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
maxdepth 8
831 ms ± 10 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
maxdepth 9
902 ms ± 4.17 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
use_tt: True
maxdepth 0
21.6 µs ± 372 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
maxdepth 1
544 µs ± 2.18 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
maxdepth 2
1.47 ms ± 2.79 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
maxdepth 3
4.32 ms ± 10.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
maxdepth 4
11.4 ms ± 184 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
maxdepth 5
24.9 ms ± 921 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
maxdepth 6
50.2 ms ± 515 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
maxdepth 7
58.1 ms ± 1.67 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
maxdepth 8
60.1 ms ± 200 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
maxdepth 9
59.8 ms ± 168 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

下記は上記の結果をまとめた表です。表の平均処理時間を回数で割った __1 回あたりの平均処理時間__ が、深さの上限が 0 以外の場合で置換表を利用しない場合とする場合の両方で平均である __約 53 μs__ と __約 58 μs__ に __近い値になっている__ ことから、__処理時間__ が計算した __ノードの数にほぼ比例する__ ことが確認できます。なお、深さの上限が 0 の場合の平均処理時間が短い理由はおそらく子ノードの評価値を比較する処理が必要ないからだと思います。また、置換表を利用する場合は置換表に関する処理を行う分だけ平均処理時間が長くなります。

__置換表を利用しない場合__

|深さの上限|回数|平均処理時間(ms)|1 回あたりの平均処理時間（μs）|
|--:|--:|--:|--:|
|__0__|1|0.0218|21.8|
|__1__|10| 0.524| 52.4|
|__2__|36|1.97|54.7|
|__3__|171|9.74|57.0|
|__4__|658|38.6|58.7|
|__5__|2648|152|57.4|
|__6__|7202|412|57.2|
|__7__|12762|691|54.1|
|__8__|15640|831|53.1|
|__9__|18297|902|49.3|
|__合計__|57425|3039|52.9|

__置換表を利用する場合__

|深さの上限|回数|平均処理時間(ms)|1 回あたりの平均処理時間（μs）|
|--:|--:|--:|--:|
|__0__|1|0.0216|21.6|
|__1__|10| 0.544| 54.4|
|__2__|27|1.47|54.4|
|__3__|76|4.32|56.8|
|__4__|189|11.4|60.3|
|__5__|413|24.9|60.3|
|__6__|831|50.2|60.4|
|__7__|978|58.1|59.4|
|__8__|1049|60.1|57.3|
|__9__|1069|59.8|55.0|
|__合計__|4643|269.9|58.1|

上記から下記の事が確認できました。

:::note warn
__深さ制限探索__ の __処理時間__ は、計算する __ノードの数に比例__ する。

従って、ノードの数が __深さに対して指数関数的に増えるゲーム木__ の __深さ制限探索__ による __処理時間__ は、__深さの上限__ に対して __指数関数的に増える__。
:::

# 〇×ゲームでの深さの上限と精度の関係

__〇×ゲーム__ での __深さ制限探索__ によって計算された __ミニマックス値の近似値__ の __精度__ と、__深さの上限の関係__ について検証することにします。

## 深さの上限が 0 の場合に行われる処理

__深さの上限を 0__ とした深さ制限探索による __ミニマックス値の近似値の計算__ は、深さが 0 の __ルートノードの局面__ に対して __静的評価関数が計算した評価値__ になります。従って、__`ai_abs_dls`__ にキーワード引数 __`maxdepth=0`__ と __`calc_score=True`__ を記述して呼び出すと、キーワード引数 __`eval_func`__ で指定した __評価関数が計算した評価値__ が返されます。

:::note warn
__深さの上限を 0__ とした深さ制限探索によって計算されるミニマックス値の近似値の __精度__ は、深さ制限探索で利用する __静的評価関数と同じ__ になる。
:::

そのことを、__AI どうしの通算成績を計算__ する __[`ai_match`](https://qiita.com/ysgeso/items/93fb9b6daa59149514e9#%E8%A1%A8%E7%A4%BA%E3%81%AE%E6%94%B9%E8%89%AF%E3%81%9D%E3%81%AE-5ai-%E3%81%AE%E5%90%8D%E5%89%8D%E3%81%AE%E8%A1%A8%E7%A4%BA)__ を利用した下記の処理を行うことで __確認する__ ことにします。下記では 3 種類の静的評価関数で確認を行なっていますが、余裕がある方は他の評価関数でも確認を行なってみて下さい。

* __静的評価関数を `ai2s`__、__深さの上限を 0__ とした __`ai_ab_dls`__ VS __`ai2s`__ との対戦を `ai_match` を利用して 1000 回行う
* __`ai2s`__ VS __`ai2s`__ との対戦を `ai_match` を利用して 1000 回行い、__上記の通算成績とほぼ同じになる__ ことを確認する
* __静的評価関数__ を __`ai10s`__、__`ai14s`__ とした場合で __上記と同様の対戦__ を行ない、__通算成績がほぼ同じになる__ ことを確認する

:::note
`ai_abs_dls` が行う処理を正しく理解している人にとっては両者が同じ処理を行うことは明らかなので、このような確認を行うことに意味がないと思う人がいるかもしれませんが、__実際に実行して結果に差がないことを確認__ することで、__`ai_abs_dls`__ が少なくとも __深さの上限を 0__ とした場合の __処理を正しく実装できている__ ことを __確認できる__ という意味があります。
:::

下記はそのプログラムです。

* __3 行目__：`ai_abs_dls` を呼び出す際の実引数を表す dict を `params` に代入する
* __4 行目__：3 つの静的評価関数に対する繰り返し処理を行う
* __5 行目__：静的評価関数の名前を表示する。なお、関数の名前は[特殊属性](https://qiita.com/ysgeso/items/a189461ae32a6531ff7f#%E7%89%B9%E6%AE%8A%E5%B1%9E%E6%80%A7) `__name__` に代入されている
* __6 行目__：`params` の `"eval_func"` のキーに静的評価関数を代入する
* __7 行目__：`ai_abs_dls` VS `ai2s` の対戦を 1000 回行う 
* __8 行目__：静的評価関数 `eval_func` VS `ai2s` の対戦を 1000 回行う 

```python
1  from ai import ai_match, ai2s, ai10s
2  
3  params = {"maxdepth": 0, "eval_func": ai2s, "eval_params": {"minimax": True}}
4  for eval_func in [ai2s, ai10s, ai14s]:
5      print(f"eval_func {eval_func.__name__}")
6      params["eval_func"] = eval_func
7      ai_match(ai=[ai_abs_dls, ai2s], params=[params, {}], match_num=1000)
8      ai_match(ai=[eval_func, ai2s], match_num=1000) 
```

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

```python
from ai import ai_match, ai2s, ai10s

params = {"maxdepth": 0, "eval_func": ai2s, "eval_params": {"minimax": True}}
for eval_func in [ai2s, ai10s, ai14s]:
    print(f"eval_func {eval_func.__name__}")
    params["eval_func"] = eval_func
    ai_match(ai=[ai_abs_dls, ai2s], params=[params, {}], match_num=1000)
    ai_match(ai=[eval_func, ai2s], match_num=1000)
```

</details>

実行結果

```
100%|██████████| 1000/1000 [00:06<00:00, 148.24it/s]
count     win    lose    draw
o         592     275     133
x         277     597     126
total     869     872     259

ratio     win    lose    draw
o       59.2%   27.5%   13.3%
x       27.7%   59.7%   12.6%
total   43.5%   43.6%   13.0%

ai2s VS ai2s
100%|██████████| 1000/1000 [00:06<00:00, 159.47it/s]
count     win    lose    draw
o         591     291     118
x         284     597     119
total     875     888     237

ratio     win    lose    draw
o       59.1%   29.1%   11.8%
x       28.4%   59.7%   11.9%
total   43.8%   44.4%   11.8%

eval_func ai10s
ai_abs_dls VS ai2s
100%|██████████| 1000/1000 [00:07<00:00, 139.58it/s]
count     win    lose    draw
o         970       0      30
x         847      29     124
total    1817      29     154

ratio     win    lose    draw
o       97.0%    0.0%    3.0%
x       84.7%    2.9%   12.4%
total   90.8%    1.5%    7.7%

ai10s VS ai2s
100%|██████████| 1000/1000 [00:06<00:00, 146.69it/s]
count     win    lose    draw
o         976       0      24
x         852      20     128
total    1828      20     152

ratio     win    lose    draw
o       97.6%    0.0%    2.4%
x       85.2%    2.0%   12.8%
total   91.4%    1.0%    7.6%

eval_func ai14s
ai_abs_dls VS ai2s
100%|██████████| 1000/1000 [00:07<00:00, 138.40it/s]
count     win    lose    draw
o         988       0      12
x         884       0     116
total    1872       0     128

ratio     win    lose    draw
o       98.8%    0.0%    1.2%
x       88.4%    0.0%   11.6%
total   93.6%    0.0%    6.4%

ai14s VS ai2s
100%|██████████| 1000/1000 [00:06<00:00, 160.48it/s]
count     win    lose    draw
o         988       0      12
x         892       0     108
total    1880       0     120

ratio     win    lose    draw
o       98.8%    0.0%    1.2%
x       89.2%    0.0%   10.8%
total   94.0%    0.0%    6.0%
```

実行結果から __通算成績がほぼ同じである__ ことが実際に確認できました。

## 深さの上限を増やした場合の AI の通算成績の計算

ミニマックス値の近似値の __精度が高まる__ と、__正確なミニマックス値__ が計算される __可能性が高まる__ ので __強解決の AI に近づきます__。そのため、`ai_match` を使ってランダムな AI である __`ai2s` と対戦した際の通算成績を比べる__ ことで、__近似値の精度を測る__ ことができます。

__〇× ゲーム__ は __ゲーム開始時__ の局面の __状態が引き分け__ なので、近似値の __精度が高いほど__ `ai2s` との通算成績の __敗率が 0 % に近づき__、__敗率が 0 %__ になった時点で `ai2s` との対戦で生じる局面に対するミニマックス値の近似値の __精度が 100 %__ だとみなすことができます。

:::note
`ai2s` はランダムな着手を行うので、__充分な回数の対戦__ を行わないと敗率が 0 % になったとしても精度が 100 % になったとみなすことはできません。今回の記事では 1000 回対戦を行うことにしました。

また、`ai2s` との対戦で発生しない局面のミニマックス値の精度は判定できないので、その場合 __弱解決の AI__ であることは判定できますが、強解決の AI であることは判定できません。強解決の AI であるかどうかの判定は `Check_solved` で行います。
:::

そこで、下記の __様々な異なる精度__ の静的評価関数を使って、__深さの上限を 0 から 8__[^1] まで増やした場合の __`ai_abs_dls` VS `ai2s`__ の対戦を行うことにします。興味がある方は他の AI でも同様の計算を行ってみて下さい。

* すべての局面で評価値として 0 を計算する、ランダムな着手を行う [`ai2s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E9%96%A2%E6%95%B0%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E3%83%AB%E3%83%BC%E3%83%AB-2-%E3%81%A7%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9)
* 真ん中のマスを優先的に着手する [`ai3s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#ai_by_score-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E3%83%AB%E3%83%BC%E3%83%AB-3-%E3%81%A7%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9)
* 自分が勝利している場合に 1、そうでない場合に 0 を計算する [`ai5s`](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#ai5s-%E3%81%AE%E5%AE%9F%E8%A3%85)
* 弱解決ではないが、それなりに高い精度で近似値を計算する [`ai10s`](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#ai10s-%E3%81%AE%E5%AE%9A%E7%BE%A9)
* 弱解決で、対戦においては精度が 100 % のミニマックス値を計算する [`ai14s`](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#ai14s-%E3%81%AE%E5%AE%9A%E7%BE%A9)

### `ai_match` の修正

現状の __`ai_match`__ は __通算成績を画面に表示するだけ__ で返り値として返さないので、__後から通算成績を利用__ することは __できません__。そこで、下記のプログラムのように、__通算成績を返り値として返す__ ように `ai_match` を修正することにします。

* __9 行目__：通算成績に関するデータは 7 行目で `diff_list` に代入されるので、それを返り値として返すように修正する

```python
1  from collections import defaultdict
2  from tqdm import tqdm
3  
4  def ai_match(ai, params, match_num=10000):
元と同じなので省略
5      # 通算成績の回数と比率の表示
6      width = max(len(str(match_num * 2)), 7)
7      diff_list = [ ("count", count_list_ai0, f"{width}d"),
8                    ("ratio", ratio_list, f"{width}.1%") ]
元と同じなので省略
9      return  diff_list
```

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

```python
from collections import defaultdict
from tqdm import tqdm

def ai_match(ai, params, match_num=10000):
    print(f"{ai[0].__name__} VS {ai[1].__name__}")
    
    mb = Marubatsu()

    # ai[0] VS ai[1] と ai[1] VS a[0] の対戦を match_num 回行い、通算成績を数える
    count_list = [ defaultdict(int), defaultdict(int)]
    for _ in tqdm(range(match_num)):
        count_list[0][mb.play(ai, params=params, verbose=False)] += 1
        count_list[1][mb.play(ai=ai[::-1], params=params[::-1], verbose=False)] += 1

    # ai[0] から見た通算成績を計算する
    count_list_ai0 = [
        # ai[0] VS ai[1] の場合の、ai[0] から見た通算成績
        { 
            "win": count_list[0][Marubatsu.CIRCLE],
            "lose": count_list[0][Marubatsu.CROSS],
            "draw": count_list[0][Marubatsu.DRAW],
        },
        # ai[1] VS ai[0] の場合の、ai[0] から見た通算成績
        { 
            "win": count_list[1][Marubatsu.CROSS],
            "lose": count_list[1][Marubatsu.CIRCLE],
            "draw": count_list[1][Marubatsu.DRAW],
        },
    ]           

    # 両方の対戦の通算成績の合計を計算する
    count_list_ai0.append({})
    for key in count_list_ai0[0]:
        count_list_ai0[2][key] = count_list_ai0[0][key] + count_list_ai0[1][key]

    # それぞれの比率を計算し、ratio_list に代入する
    ratio_list = [ {}, {}, {} ]
    for i in range(3):
        for key in count_list_ai0[i]:
            ratio_list[i][key] = count_list_ai0[i][key] / sum(count_list_ai0[i].values())
            
    # 各行の先頭に表示する文字列のリスト
    item_text_list = [ Marubatsu.CIRCLE, Marubatsu.CROSS, "total" ]    
    
    # 通算成績の回数と比率の表示
    width = max(len(str(match_num * 2)), 7)
    diff_list = [ ("count", count_list_ai0, f"{width}d"),
                  ("ratio", ratio_list, f"{width}.1%") ]
    for title, data, format in diff_list:
        print(title, end="")
        for key in data[0]:
            print(f" {key:>{width}}", end="")
        print()
        for i in range(3):
            print(f"{item_text_list[i]:5}", end="")
            for value in data[i].values():
                print(f" {value:{format}}", end="")
            print()
        print()
        
    return  diff_list
```
</details>

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

```diff_python
from collections import defaultdict
from tqdm import tqdm

def ai_match(ai, params, match_num=10000):
元と同じなので省略
    # 通算成績の回数と比率の表示
    width = max(len(str(match_num * 2)), 7)
    diff_list = [ ("count", count_list_ai0, f"{width}d"),
                  ("ratio", ratio_list, f"{width}.1%") ]
元と同じなので省略
+    return  diff_list
```
</details>

### 対戦を行うプログラムの実行

下記は __`ai2s`__、__`ai3s`__、__`ai5s`__、__`ai10s`__、__`ai14s`__ を __静的評価関数__ とした __`ai_ab_dls` VS `ai2s`__ の対戦を、__深さの上限が 0 から 8__ までのそれぞれの場合で行うプログラムです。

それぞれの AI との __通算成績__ は __下記のデータ構造で記録__ することにします。

* 全体を dict で記録する
* 上記の dict の AI の関数名のキーの値に、その AI を静的評価関数とした場合の通算成績を list で記録する
* 上記の list には深さの上限ごとの通算成績を順番に記録する

例えば __`ai2s`__ を静的評価関数とし、__深さの上限を 2__ とした場合の通算成績は、全体のデータを表す dict を __`result`__ という変数に代入した場合は、__`result["ai2s"][2]`__ に記録されます。

なお、置換表を利用しないと処理時間がかなり長くなるので置換表を利用しています。また、__通算成績の精度を上げるため__ に __対戦回数を 1000 回__ としました。そのため下記のプログラムの処理は筆者のパソコンでは __1 時間半ほど__ かかりました。

* __3 行目__：それぞれの通算成績を記録する `result` という変数を空の dict で初期化する
* __4 行目__：`ai_abs_dls` を呼び出す際に記述する実引数を表す `params` を初期化する
* __5 行目__：それぞれの AI の関数に対する繰り返し処理を行う
* __6 行目__：`params` の中で静的評価関数を表すキーの値を設定する
* __7、8 行目__：静的評価関数の名前を `name` に代入し、その静的評価関数を利用した場合の深さの上限ごとの通算成績を記録する `result[name]` を空の list で初期化する
* __10 行目__：`params` の中で深さの上限を表すキーの値を設定する
* __11、12 行目__：`ai_match` で対戦を行い、通算成績を `diff_list` に代入する
* __13 行目__：`result[name]` の list の要素に通算成績を追加する

```python
 1  from ai import ai3s, ai5s
 2  
 3  result = {}
 4  params = {"maxdepth": 0, "eval_func": ai2s, "eval_params": {"minimax": True}}
 5  for eval_func in [ai2s, ai3s, ai5s, ai10s, ai14s]:
 6      params["eval_func"] = eval_func
 7      name = eval_func.__name__
 8      result[name] = []
 9      for maxdepth in range(9):
10          print(f"{name} maxdepth: {maxdepth}")
11          params["maxdepth"] = maxdepth
12          diff_list = ai_match(ai=[ai_abs_dls, ai2s], params=[params, {}], match_num=1000)
13          result[name].append(diff_list)
```

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

```python
from ai import ai3s, ai5s

result = {}
params = {"maxdepth": 0, "eval_func": ai2s, "eval_params": {"minimax": True}}
for eval_func in [ai2s, ai3s, ai5s, ai10s, ai14s]:
    params["eval_func"] = eval_func
    name = eval_func.__name__
    result[name] = []
    for maxdepth in range(9):
        print(f"{name} maxdepth: {maxdepth}")
        params["maxdepth"] = maxdepth
        diff_list = ai_match(ai=[ai_abs_dls, ai2s], params=[params, {}], match_num=1000)
        result[name].append(diff_list)
```
</details>

実行結果

```
ai2s maxdepth: 0
ai_abs_dls VS ai2s
100%|██████████| 1000/1000 [00:06<00:00, 160.04it/s]
count     win    lose    draw
o         568     292     140
x         301     569     130
total     869     861     270

ratio     win    lose    draw
o       56.8%   29.2%   14.0%
x       30.1%   56.9%   13.0%
total   43.5%   43.0%   13.5%

ai2s maxdepth: 1
ai_abs_dls VS ai2s
100%|██████████| 1000/1000 [00:18<00:00, 54.30it/s]
count     win    lose    draw
o         593     271     136
x         293     563     144
total     886     834     280

ratio     win    lose    draw
o       59.3%   27.1%   13.6%
x       29.3%   56.3%   14.4%
total   44.3%   41.7%   14.0%
略
```

### グラフによる視覚化

上記の通算成績を __表でまとめても__ 大量の数字が並ぶだけで __わかりづらい__ ので、下記のプログラムを実行して __グラフで視覚化__ することにします。なお、__x 軸の下と y 軸の左に表示するラベル__（説明のこと）は __`xlabel`__、__`ylabel`__ というメソッドで表示することができます。

* __3 行目__：勝率、敗率、引分率のそれぞれに対するグラフの描画の繰り返し処理を行う
* __4 行目__：それぞれの静的評価関数に対する繰り返し処理を行う
* __5 行目__：深さの上限ごとの比率（ratio）を記録する `ratio` を空の list で初期化する
* __6、7 行目__：比率のデータは `diff_list[1][1][2][type]` に代入されているので、それを `ratio` に代入された list の要素に追加する。`diff_list` について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/729c5425573cf1e8051f#ai_match-%E3%81%AE%E6%94%B9%E8%89%AF-%E3%81%9D%E3%81%AE-6ai-%E3%81%AE%E8%A6%96%E7%82%B9%E3%81%8B%E3%82%89%E3%81%AE%E7%B5%90%E6%9E%9C%E3%81%AE%E8%A1%A8%E7%A4%BA)を復習すること
* __8 行目__：静的評価関数の名前のラベルをつけて比率を折れ線グラフで表示する
* __9、10 行目__：x 軸と y 軸のラベルを表示する
* __11 行目__：グラフの凡例を描画する。凡例とラベルについて忘れた方は [以前の記事](https://qiita.com/ysgeso/items/1468226fe9a96ae6a55c#%E5%87%A1%E4%BE%8B%E3%81%AE%E6%8F%8F%E7%94%BB)を復習すること
* __12 行目__：`plt.show()` を実行してグラフを描画する。これを実行しないと、勝率、敗率、引分率のグラフが 1 つのグラフで表示されてしまう

```python
 1  import matplotlib.pyplot as plt
 2  
 3  for type in ["win", "lose", "draw"]:
 4      for name, value in result.items():
 5          ratio = []
 6          for diff_list in value:
 7              ratio.append(diff_list[1][1][2][type])
 8          plt.plot(ratio, label=f"{name}")
 9      plt.xlabel("max depth")
10      plt.ylabel(f"{type} ratio")
11      plt.legend()
12      plt.show()
```

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

```python
import matplotlib.pyplot as plt

for type in ["win", "lose", "draw"]:
    for name, value in result.items():
        ratio = []
        for diff_list in value:
            ratio.append(diff_list[1][1][2][type])
        plt.plot(ratio, label=f"{name}")
    plt.xlabel("max depth")
    plt.ylabel(f"{type} ratio")
    plt.legend()
    plt.show()
```
</details>

実行結果

__勝率のグラフ__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6aae7158-e1e3-47d6-a151-c4402ffdc5be.png" width="400">

__敗率のグラフ__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/040a329b-5d4e-4d49-885a-39ac00d12470.png" width="400">

__引分率のグラフ__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b6b241f8-dd11-4456-b114-49cf9fc85118.png" width="400">

## 実行結果の考察

上記の実行結果を __静的評価関数ごとに考察__ します。

### `ai2s` の場合

実行結果のグラフから __`ai2s`__ を静的評価関数とした場合は、深さの上限を増やしても __通算成績がほとんど変わらない__ ことが確認できます。これは、__`ai2s`__ が決着がついたリーフノードを含めて __常に局面の評価値として `0` を計算__ するため、__深さの上限に関わらす__ すべての局面の評価値が 0 として計算された結果 __ランダムな着手を行う__ からです。

このことから __静的評価関数__ が計算するミニマックス値の近似値の __精度が低すぎる場合__ は、深さ制限探索で深さの上限を増やしても近似値の __精度は向上しない__ ことがわかります。

### `ai3s` の場合

__`ai3s`__ を静的評価関数とした場合は下記のような評価値を計算します。その結果、__`ai3s` は真ん中のマスに優先的に着手__ を行います。なお、以後の説明ではキーワード引数に __`minimax=True`__ を記述して __ミニマックス値の近似値__ を計算した場合の説明を行います。

* 直前の着手が真ん中の (1, 1) の場合は以下の計算を行う
    * (1, 1) に 〇 が着手した場合は 1 を計算する
    * (1, 1) に × が着手した場合は -1 を計算する
* そうでなければ 0 を計算する

実行結果のグラフから __`ai3s`__ を静的評価関数とした場合の __通算成績__ は、__`ai2s`__ を静的評価関数とした場合 __よりも良い__ ので、__`ai3s`__ は __`ai2s` よりも精度が高い近似値__ を計算すると考えることができます。しかし、実行結果のグラフから __`ai3s`__ を静的評価関数とした場合も、__深さの上限を増やしても__ 通算成績が __ほとんど変わらない__ ことが確認できます。その理由について少し考えてみて下さい。

その理由の一つは、__ゲーム開始時の局面__ に対して __深さの上限を 2 以上__ とした場合に、下記の理由から __`ai3s`__ が __ランダムな着手を行う__ からです。

__ゲーム開始時の局面__ に対して、__深さの上限を__ $\boldsymbol{d}$ として `ai_abs_dls` の計算を行うと、下記のような処理が行われます。

* ゲーム開始時の局面は __max ノード__ なので、合法手を着手した子ノードの局面中で __最も評価値が高い__ 合法手の中からランダムで着手を行う
* ルートノードの __子ノードを__ $\boldsymbol{C}$ と表記した場合に、$C$ の局面の評価値は __深さの上限を__ $\boldsymbol{d}$ とする深さ制限探索で計算する

__深さの上限を 0__ とした場合はルートノードの __子ノードの評価値__ を静的評価関数 __`ai3s` で計算__ します。従って __(1, 1) に着手を行った__ 子ノードの __評価値が 1__、__それ以外__ の子ノードの __評価値 が 0__ になるので、__(1, 1) のみが選択__ されます。そのことは、下記のプログラムから確認することができます。

```python
from pprint import pprint

mb = Marubatsu()
pprint(ai_abs_dls(mb, eval_func=ai3s, eval_params={"minimax":True}, maxdepth=0, analyze=True))
```

実行結果

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

__深さの上限を 1__ とした場合は下記の計算が行われた結果、__(1, 1) に着手__ を行った子ノードの __評価値が 0__、__それ以外__ の子ノードの __評価値が -1__ になるので __(1, 1) のみが選択__ されます。

* ゲーム開始時の局面で __(1, 1) に着手を行った場合__ の子ノード $C$ の評価値は、下記の理由から __0 が計算__ される
    * $C$ の __合法手__ には __(1, 1) は存在しない__ ので、$\boldsymbol{C}$ __の子ノード__ に __直前の着手が (1, 1)__ である局面は __存在しない__
    * 従って、$C$ の __すべての子ノードの評価値は 0__ が計算される
* ゲーム開始時の局面で __(1, 1) 以外__ に着手を行った場合の子ノード $C$ の評価値は、下記の理由から __-1 が計算__ される
    * $C$ の __子ノード__ の中で __直前の着手が (1, 1)__ の場合の __評価値は -1__ が計算される
    * __それ以外__ の子ノードの __評価値は 0__ が計算される
    * $\boldsymbol{C}$ は __min ノード__ なので子ノードの評価値の __最小値である -1 が計算__ される

そのことは、下記のプログラムから確認することができます。

```python
pprint(ai_abs_dls(mb, eval_func=ai3s, eval_params={"minimax":True}, maxdepth=1, analyze=True))
```

実行結果

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

__深さの上限を 2__ とした場合は、下記の計算が行われた結果 __すべての子ノードの 評価値が 0__ となるため合法手の中から __ランダムな着手__ が行われます。

* ゲーム開始時の局面で __(1, 1) に着手を行った場合__ の子ノード $C$ の評価値は、下記の理由から __0 が計算__ される
    * $\boldsymbol{C}$ の __深さが 2 以上__ の子孫ノードには、__直前の着手が (1, 1)__ である局面が __存在しない__
    * 従って、$C$ の __深さが 2 の子孫ノード__ の評価値は __すべて 0 が計算__ される
    * 従って、$C$ の __深さが 1 の子ノード__ の評価値は __すべて 0 が計算__ される
    * 従って、$\boldsymbol{C}$ __の評価値は 0__ が計算される
* ゲーム開始時の局面で __(1, 1) 以外__ に着手を行った場合の子ノード $C$ の評価値も、下記の理由から __0 が計算__ される
    * $C$ には __(1, 1)__ と __それ以外__ の __合法手__ が存在し、$C$ の子ノードを $G$ と表記すると $\boldsymbol{G}$ __の評価値__ は __深さの上限を 1__ とした __深さ制限探索__ によって計算される
    * max ノートと min ノードの違いはあるが、先程の __深さの上限を 1__ とした場合の __検証と同じ理由__ から、$G$ の評価値は下記のように計算される。そのことは、下記のプログラムから確認することができる
        * $C$ の局面で __(1, 1) に着手__ を行った場合の __評価値は 0__ となる
        * $C$ の局面で __(1, 1) 以外__ に着手を行った場合の __評価値は 1__ となる
    * $\boldsymbol{C}$ __は min ノード__ なのでその __評価値は 0 が計算__ される

```python
mb.move(0, 0)
pprint(ai_abs_dls(mb, eval_func=ai3s, eval_params={"minimax":True}, maxdepth=1, analyze=True))
```

実行結果

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

__深さの上限を 2__ とした場合に __すべての子ノードの評価値が 0__ と計算され、__ランダムな着手__ が行われることは下記のプログラムで確認することができます。

```python
mb.restart()
pprint(ai_abs_dls(mb, eval_func=ai3s, eval_params={"minimax":True}, maxdepth=2, analyze=True))
```

実行結果

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

厳密な証明は省略しますが、__深さの上限 3 以上の場合__ も深さの上限が 2 以上の場合と同様の理由から、__すべての子ノードの評価値が 0__ と計算され __ランダムな着手__ が行われます。そのことは下記のプログラムを実行することで確認できます。

```python
for maxdepth in range(9):
    result = ai_abs_dls(mb, eval_func=ai3s, eval_params={"minimax":True},
                        maxdepth=maxdepth, analyze=True)
    print(f"maxdepth {maxdepth}")
    print(f"candidate {result['candidate']}")
```

実行結果

```
maxdepth 0
candidate [(1, 1)]
maxdepth 1
candidate [(1, 1)]
maxdepth 2
candidate [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
maxdepth 3
candidate [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
maxdepth 4
candidate [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
maxdepth 5
candidate [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
maxdepth 6
candidate [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
maxdepth 7
candidate [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
maxdepth 8
candidate [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
```

上記の説明から、深さの上限を 2 以上とした場合の通算成績は深さの上限を 0、1 とした場合よりも減ると思った方がいるかもしれませんが、おそらく下記のような理由から __`ai2s` よりも精度の高い近似値を計算できる__ ので、通算成績はそれほど変わらないようです。

* `ai3s` は、__(1, 1) に着手__ を行うことで __ゲームの決着がついた局面__ では __正しいミニマックス値を計算__ することができる
* __深さの上限が大きくなる__ と __決着がついた局面__ の評価値を計算することが __多くなる__
* __ランダムな着手を行う `ai2s` との対戦__ の場合[^2]は __(1, 1) に着手を行う__ ことで __決着がつく局面が存在する__

### `ai5s` の場合

__`ai5s`__ は以下のような評価値を計算する静的評価関数で、`ai5s` は __勝利できる場合に勝利する__ 着手を行います。

* 〇 が勝利している場合は 1 を計算する
* × が勝利している場合は -1 を計算する
* それ以外の場合は 0 を計算する

下記は勝率と敗率のグラフの再掲です。引分率は重要ではないので省略しました。

__勝率のグラフ__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6aae7158-e1e3-47d6-a151-c4402ffdc5be.png" width="400">

__敗率のグラフ__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/040a329b-5d4e-4d49-885a-39ac00d12470.png" width="400">

実行結果のグラフから __`ai5s`__ を静的評価関数とした深さ制限探索の AI は、深さの上限を __増やすほど通算成績が向上する__ ことがわかります。

__深さの上限を 1__ とした場合の __通算成績__ が向上する理由は、その場合に行われる処理が __勝利できる場合に勝利__ し、相手が次の手番で勝利できる場合は __相手の勝利を妨害__ する __`ai6s`__ と同じになるからです。下記の表の __`ai_abs_dls` の行__ は先程行った静的評価関数を `ai5s`、深さの上限を 1 とした場合の対戦結果です。__`ai6s` の行__ は[以前の記事](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#%E3%81%93%E3%82%8C%E3%81%BE%E3%81%A7%E3%81%AB%E4%BD%9C%E6%88%90%E3%81%97%E3%81%9F-ai)で行った __`ai6s` VS `ai2s`__ の対戦結果で、実際に __両者がほぼ同じである__ ことが確認できます。

静的評価関数を `ai5s`、深さの上限を 1 とした `ai_abs_dls` で行われる処理が __`ai6s` と同じ__ になる理由について少し考えてみて下さい。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __`ai_abs_dls`__  |   89.4 | 2.8 | 7.8 | 68.4 | 9.0 | 22.6 | 78.9 | 5.9 | 15.2 |
| __`ai6s`__  |   88.6 | 1.9 | 9.5 | 69.4 | 9.1 | 21.5 | 79.0 | 5.5 | 15.5 |

__深さの上限を 1__ とした場合は、現在の局面に対して自分と相手が着手した __2 手先の局面の評価値__ を __`ai5s` で計算__ します。その結果、__〇 の手番__ の局面に対する処理は下記のように計算されます。なお、× の手番の局面の場合は同様なので説明を省略します。

* それぞれの __子ノードの評価値__ を下記のように計算する
    * 自分が勝利している局面の評価値は 1
    * 次の相手の手番で相手が勝利できる合法手が存在する場合の評価値は -1
    * そうでなければ 0
* 〇 の手番の局面は __max ノード__ なので __最も高い評価値の子ノード__ の合法手が選択され、下記の優先順位で着手が選択される。これは __`ai6s` が選択する着手と同じ__ ものである
    1. 自分が勝利する合法手
    2. 次の相手の勝利を妨害する合法手
    3. それ以外の合法手

__深さの上限を 0__ とした場合の __`ai5s`__ は、__次の自分の着手のみを考慮__ しますが、__深さの上限を 1__ とした場合の `ai5s` は __その次の相手の着手も考慮__ するため __より強くなります__。

深さの上限を 2 以上とした場合はより先の局面を考慮するためさらに強くなります。

また、実行結果のグラフから __深さの上限が 5 以上__ になると __敗率が 0__ になることから、__弱解決の AI と同じ強さ__ を持つようになることがわかります。さらに、__深さの上限を最大の 8__ にすると __`ai10s` や `ai14s` と同じ通算成績__ になることもわかります。

__`ai2s` と `ai3s`__ が深さの上限を増やしても __精度が上がらず__、__`ai5s`__ の場合は __精度が上がる理由__ についてはこの後で説明します。その理由について少し考えてみて下さい。

### `ai10s` と `ai14s` の場合

__`ai10s`__ は __弱解決ではありません__ が、__`ai2s`__ との __通算成績の勝率が 約 90 %__ なので計算する __近似値の精度はかなり高い__ と考えられます。また、実行結果のグラフから __`ai10s`__ を静的評価関数とした場合は __深さの上限を上げる__ と下記のような性質を持つことがわかります。

* __最初__ は `ai2s` との対戦の通算成績の __勝率が向上する__ が、__深さの上限が 5 を超えたあたり__ から __勝率が下がる__
* __敗率__ は __深さの上限が増える__ と __減り__、深さの上限が __5 以上になると 0 % になる__ 
* 従って、__深さの上限が 5 以上__ の場合は __弱解決の AI__ である

__深さの上限が 5__ の場合に __弱解決の AI である__ ことは、下記のプログラムで確認できます。

```python
from util import Check_solved

Check_solved.is_weakly_solved(ai_abs_dls, params={"eval_func": ai10s, "maxdepth": 5, 
                                                  "eval_params": {"minimax": True}})
```

実行結果

```
   o True
   x True
Both True
```

:::note
残念ながら深さの上限が 5 の場合は、下記のプログラムの実行結果から 100 % と表示されないので強解決の AI ではありません。

```python
Check_solved.is_strongly_solved(ai_abs_dls, params={"eval_func": ai10s, "maxdepth": 5, 
                                                  "eval_params": {"minimax": True}})
```

実行結果

```
100%|██████████| 431/431 [00:03<00:00, 121.83it/s]
422/431 97.91%
```
:::

また、グラフから以下の事がわかります。

* __`ai14s` の勝率__ も同様に __深さの上限が 5 以上__ になると __下がる__
* __深さの上限を上げる__ と __`ai5s`、`ai10s`、`ai14s`__ の __通算成績は近づいていき__、__深さの上限が 8__ になると __ほぼ同じ__ になる

このようなことが起きる原因は、__深さの上限が 8__ の場合に __行われる処理__ を考察することで理解できます。__深さの上限を 8__ とした場合は、静的評価関数が __評価値が計算するノード__ は __すべてゲームの決着がついた局面__ になります。別の言葉で言い換えると、__深さの上限__ を __ゲーム木の深さ以上に設定__ した深さ制限探索は、__深さの制限を行わない__ ゲーム木の __探索と同じ処理__ を行うということです。__`ai5s`、`ai10s`、`ai14s`__ はいずれも __決着がついた局面の評価値を正しく計算できる__ ので、__深さの上限を 8 以上__ とした場合は __強解決の AI__ になります。

下記は静的評価関数を __`ai5s`__、__深さの上限を 8__ とした場合 __`ai_abs_dls` が強解決の AI__ であることを確認するプログラムです。

```python
Check_solved.is_strongly_solved(ai_abs_dls, params={"eval_func": ai5s, "maxdepth": 8, 
                                                    "eval_params": {"minimax": True}})
```

実行結果

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

また、ゲーム木の中には __浅い深さのノード__ で __ゲームの決着がつく__ 場合があります。例えば (0, 0)、(1, 0)、(0, 1)、(1, 1)、(0, 2) の順で着手を行うと、__深さが 5 のノードの局面で決着__ がつきます。深さ制限探索で __深さの上限を上げる__ と近似値の __精度が上がる理由の一つ__ は、静的評価関数が計算するノードの中で、__正確な評価値を計算できる__ ゲームの __決着がついた局面の割合が増える__ ため、静的評価関数が計算した __近似値の精度の平均値が高くなる__ ためです。

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

:::note warn
__静的評価関数__ がゲームの __決着がついた局面の評価値を正確に計算できる場合__ は、__深さの上限__ を __ゲーム木の深さ以上に設定__ した深さ制限探索を行うことで __正確な評価値を計算__ することができるようになる。

また、__深さの上限を増やすことで__ と静的評価関数が計算するゲームの __決着がついた局面の割合が増える場合__ は、__評価値の精度が高く__ なる。
:::

__`ai2s` と `ai3s`__ が深さの上限を増やしても __精度が上がらない理由__ は、どちらも __決着がついた局面の評価値__ を __正確に計算できないから__ です。

### 深さの上限を増やした場合に精度が上がる別の理由

深さの上限を増やした場合に __精度が上がる他の理由__ には以下のようなものがあります。

__一般的__ に、多くのゲームでは __ゲームが進行__ するにつれて __勝敗の形勢がはっきりします__。例えば 〇× ゲームでは __ゲーム開始時の局面__ ではすべてのマスが空であるため、__ゲーム盤の局面だけから__ どちらが有利であるかの __形勢を判断することが困難__ ですが、__マスが埋まっていく__ につれて __形勢が急速にはっきり__ していきます。

__深さの上限を増やす__ ということは、__より多くゲームが進行した局面__ に対して静的評価関数が __形勢を判断する__ ことになるので、__より精度の高い評価値を計算__ できるようになる __可能性が高くなります__。特に多くのゲームでは __形勢がはっきりしやすい__  ゲームの __終盤でその傾向が高くなります__。

ただし、下記の理由から必ずしも深さの上限を増やすことで __精度が上がるとは限りません__。

* __ゲームの決着__ がつくまでに __長い手数が必要__ になるゲームの場合は、__数手程度の着手__ を行っても __形勢の判断にほとんど影響がない__ ことが多い
* __着手を進める__ ことで __形勢の判断が逆にしにくくなる__ ような場合がある

そのため上記の理由は 〇× ゲームには強く当てはまりますが、オセロや将棋などの他の多くのゲームの序盤ではではそれほど強く当てはまりません。

### 深さの上限を増やした場合に `ai14s` の勝率が下がる理由

実行結果のグラフから、__深さの上限を増やす__ と __`ai10s` と `ai14s`__ を静的評価関数とした場合の __勝率が下がる__ という、上記の説明とは __矛盾したように見える__ 結果が得られますが、それには理由があります。その理由について少し考えてみて下さい。

__深さの上限を 8__ とした `ai10s` や `ai14s` を静的評価関数とした深さ制限探索は、__常にゲームの決着がついた局面__ を静的評価関数で計算します。そのため、`ai5s`、`ai10s`、`ai14s` などの __ゲームの決着がついた局面__ の評価値を __正確に計算する静的評価関数__ を利用した場合は、__深さの上限を 8__ とした場合にいずれも __同じ着手を選択__ します。また、その際に選択する着手は、__深さの上限を制限しない__ ゲーム木の探索で着手を選択する __`ai_gt6` と同じ__ になります。従って、その通算成績は下記の表のように[以前の記事](https://qiita.com/ysgeso/items/10d1d01192c014173e4b#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA-ai-%E3%81%A7%E3%81%82%E3%82%8B-ai2-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6%E7%B5%90%E6%9E%9C)で計算した下記の `ai_gt1` VS `ai2s` と __ほぼ同じ__ になります。


| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __深さの上限 8 の `ai5s`__  |  96.8 | 0.0 | 3.2 | 76.8 | 0.0 | 23.2 | 86.8 | 0.0 | 13.2 |
| __`ai_gt1`__  |   96.9  | 0.0 |	3.1 |	78.0 |	0.0 |	22.1 |	87.4 |	0.0 |	12.6 |

__`ai14s` VS `ai2s`__ の通算成績が __`ai_gt1` VS `ai2s` よりも良い理由__ は、__`ai14s`__ がゲームの __決着がついていない局面__ の __性質を考慮した評価値を計算__ して着手を選択することで、__最善手の中__ で __`ai2s` と対戦__ した場合に __勝ちに結びつきやすい__ 合法手が選択されるからです。__深さの上限を 8__ とした場合は、ゲームの __決着がついている局面__ の評価値しか __計算されなくなり__、__すべての最善手__ の中から __ランダムに着手を選択__ するようになるので、`ai2s` に対する勝率は低くなってしまいます。

### 一般的なゲームにおける深さの上限と精度の関係

__〇× ゲーム__ はゲーム木の深さが 9 と浅く、__ノードの数もそれほど多くない__ ので今回の記事で説明した理由で、__深さの上限を増やす__ と深さ制限探索の __精度が向上__ します。

しかし、__オセロや将棋など__ のゲーム木は __深さがかなり深く__、__ノードの数が多すぎる__ ので、 __ほとんどの局面__ で深さ制限探索で __すべてのノードを探索できる__ ほど深さの上限を __増やすことはできません__。そのため、特に __序盤の局面__ では __今回の記事で説明した理由__ では深さの上限を増やしても __精度は上がりません__。それにも関わらず深さの上限を増やすと __一般的に精度が上昇する__ のは __別の理由があるから__ です。その理由については次回の記事で説明しますが、簡単に言うと __深さの上限を深くする__ ことで __より多くの局面の評価値を計算__ し、その中から __総合的に最善手を選択することができる__ ことが理由です。別の言葉で説明すると、__より広い視野__ で最善手を選択することができるということです。

なお、オセロや将棋のようなゲームであっても、ゲームの __決着が間近の局面__ をルートノードとする __部分木__ は __深さが浅くノードの数が少ない__ ため __深さの上限を部分木の深さ以上__ にして __計算を行うことができる__ 可能性が高くなります。__そのような場合__ は、ゲームの決着がついた局面の評価値を正確に計算できる静的評価関数であれば、今回の記事で説明した理由から深さの上限を増やすことで __正確な最善手を計算できる__ ようになります。

# 人間のゲームでの思考と深さ制限探索

__深さ制限探索__ は、__人間がゲームを遊ぶ際の思考__ と __よく似ています__。

ゲームの __初心者__ は、__現在の局面の合法手__ の中からいくつかを __着手した局面を思い浮かべ__、その中から __最も良さそうだと考えた合法手を着手__ します。このような __1 手先の局面だけ__ から着手を選択する方法は、__深さの上限を 1__ とした __深さ制限探索と同じ__ です。また、__初心者__ は局面の __形勢判断を正しく行うことができない__ ので、その思考は __精度の低い静的評価関数__ であるとみなすことができます。

ゲームの __上級者__ は、現在の局面から __数手先までの局面を思い浮かべ__、__その中から__ 最も自分にとって __有利な局面になると考えた合法手を着手__ します。このような __数手先の局面__ から着手を選択する方法は、__深さの上限を 2 以上__ とした __深さ制限探索と同じ__ です。将棋のプロは場合によっては 10 手以上先の局面まで考えながら着手を行うそうで、その場合は深さの上限を 10 以上とした深さ制限探索を行っています。またゲームの __上級者__ は局面の __形勢判断うまく行うことができる__ ので、__精度の高い静的評価関数__ であるとみなすことができます。

__初心者__ が何手も __先の局面を読むことができない理由__ の一つに、局面の __形勢判断に時間がかかる__ ということが挙げられると思います。それに対し、ゲームの __上級者__ は局面の __形勢判断を短い時間__ で行うことができるので、__同じ時間__ でも初心者よりも __より深い探索を行う__ ことができます。

上記から、ゲームの __上級者が強い理由__ は以下の点にあることがわかります。

* 局面の __形勢判断__ を __短い時間__ で __高い精度__ で行うことができる
* __何手も先__ の局面までを __考慮して着手を選択__ する

これを __深さ制限探索__ にあてはめると下記のようになります。

* __静的評価関数__ が __短い時間__ で __精度の高い__ 近似値を計算できる
* __大きな深さの上限__ で深さ制限探索を行う

人間がゲームを遊ぶ際の思考と、ゲーム木の探索には違う点もありますが、上記から __強い AI を作成__ する際に、__下記の点が重要__ であると言えるでしょう。

* __静的評価関数__ の __精度が高い__ こと
* 静的評価関数の __計算時間が短い__ こと
* 深さ制限探索の __深さの上限が多く__、__多くの局面の評価値を計算__ できる こと

なお、__深さの上限__ や __計算する局面の数を増やす__ ために必要となるのは、静的評価関数の計算時間だけでなく、αβ 法などの __効率の良い探索アルゴリズムを利用__ することも重要です。

# 今回の記事のまとめ

今回の記事では、ゲーム木に対する __深さ制限探索__ が一般的に下記のような性質を持つことを説明しました。

* __深さの上限を上げる__ と __処理時間__ が __指数関数的に増える__
* 深さの上限を上げると __評価値の精度が高くなる__。ただし、__静的評価関数__ が最低でも __決着がついた局面__ の評価値を __正確に計算できる__ 必要がある
* __深さの上限__ を __ゲーム木の深さよりも多くする__ と __深さを制限しないゲーム木の探索__ になるので、計算される評価値の __精度が 100 %__ になり、__強解決の AI を作成__ できる

また、今回の記事で検証から __深さの上限を上げる__ と __精度が高くなる理由__ には以下のようなものがあることを示しました。

* 深さの上限を上げると、正確な評価値を計算できる __決着がついた局面__ を静的評価関数が __計算する割合が増える__ ため
* 深さの上限を上げると、__より多くの着手が行われた局面__ に対して静的評価関数が評価値を計算することになる。__一般的__ に __着手が行われるほど形勢を判断しやすくなる__ ので __評価値の精度が上がる__

今回の記事中でも説明しましたが、上記の 2 種類の理由は、__決着がつくまでの手数が多い__ ゲームの __序盤の局面__ では __ほとんど効果はありません__。例えば __オセロ__ はゲームの __決着がつくまで__ ほとんどの場合で __60 回[^3]の着手__ を行う必要があります。そのため、オセロの __序盤の局面__ では深さ制限探索で静的評価関数が __決着がついた局面__ の評価値を __計算することは現実的に不可能__ です。また、オセロは __1 回の着手__ で多くのコマがひっくり返ることで __ゲーム盤の状況が大きく変わることが多い__ ため、__序盤の局面__ では着手を複数回行っても __形勢を判断しやすくなるとは限りません__。

次回の記事では、深さ上限を増やすと評価値の精度が高くなる別の理由を説明します。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/23c4d441e6fab315456a

[^1]:[前回の記事](https://qiita.com/ysgeso/items/8f4186d60dcd392b2f8d#%E5%8B%95%E4%BD%9C%E3%81%AE%E7%A2%BA%E8%AA%8D)で説明したように、__`ai_abs_dls`__ で __着手を選択__ する際の __仮引数 `maxdepth`__ は、ルートノードの __子ノードに対する__ 深さの制限探索の __深さの上限__ を表すので、〇× ゲームのゲーム開始時の局面に対する深さの上限の __最大値__ は 9 ではなく __8__ です
[^2]:真ん中のマスに優先的に着手を行う AI と対戦する場合は、最初の手番で (1, 1) のマスが開いていればそこに着手を行うので、(1, 1) に着手を行うことで決着がつくことはありません。そのためこの性質は、対戦相手がランダムな着手を行う AI である必要があります
[^3]:どちらの手番もコマを置くことができないマスしかなくなった場合は 60 未満の手数で決着がつく場合があります