Morpion python : Créer un morpion et son I.A qui apprend toute seule à jouer | Morpion IA | tic tac toe python
Deviens un vrai monstre du machine et du deep learning en lisant 5 à 10 minutes par jour ?
Quand j'étais en première année de licence, le premier jeu que l'on m'a appris à coder était le morpion.
Je ne me rappelle pas combien de temps j'ai pris pour coder ce jeu, j'en ai pris une tonne !
Je suis resté coincé des heures sur l'affichage du plateau.
Mais bon ce n'est pas grave, j'ai toujours pris beaucoup plus de temps que les autres pour apprendre les choses même les plus simples, ce n’est pas pour autant que j'ai mal fini.
Aujourd'hui, je suis doctorant et maintenant c'est moi le prof, et c'est moi qui enseigne le morpion aux étudiants de mon université.
J'avoue que je le prends à la cool avec les étudiants, quand je les vois je me revoie moi et mes difficultés.
Quoi qu'il en soit dans ce tutoriel je vous montrerais comment créer un morpion, mais également comment est-il possible à partir de rien de créer une intelligence artificielle capable d'apprendre toute seule.
Cela se fait à l'aide de ce que l'on appelle couramment en IA l'apprentissage par renforcement. C'est-à-dire qu'à l'origine l'IA ne sait pas du tout jouer au morpion.
Puis, elle va jouer une partie, 2 parties, 3 parties et ainsi de suite. Et après chaque partie elle en retira une petite expérience. Exactement comme le ferait un humain.
Au bout d'un certain nombre de parties, elle sera de plus en plus rodée et deviendra de plus en plus imbattable, car elle développera une sorte d'intuition. Rien qu'en voyant la situation du plateau actuelle.
Dans un premier temps, je vous expliquerais les différentes notions d'intelligence artificielle dont vous avez besoin pour comprendre ce tutoriel.
À la suite, de cela nous verrons qu'elles sont les bibliothèques python qu'il est nécessaire d'installer pour pouvoir faire de l'apprentissage automatique.
Enfin une fois tous les prérequis réunis, nous verrons comment créer un jeu de morpion simple avec 2 joueurs humains.
À l'issue de cela, nous modifierons ce jeu, pour que ce ne soit plus des humains qui jouent, mais pour que ce soit le morpion qui joue contre lui-même et qui se faisant comprenne le plateau de jeu.
Les notions d'intelligence artificielle dont nous aurons besoin
Dans cet article, nous aurons principalement besoin de deux notions classiques de l'intelligence artificielle, il s'agit de l'apprentissage par renforcement et de la classification.
Qu'est ce que l'apprentissage par renforcement ?
L'apprentissage par renforcement consiste à mettre une I.A dans un environnement dont elle n'a aucune connaissance au préalable et dont elle va devoir s'accommoder.
Pour ce faire, il est nécessaire de lui indiquer ce qui est bon et ce qui n'est pas bon.
C'est pour cela que deux concepts fondamentaux de l'apprentissage par renforcement sont les concepts de récompense et de punition.
L'I.A, ne connaissant rien à son environnement va effectuer des opérations aléatoirement, dans notre cas il s'agira de jouer un coup de morpion.
Si l'action a une issue positive, par exemple si l'action que l'I.A nous a permise de gagner le jeu, l'I.A sera récompensée.
Sinon si par exemple l'action qu'elle a effectuée l'a amené à perdre la partie de morpion, elle sera punie.
Informatiquement, cela se traduit un peu à la manière de YouTube, si l'IA à un bon comportement ont lui mettra un pouce bleu, ce pouce bleu est généralement représenté informatiquement par la valeur 1. À l'inverse, si le comportement de l'IA est mauvais elle aura droit à un joli pouce rouge qui se matérialisera informatiquement par la valeur zéro.
En plus de l'apprentissage par renforcement, nous aurons besoin d'une deuxième notion de machine learning nommée classification supervisée.
La classification supervisée c'est quoi ?
La classification supervisée est l'une des premières notions abordées en machine learning. Elle consiste à attribuer automatiquement une catégorie (ou une classe) à des données dont on ne connaît pas la catégorie.
Pour cela, il faut utilisé un classifieur, il s'agit d'un algorithme d'apprentissage automatique que l'on entraine sur des données similaires à celles que l'on souhaite classer.
En dehors du morpion, la classification supervisée peut être utilisée pour la résolution de nombreux problème de la vie réelle, tels que la détection de défaut d'usinage, de fraude, de maladie, le tri automatique de courrier, de document ou encore de vidéo, la reconnaissance d'images ( ex : reconnaissance de caractères, plantes, pollens, etc...). Et de manière générale, également toutes les tâches ou un choix est requis.
Pour illustrer le fonctionnement de la classification supervisée , je vais prendre le cas d'une application de reconnaissance de fleurs censée classer les trois types de fleurs montrée ci-dessous :
Pour résoudre ce problème, il est nécessaire de créer un classifieur. Une machine à classer, trier les fleurs.
Il est possible de se faire l'image d'un tels classifieur, en imaginant une boîte noire à laquelle, l'on va envoyer toutes les informations sur les fleurs en notre possession et qui en sortie nous fournira sa catégorie.
.
Il est important de comprendre qu'un tel modèle mathématique ne peut être obtenu qu'en analysant au mieux les données réelles des fleurs. C'est d'ailleurs pour cela qu'afin de le construire, il sera nécessaire d'entraîner le classifieur sur les données réelles du problème.
La procédure d'entraînement est la suivante :
À partir des données que l'on a du problème, 2 lots sont constitués aléatoirement:
un lot d'apprentissage que l'on nommera base d'apprentissage
un lot de test que l'on nommera base de test.
Le premier lot servira à entraîner le classifieur tandis que le second servira à tester le classifieur.
Lors de l'entraînement, les exemples sont soumis un à un dans un ordre aléatoire au classifieur.
Pour chaque exemple soumis, deux cas sont possibles.
Le premier est le classifieur trouve la réponse correcte, dans ce cas-là c’est parfait, l’on passe alors à l’exemple suivant (cf : Illustration ci-dessous).
Le second cas est le cas la réponse du classifieur est incorrect, dans ce cas l’algorithme d’entrainement répare le classifieur afin qu’il sorte la bonne réponse et l’on peut alors passer à l’exemple suivant (cf : Illustration ci-dessous).
Après cette phase dite d’entraînement du classifieur, vient alors une phase de test. Durant cette phase, des exemples qui n’ont jamais été vus par le classifieur durant son entraînement lui sont soumis.
Si les réponses du classifieur sont correctes, l’on considère qu’il a été bien entrainé, à l’inverse si elles sont incorrectes le classifieur est mal entrainé et il est alors important d’en trouver la cause.
Maintenant que nous avons vu tout le stuff nécessaire à la création de l'I.A, nous allons enfin pouvoirs passer à l'implémentation du morpion.
Installation des bibliothèques nécessaires
Avant de passer à la création du morpion, nous allons d’abord
installer Scikit-Learn. Pour cela il faut ouvrir le Shell Windows et taper.
pip install scikit-learn
Elle présente de nombreux avantages :
-c’est une bibliothèque très diversifiée.
Les algorithmes de
machine learning les plus populaires (arbre de décision, SVM, réseau de neurones, etc...) y
sont implémentés dans des versions optimisées.
-elle dispose d’une documentation très claire et concise illustrée par de nombreux exemples de codes Python.
-elle a pour but d’être une bibliothèque très ludique et accessible à tous, ce qui explique sa popularité.
Je qualifierais donc
Scikit-Learn de bibliothèque permettant à n'importe quel développeur lambda de devenir un vrai expert en
machine learning sans pour autant qu'il n'ait besoin d'un background poussé sur cette discipline.
Importation des bibliothèques nécessaires
Dans un premier temps, il faut importer les bibliothèques et fonctions dont Python aura besoin pour la création du morpion et de l’I.A :
Pour ce faire, nous importerons le module
MLPClassifier qui permet de créer un réseau de neurones de type
perceptron multi-couches
Le module RandomForestClassifier qui permet de créer une forêt aléatoire d'arbres de décision.
#Permet de copier n'importe quel objet
import copy
#Importation d'un perceptron Multi-Couche
from sklearn.neural_network import MLPClassifier
import numpy as np
#Génère des nombres aléatoires
import random
#Importation des fonctions de prétraitement des données
from sklearn import preprocessing
#Importation d'une forêt d'arbre décisionnels
from sklearn.ensemble import RandomForestClassifier
#Importation des arbres de décisions
from sklearn import tree
Une fois toutes les bibliothèques importées, nous créons une classe morpion.
Dans cette classe il y aura une fonction init qui initialisera l’ensemble des paramètres du jeu.
Une fonction jeu qui contiendra la boucle principale du jeu.
Une fonction afficher plateau qui permettra d’afficher le plateau de jeu.
Une fonction jouer qui permettra au joueur courant de choisir puis de jouer son mouvement.
class Morpion:
#Permet d'initialiser le jeu
def __init__(self):
#Contient le code qui assure le bon déroulement du jeu en lui même
def jeu(self):
#Affiche le plateau de jeu
def afficher_plateau(self):
#Test si il y a un vainqueur où si il n'y a plus de mouvement possible
def test_fin_jeu(self,joueur):
#Permet à un joueur de jouer son tour
def jouer(self, joueur):
Dans la fonction __init__, le plateau de jeu est initialisé avec des “-”, le joueur 1 est initialisé avec une croix et le joueur 2 est initialisé avec un rond.
Cela signifie que partout sur le plateau ou il y a des tirets il n’y a personne qui a joué.
Partout ou il y a des croix cela signifie que le joueur 1 a joué.
Enfin, partout où il y a des ronds, cela signifie que le joueur 2 a joué.
#Permet d'initialiser le jeu
def __init__(self):
#Création et initialisation du plateau de jeu
self.plateau=[['-','-','-'],['-','-','-'],['-','-','-']]
#Déclaration du premier Joueur
self.J1='X'
#Déclaration du second Joueur
self.J2='O'
La fonction jouer, commence par lire au clavier l’abscisse puis l’ordonnée de la position ou le joueur courant souhaite jouer.
Le signe du joueur courant est par la suite écrit sur le plateau à la position précédemment indiquée.
#Permet à un joueur de jouer son tour
def jouer(self, joueur):
#Demande les coordonnées où le joueur souhaite jouer
x = input("Entrez l'abscisse compris entre 1 et 3 : ")
y = input("Entrez l'ordonnée compris entre 1 et 3 : ")
#Affectation de la marque du joueur à la position x et y du plateau
self.plateau[int(x)][int(y)]=joueur
La fonction afficher_plateau parcourt le plateau et l’affiche en veillant à bien séparer chaque signe par deux barre “|”.
#Affiche le plateau de jeu
def afficher_plateau(self):
for i in range (0, 3):
for j in range (0, 3):
print ("|", end="")
print (self.plateau[i][j], end="")
print ("|")
print ("-----------------------------------------")
Test_fin_jeu va vérifier si l’un des deux joueurs a gagné ou s’il n’y a pas égalité.
Pour cela elle va vérifier qu’il n’y a pas 3 fois le même signe aligné ni en horizontal, ni en vertical, ni en diagonal.
Elle va également qu'il reste de la place pour jouer en vérifiant qu’il reste des signes “-” sur le plateau.
#Test si il y a un vainqueur où si il y a plus de mouvement possible
def test_fin_jeu(self,joueur):
#vérifie le joueur courant n'a pas aligné son signe sur une ligne
for i in range (0,3):
compteur=0
for j in range (0,3):
if self.plateau[i][j]==joueur:
compteur+=1
#Si il a aligné son signe 3 fois en horizontal
if compteur==3:
#le joueur est déclaré vainqueur et donc retourné par la fonction
return joueur
#vérifie le joueur courant n'a pas aligné son signe sur une colonne
for i in range (0,3):
compteur=0
for j in range (0,3):
if self.plateau[j][i]==joueur:
compteur+=1
#Si il a aligné son signe 3 fois en vertical
if compteur==3:
#le joueur est déclaré vainqueur et donc retourné par la fonction
return joueur
# Test de diagonales 1
compteur=0
for i in range (0,3):
if self.plateau[i][i]==joueur:
compteur+=1
if compteur==3:
#le joueur est déclaré vainqueur et donc retourné par la fonction
return joueur
compteur=0
# Test de diagonales 2
for i in range (0,3):
if self.plateau[2-i][i]==joueur:
compteur+=1
if compteur==3:
#le joueur est déclaré vainqueur et donc retourné par la fonction
return joueur
#vérifie qu'il reste de la place sur le plateau en comptant les signes de tout les joueurs
compteur=0
for i in range (0,3):
for j in range (0,3):
if( self.plateau[i][j]!='-'):
compteur+=1
#Si il n'y a plus de place sur le plateau
if compteur==8:
# On retourne vrai pour dire que le jeu est fini
return True
#Le jeu n'est pas encore fini on retourne false
return False
Enfin pour finir, la fonction jeu, va utiliser lancer le game en affichant premièrement le tableau, puis en appelant les fonctions que j’ai montrées plus haut.
Tant que l'un des deux joueurs n’aura pas gagné, elle va les faire jouer chacun leur tour, puis afficher le nouveau plateau et tester que le jeu n’est pas fini.
S’il est fini on sort de la fonction en revoyant le signe du joueur gagnant ou en renvoyant égalité si c’est une égalité.
#Contient le code qui assure le bon déroulement du jeu en lui même
def jeu(self):
morpion.afficher_plateau()
bool_fin_jeu=False
#Tant que le jeu n'est pas fini
while bool_fin_jeu==False:
#Le joueur 1 joue
morpion.jouer(self.J1)
morpion.afficher_plateau()
#Test de victoire de J1
resultat_test_fin_jeu=self.test_fin_jeu(self.J1)
#Si J1 à gagné
if( resultat_test_fin_jeu==self.J1):
#Affiche Joueur 1 à gagné
print ("Joueur " + self.J1 +" a gagné" );
return self.J1
elif ( resultat_test_fin_jeu==True):
#Affiche Égalité entre les joueurs
print ("Égalité entre les joueurs" );
return "égalité"
#Le joueur 2 joue
morpion.jouer(self.J2)
morpion.afficher_plateau()
resultat_test_fin_jeu=self.test_fin_jeu(self.J2)
#Test de victoire de J2
if( resultat_test_fin_jeu!=False):
print ("Joueur " + self.J2 +" a gagné" );
return self.J2
elif ( resultat_test_fin_jeu==True):
print ("Égalité entre les joueurs" );
return "égalité"
Voili voilou ! ;-D maintenant que le morpion est prêt nous pouvons enfin créer l’IA qui s’amusera à apprendre à jouer et qui deviendra un bon joueur à la fin.
Comment créer un simple IA qui apprend d'elle même à jouer au morpion
Pour ce faire, nous allons modifier la fonction d’initialisation de la classe morpion et rajouter sept nouvelles fonctions, ai_jeu, convert_plateau, train_ai_jeu,générateur_de_mouvement,train_ai_player, entraineur_ai_joue et ai_player_joue,
Tu devrais donc obtenir le schéma de classe ci-dessous :
class Morpion:
#Permet d'initialiser le jeu
def __init__(self):
#Fonction de réinitialisation du tableau
def intialiser_plateau(self):
self.plateau=[['-','-','-'],['-','-','-'],['-','-','-']]
#Fonction de jeu qui fera jouer l'ia pour l'entraîner
def ai_jeu(self,i):
#Fonction qui convertira le plateau de signe en plateau de données numériques compréhensibles pour un réseau de neurones
def convert_plateau(self,plateau):
#Fonction d'entraînement par renforcement de l'ia, elle fera l'ia jouer de nombreuses fois contre un joueur
# dont les mouvements seront aléatoire
def train_ai_jeu(self):
#Contient le code qui assure le bon déroulement du jeu en lui même
def jeu(self):
#Renvoie l'ensemble des mouvements possibles pour le joueur passé en paramètre
def generateur_de_mouvement(self,joueur):
#Fonction qui entraîne l'ia sur les parties passées
def train_ai_player(self):
#Fonction permet à l'adversaire de l'ia de jouer son tour
def entraineur_ai_joue(self,list_mvt_possible):
#Permet à l'ia de jouer son tour
def ai_player_joue(self,joueur,list_mvt_possible):
#Affiche le plateau de jeu
def afficher_plateau(self):
#Test si il y a un vainqueur où si il y a plus de mouvement possible
def test_fin_jeu(self,joueur):
#Permet à un joueur de jouer son tour
def jouer(self, joueur):
Dans la fonction init, trois variables ont été rajoutées.
Les premières sont self.base_de_jeu et self.base_resultat_jeu qui contiendront respectivement l’ensemble des parties passées et leurs résultats.
Conserver ces données nous permettra d’entraîner l’algorithme de classification que nous avons choisi.
Il y a ensuite self.clf, il s’agit du classifieur qui nous permettra de générer l’intelligence artificielle du morpion. Bien que j’aurais pu choisir un réseau de neurones, j’ai choisi un arbre de décision, car il est plus facile à configurer et plus efficace sur ce problème.
#Permet d'initialiser le jeu
def __init__(self):
#Création et initialisation du plateau de jeu
self.plateau=[['-','-','-'],['-','-','-'],['-','-','-']]
#Déclaration du premier Joueur
self.J1='X'
#Déclaration du second Joueur
self.J2='O'
#Création d'une base d'observations qui contiendra l'historique des parties jouées
self.base_de_jeu=[]
#Création d'une base de résultats contiendra l'historique des résultats des parties jouées
self.base_resultat_jeu=[]
#Création d'un classifieur de type Arbre de décision
#self.clf = tree.DecisionTreeClassifier()
#Création d'un classifieur de type réseau de neurones
self.clf = MLPClassifier(solver='lbfgs', alpha=1e-5,hidden_layer_sizes=(6, 2), random_state=1)
#Création d'un classifieur de type RandomForest
#self.clf = RandomForestClassifier(n_estimators=50, max_depth=2,random_state=0)
La fonction initialiser_plateau, nous permettra de réinitialiser le plateau à chaque fin de partie.
#Fonction de réinitialisation du tableau
def intialiser_plateau(self):
self.plateau=[['-','-','-'],['-','-','-'],['-','-','-']]
Le code de la fonction train_ai_jeu fait jouer l’IA 10 fois 10000 partie contre l’entraîneur, et à l’issue de chacune des 10000 parties, le score de chacun des joueurs est affiché et le comportement de l’IA est actualisé.
#Fonction d'entraînement par renforcement de l'ia, elle fera l'ia jouer de nombreuse fois contre un joueur aléatoire
def train_ai_jeu(self):
#L'IA va jouer 10 fois 10000 jeu pour apprendre
for i in range (0, 10):
victoire_j1=0
victoire_ia=0
egalite=0
# Pour j allant de zéro à 10000
for j in range (0,10000):
#IA joue une partie
sauvegarde_plateaux, result = self.ai_jeu(i)
#Si la fonction ai_jeu a renvoyé que j1 est vainqueur
if (result==self.J1):
#Son nombre de victoire est incrémenté
victoire_j1+=1
#sinon si elle a renvoyé que J2 est vainqueur
elif (result==self.J2):
#le nombre de victoire de l'ia est incrémenté
victoire_ia+=1
else :
#sinon le nombre d'égalité est incrémenté
egalite+=1
#Pour tout les plateau de la dernière partie jouée
for k in range (0,len(sauvegarde_plateaux)):
#La plateau sous forme de matrice de 3 x 3 est passé en vecteur de taille 9
sauvegarde_plateaux[k]=np.array(sauvegarde_plateaux[k]).reshape(-1)
#l'ensemble des données alphabétiques son convertie en données numériques
sauvegarde_plateaux[k]=self.convert_plateau(sauvegarde_plateaux[k])
sauvegarde_plateaux[k]=sauvegarde_plateaux[k].astype(np.float64)
#Si J1 0 gagné
if( result ==self.J1):
#Ajouts des plateau a la base d'observations
self.base_de_jeu.append(sauvegarde_plateaux[k])
#Ajout de 0 à la base de résultat pour dire que J1 à gagné sur ce plateau
self.base_resultat_jeu.append(0)
#Si l'IA a gagné 0
elif ( result ==self.J2):
#Ajouts des plateau a la base d'observations
self.base_de_jeu.append(sauvegarde_plateaux[k])
#Ajout de 1 à la base de résultat pour dire que J1 à gagné sur ce plateau
self.base_resultat_jeu.append(1)
#Affichage des victoires après 10000 partie
print ("Itération = ", i , " victoire J1 = ",victoire_j1, "victoire IA = ",victoire_ia, "egalite = ",egalite)
#Actualisation de l'intelligence de l'ia
self.train_ai_player()
La fonction generateur_de_mouvement, va retourner tous les mouvements possibles pour le joueur passé en paramètre. Pour cela, elle va tester chaque case du plateau afin de savoir si elle est vide.
#Renvoie l'ensemble des mouvements possibles pour le joueur passé en paramètre
def generateur_de_mouvement(self,joueur):
#Déclaration d'une liste qui contiendra tout les mvts possible
liste_mouvement_possible=[]
#Pour tout les cases du plateau
for i in range (0, 3):
for j in range (0, 3):
#Si la case courante est vide
if (self.plateau[i][j]=="-"):
#Création d'un mouvement virtuel et ajout de celui-ci a la liste des mouvements possibles
virtual_plateau=copy.deepcopy(self.plateau)
virtual_plateau[i][j]=joueur
liste_mouvement_possible.append(virtual_plateau)
return liste_mouvement_possible
La fonction update_ai_player, va actualiser le comportement de l’IA, tous simplement en entraînant le classifieur choisi clf via la fonction fit sur l’ensemble des parties qui ont été jouées depuis le début.
#Fonction qui entraîne l'ia sur les parties passées
def train_ai_player(self):
# Normalisation des données (absolument nécessaire pour un réseau de neurones)
self.scaler = preprocessing.StandardScaler().fit(self.base_de_jeu)
X_train=self.scaler.transform(self.base_de_jeu)
#Entrainement du classifieur chargé de choisir les coups de l'IA
self.clf.fit ( X_train,self.base_resultat_jeu)
L’entraineur de l’IA va choisir aléatoirement un mouvement parmi tous les mouvements possibles et le jouer.
#Fonction permet à l'adversaire de l'ia de jouer son tour
def entraineur_ai_joue(self,list_mvt_possible):
#Selon la liste des mouvements possibles un mouvement aléatoire est joué
if( len(list_mvt_possible)>1):
indice_mvt=random.randint(0,len(list_mvt_possible)-1)
self.plateau=list_mvt_possible[indice_mvt]
else :
self.plateau=list_mvt_possible[0]
Enfin, c’est au tour de l’IA de jouer.
Pour ce faire, elle va d’abord évaluer l’ensemble des mouvements possible via la fonction predict_proba qui prédira la probabilité que l’IA gagne pour chaque mouvement.
Le mouvement obtenant la plus grande probabilité de victoire est alors joué.
#Permet à l'ia de jouer son tour
def ai_player_joue(self,joueur,list_mvt_possible):
#Copie des mouvement possibles
list_mvt_possible_copy=copy.deepcopy(list_mvt_possible)
# Conversion de la copie des mouvement possibles en données numériques
for i in range (0,len(list_mvt_possible_copy)):
list_mvt_possible_copy[i]=self.convert_plateau(np.array(list_mvt_possible_copy[i]).reshape(-1)).astype(np.float64)
#Normalisation des données des plateaux numériques
X_test=self.scaler.transform(list_mvt_possible_copy)
#L'IA calcul de la probabilité de gagner selon chacun des mouvement possible
proba_success_mvt=self.clf.predict_proba(X_test)
indice_mvt=0
#Pour tout les probabilités de gagner des mouvements possible, on choisi la plus grande
for i in range (0, len(proba_success_mvt)):
if(proba_success_mvt[indice_mvt][1]<proba_success_mvt[i][1]):
indice_mvt=i
self.plateau=list_mvt_possible[indice_mvt]
Pour finir, pour tester, l’ensemble du code il suffit de créer une instance de la classe morpion et d’appeler train_ai_jeu pour que l’IA se mette à apprendre d’elle même.
morpion=Morpion()
morpion.train_ai_jeu()
Résultat :
Arbre de décision :
En utilisant le RandomForest où encore le perceptron multicouche les scores obtenus comme on peut le constater dans les images ci-dessous sont bien moins intéressants. Le modèle le plus adapté à ce problème est donc l’arbre de décision.
RandomForest
Perceptron multi-couche
