【Pygame】ミニマックス法で敵CPUを強化したオセロゲームを作成

Pygameとミニマックス法で敵CPUを強化したオセロゲームを作成する方法をソースコード付きで詳しく解説します。

ミニマックス法で敵CPUを強化したオセロゲームを作成
サンプルコード
サンプルコードの解説
関連ページ

ミニマックス法で敵CPUを強化したオセロゲームを作成

ミニマックス法（minimax法）は、主に2人対戦型のゲームで最適な手を見つけるための方法です。

ミニマックス法では、N手先まで読みをする時、相手のターンでは自分にとって一番不利な手を選びます。
そして、自分のターンでは自分にとって一番有利な手を選びます。これをN手先まで繰り返し行い、最終的に自分のターンで最も有利になる手を選びます。

今回は、ミニマックス法を使って白側（敵CPU）を強化する方法を説明します。

ミニマックス法のステップ

オセロゲームを例にミニマックスアルゴリズムのステップを解説します。

ゲームツリーの探索
- ゲームツリーとは、現在のボード状態から可能なすべての手を展開していったものです。
- 各ノード（点）はボードの状態を表し、枝（線）は手の選択を表します。
再帰的な探索
- ミニマックスアルゴリズムは、再帰的にゲームツリーを探索します。
- つまり、ある手を選んだ後、その次の手も同様に最適な手を探していきます。
評価値の計算：
- 各ノードでボードの状態を評価し、評価値を計算します。評価値は、白の石の数から黒の石の数を引いたものです。

最大化と最小化のプレイヤー

最大化プレイヤー（白）
- 白のターンでは、白が有利になるように評価値を最大化しようとします。つまり、白の石の数が増えるような手を選びます。
- 具体的には、白のターンで白が置けるすべての位置を試し、それぞれの手について評価値を計算します。その中で最も高い評価値を持つ手を選びます。
- (例)白が置ける位置A、B、Cがあるとします。それぞれの位置に置いた場合の評価値を計算します。位置Aの評価値が5、位置Bの評価値が3、位置Cの評価値が7だとすると、白は評価値が最も高い位置Cを選びます。
最小化プレイヤー（黒）
- 黒のターンでは、黒が有利になるように評価値を最小化しようとします。つまり、白の石の数が減るような手を選びます。
- 具体的には、黒が置けるすべての位置を試し、それぞれの手について評価値を計算します。その中で最も低い評価値を持つ手を選びます。
- (例)黒が置ける位置D、E、Fがあるとします。それぞれの位置に置いた場合の評価値を計算します。位置Dの評価値が2、位置Eの評価値が4、位置Fの評価値が1だとすると、黒は評価値が最も低い位置Fを選びます。

相手のターンではmin（最小）、自分のターンではmax（最大）を選ぶことから、ミニマックス法（minimax法）と呼ばれています。

サンプルコード

サンプルコードの解説

cpu_moveメソッドの修正
- CPU側の次手をランダムでなく、ミニマックスアルゴリズムを使用して、すべての有効な手を試し、最も高い評価値を持つ手を選びます。
minimaxメソッド
- 再帰的にゲームツリーを探索し、評価値を計算します。
- is_maximizing が True の場合は最大化、False の場合は最小化を行います。
evaluate_boardメソッド
- 現在のボード状態を評価し、白と黒の石の数の差を返します。

cpu_moveメソッドの解説

cpu_moveメソッドは、敵CPU（白側）がミニマックスアルゴリズムを使用して最適な手を見つけています。

def cpu_move(self):
    best_score = float('-inf')
    best_move = None
    for x in range(BOARD_SIZE):
        for y in range(BOARD_SIZE):
            if self.is_valid_move(x, y):
                self.board[x][y] = WHITE
                score = self.minimax(0, False)
                self.board[x][y] = None
                if score > best_score:
                    best_score = score
                    best_move = (x, y)
    if best_move:
        self.next_move(best_move[0], best_move[1])

以下で、各部分を詳しく解説します。

1. 初期化

best_score = float('-inf')
best_move = None

best_score は、最適な手の評価値を保持するための変数です。初期値は負の無限大に設定されています。
best_move は、最適な手の座標を保持するための変数です。初期値は None です。

2. すべてのボード位置をチェック

for x in range(BOARD_SIZE):
    for y in range(BOARD_SIZE):

ボード上のすべての位置 (x, y) をチェックするための二重ループです。

3. 有効な手の確認

if self.is_valid_move(x, y):

現在の位置 (x, y) が有効な手かどうかを確認します。is_valid_move 関数は、その位置に石を置けるかどうかを判定します。

4. 仮の手を置く

self.board[x][y] = WHITE

仮に白の石を (x, y) に置きます。

5. ミニマックスアルゴリズムの評価

score = self.minimax(0, False)

ミニマックスアルゴリズムを使って、この仮の手の評価値を計算します。minimax 関数は、再帰的にゲームツリーを探索し、評価値を返します。
0 は深さを示し、False は次のターンが相手（黒）であることを示します。

