目次と前回の記事

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

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

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

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

枝狩りが行われたノードの表示の明確化

前回の記事で αβ 法で評価値を計算する手順のアニメーションを改良しましたが、まだ改良の余地がいくつかあるので今回の記事でも引き続き改良を行うことにします。

現状の問題点は、枝狩りが行われたノード と、評価値の計算がまだ行われていないノード が同じ暗い色で描画されるため 区別が付けづらい 点です。例えば下図の 18 フレーム目では、計算された子ノードの評価値が α 値以下なので、次のフレームで α 狩りが行われます。

実際に下図の次の 19 フレーム目で α 狩りによって 紫色の枠内¹のノードの評価値の計算が省略 されて、β 値が 1 に更新されますが、下図では 枝狩りされた紫色の枠内のノード と、評価値が計算されていないノード が どちらも灰色で描画 されるため、区別がつきません。

そこで、枝狩りが行われたノード を評価値が計算されていないノード より暗い色で描画 することで、評価値が計算されていないノードと 区別ができるようにする という改良を行います。どのように修正を行えば良いかについて少し考えてみて下さい。

以下の説明では、枝狩りが行われたノードの色を、より暗い色 と表記することにします。

枝狩りが行われたフレームの記録

現状では以下の方法で評価値が計算されていないノードを暗く表示しています。忘れた方は以前の記事を復習して下さい。

それぞれのノードに対して 評価値が計算されたアニメーションのフレーム を score_index という属性に代入する
Mbtree クラスの draw_subtree メソッドでノードを描画する際に、アニメーションのフレーム とノードの score_index 属性を比較 し、アニメーションのフレームが score_index 属性未満の場合に 暗く描画 する
評価値が計算されない、枝狩りが行われたノードを暗く表示する ために、あらかじめすべてのノードの score_index 属性に正の無限大を表す数値を代入 する

上記と同様に枝狩りが行われたノードに対して 枝狩りが行われたアニメーションのフレームを記録 し、ノードを描画する際に アニメーションのフレームと比較 することで枝狩りが行われたノードをより暗く描画することができるようになります。具体的には以下のようなアルゴリズムで枝狩りが行われたノードをより暗く描画します。

それぞれのノードに対して 枝狩り（prune）が行われたフレーム を pruned_index という属性に代入する
draw_subtree ノードを描画する際に、アニメーションのフレームとノードの pruned_index 属性を比較し、アニメーションのフレームが pruned_index 属性以上の場合により暗く描画する。score_index の場合と異なり「以上」である 点に注意する事
枝狩りが 行われていない ノードが より暗く描画されないようにする ために、あらかじめすべてのノードのpruned_index 属性に正の無限大を表す数値を代入 する

pruned_index 属性の計算は、score_index と同様に calc_score_by_ab メソッド内で計算 します。どのように計算すればよいかについて少し考えてみて下さい。

`pruned_index` 属性を計算するアルゴリズム

現状の calc_score_by_ab は、α 狩りまたは β 狩り が行われる条件が満たされると、枝狩りが行われるノードに対する処理が省略 されてしまうため、枝狩りが行われたノードの pruned_index 属性を計算することはできません。この問題を解決する方法の一つに、指定したノードとその子孫ノードの pruned_index 属性に枝狩りが行われた アニメーションのフレームを代入 する 関数を定義 し、枝狩りが行われた場合に その関数を利用して枝狩りを行うノードの pruned_index 属性を計算 するという方法があります。

なお、参考までに、別の方法について今回の記事の最後で紹介します。

`pruned_index` 属性を計算する関数の定義

まず、Mbtree クラスの calc_score_by_ab の中に下記のような ローカル関数を定義 します。この関数は幅優先アルゴリズムと深さ優先アルゴリズムのどちらの方法でも定義できますが、本記事では より簡潔に記述 できる 深さ優先アルゴリズム で定義する事にします。

名前：pruned_index 属性に値を代入（assign）するので、assign_pruned_index とする
処理：指定したノードと、その子孫ノードの pruned_index 属性に、指定した値を代入する処理を、深さ優先アルゴリズムで行う
入力：仮引数 node に 処理を行うノード を、仮引数 index に pruned_index 属性に代入する値 を代入する
出力：なし

下記は assign_pruned_index の定義です。行っている処理は 2 行目で node の pruned_index 属性に index を代入 し、3、4 行目で node の それぞれの子ノード に対して index を実引数に記述して assign_pruned_index を 再帰呼び出し するというものです。この処理によって深さ優先アルゴリズムで、指定したノードとそのすべての子孫ノードの pruned_index 属性に index を代入することができます。

