目次と前回の記事

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

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

リンク	説明
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 は αβ 法で評価値の計算を行う際の処理の視覚化を行いますが、その処理によってどのくらいの数の枝狩りが行われているかの情報は表示されません。

そこで、今回の記事では Mbtree_Anim が 枝狩りを行ったノードの数などを表示 するように改良することにします。どのように改良すればよいかについて少し考えてみて下さい。

視覚化の方針

αβ 法の性能を評価するためには、枝狩りが行われたノードの数の情報だけでは 不十分 です。αβ 法の性能に限らず、何らかのものの性能を評価するため には、他のものと比較する必要がある からです。αβ 法はミニマックス法を改良したものなので、比較の対象 となるのは ミニマックス法 です。従って、同じノードの評価値 を αβ 法とミニマックス法で計算した際の、下記の 2 つを比較 することで αβ 法の評価を行うことができます。

αβ 法で計算を行った ノードの数。以後は alpha beta の頭文字から A と表記 する
ミニマックス法で計算を行った ノードの数。以後は mini max から M と表記 する

上記の 2 つの数の比率である A / M が、それぞれのアルゴリズムで同じノードの評価値を計算した際の 計算時間の比率にほぼ一致 します。例えば A が 10、M が 100 の場合は、10 ÷ 100 = 0.1 なので αβ 法によってミニマックス法の約 10 %（10 分の 1）の時間で評価値を計算できることがわかります。

以後は この比率 のことを割合を表す ratio の頭文字を取って R と表記 することにします。

そこで、本記事では上記の A、M、R を表示するように Mbtree_Anim を改良することにします。そのためには、上記の A と M を計算する必要があるので、その計算方法について少し考えてみて下さい。

A と M の計算方法

A と M を計算するために、同じノードに対して αβ 法と、ミニマックス法の両方で評価値を計算する必要があると思った人がいるかもしれませんが、実際には αβ 法による評価値の計算を行うだけ で A と M の 両方を計算 することができます。

その理由は、αβ 法では 枝狩りを行ったノードの数だけ、ミニマックス法と比較して 計算するノードの数が減る ので、αβ 法で 枝狩り（pruning）を行ったノードの数 を P と表記 した場合に 下記の式が成り立つ からです。

M = A + P

従って、αβ 法で計算を行う際に A と P の数を数えることで M を計算することができます。

表示の仕様の具体化

Mbtree_Anim では、αβ 法で評価値を計算する手順をアニメーションのフレームで 順番に表示 しているので、本記事では Mbtree_Anim で表示している アニメーションのフレームまでに行われた処理 での A、M、R を表示 することにします。また、M を計算する際に P を計算する必要があるので、P も表示する ことにします。

そのようにすることで、αβ 法の処理の 途中経過 での A、M、P、R の値を観察 することができるようになります。また、全ての処理が完了 したアニメーションの 最後のフレーム での A、M、P、R を見ることで、それらの 最終的な値 を知ることができます。

具体的には、以下の 2 つの図のように A、P、M、R の順でそれぞれの値を上の行から順に表示します。なお、A、P、M、R ではわかりづらいので、それぞれの 見出し を「計算済」、「枝狩り」、「合計」、「割合」と表示しました。

下図は計算を開始する前の最初のフレームの図なので、A、P、M はいずれも 0 で、R は 0.0 % と表示されます。

下図はルートノードの 評価値の計算が完了 した最後のフレームの図で、A は 18297、P は 531649、M は 549946¹、R は 3.3 % と表示されるので、αβ 法 では ルートノードの評価値 の計算を ミニマックス法の約 3.3 % というかなり短い時間で計算できることを表します。

本記事で利用する 4 つの記号について下記の表にまとめます。4 つの記号 はいずれも Mbtree_Anim で表示している アニメーションのフレームまでに行われた処理 を表します。

記号	意味	見出し
A	αβ 法で計算を行ったノードの数	計算済
P	αβ 法で枝狩りを行ったノードの数	枝狩り
M	ミニマックス法で計算を行ったノードの数。M = A + P で計算できる	合計
R	M に対する A の比率。A / M で計算できる	割合

上記のような図の表示を行う方法について少し考えてみて下さい。

Mbtree クラスの `calc_score_by_ab` メソッドの修正

A と P は以下のような方法で計算することができます。

