今回はゲーム MiniMax に「アルファベータ法」を実装してみます。アルファベータ法の説明は拙作のページ Algorithms with Python: アルファベータ法 をお読みください。
それではアルファベータ法を実装しましょう。ポイントは基準値（α値、β値）の管理です。プログラムは次のようになります。
リスト : 先手の指し手を選択
def move_first(depth, board, prev, fval, sval, limit):
if depth == 0:
return value_func(fval, sval), -1
value = MIN_VAL
m = -1
for x in range(SIZE):
if board[prev][x] == NON_VAL: continue
num = board[prev][x]
board[prev][x] = NON_VAL
if gameover(board, prev, x):
v = value_func(fval, sval, True)
else:
v, _ = move_second(depth - 1, board, x, fval + num, sval, value)
board[prev][x] = num
# ミニマックス法
if v > value:
value = v
m = x
# アルファベータ法
if value >= limit: break
return value, m
引数 limit がアルファベータ法で使用する基準値です。この値は 1 手前の局面の評価値です。変数 value は MIN_VAL に初期化し、選択した指し手の評価値を格納します。この値が次の局面 (後手番) での基準値となります。逆に、後手 move_second() の場合は value を MAX_VAL で初期化します。これが評価値の中で最大の値となります。後手の場合、ミニマックスでは小さな値を選ぶので、最初に求めた評価値が無条件に選択されます。
アルファベータ法の処理は簡単です。value が limit 以上になった時点で、for ループから break で脱出するだけです。まだ評価値が求まっていない場合、limit は 1 手前 (後手番) の局面の評価値ですから MAX_VAL がセットされています。MAX_VAL より大きな評価値はないので、枝刈りが実行されることはありません。後手の場合は、逆に vlaue が limit 以下になった時点で、枝刈りを行えばいいわけです。
あとは、関数 play() を修正します。
リスト : ゲームの実行
def play(first_depth, second_depth, verbos = True):
global count
count = 0
b = init_board()
fval, sval = 0, 0
if verbos: print_board(b, fval, sval)
prev = 0
move = 1
while True:
if move % 2 != 0:
# 先手
_, m = move_first(first_depth, b, prev, fval, sval, MAX_VAL)
num = b[prev][m]
fval += num
b[prev][m] = NON_VAL
if verbos: print(f'\n{move}: 先手 ({prev}, {m}) の {num} をゲット\n')
if gameover(b, prev, m): break
else:
# 後手
_, m = move_second(second_depth, b, prev, fval, sval, MIN_VAL)
num = b[m][prev]
sval += num
b[m][prev] = NON_VAL
if verbos: print(f'\n{move}: 後手 ({m}, {prev}) の {num} をゲット\n')
if gameover(b, m, prev): break
if verbos: print_board(b, fval, sval)
prev = m
move += 1
#
if verbos:
print('Game Over')
print_board(b, fval, sval)
print(count)
if fval > sval:
print('先手の勝ちです')
elif fval < sval:
print('後手の勝ちです')
else:
print('引き分けです')
return fval - sval, count
注意する個所は、move_first() を呼び出すとき、引数 limit には MAX_VAL をセットし、move_second() を呼び出すときは MIN_VAL をセットするところだけです。プログラムの主な修正はこれだけです。
それでは、実行結果を示しましょう。前回と同じテストプログラムを使用します。結果は次のようになりました。
表 : 勝敗と評価回数
先 手
: 2 : 3 : 4 : 5
------+-----------+-----------+-----------+-----------
2 : 63, 33, 2 : 84, 16, 0 : 91, 8, 1 : 90, 10, 0
: 1009 : 3420 : 17829 : 101983
: 586 : 1383 : 4336 : 15598
:
後 3 : 45, 55, 0 : 73, 25, 2 : 78, 21, 1 : 77, 22, 1
: 3512 : 6201 : 21278 : 109437
: 1496 : 2503 : 5732 : 17976
:
4 : 33, 67, 0 : 49, 49, 2 : 70, 29, 1 : 79, 20, 1
手 : 17373 : 20281 : 34851 : 122856
: 4367 : 5485 : 8539 : 20464
:
5 : 31, 68, 1 : 56, 43, 1 : 61, 37, 2 : 66, 32, 2
: 96798 : 99393 : 114155 : 201120
: 15648 : 16691 : 20115 : 31431
上段 : 先手勝, 後手勝, 引き分け
中段 : 平均評価回数 (ミニマックス法)
下段 : 平均評価回数 (アルファベータ法)
結果を見ればおわかりのように、ゲーム MiniMax ではアルファベータ法の効果が極めて高いですね。ご参考までにレベル 6 - 8 の対戦結果を示します。
>>>> test1(6, 9) ---- 6 6 ---- 先手 72 勝, 後手 26 勝, 2 分け 平均評価回数 118035 ---- 6 7 ---- 先手 66 勝, 後手 33 勝, 1 分け 平均評価回数 262571 ---- 6 8 ---- 先手 64 勝, 後手 33 勝, 3 分け 平均評価回数 789782 ---- 7 6 ---- 先手 70 勝, 後手 24 勝, 6 分け 平均評価回数 264260 ---- 7 7 ---- 先手 72 勝, 後手 26 勝, 2 分け 平均評価回数 419458 ---- 7 8 ---- 先手 62 勝, 後手 36 勝, 2 分け 平均評価回数 974394 ---- 8 6 ---- 先手 76 勝, 後手 23 勝, 1 分け 平均評価回数 900102 ---- 8 7 ---- 先手 81 勝, 後手 17 勝, 2 分け 平均評価回数 986215 ---- 8 8 ---- 先手 76 勝, 後手 22 勝, 2 分け 平均評価回数 1520480
興味のある方はいろいろ試してみてください。
#
# minimax_ab.py : 数字を取り合うゲーム (アルファベータ法)
#
# Copyright (C) 2022 Makoto Hiroi
#
import random
# 定数
SIZE = 8
NON_VAL = 999
MAX_VAL = 999
MIN_VAL = -999
WIN_FST = 500
WIN_SND = -500
# 盤面の初期化
def init_board():
def select_number():
n = random.randint(-9, 9)
if n == 0:
n = random.randint(1, 9)
return n
return [[select_number() for _ in range(SIZE)] for _ in range(SIZE)]
# 盤面の表示
def print_board(b, fval, sval):
print(f'先手 {fval} 点, 後手 {sval} 点')
for xs in b:
for x in xs:
if x == NON_VAL:
print('**', end=' ')
else:
print('{:+d}'.format(x), end=' ')
print()
# 終了判定
def gameover(board, x, y):
c1, c2 = True, True
for i in range(SIZE):
if board[x][i] != NON_VAL: c1 = False
if board[i][y] != NON_VAL: c2 = False
return c1 or c2
# 評価関数
def value_func(fval, sval, final = False):
global count
count += 1
if final:
if fval > sval:
m = WIN_FST
elif fval < sval:
m = WIN_SND
else:
m = 0
else:
m = fval - sval
return m
# 先手の指し手
def move_first(depth, board, prev, fval, sval, limit):
if depth == 0:
return value_func(fval, sval), -1
value = MIN_VAL
m = -1
for x in range(SIZE):
if board[prev][x] == NON_VAL: continue
num = board[prev][x]
board[prev][x] = NON_VAL
if gameover(board, prev, x):
v = value_func(fval, sval, True)
else:
v, _ = move_second(depth - 1, board, x, fval + num, sval, value)
board[prev][x] = num
# ミニマックス法
if v > value:
value = v
m = x
# アルファベータ法
if value >= limit: break
return value, m
# 後手の指し手
def move_second(depth, board, prev, fval, sval, limit):
if depth == 0:
return value_func(fval, sval), -1
value = MAX_VAL
m = -1
for x in range(SIZE):
if board[x][prev] == NON_VAL: continue
num = board[x][prev]
board[x][prev] = NON_VAL
if gameover(board, x, prev):
v = value_func(fval, sval, True)
else:
v, _ = move_first(depth - 1, board, x, fval, sval + num, value)
board[x][prev] = num
# ミニマックス法
if v < value:
value = v
m = x
# アルファベータ法
if value <= limit: break
return value, m
# ゲームの実行
def play(first_depth, second_depth, verbos = True):
global count
count = 0
b = init_board()
fval, sval = 0, 0
if verbos: print_board(b, fval, sval)
prev = 0
move = 1
while True:
if move % 2 != 0:
# 先手
_, m = move_first(first_depth, b, prev, fval, sval, MAX_VAL)
num = b[prev][m]
fval += num
b[prev][m] = NON_VAL
if verbos: print(f'\n{move}: 先手 ({prev}, {m}) の {num} をゲット\n')
if gameover(b, prev, m): break
else:
# 後手
_, m = move_second(second_depth, b, prev, fval, sval, MIN_VAL)
num = b[m][prev]
sval += num
b[m][prev] = NON_VAL
if verbos: print(f'\n{move}: 後手 ({m}, {prev}) の {num} をゲット\n')
if gameover(b, m, prev): break
if verbos: print_board(b, fval, sval)
prev = m
move += 1
#
if verbos:
print('Game Over')
print_board(b, fval, sval)
print(count)
if fval > sval:
print('先手の勝ちです')
elif fval < sval:
print('後手の勝ちです')
else:
print('引き分けです')
return fval - sval, count
def test(n, fd, sd):
fwin = swin = draw = 0
cnt = 0
for _ in range(n):
v, c = play(fd, sd, False)
if v > 0: fwin += 1
elif v < 0: swin += 1
else: draw += 1
cnt += c
print(f'先手 {fwin} 勝, 後手 {swin} 勝, {draw} 分け')
print(f'平均評価回数 {cnt // n}')
def test1(s, e):
random.seed(0)
for x in range(s, e):
for y in range(s, e):
print('----', x, y, '----')
test(100, x, y)