Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ysgeso

Pythonで〇×ゲームのAIを一から作成する　その141　αβ 法の視覚化の改良

Posted at

目次と前回の記事

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

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

リンク 説明
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 クラスの calc_score_by_ab メソッドの修正

Mbtree クラスの calc_score_by_ab では、αβ 法で評価値を計算する際に nodelist_by_score という属性にアニメーションの 各フレーム で処理が行われる ノードのデータを list の形式で保存 しました。同様に、ablist_by_score という属性に 各フレーム での α 値と β 値 を表す (α 値, β 値) という tuple を要素として持つ list を代入して記録することにします。

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

  • 9、32 行目：nodelist_by_score に node を追加した後で、ablist_by_score の要素に (α 値, β 値) を表す tuple を追加する
  • 14、17 行目：11 行目で nodelist_by_score に node を追加した場合は その後の処理で alpha の値を更新する が、β 狩りを行う場合と行わない場合のそれぞれに対して alpha の値の更新方法が異なる ので、それぞれの場合で alpha の更新後 に ablist_by_score の要素に (α 値, β 値) を表す tuple を追加する必要がある 点に注意すること
  • 25、28 行目：min node の処理を行う場合に 14、17 行目 と同様の処理を行う
  • 34 行目：nodelist_by_score を空の list で初期化した後で、ablist_by_score を空の list で初期化する
 1  from marubatsu import Marubatsu
 2  from tree import Mbtree
 3
 4  def calc_score_by_ab(self, abroot, debug=False):           
 5      self.count = 0
 6     
 7      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
 8          self.nodelist_by_score.append(node)
 9          self.ablist_by_score.append((alpha, beta))
元と同じなので省略
10                      score = calc_ab_score(childnode, alpha, beta)
11                      self.nodelist_by_score.append(node)
12                      if score >= beta:
13                          alpha = score
14                          self.ablist_by_score.append((alpha, beta))
15                          break
16                      alpha = max(alpha, score)
17                      self.ablist_by_score.append((alpha, beta))
18                  node.score = alpha
19              else:
20                  for childnode in node.children:
21                      score = calc_ab_score(childnode, alpha, beta)
22                      self.nodelist_by_score.append(node)
23                      if score <= alpha:
24                          beta = score
25                          self.ablist_by_score.append((alpha, beta))
26                          break
27                      beta = min(beta, score)
28                      self.ablist_by_score.append((alpha, beta))
29                  node.score = beta
30
31          self.nodelist_by_score.append(node)
32          self.ablist_by_score.append((alpha, beta))
元と同じなので省略        
33      self.nodelist_by_score = []
34      self.ablist_by_score = []
35      calc_ab_score(abroot)
36      dprint(debug, "count =", self.count) 
37    
38  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 calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta))
        self.count += 1
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
        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)
                    if score >= beta:
                        alpha = score
                        self.ablist_by_score.append((alpha, beta))
                        break
                    alpha = max(alpha, score)
                    self.ablist_by_score.append((alpha, beta))
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    self.nodelist_by_score.append(node)
                    if score <= alpha:
                        beta = score
                        self.ablist_by_score.append((alpha, beta))
                        break
                    beta = min(beta, score)
                    self.ablist_by_score.append((alpha, beta))
                node.score = beta

        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta))
        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
修正箇所 
from marubatsu import Marubatsu
from tree import Mbtree

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))
元と同じなので省略
                    score = calc_ab_score(childnode, alpha, beta)
                    self.nodelist_by_score.append(node)
                    if score >= beta:
                        alpha = score
+                       self.ablist_by_score.append((alpha, beta))
                        break
                    alpha = max(alpha, score)
+                   self.ablist_by_score.append((alpha, beta))
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    self.nodelist_by_score.append(node)
                    if score <= alpha:
                        beta = score
+                       self.ablist_by_score.append((alpha, beta))
                        break
                    beta = min(beta, score)
+                   self.ablist_by_score.append((alpha, beta))
                node.score = beta

        self.nodelist_by_score.append(node)