calc_score_by_ab で αβ 法による評価値の計算を開始する前に、A と P を記録する属性を 0 で初期化 する
calc_score_by_ab の処理の中で、ノードの評価値が確定した時点 で A の値に 1 を足す
calc_score_by_ab の処理の中で、ノードの枝狩りの処理を行う際 に P の値に 1 を足す

A と P を記録する属性の名前を A や P にするのはわかりづらいので、それぞれ num_calculated² と num_pruned という名前にします。

また、A と P の値は 各フレームごとに記録 する必要があるので、各フレームのデータを記録する ablist_by_score の要素の tuple を以下のように変更することにします。太字が変更の際に A と P を記録するために追加した部分です。

変更前：(α 値, β 値, 子ノードの評価値, フレームの状態を表す文字列)
変更後：(α 値, β 値, 子ノードの評価値, フレームの状態を表す文字列, A の値, P の値)

なお、calc_score_by_ab では、αβ 法で 計算を行ったノードの数 を count という属性で計算 していますが、count は ノードの計算が開始された時点で 1 を足す ので、num_calculated とはよく似ていますが 少し異なる処理を行っています。以下の理由から、count の処理を削除 して num_calculated に統合する ことにします。

ノードの評価値の計算が すべて終了した時点 では count と num_calculated には 同じ値が計算される
count は calc_score_by_ab によるノードの評価値の計算が すべて終了した後でのみ利用されている ので、その時点で同じ値が代入されている num_caluculated で代替できる

下記は、num_calculated と num_pruned を計算して ablist_by_score に記録するように calc_score_by_ab を修正したプログラムです。

4、14、38 行目の後にあった score 属性に関する処理を削除する
7 行目：枝狩りが行われたノードの処理を行う際に、num_pruned 属性の値に 1 を加算する処理を追加する
13 ~ 22、25、26 行目：ablist_by_score に追加する tuple の要素の末尾に num_calculated と num_pruned 属性を追加する
24 行目：このノードの評価値が確定したので、num_calculated 属性に 1 を加算する処理を追加する
36、37 行目：αβ 法の処理を開始する前に、num_calculated 属性と num_pruned 属性の値を 0 で初期化するようにする
39 ~ 44 行目：debug が True の場合に最終的な A、P、M、R の値を dprint で表示するように修正する。なお、プログラムがわかりやすくなるように 39、40 行目で M と R の値を計算して変数に代入している。また、44 行目で M を表示する際の単位は % なので 100 で掛け算し、小数点以下 1 桁まで表示するように :.1f を記述している。この点について忘れた方は、以前の記事を復習すること

 1  from marubatsu import Marubatsu
 2  from tree import Mbtree
 3  
 4  def calc_score_by_ab(self, abroot, debug=False):           
 5      def assign_pruned_index(node, index):
 6          node.pruned_index = index
 7          self.num_pruned += 1
 8          for childnode in node.children:
 9              assign_pruned_index(childnode, index)
10          
11      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
12          self.nodelist_by_score.append(node)
13          self.ablist_by_score.append((alpha, beta, None, "start",
14                                       self.num_calculated, self.num_pruned))
元と同じなので省略
15                      self.ablist_by_score.append((alpha, beta, score, "score",
16                                                   self.num_calculated, self.num_pruned))
元と同じなので省略
17                      self.ablist_by_score.append((alpha, beta, None, "update",
18                                                   self.num_calculated, self.num_pruned))
元と同じなので省略
19                      self.ablist_by_score.append((alpha, beta, score, "score",
20                                                   self.num_calculated, self.num_pruned))
元と同じなので省略
21                      self.ablist_by_score.append((alpha, beta, None, "update",
22                                                   self.num_calculated, self.num_pruned))
元と同じなので省略
23          self.nodelist_by_score.append(node)
24          self.num_calculated += 1     
25          self.ablist_by_score.append((alpha, beta, None, "end",
26                                       self.num_calculated, self.num_pruned))
27          node.score_index = len(self.nodelist_by_score) - 1     
28          return node.score
29  
30      from ai import dprint       
31      for node in self.nodelist:
32          node.score_index = float("inf")
33          node.pruned_index = float("inf")
34      self.nodelist_by_score = []
35      self.ablist_by_score = []
36      self.num_calculated = 0
37      self.num_pruned = 0
38      calc_ab_score(abroot)
39      total_nodenum = self.num_pruned + self.num_calculated
40      ratio = self.num_calculated / total_nodenum * 100
41      dprint(debug, "計算したノードの数",  self.num_calculated)
42      dprint(debug, "枝狩りしたノードの数",  self.num_pruned)
43      dprint(debug, "合計",  total_nodenum)
44      dprint(debug, f"割合 {ratio:.1f}%")
45      
46  Mbtree.calc_score_by_ab = calc_score_by_ab

