Implémentation d’une IA pour l’Awalé (Partie 2)

Hellooo, cet article est la suite d’un autre qui se charge d’introduire les concepts nécessaires à la compréhension du code exposé ici. Si vous n’y avez pas encore fait un tour je vous encourage vivement à le faire. Au risque de ne rien saisir de tout ce qui va se passer ici.

Jeu d’awalé

Si vous avez manqué l’épisode précédent, je vous remet le lien:

[embed]Implémentation d’une IA pour l’Awalé (Partie 1) Helloooo, dans ce article je vous apprends comment écrire une IA qui arrive à jouer à l’Awalé. On verra uniquement dans…medium.com

Implémentation du simulateur en Dart

Pourquoi Dart ? Premièrement parce que c’est un langage simple, facile à comprendre de tous, Il est assez proche du javascript. Deuxièmement parce ça sera plus facile à intégrer après dans un jeu mobile fait avec Flutter & Flame :) .

En matière d’implémentation nous ne sommes pas tous égaux, et de plus nous n’avons pas tous les mêmes goûts. L’implémentation que je propose ici ne se veut pas être la plus optimale, Si vous trouvez une meilleure implémentation je serai heureux que vous la partagiez avec moi 😊.

Je tiens a m’excuser d’avance pour les erreurs éventuelles que vous constaterez, je vous prie de m’en informer gentiment dans l’espace des commentaires.

Classe / Etat de jeu

Nous allons commencer ce périple de programmation, par la classe associée à l’état de jeu. J’ai volontairement choisi de ne pas utiliser une vraie matrice pour implémenter le plateau ici, afin d’améliorer la lisibilité et faciliter le débogage. Vous pouvez utiliser une matrice de votre coté si vous le souhaitez.

/// Represente un état du jeu awalé
class GameState {
  /// Liste des cercles contenant les pions en face du joueur 1
  List<int> p1pad;
/// Liste des cercles contenant les pions en face du joueur 2
  List<int> p2pad;
  /// Gains du joueur 1
  int p1points;
  /// Gains du joueur 2
  int p2points;
  GameState({
    required this.p1pad,
    required this.p2pad,
    required this.p1points,
    required this.p2points,
  });

p1pad représente la première ligne de la matrice, p2pad représente la seconde ligne. Les points des joueur 1, et 2 sont respectivement p1points, et p2points.

On énumère nos joueurs, en leur définissant des types associés:

/// Enumération représentant les joueurs du jeu
enum GamePlayer {
  p1,
  p2,
}

Tadaaaa! notre fonction d’évaluation peut prendre forme:

/// Evalue t'état du jeu par rapport au joueur [mainPlayer]
  int evaluate([GamePlayer mainPlayer = GamePlayer.p1]) {
    int v1 = p1pad.where((p) => p == 1 || p == 2).length;
    int v2 = p2pad.where((p) => p == 1 || p == 2).length;
    switch (mainPlayer) {
      case GamePlayer.p1:
        return (2 * p2points + v1) - (2 * p1points + v2);
      case GamePlayer.p2:
        return (2 * p1points + v2) - (2 * p2points + v1);
    }
  }

Si vous avez compris la formule, le code ne devrai pas vous gêner, c’est son implémentation dans sa forme la plus naïve.

Je vous épargne le scrolling, je remet la formule

Et le delta :)

Petit détour, avant la simulation

Avant de pouvoir écrire notre fonction de simulation, nous allons écrire la classe qui nous permettra de gérer notre matrice “circulaire”. Afin de faire les différentes conversions, entre le vecteur et la matrice d’état.

/// Classe utilitaire servant à gérer une matrice à 2 lignes
/// à indexation circulaire, optimisée pour le jeu d'awalé
class CircularMatrix {
  List<int> buffer; // Tampon global
  int rowLength; // Longueur d'une ligne

CircularMatrix({
    required this.buffer,
    required this.rowLength,
  });
}

Buffer représente le vecteur, et rowLength représente le N, la largeur de la ligne, le nombre de cases par joueur. Pardonnez mon lexique de vieux programmeur système. 😞

On donne le constructeur qui permet de construire le vecteur à partir des deux lignes de la matrice:

