Dans ce cours, nous allons voir quelque chose d'assez intéressant, comme tout ce qui touche l'intelligence artificielle d'ailleurs. Nous allons aborder le sujet des MRM, c'est à dire Mind Reading Machine. Mind Reading Maching vient de l'anglais "Machine permettant de lire l'esprit" et est un domaine de l'intelligence artificielle où le but est d'essayer de savoir ce qui se passe dans le cerveau humain. Bien entendu, la complexité de ce dernier ne permettra probablement jamais de faire cela à la perfection, mais il y a cependant des facettes de raisonnement qui peuvent permettre l'établissement de certaines lois et règles permettant d'approcher la pensée humaine. Ici, nous allons modéliser ce que nous voulons expliquer par la programmation d'un jeu très simple : le pierre/papier/ciseaux. Sans intelligence artificielle, ca ne serait pas un programme très compliqué à faire. Il suffirait de faire un programme qui choisit aléatoirement entre pierre, papier ou ciseau et qui joue le coup. Dans un tel programme, cela serait purement aléatoire et il n'y aurait aucune intelligence artificielle. Ici, nous n'allons pas utiliser cette technique, mais l'algorithme de Minasi. Il existe plusieurs algorithmes différents pour "lire la pensée humaine", mais ici, nous allons commencer par le plus simple. Son principe est assez facile. La machine commencera la partie en étant idiote et plus des parties seront jouées, plus celle-ci apprendra et essayera d'interprêter la pensée humaine. L'algorithme de Minasi se base sur le fait que dans des jeux tels que pierre/papier/ciseaux, notre esprit va inconsciement faire des séquences. Effectivement, quand nous jouons aléatoirement des coups à ce jeu, il en résulte que sans le vouloir nous jouons des séquences de coup qui ont un certain pourcentage de chance de revenir. L'algorithme va donc se baser sur ce principe et analyser les coups précédent pour essayer de prévoir le prochain coup. Avant de passer à un exemple en programmation, nous allons voir le principe en simulant une partie. Nous allons utiliser 3 symboles : P pour papier (Paper), R pour pierre (Rock) et S pour ciseaux (Scissors). Nous représenterons ces coups en minuscule lorsque c'est le joueur qui effectue le coup et en majuscule lorsque c'est notre algorithme. Pour être certain que l'algorithme ne "triche pas", nous allons faire jouer l'algorithme avant le joueur, ainsi l'algorithme ne pourra pas simplement choisir le meilleur choix face à celui du joueur. Ici, nous allons partir d'une suite de coup déjà existante. Le principe de l'algorithme au démarrage sera expliqué ensuite. Imaginez que jusqu'à présent, la suite ressemble à celle-ci : R r S r P s S s P s R p P p R s R r S p S s P s S r R p P s R p P s S s P s L'algorithme va partir de la fin de cette combinaison de coup et va remonter jusqu'à ce qu'il trouve le meilleur coup jouable. La première chose qu'il va faire, c'est prendre le dernier coup joué par l'utilisateur, à savoir s : R r S r P s S s P s R p P p R s R r S p S s P s S r R p P s R p P s S s P <span style="color:red;">s</span> Il va ensuite rechercher cette séquence dans la combinaison d'avant : R r S r P <span style="color:green;">s</span> S <span style="color:green;">s</span> P <span style="color:green">s</span> R p P p R <span style="color:green;">s</span> R r S p S <span style="color:green;">s</span> P <span style="color:green;">s</span> S r R p P <span style="color:green;">s</span> R p P <span style="color:green;">s</span> S <span style="color:green;">s</span> P <span style="color:green;">s</span> Comme vous pouvez le voir, l'algorithme a détecté que le joueur a choisis 10 fois le coups s. L'algorithme va alors faire un récapitulatif des coup choisis par l'utilisateur après le coup s, au final cela donnera ce résultat : r : 2 fois s : 5 fois p : 2 fois Selon ces chiffres, l'algorithme pourrait en conclure que le prochain coup joué par le joueur sera certainement s, mais cette précision n'est tout simplement pas acceptable et l'algorithme n'a aucune raison de s'arrêter maintenant, il va donc maintenant rechercher la séquence contenant le dernier coup de l'utilisateur et le dernier coup de l'algorithme : R r S r <span style="color:green;">P s</span> S s <span style="color:green;">P s</span> R p P p R s R r S p S s <span style="color:green">P s</span> S r R p <span style="color:green">P s</span> R p <span style="color:green">P s</span> S s <span style="color:red;">P s</span> Comme vous le voyez, la précision augmente déjà étant donné que cette séquence ne s'est repetée que 5 fois. L'algorithme va encore une fois faire le compte des coups joués par l'utilisateur après ces séquences : r : 1 fois s : 2 fois p : 2 fois Comme vous le voyez, selon cette séquence, l'algorithme ne peut maintenant plus prédire avec autant de certitude que l'utilisateur jouera certainement s. Il peut conclure qu'il y a peu de chance qu'il joue r, mais qu'il y a autant de chance qu'il joue s ou p. N'ayant pas encore de résultat définitif, l'algorithme va continuer avec les 3 derniers coups : R r S r P s S <span style="color:green;">s P s</span> R p P p R s R r S p S <span style="color:green;">s P s</span> S r R p P s R p P s S <span style="color:red;">s P s</span> Il apparait maintenant que la séquence est retrouvée 2 fois dans la combinaison, mais les statistiques deviennent : r : 1 fois s : 0 fois p : 1 fois Comme vous le voyez, aussi étonnant que cela puisse paraître, l'algorithme ne détecte plus de séquence suivie par le coup s. Voilà donc bien l'utilité de parcourir la plus longue séquence de coups possibles plutot que seul le dernier coup. Effectivement, avec juste le dernier coup, l'algorithme aurait supposé que le prochain coup de l'utilisateur serait s, alors que lorsqu'il se base sur une séquence de 3 coups, il apparaît clairement que le prochain coup de l'utilisateur a très peu de chance d'être s. Etant donné que des résultats sont encore possibles avec 3 coups, l'algorithme va continuer avec 4 : R r S r P s <span style="color:green">S s P s</span> R p P p R s R r S p <span style="color:green;">S s P s</span> S r R p P s R p P s <span stlye="color:red;">S s P s</span> Ici, la séquence est encore retrouvée deux fois et les statistiques restent les même : r : 1 fois s : 0 fois p : 1 fois L'algorithme va donc continuer son chemin : R r S r P <span style="color:green;">s S s P s</span> R p P p R s R r S p S s P s S r R p P s R p P <span style="color:red;">s S s P s</span> Comme vous voyez, l'algorithme ne retrouve maintenant plus qu'une seule séquence correspondant à celle recherchée. Les statistiques deviennent donc : r : 0 fois s : 0 fois p : 1 fois Ainsi, l'algorithme va donc "penser" que l'utilisateur a toute les raisons de choisir p (donc papier) comme prochain coup, l'algorithme choisira donc s (donc ciseaux) comme prochain coup. Ici, il est évident que pour être efficace, l'algorithme devra connaitre les règles du jeu et savoir quel coup l'emporte face à quel coup. Bien que cet algorithme soit assez basique ces résultats ne sont pas mauvais du tout. D'après une série de 10 parties composées de 500 coups chacune, entre l'algorithme et un humain, le pourcentage de victoire est de 56% en faveur de l'algorithme.