行番号のないプログラム

from marubatsu import Marubatsu
from tree import Mbtree

def calc_score_by_ab(self, abroot, debug=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, alpha=float("-inf"), beta=float("inf")):
        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, 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)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                 self.num_calculated, self.num_pruned))
                    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)
                        break
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, 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)
                    self.ablist_by_score.append((alpha, beta, None, "update",
                                                 self.num_calculated, self.num_pruned))
                    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)
                        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     
        return node.score

    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
    calc_ab_score(abroot)
    total_nodenum = self.num_pruned + self.num_calculated
    ratio = self.num_calculated / total_nodenum * 100
    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

修正箇所

from marubatsu import Marubatsu
from tree import Mbtree

def calc_score_by_ab(self, abroot, debug=False):    
-   self.count = 0
    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, alpha=float("-inf"), beta=float("inf")):
        self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alpha, beta, None, "start"))
+       self.ablist_by_score.append((alpha, beta, None, "start",
+                                    self.num_calculated, self.num_pruned))
-       self.count += 1
元と同じなので省略
-                   self.ablist_by_score.append((alpha, beta, score, "score"))
+                   self.ablist_by_score.append((alpha, beta, score, "score",
+                                                self.num_calculated, self.num_pruned))
元と同じなので省略
-                   self.ablist_by_score.append((alpha, beta, None, "update"))
+                   self.ablist_by_score.append((alpha, beta, None, "update",
+                                                self.num_calculated, self.num_pruned))
元と同じなので省略
-                   self.ablist_by_score.append((alpha, beta, score, "score"))
+                   self.ablist_by_score.append((alpha, beta, score, "score",
+                                                self.num_calculated, self.num_pruned))
元と同じなので省略
-                   self.ablist_by_score.append((alpha, beta, None, "update"))
+                   self.ablist_by_score.append((alpha, beta, None, "update",
+                                                self.num_calculated, self.num_pruned))
元と同じなので省略
        self.nodelist_by_score.append(node)
+       self.num_calculated += 1     
-       self.ablist_by_score.append((alpha, beta, None, "end"))
+       self.ablist_by_score.append((alpha, beta, None, "end",
+                                    self.num_calculated, self.num_pruned))
        node.score_index = len(self.nodelist_by_score) - 1     
        return node.score

    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
    calc_ab_score(abroot)
-   dprint(debug, "count =", self.count) 
+   total_nodenum = self.num_pruned + self.num_calculated
+   ratio = self.num_calculated / total_nodenum * 100
+   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

上記の修正後に下記のプログラムのように実引数に debug=True を記述して calc_score_by_ab を呼び出すと、実行結果のように計算された A、P、M、R の値が表示されることが確認できます。

mbtree = Mbtree(algo="df")
mbtree.calc_score_by_ab(mbtree.root, debug=True)

実行結果

計算したノードの数 18297
枝狩りしたノードの数 531649
合計 549946
割合 3.3%

Mbtree_Anim クラスの `create_widgets` メソッドの修正

A、P、M、R の値を表示するためには、Mbtree_Anim の上部に表示する Figure の幅を広げる 必要があるので、下記のプログラムのように create_widgets メソッドを修正します。

8 行目：Figure の大きさを (5, 1) から (7, 1) に修正する。なお、修正後の大きさは筆者が A、P、M、R がうまく表示されるように試行錯誤して決めた値である

 1  from tree import Mbtree_Anim
 2  import matplotlib.pyplot as plt
 3  import ipywidgets as widgets
 4  
 5  def create_widgets(self):
元と同じなので省略
 6      with plt.ioff():
元と同じなので省略
 7          if self.isscore and hasattr(self.mbtree, "ablist_by_score"):
 8              self.abfig = plt.figure(figsize=(7, 1))
元と同じなので省略
 9          
10  Mbtree_Anim.create_widgets = create_widgets

行番号のないプログラム

from tree import Mbtree_Anim
import matplotlib.pyplot as plt
import ipywidgets as widgets