/// Détermine le tampon associé à la matrice en fonction des
  /// deux lignes soumises
  factory CircularMatrix.from2Rows(List<int> row0, List<int> row1) {
    if (row0.length != row1.length) {
      throw Exception("Les lignes n'ont pas pas la même taille");
    }
    int rowLength = row0.length;
    return CircularMatrix(buffer: [
      ...row1,
      ...row0.reversed,
    ], rowLength: rowLength);
  }

On vérifie que les lignes ont bel et bien le même nombre de colonnes, et on calcul le vecteur, qui n’est rien d’autre qu’une liste ayant comme éléments la seconde ligne de la matrice, suivie de la première ligne renversée de cette dernière.

Après il faut pouvoir convertir les indices de la matrice en indices du vecteur:

/// Retourne l'index circulaire
  int getCircularIndex(int row, int index) {
    if (index < 0 || index > rowLength) {
      throw Exception("Indexation en déhors des limites");
    }
    return row == 1 ? index : 2 * rowLength - 1 - index;
  }

Pour une ligne et une colonne de la matrice, il faut retourner l’indice du vecteur correspondant. La formule est légèrement différente ici parce que les indices commencent à partir de 0 , au lieu de 1. Je vous explique rapidement comment retrouver ces expressions.

La formule de base est :

On ne va garder que la première ligne:

Encadrons les indices:

Posons les variables k et l, qui représentent respectivement les indices i et j mais qui démarrent à partir de 0.

J’ai ajouté (-1) dans la dernière expression pour que le résultat soit compris entre N et 2N-1 au lieu de N+1 et 2N, vu que les indices du vecteur commencent aussi à partir de zéro. En effectuant les remplacement on retrouve les formules utilisées dans le code :

Le passage des indices du vecteur à ceux de la matrice se font avec cette méthode:

/// Convertit un index circulaire en index matriciel
  List<int> getMatrixIndex(int circularIndex) {
    if (circularIndex >= 0 && circularIndex < rowLength) {
      return [1, circularIndex];
    } else {
      return [0, 2 * rowLength - 1 - circularIndex];
    }
  }

En appliquant le même changement de variable on retrouve aisément ces expressions également.

A partir du vecteur il est également possible de récupérer les lignes de notre matrice. Il n’y aura pas de formules cette fois je vous promet !

/// Retourne la seconde ligne de la matrice
  /// (celle du bas)
  List<int> getRow1() {
    return buffer.sublist(0, rowLength);
  }

/// Retourne la première ligne de la matrice
  /// (celle du haut)
  List<int> getRow0() {
    return buffer.sublist(rowLength, 2 * rowLength).reversed.toList();
  }

getRow0 retourne la ligne du haut, et getRow1 retourne la ligne du bas. La ligne du haut doit être renversée et vous devez savoir pourquoi, si vous êtes arrivé jusqu’ici dans la lecture. 😉

Voilà on a tout ce qu’il nous faut, on peut maintenant, sereinement aborder l’implémentation de notre simulation.

Implémentation de la distribution des graines

On implémente l’algorithme de distribution des graines dans la classe d’état de jeu comme suit :

/// Effectue un jeu pour le joueur [player] à l'emplacement [cavityIndex]
  /// Sur un jeu ayant pour matrice circulaire [circularMatrix]
  /// Et retourne le dernier emplacement
  int _distributeHand(
    CircularMatrix circularMatrix,
    GamePlayer player,
    int cavityIndex,
  ) {
    int row = player == GamePlayer.p1 ? 0 : 1;
    int startIndex = circularMatrix.getCircularIndex(row, cavityIndex);
    int hand = circularMatrix.buffer[startIndex];
    circularMatrix.buffer[startIndex] = 0;
    int index = startIndex;

// Distribuer la main en sautant la case de début
    while (hand != 0) {
      index = (index + 1) % circularMatrix.buffer.length;
      if (index != startIndex) {
        circularMatrix.buffer[index]++;
        hand--;
      }
    }
    return index;
  }

L’algorithme reçoit la matrice circulaire, le joueur qui joue et l’indice, le numéro de la case à partir duquel il joue. Il commence par déterminer l’indice du vecteur de jeu, puis l’algorithme se lance comme vu précédemment.

Implémentation de la recupération des gains

La récupération des gains est un peu plus vilaine à regarder:

