profondità Minimax prima ricerca albero di gioco
Domanda
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
Soluzione
Si potrebbe dare un'occhiata al iterativo profondità approfondimento di ricerca prima .
Altri suggerimenti
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 α