1  def assign_pruned_index(node, index):
2      node.pruned_index = index
3      for childnode in node.children:
4          assign_pruned_index(childnode, index)

次に、calc_score_by_ab の中で 枝狩りが行われた際 に、枝狩りによって評価値の計算を省略する 残りの子ノードに対して assign_pruned_index を呼び出す ように修正します。また、あらかじめ すべてのノードの pruned_index 属性に正の無限大を代入 する処理を記述します。下記はそのように calc_score_by_ab を修正したプログラムです。

7 ~ 10 行目：上記の assign_pruned_index をローカル関数として定義する
16 ~ 18 行目：15 行目の条件式で max ノードで β 狩りを行うことが判定された場合に、下記の手順で 残りの子ノード に対して calc_score_by_ab を呼び出す ことで、枝狩りが行われたすべてのノード の pruned_index 属性に アニメーションのフレームを代入 する
16 行目：残りの子ノードは、子ノードの一覧を表す node.children の中で childnode より後の要素 である。そこで、node.children の中で childnode が代入されている 要素のインデックス を list の index メソッド を利用して計算する
17 行目：childnode より後の要素の一覧 は、list の スライス表記 を利用して node.children[index + 1:] と記述できるので、それに対する繰り返し処理を行う
18 行目：assign_pruned_index を呼び出して残りの子ノードとその子孫ノードの pruned_index 属性に枝狩りが行われたアニメーションのフレームを代入する。枝狩りが行われた アニメーションのフレームのデータ は nodelist_by_score の 最後の要素に代入 されているので、そのインデックスは len(self.nodelist_by_score) - 1) で計算できる
24 ~ 26 行目：min ノードの α 狩りが行われた場合も同様の処理を行う
32 行目：αβ 法で評価値を計算する前に、すべてのノードの pruned_index 属性に正の無限大を表す float("inf") を代入しておく

 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3
 4  def calc_score_by_ab(self, abroot, debug=False):           
 5      self.count = 0
 6       
 7      def assign_pruned_index(node, index):
 8          node.pruned_index = index
 9          for childnode in node.children:
10              assign_pruned_index(childnode, index)
11         
12      def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
13              if node.mb.turn == Marubatsu.CIRCLE:
14                  for childnode in node.children:
元と同じなので省略                
15                      if score >= beta:
16                          index = node.children.index(childnode)
17                          for prunednode in node.children[index + 1:]:
18                              assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
19                          break
20                  node.score = alpha
21              else:
22                  for childnode in node.children:
元と同じなので省略
23                      if score <= alpha:
24                          index = node.children.index(childnode)
25                          for prunednode in node.children[index + 1:]:
26                              assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
27                          break
28                  node.score = beta
元と同じなので省略
29      from ai import dprint       
30      for node in self.nodelist:
31          node.score_index = float("inf")
32          node.pruned_index = float("inf")
元と同じなので省略        
33     
34  Mbtree.calc_score_by_ab = calc_score_by_ab

行番号のないプログラム

from tree import Mbtree
from marubatsu import Marubatsu

def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
    def assign_pruned_index(node, index):
        node.pruned_index = index
        for childnode in node.children:
            assign_pruned_index(childnode, index)
        
    def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
        self.nodelist_by_score.append(node)
        self.ablist_by_score.append((alpha, beta, None, "start"))
        self.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:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                        break
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta)
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, score, "score"))
                    if score < beta:
                        beta = score
                    self.nodelist_by_score.append(node)
                    self.ablist_by_score.append((alpha, beta, None, "update"))
                    if score <= alpha:
                        index = node.children.index(childnode)
                        for prunednode in node.children[index + 1:]:
                            assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                        break
                node.score = beta

        self.nodelist_by_score.append(node)
        self.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")
        node.pruned_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 tree import Mbtree
from marubatsu import Marubatsu

def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
+   def assign_pruned_index(node, index):
+       node.pruned_index = index
+       for childnode in node.children:
+           assign_pruned_index(childnode, index)
        
    def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
元と同じなので省略                
                    if score >= beta:
+                       index = node.children.index(childnode)
+                       for prunednode in node.children[index + 1:]:
+                           assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                        break
                node.score = alpha
            else:
                for childnode in node.children:
元と同じなので省略
                    if score <= alpha:
