Les maths en jeux

 
En raison de cette variété, la théorie des jeux a adopté bien des visages différents au cours des dernières décennies, et nombreux sont les outils mathématiques qui se sont immiscés dans la discipline. Nous nous attardons ici sur un outil central, qui apparaît assez naturellement et s’est révélé très utile pour étudier de nombreux jeux: les graphes.

Pour comprendre comment la théorie des graphes s’immisce dans la théorie des jeux, prenons un exemple connu de toutes et tous: le jeu Oxo sur une grille à 9 cases. Il est facile de se convaincre que si les 2 adversaires jouent correctement, la partie d’achèvera sur un match nul. Mais comment s’en assurer mathématiquement ? Une solution consiste à construire ce que l’on appelle un «arbre du jeu»: un objet qui présente sous une forme synthétique l’ensemble des parties possibles. Un «arbre», en mathématiques, est un type particulier de graphe, c’est-à-dire un ensemble de sommets relié par des arêtes, comme dans la figure ci‑dessous.

 
Dans le cadre plus précis qui nous intéresse, un arbre de jeu est un arbre mathématique dont les sommets sont des états possibles du plateau de jeu – on appelle ces états les «positions» du jeu – et tel que 2 sommets sont reliés par une arête si et seulement si l’on peut passer d’une position à l’autre quand un joueur joue.

En pratique, pour construire l’arbre du jeu Oxo, on procède de la manière suivante. La première ligne de l’arbre est constituée d’un unique sommet, appelé la «racine», qui représente la grille à 9 cases vide, c’est-à-dire la position de départ du jeu. Partant de là, le premier joueur peut placer son symbole, au choix, dans la case du centre de la grille, ou dans la case en haut au milieu, ou dans la case en haut à gauche etc.: il dispose, en tout, de 9 options. Les 9 positions d’arrivée correspondantes sont représentées par 9 sommets, qui constituent la deuxième ligne de l’arbre. Par définition, on peut passer de la position de départ du jeu à chacune de ces 9 positions: chacune est donc reliée à la racine de l’arbre par une arête. On poursuit en répétant l’opération à partir de chacune des 9 positions de la deuxième ligne: partant de l’une d’entre elles, le second joueur doit choisir entre 8 options, pour placer son symbole, ce qui donne 8 positions d’arrivée possibles. Donc chacune des 9 positions de la deuxième ligne est reliée à 8 positions, placées sur la troisième ligne. Etc. On trouvera ci-dessous une représentation partielle des 3 premières lignes de cet arbre du jeu Oxo (toutes les options ne sont pas présentées à chaque ligne, seulement quelques exemples).

 
On comprend aisément que l’arbre grossit très rapidement ! Et encore, il s’agit ici d’un jeu très simple, où à chaque coup les joueurs disposent d’un nombre réduit d’options. L’arbre du jeu d’échecs – ou pire: celui du jeu de Go – sont bien plus étendus encore !

L’intérêt de représenter un jeu sous cette forme, qui peut pourtant sembler lourde et compliquée au premier abord, c’est que l’arbre ainsi créé contient toutes les parties possibles, agencées d’une manière qui rend facile leur étude algorithmique. En effet, une partie d’un jeu est une succession de positions, qui s’enchaînent à mesure que les joueurs jouent en suivant les règles. Par construction de l’arbre, une partie est donc représentée par un chemin qui part du sommet (la position initiale) et qui progresse de position en position, une ligne après l’autre, en suivant les arêtes, jusqu’à arriver à une position finale dans laquelle le joueur dont c’est le tour n’a plus aucune option à sa disposition.

Cela permet de programmer des algorithmes d’exploration de l’arbre d’un jeu, par exemple pour identifier une stratégie optimale pour l’un des joueurs. Partant d’une position donnée, c’est-à-dire d’un sommet de l’arbre, on peut en effet dérouler toutes les suites possibles pour la partie en cours, en parcourant entièrement ou partiellement les branches de l’arbre qui partent de ce sommet. Cela permet de juger dans quelle direction il est préférable d’emmener la partie, pour le joueur dont c’est le tour. C’est en réalité exactement ce que font les joueurs de bon niveau aux échecs ou à d’autres jeux de ce type, et ce procédé est facilement automatisable pour pouvoir être mené par un ordinateur en exploitant une importante puissance de calcul.

Ce genre de raisonnement est à la base d’un algorithme très célèbre, appelé «MiniMax» (ou parfois «MinMax»), qui permet de déterminer si une position donnée dans un jeu est «gagnante» pour l’un des joueurs – c’est-à-dire si quels que soient les choix de jeu de son adversaire par la suite, ce joueur peut forcément réagir d’une manière qui, en définitive, lui assurera la victoire. Cependant, il n’est pas toujours possible d’exploiter directement cet algorithme, car les arbres de certains jeux sont tellement grands que même les ordinateurs les plus puissants ne parviennent pas à les parcourir en entier en un temps raisonnable !

Revenons à Oxo et à notre question d’origine: comment s’assurer de ce que notre intuition nous indique: si les 2 joueurs jouent bien, la partie s’achèvera nécessairement sur un match nul. En parcourant toutes les branches de l’arbre depuis l’origine, on constate pourtant que certaines parties s’achèvent par la victoire de l’un ou l’autre des joueurs. Mais dans ces parties, il existe en fait forcément une position où le joueur perdant aurait pu prendre une autre décision, orienter la partie vers une autre branche qui, elle, aurait abouti à un match nul. Les arbres sont formels: dans ce jeu, si l’on joue bien, on ne perd pas. À vous de jouer !