L'effet 2048

Catégories : Expertise TechniquePar SoftFluent FranceTags: Astuces

Il y a quelques temps, un jeu a fait pas mal de buzz, il s’agit de 2048.

Le principe est simple. Sur une grille de 4 cases par 4, une tuile aléatoire (un 2 ou un 4 plus rarement) va apparaître sur une des cases vides. Le joueur pourra alors déplacer toutes les tuiles existantes dans une direction (haut bas gauche droite), et lorsque deux tuiles de même valeur entreront en contact, elle s’additionneront. Si une de ses tuiles vaut 2048, il gagne.

Gagner à ce jeu n’étant pas évident, je me suis demandé si une IA pouvait le résoudre de manière efficace. N’étant pas un inconditionnel du JavaScript, je me suis tourné vers le C# pour résoudre ce petit cas. Il me fallait donc, dans un premier temps, recréer le jeu en .NET et c’est le sujet de cette première partie.

PARTIE 1 : Création d’un 2048 en ligne de commande

La création de ce jeu se passe donc en deux étapes.

La première, de loin la plus intéressante, consiste à créer la logique du jeu, tandis que la seconde consistera a traiter l’interface.

Décomposons donc le jeu :- Nous avons un tableau d’entiers, composant la surface de jeu. – Le joueur doit selectionner une direction, vers laquelle nos tuiles se déplaceront. – A l’issue de ce déplacement, une tuile aléatoire apparaitra. – Finalement, trois choix se poseront :

Le joueur a atteint le score de 2048 et a gagné.
Le joueur n’a plus aucun mouvement disponible (le plateau avant et après mouvement est identique) et a perdu.
Dans tous les autres cas, la partie continue et le joueur doit choisir une nouvelle direction.

Pour représenter ceci, nous allons créer une classe principale « Game2048 », qui contiendra l’état et la logique de notre jeu. Pour les états du jeu, ainsi que le choix utilisateur, des énumérations feront l’affaire.

Propriétés et stockage des données

public enum GameResult { Win, Loss, Continue }    
public enum Direction { Top, Bottom, Left, Right }
public class Game2048   
{    
   public const int POW = 2;    
   public const int SIZE = 4;    
   public const int WIN = 11;    
   public const int TOTAL_CASES = SIZE * SIZE; 
   private static readonly int[] RANDOM_ITEMS = new int[] {1,1, 1, 1, 1, 2 }; 
   private int[,] _WorkBoard;   
   public int[,] WorkBoard    
   {    
   get    
   {    
   return _WorkBoard;    
   }    
   }    
}

Pour comprendre le code de la classe Game2048, une explication s’impose : En effet, on remarque que la constante WIN vaut 11, et non 2048, et que les items insérés aléatoirement sont 1 et 2, et non 2 et 4.

De manière à simplifier mes calculs d’IA (qui seront traités dans un prochain article), ainsi que pour rendre le code plus générique (pourquoi ne pas créer un 177147 avec des puissances de 3 au lieu de 2), j’ai choisi de baser mon code métier sur l’exposant de la puissance de 2 de la tuile, et non sur le chiffre réel. Ainsi, je n’additionnerais pas 2 tuiles de valeur 64 en une tuile 128, mais deux tuiles de valeur 6 se transformeront en une de valeur 7.

Egalement, on remarque que RANDOM_ITEMS donne une chance sur 4 d’obtenir un 2 plutôt qu’un 1. Dans le jeu originel, la valeur 4 apparait un nombre de fois nettement inférieur. Néanmoins, j’ai préféré donner un grand nombre d’apparitions à ce chiffre de manière à ce que mes algorithmes de résolution soient obligés de prendre en compte l’apparition fréquente des 4, et ne se contentent pas d’espérer qu’un 2 tombera, ce qui est souvent le cas.

Je prévois néanmoins un méchanisme pour récupérer, depuis le tableau « de travail », le tableau a afficher.

private Dictionary<int, int> _Pows = new Dictionary<int, int> { { 0, 0 } }; 
public int[,] ShowBoard   
{    
   get    
   {    
   int[,] board = new int[SIZE, SIZE];    
   for (int x = 0; x < SIZE; x++)    
   {    
   for (int y = 0; y < SIZE; y++)    
   {    
   var current = WorkBoard[x, y];    
   int show;    
   if (!_Pows.TryGetValue(current, out show))    
   {    
   show = (int)Math.Pow(POW, current);    
   _Pows.Add(current, show);    
   }    
   board[x, y] = show;    
   }    
   }    
   return board;    
   }    
}

Ainsi, toute la partie logique s’effectuera sur le « Workboard », et la partie affichage via le « ShowBoard ».

