目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| test.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義。現在は gui_play のみ定義されている |
| tree.py | ゲーム木に関する Node、Mbtree クラスの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
今回の記事の内容
前回の記事では、draw_subtree メソッドで表示する 部分木を動的に作成する処理 の実装を開始しました。今回の記事ではその実装の続きを行います。
また、今回の記事では、これまでのプログラムに存在していたが、明るみに出ていなかった 潜在的なバグ がいくつか発生します。このような潜在的なバグは、プログラムに 新しい機能を実装した際に発生 し、しばらくたった後で発覚する ことが良くあるので、その実例として紹介します。
最善手を着手し続けた場合の局面の表示
Mbtree_GUI クラスで表示する部分木は、下記のプログラムの実行結果のように 最善手を着手し続けた場合の局面 を灰色の背景の上に表示しますが、create_subtree で作成した部分木には最善手を着手し続けた場合の局面のノードは 作成されていない ので、 draw_subtree で最善手を着手し続けた場合の局面を 描画することはできません。
from tree import Mbtree, Mbtree_GUI
mbtree = Mbtree.load("../data/aidata")
Mbtree_GUI(mbtree)
実行結果
従って、Mbtree_GUI クラスで表示する部分木のデータを create_subtree で作成して表示するためには、最善手を着手し続けた場合の局面のノードを作成する ように create_subtree を修正する必要があります。
最善手を着手し続けた場合の局面のノードを作成するためには、各ノードの最善手の一覧の情報をノードの bestmoves 属性に代入するが必要 があります。以前の記事で 局面と最善手の対応表を dict で表現したデータを計算してファイルに保存済 なので、それを使ってノードの最善手の一覧を計算することができます。また、そのデータを保存した bestmoves_by_board.dat や bestmoves_by_board_shortest_victory.dat などの ファイルサイズは約 20 KB と小さい のでファイルから 読み込む際に時間はほとんどかかりません。
実際に筆者のパソコンで下記のプログラムで %%timeit を使ってファイルから bestmoves_by_board.dat を読み込む処理の時間を計測した所、実行結果のように数ミリ秒で実行できることが確認できました。
%%timeit
from util import load_bestmoves
load_bestmoves("../data/bestmoves_by_board.dat")
実行結果
5.48 ms ± 327 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Node クラスの __init__ メソッドの修正
下記のプログラムのように Node クラスの __init__ メソッドを修正することで、ノードの作成時に最善手を計算して bestmoves 属性に代入 することができます。
-
3 行目：デフォルト値を
Noneとする、局面と最善手の対応表のデータを代入する仮引数bestmoves_by_boardを追加する -
4、5 行目：
bestmoves_by_boardがNoneでない場合に、その値とゲーム盤を文字列に変換した値を利用して最善手の一覧を計算し、bestmoves属性に代入する
1 from tree import Node
2
3 def __init__(self, mb, parent=None, depth=0, bestmoves_by_board=None):
元と同じなので省略
4 if bestmoves_by_board is not None:
5 self.bestmoves = bestmoves_by_board[self.mb.board_to_str()]
6
7 Node.__init__ = __init__
行番号のないプログラム
from tree import Node
def __init__(self, mb, parent=None, depth=0, bestmoves_by_board=None):
self.id = Node.count
Node.count += 1
self.mb = mb
self.parent = parent
self.depth = depth
self.children = []
self.children_by_move = {}
if bestmoves_by_board is not None:
self.bestmoves = bestmoves_by_board[self.mb.board_to_str()]
Node.__init__ = __init__
修正箇所
from tree import Node
-def __init__(self, mb, parent=None, depth=0):
+def __init__(self, mb, parent=None, depth=0, bestmoves_by_board=None):
元と同じなので省略
+ if bestmoves_by_board is not None:
+ self.bestmoves = bestmoves_by_board[self.mb.board_to_str()]
Node.__init__ = __init__
Node クラスの calc_children メソッドの修正
Node クラスの __init__ メソッドの修正にあわせて Node クラスのインスタンスを作成する処理を修正 する必要があります。まず、子ノードの一覧を作成する Node クラスの calc_children メソッドを下記のプログラムのように修正します。
-
3 行目：デフォルト値を
Noneとする仮引数bestmoves_by_boardを追加する -
9 行目：
Nodeクラスのインスタンスを作成する際 にキーワード引数bestmoves_by_board=bestmoves_by_boardを記述する ように修正する
1 from copy import deepcopy
2
3 def calc_children(self, bestmoves_by_board=None):
4 self.children = []
5 for x, y in self.mb.calc_legal_moves():
6 childmb = deepcopy(self.mb)
7 childmb.move(x, y)
8 self.insert(Node(childmb, parent=self, depth=self.depth + 1,
9 bestmoves_by_board=bestmoves_by_board))
10
11 Node.calc_children = calc_children
行番号のないプログラム
from copy import deepcopy
def calc_children(self, bestmoves_by_board=None):
self.children = []
for x, y in self.mb.calc_legal_moves():
childmb = deepcopy(self.mb)
childmb.move(x, y)
self.insert(Node(childmb, parent=self, depth=self.depth + 1,
bestmoves_by_board=bestmoves_by_board))
Node.calc_children = calc_children
修正箇所
from copy import deepcopy
-def calc_children(self):
+def calc_children(self, bestmoves_by_board=None):
self.children = []
for x, y in self.mb.calc_legal_moves():
childmb = deepcopy(self.mb)
childmb.move(x, y)
- self.insert(Node(childmb, parent=self, depth=self.depth + 1))
+ self.insert(Node(childmb, parent=self, depth=self.depth + 1,
+ bestmoves_by_board=bestmoves_by_board))
Node.calc_children = calc_children
Mbtree クラスの create_subtree の修正
次に、Mbtree クラスの create_subtree の中で ノードを作成する処理を修正 します。
局面と最善手の対応表 のデータは、create_subtree の仮引数 subtree に代入する dict の bestmoves_by_board というキーの値に代入することにし、その値を使ってノードを作成するように修正します。
また、これまでは maxdepth までの深さのノードを作成しましたが、maxdepth より深いノード として、最善手を着手しつづけた局面を表すノードを作成する ように修正する必要があります。
下記は、そのように修正したプログラムです。
-
4 行目：
bestmoves_by_boardに局面と最善手の対応表のデータを代入する -
5、8、10 行目：ノードを作成する際と、子ノードの一覧を作成する際に、キーワード引数
bestmoves_by_board=bestmoves_by_boardを記述するように修正する -
6 行目：繰り返しの条件式から、
depth < maxdepthの条件を削除する -
9 行目：10 行目の処理は、深さが
maxdepth未満の場合に行う処理なので、elseをelif depth < maxdepthに修正する -
11 ~ 20 行目：
depthがmaxdepth以上の場合の処理を記述する - 12 行目：合法手が存在する、ゲーム中の場合のみ処理を行うようにする
-
13 行目：
nodeの局面のデータを複製してchildmbに代入する -
14 ~ 16 行目：
nodeの局面を表す文字列を計算し、bestmoves_by_boardを使って、その局面の最初の最善手を計算してchildmbに着手を行う - 17 ~ 19 行目：最善手を着手した局面のノードを作成し、子ノードに追加する
1 from marubatsu import Marubatsu
2
3 def create_subtree(self):
4 bestmoves_by_board = self.subtree["bestmoves_by_board"]
5 self.root = Node(Marubatsu(), bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
6 while len(nodelist) > 0:
元と同じなので省略
7 childnode = Node(childmb, parent=node, depth=depth+1,
8 bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
9 elif depth < maxdepth:
10 node.calc_children(bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
11 else:
12 if node.mb.status == Marubatsu.PLAYING:
13 childmb = deepcopy(node.mb)
14 board_str = node.mb.board_to_str()
15 x, y = bestmoves_by_board[board_str][0]
16 childmb.move(x, y)
17 childnode = Node(childmb, parent=node, depth=depth+1,
18 bestmoves_by_board=bestmoves_by_board)
19 node.insert(childnode)
20 childnodelist.append(childnode)
21 nodelist = childnodelist
22 depth += 1
23
24 Mbtree.create_subtree = create_subtree
行番号のないプログラム
from marubatsu import Marubatsu
def create_subtree(self):
bestmoves_by_board = self.subtree["bestmoves_by_board"]
self.root = Node(Marubatsu(), bestmoves_by_board=bestmoves_by_board)
depth = 0
nodelist = [self.root]
centermb = self.subtree["centermb"]
centerdepth = centermb.move_count
records = centermb.records
maxdepth = self.subtree["maxdepth"]
while len(nodelist) > 0:
childnodelist = []
for node in nodelist:
if depth < centerdepth - 1:
childmb = deepcopy(node.mb)
x, y = records[depth + 1]
childmb.move(x, y)
childnode = Node(childmb, parent=node, depth=depth+1,
bestmoves_by_board=bestmoves_by_board)
node.insert(childnode)
childnodelist.append(childnode)
elif depth < maxdepth:
node.calc_children(bestmoves_by_board=bestmoves_by_board)
if depth == centerdepth - 1:
for move, childnode in node.children_by_move.items():
if move == records[depth + 1]:
self.centernode = childnode
childnodelist.append(self.centernode)
else:
if childnode.mb.status == Marubatsu.PLAYING:
childnode.children.append(None)
else:
childnodelist += node.children
else:
if node.mb.status == Marubatsu.PLAYING:
childmb = deepcopy(node.mb)
board_str = node.mb.board_to_str()
x, y = bestmoves_by_board[board_str][0]
childmb.move(x, y)
childnode = Node(childmb, parent=node, depth=depth+1,
bestmoves_by_board=bestmoves_by_board)
node.insert(childnode)
childnodelist.append(childnode)
nodelist = childnodelist
depth += 1
Mbtree.create_subtree = create_subtree
修正箇所
from marubatsu import Marubatsu
def create_subtree(self):
+ bestmoves_by_board = self.subtree["bestmoves_by_board"]
- self.root = Node(Marubatsu())
+ self.root = Node(Marubatsu(), bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
maxdepth = self.subtree["maxdepth"]
- while len(nodelist) > 0 and depth < maxdepth:
+ while len(nodelist) > 0:
元と同じなので省略
- childnode = Node(childmb, parent=node, depth=depth+1)
+ childnode = Node(childmb, parent=node, depth=depth+1,
+ bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
- else:
+ elif depth < maxdepth:
- node.calc_children()
+ node.calc_children(bestmoves_by_board=bestmoves_by_board)
元と同じなので省略
+ else:
+ if node.mb.status == Marubatsu.PLAYING:
+ childmb = deepcopy(node.mb)
+ board_str = node.mb.board_to_str()
+ x, y = bestmoves_by_board[board_str][0]
+ childmb.move(x, y)
+ childnode = Node(childmb, parent=node, depth=depth+1,
+ bestmoves_by_board=bestmoves_by_board)
+ node.insert(childnode)
+ childnodelist.append(childnode)
nodelist = childnodelist
depth += 1
Mbtree.create_subtree = create_subtree
上記の修正後に、下記のプログラムを実行して以下のような部分木を作成して draw_subtree で表示しようとすると、実行結果のような エラーが発生 します。このエラーの原因について少し考えてみて下さい。なお、深さが 3 以降のノードに最善手を着手し続けた場合の局面を表示するためには draw_subtree を呼び出す際に、キーワード引数 show_bestmove=True を記述する必要がある 点に注意して下さい。
- (0, 0)、(1, 0) の順に着手を行った局面を中心とする部分木
- 深さが 3 以降のノードは最善手を着手し続けた場合の局面を表す
from util import load_bestmoves
mb = Marubatsu()
mb.move(0, 0)
mb.move(1, 0)
maxdepth = 3
bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": maxdepth,
"bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth,
show_bestmove=True)
実行結果
略
File c:\Users\ys\ai\marubatsu\121\marubatsu.py:973, in Marubatsu_GUI.draw_board(ax, mb, show_result, score, bc, bw, darkness, dx, dy, lw)
971 if score is None and mb.status == Marubatsu.PLAYING:
972 bgcolor = "white"
--> 973 elif score > 0 or mb.status == Marubatsu.CIRCLE:
974 bgcolor = "lightcyan"
975 elif score < 0 or mb.status == Marubatsu.CROSS:
TypeError: '>' not supported between instances of 'NoneType' and 'int'
%%timeit が先頭に記述されているセルの中で行ったインポートやローカル変数などの名前は、そのセルの中だけでしか利用できません。そのため、先程 %%timeit を先頭に記述したセルの中で load_bestmoves をインポートしましたが、上記のプログラムで改めて load_bestmoves をインポートする必要があります。
エラーの原因の検証
エラーメッセージから、このエラーは Marubatsu_GUI クラスの draw_board メソッドで発生したことがわかります。また、このエラーメッセージは、「> という演算子は None 型と整数型（int）の演算をサポートしていない」という意味です。従って、score に None が代入 された状態で score > 0 という式を計算しようとした ことが原因でエラーが発生した可能性が高いことがわかります。そこで、draw_board の仮引数 score に None が代入されるか どうかを検証することにします。
draw_board メソッドは、Node クラスの draw_node メソッド内の下記のプログラムで呼び出されます。
1 def draw_node(略):
略
2 Marubatsu_GUI.draw_board(ax, self.mb, show_result=True,
3 score=getattr(self, "score", None), bc=bc, darkness=darkness, lw=lw, dx=dx, dy=y)
略
3 行目の キーワード引数 score に記述されている getattr(self, "score", None) は以前の記事 で説明したように、以下のような処理を行います。
- Node クラスのインスタンスを表す
selfにscore属性が 存在する場合はscore属性の値を計算 する -
score属性が 存在しない場合はNoneを計算 する
calc_subtree メソッドで 部分木を作成する際 に、ノードの評価値の計算は行っていない ので、ノードの score 属性は存在しません。そのため、上記の 2 行目で draw_board を呼び出すと、仮引数 score には確かに None が代入される ことが確認できました。
次に、仮引数 score に None が代入された場合 に draw_board で行われる処理を検証します。draw_board では下記のプログラムによって score と mb.status の値に応じてゲーム盤の背景色を変更する処理を行っています。
1 def draw_board(略)
略
2 # 結果によってゲーム盤の背景色を変更する
3 if show_result:
4 if score is None and mb.status == Marubatsu.PLAYING:
5 bgcolor = "white"
6 elif score > 0 or mb.status == Marubatsu.CIRCLE:
7 bgcolor = "lightcyan"
8 elif score < 0 or mb.status == Marubatsu.CROSS:
9 bgcolor = "lavenderblush"
10 else:
11 bgcolor = "lightyellow"
12 rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
13 height=mb.BOARD_SIZE, fc=bgcolor)
14 ax.add_patch(rect)
略
mb.status は、ゲームの状態を表す属性なので、その中には ゲームの状態を表す 4 種類のデータのいずれかが代入 されます。下記は、score に None が代入 されている場合に mb.status に に代入される可能性がある 4 種類のそれぞれの値に対して 4 行目の条件式を計算したものです。下記の表から、score が None であり、なおかつ ゲームの決着がついている場合 に 4 行目の条件式が False になり、その後の 6 行目で score > 0 が実行されて エラーが発生する ことが確認できました。
score |
mb.status |
条件式の値 |
|---|---|---|
None |
Marubatsu.PLAYING |
True |
None |
Marubatsu.CIRCLE |
False |
None |
Marubatsu.DRAW |
False |
None |
Marubatsu.CROSS |
False |
このバグは、score に None が代入されている場合の処理を筆者が 間違って記述してしまった ことが原因です。
潜在的なバグ
draw_board メソッドにこのような バグが存在するにも関わらず、このバグが これまで発生しなかった理由 は、これまでの記事ではノードの score 属性に評価値を計算済の状態 で draw_board を呼び出していたからです。
このような、バグが存在するにも関わらず、そのバグが発生する条件が満たされないという理由で 見つかっていないようなバグ を 潜在的なバグ と呼び、これまでの記事でも後から発見された潜在的なバグは数多くありました。
厳密に言えば見つかってないバグはすべて潜在的なバグですが、すぐに発見できるような単純なバグのことは潜在的なバグとは呼ばないのではないかと思います。
潜在的なバグは、プログラムの機能を修正した際に良く発生します。また、潜在的なバグは 長い間発見されない ことが多く、今回の記事のように、それまでとは異なる方法でプログラムを実行した際に発覚することが良くあります。
そのため、プログラムの機能を修正した際には、潜在的なバグが新しく発生していないかどうかを確認する ことが重要になります。本記事でも最初の頃はプログラムの修正を行うたびにそのような確認を良く行っていました。特に〇×ゲームの判定を行う judge 関数を実装する際には、かなり念入りに 関数のテスト を行いました。
ただし、最近の記事では以前よりもその確認作業が減っています。その理由は、プログラムの規模が大きくなる とすべての場合で処理が正しく行われるかを 確認することが現実的に困難になる からです。そのため、このバグのように潜在的なバグの発生に気づかずに、後になってバグの存在に気が付くことがよくあります。実際に、今回の記事で紹介する潜在的なバグは、潜在的なバグを紹介するために意図的に記述したものではありません。いずれも筆者の不注意で発生したもので、今回の記事を執筆するまでは筆者はその存在に気づいていませんでした。
なお、どれだけ頑張ってテストを行っても 潜在的なバグの発生を 0 にすることはほぼ不可能 です。潜在的なバグが存在する可能性が常にある ことを忘れないようにして下さい。
企業などで作成する大規模なプログラムでは、あらかじめ厳密な仕様を作成してからプログラミングを行うため、プログラムを修正するたびに、修正したプログラムが仕様通りに動作するかの厳密なテストを行うのが一般的です。それに対して、〇×ゲームのような個人で作成する、その場の思い付きで仕様をどんどん変えていくような小規模なプログラムでは、厳密な確認を行ってもすぐに仕様が変わる可能性が高いので、確認作業を簡易的に済ませることが多いと思います。
バグの修正方法
このバグの原因は、score に None が代入されている場合に score > 0 という演算を行っている ことなので、下記のプログラムのように、and 演算子 を使って score に None が代入されていない場合のみ score > 0 の演算を行うようにすることでバグを修正することができます。
-
10、12 行目：
score > 0やscore < 0の前に、scoreがNoneでないという条件を加える。and 演算子のほうが or 演算子よりも 優先順位 が高いので、 () を記述する必要はないが、わかりづらいので記述した。同様に、is not 演算子のほうが and 演算子よりも優先順位が高いことがわかりづらいと感じた場合は条件式の前半部分を((score is not None) and score > 0)のように記述すると良い
1 from marubatsu import Marubatsu_GUI
2 import matplotlib.patches as patches
3
4 def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
5 # 結果によってゲーム盤の背景色を変更する
6 if show_result:
7 if score is None:
8 if score is None and mb.status == Marubatsu.PLAYING:
9 bgcolor = "white"
10 elif (score is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
11 bgcolor = "lightcyan"
12 elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
13 bgcolor = "lavenderblush"
14 else:
15 bgcolor = "lightyellow"
元と同じなので省略
16
17 Marubatsu_GUI.draw_board = draw_board
行番号のないプログラム
from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches
def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
# 結果によってゲーム盤の背景色を変更する
if show_result:
if score is None and mb.status == Marubatsu.PLAYING:
bgcolor = "white"
elif (score is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
bgcolor = "lightcyan"
elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
bgcolor = "lavenderblush"
else:
bgcolor = "lightyellow"
rect = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
height=mb.BOARD_SIZE, fc=bgcolor)
ax.add_patch(rect)
# ゲーム盤の枠を描画する
for i in range(1, mb.BOARD_SIZE):
ax.plot([dx, dx + mb.BOARD_SIZE], [dy + i, dy + i], c="k", lw=lw) # 横方向の枠線
ax.plot([dx + i, dx + i], [dy, dy + mb.BOARD_SIZE], c="k", lw=lw) # 縦方向の枠線
# ゲーム盤のマークを描画する
for y in range(mb.BOARD_SIZE):
for x in range(mb.BOARD_SIZE):
color = "red" if (x, y) == mb.last_move else "black"
Marubatsu_GUI.draw_mark(ax, dx + x, dy + y, mb.board[x][y], color, lw=lw)
# darkness 0 より大きい場合は、半透明の黒い正方形を描画して暗くする
if darkness > 0:
ax.add_artist(patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
height=mb.BOARD_SIZE, fc="black", alpha=darkness))
# bc が None でない場合はその色で bw の太さで外枠を描画する
if bc is not None:
frame = patches.Rectangle(xy=(dx, dy), width=mb.BOARD_SIZE,
height=mb.BOARD_SIZE, ec=bc, fill=False, lw=bw)
ax.add_patch(frame)
Marubatsu_GUI.draw_board = draw_board
修正箇所
from marubatsu import Marubatsu_GUI
import matplotlib.patches as patches
def draw_board(ax, mb, show_result=False, score=None, bc=None, bw=1, darkness=0, dx=0, dy=0, lw=2):
# 結果によってゲーム盤の背景色を変更する
if show_result:
if score is None and mb.status == Marubatsu.PLAYING:
bgcolor = "white"
- elif score > 0 or mb.status == Marubatsu.CIRCLE:
+ elif (score is not None and score > 0) or mb.status == Marubatsu.CIRCLE:
bgcolor = "lightcyan"
- elif score < 0 or mb.status == Marubatsu.CROSS:
+ elif (score is not None and score < 0) or mb.status == Marubatsu.CROSS:
bgcolor = "lavenderblush"
else:
bgcolor = "lightyellow"
元と同じなので省略
Marubatsu_GUI.draw_board = draw_board
忘れている方がいるかもしれないので補足しますが、以前の記事で説明した 短絡評価 が行われるため、score is not None and score > 0 という式は、score が None の場合は and の後ろの score > 0 という式は実行されません。
また、score > 0 and score is not None のように、and の前後の式を入れ替えると、score > 0 が必ず実行されるようになるので score が None の場合はエラーが発生してしまう点に注意して下さい。
上記の修正後に下記のプログラムを実行すると、実行結果のように中心となるノードの子ノードの右に 子ノードが存在することを表す線が表示 されるようになります。また、それぞれのノードに最善手を表すデータが記録されるようになったので、最善手を着手していないノードが灰色で表示 されるようになりますが、最善手を着手し続けた局面のノードが表示されない という問題が発生しています。その理由について少し考えてみて下さい。
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": maxdepth,
"bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth,
show_bestmove=True)
実行結果
最善手を着手し続けた局面が表示されない原因の検証
上記で表示された部分木をよく見ると、画像の横幅が狭い ことが確認できるので、原因としては Figure の横幅が狭い ため、表示されるはずのノードが表示されていない 可能性が高いことがわかります。そこで、draw_subtree メソッドの中で Figure がどのように作成されるか を確認することにします。
下記は、draw_subtree メソッドで Figure を作成する処理を行うプログラムです。
1 def draw_subtree(self, 略, ax=None, 略):
略
2 width = 5 * (maxdepth + 1)
略
3 if ax is None:
4 fig, ax = plt.subplots(figsize=(width * size, height * size))
5 ax.set_xlim(0, width)
6 ax.set_ylim(0, height)
7 ax.invert_yaxis()
8 ax.axis("off")
略
上記のプログラムから、draw_subtree では Figure と Axes に対して以下のような処理が行われることがわかります。
-
仮引数
axにNoneが代入されている場合 は以下の処理を行う- 2 行目で
widthに仮引数maxdepth + 1に比例した値を計算 する - 4 行目で
widthに比例したサイズの Figure を作成する - 5 行目で Axes の x 軸方向の表示範囲 を 深さが
maxdepthまでのノードを表示 するように設定する
- 2 行目で
-
axがNoneでない場合 はdraw_subtreeでは Figure を作成せず、別の所で作成された Figure の Axes が代入された 仮引数axに対して描画を行う
先程のプログラムでは、draw_subtree を呼び出す際に キーワード引数 ax を記述していない ので、maxdepth + 1 に比例するサイズの Figure が作成され、Axes の表示範囲として 深さが maxdepth までのノードを表示する Axes が作成される ことになります。そのため、最善手を着手し続けた場合の局面 を表す maxdepth よりも深いノードは表示されません。これがバグの原因です。
バグの修正方法
show_bestmove に True が代入されている場合 は、最大で 〇×ゲームの ゲーム木の深さの最大値である 9 までの深さの部分木が作成 される可能性があります。そのため、その場合は下記のプログラムのように、width に maxdepth + 1 ではなく、9 + 1 = 10 に比例する値を計算する必要があります。なお、最善手を着手し続けた場合のノードを表示しても Figure の高さは変わらないので height に代入する値は変更する必要はありません。
1 import matplotlib.pyplot as plt
2
3 def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
4 isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
5 if show_bestmove:
6 width = 5 * 10
7 else:
8 width = 5 * (maxdepth + 1)
9 height = centernode.height
元と同じなので省略
10
11 Mbtree.draw_subtree = draw_subtree
行番号のないプログラム
import matplotlib.pyplot as plt
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
elif node.mb.last_move in node.parent.bestmoves:
return 0
else:
return 0.2
if anim_frame is None:
return 0
index = node.score_index if isscore else node.id
return 0.5 if index > anim_frame else 0
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 * size))
ax.set_xlim(0, width)
ax.set_ylim(0, height)
ax.invert_yaxis()
ax.axis("off")
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 = 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
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 = 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 = 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 = 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.pyplot as plt
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):
元と同じなので省略
- width = 5 * (maxdepth + 1)
+ if show_bestmove:
+ width = 5 * 10
+ else:
+ width = 5 * (maxdepth + 1)
height = centernode.height
元と同じなので省略
Mbtree.draw_subtree = draw_subtree
上記の修正後に下記のプログラムを実行すると、実行結果のように最善手を着手し続けた局面のノードが正しく表示されるようになったことが確認できます。なお、ノードの 評価値は計算されていない ので、決着がついたノードのみ色が表示 されます。
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": maxdepth,
"bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth,
show_bestmove=True)
実行結果
バグが発生した原因
このバグは先ほど説明した潜在的なバグで、draw_subtree に仮引数 show_bestmove を追加した際に上記の修正を行うのを忘れてしまったこと が原因で発生しました。また、このバグがこれまで生じなかった原因は、Marubatsu_GUI クラスの update_gui メソッドから draw_subtree を呼び出す際は、先に 深さが 9 までのゲーム木を表示できるように Figure と Axes を作成 した後で、下記のプログラムの 4 行目のように キーワード引数 ax=ax を記述 して呼び出しているからです。
1 def update_gui(略):
略
2 self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode,
3 anim_frame=self.play.value, isscore=self.isscore,
4 ax=self.ax, maxdepth=maxdepth)
略
選択されたノードの計算
draw_subtree では、中心となるノードと、赤い枠で表示される 選択されたノード を centernode と selectednode という別々の仮引数に代入します。そのため、create_subtree で作成した部分木を draw_subtree で表示 する際には、中心となるノードと 選択されたノード を作成した 部分木から探す必要 があります。
この問題に対処するために、前回の記事では create_subtree の処理の中 で、中心となるノードを centernode という属性に代入 するという工夫を行いましたので、選択されたノード に対しても同様に selectednode という属性に代入 することにします。
選択されたノードの指定 は、前回の記事の中心となるノードの指定と同様に、その局面のデータ を、仮引数 subtree に代入する dict の selectedmb というキーの値に代入 することにします。選択されたノードは、部分木を作成した後で ルートノードから 選択されたノードの局面の 棋譜に従って子ノードを辿る ことで探すことができます。
下記はそのように create_subtree を修正したプログラムです。なお、この処理は部分木の作成の処理がすべて終わった後で行っています。
-
2 行目：選択されたノードを表す局面を
selectedmbに代入する -
3 行目：選択されたノードを代入する
selectednode属性を、作成した部分木のルートノードで初期化する -
4、5 行目：選択されたノードの局面の棋譜を表す
records属性から着手を順番に取り出して、その着手を行った子ノードでselectednode属性を更新する処理を行う
1 def create_subtree(self):
元と同じなので省略
2 selectedmb = self.subtree["selectedmb"]
3 self.selectednode = self.root
4 for move in selectedmb.records[1:]:
5 self.selectednode = self.selectednode.children_by_move[move]
6
7 Mbtree.create_subtree = create_subtree
行番号のないプログラム
def create_subtree(self):
bestmoves_by_board = self.subtree["bestmoves_by_board"]
self.root = Node(Marubatsu(), bestmoves_by_board=bestmoves_by_board)
depth = 0
nodelist = [self.root]
centermb = self.subtree["centermb"]
centerdepth = centermb.move_count
records = centermb.records
maxdepth = self.subtree["maxdepth"]
while len(nodelist) > 0:
childnodelist = []
for node in nodelist:
if depth < centerdepth - 1:
childmb = deepcopy(node.mb)
x, y = records[depth + 1]
childmb.move(x, y)
childnode = Node(childmb, parent=node, depth=depth+1,
bestmoves_by_board=bestmoves_by_board)
node.insert(childnode)
childnodelist.append(childnode)
elif depth < maxdepth:
node.calc_children(bestmoves_by_board=bestmoves_by_board)
if depth == centerdepth - 1:
for move, childnode in node.children_by_move.items():
if move == records[depth + 1]:
self.centernode = childnode
childnodelist.append(self.centernode)
else:
if childnode.mb.status == Marubatsu.PLAYING:
childnode.children.append(None)
else:
childnodelist += node.children
else:
if node.mb.status == Marubatsu.PLAYING:
childmb = deepcopy(node.mb)
board_str = node.mb.board_to_str()
x, y = bestmoves_by_board[board_str][0]
childmb.move(x, y)
childnode = Node(childmb, parent=node, depth=depth+1,
bestmoves_by_board=bestmoves_by_board)
node.insert(childnode)
childnodelist.append(childnode)
nodelist = childnodelist
depth += 1
selectedmb = self.subtree["selectedmb"]
self.selectednode = self.root
for move in selectedmb.records[1:]:
self.selectednode = self.selectednode.children_by_move[move]
Mbtree.create_subtree = create_subtree
修正箇所
def create_subtree(self):
元と同じなので省略
+ selectedmb = self.subtree["selectedmb"]
+ self.selectednode = self.root
+ for move in selectedmb.records[1:]:
+ self.selectednode = self.selectednode.children_by_move[move]
Mbtree.create_subtree = create_subtree
上記の修正後に下記のプログラムで以下のような部分木を表示するプログラムを実行すると、実行結果のように最善手を着手し続けた局面のノードが表示されるようになりますが、選択されたノードの子孫ノードがすべて赤い枠で表示される という問題が発生します。この問題の理由について少し考えてみて下さい。
- 中心となるノードは先ほどと同様に (0, 0) と (1, 0) に着手を行った局面のノード
- 選択されたノードは、さらに (2, 0) に着手を行った局面のノード
- それ以外は先ほどと同様の部分木を表示する
mb2 = Marubatsu()
mb2.move(0, 0)
mb2.move(1, 0)
mb2.move(2, 0)
subtree = Mbtree(subtree={"centermb": mb, "selectedmb": mb2, "maxdepth": maxdepth,
"bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
selectednode = subtree.selectednode
subtree.draw_subtree(centernode=centernode, selectednode=selectednode, maxdepth=maxdepth,
show_bestmove=True)
実行結果
問題の考察と修正
部分木を作成する際に、選択された局面のデータ は下記のプログラムのように 1 つしか記述していない ので、複数のノードが赤い枠で描画される原因 は、最善手を着手し続けた局面の ノードを描画するプログラムのほうにある 可能性が高そうです。
subtree = Mbtree(subtree={"centermb": mb, "selectedmb": mb2, "maxdepth": maxdepth,
"bestmoves_by_board": bestmoves_by_board})
下記は、draw_subtree の中で、最善手を着手し続けた局面のノードを描画 する処理を行う 付近のプログラム です。
1 def draw_subtree(略)
略
2 emphasize = node is selectednode
3 darkness = calc_darkness(node)
4 rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, darkness=darkness,
5 show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
6 self.nodes_by_rect[rect] = node
7 if show_bestmove and depth == maxdepth:
8 bestnode = node
9 while len(bestnode.bestmoves) > 0:
10 bestmove = bestnode.bestmoves[0]
11 bestnode = bestnode.children_by_move[bestmove]
12 dx = 5 * bestnode.depth
13 bestnode.height = 4
14 rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth,
15 emphasize=emphasize, show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
略
2 ~ 4 行目では、node に代入されたノードを描画 する処理を下記の手順で行います。
-
2 行目：
nodeに代入されたノードが選択されたノードであるかを計算してemphasizeというローカル変数にその結果を代入する -
4 行目：キーワード引数
emphasize=emphasizeを記述してdraw_nodeを呼び出すことで、nodeが選択されたノードである場合に赤い枠のノードを描画する
その次の 7 ~ 15 行目では、node の深さが maxdepth の場合に、最善手を着手し続けた場合の子ノードを描画する処理を行っていますが、その際に ノードを描画する処理 を行う 14、15 行目では、キーワード引数 emphasize=emphasize を記述して draw_node を呼び出しています。
2 行目以降の処理 でローカル変数 emphasize に対する代入処理は行われない ので、14 行目 で draw_node を呼び出した際の empasize の値 は、2 行目 で emphasize に代入した値と 同じ値が代入されたまま になっています。そのため、14 行目で描画される node の子孫ノードの枠は、4 行目で描画される node の枠と同じものが表示されることになります。これが、先程の実行結果のように、選択されたノードの子孫ノードがすべて赤枠で描画されてしまう理由です。
draw_subtree の修正
従って、このバグは下記のプログラムの 10 行目のように、最善手を着手し続けた場合の子ノードを描画する直前で、その 子ノードが選択されたノードであるかを計算し直す ようにすることで修正することができます。
1 def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
2 isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
3 if show_bestmove and depth == maxdepth:
4 bestnode = node
5 while len(bestnode.bestmoves) > 0:
6 bestmove = bestnode.bestmoves[0]
7 bestnode = bestnode.children_by_move[bestmove]
8 dx = 5 * bestnode.depth
9 bestnode.height = 4
10 emphasize = bestnode is selectednode
11 rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth, emphasize=emphasize,
12 show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
13 self.nodes_by_rect[rect] = bestnode
元と同じなので省略
14
15 Mbtree.draw_subtree = draw_subtree
行番号のないプログラム
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
elif node.mb.last_move in node.parent.bestmoves:
return 0
else:
return 0.2
if anim_frame is None:
return 0
index = node.score_index if isscore else node.id
return 0.5 if index > anim_frame else 0
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 * size))
ax.set_xlim(0, width)
ax.set_ylim(0, height)
ax.invert_yaxis()
ax.axis("off")
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 = 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 = 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 = 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 = 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
修正箇所
def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
if 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 元と同じなので省略
Mbtree.draw_subtree = draw_subtree
上記の修正後に下記のプログラムを実行すると、実行結果のように正しい表示が行われるようになることが確認できます。
subtree = Mbtree(subtree={"centermb": mb, "selectedmb": mb2, "maxdepth": maxdepth,
"bestmoves_by_board": bestmoves_by_board})
centernode = subtree.centernode
selectednode = subtree.selectednode
subtree.draw_subtree(centernode=centernode, selectednode=selectednode, maxdepth=maxdepth,
show_bestmove=True)
実行結果
バグが発生した原因
このバグもは先ほど説明した潜在的なバグで、draw_subtree を最善手を着手し続けた局面のノードを表示するように修正した際に、上記の修正を行うのを忘れてしまったことが原因で発生しました。このバグがこれまで生じなかった原因を下記に記しますが、少々ややこしいの意味がわからない人は無視しても構いません。
このバグは、下記の 修正前 のプログラムの 14 行目が実行された際に発生するバグです。
1 def draw_subtree(略)
略
2 emphasize = node is selectednode
3 darkness = calc_darkness(node)
4 rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, darkness=darkness,
5 show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
6 self.nodes_by_rect[rect] = node
7 if show_bestmove and depth == maxdepth:
8 bestnode = node
9 while len(bestnode.bestmoves) > 0:
10 bestmove = bestnode.bestmoves[0]
11 bestnode = bestnode.children_by_move[bestmove]
12 dx = 5 * bestnode.depth
13 bestnode.height = 4
14 rect = bestnode.draw_node(ax=ax, maxdepth=bestnode.depth,
15 emphasize=emphasize, show_score=show_score, size=size, lw=lw, dx=dx, dy=dy)
略
14 行目の処理は、下記の条件を すべて満たす場合でのみ 行われます。先ほどの例では、node が選択されたノードの場合 は、この条件をすべて満たす のでバグが発生しました。
-
nodeが選択されたノードである -
nodeの深さがmaxdepthである -
nodeに子ノードが存在する
一方、Marubatsu_GUI クラスで部分木を表示 する際には、update_gui メソッドの下記のプログラムで、選択されたノードから maxdepth が計算 されます。下記のプログラムでは、選択されたノードの深さが、子ノードが存在しない深さが 9 でない場合 は、必ず maxdepth の深さが選択されたノードよりも深くなります。そのため、node が選択されたノードの場合 に上記の条件を すべて満たすことはない ので、このバグは発生しません。
def update_gui(略):
略
if self.selectednode.depth <= 4:
maxdepth = self.selectednode.depth + 1
elif self.selectednode.depth == 5:
maxdepth = 7
else:
maxdepth = 9
略
draw_subtree の計算時間
下記のプログラムで draw_subtree の処理時間を計測した所、実行結果のように平均で 約 2.5 ミリ秒 であることがわかりましたので、今回の記事の最初で見積もったように、部分木を動的に作成する処理にはほとんど時間がかからない ことが確認できました。
%%timeit
Mbtree(subtree={"centermb": mb, "selectedmb": mb2, "maxdepth": maxdepth,
"bestmoves_by_board": bestmoves_by_board})
実行結果
2.51 ms ± 84.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
今回の記事はここまでにします。評価値をゲーム盤の上に表示する処理がまだ残っていますが、その処理は次回の記事で実装することにします。また、次回の記事では Mbtree_GUI クラスで create_subtree を利用して部分木を表示する処理を実装します。
今回の記事のまとめ
今回の記事では、最善手を着手し続けた場合のノードを作成するように create_subtree を修正しました。また、潜在的なバグをいくつか紹介し、その性質と修正方法について説明しました。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| marubatsu_new.py | 今回の記事で更新した marubatsu.py |
| tree_new.py | 今回の記事で更新した tree.py |
次回の記事