Est-il vrai que tous les programmes informatiques d'échecs peuvent être contraints à une triple répétition ?

Question

Clause de non-responsabilité : je sais que très peu sur les échecs : en gros, comment placer des pièces sur l'échiquier, comment les déplacer et comment perdre (je suis un pro en la matière). Je n'ai aucune idée de mon classement Elo, mais je suppose qu'il est de l'ordre de deux chiffres. Je vous prie donc de bien vouloir excuser les éventuelles maladresses que je pourrais commettre dans ma question.

L'une des rares choses que j'ai cru savoir, c'est qu'aujourd'hui les ordinateurs sont plus forts que les humains aux échecs. Des programmes tels que Stockfish , Komodo y Leela Chess Zero devrait être capable de battre régulièrement des Grands Maîtres, et même de donner du fil à retordre au champion du monde. Cependant, une connaissance qui est un bien meilleur joueur que moi, m'a dit que vous pouvez faire match nul contre n'importe quel programme d'échecs informatique en utilisant simplement la triple répétition. En d'autres termes, vous jouez votre coup, le programme d'échecs joue le sien, vous revenez en arrière, le programme d'échecs fait de même ( ??), vous répétez trois fois et voilà, vous obtenez votre match nul. Il a dit qu'il avait utilisé cette stratégie contre des moteurs d'échecs avec lesquels on peut jouer sur Internet, et que cela fonctionnait.

Cela semble incroyable :

1. Même moi, je pourrais écrire un programme qui ne tombe pas dans un tel piège. Il suffit de comparer le coup actuel avec le précédent : s'ils sont identiques, on augmente un compteur, sinon on le met à 0. Lorsque le compteur arrive à 2, on supprime ce coup de la liste des coups candidats. En d'autres termes, il ne faut jamais effectuer trois fois le même coup. Bien sûr, il peut y avoir des cas où exécuter le même coup trois fois pourrait être la meilleure stratégie : dans ce cas, il suffit d'offrir un match nul à l'adversaire humain. Mais en moyenne, il suffit d'éviter de jouer le même coup trois fois de suite.

2. Les différents moteurs d'échecs utilisent également des algorithmes très différents (par exemple, Leela Chess Zero est basé sur des réseaux neuronaux, RL et MCTS, tandis que Stockfish et Komodo utilisent d'autres approches, y compris des bases de données d'ouvertures, une liste d'heuristiques codées en dur, etc.), de sorte qu'il semble très improbable qu'une approche unique puisse exister qui puisse forcer un match nul contre tous les moteurs d'échecs existants.

