Java Minimax Alpha-Beta Tailler La Récursivité Retour
Je suis en train de mettre en œuvre minimax avec des alpha-bêta élagage pour un pions de jeu en Java. Mon minimax algorithme fonctionne parfaitement. Mon code fonctionne avec de l'alpha-beta code à la place. Malheureusement, quand j'ai jouer 1000 jeux vs la norme algorithme minimax, l'alpha-bêta algorithme s'en sort toujours derrière par 50 jeux ou.
Depuis alpha-bêta élagage devrait pas être de réduire la qualité de la se déplace, juste le temps qu'il faut pour les atteindre, quelque chose doit être mal. Cependant, j'ai pris la plume et du papier et dessiné hypothétique nœud feuille valeurs et utilisé mon algorithme pour prédire s'il va calculer le bon meilleur coup, et il ne semble pas être des erreurs de logique. J'ai utilisé l'arbre à partir de cette vidéo: Alpha-Beta Tailler de trace de mon algorithme. Logiquement, il devrait faire tous les mêmes choix, et donc un fonctionnement de mise en œuvre.
J'ai aussi mis des instructions d'impression dans le code (ils ont été supprimés afin de réduire l'encombrement), et les valeurs sont retournés correctement, il apparaît et l'élagage se fait. Malgré tous mes efforts, j'ai été incapable de trouver l'endroit où l'erreur logique de mensonges. C'est ma troisième différents tentative de mise en œuvre de ce et tous ont eu le même problème.
Je ne peux pas poster le code complet ici, c'est beaucoup trop long, donc j'ai inclus les méthodes qui sont pertinents à l'erreur. Je ne suis pas certain, mais je soupçonne que le problème peut probablement être dans le non-récursif de la méthode move (), mais je ne trouve pas une erreur de logique, alors que je venais d'agiter autour de en plus, probablement empirer les choses au lieu de s'améliorer sans avoir une rime ni raison.
Est-il une astuce pour récupérer plusieurs valeurs de nombre entier à partir d'appels récursifs dans une boucle for? Il fonctionne très bien avec mes deux minimax et negamax implémentations, mais alpha-beta tailler semble produire des résultats étranges.
@Override
public GameState move(GameState state)
{
int alpha = -INFINITY;
int beta = INFINITY;
int bestScore = -Integer.MAX_VALUE;
GameTreeNode gameTreeRoot = new GameTreeNode(state);
GameState bestMove = null;
for(GameTreeNode child: gameTreeRoot.getChildren())
{
if(bestMove == null)
{
bestMove = child.getState();
}
alpha = Math.max(alpha, miniMax(child, plyDepth - 1, alpha, beta));
if(alpha > bestScore)
{
bestMove = child.getState();
bestScore = alpha;
}
}
return bestMove;
}
private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta)
{
if(depth <= 0 || terminalNode(currentNode.getState()))
{
return getHeuristic(currentNode.getState());
}
if(currentNode.getState().getCurrentPlayer().equals(selfColor))
{
for(GameTreeNode child: currentNode.getChildren())
{
alpha = Math.max(alpha, miniMax(child, depth - 1, alpha, beta));
if(alpha >= beta)
{
return beta;
}
}
return alpha;
}
else
{
for(GameTreeNode child: currentNode.getChildren())
{
beta = Math.min(beta, miniMax(child, depth - 1, alpha, beta));
if(alpha >= beta)
{
return alpha;
}
}
return beta;
}
}
//Checks to see if the node is terminal
private boolean terminalNode(GameState state)
{
if(state.getStatus().equals(win) || state.getStatus().equals(lose) || state.getStatus().equals(draw))
{
return true;
}
else
{
return false;
}
}
- Dames dispose d'une position de départ et les deux minimax et minimax avec des alpha-bêta élagage sont des algorithmes déterministes, de sorte que chaque jeu doit se jouer à l'identique, sauf si vous avez introduit l'aléatoire quelque part. Peut-être ce caractère aléatoire est la production de la divergence dans les résultats.
- Minimax et minimax avec des alpha-bêta sont par définition censé produire des résultats identiques, seul alpha-beta tailler vous donne le résultat un peu plus vite, avec "un peu" étant déterminée par la qualité de votre déplacez la commande de hueristic est. Ainsi, la manière de tester votre alpha-bêta de la mise en œuvre consiste à exécuter minimax avec et sans sur un grand ensemble de positions et de vérifier que des résultats identiques sont produites pour les deux versions.
- J'ai réalisé que c'est en fait parce que mon minimax algorithme renvoie un hasard parmi l'égalité des meilleurs coups et mon alpha-bêta élagage, l'algorithme retourne le premier meilleur mouvement considéré (à cause de la façon dont l'alpha est passé mon application ne peut pas trouver de l'égalité des déplacements). Au début un mouvement sur le côté de la carte des points de la même à 3 plis, mais est en fait pire, mais c'est la première considérée comme l'alpha-bêta de la taille et, par conséquent, est renvoyé. Afin de choisir un hasard parmi les meilleurs coups est mieux que le simple fait de choisir le premier dans ce cas. Merci pour l'aide.
- Si vous avez trouvé la solution à cette question, vous pourriez répondre par vous-même, si vous le souhaitez.
Vous devez vous connecter pour publier un commentaire.
J'ai remarqué que vous avez dit que vous avez trouvé le problème, mais ne devrais pas le minimax alpha beta tailler être
vous avez écrit:
De simplement répondre à votre question
Oui, en Java, vous devrez passer un objet dans la fonction récursive appel, puis modifier le contenu de cet objet. Après les retours de fonction vous serez en mesure d'accéder à la modification de valeurs.
Par exemple.
Le 16 Mars 2013, sage88 demandé:
En alpha bêta de l'élagage, la seule valeur de sortie de l'intérêt est un nœud du score: la valeur finale de la bêta dans un min nœud est considéré comme la valeur alpha de son parent max nœud; de même, la valeur finale de l'alpha dans un max de nœud est considéré comme pour la bêta de la valeur de son parent min nœud. Donc:
La réponse à votre question est que l'algorithme lui-même, comme c'est le plus pertinent truc.
Cela dit, il y a deux erreurs dans votre mise en œuvre: 1) Comme Adrian Blackburn à l'origine, a souligné, il est correctement retourner alpha min à partir d'un nœud, et vice-versa, ce qui inclinaison de la précision; 2) qu'Il donne à tailler les opportunités par prématurément compte tenu de la mère alpha ou bêta dans le courant de la valeur du nœud. Cette version corrige les valeurs de retour et maximise la taille:
Merci de contribuer, amusante et intéressante question 🙂
Pour plus de fun, voici une clarification de votre
move()
méthode, la suppression d'un redondant appel àMath.max()
:Enfin (encore plus de plaisir), juste une suggestion, une méthode de changement de nom afin de clarifier l'intention de
terminalNode()
, mais je voudrais déplacer dansGameState
, elle pourrait être appelée sans paramètres:D'arriver à paris prunning résultats, vous devez implémenter une sorte de déplacer la commande. Dans les échecs, il est généralement de capture ou de vérifications. Ces mouvements ont tendance à changer d'évaluation plus et donc ils ont une grande incidence sur prunning. En dames, il prend peut-être des oposants de pierres ou de la promotion de l'auto pierres sur la 8ème rang (désolé de ne pas connaître les termes utilisés).
Vous déjà résolu votre problème, mais le problème que vous rencontrez est assez commun. Donc, chaque fois que vous construisez une partie de l'algorithme pour un agent AI, vous devez le tester correctement. Donc, une fois que votre minimax algorithme est correct, vous pouvez tout simplement de générer de nombreux aléatoire d'arbres et de vérifier si les résultats sont les mêmes. Par exemple en python, vous pouvez le faire de cette façon:
Maintenant vous pouvez générer un arbre avec de nombreuses aléatoire d'arbres et de comparer les résultats.
Ne pas oublier que minimax et alpha-bêta de renvoyer simplement le meilleur de la valeur, alors que ce que vous êtes intéressé dans un jeu réel est à un déménagement. Il est simple de les modifier de telle manière qu'ils puissent revenir à un déménagement, mais c'est au développeur de décider de la manière dont le mouvement est retourné. C'est parce qu'il peut y avoir beaucoup de mouvements qui conduisent à la meilleure solution (vous pouvez revenir sur la première, la dernière ou la plus commune est de trouver tous les mouvements et à retourner le hasard).
Dans votre cas, le problème était avec le caractère aléatoire des valeurs renvoyées, donc lors de la vérification de la bonne approche est de fixer l'aléatoire.