Pythonで〇×ゲームのAIを一から作成する　その166　スカウト法の実装と効率

# 目次と前回の記事

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

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

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

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

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

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

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

# スカウト法の実装と効率の確認

前回の記事では、αβ 法を改良した __スカウト法__ を紹介しました。スカウト法は move ordering を前提とする、以下のような考え方の手法です。

* __精度の高い move ordering__ によって __最善手の子ノードが先頭に移動__ したと __仮定する__
* 先頭の子ノードの処理は αβ 法同じ処理を行い、__2 番目以降の子ノードの処理__ を以下のように行う
* __仮定が正しい場合__ は __null window search を行う__ ことで、__αβ 法以上__ の枝狩りの __効率を得る__ ことができる
* __仮定が正しくない場合__ は __αβ 法で計算処理をやり直し__、計算された評価値が最大の評価値であると __仮定し直して処理を続ける__
* __仮定が正しくない場合__ は null window search を行なった分だけ __αβ 法よりも効率が悪くなる__ が、move ordering の精度が充分高ければ __総合的に見て αβ 法以上の効率を得る__ ことが __期待できる__

今回の記事ではスカウト法を実装し、その効率を確認します。

## null window search に関する補足

[以前の記事](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%8C-3-%E7%A8%AE%E9%A1%9E%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE-null-window-search-%E3%81%AE%E5%88%A9%E7%94%A8%E4%BE%8B)では評価値が 3 種類の場合の null window serach の利用例を紹介しましたが、null window search をそのような目的で利用することはほとんどないと思います。__null window search__ は __一般的に__ スカウト法で利用した場合のように、__ミニマックス値が特定の値以下__（または以上）であるかどうかを __効率よく判定するために利用__ されます。

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

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

* [以前の記事](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)$ と表記する

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

