目次と前回の記事

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

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

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

ルールベースの AI の一覧については、下記の記事を参照して下さい。

深さ優先アルゴリズムによる評価値の計算の過程の視覚化

前回の記事では、深さ優先アルゴリズム でゲーム木の評価値を計算する calc_score_by_df を実装しましたが、評価値の計算の過程が直観的にわかりづらい と思いましたので、今回の記事ではその処理の過程を視覚化することにします。

最強の AI の作成は次回の記事で行います。

視覚化に必要なデータの計算

以前の記事でゲーム木の作成の過程のアニメーションを行う Mbtree_Anim クラスを定義しましたが、評価値の計算の過程の視覚化 も同様に アニメーションで行う ことにします。どのようなアニメーションにすれば良いかについて少し考えてみて下さい。

視覚化の方針

本記事では下記のような方針のアニメーションで計算の過程を視覚化することにします。もっと良い視覚化の方法を思いついた方はその方針での実装にチャレンジしてみて下さい。

計算の過程で calc_score_by_df が 処理を行うノードの移り変わりがわかる ようにする
評価値を計算 する タイミングがわかる ようにする

上記の方針でアニメーションを行うためには、calc_score_by_df による、別のノードへの処理の移り変わりを記録する 必要があります。また、評価値が計算されるタイミングを記録 する必要があります。

`nodelist_by_score` の記録

まず、別のノードへの処理の移り変わりを記録 する処理を実装することにします。本記事ではそのデータを、Mbtree クラスの nodelist_by_score という名前の属性に list で記録する ことにします。次に、別のノードへの処理の移り変わりが どのタイミングで行われるか を考える必要があります。どのようなタイミングであるかについて少し考えてみて下さい。

calc_score_by_df は、仮引数 node に代入されたノードの処理を行う 関数で、評価値を計算する処理は、この関数に対する 再帰呼び出し で行います。従って、別のノードへの処理の移り変わりは、以下のタイミングで行われます。

calc_score_by_df が 呼び出された時
calc_score_by_df の中で呼び出された 再帰呼び出しの処理が終了した時

従って、calc_score_by_df を下記のプログラムのように修正することで、nodelist_by_score に別のノードへの処理の移り変わりを記録することができます。

5 行目：calc_score_by_df が 呼び出された直後 に、nodelist_by_score の要素に node を追加して記録する
14、15 行目：node のそれぞれの子ノードの評価値を計算するための再帰呼び出しの処理が終了するたびに　nodelist_by_score に要素を追加する処理は、list 内包表記では記述できない ので、list 内包表記を for 文を使った記述に修正する
16 行目：子ノードの評価値を計算するための 再帰呼び出しの処理の終了後 に、nodelist_by_score の要素に node を追加して記録する

 1  from tree import Mbtree
 2  from marubatsu import Marubatsu
 3
 4  def calc_score_by_df(self, node):
 5      self.nodelist_by_score.append(node)
 6      if node.mb.status == Marubatsu.CIRCLE:
 7          node.score = 1
 8      elif node.mb.status == Marubatsu.DRAW:
 9          node.score = 0
10      elif node.mb.status == Marubatsu.CROSS:
11          node.score = -1
12      else:
13          score_list = []
14          for childnode in node.children:
15              score_list.append(self.calc_score_by_df(childnode))
16              self.nodelist_by_score.append(node)
17          if node.mb.move_count % 2 == 0:
18              score = max(score_list)
19          else:
20              score = min(score_list)
21          node.score = score
22
23      return node.score                
24
25  Mbtree.calc_score_by_df = calc_score_by_df

行番号のないプログラム

from tree import Mbtree
from marubatsu import Marubatsu

def calc_score_by_df(self, node):
    self.nodelist_by_score.append(node)
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = -1
    else:
        score_list = []
        for childnode in node.children:
            score_list.append(self.calc_score_by_df(childnode))
            self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score

    return node.score                

Mbtree.calc_score_by_df = calc_score_by_df

修正箇所

from tree import Mbtree
from marubatsu import Marubatsu

def calc_score_by_df(self, node):
+   self.nodelist_by_score.append(node)
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = -1
    else:
        score_list = []
-       score_list = [self.calc_score_by_df(childnode) for childnode in node.children]
+       for childnode in node.children:
+           score_list.append(self.calc_score_by_df(childnode))
+           self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score

    return node.score                

Mbtree.calc_score_by_df = calc_score_by_df

上記の修正を行った後で、下記のプログラムを実行すると、実行結果から calc_score_by_df によって nodelist_by_score のデータが 計算できていそうなことが確認 できます。なお、本当に計算できているかどうかについてはもっとデータを見る必要がありますが、その確認はこの後で作成するアニメーションで行うことにします。

