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.
InformationsquelleAutor sage88 | 2013-03-16