{% extends "articles/complexite-et-machine-de-turing/_layout.html" %} {% block section %}

{{ _("Jeux, Complexité et Résolution") }}

{% trans trimmed table_resolution=''|format(url=url_for('static', filename='img/table_resolution.png'))|safe %}

Présentation des concepts de complexité et de résolution

Peut-être en aviez vous entendu parlé, mais en mars 2016 une intelligence artificielle créée pour jouer au jeu de Go vit le jour. Il s'agit de AlphaGo. Un match en 5 parties fut organisé par Google entre AlphaGo et un grand maitre du Go : Lee Sedol, et bien sur l’événement fut abondamment relayé par les médias. Score finale 4-1 pour Alpha Go. Cet événement eut l'impact d'une petite bombe. Mais Pourquoi donc ?

Alors rassurez vous si vous ne savez pas jouer au jeu de Go, il n'y a nul besoin de ça pour comprend la portée de ce qui a été accompli. Pour cela nous devons nous pencher sur la notion de complexité d'un jeu. Le jeu de Go fait partie d'une vaste famille de jeu de stratégie que l'on appelle les jeux finis à informations complètes. Il s'agit de jeux où chaque joueur connaît lors de la prise de décision :

Enfin dire que le jeu est fini revient à dire qu'à chaque étape les joueurs n'ont qu'un nombre fini d'actions possibles et que nécessairement le jeu s'arrêtera après un certain nombre de coup (en l'occurrence le jeu de go s'arrête lorsque le goban est remplie soit après 361 coups).

Depuis l'avènement de l'informatique, on a commencé à concevoir des machines capables de jouer à ces jeux et d'élaborer des stratégies en essayant de prévoir un maximum de coups à l'avance. Ces ordinateurs construisent en réalité un arbre des possibilités où chaque choix fait par tel ou tel joueur crée une nouvelle branche. Grâce à l'informatique, il a été possible de construire l'arbre de certains jeux dans leur totalité. On ne parle donc plus de déterminer les possibilités après 4 ou 5 coups mais bien à partir de la position initiale de déterminer toutes les parties possibles. L'intérêt d'une telle construction est de trouver une stratégie gagnante pour un des joueurs (c'est à dire une stratégie qui lui assurera obligatoirement la victoire quelque soit les choix de son adversaire) ou à l'inverse de démontrer qu'il n'existe pas de telle stratégie et dans ce dernier cas on dira que le jeu est équitable. On appelle cela en mathématiques : Résoudre le jeu.

On appelle complexité algorithmique, l'estimation des ressources nécessaires à l’exécution d'un algorithme donné. En ce qui concerne notre sujet, on peut s’intéresser à deux grandeurs qui peuvent attester de la complexité d'un jeu :

{{ table_resolution }}

Comme l'atteste le tableau ci-dessus, le jeu de stratégie le plus complexe ayant pu être entièrement résolu à ce jour est le jeu de Dames sur un plateau 8x8. Cette résolution a demandé 18 années de calculs et a permis la modélisation de l'arbre des possibilités dans son ensemble.

Avant le jeu de Go, les échecs furent au centre des affrontements entre humain et machine. Et après quelques essais infructueux, la première fois qu'un programme prit l'ascendant sur un grand maître fut en 1997 dans un match opposant Kasparov et Deeper Blue. A l'époque la machine Deeper Blue pesait plus d'une tonne et sa stratégie était entièrement basée sur sa puissance de calcul. Le but étant de prévoir un maximum de coups à l'avance. Il a fallut presque 20 ans pour que l'intelligence artificielle soit capable de franchir le cap immense entre les échecs et le jeu de Go et rivaliser à nouveau avec les experts humains. Cela n'a été possible que grâce à l'avènement d'une révolution informatique récente : Le Machine Learning. C'est un sujet passionnant d'autant qu'après le succès d'Alpha Go en Mars 2016, Google DeepMind lors d'un communiqué a affirmé sa volonté de s'attaquer à de nouveaux jeux dont : Starcraft II (objectif rempli le 29 janvier 2019), Hearstone et Magic the Gathering. Oui Magic a bien été cité, mais hélas je ne vais pas m'aventurer plus loin concernant la notion d'I.A. à Magic car le sujet est vaste et que je ne souhaite pas trop m'éloigné du sujet initial.

{% endtrans %} {% trans trimmed elixir_of_immortality=card("Elixir of Immortality"), lich=card("Lich"), transcendence=card("Transcendence"), laboratory_maniac=card("Laboratory Maniac"), menacing_ogre=card("Menacing Ogre") %}

Quel pourrait bien être la complexité d'un jeu tel que Magic the Gathering ?

Pour commencer, il faut bien comprendre que Magic n'est vraiment pas un jeu que l'on peux ranger dans la même catégorie que les précédents. En effet :

Le fait que le jeu soit à information incomplète et qu'il y ait une part de hasard dans son déroulement est une grosse différence avec les jeux précédents mais ce n'est pas le plus gros problème car il est toujours possible de raisonner en terme d'espérance. L'introduction de probabilités dans cette affaire semble rendre les rendre les choses encore plus compliquées mais sachez que c'est néanmoins possible d'arriver à des résultats avec des jeux similaires. En 2015 par exemple, des informaticiens de l'université d'Alberta ont réussis à résoudre une variante du Poker à deux joueurs (heads-up en Limit Hold'Em) avec un algorithme nommé Cepheus.

Le fait que certaines parties peuvent ne pas se terminer est déjà un peu plus problématique. En effet, cela signifie que notre arbre des possibilités peut être infini et c'est évidemment un problème si on veut en compter les branches ! Ainsi si on souhaite mesurer la complexité de Magic pour la comparer à d'autres jeux, il va falloir trouver un autre moyen de la mesurer. Car ce n'est pas la simple existence de parties infinie qui rend un jeu complexe (la bataille est en effet un exemple de jeu simpliste qui peut ne pas se terminer si les joueurs ne mélangent pas leur défausse quand ils la récupèrent).

Précédemment j'ai aussi évoqué le fait qu'un joueur à Magic puisse avoir une infinité de choix d'actions à certains moment. Quand un joueur peut mettre en place une boucle à Magic, il peut choisir de l'effectuer autant de fois qu'il le souhaite. En réalité dans la pratique, créer un million ou un milliard de jetons correspond le plus souvent à un même cas de figure : "créer beaucoup trop de jetons". Il n'empêche que le fait qu'il est possible d'avoir à certains moments de la partie une infinité de choix, peut provoquer des situations très particulières.

Prenons l'exemple de deux joueurs possédant tous les deux sur le champ de bataille : {{ lich }}, {{ transcendence }} et {{ laboratory_maniac }}. Un joueur joue {{ menacing_ogre }} et la partie se transforme immédiatement en : "Chaque joueur choisit secrètement un nombre et celui qui a choisit le plus grand a gagné".

C'est en fait l'exemple classique du jeu qui offre aux joueurs une infinité de choix et pour lequel il n'existe pas de meilleure stratégie.

{% endtrans %} {% endblock %}