Maintenant que nous disposons de toutes les propriétés nécessaires au stockage d’une partie, il nous faut créer la logique du jeu. Commençons par le commencement : l’initialisation du plateau.

Initialisation du plateau

Pour initialiser le plateau, nous devons ajouter, de manière aléatoire, deux tuiles de valeur minimale sur le plateau.

La méthode permettant d’ajouter les 2 tuiles initiales sera celle qui servira à chaque tour de jeu jusqu’à la victoire ou la défaite du joueur.

private Random _GameRandom = new Random(); 
public Game2048()   
{    
   InitializeBoard();    
} 
private void InitializeBoard()   
{    
   _WorkBoard = new int[SIZE, SIZE];    
   _WorkBoard.Fill(SIZE, SIZE, 0); 
   InsertRandom(RANDOM_ITEMS.Min());   
   InsertRandom(RANDOM_ITEMS.Min()); 
} 
private void InsertRandom(int fixedRandomValue = -1)   
{ 
   int item = fixedRandomValue == -1 ? RANDOM_ITEMS[_GameRandom.Next(0, RANDOM_ITEMS.Length)] : fixedRandomValue;   
   int position = _GameRandom.Next(0, TOTAL_CASES);    
   while (true)    
   {    
   for (int x = 0; x < SIZE; x++)    
   {    
   for (int y = 0; y < SIZE; y++)    
   {    
   int numPos = _WorkBoard[x, y];    
   if (numPos == 0)    
   {    
   if (position == 0)    
   {    
   _WorkBoard[x, y] = item;    
   return;    
   }    
   else    
   position--;    
   }    
   }    
   }    
   }    
}

Lors de l’initialisation, on aura toujours des tuiles de valeur 2, mais pour toutes les autres utilisations de la méthode, la valeur de la tuile sera aléatoire parmi les valeurs possibles de RANDOM_ITEMS.

On remarque également que quelques méthodes d’extension ont été créées sur les tableaux d’entiers, de manière à simplifier la lecture du code.

Voici le détail de celles qui seront utilisées :

//Cette méthode remplis le tableau avec la valeur donnée en argument.    
public static void Fill(this T[,] array, int x_size, int y_size, T value);    
//Comme son nom l'indique, cette méthode valide si une des valeurs du tableau satisfait une condition donnée.     
public static bool Any(this T[,] array, int x_size, int y_size, Predicate condition);    
//Idem, mais la fonction d'évaluation donne accès à la position de la case dans le tableau     
public static bool Any(this T[,] array, int x_size, int y_size, Func<T, int, int, bool> condition);    
//Cette fonction compare deux tableaux, afin de déterminer si toutes les valeurs de leurs cases sont identiques     
public static bool IsDifferent(this T[,] array, T[,] array2, int x_size, int y_size);    
//Permet d'effectuer une action sur toutes les cases d'un tableau     
public static void Foreach(this T[,] array, int arraySideSize, Action<int, int> toDo);    
//Identique à la précédente, mais donne également la valeur de la case en variable d'entrée     
public static void Foreach(this T[,] array, int arraySideSize, Action<int, int, T> toDo);    
//Retourne la plus grande tuile d'un tableau     
public static int Max(this int[,] array, int arraySideSize);    
//Retourne la somme des tuiles d'un tableau     
public static int Sum(this int[,] array, int arraySideSize);    
//Indique si la partie est perdue (pour cela, teste si des cases de valeur 0 existent,    
//ou si toutes les cases adjacentes sont de valeurs différentes.     
public static bool IsLost(this int[,] array, int arraySideSize)   
{    
   if (array.Any(arraySideSize, arraySideSize, x => x == 0))    
   return false; 
   for (int x = 0; x < arraySideSize; x++)   
   {    
   for (int y = 0; y < arraySideSize; y++)    
   {    
   if ((x != arraySideSize - 1 && array[x, y] == array[x + 1, y]) ||    
   (y != arraySideSize - 1 && array[x, y] == array[x, y + 1]))    
   return false;    
   }    
   }    
   return true;    
}

Une fois le plateau initialisé, il est temps de gérer les mouvements sur le plateau.

Agir sur le plateau

L’action de bouger sur le plateau est assez simple : il s’agit de déplacer toutes les tuiles dans une direction, puis lorsque deux tuiles se touchent et ont la même valeur, augmenter la valeur de la tuile cible du mouvement.

Attention : une tuile ayant déjà été fusionnée ne peut l’être une seconde fois. Par exemple :

Si une ligne comporte les valeurs 1 1 2 3 (ou 2 2 4 8 en terme d’affichage), et que l’on décide de se déplacer vers la droite, le résultat devra être 0 2 2 3 et non 0 0 0 4.