/// Determine les gains du joueur [player] ayant joué, à partir du dernier index [lastIndex] et
  /// de la dernière ligne [lastRow].
  /// Et retourne une liste avec
  /// [0] => les gains du joueur 1
  /// [1] => les gains du joueur 2
  List<int> _computeGains(
    CircularMatrix circularMatrix,
    GamePlayer player,
    int lastCircularIndex,
  ) {
    int index = lastCircularIndex;
    final [lastRow, _] = circularMatrix.getMatrixIndex(lastCircularIndex);
    int gains = 0;
// retourne vrai si la position est gagnante
    isGaining(int idx) =>
        circularMatrix.buffer[idx] == 2 || circularMatrix.buffer[idx] == 3;
    // Le premier joueur termine t-il sur la zone du second joueur ?
    bool isPlayer1Jackpot = player == GamePlayer.p1 && lastRow == 1;
    // Le second joueur termine t-il sur la zone du premier joueur ?
    bool isPlayer2Jackpot = player == GamePlayer.p2 && lastRow == 0;
    if (!isPlayer1Jackpot && !isPlayer2Jackpot) {
      return [0, 0];
    }
    bool sameRow = true;
    bool gaining = true;
    do {
      final [row, _] = circularMatrix.getMatrixIndex(index);
      sameRow = row == lastRow;
      gaining = isGaining(index);
      if (sameRow && gaining) {
        gains += circularMatrix.buffer[index];
        circularMatrix.buffer[index] = 0;
        --index;
        if (index < 0) {
          // si on sors par le debut on retourne à la fin
          index = circularMatrix.buffer.length - 1;
        }
      }
    } while (sameRow && gaining);
    return [
      isPlayer1Jackpot ? gains : 0,
      isPlayer2Jackpot ? gains : 0,
    ];
  }

J’espère que les commentaires vous aideront à mieux comprendre tout le reste, reste l’algorithme qu’on à déja vu plus haut.

Je vous conseille vivement de d’implémenter vous même ces méthodes avec votre langage favori, vos noms de variables, et de méthodes pour mieux comprendre.

Implémentation de la fonction de simulation

La fonction de simulation dans toute son innocence:

/// Effectue la simulation d'un jeu du joueur [player]
  /// Dans la cavité ayant pour index [cavityIndex]
  /// et retourne le nouvel état de jeu
  GameState simulate(GamePlayer player, int cavityIndex) {
    CircularMatrix circularMatrix = CircularMatrix.from2Rows(p1pad, p2pad);
  // Distribuer la main
    int lastCircularIndex =
        _distributeHand(circularMatrix, player, cavityIndex);
    // Recupérer les gains
    final [p1gains, p2gains] =
        _computeGains(circularMatrix, player, lastCircularIndex);
    return GameState(
      p1pad: circularMatrix.getRow0(),
      p2pad: circularMatrix.getRow1(),
      p1points: p1points + p1gains,
      p2points: p2points + p2gains,
    );
  }

Implémentation de l’algorithme Alpha Béta

Vu que nous disposons de nos heuristiques, correctement implémentés, on peut se lancer dans l’implémentation de la recherche MinMax couplée au hack Alpha Béta pour que notre ordinateur puisse jouer intelligemment à l’Awalé avec nous.

On commence par créer une classe qui contiendra les paramètres de l’IA:

const __infinty = 0xFFFFFFFF; // (2^32 - 1)
const __invalidMove = -100; // Mouvement invalide