3. Le prochain coup d'un moteur d'échecs ne dépend évidemment pas uniquement de mon coup actuel (celui de l'adversaire humain). Je suppose qu'il dépend de l'historique complet des coups de la partie en cours, ainsi que de l'estimation, faite par le moteur d'échecs, des coups qui ont le plus de chances de mener à la victoire à un stade ultérieur de la partie. Pourquoi mon coup actuel serait-il si important pour le moteur d'échecs qu'il répéterait le même coup simplement parce que je le fais ?

J'en conclus qu'il s'agit d'une "fake news", ou tout au plus d'un bug stupide dans les moteurs d'échecs contre lesquels cette connaissance a joué (peut-être pas un bug majeur, parce que les gens qui jouent aux échecs sur Internet ne sont probablement pas intéressés par une astuce bon marché pour faire match nul contre l'ordinateur, mais c'est tout de même un bug). Mais ce n'est certainement pas quelque chose qui se produit lorsque l'on joue contre les principaux moteurs d'échecs, tels que les trois que j'ai mentionnés initialement. Ai-je raison ?

Answer 1

Ce que dit votre ami n'est pas une "fake news", c'est carrément de la foutaise****. Bien sûr, les ordinateurs peuvent reconnaître les triples tirages. En fait, la première étape de l'écriture d'un nouveau moteur consiste à lui indiquer les règles du jeu.

Voici les lignes correspondantes dans Code de Stockfish :

bool Position::is_draw(int ply) const {

 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
     return true;

 // Return a draw score if a position repeats once earlier but strictly
 // after the root, or repeats twice before or at the root.

 if (st->repetition && st->repetition < ply)
     return true;

 return false;
}

Answer 2

Le point 1 est crucial. À moins que les codeurs n'aient complètement omis la règle de répétition, le robot calculera sa troisième répétition comme conduisant à un match nul. Il peut encore le choisir, mais seulement s'il calcule qu'aucune autre alternative n'est meilleure - c'est-à-dire que le match nul est le meilleur résultat qu'il puisse obtenir en supposant que vous ne commettiez pas de gaffe. Dans cette situation, soit le match nul est de toute façon inévitable, soit vous gâchez votre chance de gagner en répétant le coup.

Answer 3

Il est possible que votre ami ait trouvé une séquence qui fonctionne contre un moteur particulier fonctionnant à une difficulté particulière. Mais il est presque certain que cela ne se généralisera pas.

Les moteurs peuvent avoir ce que l'on appelle un "facteur de mépris" qui les pousse à éviter les tirages au sort s'ils évaluent la position comme légèrement négative. La présence et l'importance de ce facteur dépendent de chaque moteur.

Les moteurs connaissent le principe de la triple répétition et en tiennent compte. Si le moteur pense qu'il est en train de gagner ou de perdre avec un écart inférieur au facteur de mépris, il évitera un coup qui entraîne une triple répétition, même s'il s'agit du coup qu'il évalue comme étant le meilleur.

De plus, les moteurs puissants ne joueront pas toujours la même ouverture. Pour un moteur, si vous commencez par 1.e4, l'ordinateur jouera 8 réponses différentes à ce coup, avec des probabilités allant de 49% à 2%. Il est impossible que votre ami ait une ligne qui amène le moteur à répéter pour 1.e4. tous d'entre eux.

Answer 4

Tout d'abord, il n'est souvent pas possible de revenir en arrière. Pratiquement toutes les ouvertures impliquent des déplacements de pions, et vous ne pouvez pas revenir en arrière. Vous ne pouvez pas non plus annuler les captures. Il est donc évident que vous devrez faire des efforts pour vous retrouver dans une situation où l'ordinateur peut ne reprendra pas sa marche en avant, et encore moins ne le fera-t-elle.

L'ordinateur a généralement des attributs qu'il s'efforce d'atteindre, et il fera des mouvements "vers l'avant" par rapport à ces objectifs, et faire un mouvement vers l'arrière reviendrait à revenir en arrière.

Lors de l'ouverture, l'un des objectifs majeurs est le développement, qui consiste généralement à déplacer les pièces vers le centre. L'ordinateur aura besoin d'une bonne raison pour éloigner ses pièces du centre, et "je viens juste de reculer mes pièces" n'en est pas une.

En fin de partie, l'ordinateur s'efforcera d'avancer ses pions et d'éloigner votre roi du centre. Le premier ne peut pas être annulé, le second peut l'être, mais l'ordinateur n'a aucune raison de le faire.

Même moi, je pourrais écrire un programme qui ne tombe pas dans un tel piège. Il suffit de comparer le mouvement actuel avec le précédent : s'ils sont identiques, on augmente un compteur, sinon on le met à 0.

Un tel test n'aurait qu'une valeur limitée. Supposons que l'ordinateur attribue à chaque position un score égal à la probabilité qu'il pense gagner dans cette position, moins la probabilité qu'il pense perdre. On peut supposer que l'ordinateur choisira le coup ayant le score le plus élevé. Si l'ordinateur choisit toujours le même coup, cela signifie qu'il pense que tous les autres coups ont un score inférieur. Comme le fait de se déplacer encore et encore revient à dessiner, cela signifie que son score est au maximum de zéro. Il pense donc que tous les autres coups ont un score négatif, c'est-à-dire qu'il pense que tous les autres coups entraîneront probablement une perte. Alors pourquoi devrait-il éviter le tirage au sort, alors que l'alternative est une perte ?

Cela suppose que l'ordinateur attribue la même valeur à un match nul qu'à une victoire et une défaite, c'est-à-dire qu'il attribue la même valeur à "50 % de chances de gagner et 50 % de chances de perdre" qu'à "100 % de chances de gagner", ce qui pourrait ne pas être le cas, et il serait assez compliqué d'expliquer dans quelles circonstances il serait logique de ne pas attribuer la même valeur à ces deux éléments, mais en première approximation, nous pouvons faire cette hypothèse.

Answer 5

Même s'il n'y avait pas de règle stipulant que le fait d'entrer dans la même position constitue un match nul, un moteur d'échecs digne de ce nom l'ajouterait comme règle.

On ne peut pas gagner si l'on répète sans cesse les mêmes positions. Pour obtenir un mat, vous devez cesser de répéter les positions à un moment donné. Ainsi, si vous entrez dans la même position une deuxième fois, une évaluation en profondeur limitée de la position pourrait vous indiquer que le meilleur coup mènera à la même position avec une valeur positive, mais l'évaluation sera erronée : entrer dans la même position encore et encore mènera à un match nul et devrait donc être considéré comme ayant une valeur nulle.

Revenir à la même position une fois peut être correcte : dans la position X, une évaluation peu approfondie peut vous indiquer que a est le meilleur mouvement et que b est le deuxième meilleur. Avec les coups exécutés et votre évaluation plus poussée, vous constatez que le jeu optimal entre dans la même position. À ce stade, vous devez utiliser le coup b, ou vérifier s'il est préférable de refaire a puis de rompre la boucle.