def create_widgets(self):
    self.play = widgets.Play(max=self.nodenum - 1, interval=500)
    self.prev_button = self.create_button("<", width=30)
    self.next_button = self.create_button(">", width=30)
    self.frame_slider = widgets.IntSlider(max=self.nodenum - 1, description="frame")
    self.interval_slider = widgets.IntSlider(value=500, min=1, max=2000, description="interval")
    widgets.jslink((self.play, "value"), (self.frame_slider, "value"))    
    widgets.jslink((self.play, "interval"), (self.interval_slider, "value"))

    with plt.ioff():
        self.fig = plt.figure(figsize=[self.width * self.size,
                                        self.height * self.size])
        self.ax = self.fig.add_axes([0, 0, 1, 1])
        self.fig.canvas.toolbar_visible = False
        self.fig.canvas.header_visible = False
        self.fig.canvas.footer_visible = False
        self.fig.canvas.resizable = False 
        if self.isscore and hasattr(self.mbtree, "ablist_by_score"):
            self.abfig = plt.figure(figsize=(7, 1))
            self.abax = self.abfig.add_axes([0, 0, 1, 1])
            self.abfig.canvas.toolbar_visible = False
            self.abfig.canvas.header_visible = False
            self.abfig.canvas.footer_visible = False
            self.abfig.canvas.resizable = False 
        else:
            self.abfig = None
            
    if self.abfig is not None:
        self.node_label = widgets.Label("選択中のノード内の移動")
        self.node_first_button = self.create_button("<<", width=40)
        self.node_prev_button = self.create_button("<", width=30)
        self.node_next_button = self.create_button(">", width=30)
        self.node_last_button = self.create_button(">>", width=40)
        
Mbtree_Anim.create_widgets = create_widgets

修正箇所

from tree import Mbtree_Anim
import matplotlib.pyplot as plt
import ipywidgets as widgets

def create_widgets(self):
元と同じなので省略
    with plt.ioff():
元と同じなので省略
        if self.isscore and hasattr(self.mbtree, "ablist_by_score"):
-           self.abfig = plt.figure(figsize=(5, 1))
+           self.abfig = plt.figure(figsize=(7, 1))
元と同じなので省略
        
Mbtree_Anim.create_widgets = create_widgets

Mbtree_Anim クラスの `update_ab` メソッドの修正

次に、下記のプログラムのように A、P、M、R の値を表示 するように update_ab を修正します。

4 行目：先程の ablist_by_score の要素に代入された tuple の修正に合わせて、A と P の値を tuple から取り出して num_calculated と num_pruned に代入する ように修正する
5 行目：Figure の幅を広げたので、Axes の表示範囲をそれに合わせて 23 に広げる。この値も筆者が試行錯誤して決めた値である
6、7 行目：M と R の値を計算して変数に代入する
8、9 行目：4 つの行の見出しとデータを表す list を textlist と datalist に代入する
10 ~ 12 行目：for 文を使って、4 つの行を繰り返し処理で表示する。この部分について忘れた方は、この処理の直前で同様の処理を行っている以前の記事を復習すること

 1  import matplotlib.patches as patches
 2  
 3  def update_ab(self):
 4      alpha, beta, score, status, num_calculated, num_pruned = self.mbtree.ablist_by_score[self.play.value]
元と同じなので省略
 5      self.abax.set_xlim(-4, 23)
元と同じなので省略 
 6      num_total = num_calculated + num_pruned
 7      num_ratio = num_calculated / num_total
 8      textlist = [ "計算済", "枝狩り", "合計", "割合" ]
 9      datalist = [ num_calculated, num_pruned, num_total, num_ratio]
10      for i in range(4):
11           self.abax.text(15, 1 - i * 0.7, textlist[i])
12           self.abax.text(17, 1 - i * 0.7, datalist[i])
13         
14  Mbtree_Anim.update_ab = update_ab

行番号のないプログラム

import matplotlib.patches as patches

