Pythonで〇×ゲームのAIを一から作成する　その149　 Mbtree_Anim を用いた αβ 法による評価値の計算手順と差分データの確認方法のまとめ

# 目次と前回の記事

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

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

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

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

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

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

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

# 今回の記事の内容

前回の記事ではフレーム間の差分のデータを表示するように Mbtree_Anim を改良することで、枝狩りが行われた際に計算が省略されたノードの数を確認できるようにしましたが、__差分データを表示__ することで __他の様々な情報を得ることができます__。

また、前回の記事で筆者が実装したかった Mb_Anim の機能が完成しました。そこで、今回の記事では __Mbtree_Anim__ で __αβ 法による評価値の計算手順__ と、枝狩りが行われた数などの __様々な差分情報を確認する方法をまとめる__ ことにします。

# αβ 法で評価値を計算したゲーム木の作成と Mbtree_Anim での表示のおさらい

まず最初に、__αβ 法で評価値を計算したゲーム木__ を下記の手順で __作成する__ 必要があります。

1. __実引数に `algo="df"` を記述__ して、深さ優先アルゴリズムでゲーム木を作成する
2. 評価値を計算したいノードを実引数に記述して __`calc_score_by_ab`__ メソッドを実行し、αβ 法で評価値を計算する。その際にキーワード引数 [`shortest_victory`](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95%E3%81%AE%E5%A4%89%E6%9B%B4) を記述するこで、最短の勝利を優先した評価値を計算するかどうかを設定することができる

例えばルートノードの αβ 法による評価値を、最短の勝利を優先しない場合とする場合で計算するには下記のようなプログラムを実行します。

```python
from tree import Mbtree

mbtree = Mbtree(algo="df")
mbtree.calc_score_by_ab(mbtree.root)

mbtree_sv = Mbtree(algo="df", shortest_victory=True)
mbtree_sv.calc_score_by_ab(mbtree_sv.root)
```

:::note
手順 1 で `algo="df"` を記述する必要があるのは、Mbtree_Anim ではゲーム木が幅優先アルゴリズムで作成されている場合は、[以前の記事](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E7%94%9F%E6%88%90%E3%81%AE%E9%81%8E%E7%A8%8B%E3%81%AE%E3%82%A2%E3%83%8B%E3%83%A1%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E4%BF%AE%E6%AD%A3)で説明した理由から __ゲーム木の部分木の中心となるノード__ を __選択されたノードの親ノードに設定__ しているからです。下記の 4 ~ 6 行目がその処理を行う `update_gui` メソッドのプログラムです。

```python
1  def update_gui(self):
略
2      self.selectednode = self.nodelist[self.play.value]
3      self.centernode = self.selectednode
4      if self.mbtree.algo == "bf":
5          if self.centernode.depth > 0:
6              self.centernode = self.centernode.parent
```

αβ 法は深さ優先アルゴリズムで評価値の計算を行うため、`algo="bf"` で作成されたゲーム木の場合は、アニメーションがわかりづらくなります。
:::

## 作成したゲーム木のデータの保存

