2

三目並べAIをAlphaBeta法で実装しています.
三目並べは以下のサイトを参考にしており,Minimax法で実装されていますが,それをAlphaBeta法に変更しました.

https://github.com/koki0702/tictactoe-ai-youtube

AlphaBeta法はMinimax法の上位互換であり,計算量を少なくしたアルゴリズムであることから,同じ手を打ってくることを期待しているのですが,結果が異なってしまっています.

どのサイトを見ても解決できず,お力をお借りしたいです.よろしくお願いします.

ソースコードを以下に示します.

mainプログラム

import Board as b
import NPC
import PLAYER

board = b.Board()
players = [NPC.AplhaBeta(0), PLAYER.HumanPlayer(1)]
# players = [NPC.MiniMax(0), PLAYER.HumanPlayer(1)]
player = 1 # 0 or 1

while True:
    p = players[player]
    p.play(board)
    board.render()

    if board.is_win(player):
        break
    elif board.is_end():
        print("引き分け")
        break

    player = 1 if player == 0 else 0

Boardクラス

import copy

class Board:
    def __init__(self) -> None:
        self.state = [-1] * 9   #置かれている種類(O or X)
        self.count = 0

    def render(self):
        MARKS = {0: 'X', 1: 'O'}
        text = """
                0|1|2
                -----
                3|4|5
                -----
                6|7|8
                """
        for idx, x in enumerate(self.state):
            if x is not -1:
                text = text.replace(str(idx), MARKS[x])  # 4 -> X
        print(text)

    def put(self, player, idx):
        if self.state[idx] != -1 or (not(0 <= idx <= 8)):
            return False

        self.state[idx] = player
        self.count += 1
        return True

    def take(self, idx):
        self.count -= 1
        self.state[idx] = -1

    def is_win(self, player):
        s = self.state
        if(
            s[0] == s[1] == s[2] == player or
            s[3] == s[4] == s[5] == player or
            s[6] == s[7] == s[8] == player or
            s[0] == s[3] == s[6] == player or
            s[1] == s[4] == s[7] == player or
            s[2] == s[5] == s[8] == player or
            s[0] == s[4] == s[8] == player or
            s[2] == s[4] == s[6] == player
        ):
            return True
        return False

    def eva_value(self, player):
        opp = 0 if player == 1 else 1
        if self.is_win(player):
            return 1
        elif self.is_win(opp):
            return -1
        else:
            return 0

    def is_end(self):
        if -1 in self.state:
            return False
        
        return True

    def valid_puts(self):
        puts = []   #置ける候補
        for idx, player in enumerate(self.state):
            if player == -1:
                puts.append(idx)
        return puts

    def board_result(self, idx):
        tmp = copy.deepcopy(self)
        n_player = tmp.next_player()
        tmp.put(n_player, idx)
        return tmp

    def next_player(self):
        # 0...先行f, 1...後攻s
        state = self.state
        f = s = 0
        if self.count == 0:
            return 0
        
        for p in state:
            if p == 0:
                f += 1
            elif p == 1:
                s += 1

        if f == s:
            return 0
        elif f > s:
            return 1
        else:
            return -1

NPCクラス #このプログラムにMiniMaxとAlphaBetaがあります

import random
import Board3x3 as bo

def main():
    board = bo.Board()
    cpu = AplhaBeta(0)

    # score ,idx = alphabeta(board, cpu.player, cpu.depth, float('-inf'), float('inf'))

    board.put(0,8)
    board.put(1,4)
    board.put(0,7)
    board.put(1,6)

    # score ,idx = alphabeta(board, cpu.player, cpu.depth, float('-inf'), float('inf'))
    score ,idx = minimax(board, 0)

    print(score, idx)

class RandomPlay:
    def __init__(self , player):
        self.player = player

    def play(self, board):
        idx = random.randint(0,15)
        return board.put(self.player, idx), idx

def minimax(board, player):
    maximize_player = 0
    minimize_player = 1

    if board.is_win(maximize_player):
        return (1, None)
    elif board.is_win(minimize_player):
        return (-1, None)
    elif board.is_end():
        return (0, None)

    opp = 1 if player == 0 else 0

    if player == maximize_player:
        max_score = float('-inf')
        max_idx = None

        for idx in board.valid_puts():
            board.put(player, idx)
            score, next_idx = minimax(board, opp)
            if max_score < score:
                max_score = score
                max_idx = idx
            board.take(idx)
        
        return (max_score, max_idx)
    else:
        min_score = float('inf')
        min_idx = None

        for idx in board.valid_puts():
            board.put(player, idx)
            score, next_idx = minimax(board, opp)
            if min_score > score:
                min_score = score
                min_idx = idx
            board.take(idx)
        
        return (min_score, min_idx)

