ミニマックス法の続きです。今回はミニマックス法 (アルファベータ法) の改良方法について取り上げます。題材とするゲームは前回と同じく「ミニミニリバーシ」です。なお、このドキュメントは拙作のページ Algorithms with Python ネガアルファ法とネガスカウト法 と、題材となるゲームとプログラミング言語が異なるだけで、内容はほとんど同じです。あしからずご了承くださいませ。
ミニマックス法の場合、先手は最も大きな評価値の手を選び、後手は最も小さな評価値の手を選びます。ここで後手番のときに評価値の符号を反転すると、先手と同様に後手でも最大な評価値の手を選べばよいことになります。つまり、手番を変えて思考ルーチンを呼び出すときは、その返り値 (評価値) にマイナス符号をつけて符号を反転させるわけです。この方法を「ネガマックス法 (nega-max method) 」といいます。
ネガマックス法は、先手番でも後手番でも評価値が最大となる指し手を選ぶようになるため、プログラムはミニマックス法よりも簡単になります。なお、ネガマックス法の動作はミニマックス法とまったく同じです。
プログラムは次のようになります。
リスト : ネガマックス法
(define (nega-max turn ls pass)
(if (null? ls)
(values (if (eq? turn 'B) (get-value) (- (get-value)))
'())
(let loop ((xs ls) (move #f) (value MIN-VALUE))
(if (null? xs)
(if (not move)
; パス
(if pass
; 白黒ともにパス
(values (if (eq? turn 'B) (get-value) (- (get-value)))
(list 'pass))
; 手番を移す
(receive (v m) (nega-max (change-turn turn) ls #t)
(values (- v) (cons 'pass m))))
; 評価値と指し手を返す
(values value move))
(let* ((v #f)
(m #f)
(x (car xs))
(r (get-reverse-stone x turn)))
(when (pair? r)
(reverse-stone r turn)
(put-piece! x turn)
; 手番を移す
(set!-values (v m)
(nega-max (change-turn turn) (remove-item x ls) #f))
(set! v (- v))
; 元に戻す
(reverse-stone r (change-turn turn))
(del-piece! x))
; ミニマックス法
(if (and v (> v value))
(loop (cdr xs) (cons x m) v)
(loop (cdr xs) move value)))))))
前回のミニマックス法は関数 think-black と think-white の相互再帰になりましたが、ネガマックス法は関数 nega-max の再帰呼び出しだけでプログラムすることができます。引数 turn は手番を表します。先手をシンボル B で、後手をシンボル W で表します。
関数 get-value で評価値を求めるとき、手番が後手であれば評価値の符号を反転します。手番を変える場合、nega-max を再帰呼び出しして、返り値 (評価値) v の符号を反転します。ネガマックス法における指し手の選択処理も簡単です。v が value よりも大きいときに、その指し手を選ぶだけです。このようにプログラムを簡単に記述できるのがネガマックス法の長所です。
次はネガマックス法に対応したアルファベータ法のプログラムを説明します。これを「ネガアルファ法 (nega-α method) 」と呼びます。次のリストを見てください。
リスト : ネガアルファ法
(define (nega-alpha turn ls pass limit)
(if (null? ls)
(values (if (eq? turn 'B) (get-value) (- (get-value)))
'())
(let loop ((xs ls) (move #f) (value MIN-VALUE))
(if (null? xs)
(if (not move)
; パス
(if pass
; 白黒ともにパス
(values (if (eq? turn 'B) (get-value) (- (get-value)))
(list 'pass))
; 手番を移す
(receive (v m)
(nega-alpha (change-turn turn) ls #t (- value))
(values (- v) (cons 'pass m))))
; 評価値と指し手を返す
(values value move))
(let* ((v #f)
(m #f)
(x (car xs))
(r (get-reverse-stone x turn)))
(when (pair? r)
(reverse-stone r turn)
(put-piece! x turn)
; 手番を移す
(set!-values (v m)
(nega-alpha (change-turn turn)
(remove-item x ls)
#f
(- value)))
(set! v (- v))
; 元に戻す
(reverse-stone r (change-turn turn))
(del-piece! x))
; ミニマックス法
(if (and v (> v value))
; αβ法
(if (>= v limit)
(values v (cons x m))
(loop (cdr xs) (cons x m) v))
(loop (cdr xs) move value)))))))
引数 limit が基準値になります。ネガアルファ法の場合、手番を変えるときは基準値の符号を反転して渡すことに注意してください。前回のアルファベータ法の場合、基準値として value を渡しましたが、ネガアルファ法の場合は (- value) を渡します。そうすると、ネガアルファ法による枝刈りの条件は (>= v limit) で表すことができます。このように、ネガアルファ法のプログラムもとても簡単になります。
ところで、今までのアルファベータ法のプログラムでは、次の局面の基準値となる変数 value の値を MIN-VALUE または MAX-VALUE で初期化しているため、最初に探索する局面 (最も左側の枝の局面) の評価値を求めないと、アルファベータ法による枝刈りは発生しません。α値とβ値を (α, β) で表すと、新しい局面は (-∞, β) または (α, ∞) の幅で局面を探索することになります。たとえば、左側の枝から順番に探索していく場合、最も左側の枝の評価値 value が求まると、それ以降の枝は (value, β) または (α, value) の幅で局面を探索します。
これに対し、一つ前の局面で求まったα値とβ値を使っても、アルファベータ法を動作させることができます。つまり、新しい局面でも (α, β) の幅でゲーム木を探索してもいいのです。(-∞, β) または (α, ∞) で探索を始めるよりも (α, β) の方が幅が狭くなるので、枝刈り (αカット、βカット) の回数が多くなることが期待できます。
これで正しく動作することを、前回示したアルファベータ法の図を使って確かめてみましょう。アルファベータ法の図を再掲します。
Ｒ 先手の局面
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
Ａ(3) Ｂ(2) 後手の局面
／ ＼ ／ ×
／ ＼ ／ ×
Ｃ(3) Ｄ(4) Ｅ(2) Ｆ(5) 先手の局面
／ ＼ ／ × ／ ＼ ／ ＼
Ｇ Ｈ Ｉ Ｊ Ｋ Ｌ Ｍ Ｎ 後手の局面
１ ３ ４ ２ ２ １ ３ ５ 評価値
× × ×
図 : アルファベータ法
局面 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, ∞)
図 : ベータカット
局面 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 を選択する)
図 : アルファカット
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 を使って、アルファベータ法よりも効率よくゲーム木を探索することができます。
それではプログラムを作りましょう。次のリストを見てください。
リスト : ネガアルファ法の改良 (fail soft 対応版)
(define (nega-alpha2 turn ls pass alpha beta)
(if (null? ls)
(values (if (eq? turn 'B) (get-value) (- (get-value)))
'())
(let loop ((xs ls) (move #f) (value MIN-VALUE))
(if (null? xs)
(if (not move)
; パス
(if pass
; 白黒ともにパス
(values (if (eq? turn 'B) (get-value) (- (get-value)))
(list 'pass))
; 手番を移す
(receive (v m)
(nega-alpha2 (change-turn turn) ls #t (- beta) (- alpha))
(values (- v) (cons 'pass m))))
; 評価値と指し手を返す
(values value move))
(let* ((v #f)
(m #f)
(x (car xs))
(r (get-reverse-stone x turn)))
(when (pair? r)
(reverse-stone r turn)
(put-piece! x turn)
; 手番を移す
(set!-values (v m)
(nega-alpha2 (change-turn turn)
(remove-item x ls)
#f
(- beta)
(- (max alpha value))))
(set! v (- v))
; 元に戻す
(reverse-stone r (change-turn turn))
(del-piece! x))
; ミニマックス法
(if (and v (> v value))
; αβ法
(if (>= v beta)
(values v (cons x m))
(loop (cdr xs) (cons x m) v))
(loop (cdr xs) move value)))))))
引数 alpha がα値、beta がβ値です。value は MIN-VALUE で初期化します。これで alpha よりも小さな評価値の局面しか見つからない場合でも、value にはその中の最大値がセットされます。評価値 v が beta 以上になったら枝刈りを行うところは今までと同じです。
ネガアルファ法を使っているので、手番を変えて nega-max を再帰呼び出しするときは符号を反転するとともに、α値とβ値を逆にして渡すことと、alpha と value の大きいほうを関数 max で選んで渡すことに注意してください。
それでは、実行結果を示しましょう。ゲームの結果は、当然ですがアルファベータ法とネガアルファ法改良版 (fail soft 対応) で変わりはありません。改良版の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。改良方法が有効に機能すれば、アルファベータ法よりも局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数
| W B | W B
初期値 | B W | W B
---------+-------+-------
minimax : 60060 : 67116
αβ法 : 10016 : 13590
順序変更 : 2387 : 4832
failsoft : 718 : 1059
fail soft 対応版の評価回数は大幅に減少しています。改良の効果はとても大きいですね。ゲーム木を探索する場合、(α, β) の範囲を狭める方法は有効であることがわかります。
;
; rev16.scm : 4 * 4 リバーシ
;
; Copyright (C) 2010 Makoto Hiroi
;
(use srfi-1)
; 定数
(define MIN-VALUE -50)
(define MAX-VALUE 50)
; 方向
(define *direction* '(1 -1 6 -6 7 -7 5 -5))
; 初期値
(define *init-board*
'(O O O O O O
O S S S S O
O S W B S O
O S B W S O
O S S S S O
O O O O O O))
; 盤面
(define *board* (list->vector *init-board*))
; 石の個数
(define *black* 2)
(define *white* 2)
; 評価回数
(define *count* 0)
; アクセス関数
(define (get-piece x) (vector-ref *board* x))
(define (put-piece! x p)
(if (eq? p 'B) (inc! *black*) (inc! *white*))
(vector-set! *board* x p))
(define (del-piece! x)
(if (eq? (get-piece x) 'B) (dec! *black*) (dec! *white*))
(vector-set! *board* x 'S))
; 反転できる石に対して畳み込みを行う
(define (fold-direction func x p1 a dir)
(let loop ((x (+ x dir)) (b a))
(let ((p (get-piece x)))
(cond ((or (eq? p 'S)
(eq? p 'O))
a) ; 反転できず
((eq? p p1) b) ; 反転した
(else
(loop (+ x dir) (func x b)))))))
; 反転する石を求める
(define (get-reverse-stone x p)
(fold (lambda (dir a)
(fold-direction cons x p a dir))
'()
*direction*))
; 要素の削除
(define (remove-item x ls)
(remove (lambda (y) (eqv? x y)) ls))
; 評価値
(define (get-value)
(inc! *count*)
(- *black* *white*))
; 石を反転する
(define (reverse-stone ls p)
(for-each (lambda (x) (put-piece! x p)) ls)
(if (eq? p 'B)
(dec! *white* (length ls))
(dec! *black* (length ls))))
; 手番の交代
(define (change-turn turn)
(if (eq? turn 'B) 'W 'B))
; ネガマックス法
(define (nega-max turn ls pass)
(if (null? ls)
(values (if (eq? turn 'B) (get-value) (- (get-value)))
'())
(let loop ((xs ls) (move #f) (value MIN-VALUE))
(if (null? xs)
(if (not move)
; パス
(if pass
; 白黒ともにパス
(values (if (eq? turn 'B) (get-value) (- (get-value)))
(list 'pass))
; 手番を移す
(receive (v m) (nega-max (change-turn turn) ls #t)
(values (- v) (cons 'pass m))))
; 評価値と指し手を返す
(values value move))
(let* ((v #f)
(m #f)
(x (car xs))
(r (get-reverse-stone x turn)))
(when (pair? r)
(reverse-stone r turn)
(put-piece! x turn)
; 手番を移す
(set!-values (v m)
(nega-max (change-turn turn) (remove-item x ls) #f))
(set! v (- v))
; 元に戻す
(reverse-stone r (change-turn turn))
(del-piece! x))
; ミニマックス法
(if (and v (> v value))
(loop (cdr xs) (cons x m) v)
(loop (cdr xs) move value)))))))
; ネガアルファ法
(define (nega-alpha turn ls pass limit)
(if (null? ls)
(values (if (eq? turn 'B) (get-value) (- (get-value)))
'())
(let loop ((xs ls) (move #f) (value MIN-VALUE))
(if (null? xs)
(if (not move)
; パス
(if pass
; 白黒ともにパス
(values (if (eq? turn 'B) (get-value) (- (get-value)))
(list 'pass))
; 手番を移す
(receive (v m)
(nega-alpha (change-turn turn) ls #t (- value))
(values (- v) (cons 'pass m))))
; 評価値と指し手を返す
(values value move))
(let* ((v #f)
(m #f)
(x (car xs))
(r (get-reverse-stone x turn)))
(when (pair? r)
(reverse-stone r turn)
(put-piece! x turn)
; 手番を移す
(set!-values (v m)
(nega-alpha (change-turn turn)
(remove-item x ls)
#f
(- value)))
(set! v (- v))
; 元に戻す
(reverse-stone r (change-turn turn))
(del-piece! x))
; ミニマックス法
(if (and v (> v value))
; αβ法
(if (>= v limit)
(values v (cons x m))
(loop (cdr xs) (cons x m) v))
(loop (cdr xs) move value)))))))
; ネガアルファ法改良版 (fail-soft 対応)
(define (nega-alpha2 turn ls pass alpha beta)
(if (null? ls)
(values (if (eq? turn 'B) (get-value) (- (get-value)))
'())
(let loop ((xs ls) (move #f) (value MIN-VALUE))
(if (null? xs)
(if (not move)
; パス
(if pass
; 白黒ともにパス
(values (if (eq? turn 'B) (get-value) (- (get-value)))
(list 'pass))
; 手番を移す
(receive (v m)
(nega-alpha2 (change-turn turn) ls #t (- beta) (- alpha))
(values (- v) (cons 'pass m))))
; 評価値と指し手を返す
(values value move))
(let* ((v #f)
(m #f)
(x (car xs))
(r (get-reverse-stone x turn)))
(when (pair? r)
(reverse-stone r turn)
(put-piece! x turn)
; 手番を移す
(set!-values (v m)
(nega-alpha2 (change-turn turn)
(remove-item x ls)
#f
(- beta)
(- (max alpha value))))
(set! v (- v))
; 元に戻す
(reverse-stone r (change-turn turn))
(del-piece! x))
; ミニマックス法
(if (and v (> v value))
; αβ法
(if (>= v beta)
(values v (cons x m))
(loop (cdr xs) (cons x m) v))
(loop (cdr xs) move value)))))))
; 盤面の表示
(define (print-board)
(let ((i 0))
(dotimes (x (vector-length *board*) (newline))
(when (not (eq? (get-piece x) 'O))
(format #t "~S " (get-piece x))
(inc! i)
(if (= i 4)
(begin (newline) (set! i 0)))))))
; 手順の表示
(define (print-move ls)
(let ((turn 'B))
(dolist (x ls)
(cond ((eq? x 'pass)
(format #t "~S : PASS!!~%" turn))
(else
(format #t "~S : ~D~%" turn x)
(reverse-stone (get-reverse-stone x turn) turn)
(put-piece! x turn)
(format #t "B = ~D : W = ~D~%" *black* *white*)
(print-board)))
(set! turn (if (eq? turn 'B) 'W 'B)))))
; 実行
(receive (v m)
(nega-alpha2 'B
'(7 10 25 28 8 9 13 16 19 22 26 27)
#f
MIN-VALUE
MAX-VALUE)
(print v)
(print m)
(print-move m)
(print *count*))