Pour réaliser ceci, j’ai fait le choix de me contenter d’une seule méthode GoDirection, et d’inverser le sens de parcours en fonction de la direction choisie.

private void GoDirection(Direction direction)   
{    
   bool revertXY = false, revertOrder = false; 
   // go top   
   switch (direction)    
   {    
   case Direction.Top:    
   revertXY = true;    
   break;    
   case Direction.Bottom:    
   revertXY = true;    
   revertOrder = true;    
   break;    
   case Direction.Left:    
   break;    
   case Direction.Right:    
   revertOrder = true;    
   break;    
   }    
   bool[,] changed = new bool[SIZE, SIZE];    
   changed.Fill(SIZE, SIZE, false); 
   for (int x = 0; x < SIZE; x++)   
   {    
   bool changes;    
   do    
   {    
   changes = false;    
   if (DirectionChooser(changed, x, revertXY, revertOrder))    
   changes = true;    
   }    
   while (changes);    
   }    
}

On séléctionne dans quel sens va aller notre boucle, puis on crée un tableau contenant les positions de toutes les tuiles ayant été fusionnées.

Après avoir décalé d’une position toutes les tuiles d’une case, on vérifie s’il y a eu des changements, et si c’est le cas, on tente de re-décaler les cases jusqu’à ce que plus rien ne se passe.

private bool DirectionChooser(bool[,] changed, int x, bool revertXY, bool revertOrder)   
{    
   bool changes;    
   changes = false; 
   if (revertOrder)   
   {    
   for (int y = SIZE - 2; y >= 0; y--)    
   {    
   if (InsideTheGo(changed, x, y, revertOrder, revertXY))    
   changes = true;    
   }    
   }    
   else    
   {    
   for (int y = 1; y < SIZE; y++)    
   {    
   if (InsideTheGo(changed, x, y, revertOrder, revertXY))    
   changes = true;    
   }    
   }    
   return changes;    
}

La fonction « DirectionChooser », quand à elle, gère la boucle principale de déplacement : On détermine si l’on va effectuer nos déplacements dans le sens normal, ou d’avant vers l’arrière via le boolean revertOrder, et si l’on vas agir sur l’axe des X ou des Y via revertXY.

Puis, on laisse la fonction InsideTheGo effectuer des fusions et des déplacements, et nous indiquer si une modification a été détectée.

private bool InsideTheGo(bool[,] changed, int x, int y, bool revertOrder, bool revertXY)   
{    
   int addremove = (revertOrder ? 1 : -1);    
   int finalStartX = revertXY ? y : x;    
   int finalStartY = revertXY ? x : y;    
   int finalNextX = revertXY ? (finalStartX + addremove) : finalStartX;    
   int finalNextY = revertXY ? finalStartY : (finalStartY + addremove); 
   int me = _WorkBoard[finalStartX, finalStartY];   
   if (me == 0)    
   return false; 
   int next = _WorkBoard[finalNextX, finalNextY]; 
   if ((next != 0) && (next != me || changed[finalNextX, finalNextY] || changed[finalStartX, finalStartY]))   
   return false; 
   _WorkBoard[finalNextX, finalNextY] = next == 0 ? me : (me + 1);   
   _WorkBoard[finalStartX, finalStartY] = 0;    
   if (next == 0)    
   changed[finalNextX, finalNextY] = changed[finalStartX, finalStartY];    
   else    
   changed[finalNextX, finalNextY] = true;    
   changed[finalStartX, finalStartY] = false; 
   return true;   
}

Pour effectuer les actions nécessaires, on détermine quelle est la cellule actuelle et quelle est la cellule cible.

Une fois ceci effectué, il ne reste qu’a vérifier si la cellule actuelle ou la cible a déjà été fusionnée à cette action, ou si elle doit être déplacée, et faire l’action correspondante.

Une fois toutes ces opérations effectuée, le déplacement du joueur a été réalisé.

Résultat du mouvement du joueur

Nous sommes maintnant capables de faire déplacer un joueur. Reste donc à lui faire connaitre le résultat de son action.

Pour ceci, la fonction GoDirection est wrappée dans une méthode publique « DoAction », qui préviendra le joueur si il a gagné ou perdu la partie, ou s’il doit continuer a effectuer des déplacements.