+                       index = node.children.index(childnode)
+                       for prunednode in node.children[index + 1:]:
+                           assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
                        break
                node.score = beta
元と同じなので省略
    from ai import dprint       
    for node in self.nodelist:
        node.score_index = float("inf")
+       node.pruned_index = float("inf")
元と同じなので省略        
    
Mbtree.calc_score_by_ab = calc_score_by_ab

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

次に、ゲーム木の部分木を描画する Mbtree クラスの draw_subtree メソッドを、枝狩りが行われたノードがより暗く描画 されるように修正します。どのように修正すれば良いかについて少し考えてみて下さい。

ノードの表示の暗さ は、draw_subtree 内の下記のローカル関数 calc_darkness で計算 しています。この中で、Mbtree_Anim によるアニメーション が行われている場合の処理は 12、13 行目に記述 されています。

 1  def calc_darkness(node):
 2      if show_bestmove:
 3          if node.parent is None:
 4              return 0, show_score
 5          elif node.mb.last_move in node.parent.bestmoves:
 6              return 0, show_score
 7          else:
 8              return 0.2, show_score
 9         
10      if anim_frame is None:
11          return 0, show_score
12      index = node.score_index if isscore else node.id
13      return (0.5, False) if index > anim_frame else (0, isscore)

Mbtree_Anim で評価値を計算する手順を描画する場合は isscore に True が代入されているので、12、13 行目では以下の処理が行われます。

評価値が計算されるより前のアニメーションのフレーム の場合は 暗い色（0.5)で評価値を描画しない（False） という意味を表す (0.5, False) を返す
そうでない場合は 明るい色で評価値を描画する という意味を表す (0, True) を返す

枝狩りが行われたノード は 評価値が計算されることはない ので、12、13 行目が実行されるとそのノードが 暗い色で描画される ことになります。そのため、枝狩りが行われたノードを、枝狩りが行われたフレーム以降 で より暗く描画 するためには、その処理を 12 行目よりも前に記述 する必要があります。

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

9 行目：pruned_index 属性は、calc_score_by_ab を実行しない限り作られないので 存在しない場合がある。そこで、組み込み関数 get_attr を利用して、pruned_index 属性が存在する場合はその値 を、存在しない場合は None をローカル変数 pruned_index に代入する処理を行う。get_attr について忘れた方は以前の記事を復習すること
10、11 行目：pruned_index が None ではなく、アニメーションのフレーム 以下の場合 にノードを より暗い色で評価値を表示しない ことを表す (0.8, False) を返すように修正する。なお、もっと暗くしたい場合は 0.8 を 1 以下のより大きな値に修正すれば良い

 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                     
 6      def calc_darkness(node):
元と同じなので省略
 7          if anim_frame is None:
 8              return 0, show_score
 9          pruned_index = getattr(node, "pruned_index", None)
10          if pruned_index is not None and anim_frame >= pruned_index:
11              return (0.8, False)
12          index = node.score_index if isscore else node.id
13          return (0.5, False) if index > anim_frame else (0, isscore)
元と同じなので省略
14             
15  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
        pruned_index = getattr(node, "pruned_index", None)
        if pruned_index is not None and anim_frame >= pruned_index:
            return (0.8, False)
        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):   
                    
    def calc_darkness(node):
元と同じなので省略
        if anim_frame is None:
            return 0, show_score
+       pruned_index = getattr(node, "pruned_index", None)
+       if pruned_index is not None and anim_frame >= pruned_index:
+           return (0.8, False)
        index = node.score_index if isscore else node.id
        return (0.5, False) if index > anim_frame else (0, isscore)
元と同じなので省略
            
Mbtree.draw_subtree = draw_subtree

動作の確認

上記の修正後に下記のプログラムで calc_score_by_ab によって αβ 法で評価値を計算した mbtree に対して Mbtree_Anim を実行して 正しく表示されるかどうかを確認します。

from tree import Mbtree_Anim

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

下記は α 狩りが行われる直前 の 18 フレーム目²と α 狩りが行われた 19 フレーム目の画像です。19 フレーム目の画像では、2 つのノード の枝狩りが行われて より暗い色で描画される ようになったことが確認できます。なお、下図を見てまだ区別がつきづらいと思った方は、先程の calc_darkness の 13 行目の評価値が計算されていないノードの暗さを表す 0.5 より小さくしてもう少し明るく描画するようにすると良いでしょう。

下記は β 狩りが行われる直前 の 125 フレーム目と β 狩りが行われた 126 フレーム目の画像です。126 フレーム目の画像から 5 つのノード が枝狩りが行われて より暗い色で描画される ようになったことが確認できます。

