Jeu d'échecs et IA

S'agissant des échecs, Stockfish n'est pas de l'IA, c'est de la programmation "à l'ancienne"
et il résiste aux programmes d'IA issus de Leela.

Dans l'IA aux échecs il y a le nom zero comme (alpha go zero pour le go) leela zero, ce qui signifie que l'humain laisse le programme comme le dit Gérard jouer contre lui-même et progressivement fabriquer ses propres déductions et règles.

Il y a des gens qui font de l’entraînement dit supervisé avec l'IA, c'est-à-dire par exemple qu'ils nourrissent l'IA avec l'ensemble des parties jouées par les humains, afin qu'elles ne démarrent pas de zéro.
...

Oui beaucoup de nulles comme en 1984, les deux K s'affrontent. La règle est le premier qui gagne 6 matchs est champion du monde, les nulles ne comptent pas. Karpov mène haut la main très rapidement mais ne parvient pas à remporter une sixième victoire, il y a nulle sur nulle, Karpov s'épuise et Kasporov remonte petit à petit. L'affrontement est interminable, le clan Karpov voyant l'ogre de Bakou rattraper son retard, finit par faire interrompre ce championnat du monde.

Ce serait dommage que sur un forum de maths comme le nôtre, personne ne mentionne explicitement que les algorithmes utilisés reposent sur de l'apprentissage par renforcement (reinforcement learning en anglais), c'est-à-dire entre autres sur des maths très intéressantes concernant les processus de décision markoviens (Markov decision processes).

En gros, l'idée de base des algorithmes les plus souvent utilisés est que la machine joue de nombreuses parties dans le but de découvrir (pendant son apprentissage) ou de maximiser (après son apprentissage) les valeurs d'une fonction Q définie comme une moyenne de cumuls de récompenses à long terme. Une fois que la machine a appris une estimation de cette fonction, quand elle joue, il lui suffit de choisir à chaque étape le coup qui maximise cette fonction Q, ce qui lui permet entre autres de faire des choix qui paraissent perdants à court terme mais qui sont en fait gagnants à long terme (voir les slides ci-jointes pour plus de détails techniques).

La grande nouveauté de ces dernières années n'est pas vraiment dans ces algorithmes, dits de Q-learning, qui existent depuis quelques décennies mais davantage dans l'utilisation des réseaux de neurones combinés au Q-learning et dans les capacités de calcul élevées qui vont avec.

Enfin, l'apprentissage par renforcement a bien d'autres applications que les jeux, cf. https://fr.wikipedia.org/wiki/Apprentissage_par_renforcement

NB : les algorithmes de Q-learning ne sont pas les seuls qui existent en apprentissage par renforcement.

Ahem, qu'est-ce que « scaler » veut dire ?

Bonjour,

"snowballer" signifie "faire boule de neige" (un effet amplificateur et auto entretenu) et "scaler" signifie "déployer à grande échelle."

Dans ce contexte, cela signifie que sur les gros problèmes, avec un espace d'états très grand, où lorsque la Q fonction est complexe, le Q learning marche très mal.