def update_ab(self):
    alpha, beta, score, status, num_calculated, num_pruned = self.mbtree.ablist_by_score[self.play.value]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    acolor = "red" if maxnode else "black"
    bcolor = "black" if maxnode else "red"
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3
    plus_inf = 4   
    alphacoord = max(minus_inf, alpha)
    betacoord = min(plus_inf, beta)
    
    color = "lightgray" if maxnode else "aqua"
    rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf,
                            height=1, fc=color)
    self.abax.add_patch(rect)
    rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord,
                            height=1, fc="yellow")
    self.abax.add_patch(rect)
    color = "aqua" if maxnode else "lightgray"
    rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
                            height=1, fc=color)
    self.abax.add_patch(rect)

    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")
        
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
                    arrowprops=arrowprops, ha="center", c=acolor)
    self.abax.plot(betacoord, 0, "ob")
    self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
                    arrowprops=arrowprops, ha="center", c=bcolor)
    if score is not None:
        self.abax.plot(score, 0, "og")
        self.abax.annotate(f"score = {score}", xy=(score, 0),
                        xytext=((minus_inf + plus_inf) / 2, 1), 
                        arrowprops=arrowprops, ha="center")
            
    facecolorlist = ["aqua", "yellow", "lightgray"]
    textcolorlist = ["black", "black", "black"]
    if maxnode:
        nodetype = f"深さ {self.selectednode.mb.move_count} max node"
        textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)", "α 値の更新なし (score ≦ α)"]
        if score is not None :
            if beta <= score:
                textcolorlist[0] = "red"
            elif alpha < score:
                textcolorlist[1] = "red"
            else:
                textcolorlist[2] = "red"
    else:
        nodetype = f"深さ {self.selectednode.mb.move_count} min node"
        textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)", "β 値の更新なし (score ≦ β)"]
        if score is not None :
            if score <= alpha:
                textcolorlist[0] = "red"
            elif score < beta:
                textcolorlist[1] = "red"
            else:
                textcolorlist[2] = "red"
            
    if status == "start":
        facecolor = "white"
        nodetype += " 処理の開始"
    elif status == "score":
        facecolor = "lightyellow"
        nodetype += " 子ノードの評価値"
    elif status == "update":
        facecolor = "lightcyan"
        if maxnode:
            nodetype += " α 値の処理"
        else:
            nodetype += " β 値の処理"
    else:
        facecolor = "lavenderblush"
        nodetype += " 評価値の確定"
    self.abfig.set_facecolor(facecolor)
    self.abax.text(6, 1, nodetype)   
    for i in range(3):
        rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5, fc=facecolorlist[i])
        self.abax.add_patch(rect)
        self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
    
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total
    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    datalist = [ num_calculated, num_pruned, num_total, num_ratio]
    for i in range(4):
        self.abax.text(15, 1 - i * 0.7, textlist[i])
        self.abax.text(17, 1 - i * 0.7, datalist[i])
        
Mbtree_Anim.update_ab = update_ab

修正箇所

import matplotlib.patches as patches

def update_ab(self):
-   alpha, beta, score, status = self.mbtree.ablist_by_score[self.play.value]
+   alpha, beta, score, status, num_calculated, num_pruned = self.mbtree.ablist_by_score[self.play.value]
元と同じなので省略
-   self.abax.set_xlim(-4, 14)
+   self.abax.set_xlim(-4, 23)
元と同じなので省略   
+   num_total = num_calculated + num_pruned
+   num_ratio = num_calculated / num_total
+   textlist = [ "計算済", "枝狩り", "合計", "割合" ]
+   datalist = [ num_calculated, num_pruned, num_total, num_ratio]
+   for i in range(4):
+       self.abax.text(15, 1 - i * 0.7, textlist[i])
+       self.abax.text(17, 1 - i * 0.7, datalist[i])
        
Mbtree_Anim.update_ab = update_ab

上記の 10 ~ 14 行目の処理は組み込み関数 enumerate とまだ説明していない組み込み関数 zip を利用して下記のプログラムのように記述することもできます。

for i, (text, data) in enumerate(zip(textlist, datalist)):
     self.abax.text(15, 1 - i * 0.7, text)
     self.abax.text(17, 1 - i * 0.7, data)

ただし、本記事では組み込み関数 zip をまだ説明していない点と、enumerate と zip を併用した場合に 1 行目で下記のようなプログラムを記述するとエラーになってしまう点が慣れていないと間違いやすいので本記事では採用しません。

for i, text, data in enumerate(zip(textlist, datalist)):

なお、組み込み関数 zip は良く使われるので、今後の記事で解説する予定です。

上記の修正後に下記のプログラムで Mbtree_Anim のアニメーションを表示しようとすると、実行結果のような エラーが発生 します。エラーメッセージから、どのようなエラーが発生しているかについて少し考えてみて下さい。

Mbtree_Anim(mbtree, isscore=True)

実行結果

略
Cell In[4], line 100
     97     self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
     99 num_total = num_calculated + num_pruned
--> 100 num_ratio = num_calculated / num_total
    101 textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    102 datalist = [ num_calculated, num_pruned, num_total, num_ratio]

