NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : Terminale générale, enseignement de spécialité NSI

D
É
C
O
N
N
E
C
T
É

Intelligence Artificielle IA

1 - Introduction et historique

Donald Michie (1923-2007) est un chercheur britannique en intelligence artificielle reconnu pour avoir travaillé au déchiffrage des messages codés allemands pendant la seconde guerre mondiale. Tout comme Alan Turing, avec qui il a travaillé à Bletchley Park, Michie s’intéresse à théoriser les mécanismes du jeu d’Échecs ; les deux hommes entretiennent régulièrement des discussions, sur la possibilité de construire des programmes informatiques qui pourraient faire preuve d’intelligence et capables d’apprendre par eux-mêmes. Ils mettent respectivement au point les programmes Turochamp (d’Alan Turing et David Champernowne) et Machiavelli (de Donald Michie et Shaun Wylie) vers la fin des années 1940, alors qu’il n’existe pas encore de machine pour exécuter les instructions. Turochamp et Machiavelli ont joué quelques parties par correspondance, mais les calculs fastidieux ont rapidement découragé les concepteurs... Ces réflexions sur la possibilité de créer des machines « qui apprennent » amènent Donald Michie à développer en 1961 une machine destinée à jouer, et surtout à apprendre à jouer, au Tic-Tac-Toe. Il la nomme MENACE (Matchbox Educable Noughts And Crosses Engine).

Source : CNRS Images des Mathématiques

Elle est composée de 304 boîtes d’allumettes vides et de perles de couleur. L’objectif de Michie n’est pas d’élaborer une machine qui jouerait parfaitement dès le début, mais de construire un dispositif qui ne dispose d’aucune information préalable - à part les règles du jeu - et qui devient un joueur expert avec de la pratique.

Vu la complexité de cette machine, on va s'appuyer sur les règles du jeu de Nim

2 - Apprentissage du jeu de Nim

Sources : Marie Duflot-Kremer

2.1 - Principe

Tout d'abord il faut que l'ordinateur connaisse les règles du jeu :

Le jeu se joue à tour de rôle et le perdant est celui qui ne pourras plus prendre de bâtonnets
Il se joue avec 9 bâtonnets (on se limite à 9 pour simplifier la compréhension)
On ne peut prendre que 1, 2 ou 3 bâtonnets
C'est l'ordinateur qui commence et l'homme joue après lui

Au départ on dispose au-dessus de chaque bâtonnet 9 verres contenant des jetons numérotés de 1 à 3, représentants le nombre d'allumettes que peut prendre l'ordinateur à chaque coup :

nim

On retire les bâtonnets de la gauche vers la droite, donc lorsqu'il reste :

9 bâtonnets l'ordinateur pourra enlever 1, 2 ou 3 batônnets,
8 bâtonnets l'ordinateur pourra enlever 1, 2 ou 3 batônnets,
... jusqu'à ce qu'il en reste 3,
2 bâtonnets l'ordinateur ne pourra plus qu'en enlever 1 ou 2,
1 bâtonnet l'ordinateur ne pourra prendre qu' 1 bâtonnet.

Questions :

Lorsqu'il reste 8 bâtonnets, pourquoi le verre contient-il encore tous ces jetons alors que s'il reste 4 bâtonnets le verre est vide ?
Lorsque les verres contiennent 2 ou 3 jetons, l'ordinateur peut-il en choisir un au hasard parmi les 3 ou a-t-on énoncé une règle ci-dessus ?

2.2 - Programme en langage python

Structure des données :

En entrée : une liste de verres contenant chacun une liste des numéros des jetons : verres=[[],[1],[1,2],[1,2,3],[1,2,3],...]
En sortie : une liste de verres modifiée, contenant la liste du ou des jetons correspondant au nombre de bâtonnets à prendre

Afin que le verre 1 corresponde bien à son indice on peut commencer par un élément de rang 0 vide, cela évitera de retrancher 1 à l'indice.

Programme de test

""" IA Jeu de Nim
le jeu se joue contre l'homme avec 9 Allumettes. C'est l'ordinateur qui commence
On dispose 9 gobelet contenant : 3 jetons (1, 2 et 3) chacuns à l'exeption du 2ème qui comprens 2 jetons (1 et 2) et du permier qui n'a qu'un jeton (1)
Chaque gobelet contien le nombre d'allumettes que peut prendre l'ordinateur selon le nombre d'allumettes restant
l'ordinateur commence et tire au hasard 1 des 3 jetons du gobelet 9 ...
pour éviter les erreurs d'indices, on placera un gobelet 0 vide
l'ordinateur n'a aucune stratégie mais va apprendre de ses erreurs pour gagner

IA : Jeu de nim décrit par Marie Duflot-Kremer
https://members.loria.fr/MDuflot/files/med/doc/Nim/ficheIAnim.pdf
https://members.loria.fr/MDuflot/

Pour un apprentissage rapide laisser 7 ou 4 alummettes à l'IA pour la faire perdre."""

import random
verres=[[],[1],[1,2],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]] # on lui donne ici tous les coups possibles
###      0  1    2      3       4       5       6       7       8       9     # indices de la liste

nb_bat=9

while(verres!=[[], [1], [2], [3], [], [1], [2], [3], [1, 2, 3], [1]]): # combinaison gagnante
    while (nb_bat!=0):                         # tant qu'il y a des allumettes

if len(verres[nb_bat])!=0:             # s'il y a un ou plusieurs jetons dans le gobelet courant
            random.shuffle(verres[nb_bat])     # on mélange les jetons

