Pygameとアルファ・ベータ法で敵CPUを強化したオセロゲームを作成する方法をソースコード付きで詳しく解説します。
アルファ・ベータ法で敵CPUを強化したオセロゲームを作成
アルファ・ベータ法(αβ法)は、2人対戦型のゲームで最適な手を見つけるための方法です。
前回の記事「【Pygame】ミニマックス法で敵CPUを強化したオセロゲームを作成」で用いたミニマックス法の探索効率を向上させるために開発されたのが、アルファ・ベータ法です。
今回は、前回の記事で解説したコードアルファ・ベータ法を使ったものに改良し、白側(敵CPU)を強化する方法を説明します。
アルファ・ベータ法の概要
- アルファ・ベータ剪定:
- アルファ・ベータ法は、ミニマックス法の探索効率を向上させるために、不要な部分木の探索を省略する技法です。これを「枝刈り」と呼びます。
- アルファ値(α)は、現在の局面で考えられる最小限の損失を示します。α以上の損失が確定した場合、その先の探索を省略します(αカット)。
- ベータ値(β)は、現在の局面で考えられる最大限の利益を示します。β以下の利益が確定した場合、その先の探索を省略します(βカット)。
アルファ・ベータ法の利点
- 効率的な探索: 不要な探索を省略することで、計算量を大幅に削減し、探索の効率を向上させます。
- 高速な意思決定: 枝刈りにより、より短時間で最善の手を見つけることができます。
サンプルコード
サンプルコードの解説
前回の記事「【Pygame】ミニマックス法で敵CPUを強化したオセロゲームを作成」で解説したサンプルコードのminimax
メソッドにアルファベータ剪定を追加し、cpu_move
メソッドで最適な手を選ぶ際に使用しています。これにより、探索の効率が向上し、CPUの思考時間が短縮されます。
def minimax(self, depth, is_maximizing, alpha, beta):
if depth == 3 or not self.has_valid_move():
return self.evaluate_board()
if is_maximizing:
max_eval = float('-inf')
for x in range(BOARD_SIZE):
for y in range(BOARD_SIZE):
if self.is_valid_move(x, y):
self.board[x][y] = WHITE
eval = self.minimax(depth + 1, False, alpha, beta)
self.board[x][y] = None
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break
return max_eval
else:
min_eval = float('inf')
for x in range(BOARD_SIZE):
for y in range(BOARD_SIZE):
if self.is_valid_move(x, y):
self.board[x][y] = BLACK
eval = self.minimax(depth + 1, True, alpha, beta)
self.board[x][y] = None
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break
return min_eval
- minimax(self, depth, is_maximizing, alpha, beta):
- depth: 現在の探索の深さを示します。再帰的に呼び出されるたびに1ずつ増加します。
- is_maximizing: 現在のプレイヤーが最大化プレイヤー(ここでは白)かどうかを示します。
- alpha: 最大化プレイヤーのための最良の評価値。
- beta: 最小化プレイヤーのための最良の評価値。
以下に各部分の詳細を説明します。
基本的な動作
- 終了条件のチェック:
if depth == 3 or not self.has_valid_move(): return self.evaluate_board()
- 探索の深さが3に達するか、有効な手がない場合、現在のボードの評価値を返します。
- 最大化プレイヤーの処理:
if is_maximizing: max_eval = float('-inf') for x in range(BOARD_SIZE): for y in range(BOARD_SIZE): if self.is_valid_move(x, y): self.board[x][y] = WHITE eval = self.minimax(depth + 1, False, alpha, beta) self.board[x][y] = None max_eval = max(max_eval, eval) alpha = max(alpha, eval) if beta <= alpha: break return max_eval
- max_eval: 最大化プレイヤーのための最良の評価値を初期化します。
- ボード上の全ての位置をチェックし、有効な手がある場合、その手を試します。
- 再帰的に
minimax
を呼び出し、評価値を計算します。 - alphaを更新し、betaと比較します。beta以下の場合、探索を打ち切ります(枝刈り)。
- 最小化プレイヤーの処理:
else: min_eval = float('inf') for x in range(BOARD_SIZE): for y in range(BOARD_SIZE): if self.is_valid_move(x, y): self.board[x][y] = BLACK eval = self.minimax(depth + 1, True, alpha, beta) self.board[x][y] = None min_eval = min(min_eval, eval) beta = min(beta, eval) if beta <= alpha: break return min_eval
- min_eval: 最小化プレイヤーのための最良の評価値を初期化します。
- ボード上の全ての位置をチェックし、有効な手がある場合、その手を試します。
- 再帰的に
minimax
を呼び出し、評価値を計算します。 - betaを更新し、alphaと比較します。alpha以上の場合、探索を打ち切ります(枝刈り)。
【Pygame】アルファ・ベータ法で敵CPUを強化したオセロゲームを作成
Pygameとアルファ・ベータ法で敵CPUを強化したオセロゲームを作成する方法をソースコード付きで詳しく解説します。
関連ページ
Pygameの使い方については以下ページで解説しています。
【Pygame超入門】使い方とサンプルゲームを解説
Pygameで2Dゲームを簡単に制作する方法を入門者向けに解説します。
Python全般については以下ページで解説しています。
【Python超入門】使い方とサンプル集
Pythonの基礎文法から応用例まで入門者向けに解説します。
コメント