TP 2 : IA et Jeux

Le développement d’IA pour les jeux a été depuis le début et représente encore un important moteur d’innovation (par exemple, voir Turochamp, une IA pour les échecs développée par Turing et Champernowne dès 1948). D’une part, il est facile pour des chercheurs de communiquer au grand public des avancées dans ce domaine (voir par exemple le retentissement du programme AlphaGo dans la presse grand public) et ses applications au marché du jeu vidéo sont directes. D’autre part, les jeux représentent des cas d’études déjà complexes en logique, plannification et représentation des connaissances où il est facile de se confronter à des humains. Dans ce TP, nous verrons deux types d’IA pour les jeux :

• Une IA stochastique qui essaie d’apprendre le comportement du joueur pour le battre. Nous montrerons cette approche via le jeu “Pierre Feuille Ciseau”.
• Une IA qui simule plusieurs tours d’un jeu simple et choisit son mouvement suivant en fonction de l’existance d’une stratégie gagnante.

Pierre Feuille Ciseau

Le jeu de pierre feuille ciseau est un jeu célèbre où deux joueurs choisissent simultanément une des trois options suivantes : Pierre, Feuille ou Ciseau. La pierre gagne contre les ciseaux, les ciseaux gagnent contre la feuille et la feuille gagne contre la pierre. Tous les autres cas sont des cas d’égalité. Si ce jeu semble être un pur jeu de hasard, il se trouve que nous autres humains sommes de très mauvais générateurs aléatoires et nos comportements sont assez prédictibles. On peut donc “apprendre” un modèle du comportement du joueur pour gagner un avantage statistique.

Vous trouverez dans le fichier pfc.py une implémentation simple du jeu de Pierre Feuille Ciseau avec une IA toute bête : elle choisit uniformément une option parmi les trois disponibles. La stratégie de l’IA est abstraite dans la fonction iaMove(). Le code est fait de tel sorte qu’on pourra aussi intervenir facilement sur la stratégie du joueur via la fonction playerMove() qui pour l’instant demande au joueur le coup suivant. La partie s’arrête lorsqu’un des deux joueurs atteint 50.

def playerMove():
    return "p"

Les humains sont notoirement de mauvais générateurs uniformes. On va essayer d’exploiter cette faiblesse pour les battre ! Pour cela, on va garder en mémoire la chose suivante : on va maintenir un dictionnaire history tel que history[c1][c2] contient le nombre de fois où le joueur a joué le coup c2 après avoir joué c1 pour c1 et c2 qui sont dans “p”, “f” et “c”. L’IA va utiliser l’historique pour contrer le coup le plus probable : si le joueur vient de jouer c1 alors on va chercher que c2 qui maximise history[c1][c2] et jouer le coup qui bat c2.

def iaMove(last_c):
    win = {"p": "f", "f": "c", "c": "p"}
    if last_c == "":
        return choices[randint(0, 2)] # Début de partie
    else:
        coup_probable = maxKey(history[last_c])
        return win[coup_probable]
        # maxKey(history[last_c]) vaut le coup que 
        # le joueur a joué après avoir joué last_c
        # win[coup_probable] est donc le coup à jouer pour le contrer !

if last_c != "": # Si on n'est pas au début de la partie
    history[last_c][c] += 1

Il s’avère que retenir seulement le dernier coup n’est général pas assez bon pour battre un humain. On va essayer de retenir les trois derniers coups. On modifie donc l’initialisation de history ainsi:

history = {a+b+c: {"p":0, "f":0, "c":0} for a in "pfc" for b in "pfc" for c in "pfc"}

print(history)

