Le jeu d'échecs Le jeu d'échecs est un jeu ancien datant du 10ème siècle environ. C'est un jeu de plateau, c'est-à-dire un jeu qui se joue avec des pièces positionnées sur un plateau découpé en cases. Le plateau du jeu d'échecs est un plateau de 64 cases de forme carrée avec des cases blanches et des cases noires. C'est un jeu à deux joueurs. Chacun des joueurs dispose de 16 pièces de différente nature : les pions, les tours, ..., le roi et la reine. Chacune des pièces a des possibilités de déplacement et des possibilités de prise de pièce adverse. Le jeu est défini par un ensemble de règles très précises pour les déplacements, les prises, le calcul du gagnant.

Nous nous intéressons à la question de faire jouer un ordinateur au jeu d'échecs. La réalisation d'un programme de jeu capable de gagner contre les humains a été un sujet important de l'intelligence artificielle sur toute la seconde moitié du 20ème siècle. Il a fallu plus d'un demi-siècle pour qu'un ordinateur puisse gagner contre le meilleur joueur humain, en l'occurence le programme "Deep Blue" qui gagne contre Kasparov en 1997 . Désormais, des programmes, qui peuvent être exécutés sur un ordinateur personnel, sont plus forts que tout expert humain. Nous allons expliquer les principes algorithmiques qui font "l'intelligence" de ces programmes.

Nous laissons complètement de côté toutes les questions liées au graphisme, aux interactions entre le joueur humain et le programme. Nous supposons que le programme dispose d'une représentation numérique du plateau et des pièces, qu'il existe des programmes permettant de vérifier qu'un déplacement est autorisé, permettant de calculer, pour un état du jeu, tous les déplacements possibles du joueur qui doit jouer, permettant de voir si la partie est finie et de déclarer le match nul ou le gagnant. Nous nous intéressons donc simplement à la question suivante (la plus difficile) : la partie étant dans un certain état après plusieurs coups de chacun des deux joueurs, comment le programme peut-il choisir le meilleur coup à jouer ?

Si vous avez déja joué à un jeu de plateau, vous raisonnez très certainement de la façon suivante : quels sont les coups possibles ? Pour chacun d'eux, voir leur effet, réfléchir à la réponse potentielle de mon adversaire, penser à ce que je pourrais jouer ensuite, ... Après avoir examiné un certain nombre de coups possibles, je fais un choix. Un algorithme va avoir une approche similaire mais très systématique. Il va considérer tous les coups possibles de sa part, tous les coups possibles de l'adversaire, tous les coups possibles de sa part en réponse, ... On peut ainsi construire une structure, appelée arbre en informatique, qui possède une racine pour l'état courant du jeu, des fils pour les états du jeu pour chaque coup possible, etc. Une première idée est alors de construire cet arbre de toutes les suites possibles du jeu à partir de l'état courant, puis de calculer le coup qui va me mener à la victoire quoi que fasse l'adversaire.

Le problème est-il résolu ? Malheureusement non ! Nous avons signalé, dans l'introduction de ce module, la notion d'être calculable par une machine. Mais il ne suffit pas qu'un problème soit calculable. Il faut qu'il le soit avec une mémoire et un temps de calcul raisonnables. Sur notre exemple, imaginez qu'il y ait environ 10 coups possibles et qu'on souhaite regarder les états possible pour 10 tours de jeu, soit pour 20 coups. Il y aurait 10 puissance 20 états possibles, soit encore 1 suivi de 20 zéros, soit encore 100 milliards de milliards d'états possibles. Il est impossible à toute machine de mémoriser ces états ou de faire des calculs sur tous ces états. C'est ici qu'il faut donc être "intelligent" pour notre programme.

Vu que le programme ne peut pas explorer le jeu pour voir si un coup mène sur une position gagnante, nous allons doter le programme d'une fonction d'évaluation d'un état du jeu. Dans sa forme la plus simple, une valeur est attribuée à chacune des pièces et l'évaluation d'un état du jeu consiste à sommer la valeur des pièces dont le joueur dispose dans cet état. Cette fonction peut être améliorée par des bonus ou malus dépendant de la position de la pièce. Par exemple, on va bonifier un pion qui est près du camp adverse car il peut se transformer en reine, on va pénaliser un pion isolé car il peut être pris facilement. Nous supposons qu'une fonction d'évaluation a été choisie.

Faisons le point. Le jeu est dans un certain état (une configuration du jeu après plusieurs coups), le programme doit choisir un meilleur coup à jouer. La succession des coups que chacun des joueurs peut jouer définit un arbre de tous les états possibles. Nous savons qu'il est impossible d'explorer cet arbre complètement. L'idée de base de l'algorithme est de l'explorer incomplètement mais intelligemment. Pour cela, on utilise la fonction d'évaluation pour attribuer un score à un état de l'arbre. En effet, on va explorer l'arbre en éliminant complètement des sous-arbres lorsqu'on estime que les scores dans ce sous-arbre ne seront pas assez bons. C'est un peu ce qu'un joueur humain fait : si je joue ce coup, je perd ma reine et, sauf cas particulier, ce coup n'est pas intéressant donc je ne vais pas explorer plus loin ce qui peut se passer. C'est ce principe qui a été formalisé bien plus précisémment en utilisant les scores sous forme d'un algorithme célèbre appelé algorithme alpha-beta .

Vous connaissez maintenant les principes du fonctionnement de l'algorithme. Pour l'améliorer on examinera le plus grand nombre d'états possibles dans l'arbre simplifié grâce à la méthode alpha-beta. Pour avoir un algorithme encore plus performant, on ajoute d'autres éléments comme, par exemple, une bibliothèque des débuts de partie. C'est-à-dire que le programme pourra mimer des débuts de partie classiques des meilleurs joueurs qui sont connues sur quelques coups en début de partie. Mais avoir le jeu le plus fort ne sera pas le seul critère car un joueur standard n'a pas le niveau du champion du monde et ne prendra pas plaisir à perdre toutes les parties qu'il joue ! Avoir un jeu qui s'adapte à l'utilisateur est une question importante qui est toujours étudiée par les concepteurs de jeux.

Il est difficile de ne pas parler du jeu de Go qui défraie la chronique au moment de la rédaction de ce cours en 2016. En effet, pour la première fois, un programme a gagné contre le champion du monde humain du Go. On croyait le Go hors de portée des machines car le nombre de configurations possibles est encore plus gigantesque que pour les échecs et les stratégies des joueurs humains utilisent une vue spatiale de l'état du jeu. Le programme de Go n'utilise pas les stratégies développées par les humains mais utilise des techniques d'apprentissage automatique ("machine learning" en anglais) avec un programme de jeu qui s'améliore avec l'expérience, c'est-à-dire qu'il "apprend" à partir de parties jouées (contre un humain ou contre lui-même). Un petit cocorico Lillois (les rédacteurs de ce cours sont Lillois) car c'est notre collègue Rémi Coulom qui a initié ces recherches sur le Go avec un programme champion du monde dans les années 2010, battant même des experts humains mais avec handicap.