ミニマックス法の続きです。今回は「置換表 (transposition table)」と「MTD(f) 法」を取り上げます。題材とするゲームは前回と同じくカラハ (Kalah) です。
置換表は局面の情報を格納しておく表 (table) のことです。ゲーム木の探索では、同じ局面が何度も現れることがよくあります。同じ局面を何度も探索するのは時間の無駄なので、すでに探索した局面はその情報 (評価値、手番、探索の深さなど) を表に格納しておき、同一局面が現れたら表の情報を再利用します。
表の情報が十分なものであれば、そこで探索を打ち切って、評価値をそのまま返すことができます。もし、情報が不十分な場合でも、それを基にして探索を続行し、その結果で表の情報を更新します。
一般に、何度も同じ値を計算することがないように、計算した値は表に格納しておいて、2 回目以降は表から計算結果を求めることでアルゴリズムを高速化する手法を「表計算法」といいます。
有名なところでは拙作のページ「欲張り法 [2], 動的計画法」で説明した動的計画法や、「再帰定義」で説明したメモ化などがあります。置換表は表計算法の一種と考えることができます。置換表はチェス、将棋、リバーシなどのプログラムでよく用いられる手法です。
一般に、置換表はハッシュ法を使って実装します。今回は Python の辞書 (dictionary) を使って置換表をプログラムしてみましょう。
まずは最初にネガマックス法で置換表を使ってみて、どの程度の効果があるか確かめてみましょう。ネガマックス法の場合、置換表に登録するデータは評価値、指し手、手番、探索の深さなどがあります。とくに、探索の深さは重要な情報です。次の図を見てください。
Ｒ レベル０
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
Ａ Ｂ レベル１
／ ＼ ／ ＼
／ ＼ ／ ＼
Ｃ Ｄ Ｅ Ｆ レベル２
／ ＼ ／ ＼ ／ ＼ ／ ＼
Ｇ Ｈ Ｉ Ｊ Ｋ Ｌ Ｍ Ｎ レベル３
図 1 : ゲームの木
たとえば、探索レベルが 5 で、局面 J と B が同じだったとしましょう。この場合、置換表には J の評価値が登録されますが、局面 B にこの評価値を適用することはできません。J はレベル 3 の局面なので、このあと 2 手先読みした局面の中から J の評価値が求まります。局面 B はレベル 1 なので、あと 4 手先読みしないと探索レベルが 5 に到達しません。つまり、F で J の評価値を適用すると、探索レベルが 3 に下がってしまうのです。
逆に、レベル 1 の局面 A とレベル 3 の局面 N が同じだった場合、A の評価値を N に適用すると、その探索レベルは 7 に上がります。つまり、2 レベル分だけ深くゲーム木を探索できたことになります。この場合、置換表の評価値を採用して、N の評価値として A の評価値を返しても問題ありません。また、同じレベルの局面の場合も置換表の評価値をそのまま利用することができます。
このように、探索の深さにより置換表の情報を採用するか否かを決定することができます。今回のカラハもそのようにプログラムすることができますが、勝敗の結果が今までと異なる場合がでてきます。そうすると、今までの評価結果と単純に比較するのは難しくなるので、置換表を使うのは探索レベルが同じ局面だけに制限することにします。この場合、置換表の効果を十分に引き出すことはできません。ご注意ください。
そこで、今回は探索の深さと手番も置換表 (Python の辞書) のキーに含めることにします。プログラムは次のようになります。
リスト : ネガマックス法 + 置換表
def negamax(turn, depth, board):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
# 置換表の探索
key = (depth, turn) + tuple(board.board)
if key in table: return table[key]
#
value = MIN_VALUE
move = []
for pos in range(turn - 6, turn):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(turn, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = negamax(turn, depth, b)
else:
# 後手番
v, _ = negamax((turn + 7) % 14, depth - 1, b)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# 置換表の更新
table[key] = (value, move)
return value, move
ネガマックス法の関数 negamax() に置換表の探索処理と更新処理を追加します。置換表 (Python の辞書) はグローバル変数 table にセットします。Python の辞書は配列 (Python のリスト) をキーに使用できないので、関数 tuple() で盤面 board をタプルに変換します。これに探索の深さと手番 (depth, turn) を追加して変数 key にセットします。key が table にある場合は、その値をそのまま返します。
置換表には評価値 value と指し手 move をタプルに格納してセットします。この処理は return の前で行います。それから、negamax() を呼び出す前に置換表 table をクリアすることをお忘れなく。なお、今回は盤面 board をそのままタプルに変換してキーとしましたが、盤面が大きなゲームでは局面のハッシュ値を高速に求めるための工夫が必要になります。ご注意ください。
それでは実行結果を示します。勝敗はネガマックス法とまったく同じです。置換表の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。置換表が有効に機能すれば、局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数 (ネガマックス法 + 置換表)
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 11775 : 90968 : 318340 : 1221294
: 11775 : 88587 : 280641 : 1133706
: 0 : 177 : 2163 : 8344
後 3 : 4383 : 41159 : 654559 : 588627
: 4169 : 39527 : 499265 : 465047
: 15 : 217 : 8348 : 10836
手 4 : 160765 : 131496 : 510241 : 1734092
: 153855 : 122566 : 471636 : 1594021
: 876 : 872 : 4000 : 12365
5 : 3648321 : 1580529 : 2488362 : 4806261
: 2750886 : 1319953 : 2086842 : 4093994
: 47583 : 17254 : 26862 : 40012
上段 : ネガマックス法 中段 : ネガマックス法 + 置換表 下段 : 置換表にヒットした回数
探索レベルが 2, 3 の場合、置換表の効果はほとんどありません。探索レベルが 4, 5 になると、置換表にヒットする回数が多くなり、その分だけ局面の評価回数が少なくなります。ただし、これだけで実行速度が高速になるとはかぎりません。置換表の探索に時間がかかるようでは、かえって実行速度が遅くなってしまいます。ご参考までにレベル 3, 4, 5 の実行時間を示します。
表 : ミニマックス法の実行時間 (単位 : 秒)
探索レベル: (3, 3) : (4, 4) : (5, 5)
-------------------------------------
置換表無し: 0.47 : 3.64 : 31.38
置換表有り: 0.45 : 3.53 : 29.15
実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
ミニマックス法の場合、置換表の効果はそれほど大きくないようです。
次はアルファベータ法 (ネガアルファ法) で置換表を使ってみましょう。アルファベータ法の場合、枝刈り (αカット、βカット) が行われると、局面の評価値はミニマックス法で求められる正確な値にはなりません。この値を minimax 値と呼ぶことにします。
window の幅を (α, β) とすると、null window search と同様にα値以下であれば fail-low になり、β値以上であれば fail-high になります。このため、置換表に評価値だけを格納しても、それが minimax 値なのか、それとも fail-low, fail-high なのか判断することができません。
そこで、置換表には minimax 値が存在する範囲 (lower, upper) を格納することにします。lower と upper は下限値と上限値を表し、MIN_VALUE と MAX_VALUE で初期化しておきます。そして、求めた評価値 value が fail-low であれば、minimax 値は value 以下であることがわかるので、置換表のデータを (lower, value) に書き換えます。
逆に、value が fail-high であれば、minimax 値は value 以上であることがわかるので、置換表のデータを (value, upper) に書き換えます。もしも、value が (α, β) の範囲内にあれば、それは minimax 値なので、置換表のデータを (value, value) に書き換えます。これで、minimax 値と fail-low, fail-high を区別することができます。
そして、置換表の範囲 (lower, upper) と window の幅 (α, β) を比較して、置換表の情報を採用するか否かを決定します。これは次に示す 3 通りの場合があります。
(1) β <= lower (2) upper <= α (3) upper == lower
(1) の場合、minimax 値はβ値以上にあることが確定するので、ここで枝刈りすることができます。この場合は評価値として lower を返します。(2) の場合、minimax 値はα値以下であることが確定します。つまり、fail-low になるので、この局面は選択されません。この場合、評価値として upper を返します。最後に (3) の場合は minimax 値なので、その値 (lower or upper) を返します。
これ以外の場合は、置換表の情報は採用しないで実際に探索を行います。このとき、(lower, upper) と (α, β) を比較して、window の幅が狭くなるように設定してから、ゲーム木を探索します。そして、その結果を使って置換表の情報を更新します。このように、アルファベータ法の場合はミニマックス法よりも処理が複雑になります。
プログラムは次のようになります。
リスト : ネガアルファ法 + 置換表
def negamax(turn, depth, board, alpha, beta):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
# 置換表
key = (depth, turn) + tuple(board.board)
if key in table:
lower, upper, m = table[key]
if lower >= beta: return lower, m
if upper <= alpha or upper == lower: return upper, m
alpha = max(alpha, lower)
beta = min(beta, upper)
else:
lower = MIN_VALUE
upper = MAX_VALUE
#
value = MIN_VALUE
move = []
for pos in range(turn - 6, turn):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(turn, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = negamax(turn, depth, b, max(alpha, value), beta)
else:
# 後手番
v, _ = negamax((turn + 7) % 14, depth - 1, b, -beta, -max(alpha, value))
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= beta: break
# 置換表の更新
if value <= alpha:
table[key] = (lower, value, move)
elif value >= beta:
table[key] = (value, upper, move)
else:
table[key] = (value, value, move)
return value, move
まず、置換表からデータ lower, value, m を取り出します。m は指し手になります。lower >= beta の場合、枝刈りできるので lower, m を返します。upper >= alpha の場合、fail-low になるので upper, m を返します。また、lower == upper の場合は minimax 値なので upper, m を返します。
それ以外の場合、alpha と lower を比較して、大きいほうを alpha にセットします。beta と upper の場合は、小さいほうを beta にセットします。
たとえば、lower < alpha < upper < beta であれば、window の幅は (alpha, upper) になります。これで、window の幅 (alpha, beta) を狭くしてゲーム木を探索することができます。置換表にデータがない場合は、lower を MIN_VALUE に、upper を MAX_VALUE に初期化します。
ゲーム木の探索が終わったら、置換表のデータを更新します。評価値 value が alpha 以下の場合は fail-low なので、minimax 値は value 以下であることがわかります。置換表の上限値を value に書き換えます。初出の局面の場合、lower は MIN_VALUE に初期化されているので、(MIN_VALUE, value) が minimax 値の範囲になります。
value が beta 以上であれば fail-high なので、置換表の下限値を value に書き換えます。初出の局面の場合、upper は MAX_VALUE に初期化されているので、(value, MAX_VALUE) が minimax 値の範囲になります。それ以外の場合、value は minimax 値になるので、上限値と下限値を value に書き換えます。
それでは実行結果を示します。勝敗はネガアルファ法とまったく同じです。置換表の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。置換表が有効に機能すれば、局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数 (ネガアルファ法改良版 + 置換表)
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 2672 : 13450 : 39302 : 100648
: 2672 : 12303 : 32903 : 94461
: 0 : 122 : 175 : 940
後 3 : 1654 : 10122 : 37689 : 37778
: 1589 : 9732 : 35909 : 33351
: 9 : 77 : 337 : 828
手 4 : 18117 : 19860 : 58028 : 116496
: 17342 : 19218 : 53016 : 104106
: 139 : 103 : 595 : 1432
5 : 100583 : 86327 : 183703 : 314184
: 81791 : 77532 : 161446 : 255539
: 1580 : 934 : 2576 : 5682
上段 : ネガアルファ法改良版 中段 : ネガアルファ法改良版 + 置換表 下段 : 置換表にヒットした回数
探索レベルが 2, 3, 4 の場合、置換表の効果はほとんどありません。探索レベルが 5 になると、置換表にヒットする回数が多くなり、その分だけ局面の評価回数が少なくなりますが、ミニマックス法よりも少ないです。もっと深く探索しないと、置換表の効果は現れないようです。ご参考までにレベル 3, 4, 5 の実行時間を示します。
表 : ネガアルファ法の実行時間 (単位 : 秒)
探索レベル: (3, 3) : (4, 4) : (5, 5)
------------------------------------
置換表無し: 0.22 : 0.63 : 2.63
置換表有り: 0.23 : 0.62 : 2.56
探索レベルが 3 の場合、実行時間は少し遅くなりました。探索レベルが 4, 5 の場合でも、置換表の効果はほとんどないようです。興味のある方は探索レベルを増やして試してみてください。
置換表はネガスカウト法でも利用することができます。次のリストを見てください。
リスト : ネガスカウト法
def negascout(turn, depth, board, alpha, beta):
if depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
# 置換表の探索
key = (depth, turn) + tuple(board.board)
if key in table:
lower, upper, m = table[key]
if lower >= beta: return lower, m
if upper <= alpha or upper == lower: return upper, m
alpha = max(alpha, lower)
beta = min(beta, upper)
else:
lower = MIN_VALUE
upper = MAX_VALUE
#
value = MIN_VALUE
move = []
for pos in range(turn - 6, turn):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(turn, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
if turn == SECOND_KALAH: v = -v
elif result == KALAH:
# 手番は同じまま
# null window search は適用しない
v, m = negascout(turn, depth, b, max(alpha, value), beta)
else:
# 後手番
# null window search
a = max(alpha, value)
v, _ = negascout((turn + 7) % 14, depth - 1, b, -(a+1), -a)
v = -v
if beta > v > a:
# 再探索
v, _ = negascout((turn + 7) % 14, depth - 1, b, -beta, -v)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if v > value:
value = v
move = [pos] + m
# ネガアルファ法
if value >= beta: break
# 置換表の更新
if value <= alpha:
table[key] = (lower, value, move)
elif value >= beta:
table[key] = (value, upper, move)
else:
table[key] = (value, value, move)
return value, move
ネガスカウト法のプログラムに置換表の処理を追加するだけです。置換表の探索と更新処理はネガアルファ法のプログラムとまったく同じです。
それでは、実行結果を示しましょう。勝敗はネガスカウト法とまったく同じです。置換表の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。置換表が有効に機能すれば、局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 3266 : 8331 : 29077 : 61463
: 3145 : 6742 : 25288 : 49840
: 167 : 491 : 2368 : 7581
後 3 : 2101 : 10270 : 35314 : 36693
: 1334 : 9208 : 25862 : 28412
: 294 : 1449 : 3155 : 4341
手 4 : 18432 : 19705 : 45380 : 86734
: 15615 : 12154 : 37836 : 55457
: 2553 : 1953 : 4233 : 6021
5 : 90777 : 81087 : 139926 : 273441
: 65232 : 61329 : 78267 : 187422
: 8342 : 6762 : 10206 : 20909
先手
: 6 : 7 : 8
-------+---------+---------+----------
6 : 428582 : 1264011 : 1150929
: 293413 : 733916 : 722508
: 29593 : 56751 : 53114
後 7 : 947314 : 1982292 : 9305964
: 413288 : 1439752 : 4708651
: 39482 : 86472 : 238704
手 8 : 1342922 : 3063914 : 1651417
: 925000 : 1472836 : 1105233
: 67427 : 97226 : 77675
上段 : ネガスカウト法 中段 : ネガスカウト法 + 置換法 下段 : 置換表にヒットした回数
探索レベルが 2, 3 の場合、置換表の効果はほとんどありません。探索レベルが高くなると、置換表にヒットする回数が多くなり、その分だけ局面の評価回数は少なくなります。ネガスカウト法の場合、null window search を行っている分だけ、置換表の効果は他の方法よりも大きくなるようです。
ご参考までにレベル 4, 5, 6 の実行時間を示します。
表 : ネガスカウト法の実行時間 (単位 : 秒)
探索レベル: (4, 4) : (5, 5) : (6, 6)
-------------------------------------
置換表無し: 0.63 : 2.58 : 3.84
置換表有り: 0.52 : 2.21 : 3.25
探索レベルを上げると、実行時間は置換表を用いたほうが速くなります。置換表の効果は十分に出ていると思います。
次は MTD(f) 法を説明します。MTD は "Memory Test Drive" の略で、探索した局面の情報をメモリに保存しておいて、null window search を繰り返し適用することで minimax 値が存在する範囲を絞っていく手法です。局面の情報は置換表を使って保存します。
MTD(f) 法は null window search で window の値を変えながらゲーム木を何度も探索するので、置換表がないと高速に動作しません。置換表が必須のアルゴリズムなのです。
ところで、今まで説明した方法は全て「深さ優先探索」でプログラムしています。ゲーム木を探索する場合、プログラムは深さ優先探索で実装するのが一般的ですが、このほかに「最良優先探索 (best-first search)」という方法を用いる場合があります。これは、局面の情報を保存しておいて、評価値の高い局面から優先的に調べていく方法です。
参考 URL『-鶯教-コンピュータ・リバーシ講座』によると、『MTD(f)とは、最良優先探索アルゴリズムSSS* を、Alpha-Beta とTransposition Table (TT)を用いて再定式化したものです。』 とのことです。一般に、最良優先探索のプログラムは複雑になりますが、MTD(f) 法のプログラムはとても簡単です。
それでは、プログラムを作りましょう。MTD(f) 法はアルファベータ法と置換表で作成した関数 negamax() を使うと、とても簡単にプログラムすることができます。次のリストを見てください。
リスト : MTD(f) 法
def mtdf(turn, depth, board, f):
global table
lower = MIN_VALUE
upper = MAX_VALUE
bound = f
table = {}
while lower < upper:
value, move = negamax(turn, depth, board, bound - 1, bound)
if value < bound:
upper = value # (lower, value)
else:
lower = value # (value, upper)
if lower == value:
bound = value + 1
else:
bound = value
return value, move
関数 mtdf() の引数 turn が手番、depth が探索レベル、board が盤面です。引数 f は "first guess" の意味で、null window search を行うときの window の初期値です。f が minimax 値に近いほど MTD(f) 法の探索効率は良くなります。f の設定が MTD(f) 法を使いこなすポイントの一つになります。
変数 lower, upper は minimax 値が存在する範囲を表します。lower が下限値で MIN_VALUE に初期化し、upper が上限値で MAX_VALUE に初期化します。bound は null window search での window の値で f に初期化します。table は置換表を格納します。MTD(f) 法の場合、同じゲーム木を何度も探索するので、置換表 table は while ループの前で空に初期化します。
あとは while ループで null window search を繰り返します。negamax() は置換表を用いたネガアルファ法のプログラムと同じです。window の幅を (bound - 1, bound) に設定して呼び出すと、null window search になります。置換表がないと MTD(f) 法は高速に動作しません。ご注意ください。
返り値 value が bound よりも小さい場合は fail-low なので、minimax 値は value 以下であることがわかります。upper を書き換えて範囲を (lower, value) に設定します。そうでなければ fail-high なので、minimax 値は value 以上であることがわかります。lower を value に書き換えて、範囲を (value, upper) に設定します。
それから、bound の値を更新します。value が下限値 (lower) の場合、次の null window search は (value, value + 1) で行うので、bound を value + 1 に設定します。value が上限値 (upper) の場合は、(value - 1, value) で null window search を行うので、bound を value に設定します。null window serach を繰り返すたびに (lower, upper) の範囲が絞られていき、最後は lower >= upper になります。ここで、while ループを終了して value, move を返します。
あとは f の設定ですが、今回は一つ前の評価値を使うことにします。次のリストを見てください。
リスト : 関数 mtdf の呼び出し
def play(first_depth, second_depth):
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
value_first = 0
value_second = 0
while True:
if turn == FIRST_KALAH:
value_first, move = mtdf(turn, first_depth, board, value_first)
else:
value_second, move = mtdf(turn, second_depth, board, value_second)
・・・ 省略 ・・・
先手番の評価値を value_first に、後手番の評価値を value_second に格納します。この値を mtdf の引数 f に渡します。簡単な方法ですが、カラハの場合はこれでも十分に機能するようです。このほかに、数レベルの浅い探索を行って評価値を求め、その値を使って MTD(f) で深く探索する方法があります。興味のある方はいろいろ試してみてください。
それでは実行結果を示します。勝敗は今までの方法とまったく同じです。局面の評価回数と置換表にヒットした回数は次のようになりました。
表 : 局面の評価回数 (MTD(f) 法)
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 2918 : 12567 : 19852 : 35114
: 586 : 3549 : 2596 : 3735
後 3 : 1363 : 5941 : 18378 : 18045
: 476 : 1228 : 2653 : 2004
4 : 9281 : 9818 : 26684 : 45592
手 : 1253 : 1455 : 3238 : 4850
5 : 19073 : 45141 : 58735 : 157227
: 2247 : 4080 : 4034 : 14716
先手
: 6 : 7 : 8
-------+---------+---------+---------
6 : 154844 : 624552 : 451126
: 11825 : 43571 : 20609
後 7 : 334048 : 1090707 : 3210172
: 23778 : 55462 : 162783
手 8 : 553670 : 1334806 : 687886
: 20377 : 91978 : 29592
上段 : MTD(f) 法 下段 : 置換表にヒットした回数
MTD(f) 法の場合、同じゲーム木を何度も探索するので、置換表にヒットする回数は他の方法よりも多くなると予想していました。確かにネガアルファ法よりも多くなりましたが、ネガスカウト法よりは少なくなりました。それだけではなく、局面の評価回数もネガスカウト法より少なくなりました。これは置換表の効果だけではなく、null window search を繰り返し適用する MTD(f) 法の効果が出ていると思われます。また、初期値 f の選択も適切だったのでしょう。ご参考までにレベル 4, 5, 6 の実行時間を示します。
表 : MTD(f) 法の実行時間 (単位 : 秒)
探索レベル: (4, 4) : (5, 5) : (6, 6)
-------------------------------------
NegaScout : 0.52 : 2.21 : 3.25 (置換表有り)
MTD(f) : 0.41 : 1.76 : 1.69
ネガスカウト法よりも MTD(f) 法のほうが高速になりました。MTD(f) 法は優秀なアルゴリズムだと思います。MTD(f) 法の場合、初期値 f の設定で実行時間は左右されます。興味のある方はいろいろ試してみてください。
#
# kalah6.py : カラハ (ネガマックス法 + 置換表)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from board import *
# ネガマックス法 + 置換表
def negamax(turn, depth, board):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
# 置換表の探索
key = (depth, turn) + tuple(board.board)
if key in table: return table[key]
#
value = MIN_VALUE
move = []
for pos in range(turn - 6, turn):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(turn, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = negamax(turn, depth, b)
else:
# 後手番
v, _ = negamax((turn + 7) % 14, depth - 1, b)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# 置換表の更新
table[key] = (value, move)
return value, move
# 実行
def play(first_depth, second_depth):
global table
init_count()
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
table = {}
if turn == FIRST_KALAH:
value, move = negamax(turn, first_depth, board)
else:
value, move = negamax(turn, second_depth, board)
# 表示
for x in move:
print('move', x)
board.move_stone(turn, x)
board.print_board()
print()
if board.check_gameover():
print('Game Over')
board.print_board()
print_count()
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH
#
# kalah7.py : カラハ (ネガアルファ法 + 置換表)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from board import *
# ネガアルファ法
def negamax(turn, depth, board, alpha, beta):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
# 置換表
key = (depth, turn) + tuple(board.board)
if key in table:
lower, upper, m = table[key]
if lower >= beta: return lower, m
if upper <= alpha or upper == lower: return upper, m
alpha = max(alpha, lower)
beta = min(beta, upper)
else:
lower = MIN_VALUE
upper = MAX_VALUE
#
value = MIN_VALUE
move = []
for pos in range(turn - 6, turn):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(turn, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = negamax(turn, depth, b, max(alpha, value), beta)
else:
# 後手番
v, _ = negamax((turn + 7) % 14, depth - 1, b, -beta, -max(alpha, value))
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= beta: break
# 置換表の更新
if value <= alpha:
table[key] = (lower, value, move)
elif value >= beta:
table[key] = (value, upper, move)
else:
table[key] = (value, value, move)
return value, move
# 実行
def play(first_depth, second_depth):
global table
init_count()
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
table = {}
if turn == FIRST_KALAH:
value, move = negamax(turn, first_depth, board, MIN_VALUE, MAX_VALUE)
else:
value, move = negamax(turn, second_depth, board, MIN_VALUE, MAX_VALUE)
# 表示
for x in move:
print('move', x)
board.move_stone(turn, x)
board.print_board()
print()
if board.check_gameover():
print('Game Over')
board.print_board()
print_count()
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH
#
# kalah8.py : カラハ (ネガスカウト法 + 置換表)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from board import *
# ネガスカウト法
def negascout(turn, depth, board, alpha, beta):
if depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
# 置換表
key = (depth, turn) + tuple(board.board)
if key in table:
lower, upper, m = table[key]
if lower >= beta: return lower, m
if upper <= alpha or upper == lower: return upper, m
alpha = max(alpha, lower)
beta = min(beta, upper)
else:
lower = MIN_VALUE
upper = MAX_VALUE
#
value = MIN_VALUE
move = []
for pos in range(turn - 6, turn):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(turn, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
if turn == SECOND_KALAH: v = -v
elif result == KALAH:
# 手番は同じまま
# null window search は適用しない
v, m = negascout(turn, depth, b, max(alpha, value), beta)
else:
# 後手番
# null window search
a = max(alpha, value)
v, _ = negascout((turn + 7) % 14, depth - 1, b, -(a+1), -a)
v = -v
if beta > v > a:
# 再探索
v, _ = negascout((turn + 7) % 14, depth - 1, b, -beta, -v)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if v > value:
value = v
move = [pos] + m
# ネガアルファ法
if value >= beta: break
# 置換表の更新
if value <= alpha:
table[key] = (lower, value, move)
elif value >= beta:
table[key] = (value, upper, move)
else:
table[key] = (value, value, move)
return value, move
# 実行
def play(first_depth, second_depth):
global table
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
table = {}
while True:
if turn == FIRST_KALAH:
value, move = negascout(turn, first_depth, board, MIN_VALUE, MAX_VALUE)
else:
value, move = negascout(turn, second_depth, board, MIN_VALUE, MAX_VALUE)
# 表示
for x in move:
print('move', x)
a = board.move_stone(turn, x)
board.print_board()
print
if a == KALAH: raise 'error'
if a == GAMEOVER:
print('Game Over')
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH
#
play(2, 2)
print_count()
#
# kalah9.py : カラハ (MTD(f)法)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from board import *
# ネガアルファ法 + 置換表
def negamax(turn, depth, board, alpha, beta):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
# 置換表
key = (depth, turn) + tuple(board.board)
if key in table:
lower, upper, m = table[key]
if lower >= beta: return lower, m
if upper <= alpha or upper == lower: return upper, m
alpha = max(alpha, lower)
beta = min(beta, upper)
else:
lower = MIN_VALUE
upper = MAX_VALUE
#
value = MIN_VALUE
move = []
for pos in range(turn - 6, turn):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(turn, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = negamax(turn, depth, b, max(alpha, value), beta)
else:
# 後手番
v, _ = negamax((turn + 7) % 14, depth - 1, b, -beta, -max(alpha, value))
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= beta: break
# 置換表の更新
if value <= alpha:
table[key] = (lower, value, move)
elif value >= beta:
table[key] = (value, upper, move)
else:
table[key] = (value, value, move)
return value, move
# MTD(f) 法
def mtdf(turn, depth, board, f):
global table
lower = MIN_VALUE
upper = MAX_VALUE
bound = f
table = {}
while True:
v, m = negamax(turn, depth, board, bound - 1, bound)
if v < bound:
upper = v # (lower, v)
else:
lower = v # (v, upper)
if lower == v:
bound = v + 1
else:
bound = v
if lower >= upper: return v, m
# 実行
def play(first_depth, second_depth):
init_count()
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
value_first = 0
value_second = 0
while True:
if turn == FIRST_KALAH:
value_first, move = mtdf(turn, first_depth, board, value_first)
else:
value_second, move = mtdf(turn, second_depth, board, value_second)
# 表示
for x in move:
#print('move', x)
board.move_stone(turn, x)
#board.print_board()
#print()
if board.check_gameover():
print('Game Over')
board.print_board()
print_count()
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH