目次と前回の記事

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

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

リンク	説明
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 の修正

前回の記事では calc_score_for_anim で行ったミニマックス法の計算手順の視覚化の検討と、視覚化に必要なデータの記録の実装を行いました。今回の記事では Mbtree_Anim を修正してミニマックス法の視覚化 を行います。

視覚化の検討のおさらい

前回の記事で行ったミニマックス法の視覚化と、フレームに記録するデータの検討結果は以下の通りです。

常に表示する内容

常に表示する内容と、表示するために必要な情報は以下の表の通りです。なお、mbtree は calc_score_for_anim で計算した 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_Anim と同様に 状態の種類によって背景色を変える ことにします。

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

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

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

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

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

フレームに記録するデータ

calc_score_for_anim が記録する フレームのデータを表す dict の内容 は以下の通りです。

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

上記で検討したように表示を行うために、Mbtree_Anim をどのように修正すれば良いかについて少し考えてみて下さい。

`calc_score_by_ab` と `calc_score_for_anim` への両対応

前回の記事では、互換性を重視 して Mbtree_Anim が calc_score_by_ab と calc_score_for_anim の両方のメソッドで作成されたデータに 対応する ように修正することにしました。また、どちらのメソッドで作成された データであるかを判定するために、calculated_by_calc_score_for_animという名前の属性を導入 しました。

そこで、calc_score_by_ab で作成されたデータに対しては 従来通りの方法で視覚化 を行い、calc_score_for_anim で作成されたデータに対しては 前回の記事で検討した方法で視覚化 を行うように Mbtree_Anim を修正する必要があります。

`init` メソッドの修正

前回の記事のノートで言及したように "../data/abtree_root.mbtree" などの、前回の記事で修正する前の calc_score_by_ab で作成 したゲーム木のデータには calculated_by_calc_score_for_anim 属性は存在していません。従って、それらのデータにも対応 できるようにするためには、下記のプログラムのようにゲーム木のデータの calculated_by_calc_score_for_anim 属性が存在しない場合は False を代入する ように __init__ メソッドを修正する 必要があります。

5 行目：組み込み関数 getattr を利用して calculated_by_calc_score_for_anim 属性が self.mbtree に存在しない場合 は、その属性に False を代入する ように修正する

 1  from tree import Mbtree_Anim
 2  
 3  def __init__(self, mbtree, isscore, size=0.15):
 4      self.mbtree = mbtree
 5      self.mbtree.calculated_by_calc_score_for_anim = \
 6                   getattr(self.mbtree, "calculated_by_calc_score_for_anim", False)
元と同じなので省略
 7      
 8  Mbtree_Anim.__init__ = __init__

行番号のないプログラム

from tree import Mbtree_Anim

def __init__(self, mbtree, isscore, size=0.15):
    self.mbtree = mbtree
    self.mbtree.calculated_by_calc_score_for_anim = \
                getattr(self.mbtree, "calculated_by_calc_score_for_anim", False)
    self.isscore = isscore
    self.size = size
    self.width = 50
    self.height = 65
    self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
    self.nodenum = len(self.nodelist)
    self.prev_frame = 0
    super(Mbtree_Anim, self).__init__()
    
Mbtree_Anim.__init__ = __init__

修正箇所

from tree import Mbtree_Anim

def __init__(self, mbtree, isscore, size=0.15):
    self.mbtree = mbtree
+   self.mbtree.calculated_by_calc_score_for_anim = \
+               getattr(self.mbtree, "calculated_by_calc_score_for_anim", False)
元と同じなので省略
    
Mbtree_Anim.__init__ = __init__

`create_event_handler` メソッドの修正

calc_score_by_ab と calc_score_for_anim では、ablist_by_score の要素 に記録したフレームの情報の データ型 が tuple と dict のように 異なっています。そのため、ablist_by_score に関する処理を修正 する必要があります。

どこを修正すれば良いかについては、Ctrl + F キーで呼びだせる VSCode の検索機能 を使って、tree.py 内の Mbtree_Anim の定義の中で記述 されている ablist_by_score の処理を検索 すると良いでしょう。検索を行うと create_event_handler 内で ablist_by_score の処理が行われていることがわかるので、create_event_handler を修正する必要があります。

create_widgets メソッド内でも下記のプログラムのように ablist_by_score の処理が記述されていますが、この処理は self.mbtree が ablist_by_score という属性を持っているかどうかを判定する処理を行っており、ablist_by_score の内容に関する処理を行っていない ので 修正する必要はありません。

    if self.isscore and hasattr(self.mbtree, "ablist_by_score"):

また、calc_score_by_ab では、置換表にノードの評価値が登録されていた場合は "tt" のフレームしか記録しませんでしたが、以前の記事で calc_score_for_anim では 常に "start" と "end" のフレームを記録 するように修正しました。その結果、"tt" のフレーム は "start" の直後のフレームに記録 されることになりますが、現状の Mbtree_Anim では 下段の < ボタンや > ボタン をクリックした際に、"tt" のフレームが飛ばされてしまう ので、それらのボタンをクリックした際に "tt" のフレームを飛ばさないように修正 する必要があります。

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

5 ~ 8、14 ~ 17 行目：calc_score_by_ab ではフレームの状態は ablist_by_score に記録されたフレームの情報を表す tuple の 3 番の要素に代入されていたが、calc_score_for_anim では dict の "status" のキーの値に代入されているので、calculated_by_calc_score_for_anim 属性の値によってフレームの状態を正しく変数に代入できるように修正した
27 ~ 30、33 ~ 36 行目：下段の < と > ボタンをクリックした際に、calc_score_for_anim で計算されたデータの場合は "tt" のフレームにも移動するように修正した。chage_frame の処理について忘れた方は、以前の記事を復習すること

 1  def create_event_handler(self):
元と同じなので省略
 2      def change_frame(edge_status, diff, status_list):
 3          frame = self.play.value
 4          selectednode = self.mbtree.nodelist_by_score[frame]
 5          if self.mbtree.calculated_by_calc_score_for_anim:
 6              selectedstatus = self.mbtree.ablist_by_score[frame]["status"]
 7          else:
 8              selectedstatus = self.mbtree.ablist_by_score[frame][3]
 9          if selectedstatus == edge_status:
10              return
11          while True:
12              frame += diff
13              node = self.mbtree.nodelist_by_score[frame]
14              if self.mbtree.calculated_by_calc_score_for_anim:
15                  status = self.mbtree.ablist_by_score[frame]["status"]
16              else:
17                  status = self.mbtree.ablist_by_score[frame][3]
18              if node == selectednode and status in status_list:
19                  break
20          self.play.value = frame
21          self.update_gui()
22              
23      def on_node_first_button_clicked(b=None):
24          change_frame("start", -1, ["start"])
25              
26      def on_node_prev_button_clicked(b=None):
27          if self.mbtree.calculated_by_calc_score_for_anim:
28              change_frame("start", -1, ["start", "score", "tt"])
29          else:
30              change_frame("start", -1, ["start", "score"])
31  
32      def on_node_next_button_clicked(b=None):
33          if self.mbtree.calculated_by_calc_score_for_anim:
34              change_frame("end", 1, ["end", "score", "tt"])
35          else:
36              change_frame("end", 1, ["end", "score"])
元と同じなので省略
37  
38  Mbtree_Anim.create_event_handler = create_event_handler

行番号のないプログラム