+       self.ablist_by_score.append((alpha, beta))
元と同じなので省略        
    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

nodelist_by_score の要素を (ノード, α 値, β 値) に修正 することで ablist_by_score を追加せず にプログラムを修正することもできますが、そのようにした場合は、α 値や β 値を計算しない calc_score_by_bf や calc_score_by_df 内で nodelist_by_score に (node, None, None) のような tuple を代入するように修正する必要が生じるため本記事では採用しませんでした。

Mbtree_Anim クラスの __init__ メソッドの修正

次に、α 値と β 値 を Mbtree_Anim で どこに表示するか を決める必要があります。本記事では、Mbtree_Anim で表示する Figure の縦幅を 1 増やし て、Figure の 最上部に α 値と β 値を表示 することにします。別の場所に表示したい人は自由に表示場所を変更して下しさい。

まず、下記のプログラムの 5 行目のように、__init__ メソッドの中で Mbtree_Anim で作成する Figure の縦幅 を表す height 属性の値を 65 から 66 に 1 増やします。

1  from tree import Mbtree_Anim
2
3  def __init__(self, mbtree, isscore=False, size=0.15):
元と同じなので省略
4      self.width = 50
5      self.height = 66
元と同じなので省略
6
7  Mbtree_Anim .__init__ = __init__
行番号のないプログラム 
from tree import Mbtree_Anim

def __init__(self, mbtree, isscore=False, size=0.15):
    self.mbtree = mbtree
    self.isscore = isscore
    self.size = size
    self.width = 50
    self.height = 66
    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__
修正箇所 
from tree import Mbtree_Anim

def __init__(self, mbtree, isscore=False, size=0.15):
元と同じなので省略
    self.width = 50
-   self.height = 65
+   self.height = 66
元と同じなので省略

Mbtree_Anim .__init__ = __init__

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

α 値と β 値の表示 を行う必要があるのは、Mbtree_Anim で 評価値の計算の手順を表示する際だけ なので、Mbtree クラスの draw_subtree メソッドではなく、Mbtree_Anim クラスの update_gui メソッドを下記のプログラムのように修正することにします。

  • 4 行目：上部に α 値と β 値 を表示できるように、Axes の表示範囲 の 上端の y 座標 を -1 から -2 に変更 する。それにあわせて表示範囲の 下端の y 座標も 1 減らす 必要がある
  • 8 行目：α 値と β 値を表示するのは、評価値の計算手順を表示する「isscore 属性が True」で、なおかつ「mbtree が α 値と β 値を 記録した ablist_by_score 属性を持つ」場合なので、そのことを判定する。オブジェクトが属性を持つかどうかの判定は、以前の記事で説明した組み込み関数 hasattr を利用して行うことができる
  • 9 ~ 12 行目：ablist_by_score から表示するのフレームの α 値と β 値を取り出し、Figure の上部に表示する。文字の大きさは、Mbtree クラスの draw_subtree での文字の表示と同じ大きさに設定した。それぞれの表示位置は筆者が試行錯誤して決めた値なので、別の場所に表示したい場合は自由に変更すること
 1  def update_gui(self):
 2      self.ax.clear()
 3      self.ax.set_xlim(-1, self.width - 1)
 4      self.ax.set_ylim(-2, self.height - 2)   
元と同じなので省略
 5      self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode,
 6                               anim_frame=self.play.value, isscore=self.isscore, 
 7                               ax=self.ax, maxdepth=maxdepth, size=self.size)
 8      if self.isscore and hasattr(self.mbtree, "ablist_by_score"):
 9          fontsize = 70 * self.size
10          alpha, beta = self.mbtree.ablist_by_score[self.play.value]
11          self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize)        
12          self.ax.text(10, -1, f"β: {beta}", fontsize=fontsize)        
13    
14  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.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.isscore and hasattr(self.mbtree, "ablist_by_score"):
        fontsize = 70 * self.size
        alpha, beta = self.mbtree.ablist_by_score[self.play.value]
        self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize)        
        self.ax.text(10, -1, f"β: {beta}", fontsize=fontsize)        
                            
    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(-1, self.height - 1)   