public GameResult DoAction(Direction direction)   
{    
   int[,] oldBoard = new int[SIZE, SIZE];    
   Array.Copy(_WorkBoard, 0, oldBoard, 0, SIZE * SIZE);    
   GoDirection(direction); 
   if (_WorkBoard.IsDifferent(oldBoard, SIZE, SIZE))   
   { 
   if (_WorkBoard.Any(SIZE, SIZE, x => x == 0))   
   InsertRandom(); 
   if (CheckWin())   
   return GameResult.Win;    
   else if (CheckLost())    
   return GameResult.Loss;    
   else    
   return GameResult.Continue;    
   }    
   else    
   return GameResult.Continue;    
} 
private bool CheckLost()   
{    
   return _WorkBoard.IsLost(SIZE);    
} 
private bool CheckWin()   
{    
   return _WorkBoard.Any(SIZE, SIZE, x => x == WIN);    
}

Rien de bien sorcier ici, nous réutilisons les méthodes d’extension que nous avons détaillé plus haut, de manière à donner l’état du jeu.

Finalement, il ne nous reste plus qu’a afficher le plateau de jeu, et nous pourrons enfin profiter de 2048, en ligne de commande.

Interface graphique

Un petit projet d’interface console est créé pour l’occasion.

On y crée la partie (new Game2048 ()), et tant que la partie n’est pas finie (réception d’un résultat Win ou Loss) , on affiche la grille de jeu, et on demande au joueur dans quelle direction il compte aller.

Pour un jeu un peu plus agréable à jouer, on colorise les numéros en fonction de leur score ( on affiche les 0 en noir sur noir, pour les voir disparaître par exemple).

Le code de l’interface graphique en lui même ne présentant pas d’intérêt particulier, il ne sera pas détaillé dans cet article. Vous pourrez néanmoins le retrouver ici :

https://github.com/NicolasVoyez/Softfluent.Articles.NVO.Game2048-Part1

PARTIE 2 : IA et règles

Le principe est très simple :

Il s’agit de définir des règles, et de les combiner de manière à obtenir le meilleur mouvement possible à partir d’une situation donnée.

De là, on tirera deux types de règles :

Celles qui s’appliquent sur le plateau indépendamment de l’endroit ou apparaitra la nouvelle tuile aléatoire.
Celles qui doivent tenir compte des apparitions “pas de chance” et agir en limitant les dégâts.

Chaque règle disposera aussi d’un coefficient, permettant, si nécessaire, d’augmenter l’importance de certaines règles comparées à d’autres.

Toutes mes règles hériteront donc de AIRule, précisant toutes ces informations :

public abstract class AIRule    
{     
   public abstract AIUse Usecase { get; }     
   public abstract double Coefficient { get; set; }     
   public abstract double CalculatePoints(int[,] grid, Direction fromDirection, int gridSideSize);     
   public string TypeName     
   {     
   get     
   {     
   return GetType().Name;     
   }     
   }     
   public override string ToString()     
   {     
   return TypeName + " : " + Math.Round(Coefficient, 3);     
   }     
}     
public enum AIUse     
{     
   WorstCaseGrid,     
   AfterMoveGrid,     
}

J’ai ainsi crée un certain nombre de règles que je vais maintenant détailler :

EmptyCellsRule : Cette règle tend à maximiser le nombre de cellules vides (plus il y a de cellules vides, plus on a de marge de manoeuvre et plus on est dans une position avantageuse)

var emptyCellsCount = 0;         
grid.Foreach(gridSideSize, (x, y, content) =>         
{         
   if (content == 0)         
   emptyCellsCount++;         
});         
return emptyCellsCount == 0 ? 0 : Coefficient * emptyCellsCount;

LostRule : Si le prochain mouvement peut vous faire perdre, cette règle s’efforce de vous l’interdire.
```
return Coefficient *( grid.IsLost(gridSideSize) ? _LoosingScore : 0);
```
MaxValueRule : Il est toujours intéressant d’avoir un plus gros chiffre qui apparait sur l’écran que ceux que l’on avait précédemment. Eventuellement, ça peut même nous faire gagner la partie
```
return Coefficient * grid.Max(gridSideSize);
```

MonotonyRule : Fait en sorte que toutes les tuiles soient dans le même “ordre” vers le haut/bas et gauche/droite. C’est une des règles les plus importantes, vu qu’elle permet de ne pas désorganiser son jeu.

var totals = new double[] { 0, 0, 0, 0 }; grid.Foreach(gridSideSize, (x, y, content) =>         
{         
   if (content == 0) return;         
   if (y < 3)         
   {         
   int nextY = y;         
   int next;         
   do         
   {         
   nextY++;         
   next = grid[x, nextY];         
   }         
   while (nextY < gridSideSize - 1 && next == 0);         
   if (content > next)         
   totals[0] -= content - next;         
   else         
   totals[1] -= next - content;         
   }         
   if (x < 3)         
   {         
   int nextX = x;         
   int next;         
   do         
   {         
   nextX++;         
   next = grid[nextX, y];         
   }         
   while (nextX < gridSideSize - 1 && next == 0);         
   if (content > next)         
   totals[2] -= content - next;         
   else         
   totals[3] -= next - content;         
   }         
});         
return Coefficient * (Math.Min(totals[0], totals[1]) + Math.Min(totals[2], totals[3]));

