Minimax pour Puissance 4

Version imprimable

Bonjour tout le monde !

Je n'arrive pas à appliquer le principe du minimax pour un jeu de puissance 4. J'ai tenté d'implémenter l'algorithme tel qu'il est présenté sur ce site (qui l'st pour un morpion) mais il ne fonctionne pas.
Voici mon code commenté, j'espère que vous pourrez m'aider à trouver la solution (la partie non commentée fonctionne parfaitement, le joueur humain est le joueur 1 et le joueur IA est le joueur 2).

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <vector>
 
using namespace std;
 
void printGame(vector< vector<int> > game);
char coin(int player)    {return (player == 1 ? '1' : (player == 2 ? '2' : ' '));}
int checkEnded(vector< vector<int> > game);
bool play(vector< vector<int> > game, int column, int player);
int robotGo(vector< vector<int> > game);
int calcMax(vector< vector<int> > game, int depth);
int calcMin(vector< vector<int> > game, int depth);
 
int main()
{
    vector< vector<int> > game(7, vector<int>(6, 0));
    printGame(game);
 
    int winner;
    bool robot = false;
 
    while((winner = checkEnded(game)) < 0)
    {
        int column = 0;
        if(robot)    column = robotGo(game);
        else    cout << endl << "Where play ? ", cin >> column, column--;
 
        for(int i = 0; i < 6; i++)    if(game[column][i] == 0)    { game[column][i] = (robot ? 2 : 1); break; }
 
        printGame(game);
 
        robot = !robot;
    }
 
    switch(winner)
    {
        case 0 : cout << endl << "Match nul" << endl; break;
        case 1 : cout << endl << "Gagne !!!" << endl; break;
        case 2 : cout << endl << "Perdu !!!" << endl; break;
    }
 
    cin.get();
    return 0;
}
 
void printGame(vector< vector<int> > game)
{
    system("cls"), cout << "  1   2   3   4   5   6   7" << endl << endl;
    for(int i = 5; i >= 0; i--)
    {
        cout << "| " << coin(game[0][i]) << " | " << coin(game[1][i]) << " | " << coin(game[2][i]) << " | " << coin(game[3][i]) << " | "
        << coin(game[4][i]) << " | " << coin(game[5][i]) << " | " << coin(game[6][i]) << " |" << endl << "+---+---+---+---+---+---+---+" << endl;
    }
}
 
int checkEnded(vector< vector<int> > game)
{
    for(int i = 0; i < 7; i++)    for(int j = 0; j < 3; j++)    for(int p = 1; p < 3; p++)
        if(game[i][j] == p && game[i][j + 1] == p && game[i][j + 2] == p && game[i][j + 3] == p)    return p;
    for(int i = 0; i < 4; i++)    for(int j = 0; j < 6; j++)    for(int p = 1; p < 3; p++)
        if(game[i][j] == p && game[i + 1][j] == p && game[i + 2][j] == p && game[i + 3][j] == p)    return p;
    for(int i = 0; i < 4; i++)    for(int j = 0; j < 3; j++)    for(int p = 1; p < 3; p++)
        if(game[i][j] == p && game[i + 1][j + 1] == p && game[i + 2][j + 2] == p && game[i + 3][j + 3] == p)    return p;
    for(int i = 0; i < 4; i++)    for(int j = 3; j < 6; j++)    for(int p = 1; p < 3; p++)
        if(game[i][j] == p && game[i + 1][j - 1] == p && game[i + 2][j - 2] == p && game[i + 3][j - 3] == p)    return p;
    for(int i = 0; i < 7; i++)    for(int j = 0; j < 6; j++)    if(game[i][j] == 0)    return -1;
    return 0;
}
 
bool play(vector< vector<int> > game, int column, int player)
{
    // On joue sur la première case de la colonne qui est vide. Si on ne peut pas, on retourne faux
    for(int i = 0; i < 5; i++)    if(game[column][i] == 0)    {game[column][i] = player; return true;}
    return false;
}
 
