jouer à raisonner, échecs: solutions du jeu

NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 20/08/2023 Orientation générale DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Jeux et problèmes
Débutants Général	ÉCHECS			Glossaire Général
INDEX Jeux	Introduction & invention	Solutions	Cavalier	Dame / Reine
		Pavage		Fou
		Sommaire de cette page >>> Nombre de parties >>> Calcul d'un mouvement >>> Échecs et Edgar Poe >>> Ordinateurs et échecs >>> Programmation – Méthodes et comparaison >>> Échecs terrestres >>> Ordinateurs et autres jeux voisins: dames, go >>> Bridge

Le joueur d'échecs est brillant ou mat.

Aux échecs, si le roi ne peut plus bouger sans se faire prendre il est mat. Il y a échec et mat. Le joueur ayant ainsi immobilisé le roi est le vainqueur de la partie.

Étymologie: Cheikh mat (arabe) veut dire le roi est mort ou alors, Shah mat (persan), le roi est pris.

Voir Pensées & humour

Échecs et autres jeux

Solutions par ordinateurs?

Combien de parties possibles?
Humains contre ordinateurs …

NOMBRE DE PARTIES
Quantité de positions légales	10⁴³ à 10⁴⁷
Quantité de mouvements à partir d'une position	De 0 à 218 Moyenne 36
Quantité de parties possibles aux échecs: Cette valeur estimée par Shannon en 1950 est la limite basse (nombre de Shannon)	> 10¹²⁰
D'autres estimations plus récentes donnent: Une autre source donnait:	10¹²³ 10¹²⁸
Quantité de mouvements après que chaque joueur a joué cinq fois.	4 897 256
Avec 100 nanosecondes pour examiner chaque situation pour jouer un coup, il faudrait 3 x 10¹¹² années de calcul pour une seule partie. En aucun cas, un programme pour jeu d'échecs ne peut être exhaustif (algorithmique). Il faut faire des choix arbitraires correspondant à des paris intuitifs (heuristiques). Évidemment ce choix n'est pas infaillible! Certains joueurs d'échecs affirment qu'une part de leur talent n'est ni algorithmique, ni heuristique, mais c'est une part qui progresse dans l'obscurité, dans le non-identifiable et jaillit soudain sous forme d'une *illumination*.

Voir Suite pour jeux voisins

CALCUL D'UN MOUVEMENT

Pour une position, il y a en moyenne 36 coups possibles.
Une anticipation de 11 coups nécessiterait
36¹¹ (soit: 1,7 10¹⁶) possibilités à examiner.

Ce qui est beaucoup trop pour la puissance de calcul des ordinateurs d'aujourd'hui. En effet, avec un milliard de coups par seconde, il faudrait 6 mois pour proposer un mouvement!

Le joueur d’échecs de Maelzel

Edgar Poe (1809-1849) a écrit le joueur d’échecs de Maelzel en 1836 relatant une sorte d’arnaque aux échecs: une petite machine, présentée comme un automate joueur d’échecs, dans laquelle est en réalité caché un nain.

La machine de Babbage (1834) existait déjà et Edgar Poe se pose la question: est-ce plus facile de concevoir une machine qui calcule ou une machine qui sait jouer aux échecs?

Il n’y a pour lui absolument aucun doute, aucune analogie entre la calculette de Babbage et un automate joueur d’échecs: la machine qui joue aux échecs est infiniment plus compliquée à construire.

Aux échecs, il n’y a pas de marche déterminée, il y a une part d’incertitude liée à l’adversaire. Pour Poe, une machine qui joue aux échecs est impossible. Il est impossible, écrit-il, qu’une telle machine existe et si elle existait, ce serait "la plus extraordinaire invention de l’humanité".

D'après: Pourquoi apprendre à programmer avec des robots ? – Thierry Klein – 12/01/2018

