

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

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

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

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

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

mainプログラム

[code]

    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
    
[/code]

Boardクラス

[code]

    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
    
[/code]

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

[code]

    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()
    
[/code]

PLAYERクラス

[code]

    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
    
[/code]


CC BY-SA 4.0
2022-12-25T05:27:28.220
92999
2022-12-31T06:59:31.703
2022-12-26T01:41:23.747
3060
56203
question
python アルゴリズム
三目並べのAIをAlphaBeta法で実装したが，MiniMax法と同じ動作をしてくれない


提示された `alphabeta()` の動作を読み解けなかったので，`minimax()`
を基に修正する形の記述例を示します。なお，アルファ・ベータ法の記述についてはウィキペディアの[擬似コード](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E3%83%BB%E3%83%99%E3%83%BC%E3%82%BF%E6%B3%95)を参考にしましたが，`minimax()`
が `depth` を使わずに終端を処理をしているので同様にしました。

[code]

    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)
    
[/code]

[code]

    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
    
[/code]

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

[code]

    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)]
    
[/code]


CC BY-SA 4.0
2022-12-31T06:41:37.010
93118
2022-12-31T06:59:31.703
2022-12-31T06:59:31.703
54588
54588
92999
answer