1 行目：前回の記事で保存した dfscore.mbtree から Mbtree のデータを読み込む
2 行目：nodelist_by_score 属性を空の list で初期化する
3 行目：calc_score_by_df を呼び出して、評価値と nodelist_by_score を計算する
4、5 行目：nodelist_by_score の最初の 5 つのノードの局面を表示する

1  mbtree_df = Mbtree.load("dfscore")
2  mbtree_df.nodelist_by_score = []
3  mbtree_df.calc_score_by_df(mbtree_df.root)
4  for i in range(5):
5      print(mbtree_df.nodelist_by_score[i].mb)

行番号のないプログラム

mbtree_df = Mbtree.load("dfscore")
mbtree_df.nodelist_by_score = []
mbtree_df.calc_score_by_df(mbtree_df.root)
for i in range(5):
    print(mbtree_df.nodelist_by_score[i].mb)

実行結果

Turn o
...
...
...

Turn x
O..
...
...

Turn o
oX.
...
...

Turn x
oxO
...
...

Turn o
oxo
X..
...

評価値が計算されたタイミングの記録

次にノードの 評価値が計算されたタイミングを記録 する処理を実装します。どのように実装すればよいかについて少し考えてみて下さい。

まず、ノードの評価値が計算されたタイミングを どのように表現するか を考える必要があります。先程 nodelist_by_score には別のノードへの処理の移り変わりを表すデータ記録しましたが、その中にノードの評価値が計算されたことを表すデータを記録 することによって、ノードの評価値が計算されたタイミングを、nodelist_by_score の要素のインデックスで表現 することができるようになります。

ノード評価値が計算されたタイミングを表すデータは、そのノードの属性に記録するのが自然なので、score_index という属性に代入することにします。

言葉の説明ではわかりづらいと思いますので、具体例として、評価値を計算する過程で、再起呼びしで calc_score_by_df が下図の ノード A を実引数に記述して 呼び出された場合 に行われる処理について説明します。

この場合は、以下の手順で処理が行われます。

ノード A が実引数に記述されて calc_score_by_df が呼び出される
呼び出された calc_score_by_df の最初で nodelist_by_score にノード A が登録される
ノード B が実引数に記述されて calc_score_by_df が呼び出される
呼び出された calc_score_by_df の最初で nodelist_by_score にノード B が登録される
ノード C が実引数に記述されて calc_score_by_df が呼び出される
呼び出された calc_score_by_df の最初で nodelist_by_score にノード C が登録される
ノード C の 評価値が計算 され nodelist_by_score に図の 赤字のノード C が登録 される
ノード C の score_index 属性に、図の 赤字のノード C が代入 されている nodelist_by_score の要素のインデックス を代入する
ノード C の処理を行う calc_score_by_df の処理が終了する
ノード B の処理を行う calc_score_by_df の中で、nodelist_by_score にノード B が登録される
以下処理が続いていく

下記は、評価値が計算されたタイミングを記録するように calc_score_by_df を修正したプログラムです。

3 行目：node の評価値が計算され、返り値を返す前に、nodelist_by_score に node を追加する
4 行目：追加した node のインデックスは、nodelist_by_score の要素の数 - 1 なので、その値を node の score_index 属性に代入する

1  def calc_score_by_df(self, node):
元と同じなので省略
2
3      self.nodelist_by_score.append(node)
4      node.score_index = len(self.nodelist_by_score) - 1        
5      return node.score                
6
7  Mbtree.calc_score_by_df = calc_score_by_df

行番号のないプログラム

def calc_score_by_df(self, node):
    self.nodelist_by_score.append(node)
    if node.mb.status == Marubatsu.CIRCLE:
        node.score = 1
    elif node.mb.status == Marubatsu.DRAW:
        node.score = 0
    elif node.mb.status == Marubatsu.CROSS:
        node.score = -1
    else:
        score_list = []
        for childnode in node.children:
            score_list.append(self.calc_score_by_df(childnode))
            self.nodelist_by_score.append(node)
        if node.mb.move_count % 2 == 0:
            score = max(score_list)
        else:
            score = min(score_list)
        node.score = score
        
    self.nodelist_by_score.append(node)
    node.score_index = len(self.nodelist_by_score) - 1        
    return node.score                

Mbtree.calc_score_by_df = calc_score_by_df

修正箇所

def calc_score_by_df(self, node):
元と同じなので省略

+   self.nodelist_by_score.append(node)
+   node.score_index = len(self.nodelist_by_score) - 1        
    return node.score                

