【Pygame】アルファ・ベータ法で敵CPUを強化したオセロゲームを作成

Pygameとアルファ・ベータ法で敵CPUを強化したオセロゲームを作成する方法をソースコード付きで詳しく解説します。

アルファ・ベータ法で敵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