Pythonで〇×ゲームのAIを一から作成する　その164　move ordering を行う AI の定義と dict の要素の並べ替え

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc

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

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

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

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

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

# スカウト法と move ordering

前回の記事では、__αβ 法の効率を高める__ ために使われる手法として __null window search__ を紹介しました。null window search を使った手法の一つに __スカウト（scout）法__[^1] があります。スカウト法は[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29)で説明した、子ノードの __評価値の計算の順番__ を、max ノードでは最も評価値の高い（min ノードでは最も評価値の低い）と __思われる__ 子のノードを最初に行うように __並べ替える__（order）ことで αβ 法の枝狩りの効率を向上させる、__move ordering を前提とする手法__ です。つまり、__スカウト法__ は __move ordering を行う αβ 法の効率__ を __さらに上昇させる__ という手法です。

今回の記事ではこのスカウト法について説明しようと最初は考えていたのですが、__スカウト法による枝狩りの効率の上昇を確認__ するためには、__move ordering を行う αβ 法__ による枝狩りの __効率と比較する必要__ があります。そこで、今回の記事では __move ordering を行う αβ 法の AI の関数を定義__[^2]してその枝狩りの効率を確認し、次回の記事でスカウト法を実装してその効率を比較することにします。

## move ordering の精度

上記の move ordering の説明で最も評価値の高いと __思われる__ と説明したのは、一般的には __move ordering の精度（正確性）は 100 % ではないからです__。従って __move ordering__ によって __最も評価値が高い子ノードが先頭になるとは限りません__。

その理由は、__move ordering の精度が 100 %__ であれば、__move ordering だけを使って最善手を計算することができる__ からです。αβ 法を利用した AI の __目的は最善手を求めること__ なので、move ordering の精度が 100 % であれば、__αβ 法を利用する必要はありません__。

なお、__精度__ は状況によって __さまざまな計算方法__ があり、本記事では __正解率__ を精度とすることにします。具体的には、子ノードの順番の __並べ替えを正しく行うことができる割合__ のことを __move ordering の精度__ と呼ぶことにします。従って、move ordering の __精度が 100 %__ の場合は __必ず正しい順番で並べ替えが行われます__。

:::note
精度として良く使われる他の指標には相対誤差があります。相対誤差は「絶対誤差／真の値」で計算できます。ただし、__真の値__ は __正確な値__ を、__絶対誤差__ は __計算した値と真の値の差の絶対値__ を表す用語です。また、計算や計測などによって求められた、__真の値に近い値__ と考えられる値のことを __近似値__ と呼びます。

例えば真の値が 10、近似値が 101 の場合は、絶対誤差は 1 で、相対誤差は 1 / 100 = 1 % となります。この場合は相対誤差が 0 となった場合が最も精度が高くなります。
:::

## move ordering を行うアルゴリズムに求められる性質

__move ordering__ は、何らかのアルゴリズムで __評価値が最も高い子ノードを計算__ し、その子ノードが先頭になるように __合法手の順番を並べ替える__ 処理を行います。その際に、そのアルゴリズムが __以下のような性質を持つ__ ことが __重要__ になります。 その理由について少し考えてみて下さい。

* 評価値が最も高い子ノードを __短い時間で計算できる__
* 評価値が最も高い子ノードの計算が __ある程度以上の精度__ を持つ。ここでいう精度とは、先程説明した __正解率__ のことである

__短い時間で計算できる必要がある理由__ は、move ordering による __枝狩りの効率の上昇による処理時間の短縮よりも__、move ordering のための __計算時間が上回ってしまう__ ことになり、__全体の処理時間がかえって長くなってしまう__ からです。