Mbtree.calc_score_by_df = calc_score_by_df

深さ優先アルゴリズムの場合は、ルートノードの評価値は最後に計算される ので、ルートノードの score_index 属性 は、nodelist_by_score の最後の要素 のインデックスであるnodelist_by_score の要素の数 - 1 になります。上記の修正後に、下記のプログラムで calc_score_by_df を実行し直し、nodelist_by_score の要素の数とルートノードの score_index 属性を表示すると、実行結果からそのようになっていることが確認できます。

mbtree_df.nodelist_by_score = []
mbtree_df.calc_score_by_df(mbtree_df.root)
print(len(mbtree_df.nodelist_by_score), mbtree_df.root.score_index)

実行結果

1649837 1649836

`init` メソッドの修正

修正した calc_score_by_df で評価値を計算する際には、上記のプログラムのように nodelst_by_score を空の list で初期化する処理が必要になりますが、その処理は Mbtree クラスの __init__ メソッドには記述されていない ので、下記のプログラム 5 行目のように __init__ メソッドを修正する必要があります。

1  from tree import Node
2
3  def __init__(self, algo:str="bf"):   
元と同じなので省略
4          self.create_tree_by_df(self.root)
5          self.nodelist_by_score = []
6          self.calc_score_by_df(self.root)
7        
8  Mbtree.__init__ = __init__

行番号のないプログラム

from tree import Node

def __init__(self, algo:str="bf"):
    self.algo = algo
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
        self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
        
Mbtree.__init__ = __init__

修正箇所

from tree import Node

def __init__(self, algo:str="bf"):   
元と同じなので省略
        self.create_tree_by_df(self.root)
+       self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
        
Mbtree.__init__ = __init__

上記の修正後に、下記のプログラムを実行することで、深さ優先アルゴリズムで Mbtree クラスのインスタンスを作成した際に、nodelist_by_score とルートノードの score_index 属性が計算されることが確認できます。

mbtree_df = Mbtree(algo="df")
print(len(mbtree_df.nodelist_by_score), mbtree_df.root.score_index)

実行結果

1649837 1649836

アニメーション処理の実装

実は、上記の視覚化の処理の方針は、アニメーションを行う Mbtree_Anim を使って 深さ優先アルゴリズムによる評価値の計算の過程の 視覚化を行えるように考えて作った ものです。

Mbtree_Anim は、ゲーム木のノードの作成の経過 を以下のアニメーションで行います。

Mbtree の nodelist 属性は、ゲーム木に ノードが登録された順番 でノードを記録する
nodelist に記録されたノードの順番で、ゲーム木の部分木の選択されたノードが移り変わるアニメーションを行う
アニメーションでは、選択されたノードよりも 後に作成されたノード を暗く表示する
その判定は、nodelist の中で選択されたノードが代入された要素のインデックスと、描画するノードが ゲーム木に登録された順番 を表す id 属性を比較 することで行える

一方、これから実装する 深さ優先アルゴリズムによる評価値の計算の過程 のアニメーションは、以下のように行います。

Mbtree の nodelist_by_score 属性は、評価値の計算の過程で処理が 別のノードに移り変わった場合 と、評価値が計算された場合 のノードを順番に記録する
nodelist_by_score に記録されたノードの順番で、ゲーム木の部分木の選択されたノードが移り変わるアニメーションを行う
アニメーションのでは、選択されたノードよりも 後に評価値の計算が行われたノード を暗く表示する
その判定は、nodelist_by_score の中で選択されたノードが代入された要素のインデックスと、描画するノードの 評価値が計算された順番 を表す score_index 属性を比較 することで行える

上記の 2 つの違いは以下の通りです。

	ノードの作成の過程	評価値の計算の過程
ノードのリストの属性	`nodelist`	`nodelist_by_score`
選択されたノードのインデックスの比較対象	ノードの `id` 属性	ノードの `score_index` 属性

上記以外の処理は共通する ので、深さ優先アルゴリズムによる評価値の計算の過程の視覚化の処理を、Mbtree_Anim クラスを修正することで実装 することができます。

`init` 属性の修正

Mbtree_Anim クラスで 両方のアニメーション処理 を行うことができるようにするためには、Mbtree_Anim クラスの インスタンスを作成する際 に、どちらのアニメーションで処理を行うかを指定 できるようにする必要があります。そこで、下記のプログラムのように、__init__ メソッドに下記のような 仮引数 isscore を追加 することにします。

False が代入されている場合は、ゲーム木の生成の過程のアニメーションを、True が代入されている場合は、評価値の計算の過程のアニメーションを行う
互換性を考慮して、デフォルト値が False のデフォルト引数とする