>>> {'ppp': {'p': 0, 'f': 0, 'c': 0}, 'ppf': {'p': 0, 'f': 0, 'c': 0}, 'ppc': {'p': 0, 'f': 0, 'c': 0}, 'pfp': {'p': 0, 'f': 0, 'c': 0}, 'pff': {'p': 0, 'f': 0, 'c': 0}, 'pfc': {'p': 0, 'f': 0, 'c': 0}, 'pcp': {'p': 0, 'f': 0, 'c': 0}, 'pcf': {'p': 0, 'f': 0, 'c': 0}, 'pcc': {'p': 0, 'f': 0, 'c': 0}, 'fpp': {'p': 0, 'f': 0, 'c': 0}, 'fpf': {'p': 0, 'f': 0, 'c': 0}, 'fpc': {'p': 0, 'f': 0, 'c': 0}, 'ffp': {'p': 0, 'f': 0, 'c': 0}, 'fff': {'p': 0, 'f': 0, 'c': 0}, 'ffc': {'p': 0, 'f': 0, 'c': 0}, 'fcp': {'p': 0, 'f': 0, 'c': 0}, 'fcf': {'p': 0, 'f': 0, 'c': 0}, 'fcc': {'p': 0, 'f': 0, 'c': 0}, 'cpp': {'p': 0, 'f': 0, 'c': 0}, 'cpf': {'p': 0, 'f': 0, 'c': 0}, 'cpc': {'p': 0, 'f': 0, 'c': 0}, 'cfp': {'p': 0, 'f': 0, 'c': 0}, 'cff': {'p': 0, 'f': 0, 'c': 0}, 'cfc': {'p': 0, 'f': 0, 'c': 0}, 'ccp': {'p': 0, 'f': 0, 'c': 0}, 'ccf': {'p': 0, 'f': 0, 'c': 0}, 'ccc': {'p': 0, 'f': 0, 'c': 0}}

On va modifier le code pour que l’historique contienne désormais les trois derniers coups. Pour cela, on modifie la partie du code qui met à jour last_c : on testera désormais si last_c a une longueur (len) plus petite que 3. Si oui, on ajoutera le dernier coup du joueur. Sinon, on ajoutera le dernier coup du joueur et on supprimera le premier caractère de last_c (puisqu’on ne garde en mémoire que les 3 derniers coups). On modifie donc la partie suivante du code :

if last_c != "": # Si on n'est pas au début de la partie
    pass # TODO: Mettre à jour history!
        
last_c = c # On retient le dernier coup

On rappelle qu’on peut concaténer des chaînes de caractères avec + : par exemple last_c=last_c+"p" ajoute “p” à la fin de la chaîne last_c. De même, on pourra utiliser s[i:] prendre une chaîne de caractère à partir du ième caractère. Par exemple, "coucou"[1:] vaut "oucou". On aura quelque chose sur cette structure :

if len(last_c) < 3: # Si on n'est pas au début de la partie
    # TODO: ajouter le coup joué par le joueur à last_c
else:
    # TODO : 
    # 1. mettre à jour history 
    #    (les trois derniers coups sont stockés dans last_c
    #     et le joueur vient de jouer c)
    # 2. mettre à jour last_c pour que ce soit les trois derniers coups joués, 
    #    soit les trois derniers caractères de last_c+c

if len(last_c) < 3: # Si on n'est pas au début de la partie
    last_c = last_c+c # on ajoute le dernier coup joué
else:
    # on incrémente le nombre de fois à c a été joué après last_c
    history[last_c][c] = history[last_c][c]+1
    # on met à jour last_c : on garde les deux derniers coups last_c[1:] et on ajoute le dernier coup c joué 
    last_c = last_c[1:]+c

Normalement, il n’y a pas besoin de modifier la façon dont joue l’IA car c’est la même stratégie qu’avant : on joue le coup qui contre le coup le plus probable de history.

Aller plus loin

En fait, l’IA qu’on a vu bat facilement des humains mais se ferait prendre au même piège si elle jouait contre une autre IA qui essaierait d’apprendre la stratégie de notre IA. Des gens tiennent régulièrement une compétition où différentes IA s’affrontent au jeu du pierre-feuille-ciseau, voir http://www.rpscontest.com/. Il ne suffit pas ici de battre un joueur humain, il faut être capable de s’adapter à une stratégie adverse et de l’apprendre à la volée ! Voir ici pour le champion.

Jeu de Nim et Arbres de Recherche

On va désormais s’intéresser au jeu de Nim. Le jeu est le suivant : N bâtons sont disposés sur un plateau. Chaque joueur, à son tour, peut enlever 1, 2 ou 3 bâtons. Le joueur qui enlève le dernier bâton a perdu. Un petite implémentation du jeu avec une IA qui joue aléatoirement le prochain coup peut être trouvée dans le fichier nim.py.

