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

目次と前回の記事

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

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

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
test.py	テストに関する関数
util.py	ユーティリティ関数の定義。現在は gui_play のみ定義されている
tree.py	ゲーム木に関する Node、Mbtree クラスの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

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

今回の記事の内容

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

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

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

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

1. 実引数に algo="df" を記述 して、深さ優先アルゴリズムでゲーム木を作成する
2. 評価値を計算したいノードを実引数に記述して calc_score_by_ab メソッドを実行し、αβ 法で評価値を計算する。その際にキーワード引数 shortest_victory を記述するこで、最短の勝利を優先した評価値を計算するかどうかを設定することができる

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

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)

手順 1 で algo="df" を記述する必要があるのは、Mbtree_Anim ではゲーム木が幅優先アルゴリズムで作成されている場合は、以前の記事で説明した理由から ゲーム木の部分木の中心となるノード を 選択されたノードの親ノードに設定 しているからです。下記の 4 ~ 6 行目がその処理を行う update_gui メソッドのプログラムです。

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 秒以上の時間がかかるので、下記のプログラムを実行して 作成したゲーム木のデータをファイルに保存 することにします。αβ 法 で ルートノードの評価値を計算 したデータなのでファイル名は abtree_root と abtree_sv_root としました。

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

実行結果

save completed.
save completed.

2025/01/25：修正

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

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

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

Mbtree_Anim での表示

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

from tree import Mbtree_Anim

Mbtree_Anim(mbtree, isscore=True)

実行結果

図の 数直線の部分の表示 や 背景色の意味 について忘れた方は以前の記事を復習して下さい。ゲーム木のノードの表示の色 について忘れた方は以前の記事を復習して下さい。

様々な情報の確認方法

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

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

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

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

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

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

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

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

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

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

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

　

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

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

親ノードの処理を行うフレームへの移動 は 以下の 2 種類 の方法があります。下記の説明で表記している背景色の色の意味を忘れた方は以前の記事を復習して下さい。

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

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

　

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

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

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

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

　

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

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

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

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

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

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

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

0 フレーム目を表示した後で IntSlider をドラッグして最後のフレームに移動 するという方法では差分データの表示の部分に 0 フレーム目からの差分データが表示されません。その理由は、前回の記事で説明したように、IntSlider を ドラッグして移動 すると必ず ドラッグ途中のフレームが表示されてしまう ため 0 フレーム目ではなく そのフレームとの差分が表示 されてしまうからです。

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

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

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

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

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

　

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

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

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

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

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

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

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

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

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

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

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

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

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

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

今回の記事のまとめ

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

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

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
abtree_root.mbtree	本記事でファイルに保存した αβ 法で最短の勝利を優先しない評価値を計算したゲーム木のファイル
abtree_sv_root.mbtree	本記事でファイルに保存した αβ 法で最短の勝利を優先する評価値を計算したゲーム木のファイル

次回の記事

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

1. 自動ループとは、アニメーションの最後のフレームが表示された後で、自動的に最初のフレームにアニメーションが戻る事です ↩

2. 現在のフレームが選択中のノードの処理を開始するフレームの場合はこの操作を行う必要はありません ↩ ↩²

3. > ボタンを 1 回だけクリックすると α 値または β 値を更新するフレームに移動します ↩