下記はそのように __init__ メソッドを修正したプログラムです。なお、__init__ メソッドでは super() を呼び出しているので、クラスを定義し直す必要があります。

8 行目：デフォルト値を False とする仮引数 isscore を追加する
10 行目：isscore を同名の属性に代入する
14 行目：アニメーション処理を行うノードの一覧 が代入された Mbtree クラスの属性を isscore の値に応じて計算 し、nodelist 属性に代入 する。この処理によって isscore 属性の値に関わらず、共通の記述でアニメーションを行うことができる ようになる
15 行目：self.nodelist の 要素の数 を計算し、nodenum 属性に代入 しておく。この処理も、共通の記述でアニメーションを行うことができるようにするためのものである

 1  from tree import Mbtree_Anim
 2  from gui import GUI
 3  import matplotlib.pyplot as plt
 4  import matplotlib.patches as patches
 5  from ipywidgets import widgets
 6
 7  class Mbtree_Anim(GUI):
 8      def __init__(self, mbtree, isscore=False, size=0.15):
 9          self.mbtree = mbtree
10          self.isscore = isscore
11          self.size = size
12          self.width = 50
13          self.height = 64
14          self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
15          self.nodenum = len(self.nodelist)
16          super().__init__()
元と同じなので省略

行番号のないプログラム

from tree import Mbtree_Anim
from gui import GUI
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from ipywidgets import widgets

class Mbtree_Anim(GUI):
    def __init__(self, mbtree, isscore=False, size=0.15):
        self.mbtree = mbtree
        self.isscore = isscore
        self.size = size
        self.width = 50
        self.height = 64
        self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
        self.nodenum = len(self.nodelist)
        super().__init__()
        
    def create_widgets(self):
        """ウィジェットを作成する."""
        
        self.play = widgets.Play(max=self.mbtree.nodenum - 1, interval=500)
        self.frame_slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
        self.interval_slider = widgets.IntSlider(value=500, min=1, max=2000, description="interval")
        widgets.jslink((self.play, "value"), (self.frame_slider, "value"))    
        widgets.jslink((self.play, "interval"), (self.interval_slider, "value"))

        with plt.ioff():
            self.fig = plt.figure(figsize=[self.width * self.size,
                                            self.height * self.size])
            self.ax = self.fig.add_axes([0, 0, 1, 1])
        self.fig.canvas.toolbar_visible = False
        self.fig.canvas.header_visible = False
        self.fig.canvas.footer_visible = False
        self.fig.canvas.resizable = False 
        
    def display_widgets(self):
        """ウィジェットを配置して表示する."""
        
        hbox = widgets.HBox([self.play, self.frame_slider, self.interval_slider])
        display(widgets.VBox([hbox, self.fig.canvas]))
        
    def create_event_handler(self):
        """イベントハンドラを登録する."""

        def on_play_changed(changed):
            self.update_gui()
            
        self.play.observe(on_play_changed, names="value")
    
    def update_gui(self):
        """GUI の表示を更新する."""
        
        self.ax.clear()
        self.ax.set_xlim(-1, self.width - 1)
        self.ax.set_ylim(0, self.height)   
        self.ax.invert_yaxis()
        self.ax.axis("off")   
        
        self.selectednode = self.mbtree.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, ax=self.ax, maxdepth=maxdepth)
        for rect, node in self.mbtree.nodes_by_rect.items():
            if node.id > self.play.value:
                self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))

修正箇所

from tree import Mbtree_Anim
from gui import GUI
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from ipywidgets import widgets

class Mbtree_Anim(GUI):
-   def __init__(self, mbtree, size=0.15):
+   def __init__(self, mbtree, isscore=False, size=0.15):
        self.mbtree = mbtree
+       self.isscore = isscore
        self.size = size
        self.width = 50
        self.height = 64
+       self.nodelist = self.mbtree.nodelist_by_score if isscore else self.mbtree.nodelist 
+       self.nodenum = len(self.nodelist)
        super().__init__()
元と同じなので省略

`create_widgets` の修正

isscore 属性などの追加に合わせて、他のメソッドを修正する必要があります。

まず、create_widgets を下記のプログラムのように修正します。

2、3 行目：元のプログラムでは、Play と IntSlider ウィジェットの value 属性の最大値 を self.mbtree.nodelist - 1 という式で計算して設定していたが、__init__ メソッドででアニメーションを行うノードの一覧を表す list の 要素の数をnodenum 属性に代入 したので、それを使うように修正する

1  def create_widgets(self):
2      self.play = widgets.Play(max=self.nodenum - 1, interval=500)
3      self.frame_slider = widgets.IntSlider(max=self.nodenum - 1, description="frame")
元と同じなので省略
4
5  Mbtree_Anim.create_widgets = create_widgets

