Le fonctionnement des programmes dédiés à la résolution de jeux n'obéit pas aux mêmes contraintes de temps que les programmes fabriqués pour jouer en temps réel, ils ont beaucoup plus de temps pour s'orienter correctement dans l'arbre. En réalité, plutôt que d'utiliser un simple algorithme "alpha-beta" tel celui décrit dans l'article, ils utilisent souvent en haut de l'arbre un algorithme de recherche de type "best-first", par exemple le PN-search que Schaeffer a utilisé pour résoudre les dames anglaises.
C'est plus complexe qu'un alpha-beta avec une heuristique : l'alpha-beta, tu fais ton choix, puis tu t'y tiens - et si tu t'es trompé, tant pis pour toi. Le PN-search, une fois qu'il considère qu'il a passé trop de temps dans une branche, il la quitte et va essayer ailleurs. Il peut aussi déduire de ses calculs une probabilité que tel coup soit le meilleur coup.
C'est moins spontané qu'un alpha-beta, ça met plus de temps à tourner, mais sur le long terme c'est bien plus efficace, en particulier pour un jeu comme les échecs où il y a "mort subite".
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... Évalué à 1.
Le fonctionnement des programmes dédiés à la résolution de jeux n'obéit pas aux mêmes contraintes de temps que les programmes fabriqués pour jouer en temps réel, ils ont beaucoup plus de temps pour s'orienter correctement dans l'arbre. En réalité, plutôt que d'utiliser un simple algorithme "alpha-beta" tel celui décrit dans l'article, ils utilisent souvent en haut de l'arbre un algorithme de recherche de type "best-first", par exemple le PN-search que Schaeffer a utilisé pour résoudre les dames anglaises.
C'est plus complexe qu'un alpha-beta avec une heuristique : l'alpha-beta, tu fais ton choix, puis tu t'y tiens - et si tu t'es trompé, tant pis pour toi. Le PN-search, une fois qu'il considère qu'il a passé trop de temps dans une branche, il la quitte et va essayer ailleurs. Il peut aussi déduire de ses calculs une probabilité que tel coup soit le meilleur coup.
C'est moins spontané qu'un alpha-beta, ça met plus de temps à tourner, mais sur le long terme c'est bien plus efficace, en particulier pour un jeu comme les échecs où il y a "mort subite".