Ajax's Home

Quel sujet vaste que celui de l’intelligence artificielle !

Il m’en impossible ici d’en aborder toutes les facettes, ne serait-ce que parce que les principes de certaines m’échappent totalement. Non, je vais essayer de vous montrer deux trois choses, des éléments qui pourront vous aider dans votre compréhension de ce vaste monde. Peut-être que d’autres articles suivront…

En tout cas, celui-ci va d’abord vous présentez un jeu, le tic-tac-toe ( ou morpion ), ainsi qu’un possible joueur artificiel à ce jeu. Cela me permettra d’aborder l’algorithme MinMax et son “extension” Alpha-Bêta.

Après avoir vu ces joueurs déterministes, c’est à dire qu’ils joueront la même chose pour une même situation, je vous présenterais différentes méthodes d’apprentissage. Notre joueur évoluera au fil des parties.

Tout d’abord, qu’est-ce que le tic-tac-toe ?

Les règles sont simples : Le terrain de jeu contient 3×3 cases. Les 2 joueurs jouent en tour par tour. A chaque tour, un joueur remplis une case vide avec un signe/couleur qui lui correspond. Le but du jeu est de réussir à aligner 3 fois son signe, que ce soit horizontalement, verticalement ou en diagonale, avant son adversaire. A ce moment là, la partie s’arrête. Si aucun des deux n’arrivent à aligner 3 cases et que les 9 cases sont remplies, il y a match nul.
Bref, c’est un jeu que vous connaissez surement.

Maintenant, notre but va être de construire un adversaire virtuel, artificiel. Une première possibilité serait de lui dire de jouer aléatoirement sur une case libre. On conçoit assez facilement qu’un adversaire de ce type est très facile à battre.

Une deuxième possibilité va être d’utiliser un algorithme, nommé MinMax. Cette algorithme va nous donner des résultats très satisfaisant, mais pour un temps de calcul relativement long ( relativement, parce que pour un jeu de 9 cases, il est en faite très rapide; mais il devient inutilisable pour un jeu comme celui des échecs ).

Considérons l’arbre de possibilité d’une partie. Je m’explique :

Nous allons utiliser la notation suivante, les chiffres représentent les cases ordonnées de cette façon :

1 2 3
4 5 6
7 8 9
et X le signe du Joueur 1(humain), O le signe du Joueur 2(artificiel), V une case vide.

La situation actuelle est :
V X X
O O V
X O X

C’est donc à J2 de jouer. Son arbre de possibilité, avec une profondeur de 1, est

Il joue en 1=>

O X X
O O V
X O X

Il joue en 6 =>

V X X
O O O
X O X

De profondeur 1, car nous nous intéressons seulement au prochain coup.

Maintenant, nous allons nous définir une fonction d’évaluation, que l’on nommera eval() . Cette fonction évalue la partie à un instant donné. C’est en général son écriture qui est la principale difficulté de l’algorithme MinMax. En effet, comment définir une évaluation du jeu ?

Pour nous simplifier les choses, nous diront que la fonction renvoi 1 si J2 gagne, -1 si J1 gagne et 0 si il y a impression d’égalité.

Bien, maintenant, regardons notre précédent jeu, avec une profondeur d’arbre de 2 ( qui suffit à décrire toutes les possibilités restantes ).

A:J2 => 1 – B: J2 => 6

C:J1 => 6

SI J2 joue en 1, on se retrouve dans la situation A, et J1 va jouer en 6, pour se retrouver dans la situation C ( fin de partie ). Si J2 joue en 6, on se retrouve dans la situation B ( fin de partie ).

Maintenant, on a eval(A) = 0, car aucun gagnant; eval(B) = 1, car c’est J2 qui gagne; eval(C) = -1 car c’est J1 qui gagne.

L’algorithme va donc construire l’arbre complet des possibilités, puis il va remonter. Chaque départ de branche est appelé un nœud . Donc à chaque fois que l’on augmente la profondeur, on descend d’un nœud .

Une fois l’arbre complet des possibilités fait, et chaque possibilité évaluée, l’algorithme va progressivement remonter l’arbre. Pour se faire, il va prendre la valeur Minimale de toute les possibilités obtenus au départ d’un nœud .

Par exemple, la valeur en A va devenir -1, car depuis A, on peut atteindre C, qui vaut -1 et qui est la plus petite valeur que l’on obtenir depuis A. En B, la valeur restera 1, car c’est la seule valeur que l’on peut obtenir depuis B ( et donc la plus petite ).

On se retrouve ainsi avec jouer en 1 => -1, joueur en 6 => +1 . A ce moment là, l’algorithme va choisir le Maximum, c’est à dire +1, et donc J2 va jouer en 6 ( et remporter la partie ).

