目次と前回の記事

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

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

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

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

アニメーションの各フレームで行われる処理の視覚化

前回の記事では、下図のように数直線を使って α 値、β 値、子ノードの評価値の視覚化を行いましたが、前回の記事で説明したように、α 値や β 値の値が更新された際の理由がわかりづらいという問題がありました。

今回の記事では アニメーションの各フレームで行われる処理 を わかりやすく表示 するための改良を行います。

max ノードと min ノードで行われる処理の分類

αβ 法では max ノードで子ノードの評価値がが計算された際に、下記の処理を行います。

β 値 ≦ 子ノードの評価値 の場合
- α 値を子ノードの評価値に更新する
- β 狩りによって、残りの子ノードの評価値の計算処理を省略する
α 値 < 子ノードの評価値 < β 値 の場合
- α 値を子ノードの評価値に更新する
- 次の子ノードの評価値の計算処理を行う
子ノードの評価値 ≦ α 値
- α 値は更新しない
- 次の子ノードの評価値の計算処理を行う

上記の 1、2 はいずれも α 値を子ノードの評価値に更新する処理を行うので、α 値 を子ノードの評価値に 更新する範囲 は「α 値 < 子ノードの評価値」であることがわかります。

また、min ノードでは下記のようになります。

子ノードの評価値 ≦ α 値 の場合
- β 値を子ノードの評価値に更新する
- α 狩りによって、残りの子ノードの評価値の計算処理を省略する
α 値 < 子ノードの評価値 < β 値 の場合
- β 値を子ノードの評価値に更新する
- 次の子ノードの評価値の計算処理を行う
β 値 ≦ 子ノードの評価値 の場合
- β 値は更新しない
- 次の子ノードの評価値の計算処理を行う

max ノードの場合と同様の理由で min ノードの場合 は、β 値 を子ノードの評価値に 更新する範囲 は「子ノードの評価値 < β 値」であることがわかります。

範囲ごとの色分け

数直線の図で上記の max ノード の場合の 範囲の色を分けて塗る と下図のようになります。なお、水色と黄色の境界線 は水色、黄色と灰色の境界線 は 灰色の範囲 になります。

水色が上記の 1 の β 狩りを行う範囲、黄色が上記の 2 の α 値を更新する範囲、灰色が上記の 3 の α 値を更新しない範囲 を表します。3 種類の処理を行う 範囲を色分けする ことで、緑の円の 子ノードの評価値 が上図のように どの範囲にあるかが明確 になり、上記の 3 種類の どの処理が行われるかが一目でわかる ようになります。

min ノードの場合も色分けを行う範囲は変わりませんが、下図のように 枝狩りを行う範囲を水色、β 値を更新しない範囲を灰色 で 色分けを統一 したほうがわかりやすいでしょう。

そこで、本記事では下記の表のように範囲の色分けを行うことにします。

色	意味
水色	枝狩り（α 狩りまたは β 狩り）が行われる範囲
黄色	α 値または β 値を更新する範囲
灰色	α 値または β 値を更新しない範囲

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

上記のような表示が行われるように、Marubatsu_GUI クラスの update_ab メソッドを下記のプログラムのように修正します。なお、下記のプログラムでは上記の範囲に色を塗る修正に加えて、ゲーム木の上部に表示される α 値や β 値と同様に、更新の対象 となる α 値または β 値の 注釈の色を赤色で表示 するという修正も行っています。

8 ~ 10 行目：max ノードであるかどうかの判定は、この後で何度も行う必要があるので、maxnode という変数に max ノードである場合に True、そうでない場合に False を代入し、それを使って acolor と bcolor の値を代入するように修正する
13、14 行目：範囲の塗りつぶし を行う際には、α 値の値ではなく、α 値を数直線上に描画する座標の値が必要 になるので、その値を表す alphacoord や betacoord の 計算の処理 を この場所に移動 する必要がある
16 ~ 19 行目：負の無限大を表す座標（minus_inf）から α 値を表す座標（alphacoord）までの範囲の長方形の塗りつぶしの色を 16 行目で計算し、17 ~ 19 行目でその色でその範囲を塗りつぶす。塗りつぶす長方形の y 座標の範囲は筆者が試行錯誤して設定した値なので自由に変更しても良い
20 ~ 26 行目：上記と同様の方法で残りの範囲を塗りつぶす。なお、α 値から β 値までの範囲は常に黄色で塗りつぶせばよいので色を計算する必要はない
上記の 塗りつぶしの処理 は、28 行目以降の 数直線などを描画する前に行わないと、数直線の上に灰色の長方形などが描画されてしまうため、数直線が見えなくなってしまう 点に注意すること
32、35 行目：α 値の注釈の色（β 値の注釈も同様）は、9 行目で計算済なので、キーワード引数 c=acolor を記述してその色で α 値の注釈が描画されるように修正する

 1  from marubatsu import Marubatsu
 2  from tree import Mbtree_Anim
 3  import matplotlib.patches as patches
 4
 5  def update_ab(self):
 6      fontsize = 70 * self.size
 7      alpha, beta, score, message = self.mbtree.ablist_by_score[self.play.value]
 8      maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
 9      acolor = "red" if maxnode else "black"