__ある程度以上の精度を持つ必要がある理由__ は、精度が低いと、move ordering によって子ノードの評価値の順で __うまく並べ替えることができなくなり__、枝狩りの効率を高めることができなくなるからです。そのことは、[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#%E6%A7%98%E3%80%85%E3%81%AA-ai-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E8%A8%88%E7%AE%97)で __精度が異なる AI の関数__ で __先頭の子ノードのみを入れ替えた場合__ の __枝狩りの効率を比較__ することで確認済です。

:::note
move ordering では数多くのアルゴリズムが考えられているので、本記事ではそのすべてを紹介することはできません。参考までに Chess programming wiki の move ordering のリンクを下記に紹介します。
:::

https://www.chessprogramming.org/Move_Ordering

## move ordering のアルゴリズムの種類と本記事が採用するアルゴリズム

__move ordering__ のアルゴリズムの中の有力な手法の一つに __反復深化（iterative deepening）__ という手法を利用して __最善手__ を __効率よく高い精度で計算__ するという手法がありますが、その手法は __ゲームの決着がついたリーフノードの評価値を元にミニマックス値を計算する__ という手法では __利用することができない__ ので今回の記事では紹介しません。反復深化については必要があれば今後の記事で紹介したいと思いますが、興味がある方は参考までに wikipedia と Chess programming wiki の記事のリンクを紹介するので参照して下さい。

https://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1%E5%8C%96%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

https://www.chessprogramming.org/Iterative_Deepening

本記事では、move ordering について[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#ai-%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%97%E3%81%9F%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E7%9D%80%E6%89%8B%E3%81%97%E3%81%9F%E5%AD%90%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E6%9C%80%E5%88%9D%E3%81%AB%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B)で説明した、__ルールベースの AI 計算した評価値を利用する__ という手法を利用することにします。その理由は、以下の通りです。

### 近似値を __αβ 法と比較して短い時間で計算できる__

__αβ 法__ ではミニマックス値を計算する際に枝狩りを効率よく行えた場合でも __数多くの子孫ノードの計算を行う必要__ がありますが、__本記事で作成したルールベースの AI__ では、__子ノードのみの評価値の計算__ を行なっているので αβ 法と比較して短い時間で計算できます。そのことは、下記のプログラムで __ゲーム開始時の局面の最善手の計算時間を比較__ することで確認することができます。興味がある方は他の局面でも比較してみて下さい。

まず、下記のプログラムで必要なインポートを行い、ゲーム開始時の局面のデータを計算します。比較対象としてインポートする AI は以下の 3 つです。

* これまでに紹介した αβ 法の中で __枝狩りの効率が高く計算時間が短い__、__置換表付き αβ 法__ で着手を選択する __`ai_abs_tt4`__
* __ルールベースの AI__ の中ですべての子ノードの評価値を 0 と計算する __最も処理が少ない__、ランダムな着手を選択する __`ai2s`__
* ルールベースの AI の中で __最も複雑__ で、__処理時間が長い__ と考えられる __`ai14s`__

上記の AI の関数のアルゴリズムの詳細については[こちらの記事](https://qiita.com/ysgeso/items/10d1d01192c014173e4b#%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E4%B8%80%E8%A6%A7)を参照して下さい。

```python
from marubatsu import Marubatsu
from ai import ai_abs_tt4, ai2s, ai14s

mb = Marubatsu()
```

次に、下記のプログラムで [%%timeit](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#index-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E6%AC%A0%E7%82%B9%E3%81%A8timeit-%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB%E3%81%AB%E3%82%88%E3%82%8B%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E8%A8%88%E6%B8%AC) を使って、それぞれの AI の計算時間を計算します。

```python
%%timeit
ai_abs_tt4(mb)
```

実行結果

```
310 ms ± 1.01 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

```python
%%timeit
ai2s(mb)
```

実行結果

```
345 µs ± 753 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
```

```python
%%timeit
ai14s(mb)
```

実行結果

```
519 µs ± 2.38 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
```

ms は 1000 分の 1 秒、__μs は ms の 1000 分の 1__ の 100 万分の 1 秒です。`ai2s` のほうが `ai14s` よりも処理時間が短いですが、__どちらのルールベースの AI も__ 置換表付き αβ 法の __約 1000 分の 1__ という __充分に短い時間__ で計算を行うことができること確認できました。


### ルールベースの AI が様々な精度を持つ

当然ですが、AI が計算する評価値の精度は高ければ高い程 AI が強くなります。__本記事で作成したルールベースの AI__ である `ai1s` ~ `ai14s` は、__[ランダムな着手を行う `ai2s` との対戦成績](https://qiita.com/ysgeso/items/10d1d01192c014173e4b#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA-ai-%E3%81%A7%E3%81%82%E3%82%8B-ai2-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6%E7%B5%90%E6%9E%9C)__ からわかるように __様々な精度を持ちます__。そのため、__異なる精度の AI__ によって __move ordering の効率がどのように変化するか__ を実際に比較して __確認することができます__。

なお、__これまでの記事で作成したルールベースの AI__ は __いずれも強解決の AI ではない__ ので、それらの AI が計算した __最善手の精度は 100 % ではありません__。例えば、弱解決の AI である `ai14s` は[以前の記事で検証](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#ai14s-%E3%81%8C%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E9%81%B8%E6%8A%9E%E3%81%97%E3%81%AA%E3%81%84%E5%B1%80%E9%9D%A2%E3%81%AE%E6%A4%9C%E8%A8%BC)したように強解決の AI ではないので、ほとんどの局面で最善手を計算しますが、[ほんの一部の局面では間違った最善手を計算](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E7%9D%80%E6%89%8B%E3%81%97%E3%81%AA%E3%81%84%E5%B1%80%E9%9D%A2%E3%81%AE%E8%A1%A8%E7%A4%BA)します。

## move ordering で行う子ノードの並べ替えの方法

max ノードと min ノードでは考え方は同じなので、本記事では以後は基本的に max ノードの場合のみの説明を行います。

[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E6%80%A7%E8%B3%AA) で説明したように __move ordering__ は、__max ノード__ では __最も評価値の高い子ノードが先頭__ に来るように子ノードを __並べ替える__ ことで __枝狩りの効率が最も高くなります__。

また、move ordering の精度が低いせいで __先頭の子ノードの評価値が最も高くならなかった場合__ は、同様の理由でその __次の子ノードの評価値が最も高い場合__ に枝狩りの効率が __最も高くなります__。

そのため、__子ノードの評価値を正しい大きさの順で計算できること__[^3]が __move ordering の精度の高さにつながります__。そこで、以後は AI が計算する __評価値の精度__ を __move ordering の精度と同じ意味で表記__ することにします。

[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29)では、ミニマックス法で計算されたゲーム木を使って本当の（最も評価値が高い）最善手の子ノードを先頭に移動する __[`move_bestmove_to_head`](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)__ や、AI の関数が計算した最善手の子ノードを先頭に移動する __[`move_ai_bestmove_to_head`](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-move_ai_bestmove_to_head-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ のように、__最善手として計算された子ノードのみを先頭に移動する__ という並べ替えを行いました。本記事ではこの方法で並べ替えを行う move ordering を __先頭のみの move ordering__ と表記することにします。

:::note
先程言及した反復深化を利用した move ordering ではノードの評価値を計算する際に、子ノードの中で最善手である可能性が非常に高いノードをあらかじめ計算しておくことができるため、先頭のみの move ordering が使われるようです。
:::

計算される子ノードの評価値の __精度が 100 % であれば先頭のみの move ordering で充分__ ですが、先程説明したように __通常__ は move ordering で計算する __子ノードの評価値の精度が 100 % になることはない__ ので、move ordering の結果、__最も評価値の高い子ノードが先頭にならない場合__ があります。その場合は __2 つ目の子ノードは並べ替えが行われていない__ ため、__評価値が最も高くなるとは限らない__ という問題が発生します。

この問題は、先頭の子ノードだけでなく、__すべての子ノードを対象__ にして、計算された評価値の順に __並べかえる__ ことで改善することができます。その場合は、最も評価値が高い子ノードが先頭にならない場合でも、__次の子ノードの評価値が最も高くなる可能性が高くなる__ からです。以後はこの方法で並べ替えを行う move ordering を __全ノードの move ordering__ と表記することにします。

__全ノードの move ordering__ では、__すべての子ノードの評価値を計算する必要がある__ 点と、__すべての子ノードを対象に並べ替えを行う必要がある__ という点で先頭のみの move ordering よりも __処理に時間がかるという欠点があります__。ただし、本記事でこれから実装する、__ルールベースの AI を利用して move ordering 最善手を計算する場合__ は、__その過程ですべての子ノードの評価値を必ず計算する__ ので、前者の欠点は問題にはなりません。後者の問題は並べ替える子ノードの数が少ない場合は全体の処理時間と比較すると __無視できるほど短く計算できる__ ので大きな問題ではありません。

本記事では先頭のみの move ordering と 全ノードの move ordering の __両方を実装する__ ことで、__枝狩りの効率の差を比較する__ ことにします。


:::note
反復深化を利用した move ordering であらかじめ計算しておくことができるのは、最善手である可能性が高い子ノードだけです。また、高い精度で最善手を計算することができるので、全ノードの move ordering は利用されないようです。
:::

# move ordering を行う AI の関数の定義

これまでは、__αβ 法で着手を選択する AI を定義する際__ に、最短の勝利を目指すかどうか、置換表の利用の有無などの設定ごとに __別々の AI の関数を作ってきました__ が、それらの設定ごとに move ordering を行う AI を別々に定義するのは大変なので、__以下の設定を仮引数で行うことができる AI の関数を定義__ する事にします。

* 最短の勝利を目指すかどうか
* ルートノードの評価値を計算する際の α 値と β 値の初期値を設定するかどうか
* 置換表を利用するかどうか
* move ordering を行うかどうか
* move ordering を行う場合は、全ノードの move ordering を行うかどうか

また、これまでの AI の関数では、キーワード引数 __`debug=True`__ を記述することで __評価値を計算したノードの数を表示する__ という機能を持っていましたが、__表示された数値をその後のプログラムで利用することはできませんでした__。そこで、__評価値を計算したノードの数を返り値として返す機能を持つ__ ように実装することにします。

下記は、__定義する AI の関数の仕様__ です。なお、下記の関数は、@ai_by_score のデコレータ式を先頭に記述することで AI の関数として着手を選択するようになります。

__名前__：αβ 法で評価値を計算する AI で、これまでに説明したすべて（all）の機能を持つので __`ai_abs_all`__ とする
__処理__：指定した設定で αβ 法で局面の評価値を計算する。また、評価値を計算したノードの数を返す機能を持つ
__入力__：下記の表の仮引数を持つ
__出力__：`calc_count` が `False` の場合は評価値を、`False` の場合は評価値を計算したノードの数を返す

|仮引数|デフォルト値|意味|
|:--|:--|:--|
| __`mb`__ | なし | 評価値を計算する局面 |
| __`debug`__ | `False` | `True` の場合にデバッグの表示を行う |
| __`shortest_victory`__ | `False` | `True` の場合に最短の勝利を目指す評価値を計算する |
| __`init_ab`__ | `False` | `True` の場合にルートノードの α 値と β 値の初期値を評価値の最小値と最大値に設定する |
| __`use_tt`__| `False` | `True` の場合に置換表を利用する |
| __`ai_for_mo`__ | `None` | move ordering を行うための AI の関数。`None` の場合は move ordering を行わない |
| __`params`__ | `{}` | `ai_for_mo` を呼び出す際に記述する実引数の dict |
| __`sort_allnodes`__ | `False` | `True` の場合に全ノードの move ordering を行う |
| __`calc_count`__ | `False` | `True` の場合に返り値として評価値を計算したノードの数を返す |

##  `ai_abs_all` の定義

__先頭の子ノードを最善手の子ノードに並べ替える__ という処理は[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-move_ai_bestmove_to_head-%E3%81%AE%E5%AE%9A%E7%BE%A9)で __`move_ai_bestmove_to_head`__ で実装したので、それを参考に実装することができます。__子ノード全体を並べ替える処理__ については説明が必要なので __後で実装することにします__。

__`ai_abs_all`__ は 置換表付き αβ 法で評価値を計算する `ai_abs_tt4` を修正して、以下のように定義することができます。

* __5 ~ 7 行目__：関数の名前を `ai_abs_all` に修正し、上記の表の仮引数を追加する
* __10 ~ 25、36 ~ 48 行目__：置換表に関する処理を `if use_tt:` のブロックの中に記述するようにする
* __31 ~ 34 行目__：`ai_for_mo` が `None` でない場合に、32 行目で `ai_for_mo` が計算した最善手の子ノードを、33、34 行目で先頭の子ノードと入れ替える処理を行う。この部分の処理は[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#ai-%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%97%E3%81%9F%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E7%9D%80%E6%89%8B%E3%81%97%E3%81%9F%E5%AD%90%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E6%9C%80%E5%88%9D%E3%81%AB%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B)で定義した `move_ai_bestmove_to_head` メソッドの処理とほぼ同じである
* __53 ~ 56 行目__：ルートノードの評価値を計算する際の α 値と β 値の初期値を計算し、それを使ってルートノードの評価値を計算するように修正する
* __58、59 行目__：`calc_count` が `True` の場合に評価値を計算したノードの数を返り値として返すようにする

```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 use_tt:
11              boardtxt = mborig.board_to_str()
12              if boardtxt in tt:
13                  lower_bound, upper_bound = tt[boardtxt]
14                  if lower_bound == upper_bound:
15                      return lower_bound
16                  elif upper_bound <= alpha:
17                      return upper_bound
18                  elif beta <= lower_bound:
19                      return lower_bound
20                  else:
21                      alpha = max(alpha, lower_bound)
22                      beta = min(beta, upper_bound)
23              else:
24                  lower_bound = min_score
25                  upper_bound = max_score
26          
27          alphaorig = alpha
28          betaorig = beta
29  
30          legal_moves = mborig.calc_legal_moves()
31          if ai_for_mo is not None:
32              bestmove = ai_for_mo(mborig, **params)
33              index = legal_moves.index(bestmove)
34              legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]            
35          if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
36          if use_tt:
37              from util import calc_same_boardtexts
38      
39              boardtxtlist = calc_same_boardtexts(mborig)
40              if score <= alphaorig:
41                  upper_bound = score
42              elif score < betaorig:
43                  lower_bound = score
44                  upper_bound = score
45              else:
46                  lower_bound = score
47              for boardtxt in boardtxtlist:
48                  tt[boardtxt] = (lower_bound, upper_bound)
49          return score
50                  
51      min_score = -2 if shortest_victory else -1
52      max_score = 3 if shortest_victory else 1
53      alpha = min_score if init_ab else float("-inf")
54      beta = max_score if init_ab else float("inf")
55  
56      score = ab_search(mb, {}, alpha=alpha, beta=beta)
57      dprint(debug, "count =", count)
58      if calc_count:
59          return count
60      if mb.turn == Marubatsu.CIRCLE:
61          score *= -1
62      return score
```

<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:
            bestmove = ai_for_mo(mborig, **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)   
            
        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 copy import deepcopy

@ai_by_score
-def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
+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")):
元と同じなので省略
-       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
+       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:
+           bestmove = ai_for_mo(mborig, **params)
+           index = legal_moves.index(bestmove)
+           legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]            
        if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
-       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)
+       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=min_score, beta=max_score)
+   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>

上記の定義後に、下記のプログラムを実行することで、まだ実装していない __`sort_allnodes` 以外のすべての設定の組み合わせ__ で __`ai_abs_all`__ が __強解決の AI であることを確認__ することができます。__move ordering で利用する AI__ としては __`ai2s`__ と __`ai14s`__ を採用しました。

なお、実行結果は長いので途中から省略していますが、すべての場合で強解決であることを表す 100 % が表示されます。

* __3 ~ 6 行目__：for 文を入れ子にすることで、すべての組み合わせに対して 7 ~ 14 行目のブロックを実行する
* __7 行目__：設定を表示する
* __8 ~ 13 行目__：`ai_abs_all` を呼び出す際のパラメータを `params` に代入する
* __14 行目__：`Check_solved.is_strongly_solved` 呼び出して、`params` の実引数を記述して呼び出した `ai_abs_all` が強解決の AI であるかどうかを確認する

```python
 1  from util import Check_solved
 2  
 3  for ai_for_mo in [None, ai2s, ai14s]:
 4      for shortest_victory in [False, True]:
 5          for use_tt in [False, True]:
 6              for init_ab in [False, True]:
 7                  print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab}")
 8                  params = {
 9                      "ai_for_mo": ai_for_mo,
10                      "shortest_victory": shortest_victory,
11                      "init_ab": init_ab,
12                      "use_tt": use_tt,
13                  }
14                  Check_solved.is_strongly_solved(ai_abs_all, params=params)
```

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

```python
from util import Check_solved

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]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab}")
                params = {
                    "ai_for_mo": ai_for_mo,
                    "shortest_victory": shortest_victory,
                    "init_ab": init_ab,
                    "use_tt": use_tt,
                }
                Check_solved.is_strongly_solved(ai_abs_all, params=params)