Programmation

Nous allons maintenant voir comment implémenter cet algorithme en C#. Il existe plusieurs façons de le faire et il est possible que celle que nous allons exposer ne soit pas la plus performante, mais ici, ce n'est pas tant la rapidité que l'efficacité de l'algorithme qui compte. Nous n'allons pas décrire en profondeur les étapes nécessaires à la réalisation de l'interface graphique de ce code, nous n'expliquerons pas non plus les différentes instructions du programme de façon technique. Effectivement, des cours sur le C# existent sur ce site, nous nous contenterons dans ce cours d'expliquer l'utilité des lignes de code. Voici à quoi ressemblera notre jeu : Comme vous le voyez, cette architecture est très basique. La première chose que nous allons faire est déclarer quelques variables de classe :

private string pattern = "";
private List<string> coupGagnant = new List<string> { "Rp", "Ps", "Sr" };
private List<string> coupDraw = new List<string> { "Rr", "Pp", "Ss" };

private int scoreJoueur = 0;
private int scoreMinasi = 0; 

La variable pattern ici va nous permettre de contenir la combinaison des coups joués. Nous avons ensuite deux tableaux qui vont nous permettre de définir les règles du jeu, donc la priorité des coups. Nous faisons donc un tableau contenant les coups gagnant et un nombre contenant les coup nuls. La première liste contiendra les coups gagnant pour l'utilisateur et non pour la machine. Le principe sera donc de regarder les deux derniers coups joués, de voir dans quel tableau ils se trouvent et d'en définir le gagnant, nous verrons cela un peu plus loin. Nous avons ensuite deux variables qui permettront simplement de contenir le score des deux joueurs. Doublez cliquez maintenant sur le bouton Pierre et tapez :

