Pythonで〇×ゲームのAIを一から作成する　その167　完璧な move ordering での αβ 法とスカウト法

# 目次と前回の記事

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

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

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

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

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

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

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

# 完璧な move ordering での αβ 法とスカウト法の効率

前回の記事では __move ordering の精度が 100 %__ の場合の __αβ 法とスカウト法の効率が同じになる__ ことを示しました。今回の記事ではその理由を説明します。

なお、これまでは「move ordering の精度が 100 % の場合」のように表記していましたが、表記が長いので今後は短く「__完璧な move ordering__」と表記することにします。

## 説明で利用する記号等の説明

今回の記事では、αβ 法やスカウト法で計算を行う際の __各ノード__ を「max ノードか min ノードであるか」、「ミニマックス値」、「ウィンドウ」の __3 種類の情報の組み合わせ__ で __分類して説明__ します。

その際に下記の記号を用い、3 種類の情報を __,（半角のカンマ） で区切って表記__ します。

|表記|意味|
|:--|:--|
|__max__|max ノード|
|__min__|min ノード|
|$\boldsymbol{s}$|ミニマックス値が $s$ である|
|$\boldsymbol{s_-}$|ミニマックス値が $s$ 以下である|
|$\boldsymbol{s_+}$|ミニマックス値が $s$ 以上である|
|$\boldsymbol{s_>}$|ミニマックス値が $s$ より大きい|
|(α 値の初期値, β 値の初期値)|ノードを計算する際のウィンドウの範囲|

例えば「max ノード」、「ミニマックス値が $s$ 以下」、「ウィンドウが ($s$, $s + 1$)」のノードの分類は以下のように表記します。

max, $s_-$, ($s$, $s + 1$)

# 完璧な move ordering での αβ 法で行なわれる処理

まず、__完璧な move ordering__ での __αβ 法が行う処理__ について説明します。

具体的には、下記の条件でノード $N$ の評価値を αβ 法で計算する場合の処理を説明します。

* $N$ は max ノードである
* $N$ のミニマックス値は $s$ である
* $N$ を計算する際の α 値と β 値の初期値を負の無限大と正の無限大とする
* $N$ と $N$ のすべての子孫ノードで、完璧な move ordering が行なわれている
* 置換表は利用しない

なお、本記事では説明を省略しますが「$N$ が min ノードの場合」、「$N$ を計算する際の α 値と β 値の初期値を、評価値の最小値と最大値に設定する場合」、「置換表を利用する場合」でも、同様の手順で行なわれる処理を説明することができるので、余裕がある方はそのような場合で行なわれる処理についても確認してみて下さい。

## max, s, (-∞, ∞) のノードで行なわれる処理

$N$ の評価値を計算する際は「max ノード」、「ミニマックス値は $s$」、「ウィンドウは ($-∞$, $∞$)」なので、$N$ は「max, $s$, ($-∞$, $∞$)」に分類されます。

この分類のノードは max ノードで、そのミニマックス値は $s$ なので、__子ノードの評価値の最大値は__ $\boldsymbol{s}$ となります。

完璧な move ordering では、max ノードの __先頭の子ノードのミニマックス値__ は最大値である $\boldsymbol{s}$ となり、__それ以外の子ノードのミニマックス値__ は $\boldsymbol{s}$ __以下__、すなわち $\boldsymbol{s_-}$ となります。

以下では __子ノードの分類__ を行います。子ノードの数が 0 や 1 の場合は当然ですが、そのノードには下記の分類に対応する子ノードが存在しない場合があります。

### 最初の子ノードの計算処理

この分類のノードの __最初の子ノード__ は以下のように計算されるので「__min__, $\boldsymbol{s}$, ($\boldsymbol{-∞}$, $\boldsymbol{∞}$)」に __分類__ されます。

* min ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($-∞$, $∞$) となる
* ミニマックス値は $s$ である

また、最初の子ノードの評価値として $s$ が計算されるので、__α 値__ は -∞ から $\boldsymbol{s}$ __に更新__ され、次の子ノードの評価値を計算する際の __ウィンドウが ($\boldsymbol{s}$, $\boldsymbol{∞}$)__ となります。

### 2 番目以降の子ノードの計算処理

この分類の 2 番目の子ノードは以下のように計算されるので「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」に __分類__ されます。

* min ノードである
* ウィンドウは ($s$, $∞$) である
* ミニマックス値は $s_-$（$s$ 以下）である

$s_- ≦ s$ なので、__α 値__ は $s$ のまま __更新されません__。従って、次の子ノードの評価値を計算する際の __ウィンドウは__ ($s$, $∞$) のまま __変化しません__。

2 番目の子ノードの評価値を計算した結果、__ウィンドウが変化せず__、__2 番目以降のすべて__ の子ノードの __ミニマックス値は__ $\boldsymbol{s_-}$ なので、__3 番目以降のすべての子ノード__ も「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」に __分類__ されます。

### 子ノードの分類

上記から、この分類のノードの子ノードは、以下の __2 種類に分類__ されます。

|分類|子ノード|
|:--|:--|
|__min__, $\boldsymbol{s}$, ($\boldsymbol{-∞}$, $\boldsymbol{∞}$)|最初の子ノード|
|__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)|2 番目以降の子ノード|

下記は、そのことを表す図です。なお、今回の記事の図では、円はノードを表し、ノードや文字の色を以下のように色分けしました。

* max ノードは円の枠を黒色で、min ノードは赤色とした
* 円の塗りつぶしの色でノードの分類の種類を区別できるようにした
* 右に表記するノードの図形の説明では、$s_-$ の背景色を黄色で、$s_+$ の背景色を水色で表記して区別できるようにした

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4b29977b-3f9d-41e1-9409-3cb4548368c8.png" width="350">

「max, $s$, ($-∞$, $∞$)」の子ノードは 2 種類に分類されることがわかったので、それらの分類のノードで行なわれる処理を検証します。

## min, s, (-∞, ∞) のノードで行なわれる処理

勘の良い方は、この分類のノードで行われる処理は、__先程__ の「max, $s$, ($-∞$, $∞$)」と __同様である__ ことがわかり、以下の説明が冗長だと感じるかもしれません。そのような人は、子ノードの分類まで説明を読み飛ばしてください。

この分類のノードは min ノードで、そのミニマックス値は $s$ なので、__子ノードの評価値の最小値__ は $\boldsymbol{s}$ となります。

