IA de jeux, Implémenter un Puissance 4, en C++

Voir aussi : video youtube - video peertube - code source

Cet article, de la série “IA de jeux”, aborde l’implémentation d’un Puissance 4, en C++. Il rappelle d’abord les règles du jeu, les fonctionnalités à implémenter et les difficultés à prévoir. Il propose ensuite une implémentation, relativement simple et efficace. Enfin, il montre comment tester cette implémentation avec des tests unitaires.

Articles de la séries IA de jeux :

Généralités

Le jeu de Puissance 4

Le Puissance 4 est un jeu abstrait à 2 joueurs (Rouge et Jaune). Alternativement, chaque joueur fait tomber un pion de sa couleur dans l’une des colonnes du plateau de jeu vertical. Le premier joueur qui aligne 4 pions (en ligne, en colonne ou en diagonal) gagne. Si le plateau est rempli, il y a égalité.

Fonctionnalités à implémenter

L’implémentation doit permettre de connaitre l’état du jeu courant : le status (Rouge doit jouer, Rouge a gagné, etc), le joueur courant, les coups possibles, le plateau de jeu.

On doit également pouvoir jouer un coup. Par exemple, en indiquant la colonne à jouer, ou le numéro du coup voulu parmi les “coups possibles”.

Enfin, on doit pouvoir passer à la partie suivante (en changeant le joueur qui commence).

Ces fonctionnalités permettront de réaliser une interface utilisateur mais également d’implémenter des IA.

Difficultés

Tout d’abord, on doit gérer un plateau de jeu à deux dimensions (6 lignes et 7 colonnes). Il y a plusieurs façons d’implémenter un tableau 2D en C++ (tableau de tableaux, tableau 1D avec calcul d’indice, bibliothèques spécifiques), chacune avec leurs avantages et inconvénients.

L’exécution d’un coup n’est pas complètement triviale car on doit “faire tomber le pion”. Par exemple, si Rouge joue la colonne 0 sur le jeu suivant :

0123456
.......
.......
.......
R...Y..
R...Y..
R...Y..
moves: 0 1 2 3 4 5 6
status: PlayR

j ? 0

alors il faut remplir la case de la ligne 3 (les lignes vont de 0 à 6, de bas en haut).

0123456
.......
.......
R......
R...Y..
R...Y..
R...Y..
moves: 
status: WinR

De mème, la détection de victoire pose quelques questions. Par exemple, on peut tester le plateau complet, ce qui permet de tester n’importe quel plateau donné. Mais on peut également essayer de réduire les calculs en considérant uniquement les voisins de la case jouée, car une case déjà jouée ne change plus d’état dans le reste de la partie de jeu.

Enfin, il faut également prendre en compte quelques difficultés habituelles mais importantes ici. Par exemple, on va essayer d’avoir du code robuste pour éviter de mélanger les différentes notions (joueur, status, coup, case du plateau…). De même, on va essayer d’avoir du code suffisamment performant et générique pour pouvoir implémenter des IA.

Implémentation

L’implémentation proposée ici est un compromis de simplicité, de lisibilité et de performance. Elle peut très certainement être améliorée de nombreuses façons.

Types de base

On définit 3 types pour représenter : le contenu d’une case du plateau (Cell), le joueur (Player) et le status du jeu (Status).

// Game.hpp

enum class Cell { E, R, Y };  // Empty, Red, Yellow
enum class Player { R, Y };   // Red, Yellow
enum class Status { PlayR, PlayY, Tie, WinR, WinY };

Cell player2cell(Player p);
Player nextPlayer(Player p);

Ici les enum class ont l’avantage de rendre le code lisible et robuste. Par exemple, la valeur “Rouge” a un sens et une utilisation différents si on parle d’un joueur (Player::R) ou d’une case du plateau (Cell::R).

La fonction player2cell permet de trouver la valeur d’une case correspondant à un joueur donné. La fonction nextPlayer permet de passer au joueur suivant (pour le coup suivant ou pour la partie suivante).

// Game.cpp

Cell player2cell(Player p) {
    return p == Player::R ? Cell::R : Cell::Y;
}

Player nextPlayer(Player p) {
    return p == Player::R ? Player::Y : Player::R;
}

Plateau de jeu

Le plateau du Puissance 4 a des tailles constantes. On peut donc les mettre dans des constantes globales et définir le plateau avec un tableau statique de tableaux statiques (de Cell). Pour simplifier le code, on définit un alias board_t pour ce type.

