今回はゲームで用いられる探索アルゴリズムの一つであるMini-Max法とその発展系であるαβ法について学習していきます。
Mini-Max法
Mini-Max法の概要
Mini-Max法はゲームの中で手を決定するための手法の一つです。ゲームといっても、シューティングゲームや格闘ゲームなどではなく、オセロやチェスといった2人で交互に手を指すようなゲームで用いられます。MIni-Max法を理解し、実装できるようになることで、簡単なゲームでAIの敵を実装したり、定量的な手の決定ができるようになるので、楽しみながら学習していきましょう。
Mini-Max法を使うことができるゲームとゲーム木
Mini-Max法はゲーム木を探索していく中で特定の決まりにしたがって次に指す手を決めるアルゴリズムです。ゲーム木を探索する上で深さ優先探索という探索アルゴリズムを使用します。深さ優先探索の学習がまだな方はぜひこちらの記事（リンク埋め込む）から一度学習してみてください！
はじめに、Mini-Max法を使用することができるゲームについて説明します。Mini-Max法は2人で交互に手をさすオセロやチェスのようなゲームで使用することができます。なぜなら、このようなゲームはゲーム木と呼ばれる木構造を使用してゲームの盤面を表すことができるからです。
ではゲーム木とはどのようなものなのかを具体的に見ていきましょう。まずは、簡単な2人でできるゲームを考えます。今回は三目並べ（3×3の⚪︎×ゲーム）を使用します。ある段階から三手先までの盤面の状態は次のような木構造で表すことができます。
このようにゲームの盤面の推移を木構造として表したものをゲーム木やゲームの木といいます。この記事（リンクを埋め込む）で深さ優先探索・幅優先探索を学習した方は馴染み深いデータ構造ですね。
評価関数
Mini-Max法は特定の指標にしたがって次に指す手を選択します。その時に使用する指標が評価関数です。例えば、下の図の×の番の手を⚪︎が有利になればなるほど数値が大きくなるという基準の評価関数を用いて評価します。図のように⚪︎が必ず勝つ真ん中の手がもっも評価関数の値が大きくなっているのがわかります。
評価関数は多くの場合、経験に基づいて決められます。例えば将棋の場合は、それぞれの駒に点数を割り振り、その重み付き和にするなどです。
評価関数=飛車の点数×駒数+角の点数×駒数+…
このように評価関数はある基準に沿ってどちらかのプレイヤーが有利になれば値が大きくなるように設定されている必要があり、定め方はゲームによって様々となっています。
具体例で学ぶMini-Max法
ここから実際にゲーム木を探索し、Mini-Max法を用いて手を決定していきます。ここでのスコアは緑が有利なほど高くなるとします（つまり緑は高い方: maxを選び、紫は低い方: minを選ぶ）。まずは下のようなゲーム木を考えます。一番末端のノードで評価関数が計算されています。
それでは順に手を見ていきましょう。Mini-Max法では深さ優先探索で木を探索するので、まずはA→B→Dと進んでいきます。末端のHとIでは評価関数の値が計算できているので、どちらのノードかを選ぶことができます。ここで、Dは最大値を選ぶ時なので評価関数の値の大きいIを選びます。これでDの評価関数の値が5に決まります。
同様にしてA→B→Eの分岐も探索します。先ほどと同様にしてEの評価関数の値が10に決まります。ここで、DとEの評価関数の値が出揃ったので、どちらのノードを選ぶかを決めます。Bは最小値を選ぶ時なので、Dを選びます。ここでBの評価関数の値が5に決まります。
Bの評価関数を決めるまでと全く同じプロセスでCの評価関数も決めます。するとCの評価関数の値は3に決まりました。ここでようやくAからBとCのどちらのノードを選べばいいのかを決めることができます。Aは最大値を選ぶ時なのでBを選びます。
このように相手がお互いの邪魔をする＝自分にとって最善の手を打つという仮定のもと評価関数の大小から次に移動するノードを決定する手法がMini-Max法です。
Pythonで三目並べAIを作ってみる
今回はMini-Max法を用いて手を決定するコンピュータの敵を実装したいと思います。まずは、三目並べを進めるためのメソッドや変数をまとめたクラスを実装していきます。このクラスには、Mini-Max法に直接は関係ありませんが、勝敗判定や指す手を決定するといったメソッドが含まれています。もし、興味がある方や余力のある方はコードを眺めてみてください。
デフォルトのコード
from enum import Enum, auto
# ゲームの勝敗を管理するためのクラス
class GameState(Enum):
DRAW = auto()
ON = auto()
OVER = auto()
# 盤の印を管理するためのクラス
class Mark(Enum):
X = auto()
O = auto()
EMPTY = auto()
# 盤の状態全体を管理するクラス
class Board:
# 盤を初期化するメソッド
def __init__(self):
self.cell = [[Mark.EMPTY for i in range(3)] for j in range(3)]
self.is_first_player = True
# 現在のゲームの状態（決着がついたか進行中か）を判定するメソッド
def state(self):
if self.won():
return GameState.OVER
elif len(self.possible_moves()) == 0:
return GameState.DRAW
else:
return GameState.ON
# 現在置くことができる場所を取得するメソッド
def possible_moves(self):
moves = []
for i in range(3):
for j in range(3):
if self.cell[i][j] == Mark.EMPTY:
moves.append((i, j))
return moves
# 指定された場所に印をつけるメソッド
def make_move(self, move):
# make a move
if self.cell[move[0]][move[1]] == Mark.EMPTY:
if self.is_first_player:
self.cell[move[0]][move[1]] = Mark.X
else:
self.cell[move[0]][move[1]] = Mark.O
self.is_first_player = not self.is_first_player
# 印が３つそろったかを判定するメソッド
def won(self):
# 指定された場所から指定された方向に3つの印がそろっているかを判定する関数
def check_cells(x, y, dx, dy):
if self.cell[x][y] == Mark.EMPTY:
return False
for i in range(3):
if self.cell[x][y] != self.cell[x + i * dx][y + i * dy]:
return False
return True
for i in range(3):
# 垂直方向にチェック
if check_cells(i, 0, 0, 1):
return True
# 水平方向にチェック
if check_cells(0, i, 1, 0):
return True
# 対角方向にチェック
if check_cells(0, 0, 1, 1):
return True
if check_cells(0, 2, 1, -1):
return True
# 指定した場所の印を空欄にする（手を巻き戻す）メソッド
def rewind(self, move):
# rewind the board
self.cell[move[0]][move[1]] = Mark.EMPTY
self.is_first_player = not self.is_first_player
# 盤面を表示する特殊メソッド
# print(object自身)で呼ばれる
def __str__(self):
board_str = ""
for i in range(3):
for j in range(3):
if self.cell[i][j] == Mark.X:
board_str += "X"
elif self.cell[i][j] == Mark.O:
board_str += "O"
else:
board_str += "/"
board_str += "\\n"
return board_str
board = Board()
print(board)
次はこのクラスを使って実際に三目並べを行なってみます。まずそれぞれのプレイヤーにはMini-Max法で手を選択するのではなく、ランダムに手を選択させてみます。
デフォルトのコード
import random
from enum import Enum, auto
# ゲームの勝敗を管理するためのクラス
class GameState(Enum):
DRAW = auto()
ON = auto()
OVER = auto()
# 盤の印を管理するためのクラス
class Mark(Enum):
X = auto()
O = auto()
EMPTY = auto()
# 盤の状態全体を管理するクラス
class Board:
# 盤を初期化するメソッド
def __init__(self):
self.cell = [[Mark.EMPTY for i in range(3)] for j in range(3)]
self.is_first_player = True
# 現在のゲームの状態（決着がついたか進行中か）を判定するメソッド
def state(self):
if self.won():
return GameState.OVER
elif len(self.possible_moves()) == 0:
return GameState.DRAW
else:
return GameState.ON
# 現在置くことができる場所を取得するメソッド
def possible_moves(self):
moves = []
for i in range(3):
for j in range(3):
if self.cell[i][j] == Mark.EMPTY:
moves.append((i, j))
return moves
# 指定された場所に印をつけるメソッド
def make_move(self, move):
# make a move
if self.cell[move[0]][move[1]] == Mark.EMPTY:
if self.is_first_player:
self.cell[move[0]][move[1]] = Mark.X
else:
self.cell[move[0]][move[1]] = Mark.O
self.is_first_player = not self.is_first_player
# 印が３つそろったかを判定するメソッド
def won(self):
# 指定された場所から指定された方向に3つの印がそろっているかを判定する関数
def check_cells(x, y, dx, dy):
if self.cell[x][y] == Mark.EMPTY:
return False
for i in range(3):
if self.cell[x][y] != self.cell[x + i * dx][y + i * dy]:
return False
return True
for i in range(3):
# 垂直方向にチェック
if check_cells(i, 0, 0, 1):
return True
# 水平方向にチェック
if check_cells(0, i, 1, 0):
return True
# 対角方向にチェック
if check_cells(0, 0, 1, 1):
return True
if check_cells(0, 2, 1, -1):
return True
# 指定した場所の印を空欄にする（手を巻き戻す）メソッド
def rewind(self, move):
# rewind the board
self.cell[move[0]][move[1]] = Mark.EMPTY
self.is_first_player = not self.is_first_player
# 盤面を表示する特殊メソッド
# print(object自身)で呼ばれる
def __str__(self):
board_str = ""
for i in range(3):
for j in range(3):
if self.cell[i][j] == Mark.X:
board_str += "X"
elif self.cell[i][j] == Mark.O:
board_str += "O"
else:
board_str += "/"
board_str += "\\n"
return board_str
board = Board()
# ゲーム終了まで無限ループ
while True:
# ゲームの終了を判定する
if board.state() == GameState.OVER or board.state() == GameState.DRAW:
break
print("先手" if board.is_first_player else "後手")
next_move = random.choice(board.possible_moves())
board.make_move(next_move)
print(board)
これで三目並べをPythonで実装することができましたね！次はいよいよMini-Max法を用いて手の選択をするコンピュータを実装していきます。まずはMini-Max法を実行する関数minimaxを見ていきましょう。今回は簡単のため評価関数の設計を省略します。具体的には評価関数の値を途中の盤面の状態から決めるのではなく、完全なゲーム木を描き、最終的な勝敗から評価関数の値を決定します。したがって、全ての手について評価関数の値を求めるループになっています。評価関数の値は勝った場合が1、負けた場合が -1、引き分けの場合が0としています。ループの中での処理では大きく次のような処理を行なっています。
- もし勝敗がついているならば、結果に応じて評価関数の値を決定する
- 勝敗がついていないならば、その時点から指せる全ての手に対して、手を指してみて評価関数の値が決まるかを調べる
- 調べた手の評価関数の値が暫定値よりも大きければ更新
- 実際に調べた手を指すわけでは無いので、指した手を戻す
特に2番の部分が再帰的な処理となっていて、理解しずらいと思います。この時のポイントが次の手のチェックに移るときに、関数の返り値であるscoreの符号を反転して返してもらうようにしています。この理由を具体的な盤面を使って説明していきます。
# mini-max法を再帰的に実装するための関数
def minimax(board):
# 評価関数の値
# 引き分け: 0
# 負け: -1
# 勝ち: 1
if board.state() == GameState.DRAW:
return 0
# 1が無いのは、次の手の評価関数を計算するときに符号を反転させるため
elif board.state() == GameState.OVER:
return -1
best_score = -math.inf
# 全ての可能な手について評価関数を計算
for move in board.possible_moves():
board.make_move(move)
# 自分が勝つ: 1, 相手が勝つ: -1だから、符号を反転させると
# 最小値を求める処理無しでMini-Max法を実装できる
score = -minimax(board)
# 次のループのために、手を戻す
board.rewind(move)
if score > best_score:
best_score = score
return best_score
具体的な盤面で関数の動きを見てみましょう。次のような盤面を考えます。xの番の一手を選択する場面です。
まずはAのノードのスコアを決める場面を見てみましょう。DとEの評価関数が求まりましたが、今回の関数の中でAからはDのスコアが-1、Eのスコアが0といったように、それぞれ-1をかけたスコアに見えています。このようにしているのは、Mini-Max法の評価関数の最大値の選択と最小値の選択が交互に現れる部分を、最大値の選択一つだけで表現するためです。今回のように評価関数に対称性（”勝ち: 1″に-1をかけると”負け: -1″になる）があるときは最小値計算を省略できるというテクニックです。
では実際にランダムな手を選択するプレイヤー: oとMini-Max法を用いるプレイヤー: xを対戦させてみます。各手に対する評価関数の値も表示しているので、ちゃんとMini-Max法が実行されていることを確認してみてください。
デフォルトのコード
import math
import random
from enum import Enum, auto
# ゲームの勝敗を管理するためのクラス
class GameState(Enum):
DRAW = auto()
ON = auto()
OVER = auto()
# 盤の印を管理するためのクラス
class Mark(Enum):
X = auto()
O = auto()
EMPTY = auto()
# 盤の状態全体を管理するクラス
class Board:
# 盤を初期化するメソッド
def __init__(self):
self.cell = [[Mark.EMPTY for i in range(3)] for j in range(3)]
self.is_first_player = True
# 現在のゲームの状態（決着がついたか進行中か）を判定するメソッド
def state(self):
if self.won():
return GameState.OVER
elif len(self.possible_moves()) == 0:
return GameState.DRAW
else:
return GameState.ON
# 現在置くことができる場所を取得するメソッド
def possible_moves(self):
moves = []
for i in range(3):
for j in range(3):
if self.cell[i][j] == Mark.EMPTY:
moves.append((i, j))
return moves
# 指定された場所に印をつけるメソッド
def make_move(self, move):
# make a move
if self.cell[move[0]][move[1]] == Mark.EMPTY:
if self.is_first_player:
self.cell[move[0]][move[1]] = Mark.X
else:
self.cell[move[0]][move[1]] = Mark.O
self.is_first_player = not self.is_first_player
# 印が３つそろったかを判定するメソッド
def won(self):
# 指定された場所から指定された方向に3つの印がそろっているかを判定する関数
def check_cells(x, y, dx, dy):
if self.cell[x][y] == Mark.EMPTY:
return False
for i in range(3):
if self.cell[x][y] != self.cell[x + i * dx][y + i * dy]:
return False
return True
for i in range(3):
# 垂直方向にチェック
if check_cells(i, 0, 0, 1):
return True
# 水平方向にチェック
if check_cells(0, i, 1, 0):
return True
# 対角方向にチェック
if check_cells(0, 0, 1, 1):
return True
if check_cells(0, 2, 1, -1):
return True
# 指定した場所の印を空欄にする（手を巻き戻す）メソッド
def rewind(self, move):
# rewind the board
self.cell[move[0]][move[1]] = Mark.EMPTY
self.is_first_player = not self.is_first_player
# 盤面を表示する特殊メソッド
# print(object自身)で呼ばれる
def __str__(self):
board_str = ""
for i in range(3):
for j in range(3):
if self.cell[i][j] == Mark.X:
board_str += "X"
elif self.cell[i][j] == Mark.O:
board_str += "O"
else:
board_str += "/"
board_str += "\\n"
return board_str
# mini-max法を再帰的に実装するための関数
def minimax(board):
# 評価関数の値
# 引き分け: 0
# 負け: -1
# 勝ち: 1
if board.state() == GameState.DRAW:
return 0
# 1が無いのは、次の手の評価関数を計算するときに符号を反転させるため
elif board.state() == GameState.OVER:
return -1
best_score = -math.inf
# 全ての可能な手について評価関数を計算
for move in board.possible_moves():
board.make_move(move)
# 次の手は相手の手なので、符号を反転させる
score = -minimax(board)
# 次のループのために、手を戻す
board.rewind(move)
if score > best_score:
best_score = score
return best_score
board = Board()
while True:
if board.state() == GameState.OVER or board.state() == GameState.DRAW:
break
print("先手" if board.is_first_player else "後手")
best_score = -math.inf
best_move = None
# 先手の場合はmini-max法を用いて最善手を選択する
if board.is_first_player:
# 全ての可能な手について評価関数を計算し，最大の評価関数を持つ手を選択する
move_dict = {}
for move in board.possible_moves():
board.make_move(move)
score = -minimax(board)
move_dict[move] = score
board.rewind(move)
if score > best_score:
best_score = score
best_move = move
next_move = best_move
print(move_dict)
else:
# 後手の場合はランダムに手を選択する
next_move = random.choice(board.possible_moves())
board.make_move(next_move)
print(board)
何度対戦しても、ランダムな手を選択するoのプレイヤーは勝てなくなりました。Mini-Max方が機能しているのを実感できましたか？次はαβ法を解説していきます。
αβ法
αβ法の概要
αβ法はMini-Max法の計算量を削減した手法といえます。したがって、ゲーム木を探索して、評価関数の値によって手を決定するという方針はMini-Max法と同じです。大きく違うのは、ゲーム木をどこまで探索するかという部分です。Mini-Max法ではゲーム木を深さ優先探索で全探索していました。しかし、実際には手の決定には不必要なノードまで探索してしまっています。このような不必要なノードの探索をカットしたのがαβ法です。では、具体的なケースを見てみましょう。
具体例で学ぶαβ法
ゲーム木を見ながらαβ方でゲーム木の枝刈りを行う様子を見てみましょう。まず、下のようなゲーム木を考えます。
ここからMini-Max法と同様に深さ優先探索で木を探索していきます。まずは、Bのノードを探索しにいきましょう。
ここでのαは探索中の自分から見た最善のスコアで、βは一つ下の最善のスコアです。HとIの二つのノードを探索し終わると、ひとまずαの値が5に決まります。すると、一つ上のβの値も5に決まります。では次のEのノードを探索しにいきましょう。
Eの最善のスコアを決めるためには、まずJを見ます。すると暫定のαが6に決まります。Bノードでは最小値を求めるので、隣のDの最善スコアである5以下にしかBの最善スコアはなりません。ここで隣のDの最善スコアはEにはβとして渡されていますので、αがβを超えた時点でEからの探索はする必要がないということになります。これはスコアが最小な手を選ぶ場面で、現在の最小スコアより大きいスコアが出た時点で探索を終了するという処理をしており、βカットと呼ばれます。これでBのスコアを確定することができたので、次はCを探索しにいきましょう。
Cに移動した後にFのスコアが確定した後をみます。ここまででCのαは5、βは3になります。A→Cの場面ではスコアが最大の手を選択します。そしてC→F or Gの場面ではスコアが最小の手を選択します。つまり、Fのスコアが3ならば、Gのスコアは3以下にしかなりません。しかし、3以下のスコアならば、Bのスコアが5に確定している以上、5以上にならなければ選択されないのでCが選択される可能性は無くなります。したがって、Cにぶら下がっているノードはこれ以上探索する必要がなくなります。これは、スコアが最大の手を選択する場面で、それより小さいスコアが出た時点で探索を終了するという処理をしており、αカットと呼ばれます。このようにβカットとαカットを行いながらMini-Max法を行う手の選択アルゴリズムをαβ法といいます。
AIにαβ法で手を選択させる
では実際にPythonでαβ法を使用して三目並べをプレーするAIを作っていきます。ゲームを進める上での基本的なクラスはそのままです。必要なのは手を選択するための関数です。この関数も大部分はMini-Max法を行うものと同様ですが、αカット、βカットを行う上で二つのポイントがあります。
- αとβを入れ替えて次のノードの渡す
- スコアの符号を反転させて受け取る
まず、一つ目のポイントについてはαが現在探索中のノードから見た最善手のスコアであり、βが一つ下のノードの最善手のスコアであることを表現するために行なっています。そして二つ目は、Mini-Max法と同様にスコアの対象性を利用して最小値計算を省略するために行なっています。
# alpha-beta法を再帰的に実装するための関数
def alpha_beta(board, alpha, beta):
if board.state() == GameState.DRAW:
return 0
elif board.state() == GameState.OVER:
return -1
# 現在のノードから選択可能な全ての手について評価関数を計算
for move in board.possible_moves():
board.make_move(move)
# minimax法と同じように、符号を反転させることで最小値計算を省略
# alphaは自分の最善手の評価値
# betaは一つ下のノードの最善手の評価値
# 木が一つ深くなると、alphaとbetaの値が入れ替わる
score = -alpha_beta(board, alpha=-beta, beta=-alpha)
if score > alpha:
alpha = score
board.rewind(move)
# alphaよりもbetaが小さいなら、そのノードはalphaよりも大きい値を持つことはないので、
# 現ノードと並列なノード（同じ親を持つノード）を探索する必要はない
if alpha >= beta:
return alpha
return alpha
関数だけではイメージしずらい部分をαカットの様子を具体例でみていきましょう。下のような盤面を考えます。Aのスコアが0に決まった後Bを見にいきます。するとFのスコアが-1でBのβが-1になります。この時点でBの探索は終了です。同様にCも途中でカットすることができます。
最後に、αβ法を用いてランダムに手を選択するプレイヤーと対戦してみます。Mini-Max法の時と比べ実行時間が短くなったことがわかります。
デフォルトのコード
import random
import math
from enum import Enum, auto
class GameState(Enum):
DRAW = auto()
ON = auto()
OVER = auto()
class Mark(Enum):
X = auto()
O = auto()
EMPTY = auto()
class Board:
def __init__(self):
self.cell = [[Mark.EMPTY for i in range(3)] for j in range(3)]
self.is_first_player = True
def state(self):
if self.won():
return GameState.OVER
elif len(self.possible_moves()) == 0:
return GameState.DRAW
else:
return GameState.ON
def possible_moves(self):
moves = []
for i in range(3):
for j in range(3):
if self.cell[i][j] == Mark.EMPTY:
moves.append((i, j))
return moves
def make_move(self, move):
if self.cell[move[0]][move[1]] == Mark.EMPTY:
if self.is_first_player:
self.cell[move[0]][move[1]] = Mark.X
else:
self.cell[move[0]][move[1]] = Mark.O
self.is_first_player = not self.is_first_player
def won(self):
def check_cells(x, y, dx, dy):
if self.cell[x][y] == Mark.EMPTY:
return False
for i in range(3):
if self.cell[x][y] != self.cell[x + i * dx][y + i * dy]:
return False
return True
for i in range(3):
if check_cells(i, 0, 0, 1):
return True
if check_cells(0, i, 1, 0):
return True
if check_cells(0, 0, 1, 1):
return True
if check_cells(0, 2, 1, -1):
return True
def rewind(self, move):
self.cell[move[0]][move[1]] = Mark.EMPTY
self.is_first_player = not self.is_first_player
def __str__(self):
board_str = ""
for i in range(3):
for j in range(3):
if self.cell[i][j] == Mark.X:
board_str += "X"
elif self.cell[i][j] == Mark.O:
board_str += "O"
else:
board_str += "/"
board_str += "\\n"
return board_str
# alpha-beta法を再帰的に実装するための関数
def alpha_beta(board, alpha, beta):
if board.state() == GameState.DRAW:
return 0
elif board.state() == GameState.OVER:
return -1
# 現在のノードから選択可能な全ての手について評価関数を計算
for move in board.possible_moves():
board.make_move(move)
# minimax法と同じように、符号を反転させることで最小値計算を省略
# alphaは自分の最善手の評価値
# betaは一つ下のノードの最善手の評価値
# 木が一つ深くなると、alphaとbetaの値が入れ替わる
score = -alpha_beta(board, alpha=-beta, beta=-alpha)
if score > alpha:
alpha = score
board.rewind(move)
# alphaよりもbetaが小さいなら、そのノードはalphaよりも大きい値を持つことはないので、
# 現ノードと並列なノード（同じ親を持つノード）を探索する必要はない
if alpha >= beta:
return alpha
return alpha
board = Board()
while True:
if board.state() == GameState.OVER or board.state() == GameState.DRAW:
break
print("先手" if board.is_first_player else "後手")
# best_score = -math.inf
best_move = None
alpha = -math.inf
# 先手の場合はalpha-beta法を用いて最善手を選択する
if board.is_first_player:
# 全ての可能な手について評価関数を計算し，最大の評価関数を持つ手を選択する
move_dict = {}
for move in board.possible_moves():
board.make_move(move)
score = -alpha_beta(board, alpha=-math.inf, beta=-alpha)
move_dict[move] = score
board.rewind(move)
if score > alpha:
best_move = move
alpha = score
next_move = best_move
print(move_dict)
else:
# 後手の場合はランダムに手を選択する
next_move = random.choice(board.possible_moves())
board.make_move(next_move)
print(board)
まとめ
今回はMini-Max法とαβ法を通して、機械学習を用いない、より原始的なAIを学びました。これらのアルゴリズムは今回例として扱った三目並べだけでなく、記事内で説明した仮定に基づくものであれば、さまざまなゲームに応用することができます。ぜひ、皆さんでさまざまなゲームのAIを作ってみてみましょう。
