Comment sélectionner un nœud en utilisant Alpha Beta

Question

J'implémente une IA pour un jeu Othello en utilisant MiniMax avec l'élagage Alpha Beta. J'ai implémenté un algorithme Alpha Beta qui me dit la valeur que je peux obtenir, mais pas quel nœud je devrais sélectionner? Donc, ma question est comment puis-je utiliser alpha-bêta pour me dire quel noeud je devrais sélectionner, pas ce que la valeur résultante serait. Voici le pseudo-code de mon algorithme Alpha-Beta.

01 function alphabeta(node, depth, α, β, maximizingPlayer) 
02  if depth = 0 or node is a terminal node 
03   return the heuristic value of node 
04  if maximizingPlayer 
05   v := -∞ 
06   for each child of node 
07    v := max(v, alphabeta(child, depth – 1, α, β, FALSE)) 
08    α := max(α, v) 
09    if β ≤ α 
10     break (* β cut-off *) 
11   return v 
12  else 
13   v := ∞ 
14   for each child of node 
15    v := min(v, alphabeta(child, depth – 1, α, β, TRUE)) 
16    β := min(β, v) 
17    if β ≤ α 
18     break (* α cut-off *) 
19   return v 

Answer 1

Si vous voulez seulement connaître le meilleur mouvement dans la position de la racine, il suffit de se rappeler qui se déplacent dans la position racine avait le score le plus élevé. Pour cela, il suffit de renvoyer le score. Aucun changement dans le pseudo-code n'est nécessaire. Comme vous vous interrogez sur le chemin vers le nœud critique, je suppose que vous demandez un moyen de reconstruire le principal variation, qui donne des informations sur la série de coups attendus par la recherche.

En théorie, vous pouvez simplement renvoyer la valeur et la variation principale de l'appel récursif. Cela vous permet de reconstruire le chemin. Triangular PV-Tables sont des structures de données optimisées à cette fin.

Si votre recherche utilise un transposition table, une approche plus simple consiste simplement à démarrer la position racine et à rechercher le meilleur mouvement dans la table de transposition. Faites ensuite ce mouvement et répétez (recherchez le meilleur coup, faites le meilleur coup, cherchez à nouveau, etc.) jusqu'à ce que le jeu soit terminé ou qu'aucune entrée n'ait été trouvée. À la fin, les mouvements qui ont été faits sont la principale variation. L'approche de la table de transposition n'est pas aussi précise que le suivi explicite de la variation principale, mais elle est simple à implémenter et n'ajoute aucun surcoût pendant la recherche.