Comment fonctionne exactement minimax la récursivité de travail?

StackOverflow https://stackoverflow.com//questions/11703846

Question

J'ai donc été à la recherche Mini-max pour un Tic-Tac-Toe Jeu, mais je ne pouvais pas comprendre comment la récursivité travaillé?Ok, donc en gros voici mes questions:

  1. Comment minimax savoir à qui le tour?Quel est le meilleur moyen pour indiquer le joueur dont c'est le tour de la génération?
  2. Comment pouvez-vous générer des coups?
  3. Comment savez-vous quand vous êtes à un nœud terminal, et comment pouvez-vous générer les terminaux?

Par exemple, dans ce Pseudo-code

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 α

Un node c'est un conseil de bon?Et est la profondeur de la façon dont beaucoup de plis, le code est à entrer dans la récursivité?Aussi quel est le max fonction et où sont les nœuds générés à partir de?

Jusqu'à maintenant, j'ai ce code pour la création d'un conseil:

class Board{
    public:
        Board();
        ~Board(){};
    public: // The board
        // In the board, 1 is x, 2 is o, 0 is empty square.
        int board[3][3];
};

Mais comment pourrais-je savoir à qui le tour?Et comment puis-je générer les nœuds enfants pour le conseil?

Était-ce utile?

La solution

Nous allons utiliser votre tic-tac-toe est un exemple de la première.

  • Un algorithme minimax qui fonctionne le mieux pour les jeux où les joueurs jouent à tour de rôle, mais peuvent être adaptées à des jeux où les joueurs peuvent faire plusieurs mouvements par tour.Nous supposerons que l'ancien, pour des raisons de simplicité.Dans ce cas, vous n'avez pas besoin de stocker 'X pour déplacer" ou " O pour aller avec chaque nœud, parce que peut juste être déterminée par la parité du nœud de profondeur (si je suis un même nombre d'étapes, ou un nombre impair d'étapes, à partir du haut).
  • Génération de mouvements possibles à partir de chaque poste nécessite que vous connaissez son déménagement, il est (ce qui peut être déterminé comme avant), et les règles juridiques se déplace d'une position particulière.Pour un jeu simple comme tic-tac-toe, compte tenu d'une position, il suffit d'énumérer tous les états qui se composent d'une copie de la position actuelle en plus d'un nouveau morceau, appartenant à l'actuel joueur, placé à chaque case vide à son tour.Pour des jeux comme Othello, vous devez également vérifier chaque placement pour s'assurer qu'il respecte les règles, et la mise à jour de la position finale selon les conséquences de la règle (pour Othello, inverser les couleurs d'un tas de pièces).En général, à partir de chaque position valide, vous êtes suivi, vous énumérer toutes les possibilités de classement d'une nouvelle pièce et vérifier pour voir ceux qui sont autorisés par le jeu de règles.
  • En général, vous n'avez JAMAIS générer de l'arbre tout entier, depuis le jeu de l'arbre tailles peuvent facilement dépasser la capacité de stockage de la Terre.Vous avez toujours donner une profondeur maximale de l'itération.Un nœud terminal, alors, est tout simplement un nœud à la profondeur maximale, ou d'un nœud à partir de laquelle aucun coup légal existe pas (pour tic-tac-toe, une carte de chaque carré rempli).Vous n'avez pas de générer les terminaux à l'avance;ils se produit naturellement au cours du jeu de la construction de l'arbre.Tic-tac-toe est assez simple pour que vous peut générer la totalité de l'arborescence du jeu, mais alors n'essayez pas d'utiliser votre tic-tac-toe code pour par exempleOthello.

En regardant votre pseudo:

  • max(a, b) est une fonction qui renvoie le plus grand de a ou b.C'est généralement fournie par une bibliothèque de mathématiques ou similaire.
  • L' depth est la profondeur maximale à laquelle vous recherche.
  • La valeur heuristique vous êtes le calcul est certaine valeur numérique qui décrit la valeur de la carte.Pour un jeu comme tic-tac-toe, ce qui est assez simple que vous POUVEZ énumérer l'ensemble de l'arborescence du jeu, vous pouvez désigner 1 pour un poste au conseil d'administration qui gagne pour le joueur de faire l'analyse, -1 pour un poste au conseil d'administration qui gagne pour l'autre joueur, et 0 pour toute concluants position.En général, vous devez faire cuire jusqu'à une heuristique de vous-même, ou bien reconnus.
  • Vous générez les nœuds à la volée lors de votre analyse basée sur leurs nœuds parents.Votre nœud racine est toujours la position à partir de laquelle vous êtes en train de faire l'analyse.

Si vous n'avez pas travaillé avec des graphiques ou des arbres encore, je vous suggère de le faire en premier;l'arbre primitif, en particulier, est essentiel pour ce problème.

Comme une réponse à un commentaire de ce fil pour demander un exemple de la détermination dont c'est le tour pour un noeud donné, je vous offre cette pseudo-Python:

who_started_first = None

class TreeNode:
    def __init__(self, board_position = EMPTY_BOARD, depth = 0):
        self.board_position = board_position
        self.children = []
        self.depth = depth
    def construct_children(self, max_depth):
        # call this only ONCE per node!
        # even better, modify this so it can only ever be called once per node
        if max_depth > 0:

            ### Here's the code you're actually interested in.
            if who_started_first == COMPUTER:
                to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
            elif who_started_first == HUMAN:
                to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
            else:
                raise ValueError('who_started_first invalid!')

            for position in self.board_position.generate_all(to_move):
                # That just meant that we generated all the valid moves from the
                # currently stored position. Now we go through them, and...
                new_node = TreeNode(position, self.depth + 1)
                self.children.append(new_node)
                new_node.construct_children(max_depth - 1)

Chaque nœud est capable de garder une trace de sa profondeur absolue de la "racine" du nœud.Quand nous essayons de déterminer comment nous devrions générer des postes au conseil d'administration pour la prochaine étape, nous allons vérifier son déménagement, il est basé sur la parité de notre profondeur (le résultat de la self.depth % 2) et notre dossier de qui s'installe d'abord.

Autres conseils

1) Comment minimax savoir à qui le tour?Quel est le meilleur moyen pour indiquer le joueur dont c'est le tour de la génération?

