Day7 Alpha-Beta Pruning
===
昨天分享了如果是較為複雜的遊戲，可以使用審局函數來限制Minimax的搜索深度，好讓我們的程式停下來。但是搜索深度通常會直接引響到程式的棋力，搜索得愈深通常也會愈強，要想在相同時間內搜索得更深，那就得升級硬體設備了，沒有什麼是花錢解決不了的。
> 什麼？你說升級太貴了？


以上純屬開玩笑，這是我的缺點。
身為軟體人當然要用寫程式解決，今天要使用Alpha-Beta Pruning演算法來優化我們的程式。

## Alpha-Beta Pruning
Alpha-Beta Pruning(Alpha-Beta剪枝)是一種搜索演算法，為了改進Minimax Algorithm而產生的，用來減少Minimax產生的對局樹節點數。在很多時候Minimax對局樹展開是相當費時的，所以我們應該要盡可能的減少不必要的節點展開。當演算法計算出某節點的後續走法比之前節點的還差時，就會停止計算該節點的後續子節點。這樣可以省去搜索那些沒有機會的節點，把搜索時間用在更有希望的子樹上，提升單位時間的搜索深度。

> 不要跟他拼硬體，嘗試切他節點。


Alpha-Beta Pruning在原本的Minimax Algorithm新增加了兩個參數，α跟β，α記錄max層的目前的最大值，β記錄min層目前的最小值。兩個參數以交錯的方式向下層傳遞，當我們在max層取最大值的時候發現了一個大於等於β的值，就不用再對其他分支進行搜索，此剪枝稱為β cut。當我們在min層取最小值的時候發現了一個小於等於α的值，一樣也不用再對其他分支進行搜索，此剪枝稱為α cut。

以下圖為例，此圖為一個深度優先由左至右拜訪的對局樹。


當搜索至D節點時，更新C節點的值為4，小於此時的α值5，發生α cut。此時C節點若再繼續往其它子節點搜尋，C節點的值也只會小於等於4，位於max層的A節點會選擇最大的子節點B節點。
所以不管結果如何，C節點的結果都不會改變A節點的值了。此時我們就可以把E節點給剪掉，C節點剩下的子節點都可以不必再搜索了。
當搜索至I節點時，更新H節點的值為6，小於等於此時的α值6，發生α cut，所以一樣把J節點給剪掉不必再搜了。
當M節點更新為8時，8大於等於此時的β值3，發生β cut，所以將M節點剩下的子節點都剪掉。


## 實作
這邊比起昨天就只是需要多去維護`alpha`跟`beta`兩個參數，程式寫起來也非常簡單，幾乎沒有什麼改變。

def alpha_beta_pruning(board, depth, current_player, maximizing_player, alpha, beta):
    """
    board: 棋盤狀態
    depth: 目前遞迴深度
    current_player: 當前回合玩家 ('X' 或 'O')
    maximizing_player: 最大化玩家 ('X' 或 'O')
    alpha: 紀錄max層的下限值
    beta: 紀錄min層的上限值
    """
    winner = board.check_winner()
    if winner is not None:
        if winner == maximizing_player:
            return 1
        elif winner == 'Draw':
            return 0
        else:
            return -1
        
    if depth == 10:
        return evaluate(board)

    opponent = 'O' if current_player == 'X' else 'X'

    if current_player == maximizing_player:  # max層
        best_score = -float('inf')
        for move in board.get_available_moves():
            board.set_move(move, current_player)
            score = minimax(board, depth + 1, opponent, maximizing_player, alpha, beta) 
            board.undo_move(move)
            best_score = max(score, best_score)
            alpha = max(alpha, best_score)  # 更新 alpha
            if beta <= alpha:  # Beta 剪枝
                break
        return best_score
    else:  # min層
        best_score = float('inf')
        for move in board.get_available_moves():
            board.set_move(move, current_player)
            score = minimax(board, depth + 1, opponent, maximizing_player, alpha, beta)
            board.undo_move(move)
            best_score = min(score, best_score)
            beta = min(beta, best_score)  # 更新 beta
            if beta <= alpha:  # Alpha 剪枝
                break
        return best_score

如果是井字遊戲的話那就更簡單了，甚至不需要使用`alpha`、`beta`做為參數傳遞下去，因為他的狀態很單純就是只有1、0、-1。
我們只需要找到一種勝利的方式，不用找出全部，在Max層中只要找到其中一個子節點能獲勝，就可以直接`break`不再繼續搜索其他分支了，反之亦然。

def alpha_beta_pruning(board, depth, current_player, maximizing_player):
    """
    board: 棋盤狀態
    depth: 目前遞迴深度
    current_player: 當前回合玩家 ('X' 或 'O')
    maximizing_player: 最大化玩家 ('X' 或 'O')
    """
    winner = board.check_winner()
    if winner is not None:
        if winner == maximizing_player:
            return 1
        elif winner == 'Draw':
            return 0
        else:
            return -1
    
    if depth == 10:
        return evaluate(board)
    
    oppenent = 'O' if current_player == 'X' else 'X'

    if current_player == maximizing_player:  # max層
        best_score = -float('inf')
        for move in board.get_available_moves():
            board.set_move(move, current_player)
            score = alpha_beta_pruning(board, depth + 1, oppenent, maximizing_player)
            board.undo_move(move)
            if score == 1:
                break
            best_score = max(score, best_score)
    else:  # min層
        best_score = float('inf')
        for move in board.get_available_moves():
            board.set_move(move, current_player)
            score = alpha_beta_pruning(board, depth + 1, oppenent, maximizing_player)
            board.undo_move(move)
            if score == -1:
                break
            best_score = min(score, best_score)
    return best_score

### Negamax + Alpha-Beta Pruning
如果是Negamax的版本一樣可以使用Alpha-Beta Pruning，這邊只需要注意`alpha`跟`beta`也要跟著做交換。

def negamax(board, depth, player, maximizing_player, alpha, beta):
    winner = board.check_winner()
    if winner is not None:
        if winner == maximizing_player:
            return 1
        elif winner == 'Draw':
            return 0
        else:
            return -1
        
    if depth == 10:
        return evaluate(board)

    best_score = -float('inf')
    oppenent = 'O' if player == 'X' else 'X'
    
    for move in board.get_available_moves():
        board.set_move(move, player)
        score = -negamax(board, depth + 1, oppenent, maximizing_player, -beta, -alpha)
        board.undo_move(move)
        best_score = max(score, best_score)

    return best_score

## 結論
使用Alpha-Beta Pruning可以提早剪去較差的分支，剪掉的分支愈多，單位時間能搜索的深度就能夠愈深，後續幾天會再分享更多種的剪枝。