行番号のないプログラム

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

    with plt.ioff():
        self.fig = plt.figure(figsize=[self.width * self.size,
                                        self.height * self.size])
        self.ax = self.fig.add_axes([0, 0, 1, 1])
    self.fig.canvas.toolbar_visible = False
    self.fig.canvas.header_visible = False
    self.fig.canvas.footer_visible = False
    self.fig.canvas.resizable = False 

Mbtree_Anim.create_widgets = create_widgets

修正箇所

def create_widgets(self):
-   self.play = widgets.Play(max=self.mbtree.nodenum - 1, interval=500)
+   self.play = widgets.Play(max=self.nodenum - 1, interval=500)
-   self.frame_slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
+   self.frame_slider = widgets.IntSlider(max=self.nodenum - 1, description="frame")
元と同じなので省略

Mbtree_Anim.create_widgets = create_widgets

`update_gui` の修正

次に、update_gui を下記のプログラムのように修正します。

8 行目：選択されたのノード を、self.nodelist から選択する ように修正する
10 行目：暗い色で表示するかどうかを判定するために用いるノードの属性を self.isscore の値に応じて計算 し、index に代入する
11 行目：選択されたのノードのインデックスを表す self.play.value と index と比較することで、ノードを暗く表示するかを判定するように修正する

 1  def update_gui(self):
 2      self.ax.clear()
 3      self.ax.set_xlim(-1, self.width - 1)
 4      self.ax.set_ylim(0, self.height)   
 5      self.ax.invert_yaxis()
 6      self.ax.axis("off")   
 7   
 8      self.selectednode = self.nodelist[self.play.value]
元と同じなので省略
 9      for rect, node in self.mbtree.nodes_by_rect.items():
10          index = node.score_index if self.isscore else node.id
11          if index > self.play.value:
12              self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))
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(0, self.height)   
    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, ax=self.ax, maxdepth=maxdepth)
    for rect, node in self.mbtree.nodes_by_rect.items():
        index = node.score_index if self.isscore else node.id
        if index > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))

Mbtree_Anim.update_gui = update_gui

修正箇所

def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(0, self.height)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
-   self.selectednode = self.mbtree.nodelist[self.play.value]
+   self.selectednode = self.nodelist[self.play.value]
元と同じなので省略
    for rect, node in self.mbtree.nodes_by_rect.items():
-       if node.id > self.play.value:
+       index = node.score_index if self.isscore else node.id
+       if index > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))

Mbtree_Anim.update_gui = update_gui

上記の修正後に、下記のプログラムを実行すると、実行結果のように評価値を生成する過程を表すアニメーションが表示されます。

mbtree_anim = Mbtree_Anim(mbtree_df, isscore=True)

実行結果（0 ~ 30 フレームまでのアニメーションの繰り返しです）

Mbtree_Anim の改良

Mbtree_Anim にはいくつかの欠点があるので、改良することにします。どのような欠点があるかについて少し考えてみて下さい。

コマ送りとコマ戻しの機能の実装

ゲーム木の生成の過程のアニメーションの場合は、処理の流れを実感することが大事だと思ったので、アニメーションの ON/OFF と、アニメーションの速度の調整の機能のみを実装しましたが、自分でアニメーションのフレームを前後に移動 することができれば、処理の流れをより確認しやすくなります。

そこで、Mbtree_Anim に、フレームを前後に移動 する、いわゆる コマ送りとコマ戻し の機能を実装することにします。具体的には一つ前のフレームに戻るボタンと、一つ後のフレームに進むボタンを追加します。

それぞれのボタンに表示する文字は、〇×ゲームの GUI と同様に < と > にし、Play ウィジェットの右に配置することにします。

`create_widgets` の修正

まず、create_widgets を下記のプログラムのように修正します。

2、3 行目：create_button メソッドを使って、2 つのボタンを作成する

1  def create_widgets(self):
2      self.play = widgets.Play(max=self.nodenum - 1, interval=500)
3      self.prev_button = self.create_button("<", width=30)
4      self.next_button = self.create_button(">", width=30)
元と同じなので省略
5
6  Mbtree_Anim.create_widgets = create_widgets

行番号のないプログラム

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

    with plt.ioff():
        self.fig = plt.figure(figsize=[self.width * self.size,
                                        self.height * self.size])
        self.ax = self.fig.add_axes([0, 0, 1, 1])
    self.fig.canvas.toolbar_visible = False
    self.fig.canvas.header_visible = False
    self.fig.canvas.footer_visible = False
    self.fig.canvas.resizable = False 