10      bcolor = "black" if maxnode else "red"
元と同じなので省略
11      minus_inf = -3
12      plus_inf = 4   
13      alphacoord = max(minus_inf, alpha)
14      betacoord = min(plus_inf, beta)
15
16      color = "lightgray" if maxnode else "aqua"
17      rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphacoord-minus_inf, 
18                               height=1, fc=color)
19      self.abax.add_patch(rect)
20      rect = patches.Rectangle(xy=(alphacoord, -0.5), width=betacoord-alphacoord, 
21                               height=1, fc="yellow")
22      self.abax.add_patch(rect)
23      color = "aqua" if maxnode else "lightgray"
24      rect = patches.Rectangle(xy=(betacoord, -0.5), width=plus_inf-betacoord,
25                               height=1, fc=color)
26      self.abax.add_patch(rect)
27
28      self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
元と同じなので省略
29      arrowprops = { "arrowstyle": "->"}
30      self.abax.plot(alphacoord, 0, "or")
31      self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
32                         arrowprops=arrowprops, ha="center", c=acolor)
33      self.abax.plot(betacoord, 0, "ob")
34      self.abax.annotate(f"β = {beta}", xy=(betacoord, 0), xytext=(plus_inf, 1),
35                         arrowprops=arrowprops, ha="center", c=bcolor)
元と同じなので省略
36        
37  Mbtree_Anim.update_ab = update_ab

行番号のないプログラム

from marubatsu import Marubatsu
from tree import Mbtree_Anim
import matplotlib.patches as patches

def update_ab(self):
    fontsize = 70 * self.size
    alpha, beta, score, message = 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.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
    self.ax.text(9, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
    self.ax.text(19, -1, message, fontsize=fontsize)             
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 14)
    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")
        
Mbtree_Anim.update_ab = update_ab

修正箇所

from marubatsu import Marubatsu
from tree import Mbtree_Anim
import matplotlib.patches as patches

def update_ab(self):
    fontsize = 70 * self.size
    alpha, beta, score, message = self.mbtree.ablist_by_score[self.play.value]
+   maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
-   acolor = "red" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "black"
+   acolor = "red" if maxnode else "black"
-   bcolor = "black" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "red"
+   bcolor = "black" if maxnode else "red"    
元と同じなので省略
    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")
元と同じなので省略
-   alphacoord = max(minus_inf, alpha)
-   betacoord = min(plus_inf, beta)
    arrowprops = { "arrowstyle": "->"}
    self.abax.plot(alphacoord, 0, "or")
    self.abax.annotate(f"α = {alpha}", xy=(alphacoord, 0), xytext=(minus_inf, 1),
-                      arrowprops=arrowprops, ha="center")
+                      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")
+                      arrowprops=arrowprops, ha="center", c=bcolor)
元と同じなので省略
        
Mbtree_Anim.update_ab = update_ab

上記の修正後に下記のプログラムで αβ 法で評価値を計算した mbtree に対して Mbtree_Anim を実行すると、実行結果のように 数直線上の範囲が塗りつぶさ、更新の対象 となる α 値が 赤色で描画される ことが確認できます。

from tree import Mbtree

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

実行結果

上図では黄色の範囲しか描画されませんが、下図の 50 フレーム目の max ノード では 3 つの範囲が正しい色で描画 され、α 値の注釈が赤色 で正しく描画されることが確認できます。

また、その次の下図の 51 フレーム目の min ノード では 3 つの 範囲の色の順番が max ノードの逆 になり、β 値の注釈が赤色 で正しく描画されることが確認できます。

塗りつぶしの処理を for 文で下記のプログラムのようにまとめることもできます。

1 行目：3 つの範囲の色を要素として持つ list を変数に代入する
2 行目：負の無限大の座標、α 値の座標、β 値の座標、正の無限大の座標を要素として持つ list を変数に代入する
3 行目：3 つの範囲を描画するために、0 から 2 までの整数の繰り返し処理を行う
4 行目：i 番の塗りつぶしの幅を計算する
5 行目：i 番の塗りつぶしの色を計算する。なお、× の手番では i が 0、1、2 の場合の色はそれぞれ color[2]、color[1]、color[0] になるので、color[2 - i] という式で計算できる
6 ~ 8 行目：i 番の長方形を numlist、colorlist の i 番の要素と 4 行目で計算した幅を利用して描画する

