Je n'ai jamais beaucoup aimé les jeux de société ; mais j'ai fait semblant de m'intéresser au go, dont la symétrie et les possibilités infinies me plaisaient. Je rejoignais ainsi la philosophie de Dupin, le personnage de détective créé par Edgar Allan Poe. Vers le début de Double assassinat dans la rue Morgue (traduit par Baudelaire), Dupin proclame la supériorité du jeu de dames sur les échecs :
[...] la haute puissance de la réflexion est bien plus activement et plus profitablement exploitée par le modeste jeu de dames que par toute la laborieuse futilité des échecs. Dans ce dernier jeu, où les pièces sont douées de mouvements divers et bizarres, et représentent des valeurs diverses et variées, la complexité est prise – erreur fort commune – pour de la profondeur. L’attention y est puissamment mise en jeu. Si elle se relâche d’un instant, on commet une erreur, d’où il résulte une perte ou une défaite. Comme les mouvements possibles sont non seulement variés, mais inégaux en puissance, les chances de pareilles erreurs sont très multipliées ; et dans neuf cas sur dix, c’est le joueur le plus attentif qui gagne et non pas le plus habile. Dans les dames, au contraire, où le mouvement est simple dans son espèce et ne subit que peu de variations, les probabilités d’inadvertance sont beaucoup moindres, et l’attention n’étant pas absolument et entièrement accaparée, tous les avantages remportés par chacun des joueurs ne peuvent être remportés que par une perspicacité supérieure.
Pour laisser là ces abstractions, supposons un jeu de dames où la totalité des pièces soit réduite à quatre dames, et où naturellement il n’y ait pas lieu de s’attendre à des étourderies. Il est évident qu’ici la victoire ne peut être décidée, – les deux parties étant absolument égales, – que par une tactique habile, résultat de quelque puissant effort de l’intellect. Privé des ressources ordinaires, l’analyste entre dans l’esprit de son adversaire, s’identifie avec lui, et souvent découvre d’un seul coup d’œil l’unique moyen – un moyen quelquefois absurdement simple – de l’attirer dans une faute ou de le précipiter dans un faux calcul.
Hélas, trois fois hélas, le champion du monde de dames est désormais battu par l'ordinateur.... reste le go, et il y a encore une assez grande marge de ce côté-là. Mais. chose plus intéressante, le chercheur qui a programmé l'ordinateur a également démontré que deux joueurs de dames parfaitement rationnels ne pouvaient aboutir qu'à un match nul. Que les aficionados se rassurent : il ne s'agit que du jeu de checkers, nos dames à nous sont bien plus complexes... mais c'est l'occasion pour moi d'aborder le théorème de Zermelo.
Revenons en arrière, à 1913. A l'époque, la théore des jeux, qui est devenue un outil fondamental dans les sciences sociales, n'existait pas encore ; mais plusieurs mathématiciens s'intéressaient à l'étude des situations de jeu, comme Emile Borel en France. Après tout, la théorie des probabilités a pris naissance avec les jeux de société... Un autre mathématicien, allemand celui-là, fut conduit par ses préoccupations de logicien à formuler ce que les théoriciens des jeux connaissent aujourd'hui comme le théorème de Zermelo :
Tout jeu fini à deux joueurs et à somme nulle admet un nombre V et un couple de stratégies tel que :
- le premier joueur peut s'assurer un gain au moins égal à V s'il joue la première de ces deux stratégies
- symétriquement, le second joueur peut s'assurer un gain au au moins égal à -V s'il joue la seconde stratégie.
Tout ceci peut paraître bien éloigné de Dupin et de ses dames. Mais le jeu de dames se joue à deux joueurs ; et il est à somme nulle puisque le gain d'un joueur est la perte de l'autre---au moins si nous convenons que ma perte me peine autant que votre gain vous satisfait, et qu'un match nul nous laisse tous deux au juste milieu de ces deux extrêmes. (Imaginez que celui qui gagne prend un euro au perdant, et que personne ne doit rien à personne en cas de nullité).
Un jeu fini est par définition un jeu qui ne peut pas engendrer un nombre infini de parties. Si nous laissions deux ordinateurs jouer aux dames au hasard (mais selon les règles !), ils finiraient par épuiser toutes les parties possibles. Pour cela, il faut que dans chaque situation donnée dans une partie, le nombre de coups possibles soit fini. C'est évidemment le cas aux dames, comme au go ou aux échecs. Il faut ensuite que le nombre de coups successifs soit limité. C'est le cas aux échecs de par la règle de non-répétition de situation ; et le jeu de dames a une règle très semblable.
Qu'est ce qu'une stratégie pour un joueur de dames ? C'est simplement la liste complète des coups qu'il jouera dans toute situation possible du jeu, les plus probables (par exemple le premier coup s'il a le trait) comme les moins probables (si par exemple il a six dames et son opposant n'a plus qu'un pion). Personne ne joue ainsi, bien sûr, sauf peut-être à des jeux élémentaires comme le tic-tac-toe ; mais c'est un concept bien défini, une sorte de plan d'action complet, ou une liste complète d'instructions pour un ordinateur très bête.
Le théorème nous indique donc la chose suivante : il existe un nombre V (soit 1, 0 ou -1, correspondant au gain de 1 dollar, à une nulle ou à la perte de 1 euro par les blancs) et un programme pour l'ordinateur-blanc et un pour l'ordinateur-noir tels que :
- les blancs se garantissent un gain au moins égal à V, quoi que les noirs fassent ;
- et les noirs se garantissent une perte au plus égale à V, quoi que les blancs fassent.
"Bien sûr", me direz-vous, "les blancs peuvent toujours se garantir la perte d'un euro (V=-1) en jouant n'importe comment, et ibidem pour les noirs". Certes ! Mais regardez bien les deux clauses ci-dessus, en remplaçant V par -1 : si les blancs se garantissent un gain au moins égal à -1 (ce qui n'est effectivement pas difficile), les noirs doivent se garantir une perte au plus égale à -1, soit un gain au moins égal à 1, quoi que les blancs fassent ; et c'est une autre paire de manches ! Ce que Jonathan Schaeffer et ses ordinateurs ont démontré, c'est que V=0 aux dames (enfin, aux checkers).
Pour ce faire, ils ont suivi une méthode "simple":
- ils ont analysé par ordinateur les quelques 39 000 milliards de positions possibles quand il ne reste plus que dix pièces au plus ;
- ils ont classé ces positions dans trois catégories : celles qui conduisaient à un gain des blancs (1), à un nul (0), à un gain des noirs (-1) ;
- puis ils ont montré (en aidant subtilement l'ordinateur) que des joueurs qui ne feraient jamais d'erreur ne pourraient aboutir qu'à l'une des positions à dix pièces (ou moins) étiquetées 0.
...et, comme l'eût dit Fermat,
cujus rei demonstrationem mirabilem sane detexi. Hanc blogis exiguitas non caperet.
Ceci dit, je peux vous offrir une démonstration simple du théorème de Zermelo. Remarquez d'abord qu'il est évidemment vrai... pour tous les jeux à un seul coup. Je ne sais pas si un jeu en un seul coup mérite vraiment le nom de jeu, mais le joueur (unique !) peut bien sûr s'assurer le gain de la partie, ou plus généralement le gain maximal.
Supposez maintenant que le théorème s'applique à tous les jeux à m coups, quels que soient leurs règles, leur support, etc. Si par exemple m=9, le tic-tac-toe serait contenu dans cette catégorie, avec quantité d'autres jeux. Pour les dames et les échecs, m devra être très grand ; peu importe, puisque nous savons déjà que le théorème marche pour m=1, et que nous allons utiliser la force merveilleuse du raisonnement par récurrence.
Soit donc maintenant un jeu quelconque à (m+1) coups et concentrons-nous sur le premier coup du jeu. Quel que soit le coup c choisi par le joueur qui a le trait au début du jeu (disons les blancs), il amènera le second joueur (les noirs) au début d'un jeu à m coups. Ce jeu entre par hypothèse dans la catégorie zermeliste ; il existe donc un nombre V(c) et deux stratégies dans ce jeu qui, etc. Supposons, assez naturellement,q ue les blancs choisissent le coup (ou un des coups) c=d pour lequel leur gain garanti V(c) est le plus élevé. Prenons maintenant la stratégie des blancs qui consiste à
- jouer d au premier coup
- puis jouer dans la suite la stratégie dont le théorème de Zermelo nous garantit l'existence dans le jeu qui suit d
et la stratégie des noirs qui est simplement celle dont le théorème de Zermelo nous garantit l'existence dans le jeu qui suit d.
Il doit être maintenant clair que V(d), avec ces deux stratégies, remplissent les conditions du théorème pour le nouveau jeu à (m+1) coups. Le théorème s'applique à m=1, donc à m+1=2 ; à m=2, donc à m+1=3...et de proche en proche, il s'applique aux jeux de dames et de checkers comme aux échecs ou au go.
Mais que devraient jouer des joueurs de dames rationnels ? Ce qu'on peut dire, c'est que les stratégies du théorème sont un équilibre de Nash. Supposez par exemple que les noirs annoncent qu'ils joueront leur stratégie du théorème de Zermelo, qui leur garantit une nulle quoi que les blancs fassent. Que peuvent faire les blancs ? Pas gagner, puisque les noirs perdraient, ce qui contredirait le théorème (amendé par Schaeffer). Ils peuvent perdre, bien sûr ; mais le théorème leur indique une stratégie qui leur garantit aussi la nulle. Ils n'ont donc rien de mieux à faire que d'adopter cette stratégie ; et symétriquement pour les noirs. Le théorème de Zermelo suggère donc, en corollaire, un plan d'action simple (et très ennuyeux, mais heureusement d'application un peu lourde) : annoncer la stratégie de Zermelo et aller se coucher !
Soit dit en passant, les jeux à somme nulle ne sont qu'un cas (très) particulier, et c'est celui qui offre le moins d'intérêt pour les économistes : un jeu à somme nulle exclut toute possibilité de coopération, de collusion, de coordination, etc. Mais c'est une autre histoire...