class AlphaBetaContext {
  GameState currentState;
  GamePlayer mainPlayer;
  int maxDepth;
  AlphaBetaContext({
    required this.currentState,
    required this.mainPlayer,
    required this.maxDepth,
  });

On défini deux constantes:

• La première symbolise plus l’infini nécessaire pour le fonctionnement du MinMax, j’ai choisi personnellement la valeur max qu’on peut avoir sur 32 bits, je doutes que vous ayez un jour besoin de faire des fonctions d’évaluation qui retournent des valeurs > 2³²— 1 même si vous faites une IA pour les échecs. 😅
• La seconde permet de représenter un mouvement, un jeu invalide, c’est utile pour notre implémentation du MinMax

Puis après on défini les paramètres de l’IA:

• L’état actuel du jeu
• Le joueur principal, celui qui est piloté par l’IA
• La profondeur de l’arbre de recherche MinMax.

Minute papillon !

Avant de pouvoir implémenter les algorithmes de recherche, et leurs vilaines récursivités mutuelles, on a besoin d’une méthode au niveau de l’état du jeu qui retourne les jeux possibles pour un joueur par rapport à l’état actuel. Chaque jeu possible est représenté par chaque case non vide devant le joueur concerné.

/// Retourne les mouvements possibles pour le joueur [player]
  List<int> getAvailableMoves(GamePlayer player) {
    if (player == GamePlayer.p1) {
      return List.generate(p1pad.length, (index) => index)
          .where((index) => p1pad[index] > 0)
          .toList();
    } else {
      return List.generate(p2pad.length, (index) => index)
          .where((index) => p2pad[index] > 0)
          .toList();
    }
  }

On retourne juste les index jouables, pour le joueur actuel donné.

Implémentation de l’algorithme Alpha Béta

Bon maintenant le saint Graal, les algorithmes de recherche:

Le minimum

/// Algorithme min-max couplé au hack alpha-beta
  /// [state] est l'état actuel du jeu
  /// [depth] est la profondeur
  /// [alpha] le paramètre alpha
  /// [beta] le paramètre beta
  List<int> _min(GameState state, int depth, int alpha, int beta, int moveNo) {
    int bestMoveValue = __infinty;
    int bestMoveId = __invalidMove;
    List<int> availableMoves = getAvailableMoves(state, mainPlayer);
    if (depth == maxDepth || availableMoves.isEmpty) {
      return [moveNo, state.evaluate(mainPlayer)];
    }
    for (int move in availableMoves) {
      GameState simulated = state.simulate(mainPlayer, move);
      final [_, moveValue] = _max(simulated, depth + 1, alpha, beta, move);
      if (moveValue < bestMoveValue) {
        bestMoveValue = moveValue;
        bestMoveId = move;
      }
      beta = min(beta, bestMoveValue);
      if (beta <= alpha) {
        // hack: alpha beta pruning
        break;
      }
    }
    return [bestMoveId, bestMoveValue];
  }

Ici on retourne le mouvement et son coût au lieu de retourner juste le coût comme on le voit dans la plupart des pseudo code par rapport à alpha béta.

Le maximum

/// Algorithme min-max couplé au hack alpha-beta
  /// [state] est l'état actuel du jeu
  /// [depth] est la profondeur
  /// [alpha] le paramètre alpha
  /// [beta] le paramètre beta
List<int> _max(GameState state, int depth, int alpha, int beta, int moveNo) {
    int bestMoveValue = -__infinty;
    int bestMoveId = __invalidMove;
    GamePlayer oppositePlayer = _opposite(mainPlayer);
    List<int> availableMoves = getAvailableMoves(state, oppositePlayer);
    if (depth == maxDepth || availableMoves.isEmpty) {
      return [moveNo, state.evaluate(mainPlayer)];
    }
    for (int move in availableMoves) {
      GameState simulated = state.simulate(oppositePlayer, move);
      final [_, moveValue] = _min(simulated, depth + 1, alpha, beta, move);
      if (moveValue > bestMoveValue) {
        bestMoveValue = moveValue;
        bestMoveId = move;
      }
      alpha = max(alpha, bestMoveValue);
      if (beta <= alpha) {
        // hack: alpha beta pruning
        break;
      }
    }
    return [bestMoveId, bestMoveValue];
  }

Le lancement:

/// Retourne le meilleur mouvement à réaliser
  int guessBestMove() {
    final [move, _] =
        _min(currentState, 0, -__infinty, __infinty, __invalidMove);
    return move;
  }

Les autres méthodes

/// Retourne le joueur opposant le joueur [player]
  GamePlayer _opposite(GamePlayer player) {
    return player == GamePlayer.p1 ? GamePlayer.p2 : GamePlayer.p1;
  }
/// Retourne la liste des mouvement possibles rangées
  /// aléatoirement ou non
  List<int> getAvailableMoves(GameState state, GamePlayer player) {
    List<int> moves = state.getAvailableMoves(player);
    return moves;
  }

Si vous connaissez bien les algorithmes Alpha Béta, les codes-ci ne devraient pas vous effrayer. Vous devez avoir appréhendé, apprivoisé, la récursivité mutuelle qui est utilisée ici et qui rend tout ça assez intimidant.

Peut-on jouer maintenant ?

Déjà félicitations si vous êtes arrivé jusqu’ici, vous avez mérité une petite fonction main() qui vous permettra de jouer tranquillement contre votre ordinateur :

/// Affiche l'état du jeu à la console
void displayGameState(GameState state) {
  final table0 = Table();
  for (var c in List.generate(state.p1pad.length, (index) => "($index)")) {
    table0.insertColumn(header: c);
  }
  table0.insertColumn(header: "P");
  table0.insertRows([
    [...state.p1pad, "p1"],
    [...state.p2pad, "p2"],
  ]);
print(table0);
  final table1 = Table()
    ..insertColumn(header: "Gains p1")
    ..insertColumn(header: "Gains p2")
    ..insertRow([state.p1points, state.p2points]);
  print(table1);
}
void main(List<String> arguments) {
  final cl = Console();
  cl.clearScreen();
  print("Bienvenue dans le simulateur de l'awalé");
  GameState state = GameState.start(6);
  GamePlayer player = GamePlayer.p2;
  GamePlayer opposite = player == GamePlayer.p2 ? GamePlayer.p1 : GamePlayer.p2;
  while (true) {
    displayGameState(state);
    print(
        "\r [${player.name}] Choisissez une case [0-${state.p1pad.length - 1}] (-1 pour quitter) : ");
    int move = int.parse(cl.readLine() ?? '0');
    if (move == -1) {
      break;
    }
    state = state.simulate(player, move);
    AlphaBetaContext aiContext = AlphaBetaContext(
      currentState: state,
      mainPlayer: opposite,
      maxDepth: 10,
    );
    int bestAIMove = aiContext.guessBestMove();
    print("L'IA à joue la case N°$bestAIMove !");
    state = state.simulate(opposite, bestAIMove);
  }
}

Le resultat

Bienvenue dans le simulateur de l'awalé
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 4   │ 4   │ 4   │ 4   │ 4   │ 4   │ p1 │
│ 4   │ 4   │ 4   │ 4   │ 4   │ 4   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 0        │ 0        │
╰──────────┴──────────╯
 [p2] Choisissez une case [0-5] (-1 pour quitter) : 
0
L'IA à joue la case N°5 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 4   │ 5   │ 5   │ 5   │ 5   │ 0   │ p1 │
│ 0   │ 5   │ 5   │ 5   │ 5   │ 4   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 0        │ 0        │
╰──────────┴──────────╯
 [p2] Choisissez une case [0-5] (-1 pour quitter) : 
2
L'IA à joue la case N°5 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 4   │ 5   │ 5   │ 5   │ 7   │ 0   │ p1 │
│ 0   │ 5   │ 0   │ 6   │ 6   │ 5   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 0        │ 0        │
╰──────────┴──────────╯
 [p2] Choisissez une case [0-5] (-1 pour quitter) : 
1
L'IA à joue la case N°2 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 5   │ 6   │ 0   │ 5   │ 7   │ 1   │ p1 │
│ 1   │ 1   │ 0   │ 7   │ 7   │ 6   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 2        │ 0        │
╰──────────┴──────────╯
 [p2] Choisissez une case [0-5] (-1 pour quitter) : 
4
L'IA à joue la case N°1 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 7   │ 0   │ 1   │ 6   │ 8   │ 2   │ p1 │
│ 2   │ 2   │ 1   │ 8   │ 1   │ 8   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 2        │ 0        │
╰──────────┴──────────╯
 [p2] Choisissez une case [0-5] (-1 pour quitter) : 
1
L'IA à joue la case N°3 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 8   │ 1   │ 2   │ 0   │ 8   │ 2   │ p1 │
│ 3   │ 1   │ 0   │ 9   │ 1   │ 8   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 5        │ 0        │
╰──────────┴──────────╯
 [p2] Choisissez une case [0-5] (-1 pour quitter) :

L’IA joue comme étant le joueur 1.

Personnellement je la trouve assez difficile à battre(je lui ai donné comme profondeur 10, pour réduire la difficulté vous pouvez diminuer ce nombre), et vu que je ne suis pas un pro de l’Awalé vous seul vous pouvez juger, à vous de jouer !

Conclusion

Je tiens sincèrement à vous remercier, et à vous féliciter si vous êtes arrivé jusqu’ici. Si cet article vous à enseigné quelque chose, si vous en avez tiré des leçons, je m’en réjouis. 🤓🤓

Les codes sources du simulateur sont disponibles ici:

https://github.com/momole02/awale-flutter.git

Vous pouvez le cloner et l’utiliser sous les termes de la licence GNU GPL.