1  colorlist = ["lightgray", "yellow", "aqua"]
2  numlist = [minus_inf, alphacoord, betacoord, plus_inf]
3  for i in range(3):
4      width = numlist[i + 1] - numlist[i]
5      color = colorlist[i] if maxnode else colorlist[2 - i]
6      rect = patches.Rectangle(xy=(numlist[i], -0.5), width=width, height=1,
7                               fc=color)
8      self.abax.add_patch(rect)

上記のようにまとめることで、プログラムが短くなる、色を変更する際に 1 行目だけを修正すれば良くなるなどの利点が得られますが、プログラムがわかりづらくなるという欠点が生じるので、上記のプログラムは本記事では採用しません。

塗りつぶしの種類がもっと多くなった場合や、それぞれでもっと複雑な処理を行う必要がある場合はこのような方法を採用したほうが良いでしょう。実際に、この後で上記のような方法でプログラムを記述することにします。

塗りつぶしの色の説明の描画

それぞれの 塗りつぶしの色が何を意味するか が わかりづらい ので、その説明を表示 したほうが良いでしょう。また、子ノードの評価値が計算された際に、どの処理が行われるかを明確にする ために、範囲の 説明文の色を赤色で表示 するとさらにわかりやすくなります。

具体的には、下図のような説明を数直線の右に描画します。もっとわかりやすい表示方法を思いついた人は自由に変更して下さい。

1 行目にゲーム木の赤枠の選択中の「ノードの深さとノードの種類」を表示する
2 ~ 4 行目にそれぞれの範囲の色の説明を表示する
下図のように 子ノードの評価値が表示される場合 は、その 評価値を含む範囲の文字を赤色で表示 する
子ノードの評価値が表示されない場合 や、子ノードの評価値の 範囲でない 文字は 黒色で表示 する

下記はそのように Marubastu_Anim クラスの update_ab を修正したプログラムです。facecolorlist など に代入された list の要素 は、2 ~ 4 行目の表示に関するデータ を表します。また、2 ~ 4 行目の描画処理を 1 つずつ別々に記述すると、プログラムがかなり長くなるので、先程のノートで紹介した方法で for 文を使って行うように工夫しました。

2 行目：右に表示する、範囲の色を表す list を変数に代入する
3 行目：右に表示する、範囲の説明文の文字の色を表す list を変数に代入する。初期値 として すべての要素 を黒色を表す "black" とし、この後で 赤く表示する必要がある行に対応する要素を "red" に変更 する
4 ~ 14 行目：max ノードの場合の処理を行う
5 行目：1 行目に表示する「ノードの深さと種類」を表す文字列を変数に代入する
6、7 行目：右に表示する、範囲の説明文を表す list を変数に代入する
8 ~ 14 行目：子ノードの評価値が score に代入されている場合に、score を含む範囲に対応する textcolorlist の要素を "red" に変更 する
15 ~ 25 行目：min ノードの場合に上記と同様の処理を行う
27 行目：右の 1 行目の文字列の描画を行う
28 ~ 32 行目：上記で計算したデータを使って、右の 2 ~ 4 行目の描画を行う。29、30 行目で長方形の y 座標に 0.3 - i * 0.7 を記述 することで、1 行ごとに 0.7 ずつ下にずらして長方形が描画 される。32 行目で範囲の説明文を描画する y 座標も同様の方法で計算する。なお、色のついた長方形と説明文の描画位置は筆者が試行錯誤して調整したものなので、別のレイアウトで描画を行いたい場合は自由に変更しても良い

 1  def update_ab(self):
元と同じなので省略
 2      facecolorlist = ["aqua", "yellow", "lightgray"]
 3      textcolorlist = ["black", "black", "black"]
 4      if maxnode:
 5          nodetype = f"深さ {self.selectednode.mb.move_count} max node"
 6          textlist = ["β 狩り (β ≦ score)", "α 値の更新 (α < score < β)",
 7                      "α 値の更新なし (score ≦ α)"]
 8          if score is not None :
 9              if beta <= score:
10                 textcolorlist[0] = "red"
11              elif alpha < score:
12                 textcolorlist[1] = "red"
13              else:
14                 textcolorlist[2] = "red"
15      else:
16          nodetype = f"深さ {self.selectednode.mb.move_count} min node"
17          textlist = ["α 狩り (score <= α)", "β 値の更新 (α < score < β)",
18                      "β 値の更新なし (score ≦ β)"]
19          if score is not None :
20              if score <= alpha:
21                 textcolorlist[0] = "red"
22              elif score < beta:
23                 textcolorlist[1] = "red"
24              else:
25                textcolorlist[2] = "red"
26  
27      self.abax.text(6, 1, nodetype)   
28      for i in range(3):
29          rect = patches.Rectangle(xy=(5, 0.3 - i * 0.7), width=0.8, height=0.5,
30                                   fc=facecolorlist[i])
31          self.abax.add_patch(rect)
32          self.abax.text(6, 0.4 - i * 0.7, textlist[i], c=textcolorlist[i])    
33         
34  Mbtree_Anim.update_ab = update_ab