完璧な move ordering では、min ノードの __先頭の子ノードのミニマックス値__ は最小値である $\boldsymbol{s}$ となり、__それ以外の子ノードのミニマックス値__ は $\boldsymbol{s}$ __以上__、すなわち $\boldsymbol{s_+}$ となります。

### 最初の子ノードの計算処理

この分類のノードの __最初の子ノード__ は以下のように計算されるので「__max__, $\boldsymbol{s}$, ($\boldsymbol{-∞}$, $\boldsymbol{∞}$)」に __分類__ されます。

* max ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($-∞$, $∞$) となる
* ミニマックス値は $s$ である

また、最初の子ノードの評価値として $s$ が計算されるので、__β 値__ は ∞ から $\boldsymbol{s}$ __に更新__ され、次の子ノードの評価値を計算する際の __ウィンドウが ($\boldsymbol{―∞}$, $\boldsymbol{s}$)__ となります。

### 2 番目以降の子ノードの計算処理

この分類の 2 番目の子ノードは以下のように計算されるので「__max__, $\boldsymbol{s_+}$, ($\boldsymbol{-∞}$, $\boldsymbol{s}$)」に __分類__ されます。

* max ノードである
* ウィンドウは ($-∞$, $s$) である
* ミニマックス値は $s_+$ である

$s ≦ s_+$ なので、__β 値__ は $s$ のまま __更新されません__。従って、次の子ノードの評価値を計算する際の __ウィンドウ__ は ($-∞$, $s$) のまま __変化しません__。

2 番目の子ノードの評価値を計算した結果、__ウィンドウが変化せず__、__2 番目以降のすべての子ノードのミニマックス値__ は $\boldsymbol{s_+}$ なので、__3 番目以降のすべての子ノード__ も「__max__, $\boldsymbol{s_+}$, ($\boldsymbol{-∞}$, $\boldsymbol{s}$)」に __分類__ されます。

### 子ノードの分類

上記から、この分類のノードの子ノードは、以下の __2 種類に分類__ されます。

|分類|子ノード|
|:--|:--|
|__max__, $\boldsymbol{s}$, ($\boldsymbol{-∞}$, $\boldsymbol{∞}$)|最初の子ノード|
|__max__, $\boldsymbol{s_+}$, ($\boldsymbol{-∞}$, $\boldsymbol{s}$)|2 番目以降の子ノード|

下記は、そのことを表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/86d6d8d5-3de0-4360-b6af-7a327e034471.png" width="350">

「min, $s$, ($-∞$, $∞$)」の子ノードは上記の 2 種類に分類されることがわかりましたが、__そのうちの一つは先程検証__ した「max, $s$, ($-∞$, $∞$)」です。従って、$N$ から __先頭の子ノードを順番にたどる__ と「max, $s$, ($-∞$, $∞$)」と「min, $s$, ($-∞$, $∞$)」に分類されるノードが、下図のように __繰り返される__ ことになります。なお、下図の黄色と水色のノードはまだ検証していないので、それらの子孫ノードは省略しています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8a6560a7-9f4d-4745-9e63-3fd98ef247fb.png" width="500">

次に、まだ検証していない黄色の「min, $s_-$, ($s$, $∞$)」と、水色の「max, $s_+$, ($-∞$, $s$)」の分類のノードについて順番に検証します。

## min, s-, (s, ∞) のノードで行なわれる処理

この分類のノードは __min ノード__ で、その __ミニマックス値__ は $\boldsymbol{s_-}$ です。

### 最初の子ノードの計算処理

完璧な move ordering によって __最初の子ノードのミニマックス値__ は $\boldsymbol{s_-}$ となり、この分類のノードの最初の子ノードは以下のように計算されるので「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」に __分類__ されます。

* max ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($s$, $∞$) となる
* ミニマックス値は $s_-$ である

ウィンドウが ($s$, $∞$) で、最初の子ノードのミニマックス値である $s_-$ は、$\boldsymbol{s_- ≦ s}$ なので、__最初の子ノードで計算される評価値__ は __fail low の範囲__ になります。__min ノード__ では __fail low__ が計算された場合は __α 狩りが行なわれ__ て残りの子ノードの処理は省略されるので、この分類のノードは __最初の子ノードのみが計算__ されます。

### 子ノードの分類

上記から、この分類のノードの子ノードは、以下の 2 種類に分類され、その中で __計算が行なわれるノードは 1 種類のみ__ となります。

|分類|子ノード|
|:--|:--|
|__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)|最初の子ノード|
|__枝狩りが行われて計算されない__|2 番目以降のノード|

下記はそのことを表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/abb49178-6ba2-484b-a776-75a55a68516b.png" width="350">

次に上記の表の「max, $s_-$, ($s$, $∞$)」の分類の検証を行います。

## max, s-, (s, ∞) のノードで行なわれる処理

この分類のノードは __max ノード__ で、そのミニマックス値は $\boldsymbol{s_-}$ なので、__move ordering の有無に関わらず__、__すべての子ノードのミニマックス値__ は $\boldsymbol{s_-}$ となります。

### 最初の子ノードの計算処理

この分類のノードの __最初の子ノード__ は、以下のように計算されるので「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」に __分類__ されます。

* min ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($s$, $∞$) となる
* ミニマックス値は $s_-$ である

計算されたミニマックス値は $s_-$ で $\boldsymbol{s_- ≦ s}$ なので、__α 値__ は $s$ のまま __更新されません__。従って、次の子ノードの評価値を計算する際の __ウィンドウ__ は ($s$, $∞$) のまま __変化しません__。

### 2 番目以降の子ノードの計算処理

最初の子ノードの評価値を計算した結果、__ウィンドウ__ が ($s$, $∞$) から __変化せず__、__すべての子ノードのミニマックス値__ は $\boldsymbol{s_-}$ なので、__2 番目以降のすべての子ノード__ も「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」に __分類__ されます。

### 子ノードの分類

上記から、この分類のノードの子ノードは、以下の __1 種類のみに分類__ されます。

|分類|子ノード|
|:--|:--|
|__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)|すべての子ノード|

下記は、そのことを表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/31fd7f89-36ff-4c3d-8861-096ec5305e04.png" width="350">