ゲーム木の作成には 30 秒以上の時間がかかるので、下記のプログラムを実行して __作成したゲーム木のデータを[ファイルに保存](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#mbtree-%E3%81%AE%E3%82%A4%E3%83%B3%E3%82%B9%E3%82%BF%E3%83%B3%E3%82%B9%E3%81%AE%E4%BF%9D%E5%AD%98%E3%81%A8%E8%AA%AD%E8%BE%BC)__ することにします。__αβ 法__ で __ルートノードの評価値を計算__ したデータなのでファイル名は  abtree_root と abtree_sv_root としました。

```python
mbtree.save("../data/abtree_root")
mbtree_sv.save("../data/abtree_sv_root")
```

実行結果

```
save completed.
save completed.
```

:::note
2025/01/25：修正

上記の 2 行目が `mbtree.save("../data/abtree_sv_root")` と間違って記述されていたので修正しました。それに伴い `data` フォルダの abtree_sv_root.mbtree を更新したので、2025/01/25 以前に data フォルダのデータをダウンロードした方は、ダウンロードし直してください。
:::

データをファイルに保存することで、下記のプログラムでファイルからゲーム木のデータを、__ゲーム木を作成するよりも短い時間__ で読み込むことができるようになります。

```python
mbtree = Mbtree.load("../data/abtree_root")
```

## Mbtree_Anim での表示

次に、下記のプログラムのように __実引数__ に上記で作成した __ゲーム木のデータ__ と、__キーワード引数 `isscore=True`__ を記述して __Mbtree_Anim を呼び出す__ と、実行結果のような画面が描画されます。今回の記事では下記で表示した Mbtree_Anim での説明を行います。

```python
from tree import Mbtree_Anim

Mbtree_Anim(mbtree, isscore=True)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/221a0a2d-42f9-be90-4c66-37984e287dc7.png" width="500">

図の __数直線の部分の表示__ や __背景色の意味__ について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/fd421d90cd1f47e38cdb)を復習して下さい。__ゲーム木のノードの表示の色__ について忘れた方は[以前の記事](https://qiita.com/ysgeso/items/289c8067774951433941)を復習して下さい。


# 様々な情報の確認方法

__Mbtree_Anim__ を利用して __αβ 法に関する様々な情報を確認する方法__ について説明します。

## αβ 法での評価値の計算手順の確認方法

上段の左にある下図のボタンによって、__αβ 法での評価値の計算手順__ の __アニメーションの表示、停止、自動ループ__[^1]の操作を行うことができます。また、上段の右にある interval の IntSlider によってアニメーションの描画速度を調整することができます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a332632e-77b5-8199-8749-5ff16dcf47d9.png" width="150">

また、下記の表のウィジェットで __フレームを手動で移動__ することができます。

|  | 操作 |
|:--|:--|
| __上段の < と >__  |  フレームを前後に移動する |
| __上段の frame の__<br>__IntSlider__ |  つまみをドラッグしてフレームを移動する<br>つまみ以外の場所をクリックしてフレームを移動する<br>右の数値をクリックし、フレームを入力して移動する |
| __下段の <<__  | 選択中のノードの処理が開始されたフレームに移動  |
| __下段の <__  | 選択中のノードの前の子ノードの評価値が計算されたフレームに移動  |
| __下段の >__  | 選択中のノードの次の子ノードの評価値が計算されたフレームに移動  |
| __下段の >>__  | 選択中のノードの評価値が確定したフレームに移動  |

## 複数のボタンの操作によるフレームの移動

__複数のボタンの操作を組み合わせる__ ことによって、__下記のフレームに移動__ することができます。なお、下記のフレームに移動するために複数のボタンをクリックするのが面倒だと思った方は、下記の操作を行うためのボタンを用意すると良いでしょう。

### 選択中のノードの子ノードの計算を開始するフレームへの移動

選択中のノードの __子ノードの計算を開始するフレームへの移動__ は以下の操作で行います。

* __最初の子ノード__ の計算を開始するフレームへの移動
__&lt;&lt; ボタン__ をクリック[^2]して選択中のノードの処理を開始するフレームに移動した後で __> ボタン__ をクリックする。
* __それ以外の子ノード__ の計算を開始するフレームへの移動
    * __下段の < または > ボタン__ をクリックして移動したい子ノードの __一つ前の子ノードの評価値が計算されたフレームに移動__ する
    * 上段の __&gt; ボタンを 2 回クリック__ して 2 つ後のフレームに移動する[^3]

具体例を挙げて説明します。下図左の __ルートノード__ の __3 番目の子ノードの計算を開始するフレームへ移動__ するためには、__下段の > ボタンを 2 回クリック__ して下図右の __2 番目の子ノードの評価値が計算されたフレームに移動__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7326948e-fbf3-ab6e-4dea-374566138181.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0f6ea50a-4a53-b7fa-0c8d-4512b2410a60.png" width="300">

その後 __上段の > ボタンを 2 回クリック__ すると、下図のようにルートノードの 3 番目の子ノードの評価値の計算を開始するフレームに移動できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a7687567-eca0-0858-0b05-a3e239f12123.png" width="300">

### 親ノードの処理を行うフレームへの移動

__親ノードの処理を行うフレームへの移動__ は __以下の 2 種類__ の方法があります。下記の説明で表記している背景色の色の意味を忘れた方は[以前の記事](https://qiita.com/ysgeso/items/fd421d90cd1f47e38cdb#%E3%83%95%E3%83%AC%E3%83%BC%E3%83%A0%E3%81%A7%E8%A1%8C%E3%82%8F%E3%82%8C%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E6%98%8E%E7%A2%BA%E5%8C%96)を復習して下さい。

* 親ノードでの __選択中のノードの計算を開始する直前のフレーム__ への移動
__下段の << ボタン__、__上段の < ボタン__ の順でクリックする

具体例を挙げます。下図左の 4673 フレーム目で __<< ボタンをクリック__ すると、__赤枠のノード__ の __計算を開始__ する下図右の __背景色が白色__ の 4490 フレーム目に移動します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/77877d84-5f5e-e8dc-6a11-f30e3859d4fc.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/99c02e15-3e6a-05df-fd09-7d4233f55e1b.png" width="300">

その後で __< ボタンをクリック__ すると下図のように、上図の赤枠の __親ノードが選択__ された 4489 フレーム目に移動します。また、このフレームは __上図の赤枠のノードの処理を計算する直前__ のフレームです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/27f5f2cd-983c-1971-a84d-4c9369113516.png" width="300">

:::note
元のノードが親ノードの __最初の子ノード__ の場合は、__親ノードの計算を開始__ する __背景が白色__ のフレームに移動します。そうでない場合は上図のように α 値または β 値の更新が行われる __背景色が水色__ のフレームに移動します。
:::

* 親ノードで __選択中のノードの評価値が計算されたフレーム__ への移動
__下段の >> ボタン__、__上段の > ボタン__ の順でクリックする

下図左の 4673 フレーム目で __>> ボタンをクリック__ すると、__赤枠のノード__ の __評価値が確定__ した下図右の __背景色が薄紫色__ の 4675 フレーム目に移動します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/77877d84-5f5e-e8dc-6a11-f30e3859d4fc.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/84bd7e82-c89c-2863-4db4-e0aeb6bce588.png" width="300">

その後で __> ボタンをクリック__ すると下図のように、上図の赤枠の __親ノードが選択__ された 4476 フレーム目に移動します。また、このフレームは __上図の赤枠のノードの評価値が計算__ された __背景色が薄黄色__ のフレームです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a40f1ab6-f0da-bc05-910d-b79f024756c2.png" width="300">

## 様々な差分データの確認方法

下記の操作を行うことで __様々な差分データを確認__ することができます。

### αβ 法で評価値を計算した際の差分データの表示

上部の __frame の IntSlier__ をドラッグして __0 フレーム目を表示__ してから、__下段の >> ボタンをクリック__ することで下図のような __最後のフレームに移動__ することができます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f92b3ebd-3202-5628-2c24-8b020e1b6838.png" width="500">

その際に表示される __差分データ__ は、上から __αβ 法で評価値を計算した際__ の下記のデータが表示されます。

* __評価値の計算__ が行われたノードの数
* __枝狩り__ が行われたノードの数
* 評価値の計算を行ったノードをルートノードとする部分木の __ノードの総数__
* 評価値の計算が行われたノードの数の __割合__

:::note
0 フレーム目を表示した後で __IntSlider をドラッグして最後のフレームに移動__ するという方法では差分データの表示の部分に __0 フレーム目からの差分データが表示されません__。その理由は、[前回の記事](https://qiita.com/ysgeso/items/f8fe755341b3cff2d770#intslider-%E3%81%AE%E6%93%8D%E4%BD%9C%E3%81%AB%E3%82%88%E3%81%A3%E3%81%A6%E8%A1%8C%E3%82%8F%E3%82%8C%E3%82%8B%E5%87%A6%E7%90%86)で説明したように、IntSlider を __ドラッグして移動__ すると必ず __ドラッグ途中のフレームが表示されてしまう__ ため 0 フレーム目ではなく __そのフレームとの差分が表示__ されてしまうからです。

ただし、0 フレーム目からの差分は左の __合計のデータを見ればよい__ ので、IntSlider をドラッグして最後のフレームを表示しても良いでしょう。
:::

### 特定のノードの評価値を計算した際の差分データの表示

__特定のノードの評価値を計算__ した際の __差分データ__ は、下記の手順で表示できます。

1. __差分データを計算したいノード__ を __選択状態__ にする
2. __<< ボタンをクリック__[^2]してそのノードの __計算を開始するフレームに移動__ する
3. __&gt;&gt; ボタンをクリック__ してそのノードの __評価値の計算が確定したフレームに移動__ する

下図左の 4673 フレーム目の __赤枠のノードの評価値を計算した際の差分データを表示__ するためには __<< ボタンをクリック__ して下図右の赤枠のノードの __計算を開始したフレームに移動__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/77877d84-5f5e-e8dc-6a11-f30e3859d4fc.png" width="300">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/99c02e15-3e6a-05df-fd09-7d4233f55e1b.png" width="300">

__&gt;&gt; ボタンをクリック__ すると下図の赤枠の __評価値が確定したフレームに移動__ し、__上図右のフレームとの差分__ が表示されます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c5c62cd0-a880-aa10-169c-a88845f0231b.png" width="500">

上図から __赤枠のノードの評価値を計算した際__ に以下の処理が行われた事がわかります。

* 評価値の計算が行われたノードの数は 47 である
* 枝狩りが行われたノードの数は 8185 である
* 赤枠のノードをルートノードとする部分木には 8232 のノードがある
* 評価値の計算が行われたノードの数の割合は 0.6 % である

上図では赤枠の __いくつかの子ノードが暗く表示されて枝狩りが行われている__ ことがわかりますが、上記の枝狩りが行われたノードの数の __+8185 は__ 上図の __暗く表示されているノードの子孫ノードの合計であるとは限らない__ 点に注意が必要です。具体的には上図の赤枠の __最初の子ノードは枝狩りが行われていません__ が、上図では __表示が省略__ されている __最初の子ノードの子孫ノードの中__ に __枝狩りが行われているノードが存在する可能性__ があります。

実際に上図の赤枠の最初の子ノードを選択状態にし、<<、>> の順でボタンをクリックすると、下図のように __このノードの評価値を計算する際__ に、下図に __表示されていない 973 個の子孫ノードの枝狩りが行われている__ ことが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/cd4af4bd-78bc-2a07-4fa7-2642c5718a5c.png" width="500">

従って、この方法では選択中のノードの __全ての子孫ノード__ の中で __評価値が計算されたノードの数__ と、__枝狩りが行われたノードの数__ が計算されて表示されます。

### 選択中のノードの子ノードの評価値を計算した際の差分データの表示

選択中のノードの __子ノードの評価値を計算した際の差分データ__ の表示は、__下段の > ボタンをクリック__ することで行えます。下記に具体例を挙げて説明します。

下記は 102 フレーム目の図で、__赤枠のノードの計算が開始されたフレーム__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f5584a66-d281-ba2b-5c59-e3567d23cbdd.png" width="500">

__下段の > ボタン__ をクリックすると __最初の子ノードの評価値の計算__ が行われ、下図のような表示が行われます。__上図と比較__ して赤枠の最初の子ノードとその子孫ノードが __5 つ明るく表示される__ ようになっているので __5 つのノードの評価値の計算が行われた__ ことがわかります。また、枝狩りが行われたことを表す __暗いノードの数が増えていない__ ことから、__枝狩りが行われなかった__ ことがわかります。そのことは __差分のデータ__ の __計算済に +5__ が、__枝狩りに +0__ が表示されていることからも確認することができます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c59b8030-4a00-8372-c127-f3c90d92f254.png" width="500">

続けて __下段の > ボタン__ をクリックすると __次の子ノードの評価値の計算__ が行われ、下図のような表示が行われます。__明るく表示__ されるようになった __ノードの数は 1 つ__ で __暗いノードの数が増えていない__ ことと、__差分のデータ__ にそのことを表す __計算済に +1__ と __枝狩りに + 0__ が表示されることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/aa097ae2-9076-bafe-1728-4fac029643ad.png" width="500">

上図では __「β 狩り」が赤く表示される__ ので、__残りの子ノードは枝狩り__ が行われます。実際に __下段の > ボタン__ をクリックすると、下図のように残りの子ノードの子孫ノードが __5 つ暗い色で表示__ されて __枝狩りが行われた__ ことが確認できます。また、下図のフレームでは __赤枠のノードの評価値が確定する__ ので、__1 つのノードの評価値が計算__ されます。従って __差分のデータ__ にそのことを表す __計算済に +1__ と __枝狩りに + 5__ が表示されることが確認できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/fb8916d3-a7f9-142d-c585-f638282a088e.png" width="500">

上記をまとめると、__下段の > ボタンをクリック__ した際には __下記のような差分の表示__ が行われます。

* 次の子ノードの __枝狩りが行われない__ 場合は、__次の子ノードを計算した際の差分のデータ__ が表示される
* 次の子ノードの __枝狩りが行われる__ 場合は、__計算済に__ 選択されたノードの評価値が計算されたことを表す __+ 1__ が、枝狩りに __枝狩りが行われたノードの数__ が表示される

# 今回の記事のまとめ

今回の記事では Mbtree_Anim での αβ 法による評価値の計算手順と差分データの確認方法のまとめを行いました。

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/149/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [abtree_root.mbtree](https://github.com/ysgeso/marubatsu/blob/master/data/abtree_root.mbtree)  | 本記事でファイルに保存した αβ 法で最短の勝利を優先しない評価値を計算したゲーム木のファイル  |
| [abtree_sv_root.mbtree](https://github.com/ysgeso/marubatsu/blob/master/data/abtree_sv_root.mbtree)  | 本記事でファイルに保存した αβ 法で最短の勝利を優先する評価値を計算したゲーム木のファイル  |

# 次回の記事

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

| 更新日時 | 更新内容 |
|:--|:--|
| 2025/01/25 | mbtree_sv をファイルに保存する処理が間違っていた点を修正しました |

[^1]:自動ループとは、アニメーションの最後のフレームが表示された後で、自動的に最初のフレームにアニメーションが戻る事です
[^2]:現在のフレームが選択中のノードの処理を開始するフレームの場合はこの操作を行う必要はありません
[^3]:&gt; ボタンを 1 回だけクリックすると α 値または β 値を更新するフレームに移動します