Pythonで〇×ゲームのAIを一から作成する　その157　ミニマックス法の視覚化の検討と視覚化に必要なデータの記録

Last updated at 2025-03-17Posted at 2025-03-09

目次と前回の記事

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

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

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

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

置換表付き αβ 法の視覚化を行う方法の検討

前回の記事で、置換表付き αβ 法での評価値の計算手順を視覚化するためのデータを作成する calc_score_for_anim を作成しましたので、次はそのデータを利用して Mbtree_Anim で視覚化を行う処理を実装 する必要があります。なお、Mbtree_Anim の下部に表示されるゲーム木の表示の部分は calc_score_by_ab と calc_score_for_anim のどちらで計算した場合でも表示する内容は同じなので、実装するのはその 上部に表示 する α 値、β 値や計算したノードの数などの アニメーションのフレームの情報を表示する部分 です。

実装方法の選択

Mbtree_Anim は calc_score_by_ab で作成されたデータを利用して視覚化を行うように作られていますが、calc_score_for_anim ではそれとは異なるデータを作成する ので、以下のいずれかを行う必要 があります。

Mbtree_Anim を修正 して calc_score_for_anim で作成したデータに対する視覚化を行うことができるようにする
Mbtree_Anim とは別の calc_score_for_anim で作成したデータに対する視覚化を行う クラスを定義 する

前者の方法 の場合は、互換性を重視して calc_score_by_ab と calc_score_for_anim の 両方で作られたデータに対応 するか、互換性を捨てて calc_score_by_ab で作られたデータを 利用できないようにするか を決める必要があります。

互換性を重視 する場合は、過去に calc_score_by_ab で作成した ../data/abtree_root.mbtree 等の データを引き続き利用できる という利点がありますが、両方のデータに対応できるようにするために プログラムが複雑になる という欠点があります。互換性を重視しない場合はその逆の性質を持ちます。

後者の方法 の場合は、calc_score_by_ab で作成したデータは引き続き Mbtree_Anim で利用でき、新しく作成するクラスは calc_score_for_anim で作成したデータだけに対応すればよいので プログラムが複雑にならない という利点がありますが、Mbtree_Anim と 大部分が似た新しいクラスを定義しなければならない という欠点があります¹。

どの方法にも一長一短がありますが、本記事では 互換性を重視 して calc_score_by_ab と calc_score_for_anim の 両方で作られたデータに対応する ように Mbtree_Anim を修正する という方法をとることにします。理由の一つとしては、実際にその方法で実装してみたところ、思っていたほとはプログラムが複雑にならなかったためです。ただ、人によっては感じ方が異なると思いますので、他の方法で実装したい人は自分がもっともふさわしいと思った方法で実装してみて下さい。

`calc_score_for_anim` が行うことができる計算の種類

calc_score_for_anim は置換表付き αβ 法だけでなく、下記のような 様々な条件で評価値を計算 することができるので、Mbtree_Anim がそれらの 全ての場合で適切な視覚化を行う 必要があります。なお、括弧の中に対応する仮引数を記述しました。

アルゴリズムとして ミニマックス法 と αβ 法 のいずれかを選択できる（仮引数 minimax）
置換表を利用するか どうかを選択できる（仮引数 use_tt）
最短の勝利を目指す評価値を計算するか どうかを選択できる（仮引数 shortest_victory）
ルートノードの α 値と β 値の初期値 を評価値の最小値と最大値に設定するかどうかを選択できる（仮引数 init_ab）

4 種類の True か False を選択する設定があるので合計 $2^4 = 16$ 通りの設定 があります。

現状の Mbtree_Anim の問題点の考察

それぞれの場合の表示方法を検討するために、現状の Mbtree_Anim の問題点を考察 することにします。

Mbtree_Anim は もともと置換表を利用しない αβ 法 での評価値を計算する手順を 視覚化するために作成 したクラスです。それを 後から ミニマックス法の視覚化や、置換表を利用した場合などの 視覚化を行えるように修正 したのですが 視覚化の方法 が、下記のように あまりわかりやすいとは言えない という問題があります。

どのような条件で評価値が計算されているか が表示されていないので わかりづらい
例えば ミニマックス法 で評価値を計算した場合でも 実際にはミニマックス法では利用しない α 値と β 値が常に表示される ため、表示している内容がミニマックス法で計算されたデータなのか、αβ 法で計算されたデータであるかの 区別がつけづらい
置換表が利用されているかどうかなどの 他の条件 も、見た目から 判別しづらい

また、現時点で Mbtree_Anim が処理を行うことができる calc_score_by_ab で作成されたデータは αβ 法で置換表を利用する場合 は置換表付き αβ 法ではなく、(局面, α 値の初期値, β 値の初期値) という 3 つのデータをキーとする dict による置換表 で処理を行っているので、以下のように置換表付き αβ 法での処理を 正しく視覚化することはできません。

置換表付き αβ 法の視覚化で必要となる下記の表示が行われない
- fail low、exact value、fail high の範囲の表示の色分けが行われない。なお、現状の Mbtree_Anim が行う α 値と β 値による 範囲の色分け は α 値と β 値の初期値ではなく、子ノードの評価値によって 初期値から変化した可能性がある α 値と β 値による色分け なので、fail low、exact value、fail high の範囲で 色分けが行われない場合がある
- 置換表付き αβ 法が行う置換表に関する処理の表示が行なわれない
calc_score_by_ab では、α 値または β 値をノードの評価値として計算しているが、calc_score_for_anim では ノードの評価値を α 値や β 値とは別に計算 する。現状の Mbtree_Anim ではその表示に対応していない

