Confusion sur l'algorithme MiniMax

Question

Donc je travaille actuellement sur une affectation qui tourne autour de l'algorithme MiniMax sur un jeu qui est une combinaison de Mancala et NIM. La façon dont le programme fonctionne est de demander à l'utilisateur l'état actuel du tableau et le programme est supposé cracher le premier mouvement que l'utilisateur devrait prendre pour gagner la partie. Je suis juste confus sur je suis supposé générer l'arbre de jeu entier avec toutes les solutions possibles et aux nœuds de feuille ont la fonction d'utilité d'abord alors que l'algorithme MiniMax traverse récursivement ou l'arbre est créé dans l'algorithme MiniMax ? Je suis désolé si cette question est très floue mais je suis juste coincé sur cette idée et je n'arrive pas à la comprendre.

Answer 1

La manière correcte d'écrire une fonction minimax est de parcourir l'arbre de recherche en faisant et en décochant des mouvements. Vous ne stockez qu'un seul état de jeu à la fois, et en faisant et en défaisant les mouvements sur cet état de jeu, vous traversez l'arbre entier. Si cela est déroutant, il sera utile de regarder un peu de psodocode minimax. Notez qu'il existe deux variantes couramment utilisées de minimax, minimax régulier et negamax. Le psudeocode est minimax parce qu'il est plus intuituve, mais en pratique, je recommande la variante negamax car il est beaucoup plus simple:

int max(int depth){ 
if(this state is terminal){//won, lost, drawn, or desired search depth is reached 
    return value 
} 
//if the state is non terminal 
//we want to examine all child nodes. We do this by making all possible moves from this state, calling the min function 
//(all childs of max nodes are min nodes) and then unmaking the moves. 
int bestVal = -infinity; 
generate move list; 
for(all moves in move list){ 
    makeMove(this move in move list); 
    int val = min(depth -1); 
    unMakeMove(this move in move list); 
    bestVal = max(val,bestVal); 
} 
return bestVal; 

}

int min(int depth){ 
    if(this state is terminal){//won, lost, drawn, or desired search depth is reached 
     return value 
    } 
    //if the state is non terminal 
    //we want to examine all child nodes. We do this by making all possible moves from this state, calling the max function 
    //(all childs of min nodes are max nodes) and then unmaking the moves. 
    int bestVal = +infinity; 
    generate move list; 
    for(all moves in move list){ 
     makeMove(this move in move list); 
     int val = min(depth -1); 
     unMakeMove(this move in move list); 
     bestVal = min(val,bestVal); 
    } 
    return bestVal; 
} 

Ainsi vous traversez l'arbre tout entier en gardant la trace d'un l'état du jeu et le fait de faire et de défaire récursivement les mouvements sur cet état de jeu. Une fois que vous comprenez ce regard sur l'élagage alpha bêta. Sachez également que cette fonction ne renvoie que la valeur du meilleur mouvement et non le déplacement lui-même. Vous aurez besoin d'une fonction spéciale qui garde la trace du meilleur coup ainsi d'appeler à la racine.