def create_event_handler(self):
    def on_play_changed(changed):
        self.prev_frame = changed.old
        self.update_gui()
            
    def on_prev_button_clicked(b=None):
        self.play.value -= 1
        self.update_gui()
        
    def on_next_button_clicked(b=None):
        self.play.value += 1
        self.update_gui()

    self.prev_button.on_click(on_prev_button_clicked)
    self.next_button.on_click(on_next_button_clicked)

    self.play.observe(on_play_changed, names="value")
    
    def change_frame(edge_status, diff, status_list):
        frame = self.play.value
        selectednode = self.mbtree.nodelist_by_score[frame]
        if self.mbtree.calculated_by_calc_score_for_anim:
            selectedstatus = self.mbtree.ablist_by_score[frame]["status"]
        else:
            selectedstatus = self.mbtree.ablist_by_score[frame][3]
        if selectedstatus == edge_status:
            return
        while True:
            frame += diff
            node = self.mbtree.nodelist_by_score[frame]
            if self.mbtree.calculated_by_calc_score_for_anim:
                status = self.mbtree.ablist_by_score[frame]["status"]
            else:
                status = self.mbtree.ablist_by_score[frame][3]
            if node == selectednode and status in status_list:
                break
        self.play.value = frame
        self.update_gui()
            
    def on_node_first_button_clicked(b=None):
        change_frame("start", -1, ["start"])
            
    def on_node_prev_button_clicked(b=None):
        if self.mbtree.calculated_by_calc_score_for_anim:
            change_frame("start", -1, ["start", "score", "tt"])
        else:
            change_frame("start", -1, ["start", "score"])

    def on_node_next_button_clicked(b=None):
        if self.mbtree.calculated_by_calc_score_for_anim:
            change_frame("end", 1, ["end", "score", "tt"])
        else:
            change_frame("end", 1, ["end", "score"])
        
    def on_node_last_button_clicked(b=None):
        change_frame("end", 1, ["end"])
    
    if self.abfig is not None:
        self.node_first_button.on_click(on_node_first_button_clicked)
        self.node_prev_button.on_click(on_node_prev_button_clicked)
        self.node_next_button.on_click(on_node_next_button_clicked)
        self.node_last_button.on_click(on_node_last_button_clicked)

Mbtree_Anim.create_event_handler = create_event_handler

修正箇所

def create_event_handler(self):
元と同じなので省略
    def change_frame(edge_status, diff, status_list):
        frame = self.play.value
        selectednode = self.mbtree.nodelist_by_score[frame]
-       selectedstatus = self.mbtree.ablist_by_score[frame][3]
+       if self.mbtree.calculated_by_calc_score_for_anim:
+           selectedstatus = self.mbtree.ablist_by_score[frame]["status"]
+       else:
+           selectedstatus = self.mbtree.ablist_by_score[frame][3]
        if selectedstatus == edge_status:
            return
        while True:
            frame += diff
            node = self.mbtree.nodelist_by_score[frame]
-           status = self.mbtree.ablist_by_score[frame][3]
+           if self.mbtree.calculated_by_calc_score_for_anim:
+               status = self.mbtree.ablist_by_score[frame]["status"]
+           else:
+               status = self.mbtree.ablist_by_score[frame][3]
            if node == selectednode and status in status_list:
                break
        self.play.value = frame
        self.update_gui()
            
    def on_node_first_button_clicked(b=None):
        change_frame("start", -1, ["start"])
            
    def on_node_prev_button_clicked(b=None):
-       change_frame("start", -1, ["start", "score"])
+       if self.mbtree.calculated_by_calc_score_for_anim:
+           change_frame("start", -1, ["start", "score", "tt"])
+       else:
+           change_frame("start", -1, ["start", "score"])

    def on_node_next_button_clicked(b=None):
-       change_frame("end", 1, ["end", "score"])
+       if self.mbtree.calculated_by_calc_score_for_anim:
+           change_frame("end", 1, ["end", "score", "tt"])
+       else:
+           change_frame("end", 1, ["end", "score"])
元と同じなので省略

Mbtree_Anim.create_event_handler = create_event_handler

`update_gui` メソッドの修正

ablist_by_score の処理は updata_gui メソッドでも行われているので修正を行います。

一つ目の修正は、下段の <<、<、>、>> ボタンの状態 に関する処理です。calc_score_by_ab で作成したデータでは、ノードの情報が置換表に記録されていた場合は "tt" のフレームしか存在しませんでした。そのため、"tt" のフレームが表示されている場合は 4 つすべてのボタンを押せないようにしていました。一方、calc_score_for_anim で作成されたデータ の場合は、"tt" のフレーム は "start" と "end" のフレームの間に配置 されるので、"tt" のフレームでは 4 つのボタンを全て押せる ように修正する必要があります。

もう一つの修正は、calc_score_by_ab で作成されたデータと calc_score_for_anim で作成されたデータでは、ゲーム木の上部の フレームの情報の表示内容が全く異なる ので、calc_score_by_ab で作成されたデータの場合は これまで通り update_ab で表示 を行い、calc_score_for_anim で作成されたデータの場合は update_frameinfo というこの後で定義する別のメソッドで 表示を行う ように修正する点です。なお、メソッドの名前はフレーム（frame）の情報（information）を表示する事からそのように命名しました。

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

4、9 行目：calc_score_for_anim で作成されたデータの場合は update_frameinfo を、そうでない場合はこれまで通り update_ab を呼び出すように修正した
5、10 行目：先程と同様に ablist_by_score から状況に応じてフレームの状態のデータを正しく取得するように修正した
6、7、11 ~ 16 行目：<< と < ボタンの状態を disabled、> と >> ボタンの状態を disabled2 という変数で計算し、13 ~ 16 行目ではその変数を利用してそれぞれのボタンの状態を設定するように修正した。calc_score_for_anim で作成されたデータの場合は、"tt" の状態ですべてのボタンを押すことができるようにしている

 1  def update_gui(self):
元と同じなので省略
 2      if self.abfig is not None:
 3          if self.mbtree.calculated_by_calc_score_for_anim:
 4              self.update_frameinfo()
 5              status = self.mbtree.ablist_by_score[self.play.value]["status"]
 6              disabled = status == "start"
 7              disabled2 = status == "end"
 8          else:
 9              self.update_ab()
10              status = self.mbtree.ablist_by_score[self.play.value][3]
11              disabled = status == "start" or status == "tt"
12              disabled2 = status == "end" or status == "tt"
13          self.set_button_status(self.node_first_button, disabled=disabled)
14          self.set_button_status(self.node_prev_button, disabled=disabled)
15          self.set_button_status(self.node_next_button, disabled=disabled2)
16          self.set_button_status(self.node_last_button, disabled=disabled2)
元と同じなので省略
17      
18  Mbtree_Anim.update_gui = update_gui
19

行番号のないプログラム

def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(-1, self.height - 1)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    self.selectednode = self.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.mbtree.algo == "bf":
        if self.centernode.depth > 0:
            self.centernode = self.centernode.parent
    while self.centernode.depth > 6:
        self.centernode = self.centernode.parent
    if self.centernode.depth <= 4:
        maxdepth = self.centernode.depth + 1
    elif self.centernode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode,
                            anim_frame=self.play.value, isscore=self.isscore, 
                            ax=self.ax, maxdepth=maxdepth, size=self.size)
    if self.abfig is not None:
        if self.mbtree.calculated_by_calc_score_for_anim:
            self.update_frameinfo()
            status = self.mbtree.ablist_by_score[self.play.value]["status"]
            disabled = status == "start"
            disabled2 = status == "end"
        else:
            self.update_ab()
            status = self.mbtree.ablist_by_score[self.play.value][3]
            disabled = status == "start" or status == "tt"
            disabled2 = status == "end" or status == "tt"
        self.set_button_status(self.node_first_button, disabled=disabled)
        self.set_button_status(self.node_prev_button, disabled=disabled)
        self.set_button_status(self.node_next_button, disabled=disabled2)
        self.set_button_status(self.node_last_button, disabled=disabled2)

    disabled = self.play.value == 0
    self.set_button_status(self.prev_button, disabled=disabled)
    disabled = self.play.value == self.nodenum - 1
    self.set_button_status(self.next_button, disabled=disabled)
    