実装の手順の検討

問題点がある程度明確になった ので、それらの問題点を解決するような 表示方法を検討する ことにします。先ほど 16 通りの設定があると説明しましたが、16 通りの設定に対する表示方法を一度に考えるのは大変 なので、本記事ではミニマックス法と αβ 法の それぞれの場合に分けて表示方法を検討する ことにします。

具体的には下記の手順で実装を行います。今回の記事では下記の手順 1、2 を行い、手順 3 以降は次回以降の記事で実装することにします。

ミニマックス法 での 視覚化の方法を検討 する
検討した 視覚化を行うために必要なフレームのデータを記録 するように calc_score_for_anim を修正 する
Mbtree_Anim を 検討した視覚化を行うように 修正する
αβ 法で上記の 1 ~ 3 の手順を行う

ミニマックス法の視覚化の検討

ミニマックス法での視覚化をどのように行えば良いかについて少し考えてみて下さい。

ミニマックス法での視覚化の種類

先程 calc_score_for_anim は下記の 4 つの条件で評価値を計算できると説明しました。

アルゴリズムとして ミニマックス法 と αβ 法 のいずれかを選択できる（仮引数 minimax）
置換表を利用するか どうかを選択できる（仮引数 use_tt）
最短の勝利を目指す評価値を計算するか どうかを選択できる（仮引数 shortest_victory）
ルートノードの α 値と β 値の初期値 を評価値の最小値と最大値に設定するかどうかを選択できる（仮引数 init_ab）

ただし、ミニマックス法では α 値と β 値を利用しない ので、ミニマックス法の場合で 設定できる条件 は下記の 2 種類だけ です。従って、組み合わせ は $2^2 = 4$ 通りです。

置換表を利用するか どうかを選択できる（仮引数 use_tt）
最短の勝利を目指す評価値を計算するか どうかを選択できる（仮引数 shortest_victory）

設定された条件の表示

先程考察したように、現状の Mbtree_Anim では どのような条件で評価値が計算されているかがわかりづらい という問題があるので、以下の方法でそれらを明確にすることにします。

「ミニマックス法　置換表〇　最短 ×　初期値〇」のように、「アルゴリズムの種類」、「置換表を利用しているかどうか」、「最短の勝利を目指す評価値を計算するかどうか」、「ルートノードの α 値と β 値を評価値の最小値と最大値で初期化するかどうか」について 設定された条件を表示 する
ミニマックス法 では α 値と β 値を利用しないので 「初期値〇」の部分は表示しない

さらに、下記の方法で 設定された条件が明確になる ような 工夫を行う ことにします。

ミニマックス法と αβ 法での表示の区別

下記の方法で、ミニマックス法と αβ 法のどちらで計算が行われたか を一目で区別できるようにするという工夫を行ないます。

現状の Mbtree_Anim では常に α 値と β 値を表示するが、ミニマックス法 ではそれらの値は利用しないので α 値と β 値を表示しない ようにする
同様の理由で、ミニマックス法 では α 値と β 値による 評価値の範囲の色分けを行わない ようにする

最短の勝利を目指す評価値を計算しているかどうかの表示の区別

現状の Mbtree_Anim では、常に評価値の 数直線の範囲 が正負の無限大と -2 ~ 3 の範囲 になっていますが、最短の勝利を目指さない場合 は数直線の範囲を正負の無限大と -1 ~ 1 の範囲とする ことで一目で区別できるようにするという工夫を行ないます。

以後の説明に関する補足

上記の工夫について毎回記述するのは大変なので、以後の検討では これらの工夫による表示が行われるという前提 で行います。

それぞれの状態での表示の検討

次に、ミニマックス法での "start"、"tt"、"score"、"update"、"end" の 5 つのそれぞれの状態のフレーム に対して、どのような表示を行うか について検討する必要があります。どのように表示すれば良いかについて少し考えてみて下さい。

共通する表示内容の検討

最初に、すべての場合で 共通する表示内容 について検討することにします。

評価値を表示する 数直線は必ず表示する必要 があります。ただし、数直線の範囲は先ほど説明したように最短の勝利を目指す評価値を計算するかによって変化する可能性があります。

現状の Mbtree_Anim では、真ん中の上の行に「深さ 0 max node 処理の開始」のように、「選択中のノードの深さ」、「ノードの種類」、「フレームで行われる処理を表す状態」を表す内容が表示されます。これは すべての場合で表示したほうが良い情報 なので、常に表示する ことにします。なお、他の表示内容とのバランスを考えて、表示位置を現状の Mbtree_Anim から変更する可能性はあります。

右に表示される「計算済」や「枝狩り」などの、枝狩りが行われたノードの数などの表示 も常に表示したほうが良い情報です。また、calc_score_by_ab と calc_score_for_anim で表示する内容を 変える必要は特にない ので、現状の Mbtree_Anim と同じ内容を表示 することにします。

以後は、上記の情報を常に表示するという前提で説明を行います。

条件による表示の違いの検討