// Game.hpp

const int NI = 6;
const int NJ = 7;

using board_t = std::array<std::array<Cell, NJ>, NI>;

extern const board_t CELLS;

Implémenter un tableau 2D par un tableau de tableaux a l’avantage de simplifier l’accès aux éléments car on a naturellement un indexage 2D. En revanche, la construction de tableau de tableaux est généralement plus compliquée mais dans notre cas on construit simplement un plateau statique initialisé à Cell::E. On peut même définir le plateau initial dans une constante globale, qu’on copiera ensuite pour initialiser les jeux.

// Game.cpp

const board_t CELLS({Cell::E});

Jeu

Classe Game

La classe Game permet de représenter et de gérer un jeu de Puissance 4. Elle contient notamment le plateau, le tableau des coups possibles, le status courant, le joueur courant et le joueur qui a commencé la partie.

// Game.hpp

class Game {
    private:
        board_t _cells;
        std::vector<int> _moves;
        Status _status;
        Player _currentPlayer;
        Player _firstPlayer;

    public:
        Game();
        void newGame();
        void playK(int k);
        Player getCurrentPlayer() const;
        const std::vector<int> & getMoves() const;
        Cell getCell(int i, int j) const;
        Status getStatus() const;
        bool isRunning() const;

    private:
        bool checkIJ(int i, int j) const;
        int length(int i0, int j0, int di, int dj) const;
        bool checkLine(int i0, int j0, int di, int dj) const;
};

Les méthodes implémentent les fonctionnalités demandées ou nécessaires au fonctionnement interne de la classe. Elles sont expliquées ci-dessous.

Construction

La méthode newGame permet de réinitialiser un nouveau jeu, en changeant le joueur qui commence. Pour le plateau, il suffit de copier la constante globale CELLS. Pour les coups possibles, il s’agit initialement des numéros de colonne, donc de 0 à 6. Enfin, pour le joueur initial, on alterne le joueur initial de la partie précédente, ce qui permet aussi d’initialiser le nouveau joueur courant et status courant.

// Game.cpp

void Game::newGame() {
    _cells = CELLS;
    _moves.clear();
    for (int k=0; k<NJ; k++)
        _moves.push_back(k);
    _firstPlayer = nextPlayer(_firstPlayer);
    _currentPlayer = _firstPlayer;
    _status = _currentPlayer == Player::R ? Status::PlayR : Status::PlayY;
}

Pour construire le premier jeu, il suffit d’initialiser le joueur initial et de faire un appel à newGame. On peut également réserver la mémoire nécessaire pour stocker les coups possibles car le Puissance 4 ne peut jamais avoir plus de coups possibles que le nombre de colonnes.

// Game.cpp

Game::Game() : _firstPlayer(Player::Y) {
    _moves.reserve(NJ);
    newGame();
}

Accesseurs

Les différents accesseurs permettent de connaitre l’état du jeu, ce qui sera nécessaire pour l’interface utilisateur et pour les IA.

// Game.cpp

Player Game::getCurrentPlayer() const {
    return _currentPlayer;
}

const std::vector<int> & Game::getMoves() const {
    return _moves;
}

Cell Game::getCell(int i, int j) const {
    return _cells[i][j];
}

Status Game::getStatus() const {
    return _status;
}

bool Game::isRunning() const {
    return _status == Status::PlayR or _status == Status::PlayY;
}

On notera que, comme l’accès public au plateau se fait par un accesseur (getCell), on peut changer son implémentation sans avoir à changer les codes utilisateurs (interface utilisateur, IA).

Jouer un coup

La plus grosse difficulté du Puissance 4 est de jouer un coup, et en particulier de détecter les alignements. Comme on ne fait que remplir des cases sans les changer ensuite, on peut détecter les alignements à partir de la case jouée et en regardant uniquement les alignements possibles à partir de cette case.

On définit donc une méthode length qui calcule le nombre de voisins de la case (i0, j0) dans la direction (di, dj) et de même valeur.

// Game.cpp

int Game::length(int i0, int j0, int di, int dj) const {
    Cell c = _cells[i0][j0];
    int l = 0;
    int i = i0 + di;
    int j = j0 + dj;
    while (checkIJ(i, j) and _cells[i][j] == c) {
        l++;
        i += di;
        j += dj;
    }
    return l;
}

bool Game::checkIJ(int i, int j) const {
    return i>=0 and i<NI and j>=0 and j<NJ;
}

