Pythonで〇×ゲームのAIを一から作成する　その165　スカウト法のアルゴリズムと性質

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/97c293d8876190849ec8

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

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

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

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

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

# スカウト法


今回の記事では、null window search を使った手法の一つである __スカウト（scout）法__ について説明します。スカウト法について記事を書いた後でいくつか勘違いしていたことに気が付きましたので、一度書いた内容を大幅に修正したため更新が遅くなりました。


スカウト法は __move ordering を前提__ とする手法ですが、[前回の記事](https://qiita.com/ysgeso/items/97c293d8876190849ec8#move-ordering-%E3%81%AE%E7%B2%BE%E5%BA%A6)で説明したように move ordering の __精度は通常は 100 % ではない__ ので、今回の記事では move ordering の __精度が 100 % ではないという前提__ で話を進めることにします。

また、max ノードと min ノードでの考え方は同じなので、今回の記事でも特に記述がなければ max ノードの場合での説明を行います。

なお、勘違いしていたのは move ordering が 100 % の場合にスカウト法で行われる処理で、その点については次回以降の記事で説明します。

参考までに Chess Programming wiki と Wikipedia のスカウト法のリンクを下記に紹介します。Wikipedia のほうはスカウト法を改良したネガスカウト法のリンクですが、行われる処理はスカウト法と本質的に同じです。スカウト法の論文などの参考文献について知りたい方は、リンク先の記事を参照して下さい。

https://www.chessprogramming.org/Scout

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

## 今回の記事で利用する記号

今回の記事では以下の記号を使って説明を行います。

* [以前の記事](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{α}$、$\boldsymbol{β}$ と表記する。また、__次の子ノードの評価値を計算する時点での α 値と β 値__ は、__α 値、β 値__ と表記して区別する
* αβ 法でノードの評価値を計算する際に下記の記号を用いる
    * α 値と β 値の範囲 を表す __[ウィンドウ](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc#%E3%82%A6%E3%82%A3%E3%83%B3%E3%83%89%E3%82%A6%E3%81%A8%E3%82%A6%E3%82%A3%E3%83%B3%E3%83%89%E3%82%A6%E5%B9%85)__ を (α 値, β 値) のように __() の記号で表記__ する
    * $\boldsymbol{i}$ __番目の子ノードの評価値__ を $\boldsymbol{s_i}$ と表記する
    * __それまでに計算されたノードの評価値__ を $\boldsymbol{s}$ と表記する。$s$ は max ノードではそれまでに計算された子ノードの評価値の最大値、min ノードでは最小値である
* $a$ と $b$ の最大値を $max(a, b)$、最小値を $min(a, b)$ と表記する

:::note
数学では $a$ より大きく $b$ より小さい範囲のように、__端を含まない範囲__ を $(a, b)$ と表記します。また、$a$ 以上 $b$ 以下の範囲のように __端を含む範囲__ を $[a, b]$ のように表記します。また、両方を組み合わせた $a$ 以上 $b$ 未満の範囲は $[a, b)$ と表記します。

このような数値の範囲のことを数学では __区間__ と呼びます。参考までに、区間に関する wikipedia のリンクを下記に示します。
:::

https://ja.wikipedia.org/wiki/%E5%8C%BA%E9%96%93_(%E6%95%B0%E5%AD%A6)

# スカウト法のアルゴリズム

__スカウト法__ は __move ordering を行う αβ 法__ に下記の __手順 3 の修正を加えた処理を行う__ というアルリズムです。下記では置換表に関する処理を省略していますが、置換表に関する処理を含め、__下記の手順 3 以外は move ordering を行う αβ 法と全く同じ処理__ を行います。

1. move ordering を行う
2. __先頭の子ノードの評価値の計算処理__ を __αβ 法と同じ__ 方法で計算する
3. __2 番目以降の子ノード__ の評価値の計算処理を以下の手順で行う。以下は $i$（$i ≧ 2$）番目の子ノードの評価値 $s_i$ を計算する場合の処理の説明である
    * __max ノード__ の場合は以下の手順で計算を行う
        1. __ウィンドウを __(α 値, α 値 + 1)__ とした αβ 法__ で $s_i$ を計算し、$s$ を更新する
        2. $s$ の値に応じて以下の処理を行う
            * __β 値 ≦__ $\boldsymbol{s}$[^1] の場合は $s$ をこのノードの評価値として処理を終了するという、__β 狩り__ の処理を行う
            * __α 値 <__ $\boldsymbol{s}$ __< β 値__ の場合は __ウィンドウを (α 値, β 値)__ とした __αβ 法と同じ方法__ で __計算しなおす__。$s$ や α 値の更新、β 狩りの処理も αβ 法と同じ
            * $\boldsymbol{s}$ __≦ α 値__ の場合は何もしない
    * __min ノード__ の場合は以下の手順で計算を行う
        1. __ウィンドウを __(β 値 - 1, β 値)__ とした αβ 法__ で $s_i$ を計算し、$s$ を更新する
        2. $s$ の値に応じて以下の処理を行う
            * $\boldsymbol{s}$ __≦ α 値__ の場合は $s$ をこのノードの評価値として処理を終了するという、__β 狩り__ の処理を行う
            * __α 値 <__ $\boldsymbol{s}$ __< β 値__ の場合は __ウィンドウを (α 値, β 値)__ とした __αβ 法と同じ方法__ で __計算 しなおす__。$s$ や β 値の更新、α 狩りの処理も αβ 法と同じ
            * __β 値 ≦__ $\boldsymbol{s}$ の場合は何もしない

__αβ 法との違い__ は以下の通りです。

* __2 番目以降の子ノード__ の評価値を計算する際に __αβ 法以下の[ウィンドウ幅](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc#%E3%82%A6%E3%82%A3%E3%83%B3%E3%83%89%E3%82%A6%E3%81%A8%E3%82%A6%E3%82%A3%E3%83%B3%E3%83%89%E3%82%A6%E5%B9%85)__ で計算を行う
* 2 番目以降の子ノードの __評価値の計算結果によって__、その子ノードの評価値を __αβ 法と同じウィンドウで計算し直す__ 場合がある

なお、__置換表に関する処理__ は αβ 法とスカウト法で __全く同じ__ なので、置換表を利用する場合とそうでない場合の両方でスカウト法を利用することができます。以後は置換表を利用しない場合の説明を行ないますが、置換表を利用する場合でも説明の内容は同じです。

# スカウト法の性質

__スカウト法__ は __move ordering の精度が 100 % でない場合__ に、__move ordering の精度が充分高ければ__ 枝狩りの効率が αβ 法 __以上になることが期待できる[^2]__ ように __αβ 法を改良__ したアルゴリズムです。

逆に言えば、__move ordering の精度が悪く__、__評価値が低いノードが先頭に並べ替えられてしまった場合__ は、スカウト法によって __枝狩りの効率__ が αβ 法よりも __悪くなる可能性が高くなります__。

先程説明したスカウト法のアルゴリズムによって上記のような性質が得られる理由について少し考えてみて下さい。

なお、スカウト法によって __どの位の枝狩りの効率の上昇が得られるか__ は、__ゲーム木の内容によっても異なります__。従って、__ゲームの種類__ や、同じゲームでも __局面の違いによって__ はスカウト法で __効率の上昇がほとんど得られない場合があります__。

## スカウト法の性質に関する筆者の誤解

先程紹介したスカウト法と同様の処理を行う [ネガスカウト法の wikipedia](https://ja.wikipedia.org/wiki/Negascout) では「NegaScout が効率よく機能するかどうかは手の並べ替えの精度に依存しており、__初めに調べる手が最善手である場合に最も効率が良くなる__」と記載されています。そのため、今回の記事では最初は以下のような説明を記述していましたが、それは __筆者の誤解である__ ことがわかったので記事を大幅に修正しました。もしかするとそのように勘違いしている人がいるかもしれませんので、下記の説明がどのように間違っているかについては次回以降の記事で説明します。

:::note alert
move ordering の精度が 100%で、先頭の子ノードの評価値が最も高い場合にスカウト法の効率が αβ 法と比較して最も高くなる。

上記の説明は __間違っている__ ので赤い背景色のノートにしました。
:::

なお、上記で引用した __Wikipedia の説明は厳密には間違ってはいない__ と思いますが、__誤解を産みやすい表現__ だと思います。その点についても次回以降の記事で説明する予定です。

# スカウト法の考え方

__スカウト法__ では __最初の子ノード__ の評価値は __αβ 法と同じ方法で計算__ されるので、最初の子ノードの評価値の __計算の効率__ と __計算結果__ である $\boldsymbol{s_1}$ の値は __変わりません__。従って、__子ノードの数が 1 以下__ の場合に行なわれる処理は __αβ 法と変わらない__ ので、以下では __子ノードが 2 つ以上ある場合について説明__ します。

## スカウト法で行われる仮定

スカウト法は、精度が高い move ordering によって __最も高い評価値の子ノードが先頭に移動した__ と __仮定__ し、__その場合に枝狩りの効率が高くなるように__ αβ 法に改良を加えたアルゴリズムです。もちろん通常は move ordering の精度は 100% ではないため、__この仮定は正しくない場合もあります__。

## null window search による効率化

__(α 値, β 値)__ をウィンドウとする __αβ 法__ は、__正確なミニマックス値を計算したい範囲をウィンドウ__ とし、__ウィンドウの範囲外が計算__ された場合は __ミニマックス値__ が __α 値 以下または β 値以上__ であることを判定することができるアルゴリズムです。

また、αβ 法では __ウィンドウ幅が狭い程__、α 狩りや β 狩りの __枝狩りが行われやすくなる__ という性質を持ちます。なお、範囲を狭くした際に枝狩りの効率が変わらない場合がありますが、__効率が悪くなることはありません__。[以前の記事](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc)で説明した __null window search__ はそのことを利用した枝狩りの効率化の手法です。

最も高い評価値の子ノードが先頭に移動するという __スカウト法の仮定が正しければ 2 番目以降のすべての子ノードの評価値__ は最初の子ノードの評価値である $\boldsymbol{s_1}$ __以下__ になり、__(__$\boldsymbol{s_1}$ __, β 値)__ というウィンドウの αβ 法で __2 番目以降の子ノードの評価値を計算__ すると、その __すべてが fail low__ となります。

スカウト法の __仮定が正しければ (__$\boldsymbol{s_1}$ __, β 値)__ というウィンドウの __β 値を__ $\boldsymbol{s_1}$ __より大きなどのような値に変更__ しても、__fail low という計算結果は変わりません__。従ってウィンドウの $\boldsymbol{s_1}$ __を変えず__ に __ウィンドウ幅を null window search になるまで減らす__ ことで、__枝狩りの効率を同じかそれ以上にする__ ことができます。これがスカウト法による効率化の考え方です。

ただし、[以前の記事](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc#%E6%9E%9D%E7%8B%A9%E3%82%8A%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%8C%E6%82%AA%E3%81%8F%E3%81%AA%E3%82%8B%E7%90%86%E7%94%B1)で説明したように、__ウィンドウ幅を 0 にしてしまうと枝狩りの効率が悪く__ なるので、実際には [以前の記事](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc#%E3%82%A6%E3%82%A3%E3%83%B3%E3%83%89%E3%82%A6%E3%81%AE%E8%A8%AD%E5%AE%9A%E6%96%B9%E6%B3%95%E3%81%AE%E8%80%83%E3%81%88%E6%96%B9)で説明したように、__ウィンドウ（exact value の範囲）の中に評価値として計算される値が必要最小限となるようなウィンドウを設定__ する必要があります。今回の場合は __ウィンドウの中__ に評価値として計算される値を __1 つも入れる必要はありません__。また、__評価値として整数のみが計算__ され、__ウィンドウの端が整数__ であることから、[以前の記事](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc#%E6%95%B4%E6%95%B0%E3%82%92%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%A8%E3%81%97%E3%81%A6%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AF%E3%82%A6%E3%82%A3%E3%83%B3%E3%83%89%E3%82%A6%E5%B9%85%E3%81%A8%E3%81%97%E3%81%A6-1-%E3%81%8C%E9%81%A9%E3%81%97%E3%81%A6%E3%81%84%E3%82%8B)で説明したように、__ウィンドウ幅として 1 を設定__ することで null window search を行うことができます。

先程のアルゴリズムで 2 番目以降の max ノードの子ノードの評価値を計算する際に __ウィンドウを (α 値, α 値 + 1)__ としたのは __枝狩りの効率が高い null window search を行うため__ です。min ノードで __(β 値 - 1, β 値)__ としたのも同様の理由です。

αβ 法とスカウト法では、2 番目以降の子ノードの評価値を計算する際に下記の処理を行い、スカウト法の __仮定が正しい場合__ はどちらも __同じ fail low の計算結果__ が得られます。

* __αβ 法__：ウィンドウが (α 値, β 値) の αβ 法
* __スカウト法__：ウィンドウが (α 値, α 値 + 1) の null window search

評価値が整数の場合は、__(α 値, β 値)__ のウィンドウ幅は __1 以上__、__(α 値, α 値 + 1)__ のウィンドウ幅は __1__ になります。従ってスカウト法の __仮定が正しければ__ スカウト法の場合の __ウィンドウ幅__ は αβ 法のウィンドウ幅 __以下__ になるため、__枝狩りの効率__ は αβ 法 __以上__ になります。

ところで、上記のアルゴリズムでは __null window search のウィンドウ__ を (${s_1}$ ,${s_1}$ + 1) ではなく、__(α 値, α 値 + 1)__ としています。その理由は少し後で説明しますが、余裕がある方はその理由について少し考えてみて下さい。

:::note
__スカウト法の実装例の多く__ は __評価値として整数が計算されることが前提__ となっており、特にその説明もなくウィンドウ幅を 1 としている場合が多いようですが、__評価値として実数が計算される場合__ は、__ウィンドウ幅を__ 何も考えずに __1 と設定するのは避けたほうが良い__ でしょう。

例えば、__評価値として実数が計算される場合__ は、αβ 法の計算の過程で子ノードの評価値を計算する際の __ウィンドウ幅が 1 未満になることがあります__。そのような場合にスカウト法の処理で __ウィンドウ幅を 1 に設定してしまうと__、__ウィンドウ幅を逆に広げてしまう__ ことになり、枝狩りの __効率が悪くなってしまうことがあります__。従って、__評価値として実数が計算される場合__ は、ウィンドウ幅を __最低でも αβ 法のウィンドウ幅よりも狭く設定することが重要__ となります。
:::

## スカウト法の仮定が間違っていた場合の処理

move ordering の精度が 100 % ではない場合は、__どれだけ精度が高くてもスカウト法の仮定が間違う__ 場合が生じ、その場合は __2 番目以降__ に __最初の子ノードよりも評価値が高い子ノードが存在__ することになります。そのため、その子ノードの評価値を計算すると __fail low ではない評価値が計算__ されますが、null window search では __正しい評価値を計算することはできない__ ので、__αβ 法と同じウィンドウで計算をやりなおします__。

ただし、スカウト法で __(α 値, α 値 + 1)__ というウィンドウで計算された評価値が __β 値以上__ の場合は以下の理由から計算をやりなおさずに、__即座に β 狩りを行うことができます__。これが先程のアルゴリズムの手順 3-2 で「__β 値 ≦__ $\boldsymbol{s}$ の場合は β 狩りを行う」とした理由です。

* αβ 法では __(α 値, β 値)__ というウィンドウで評価値を計算し、計算結果が β 値以上になった場合は β 枝狩りを行う
*  __(α 値, α 値 + 1)__ というウィンドウで計算された評価値が __β 値以上__ の場合は、α 値 < β 値なので fail high の範囲になる[^3]
* 従って __ミニマックス値は β 値以上になる__ ことが確定するので (α 値, β 値) というウィンドウで評価値を計算しなおさなくても、__β 狩りを行うことができる__

αβ 法と同じ (α 値, β 値) というウィンドウで __計算しなおした評価値__ は、最初の子ノードの評価値である __$s_1$ よりも大きいので $s$ をその値で更新し、__ 更新した $\boldsymbol{s}$ __を子ノードの評価値の最大値であると仮定__ して残りの子ノードの処理を __スカウト法のアルゴリズムで続けます__。

__move ordering の精度が高けれ__ ば、最初に最大の評価値であると仮定していた $s_1$ よりも大きな評価値は  __非常に高い確率で子ノードの最大値であると考えられる__ ので、$s$ が子ノードの評価値の最大値であるという __新しい仮定は合理的__ であると考えることができます。

なお、この場合でも __残りの子ノード__ の評価値を計算する際の __ウィンドウ__ は ($s$, $s$ + 1) ではなく、__(α 値, α 値 + 1)__ とします。その理由はこの後で説明します。

以後の子ノードで $s$ よりも大きな評価値が計算された場合の処理も同様です。

:::note warn
スカウト法の __仮定が間違っていると判明した場合__ は、__新しく計算された子ノードの評価値__ を __最大値と仮定しなおして__ 計算を続ける。
:::

### スカウト法の仮定が間違っていた場合の処理の効率

スカウト法の仮定が間違っていた場合は、αβ 法とスカウト法では以下の処理を行います。下記からわかるように、この場合は明らかに __スカウト法のほうが__ null window search を行う分だけ __処理の効率が悪くなります__。

||行う処理|
|:--|:--|
|__αβ 法__|ウィンドウが (α 値, β 値) の αβ 法|
|__スカウト法__|ウィンドウが (α 値, α 値 + 1) の null window search<br>ウィンドウが (α 値, β 値) の αβ 法|

## 総合的なスカウト法の効率

スカウト法の処理では、2 番目以降のそれぞれの __子ノードの評価値を計算する際の効率__ が、null window search の結果によって __αβ 法と比較__ して以下のようになります。

* スカウト法の __仮定が正しく__ fail low になった場合は __効率が同じか良くなる__
* スカウト法の __仮定が間違って__ おり fail low 以外になった場合は __効率が悪くなる__

従って、スカウト法の __仮定が正しい子ノード__ によって得られた __効率の改善の合計__ が、スカウト法の __仮定が間違っている子ノード__ による __効率の悪化の合計__ よりも __多い場合__ は、__全体__ としてスカウト法のほうが αβ 法よりも __効率が良くなります__。逆に __悪化の合計の方が多い場合__ は、スカウト法が αβ 法よりも __効率が悪くなる場合__ もあります。

スカウト法の __仮定__ は move ordering の __精度が高いほど正しい確率が増える__ ので、スカウト法の __効率は move ordering の精度と密接な関係__ があります。

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

:::note warn
* __スカウト法__ は __move ordering の精度が高い程__、__効率が良くなる__ ことが __期待できる__ が、必ず良くなるとは限らない
* move ordering の __精度が悪い__ と、αβ 法よりも __効率が悪くなる場合がある__
:::

## null window search のウィンドウを (α 値, α 値 + 1) とする理由  

null window search のウィンドウを (${s}$ ,${s}$ + 1) ではなく、__(α 値, α 値 + 1)__ とする
理由について説明します。

__最初の子ノード__ の評価値である $\boldsymbol{s_1}$ は、fail low、exact value、fail high の __3 種類の場合がある__ ので、__max ノード__ での __それぞれの場合__ について分けて説明します。min ノードの場合の考え方は同様なので説明は省略します。

## fail high の場合

__fail high__（$β ≦ s_1$）の場合は αβ 法の場合と同様に __β 狩りが行なわれ__、$s_1$ がこのノードの評価値として計算されます。従って、この場合は 2 番目以降の子ノードの計算は行われず、__枝狩りの効率は αβ 法と同じ__ になります。

## exact value の場合

__exact value__（$α < s_1 < β$）の場合は $\boldsymbol{α < s_1}$ となります。__max ノード__ では __α 値は__ $\boldsymbol{max(α, s)}$ __で計算__ されるので、__2 番目の子ノードの評価値__ を計算する際の __α 値 =__ $\boldsymbol{s_1}$ となります。従って、2 番目の子ノードの評価値を計算する際の null window search のウィンドウは __(α 値, α 値 + 1)__ となります。

### スカウト法の仮定が正しい場合

スカウト法の __仮定が正しければ__ 残りの子ノードの評価値はすべて $s_1$ 以下なので、それまでに計算された子ノードの評価値の最大値である $\boldsymbol{s}$ __は__ $\boldsymbol{s_1}$ __のまま更新されません__。従って、__α 値も__ $\boldsymbol{s_1}$ __のまま更新されない__ ので null window search のウィンドウは残りの子ノードですべて __(α 値, α 値 + 1)__ となります。

### スカウト法の仮定が間違っている場合

スカウト法の仮定が間違っている場合は、どこかの子ノードで $\boldsymbol{s_1}$ __よりも高い評価値が計算__ され、$\boldsymbol{s}$ __がその評価値で更新__ されます。また、$\boldsymbol{s}$ __が最も高い評価値__ として __新しく仮定される__ ので、残りの子ノードの null window search のウィンドウは __(__$\boldsymbol{s}$__,__ $\boldsymbol{s}$ __+ 1)__ になります。

先ほど説明したように $s_1$ が exact value の場合は $\boldsymbol{α < s_1}$ で、$\boldsymbol{s_1 < s}$ なので、$\boldsymbol{α < s}$ となります。また、__α 値は__ $\boldsymbol{max(α, s)}$ __で計算__ されるので、__α 値 =__ $\boldsymbol{s}$ となります。従って、残りの子ノードの null window search のウィンドウは __(α 値, α 値 + 1)__ になります。

その後の残りの子ノードの中で、スカウト法の仮定が間違っている子ノードが存在する場合も、上記と同様の理由からそのさらに後の子ノードの null window search のウィンドウも __(α 値, α 値 + 1)__ になります。

以上から、$s_1$ が exact value の場合は 2 番目以降の子ノードの null window search のウィンドウは __すべて (α 値, α 値 + 1)__ になります。

### 別の説明

上記を別の言葉で説明すると、$s_1$ が exact value の場合は常に $\boldsymbol{α < s}$ となるため、__α 値 =__ $\boldsymbol{max(α, s)}$ __=__ $\boldsymbol{s}$ となるので、ウィンドウを (α 値, α 値 + 1) とすることで __ミニマックス値が__ $\boldsymbol{s}$ __以下__ であることを null window search で判定することができます。

## fail low の場合

最初の子ノードの評価値 $s_1$ が exact value（$α < s_1 < β$）の場合は、上記で説明したように 2 番目以降の子ノードの評価値を計算する際の α 値は必ず $s$ になります。

一方、$s_1$ が __fail low__（$s_1 ≦ α$）__の場合__ は、以下の理由から 2 番目以降の子ノードの評価値を計算する際の __α 値が__ $s$ ではなく $\boldsymbol{s}$ __より大きな__ $\boldsymbol{α}$ __になる場合があります__。

* $i$ 番目までの __子ノードの評価値がすべて__ $\boldsymbol{α}$ __未満の場合__ は、それまでの子ノードの評価値の最大値である $\boldsymbol{s}$ __は__ $\boldsymbol{α}$ __未満となる__
* $α 値 = max(s, α)$ なので、__その場合は α 値は__ $s$ ではなく $\boldsymbol{s}$ __より大きな__ $\boldsymbol{α}$ __になる__

このように、$s_1$ が __fail low の場合__ は $\boldsymbol{s}$ __< α 値 となる場合がある__ ので、その判定を行う null window search の __ウィンドウを (__$s$__,__ $s$ __+ 1) のように修正する必要がある__ と思った人がいるかもしれませんが、__fail low の場合も__ exact value と同様に __ウィンドウを (α 値, α 値 + 1) として計算したほうが効率が良くなります__。その理由について少し考えてみて下さい。

### 常にウィンドウを (α 値, α 値 + 1) としたほうが良い理由

まず、$\boldsymbol{s < α}$ __= α 値__ の場合にウィンドウを ($s$, $s$ + 1) とした場合と (α 値, α 値 + 1) とした場合で __同じ評価値が計算される__ ことを示します。

__αβ 法__ では max ノードで __fail low__ である __$\boldsymbol{α}$ 以下の評価値が計算された場合__ は、min ノードである __親ノードで α 狩りが行われるの__ で、__$\boldsymbol{α}$ 以下の__ どのような __評価値が計算された場合__ でも __親ノードの評価値の計算に影響を与えません__。従って、null window search で子ノードの評価値が $\boldsymbol{α}$ __以下である事が判定されても__、$α$ よりも小さい $\boldsymbol{s}$ __以下である事が判定されても__、最終的に計算される __評価値は同じになります__。

次に、ウィンドウを (α 値, α 値 + 1) とした場合のほうが __効率が良くなる場合がある__ ことを示します。

$\boldsymbol{s < α}$ __の場合__ に、move ordering の精度が低いため __残りの子ノードの中__ に $\boldsymbol{s}$ __より大きく__ $\boldsymbol{α}$ = __α 値以下__ の評価値のノードが存在した場合は、その子ノードの __null window search__ で以下のように __α 値以下であることを判定__ したほうが __処理の効率が良くなります__。

* null window search で __α 値以下__ の評価値であることを判定した場合は fail low になる
* null window search で $\boldsymbol{s}$ __以下__ の評価値であることを判定した場合は __null window search が fail low にならない__ ので、__αβ 法と同じウィンドウで計算をやり直す必要が生じる__

上記が null window search のウィンドウを __常に (α 値, α 値 + 1) としたほうが良い__ 理由です。

:::note
ウィンドウを (α 値, α 値 + 1) と ($s$, $s + 1$) にした場合では、子孫ノードで α 狩りや β 狩りが行なわれる条件が異なるので枝狩りの効率が異なる場合がありますが、__どちらも null window search なのでそれほど大きな差はない__ と思います。
:::

:::note
スカウト法がピンとこない人がいるかもしれませんので、__スカウト法の考え方__ について別の言葉で説明します。

スカウト法は、__以下と類似する考え方__ で __最も高い点数を計算__ するアルゴリズムです。なお、__実際のスカウト法__ は max ノードと min ノードでの違い、α 狩りと β 狩りなどが行なわれる、αβ 法と null window search の効率が変わらない場合があるなど、 __いくつかの点で下記の手順と異なります__。下記は __厳密なスカウト法の手順ではなく__、スカウト法の __おおまかな考え方__ だと思って下さい。

1. 手間のかからない簡潔な方法で最も点数が高いと思われる候補を選ぶ（move ordering に相当）
2. その候補の点数 $s$ を計算する（最初の子ノードの αβ 法での計算に相当）
3. 残りの候補に対して下記の処理を行う
    1. その候補の点数が $s$ 以下であることを簡潔な方法で計算する（null window search に相応）
    2. $s$ より大きい場合はその候補の点数を計算しなおして $s$ を更新する（αβ 法での計算のやりなおしに相当）

上記の具体例としては、以下のような例が考えられるでしょう。

クラスの生徒の中から最も背の高い生徒の身長を下記の手順で測る。

1. 目測で最も背が高そうな生徒を 1 人選ぶ（move ordering に相当）
2. 選んだ生徒の身長（height）を身長測定器で測り、その身長を $h$ とする（αβ 法に相当）
3. 残りの生徒に対して順番に以下の手順で身長を測定する
    1. 身長測定器の天井を高さが $h$ になるように設定し、生徒が頭をぶつけずにそこを通過できるかどうかで、身長が $h$ 以下であるかどうかを判定する（スカウト法の手順 1 の判定に相当）
    2. $h$ よりも背が高い生徒がいた場合は、身長測定器で改めて身長を測ってその身長で $h$ を更新する

上記の __手順 3-1__ は __手順 2__ で具体的な身長を測る __よりも簡潔に行うことができます__。その結果、__最初に選んだ生徒の身長が高ければ高い程__ 上記の __手順 3-1 で身長が__ $\boldsymbol{h}$ __以下である生徒が増え__、結果として __全体の効率が高まることが期待できます__。
:::

# スカウト法と αβ 法の効率の比較のための準備

__スカウト法__ は __move ordering を前提__ とするアルゴリズムなので、__αβ 法__ と __効率を比較するため__ には、__同じ局面__ のノードに対して __同一の  move ordering__ を行う必要があります。その理由は、__子ノードの並び方が変わる__ と __枝狩りの効率が変わってしまう__ からです。

残念ながら[前回の記事](https://qiita.com/ysgeso/items/97c293d8876190849ec8#move-ordering-%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)で定義した αβ 法の計算を行う __`ai_abs_all`__ で __[先頭のみの move ordering](https://qiita.com/ysgeso/items/97c293d8876190849ec8#move-ordering-%E3%81%A7%E8%A1%8C%E3%81%86%E5%AD%90%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E4%B8%A6%E3%81%B9%E6%9B%BF%E3%81%88%E3%81%AE%E6%96%B9%E6%B3%95)__ を行うと、__同じノードに対して毎回異なる move ordering__ が行われる __場合がある__ ため、同じ局面のノードに対して __同一の  move ordering__ を __行うことができない場合がある__ という問題があります。そのような問題が発生する理由について少し考えてみて下さい。

今回の記事の残りでは、スカウト法と αβ 法の __比較を行うことができるように `ai_abs_all` を修正__ することにします。

## 異なる move ordering が行われる場合がある理由

__`ai_abs_all`__ が同じ局面のノードに対して異なる move ordering を行う場合がある理由は以下の通りです。

* 先頭のみの move ordering では、__AI の関数が計算した最善手[^4]を先頭に移動__ する
* AI の関数が計算した __最善手が複数存在する場合__ はその中から __ランダムに 1 つ選択__ する
* 従って、__AI の関数が複数の最善手を計算__ する場合は、先頭のみの move ordering は __ランダムに行なわれる__

そのことを実際に確認してみることにします。

__`ai2s`__ は局面の評価値を常に 0 と計算するため、__すべての合法手を最善手として計算__ します。従って、__`ai2s`__ を使って __先頭のみの move ordering__ を行うと、__`ai2s` が最善手として計算したすべての子ノード__ の中から __ランダムに選ばれた子ノードが先頭に移動__ します。下記のプログラムでゲーム開始時の局面に対して `ai2s` を利用した move ordering を行い、その際に評価値が計算されたノードの数の表示処理を __複数回行う__ と、実行結果のように __毎回異なる値が表示__ されます。このことから、move ordering による __並べ替えの順序が異なる__ と、実際に __枝狩りの効率が変わる__ ことが確認できました。従って、__枝狩りの効率を比較__ する際には __同じノードに対して同じ move ordering を行う必要があります__。

```python
from marubatsu import Marubatsu
from ai import ai2s, ai_abs_all

mb = Marubatsu()
for _ in range(5):
    print(ai_abs_all(mb, ai_for_mo=ai2s, calc_score=True, calc_count=True))
```

実行結果

```
14504
12347
15300
15799
14739
```

:::note
__[全ノードの move ordering](https://qiita.com/ysgeso/items/97c293d8876190849ec8#%E5%85%A8%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE-move-ordering-%E3%81%AE%E5%AE%9F%E8%A3%85)__ の場合は AI が計算した子ノードの評価値の順で並べ替えを行います。その際に利用する list の __`sort`__ メソッドや組み込み関数 __`sorted`__ は __同じ大きさの値を並べ替える際__ に、__順序を変えずに並べ替え__ を行います。そのため、__同じデータに対して必ず同じ並べ替えが行われる__ ので __この問題は発生しません__。

αβ 法の処理にランダム性はないので、move ordering にランダム性がなく、__同じ局面のノードで同じ move ordering が行われる__ 場合は __同じ処理が行われます__。

そのことは先ほどのプログラムにキーワード引数 [`sort_allnodes=True`](https://qiita.com/ysgeso/items/97c293d8876190849ec8#move-ordering-%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9) を記述することで、全ノードの move ordering を行うように修正した下記のプログラムの実行結果が、すべて同じになることから確認できます。

```python
for _ in range(5):
    print(ai_abs_all(mb, ai_for_mo=ai2s, sort_allnodes=True, calc_score=True, calc_count=True))
```

実行結果

```
18297
18297
18297
18297
18297
```

なお、__同じ大きさの値を順序を変えずに行う__ 並べ替えのことを __安定ソート__（stable sort）と呼びます。一方、__同じ値が複数存在する場合__ に、それらの __順番が入れ替わる可能性があるソート__ の事を __不安定ソート__ と呼びます。Python の `sort` メソッドや組み込み関数 `sorted` は安定ソートを行います。

参考までに、下記に安定ソートの Wikipedia の記事のリンクを示します。
:::

https://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E3%82%BD%E3%83%BC%E3%83%88

## `ai_abs_all` の修正

この問題は、__AI の関数が複数の最善手を計算した場合__ に常にその中の __特定の合法手を選択する__ ようにすることで解決できます。AI の関数は __[キーワード引数 `rand=False` を記述](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#ai1s-%E3%81%AE%E5%AE%9A%E7%BE%A9-%E3%81%9D%E3%81%AE-4%E6%9C%80%E5%88%9D%E3%81%AE%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E6%8E%A1%E7%94%A8%E3%81%99%E3%82%8B)__ を記述して呼び出すことで、AI の関数が計算した複数の最善手の中の __先頭の合法手が常に選択される__ よう定義したので、__`ai_abs_all`__ を下記のプログラムのように修正することにします。

* __17 行目__：先頭のみの move ordering を行うための AI の関数を呼び出す際に、キーワード引数 `rand=False` を記述するように修正する

```python
 1  from ai import ai_by_score, dprint
 2  from copy import deepcopy
 3  
 4  @ai_by_score
 5  def ai_abs_all(mb, debug=False, shortest_victory=False,
 6                 init_ab=False, use_tt=False, ai_for_mo=None,
 7                 params={}, sort_allnodes=False, calc_count=False):        
 8      count = 0
 9      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
10          if ai_for_mo is not None:
11              if sort_allnodes:
12                  score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
13                  score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
14                  legal_moves = [x[0] for x in score_by_move_list]
15              else:
16                  legal_moves = mborig.calc_legal_moves()
17                  bestmove = ai_for_mo(mborig, rand=False, **params)
18                  index = legal_moves.index(bestmove)
19                  legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
元と同じなので省略
```

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

```python
from ai import ai_by_score, dprint
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):        
    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")

    score = ab_search(mb, {}, 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>修正箇所</strong></summary>

```diff_python
from ai import ai_by_score, dprint
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):        
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        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, **params)
+               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]
元と同じなので省略
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように __毎回同じ数値が表示される__ ようになったことから、__先頭のみの move ordering__ が __常に同じ並べ替えを行うようになった__ ことが確認できます。

```python
mb = Marubatsu()
for _ in range(5):
    print(ai_abs_all(mb, ai_for_mo=ai2s, calc_score=True, calc_count=True))
```

実行結果

```
18297
18297
18297
18297
18297
```

### 最善手が複数存在する場合の move ordering の補足

__最善手[^5]が複数存在する場合__ は、move ordering で __最善手の中のどの合法手を先頭に移動__ しても __枝狩りの効率が変わらないのではないか__ と思う人がいるかもしれませんが、__そうではありません__。そのようなことが起きる理由は、同じ最善手のノードであっても __子孫ノードの構成が異なる__ と、move ordering の順番によって __子孫ノードでの α 狩りや β 狩りが行なわれる状況が異なる__ からです。

例えば下図の __赤枠の局面のノード__ の __3 つの子ノード__ はすべて評価値が 1 なので __すべてが最善手__ です。__赤枠のノードの評価値の計算__ を、図の赤枠の子ノードを __上から順に αβ 法で計算__ すると、以下のような計算が行われるため、__黒色の 2 つのノード__ が __α 狩りによって枝狩り__ が行われます。

1. 赤枠の最初の子ノードの評価値を計算する際のウィンドウは (-∞, ∞) である
2. 赤枠の最初の子ノードの評価値が計算された結果、赤枠の 2 番目の子ノードの評価値を計算する際のウィンドウは (1, ∞) になる
3. 赤枠の 2 番目の子ノードの最初の子ノードの評価値が 1 として計算されると、1 ≦ α 値 = 1 で fail low なので α 狩りが行われ、黒色の 2 つのノードの計算が省略される

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4d812426-aeb6-4174-8e8a-bb1f88950494.png" width="300">

なお、上記でどのように枝狩りが行われるかについては、下記のプログラムを実行し、6 番目のフレームからの処理を表示することでも確認することができます。

```python
from tree import Mbtree, Mbtree_Anim

mbtree = Mbtree.load("../data/abtree_root")
Mbtree_Anim(mbtree, isscore=True)
```

一方、__move ordering__ によって上図の __赤枠の上から 2 番目の子ノードを先頭に移動__ して最初に計算すると、先程と異なりそのノードの評価値を計算する際の __ウィンドウが (-∞, ∞)__ となるため、その最初の子ノードの評価値が 1 と計算されても __α 狩りは行われません__。そのため上図の __黒色の 2 つのノードの枝狩りが行われなくなり__、その分だけ __枝狩りの効率が悪くなります__。上記のプログラムではそのような move ordering を行った場合の処理の視覚化を行えないので、余裕がある方は実際に順番に α 値と β 値を計算して α 狩りが行われないことを確認して下さい。

__理想的__ には最善手の子ノードの中から __最も枝狩りの効率が高くなる子ノードを探して先頭に移動したほうが良い__ のですが、残念ながら下記の理由からそのような処理を行うと __処理の効率がかえって悪化する__ のでそのような処理は行いません。

* AI の関数が計算した最善手の子ノードの中から、どの子ノードを先頭に移動すれば最も効率が良くなるかを __確認するため__ には、__実際にそれらの子ノードを先頭に移動して計算して比較する必要__ がある
* その際には、AI の関数が計算した最善手の数だけ __αβ 法と同様の処理が必要__ となる
* その結果、__全体の処理時間__ が __αβ 法の数倍__ になってしまう

# 今回の記事のまとめ

今回の記事ではスカウト法のアルゴリズムと性質の説明を行いました。また、αβ 法の効率と比較するための `ai_abs_all` の修正を行いました。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/70f58152e629be63390d

[^1]:(α 値, α 値 + 1) というウィンドウで計算を行ったので、その場合の fail high の範囲を表す α 値 + 1 値 ≦ $s$ の場合に β 狩りを行うのではないかと思うかもしれませんが、__そうではありません__。その理由については後述します。min ノードの場合も同様です
[^2]:期待できるとしたのは、効率が __変わらない__ 場合や __悪化__ する __場合がある__ からです
[^3]:評価値が整数のみの場合は、exact value の範囲に計算される評価値は一つも存在しないので、必ず fail high の範囲になります
[^4]:強解決ではない AI の関数が計算した最善手は、必ずしも本当の最善手とは限らない点に注意して下さい
[^5]:強解決でない AI が計算した間違っている可能性がある最善手ではなく __本当の最善手__ のことです