Pythonで〇×ゲームのAIを一から作成する　その172　深さ制限探索と @ai_by_score の補足説明と改良

# 目次と前回の記事

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

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

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

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

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

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

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

# 深さ制限探索

これまでに紹介した __ゲーム木を探索__ することで __ミニマックス値を計算__ する、ミニマックス法や αβ 法などのアルゴリズムでは、ゲームの __決着がついた局面__ を表すリーフノードの __勝敗の状況を表す評価値__ を元に __ミニマックス値の計算__ を行ないました。ゲームの決着がついた局面では __100 % 正しい評価値__ を計算することができるので、計算された __ミニマックス値はその局面の状況を正確に表す値__ になります。従って、__この手法__ で計算されたミニマックス値を利用して作成した AI は __強解決の AI__ になります。

__この手法の問題点__ は、ミニマックス値を計算する __処理時間__ がゲーム木の中で __評価値を計算するノードの数に比例__ することです。下記は〇×ゲーム、オセロ、将棋、囲碁の局面の、同一局面を考慮した場合の種類を表す表で、ゲーム木の __全てのノードの評価値を計算__ する __ミニマックス法__ では、ゲーム開始時の局面のミニマックス値を計算するために __下記の表の数のノードの評価値の計算__ を行う必要があります。そのため __ミニマックス法__ では、〇× ゲームのような __小規模なゲーム木の場合__ は __短時間でミニマックス値を計算__ することができますが、オセロや将棋のような __大規模なゲーム木の場合__ は、ノードの数が多すぎるためミニマックス値を求めることは __現実的に不可能__ になります。

||〇×ゲーム|オセロ|将棋|囲碁|
|:--|--:|--:|--:|--:|
|局面の種類|5478|$10^{28}$|$10^{69}$|$10^{171}$|
|局面の種類の平方根|約74|$10^{14}$|$10^{34.5}$|$10^{85.5}$|