かなり多くのノードの枝狩りが行われる例 として下図の 14324 フレーム目とその次のフレームを紹介します。14325 フレーム目では、赤枠の 2 つ目以降の子ノードとその子孫ノード が すべて枝狩りの対象となる ため、図にはそれらのノードが全て描画されてはいませんが、かなり多くの数のノードの枝狩りが行われます。

別の実装方法

上記では assign_pruned_index という 関数を定義 して枝狩りが行われたノードの pruned_index 属性の値を計算しましたが、そのような関数を定義せず に、calc_score_by_ab の中で pruned_index 属性の値を計算 することもできます。

なお、その実装方法 は assign_pruned_index という関数を定義する実装方法と比べると、プログラムがわかりづらい と思いますので 本記事では採用しません。ただし、どちらがわかりやすいかは人それぞれだと思います。また、場合によってはこちらの実装方法のほうがわかりやすくなることもある と思いますので紹介します。

実装方法の考え方

この実装方法の考え方は以下の通りです。

calc_score_by_ab 内で定義されたローカル関数 calc_ab_score に、処理を行うノード が 枝狩りが行われているかどうかを表す仮引数 pruned を追加する
仮引数 pruned が True の場合は、その 子ノードも枝狩りが行われる ので calc_ab_score 内で calc_ab_score を 再帰呼び出し して 子ノードの処理を行う際 に、仮引数 pruned に対応する 実引数に pruned を記述 して呼び出すことで、子ノードでも枝狩りが行われたノードとして処理が行われるようになる
仮引数 pruned が False の場合は場合は、α 狩りまたは β 狩りが行われるまでの間 は、子ノードの枝狩りは行われない。そこで、以下のような処理を行うことで、適切な処理が行われるようにする
- calc_ab_score を 再帰呼び出し する際に、上記の場合と同様に仮引数 pruned に対応する 実引数に pruned を記述 する
- 枝狩りが行われた時点で pruned に True を代入する ことで、枝狩りが行われるまでの間は子ノードが枝狩りが行われていないノードとして処理が行われ、枝狩りが行われた後は子ノードが枝狩りが行われたノードとして処理が行われるようになる
calc_score_by_ab から calc_ab_score を呼び出す際 には、αβ 法の計算を行う前で 枝狩りは行われていない ので、仮引数 pruned に False が代入 されるように呼び出す

具体的には、calc_ab_score 内で、仮引数 pruned の値に応じて 以下のような処理を行うようにプログラムを修正します。ただし、何れの場合も calc_ab_score を再帰呼び出し する際には、仮引数 pruned に対応する 実引数に pruned を記述 して呼び出します。

pruned に True が代入 されている場合
- 最初に pruned_index 属性に 現在のアニメーションのフレームを代入 する
- 枝狩りがされたノードは 評価値の計算の処理が行われない ので、nodelist_by_score 属性や、ablist_by_score 属性に要素を追加する 処理を行わないようにする
- 繰り返し処理の中で 子ノードに対する calc_ab_score の再帰呼び出しは行う が、子ノードの 評価値に関する 枝狩りや α 値、β 値の更新の 処理は行わない
pruned に False が代入 されている場合
- 枝狩りが行われていないことを意味するので これまでと同様の処理 を行う
- ただし、α 狩りまたは β 狩り が行われた場合は pruned に True を代入し、break 文を削除 して繰り返し処理を 中断しないよう にする。そのようにすることで、残りの子ノード に対する繰り返し 処理が続行 し、calc_ab_score の再帰呼び出しで仮引数 pruned に対応する 実引数に True が記述されて呼び出されるようになる

`calc_score_by_ab` の修正

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

4 行目：仮引数 pruned を追加する。また、pruned を デフォルト値が False の デフォルト引数とする ことで、calc_score_by_ab から calc_ab_score を呼び出す際に 仮引数 pruned に対応する実引数を記述するように 修正しなくても良いようにする
5、6 行目：pruned が True の場合に pruned_index に現在のアニメーションのフレームを代入するようにする
7 ~ 9、37 ~ 40 行目：pruned が False の場合のみ nodelist_by_score 属性や、ablist_by_score 属性に 要素を追加する処理を行う ようにする
12、25 行目：calc_ab_score の 再帰呼び出し で仮引数 pruned に対応する 実引数に pruned を記述 して呼び出すように修正する
13 ~ 21 行目：子ノードの評価値に関する枝狩りなどの処理を、pruned が False の場合のみ行うように修正する
21 行目：β 狩り が行われる場合に pruned に True を代入 し、break 文を削除 して残りの枝狩りがされたノードに対する 繰り返し処理が続行される ように修正する
26 ~ 34 行目：min ノードに対して上記と同様の修正を行う

 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"), pruned=False):
 5          if pruned:
 6              node.pruned_index = len(self.nodelist_by_score) - 1
 7          else:
 8              self.nodelist_by_score.append(node)
 9              self.ablist_by_score.append((alpha, beta, None, "start"))
