Qu’est-ce qu’un jeu pour un mathématicien ?

Théorie des jeux, partie 1 sur 9

Pendant la Seconde Guerre mondiale, dans un taxi londonien, le mathématicien John von Neumann confie à son compagnon de route, Jacob Bronowski, une idée étrange : les échecs ne sont pas un jeu. Selon lui, les échecs sont une forme de calcul parfaitement définie : dans n’importe quelle position, il existe en théorie un bon coup, même si personne n’est capable de le trouver. Les vrais jeux, comme la vraie vie, sont faits de bluff, de petites ruses et d’une question permanente : « Que pense l’autre que je vais faire ? » C’est ainsi que Bronowski se souvient de cette conversation dans L’Ascension de l’homme (1973) : un souvenir, pas une transcription.

Pour qui aime les échecs, la formule peut sembler presque provocante. Mais la théorie des jeux commence précisément par ce genre de distinctions. Von Neumann en a démontré le premier théorème clé en 1928, puis en a fait une discipline à part entière avec l’économiste Oskar Morgenstern dans Theory of Games and Economic Behavior (1944). Dans cette série, nous irons de l’échiquier à la négociation et à la confiance. Commençons par une question simple : qu’est-ce qu’un mathématicien appelle un « jeu » ?

Les trois ingrédients de tout jeu

Pour un mathématicien, un jeu est toute situation où le résultat dépend des décisions de plusieurs participants, et où chacun le sait. Les échecs entrent dans cette définition, mais aussi une enchère, la négociation du prix d’un appartement, ou même la décision de laisser passer une voiture à un carrefour.

Pour décrire un jeu, il faut trois choses :

• Les joueurs : ceux qui décident. Une personne, une entreprise, un pays, un programme.
• Les stratégies : toutes les conduites possibles pour chaque joueur.
• Les gains : ce que chacun obtient pour chaque combinaison de décisions. Des points, de l’argent, une victoire ou une défaite.

L’exemple le plus simple est pierre-feuille-ciseaux. Deux joueurs, trois options chacun, et tout le jeu tient dans un tableau. Chaque case indique le gain du joueur A : 1 pour une victoire, −1 pour une défaite, 0 pour une égalité.

Le gain du joueur B est toujours le même nombre, de signe opposé. On appelle ces jeux des jeux à somme nulle : ce que l’un gagne, l’autre le perd. Les échecs, les dames et le go en font partie. La plupart des situations de la vie, non, et ce sont elles qui occuperont les prochains épisodes de la série.

Une stratégie n’est pas un coup

Dans la langue courante, une « stratégie » est une idée générale : « je vais jouer défensivement ». En théorie des jeux, c’est un mode d’emploi complet : que faire dans chaque situation qui peut se présenter, y compris celles dont on est sûr qu’elles n’arriveront jamais.

Prenons un jeu auquel on peut jouer avec n’importe qui, tout de suite (exemple pédagogique). Dix allumettes sont posées sur la table. À tour de rôle, chaque joueur en retire une ou deux. Celui qui prend la dernière gagne. Les mathématiciens parlent d’un jeu de soustraction, proche cousin du jeu de Nim ; beaucoup le connaissent aussi par le jeu des bâtonnets de Fort Boyard, une variante proche.

Essayons de le résoudre en partant de la fin :

1. Il reste une ou deux allumettes devant vous : vous prenez tout et vous gagnez.
2. Il en reste trois : vous avez perdu, car quoi que vous preniez, l’adversaire prend le reste.
3. Il en reste quatre ou cinq : vous en laissez trois à l’adversaire, et vous gagnez.
4. Il en reste six : nouveau piège, tout coup laisse quatre ou cinq à l’adversaire.

La règle apparaît : les positions perdantes sont les multiples de 3. Avec dix allumettes, le premier joueur en prend donc une et en laisse neuf. Ensuite, il complète toujours le coup de l’adversaire jusqu’à trois : si l’autre en prend une, il en prend deux ; s’il en prend deux, il en prend une. La victoire est assurée, quoi que fasse le second joueur.

Voilà une stratégie au sens mathématique : une règle qui donne une réponse à toute position. Et la méthode employée, raisonner de la fin vers le début, s’appelle l’induction à rebours.

C’est la même idée qui se cache derrière la remarque de von Neumann sur les échecs. Les échecs comptent incomparablement plus de positions, mais le principe est le même : quelque part, il existe une bonne réponse pour chacune. Ce qui en découle, et ce qui n’en découle pas, sera le sujet du prochain article.

Cinq questions pour classer n’importe quel jeu

Les échecs et le poker sont tous deux des « jeux », mais mathématiquement ils vivent dans des mondes différents. Pour voir où passe la frontière, il suffit de poser cinq questions à un jeu :

1. Combien de joueurs ? À partir de trois, des alliances apparaissent et l’analyse se complique fortement.
2. Les intérêts sont-ils opposés ? Somme nulle, ou bien peut-on gagner ou perdre ensemble ?
3. Voit-on tout ? Dans un jeu à information parfaite, le joueur qui doit jouer connaît tout ce qui s’est passé jusque-là. Les cartes cachées dans la main de l’adversaire brisent cette condition.
4. Y a-t-il du hasard ? Des dés, un paquet de cartes mélangé.
5. Chacun son tour ou en même temps ? Un choix simultané, comme à pierre-feuille-ciseaux, revient mathématiquement à ne pas voir le coup de l’adversaire.

Voici comment se classent quelques jeux connus :

Regardez le backgammon. Il y a du hasard, mais pas d’information cachée : les dés sont lancés sous les yeux de tous. « Hasard » et « inconnu » ne sont donc pas la même chose. Au backgammon, vous ignorez l’avenir. Au poker, vous ignorez le présent : ce que l’adversaire a déjà en main. Cette différence change tout.

