Par contre je me pose la question de savoir à quel moment un jeu peut être considéré comme résolu? A défaut de prouver une stratégie gagnante définir un programme invincible semble le terme du jeu.
Un programme invincible ne te dit pas du tout que le jeu est résolu (tant que tu ne peux pas reproduire toi-même la stratégie gagnante, le jeu n'est pas résolu). Le jeu d'échec est loin d'être résolu, puisque d'après l'article AlphaZero utilise toute une variété d'ouvertures, et donc ne reproduit pas une stratégie unique : il sait gagner en jouant des parties diversifiées. Du coup, il n'a pas résolu le jeu, il est juste super-bon.
Formellement, il y a plusieurs niveaux dans la résolution du jeu. Tu dois d'abord prouver que le jeu peut être résolu, ce qui n'est pas encore fait aux échecs (on ne sait pas si la meilleure stratégie blanche mène à la victoire ou à une partie nulle, on pense que ça mène au match nul mais ça n'est pas prouvé—formellement, on pourrait aussi aller à la victoire des noirs, mais ça surprendrait vraiment tout le monde. La raison pour laquelle on penche vers la nulle est qu'un joueur qui joue les noirs et qui n'a qu'à annuller la dernière partie pour gagner un match y arrive assez facilement ; il suffit d'échanger les pièces jusqu'à la nulle par manque de matériel.
Si tu sais que ton jeu peut être résolu, il faut ensuite déterminer la meilleure stratégie (suite de coups qui mène à la victoire des blancs malgré la meilleure défense des noirs). Tu peux considérer à ce stade que le jeu est résolu. Sauf que si tu ne sais pas comment répondre à un coup sous-optimal des noirs, en pratique, tu ne vas pas gagner à tous les coups. Il te faut donc connaitre la stratégie qui mène à la victoire à partir de n'importe quelle réaction des noirs. Et là, tu as résolu ton jeu. Mais techniquement, il n'est pas dit que ça soit faisable pour les échecs. Même si tu contrôles les blancs (et donc, tu n'as pas à envisager tous les coups possibles des blancs), et qu'en moyenne les noirs ont 20 coups légaux, pour une partie qui s'achève en 40 coups, il te reste quand même 1052 parties à mémoriser... Si tu te concentres que sur 3 coups possibles (en partant du principe que les 17 autres coups sont tellement mauvais que tu serais capable de gagner sans l'algorithme optimal), tu restes à 1019 parties, ce qui semble difficilement faisaible avec le matériel informatique d'aujourd'hui... Bref, au delà des problèmes de calcul, stocker quelque part les suites de coups qui te permettent de gagner à tous les coups n'est peut-être même pas faisable.
Ceci dit, d'énormes progrès ont été faits sur les fins de parties, et je crois que toutes les fins à moins de 8 pièces sont résolues dans toutes les positions, par exemple. Honnêtement, rien qu'avec ça, tu bats n'importe quel joueur humain, à moins d'arriver en fin de partie avec un gros handicap. C'est vraiment le milieu de partie qui pose problème.
# jeu résolu
Posté par arnaudus . En réponse au journal Les échecs en échec. Évalué à 10.
Un programme invincible ne te dit pas du tout que le jeu est résolu (tant que tu ne peux pas reproduire toi-même la stratégie gagnante, le jeu n'est pas résolu). Le jeu d'échec est loin d'être résolu, puisque d'après l'article AlphaZero utilise toute une variété d'ouvertures, et donc ne reproduit pas une stratégie unique : il sait gagner en jouant des parties diversifiées. Du coup, il n'a pas résolu le jeu, il est juste super-bon.
Formellement, il y a plusieurs niveaux dans la résolution du jeu. Tu dois d'abord prouver que le jeu peut être résolu, ce qui n'est pas encore fait aux échecs (on ne sait pas si la meilleure stratégie blanche mène à la victoire ou à une partie nulle, on pense que ça mène au match nul mais ça n'est pas prouvé—formellement, on pourrait aussi aller à la victoire des noirs, mais ça surprendrait vraiment tout le monde. La raison pour laquelle on penche vers la nulle est qu'un joueur qui joue les noirs et qui n'a qu'à annuller la dernière partie pour gagner un match y arrive assez facilement ; il suffit d'échanger les pièces jusqu'à la nulle par manque de matériel.
Si tu sais que ton jeu peut être résolu, il faut ensuite déterminer la meilleure stratégie (suite de coups qui mène à la victoire des blancs malgré la meilleure défense des noirs). Tu peux considérer à ce stade que le jeu est résolu. Sauf que si tu ne sais pas comment répondre à un coup sous-optimal des noirs, en pratique, tu ne vas pas gagner à tous les coups. Il te faut donc connaitre la stratégie qui mène à la victoire à partir de n'importe quelle réaction des noirs. Et là, tu as résolu ton jeu. Mais techniquement, il n'est pas dit que ça soit faisable pour les échecs. Même si tu contrôles les blancs (et donc, tu n'as pas à envisager tous les coups possibles des blancs), et qu'en moyenne les noirs ont 20 coups légaux, pour une partie qui s'achève en 40 coups, il te reste quand même 1052 parties à mémoriser... Si tu te concentres que sur 3 coups possibles (en partant du principe que les 17 autres coups sont tellement mauvais que tu serais capable de gagner sans l'algorithme optimal), tu restes à 1019 parties, ce qui semble difficilement faisaible avec le matériel informatique d'aujourd'hui... Bref, au delà des problèmes de calcul, stocker quelque part les suites de coups qui te permettent de gagner à tous les coups n'est peut-être même pas faisable.
Ceci dit, d'énormes progrès ont été faits sur les fins de parties, et je crois que toutes les fins à moins de 8 pièces sont résolues dans toutes les positions, par exemple. Honnêtement, rien qu'avec ça, tu bats n'importe quel joueur humain, à moins d'arriver en fin de partie avec un gros handicap. C'est vraiment le milieu de partie qui pose problème.