「min, $s_-$, ($s$, $∞$)」の分類のノードは __既に検証済み__ です。その __検証結果を組み合わせる__ と以下のようになり、__2 種類の分類のノードが繰り返される__ ことがわかります。

* 「min, $s_-$, ($s$, $∞$)」の子ノードは __最初の子ノードのみが計算__ され、その分類は「max, $s_-$, ($s$, $∞$)」である
* 「max, $s_-$, ($s$, $∞$)」の __すべての子ノードの分類__ は「min, $s_-$, ($s$, $∞$)」に __戻る__

下記はそのことを表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ef86fe84-7e17-4f59-af9d-c322075f09a0.png" width="500">

## max, s+, (-∞, s) のノードで行なわれる処理

勘の良い方はこの分類のノードでは、先程の「min, $s_-$, ($s$, $∞$)」と __同様の処理が行われる__ ことに気づくのではないかと思います。その場合はこの後のノードの分類のまとめの所まで読み飛ばしてください。

この分類のノードは __max__ ノードで、そのミニマックス値は $\boldsymbol{s_+}$ です。

### 最初の子ノードの計算処理

完璧な move ordering では最初の子ノードの評価値は $\boldsymbol{s_+}$ となり、この分類のノードの最初の子ノードは以下のように計算されるので「__min__, $\boldsymbol{s_+}$, ($\boldsymbol{-∞}$, $\boldsymbol{s}$)」に __分類__ されます。

* min ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($-∞$, $s$) となる
* ミニマックス値は $s_+$ である

ウィンドウが ($-∞$, $s$) で、__最初の子ノードのミニマックス値__ である $s_+$ は、$\boldsymbol{s ≦ s_+}$ なので、__最初の子ノードで計算される評価値__ は __fail high の範囲__ になります。__max ノード__ では __fail high__ が計算された場合は __β 狩りが行なわれ__ て残りの子ノードの処理は省略されるので、この分類のノードは __最初の子ノードのみが計算されます__。

### 子ノードの分類

上記から、この分類の子ノードは以下の 2 種類に分類され、その中で __計算が行なわれるノードは 1 種類のみ__ となります。

|分類|子ノード|
|:--|:--|
|__min__, $\boldsymbol{s_+}$, ($\boldsymbol{-∞}$, $\boldsymbol{s}$)|最初の子ノード|
|__枝狩りが行われて計算されない__|2 番目以降のノード|

下記はそのことを表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/36c41380-8dec-4a89-b83b-b6e1b9ca64dc.png" width="350">

次に上記の表の「min, $s_+$, ($-∞$, $s$)」の分類の検証を行います。

## min, s+, (-∞, s) のノードで行なわれる処理

この分類のノードは __max ノード__ で、そのミニマックス値は $\boldsymbol{s_+}$ なので、__move ordering の精度に関わらず__、__すべての子ノードのミニマックス値__ は $\boldsymbol{s_+}$ となります。

### 最初の子ノードの計算処理

この分類のノードの __最初の子ノード__ は以下のように計算されるので「__max__, $\boldsymbol{s_+}$, ($\boldsymbol{-∞}$, $\boldsymbol{s}$)」に分類されます。

* max ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは「($-∞$, $s$)」となる
* ミニマックス値は $s_+$ である

計算されたミニマックス値は $s_+$ で $\boldsymbol{s ≦ s_+}$なので、__β 値__ は $s$ のまま __更新されない__ ので、次の子ノードの評価値を計算する際の __ウィンドウ__ は ($-∞$, $s$) のまま __変化しません__。

### 2 番目以降の子ノードの計算処理

最初の子ノードの評価値を計算した結果、__ウィンドウ__ が __変化せず__、__すべての子ノードのミニマックス値__ は $\boldsymbol{s_+}$ なので、__2 番目以降のすべての子ノード__ も「__max__, $\boldsymbol{s_+}$, ($\boldsymbol{-∞}$, $\boldsymbol{s}$)」に __分類__ されます。

### 子ノードの分類

上記から、この分類のノードの子ノードは、以下の __ 1 種類のみに分類__ されます。

|分類|子ノード|
|:--|:--|
|__max__, $\boldsymbol{s_+}$, ($\boldsymbol{-∞}$, $\boldsymbol{s}$)|すべての子ノード|

下記は、そのことを表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5875c871-1dd3-4387-9e5d-4b98e4660e8b.png" width="350">

「max, $s_+$, ($-∞$, $s$)」の分類のノードは __既に検証済み__ です。その __検証結果を組み合わせる__ と以下のようになり、__2 種類の分類のノードが繰り返される__ ことがわかります。

* 「max, $s_+$, ($-∞$, $s$)」の子ノードは __最初の子ノードのみが計算__ され、その分類は「min, $s_+$, ($-∞$, $s$)」である
* 「min, $s_+$, ($-∞$, $s$)」の __すべての子ノードの分類__ は「max, $s_+$, ($-∞$, $s$)」に __戻る__

下記はそのことを表す図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f65b0e7e-16ce-4ceb-8c35-be9a8c5fa606.png" width="500">

以上で αβ 法で計算されるノードの分類をすべて検証することができました。

## ノードの分類のまとめ

__完璧な move ordering での αβ 法__ では、評価値が計算される __ノードは 6 種類に分類__ され、下記の表のように __それぞれの子ノードが分類__ されます。

|番号|分類|最初の子ノードの番号|2 番目以降の子ノードの番号|
|:--|:--|:--|:--
|①|max, $s$, ($-∞$, $∞$)|②|③|
|②|min, $s$, ($-∞$, $∞$)|①|⑤|
|③|min, $s_-$, ($s$, $∞$)|④|枝狩りされるので存在しない|
|④|max, $s_-$, ($s$, $∞$)|③|③|
|⑤|max, $s_+$, ($-∞$, $s$)|⑥|枝狩りされるので存在しない|
|⑥|min, $s_+$, ($-∞$, $s$)|⑤|⑤|

また、それぞれの分類のノードの __子孫ノードの分類__ は以下のように __繰り返されます__。

||繰り返しの法則|
|:--|:--|
| $\boldsymbol{N}$ __から先頭の子ノードのみを辿った子孫ノード__| ① → ② → ① → ② の 繰り返し |
| __① の 2 番目以降の子ノードの子孫ノード__| ③ → ④ → ③ → ④ の繰り返し<br>③ → ④ は先頭の子ノードのみ<br>④ → ③ はすべての子ノード |
| __② の 2 番目以降の子ノードの子孫ノード__| ⑤ → ⑥ → ⑤ → ⑥ の繰り返し<br>⑤ → ⑥ は先頭の子ノードのみ<br>⑥ → ⑤ はすべての子ノード |

