Day5 Minimax Algorithm
===
昨天有說到很多遊戲其實都沒辦法在有限的時間(甚至是有生之年)暴力破解，所以我們今天用最簡單的井字遊戲作為示範，並且會帶著大家實作出來。

## 如何選點？
在我們把整顆對局樹給展開來之後，接下來就是要知道如何獲勝，**選出獲勝的葉節點**，但是這邊又會衍生出新的問題。
下圖為部分分支展開的示意圖，**我們可以看到A節點為 X 獲勝的盤面，有些人可能看到就會很開心的認為這是通往勝利的分支，所以就選擇了左邊分支的下法。**


乍看似乎很合理，但再仔細看就會發現這條路徑中 O 應對方式明顯不是最佳， O 是有辦法可以擋住 X 的，**雖然這條路徑結局是贏的，但對方並不會乖乖配合演出，這樣該怎麼判斷哪條路徑才是真的能夠贏呢？**

## Minimax Algorithm
跟單人對局還有解謎遊戲不同，在兩人對局中需要**考慮到對手的策略**，在選擇路徑的時候也需要考慮對手的選擇，這時候就會用到**Minimax Algorithm** (極小化極大演算法)，在我方先手時選擇最佳的下法，輪到對方時也要幫對方選擇最佳的下法。
如果將勝負結果量化的話，**我方先手時要選擇的就是分數最大的子節點，這一層我們稱為Max層，輪到下一層對方先手時，因為是零和遊戲，對方最佳的下法會使我方分數最低，所以這一層的節點我們要選子節點中最小的，這一層我們稱為Min層。**

### 深度優先搜索 (Depth-First-Search)
這邊我們會使用深度優先搜索，一開始將根節點的分數設為負無限大，往搜索尚未到葉節點之前的Min層設為無限大，Max層設為負無限大。
如下圖，會先一路搜到葉節點A，然後將值與B節點比較，B節點是Max層的所以要選大的值，此時將B節點的值更新為0，再接著探索C節點。


如下圖搜索到葉節點C的值為1，一樣會跟父節點B做比較，C > B，更新父節點B的值為1。



這邊B節點會再更新回他的父節點，B的父節點是在Min層所以是要選小的，0 < ∞ ，將其父節點的值更新為1。


最後就一路更新到填滿整棵樹為止。

### 練習

以下圖為例，獲勝的分數為1，輸掉則為-1，和局為0，在Max層的節點就是從子節點中選最大的，反之亦然，大家可以試著填填看。


這步肯定沒有問題，很簡明Max層就是挑最大的子節點，方便大家理解我把節點都上色了。


這邊要注意的是Min層，要挑最小的。


最後又是Max層，將勝負結果層層回傳至根節點，這樣就完成了。


## 實作
這邊就以井字遊戲作為示範，開始寫minimax之前我們先將一些基礎規則完成。

用最簡單的二維陣列來表達棋盤。

initial_grid = [
    ['X', 'O', 'X'],
    ['X', ' ', 'O'],
    ['O', ' ', ' ']
]

class Move:
    def __init__(self, row, col):
        self.row = row
        self.col = col


class Board:
    def __init__(self, grid=None):
        if grid:
            self.grid = grid  # 可以傳入任意盤面
        else:
            self.grid = [[' ' for _ in range(3)] for _ in range(3)]

    def set_move(self, move, player):
        if self.grid[move.row][move.col] == ' ':
            self.grid[move.row][move.col] = player
            return True
        return False

    def undo_move(self, move):
        self.grid[move.row][move.col] = ' '

    def get_available_moves(self):
        return [Move(row, col) for row in range(3) for col in range(3) if self.grid[row][col] == ' ']

    def check_winner(self):
        # 檢查橫排和直排
        for i in range(3):
            if self.grid[i][0] == self.grid[i][1] == self.grid[i][2] != ' ':
                return self.grid[i][0]
            if self.grid[0][i] == self.grid[1][i] == self.grid[2][i] != ' ':
                return self.grid[0][i]
        # 檢查對角線
        if self.grid[0][0] == self.grid[1][1] == self.grid[2][2] != ' ':
            return self.grid[0][0]
        if self.grid[0][2] == self.grid[1][1] == self.grid[2][0] != ' ':
            return self.grid[0][2] 
        # 檢查是否平局
        if all(cell != ' ' for row in self.grid for cell in row):
            return 'Draw'  # 平局
        return None

    def display(self):
        for row in self.grid:
            print('|'.join(row))
            print('-' * 5)

`set_move` `undo_move` 為設定走子跟復原用的。
`check_winner` 用來檢查勝負結果。
`get_available_moves` 取得所有的合法走步
`display` 印出棋盤

### minimax
我們採用深度優先搜索，遞迴展開整個遊戲樹，既然是遞迴就一定要有終止條件，終止條件就設定為下到結束為止，就是當有一方勝利時，或是棋盤已經沒有地方可以下了，那就是和棋，利用`check_winner`來檢查勝負結果。

`board`就是棋盤資訊。
`current_player`是當前輪到誰。
`maximizing_player`最大化玩家，就是max層的玩家。

def minimax(board, current_player, maximizing_player):
    """
    board: 棋盤狀態
    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
    
    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 = minimax(board, oppenent, maximizing_player)
            board.undo_move(move)
            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 = minimax(board, oppenent, maximizing_player)
            board.undo_move(move)
            best_score = min(score, best_score)
    return best_score

當`current_player`等於`maximizing_player`時，就代表是max層，我們將max層的`best_score`先設為負無限大，取出所有合法走步後開始嘗試每一手，遞迴繼續展開，這邊要記得試完之後要記得把試下的走步還原。

def find_best_move(board, player):
    """
    找到當前玩家的最佳手
    board: 棋盤狀態 (Board 物件)
    player: 當前回合玩家 ('X' 或 'O')
    """
    best_move = None
    best_score = -float('inf')
    openent = 'O' if player == 'X' else 'X'

    for move in board.get_available_moves():
        board.set_move(move, player)
        score = minimax(board, openent, player)
        board.undo_move(move)

        if score > best_score:
            best_score = score
            best_move = move

    return best_move

### negamax
negamax是minimax的簡化版本，在對手回合時直接乘上負號，這樣的話通通取max就可以了，就省去了分別對max層跟min層做判斷的部分。

def negamax(board, player, maximizing_player):
    """
    使用 negamax 演算法來評估棋盤狀態
    board: 棋盤狀態 (Board 物件)
    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

    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, oppenent, maximizing_player)
        board.undo_move(move)
        best_score = max(score, best_score)

    return best_score

## 特殊情況
如果你的遊戲先後手順序是會變化的就要加上一些例外處理了，比如蜜月橋牌，由前一輪點數大的玩家為先手，這樣會出現連續先手與連續後手的狀況。

做圖做得好累，偷渡一張我當年論文裡的圖，不知道為什麼解析度有點低，大家將就一下。


像這樣有連續先後手的遊戲，會產生你的Max層子節點不一定是Min層的情況，這樣就不能按照上面的方式更新節點了，大家可以動動腦思考一下該怎麼辦，我這邊先留個懸念，如果原先預計介紹的基礎內容都寫完了還有天數的話再來跟大家分享。