Day6 Evaluation Function
===
在有限的時間中，很多遊戲是不可能搜索完所有的結果的，因為昨天我們的範例是井字遊戲，他的對局樹複雜度很低，可以直接把所有下法都試一遍，如果換成圍棋、西洋棋等，就不可能這麼做了，你會以為你的程式進入到了無窮迴圈之中，根本跑不完，所以我們必須想個辦法讓他停下來，這時候就可以使用審局函數。

## 審局函數
審局函數（Evaluation Function）是電腦對局中用來評估當前盤面好壞的一種數學函數。其主要目的是在沒有明確勝負的情況下，根據當前的盤面，給出一個評分，來衡量該局面對於某一方玩家的優劣程度。

判斷局勢是在各種對局中都相當重要的，你必須了解到目前的局面形勢才有辦法去決定你的策略，比如在優勢中可能會選擇較為保守的策略來確保最後能夠獲勝，在劣勢中則可能會考慮選擇激進的策略以求逆轉戰局。
如果不小心誤判了局勢，比如在劣勢中仍然選擇了保守的策略，則有可能得到「安樂死」的下場。

在我們限制搜索深度後，葉節點可能並沒有算到勝負結果，這時候就使用審局函數給予評分，然後一樣使用minimax一路回傳到根節點，如下圖所示：


### 完美審局函數
理論上任何一個遊戲都有一個完美的審局函數，假設 $f(x)$ 為井字遊戲的完美審局函數，$x$ 為任意盤面，只要輸入任意盤面就可以得到勝負結果。

獲勝：$f(x) = 1$
和棋：$f(x) = 0$
失敗：$f(x) = -1$

如果找到一個完美的審局函數，那遊戲等於被破解了，任何盤面只要經過此完美審局函數則立刻可以得知勝負。

### 近似審局函數
大多數情況我們找不到完美的審局函數，只能盡量找出一個近似解或是找出一個較佳的範圍。
那要如何設計審局函數呢？
根據不同遊戲我們必須設計不同的策略，以下是我認為比較常見的三大類做法：
1. 靜態評估
對當前盤面做出的靜態分析。
像是Day4中提到的人類經驗法則，此時就可以作為一種評估的方式，還可以根據**棋子數量、功能性、形狀特徵**等方式給分數，例如西洋棋、象棋在過去就很常透過子力分析來作為一種評估方式。
或是根據不同類型的遊戲可以使用特別的演算法，例如之前我與一位UCLA博士生Steven大大，曾經用影像處理中常見的**Morphology**(形態學)來實作圍棋的形勢判斷，如果過幾天我還能堅持下去的話會再來分享的。
2. 模擬法
**通過大量模擬對局，統計勝負結果來評估當前盤面。**
從當前盤面模擬下到結束，假設100次中贏了70次，那此盤面的勝率就評估為70%，最常見的方式就是使用Monte Carlo Method做大量的隨機模擬，這個後續章節也會更詳細的做介紹。
3. 機器學習
這邊最經典的例子就是AlphaGo中的value network，他就是用來評估當前盤面好壞的。

## 程式修改
我們在昨天的minimax中加上一個`depth`參數，用來讓遞迴停止，可以根據硬體設備或比賽規範的時間來設定搜索深度，當到達指定深度後，直接停止並且對當前盤面進行判斷。

def minimax(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)
    
    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)
            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, depth + 1, opponent, maximizing_player)
            board.undo_move(move)
            best_score = min(score, best_score)
    return best_score

我們要在其中多加入一個遞迴終止條件，比如此處我們設定為10，並且在每次遞迴呼叫的時候將`depth`+1。

if depth == 10:
    return evaluate(board)

這邊的`evaluate`就是我們要設計的審局函數了，因為井字遊戲實在是沒什麼好設計的，所以這裡就先寫到這裡，其他遊戲的審局函數設計我們就保留到後面再來分享。

## 相關論文分享
其實研究各遊戲審局函數的論文也不少，最後來分享幾篇論文吧。

* [暗棋子力價值之審局設計](https://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/login?o=dnclcdr&s=id=%22110NTPU0392012%22.&searchmode=basic)
* [六子棋之棋型分類及審局函數之研究](https://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/login?o=dnclcdr&s=id=%22099NTNU5392014%22.&searchmode=basic)
* [暗棋殘局庫對審局函數之改良](https://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/login?o=dnclcdr&s=id=%22112NTPU0392002%22.&searchmode=basic)
* [電腦象棋審局評分自動調整系統](https://www.airitilibrary.com/Article/Detail/U0030-0309201012110423)