下記は[前回の記事](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e#%E3%82%B9%E3%82%AB%E3%82%A6%E3%83%88%E6%B3%95%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)で説明した __スカウト法のアルゴリズムの再掲__ です。ただし、[前回の記事](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e#null-window-search-%E3%81%AB%E3%82%88%E3%82%8B%E5%8A%B9%E7%8E%87%E5%8C%96)で説明したように、手順 3-1 の処理は null window search なので、前回の記事で「αβ 法」と記述していた部分を null window search に改めました。

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

## ネガスカウト法

スカウト法は一般的には __評価値の符号を反転させる__ ことで __max ノードと min ノードの処理をまとめる__ という __ネガスカウト法__ で実装されることが多いようです。また、プログラムが少しわかりづらくなるので本記事では紹介しませんでしたが、最初の子ノードの処理と、2 番目以降の子ノードの処理をまとめるという実装方法もあります。

具体的なプログラムの例については下記のネガスカウト法の Wikipedia と Chess Programmin  wiki を参照して下さい。

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

https://www.chessprogramming.org/NegaScout

## `ai_scout` の定義

上記のアルゴリズムのスカウト法で着手を選択する __`ai_scout`__ という関数を定義する事にします。__スカウト法__ は __αβ 法に上記の手順 3 を加えたもの__ なので、αβ 法で着手を選択する __`ai_abs_all` を修正して定義__ する事にします。従って、`ai_scout` と `ai_abs_all` の __仮引数や返り値は同じ__ です。

下記は __`ai_scout`__ を定義するプログラムです。下記では表示を省略していますが、11 行目の前で __[`ai_abs_all` と同じ方法で move ordering の処理を行う](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e#ai_abs_all-%E3%81%AE%E4%BF%AE%E6%AD%A3)__ ことで、move ordering 利用する AI の関数が同じであれば、__同じノードで同じ move ordering が行われます__。

* __6 行目__：関数名を `ai_scout` に修正する
* __12 ~ 16 行目__：最初の子ノードの評価値を αβ 法と同じウィンドウで計算し、$s$(`score`) と α 値(`alpha`) を計算する
* __17 行目__：β 狩りが行なわれる場合は残りの子ノードの処理が省略されるので、β 狩りが行なわれない場合のみ残りの子ノードの処理を行うように修正する
* __18 ~ 28 行目__：list の[スライス表記](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#%E3%82%B9%E3%83%A9%E3%82%A4%E3%82%B9%E8%A1%A8%E8%A8%98-%E3%81%9D%E3%81%AE-1start-%E3%81%A8-end)を使って 2 番目以降の子ノードの繰り返し処理を行うように修正する
* __19 ~ 21 行目__：ウィンドウを (α 値, α 値 + 1) とした null window search で子ノードの評価値の計算を行ない、$s$ を更新する（手順 3-1）
* __22、23 行目__：β 値 ≦ $s$ の場合は β 狩りを行うので繰り返し処理を終了する（手順 3-2-1）
* __24 ~ 28 行目__：α 値 < $s$ < β 値[^1] の場合は、αβ 法と同じ (α 値, β 値) のウィンドウで子ノードの評価値の計算をやり直す。26、27 行目で β 狩り、28 行目で β 値の更新処理を行う（手順 3-2-2）
* __29 ~ 46 行目__：min ノードで上記と同様の処理を行うように修正する

```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_scout(mb, debug=False, shortest_victory=False,
 7               init_ab=False, use_tt=False, ai_for_mo=None,
 8               params={}, sort_allnodes=False, calc_count=False):        
 9      count = 0
10      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
11          if mborig.turn == Marubatsu.CIRCLE:
12              x, y = legal_moves[0]
13              mb = deepcopy(mborig)
14              mb.move(x, y)
15              score = ab_search(mb, tt, alpha, beta)
16              alpha = max(alpha, score)
17              if score < beta:
18                  for x, y in legal_moves[1:]:
19                      mb = deepcopy(mborig)
20                      mb.move(x, y)
21                      score = max(score, ab_search(mb, tt, alpha, alpha + 1))
22                      if score >= beta:
23                          break
24                      elif score > alpha:
25                          score = max(score, ab_search(mb, tt, alpha, beta))
26                          if score >= beta:
27                              break
28                          alpha = max(alpha, score)
29          else:
30              x, y = legal_moves[0]
31              mb = deepcopy(mborig)
32              mb.move(x, y)
33              score = ab_search(mb, tt, alpha, beta)
34              beta = min(beta, score)
35              if score > alpha:
36                  for x, y in legal_moves[1:]:
37                      mb = deepcopy(mborig)
38                      mb.move(x, y)
39                      score = min(score, ab_search(mb, tt, beta - 1, beta))
40                      if score <= alpha:
41                          break
42                      elif score < beta:
43                          score = min(score, ab_search(mb, tt, alpha, beta))
44                          if score <= alpha:
45                              break
46                          beta = min(beta, 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_scout(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:
            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")

    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 marubatsu import Marubatsu
from copy import deepcopy

@ai_by_score
-def ai_abs_all(mb, debug=False, shortest_victory=False,
+def ai_scout(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 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)
+           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:
-           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) 
+           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)   
元と同じなので省略
```
</details>

:::note
`ai_abs_all` では、max ノードでは `score` にそれまでに計算された子ノードの評価値の最大値を計算する必要があるため、`score` を負の無限大で初期化し、子ノードの繰り返し処理の中で `score = max(score, ab_search(mb, tt, alpha, beta)` という計算を行なっていました。

一方、`ai_scout` では最初の子ノードの処理を繰り返し処理の前に行うため、最初の子ノードの評価値が計算された時点ではその評価値が最大値となります。そのため `score` を負の無限大で初期化するという処理を削除し、15 行目では最初の子ノードの評価値を `score` にそのまま代入するという処理を行っています。
:::

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

なお、スカウト法は move ordering を前提とするアルゴリズムですが、__move ordering を行わない場合でも効率が悪いだけで 強解決であることには変わらない__ ので、下記では move ordering を行わない場合も確認しています。また、[先頭のみの 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 の両方を確認するように修正しました。

```python
from util import Check_solved
from ai import ai2s, ai14s

for ai_for_mo in [None, ai2s, ai14s]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                for sort_allnodes in [False, True]:
                    print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab} sort: {sort_allnodes}")
                    params = {
                        "ai_for_mo": ai_for_mo,
                        "shortest_victory": shortest_victory,
                        "init_ab": init_ab,
                        "use_tt": use_tt,
                        "sort_allnodes": sort_allnodes,
                    }
                    Check_solved.is_strongly_solved(ai_scout, params=params)
```

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

```diff_python
from util import Check_solved
from ai import ai2s, ai14s

for ai_for_mo in [None, ai2s, ai14s]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
+               for sort_allnodes in [False, True]:
-                   print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab}")
+                   print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab} sort: {sort_allnodes}")
                    params = {
                        "ai_for_mo": ai_for_mo,
                        "shortest_victory": shortest_victory,
                        "init_ab": init_ab,
                        "use_tt": use_tt,
-                       "sort_allnodes": True,
+                       "sort_allnodes": sort_allnodes,
                    }
                    Check_solved.is_strongly_solved(ai_scout, params=params)
-               Check_solved.is_strongly_solved(ai_abs_all, params=params)
+               Check_solved.is_strongly_solved(ai_scout, params=params)
```
</details>

実行結果

```
ai_for_mo: None, sv: False, use_tt: False, init_ab: False sort: False
100%|██████████| 431/431 [00:04<00:00, 100.60it/s]
431/431 100.00%
ai_for_mo: None, sv: False, use_tt: False, init_ab: False sort: True
100%|██████████| 431/431 [00:04<00:00, 101.34it/s]
略
```

## スカウト法の効率の確認

__スカウト法の効率を確認__ するために、[以前の記事](https://qiita.com/ysgeso/items/97c293d8876190849ec8#%E3%81%99%E3%81%B9%E3%81%A6%E3%81%AE%E5%B1%80%E9%9D%A2%E3%81%A7%E3%81%AE%E5%90%88%E8%A8%88%E3%81%A7%E3%81%AE%E6%AF%94%E8%BC%83)で行った下記の方法で、__αβ 法とスカウト法の枝狩りの効率を比較__ することにします。ただし、スカウト法は move ordering を行うことが前提のアルゴリズムなので、move ordering を行わない場合の比較は行ないません。なお、move ordering の処理では [前回の記事](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e#ai_abs_all-%E3%81%AE%E4%BF%AE%E6%AD%A3)で修正した `ai_abs_all` と同じ処理を `ai_scout` で行うので、仮引数 `ai_for_mo` に代入された move ordering を行う AI の関数が同じであれば、__`ai_abs_all` と `ai_scout` は同一の局面に対して同じ move ordering__ を行ないます。

* 同一局面を除いた 〇×ゲームのすべての局面に対して、同一の設定で αβ 法とスカウト法で計算を行う
* それぞれの場合で、計算されたノードの数の合計を比較することで処理の効率を比較する

下記はその比較を行うプログラムです。以前の記事のプログラムとの違いは以下の通りです。なお、結果の数値が多くなりすぎるとわかりづらくなるので、move ordering に関しては __先頭のみの move ordering だけで比較__ しました。 

* 以前の記事では全ノードの move ordering を行うかどうかで比較を行ってたが、下記のプログラムでは `ai_abs_all` と `ai_scout` の比較を行っている
* 結果の表示をわかりやすくなるように少しだけ変えた

```python
from util import load_mblist
from ai import ai10s

mblist = load_mblist("../data/mblist_by_board_min.dat")
for ai_for_mo in [ai10s, ai14s]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
                count = 0
                count2 = 0
                for mb in mblist:
                    count += ai_abs_all(mb, ai_for_mo=ai_for_mo,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        sort_allnodes=False, calc_score=True, calc_count=True)
                    count2 += ai_scout(mb, ai_for_mo=ai_for_mo,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        sort_allnodes=False, calc_score=True, calc_count=True)
                print("abs count=", count)
                print("scout count=", count2)
```

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

```diff_python
from util import load_mblist
from ai import ai10s

mblist = load_mblist("../data/mblist_by_board_min.dat")
for ai_for_mo in [ai10s, ai14s]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
                count = 0
                count2 = 0
                for mb in mblist:
                    count += ai_abs_all(mb, ai_for_mo=ai_for_mo,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        sort_allnodes=False, calc_score=True, calc_count=True)
-                   count2 += ai_abs_all(mb, ai_for_mo=ai_for_mo,
+                   count2 += ai_scout(mb, ai_for_mo=ai_for_mo,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
-                                       sort_allnodes=True, calc_score=True, calc_count=True)
+                                       sort_allnodes=False, calc_score=True, calc_count=True)
-               print("count=", count)
-               print("count2=", count2)
+               print("abs count=", count)
+               print("scout count=", count2)
```
</details>

実行結果

```
ai_for_mo: <function ai10s at 0x0000016BFAD09EE0>, sv: False, init_ab: False, use_tt: False
abs count= 13866
scout count= 14726
ai_for_mo: <function ai10s at 0x0000016BFAD09EE0>, sv: False, init_ab: True, use_tt: False
abs count= 8769
scout count= 9400
ai_for_mo: <function ai10s at 0x0000016BFAD09EE0>, sv: False, init_ab: False, use_tt: True
abs count= 10384
scout count= 10392
略
```

下記は実行結果をまとめた表です。一番上の行の ab は init_ab、tt は use_tt の値で 〇 は True、× は False を表します。各セルの __上段が `ai_abs_all`__、__下段が `ai_scout`__ の場合です。

最短の勝利を目指さない（`shortest_victory=False`）場合

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __`ai10s`__ | 13866<br>14726 | 8769<br>9400 | 10384<br>10392 | 6651<br>6837 | 
| __`ai14s`__ | 10679<br>10839| 6127<br>6194 | 8792<br>8761 | 5016<br>5028 |

最短の勝利を目指す（`shortest_victory=True`）場合

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __`ai10s`__ | 15135<br>15645 | 13145<br>14052 | 11091<br>11135| 9743<br>9918 | 
| __`ai14s`__ | 10691<br>10869 | 9263<br>9441 | 8808<br>8850 | 7561<br>7603 |

上記の結果から、__`ai10s`__ を利用して move ordering を行う場合は、__下段のスカウト法のほうが__ 上段の αβ 法よりもほとんどの場合で評価値を計算したノードの数が多く、__効率が悪い__ ことがわかります。これは、`ai10s` による move ordering は __精度が充分に高くない__ のでスカウト法の __仮定が正しくない場合が多く生じるため__、null window search の後で αβ 法で計算の __やり直しを行う必要がある回数が多いから__ だと考えられます。このように、__move ordering の精度が低い場合__ はスカウト法の効率は __αβ 法よりも悪くなります__。

一方、__弱解決の AI__ である __`ai14s`__ を利用して move ordering を行う場合は、ほとんどの場合でスカウト法と αβ 法の効率が __少しだけ悪化するかほとんど変わらない__ ことがわかります。その原因としては、以下のようなものが考えられます。

* __〇× ゲーム__ で計算する __評価値の範囲__ が -1 ~ 1 や、-2 ~ 3 のように __もともと狭い__ ため、__ウィンドウ幅が 1__ の null window search を行なっても __ウィンドウ幅がほとんど狭くならず__、枝狩りの __効率が変わらないか、ほとんど向上しない__
* __`ai14s`__ は __強解決の AI ではない__ ので、__いくつかのノード__ で先頭の子ノードの評価値が最大値にならず、null window search の後の __やり直しを行う必要が何回か生じる__

また、枝狩りは枝狩りを行ったノードの __すべての子孫ノードが対象となる__ ので、一般的にはゲーム木の深さ __深い程効果が高まります__。__〇× ゲームのゲーム木の深さは 9__ であり __あまり深くない__ ので、それが原因で多くのノードでスカウト法による効率の上昇が得らなかった可能性が考えられます。

## 一般的なスカウト法の効率

上記の結果から、残念ながら __〇× ゲーム__ の場合は __スカウト法による効率の上昇は得られない__ ことがわかりましたが、move ordering の精度が高ければ __スカウト法が多くのゲームで有効であることが確認__ されています。例えば、[Wikipedia のスカウト法に関する記事](https://ja.wikipedia.org/wiki/Negascout)には「__チェスプログラムではアルファ・ベータ法に比べ、典型的には10％程度のパフォーマンス上昇が見込めると言われる__」と記述されています。また、将棋の AI などでもスカウト法を利用することで効率の上昇が見込めるようです。

# 精度が 100 % の move ordering の場合のスカウト法

__move ordering の精度が 100 %__ であれば、2 番目以降の __すべての子ノード__ の __null window search__ の結果が max ノードでは fail low、min ノードでは fail high になるため、__αβ 法での計算のやり直しを行う必要が生じません__。そのため、その場合は __必ず αβ 法以上の効率__ で計算を行うことができます。

__精度が 100 % の move ordering__ は __強解決の AI__ を利用することで行なえるので、__強解決の AI__ である __[`ai_gt6`](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#bestmoves_by_board-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ を使った move ordering を行う下記のプログラムでそのことを確認することにします。なお、__先頭の子ノードが最善手を着手したノード__ であれば __move ordering の精度が 100 % になる__ ので、以下の処理では __先頭のみの move ordering を行う__ ことにします。また、`ai_gt6` を利用する際には、__局面と最善手の対応表のデータが必要__ となるので、そのデータを `load_bestmoves` を使ってファイルから読み込んでいます。

```python
from util import load_bestmoves
from ai import ai_gt6

bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
params = {"bestmoves_by_board": bestmoves_by_board}
for ai_for_mo in [ai_gt6]:
    for shortest_victory in [False, True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
                count = 0
                count2 = 0
                for mb in mblist:
                    count += ai_abs_all(mb, ai_for_mo=ai_for_mo, params=params,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
                    count2 += ai_scout(mb, ai_for_mo=ai_for_mo, params=params,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
                print("abs count=", count)
                print("scout count=", count2)
```

実行結果

```
ai_for_mo: <function ai_gt6 at 0x0000016BFAD0AB60>, sv: False, init_ab: False, use_tt: False
abs count= 13151
scout count= 13151
ai_for_mo: <function ai_gt6 at 0x0000016BFAD0AB60>, sv: False, init_ab: True, use_tt: False
abs count= 8225
scout count= 8225
ai_for_mo: <function ai_gt6 at 0x0000016BFAD0AB60>, sv: False, init_ab: False, use_tt: True
abs count= 10035
scout count= 10035
略
```

:::note
強解決の AI である [`ai_abs_tt4`](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc#%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%81%A4%E3%81%8D-%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E5%A0%B4%E5%90%88) などの、αβ 法を利用した AI を move ordering を行うために利用することもできますが、`ai_abs_tt4` は ゲーム木を探索する必要があるため、局面と最善手の対応表を使って最善手を選択する `ai_gt6` と比べて計算速度がかなり遅く、上記のプログラムの実行時間がかなり長くなってしまうという問題があります。興味がある方は実際に確認してみて下さい。

なお、余談ですが `ai_gt6` は最善手のみを計算する機能しか持たないので、`ai_gt6` を使って全ノードの move ordering を行うことはできません。また、`ai_gt7` はすべての子ノードの評価値を計算する機能を持ちますが、× の手番では評価値の低いほうが × が有利になるという評価値を計算するので `ai_scout` で `ai_gt7` を使って全ノードの move ordering を行うことはできません。
:::

下記は実行結果をまとめた表です。実行結果から、__最短の勝利を目指さない場合__ は、下段の __スカウト法の結果__ と上段の __αβ 法の結果が全く同じ__ であり、__枝狩りの効率が変わらない__ ことが確認できます。

なお、下記の表では __最短の勝利を目指す場合__ は __結果が同じになりません__ が、それには上記のプログラムでは最短の勝利を目指す際の __move ordering の精度が 100 % ではないから__ です。その理由については後で説明しますが、余裕がある方は考えてみて下さい。

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __最短の勝利を目指さない__ | 13151<br>13151 | 8225<br>8225 | 10035<br>10035 | 6080<br>6080 | 
| __最短の勝利を目指す__ | 14404<br>14389| 13215<br>13345 | 10634<br>10590 | 9691<br>9670 |

[前回の記事](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e#%E3%82%B9%E3%82%AB%E3%82%A6%E3%83%88%E6%B3%95%E3%81%AE%E6%80%A7%E8%B3%AA%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E7%AD%86%E8%80%85%E3%81%AE%E8%AA%A4%E8%A7%A3)で __筆者が__ スカウト法が __下記のような性質を持つと誤解していた__ と書きましたが、実際にスカウト法を下記のように誤解している人は多いのではないかと思います。

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

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

また、[Wikipedia のネガスカウト法の説明](https://ja.wikipedia.org/wiki/Negascout)には以下のような記述があり、この記述からスカウト法が上記のような性質を持っていると誤解した人が多いのではないでしょうか？

「NegaScout が効率よく機能するかどうかは手の並べ替えの精度に依存しており、初めに調べる手が最善手である場合に最も効率が良くなる」

しかし、上記の実行結果からわかるように、__move ordering の精度が 100%__ の場合は __αβ 法とスカウト法の効率は全く同じ__ になります。筆者は `ai_scout` に何かのバグがあるため上記のような結果になったのではないかと最初は思っていたのですが、色々と考えた結果、`ai_scout` は正しい処理が行っていることがわかりました。

move ordering の __精度が 100 % の場合__ に αβ 法とスカウト法の __効率が同じになる理由__ は、__精度が 100 % の場合はどちらも全く同じ処理を行う__ からです。同じ処理が行われる理由と、スカウト法がどのような場合に枝狩りの効率を上昇させるかについては次回の記事で説明します。余裕がある方はその理由について考えてみて下さい。

今回の記事ではこのような __誤解が起きた理由__ についての __筆者の考察__ を説明します。筆者と同じ誤解をしていた人は、上記のような誤解が生じる原因について少し考えてみて下さい。

## 誤解の原因の考察

上記のような誤解が起きる原因について考えてみたのですが、スカウト法が以下のような性質を持つからではないかと思います。

[前回の記事](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e#%E7%B7%8F%E5%90%88%E7%9A%84%E3%81%AA%E3%82%B9%E3%82%AB%E3%82%A6%E3%83%88%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)で説明したように、__スカウト法__ は __それまでに計算したノードの評価値__ が子ノードの評価値の __最大値である[^2]という仮定__ をたて、その __仮定が正しい場合__ に null window search によって __枝狩りの効率が高くなるよう工夫__ したアルゴリズムです。

また、仮定が正しいかどうかによって、__2 番目以降の子ノードの評価値を計算する際の効率__ が __αβ 法と比較__ して以下のようになります。

* 仮定が __正しい場合__ は効率が __同じか良くなる__
* 仮定が __間違っている場合__ は __効率が悪くなる__

__仮定が正しい子ノード__ によって得られた __効率の改善の合計__ を $\boldsymbol{A}$、__仮定が間違っている子ノード__ による __効率の悪化の合計__ を $\boldsymbol{B}$ と表記した場合に、αβ 法と比較した際の __全体の効率の差__ は $\boldsymbol{A - B}$ となります。従って、$\boldsymbol{A > B}$ の時にスカウト法のほうが αβ 法よりも __効率が良くなり__、$\boldsymbol{A < B}$ の場合はスカウト法のほうが __効率が悪くなります__。

### B の性質の考察

スカウト法では __仮定が間違っている場合__ は、__null window search__ を行う必要がある __分だけ必ず効率が悪く__ なります。move ordering の __精度が高い程__ 仮定の __間違いが少なくなる__ ので、$\boldsymbol{B}$ は __仮定が間違っている子ノードが多い程大きく__ なり、move ordering の __精度が 100% の場合__ は間違った仮定の子ノードが存在しなくなるため $\boldsymbol{B = 0}$ で __最小となります__。

### A の性質の考察

先程の 〇× ゲームでの効率の比較では残念ながらスカウト法のほうが αβ 法よりも効率が高いという実例を示すことはできませんでしたが、先程説明したように、[スカウト法の Wikipedia](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e#%E7%B7%8F%E5%90%88%E7%9A%84%E3%81%AA%E3%82%B9%E3%82%AB%E3%82%A6%E3%83%88%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)には、__チェスでは実際にスカウト法のほうが αβ 法よりも 10 % 程度効率が高くなる__ という __実例が示されています__。このことから、__move ordering の精度が高ければ__ $\boldsymbol{A > B}$ となることが __実際にある__ ことがわかります。

また、__move ordering の精度が低い__ と __仮定が正しい子ノードの数が減る__ ため、$\boldsymbol{A}$ __が減る__ と考えられます。

上記の考察から、__move ordering の精度__ と $\boldsymbol{A}$、$\boldsymbol{B}$、$\boldsymbol{A - B}$ が以下のような関係を持つと考えた人は多いのではないでしょうか？

* $\boldsymbol{A}$ は move ordering の __精度が 0 % の時に 0__ となり、__精度が 100 % の時に最大__ になる
* $\boldsymbol{B}$ は move ordering の __精度が 0 % の時に 最大__ となり、__精度が 100 % の時に 0__ になる
* $\boldsymbol{A - B}$ は move ordering の __精度が 0 % の時に負の値の最小値__ となり、精度が高くなるにつれ大きくなり、__精度が 100 % の時に正の値の最大値__ になる

__上記の関係__ を __グラフで視覚化__ すると下記のようになります。__緑色の__ $\boldsymbol{A - B}$ のグラフの中で、効率の差が 0 であることを表す __灰色の横線より上になっている部分__ が、__スカウト法のほう__ が αβ 法よりも __効率が良い__ ことを表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/394159a0-e95a-4c5d-8fea-c295a1f159e3.png" width="350">

:::note
上記のグラフでは便宜的に  $\boldsymbol{A}$ と  $\boldsymbol{B}$ の最大値を同じにしましたが、異なる最大値を持つようなグラフで視覚化してもかまいません。
:::

__上記のグラフから__、先程の考察が正しければ move ordering の __精度が 100% の場合に $\boldsymbol{A - B}$ が最大となる__ ので、「move ordering の精度が 100% の場合にスカウト法の効率が αβ 法と比較して最も高くなる」事がわかりますが、__実際にはそうはなりません__。これは上記で示した __$\boldsymbol{A}$ の性質の考察__ のどこかが __間違っている__ からです。どこが間違っているかについて少し考えてみて下さい。

### A の性質の考察の間違い

上記の考察で間違っているのでは、「__move ordering の精度が低い程__ と __仮定が正しい子ノードの数が減る__ ため、$\boldsymbol{A}$ __が減る__ と考えられる」という部分です。この考察を行なった人はおそらく上記のグラフのように $A$ は move ordering の __精度が減ると__ 0 に向けて __常に減少（単調減少）していく__ と考えていたのではないかと思います。しかし、実際には $\boldsymbol{A}$ は move ordering の __精度が 100 % に近づくと 0 に向かって減る__ ようになり、__精度が 100 % になると 0 になる__ という性質があります。そのため、move ordering の __精度が 100% の場合__ は $\boldsymbol{A = B = 0}$ となるので、αβ 法とスカウト法の __効率が同じ__ になります。

このことをグラフにすると以下のようになります。グラフからわかるように __スカウト法が αβ 法よりも効率が高くなる可能性がある__ のは __特定の範囲の精度だけ__（下図の場合は精度が 50 % 以上 100 % 未満の範囲）で、一定の精度を下回るとスカウト法の効率が下回り、__100 % になると効率が等しく__ なります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e2fdeaa4-f589-4f34-a269-a8702958f39a.png" width="350">

なお、__上記のグラフは正確なグラフでは全くありません__。実際には $\boldsymbol{A}$ と $\boldsymbol{B}$ がどのようなグラフになるかは、__ゲーム木によって異なります__。$\boldsymbol{A}$ が上記のグラフのように上に綺麗な凸のようなグラフになるとは限りませんし、$\boldsymbol{B}$ が直線になるとは限りません。また、上記のグラフでは精度が 50 % の所で $\boldsymbol{A - B}$ が 0 となっていますが、一般的にはもっと高い精度の所で 0 となります。

:::note
上記の説明で「スカウト法が αβ 法よりも効率が高くなる __可能性がある__」と記述したのは、下記のグラフのような場合はスカウト法の効率が __常に αβ 法以下__ になる場合があるからです。先程の 〇×ゲームの効率の比較の結果から、〇× ゲームの場合はおそらく下記のグラフのようになっている可能性が高いでしょう。ただし、__どのような場合でも move ordering の精度が 100 % の場合は効率が同じ__ になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/743ecc8c-4224-4f3f-8e51-f94e9d3791a5.png" width="350">
:::

### スカウト法と move ordering の精度の関係

move ordering の精度が 100 % の場合に、αβ 法とスカウト法の効率ga
同じになるという事実から、スカウト法では move ordering の精度が __一定以上高ければ__、効率の上昇がほぼ 0 になるため __それ以上精度を高くしても意味がない__ のではないかと __錯覚した人がいるかもしれません__ が、それは __間違い__ です。その理由は、以下通りです。

* move ordering の精度を高くすると αβ 法の効率は上昇する
* move ordering が 100 % に近くなると αβ 法の効率との差はほとんどなくなるが、αβ 法の効率が上昇するということは __スカウト法の効率も上昇する__

先程のグラフでは move ordering の精度と αβ 法とスカウト法の効率の差をグラフにしましたが、__move ordering の精度__ と αβ 法とスカウト法の __それぞれの効率__ をグラフにすると下記のようになります。グラフから move ordering の精度を高くすると、最後は上昇速度が αβ 法に比べて緩やかになりますが、最大値に向かって __上昇し続ける__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c248f52e-f8bb-4a7c-bb86-e289909c769f.png" width="350">

また、このグラフから、スカウト法は move ordering の精度が一定以上の場合に、__αβ 法よりも低い move ordering の精度__ で __最高の効率__（100 % の move ordering での αβ 法）に __より近い効率を得ることができるように工夫__ したアルゴリズムであることがわかります。

:::note
上記のグラフも __正確なグラフでは全くありません__。実際には $\boldsymbol{B}$ が上記のグラフのように直線になることはまずありませんし、$\boldsymbol{A}$ はもっと複雑な形になるでしょう。
:::

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

:::note warn
* αβ 法もスカウト法も move ordering の精度を上げると効率が上昇する
* αβ 法もスカウト法も move ordering の精度が 100 % の場合の効率は同じである
* move ordering の __精度が一定以上の場合__ に、__スカウト法の方が__ αβ 法よりも __早く最大の効率に近づいていく__ ことが期待できる
:::

move ordering の __精度が 100 % の場合__ は αβ 法とスカウト法の効率が同じになるので、その場合は __スカウト法を利用する必要がないのではないか__ と思う人がいるかもしれませんが、__そのような心配をする必要はありません__。その理由は __精度が 100 % の場合は move ordering だけで最善手を計算できる__ ので __αβ 法やスカウト法を利用する意味がない__ からです。

:::note
move ordering の精度が 100 % の場合に αβ 法とスカウト法が同じ処理を行うことを示した論文がないか探してみたところ、[Trends in Game Tree Search](https://www.researchgate.net/publication/2643632_Trends_in_Game_Tree_Search)という論文で以下のように言及されていました。

「On the other hand, if the tree would be perfectly ordered again NegaScout and Alpha-Beta would search the same subtree」

以下は、筆者による上記の意訳です。

一方、ゲーム木が完全（100 % の精度）に並べ替えられていた場合は、ネガスカウト法と αβ 法は再び同じ部分木を探索する（同じ枝狩りの処理を行う）ようになる。

なお、他にもこのことを言及している論文や文献があるかもしれません。
:::

:::note
ChatGPT に「move ordering が完ぺきな場合に、同じ move ordrering を行った場合はスカウト法は αβ 法よりも効率がどれくらい良くなりますか？」と質問した所、長い答えの中で「完璧な move ordering がある場合、Scout 法は αβ 法よりもさらに少ないノード数で済むことがあります」という筆者と同じ誤解の回答が返ってきました。その後それは違うのではないかという質問をいくつかした所、誤解は無事に解けましたが、やはり生成 AI の回答を鵜呑みにするのは危険なようです。
:::

### Wikipedia 内での説明についての補足

先程紹介した __Wikipedia の下記の説明__ は、誤解を生じさせるような表現になっていると思いますが、__厳密には間違ってはいない__ と思います。

「この様に NegaScout が効率よく機能するかどうかは手の並べ替えの精度に依存しており、初めに調べる手が最善手である場合に最も効率が良くなる」

その理由は、上記の説明の中に「__αβ 法と比べて__ 効率が良くなる」とは __書いておらず__、move ordering の __精度が高い程効率が良くなる__ のは __事実__ だからです。

ただし、__スカウト法__ は __αβ 法の効率を高めるため__ に考え出された手法なので、スカウト法の効率について言及した場合は __αβ 法と比べてどれくらい効率が良くなっているか__ について言及していると __考えるのが自然ではないか__ と思います。上記の Wikipedia の説明から、最終的にスカウト法の効率が αβ 法と同じになると思った人はほとんどいないのではないでしょうか？これが筆者が上記の説明が誤解を生じさせるような表現であると考える理由です。

## 最短の勝利を目指す場合の検証

下記は先ほどの move ordering の精度が 100 % の場合の効率の比較結果の再掲です。

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __最短の勝利を目指さない__ | 13151<br>13151 | 8225<br>8225 | 10035<br>10035 | 6080<br>6080 | 
| __最短の勝利を目指す__ | 14404<br>14389| 132157<br>13345 | 10634<br>10590 | 9691<br>9670 |

上記の結果では、__最短の勝利を目指す場合__ に αβ 法とスカウト法の効率が一致していません。この結果は __精度が 100 % の move ordering__ を行った場合に αβ 法とスカウト法の __効率が同じになる__ という先程の説明に __矛盾している__ ように思えるかもしれません。このようなことが起きる原因について少し考えてみて下さい。

そのようなことが起きる原因は、__最短の勝利を目指す場合__ は複数の最善手の中から __最短で勝利する合法手の評価値が最も高く__ なりますが、__`ai_gt6`__ は __すべての最善手に対して同じ評価値を計算する__ ため、__`ai_gt6`__ による move ordering によって __最大の評価値を持つ子ノードが先頭に移動しない場合がある__ からです。

このように、__move ordering の精度__ は、__強解決の AI を利用すれば常に 100 % となるわけではありません__。move ordering を行う AI は、__決着がついた局面に対して計算される評価値に合ったものにする必要がある__ 点に注意が必要です。

最短の勝利を目指す場合は、下記のプログラムのように __最短の評価値を計算する場合の最善手を記録したファイル__（__bestmoves_by_board_shortest_victory.dat__）を利用する必要があります。なお、下記では先ほどと異なり最短の勝利を目指す場合のみの計算を行っています。

```python
bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board_shortest_victory.dat")
params = {"bestmoves_by_board": bestmoves_by_board}
for ai_for_mo in [ai_gt6]:
    for shortest_victory in [True]:
        for use_tt in [False, True]:
            for init_ab in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
                count = 0
                count2 = 0
                for mb in mblist:
                    count += ai_abs_all(mb, ai_for_mo=ai_for_mo, params=params,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
                    count2 += ai_scout(mb, ai_for_mo=ai_for_mo, params=params,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        calc_score=True, calc_count=True)
                print("abs count=", count)
                print("scout count=", count2)
```

実行結果

```
ai_for_mo: <function ai_gt6 at 0x0000016BFAD0AB60>, sv: True, init_ab: False, use_tt: False
abs count= 11106
scout count= 11106
ai_for_mo: <function ai_gt6 at 0x0000016BFAD0AB60>, sv: True, init_ab: True, use_tt: False
abs count= 9718
scout count= 9718
ai_for_mo: <function ai_gt6 at 0x0000016BFAD0AB60>, sv: True, init_ab: False, use_tt: True
abs count= 8955
scout count= 8955
ai_for_mo: <function ai_gt6 at 0x0000016BFAD0AB60>, sv: True, init_ab: True, use_tt: True
abs count= 7706
scout count= 7706
```

実行結果をまとめた表は省略しますが、上記の実行結果から、move ordering の精度が 100 % の場合は __最短の勝利を目指す場合__ でもスカウト法と αβ 法の __効率が同じ__ になることがわかります。

# 今回の記事のまとめ

今回の記事ではスカウト法の実装を行い、いくつかの条件で αβ 法の効率と比較しました。また、直観に反して move ordering の精度が 100 % の場合に αβ 法とスカウト法の効率が同じになることを示しました。

次回の記事では move ordering の精度が 100 % の場合に αβ 法とスカウト法の効率が同じになる理由について説明します。

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

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

# 次回の記事

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

[^1]:24 行目の処理は 22 行目の β 値 ≦ $s$ の条件式が False の場合に実行されるので α 値 < $s$ を判定するだけでかまいません
[^2]:これは max ノードの場合で、min ノードの場合は最小値であるという仮定をたてます