Fonction minimax C++

Question

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

J'ai trouvé que l'entrée Wikipédia contient une version pseudocode 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 minimax que j'ai trouvées avec Google sont fondamentalement la même chose ;J'essaie d'implémenter cela en C++, et voici ce que j'ai trouvé 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 échantillon de Wikipédia fait NegaMax avec taille Alpha/Bêta.

Vous pourriez être aidé en précisant le nom :

• La base est MiniMax, une implémentation littérale impliquerait 2 méthodes qui se relaient (mutuellement récursives), 1 pour chaque côté.

• Les programmeurs paresseux transforment cela en NegaMax, une méthode avec un emplacement stratégique. - opérateur.

• L'élagage alpha/bêta consiste à garder une trace d'une fenêtre des meilleurs mouvements (sur plusieurs profondeurs) pour détecter les branches mortes.

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

Answer 2

Votre fonction miniMax () doit se rappeler le meilleur coup qu'il a 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 comme argument pour miniMax et miniMax d'appel qui mouvement du joueur en cours au départ et récursive.

En outre, les besoins de opponentSide être fonction de playerTurn.

Answer 4

Un bon endroit pour commencer la recherche de l'arbre de jeu est le wiki de programmation échecs . Pour votre question à propos du déménagement: Je pense qu'il est plus fréquent d'avoir deux fonctions max. La différence entre les deux fonctions max est que l'on ne retourne que le score et les autres rendements 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 Beta Alpha:

• TA Marsland - Computer Chess et Recherche
• J Schaeffer - les jeux Ordinateurs (et personnes) Jouer

Pour votre question dans le commentaire:! et Math.max (alpha, score) ou Math.min (alpha, score) est un booléen alpha il

Pas alpha est une fenêtre liée à un algorithme bêta alpha. La valeur alpha est mis à jour avec une nouvelle valeur. Parce que alpha et bêta sont permutés avec l'appel récursif de la negamax-fonction de la variable alpha fait référence à la variable bêta dans le prochain appel récursif.

Une note à la variable playerTurn: Minimax ou algorithme alpha-bêta n'a pas besoin de ces informations. Donc, je voudrais donner l'information - qui est le suivant -, dans le conseil-structure. Les fonctions findPossibleMoves et boardEval obtenir toutes les informations dont ils ont besoin du Conseil-Structure.

Une note à la condition de rupture récursive: Si je comprends bien votre code, vous avez seulement celui avec iterations == o. Je pense que cela signifie que l'algorithme a atteint la profondeur désirée. Mais s'il n'y a pas possibles déplace vers la gauche befor l'algorithme atteint cette profondeur. Peut-être vous devriez écrire suivant:

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

Answer 5

Dans votre pseudo-code, la variable de nœud doit contenir toutes les informations sur la position actuelle du conseil (ou autre). Cette information comprendrait dont le tour est de se déplacer.