+   self.ax.set_ylim(-2, self.height - 2)   
元と同じなので省略
    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.isscore and hasattr(self.mbtree, "ablist_by_score"):
+       fontsize = 70 * self.size
+       alpha, beta = self.mbtree.ablist_by_score[self.play.value]
+       self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize)        
+       self.ax.text(10, -1, f"β: {beta}", fontsize=fontsize)        
    
Mbtree_Anim.update_gui = update_gui

上記の修正後に下記のプログラムで Mbtree クラスのインスタンスを作成し、Mbtree_Anim で表示を行うと、Mbtree クラスのインスタンスを作成した際には ablist_by_score を計算しない ので実行結果のように上部に α 値も β 値も 表示されません。

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

実行結果

その後で下記のプログラムで calc_score_by_ab を呼び出して αβ 法での評価値の計算を行ったデータに対して Mbtree_Anim を実行すると、実行結果のように 上部に α 値と β 値が表示される ことが確認できます。

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

実行結果

ノードの手番の明確化

現状では、表示されたゲーム木の ノードが 〇 の手番の max ノードであるか、× の手番の min ノードであるか が わかりづらい という問題があります。そこで、× の手番の min ノード周辺の背景色を薄い灰色で表示 して 区別できるようにする ことにします。

その表示は Mbtree_Anim でゲーム木を表示する場合だけでなく、部分木を表示する場合は常に行ったほうがわかりやすい と思いましたので、部分木を表示する Mbtree クラスの draw_subtree メソッドを修正 することにします。

× の手番の min ノード周辺の背景色を薄い灰色で表示するためには、その 表示範囲を決める 必要があります。どのような表示範囲にすればよいかについて少し考えてみて下さい。

本記事では、× の手番の min ノードを表示する周辺の背景色 を 下図のよう に縦に細長い薄い灰色で表示することにします。下図のような薄い灰色は 長方形の図形で表示 できます。

上図の薄い灰色の長方形の x 座標の範囲 は、min ノードの局面の x 座標の範囲を 少し広くしたもの です。深さ depth の局面の x 座標の表示範囲 は depth * 5 ~ depth * 5 + 3 なので、その範囲の左右を 1 ずつ広げた depth * 5 - 1 ~ depth * 5 + 4 を薄い灰色の長方形の x 座標の範囲とすることにします。

薄い灰色の長方形の y 座標の範囲 については、Axes の範囲と同じにする という方法が考えられます。下図はそのように表示した場合の図です。下図では問題はありませんが、今後 別のメッセージを表示 しようとした際に、メッセージが薄い灰色の長方形の上にが 重なって表示 されてしまい、少し 見づらくなってしまう という問題が発生することが考えられます。

そこで、y 座標の範囲を α 値と β 値の表示を含まない、-1 ~ Axes の下端の座標 とすることにします。下図はそのように表示した場合の図です。上図と見比べてみて下さい。

Axes の y 座標の表示範囲 は、Axes の get_ylim というメソッドで得ることができ、その返り値は (下端の y 座標, 上端 の y 座標) という tuple になります。

get_ylim の詳細については、下記のリンク先を参照して下さい。

下記は、上図のような灰色の長方形を表示するように draw_subtree を修正したプログラムです。draw_subtree では下記のプログラムの 5 ~ 10 行目で Figure と Axes を作成する場合がある ので、その後 で薄い灰色の長方形を表示する 処理を記述 する必要があります。

  • 12 行目：get_ylim で Axes の下端と上端の y 座標を計算する
  • 13 行目：薄い灰色の長方形の上端の座標を -1 とする
  • 14 行目：x の手番の min ノードの深さは奇数なので、for 文と range(1, 10, 2) によって奇数の深さの繰り返し処理を行う
  • 15、16 行目：深さ depth の min ノードに対する灰色の長方形を表示する。長方形の幅は 5、高さは bottom - height で計算できる。なお、whitesmoke は、lightgray よりも薄い灰色を表す色の文字列である
 1  import matplotlib.patches as patches
 2
 3  def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
 4                   isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略 
 5  if ax is None:
 6      fig, ax = plt.subplots(figsize=(width * size, (height + 1) * size))
 7      ax.set_xlim(0, width)
 8      ax.set_ylim(-1, height)   
 9      ax.invert_yaxis()