Même en incluant le deep Q learning (qui n'est pas du Q learning stricto sensu) les méthodes par policy gradient marchent très souvent beaucoup mieux. Et pour le coup l'approche n'a vraiment rien à voir.

On ne sait toujours qui est gagnant au échecs, soit il y à nul, soit ce sont les blancs ou les noirs qui gagnent
Sinon les ordinateurs sont plus fort que l'homme mais il se peut que l'ordinateur soit battu (ça m'est déjà arrivé de battre l'ordi niveau 2700 avec le muzio gambit). Donc il se peut que des GM arrivent à battre des ordinateurs comme stockfish ou alpha0.
Sinon les matchs GM-Ordinateurs ne se font plus trop pour éviter d'être "humilié" par des ordinateurs.

Si tu prends deux joueurs un 2200 et un 2400 que tu fais se mesurer à une floppée de 1200,
ben tu ne verras jamais la différence de niveau entre le 2200 et le 2400,
le elo calculé à partir de parties contre joueurs de 1200 sera identique …
Le combat homme machine sous cette forme n'a plus de sens.

Ce qui est rigolo ce sont des résolutions de problèmes, de gains ou de mats
sur des positions où l'ordi:
n'y arrivait pas du tou
y arrivait en 10 heures
puis y arrivait en qqs mn
et maintenant qqs secondes.
Faudrait refaire des trucs comme le faisait il me semble Pierre Nolot dans Europe-échecs il ya qqs décennies?

beagle a écrit:

Faudrait refaire des trucs comme le faisait il me semble Pierre Nolot dans Europe-échecs il ya qqs décennies ?

Tu voudrais en dire plus ?

Jean-Louis écrivait :

---

> Peut-on vraiment comparer des elo de joueurs humains et d'ordis qui ne jouent jamais l'un contre l'autre.

Le nombre elo résulte d'un calcul de probabilité de victoire en cas de rencontre. Si des machines ont un elo fini c'est quelles ont rencontré des joueuses ou des joueurs homo-sapiens et que leurs algorithmes ne résolvent pas le théorème de Zermelo de la théorie des jeux (le match ordinateur-homo-sapiens n'est pas encore déterminé par la couleur des pièces et pions des joueurs).

Quand je m'intéressais au jeu d'échecs, l'Elo était calculé en gros ainsi :

E0 = Elo de départ
Pour chaque match gagné, je marque des points (très peu si c'était un match contre un joueur beaucoup moins bien classé, et beaucoup si c'était un match contre un joueur mieux classé).
Et le perdant décaissait des points (le même nombre ?, supposons que oui)
Et pour les matchs nuls, pareil, l'un des 2 joueurs marquait quelques points, et l'autre en perdait.

Matériellement, c'était difficile de faire plus d'un match homologué par semaine.
Idéalement, si je sais que contre tel joueur, je gagne très souvent, et si j'arrive à jouer 50 matchs contre lui chaque semaine, je vais marquer plein de points, Enormément !

Le système marchait, parce que le nombre de matchs joués était fixe, limité. Disons 200 parties par an pour les pros.

Les logiciels, ils ne jouent pas 200 parties par an, mais 200 par semaine. Comment ceci a été pris en compte ? Est-ce que ça a été pris en compte ?

Bonjour,

Pour le elo des machines, on utilise des classements sous contraintes (de temps, de puissance de calcul, etc.). Et il est impossible de comparer au elo entre humains.

Donc les différents classements essaient de calibrer pour donner une idée, une estimation, mais pas une mesure.

On n’a pas suffisamment de parties humains-machines pour établir un elo pour les machines.

Mais bon, le meilleur humain c’est elo 2850 (à peu près).

La meilleure machine battrait cet humain sans aucun doute. Ce n’est pas pas discutable. Ni drôle. Donc on donne en 2020 un elo machine autour de 3500. Mais on pourrait donner 100 000.

Le problème d’un elo entre machines c’est que une machine plus forte qu’une autre peut jouer et gagner des millions de parties et augmenter son elo à volonté.

Ce qui est intéressant c’est la progression elo des machines. On verra dans combien de temps on atteint les 5 000. En 1950, c’était 1000. En 1990, c’était 2200. En 2020, c’est 3500.

Petite question complément inutile :
Quand on teste une IA contre une autre IA aux échecs, avec de puissants processeurs, une partie doit durer très peu de temps j’imagine.
Quelqu’un a une idée de ça ? De la durée moyenne d’une partie aujourd’hui ?
On peut même se passer de graphisme, ce sont juste des codes qui tournent et qui à la fin indiquent qui a gagné.

Suis-je à côté de la plaque ?

J’utilise « IA » de manière très naïve, un peu dans une expression du langage courant.

Bonjour,

@gilles benson : il est naturel de considérer que le niveau elo du meilleur humain augmente avec le temps. D’une part c’est une fonction nécessairement croissante, d’autre part les joueurs récents connaissent les parties de leurs prédécesseurs ET bénéficient de l’aide de l’AI (dont ils usent et abusent).

Donc on devrait voir un elo à 2900 bientôt.

@Dom : Avec les machines ont fait ce qu’on veut pour les programmer, y compris jouer des millions de parties dont on se fout. Puis quand on estime qu’on est prêt, on demande à jouer contre AlphaZero ou Leela.

On définit les règles : ordinateur de bureau, temps, processeurs et là encore, on s’en fout ou on polémique sans fin sur la validité de telle ou telle contrainte.

Puis on fixe les mêmes règles que dans un tournoi (souvent avec une limite de temps par coup, disons 5 minutes). Et là, on se fout des parties nulles (certains les étudient tout de même), et on ne retient que les parties où AlphaZero éviscère Leela. On analyse tous les coups. On découvre des pépites et des stratégies élégantes et originales.

Des fois AlphaZero s’éloigne des parties historiques très tôt et ça laisse les spécialistes bouche bée : les grands maîtres passent-ils à côté d’une solution optimale depuis 200 ans ? Il semble que oui avec certaines ouvertures...

J’ai vu l’analyse d’une partie où les coups sont surhumains. On ne voit pas le truc venir et, coup après coup, les pièces de l’adversaires sont rendues inopérantes (comme dans une camisole). C’est fabuleux.

Un humain ne peut pas vraiment décrire comment l'IA "pense". Le programme peut dépasser les 100 mégaoctets. Un cerveau humain ne peut pas reproduire les calculs de la machine.

Bonjour,

Il s’agit d’une stratégie. Sans aucun doute.

Les blancs commencent. Les noirs jouent l’ouverture connue. Et là, dés le coup 6, les blancs proposent un nouveau coup. Et coup après coup, on commence à voir le truc : les blancs cherchent avec succès à bloquer le déploiement des noirs. Si les noirs essaient d’y échapper, ils se retrouvent avec une position clairement inférieure (et contre AlphaZero ça ne pardonne pas). Et puis le piège est tendu, les noirs se retrouvent avec une tour, un fou et un cheval bloqués, inopérants. La partie est perdue (même s’il faut 8 coups supplémentaires pour le coup de grâce).

Alors on revient en arrière.

On se rend compte que le coup 6 est la préparation du piège.

Dans d’autres parties, c’est une autre stratégie qui est jouée : par exemple, AlphaZero pousse un pion en 5, puis 6 (très rapidement lors de l’ouverture). Toute la partie est alors centrée sur l’avancée en 7. Les noirs le savent. Contrent sans erreur (ce qui est une prouesse). Mais aux coups 23, les noirs abandonnent : c’est l’avancée en 7 qui gagne ou une pièce sacrifiée pour l’empêcher.

Donc la stratégie est jouée dés l’ouverture.

Une dernière : ouverture connue, 7 premiers coups connus. Et là au coup 8, AlphaZero semble déconner : il éclate les pions de son petit roque avec une avancée en 4 du pion central. N’importe quel joueur sait que c’est une connerie, jamais jouée en tournoi. Ni même en famille : qui détruirait ainsi le roque dès le début ?
Pourtant, c’est le premier coup d’une attaque en règle du roque adverse. Les noirs ne peuvent se défendre efficacement parce que leurs pièces sont de l’autre côté de l’échiquier. Les blancs manquent aussi de pièces de ce côté mais ont et gardent un petit avantage qui les mène à la victoire.

Du jamais vu.

L’éclatement du roque est joué si tôt parce qu’un coup plus tard permettrait aux noirs de déployer une pièce supplémentaire et de contrer l’attaque (qui serait suicidaire).

AlphaZero comprend les avantages et les défauts des positions. Et les exploitent à merveilles dés le début de la partie.

"Est-ce vraiment une stratégie dont tu parles ou bien est-ce « statistiquement je joue les meilleurs coups sans forcément anticiper les succès "

J'ai un peu de mal à voir la différence, la stratégie c'est justement rechercher le mieux mais sans aboutir à un gain forcé,
c'est ma position s'améliore, celle de mon adversaire se détériore,
et comment cela va finir je ne sais pas encore.
Dans les softs anciens la stratégie était donnée par l'homme si tour devant colonne ouverte ma fonction d'évaluation grimpe.
Les stats venaient de l'homme.

Dans le machine learning, la stratégie je ne vois pas comment elle pourrait ètre autre que statistiques, règles ici trouvées par la machine sur base de ses propres stats, non?

Ce qui m'a semblé est ceci, je ne sais pas si c'est vrai.
Avec le ZERO, la machine établit ses règles en jouant contre elle-même des parties avec du Monte-Carlo?.
Comme le départ est en équilibre, elle va tirer ses règles de forcer de petits déséquilibres de plus en plus.
Mais cela produit un jeu très positionnel de base. Une machine à gagner de l'espace comme alpha zero , son espace augmente , ses adversaires sont étouffés. Certaines parties cela ressemble à un jeu de go (que je ne connais pas).
Leela ZERO comme alpha ZERO c'était un apprentissage sans intervention de l'homme.
Idem super-positionnel. Plus imbattable que capable de battre des adversaires un peu moins forts.

Il ya eu un gars qui a repris la structure de base de Leela, mais avec de l'apprentissage dit supervisé je crois qu'ils disent.Bref il a fait apprendre la machine en la nourrissant des parties humaines il ya de fameuses bases de données des parties jouées par des pros humains.
Cela a donné un jeu plus agressif, plus attaquant. Et une machine qui n'est plus imbattable, mais qui sait mieux battre les adversaires qui lui sont inférieurs. Donc meilleurs résultats dans un tournoi multijoueurs, multimachines ici.
Et une année je crois les deux premiers étaient stockfish et un clone de Leela en apprentissage supervisé car il avait gagne plus de parties que le Leela zero qui n'avait concédé que tres peu de défaites mais avait annulé plus de machines plus faibles.Exit Leela de la finale cette année là.

Bonjour,

@AlainLyon : Tu répètes que les échecs sont à pièces et positions égales.

Je ne comprends pas.

Le roi et la reine ne sont pas placés aux mêmes endroits pour les blancs et les noirs.

Si on commence une partie et tu peints en blanc les noirs et en noir les blancs, je sais le dire. Les vrais blancs ont le roi à droite de la reine.C'est une différence de position, non ?

A propos des positons distinctes des blancs et des noirs.

A-t-on des données qui mettraient en doute l’équité des joueurs selon qu’il ait les blancs ou les noirs.
Les blancs commencent, c’est déjà inéquitable sans savoir où ça penche.

Une IA contre elle-même gagne-t-elle plus avec les blanches ou les noirs ?

Autre question de béotien : quand on teste une IA contre une autre, les parties ne sont pas les mêmes.
Est-ce seulement parce qu’elle « apprend » et que la dernière partie a « changé » l’IA ?
N’y a-t-il pas un morceau de code où de l’aléatoire s’en mêle ? (« Dans ce cas, choisir l’une ou l’autre des situations »).

https://fr.wikipedia.org/wiki/Avantage_du_trait_aux_échecs

C'est typique des amateurs (j'en suis un aussi, aucun jugement négatif). Très peu de nulles, encore moins de nulles en blitz. Et à peu près autant de victoires avec les blancs que les noirs. En parties longues (le standard des compétitons) chez des joueurs pros, la donne est toute autre. C'est ce qui faisait craindre à certains une mort à petit feu du jeu. Les avancées d'AlphaZero ont montré que le jeu était loin d'être mort et qu'il y avait largement de la place pour dépasser les 3500 elo, alors qu'il y a encore quelques années certains pensaient que le plafond était atteint et qu'on tendait vers la nulle systématique ou presque à ce niveau de jeu (qui certes reste non atteignable pour un humain).

Bon et sinon sauf si tu joues sur un site ultra confidentiel, je doute que ce soit le webmaster qui fasse le match making, ni aucun autre humain d'ailleurs ;-)

Ha non !
Inéquitable, dis-je, mais sans savoir dans quel sens ça penche.

On pourrait avoir "les noirs s'en prennent à la dame blanche". (Bienvenue chez les "Karen" !)

On peut aussi placer "un mat à l'étouffé", faisant écho à un triste évènement.