Pythonで〇×ゲームのAIを一から作成する　その150　αβ 法の処理の効率の性質と改善方法

# 目次と前回の記事

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

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

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

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

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

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

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

# αβ 法の目的のおさらいと〇×ゲームでの効率

αβ 法の目的は、__ミニマックス法__ で __ゲーム木の評価値を計算__ する際に、__枝狩りを行うことで__ 計算を行う必要がないノードの処理を省略して __計算時間を短縮__ することです。忘れた方は[以前の記事](https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9)を復習して下さい。

__〇× ゲームの場合__ は __ルートノードの評価値を αβ法で計算__ すると、__最短の勝利を優先しない__ 評価値を計算する場合は、下記のプログラムの実行結果から __ミニマックス法と比較__ して __計算時間を約 3.3 %__ という __かなり短い時間で計算__ することができます。

なお、ゲーム木のデータは[前回の記事](https://qiita.com/ysgeso/items/ffa55bf637e6810b0330#%E4%BD%9C%E6%88%90%E3%81%97%E3%81%9F%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E4%BF%9D%E5%AD%98)で αβ 法の評価値を計算したゲーム木を保存したファイルから読み込んでいます。

```python
from tree import Mbtree

mbtree = Mbtree.load("../data/abtree_root")
mbtree.calc_score_by_ab(mbtree.root, debug=True)
```

実行結果

```
計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%
```

また、__最短の勝利を優先する__ 評価値を計算する場合も、下記のプログラムの実行結果からミニマックス法と比較して計算時間を __約 3.8 %__ というかなり短い時間で計算することができることがわかります。

```python
mbtree = Mbtree.load("../data/abtree_sv_root")
mbtree.calc_score_by_ab(mbtree.root, debug=True)
```

実行結果

```
計算したノードの数 20866
枝狩りしたノードの数 529080
合計 549946
割合 3.8%
```

今回の記事では以後は最短の勝利を __優先しない__ 評価値を計算する __場合の説明__ を行います。最短の勝利を __優先する場合も同様__ なので、興味がある方は調べてみて下さい。

# αβ 法の処理の効率の性質

[以前の記事](https://qiita.com/ysgeso/items/abe910c5067cb7143faa#%CE%B1%CE%B2-%E6%B3%95%E3%81%A7%E8%A1%8C%E3%82%8F%E3%82%8C%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81)で説明したように αβ 法では、__α 値や β 値が更新__ されると __子孫ノードの評価値の計算の際__ に __枝狩りが行われる評価値の範囲が増える__ ので __枝狩りが行われやすく__ なります。

__max ノード__ の評価値を計算する際は __α 値__ は __増加する方向でのみ更新される__ ので、max ノードの子ノードの評価値を計算する処理を行う際に、__最も評価値が高い子ノードの評価値を最初に計算__ すると、__2 つ目以降の子ノード__ の評価値を計算する際の __α 値が最も高くなり__、その結果として __最も多くの枝狩りが行われる__ ようになります。

同様の理由で __min ノード__ の場合は __最も評価値が低い子ノードの評価値を最初に計算__ することで、最も多くの枝狩りが行われるようになります。

max ノードの最も評価値が高い子ノードと、min ノードの最も評価値が低い子ノードは、__いずれもそのノードの最善手を着手した子ノード__ なので、上記は以下のようにまとめることが出来ます。

:::note warn
αβ 法ではそのノードの __最善手を着手した子ノードを最初に計算__ することで __最も多くの枝狩りが行われる__ 。
:::

わかりづらいと思いますので、具体例として以下のようなノード $N$ の評価値を αβ 法で計算する例を紹介します。なお、min ノードの性質は max ノードの逆であるため同様の方法で説明できるため、__max ノードのみの説明__ を行います。

* max ノードである
* 評価値がそれぞれ -1、0、1 である 3 つの子ノードを持つ
* このノードの評価値を計算する際の α 値と β 値の初期値は、それぞれ負の無限大と正の無限大である

ノード $N$ の評価値を αβ 法で計算する際に、__3 つの子ノード__ の評価値を計算する __順番__ は 3 × 2 × 1 = __6 通り__ あるので、それぞれの場合で行われる処理について説明します。

以下の説明では 3 つの子ノード（child node）を $C_1$、$C_2$、$C_3$ と表記し、$C_1$、$C_2$、$C_3$ の順で子ノードの評価値が計算されるものとします。また、$C_1$、$C_2$、$C_3$ の評価値（score）をそれぞれ $S_1$、$S_2$、$S_3$ と表記することにします。

## 評価値が高い順に子ノードの評価値を計算した場合の処理

子ノードの __評価値が高い順__ に計算を行った場合は、$S_1=1$、$S_2=0$、$S_3=-1$ となり、以下の手順で計算が行われます。なお、下記には記していませんが、α 狩りが行われた場合は残りの子ノードの処理は省略されます。

1. $N$ の最初の子ノードの $C_1$ の評価値を計算する際の α 値と β 値はそれぞれ負の無限大と正の無限大なので、$C_1$ の評価値を計算する際の α 値と β 値の初期値はその値になる
2. $C_1$ の評価値の計算が行われるが、下記の理由から __枝狩りが行われることはない__
    * $N$ の子ノードは min ノードであり、__min ノードでの枝狩りは α 狩り__ である
    * __α 値の初期値__ は __負の無限大__ であり、__min ノードの計算の最中__ に __α 値が変更されることはない__ ので $C_1$ の評価値を計算する際の __α 値は常に負の無限大__ である
    * __α 狩りが行われる条件__ は、$C_1$ の __子ノードの評価値が α 値以下__ であるが、__α 値は負の無限大__ なので $C_1$ の評価値を計算する際に __α 狩りが行われることはない__
3. $C_1$ の評価値が 1 と計算され、α 値が 1 に更新される
4. $N$ の次の子ノード $C_2$ の評価値の計算を α 値が 1、β 値が正の無限大として開始する
5. $C_2$ の子ノードの評価値が α 値以上の場合に α 狩りが行われる
6. $C_2$ の評価値が 0 と計算されるが、α 値以下なので α 値は 1 のまま更新されない
7. $N$ の次の子ノード $C_3$ の評価値の計算を α 値が 1、β 値が正の無限大として開始する
8. $C_3$ の子ノードの評価値が α 値以上の場合に α 狩りが行われる
9. $C_3$ の評価値が -1 と計算されるが、α 値以下なので α 値は 1 のまま更新されない
10. $N$ の評価値が α 値である 1 と計算される

上記の処理を表にすると以下のようになります。上記の処理からわかるように β 値は $C_1$、$C_2$、$C_3$ での枝狩りに影響しないので省略しました。また、表ではそれぞれの __子ノードの評価値の計算__ で __α 狩りが行われる条件__ を記しました。

|  | α 値 | α 狩りが行われる条件 | 評価値 |
|:-:|:-:|:-:|:-:|
| $C_1$ | 負の無限大  | α 狩りは行われない  | 1 | 
| $C_2$  |  1 | $C_2$ の子ノードの評価値 ≦ 1  | 0  |
| $C_3$  |  1 | $C_3$ の子ノードの評価値 ≦ 1  | -1  |

## 評価値が低い順に子ノードの評価値を計算した場合の処理

子ノードの __評価値が低い順__ に計算を行った場合は、$S_1=-1$、$S_2=0$、$S_3=1$ となり、以下の手順で計算が行われます。__先ほどの手順と異なる部分を太字__ にしました。

1. $N$ の最初の子ノードの $C_1$ の評価値を計算する際の α 値と β 値はそれぞれ負の無限大と正の無限大なので、$C_1$ の評価値を計算する際の α 値と β 値の初期値はその値になる
2. $C_1$ の評価値の計算が行われるが、下記の理由から枝狩りが行われることはない
    * $N$ の子ノードは min ノードであり、min ノードでの枝狩りは α 狩りである
    * α 値の初期値は負の無限大であり、min ノードの計算の最中に α 値が変更されることはないので $C_1$ の評価値を計算する際の α 値は常に負の無限大である
    * α 狩りが行われる条件は、$C_1$ の 子ノードの評価値が α 値以下であるが、α 値は負の無限大なので $C_1$ の評価値を計算する際に α 狩りが行われることはない
3. $C_1$ の __評価値が -1__ と計算され、__α 値が -1 に更新__ される
4. $N$ の次の子ノード $C_2$ の評価値の計算を __α 値が -1__、β 値が正の無限大として開始する
5. $C_2$ の子ノードの評価値が α 値以上の場合に α 狩りが行われる
6. $C_2$ の評価値が 0 と計算され、__α 値より大きい__ ので __α 値は 0 に更新__ される
7. $N$ の次の子ノード $C_3$ の評価値の計算を __α 値が 0__、β 値が正の無限大として開始する
8. $C_3$ の子ノードの評価値が α 値以上の場合に α 狩りが行われる
9. $C_3$ の評価値が 1 と計算され、__α 値より大きい__ ので __α 値は 1 に更新__ される
10. $N$ の評価値が α 値である 1 と計算される

上記の処理を先程と同様の表にすると以下のようになります。

|  | α 値 | α 狩りが行われる条件 | 評価値 |
|:-:|:-:|:-:|:-:|
| $C_1$ | 負の無限大  | α 狩りは行われない  | -1 | 
| $C_2$  |  -1 | $C_2$ の子ノードの評価値 ≦ -1  | 0  |
| $C_3$  |  0 | $C_3$ の子ノードの評価値 ≦ 0  | 1  |

## 他の場合の処理

残りの場合も同様の方法で処理が行われ、先程と同様の表にすると以下のようになります。

$S_1=1$、$S_2=-1$、$S_3=0$ の場合

|  | α 値 | α 狩りが行われる条件 | 評価値 |
|:-:|:-:|:-:|:-:|
| $C_1$ | 負の無限大  | α 狩りは行われない  | 1 | 
| $C_2$  |  1 | $C_2$ の子ノードの評価値 ≦ 1  | -1  |
| $C_3$  |  1 | $C_3$ の子ノードの評価値 ≦ 1  | 0  |

$S_1=0$、$S_2=1$、$S_3=-1$ の場合

|  | α 値 | α 狩りが行われる条件 | 評価値 |
|:-:|:-:|:-:|:-:|
| $C_1$ | 負の無限大  | α 狩りは行われない  | 0 | 
| $C_2$  |  0 | $C_2$ の子ノードの評価値 ≦ 0  | 1  |
| $C_3$  |  1 | $C_3$ の子ノードの評価値 ≦ 1  | -1  |

$S_1=0$、$S_2=-1$、$S_3=1$ の場合

|  | α 値 | α 狩りが行われる条件 | 評価値 |
|:-:|:-:|:-:|:-:|
| $C_1$ | 負の無限大  | α 狩りは行われない  | 0 | 
| $C_2$  |  0 | $C_2$ の子ノードの評価値 ≦ 0  | -1  |
| $C_3$  | 0  | $C_3$ の子ノードの評価値 ≦ 0  | 1  |

$S_1=-1$、$S_2=1$、$S_3=0$ の場合

|  | α 値 | α 狩りが行われる条件 | 評価値 |
|:-:|:-:|:-:|:-:|
| $C_1$ | 負の無限大  | α 狩りは行われない  | -1 | 
| $C_2$  |  -1 | $C_2$ の子ノードの評価値 ≦ -1  | 1  |
| $C_3$  |  1 | $C_3$ の子ノードの評価値 ≦ -1  | 0  |

## それぞれの場合の α 狩りが行われる条件の比較

それぞれの場合で __α 狩りが行われる条件を比較__ すると以下のような表になります。表の中身の意味は以下の通りです。

* 一番上の行には $S_1$、$S_2$、$S_3$ の値を順に表記する
* 表のセルには __α 狩り__ が行われる __子ノードの評価値の条件__ を表記する
* $C_1$ ではいずれの場合も α 狩りは行われないので省略した
* 最も条件が緩いものを __太字__ で、最も条件が厳しいものを _斜体_ で表示した

|  | 1、0、-1 | 1、-1、0 | 0、1、-1| 0、-1、1| -1、1、0 |-1、0、1|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $C_2$  | __1 以下__ | __1 以下__ | 0 以下 | 0 以下 | _-1 以下_ | _-1 以下_ |
| $C_3$  | __1 以下__ | __1 以下__ | __1 以下__ | _0 以下_ | 1 以下 | _0 以下_ |

上記の表から __最初に最も評価値が高い子ノード__ の評価値を計算した場合に $C_2$ と $C_3$ の __両方で α 狩りが行われる条件が最も緩い__ ので __最も多く枝狩りが行われる__ ことがわかります。

また、__評価値が低い順__ に子ノードの評価値を計算した場合に $C_2$ と $C_3$ の __両方で α 枝狩りが行われる条件が最も厳しい__ ので、__最も少なくの枝狩りが行われる__ こともわかります。

上記の例では α 値と β 値の初期値を負の無限大と正の無限大、子ノードの数を 3、それぞれの子ノードの評価値の値を -1、0、1 としましたが、__他の条件でも上記と同じことが言えます__。興味がある方は様々な条件で表を作って確認してみて下さい。

## max ノードで最も評価値が高い子ノードが複数ある場合

__max ノード__ で __最も評価値が高い子ノード__ が __複数ある場合__ は、それらの中の __どの子ノードを最初に計算__ しても __上記の表の結果は変わりませんが__、実際には最も評価値が高い子ノードの中で __どの子ノードを先頭に移動するか__ によって、__枝狩りが行われる数が変わります__。その理由について少し考えてみて下さい。

αβ 法では、__親ノードから受け渡された α 値と β 値__ を利用して計算を行います。また、__子ノードの評価値が計算__ されることで、__α 値または β 値を更新__ します。

従って、__最初に計算する子ノード__ は必ず __親ノードから受け渡された α 値と β 値__ を利用して計算を行を行う必要があります。

例えば max ノードで $C_1$、$C_2$ という 2 つの子ノードが、最も高い $S$ という評価値を持つ場合に、$C_1$ の評価値を最初に計算すると以下の順番で計算が行われます。

1. 親ノードから受け継がれた α 値と β 値を初期値として $C_1$ の評価値を計算する
2. $C_1$ の評価値が $S$ と計算され、α 値 < $S$ の場合は α 値を $S$ で更新する
3. $C_2$ の評価値を計算する

一方 $C_2$ を最初に計算すると以下の順番で計算が行われます。

1. 親ノードから受け継がれた α 値と β 値を初期値として $C_2$ の評価値を計算する
2. $C_2$ の評価値が $S$ と計算され、α 値 < $S$ の場合は α 値を $S$ で更新する
3. $C_1$ の評価値を計算する

__親ノードから受け継がれた α 値が $S$ よりも小さい場合__ は上記の手順 2 で __α 値が更新される__ ので、$C_1$ と $C_2$ を計算する際の __α 値の初期値__ は、$C_1$ と $C_2$ の __どちらを最初に計算するか__ によって、下記の表のように __異なります__。

|  | $C_1$ を先に計算した場合  | $C_2$ を先に計算した場合  |
|:-:|:-:|:-:|
| $C_1$ | 親から受け継がれた α 値  | $S$  |
| $C_2$  | $S$  | 親から受け継がれた α 値  |

__α 値の初期値が異なれば__ $C_1$、$C_2$ の評価値の計算を行った際の __枝狩りの数は異なる__ 場合が生じるので、__どちらを先に計算するか__ によって __枝狩りの数が異なる__ 可能性が生じます。

ただし、一般的には最も評価値が高い子ノードの中で、どの子ノードを最初に計算すると最も枝狩りが行われるかを __知ることは困難__ です。また、__ほとんどの場合は枝狩りの数が大きく異なることはない__ ので、最初に計算する子ノードは __どれを選んでも構わない__ でしょう。

なお、この性質は max ノードで評価値の低い順に計算する場合も同様です。

## αβ 法の枝狩りの効率のまとめ

ここまでの内容をまとめると以下のようになります。

:::note warn
αβ 法では子ノードの評価値を計算する際に、__最善手を着手した子ノードを最初に計算__ すると __最も多くの枝狩り__ が行われる。

__最善手を着手した子ノードが複数ある場合__ は、その中のどの子ノードを最初に計算するかによって、枝狩りの数が異なる場合があるが、ほとんどの場合で大きく異なることはないので __一般的にはどれを選んでも良い__。
:::

なお、わざわざ効率の悪い処理を行うことは通常はないので、下記の内容は上記のまとめから除外しました。

:::note
αβ 法では、max ノードの子ノードの評価値を計算する際に、評価値が低い順に子ノードの計算を行うと最も少なく枝狩りが行われる。min ノードでは、評価値の大小を逆に考えると同じことが言える。
:::

## 効率の良い αβ 法の処理を行う工夫

残念ながら __αβ 法の計算__ を行う際に、それぞれの __子ノードの評価値の正確な値__ を __あらかじめ知ることはできません__[^1]。そのため、αβ 法で効率の良い計算を行いたい場合に、__αβ 法以外の方法__ で __最善手と思われる着手を見積もる__ ことで、最も評価値が高いと __考えられる__ 子ノードの評価値の計算を最初に行うという工夫があります。

例えば本記事でこれまでに作成した __αβ 法とは異なる方法で最善手を計算する関数を利用__ するなどの方法があるので、この後で実際に行ってみることにします。他にも αβ 法の効率を高める様々な方法が考えられているので、興味がある方は調べてみると良いでしょう。

# αβ 法の枝狩りの効率の確認

__上記が本当に正しいか__ どうかを、以下のそれぞれの場合で αβ 法を実行して比較することで __確認する__ ことにします。なお、下記では max ノードでの条件を記述していますが、min ノードではその逆の条件で計算を行います。

* 最善手を着手した子ノードを最初に計算する
* 様々な AI で計算した最善手を着手した子ノードを最初に計算する。なお、弱解決でない AI は本当の最善手を計算するとは限らない
* max ノードでは評価値が低い順に、min ノードでは評価値が高い順に子ノードを計算する

上記のような計算を行う方法について少し考えてみて下さい。

## 最善手を着手した子ノードを最初に計算する

αβ 法で評価値を計算する __`calc_score_by_ab`__ では、__子ノードの評価値を計算する際__ に、下記のプログラムのように __子ノードの一覧が list で記録__ されている __`children` 属性の先頭の要素から順番__ に計算を行っています。

```python
    for childnode in node.children:
```

そのため、ゲーム木の __全てのノードに対して__、__下記の処理を行った後で `calc_score_by_ab` を実行する__ ことで、__評価値が最も高い子ノードが最初に計算される__ ようになります。

* 最善手を着手した子ノードを `children` 属性の list の __要素から探す__
* __見つけた要素__ を `children` 属性の __先頭の要素と交換__ する

上記の処理を行う方法について少し考えてみて下さい。

:::note
見つけた要素を先頭に移動し、先頭から見つけた要素までを 1 つずつ後ろにずらすという方法も考えられますが、順番を維持する必要がないのであれば、ずらすという処理に時間がかかるのであまりお勧めしません。

例えば、1000 冊の本が並べられている本棚の 900 冊目の本を先頭に移動したい場合に、1 冊目と 900 冊目を交換するのは簡単ですが、900 冊目を取り出して、1 ~ 899 冊目の本を 1 つずつずらして、900 冊目を 1 冊目の所にいれるのは大変です。
:::

### 上記の処理の記述方法

最善手を着手した子ノードが代入された要素を `children` 属性の先頭の要素と交換するということは、最善手の要素の __インデックスを `i`__ とした場合に __0 番と `i` 番の要素を入れ替える__ 処理を行うということです。

ノードが `node` という変数に代入されている場合は、[以前の記事](https://qiita.com/ysgeso/items/9303214ec798a920174e#%E5%A4%89%E6%95%B0%E3%81%AE%E5%80%A4%E3%81%AE%E4%BA%A4%E6%8F%9B)で説明した、変数の値を入れ替える方法を利用することで下記のプログラムのように記述することができます。

```python
node.children[0], node.children[i] = node.children[i], node.children[0]
```

最善手を着手した子ノードが代入された `children` 属性の要素の __インデックス__ は、以下の手順で求めることができます。

* 最善手を着手した子ノードの __評価値は__ 、__そのノードの評価値と等しい__
* `children` 属性の __先頭の要素から__ そのノードの評価値と __等しい要素を探す__

なお、先程説明したように __最善手が複数ある場合__ は、その中の __どの最善手を選択しても枝狩りの数は大きく変わらない__ ので、__最初に見つかった最善手を選択する__ ことにします。

従って `node` の最善手を着手した子ノードを `children` 属性の先頭と入れ替える処理は下記のプログラムのように記述することができます。

* __1 行目__：組み込み関数 [`enumerate`](https://qiita.com/ysgeso/items/7cd67869855550d222f5#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0-enumerate) を利用して `children` 属性の先頭の要素から順番に、そのインデックスと要素を変数に代入するという繰り返し処理を行う
* __2 ~ 4 行目__：親ノードと子ノードの評価値が等しい場合は、最善手を着手した子ノードなので、4 行目でそのノードと先頭のノードを交換し、5 行目の break 文で繰り返し処理を終了する

```python
1  for i, childnode in enumerate(node.children):
2      if node.score == childnode.score:
3          node.children[0], node.children[i] = node.children[i], node.children[0]
4          break
```

:::note
ゲームの決着がついたノードには子ノードは存在しませんが、その場合は `children` 属性に空の list が代入されているので、2 ~ 4 行目の処理は 1 度も行われません

先頭の子ノードの評価値が親ノードの評価値と等しい場合は `i` に 0 が代入された状態で 3 行目が実行されますが、その場合は下記のプログラムのように 0 番の要素に 0 番の要素が代入されるという処理が 2 回行われ、実質的に何の処理も行われないことになるので問題はありません。

```python
node.children[0], node.children[0] = node.children[0], node.children[0]
```
:::

:::note
以下の手順で先頭に移動したい要素のインデックスを求めることもできます。同様の方法を、この後の [`move_ai_bestmove_to_head`](#ai-の最善手のノードを最初に計算する) で実際に利用します。また、この方法は Mbtree クラスの [`draw_subtree`](https://qiita.com/ysgeso/items/6d1430a88e251279d77a#draw_subtree-%E3%81%AE%E4%BF%AE%E6%AD%A3-2) メソッドの中で既に記述しています。

* __1 行目__：子ノードが存在しない場合に 2 行目を実行するとエラーになるので子ノードが存在する場合のみ処理を行うようにする
* __2 行目__：最善手の一覧を表す `bestmoves` 属性の中から先頭の要素を取り出す
* __3 行目__：最善手を着手したノードを `children_by_move` 属性から取り出す
* __4 行目__：実引数に記述した値が代入されている要素のインデックスを計算する list の [`index` メソッド](https://qiita.com/ysgeso/items/51c2eba867aa560808c6#index-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E8%A3%9C%E8%B6%B3) を利用してインデックスを計算する

```python
1  if len(node.bestmoves) > 0:
2      bestmove = node.bestmoves[0]
3      bestnode = node.children_by_move[bestmove]
4      index = node.children.index(bestnode)
```
:::

### Mbtree クラスの `move_bestmove_to_head` の定義

__すべてのノード__ に対して上記の処理を行う __`move_bestmove_to_head`__ というメソッドを Mbtree クラスに下記のプログラムのように定義する事にします。なお、先頭（head）に移動する子ノードは __最善手（bestmove）のノード__ なので、そのような名前にしました。

全てのノードに対して先程の処理を記述しているだけなので、説明は省略します。

```python
from tree import Mbtree

def move_bestmove_to_head(self):
    for node in self.nodelist:
        for i, childnode in enumerate(node.children):
            if node.score == childnode.score:
                node.children[0], node.children[i] = node.children[i], node.children[0]
                break
            
Mbtree.move_bestmove_to_head = move_bestmove_to_head
```

[以前の記事](https://qiita.com/ysgeso/items/abe910c5067cb7143faa#%CE%B1-%E5%80%A4%E3%82%84-%CE%B2-%E5%80%A4%E3%82%92%E5%88%9D%E6%9C%9F%E5%80%A4%E3%81%A8%E3%81%97%E3%81%A6%E8%A8%88%E7%AE%97%E3%82%92%E8%A1%8C%E3%81%A3%E3%81%A6%E8%89%AF%E3%81%84%E7%90%86%E7%94%B1)で説明したように、αβ 法では __本当の評価値とは異なる評価値__ が計算される __ノードが存在する__ ので、下記のプログラムのように __新しくゲーム木を作成__ しそのデータに対して __`move_bestmove_to_head`__ メソッドを __呼び出す必要__ があります。その後で __`calc_score_by_ab`__ を実行すると、実行結果のように評価値を計算するノードの割合が __0.4 %__ のように、先程の 3.3 % と比べて __さらに少なくなったことが確認__ できます。

```python 
mbtree = Mbtree(algo="df")
mbtree.move_bestmove_to_head()
mbtree.calc_score_by_ab(mbtree.root, debug=True)
```

実行結果

```
計算したノードの数 2312
枝狩りしたノードの数 547634
合計 549946
割合 0.4%
```

なお、αβ 法で __最も効率よく枝狩りを行なえる場合__ は、計算する必要があるノード数が __全体のノードの数の平方根の値くらいになる__ と言われています。$\sqrt{549946} = 約 741.5 $ なので、上記の 2312 は平方根よりは多いですが、〇× ゲームのゲーム木では __平方根と大きく変わらないくらいの効率__ で枝狩りが行うことができていることが確認できました。

## AI が計算した最善手を着手した子ノードを最初に計算する

次に、__指定した AI で計算した最善手__ を着手した子ノードを __最初に計算__ する __`move_ai_bestmove_to_head`__ というメソッドを Mbtree クラスに定義する事にします。この関数の __仮引数__ は __AI の関数を代入する `ai`__ とその __パラメータ―を代入する `params`__ です。

### Mbtree クラスの `move_ai_bestmove_to_head` の定義

下記は `move_ai_bestmove_to_head` の定義です。

* __1 行目__：仮引数 `ai` と `params` を持つメソッドとして定義する。また `params` はデフォルト値を `{}` とするデフォルト引数とする
* __3 行目__：子ノードが存在する場合のみ処理を行うようにする
* __4 行目__：`node` の局面に対する最善手の計算を仮引数 `ai` に代入された AI で行う。またその際に、仮引数 `params` に代入されたパラメータを利用する
* __5 行目__：list の `index` メソッドを利用して `children` 属性の list の中から `bestmove` が代入されている要素のインデックスを計算する
* __6 行目__：0 番と `i` 番の要素を入れ替える

```python
1  def move_ai_bestmove_to_head(self, ai, params={}):
2      for node in self.nodelist:
3          if len(node.children) > 0:
4              bestmove = ai(node.mb, **params)
5              bestnode = node.children_by_move[bestmove]
6              i = node.children.index(bestnode)
7              node.children[0], node.children[i] = node.children[i], node.children[0]
8              
9  Mbtree.move_ai_bestmove_to_head = move_ai_bestmove_to_head
```

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

```python
def move_ai_bestmove_to_head(self, ai, params={}):
    for node in self.nodelist:
        if len(node.children) > 0:
            bestmove = ai(node.mb, **params)
            bestnode = node.children_by_move[bestmove]
            i = node.children.index(bestnode)
            node.children[0], node.children[i] = node.children[i], node.children[0]
            
Mbtree.move_ai_bestmove_to_head = move_ai_bestmove_to_head
```

</details>

### 様々な AI を利用した αβ 法の計算

上記の定義後に、下記のプログラムで __`ai1s` から `ai14s`__ で計算した __最善手を着手した子ノードを最初に計算__ した場合の αβ 法の計算を行います。なお、先ほどの `move_bestmove_to_head` と異なり、__最善手__ はゲーム木のノードの `score` 属性ではなく __AI の関数で計算する__ ので、__ゲーム木のデータを毎回作り直す必要はありません__。

なお、これらの AI では最善手を計算する際に __乱数を利用する__ ので、下記の実行結果とは __異なる結果になる場合があります__。

* __1 行目__：ai モジュールを ai_module という名前でインポートする
* __3 行目__：1 ~ 14 までの整数の繰り返し処理を行う
* __4、5 行目__：AI の名前を変数に代入し、`print` で表示する
* __6 行目__：`getattr` を利用して AI の関数を ai のモジュールから取り出す
* __7 行目__：取り出した AI の関数を実引数に記述して `move_ai_bestmove_to_head` を呼び出す
* __8 行目__：キーワード引数 `debug=True` を記述して `calc_score_by_ab` を呼び出して、ルートノードの評価値を計算した結果を表示する

```python
1  import ai as ai_module
2
3  for i in range(1, 15):
4      ainame = f"ai{i}s"
5      print(ainame)
6      ai = getattr(ai_module, ainame)
7      mbtree.move_ai_bestmove_to_head(ai)
8      mbtree.calc_score_by_ab(mbtree.root, debug=True)
```

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

```python
import ai as ai_module

for i in range(1, 15):
    ainame = f"ai{i}s"
    print(ainame)
    ai = getattr(ai_module, ainame)
    mbtree.move_ai_bestmove_to_head(ai)
    mbtree.calc_score_by_ab(mbtree.root, debug=True)
```
</details>

実行結果

```
ai1s
計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%
ai2s
計算したノードの数 14941
枝狩りしたノードの数 535005
合計 549946
割合 2.7%
ai3s
計算したノードの数 8906
枝狩りしたノードの数 541040
合計 549946
割合 1.6%
ai4s
計算したノードの数 8461
枝狩りしたノードの数 541485
合計 549946
割合 1.5%
ai5s
計算したノードの数 5721
枝狩りしたノードの数 544225
合計 549946
割合 1.0%
ai6s
計算したノードの数 4839
枝狩りしたノードの数 545107
合計 549946
割合 0.9%
ai7s
計算したノードの数 2156
枝狩りしたノードの数 547790
合計 549946
割合 0.4%
ai8s
計算したノードの数 1918
枝狩りしたノードの数 548028
合計 549946
割合 0.3%
ai9s
計算したノードの数 1756
枝狩りしたノードの数 548190
合計 549946
割合 0.3%
ai10s
計算したノードの数 2337
枝狩りしたノードの数 547609
合計 549946
割合 0.4%
ai11s
計算したノードの数 1582
枝狩りしたノードの数 548364
合計 549946
割合 0.3%
ai12s
計算したノードの数 1496
枝狩りしたノードの数 548450
合計 549946
割合 0.3%
ai13s
計算したノードの数 1496
枝狩りしたノードの数 548450
合計 549946
割合 0.3%
ai14s
計算したノードの数 1496
枝狩りしたノードの数 548450
合計 549946
割合 0.3%
```

下記は上記の実行結果から、__計算したノードの数__ と __割合__ を __表にまとめたもの__ です。それぞれの 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)を参照して下さい。

| AI | ノードの数 | 割合 |
|:-:|--:|--:|
| なにもしない | 18297 | 3.3 % |
| __`ai1s`__  | 18297  | 3.3 % |
| __`ai2s`__  | 14941  | 2.7 % |
| __`ai3s`__  | 8906  | 1.6 % |
| __`ai4s`__  | 8461  | 1.5 % |
| __`ai5s`__  | 5721  | 1.0 % |
| __`ai6s`__  | 4839  | 0.9 % |
| __`ai7s`__  | 2156  | 0.4 % |
| __`ai8s`__  | 1918  | 0.3 % |
| __`ai9s`__  | 1756  | 0.3 % |
| __`ai10s`__  | 2337  | 0.4 % |
| __`ai11s`__  | 1582  | 0.3 % |
| __`ai12s`__  | 1496  | 0.3 % |
| __`ai13s`__  | 1496  | 0.3 % |
| __`ai14s`__  | 1496  | 0.3 % |
| `move_bestmove_to_head` で<br>最善手を先頭に移動 | 2312  | 0.4 % |

### 計算結果の考察

__`ai1s`__ は左上のマスから順に空いているマスを調べて着手する AI なので __`children` 属性の先頭の要素を常に選択する AI__ です。従って __なにもせずに αβ 法を計算した際と同じ結果__ になります。

__`ai2s`__ は __ランダムな着手を行う AI__ です。何もしない場合よりは __若干割合が減っている__ のはおそらくランダムに着手を行ったほうが、なにもしない場合よりも __先頭のノードの評価値が平均的に高くなる__ からだと思います[^2]。

__`ai3s`__ は __真ん中のマスに優先的に着手する__ という __単純な AI__ なので決して __強くはありません__。それにも関わらず、`ai3s` を利用することで枝狩りを行わないノードの割合を、何もしない場合の 3.3 % と比べて __約半分の 1.6 %__ に減らすことが出来ている点が気になった人はいないでしょうか？その理由について少し考えてみて下さい。

__`ai3s`__ は __〇 が最初に真ん中のマスに着手しなかった場合は、× の 1 手目で必ず最善手を着手する__ AI です。〇 の 1 手目は 9 通りの着手があるため、× の 1 手目を表す __深さ 1 の 9 つのノードのうち 8 つのノード__ で `ai3s` は __必ず最善手を選択__ します。

ゲーム木では一般的に __深さが浅い程、子孫ノードの数が多くなる__ ので、αβ 法では枝狩りを行ったノードの __深さが浅い程、一般的に多くの枝狩りを行うことができます__。そのため、__深さが 1 のノードの多くで最善手を選択__ する `ai3` を利用することで多くの枝狩りを行うことが出来、その結果割合を 1.6 % まで減らすことが出来たと考えられます。

__`ai3s`__ から __強くなるための様々な工夫__ が少しづつ行われており、その結果 __最善手が先頭に移動する場合が多くなる__ ため __割合も減っていく__ ことが確認できます。

__`ai8s`__ はまだ __弱解決の AI ではありません__ が、__弱解決の AI__ である `ai12s` 以降の AI と __割合が大きく変わりません__。このことから、弱解決の AI ではなくても、__ある程度以上の強さを持った AI__ を利用することで、__αβ 法の効率を大きく改善することが出来る__ ことがわかります。

なお、__弱解決の `ai12s` 以降の AI を利用__ した場合は、__`move_bestmove_to_head`__ によって __最善手を最初に計算する場合__ と比べて __割合が低くなっています__。これは、[先程説明](#max-ノードで最も評価値が高い子ノードが複数ある場合)したように、__最善手が複数存在する場合__ に、どの最善手の子ノードを最初に計算するかによって __枝狩りの数が若干変わることが原因__ です。ただし、この程度の差であれば処理時間に大きな差は生じないので、気にする必要はないでしょう。

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

:::note warn
最善手と思われる着手を計算する __AI を利用する__ ことで __αβ 法の枝狩りの効率__ を以下のように __改善することができる__

* __AI の精度が低すぎる__ と効率を上げることは __できない__
* __AI の精度が高いほど__ より __多くの効率をあげることができる__ が、__一定の精度から先__ は __効率がほとんど変わらなくなる__
:::

## max ノードで評価値が低い順、min ノードで評価値が高い順に子ノードを計算する

αβ 法が __最低でもどのくらいの効率を得ることが出来るか__ を、__max ノードで評価値が低い順、min ノードで評価値が高い順__ に子ノードを計算することで確認することにします。

max ノードで評価値が低い順に子ノードを計算するためには、すべての max ノードの __`children`__ 属性の __要素を評価値が低い順に並べ替える__ 必要があります。min ノードの場合は高い順に並べる必要があります。データを何らかの基準で __並べ替える__ ことを __ソート（sort）__ と呼び、python では以下の方法で __list のソート__ を行うことができます。

* list の __`sort` メソッド__ を利用する
* 組み込み関数 __`sorted`__ を利用する

list の `sort` メソッドの詳細は下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/library/stdtypes.html#list.sort

組み込み関数 `sorted` の詳細は下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/library/functions.html#sorted

なお、__ソートを行うアルゴリズム__ にはさまざまなものがあり、__アルゴリズムを勉強する際に役立つ__ ので、今後の記事でソートのアルゴリズムについて取り上げる予定です。

### list の `sort` メソッドと組み込み関数 `sorted` の使い方

この 2 つは似ていますが、__`sort` メソッド__ はその __list の要素そのものがソートされる__ のに対し、__`sorted`__ は __元の list は変更せず__ に、元のリストの要素をソートした __新しい list を作成して返す__ 処理を行う点が __異なります__。また、__`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)であればなんでもソートできる__ 点が異なります。

具体例を挙げます。下記のプログラムは list が代入された `a` に対して __`sort` メソッド__ を呼び出すことで、__`a` の要素を小さい順にソート__ するプログラムです。

```python
a = [3, 1, 2, 5, 4]
a.sort()
print(a)
```

実行結果

```
[1, 2, 3, 4, 5]
```

一方、下記のプログラムは __`sorted`__ を利用して __`a`__ の要素をソートした __新しい list を作成__ して __`b` に代入__ しています。実行結果からわかるように __`a` の中身は変更されません__。

```python
a = [3, 1, 2, 5, 4]
b = sorted(a)
print(a)
print(b)
```

実行結果

```
[3, 1, 2, 5, 4]
[1, 2, 3, 4, 5]
```

また、下記のプログラムのように __`sorted`__ は list だけでなく、__反復可能オブジェクトである tuple のソート__ を行うこともできます。__tuple__ はその内容を後から変更できない __イミュータブル__ なオブジェクト[^3]ですが、__`sorted`__ は元の tuple を変更するのではなく __新しい list を作成する__ のでこのような処理を行うことができます。

なお、実行結果からわかるように、__`sorted` が返す値__ は、実引数に記述したデータの種類に関わらず __必ず list になります__。

```python
a = (3, 1, 2, 5, 4)
b = sorted(a)
print(a)
print(b)
```

実行結果

```
(3, 1, 2, 5, 4)
[1, 2, 3, 4, 5]
```

このように、__list の `sort` メソッド__ と、__組み込み関数 `sorted`__ はどちらもソートを行いますが __異なる点がある__ ので、__状況に応じて使い分ける必要__ があります。


### 大きい順のソート

上記のソートでは数値の小さい順にソートが行われましたが、__大きい順にソートを行う__ 場合はどちらの場合でも下記のプログラムのように __反転（reverse）__ を表すキーワード引数 __`reverse=True` を記述__ します。

```python
a = [3, 1, 2, 5, 4]
a.sort(reverse=True)
print(a)
a = [3, 1, 2, 5, 4]
b = sorted(a, reverse=True)
print(a)
print(b)
```

実行結果

```
[5, 4, 3, 2, 1]
[3, 1, 2, 5, 4]
[5, 4, 3, 2, 1]
```

__以後の説明__ は `sort` メソッドも組み込み関数 `sorted` も __同じ__ なので __`sort` メソッドのみの説明を行います__。

### 数値以外のデータのソート

__`sort`__ メソッドは __< 演算子を利用__ してソートの処理を行っています[^4]。そのため、__< 演算子で比較を行うことができるデータ__ であれば、数値以外のデータが要素に代入されていても __利用することができます__。

例えば、__文字列型__ のデータは __< 演算子__ で __辞書順で比較が行われる__ ので下記のプログラムのように __辞書順でソート__ することができます。

```python
a = ["happy", "sad", "angry"]
a.sort()
print(a)
```

実行結果

```
['angry', 'happy', 'sad']
```

:::note
直観的に反すると思うかもしれませんが、下記のプログラムのように __小文字は大文字よりも大きい__ と判定されます。

```python 
print("abc" > "ABC")
```

実行結果

```
True
```

これは、__文字列の比較__ は __文字コード（文字を表す番号のこと）の数値__ で行われるためで、半角の文字の文字コードを定めた[ASCII 文字コード表](https://ja.wikipedia.org/wiki/ASCII)では小文字よりも大文字の方が文字コードの数字が大きく設定されているからです。

:::

一方、__クラスから作成されたインスタンス__ は、__通常は < 演算子で比較することはできません__[^5]。そのため、ノードを表す __Node クラスのインスタンス__ は __< 演算子で比較することができないの__ で、下記のプログラムのように __`children`__ 属性に代入されたノードの一覧を表す list の `sort` メソッドを呼び出すと実行結果のような __エラーが発生__ します。

```python
mbtree.root.children.sort()
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[13], line 1
----> 1 mbtree.root.children.sort()

TypeError: '<' not supported between instances of 'Node' and 'Node'
```

上記の Node クラスのインスタンス（instances）どうし（between）を < 演算子で比較することができない（not supported）というエラーメッセージはそのことを表しています。

__`children`__ 属性の要素に代入された __ノードのソート__ は、ノードの __`score` 属性に代入された評価値を基準__ として行う必要があります。そのような場合は、`sort` メソッドに下記のような __キーワード引数 `key` を記述__ することでソートを行うことができます。

* キーワード引数 `key` には以下のような __関数を代入__ する
    * ソートを行う __list の要素を代入__ する __仮引数を 1 つだけ__ 持つ
    * __返り値__ として、仮引数に代入されたオブジェクトの中の、__ソートの基準となるデータを返す__。返り値のデータは必ず __< 演算子で比較できる必要がある__
    * 関数の名前は何でもよい

具体例を挙げて説明します。下記のプログラムの 3 ~ 7 行目は __果物（fruit）の値段と名前を表す dict__ を要素として持つ list です。この list の要素を __値段の小さい順でソート__ するために、9、10 行目でこの __list の要素を代入する仮引数__ を持ち、__`price` のキーの値を返す__ という処理を行う __`keyfunc` という関数を定義__ しています。12 行目で __キーワード引数 `key=keyfunc`__ を記述して __`sort` メソッドを呼び出す__ ことで、実行結果のように __値段の小さい順に list の要素がソートされた__ ことが確認できます。

```python
 1  from pprint import pprint
 2  
 3  fruits = [
 4      { "name": "orange", "price": 200},
 5      { "name": "melon", "price": 1000},
 6      { "name": "apple", "price": 100},
 7  ]
 8  
 9  def keyfunc(fruit):
10      return fruit["price"]
11  
12  fruits.sort(key=keyfunc)
13  pprint(fruits)
```

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

```python
from pprint import pprint

fruits = [
    { "name": "orange", "price": 200},
    { "name": "melon", "price": 1000},
    { "name": "apple", "price": 100},
]

def keyfunc(fruit):
    return fruit["price"]

fruits.sort(key=keyfunc)
pprint(fruits)
```
</details>

実行結果

```
[{'name': 'apple', 'price': 100},
 {'name': 'orange', 'price': 200},
 {'name': 'melon', 'price': 1000}]
```

### ラムダ式（lambda expression）による関数の定義

上記の __`keyfunc`__ という __関数__ は、__12 行目のキーワード引数でしか利用されません__。__一度しか利用しない関数__ を上記のように __定義するのは記述が面倒__ なので、Python ではこのような関数を __ラムダ式__ という記述方法で __簡潔に記述__ することができるようになっています。

__ラムダ式__ は、下記のように記述して定義する __関数__ で、ラムダ式を __変数やキーワード引数に直接代入__ することができます。__仮引数__ の部分は通常の関数と同様の方法で __() で囲わずに記述__ します。また、__文の所__ には __1 つの文だけを記述__ することができます。

```pyhon
lambda 仮引数: 文
```

上記のラムダ式は __下記のような関数を定義__ したのと同じ意味を持ちます。ただし、ラムダ式で定義した関数を `<lambda>()` のような方法で呼び出すことはできないので、__必ず変数やキーワード引数に代入する必要__ があります。

```python
def <lambda>(仮引数):
    return 文
```

先程のプログラムはラムダ式を利用することで、下記のプログラムのように簡潔に記述することができます。先ほどの __`keyfunc` の定義__ が 7 行目の __`lambda fruits: fruits["price"]`__ という __ラムダ式で記述__ されています。

```python
1  fruits = [
2      { "name": "orange", "price": 200},
3      { "name": "melon", "price": 1000},
4      { "name": "apple", "price": 100},
5  ]
6  
7  fruits.sort(key=lambda fruit: fruit["price"])
8  pprint(fruits)
```

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

```python
fruits = [
    { "name": "orange", "price": 200},
    { "name": "melon", "price": 1000},
    { "name": "apple", "price": 100},
]

fruits.sort(key=lambda fruit: fruit["price"])
pprint(fruits)
```
</details>

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

```diff_python
fruits = [
    { "name": "orange", "price": 200},
    { "name": "melon", "price": 1000},
    { "name": "apple", "price": 100},
]

-def keyfunc(fruit):
-   return fruit["price"]

-fruits.sort(key=keyfunc)
+fruits.sort(key=lambda fruit: fruit["price"])
pprint(fruits)
```
</details>

実行結果

```
[{'name': 'apple', 'price': 100},
 {'name': 'orange', 'price': 200},
 {'name': 'melon', 'price': 1000}]
```

:::note warn
__ラムダ式__ はこのように、__以下のような条件を満たす関数を定義__ する際に __良く使われる__ ので、覚えておくと便利です。

* プログラムの中で __一度しか呼び出されない__
* 関数が行う処理を __1 つの文で記述できる__
* 1 つの文が行った計算結果を __返り値として返す__
:::

ラムダ式の詳細については、下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/tutorial/controlflow.html#lambda-expressions

:::note
組み込み関数 `max` や `min` でも上記と同様の キーワード引数 `key` を記述することで、数値以外のデータの最大値や最小値を計算することが出来ます。

下記は、先程と同じデータの中の最も値段の高い果物を表示するプログラムです。

```python
fruits = [
    { "name": "orange", "price": 200},
    { "name": "melon", "price": 1000},
    { "name": "apple", "price": 100},
]

print(max(fruits, key=lambda fruit: fruit["price"]))
```

実行結果

```
{'name': 'melon', 'price': 1000}
```
:::

### Mbtree クラスの `sort_children_by_worst_score` メソッドの定義

__すべてのノード__ に対して __`children`__ 属性の要素を、__max ノードでは評価値の低い順__、__min ノードでは評価値の高い順__ で __並べ替える__ 処理を行う __`sort_children_by_worst_score`__ というメソッドを Mbtree クラスに定義する事にします。下記はそのメソッドの定義です。最善手（best move）と逆の順で並べ替えるので最悪（worst）を名前に入れました。

* __5 行目__：〇 の手番の max ノードの場合は評価値の小さい順、× の手番の min ノードの場合は大きい順で並べ替える必要があるので `sort` メソッドのキーワード引数に記述する値をそのように計算する
* __6 行目__：list の `sort` メソッドに、要素の `score` 属性を取り出して返す関数をラムダ式を利用して定義し、3 行目で計算した順番でソートする

```python
1  from marubatsu import Marubatsu
2
3  def sort_children_by_worst_score(self):
4      for node in self.nodelist:
5          reverse = False if node.mb.turn == Marubatsu.CIRCLE else True
6          node.children.sort(key=lambda childnode: childnode.score, reverse=reverse)
7      
8  Mbtree.sort_children_by_worst_score = sort_children_by_worst_score
```

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

```python
from marubatsu import Marubatsu

def sort_children_by_worst_score(self):
    for node in self.nodelist:
        reverse = False if node.mb.turn == Marubatsu.CIRCLE else True
        node.children.sort(key=lambda childnode: childnode.score, reverse=reverse)
    
Mbtree.sort_children_by_worst_score = sort_children_by_worst_score
```
</details>

先程の `mbtree` の各ノードの評価値は αβ 法の計算処理によって正しくない値が計算されている場合があるので、上記の定義後に下記のプログラムでゲーム木を作成し __`sort_children_by_worst_score`__ で子ノードの順番を並べ変えたゲーム木に対して __`calc_score_by_ab`__ を呼び出すと、__割合__ が実行結果のように何もしない場合の 3.3 % と比べて __10 倍以上の 36.2 % という値になる__ ことがわかります。

```python
mbtree = Mbtree(algo="df")
mbtree.sort_children_by_worst_score()
mbtree.calc_score_by_ab(mbtree.root, debug=True)
```

実行結果

```
計算したノードの数 198837
枝狩りしたノードの数 351109
合計 549946
割合 36.2%
```

また、この結果から __〇×ゲームのゲーム木__ の場合は __最悪の場合__ でも αβ 法を利用することでミニマックス法の __1/3 の時間で処理を行うことができる__ ことが確認できました。

# 今回の記事のまとめ

今回の記事では、__αβ 法の処理の効率の性質__ について説明し、__最善手の着手が行われた子ノードの評価値を最初に計算する__ ことで、__最も多くの枝狩りを行うことが出来る__ ことを示しました。また、__ある程度の精度を持つ AI を利用__ することで、αβ 法の __処理の効率を大幅に改善できる__ ことを示しました。

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

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

# 次回の記事

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

[^1]:あらかじめ知ることができているのであれば、αβ 法を行わなくても子ノードの評価値の最大値（または最小値）を計算することで即座に評価値の計算を行うことができます
[^2]:本当にそうであるかどうかについて知りたい場合は実際に検証する必要がありますが、特に重要ではないと思いますので本記事では検証はしません。興味がある方は実際に検証してみると良いでしょう
[^3]:tuple に `sort` メソッドが存在しないのはそのためです
[^4]:そのことは [`sorted` の公式ドキュメント](https://docs.python.org/ja/3/library/functions.html#sorted)に記述されています
[^5]:今回の記事では紹介しませんが、特殊メソッドを定義する事で < 演算子で比較することができるようになり、その場合は `sort` メソッドで比較できるようになります