Pythonで〇×ゲームのAIを一から作成する その161 αβ 法の視覚化のための Mbtree_Anim の修正 その 2

目次と前回の記事

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

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

リンク	説明
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 の修正のうち、常に表示する内容の表示の実装を行いました。今回の記事はその続きです。

視覚化の検討のおさらい

以前の記事で行った αβ 法の視覚化と、フレームに記録するデータの検討結果は以下の通りです。

常に表示する内容

常に表示する内容と、表示するために必要な情報は以下の表の通りです。以前の記事で検討したミニマックス法での表示と共通する内容は省略しました。

なお、この部分は前回の記事で実装しました。

表示内容	必要な情報
α 値と β 値の初期値 範囲の色分け 範囲の説明	α 値と β 値の初期値

"start" 以外の状態で表示する内容

"start" 以外 の状態で表示する内容と、表示するために必要な情報は以下の通りです。

表示内容	必要な情報
置換表の範囲	置換表の範囲の下界と上界
置換表の登録の区別	置換表に登録されているかどうか

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

それぞれのフレームの状態で表示する内容は以下の通りです。上記の "start" 以外の状態で表示する内容は省略しました。なお、ミニマックス法と共通する内容には先頭に（※）を記述しました。

• "start" の状態
  なし
• "tt" の状態
  • 置換表にノードの評価値が登録されている場合
    • （※）赤字で「置換表に登録済」を表示
    • ミニマックス法で表示した置換表に登録されていた評価値は 表示しない
    • 置換表による枝狩りが行われている場合
      • $l=u$ の場合は赤字で「置換表による枝狩り（exact value）」を表示
      • $u≦α$ の場合は赤字で「置換表による枝狩り（fail low）」を表示
      • $β≦l$ の場合は赤字で「置換表による枝狩り（fail high）」を表示
    • 置換表による枝狩りが行われていない場合
      • α 値と β 値の初期値が更新される場合は赤字で「α 値または β 値の初期値の更新」を表示
  • 登録されていない場合
    • （※）黒字で「置換表に未登録」を表示
• "score" の状態
  • （※）数直線上にそのフレームでのノードの評価値を表示
  • （※）数直線上に子ノードの評価値を表示
  • そのフレームでの α 値と β 値
• "update" の状態
  • （※）数直線上にそのフレームでのノードの評価値を表示
  • ノードの評価値が更新された場合
    • （※）赤字で「評価値の更新」を表示
  • 更新されていない場合
    • （※）黒字で「評価値の更新なし」を表示
  • そのフレームでの α 値と β 値
  • α 狩りが行われた場合は赤字で「α 狩り」と表示
  • β 狩りが行われた場合は赤字で「β 狩り」と表示
• "end" の状態
  • （※）数直線上にそのフレームでのノードの評価値を表示
  • このノードの評価値の種類によってフレームの状態を以下のように表示する
    • fail low の場合は「評価値の確定（fail low）」を表示
    • exact value の場合は「評価値の確定（exact value）」を表示
    • fail high の場合は「評価値の確定（fail high）」を表示
  • 置換表を利用する場合
    • 置換表による枝狩りが行われた場合
      • （※）黒字で「置換表に登録されていたデータを利用」を表示
    • 置換表による枝狩りが行われていない場合
      • （※）赤字で「置換表への登録」を表示
      • 計算された範囲
      • 登録する範囲

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

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

キー	キーの値の意味
"alphaorig"	α 値の初期値
"betaorig"	β 値の初期値
"registered_in_tt"	（※）置換表にノードの評価値が登録されていたかどうか
"lower_bound"	（※）置換表の範囲の下界
"upper_bound"	（※）置換表の範囲の上界
"tt_pruned"	置換表による枝狩りが行われたかどうか
"ab_updated"	α 値または β 値の初期値が更新されたかどうか
"ab_pruned"	α 狩りまたは β 狩りが行われたかどうか
"score_type"	ノードの評価値の種類
"clower_bound"	計算された範囲の下界
"cupper_bound"	計算された範囲の上界
"tlower_bound"	登録する範囲の下界
"tupper_bound"	登録する範囲の上界

"start" 以外の状態で表示する内容の実装

"start" 以外 の状態では 置換表の範囲 を表示する必要がありますが、「置換表の範囲」は本記事独自の用語で意味を忘れた方が多いと思いますので先にその復習を行います。

3 種類のミニマックス値の範囲を表す用語

以前の記事で説明したように、本記事では 3 種類のミニマックス値の範囲 を 区別できるよう に、それぞれを以下の表のように短く表記することにします。

表記	意味	そのデータが記録されている dict のキー
置換表の範囲	置換表に登録されていたミニマックス値の範囲	lower_bound、upper_bound
計算された範囲	子ノードの評価値から計算されたミニマックス値の範囲	clower_bound、cupper_bound
登録する範囲	置換表に登録する、上記の 2 つの共通する範囲	ltower_bound、tupper_bound

ただし、置換表に ミニマックス値が登録されていない場合 は、置換表の範囲として 下界を負の無限大または評価値の最小値、上界を正の無限大または評価値の最大値 とします¹。

置換表の範囲の表示方法の検討

置換表の範囲をどのように表示すればよいかについて少し考えてみて下さい。

置換表の範囲 は下記の表の 2 通りの場合 があり、本記事ではそれぞれについて下記のような図形で表示することにします。また、下記とは別に 下界と上界の値 を 文字でも表示 することにします。

