Le graphe de pile ou face

Commençons par un exemple encore plus simple : imaginons que nous ayons une pièce truquée qui tombe toujours sur pile. Nous savons alors que pour gagner, il faut choisir « pile », et que si l'on choisit " face ", on va perdre. Le graphe représentant ce problème est le suivant : Nous avons donc représenté un jeu (certes très simple ici) par un graphe, c'est-à-dire des noeuds (les ronds) reliés par des arêtes (les flèches). Nous avons placé un 1 pour la situation finale conduisant à une victoire, et un 0 pour la situation finale conduisant à une défaite.

Généralisons à présent ce principe d'un graphe pour représenter un jeu, mais cette fois-ci avec deux joueurs : le premier choisit pile ou face, et le second, qui entend la décision du premier joueur, place la pièce selon son propre choix, sur pile ou sur face. Si le premier joueur a deviné ce qu'allait faire le second, il gagne ; sinon, le second joueur gagne. Quoique le jeu ne soit pas bien compliqué, on n'a pas immédiatement accès à une stratégie pour le premier joueur. En regardant le noeud tout en haut, et même les noeuds juste en dessous, nous ne savons pas ce que le joueur 1 devrait jouer. Par contre, dans chacun des noeuds jaunes, nous voyons bien que le second joueur a une stratégie très simple pour gagner.

Nous obtenons ainsi deux certitudes :

• nous savons que si les joueurs jouent " bien ", le joueur 2 gagne ;
• nous savons que le joueur 2 doit jouer une arête menant à un 1 pour gagner.

Nous savons que le joueur 2 doit jouer une arête menant à un 1 pour gagner.

Le cas du jeu d'échecs

Pour traiter le jeu d'échecs, Claude Shannon a proposé en 1950 une approximation: on définit la profondeur d'un noeud comme le nombre d'arêtes à parcourir avant de remonter à la racine. On décide alors d'une profondeur limite k. Pour tous les noeuds à profondeur k ou les noeuds où le jeu est fini, la valeur sera :

• un nombre positif très élevé (par exemple + 100 000) en cas de victoire dans cette situation ;
• un nombre très négatif (par exemple -100 000) en cas de défaite dans cette situation ;
• une valeur approchée, calculée à partir des éléments visibles sur le plateau, par exemple pour les échecs, comme suit :
• +10 pour une dame (-10 pour la dame adverse) ;
• +5 pour une tour (-5 pour une tour adverse) ;
• +3 pour un cavalier ou un fou (-3 pour un cavalier ou fou adverse) ;
• +1 pour un pion (-1 pour un pion adverse) ;

Cette approximation va permettre à l’ordinateur de s’orienter vers des chemins de valeur plus élevée.

à quels jeux s'attaquer avec ces principes ?

Une première limitation est que nous avons supposé que le jeu est à information parfaite : on connaît exactement tout l'état du jeu. Mais ce n'est de loin pas le cas de tous les jeux. Les jeux à information imparfaite sont par exemple le poker, le bridge, le scrabble. Lorsque l'information cachée est critique (par exemple pour le poker et le bridge), les algorithmes deviennent souvent très heuristiques. Cela signifie qu'ils contiennent de nombreuses astuces spécifiques au jeu, et ne sont pas mathématiquement prouvés efficaces (ce qui certes ne les empêche pas d'être performants). Une seconde limitation est que nous avons supposé qu'il n'y avait aucun hasard. Cette limitation est usuellement aisée à lever : il suffit d'introduire un troisième type de noeuds : à côté des noeuds où moi, joueur 1, je décide l'action, et des noeuds où mon adversaire, joueur 2, décide l'action, introduisons des noeuds où l'action est tirée au sort. Le nombre à inscrire dans ces noeuds est la moyenne des nombres inscrits dans les noeuds où le hasard peut mener. L'algorithme n'est donc pas à modifier de fond en comble. Une troisième limitation est que nous avons supposé que l'on pouvait commodément fournir une valeur approchée pour un noeud – en utilisant une fonction d'évaluation. C'est une forte limitation en fait : de nombreux jeux où les ordinateurs sont faibles, face à l'humain, sont des jeux où l'on ne sait pas fournir une valeur approchée de la valeur d'une situation.

à quoi bon tout ça ?

Les jeux sont certes un plaisir, et ils ont une portée pédagogique. Mais peut-être vous demandez-vous si le jeu en vaut vraiment la chandelle ? N'y a-t-il pas des activités plus utiles ? Les jeux fournissent un fascinant défi pour l'intelligence artificielle. Il est critique de comprendre ce que nous savons programmer, ou non, des activités humaines. Les jeux sont un outil parfait pour tester nos outils d'intelligence artificielle dans un cadre où la compétition avec nos collègues du monde entier est claire et nette. C'est pour ce rôle qu'à côté d'applications plus industrielles, nous nous intéressons aux jeux, notamment des jeux plus difficiles pour les ordinateurs que les échecs.