La méthode checkLine permet alors de tester la ligne complète, en appelant length dans la direction de la ligne et dans la direction opposée.

// Game.cpp

bool Game::checkLine(int i0, int j0, int di, int dj) const {
    int l = length(i0, j0, di, dj) + length(i0, j0, -di, -dj);
    return l >= 3;
}

On peut alors implémenter la méthode playK, qui joue le coup d’indice k dans le tableau des coups possibles. Pour cela, on détermine la colonne j correspondante, puis la ligne i de la case vide la plus basse. On remplit la case trouvée et on cherche les alignements dans les 4 directions. S’il n’y a pas de victoire, on recalcule les coups possibles (c’est-à-dire les colonnes ayant au moins la dernière ligne de vide) et on passe au joueur suivant, sauf en cas d’égalité (plus aucun coup possible).

// Game.cpp

void Game::playK(int k) {
    // find and play cell
    const int j0 = _moves[k];
    int i0 = NI;
    while (i0>0 and _cells[i0-1][j0] == Cell::E)
        i0--;
    _cells[i0][j0] = player2cell(_currentPlayer);

    // update status/current/moves
    _moves.clear();
    if (checkLine(i0, j0, 0, 1) 
            or checkLine(i0, j0, 1, 0) 
            or checkLine(i0, j0, 1, 1) 
            or checkLine(i0, j0, 1, -1)) {
        _status = _currentPlayer == Player::R ? Status::WinR : Status::WinY;
    }
    else {
        // update moves
        for (int j=0; j<NJ; j++) {
            if (_cells[NI-1][j] == Cell::E)
                _moves.push_back(j);
        }

        if (_moves.empty()) {
            _status = Status::Tie;
        }
        else {
            _currentPlayer = nextPlayer(_currentPlayer);
            _status = _currentPlayer == Player::R ? Status::PlayR : Status::PlayY;
        }
    }
}

Tests unitaires

Pour tester notre implémentation de Puissance 4, on pourrait écrire une interface utilisateur qui fait jouer 2 joueurs, en saisissant alternativement les coups au clavier. Cependant, ceci nécessite du code supplémentaire et ne permet pas de tester le code facilement : il faut vérifier les résultats manuellement, il faut exécuter les différentes situations de jeu possibles, les erreurs potentielles sont difficiles à localiser…

Une autre solution serait d’écrire un programme qui appelle les différentes fonctions et affichent les résultats. Ceci permet de résoudre une bonne partie des inconvénients précédents mais nécessite toujours de vérifier les résultats manuellement.

Principe et utilisation

Le principe des tests unitaires est d’exécuter et de vérifier automatiquement un ensemble de scénarios de test. Prenons, par exemple, la fonction mul2 suivante.

int mul2(int x) { return x * 2; }

Cette fonction est censée multiplier un entier par 2. Par exemple, elle doit retourner la valeur 42 pour le paramètre 21 et la valeur 0 pour le paramètre 0.

Les tests unitaires permettent de réaliser ces vérifications automatiquement. Par exemple avec la bibliothèque GoogleTest, on écrit des fonctions de test contenant chacune un scénario (ici, appeler la fonction mul2 sur un paramètre particulier) et ses assertions (le résultat attendu après l’exécution du scénario).

#include <gtest/gtest.h>

TEST( mul2, test_1 ) {
    ASSERT_EQ(42, mul2(21));
}

TEST( mul2, test_2 ) {
    ASSERT_EQ(0, mul2(0));
}

int main(int argc, char** argv) {
  ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}

Pour lancer les tests, il suffit ensuite de compiler et d’exécuter le programme de test.

$ make tests2.out 
g++ -Wall -Wextra -std=c++17 -O3   -c -o tests2.o tests2.cpp
g++ -Wall -Wextra -std=c++17 -O3 -o tests2.out tests2.o -lgtest