先程説明したように、ミニマックス法では下記の 2 種類の条件で評価値を計算することができます。

置換表を利用するか どうかを選択できる（仮引数 use_tt）
最短の勝利を目指す評価値を計算するか どうかを選択できる（仮引数 shortest_victory）

5 つの状態の中で、置換表を利用するかどうか によって 行う処理が変わる のは "tt" と "end" の状態のフレームだけで、以下のように異なります。従って、"end" のフレームの表示のみ、置換表を利用するかどうかで 表示が変わる場合があります。

"tt" のフレームの処理は 置換表を利用する場合のみ 行なわれる
"end" のフレームの処理では、置換表を利用する場合のみ 計算したノードの評価値を 置換表に登録する処理が行われる 場合がある

最短の勝利を目指す評価値を計算するかどうか によって変わるのは、決着がついたノードの評価値の計算方法だけ で、それ以外の処理は全く変わりません。そのため、5 つの状態の表示方法は、先程説明した 数直線の表示範囲を変えるという工夫以外 では 共通します。

上記の考察を元に、5 つのそれぞれの状態での表示方法を検討することにします。

"start" の状態の表示

ノードの処理の開始 を表す "start" の状態のフレームでは、常に表示する内容を除いて 特に何かを表示する必要はない でしょう。

"tt" の状態の表示

置換表に関する処理が行われた ことを表す "tt" の状態のフレームでは、ノードの評価値が 置換表に登録されている場合 と、そうでない場合 の 2 種類の処理が行われます。そこで、以下の表示を行うことにします。

ノードの評価値が置換表に 登録されている 場合は 赤字で「置換表に登録済」 と表示し、数直線上 に登録されていた 評価値を表示 する
登録されていない 場合は 黒字で「置換表に未登録」 と表示する

"score" の状態の表示

子ノードの評価値が計算された ことを表す "score" の状態のフレームでは、数直線上に以下の表示 を行うことにします。

計算された 子ノードの評価値
子ノードの評価値で更新する前の、その時点でのノードの評価値

"update" の状態の表示

子ノードの評価値を使ってこのノードの 評価値を更新する処理 を行う "update" の状態のフレームでは、以下の表示を行うことにします。

ノードの 評価値が更新 された場合は 赤字で「評価値の更新」 と表示する
更新されていない 場合は 黒字で「評価値の更新なし」 と表示する
いずれの場合でも、数直線上 にノードの 評価値を表示する

"end" の状態の表示

ノードの 評価値が確定 したことを表す "end" の状態のフレームでは、以下の表示を行うことにします。

数直線上 に確定した ノードの評価値を表示 する
置換表を 利用する場合 は、以下の表示を行う
- このノードの評価値が置換表に 登録されていなかった 場合は置換表への登録が行われるので 赤字で「置換表への登録」 と表示する
- 登録されていた 場合は 黒字で「置換表に登録されていたデータを利用」 と表示する
置換表を 利用しない場合 は 何も表示しない

表示内容と表示に必要な情報の検討

表示する内容が検討できたので、上記で検討した 表示内容を整理 し、その内容を 表示するために必要な情報を検討 します。

常に表示する内容

常に表示する内容と、表示するために必要な情報は以下の表の通りです。なお、mbtree は Mbtree_Anim で表示を行うゲーム木のデータ、node は表示するフレームで処理を行うノードのデータ表すものとします。

表示内容	必要な情報
設定された条件の表示	`mbtree.minimax` `mbtree.use_tt` `mbtree.shortest_victory` `mbtree.init_ab`
数直線	`mbtree.shortest_victory`²
深さ	`node.mb.move_count`
ノードの種類	`node.mb.move_count`
フレームの状態	フレームの状態を表す文字列
枝狩りが行われた数などの情報	計算を行ったノードの数と枝狩りを行ったノードの数

ただし、数直線の表示範囲は負の無限大と正の無限大の間に、以下の 評価値の最小値と最大値の範囲 を表示することにします。

最短の評価値を目指さない場合は -1 ~ 1 の範囲
最短の評価値を目指す場合は -2 ~ 3 の範囲

mbtree と node の情報は Mbtree_Anim で処理を行う際に 利用でき るので、常に表示する内容に対して 必要となるデータ は以下の通りです。

フレームの状態を表す文字列
計算が行われたノードの数
枝狩りが行われたノードの数

また、これらの情報は下記のプログラムのように、calc_score_by_ab でもフレームの情報を記録する際の tuple の 3 ~ 5 番の要素に記録しています。下記の "start" がフレームの状態、self.num_calculated と self.num_pruned が計算が行われたノードの数と、枝狩りが行われたノードの数を表します。

    self.ablist_by_score.append((alpha, beta, None, "start",
                                 self.num_calculated, self.num_pruned))

フレームの状態ごとに表示する内容

それぞれのフレームの状態で表示する内容は以下の通りです。

"start" の状態
なし
"tt" の状態
- 置換表にノードの評価値が登録されている場合
  - 赤字で「置換表に登録済」を表示
  - 数直線上に置換表に登録されていた評価値を表示
- 登録されていない場合
  - 黒字で「置換表に未登録」を表示