ZeroDivisionError: division by zero

ゼロ除算のエラー原因と修正

エラーメッセージから、下記のプログラムを実行した際に、0（zero）で（by）割り算（division）を行ったことが原因 であることがわかります。

num_ration = num_calculated / num_total

Mbtree_Anim で 最初に表示 されるのはアニメーションの 最初のフレーム で、最初のフレームでは αβ 法の 処理がまだ行われていない ので、A も P も 0 になるため、その合計である M も 0 になります。従って、R = A / M の計算は 0 ÷ 0 が計算される ことになるため、確かに 0 で割り算を行っています。

数学では 0 で割り算を行ってはいけない³ という 決まりがあり、0 で割り算することを 0 除算 と呼びます。Python を含む 多くのプログラム言語 では 0 除算を行うとエラーが発生 してプログラムが止まります⁴。そのため、上記のプログラムのように 0 除算が行われる可能性がある 場合は、「分母が 0 になる場合は割り算を行わずに別の処理を行う」ようにプログラムを記事する必要があります。

割り算の 代わりとなる処理 としては、「エラーメッセージを表示」する、「何らかの値を割り算の答えの代わりとする」など、状況に応じて適切な処理を選択する必要 があります。

今回の場合は、分子の A が 0 なので割合として 0 を代わりの答えとして計算 することにします⁵。下記はそのように修正したプログラムです。

if num_total != 0:
    num_ratio = num_calculated / num_total
else:
    num_ratio = 0

もしくは下記のプログラムのように記述しても良いでしょう。本記事ではこちらの方法を採用することにします。

num_ratio = num_calculated / num_total if num_total != 0 else 0

0 除算 はプログラムのエラーの中で 比較的良く発生するエラーの一つ です。上記の「何らかの 集合の中 で 特定の性質を持つものの割合 の計算」で起きるエラーは、初心者が発生させる 0 除算のエラーの典型例と言えるでしょう。

上記の A / M のような「何らかの集合の中で特定の性質を持つものの割合の計算」の場合は、0 ≦ A ≦ M という性質が必ず満たされるため、A / M の M が 0 の場合は A も必ず 0 になります。そのような場合は、下記のプログラムの 1 行目のように、合計を計算する際に組み込み関数 max を利用して 分母の最小値を 1 にする⁶ことで M が 0 の場合の答えとして 0 が計算される ようにすることもできます。

num_total = max(1, num_calculated + num_pruned)
num_ratio = num_calculated / num_total

上記の方法で 0 除算に対処するプログラムを見かけることがあるので紹介しました。

なお、M が 0 の場合に A が 0 にならないことがある場合 に上記の方法で計算を行うと、割合を表すはずの R の値が負の値や 1 を超える値になることがあるので、上記の方法は利用できない 点に注意して下さい。

0 除算に対する他の対処法としては、下記のプログラムのように以前の記事で紹介した、エラーが発生した際にプログラムを中断せずに特定の処理を行うという、例外処理を利用するという方法があります。

try:
    num_ratio = num_calculated / num_total
except:
    num_ratio = 0

数値の右揃えの表示

先程説明したように、num_ratio を計算する処理を下記のプログラムのように修正します。

num_ratio = num_calculated / num_total if num_total != 0 else 0

行番号のないプログラム

