IA de jeux, Implémenter une IA basique, en C++

Voir aussi : video youtube - video peertube - code source

Cet article, de la série “IA de jeux”, aborde la mise en place d’une intelligence artificielle. Il se base sur le jeu de Puissance 4 implémenté dans l’article précédent mais doit pouvoir s’appliquer facilement à d’autres jeux ou implémentations. Enfin, seules quelques IA simples sont présentées ici, ainsi que leur utilisation dans une interface utilisateur ou dans un programme de comparaison. Une IA plus évoluée sera détaillée dans le prochain article.

Articles de la séries IA de jeux :

Introduction

Implémenter un Puissance 4, en C++

Implémenter une IA basique, en C++

Implémenter une IA arborescente, en C++

Performances de code, en C++

Implémenter un Puissance 4, en Haskell

Implémenter une IA basique, en Haskell

Implémenter une IA arborescente, en Haskell

Performances de code, en Haskell

Conclusion

Architecture de Bot

Rappel sur la classe Game

En simplifiant, notre jeu de Puissance 4 possède des méthodes publiques pour créer/initialiser un jeu, identifier/jouer les coups, et connaitre l’état du jeu.

L’action d’un joueur se résume à choisir un coup parmi les coups possibles. Mais pour choisir plus intelligemment, on a besoin de connaitre plus finement l’état du jeu ou de pouvoir évaluer les coups, d’où les différentes méthodes de la classe Game.

Interface Bot

Pour implémenter des algorithmes d’IA (bots), on doit d’abord prévoir une architecture de code qui permette non seulement ces implémentations mais également de les utiliser facilement dans divers programmes (interface utilisateur, comparateur, etc).

Un bot est une fonction qui prend un Game en paramètre et retourne le numéro du coup choisi. Au lieu d’utiliser directement des fonctions, on peut définir une interface Bot avec une méthode virtuelle pure genmove.

// Bot.hpp

class Bot {
    public:
        virtual ~Bot() = default;
        virtual int genmove(const Game & game) = 0;
};

Pour implémenter nos différents bots, il suffira alors de dériver, de Bot, une classe qui redéfinit genmove.

Cette architecture permet d’ajouter des attributs et des méthodes spécifiquement à chaque bot, en fonction de l’algorithme qu’il implémente. Elle permet également d’avoir une interface commune, pour les programmes utilisateurs.

Bot de test

Pour commencer à implémenter notre architecture de Bot, on peut écrire un bot de test, qui choisit toujours le premier coup.

// Bot.hpp

class BotZero : public Bot {
    public:
        int genmove(const Game & game) override;
};

// Bot.cpp

int BotZero::genmove(const Game &) {
    return 0;
}

On va également avoir besoin de dérouler une partie de jeu, où un premier bot joue Rouge et un second bot joue Jaune. Pour cela, on écrit la fonction playoutBots suivante.

// Bot.cpp

void playoutBots(Game & game, Bot & botR, Bot & botY) {
    while (game.isRunning()) {
        Bot & bot = game.getCurrentPlayer() == Player::R ? botR : botY;
        const int k = bot.genmove(game);
        game.playK(k);
    }
}

On peut alors déjà tester deux BotZero l’un contre l’autre. Quand les bots choisissent toujours le premier coup possible, le premier joueur gagne. Par exemple, si Rouge commence, on obtient le résulat suivant.

0123456
YYY....
RRR....
YYY....
RRR....
YYY....
RRRR...
moves:
status: WinR

Si on déroule des parties de jeu, avec deux BotZero et en alternant le joueur qui commence, alors on devrait avoir 50% de victoire pour Rouge, 50% de victoire pour Jaune et aucune égalité. On peut donc tester ce scénario avec un test unitaire.

// tests.cpp