Mbtree_Anim.update_gui = update_gui

修正箇所

def update_gui(self):
元と同じなので省略
    if self.abfig is not None:
-       self.update_ab()
-       status = self.mbtree.ablist_by_score[self.play.value][3]
+       if self.mbtree.calculated_by_calc_score_for_anim:
+           self.update_frameinfo()
+           status = self.mbtree.ablist_by_score[self.play.value]["status"]
+           disabled = status == "start"
+           disabled2 = status == "end"
+       else:
+           self.update_ab()
+           status = self.mbtree.ablist_by_score[self.play.value][3]
+           disabled = status == "start" or status == "tt"
+           disabled2 = status == "end" or status == "tt"
-       disabled = status == "start" or status == "tt"
        self.set_button_status(self.node_first_button, disabled=disabled)
        self.set_button_status(self.node_prev_button, disabled=disabled)
-       disabled2 = status == "end" or status == "tt"
-       self.set_button_status(self.node_next_button, disabled=disabled)
-       self.set_button_status(self.node_last_button, disabled=disabled)
+       self.set_button_status(self.node_next_button, disabled=disabled2)
+       self.set_button_status(self.node_last_button, disabled=disabled2)
元と同じなので省略
    
Mbtree_Anim.update_gui = update_gui

`update_frameinfo` の定義

次に、calc_score_for_anim で作成したデータの フレームの情報を描画 する update_frameinfo メソッドを定義します。まず、常に表示する内容を実装し、その後でそれぞれの状態で表示する内容を実装します。

常に表示する内容の実装

まず、先程説明した常に表示する内容の表示を実装します。それぞれの実装方法について少し考えてみて下さい。

数直線の描画

先程の表では「設定された条件の表示」を表の最初に表記しましたが、本記事では一番左に表示する 数直線の描画から実装 することにします。

数直線には無限大と正の無限大の間に、以下の 評価値の最小値と最大値の範囲 を表示する必要があります。どのようにプログラムを記述すれば良いかについて少し考えてみて下さい。

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

下記はそのような数直線を描画する update_frame_info メソッドの定義です。

2 ~ 5 行目：Axes の表示のクリア、表示範囲の設定、軸の表示の消去を行う。update_ab 内の処理と同じ
7、8 行目：負の無限大と正の無限大 の 数直線上の座標 をそれぞれ「評価値の最小値 - 1」、「評価値の最大値 + 1」として計算する
10 ~ 19 行目：数直線を描画する。この部分の処理について忘れた方は以前の記事を復習すること

 1  def update_frameinfo(self):
 2      self.abax.clear()
 3      self.abax.set_xlim(-4, 23)
 4      self.abax.set_ylim(-1.5, 1.5)
 5      self.abax.axis("off")
 6  
 7      minus_inf = -3 if self.mbtree.shortest_victory else -2
 8      plus_inf = 4 if self.mbtree.shortest_victory else 2
 9  
10      # 数直線の描画    
11      self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
12      for num in range(minus_inf, plus_inf + 1):
13          if num == minus_inf:
14              numtext = "-∞"
15          elif num == plus_inf:
16              numtext = "∞"
17          else:
18              numtext = num
19          self.abax.text(num, -1, numtext, ha="center")        
20  
21  Mbtree_Anim.update_frameinfo = update_frameinfo

行番号のないプログラム

def update_frameinfo(self):
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3 if self.mbtree.shortest_victory else -2
    plus_inf = 4 if self.mbtree.shortest_victory else 2

    # 数直線の描画    
    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

Mbtree_Anim.update_frameinfo = update_frameinfo

上記の修正後に下記のプログラムで calc_score_by_ab で計算されたゲーム木のデータを Mbtree_Anim で視覚化を行うと、実行結果のように これまで通りの視覚化 が行われることが確認できます。なお、ゲーム木の部分の表示は省略しました。余裕がある方は、他のフレームでもこれまで通りの表示が行われるかを確認してみて下さい。

from tree import Mbtree

mbtree = Mbtree.load("../data/abtree_root")
Mbtree_Anim(mbtree, isscore=True)

実行結果

次に、下記のプログラムで calc_score_for_anim で ミニマックス法 で 最短の勝利を目指さない という条件で計算を行った場合は、実行結果のように 数直線の範囲が正しく描画される ことが確認できます。

mbtree.calc_score_for_anim(mbtree.root, minimax=True, shortest_victory=False)
Mbtree_Anim(mbtree, isscore=True)

実行結果

下記のプログラムを実行すると、最短の勝利を目指す場合 も実行結果のように 数直線の範囲が正しく描画される ことが確認できます。

mbtree.calc_score_for_anim(mbtree.root, minimax=True, shortest_victory=True)
Mbtree_Anim(mbtree, isscore=True)

実行結果

設定された条件の表示

前回の記事で説明したように、設定された条件 は下記のように表示します。

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

update_ab では真ん中の 1 行目に「深さ 0 max node」という表示を行い、その下に α 値と β 値によって分けられる 3 つの評価値の範囲に関する表示を行っていましたが、ミニマックス法 では α 値と β 値は利用しない ため 評価値の範囲に関する表示 を 行う必要はありません。そのため、真ん中に表示するメッセージ は update_ab の場合と比べて 少なくて済みます。そこで、update_frameinfo では 真ん中の 1 行目 に 設定された条件を表示 することにします。また、update_ab では真ん中の 1 行目に表示する内容と、その下の行で表示する内容を別の処理で行なっていましたが、update_frameinfo では まとめて表示する といという工夫を行なうことにします。

下記は update_frameinfo にその処理を記述したプログラムです。

5 行目：真ん中に表示するメッセージの行数を変数に代入する。ミニマックス法では真ん中に最大で 4 行分表示することになるので 4 を設定した
6、7 行目：真ん中に表示するメッセージの一覧とメッセージの色の一覧を表す変数を、すべての行が空文字と黒色を表すような list で初期化する
9 ~ 15 行目：1 行目に表示する文字列を計算し、1 行目に表示する文字列を表す textlist[0] に代入する。その際に 13 ~ 15 行目の処理で αβ 法の場合のみ init_ab に対応する表示を行うようにしている
17、18 行目：linenum の行の数だけメッセージを描画する。行なっている処理は、表示する座標を少し調整した点と、αβ 法での評価値の範囲の色を表す長方形を表示しない点以外は update_ab で行なっている処理とほぼ同じである

 1  def update_frameinfo(self):
 2      数直線の描画処理
 3  
 4      # メッセージの表示
 5      linenum = 4
 6      textlist = [""] * linenum
 7      textcolorlist = ["black"] * linenum
 8  
 9      algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