def update_ab(self):
    alpha, beta, score, status, num_calculated, num_pruned = self.mbtree.ablist_by_score[self.play.value]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    acolor = "red" if maxnode else "black"
    bcolor = "black" if maxnode else "red"
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3
    plus_inf = 4   
    alphacoord = max(minus_inf, alpha)
    betacoord = min(plus_inf, beta)
    
    color = "lightgray" if maxnode else "aqua"
    rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf,
                            height=1, fc=color)
    self.abax.add_patch(rect)
    rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord,
                            height=1, fc="yellow")
    self.abax.add_patch(rect)
    color = "aqua" if maxnode else "lightgray"
    rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
                            height=1, fc=color)
    self.abax.add_patch(rect)

    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")
        
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
                    arrowprops=arrowprops, ha="center", c=acolor)
    self.abax.plot(betacoord, 0, "ob")
    self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
                    arrowprops=arrowprops, ha="center", c=bcolor)
    if score is not None:
        self.abax.plot(score, 0, "og")
        self.abax.annotate(f"score = {score}", xy=(score, 0),
                        xytext=((minus_inf + plus_inf) / 2, 1), 
                        arrowprops=arrowprops, ha="center")
            
    facecolorlist = ["aqua", "yellow", "lightgray"]
    textcolorlist = ["black", "black", "black"]
    if maxnode:
        nodetype = f"深さ {self.selectednode.mb.move_count} max node"
        textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)", "α 値の更新なし (score ≦ α)"]
        if score is not None :
            if beta <= score:
                textcolorlist[0] = "red"
            elif alpha < score:
                textcolorlist[1] = "red"
            else:
                textcolorlist[2] = "red"
    else:
        nodetype = f"深さ {self.selectednode.mb.move_count} min node"
        textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)", "β 値の更新なし (score ≦ β)"]
        if score is not None :
            if score <= alpha:
                textcolorlist[0] = "red"
            elif score < beta:
                textcolorlist[1] = "red"
            else:
                textcolorlist[2] = "red"
            
    if status == "start":
        facecolor = "white"
        nodetype += " 処理の開始"
    elif status == "score":
        facecolor = "lightyellow"
        nodetype += " 子ノードの評価値"
    elif status == "update":
        facecolor = "lightcyan"
        if maxnode:
            nodetype += " α 値の処理"
        else:
            nodetype += " β 値の処理"
    else:
        facecolor = "lavenderblush"
        nodetype += " 評価値の確定"
    self.abfig.set_facecolor(facecolor)
    self.abax.text(6, 1, nodetype)   
    for i in range(3):
        rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5, fc=facecolorlist[i])
        self.abax.add_patch(rect)
        self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
    
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total if num_total != 0 else 0
    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    datalist = [ num_calculated, num_pruned, num_total, num_ratio]
    for i in range(4):
        self.abax.text(15, 1 - i * 0.7, textlist[i])
        self.abax.text(17, 1 - i * 0.7, datalist[i])
        
Mbtree_Anim.update_ab = update_ab

上記の修正後に下記のプログラムを実行するとエラーが発生しなくなり、実行結果のような表示が行われます。なお、ゲーム木の部分の表示は特に重要ではないので省略しました。

Mbtree_Anim(mbtree, isscore=True)

実行結果

下図は 最後のフレームでの表示 ですが、以下の点が わかりづらい 表示になっています。

数字が左揃えで表示 されている点がわかりづらい
割合の 小数点以下の表示が多すぎて わかりづらい
割合が % で表示されていない

そこで、数字を右揃えで表示 し、割合の数字を % の単位で小数点以下 1 桁までの数値で表示 するように修正することにします。

後者に関しては先程 dprint で割合を表示したのと同様の方法で修正することができます。

文字を右揃えで表示するには、Axes の text メソッドの 実引数に以下のような記述 を行います。なお、以前の記事で紹介した f 文字列 の > という 書式指定子 を利用して右揃えを行うこともできますが、その場合は 右揃えの位置 を 座標で設定できない という問題があるので本記事では採用しませんが、そちらの方が良いと思った方は採用しても良いでしょう。

x 座標 を表す実引数に、文字列の 右端の座標を記述 する
文字の表示の揃えを指定 するキーワード引数 ha="right" を記述 する

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

5 行目：割合を f 文字列を使って % の単位で小数点以下 1 桁までの文字列に修正する
8 行目：数値を表示する x 座標を文字の右端の座標に修正し、キーワード引数 ha="right" を記述するように修正する

 1  def update_ab(self):
元と同じなので省略
 2      num_total = num_calculated + num_pruned
 3      num_ratio = num_calculated / num_total if num_total != 0 else 0
 4      textlist = [ "計算済", "枝狩り", "合計", "割合" ]
 5      datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
 6      for i in range(4):
 7          self.abax.text(15, 1 - i * 0.7, textlist[i])
 8          self.abax.text(19.5, 1 - i * 0.7, datalist[i], ha="right")
 9          
10  Mbtree_Anim.update_ab = update_ab

行番号のないプログラム

