今回は、囲碁や将棋のように 2 人が交互に 1 手ずつ指していくゲームを取り上げます。コンピュータにゲームの相手をさせる場合、コンピュータの指し手を決定するためのプログラム、いわゆる「思考ルーチン」が必要になります。この思考ルーチンで使われる基本的なアルゴリズムが「ミニマックス法 (mini-max method) 」と「アルファベータ法 (αβ method) 」です。難しそうな名前がついていますが、ミニマックス法の基本は深さ優先探索ですし、アルファベータ法はミニマックス法を効率化するための枝刈りにすぎません。拙作のページ お気楽 Python プログラミング入門第 3 回 や 集合、グラフ、経路の探索 で説明した基本的な探索アルゴリズムを理解していれば、それほど難しい話ではないのです。
そうはいっても、実際のゲームで強い思考ルーチンを作成するのは簡単な話ではありません。チェスや将棋などに比べると、リバーシの思考ルーチンは簡単だといわれています。ところが、実際にプログラムしてみると、強い思考ルーチンを作るのは本当に難しい、というのが M.Hiroi の実感です。それでも、リバーシは終盤になると最後まで読み切ることができるので、初心者や初級者レベルよりも強いプログラムを作るのは比較的簡単なほうでしょう。
今回は「カラー (kalah) 」という簡単なゲームを題材に、ミニマックス法とアルファベータ法を説明します。まずは、思考ゲームの基本から説明しましょう。
二人で対戦するゲームの場合、ゲームの進行状況は盤面の状態で表すことができます。指し手が進むにつれて盤面の状態は変化し、最後にはゲームが終了します。このようなゲームでは、その状態の変化を木構造に対応させることができます。これを「ゲームの木 (game tree) 」といいます。
たとえば、「エイト」というゲームを考えてみます。このゲームのルールは、2 人のプレーヤーが 1 から 3 までの数字を交互に選び、2 人が選んだ数の合計が 8 になったら勝ち、8 を越えたら負けになります。数字の選び方には条件があって、一番最初は好きな数字を選ぶことができますが、それ以降は前回相手が選んだ数を選ぶことはできません。このゲームの木は、手作業でも簡単に作成することができます。下図にゲームの木の一部を示します。
root
／│＼
先手 １ ２ ３
／ ＼
後手 １(3) ３(5)
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
先手 ２(5) ３(6)
／ ＼ ／ ＼
／ ＼ ／ ＼
後手 １(6) ３(8) １(7) ２(8)
／ ＼ ● ／ ＼ ●
先手 １(7) ３(9) ２(9) ３(10)
／ ＼ ● ● ●
後手 ２(9) ３(10)
○ ○
○：先手勝ち ●：後手勝ち
図 : ゲームの木（一部）
先手は最初に 1 から 3 の中の好きな数字を選ぶことができます。この木は、最初に先手が 2 を選び、次に後手が 1 を選んだ状態のゲームの木を示しています。数字の合計が 8 以上になったらゲームは終了です。木の高さはたかだか 6 レベルしかないので、エイトはとても簡単なゲームであることがわかります。
エイトのように、ゲーム開始から終了までの「ゲームの木」を作成できれば完璧な指し手を実現できます。ところが一般のゲームでは、ある局面で可能な指し手は多数あるので、ゲームの木はとても大きくなります。このため、完全なゲームの木を作成することは不可能です。
そこで、不完全ですが数レベル分の木を作成します。つまり、数手先読みするわけです。先読みした局面の状態は、ほとんどが勝ちでも負けでもない曖昧なものです。ここで、その局面の状態を評価して、自分が有利であれば 50 点とか不利であれば -10 点という具合に、局面の状態を数値化します。この処理を行う関数を「評価関数」といいます。とりあえず勝ち負けはわかりませんが、この評価値が高くなるように、つまり自分が有利になるように指し手を進めていくわけです。
もしも、完璧な評価関数がわかれば、その局面の状態から最善手がわかることになり、わざわざ木を探索する必要はありません。ところが、一般のゲームは状況がとても複雑なので、局面を正確に評価することは至難の技です。計算した評価値はどうしても適当なものになってしまいます。そこで、これを補うために「ミニマックス法」という手法を使います。
ミニマックス法の考え方はそれほど難しいものではありません。自分にとって良い指し手は相手にとって都合が悪く、逆もまたそうであるという仮説に基づいたアルゴリズムです。ゲームの木を何層か探索して、その局面を評価することは同じですが、「相手は自分に取って最悪の指し手を選択する」と仮定するところが、このアルゴリズムのポイントです。つまり、自分の指し手では評価値が最大になるように選択し、相手の指し手では評価値が最小になるように選択するのです。これが「ミニマックス」という名前の由来です。
ひらたくいえば、相手の手を先読みして自分の手を決めるということです。たとえば将棋の場合でも、駒の動かし方がわかる程度の初心者では相手の手を読むことは難しいですが、慣れてくると 2 手 3 手程度の先読みはできるようになります。これがプロ棋士になると、十数手から二十手前後まで考えるというのですから驚きです。
ミニマックス法を使う場合でも、評価関数が適切なものであれば、ゲームの木を深く探索するほど正確な評価値を求めることができるようになります。ただし、木を深いレベルまで探索しようとすると、特に囲碁や将棋のような一つの局面で有効な指し手が多数あるゲームでは、木の枝が多数分岐するので、探索のために消費するメモリと時間が膨大なものになってしまいます。
これを防ぐために、あとで説明する「アルファベータ法」という方法を用いたり、ほかにもさまざまな工夫を行うことで無駄な木の探索を極力省くようにします。それでもハードウェアの限界により、ある程度のレベルで探索を打ち切ることになります。また、持ち時間が設定されている場合は、それも考慮して探索レベルを決める必要があります。
それでは、具体的にミニマックス法を説明しましょう。ここでは、簡単な仮想ゲームを考えてみます。このゲームは、先手後手とも指し手は常に 2 通りあって、そのうちの一つを選ぶことでゲームが進行します。
ミニマックス法を使う場合、局面の評価値が必要になります。評価関数は、先手が有利（後手が不利）な局面ほど大きな値（正の値）、逆に後手が有利（先手が不利）なほど小さな値（負の値）、互角の場合は 0 になるように作るのが一般的です。
探索のレベルは、先手−後手−先手の 3 手先まで読むことにします。先手の局面 R を探索すると、下図に示すゲームの木になりました。
Ｒ 先手の局面
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
Ａ(3) Ｂ(2) 後手の局面
／ ＼ ／ ＼
／ ＼ ／ ＼
Ｃ(3) Ｄ(4) Ｅ(2) Ｆ(5) 先手の局面
／ ＼ ／ ＼ ／ ＼ ／ ＼
Ｇ Ｈ Ｉ Ｊ Ｋ Ｌ Ｍ Ｎ 後手の局面
１ ３ ４ ２ ２ １ ３ ５ 評価値
図 : ミニマックス法
評価値は最も深いレベル、この場合は 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 手先までは読んでいたが、その先の手は読んでいなかった、ということです。これは私達がゲームをプレイする場合でもあることですね。
もしも、ゲームの木を最後まで探索できれば、最善手を指すことができます。たとえば、リバーシは終盤になると最後まで読み切ることが可能なゲームです。この状態になるとコンピュータは最善手を指してきます。コンピュータリバーシの得意技「終盤の大逆転」は、ゲームの木を最後まで読み切るからこそできることなのです。
次はアルファベータ法を説明します。ミニマックス法の説明では、木を全て探索するので 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) といい、そのとき基準になる値をアルファ値といいます。
この「アルファベータ法」がうまく働くと、局面を半分以上評価しないで済ますことができるようです。これは、実際にゲームを作ってその効果を確かめてみましょう。
それでは、例題として取り上げるゲーム「カラー (Kalah) 」を説明します。このゲームはルールこそ単純ですが、展開がスリリングで面白いゲームです。
後手側
12 11 10 ９ ８ ７
[ 6] [ 6] [ 6] [ 6] [ 6] [ 6]
後手の kalah [ 0] [ 0] 先手の kalah
[ 6] [ 6] [ 6] [ 6] [ 6] [ 6]
０ １ ２ ３ ４ ５
先手側
【注意】[n] は穴を示し n は石の数を表す
[n] に付いている数字は場所を表す
図 : カラーの盤面
上図に示すように、カラーの盤面は 6 個の穴が向かい合って並んでいます。左右にはカラー (kalah) と呼ばれる穴があり、右隣が自分のカラーです。初期状態では、各穴に 6 個ずつ石が入っていて 2 つのカラーは空の状態です。ゲームの目的は、自分のカラーに過半数以上の石を集めることです。
カラーは自分の穴の一つから石を全部取り出し、右隣の穴から反時計回りに石を一つずつ配っていくことで、ゲームを進めていきます。石を配るとき、自分のカラーには石を入れますが、相手のカラーには入れません。そして、最後の石が入る穴の位置によって、2 通りのスペシャルケースが発生します。
このドキュメントでは 2 番目のケースを「両取り」と呼ぶことにしましょう。これ以外の場合は、自分の番は終わり相手の番になります。それから、もう一つスペシャルケースがあり、自分の穴に石が無くなった場合は、相手の穴に残った石を全て相手のカラーに入れてゲームを終了します。
カラーは最大でも 6 通りの指し手しかないので、ゲームの木が簡単で扱いやすいこと、それから単純な評価関数でも探索レベルを増やすと相当に強くなること、などの理由からミニマックス法の枠組みによく当てはまります。例題にはちょうどよい思考ゲームなのです。
それでは、プログラムを作りましょう。最初に、盤面を表すクラスを定義します。
リスト : 盤面の定義
# 定数
SIZE = 14 # 盤面の大きさ
FIRST_KALAH = 6 # 先手、先手のカラーの位置
SECOND_KALAH = 13 # 後手、後手のカラーの位置
STONE = 72 # 石の個数
EVEN = STONE / 2
NORMAL = 0 # 通常の穴に入った場合
KALAH = 1 # KALAH に入った場合
GAMEOVER = 2 # ゲーム終了
# 盤面
class Board:
def __init__(self, b):
self.board = b[:]
def __getitem__(self, x):
return self.board[x]
def copy(self):
return Board(self.board)
クラス名は Board としました。盤面の実体は配列 (Python のリスト) で、インスタンス変数 board に格納します。穴との対応はルールの説明でも示したように、先手側の穴は左側から 0 - 5 でカラーの位置は FIRST_KALAH (6) になります。後手側の穴は反時計回りに 7 - 12 で、カラーの位置は SECOND_KALAH (13) になります。このように定義すると、穴に石を配るときには添字をひとつずつ増やしていけばいいので処理が簡単になります。FIRST_KALAH と SECOND_KALAH は手番を表すのにも使います。
メソッド __getitem__ は角カッコ [ ] で盤面の要素にアクセスするために定義します。メソッド copy は Board のオブジェクトをコピーするために使用します。
次は盤面を操作するメソッドを定義します。最初に、石を配るメソッド distribute を作ります。
リスト : 石を配る（終了位置を返す）
def distribute(self, turn, pos):
num = self.board[pos]
self.board[pos] = 0
while num > 0:
pos += 1
if pos == SIZE: pos = 0
if (turn == FIRST_KALAH and pos == SECOND_KALAH) or \
(turn == SECOND_KALAH and pos == FIRST_KALAH): continue
self.board[pos] += 1
num -= 1
return pos
この処理は簡単です。引数 turn は手番を、pos は石を取り出す穴の位置を表します。まず、pos 番目の穴にある石の数を変数 num にセットし、その穴を 0 にクリアします。あとは while ループで石を一つずつ配っていきます。pos が盤面の範囲を越えたら 0 に戻します。このとき、pos が相手のカラーでないことを確かめて、穴にある石の数を一つ増やしていきます。最後に配り終わった位置 pos を返します。
次は両取りのチェックを行う check_capture を作ります。
リスト : 両取りのチェック
def check_capture(self, turn, pos):
if (turn == FIRST_KALAH and 0 <= pos <= 5) or \
(turn == SECOND_KALAH and 7 <= pos <= 12):
if self.board[pos] == 1 and self.board[12 - pos] > 0:
# 両取りができる
num = self.board[12 - pos] + 1
self.board[turn] += num
self.board[pos] = 0
self.board[12 - pos] = 0
return True
return False
check_capture は両取りの条件をそのままコーディングしただけです。引数 turn は手番を、pos はチェックする穴の位置を表します。まず pos の条件をチェックします。turn が FIRST_KALAH であれば pos は 0 - 5 の範囲で、SECOND_KALAH であれば 7 - 12 の範囲であることを確認します。次に、pos の穴に石が一つあり、向かいの穴に石があることを確認します。向かいの穴の位置は 12 - pos で計算できます。
条件を満たしているのであれば、両取りする石の数を num にセットしてカラーに追加します。pos と向かいの穴は 0 にクリアして True を返します。両取りできない場合は False を返します。
次は、終了をチェックするメソッド check_gameover を作ります。
リスト : 終了チェック
# 穴にある石を数える
def count_stone(self, turn):
n = 0
for x in xrange(turn - 6, turn): n += self.board[x]
return n
# 石をカラーに入れる
def put_stone_into_kalah(self, turn):
n = 0
for x in xrange(turn - 6, turn):
n += self.board[x]
self.board[x] = 0
self.board[turn] += n
# 終了チェック
def check_gameover(self):
if self.count_stone(FIRST_KALAH) == 0:
self.put_stone_into_kalah(SECOND_KALAH)
return True
elif self.count_stone(SECOND_KALAH) == 0:
self.put_stone_into_kalah(FIRST_KALAH)
return True
elif self.board[FIRST_KALAH] > EVEN or \
self.board[SECOND_KALAH] > EVEN:
return True
return False
count_stone は turn 側の穴の石を数えるメソッドです。先手側の穴に石がなければ後手側にある石を全てカラーに入れます。逆に、後手側の石が無くなれば、先手側の石を全てカラーに入れます。put_stone_into_kalah は指定されたサイドの石を全てカラーに入れるメソッドです。それから、どちらかのカラーが過半数 EVEN (36)より多くの石が入っているならばゲーム終了です。ゲーム終了の場合は True を返し、そうでなければ False を返します。
これらのメソッドを使って、石を動かすメソッド move_stone を作ります。
リスト : 石を動かす
def move_stone(self, turn, pos):
pos = self.distribute(turn, pos)
self.check_capture(turn, pos)
if self.check_gameover(): return GAMEOVER
elif pos == turn: return KALAH
return NORMAL
引数 turn は手番を、pos は石を動かす穴の位置を表します。最初に、distribute で石を配る処理を行い、最後の石が入った穴の位置を pos にセットします。次に、check_capture を呼び出して両取りのチェックを行います。それから、ゲーム終了を判定する check_finish を呼び出します。
ゲーム終了の場合は GAMEOVER を返します。そうでなければ、最後の石がカラーに入ったかチェックします。turn はカラーの位置で表されているので、turn と pos が等しいのであれば、最後の石がカラーに入ったことがわかります。この場合は KALAH を返します。それ以外であれば NORMAL を返します。
それでは、ゲームの中心となるゲーム木の探索処理を作成します。カラーの場合、最後の石がカラーに入った場合の処理が少々厄介です。指し手は 1 手とは限らず、複数になる場合もあるからです。
この処理を繰り返しで実現しようとすると面倒なことになってしまいますが、再帰を使うとあっさりと実現できます。探索レベルと手番を変えずに、そのまま再帰するだけでいいのです。したがってゲーム木を作成する場合、交互に手番が移るときはゲーム木の高さと探索レベルは一致しますが、この処理が含まれるとゲームの木はいっきに高さを増すことになります。探索レベルが 2 の場合でも、お互いに最後の石がカラーに入る局面では、木の高さは 10 を越えることもあるでしょう。
あとは、石をカラーに入れたときの指し手を集めておけばいいわけです。指し手は配列に格納して返すことにしましょう。先手の指し手を求める関数を move_first、後手の指し手を求める関数を move_second とします。これらの関数は評価値と指し手の配列を返します。一般に、ミニマックス法で必要なのは評価値だけで、指し手はなくても動作するのですが、今回は指し手も返すことにします。
関数 move_first は次のようになります。
リスト : 思考ルーチン
# 定数
MAX_VALUE = 100 # 評価値の最大値
MIN_VALUE = -100 # 評価値の最小値
# 先手の指し手
def move_first(depth, board):
if depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in xrange(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
elif result == KALAH:
# 手番は同じまま
v, m = move_first(depth, b)
else:
# 後手番
v, _ = move_second(depth - 1, b)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
return value, move
引数 depth はゲーム木の探索レベルを表します。引数 board は現在の局面を表します。カラーのように、1 手指すたびに局面の大部分が変化するようなゲームでは、局面をコピーしてから石を動かして新しい局面を生成するといいでしょう。逆に、局面の一部分しか変化しないゲームでは、局面を直接書き換えて新しい局面を生成する方法が一般的です。 この場合、バックトラックするとき新しい局面から前の局面に戻す処理が必要になります。
depth が 0 になったとき、board の評価値を計算して返します。カラーの場合、評価関数は先手番のカラーと後手番のカラーの差 (board[FIRST_KALAH] - board[SECOND_KALAH]) としました。もしも、勝負がついている場合は FIRST_WIN (99) または SECOND_WIN (-99) を返します。とても単純な関数ですが、これでも十分に機能します。実際、探索レベルを上げると、M.Hiroi はほとんど勝てなくなります。評価値はメソッド value_func で計算し、その結果と空の配列を return で返します。
次に、ミニマックス法で指し手を求めます。変数 value は評価値を格納し、評価値の最小値 MIN_VALUE (-100) で初期化します。先手は評価値の高い手を選択するので、最初に調べた手は必ず選択されることになります。あとは、評価値を比較して、高い手を選択すればいいわけです。変数 move は選択した指し手を格納します。
次の for ループで、実際に石を動かして探索を行います。最初に pos の位置に石があるかチェックします。次に、局面をコピーしてから move_stone で石を動かし、その結果を result にセットします。result が GAMEOVER の場合は、value_func で評価値を計算して変数 v にセットします。
KALAH の場合は石が自分のカラーに入ったので、move_first を再帰呼び出しします。このとき、depth の値はそのままで、新しい局面 b を渡します。返り値は v と m に格納します。NORMAL の場合は、手番が後手に移るので、move_second を再帰呼び出しします。depth を -1 して局面 b を渡します。この場合、評価値だけが必要なので、指し手は無名変数 _ で受け取ります。
次の処理がミニマックス法の心臓部です。先手は評価値の大きい方が有利なわけですから、いちばん大きな評価値（マックス）の指し手を選びます。選んだ指し手は move に格納し、その評価値は value に格納しておきます。評価値 v が value よりも大きい値であれば、その指し手を選べばいいわけです。最後に return で value と move を返します。
次は後手の指し手を選ぶ関数 move_second を作ります。
リスト : 後手の指し手
def move_second(depth, board):
if depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in xrange(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
elif result == KALAH:
# 手番は同じまま
v, m = move_second(depth, b)
else:
# 先手番
v, _ = move_first(depth - 1, b)
# ミニマックス法 : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
return value, move
後手番の場合、先手とは逆にいちばん小さな評価値（ミニマム）の指し手を選択することに注意してください。変数 value は評価値の最大値 MAX_VALUE に初期化します。石がカラーに入った場合は move_second を再帰呼び出しして、カラー以外の穴に入った場合は move_first を再帰呼び出しします。そして、ミニマックス法では v が value よりも小さい場合に value と move の値を更新します。あとは、全ての指し手を調べるだけです。とても簡単ですね。
今度はゲームを進める処理を作成します。とりあえず、先手と後手どちらも同じ思考ルーチンを使って、探索レベルによって局面を評価する回数がどのくらい増えるのか確かめてみます。そのあとで、アルファベータ法と比較してみましょう。次のリストを見てください。
リスト : ゲームの実行
def play(first_depth, second_depth):
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
if turn == FIRST_KALAH:
value, move = move_first(first_depth, board)
else:
value, move = move_second(second_depth, board)
# 表示
for x in move:
print 'move', x
a = board.move_stone(turn, x)
board.print_board()
print
if a == GAMEOVER:
print 'Game Over'
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH
引数 first_depth は先手の探索レベル、second_depth は後手の探索レベルです。最初に初期状態の盤面を生成して変数 board にセットします。変数 turn は手番を表します。あとは while ループの中で思考ルーチンを呼び出してゲームを進めます。
思考ルーチンの返り値を value, move で受け取ります。そして、move から指し手を一つずつ取り出して、メソッド move_stone で石を動かします。盤面の表示はメソッド print_board で行います。あとは play を呼び出すだけです。
それでは実行結果を示します。
表 : 局面の評価回数 (ミニマックス法)
先手＼後手 : 2 : 3 : 4 : 5
----------------------------------------------------
2 : 41, 31 : 43, 17 : 26, 37 : 39, 33
: 11775 : 90968 : 318340 : 1221294
3 : 39, 23 : 40, 32 : 53, 19 : 48, 24
: 4383 : 41159 : 654559 : 588627
4 : 36, 36 : 43, 29 : 38, 34 : 44, 28
: 160765 : 131496 : 510241 : 1734092
5 : 23, 49 : 26, 39 : 43, 29 : 35, 37
: 3648321 : 1580529 : 2488362 : 4806261
上段 : 先手の石数, 後手の石数
下段 : 局面の評価回数
探索レベルを増やすと、局面を評価する回数は大幅に増加します。当然ですが、それだけ実行時間も長くなります。アルファベータ法を使うと、局面を評価する回数を大幅に減らすことができるので、実行時間も速くなります。
それではアルファベータ法のプログラムを作りましょう。ポイントは基準値（α値、β値）の管理です。プログラムは次のようになります。
リスト : 先手の指し手 (アルファベータ法)
def move_first(depth, board, limit):
if depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in xrange(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
elif result == KALAH:
# 手番は同じまま
v, m = move_first(depth, b, limit)
else:
# 後手番
v, _ = move_second(depth - 1, b, value)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# αβ法
if value >= limit: break
return value, move
引数 limit がアルファベータ法で使用する基準値です。この値は 1 手前の局面の評価値です。変数 value は評価値を格納します。これはミニマックス法と同じです。この値が次の局面（後手番）での基準値となります。
石を動かした結果が KALAH であれば move_first を再帰呼び出しします。このとき、depth だけではなく、limit もそのまま渡します。アルファベータ法では相手番の評価値が基準点になるので、この再帰処理では基準点として value を渡すのではなく、limit をそのまま渡すことに注意してください。
アルファベータ法の処理は簡単です。ミニマックス法で指し手を選択したあと、value が limit 以上の値になった時点で、for ループから break で抜けるだけです。value が limit よりも大きな値になった時点、つまり value > limit で枝刈りしても正常に動作しますが、value >= limit としたほうが効率よく枝刈りできるようです。まだ評価値が求まっていない場合、limit は 1 手前（後手番）の局面の評価値ですから MAX_VALUE がセットされています。MAX_VALUE より大きな評価値はないので、アルファベータ法により枝刈りが実行されることはありません。
後手の指し手を選ぶ関数 move_second は次のようになります。
リスト : 後手の指し手 (アルファベータ法)
def move_second(depth, board, limit):
if depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in xrange(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
elif result == KALAH:
# 手番は同じまま
v, m = move_second(depth, b, limit)
else:
# 先手番
v, _ = move_first(depth - 1, b, value)
# ミニマックス : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
# αβ法
if value <= limit: break
return value, move
先手 (move_first) とは逆に、後手 (move_second) の場合は value を MAX_VALUE で初期化します。これが評価値の中で最大の値となります。後手の場合、ミニマックス法では小さな値を選ぶので、最初に求めた評価値が無条件に選択されます。アルファベータ法の場合も先手とは逆に、vlaue が limit 以下の値になった時点で枝刈りを行えばいいわけです。
あとは、関数 play を修正します。プログラムは次のようになります。
リスト : ゲームの実行
def play(first_depth, second_depth):
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
if turn == FIRST_KALAH:
value, move = move_first(first_depth, board, MAX_VALUE)
else:
value, move = move_second(second_depth, board, MIN_VALUE)
# 表示
for x in move:
print 'move', x
a = board.move_stone(turn, x)
board.print_board()
print
if a == GAMEOVER:
print 'Game Over'
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH
注意する個所は、move_first を呼び出すとき、引数 limit には MAX_VALUE をセットし、move_second を呼び出すときは MIN_VALUE をセットするところだけです。プログラムの主な修正はこれだけです。
それでは、実行結果を示しましょう。ゲームの結果は、当然ですがミニマックス法とアルファベータ法で変わりはありません。アルファベータ法の効果を確かめるため、局面を評価した回数をカウントして比較してみましょう。アルファベータ法が有効に機能すれば、ミニマックス法よりも局面の評価回数は少なくなるはずです。結果は次のようになりました。
表 : 局面の評価回数
先手＼後手 : 2 : 3 : 4 : 5
----------------------------------------------------
2 : 11775 : 90968 : 318340 : 1221294
: 6207 : 40657 : 85880 : 226145
3 : 4383 : 41159 : 654559 : 588627
: 1757 : 11320 : 119750 : 65362
4 : 160765 : 131496 : 510241 : 1734092
: 30242 : 31230 : 111266 : 238004
5 : 3648321 : 1580529 : 2488362 : 4806261
: 504203 : 221814 : 505170 : 815589
上段 : ミニマックス法
下段 : アルファベータ法
結果を見ればおわかりのように、アルファベータ法の比較回数はミニマックス法の 1/2 から 1/9 程度になりました。カラーの場合、アルファベータ法の効果は極めて高いですね。それだけ実行時間も速くなります。
思考ゲームの基本である「ミニマックス法」と「アルファベータ法」を説明しました。今回説明したのは単純なアルファベータ法ですが、簡単な思考ゲームであれば、これだけでも十分な効果を発揮します。今まで M.Hiroi が作成した思考ゲーム (Tcl/Tk GUI Programming : Mini Games 2 [*1]) は、今回説明したミニマックス法とアルファベータ法が基本となっています。このほかにも、探索効率を上げるためのアルゴリズムが数多く提案されています。興味のある方は 参考文献 1, 2 を読んでみてください。
今回説明したように、ミニマックス法とアルファベータ法はけっして難しいアルゴリズムではありません。実は、思考ゲームのプログラミングで一番大変なのが「評価関数」の作成です。これはプログラムの作成が難しいというよりも、局面の評価方法を考えることが難しいのです。チェスや将棋に比べて囲碁のプログラムは弱いといわれていますが、これは精度の高い評価関数を作るのが非常に難しいからです。
思考ルーチンに興味を持たれた方は、まずリバーシから作ってみるといいでしょう。リバーシの評価関数はチェスや将棋に比べると比較的簡単なほうですが、それでも強い思考ルーチンを作るのは大変です。いろいろ試してみてください。リバーシには変形バージョンもありますので、そちらを作ってみるのも面白いと思います。
ミニマックス法で評価関数を修正しました。
アルファベータ法で枝刈りの条件を修正しました。
これにともない、アルファベータ法の評価結果を修正しました。
# coding: utf-8
#
# board.py : カラー 盤面の定義
#
# Copyright (C) 2007 Makoto Hiroi
#
# 定数
SIZE = 14 # 盤面の大きさ
FIRST_KALAH = 6 # 先手、先手のカラーの位置
SECOND_KALAH = 13 # 後手、後手のカラーの位置
STONE = 72 # 石の個数
EVEN = STONE / 2
MAX_VALUE = 100 # 評価値の最大値
MIN_VALUE = -100 # 評価地の最小値
FIRST_WIN = 99 # 先手勝ち
SECOND_WIN = -99 # 後手勝ち
NORMAL = 0 # 通常の穴に入った場合
KALAH = 1 # KALAH に入った場合
GAMEOVER = 2 # ゲーム終了
# 評価関数の呼び出し回数
count = 0
# 盤面
class Board:
def __init__(self, b):
self.board = b[:]
def __getitem__(self, x):
return self.board[x]
def copy(self):
return Board(self.board)
# 石を配る
def distribute(self, turn, pos):
num = self.board[pos]
self.board[pos] = 0
while num > 0:
pos += 1
if pos == SIZE: pos = 0
if (turn == FIRST_KALAH and pos == SECOND_KALAH) or \
(turn == SECOND_KALAH and pos == FIRST_KALAH): continue
self.board[pos] += 1
num -= 1
return pos
# 両取りのチェック
def check_capture(self, turn, pos):
if (turn == FIRST_KALAH and 0 <= pos <= 5) or \
(turn == SECOND_KALAH and 7 <= pos <= 12):
if self.board[pos] == 1 and self.board[12 - pos] > 0:
# 両取りができる
num = self.board[12 - pos] + 1
self.board[turn] += num
self.board[pos] = 0
self.board[12 - pos] = 0
return True
return False
# 穴にある石を数える
def count_stone(self, turn):
n = 0
for x in xrange(turn - 6, turn): n += self.board[x]
return n
# 石をカラーに入れる
def put_stone_into_kalah(self, turn):
n = 0
for x in xrange(turn - 6, turn):
n += self.board[x]
self.board[x] = 0
self.board[turn] += n
# 終了チェック
def check_gameover(self):
if self.count_stone(FIRST_KALAH) == 0:
self.put_stone_into_kalah(SECOND_KALAH)
return True
elif self.count_stone(SECOND_KALAH) == 0:
self.put_stone_into_kalah(FIRST_KALAH)
return True
elif self.board[FIRST_KALAH] > EVEN or \
self.board[SECOND_KALAH] > EVEN:
return True
return False
# 石を動かす
def move_stone(self, turn, pos):
pos = self.distribute(turn, pos)
self.check_capture(turn, pos)
if self.check_gameover(): return GAMEOVER
elif pos == turn: return KALAH
return NORMAL
# 評価関数
def value_func(self):
global count
count += 1
n1 = self.board[FIRST_KALAH]
n2 = self.board[SECOND_KALAH]
if n1 > EVEN: return FIRST_WIN
if n2 > EVEN: return SECOND_WIN
return n1 - n2
# 盤面の表示
def print_board(self):
print ' ',
for x in xrange(12, 6, -1):
print '%2d' % self.board[x],
print
print '%2d' % self.board[13],
print ' ' * 6,
print '%2d' % self.board[6]
print ' ',
for x in xrange(0, 6):
print '%2d' % self.board[x],
print
# debug 用
def print_count(): print count
# coding: utf-8
#
# kalah.py : カラー (ミニマックス法)
#
# Copyright (C) 2007 Makoto Hiroi
#
from board import *
# 思考ルーチン
# 先手の指し手
def move_first(depth, board):
if depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in xrange(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
elif result == KALAH:
# 手番は同じまま
v, m = move_first(depth, b)
else:
# 後手番
v, _ = move_second(depth - 1, b)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
return value, move
# 後手の指し手
def move_second(depth, board):
if depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in xrange(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
elif result == KALAH:
# 手番は同じまま
v, m = move_second(depth, b)
else:
# 先手番
v, _ = move_first(depth - 1, b)
# ミニマックス法 : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
return value, move
# ゲームの実行
def play(first_depth, second_depth):
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
if turn == FIRST_KALAH:
value, move = move_first(first_depth, board)
else:
value, move = move_second(second_depth, board)
# 表示
for x in move:
print 'move', x
a = board.move_stone(turn, x)
board.print_board()
print
if a == GAMEOVER:
print 'Game Over'
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH
# 実行
play(2, 2)
print_count()
# coding: utf-8
#
# kalah1.py : カラー (アルファベータ法)
#
# Copyright (C) 2007 Makoto Hiroi
#
from board import *
# 思考ルーチン
# 先手の指し手
def move_first(depth, board, limit):
if depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in xrange(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
elif result == KALAH:
# 手番は同じまま
v, m = move_first(depth, b, limit)
else:
# 後手番
v, _ = move_second(depth - 1, b, value)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
# αβ法
if value >= limit: break
return value, move
# 後手の指し手
def move_second(depth, board, limit):
if depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in xrange(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == GAMEOVER:
v = b.value_func()
elif result == KALAH:
# 手番は同じまま
v, m = move_second(depth, b, limit)
else:
# 先手番
v, _ = move_first(depth - 1, b, value)
# ミニマックス : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
# αβ法
if value <= limit: break
return value, move
# 実行
def play(first_depth, second_depth):
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
if turn == FIRST_KALAH:
value, move = move_first(first_depth, board, MAX_VALUE)
else:
value, move = move_second(second_depth, board, MIN_VALUE)
# 表示
for x in move:
print 'move', x
a = board.move_stone(turn, x)
board.print_board()
print
if a == GAMEOVER:
print 'Game Over'
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH
# 実行
play(2, 2)
print_count()