int robotGo(vector< vector<int> > game)
{
    // On initialise le meilleur coup (score minimum, première colonne)
    int max = -1, best = 0;
    // Pour tous les coups
    for(int i = 0; i < 7; i++)
    {
        // On fait une copie du jeu
        vector< vector<int> > tmpGame = game;
        if(play(tmpGame, i, 2))
        {
            // Si on peut jouer le coup, on calcul son score
            int tmp = calcMax(tmpGame, 3);
            // Si le score est meilleur que le précédant, on l'enregistre
            if(tmp > max)    { max = tmp; best = i; }
        }
    }
    // On retourne le meilleur coup trouvé
    return best;
}
 
int calcMax(vector< vector<int> > game, int depth)
{
    // Si le noeud est une feuille ou si le jeu est fini, on retourne 1 si on a gagné, -1 si l'adversaire a gagné ou 0 si il n'y a pas de gagnant
    int winner = checkEnded(game);
    if(depth == 0 || winner > -1)    return winner == 1 ? -1 : (winner == 2 ? 1 : 0);
 
    // On initialise le score : minimum
    int max = -1;
    // Pour tous les coups suivants
    for(int i = 0; i < 7; i++)
    {
        // On fait une copie du jeu
        vector< vector<int> > tmpGame = game;
        if(play(tmpGame, i, 2))
        {
            // Si on peut jouer le coup, on calcul son score
            int tmp = calcMin(tmpGame, depth - 1);
            // Si le score est meilleur que le précédant, on l'enregistre
            if(tmp > max)    max = tmp;
        }
    }
    // On retourne le score
    return max;
}
 
int calcMin(vector< vector<int> > game, int depth)
{
    // Si le noeud est une feuille ou si le jeu est fini, on retourne 1 si on a gagné, -1 si l'adversaire a gagné ou 0 si il n'y a pas de gagnant
    int winner = checkEnded(game);
    if(depth == 0 || winner > -1)    return winner == 1 ? -1 : 1;
 
    // On initialise le score : minimum
    int min = 1;
    // Pour tous les coups suivants
    for(int i = 0; i < 7; i++)
    {
        // On fait une copie du jeu
        vector< vector<int> > tmpGame = game;
        if(play(tmpGame, i, 1))
        {
            // Si on peut jouer le coup, on calcul son score
            int tmp = calcMax(tmpGame, depth - 1);
            // Si le score est meilleur que le précédant, on l'enregistre
            if(tmp < min)    min = tmp;
        }
    }
    // On retourne le score
    return min;
}

Merci d'avance !

26/03/2010, 00h08
Epsilon012

Tu as plusieurs problemes dans ton code :

Tout d'abbord ta fonction robotGo est en fait une fonction max, elle prend bien le maximum, mais elle choisie ses coups après le jeu de max.. hors c'est au tour de min...
Dans robotGo change tmp = calcMax(blabla) par tmp = calcMin(blabla).

Ton return dans CalcMin, devrait être le même que dans CalcMax, quoi en fait avec une profondeur de 4 demi coups (donc argument 3 pour calcMin dans robotGo), depth sera toujours positif dans min, mais dans quel cas ton depth==0 est innutile, si tu veux que ton code fonctionne avec toutes les profondeurs possibles, change ton return dans calcMin.

Enfin, il te faut faire des progrès en C++ (je te conseille le livre de Stroustrup qui est très complet). En effet tu passe tes vectors par copie, même à la fonction play, du coup tes "prévisions" de coups ne sont pas vraiment réalisé sur tes variables tmpGame, pour le coriger, tu dois faire un passage d'argument par référence, la déclaration de play devient alors :
bool play(vector< vector<int> >& game, int column, int player);

Salut. Merci beaucoup d'avoir pris le temps d'étudier mon code.

C'est vrai que ce n'est pas très logique d'appeler calcMax dans robotGo, mais c'est ce qui est fait dans http://fearyourself.developpez.com/tutoriel/sdl/morpion/part6/ ^^

Par contre je n'ai pas très bien compris l'histoire du retour de calcMin.

Et pour les problèmes avec le c++, le truc c'est que je programme principalement en C sur micro-contrôleur (ceci sera l'intelligence artificielle d'un robot qui joue au puissance 4...). J'ai simplement utiliser le c++ ici car il me permettait de ne pas m'embêter avec les tableaux (les vectors sont plus simples à gérer) et me focaliser sur l'algorithme.