枝狩りを行う __αβ 法__ は [前回の記事](https://qiita.com/ysgeso/items/248c2dcfc35f4a231dcc#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E6%9C%80%E5%A4%A7%E5%8A%B9%E7%8E%87%E3%81%AE%E8%A8%BC%E6%98%8E)で説明したように、子ノードの数が同じである [バランス木](https://qiita.com/ysgeso/items/248c2dcfc35f4a231dcc#%E6%A4%9C%E8%A8%BC%E3%82%92%E8%A1%8C%E3%81%86%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E6%80%A7%E8%B3%AA%E3%81%A8%E6%A4%9C%E8%A8%BC%E6%96%B9%E6%B3%95)では __最も枝狩りの効率が高い場合__ は __ノードの数の平方根に比例__ する数のノードを計算する必要がありますが、上記の表のように __大規模なゲーム木の場合__ は平方根であってもノードの数が多すぎるため、ミニマックス値を求めることは __現実的に不可能__ です。

一般的に __ゲーム木のノードの数__ は深さが __1 つ深くなるたびに数倍になる__ という、__指数関数的に増加__ します。そこで __ゲーム木の探索の際__ に、計算を行う __ノードの深さを制限する__ ことで計算する __ノードの数を減らし__、__現実的な時間内に計算が終わるようする__ という、__深さ制限探索__（depth limited search）という手法が、オセロや将棋などの __大規模なゲーム木の探索__ を行う際に __良く用いられます__。

__深さ制限探索__ は、__ゲーム木を探索する任意のアルゴリズム__ に対して適用することができます。本記事では __深さ制限探索を適用する__ ゲーム木の探索 __アルゴリズムの事__ を __ベースとなるアルゴリズム__ と表記することにします。

:::note
__深さ制限探索__ は、__ゲーム木以外の様々なデータ構造を探索するアルゴリズム__ に対しても適用することができますが、__本記事では__ 深さ制限探索の __ベースとなるアルゴリズムが__ ミニマックス法や αβ 法などの、__ゲーム木の探索アルゴリズムの場合__ の説明を行います。
:::

__深さ制限探索__ はベースとなるアルゴリズムでゲーム木の探索を行う際に、探索するノードの __深さの上限を制限__ することで __処理時間を短くする代わりに__、__計算結果__ としてが正確な値ではない __近似値__ を求める __[ヒューリスティック](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 を作成することはできません__[^1]。

次回の記事で説明しますが、深さ制限探索は __一般的に下記のような性質__ があります。

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

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

参考までに深さ制限探索の Wikipedia のリンクを紹介します。

https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%88%B6%E9%99%90%E6%8E%A2%E7%B4%A2

## 評価関数

__任意の局面__ に対して __評価値を計算__ する関数のことを、__評価関数__（evaluation function）と呼びます。ゲーム木に関する深さ制限探索のアルゴリズムでは、下記の性質を持つ __静的評価関数__ を定義する必要があります。

* 任意の局面に対して、その __局面の情報だけから__ 局面の状況を表す __評価値__ と呼ばれる数値を計算する
* 評価値は __ベースとなるアルゴリズムに応じた値__ を計算する。これまでに紹介したミニマックス法などの探索アルゴリズムでは先手が有利であるほど大きな数値を計算するが、後述するネガマックス法では手番のプレイヤーが有利であるほど大きな数値を計算する

__静的__（static）とは、あらかじめ与えられた __状態が変化しない__ ことを表す用語で、静的評価関数の静的は局面の評価値を計算する際に __局面の状況を変えず__ に __その局面の情報だけから__ 評価値を計算することが名前の由来です。

一方、ミニマックス法などの __ゲーム木の探索を行うアルゴリズム__ は __局面の状況を変えた__ 子孫ノードの情報を利用して計算するので __静的評価関数ではありません__。静的の反対語は動的（dynamic）ですが、筆者の調べた範囲では静的評価関数の反対語として動的評価関数という用語はほとんど使われていないと思います。そこで、本記事では __ゲーム木の探索を行う評価関数__ のことを静的評価関数と区別して __探索ベースの評価関数__ と表記することにします。

深さ制限探索で静的評価関数を利用する必要がある理由については次回の記事でします。

一般的に、__決着がついていない局面__ の状況を、その __局面の情報だけから正確に判定することは困難__ です。そのため、__静的評価関数__ は __決着がついていない局面__ の評価値を __正しく計算できるとは限りません__。深さ制限探索が __近似値を計算する理由__ は、__静的評価関数が計算する評価値が近似値__ だからです。

逆に言えば、静的評価関数が 100 % 正確な評価値を計算できる場合は深さ制限探索の計算結果も 100 % 正しくなります。ただし、そのような静的評価関数を作成することができる場合は、その静的評価関数だけを使って最善手を計算できるので、そもそもゲーム木の探索を行う必要はありません。以後の記事では __原則として静的評価関数__ が評価値の __近似値を計算するものとします__。

### これまでに定義した評価値を計算するルールベースの AI 

本記事でこれまでに作成した ルールベースの AI の中で、__`ai1s` ~ `ai14s`__ は、キーワード引数に `calc_score=True` を記述することで __任意の局面の評価値__ を __局面の情報だけから計算する__ ことができるので __静的評価関数__ です。ただし、それらの関数が計算する評価値は「__先手__ がどれくらい有利であるか」__ではなく__、「__直前の手番のプレイヤー__ がどれくらい有利であるか」を表します。そのため、それらの関数をミニマックス法や αβ 法をベースとする深さ制限探索の評価関数として利用する場合は、__先手の手番の場合__ は評価値に __-1 を乗算__ して __符号を反転する__ 必要があります。この点の詳細については次回の記事で説明します。

また、ルールベースの AI の中で __最も強い `ai14s`__ は [以前の記事](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#ai14s-%E3%81%8C%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E9%81%B8%E6%8A%9E%E3%81%97%E3%81%AA%E3%81%84%E5%B1%80%E9%9D%A2%E3%81%AE%E6%A4%9C%E8%A8%BC)で説明したように __弱解決の AI__ なので、__一部の局面で正しい評価値を計算できません__。そのため、__`ai1s` ~ `ai14s`__ はいずれも評価値の __近似値を計算__ する静的評価関数です。

### 静的評価関数が計算する評価値の一般的な性質

ゲーム木に対する深さ制限探索で用いられる __静的評価関数の一般的な性質__ を説明します。

__深さ制限探索__ では、これまでに説明した深さを制限しないゲーム木の探索と同様に __null window search が行なわれることがある__ ので、静的評価関数が計算する __評価値として__ は、__整数の値を計算__ するのが __一般的__ なようです。本記事で定義した __[`ai11s`](https://qiita.com/ysgeso/items/70c50f75319373399871#ai2-vs-ai11s-%E3%81%AE%E6%A4%9C%E8%A8%BC%E3%81%A8-ai11s-%E3%81%AE%E4%BF%AE%E6%AD%A3) ~ [`ai14s`](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E5%8A%A0%E7%AE%97%E3%81%99%E3%82%8B%E9%9A%9B%E3%81%AE%E6%B3%A8%E6%84%8F%E7%82%B9)__ は __整数以外の評価値を計算する場合がある__ ので、 __null window search を行う__ スカウト法などをベースとする深さ制限探索で利用する場合は、評価値として __整数のみが計算されるように修正したほうが良い__ でしょう。ミニマックス法や通常の αβ 法の場合は整数以外の評価値を計算しても大きな問題はありませんが、特に理由がなければ整数を計算したほうが良いでしょう。

静的評価関数が __評価値を計算する局面__ は、以下の __3 種類に分類__ されます。

* 必ず局面の状況を正確に判定できる、__ゲームの決着がついた局面__
* __決着がついていない__ が、__局面の状況を正確に判定できる局面__。例えば 〇× ゲームの 〇 の手番で、次の着手で 〇 が勝利できる局面など
* 決着がついておらず、__局面の状況を正確に判定できない局面__

__評価値の計算方法の方針__ には様々な手法がありますが、その中の一つに __大きな正の整数__ $\boldsymbol{s}$ __を決め__、評価値を __下記の表のように計算する__ というものがあります。先手の勝利の局面の評価値を $s + 1$ としたのは、先手の必勝の局面よりも先手の勝利の局面が優先されるようにするためです。

|状況|評価値|
|--:|--:|
|__決着がついた先手の勝利の局面__|$s + 1$|
|__先手の必勝と正確に判定できる局面__|$s$|
|__先手が有利と判定する局面__| $1$ 以上 $s$ 未満の整数 |
|__決着がついた引き分けの局面__<br>__引き分けと正確に判定できる局面__<br>__互角だと判定する局面__|$0$|
|__後手が有利と判定する局面__|  $s-1$ 以上 $-1$ 以下の整数 |
|__後手の必勝と正確に判定できる局面__|$-s$|
|__決着がついた後手の勝利の局面__|$-s - 1$|

__上記の評価値__ を利用する AI は __最短の勝利を目指さない__ 最善手を計算します。__最短の勝利を目指す__ 最善手を計算する場合は $s$ と $s + 1$ の代わりに「$\boldsymbol{s}$ __+ そのゲームの最長の手数__[^2] __- 先手が勝利する局面の最短手数__」を計算することで、先手の必勝及び、先手の勝利の局面の評価値が以下のようになります。

* 評価値が $\boldsymbol{s}$ __以上__ になる
* __先手がより早く勝利できる__ 局面の評価値が __より高く__ なる

__最遅の敗北を目指す場合__ は $\boldsymbol{-s}$ の代わりに「$\boldsymbol{-s}$ __- (そのゲームの最長の手数 - 先手が敗北する局面の最短手数)__」を計算します。

上記のように評価値を計算する理由は、評価値を見るだけで __どちらがどのくらい有利であるか__、先手や後手が必勝の局面の場合は __後何手でどちらが勝利するか__ を __評価値を見て判断できるようになるから__ です。具体的には正の値で大きいほど先手が有利、0 が互角、負の値で小さいほど後手が有利という意味になります。

上記のような利点が無くなってしまいますが、__ベースとなるアルゴリズムに対応した評価値を計算する__ という __性質が満たされていれば__、上記の表とは __別の基準で評価値を計算__ しても __かまいません__。例えば以前の記事で定義したルールベースの [`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__ という の評価値を計算しています。

| 順位 | 局面の状況 | 個別 | 評価値 | 
|:-:|:--|:-:|:-:|
| 1 | __真ん中のマスに着手している__ | | `12` |
| 2 | __自分が勝利している__  | | `11` |
| 4 | __「自 2 敵 0 空 1」が 2 つ以上存在する__  | | `10` |
| 5 | __「自 2 敵 0 空 1」が 1 つ存在する__<br>__「自 1 敵 0 空 2」が x 個存在する__ | `1` (`0～1`)<br>`x` (`0～8`) | `0～9`|
| 3 | __相手が勝利できる__  | | `-1` |

## 深さ制限探索のアルゴリズム

深さ制限探索の __アルゴリズム__ は以下の通りです。

__ベースとなる__ αβ 法やスカウト法などの __ゲーム木の探索__ でノード $N$ に対するミニマックス値の近似値の計算を行う際に、下記の処理を行う。

* __深さの上限__ $\boldsymbol{d}$ を決める
* $N$ をルートノードとした、__深さが__ $\boldsymbol{d}$ __までのノード__ から構成される __部分木__ に対して下記の計算を行う
    * __リーフノード以外__ のノードの評価値の計算は、__ベースとなるゲーム木の探索と同じ方法__ で行う
    * __リーフノード__ の評価値の計算は __静的評価関数で行う__

__ベースとなる__ ゲーム木の __探索アルゴリズム__ そのものは、深さの __制限をなくし__、__リーフノードのみ__ の評価値を __100 % の精度__ で計算できる __静的評価関数__ を用いた __深さ制限探索と考える__ ことができます。

### 本記事での深さ制限探索の表記方法

本記事では __深さの上限を__ $\boldsymbol{d}$、__静的評価関数を `eval_func`__ とする __深さ制限探索(depth limited search)__ のことを下記のように表記することにします。なお、この表記法は __本記事独自__ のもので、一般的な表記法ではありません。

DLS(ベースとなるアルゴリズム, d, `eval_func`)

例えばベースとなるアルゴリズムが αβ 法、深さの上限が 3、静的評価関数が `ai2s` の場合は __DLS(αβ 法, 3, `ai2s`)__ と表記します。

__深さを制限しない__ 場合のゲーム木の探索は __深さの上限__ を __無限大__ とした深さ制限探索とみなすことができます。従って通常のミニマックス法は __DLS(ミニマックス法, ∞, `eval_func`)__ と表記することができます。ただし、この場合の __`eval_func`__ は __決着がついた局面__ の評価値を __正しく評価できる静的評価関数__ です。

__静的評価関数__ そのものは __深さが 0__ のルートノードの __計算しか行わない__ ので、__深さの上限を 0__ とした深さ制限探索です。従って静的評価関数は __DLS(なし, 0, `eval_func`)__ と表記することができます。なお、__ベースとなるアルゴリズム__ はルートノードしか計算しないため __なんでもかまわない__ ので __なし__ と表記しました。

# `@ai_by_score` が行う処理の説明と改良

__深さ制限探索__ によって着手を選択する __AI の関数__ は、深さを制限しない通常のミニマックス法や αβ 法などで着手を選択する `ai_mmdfs` などの AI と同様に、__[`@ai_by_score`](https://qiita.com/ysgeso/items/7e1d948c4b9208ab44fb#%E3%83%87%E3%82%B3%E3%83%AC%E3%83%BC%E3%82%BF%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE-ai_by_score-%E3%81%AE%E5%AE%9A%E7%BE%A9) というデコレータ式を利用して定義__ することができますが、__`@ai_by_score`__ が行う処理に __わかりづらい点がある__ と思いましたので、今回の記事ではその補足説明を行うことにし、深さ制限探索の AI の実装は次回の記事で行うことにします。デコレータについて忘れた方は[以前の記事](https://qiita.com/ysgeso/items/bd63433b7491d8a07ff5)を復習して下さい。

## 静的評価関数を `@ai_by_score` でラップした場合に行なわれる処理

先程の深さ制限探索のアルゴリズムを見た方は、これまでに本記事で定義したルールベースで局面の評価値を計算する __`ai1s` ~ `ai14s`__ が __深さ 1 を上限__ とする __深さ制限探索__ の処理を行なっていることに気づいたかもしれません。また、それらの関数は __`@ai_by_score`__ という __デコレータ式を利用して定義__ されています。そこで、最初に __`@ai_by_score` を用いて定義されたそれらの関数__ が __深さ 1 を上限__ とする __深さ制限探索__ を行うことを説明します。

__`@ai_by_score`__ がラップして __機能を拡張する上記の関数__ は __任意の局面__ に対して局面の情報だけから __直前の局面の手番__ のプレイヤーが __有利になるほど大きな値__ となる __評価値を計算__ するので、__静的評価関数__ です。

また、__`@ai_by_score`__ を利用して __定義された関数__ は下記の処理を行います。なお、下記ではラップされた静的評価関数を `eval_func` と表記します。

* __仮引数 `mb_orig`__ に代入された __局面に対して__、__合法手が着手された局面をすべて計算__ する
* 計算した __それぞれの局面の評価値__ を静的評価関数である __`eval_func`__ を呼び出すことで __計算する__
* __`eval_func` が計算する評価値__ は、`mb_orig` の局面に合法手を着手した局面の直前の手番のプレイヤー、すなわち __`mb_orig` の局面のプレイヤーが有利になるほど大きな値__ を計算する。従って、__最も高い評価値__ が計算された合法手が __`mb_orig` の局面の最善手__ となる
* __最も高い評価値__ が計算された __合法手が複数存在する場合__ は、その中から __ランダムに選んだ合法手__ を最善手として返す

上記の処理は、__`mb_orig` をルートノード__ とした部分木の __深さ 1 のノードまでの計算__ を行うので、__深さが 1 を上限__ とする __深さ制限探索__ です。

上記の __深さ制限探索__ の __ベースとなるアルゴリズム__ がミニマックス法だと思う人がいるかもしれませんが、実際にはこの後で説明するミニマックス法を改良した __ネガマックス法__ が __ベースとなるアルゴリズム__ です。上記をまとめると以下のようになります。

:::note warn
__`@ai_by_score`__ を利用して __定義された関数__ が行う処理は、__ラップされた静的評価関数を `eval_func`__ と表記すると下記のように表記できる。

__DLS(ネガマックス法, 1, `eval_func`)__
:::

### ネガマックス法

__ネガマックス法__ については[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E3%83%8D%E3%82%AC%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95%E3%81%A8%E3%83%8D%E3%82%AC%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E6%B3%95)で言及しましたが詳しく説明していませんでした。__`@ai_by_score`__ を利用して定義した関数が行う処理を __理解するために必要__ となるので、ネガマックス法について説明します。

__ミニマックス法__ は、__すべてのノード__ で __先手が有利なほど大きな値__ となる評価値を計算するアルゴリズムで、下記のように __max ノードと min ノード__ で __行う処理が異なります__。

* 先手が有利なほど大きな値となるようにリーフノードの評価値を計算する
* 先手が最も有利な着手を選択する必要がある max ノードの評価値として、子ノードの評価値の最大値を計算する
* 後手が最も有利な着手を選択する必要がある min ノードの評価値として、子ノードの評価値の最小値を計算する

それに対して __ネガマックス法__ は、__max ノードと min ノード__ で __同じ方法で評価値を計算する__ ようにミニマックス法を改良したアルゴリズムで、プログラムを __ミニマックス法よりも簡潔に記述できる__ という利点があります。

ネガマックス法は __すべてのノード__ で、__ノードの局面の手番のプレイヤーが有利なほど大きな値__ となる評価値を計算するアルゴリズムで、下記のように __ノードの種類に関わらず同じ方法__ で各ノードの __評価値を計算__ します。

* その局面の手番のプレイヤーが有利なほど大きな値となるようにリーフノードの評価値を計算する
* ノードの種類に関わらず、下記の手順でノードの評価値を計算する
    * __子ノードの評価値__ に __-1 を乗算して符号を反転__ させる
    * 上記で符号を反転した子ノードの評価値の __最大値__ をそのノードの評価値とする

上記のアルゴリズムで __すべてのノード__ で __その手番のプレイヤーにとって最も有利__ な子ノードの __評価値が計算される__ 理由は以下の通りです。

__先手の手番である max ノード__ の場合は、下記の理由から __先手にとって最も有利__ な子ノードの評価値が計算されます。

* max ノードの __子ノードの min ノード__ では __後手が有利なほど大きな値__ となる評価値が計算される
* max ノードの子 __ノードの評価値に -1 を乗算して符号を反転__ すると、__先手が有利なほど大きな値__ となる評価値に __変換される__
* 従って、__符号を反転した子ノードの評価値の最大値__ は、__先手にとって最も有利__ な子ノードの評価値となる

__後手の手番である min ノード__ の場合は、下記の理由から __後手にとって最も有利__　な子ノードの評価値が計算されます。

* min ノードの __子ノードの max ノード__ では __先手が有利なほど大きな値__ となる評価値が計算される
* min ノードの子 __ノードの評価値に -1 を乗算して符号を反転__ すると、__後手が有利なほど大きな値__ となる評価値に __変換される__
* 従って、__符号を反転した子ノードの評価値の最大値__ は、__後手にとって最も有利__ な子ノードの評価値となる

__ネガマックス法__ という __名前__ は、子ノードの評価値の符号の __反対（negative）__ を計算することで、常に子ノードの評価値の __最大値（maximum）__ を計算することが由来です。
### ネガマックス法の実装例

__ネガマックス法__ は、ミニマックス法と比べて max ノードと min ノードで行う __処理を 1 つにまとめる__ ことができるという __利点がある__ ので __実際に良く使われます__。ただし、__プログラムの意味がわかりづらくなる__ という欠点があるので、本記事ではこれまで深さを限定しないミニマックス法を実装する際には採用しませんでした。

下記は、__ミニマックス法__ で計算を行う __[`ai_mmdfs`](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#ai-%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE-ai_mmdfs-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ 内で定義された、__ノードの評価値を計算__ するローカル関数 __[`mm_search`](https://qiita.com/ysgeso/items/66fdfcc4c732277bcb82#%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2%E3%81%AB%E3%82%88%E3%82%8B%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95%E3%81%AE%E5%AE%9F%E8%A3%85)__ の定義です。このプログラムでは、__17 ~ 20 行目__ で __max ノードと min ノード__ で行う処理を __別々に記述__ しています。

```python
 1  def mm_search(mborig):
 2      nonlocal count
 3      count += 1
 4      if mborig.status == Marubatsu.CIRCLE:
 5          return 1
 6      elif mborig.status == Marubatsu.CROSS:
 7          return -1
 8      elif mborig.status == Marubatsu.DRAW:
 9          return 0
10      
11      legal_moves = mborig.calc_legal_moves()
12      score_list = []
13      for x, y in legal_moves:
14          mb = deepcopy(mborig)
15          mb.move(x, y)
16          score_list.append(mm_search(mb))
17      if mborig.turn == Marubatsu.CIRCLE:
18          return max(score_list)
19      else:
20          return min(score_list)
```

下記は、`mm_search` を __ネガマックス法の処理__ を行うように __修正したプログラム__ です。nega max search なので関数の名前を __`nm_search`__ に変更しました。修正点は以下のとおりです。

* __1 行目__：関数名を `nm_search` に修正した
* __4 ~ 13 行目__：__リーフノード__ の評価値の計算処理を、__手番のプレイヤーが有利なほど大きな値を計算__ するように修正する。具体的には 11、12 行目で __後手の × の手番の場合__ に評価値の __符号を反転__ する
* __20 行目__：子ノードの評価値を list に登録する際に、`nm_search` で計算した子ノードの評価値の __符号を反転した値__ を登録する
* __21 行目__：__常に__ `score_list` の __最大値を計算__ するように修正する

```python
 1  def nm_search(mborig):
 2      nonlocal count
 3      count += 1
 4      if mborig.status != Marubatsu.PLAYING:
 5          if mborig.status == Marubatsu.CIRCLE:
 6              score = 1
 7          elif mborig.status == Marubatsu.CROSS:
 8              score = -1
 9          elif mborig.status == Marubatsu.DRAW:
10              score = 0
11          if mborig.turn == Marubatsu.CROSS:
12              score *= -1
13          return score
14      
15      legal_moves = mborig.calc_legal_moves()
16      score_list = []
17      for x, y in legal_moves:
18          mb = deepcopy(mborig)
19          mb.move(x, y)
20          score_list.append(-nm_search(mb))
21      return max(score_list)
```

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

```diff_python
-def mm_search(mborig):
+def nm_search(mborig):
    nonlocal count
    count += 1
-   if mborig.status == Marubatsu.CIRCLE:
-       return 1
-   elif mborig.status == Marubatsu.CROSS:
-       return -1
-   elif mborig.status == Marubatsu.DRAW:
-       return 0
+   if mborig.status != Marubatsu.PLAYING:
+       if mborig.status == Marubatsu.CIRCLE:
+           score = 1
+       elif mborig.status == Marubatsu.CROSS:
+           score = -1
+       elif mborig.status == Marubatsu.DRAW:
+           score = 0
+       if mborig.turn == Marubatsu.CROSS:
+           score *= -1
+       return score
    
    legal_moves = mborig.calc_legal_moves()
    score_list = []
    for x, y in legal_moves:
        mb = deepcopy(mborig)
        mb.move(x, y)
-       score_list.append(mm_search(mb))
+       score_list.append(-nm_search(mb))
-   if mborig.turn == Marubatsu.CIRCLE:
-       return max(score_list)
-   else:
-       return min(score_list)
+   return max(score_list)
```
</details>

__ネガマックス法__ では、21 行目のように __子ノードからノードの評価値を計算する処理__ は __1 つにまとまります__ が、__リーフノード__ の評価値の __計算処理__ と、__子ノードの評価値__ を計算する 20 行目の __処理の意味がわかりづらくなる__ という欠点があります。

:::note
`ai_mmdfs` の中の `mm_search` を `nm_search` に置き換えるだけではネガマックス法にはなりません。それ以外の部分もネガマックス法に合わせて修正する必要があります。興味がある方は実際に実装してみて下さい。
:::

### ネガアルファ法とネガスカウト法

__αβ 法__ や __スカウト法__ なども __同様の方法__ で max ノードと min ノードで __行われる処理をまとめる__ ことができ、それぞれを __ネガアルファ法__、__ネガスカウト法__ と呼びます。なお、__ネガアルファ法__ では、子ノードの評価値の符号を反転させるだけでなく、子ノードの計算を行う際に __ウィンドウの範囲__ を (α 値, β 値) ではなく __(－β 値, －α 値)__ とする必要があるため、__さらにわかりづらくなります__。ネガスカウト法でも同様です。そのため、本記事ではわかりやすさを重視してネガアルファ法とネガスカウト法の実装は行いません。

参考までにネガマックス法、ネガアルファ法、ネガスカウト法の疑似コードが載っている Wikipedia のリンクを下記に紹介します。

https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95

https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E3%83%BB%E3%83%99%E3%83%BC%E3%82%BF%E6%B3%95

https://ja.wikipedia.org/wiki/Negascout

:::note
MTD(f) 法はルートノードのミニマックス値を、null window search のみを利用して行う手法なので、ネガ MTD(f) 法のような手法はありません。
:::

### `@ai_by_score` を利用して定義された関数が行う処理

__`@ai_by_score`__ を利用して定義された関数が行う処理が __DLS(ネガマックス法, 1, `eval_func`)__（ネガマックス法で深さが 1 を上限とする深さ制限探索）であることを示します。

下記は、__`@ai_by_score`__ を利用して __定義された関数__ が行う処理の再掲です。__`mb_orig`__ から見て __深さが 1 のノードまでしか処理を行っていない__ ので、__深さの上限を 1__ とする __深さ制限探索__ を行っていることは明らかです。

* __仮引数 `mb_orig`__ に代入された __局面に対して__、__合法手が着手された局面をすべて計算__ する
* 計算した __それぞれの局面の評価値__ を静的評価関数である __`eval_func`__ を呼び指すことで __計算する__
* __`eval_func` が計算する評価値__ は、`mb_orig` に合法手を着手した局面の直前の手番のプレイヤー、すなわち __`mb_orig` の局面のプレイヤーが有利になるほど大きな値__ を計算する。従って、__最も高い評価値__ が計算された合法手が __`mb_orig` の局面の最善手__ となる
* __最も高い評価値__ が計算された __合法手が複数存在する場合__ は、その中から __ランダムに選んだ合法手__ を最善手として返す

静的評価関数 __`eval_func`__ は __直前の局面の手番__ のプレイヤーが __有利になるほど大きな値__ となる評価値を計算するので、__親ノードの局面の手番__ のプレイヤーが __有利になるほど大きな評価値を計算__ することになります。__先ほどのネガマックス法の実装例の `nm_search`__ では、子ノードの評価値を計算する __関数の返り値の符号を反転__ させていましたが、__`@ai_by_score`__ を利用して定義された関数では __子ノードの評価値の符号を反転する処理__ を、__`eval_func` の処理の中__ で行なっていることになります。

上記から、__`@ai_by_score`__ を利用して定義された関数が行う処理が __DLS(ネガマックス法, 1, `eval_func`)__ であることが示されました。

### `@ai_by_score` をネガマックス法で処理を行うように実装した理由

本記事で、__`@ai_by_score`__ を先程わかりづらいと説明した __ネガマックス法で処理を行うように実装した理由__ は以下の通りで、ミニマックス法やネガマックス法の __性質を意識して決めたわけではありません__。

* __`ai1s` ~ `ai14s`__ を定義した時点では、__ゲーム木の説明はまだ行なっていなかった__ ので、ミニマックス法やネガマックス法のことは考慮していなかった
* __合法手を着手した局面の評価値から最善手を選択__ する処理を行う際に、合法手を着手した局面が __合法手を着手したプレイヤーからみてどれだけ有利であるか__ を表す評価値を計算したほうが __直観的にわかりやすい__ と筆者が考えたから

## 探索ベースの評価関数を `@ai_by_score` でラップした場合に行なわれる処理

__`ai_mmdfs`__ や __`ai_abs_all`__ などの、__ゲーム木の探索__ を行うことで着手を選択する AI でも __`@ai_by_score` を利用して定義__ していますが、その場合は __`@ai_by_score`__ が __ラップする関数__ は静的評価関数ではなく、__探索ベースの評価関数__ である点が `ai1s` ~ `ai14s` と異なります。

また、その場合にゲーム木の探索を 1 種類のベースとなる探索アルゴリズムで行なっていると思った人がいるかもしれませんが、実際には __`@ai_by_score` を利用して定義したことが原因__ で、下記のように __2 種類の探索アルゴリズム__ が使われます。

* __ルートノード__ に対しては、探索ベースの評価関数を利用した __DLS(ネガマックス法, 1, 探索ベースの評価関数)__ で処理を行う
* __深さ 1 のそれぞれの子ノード__ に対しては、ゲームの決着がついた局面の評価値を計算できる静的評価関数を利用した __DLS(探索アルゴリズム, ∞, 静的評価関数)__ で処理を行う

2 種類の探索アルゴリズムを利用するのが不自然だと思う人がいるかもしれませんが、これには理由があります。どのような理由があるかについて少し考えてみて下さい。

### 2 種類の探索アルゴリズムを利用することの利点

__2 種類の探索アルゴリズム__ を利用することの __利点__ は、__探索アルゴリズムの種類に関わらず__、__最善手が複数存在する場合__ にその中から __ランダムに着手を選択できる__ ことです。__1 種類の探索アルゴリズム__ で計算を行う場合は、__ミニマックス法以外__ の探索アルゴリズムでは __そのようなことはできません__。その理由について少し考えてみて下さい。

__ミニマックス法__ では、__すべてのノードでミニマックス値が計算__ されるので、最善手が複数存在する場合に __最善手を着手した子ノードのミニマックス値が同じ__ になります。一方、αβ 法やスカウト法などの、__αβ 法を利用するアルゴリズム__ は、下記のような理由から、__最初の子ノード以外__ は __正確なミニマックス値__ を __計算できない場合__ があるため、複数の最善手が存在する場合でも、その中の __最初に見つかった最善手しかわかりません__。

* αβ 法やスカウト法では、__ルートノードの最初の子ノード__ の __αβ 値__ を計算する際の、exact value の範囲を表す __ウィンドウの範囲内__ に __計算される可能性がある評価値がすべて含まれる__ ので、__正確なミニマックス値__ を __計算できる__
* 一方、__2 番目以降の子ノード__ の αβ 値を計算する際の __ウィンドウの範囲__ は __狭くなっていく__ ため、 __ウィンドウの範囲内__ に __子ノードのミニマックス値が含まれない場合__ が生じ、その場合に計算されるのは __ミニマックス値の範囲__ となる。そのため、__2 番目以降の子ノード__ の __正確なミニマックス値__ を __計算できない場合がある__

:::note
MTD(f) 法の場合は最初の子ノードから null window search を行うので上記とは異なりますが、αβ 値の性質から最善手が複数存在する場合にその中の 1 つの最善手しか計算できない点は変わりません。本記事では説明を省略しますが、興味がある方はその理由について考えてみて下さい。
:::

わかりづらいと思いますので、具体例を挙げます。__ルートノードが max ノード__ で __子ノードのミニマックス値が 2、2、0__ の場合は、__最初と 2 番目の子ノードの合法手が最善手__ となります。__ミニマックス法__ では　__ミニマックス値__ として 2、2、0 が計算されるので __最初と 2 番目の合法手が最善手__ であることが計算できます。

一方、__αβ 法__ では下記の表のような計算が行われます。

|子ノード|ウィンドウ|ミニマックス値|計算される αβ 値|αβ 値の範囲|判明したミニマックス値|
|:--|:-:|--:|--:|--:|--:|
|__最初の子ノード__|(-∞, ∞)|2|2|exact value|2|
|__2 番目の子ノード__|(2, ∞)|2|2|fail low|2 以下|
|__3 番目の子ノード__|(2, ∞)|0|0 以上 2 以下の値|fail low|αβ 値以下|

上記の表から、__2 番目以降の子ノード__ の __αβ 値__ として __2 が計算された場合でも__、下記の理由からそれらの __ミニマックス値が 2 であると判定することはできません__。

* __2 番目の子ノード__ の αβ 値として __2 が必ず計算__ されるが __fail low の範囲__ である。そのため実際のミニマックス値が 2 であっても __2 番目の子ノード__ のミニマックス値は __2 以下であることしかわからない__
* __3 番目の子ノード__ のミニマックス値は 0 なので __fail low の範囲__ として __αβ 値は 0 以上 2 以下のいずれかの値__ が計算される。そのため、__αβ 値として 2 が計算される場合がある__ が、その場合も __3 番目の子ノード__ のミニマックス値は __2 以下であることしかわからない__

従って、__上記の計算結果からわかること__ は __以下の点だけ__ になります。

* 子ノードの __ミニマックス値の最大値が 2__ である
* 子ノードの中で __最大のミニマックス値__ を持つのは __最初の子ノード__ である

このように __ルートノード__ から __ミニマックス法以外__ の探索アルゴリズムで計算を行う場合は、__最善手は最初にみつかったもののみ__ しかわかりません。__そのような AI でも構わない場合__ は __1 つの探索アルゴリズムで計算を行ってもかまいません__。また、その場合は __1 種類の最善手しか選択されなくなる代わり__ に、ルートノードの 2 番目以降の子ノードの αβ 値を計算する際の __ウィンドウが狭くなる__ ので __枝狩りの効率を向上__ させることができます。本記事では実装しませんが、興味がある方はそのような AI を実装してみて下さい。

一方、__ルートノード__ に対して探索ベースの評価関数を利用した __DLS(ネガマックス法, 1, 探索ベースの評価関数)__ で処理を行うことで、すべての子ノードで正確なミニマックス値を計算することができるようになるので、__複数の最善手がある場合__ でも、__そのすべてを正しく計算__ できるようになります。

:::note warn
__探索ベースの評価関数__ を __`@ai_by_score` でラップ__ することで下記の処理が行われ、__複数の最善手がある場合__ にその中から __ランダムな着手を行うことができる__。

* __ルートノード__ に対しては、探索ベースの評価関数を利用した __DLS(ネガマックス法, 1, 探索ベースの評価関数)__ で処理を行う
* __深さ 1 のそれぞれの子ノード__ に対しては、ゲームの決着がついた局面の評価値を計算できる静的評価関数を利用した __DLS(探索アルゴリズム, ∞, 静的評価関数)__ で処理を行う
:::

:::note
同様の理由で αβ 法だけを利用すると、ルートノードの子ノードをミニマックス値の高い順に並べることで、合法手を良い手の順に並べるようなことはできません。
:::

## `@ai_by_score` での置換表の共有

`@ai_by_score` が行う処理の説明を記述している際に、現状の `ai_mmdfs` などの __ゲーム木の探索を行う AI の関数__ では __ルートノードの子ノード__ の評価値を __探索ベースの評価関数で計算する際__ に __置換表が共有されない__ という __問題がある__ ことに気が付きました。置換表が共有されない理由について説明します。

__ゲーム木の探索__ によって __評価値を計算する関数__ では、いずれも下記のプログラムのように __ルートノードの評価値を計算する関数呼び出し__ を行う際に、__置換表を表す実引数に空の dict を記述__ して呼び出しています。下記は `ai_abs_all` の場合のプログラムですが、__他の場合でも同様__ です。そのため、`@ai_by_score` の処理の中で __ルートノードの子ノードの評価値を計算する際__ は、置換表は __毎回空の dict で初期化される__ ので置換表は共有されません。

```python
    score = ab_search(mb, {}, alpha=alpha, beta=beta)
```

これまでに紹介した __ゲーム木の探索を行うアルゴリズム__ はいずれも __置換表の利用の有無__ によって計算される __ミニマックス値が変わることはありません__。そのため、ルートノードの子ノードの __ミニマックス値を計算した後の置換表__ のデータは、__次の子ノード__ のミニマックス値を計算する際に __そのまま利用__ できます。そのような __置換表の共用__ を行なえるようにする方法について少し考えてみて下さい。

### 置換表を共有するための探索ベースの評価関数の修正

上記で説明したように、`ai_abs_all` などの __置換表を利用できる探索ベースの評価関数__ は、現状では __空の dict を置換表として計算を開始__ します。__置換表を共有できるようにするため__ には、下記のような修正を行う必要があります。

* __共有する置換表を代入__ する __仮引数を追加__ する
* __その置換表__ を使って __ルートノードの計算を開始__ する

下記はそのように置換表を利用したミニマックス法で計算を行う __`ai_mmdfs_tt` を修正__ したプログラムです。なお、互換性を重視してこれまで通り __置換表を共有しない場合にも対応__ できるような修正を行ないました。

* __6 行目__：仮引数 `tt` を、デフォルト値を `None` としたデフォルト引数として追加した
* __7、8 行目__：`tt` が `None` の場合は `tt` に空の dict を代入して初期化することで、これまで通りに置換表を共有しない場合の処理を行うようにした。なお、`tt` の __デフォルト値を空の dict としてはいけない理由__ について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/1dbfec99a08b8996f53c)を復習すること
* __9 行目__：`tt` を置換表としてルートノードの計算を開始するように修正する

```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_mmdfs_tt(mb, debug=False, tt=None, shortest_victory=False):
元と同じなので省略
 7      if tt is None:
 8          tt = {}
 9      score = mm_search(mb, tt)
10      dprint(debug, "count =", count)
11      if mb.turn == Marubatsu.CIRCLE:
12          score *= -1
13      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_mmdfs_tt(mb, debug=False, tt=None, shortest_victory=False):
    count = 0
    def mm_search(mborig, tt):
        nonlocal count
        count += 1

        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        boardtxt = mborig.board_to_str()
        if boardtxt in tt:
            return tt[boardtxt]
        
        legal_moves = mborig.calc_legal_moves()
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(mborig)
            mb.move(x, y)
            score_list.append(mm_search(mb, tt))
        if mborig.turn == Marubatsu.CIRCLE:
            score = max(score_list)
        else:
            score = min(score_list)
            
        from util import calc_same_boardtexts

        boardtxtlist = calc_same_boardtexts(mborig)
        for boardtxt in boardtxtlist:
            tt[boardtxt] = score
        return score
    
    if tt is None:
        tt = {}
    score = mm_search(mb, tt)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
from copy import deepcopy

@ai_by_score
-def ai_mmdfs_tt(mb, debug=False, shortest_victory=False):
+def ai_mmdfs_tt(mb, debug=False, tt=None, shortest_victory=False):
元と同じなので省略
+   if tt is None:
+       tt = {}
-   score = mm_search(mb, {})
+   score = mm_search(mb, tt)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

### 置換表の共有方法

次に、上記の修正を行った `ai_mmdfs_tt` を使って、__置換表を共有する方法__ について少し考えてみて下さい。

置換表を共有するために `@ai_by_score` を修正する必要があると思った方がいるかもしれませんが、__`@ai_by_score` を修正する必要はありません__。置換表を共有するためには、下記のプログラムのように キーワード引数 __`tt={}`__ を記述して `ai_mmdfs_tt` を呼び出すだけで済みます。なお、下記は __ゲーム開始時の局面の__ のミニマックス値を __置換表を共有__ して計算するプログラムで、__それぞれの子ノード__ の評価値を計算する際に __計算されたノードの数__ を表示するために、キーワード引数 __`debug=True`__ を記述しました。

```python
mb = Marubatsu()
ai_mmdfs_tt(mb, tt={}, debug=True)
```

実行結果

```
Start ai_by_score
Turn o
...
...
...

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn x
O..
...
...

count = 1820
score 0 best score -inf
UPDATE
  best score 0
  best moves [(0, 0)]
====================
move (1, 0)
Turn x
.O.
...
...

count = 421
score 0 best score 0
APPEND
  best moves [(0, 0), (1, 0)]
====================
略
```

キーワード引数 __`tt={}` を記述するだけ__ で __置換表が共有されるようになる理由__ について説明します。__`@ai_by_score`__ では、ルートノードである `mborig` の __子ノードの評価値を計算する処理__ を __ラッパー関数 `wrapper` 内__ の下記のプログラムで行っています。なお、説明に必要がない処理は省略しました。

```python
1  @wraps(eval_func)
2  def wrapper(mb_orig, debug=False, *args, rand=True,
3              analyze=False, calc_score=False, **kwargs):
略
4      legal_moves = mb_orig.calc_legal_moves()
5      for move in legal_moves:
6          mb = deepcopy(mb_orig)
7          x, y = move
8          mb.move(x, y)
9          score = eval_func(mb, debug, *args, **kwargs)
略
```

__`ai_mmdfs_tt(mb, tt={}, debug=True)`__ を実行すると、__ラッパー関数の仮引数に `tt` は存在しない__ ので __仮引数 `kwargs`__ には __下記の dict が代入__ されます。`**kwargs` について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/474db9ea1805993eaa34#%E3%82%AD%E3%83%BC%E3%83%AF%E3%83%BC%E3%83%89%E5%BC%95%E6%95%B0%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B%E5%8F%AF%E5%A4%89%E9%95%B7%E5%BC%95%E6%95%B0)を復習して下さい。

```
{
    "tt": {}
}
```

従って、__最初の子ノードの評価値を計算__ する際の __`kwargs` には上記の dict が代入__ された状態で呼び出されるので、__9 行目__ が行う処理は __`ai_mmdfs_tt(mb, debug, tt={})`__ となり、__空の dict を置換表として計算__ が行われます。

__最初の子ノードの評価値を計算__ すると、__置換表の値が更新される__ ので __`kwargs`__ は __以下の内容で更新__ されます。

```
{
    "tt": 最初の子ノードの計算によって更新された置換表を表す dict
}
```

従って、__次の子ノード__ に対して __9 行目で行う処理__ は __`ai_mmdfs_tt(mb, debug, tt=更新された置換表)`__ となり、最初の子ノードの評価値を計算した際の __置換表が共有される__ ことになります。__以後の子ノード__ の評価値を計算する際も __同様に同じ置換表が共有__ されます。 

下記は、先程の実行結果の中から __計算されたノードの数__ を抜き出し、その __合計を計算__ した表です。__四隅__ に着手を行う 1、3、7、9 番目の子ノードと、__四辺__ に着手を行う 2、4、6、8 番目の子ノードの局面は __同一局面__ なので、__それぞれの最初以外の子ノードの計算__ は __置換表のデータを利用できる__ ため計算されたノードの数が __1 になる__ ことが確認できます。

|子ノード|count|
|--:|--:|
|1|1820|
|2|421|
|3|1|
|4|1|
|5|23|
|6|1|
|7|1|
|8|1|
|9|1|
|合計|2270|

次に、下記のプログラムでキーワード引数 `tt={}` を __記述しない__ ことで、__ルートノード__ のミニマックス値を __置換表を共有せずに__ 計算し、その結果を比較することにします。

```python
ai_mmdfs_tt(mb, debug=True)
```

実行結果

```
Start ai_by_score
Turn o
...
...
...

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn x
O..
...
...

count = 1820
score 0 best score -inf
UPDATE
  best score 0
  best moves [(0, 0)]
====================
move (1, 0)
Turn x
.O.
...
...

count = 1817
score 0 best score 0
APPEND
  best moves [(0, 0), (1, 0)]
====================
略
```

下記は、実行結果の中から計算されたノードの数を抜き出し、その合計を計算した表です。四隅に着手を行う 1、3、7、9 番目の子ノードと、四辺に着手を行う 2、4、6、8 番目の子ノードの局面は __同一局面__ ですが、置換表を共有しないため __同じ数のノードが計算__ されていることが確認できます。

|子ノード|count|
|--:|--:|
|1|1820|
|2|1817|
|3|1820|
|4|1817|
|5|643|
|6|1817|
|7|1820|
|8|1817|
|9|1820|
|合計|15191|

置換表を __共有する__ 場合の __合計は 2270__、__共有しない__ 場合の __合計は 15191__ になることから、__置換表を共有__ することで __大幅に処理の効率を上げることができる__ ことが確認できました。

### 置換表を共有した場合に強解決の AI であることの確認

__置換表を共有した場合の `ai_mmdfs_tt`__ が強解決の AIであることを下記のプログラムで確認すると、実行結果から __強解決の AI であることが確認__ できました。

```python
from util import Check_solved

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

実行結果

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

### 処理時間の差の確認

上記では処理時間が 00:00 と表記されていることから __1 秒以内で処理が終わる事__ が確認できます。また、また、__VSCode のセル__ には __計算時間が 0.3 秒__ と表示されていました。

一方、下記のプログラムで __置換表を共有しない__ 場合で __同じ処理__ を行うと、実行結果から処理時間が 00:05 と __約 5 秒かかった__ ことが確認できます。また、VSCode のセルには __計算時間が 5.2 秒__ と表示されます。

```python
Check_solved.is_strongly_solved(ai_mmdfs_tt)
```

実行結果

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

上記から、__置換表を共有__ することで __`Check_solved.is_strongly_solved` の処理__ が __約 20 倍弱__ ほど __速く計算できる__ ことが確認できました。

次に、__実戦での処理時間の差を比較__ するために __`ai2s` とのランダムな対戦__ を __100 回行った場合で比較__ することにします。なお、対戦回数を 100 回としたのは、1000 回だと置換表を共有しない場合の処理時間に時間がかかりすぎるからです。

下記は __置換表を共有しない `ai_mmdfs`__ VS `ai2s` の対戦を 100 回行うプログラムで、実行結果から __処理時間が 02:26__ と、__約 150 秒__ ほどかかったことが確認できます。

```python
from ai import ai2s, ai_match

ai_match(ai=[ai_mmdfs_tt, ai2s], match_num=100)
```

実行結果

```
ai_mmdfs_tt VS ai2s
100%|██████████| 100/100 [02:26<00:00,  1.46s/it]
count     win    lose    draw
o          89       0      11
x          74       0      26
total     163       0      37

ratio     win    lose    draw
o       89.0%    0.0%   11.0%
x       74.0%    0.0%   26.0%
total   81.5%    0.0%   18.5%
```

下記は __置換表を共有する `ai_mmdfs`__ VS `ai2s` の対戦を 100 回行うプログラムで、実行結果から処理時間が 00:00 と、1 秒以内で処理が完了したことが確認できます。

```python
ai_match(ai=[ai_mmdfs_tt, ai2s], params=[{"tt": {}}, {}], match_num=100)
```

実行結果

```
ai_mmdfs_tt VS ai2s
100%|██████████| 100/100 [00:00<00:00, 103.11it/s]
count     win    lose    draw
o          98       0       2
x          74       0      26
total     172       0      28

ratio     win    lose    draw
o       98.0%    0.0%    2.0%
x       74.0%    0.0%   26.0%
total   86.0%    0.0%   14.0%
```

上記の結果から、__実戦__ においても __置換表の共有によって大幅な処理時間の短縮__ を行えることが確認できました。

### 他の置換表を利用する関数の修正

__他の置換表を利用する AI の関数__ も、__同様の方法で置換表を共有__ することができるようになります。そこで、__αβ 法の `ai_abs_all`__、__スカウト法の `ai_scout`__、__MTD(f) 法の `ai_mtdf`__ の 3 つの関数を __置換表を共有できるように修正__ することにします。なお、他の置換表を利用することができる αβ 法の関数については `ai_abs_all` で同じ処理を行うことができるので修正は省略します。

下記は修正したプログラムですが、表記が長くなるので折りたたみました。また、修正箇所は `ai_mmdfs_tt` とほぼ同じなので説明は省略します。

<details><summary><strong><code>ai_abs_all</code>の修正プログラム</strong></summary>

```python
@ai_by_score
def ai_abs_all(mb, debug, shortest_victory=False, init_ab=False,
               use_tt=False, tt=None, 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
    alpha = min_score if init_ab else float("-inf")
    beta = max_score if init_ab else float("inf")

    if tt is None:
        tt = {}
    score = ab_search(mb, tt=tt, alpha=alpha, beta=beta)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

<details><summary><strong><code>ai_scout</code>の修正プログラム</strong></summary>

```python
@ai_by_score
def ai_scout(mb, debug=False, shortest_victory=False,
             init_ab=False, use_tt=False, tt=None, 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:
            x, y = legal_moves[0]
            mb = deepcopy(mborig)
            mb.move(x, y)
            score = ab_search(mb, tt, alpha, beta)
            alpha = max(alpha, score)
            if score < beta:
                for x, y in legal_moves[1:]:
                    mb = deepcopy(mborig)
                    mb.move(x, y)
                    score = max(score, ab_search(mb, tt, alpha, alpha + 1))
                    if score >= beta:
                        break
                    elif score > alpha:
                        score = max(score, ab_search(mb, tt, alpha, beta))
                        if score >= beta:
                            break
                        alpha = max(alpha, score)
        else:
            x, y = legal_moves[0]
            mb = deepcopy(mborig)
            mb.move(x, y)
            score = ab_search(mb, tt, alpha, beta)
            beta = min(beta, score)
            if score > alpha:
                for x, y in legal_moves[1:]:
                    mb = deepcopy(mborig)
                    mb.move(x, y)
                    score = min(score, ab_search(mb, tt, beta - 1, beta))
                    if score <= alpha:
                        break
                    elif score < beta:
                        score = min(score, ab_search(mb, tt, alpha, beta))
                        if score <= alpha:
                            break
                        beta = min(beta, score)   
            
        if use_tt:
            from util import calc_same_boardtexts

            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
    alpha = min_score if init_ab else float("-inf")
    beta = max_score if init_ab else float("inf")

    if tt is None:
        tt = {}
    score = ab_search(mb, tt=tt, alpha=alpha, beta=beta)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

<details><summary><strong><code>ai_mtdf</code>の修正プログラム</strong></summary>

```python
@ai_by_score
def ai_mtdf(mb, debug=False, shortest_victory=False,
             init_ab=False, use_tt=False, tt=None, 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")

    if tt is None:
        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>

下記のプログラムでそれぞれについて置換表を共有した場合に強解決の AI であるかを確認すると、__いずれも強解決の AI であることが確認__ できます。なお、スカウト法では最善手を推定するための関数として `ai14s` を利用しました。

```python
from ai import ai14s

Check_solved.is_strongly_solved(ai_abs_all, params={"use_tt": True, "tt": {}})
Check_solved.is_strongly_solved(ai_scout, params={"use_tt": True, "tt": {}, "ai_for_mo": ai14s})
Check_solved.is_strongly_solved(ai_mtdf, params={"use_tt": True, "tt": {}, "f": 0})
```

実行結果

```
100%|██████████| 431/431 [00:00<00:00, 1549.70it/s]
431/431 100.00%
100%|██████████| 431/431 [00:00<00:00, 576.61it/s]
431/431 100.00%
100%|██████████| 431/431 [00:00<00:00, 1221.49it/s]
431/431 100.00%
```

また、下記のプログラムで __αβ 法__ で計算を行う __`ai_abs_all`__ VS `ai2s` の対戦を __置換表を共有しない場合とする場合__ で行い、__処理時間を比較__ することにします。

```python
ai_match(ai=[ai_abs_all, ai2s], params=[{"use_tt": True, "tt": {}}, {}], match_num=100)
```

実行結果

```
ai_abs_all VS ai2s
100%|██████████| 100/100 [01:11<00:00,  1.41it/s]
count     win    lose    draw
o          96       0       4
x          79       0      21
total     175       0      25

ratio     win    lose    draw
o       96.0%    0.0%    4.0%
x       79.0%    0.0%   21.0%
total   87.5%    0.0%   12.5%
```

```python
ai_match(ai=[ai_abs_all, ai2s], params=[{"use_tt": True}, {}], match_num=100)
```

実行結果

```
ai_abs_all VS ai2s
100%|██████████| 100/100 [00:01<00:00, 98.88it/s]
count     win    lose    draw
o         100       0       0
x          75       0      25
total     175       0      25

ratio     win    lose    draw
o      100.0%    0.0%    0.0%
x       75.0%    0.0%   25.0%
total   87.5%    0.0%   12.5%
```

実行結果から __置換表を共有しない場合は 約 70 秒__、__共有する場合は約 1 秒__ となり、__αb 法__ の場合でも __置換表を共有したほうが処理速度が大幅に短くなる__ ことが確認できました。

本記事では省略しますが、興味がある方は `ai_scout` と `ai_mtdf` でも同様の比較を行ってみて下さい。

# 今回の記事のまとめ

今回の記事では __深さ制限探索__ について説明し、`ai1s` ~ `ai14s` の __ルールベースで評価値を計算する AI__ が __DLS(ネガマックス法, 1, `eval_func`)__（ネガマックス法で深さが 1 を上限とする深さ制限探索）という __処理を行っていた__ ことを説明しました。

また、__`@ai_by_score`__ を利用して __ゲーム木の探索を行う AI__ が __2 種類の探索アルゴリズム__ で計算を行なっていることを説明しました。

最後に、__ゲーム木の探索を行う AI__ で __置換表を共有__ できるように改良することで、__処理時間を大幅に短縮__ できるようにしました。

次回の記事では `@ai_by_score` を利用した深さ制限探索の処理を実装します。

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

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

# 次回の記事

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

[^1]:深さの上限をゲーム木の深さよりも深く設定した場合や、後述する評価関数の精度が 100 % の場合は強解決の AI を作成することができますが、大規模なゲーム木のゲームでそのような処理を行うことは一般的には不可能です
[^2]:〇×ゲームの場合は 9、オセロの場合は 64 マスから最初に配置された 4 マスを除いた 60 です。将棋や囲碁のように最長の手数がわからない場合は、10000 のような絶対にあり得ない値を設定します