Java Minimax Alpha-Beta Pruning Recursion Return

j'ai remarqué que vous avez dit que vous avez trouvé le problème mais que vous ne devriez pas le Minimax alpha bêta élagage être

if it is MAX's turn to move
  for child in children
     result = alphaBetaMinimax(child, alpha, beta)
     if result > alpha
        alpha = result
        if node is root
           bestMove = operator of child
     if alpha >= beta
        return alpha
  return alpha

if it is MIN's turn to move
  for child in children
     result = alphaBetaMinimax(child, alpha, beta)
     if result < beta
        beta = result
        if node is root
           bestMove = operator of child
     if beta <= alpha
        return beta
  return beta

vous avez écrit:

  if alpha >= beta
    return beta
return alpha

Pour juste répondre à votre question

Est-il une astuce pour récupérer plusieurs valeurs entières de récursive les appels dans une boucle for?

Oui, en Java, vous devrez passer un objet dans la fonction récursive appel, puis modifier le contenu de cet objet. Après le retour de la fonction, vous pourrez accéder aux valeurs modifiées.

par exemple.

class ToBeReturned {
    int returnValue1;
    int returnValue2;
    int returnValue3;
}

le 16 Mars 2013, sage88 demandé:

y a-t-il une astuce pour récupérer des valeurs entières multiples à partir d'appels récursifs dans une boucle for? cela fonctionne très bien avec mes implémentations minimax et negamax, mais l'élagage alpha-bêta semble produire des résultats étranges.

dans l'élagage alpha beta, la seule valeur de sortie d'intérêt est le score d'un noeud: la valeur finale de beta dans un noeud min est considérée pour la valeur alpha de son parent max noeud; de même, la valeur finale d'alpha dans un noeud max est considérée pour la valeur bêta de son noeud parent min. Donc:

la réponse à votre question Est l'algorithme lui-même, car c'est l'astuce la plus pertinente.

cela dit, il y a deux erreurs dans votre implémentation: 1) comme Adrian Blackburn l'a fait remarquer à l'origine, il retourne incorrectement alpha à partir d'un nœud min et vice-versa, ce qui altère sa précision; 2) il abandonne l'élagage possibilités en considérant prématurément l'alpha ou le bêta parent dans la valeur du noeud courant. Cette version fixe les valeurs de retour et maximise l'élagage:

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)) {
        int currentAlpha = -INFINITY;
        for (GameTreeNode child : currentNode.getChildren()) {
            currentAlpha = Math.max(currentAlpha, miniMax(child, depth - 1, alpha, beta));
            alpha = Math.max(alpha, currentAlpha);
            if (alpha >= beta) {
                return alpha;
            }
        }
        return currentAlpha;
    }
    int currentBeta = INFINITY;
    for (GameTreeNode child : currentNode.getChildren()) {
        currentBeta = Math.min(currentBeta, miniMax(child, depth - 1, alpha, beta));
        beta = Math.min(beta, currentBeta);
        if (beta <= alpha) {
            return beta;
        }
    }
    return currentBeta;
}

Merci de contribuer, amusante et intéressante question :)

pour plus de plaisir, voici une clarification de votre move() méthode, suppression d'un appel redondant vers Math.max():

@Override
public GameState move(GameState state) {
    GameState bestMove = null;
    int bestScore = -INFINITY;
    GameTreeNode gameTreeRoot = new GameTreeNode(state);
    for (GameTreeNode child : gameTreeRoot.getChildren()) {
        int alpha = miniMax(child, plyDepth - 1, bestScore, INFINITY);
        if (alpha > bestScore || bestMove == null) {
            bestMove = child.getState();
            bestScore = alpha;
        }
    }
    return bestMove;
}

enfin (encore plus amusant), juste une suggestion, un changement de nom de méthode pour clarifier l'intention de terminalNode(), mais je voudrais déplacer dans GameState donc il peut être appelé sans paramètres:

private boolean isTerminal(GameState state) {
    //return Is.any(state.getStatus(), win, lose, draw);
    return state.getStatus().equals(win)
        || state.getStatus().equals(lose)
        || state.getStatus().equals(draw);
}

pour obtenir des résultats d'émondage, vous devez mettre en place une sorte d'ordre de mouvement. Aux échecs, il s'agit généralement de captures ou de chèques. Ces types de mouvements ont tendance à changer l'évaluation la plupart du temps et ont donc un grand impact sur l'élagage. Dans checkers, il peut s'agir de prendre des potences ou de promouvoir des SELF-stones au 8ème rang (désolé, Je ne connais pas les termes utilisés).

Vous avez 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. Ainsi, une fois que votre algorithme minimax est correct, vous pouvez simplement générer de nombreux arbres aléatoires et vérifier si les résultats sont les mêmes. Par exemple en python, vous pouvez le faire de cette façon:

class Node():
    def __init__(self, data, children):
        self.data = data
        self.children = children

def generateTree(depth, branching):
    total = branching**depth
    values = [randint(-100, 100) for _ in xrange(total)]
    level = [Node(values[i], []) for i in xrange(total)]

    for _ in xrange(depth):
        total /= branching
        level = [Node(None, level[i * branching: (i+1) * branching]) for i in xrange(total)]

    return level[0], values

maintenant vous pouvez générer un arbre avec beaucoup d'arbres aléatoires et comparer résultat.

tree, values = generateTree(depth, branching)
print negamax(tree, depth, 1) == alpha_beta_negamax(tree, depth, float('-inf'), float('inf'), 1)

n'oubliez pas que minimax et alpha-beta ne rapportent que la meilleure valeur, alors que ce qui vous intéresse dans un vrai jeu est un mouvement. 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 mènent à la meilleure solution (vous pouvez retourner le premier, Le Dernier ou le plus commun est de trouver tous les mouvements et de revenir le hasard).

dans votre cas le problème était avec le caractère aléatoire des valeurs retournées, donc pendant les tests la bonne approche est de corriger le caractère aléatoire.