目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| test.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義。現在は gui_play のみ定義されている |
| tree.py | ゲーム木に関する Node、Mbtree クラスの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
αβ 法の視覚化の検討と視覚化に必要なデータの記録
以前の記事で、ミニマックス法と αβ 法の視覚化の実装を下記の手順で行うという説明を行いました。手順 1 ~ 3 については前回の記事で完了したので、手順 4 を行うことにします。
- ミニマックス法 での 視覚化の方法を検討 する
- 検討した 視覚化を行うために必要なフレームのデータを記録 するように
calc_score_for_animを修正 する - Mbtree_Anim を 検討した視覚化を行うように 修正する
- αβ 法で上記の 1 ~ 3 の手順を行う
具体的には下記の作業を行います。
- αβ 法 での 視覚化の方法を検討 する
- 検討した 視覚化を行うために必要なフレームのデータを記録 するように
calc_score_for_animを修正 する - Mbtree_Anim を 検討した視覚化を行うに 修正する
今回の記事では上記の手順 1 と 2 を行います。
今回の記事で利用する記号
今回の記事では以前の記事と同様に以下の記号を使って説明を行ないます。また、今回の記事で用いる用語の意味について忘れた方は以前の記事を復習して下さい。
| 記号 | 意味 |
|---|---|
| $l$ | ミニマックス値の下界（lower bound） |
| $u$ | ミニマックス値の上界（upper bound） |
| $α$ | $α$ 値の初期値 |
| $β$ | $β$ 値の初期値 |
| $α 値$ | 現在の $α$ 値 |
| $β 値$ | 現在の $β$ 値 |
| $s$ | ノードの評価値 |
| $c$ | 子ノードの評価値 |
| $min(a, b)$ | $a$ と $b$ の最小値 |
| $max(a, b)$ | $a$ と $b$ の最大値 |
αβ 法での視覚化の方法の検討
αβ 法での視覚化 をどのように行えば良いかについて少し考えてみて下さい。なお、行う作業は以前の記事でミニマックス法での視覚化の方法の検討で行った作業とよく似ています。
αβ 法での視覚化の種類と設定された条件の表示
以前の記事で説明したように、calc_score_for_anim は下記の 4 つの条件で評価値を計算できます。
- アルゴリズムとして ミニマックス法 と αβ 法 のいずれかを選択できる（仮引数
minimax） -
置換表を利用するか どうかを選択できる（仮引数
use_tt） -
最短の勝利を目指す評価値を計算するか どうかを選択できる（仮引数
shortest_victory） -
ルートノードの α 値と β 値の初期値 を評価値の最小値と最大値に設定するかどうかを選択できる（仮引数
init_ab）
従って、αβ 法では $2^3 = 8$ 通りの条件の組み合わせがあります。
設定された条件の表示方法 については、以前の記事で 考察済 です。また、考察した内容の表示のうち、αβ 法で α 値と β 値を表示する以外の処理 は前回の記事で 実装済 です。
表示内容の検討の方針
次に、αβ 法での "start"、"tt"、"score"、"update"、"end" の 5 つのそれぞれの状態のフレーム に対して、どのような表示を行うか について検討する必要があります。どのように表示すれば良いかについて少し考えてみて下さい。
なお、本記事では先に表示内容を検討してから、表示の実装を行うという流れで説明を行っていますが、今回の場合のようにある程度以上 表示内容が複雑になる場合 は、実際には 表示の実装を行う際 に検討した 表示内容の不備が見つかったり、新たに表示したほうが良い内容を思いつく ことが 良くあります。従って、実際の作業 では以下のような 作業の繰り返し の 試行錯誤 によって実装を進めるのが一般的だと思います。今回の実装では実際に筆者もそのような作業を行いましたが、行った作業をそのままの順番で説明すると長くなりすぎるので、本記事では 最終的な実装で行う表示内容を元 に下記の表示の 検討内容を記しました。
- 表示内容を検討する
- 検討した内容に従って実装を行う
- 検討の不備が見つかった場合は手順 1 に戻って表示内容を修正する
共通する表示内容の検討
最初に、すべての場合で 共通する表示内容 について検討することにします。
以前の記事でミニマックス法での共通する表示内容として検討した下記の表示に関しては、ミニマックス法と αβ 法で違いは無い ので 同じ表示を行う ことにします。
- 数直線
- 選択中のノードの深さ
- ノードの種類
- フレームで行われる処理を表す状態
- 右に表示される「計算済」や「枝狩り」などの、枝狩りが行われたノードの数などの表示
αβ 法での共通する表示内容 としては、下記の内容が挙げられます
- α 値と β 値の初期値
- α 値と β 値の初期値によって分けられる fail low、exact value、fail high の 範囲の色分け。具体的な色分けの方法については実装の際に検討する
- 色分けされた 範囲の説明
なお、これらの表示内容は、下図の calc_score_by_ab で計算されたデータに対して Mbtree_Anim が行っていた 表示と似ています。ただし、下図では α 値と β 値の初期値ではなく、現在の α 値と β 値に対する表示 が行われている点が 異なる ので、実装の際にはその点に注意する必要があります。
以後は、上記の情報を常に表示するという前提で説明を行います。
条件による表示の違いの検討
先程説明したように、αβ 法 では下記の 3 種類の条件 で評価値を計算することができます。
-
置換表を利用するか どうかを選択できる（仮引数
use_tt） -
最短の勝利を目指す評価値を計算するか どうかを選択できる（仮引数
shortest_victory） -
ルートノードの α 値と β 値の初期値 を評価値の最小値と最大値に設定するかどうかを選択できる（仮引数
init_ab）
5 つの状態の中で、置換表を利用するかどうか によって 行う処理が変わる のは "tt" と "end" の状態のフレームだけで、以下のように異なります。従って、"end" のフレームの表示のみ、置換表を利用するかどうかで 表示が変わる場合があります。
-
"tt"のフレームの処理は 置換表を利用する場合のみ 行なわれる -
"end"のフレームの処理では、置換表を利用する場合のみ 計算されたミニマックス値の範囲を 置換表に登録または更新する処理が行われる 場合がある1
最短の勝利を目指す評価値を計算するかどうか によって変わるのは、決着がついたノードの評価値の計算方法だけ で、それ以外の処理は全く変わりません。そのため、5 つの状態の表示方法は 数直線の表示範囲を変えるという工夫以外 では 共通します。これは、ミニマックス法の場合と同様でその表示は、前回の記事で既に実装済です。
ルートノードの α 値と β 値の初期値を評価値の最小値と最大値に設定するか どうかによって変わるのは以下の通りです。
- 各ノードの評価値を計算する際の α 値と β 値の初期値
- 各ノードの ミニマックス値の下界の最小値 が負の無限大でく評価値の最小値となる
- 各ノードの ミニマックス値の上界の最大値 が正の無限大でく評価値の最大値となる
上記の考察を元に、5 つのそれぞれの状態での表示方法を検討することにします。
"start" の状態の表示
ノードの処理の開始 を表す "start" の状態のフレームでは、常に表示する内容を除いて 特に何かを表示する必要はない でしょう。
"tt" の状態の表示
置換表に関する処理が行われた ことを表す "tt" の状態のフレームでは以下の処理が行われます。
- ノードのミニマックス値の範囲が 置換表に登録されている場合
- 置換表に登録されているミニマックス値の 下界（$l$）と上界（$u$）が等しい（$l = u$）場合は $l$（または $u$）をそのノードの評価値とする
- $u ≦ α$（ミニマックス値の範囲が fail low に完全に含まれている）の場合は $u$ をそのノードの評価値とする
- $β ≦ l$（ミニマックス値の範囲が fail high に完全に含まれている）の場合は $l$ をそのノードの評価値とする
- 上記の どれでもない場合 は α 値と β 値の初期値 を下記のように 更新して 子ノードの評価値から このノードの評価値を計算 する
- ノードのミニマックス値の範囲が 置換表に登録されていない場合 は子ノードの評価値から このノードの評価値を計算 する
上記の 違いがわかるような表示 として、下記の表示を行うことにします。
まず、ノードのミニマックス値の範囲が 置換表に登録されているかどうか によって、ミニマックス法の場合と同様 に下記の表示を行うことにします。
| 置換表の登録 | 表示 |
|---|---|
| あり | 赤字で「置換表に登録済」 |
| なし | 黒字で「置換表に未登録」 |
ミニマックス法の場合は置換表にそのノードの評価値が登録されていた場合は数直線上にその評価値を表示していましたが、αβ 法 では置換表には ミニマックス値の範囲が記録 されるので、下記のような表示を行うことにします。その際に 置換表の登録の有無 を何らかの方法で 区別してわかるように表示する ことにします。また、この ミニマックス値の範囲 は "score"、"update"、"end" の状態でも表示 することにします。
| 置換表の登録 | 表示 |
|---|---|
| あり | ミニマックス値の範囲（下界と上界）を何らかの方法で表示する |
| なし | 下界を負の無限大または評価値の最小値、上界を正の無限大または評価値の最大値として、ミニマックス値の範囲 を何らかの方法で表示する |
また、置換表に登録されている場合は下記の表のような表示を行うことにします。
| 条件 | 表示 |
|---|---|
| $l = u$ | 赤字で「置換表による枝狩り（exact value）」 |
| $u ≦ α$ | 赤字で「置換表による枝狩り（fail low）」 |
| $β ≦ l$ | 赤字で「置換表による枝狩り（fail high）」 |
| 上記以外で α 値と β 値の初期値が更新 | 赤字で「α 値または β 値の初期値の更新」 |
"score" の状態の表示
ミニマックス法では 子ノードの評価値が計算された ことを表す "score" の状態のフレームでは、数直線上に以下の表示 を行いました。αβ 法でも同様の表示 を行うことにします。
- 計算された 子ノードの評価値
- 子ノードの評価値で更新する前の、その時点でのノードの評価値
αβ 法では上記に加えて そのフレームでの α 値と β 値 の情報があるので それらの情報の表示 も行うことにします。
"update" の状態の表示
ミニマックス法では子ノードの評価値を使ってこのノードの 評価値を更新する処理 を行う "update" の状態のフレームでは、以下の表示を行いました。αβ 法でも同様の表示 を行うことにします。
- ノードの 評価値が更新 された場合は 赤字で「評価値の更新」 と表示する
- 更新されていない 場合は 黒字で「評価値の更新なし」 と表示する
- いずれの場合でも、数直線上 にノードの 評価値を表示する
αβ 法 では上記に加えて そのフレームでの α 値と β 値の情報 があるので "score" の状態の場合と同様に それらの情報の表示 も行うことにします。
また、αβ 法 では α 狩りまたは β 狩り による 枝狩りが行われる場合があ るので、下記の表示を行うことにします。
- α 狩りが行われた場合は赤字で「α 狩り」と表示する
- β 狩りが行われた場合は赤字で「β 狩り」と表示する
"end" の状態の表示
ミニマックス法ではノードの 評価値が確定 したことを表す "end" の状態のフレームでは、以下の表示を行いました。αβ 法でも同様の表示を行う ことにします。
- 数直線上 に確定した ノードの評価値を表示 する
ミニマックス法では置換表に評価値が登録されていた場合は、必ずその評価値をそのノードの評価値として利用し、置換表による子孫ノードの枝狩りが行われましたが、置換表付き αβ 法 では 置換表に ミニマックス値の範囲が 登録されていた場合でも 置換表による 枝狩りが行われない場合 があります。そこで下記のように表示することにします。
- 置換表を 利用する場合 は、以下の表示を行う
- 置換表による枝狩り が 行われた場合 は 黒字で「置換表に登録されていたデータを利用」 と表示する
- 置換表による枝狩りが 行われなかった場合 はこのノードの評価値を元に計算されたミニマックス値の範囲が置換表に登録または更新されるので 赤字で「置換表への登録」 と表示する
- 置換表を 利用しない場合 は 何も表示しない
また、置換表を利用する場合で、置換表による枝狩りが行われなかった場合 は、以前の記事で説明した方法で置換表に登録するミニマックス値の計算を行います。
- 「置換表に登録されていたミニマックス値の範囲」2と子ノードの評価値を計算することで「得られた評価値によって決まるミニマックス値の範囲」の共通部分を計算する
- 計算された共通部分をミニマックス値の範囲として置換表に登録または更新する
なお、本記事では 3 種類のミニマックス値の範囲 を 区別できるよう に、それぞれを以下の表のように短く表記することにします。
| 表記 | 意味 |
|---|---|
| 置換表の範囲 | 置換表に登録されていたミニマックス値の範囲 |
| 計算された範囲 | 子ノードの評価値から計算されたミニマックス値の範囲 |
| 登録する範囲 | 置換表に登録する、上記の 2 つの共通する範囲 |
登録する範囲 が どのように計算されたかがわかる ように下記の表示を行うことにします。
- 「計算された範囲」を何らかの方法で表示する
- 「登録する範囲」を何らかの方法で表示する
ミニマックス法ではすべてのノードで必ず正しい評価値が計算されますが、αβ 法 では fail low、exact value、fail high の 3 種類の評価値が計算される ので、それぞれの場合で フレームの状態を表す文字列 として下記の表示を行うことにします。なお、計算された評価値 が fail low や fail high の範囲であったとしても、登録する範囲が 範囲を持たない（下界 = 上界）場合 は正確なミニマックス値が計算されるので exact value とみなす ことにします。
| 評価値の種類 | 表示 |
|---|---|
| fail low | 評価値の確定（fail low） |
| exact value | 評価値の確定（exact value） |
| fail high | 評価値の確定（fail high） |
表示内容と表示に必要な情報の検討
表示する内容が検討できたので、上記で検討した 表示内容を整理 し、その内容を 表示するために必要な情報を検討 します。
常に表示する内容
常に表示する内容と、表示するために必要な情報は以下の表の通りです。以前の記事で検討したミニマックス法での表示と共通する内容は省略しました。
| 表示内容 | 必要な情報 |
|---|---|
|
α 値と β 値の初期値 範囲の色分け 範囲の説明 |
α 値と β 値の初期値 |
従って、αβ 法の場合で新しく必要になる情報は以下の通りです。
- α 値と β 値の初期値
"start" 以外の状態で表示する内容
"start" 以外 の状態で表示する内容と、表示するために必要な情報は以下の通りです。
| 表示内容 | 必要な情報 |
|---|---|
| 置換表の範囲 | 置換表の範囲の下界と上界 |
| 置換表の登録の区別 | 置換表に登録されているかどうか |
フレームの状態ごとに表示する内容
それぞれのフレームの状態で表示する内容は以下の通りです。上記の "start" 以外の状態で表示する内容は省略しました。なお、ミニマックス法と共通する内容には先頭に（※）を記述しました。
-
"start" の状態
なし -
"tt" の状態
- 置換表にノードの評価値が登録されている場合
- （※）赤字で「置換表に登録済」を表示
- ミニマックス法で表示した置換表に登録されていた評価値は 表示しない
- 置換表による枝狩りが行われている場合
- $l=u$ の場合は赤字で「置換表による枝狩り（exact value）」を表示
- $u≦α$ の場合は赤字で「置換表による枝狩り（fail low）」を表示
- $β≦l$ の場合は赤字で「置換表による枝狩り（fail high）」を表示
- 置換表による枝狩りが行われていない場合
- α 値と β 値の初期値が更新される場合は赤字で「α 値または β 値の初期値の更新」を表示
- 登録されていない場合
- （※）黒字で「置換表に未登録」を表示
- 置換表にノードの評価値が登録されている場合
-
"score" の状態
- （※）数直線上にそのフレームでのノードの評価値を表示
- （※）数直線上に子ノードの評価値を表示
- そのフレームでの α 値と β 値
-
"update" の状態
- （※）数直線上にそのフレームでのノードの評価値を表示
- ノードの評価値が更新された場合
- （※）赤字で「評価値の更新」を表示
- 更新されていない場合
- （※）黒字で「評価値の更新なし」を表示
- そのフレームでの α 値と β 値
- α 狩りが行われた場合は赤字で「α 狩り」と表示
- β 狩りが行われた場合は赤字で「β 狩り」と表示
-
"end" の状態
- （※）数直線上にそのフレームでのノードの評価値を表示
- このノードの評価値の種類によってフレームの状態を以下のように表示する
- fail low の場合は「評価値の確定（fail low）」を表示
- exact value の場合は「評価値の確定（exact value）」を表示
- fail high の場合は「評価値の確定（fail high）」を表示
- 置換表を利用する場合
- 置換表による枝狩りが行われた場合
- （※）黒字で「置換表に登録されていたデータを利用」を表示
- 置換表による枝狩りが行われていない場合
- （※）赤字で「置換表への登録」を表示
- 計算された範囲
- 登録する範囲
- 置換表による枝狩りが行われた場合
また、それぞれの状態で必要となる情報は以下の通りです。そのフレームでの α 値と β 値 はそれぞれ $max(α, s)$、$min(β, s)$ で 計算できる ので、フレームの情報に 記録する必要はありません。なお、ミニマックス法と共通する内容には先頭に（※）を記述しました。
-
"start" の状態
- なし
-
"tt" の状態
- （※）置換表にノードの評価値が登録されているかどうか
- 置換表による枝狩りが行われたかどうか
- ミニマックス値の上界と下界
-
"score" の状態
- （※）そのフレームでのノードの評価値
- （※）子ノードの評価値
- ミニマックス値の上界と下界
-
"update" の状態
- （※）そのフレームでのノードの評価値
- （※）ノードの評価値が更新されたかどうか
- ミニマックス値の上界と下界
- α 狩りまたは β 狩りが行われたかどうか
-
"end" の状態
- （※）そのフレームでのノードの評価値
- ミニマックス値の上界と下界
- ノードの評価値の種類
- 置換表による枝狩りが行われたかどうか
- 置換表による枝狩りが行われた場合
- 子ノードの評価値の計算によって計算されたミニマックス値の下界と上界
- 置換表に登録または更新するミニマックス値の下界と上界
それぞれの状態で 必要となるデータを表にまとめる と以下のようになります。データが必要な場合は 〇 を表記しました。ミニマックス法と共通する内容には先頭に（※）を記述しました。なお、置換表の範囲3 と 置換表に登録されているかどうか はミニマックス法でも記録していましたが "score" と "update" の状態でも記録する ようになった点が 異なります。
| データ | start | tt | score | update | end |
|---|---|---|---|---|---|
| α 値と β 値の初期値 | 〇 | 〇 | 〇 | 〇 | 〇 |
| 置換表に登録されているかどうか | × | 〇 | 〇 | 〇 | 〇 |
| 置換表の範囲 | × | 〇 | 〇 | 〇 | 〇 |
| 置換表による枝狩りが行われたかどうか | × | 〇 | × | × | 〇 |
| α 値または β 値の初期値が更新されたかどうか | × | 〇 | × | × | × |
| α 狩りまたは β 狩りが行われたかどうか | × | × | × | 〇 | × |
| ノードの評価値の種類 | × | × | × | × | 〇 |
| 計算された範囲 | × | × | × | × | 〇 |
| 登録する範囲 | × | × | × | × | 〇 |
| （※）置換表に登録されていた評価値 | × | 〇 | × | × | × |
| （※）そのフレームでのノードの評価値 | × | × | 〇 | 〇 | 〇 |
| （※）子ノードの評価値 | × | × | 〇 | × | × |
| （※）ノードの評価値が更新されたかどうか | × | × | × | 〇 | × |
calc_score_for_anim の修正
表示に必要なデータが整理できたので、上記のデータを記録する ように calc_score_for_anim を修正 することにします。
必要なデータを記録する dict のデータ構造
下記の表は ablist_by_score に記録する フレームの情報を表す dict に どのように上記の表のデータを記録するか を表した表です。（※）はミニマックス法でも記録していましたが、ミニマックス法とは異なるフレームの状態でも記録する という点が異なります。
| キー | キーの値の意味 |
|---|---|
| "alphaorig" | α 値の初期値 |
| "betaorig" | β 値の初期値 |
| "registered_in_tt" | （※）置換表にノードの評価値が登録されていたかどうか |
| "lower_bound" | （※）置換表の範囲の下界 |
| "upper_bound" | （※）置換表の範囲の上界 |
| "tt_pruned" | 置換表による枝狩りが行われたかどうか |
| "ab_updated" | α 値または β 値の初期値が更新されたかどうか |
| "ab_pruned" | α 狩りまたは β 狩りが行われたかどうか |
| "score_type" | ノードの評価値の種類 |
| "clower_bound" | 計算された範囲の下界 |
| "cupper_bound" | 計算された範囲の上界 |
| "tlower_bound" | 登録する範囲の下界 |
| "tupper_bound" | 登録する範囲の上界 |
ミニマックス法 では 枝狩りは置換表に登録されている場合のみ行われる ので 置換表に登録されているかどうか を "pruned" というキーの値に代入していました。αβ 法の場合 は 枝狩りは 置換表に登録されている場合と、α 狩りまたは β 狩りが行われる場合の 2 種類がある ので、上記の表のように 置換表（transposition table）によって 枝狩りが行われたかどうかを "tt_pruned"、α 狩りまたは β 仮によって 枝狩りが行われたかどうかを "ab_pruned" という名前の キーで区別する ことにします。
Mbtree クラスの calc_score_for_anim メソッドの修正
下記は上記のデータを記録するように Mbtree クラスの calc_score_for_anim メソッドを修正したプログラムです。非常に長いように見えるかもしれませんが、行っている修正はそれほど難しいものではありません。
- 6 ~ 12、44 ~ 55、69 ~ 80、98 ~ 110、144 ~ 160 行目：それぞれの状態で必要な情報を記録するように修正する
-
15 行目：置換表によって枝狩りが行われたかどうかを表す変数
tt_prunedをFalseで初期化する。元のプログラムではこの情報は "tt" のフレームのみで記録していたので 17 行目の後で初期化を行っていたが、"end" のフレームでも記録するようになったので 16 行目の if 文の前に移動した。また、変数の名前を"tt_pruned"に修正した -
26、29、32、41、48、60 行目：
prunedをtt_prunedに修正した -
18、34 行目：18 行目で α 値または β 値の初期値が更新されたかどうかを表す
ab_updatedをFalseで初期化し、34 行目で更新された場合にTrueを代入する -
56 ~ 58 行目：
lower_boundとupper_boundを "tt" 以外の状態でも記録するようになったので、置換表を利用しない場合のlower_boundとupper_boundの値に置換表に登録されていない場合の 38、39 行目と同じ値を代入するように修正した -
63 行目：元のプログラムでは
prunedという 1 つの変数で枝狩りが行われたことを表していたが、枝狩りの区別を行う必要が生じたので α 狩りまたは β 狩りが行われたことを表すab_prunedをFalseで初期化するように修正した -
86、92、94、111 行目：
prunedをab_prunedに修正した -
114 ~ 133 行目：元のプログラムでは置換表を利用する場合のみ下界と上界を更新する処理を行っていたが、その処理を常に行うようにし、下記の計算を行うように修正した。なお、置換表を利用しない場合など、下記で計算した値が Mbtree_Anim での表示で利用されない場合があるが、利用しない値を計算して記録してもそれらの記録が無駄になるだけで間違った処理が行われるという問題は発生しない
- 評価値の種類表す文字列を
score_typeに代入する。ただし、登録する範囲が範囲を持たない場合は 132、133 行目の処理で "exact value" とした - 計算された範囲を
clower_boundとcupper_boundに計算するようにした - 登録する範囲を
tlower_boundとtupper_boundに計算するようにした
- 評価値の種類表す文字列を
-
140 行目：
lower_boundとupper_boundをtlower_boundとtupper_boundに修正した
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.ablist_by_score.append({
7 "status": "start",
8 "alphaorig": alphaorig,
9 "betaorig": betaorig,
10 "num_calculated": self.num_calculated,
11 "num_pruned": self.num_pruned,
12 })
13
14 registered_in_tt = False
15 tt_pruned = False
16 if node.mb.status != Marubatsu.PLAYING:
元と同じなので省略
17 else:
18 ab_updated = False
19 if use_tt:
20 boardtxt = node.mb.board_to_str()
21 if boardtxt in tt:
22 registered_in_tt = True
23 lower_bound, upper_bound = tt[boardtxt]
24 if lower_bound == upper_bound:
25 node.score = lower_bound
26 tt_pruned = True
27 elif upper_bound <= alphaorig:
28 node.score = upper_bound
29 tt_pruned = True
30 elif betaorig <= lower_bound:
31 node.score = lower_bound
32 tt_pruned = True
33 else:
34 ab_updated = alphaorig > lower_bound or betaorig < upper_bound
35 alphaorig = min(alphaorig, lower_bound)
36 betaorig = max(betaorig, upper_bound)
37 else:
38 lower_bound = min_score
39 upper_bound = max_score
40 self.nodelist_by_score.append(node)
41 if tt_pruned:
42 for childnode in node.children:
43 assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
44 self.ablist_by_score.append({
45 "status": "tt",
46 "alphaorig": alphaorig,
47 "betaorig": betaorig,
48 "tt_pruned": tt_pruned,
49 "ab_updated": ab_updated,
50 "registered_in_tt": registered_in_tt,
51 "lower_bound": lower_bound,
52 "upper_bound": upper_bound,
53 "num_calculated": self.num_calculated,
54 "num_pruned": self.num_pruned,
55 })
56 else:
57 lower_bound = min_score
58 upper_bound = max_score
59
60 if not tt_pruned:
61 alpha = alphaorig
62 beta = betaorig
63 ab_pruned = False
64 maxnode = node.mb.turn == Marubatsu.CIRCLE
65 node.score = min_score if maxnode else max_score
66 for childnode in node.children:
67 childscore = calc_node_score(childnode, tt, alpha, beta)
68 self.nodelist_by_score.append(node)
69 self.ablist_by_score.append({
70 "status": "score",
71 "alphaorig": alphaorig,
72 "betaorig": betaorig,
73 "score": node.score,
74 "childscore": childscore,
75 "registered_in_tt": registered_in_tt,
76 "lower_bound": lower_bound,
77 "upper_bound": upper_bound,
78 "num_calculated": self.num_calculated,
79 "num_pruned": self.num_pruned,
80 })
81 if maxnode:
82 updated = node.score < childscore
83 node.score = max(node.score, childscore)
84 alpha = max(node.score, alpha)
85 if node.score >= beta:
86 ab_pruned = True
87 else:
88 updated = node.score > childscore
89 node.score = min(node.score, childscore)
90 beta = min(node.score, beta)
91 if node.score <= alpha:
92 ab_pruned = True
93 self.nodelist_by_score.append(node)
94 if ab_pruned:
95 index = node.children.index(childnode)
96 for prunednode in node.children[index + 1:]:
97 assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
98 self.ablist_by_score.append({
99 "status": "update",
100 "alphaorig": alphaorig,
101 "betaorig": betaorig,
102 "score": node.score,
103 "registered_in_tt": registered_in_tt,
104 "updated": updated,
105 "ab_pruned": ab_pruned,
106 "lower_bound": lower_bound,
107 "upper_bound": upper_bound,
108 "num_calculated": self.num_calculated,
109 "num_pruned": self.num_pruned,
110 })
111 if ab_pruned:
112 break
113
114 if node.score <= alphaorig:
115 score_type = "fail low"
116 clower_bound = min_score
117 cupper_bound = node.score
118 tlower_bound = lower_bound
119 tupper_bound = node.score
120 elif node.score < betaorig:
121 score_type = "exact value"
122 clower_bound = node.score
123 cupper_bound = node.score
124 tlower_bound = node.score
125 tupper_bound = node.score
126 else:
127 score_type = "fail high"
128 clower_bound = node.score
129 cupper_bound = max_score
130 tlower_bound = node.score
131 tupper_bound = upper_bound
132 if tlower_bound == tupper_bound:
133 score_type = "exact value"
134
135 if use_tt:
136 from util import calc_same_boardtexts
137
138 boardtxtlist = calc_same_boardtexts(node.mb)
139 for boardtxt in boardtxtlist:
140 tt[boardtxt] = (tlower_bound, tupper_bound)
141
142 self.nodelist_by_score.append(node)
143 self.num_calculated += 1
144 self.ablist_by_score.append({
145 "status": "end",
146 "alphaorig": alphaorig,
147 "betaorig": betaorig,
148 "score": node.score,
149 "registered_in_tt": registered_in_tt,
150 "tt_pruned": tt_pruned,
151 "score_type": score_type,
152 "lower_bound": lower_bound,
153 "upper_bound": upper_bound,
154 "clower_bound": clower_bound,
155 "cupper_bound": cupper_bound,
156 "tlower_bound": tlower_bound,
157 "tupper_bound": tupper_bound,
158 "num_calculated": self.num_calculated,
159 "num_pruned": self.num_pruned,
160 })
161 node.score_index = len(self.nodelist_by_score) - 1
162 return node.score
163
元と同じなので省略
164
165 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",
"alphaorig": alphaorig,
"betaorig": betaorig,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
registered_in_tt = False
tt_pruned = False
if node.mb.status != Marubatsu.PLAYING:
self.calc_score_of_node(node)
lower_bound = node.score
upper_bound = node.score
else:
ab_updated = 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
tt_pruned = True
elif upper_bound <= alphaorig:
node.score = upper_bound
tt_pruned = True
elif betaorig <= lower_bound:
node.score = lower_bound
tt_pruned = True
else:
ab_updated = alphaorig > lower_bound or betaorig < upper_bound
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 tt_pruned:
for childnode in node.children:
assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
self.ablist_by_score.append({
"status": "tt",
"alphaorig": alphaorig,
"betaorig": betaorig,
"tt_pruned": tt_pruned,
"ab_updated": ab_updated,
"registered_in_tt": registered_in_tt,
"lower_bound": lower_bound,
"upper_bound": upper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
else:
lower_bound = min_score
upper_bound = max_score
if not tt_pruned:
alpha = alphaorig
beta = betaorig
ab_pruned = False
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",
"alphaorig": alphaorig,
"betaorig": betaorig,
"score": node.score,
"childscore": childscore,
"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 maxnode:
updated = node.score < childscore
node.score = max(node.score, childscore)
alpha = max(node.score, alpha)
if node.score >= beta:
ab_pruned = True
else:
updated = node.score > childscore
node.score = min(node.score, childscore)
beta = min(node.score, beta)
if node.score <= alpha:
ab_pruned = True
self.nodelist_by_score.append(node)
if ab_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",
"alphaorig": alphaorig,
"betaorig": betaorig,
"score": node.score,
"registered_in_tt": registered_in_tt,
"updated": updated,
"ab_pruned": ab_pruned,
"lower_bound": lower_bound,
"upper_bound": upper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
if ab_pruned:
break
if node.score <= alphaorig:
score_type = "fail low"
clower_bound = min_score
cupper_bound = node.score
tlower_bound = lower_bound
tupper_bound = node.score
elif node.score < betaorig:
score_type = "exact value"
clower_bound = node.score
cupper_bound = node.score
tlower_bound = node.score
tupper_bound = node.score
else:
score_type = "fail high"
clower_bound = node.score
cupper_bound = max_score
tlower_bound = node.score
tupper_bound = upper_bound
if tlower_bound == tupper_bound:
score_type = "exact value"
if use_tt:
from util import calc_same_boardtexts
boardtxtlist = calc_same_boardtexts(node.mb)
for boardtxt in boardtxtlist:
tt[boardtxt] = (tlower_bound, tupper_bound)
self.nodelist_by_score.append(node)
self.num_calculated += 1
self.ablist_by_score.append({
"status": "end",
"alphaorig": alphaorig,
"betaorig": betaorig,
"score": node.score,
"registered_in_tt": registered_in_tt,
"tt_pruned": tt_pruned,
"score_type": score_type,
"lower_bound": lower_bound,
"upper_bound": upper_bound,
"clower_bound": clower_bound,
"cupper_bound": cupper_bound,
"tlower_bound": tlower_bound,
"tupper_bound": tupper_bound,
"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.ablist_by_score.append({
"status": "start",
+ "alphaorig": alphaorig,
+ "betaorig": betaorig,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
registered_in_tt = False
+ tt_pruned = False
if node.mb.status != Marubatsu.PLAYING:
元と同じなので省略
else:
- pruned = False
+ ab_updated = 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
+ tt_pruned = True
elif upper_bound <= alphaorig:
node.score = upper_bound
- pruned = True
+ tt_pruned = True
elif betaorig <= lower_bound:
node.score = lower_bound
- pruned = True
+ tt_pruned = True
else:
ab_updated = alphaorig > lower_bound or betaorig < upper_bound
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:
+ if tt_pruned:
for childnode in node.children:
assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
self.ablist_by_score.append({
"status": "tt",
+ "alphaorig": alphaorig,
+ "betaorig": betaorig,
+ "tt_pruned": tt_pruned,
+ "ab_updated": ab_updated,
+ "registered_in_tt": registered_in_tt,
"lower_bound": lower_bound,
"upper_bound": upper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
+ else:
+ lower_bound = min_score
+ upper_bound = max_score
- if not pruned:
+ if not tt_pruned:
alpha = alphaorig
beta = betaorig
+ ab_pruned = False
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",
+ "alphaorig": alphaorig,
+ "betaorig": betaorig,
"score": node.score,
"childscore": childscore,
+ "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 maxnode:
updated = node.score < childscore
node.score = max(node.score, childscore)
alpha = max(node.score, alpha)
if node.score >= beta:
- pruned = True
+ ab_pruned = True
else:
updated = node.score > childscore
node.score = min(node.score, childscore)
beta = min(node.score, beta)
if node.score <= alpha:
- pruned = True
+ ab_pruned = True
self.nodelist_by_score.append(node)
- if pruned:
+ if ab_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",
+ "alphaorig": alphaorig,
+ "betaorig": betaorig,
"score": node.score,
+ "registered_in_tt": registered_in_tt,
"updated": updated,
+ "ab_pruned": ab_pruned,
+ "lower_bound": lower_bound,
+ "upper_bound": upper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
- if pruned:
+ if ab_pruned:
break
+ if node.score <= alphaorig:
+ score_type = "fail low"
+ clower_bound = min_score
+ cupper_bound = node.score
+ tlower_bound = lower_bound
+ tupper_bound = node.score
+ elif node.score < betaorig:
+ score_type = "exact value"
+ clower_bound = node.score
+ cupper_bound = node.score
+ tlower_bound = node.score
+ tupper_bound = node.score
+ else:
+ score_type = "fail high"
+ clower_bound = node.score
+ cupper_bound = max_score
+ tlower_bound = node.score
+ tupper_bound = upper_bound
+ if tlower_bound == tupper_bound:
+ score_type = "exact value"
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)
+ tt[boardtxt] = (tlower_bound, tupper_bound)
self.nodelist_by_score.append(node)
self.num_calculated += 1
self.ablist_by_score.append({
"status": "end",
+ "alphaorig": alphaorig,
+ "betaorig": betaorig,
"score": node.score,
"registered_in_tt": registered_in_tt,
+ "tt_pruned": tt_pruned,
+ "score_type": score_type,
+ "lower_bound": lower_bound,
+ "upper_bound": upper_bound,
+ "clower_bound": clower_bound,
+ "cupper_bound": cupper_bound,
+ "tlower_bound": tlower_bound,
+ "tupper_bound": tupper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
node.score_index = len(self.nodelist_by_score) - 1
return node.score
元と同じなので省略
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_for_anim でミニマックス法で評価値を計算したデータに対して Mbtree_Anim で評価値の計算手順を表示すると、前回の記事と同じ表示が行われる ことが確認できます。実際に確認してみて下さい。
from tree import Mbtree_Anim
mbtree = Mbtree.load("../data/abtree_root")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, use_tt=True, shortest_victory=False)
Mbtree_Anim(mbtree, isscore=True)
今回の記事のまとめ
今回の記事では、calc_score_for_anim で αβ 法で評価値を計算したデータ を Mbtree_Anim で 視覚化する方法について検討 し、そのために 必要なデータを記録する ように calc_score_for_anim を修正 しました。
次回の記事では Mbtree_Anim を修正して実際の視覚化を行うことができるようにします。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| tree.py | 本記事で更新した tree_new.py |
次回の記事