10      ax.axis("off") 
11        
12      bottom, top = ax.get_ylim()
13      top = -1
14      for depth in range(1, 10, 2):
15          ax.add_artist(patches.Rectangle(xy=(depth * 5 - 1, top), width=5,
16                                          height=bottom - top, fc="whitesmoke"))            
元と同じなので省略
17            
18  Mbtree.draw_subtree = draw_subtree
行番号のないプログラム 
import matplotlib.patches as patches

def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
                    isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
    
    def calc_darkness(node):
        if show_bestmove:
            if node.parent is None:
                return 0, show_score
            elif node.mb.last_move in node.parent.bestmoves:
                return 0, show_score
            else:
                return 0.2, show_score
            
        if anim_frame is None:
            return 0, show_score
        index = node.score_index if isscore else node.id
        return (0.5, False) if index > anim_frame else (0, isscore)
    
    self.nodes_by_rect = {}

    if centernode is None:
        centernode = self.root
    self.calc_node_height(N=centernode, maxdepth=maxdepth)
    if show_bestmove:
        width = 5 * 10
    else:
        width = 5 * (maxdepth + 1)
    height = centernode.height
    parent = centernode.parent
    if parent is not None:
        height += (len(parent.children) - 1) * 4
        parent.height = height
    if ax is None:
        fig, ax = plt.subplots(figsize=(width * size, (height + 1) * size))
        ax.set_xlim(0, width)
        ax.set_ylim(-1, height)   
        ax.invert_yaxis()
        ax.axis("off")        
    
    bottom, top = ax.get_ylim()
    top = -1
    for depth in range(1, 10, 2):
        ax.add_artist(patches.Rectangle(xy=(depth * 5 - 1, top), width=5,
                                        height=bottom - top, fc="whitesmoke"))               

    if show_bestmove:
        bestx = 5 * maxdepth + 4
        bestwidth = 50 - bestx
        ax.add_artist(patches.Rectangle(xy=(bestx, -1), width=bestwidth,
                                        height=height + 1, fc="lightgray"))
    
    nodelist = [centernode]
    depth = centernode.depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        if parent is not None:
            dy = parent.children.index(centernode) * 4
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
                childnodelist.append(None)
            else:
                dx = 5 * node.depth
                emphasize = node is selectednode
                darkness, show_score = calc_darkness(node)
                rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, darkness=darkness,
                                    show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = node
                if show_bestmove and depth == maxdepth:
                    bestnode = node
                    while len(bestnode.bestmoves) > 0:
                        bestmove = bestnode.bestmoves[0]
                        bestnode = bestnode.children_by_move[bestmove]
                        dx = 5 * bestnode.depth
                        bestnode.height = 4
                        emphasize = bestnode is selectednode
                        rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth, emphasize=emphasize,
                                                show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
                        self.nodes_by_rect[rect] = bestnode                                          
                    
                dy += node.height
                if len(node.children) > 0:  
                    childnodelist += node.children
                else:
                    childnodelist.append(None)
        depth += 1
        nodelist = childnodelist
        
    if parent is not None:
        dy = 0
        for sibling in parent.children:
            if sibling is not centernode:
                sibling.height = 4
                dx = 5 * sibling.depth
                darkness, show_score  = calc_darkness(sibling)
                rect = sibling.draw_node(ax, maxdepth=sibling.depth, size=size, darkness=darkness,
                                        show_score=show_score, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = sibling
            dy += sibling.height
        dx = 5 * parent.depth
        darkness, show_score  = calc_darkness(parent)
        rect = parent.draw_node(ax, maxdepth=maxdepth, darkness=darkness, 
                                show_score=show_score, size=size, lw=lw, dx=dx, dy=0)
        self.nodes_by_rect[rect] = parent
    
        node = parent
        while node.parent is not None:
            node = node.parent
            node.height = height
            dx = 5 * node.depth
            darkness, show_score  = calc_darkness(node)
            rect = node.draw_node(ax, maxdepth=node.depth, darkness=darkness,
                                show_score=show_score, size=size, lw=lw, dx=dx, dy=0)
            self.nodes_by_rect[rect] = node
            
Mbtree.draw_subtree = draw_subtree
修正箇所 
import matplotlib.patches as patches

def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
                 isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略 
    if ax is None:
        fig, ax = plt.subplots(figsize=(width * size, (height + 1) * size))
        ax.set_xlim(0, width)
        ax.set_ylim(-1, height)   
        ax.invert_yaxis()
        ax.axis("off")  
        
+   bottom, top = ax.get_ylim()
+   top = -1
+   for depth in range(1, 10, 2):
+       ax.add_artist(patches.Rectangle(xy=(depth * 5 - 1, top), width=5,
+                                       height=bottom - top, fc="whitesmoke"))                 
元と同じなので省略
            
Mbtree.draw_subtree = draw_subtree

上記の修正後に下記のプログラムを実行すると、実行結果（先ほどと同じ 7 フレーム目の図です）のように α 値と β 値の行の部分に重ならない範囲 で min ノードの周囲の背景色が薄い灰色で表示されるようになることが確認できます。

Mbtree_Anim(mbtree, isscore=True)

実行結果

α 値 と β 値の表示に関する改良

現状では α 値 と β 値が表示されるだけで、それらが どのように計算されているかがわかりづらい ので、α 値 と β 値に関する表示を改良することにします。どのように改良すればよいかについて少し考えてみて下さい。

計算中の α 値 と β 値の明確化

αβ 法では、max ノード の子ノードの評価値によって α 値 が、min ノード の子ノードの評価値によって β 値 が 計算 されます。そこで、赤枠の選択中のノード の子ノードの評価値によって 計算する α 値または β 値 を 赤色で表示 することにします。

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

  • 4、5 行目：α 値と β 値の文字の色を、選択中のノードの手番によって計算する
  • 7、8 行目：4、5 行目で計算した色で α 値と β 値 を表示するように修正する
 1  def update_gui(self):
元と同じなので省略
 2      if self.isscore and hasattr(self.mbtree, "ablist_by_score"):
 3          fontsize = 70 * self.size
 4          acolor = "red" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "black"
 5          bcolor = "black" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "red"
 6          alpha, beta = self.mbtree.ablist_by_score[self.play.value]
 7          self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
 8          self.ax.text(10, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
元と同じなので省略 
 9
10  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.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.isscore and hasattr(self.mbtree, "ablist_by_score"):
        fontsize = 70 * self.size
        acolor = "red" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "black"
        bcolor = "black" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "red"
        alpha, beta = self.mbtree.ablist_by_score[self.play.value]
        self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
        self.ax.text(10, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
                            
    disabled = self.play.value == 0
    self.set_button_status(self.prev_button, disabled=disabled)
    disabled = self.play.value == self.nodenum - 1
    self.set_button_status(self.next_button, disabled=disabled)
    
Mbtree_Anim.update_gui = update_gui
修正箇所 
def update_gui(self):
元と同じなので省略
    if self.isscore and hasattr(self.mbtree, "ablist_by_score"):
        fontsize = 70 * self.size
+       acolor = "red" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "black"
+       bcolor = "black" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "red"
        alpha, beta = self.mbtree.ablist_by_score[self.play.value]
-       self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize)       
+       self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
-       self.ax.text(10, -1, f"β: {beta}", fontsize=fontsize)
+       self.ax.text(10, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)
元と同じなので省略 

Mbtree_Anim.update_gui = update_gui

上記の修正後に下記のプログラムを実行すると、実行結果のように α 値と β 値の文字が選択中のノードの種類によって色が変化することが確認できます。

Mbtree_Anim(mbtree, isscore=True)

実行結果

　

下図は上から順に 8 フレーム目と 9 フレーム目の図です。8 フレーム目で 赤枠のノードの評価値が 1 と計算されています。

その次の 9 フレーム目 では赤枠のノードは max ノード なので、子ノードの評価値の最大値 が α 値として計算 され、実際に α 値が -inf（負の無限大）から 1 に正しく更新されている ことが確認できます。

行う処理を表すメッセージの表示

現状では、上記のように α 値 と β 値 が 説明なしで更新 される点が 分かりづらい という問題があります。また、枝狩りが行われたことがわかりづらい という問題もあります。そこで、α 値と β 値の右に 行われた処理の種類を表す 以下の表のような メッセージを表示 することにします。もっとわかりやすいメッセージを思いついた人は自由に変更して下さい。

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

上記のメッセージは calc_score_by_ab で作成し、ablist_by_score の要素に記録するデータを (α 値, β 値, メッセージ) という tuple に変更します。

下記はそのように calc_score_by_ab を修正したプログラムです。下記の説明では、上記の表のメッセージを左端の列の番号に対応させて説明します。

  • 6 行目：ablist_by_score に ① のメッセージを入れた tuple を追加する
  • 8、26 行目：子ノードの評価値の計算が終了した直後の、枝狩りや α 値や β 値の更新を行う前の時点で ablist_by_score に ② のメッセージを入れた tuple を追加する
  • 11、12 行目：max node で β 狩りが行われた場合に α 値を更新し、nodelist_by_score にノードを追加し、ablist_by_score に ③ のメッセージを入れた tuple を追加する
  • 14 行目にあった alpha = max(alpha, score) の処理は、score > alpha の場合とそうでない場合に 異なるメッセージを計算する処理を行う必要がある ため、14、16 行目の if 文で行うように修正した
  • 14 ~ 16 行目：max node で β 狩りが行われず、α 値を更新する場合の ④ のメッセージを message に代入し、alpha を score の値で更新する
  • 17、18 行目：α 値を更新しない場合 の ⑤ のメッセージを message に代入する
  • 19、20 行目：nodelist_by_score にノードを追加し、ablist_by_score に 14 ~ 18 行目で計算したメッセージを入れた tuple を追加する
  • 26 ~ 38 行目：min node に対して上記と同様の修正を行う（⑥ ~ ⑧ のメッセージ）
  • 42 行目：このノードの評価値が確定したので、ablist_by_score に ⑨ のメッセージを入れた tuple を追加する
 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, "このノードの処理の開始"))
