Fonction C++ minimax

Question

J'ai cherché Google et Stackoverflow pour cette question, mais je ne comprends toujours pas comment fonctionne une fonction minimax.

Je trouve l'entrée wikipedia a une version pseudo-code de la fonction:

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 α 

Plusieurs autres fonctions que je Minimax avec ce Google sont essentiellement la même chose; Je suis en train de mettre en œuvre ce en C++, et voici ce que je suis venu avec jusqu'à présent:

double miniMax(Board eval, int iterations) 
{ 
    //I evaluate the board from both players' point of view and subtract the difference 
    if(iterations == 0) 
     return boardEval(eval, playerNumber) - boardEval(eval, opponentSide()); 

    /*Here, playerTurn tells the findPossibleMoves function whose turn it is; 
    I mean, how do you generate a list of possible moves if you don't even know 
    whose turn it's supposed to be? But the problem is, I don't see where I can 
    get playerTurn from, as there are only 2 parameters in all the examples of 
    minimax I've seen*/ 
    vector<int> moves = eval.findPossibleMoves(playerTurn); 

    //I'm assuming -∞ in the wikipedia article means a very low number? 
    int result = -999999999; 

    //Now I run this loop to evaluate each possible move 
    /*Also, the Lua example in the wiki article has 
     alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score) 
     Is alpha a boolean there?!*/ 
    for(int i = 0; i * 2 < moves.size(); i++) 
    { 
     //I make a copy of the board... 
     Board temp = eval; 

     /*and make the next possible move... once again playerTurn crops up, and I 
     don't know where I can get that variable from*/ 
     temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn); 

     /*So do I create a function max that returns the bigger of two doubles?*/ 
     result = max(result, -miniMax(temp, iterations - 1)); 
    } 

    return result; 
    /*So now I've returned the maximum score from all possible moves within a certain 
    # of moves; so how do I know which move to make? I have the score; how do I know 
    which sequence of moves that score belongs to?*/ 
} 

Comme vous pouvez le voir, je suis assez confus au sujet de cette fonction minimax. S'il vous plaît, donnez-moi au moins quelques conseils pour m'aider.

Merci! :)

Answer 1

Cet exemple de Wikipedia fait NegaMax avec l'élagage Alpha/Beta .

Vous pouvez être aidé en obtenant la dénomination droite:

• La base est MiniMax, une mise en œuvre littérale impliquerait 2 méthodes qui se relaient mutuellement (récursifs), 1 pour chaque côté.

• Les programmeurs paresseux transforment cela en NegaMax, une méthode avec un opérateur - stratégiquement placé. L'élagage Alpha/Beta garde une trace des meilleurs coups (sur plusieurs profondeurs) pour détecter les branches mortes.

Votre playerTurn est utilisé pour déterminer qui est le tour. Dans NegaMax vous pouvez déduire cela de la profondeur (itérations) étant impair ou pair. Mais il serait plus facile d'utiliser 2 paramètres (myColor, otherColor) et de les changer à chaque niveau.

Answer 2

Votre fonction miniMax() doit mémoriser le meilleur mouvement trouvé jusqu'à présent. Ainsi, au lieu de ce code:

    /*So do I create a function max that returns the bigger of two doubles?*/ 
    result = max(result, -miniMax(temp, iterations - 1)); 

Vous devriez faire quelque chose comme ceci:

    /*So do I create a function max that returns the bigger of two doubles?*/ 
    double score = -miniMax(temp, iterations - 1); 
    if (score > result) 
    { 
    result = score; 
    bestMove = i; 
    } 

Bien sûr, vous avez besoin d'une variable « bestMove » et une façon de retourner le meilleur mouvement trouvé à l'appelant.

Answer 3

Ajoutez la variable playerTurn en tant qu'argument à miniMax et appelez le miniMax que le joueur actuel déplace initialement et récursivement.

En outre, opponentSide doit être une fonction de playerTurn.

Answer 4

Dans votre pseudo-code, la variable de noeud doit contenir toutes les informations sur la position actuelle de la carte (ou autre). Cette information inclurait le changement de direction.

Answer 5

Un bon endroit pour commencer la recherche d'arborescence de jeu est le chess programming wiki. Pour votre question sur le déménagement: Je pense qu'il est plus commun d'avoir deux fonctions max. La différence entre les deux fonctions max est que l'une ne renvoie que le score et l'autre renvoie le score et le meilleur coup.Un ordre d'appel récursif serait comme suit:

maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...) 

Il y a quelques bons papiers avec pseudo-code pour l'algorithme de Beta Alpha:

• TA Marsland - Computer Chess and Search
• J Schaeffer - The games Computers (and People) Play

à votre question le commentaire: et math.max (alpha, score) ou math.min (alpha, score) Alpha est-il un booléen ?!

Aucun alpha n'est une fenêtre liée à un algorithme alpha bêta. La valeur alpha est mise à jour avec une nouvelle valeur. Comme alpha et bêta sont échangés avec l'appel récursif de la fonction negamax, la variable alpha fait référence à la variable bêta dans l'appel récursif suivant.

Une note à la variable playerTurn: L'algorithme minimax ou alpha-beta n'a pas besoin de cette information. Donc, je donnerais l'information - qui est la prochaine - dans la structure du Conseil. Les fonctions findPossibleMoves et boardEval obtiennent toutes les informations dont ils ont besoin à partir de la Board-Structure.

Une note à la condition de coupure récursive: Si je comprends bien votre code, alors vous avez seulement celui avec iterations == o. Je pense que cela signifie que l'algorithme a atteint la profondeur désirée. Mais que se passe-t-il s'il n'y a aucun mouvement possible avant que l'algorithme atteigne cette profondeur. Peut-être que vous devriez écrire ce qui suit:

vector<int> moves = findPossibleMoves(...); 
if (!moves.size()) 
    return boardEval(...);