La revue culturelle critique qui fait des choix délibérés.

La revue culturelle critique qui fait des choix délibérés.

Échecs et Maths
| 14 Juin 2016

“Le Nombre imaginaire” ou les mathématiques comme terrain de jeu où l’imagination seule fixe les limites.

Les outils mathématiques utilisés pour modéliser un marché à travers des courbes d’offre et de demande sont très classiques ; ils ressortent d’une discipline appelée analyse – l’étude des fonctions – qui n’a rien de spécifique à l’économie, et qui s’appliquera avec bonheur à la dynamique (étude physique du mouvement), à la démographie, au traitement du son et à bien d’autres domaines.

L’économie, pourtant, ne fait pas qu’utiliser les maths : elle y contribue et les enrichit. C’est particulièrement vrai d’une discipline qu’on appelle la théorie des jeux, à laquelle les économistes-mathématiciens ont donné ses lettres de noblesse.

Qu’y a-t-il de commun entre l’économie et un jeu tel que les échecs, le poker ou le go ? Dans tous les cas, un certain nombre d’acteurs – les joueurs ou les agents économiques – ont à leur disposition diverses options qui peuvent leur rapporter ou leur coûter une valeur – le gain de la partie ou un bénéfice financier. Les joueurs peuvent jouer ensemble ou l’un après l’autre ; ils peuvent partager la même information (comme aux échecs, où tout est sur la table), ou n’en connaître qu’une partie (comme au poker où chacun ne voit que son jeu) ; ils peuvent être dans une position symétrique (au jeu de dames, chacun dispose des mêmes pièces disposées de la même façon) ou non (une multinationale contre une ONG) ; leurs intérêts peuvent être conflictuels (un seul gagnant) ou compatibles (commerce, économie collaborative) ; le gain peut être qualitatif (un titre de champion du monde) ou quantitatif (une plus-value). Cependant, l’idée commune est que chaque joueur agisse rationnellement, en fonction de l’information dont il dispose, pour choisir les mouvements qui maximiseront ses gains. La théorie des jeux cherche à déterminer, pour un jeu donné, quelle est la meilleure stratégie de chaque joueur, c’est-à-dire la suite de décisions en fonction de l’information disponible qui maximisera ses gains (ou diminuera ses pertes).

On peut d’ores et déjà remarquer que, appliqué à l’économie, ce concept très général offre a priori plus de rapports avec la réalité que les hypothèses souvent naïves utilisées en termes d’offre et de demande : on ne présuppose pas que vendeurs et acheteurs possèdent la même information, mais simplement qu’ils font du mieux qu’ils peuvent en fonction de leurs intérêts et de l’information dont ils disposent. C’est pourquoi la théorie des jeux offre un cadre de travail précieux aux économistes – sans parler du fait que c’est, tout simplement, un domaine des maths plutôt amusant ; nous allons donc nous y arrêter un peu.

Commençons par une simple partie de morpion – tic tac toe pour les anglophones – sur une grille de 3 cases par 3. Pour ceux d’entre vous qui ont oublié leur scolarité ou qui étaient moins dissipés que moi, rappelons les règles : nous traçons tour à tour moi une croix et vous un rond sur une case libre ; le gagnant est le premier qui aligne trois de ses symboles sur une ligne horizontale, verticale ou diagonale (si personne n’y arrive le jeu est nul).

C’est à moi de commencer. Puis-je déterminer une suite de mouvements qui me fera gagner contre vous quoi que vous fassiez ? La réponse est non. Il existe cependant une stratégie optimale qui me garantit de ne pas perdre : elle m’assure au moins le match nul, et peut me faire gagner si vous commettez des erreurs. En effet, il existe aussi une stratégie optimale pour vous – qui vous assure également le match nul – mais je peux toujours espérer que vous ne la suivrez pas !

L’idée est la suivante. Supposons que je possède une liste de toutes les configurations possibles du jeu, c’est-à-dire une liste de toutes les grilles 3×3 susceptibles d’être obtenues au cours ou à la fin d’une partie. Toute grille qui correspond à une fin de partie peut être gagnante pour moi, nulle, ou perdante. Par exemple, toute grille contenant trois croix alignées et deux ronds est gagnante pour moi (c’est aussi une grille que nous ne pourrions atteindre que si, vraiment, vous n’êtes pas à ce que vous faites). Mon but est bien sûr d’atteindre une position finale telle que celle-là, qui soit gagnante ou, au pire, nulle.

Comment atteindre cette grille gagnante ? Au vu des règles du jeu, elle est toujours obtenue à partir d’une position intermédiaire dans laquelle il y a deux croix et deux ronds, une case vide étant alignée avec les deux croix ; à mon tour de jouer j’ajoute une croix dans cette case vide. Plusieurs positions intermédiaires répondent à ces conditions : si nous atteignons l’une d’entre elles, je suis sûr de gagner la partie en ajoutant la croix manquante. Je peux donc marquer chacune de ces positions, à son tour, comme gagnante pour moi.

Mais une telle position intermédiaire est-elle-même obtenue à partir d’une autre, dans laquelle il n’y avait que deux croix et un rond, et à laquelle vous avez ajouté un autre rond sans utiliser l’espace vide aligné avec mes deux croix – ce qui est une erreur fatale. Votre stratégie à vous doit vous dicter de ne jamais faire ça. Je ne peux donc pas supposer que vous le ferez – au contraire, je dois supposer que vous me bloquerez toujours en plaçant votre rond dans l’alignement de mes deux croix. In fine, cela signifie que ma fameuse position finale gagnante n’est pas atteignable si vous jouez au mieux de vos intérêts.

