● Comment peut-on illustrer l’ampleur du nombre de parties possibles aux échecs?
★ introduction
Si je vous parle d’un jeu de société, l’un des plus anciens que notre société ait pu
connaître en faisant son apparition autour du 6e siècle, mais qui s’est imposé
seulement à la fin du 20e siècle, et qui oppose deux joueurs de part et d’autre d’un
échiquier? A quoi pensez-vous? Je pense que vous avez deviné, je parle bien des
échecs.
Ce jeu de stratégie ancien est basé sur un ensemble de règles simples, mais pourtant
conduisant à une immense complexité. Les 2 joueurs adverses déplacent leurs pièces
qui représentent 2 armées ennemies, chacun leur tour sur un échiquier composé d’une
grille carrée dessinant 64 cases, alternativement claires et sombres. Ces deux armées
ennemies sont représentées par 16 pièces par joueur, soit blanches soit noires. Parmi
ces 16 pièces, il y a 8 pions, 2 tours, 2 fous, 2 cavaliers, une dame et un roi. Pour
gagner le jeu, il faut faire échec et mat au roi adverse, c'est-à-dire le piéger pour qu’il
ne puisse plus bouger.
Pour que je puisse vous illustrer l’ampleur du nombre de parties possibles aux échecs,
je vais prendre pour appui de comparaison, l’estimation que l’on se fait du nombre
d’atomes dans l’univers observable.
★ présentation
Une partie d’échecs classique dure en moyenne 40 coups (un coup étant effectué
quand les deux joueurs ont chacun déplacé une pièce). Au premier coup, chaque
joueur a 20 possibilités (2 déplacements possibles pour chacun des 8 pions, et 2 pour
chacun des 2 cavaliers). Donc 16 possibilités pour les pions et 4 pour les cavaliers.
Après la réponse des noirs, car ce sont toujours les blancs qui commencent, le nombre
total de positions possibles au bout d’un coup complet est environ 400, après 3 coups
complets, il y a environ 120 000 positions possibles, après 4 coups, ce nombre dépasse
300 millions. Cette croissance exponentielle est caractéristique de nombreux jeux
combinatoires comme les échecs. Chaque coup ajoute des dizaines de branches à ce
qu’on appelle l’arbre des possibles.
★
Le nombre total de parties possibles aux échecs est souvent estimé à l’aide du nombre
de Shannon, qui donne une approximation de l’ensemble des parties jouables.
En 1950, Claude Shannon, considéré comme le père de la théorie de l'information,
publia un article fondateur intitulé "Programming a Computer for Playing Chess".
, Dans ce texte visionnaire, il ne se contente pas seulement de poser les bases du jeu
d’échecs sur ordinateur: il s'attelle également à estimer l’ampleur de l’univers des
possibles dans une partie d’échecs. L'un des calculs les plus célèbres qu’il y expose
donne la mesure vertigineuse de la complexité du jeu.
La première approximation que fait Shannon repose sur une estimation du nombre
moyen de coups qu’un joueur peut jouer à chaque tour. Il note que ce chiffre peut
varier considérablement selon la position allant de très peu dans les positions
bloquées, jusqu’à plusieurs dizaines dans les situations ouvertes. Shannon considère
une moyenne représentative de 30 coups légaux par position.
Ensuite, Shannon suppose qu’une partie typique d’échecs comprend environ 40 coups
par joueur, soit 80 demi-coups. Cette estimation tient compte du fait que certaines
parties peuvent être courtes tandis que d’autres peuvent durer plusieurs heures.
Fort de ces deux hypothèses, Shannon applique une formule simple pour estimer le
nombre total de parties différentes possibles. Si, à chaque coup, un joueur a en
moyenne 30 choix, et que la partie dure 80 demi-coups, alors le nombre total de
séquences possibles est donné par un calcul de dénombrement, qui concernent des
p-uplets.
Ce calcul représente une estimation grossière du nombre de chemins différents qu'une
partie peut emprunter, sans tenir compte des répétitions, des fins prématurées, ou
encore des règles spécifiques (comme la règle des 50 coups ou la triple répétition).
Pour donner un ordre de grandeur de ce chiffre indécent et gigantesque, Shannon
utilise les logarithmes décimaux.
★ introduction
Si je vous parle d’un jeu de société, l’un des plus anciens que notre société ait pu
connaître en faisant son apparition autour du 6e siècle, mais qui s’est imposé
seulement à la fin du 20e siècle, et qui oppose deux joueurs de part et d’autre d’un
échiquier? A quoi pensez-vous? Je pense que vous avez deviné, je parle bien des
échecs.
Ce jeu de stratégie ancien est basé sur un ensemble de règles simples, mais pourtant
conduisant à une immense complexité. Les 2 joueurs adverses déplacent leurs pièces
qui représentent 2 armées ennemies, chacun leur tour sur un échiquier composé d’une
grille carrée dessinant 64 cases, alternativement claires et sombres. Ces deux armées
ennemies sont représentées par 16 pièces par joueur, soit blanches soit noires. Parmi
ces 16 pièces, il y a 8 pions, 2 tours, 2 fous, 2 cavaliers, une dame et un roi. Pour
gagner le jeu, il faut faire échec et mat au roi adverse, c'est-à-dire le piéger pour qu’il
ne puisse plus bouger.
Pour que je puisse vous illustrer l’ampleur du nombre de parties possibles aux échecs,
je vais prendre pour appui de comparaison, l’estimation que l’on se fait du nombre
d’atomes dans l’univers observable.
★ présentation
Une partie d’échecs classique dure en moyenne 40 coups (un coup étant effectué
quand les deux joueurs ont chacun déplacé une pièce). Au premier coup, chaque
joueur a 20 possibilités (2 déplacements possibles pour chacun des 8 pions, et 2 pour
chacun des 2 cavaliers). Donc 16 possibilités pour les pions et 4 pour les cavaliers.
Après la réponse des noirs, car ce sont toujours les blancs qui commencent, le nombre
total de positions possibles au bout d’un coup complet est environ 400, après 3 coups
complets, il y a environ 120 000 positions possibles, après 4 coups, ce nombre dépasse
300 millions. Cette croissance exponentielle est caractéristique de nombreux jeux
combinatoires comme les échecs. Chaque coup ajoute des dizaines de branches à ce
qu’on appelle l’arbre des possibles.
★
Le nombre total de parties possibles aux échecs est souvent estimé à l’aide du nombre
de Shannon, qui donne une approximation de l’ensemble des parties jouables.
En 1950, Claude Shannon, considéré comme le père de la théorie de l'information,
publia un article fondateur intitulé "Programming a Computer for Playing Chess".
, Dans ce texte visionnaire, il ne se contente pas seulement de poser les bases du jeu
d’échecs sur ordinateur: il s'attelle également à estimer l’ampleur de l’univers des
possibles dans une partie d’échecs. L'un des calculs les plus célèbres qu’il y expose
donne la mesure vertigineuse de la complexité du jeu.
La première approximation que fait Shannon repose sur une estimation du nombre
moyen de coups qu’un joueur peut jouer à chaque tour. Il note que ce chiffre peut
varier considérablement selon la position allant de très peu dans les positions
bloquées, jusqu’à plusieurs dizaines dans les situations ouvertes. Shannon considère
une moyenne représentative de 30 coups légaux par position.
Ensuite, Shannon suppose qu’une partie typique d’échecs comprend environ 40 coups
par joueur, soit 80 demi-coups. Cette estimation tient compte du fait que certaines
parties peuvent être courtes tandis que d’autres peuvent durer plusieurs heures.
Fort de ces deux hypothèses, Shannon applique une formule simple pour estimer le
nombre total de parties différentes possibles. Si, à chaque coup, un joueur a en
moyenne 30 choix, et que la partie dure 80 demi-coups, alors le nombre total de
séquences possibles est donné par un calcul de dénombrement, qui concernent des
p-uplets.
Ce calcul représente une estimation grossière du nombre de chemins différents qu'une
partie peut emprunter, sans tenir compte des répétitions, des fins prématurées, ou
encore des règles spécifiques (comme la règle des 50 coups ou la triple répétition).
Pour donner un ordre de grandeur de ce chiffre indécent et gigantesque, Shannon
utilise les logarithmes décimaux.
