最小最大化法

最小最大化法（Min-Max Algorithm）是一種用於零和遊戲的經典算法，其中遊戲的每一方都試圖最大化自己的收益，同時最小化對手的收益。這種算法常用於象棋和圍棋等策略遊戲中，以幫助計算機玩家做出決策。

最小最大化法的思想很簡單：

1. 玩家1（通常稱為Max）嘗試預測玩家2（通常稱為Min）的最優反應，並選擇一個能夠最大化自己收益的策略。
2. 然後，玩家2（Min）嘗試預測玩家1（Max）的最優反應，並選擇一個能夠最小化對手收益的策略。
3. 這個過程不斷交替進行，直到達到一個穩定的策略或狀態，即納什均衡。

在實際套用中，最小最大化法通常與動態規劃相結合，以減少搜尋的複雜性。這種結合被稱為α-β剪枝，它通過在搜尋樹中剪枝來避免搜尋所有可能的後續狀態，從而加快搜尋過程。

最小最大化法的偽代碼如下：

function MinMax(node, depth, isMaximizingPlayer) {
    if (node is a leaf) {
        return the value of the leaf
    }

    if (isMaximizingPlayer) {
        value = -infinity
        for each child of node {
            value = max(value, MinMax(child, depth - 1, false))
        }
    } else {
        value = +infinity
        for each child of node {
            value = min(value, MinMax(child, depth - 1, true))
        }
    }

    return value
}

在這個偽代碼中，isMaximizingPlayer 參數表示當前是否是Max玩家在做出決策。如果isMaximizingPlayer為真，那麼Max玩家試圖最大化其收益；如果為假，那麼Min玩家試圖最小化Max玩家的收益。depth參數表示搜尋樹的深度，它限制了搜尋的廣度以避免無限遞歸。

最小最大化法雖然簡單，但在實際套用中可能會遇到一些問題，比如它假設遊戲的狀態是有限的，而且它不考慮對手可能不是最優的情況。因此，在實際的遊戲中，通常會使用更複雜的算法，如蒙特卡洛樹搜尋（MCTS）來提高性能。