元と同じなので省略
10              if node.mb.turn == Marubatsu.CIRCLE:
11                  for childnode in node.children:
12                      score = calc_ab_score(childnode, alpha, beta, pruned)
13                      if not pruned:
14                          self.nodelist_by_score.append(node)
15                          self.ablist_by_score.append((alpha, beta, score, "score"))
16                          if score > alpha:
17                              alpha = score
18                          self.nodelist_by_score.append(node)
19                          self.ablist_by_score.append((alpha, beta, None, "update"))
20                          if score >= beta:
21                              pruned = True
22                  node.score = alpha
23              else:
24                  for childnode in node.children:
25                      score = calc_ab_score(childnode, alpha, beta, pruned)
26                      if not pruned:
27                          self.nodelist_by_score.append(node)
28                          self.ablist_by_score.append((alpha, beta, score, "score"))
29                          if score < beta:
30                              beta = score
31                          self.nodelist_by_score.append(node)
32                          self.ablist_by_score.append((alpha, beta, None, "update"))
33                          if score <= alpha:
34                              pruned = True
35                  node.score = beta
36 
37          if not pruned:
38              self.nodelist_by_score.append(node)
39              self.ablist_by_score.append((alpha, beta, None, "end"))
40              node.score_index = len(self.nodelist_by_score) - 1          
41          return node.score
元と同じなので省略
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"), pruned=False):
        if pruned:
            node.pruned_index = len(self.nodelist_by_score) - 1
        else:
            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, pruned)
                    if not pruned:
                        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:
                            pruned = True
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta, pruned)
                    if not pruned:
                        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:
                            pruned = True
                node.score = beta

        if not pruned:
            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

修正箇所（3 箇所ある if not pruned: のブロックのインデントの修正は省略しました）

def calc_score_by_ab(self, abroot, debug=False):           
    self.count = 0
      
-   def calc_ab_score(node, alpha=float("-inf"), beta=float("inf")):
+   def calc_ab_score(node, alpha=float("-inf"), beta=float("inf"), pruned=False):
-       self.nodelist_by_score.append(node)
-       self.ablist_by_score.append((alpha, beta, None, "start"))
+       if pruned:
+           node.pruned_index = len(self.nodelist_by_score) - 1
+       else:
+           self.nodelist_by_score.append(node)
+           self.ablist_by_score.append((alpha, beta, None, "start"))
元と同じなので省略
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta)
+                   score = calc_ab_score(childnode, alpha, beta, pruned)
+                   if not pruned:
                        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:
+                           pruned = True
-                           break                            
                node.score = alpha
            else:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta)
+                   score = calc_ab_score(childnode, alpha, beta, pruned)
+                   if not pruned:
                        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:
+                           pruned = True
-                           break
                node.score = beta

+       if not pruned:
            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
元と同じなので省略
    
Mbtree.calc_score_by_ab = calc_score_by_ab

動作の確認

上記の修正後に下記のプログラムを実行して calc_score_by_ab で計算し直した mbtree に対する Mbtree_Anim の動作を確認します。

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

次のフレームでα 狩り が行われる下図の 18 フレーム目は 先ほどと同じ表示 が行われることが確認できます。

その次の α 狩りが行われた 下図の 19 フレーム目も先ほどと同様に 枝狩りが行われたノードがより暗く表示される ことが確認できます。

しかし、その次の下図の 20 フレーム目では、評価値が確定するフレームが飛ばされて、親ノードのフレームの処理が表示されるという バグが発生 していることが確認できます。

このようなバグが発生する原因について少し考えてみて下さい。

バグの検証

上記のバグは、α 狩りが発生した際に生じている ので、その場合の calc_ab_score の 処理を検証 することにします。

18 フレームの赤枠のノードに対して calc_ab_score が呼ばれると、下記のような手順で処理が行われるため評価値が確定されたフレームが記録されなくなります。

