ミニマックス法の続きです。今回はミニマックス法 (アルファベータ法) の改良方法について取り上げます。題材とするゲームは前回と同じくカラハ (Kalah) です。
ミニマックス法の場合、先手は最も大きな評価値の手を選び、後手は最も小さな評価値の手を選びます。ここで後手番のときに評価値の符号を反転すると、先手と同様に後手でも最大な評価値の手を選べばよいことになります。つまり、手番を変えて思考ルーチンを呼び出すときは、その返り値 (評価値) にマイナス符号をつけて符号を反転させるわけです。この方法を「ネガマックス法 (nega-max method)」といいます。
ネガマックス法は、先手番でも後手番でも評価値が最大となる指し手を選ぶようになるため、プログラムはミニマックス法よりも簡単になります。なお、ネガマックス法の動作はミニマックス法とまったく同じです。
プログラムは次のようになります。
リスト : ネガマックス法
def negamax(turn, depth, board):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
#
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
return value, move
前回のミニマックス法は関数 move_first() と move_second() の相互再帰になりましたが、ネガマックス法は関数 negamax() の再帰呼び出しだけでプログラムすることができます。
引数 turn は手番を表します。ゲームが終了する、または depth が 0 の場合、関数 value_func() で評価値を求めたあと、手番が後手であれば、評価値 v を -v にして符号を反転します。この処理は value_func() に turn を渡して、その中で行ってもかまいません。その場合はモジュール board を修正してください。
石を動かしたあと、その結果 result が KALAH であれば、手番をそのままにして negamax() を再帰呼び出しします。このとき、評価値の符号を反転する必要はありません。手番を変える場合、次の turn は (turn + 7) % 14 で求めることができます。そして、negamax() を再帰呼び出しして、返り値 (評価値) v を -v にして符号を反転します。
KALAH の処理を簡略化する場合は次のようになります。
リスト : KALAH の処理 (簡易版)
if result == KALAH:
# 手番は同じで 1 手だけ探索
v, m = negamax1(turn, 1, b)
for x in m:
b.move_stone(turn, x)
# 手番を変える
v, _ = negamax1((turn + 7) % 14, depth - 1, b)
v = -v
次がネガマックス法の心臓部である指し手の選択処理です。これはとても簡単で、v が value よりも大きいときに、その指し手を選ぶだけです。このようにプログラムを簡単に記述できるのがネガマックス法の長所です。
実行結果 (勝敗と局面の評価回数) は当然ですがミニマックス法とまったく同じになります。興味のある方は実際に試してみてください。
次はネガマックス法に対応したアルファベータ法のプログラムを説明します。これを「ネガアルファ法 (nega-α method)」と呼びます。次のリストを見てください。
リスト : ネガアルファ法
def negamax(turn, depth, board, limit):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
#
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, limit)
else:
# 手番を変える
v, _ = negamax((turn + 7) % 14, depth - 1, b, -value)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= limit: break
return value, move
引数 limit が基準値になります。ネガアルファ法の場合、手番を変えるときは基準値の符号を反転して渡すことに注意してください。前回のアルファベータ法の場合、基準値として value を渡しましたが、ネガアルファ法の場合は -value を渡します。そうすると、ネガアルファ法による枝刈りの条件は value >= limit で表すことができます。このように、ネガアルファ法のプログラムもとても簡単になります。
KALAH の処理を簡略化する場合は次のようになります。
リスト : KALAH の処理 (簡易版)
if result == KALAH:
# 手番は同じで 1 手だけ探索
v, m = negamax1(turn, 1, b, MAX_VALUE)
for x in m:
b.move_stone(turn, x)
# 手番を変える
v, _ = negamax1((turn + 7) % 14, depth - 1, b, -value)
v = -v
実行結果 (勝敗と局面の評価回数) は当然ですがアルファベータ法とまったく同じになります。興味のある方は実際に試してみてください。
ところで、今までのアルファベータ法のプログラムでは、次の局面の基準値となる変数 value の値を MIN_VALUE または MAX_VALUE で初期化しているため、最初に探索する局面 (最も左側の枝の局面) の評価値を求めないと、アルファベータ法による枝刈りは発生しません。α値とβ値を (α, β) で表すと、新しい局面は (-∞, β) または (α, ∞) の幅で局面を探索することになります。たとえば、左側の枝から順番に探索していく場合、最も左側の枝の評価値 value が求まると、それ以降の枝は (value, β) または (α, value) の幅で局面を探索します。
これに対し、一つ前の局面で求まったα値とβ値を使っても、アルファベータ法を動作させることができます。つまり、新しい局面でも (α, β) の幅でゲーム木を探索してもいいのです。(-∞, β) または (α, ∞) で探索を始めるよりも (α, β) の方が幅が狭くなるので、枝刈り (αカット、βカット) の回数が多くなることが期待できます。
これで正しく動作することを、前回示したアルファベータ法の図を使って確かめてみましょう。アルファベータ法の図を再掲します。
Ｒ 先手の局面
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
Ａ(3) Ｂ(2) 後手の局面
／ ＼ ／ ×
／ ＼ ／ ×
Ｃ(3) Ｄ(4) Ｅ(2) Ｆ(5) 先手の局面
／ ＼ ／ × ／ ＼ ／ ＼
Ｇ Ｈ Ｉ Ｊ Ｋ Ｌ Ｍ Ｎ 後手の局面
１ ３ ４ ２ ２ １ ３ ５ 評価値
× × ×
図 1 : アルファベータ法
局面 A の評価は次の図のようになります。
後手の局面 Ａ
／ ＼
／ ＼
先手の局面 Ｃ Ｄ
／ ＼ ／ ×
後手の局面 Ｇ Ｈ Ｉ Ｊ
評価値 １ ３ ４
(1) R = (-∞, ∞) -> A = (-∞, ∞) -> C = (-∞, ∞)
(2) G を評価 => 1, C = (1, ∞)
(3) H を評価 => 3, C = (3, ∞)
(4) C の評価 => 3, A = (-∞, 3)
(5) A = (-∞, 3) -> D = (-∞, 3)
(6) I を評価 => 4, D = (4, 3) 4 >= 3 なのでβカット
(7) D の評価 => 4, A = (-∞, 3)
(8) A の評価 => 3, R = (3, ∞)
図 2 : ベータカット
局面 R のα値とβ値は R = (-∞, ∞) になります。この値が渡されていくので、局面 C も C = (-∞, ∞) になります。次に、局面 G の評価値を求めると 1 になります。局面 C は先手の局面なので、α値と評価値を比較して大きな値を選びます。したがって、C = (1, ∞) になります。次に G の局面を評価して C = (3, ∞) になります。そして、局面 C の評価値はα値の 3 になります。
局面 A は後手の局面なので、評価値とβ値を比較して小さな値を選びます。C の評価値は 3 なので、A = (-∞, 3) になります。次に局面 D を評価します。α値とβ値は局面 A の値が渡されるので D = (-∞, 3) になります。そして、局面 I を評価します。I の値は 4 になるので、D = (4, 3) になり α値 >= β値 の条件を満たします。ここでβカットされて、局面 D の評価値は 4 になります。
局面 A に戻って、D の評価値 4 とβ値 3 を比較します。β値のほうが小さいので、D は選択されません。 A = (-∞, 3) のままです。そして、β値 3 が返されて、局面 R に戻ります。R は先手の局面なのでα値と評価値を比較して大きな値を選択します。したがって、R = (3, ∞) になります。
次に、局面 B の評価を下図に示します。
Ｒ
／ ＼
／ ＼
後手の局面 Ａ Ｂ
／ ×
／ ×
先手の局面 Ｅ Ｆ
／ ＼
後手の局面 Ｋ Ｌ
評価値 ２ １
(1) R = (3, ∞) -> B = (3, ∞) -> E = (3, ∞)
(2) K を評価 => 2, E = (3, ∞)
(3) L を評価 => 1, E = (3, ∞)
(4) E の評価 => 3, B = (3, 3) 3 >= 3 なのでαカット
(5) B の評価 => 3, R = (3, ∞)
(6) R の評価 => 3, (A を選択する)
図 3 : アルファカット
R = (3, ∞) の値が渡されていくので、局面 E も E = (3, ∞) になります。次に、K を評価します。評価値は 2 でα値 3 よりも小さいので、この局面は選択されません。次に、局面 L を評価しますが、評価値が 1 なのでこの局面も選択されません。このように、α値よりも小さな評価値の局面しか存在しない場合、局面を選択することができなくなります。
この場合、2 通りの方法があります。一つはα値を E の評価値として返す方法です。既にα値が 3 となる局面が見つかっているので、これよりも小さな局面が選択されることはありません。正確な評価値がわからなくても、α値以下であることがわかればアルファベータ法は動作します。評価値として 3 を返すと、上図 (4) のように B = (3, 3) になるので、条件 α値 >= β値 を満たしてαカットされます。
もう一つは最も大きな評価値を返す方法です。上図の場合では、局面 K の評価値 2 を返します。この方法を「fail soft [*1] アルファベータ法」と呼びます。アルファベータ法 (ネガアルファ法) の場合、どちらの方法でも正常に動作します。前者の場合、B の評価値は 3 になり、後者の場合は 2 になりますが、どちらの場合でも局面 A が選択されます。
この fail soft をうまく使った方法に window search があります。window とはα値とβ値の幅 (α, β) のことです。アルファベータ法でゲーム木を探索する場合、ルートの局面では (-∞, ∞) を指定するのが普通ですが、window search では window の幅を狭めて探索を行います。とくに、window の幅を極端に狭めて (α, α + 1) に制限する方法を null window search といいます。ネガスカウト (NegaScout) 法や MTD(f) 法は null window search を使って、アルファベータ法よりも効率よくゲーム木を探索することができます。
それではプログラムを作りましょう。次のリストを見てください。
リスト : ネガアルファ法の改良
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, []
#
value = alpha
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, value, beta)
else:
# 手番を変える
v, _ = negamax((turn + 7) % 14, depth - 1, b, -beta, -value)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= beta: break
return value, move
引数 alpha がα値、beta がβ値です。変数 value は評価値を格納します。ネガアルファ法は MIN_VALUE で初期化しましたが、このプログラムでは alpha で初期化します。これにより、alpha よりも大きな値の指し手が選択されます。そして、value が beta 以上になったら枝刈りを行います。ネガアルファ法を使っているので、手番を変えるときは符号を反転するとともに、α値とβ値を逆にして渡すことに注意してください。つまり、-beta, -value の順番で渡します。手番を変えないときは value, beta の順番で渡します。
ところで、このプログラムは fail soft ではありません。局面が選択されなかった場合は alpha を返します。fail soft にするには次のように修正します。
リスト : ネガアルファ法の改良 (failsoft)
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, []
#
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
return value, move
value は MIN_VALUE に初期化します。そして、negamax を再帰呼び出しするときは、alpha と value の大きいほうを関数 max で選んで渡します。これで、alpha よりも小さな評価値の局面しか見つからない場合でも、value にはその中の最大値がセットされます。最後に value, move を返します。
それでは、実行結果を示しましょう。ゲームの結果は、当然ですがアルファベータ法とネガアルファ法改良版で変わりはありません。改良版の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。改良方法が有効に機能すれば、アルファベータ法よりも局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 41, 31 : 43, 17 : 26, 37 : 39, 33
: 6207 : 40657 : 85880 : 226145
: 2672 : 13450 : 39302 : 100648
3 : 39, 23 : 40, 32 : 53, 19 : 48, 24
後 : 1757 : 11320 : 119750 : 65362
: 1654 : 10122 : 37689 : 37778
手 4 : 36, 36 : 43, 29 : 34, 38 : 44, 28
: 30242 : 31230 : 111266 : 238004
: 18117 : 19860 : 58028 : 116496
5 : 23, 49 : 26, 39 : 43, 29 : 35, 37
: 504203 : 221814 : 505170 : 815589
: 100583 : 86327 : 183703 : 314184
上段 : 先手の石数, 後手の石数 中段 : アルファベータ法 下段 : ネガアルファ改良版
ほとんどの場合で評価回数は大幅に減少しています。改良版の効果はとても大きいですね。ゲーム木を探索する場合、(α, β) の範囲を狭める方法は有効であることがわかります。
表 : 局面の評価回数 (KALAH 簡易版)
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 37, 23 : 37, 22 : 41, 31 : 39, 33
: 1500 : 4474 : 12138 : 32710
: 1500 : 4474 : 11097 : 24086
3 : 35, 37 : 49, 23 : 43, 21 : 37, 25
後 : 1726 : 11476 : 7779 : 54995
: 1726 : 11476 : 6871 : 43778
手 4 : 26, 46 : 35, 37 : 31, 41 : 49, 23
: 15592 : 23685 : 21359 : 53430
: 12409 : 20905 : 16909 : 37308
5 : 45, 27 : 37, 27 : 28, 44 : 24, 48
: 39890 : 25602 : 50537 : 145099
: 31981 : 19961 : 40470 : 117365
上段 : 先手の石数, 後手の石数 中段 : アルファベータ法 下段 : ネガアルファ法改良版
次に、KALAH の処理を簡略化した結果を示します。探索レベルが低いと効果はほとんどありませんが、レベルを上げると効果がでてくるようです。簡易版の場合、レベル 5 までならばアルファベータ法で十分のようです。
次は null window search について簡単に説明します。null window search は window の幅を (α, α + 1) のように制限してアルファベータ法による探索を行います。window の幅がとても狭いため、通常のアルファベータ法よりも多くの枝刈りが発生し、高速に探索することができます。
ただし、null winodow search で正確な評価値を求めることはできません。ミニマックス法で求められる正確な評価値を v、window の幅を (a, a + 1) とすると、null window search は次の条件を満たす評価値 x を返します。
(1) v <= x <= a (2) a + 1 <= x <= v
(1) の場合を fail-low といい、(2) の場合を fail-high といいます。fail-low の場合、正しい評価値 v は x 以下であることがわかります。また fail-high の場合、v は x 以上であることがわかります。つまり、null window search を使うと、評価値が a よりも大きいか小さいかを高速に判定することができるわけです。
null window search を使った探索方法には、ネガスカウト (NegaScout) 法や MTD(f) 法などがありますが、今回はネガスカウト法を取り上げます。ネガスカウト法は null window search を使って、アルファベータ法の探索で winodw の幅を絞り込む方法です。
たとえば、winodw の幅が (a, b) のときに (a, a + 1) で null window search を行ってみましょう。返り値 x が fail-low の場合、正確な評価値は a 以下であることが保障されているので、評価値はα値以下であることが確定します。したがって、この局面が選択されることはありません。探索は null window search だけでよく、正確な評価値を求める必要はありません。
次に、返り値 x が b 以上の場合、正確な評価値は x 以上であることが保障されているので、β値以上であることが確定します。したがって、ここで枝刈りすることができます。この場合も null window search で求めた評価値 x だけで十分です。
最後に、a < x < b の場合ですが、正確な評価値は x 以上であることが保障されているので、window の幅を (x, b) に設定してアルファベータ法で正確な評価値を求めます。幅が (x, b) と制限される分だけ、効率的に探索することができます。
ネガスカウト法の場合、最初に探索する (最も左側の枝の) 局面は通常のネガアルファ法で評価値を求め、そのあとに探索する局面に対して null window search を適用します。一般に、アルファベータ法の探索では、評価値の高い局面から順番に探索すると効率が良くなります。評価値が高いほど window の幅が制限されるので、最初に高い評価値が求まると効率よく枝刈りできるわけです。
これはネガスカウト法でも同じです。高い評価値の局面から順番に探索した場合、最初の評価値を求めたあと、そのあとの局面は最初の評価値よりも大きくならないことを null window search で確認するだけですみます。一般に、指し手の順番を並べ替えることでアルファベータ法の効率を改善する方法を move ordering といいます。
たとえば、数レベルの浅い探索を行って評価値を求め、それに基づいて指し手の順番を並べ替えます。もちろん、完全に move ordering することは不可能ですが、指し手が多いゲームでは効果があります。ネガスカウト法の場合、move ordering と一緒に用いられることが多いようです。カラハの場合、指し手が最大でも 6 通りしかないので、move ordering は行わないことにします。
ネガスカウト法のプログラムは次のようになります。
リスト : ネガスカウト法 (failsoft)
def negascout(turn, depth, board, alpha, beta):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
#
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:
# 手番は同じまま
# 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
return value, move
石を動かしたあと、手番を変えるときに null window search を適用します。result が KALAH の場合でも null window search を適用できますが、実際に試してみると効果がなかったで不適用としました。また、move ordering を行っていないので、最初に探索する局面でも null window search を適用することにします。一般的なネガスカウト法とはちょっと違いますが、カラハの場合はこれでも十分に機能するようです。
手番を変える場合、最初に alpha と value を比較して大きいほうを変数 a にセットします。そして、window の幅を (-(a+1), -a) に制限して関数 negascout() を再帰呼び出しします。これで null window search が実行されます。プログラムはネガアルファ法で実装しているので、null window search の幅 (a, a+1) は、符号を反転してα値とβ値を逆にすることに注意してください。
評価値 v が a よりも大きくて beta よりも小さい場合は、window の幅を (v, beta) に設定してネガアルファ法で再探索します。これで正しい評価値を求めることができます。あとはネガアルファ法と同じで、v が value よりも大きい場合はその局面を選択し、beta 以上の場合は枝刈りを行います。
それでは、実行結果を示しましょう。ゲームの結果は、当然ですがネガアルファ法の改良版とネガスカウト法で変わりはありません。ネガスカウト法の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。ネガスカウト法が有効に機能すれば、ネガアルファ法の改良版よりも局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 41, 31 : 43, 17 : 26, 37 : 39, 33
: 2672 : 13450 : 39302 : 100648
: 3266 : 8331 : 29077 : 61463
3 : 39, 23 : 40, 32 : 53, 19 : 48, 24
後 : 1654 : 10122 : 37689 : 37778
: 2101 : 10270 : 35314 : 36693
手 4 : 36, 36 : 43, 29 : 34, 38 : 44, 28
: 18117 : 19860 : 58028 : 116496
: 18432 : 19705 : 45380 : 86734
5 : 23, 49 : 26, 39 : 43, 29 : 35, 37
: 100583 : 86327 : 183703 : 314184
: 90777 : 81087 : 139926 : 273441
上段 : 先手の石数, 後手の石数 中段 : ネガアルファ法改良版 下段 : ネガスカウト法
先手と後手の探索レベルが 4 以上になると、null window search の効果により局面の評価回数はネガスカウト法のほうが少なくなります。探索レベルが 2, 3 の場合は、ネガアルファ法改良版で十分のようです。ご参考までに、探索レベルが 6, 7, 8 の場合を示します。
表 : 局面の評価回数
先手
: 6 : 7 : 8
-------+---------+---------+----------
6 : 28, 44 : 43, 29 : 36, 36
: 590188 : 2684393 : 1904761
: 428582 : 1264011 : 1150929
後 7 : 34, 38 : 47, 25 : 46, 26
: 1327863 : 4024770 : 19937206
: 947314 : 1982292 : 9305964
手 8 : 40, 32 : 20, 52 : 34, 38
: 1855840 : 5071128 : 2444127
: 1342922 : 3063914 : 1651417
上段 : 先手の石数, 後手の石数 中段 : ネガアルファ法改良版 下段 : ネガスカウト法
ネガスカウト法のほうが評価回数は少なくなります。ゲーム木を深く探索する場合は、ネガアルファ法よりもネガスカウト法のほうがよさそうです。ところで、move ordering を行うと、異なる結果になるかもしれません。興味のある方は試してみてください。
#
# kalah2.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, []
#
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
return value, move
def negamax1(turn, depth, board):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
#
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:
# 手番は同じで 1 手だけ探索
v, m = negamax1(turn, 1, b)
for x in m:
b.move_stone(turn, x)
# 手番を変える
v, _ = negamax1((turn + 7) % 14, depth - 1, b)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
return value, move
# 実行
def play(first_depth, second_depth, think1 = negamax, think2 = negamax):
init_count()
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
if turn == FIRST_KALAH:
value, move = think1(turn, first_depth, board)
else:
value, move = think2(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
#
# kalah3.py : カラハ (ネガアルファ法)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from board import *
# ネガアルファ法
def negamax(turn, depth, board, limit):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
#
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, limit)
else:
# 手番を変える
v, _ = negamax((turn + 7) % 14, depth - 1, b, -value)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= limit: break
return value, move
def negamax1(turn, depth, board, limit):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
#
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:
# 手番は同じで 1 手だけ探索
v, m = negamax1(turn, 1, b, MAX_VALUE)
for x in m:
b.move_stone(turn, x)
# 手番を変える
v, _ = negamax1((turn + 7) % 14, depth - 1, b, -value)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= limit: break
return value, move
# 実行
def play(first_depth, second_depth, think1 = negamax, think2 = negamax):
init_count()
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
if turn == FIRST_KALAH:
value, move = think1(turn, first_depth, board, MAX_VALUE)
else:
value, move = think2(turn, second_depth, board, 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
#
# kalah4.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, []
#
value = alpha
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, value, beta)
else:
# 手番を変える
v, _ = negamax((turn + 7) % 14, depth - 1, b, -beta, -value)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= beta: break
return value, move
def negamax1(turn, depth, board, alpha, beta):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
#
value = alpha
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:
# 手番は同じまま 1 手だけ探索する
v, m = negamax1(turn, 1, b, MIN_VALUE, MAX_VALUE)
for x in m:
b.move_stone(turn, x)
# 手番を変える
v, _ = negamax1((turn + 7) % 14, depth - 1, b, -beta, -value)
v = -v
# ネガマックス法 : 大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# ネガアルファ法
if value >= beta: break
return value, move
# 実行
def play(first_depth, second_depth, think1 = negamax, think2 = negamax):
init_count()
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
if turn == FIRST_KALAH:
value, move = think1(turn, first_depth, board, MIN_VALUE, MAX_VALUE)
else:
value, move = think2(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
#
# kalah5.py : カラハ (ネガスカウト法)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from board import *
# ネガスカウト法 (failsoft)
def negascout(turn, depth, board, alpha, beta):
if board.check_gameover() or depth == 0:
v = board.value_func()
if turn == SECOND_KALAH: v = -v
return v, []
#
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:
# 手番は同じまま
# 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
return value, move
# 実行
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
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)
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