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

1043 à 1047

*    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)

> 10120

*    D'autres estimations plus récentes donnent:

Une autre source donnait:

10123

10128

*    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 10112 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 
                     3611 (soit: 1,7 1016) 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

 

1093 = 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 1047 bits / seconde

*    Avec la masse de la Terre:

5,9 x 1027 g

*    Âge de la Terre:

4,56 x 109 ans

*    Secondes dans une année

3,1 556 926 107

*    " Calculateur " Terre depuis sa création:

1,7 1092 soit en arrondissant:

1093 bits / seconde

*    Nombre de parties dans un jeu d'échecs:

10120 (selon un calcul Shannon).

*    Rapport "parties / calculateur Terre"

1027

*    Pour calculer toutes les parties d'échecs, il faudrait un calculateur:

3 1027 = 109 fois plus gros.

*    Rapport Soleil / Terre en volume

1,3 106

*    Soleil à la place de la Terre:

Il faudrait 1000 fois plus gros.

*    Rapport orbite Terre sur Soleil " en volume"

1,26 106

*    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 12

Awélé

12 trous

48 graines

10 32

Dames

100 cases

2 x 20 pions noirs et blancs

10 60

Othello

64 cases

64 pions bicolores

10 128

Échecs

64 cases

2 x 16 pièces noires et blanches

10 172

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 11e 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 1011.

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

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 énigmesIndex

*         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