ミニマックス法と三目並べ
今回は囲碁や将棋のように 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 通りしかありません。あとは、ミニマックス法により最善手を選択させ、その結果を求めればいいわけです。今回のプログラムでは、指し手を保存しないで評価値の結果だけを出力することにします。
●プログラムの作成
それではプログラムを作ります。最初に大域変数とアクセス関数を定義します。
リスト : 大域変数とアクセス関数の定義
(import (scheme base) (scheme write)
(mylib list))
;;; 定数
(define SIZE 9)
(define MARU 1)
(define DRAW 0)
(define BATU -1)
(define MAX-VALUE 2)
(define MIN-VALUE -2)
;;; 盤面 : #f space, O maru, X batu
(define *board* (make-vector SIZE #f))
;;; 直線
(define *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
;;; アクセス関数
(define (get-piece n) (vector-ref *board* n))
(define (put-piece! n p) (vector-set! *board* n p))
(define (del-piece! n) (vector-set! *board* n #f))
今回のプログラムは拙作のライブラリ (mylib list) を使います。三目並べの場合、ゲーム終了まで読み切ることができるので、評価値は、勝ち、負け、引き分けの 3 つで十分です。これを MARU (先手勝ち)、BATU (後手勝ち)、DRAW (引き分け) で定義します。
盤面はベクタ *board* で表します。先手 ○ をシンボル O で、後手 × をシンボル X で、空き場所を #f で表します。*board* のアクセスは関数 get-piece, put-piece!, del-piece! で行います。盤面の場所とベクタの対応は、上図のように定義します。駒を置いた場所から直線を求めるためベクタ *lines* を定義します。たとえば、場所 0 が属する直線は 3 本あって、残り 2 か所の場所は (1 2), (3 6), (4 8) となります。
●勝敗の判定
勝敗を判定するプログラムは *lines* を使うと簡単にプログラムできます。
リスト : 勝敗の判定
;;; p が 3 つ並ぶか
(define (check-line? p a b)
(and (eq? (get-piece a) p) (eq? (get-piece b) p)))
;;; 勝負の判定
(define (win? n p)
(let loop ((ls (vector-ref *lines* n)))
(if (null? ls)
#f
(or (apply check-line? p (car ls))
(loop (cdr ls))))))
関数 win? は駒 p を場所 n に置いたときに勝負が決まるか調べます。*lines* から n が属する直線を順番に取り出して、関数 check-line で p と同じ駒が 3 つ並ぶかチェックします。そうであれば真を返し、そうでなければ次の直線を調べます。
●先手の指し手
次は、先手 (○) の指し手を決める think-maru を作ります。プログラムは次のようになります。
リスト : 先手の指し手
(define (think-maru n)
(if (= n SIZE)
DRAW
(let loop ((x 0) (value MIN-VALUE))
(cond
((= x SIZE) value)
((get-piece x)
(loop (+ x 1) value))
((win? x 'O) BATU) ; MARU)
(else
(put-piece! x 'O)
(let ((v (think-batu (+ n 1))))
(del-piece! x)
(loop (+ x 1) (max v value))))))))
think-maru の引数 n は手数を表します。n が SIZE と等しい場合、もう駒を置くことはできないので DRAW を返します。そうでなければ先手の指し手を選びます。選んだ指し手の評価値は named-let の変数 value に格納します。MIN-VALUE は BATU よりも小さな値にします。
次に、named-let で盤面の空き場所を探して、そこに O を置くと勝つことができるか win? でチェックします。返り値が真であれば O の勝ちなので MARU を返します。そうでなければ、put-piece! で盤面の x 番目に O をセットし、think-batu を呼び出して後手の指し手を選びます。返り値 (評価値) は変数 v にセットします。
ミニマックス法による指し手の決定は簡単です。先手は評価値が大きい手を選べばいいのですから、v が value よりも大きな値であれば、それを指し手として選びます。value は MIN-VALUE に初期化されているので、最初に調べた指し手は必ず選ばれることになります。最後に value を返します。
●後手の指し手
次は、後手 (×) の指し手を決める think-batu を作ります。プログラムは次のようになります。
リスト : 後手の指し手
(define (think-batu n)
(if (= n SIZE)
DRAW
(let loop ((x 0) (value MAX-VALUE))
(cond
((= x SIZE) value)
((get-piece x)
(loop (+ x 1) value))
((win? x 'X) MARU); BATU)
(else
(put-piece! x 'X)
(let ((v (think-maru (+ n 1))))
(del-piece! x)
(loop (+ x 1) (min v value))))))))
関数 think-batu は think-maru とは逆に、後手が有利になる指し手 (評価値が小さな手) を選びます。value は MARU よりも大きな値 MAX-VALUE に初期化しておきます。そして、ミニマックス法では、v が value よりも小さければ、それを選べばいいわけです。ミニマックス法のプログラムはこれだけです。
●初手の評価値を求める
最後に関数 solver を作ります。
リスト : 三目並べの解法
(define (solver)
(do ((x 0 (+ x 1)))
((>= x SIZE))
(put-piece! x 'O)
(display x) (display ":value = ")
(display (think-batu 1))
(newline)
(del-piece! x)))
solver は初手を指してから think-batu を呼び出して手番を相手に移します。この返り値が勝敗の結果を表しているので、それを出力するだけです。
●実行結果
それでは実行結果を示しましょう。
gosh[r7rs.user]> (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 #t
初手がどこでも結果は引き分けとなりました。これで、両者が最善を尽くすと引き分けになることが確かめられました。それでは、ルールを「3 つ並べた方が負け」に変更すると、結果はどうなるでしょうか。プログラムは簡単に改造できます。think-maru と think-batu で駒が 3 つ並んだとき、think-maru では BATU を、think-batu では MARU を返すように変更するだけです。
このルールでは先手が不利なように思いますが、それでも引き分けになるのでしょうか。さっそく実行してみましょう。
gosh[r7rs.user]> (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 #t
初手が中央の場合のみ引き分けで、あとは後手の勝ちとなりました。後手必勝にはなりませんでしたね。興味のある方は、実際にプレイして確かめてみてください。また、今回のプログラムは評価値を出力するだけでしたが、指し手を表示するように改造してみるのも面白いと思います。
●戦略に基づいたプレイ
ところで、参考文献 [1] によると、三目並べで両者が次の戦略を用いると、ゲームは常に引き分けになります。
- 3 つ並べることができるならばそうする
- 相手が 3 つ並べるのを妨げる
- 可能ならば中央へ着手する
- 可能ならば隅へ着手する
本当に引き分けになるのか、実際にプログラムを作って確かめてみましょう。
●プログラムの作成 (2)
最初に同じ駒を 3 つ並べることができる場所を探す関数 get-win-position を作ります。
リスト : 勝てる場所を探す (define (get-win-position p xs) (find-if (lambda (x) (and (not (get-piece x)) (win? x p))) xs))
この処理は次の 1 手で勝てる場所を探すことになるので、関数名を get-win-position としました。引数 p は駒の種類を、xs は空き場所を格納したリストです。関数 find-if は拙作のライブラリ (mylib list) に用意されている高階関数で、SRFI-1 の find と同じ働きをします。ラムダ式の引数 x が調べる場所を表します。(win? x p) を呼び出して返り値が真ならば x を返します。
次はコンピュータの指し手を決める関数 move-com を作ります。
リスト : コンピュータの指し手を決定する
;;; 空いているコーナーを探す
(define (get-corner)
(find-if (lambda (x) (not (get-piece x))) '(0 2 6 8)))
;;; COM の指し手
(define (move-com p xs)
(or (get-win-position p xs)
(get-win-position (if (eq? p 'O) 'X 'O) xs)
(and (not (get-piece 4)) 4)
(get-corner)
(car xs)))
関数 move-com は戦略に従ってコンピュータの指し手を決定します。引数 p は自分の駒の種類を表します。まず最初に get-win-position を呼び出して、駒を 3 つ並べることができるか調べます。自分が勝てるのであれば、その場所を返します。そうでなければ、相手が駒を 3 つ並べることができるか調べます。これは get-win-position で相手の駒の種類を渡せば調べることができます。そうであれば、その場所に自分の駒をおきます。
それ以外の場合は、優先順位（中央 -> 隅 -> 空き場所) に従って駒を置きます。空いているコーナーは関数 get-corner で求めます。空き場所は引数 xs の先頭要素を返すだけです。
最後にゲームを進める関数 play を作ります。
リスト : ゲームの進行
(define (play)
(vector-fill! *board* #f)
(let loop ((xs (iota 9 0)) (turn 'O))
(if (null? xs)
(display "DRAW\n")
(let ((x (move-com turn xs)))
(put-piece! x turn)
(print-board)
(cond
((win? x turn)
(display turn)
(display " WIN!\n"))
(else
(loop (remove x xs) (if (eq? turn 'O) 'X 'O))))))))
named-let の変数 xs は空き場所を格納したリストです。turn は手番を表す変数です。move-com で指し手を決め、(win? x turn) を呼び出して勝敗の判定を行います。返り値が真であればゲーム終了です。そうでなければ、手番を変えてゲームを続行します。
●実行結果 (2)
それでは実行結果を示します。
gosh[r7rs.user]> (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 #<undef>
確かに引き分けになりますね。
●参考文献
- 松原仁・竹内郁雄 編著,『bit別冊 ゲームプログラミング』, 共立出版, 1997
●プログラムリスト
;;;
;;; tictactoe.scm : 三目並べ (ミニマックス法)
;;;
;;; Copyright (C) 2010-2020 Makoto Hiroi
;;;
(import (scheme base) (scheme write)
(mylib list))
;;; 定数
(define SIZE 9)
(define MARU 1)
(define DRAW 0)
(define BATU -1)
(define MAX-VALUE 2)
(define MIN-VALUE -2)
;;; 盤面 : #f space, O maru, X batu
;;; 0 1 2
;;; 3 4 5
;;; 6 7 8
(define *board* (make-vector SIZE #f))
;;; 直線
(define *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
;;; アクセス関数
(define (get-piece n) (vector-ref *board* n))
(define (put-piece! n p) (vector-set! *board* n p))
(define (del-piece! n) (vector-set! *board* n #f))
;;; p が 3 つ並ぶか
(define (check-line? p a b)
(and (eq? (get-piece a) p) (eq? (get-piece b) p)))
;;; 勝負の判定
(define (win? n p)
(let loop ((ls (vector-ref *lines* n)))
(if (null? ls)
#f
(or (apply check-line? p (car ls))
(loop (cdr ls))))))
;;; 先手 (まる)
(define (think-maru n)
(if (= n SIZE)
DRAW
(let loop ((x 0) (value MIN-VALUE))
(cond
((= x SIZE) value)
((get-piece x)
(loop (+ x 1) value))
((win? x 'O) BATU) ; MARU)
(else
(put-piece! x 'O)
(let ((v (think-batu (+ n 1))))
(del-piece! x)
(loop (+ x 1) (max v value))))))))
;;; 後手 (ばつ)
(define (think-batu n)
(if (= n SIZE)
DRAW
(let loop ((x 0) (value MAX-VALUE))
(cond
((= x SIZE) value)
((get-piece x)
(loop (+ x 1) value))
((win? x 'X) MARU); BATU)
(else
(put-piece! x 'X)
(let ((v (think-maru (+ n 1))))
(del-piece! x)
(loop (+ x 1) (min v value))))))))
;;; 三目並べの解法
(define (solver)
(do ((x 0 (+ x 1)))
((>= x SIZE))
(put-piece! x 'O)
(display x) (display ":value = ")
(display (think-batu 1))
(newline)
(del-piece! x)))
;;;
;;; 戦略に基づいたプレイ
;;;
;;; 勝てる場所を探す
(define (get-win-position p xs)
(find-if (lambda (x) (and (not (get-piece x)) (win? x p))) xs))
;;; 空いているコーナーを探す
(define (get-corner)
(find-if (lambda (x) (not (get-piece x))) '(0 2 6 8)))
;;; COM の指し手
(define (move-com p xs)
(or (get-win-position p xs)
(get-win-position (if (eq? p 'O) 'X 'O) xs)
(and (not (get-piece 4)) 4)
(get-corner)
(car xs)))
;;; 盤面の表示
(define (print-piece p)
(display (if p p '_))
(display " "))
(define (print-board)
(do ((x 0 (+ x 1)))
((>= x SIZE) (newline))
(if (zero? (modulo x 3)) (newline))
(print-piece (get-piece x))))
;;; ゲームの進行
(define (play)
(vector-fill! *board* #f)
(let loop ((xs (iota 9 0)) (turn 'O))
(if (null? xs)
(display "DRAW\n")
(let ((x (move-com turn xs)))
(put-piece! x turn)
(print-board)
(cond
((win? x turn)
(display turn)
(display " WIN!\n"))
(else
(loop (remove x xs) (if (eq? turn 'O) 'X 'O))))))))
改訂 2020 年 10 月 18 日