Voici donc le principe de l’algorithme MinMax . On comprend la lenteur de l’algorithme, car il doit explorer et évalué chacune des possibilités à partir d’une situation donnée, ce qui peut vite devenir interminable .

Imaginons maintenant une branche de l’arbre de possibilités suivant, pour un jeu arbitraire :

A

D            -        E

B:3 – C:1       F:2 – G:5 – H: 3

Que vaut eval(A) ?

Tout d’abord, trouvons eval(D). max(B,C) = 1. Donc eval(D) = 3. Ensuite, nous allons calculer eval(E). Il faudrait donc calculer max(F,G,H), c’est à dire d’abord évaluer F, puis G, puis H, en espérant par aussi qu’il n’y ai pas encore de nœud . Beaucoup de travail en perspective encore. Mais rappelons nous que A = min(D,E). Or, l’évaluation de G renvoi 5, 5 > 3. Et comme eval(E) = max(F,G,H), eval(E) >= 5 . La valeur de E sera de minimum 5. Et 5 est plus grand que la valeur obtenu en D. Donc pas besoin d’évaluer H, car de toute façon, E > D . Donc A = D = 3 .

On a sauté une étape de calcul, ce n’est peut-être pas flagrant côté temps gagné. Mais imaginé la même chose avec des arbres de profondeur 10 et plus . Le temps d’exécution de l’algorithme peut être aisément divisé par 10 !

Ce nouvel algorithme s’appelle Alpha-Bêta.

Je ne vous présente pas ici de code implémentant ces deux algorithmes pour le jeu du tic-tac-toe, car vous pourrez aisément les trouver sur http://fearyourself.developpez.com/tutoriel/sdl/morpion/ ( part6 et part7 ). Si vous n’avez pas très bien compris mon explication, je vous invite à lire celles présentés à cette adresse, elles sont très bien illustrées.

Ces différents algorithme ont le désavantage d’être déterministe. C’est à dire que pour une situation donnée, ils joueront toujours la même chose. Pour le jeu du tic-tac-toe, ce n’est pas grave, puisqu’il existe une stratégie optimale. Mais pour d’autre jeu, plus complexe, ce n’est plus utilisable.

On peut alors se tourner vers des algorithmes qui vont apprendre au fur et à mesure des parties.

Il faut savoir qu’il y a plusieurs méthodes d’apprentissage :

- Par cœur : Vous apprenez par exemple par cœur les règles. Ce sera toujours pareils. Certains bon joueurs au échecs connaissent dans certaines situation le coup optimal à jouer. Ils connaissent donc ces situations par cœur .

- Supervisé : Un apprentissage supervisé est un apprentissage assisté d’un expert du jeu. Il vous donnera les bonnes stratégies, les erreurs à ne pas commettre, …

- Par imitation : On peut apprendre par imitation en reproduisant une stratégie qu’on l’on à déjà vue.

- Par renforcement : On apprend de nos erreurs.

- Par découverte : Au fur et à mesures des jeux, on trouve de nouvelles possibilités.

Il faut savoir que certaines machines sont très fortes dans des jeux répétés contre des adversaires humains, car elles apprennent au fur et à mesures à la fois de nouvelles stratégies, les renforcent, et arrivent même à prédire ce que l’humain va jouer. Je citerais par exemple le résultat d’une thèse, SAGACE ( dont je ne présenterais pas le fonctionnement ici, car il est plutôt complexe ).

Alors qu’est-ce que nous donnent un adversaire qui va apprendre au fur et à mesure des parties ?

J’ai réalisé un adversaire qui apprend à jouer au tic-tac-toe par imitation ( le code python est disponible tout en bas de l’article ).

C’est à dire qu’il va, au fur et à mesure des différents jeux, voir ce que je joue dans une situation donné. Si il se retrouve dans la même situation, il jouera alors ce que j’ai joué.

Il est clair que les premières parties sont gagnées haut la main par le joueur humain. Mais on sent tout doucement l’IA tendre vers une stratégie optimale ( si on considère que le joueur humain joue de façon optimale ). Au bout d’un moment, il n’est plus possible de gagner, toutes les parties mènent à égalités, si l’on joue de manière optimale.

Pour gagner, à ce moment là, il faut jouer un coup inattendu, voir idiot, pour se retrouver dans une situation que la base de données des coups précédemment joué ne connais pas. Et à ce moment là, vous pourrez facilement gagné.

De même, au bout d’un moment, il n’y a plus possibilité de gagné, même de cette façon.