条件	表示方法
下界と上界が等しい場合	色のついた丸で表示する
下界と上界が等しくない場合	下界と上界を両端とする矢印で表示する

また、置換表 にそのノードのミニマックス値の範囲が 登録されていたか どうかを 区別できる ように、置換表に 登録されていた場合 は 図形を赤 で、登録されていない場合 は 黒で表示 し、そのことを 文字でも表示する ことにします。

置換表の範囲を表すの 図形の表示場所 としては、数直線上に表示するという方法も考えられますが、数直線上には α 値や β 値の初期値なども表示されるので、置換表の範囲を表す図形を 数直線上に表示するとわかりづらくなります。そこで、本記事では 数直線の下に表示 することにします。また、その 図形のすぐ上に下界と上界の値 を、すぐ右に置換表に登録されていたかどうか を表す文字を表示することにします。言葉で説明だけではわかりづらいと思いますので、下記に実際の表示の図を示します。置換表の表示範囲の表示方法を検討する際は、このような図をノートなどに書きながら行うと良いでしょう。

前回の記事でも説明しましたが、今回の記事で実装する視覚化の方法は筆者が思いついた方法に過ぎないので、もっと良い視覚化の方法を思いついた方はぜひ実装してみて下さい。

両端の矢印が付いた線の描画方法

matplotlib には、片方の端または、両方の端に 矢印が付いた線を描画する方法がいくつかあります。そのうちの 1 つは Axes の arrow というメソッドを利用するという方法です。ただし、arrow メソッド は下記の公式のドキュメントでうまく矢印が描画されない場合があるので 利用しないほうが良い（discouraged）と記述されている ので本記事では利用しません。

もう一つの方法はこれまでに注釈を表示する際に利用していた Axes の annotate メソッド を下記のように利用するという方法で、上記のドキュメントで紹介されていました。

