Alpha-Beta cutoff

Question

Je comprends les bases de cette recherche, mais la partie bêta me déroute, quand beta < = valeur de l'alphabet je peux soit retourner bêta, casser, ou continuer la boucle.

• beta de retour ne semble pas fonctionner correctement du tout, il retourne les mauvais joueurs se déplacent pour un état différent du conseil d'administration (plus loin dans l'arbre de recherche)

• pause semble fonctionner correctement, il est très rapide, mais il semble un peu trop vite

• continue est beaucoup plus lent que la rupture, mais il semble plus correct ... Je devine que c'est la bonne façon, mais pseudocode sur Google utilisent tous « break », mais parce que c'est pseudocode je ne suis pas sûr de ce qu'ils veulent dire par «break»

Answer 1

Juste pour le plaisir que je vais deviner que vous parlez Minimax avec coupure Alpha-Beta, où

coupure ALPHA-BETA est une méthode pour réduire le nombre de nœuds explorés dans la stratégie Minimax. Pour les nœuds il explore calcule, en plus au score, une valeur alpha et une valeur bêta .

Here is a page qui décrit cette méthode et fournit également un lien vers un C program qui implémente cette méthode. Espérons que quelque chose ici vous aide avec votre problème, si je suis totalement hors de mon estimation s'il vous plaît donner plus de détails dans votre question.

function MINIMAX(N) is 
    begin 
     if N is a leaf then 
      return the estimated score of this leaf 
     else 
      Let N1, N2, .., Nm be the successors of N; 
      if N is a Min node then 
       return min{MINIMAX(N1), .., MINIMAX(Nm)} 
      else 
       return max{MINIMAX(N1), .., MINIMAX(Nm)} 
     end MINIMAX; 

Answer 2

Beta cutoffs se produisent lorsque la branche que vous recherchez actuellement est mieux pour votre adversaire que celui que vous avez déjà recherché. Il m'a été une fois expliqué comme suit:

Supposons que vous vous battez avec votre ennemi, et vous considérez un certain nombre de vos choix. Après avoir recherché le meilleur résultat possible de votre premier choix (lancer un coup de poing), vous déterminez le résultat que votre adversaire finira par vous piquer dans les yeux. Nous appellerons cette bêta ... le meilleur que votre adversaire puisse faire jusqu'à présent. Évidemment, vous aimeriez trouver un résultat qui fait mieux.

Maintenant, nous considérons votre prochaine option (fuir en disgrâce). Lorsque vous explorez la première réponse possible de vos adversaires, nous constatons que le meilleur résultat possible est que vous êtes abattu dans le dos avec une arme à feu. C'est là que la coupure bêta est déclenchée ... nous arrêtons de chercher le reste des mouvements de vos adversaires et retournons la bêta, parce que nous ne nous soucions pas si vous trouvez dans la recherche de ses autres réponses il peut également vous nuke ... vous le feriez déjà opter pour le poke dans l'oeil de l'option précédente.

Maintenant, spécifiquement ce que cela signifie est que votre programme devrait renvoyer bêta ... si cela ne fonctionne pas, vous devriez comparer à un algorithme de recherche alpha-bêta elsewhere.