"score" の状態
- 数直線上にそのフレームでのノードの評価値を表示
- 数直線上に子ノードの評価値を表示
"update" の状態
- 数直線上にそのフレームでのノードの評価値を表示
- ノードの評価値が更新された場合
  - 赤字で「評価値の更新」を表示
- 更新されていない場合
  - 黒字で「評価値の更新なし」を表示
"end" の状態
- 数直線上にそのフレームでのノードの評価値を表示
- 置換表を利用する場合
  - 置換表にノードの評価値が登録されている場合
    - 黒字で「置換表に登録されていたデータを利用」を表示
  - 登録されていない場合
    - 赤字で「置換表への登録」を表示

また、それぞれの状態で必要となる情報は以下の通りです。

"start" の状態
なし
"tt" の状態
- 置換表にノードの評価値が登録されているかどうか
- 登録されている場合は、置換表に登録されていた評価値
"score" の状態
- そのフレームでのノードの評価値
- 子ノードの評価値
"update" の状態
- そのフレームでのノードの評価値
- ノードの評価値が更新されたかどうか
"end" の状態
- そのフレームでのノードの評価値
- 置換表を利用する場合は「置換表にノードの評価値が登録されているかどうか」

それぞれの状態で 必要となるデータを表にまとめる と以下のようになります。データが必要な場合は〇を表記しました。

データ	"start"	"tt"	"score"	"update"	"end"
置換表に登録されているかどうか	×	〇	×	×	〇
置換表に登録されていた評価値	×	〇	×	×	×
そのフレームでのノードの評価値	×	×	〇	〇	〇
子ノードの評価値	×	×	〇	×	×
ノードの評価値が更新されたかどうか	×	×	×	〇	×

`calc_score_for_anim` の修正

前回の記事では、calc_score_for_anim の中で フレームの情報を記録 する部分を 修正しませんでした が、その理由は どのようなデータを記録すればよいか が、表示する内容が決まらないと わからなかったから です。表示に必要なデータが整理できたので、上記のデータを記録する ように calc_score_for_anim を修正 することにします。なお、calc_score_for_anim の修正にあたっては、以下のような工夫を行なうことにしました。

今回の記事の最初で 互換性を重視 して Mbtree_Anim が calc_score_by_ab と calc_score_for_anim の 両方で作成されたデータを表示できるようにする ことにした。そのため、それぞれの場合 で 表示する処理を変える必要 がある。そこで、Mbtree に どちらのメソッドで作成された データであるかを 区別できるようにする ための、calculated_by_calc_score_for_anim という 属性を追加 した
calc_score_by_ab では、フレームの情報を記録する ablist_by_score という list の要素に tuple でフレームの情報を記録していた が、tuple ではそれぞれの要素に代入された値がどのような意味を持つかが わかりづらい ので、dict を使って 下記の表のような データを記録する ようにした。また、dict でデータを記録することで、tuple のように記録する必要がないデータの要素に None を代入する必要がなくなるという利点が得られる
calc_score_for_anim では 置換表に記録するデータ は、ミニマックス値の下界と上界 であり、ミニマックス法 の場合は 置換表の下界と上界の両方にミニマックス値が記録される。ミニマックス法の場合はフレームの情報にミニマックス値を表すデータを 1 つだけ記録してもかまわないが、今後の記事で 置換表付き αβ 法の視覚化 を行う際に 下界と上界の両方の値が必要となる ので、下記の表のように置換表に登録されていたミニマックス値の下界と上界の 両方を "tt" のフレームのデータに記録 することにした

キー	キーの値の意味
"status"	フレームの状態を表す文字列
"num_calculated"	計算されたノードの数
"num_pruned"	枝狩りされたノードの数
"registered_in_tt"	置換表にノードの評価値が登録されていたかどうか
"lower_bound"	ミニマックス値の下界
"upper_bound"	ミニマックス値の上界
"score"	そのフレームでのノードの評価値
"childscore"	子ノードの評価値
"updated"	ノードの評価値が更新されたかどうか

なお、calc_score_for_anim では、置換表に 登録されていない場合 はミニマックス値の 下界と上界として評価値の最小値と最大値が設定 されますが、その場合はそれらの値は "tt" のフレームの表示では利用しない ので問題はありません。

下記は、そのように修正した calc_score_for_anim のプログラムです。なお、前回の記事で定義 した calc_score_for_anim には フレームの記録の処理に関するバグがありました ので、その修正も行なっています。ただし、そのバグは前回の記事で表示した 枝狩りが行われた数などの計算には影響を与えない ので、前回の記事のプログラムは修正しないことにします。なお、下記のプログラムは非常に長いですが、修正した内容のほとんどはフレームの情報を記録する処理なので、見た目ほどの大きな変更ではありません。

7 ~ 11、25 ~ 32、42 ~ 48、66 ~ 72、78 ~ 84 行目：ablist_by_score に記録するフレームの情報を、tuple から dict に修正し、それぞれのフレームの状態で必要となる情報を記録するように修正した
13 行目：置換表に登録されていたかどうかを表す変数を False で初期化する
20 行目：置換表に登録されていた場合に上記の変数を True にする
50、56 行目："update" のフレームでノードの評価値が更新されるかどうかを計算して updated に代入する。"updated" は 69 行目でこのフレームの情報として記録する
88 行目：calc_score_for_anim によって計算されたことがわかるように、calculated_by_calc_score_for_anim 属性に True を代入するようにした