10      use_tt = "〇" if self.mbtree.use_tt else "×"
11      shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
12      init_ab = "〇" if self.mbtree.init_ab else "×"
13      textlist[0] = f"{algorithm}　置換表 {use_tt}　最短 {shortest_victory}"
14      if not self.mbtree.minimax:
15          textlist[0] += f"　初期値 {init_ab}"
16  
17      for i in range(linenum):
18          self.abax.text(5, 1 - i * 0.7, textlist[i], c=textcolorlist[i])
19  
20  Mbtree_Anim.update_frameinfo = update_frameinfo

行番号のないプログラム

def update_frameinfo(self):
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3 if self.mbtree.shortest_victory else -2
    plus_inf = 4 if self.mbtree.shortest_victory else 2

    # 数直線の描画    
    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

    # メッセージの表示
    linenum = 4
    textlist = [""] * linenum
    textcolorlist = ["black"] * linenum

    algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
    use_tt = "〇" if self.mbtree.use_tt else "×"
    shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
    init_ab = "〇" if self.mbtree.init_ab else "×"
    textlist[0] = f"{algorithm}　置換表 {use_tt}　最短 {shortest_victory}"
    if not self.mbtree.minimax:
        textlist[0] += f"　初期値 {init_ab}"

    for i in range(linenum):
        self.abax.text(5, 1 - i * 0.7, textlist[i], c=textcolorlist[i])

Mbtree_Anim.update_frameinfo = update_frameinfo

上記を実行後に いくつかの設定でプログラムを実行 することで、設定した条件の部分が正しく表示されることを確認しすることにします。

下記は ミニマックス法、置換表を利用しない、最短の勝利を目指す 場合で、実行結果のように 意図通りの表示が行われている ことが確認できます。なお、ミニマックス法では init_ab に対する表示は行いません。

mbtree.calc_score_for_anim(mbtree.root, minimax=True, shortest_victory=True, init_ab=True)
Mbtree_Anim(mbtree, isscore=True)

実行結果

下記は αβ 法、置換表を利用する、最短の勝利を目指さない、α 値と β 値の初期値を設定する 場合で、実行結果のように 意図通りの表示が行われている ことが確認できます。なお、αβ 法なので init_ab に対する表示が行なわれています。

mbtree.calc_score_for_anim(mbtree.root, minimax=False, use_tt=True,
                           shortest_victory=False, init_ab=True)
Mbtree_Anim(mbtree, isscore=True)

実行結果

深さ、ノードの種類、フレームの状態の表示

次に、update_ab で表示していた「深さ 0 max node 処理の開始」の表示と、フレームの状態に応じた背景色の表示処理を実装します。ただし、「深さとノードの種類の表示」と「フレームの状態の表示」を 同じ行に表示するのがわかりにくい 気がした点と、ミニマックス法では表示する内容が少ない点から、それらを別の行で表示 することにします。

下記は update_frameinfo にその処理を記述したプログラムです。処理の多くは update_ab と似ていますが、フレームの状態を表す文字列と背景色を表すデータを dict に代入して利用するなど、いくつかの点でプログラムの工夫を行ないました。

3 行目：このフレームの情報を表す dict を framedata に代入する
4 行目：このフレームの状態を status に代入する
5 行目：max ノードであるかどうかを計算して maxnode に代入する
11、12 行目：深さとノードの種類を表す文字列を計算して 1 行目の文字列を表す textlist[1] に代入する
14 ~ 35 行目：それぞれのフレームの状態の文字列と背景色を表す dict を変数に代入する
36 ~ 38 行目：上記の dict からフレームの状態を表す文字列と背景色を textlist[2] と facecolor に代入する。38 行目で set_facecolor メソッドを利用して背景色を変更する

 1  from marubatsu import Marubatsu
 2
 3  def update_frameinfo(self):
 4      framedata = self.mbtree.ablist_by_score[self.play.value]
 5      status = framedata["status"]
 6      maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
 7      
 8      数直線の描画処理
 9      1 行目の表示処理
10      
11      nodetype = "max node" if maxnode else "min node"
12      textlist[1] = f"深さ {self.selectednode.mb.move_count} {nodetype}"
13
14      statusdata = {
15          "start": {
16              "text": "処理の開始",
17              "color": "white"
18          },
19          "tt": {
20              "text": "置換表の処理",
21              "color": "honeydew"
22          },
23          "score": {
24              "text": "子ノードの評価値",
25              "color": "lightyellow"
26          },
27          "update": {
28              "text": "更新処理",
29              "color": "lightcyan"
30          },
31          "end": {
32              "text": "評価値の確定",
33              "color": "lavenderblush"
34          },
35      }
36      textlist[2] = statusdata[status]["text"]
37      facecolor = statusdata[status]["color"]
38  
39      self.abfig.set_facecolor(facecolor)
40      for i in range(linenum):
41          self.abax.text(5, 1 - i * 0.7, textlist[i], c=textcolorlist[i])
42  
43  Mbtree_Anim.update_frameinfo = update_frameinfo

行番号のないプログラム

from marubatsu import Marubatsu

def update_frameinfo(self):
    framedata = self.mbtree.ablist_by_score[self.play.value]
    status = framedata["status"]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE

    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3 if self.mbtree.shortest_victory else -2
    plus_inf = 4 if self.mbtree.shortest_victory else 2

    # 数直線の描画    
    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

    # メッセージの表示
    linenum = 4
    textlist = [""] * linenum
    textcolorlist = ["black"] * linenum

    algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
    use_tt = "〇" if self.mbtree.use_tt else "×"
    shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
    init_ab = "〇" if self.mbtree.init_ab else "×"
    textlist[0] = f"{algorithm}　置換表 {use_tt}　最短 {shortest_victory}"
    if not self.mbtree.minimax:
        textlist[0] += f"　初期値 {init_ab}"

    nodetype = "max node" if maxnode else "min node"
    textlist[1] = f"深さ {self.selectednode.mb.move_count} {nodetype}"
    
    statusdata = {
        "start": {
            "text": "処理の開始",
            "color": "white"
        },
        "tt": {
            "text": "置換表の処理",
            "color": "honeydew"
        },
        "score": {
            "text": "子ノードの評価値",
            "color": "lightyellow"
        },
        "update": {
            "text": "更新処理",
            "color": "lightcyan"
        },
        "end": {
            "text": "評価値の確定",
            "color": "lavenderblush"
        },
    }
    textlist[2] = statusdata[status]["text"]
    facecolor = statusdata[status]["color"]

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, 1 - i * 0.7, textlist[i], c=textcolorlist[i])

Mbtree_Anim.update_frameinfo = update_frameinfo

上記の修正後に下記のプログラムを実行し、ミニマックス法、置換表を利用しない、最短の勝利を目指さない 場合で 様々なフレームの表示を行う ことで 正しく実装できたかどうかを確認 することにします。

mbtree.calc_score_for_anim(mbtree.root, minimax=True, use_tt=True, shortest_victory=False)
Mbtree_Anim(mbtree, isscore=True)

下記は "start" の状態の最初のフレームの表示で、「深さ 0 max node」と「処理の開始」が 背景色が白色 で 正しく表示 されています。

下記は 上段の > をクリックした "tt" の状態の 1 フレーム目の表示で、置換表を利用する場合 は "start" の次のフレームが必ず "tt" のフレームになる ので、「深さ 0 max node」と「置換表の処理」が 背景色が薄緑色 で正しく表示されています。なお、先程の create_event_handler の修正によって、"start" の状態のフレームで下段の > をクリックした場合でも "tt" のフレームになります。そのことはこの後で検証します。