ORDINATEURS et ÉCHECS
1960	MENACE	Donald Michie met au point la Machine Educable Noughts And Crosses Engine qui sait jouer au tic-tact-toe. En fait, faute d'ordinateur à cette époque, il simule le jeu avec des boites d'allumettes.
1967	Programme d'échecs	Le premier programme à atteindre un bon niveau de jeu par Richard Greenblatt.
1989	Ordinateur dédié	IBM étudie un ordinateur spécifique pour jouer aux échecs.
11 mai 1997	Deeper Blue Ordinateur IBM 200 millions de combinaisons par seconde	Bat Garry Kasparov le champion du monde d'échecs pendant 15 ans (score 3 ½ à 2 ½) Voir Histoire des robots
Juillet 1999	Programme Fritz sur machine Siemens	Il est battu par le champion d'échecs indien Viswanathan Anand. Celui-ci, âgé de 29 ans, est surnommé le Tigre de Madras. Il est numéro deux mondial derrière le vétéran russe Anatoly Karpov au classement de la Fédération internationale d'échecs (FIDE) dont Garry Kasparov est exclu depuis 1993.
*Plus tard!*	Deeper Blue IV	Imaginé par Bernard Werber dans son roman: L'ultime secret
*19 octobre 2002*	Deep Fritz 4 millions de combinaisons par seconde	Match nul 4 à 4 avec Vladimir Kramnik (27 ans). Il a gagné 0,8 M$ (il aurait gagné 1 M$ en cas de victoire). Vladimir Kramnik est l'actuel champion du monde d'échecs. Il a battu Garry Kasparov en 2000. Il est surnommé Monsieur Iceberg pour son extraordinaire sang-froid.
*2004 ?*	Blue Gene IBM = 1000 Deep Blue	Annoncé en 1999 Investissement de 100 millions de dollars Plus d'1 million de processeurs ultra-rapides, chacun est capable d'effectuer 1 milliard d'opérations par seconde. Un million de milliards d'opérations par seconde (soit un péta-flop).
*2005*	Hydra 32 processeurs	Bat Adams 5,5 à 0,5, le n°7 mondial britannique.
*2006*		Le champion du monde, Vladimir Kramnik, s’est incliné une machine, non sans avoir lutté 5 heures durant, en 47 coups.
?	1 milliard de combinaisons par seconde	Avec cette puissance, la machine bat l'homme systématiquement. Elle correspond à l'exploration d'environ 14 coups d'avance.
*15 mars 2016*	Programme AlphaGo	L'ordinateur bat le champion du monde 4 manches à 1.
*2017*	Une étape supplémentaire!	Le meilleur joueur atteint un niveau ELO de 2 800 points alors que l'ordinateur est à 3 300 points et continue de progresser. Le successeur d'AlphaGo, AlphaZero a pu en 9 heures devenir le meilleur programme d'échecs capable d'infliger au programme StockFish, champion du monde 2016 d'échecs, un score de 28 gains contre 0 sur cent parties. Dans la même journée, Alphazero est devenu le programme le plus puissant au Go et au ShOGI.

Voir Chronologie complète (anglais) / Actualités

Comparaison

Deep Blue (1996)

Le programme comprend:

une bibliothèque d'ouvertures qui résulte de la compilation d'un grand nombre de parties jouées dans le passé,

un milieu de partie ou le calcul pur est mis au service d'un algorithme alpha beta, et

des fonctions d'évaluation des positions obtenues à l'horizon du calculable.

AlphaZero (2017)

Seules sont implémentées les règles du jeu, et c'est

Le deep learning et les ajustements automatiques des réseaux neuronaux qui font le reste.

Le programme devient opérationnel après un apprentissage durant lequel la machine se forge sa logique propre. >>>.

Voir Programmation – Les trois méthodes fondamentales

En 1980, personne ne pensait que la machine battrait l'homme avant l'an 2000.
Même si la puissance de calcul des machines du commerce sont très loin de la puissance de Deeper Blue, elles sont capables de battre 99% des joueurs.