行番号のないプログラム

def update_ab(self):
    fontsize = 70 * self.size
    alpha, beta, score, message = 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.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
    self.ax.text(9, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
    self.ax.text(19, -1, message, fontsize=fontsize)             
                            
    self.abax.clear()
    self.abax.set_xlim(-4, 14)
    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"

    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])    
        
Mbtree_Anim.update_ab = update_ab

修正箇所

def update_ab(self):
元と同じなので省略
+   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"

+   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])    
        
Mbtree_Anim.update_ab = update_ab

表示の確認

上記の修正後に下記のプログラムを実行し、いくつかのフレームを表示 してプログラムが 正しく動作するかどうかを確認 します。

具体的には以下のフレームでの処理を確認します。

ノードの処理が開始されたフレーム
枝狩りが行われるフレーム
枝狩りが行われなかった場合に α 値または β 値が更新されるフレーム
α 値または β 値が更新されないフレーム
ゲームの決着がついた局面の評価値が計算されるフレーム

Mbtree_Anim(mbtree, isscore=True)

ノードの処理が開始されたフレームの表示の確認

下記は最初の 0 フレーム目の max ノード の 処理を開始するフレーム の図です。以下のように正しい描画が行われていることが確認できます。なお、実際に描画される内容をすべて表示すると図が大きくなりすぎるので、重要でない部分は図から省略します。

α 値の注釈が赤色で描画されている
右の 1 行目に「深さ 0 max node」が表示されている
右の 2 ~ 4 行目に、max ノードの場合の説明が表示されている
このフレームでは子ノードの評価値が計算されていないので、右の 2 ~ 4 行目の文字の色はすべて黒色で表示されている

下記はその次の 1 フレーム目の min ノード の 処理を開始するフレーム の図です。以下のように正しい描画が行われていることが確認できます。

β 値の注釈が赤色で描画されている
右の 1 行目に「深さ 1 min node」が表示されている
右の 2 ~ 4 行目に、min ノードの場合の説明が表示されている
このフレームでは子ノードの評価値が計算されていないので、右の 2 ~ 4 行目の文字の色はすべて黒色で表示されている

枝狩りを行うフレームの表示の確認

下記は 18 フレーム目の min ノード の α 狩りを行う直前のフレーム の図です。以下のように正しい描画が行われていることが確認できます。

β 値の注釈が赤色で描画されている
右の 1 行目に「深さ 7 min node」が表示されている
右の 2 ~ 4 行目に、min ノードの場合の説明が表示されている
このフレームでは子ノードの評価値が計算されており、子ノードの評価値は水色の α 狩りを行う範囲¹なので、2 行目の水色の説明文が赤字で表示 されている

下記はその次の 19 フレーム目の図で、α 狩りが行われた結果、β 値 が上図の 子ノードの評価値の値に更新されている ことが確認できます。

下記はその次の 20 フレーム目の図で、α 狩りが行われた結果、赤枠の残りの 子孫ノードの色が暗い ことから、それらのノードの評価値を計算する処理を行わず に赤枠のノードの 評価値が確定 したことが確認できます。

説明は上記とほぼ同じなので省略しますが、下記の 97 フレーム目の max ノード の β 狩りを行う直前のフレーム の図と、その後の 2 フレームの図から正しい描画が行われていることが確認できます。

枝狩りが行われずに α 値や β 値が更新されるフレームの表示の確認

下記は 9 フレーム目の max ノード の図です。以下のように正しい描画が行われていることが確認できます。

α 値の注釈が赤色で描画されている
右の 1 行目に「深さ 6 のmax node」が表示されている
右の 2 ~ 4 行目に、max ノードの場合の説明が表示されている
このフレームでは子ノードの評価値が計算されており、子ノードの評価値は黄色の α 値を更新する範囲なので、3 行目の黄色の説明文が赤字で表示 されている

下記はその次の 10 フレーム目の図で、α 値が 上図の 子ノードの評価値の値に更新 されていることが確認できます。

説明は上記とほぼ同じなので省略しますが、下記の 28 フレーム目の min ノード の β 値を更新する直前のフレーム の図と、その次の β 値が更新されるフレーム の図から正しい描画が行われていることが確認できます。

α 値や β 値が更新されないフレームの表示の確認

下記は 15 フレーム目の max ノード の図です。以下のように正しい描画が行われていることが確認できます。

α 値の注釈が赤色で描画されている
右の 1 行目に「深さ 8 max node」が表示されている
右の 2 ~ 4 行目に、max ノードの場合の説明が表示されている
このフレームでは子ノードの評価値が計算されており、子ノードの評価値は灰色の α 値を更新しない範囲²なので、4 行目の灰色の説明文が赤字で表示 されている