Cet exercice est une excuse pour illustrer les arbres de recherche, une technique qui peut être appliquée à de nombreux jeux. La version qu’on va voir ici est sa forme la plus simple sur un jeu extrêmement simple. Sa complexité est bien trop élevée pour fonctionner dans la plupart des jeux cependant et beaucoup de variations ont été proposées pour la rendre praticable dans des cas plus difficiles (Échecs, Go, etc.). Nous expliquons une partie de ces approches dans la partie Aller plus loin.

On va donc utiliser une stratégie basée sur les arbres de recherche : on explore toutes les parties possibles depuis l’état actuel du jeu et on essaie de jouer un coup qui assure la victoire à l’IA. On représente les parties possibles par un arbre de recherche. Chaque noeud de l’arbre est un état du jeu. Dans notre cas, le nombre de bâtons restant ainsi que le joueur qui doit jouer le prochain coup. Chaque noeud a autant d’enfants que de coups possibles pour le joueur courant, chaque enfant étant étiquetté par l’état du jeu après qu’un coup ait été joué. Une partie est donc un chemin dans cet arbre.

Par exemple, voici une représentation des parties qu’on peut jouer depuis l’état initial où l’IA (rose) commence et qu’il y a 6 bâtons sur le plateau :

L’explosion combinatoire peut être contenue ici en remarquant que ce n’est pas tant le déroulement de la partie qui importe plutôt que l’état dans lequel on se trouve à un moment du jeu. Ainsi, si l’IA joue 1 puis que le joueur joue 2, on se retrouve dans la même situation que si l’IA joue 2 puis que le joueur joue 1.

On dit qu’un état du jeu est gagnant pour un joueur (IA ou vous) si c’est à ce joueur de jouer et s’il a un coup qui lui garantit de gagner s’il joue bien. On dit qu’un état est perdant pour un joueur A si quelque soit le coup que joue A, si l’autre joueur B joue bien, alors B gagnera.

1. Repérer sur le schéma précédent quels sont les états gagnants/perdants pour l’IA (rose) et vous (vert).

Correction

2. Une bonne IA peut-elle donc gagner la partie qui commence avec 6 bâtons ?

Correction

Oui, l’IA a ici une stratégie gagnante !

3. Montrer qu’un état est soit perdant soit gagnant (on pourra faire une récurrence sur le nombre de bâtons).

Correction

Clairement, quand il reste 0 bâton, l’état est soit gagnant soit perdant. Admettons que tous les états où il y a i < N bâtons sont soit gagnants soit perdants pour l’IA. Alors quand il y a N bâtons et que c’est à l’IA de jouer, soit l’état N − 1, N − 2 ou N − 3 est gagnant pour l’IA auquel cas, l’IA peut jouer le bon coup pour gagner et l’état à N bâtons est gagnant. Soit ces trois états-là sont perdants pour l’IA auquel cas, l’état avec N bâtons est forcément perdant pour l’IA.

Si c’est au joueur de jouer, un raisonnement symétrique permet de conclure.

On en déduit la fonction suivante :

def gagnants(N):
    g = [False]*(N+1)
    g[0] = True # Si 0 bâton, le joueur courant gagne   
    if N>0: # Si 1 bâton, le joueur courant perd forcément
        g[1]=False 
    if N>1: # Si 2 bâtons, le joueur courant gagne (enlève 1 bâton)
        g[2]=True 
    if N>2: # Si 3 2 bâtons, le joueur courant gagne (enlève 2 bâton)
        g[3]=True 
    
    # Calcul la stratégie pour K>3.
    for k in range(4,len(g)):
        # on est gagnant si un des 3 états accessibles est perdant
        g[k] = not(g[k-1]) or not(g[k-2]) or not(g[k-3]) 
    return g

La fonction gagnants(N) retourne une liste de taille N+1 tel que gagnants[i] vaut True si l’état où il reste i bâtons est gagnant pour le joueur courant.