元と同じなので省略
 7                      self.nodelist_by_score.append(node)
 8                      self.ablist_by_score.append((alpha, beta, f"child score = {score}"))
 9                      if score >= beta:
10                          alpha = score
11                          self.nodelist_by_score.append(node)
12                          self.ablist_by_score.append((alpha, beta, f"child score = {score} ≧ {beta}(β値) によるβ狩り"))
13                          break
14                      if score > alpha:
15                          message = f"child score = {score} > {alpha}(α値)によるα値の更新"
16                          alpha = score
17                      else:
18                          message = f"child score = {score} ≦ {alpha}(α値)なのでα値の更新は行わない"
19                      self.nodelist_by_score.append(node)
20                      self.ablist_by_score.append((alpha, beta, message))
21                  node.score = alpha
22              else:
23                  for childnode in node.children:
24                      score = calc_ab_score(childnode, alpha, beta)
25                      self.nodelist_by_score.append(node)
26                      self.ablist_by_score.append((alpha, beta, f"child score = {score}"))
27                      if score <= alpha:
28                          beta = score
29                          self.nodelist_by_score.append(node)
30                          self.ablist_by_score.append((alpha, beta, f"child score = {score} ≦ {alpha}(α値)によるα狩り"))
31                          break
32                      if score < beta:
33                          message = f"child score = {score} < {beta}(β値) によるβ値の更新"
34                          beta = score
35                      else:
36                          message = f"child score = {score} ≧ {beta}(β値) なのでβ値の更新は行わない"
37                      self.nodelist_by_score.append(node)
38                      self.ablist_by_score.append((alpha, beta, message))
39                  node.score = beta
40
41          self.nodelist_by_score.append(node)
42          self.ablist_by_score.append((alpha, beta, f"このノードの評価値が {node.score} で確定"))
元と同じなので省略
43    
44  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, "このノードの処理の開始"))
        self.count += 1
        if node.mb.status != Marubatsu.PLAYING:
            self.calc_score_of_node(node)
        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, f"child score = {score}"))
                    if score >= beta:
                        alpha = score
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, 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, message))
                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, f"child score = {score}"))
                    if score <= alpha:
                        beta = score
                        self.nodelist_by_score.append(node)
                        self.ablist_by_score.append((alpha, beta, 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, message))
                node.score = beta

        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, f"このノードの評価値が {node.score} で確定"))
        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))