下記はその次の 16 フレーム目の図で、α 値 が 変化していない ことが確認できます。

説明は上記とほぼ同じなので省略しますが、下記の 38 フレーム目の min ノード の β 値を更新しない直前のフレーム の図と、その次のフレーム の図から正しい描画が行われていることが確認できます。

ゲームの決着がついた局面の評価値が計算されるフレームの確認

下記は 8 フレーム目の min ノード で、決着がついた局面の評価値が確定したフレーム の図です。min ノード では評価値が確定したフレームの β 値がそのフレームの評価値 となりますが、β 値が -inf のまま 1 に更新されない という 問題があることが確認 できました。

下記は 137 フレーム目の max ノード で、決着がついた局面の評価値が確定したフレーム の図で、上記と同様に α 値が 1 のまま -1 更新されない という 問題があります。

この問題については、この後でフレームで行われる処理の明確化を行う際に修正します。

余裕がある方は他のフレームでどのように表示されるかどうかを確認してみて下さい。

フレームで行われる処理の明確化

上記でかなりわかりやすくなったのではないかと思いますが、子ノードの評価値が表示されないフレーム で行われる 処理の区別 が下記のように わかりづらい という問題があります。

以前の記事では下記の表のように フレームで行われた処理 を 9 種類に分類 しました。

	行われた処理	メッセージの例