Précision pour les curieux : la théorie des jeux distingue l’information parfaite (connaître tous les coups joués) de l’information complète (connaître les règles et les objectifs de tous les joueurs). Le poker offre la seconde (chacun sait que les autres veulent gagner des jetons), mais pas la première.

Pourquoi, au poker, le bluff relève des maths et non du caractère

Aux échecs, rien n’est caché : tout ce que sait l’adversaire, vous le savez aussi. Le meilleur coup ne dépend donc pas de ce que l’adversaire attend. En théorie, vous pourriez annoncer votre plan à voix haute sans que l’évaluation de la position change.

Au poker, impossible. Si vous misez toujours avec de bonnes cartes et jamais avec de mauvaises, votre mise devient une carte retournée. Un adversaire attentif se couchera chaque fois que vous misez, et vos belles mains ne vous rapporteront rien.

Von Neumann et Morgenstern avaient déjà mis en évidence le bluff dans un poker simplifié dans leur livre de 1944. En 1950, le mathématicien Harold Kuhn a proposé un modèle encore plus petit, devenu l’exemple de manuel. Son « poker simplifié » n’utilise que trois cartes : valet, dame et roi. Chaque joueur en reçoit une, la troisième reste face cachée, et une seule mise est permise. Même dans ce jeu jouet, le calcul aboutit à un résultat qui surprend les débutants : la stratégie optimale doit comporter du bluff.

Par exemple, quand le premier joueur passe, le second, s’il tient la carte la plus faible (le valet), doit miser exactement une fois sur trois. Plus souvent, son bluff se fera payer ; moins souvent, ses mises deviendront trop honnêtes. Et celui qui parle en premier dans ce jeu, si les deux jouent parfaitement, perd en moyenne 1/18 de jeton par donne : le second joueur n’agit qu’après avoir vu la décision du premier.

Voilà la différence essentielle. Dans un jeu à information parfaite, la stratégie optimale est un coup précis dans chaque position. Dans un jeu à information cachée, c’est souvent une proportion : à quelle fréquence faire telle ou telle chose pour que l’adversaire ne puisse pas vous « lire ». Les mathématiciens parlent de stratégie mixte, à laquelle un article de cette série sera consacré.

Cela ne rend pas les échecs « plus simples ». Trouver le bon coup parmi un nombre gigantesque de variantes est aussi difficile que de tenir la bonne proportion de bluffs. Ce sont simplement deux difficultés de nature différente.

Ce que cela change, sur l’échiquier et ailleurs

Cette classification n’est pas qu’académique. Elle aide à comprendre dans quel ordre les machines ont dépassé les humains. Deep Blue, d’IBM, a remporté un match contre Garry Kasparov en 1997. AlphaGo, de DeepMind, a battu Lee Sedol au go en 2016, 4 à 1. En revanche, il a fallu attendre 2017 pour que des programmes, Libratus en tête, battent nettement des professionnels de haut niveau au Texas hold’em sans limite, et seulement en tête-à-tête. À une table de six joueurs, c’est son successeur Pluribus qui y est parvenu, en 2019.

Ce n’est pas qu’une question de puissance de calcul. Un programme d’échecs ou de go répond à la question « quel est le meilleur coup ? ». Un programme de poker doit répondre à une autre : « à quelle fréquence jouer chaque coup, sachant que l’adversaire observe mes habitudes ? ». Les machines ont dû apprendre à bluffer dans les bonnes proportions.

Pour un joueur en chair et en os, il en découle trois questions à se poser avant toute décision importante, sur l’échiquier ou ailleurs :

• Que voit mon adversaire ? S’il voit tout, votre plan doit rester bon même une fois deviné. Un piège aux échecs qui ne fonctionne que si personne ne le remarque est un pari sur l’erreur de l’autre, pas une stratégie.
• Que ne voit-il pas ? Si quelque chose est caché, la prévisibilité devient une faiblesse.
• Est-ce vraiment un jeu à somme nulle ? Sur l’échiquier, oui. Au travail, en amitié ou en négociation, souvent non, et traiter ces situations comme une partie d’échecs est l’erreur la plus coûteuse.

Exercice

1. Classez ces jeux à l’aide des cinq questions : les dominos, le Monopoly, le Loup-garou, le morpion. L’un d’eux est un jeu à deux, à information parfaite et sans aucun hasard, résolu depuis longtemps : si les deux joueurs jouent correctement, c’est match nul. Lequel ?
2. Changez la règle des allumettes : on peut désormais en prendre une, deux ou trois. Avec combien d’allumettes sur la table le premier joueur est-il condamné à perdre ?
3. Jouez aux allumettes avec quelqu’un qui n’a pas lu cet article. Combien de parties lui faut-il pour découvrir la règle ?

Réponses à la fin de l’article.

Questions pour la discussion

• Pensez à une partie perdue non pas à cause de mauvais coups, mais parce qu’on vous a « lu ». Qu’est-ce qui vous a trahi ?
• Êtes-vous d’accord avec von Neumann pour dire que les échecs ne sont « pas un vrai jeu » ? Que manque-t-il à sa définition, vu par un joueur ?
• Quelle situation de votre vie ressemble le plus au poker, et laquelle aux échecs ?

Prochainement dans la série : « Les échecs ont une réponse, mais personne ne la connaît », sur le théorème de Zermelo, les dames résolues et le go, qui résiste encore.

Réponses. 1) Le morpion. Les dominos et le Loup-garou comportent de l’information cachée ; le Monopoly a des dés et plus de deux joueurs. 2) Quand le nombre d’allumettes est un multiple de 4 : le second joueur complète toujours le coup de l’adversaire jusqu’à quatre.