枝狩りがされていない ので、仮引数 pruned には False が代入 されている
2 つ目の子ノードの評価値が計算された時点で α 狩り が行われて pruned に True が代入 される
その結果、繰り返し処理が終了した時点 の pruned の値は True なので、calc_ab_score の最後の下記の 評価値が確定したフレームを記録する処理 が 実行されなくなる

        if not pruned:
            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

枝狩り が行われた際に 評価値の計算の処理が省略される のは、残りの子ノードとその子孫ノード で、そのノードの評価値を計算する処理が省略されるわけではない ので、calc_ab_score の処理の途中で pruned の値を変更してはいけません。それも関わらず枝狩りが行われた際に pruned の値を変更してしまっている のがこの エラーの原因 です。

バグの修正

仮引数 pruned を変更しないようにする 方法の一つに、子ノードに対する繰り返し処理を行う前 に 別の変数に pruend を代入 し、枝狩りが行われた際に その変数の値を True に変更する という方法があります。

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

5 行目：子ノードの評価値を計算する前に、child_pruned に pruned を代入する
8、9、17、21、22、30 行目：pruned を child_pruned に修正する

 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"), pruned=False):
元と同じなので省略
 5              child_pruned = pruned
 6              if node.mb.turn == Marubatsu.CIRCLE:
 7                  for childnode in node.children:
 8                      score = calc_ab_score(childnode, alpha, beta, child_pruned)
 9                      if not child_pruned:
10                          self.nodelist_by_score.append(node)
11                          self.ablist_by_score.append((alpha, beta, score, "score"))
12                          if score > alpha:
13                              alpha = score
14                          self.nodelist_by_score.append(node)
15                          self.ablist_by_score.append((alpha, beta, None, "update"))
16                          if score >= beta:
17                              child_pruned = True
18                  node.score = alpha
19              else:
20                  for childnode in node.children:
21                      score = calc_ab_score(childnode, alpha, beta, child_pruned)
22                      if not child_pruned:
23                          self.nodelist_by_score.append(node)
24                          self.ablist_by_score.append((alpha, beta, score, "score"))
25                          if score < beta:
26                              beta = score
27                          self.nodelist_by_score.append(node)
28                          self.ablist_by_score.append((alpha, beta, None, "update"))
29                          if score <= alpha:
30                              child_pruned = True
31                  node.score = beta
元と同じなので省略
32    
33  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"), pruned=False):
        if pruned:
            node.pruned_index = len(self.nodelist_by_score) - 1
        else:
            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:
            child_pruned = pruned
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta, child_pruned)
                    if not child_pruned:
                        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:
                            child_pruned = True
                node.score = alpha
            else:
                for childnode in node.children:
                    score = calc_ab_score(childnode, alpha, beta, child_pruned)
                    if not child_pruned:
                        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:
                            child_pruned = True
                node.score = beta

        if not pruned:
            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"), pruned=False):
元と同じなので省略
+           child_pruned = pruned
            if node.mb.turn == Marubatsu.CIRCLE:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta, pruned)
+                   score = calc_ab_score(childnode, alpha, beta, child_pruned)
-                   if not pruned:
+                   if not child_pruned:
                        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:
-                           pruned = True
+                           child_pruned = True
                node.score = alpha
            else:
                for childnode in node.children:
-                   score = calc_ab_score(childnode, alpha, beta, pruned)
+                   score = calc_ab_score(childnode, alpha, beta, child_pruned)
-                   if not pruned:
+                   if not child_pruned:
                        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:
-                           pruned = True
+                           child_pruned = True
                node.score = beta
元と同じなので省略
   
Mbtree.calc_score_by_ab = calc_score_by_ab

上記の修正後に下記のプログラムを実行して calc_score_by_ab で計算し直した mbtree に対する Mbtree_Anim の動作を確認すると、実行結果のように 20 フレーム目 に赤枠のノードの評価値が確定した図が 正しく描画される ことが確認できます。

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

実行結果

なお、先程も説明しましたが、この方法はプログラムがわかりづらくなる点と、上記のようなバグが発生する可能性があるので本記事では採用しません。

今回の記事のまとめ

今回の記事では枝狩りされたノードをより暗い色で描画して区別できるようにする改良を行いました。また、その改良を行う 2 種類の方法を紹介しました。

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

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

次回の記事

この紫色の枠は説明のために表記したものなので、実際には描画されません ↩
18 フレーム目の画像は先ほどと同じです ↩