+       self.ablist_by_score.append((alpha, beta, "このノードの処理の開始"))
元と同じなので省略
                    self.nodelist_by_score.append(node)
+                   self.ablist_by_score.append((alpha, beta, f"child score = {score}"))
                    if score >= beta:
                        alpha = score
+                       self.nodelist_by_score.append(node)
-                       self.ablist_by_score.append((alpha, beta))
+                       self.ablist_by_score.append((alpha, beta, f"child score = {score} ≧ {beta}(β値) によるβ狩り"))
                        break
-                   alpha = max(alpha, score)
+                   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))
+                   self.ablist_by_score.append((alpha, beta, message))
                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, f"child score = {score}"))
                    if score <= alpha:
                        beta = score
+                       self.nodelist_by_score.append(node)
-                       self.ablist_by_score.append((alpha, beta))
+                       self.ablist_by_score.append((alpha, beta, f"child score = {score} ≦ {alpha}(α値)によるα狩り"))
                        break
-                   beta = min(beta, score)
+                   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))
+                   self.ablist_by_score.append((alpha, beta, message))
                node.score = beta

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

次に、update_gui を下記のプログラムのように 上記で作成したメッセージを表示 するように修正します。なお、8 行目で β 値のメッセージの表示場所 を 薄い灰色の長方形の位置に合わせて表示 するように修正しました。

  • 4 行目：2 番の要素に代入されたメッセージを message に代入するように修正した
  • 8 行目：β 値の表示位置を薄い灰色の長方形の位置にあわせて 10 から 9 に修正した
  • 9 行目：メッセージを表示するようにした
 1  def update_gui(self):