TEST( BotZero, genmove_1 ) {
    Game game;
    BotZero botR;
    BotZero botY;

    const int N = 100;
    int nbR = 0;
    int nbY = 0;
    int nbT = 0;

    for (int i=0; i<N; i++) {
        playoutBots(game, botR, botY);
        switch (game.getStatus()) {
            case Status::WinR: nbR++; break;
            case Status::WinY: nbY++; break;
            case Status::Tie: nbT++; break;
            default: FAIL();
        }
        game.newGame();
    }

    ASSERT_NEAR(0.5, nbR/double(N), 0.01);
    ASSERT_NEAR(0.5, nbY/double(N), 0.01);
    ASSERT_NEAR(0.0, nbT/double(N), 0.01);
}

Interface utilisateur

On veut maintenant écrire un programme qui permet de faire jouer des bots ou des humains au Puissance 4.

Afficher et dérouler des jeux

Tout d’abord, on a besoin de pouvoir afficher un jeu, notamment le plateau, les coups possibles et le status. Pour cela, on définit les fonctions suivantes.

// cli.cpp

char formatCell(Cell c) {
    switch (c) {
        case Cell::E: return '.';
        case Cell::R: return 'R';
        case Cell::Y: return 'Y';
        default: abort();
    }
}

std::string formatStatus(Status s) {
    switch (s) {
        case Status::PlayR: return "PlayR";
        case Status::PlayY: return "PlayY";
        case Status::Tie: return "Tie";
        case Status::WinR: return "WinR";
        case Status::WinY: return "WinY";
        default: abort();
    }
}

void printGame(const Game & game) {
    std::cout << '\n';
    for (int j=0; j<NJ; j++)
        std::cout << j;
    for (int i=NI-1; i>=0; i--) {
        std::cout << '\n';
        for (int j=0; j<NJ; j++) {
            Cell c = game.getCell(i, j);
            std::cout << formatCell(c);
        }
    }
    std::cout << "\nmoves:";
    for (int j : game.getMoves())
        std::cout << ' ' << j;
    std::cout << "\nstatus: " << formatStatus(game.getStatus()) << std::endl;
}

On peut ensuite écrire le programme principal de notre interface utilisateur. Il s’agit tout simplement de créer un jeu et deux bots puis de dérouler la partie avec la fonction playoutBots. A la fin de la partie, on affiche le résultat et on demande s’il faut recommencer une autre partie.

// cli.cpp

int main() {
    BotZero botR;
    BotZero botY;

    Game game;
    char newgame = 'y';
    while (newgame == 'y') {
        playoutBots(game, botR, botY);
        printGame(game);
        std::cout << "new game (y/n) ? ";
        std::cin >> newgame;
        game.newGame();
    }

    return 0;
}

Avec deux bots de test BotZero, on obtient alternativement les résultats déjà présentés.

$ ./cli.out 

0123456
YYY....
RRR....
YYY....
RRR....
YYY....
RRRR...
moves:
status: WinR
new game (y/n) ? y

0123456
RRR....
YYY....
RRR....
YYY....
RRR....
YYYY...
moves:
status: WinY
new game (y/n) ?

Joueur humain

Notre architecture de bot permet d’implémenter un joueur humain assez naturellement : il suffit de dériver un bot dont la méthode genmove demande à l’utilisateur de saisir le coup au clavier. Pour simplifier l’utilisation, on demande de saisir la colonne à jouer et on appelle la fonction j2k pour trouver le numéro du coup correspondant.

// cli.cpp

class BotHuman : public Bot {
    public:
        int genmove(const Game & game) override {
            printGame(game);
            std::cout << "\nj ? ";
            int j;
            std::cin >> j;
            return j2k(game, j);
        }
};

int j2k(const Game & game, int j) {
    auto moves = game.getMoves();
    auto iter = std::find(moves.begin(), moves.end(), j);
    assert(iter != moves.end());
    return std::distance(moves.begin(), iter);
}

Exemple d’exécution, avec un BotZero (Rouge) contre un BotHuman (Jaune) :