Avec cette victoire sur le champion du monde, la machine a brutalement séparé les échecs de leur prestige. Du coup, ces 64 cases de l'échiquier ne deviennent plus qu'un ingénieux passe-temps.

IBM a mis Deeper Blue à la retraite en septembre 97. Il n'y a pas de revanche programmée. Personne n'est intéressé à combattre contre un machine, sauf comme dans le cas de Kasparov, à mettre en jeu une très importante récompense y compris en cas de défaite.

En 2010, la supériorité de la machine sur l'homme aux échecs semble acquise. Pourtant, même les meilleurs programmes ne sont pas encore infaillibles. À partir de la défaite de Kasparov en 1997, les spécialistes ont considéré que c'était fini.

Aujourd'hui, les microordinateurs atteignent 20 millions de coups par seconde, dix fois moins que Deep Blue, mais c'est suffisant pour que la machine ne fasse aucune erreur tactique et exploite celles inévitables de son adversaire humain.

Par contre, la machine reste moins forte que l'homme au niveau stratégique: vision d'ensemble du jeu, intelligence de la position.

Certes, si on organisait des matches demain, tous les meilleurs joueurs seraient probablement battus. Toutefois, jouer contre l'ordinateur n'intéresse pas les grands maîtres.

D'après Pierre Nolot, spécialiste des échecs et des programmes de jeu, journaliste et auteur de manuels d'échecs. Le Monde 22/09/2009

Déontologie Homme-machine :

Pourquoi faut-il renoncer aux machines aux concours d'échecs ?

- aucune autre disciple sportive ne fait concourir simultanément hommes et machines,

- entre hommes et programmes, les chances ne sont pas égales : un logiciel ne se fatigue pas,

- la machine dispose de bases de données et n'a pas besoin de s'entraîner,

- le succès des machines met en péril l'existence même du jeu d'échecs par les humains,

- etc.

Selon Joël Lautier, un des meilleurs joueurs français.

Note: le Champion de France s'appelle Etienne Bacrot –20 ans - 5 ans de suite

ÉCHECS TERRESTRES
10⁹³ = Limite de Bremermann Un calculateur de la taille de la Terre et, ayant travaillé depuis son origine à la vitesse maximum théorique, n'auraient pas encore identifié toutes les parties d'un jeu d'échecs. C'est Hans Bremermann, Université de Berkeley qui a démontré ce fait. en 1962.
Raisonnement basé sur la mécanique quantique, pour un gramme de matière:	2 x 10⁴⁷ bits / seconde
Avec la masse de la Terre:	5,9 x 10²⁷ g
Âge de la Terre:	4,56 x 10⁹ ans
Secondes dans une année	3,1 556 926 10⁷
" Calculateur " Terre depuis sa création:	1,7 10⁹² soit en arrondissant: 10⁹³ bits / seconde
Nombre de parties dans un jeu d'échecs:	10¹²⁰ (selon un calcul Shannon).
Rapport "parties / calculateur Terre"	10²⁷
Pour calculer toutes les parties d'échecs, il faudrait un calculateur:	³ 10²⁷ = 10⁹ fois plus gros.
Rapport Soleil / Terre en volume	1,3 10⁶
Soleil à la place de la Terre:	Il faudrait 1000 fois plus gros.
Rapport orbite Terre sur Soleil " en volume"	1,26 10⁶
Calculateur de la taille de l'orbite terrestre:	Alors, il fait 1000 fois les calculs.

Voir Nombres voisins

Autres jeux

Nombres de possibilités aux jeux voisins

10¹²	Awélé	12 trous	48 graines
10³²	Dames	100 cases	2 x 20 pions noirs et blancs
10⁶⁰	Othello	64 cases	64 pions bicolores
10¹²⁸	Échecs	64 cases	2 x 16 pièces noires et blanches
10¹⁷²	Go	361 points d'intersection	180 pierres blanches 181 pierres noires