バグの修正は以下の通りです。

21、61 行目：枝狩りを行う場合にノードを nodelist_by_score に登録する処理を、枝狩りが行なわれた数を数える処理の後で行なうように記述していたが³、そのようにすると枝狩りが一つ前のフレームで行なわれてしまうようになるので、枝狩りが行われた数を数える処理の前に移動した
25 ~ 32 行目：状態が "tt" の場合に ablist_by_score にフレームの情報を記録する処理のインデントが間違っていたため、"use_tt" が False の場合も "tt" の状態のフレームが記録されるようになっている点を修正した

 1  from marubatsu import Marubatsu
 2  from tree import Mbtree
 3  
 4  def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
元と同じなので省略
 5      def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
元と同じなので省略
 6          self.nodelist_by_score.append(node)
 7          self.ablist_by_score.append({
 8              "status": "start",
 9              "num_calculated": self.num_calculated,
10              "num_pruned": self.num_pruned,
11          })
12          
13          registered_in_tt = False
14          if node.mb.status != Marubatsu.PLAYING:
元と同じなので省略
15          else:
16              pruned = False
17              if use_tt:
18                  boardtxt = node.mb.board_to_str()
19                  if boardtxt in tt:
20                      registered_in_tt = True
元と同じなので省略
21                  self.nodelist_by_score.append(node)
22                  if pruned:
23                      for childnode in node.children:
24                          assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
25                  self.ablist_by_score.append({
26                      "status": "tt",
27                      "registered_in_tt": registered_in_tt,
28                      "lower_bound": lower_bound,
29                      "upper_bound": upper_bound,
30                      "num_calculated": self.num_calculated,
31                      "num_pruned": self.num_pruned,
32                  })   
33          
34              if not pruned:
35                  alpha = alphaorig
36                  beta = betaorig
37                  maxnode = node.mb.turn == Marubatsu.CIRCLE
38                  node.score = min_score if maxnode else max_score
39                  for childnode in node.children:
40                      childscore = calc_node_score(childnode, tt, alpha, beta)
41                      self.nodelist_by_score.append(node)
42                      self.ablist_by_score.append({
43                          "status": "score",
44                          "score": node.score,
45                          "childscore": childscore,
46                          "num_calculated": self.num_calculated,
47                          "num_pruned": self.num_pruned,
48                      })   
49                      if maxnode:
50                          updated = node.score < childscore
51                          node.score = max(node.score, childscore)
52                          alpha = max(node.score, alpha)
53                          if node.score >= beta:
54                              pruned = True
55                      else:
56                          updated = node.score > childscore
57                          node.score = min(node.score, childscore)
58                          beta = min(node.score, beta)
59                          if node.score <= alpha:
60                              pruned = True
61                      self.nodelist_by_score.append(node)
62                      if pruned:
63                          index = node.children.index(childnode)
64                          for prunednode in node.children[index + 1:]:
65                              assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
66                      self.ablist_by_score.append({
67                          "status": "update",
68                          "score": node.score,
69                          "updated": updated,
70                          "num_calculated": self.num_calculated,
71                          "num_pruned": self.num_pruned,
72                      })   
73                      if pruned:
74                          break 
75  
元と同じなので省略
76          self.nodelist_by_score.append(node)
77          self.num_calculated += 1     
78          self.ablist_by_score.append({
79              "status": "end",
80              "score": node.score,
81              "registered_in_tt": registered_in_tt,
82              "num_calculated": self.num_calculated,
83              "num_pruned": self.num_pruned,
84          })   
85          node.score_index = len(self.nodelist_by_score) - 1          
86          return node.score                
87                                      
88      self.calculated_by_calc_score_for_anim = True
89      self.minimax = minimax
元と同じなので省略
90      
91  Mbtree.calc_score_for_anim = calc_score_for_anim

行番号のないプログラム

from marubatsu import Marubatsu
from tree import Mbtree

