pour résoudre le jeu d'échec (et bien d'autres) il « suffit » de trouver un seul chemin qui fait gagner un camp à coup sûr
Ce n'est pas vraiment «un chemin». On peut représenter l'ensemble des parties d'échecs possibles par un «arbre de jeu» : à la racine, on met la position initiale, à l'étage 1, les coups jouables à partir de la position initiale, etc. Il n'est pas possible de développer tout l'arbre qui contient bien trop de positions (voir https://fr.wikipedia.org/wiki/Nombre_de_Shannon) ; mais pour résoudre le jeu d'échecs, seule la connaissance d'une partie de cet arbre de jeu est nécessaire (ce qu'on appelle un «arbre solution»). La question est : existe-t-il des arbres solutions du jeu d'échecs assez petits pour être calculables ? (et si oui, arrivera-t-on à les trouver...)
Par contre ça ne fonctionne pas si la résolution donne nul ?
Si, pas besoin de parcours exhaustif dans ce cas. Un moyen simple de s'en tirer : tu changes légèrement les règles du jeu d'échecs en «Blanc est déclaré vainqueur s'il gagne ou si ça finit en nul, Noir est le vainqueur sinon». Tu fais le calcul. Puis tu changes à nouveau les règles : «Blanc est déclaré vainqueur s'il gagne, Noir est déclaré vainqueur s'il gagne ou si ça finit en nul». Tu refais le calcul. Si Blanc est en position de force dans le premier calcul, et Noir dans le deuxième calcul, c'est que deux joueurs jouant parfaitement feront nul. Et tu as obtenu ce résultat en deux «petits» calculs, ce qui est bien meilleur que le développement de tout l'arbre de jeu.
Notez que les dames sont "résolues" dans le sens où on connait le résultats quand les deux joueurs jouent parfaitement, mais je ne pense pas qu'il existe un programme parfait (qui joue parfaitement dans toutes les positions)
Pas sûr qu'on puisse utiliser cette stratégie pour les échecs, parce qu'aux échecs une partie peut se terminer avant la finale (et il existe donc de nombreuses fins de partie qui ne sont pas dans les tables)
Schaeffer a utilisé une base de fin de parties en précalculant le résultat de toutes les positions avec <= 10 pièces encore en jeu. Ça lui a probablement permis un petit gain de temps, mais c'est l'élément le moins important de son calcul. Le fait de ne pas disposer d'une base complète de positions finales aux échecs n'empêche pas d'appliquer la même stratégie : quand on rencontre une position, au lieu de la chercher dans la grande base de données de positions finales, il suffit de tester si c'est un mat. On perd certes un peu de temps de calcul, mais les mêmes algorithmes peuvent être utilisés.
[^] # Re: Fascinant
Posté par Lapinot (site web personnel) . En réponse à la dépêche Stockfish 12 est sorti. Évalué à 1.
Ce n'est pas vraiment «un chemin». On peut représenter l'ensemble des parties d'échecs possibles par un «arbre de jeu» : à la racine, on met la position initiale, à l'étage 1, les coups jouables à partir de la position initiale, etc. Il n'est pas possible de développer tout l'arbre qui contient bien trop de positions (voir https://fr.wikipedia.org/wiki/Nombre_de_Shannon) ; mais pour résoudre le jeu d'échecs, seule la connaissance d'une partie de cet arbre de jeu est nécessaire (ce qu'on appelle un «arbre solution»). La question est : existe-t-il des arbres solutions du jeu d'échecs assez petits pour être calculables ? (et si oui, arrivera-t-on à les trouver...)
Si, pas besoin de parcours exhaustif dans ce cas. Un moyen simple de s'en tirer : tu changes légèrement les règles du jeu d'échecs en «Blanc est déclaré vainqueur s'il gagne ou si ça finit en nul, Noir est le vainqueur sinon». Tu fais le calcul. Puis tu changes à nouveau les règles : «Blanc est déclaré vainqueur s'il gagne, Noir est déclaré vainqueur s'il gagne ou si ça finit en nul». Tu refais le calcul. Si Blanc est en position de force dans le premier calcul, et Noir dans le deuxième calcul, c'est que deux joueurs jouant parfaitement feront nul. Et tu as obtenu ce résultat en deux «petits» calculs, ce qui est bien meilleur que le développement de tout l'arbre de jeu.
Effectivement, Schaeffer a produit ce qu'on appelle une «résolution faible», mais pas une «résolution forte» : https://fr.wikipedia.org/wiki/Jeu_r%C3%A9solu
Schaeffer a utilisé une base de fin de parties en précalculant le résultat de toutes les positions avec <= 10 pièces encore en jeu. Ça lui a probablement permis un petit gain de temps, mais c'est l'élément le moins important de son calcul. Le fait de ne pas disposer d'une base complète de positions finales aux échecs n'empêche pas d'appliquer la même stratégie : quand on rencontre une position, au lieu de la chercher dans la grande base de données de positions finales, il suffit de tester si c'est un mat. On perd certes un peu de temps de calcul, mais les mêmes algorithmes peuvent être utilisés.