目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| test.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義 |
| tree.py | ゲーム木に関する Node、Mbtree クラスなどの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
αβ 法との比較による MTD(f) 法と 効率の検証
今回の記事では、前回の記事で実装した MTD(f) 法の効率 を αβ 法と比較 することで検証します。スカウト法との比較は次回の記事で行います。最初に以前の記事で行った下記の方法で、αβ 法と MTD(f) 法の効率を比較 することにします。
- 同一局面を除いた 〇×ゲームのすべての局面に対して、同一の設定で αβ 法と MTD(f) 法で計算を行う
- それぞれの場合で、計算されたノードの数の合計を比較することで処理の効率を比較する
なお、以前の記事では move ordering に関する比較を行っていましたが、MTD(f) 法を紹介した論文では move ordering を行なっていない ので、αβ 法との比較では move ordering を行なわないことにします。また、前回の記事で説明したように、MTD(f) 法では局面の ミニマックス値の推定値の精度が高い程効率が高くなる ことが期待できますが、move ordering を行なわない αβ 法と比較することを考慮 して今回の比較ではあえて精度が高くない、すべての局面のミニマックス値を 0 と推定した場合の比較 を行うことにしました。
ミニマックス値の推定値の精度を高くした場合の MTD(f) 法の検証は、次回の記事で move ordering を行うスカウト法との比較の際に行うことにします。
最短の勝利を考慮しない場合の評価値は -1、0、1 のいずれかなので、ミニマックス値として 0 を推定した場合の誤差は最大でも ± 1 しかありません。従ってその場合の精度は実はかなり高いと言えると思います。
下記はその比較を行うプログラムです。なお、実は 下記のプログラムの検証には問題がある ことが 検証を行った後で判明 しました。問題の発見と修正の経緯が参考になるのではないか と思いましたので、あえて問題があるまま検証を進める ことにします。
from ai import ai_abs_all, ai_mtdf
from util import load_mblist
mblist = load_mblist("../data/mblist_by_board_min.dat")
for shortest_victory in [False, True]:
for use_tt in [False, True]:
for init_ab in [False, True]:
print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
count = 0
count2 = 0
for mb in mblist:
count += ai_abs_all(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
count2 += ai_mtdf(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
print("abs count=", count)
print("mtdf count=", count2)
実行結果
sv: False, init_ab: False, use_tt: False
abs count= 32020
mtdf count= 35728
sv: False, init_ab: True, use_tt: False
abs count= 23850
mtdf count= 28803
sv: False, init_ab: False, use_tt: True
abs count= 17582
mtdf count= 14362
sv: False, init_ab: True, use_tt: True
abs count= 12576
mtdf count= 14042
sv: True, init_ab: False, use_tt: False
abs count= 36423
mtdf count= 39740
sv: True, init_ab: True, use_tt: False
abs count= 33947
mtdf count= 37643
sv: True, init_ab: False, use_tt: True
abs count= 19459
mtdf count= 18546
sv: True, init_ab: True, use_tt: True
abs count= 18191
mtdf count= 18447
下記は実行結果をまとめた表です。一番上の行の ab は init_ab、tt は use_tt の値で 〇 は True、× は False を表します。各セルの 上段が ai_abs_all、下段が ai_mtdf の結果です。
| ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 | |
|---|---|---|---|---|
| 最短の勝利を目指さない場合 | 32020 35728 |
23850 28803 |
17582 14362 |
12576 14042 |
| 最短の勝利を目指さす場合 | 36423 39740 |
33947 37643 |
19459 18546 |
18191 18447 |
実行結果から、init_ab=False、use_tt=True の場合のみ MTD(f) 法のほうが効率が良くなることが確認できました。
MTD(f) 法は置換表の利用を前提 とするアルゴリズムです。その理由を説明するために、置換表を利用する場合と利用しない場合にわけて検証を行う ことに会います。
置換表を利用しない場合の検証
上記の結果では、置換表を利用しない場合 はいずれも αβ 法よりも効率が悪くなります。その理由についていくつかの考察と検証を行います。
枝狩りの効率とゲーム木の深さの関係の考察
前回の記事で説明したように、MTD(f) 法は、null window search の効率の高さを利用 することで、複数回（2 回以上）の null window search の計算のほうが、αβ 法による 広いウィンドウでの 1 回の αβ 値の計算よりも効率が高くなる ことを期待するという手法です。そのため、置換表を利用しない場合 は、null window search による 枝狩りの効率が高いことが非常に重要 となります。
null window search に限らず、下記のような理由から αβ 値を計算する場合はその 子孫ノードの部分木 の 深さが浅い場合 は一般的に 枝狩りの効率が低くなります。
- 枝狩り は、枝狩りを行ったノードの すべての子孫ノードの処理を省略する ので、子孫ノードの数が多い程 枝狩りの 効率が良くなる
- リーフノードを除くゲーム木のほとんどのノードには複数の子ノードが存在するので、ゲーム木のノードの数 は 深さが増えるごとに爆発的に増えていく。このような毎回数倍に増えていくような増え方を 指数関数的に増えていく と呼ぶ1
- 従って、子孫ノードの部分木の 深さが浅いほど 一般的に 枝狩りの効率が低くなる
〇× ゲーム のゲーム木の 各深さの具体的なノードの数 は以前の記事で 下記のように計算済 です。下記からノードの総数は 549946 で、深さが 7 以上のノードの数は 148176 + 200448 + 127872 = 476496 です。476496 ÷ 549946 = 約 0.866 なので、85 % 以上のほとんどのノードが深さ 7 以上のノード であることが確認できます。
〇× ゲームのゲーム木の深さは 9 なので、深さが $n$ のノードをルートノードとする部分木の深さは $9 - n$ 以下になります。従って、〇× ゲームの ほとんどのノードをルートノードとする部分木の深さ は 2 以下 と、実際にかなり浅い ことが確認できました。
9 depth 1 node created
72 depth 2 node created
504 depth 3 node created
3024 depth 4 node created
15120 depth 5 node created
54720 depth 6 node created
148176 depth 7 node created
200448 depth 8 node created
127872 depth 9 node created
0 depth 10 node created
total node num = 549946
このことから、先程行った検証では、ほとんどのノードでの null window search の効率が低く なるため、すべてのノードの 合計を比較した場合 に MTD(f) 法のほうが αβ 法よりも 効率が低くなった ことが推測されます。
なお、mblist_by_board_min.dat は 同一局面を削除 しているので、先程の検証で上記と同じ数のノードが計算されるわけではありません。それぞれの深さでいくつの局面を計算しているかについてはこの後で示すことにします。
〇× ゲームのゲーム木特有の性質の考察
他の理由としては、〇× ゲーム特有の性質 として、〇× ゲームの合法手は開いているマスの数に等しいので 局面のノードの深さが深い程、子ノードの数が減る というものがあります。αβ 法 では 枝狩りは 2 番目以降の子ノード に対して行なわれるので、子ノードの数が多いほうが枝狩りが行なわれやすくなる という性質があります。そのため 〇× ゲームのゲーム木のように、深さが 深い程子ノードの数が減るようなゲーム木 では、ノードが 深い程枝狩りの効率が悪くなります。
実際に 〇× ゲームの場合 は下記の理由から 深さが 8 のノード のミニマックス値を計算すると、MTD(f) 法の方 が αβ 法よりも 必ず効率が悪くなります。
-
深さが 8 のノードの αβ 値を計算する際 は、下記の理由から ウィンドウの範囲に関わらず枝狩りは行なわれない
- 深さが 8 のノード の 子ノードの数は 1 つ である
- 深さが 9 のノード は決着がついた 子ノードが存在しないリーフノード である
- α 狩りや β 狩りは子ノードが 2 つ以上存在する場合に行なわれる
- 従って、深さ 8 のノードの αβ 値を計算する際には、ウィンドウ幅に関わらず そのノードと子ノードの 2 つのノード の評価値の 計算が必ず行われる
- MTD(f) 法 では必ず 2 回以上 の null window search が行なわれるので、2 × 2 = 4 個以上 のノードの計算が行われる
- αβ 法 では 1 回 の αβ 値の計算を行うので 2 個 のノードの計算が行なわれる
ノードの深さごとの効率の差の確認
上記の考察が正しいことを検証するために、〇× ゲームの ノードの深さごと に αβ 法と MTD(f) 法の効率を比較 することにします。
具体的には、先程のプログラムを下記のように修正して実行します。
- 5、6 行目：深さごとの回数を数える ことができるようにするために、回数を数える変数を 9 つの 0 を要素として持つ list で初期化するように修正した。list の インデックスの番号 が ゲーム木の深さを表す ものとする
-
8、11 行目：ノードの深さは着手した回数に等しい ので、着手した回数を表す
mb.move_countのインデックスの要素を増やすように修正する - 15、16 行目：深さごとの αβ 法、MTD(f) 法、両者の差（difference）を表示するように修正する。diff の後に表示される両者の差は 負の値が表示された場合 に MTD(f) 法の方が効率が良い ことを表す。また、上下の数字の表示位置が揃うように書式指定 を利用して 5 桁で表示するようにした
-
17 行目：深さごとの合計を表示するように修正する。合計は組み込み関数
sumを利用して計算した
1 for shortest_victory in [False, True]:
2 for use_tt in [False, True]:
3 for init_ab in [False, True]:
4 print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
5 count = [0] * 9
6 count2 = [0] * 9
7 for mb in mblist:
8 count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
9 init_ab=init_ab, use_tt=use_tt,
10 calc_score=True, calc_count=True)
11 count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
12 init_ab=init_ab, use_tt=use_tt,
13 calc_score=True, calc_count=True)
14
15 for depth in range(9):
16 print(f"depth = {depth} abs = {count[depth]:5} mtdf = {count2[depth]:5} diff = {count2[depth] - count[depth]:5}")
17 print(f"total abs = {sum(count):5} mtdf = {sum(count2):5} diff = {sum(count2) - sum(count):5}")
行番号のないプログラム
for shortest_victory in [False, True]:
for use_tt in [False, True]:
for init_ab in [False, True]:
print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
count = [0] * 9
count2 = [0] * 9
for mb in mblist:
count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
for depth in range(9):
print(f"depth = {depth} abs = {count[depth]:5} mtdf = {count2[depth]:5} diff = {count2[depth] - count[depth]:5}")
print(f"total abs = {sum(count):5} mtdf = {sum(count2):5} diff = {sum(count2) - sum(count):5}")
修正箇所
for shortest_victory in [False, True]:
for use_tt in [False, True]:
for init_ab in [False, True]:
print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
- count = 0
+ count = [0] * 9
- count2 = 0
+ count2 = [0] * 9
for mb in mblist:
- count += ai_abs_all(mb, shortest_victory=shortest_victory,
+ count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
- count2 += ai_mtdf(mb, shortest_victory=shortest_victory,
+ count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
- print("abs count=", count)
- print("mtdf count=", count2)
+ for depth in range(9):
+ print(f"depth = {depth} abs = {count[depth]:5} mtdf = {count2[depth]:5} diff = {count2[depth] - count[depth]:5}")
+ print(f"total abs = {sum(count):5} mtdf = {sum(count2):5} diff = {sum(count2) - sum(count):5}")
実行結果
sv: False, init_ab: False, use_tt: False
depth = 0 abs = 0 mtdf = 0 diff = 0
depth = 1 abs = 7523 mtdf = 7024 diff = -499
depth = 2 abs = 5423 mtdf = 5636 diff = 213
depth = 3 abs = 8369 mtdf = 9188 diff = 819
depth = 4 abs = 6515 mtdf = 8109 diff = 1594
depth = 5 abs = 2715 mtdf = 3397 diff = 682
depth = 6 abs = 1193 mtdf = 1866 diff = 673
depth = 7 abs = 282 mtdf = 508 diff = 226
depth = 8 abs = 0 mtdf = 0 diff = 0
total abs = 32020 mtdf = 35728 diff = 3708
略
実行結果を見ると 深さが 0 と 8 のノードが 1 つも計算されていない ことがわかります。これが先程言及した検証の 問題点 です。何故このようなことが起きたかについて少し考えてみて下さい。
検証データの作成
上記のようなことがおきるのは、検証するためにファイルから読み込んだ mblist_by_board_min.dat というファイルにあります。このデータは、Check_solved で AI が 強解決の AI であるかを検証するために作成 したデータですが、その際に強解決であるかどうかを 判定する必要がない、すべての合法手が最善手である局面を削除 しています。
実際にゲーム開始時の 深さが 0 の局面 は すべての合法手が最善手 です。また、深さが 8 の局面 は 子ノードが 1 つしか存在しない ので すべての合法手が最善手 です。従って、それらの局面のデータ は mblist_by_board_min.dat には 含まれていません。
そこで、それらのデータを含むデータを作成 し、そのデータを使って検証し直す ことにします。下記のプログラムはそのデータを作成するプログラムで、以前の記事での mblist_by_board_min.dat のデータを作成するプログラムを修正したものです。下記では mblist_by_board_min2.dat という名前のファイルに作成したデータを保存していますが、わかりづらいと思った方は別のもっとわかりやすい名前で保存してくさだい
- 6 行目：ゲーム木のデータをファイルから読み込む
-
7、14 行目：作成したデータをこの後ですぐに利用できるようにするために、
mblist_by_boardではなく、mblistという名前の変数に計算したデータを記録するように修正した - 13 行目：ゲーム中のデータであればすべて登録するように条件式を修正する
- 15、16 行目：作成したデータを mblist_by_board_min2.dat というファイルに保存する
1 import gzip, pickle
2 from util import calc_same_boardtexts
3 from tree import Mbtree
4 from marubatsu import Marubatsu
5
6 mbtree = Mbtree.load("../data/aidata")
7 registered_boards = set()
8 mblist = []
9 for node in mbtree.nodelist:
10 txt = node.mb.board_to_str()
11 if not txt in registered_boards:
12 registered_boards |= calc_same_boardtexts(node.mb)
13 if node.mb.status == Marubatsu.PLAYING:
14 mblist.append(node.mb)
15 with gzip.open("../data/mblist_by_board_min2.dat", "wb") as f:
16 pickle.dump(mblist, f)
行番号のないプログラム
import gzip, pickle
from util import calc_same_boardtexts
from tree import Mbtree
from marubatsu import Marubatsu
mbtree = Mbtree.load("../data/aidata")
registered_boards = set()
mblist = []
for node in mbtree.nodelist:
txt = node.mb.board_to_str()
if not txt in registered_boards:
registered_boards |= calc_same_boardtexts(node.mb)
if node.mb.status == Marubatsu.PLAYING:
mblist.append(node.mb)
with gzip.open("../data/mblist_by_board_min2.dat", "wb") as f:
pickle.dump(mblist, f)
修正箇所
import gzip, pickle
from util import calc_same_boardtexts
from tree import Mbtree
from marubatsu import Marubatsu
mbtree = Mbtree.load("../data/aidata")
registered_boards = set()
-mblist_by_board = []
+mblist = []
for node in mbtree.nodelist:
txt = node.mb.board_to_str()
if not txt in registered_boards:
registered_boards |= calc_same_boardtexts(node.mb)
if node.mb.status == Marubatsu.PLAYING:
- mblist_by_board.append(node.mb)
+ mblist.append(node.mb)
+with gzip.open("../data/mblist_by_board_min2.dat", "wb") as f:
+ pickle.dump(mblist, f)
深さごとの効率の差の再確認
プログラムは省略しますが、先程と同じプログラム で 深さごとの効率の差を再検証 すると、以下のような実行結果が表示されます。
実行結果
sv: False, init_ab: False, use_tt: False
depth = 0 abs = 18297 mtdf = 17125 diff = -1172
depth = 1 abs = 7523 mtdf = 7024 diff = -499
depth = 2 abs = 7653 mtdf = 7726 diff = 73
depth = 3 abs = 10465 mtdf = 11928 diff = 1463
depth = 4 abs = 7671 mtdf = 9290 diff = 1619
depth = 5 abs = 3943 mtdf = 5084 diff = 1141
depth = 6 abs = 1660 mtdf = 2492 diff = 832
depth = 7 abs = 406 mtdf = 709 diff = 303
depth = 8 abs = 68 mtdf = 136 diff = 68
total abs = 57686 mtdf = 61514 diff = 3828
略
下記は実行結果の 合計をまとめた表 です。一番上の行の ab は init_ab、tt は use_tt の値で 〇 は True、× は False を表します。各セルの 上段が ai_abs_all、中段が ai_mtdf、下段がその差 です。
| ab × tt × | ab 〇 tt x | ab × tt 〇 | ab 〇 tt 〇 | |
|---|---|---|---|---|
| 最短の勝利を目指さない場合 | 57686 61514 3828 |
46467 53105 6638 |
23172 19403 -3769 |
16291 18924 2003 |
| 最短の勝利を目指さす場合 | 65583 67861 2278 |
62147 65402 3255 |
25711 25134 -577 |
24087 25022 935 |
合計の結果は修正前と同様に init_ab=False、use_tt=True の場合のみ MTD(f) 法のほうが効率が悪くなります。全体の傾向は大きく変わりません。
置換表を利用しない場合 で、深さごとの結果の差をまとめる と以下の表のようになります。sv は最短の勝利を目指すかどうかを表します。
| 深さ | sv × ab × | sv × ab 〇 | sv 〇 ab × | sv 〇 ab 〇 |
|---|---|---|---|---|
| 0 | -1172 | 314 | -3741 | -3359 |
| 1 | -499 | 531 | -1410 | -1032 |
| 2 | 73 | 698 | -39 | 541 |
| 3 | 1463 | 2605 | 1873 | 2649 |
| 4 | 1619 | 1334 | 2820 | 2170 |
| 5 | 1141 | 762 | 1513 | 1024 |
| 6 | 832 | 261 | 891 | 891 |
| 7 | 303 | 111 | 303 | 303 |
| 8 | 68 | 22 | 68 | 68 |
| 合計 | 3828 | 6638 | 2278 | 3255 |
表から α 値と β 値の初期値を負の無限大と正の無限大とする場合（ab ×） はいずれも 深さが 0 と 1 のノードで MTD(f) 法の方が効率が高くなる ことがわかります。
上記では 深さごとの合計 を計算していますが、深さごとにノードの数が異なる ので 深さごとの平均 を比較したほうが適切しょう。そこで、上記のプログラムを下記のように修正して 深さごとの平均、平均の差、平均の割合（ratio） を表示することにします。割合は 100 % よりも小さい場合 に MTD(f) 法のほうが効率が高い ことを表します。
- 7、8 行目：深さごとのノードの数を数える変数を初期化する
- 13、17 行目：計算したノードの深さの数を増やす
- 19 ~ 20 行目：深さごとのノードの数、平均、平均の差、平均の割合などを計算して表示する。最後にあった全体の合計に関する表示は削除した
1 for shortest_victory in [False, True]:
2 for use_tt in [False, True]:
3 for init_ab in [False, True]:
4 print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
5 count = [0] * 9
6 count2 = [0] * 9
7 num = [0] * 9
8 num2 = [0] * 9
9 for mb in mblist:
10 count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
11 init_ab=init_ab, use_tt=use_tt,
12 calc_score=True, calc_count=True)
13 num[mb.move_count] += 1
14 count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
15 init_ab=init_ab, use_tt=use_tt,
16 calc_score=True, calc_count=True)
17 num2[mb.move_count] += 1
18 for depth in range(9):
19 ave1 = count[depth] / num[depth]
20 ave2 = count2[depth] / num2[depth]
21 print(f"depth = {depth} num = {num[depth]:3} abs = {ave1:7.1f} mtdf = {ave2:7.1f} diff = {ave2 - ave1:7.1f} ratio = {ave2 / ave1 * 100:3.0f}%")
行番号のないプログラム
for shortest_victory in [False, True]:
for use_tt in [False, True]:
for init_ab in [False, True]:
print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
count = [0] * 9
count2 = [0] * 9
num = [0] * 9
num2 = [0] * 9
for mb in mblist:
count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
num[mb.move_count] += 1
count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
num2[mb.move_count] += 1
for depth in range(9):
ave1 = count[depth] / num[depth]
ave2 = count2[depth] / num2[depth]
print(f"depth = {depth} num = {num[depth]:3} abs = {ave1:7.1f} mtdf = {ave2:7.1f} diff = {ave2 - ave1:7.1f} ratio = {ave2 / ave1 * 100:3.0f}%")
修正箇所
for shortest_victory in [False, True]:
for use_tt in [False, True]:
for init_ab in [False, True]:
print(f"sv: {shortest_victory}, init_ab: {init_ab}, use_tt: {use_tt}")
count = [0] * 9
count2 = [0] * 9
+ num = [0] * 9
+ num2 = [0] * 9
for mb in mblist:
count[mb.move_count] += ai_abs_all(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
+ num[mb.move_count] += 1
count2[mb.move_count] += ai_mtdf(mb, shortest_victory=shortest_victory,
init_ab=init_ab, use_tt=use_tt,
calc_score=True, calc_count=True)
+ num2[mb.move_count] += 1
for depth in range(9):
- print(f"depth = {depth} abs = {count[depth]:5} mtdf = {count2[depth]:5} diff = {count2[depth] - count[depth]:5}")
+ ave1 = count[depth] / num[depth]
+ ave2 = count2[depth] / num2[depth]
+ print(f"depth = {depth} num = {num[depth]:3} abs = {ave1:7.1f} mtdf = {ave2:7.1f} diff = {ave2 - ave1:7.1f} ratio = {ave2 / ave1 * 100:3.0f}%")
- print(f"total abs = {sum(count):5} mtdf = {sum(count2):5} diff = {sum(count2) - sum(count):5}")
実行結果
sv: False, init_ab: False, use_tt: False
depth = 0 num = 1 abs = 18297.0 mtdf = 17125.0 diff = -1172.0 ratio = 94%
depth = 1 num = 3 abs = 2507.7 mtdf = 2341.3 diff = -166.3 ratio = 93%
depth = 2 num = 12 abs = 637.8 mtdf = 643.8 diff = 6.1 ratio = 101%
depth = 3 num = 38 abs = 275.4 mtdf = 313.9 diff = 38.5 ratio = 114%
depth = 4 num = 108 abs = 71.0 mtdf = 86.0 diff = 15.0 ratio = 121%
depth = 5 num = 153 abs = 25.8 mtdf = 33.2 diff = 7.5 ratio = 129%
depth = 6 num = 183 abs = 9.1 mtdf = 13.6 diff = 4.5 ratio = 150%
depth = 7 num = 95 abs = 4.3 mtdf = 7.5 diff = 3.2 ratio = 175%
depth = 8 num = 34 abs = 2.0 mtdf = 4.0 diff = 2.0 ratio = 200%
略
置換表を利用しない場合で、深さごとの 平均の差 をまとめると以下の表のようになります。
| 深さ | ノードの数 | sv × ab × | sv × ab 〇 | sv 〇 ab × | sv 〇 ab 〇 |
|---|---|---|---|---|---|
| 0 | 1 | -1172.0 | 314.0 | -3741.0 | -3359.0 |
| 1 | 3 | -166.3 | 177.0 | -470.0 | -344.0 |
| 2 | 12 | 6.1 | 58.2 | -3.2 | 45.1 |
| 3 | 38 | 38.5 | 68.6 | 49.3 | 69.7 |
| 4 | 108 | 15.0 | 12.4 | 26.1 | 20.1 |
| 5 | 153 | 7.5 | 5.0 | 9.9 | 6.7 |
| 6 | 183 | 4.5 | 1.4 | 4.9 | 4.9 |
| 7 | 95 | 3.2 | 1.2 | 3.2 | 3.0 |
| 8 | 34 | 2.0 | 0.6 | 2.0 | 2.0 |
平均の差 の表では 深さが 3 以下 の場合は先ほどの考察通りに深さが 浅いほうが小さくなる ので MTD(f) 法のほうが効率が良い ことがわかります。一方 深さが 4 以上 の場合は逆に深さが 深いほうが小さくなる ため、先程の考察に反して 深さが 深いほうが効率が高くなるように見えるかもしれません。実際にはそれは 錯覚 で、深さが 深い程子孫ノードの数が少なくなる ため、枝狩りの数に大きな差が生まれなくなってしまう からです。
他にも上記の表から、同一局面を考慮した場合は深さが 6 のノードが最も多く、深さが 4 ~ 7 のノードの数が多いことがわかります。
一方、下記の 平均の割合（MTD(f) 法 / αβ 法）をまとめた表では、先程の説明通りに深さが 深いほうがほぼすべての場合で MTD(f) 法のほうが 効率が悪くなる ことが確認できます。このように、2 つの数値の比較 を行う際には 差と割合のどちらが適切であるか を考える必要がある点に注意して下さい。
| 深さ | sv × ab × | sv × ab 〇 | sv 〇 ab × | sv 〇 ab 〇 |
|---|---|---|---|---|
| 0 | 94 % | 102 % | 82 % | 84 % |
| 1 | 93 % | 108 % | 83 % | 87 % |
| 2 | 101 % | 113 % | 100 % | 106 % |
| 3 | 114 % | 131 % | 115 % | 123 % |
| 4 | 121 % | 127 % | 135 % | 131 % |
| 5 | 129 % | 126 % | 138 % | 128 % |
| 6 | 150 % | 122 % | 154 % | 154 % |
| 7 | 175 % | 132 % | 175 % | 175 % |
| 8 | 200 % | 132 % | 200 % | 200 % |
先程深さが 8 のノードの場合は MTD(f) 法では 4 個以上、αβ 法では 2 個のノードの計算が行なわれると説明しましたが、sv × ab × の場合に下記のように abs = 2.0、mtdf = 4.0 と表示されることからそのことが正しいことが確認できます。
depth = 8 num = 34 abs = 2.0 mtdf = 4.0 diff = 2.0 ratio = 200%
sv × ab 〇 の場合は下記のように abs = 2.0 となりますが、mtdf のほうが mtdf = 2.6 のように 4 以上とならない点がおかしいと思った人はいないでしょうか？
depth = 8 num = 34 abs = 2.0 mtdf = 2.6 diff = 0.6 ratio = 132%
その理由はこの場合に MTD(f) 法のアルゴリズム に従って計算を行うと、最初の null window search で αβ 値として 1 が計算された場合に 下記の理由から次の null window search が行われず、1 回の null window search しか行われない からです。
- 最初のミニマックス値の範囲（下界と上界）は [-1, 1] である
- 最初のウィンドウが (0, 1) の null window search で αβ 値が 1 と計算された場合は fail high なので、ミニマックス値の範囲の下界が 1 で更新される
- その結果ミニマックス値の範囲が [1, 1] となり、下界と上界が等しくなるため次の null window search は行われない
このように、MTD(f) 法では例外的に 1 回の null window search しか行われない場合がありますが、一般的にはそのような状況はまず起きないので 2 回以上の null window search を行うと考えて良いと思います。
sv と ab の違いに対する考察
上記の表から、以下の事がわかりますが、いずれも αβ 法の場合のウィンドウ幅と null window search の場合の ウィンドウ幅の差が小さくなるため、両者の 枝狩りの効率の差が小さくなるから です。
- sv が × のほうが MTD(f) の効率が悪い
- ab が 〇 のほうが効率が悪い
下記は αβ 法 で $N$ のミニマックス値を計算する際の $N$、$N$ の子ノード、$N$ の孫以降の子孫ノードでの ウィンドウの最大幅 です。ただし、$N$ は max ノードであるとします。min ノードの場合も同様なので余裕がある方は表を作ってみて下さい。表のように sv が × のほうが 〇 よりも、ab が 〇 のほうが × よりも ウィンドウ幅が同じか狭く なります。
| $N$ | $N$ の子ノード | $N$ の孫ノード以降のノード | |
|---|---|---|---|
| sv × ab × | (-∞, ∞) | (-1, ∞) | (-1, 1) |
| sv × ab 〇 | (-1, 1) | (-1, 1) | (-1, 1) |
| sv 〇 ab × | (-∞, ∞) | (-2, ∞) | (-2, 3) |
| sv 〇 ab 〇 | (-2, 3) | (-2, 3) | (-2, 3) |
特に sv × ab 〇 の場合は、αβ 法では ウィンドウ幅の最大値が常に 2 であるため、MTD(f) 法での null window search のウィンドウ幅である 1 と比べて ウィンドウ幅が最大でもたったの 1 しか変わりません。そのため 両者の効率の差が小さくなり、この場合は 常に null window search を複数回行う MTD(f) の効率が αβ 法よりも悪化する ようです。
置換表を利用する場合の効率の比較
次に 置換表を利用する場合 の効率の比較を行います。
先程の結果から、置換表を利用する場合の 深さごとの平均の割合（MTD(f) 法 / αβ 法）をまとめた表です。
| 深さ | sv × ab × | sv × ab 〇 | sv 〇 ab × | sv 〇 ab 〇 |
|---|---|---|---|---|
| 0 | 83 % | 105 % | 69 % | 71 % |
| 1 | 86 % | 108 % | 72 % | 75 % |
| 2 | 71 % | 107 % | 94 % | 98 % |
| 3 | 88 % | 111 % | 92 % | 98 % |
| 4 | 75 % | 111 % | 98 % | 110 % |
| 5 | 90 % | 116 % | 107 % | 114 % |
| 6 | 95 % | 118 % | 140 % | 140 % |
| 7 | 127 % | 128 % | 166 % | 166 % |
| 8 | 166 % | 132 % | 200 % | 200 % |
sv × ab 〇 では残念ながら相変わらずすべての場合で MTD(f) 法のほうが効率が悪いですが、それ以外の場合 では置換表を利用しない場合と比べて 先程よりも深いノードまで MTD(f) のほうが効率が良く なっています。なお、深さが浅いほうが MTD(f) 法の方が効率が良い 点は 置換表を利用しない場合と同様 です。
置換表を利用した場合に効率が上昇する理由
αβ 法と比較した場合に、置換表を利用したほうがより効率が高くなる理由 は、前回の記事でも説明しましたが、MTD(f) 法 では 同じノードに対して 異なるウィンドウで 複数回の αβ 値を計算 するので、同じ子孫ノードに対して何度も αβ 値を計算 することになるからです。
そのことを確認するために、毎回の null window search で 計算されたノードの数などを表示 するように ai_mtdf を修正することにします。その際に回数を「その回の null window search での回数/回数の合計」のように表示することにします。また、前回の記事で示した 下記の表の情報の表示 を行うことにします。ただし、回数と分類の列の表示はあまり重要ではないので省略しました。
| 回数 | 分類 | ウィンドウ | αβ 値 | αβ の範囲 | MM の範囲 |
|---|---|---|---|---|---|
| 1 | $f < s$, [$-∞$, $∞$] | ($f_0 - 1$, $f_0$) | $f_1$ | fail high | [$f_1$, $∞$] |
下記はそのように ai_mtdf を修正したプログラムです。
- 8 行目：結果の表の見出しの行を表示する
-
11 行目：
countにはそれまでに行なった null window search で評価値を計算したノードの合計が計算されている。この回での null window search の合計を計算するために、null window search を行う直前のcountをprevcountに代入して記録しておく -
15、17 行目：計算した αβ の範囲の種類表す文字列を
typeに代入する - 19 行目：その回の null window search に対する情報を表示する
- 23 行目の前にあった
couhtを表示する処理はもう必要がないので削除した
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 beta = f + 1 if lbound == f else f
11 prevcount = count
12 f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
13 if f >= beta:
14 lbound = f
15 type = "fail high"
16 else:
17 ubound = f
18 type = "fail low "
19 dprint(debug, f"{count - prevcount:5}/{count:5} | ({beta - 1:2}, {beta:2}) | {f:2} | {type} | [{lbound:4}, {ubound:4}]")
20
21 score = f
22
23 if calc_count:
24 return count
25 if mb.turn == Marubatsu.CIRCLE:
26 score *= -1
27 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):
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}/{count:5} | ({beta - 1:2}, {beta:2}) | {f:2} | {type} | [{lbound:4}, {ubound:4}]")
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:
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}/{count:5} | ({beta - 1:2}, {beta:2}) | {f:2} | {type} | [{lbound:4}, {ubound:4}]")
score = f
- dprint(debug, "count =", count)
if calc_count:
return count
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
上記の修正後に下記のプログラムで 置換表を利用しない場合 の ゲーム開始時の局面 のミニマックス値を計算すると、実行結果のように 1 回目 の null window search で 966 個、2 回目 で 16159 個 のノードの評価値が計算されたことがわかります。また、それぞれの null window search での ウィンドウ、計算された αβ 値、ミニマックス値の範囲 がどのように変化したかを 確認することができます。
mb = Marubatsu()
ai_mtdf(mb, calc_score=True, calc_count=True, debug=True)
実行結果
count | ウィンドウ | αβ 値 | type | MM の範囲
966/ 966 | (-1, 0) | 0 | fail high | [ 0, inf]
16159/17125 | ( 0, 1) | 0 | fail low | [ 0, 0]
なお、ゲーム開始時の局面 は 引き分けの局面 なのでその ミニマックス値は 0 です。上記のプログラムでは f = 0 という 正しいミニマックス値を推定 したので、前回の記事で検証した $\boldsymbol{f = s}$, [$\boldsymbol{-∞}$, $\boldsymbol{∞}$] という分類で行なわれる 下記の表と同じ計算 が行なわれることが確認できます。
| 回数 | 分類 | ウィンドウ | αβ 値 | αβ の範囲 | MM の範囲 |
|---|---|---|---|---|---|
| 1 | $f = s$, [$-∞$, $∞$] | ($s - 1$, $s$) | $f_1 = s$ | fail high | [$f_1$, $∞$] = [$s$, $∞$] |
| 2 | $f = s$, [$f$, $∞$] | ($s$, $s + 1$) | $f_2=s$ | fail low | [$f_1$, $f_2$] = [$s$, $s$] |
次に、下記のプログラムで 置換表を利用する場合 の ゲーム開始時の局面 のミニマックス値を計算すると、実行結果のように 1 回目 の null window search で 356 個、2 回目 で 521 個 のノードの評価値が計算されたことから、置換表を利用する事で 2 回目 の null window search で評価値が計算されたノードの数が 大幅に減ったことが確認 できます。なお、ウィンドウや αβ 値など、それ以外の部分の表示は置換表を利用する場合とそうでない場合で同じになります。
ai_mtdf(mb, use_tt=True, calc_score=True, calc_count=True, debug=True)
実行結果
count | ウィンドウ | αβ 値 | type | MM の範囲
356/ 356 | (-1, 0) | 0 | fail high | [ 0, inf]
521/ 877 | ( 0, 1) | 0 | fail low | [ 0, 0]
次に、下記のプログラムで ゲーム開始後に (0, 0) に着手 を行った局面で比較を行うと、実行結果のように 1 回目 の null window search の 回数が 965 から 355 に 約 1/3 に減っている のに対し、2 回目 の null window search の 回数が 1251 から 209 に 約 1/6 に さらに大幅に減っている ことが確認できます。
mb.move(0, 0)
ai_mtdf(mb, calc_score=True, calc_count=True, debug=True)
ai_mtdf(mb, use_tt=True, calc_score=True, calc_count=True, debug=True)
実行結果
count | ウィンドウ | αβ 値 | type | MM の範囲
965/ 965 | (-1, 0) | 0 | fail high | [ 0, inf]
1251/ 2216 | ( 0, 1) | 0 | fail low | [ 0, 0]
count | ウィンドウ | αβ 値 | type | MM の範囲
355/ 355 | (-1, 0) | 0 | fail high | [ 0, inf]
209/ 564 | ( 0, 1) | 0 | fail low | [ 0, 0]
このように、MTD(f) 法 では 置換表を利用することが重要 であることが確認できました。
余裕がある方は他の局面でも比較してみて下さい。
今回の記事のまとめ
今回の記事では αβ 法と比較 することで MTD(f) 法の効率について検証 しました。また、ゲーム木の 部分木の深さと枝狩りの関係について検証 し、部分木の深さが浅すぎる と MTD(f) 法 は αβ 法よりも効率が悪くなる場合がある ことを示しました。
次に、MTD(f) で置換表を利用することの重要性について検証 しました。
今回の記事の MTD(f) 法での計算では、すべてのノードでミニマックス値を 0 と推定 して行なったため、ミニマックス値の 推定の精度はあまり高くありません。それでも 〇× ゲームでは、浅いノードの局面であれば MTD(f) のほうが αβ 法よりも効率が高くなります。
次回の記事では推定したミニマックス値の精度と MTD(f) 法の効率の関係と、スカウト法と MTD(f) 法を比較することで MTD(f) 法の効率の検証を行うことにします。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| ai.py | 本記事で更新した ai_new.py |
次回の記事
近日公開予定です。
-
指数関数は $n^d$ のような関数で、$n^d$ の場合は $d$ が 1 増えるごとに $n$ 倍になります。ただし、爆発的に増えるのは $n > 1$ の場合です ↩