ordi=verres[nb_bat][0]             # on tire un jeton au hasard
            verre_select=nb_bat                      # on mémorise le gobelet choisi
            jeton=ordi                         # on mémorise le jeton tiré
            nb_bat-=ordi
            if nb_bat==0:                      # s'il reste aucune allumette
                print ("j'ai gagne")

else:
            ordi=random.randint(1,3)           # sinon on prend 1 chiffre au hasard
            nb_bat-=ordi

if nb_bat!=0:
            p=int(input ("J'ai pris {} allumettes, il reste {} allumettes combien en prends tu ? ".format(jeton,nb_bat)))
            while p<=0 or p>3 or nb_bat-p<0:
                p=int(input ("impossible ! il y a {0} allumettes combien en prends tu ?".format(nb_bat)))
            print (p)
            nb_bat-=p
            if nb_bat==0:
                print ("tu as gagné")
                verres[verre_select].remove(jeton)      # on retire le dernier jeton mémorisé du verre

print (verres)
    print ("nouvelle partie")
    nb_bat=9

print("Je suis maintenant imbattable")

3 - Réseau de neurones artificiels

Leur origine remonte à 1957 avec Franck Rosenblatt qui inventa le perceptron qui est un algorithme se basant sur le modèle de la structure de la cellule nerveuse.

Représentation du réseau de neurones du jeu de Nin

En disposant de très grands jeux de données et d’une forte puissance de calcul, les machines peuvent désormais reconnaître des objets, traduire des discours, s’auto-entraîner à identifier des motifs complexes, apprendre à définir une stratégie et gérer des imprévus en temps réel

Revoir l'exemple de machine learning de première : le KNN

Apprentissage automatique et interface graphique

Téléchargez le fichier suivant : graph.zip

Décompressez ces fichiers dans vos documents, dans le même répertoire contenant votre programme précédent

Ajoutez au début de votre programme les lignes suivantes :

# Programmation d'une IA pour jeu de Nim from ANim import * # Charge la librairie graphique pour l'animation def afficher_IA(): # Tâche indépendante, qui se lance en parallèle avec le programme global boucle,tour,decale,gagne,nbr_bat,bat_adversaire while boucle: i=1 fenetre.fill(0xA5BFBC) # couleur de fond for verre in liste_verres: # Dessine les verres et leurs jetons verre.affiche_verre(i) i+=1 i=Taille_fenetre-120 for al in range (nbr_bat): if al<nbr_bat-decale: fenetre.blit(img_allumette,(i,350)) # Dessine les allumettes sélectionnées else: fenetre.blit(img_allumette,(i,310)) # Dessine les allumettes restantes i-=150 for jeton1 in tirage: fenetre.blit(img_jetons[jeton1[1]-1],((MaxAllumettes-jeton1[0])*150+70,260)) # dessine les jetons sélectionnés pendant la partie if tour=="adversaire" or gagne=="adversaire": fenetre.blit(img_joueur[1],(10,450)) # Dessine le joueur adversaire if tour=="IA" or gagne=="IA": fenetre.blit(img_joueur[0],(10,450)) # Dessine l'ordinateur (IA) if tour=="adversaire" : fenetre.blit(img_jetons[bat_adversaire-1],(150,500)) # dessine le jeton choisi par l'adversaire if gagne=="IA" or gagne =="adversaire": fenetre.blit(img_coupe,(240,500)) # dessine la coupe pour le vainqueur pygame.display.update() # Affiche tout durant 1/20ème de seconde puis recommence clock.tick(20) th1=threading.Thread(target=afficher_IA) # Lance la tâche en parrallèle du programme th1.start()

Remplacer la partie du code où on demandait à l'utilisateur de choisir le nombre de bâtonnets :

On pourrait faire jouer l'adversaire de l'IA de manière complètement aléatoire. Pour gagner en vitesse d'apprentissage de l'IA, l'adversaire va faire un choix menant à la victoire lorsque c'est possible.

Expliquez les lignes 21 à 23 et indiquez comment l'adversaire arrive à gagner au début des parties

Supprimez la ligne qui définit la variable verres, elle existe déjà dans la librairie ANim importée.

Enfin ajoutez une pause d'une seconde à la fin du programme

Si vos variables correspondent à celles de l'algorithme et que vous avez scrupuleusement suivi les indications ci-dessus, les verres devraient se vider de leurs jetons.

Si le programme ne s'arrête plus avec stop ni la croix de l'interface graphique, sélectionner la fenêtre Edupython et appuyer sur ctrlF2

Animations

En observant les lignes de codes de la fonction afficher_IA ci-dessous, ajoutez au programme les variables tour et gagne suivies d'une pause

La liste tirage comprend les listes des tirages effectués [nbr_bat,jeton] de chaque tour

Une fois le nombre de jetons choisi par l'IA, ajouter à tirage [nbr_bat,jeton] suivi d'une pause

A la fin de la partie, pensez à remettre certaines variables à leur état initial.

Décalage des allumettes

Lorsque l'IA a choisi le jeton on peut aussi l'affecter la variable decale suivi d'une pause

Lorsque l'adversaire à choisi le nombre de bat_adversaire on peut aussi l'affecter à la variable decale suivi d'une pause

Collez puis enregistrez votre code python ci-dessous

Fond : Texte : Tables : Thème du langage:

Contenu sous licence CC BY-NC-SA 3.0
Pascal Hassenforder 17/08/2021
MAJ le 28/09/2021
Marie Duflot-Kremer