jouer("r"); 

Pour le bouton Papier, tapez :

jouer("p"); 

Et pour le bouton Ciseaux :

jouer("s"); 

La fonction jouer est une fonction personnelle qui va nous permettre de jouer notre coup, d'attendre le coup de l'algorithme, de comparer les deux et d'attribuer les points en conséquence. Voici comment l'implémenter :

private void jouer(string joueur)
{
	pattern += joueur;

	string minasi = getNextHit();

	string dernierCoup = pattern.Substring(pattern.Length - 2);

	if (coupDraw.IndexOf(dernierCoup) >= 0)
	{
		scoreJoueur++;
		scoreMinasi++;
	}
	else if (coupGagnant.IndexOf(dernierCoup) >= 0)
		scoreJoueur++;
	else
		scoreMinasi++;

	pattern += minasi;

	lblScoreMinasi.Text = scoreMinasi.ToString();
	lblScoreJoueur.Text = scoreJoueur.ToString();
} 

Le code de cette fonction n'est pas très compliqué. La première ligne permet simplement d'ajouter le coup de l'utilisateur à la liste des coups déjà joués. Nous récupérons ensuite dans la variable minasi le résultat de la fonction getNextHit. Cette fonction permet d'utiliser l'algorithme et renvoie le coup déterminé par ce dernier. Nous récupérons ensuite les deux derniers coups joués dans la variable dernierCoup. Le premier if va vérifier si ce coups se trouvent dans la liste des coups nuls, si c'est le cas, nous incrémentons les deux scores. Par contre, si ces deux coups se trouvent dans la liste des coups gagnant, nous n'incrémentons que le score du joueur. Si les coups ne se trouvent dans aucune des deux listes, nous incrémentons juste le score de l'algorithme. Nous ajoutons ensuite le coup joué par l'algorithme à la suite de la combinaison et enfin nous modifons la valeur des labels contenant les scores. Avant de passer à l'implémentation de l'algorithme, rendez-vous dans le constructeur de la form et tapez :

pattern += getNextHit(); 

Cela permet à l'algorithme de jouer le premier coup de la partie. Voyons maintenant l'implémentation de la fonction getNextHit. La signature de celle-ci sera simplement :

private string getNextHit()
{

} 

Comme vous le voyez, cette fonction va renvoyer un string correspond au coup choisi par l'algorithme. Commencez l'implémentation de cette fonction avec la déclaration de 4 variables :

Random r = new Random();

int pierre = 0;
int ciseaux = 0;
int papier = 0; 

Le premier objet va simplement permettre (plus tard) de générer un nombre aléatoire quand l'algorithme hésitera. Les 3 variables suivantes sont celles qui vont permettre de faire les statistiques des coups joués après la séquence couramment analysée. Faites ensuite cette boucle :

for (int i = pattern.Length - 1; i >= 0; --i)
{

} 

Cette boucle va permettre de remonter la liste des combinaisons depuis la fin jusqu'au début afin de rechercher les séquences. Dans cette boucle, déclarez ces 3 objets :

string sequenceAChercher = pattern.Substring(i);
string chaineAnalysee = pattern.Substring(0, i);

List<string> lstOccurence = new List<string>(); 

La variable sequenceAChercher va contenir la sous-chaine de la combinaison depuis la valeur de i à la fin de cette chaine. Etant donné que i démarre avant le dernier caractère de la combinaison et va, au maximum, jusqu'au début de celle-ci, vous aurez facilement compris que cette variable va contenir la séquence de coup à rechercher dans la combinaison. Cette chaine ne devra être recherchée que dans la partie de la combinaison se trouvant avant cette séquence en question, nous plaçons donc cette partie de la combinaison dans la variable chaineAnalysee. Enfin, nous créons une liste qui va permettre de retenir les différents coups joués après la séquence recherchée dans la combinaison. Tapez ensuite :