下記は上記の繰り返しを図示したものです。わかりやすいようにノードの円の中に分類の番号を入れました。

__① → ② → ① → ② の 繰り返しの図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c5da1ebe-38b1-4f9b-90ab-f5d926a92685.png" width="500">

__③ → ④ → ③ → ④ の繰り返しの図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/785a08bf-8de9-4570-9b6f-73e94a038cbd.png" width="500">

__⑤ → ⑥ → ⑤ → ⑥ の繰り返しの図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c0c62944-2c8f-4ed8-8818-1a9661359ed6.png" width="500">

## Mbtree_Anim での確認

__上記の検証結果の処理が行われること__ を、下記のプログラムで __完璧な move ordering が行なわれた 〇× ゲームのゲーム木__ に対して αβ 法で評価値を計算した結果を __Mbtree_Anim で表示することで確認__ することにします。

* __3 行目__：ファイルからゲーム木のデータを読み込む
* __4 行目__：[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-move_bestmove_to_head-%E3%81%AE%E5%AE%9A%E7%BE%A9)で定義した `move_bestmove_to_head` メソッドを利用して完璧な move ordering を行う
* __5 行目__：Mbtree_Anim で視覚化を行えるように `calc_score_for_anim` で αβ 法での計算を行う
* __6 行目__：Mbtree_Anim で視覚化を行う

```python
1  from tree import Mbtree, Mbtree_Anim
2
3  mbtree = Mbtree.load("../data/abtree_root")
4  mbtree.move_bestmove_to_head()
5  mbtree.calc_score_for_anim(mbtree.root, minimax=False)
6  Mbtree_Anim(mbtree, isscore=True)
```

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

```python
from tree import Mbtree, Mbtree_Anim

mbtree = Mbtree.load("../data/abtree_root")
mbtree.move_bestmove_to_head()
mbtree.calc_score_for_anim(mbtree.root, minimax=False)
Mbtree_Anim(mbtree, isscore=True)
```
</details>

### 検証を行うノード

検証を行うのは、〇× ゲームのゲーム木の __下図の数字が表示されているノード__ で、この番号は先程の表の分類番号に対応しています。なお、1 はゲーム開始時の局面のノードです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/df48919f-a6be-4358-acfb-684802e32991.png" width="500">

〇×ゲームの __ゲーム開始時の局面__ は引き分けの局面なので、その __ミニマックス値は 0__ です。そのため、図のそれぞれの番号のノードの __ミニマックス値__、__ウィンドウ__、__計算される子ノード__ は以下のようになります。

|番号|ミニマックス値|ウィンドウ|計算される子ノード|
|:--|:--|:--|:--|
|1|0|($-∞$, $∞$)|すべて|
|2|0|($-∞$, $∞$)|すべて|
|3|0 以下|($0$, $∞$)|最初の子ノードのみ|
|4|0 以下|($0$, $∞$)|すべて|
|5|0 以上|($-∞$, $0$)|最初の子ノードのみ|
|6|0 以上|($-∞$, $0$)|すべて|

下記はそれぞれの番号のノードの __計算を開始する start のフレーム__ と __評価値が確定した end__ のフレームです。__start__ のフレームには __ウィンドウ__ が、__end__ のフレームには __score に計算された評価値__ と、__計算が行われた子ノードが明るい色で表示__ されます。

1 のノード。左図のウィンドウが ($-∞$, $∞$)、右図の評価値が 0、すべての子ノードの評価値が計算されていることから、検証したとおりの計算が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a1f8d525-d5e4-44a5-963f-d935f32f64a3.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d55c0816-1db5-4c99-9b2a-c7742ceeb622.png" width="300">

2 のノード。左図のウィンドウが ($-∞$, $∞$)、右図の評価値が 0、すべての子ノードの評価値が計算されていることから、検証したとおりの計算が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0698655c-1997-48ce-92e4-506fa147697c.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/630f56bb-c457-4849-89ae-0dfdb6bafd5f.png" width="300">

3 のノード。左図のウィンドウが ($0$, $∞$)、右図の評価値が 0 で 0 以下、最初の子ノードのみが計算されていることから、検証したとおりの計算が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ff9efd24-3381-4cdb-93ac-482754802cba.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b6fbbc1d-edec-42fa-a0c4-29e183990c22.png" width="300">

4 のノード。左図のウィンドウが ($0$, $∞$)、右図の評価値が 0 で 0 以下、すべての子ノードの評価値が計算されていることから、検証したとおりの計算が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ab2e9a7f-e4c0-4d67-a9f3-24baa096422a.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b3c3808e-45ac-473d-bee1-99139359a05f.png" width="300">

5 のノード。左図のウィンドウが ($-∞$, $0$)、右図の評価値が 1 で 0 以上、最初の子ノードのみが計算されていることから、検証したとおりの計算が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7cb2be10-7f05-410c-befb-e93b3f20d1e6.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1abcbfe3-6b61-4102-84ad-bb1f79957d1e.png" width="300">

6 のノード。左図のウィンドウが ($-∞$, $0$)、右図の評価値が 1 で 0 以上、すべての子ノードの評価値が計算されていることから、検証したとおりの計算が行われていることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3eac0a7d-dc5e-44ae-b180-4da7f1f168d2.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3dcab1de-6aff-465e-9ad9-d15850ec8745.png" width="300">

長くなるので本記事での検証はここまでにします。興味がある方は様々な操作を行い、1 と 2 が繰り返されるなど、他のノードでも検証した処理が行われることを確認してみて下さい。

# 完璧な move ordering でのスカウト法で行なわれる処理

次に、__完璧な move ordering__ での __スカウト法で行なわれる処理__ を、αβ 法と同様の方法で検証します。

## max, s, (-∞, ∞) のノードで行なわれる処理

αβ 法の場合と同様に、$\boldsymbol{N}$ は「__max__, $\boldsymbol{s}$, ($\boldsymbol{-∞}$, $\boldsymbol{∞}$)」に __分類__ されます。

### 最初の子ノードの計算処理

