目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| test.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義 |
| tree.py | ゲーム木に関する Node、Mbtree クラスなどの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
ミニマックス値の推定値の精度と MTD(f) 法の効率の関係の検証
前回の記事ではすべての局面でミニマックス値を 0 と推定した状態での MTD(f) 法の効率を検証しました。
以前の記事で MTD(f) 法 では 推定したミニマックス値の精度が高いことが重要 であると説明しましたので、今回の記事では最初にそのことを検証することにします。
具体的には ミニマックス値の推定値の精度と MTD(F) 法の効率の関係 について、以下の条件で検証します。
- 最短の勝利を目指さない場合の評価値の範囲が -1 ~ 1 と狭いため、より広い -2 ~ 3 を評価値として計算する 最短の勝利を目指す場合 で計算を行う
- MTD(f) 法は置換表の利用を前提とするアルゴリズムなので置換表を利用する
- 初期設定のミニマックス値の範囲が最も広くなるように、α 値と β 値の初期値を負の無限大と正の無限大とする
- ゲーム開始時の局面に対して、-2 ~ 3 の範囲の整数の値を ミニマックス値として 推定 して MTD(f) 法で計算を行ない、それらの結果を比較 する
検証を行うプログラムの実行と問題点
下記は、その計算を行うプログラムですが、実行結果のようにウィンドウや αβ 値などで小数点以下の数値が表示されたりされなかったりする場合があり、表示が縦に揃わないという問題がある ことが判明しました。
-
5 行目：-2 ~ 3 の範囲の整数でミニマックス値の推定値である
fを増加しながら繰り返し処理を行う - 7、8 行目：上記の設定で MTD(f) 法の計算を行ない、評価値が計算された数などのデバッグ表示を行う
- 9 行目：空行を表示することで、それぞれの結果の間を開けて見やすいようにした
1 from ai import ai_mtdf
2 from marubatsu import Marubatsu
3
4 mb = Marubatsu()
5 for f in range(-2, 4):
6 print(f"f = {f}")
7 ai_mtdf(mb, f=f, shortest_victory=True, use_tt=True, calc_score=True,
8 calc_count=True, debug=True)
9 print()
行番号のないプログラム
from ai import ai_mtdf
from marubatsu import Marubatsu
mb = Marubatsu()
for f in range(-2, 4):
print(f"f = {f}")
ai_mtdf(mb, f=f, shortest_victory=True, use_tt=True, calc_score=True,
calc_count=True, debug=True)
print()
実行結果
f = -2
count | ウィンドウ | αβ 値 | type | MM の範囲
171/ 171 | (-3, -2) | -2.0 | fail high | [-2.0, inf]
171/ 342 | (-2.0, -1.0) | -1.0 | fail high | [-1.0, inf]
206/ 548 | (-1.0, 0.0) | 0 | fail high | [ 0, inf]
520/ 1068 | ( 0, 1) | 0 | fail low | [ 0, 0]
略
ai_mtdf のデバッグ表示の修正
評価値は整数のみが計算される ので、下記のプログラムのように ai_mtdf のデバッグ表示で 小数点以下の数値が表示されないように修正 することにします。
- 10 行目：書式指定 に 2.0f や 4.0f を指定することで、小数点以下の数値を表示しないように修正した
1 from ai import ai_by_score, dprint
2 from copy import deepcopy
3
4 @ai_by_score
5 def ai_mtdf(mb, debug=False, shortest_victory=False, init_ab=False, use_tt=False,
6 f=0, ai_for_mo=None, params={}, sort_allnodes=False, calc_count=False):
元と同じなので省略
7 tt = {}
8 dprint(debug, " count | ウィンドウ | αβ 値 | type | MM の範囲")
9 while lbound != ubound:
元と同じなので省略
10 dprint(debug, f"{count - prevcount:5.0f}/{count:5.0f} | ({beta - 1:2.0f}, {beta:2.0f}) | {f:2.0f} | {type} | [{lbound:4.0f}, {ubound:4.0f}]")
元と同じなので省略
行番号のないプログラム
from ai import ai_by_score, dprint
from copy import deepcopy
@ai_by_score
def ai_mtdf(mb, debug=False, shortest_victory=False, init_ab=False, use_tt=False,
f=0, ai_for_mo=None, params={}, sort_allnodes=False, calc_count=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
if use_tt:
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 ai_for_mo is not None:
if sort_allnodes:
score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
legal_moves = [x[0] for x in score_by_move_list]
else:
legal_moves = mborig.calc_legal_moves()
bestmove = ai_for_mo(mborig, rand=False, **params)
index = legal_moves.index(bestmove)
legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
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
if use_tt:
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
lbound = min_score if init_ab else float("-inf")
ubound = max_score if init_ab else float("inf")
tt = {}
dprint(debug, " count | ウィンドウ | αβ 値 | type | MM の範囲")
while lbound != ubound:
beta = f + 1 if lbound == f else f
prevcount = count
f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
if f >= beta:
lbound = f
type = "fail high"
else:
ubound = f
type = "fail low "
dprint(debug, f"{count - prevcount:5.0f}/{count:5.0f} | ({beta - 1:2.0f}, {beta:2.0f}) | {f:2.0f} | {type} | [{lbound:4.0f}, {ubound:4.0f}]")
score = f
if calc_count:
return count
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
修正箇所
from ai import ai_by_score, dprint
from copy import deepcopy
@ai_by_score
def ai_mtdf(mb, debug=False, shortest_victory=False, init_ab=False, use_tt=False,
f=0, ai_for_mo=None, params={}, sort_allnodes=False, calc_count=False):
元と同じなので省略
tt = {}
dprint(debug, " count | ウィンドウ | αβ 値 | type | MM の範囲")
while lbound != ubound:
元と同じなので省略
- dprint(debug, f"{count - prevcount:5}/{count:5} | ({beta - 1:2}, {beta:2}) | {f:2} | {type} | [{lbound:4}, {ubound:4}]")
+ dprint(debug, f"{count - prevcount:5.0f}/{count:5.0f} | ({beta - 1:2.0f}, {beta:2.0f}) | {f:2.0f} | {type} | [{lbound:4.0f}, {ubound:4.0f}]")
元と同じなので省略
検証の再実行
上記の修正後に改めて下記のプログラムを実行すると、下記のような実行結果が表示されます。以前の記事で説明したように、null window search が行なわれるたび に 必ずミニマックス値の範囲が狭まり1、最後には 下界と上界がミニマックス値に等しくなる ことが確認できます。
for f in range(-2, 4):
print(f"f = {f}")
ai_mtdf(mb, f=f, shortest_victory=True, use_tt=True, calc_score=True,
calc_count=True, debug=True)
print()
実行結果
f = -2
count | ウィンドウ | αβ 値 | type | MM の範囲
171/ 171 | (-3, -2) | -2 | fail high | [ -2, inf]
171/ 342 | (-2, -1) | -1 | fail high | [ -1, inf]
206/ 548 | (-1, 0) | 0 | fail high | [ 0, inf]
520/ 1068 | ( 0, 1) | 0 | fail low | [ 0, 0]
f = -1
count | ウィンドウ | αβ 値 | type | MM の範囲
261/ 261 | (-2, -1) | -1 | fail high | [ -1, inf]
206/ 467 | (-1, 0) | 0 | fail high | [ 0, inf]
520/ 987 | ( 0, 1) | 0 | fail low | [ 0, 0]
f = 0
count | ウィンドウ | αβ 値 | type | MM の範囲
356/ 356 | (-1, 0) | 0 | fail high | [ 0, inf]
521/ 877 | ( 0, 1) | 0 | fail low | [ 0, 0]
f = 1
count | ウィンドウ | αβ 値 | type | MM の範囲
700/ 700 | ( 0, 1) | 0 | fail low | [-inf, 0]
118/ 818 | (-1, 0) | 0 | fail high | [ 0, 0]
f = 2
count | ウィンドウ | αβ 値 | type | MM の範囲
661/ 661 | ( 1, 2) | 1 | fail low | [-inf, 1]
236/ 897 | ( 0, 1) | 0 | fail low | [-inf, 0]
124/ 1021 | (-1, 0) | 0 | fail high | [ 0, 0]
f = 3
count | ウィンドウ | αβ 値 | type | MM の範囲
517/ 517 | ( 2, 3) | 2 | fail low | [-inf, 2]
493/ 1010 | ( 1, 2) | 1 | fail low | [-inf, 1]
256/ 1266 | ( 0, 1) | 0 | fail low | [-inf, 0]
125/ 1391 | (-1, 0) | 0 | fail high | [ 0, 0]
下記は上記の実行結果をまとめた表です。ノードの数 の列は 評価値が計算されたノードの数、nw の回数 は null window search を行なった回数 を表します。それ以外の列の意味についてはこの後で説明します。
| f | 絶対誤差 | ノードの数 | nw の回数 |
f の推移 |
|---|---|---|---|---|
| -2 | 2 | 1068 | 4 | -2 → -2 → -1 → 0 → 0 |
| -1 | 1 | 987 | 3 | -1 → -1 → 0 → 0 |
| 0 | 0 | 877 | 2 | 0 → 0 → 0 |
| 1 | 1 | 818 | 2 | 1 → 0 → 0 |
| 2 | 2 | 1021 | 3 | 2 → 1 → 0 → 0 |
| 3 | 3 | 1391 | 4 | 3 → 2 → 1 → 0 → 0 |
精度を表す指標の一つ に正確な値との差を計算する 誤差（error）があります。誤差が 0 の場合が正確な値 なので 精度が最も高く、0 から離れるほど精度が低い ことを表します。
誤差は正の値と負の値があるので、その 絶対値（absolute value）を計算した 絶対誤差（absolute error）を精度の指標とする場合があります。絶対誤差の場合は 0 が精度が最も高く、大きい程精度が低い という性質があり、符号を気にすることなく精度を表すことができる ので実際に良く使われます。そこで、上記の表には絶対誤差の列を作りました。
〇×ゲームの ゲーム開始時の局面 は引き分けの局面なので、その ミニマックス値は 0 です。そのため絶対誤差は f - 0 = f の絶対値で計算されるので、 絶対誤差の列 には f の絶対値と同じ値を表記 しました。
日本語で 誤差と表記 した場合は 絶対誤差を表す場合が多い のではないかと思います。例えば誤差が -1 から -10 になった場合は、数値としては減っていますが、精度が減っている ので 誤差は増えていると説明される ことがあります。この「誤差が増えている」という表記の誤差は絶対誤差を表します。
MTD(f) 法は 最初にミニマックス値として推定した f を、null window search で計算した αβ 値で更新 していくことで 最終的に f にミニマックス値が計算される というアルゴリズムです。そこで、f の推移の列には f がミニマックス値に向けて 更新されていく様子 を表記することにしました。最初に推定した数値を表記する ので f の推移には null window search の回数 + 1 個 の数値が表記されます。
検証結果の考察
下記は先ほどの表の再掲です。
| f | 絶対誤差 | ノードの数 | nw の回数 |
f の推移 |
|---|---|---|---|---|
| -2 | 2 | 1068 | 4 | -2 → -2 → -1 → 0 → 0 |
| -1 | 1 | 987 | 3 | -1 → -1 → 0 → 0 |
| 0 | 0 | 877 | 2 | 0 → 0 → 0 |
| 1 | 1 | 818 | 2 | 1 → 0 → 0 |
| 2 | 2 | 1021 | 3 | 2 → 1 → 0 → 0 |
| 3 | 3 | 1391 | 4 | 3 → 2 → 1 → 0 → 0 |
上記の表と先程の実行結果から、以前の記事で説明した下記のように f とミニマックス値の範囲が実際に推移 していくことが確認できます。
-
fの推移の列の値は いずれもミニマックス値である 0 に向かって 値の更新が行われ、ミニマックス値の範囲の 下界または上界がfの値で更新 される - 最後から 2 番目の null window search で
fがミニマックス値で更新 され、ミニマックス値の範囲の 下界または上界がミニマックス値に更新 される - 最後の null window search によって もう片方のミニマックス値の下界と上界がミニマックス値に更新 されることで 下界と上界が等しくなり、ミニマックス値が計算される
細かい話になりますが、ミニマックス値の推定値を $f$、ミニマックス値を $s$ と表記した場合に下記のような計算が実際に行われることが確認できます。
- $f < s$ の場合は 以前の記事で説明したように、最後から 2 番目までの null window search で
fの値が増える 方向でsに向かって更新 される。ただし、初回 の null window search のみfが変化しない場合がある - $f = s$ の場合は 以前の記事で説明したように、2 回 の null window search が行なわれる
- $f > s$ の場合は 以前の記事で説明したように、初回も含めて最後から 2 番目までの null window search で
fの値が減る 方向でsに向かって更新 される
また、以前の記事で説明したように、null window search の回数と、$f$、$s$ の間には下記の表のような関係があります。
| 条件 | 最小回数 | 最大回数 |
|---|---|---|
| $\boldsymbol{f < s}$ | $2$ | $s - f + 2$ |
| $\boldsymbol{f = s}$ | $2$ | $2$ |
| $\boldsymbol{f > s}$ | $2$ | $f - s + 1$ |
上記の表の最大回数を絶対誤差を利用して表すと下記の表のようになります。
| 条件 | 最小回数 | 最大回数 |
|---|---|---|
| $\boldsymbol{f < s}$ | $2$ | 絶対誤差 + 2 |
| $\boldsymbol{f = s}$ | $2$ | $2$ |
| $\boldsymbol{f > s}$ | $2$ | 絶対誤差 + 1 |
上記の表から、絶対誤差が大きい程 null window search の 最大回数が増える ことがわかります。また、最も精度が高い絶対誤差が 0 の場合は 常に最小回数である 2 回 の null window search が行なわれます。従って、MTD(f) 法では ミニマックス値の精度が高いほど、null window search の 回数が少なくなる という 傾向がある ことがわかります。
下記は先ほどの表から、絶対誤差 と null window search の回数 を抜き出してまとめたものです。平均の列から、実際に 精度が高い（絶対誤差が少ない）ほうが null window search の 回数が少なくなるという傾向がある ことが確認できます。
| 絶対誤差 | nw の回数 | nw の回数の平均 |
|---|---|---|
| 0 | 2 | 2.0 |
| 1 | 2、3 | 2.5 |
| 2 | 3、4 | 3.5 |
| 3 | 4 | 4.0 |
また、null window search の 回数が少ない程、一般的に 評価値を計算するノードの数 が 減ります。下記は先ほどの表から、null window search と評価値を計算したノードの数を抜き出してまとめたものです。平均の列から実際に null window search が少ないほう が計算された ノードの数が少なくなるという傾向がある 事が確認できます。
| nw の回数 | ノードの数 | ノードの数の平均 |
|---|---|---|
| 2 | 877 818 |
847.5 |
| 3 | 987 1021 |
1004.0 |
| 4 | 1068 1391 |
1229.5 |
下記は 絶対誤差と評価値が計算されたノードの数 をまとめた表です。平均の列から実際に 精度が高い（絶対誤差が少ない）ほうが計算された ノードの数が少なくなるという傾向がある ことが確認できます。
| 絶対誤差 | ノードの数 | ノードの数の平均 |
|---|---|---|
| 0 | 877 | 877.0 |
| 1 | 987 818 |
902.5 |
| 2 | 1068 1021 |
1044.5 |
| 3 | 1391 | 1391.0 |
これらのことから、MTD(f) には以下の性質があり、〇× ゲームではゲーム開始時の局面でその性質が正しいことが確認できました。
MTD(f) 法 では、推定したミニマックス値の 精度が高い程 null window search の回数が減り、その結果評価値を計算するノードの数が減るため、効率が高くなる傾向がある。
別の局面での検証
念のため、他の局面 でも同様の検証を行うことにします。
ゲーム開始時の局面では 'f' はミニマックス値に向かって 1 つずつ変化していますが、2 つ以上変化 する場合もあります。下記はゲーム開始時の局面から (1, 1)、(0, 0) に着手を行った局面 に対して 先程と同じ検証 を行うプログラムです。
mb.move(1, 1)
mb.move(0, 0)
for f in range(-2, 4):
print(f"f = {f}")
ai_mtdf(mb, f=f, shortest_victory=True, use_tt=True, calc_score=True, calc_count=True, debug=True)
print()
実行結果
f = -2
count | ウィンドウ | αβ 値 | type | MM の範囲
71/ 71 | (-3, -2) | -2 | fail high | [ -2, inf]
30/ 101 | (-2, -1) | -1 | fail high | [ -1, inf]
58/ 159 | (-1, 0) | 0 | fail high | [ 0, inf]
136/ 295 | ( 0, 1) | 0 | fail low | [ 0, 0]
f = -1
count | ウィンドウ | αβ 値 | type | MM の範囲
83/ 83 | (-2, -1) | -1 | fail high | [ -1, inf]
58/ 141 | (-1, 0) | 0 | fail high | [ 0, inf]
136/ 277 | ( 0, 1) | 0 | fail low | [ 0, 0]
f = 0
count | ウィンドウ | αβ 値 | type | MM の範囲
99/ 99 | (-1, 0) | 0 | fail high | [ 0, inf]
136/ 235 | ( 0, 1) | 0 | fail low | [ 0, 0]
f = 1
count | ウィンドウ | αβ 値 | type | MM の範囲
174/ 174 | ( 0, 1) | 0 | fail low | [-inf, 0]
47/ 221 | (-1, 0) | 0 | fail high | [ 0, 0]
f = 2
count | ウィンドウ | αβ 値 | type | MM の範囲
172/ 172 | ( 1, 2) | 0 | fail low | [-inf, 0]
49/ 221 | (-1, 0) | 0 | fail high | [ 0, 0]
f = 3
count | ウィンドウ | αβ 値 | type | MM の範囲
163/ 163 | ( 2, 3) | 2 | fail low | [-inf, 2]
99/ 262 | ( 1, 2) | 1 | fail low | [-inf, 1]
34/ 296 | ( 0, 1) | 0 | fail low | [-inf, 0]
50/ 346 | (-1, 0) | 0 | fail high | [ 0, 0]
下記は上記の実行結果をまとめた表です。この局面のミニマックス値は 0 なので、絶対誤差は先ほどと同じ になります。下記の表から、ミニマックス値として 2 を推定した場合 は 2 → 0 → 0 のように 2 以上変化して推移する ことが確認できます。
| f | 絶対誤差 | 回数 | nw の回数 | αβ 値の推移 |
|---|---|---|---|---|
| -2 | 2 | 295 | 4 | -2 → -2 → -1 → 0 → 0 |
| -1 | 1 | 277 | 3 | -1 → -1 → 0 → 0 |
| 0 | 0 | 235 | 2 | 0 → 0 → 0 |
| 1 | 1 | 221 | 2 | 1 → 0 → 0 |
| 2 | 2 | 221 | 2 | 2 → 0 → 0 |
| 3 | 3 | 346 | 4 | 3 → 2 → 1 → 0 → 0 |
先程の ゲーム開始時の局面での MTD(f) 法で行なった 考察は、上記の局面でもそのまま当てはまります。下記は 絶対誤差 と null window search の回数 を抜き出してまとめたものです。実際に 精度が高い（絶対誤差が少ない）ほうが null window search の 回数が少なくなるという傾向がある ことが確認できます。
| 絶対誤差 | nw の回数 | nw の回数の平均 |
|---|---|---|
| 0 | 2 | 2.0 |
| 1 | 2、3 | 2.5 |
| 2 | 2、4 | 3.0 |
| 3 | 4 | 4.0 |
これまで「傾向がある」のように表記したのは、上記の表で「絶対誤差が 1 の場合に nw の回数が 3」、「絶対誤差が 2 の場合に nw の回数が 2」という、絶対誤差が多いほうが nw の回数が少ない場合がたまに存在するからです。
下記は null window search の回数 と 計算したノードの数 を抜き出してまとめた表で、この局面でも null window search の回数が少ないほうが計算したノードの数が少なくなる傾向がある ことが確認できます。
| nw の回数 | ノードの数 | ノードの数の平均 |
|---|---|---|
| 2 | 235 221 221 |
225.7 |
| 3 | 277 | 277.0 |
| 4 | 295 346 |
320.5 |
下記は 絶対誤差と評価値が計算されたノードの数 をまとめた表です。平均の列から実際に 精度が高い（絶対誤差が少ない）ほうが計算された ノードの数が少なくなるという傾向がある ことが確認できます。
| 絶対誤差 | ノードの数 | ノードの数の平均 |
|---|---|---|
| 0 | 235 | 235.0 |
| 1 | 277 221 |
249.0 |
| 2 | 295 221 |
258.0 |
| 3 | 346 | 346.0 |
ここまでで、2 つの局面で検証を行いましたが、いずれも推定した ミニマックス値の精度が高い（ミニマックス値に近い）ほど 効率が高くなる傾向がある ことが 確認できました。余裕がある方は、他の局面でも同様の傾向があることを確認してみて下さい。
スカウト法との比較による MTD(f) 法と 効率の検証
前回の記事では move ordering を行なわない αβ 法と比較しましたが、今回の記事では move ordering を行うスカウト法 との 効率の比較 を以下の条件で行うことにします。
- 最短の勝利を目指す場合と目指さない場合の両方で行う
- 置換表を利用する
- 初期設定のミニマックス値の範囲が最も広くなるように、α 値と β 値の初期値を負の無限大と正の無限大とする
-
move ordering と ミニマックス値の推定 を 精度の低い順 に、弱解決ではない
ai10s、弱解決のai14s、強解決のai_gt6の 3 種類の AI を利用 して行う - スカウト法、move ordering を行なわない MTD(f) 法、move ordering を行う MTD(f) 法 の 3 種類の効率の比較 を行う
- 同一局面を除いた すべての局面 に対して計算を行ない、評価値が計算された ノードの数の合計を計算 する。その後で、スカウト法を 1 とした場合の比率 を計算することで 効率を比較 する
上記では、同じくらいの精度 で move ordering と ミニマックス値の推定 を行った場合の効率の 比較を行うことができるようにする ために、同じ AI の関数 を利用して move ordering と ミニマックス値の推定を行う ことにしました。なお、ai10s と ai14s が 計算する評価値 は、ミニマックス法 で計算するノードの 評価値とは異なる ので、ミニマックス値ではありません。例えば、ai10s は以前の記事で説明したように、-1 ~ 12 の評価値を計算 します。また、ai_gt6 は局面と最善手の対応表のデータを使って最善手を計算するので、局面の評価値を計算することはありません。そのため、ミニマックス値の推定値 を ai10s などを利用して 直接計算することはできない 点に注意が必要です。それらの関数でミニマックス値の推定値をどのように計算すればよいかについて少し考えてみて下さい。
ミニマックス値の推定値の計算方法とその実装
ミニマックス値 と 異なる評価値を計算 する AI の関数で、ミニマックス値の推定値を計算する方法 は以下の通りで、AI の関数で計算した評価値を利用するのではなく、AI の関数で計算した最善手を利用 します。この方法を思いつくのは少し難しいかもしれませんが、行う処理は単純です。
-
ai10sなどの AI で 最善手を計算 する - 上記で計算した 最善手を着手した局面のミニマックス値 を、
ai_scoutなどの ミニマックス値を計算する関数で計算 し、その値を ミニマックス値の 推定値とする
下記は上記の手法でスカウト法との比較を行う行うプログラムです。
-
4、5 行目：
ai_gt6で必要となる、局面と最善手の対応表のデータをファイルから読み込み、ai_gt6のキーワード引数paramsに代入するデータをgt6_paramsに代入する - 6 行目：前回の記事で作成した、同一局面を除いた決着がついていない局面のデータの一覧をファイルから読み込む
-
7 行目：
ai10s、ai14s、ai_gt6のそれぞれの AI に対する繰り返し処理を行う。for 文の list の要素には、AI の関数とその AI が必要とするパラメータを表す tuple を代入した - 8 行目：最短の勝利を目指さない場合と目指す場合の繰り返し処理を行う
- 9 行目：計算の条件を表示する
- 10 行目：計算結果の表の見出しを表示する。move ordering を行う MTD(f) 法は mtdf(mo) と表記した
- 11 ~ 13 行目：スカウト法、move ordering を行わない MTD(f) 法、move ordering を行う MTD(f) 法のそれぞれで評価値を計算したノードの数を数える変数を 0 で初期化する
- 14 ~ 26 行目：それぞれの局面に対する繰り返し処理を行う
- 15 ~ 17 行目：スカウト法の処理を行う
-
18 ~ 21 行目：
ai_for_moに代入された AI の関数で最善手を計算し、その最善手を着手した局面に対するミニマックス値をai_scoutで計算する。なお、mbは 22 行目以降で利用する必要があるので、最善手を着手した局面はmbをコピーしたmbcopyに対して行う必要がある点に注意する事 -
22、23 行目：21 行目で計算した
fをミニマックス値として推定した move ordering を行なわない MDT(f) 法による処理を行う - 24、25 行目：move ordrering を行う MTD(f) による処理を行う
- 28、29 行目：最初の行にそれぞれの場合の回数を、次の行にスカウト法との比率を表示する
1 from util import load_mblist, load_bestmoves
2 from ai import ai10s, ai14s, ai_gt6, ai_scout
3
4 bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
5 gt6_params = {"bestmoves_by_board": bestmoves_by_board}
6 mblist = load_mblist("../data/mblist_by_board_min2.dat")
7 for ai_for_mo, params in [(ai10s, {}), (ai14s, {}), (ai_gt6, gt6_params)]:
8 for shortest_victory in [False, True]:
9 print(f"ai_for_mo: {ai_for_mo} shortest_victory: {shortest_victory}")
10 print(" | scout | mtdf | mtdf(mo)")
11 count = 0
12 count2 = 0
13 count3 = 0
14 for mb in mblist:
15 count += ai_scout(mb, ai_for_mo=ai_for_mo, params=params,
16 shortest_victory=shortest_victory, use_tt=True,
17 calc_score=True, calc_count=True)
18 x, y = ai_for_mo(mb, **params)
19 mbcopy = deepcopy(mb)
20 mbcopy.move(x, y)
21 f = ai_scout(mbcopy, shortest_victory=shortest_victory, use_tt=True, calc_score=True)
22 count2 += ai_mtdf(mb, shortest_victory=shortest_victory, f=f,
23 use_tt=True, calc_score=True, calc_count=True)
24 count3 += ai_mtdf(mb, shortest_victory=shortest_victory, f=f,
25 ai_for_mo=ai_for_mo, params=params, use_tt=True,
26 calc_score=True, calc_count=True)
27
28 print(f"count | {count:5} | {count2:5} | {count3:5}")
29 print(f"ratio | | {count2 / count * 100:3.0f}% | {count3 / count * 100:3.0f}%")
30
行番号のないプログラム
from util import load_mblist, load_bestmoves
from ai import ai10s, ai14s, ai_gt6, ai_scout
bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
gt6_params = {"bestmoves_by_board": bestmoves_by_board}
mblist = load_mblist("../data/mblist_by_board_min2.dat")
for ai_for_mo, params in [(ai10s, {}), (ai14s, {}), (ai_gt6, gt6_params)]:
for shortest_victory in [False, True]:
print(f"ai_for_mo: {ai_for_mo} shortest_victory: {shortest_victory}")
print(" | scout | mtdf | mtdf(mo)")
count = 0
count2 = 0
count3 = 0
for mb in mblist:
count += ai_scout(mb, ai_for_mo=ai_for_mo, params=params,
shortest_victory=shortest_victory, use_tt=True,
calc_score=True, calc_count=True)
x, y = ai_for_mo(mb, **params)
mbcopy = deepcopy(mb)
mbcopy.move(x, y)
f = ai_scout(mbcopy, shortest_victory=shortest_victory, use_tt=True, calc_score=True)
count2 += ai_mtdf(mb, shortest_victory=shortest_victory, f=f,
use_tt=True, calc_score=True, calc_count=True)
count3 += ai_mtdf(mb, shortest_victory=shortest_victory, f=f,
ai_for_mo=ai_for_mo, params=params, use_tt=True,
calc_score=True, calc_count=True)
print(f"count | {count:5} | {count2:5} | {count3:5}")
print(f"ratio | | {count2 / count * 100:3.0f}% | {count3 / count * 100:3.0f}%")
実行結果
ai_for_mo: <function ai10s at 0x00000213B5BE51C0> shortest_victory: False
| scout | mtdf | mtdf(mo)
count | 13562 | 20420 | 11188
ratio | | 151% | 82%
ai_for_mo: <function ai10s at 0x00000213B5BE51C0> shortest_victory: True
| scout | mtdf | mtdf(mo)
count | 14508 | 25239 | 15115
ratio | | 174% | 104%
ai_for_mo: <function ai14s at 0x00000213B5BE56C0> shortest_victory: False
| scout | mtdf | mtdf(mo)
count | 11609 | 19727 | 8323
ratio | | 170% | 72%
ai_for_mo: <function ai14s at 0x00000213B5BE56C0> shortest_victory: True
| scout | mtdf | mtdf(mo)
count | 11698 | 24275 | 11974
ratio | | 208% | 102%
ai_for_mo: <function ai_gt6 at 0x00000213B5BE5E40> shortest_victory: False
| scout | mtdf | mtdf(mo)
count | 13383 | 19644 | 9947
ratio | | 147% | 74%
ai_for_mo: <function ai_gt6 at 0x00000213B5BE5E40> shortest_victory: True
| scout | mtdf | mtdf(mo)
count | 14419 | 24471 | 15564
ratio | | 170% | 108%
下記は実行結果の中の回数の部分をまとめた表です。より精度が高い ai14s のほうが ai10s と比べて いずれの場合でも効率が高くなる ことが確認できます。
最も精度が高い 強解決の ai_gt6 が ai14s よりもほどんとの場合で 効率が悪くなる理由 は、ai10s や ai14s と ai_gt6 が 選択する最善手が異なる からです。例えば ai10s と ai14s はゲーム開始時の局面で必ず真ん中の (1, 1) のみを最善手として選択 しますが、ゲーム開始時の局面は 9 種類のすべての合法手が最善手なので ai_gt6 はその中から ランダムで最善手を選択 します。最善手が複数存在 する場合は、その中の どの最善手を先頭に移動するか によって 枝狩りが行われるノードが変わる ので、その 効率が異なります。ai10s と ai14s が選択する最善手を先頭に移動する move ordering のほうが、ai_gt6 が選択する選択する最善手を先頭に移動する move ordering よりも効率が高くなるため、下記のような一見すると矛盾したように見える結果になります。
最短の勝利を目指さない場合
| Scout | MTD(f) | MTD(f) mo | |
|---|---|---|---|
ai10s |
13562 | 20420 | 11188 |
ai14s |
11609 | 19727 | 8323 |
ai_gt6 |
13383 | 19644 | 9947 |
最短の勝利を目指す場合
| Scout | MTD(f) | MTD(f) mo | |
|---|---|---|---|
ai10s |
14508 | 25239 | 15115 |
ai14s |
11698 | 24275 | 11974 |
ai_gt6 |
14419 | 24471 | 15564 |
下記は実行結果の中の スカウト法を基準とした比率 の部分をまとめた表です。
最短の勝利を目指さない場合
| MTD(f) | MTD(f) mo | |
|---|---|---|
ai10s |
151 % | 82 % |
ai14s |
170 % | 72 % |
ai_gt6 |
147 % | 74 % |
最短の勝利を目指す場合
| MTD(f) | MTD(f) mo | |
|---|---|---|
ai10s |
174 % | 104 % |
ai14s |
208 % | 102 % |
ai_gt6 |
170 % | 108 % |
〇× ゲームでは残念ながら最短の勝利を目指す場合の MTD(f) 法は常にスカウト法よりも効率が悪くなりますが、最短の勝利を目指さない場合 は、move ordering を行う MTD(f) 法 の方がいずれも スカウト法よりも効率が良くなる ことがわかりました。最短の勝利を目指す場合に関しては、おそらく 〇× ゲームの ゲーム木の深さが浅い ため、null window search の効率が高くならない からではないかと思いますが、最短の勝利を目指す場合 でも、スカウト法と move ordering を行う MTD(f) 法の効率は ほぼ同じ になります。
また、上記の結果から move ordering は MTD(f) 法でも効率を高めるために有効である ことが確認できました。
前回の記事で説明したように、一般的に ゲーム木がより深くなれば null window search の効率がより高くなります。そのため、チェスなど のより深いゲーム木の場合は、move ordering を行なわない MTD(f) の効率がスカウト法よりも高くなるという事例がある ようです。例えば An Algorithm Faster than NegaScout and SSS* in Practice という論文では チェスでは MTD(f) 法によってスカウト法に分類されるアルゴリズムよりも約 10 % 程効率が高くなった ことが確認されたとの報告があります。
なお、Wikipedia の MTD(f) 法の記事 では「しかし置換表に強く依存する事や、探索の非安定性などの問題が存在するので、 現在のチェスプログラムでは NegaScout 法もいまだに広く使われている」とあるので、スカウト法と MTD(f) 法のどちらが良いかについては意見が分かれているようです。
探索の非安定性（search instability）とは、同じノードに対して異なるウィンドウで αβ 値を計算した際に、矛盾した計算結果が得られることを表します。探索の非安定性は、本記事でこれまでに行なってきた、正確な評価値を計算できる リーフノードの評価値を使って〇×ゲームのミニマックス値を計算する手法では発生しません。
探索の非安定性は、それが発生する条件が満たされれば MTD(f) 法だけでなく、スカウト法でも発生するような気がします。そのため、探索の非安定性を理由に MTD(f) 法ではなくスカウト法を利用する場合があるという上記の Wikipedia の説明については、筆者はあまり納得できませんでした。この点については筆者はまだ勉強不足なので、詳しい方がいればコメントなどで補足していただけると大変助かります。
参考までに探索の非安定性の Chess Programming wiki のリンクを下記に示します。
MTD(f) 法に限らず、枝狩りを行うアルゴリズム は、ゲーム木の性質によって効率が大きく変わります。〇×ゲーム以外のゲーム木では、本記事の検証と異なる結果になる場合があるので、他のゲームで実装を行う場合は、様々な枝狩りのアルゴリズムを実際に試して比較を行うことが重要 となります。
今回の記事のまとめ
今回の記事では 推定したミニマックス値の精度と MTD(f) 法の効率の関係 について説明しました。また、スカウト 法と MTD(f) 法の比較による効率の検証 を行ないました。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| ai.py | 本記事で更新した ai_new.py |
次回の記事
近日公開予定です。
-
表には記載されていませんが、ミニマックス値の範囲の初期値は [$-∞$, $∞$] なので、最初の null window search では下界または上界の値が更新されてミニマックス値の範囲が必ず狭くなります ↩