ミニマックス法と三目並べ
今回は囲碁や将棋のように 2 人が交互に 1 手ずつ指していくゲームを取り上げます。コンピュータにゲームの相手をさせる場合、コンピュータの指し手を決定するためのプログラム、いわゆる「思考ルーチン」が必要になります。この思考ルーチンで使われる基本的なアルゴリズムが「ミニマックス法 (mini-max method)」です。難しそうな名前がついていますが、ミニマックス法は基本的には深さ優先探索と同じです。拙作のページ 経路の探索 で説明した基本的な探索アルゴリズムを理解していれば、それほど難しい話ではありません。
そうはいっても、実際のゲームで強い思考ルーチンを作成するのは簡単な話ではありません。チェスや将棋などに比べると、リバーシの思考ルーチンは簡単だといわれています。ところが、実際にプログラムしてみると強い思考ルーチンを作るのは本当に難しい、というのが M.Hiroi の実感です。それでも、リバーシは終盤になると最後まで読み切ることができるので、初心者や初級者レベルよりも強いプログラムを作るのは比較的簡単なほうでしょう。
今回は思考ゲームの基本とミニマックス法について説明します。そして、簡単なゲームである「三目並べ」の勝敗結果 (先手必勝、後手必勝、引き分け) をミニマックス法で調べてみましょう。最初に思考ゲームの基本とミニマックス法について説明します。
●ゲームの木
二人で対戦するゲームの場合、ゲームの進行状況は盤面の状態で表すことができます。指し手が進むにつれて盤面の状態は変化し、最後にはゲームが終了します。このようなゲームでは、その状態の変化を木構造に対応させることができます。これを「ゲームの木 (game tree)」といいます。
たとえば、「エイト」というゲームを考えてみます。このゲームのルールは、2 人のプレーヤーが 1 から 3 までの数字を交互に選び、2 人が選んだ数の合計が 8 になったら勝ち、8 を越えたら負けになります。数字の選び方には条件があって、一番最初は好きな数字を選ぶことができますが、それ以降は前回相手が選んだ数を選ぶことはできません。このゲームの木は、手作業でも簡単に作成することができます。下図にゲームの木の一部を示します。
先手は最初に 1 から 3 の中の好きな数字を選ぶことができます。この木は、最初に先手が 2 を選び、次に後手が 1 を選んだ状態のゲームの木を示しています。数字の合計が 8 以上になったらゲームは終了です。木の高さはたかだか 6 レベルしかないので、エイトはとても簡単なゲームであることがわかります。
エイトのように、ゲーム開始から終了までの「ゲームの木」を作成できれば完璧な指し手を実現できます。ところが一般のゲームでは、ある局面で可能な指し手は多数あるので、ゲームの木はとても大きくなります。このため、完全なゲームの木を作成することは不可能です。
そこで、不完全ですが数レベル分の木を作成します。つまり、数手先読みするわけです。先読みした局面の状態は、ほとんどが勝ちでも負けでもない曖昧なものです。ここで、その局面の状態を評価して、自分が有利であれば 50 点とか不利であれば -10 点という具合に、局面の状態を数値化します。この処理を行う関数を「評価関数」といいます。とりあえず勝ち負けはわかりませんが、この評価値が高くなるように、つまり自分が有利になるように指し手を進めていくわけです。
もしも、完璧な評価関数がわかれば、その局面の状態から最善手がわかることになり、わざわざ木を探索する必要はありません。ところが、一般のゲームは状況がとても複雑なので、局面を正確に評価することは至難の技です。計算した評価値はどうしても適当なものになってしまいます。そこで、これを補うために「ミニマックス法」という手法を使います。
ミニマックス法の考え方はそれほど難しいものではありません。自分にとって良い指し手は相手にとって都合が悪く、逆もまたそうであるという仮説に基づいたアルゴリズムです。ゲームの木を何層か探索して、その局面を評価することは同じですが、「相手は自分に取って最悪の指し手を選択する」と仮定するところが、このアルゴリズムのポイントです。つまり、自分の指し手では評価値が最大になるように選択し、相手の指し手では評価値が最小になるように選択するのです。これが「ミニマックス」という名前の由来です。
ひらたくいえば、相手の手を先読みして自分の手を決めるということです。たとえば将棋の場合でも、駒の動かし方がわかる程度の初心者では相手の手を読むことは難しいですが、慣れてくると 2 手 3 手程度の先読みはできるようになります。これがプロ棋士になると、十数手から二十手前後まで考えるというのですから驚きです。
ミニマックス法を使う場合でも、評価関数が適切なものであれば、ゲームの木を深く探索するほど正確な評価値を求めることができるようになります。ただし、木を深いレベルまで探索しようとすると、特に囲碁や将棋のような一つの局面で有効な指し手が多数あるゲームでは、木の枝が多数分岐するので、探索のために消費するメモリと時間が膨大なものになってしまいます。
これを防ぐために「アルファベータ法」という方法を用いたり、ほかにもさまざまな工夫を行うことで無駄な木の探索を極力省くようにします。それでもハードウェアの限界により、ある程度のレベルで探索を打ち切ることになります。また、持ち時間が設定されている場合は、それも考慮して探索レベルを決める必要があります。
●ミニマックス法
それでは、具体的にミニマックス法を説明しましょう。ここでは、簡単な仮想ゲームを考えてみます。このゲームは、先手後手とも指し手は常に 2 通りあって、そのうちの一つを選ぶことでゲームが進行します。
ミニマックス法を使う場合、局面の評価値が必要になります。評価関数は、先手が有利（後手が不利）な局面ほど大きな値 (正の値)、逆に後手が有利 (先手が不利) なほど小さな値 (負の値)、互角の場合は 0 になるように作るのが一般的です。
探索のレベルは、先手－後手－先手の 3 手先まで読むことにします。先手の局面 R を探索すると、下図に示すゲームの木になりました。
評価値は最も深いレベル、この場合は 3 手指した後手の局面で計算します。3 レベルまで探索すると 8 通りの評価値が計算されますが、この評価値を使って、A と B のどちらの手を指すかミニマックス法で決定します。
R - A - C の局面に注目してください。この局面では、先手は 2 通りの指し手があり、それぞれ G と H という局面になります。この局面の評価値を計算すると、それぞれ 1 と 3 になります。ここでは先手の手番ですから、評価値が最大になるような指し手を選択します。したがって、局面 C の評価値は 3 に定まります。
同様に R - A - D の局面を計算すると、局面 D の評価値は 4 になります。局面 C と D の評価値が決まったので、局面 A の評価値を決めることができます。局面 A は後手の手番ですから、今度は評価値が最小になるような指し手を選びます。局面 C と D の小さい方を選ぶので、局面 A の評価値は 3 になります。
同様に局面 B の評価値を求めると 2 になります。局面 R は先手の手番なので、評価値の大きい指し手を選びます。この場合は、A が有利であることがわかります。このように、先手番では評価値が最大値となる指し手を選び、後手番では評価値が最小値となる指し手を選ぶことで、指し手を決定する方法がミニマックス法なのです。
ただし、ミニマックス法で選んだ指し手が最善手である保証はありません。この例では、ゲームの木を 3 レベル探索して A を選びましたが、もう一段深く探索してみると B の方が有利だった、ということもありえます。ようするに、3 手先までは読んでいたが、その先の手は読んでいなかった、ということです。これは私達がゲームをプレイする場合でもあることですね。
もしも、ゲームの木を最後まで探索できれば、最善手を指すことができます。たとえば、リバーシは終盤になると最後まで読み切ることが可能なゲームです。この状態になるとコンピュータは最善手を指してきます。コンピュータリバーシの得意技「終盤の大逆転」は、ゲームの木を最後まで読み切るからこそできることなのです。
●三目並べ
三目並べは皆さんお馴染みの二人で対戦するゲームです。ひとりが○側でもうひとりが×側を受け持ち、3 行 3 列のマス目に○×を書いて、3 つ並べた方が勝ちというゲームです。
上図は○側が先手で引き分けになった例です。三目並べは、両者が最善を尽くすと引き分けになることが知られています。本当に引き分けになるのか、プログラムを作って確かめてみましょう。
三目並べは簡単なゲームなので、ゲーム終了まで読み切ることができます。局面の状態は、○側の勝ち、×側の勝ち、引き分けの 3 通りしかありません。あとは、ミニマックス法により最善手を選択させ、その結果を求めればいいわけです。
とりあえず、プログラムでは指し手を保存しないで、評価値の結果だけを出力することにします。初手をどこに選んでも、引き分けの評価値が出力されるはずです。
●プログラムの作成
それではプログラムを作ります。最初に盤面とアクセス関数を定義します。
リスト : 盤面とアクセス関数の定義
;;; 定数
(defconstant size 9)
(defconstant maru 1)
(defconstant draw 0)
(defconstant batu -1)
(defconstant max-value 2)
(defconstant min-value -2)
;;; 直線
(defconstant lines
#(((1 2) (3 6) (4 8)) ; 0
((0 2) (4 7)) ; 1
((0 1) (5 8) (4 6)) ; 2
((0 6) (4 5)) ; 3
((1 7) (3 5) (0 8) (2 6)) ; 4
((2 8) (3 4)) ; 5
((0 3) (2 4) (7 8)) ; 6
((1 4) (6 8)) ; 7
((0 4) (2 5) (6 7)))) ; 8
;;; 盤面
(defvar *board* (make-array size :initial-element nil))
;;; アクセス関数
(defun get-piece (n) (aref *board* n))
(defun put-piece (n p) (setf (aref *board* n) p))
(defun del-piece (n) (put-piece n nil))
三目並べの場合、ゲーム終了まで読み切ることができるので、評価値は、勝ち、負け、引き分けの 3 つで十分です。これを定数 MARU (先手勝ち)、BARU (後手勝ち)、DRAW (引き分け) で定義します。
盤面はベクタ *board* で表します。先手 ○ をシンボル O で、後手 × をシンボル X で、空き場を NIL で表します。*board* のアクセスは関数 get-piece, put-piece, del-piece で行います。盤面の場所とベクタの対応は、上図のように定義します。駒を置いた場所から直線を求めるためベクタ LINES を定義します。たとえば、場所 0 が属する直線は 3 本あって、残り 2 か所の場所は (1 2), (3 6), (4 8) となります。
●勝敗の判定
勝敗を判定するプログラムは lines を使うと簡単にプログラムできます。
リスト : 勝敗の判定
(defun check-win (n p)
(loop for (i j) in (aref lines n)
when (and (eq (get-piece i) p) (eq (get-piece j) p))
do (return t)))
関数 check-win は場所 N に駒 P を置いたとき、勝負が決まるかチェックします。loop マクロで LINES から N が属する直線を順番に取り出して、N 以外の位置を変数 I, J にセットします。そして、P と同じ駒が 3 つ並ぶかチェックして、そうであれば T を返します。
●先手の指し手
次は、先手 (○) の指し手を決める think-maru を作ります。プログラムは次のようになります。
リスト : 先手の指し手
(defun think-maru (n)
(if (= n size)
draw
(let ((value min-value) v)
(dotimes (x size value)
(unless (get-piece x)
(when (check-win x 'o) (return maru))
(put-piece x 'o)
(setq v (think-batu (1+ n)))
(when (< value v) (setq value v))
(del-piece x))))))
think-maru の引数 N は手数を表します。N が SIZE と等しい場合、もう駒を置くことはできないので DRAW を返します。そうでなければ先手の指し手を選びます。選んだ指し手の評価値は VALUE に格納します。MIN-VALUE は BATU よりも小さな値にします。
次に、dotimes で盤面の空き場所を探して、そこに O を置くと勝つことができるか check-win でチェックします。返り値が真であれば O の勝ちです。return で MARU を返します。そうでなければ、put-piece で盤面の X 番目に O をセットし、think-batu を呼び出して後手の指し手を選びます。返り値 (評価値) は変数 V にセットします。
ミニマックス法による指し手の決定は簡単です。先手は評価値が大きい手を選べばいいのですから、V が VALUE よりも大きな値であれば、それを指し手として選びます。VALUE は MIN-VALUE に初期化されているので、最初に調べた指し手は必ず選ばれることになります。最後に VALUE を返します。
●後手の指し手
次は、後手 (×) の指し手を決める think-batu を作ります。プログラムは次のようになります。
リスト : 後手の指し手
(defun think-batu (n)
(if (= n size)
draw
(let ((value max-value) v)
(dotimes (x size value)
(unless (get-piece x)
(when (check-win x 'x) (return batu))
(put-piece x 'x)
(setq v (think-maru (1+ n)))
(when (< v value) (setq value v))
(del-piece x))))))
関数 think-batu は think-maru とは逆に、後手が有利になる指し手 (評価値が小さな手) を選びます。VALUE は MARU よりも大きな値 MAX-VALUE に初期化しておきます。そして、ミニマックス法では、V が VALUE よりも小さければ、それを選べばいいわけです。ミニマックス法のプログラムはこれだけです。
●初手の評価値を求める
最後に関数 solver を作ります。
リスト : 三目並べの解法
(defun solver ()
(dotimes (x size)
(put-piece x 'o)
(format t "~d: value = ~d~%" x (think-batu 1))
(del-piece x)))
solver は初手を指してから think-batu を呼び出して手番を相手に移します。この返り値が勝敗の結果を表しているので、それを出力するだけです。
●実行結果
それでは実行結果を示しましょう。
* (solver) 0: value = 0 1: value = 0 2: value = 0 3: value = 0 4: value = 0 5: value = 0 6: value = 0 7: value = 0 8: value = 0 NIL
初手がどこでも、結果は引き分けとなりました。これで、両者が最善を尽くすと引き分けになることが確かめられました。それでは、ルールを「3 つ並べた方が負け」に変更すると、結果はどうなるでしょうか。プログラムは簡単に改造できます。think-maru と think-batu で駒が 3 つ並んだとき、think-maru では BATU を、think-batu では MARU を返すように変更するだけです。
このルールでは先手が不利なように思いますが、それでも引き分けになるのでしょうか。さっそく実行してみましょう。
* (solver) 0: value = -1 1: value = -1 2: value = -1 3: value = -1 4: value = 0 5: value = -1 6: value = -1 7: value = -1 8: value = -1 NIL
初手が中央の場合のみ引き分けで、あとは後手の勝ちとなりました。後手必勝にはなりませんでしたね。興味のある方は、実際にプレイして確かめてみてください。また、今回のプログラムは評価値を出力するだけでしたが、指し手を表示するように改造してみるのも面白いと思います。
●戦略に基づいたプレイ
ところで、参考文献 [1] によると、三目並べで両者が次の戦略を用いると、ゲームは常に引き分けになります。
- 3 つ並べることができるならばそうする
- 相手が 3 つ並べるのを妨げる
- 可能ならば中央へ着手する
- 可能ならば隅へ着手する
本当に引き分けになるのか、実際にプログラムを作って確かめてみましょう。
●プログラムの作成 (2)
最初に同じ駒を 3 つ並べることができる場所を探す関数を作ります。
リスト : 勝てる場所を探す
(defun get-win-position (p)
(dotimes (x SIZE)
(when (and (not (get-piece x)) (check-win x p))
(return x))))
この処理は次の 1 手で勝てる場所を探すことになるので、関数名を get-win-position としました。引数 P は駒の種類を表します。dotimes で盤面を探索し、X が空き場所で P を置くと 3 つ並ぶ場合、return で X を返します。
次はコンピュータの指し手を決める関数 move-com を作ります。
リスト : コンピュータの指し手を決定する
;;; 空いているコーナーを探す
(defun get-corner ()
(dolist (x '(0 2 6 8))
(unless (get-piece x) (return x))))
;;; COM の指し手
(defun move-com (p)
(or (get-win-position p)
(get-win-position (if (eq p 'o) 'x 'o))
(and (not (get-piece 4)) 4)
(get-corner)
(position nil *board*)))
関数 move-com は戦略に従ってコンピュータの指し手を決定します。引数 P は自分の駒の種類を表します。まず最初に get-win-position を呼び出して、P を 3 つ並べることができるか調べます。自分が勝てるのであれば、その場所を返します。そうでなければ、相手が駒を 3 つ並べることができるか調べます。これは get-win-position で相手の駒の種類を渡せば調べることができます。そうであれば、その場所に自分の駒をおきます。
それ以外の場合は、優先順位（中央 -> 隅 -> 空き場所) に従って駒を置きます。空いているコーナーは関数 get-corner で求めます。空き場所は position で NIL を探索するだけです。
最後にゲームを進める関数 play を作ります。
リスト : ゲームの進行
(defun play ()
(fill *board* nil)
(let ((turn 'o))
(dotimes (x size (format t "DRAW~%"))
(let ((x (move-com turn)))
(put-piece x turn)
(print-board)
(when (check-win x turn)
(format t "~s WIN!!~%" turn)
(return))
(setq turn (if (eq turn 'o) 'x 'o))))))
TURN は手番を表す変数です。move-com で指し手を決め、put-piece で駒を置いて print-board で盤面を表示します。それから、check-win で勝敗の判定を行います。返り値が真であれば TURN の勝ちです。そうでなければ、手番を変えてゲームを続行します。
●実行結果 (2)
それでは実行結果を示します。
* (play) _ _ _ _ O _ _ _ _ X _ _ _ O _ _ _ _ X _ O _ O _ _ _ _ X _ O _ O _ X _ _ X _ O O O _ X _ _ X _ O O O X X _ _ X _ O O O X X _ O X X O O O X X _ O X X O O O X X O O DRAW NIL
確かに引き分けになりますね。そこで問題です。
相手が次の戦略を用いる場合、先手に必勝法があります。それを見つけてください。
- 3 つ並べることができるならばそうする
- 相手が 3 つ並べるのを妨げる
- 可能ならば中央へ着手する
- 可能ならば隅へ着手する
簡単な問題なので、息抜きや気分転換のときにちょっと考えてみてください。
●参考文献
- 松原仁・竹内郁雄 編著,『bit別冊 ゲームプログラミング』, 共立出版, 1997
●プログラムリスト
;;;
;;; tictactoe.lisp : 三目並べ
;;;
;;; Copyright (C) 2020 Makoto Hiroi
;;;
;;; 定数
(defconstant size 9)
(defconstant maru 1)
(defconstant draw 0)
(defconstant batu -1)
(defconstant max-value 2)
(defconstant min-value -2)
;;; 盤面
;;; 0 1 2
;;; 3 4 5
;;; 6 7 8
;;; 直線
(defconstant lines
#(((1 2) (3 6) (4 8)) ; 0
((0 2) (4 7)) ; 1
((0 1) (5 8) (4 6)) ; 2
((0 6) (4 5)) ; 3
((1 7) (3 5) (0 8) (2 6)) ; 4
((2 8) (3 4)) ; 5
((0 3) (2 4) (7 8)) ; 6
((1 4) (6 8)) ; 7
((0 4) (2 5) (6 7)))) ; 8
;;; 盤面
(defvar *board* (make-array size :initial-element nil))
;;; アクセス関数
(defun get-piece (n) (aref *board* n))
(defun put-piece (n p) (setf (aref *board* n) p))
(defun del-piece (n) (put-piece n nil))
;;; 勝敗の判定
(defun check-win (n p)
(loop for (i j) in (aref lines n)
when (and (eq (get-piece i) p) (eq (get-piece j) p))
do (return t)))
;;; 先手の指し手
(defun think-maru (n)
(if (= n size)
draw
(let ((value min-value) v)
(dotimes (x size value)
(unless (get-piece x)
(when (check-win x 'o) (return maru))
(put-piece x 'o)
(setq v (think-batu (1+ n)))
(when (< value v) (setq value v))
(del-piece x))))))
;;; 後手の指し手
(defun think-batu (n)
(if (= n size)
draw
(let ((value max-value) v)
(dotimes (x size value)
(unless (get-piece x)
(when (check-win x 'x) (return batu))
(put-piece x 'x)
(setq v (think-maru (1+ n)))
(when (< v value) (setq value v))
(del-piece x))))))
;;; 三目並べの解法
(defun solver ()
(dotimes (x size)
(put-piece x 'o)
(format t "~d: value = ~d~%" x (think-batu 1))
(del-piece x)))
;;;
;;; 戦略に基づいたプレイ
;;;
;;; 勝てる場所を探す
(defun get-win-position (p)
(dotimes (x SIZE)
(when (and (not (get-piece x)) (check-win x p))
(return x))))
;;; 空いているコーナーを探す
(defun get-corner ()
(dolist (x '(0 2 6 8))
(unless (get-piece x) (return x))))
;;; COM の指し手
(defun move-com (p)
(or (get-win-position p)
(get-win-position (if (eq p 'o) 'x 'o))
(and (not (get-piece 4)) 4)
(get-corner)
(position nil *board*)))
;;; 盤面の表示
(defun print-piece (p)
(format t "~s " (if p p '_)))
(defun print-board ()
(dotimes (x 9 (terpri))
(if (zerop (mod x 3)) (terpri))
(print-piece (get-piece x))))
;;; ゲームの進行
(defun play ()
(fill *board* nil)
(let ((turn 'o))
(dotimes (x size (format t "DRAW~%"))
(let ((x (move-com turn)))
(put-piece x turn)
(print-board)
(when (check-win x turn)
(format t "~s WIN!!~%" turn)
(return))
(setq turn (if (eq turn 'o) 'x 'o))))))
●解答
解答の一例を示します。
初手を中央ではなく隅へ着手するのがポイントです。後手は戦略に従って中央を取るので、次は初手の対角線上にある隅を取ります (局面 A)。後手が戦略に従う場合、次は隅を取ることになりますね。どちらの隅を取っても、先手は残りの隅を取れば勝つことができます。
もちろん、後手が戦略に従わなければ、局面 A からでも引き分けになります。一例を示しましょう。
このように、局面 A で後手が隅を取らなければ引き分けになります。