__スカウト法__ では、__最初の子ノード__ の計算処理は __αβ 法と同じ方法で行う__ ため、この分類のノードの __最初の子ノード__ は αβ 法の場合と同様に「__min__, $\boldsymbol{s}$, ($\boldsymbol{-∞}$, $\boldsymbol{∞}$)」に分類されます。

また、以下の性質は αβ 法の場合と同様です。

* __α 値__ が $\boldsymbol{s}$ __に更新__ される
* 完璧な move ordering の結果、__2 番目以降の子ノードのミニマックス値__ は $\boldsymbol{s_-}$ になる

### 2 番目以降の子ノードの計算処理

__スカウト法__ では __2 番目以降の子ノード__ は __(α 値, α 値 + 1)__ というウィンドウの __null window search で計算__ されます。従って、この分類のノードの __2 番目の子ノード__ は、以下のように計算されるので「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」に分類されます。

* min ノードである
* ウィンドウは ($s$, $s + 1$) となる
* ミニマックス値は $s_-$ である

$\boldsymbol{s_- ≦ s}$ なので、__α 値__ は $s$ のまま __更新されません__。従って、次の子ノードの評価値を計算する際の __ウィンドウ__ は ($s$, $s + 1$) のまま __変化しません__。また、ミニマックス値は fail low の範囲なので __αβ 法と同じウィンドウで計算をやり直す必要はありません__[^1]。

2 番目の子ノードの評価値を計算した結果、ウィンドウが変化せず、2 番目以降のすべての子ノードのミニマックス値は $s_-$ なので、__3 番目以降のすべての子ノード__ も「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」に __分類__ されます。

### 子ノードの分類

上記から、「max, $s$, ($-∞$, $∞$)」に分類されるノードの子ノードは、以下の __2 種類に分類__ されます。比較できるように、αβ 法の場合の分類も表に入れました。

|スカウト法の場合の分類|αβ 法の場合の分類|子ノード|
|:--|:--|:--|
|__min__, $\boldsymbol{s}$, ($\boldsymbol{-∞}$, $\boldsymbol{∞}$)|スカウト法と同じ|最初の子ノード|
|__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)|min, $s_-$, ($s$, $∞$)|2 番目以降の子ノード|

上記から、__αβ 法との違い__ は __2 番目以降の子ノード__ の __ウィンドウだけ__ であることがわかります。従って、このことを表す図は αβ 法の場合とほぼ同じになるので省略します。

## min, s, (-∞, ∞) のノードで行なわれる処理

同じような分析を何度も繰り返すのは冗長なので、この分類のノードで行なわれる処理は __結果のみを示します__。余裕がある方はこれまでと同様の手順で下記のような結果になることを確認して下さい。

「min, $s$, ($-∞$, $∞$)」に分類されるノードの子ノードは、以下の __2 種類に分類__ されます。

|スカウト法の場合の分類|αβ 法の場合の分類|子ノード|
|:--|:--|:--|
|__max__, $\boldsymbol{s}$, ($\boldsymbol{-∞}$, $\boldsymbol{∞}$)|スカウト法と同じ|最初の子ノード|
|__max__, $\boldsymbol{s_+}$, ($\boldsymbol{s-1}$, $\boldsymbol{s}$)|max, $s_+$, ($-∞$, $s$)|2 番目以降の子ノード|

上記から、__スカウト法__ でも __αβ 法と同様__ に、$N$ から __先頭の子ノードを順番にたどる__ と、「max, $s$, ($-∞$, $∞$)」と「min, $s$, ($-∞$, $∞$)」に分類されるノードが、下図のように __繰り返される__ ことになります。その下の αβ 法の場合の図と比較して、ここまでに検証した範囲では、__αβ 法同じノードの処理が行われる__ ことを確認して下さい。なお、下図では αβ 法と異なる部分を緑色の背景色で塗りつぶしました。

__スカウト法の場合の図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/09f49476-107b-47cd-9e95-3a2f1010147a.png" width="500">

__αβ 法の場合の図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8a6560a7-9f4d-4745-9e63-3fd98ef247fb.png" width="500">

## min, s-, (s, s + 1) のノードで行なわれる処理

この分類のノードは __min ノード__ で、その __ミニマックス値は__ $\boldsymbol{s_-}$ です。

### 最初の子ノードの計算処理

完璧な move ordering では __最初の子ノードの評価値__ は $\boldsymbol{s_-}$ となり、この分類のノードの __最初の子ノード__ は以下のように計算されるので「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」に分類されます。

* max ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($s$, $s + 1$) となる
* ミニマックス値は $s_-$ である

ウィンドウが ($s$, $s + 1$) で、最初の子ノードのミニマックス値である $s_-$ は、$\boldsymbol{s_- ≦ s}$ なので、__最初の子ノードのミニマックス値__ は __fail low の範囲__ になります。__min ノード__ では __fail low__ が計算された場合は __α 狩り__ が行なわれて __残りの子ノードの処理は省略__ されるので、この分類のノードは __最初の子ノードのみが計算__ されます。

これは、__αβ 法__ で「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」の分類のノードで __行われる処理と同じ__ です。

### 子ノードの分類

上記から、この分類のノードの子ノードは以下の 2 種類に分類され、その中で __計算が行なわれるノードは 1 種類のみ__ となります。比較できるように αβ 法で「min, $s_-$, ($s$, $∞$)」の分類のノードで行なわれる処理を表に入れました。

|スカウト法の場合の分類|αβ 法の場合の分類|子ノード|
|:--|:--|:--|
|__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)|max, $s_-$, ($s$, $∞$)|最初の子ノード|
|__枝狩りが行われて計算されない__|スカウト法と同じ|2 番目以降のノード|

従って、この分類のノードで行なわれる処理は、__αβ 法__ で「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」の分類のノードで行なわれる処理と __同じ構造になる__ ことがわかりました。

## max, s-, (s, s + 1) のノードで行なわれる処理

この分類のノードは __max ノード__ で、そのミニマックス値は $s_-$ なので、__move ordering の有無に関わらず__、__すべての子ノードのミニマックス値__ は $\boldsymbol{s_-}$ となります。

### 最初の子ノードの計算処理

この分類のノードの最初の子ノードは以下のように計算されるので「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」に分類されます。

* min ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($s$, $s + 1$) となる
* ミニマックス値は $s_-$ である