for (int x = 0; x < pattern.Length - sequenceAChercher.Length; ++x)
	if (pattern.Substring(x, sequenceAChercher.Length) == sequenceAChercher)
		lstOccurence.Add(pattern.Substring(x + sequenceAChercher.Length, 2)); 

Cette boucle va nous permettre de parcourir toute la chaine dans laquelle nous devons rechercher les séquences. Si jamais cette séquence est trouvée, nous ajoutons les deux coups suivants dans la liste. Tapez ensuite :

string[] occurence = lstOccurence.ToArray();

if (occurence.Length == 0)
	break;

papier = 0;
pierre = 0;
ciseaux = 0; 

Pour plus de facilité, nous convertissons la liste remplie précédemment en un tableau de string nommé occurence. Si ce tableau est vide, cela signifie que la séquence n'a pas été trouvé dans la sous-chaine, nous sortons donc de la boucle for. Si ce n'est pas le cas, nous mettons les statistiques à 0. Tapez ensuite cette boucle :

for (int x = 0; x < occurence.Length; ++x)
{
	if (occurence[x][1] == 'p')
		papier++;
	else if (occurence[x][1] == 'r')
		pierre++;
	else ciseaux++;
}

Ici, cette boucle est assez simple. Elle va parcourir l'ensemble des coups joués et elle va analyser le deuxième caractère de ces coups car celui-ci correspond à celui joué par l'utilisateur. Selon ce coup, cette boucle va incrémenter la variable correspondant au coup. Dans l'ensemble, la boucle for (celle se basant sur la variable i) est assez simple. Elle va remonter dans la combinaison et rechercher les séquences de coups. Au fur et à mesure, cette boucle va remettre les statistiques à 0 et les mettre à jour selon la séquence analysée. La boucle va bien veiller à se terminer si la séquence n'a pas été trouvée. Effectivement, si la boucle ne se terminait pas prématurément dans ce cas, les statistiques seraient remises à 0. Tapez ensuite ceci :

List<string> possibilite = new List<string> { "P", "R", "S" };

if (pierre == 0 && papier == 0 && ciseaux == 0)
	return possibilite[r.Next(0, 2)];

int max = Math.Max(pierre, Math.Max(papier, ciseaux));

if (pierre != max)
	possibilite.RemoveAt(possibilite.IndexOf("P"));

if (ciseaux != max)
	possibilite.RemoveAt(possibilite.IndexOf("R"));

if (papier != max)
	possibilite.RemoveAt(possibilite.IndexOf("S"));

return possibilite[r.Next(0, possibilite.Count - 1)]; 

Ici, c'est assez simple encore une fois. La liste va simplement contenir la liste des coups que l'algorithme a actuellement la possibilité de jouer. Si les trois variables contiennent 0 (dans le cas du premier coup par exemple), l'algorithme va générer un nombre entre 0 et 2 et renvoyer le coup correspondant à cet index de la liste. Ici, c'est donc le cas où l'algorithme n'a pas pu déterminer un coup valable, généralement c'est lors du premier coup. Ensuite, nous déterminons la valeur la plus grande de celles contenues dans les 3 variables pour connaitre la plus grande possibilité qu'un certain coup soit joué. Les 3 conditions suivantes sont assez similaires. La première regarde si la probabilité contenue dans la variable pierre est différente de la plus grande probabilité récéupérée précédemment. Si elle est bien différente, cela veut dire que ce n'est pas le coup pierre qui a le plus de chance d'être joué par l'utilisateur. Nous supprimons donc la valeur P de la liste des coups envisageables par l'algorithme. Le coup pierre (R) ne peut être battu que par papier (P), c'est donc pour cela que nous enlevons P de la liste. Les deux conditions suivantes font pareils mais avec les deux autres coups. Ensuite, nous générons un nombre aléatoire qui va nous permettre de sélectionner un coup dans la liste des coups possibles pour l'algorithme. Nous générons un nombre aléatoire car il peut arriver que deux coups aient la même probabilité d'être joué par l'utilisateur, l'algorithme devra alors choisir un coup aléatoirement. Et voilà, notre petit programme est terminé, testez le, vous verrez, si vous avez le dessus dans les premiers coups, vous vous ferez vite dépasser par l'algorithme ;-)