今回はアルファベータ法の改良法である「ネガスカウト (Nega Scout) 法」について説明します。題材とするゲームはミニミニリバーシです。ただし、ミニミニリバーシはゲームの木が小さくて効果がわからないので、少しだけ盤面を大きくした変形版を考えます。なお、ネガスカウト法の説明は拙作のページ Algorithms with Python ネガアルファ法とネガスカウト法 と、題材となるゲームとプログラミング言語が異なるだけで、内容はほとんど同じです。あしからずご了承くださいませ。
ミニミニリバーシ変形版を下図に示します。
┌─┬─┐
│ │ │
┌─┼─┼─┼─┐
│ │ │ │ │
┌─┼─┼─┼─┼─┼─┐
│ │ │○│●│ │ │
├─┼─┼─┼─┼─┼─┤
│ │ │●│○│ │ │
└─┼─┼─┼─┼─┼─┘
│ │ │ │ │
└─┼─┼─┼─┘
│ │ │
└─┴─┘
図 : ミニミニリバーシ変形版
ひし形みたいな形をしていて、隅が 8 か所あるのが特徴です。この場合、すぐに隅を取ることはできないので、後手必勝ではないかもしれません。最初にネガアルファ法 fail soft 対応版で勝敗の結果を求め、それからネガスカウト法を適用してその効果を確かめてみましょう。
プログラムはミニミニリバーシの大域変数 *direction* と *init-board* を修正するだけで簡単に作成することができます。次のリストを見てください。
リスト : 大域変数の修正
; 方向
(define *direction* '(1 -1 8 -8 9 -9 7 -7))
; 初期値
(define *init-board*
'(O O O O O O O O ; 盤面の位置
O O O S S O O O ; 11 12
O O S S S S O O ; 18 19 20 21
O S S W B S S O ; 25 26 27 28 29 30
O S S B W S S O ; 33 34 35 36 37 38
O O S S S S O O ; 42 43 44 45
O O O S S O O O ; 51 52
O O O O O O O O))
盤面 (ベクタ) のサイズは 8 * 8 = 64 になります。したがって、方向を表す *direction* は、左右が n - 1, n + 1 で、上下が n - 8, n + 8 で、斜めが n - 7, n + 7, n - 9, n + 9 になります。
あとは、関数 nega-alpha を呼び出すだけです。次のリストを見てください。
リスト : 関数 nega-alpha の呼び出し
(nega-alpha 'B
'(11 12 25 30 33 38 51 52 18 21
42 45 19 20 26 29 34 37 43 44)
#f
MIN-VALUE
MAX-VALUE)
最初に 8 か所の隅を探索し、次に 4 か所ある辺を探索します。それから、残りの 8 か所を探索します。このように、探索順序を変更するだけでも、アルファベータ法の枝刈りの効率はかなり改善されます。
それでは実行結果を示します。
0
(19 34 45 21 33 26 20 29 37 12 11 44 38 30 52 51 18 25 43 42)
B : 19
B = 4 : W = 1
S S
S B S S
S S B B S S
S S B W S S
S S S S
S S
W : 34
B = 3 : W = 3
S S
S B S S
S S B B S S
S W W W S S
S S S S
S S
B : 45
B = 5 : W = 2
S S
S B S S
S S B B S S
S W W B S S
S S S B
S S
W : 21
B = 4 : W = 4
S S
S B S W
S S B W S S
S W W B S S
S S S B
S S
B : 33
B = 7 : W = 2
S S
S B S W
S S B W S S
B B B B S S
S S S B
S S
W : 26
B = 6 : W = 4
S S
S B S W
S W W W S S
B B B B S S
S S S B
S S
B : 20
B = 9 : W = 2
S S
S B B W
S W B B S S
B B B B S S
S S S B
S S
W : 29
B = 7 : W = 5
S S
S B B W
S W W W W S
B B B B S S
S S S B
S S
B : 37
B = 9 : W = 4
S S
S B B W
S W W B W S
B B B B B S
S S S B
S S
W : 12
B = 8 : W = 6
S W
S W B W
S W W B W S
B B B B B S
S S S B
S S
B : 11
B = 11 : W = 4
B W
S B B W
S W B B W S
B B B B B S
S S S B
S S
W : 44
B = 7 : W = 9
B W
S B W W
S W B W W S
B B W W B S
S S W B
S S
B : 38
B = 10 : W = 7
B W
S B B W
S W B W B S
B B W W B B
S S W B
S S
W : 30
B = 8 : W = 10
B W
S B B W
S W B W W W
B B W W W B
S S W B
S S
B : 52
B = 12 : W = 7
B W
S B B W
S W B B W W
B B W B W B
S S B B
S B
W : 51
B = 11 : W = 9
B W
S B B W
S W B B W W
B B W B W B
S S W B
W B
B : 18
B = 13 : W = 8
B W
B B B W
S B B B W W
B B W B W B
S S W B
W B
W : 25
B = 10 : W = 12
B W
B B B W
W W W W W W
B B W B W B
S S W B
W B
B : 43
B = 14 : W = 9
B W
B B B W
W W B W W W
B B B B W B
S B B B
W B
W : 42
B = 12 : W = 12
B W
B B B W
W W B W W W
B W W B W B
W B B B
W B
1690895
ミニミニリバーシ変形版の場合、両者が最善を尽くすと引き分けになりました。ちなみに、下図のように初期の配置を変更すると先手必勝になります。
┌─┬─┐
│ │ │
┌─┼─┼─┼─┐
│ │ │ │ │
┌─┼─┼─┼─┼─┼─┐
│ │ │○│●│ │ │
├─┼─┼─┼─┼─┼─┤
│ │ │○│●│ │ │
└─┼─┼─┼─┼─┼─┘
│ │ │ │ │
└─┼─┼─┼─┘
│ │ │
└─┴─┘
図 : ミニミニリバーシ変形版(2)
実行結果を示します。
10
(18 21 29 37 42 20 38 26 12 11 30 25 19 43 34 44 33 45 52 51)
B : 18
B = 4 : W = 1
S S
B S S S
S S B B S S
S S W B S S
S S S S
S S
W : 21
B = 3 : W = 3
S S
B S S W
S S B W S S
S S W B S S
S S S S
S S
B : 29
B = 5 : W = 2
S S
B S S W
S S B B B S
S S W B S S
S S S S
S S
W : 37
B = 3 : W = 5
S S
B S S W
S S B B W S
S S W W W S
S S S S
S S
B : 42
B = 5 : W = 4
S S
B S S W
S S B B W S
S S B W W S
B S S S
S S
W : 20
B = 4 : W = 6
S S
B S W W
S S B W W S
S S B W W S
B S S S
S S
B : 38
B = 7 : W = 4
S S
B S W W
S S B W W S
S S B B B B
B S S S
S S
W : 26
B = 6 : W = 6
S S
B S W W
S W W W W S
S S B B B B
B S S S
S S
B : 12
B = 9 : W = 4
S B
B S B W
S W W B W S
S S B B B B
B S S S
S S
W : 11
B = 8 : W = 6
W B
B S W W
S W W B W S
S S B B B B
B S S S
S S
B : 30
B = 11 : W = 4
W B
B S W B
S W W B B B
S S B B B B
B S S S
S S
W : 25
B = 10 : W = 6
W B
W S W B
W W W B B B
S S B B B B
B S S S
S S
B : 19
B = 13 : W = 4
W B
W B B B
W W B B B B
S S B B B B
B S S S
S S
W : 43
B = 10 : W = 8
W B
W W B B
W W W B B B
S S W B B B
B W S S
S S
B : 34
B = 13 : W = 6
W B
W W B B
W W B B B B
S B B B B B
B W S S
S S
W : 44
B = 12 : W = 8
W B
W W B B
W W B B B B
S B W B B B
B W W S
S S
B : 33
B = 15 : W = 6
W B
W B B B
W B B B B B
B B W B B B
B W W S
S S
W : 45
B = 13 : W = 9
W B
W B B B
W B W B B B
B B W W B B
B W W W
S S
B : 52
B = 18 : W = 5
W B
W B B B
W B W B B B
B B W B B B
B B B B
S B
W : 51
B = 17 : W = 7
W B
W B B B
W B W B B B
B B W B B B
B W B B
W B
898585
黒の 10 石勝ちとなりました。隅がたくさんあるので、普通のリバーシとはゲーム感覚がかなり異なると思います。興味のある方は対戦バージョンを作ってみてください。
次は 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 を適用します。高い評価値の局面から順番に探索した場合、最初の評価値を求めたあと、そのあとの局面は最初の評価値よりも大きくならないことを null window search で確認するだけですみます。このため、ネガスカウト法は move ordering と一緒に用いられることが多いようです。
ネガスカウト法のプログラムは次のようになります。
リスト : ネガスカウト法
(define (nega-scout 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-scout (change-turn turn) ls #t (- beta) (- alpha))
(values (- v) (cons 'pass m))))
; 評価値と指し手を返す
(values value move))
(let* ((v #f)
(m #f)
(a (max alpha value))
(x (car xs))
(r (get-reverse-stone x turn)))
(when (pair? r)
(reverse-stone r turn)
(put-piece! x turn)
; null window search
(set!-values (v m)
(nega-scout (change-turn turn)
(remove-item x ls)
#f
(- (+ a 1))
(- a)))
(set! v (- v))
(when (> beta v a)
; 再度探索する
(set!-values (v m)
(nega-scout (change-turn turn)
(remove-item x ls)
#f
(- beta)
(- v)))
(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)))))))
手番を変えるときに null window search を適用します。また、最初に探索する局面でも null window search を適用することにします。一般的なネガスカウト法とはちょっと違いますが、ミニミニリバーシの場合はこれでも十分に機能するようです。
手番を変える場合、最初に alpha と value を比較して大きいほうを変数 a にセットします。そして、window の幅を (-(a+1), -a) に制限して関数 nega-scout を再帰呼び出しします。これで null window search が実行されます。プログラムはネガアルファ法で実装しているので、null window search の幅 (a, a+1) は、符号を反転してα値とβ値を逆にすることに注意してください。
評価値 v が a よりも大きくて beta よりも小さい場合は、window の幅を (v, beta) に設定してネガアルファ法で再探索します。これで正しい評価値を求めることができます。あとはネガアルファ法と同じで、v が value よりも大きい場合はその局面を選択し、beta 以上の場合は枝刈りを行います。
それでは、実行結果を示しましょう。ゲームの結果は、当然ですがネガアルファ法 fail soft 対応版とネガスカウト法で変わりはありません。ただし、ネガアルファ法とネガスカウト法では求まる手順が異なるので注意してください。ネガスカウト法の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。ネガスカウト法が有効に機能すれば、ネガアルファ法 fail soft 対応版よりも局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数
| W B | W B
初期値 | B W | W B
---------+---------+---------
fail soft: 1690895 | 898585
negascout: 1309977 | 524627
評価回数はネガアルファ法 fail soft 対応版よりもネガスカウト法の方が少なくなりました。ネガスカウト法の効果はとても高いと思います。興味のある方はいろいろ試してみてください。
;
; rev24.scm : ミニミニリバーシ変形版
;
; Copyright (C) 2010 Makoto Hiroi
;
(use srfi-1)
; 定数
(define MIN-VALUE -50)
(define MAX-VALUE 50)
; 方向
(define *direction* '(1 -1 8 -8 9 -9 7 -7))
; 初期値
(define *init-board*
'(O O O O O O O O
O O O S S O O O ; 11 12
O O S S S S O O ; 18 19 20 21
O S S W B S S O ; 25 26 27 28 29 30
O S S W B S S O ; 33 34 35 36 37 38
O O S S S S O O ; 42 43 44 45
O O O S S O O O ; 51 52
O 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))
; ネガアルファ法 (fail-soft 対応)
(define (nega-alpha 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-alpha (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-alpha (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 (nega-scout 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-scout (change-turn turn) ls #t (- beta) (- alpha))
(values (- v) (cons 'pass m))))
; 評価値と指し手を返す
(values value move))
(let* ((v #f)
(m #f)
(a (max alpha value))
(x (car xs))
(r (get-reverse-stone x turn)))
(when (pair? r)
(reverse-stone r turn)
(put-piece! x turn)
; null window search
(set!-values (v m)
(nega-scout (change-turn turn)
(remove-item x ls)
#f
(- (+ a 1))
(- a)))
(set! v (- v))
(when (> beta v a)
; 再度探索する
(set!-values (v m)
(nega-scout (change-turn turn)
(remove-item x ls)
#f
(- beta)
(- v)))
(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))
(if (eq? (get-piece x) 'O)
(display " ")
(format #t "~S " (get-piece x)))
(inc! i)
(if (= i 8)
(begin (newline) (set! i 0))))))
; 手順の表示
(define (print-move ls turn)
(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-scout 'B
'(11 12 25 30 33 38 51 52 18 21 42 45
19 20 26 29 34 37 43 44)
#f
MIN-VALUE
MAX-VALUE)
(print v)
(print m)
(print-move m 'B)
(print *count*))