計算されたミニマックス値は $s_-$ で $\boldsymbol{s_- ≦ s}$ なので、__α 値__ は $s$ のまま __更新されません__。従って、__次の子ノード__ の評価値を計算する際の __ウィンドウ__ は __変化しません__。

### 2 番目以降の子ノードの計算処理

最初の子ノードの評価値を計算した結果、ウィンドウが ($s$, $s + 1$) から変化せず、すべての子ノードのミニマックス値は $s_-$ なので、__2 番目以降のすべての子ノード__ も「__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」に __分類__ されます。

### 子ノードの分類

上記から、この分類の子ノードは、以下の __1 種類のみに分類__ されます。比較できるように αβ 法で「max, $s_-$, ($s$, $∞$)」の分類のノードで行なわれる処理を表に入れました。

|スカウト法の場合の分類|αβ 法の場合の分類|子ノード|
|:--|:--|:--|
|__min__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)|min, $s_-$, ($s$, $∞$)|すべての子ノード|

従って、この分類のノードで行なわれる処理は、__αβ 法__ で「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」の分類のノードで行なわれる処理と __同じ構造になる__ ことがわかりました。

「min, $s_-$, ($s$, $s + 1$)」の分類のノードは既に __検証済み__ です。その __検証結果を組み合わせる__ と以下のようになり、__2 種類の分類のノードが繰り返される__ ことがわかります。

* 「min, $s_-$, ($s$, $s + 1$)」の子ノードは __最初の子ノードのみが計算__ され、その分類は「max, $s_-$, ($s$, $s + 1$)」である
* 「max, $s_-$, ($s$, $s + 1$)」の __すべての子ノードの分類__ は「min, $s_-$, ($s$, $s + 1$)」に __戻る__

下図はそのことを表す図です。その下の __αβ 法の場合の図と同じ処理が行われる__ ことを確認して下さい。

__スカウト法の場合の図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/769cde3f-aeaf-435c-aa8b-539527af654d.png" width="500">

__αβ 法の場合の図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ef86fe84-7e17-4f59-af9d-c322075f09a0.png" width="500">

## 残りの分類のノードで行なわれる処理

説明はこれまでと同様なので省略しますが、「__max__, $\boldsymbol{s_+}$, ($\boldsymbol{s - 1}$, $\boldsymbol{s}$)」に分類されるノードの子ノードは以下の 2 種類に分類され、その中で __計算が行なわれるノードは 1 種類のみ__ となります。

|スカウト法の場合の分類|αβ 法の場合の分類|子ノード|
|:--|:--|:--|
|__min__, $\boldsymbol{s_+}$, ($\boldsymbol{s - 1}$, $\boldsymbol{s}$)|min, $s_+$, ($-∞$, $s$)|最初の子ノード|
|枝狩りが行われて計算されない|スカウト法と同じ|2 番目以降のノード|

残りの「__min__, $\boldsymbol{s_+}$, ($\boldsymbol{s-1}$, $\boldsymbol{s}$)」に分類されるノードの子ノードは、以下の __1 種類のみに分類__ されます。

|スカウト法の場合の分類|αβ 法の場合の分類|子ノード|
|:--|:--|:--|
|__max__, $\boldsymbol{s_+}$, ($\boldsymbol{s-1}$, $\boldsymbol{s}$)|max, $s_+$, ($-∞$, $s$)|すべての子ノード|

上記の __検証結果を組み合わせる__ 先程と同様に __2 種類の分類のノードが繰り返される__ ことがわかります。下図はそのことを表す図です。その下の __αβ 法の場合の図と同じ処理が行われる__ ことを確認して下さい。

__スカウト法の場合の図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/82a0ac83-cfe0-4f0f-a516-da6a0bd9ac59.png" width="500">

__αβ 法の場合の図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f65b0e7e-16ce-4ceb-8c35-be9a8c5fa606.png" width="500">

以上でスカウト法で計算されるノードの分類をすべて検証することができました。

## スカウト法と αβ 法で行なわれる処理の比較

下記は __完璧な move ordering__ でスカウト法と αβ 法の __ノードの分類__ を __まとめた表__ で、スカウト法と αβ 法では __どちらもノードが 6 種類に分類__ されます。また、先ほど行った検証から、どちらも __対応する分類で同じ子ノードの処理が行われる__ ことが確認できたことから、__同じノードが同じ番号に分類__ されます。

なお、__番号1__ は __最初の子ノードの番号__ 、__番号2__ は __2 番目以降の子ノードの番号__ を表します。

|番号|スカウト法での分類|αβ 法での分類|番号1|番号2|
|:--|:--|:--|:--|:--|
|①|max, $s$, ($-∞$, $∞$)|スカウト法と同じ|②|③|
|②|min, $s$, ($-∞$, $∞$)|スカウト法と同じ|①|⑤|
|③|min, $s_-$, ($s$, $s + 1$)|min, $s_-$, ($s$, $∞$)|④|枝狩り|
|④|max, $s_-$, ($s$, $s + 1$)|max, $s_-$, ($s$, $∞$)|③|③|
|⑤|max, $s_+$, ($s-1$, $s$)|max, $s_+$, ($-∞$, $s$)|⑥|枝狩り|
|⑥|min, $s_+$, ($s-1$, $s$)|min, $s_+$, ($-∞$, $s$)|⑤|⑤|

また、それぞれの分類のノードの __子孫ノードの分類__ は、スカウト法と αβ 法で以下のように __全く同じ法則の繰り返し__ が行なわれます。

||繰り返しの法則|
|:--|:--|
| $\boldsymbol{N}$ __から先頭の子ノードのみを辿った子孫ノード__| ① → ② → ① → ② の 繰り返し |
| __① の 2 番目以降の子ノードの子孫ノード__| ③ → ④ → ③ → ④ の繰り返し<br>③ → ④ は先頭の子ノードのみ<br>④ → ③ はすべての子ノード |
| __② の 2 番目以降の子ノードの子孫ノード__| ⑤ → ⑥ → ⑤ → ⑥ の繰り返し<br>⑤ → ⑥ は先頭の子ノードのみ<br>⑥ → ⑤ はすべての子ノード |

上記を言葉で説明すると以下のようになります。

