はじめに
こんにちは、アビネクです。
今回はミニマックス法というアルゴリズムについての解説とそれを用いた実例をご紹介します。
pythonで実際にコーディングもしていくので、ぜひ最後までお楽しみください。
ミニマックス法とは
ミニマックス法を一言で表すと「総当たり戦略」です。
もう少し具体的に申し上げますと、以下の流れに沿って決定を行っていきます。
- すべての可能な行動をリストアップします
- それぞれの行動に対して、スコアを付与します
- そのスコアを基に各行動がもたらす結果を予測します
- 最も高いスコアを得られる行動を選択します
このアルゴリズムは主に二人零和ゲーム（例：チェス、囲碁、オセロなど）で使用されます。ここで「零和ゲーム」とは、一方のプレイヤーの得点がもう一方のプレイヤーの失点となるゲームを意味します。ミニマックス法は、相手が自分にとって最も不利な手を選んでくることを前提に、自分にとって最も有利な手を選択する戦略です。
ミニマックス法の仕組み
具体的な例を使ってミニマックス法の仕組みを見てみましょう。今回、取り扱うゲームはシンプルな3x3の三目並べ（マルバツゲーム）です。
ステップ1: すべての可能な行動をリストアップする
まず、プレイヤー（X）が最初の一手を打つとしましょう。盤上に9つの空きマスがあるため、最初の一手には9通りの可能性があります。
ステップ2: それぞれの行動にスコアを付与する
ここでは全ての可能な行動ごとに、その後の展開をシミュレーションします。例えば、Xが中央のマスに打った場合、次の手として相手（O）がどこに置くかを考慮します。このように、各手の結果を逐次評価していきます。
ステップ3: 結果を予測する
すべての可能な手とその先の結果を評価した後、その結果に基づいてスコアを計算します。勝ちの手には高得点、負けの手には低得点を与えます。当然、その間に引き分けとなる手も評価します。
ステップ4: 最も高いスコアを得られる行動を選択する
最後に、得られた各行動のスコアを比較し、最も高いスコアを持つ行動を選びます。こうすることで、Xは自分が勝つ可能性が最も高い手を選択できます。
ミニマックス法コード
以下が三目並べのためのミニマックス法のコードです。
import random
class Ai:
# prototype for the AI class
def __init__(self, sign):
self.sign = sign
self.opponent_sign = 'O' if sign == 'X' else 'X'
def get_next_action(self, board):
pass
class MinimaxAi(Ai):
# the MinimaxAi class
def get_next_action(self, board):
# ミニマックス法で最適な手を選択
best_score = -float('inf')
best_action = None
# 行動パターンを全て評価するループ
for i in range(3):
for j in range(3):
if board[i][j] == '':
board[i][j] = self.sign
score = self.minimax(board, False)
board[i][j] = ''
if score > best_score:
best_score = score
best_action = (i, j)
return best_action
def minimax(self, board, is_maximizing):
# すでに勝負がついている場合はその結果を返す
winner = self.check_winner(board)
if winner == self.sign:
return 1
elif winner == self.opponent_sign:
return -1
elif self.is_board_full(board):
return 0
if is_maximizing:
# 自身が行動したときの評価
best_score = -float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == '':
board[i][j] = self.sign
score = self.minimax(board, False)
board[i][j] = ''
best_score = max(score, best_score)
return best_score
else:
# 相手が行動したときの評価
best_score = float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == '':
board[i][j] = self.opponent_sign
score = self.minimax(board, True)
board[i][j] = ''
best_score = min(score, best_score)
return best_score
def check_winner(self, board):
# 勝敗確認
for i in range(3):
if board[i][0] == board[i][1] == board[i][2] != '':
return board[i][0]
if board[0][i] == board[1][i] == board[2][i] != '':
return board[0][i]
if board[0][0] == board[1][1] == board[2][2] != '':
return board[0][0]
if board[0][2] == board[1][1] == board[2][0] != '':
return board[0][2]
return None
def is_board_full(self, board):
return all(all(cell != '' for cell in row) for row in board)
100行程度で実装できました！
こちらのコードを活用する、三目並べのゲームを実装します。
本記事の本質とはズレるので省略しますが、ゲームのコードに興味のある方はこちらのレポジトリをご確認ください。
実際に遊んでみる
それでは上で実装したゲームを遊んでみます。
バツが人間、丸がAIです。
まずは人間から動きます。
次はAIです。
一番いいところに置いてきましたね。
次に左下に置きました。これに対し、AIはそれに対してこちらの勝利を防ぐ行動を取りました。
想定通りです！
これを続けて最終的に以下の状態で引き分けになりました。
対戦してみた感想
何回かプレイしましたが、どれも引き分けに持ち込まれました。（気を抜いたところで一回負けてしまいました😅）
完全に人間相手にプレイしていると言われても違和感がないレベルです。
弱点だと感じたのは、序盤では探索する行動パターンの数が多いせいか、１〜２秒程度静止した点です。
マルバツゲームの行動パターンの数は850あるそうです。
チェスや将棋はもっと探索範囲が広くなるわけですので、実際にプロのプレイヤーと対戦するとなると、相当な計算資源が必要になります。それを補うために、深さ制限やアルファベータカットオフといった手法が活用されます。これにより、探索範囲を制限しつつも、効率的な手を見つけることが可能になります。
アルゴリズムの改良: アルファベータカットオフ
ミニマックス法の改善策として、アルファベータカットオフがあります。これは、探索中に必要のない部分を早期に切り捨てる方法です。具体的には以下の通りです。
- 探索の途中で得られた最低限のスコア（アルファ）を保存します。
- 同様に、最大限のスコア（ベータ）も保存します。
- あるノードのスコアがアルファよりも小さく、またはベータよりも大きくなると、そのサブツリーの探索を停止します。
こうして、計算量を大幅に削減し、より早く最適な手を見つけることができます。この改良により、例えばチェスのような複雑なゲームでも現実的な時間内に有力な手を探索することが可能となります。
結論
ミニマックス法とその改良手法であるアルファベータカットオフは、二人零和ゲームにおける戦略的意思決定の重要なツールです。これらのアルゴリズムを理解し実装することで、複雑なゲームにおいても強力な対戦相手に立ち向かうことが可能となります。
ミニマックス法を理解し、自分なりの改良を加えることで、より効果的な戦略を練るための堅固な基盤が築かれます。これを機に、さまざまなゲームやシミュレーションに挑戦し、さらに深く掘り下げてみると良いと感じました。
今後の展望
さらに効率的なアルゴリズムの開発や、他の分野への応用も視野に入れ、ミニマックス法の理解を深めていきます。
例えば、機械学習や経済学、さらにはリアルタイム戦略ゲームなど、多岐にわたる分野での活用が期待されています。そのため、次回以降の記事では、これらの応用例についても詳しく解説していく予定です。お楽しみに！