$ ./cli.out 

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

j ? 2

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

j ?

Bot aléatoire

On veut maintenant écrire un bot qui choisit un coup aléatoirement parmi les coups possibles.

Gestion de l’aléatoire

Génerer des nombres aléatoires correctement et efficacement est une vraie problématique mais pour nos bots, on se contentera des fonctionnalités fournies par la bibliothèque standard du C++. On définit un alias de type random_t ainsi qu’une fonction random qui génère un entier strictement inférieur à un entier donné et selon la loi uniforme.

// Bot.hpp

using random_t = std::mt19937;

// Bot.cpp

int random(random_t & rng, int n) {
    std::uniform_int_distribution<int> dist(0, n-1);
    return dist(rng);
}

Cette fonction repose entièrement sur la bibliothèque standard C++ mais on peut tout de même écrire quelques tests unitaires, pour vérifier que son utilisation est correcte. On peut notamment tester le domaine, l’espérance et la distribution.

// tests.cpp

TEST( BotRandom, random_1 ) {
    const int N = 100;
    random_t rng(std::random_device{}());
    for (int i=0; i<N; i++) {
        const int x = random(rng, 10);
        ASSERT_TRUE(x >= 0);
        ASSERT_TRUE(x < 10);
    }
}

TEST( BotRandom, random_2 ) {
    const int N = 10000;
    random_t rng(std::random_device{}());
    int sum = 0;
    for (int i=0; i<N; i++) {
        sum += random(rng, 11);
    }
    const double avg = sum / double(N);
    ASSERT_NEAR(5, avg, 0.1);
}

TEST( BotRandom, random_3 ) {
    const int N = 10000;
    random_t rng(std::random_device{}());
    std::vector<int> hist(10, 0);
    for (int i=0; i<N; i++) {
        const int x = random(rng, 10);
        hist[x]++;
    }
    for (int h : hist) {
        const double freq = h / double(N);
        ASSERT_NEAR(0.1, freq, 0.05);
    }
}

Bot random

On peut maintenant écrire facilement un bot qui joue aléatoirement : on met un générateur aléatoire en attribut, ce qui nous permet d’appeler la fonction random lorsque qu’on doit choisir un coup à jouer parmi les coups possibles.

// Bot.hpp

class BotRandom : public Bot {
    private:
        random_t _rng;

    public:
        BotRandom();
        int genmove(const Game & game) override;
};

// Bot.cpp

BotRandom::BotRandom() : _rng(std::random_device{}()) {}

int BotRandom::genmove(const Game & game) {
    const int nMoves = game.getMoves().size();
    return random(_rng, nMoves);
}

Pour tester, on peut faire jouer deux BotRandom l’un contre l’autre : chacun aura environ une chance sur deux de gagner.

// tests.cpp

TEST( BotRandom, genmove_1 ) {
    Game game;
    BotRandom botR;
    BotRandom botY;

    const int N = 1000;
    int nbR = 0;
    int nbY = 0;
    int nbT = 0;

    for (int i=0; i<N; i++) {
        playoutBots(game, botR, botY);
        switch (game.getStatus()) {
            case Status::WinR: nbR++; break;
            case Status::WinY: nbY++; break;
            case Status::Tie: nbT++; break;
            default: FAIL();
        }
        game.newGame();
    }

    ASSERT_NEAR(0.5, nbR/double(N), 0.05);
    ASSERT_NEAR(0.5, nbY/double(N), 0.05);
    ASSERT_NEAR(0.0, nbT/double(N), 0.05);
}

Bot Monte-Carlo

La méthode de Monte-Carlo consiste à estimer l’espérance d’une fonction d’une variable aléatoire par la moyenne de cette fonction sur des réalisations de la variable.

Ici, la variable aléatoire correspond à terminer la partie de Puissance 4 en jouant aléatoirement,

// Bot.cpp