下記は 上段の > をクリックした "start" の状態の 2 フレーム目の表示で、深さ 1 のノード の評価値の計算が開始されるので「深さ 1 min node」と「処理の開始」が 背景色が白色 で正しく表示されています。

下記は 下段の > をクリックした "tt" の状態の 3 フレーム目の表示で、「深さ 1 min node」と「置換表の処理」が背景色が薄緑色で正しく表示されています。先ほど説明したように、"start" のフレームで 下段の > をクリックした場合でも "tt" のフレームが表示される ことが確認できました。

下記は 下段の > をクリックした "score" の状態の 5061 フレーム目の表示で、「深さ 1 min node」と「子ノードの評価値」が 背景色が薄黄色 で正しく表示されています。

下記は 上段の > をクリックした "update" の状態の 5062 フレーム目の表示で、「深さ 1 min node」と「更新処理」が 背景色が水色 で正しく表示されています。

下記は 下段の >> をクリックした "end" の状態の 5061 フレーム目の表示で、「深さ 1 min node」と「評価値の確定」が 背景色が薄赤色 で正しく表示されています。

興味がある方は、他の状態でも正しく表示されることを確認してみて下さい。

枝狩りが行われた数などの情報の表示

枝狩りが行われた数などの情報 の表示方法は これまでと同じで良い ので、update_ab の対応する部分を参考 に、下記のプログラムのように記述することができます。なお、下記の 5、6、9 ~ 11 行以外は update_ab と全く同じ です。

5、6 行目：このフレームの情報を表す dict から num_calculated と num_pruned の情報を取り出す。update_ab ではブロックの先頭でこの処理を行っていたが、これらの情報はこの行以前では利用しないのでここに移動した
9 ~ 11 行目：直前に表示されていたフレームの情報を表す dict から prev_num_calculated と prev_num_pruned の情報を取り出す

 1  def update_frameinfo(self):
 2      数直線の描画処理
 3      1 ~ 3 行目の表示処理
 4  
 5      num_calculated = framedata["num_calculated"]
 6      num_pruned = framedata["num_pruned"]
 7      num_total = num_calculated + num_pruned
 8      num_ratio = num_calculated / num_total if num_total != 0 else 0
 9      prev_framedata = self.mbtree.ablist_by_score[self.prev_frame]
10      prev_num_calculated = prev_framedata["num_calculated"]
11      prev_num_pruned = prev_framedata["num_pruned"]
12      prev_num_total = prev_num_calculated + prev_num_pruned
13      diff_num_calculated = num_calculated - prev_num_calculated
14      diff_num_pruned = num_pruned - prev_num_pruned
15      diff_num_total = num_total - prev_num_total
16      diff_num_ratio = diff_num_calculated / diff_num_total if diff_num_total != 0 else 0
17  
18      textlist = [ "計算済", "枝狩り", "合計", "割合" ]
19      datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
20      diff_datalist = [ f"{diff_num_calculated:+d}", f"{diff_num_pruned:+d}", 
21                      f"{diff_num_total:+d}", f"{diff_num_ratio * 100:.1f}%"]
22      for i in range(4):
23          self.abax.text(15, 1 - i * 0.7, textlist[i])
24          self.abax.text(19.5, 1 - i * 0.7, datalist[i], ha="right")
25          self.abax.text(22.5, 1 - i * 0.7, diff_datalist[i], ha="right")
26          
27  Mbtree_Anim.update_frameinfo = update_frameinfo

行番号のないプログラム

def update_frameinfo(self):
    framedata = self.mbtree.ablist_by_score[self.play.value]
    status = framedata["status"]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE

    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3 if self.mbtree.shortest_victory else -2
    plus_inf = 4 if self.mbtree.shortest_victory else 2

    # 数直線の描画    
    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

    # メッセージの表示
    linenum = 4
    textlist = [""] * linenum
    textcolorlist = ["black"] * linenum

    algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
    use_tt = "〇" if self.mbtree.use_tt else "×"
    shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
    init_ab = "〇" if self.mbtree.init_ab else "×"
    textlist[0] = f"{algorithm}　置換表 {use_tt}　最短 {shortest_victory}"
    if not self.mbtree.minimax:
        textlist[0] += f"　初期値 {init_ab}"

    nodetype = "max node" if maxnode else "min node"
    textlist[1] = f"深さ {self.selectednode.mb.move_count} {nodetype}"
    
    statusdata = {
        "start": {
            "text": "処理の開始",
            "color": "white"
        },
        "tt": {
            "text": "置換表の処理",
            "color": "honeydew"
        },
        "score": {
            "text": "子ノードの評価値",
            "color": "lightyellow"
        },
        "update": {
            "text": "更新処理",
            "color": "lightcyan"
        },
        "end": {
            "text": "評価値の確定",
            "color": "lavenderblush"
        },
    }
    textlist[2] = statusdata[status]["text"]
    facecolor = statusdata[status]["color"]

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, 1 - i * 0.7, textlist[i], c=textcolorlist[i])
        
    num_calculated = framedata["num_calculated"]
    num_pruned = framedata["num_pruned"]
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total if num_total != 0 else 0
    prev_framedata = self.mbtree.ablist_by_score[self.prev_frame]
    prev_num_calculated = prev_framedata["num_calculated"]
    prev_num_pruned = prev_framedata["num_pruned"]
    prev_num_total = prev_num_calculated + prev_num_pruned
    diff_num_calculated = num_calculated - prev_num_calculated
    diff_num_pruned = num_pruned - prev_num_pruned
    diff_num_total = num_total - prev_num_total
    diff_num_ratio = diff_num_calculated / diff_num_total if diff_num_total != 0 else 0

    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
    diff_datalist = [ f"{diff_num_calculated:+d}", f"{diff_num_pruned:+d}", 
                    f"{diff_num_total:+d}", f"{diff_num_ratio * 100:.1f}%"]
    for i in range(4):
        self.abax.text(15, 1 - i * 0.7, textlist[i])
        self.abax.text(19.5, 1 - i * 0.7, datalist[i], ha="right")
        self.abax.text(22.5, 1 - i * 0.7, diff_datalist[i], ha="right")
        
Mbtree_Anim.update_frameinfo = update_frameinfo

上記の修正後に下記のプログラムを実行し、>> ボタンをクリック すると実行結果のように 置換表付きミニマックス法 で ルートノードの評価値を計算 した際に 計算したノードの数 が以前の記事で計算した結果と同じ 2271 と正しく表示される ことが確認できます。

Mbtree_Anim(mbtree, isscore=True)

実行結果

それぞれの状態での表示

次に、先程示した下記のそれぞれの状態の表示を実装します。

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

calc_score_for_anim が記録するフレームのデータを表す dict の内容は以下の通りです。

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

`update_frameinfo` の修正

上記の表示内容をよく見ると、「数直線上にそのフレームでのノードの評価値を表示」などのように、複数の状態で共通する表示がある 事がわかります。このような場合に、状態の種類ごとに表示処理を実装すると、同じ表示処理を複数回記述する必要が生じる という問題が発生します。そこで、表示するデータの種類ごとに表示処理を実装する ことにします。

なお、評価値を数直線上に表示 する際に、評価値が負の無限大 または 正の無限大 の場合は、その 座標を計算する必要 があります。そこで、評価値を数直線上に描画する際の座標を計算 する以下のような ローカル関数を定義 するという工夫を行ないました。

名前：評価値から座標（coordinate）を計算（calculate）するので calc_coord と命名する
処理：評価値を数直線上に描画する際の座標を計算する
入力：評価値を仮引数 score に代入する
出力：計算した座標を返り値として返す

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

