Etude préliminaire
Tout d’abord le TIC TAC TOE c’est quoi ? (merci Wikipedia)
Le Tic-tac-toe est un jeu de réflexion se pratiquant à deux joueurs au tour par tour et dont le but est de créer le premier un alignement. Il se joue sur une grille carrée de 3x3 cases contrairement au Morpion avec lequel il est souvent confondu et qui se joue sur des grille de 5x5 cases. Deux joueurs s’affrontent et doivent remplir chacun à leur tour une case de la grille avec le symbole qui leur est attribué. Le gagnant est celui qui arrive à aligner trois symboles identiques, horizontalement, verticalement ou en diagonale.
En raison du nombre de combinaisons limité, l’analyse complète du jeu est facile à réaliser, et c’est ce qui va nous intéresser ici. Tout comme le PONG, le code du jeu est très simple, mais il fait appel à une ébauche d’intelligence artificielle pour jouer contre un ordinateur. C’est le point important que nous allons développer aujourd’hui.
Je n’ai pas pensé à le dire lors des précédents exercices, mais le but du jeu est qu’à partir de l’étude préliminaire vous essayiez vous même de résoudre le problème avant de lire l’exercice. J’ai en effet utilisé ma propre méthode, mais votre approche de la chose est tout aussi importante que la lecture de l’exercice, comparer votre résultat et le mien vous donnera bien plus d’informations que de lire simplement la solution, de plus vous pourriez trouver une autre approche sans doute plus light et optimisée et donc me corriger dans la foulée ;-)
Les pré-requis
Je vous recommande fortement d’avoir au moins lu les exercices suivants : PONG, SNAKE, TAQUIN
Les exercices sont courts mais de nombreuses astuces y sont proposées, je ne les expliquerai pas à chaque nouvel exercice.
Pour ce programme vous devez connaître :
Variables et types : http://help.adobe.com/fr_FR/FlashPl...
Fonctions et paramètres : http://help.adobe.com/fr_FR/FlashPl...
Manipulation de tableaux : http://help.adobe.com/fr_FR/FlashPl...
Ecouteurs d’événements : http://help.adobe.com/fr_FR/FlashPl...
Si vous souhaitez plus de précisions sur ces points, je vous encourage à parcourir le Wiki de Mediabox où vous trouverez de nombreux tutoriaux détaillés.
Le code
On se regarde tout ça d’un bloc avant de se lancer dans les explications.
// variables
var J:int = 1;
var T:int = 160;
var C:int = 3;
var P:int = 0;
// tableaux
var stock:Array = [];
var valid:Array = [];
var libre:Array = [];
// fond
var grille:Grille = new Grille();
var panneaux:Panneaux = new Panneaux();
addChild(panneaux);
panneaux.addEventListener(MouseEvent.CLICK, init);
panneaux.buttonMode = true;
// initialisation du jeu
function init(e:MouseEvent):void{
J=1;
while(numChildren>0) removeChildAt(0);
grille.addEventListener(MouseEvent.CLICK, remplir);
grille.buttonMode = true;
addChild(grille);
stock = [0,0,0,0,0,0,0,0,0];
valid = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]];
libre = [0,1,2,3,4,5,6,7,8];
}
// quel joueur joue
function remplir(e:Event):void{
if(J==1 && stock[P=int(mouseX/T)+int(mouseY/T)*C]==0) {
remplirCase(new TileO());
latenceAI();
return;
}
if(J==2) remplirCase(new TileX());
}
// remplir la case du joueur
function remplirCase(b:Sprite):void{
b.x = int(P%C)*T;
b.y = int(P/C)*T;
b.mouseEnabled = false;
addChild(b);
stock[P] = J;
libre.splice(libre.indexOf(P),1);
checkGagne();
}
// vérifie si un joueur gagne
function checkGagne():void{
for each (var c:Array in valid){
var w:Boolean = true;
for each (var i:int in c) w = w && stock[i] == J;
if (w){
nettoyage(J+1);
return;
}
}
if (libre.length==0) {
nettoyage(4);
return;
}
J==1 ? J=2 : J=1;
}
function nettoyage(f:int):void{
grille.removeEventListener(MouseEvent.CLICK, remplir);
addChild(panneaux);
panneaux.gotoAndStop(f);
}
// temps de latence avant réponse de l'ordi
function latenceAI():void{
var timer:Timer = new Timer(500,1);
timer.addEventListener(TimerEvent.TIMER_COMPLETE, choisiCase);
timer.start();
}
// l'ordi choisi une case
function choisiCase(e:TimerEvent):void{
var tab:Array = stock.concat();
var i:String;
for (i in libre) if (verifieCase(tab,2,libre[i])) return;
for (i in libre) if (verifieCase(tab,1,libre[i])) return;
remplirOrdi(libre[int(Math.random()*libre.length)]);
}
// l'ordi vérifie si la case est gagnante
function verifieCase(tab:Array, id:int, b:int):Boolean{
tab[b] = id;
for each (var c:Array in valid){
var w:Boolean = true;
for each (var i:int in c) w = w && tab[i] == id;
if (w){
remplirOrdi(b);
return true;
}
}
tab[b] = 0;
return false;
}
// l'ordi joue son coup
function remplirOrdi(p:int):void{
P = p;
remplir(null);
}
Etude du programme
Comme à chaque exercice, j’utilise la bibliothèque de Flash pour stocker mes objets, c’est pratique et évite du code superflu pour ce que nous avons à étudier dans l’exercice. Si n’utilisez pas Flash sachez que je me sert de 2 clips simples, chacun représentant un signe pour un des joueurs, et un dernier pour afficher la grille de fond du jeu. Tous les clips sont exportés pour AS.
Si vous avez lu les pré-requis l’étude du programme ne vous posera pas de problème :
// variables
var J:int = 1;
var T:int = 160;
var C:int = 3;
var P:int = 0;
Je déclare les variables globales, vous noterez que j’ai volontairement utilisé des initiales pour les noms des variables les plus courantes, ceci permet de simplifier la lecture des formules. Pour information :
J = le joueur en cours
T = la largeur et hauteur d’une case
C = nombre de colonnes et de lignes de la grille
P = la pièce à jouer par le joueur en cours
// tableaux
var stock:Array = [];
var libre:Array = [];
var valid:Array = [];
Je vais avoir besoin de trois tableaux, le stock représente les cases de la grille, à chaque nouveau coup joué on modifiera la valeur de la case correspondante dans le stock. Libre représente les cases encore disponibles pour jouer un coup, je m’en sert surtout lorsque l’ordinateur doit jouer. Valid est le plus important pour cet exercice, il regroupe par tableaux les différentes combinaisons gagnantes, nous allons l’étudier plus en détail ci-dessous.
// fond
var grille:Grille = new Grille();
var panneaux:Panneaux = new Panneaux();
addChild(panneaux);
panneaux.addEventListener(MouseEvent.CLICK, init);
panneaux.buttonMode = true;
Je crée mes objets utiles dont la grille du fond et le panneau d’interface, je n’ajoute pour le moment que le panneau d’interface à la liste d’affichage et je lui passe un écouteur au clic pour démarrer la partie.
// initialisation du jeu
function init(e:MouseEvent):void{
J=1;
while(numChildren>0) removeChildAt(0);
grille.addEventListener(MouseEvent.CLICK, remplir);
grille.buttonMode = true;
addChild(grille);
stock = [0,0,0,0,0,0,0,0,0];
valid = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]];
libre = [0,1,2,3,4,5,6,7,8];
}
J’initialise le jeu en commençant par supprimer tout ce qui se trouve dans la liste d’affichage, cela nous servira aussi lorsqu’une partie est terminée et qu’on veut en relancer une autre. J’ajoute la grille que je rend interactive pour que le joueur puisse poser ses pièces, et enfin j’initialise les tableaux. Si vous voulez mieux comprendre l’utilisation de ces tableaux comparez les valeurs des tableaux de Valid avec les valeurs de Libre, il s’agit en fait des index dans la grille.
Prenons le premier sous tableau de Valid : [0,1,2]
L’index 0 du stock correspond à la première case de la première ligne de la grille
L’index 1 du stock correspond à la deuxième case de la première ligne de la grille
L’index 2 du stock correspond à la troisième case de la première ligne de la grille
Prenons le cinquième sous tableau de Valid : [1,4,7]
L’index 1 du stock correspond à la deuxième case de la première ligne de la grille
L’index 4 du stock correspond à la deuxième case de la deuxième ligne de la grille
L’index 7 du stock correspond à la deuxième case de la troisième ligne de la grille
Vous avez compris le principe ?
Chaque tableau est une combinaison d’index gagnante, soit trois cases alignées ou en diagonales.
En interrogeant ce tableau je sait si un joueur gagne ou peut gagner la partie.
// quel joueur joue
function remplir(e:Event):void{
if(J==1 && stock[P=int(mouseX/T)+int(mouseY/T)*C]==0) {
remplirCase(new TileO());
latenceAI();
return;
}
if(J==2) remplirCase(new TileX());
}
Ici je regarde quel est le joueur en cours, si c’est l’humain, je regarde la position de la souris dans la grille, si elle correspond à un index libre dans le stock je peux jouer la pièce, sinon je ne fais rien.
Notez l’écriture particulière pour la pièce :
[P=int(mouseX/T)+int(mouseY/T)*C]
Je dis à P qu’il prend la valeur de l’index renvoyé par la position de la souris au moment du clic. Puis je vérifie que cette valeur correspond à un index libre dans le stock. Affecter directement la valeur de P à cet endroit n’a aucune incidence, car tant que le joueur n’a pas posé une pièce l’ordinateur ne peut pas jouer, donc P prendra forcément la bonne valeur une fois que le joueur aura posé une pièce.
Quand le joueur peut poser une pièce, on rempli la case concernée avec un clip correspondant à son signe puis on indique à l’ordinateur qu’il peut jouer. Si c’est l’ordinateur qui pose une pièce on se contente de poser la pièce, inutile de prévenir le joueur qu’il peut jouer il le voit bien.
// remplir la case du joueur
function remplirCase(b:Sprite):void{
b.x = int(P%C)*T;
b.y = int(P/C)*T;
b.mouseEnabled = false;
addChild(b);
stock[P] = J;
libre.splice(libre.indexOf(P),1);
checkGagne();
}
Quelque chose de très classique, si vous avez fait l’exercice du Taquin la formule pour passer d’une liste à une grille 2D ne vous est pas inconnue, on va donc se concentrer sur ce qui est important, à savoir :
stock[P] = J;
libre.splice(libre.indexOf(P),1);
checkGagne();
Lorsqu’une pièce est jouée je modifie l’index correspondant dans le stock, il prend la valeur du joueur en cours (1 ou 2). Puis je vérifie si un des joueurs à gagné, puis je supprime de Libre l’emplacement que le joueur viens de remplir, et je vérifie si la pièce posée permet au joueur en cours de gagner la partie.
// vérifie si un joueur gagne
function checkGagne():void{
for each (var c:Array in valid){
var w:Boolean = true;
for each (var i:int in c) w = w && stock[i] == J;
if (w){
nettoyage(J+1);
return;
}
}
if (libre.length==0) {
nettoyage(4);
return;
}
J==1 ? J=2 : J=1;
}
Pour vérifier si un joueur gagne en posant une pièce je vais parcourir le tableau des combinaisons.
Pour chaque sous tableau je commence par indiquer que le joueur gagne par défaut.
Puis je parcours le sous tableau et c’est là que ça se corse un peu...
w = w && stock[i] == J;
Encore une autre méthode pour écrire une condition, on va la traduire :
"w" prend la valeur "vrai" si "w" est vrai et que la valeur de l’index trouvé dans le sous tableau correspond à la valeur du joueur dans le stock.
Autrement dit, je parcours toutes les combinaisons gagnantes et je vérifie si le joueur concerné a ses pièces qui s’inscrivent dans une de ces combinaisons, si c’est le cas le joueur gagne et on stoppe la boucle et on nettoie le jeu (on y reviendra).
Si le joueur ne gagne pas on vérifie si il reste des cases à jouer, si ce n’est pas le cas c’est un match nul, on nettoie le jeu et on stoppe la boucle.
Et enfin, si le joueur ne gagne pas et qu’il reste des cases à jouer on change de joueur (si vous avez fait l’exercice du PONG cette écriture ne devrait pas vous poser de problème).
function nettoyage(f:int):void{
grille.removeEventListener(MouseEvent.CLICK, remplir);
addChild(panneaux);
panneaux.gotoAndStop(f);
}
Lorsque je dois nettoyer le jeu, j’utilise une petite fonction dans laquelle je passe le numéro de frame des panneaux à afficher selon si c’est l’humain ou l’ordinateur qui gagne ou si il s’agit d’un match nul. Je retire l’écouteur de la grille et j’ajoute le panneau d’interface que je place à la bonne frame. Un clic sur le panneau relancera le jeu et la fonction init() que nous avons déjà étudié plus haut.
// temps de latence avant réponse de l'ordi
function latenceAI():void{
var timer:Timer = new Timer(500,1);
timer.addEventListener(TimerEvent.TIMER_COMPLETE, choisiCase);
timer.start();
}
Cette partie ne sert techniquement à rien... Le programme est trop rapide pour calculer les coups de l’ordinateur, ce qui fait que lorsque le joueur humain pose une pièce l’ordinateur réagit aussitôt et pose la sienne, de fait on a l’impression que le joueur humain pose deux pièces car on n’a pas le temps de voir l’ordinateur réfléchir. Pour éviter ça je vais utiliser un petit timer qui va simplement augmenter le temps de réponse afin de donner l’illusion que l’ordinateur prend un temps pour réfléchir. il s’agit donc d’un artifice utilisé pour le confort du joueur uniquement.
// l'ordi choisi une case
function choisiCase(e:TimerEvent):void{
var tab:Array = stock.concat();
var i:String;
for (i in libre) if (verifieCase(tab,2,libre[i])) return;
for (i in libre) if (verifieCase(tab,1,libre[i])) return;
remplirOrdi(libre[int(Math.random()*libre.length)]);
}
Lorsque l’ordinateur peut jouer, il doit choisir une case, nous sommes en plein dans l’IA de l’ordi pour ce jeu, c’est la partie importante de l’exercice. Comment l’ordinateur va faire pour choisir la bonne case ?
Je commence par faire une copie isolée du stock, donc de tous les index qui ont été joués par les deux joueurs, puis je fais une boucle sur les index libres. Notez que la méthode concat() permet de copier un à un les cellules d’un tableau dans un nouveau tableau totalement indépendant.
Pour chaque index libre, je vérifie d’abord que l’ordinateur peut gagner en posant sa pièce à cet index.
Puis je refais une boucle et je regarde si l’humain peut gagner en posant sa pièce à cet index.
Pourquoi deux boucles et pas une seule avec les deux vérifications en même temps ?
Parce que si on effectue les tests simultanément il se peut que l’ordinateur choisisse de jouer un coup qui empêche le joueur de gagner alors que si il posait sa pièce à un index différent il pourrait gagner. La priorité devant être donnée à la pièce gagnante et non à la pièce bloquante, il convient de faire deux boucles complètes pour vérifier les index un à un pour chaque joueur en commençant par l’ordinateur.
Si l’ordinateur trouve une position où il gagne, ou bien une position où il empêche l’humain de gagner, il pose sa pièce à cette position, sinon il pose une pièce aléatoirement parmi les index libres.
Voyons de plus près comment l’intelligence artificielle détermine si une pièce est gagnante ou bloquante.
// l'ordi vérifie si la case est gagnante
function verifieCase(tab:Array, id:int, b:int):Boolean{
tab[b] = id;
for each (var c:Array in valid){
var w:Boolean = true;
for each (var i:int in c) w = w && tab[i] == id;
if (w){
remplirOrdi(b);
return true;
}
}
tab[b] = 0;
return false;
}
Nous avons vu cette fonction précédemment, c’est la même que pour déterminer si un joueur gagne la partie à quelques différences près. "tab" est une copie exacte du stock, je commence donc par modifier la pièce en cours avec la valeur correspondant au joueur testé ("id"). Puis je fais la vérification classique pour savoir si une combinaison est gagnante avec cette nouvelle pièce. Si c’est le cas on stoppe la boucle et l’ordi pose sa pièce. Sinon on remet la valeur ajoutée nouvellement au tableau à sa valeur initiale, à savoir 0. Pensez à le faire car c’est le même tableau qui sert aux deux tests (ordi et humain), il ne faut donc pas qu’une valeur parasite reste à la fin du test.
// l'ordi joue son coup
function remplirOrdi(p:int):void{
P = p;
remplir(null);
}
Et on termine par le coup joué par l’ordi, quelle que soit la pièce à jouer P prend la valeur de la pièce et on rempli la case correspondante dans la grille.
Conclusion
Nous avions traité un peu de l’IA dans l’exercice du PONG, ce petit programme nous apporte un autre éclairage sur la manière dont on peut faire réfléchir un ordinateur dans un jeu vidéo. Là encore il s’agit de simuler un comportement parfait, cette fois à l’aide de combinaisons préenregistrées. L’ordi ne se trompe jamais, mais il y a des chances pour que quel que soit le choix de l’ordi l’humain puisse gagner, il suffit par exemple que deux combinaisons gagnantes soient possible et là, qu’il soit humain ou ordinateur, l’issue est la même. La faille qui va permettre à un joueur humain de gagner réside en fait dans le choix aléatoire de l’ordi lorsqu’il est libre de poser une pièce où ça lui chante, alors qu’un joueur humain va tenter de calculer à l’avance la meilleure position pour bloquer son adversaire.
Les sources sont disponibles à la fin de l’exercice.