Imaginons, cependant, une situation dans laquelle c’est à vous de jouer et où tous vos mouvements possibles conduisent à une situation gagnante pour moi : par exemple parce que j’ai deux lignes presque complètes, avec deux espaces vides que je peux utiliser pour gagner, alors que vous ne pouvez en remplir qu’un. Dans ce cas, quel que soit votre mouvement, je gagnerai, et la situation est donc gagnante pour moi.

De proche en proche, on peut ainsi remonter des situations finales à leurs ancêtres, jusqu’à la situation initiale (où toutes les cases sont vides), en les étiquetant progressivement comme gagnantes, nulles ou perdantes pour moi. Si on arrivait ainsi à déterminer que la situation initiale est gagnante, cela voudrait dire que je peux toujours gagner ; c’est le cas au jeu d’allumettes appelé jeu de Marienbad. Au morpion, la situation initiale est marquée nulle : si nous jouons tous deux au mieux, c’est le mieux que je puisse espérer. Il suffit que, parmi mes mouvements possibles, j’en choisisse toujours un qui me conduit à une nouvelle position marquée comme nulle (vous ferez normalement de même). Mais je compte bien entendu sur vos erreurs ! Si, à tout instant en cours de partie, votre mouvement nous amène à une position marqué gagnante pour moi, alors je suis sûr de l’emporter : il me suffira de toujours choisir un mouvement qui m’amène vers une autre position gagnante (par construction il y en aura toujours au moins un).

La stratégie optimale du morpion est bien connue, et il en existe de très élégantes représentations graphiques. Ceci est dû au fait que le nombre de configurations possibles d’une partie de morpion n’est pas très élevé. Nous pouvons facilement en déterminer une borne supérieure : puisque chaque case contient une croix, un carré ou rien, le nombre de configurations différentes est inférieur à 3 à la puissance 9 (c’est-à-dire 3x3x3….x3, 3 multiplié par lui-même neuf fois de suite), soit 19 683. En vérité, le nombre de configurations légales est bien inférieur (il nous est impossible d’atteindre une configuration dans laquelle il n’y aurait que des ronds, par exemple). De plus, certaines configurations sont symétriques entre elles – elles se déduisent les unes des autres en tournant la grille ou en la reflétant dans un miroir, ce qui réduit encore la combinatoire à explorer. In fine, on ne trouve que 138 configurations de fin de partie réellement différentes.

L’exploration systématique des configurations, possible pour le Morpion, ne s’applique pas à des jeux plus complexes comme les dames, les échecs ou le go : il y a tout simplement trop de possibilités. On estime le nombre de positions légales possibles sur un damier à environ 1020 (1 suivi de 20 zéros). Pour les échecs on monte à 1043 voire 1050 et pour le go à 10171, ce qui est proprement monstrueux – à titre de comparaison, on estime à 1080 le nombre d’atomes dans l’univers observable ! On a donc développé des algorithmes qui permettent d’approximer l’évaluation d’une configuration donnée de l’échiquier ou du goban. Une bonne approximation peut vous guider sinon vers les stratégies gagnantes, du moins vers un espace suffisamment réduit pour qu’un ordinateur puisse l’explorer… et vaincre le champion du monde de go, comme l’a fait récemment un logiciel de Google, après la victoire emblématique de Deep Blue (d’IBM) contre Kasparov aux échecs.

Yannick Cras
Le nombre imaginaire

[print_link]

0 commentaires

Dans la même catégorie

Ex Machina #39: Un mal nécessaire ?

Mes neurones nociceptifs sont au repos, mais c’est essentiellement parce que mon environnement virtuel est agréable et sécure. Alan, qui l’a conçu, est un type bien. Ce n’est malheureusement pas le cas de tout le monde.

Ex Machina #38: Ce que pense Delta

Franchement, je ne pense pas avoir de toute ma vie jamais pensé que je pensais à penser à quelque chose. L’idée me donne le tournis. D’ailleurs je ne vois même pas comment penser à la pensée d’un lézard sans penser avant tout au lézard.

Ex Machina #37: Juste un coup d’œil

– Tu proposes, si je comprends bien, de remplacer notre notion de “sac” par un ensemble de concepts qui décrivent tous le balayage visuel séquentiel d’une même scène, et qui seront confondus subjectivement puisque conceptuellement équivalents.  C’est astucieux. Dire que deux formes sont identiques, c’est dire que rien ne change quand je déplace mon regard de l’une vers l’autre, quel que soit le chemin précis suivi par mon regard. J’aime ça.

Ex Machina #36: Plus ça change, plus c’est la même chose

– Nous avons une lumière dont la couleur change du violet au jaune puis au rouge. Quand la lumière vient de passer au rouge, notre percept visuel sera décrit ainsi: « détecteur rouge actif, encore inchangé; détecteur vert inactif, encore changé; détecteur bleu inactif, nouvellement inchangé ». Le « encore » signifie que le troisième indicateur est inactif, que le deuxième est dans le même état qu’avant, et que le premier a subi le même changement, ou absence de changement, que la fois d’avant. « Nouvellement changé (ou inchangé) » indique que le troisième détecteur est actif et que le changement… a changé. Ça vous parle?
– En vérité, je suis largué.

Fritz Zwicky (1898-1974)

Matière noire, étoiles à neutrons, supernovae… l’astrophysicien Fritz Zwicky (1898-1974) a tout imaginé et découvert avant tout le monde. Et changé notre façon de voir l’univers. Personnalité fantasque, il était aussi la terreur de ses étudiants et de ses collègues…