①	ノードの処理が開始 (`calc_ab_score` が呼ばれた直後）	このノードの処理の開始
②	子ノードの評価値の計算の直後	child score = 0
③	max ノードで β 狩りを行う	child score = 0 ≧ -1(β 値) による β 狩り
④	max ノードで α 値を更新する	child score = 0 > -inf(α 値) による α 値の更新
⑤	max ノードで α 値を更新しない	child score = 0 ≦ 1(α 値) なので α 値は更新しない
⑥	min ノードで α 狩りを行う	child score = 0 ≦ 1(α 値) による α 狩り
⑦	min ノードで β 値を更新する	child score = 0 < inf(β 値) による β 値の更新
⑧	min ノードで β 値を更新しない	child score = 0 ≧ -1(β 値) なので β 値は更新しない
⑨	ノードの処理が終了	このノードの評価値が 0 で確定

今回の記事ではこの表の ② のフレーム に対して、数直線上に子ノードの評価値を表示 し、右の 2 ~ 4 行目の その次のフレームで行う処理の説明文を赤字で表示 するという工夫を行ないましたが、それ以外のフレームでの表示 は 全く同じ なので 区別がつきません³。

上記の表の ③ ~ ⑧ のフレーム は、いずれも ② のフレームの 次のフレームで行われる処理 を表しているので、それらをまとめて 下記の表の 4 種類の状態を区別できるようにする ことにします。なお、③ ~ ⑧ に対する説明文は「α 値の処理」のように表記しますが、α 値または β 値を 更新しないという処理も含みます。

行われた処理	右の 1 行目の表示例	背景色
① ノードの処理が開始	深さ 0 max node 処理の開始	白
② 子ノードの評価値の計算の直後	深さ 0 max node 子ノードの評価値	薄黄色
③ ~ ⑧ α 値または β 値に対する処理	深さ 0 max node α 値の処理	薄水色
⑨ ノードの処理が終了して評価値が確定	深さ 0 max node 評価値の確定	薄紫色

具体的には数直線の 右の 1 行目 に 上の表のような表示 を行います。また、文字の表示だけではわかりづらいので、Figure の背景色 を 上の表のように塗りつぶす ことで、現在の状態が一目でわかる ようにします。

また、上記の表示を行うことで、ゲーム木の上に表示していた α 値、β 値、メッセージの表示 はもう 必要がなくなる ので、それらの表示を削除する ことにします。

③ ~ ⑧ のそれぞれに対して別のメッセージと、別の背景色を設定することもできますが、色が多すぎる と かえってわかりづらくなる という欠点が生じます。

Mbtree クラスの `calc_node_by_ab` の修正

Mbtree_Anim で上記のような表示を行うためには、それぞれのアニメーションのフレームで そのフレームが上記のどの状態であるかを記録しておく 必要があります。現状では、アニメーションのフレームの情報を表す ab_list_by_score 属性の要素には (α 値, β 値, 子ノードの評価値, メッセージ) という tuple が代入されていますが、ゲーム木の上に表示していた メッセージの情報は必要がなくなった ので、(α 値, β 値, 子ノードの評価値, フレームの状態を表す文字列) という tuple を代入するように修正することにします。また、フレームの状態を表す文字列 は、以下のように設定することにします。なお、③ ~ ⑧ の状態を表す文字列を更新を表す "update" としましたが、先程説明したように α 値や β 値を変更しない場合も含むので、別のもっと良い文字列を思いついた方は変更して下さい。

行われた処理	状態を表す文字列
ノードの処理が開始	`"start"`
子ノードの評価値の計算の直後	`"score"`
③ ~ ⑧ の α 値または β 値に対する処理	`"update"`
ノードの処理が終了して評価値が確定	`"end"`

また、上記とは別に先程の検証で発見した、決着がついた局面で評価値が確定したフレーム で α 値または β 値が評価値の値に更新されない という バグを修正する ことにします。

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

6 行目：ablist_by_score に追加する tuple の最後の要素を "start" に修正する
10 ~ 13 行目：決着がついているノードの場合は、α 値または β 値をノードの評価値に更新することで、α 値または β 値が更新されないバグを修正 する
19、31 行目：ablist_by_score に追加する tuple の最後の要素を "score" に修正する
20、21 行目：max ノードで α 値が更新されるのは今回の記事の最初で説明したように score > alpha の場合なので、その条件が満たされる場合に alpha を score で更新する処理を行うように修正する。なお、メッセージに関する処理は必要がないので削除した
22、23 行目：20、21 行目のように修正することで、nodelist_by_score と ablist_by_score にフレームの情報を追加する処理を 22、23 行目でまとめて行うことができるようになる。また、その際に ablist_by_score に追加する tuple の最後の要素を "update" に修正する
24、25 行目：β 狩りが行われる場合に break 文を実行して残りの子ノードの評価値を計算する処理を省略する
27 ~ 38 行目：min ノードに対しても上記と同様の処理を行うように修正する
41 行目：ablist_by_score に追加する tuple の最後の要素を "end" に修正する

 1  def calc_score_by_ab(self, abroot, debug=False):           
 2      self.count = 0
 3       
 4      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
 5          self.nodelist_by_score.append(node)
 6          self.ablist_by_score.append((alpha, beta, None, "start"))
 7          self.count += 1
 8          if node.mb.status != Marubatsu.PLAYING:
 9              self.calc_score_of_node(node)
10              if node.mb.turn == Marubatsu.CIRCLE:
11                  alpha = node.score
12              else:
13                  beta = node.score
14          else:
15              if node.mb.turn == Marubatsu.CIRCLE:
16                  for childnode in node.children:
17                      score = calc_ab_score(childnode, alpha, beta)
18                      self.nodelist_by_score.append(node)
19                      self.ablist_by_score.append((alpha, beta, score, "score"))
20                      if score > alpha:
21                          alpha = score
22                      self.nodelist_by_score.append(node)
23                      self.ablist_by_score.append((alpha, beta, None, "update"))
24                      if score >= beta:
25                          break
26                  node.score = alpha
27              else:
28                  for childnode in node.children:
29                      score = calc_ab_score(childnode, alpha, beta)
30                      self.nodelist_by_score.append(node)
31                      self.ablist_by_score.append((alpha, beta, score, "score"))
32                      if score < beta:
33                          beta = score
34                      self.nodelist_by_score.append(node)
35                      self.ablist_by_score.append((alpha, beta, None, "update"))
36                      if score <= alpha:
37                          break
38                  node.score = beta
39 
40          self.nodelist_by_score.append(node)
41          self.ablist_by_score.append((alpha, beta, None, "end"))
元と同じなので省略
42     
43 Mbtree.calc_score_by_ab = calc_score_by_ab

行番号のないプログラム

def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
    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.count += 1
        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"))
                    if score > alpha:
                        alpha = score
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update"))
                    if score >= beta:
                        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"))
                    if score < beta:
                        beta = score
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update"))
                    if score <= alpha:
                        break
                node.score = beta

        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, None, "end"))
        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")
    self.nodelist_by_score = []
    self.ablist_by_score = []
    calc_ab_score(abroot)
    dprint(debug, "count =", self.count) 
    
Mbtree.calc_score_by_ab = calc_score_by_ab

修正箇所

def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
    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, "このノードの処理の開始"))
+       self.ablist_by_score.append((alpha, beta, None, "start"))
        self.count += 1
        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, f"child score = {score}"))
+                   self.ablist_by_score.append((alpha, beta, score, "score"))
-                   if score >= beta:
-                       alpha = score
-                       self.nodelist_by_score.append(node)
-                       self.ablist_by_score.append((alpha, beta, None, f"child score = {score} ≧ {beta}(β値) によるβ狩り"))
-                       break
                    if score > alpha:
+                       message = f"child score = {score} > {alpha}(α値)によるα値の更新"
                        alpha = score
-                   else:
-                       message = f"child score = {score} ≦ {alpha}(α値)なのでα値の更新は行わない"
                    self.nodelist_by_score.append(node)
