Chapitre 2 : 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

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 :

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 ?
  

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.

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

3 - Implantation du code en python

Structure des données :

• En entrée : une liste de verres contenant chacun une liste des numéros des jetons
• En sortie : une liste de verres modifiée, contenant la liste du ou des jetons correspondant au nombre de bâtonnets à prendre
  

verres=[[],[1],[1,2],[1,2,3],[1,2,3],...]

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 au rang.

Algorithme :

Début du programme
verres ←  [[],[1],[1,2],[1,2,3],[1,2,3],...]
Répéter 50 fois
	nbr_bat ← nombre de bâtonnets total
	Tant que le nbre de bâtonnets est supérieur à 0 alors
		si des jetons sont présents dans le verre alors
			jeton ← prendre au hasard un jeton parmi ceux qui restent dans le verre (librairie random)
			der_jeton ← jeton	# on mémorise le dernier jeton pris
			der_verre ← numéro du verre (nbr_bat)	# on mémorise le dernier verre utilisé
			nbr_bat ← retrancher au nombre de bâtonnets le jeton tiré
			si le nombre de bâtonnets restants = 0 alors
				afficher que l'ordinateur gagne.
				on sort la boucle tant que 	(l'instruction break) 
			fin si 			
		fin si 
		sinon 		# le verre est vide  
			jeton ← prendre au hasard 1, 2 ou 3 bâtonnets
			nbr_bat ← retrancher au nombre de bâtonnets le jeton tiré
		fin sinon 
		on affiche le nombre de bâtonnets pris par l'ordinateur de bâtonnets restants
		bat_adversaire ←  demander à l'adversaire d'entrer le nombre de bâtonnets qu'il veut prendre (input)
		tant qu'il n'a pas choisi un nombre compris entre 1 et 3 ou qu'il dépasse le nombre de bâtonnets restants 
			bat_adversaire ←  on redemande à l'adversaire d'entrer le nombre de bâtonnets qu'il veut prendre
		fin tant que 
		nbr_bat ← retrancher son choix au nombre de bâtonnets restants
		s'il ne reste plus de bâtonnets alors
			on affiche que l'humain gagne
			on retire le dernier jeton mémorisé du dernier verre mémorisé (Variable.remove(nombre))
			on sort de la boucle tant que 
		fin si 
	fin tant que 
	afficher le nouveau contenu des verres
fin répéter
Fin du programme 

Collez puis enregistrez votre code python ci-dessous

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 :

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