RandomRule : Comme son nom l’indique, une règle donnant un résultat aléatoire. Utile notamment pour comparer les résultats statistiques d’une règle à un comportement random.
```
return (_r.Next(0,600)-300)/100d;
```

SmoothnessRule : Règle qui minimise la différence de valeur entre deux tuiles adjacentes. C’est cette règle qui permet de positionner les tuiles de manières à ce qu’elles se fusionnent facilement.

double smoothness = 0; grid.Foreach(gridSideSize, (x, y) =>         
{         
   var currCell = grid[x, y];         
   if (currCell != 0)         
   {         
   var cellX = grid.GetNextValueWithVector(x, y, 1, 0, gridSideSize);         
   if (currCell != cellX && cellX != 0)         
   smoothness -= Math.Abs(currCell - cellX);         
   var cellY = grid.GetNextValueWithVector(x, y, 0, 1, gridSideSize);         
   if (currCell != cellY && cellY != 0)         
   smoothness -= Math.Abs( currCell - cellY);         
   }         
});         
return smoothness * Coefficient;

SpamTopRightTillReflexionNeeded : En début de partie, pas besoin de réfléchir, autant spammer les touches haut et droite tant que nous n’avons pas une tuile d’une taille suffisante.

if (!(fromDirection == Direction.Bottom || fromDirection == Direction.Right))         
   return 0; if (grid.Max(gridSideSize) > ReflexionPoint)         
   return 0;         
return ReflexionPoint * Coefficient;

Nous disposions maintenant de notre liste de règles, il va nous falloir les appliquer à chaque phase de jeu de manière à ce que notre IA puisse réussir une partie complète.

IA gérant une partie complète

Comme dit précédemment, maintenant que nous disposons d’une base de règles (celle-ci peut bien sûr être complétée à loisir), il va nous falloir utiliser ces règles pour gérer une partie.

Le seul paramètre composant notre AI sera la liste des règles la composant, que nous décomposerons entre les règles de type “WorstCase” et celles de type “AfterMove”

public List<AIRule> Rules { get; set; }      
private IEnumerable<AIRule> AfterMoveRules       
{       
   get { return Rules.Where(x => x.Usecase == AIUse.AfterMoveGrid); }       
}       
private IEnumerable<AIRule> WorstCaseRules       
{       
   get { return Rules.Where(x => x.Usecase == AIUse.WorstCaseGrid); }       
}

Puis, la gestion d’une partie sera très simple : On sélectionne la meilleure direction, on l’applique, et on répète la boucle tant que la partie n’est pas terminée. Petite subtilité :

Un paramètre “onPlayed” de type action est ajouté pour permettre à la couche graphique d’afficher les mouvements successifs si besoin.

public GameResult PlayGame()      
{       
   Game2048 game = new Game2048();       
   return PlayGame(game,null).Item1;       
}       
public Tuple<GameResult, int[,]> PlayGame(Game2048 game, Action onPlayed = null)       
{       
   GameResult result = GameResult.Continue;       
   while (result == GameResult.Continue)       
   {       
   result = game.DoAction(GetBestDirection(game));       
   if (onPlayed != null)       
   onPlayed();       
   }       
   return new Tuple<GameResult,int[,]>(result, game.WorkBoard);       
}

Reste maintenant à déterminer le meilleur mouvement à réaliser. Pour cela, on va, pour chaque direction possible, calculer le score de la grille résultante. Nous avons donc besoin d’une nouvelle méthode “TryDirection” qui copie le jeu actuel pour tester indépendamment chaque direction sans l’ajout de tuile aléatoire.

Cette méthode créée, nous n’avons plus qu’à boucler sur les directions, et calculer le score de toutes les règles “afterMove” pour chaque direction, puis de prendre le pire score possible pour chaque possibilité d’apparition de case aléatoire pour chaque règle “WorstCase”. L’addition des deux nous donnera un score par direction, et nous choisirons le meilleur.

Evidemment, les directions qui ne produisent aucun résultat (i. e. la grille avant et après mouvement est la même) sont éliminées d’office.