* __ウィンドウが ($-∞$, $∞$)__ の __最初の子ノード__ は、αβ 法でもスカウト法でも __同じ ($―∞$, $∞$) のウィンドウ__ で $\boldsymbol{s}$ という __ミニマックス値が計算__ される
* __max ノード__ で __ウィンドウが ($-∞$, $∞$)__ のノードの __2 番目以降の子孫ノード__ では、以下のような計算が行われる
    * __すべての子孫ノード__ で、__αβ 法__ では ($\boldsymbol{s}$, $\boldsymbol{∞}$)、__スカウト法__ では ($\boldsymbol{s}$, $\boldsymbol{s + 1}$) というウィンドウで計算がおこなわれる
    * __すべての子孫ノード__ で、__ミニマックス値__ が $\boldsymbol{s_-}$ であることが計算される
    * 子孫ノードの中の __max ノード__ では、__すべての子ノードのミニマックス値__ が __fail low__ となるので、__すべての子ノードの評価値の計算が行なわれる__
    * 子孫ノードの中の __min ノード__ では、move ordering によって __最初の子ノードのミニマックス値が fail low__ の $\boldsymbol{s_-}$ となるため、__いずれの場合も α 狩り__ が行なわれ __2 番目以降の子ノードは計算されない__
* __max ノード__ で __ウィンドウが ($-∞$, $∞$)__ のノードの __2 番目以降の子孫ノード__ の場合も、__上記と同様の計算__ が行われる

:::note warn
上記から、__完璧な move ordering__ が行われる場合は、スカウト法と αβ 法で __まったく同じノードの計算が行なわれる__ ことが確認できました。従って __完璧な move ordering__ が行われる場合は、__スカウト法と αβ 法の効率は全く同じ__ になります。
:::

# スカウト法によって行なわれる効率化

__スカウト法__ が、__どのような場合に αβ 法よりも効率が高くなるか__ についてピンと来ない人がいるかもしれないので、__スカウト法の方が__ αβ 法よりも __効率が良くなる場合の具体例__ を紹介します。これは __一例にすぎない__ ので、__他にも効率が良くなる場合があります__。余裕がある方はそのような場合を探してみて下さい。

__下記の条件__ で $N$ の評価値を計算すると、__スカウト法の方が__ αβ 法よりも __枝狩りが多く行われるため__、__効率が高く__ なります。

* 評価値は整数のみが計算されるものとする
* $N$ の 2 番目の子ノードを $C$ と表記する
* $C$ の $i$ 番目の子ノードを $G_i$[^2] と表記する
* $\boldsymbol{C}$ __の子ノードのみ move ordering が正しく行われず__、最初の子ノード $\boldsymbol{G_1}$ の __ミニマックス値__ が $\boldsymbol{s}$ __より大きな値__ になる。以後は $s$ __より大きな値__ を $\boldsymbol{s_>}$ と表記[^3]する
* $C$ の 2 番目の子ノード $\boldsymbol{G_2}$ の __ミニマックス値__ が $\boldsymbol{s_-}$（$s$ 以下）になる

下図は上記のゲーム木の一部を図示したものです。$C$ の子ノードの数は 2 以上であれば何でも構いません。下図では $C$ に $n$ 個の子ノードが存在するものとして図示しました。また、$C$ の子ノードは move ordering が正しく行われていないので、その __分類はまだ検証されていません__。そのことを表すため $C$ の子ノードを __紫色で塗りつぶしました__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a61adddf-4508-45ca-8d6d-044cbd9886ba.png" width="500">

$\boldsymbol{C}$ __以外__ のノードでは __完璧な move ordering__ が行われるので、$\boldsymbol{C}$ __以外__ の $N$ の子ノードの __計算の効率__ は __αβ 法とスカウト法で同じ__ になります。従って、$\boldsymbol{C}$ の評価値の計算の __効率の差__ が、$N$ の評価値を計算した際の __αβ 法とスカウト法の効率の差__ になります。

## αβ 法でのノード C の計算処理

まず、__αβ 法__ でのノード $\boldsymbol{C}$ __の計算処理__ を検証します。

$\boldsymbol{N}$ の __子ノードは完璧な move ordering__ が行われており、$C$ は $N$ の 2 番目の子ノードなので、$C$ を計算する際の __ウィンドウ__ は先程検証した際と同様に ($\boldsymbol{s}$, $\boldsymbol{∞}$) となります。

### 最初の子ノードの計算処理

この分類のノードの最初の子ノードは以下のように計算されるので「__max__, $\boldsymbol{s_>}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」に __分類__ されます。

* min ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($s$, $∞$) となる
* ミニマックス値は $s_>$ である

計算されたミニマックス値は $s_>$ で $\boldsymbol{s &lt; s_&gt;}$ なので、__α 狩りは行なわれません__。__β 値__ が $∞$ から $\boldsymbol{s_>}$ に __更新される__ ので、次の $\boldsymbol{G_2}$ の評価値を計算する際の __ウィンドウ__ は ($\boldsymbol{s}$, $\boldsymbol{s_>}$) に更新されます。

### 2 番目の子ノードの計算処理

$G_2$ のノードは、以下のように計算されるので「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s_>}$)」に分類されます。

* min ノードである
* ウィンドウは ($s$, $s_>$) である
* ミニマックス値は $s-$ である

計算された $G_2$ のミニマックス値 $s_-$ は $\boldsymbol{s_- < s}$　なので __α 狩りが行われ__、__残りの子ノードの評価値の計算は省略__ されます。

### 行なわれる処理のまとめ

上記から $C$ の評価値を計算する際には下記の __2 つの子ノードの計算__ が行われます。

* 「__max__, $\boldsymbol{s_>}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」に分類される $G_1$
* 「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s_>}$)」に分類される $G_2$

## スカウト 法でのノード C の計算処理

次に、__スカウト法__ でのノード $\boldsymbol{C}$ __の計算処理__ を検証します。

$\boldsymbol{N}$ の __子ノードは完璧な move ordering__ が行われており、$C$ は $N$ の 2 番目の子ノードなので、$C$ を計算する際の __ウィンドウ__ は先程検証した際と同様に ($\boldsymbol{s}$, $\boldsymbol{s + 1}$) となります。

### 最初の子ノードの計算処理

この分類のノードの最初の子ノードは以下のように計算されるので「__max__, $\boldsymbol{s_>}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」に分類されます。