Mbtree_Anim.create_widgets = create_widgets

修正箇所

def create_widgets(self):
    self.play = widgets.Play(max=self.nodenum - 1, interval=500)
+   self.prev_button = self.create_button("<", width=30)
+   self.next_button = self.create_button(">", width=30)
元と同じなので省略

Mbtree_Anim.create_widgets = create_widgets

`display_widgets` の修正

次に、display_widgets を下記のプログラムのように修正します。

2 行目：Play ウィジェットの右に、< ボタンと > ボタンを並べて配置する

1  def display_widgets(self):
2      hbox = widgets.HBox([self.play, self.prev_button, self.next_button, self.frame_slider, self.interval_slider])
3      display(widgets.VBox([hbox, self.fig.canvas])) 
4
5  Mbtree_Anim.display_widgets = display_widgets

行番号のないプログラム

def display_widgets(self):
    hbox = widgets.HBox([self.play, self.prev_button, self.next_button, self.frame_slider, self.interval_slider])
    display(widgets.VBox([hbox, self.fig.canvas])) 

Mbtree_Anim.display_widgets = display_widgets

修正箇所

def display_widgets(self):
-   hbox = widgets.HBox([self.play, self.frame_slider, self.interval_slider])
+   hbox = widgets.HBox([self.play, self.prev_button, self.next_button, self.frame_slider, self.interval_slider])
    display(widgets.VBox([hbox, self.fig.canvas])) 

Mbtree_Anim.display_widgets = display_widgets

`create_event_handler` の修正

次に、create_event_handler を下記のプログラムのように修正します。なお、キー入力による操作や、ヘルプボタンは省略しました。必要だと思った方は実装して下さい。

5 ~ 7 行目：< ボタンをクリックした際に実行するイベントハンドラを定義する。行う処理は、Play ウィジェットの value 属性を 1 減らし、update_gui で表示を更新する
9 ~ 11 行目：> ボタンをクリックした際に実行するイベントハンドラを定義する。行う処理は、Play ウィジェットの value 属性を 1 f増やし、update_gui で表示を更新する
13、14 行目：ボタンとイベントハンドラを結び付ける

 1  def create_event_handler(self):
 2      def on_play_changed(changed):
 3          self.update_gui()
 4       
 5      def on_prev_button_clicked(b=None):
 6          self.play.value -= 1
 7          self.update_gui()
 8       
 9      def on_next_button_clicked(b=None):
10          self.play.value += 1
11          self.update_gui()
12
13      self.prev_button.on_click(on_prev_button_clicked)
14      self.next_button.on_click(on_next_button_clicked)
15
16      self.play.observe(on_play_changed, names="value")
17    
18  Mbtree_Anim.create_event_handler = create_event_handler

行番号のないプログラム

def create_event_handler(self):
    def on_play_changed(changed):
        self.update_gui()
        
    def on_prev_button_clicked(b=None):
        self.play.value -= 1
        self.update_gui()
        
    def on_next_button_clicked(b=None):
        self.play.value += 1
        self.update_gui()

    self.prev_button.on_click(on_prev_button_clicked)
    self.next_button.on_click(on_next_button_clicked)

    self.play.observe(on_play_changed, names="value")
    
Mbtree_Anim.create_event_handler = create_event_handler

修正箇所

def create_event_handler(self):
    def on_play_changed(changed):
        self.update_gui()
        
+   def on_prev_button_clicked(b=None):
+       self.play.value -= 1
+       self.update_gui()
        
+   def on_next_button_clicked(b=None):
+       self.play.value += 1
+       self.update_gui()

+   self.prev_button.on_click(on_prev_button_clicked)
+   self.next_button.on_click(on_next_button_clicked)

    self.play.observe(on_play_changed, names="value")
    
Mbtree_Anim.create_event_handler = create_event_handler

`update_gui` の修正

最後に、update_gui を下記のプログラムのように修正します。

2、3 行目：set_button_status メソッドを使って、最初のフレームで < ボタンを灰色にして押せないようにする
4、5 行目：最後のフレームで > ボタンを灰色にして押せないようにする

1  def update_gui(self):
元と同じなので省略
2      disabled = self.play.value == 0
3      self.set_button_status(self.prev_button, disabled=disabled)
4      disabled = self.play.value == self.nodenum - 1
5      self.set_button_status(self.next_button, disabled=disabled)
6
7  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(0, self.height)   
    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, ax=self.ax, maxdepth=maxdepth)
    for rect, node in self.mbtree.nodes_by_rect.items():
        index = node.score_index if self.isscore else node.id
        if index > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width, height=rect.height, fc="black", alpha=0.5))

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