private Direction GetBestDirection(Game2048 game)      
{       
   Direction bestDirection = Direction.Right;       
   double bestScore = double.MinValue;       
   foreach (var direction in Directions.All)       
   {       
   var gameAfterMove = game.TryDirection(direction);       
   // verify no move is forbidden       
   if (!game.WorkBoard.IsDifferent(gameAfterMove,Game2048.SIZE,Game2048.SIZE))       
   continue;       
   double afterMoveScore = AfterMoveRules.Sum(rule => rule.CalculatePoints(gameAfterMove, direction, Game2048.SIZE));       
   double worstCaseScore = double.MaxValue;       
   // after moving the gameboard, let's check what new item position is the worst possible, and use this score.       
   gameAfterMove.Foreach(Game2048.SIZE, (x, y, content) =>       
   {       
   if (content != 0) return;       
   foreach (int possibleRandomValue in Game2048.DISTINCT_RANDOM_ITEMS)       
   {       
   gameAfterMove[x, y] = possibleRandomValue;       
   double possibleScore = WorstCaseRules.Sum(rule => rule.CalculatePoints(gameAfterMove, direction, Game2048.SIZE));       
   if (possibleScore < worstCaseScore)       
   worstCaseScore = possibleScore;       
   gameAfterMove[x, y] = 0;       
   }       
   });       
   double score = worstCaseScore + afterMoveScore;       
   if (score > bestScore )       
   {       
   bestScore = score;       
   bestDirection = direction;       
   }       
   }       
   return bestDirection;       
}

Tout est maintenant prêt pour afficher cette IA.

Affichage du travail de l’IA

Maintenant que notre IA est fonctionnelle, il nous faut encore l’afficher afin d’avoir la joie de la voir se débattre contre le jeu devant nos yeux. Pour cela, nous allons reprendre le code console de la partie 1 et lui permettre, via certains paramètres de démarrage, de lancer une IA.

Pour évaluer la compétence de notre IA, nous rajoutons d’ailleurs un Score à chaque partie :

public int Score    
{     
   get     
   {     
   int score = 0;     
   ShowBoard.Foreach(SIZE, (x, y, content) =>     
   {     
   score += content;     
   });     
   return score;     
   }     
}

Sans paramètre, le jeu se lancera de manière classique pour qu’un humain puisse y jouer. Avec paramètre, on lancera une IA contenant les règles qui nous intéressent. Enfin, un paramètre supplémentaire (“-stats”) permettra de lancer 1000 parties afin d’évaluer la pertinence de cette IA.

Résumons :

- - notreExecutable. exe : lancement du jeu pour un joueur humain
  - notreExecutable. exe –empty –lost Lancement d’une partie jouée par une IA avec les règles “EmptyCellsRule” et “LostRule”
  - notreExecutable. exe –all –stats Lancement de 1000 parties jouées par une IA avec toutes les règles configurées.

A l’occasion de ce dernier test, on s’aperçoit d’ailleurs que le résultat n’est pas fameux :

résultat

1% de victoire, on ne peut pas appeler cela une IA performante.

La raison viens très probablement des coefficients qui sont actuellement tous positionnés à la valeur “1”.

Mais comment les positionner, si ce n’est au hasard en essayant petit à petit de les rectifier jusqu’à tomber sur de meilleurs résultats ? C’est justement le sujet du prochain article à paraître. Comme toujours, les sources peuvent être trouvées sur github !

PARTIE 3 : Un Algorithme génétique ?

Pour commencer, qu’est-ce qu’un algorithme génétique ?

C’est très simple : un algorithme génétique va reproduire le fonctionnement de l’évolution, dans le but d’obtenir un résultat le plus probant possible. Un algorithme génétique est particulièrement bien indiqué lorsque le nombre de possibilités est beaucoup trop important pour effectuer un parcours de toutes les possibilités afin de déterminer la meilleure.

Comment fonctionne-t-il ?

A partir d’une population d’individus donnés (dans notre cas, un individu sera une IA résolvant le jeu), l’algorithme va sélectionner un certain nombre d’entre eux. Meilleur l’individu est, plus il aura de chances d’être sélectionné. Néanmoins, un individu plus mauvais aura lui aussi ses chances.

Ces individus sélectionnés vont ensuite se reproduire, et mélanger leurs gènes (dans notre cas, les règles d’IA), créant une génération d’enfants. De temps en temps, certains individus peuvent également muter, en créant des individus totalement nouveaux dus aux aléas de la vie. Finalement, dans cette population de parents, d’enfants et de mutants, certains (les plus mauvais dans notre cas) mourront, de manière à garder la taille de la population stable.

Il sera possible d’agir sur tous ces facteurs, de manière à spécialiser notre algorithme.