元と同じなので省略
 2      if self.isscore and hasattr(self.mbtree, "ablist_by_score"):
 3          fontsize = 70 * self.size
 4          alpha, beta, message = self.mbtree.ablist_by_score[self.play.value]
 5          acolor = "red" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "black"
 6          bcolor = "black" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "red"
 7          self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
 8          self.ax.text(9, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
 9          self.ax.text(19, -1, message, fontsize=fontsize)        
元と同じなので省略
10    
11  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.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.isscore and hasattr(self.mbtree, "ablist_by_score"):
        fontsize = 70 * self.size
        alpha, beta, message = self.mbtree.ablist_by_score[self.play.value]
        acolor = "red" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "black"
        bcolor = "black" if self.selectednode.mb.turn == Marubatsu.CIRCLE 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)             
                            
    disabled = self.play.value == 0
    self.set_button_status(self.prev_button, disabled=disabled)
    disabled = self.play.value == self.nodenum - 1
    self.set_button_status(self.next_button, disabled=disabled)
    
Mbtree_Anim.update_gui = update_gui
修正箇所 
def update_gui(self):
元と同じなので省略
    if self.isscore and hasattr(self.mbtree, "ablist_by_score"):
        fontsize = 70 * self.size
-       alpha, betae = self.mbtree.ablist_by_score[self.play.value]
+       alpha, beta, message = self.mbtree.ablist_by_score[self.play.value]
        acolor = "red" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "black"
        bcolor = "black" if self.selectednode.mb.turn == Marubatsu.CIRCLE else "red"
        self.ax.text(0, -1, f"α: {alpha}", fontsize=fontsize, c=acolor)        