```
</details>

実行結果

```
ai_for_mo: None, sv: False, use_tt: False, init_ab: False
  0%|          | 0/431 [00:00<?, ?it/s]
100%|██████████| 431/431 [00:03<00:00, 108.73it/s]
431/431 100.00%
ai_for_mo: None, sv: False, use_tt: False, init_ab: True
100%|██████████| 431/431 [00:03<00:00, 140.83it/s]
431/431 100.00%
略
ai_for_mo: <function ai14s at 0x00000216EC395260>, sv: True, use_tt: True, init_ab: True
100%|██████████| 431/431 [00:04<00:00, 86.67it/s] 
431/431 100.00%
```

### 枝狩りの効率の確認

次に、下記のプログラムを実行して、__ゲーム開始時の局面__ の評価値を上記と同様の設定の組み合わせで計算した際に __評価値が計算されるノードの数を計算__ します。なお、__評価値が計算されたノードの数を返り値とするため__ には、指定したノードの評価値を計算することを表す __`calc_score=True`__ と、評価値ではなく計算されたノードの数を返すようにすることを表す __`calc_count=True`__ の __両方を記述する必要がある__ 点に注意して下さい。

:::note
__`calc_count=True` だけを記述__ した場合は、`@ai_by_score` の中で定義されたラッパー関数 `wrapper` 内で、評価値ではなく __計算されたノードの数を使って着手を選択する__ という、__意図しない処理__ が行われます。
:::

ただし、__move ordering で利用する AI__ は、下記の理由から下記の 4 つを選択しました。

* __[`ai1s`](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#ai1s-%E3%81%AE%E5%AE%9A%E7%BE%A9-%E3%81%9D%E3%81%AE-3%E5%BC%8F%E3%81%A7%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E6%96%B9%E6%B3%95)__：前にある子ノードのほうが高い評価値が計算されるので、__実質的に move ordering が行なわれない__ 
* __[`ai2s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E9%96%A2%E6%95%B0%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E3%83%AB%E3%83%BC%E3%83%AB-2-%E3%81%A7%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9)__：すべてのノードで 0 を計算するので、__でたらめな move ordering__ が行なわれる
* __[`ai10s`](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#ai10s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__：__`ai10s` は弱解決の AI ではない__ ので __`ai14s` より低い精度__ の move ordering が行なわれる
* __[`ai14s`](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#ai14s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__：完璧ではないが、__弱解決__ で __ほぼ完ぺきな精度__ で move ordering が行われる

なお、[`ai10s VS ai2s` の対戦成績](https://qiita.com/ysgeso/items/10d1d01192c014173e4b#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA-ai-%E3%81%A7%E3%81%82%E3%82%8B-ai2-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6%E7%B5%90%E6%9E%9C)は 91.5 %、`ai14s VS ai2s` の対戦成績は 93.9 % なので __`ai10s` はかなり強い AI__ であり、__その精度は高い__ と考えられます

```python
from ai import ai10s

for ai_for_mo in [None, ai2s, ai10s, ai14s]:
    for shortest_victory in [False, True]:
        for init_ab in [False, True]:
            for use_tt in [False, True]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
                print("count=", ai_abs_all(mb, ai_for_mo=ai_for_mo,
                                          shortest_victory=shortest_victory,
                                          init_ab=init_ab, use_tt=use_tt,
                                          calc_score=True, calc_count=True))
```

実行結果

```
ai_for_mo: None, sv: False, init_ab: False, use_tt: False
count= 18297
ai_for_mo: None, sv: False, init_ab: True, use_tt: False
count= 16811
ai_for_mo: None, sv: False, init_ab: False, use_tt: True
count= 1054
略
```

実行結果を表にまとめると以下のようになります。一番上の行の ab は `init_ab`、tt は `use_tt` の値で 〇 は `True`、× は `False` を表します。リンクになっている数値は、過去の記事でその値を計算した記事へのリンクで、そのことからそれらの値が正しく計算されていることが確認できます。なお、__`ai1s` 以外__ の AI は、__同じ評価値__ が計算される __合法手が複数ある場合__ はその中から __ランダムに最善手を選択する__ ので、上記のプログラムを実行する度に __実行結果が若干変化する可能性__ があります。


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

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __mo なし__ | [18297](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9#%E7%A5%96%E5%85%88%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F-%CE%B1-%E7%8B%A9%E3%82%8A%E3%81%A8%CE%B2-%E7%8B%A9%E3%82%8A%E3%81%AE%E5%AE%9F%E8%A3%85) | [16811](https://qiita.com/ysgeso/items/b90305993d682ff16793#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-calc_score_by_ab-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3) | 1054 | [832](https://qiita.com/ysgeso/items/20317d7b67518a119382#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E6%9C%80%E5%B0%8F%E5%80%A4%E3%81%AE%E6%9C%80%E5%A4%A7%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E6%94%B9%E8%89%AF) |
| __`ai1s`__ | 18297 | 16811 | 1054 | 832 |
| __`ai2s`__ | 14810 | 11274 | 884 | 734 |
| __`ai10s`__ | 2267 | 1980 | 274 | 270 | 
| __`ai14s`__ | 1496 | 1496 | 234 | 239 |

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

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __mo なし__ | [20866](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E7%9B%AE%E7%9A%84%E3%81%AE%E3%81%8A%E3%81%95%E3%82%89%E3%81%84%E3%81%A8%E3%80%87%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%A7%E3%81%AE%E5%8A%B9%E7%8E%87) | 20484 | 1275 | [1242](https://qiita.com/ysgeso/items/094fc04eb693b208fa02#%E4%BF%AE%E6%AD%A3%E3%81%97%E3%81%9F%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%81%AE%E7%A2%BA%E8%AA%8D) |
| __`ai1s`__ | 20866 | 20484 | 1275 | 1242 |
| __`ai2s`__ | 17919 | 17262| 1642 | 1246 |
| __`ai10s`__ | 2189 | 2232 | 261 | 277 | 
| __`ai14s`__ | 1496 | 1496 | 234 | 234 |

move ordering の有無や AI の種類に関係なく __α 値と β 値の初期値を設定__ したほうが __多くの場合で高い枝狩りの効率__ を持つことが確認できます。また、__置換表を利用__ したほうが __枝狩りの効率がかなり高くなる__ ことが確認できます。これらの結果は、__これまでの記事で説明した通り__ なので、__`ai_abs_all`__ が __この 2 つの設定を正しく計算する__ ことが確認できました。

__`ai1s`__ は前にある子ノードのほうが高い評価値が計算されるので、__実質的に move ordering が行なわれません__。従って、上記の表では __mo なしと `ai_1s` の結果が同じ__ になります。

上記の実行結果では __`ai1s`__ より __`ai2s`__ のほうが枝狩りの効率が __高くなる場合と低くなる場合__ がありますが、これは __`ai2s`__ が __でたらめな move ordering__ を行うので __運が良ければ枝狩りの効率が高く__ なり、__運が悪ければ枝狩りの効率が悪く__ なるからです。

__高い精度__ で評価値を計算する __`ai10s`__ と、弱解決で __さらに高い精度__ で評価値を計算する __`ai14s`__ は `ai1s` よりかなり __枝狩りの効率が良く__、__精度が高い `ai14s` のほうが `ai10s` よりも枝狩りの効率が高い__ ことが確認できます。

上記から、__move ordering の精度__ は確かに __枝狩りの効率に大きな影響を与える__ ことがわかります。このことは[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#%E6%A7%98%E3%80%85%E3%81%AA-ai-%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-%CE%B1%CE%B2-%E6%B3%95%E3%81%AE%E8%A8%88%E7%AE%97)で α 値と β 値の初期設定を行わず、置換表を利用しない場合で確認済ですが、上記ではそれらの設定を行った場合についての確認を行いました。

## 全ノードの move ordering の実装

先頭のみの move ordering の実装が正しく行われたことが確認できたので、次は __全ノードの move ordering__ を実装します。

__AI が計算する子ノードの評価値__ は、下記のプログラムのように、AI の関数の実引数に __[`analyze=True`](https://qiita.com/ysgeso/items/2c76474ff139a824f4fd#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E8%A1%A8%E7%A4%BA%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AB%E5%BF%85%E8%A6%81%E3%81%AA%E5%87%A6%E7%90%86%E3%81%AE%E5%AE%9F%E8%A3%85)__ を記述して呼び出すことで計算することができます。なお、実行結果を見やすくするために `pprint` を使って表示を行っています。

```python
from pprint import pprint

result = ai14s(mb, analyze=True)
pprint(result)
```

実行結果

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

実行結果の中で、__それぞれの合法手を着手した際の評価値__ は、__`score_by_move`__ というキーの値の代入されているので、下記のプログラムでそれを表示すると、その内容は __合法手をキー__ とし、__キーの値に__ その合法手を着手した際の局面の __評価値が代入__ された __dict__ であることがわかります。

```python
score_by_move = result["score_by_move"]
pprint(score_by_move)
```

実行結果

```
{(0, 0): 1.5,
 (0, 1): 1.0,
 (0, 2): 1.5,
 (1, 0): 1.0,
 (1, 1): 2.0,
 (1, 2): 1.0,
 (2, 0): 1.5,
 (2, 1): 1.0,
 (2, 2): 1.5}
```

従って、上記の __dict のキー__ を、__キーの値の順で並べ替える__ ことで、AI が計算した評価値の順で合法手の一覧を並べ替えることができます。

[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#list-%E3%81%AE-sort-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%A8%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-sorted-%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9)では、__list の `sort` メソッド__ や組み込み関数 __`sorted`__ を利用して __list の要素を特定の基準で並べ替える__ 方法を紹介しましたが、残念ながら __dict は `sort` メソッドを持たない__ ので、__`sort`__ メソッドでは __dict の要素を並べ替えることはできません__。

また、__dict__ に対して下記のプログラムのように __`sorted`__ を使って並べ替えを行うと dict のキーの値ではなく、__dict のキーのみが並べ替えられる__ ためうまくいきません。なお、[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#list-%E3%81%AE-sort-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%A8%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-sorted-%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9)で説明したように、__`sorted` の返り値は list__ になるので、下記の実行結果は dict ではなく list になる点にも注意が必要です。

```python
pprint(sorted(score_by_move))
```

実行結果

```
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
```

### dict の要素の並べ替え

__dict の要素__ は下記の手順で並べ替えることができます。

1. __dict__ を、以下のような要素を持つ __list に変換__ する
    * dict の __キー__ と __キーの値__ を要素として持つ __tuple__
2. __`sort`__ メソッドまたは組み込み関数 __`sorted`__ を利用してその list を、__tuple の キーの値を表す要素の順__ で __並べ替える__
3. 並べ替えた list を __dict に変換する__

__dict__ から __キー__ と __キーの値__ を要素として持つ __tuple__ を __順番に取り出す__ という処理は、dict の __[`items`](https://qiita.com/ysgeso/items/44884dcf168aab949508#for-%E6%96%87%E3%81%A7-dict-%E3%81%AE%E3%82%AD%E3%83%BC%E3%81%A8%E5%80%A4%E3%81%AE%E4%B8%A1%E6%96%B9%E3%82%92%E5%8F%96%E3%82%8A%E5%87%BA%E3%81%99%E7%B9%B0%E3%82%8A%E8%BF%94%E3%81%97)__ メソッドを利用して下記のプログラムのように記述することができます。

```python
for item in score_by_move.items():
    print(item)
```

実行結果

```
((0, 0), 1.5)
((1, 0), 1.0)
((2, 0), 1.5)
((0, 1), 1.0)
((1, 1), 2.0)
((2, 1), 1.0)
((0, 2), 1.5)
((1, 2), 1.0)
((2, 2), 1.5)
```

このことから、dict の __`items` メソッド__ が dict を上記の __手順 1 のような list に変換する処理__ だと __勘違いされがち__ ですが、__`items`__ メソッドの __返り値__ は for 文で利用できるという意味では list と似ていますが、__list とは異なるデータです__。実際に、下記のプログラムのように `items` メソッドの返り値を __list だと考えて 0 番の要素を取り出して__ 表示しようとすると __エラーが発生__ します。

```python
items = score_by_move.items()
items[0]
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[12], line 2
      1 items = score_by_move.items()
----> 2 items[0]

TypeError: 'dict_items' object is not subscriptable
```

上記のエラーメッセージは dict の `items` メソッドの返り値が list ではないので list のように [] を使って要素を取り出すことができないという意味を表します。なお、subscript は、$ x_1 $ の 1 のような、数学の変数の右下に小さく表示する __下付き文字__ のことで、__同じ名前__ の変数で __複数の数値を区別して扱う__ 際に使用します。python では、list や dict の右に記述する __`[]`__ によって要素を参照する仕組みのことを指します。

dict の __`items` メソッドの返り値__ は、下記のプログラムの実行結果のように組み込み関数 __`list` の実引数に記述して呼び出す__ ことで、__list に変換__ することができます。

```python
score_by_move_list = list(items)
pprint(score_by_move_list)
```

実行結果

```
[((0, 0), 1.5),
 ((1, 0), 1.0),
 ((2, 0), 1.5),
 ((0, 1), 1.0),
 ((1, 1), 2.0),
 ((2, 1), 1.0),
 ((0, 2), 1.5),
 ((1, 2), 1.0),
 ((2, 2), 1.5)]
```

### list の `sort` メソッドを利用した並べ替え

__dict を list に変換__ したので、[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#list-%E3%81%AE-sort-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%A8%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-sorted-%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9)で紹介した list の __`sort`__ メソッドや組み込み関数 __`sorted`__ を利用してキーの値の順で list の要素を並べ替えることができます。下記は `sort` メソッドの場合のプログラムで、実行結果のように __キーの値の小さい順で並べ替え__ られます。

下記のプログラムでは[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#%E3%83%A9%E3%83%A0%E3%83%80%E5%BC%8Flambda-expression%E3%81%AB%E3%82%88%E3%82%8B%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)で説明した __ラムダ式__ を使って list の要素に代入された tuple の中で、評価値が代入されている __1 番の要素を使って並べ替え__ を行っています。ラムダ式の __`lambda x:x[1]`__ の中の __`x` が list の要素__ を、__`x[1]` が並べ替えの基準として利用する値__ を表します。

```python
score_by_move_list.sort(key=lambda x:x[1])
pprint(score_by_move_list)
```

実行結果

```
[((1, 0), 1.0),
 ((0, 1), 1.0),
 ((2, 1), 1.0),
 ((1, 2), 1.0),
 ((0, 0), 1.5),
 ((2, 0), 1.5),
 ((0, 2), 1.5),
 ((2, 2), 1.5),
 ((1, 1), 2.0)]
 ```

### 組み込み関数 `sorted` を利用した並べ替え

組み込み関数 __`sorted`__ を利用する場合は、下記のプログラムのように記述します。

```python
score_by_move_list = sorted(items, key=lambda x:x[1])
pprint(score_by_move_list)
```

実行結果

```
[((1, 0), 1.0),
 ((0, 1), 1.0),
 ((2, 1), 1.0),
 ((1, 2), 1.0),
 ((0, 0), 1.5),
 ((2, 0), 1.5),
 ((0, 2), 1.5),
 ((2, 2), 1.5),
 ((1, 1), 2.0)]
```

また、組み込み関数 __`sorted`__ は list だけでなく、__[反復可能オブジェクト](https://qiita.com/ysgeso/items/0d64d1ddba1982b5a5d3#%E5%8F%8D%E5%BE%A9%E5%8F%AF%E8%83%BD%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88)__ の並べ替えを行うことができます。dict の __`items`__ メソッドの __返り値は反復可能オブジェクト__ なので、下記のプログラムのように list に変換せずに __直接 dict の `items` メソッドの返り値を使って並べ替え__ を行うことができます。また、__`sorted` の返り値__ は、並べ替えるデータの種類に関わらず __list になる__  ので、下記のプログラム尾ように組み込み関数 __`list` を利用しなくても良いという利点__ があります。上記の性質から、__dict の要素の並べ替えを行う場合__ は、__`sorted`__ を利用したほうがプログラムが __少し簡潔__ になります。

```python
score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1])
pprint(ordered_score_by_move_list)
```

実行結果

```
[((1, 0), 1.0),
 ((0, 1), 1.0),
 ((2, 1), 1.0),
 ((1, 2), 1.0),
 ((0, 0), 1.5),
 ((2, 0), 1.5),
 ((0, 2), 1.5),
 ((2, 2), 1.5),
 ((1, 1), 2.0)]
```

### キーの順番での並べ替えと、大きい順の並べ替え

本記事では利用しませんが、dict のキーの値ではなく、__キーの順番で並べ替えを行う場合__ は下記のプログラムのようにラムダ式の中で __並べ替えの基準を表す部分__ に __dict のキーを表す `x[0]` を記述__ します。

```python
score_by_move_list.sort(key=lambda x:x[0])
pprint(score_by_move_list)
```

実行結果

```
[((0, 0), 1.5),
 ((0, 1), 1.0),
 ((0, 2), 1.5),
 ((1, 0), 1.0),
 ((1, 1), 2.0),
 ((1, 2), 1.0),
 ((2, 0), 1.5),
 ((2, 1), 1.0),
 ((2, 2), 1.5)]
```

組み込み関数 __`sorted`__ でも同様のラムダ式を記述することで並べ替えを行うことができますが、下記のプログラムのように __実引数に dict の `items` メソッドの返り値を直接記述したほうが簡単__ です。なお、`score_by_move` のキーは小さい順で並んでいるので、下記のプログラムでは __キーワード引数 `reverse=True`__ を記述して逆順に並べ替えました。

```python
pprint(sorted(score_by_move.items(), reverse=True))
```

実行結果

```
[((2, 2), 1.5),
 ((2, 1), 1.0),
 ((2, 0), 1.5),
 ((1, 2), 1.0),
 ((1, 1), 2.0),
 ((1, 0), 1.0),
 ((0, 2), 1.5),
 ((0, 1), 1.0),
 ((0, 0), 1.5)]
 ```

キーの値の __大きい順で並べ替えたい場合__ は、下記のプログラムのように __キーワード引数 `reverse=True` を記述__ します。

```python
score_by_move_list.sort(key=lambda x:x[1], reverse=True)
pprint(score_by_move_list)
```

実行結果

```
[((1, 1), 2.0),
 ((0, 0), 1.5),
 ((0, 2), 1.5),
 ((2, 0), 1.5),
 ((2, 2), 1.5),
 ((0, 1), 1.0),
 ((1, 0), 1.0),
 ((1, 2), 1.0),
 ((2, 1), 1.0)]
```

こうして並べ替えが行われた __list を dict に戻す方法__ は簡単で、下記のプログラムのように __組み込み関数 `dict` の実引数に記述して呼び出す__ という処理を記述するだけです。変数名の ordered は、並べ替えられという意味の英語です。なお、`pprint` はキーワード引数 `sort_dicts=False` を記述しないと __キーの内容の順で並べ替えられて表示されてしまう__ ため記述しました。

```python
ordered_score_by_move = dict(score_by_move_list)
pprint(ordered_score_by_move, sort_dicts=False)
```

実行結果

```
{(1, 1): 2.0,
 (0, 0): 1.5,
 (0, 2): 1.5,
 (2, 0): 1.5,
 (2, 2): 1.5,
 (0, 1): 1.0,
 (1, 0): 1.0,
 (1, 2): 1.0,
 (2, 1): 1.0}
```

:::note
下記は `sort_dicts=False` を記述しなかった場合で、キーの順で並べ替えて表示されています。

```python
pprint(ordered_score_by_move)
```

実行結果

```
{(0, 0): 1.5,
 (0, 1): 1.0,
 (0, 2): 1.5,
 (1, 0): 1.0,
 (1, 1): 2.0,
 (1, 2): 1.0,
 (2, 0): 1.5,
 (2, 1): 1.0,
 (2, 2): 1.5}
```
:::

### キーの値による dict のキーの並べ替え

上記では __dict の要素をキーの値の順で並べ替え__ ましたが、__move ordering で必要となる__ のはそのような dict ではなく、__並べ替えられた合法手のみを要素として持つ list__ です。従って、上記の __手順 3 を実行して list を dict に戻す必要はありません__。

その代わりに、__手順 2 で並べ替えられた list__ から __合法手のみを要素として持つ list__ を下記のプログラムで list 内包表記を使って __作成する処理__ を行います。

```python
ordered_move_list = [x[0] for x in score_by_move_list]
print(ordered_move_list)
```

実行結果

```
[(1, 1), (0, 0), (0, 2), (2, 0), (2, 2), (0, 1), (1, 0), (1, 2), (2, 1)]
```

:::note
dict に変換した後で、下記のプログラムで list に変換するという方法もあります。

```python
ordered_move_list = list(ordered_score_by_move.keys())
print(ordered_move_list)
```

実行結果

```python
[(1, 1), (0, 0), (0, 2), (2, 0), (2, 2), (0, 1), (1, 0), (1, 2), (2, 1)]
```
:::

### 処理のまとめ

下記は上記で説明した処理をまとめたプログラムです。なお、__評価値は高い順に並べる必要がある__ ので、`sort` メソッドのキーワード引数に __`reverse=True` を記述__ しました。

```python
result = ai14s(mb, analyze=True)
score_by_move = result["score_by_move"]
items = score_by_move.items()
score_by_move_list = list(items)
score_by_move_list.sort(key=lambda x:x[1], reverse=True)
orderd_move_list = [x[0] for x in score_by_move_list]
print(orderd_move_list)
```

実行結果

```
[(1, 1), (0, 0), (2, 0), (0, 2), (2, 2), (1, 0), (0, 1), (2, 1), (1, 2)]
```

上記のプログラムはかなり冗長なので、下記のプログラムのように、__いくつかの処理をまとめる__ ことにします。

* __1 行目__：上記の 1、2 行目の処理を 1 行でまとめた
* __2 行目__：先程説明した、組み込み関数 `sorted` を利用した並べ替えに修正した

```python
1  score_by_move = ai14s(mb, analyze=True)["score_by_move"]
2  score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
3  orderd_move_list = [x[0] for x in score_by_move_list]
4  print(orderd_move_list)
```

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

```python
score_by_move = ai14s(mb, analyze=True)["score_by_move"]
score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
orderd_move_list = [x[0] for x in score_by_move_list]
print(orderd_move_list)
```
</details>

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

```diff_python
-result = ai14s(mb, analyze=True)
-score_by_move = result["score_by_move"]
+score_by_move = ai14s(mb, analyze=True)["score_by_move"]
-items = score_by_move.items()
-score_by_move_list = list(items)
-score_by_move_list.sort(key=lambda x:x[1], reverse=True)
+score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
orderd_move_list = [x[0] for x in score_by_move_list]
print(orderd_move_list)
```
</details>

実行結果

```
[(1, 1), (0, 0), (2, 0), (0, 2), (2, 2), (1, 0), (0, 1), (2, 1), (1, 2)]
```

:::note
下記のプログラムのように、無理やり 1 行のプログラムにまとめることもできますが、プログラムがわかりづらくなるので本記事では採用しません。

```python
orderd_move_list = [x[0] for x in sorted(ai14s(mb, analyze=True)["score_by_move"].items(), key=lambda x:x[1], reverse=True)]
print(orderd_move_list)
```

実行結果

```
[(1, 1), (0, 0), (2, 0), (0, 2), (2, 2), (1, 0), (0, 1), (2, 1), (1, 2)]
```
:::

### `ai_abs_all` の修正

AI が計算した評価値の順で子ノードの評価値を並べ替える方法がわかったので、__`ai_abs_all`__ を下記のプログラムのように修正します。

* __9 ~ 12 行目__:`sort_allnodes` が `True` の場合は上記で説明した方法で評価値の高い順で合法手を並べ替えた list を計算し、`legal_moves` という変数に代入する。なお、__`@ai_by_score` のデコレータ式でデコレートする関数__ は、max ノードでも min ノードでも __常に高いほうが有利であるという意味の評価値を計算する__ ので、__常に評価値の高い順__ に並べ替えれば良い
* __13 ~ 17 行目__：`sort_allnodes` が `False` の場合は修正前と同じ処理を行う

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

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

```python
@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, **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
@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")):
元と同じなので省略
        legal_moves = mborig.calc_legal_moves()
        if ai_for_mo is not None:
-           legal_moves = mborig.calc_legal_moves()
-           bestmove = ai_for_mo(mborig, **params)
-           index = legal_moves.index(bestmove)
-           legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
+           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)
+               index = legal_moves.index(bestmove)
+               legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
```
</details>

### 枝狩りの効率の比較による検証

上記の修正後に、下記のプログラムを実行すると、__全ノードの move ordering を行う場合__ でも __`ai_abs_all` が強解決の AI である__ ことを確認することができます。先程のプログラムとの違いはパラメータの dict に `sort_allnodes: True` を追加した点です。

```python
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]:
                print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, use_tt: {use_tt}, init_ab: {init_ab}")
                params = {
                    "ai_for_mo": ai_for_mo,
                    "shortest_victory": shortest_victory,
                    "init_ab": init_ab,
                    "use_tt": use_tt,
                    "sort_allnodes": True,
                }
                Check_solved.is_strongly_solved(ai_abs_all, params=params)
```

実行結果

```
ai_for_mo: None, sv: False, use_tt: False, init_ab: False
100%|██████████| 431/431 [00:03<00:00, 110.35it/s]
431/431 100.00%
ai_for_mo: None, sv: False, use_tt: False, init_ab: True
100%|██████████| 431/431 [00:03<00:00, 137.48it/s]
431/431 100.00%
略
```

次に、下記のプログラムで __ゲーム開始時の局面__ の評価値を計算した際に __評価値が計算されるノードの数__ を、__全ノードの move ordering を行う場合__ で先程と同様の様々な設定で計算します。なお、__move ordering を行わない場合__ は結果は変わらないので __省略__ しました。また、実質的に　move ordering を行わない __`ai1s`__ とでたらめな move ordering を行う __`ai2s`__ を比較する意味はないので、それらの計算も __省略__ しました。

```python
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}")
                print("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=True, calc_score=True, calc_count=True))
```

実行結果

```
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: False, use_tt: False
count= 2305
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: True, use_tt: False
count= 2082
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: False, use_tt: True
count= 285
略
```

下記は上記の結果と、先程の move ordering の __結果をまとめた__ ものです。下記の表の __上段が先頭のみの move ordering__、__下段が全ノードの move ordering__ を行う場合の結果です。

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

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __`ai10s`__ | 2267<br>2305 | 1980<br>2082 | 274<br>285 | 270<br>260 | 
| __`ai14s`__ | 1496<br>1496 | 1496<br>1496 | 234<br>239 | 239<br>239 |

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

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __`ai10s`__ | 2189<br>2305 | 2232<br>2305 | 261<br>285 | 277<br>285 | 
| __`ai14s`__ | 1496<br>1496 | 1496<br>1496 | 234<br>239 | 234<br>239 |





実行結果から、いずれれの場合も __結果がほとんど変わらない__ か、一部の結果では全ノードの move ordering を行う場合のほうが効率が悪いことが確認できました。この結果はおかしいと思えるかもしれませんが理由があります。その理由について少し考えてみて下さい。

### すべての局面での合計での比較

move ordering による枝狩りの効率は、__すべてのノードで同じであるとは限りません__。そのため、ゲーム開始時の局面では __たまたま効率が変わらなかった可能性__ があります。そこで、〇× ゲームの __すべてのノード__ 対して評価値の計算を行ない、評価値が計算されたノードの数の __合計を比較__ することにします。ただし、その際に Check_Solved が強解決の AI であるかの判定を行う際と同様に、__同一局面は重複して計算しない__ ことにします。

下記はそのような計算を行うためのプログラムです。

* __3 行目__：同一局面を除いた 〇× ゲームの全ての局面を表す list をファイルから読み込む。この処理は [Check_solved で行なっている処理](https://qiita.com/ysgeso/items/7cb0c709f6d5884d925e#%E5%90%8C%E4%B8%80%E5%B1%80%E9%9D%A2%E3%82%92%E8%80%83%E6%85%AE%E3%81%97%E3%81%9F%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AB%E3%82%88%E3%82%8B%E5%BC%B7%E8%A7%A3%E6%B1%BA%E3%81%AE-ai-%E3%81%A7%E3%81%82%E3%82%8B%E3%81%8B%E3%81%A9%E3%81%86%E3%81%8B%E3%81%AE%E5%88%A4%E5%AE%9A)と同じである
* __9、10 行目__：それぞれの move ordering での合計を計算する変数を 0 で初期化する
* __11 ~ 19 行目__：すべての局面に対してそれぞれの move ordering で `ai_abs_all` を呼び出し、`count` と `count2` に計算したノードの数を加算する
* __20 行目__：それぞれの move ordering での合計を表示する

```python
 1  from util import load_mblist
 2  
 3  mblist = load_mblist("../data/mblist_by_board_min.dat")
 4  for ai_for_mo in [ai10s, ai14s]:
 5      for shortest_victory in [False, True]:
 6          for use_tt in [False, True]:
 7              for init_ab in [False, True]:
 8                  print(f"ai_for_mo: {ai_for_mo}, sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
 9                  count = 0
10                  count2 = 0
11                  for mb in mblist:
12                      count += ai_abs_all(mb, ai_for_mo=ai_for_mo,
13                                          shortest_victory=shortest_victory,
14                                          init_ab=init_ab, use_tt=use_tt,
15                                          sort_allnodes=False, calc_score=True, calc_count=True)
16                      count2 += ai_abs_all(mb, ai_for_mo=ai_for_mo,
17                                          shortest_victory=shortest_victory,
18                                          init_ab=init_ab, use_tt=use_tt,
19                                          sort_allnodes=True, calc_score=True, calc_count=True)
20                  print("count=", count)
21                  print("count2=", count2)        
```

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

```python
from util import load_mblist

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,
                                        shortest_victory=shortest_victory,
                                        init_ab=init_ab, use_tt=use_tt,
                                        sort_allnodes=True, calc_score=True, calc_count=True)
                print("count=", count)
                print("count2=", count2)
```
</details>

実行結果

```
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: False, use_tt: False
count= 13816
count2= 13214
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: True, use_tt: False
count= 8745
count2= 7938
ai_for_mo: <function ai10s at 0x00000216EC394D60>, sv: False, init_ab: False, use_tt: True
count= 10371
count2= 9904
略
```

下記は実行結果をまとめた表です。

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

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __`ai10s`__ | 13816<br>13214 | 8475<br>7938 | 10371<br>9904 | 6625<br>5976 | 
| __`ai14s`__ | 10683<br>10679 | 6131<br>6076 | 8795<br>8792 | 5003<br>4964 |

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

| | ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 |
|:--|--:|--:|--:|--:|
| __`ai10s`__ | 15048<br>13950 | 13131<br>11818 | 11082<br>10300 | 9806<br>8811 | 
| __`ai14s`__ | 10691<br>10679 | 9267<br>9251 | 8810<br>8796 | 7556<br>7549 |


上記の結果から、move ordering の関数に __`ai10s`__ を利用した場合の比較を行うと、下段の __全ノードの move ordering を行う場合のほうが__ 計算されたノードの数がいずれも __約 5 ~ 10 % 減り__、効率が高くなることが確認できました。このことから、__弱解決ではない `ai10s`__ で move ordering を行う場合は、先頭の子ノードを並べ替えるよりは、__全ての子ノードを並べ替えたほうが効率が向上する__ ことが確認できました。

一方、move ordering の関数に __`ai14s`__ を利用した場合の比較を行うと move ordering の種類によって効率がほとんど変わらないことが確認できます。__全ノードの move ordering を行う場合のほうが__ 一部の例外を除いてほんの少しだけ効率が上がっているのは、`ai14s` は弱解決の AI なので、ほんの一部の局面で正しい評価値を計算できないからでしょう。従って、__精度が非常に高い AI__ で move ordering を行う場合は、ほとんどの場合で先頭の子ノードの評価値が一番高くなるため、__先頭の子ノードを並べ替えるだけで充分__ であることがわかります。

上記から move ordering で全ノードの move ordering を行う必要があるかどうかは、__以下の 2 つの時間を見積り__、__全体の処理時間が短くなるほうを適切に選択__ する必要があります。

* move ordering による枝狩りの効率の差による処理時間
* move ordering を行うための計算に必要な処理時間

本記事で紹介したルールベースの AI を使って move ordering を行う場合は、後者の処理時間はほとんどかわらないので、全ノードの move ordering を行う方が良いでしょう。一方本記事では説明していませんが、move ordering で良く使われる反復深化の場合は、全ノードの move ordering を行う場合は後者の処理時間が前者よりも長くなる可能性が高いので先頭のみの move ordering が使われているのだと思います。

# 今回の記事のまとめ

今回の記事では、move ordering を行う αβ 法の AI を定義し、先頭のみと全ノードのそれぞれで move ordering の精度と枝狩りの効率化の関係について説明しました。

次回の記事ではスカウト法を紹介し、move ordering を行う αβ 法との比較を行います。

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

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

# 次回の記事

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

[^1]:一般的にはスカウト法と実質的に同じ処理を行う __ネガスカウト（negascout）法のほうが良く使われる__ ようです。ネガスカウト法については次回の記事で説明します
[^2]:move ordering の説明を行った[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#ai-%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%97%E3%81%9F%E6%9C%80%E5%96%84%E6%89%8B%E3%82%92%E7%9D%80%E6%89%8B%E3%81%97%E3%81%9F%E5%AD%90%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E6%9C%80%E5%88%9D%E3%81%AB%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B)では Mbtree クラスの `move_ai_bestmove_to_head` メソッドなどを定義して __作成済のゲーム木の子ノードの順番を直接並べ替える__ という move ordering を行いましたが、αβ 法で __ゲーム木を実際に作成せず__ に move ordering を行う __AI の関数は定義しませんでした__
[^3]:この条件が満たされていれば move ordering で __子ノードを正しく並べ替えることができる__ ので、計算される評価値は αβ 法で計算される -1 ~ 1 のような値と __異っていてもかまいません__。例えば `ai14s` では 100 のような -1 ~ 1 の範囲とは全く異なる評価値を計算します