Voilà où en est mon code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <vector>
 
using namespace std;
 
void printGame(vector< vector<int> > game);
char coin(int player)    {return (player == 1 ? '1' : (player == 2 ? '2' : ' '));}
int checkEnded(vector< vector<int> > game);
bool play(vector< vector<int> >& game, int column, int player);
int robotGo(vector< vector<int> > game);
int calcMax(vector< vector<int> > game, int depth);
int calcMin(vector< vector<int> > game, int depth);
 
int main()
{
    vector< vector<int> > game(7, vector<int>(6, 0));
    printGame(game);
 
    int winner;
    bool robot = false;
 
    while((winner = checkEnded(game)) < 0)
    {
        int column = 0;
        if(robot)    column = robotGo(game);
        else    cout << endl << "Where play ? ", cin >> column, column--;
 
        for(int i = 0; i < 6; i++)    if(game[column][i] == 0)    { game[column][i] = (robot ? 2 : 1); break; }
 
        printGame(game);
 
        robot = !robot;
    }
 
    switch(winner)
    {
        case 0 : cout << endl << "Match nul" << endl; break;
        case 1 : cout << endl << "Gagne !!!" << endl; break;
        case 2 : cout << endl << "Perdu !!!" << endl; break;
    }
 
    cin.get();
    return 0;
}
 
void printGame(vector< vector<int> > game)
{
    system("cls"), cout << "  1   2   3   4   5   6   7" << endl << endl;
    for(int i = 5; i >= 0; i--)
    {
        cout << "| " << coin(game[0][i]) << " | " << coin(game[1][i]) << " | " << coin(game[2][i]) << " | " << coin(game[3][i]) << " | "
        << coin(game[4][i]) << " | " << coin(game[5][i]) << " | " << coin(game[6][i]) << " |" << endl << "+---+---+---+---+---+---+---+" << endl;
    }
}
 
int checkEnded(vector< vector<int> > game)
{
    for(int i = 0; i < 7; i++)    for(int j = 0; j < 3; j++)    for(int p = 1; p < 3; p++)
        if(game[i][j] == p && game[i][j + 1] == p && game[i][j + 2] == p && game[i][j + 3] == p)    return p;
    for(int i = 0; i < 4; i++)    for(int j = 0; j < 6; j++)    for(int p = 1; p < 3; p++)
        if(game[i][j] == p && game[i + 1][j] == p && game[i + 2][j] == p && game[i + 3][j] == p)    return p;
    for(int i = 0; i < 4; i++)    for(int j = 0; j < 3; j++)    for(int p = 1; p < 3; p++)
        if(game[i][j] == p && game[i + 1][j + 1] == p && game[i + 2][j + 2] == p && game[i + 3][j + 3] == p)    return p;
    for(int i = 0; i < 4; i++)    for(int j = 3; j < 6; j++)    for(int p = 1; p < 3; p++)
        if(game[i][j] == p && game[i + 1][j - 1] == p && game[i + 2][j - 2] == p && game[i + 3][j - 3] == p)    return p;
    for(int i = 0; i < 7; i++)    for(int j = 0; j < 6; j++)    if(game[i][j] == 0)    return -1;
    return 0;
}
 
bool play(vector< vector<int> >& game, int column, int player)
{
    // On joue sur la première case de la colonne qui est vide. Si on ne peut pas, on retourne faux
    for(int i = 0; i < 5; i++)    if(game[column][i] == 0)    {game[column][i] = player; return true;}
    return false;
}
 
int robotGo(vector< vector<int> > game)
{
    // On initialise le meilleur coup (score minimum, première colonne)
    int min = 1, best = 0;
    // Pour tous les coups
    for(int i = 0; i < 7; i++)
    {
        // On fait une copie du jeu
        vector< vector<int> > tmpGame = game;
        if(play(tmpGame, i, 2))
        {
            // Si on peut jouer le coup, on calcul son score
            int tmp = calcMin(tmpGame, 3);
            // Si le score est meilleur que le précédant, on l'enregistre
            if(tmp < min)    { min = tmp; best = i; }
        }
    }
    // On retourne le meilleur coup trouvé
    return best;
}
 