上記の修正後に、下記のプログラムを実行すると、実行結果のように < と > ボタンが表示されるようになります。また、< と > ボタンが正しく動作することを確認して下さい。

mbtree_anim = Mbtree_Anim(mbtree_df, isscore=True)

実行結果

選択されたのノードの表示の改良

評価値の経過を表示するアニメーションでは、上図のように、選択されたノードの 赤い枠が暗く表示されてしまう ため、あまり 目立たなくなってしまう という問題があります。これは、選択されたノードを暗く表示する際に、ゲーム盤の上に半透明の黒い図形を重ねて表示したため、選択されたノードの 赤い枠も暗く表示されてしまう からです。

この問題はゲーム木の作成の過程を表示するアニメーションでは、選択されたノードは暗く表示されることがないのでこのような現象は発生しません。

本記事では、update_gui で選択されたノードに対して暗く表示する処理を行った後で、改めて赤い枠を表示する ことでこの問題に対処することにします。また、その際に以下のような工夫を行いました。他にも様々な対処法があると思いますので、もっと良い方法を思いついた人は、その方法を実装してみて下さい。

元と同じ太さで赤枠を表示してもあまり目立たないので、赤枠の太さを太くして表示する
暗く表示しない場合の赤枠の太さを元のままにすると、見た目が不自然 だったので、赤枠の太さは 常に太くして表示する

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

7 ~ 9 行目：選択されたノードに対して太さが 2 の赤枠を表示する

 1  def update_gui(self):
元と同じなので省略
 2      for rect, node in self.mbtree.nodes_by_rect.items():
 3          index = node.score_index if self.isscore else node.id
 4          if index > self.play.value:
 5              self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
 6                                                   height=rect.height, fc="black", alpha=0.5))
 7         if node is self.selectednode:
 8             self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
 9                                height=rect.height, ec="red", fill=False, lw=2))
元と同じなので省略
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(0, self.height)   
    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,
                             ax=self.ax, maxdepth=maxdepth)
    for rect, node in self.mbtree.nodes_by_rect.items():
        index = node.score_index if self.isscore else node.id
        if index > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
                                                     height=rect.height, fc="black", alpha=0.5))
        if node is self.selectednode:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
                                                     height=rect.height, ec="red", fill=False, lw=2))

    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):
元と同じなので省略
    for rect, node in self.mbtree.nodes_by_rect.items():
        index = node.score_index if self.isscore else node.id
        if index > self.play.value:
            self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
                                                     height=rect.height, fc="black", alpha=0.5))
+       if node is self.selectednode:
+           self.ax.add_artist(patches.Rectangle(xy=(rect.x, rect.y), width=rect.width,
+                                                height=rect.height, ec="red", fill=False, lw=2))
元と同じなので省略

Mbtree_Anim.update_gui = update_gui

上記の修正後に、下記のプログラムを実行すると、実行結果のように赤枠が明るい色で太く表示されるようになります。

mbtree_anim = Mbtree_Anim(mbtree_df, isscore=True)

実行結果

幅優先アルゴリズムによる評価値の計算の過程の視覚化

せっかくなので、幅優先アルゴリズム による評価値の計算の過程の視覚化も行うことにします。幅優先アルゴリズムでの評価値の計算は、以下の手順で行われます。

深さの浅い順に各深さのノードの一覧を計算する
深さの深い順に各深さのノードの評価値を計算する

前者の処理は、create_tree_by_bf で行われている ので、calc_score_by_bf では 後者の処理のみ を行っていますが、幅優先アルゴリズムによる評価値の過程の視覚化では、前者の処理も視覚化を行う必要があります。

前者の処理 で処理が行われる ノードの順番 は、幅優先アルゴリズムでゲーム木の ノードを作成する順番と全く同じ なので、その順番は幅優先アルゴリズムで作成した Mbtree の nodelist 属性に代入されています。従って、前者の処理で行われるノードに対する処理の順番の計算は、nodelist_by_score に nodelist の値をコピーすれば良い ことがわかります。

後者の処理 では、ノードの処理を行う際に 必ずそのノードの評価値が計算 されます。そのため、後者の処理で nodelist_by_score に登録するノードは すべて評価値が計算されたことを表すノード になります。

上記から、calc_score_by_bf は下記のプログラムのように修正します。

