今回は「アルファベータ法 (αβ method)」について説明します。難しそうな名前がついていますが、アルファベータ法はミニマックス法を効率化するための枝刈りにすぎません。基本的な探索アルゴリズムを理解していれば、それほど難しい話ではありません。
このアルファベータ法がうまく機能すると、局面を半分以上評価しないで済ますことができるようです。そこで今回は簡単なゲームであるミニミニリバーシ (4 行 4 列盤) の勝敗結果 (先手必勝、後手必勝、引き分け) をミニマックス法で求め、次にアルファベータ法を適用してその効果を確かめてみることにします。
ミニミニリバーシは M.Hiroi が勝手につけた名前で、ようするに 4 行 4 列盤の小さなリバーシのことです。次の図を見てください。
┌─┬─┬─┬─┐ │ │ │ │ │ ├─┼─┼─┼─┤ │ │○│●│ │ ├─┼─┼─┼─┤ │ │●│○│ │ ├─┼─┼─┼─┤ │ │ │ │ │ └─┴─┴─┴─┘ 図 : ミニミニリバーシ
初手で黒石を置くことができる場所は 4 か所あります。黒石をどこに置いても次の手で隅を取られてしまうので、ミニミニリバーシは後手必勝だと思われます。実際にプログラムを作って確かめてみましょう。
まず最初に、盤面を表すデータ構造から定義しましょう。盤面はベクタで表します。ベクタの大きさを 16 とすると、石を反転できるか調べるときに、盤面の範囲をチェックする必要があります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。下図を見てください。
O O O O O O O : 外側 (範囲外) O S S S S O S : 空き場所 O S W B S O B : 黒石 O S B W S O W : 白石 O S S S S O O O O O O O 図 : 盤面を表すデータ構造 |
０ １ ２ ３ ４ ５
６ ７ ８ ９ 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35
図 : ベクタの添字と盤面の対応
|
盤面を表すベクタの大きさは 36 (6 行 6 列) になります。ベクタの要素はシンボル (O, S, B, W) です。盤面の位置を n とすると、左右の位置は n - 1, n + 1 で、上下の位置は n - 6, n + 6 で、斜めの位置は n - 7, n + 7, n - 5, n + 5 で求めることができます。そして、ベクタの要素が O であれば盤外であることがわかります。
次はスペシャル変数を定義します。
リスト : スペシャル変数の定義
;;; 盤面の初期値
;;; o: 壁, s: 空き場所, b: 黒石, w: 白石
(defconstant 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))
(defconstant direction '(1 -1 6 -6 7 -7 5 -5)) ; 方向
(defconstant max-value 50)
(defconstant min-value -50)
(defvar *board*) ; 盤面
(defvar *black*) ; 黒石の個数
(defvar *white*) ; 白石の個数
(defvar *count*) ; 評価回数
定数 INIT-BOARD は盤面の初期値を、DIRECTION は方向を表すリストです。MAX-VALUE と MIN-VALUE は評価値の最大値と最小値を表します。MAX-VALUE は +16 より大きな値、MIN-VALUE は -16 よりも小さな値であれば OK です。それから、盤面を *BOARD* に、黒石と白石の個数を *BLACK* と *WHITE* に格納します。*COUNT* は局面を評価した回数 (ゲーム終了となる局面の個数) を格納します。
次は盤面にアクセスする関数を定義します。
リスト : アクセス関数 (defun get-piece (x) (aref *board* x)) (defun put-piece (x p) (case p (b (incf *black*)) (w (incf *white*))) (setf (aref *board* x) p)) (defun del-piece (x) (case (get-piece x) (b (decf *black*)) (w (decf *white*))) (setf (aref *board* x) 's))
get-piece は盤面の値を求めます。put-piece は盤面に石を置きます。このとき、石の個数を +1 します。del-piece は盤面から石を取り除き、石の個数を -1 します。
次は反転する石を求める関数 get-rev-stone を作ります。
リスト : 反転する石を求める
(defun get-rev-stone-sub (n p q d &optional a)
(cond
((eq (get-piece n) p) a)
((eq (get-piece n) q)
(get-rev-stone-sub (+ n d) p q d (cons n a)))
(t nil)))
(defun get-rev-stone (n p)
(let ((q (if (eq p 'b) 'w 'b)))
(mapcan (lambda (d) (get-rev-stone-sub (+ n d) p q d))
direction)))
実際の処理は関数 get-rev-stone-sub で行います。引数 N は裏返す石の位置、P は最初に置いた石の種類、Q は反転する石の種類、D は方向、A が反転した石の位置を格納する累積変数です。N に D を加算することで、その方向にある盤面の要素を順番に調べていきます。N 番目の石 (get-piece n) が P と同じ種類であれば、同じ種類の石で挟むことができました。累積変数 A をそのまま返します。
N 番目の石が Q と同じ種類であれば、その石を裏返すことができます。N を累積変数 A に追加して get-rev-stone-sub を再帰呼び出しします。このとき、引数 N に D を加算することをお忘れなく。それ以外の場合、N 番目は空き場所 (S) か壁 (O) なので石を反転させることはできません。空リスト NIL を返します。
あとは、get-rev-stone で get-rev-stone-sub を呼び出し、8 方向の結果を関数 mapcan でまとめるだけです。このとき、get-rev-stone-sub の第 1 引数には N の隣の位置 (+ n d) を渡すことに注意してください。
それではミニマックス法のプログラムを作りましょう。先手の指し手を決める関数 think-black は次のようになります。
リスト : ミニマックス法 (先手の手番)
(defun think-black (xs pass)
(if (null xs)
(values (get-value) nil) ; ゲーム終了 (空き場所なし)
(let ((value min-value) move)
(dolist (x xs)
(let ((rs (get-rev-stone x 'b)))
(when rs
(reverse-stone rs 'b)
(put-piece x 'b)
(multiple-value-bind
(v m)
(think-white (remove x xs) nil)
(del-piece x)
(reverse-stone rs 'w)
;; ミニマックス法
(when (< value v)
(setq value v move (cons x m)))))))
(if (not move)
(if pass
(values (get-value) (list 'pass)) ; ゲーム終了 (両者ともにパス)
(multiple-value-bind
(v m)
(think-white xs t)
(values v (cons 'pass m))))
(values value move)))))
引数 XS は空き場所を格納したリストです。相手がパスしたときは引数 PASS に真 (T) を渡します。think-black は評価値と指し手を格納したリストを多値で返します。XS が空リストの場合はゲーム終了です。評価値は関数 get-value で求めます。評価値は単純な石差 (黒石の数 - 白石の数) です。このとき *COUNT* の値も +1 します。そして values で評価値と空リストを返します。指し手はこの返り値のリストに追加していきます。
空き場所がある場合はミニマックス法で指し手を選びます。選んだ指し手は変数 MOVE に、評価値は VALUE に格納します。dolist で XS から空き場所を取り出して変数 X にセットし、get-rev-stone で反転する石を求めて変数 RS にセットします。RS が真の場合、reverse-stone で白石を黒石に反転して、put-piece で X に黒石を置きます。次に think-white を呼び出して手番を後手に移します。返り値は変数 V と M にセットされます。そのあと、盤面を元の状態に戻します。
次に、評価値 V と VALUE を比較します。V が VALUE よりも大きい場合は、指し手 X を選びます。指し手のリスト M に X を追加して、MOVE と VALUE の値を更新します。そうでなければ、MOVE と VALUE の値は更新しません。これでミニマックス法が動作します。
空き場所をすべて調べたあと、MOVE の値が NIL ならば、黒石を置くことができなかったのでパスします。もし引数の PASS が真ならば、白石と黒石どちらも置くことができないのでゲームを終了します。values で評価値とリスト (pass) を返します。
そうでなければ、関数 think-white を呼び出して手番を後手に移します。このとき、引数 PASS に T を渡します。その返り値を変数 V と M で受け取り、M に PASS を追加してから values で返します。MOVE が真の場合は、values で VALUE と MOVE を返します。
think-white は白石と黒石の処理が逆になるだけで、前回説明したミニマックス法と同じです。あとは特に難しいところは無いので説明は割愛いたします。詳細はプログラムリストをお読みください。
それでは実行結果を示します。
* (solver) value = -8 B : 8 B = 4 : W = 1 S B S S S B B S S B W S S S S S W : 7 B = 3 : W = 3 W B S S S W B S S B W S S S S S B : 13 B = 5 : W = 2 W B S S B B B S S B W S S S S S W : 9 B = 3 : W = 5 W W W S B B W S S B W S S S S S B : 28 B = 5 : W = 4 W W W S B B W S S B B S S S S B W : 19 B = 3 : W = 7 W W W S W W W S W B B S S S S B B : 10 B = 5 : W = 6 W W W B W W B S W B B S S S S B W : 26 B = 4 : W = 8 W W W B W W B S W W B S S W S B B : 25 B = 6 : W = 7 W W W B W W B S W B B S B W S B W : 27 B = 3 : W = 11 W W W B W W W S W W W S B W W B B : PASS!! W : PASS!! 60060
後手の 8 石勝ちとなりました。局面の評価回数は 60060 回です。アルファベータ法を使うと、もっと少なくすることができます。なお、この他にも白が 8 石勝ちとなる手順は存在します。ミニミニリバーシの場合、初手で黒石をどこにおいても、盤面を回転させれば同じ状態になります。また、初手を限定した場合でも、白が 8 石勝ちとなる手順は複数あるかもしれません。このプログラムは手順のひとつを求めているだけで、それが何通りあるかはわかりません。興味のある方は調べてみてください。
ちなみに、最初の黒石と白石の並びを下図のように変更しても後手必勝となりました。
┌─┬─┬─┬─┐ │ │ │ │ │ ├─┼─┼─┼─┤ │ │○│●│ │ ├─┼─┼─┼─┤ │ │○│●│ │ ├─┼─┼─┼─┤ │ │ │ │ │ └─┴─┴─┴─┘ 図 : ミニミニリバーシ(2)
実行結果を示します。
* (solver) value = -3 B : 7 B = 4 : W = 1 B S S S S B B S S W B S S S S S W : 10 B = 3 : W = 3 B S S W S B W S S W B S S S S S B : 16 B = 5 : W = 2 B S S W S B B B S W B S S S S S W : 22 B = 3 : W = 5 B S S W S B B W S W W W S S S S B : 25 B = 5 : W = 4 B S S W S B B W S B W W B S S S W : 9 B = 4 : W = 6 B S W W S B W W S B W W B S S S B : 28 B = 6 : W = 5 B S W W S B W W S B B W B S S B W : 19 B = 3 : W = 9 B S W W S W W W W W W W B S S B B : 13 B = 5 : W = 8 B S W W B W W W B W W W B S S B W : PASS!! B : 27 B = 7 : W = 7 B S W W B W W W B B W W B S B B W : 26 B = 6 : W = 9 B S W W B W W W B W W W B W B B B : PASS!! W : PASS!! 67116
後手の 3 石勝ちで、局面の評価回数は 67116 回となりました。
次はアルファベータ法を説明します。ミニマックス法の説明では、木を全て探索するので 8 回評価値を計算しましたが、アルファベータ法を使うと木を枝刈りすることができます。次の図を見てください。
Ｒ 先手の局面
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
Ａ(3) Ｂ(2) 後手の局面
／ ＼ ／ ×
／ ＼ ／ ×
Ｃ(3) Ｄ(4) Ｅ(2) Ｆ(5) 先手の局面
／ ＼ ／ × ／ ＼ ／ ＼
Ｇ Ｈ Ｉ Ｊ Ｋ Ｌ Ｍ Ｎ 後手の局面
１ ３ ４ ２ ２ １ ３ ５ 評価値
× × ×
図 : アルファベータ法
アルファベータ法を使うと、×で示した箇所で枝刈りが行われます。評価値の計算が 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 を枝刈りする
図 : ベータカット
今、後手が指し手を選ぶところなので、小さな評価値の方を選びます。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 を枝刈りする
図 : アルファカット
今、先手が指し手を選ぶところなので、大きな評価値の方を選びます。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) といい、そのとき基準になる値をアルファ値といいます。
この「アルファベータ法」がうまく働くと、局面を半分以上評価しないで済ますことができるようです。これは、実際にゲームを作ってその効果を確かめてみましょう。
それではアルファベータ法のプログラムを作りましょう。ポイントは基準値 (α値、β値) の管理です。プログラムは次のようになります。
リスト : 先手の手番
(defun think-black-ab (xs pass limit)
(if (null xs)
(values (get-value) nil) ; ゲーム終了 (空き場所なし)
(let ((value min-value) move)
(dolist (x xs)
(let ((rs (get-rev-stone x 'b)))
(when rs
(reverse-stone rs 'b)
(put-piece x 'b)
(multiple-value-bind
(v m)
(think-white-ab (remove x xs) nil value)
(del-piece x)
(reverse-stone rs 'w)
;; ミニマックス法
(when (< value v)
;; アルファベータ法
(when (<= limit v)
(return-from think-black-ab (values v (cons x m))))
(setq value v move (cons x m)))))))
(if (not move)
(if pass
(values (get-value) (list 'pass)) ; ゲーム終了 (両者ともにパス)
(multiple-value-bind
(v m)
(think-white-ab xs t value)
(values v (cons 'pass m))))
(values value move)))))
引数 LIMIT がアルファベータ法で使用する基準値です。この値は 1 手前の局面の評価値です。変数 VALUE は評価値を格納します。これはミニマックス法と同じです。この値が次の局面（後手番）での基準値となります。
アルファベータ法の処理は簡単です。ミニマックス法で指し手 X を選択した場合、評価値 V が LIMIT 以上の値になった時点で、その指し手と評価値を values で返すだけです。V が LIMIT よりも大きな値になった時点、つまり V > LIMIT で枝刈りしても正常に動作しますが、v >= limit としたほうが効率よく枝刈りできるようです。まだ評価値が求まっていない場合、LIMIT は 1 手前 (後手番) の局面の評価値ですから MAX-VALUE がセットされています。MAX-VALUE より大きな評価値はないので、アルファベータ法により枝刈りが実行されることはありません。
後手の指し手を選ぶ関数 think-white-ab は次のようになります。
リスト : 後手の手番
(defun think-white-ab (xs pass limit)
(if (null xs)
(values (get-value) nil) ; ゲーム終了 (空き場所なし)
(let ((value max-value) move)
(dolist (x xs)
(let ((rs (get-rev-stone x 'w)))
(when rs
(reverse-stone rs 'w)
(put-piece x 'w)
(multiple-value-bind
(v m)
(think-black-ab (remove x xs) nil value)
(del-piece x)
(reverse-stone rs 'b)
;; ミニマックス法
(when (< v value)
;; アルファベータ法
(when (<= v limit)
(return-from think-white-ab (values v (cons x m))))
(setq value v move (cons x m)))))))
(if (not move)
(if pass
(values (get-value) (list 'pass)) ; ゲーム終了 (両者ともにパス)
(multiple-value-bind
(v m)
(think-black-ab xs t value)
(values v (cons 'pass m))))
(values value move)))))
先手 (think-black-ab) とは逆に、後手 (think-white-ab) の場合は VALUE を MAX-VALUE で初期化します。後手の場合、ミニマックス法では小さな値を選ぶので、最初に求めた評価値が無条件に選択されます。アルファベータ法の場合も先手とは逆に、V が LIMIT 以下の値になった時点で枝刈りを行えばいいわけです。
それでは、実行結果を示しましょう。当然ですが、ゲームの結果はミニマックス法とアルファベータ法で変わりはありません。アルファベータ法が有効に機能すれば、ミニマックス法よりも局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数
| W B | W B
初期値| B W | W B
-------+-------+-------
minimax| 60060 | 67116
ab | 10016 | 13590
結果を見ればおわかりのように、アルファベータ法の比較回数はミニマックス法の約 1/5 から 1/6 程度になりました。ミニミニリバーシの場合、アルファベータ法の効果はとても高いですね。
一般に、アルファベータ法の探索では、評価値の高い局面から順番に探索すると効率が良くなります。最初に高い評価値が求まると、その値を使って効率よく枝刈りすることができるからです。実際のゲームでも、数レベルの浅い探索を行って評価値を求め、それに基づいて指し手の順番を並べ替えてから、深いレベルの探索を行う場合があります。このように、指し手の順番を並べ替えることでアルファベータ法の効率を改善する方法を move ordering といいます。
もちろん、完全に move ordering することは不可能ですが、指し手が多いゲームでは効果を期待することができます。今回のミニミニリバーシは隅を取ったほうが有利なので、隅に石を置く手から探索すると、move ordering と同様の効果を得ることができると思われます。具体的には、次のように think-black-ab を呼び出します。
リスト : 探索順序の変更 (think-black-ab '(7 10 25 28 8 9 13 16 19 22 26 27) nil max-value)
これで 4 か所の隅 (7, 10, 25, 28) から探索が行われます。実行結果は次のようになりました。
表 : 局面の評価回数
| W B | W B
初期値 | B W | W B
--------+-------+-------
minimax | 60060 | 67116
ab | 10016 | 13590
順序変更| 2387 | 4832
探索順序を変更するだけで、ここまで評価回数を減らすことができるとは驚きました。アルファベータ法の効率は探索する指し手の順序に依存することがよくわかります。
リバーシの場合、初手で石を置ける場所は 4 つありますが、盤面が正方形で石の配置も対称なので、4 つの場所をすべて調べる必要はありません。初手を限定することで解を高速に求めることができます。実行結果は次のようになりました。
表 : 局面の評価回数
| W B | W B
初期値 | B W | W B
--------+-------+-------
minimax | 15015 | 33558
ab | 730 | 5586
順序変更| 643 | 3410
初手 | 8 | 7, 13
結果は今までと同じです。初手を限定することで評価回数を大幅に減らすことができました。
;;;
;;; rev16.lisp : 4 行 4 列盤リバーシ
;;;
;;; Copyright (C) 2020 Makoto Hiroi
;;;
;;; 盤面の初期値
;;; o: 壁, s: 空き場所, b: 黒石, w: 白石
(defconstant 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))
(defconstant direction '(1 -1 6 -6 7 -7 5 -5)) ; 方向
(defconstant max-value 50)
(defconstant min-value -50)
(defvar *board*) ; 盤面
(defvar *black*) ; 黒石の個数
(defvar *white*) ; 白石の個数
(defvar *count*) ; 評価回数
;;; アクセス関数
(defun get-piece (x) (aref *board* x))
(defun put-piece (x p)
(case
p
(b (incf *black*))
(w (incf *white*)))
(setf (aref *board* x) p))
(defun del-piece (x)
(case
(get-piece x)
(b (decf *black*))
(w (decf *white*)))
(setf (aref *board* x) 's))
;;; 評価値を求める
(defun get-value ()
(incf *count*)
(- *black* *white*))
;;; 反転する石を求める
(defun get-rev-stone-sub (n p q d &optional a)
(cond
((eq (get-piece n) p) a)
((eq (get-piece n) q)
(get-rev-stone-sub (+ n d) p q d (cons n a)))
(t nil)))
(defun get-rev-stone (n p)
(let ((q (if (eq p 'b) 'w 'b)))
(mapcan (lambda (d) (get-rev-stone-sub (+ n d) p q d))
direction)))
;;; 石を反転する
(defun reverse-stone (xs p)
(mapc (lambda (x) (put-piece x p)) xs)
(case
p
(b (decf *white* (length xs)))
(w (decf *black* (length xs)))))
;;; 関数宣言
(declaim (ftype (function (list t) t) think-white)
(ftype (function (list t integer) t) think-white-ab))
;;; 先手の指し手
(defun think-black (xs pass)
(if (null xs)
(values (get-value) nil) ; ゲーム終了 (空き場所なし)
(let ((value min-value) move)
(dolist (x xs)
(let ((rs (get-rev-stone x 'b)))
(when rs
(reverse-stone rs 'b)
(put-piece x 'b)
(multiple-value-bind
(v m)
(think-white (remove x xs) nil)
(del-piece x)
(reverse-stone rs 'w)
;; ミニマックス法
(when (< value v)
(setq value v move (cons x m)))))))
(if (not move)
(if pass
(values (get-value) (list 'pass)) ; ゲーム終了 (両者ともにパス)
(multiple-value-bind
(v m)
(think-white xs t)
(values v (cons 'pass m))))
(values value move)))))
;;; 後手の指し手
(defun think-white (xs pass)
(if (null xs)
(values (get-value) nil) ; ゲーム終了 (空き場所なし)
(let ((value max-value) move)
(dolist (x xs)
(let ((rs (get-rev-stone x 'w)))
(when rs
(reverse-stone rs 'w)
(put-piece x 'w)
(multiple-value-bind
(v m)
(think-black (remove x xs) nil)
(del-piece x)
(reverse-stone rs 'b)
;; ミニマックス法
(when (< v value)
(setq value v move (cons x m)))))))
(if (not move)
(if pass
(values (get-value) (list 'pass)) ; ゲーム終了 (両者ともにパス)
(multiple-value-bind
(v m)
(think-black xs t)
(values v (cons 'pass m))))
(values value move)))))
;;;
;;; アルファベータ法
;;;
;;; 先手の指し手
(defun think-black-ab (xs pass limit)
(if (null xs)
(values (get-value) nil) ; ゲーム終了 (空き場所なし)
(let ((value min-value) move)
(dolist (x xs)
(let ((rs (get-rev-stone x 'b)))
(when rs
(reverse-stone rs 'b)
(put-piece x 'b)
(multiple-value-bind
(v m)
(think-white-ab (remove x xs) nil value)
(del-piece x)
(reverse-stone rs 'w)
;; ミニマックス法
(when (< value v)
;; アルファベータ法
(when (<= limit v)
(return-from think-black-ab (values v (cons x m))))
(setq value v move (cons x m)))))))
(if (not move)
(if pass
(values (get-value) (list 'pass)) ; ゲーム終了 (両者ともにパス)
(multiple-value-bind
(v m)
(think-white-ab xs t value)
(values v (cons 'pass m))))
(values value move)))))
;;; 後手の指し手
(defun think-white-ab (xs pass limit)
(if (null xs)
(values (get-value) nil) ; ゲーム終了 (空き場所なし)
(let ((value max-value) move)
(dolist (x xs)
(let ((rs (get-rev-stone x 'w)))
(when rs
(reverse-stone rs 'w)
(put-piece x 'w)
(multiple-value-bind
(v m)
(think-black-ab (remove x xs) nil value)
(del-piece x)
(reverse-stone rs 'b)
;; ミニマックス法
(when (< v value)
;; アルファベータ法
(when (<= v limit)
(return-from think-white-ab (values v (cons x m))))
(setq value v move (cons x m)))))))
(if (not move)
(if pass
(values (get-value) (list 'pass)) ; ゲーム終了 (両者ともにパス)
(multiple-value-bind
(v m)
(think-black-ab xs t value)
(values v (cons 'pass m))))
(values value move)))))
;;; 盤面の表示
(defun print-line (xs)
(mapc (lambda (x) (format t "~s " (get-piece x))) xs)
(terpri))
(defun print-board ()
(dolist (xs '((7 8 9 10) (13 14 15 16) (19 20 21 22) (25 26 27 28)))
(print-line xs))
(terpri))
;;; 手順の表示
(defun print-move (ls)
(let ((turn 'B))
(dolist (x ls)
(cond
((eq x 'pass)
(format t "~s : PASS!!~%" turn))
(t
(format t "~s : ~d~%" turn x)
(reverse-stone (get-rev-stone x turn) turn)
(put-piece x turn)
(format t "B = ~d : W = ~d~%" *black* *white*)
(print-board)))
(setq turn (if (eq turn 'b) 'w 'b)))))
;;; 解法
(defun solver ()
(setq *board* (make-array (length init-board) :initial-contents init-board)
*white* 2
*black* 2
*count* 0)
(multiple-value-bind
(v m)
; (think-black '(7 8 9 10 13 16 19 22 25 26 27 28) nil)
; (think-black-ab '(7 8 9 10 13 16 19 22 25 26 27 28) nil max-value)
(think-black-ab '(7 10 25 28 8 9 13 16 19 22 26 27) nil max-value)
(format t "value = ~d~% v)
(print-move m)
(print *count*)))