• 注釈の文字列 に ""（空文字）を指定 して注釈の文字を描画しないようにする
• 矢印の 両端の座標 をキーワード引数 xy と xytext で指定 する
• 両端の矢印を描画 する場合はキーワード引数 arrowprops に { "arrowstyle": "<->" }` というキーの値を持つ dict を代入 する

なお、矢印の 線の色 はキーワード引数 arrowprops に代入する dict の color というキーの値で指定 することができます。

ミニマックス値の範囲は、置換表の範囲だけでなく 計算された範囲 や 登録する範囲 を "end" のフレームで表示 する必要があるので、下記のような ミニマックス値の範囲を描画 する update_frameinfo のローカル関数を定義 する事にします。

名前：範囲（bound）を描画（draw）するので draw_bound とする
処理：指定した範囲を表す図形を指定した色で描画する
入力：仮引数 lower に下界を、upper に上界を、y に図形を描画する y 座標を、color に図形の色を代入する
出力：なし

下記は draw_bound の定義です。

• 1 行目：上記の仮引数を持つ draw_bound を定義する
• 2、3 行目：下界と上界の x 座標をローカル関数 calc_coord を使って計算する
• 4、5 行目：下界と上界が等しい場合は指定した色で (下界の x 座標, y) の座標に color の色の丸（marker="o"）を描画する
• 6 ~ 8 行目：下界と上界が等しくない場合は annotate メソッドを利用して (下界の x 座標, y) と (上界の x 座標, y) を結ぶ両端に矢印が付いたcolor の色の線を描画する

1  def draw_bound(lower, upper, y, color):
2      lower_coord = calc_coord(lower)
3      upper_coord = calc_coord(upper)
4      if lower == upper:
5          self.abax.plot(lower_coord, y, color=color, marker="o")        
6      else:
7          self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
8                             arrowprops={ "arrowstyle": "<->", "color": color }) 

update_frameinfo の修正

下記は draw_bound を利用して 置換表の範囲を表示 するように update_frameinfo を修正したプログラムです。なお、図形やメッセージの描画位置 は前回の記事で説明したように筆者が 試行錯誤の結果決めた ものです。

• 15 ~ 22 行目：draw_bound をローカル関数として定義する
• 25 ~ 39 行目：αβ 法で計算されており "start" 以外のフレームで置換表の範囲を描画する
• 27、28 行目：置換表の範囲の下界と上界の値を変数に代入する
• 29 ~ 31 行目：置換表に登録されていた場合の図形の色を赤とし、真ん中の 7 行目を表す textlist[6] に置換表に登録されていたことを表す文字列を代入する
• 32 ~ 34 行目：置換表に登録されていない場合の図形の色を黒とし、真ん中の 7 行目を表す textlist[6] に置換表に登録されていないことを表す文字列を代入する
• 35 行目：draw_bound を呼び出して置換表の範囲の図形を描画する
• 36 ~ 39 行目：置換表の範囲の図形の左上に下界の値を、右上に上界の値を表示する

 1  from tree import Mbtree_Anim
 2  from marubatsu import Marubatsu
 3  import matplotlib.patches as patches
 4  
 5  def update_frameinfo(self):
元と同じなので省略
 6      # 置換表に登録したかどうかの表示
 7      elif status == "end":
 8          if self.mbtree.use_tt:
 9              if framedata["registered_in_tt"]:
10                  textlist[3] = "置換表に登録されていたデータを利用"
11              else:
12                  textlist[3] = "置換表への登録"
13                  textcolorlist[3] = "red"
14                  
15      def draw_bound(lower, upper, y, color):
16          lower_coord = calc_coord(lower)
17          upper_coord = calc_coord(upper)
18          if lower == upper:
19              self.abax.plot(lower_coord, y, color=color, marker="o")        
20          else:
21              self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
22                                 arrowprops={ "arrowstyle": "<->", "color": color })
23              
24      # ミニマックス値の範囲に関する表示
25      if not minimax:
26          if status != "start":
27              lower_bound = framedata["lower_bound"]
28              upper_bound = framedata["upper_bound"]
29              if framedata["registered_in_tt"]:
30                  color = "red"
31                  textlist[6] = "置換表のミニマックス値の範囲"
32              else:
33                  color = "black"
34                  textlist[6] = "ミニマックス値は置換表に未登録"
35              draw_bound(lower_bound, upper_bound, -2.3, color)
36              lower_text = f"下界 = {lower_bound}"
37              upper_text = f"上界 = {upper_bound}"
38              self.abax.text(leftx, -1.8, lower_text, ha="left")   
39              self.abax.text(rightx, -1.8, upper_text, ha="right")                   
40  
41      self.abfig.set_facecolor(facecolor)
42      for i in range(linenum):
43          self.abax.text(5, linetop - i * 0.7, textlist[i], c=textcolorlist[i])
元と同じなので省略
44           
45  Mbtree_Anim.update_frameinfo = update_frameinfo

行番号のないプログラム

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

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
    minimax = self.mbtree.minimax
    
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    if minimax:
        self.abax.set_ylim(-1.5, 1.5)
    else:
        self.abax.set_ylim(-4.3, 2.3)
    self.abax.axis("off")

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

    # 範囲の色分け
    if not minimax:
        alphaorig = framedata["alphaorig"]
        betaorig = framedata["betaorig"]
        alphaorig_coord = calc_coord(alphaorig)
        betaorig_coord = calc_coord(betaorig)
        color = "lightgray" if maxnode else "aqua"
        rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphaorig_coord-minus_inf,
                                 height=1, fc=color)
        self.abax.add_patch(rect)
        rect = patches.Rectangle(xy=(alphaorig_coord, -0.5), width=betaorig_coord-alphaorig_coord,
                                 height=1, fc="yellow")
        self.abax.add_patch(rect)
        color = "aqua" if maxnode else "lightgray"
        rect = patches.Rectangle(xy=(betaorig_coord, -0.5), width=plus_inf-betaorig_coord,
                                 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 = "" if self.mbtree.init_ab else "-∞"
        elif num == plus_inf:
            numtext = "" if self.mbtree.init_ab else "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

    # メッセージの表示
    if minimax:
        linenum = 4
        linetop = 1
    else:
        linenum = 9
        linetop = 1.7
    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 not minimax:
        if status == "start" or status == "tt":
            self.abax.plot(alphaorig_coord, 0, "or")
            self.abax.annotate(f"α = {alphaorig}", xy=(alphaorig_coord, 0),
                           xytext=(leftx, 1.7), arrowprops=arrowprops, ha="left")        
            self.abax.plot(betaorig_coord, 0, "ob")
            self.abax.annotate(f"β = {betaorig}", xy=(betaorig_coord, 0),
                           xytext=(rightx, 1.7), arrowprops=arrowprops, ha="right")        
        else:
            self.abax.text(leftx, 1.7, f"α = {alphaorig}", ha="left")   
            self.abax.text(rightx, 1.7, f"β = {betaorig}", ha="right")       
    # そのフレームでのノードの評価値の表示
    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"
                
    def draw_bound(lower, upper, y, color):
        lower_coord = calc_coord(lower)
        upper_coord = calc_coord(upper)
        if lower == upper:
            self.abax.plot(lower_coord, y, color=color, marker="o")        
        else:
            self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
                               arrowprops={ "arrowstyle": "<->", "color": color })
            
    # ミニマックス値の範囲に関する表示
    if not minimax:
        if status != "start":
            lower_bound = framedata["lower_bound"]
            upper_bound = framedata["upper_bound"]
            if framedata["registered_in_tt"]:
                color = "red"
                textlist[6] = "置換表のミニマックス値の範囲"
            else:
                color = "black"
                textlist[6] = "ミニマックス値は置換表に未登録"
            draw_bound(lower_bound, upper_bound, -2.3, color)
            lower_text = f"下界 = {lower_bound}"
            upper_text = f"上界 = {upper_bound}"
            self.abax.text(leftx, -1.8, lower_text, ha="left")   
            self.abax.text(rightx, -1.8, upper_text, ha="right")                   

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, linetop - 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, linetop - i * 0.7, textlist[i])
        self.abax.text(19.5, linetop - i * 0.7, datalist[i], ha="right")
        self.abax.text(22.5, linetop - i * 0.7, diff_datalist[i], ha="right")
        
    # 範囲の説明の表示
    if not minimax:
        facecolorlist = [
            "lightgray" if maxnode else "aqua", 
            "yellow",
            "aqua" if maxnode else "lightgray", 
        ]
        textlist = ["fail low", "exact value", "fail high"]
        textcolorlist = ["black", "black", "black"]
        for i in range(3):
            rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7), 
                                     width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
            self.abax.add_patch(rect)
            self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])  
         
Mbtree_Anim.update_frameinfo = update_frameinfo

修正箇所

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

def update_frameinfo(self):
元と同じなので省略
    # 置換表に登録したかどうかの表示
    elif status == "end":
        if self.mbtree.use_tt:
            if framedata["registered_in_tt"]:
                textlist[3] = "置換表に登録されていたデータを利用"
            else:
                textlist[3] = "置換表への登録"
                textcolorlist[3] = "red"
                
+   def draw_bound(lower, upper, y, color):
+       lower_coord = calc_coord(lower)
+       upper_coord = calc_coord(upper)
+       if lower == upper:
+           self.abax.plot(lower_coord, y, color=color, marker="o")        
+       else:
+           self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
+                              arrowprops={ "arrowstyle": "<->", "color": color })
            
    # ミニマックス値の範囲に関する表示
+   if not minimax:
+       if status != "start":
+           lower_bound = framedata["lower_bound"]
+           upper_bound = framedata["upper_bound"]
+           if framedata["registered_in_tt"]:
+               color = "red"
+               textlist[6] = "置換表のミニマックス値の範囲"
+           else:
+               color = "black"
+               textlist[6] = "ミニマックス値は置換表に未登録"
+           draw_bound(lower_bound, upper_bound, -2.3, color)
+           lower_text = f"下界 = {lower_bound}"
+           upper_text = f"上界 = {upper_bound}"
+           self.abax.text(leftx, -1.8, lower_text, ha="left")   
+           self.abax.text(rightx, -1.8, upper_text, ha="right")                   

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, linetop - i * 0.7, textlist[i], c=textcolorlist[i])
元と同じなので省略
         
Mbtree_Anim.update_frameinfo = update_frameinfo

表示の確認

上記の修正後に下記のプログラムを実行して下記の条件で計算したデータを Mbtree_Anim で表示すると、実行結果のように "start" のフレームでは置換表の範囲は表示されない ことが確認できます。余裕がある方は、他の条件でも確認してみて下さい。

• αβ 法で計算する
• 置換表を利用する
• 最短の勝利を目指す評価値を計算する
• ルートノードの α 値と β 値を評価値の最小値と最大値で初期化する

from tree import Mbtree

mbtree = Mbtree.load("../data/abtree_root")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, use_tt=True,
                           shortest_victory=True, init_ab=True)
Mbtree_Anim(mbtree, isscore=True)

実行結果

次に、置換表に ミニマックス値の範囲が 登録されていない場合の表示を確認 します。

当然ですが、ルートノード のミニマックス値の範囲は 置換表に登録されていません。従って、下段の > をクリックして表示される下図の ルートノードの "tt" のフレーム では、 置換表の範囲 が 評価値の最小値と最大値の範囲である -2 ~ 3 となります。そのことが図では下記のように描画されます。

• 数直線の下に -2 ~ 3 の範囲が 両端に矢印がついた線で描画 されている
• 置換表に登録されていなかった ので矢印が 黒色で描画 されている
• 矢印の右に「ミニマックス値は置換表に未登録」と表示されている

ルートノードの α 値と β 値を評価値の最小値と最大値で 初期化しない場合 は下記のプログラムの実行結果のように 置換表の範囲が負の無限大 ~ 正の無限大 のように正しく表示されます。

mbtree2 = Mbtree.load("../data/abtree_root")
mbtree2.calc_score_for_anim(mbtree.root, minimax=False, use_tt=True,
                            shortest_victory=True, init_ab=False)
Mbtree_Anim(mbtree2, isscore=True)

実行結果

下図は > をクリックして "score"、"update"、"end" のフレーム を表示した図です。いずれの場合でも 置換表の範囲が同様の方法で正しく表示される ことが確認できます。

次に、置換表に ミニマックス値の範囲が 登録されていた場合の表示を確認 します。

下図は赤枠の ルートノードの最初の子ノード の評価値が確定した "end" のフレームの図 です。ルートノードの最初の子ノードの ミニマックス値の範囲は置換表に登録されていない ので 評価値の範囲は上図と同じ内容が表示 されます。また、計算された評価値である 0 は exact value の範囲 なので 置換表には ミニマックス値の範囲として 下界と上界が 0 というデータが登録 されます。

下図は 上図の赤枠のノードの 局面を時計回りに 90 度回転させた 同一局面のノード が選択されたフレームの図なので、下図の赤枠のノードの局面の ミニマックス値の範囲 は 置換表に下界と上界が共に 0 として登録 されています。また、下図は "tt" のフレーム の図ではそのことが下記のように 正しく描画されています。

• 置換表の範囲の 下界と上界が等しい ので、数直線の下の 0 の位置に丸が描画 されている
• 置換表に登録されていた ので丸が 赤色で描画 されている
• 赤い丸の右に「置換表のミニマックス値の範囲」と表示されている

なお、上図で数直線の上に表示される「置換表の評価値＝０」と 矢印が重なって表示 されていますが、この表示はミニマックス法の場合で行う表示 なので、この後 の "tt" の状態で表示する内容の実装で 表示しないように修正します。

置換表の範囲 の 下界と上界が等しい ので置換表の範囲の下界（または上界）である 0 がこのノードの評価値として計算 されて 置換表による枝狩り が行われます。従って 下段の > をクリックして 次に表示 されるのは下図の "end" のフレーム で、置換表の範囲が上図と同様の方法で正しく表示 されます。

下図は 置換表に登録 されており、置換表の範囲の 下界と上界が等しくない場合 の 67 フレーム目の図で、そのことが図では下記のように正しく描画されています。

• 置換表の範囲の 下界と上界が等くない ので、数直線の下に 下界と上界の範囲を表す矢印が表示 されている
• 置換表に登録されていた ので矢印が 赤色で描画 されている
• 矢印の右に「置換表のミニマックス値の範囲」と表示されている

上図のフレームでは置換表の範囲が fail low または fail high に完全に含まれていないので置換表による枝狩りは行われません。図は省略しますが下段の > をクリックして "score"、"update"、"end" のフレームでも置換表の範囲が上図同様の方法で表示されることを確認して下さい。

置換表に登録されており、置換表の下界と上界が等しくない "tt" のフレームを Mbtree_Anim の > ボタンなどを使って探すのは大変 なので、上記の 67 フレーム目は、下記のプログラムを実行して求めました。

• 1 行目：組み込み関数 enumerate を利用してフレームの情報の一覧を表す list から順番にインデックスとフレームのデータを取り出すという繰り返し処理を行う
• 2 ~ 8 行目：状態が "tt"、置換表に登録されている、置換表の範囲の下界と上界が等しくないという 3 つの条件がすべて満たされている場合に 7 行目でインデックスを表示し、8 行目の break 文で繰り返し処理を終了する

1  for i, framedata in enumerate(mbtree.ablist_by_score):
2      if framedata["status"] == "tt":
3          registered_in_tt = framedata["registered_in_tt"]
4          lower_bound = framedata["lower_bound"]
5          upper_bound = framedata["upper_bound"]
6          if registered_in_tt and lower_bound != upper_bound:
7              print(i)
8              break

行番号のないプログラム

for i, framedata in enumerate(mbtree.ablist_by_score):
    if framedata["status"] == "tt":
        registered_in_tt = framedata["registered_in_tt"]
        lower_bound = framedata["lower_bound"]
        upper_bound = framedata["upper_bound"]
        if registered_in_tt and lower_bound != upper_bound:
            print(i)
            break

実行結果

67

"tt" の状態で表示する内容の実装

下記は "tt" の状態のフレーム で表示する内容の再掲です。（※）の部分は実装済なので、それ以外の場合の表示を実装する必要があります。

• 置換表にノードの評価値が登録されている場合
  • （※）赤字で「置換表に登録済」を表示
  • ミニマックス法で表示した置換表に登録されていた評価値は 表示しない
  • 置換表による枝狩りが行われている場合
    • $l=u$ の場合は赤字で「置換表による枝狩り（exact value）」を表示
    • $u≦α$ の場合は赤字で「置換表による枝狩り（fail low）」を表示
    • $β≦l$ の場合は赤字で「置換表による枝狩り（fail high）」を表示
  • 置換表による枝狩りが行われていない場合
    • α 値と β 値の初期値が更新される場合は赤字で「α 値または β 値の初期値の更新」を表示
• 登録されていない場合
  • （※）黒字で「置換表に未登録」を表示

上記に加えて 右下に表示する範囲の説明の表示 を以下のように修正することにします。

• 置換表による枝狩りが行われている場合 は、対応する範囲の文字を赤字で表示 する

どのように実装すればよいかについて少し考えてみて下さい。

update_frameinfo の修正

下記は上記を表示するように update_frameinfo を修正したプログラムです。

• 7 ~ 12 行目：ミニマックス法で計算されていた場合のみ 数直線上に置換表に 登録されていた評価値とその注釈を表示 するようにする
• 13 ~ 28 行目：αβ 法で計算されていた場合の表示を行う
• 14 ~ 24 行目：置換表による枝狩りが行われていた場合に pruned_type という変数に行なわれた 枝狩りの種類を表す文字列を計算 し、23 行目で真ん中の 5 行目に表示する文字列を計算し、24 行目でその文字列の色を赤色にする
• 25 ~ 28 行目：置換表に登録されていた場合で、置換表による枝狩りが行われず、α 値または β 値の初期値が更新されている場合 は真ん中の 5 行目に赤字で「α 値または β 値の初期値の更新」を表示するようにする
• 40 ~ 46 行目："tt" の状態で置換表による枝狩りが行われていた場合は、14 ~ 22 行目の処理で pruend_type という変数に枝狩りの種類を表す文字列が代入されているので、その値に応じて 対応する範囲の説明の文字を赤色にする

 1  def update_frameinfo(self):
元と同じなので省略
 2      # 置換表にデータが登録されていたかどうかの表示
 3      elif status =="tt":
 4          if framedata["registered_in_tt"]:
 5              textlist[3] = "置換表に登録済"
 6              textcolorlist[3] = "red"
 7              if minimax:
 8                  score = framedata["lower_bound"]
 9                  score_coord = calc_coord(score)
10                  self.abax.plot(score_coord, 0, "om")
11                  self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
12                                     xytext=(centerx, 1), arrowprops=arrowprops, ha="center")
13              else:
14                  if framedata["tt_pruned"]:
15                      lower_bound = framedata["lower_bound"]
16                      upper_bound = framedata["upper_bound"]
17                      if lower_bound == upper_bound:
18                          pruned_type = "exact value"
19                      elif upper_bound <= alphaorig:
20                          pruned_type = "fail low"
21                      elif betaorig <= lower_bound:
22                          pruned_type = "fail high"
23                      textlist[4] = f"置換表による枝狩り ({pruned_type})"
24                      textcolorlist[4] = "red"
25                  else:
26                      if framedata["ab_updated"]:
27                          textlist[4] = "α 値または β 値の初期値の更新"
28                          textcolorlist[4] = "red"            
29          else:
30              textlist[3] = "置換表に未登録"
元と同じなので省略
31      # 範囲の説明の表示
32      if not minimax:
33          facecolorlist = [
34              "lightgray" if maxnode else "aqua", 
35              "yellow",
36              "aqua" if maxnode else "lightgray", 
37          ]
38          textlist = ["fail low", "exact value", "fail high"]
39          textcolorlist = ["black", "black", "black"]
40          if status == "tt" and framedata["tt_pruned"]:
41              if pruned_type == "fail low":
42                  textcolorlist[0] = "red"
43              elif pruned_type == "exact value":
44                  textcolorlist[1] = "red"
45              elif pruned_type == "fail high":
46                  textcolorlist[2] = "red"
47          for i in range(3):
48              rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7), 
49                                       width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
50              self.abax.add_patch(rect)
51              self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])  
52           
53  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
    minimax = self.mbtree.minimax
    
    self.abax.clear()
    self.abax.set_xlim(-4, 23)
    if minimax:
        self.abax.set_ylim(-1.5, 1.5)
    else:
        self.abax.set_ylim(-4.3, 2.3)
    self.abax.axis("off")

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

    # 範囲の色分け
    if not minimax:
        alphaorig = framedata["alphaorig"]
        betaorig = framedata["betaorig"]
        alphaorig_coord = calc_coord(alphaorig)
        betaorig_coord = calc_coord(betaorig)
        color = "lightgray" if maxnode else "aqua"
        rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphaorig_coord-minus_inf,
                                 height=1, fc=color)
        self.abax.add_patch(rect)
        rect = patches.Rectangle(xy=(alphaorig_coord, -0.5), width=betaorig_coord-alphaorig_coord,
                                height=1, fc="yellow")
        self.abax.add_patch(rect)
        color = "aqua" if maxnode else "lightgray"
        rect = patches.Rectangle(xy=(betaorig_coord, -0.5), width=plus_inf-betaorig_coord,
                                 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 = "" if self.mbtree.init_ab else "-∞"
        elif num == plus_inf:
            numtext = "" if self.mbtree.init_ab else "∞"
        else:
            numtext = num
        self.abax.text(num, -1, numtext, ha="center")        

    # メッセージの表示
    if minimax:
        linenum = 4
        linetop = 1
    else:
        linenum = 9
        linetop = 1.7
    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 not minimax:
        if status == "start" or status == "tt":
            self.abax.plot(alphaorig_coord, 0, "or")
            self.abax.annotate(f"α = {alphaorig}", xy=(alphaorig_coord, 0),
                               xytext=(leftx, 1.7), arrowprops=arrowprops, ha="left")        
            self.abax.plot(betaorig_coord, 0, "ob")
            self.abax.annotate(f"β = {betaorig}", xy=(betaorig_coord, 0),
                               xytext=(rightx, 1.7), arrowprops=arrowprops, ha="right")        
        else:
            self.abax.text(leftx, 1.7, f"α = {alphaorig}", ha="left")   
            self.abax.text(rightx, 1.7, f"β = {betaorig}", ha="right")       
    # そのフレームでのノードの評価値の表示
    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"
            if minimax:
                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:
                if framedata["tt_pruned"]:
                    lower_bound = framedata["lower_bound"]
                    upper_bound = framedata["upper_bound"]
                    if lower_bound == upper_bound:
                        pruned_type = "exact value"
                    elif upper_bound <= alphaorig:
                        pruned_type = "fail low"
                    elif betaorig <= lower_bound:
                        pruned_type = "fail high"
                    textlist[4] = f"置換表による枝狩り ({pruned_type})"
                    textcolorlist[4] = "red"
                else:
                    if framedata["ab_updated"]:
                        textlist[4] = "α 値または β 値の初期値の更新"
                        textcolorlist[4] = "red"            
        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"
                
    def draw_bound(lower, upper, y, color):
        lower_coord = calc_coord(lower)
        upper_coord = calc_coord(upper)
        if lower == upper:
            self.abax.plot(lower_coord, y, color=color, marker="o")        
        else:
            self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
                               arrowprops={ "arrowstyle": "<->", "color": color })
            
    # 下界と上界に関する表示
    if not minimax:
        lower_text = ""
        upper_text = ""
        if status != "start":
            lower_bound = framedata["lower_bound"]
            upper_bound = framedata["upper_bound"]
            if framedata["registered_in_tt"]:
                color = "red"
                textlist[6] = "置換表のミニマックス値の範囲"
            else:
                color = "black"
                textlist[6] = "ミニマックス値は置換表に未登録"
            draw_bound(lower_bound, upper_bound, -2.3, color)
            lower_text = f"下界 = {lower_bound}"
            upper_text = f"上界 = {upper_bound}"
            self.abax.text(leftx, -1.8, lower_text, ha="left")   
            self.abax.text(rightx, -1.8, upper_text, ha="right")                   

    self.abfig.set_facecolor(facecolor)
    for i in range(linenum):
        self.abax.text(5, linetop - 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, linetop - i * 0.7, textlist[i])
        self.abax.text(19.5, linetop - i * 0.7, datalist[i], ha="right")
        self.abax.text(22.5, linetop - i * 0.7, diff_datalist[i], ha="right")
        
    # 範囲の説明の表示
    if not minimax:
        facecolorlist = [
            "lightgray" if maxnode else "aqua", 
            "yellow",
            "aqua" if maxnode else "lightgray", 
        ]
        textlist = ["fail low", "exact value", "fail high"]
        textcolorlist = ["black", "black", "black"]
        if status == "tt" and framedata["tt_pruned"]:
            if pruned_type == "fail low":
                textcolorlist[0] = "red"
            elif pruned_type == "exact value":
                textcolorlist[1] = "red"
            elif pruned_type == "fail high":
                textcolorlist[2] = "red"
        for i in range(3):
            rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7), 
                                     width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
            self.abax.add_patch(rect)
            self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])  
         
Mbtree_Anim.update_frameinfo = update_frameinfo

修正箇所

def update_frameinfo(self):
元と同じなので省略
    # 置換表にデータが登録されていたかどうかの表示
    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")
+           if minimax:
+               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:
+               if framedata["tt_pruned"]:
+                   lower_bound = framedata["lower_bound"]
+                   upper_bound = framedata["upper_bound"]
+                   if lower_bound == upper_bound:
+                       pruned_type = "exact value"
+                   elif upper_bound <= alphaorig:
+                       pruned_type = "fail low"
+                   elif betaorig <= lower_bound:
+                       pruned_type = "fail high"
+                   textlist[4] = f"置換表による枝狩り ({pruned_type})"
+                   textcolorlist[4] = "red"
+               else:
+                   if framedata["ab_updated"]:
+                       textlist[4] = "α 値または β 値の初期値の更新"
+                       textcolorlist[4] = "red"            
        else:
            textlist[3] = "置換表に未登録"
元と同じなので省略
    # 範囲の説明の表示
    if not minimax:
        facecolorlist = [
            "lightgray" if maxnode else "aqua", 
            "yellow",
            "aqua" if maxnode else "lightgray", 
        ]
        textlist = ["fail low", "exact value", "fail high"]
        textcolorlist = ["black", "black", "black"]
+       if status == "tt" and framedata["tt_pruned"]:
+           if pruned_type == "fail low":
+               textcolorlist[0] = "red"
+           elif pruned_type == "exact value":
+               textcolorlist[1] = "red"
+           elif pruned_type == "fail high":
+                textcolorlist[2] = "red"
        for i in range(3):
            rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7), 
                                     width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
            self.abax.add_patch(rect)
            self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])  
         
Mbtree_Anim.update_frameinfo = update_frameinfo

表示の確認方法

上記の修正後に下記のプログラムを実行して正しく表示されることを確認します。

Mbtree_Anim(mbtree, isscore=True)

下記のそれぞれの場合について表示を確認することにします。

• 置換表に登録されていない場合（条件 1）
• 置換表に登録されている場合
  • 置換表による枝狩りが行われる場合
    • 置換表の範囲が exact value である²（条件 2）
    • 置換表の範囲が fail low に完全に含まれる（条件 3）
    • 置換表の範囲が fail high に完全に含まれる（条件 4）
  • 置換表による枝狩りが行われない場合
    • α 値または β 値の 初期値が更新される（条件 5）
    • α 値または β 値の 初期値が更新されない（条件 6）

条件 1 の表示の確認

下図は ルートノードの "tt" の状態のフレーム で、修正前と同じ表示が行われるので 条件 1 の置換表に登録されていない場合 に 正しく表示されることが確認 できます。

条件 2 ~ 6 を満たすフレームを探すプログラムの作成

上記の条件 2 から 6 を満たす "tt" のフレームを 手動で探すのは困難 なので、下記のような 関数を定義 することにします。

名前：条件にあった "tt" のフレームを探すので search_tt_frame とする
処理：指定した番号の条件を満たす最初のフレームの番号を計算して返す
入力：仮引数 type に条件の番号を代入する
出力：指定した番号の条件を満たす最初のフレームの番号を返り値として返す

下記は search_frame の定義です。なお、この関数は 今後の記事で利用することはない ので ai.py などの ファイルには保存しない ことにします。

• 2 行目：組み込み関数 enumerate を利用してフレームの情報の一覧を表す list から順番にインデックスとフレームのデータを取り出すという繰り返し処理を行う
• 3 ~ 25 行目：type のそれぞれの条件を満たす場合にフレームの番号を返す処理を行う

 1  def search_tt_frame(type):
 2      for i, framedata in enumerate(mbtree.ablist_by_score):
 3          if framedata["status"] == "tt":
 4              if framedata["registered_in_tt"]:
 5                  if framedata["tt_pruned"]:
 6                      lower_bound = framedata["lower_bound"]
 7                      upper_bound = framedata["upper_bound"]
 8                      alphaorig = framedata["alphaorig"]
 9                      betaorig = framedata["betaorig"]
10                      if lower_bound == upper_bound:
11                          if type == 2:
12                              return i
13                      elif upper_bound <= alphaorig:
14                          if type == 3:
15                              return i
16                      elif betaorig <= lower_bound:
17                          if type == 4:
18                              return i
19                  else:
20                      if framedata["ab_updated"]:
21                          if type == 5:
22                              return i
23                      else:
24                          if type == 6:
25                              return i

行番号のないプログラム

def search_tt_frame(type):
    for i, framedata in enumerate(mbtree.ablist_by_score):
        if framedata["status"] == "tt":
            if framedata["registered_in_tt"]:
                if framedata["tt_pruned"]:
                    lower_bound = framedata["lower_bound"]
                    upper_bound = framedata["upper_bound"]
                    alphaorig = framedata["alphaorig"]
                    betaorig = framedata["betaorig"]
                    if lower_bound == upper_bound:
                        if type == 2:
                            return i
                    elif upper_bound <= alphaorig:
                        if type == 3:
                            return i
                    elif betaorig <= lower_bound:
                        if type == 4:
                            return i
                else:
                    if framedata["ab_updated"]:
                        if type == 5:
                            return i
                    else:
                        if type == 6:
                            return i

条件 2 の表示の確認

下記のプログラムを実行して 条件 2 を満たすフレームを計算 すると、実行結果から 99 フレーム目が計算 されます。

print(search_tt_frame(2))

実行結果

99

下図は 99 フレーム目の図で、下記のように 正しく描画されていることが確認 できます。

• 数直線上に置換表の評価値とその注釈が表示されなくなっている
• 真ん中の 5 行目に赤字で「置換表による枝狩り（exact value）」が表示されている
• 右下の範囲の説明の exact value が赤字で表示されている

条件 3 の表示の確認

下記のプログラムを実行して 条件 3 を満たすフレームを計算 すると、実行結果から 191 フレーム目が計算 されます。

print(search_tt_frame(3))

実行結果

191

下図は 191 フレーム目の図で、下記のように 正しく描画されていることが確認 できます。

• ミニマックス法の場合と異なり、数直線に置換表の評価値が表示されなくなっている
• 真ん中の 5 行目に赤字で「置換表による枝狩り（fail low）」が表示されている
• 右下の範囲の説明の fail low が赤字で表示されている

条件 4 の表示の確認

下記のプログラムを実行して 条件 4 を満たすフレームを計算 すると、実行結果から 132 フレーム目が計算 されます。

print(search_tt_frame(4))

実行結果

132

下図は 132 フレーム目の図で、下記のように 正しく描画されていることが確認 できます。

• ミニマックス法の場合と異なり、数直線に置換表の評価値が表示されなくなっている
• 真ん中の 5 行目に赤字で「置換表による枝狩り（fail high）」が表示されている
• 右下の範囲の説明の fail high が赤字で表示されている

条件 5 の表示の確認

下記のプログラムを実行して 条件 5 を満たすフレームを計算 すると、実行結果から 67 フレーム目が計算 されます。

print(search_tt_frame(5))

実行結果

67

下図は 67 フレーム目の図で、下記の点では 正しく描画されていることが確認 できます。

• ミニマックス法の場合と異なり、数直線に置換表の評価値が表示されなくなっている
• 真ん中の 5 行目に赤字で「α 値または β 値の初期値の更新」が表示されている
• 右下の範囲の説明はすべて黒字で表示されている

見逃してしまう方が多いのではないかと思いますが、上図には　α 値または β 値の初期値の更新に関係 する おかしな点があります。どのような問題があるかについて少し考えてみて下さい。なお、おかしな点については先に条件 6 の表示の確認を行ってから説明します。

条件 6 の表示の確認

下記のプログラムを実行して 条件 6 を満たすフレームを計算 すると、実行結果から 276 フレーム目が計算 されます。

print(search_tt_frame(6))

実行結果

276

下図は 276 フレーム目の図で、下記のように 正しく描画されていることが確認 できます。

• ミニマックス法の場合と異なり、数直線に置換表の評価値が表示されなくなっている
• 真ん中の 5 行目に何も表示されない
• 右下の範囲の説明はすべて黒字で表示されている

ここまでの確認作業で、条件 5 以外では正しく描画される ことが確認できました。

条件 5 の表示の問題点

下図は下記の条件 5 を満たす先程の "tt" のフレームの図の再掲です。

• 置換表に登録されている
• 置換表による枝狩りが行われない
• α 値または β 値の初期値が更新される

以前の記事で説明したように、条件 5 で行われる α 値または β 値の初期値の更新 は、α 値と β 値の初期値の範囲を 置換表の範囲外の値が含まれない ように 範囲を狭める方向で更新する ことで、枝狩りの効率を上げる という目的で行います。

しかし、上図では黄色で塗りつぶされた α 値と β 値の初期値の範囲 のうち 1 ~ 2 の範囲 が、赤い矢印の置換表の範囲外 になっているという問題があります。

実はこのようなことが起きる原因は今回の記事で記述した update_frameinfo にはありません。問題の原因は 筆者がうっかり calc_score_for_anim で α 値と β 値の初期値を更新する処理を間違えて記述 してしまったからです。

記事が長くなったので間違いの修正は次回の記事で行うことにします。また、残りの状態の表示の実装も次回の記事で行います。余裕がある方は筆者がどのようなうっかりミスをしたかを探してみて下さい。

今回の記事のまとめ

今回の記事では、αβ 法の視覚化 のための Mbtree_Anim の修正 のうち、"start" 以外の状態で表示する内容 の実装と、"tt" の状態で表示する内容 の実装を行いました。ただし、現時点では "tt" の状態で表示する内容の一部にバグが存在します。

次回の記事ではバグの修正と残りの表示の実装を行います。

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

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

次回の記事

1. どちらになるかは、ルートノードの α 値と β 値の初期値を、評価値の最小値と最大値に設定するかどうかで決まります ↩

2. ミニマックス値の範囲の下界と上界が等しい場合も含みます ↩