def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
    def assign_pruned_index(node, index):
        node.pruned_index = index
        self.num_pruned += 1
        for childnode in node.children:
            assign_pruned_index(childnode, index)
            
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
        if minimax:
            alphaorig = float("-inf")
            betaorig = float("inf")            

        self.nodelist_by_score.append(node)
        self.ablist_by_score.append({
            "status": "start",
            "num_calculated": self.num_calculated,
            "num_pruned": self.num_pruned,
        })
        
        registered_in_tt = False
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            lower_bound = node.score
            upper_bound = node.score
        else:
            pruned = False
            if use_tt:
                boardtxt = node.mb.board_to_str()
                if boardtxt in tt:
                    registered_in_tt = True
                    lower_bound, upper_bound = tt[boardtxt]
                    if lower_bound == upper_bound:
                        node.score = lower_bound
                        pruned = True
                    elif upper_bound <= alphaorig:
                        node.score = upper_bound
                        pruned = True
                    elif betaorig <= lower_bound:
                        node.score = lower_bound
                        pruned = True
                    else:
                        alphaorig = min(alphaorig, lower_bound)
                        betaorig = max(betaorig, upper_bound)
                else:
                    lower_bound = min_score
                    upper_bound = max_score
                self.nodelist_by_score.append(node)
                if pruned:
                    for childnode in node.children:
                        assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
                self.ablist_by_score.append({
                    "status": "tt",
                    "registered_in_tt": registered_in_tt,
                    "lower_bound": lower_bound,
                    "upper_bound": upper_bound,
                    "num_calculated": self.num_calculated,
                    "num_pruned": self.num_pruned,
                })   
        
            if not pruned:
                alpha = alphaorig
                beta = betaorig
                maxnode = node.mb.turn == Marubatsu.CIRCLE
                node.score = min_score if maxnode else max_score
                for childnode in node.children:
                    childscore = calc_node_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append({
                        "status": "score",
                        "score": node.score,
                        "childscore": childscore,
                        "num_calculated": self.num_calculated,
                        "num_pruned": self.num_pruned,
                    })   
                    if maxnode:
                        updated = node.score < childscore
                        node.score = max(node.score, childscore)
                        alpha = max(node.score, alpha)
                        if node.score >= beta:
                            pruned = True
                    else:
                        updated = node.score > childscore
                        node.score = min(node.score, childscore)
                        beta = min(node.score, beta)
                        if node.score <= alpha:
                            pruned = True
                    self.nodelist_by_score.append(node)
                    if pruned:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append({
                        "status": "update",
                        "score": node.score,
                        "updated": updated,
                        "num_calculated": self.num_calculated,
                        "num_pruned": self.num_pruned,
                    })   
                    if pruned:
                        break 
                    
        if use_tt:
            from util import calc_same_boardtexts
            boardtxtlist = calc_same_boardtexts(node.mb)
            
            if node.score <= alphaorig:
                upper_bound = node.score
            elif node.score < betaorig:
                lower_bound = node.score
                upper_bound = node.score
            else:
                lower_bound = node.score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound) 

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append({
            "status": "end",
            "score": node.score,
            "registered_in_tt": registered_in_tt,
            "num_calculated": self.num_calculated,
            "num_pruned": self.num_pruned,
        })   
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score                
                                    
    self.calculated_by_calc_score_for_anim = True
    self.minimax = minimax
    self.init_ab = init_ab
    self.use_tt = use_tt
    if shortest_victory is not None:
        self.shortest_victory = shortest_victory

    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
        node.pruned_index = float("inf")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    self.num_calculated = 0
    self.num_pruned = 0
    if init_ab:
        min_score = -2 if self.shortest_victory else -1
        max_score = 3 if self.shortest_victory else 1
    else:
        min_score = float("-inf")
        max_score = float("inf")
    calc_node_score(abroot, {}, min_score, max_score)
    total_nodenum = self.num_pruned + self.num_calculated
    ratio = self.num_calculated / total_nodenum * 100
    dprint(debug, "ミニマックス法で計算したか", minimax)    
    dprint(debug, "計算したノードの数",  self.num_calculated)
    dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
    dprint(debug, "合計",  total_nodenum)
    dprint(debug, f"割合 {ratio:.1f}%") 
    
Mbtree.calc_score_for_anim = calc_score_for_anim

修正箇所

from marubatsu import Marubatsu
from tree import Mbtree

def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
元と同じなので省略
    def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
元と同じなので省略
        self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alphaorig, betaorig, None, "start",
-                                    self.num_calculated, self.num_pruned))
+       self.ablist_by_score.append({
+           "status": "start",
+           "num_calculated": self.num_calculated,
+           "num_pruned": self.num_pruned,
+       })
        
+       registered_in_tt = False
        if node.mb.status != Marubatsu.PLAYING:
元と同じなので省略
        else:
            pruned = False
            if use_tt:
                boardtxt = node.mb.board_to_str()
                if boardtxt in tt:
+                   registered_in_tt = True
元と同じなので省略
+               self.nodelist_by_score.append(node)
                if pruned:
                    for childnode in node.children:
                        assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)  
-           self.nodelist_by_score.append(node)
-           self.ablist_by_score.append((alphaorig, betaorig, None, "tt",
-                                        self.num_calculated, self.num_pruned))
+               self.ablist_by_score.append({
+                   "status": "tt",
+                   "registered_in_tt": registered_in_tt,
+                   "lower_bound": lower_bound,
+                   "upper_bound": upper_bound,
+                   "num_calculated": self.num_calculated,
+                   "num_pruned": self.num_pruned,
+               })   
        
            if not pruned:
                alpha = alphaorig
                beta = betaorig
                maxnode = node.mb.turn == Marubatsu.CIRCLE
                node.score = min_score if maxnode else max_score
                for childnode in node.children:
                    childscore = calc_node_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
-                   self.ablist_by_score.append((alpha, beta, node.score, "score",
-                                                self.num_calculated, self.num_pruned))
+                   self.ablist_by_score.append({
+                       "status": "score",
+                       "score": node.score,
+                       "childscore": childscore,
+                       "num_calculated": self.num_calculated,
+                       "num_pruned": self.num_pruned,
+                   })   
                    if maxnode:
+                       updated = node.score < childscore
                        node.score = max(node.score, childscore)
                        alpha = max(node.score, alpha)
                        if node.score >= beta:
                            pruned = True
                    else:
+                       updated = node.score > childscore
                        node.score = min(node.score, childscore)
                        beta = min(node.score, beta)
                        if node.score <= alpha:
                            pruned = True
+                   self.nodelist_by_score.append(node)
                    if pruned:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