Veut-on laisser beaucoup ou peu de chances aux mauvais spécimens ? (un mauvais spécimen pouvant malgré tout, par reproduction/mutation, participer à l’amélioration globale de la population)
Veut-on beaucoup de parents par génération ? peu ?
Combien de parents pour un enfant ?
Quelle est la fréquence des mutations ?
etc…

Et le code dans tout ça ?

Développement de l’algorithme

Maintenant que nous connaissons l’algorithme, voyons voir comment le développer.

Etape 1 : Créer une population initiale

Pour cette partie, rien de plus simple, il suffit de récupérer toutes les règles possibles, et de les attribuer de manière aléatoire aux IAs. Pas besoin pour un algorithme génétique que la population de départ soit efficace sur le problème, ce sont surtout les croisements qui nous apporteront la victoire.

public void PopulateAIs(int populationSize = 100)    
{     
   PopulationSize = populationSize;     
   RaiseEvent("Populating IA for DNA Lab");     
   for (int i = 0; i < PopulationSize; i++)     
   {     
   List<AIRule> rules = new List<AIRule>();     
   for (int j = 0; j < _Types.Length; j++)     
   {     
   if (RollDice(j % 5 + 1))     
   rules.Add(CreateNewIAIRule(_Types[j], _rand.NextDouble() * MAX_COEFFICIENT));  
   }     
   if (rules.Count == 0)     
   i--;     
   else     
   _Population.Add(new AIWrapper(new AI(rules)));     
   RaiseEvent(i + 1 + " rules genes created");     
   }     
}     
private bool RollDice(int faces = 2)     
{     
   return _rand.Next(0, faces) % faces == 0;     
}

PS pour les sceptiques : Oui, un dé à deux faces ça existe : dé à 2 faces

Etape 2 : Méthode de sélection des parents

De nombreuses méthodes de sélection des parents existent (quelques-uns sont présentés brièvement ici ). La méthode choisie ici est celle de la sélection par tournoi.

Des mini-tournois ont lieu par groupes aléatoires de N individus, et les G meilleurs individus sont considérés comme gagnants du tournoi. Tous les gagnants de chaque mini-tournoi peuvent ensuite se reproduire.

Cette méthode tend à nous rapprocher très rapidement d’une solution. En effet les N-G pires individus de la population globale n’ont aucune chance, ce qui, avec les valeurs choisies (tournois avec 3 gagnants parmi 10 personnes), signifie que les 7 pires individus disparaitront à chaque phase d’évolution, à moins que les enfants des gagnants ne soient pires qu’eux.

private List<AIWrapper> TournamentSelection(int roundSize = 10, int winners = 3)    
{     
   List<AIWrapper> init = new List<AIWrapper>(_Population);     
   List<AIWrapper> kept = new List<AIWrapper>();     
   while (init.Count != 0)     
   {     
   List<AIWrapper> currentTournament = new List<AIWrapper>();     
   for (int i = 0; i < roundSize; i++)     
   {     
   var challenger = init[_rand.Next(0, init.Count)];     
   init.Remove(challenger);     
   currentTournament.Add(challenger);     
   }     
   kept.AddRange(currentTournament.OrderByDescending(x => x).Take(winners));     
   }     
   return kept;     
}

Etape 3 : Croiser les gènes

On va tenter dans cette étape de croiser les gènes des gagnants du tournoi, de manière à générer des enfants. Pour se faire, on tente d’assortir les gagnants ayant les gènes les plus éloignés les uns des autres, et ceci toujours à un random près.

Evidemment, seuls les enfants au génome correct (plus d’une règle) survivront.

private List<AIWrapper> CrossGenes(List<AIWrapper> toCross, int minSizeToLive = 1)    
{     
   List<AIWrapper> init = new List<AIWrapper>(toCross);     
   List<AIWrapper> children = new List<AIWrapper>();     
   while (init.Count > 1)     
   {     
   var mother = init[_rand.Next(0, init.Count)];     
   var motherRules = new List<AIRule>(mother.Intelligence.Rules);     
   init.Remove(mother);     
   var father = GetRandomFarthestGenes(motherRules, init);     
   var fatherRules = new List<AIRule>(father.Intelligence.Rules);     
   init.Remove(father);     
   List<AIRule> childRules = new List<AIRule>();     
   List<Type> childTypes = new List<Type>();     
   CrossParent(motherRules, fatherRules, childRules, childTypes);     
   CrossParent(fatherRules, motherRules, childRules, childTypes);     
   if (childRules.Count < minSizeToLive) // not enough Genes to live on.     
   continue;     
   children.Add(new AIWrapper(new AI(childRules)));     
   }     
   return children;     
}     
private AIWrapper GetRandomFarthestGenes(IEnumerable<AIRule> motherRules, List<AIWrapper> init, int randomBetweenMaxNumber = 5)     
{     
   var distanceOrderedRules = init.OrderByDescending(x => DistanceFrom(motherRules, x.Intelligence.Rules));     
   return     
   distanceOrderedRules.ElementAt(     
   _rand.Next(0, init.Count >= randomBetweenMaxNumber ? randomBetweenMaxNumber : init.Count));     
}