Vous avez que depth argument.Si la profondeur est la même, alors c'est un tour du joueur, si il est impair, alors c'est l'autre joueur de jouer.

2) Comment pouvez-vous générer des coups?

En utilisant les règles du jeu.Dans tic tac toe, un mouvement possible consiste à placer la marque dans un cellulaire gratuit.

3) Comment savez-vous quand vous êtes à un nœud terminal, et comment pouvez-vous générer les terminaux?

Un terminal nœud est un nœud où quelqu'un a gagné.Vous les générer par récurrence.Chaque appel récursif doit être étant donné l'état actuel du conseil d'administration.Je suppose que c'est le node et child les paramètres de votre pseudo.Donc si quelqu'un a gagné, alors il est en terminal, sinon vous essayez tous les déplacements et de manière récursive.

Je peux donner un peu une idée de ce que vous recherchez, depuis que j'ai écrit un algorithme minimax pour tic-tac-toe.

Pour répondre à vos questions directement:

  1. Mon algorithme minimax n'ai pas à le déterminer.Il a accepté l'argument qui a déterminé le joueur qui l'algorithme a été à l'aide.

  2. Sachant que le joueur à se déplacer, en boucle par toutes les cases vides sur la carte, et pour chacun, de générer un noeud avec l'actuel joueur du jeton dans cette place.De manière récursive procéder à partir de là.

  3. J'ai utilisé une fonction qui a retourné une valeur qui indique si le jeu était terminé, et si c'était un match nul ou une victoire.

Mon algorithme de base a fait ceci:

  • Entrée:le joueur à se déplacer, et l'état du conseil d'administration.
  • Trouver tous les espaces vides laissés sur le bord.
    • Générer un nouveau conseil d'administration avec le joueur qui se déplace dans l'espace.
    • Si le jeu est terminé, générer un nœud avec le résultat de la partie.
    • Sinon, exécutez l'algorithme, en passant de l'autre joueur et le nouveau conseil d'administration, et de générer un nœud avec le résultat de l'adversaire idéal de se déplacer.
  • Déterminer le nœud (déplacer) conduit à la meilleure possible pire des cas.
  • Sortie:Le meilleur coup, et des informations sur le jeu en résultent.
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top