今回はゲーム 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)