Collecte et récupération de la variation principale à partir d'un cadre alphabeta

Question

J'essaie d'écrire un moteur d'échecs en python, je peux trouver le meilleur coup donné une position, mais j'ai du mal à recueillir la variation principale de cette position, ce qui suit est ce que je l'ai essayé jusqu'à présent:

def alphabeta(board, alpha, beta, depth, pvtable): 

    if depth == 0: 
     return evaluate.eval(board) 

    for move in board.legal_moves: 
     board.push(move) 
     score = -alphabeta(board, -beta, -alpha, depth - 1, pvtable) 
     board.pop() 
     if score >= beta: 
      return beta 
     if score > alpha: 
      alpha = score 
      pvtable[depth-1] = str(move) 
    return alpha 

J'utilise pvtable[depth - 1] = str(move) pour ajouter mouvements mais à la fin je trouve que pvtable contient mouvements aléatoires non uniformes, des choses comme ['g1h3', 'g8h6', 'h3g5', 'd8g5'] pour la position de départ.

Je sais que des questions similaires à ce sujet ont été posées mais je n'ai toujours pas compris comment je peux résoudre ce problème.

Answer 1

Je pense que vos mouvements sont écrasés lorsque la recherche atteint à nouveau la même profondeur (dans une branche différente de l'arbre de jeu).

Ce site explique assez bien comment récupérer la variation principale: https://web.archive.org/web/20071031100114/http://www.brucemo.com:80/compchess/programming/pv.htm

Appliqué à votre exemple de code, il devrait y avoir quelque chose comme ça (je ne pas testé):

def alphabeta(board, alpha, beta, depth, pline): 

    line = [] 
    if depth == 0: 
     return evaluate.eval(board) 

    for move in board.legal_moves: 
     board.push(move) 
     score = -alphabeta(board, -beta, -alpha, depth - 1, line) 
     board.pop() 
     if score >= beta: 
      return beta 
     if score > alpha: 
      alpha = score 
     pline[:] = [str(move)] + line 

    return alpha