在有限的時間中，很多遊戲是不可能搜索完所有的結果的，因為昨天我們的範例是井字遊戲，他的對局樹複雜度很低，可以直接把所有下法都試一遍，如果換成圍棋、西洋棋等，就不可能這麼做了，你會以為你的程式進入到了無窮迴圈之中，根本跑不完，所以我們必須想個辦法讓他停下來，這時候就可以使用審局函數。
審局函數（Evaluation Function）是電腦對局中用來評估當前盤面好壞的一種數學函數。其主要目的是在沒有明確勝負的情況下，根據當前的盤面，給出一個評分，來衡量該局面對於某一方玩家的優劣程度。
判斷局勢是在各種對局中都相當重要的，你必須了解到目前的局面形勢才有辦法去決定你的策略，比如在優勢中可能會選擇較為保守的策略來確保最後能夠獲勝，在劣勢中則可能會考慮選擇激進的策略以求逆轉戰局。
如果不小心誤判了局勢，比如在劣勢中仍然選擇了保守的策略，則有可能得到「安樂死」的下場。
在我們限制搜索深度後，葉節點可能並沒有算到勝負結果，這時候就使用審局函數給予評分，然後一樣使用minimax一路回傳到根節點，如下圖所示：
理論上任何一個遊戲都有一個完美的審局函數，假設 為井字遊戲的完美審局函數，
為任意盤面，只要輸入任意盤面就可以得到勝負結果。
獲勝：
和棋：
失敗：
如果找到一個完美的審局函數，那遊戲等於被破解了，任何盤面只要經過此完美審局函數則立刻可以得知勝負。
大多數情況我們找不到完美的審局函數，只能盡量找出一個近似解或是找出一個較佳的範圍。
那要如何設計審局函數呢？
根據不同遊戲我們必須設計不同的策略，以下是我認為比較常見的三大類做法：
我們在昨天的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就是我們要設計的審局函數了，因為井字遊戲實在是沒什麼好設計的，所以這篇就先寫到這，其他遊戲的審局函數設計我們就保留到後面再來分享。
其實研究各遊戲審局函數的論文也不少，最後來分享幾篇論文吧。
iThome鐵人賽
看影片追技術