def alphabeta(board, player, depth, alpha, beta):
    # print("depth = ",depth)
    maximize_player = 0
    minimize_player = 1

    # print(depth)

    if board.is_win(maximize_player):
        return (1, None)
    elif board.is_win(minimize_player):
        return (-1, None)
    elif board.is_end() or depth == 0:
        return (0, None)
    

    opp = 1 if player == 0 else 0

    if player == maximize_player:
        for put in board.valid_puts():
            score, next_idx = alphabeta(board.board_result(put), opp, depth-1, alpha, beta)
            alpha = max(alpha, score)
            if alpha >= beta:
                break
            next_idx = put
        return alpha, next_idx

    else:
        for put in board.valid_puts():
            score, next_idx = alphabeta(board.board_result(put), opp, depth-1, alpha, beta)
            beta = min(beta, score)
            if alpha <= beta:
                break
            next_idx = put
        return beta, next_idx


class MiniMax:
    def __init__(self, player):
        self.player = player
    
    def play(self, board):
        score, idx = minimax(board, self.player, )
        return board.put(self.player,idx), idx

class AplhaBeta:
    def __init__(self , player):
        self.player = player
        self.depth = float('inf')
        self.depth = 7

    def play(self, board):
        score ,idx = alphabeta(board, self.player, self.depth, float('-inf'), float('inf'))
        # idx = alphabeta(board, self.player, self.depth, -500, 500)
        return board.put(self.player, idx), idx

if __name__ == "__main__":
    main()

PLAYERクラス

class Player:
    def __init__(self, player):
        self.player = player

    def play(self, board, idx):
        return board.put(self.player, idx)


class HumanPlayer:
    def __init__(self, player):
        self.player = player
        
    def play(self, board):
        while True:
            print('0~8の数字を入力してください:', end="")
            idx = input()

            try:
                idx = int(idx)
                success = board.put(self.player, idx)
                if success:
                    break
                else:
                    print("適切な数字を入力してください")
            except ValueError:
                pass

1 件の回答 1

1

提示された alphabeta() の動作を読み解けなかったので,minimax() を基に修正する形の記述例を示します。なお,アルファ・ベータ法の記述についてはウィキペディアの擬似コードを参考にしましたが,minimax()depth を使わずに終端を処理をしているので同様にしました。

def alphabeta(board, player, alpha, beta):
    maximize_player = 0
    minimize_player = 1

    if board.is_win(maximize_player):
        return (1, None)
    if board.is_win(minimize_player):
        return (-1, None)
    if board.is_end():
        return (0, None)

    opp = 1 if player == 0 else 0

    if player == maximize_player:
        max_score = float('-inf')
        max_idx = None
        for idx in board.valid_puts():
            board.put(player, idx)
            score, _ = alphabeta(board, opp, alpha, beta)
            if score > max_score:
                max_score = score
                max_idx = idx
            board.take(idx)
            alpha = max(alpha, score)
            if alpha >= beta:
                break
        return (max_score, max_idx)
    else:
        min_score = float('inf')
        min_idx = None
        for idx in board.valid_puts():
            board.put(player, idx)
            score, _ = alphabeta(board, opp, alpha, beta)
            if score < min_score:
                min_score = score
                min_idx = idx
            board.take(idx)
            beta = min(beta, score)
            if alpha >= beta:
                break
        return (min_score, min_idx)
class AlphaBeta:
    def __init__(self , player):
        self.player = player

    def play(self, board):
        _, idx = alphabeta(board, self.player,
                           float('-inf'), float('inf'))
        return board.put(self.player, idx), idx

また,「初手からの対戦」と「初手(9種類)固定からの対戦」の計10戦(自動対戦)を,下記の組み合わせで行い同じ手順と結果が得られることを確認しました。一方,処理時間についてはアルファ・ベータ法を使うことで 1/10以下になりました(環境: macOS13.1(M1), Python 3.10.8)。

players = [NPC.MiniMax(0), NPC.MiniMax(1)]
players = [NPC.MiniMax(0), NPC.AlphaBeta(1)]
players = [NPC.AlphaBeta(0), NPC.MiniMax(1)]
players = [NPC.AlphaBeta(0), NPC.AlphaBeta(1)]

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。