2 行目：nodelist 属性の list を、スライス表記で nodelist_by_score にコピーする
18 行目：ノードの評価値を計算した後で、nodelist_by_score にそのノードを追加する
19 行目：追加したノードのインデックスをノードの score_index 属性に代入する

 1  def calc_score_by_bf(self):
 2      self.nodelist_by_score = self.nodelist[:]
 3      for nodelist in reversed(self.nodelist_by_depth):
 4          for node in nodelist:
 5              if node.mb.status == Marubatsu.CIRCLE:
 6                  node.score = 1
 7              elif node.mb.status == Marubatsu.DRAW:
 8                  node.score = 0
 9              elif node.mb.status == Marubatsu.CROSS:
10                  node.score = -1
11              else:
12                  score_list = [childnode.score for childnode in node.children]
13                  if node.mb.move_count % 2 == 0:
14                      score = max(score_list)
15                  else:
16                      score = min(score_list)
17                  node.score = score
18              self.nodelist_by_score.append(node)
19              node.score_index = len(self.nodelist_by_score) - 1
20    
21  Mbtree.calc_score_by_bf = calc_score_by_bf

行番号のないプログラム

def calc_score_by_bf(self):
    self.nodelist_by_score = self.nodelist[:]
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
                score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score
            self.nodelist_by_score.append(node)
            node.score_index = len(self.nodelist_by_score) - 1
    
Mbtree.calc_score_by_bf = calc_score_by_bf

修正箇所

def calc_score_by_bf(self):
+   self.nodelist_by_score = self.nodelist[:]
    for nodelist in reversed(self.nodelist_by_depth):
        for node in nodelist:
            if node.mb.status == Marubatsu.CIRCLE:
                node.score = 1
            elif node.mb.status == Marubatsu.DRAW:
                node.score = 0
            elif node.mb.status == Marubatsu.CROSS:
                node.score = -1
            else:
                score_list = [childnode.score for childnode in node.children]
                if node.mb.move_count % 2 == 0:
                    score = max(score_list)
                else:
                    score = min(score_list)
                node.score = score
+           self.nodelist_by_score.append(node)
+           node.score_index = len(self.nodelist_by_score) - 1
    
Mbtree.calc_score_by_bf = calc_score_by_bf

上記の修正後に、下記のプログラムを実行すると、実行結果のように幅優先アルゴリズムによる評価値の計算の過程のアニメーションが表示されるようになります。

mbtree_bf = Mbtree.load("bfscore")
mbtree_bf.calc_score_by_bf()
mbtree_anim = Mbtree_Anim(mbtree_bf, isscore=True)

前半の 0 ~ 549945 フレームでは下図のように、深さの浅い順にノードの処理が行われます。また、その際に評価値が計算されることはありません。

実行結果（0 ~ 30 フレームまでのアニメーションの繰り返しです）

後半の 549946 フレーム以降では、深さの深い順に、評価値の計算を行いながらノードの処理が行われます。なお、フレームを表す IntSlider の値をクリックすることで、キーボードから IntSlider の値を直接編集することができるので、実際に 549946 フレームの前後のフレームを表示して確認してみて下さい。

実行結果（549946 ~ 549976 フレームまでのアニメーションの繰り返しです）

ファイルの保存

最後に、下記のプログラムで mbtree_bf と mbtree_df のデータをファイルに保存します。なお、下記では、今回の marubatsu.ipynb のプログラムを実行する際に必要となるので、"bfscore_new" という名前で保存しましたが、古い "bfscore.mbtree" と "dfscore.mbtree" のファイルはもう必要がないので、次回以降の記事では、今回保存した "bfscore_new.mbtree" のファイル名を "bfscore.mbtree" に変更することにします。

mbtree_bf.save("bfscore_new")
mbtree_df.save("dfscore_new")

実行結果

save completed.
save completed.

互換性の確認

今回の Mbtree_Anim の修正によって、ゲーム木の生成の過程のアニメーションが正しく動作しなくなっている可能性があるので、下記のプログラムで確認します。実行結果は省略しますが、正しく動作することが確認できます。

mbtree_anim = Mbtree_Anim(mbtree_bf)
mbtree_anim = Mbtree_Anim(mbtree_df)

今回の記事のまとめ

今回の記事では、深さ優先アルゴリズムと、幅優先アルゴリズムの両方で、ゲーム木の評価値を計算する過程をアニメーションで視覚化しました。

次回の記事では、

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

今回の記事で作成した mbtree_bf と mbtree_df の中身は、以前にファイルに保存したデータと全く同じなので、改めてファイルに保存することはしません。

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
tree_new.py	今回の記事で更新した tree.py
bfscore_new.mbtree	幅優先探索アルゴリズムで作成した、評価値を含むゲーム木の保存ファイル
dfscore_new.mbtree	深さ優先探索アルゴリズムで作成した、評価値を含むゲーム木の保存ファイル

次回の記事