Je ne présente pas les autres méthodes d’apprentissages, peut-être seront-elles sujets d’un autre article, car celui-ci comment à vraiment devenir long.

Sur ce, je vous souhaite donc une agréable journée, et de belles parties de tic-tac-toe .

Le code présenté ci-dessus ne gère pas les différentes symétries des situations, il reste basique et à des fins de test.

from random import *

terrain = [0,0,0,0,0,0,0,0,0,0]
# 1 2 3
# 4 5 6
# 7 8 9
#Rien : 0, Joueur : 1, IA : 2
gagnant = 0

def check_terrain():
    global terrain,gagnant
    gagnant = 0
    if (terrain[1] == terrain[2]) and (terrain[2] == terrain[3]) :
        gagnant = terrain[2]
    elif (terrain[2] == terrain[5]) and (terrain[5] == terrain[8]) :
        gagnant = terrain[5]
    elif (terrain[4] == terrain[5]) and (terrain[5] == terrain[6]) :
        gagnant = terrain[5]
    elif (terrain[7] == terrain[8]) and (terrain[9] == terrain[8]) :
        gagnant = terrain[7]
    elif (terrain[1] == terrain[4]) and (terrain[4] == terrain[7]) :
        gagnant = terrain[1]
    elif (terrain[3] == terrain[6]) and (terrain[6] == terrain[9]) :
        gagnant = terrain[3]
    elif (terrain[1] == terrain[5]) and (terrain[5] == terrain[9]) :
        gagnant = terrain[5]
    elif (terrain[3] == terrain[5]) and (terrain[5] == terrain[7]) :
        gagnant = terrain[5]
    else :
        eg = 1
        for i in range(1,10):
            if (terrain[i] == 0) :
                eg = 0
        if (eg==1):
            gagnant = 3
    return gagnant

def cherche_strat():
    global terrain
    t = 0
    bdd = open('bdd.txt','r')
    while 1:
        txt = bdd.readline()
        if txt=='':
            t=0
            break
        if ((txt[0] == str(terrain[1]) or txt[0] == '*') and (txt[1] == str(terrain[2]) or txt[1] == '*') and (txt[2] == str(terrain[3]) or txt[2] == '*') and (txt[3] == str(terrain[4]) or txt[3] == '*') and (txt[4] == str(terrain[5]) or txt[4] == '*') and (txt[5] == str(terrain[6]) or txt[5] == '*') and (txt[6] == str(terrain[7]) or txt[6] == '*') and (txt[7] == str(terrain[8]) or txt[7] == '*') and (txt[8] == str(terrain[9]) or txt[8] == '*')):
            t = txt[10]
            break
    bdd.close()
    return t

def play_ia():
    global terrain

    t = cherche_strat()
    print t
    if (t!=0) :
        terrain[int(t)] = 2
    else:   
        #IA Aleatoire
        k = randint(1,9)
        while(terrain[k] != 0):
            k = randint(1,9)
        terrain[k] = 2

    return 0

def affiche_terrain():
    global terrain
    print ""
    print terrain[1],terrain[2],terrain[3]
    print terrain[4],terrain[5],terrain[6]
    print terrain[7],terrain[8],terrain[9]
    return 0

def joueur():
    global terrain
    i = input("Jouer sur la case : ")
    while(terrain[i] != 0):
        i = input("Jouer sur la case : ")

    #Imitation
    if (cherche_strat() == 0):
        bdd = open('bdd.txt','a')
        bdd.write(str(terrain[1]*2 % 3) + str(terrain[2]*2 % 3) + str(terrain[3]*2 % 3) + str(terrain[4]*2 % 3) + str(terrain[5]*2 % 3) + str(terrain[6]*2 % 3) + str(terrain[7]*2 % 3) + str(terrain[8]*2 % 3) + str(terrain[9]*2 % 3) + ' ' + str(i) + '\n')
        bdd.close()

    terrain[i] = 1
    return 0

flag = randint(0,1)
flag = flag * 2 - 1

while(check_terrain() == 0):
    if(flag == 1) :
        affiche_terrain()
        joueur()
        flag = -flag
        if(check_terrain() != 0):
            break
    elif(flag == -1) :
        play_ia()
        flag = -flag

k = check_terrain()
if(k ==1) :
    print "Vous avez gagner !"
elif(k ==2 ):
    print "L'IA gagne !"
else:
    print "Match NUL !"

print check_terrain()

Cet article a été publié le Jeudi 6 août 2009 à 15 h 45 min et est classé dans En vrac. Vous pouvez en suivre les commentaires par le biais du flux RSS 2.0. Vous pouvez laisser un commentaire, ou faire un trackback depuis votre propre site.