-                   self.ablist_by_score.append((alpha, beta, None, message))
+                   self.ablist_by_score.append((alpha, beta, None, "update"))
+                   if score >= beta:
+                       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, f"child score = {score}"))
+                   self.ablist_by_score.append((alpha, beta, score, "score"))
-                   if score <= alpha:
-                       beta = score
-                       self.nodelist_by_score.append(node)
-                       self.ablist_by_score.append((alpha, beta, None, f"child score = {score} ≦ {alpha}(α値)によるα狩り"))
-                       break
                    if score < beta:
-                       message = f"child score = {score} < {beta}(β値) によるβ値の更新"
                        beta = score
-                   else:
-                       message = f"child score = {score} ≧ {beta}(β値) なのでβ値の更新は行わない"
                    self.nodelist_by_score.append(node)
-                   self.ablist_by_score.append((alpha, beta, None, message))
+                   self.ablist_by_score.append((alpha, beta, None, "update"))
+                   if score <= alpha:
+                       break
                node.score = beta

        self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alpha, beta, None, f"このノードの評価値が {node.score} で確定"))
+       self.ablist_by_score.append((alpha, beta, None, "end"))
元と同じなので省略
    
Mbtree.calc_score_by_ab = calc_score_by_ab

Mbtree_Anim クラスの `init` メソッドと `update_gui` メソッドの修正

ゲーム木の上部に α 値などを表示しなくなった ので、__init__ メソッドを下記のプログラムの 6 行目のように Figure の高さ を表す height 属性の値を 66 から 65 に修正 します。

 1  def __init__(self, mbtree:Mbtree, isscore:bool=False, size:float=0.15):
 2      self.mbtree = mbtree
 3      self.isscore = isscore
 4      self.size = size
 5      self.width = 50
 6      self.height = 65
 7      self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
 8      self.nodenum = len(self.nodelist)
 9      super(Mbtree_Anim, self).__init__()
10     
11  Mbtree_Anim.__init__ = __init__

行番号のないプログラム

def __init__(self, mbtree:Mbtree, isscore:bool=False, size:float=0.15):
    self.mbtree = mbtree
    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)
    super(Mbtree_Anim, self).__init__()
    
Mbtree_Anim.__init__ = __init__

修正箇所

def __init__(self, mbtree:Mbtree, isscore:bool=False, size:float=0.15):
    self.mbtree = mbtree
    self.isscore = isscore
    self.size = size
    self.width = 50
-   self.height = 66
+   self.height = 65
    self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
    self.nodenum = len(self.nodelist)
    super(Mbtree_Anim, self).__init__()
    
Mbtree_Anim.__init__ = __init__

同様の理由で update_gui メソッドを下記のプログラムの 4 行目のように Axes の y 座標の表示範囲 を -1 ~ self.height - 1 の範囲修正します。

 1  def update_gui(self):
 2      self.ax.clear()
 3      self.ax.set_xlim(-1, self.width - 1)
 4      self.ax.set_ylim(-1, self.height - 1)   
元と同じなので省略   
 5  Mbtree_Anim.update_gui = update_gui

行番号のないプログラム

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:
        self.update_ab()
                            
    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):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
-   self.ax.set_ylim(-2, self.height - 2)   
+   self.ax.set_ylim(-1, self.height - 1)   
元と同じなので省略   
Mbtree_Anim.update_gui = update_gui

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

最後に update_ab メソッドを下記のプログラムのように修正します。

5 行目の下にあった、ゲーム木の Figure の上部に α 値などを表示する処理を削除する
8 ~ 22 行目：それぞれのフレームの状態に応じて、Figure の背景色を facecolor に代入し、右の 1 行目に表示する文字列にメッセージを += 演算子を利用して追加する。別の色を設定したい場合はこちらのリンク先のウェブページなどを参考にするとよい。メッセージに 追加する文字列の先頭を空白文字にしないと、追加した文字列とその前の文字列が くっついてしまう 点に注意すること
23 行目：Figure の set_facecolor メソッドを呼び出して、Figure の背景色を変更する。set_facecolor について忘れた方は以前の記事を復習すること

 1  def update_ab(self):
 2      alpha, beta, score, status = self.mbtree.ablist_by_score[self.play.value]
 3      maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
 4      acolor = "red" if maxnode else "black"
 5      bcolor = "black" if maxnode else "red"
 6                             
 7      self.abax.clear()
元と同じなので省略
 8      if status == "start":
 9          facecolor = "white"
10          nodetype += " 処理の開始"
11      elif status == "score":
12          facecolor = "lightyellow"
13          nodetype += " 子ノードの評価値"
14      elif status == "update":
15          facecolor = "lightcyan"
16          if maxnode:
17              nodetype += " α 値の処理"
18          else:
19              nodetype += " β 値の処理"
20      else:
21          facecolor = "lavenderblush"
22          nodetype += " 評価値の確定"
23      self.abfig.set_facecolor(facecolor)
24      self.abax.text(6, 1, nodetype)   
元と同じなので省略    
25         
26  Mbtree_Anim.update_ab = update_ab