$ ./tests2.out
[==========] Running 2 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 2 tests from mul2
[ RUN      ] mul2.test_1
[       OK ] mul2.test_1 (0 ms)
[ RUN      ] mul2.test_2
[       OK ] mul2.test_2 (0 ms)
[----------] 2 tests from mul2 (0 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test suite ran. (0 ms total)
[  PASSED  ] 2 tests.

Ainsi, on peut écrire une multitude de tests pour couvrir une bonne partie du code. Les vérifications sont faites automatiquement, ce qui évite les erreurs et permet de détecter facilement l’apparition de nouvelles erreurs lors de modifications de code existant (régression de code). Les tests unitaires sont un outil classique trés intéressant pour tester du code efficacement et précocement (Test-Driven Development).

Tests unitaires et droits d’accès

Les tests unitaires sont plutôt prévus pour tester les fonctionnalités publiques d’une classe (approche “boite-noire”), mais on peut également les utiliser pour tester le fonctionnement interne d’une classe. Soit, par exemple, la classe MyClass suivante.

class MyClass {
    protected:
        int _a;
        int mul2() { return _a * 2; }

    public:
        MyClass(int a) : _a(a) {}
};

Si on veut accéder à l’attribut _a et à la méthode mul2 (non publics donc) dans les tests unitaires, on peut dériver une classe de test qui réexporte publiquement les membres à vérifier, puis tester cette classe de test.

class MyClassTest : public MyClass {
    public:
        MyClassTest(int a) : MyClass(a) {}

        using MyClass::_a;
        using MyClass::mul2;
};

TEST( MyClass, test_1 ) {
    MyClassTest c(21);
    ASSERT_EQ(21, c._a);
    ASSERT_EQ(42, c.mul2());
}

Attention cependant : ces tests sont alors dépendants de l’implémentation interne de la classe, ce qui est discutablement une bonne idée.

Tester l’implémentation de Puissance 4

On peut donc écrire des tests unitaires pour notre code de Puissance 4. Certains tests sont triviaux mais peu coûteux à écrire et peuvent tout de même éviter des erreurs d’inattention.

TEST( Game, player2cell_1 ) {
    ASSERT_EQ(Cell::R, player2cell(Player::R));
    ASSERT_EQ(Cell::Y, player2cell(Player::Y));
}

TEST(Game, nextPlayer_1 ) {
    ASSERT_EQ( Player::Y, nextPlayer(Player::R) );
    ASSERT_EQ( Player::R, nextPlayer(Player::Y) );
}

A l’opposée, on peut également tester exhaustivement des scénarios de jeu réalistes.

void assert_board(const board_t & expected, const Game & game) {
    for (int i=0; i<NI; i++)
        for (int j=0; j<NJ; j++)
            ASSERT_EQ( expected[i][j], game.getCell(i, j) );
}

void playMoves(Game & game, const std::vector<int> & moves) {
    for (int k : moves) {
        ASSERT_TRUE(game.isRunning());
        ASSERT_TRUE(k >= 0);
        ASSERT_TRUE(k < int(game.getMoves().size()));
        game.playK(k);
    }
}

// ...

// red column
TEST( Game, playK_4 ) {
    Game game;
    const std::vector<int> moves {0, 4, 0, 4, 0, 4, 0};
    playMoves(game, moves);

    const board_t expectedBoard {{
        {Cell::R, Cell::E, Cell::E, Cell::E, Cell::Y, Cell::E, Cell::E},
        {Cell::R, Cell::E, Cell::E, Cell::E, Cell::Y, Cell::E, Cell::E},
        {Cell::R, Cell::E, Cell::E, Cell::E, Cell::Y, Cell::E, Cell::E},
        {Cell::R, Cell::E, Cell::E, Cell::E, Cell::E, Cell::E, Cell::E},
        {Cell::E, Cell::E, Cell::E, Cell::E, Cell::E, Cell::E, Cell::E},
        {Cell::E, Cell::E, Cell::E, Cell::E, Cell::E, Cell::E, Cell::E}
    }};
    const std::vector<int> expectedMoves {};

    assert_board(expectedBoard, game);
    ASSERT_EQ(Player::R, game.getCurrentPlayer());
    ASSERT_EQ(Status::WinR, game.getStatus());
    ASSERT_EQ(false, game.isRunning());
    ASSERT_EQ(expectedMoves, game.getMoves());
}

Conclusion

Dans cet article, on a vu comment implémenter un Puissance 4, qu’on pourra ensuite utiliser avec des IA ou avec une interface utilisateur. Pour cela, on a identifié les fonctionnalités importantes (connaitre l’état du jeu, jouer un coup, passer à la partie suivante) ainsi que les principales difficultés (implémenter un plateau 2D, réaliser un coup, détecter les fins de parties, etc). Enfin, on a vu comment utiliser un système de tests unitaires pour tester le fonctionnement de notre implémentation facilement.

Dans le prochain article, on verra comment implémenter des IA basiques et une interface utilisateur qui utilisent cette implémentation de Puissance 4.