Status playoutRandom(Game & game, random_t & rng) {
    while (game.isRunning()) {
        const int k = random(rng, game.getMoves().size());
        game.playK(k);
    }
    return game.getStatus();
}

Et la fonction est un score associé au résultat de la partie.

// Bot.cpp

double computeScore(Status s, Player p) {
    if ((s == Status::WinR and p == Player::R) or (s == Status::WinY and p == Player::Y))
        return 1.0;
    if (s == Status::Tie)
        return 0.5;
    return 0.0;
}

Ainsi, pour un jeu donné, on peut estimer le score espéré de chaque coup en simulant de nombreuses parties aléatoires après le coup et en calculant le score moyen. Pour implémenter un tel bot, on a besoin d’un générateur aléatoire (pour jouer les parties aléatoires) et du nombre de simulations à faire pour estimer chaque coup.

// Bot.hpp

class BotMc : public Bot {
    private:
        random_t _rng;
        const int _nSimsPerMove;

    public:
        BotMc(int nSimsPerMove);
        int genmove(const Game & game) override;

    protected:
        double evalMove(const Game & game, int k);
};

La méthode evalMove joue un coup donné puis réalise les simulations de Monte-Carlo et calcule le score moyen (ou, plus simplement, la somme des scores). La méthode genmove évalue tous les coups possibles, en utilisant evalMove, et choisit le meilleur.

// Bot.cpp

BotMc::BotMc(int nSimsPerMove) : 
    _rng(std::random_device{}()), 
    _nSimsPerMove(nSimsPerMove) 
{}

int BotMc::genmove(const Game & game) {
    const int nMoves = game.getMoves().size();
    int bestK = 0;
    double bestScore = 0.0;
    for (int k=0; k<nMoves; k++) {
        const double score = evalMove(game, k);
        if (score > bestScore) {
            bestScore = score;
            bestK = k;
        }
    }
    return bestK;
}

double BotMc::evalMove(const Game & game, int k) {
    const Player player = game.getCurrentPlayer();
    Game g1(game);
    g1.playK(k);
    double score = 0.0;
    for (int n=0; n<_nSimsPerMove; n++) {
        Game g(g1);
        Status status = playoutRandom(g, _rng);
        score += computeScore(status, player);
    }
    return score;
}

Comparer des bots

Il ne nous reste plus qu’à comparer des bots. Pour cela, la fonction run suivante fait jouer un bot Rouge et un bot Jaune sur un nombre donné de parties, et retourne le pourcentage de victoire de Rouge, le pourcentage de victoire de Jaune, le pourcentage d’égalité et le temps d’exécution.

// cmp.hpp

std::tuple<double, double, double, double> run(Bot & botR, Bot & botY, int nGames) {

    auto t0 = std::chrono::steady_clock::now();

    int nWinR = 0;
    int nWinY = 0;
    int nTie = 0;

    Game game;
    for (int n=0; n<nGames; n++) {
        playoutBots(game, botR, botY);
        switch (game.getStatus()) {
            case Status::WinR: nWinR++; break;
            case Status::WinY: nWinY++; break;
            case Status::Tie: nTie++; break;
            default: abort();
        }
        game.newGame();
    }

    const double nGamesD = nGames;
    const double winR = nWinR / nGamesD;
    const double winY = nWinY / nGamesD;
    const double tie = nTie / nGamesD;

    auto t1 = std::chrono::steady_clock::now();
    const double dt = std::chrono::duration<double>(t1 - t0).count();

    return { winR, winY, tie, dt };
}

Pour tester l’influence d’un paramètre d’un bot (par exemple, le nombre de simulations de Monte-Carlo pour BotMc), on définit une fonction test1 qui contruit un bot Rouge avec différentes valeurs de paramètres données, et les compare à un bot Jaune donné. Les résultats sont écrits dans un fichier CSV.

// cmp2.cpp