2 ~ 3 行目：ローカル関数 calc_coord を定義する。行う処理は組み込み関数 min と max を利用して、評価値が負の無限大の座標以下になった場合は負の無限大の座標に、正の無限大の座標以上になった場合は正の無限大の座標を計算している
8 行目：注釈を表示する Axes の annotate メソッドで表示する矢印の形状を表すデータを変数に代入する。この処理は update_ab 内の処理と同じである。注釈の描画方法について忘れた方は以前の記事を復習すること
9 ~ 11 行目：数直線の上部に表示する注釈の文字列の左端、右端、中央の x 座標を変数に代入する。左端と右端の座標としては、最短の勝利を目指す場合の負の無限大と正の無限大の座標である -3 と 4 を設定した。その理由については下記のノートを参照すること
13 ~ 20 行目：そのフレームでのノードの評価値を表示する処理を行う
- 13 行目：そのフレームでのノードの評価値は "score" と "update" と "end" の状態で表示するのでその判定を行う
- 14、15 行目：評価値をフレームの情報から取り出して、その評価値を数直線上に表示する際の座標を計算する
- 16、17 行目：評価値の 注釈を表示する座標 を計算する。max ノード ではノードの 評価値が左から右に増えていく ので 左端に、min ノード ではノードの評価値が 右から左に減っていく ので 右端に表示する ように工夫した
- 18 行目：ノードの評価値を黒色の丸で数直線上に表示する
- 19、20 行目：「score = 評価値」という注釈 を上部に表示する
22 ~ 29 行目："score" の状態のフレームで、子ノードの評価値を表示する処理を行う。行う処理は 13 ~ 20 行目とほぼ同じだが、子ノードの評価値は緑色の丸で表示し、「cscore = 評価値」という注釈 をそのフレームでのノードの評価値の注釈の 逆側に表示する ように工夫した。なお、cscore は child score の略である
31 ~ 41 行目："tt" の状態のフレームで、置換表にデータが登録されていた場合は赤字で真ん中の 4 行目に「置換表に登録済」と表示するようにし、置換表に登録されていた評価値を数直線上に紫色の丸で表示し、注釈を中央に表示するようにした。前回の記事で説明したように、ミニマック法 の場合は 置換表に登録されている下界（上界でも良い）が評価値 となる。登録されていない場合は黒字で「置換表に未登録」と表示するようにする
43 ~ 48 行目："update" の状態のフレームで、ノードの評価値が更新されていた場合は赤字で「評価値の更新」、更新されていない場合は黒字で「評価値の更新なし」と表示するようにする
50 ~ 56 行目："end" の状態のフレームで以下の処理を行う
- 置換表を利用する場合
  - 置換表にデータが登録されていない場合は赤字で「置換表への登録」を表示する
  - 登録されている場合は黒字で「置換表に登録されていたデータを利用」を表示する
- 置換表を利用しない場合は何も表示しない

注釈の左端の座標を負の無限大の座標である minus_inf、右端の座標を正の無限大の座標である plus_inf に設定してしまうと、最短の勝利を目指さない場合 は左端の座標が -2、右端の座標が 2 となってしまうため、左端と右端にメッセージを表示すると 間が狭すぎて表示が重なってしまう ことになります。そのため注釈の左端と右端の座標は常に -3 と 4 に設定しました。

 1  def update_frameinfo(self):
 2      def calc_coord(score):
 3          return min(max(minus_inf, score), plus_inf)
 4          
 5      数直線の描画処理
 6      1 ~ 3 行目の表示処理
 7  
 8      arrowprops = { "arrowstyle": "->"}
 9      leftx = -3
10      rightx = 4
11      centerx = (leftx + rightx) / 2
12      # そのフレームでのノードの評価値の表示
13      if status in ["score", "update", "end"]:
14          score = framedata["score"]
15          score_coord = calc_coord(score)
16          text_coord = leftx if maxnode else rightx
17          ha = "left" if maxnode else "right"
18          self.abax.plot(score_coord, 0, "ok")
19          self.abax.annotate(f"score = {score}", xy=(score_coord, 0),
20                             xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)        
21      # 子ノードの評価値の表示
22      if status == "score":
23          childscore = framedata["childscore"]
24          childscore_coord = calc_coord(childscore)
25          text_coord = rightx if maxnode else leftx
26          ha = "right" if maxnode else "left"
27          self.abax.plot(childscore_coord, 0, "og")
28          self.abax.annotate(f"cscore = {childscore}", xy=(childscore_coord, 0),
29                             xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)        
30      # 置換表にデータが登録されていたかどうかの表示
31      elif status =="tt":
32          if framedata["registered_in_tt"]:
33              textlist[3] = "置換表に登録済"
34              textcolorlist[3] = "red"
35              score = framedata["lower_bound"]
36              score_coord = calc_coord(score)
37              self.abax.plot(score_coord, 0, "om")
38              self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
39                              xytext=(centerx, 1), arrowprops=arrowprops, ha="center")        
40          else:
41              textlist[3] = "置換表に未登録"
42      # ノードの評価値が更新されたかどうかの表示
43      elif status == "update":
44          if framedata["updated"]:
45              textlist[3] = "評価値の更新"
46              textcolorlist[3] = "red"
47          else:
48              textlist[3] = "評価値の更新なし"
49      # 置換表に登録したかどうかの表示
50      elif status == "end":
51          if self.mbtree.use_tt:
52              if framedata["registered_in_tt"]:
53                  textlist[3] = "置換表に登録されていたデータを利用"
54              else:
55                  textlist[3] = "置換表への登録"
56                  textcolorlist[3] = "red"
57  
58      self.abfig.set_facecolor(facecolor)
59      for i in range(linenum):
60          self.abax.text(5, 1 - i * 0.7, textlist[i], c=textcolorlist[i])
61
62      枝狩りが行われた数などの情報の表示
63  
64  Mbtree_Anim.update_frameinfo = update_frameinfo

行番号のないプログラム