* min ノードである
* このノードのウィンドウが受け継がれるのでウィンドウは ($s$, $s + 1$) となる
* ミニマックス値は $s_>$ である

計算されたミニマックス値は $s_>$ で $\boldsymbol{s &lt; s_&gt;}$ なので、__α 狩りは行なわれません__。
評価値は整数のみが計算されるので、$s < s + 1 ≦ s_>$ となります。そのため、__β 値__ は $s + 1$ のまま更新されず、次の $\boldsymbol{G_2}$ の評価値を計算する際の __ウィンドウ__ は ($s$, $s + 1$) のまま __更新されません__。

### 2 番目の子ノードの計算処理

$G_2$ のノードは、以下のように計算されるので「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」に分類されます。

* min ノードである
* ウィンドウは ($s$, $s+1$) である
* ミニマックス値は $s-$ である

計算された $G_2$ のミニマックス値 $s_-$ は $\boldsymbol{s_- < s}$　なので __α 狩りが行われ__、__残りの子ノードの評価値の計算は省略__ されます。

### 行なわれる処理のまとめ

上記から $C$ の評価値を計算する際には下記の __2 つの子ノードの計算__ が行われます。

* 「__max__, $\boldsymbol{s_>}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」に分類される $G_1$
* 「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s+ 1}$)」に分類される $G_2$

## 計算処理の比較

上記から $C$ の計算を行う際に、αβ 法とスカウト法では __下記の 2 種類の子ノードの計算処理を行う__ ことがわかります。

|子ノード|αβ 法での分類|スカウト法での分類|
|:--|:--|:--|
|$\boldsymbol{G_1}$|__max__, $\boldsymbol{s_>}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)|__max__, $\boldsymbol{s_>}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)|
|$\boldsymbol{G_2}$|__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s_>}$)|__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s+ 1}$)|

それぞれの子ノードで行われる処理を比較します。

### 最初の子ノードの処理の比較

__αβ 法__ の場合は $G_1$ の __ウィンドウ__ が ($\boldsymbol{s}$, $\boldsymbol{∞}$) なので、__max ノード__ である $G_1$ の子ノードの評価値がどのような値であっても __β 狩りが行われることはありません__。

一方、__スカウト法__ の場合は以下の理由から $G_1$ の評価値を計算する際に __β 狩りが行われる可能性__ があります。

* $G_1$ のミニマックス値である $\boldsymbol{s_>}$ __は__ $\boldsymbol{s + 1}$ __以上__ である
* $G_1$ は __max ノード__ なので、子ノードの中に __必ずミニマックス値が $\boldsymbol{s + 1}$ 以上__ のノードが __存在する__
* ウィンドウが  ($s$, $s + 1$) なので、ミニマックス値が $\boldsymbol{s + 1}$ __以上__ の子ノード __以降の子ノードの枝狩りが行われる__。従って、そのような子ノードが __最後の子ノードでない場合__ に __β 狩りが行なわれる__

上記から、$\boldsymbol{G_1}$ のノードの評価値を計算する場合は、__スカウト法__ は __αβ 法以上の効率__ で計算が行われます。下記はそれぞれで行われる処理を図示したものです。

__αβ 法の場合__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/110356de-f33f-468d-bfaa-15437e394b2b.png" width="500">

__スカウト法の場合__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e9948ea2-0207-4bef-b49c-ec93541abbb0.png" width="500">

### 2 番目の子ノードの処理の比較

max ノードでミニマックス値が $\boldsymbol{s_-}$ の場合は、先程「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{∞}$)」と「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s + 1}$)」の場合で __同じ処理が行われる__ ことを示しました。これは、__下記の条件が満たされる場合__ は、__すべての子ノードが fail low の範囲になる__ ため β 狩りが行われず、__すべての子ノードの計算を行う__ ためです。

* max ノードである
* ミニマックス値がウィンドウの α 値以下である

「__max__, $\boldsymbol{s_-}$, ($\boldsymbol{s}$, $\boldsymbol{s_>}$)」の場合は __その条件を満たす__ ので、αβ 法とスカウト法で $\boldsymbol{G_2}$ __の効率は同じ__ になります。

上記の考察から、以下の事がわかります。

:::note warn
__子孫ノードで move ordering が正しく行われなかった場合__ に、null window search の効果によって __スカウト法__ が __αβ 法以上の効率を得ることができる場合がある__。
:::

## 上記の具体例の補足

上記では、$C$ の子ノードの中で __2 番目の子ノード__ のミニマックス値が __はじめて__ $\boldsymbol{s_-}$（$\boldsymbol{s}$ __以下__）__になる例__ を示しましたが、__3 番目以降__ の子ノードのミニマックス値が __はじめて__ $\boldsymbol{s_-}$ __になる場合__ は、__それ以前のすべての子ノード__ の計算処理を __αβ 以上の効率で行うことができる__ ようになります。

従って、__上記の例__ では、__move ordering の精度が悪く__、__最善手の子ノードが後ろの方に配置されるほど__ スカウト法の __効率が αβ よりも高くなることが期待__ できます。

なお、上記の例はスカウト法で null window search の計算後に __αβ 法でのやり直しが行われない__ 場合の例です。__計算のやり直しが行われる場合__ は上記の例のような __単純な比較を行うことはできない__ 点に注意して下さい。

また、上記では __複数のノードで完璧な move ordering が行われない場合は考慮していません__。興味と余裕がある方はそのような場合の比較を行ってみて下さい。

# スカウト法の視覚化について

Mbtree_Anim でスカウト法の視覚化を行えるようにしようと最初は考えていたのですが、話が進まなくなるのと、それほど重要ではない気がしましたので行わないことにしました。余裕がある方は、`calc_score_for_anim` を修正してスカウト法の視覚化を行えるようにしてみて下さい。

# 今回の記事のまとめ

今回の記事では、__完璧な move ordering__ での αβ 法とスカウト法が __同じノードの計算処理を行う__ ため、__効率が同じになる__ ことを示しました。また、スカウト法の効率が αβ 法以上になる具体例を示しました。

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

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

# 次回の記事

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

[^1]:以後は、αβ 法と同じウィンドウで計算をやり直す必要がない場合の説明を省略します
[^2]:$G$ は $N$ の孫ノードなので、孫を表す grandchild の略です
[^3]:$s$ を含まないので ${s_+}$ と表記することはできないので、このような表記にしました