前回はミニマックス法について説明しました。今回はアルファベータ法について説明します。
ミニマックス法の説明では、木を全て探索するので 8 回評価値を計算しましたが、アルファベータ法を使うと木を枝刈りすることができます。次の図を見てください。
Ｒ 先手の局面
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
Ａ(3) Ｂ(2) 後手の局面
／ ＼ ／ ×
／ ＼ ／ ×
Ｃ(3) Ｄ(4) Ｅ(2) Ｆ(5) 先手の局面
／ ＼ ／ × ／ ＼ ／ ＼
Ｇ Ｈ Ｉ Ｊ Ｋ Ｌ Ｍ Ｎ 後手の局面
１ ３ ４ ２ ２ １ ３ ５ 評価値
× × ×
図 3 : アルファベータ法
アルファベータ法を使うと、×で示した箇所で枝刈りが行われます。評価値の計算が 5 回で済んでいますね。もちろん、結果 (選択した指し手) はミニマックス法と同じです。それでは、なぜ枝刈りが可能なのか説明しましょう。
基本はミニマックス法と同じです。今、C の評価値 3 が決定し、D の評価値を決めるため I の評価値を計算します。その結果、評価値は 4 になりました。この時点で、J の評価値は計算しなくてもいいのです。次の図を見てください。
後手の局面 Ａ
／ ＼
／ ＼
先手の局面 Ｃ(β=3) Ｄ(4)
／ ＼ ／ ×
後手の局面 Ｇ Ｈ Ｉ Ｊ
評価値 １ ３ ４
(1) C の評価値が 3 なので A の評価値は 3 以下になる
(2) I の評価値が 4 なので D の評価値は 4 以上になる
(3) 4 > 3 (β値) なので D は選択されない
(4) J を枝刈りする
図 4 : ベータカット
今、後手が指し手を選ぶところなので、小さな評価値の方を選びます。C の評価値は 3 なので、ここで選択される指し手の評価値は 3 より大きくならないことがわかります。なぜなら、局面 D の評価値が 3 より大きいのであれば、C が選択されることになるからです。
ところが、D の評価値は I の評価値が 4 になった時点で、この値よりも小さな値にはなりません。I と J を選ぶのは先手なので、大きな評価値の指し手を選ぶからです。したがって、J が 3 より小さな値になったとしても、 D の評価値は 4 になります。また、J の評価値が I より大きくなったとしても、C の評価値 3 より大きな値になるので、けっきょく C が選択されることになります。指し手を決めるために、J の評価値を調べる必要はないのです。
このように、J の枝を枝刈りすることができます。このようなタイプの枝刈りをベータカット (β cut) といい、そのとき基準になる値をベータ値といいます。
これで、局面 A の評価値は 3 に決まりました。次に、B の評価値を求めます。ここでも局面 A の評価値を基準にした枝刈りが可能です。次の図を見てください。
Ｒ
／ ＼
／ ＼
後手の局面 Ａ(α=3) Ｂ
／ ×
／ ×
先手の局面 Ｅ(2) Ｆ
／ ＼
後手の局面 Ｋ Ｌ
評価値 ２ １
(1) A の評価値が 3 なので R の評価値は 3 以上になる
(2) E の評価値が 2 なので B の評価値は 2 以下になる
(3) 2 < 3 (α値) なので B は選択されない
(4) F を枝刈りする
図 5 : アルファカット
今、先手が指し手を選ぶところなので、大きな評価値の方を選びます。A の評価値は 3 なので、B が選ばれるには 3 より大きい値でなければいけません。まず最初に E の評価値を求めます。これは、K と L の評価値を求めて大きい方を選びます。ここで、E の評価値が 2 に決まると、F の評価値を求める必要はなくなります。
E と F は後手が指し手を選ぶところなので、評価値の小さな指し手を選びます。そして、それが局面 B の評価値になります。したがって、局面 B の評価値は 2 より小さな値にしかなりません。ところが、A と B は先手が指し手を選択するので、大きな評価値の指し手を選びます。A の評価値は 3 で、B の評価値は 2 以下の値にしかならないので、F の評価値を調べなくても A を選ぶことができるのです。
このように、F の枝を枝刈りすることができます。このようなタイプの枝刈りをアルファカット (α cut) といい、そのとき基準になる値をアルファ値といいます。この「アルファベータ法」がうまく働くと、局面を半分以上評価しないで済ますことができるようです。
それではアルファベータ法のプログラムを作りましょう。ポイントは基準値 (α値、β値) の管理です。プログラムは次のようになります。
リスト : 先手の指し手 (アルファベータ法)
def move_first(depth, board, limit):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in range(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = move_first(depth, b, limit)
else:
# 後手番
v, _ = move_second(depth - 1, b, value)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# αβ法
if value >= limit: break
return value, move
引数 limit がアルファベータ法で使用する基準値です。この値は 1 手前の局面の評価値です。変数 value は評価値を格納します。これはミニマックス法と同じです。この値が次の局面 (後手番) での基準値となります。
石を動かした結果が KALAH であれば move_first() を再帰呼び出しします。このとき、depth だけではなく、limit もそのまま渡します。アルファベータ法では相手番の評価値が基準点になるので、この再帰処理では基準点として value を渡すのではなく、limit をそのまま渡すことに注意してください。
KALAH の処理を簡略化する場合は次のようになります。
リスト : KALAH 簡易版
if result == KALAH:
# 手番は同じで 1 手だけ探索
v, m = move_first1(1, b, MAX_VALUE)
for x in m:
b.move_stone(FIRST_KALAH, x)
# 後手番
v, _ = move_second1(depth - 1, b, value)
自分の手番で 1 手だけ探索するので、move_first1() の引数 limit には MAX_VALUE を渡します。
アルファベータ法の処理は簡単です。ミニマックス法で指し手を選択したあと、value が limit 以上の値になった時点で、for ループから脱出するだけです。value が limit よりも大きな値になった時点、つまり value > limit で枝刈りしても正常に動作しますが、value >= limit としたほうが効率よく枝刈りできるようです。
まだ評価値が求まっていない場合、limit は 1 手前 (後手番) の局面の評価値ですから MAX_VALUE がセットされています。MAX_VALUE より大きな評価値はないので、アルファベータ法により枝刈りが実行されることはありません。
後手の指し手を選ぶ関数 move_second() は次のようになります。
リスト : 後手の指し手 (アルファベータ法)
def move_second(depth, board, limit):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in range(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = move_second(depth, b, limit)
else:
# 先手番
v, _ = move_first(depth - 1, b, value)
# ミニマックス : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
# αβ法
if value <= limit: break
return value, move
先手 (move_first) とは逆に、後手 (move_second) の場合は value を MAX_VALUE で初期化します。これが評価値の中で最大の値となります。後手の場合、ミニマックス法では小さな値を選ぶので、最初に求めた評価値が無条件に選択されます。アルファベータ法の場合も先手とは逆に、vlaue が limit 以下の値になった時点で枝刈りを行えばいいわけです。
あとは、関数 play() を修正します。プログラムは次のようになります。
リスト : ゲームの実行
def play(first_depth, second_depth, think1 = move_first, think2 = move_second):
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(first_depth, board, MAX_VALUE)
else:
value, move = think2(second_depth, board, MIN_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
注意する個所は、先手の思考ルーチン think1() を呼び出すとき、引数 limit には MAX_VALUE をセットし、後手の思考ルーチン think2() を呼び出すときは MIN_VALUE をセットするところだけです。プログラムの主な修正はこれだけです。
表 : 局面の評価回数
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 41, 31 : 43, 17 : 26, 37 : 39, 33
: 11775 : 90968 : 318340 : 1221294
: 6207 : 40657 : 85880 : 226145
:
3 : 39, 23 : 40, 32 : 53, 19 : 48, 24
後 : 4383 : 41159 : 654559 : 588627
: 1757 : 11320 : 119750 : 65362
:
手 4 : 36, 36 : 43, 29 : 34, 38 : 44, 28
: 160765 : 131496 : 510241 : 1734092
: 30242 : 31230 : 111266 : 238004
:
5 : 23, 49 : 26, 39 : 43, 29 : 35, 37
: 3648321 : 1580529 : 2488362 : 4806261
: 504203 : 221814 : 505170 : 815589
上段 : 先手の石数, 後手の石数 中段 : ミニマックス法 下段 : アルファベータ法 先手 : move_first() 後手 : move_second() 勝敗 : 先手 10 勝, 後手 5 勝, 1 分
それでは、実行結果を示しましょう。ゲームの結果は、当然ですがミニマックス法とアルファベータ法で変わりはありません。アルファベータ法の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。アルファベータ法が有効に機能すれば、ミニマックス法よりも局面の評価回数は少なくなるはずです。結果は上表のようになりました。
結果を見ればおわかりのように、アルファベータ法の比較回数はミニマックス法の 1/2 から 1/9 程度になりました。カラハの場合、アルファベータ法の効果は極めて高いですね。それだけ実行時間も速くなります。
次は KALAH 簡易版の結果を示します。
表 : 局面の評価回数 (KALAH 簡易版)
先手
: 2 : 3 : 4 : 5
------------+---------+---------+---------+---------
2 : 37, 23 : 37, 22 : 41, 31 : 39, 33
: 2625 : 9584 : 28001 : 134349
: 1500 : 4474 : 12138 : 32710
3 : 35, 37 : 49, 23 : 43, 21 : 37, 25
後 : 2681 : 19940 : 19330 : 177671
: 1726 : 11476 : 7779 : 54995
手 4 : 26, 46 : 35, 37 : 31, 41 : 49, 23
: 47871 : 58461 : 56932 : 144941
: 15592 : 23685 : 21359 : 53430
5 : 45, 27 : 37, 27 : 28, 44 : 24, 48
: 121195 : 75151 : 146399 : 437150
: 39890 : 25602 : 50537 : 145099
上段 : 先手の石数, 後手の石数 中段 : ミニマックス法 下段 : アルファベータ法 先手 : move_first1() 後手 : move_second1() 勝敗 : 先手 10 勝, 後手 6 勝
KALAH 簡易版でもアルファベータ法の効果により局面の評価回数は少なくなりました。興味のある方はいろいろ試してみてください。
思考ゲームの基本である「ミニマックス法」と「アルファベータ法」を説明しました。今回説明したのは単純なアルファベータ法ですが、簡単な思考ゲームであれば、これだけでも十分な効果を発揮します。
今まで M.Hiroi が作成した思考ゲーム (Tcl/Tk GUI Programming : Mini Games 2 [*1]) は、今回説明したミニマックス法とアルファベータ法が基本となっています。このほかにも、探索効率を上げるためのアルゴリズムが数多く提案されています。興味のある方は参考文献『bit別冊 ゲームプログラミング』を読んでみてください。
今回説明したように、ミニマックス法とアルファベータ法はけっして難しいアルゴリズムではありません。実は、思考ゲームのプログラミングで一番大変なのが「評価関数」の作成です。これはプログラムの作成が難しいというよりも、局面の評価方法を考えることが難しいのです。チェスや将棋に比べて囲碁のプログラムは弱いといわれていますが、これは精度の高い評価関数を作るのが非常に難しいからです。
思考ルーチンに興味を持たれた方は、まずリバーシから作ってみるといいでしょう。リバーシの評価関数はチェスや将棋に比べると比較的簡単なほうですが、それでも強い思考ルーチンを作るのは大変です。いろいろ試してみてください。リバーシには変形バージョンもありますので、そちらを作ってみるのも面白いと思います。
#
# board.py : カラハ 盤面の定義
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
# 定数
SIZE = 14 # 盤面の大きさ
FIRST_KALAH = 6 # 先手、先手のカラハの位置
SECOND_KALAH = 13 # 後手、後手のカラハの位置
STONE = 72 # 石の個数
EVEN = STONE // 2
MAX_VALUE = 100 # 評価値の最大値
MIN_VALUE = -100 # 評価地の最小値
FIRST_WIN = 99 # 先手勝ち
SECOND_WIN = -99 # 後手勝ち
NORMAL = 0 # 通常の穴に入った場合
KALAH = 1 # KALAH に入った場合
GAMEOVER = 2 # ゲーム終了
# 評価関数の呼び出し回数
count = 0
# 盤面
class Board:
def __init__(self, b):
self.board = b[:]
def __getitem__(self, x):
return self.board[x]
def copy(self):
return Board(self.board)
# 石を配る
def distribute(self, turn, pos):
num = self.board[pos]
self.board[pos] = 0
while num > 0:
pos += 1
if pos == SIZE: pos = 0
if (turn == FIRST_KALAH and pos == SECOND_KALAH) or \
(turn == SECOND_KALAH and pos == FIRST_KALAH): continue
self.board[pos] += 1
num -= 1
return pos
# 両取りのチェック
def check_capture(self, turn, pos):
if (turn == FIRST_KALAH and 0 <= pos <= 5) or \
(turn == SECOND_KALAH and 7 <= pos <= 12):
if self.board[pos] == 1 and self.board[12 - pos] > 0:
# 両取りができる
num = self.board[12 - pos] + 1
self.board[turn] += num
self.board[pos] = 0
self.board[12 - pos] = 0
return True
return False
# 穴にある石を数える
def count_stone(self, turn):
n = 0
for x in range(turn - 6, turn): n += self.board[x]
return n
# 石をカラハに入れる
def put_stone_into_kalah(self, turn):
n = 0
for x in range(turn - 6, turn):
n += self.board[x]
self.board[x] = 0
self.board[turn] += n
# 終了チェック
def check_gameover(self):
if self.count_stone(FIRST_KALAH) == 0:
self.put_stone_into_kalah(SECOND_KALAH)
return True
elif self.count_stone(SECOND_KALAH) == 0:
self.put_stone_into_kalah(FIRST_KALAH)
return True
elif self.board[FIRST_KALAH] > EVEN or \
self.board[SECOND_KALAH] > EVEN:
return True
return False
# 石を動かす
def move_stone(self, turn, pos):
pos = self.distribute(turn, pos)
if pos == turn: return KALAH
self.check_capture(turn, pos)
return NORMAL
# 評価関数
def value_func(self):
global count
count += 1
n1 = self.board[FIRST_KALAH]
n2 = self.board[SECOND_KALAH]
if n1 > EVEN: return FIRST_WIN
if n2 > EVEN: return SECOND_WIN
return n1 - n2
# 盤面の表示
def print_board(self):
print(' ', end=' ')
for x in range(12, 6, -1):
print('{:2d}'.format(self.board[x]), end=' ')
print()
print('{:2d}'.format(self.board[13]), end=' ')
print(' ' * 6, end=' ')
print('{:2d}'.format(self.board[6]))
print(' ', end=' ')
for x in range(0, 6):
print('{:2d}'.format(self.board[x]), end=' ')
print()
# debug 用
def print_count(): print(count)
def init_count():
global count
count = 0
#
# kalah.py : カラハ (ミニマックス法)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from board import *
# 思考ルーチン
# 先手の指し手
def move_first(depth, board):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in range(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = move_first(depth, b)
else:
# 後手番
v, _ = move_second(depth - 1, b)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
return value, move
def move_first1(depth, board):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in range(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま (1 手だけ探索)
v, m = move_first1(1, b)
for x in m:
b.move_stone(FIRST_KALAH, x)
# 後手番
v, _ = move_second1(depth - 1, b)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
return value, move
# 後手の指し手
def move_second(depth, board):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in range(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = move_second(depth, b)
else:
# 先手番
v, _ = move_first(depth - 1, b)
# ミニマックス法 : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
return value, move
def move_second1(depth, board):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in range(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま (1 手だけ探索)
v, m = move_second1(1, b)
for x in m:
b.move_stone(SECOND_KALAH, x)
v, _ = move_first1(depth - 1, b)
# ミニマックス法 : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
return value, move
# ゲームの実行
def play(first_depth, second_depth, think1 = move_first, think2 = move_second):
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(first_depth, board)
else:
value, move = think2(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
#
# kalah1.py : カラハ (アルファベータ法)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from board import *
# 思考ルーチン
# 先手の指し手
def move_first(depth, board, limit):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in range(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = move_first(depth, b, limit)
else:
# 後手番
v, _ = move_second(depth - 1, b, value)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# αβ法
if value >= limit: break
return value, move
def move_first1(depth, board, limit):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in range(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じで 1 手だけ探索
v, m = move_first1(1, b, MAX_VALUE)
for x in m:
b.move_stone(FIRST_KALAH, x)
# 後手番
v, _ = move_second1(depth - 1, b, value)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# αβ法
if value >= limit: break
return value, move
# 後手の指し手
def move_second(depth, board, limit):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in range(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = move_second(depth, b, limit)
else:
# 先手番
v, _ = move_first(depth - 1, b, value)
# ミニマックス : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
# αβ法
if value <= limit: break
return value, move
def move_second1(depth, board, limit):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in range(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じで 1 手だけ探索
v, m = move_second1(1, b, MIN_VALUE)
for x in m:
b.move_stone(SECOND_KALAH, x)
# 先手番
v, _ = move_first1(depth - 1, b, value)
# ミニマックス : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
# αβ法
if value <= limit: break
return value, move
# 実行
def play(first_depth, second_depth, think1 = move_first, think2 = move_second):
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(first_depth, board, MAX_VALUE)
else:
value, move = think2(second_depth, board, MIN_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