def update_frameinfo(self):
    def calc_coord(score):
        return min(max(minus_inf, score), plus_inf)
        
    framedata = self.mbtree.ablist_by_score[self.play.value]
    status = framedata["status"]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE

    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3 if self.mbtree.shortest_victory else -2
    plus_inf = 4 if self.mbtree.shortest_victory else 2

    # 数直線の描画    
    self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
    for num in range(minus_inf, plus_inf + 1):
        if num == minus_inf:
            numtext = "-∞"
        elif num == plus_inf:
            numtext = "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

    # メッセージの表示
    linenum = 4
    textlist = [""] * linenum
    textcolorlist = ["black"] * linenum

    algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
    use_tt = "〇" if self.mbtree.use_tt else "×"
    shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
    init_ab = "〇" if self.mbtree.init_ab else "×"
    textlist[0] = f"{algorithm}　置換表 {use_tt}　最短 {shortest_victory}"
    if not self.mbtree.minimax:
        textlist[0] += f"　初期値 {init_ab}"
    
    textlist[1] = f"深さ {self.selectednode.mb.move_count} "
    if maxnode:
        textlist[1] += "max node"
    else:
        textlist[1] += "min node"
    
    statusdata = {
        "start": {
            "text": "処理の開始",
            "color": "white"
        },
        "tt": {
            "text": "置換表の処理",
            "color": "honeydew"
        },
        "score": {
            "text": "子ノードの評価値",
            "color": "lightyellow"
        },
        "update": {
            "text": "更新処理",
            "color": "lightcyan"
        },
        "end": {
            "text": "評価値の確定",
            "color": "lavenderblush"
        },
    }
    textlist[2] = statusdata[status]["text"]
    facecolor = statusdata[status]["color"]
    
    arrowprops = { "arrowstyle": "->"}
    leftx = -3
    rightx = 4
    centerx = (leftx + rightx) / 2
    # そのフレームでのノードの評価値の表示
    if status in ["score", "update", "end"]:
        score = framedata["score"]
        score_coord = calc_coord(score)
        text_coord = leftx if maxnode else rightx
        ha = "left" if maxnode else "right"
        self.abax.plot(score_coord, 0, "ok")
        self.abax.annotate(f"score = {score}", xy=(score_coord, 0),
                           xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)        
    # 子ノードの評価値の表示
    if status == "score":
        childscore = framedata["childscore"]
        childscore_coord = calc_coord(childscore)
        text_coord = rightx if maxnode else leftx
        ha = "right" if maxnode else "left"
        self.abax.plot(childscore_coord, 0, "og")
        self.abax.annotate(f"cscore = {childscore}", xy=(childscore_coord, 0),
                           xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)        
    # 置換表にデータが登録されていたかどうかの表示
    elif status =="tt":
        if framedata["registered_in_tt"]:
            textlist[3] = "置換表に登録済"
            textcolorlist[3] = "red"
            score = framedata["lower_bound"]
            score_coord = calc_coord(score)
            self.abax.plot(score_coord, 0, "om")
            self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
                            xytext=(centerx, 1), arrowprops=arrowprops, ha="center")        
        else:
            textlist[3] = "置換表に未登録"
    # ノードの評価値が更新されたかどうかの表示
    elif status == "update":
        if framedata["updated"]:
            textlist[3] = "評価値の更新"
            textcolorlist[3] = "red"
        else:
            textlist[3] = "評価値の更新なし"
    # 置換表に登録したかどうかの表示
    elif status == "end":
        if self.mbtree.use_tt:
            if framedata["registered_in_tt"]:
                textlist[3] = "置換表に登録されていたデータを利用"
            else:
                textlist[3] = "置換表への登録"
                textcolorlist[3] = "red"

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, 1 - i * 0.7, textlist[i], c=textcolorlist[i])

    num_calculated = framedata["num_calculated"]
    num_pruned = framedata["num_pruned"]
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total if num_total != 0 else 0
    prev_framedata = self.mbtree.ablist_by_score[self.prev_frame]
    prev_num_calculated = prev_framedata["num_calculated"]
    prev_num_pruned = prev_framedata["num_pruned"]
    prev_num_total = prev_num_calculated + prev_num_pruned
    diff_num_calculated = num_calculated - prev_num_calculated
    diff_num_pruned = num_pruned - prev_num_pruned
    diff_num_total = num_total - prev_num_total
    diff_num_ratio = diff_num_calculated / diff_num_total if diff_num_total != 0 else 0

    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
    diff_datalist = [ f"{diff_num_calculated:+d}", f"{diff_num_pruned:+d}", 
                    f"{diff_num_total:+d}", f"{diff_num_ratio * 100:.1f}%"]
    for i in range(4):
        self.abax.text(15, 1 - i * 0.7, textlist[i])
        self.abax.text(19.5, 1 - i * 0.7, datalist[i], ha="right")
        self.abax.text(22.5, 1 - i * 0.7, diff_datalist[i], ha="right")
        
Mbtree_Anim.update_frameinfo = update_frameinfo

`create_event_handler` の修正

上記の修正後に下記のプログラムを実行して様々なフレームを表示した所、以下の点が操作しづらい と思いました。

Mbtree_Anim(mbtree, isscore=True)

"score" のフレームで 下段の > ボタン をクリックすると、"update" のフレームを飛ばして 次の子ノードの "score" のフレームに移動してしまう

calc_score_by_ab で作成したデータを Mbtree_Anim で表示する update_ab メソッドでは "score" のフレームには真ん中に 次の "update" のフレームでどのような処理が行われるかが表示 されていましたが、今回実装した update_frameinfo メソッドでは "score" のフレームには 次の "update" フレームで行われる処理が表示されない ので下段の < や > ボタンをクリックした際に、"update" のフレームを飛ばさないほうがわかりやすい 気がしました。

そこで下記のプログラムの 4、10 行目のように 下段の < と > ボタン をクリックした際に "update" のフレームを飛ばさない ように calc_event_handler を修正することにします。

 1  def create_event_handler(self):
元と同じなので省略
 2      def on_node_prev_button_clicked(b=None):
 3          if self.mbtree.calculated_by_calc_score_for_anim:
 4              change_frame("start", -1, ["start", "score", "update", "tt"])
 5          else:
 6              change_frame("start", -1, ["start", "score"])
 7  
 8      def on_node_next_button_clicked(b=None):
 9          if self.mbtree.calculated_by_calc_score_for_anim:
10              change_frame("end", 1, ["end", "score", "update", "tt"])
11          else:
12              change_frame("end", 1, ["end", "score"])
13  
14  Mbtree_Anim.create_event_handler = create_event_handler

行番号のないプログラム

def create_event_handler(self):
    def on_play_changed(changed):
        self.prev_frame = changed.old
        self.update_gui()
            
    def on_prev_button_clicked(b=None):
        self.play.value -= 1
        self.update_gui()
        
    def on_next_button_clicked(b=None):
        self.play.value += 1
        self.update_gui()

    self.prev_button.on_click(on_prev_button_clicked)
    self.next_button.on_click(on_next_button_clicked)

    self.play.observe(on_play_changed, names="value")
    
    def change_frame(edge_status, diff, status_list):
        frame = self.play.value
        selectednode = self.mbtree.nodelist_by_score[frame]
        if self.mbtree.calculated_by_calc_score_for_anim:
            selectedstatus = self.mbtree.ablist_by_score[frame]["status"]
        else:
            selectedstatus = self.mbtree.ablist_by_score[frame][3]
        if selectedstatus == edge_status:
            return
        while True:
            frame += diff
            node = self.mbtree.nodelist_by_score[frame]
            if self.mbtree.calculated_by_calc_score_for_anim:
                status = self.mbtree.ablist_by_score[frame]["status"]
            else:
                status = self.mbtree.ablist_by_score[frame][3]
            if node == selectednode and status in status_list:
                break
        self.play.value = frame
        self.update_gui()
            
    def on_node_first_button_clicked(b=None):
        change_frame("start", -1, ["start"])
            
    def on_node_prev_button_clicked(b=None):
        if self.mbtree.calculated_by_calc_score_for_anim:
            change_frame("start", -1, ["start", "score", "update", "tt"])
        else:
            change_frame("start", -1, ["start", "score"])

    def on_node_next_button_clicked(b=None):
        if self.mbtree.calculated_by_calc_score_for_anim:
            change_frame("end", 1, ["end", "score", "update", "tt"])
        else:
            change_frame("end", 1, ["end", "score"])
        
    def on_node_last_button_clicked(b=None):
        change_frame("end", 1, ["end"])
    
    if self.abfig is not None:
        self.node_first_button.on_click(on_node_first_button_clicked)
        self.node_prev_button.on_click(on_node_prev_button_clicked)
        self.node_next_button.on_click(on_node_next_button_clicked)
        self.node_last_button.on_click(on_node_last_button_clicked)

Mbtree_Anim.create_event_handler = create_event_handler

