Quand l'élagage alpha-bêta est inefficace

Question

Existe-t-il un cas où l'on puisse dire que l'élagage alpha-bêta est inefficace. En d'autres termes, disons que nous avons un jeu où vous devez atteindre 27 pour gagner, et vous et votre adversaire pouvez seulement utiliser 1,2,5 à chaque fois pour additionner. L'élagage Alpha-Beta est-il efficace ici? N'est-ce pas un peu déroutant de l'évaluer de cette façon, surtout au début de notre cas où il y a beaucoup de possibilités dont nous ne nous soucions pas vraiment? Je me sens comme je peux l'expliquer, mais je ne peux pas! Aidez-moi.

Answer 1

Pour ce jeu, il peut arriver qu'il soit possible de le réduire à une formule mathématique, et que la recherche arborescente et l'élagage alpha-bêta soient surdimensionnés.

Mais disons que ce n'est pas possible. Vous avez un jeu avec deux ou trois résultats: PERTE (-1), WIN (1) et éventuellement DRAW (0), et aucune évaluation significative des positions intermédiaires. Ensuite, vous devrez rechercher jusqu'à la fin de chaque variation, et par ex. l'approfondissement itératif serait inutile. Cependant, l'élagage alpha-bêta pourrait être très efficace: Si bêta = -1 (ce qui signifie que l'adversaire a trouvé une victoire), vous pouvez juste revenir -1 immédiatement, sans même chercher un PV. Si bêta = 0, la seule fois où vous auriez besoin de rechercher tous les nœuds enfants, c'est quand tous les coups (sauf peut-être les derniers) sont perdus. La condition pour que l'alpha-bêta soit suffisamment efficace est, bien entendu, que l'arbre complet soit suffisamment petit pour traverser dans un temps raisonnable. J'ai oublié de mentionner que pour votre exemple particulier, se souvenir des évaluations aurait beaucoup plus d'effet que l'élagage alpha-bêta par rapport au nombre de nœuds parcourus (de 2688332 à 77).