profondità Minimax prima ricerca albero di gioco

Question

Voglio costruire un albero di gioco per morris gioco nove uomini. Voglio applicare l'algoritmo minimax sull'albero per fare le valutazioni dei nodi. Minimax utilizza DFS per valutare i nodi. Quindi dovrei costruire l'albero prima fino a una data profondità e quindi applicare minimax o posso il processo di costruzione della struttura e la valutazione si verificano insieme in Minimax ricorsiva DFS?

Grazie Arvind

Answer 1

Si potrebbe dare un'occhiata al iterativo profondità approfondimento di ricerca prima .

Answer 2

Sì, è possibile costruire e valutare allo stesso tempo in una minimax ricorsiva.
Questo è un buon approccio in quanto risparmierete spazio di memoria.

In realtà, si può anche applicare potatura alfa-beta allo stesso tempo.

Modifica qui è pseudocodice dal wiki 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 α

Essendo (probabilmente) memorizzare uno stato di gioco / pensione in ogni nodo, potremmo incorporare il creazione di stati di gioco
nell'algoritmo Minimax, vale a dire

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 α