void test1(const std::string & name, int nGames,
        std::function<std::unique_ptr<Bot>(int)> mkBot,
        std::unique_ptr<Bot> & botY,
        std::vector<int> values) {

    std::cout << name << std::endl;
    std::ofstream ofs("out-test1-" + name + ".csv");
    ofs << "winR winY tie ry ryt dt nGames value\n";
    for (int value : values) {
        auto botR = mkBot(value);
        auto [ winR, winY, tie, dt ] = run(*botR, *botY, nGames);
        ofs << winR << ' ' << winY << ' ' << tie << ' ' 
            << winR+winY << ' ' << winR+winY+tie << ' ' 
            << dt << ' ' << nGames << ' ' << value << '\n';
    }
}

Ainsi on peut comparer, par exemple, différents paramétrages de BotMc avec un BotRandom ou avec un BotMc à 32 simulations par coup.

// cmp2.cpp

int main() {
    auto mkBotMc = [](int v){ return std::make_unique<BotMc>(v);};

    std::unique_ptr<Bot> botRandom = std::make_unique<BotRandom>();
    std::unique_ptr<Bot> botMc32 = std::make_unique<BotMc>(32);

    const int nGames = 300;

    test1("McX-Random", nGames, mkBotMc, botRandom, {1, 2, 4, 8, 16, 32, 64});

    test1("McX-Mc32", nGames, mkBotMc, botMc32, {4, 8, 16, 32, 64});

    return 0;
}

Par exemple, pour la comparaison avec BotRandom, on obtient un CSV comme celui-ci :

$ cat out-test1-McX-Random.csv 
winR winY tie ry ryt dt nGames value
0.78 0.21 0 1 1 0.026664 300 1
0.85 0.15 0 1 1 0.057693 300 2
0.92 0.07 0 1 1 0.116663 300 4
0.97 0.02 0 1 1 0.263468 300 8
0.98 0.01 0 1 1 0.501452 300 16
1 0 0 1 1 0.964974 300 32
0.99 0.01 0 1 1 1.81586 300 64

Avec un peu de shell et de gnuplot, on peut générer un graphique de ces données.

#!/bin/sh

FILES=$(find . -maxdepth 1 -name "out-test*.csv")

for file in ${FILES} ; do

    name="${file%.*}"
    echo "plotting ${name}"

    gnuplot -e "set out '${name}.png'; \
        set terminal png size 640,360; \
        set title '${name}.png'; \
        plot '${name}.csv' using 8:1 notitle with filledcurve x1 lc rgb 'red', \
        '' using 8:1:4 notitle with filledcurves lc rgb 'yellow', \
        '' using 8:4:5 notitle with filledcurve lc rgb 'blue'"

done

Pour McX contre Random, on remarque bien que Monte-Carlo est beaucoup plus efficace que Random.

Rouge : McX gagne. Jaune : Random gagne. Bleu : égalité.

Pour McX contre Mc32, on remarque que Monte-Carlo s’améliore en fonction du nombre de simulations. On a des résultats comparables quand les deux bots sont à 32 simulations puis Rouge prend l’avantage à 64 simulations contre 32. On remarque également qu’on commence à avoir des égalités, ce qui semble indiquer que les deux bots jouent suffisamment bien pour arriver à terminer des parties sans perdre.

Rouge : McX gagne. Jaune : Mc32 gagne. Bleu : égalité.

Conclusion

Dans cet article, on a vu qu’implémenter une IA pour un Puissance 4 se résume à coder une fonction qui choisit un coup à jouer, pour un jeu donné. Pour des algorithmes sans connaissance experte, comme Random ou Monte-Carlo, on n’a même pas besoin de connaitre en détail l’état du jeu. En architecturant soigneusement les bots, on peut également implémenter un joueur humain et une interface utilisateur, ou encore un programme de comparaison d’IA.

L’algorithme de Monte-Carlo commence à donner des résultats intéressants mais l’article suivant présentera un algorithme plus efficace, basé sur une recherche arborescente.