Voir Nombres voisins

Sur ordinateurs

Awélé	Toutes les parties sont connues: 889 063 398 406 possibilités exactement.
Puissance 4	Toutes les positions possibles (4 531 985 219 092) sont analysées en 1995. En 1988, James Allen et Victor Allis avaient montré que le joueur qui commence peut gagner
Hex	Stratégie gagnante par Nash en 1948; démonstration plus simple par David Gale, collègue de Nash à Princeton.
Dames anglaises 8 x 8	Les ordinateurs surpassent généralement les champions. Malgré tout, le meilleur programme en 2001 (du Français Guibert) a perdu contre le 11^e joueur mondial. En 2007, une équipe de l'Université de l'Alberta (Canada) a résolu le jeu de dames sur ordinateurs. L'ordinateur est assuré d'obtenir une partie nulle, qu'il joue avec les noirs ou les blancs.
Othello	Programmes très forts, mais pas de challengers à niveau En 1997, un programme (Logistello, crée par Michael Buro en 1992) bat le champion du monde, Takeshi Murakami, sans appel.
Échecs	Programmes au niveau des plus forts mondiaux. Seuls une dizaine de joueurs peuvent rivaliser.
Go	Programmes du niveau d'un faible joueur amateur. Cependant, en mars 2008, un ordinateur (superordinateur Bull) bat un professionnel pour la première fois. Version réduite du plateau (9x9). Suite (deux nouvelles importantes en janvier 2016, développements en Jeux de société – GO
Bridge	Programmes ne dépassent pas le niveau débutant. Le nombre de mains au bridge est de 635 milliards: c'est la quantité de façons de prendre 13 cartes parmi 52, soit 52! / (13! x 39!) = 635 013 559 600 = 6,3 10¹¹. Pour les jeux de plateaux (Échecs, Go), l'ordinateur dispose de la totalité des informations au départ. La difficulté est combinatoire (nombre de combinaisons possibles). Avec le bridge ou le poker, il faut compter sur les annonces, les enchères. C'est encore plus difficile. En 2016, le programme français Wbridge5 a remporté le championnat du monde robotique. Depuis 2016, les Taïwanais essaient le deep learning, technique qui a réussi pour vaincre le champion du monde de Go. Voir Logiciel de bridge – Wikipédia / L'Intelligence Artificielle et le Bridge – Philippe Pionchon
Poker	Programme quasi infaillible en janvier 2015 pour parties à deux joueurs, puis quatre en 2019 >>>
Rubik's Cube	Résolution en 1, 2 s par une IA en 2019 >>>

Voir Histoire des robots / Test du QI et ordinateurs

Nomenclature des jeux

Jeux à information complète				Jeux à information partielle
Jeux fortement résolus	Jeux faiblement résolus	Jeux faiblement résolus	Jeux hors catégorie	Jeux à information partielle
Toutes les positions explorées par ordinateur.	Position initiale connue et accès à une stratégie gagnante.	La position initiale est gagnante.	Quantité de combinaisons hors d'atteinte des ordinateurs.	Le jeu de l'adversaire est inconnu.
Puissance 4, Échecs (< 8 pièces)	Dames 8 x 8	Hex	Dames 10 x 10 Échecs Go	Poker

Voir Théorie des jeux

Suite	Pavage de l'échiquier Cavalier Voir haut de page
Voir	Intelligence artificielle Jeux et énigmes – Index Morpion solitaire Pentominos Théorie des jeux
Livre	Sciences et vie de décembre 2002: L'échec de l'intelligence artificielle.
Site	L'univers des échecs - F. Leysour de Rohello Le fou numérique – Site des échecs électroniques Human-computer chess matches – Wikipedia Chess engine – Wikipedia
Cette page	http://villemin.gerard.free.fr/Puzzle/EchecSol.htm