行番号のないプログラム

def update_ab(self):
    alpha, beta, score, status = 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, 14)
    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])    
        
Mbtree_Anim.update_ab = update_ab

修正箇所

def update_ab(self):
    alpha, beta, score, status = 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.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
-   self.ax.text(9, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
-   self.ax.text(19, -1, message, fontsize=fontsize)                             

    self.abax.clear()
元と同じなので省略
+   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)   
元と同じなので省略    
        
Mbtree_Anim.update_ab = update_ab

表示の確認

上記の修正後に下記のプログラムで修正した calc_score_by_ab を呼び出して αβ 法で評価値を計算しなおし、Mbtree_Anim で正しく表示が行われるかを確認します。

mbtree.calc_score_by_ab(mbtree.root)
Mbtree_Anim(mbtree, isscore=True)

具体的には先程示した 下記の表のように表示される かどうかを確認します。

行われた処理	右の 1 行目の表示例	背景色
① ノードの処理が開始	深さ 0 max node 処理の開始	白
② 子ノードの評価値の計算の直後	深さ 0 max node 子ノードの評価値	薄黄色
③ ~ ⑧ α 値または β 値に対する処理	深さ 0 max node α 値の処理	薄水色
⑨ ノードの処理が終了して評価値が確定	深さ 0 max node 評価値の確定	薄紫色

また、決着がついた局面で評価値が確定したフレームで α 値または β 値が評価値の値に更新されないという バグが修正されているか どうかも確認します。

ノードの処理が開始されたフレームの表示の確認

下記はノードの処理が開始された 0 フレーム目の図です。「深さ 0 max node 処理の開始」という表示と、Figure の 背景色が白色で表示 されることが確認できます。また、ゲーム木の Figure の上部に 表示されていた α 値などの メッセージが表示されなくなっている ことが確認できます。

子ノードの評価値の計算の直後のフレームの表示の確認

下記は子ノードの評価値の計算の直後の 9 フレーム目の図です。「深さ 6 max node 子ノードの評価値」という表示と、Figure の 背景色が薄黄色で表示 されることが確認できます。

上図は次のフレームで α 値を更新する評価値が計算された場合の図ですが、下図のように α 狩りを行う評価値が計算された場合も薄黄色で表示されます。

興味がある方は β 狩りや、α 値や β 値を更新しない評価値が計算された場合も薄黄色で表示されることを確認してみて下さい。

α 値または β 値に対する処理が行われるフレームの表示の確認

下記は先ほどの 9 フレーム目の次の α 値の更新処理が行われたフレームの図です。「深さ 6 min node α 値の処理」という表示と、Figure の 背景色が薄水色で表示 されることが確認できます。

興味がある方は β 値が更新されるフレームや、α 値や β 値を更新しないフレームの価値の場合も薄水色で表示されることを確認してみて下さい。

ノードの処理が終了して評価値が確定したフレームの表示の確認

下記はノードの評価値が確定した 20 フレーム目の図です。「深さ 7 min node 評価値の確定」という表示と、Figure の 背景色が薄紫色で表示 されることが確認できます。

下記は 決着がついた局面の max ノードの評価値が確定 した 8 フレーム目の図です。「深さ 7 min node 評価値の確定」という表示と、Figure の背景色が薄紫色で表示されることが確認できます。また、先程は β 値が -inf のまま更新されないというバグがありましたが、下図では β 値が正しく 1 に更新 されているので、先程のバグが修正された ことが確認できます。

下記は 決着がついた局面の min ノードの評価値が確定 した 137 フレーム目の図です。先程は α 値が 1 のまま更新されないというバグがありましたが、下図では α 値が正しく -1 に更新 されているので、先程のバグが修正された ことが確認できます。

今回の記事のまとめ

今回の記事では、αβ 法で行われる評価値の計算手順のアニメーションで、それぞれのフレームが行う処理を視覚的にわかりやすく表示 するように改良を行いました。

なお、視覚的にわかりやすくする改良方法は、本記事の方法以外にも様々な方法が考えられます。本記事よりも良い改良方法を思いついた方はその実装にチャレンジしてみて下さい。

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

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

次回の記事

min ノードで α 狩りを行う範囲は「子ノードの評価値 ≦ α 値」なので、水色と黄色の 境目は水色の範囲に含まれます ↩
max ノードで α 値を更新しない範囲は「子ノードの評価値 ≦ α 値」なので、灰色と黄色の 境目は灰色の範囲に含まれます ↩
実際には、ゲーム木の上部に表示されるメッセージで区別がつくようにしていますが、文章での区別 は 直観的ではなく、わかりやすいとは言えない でしょう ↩