-                   self.nodelist_by_score.append(node)
-                   self.ablist_by_score.append((alpha, beta, None, "update",
-                                                self.num_calculated, self.num_pruned))
+                   self.ablist_by_score.append({
+                       "status": "update",
+                       "score": node.score,
+                       "updated": updated,
+                       "num_calculated": self.num_calculated,
+                       "num_pruned": self.num_pruned,
+                   })   
                    if pruned:
                        break 
                    
元と同じなので省略
        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
-       self.ablist_by_score.append((alphaorig, betaorig, None, "end",
-                                    self.num_calculated, self.num_pruned))        
+       self.ablist_by_score.append({
+           "status": "end",
+           "score": node.score,
+           "registered_in_tt": registered_in_tt,
+           "num_calculated": self.num_calculated,
+           "num_pruned": self.num_pruned,
+       })   
        node.score_index = len(self.nodelist_by_score) - 1          
        return node.score                
                                    
+   self.calculated_by_calc_score_for_anim = True
    self.minimax = minimax
元と同じなので省略
    
Mbtree.calc_score_for_anim = calc_score_for_anim

上記の修正後に下記のプログラムで 前回の記事と同じ計算 を行うと、実行結果から前回の記事と同じ結果が表示されることが確認できます。

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

print("ai_mmdfs")
mbtree.calc_score_for_anim(mbtree.root, minimax=True, init_ab=False, use_tt=False, debug=True)
print()
print("ai_mmdfs_tt")
mbtree.calc_score_for_anim(mbtree.root, minimax=True, init_ab=False, use_tt=True, debug=True)
print()
print("ai_abs_tt")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=False, use_tt=False, debug=True)
print()
print("ai_abs_tt3")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=False, use_tt=True, debug=True)
print()
print("ai_abs_tt4")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, init_ab=True, use_tt=True, debug=True)

実行結果

ai_mmdfs
ミニマックス法で計算したか True
計算したノードの数 549946
枝狩りしたノードの数 0
合計 549946
割合 100.0%

ai_mmdfs_tt
ミニマックス法で計算したか True
計算したノードの数 2271
枝狩りしたノードの数 547675
合計 549946
割合 0.4%

ai_abs_tt
ミニマックス法で計算したか False
計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%

ai_abs_tt3
ミニマックス法で計算したか False
計算したノードの数 1173
枝狩りしたノードの数 548773
合計 549946
割合 0.2%

ai_abs_tt4
ミニマックス法で計算したか False
計算したノードの数 832
枝狩りしたノードの数 549114
合計 549946
割合 0.2%

`calc_score_by_ab` の修正

初心者の方は忘れがちだと思いますが、上記で calc_score_for_anim で計算されたかどうかを表す calculated_by_calc_score_for_anim という属性を導入 したので、calc_score_by_ab で計算処理を行った場合に この属性に False を代入する処理を記述する必要 があります。

その修正を忘れると 同じゲーム木のデータ に対して calc_score_for_anim で計算を行なった後 で calc_score_by_ab で計算を行うと calculated_by_calc_score_for_anim の値が True のまま変化しない という問題が発生するからです。

実際にそのことは 下記のプログラムで確認 できます。先程 calc_score_for_anim で計算を行なったので下記の実行結果の 1 行目では calculated_by_calc_score_for_anim の値として True が表示されますが、その後で calc_score_by_ab で計算し直した後 の 3 行目の 実行結果も True が表示 されています。

print(mbtree.calculated_by_calc_score_for_anim)
mbtree.calc_score_by_ab(mbtree.root)
print(mbtree.calculated_by_calc_score_for_anim)

実行結果

True
True

下記はそのように calc_score_by_ab を修正したプログラムです。

3 行目：calculated_by_calc_score_for_anim に False を代入するように修正した

1  def calc_score_by_ab(self, abroot, debug:bool=False, minimax=False, init_ab=False, use_tt=False):
元と同じなので省略
2      from ai import dprint       
3      self.calculated_by_calc_score_for_anim = False    
4      for node in self.nodelist:
5          node.score_index = float("inf")
6          node.pruned_index = float("inf")
元と同じなので省略 
7     
8  Mbtree.calc_score_by_ab = calc_score_by_ab

行番号のないプログラム