6. 仮の手を元に戻す

self.board[x][y] = None

仮の手を元に戻し、ボードを元の状態に戻します。

7. 最適な手の更新

if score > best_score:
    best_score = score
    best_move = (x, y)

現在の手の評価値が best_score よりも高い場合、best_score と best_move を更新します。

8. 最適な手を実行

if best_move:
    self.next_move(best_move[0], best_move[1])

最適な手が見つかった場合、その手を実行します。next_move 関数は、指定された位置に石を置き、必要な石をひっくり返し、ターンを切り替えます。

minimaxメソッドの解説

minimaxメソッドは、再帰的にゲームツリーを探索し、各ノードの評価値を計算します。
最大化プレイヤー（白）のターンでは評価値を最大化し、最小化プレイヤー（黒）のターンでは評価値を最小化します。

def minimax(self, depth, is_maximizing):
    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)
                    self.board[x][y] = None
                    max_eval = max(max_eval, eval)
        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)
                    self.board[x][y] = None
                    min_eval = min(min_eval, eval)
        return min_eval

1. 終端条件のチェック

if depth == 3 or not self.has_valid_move():
    return self.evaluate_board()

depth == 3：再帰の深さが3に達した場合、探索を終了します。深さの制限を設けることで、計算量を制御します。
not self.has_valid_move()：有効な手がない場合、探索を終了します。
self.evaluate_board()：現在のボード状態を評価し、その評価値を返します。

2. 最大化プレイヤーの処理

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)
                self.board[x][y] = None
                max_eval = max(max_eval, eval)
    return max_eval

is_maximizing が True の場合、最大化プレイヤー（白）のターンです。
max_eval を負の無限大に初期化します。
ボード上のすべての位置 (x, y) をチェックし、有効な手がある場合、その位置に仮に白の石を置きます。
再帰的に minimax 関数を呼び出し、次のターン（相手のターン）の評価値を計算します。
仮の手を元に戻します。
max_eval を更新し、最大の評価値を保持します。

3. 最小化プレイヤーの処理

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)
                self.board[x][y] = None
                min_eval = min(min_eval, eval)
    return min_eval

is_maximizing が False の場合、最小化プレイヤー（黒）のターンです。
min_eval を正の無限大に初期化します。
ボード上のすべての位置 (x, y) をチェックし、有効な手がある場合、その位置に仮に黒の石を置きます。
再帰的に minimax 関数を呼び出し、次のターン（相手のターン）の評価値を計算します。
仮の手を元に戻します。
min_eval を更新し、最小の評価値を保持します。

evaluate_boardメソッドの解説

evaluate_boardメソッドは、現在のボード状態を評価し、白と黒の石の数の差を計算して返します。
この評価値を使って、ミニマックスアルゴリズムが最適な手を選ぶ際の基準とします。評価値が高いほど白に有利な状態を示し、低いほど黒に有利な状態を示します。

def evaluate_board(self):
    black_count = sum(row.count(BLACK) for row in self.board)
    white_count = sum(row.count(WHITE) for row in self.board)
    return white_count - black_count

1. 黒の石の数をカウント

black_count = sum(row.count(BLACK) for row in self.board)

self.board は、オセロのボードを表す2次元リストです。
row.count(BLACK) は、各行に含まれる黒の石の数をカウントします。
sum(...) は、すべての行の黒の石の数を合計します。
結果として、ボード上の黒の石の総数が black_count に格納されます。

2. 白の石の数をカウント

white_count = sum(row.count(WHITE) for row in self.board)

黒の石のカウントと同様に、白の石の数をカウントします。
row.count(WHITE) は、各行に含まれる白の石の数をカウントします。
sum(...) は、すべての行の白の石の数を合計します。
結果として、ボード上の白の石の総数が white_count に格納されます。

3. 評価値の計算

return white_count - black_count

白の石の数から黒の石の数を引いた値を返します。
この評価値は、白の石が多いほど高くなり、黒の石が多いほど低くなります。

まとめ

ミニマックスアルゴリズムは、深さを3とした場合、CPU側は以下のように3手先までのパターンを試し、3ターン後に「白の石数 – 黒の石数」が最も大きくなる次手を選んでいます。

3手先までのすべてのパターンを試す
- 現在のボード状態から、白と黒が交互に手を打つ3手先までのすべての可能な手を探索します。
評価値の計算
- 各終端ノード（3手先のボード状態）で、白の石の数から黒の石の数を引いた評価値を計算します。
最適な手の選択
- 白のターンでは、評価値（白の石数 – 黒の石数）を最大化する手を選びます。CPUは自分の手を最大化しようとしますが、人が最適な手を選ぶことを前提にしているため、最小化プレイヤーの処理が必要です。
- 黒のターンでは、人（黒側）で最適な手を選ぶと仮定し、評価値（白の石数 – 黒の石数）を最小化する手を選びます。これにより、CPU（白側）は人が選ぶ可能性のある最悪のシナリオを考慮に入れて、自分の手を選びます。