Élémentaire, mon cher Watson
Qu'un ordinateur puisse nous battre en calcul mental, on l'accepte sans problème. Qu'il nous batte systématiquement au Puissance 4, ça peut encore passer. Quand il commence à battre systématiquement les champions du monde d'échec, ça commence à faire mal. Mais maintenant, il nous bat même en jeu de culture générale ! Mais jusqu'où ira l'intelligence artificielle ?
Ken, Brad et Watson
C'est ce qui est arrivé du 14 au 16 février dernier, dans le jeu télévisé américain Jeopardy, un jeu de culture générale où le principe est de retrouver la question à partir de la réponse. Lors de ce tournoi exceptionnel, c'est Watson qui a décroché le gros lot, en battant deux champions historiques de l'émission. Sauf que Watson, c'est un ordinateur construit par IBM... Avec ses 15 To de mémoire vive et ses quelques 2880 processeurs Power 7, Watson est capable de comprendre l'énoncé donné en langage naturel, fouiller dans ses bases de données (plusieurs millions de textes, notamment des dictionnaires, des encyclopédies, des pièces de théâtre ou Wikipédia...), trouver la réponse attendue (ou pas) et appuyer sur le buzzer. Le tout en quelques secondes (alors qu'un ordinateur classique mettrait 2 heures pour le même boulot). Son seul défaut est d'avoir du mal avec les jeux de mots, mais il sait apprendre de ses erreurs, en faisant moins confiance à tel ou tel algorithme pour tel ou tel thème...
Un nouveau cap est donc aujourd'hui franchi dans le monde de l'intelligence artificielle : un ordinateur est capable de comprendre le langage naturel, et donc, potentiellement, de remplir les grilles de mots croisés à notre place ! C'est l'occasion de faire un petit panorama sur la domination progressive des ordinateurs sur l'intelligence humaine... Un robot intelligent sera-t-il capable de nous pondre la démonstration de la conjecture de Riemann avant le 10 janvier 2026 ?
Là où l'ordinateur est plus intelligent qu'un autre ordinateur : Puissance 4
Puissance 4 : un morpion soumis aux forces gravitationnelles
Le monde des jeux de stratégie se divise en deux catégories : ceux où il y a forcément un gagnant en temps fini (et pas de hasard ni de secret), et les autres. Dans cette première catégorie, on peut ranger le jeu des bâtonnets de Fort Boyard, le jeu de Nim, le jeu de Grundy, le quart de singe... Depuis les années 30, on sait, grâce au théorème de Sprague-Grundy, que quand on joue à un jeu de ce type (un jeu "impartial") contre un ordinateur bien programmé suffisamment puissant, on finira toujours par perdre, à moins de connaître soi-même la stratégie gagnante. L'algorithme utilisé par l'ordinateur considère l'ensemble des positions du jeu, repère les configurations finales gagnantes et, de proche en proche, marque toutes les configurations gagnantes, celles amenant toujours à des configurations finales gagnantes.
Cependant il y a les autres jeux, où le théorème n'a plus de valeur, mais où l'algorithme de recherche en profondeur fonctionne toujours. On peut parler du jeu du morpion, où l'ordinateur égale sans difficulté les stratégies humaines (étant donné le faible nombre de configurations à considérer, le cerveau humain n'est pas dépassé par celui de la machine), et peut facilement forcer le nul, ou profiter de la moindre erreur humaine. On retrouve une jolie représentation graphique de la stratégie optimale du morpion chez xkcd.
Plus compliqué : le jeu du Puissance 4, jeu datant des années 70. Bien que ce jeu puisse théoriquement amener à des situations d'égalité, il existe un algorithme (découvert en 1988) permettant au joueur qui commence de gagner à coup sûr, en glissant le premier jeton dans la colonne centrale. Si ce joueur est l'ordinateur, c'en est fini pour l'humain en face (et dans le cas contraire, l'ordinateur sait comment profiter des erreurs de son adversaire). On peut trouver sur internet plusieurs programmes permettant de se mesurer au Dieu du puissance 4...
Dans la catégorie des jeux totalement résolu, il y a aussi le jeu africain de l'awalé. Depuis 2002, on sait qu'en se battant contre un ordinateur, on fera au mieux match nul. Pour la résolution, il a fallu explorer 889 milliards de configurations... Depuis 2007, on peut aussi ranger le jeu de dames anglais (jeu de dames sur un échiquier de 64 cases) dans cette catégorie : au mieux, on peut viser le match nul.
Là où l'ordinateur est plus intelligent que le plus intelligent des humains : Othello
Othello, ou le Maure de Venise
Dans d'autres jeux, on ne connaît pas de stratégie infaillible pour gagner, mais on peut apprendre à l'ordinateur à emprunter les chemins ayant l'air, à plus ou moins long terme, favorable. Ce mode de pensée, c'est celui de l'algorithme Minimax, et c'est sur le jeu de l'Othello (aka Reversi) que l'ordinateur utilisant cet algorithme fait des étincelles.
L'algorithme Minimax, c'est donc la clé de voute de la programmation des jeux de stratégie. Le premier principe, c'est d'attribuer un score à chacune des configurations que l'on considère. Dans le jeu d'échecs par exemple, on a ainsi l'habitude d'attribuer 1 point au pion ou 10 points à la dame. Les configurations les mieux cotées seront celles offrant la situation la plus favorable. Le deuxième principe, c'est de tout faire pour maximiser son score en considérant que de son côté, l'adversaire fera tout pour le diminuer. On calcule alors les valeurs des configurations atteignables après n coups, puis on remonte l'arbre en reportant le min ou le max des scores atteignables, suivant le deuxième principe.
Jaune joue et mate en 2 coups.
Prenons un exemple où, à chaque tour de jeu, on a le choix entre 2 coups. Jaune calcule donc les 3 prochains coups possibles, soit 8 configurations à évaluer. Jaune cherche à maximiser son score, donc la valeur d'un nœud jaune correspond à la plus grande valeur qu'il peut atteindre. A contrario, Bleu cherche à minimiser le score, donc il faut reporter le plus petit des scores. Ainsi, on s'aperçoit qu'en 3 coups, un score de 10 est atteignable, voire 13 en cas d'erreur de Bleu, et c'est pourquoi le prochain coup de Jaune sera A.
Deux soucis se présentent alors. Le premier, c'est que le nombre de configurations à considérer explose avec le nombre de coups que l'on peut jouer à son tour. Dans la pratique, on ne pourra pas prévoir trop de coups à l'avance. Pour pallier à se problème, Minimax possède une amélioration, l'algorithme alpha-bêta, qui n'explore pas les branches inintéressantes.
Le deuxième problème est dans l'attribution des scores de positions, qui sont définis par des considérations comme "Dans le jeu de dames, c'est bien d'avoir beaucoup de pions au centre. On va dire que ça vaut 100 points". L'évaluation d'une position est donc dictée par le programmeur, qui se doit de bien connaître le jeu qu'il programme. Pour renforcer cette évaluation, on fait jouer des ordinateurs les uns contre les autres en modifiant aléatoirement les notes qu'ils donnent aux positions. La sélection naturelle gardera seulement les meilleurs !
Le principe de l'Othello, c'est de prendre en tenaille les jetons de son adversaire pour les convertir en sa couleur. Avec ses règles simples, les configurations de jeu changent très rapidement, ce qui rend la stratégie humaine difficile à évaluer à long terme. In fine, l'approche calculatoire favorise la machine...
En ajoutant un peu de calcul de probabilités, on peut aussi ranger le Scrabble et le backgammon dans la liste des jeux où l'ordinateur est bien meilleur qu'un humain. Au Scrabble, en plus de repérer rapidement les mots jouables grâce à un dictionnaire intégré, la machine est capable de décider où placer ses mots pour maximiser ses points et minimiser l'ouverture laissée à l'adversaire. Au backgammon (un jeu de petits chevaux bien plus stratégique), l'ordinateur a su apprendre de ses erreurs les meilleurs mouvements pour commencer et les configurations amenant le plus souvent à des victoires.
Dans tous ces jeux, l'adéquation des bases de données d'ouverture et de fin de partie et des algorithmes Minimax (et Alpha-bêta) amène dans la très grande majorité des cas à la victoire de l'intelligence artificielle.
Là où l'ordinateur est aussi intelligent que le plus intelligent des humains : les échecs
Et mat.
Le grand bond en matière de stratégie artificielle a eu lieu dans les années 90, lorque deux grands noms des échecs se sont rencontrés. D'un côté, Garry Kasparov, champion du monde d'échecs de 1985 à 2000. De l'autre, Deep Blue, superordinateur de 700kg développé (déjà) par IBM. Le 10 février 1996, le match est serré, mais Kasparov bat l'ordinateur sur un score de 4-2. Un an plus tard, lors de sa revanche, la machine prend le dessus. C'est officiellement depuis ce jour que l'on considère l'ordinateur plus intelligent que l'homme en matière de jeux d'échecs...
En fait, non, puisque lors de ce deuxième match, Kasparov a abandonné de fatigue, et n'a jamais pu avoir de revanche, l'ordinateur ayant été démonté. Mais ça, c'était il y a plus de 15 ans... Depuis, la recherche en terme de programmation échiquienne s'est amoindrie, mais a tout de même refait parler d'elle en 2006 quand Vladimir Kramnik, champion du monde de 2000 à 2007, se fait battre par un logiciel vendu à 55€ dans le commerce...
Derrière ces victoires se cachent toujours les mêmes algorithmes minimax et alpha-bêta, mais accompagnés surtout de l'expertise de plusieurs champions d'échecs ayant aidé à la conception des bibliothèques d'ouverture.
Là où l'ordinateur est quand même un peu ridicule : le jeu de go
Le jeu de go, peuplé d'irréductibles tesuji !
Il reste un jeu de stratégie qui résiste à toutes les approches informatiques, et c'est le jeu de go. Sur un plateau carré de 19×19 cases (le goban), deux jouers posent à leur tour des pierres blanches ou noires de façon à encercler un maximum de territoires. Celui dont les territoires sont les plus étendus à la fin de la partie est le grand vainqueur.
A chaque tour de jeu, on peut choisir parmi 200 coups possibles (une quarantaine aux échecs). Une action ayant l'air quelconque en début de partie peut s'avérer décisive 30 coups plus tard. Une position locale peut influencer la partie sur son ensemble... Autant de bonnes raisons d'oublier l'approche minimax ! Aux échecs, les ressources mémoires permettent de prévoir une dizaine de coups à l'avance, contre seulement 3 ou 4 au jeu de go... L'ordinateur reste très mauvais dès qu'il s'agit appréhender des formes et des motifs, alors qu'un cerveau humain le fait sans trop de difficultés.
A l'époque de Deep Blue, le meilleur programme de go, Hand-Talk, se fait battre par la joueuse professionnelle Janice Kim alors qu'on lui avait accordé 25 coups d'avance !
De nouveaux algorithmes ont tout de même été pensés depuis. Les programmes les plus récents utilisent notamment des méthodes de Monte-Carlo : au lieu de regarder tous les coups possibles, autant en essayer au hasard pour voir s'ils sont bons ou pas. En ne gardant que les meilleurs, l'ordinateur repère les meilleures stratégies à suivre. On parle aussi de l'aglorithme UCT, une approche probabiliste de minimax.
Ces méthodes ont fait leur preuve puisque de plus en plus de professionnels se font battre sur des petits plateaux de jeux (7×7 ou 9×9). Pour gagner une partie sur un goban classique (19×19), l'ordinateur doit encore commencer avec un peu d'avance sur son adversaire humain. Le jour où un tournoi de Go sera remporté par un ordinateur face à un humain sans handicap, un nouveau grand pas aura été franchi. Peut-être avant 2020 ?
Malgré tout, les robots ont encore du souci à se faire avant de pouvoir un jour se passer de nous. Pour faire un bon programme capable de jouer aux échecs ou au go, il faut avant tout soi-même bien connaître le jeu et ses stratégies. Avant qu'un programme trouve la démonstration d'un théorème, il faut préalablement savoir où chercher, et il reste pour l'instant plus simple de chercher soi-même plutôt que d'apprendre à un ordinateur à le faire à notre place... La réflexion humaine a encore un bel avenir !
Sources :
Watson l’ordinateur a gagné à Jeopardy, un jeu télévisé, sur futura-sciences
- La programmation des jeux de stratégie, Pour la science n°293, mars 2002
- L'ordinateur, champion de go ?, Pour la science n°354, avril 2007
Wikipédia : jeu de go en informatique, et beaucoup d'autres articles
/http%3A%2F%2Fstorage.canalblog.com%2F72%2F92%2F210892%2F113119539_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F00%2F91%2F210892%2F107069165_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F33%2F48%2F210892%2F101190494_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F83%2F38%2F210892%2F101168363_o.png)