Etape 4 : Les mutants

Chaque individu aura également trois chances sur mille de muter. Si tel est le cas, il subira trois mutations, qui en réalité correspondent à peu de chose près à un croisement avec un individu qui disposerait de tous les gènes possibles.

Le code étant très semblable à celui du croisement de gènes, vous trouverez celui-ci en ligne sur gitHub.

Etape 5 : La fonction de vie

Finalement, il ne nous manque plus qu’une fonction permettant de relier ces différents aspects entre eux, de manière à pouvoir lancer l’algorithme complet. On remarquera notamment qu’à la fin de la boucle, le score du meilleur élément est recalculé. Ceci est fait de manière à éviter des faux positifs, chaque score d’IA ne portant “que” sur 200 matchs, et pouvant donc être biaisé.

Nous proposons d’ailleurs deux manières d’arrêter l’algorithme :

Soit une intervention extérieure via une méthode “stop”, soit le fait que notre algorithme arrive à satisfaire une condition de fin, comme par exemple “le meilleur individu arrive à plus de 80% de réussite”.

public void Live(Action<IEnumerable<AIWrapper>> onGenerationEnd, Predicate<AIWrapper> endCondition, double mutationOccurence = 0.003d)    
{     
   RaiseEvent("DNA samples start living");     
   AIWrapper bestWrapper = null;     
   do     
   {     
   var ToReproduce = TournamentSelection();     
   RaiseEvent("Tournament ended, {0} genes selected", ToReproduce.Count);     
   var children = CrossGenes(ToReproduce);     
   List<AIWrapper> mutated = new List<AIWrapper>();     
   foreach (var element in _Population)     
   {     
   if (_rand.NextDouble() < mutationOccurence)     
   mutated.Add(Mutate(element));     
   }     
   RaiseEvent("Mutation ended, {0} genes selected", mutated.Count);     
   var orderedPopulation = new List<AIWrapper>((from element in _Population.Union(children).Union(mutated)     
   orderby element descending     
   select element).Take(PopulationSize));     
   _Population.Clear();     
   foreach (var element in orderedPopulation)     
   _Population.Add(element);     
   bestWrapper = _Population.First();     
   RaiseEvent("Population resynchronized, best gene was " + bestWrapper);     
   // avoid exceptionnal lucky results in best scores.     
   if (bestWrapper != null)     
   bestWrapper.GenerateScore();     
   RaiseEvent("Best gene score recalculated, now he is " + bestWrapper);     
   if (onGenerationEnd != null)     
   onGenerationEnd(_Population);     
   }     
   while (!endCondition(bestWrapper) && !_stop);     
   _stop = false;     
   RaiseEvent("DNA samples pause their lives");     
}

Monitorer l’algorithme

L’algorithme créé, il est difficile de monitorer en ligne de commande 100 individus, et de suivre le parcours de celui-ci. Une petite IHM plus lisible est donc nécessaire.

Vous trouverez donc dans la solution jointe une interface permettant d’effectuer les actions minimales pour monitorer le fonctionnement de l’algorithme.

Démarrer et mettre en pause la simulation de la vie
Sauvegarder et charger une population d’IA
Générer une nouvelle population

Et après ?

Tout d’abord, je tiens à vous rappeler que les sources sont disponibles ici, et surtout à vous remercier d’avoir suivi cette suite d’articles.

Maintenant que vous les avez terminé, vous disposez de toutes les cartes en main pour développer, tester et approuver la meilleure IA possible pour 2048 (ou pour tout autre jeu d’ailleurs).

Quant à celle présente dans les sources de ce projet ? Elle peine à dépasser les 20% de parties gagnées. Comment est-ce possible ?

Une règle est-elle mal écrite ? Manque-t-il des règles pour rendre l’IA plus performante ? Est-il impossible de réaliser plus de 20% de victoire avec le 2048 écrit dans le 1er article ?

C’est à vous de le découvrir !

N’hésitez d’ailleurs pas à poster vos découvertes en commentaire.

Encore merci pour votre attention, et à bientôt.

Ne ratez plus aucunes actualités avec la newsletter mensuelle de SoftFluent

L’effet 2048