def iaMove(nTiles):
    g = gagnants(nTiles)
    if not(g[nTiles-1]): # si g[nTiles-1] vaut False, cela veut dire 
                         # qu'un joueur qui doit jouer avec nTiles-1 
                         # est en position perdante. Donc si l'IA joue 1 bâton,
                         # ce sera une position gagnante pour elle
        return 1
    elif not(g[nTiles-2]): # pareil pour 2 bâtons
        return 2
    elif not(g[nTiles-3]): # pareil pour 3 bâtons
        return 3
    else: # sinon, on est dans un état perdant, donc on joue 1.
        return 1

Aller plus loin

Une stratégie facile à expliciter. La stratégie gagnante du jeu de Nim peut être calculée encore plus rapidement qu’en faisant une exploration exhaustive comme on l’a montré ci-dessus. En observant le tableau gagnants[N], on se rend compte qu’il est très régulier : il y a systématiquement trois True avant un False. On peut rapidement se convaincre qu’une position avec N bâtons est perdante pour le joueur en cours si et seulement si N=4K+1 pour un certain K. En effet, si on se retrouve dans cette position, on ne peut que laisser un nombre de bâton de la forme 4L, 4L+2, 4L+3 à l’autre joueur, donc l’autre joueur ne se retrouvera pas dans la position critique où il reste qu’un seul bâton. L’autre joueur pourra alors nous forcer à nouveau dans une position de la forme 4L’+1 jusqu’à ce qu’il n’y ait plus qu’un bâton. On n’a donc pas besoin d’explorer tous les états du jeu pour décider de la stratégie. Une solution si simple est un cas très rare dans les jeux !

Complexité rédhibitoire des arbres de recherche. Comme dans le cas de la logique, l’approche par arbres de recherche rencontre très rapidement ses limites calculatoires. Dans la plupart des jeux, une exploration exhaustive de tous les états du jeu n’est pas possible du fait qu’il y ait un grand nombre de parties possibles ou de configurations du jeu. Par exemple, aux échecs, on peut montrer que le nombre d’états possibles du jeu est de l’ordre de 10⁴⁴, un nombre qui est hors de portée des ordinateurs les plus puissants (voir ici pour d’autres exemples du nombre d’états de différents jeux). Dans le cas où on ne peut pas se permettre de simuler toutes les parties possibles, on peut se limiter à simuler un nombre borné p de coups et choisir “la meilleure option”. Cela sous-entend qu’on a une mesure qui peut nous indiquer si un état est meilleur qu’un autre, c’est-à-dire qu’on peut associer à chaque état du jeu un score d tel que plus d est grand, plus on pense que c’est une bonne situation pour gagner. On cherchera alors à trouver le coup qui nous donne le meilleur score possible après p coups, si le joueur adverse joue sa meilleure stratégie. On utilisera pour cela un algorithme connu sous le nom de Minimax.

Cette approche souffre cependant encore de deux problèmes :

1. Parfois, le nombre p de coups qu’on doit explorer pour battre un joueur humain doit être grand, trop grand pour explorer toutes les parties possibles. On utilisera alors des algorithmes qui éviteront de visiter certaines branches, par exemple, si on est sûr que la branche ne peut mener qu’à des états pires que dans une stratégie qu’on a déjà trouvée. Cette technique est connue sous le nom d’αβ-élagage.
2. Il est difficile de définir une notion de score pertinente mesurant effectivement si position est intéressante ou pas. On a besoin d’utiliser des heuristiques dont l’efficacité peut varier énormément. Une façon de contourner le problème est d’apprendre cette heuristique à partir de parties antérieures (soit en regardant un historique des parties jouées par des humains dans des compétitions, soit en se basant sur les parties jouées avec l’IA jusqu’ici). C’est l’idée principale au coeur d’une technique appelée la recherche arborescente de Monte Carlo qui apprend des heuristiques pour explorer les branches les plus prometteuses de l’arbre de recherche. Cette technique est celle qui a été employée dans le programme AlphaGo qui est la première IA a avoir battu des maîtres du jeu de Go dont la complexité combinatoire avait été un obstacle insurmontable jusqu’ici.