目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| test.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義。現在は gui_play のみ定義されている |
| tree.py | ゲーム木に関する Node、Mbtree クラスの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
α 値または β 値の初期値に関するバグの修正
前回の記事では αβ 法の視覚化 のための Mbtree_Anim の修正の続きを行いましたが、その際に "tt" の状態で表示する内容の一部にバグが存在する ことがわかりましたので、最初にそのバグを修正することにします。
バグの原因
以前の記事で説明したように、"tt" の状態で行われる α 値または β 値の初期値の更新 は、α 値と β 値の初期値の範囲を 置換表の範囲外の値が含まれない ように 範囲を狭める方向で更新する ことで、枝狩りの効率を上げる という目的で行います。
その際に行う 更新処理 は以前の記事で説明したように、以下の式で計算 します。なお、以前の記事と同様に α 値の初期値を $α$、β 値の初期値を $β$、置換表の範囲の下界を $l$、置換表の範囲の上界を $u$ と表記します。
- α 値の初期値を $α = max(α, l)$ とする
- β 値の初期値を $β = min(β, u)$ とする
バグの原因は以前の記事で ai_abs_tt2 を修正した際に、上記の処理を行う下記のプログラムの 10、11 行目で筆者がうっかり min と max を間違えて記述 してしまったことです。
1 if boardtxt in tt:
2 lower_bound, upper_bound = tt[boardtxt]
3 if lower_bound == upper_bound:
4 return lower_bound
5 elif upper_bound <= alpha:
6 return upper_bound
7 elif beta <= lower_bound:
8 return lower_bound
9 else:
10 alpha = min(alpha, lower_bound)
11 beta = max(beta, upper_bound)
その後、以前の記事で calc_score_for_anim を ai_abs_tt2 を元に定義 したためこのバグが calc_score_for_anim でも発生してしまいました。
このような、min と max を間違えるような うっかりミス は 気を付けていても良く起きるバグの一つ です。同様のバグとして下記のようなバグは実際によく発生するので注意が必要です。
- < と > を間違える
- < と <= を間違える
- > と >= を間違える
バグの修正
このバグは ai_abs_tt2、ai_abs_tt3、ai_abs_tt4、calc_score_for_anim にあるのでそれぞれを修正することにします。
後で説明しますが、このバグによって 枝狩りの効率が悪く なりますが、評価値は正しく計算される ので 修正前の AI は強解決の AI です。また、過去の記事に遡ってこのバグを修正してしまうと、今回の記事の意味がわからなくなるので過去の記事の内容はそのままにします。
ai_abs_tt2 の修正
ai_abs_tt2 の修正は以下の通りです。先程説明したように 18、19 行目の min と max を入れ替えました。
1 from ai import ai_by_score, dprint
2 from marubatsu import Marubatsu
3 from copy import deepcopy
4
5 @ai_by_score
6 def ai_abs_tt2(mb:Marubatsu, debug:bool=False, shortest_victory:bool=False):
7 count = 0
8 def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
9 if boardtxt in tt:
10 lower_bound, upper_bound = tt[boardtxt]
11 if lower_bound == upper_bound:
12 return lower_bound
13 elif upper_bound <= alpha:
14 return upper_bound
15 elif beta <= lower_bound:
16 return lower_bound
17 else:
18 alpha = max(alpha, lower_bound)
19 beta = min(beta, upper_bound)
元と同じなので省略
行番号のないプログラム
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
from copy import deepcopy
@ai_by_score
def ai_abs_tt2(mb, debug=False, shortest_victory=False):
count = 0
def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
nonlocal count
count += 1
if mborig.status == Marubatsu.CIRCLE:
return (11 - mborig.move_count) / 2 if shortest_victory else 1
elif mborig.status == Marubatsu.CROSS:
return (mborig.move_count - 10) / 2 if shortest_victory else -1
elif mborig.status == Marubatsu.DRAW:
return 0
boardtxt = mborig.board_to_str()
if boardtxt in tt:
lower_bound, upper_bound = tt[boardtxt]
if lower_bound == upper_bound:
return lower_bound
elif upper_bound <= alpha:
return upper_bound
elif beta <= lower_bound:
return lower_bound
else:
alpha = max(alpha, lower_bound)
beta = min(beta, upper_bound)
alphaorig = alpha
betaorig = beta
legal_moves = mborig.calc_legal_moves()
if mborig.turn == Marubatsu.CIRCLE:
score = float("-inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = max(score, ab_search(mb, tt, alpha, beta))
if score >= beta:
break
alpha = max(alpha, score)
else:
score = float("inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = min(score, ab_search(mb, tt, alpha, beta))
if score <= alpha:
break
beta = min(beta, score)
from util import calc_same_boardtexts
boardtxtlist = calc_same_boardtexts(mborig)
if score <= alphaorig:
lower_bound = float("-inf")
upper_bound = score
elif score < betaorig:
lower_bound = score
upper_bound = score
else:
lower_bound = score
upper_bound = float("inf")
for boardtxt in boardtxtlist:
tt[boardtxt] = (lower_bound, upper_bound)
return score
score = ab_search(mb, {})
dprint(debug, "count =", count)
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
修正箇所
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
from copy import deepcopy
@ai_by_score
def ai_abs_tt2(mb, debug=False, shortest_victory=False):
count = 0
def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
if boardtxt in tt:
lower_bound, upper_bound = tt[boardtxt]
if lower_bound == upper_bound:
return lower_bound
elif upper_bound <= alpha:
return upper_bound
elif beta <= lower_bound:
return lower_bound
else:
- alpha = min(alpha, lower_bound)
+ alpha = max(alpha, lower_bound)
- beta = max(beta, upper_bound)
+ beta = min(beta, upper_bound)
元と同じなので省略
ai_abs_tt3 の修正
ai_abs_tt3 の修正は以下の通りです。修正箇所は先程と同様です。
1 @ai_by_score
2 def ai_abs_tt3(mb, debug=False, shortest_victory=False):
3 count = 0
4 def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
5 if boardtxt in tt:
6 lower_bound, upper_bound = tt[boardtxt]
7 if lower_bound == upper_bound:
8 return lower_bound
9 elif upper_bound <= alpha:
10 return upper_bound
11 elif beta <= lower_bound:
12 return lower_bound
13 else:
14 alpha = max(alpha, lower_bound)
15 beta = min(beta, upper_bound)
元と同じなので省略
行番号のないプログラム
@ai_by_score
def ai_abs_tt3(mb, debug=False, shortest_victory=False):
count = 0
def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
nonlocal count
count += 1
if mborig.status == Marubatsu.CIRCLE:
return (11 - mborig.move_count) / 2 if shortest_victory else 1
elif mborig.status == Marubatsu.CROSS:
return (mborig.move_count - 10) / 2 if shortest_victory else -1
elif mborig.status == Marubatsu.DRAW:
return 0
boardtxt = mborig.board_to_str()
if boardtxt in tt:
lower_bound, upper_bound = tt[boardtxt]
if lower_bound == upper_bound:
return lower_bound
elif upper_bound <= alpha:
return upper_bound
elif beta <= lower_bound:
return lower_bound
else:
alpha = max(alpha, lower_bound)
beta = min(beta, upper_bound)
else:
lower_bound = float("-inf")
upper_bound = float("inf")
alphaorig = alpha
betaorig = beta
legal_moves = mborig.calc_legal_moves()
if mborig.turn == Marubatsu.CIRCLE:
score = float("-inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = max(score, ab_search(mb, tt, alpha, beta))
if score >= beta:
break
alpha = max(alpha, score)
else:
score = float("inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = min(score, ab_search(mb, tt, alpha, beta))
if score <= alpha:
break
beta = min(beta, score)
from util import calc_same_boardtexts
boardtxtlist = calc_same_boardtexts(mborig)
if score <= alphaorig:
upper_bound = score
elif score < betaorig:
lower_bound = score
upper_bound = score
else:
lower_bound = score
for boardtxt in boardtxtlist:
tt[boardtxt] = (lower_bound, upper_bound)
return score
score = ab_search(mb, {})
dprint(debug, "count =", count)
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
修正箇所
@ai_by_score
def ai_abs_tt3(mb, debug=False, shortest_victory=False):
count = 0
def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
if boardtxt in tt:
lower_bound, upper_bound = tt[boardtxt]
if lower_bound == upper_bound:
return lower_bound
elif upper_bound <= alpha:
return upper_bound
elif beta <= lower_bound:
return lower_bound
else:
- alpha = min(alpha, lower_bound)
+ alpha = max(alpha, lower_bound)
- beta = max(beta, upper_bound)
+ beta = min(beta, upper_bound)
元と同じなので省略
ai_abs_tt4 の修正
ai_abs_tt4 を 修正する前と後 で、ゲーム開始時の局面1の評価値を計算した際に 計算されるノードの数がどのように変わるかを確認するため に、下記のプログラムを実行します。実行結果から修正前の バグのある ai_abs_tt4 では計算されるノードの数が、最短の勝利を目指さない場合は 832、目指す場合は 1343 であることが確認できました。
from ai import ai_abs_tt4
from marubatsu import Marubatsu
mb = Marubatsu()
ai_abs_tt4(mb, calc_score=True, shortest_victory=False, debug=True)
ai_abs_tt4(mb, calc_score=True, shortest_victory=True, debug=True)
実行結果
count = 832
count = 1343
ai_abs_tt4 の修正は以下の通りです。修正箇所は先程と同様です。
1 @ai_by_score
2 def ai_abs_tt4(mb, debug=False, shortest_victory=False):
3 count = 0
4 def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
5 if boardtxt in tt:
6 lower_bound, upper_bound = tt[boardtxt]
7 if lower_bound == upper_bound:
8 return lower_bound
9 elif upper_bound <= alpha:
10 return upper_bound
11 elif beta <= lower_bound:
12 return lower_bound
13 else:
14 alpha = max(alpha, lower_bound)
15 beta = min(beta, upper_bound)
元と同じなので省略
行番号のないプログラム
@ai_by_score
def ai_abs_tt4(mb, debug, shortest_victory=False):
count = 0
def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
nonlocal count
count += 1
if mborig.status == Marubatsu.CIRCLE:
return (11 - mborig.move_count) / 2 if shortest_victory else 1
elif mborig.status == Marubatsu.CROSS:
return (mborig.move_count - 10) / 2 if shortest_victory else -1
elif mborig.status == Marubatsu.DRAW:
return 0
boardtxt = mborig.board_to_str()
if boardtxt in tt:
lower_bound, upper_bound = tt[boardtxt]
if lower_bound == upper_bound:
return lower_bound
elif upper_bound <= alpha:
return upper_bound
elif beta <= lower_bound:
return lower_bound
else:
alpha = max(alpha, lower_bound)
beta = min(beta, upper_bound)
else:
lower_bound = min_score
upper_bound = max_score
alphaorig = alpha
betaorig = beta
legal_moves = mborig.calc_legal_moves()
if mborig.turn == Marubatsu.CIRCLE:
score = float("-inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = max(score, ab_search(mb, tt, alpha, beta))
if score >= beta:
break
alpha = max(alpha, score)
else:
score = float("inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = min(score, ab_search(mb, tt, alpha, beta))
if score <= alpha:
break
beta = min(beta, score)
from util import calc_same_boardtexts
boardtxtlist = calc_same_boardtexts(mborig)
if score <= alphaorig:
upper_bound = score
elif score < betaorig:
lower_bound = score
upper_bound = score
else:
lower_bound = score
for boardtxt in boardtxtlist:
tt[boardtxt] = (lower_bound, upper_bound)
return score
min_score = -2 if shortest_victory else -1
max_score = 3 if shortest_victory else 1
score = ab_search(mb, {}, alpha=min_score, beta=max_score)
dprint(debug, "count =", count)
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
修正箇所
@ai_by_score
def ai_abs_tt4(mb, debug=False, shortest_victory=False):
count = 0
def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
if boardtxt in tt:
lower_bound, upper_bound = tt[boardtxt]
if lower_bound == upper_bound:
return lower_bound
elif upper_bound <= alpha:
return upper_bound
elif beta <= lower_bound:
return lower_bound
else:
- alpha = min(alpha, lower_bound)
+ alpha = max(alpha, lower_bound)
- beta = max(beta, upper_bound)
+ beta = min(beta, upper_bound)
元と同じなので省略
修正したプログラムの確認
上記の修正後に下記のプログラムを実行することで、修正した ai_abs_tt2、ai_abs_tt3、ai_abs_tt4 が 強解決の AI であることが確認 できます。
from util import Check_solved
Check_solved.is_strongly_solved(ai_abs_tt2)
Check_solved.is_strongly_solved(ai_abs_tt3)
Check_solved.is_strongly_solved(ai_abs_tt4)
実行結果
100%|██████████| 431/431 [00:03<00:00, 143.54it/s]
431/431 100.00%
100%|██████████| 431/431 [00:02<00:00, 143.91it/s]
431/431 100.00%
100%|██████████| 431/431 [00:02<00:00, 194.00it/s]
431/431 100.00%
なお、このバグは α 値と β 値の初期値の範囲 が、意図していた範囲よりも広くなってしまう というバグです。このバグによって 枝狩りの効率が悪くなります2が、ルートノードの α 値と β 値の初期値 はこのバグによって 変化しないため、ルートノードの評価値は正しく計算されます。従ってこのバグがあっても ai_abs_tt2、ai_abs_tt3、ai_abs_tt4 が強解決の AI であることに変わりはありません。
次に、修正後の ai_abs_tt4 でゲーム開始時の局面の評価値を計算した際に 計算されるノードの数 を下記のプログラムで表示します。
ai_abs_tt4(mb, calc_score=True, shortest_victory=False, debug=True)
ai_abs_tt4(mb, calc_score=True, shortest_victory=True, debug=True)
実行結果
count = 832
count = 1242
下記は修正前と修正後の結果をまとめた表です。
| 修正前 | 修正後 | |
|---|---|---|
| 最短の勝利を目指さない場合 | 832 | 832 |
| 最短の勝利を目指す場合 | 1343 | 1242 |
最短の勝利を目指さない場合は変化はありませんでしたが、最短の勝利を目指す場合 は修正前の 1343 から 1242 に減っていることから バグによって枝狩りの効率が悪くなっていた ことが確認できました。
最短の勝利を目指さない 場合に 変化がない のは、下記のような原因だと思います。
- 最短の勝利を目指さない場合は 評価値の範囲 が -1 ~ 1 と 狭い
- また、評価値は -1、0、1 の 3 種類の整数しかない
- そのため、α 値と β 値の初期値の範囲は -1 ~ 1、-1 ~ 0、0 ~ 1 の 3 種類しかない
- そのため、このバグによって α 値と β 値の初期値の範囲が 正しく計算されないという状況がほとんど発生しない
- また、そのような状況が発生した場合でも、α 値と β 値の初期値の範囲が狭い ため 枝狩りの数が変化するような場合が存在しない
一方、最短の勝利を目指す場合 は 評価値の範囲 が -2 ~ 3 と 広い ので、α 値と β 値の初期値の範囲が正しく計算されないという 状況が多く、その中で実際に枝狩りの効率が悪くなる状況が実際に存在します。
このように バグが存在しても、プログラムが扱うデータが バグが発生する条件を満たさない 場合は 正常な計算が行われることが良くあります。プログラムが正常に動作しない場合は必ずバグが存在しますが、プログラムが正常に動作したからと言ってバグが存在しないとは限らない ということを常に忘れないようにする必要があります。
calc_score_for_anim の修正
calc_score_for_anim の修正は以下の通りです。バグの修正箇所は先程と同様です。
また、このバグとは関係ないのですが、ノードの評価値が確定した "end" のフレーム では、下記のプログラムの 39 行目の後で 下界と上界が等しい場合は評価値の種類を表す文字列を "exact value" とする 処理を行っていましたが、よく考えると それは評価値の種類の意味を考えるとおかしい 気がしましたので その処理は削除する ことにしました。この修正はこの後で実装する "end" の状態の表示に影響 します。
- 19 行目：α 値または β 値が更新されるかどうかの判定式を修正した
-
20、21 行目：
maxとminが入れ替わっていた点を修正した - 39 行目の下にあった、評価値が確定した際に、下界と上界が等しい場合に評価値の種類を "exact value" とする処理を削除した
1 from tree import Mbtree
2
3 def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
元と同じなので省略
4 if use_tt:
5 boardtxt = node.mb.board_to_str()
6 if boardtxt in tt:
7 registered_in_tt = True
8 lower_bound, upper_bound = tt[boardtxt]
9 if lower_bound == upper_bound:
10 node.score = lower_bound
11 tt_pruned = True
12 elif upper_bound <= alphaorig:
13 node.score = upper_bound
14 tt_pruned = True
15 elif betaorig <= lower_bound:
16 node.score = lower_bound
17 tt_pruned = True
18 else:
19 ab_updated = alphaorig < lower_bound or betaorig > upper_bound
20 alphaorig = max(alphaorig, lower_bound)
21 betaorig = min(betaorig, upper_bound)
元と同じなので省略
22 if node.score <= alphaorig:
23 score_type = "fail low"
24 clower_bound = min_score
25 cupper_bound = node.score
26 tlower_bound = lower_bound
27 tupper_bound = node.score
28 elif node.score < betaorig:
29 score_type = "exact value"
30 clower_bound = node.score
31 cupper_bound = node.score
32 tlower_bound = node.score
33 tupper_bound = node.score
34 else:
35 score_type = "fail high"
36 clower_bound = node.score
37 cupper_bound = max_score
38 tlower_bound = node.score
39 tupper_bound = upper_bound
元と同じなので省略
40
41 Mbtree.calc_score_for_anim = calc_score_for_anim
行番号のないプログラム
from tree import Mbtree
def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
def assign_pruned_index(node, index):
node.pruned_index = index
self.num_pruned += 1
for childnode in node.children:
assign_pruned_index(childnode, index)
def calc_node_score(node, tt, alphaorig=float("-inf"), betaorig=float("inf")):
if minimax:
alphaorig = float("-inf")
betaorig = float("inf")
self.nodelist_by_score.append(node)
self.ablist_by_score.append({
"status": "start",
"alphaorig": alphaorig,
"betaorig": betaorig,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
registered_in_tt = False
tt_pruned = False
if node.mb.status != Marubatsu.PLAYING:
self.calc_score_of_node(node)
lower_bound = node.score
upper_bound = node.score
else:
ab_updated = False
if use_tt:
boardtxt = node.mb.board_to_str()
if boardtxt in tt:
registered_in_tt = True
lower_bound, upper_bound = tt[boardtxt]
if lower_bound == upper_bound:
node.score = lower_bound
tt_pruned = True
elif upper_bound <= alphaorig:
node.score = upper_bound
tt_pruned = True
elif betaorig <= lower_bound:
node.score = lower_bound
tt_pruned = True
else:
ab_updated = alphaorig < lower_bound or betaorig > upper_bound
alphaorig = max(alphaorig, lower_bound)
betaorig = min(betaorig, upper_bound)
else:
lower_bound = min_score
upper_bound = max_score
self.nodelist_by_score.append(node)
if tt_pruned:
for childnode in node.children:
assign_pruned_index(childnode, len(self.nodelist_by_score) - 1)
self.ablist_by_score.append({
"status": "tt",
"alphaorig": alphaorig,
"betaorig": betaorig,
"tt_pruned": tt_pruned,
"ab_updated": ab_updated,
"registered_in_tt": registered_in_tt,
"lower_bound": lower_bound,
"upper_bound": upper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
else:
lower_bound = min_score
upper_bound = max_score
if not tt_pruned:
alpha = alphaorig
beta = betaorig
ab_pruned = False
maxnode = node.mb.turn == Marubatsu.CIRCLE
node.score = min_score if maxnode else max_score
for childnode in node.children:
childscore = calc_node_score(childnode, tt, alpha, beta)
self.nodelist_by_score.append(node)
self.ablist_by_score.append({
"status": "score",
"alphaorig": alphaorig,
"betaorig": betaorig,
"score": node.score,
"childscore": childscore,
"registered_in_tt": registered_in_tt,
"lower_bound": lower_bound,
"upper_bound": upper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
if maxnode:
updated = node.score < childscore
node.score = max(node.score, childscore)
alpha = max(node.score, alpha)
if node.score >= beta:
ab_pruned = True
else:
updated = node.score > childscore
node.score = min(node.score, childscore)
beta = min(node.score, beta)
if node.score <= alpha:
ab_pruned = True
self.nodelist_by_score.append(node)
if ab_pruned:
index = node.children.index(childnode)
for prunednode in node.children[index + 1:]:
assign_pruned_index(prunednode, len(self.nodelist_by_score) - 1)
self.ablist_by_score.append({
"status": "update",
"alphaorig": alphaorig,
"betaorig": betaorig,
"score": node.score,
"registered_in_tt": registered_in_tt,
"updated": updated,
"ab_pruned": ab_pruned,
"lower_bound": lower_bound,
"upper_bound": upper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
if ab_pruned:
break
if node.score <= alphaorig:
score_type = "fail low"
clower_bound = min_score
cupper_bound = node.score
tlower_bound = lower_bound
tupper_bound = node.score
elif node.score < betaorig:
score_type = "exact value"
clower_bound = node.score
cupper_bound = node.score
tlower_bound = node.score
tupper_bound = node.score
else:
score_type = "fail high"
clower_bound = node.score
cupper_bound = max_score
tlower_bound = node.score
tupper_bound = upper_bound
if use_tt:
from util import calc_same_boardtexts
boardtxtlist = calc_same_boardtexts(node.mb)
for boardtxt in boardtxtlist:
tt[boardtxt] = (tlower_bound, tupper_bound)
self.nodelist_by_score.append(node)
self.num_calculated += 1
self.ablist_by_score.append({
"status": "end",
"alphaorig": alphaorig,
"betaorig": betaorig,
"score": node.score,
"registered_in_tt": registered_in_tt,
"tt_pruned": tt_pruned,
"score_type": score_type,
"lower_bound": lower_bound,
"upper_bound": upper_bound,
"clower_bound": clower_bound,
"cupper_bound": cupper_bound,
"tlower_bound": tlower_bound,
"tupper_bound": tupper_bound,
"num_calculated": self.num_calculated,
"num_pruned": self.num_pruned,
})
node.score_index = len(self.nodelist_by_score) - 1
return node.score
self.calculated_by_calc_score_for_anim = True
self.minimax = minimax
self.init_ab = init_ab
self.use_tt = use_tt
if shortest_victory is not None:
self.shortest_victory = shortest_victory
from ai import dprint
for node in self.nodelist:
node.score_index = float("inf")
node.pruned_index = float("inf")
self.nodelist_by_score = []
self.ablist_by_score = []
self.num_calculated = 0
self.num_pruned = 0
if init_ab:
min_score = -2 if self.shortest_victory else -1
max_score = 3 if self.shortest_victory else 1
else:
min_score = float("-inf")
max_score = float("inf")
calc_node_score(abroot, {}, min_score, max_score)
total_nodenum = self.num_pruned + self.num_calculated
ratio = self.num_calculated / total_nodenum * 100
dprint(debug, "ミニマックス法で計算したか", minimax)
dprint(debug, "計算したノードの数", self.num_calculated)
dprint(debug, "枝狩りしたノードの数", self.num_pruned)
dprint(debug, "合計", total_nodenum)
dprint(debug, f"割合 {ratio:.1f}%")
Mbtree.calc_score_for_anim = calc_score_for_anim
修正箇所
from tree import Mbtree
def calc_score_for_anim(self, abroot, debug=False, minimax=False, init_ab=False, use_tt=False, shortest_victory=None):
元と同じなので省略
if use_tt:
boardtxt = node.mb.board_to_str()
if boardtxt in tt:
registered_in_tt = True
lower_bound, upper_bound = tt[boardtxt]
if lower_bound == upper_bound:
node.score = lower_bound
tt_pruned = True
elif upper_bound <= alphaorig:
node.score = upper_bound
tt_pruned = True
elif betaorig <= lower_bound:
node.score = lower_bound
tt_pruned = True
else:
- ab_updated = alphaorig > lower_bound or betaorig < upper_bound
+ ab_updated = alphaorig < lower_bound or betaorig > upper_bound
- alphaorig = min(alphaorig, lower_bound)
+ alphaorig = max(alphaorig, lower_bound)
- betaorig = max(betaorig, upper_bound)
+ betaorig = min(betaorig, upper_bound)
元と同じなので省略
if node.score <= alphaorig:
score_type = "fail low"
clower_bound = min_score
cupper_bound = node.score
tlower_bound = lower_bound
tupper_bound = node.score
elif node.score < betaorig:
score_type = "exact value"
clower_bound = node.score
cupper_bound = node.score
tlower_bound = node.score
tupper_bound = node.score
else:
score_type = "fail high"
clower_bound = node.score
cupper_bound = max_score
tlower_bound = node.score
tupper_bound = upper_bound
- if tlower_bound == tupper_bound:
- score_type = "exact value"
元と同じなので省略
Mbtree.calc_score_for_anim = calc_score_for_anim
上記の修正後に下記のプログラムを実行し、前回の記事で α 値と β 値の初期値の範囲が 間違っていた 67 フレーム目 を表示することで、正しく修正されていることを確認します。
from tree import Mbtree_Anim
mbtree = Mbtree.load("../data/abtree_root")
mbtree.calc_score_for_anim(mbtree.root, minimax=False, use_tt=True, shortest_victory=True, init_ab=True)
Mbtree_Anim(mbtree, isscore=True)
下図は 67 フレーム目の図 で、その下の図は前回の記事の間違っていた 67 フレーム目の図です。上図では下図と異なり黄色の α 値と β 値の初期値の範囲 が赤い矢印の置換表の範囲の外を含まないように 正しく更新されている ことが確認できます。
修正後の 67 フレーム目の図
修正前の 67 フレーム目の図
バグの修正前と修正後が行う 処理の違いは 、下図の 1 つ前の "start" の状態の 66 フレーム目の図 を見ることで確認することができます。修正前と修正後 の 67 フレーム目の α 値と β 値の初期値の範囲 が以下のように計算されていることを確認して下さい。
- 修正前は「66 フレーム目の α 値と β 値の初期値の範囲」と「67 フレーム目の赤い矢印の置換表の範囲」の 両方を含む（OR の）範囲 で、範囲が 広くなる
- 修正後は「66 フレーム目の α 値と β 値の初期値の範囲」と「67 フレーム目の赤い矢印の置換表の範囲」の 両方で共通する（AND の）範囲 で、範囲が 狭くなる
残りの αβ 法の視覚化のための Mbtree_Anim の修正
バグが修正できたので、残りの αβ 法の視覚化のための Mbtree_Anim の修正を行ないます。
残っているのは下記の "score"、"update"、"end" のフレームの表示です。なお、ミニマックス法と共通する内容には先頭に（※）を記述しました。全体の視覚化の検討結果については前回の記事を復習して下さい。
-
"score" の状態
- （※）数直線上にそのフレームでのノードの評価値を表示
- （※）数直線上に子ノードの評価値を表示
- そのフレームでの α 値と β 値
-
"update" の状態
- （※）数直線上にそのフレームでのノードの評価値を表示
- ノードの評価値が更新された場合
- （※）赤字で「評価値の更新」を表示
- 更新されていない場合
- （※）黒字で「評価値の更新なし」を表示
- そのフレームでの α 値と β 値
- α 狩りが行われた場合は赤字で「α 狩り」と表示
- β 狩りが行われた場合は赤字で「β 狩り」と表示
-
"end" の状態
- （※）数直線上にそのフレームでのノードの評価値を表示
- このノードの評価値の種類によってフレームの状態を以下のように表示する
- fail low の場合は「評価値の確定（fail low）」を表示
- exact value の場合は「評価値の確定（exact value）」を表示
- fail high の場合は「評価値の確定（fail high）」を表示
- 置換表を利用する場合
- 置換表による枝狩りが行われた場合
- （※）黒字で「置換表に登録されていたデータを利用」を表示
- 置換表による枝狩りが行われていない場合
- （※）赤字で「置換表への登録」を表示
- 計算された範囲
- 登録する範囲
- 置換表による枝狩りが行われた場合
"score" の状態で表示する内容の実装
"score" の状態で新しく表示する内容は「そのフレームでの α 値と β 値」です。どのように実装すればよいかについて少し考えてみて下さい。
そのフレームでの α 値と β 値は、子ノードの評価値を計算する際に受け継がれる値 ですが、現在のフレームの評価値を計算 する際には 利用されない値 です。また、"score" のフレームでは数直線上にそのノードの評価値と子ノードの評価値が表示されているので、そのフレームでの α 値と β 値を 表示するとわかりづらくなるという問題が発生 します。そこで、"score" の状態 ではそのフレームでの α 値と β 値を 表示しない ことにします。従って update_frameinfo を修正する必要はありません。
下図はゲーム開始時の局面の最初の子ノードの評価値が計算された "score" のフレームの図で、そのフレームでの α 値と β 値は表示されていませんが、それらの値はこのノードの評価値を計算する際に利用されないので表示しなくても大きな問題はありません。
"update" の状態で表示する内容の実装
下記は "update" の状態で表示する内容の再掲です。（※）の部分は実装済なので、それ以外の場合の表示を実装する必要があります。
- （※）数直線上にそのフレームでのノードの評価値を表示
- ノードの評価値が更新された場合
- （※）赤字で「評価値の更新」を表示
- 更新されていない場合
- （※）黒字で「評価値の更新なし」を表示
- そのフレームでの α 値と β 値
- α 狩りが行われた場合は赤字で「α 狩り」と表示
- β 狩りが行われた場合は赤字で「β 狩り」と表示
また、上記とは別に 以下のような表示の工夫 を行なうことにします。どのように実装すればよいかについて少し考えてみて下さい。
- 真ん中の 3 行目のメッセージを「評価値の更新（fail low）」のように、末尾にこのフレームでのノードの評価値の範囲を表示する
- 右下に表示される範囲の説明を下記のように表示する。
- max ノードの場合は fail high の範囲を「fail high（β 狩り）」と表示する
- min ノードの場合は fail low の範囲を「fail low（α 狩り）」と表示する
- このフレームでのノードの評価値の範囲を赤字で表示する
"update" のフレームで α 狩りまたは β 狩りが行なわれる場合 は、残りの子ノードの評価値の計算は省略されるので、そのフレームでの α 値と β 値が利用されることはありません。従ってその場合はそのフレームでの α 値と β 値を 表示しないことにします。
α 狩りまたは β 狩りが 行なわれない場合 は、次のフレーム では 次の子ノードの評価値の計算を開始 する "start" のフレームになり、その際に そのフレームの α 値と β 値 の値が そのまま子ノードの α 値と β 値の初期値として引き継がれます。従って、"update" のフレームにはそのフレームでの α 値と β 値を 表示したほうが良い でしょう。
具体的にはそのフレームでの α 値と β 値を下記のように表示することにします。
- α 値を数直線上に赤い丸で表示する
- β 値を数直線上に青い丸で表示する
- max ノードでは数直線の右上に「α 値」と「β 値」を注釈として表示し、そこから数直線上の α 値と β 値に矢印を表示する
- min ノードでは数直線の左上に「α 値」と「β 値」を注釈として表示し、そこから数直線上の α 値と β 値に矢印を表示する
なお、α 値と β 値の注釈を上記のように表示する理由 は以下の通りです。
- そのフレームの α 値と β 値の具体的な値を注釈に表示するスペースが無い
- max ノードではそのフレームでの α 値と β 値は以下の値になる
- α 値はそのフレームでの評価値と α 値の初期値の最大値
- β 値は β 値の初期値
- min ノードではそのフレームでの α 値と β 値は以下の値になる
- α 値は α 値の初期値
- β 値はそのフレームでの評価値と β 値の初期値の最小値
- "update" のフレームでは、α 値と β 値の初期値とそのフレームでの評価値は すべて数直線上の注釈で値が表示されている ので、そのフレームでの α 値と β 値の値 は注釈の どこかに必ず表示されている
- max ノードではそのフレームの α 値は、そのフレームでの評価値以上になるので、数直線上 では必ずそのフレームでの評価値と 同じかそれより右に配 置される。従って、そのフレームの α 値の注釈をそのフレームの評価値の右に表示することで、その 2 つの注釈から数直線上に伸びる矢印が 交差してみづらくなることが無い
- min ノードでも同様の理由で注釈から伸びる矢印が交差しない
わかりづらいと思いますので、max ノードでの "update" のフレームの数直線の表示例 を下図に示します。下記の式が常に成り立つ ので、下図の注釈から数直線に伸びる 3 本の矢印が交差してみづらくなることはありません。
そのフレームの評価値 ≦ そのフレームの α 値 < そのフレームの β 値
α 狩りや β 狩りが行なわれた場合に表示する「α 狩り」や「β 狩り」は真ん中の 4 行目に表示することにします。
update_frameinfo の修正
下記は上記を表示するように update_frameinfo を修正したプログラムです。
- 11 ~ 35 行目：αβ 法の場合で "update" のフレームの処理を記述する
-
12 ~ 18 行目：このフレームでのノードの評価値の範囲を表す文字列を
score_typeに代入し、18 行目で真ん中の 4 行目のメッセージの末尾にその文字列を追加する - 19 ~ 21 行目：α 狩りまたは β 狩りが行なわれる場合は、真ん中の 5 行目で赤字で「α 狩り」または「β 狩り」を表示するようにする
- 22 ~ 35 行目：α 狩りまたは β 狩りが行われない場合の処理を記述する
- 23 ~ 26 行目：そのフレームの α 値と β 値と、それらの数直線上の座標を計算する
-
27 行目：α 値の注釈を表示する x 座標を以下のように計算する
- max ノードの場合は左端に左揃えで表示する必要があるので、左端の座標を計算する
- min ノードの場合は右端に右揃えで表示する必要があるので右端の座標を元に計算する。その際に β 値の注釈の左に表示するように右端から 1.5 を引いた座標を計算する
- 28 行目：β 値の注釈を表示する x 座標を上記と同様の方法で計算する
- 29 行目：α 値と β 値の注釈を表示する際の文字の揃えを計算する
- 30 ~ 35 行目：α 値と β 値の数直線上の丸と注釈を描画する
- 39 ~ 49 行目："update" のフレームの場合の範囲の説明の表示の処理を記述する
- 40 ~ 43 行目：範囲の説明に max ノードの場合は "fail high (β 狩り)" を、min ノードの場合は "fail low (α 狩り)" を表示するようにする
-
44 ~ 49 行目：12 ~ 17 行目で計算した
score_typeの値を利用して、そのノードの評価値が含まれる範囲を赤字で表示するようにする
1 import matplotlib.patches as patches
2
3 def update_frameinfo(self):
元と同じなので省略
4 # ノードの評価値が更新されたかどうかの表示
5 elif status == "update":
6 if framedata["updated"]:
7 textlist[3] = "評価値の更新"
8 textcolorlist[3] = "red"
9 else:
10 textlist[3] = "評価値の更新なし"
11 if not minimax:
12 if score <= alphaorig:
13 score_type = "fail low"
14 elif score < betaorig:
15 score_type = "exact value"
16 else:
17 score_type = "fail high"
18 textlist[3] += f" ({score_type})"
19 if framedata["ab_pruned"]:
20 textlist[4] = "β 狩り" if maxnode else "α 狩り"
21 textcolorlist[4] = "red"
22 else:
23 alpha = max(alphaorig, score) if maxnode else alphaorig
24 beta = betaorig if maxnode else min(betaorig, score)
25 alpha_coord = calc_coord(alpha)
26 beta_coord = calc_coord(beta)
27 alpha_text_coord = rightx - 1.5 if maxnode else leftx
28 beta_text_coord = rightx if maxnode else leftx + 1.5
29 ha = "right" if maxnode else "left"
30 self.abax.plot(alpha_coord, 0, "or")
31 self.abax.plot(beta_coord, 0, "ob")
32 self.abax.annotate(f"α 値", xy=(alpha_coord, 0),
33 xytext=(alpha_text_coord, 1), arrowprops=arrowprops, ha=ha)
34 self.abax.annotate(f"β 値", xy=(beta_coord, 0),
35 xytext=(beta_text_coord, 1), arrowprops=arrowprops, ha=ha)
元と同じなので省略
36 # 範囲の説明の表示
37 if not minimax:
元と同じなので省略
38 if status == "tt" and framedata["tt_pruned"]:
元と同じなので省略
39 elif status == "update":
40 if maxnode:
41 textlist[2] = "fail high (β 狩り)"
42 else:
43 textlist[0] = "fail low (α 狩り)"
44 if score_type == "fail low":
45 textcolorlist[0] = "red"
46 elif score_type == "exact value":
47 textcolorlist[1] = "red"
48 elif score_type == "fail high":
49 textcolorlist[2] = "red"
50 for i in range(3):
51 rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7),
52 width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
53 self.abax.add_patch(rect)
54 self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])
元と同じなので省略
55
56 Mbtree_Anim.update_frameinfo = update_frameinfo
行番号のないプログラム
import matplotlib.patches as patches
def update_frameinfo(self):
def calc_coord(score):
return min(max(minus_inf, score), plus_inf)
framedata = self.mbtree.ablist_by_score[self.play.value]
status = framedata["status"]
maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
minimax = self.mbtree.minimax
self.abax.clear()
self.abax.set_xlim(-4, 23)
if minimax:
self.abax.set_ylim(-1.5, 1.5)
else:
self.abax.set_ylim(-4.3, 2.3)
self.abax.axis("off")
minus_inf = -3 if self.mbtree.shortest_victory else -2
plus_inf = 4 if self.mbtree.shortest_victory else 2
# 範囲の色分け
if not minimax:
alphaorig = framedata["alphaorig"]
betaorig = framedata["betaorig"]
alphaorig_coord = calc_coord(alphaorig)
betaorig_coord = calc_coord(betaorig)
color = "lightgray" if maxnode else "aqua"
rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphaorig_coord-minus_inf,
height=1, fc=color)
self.abax.add_patch(rect)
rect = patches.Rectangle(xy=(alphaorig_coord, -0.5), width=betaorig_coord-alphaorig_coord,
height=1, fc="yellow")
self.abax.add_patch(rect)
color = "aqua" if maxnode else "lightgray"
rect = patches.Rectangle(xy=(betaorig_coord, -0.5), width=plus_inf-betaorig_coord,
height=1, fc=color)
self.abax.add_patch(rect)
# 数直線の描画
self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
for num in range(minus_inf, plus_inf + 1):
if num == minus_inf:
numtext = "" if self.mbtree.init_ab else "-∞"
elif num == plus_inf:
numtext = "" if self.mbtree.init_ab else "∞"
else:
numtext = num
self.abax.text(num, -1, numtext, ha="center")
# メッセージの表示
if minimax:
linenum = 4
linetop = 1
else:
linenum = 9
linetop = 1.7
textlist = [""] * linenum
textcolorlist = ["black"] * linenum
algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
use_tt = "〇" if self.mbtree.use_tt else "×"
shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
init_ab = "〇" if self.mbtree.init_ab else "×"
textlist[0] = f"{algorithm} 置換表 {use_tt} 最短 {shortest_victory}"
if not self.mbtree.minimax:
textlist[0] += f" 初期値 {init_ab}"
textlist[1] = f"深さ {self.selectednode.mb.move_count} "
if maxnode:
textlist[1] += "max node"
else:
textlist[1] += "min node"
statusdata = {
"start": {
"text": "処理の開始",
"color": "white"
},
"tt": {
"text": "置換表の処理",
"color": "honeydew"
},
"score": {
"text": "子ノードの評価値",
"color": "lightyellow"
},
"update": {
"text": "更新処理",
"color": "lightcyan"
},
"end": {
"text": "評価値の確定",
"color": "lavenderblush"
},
}
textlist[2] = statusdata[status]["text"]
facecolor = statusdata[status]["color"]
arrowprops = { "arrowstyle": "->"}
leftx = -3
rightx = 4
centerx = (leftx + rightx) / 2
# α 値 と β 値の初期値の表示
if not minimax:
if status == "start" or status == "tt":
self.abax.plot(alphaorig_coord, 0, "or")
self.abax.annotate(f"α = {alphaorig}", xy=(alphaorig_coord, 0),
xytext=(leftx, 1.7), arrowprops=arrowprops, ha="left")
self.abax.plot(betaorig_coord, 0, "ob")
self.abax.annotate(f"β = {betaorig}", xy=(betaorig_coord, 0),
xytext=(rightx, 1.7), arrowprops=arrowprops, ha="right")
else:
self.abax.text(leftx, 1.7, f"α = {alphaorig}", ha="left")
self.abax.text(rightx, 1.7, f"β = {betaorig}", ha="right")
# そのフレームでのノードの評価値の表示
if status in ["score", "update", "end"]:
score = framedata["score"]
score_coord = calc_coord(score)
text_coord = leftx if maxnode else rightx
ha = "left" if maxnode else "right"
self.abax.plot(score_coord, 0, "ok")
self.abax.annotate(f"score = {score}", xy=(score_coord, 0),
xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)
# 子ノードの評価値の表示
if status == "score":
childscore = framedata["childscore"]
childscore_coord = calc_coord(childscore)
text_coord = rightx if maxnode else leftx
ha = "right" if maxnode else "left"
self.abax.plot(childscore_coord, 0, "og")
self.abax.annotate(f"cscore = {childscore}", xy=(childscore_coord, 0),
xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)
# 置換表にデータが登録されていたかどうかの表示
elif status == "tt":
if framedata["registered_in_tt"]:
textlist[3] = "置換表に登録済"
textcolorlist[3] = "red"
if minimax:
score = framedata["lower_bound"]
score_coord = calc_coord(score)
self.abax.plot(score_coord, 0, "om")
self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
xytext=(centerx, 1), arrowprops=arrowprops, ha="center")
else:
if framedata["tt_pruned"]:
lower_bound = framedata["lower_bound"]
upper_bound = framedata["upper_bound"]
if lower_bound == upper_bound:
pruned_type = "exact value"
elif upper_bound <= alphaorig:
pruned_type = "fail low"
elif betaorig <= lower_bound:
pruned_type = "fail high"
textlist[4] = f"置換表による枝狩り ({pruned_type})"
textcolorlist[4] = "red"
else:
if framedata["ab_updated"]:
textlist[5] = "α 値または β 値の初期値の更新"
textcolorlist[4] = "red"
else:
textlist[3] = "置換表に未登録"
# ノードの評価値が更新されたかどうかの表示
elif status == "update":
if framedata["updated"]:
textlist[3] = "評価値の更新"
textcolorlist[3] = "red"
else:
textlist[3] = "評価値の更新なし"
if not minimax:
if score <= alphaorig:
score_type = "fail low"
elif score < betaorig:
score_type = "exact value"
else:
score_type = "fail high"
textlist[3] += f" ({score_type})"
if framedata["ab_pruned"]:
textlist[4] = "β 狩り" if maxnode else "α 狩り"
textcolorlist[4] = "red"
else:
alpha = max(alphaorig, score) if maxnode else alphaorig
beta = betaorig if maxnode else min(betaorig, score)
alpha_coord = calc_coord(alpha)
beta_coord = calc_coord(beta)
alpha_text_coord = rightx - 1.5 if maxnode else leftx
beta_text_coord = rightx if maxnode else leftx + 1.5
ha = "right" if maxnode else "left"
self.abax.plot(alpha_coord, 0, "or")
self.abax.plot(beta_coord, 0, "ob")
self.abax.annotate(f"α 値", xy=(alpha_coord, 0),
xytext=(alpha_text_coord, 1), arrowprops=arrowprops, ha=ha)
self.abax.annotate(f"β 値", xy=(beta_coord, 0),
xytext=(beta_text_coord, 1), arrowprops=arrowprops, ha=ha)
# 置換表に登録したかどうかの表示
elif status == "end":
if self.mbtree.use_tt:
if framedata["registered_in_tt"]:
textlist[3] = "置換表に登録されていたデータを利用"
else:
textlist[3] = "置換表への登録"
textcolorlist[3] = "red"
def draw_bound(lower, upper, y, color):
lower_coord = calc_coord(lower)
upper_coord = calc_coord(upper)
if lower == upper:
self.abax.plot(lower_coord, y, color=color, marker="o")
else:
self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
arrowprops={ "arrowstyle": "<->", "color": color, "linewidth": 1.5})
# 下界と上界に関する表示
if not minimax:
lower_text = ""
upper_text = ""
if status != "start":
lower_bound = framedata["lower_bound"]
upper_bound = framedata["upper_bound"]
if framedata["registered_in_tt"]:
color = "red"
textlist[6] = "置換表のミニマックス値の範囲"
else:
color = "black"
textlist[6] = "ミニマックス値は置換表に未登録"
draw_bound(lower_bound, upper_bound, -2.3, color)
lower_text = f"下界 = {lower_bound}"
upper_text = f"上界 = {upper_bound}"
self.abax.text(leftx, -1.8, lower_text, ha="left")
self.abax.text(rightx, -1.8, upper_text, ha="right")
self.abfig.set_facecolor(facecolor)
for i in range(linenum):
self.abax.text(5, linetop - i * 0.7, textlist[i], c=textcolorlist[i])
num_calculated = framedata["num_calculated"]
num_pruned = framedata["num_pruned"]
num_total = num_calculated + num_pruned
num_ratio = num_calculated / num_total if num_total != 0 else 0
prev_framedata = self.mbtree.ablist_by_score[self.prev_frame]
prev_num_calculated = prev_framedata["num_calculated"]
prev_num_pruned = prev_framedata["num_pruned"]
prev_num_total = prev_num_calculated + prev_num_pruned
diff_num_calculated = num_calculated - prev_num_calculated
diff_num_pruned = num_pruned - prev_num_pruned
diff_num_total = num_total - prev_num_total
diff_num_ratio = diff_num_calculated / diff_num_total if diff_num_total != 0 else 0
textlist = [ "計算済", "枝狩り", "合計", "割合" ]
datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
diff_datalist = [ f"{diff_num_calculated:+d}", f"{diff_num_pruned:+d}",
f"{diff_num_total:+d}", f"{diff_num_ratio * 100:.1f}%"]
for i in range(4):
self.abax.text(15, linetop - i * 0.7, textlist[i])
self.abax.text(19.5, linetop - i * 0.7, datalist[i], ha="right")
self.abax.text(22.5, linetop - i * 0.7, diff_datalist[i], ha="right")
# 範囲の説明の表示
if not minimax:
facecolorlist = [
"lightgray" if maxnode else "aqua",
"yellow",
"aqua" if maxnode else "lightgray",
]
textlist = ["fail low", "exact value", "fail high"]
textcolorlist = ["black", "black", "black"]
if status == "tt" and framedata["tt_pruned"]:
if pruned_type == "fail low":
textcolorlist[0] = "red"
elif pruned_type == "exact value":
textcolorlist[1] = "red"
elif pruned_type == "fail high":
textcolorlist[2] = "red"
elif status == "update":
if maxnode:
textlist[2] = "fail high (β 狩り)"
else:
textlist[0] = "fail low (α 狩り)"
if score_type == "fail low":
textcolorlist[0] = "red"
elif score_type == "exact value":
textcolorlist[1] = "red"
elif score_type == "fail high":
textcolorlist[2] = "red"
for i in range(3):
rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7),
width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
self.abax.add_patch(rect)
self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])
Mbtree_Anim.update_frameinfo = update_frameinfo
修正箇所
import matplotlib.patches as patches
def update_frameinfo(self):
元と同じなので省略
# ノードの評価値が更新されたかどうかの表示
elif status == "update":
if framedata["updated"]:
textlist[3] = "評価値の更新"
textcolorlist[3] = "red"
else:
textlist[3] = "評価値の更新なし"
+ if not minimax:
+ if score <= alphaorig:
+ score_type = "fail low"
+ elif score < betaorig:
+ score_type = "exact value"
+ else:
+ score_type = "fail high"
+ textlist[3] += f" ({score_type})"
+ if framedata["ab_pruned"]:
+ textlist[4] = "β 狩り" if maxnode else "α 狩り"
+ textcolorlist[4] = "red"
+ else:
+ alpha = max(alphaorig, score) if maxnode else alphaorig
+ beta = betaorig if maxnode else min(betaorig, score)
+ alpha_coord = calc_coord(alpha)
+ beta_coord = calc_coord(beta)
+ alpha_text_coord = rightx - 1.5 if maxnode else leftx
+ beta_text_coord = rightx if maxnode else leftx + 1.5
+ ha = "right" if maxnode else "left"
+ self.abax.plot(alpha_coord, 0, "or")
+ self.abax.plot(beta_coord, 0, "ob")
+ self.abax.annotate(f"α 値", xy=(alpha_coord, 0),
+ xytext=(alpha_text_coord, 1), arrowprops=arrowprops, ha=ha)
+ self.abax.annotate(f"β 値", xy=(beta_coord, 0),
+ xytext=(beta_text_coord, 1), arrowprops=arrowprops, ha=ha)
元と同じなので省略
# 範囲の説明の表示
if not minimax:
元と同じなので省略
if status == "tt" and framedata["tt_pruned"]:
元と同じなので省略
+ elif status == "update":
+ if maxnode:
+ textlist[2] = "fail high (β 狩り)"
+ else:
+ textlist[0] = "fail low (α 狩り)"
+ if score_type == "fail low":
+ textcolorlist[0] = "red"
+ elif score_type == "exact value":
+ textcolorlist[1] = "red"
+ elif score_type == "fail high":
+ textcolorlist[2] = "red"
for i in range(3):
rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7),
width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
self.abax.add_patch(rect)
self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])
元と同じなので省略
Mbtree_Anim.update_frameinfo = update_frameinfo
表示の確認
上記の修正後に下記のプログラムを実行して正しく表示されることを確認します。
Mbtree_Anim(mbtree, isscore=True)
まず、max ノード である ゲーム開始時の局面の "update" のフレームの表示を確認します。
下図は 下段の > を 2 回クリック して ゲーム開始時の局面の最初の子ノードの評価値が計算 された "score" の状態の 4061 フレーム目の図で、子ノードの評価値として 0 が計算された ことがわかります。なお、ゲーム開始時の局面のミニマックス値の範囲は置換表に登録されていないことは明らかなので "tt" のフレームの表示は省略しました。
下図は 下段の > をクリック して表示される "update" の状態のフレームの図で、下記のように 正しく表示されることが確認 できます。
- max ノードなので、右下の範囲の説明に「fail high（β 狩り）」が表示される
- ノードの評価値が 0 に更新されたことが下記のように表示される
- 0 は exact value の範囲なので、真ん中の 4 行目に赤字で「評価値の更新（exact value）」が表示される
- 右下の範囲の説明の「exact value」が赤字で表示される
- このフレームの α 値と β 値に関する情報が下記のように表示される
- α 値と β 値を表す丸が正しい位置と色で数直線上に表示される
- max ノードなので α 値と β 値の注釈が数直線の右上に表示される
- 注釈から数直線上への矢印が交差することなく正しく表示される
下図は 上段の > をクリック して表示される 次の子ノードの評価値の計算が開始 される "start" の状態のフレームで、上図のフレームの α 値と β 値 がこのノードの α 値と β 値の初期値として受け継がれた ことが確認できます。
次に、この min ノード での "update" のフレームの表示を確認します。
下図は 下段の > をクリック して表示される "tt" の状態のフレームで 置換表に このノードのミニマックス値の範囲が 登録されていない ことがわかります。
下図は 下段の > をクリック して表示される "score" の状態のフレームの図で、子ノードの評価値として 0 が計算された ことがわかります。
下図は 下段の > をクリック して表示される "update" の状態のフレームの図で、下記のように 正しく表示される ことが確認できます。
- min ノードなので、右下の範囲の説明に「fail low（α 狩り）」が表示される
- ノードの評価値が 0 に更新されたことが下記のように表示される
- 0 は fail low の範囲なので、真ん中の 4 行目に赤字で「評価値の更新（fail low）」が表示される
- 右下の範囲の説明の「fail low（α 狩り）」が赤字で表示される
- α 狩りが行なわれるので真ん中の 5 行目に赤字で「α 狩り」が表示される
- α 狩りが行なわれるので、このフレームの α 値と β 値に関する情報は表示されない
min ノード で α 狩りが行なわれない場合 の表示を確認するために、ゲーム開始時の局面の最初の子ノードの計算が開始 される 2 フレーム目に移動 し、下段の > を 2 回クリック すると下図の "score" の状態のフレームが表示され、子ノードの評価値として 2 が計算されたことがわかります。なお、ゲーム開始時の局面の最初の子ノードのミニマックス値の範囲は置換表に登録されていないことは明らかなので "tt" のフレームの表示は省略しました。
下図は 下段の > をクリック して表示される "update" の状態のフレームの図で、下記のよう に正しく表示される ことが確認できます。
- min ノードなので、右下の範囲の説明に「fail low（α 狩り）」が表示される
- ノードの評価値が 2 に更新されたことが下記のように表示される
- 2 は exact value の範囲なので、真ん中の 4 行目に赤字で「評価値の更新（exact value）」が表示される
- 右下の範囲の説明の「exact value」が赤字で表示される
- このフレームの α 値と β 値に関する情報が下記のように表示される
- α 値と β 値を表す丸が正しい位置と色で数直線上に表示される
- min ノードなので α 値と β 値の注釈が数直線の左上に表示される
- 注釈から数直線上への矢印が交差することなく正しく表示される
まだ確認していない下記の場合の "update" の状態の表示を確認します。
- max ノードでそのノードの評価値が fail low の場合
- max ノードでそのノードの評価値が fail high で β 狩りが行なわれる場合
- min ノードでそのノードの評価値が fail high の場合
説明が長くなるので直前の "score" のフレームの図は省略します。
下図は max ノードで評価値が fail low の場合の "update" の状態の 25 フレーム目の図で、下記のように正しく表示されることが確認できます。なお、先程の例と異なり下図では α 値はそのノードの評価値より大きな値が正しく計算されています。
- max ノードなので、右下の範囲の説明に「fail high（β 狩り）」が表示される
- ノードの評価値が 1 に更新されたことが下記のように表示される
- 1 は fail low の範囲なので、真ん中の 4 行目に赤字で「評価値の更新（fail low）」が表示される
- 右下の範囲の説明の「fail low」が赤字で表示される
- このフレームの α 値と β 値に関する情報が下記のように表示される
- α 値と β 値を表す丸が正しい位置と色で数直線上に表示される
- max ノードなので α 値と β 値の注釈が数直線の右上に表示される
- 注釈から数直線上への矢印が交差することなく正しく表示される
前回の記事で作成したプログラムと同様なので説明は省略しますが、上記の条件を満たすフレームを探す際に、下記のようなプログラムを実行しました。
for i, framedata in enumerate(mbtree.ablist_by_score):
if framedata["status"] == "update":
node = mbtree.nodelist_by_score[i]
maxnode = node.mb.move_count % 2 == 0
score = framedata["score"]
alphaorig = framedata["alphaorig"]
betaorig = framedata["betaorig"]
if maxnode and score <= alphaorig:
print(i)
break
実行結果
25
下記は残りの条件のフレームを探すプログラムです。
max ノードでそのノードの評価値が fail high で β 狩りが行なわれる場合。
for i, framedata in enumerate(mbtree.ablist_by_score):
if framedata["status"] == "update":
node = mbtree.nodelist_by_score[i]
maxnode = node.mb.move_count % 2 == 0
score = framedata["score"]
alphaorig = framedata["alphaorig"]
betaorig = framedata["betaorig"]
if maxnode and score >= betaorig:
print(i)
break
実行結果
71
min ノードでそのノードの評価値が fail high の場合。
for i, framedata in enumerate(mbtree.ablist_by_score):
if framedata["status"] == "update":
node = mbtree.nodelist_by_score[i]
maxnode = node.mb.move_count % 2 == 0
score = framedata["score"]
alphaorig = framedata["alphaorig"]
betaorig = framedata["betaorig"]
if not maxnode and score >= betaorig:
print(i)
break
実行結果
283
下図は max ノード で評価値が fail high で β 狩りが行なわれる場合 の "update" の状態の 71 フレーム目の図で、下記のように正しく表示されることが確認できます。
- max ノードなので、右下の範囲の説明に「fail high（β 狩り）」が表示される
- ノードの評価値が 1 に更新されたことが下記のように表示される
- 1 は fail high の範囲なので、真ん中の 4 行目に赤字で「評価値の更新（fail high）」が表示される
- 右下の範囲の説明の「fail high（β 狩り）」が赤字で表示される
- β 狩りが行なわれるので真ん中の 5 行目に赤字で「β 狩り」が表示される
- β 狩りが行なわれるので、このフレームの α 値と β 値に関する情報は表示されない
下図は min ノード で評価値が fail high の場合 の "update" の状態の 283 フレーム目の図でで、fail high の場合の表示が下記のように正しく表示されることが確認できます。
- min ノードなので、右下の範囲の説明に「fail low（α 狩り）」が表示される
- ノードの評価値が 2 に更新されたことが下記のように表示される
- 2 は fail high の範囲なので、真ん中の 4 行目に赤字で「評価値の更新（fail high）」が表示される
- 右下の範囲の説明の「fail high（β 狩り）」が赤字で表示される
- このフレームの α 値と β 値に関する情報が下記のように表示される
- α 値と β 値を表す丸が正しい位置と色で数直線上に表示される
- min ノードなので α 値と β 値の注釈が数直線の左上に表示される
- 注釈から数直線上への矢印が交差することなく正しく表示される
"update" のフレームで 評価値の更新がされない場合 の確認を忘れていたことに気が付きましたので、確認することにします。ゲーム開始時の局面の全ての子ノードの評価値は 0 なので、ゲーム開始時の局面の 2 つ目の子ノードの評価値が計算された次の "update" のフレーム では 評価値は更新されません。下図は最初のフレームに戻って 下段の > を 5 回クリック して表示されるそのフレームの図で、真ん中の 4 行目に 黒字で「評価値の更新なし（exact value）」が正しく表示される ことが確認できます。
"end" の状態で表示する内容の実装
下記は "end" の状態で表示する内容の再掲です。（※）の部分は実装済なので、それ以外の場合の表示を実装する必要があります。
- （※）数直線上にそのフレームでのノードの評価値を表示
- このノードの評価値の種類によってフレームの状態を以下のように表示する
- fail low の場合は「評価値の確定（fail low）」を表示
- exact value の場合は「評価値の確定（exact value）」を表示
- fail high の場合は「評価値の確定（fail high）」を表示
- 置換表を利用する場合
- 置換表による枝狩りが行われた場合
- （※）黒字で「置換表に登録されていたデータを利用」を表示
- 置換表による枝狩りが行われていない場合
- （※）赤字で「置換表への登録」を表示
- 計算された範囲
- 登録する範囲
- 置換表による枝狩りが行われた場合
また、上記とは別に、以下のような表示の工夫 を行なうことにします。どのように実装すればよいかについて少し考えてみて下さい。
- 右下に表示される範囲の説明のうち、確定したノードの評価値の範囲を赤字で表示する
- "tt" のフレームで 置換表による枝狩りを行わない場合 は、"end" のフレームで置換表の内容を更新する処理3 を行う必要がある。そこで、置換表による枝狩りを行わない場合 は、"end" のフレーム で 計算された範囲 と 登録する範囲 を表示するようにする。また、下界と上界の注釈に表示する 値を、登録する範囲の下界と上界の 値にする
なお、置換表の範囲、計算された範囲、登録する範囲は本記事独自の用語で、以前の記事で説明した 3 種類のミニマックス値の範囲 を 区別できるよう に短く表記した用語です。
| 表記 | 意味 |
|---|---|
| 置換表の範囲 | 置換表に登録されていたミニマックス値の範囲 |
| 計算された範囲 | 子ノードの評価値から計算されたミニマックス値の範囲 |
| 登録する範囲 | 置換表に登録する、上記の 2 つの共通する範囲 |
本記事では上記の計算された範囲と登録する範囲を以下のように表示することにします。
- 計算された範囲を置換表の範囲の下に緑色の図形で表示する
- 計算された範囲の図形の右に（真ん中の 8 行目の位置）に「計算されたミニマックス値」という説明文を表示する
- 登録する範囲を計算された範囲の下に青色の図形で表示する
- 登録する範囲の図形の右に（真ん中の 9 行目の位置）に「置換表に登録したミニマックス値」という説明文を表示する
update_frameinfo の修正
下記は上記を表示するように update_frameinfo を修正したプログラムです。
評価値の種類によって対応する範囲の説明を赤く表示 するという処理は、"update" のフレームでも行っています。そこで、評価値の種類 を "update" のフレームの場合と 同じ score_type という変数に代入 することで、範囲の説明を赤く表示するという処理を 63 ~ 69 行目でまとめて行うという工夫 を行ないました。
-
4 ~ 6 行目：αβ 法の場合は、フレームの状態を表す dict の
"score_type"というキーに評価値の種類を表す文字列が代入されているので、それをscore_typeに代入し、真ん中の 2 行目の末尾に追加する - 8 行目：ミニマックス法では真ん中の 3 行目に表示するメッセージを、置換表に登録されていたかどうかで変えていたが、αβ 法では置換表に登録されていた場合でも置換表の値を更新する場合があるので、置換表による枝狩りが行われているかどうかで判定を行うように修正した
- 15、16、27、28、38、39 行目：数直線の下に表示する下界と上界の注釈とその値を、状況に応じて計算して変数に代入する。なお、"end" の状態で置換表による枝狩りが行われていない場合は、27、28 行目で計算された値を 38、39 行目で上書きする
- 40、41 行目：下界と上界の注釈の表示はこれまでは 28 行目の下に "start" 以外の状態のブロックで行なっていたが、40、41 行目でフレームの状態に関わらずすべての場合でまとめて表示するように修正した
-
29 ~ 39 行目：αβ 法、"end" のフレーム、置換表による枝狩りが行われていないという条件がすべて満たされる場合に、計算された範囲と登録する範囲をフレームの情報を表す dict から取り出し、その図形を前回の記事で定義した
draw_boundを利用して描画する - 36、37 行目：計算された範囲と登録する範囲を説明するメッセージを真ん中の 8、9 行目に表示するようにする
-
63 ~ 69 行目：ノードの評価値の種類を 5 行目で "update" の状態の場合に評価値の種類を計算した
score_typeという同じ名前の変数に代入したので、"update" と "end" の状態で右下の範囲の説明を赤く表示する処理をまとめて行うように修正した
1 def update_frameinfo(self):
元と同じなので省略
2 # 置換表に登録したかどうかの表示
3 elif status == "end":
4 if not minimax:
5 score_type = framedata['score_type']
6 textlist[2] += f"（{score_type}）"
7 if self.mbtree.use_tt:
8 if framedata["tt_pruned"]:
9 textlist[3] = "置換表に登録されていたデータを利用"
10 else:
11 textlist[3] = "置換表への登録"
12 textcolorlist[3] = "red"
元と同じなので省略
13 # 下界と上界に関する表示
14 if not minimax:
15 lower_text = ""
16 upper_text = ""
17 if status != "start":
18 lower_bound = framedata["lower_bound"]
19 upper_bound = framedata["upper_bound"]
20 if framedata["registered_in_tt"]:
21 color = "red"
22 textlist[6] = "置換表のミニマックス値の範囲"
23 else:
24 color = "black"
25 textlist[6] = "ミニマックス値は置換表に未登録"
26 draw_bound(lower_bound, upper_bound, -2.3, color)
27 lower_text = f"下界 = {lower_bound}"
28 upper_text = f"上界 = {upper_bound}"
29 if status == "end" and not framedata["tt_pruned"]:
30 clower_bound = framedata["clower_bound"]
31 cupper_bound = framedata["cupper_bound"]
32 draw_bound(clower_bound, cupper_bound, -3.0, "green")
33 tlower_bound = framedata["tlower_bound"]
34 tupper_bound = framedata["tupper_bound"]
35 draw_bound(tlower_bound, tupper_bound, -3.7, "blue")
36 textlist[7] = "計算されたミニマックス値"
37 textlist[8] = "置換表に登録したミニマックス値"
38 lower_text = f"下界 = {tlower_bound}"
39 upper_text = f"上界 = {tupper_bound}"
40 self.abax.text(leftx, -1.8, lower_text, ha="left")
41 self.abax.text(rightx, -1.8, upper_text, ha="right")
元と同じなので省略
42 # 範囲の説明の表示
43 if not minimax:
44 facecolorlist = [
45 "lightgray" if maxnode else "aqua",
46 "yellow",
47 "aqua" if maxnode else "lightgray",
48 ]
49 textlist = ["fail low", "exact value", "fail high"]
50 textcolorlist = ["black", "black", "black"]
51 if status == "tt" and framedata["tt_pruned"]:
52 if pruned_type == "fail low":
53 textcolorlist[0] = "red"
54 elif pruned_type == "exact value":
55 textcolorlist[1] = "red"
56 elif pruned_type == "fail high":
57 textcolorlist[2] = "red"
58 elif status == "update":
59 if maxnode:
60 textlist[2] = "fail high (β 狩り)"
61 else:
62 textlist[0] = "fail low (α 狩り)"
63 if status == "update" or status == "end":
64 if score_type == "fail low":
65 textcolorlist[0] = "red"
66 elif score_type == "exact value":
67 textcolorlist[1] = "red"
68 elif score_type == "fail high":
69 textcolorlist[2] = "red"
70 for i in range(3):
71 rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7),
72 width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
73 self.abax.add_patch(rect)
74 self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])
75
76 Mbtree_Anim.update_frameinfo = update_frameinfo
行番号のないプログラム
def update_frameinfo(self):
def calc_coord(score):
return min(max(minus_inf, score), plus_inf)
framedata = self.mbtree.ablist_by_score[self.play.value]
status = framedata["status"]
maxnode = self.selectednode.mb.turn == Marubatsu.CIRCLE
minimax = self.mbtree.minimax
self.abax.clear()
self.abax.set_xlim(-4, 23)
if minimax:
self.abax.set_ylim(-1.5, 1.5)
else:
self.abax.set_ylim(-4.3, 2.3)
self.abax.axis("off")
minus_inf = -3 if self.mbtree.shortest_victory else -2
plus_inf = 4 if self.mbtree.shortest_victory else 2
# 範囲の色分け
if not minimax:
alphaorig = framedata["alphaorig"]
betaorig = framedata["betaorig"]
alphaorig_coord = calc_coord(alphaorig)
betaorig_coord = calc_coord(betaorig)
color = "lightgray" if maxnode else "aqua"
rect = patches.Rectangle(xy=(minus_inf, -0.5), width=alphaorig_coord-minus_inf,
height=1, fc=color)
self.abax.add_patch(rect)
rect = patches.Rectangle(xy=(alphaorig_coord, -0.5), width=betaorig_coord-alphaorig_coord,
height=1, fc="yellow")
self.abax.add_patch(rect)
color = "aqua" if maxnode else "lightgray"
rect = patches.Rectangle(xy=(betaorig_coord, -0.5), width=plus_inf-betaorig_coord,
height=1, fc=color)
self.abax.add_patch(rect)
# 数直線の描画
self.abax.plot(range(minus_inf, plus_inf + 1), [0] * (plus_inf + 1 - minus_inf) , "|-k")
for num in range(minus_inf, plus_inf + 1):
if num == minus_inf:
numtext = "" if self.mbtree.init_ab else "-∞"
elif num == plus_inf:
numtext = "" if self.mbtree.init_ab else "∞"
else:
numtext = num
self.abax.text(num, -1, numtext, ha="center")
# メッセージの表示
if minimax:
linenum = 4
linetop = 1
else:
linenum = 9
linetop = 1.7
textlist = [""] * linenum
textcolorlist = ["black"] * linenum
algorithm = "mm 法" if self.mbtree.minimax else "αβ法"
use_tt = "〇" if self.mbtree.use_tt else "×"
shortest_victory = "〇" if self.mbtree.shortest_victory else "×"
init_ab = "〇" if self.mbtree.init_ab else "×"
textlist[0] = f"{algorithm} 置換表 {use_tt} 最短 {shortest_victory}"
if not self.mbtree.minimax:
textlist[0] += f" 初期値 {init_ab}"
textlist[1] = f"深さ {self.selectednode.mb.move_count} "
if maxnode:
textlist[1] += "max node"
else:
textlist[1] += "min node"
statusdata = {
"start": {
"text": "処理の開始",
"color": "white"
},
"tt": {
"text": "置換表の処理",
"color": "honeydew"
},
"score": {
"text": "子ノードの評価値",
"color": "lightyellow"
},
"update": {
"text": "更新処理",
"color": "lightcyan"
},
"end": {
"text": "評価値の確定",
"color": "lavenderblush"
},
}
textlist[2] = statusdata[status]["text"]
facecolor = statusdata[status]["color"]
arrowprops = { "arrowstyle": "->"}
leftx = -3
rightx = 4
centerx = (leftx + rightx) / 2
# α 値 と β 値の初期値の表示
if not minimax:
if status == "start" or status == "tt":
self.abax.plot(alphaorig_coord, 0, "or")
self.abax.annotate(f"α = {alphaorig}", xy=(alphaorig_coord, 0),
xytext=(leftx, 1.7), arrowprops=arrowprops, ha="left")
self.abax.plot(betaorig_coord, 0, "ob")
self.abax.annotate(f"β = {betaorig}", xy=(betaorig_coord, 0),
xytext=(rightx, 1.7), arrowprops=arrowprops, ha="right")
else:
self.abax.text(leftx, 1.7, f"α = {alphaorig}", ha="left")
self.abax.text(rightx, 1.7, f"β = {betaorig}", ha="right")
# そのフレームでのノードの評価値の表示
if status in ["score", "update", "end"]:
score = framedata["score"]
score_coord = calc_coord(score)
text_coord = leftx if maxnode else rightx
ha = "left" if maxnode else "right"
self.abax.plot(score_coord, 0, "ok")
self.abax.annotate(f"score = {score}", xy=(score_coord, 0),
xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)
# 子ノードの評価値の表示
if status == "score":
childscore = framedata["childscore"]
childscore_coord = calc_coord(childscore)
text_coord = rightx if maxnode else leftx
ha = "right" if maxnode else "left"
self.abax.plot(childscore_coord, 0, "og")
self.abax.annotate(f"cscore = {childscore}", xy=(childscore_coord, 0),
xytext=(text_coord, 1), arrowprops=arrowprops, ha=ha)
# 置換表にデータが登録されていたかどうかの表示
elif status == "tt":
if framedata["registered_in_tt"]:
textlist[3] = "置換表に登録済"
textcolorlist[3] = "red"
if minimax:
score = framedata["lower_bound"]
score_coord = calc_coord(score)
self.abax.plot(score_coord, 0, "om")
self.abax.annotate(f"置換表の評価値 = {score}", xy=(score_coord, 0),
xytext=(centerx, 1), arrowprops=arrowprops, ha="center")
else:
if framedata["tt_pruned"]:
lower_bound = framedata["lower_bound"]
upper_bound = framedata["upper_bound"]
if lower_bound == upper_bound:
pruned_type = "exact value"
elif upper_bound <= alphaorig:
pruned_type = "fail low"
elif betaorig <= lower_bound:
pruned_type = "fail high"
textlist[4] = f"置換表による枝狩り ({pruned_type})"
textcolorlist[4] = "red"
else:
if framedata["ab_updated"]:
textlist[5] = "α 値または β 値の初期値の更新"
textcolorlist[4] = "red"
else:
textlist[3] = "置換表に未登録"
# ノードの評価値が更新されたかどうかの表示
elif status == "update":
if framedata["updated"]:
textlist[3] = "評価値の更新"
textcolorlist[3] = "red"
else:
textlist[3] = "評価値の更新なし"
if not minimax:
if score <= alphaorig:
score_type = "fail low"
elif score < betaorig:
score_type = "exact value"
else:
score_type = "fail high"
textlist[3] += f" ({score_type})"
if framedata["ab_pruned"]:
textlist[4] = "β 狩り" if maxnode else "α 狩り"
textcolorlist[4] = "red"
else:
alpha = max(alphaorig, score) if maxnode else alphaorig
beta = betaorig if maxnode else min(betaorig, score)
alpha_coord = calc_coord(alpha)
beta_coord = calc_coord(beta)
alpha_text_coord = rightx - 1.5 if maxnode else leftx
beta_text_coord = rightx if maxnode else leftx + 1.5
ha = "right" if maxnode else "left"
self.abax.plot(alpha_coord, 0, "or")
self.abax.plot(beta_coord, 0, "ob")
self.abax.annotate(f"α 値", xy=(alpha_coord, 0),
xytext=(alpha_text_coord, 1), arrowprops=arrowprops, ha=ha)
self.abax.annotate(f"β 値", xy=(beta_coord, 0),
xytext=(beta_text_coord, 1), arrowprops=arrowprops, ha=ha)
# 置換表に登録したかどうかの表示
elif status == "end":
if not minimax:
score_type = framedata['score_type']
textlist[2] += f"（{score_type}）"
if self.mbtree.use_tt:
if framedata["registered_in_tt"]:
textlist[3] = "置換表に登録されていたデータを利用"
else:
textlist[3] = "置換表への登録"
textcolorlist[3] = "red"
def draw_bound(lower, upper, y, color):
lower_coord = calc_coord(lower)
upper_coord = calc_coord(upper)
if lower == upper:
self.abax.plot(lower_coord, y, color=color, marker="o")
else:
self.abax.annotate(f"", xy=(lower_coord, y), xytext=(upper_coord, y),
arrowprops={ "arrowstyle": "<->", "color": color, "linewidth": 1.5})
# 下界と上界に関する表示
if not minimax:
lower_text = ""
upper_text = ""
if status != "start":
lower_bound = framedata["lower_bound"]
upper_bound = framedata["upper_bound"]
if framedata["registered_in_tt"]:
color = "red"
textlist[6] = "置換表のミニマックス値の範囲"
else:
color = "black"
textlist[6] = "ミニマックス値は置換表に未登録"
draw_bound(lower_bound, upper_bound, -2.3, color)
lower_text = f"下界 = {lower_bound}"
upper_text = f"上界 = {upper_bound}"
if status == "end" and not framedata["tt_pruned"]:
clower_bound = framedata["clower_bound"]
cupper_bound = framedata["cupper_bound"]
draw_bound(clower_bound, cupper_bound, -3.0, "green")
tlower_bound = framedata["tlower_bound"]
tupper_bound = framedata["tupper_bound"]
draw_bound(tlower_bound, tupper_bound, -3.7, "blue")
textlist[7] = "計算されたミニマックス値"
textlist[8] = "置換表に登録したミニマックス値"
lower_text = f"下界 = {tlower_bound}"
upper_text = f"上界 = {tupper_bound}"
self.abax.text(leftx, -1.8, lower_text, ha="left")
self.abax.text(rightx, -1.8, upper_text, ha="right")
self.abfig.set_facecolor(facecolor)
for i in range(linenum):
self.abax.text(5, linetop - i * 0.7, textlist[i], c=textcolorlist[i])
num_calculated = framedata["num_calculated"]
num_pruned = framedata["num_pruned"]
num_total = num_calculated + num_pruned
num_ratio = num_calculated / num_total if num_total != 0 else 0
prev_framedata = self.mbtree.ablist_by_score[self.prev_frame]
prev_num_calculated = prev_framedata["num_calculated"]
prev_num_pruned = prev_framedata["num_pruned"]
prev_num_total = prev_num_calculated + prev_num_pruned
diff_num_calculated = num_calculated - prev_num_calculated
diff_num_pruned = num_pruned - prev_num_pruned
diff_num_total = num_total - prev_num_total
diff_num_ratio = diff_num_calculated / diff_num_total if diff_num_total != 0 else 0
textlist = [ "計算済", "枝狩り", "合計", "割合" ]
datalist = [ num_calculated, num_pruned, num_total, f"{num_ratio * 100:.1f}%"]
diff_datalist = [ f"{diff_num_calculated:+d}", f"{diff_num_pruned:+d}",
f"{diff_num_total:+d}", f"{diff_num_ratio * 100:.1f}%"]
for i in range(4):
self.abax.text(15, linetop - i * 0.7, textlist[i])
self.abax.text(19.5, linetop - i * 0.7, datalist[i], ha="right")
self.abax.text(22.5, linetop - i * 0.7, diff_datalist[i], ha="right")
# 範囲の説明の表示
if not minimax:
facecolorlist = [
"lightgray" if maxnode else "aqua",
"yellow",
"aqua" if maxnode else "lightgray",
]
textlist = ["fail low", "exact value", "fail high"]
textcolorlist = ["black", "black", "black"]
if status == "tt" and framedata["tt_pruned"]:
if pruned_type == "fail low":
textcolorlist[0] = "red"
elif pruned_type == "exact value":
textcolorlist[1] = "red"
elif pruned_type == "fail high":
textcolorlist[2] = "red"
elif status == "update":
if maxnode:
textlist[2] = "fail high (β 狩り)"
else:
textlist[0] = "fail low (α 狩り)"
if status == "update" or status == "end":
if score_type == "fail low":
textcolorlist[0] = "red"
elif score_type == "exact value":
textcolorlist[1] = "red"
elif score_type == "fail high":
textcolorlist[2] = "red"
for i in range(3):
rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7),
width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
self.abax.add_patch(rect)
self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])
Mbtree_Anim.update_frameinfo = update_frameinfo
修正箇所
def update_frameinfo(self):
元と同じなので省略
# 置換表に登録したかどうかの表示
elif status == "end":
+ if not minimax:
+ score_type = framedata['score_type']
+ textlist[2] += f"（{score_type}）"
if self.mbtree.use_tt:
- if framedata["registered_in_tt"]:
+ if framedata["tt_pruned"]:
textlist[3] = "置換表に登録されていたデータを利用"
else:
textlist[3] = "置換表への登録"
textcolorlist[3] = "red"
元と同じなので省略
# 下界と上界に関する表示
if not minimax:
lower_text = ""
upper_text = ""
if status != "start":
lower_bound = framedata["lower_bound"]
upper_bound = framedata["upper_bound"]
if framedata["registered_in_tt"]:
color = "red"
textlist[6] = "置換表のミニマックス値の範囲"
else:
color = "black"
textlist[6] = "ミニマックス値は置換表に未登録"
draw_bound(lower_bound, upper_bound, -2.3, color)
lower_text = f"下界 = {lower_bound}"
upper_text = f"上界 = {upper_bound}"
- self.abax.text(leftx, -1.8, lower_text, ha="left")
- self.abax.text(rightx, -1.8, upper_text, ha="right")
+ if status == "end" and not framedata["tt_pruned"]:
+ clower_bound = framedata["clower_bound"]
+ cupper_bound = framedata["cupper_bound"]
+ draw_bound(clower_bound, cupper_bound, -3.0, "green")
+ tlower_bound = framedata["tlower_bound"]
+ tupper_bound = framedata["tupper_bound"]
+ draw_bound(tlower_bound, tupper_bound, -3.7, "blue")
+ textlist[7] = "計算されたミニマックス値"
+ textlist[8] = "置換表に登録したミニマックス値"
+ lower_text = f"下界 = {tlower_bound}"
+ upper_text = f"上界 = {tupper_bound}"
+ self.abax.text(leftx, -1.8, lower_text, ha="left")
+ self.abax.text(rightx, -1.8, upper_text, ha="right")
元と同じなので省略
# 範囲の説明の表示
if not minimax:
facecolorlist = [
"lightgray" if maxnode else "aqua",
"yellow",
"aqua" if maxnode else "lightgray",
]
textlist = ["fail low", "exact value", "fail high"]
textcolorlist = ["black", "black", "black"]
if status == "tt" and framedata["tt_pruned"]:
if pruned_type == "fail low":
textcolorlist[0] = "red"
elif pruned_type == "exact value":
textcolorlist[1] = "red"
elif pruned_type == "fail high":
textcolorlist[2] = "red"
elif status == "update":
if maxnode:
textlist[2] = "fail high (β 狩り)"
else:
textlist[0] = "fail low (α 狩り)"
- if score_type == "fail low":
- textcolorlist[0] = "red"
- elif score_type == "exact value":
- textcolorlist[1] = "red"
- elif score_type == "fail high":
- textcolorlist[2] = "red"
+ if status == "update" or status == "end":
+ if score_type == "fail low":
+ textcolorlist[0] = "red"
+ elif score_type == "exact value":
+ textcolorlist[1] = "red"
+ elif score_type == "fail high":
+ textcolorlist[2] = "red"
for i in range(3):
rect = patches.Rectangle(xy=(15, linetop - 0.1 - (i + 5) * 0.7),
width=0.8, height=0.5, fc=facecolorlist[i], ec="k")
self.abax.add_patch(rect)
self.abax.text(16.2, linetop - (i + 5) * 0.7, textlist[i], c=textcolorlist[i])
Mbtree_Anim.update_frameinfo = update_frameinfo
表示の確認
上記の修正後に下記のプログラムを実行して正しく表示されることを確認します。
Mbtree_Anim(mbtree, isscore=True)
まず、置換表にミニマックス値の範囲が記録されていない場合 の表示の確認として、ゲーム開始時の局面の表示を確認 します。
下記は最初の "start" の状態のフレームで、これまでと同様に 正しく表示される ことが確認できます。
下記は 下段の > をクリック して表示されるゲーム開始時の局面の "tt"、"score"、"update" のフレームの表示で、いずれも数直線の下に表示される 下界と上界の注釈と範囲が正しく表示される ことが確認できます。
下記は 下段の >> をクリック 表示されるゲーム開始時の局面の "end" のフレームの表示で、このノードの評価値 が exact value の範囲である 0 に確定 しており、下記のように正しい表示が行われていることが確認できます。
- 確定した評価値が exact value なので以下の表示が行われる
- 真ん中の 3 行目に「評価値の確定（exact value）」が表示される
- 計算された範囲である 0 の位置に緑色の丸で表示され、その右に「計算されたミニマックス値」という説明文が表示される
- 右下の範囲の説明の「exact value」が赤色で表示される
- 置換表による枝狩りが行われなかったため真ん中の 4 行目に赤字で「置換表への登録」が表示される
- 登録する範囲は置換表の範囲と計算された範囲の共通する部分なので下界と上界は 0 となり以下の内容が表示される
- 登録する範囲が 0 の位置に青色の丸で表示される
- その右に「置換表に登録したミニマックス値」という説明文が表示される
- 下界と上界の注釈の値に、登録する範囲の下界と上界の値である 0 が表示される
次に、置換表による枝狩りが行われるノードの表示を確認します。
以前の記事で説明したように、ゲーム開始時の局面の 3 つ目の子ノードは 1 つ目の子ノードの同一局面なので、そのノードのミニマックス値の範囲は置換表に登録されています。
下図はそのノードの "tt" のフレームで、置換表にミニマックス値の範囲として下界と上界が等しい exact value に分類される値が登録されているので置換表による枝狩りが行われます。そのことが下記のように正しく表示されています。
- 真ん中の 4 行目に赤字で「置換表に登録済」が表示される
- 真ん中の 5 行目に赤字で「置換表による枝狩り（exact value）」が表示される
従って、その次のフレームは下図のように "end" のフレームとなり、下記のように正しい表示が行われていることが確認できます。
- 真ん中の 4 行目に黒字で「置換表に登録されていたデータを利用」が表示される
- 数直線の下には置換表の範囲のみが表示される
最後に、置換表にミニマックス値が登録されているが、置換表による枝狩りが行われないノードの表示を確認します。下記はそのフレームを探すプログラムです。
for i, framedata in enumerate(mbtree.ablist_by_score):
if framedata["status"] == "end":
if not framedata["tt_pruned"] and framedata["registered_in_tt"]:
print(i)
break
実行結果
72
下記は上記で見つけた 72 フレーム目の図で、下記のように正しい表示が行われていることが確認できます。
- 真ん中の 4 行目に黒字で「置換表に登録されていたデータを利用」が表示される
- 数直線の下に計算された範囲と登録された範囲が表示される
- 登録された範囲に置換表の範囲と計算された範囲の共通する部分が正しく計算されている
今回の記事のまとめ
今回の記事では前回の記事で説明したバグを修正し、αβ 法の視覚化 のための Mbtree_Anim の修正を完了 しました。余裕がある方は、様々なフレームを表示して αβ 法の視覚化がうまく行われていることを確認してみて下さい。
また、もっと良い視覚化の方法を思いついた人は是非実装してみて下さい。その際はコメントでその方法を紹介して頂けるとうれしいです。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| tree.py | 本記事で更新した tree_new.py |
| ai.py | 本記事で更新した ai_new.py |
次回の記事