修正箇所

def create_event_handler(self):
元と同じなので省略
    def on_node_prev_button_clicked(b=None):
        if self.mbtree.calculated_by_calc_score_for_anim:
-           change_frame("start", -1, ["start", "score", "tt"])
+           change_frame("start", -1, ["start", "score", "update", "tt"])
        else:
            change_frame("start", -1, ["start", "score"])

    def on_node_next_button_clicked(b=None):
        if self.mbtree.calculated_by_calc_score_for_anim:
-           change_frame("end", 1, ["end", "score", "tt"])
+           change_frame("end", 1, ["end", "score", "update", "tt"])
        else:
            change_frame("end", 1, ["end", "score"])

Mbtree_Anim.create_event_handler = create_event_handler

表示の確認

置換表を利用する場合と、利用しない場合で表示が正しく行われるかどうかを確認することにします。

置換表を利用する場合

下記のプログラムを実行し、置換表を利用する場合 に正しく表示されるかどうかを確認することにします。なお、先程確認した背景色と中央の 1 ~ 3 行目の表示の確認は省略します。

Mbtree_Anim(mbtree, isscore=True)

下記は "start" の状態の最初のフレームの表示です。"start" の状態では共通する内容以外は特に何も表示しないので、先程と同じ表示が行われます。

下記は 上段の > をクリックした "tt" の状態の 1 フレーム目の表示です。このノードの情報は置換表に登録されていない ので、3 行目に黒字で「置換表に未登録」が正しく表示されています。また、置換表による枝狩りは行われない ので右の「枝狩り」には +0 が正しく表示 されています。

下記は 上段の > をクリックした赤枠の 深さ 1 のノード の "start" の状態の 2 フレーム目の表示で、先ほどと同様の表示が行われます。ノードの評価値の計算は行われないので右の「計算済」と「枝狩り」には 0 が正しく表示されます。

次に、このノードのフレームの表示を検証することにします。

下記は 下段の > をクリックした "tt" の状態の 3 フレーム目の表示です。このノードの情報は置換表に登録されていない ので、3 行目に黒字で「置換表に未登録」が正しく表示されています。なお、ゲーム木の表示は上図と変わらないので省略します。

下記は 下段の > をクリックした赤枠の最初の子ノードの評価値が計算された "score" の状態の 5061 フレーム目の表示です。min ノード では ノードの評価値は正の無限大で初期化 され、そのことが 数直線の右に score = inf のように正しく表示されています。また、赤枠の最初の 子ノードの評価値が 1 と計算 されたことが数直線の 左上に cscore = 1 のように正しく表示されています。右には子ノードの評価値を計算する際に計算したノードの数と枝狩りが行われたノードの数が表示されます。

なお、次の "update" の状態 のフレームで ノードの評価値が更新されるか どうかは、下記のように 簡単に判別 することができます。そのことは max ノードでも同様です。

そのフレームでのノードの評価値の注釈と、子ノードの評価値の注釈の 2 つの矢印 が下図のように 離れている場合 は 更新される
2 つの矢印が同じ評価値を指して くっついているか、交差する場合 は 更新されない

下記は 下段の > をクリックした "update" の状態の 5062 フレーム目の表示です。min ノード ではノードの評価値が、それまでのノードの評価値と子ノードの評価値の 最小値で更新 され、そのことが数直線の所に score = 1 のように正しく表示されています。また、真ん中の 4 行目に 赤字で「評価値の更新」 が表示されます。

下記は 下段の > をクリックした "score" の状態と もう一度 > をクリックした "update" の 7551、7552 フレーム目の表示です。そのフレームでの評価値と子ノードの評価値は どちらも 1 なので 7552 フレーム目ではノードの評価値が score = 1 のまま変化せず、真ん中の 4 行目に「評価値の更新なし」と正しく表示されています。

なお、先程説明したように、"score" の状態のフレームでは 2 つの注釈の矢印がくっついている ことからノードの 評価値が更新されない ことが判別できます。

下記は 下段の >> をクリックした赤枠のノードの 評価値が確定 する "end" の状態の 8750 フレーム目の表示です。ゲーム木の図からわかるように、赤枠の子ノードの評価値の最小値は 0 であり、このノードの評価値が score = 0 と 正しく表示 されています。また、このノードの評価値は 置換表に登録されていなかった ので、真ん中の 4 行目に 赤字で「置換表への登録」 が正しく表示されます。

下図は下記の操作を行って、赤枠の ルートノードの 3 番目の子ノード の評価値の 計算を開始 する "score" の状態の 10815 フレーム目の表示です。

上段の > ボタンをクリックしてルートノードの最初の子ノードの評価値が計算された "score" の状態のフレームに移動する
下段の > ボタンを 3 回クリックして、ルートノードの 2 つ目の子ノードの評価値が計算された "update" の状態のフレームに移動する
上段の > ボタンをクリックする

上図の 赤枠のノードの局面 は、ルートノードの 1 番目の子ノードの局面 を時計回りに 90 度回転させた局面 なので、先程 評価値を計算して置換表に登録した ルートノードの 1 番目の子ノードと 同一局面 です。従って、赤枠のノードの評価値は置換表に登録済 です。

下段の > をクリックした "tt" の状態の下図の 10816 フレーム目の図では以下のように 置換表の処理が正しく行われたことが表示 されています。

先程 8750 フレーム目で 置換表に登録した評価値が取り出された ことが数直線の上に「置換表の評価値 = 0」のように表示される
真ん中の 4 行目に 赤字で「置換表に登録済」 が表示される
ゲーム木の 赤枠の子孫ノード が、置換表による 枝狩りが行われた ことによって 暗く表示 される
右の「枝狩り」の +59704 から、赤枠の 59704 個の子孫ノードが 置換表によって枝狩りが行われた ことが確認できる

下記は 下段の > をクリックした "end" の状態の 10817 フレーム目の表示です。真ん中の 4 行目に黒字で「置換表に登録されていたデータを利用」が正しく表示されています。

これで、置換表を利用する場合 に update_frameinfo に記述した すべての場合での表示が正しく行われることが確認 できました。余裕がある方は、他のフレームでも正しく表示されるかどうかを確認してみて下さい。

置換表を利用しない場合

下記のプログラムを実行し、置換表を利用しない場合 に正しく表示されるかどうかを確認することにします。また、その際に先程と異なり、最短の勝利を目指す場合の表示の確認も行うことにします。

mbtree.calc_score_for_anim(mbtree.root, minimax=False, use_tt=False, shortest_victory=True)
Mbtree_Anim(mbtree, isscore=True)

下記は 上段の > をクリックした 1 フレーム目の表示 です。置換表を利用しない ので、ルートノードの "start" の次のフレーム には、ルートノードの 最初の子ノードの処理を開始するフレーム が表示されます。

下記は 下段の >> をクリックした "end" の状態の 11150 フレーム目の表示です。置換表を利用しない ので真ん中の 4 行目には 何も表示されない ことが確認できます。

他の状態 のフレームの表示は、置換表を利用する場合と利用しない場合で 変わらない ので確認を省略します。余裕がある方は確認してみて下さい。

今回の記事のまとめ

今回の記事では、ミニマックス法の視覚化のための Mbtree_Anim の修正 を行いました。修正前の update_ab で行っていた視覚化よりも、ミニマックス法の視覚化がわかりやすくなった と思うのですがどうでしょうか。

次回の記事では αβ 法の視覚化についての実装を行います。

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

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

次回の記事