def update_ab(self):
    alpha, beta, score, status, num_calculated, num_pruned = self.mbtree.ablist_by_score[self.play.value]
    maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
    acolor = "red" if maxnode else "black"
    bcolor = "black" if maxnode else "red"
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    self.abax.set_ylim(-1.5, 1.5)
    self.abax.axis("off")

    minus_inf = -3
    plus_inf = 4   
    alphacoord = max(minus_inf, alpha)
    betacoord = min(plus_inf, beta)
    
    color = "lightgray" if maxnode else "aqua"
    rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf,
                            height=1, fc=color)
    self.abax.add_patch(rect)
    rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord,
                            height=1, fc="yellow")
    self.abax.add_patch(rect)
    color = "aqua" if maxnode else "lightgray"
    rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
                            height=1, fc=color)
    self.abax.add_patch(rect)

    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")
        
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
                    arrowprops=arrowprops, ha="center", c=acolor)
    self.abax.plot(betacoord, 0, "ob")
    self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
                    arrowprops=arrowprops, ha="center", c=bcolor)
    if score is not None:
        self.abax.plot(score, 0, "og")
        self.abax.annotate(f"score = {score}", xy=(score, 0),
                        xytext=((minus_inf + plus_inf) / 2, 1), 
                        arrowprops=arrowprops, ha="center")
            
    facecolorlist = ["aqua", "yellow", "lightgray"]
    textcolorlist = ["black", "black", "black"]
    if maxnode:
        nodetype = f"深さ {self.selectednode.mb.move_count} max node"
        textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)", "α 値の更新なし (score ≦ α)"]
        if score is not None :
            if beta <= score:
                textcolorlist[0] = "red"
            elif alpha < score:
                textcolorlist[1] = "red"
            else:
                textcolorlist[2] = "red"
    else:
        nodetype = f"深さ {self.selectednode.mb.move_count} min node"
        textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)", "β 値の更新なし (score ≦ β)"]
        if score is not None :
            if score <= alpha:
                textcolorlist[0] = "red"
            elif score < beta:
                textcolorlist[1] = "red"
            else:
                textcolorlist[2] = "red"
            
    if status == "start":
        facecolor = "white"
        nodetype += " 処理の開始"
    elif status == "score":
        facecolor = "lightyellow"
        nodetype += " 子ノードの評価値"
    elif status == "update":
        facecolor = "lightcyan"
        if maxnode:
            nodetype += " α 値の処理"
        else:
            nodetype += " β 値の処理"
    else:
        facecolor = "lavenderblush"
        nodetype += " 評価値の確定"
    self.abfig.set_facecolor(facecolor)
    self.abax.text(6, 1, nodetype)   
    for i in range(3):
        rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5, fc=facecolorlist[i])
        self.abax.add_patch(rect)
        self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
    
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total if num_total != 0 else 0
    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
    datalist = [ num_calculated, num_pruned, num_total, f"{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")
        
Mbtree_Anim.update_ab = update_ab

修正箇所

def update_ab(self):
元と同じなので省略
    num_total = num_calculated + num_pruned
    num_ratio = num_calculated / num_total if num_total != 0 else 0
    textlist = [ "計算済", "枝狩り", "合計", "割合" ]
-   datalist = [ num_calculated, num_pruned, num_total, num_ratio]
+   datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
    for i in range(4):
        self.abax.text(15, 1 - i * 0.7, textlist[i])
-       self.abax.text(17, 1 - i * 0.7, datalist[i])
+       self.abax.text(19.5, 1 - i * 0.7, datalist[i], ha="right")
        
Mbtree_Anim.update_ab = update_ab

上記の修正後に下記のプログラムを実行し、0 フレーム目と最後のフレームを表示すると、実行結果のように 意図通りの表示が行われる ことが確認できます。

Mbtree_Anim(mbtree, isscore=True)

実行結果

また、下図のように 途中のフレーム での A、P、M、R の値が表示されることも確認できます。他の様々なフレームを表示して確認してみて下さい。

今回の記事のまとめ

今回の記事では、Mbtree_Anim で表示されているフレームまでの A、P、M、R の値を表示するようにプログラムを改良しました。

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

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

次回の記事

以前の記事で計算した〇× ゲームの ゲーム木のノードの数と一致 します ↩
num は数を表す number の略、calculated は計算済という意味です ↩
その理由について説明すると長くなるので本記事では説明しません。興味がある方は 0 除算というキーワードで調べてみると良いでしょう ↩
JavaScript など、一部のプログラム言語 では 0 除算を行っても エラーは発生せず、無限大を表す数値が計算 されるものもあります ↩
0 ÷ 0 の答えが 0 であると勘違いしている人がいるかもしれませんが、0 ÷ 0 は数学では 行ってはいけない計算 であり、答えは 0 ではありません ↩
0 / 正の数 = 0 になるので、正の数であれば 1 でなくてもかまいません ↩