minimax深度第一搜索遊戲樹

Question

我想爲九個男人的莫里斯遊戲構建一個遊戲樹。我想在樹上應用minimax算法來做節點評估。 Minimax使用DFS來評估節點。那麼我應該首先將樹建立到給定深度，然後應用minimax，或者可以將樹和評估的構建過程一起發生在遞歸極小極小DFS中？

謝謝 阿文德

Answer 1

你可以看看iterative deepening depth first search。

Answer 2

是的，你可以建立並在遞歸極小，同時評估。
這是一個很好的方法，因爲它會節省內存空間。

事實上，你甚至可以在同一時間申請alpha-beta pruning。

編輯：這裏是從維基Minimax僞代碼：

function integer minimax(node, depth) 
    if node is a terminal node or depth == 0: 
     return the heuristic value of node 
    α = -∞ 
    for child in node: # evaluation is identical for both players 
     α = max(α, -minimax(child, depth-1)) 
    return α 

因爲我們（可能）存儲在每個節點的遊戲/板的狀態，我們可以嵌入 創建遊戲狀態的
在minimax算法，即

function integer play_minimax(node, depth) 
    if node is a terminal node or depth == 0: 
     return the heuristic value of node 
    α = -∞ 
    LOOP: # try all possible movements for this node/game state 
     player = depth mod 2 
     move = make_game_move(node, player) 
     break if not any move 
     α = max(α, -play_minimax(move, depth-1)) 
    return α