-       self.ax.text(10, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
+       self.ax.text(9, -1, f"β: {beta}", fontsize=fontsize, c=bcolor)        
+       self.ax.text(19, -1, message, fontsize=fontsize)           
元と同じなので省略
    
Mbtree_Anim.update_gui = update_gui

表示の確認

上記のプログラムが正しく動作するかどうかを、いくつかのフレームの表示で確認することにします。

上記の修正後に下記のプログラムで calc_score_by_ab を実行して ablist_by_score 属性の値を計算しなおした mbtree を Mbtree_Anim で表示し、8 フレーム目まで表示を進めると実行結果が表示されます。8 フレーム目では 赤枠のノードの評価値が 1 で確定 し、そのことが メッセージとして正しく表示される ことが確認できます。

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

実行結果

その次の下図の 9 フレーム目では、赤枠の子ノードの評価値が 1 と計算された ことを表すメッセージが表示されます。

その次の下図の 10 フレーム目では、赤枠の子ノードの評価値が 1 が上図の 9 フレーム目の α 値である -inf（負の無限大）より大きいため、α 値が更新された ことを表す メッセージが表示 され、左上の α 値が実際に 1 に更新 されます。

本記事では行いませんが、α 値が更新されたことをさらに明確にするために、α 値の文字の色を別の色で表示したり、太字や下線で表示するという方法も考えられます。

その後の下図の 15 フレーム目では、赤枠の子ノードの評価値が 1 と計算されたことを表すメッセージが表示されます。

その次の下図の 16 フレーム目では、赤枠の子ノードの評価値が 1 が上図の 15 フレーム目の α 値である 1 以下であるため α 値が更新されない ことを表す メッセージが表示 されます。また、実際に α 値は上図の値から更新されません。

その次の下図の 17 フレーム目で 赤枠のノードの評価値が 1 で確定 し、その次の下図の 18 フレーム目では 赤枠の 子ノードの評価値が 1 と計算 されたことを表すメッセージがそれぞれ表示されます。

その次の下図の 19 フレーム目で赤枠の 子ノードの評価値が α 値である 1 以下 になったため、α 狩り が行われたことを表す メッセージが表示 されます。なお、α 狩りを行った場合は、子ノードの評価値が赤枠のノードの評価値となるため、赤枠のノードの評価値を表す β 値に子ノードの評価値が代入され、図の β 値には 1 が表示されます。

その次の下図の 20 フレーム目で α 狩り が行われた結果、残りの子ノードの評価値の計算が省略 され、赤枠のノードの 評価値が β 値である 1 で確定 したことを表す メッセージが表示 されます。

上記では先ほどの表の全てのメッセージの確認を行っていませんが、② の子ノードの評価値の計算、④ の α 値の更新、⑤ の α 値を更新しない、⑥ の α 狩り、⑨ の評価値の確定のメッセージが 意図通りに表示されることが確認 できました。興味がある方は、残りのメッセージも正しく表示されることを確認してみて下さい。

今回の記事のまとめ

今回の記事では、α 値と β 値の表示、max ノードと min ノードの明確化、各フレームで行われる処理を表すメッセージの表示を実装しました。

これで αβ 法で行われる処理の手順がわかりやすくなりましたが、まだ改良の余地があります。どのような改良の余地があるかについて考えてみて下さい。

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

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

次回の記事

近日公開予定です

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?