def calc_score_by_ab(self, abroot, debug:bool=False, minimax=False, init_ab=False, use_tt=False):
    def assign_pruned_index(node, index):
        node.pruned_index = index
        self.num_pruned += 1
        for childnode in node.children:
            assign_pruned_index(childnode, index)
        
    def calc_ab_score(node, tt, alpha=float("-inf"), beta=float("inf")):
        if minimax:
            alpha = float("-inf")
            beta = float("inf")
        if use_tt:
            boardtxt = node.mb.board_to_str()
            key = (boardtxt, alpha, beta)
            if key in tt:
                node.score = tt[key]
                if node.mb.turn == Marubatsu.CIRCLE:
                    alpha = node.score
                else:
                    beta = node.score
                self.nodelist_by_score.append(node)
                self.num_calculated += 1     
                for childnode in node.children:
                    assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
                self.ablist_by_score.append((alpha, beta, None, "tt",
                                            self.num_calculated, self.num_pruned))
                node.score_index = len(self.nodelist_by_score) - 1  
                return node.score
                
        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, None, "start",
                                    self.num_calculated, self.num_pruned))
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
            if node.mb.turn == Marubatsu.CIRCLE:
                alpha = node.score
            else:
                beta = node.score
        else:
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score",
                                                self.num_calculated, self.num_pruned))
                    if score > alpha:
                        alpha = score
                    self.nodelist_by_score.append(node)
                    if score >= beta:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                self.num_calculated, self.num_pruned))
                    if score >= beta:
                        break
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, tt, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score",
                                                self.num_calculated, self.num_pruned))
                    if score < beta:
                        beta = score
                    self.nodelist_by_score.append(node)
                    if score <= alpha:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                self.num_calculated, self.num_pruned))
                    if score <= alpha:
                        break
                node.score = beta

        self.nodelist_by_score.append(node)
        self.num_calculated += 1     
        self.ablist_by_score.append((alpha, beta, None, "end",
                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1  
        if use_tt:
            from util import calc_same_boardtexts   
            
            boardtxtlist = calc_same_boardtexts(node.mb)
            _, alpha, beta = key
            for boardtxt in boardtxtlist:
                tt[(boardtxt, alpha, beta)] = node.score            
        return node.score

    from ai import dprint       
    self.calculated_by_calc_score_for_anim = False    
    for node in self.nodelist:
        node.score_index = float("inf")
        node.pruned_index = float("inf")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    self.num_calculated = 0
    self.num_pruned = 0
    if init_ab:
        alpha = -2 if self.shortest_victory else -1
        beta = 3 if self.shortest_victory else 1
    else:
        alpha = float("-inf")
        beta = float("inf")
    calc_ab_score(abroot, {}, alpha, beta)
    total_nodenum = self.num_pruned + self.num_calculated
    ratio = self.num_calculated / total_nodenum * 100
    dprint(debug, "ミニマックス法で計算したか", minimax)    
    dprint(debug, "計算したノードの数",  self.num_calculated)
    dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
    dprint(debug, "合計",  total_nodenum)
    dprint(debug, f"割合 {ratio:.1f}%")
    
Mbtree.calc_score_by_ab = calc_score_by_ab

修正箇所

def calc_score_by_ab(self, abroot, debug:bool=False, minimax=False, init_ab=False, use_tt=False):
元と同じなので省略
    from ai import dprint       
+   self.calculated_by_calc_score_for_anim = False    
    for node in self.nodelist:
        node.score_index = float("inf")
        node.pruned_index = float("inf")
元と同じなので省略 

Mbtree.calc_score_by_ab = calc_score_by_ab

上記の修正後に下記のプログラムで改めて calc_score_by_ab を実行すると、実行結果のように calculated_by_calc_score_for_anim 属性に False が代入されるようになった ことが確認できます。

mbtree.calc_score_by_ab(mbtree.root)
print(mbtree.calculated_by_calc_score_for_anim)

実行結果

False

上記の修正を行っても、"../data/abtree_root.mbtree" のように、修正前の calc_score_by_ab で計算したデータ には calculated_by_calc_score_for_anim 属性が存在しない という問題があるのではないかと思った人がいるかもしれません。その点に関する対処は次回の記事で行います。

今回の記事のまとめ

今回の記事では、calc_score_for_anim で ミニマックス法で評価値を計算したデータ を Mbtree_Anim で 視覚化する方法について検討 し、そのために 必要なデータを記録する ように calc_score_for_anim を修正 しました。

次回の記事では Mbtree_Anim を修正して実際の視覚化を行うことができるようにします。

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

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
tree.py	本記事で更新した tree_new.py

次回の記事

詳細は省略しますが、Mbtree_Anim クラスを継承して、処理の内容が異なるメソッドだけを定義することで実装を比較的簡単に行うという方法も考えられますが、そのような継承はあまり推奨されていない方法だと思います ↩
この情報が必要になるのは、最短の勝利を目指すかによって数直線の表示範囲を変えるようにしたからです ↩
calc_score_by_ab では正しく記述していたのを、calc_score_for_anim に修正する際に間違った場所に記述してしまいました ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Pythonで〇×ゲームのAIを一から作成する その157 ミニマックス法の視覚化の検討と視覚化に必要なデータの記録

目次と前回の記事

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

置換表付き αβ 法の視覚化を行う方法の検討

実装方法の選択

calc_score_for_anim が行うことができる計算の種類

現状の Mbtree_Anim の問題点の考察

実装の手順の検討

ミニマックス法の視覚化の検討

ミニマックス法での視覚化の種類

設定された条件の表示

ミニマックス法と αβ 法での表示の区別

最短の勝利を目指す評価値を計算しているかどうかの表示の区別

以後の説明に関する補足

それぞれの状態での表示の検討

共通する表示内容の検討

条件による表示の違いの検討

"start" の状態の表示

"tt" の状態の表示

"score" の状態の表示

"update" の状態の表示

"end" の状態の表示

表示内容と表示に必要な情報の検討

常に表示する内容

フレームの状態ごとに表示する内容

calc_score_for_anim の修正

calc_score_by_ab の修正

今回の記事のまとめ

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その157　ミニマックス法の視覚化の検討と視覚化に必要なデータの記録

`calc_score_for_anim` が行うことができる計算の種類

`calc_score_for_anim` の修正

`calc_score_by_ab` の修正