Question intéressante. Alpha=7 est bien trop pessimiste. D'ailleurs, je ne comprends pas le raisonnement de ton deuxième paragraphe qui donne cette valeur. Quand on cherche à prouver qu'une position est gagnante, alpha évalue le nombre d'essais que l'on fait avant de trouver un coup qui envoie l'adversaire vers une position perdante, un "coup parfait".
Déjà, un tel coup parfait n'est pas forcément unique. Dans les conditions de l'article, on considère un branching factor de 18 (18 coups sont jouables à partir de toute position). Si on suppose par exemple que sur les 18 coups jouables, 3 sont des coups parfaits (en pratique, les positions pour lesquelles un seul coup parfait existe sont rares), alors la méthode consistant à jouer au pif fournit déjà un alpha de 4,75 seulement (je le laisse en exercice)... soit déjà bien en-dessous de 7. Et évidemment, décider de programmer une meilleure technique que "jouer au pif" est susceptible d'améliorer grandement ce nombre.
Mais ce n'est pas tout. Dans le cadre de l'article, dans un souci de simplification du propos, je fais comme si on allait résoudre le jeu d'échecs par un algorithme alpha-beta. En réalité, il est probable que le jour où il sera résolu, il le sera à l'aide de méthodes plus élaborées (voir par exemple l'article de Schaeffer et al "Checkers is solved" où il explique les techniques qu'il a utilisées pour résoudre le jeu des dames anglaises), utilisant justement la recherche dans l'arbre. Ces méthodes contribuent elles-aussi à réduire le nombre de noeuds étudiés, ce qui équivaut à réduire alpha.
Attention également au parallèle avec le go. Ces deux jeux sont très différents, ce n'est pas étonnant si les ordis battent les humains d'un côté et pas de l'autre. La force d'un programme d'échecs dépend beaucoup moins de la puissance de calcul que pour les programmes de go.
Après, je suis bien d'accord que alpha=2, c'est choisi avec une bonne grosse louche bien épaisse (difficile de faire mieux sans programmer pour voir ce qui se passe). Mais si je devais parier sur la valeur réelle, je pencherais vraiment pour moins de 2.
[^] # 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.
Question intéressante. Alpha=7 est bien trop pessimiste. D'ailleurs, je ne comprends pas le raisonnement de ton deuxième paragraphe qui donne cette valeur. Quand on cherche à prouver qu'une position est gagnante, alpha évalue le nombre d'essais que l'on fait avant de trouver un coup qui envoie l'adversaire vers une position perdante, un "coup parfait".
Déjà, un tel coup parfait n'est pas forcément unique. Dans les conditions de l'article, on considère un branching factor de 18 (18 coups sont jouables à partir de toute position). Si on suppose par exemple que sur les 18 coups jouables, 3 sont des coups parfaits (en pratique, les positions pour lesquelles un seul coup parfait existe sont rares), alors la méthode consistant à jouer au pif fournit déjà un alpha de 4,75 seulement (je le laisse en exercice)... soit déjà bien en-dessous de 7. Et évidemment, décider de programmer une meilleure technique que "jouer au pif" est susceptible d'améliorer grandement ce nombre.
Mais ce n'est pas tout. Dans le cadre de l'article, dans un souci de simplification du propos, je fais comme si on allait résoudre le jeu d'échecs par un algorithme alpha-beta. En réalité, il est probable que le jour où il sera résolu, il le sera à l'aide de méthodes plus élaborées (voir par exemple l'article de Schaeffer et al "Checkers is solved" où il explique les techniques qu'il a utilisées pour résoudre le jeu des dames anglaises), utilisant justement la recherche dans l'arbre. Ces méthodes contribuent elles-aussi à réduire le nombre de noeuds étudiés, ce qui équivaut à réduire alpha.
Attention également au parallèle avec le go. Ces deux jeux sont très différents, ce n'est pas étonnant si les ordis battent les humains d'un côté et pas de l'autre. La force d'un programme d'échecs dépend beaucoup moins de la puissance de calcul que pour les programmes de go.
Après, je suis bien d'accord que alpha=2, c'est choisi avec une bonne grosse louche bien épaisse (difficile de faire mieux sans programmer pour voir ce qui se passe). Mais si je devais parier sur la valeur réelle, je pencherais vraiment pour moins de 2.