目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| 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 | 深さ優先探索アルゴリズムで作成した、評価値を含むゲーム木の保存ファイル |
次回の記事