int calcMax(vector< vector<int> > game, int depth)
{
    // Si le noeud est une feuille ou si le jeu est fini, on retourne 1 si on a gagné, -1 si l'adversaire a gagné ou 0 si il n'y a pas de gagnant
    int winner = checkEnded(game);
    if(depth == 0 || winner > -1)    return winner == 1 ? -1 : (winner == 2 ? 1 : 0);
 
    // On initialise le score : minimum
    int max = -1;
    // Pour tous les coups suivants
    for(int i = 0; i < 7; i++)
    {
        // On fait une copie du jeu
        vector< vector<int> > tmpGame = game;
        if(play(tmpGame, i, 2))
        {
            // Si on peut jouer le coup, on calcul son score
            int tmp = calcMin(tmpGame, depth - 1);
            // Si le score est meilleur que le précédant, on l'enregistre
            if(tmp > max)    max = tmp;
        }
    }
    // On retourne le score
    return max;
}
 
int calcMin(vector< vector<int> > game, int depth)
{
    // Si le noeud est une feuille ou si le jeu est fini, on retourne 1 si on a gagné, -1 si l'adversaire a gagné ou 0 si il n'y a pas de gagnant
    int winner = checkEnded(game);
    if(depth == 0 || winner > -1)    return winner == 1 ? -1 : 1;
 
    // On initialise le score : minimum
    int min = 1;
    // Pour tous les coups suivants
    for(int i = 0; i < 7; i++)
    {
        // On fait une copie du jeu
        vector< vector<int> > tmpGame = game;
        if(play(tmpGame, i, 1))
        {
            // Si on peut jouer le coup, on calcul son score
            int tmp = calcMax(tmpGame, depth - 1);
            // Si le score est meilleur que le précédant, on l'enregistre
            if(tmp < min)    min = tmp;
        }
    }
    // On retourne le score
    return min;
}

L'IA semble éviter tous les coups qui la feraient gagner ainsi que ceux qui m'empêcheraient de gagner ...

26/03/2010, 14h19
Epsilon012

Ta fonction robotGo est une fonction max ! (elle choisie le meilleur coup possible) Elle doit être exactement la même que calcMax avec une variable en plus pour savoir quel coup jouer.
Or dans ton nouveau code, tu appelles bien calcMin dans robotGo, mais tu choisie le min... c'est l'inverse, tu dois appeler calcMin, mais tu dois choisir le « max des calcMin ».

Pour le return dans calcMin, suppose que tu ais mis dans robotGo « int tmp = calcMin(tmpGame, 4) », c'est à dire que tu prevois un demi coup supplémentaire. On a donc:
- calcMin recoit un depth de 4.
- Et appelle calcMax avec un depth de 3.
- Qui appelle calcMin un depth de 2.
- Puis calcMax un depth de 1
- Puis enfin calcMin depth de 0.
Donc, ligne 127 de ton code :
if(depth == 0 || winner > -1) return winner == 1 ? -1 : 1;
depth == 0 est true, donc le return est appellé, mais si winner=-1 ou winner=0 (pas de gagnant), il y a un return 1;. Cette mauvaise estimation pourrait conduire ton AI à choisir un coup sous optimal, en fait ce return pourrait cacher un coup qui te ferais gagner.
26/03/2010, 14h47
Electroniktor

Salut. Merci pour ces explications.

Le problème du return, je l'avais vu mais je ne l'avais corrigé que dans calclMax, j'avais oublié calcMin, c'est pour ça que je ne comprenais pas.
En tout cas tout fonctionne parfaitement maintenant !

Il me reste plus qu'a choisir aléatoirement le coup à jouer parmi les meilleurs trouvés, optimiser (éviter les copies inutiles ^^), convertir en C ou en java pour mon micro-contrôleur et essayer de battre mon robot !

Je pensais faire une fonction d'évaluation plus élaborée, mais le simple fait d'analyser si il y a un gagnant ou pas a l'air de suffire amplement !

En tout cas je te remercie beaucoup pur ton aide ! :ccool: