Problème jeu d'othello

Bonjour a tous,

Voila comme l'indique l'intitule du post, je suis actuellement en train de developper un jeu d'othello en C++. Le rendu visuel ne se fait que par console.

Le plan de jeu est represente par un tableau d'entier a deux dimensions de longueur 10, car je represente les bords du jeu par des -1. L'ordinateur joue les X, et l'adversaire, par consequent, les O.

Voici le header de ma classe Othello :

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
 
/* 
 * File:   Othello.h
 * Author: V
 *
 * Created on August 28, 2010, 7:20 PM
 */
 
#ifndef _OTHELLO_H
#define	_OTHELLO_H
#include <vector>
#include <iostream>
#include "Tree.h"
#include "Node.h"
using namespace std;
 
 
#endif	/* _OTHELLO_H */
 
class Othello1 {
 
private:
 
    /*****VARIABLES*****/
 
    static const int dim = 10; //definition de la taille de notre tableau a 2 dimensions
    static const int empty_cell = 0; //definition des cases vides
    static const int side_cell = -1; //definition des bords externes du plan du jeu
 
    static const int possible_directions[8][2]; // les 8 directions possibles a parcourir
 
    static const int corners[4][2];
 
    const static int corner_bonus = 10;
    const static int good_cell_bonus = 5;
 
    int othello[dim][dim]; // 8 x 8 plus les bords, 1 a gauche, 1 a droite, 1 en haut et 1 en bas
    int tmp_othello[dim][dim];
 
    int moveHistory[64][3]; //tableau a 3 dimensions de longueur max 64, qui contient le joueur, l'abscisse x jouee et l'ordonnee y jouee.
    int moveCount;
 
    int tree_of_level[][3]; //arbre du niveau, chaque cle comporte 4 elements : le niveau de jeu, la valeur evaluee de la position, l'abscisse et l'ordonnee de la position.
 
    int final_tree[][3]; //arbre final, chaque cle comporte 4 elements :le niveau de jeu,  la valeur evaluee de la position, l'abscisse x et l'ordonnee y.
 
    int current_player;
 
    int playerScore;
    int computerScore;
 
    int depth;       //profondeur de niveau actuelle
 
    int maxDepth;    //profondeur de niveau maximale
 
    int alpha;
 
    int beta;
 
    int bestMove[2];    //tableau ou l'on stock les meilleurs positions a jouer pour l'ordi
 
    /*****METHODES*****/
 
    vector<vector<int> > Othello1::GetAllPlayablePositionsForPlayer(const int player, int board[dim][dim]);
 
    bool Othello1::isGoodPosition(int x_pos, int y_pos);
 
    bool Othello1::isEndGame(int board[dim][dim]);
 
    int Othello1::Transform(int board[dim][dim], const int player, const int x_pos, const int y_pos);
 
    /***********************************************
     ****FONCTIONS ET METHODES DESTINEES A L'IA*****
     ************************************************/
 
    int Othello1::Minimax_AlphaBetaPruning(Node node, int depth, int alpha, int beta);
 
    Tree Othello1::GenerateTree(int level);
 
    Tree Othello1::GenerateTreeToLevel(int level);
 
    int Othello1::EvaluateTreeLeaf(int player, int board[dim][dim], int x_pos, int y_pos);
 
    vector<vector<int> > Othello1::GetBestMoveForCPU();
 
 
public:
    /*****definition des joueurs*****/
    static const int O_disc = 1; //definition des pions blancs
    static const int X_disc = 2; //definition des pions noirs
 
    Othello1::Othello1();
    void Othello1::Test_othello();
    void Othello1::Display();
    bool Othello1::IsPlayable(const int player, const int x_pos, const int y_pos, int board[dim][dim]);
 
    int Othello1::GetNextPlayer();
 
    void Othello1::GetHumanMove(const int player, const int x_pos, const int y_pos);
    void Othello1::GetComputerMove(const int player);
 
    int Othello1::CountDiscsForPlayer(int player, int board[dim][dim]);
};

Les cases vides sont representees par des 0.
Les cases detenues par l'ordi sont representees par des 2 et les cases de l'adversaire par des 1.

static const int possible_directions[8][2] : represente les 8 directions possibles de jeu.
int othello[dim][dim] : represente le plan de jeu

Deux methodes sont tres importantes :

La 1ere

bool Othello1::IsPlayable(const int player, const int x_pos, const int y_pos, int board[dim][dim]) : renvoi un boolean qui teste si une position est jouable ou non pour le parametre "player".

Voici le code de cette fonction :

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
 
bool Othello1::IsPlayable(const int player, const int x_pos, const int y_pos, int board[dim][dim])
{
    /*****Test 1 : on verifie que les coordonnees sont bien celle d'une case vide *****/
    if ( board[x_pos][y_pos] != empty_cell ) return false;
 
    int other_player = O_disc;
    if (player == O_disc) other_player = X_disc;
 
    int mult = 2; /*facteur s'appliquant au tableau des directions --> permet d'analyser si un ou plusieurs
                    adversaires sont coinces entre deux de nos pions*/
 
    int pawn_t; // permet de comparer la case a jouer et la couleur du pion qui doit etre joue.
 
    /*****Test 2 : boucle autour des positions dans les 8 directions où le pion doit être un adversaire*****/
    for ( int dir = 0 ; dir < 8 ; dir++ )
    {
        if ( board[x_pos + possible_directions[dir][0]][y_pos + possible_directions[dir][1]] == other_player)
        {
            for (;;)
            {
                /*****Test 3 : si un adversaire est voisin, redirection dans la diagonale *****/
                pawn_t = board[x_pos + (mult * possible_directions[dir][0])][y_pos + (mult * possible_directions[dir][1])];
 
                if ( pawn_t == player ) return true;
 
                /*****Test 4 : verifie si une case est vide ou si c'est un bord(-1) *****/
                if ( pawn_t != other_player ) break;
 
                mult++;
            }
        }
    }
 
    return false;
}

La 2nd

vector<vector<int> > Othello1::GetAllPlayablePositionsForPlayer(const int player, int board[dim][dim]) : qui renvoit un vecteur a deux dimensions de toutes les positions jouables pour le parametre "player".

Voici son 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
 
vector<vector<int> > Othello1::GetAllPlayablePositionsForPlayer(const int player, int board[dim][dim])
{
	int row, col;
 
        int posibilityCount = 0;
 
        std::string str = "";
 
	if (player == Othello1::X_disc)
        {
            str = "CPU";
        }
        else 
        {
            str = "Player";
        }
 
        for (row = 1 ; row < dim - 1 ; row++)
	{
            for (col = 1 ; col < dim - 1 ; col++)
            {
                if ( (board[row][col] == empty_cell) && (IsPlayable(player, row, col, board)) )
                {
                    posibilityCount++;
                }
            }
	}
 
        cout << endl;
 
        cout << str << " has " << posibilityCount << " playable positions " << endl << endl;
 
        //Creation du vecteur multi-dimensionnel
	vector<vector<int> > playablePositions;
 
        //Definition de la taille du vecteur general
        playablePositions.resize(posibilityCount);
 
        for (int k = 0 ; k < posibilityCount ; k++)
        {
            playablePositions[k].resize(2); //Definition de la taille des sous-vecteurs
        }
 
	//cout << "Possibilities for the " <<  str << " are : " << endl << endl;
 
        int i = 0;
 
	for (row = 1 ; row < dim - 1 ; row++)
	{
            for (col = 1 ; col < dim - 1 ; col++)
            {
                if ( (board[row][col] == empty_cell) && (IsPlayable(player, row, col, board)) )
                {
                    playablePositions[i][0] = row;
                    playablePositions[i][1] = col;
                    //cout <<  playablePositions[i][0] << " - " << playablePositions[i][1] << endl;
                    i++;
                }
            }
	}
 
	return playablePositions;
}

int Othello1::EvaluateTreeLeaf(int player, int board[dim][dim], int x_pos, int y_pos) : est une fonction qui, comme son nom l'indique, evalue les feuilles de l'arbre.

Mon but est de permettre de jouer contre l'ordi, mais de renvoyer pour chaque joueur quelle est la position optimale a jouer mais de rendre tout de meme l'ordi (theoriquement imbattable).

Mon probleme n'est pas l'implementation de l'algorithme MiniMax, mais plutot la construction et la generation de l'arbre de facon recursive et ensuite d'appeler ma fonction Minimax_alphaBetaPruning sur chaque noeud interne de l'arbre.

Pour ce faire, j'ai cree deux classes :

- Node
- Tree

Voici le header de la classe Node :

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
 
/* 
 * File:   Node.h
 * Author: V
 *
 * Created on November 13, 2010, 1:41 AM
 */
 
#ifndef _NODE_H
#define	_NODE_H
 
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;
 
 
#endif	/* _NODE_H */
 
class Node {
 
private:
 
    Node * pere;
    vector<Node> * fils;
 
    int level;
    int value;
    int x_pos;
    int y_pos;
    const string type;
 
    vector<int> nodeData;
 
public:
 
    Node::Node();
    Node::Node(Node pere, vector<Node> fils);
    Node::Node(Node pere, vector<Node> fils, int value, int x_pos, int y_pos, int level, string type);
    Node::Node(Node pere, vector<Node> fils, vector<int> data);
 
    void Node::SetPere(Node pere);
    Node * Node::GetPere();
 
    void Node::SetFils(vector<Node> fils);
    vector<Node> * Node::GetFils();
    void Node::AddFils(Node fils);
    void Node::AddFilsAt(int index, Node fils);
 
    void Node::SetValue(int value);
    int Node::GetValue();
 
    void Node::SetX_pos(int x_pos);
    int Node::GetX_pos();
 
    void Node::SetY_pos(int y_pos);
    int Node::GetY_pos();
 
    void Node::SetLevel(int level);
    int Node::GetLevel();
 
    void Node::SetType(string type);
    const string Node::GetType();
 
    void Node::SetNodeData(vector<int> data);
    vector<int> Node::GetNodeData();
 
    void Node::AddDataToNode(int data);
    void Node::AddDataToNode(int index, int data);
 
    bool Node::IsLeaf();
    bool Node::IsRoot();
};

Et voici le fichier source de la classe Node :

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
 
#include "Node.h"
 
Node::Node()
{
    this->pere = NULL;
 
    this->fils = NULL;
}
 
Node::Node(Node pere, vector<Node> fils)
{
    this->pere = &pere;
 
    this->fils = &fils;
}
 
Node::Node(Node pere, vector<Node> fils, int value, int x_pos, int y_pos, int level, string type)
{
    this->pere = &pere;
 
    this->fils = &fils;
 
    this->value = value;
 
    this->x_pos = x_pos;
 
    this->y_pos = y_pos;
 
    this->level = level;
 
    this->type = type;
}
 
Node::Node(Node pere, vector<Node> fils, vector<int> data)
{
    this->pere = &pere;
 
    this->fils = &fils;
 
    this->nodeData = data;
}
 
void Node::SetPere(Node pere)
{
    this->pere = &pere;
}
 
Node * Node::GetPere()
{
    return this->pere;
}
 
void Node::SetFils(vector<Node> fils)
{
    this->fils = &fils;
}
 
vector<Node> * Node::GetFils()
{
    return this->fils;
}
 
void Node::AddFils(Node fils)
{
    this->fils.push_back(fils);
}
 
void Node::AddFilsAt(int index, Node fils)
{
    this->fils.assign(index, fils);
}
 
void Node::SetValue(int value)
{
    this->value = value;
}
 
int Node::GetValue()
{
    return this->value;
}
 
void Node::SetX_pos(int x_pos)
{
    this->x_pos = x_pos;
}
 
int Node::GetX_pos()
{
    return this->x_pos;
}
 
void Node::SetY_pos(int y_pos)
{
    this->y_pos = y_pos;
}
 
int Node::GetY_pos()
{
    return this->y_pos;
}
 
void Node::SetLevel(int level)
{
    this->level = level;
}
 
int Node::GetLevel()
{
    return this->level;
}
 
void Node::SetType(string type)
{
    this->type = type;
}
 
const string Node::GetType()
{
    return this->type;
}
 
void Node::SetNodeData(vector<int> data)
{
    this->nodeData = data;
}
 
vector<int> Node::GetNodeData()
{
    return this->nodeData;
}
 
void Node::AddDataToNode(int data)
{
    this->nodeData.push_back(data);
}
 
void Node::AddDataToNode(int index, int data)
{
    this->nodeData.assign(index, data);
}
 
bool Node::IsLeaf()
{
    if ((this->fils == NULL) || (this->fils.size() == 0))
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
bool Node::IsRoot()
{
    if (this->pere == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

Voici le header de la classe Tree :

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
 
/* 
 * File:   Tree.h
 * Author: V
 *
 * Created on November 13, 2010, 1:41 AM
 */
 
#ifndef _TREE_H
#define	_TREE_H
#include <vector>
#include "Node.h"
 
 
 
#endif	/* _TREE_H */
 
class Tree{
 
private:
 
    vector<Node> nodeManager;
 
public:
 
    Tree::Tree();
    Tree::Tree(vector<Node> tree);
 
    void Tree::SetNodeManager(vector<Node> nodeManager);
    vector<Node> Tree::GetNodeManager();
 
    void Tree::AddNodeToTree(Node node);
    void Tree::AddNodeToTree(int index, Node node);
};

Voici le fichier source de la classe Tree :

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
 
#include "Tree.h"
 
Tree::Tree()
{
 
}
 
Tree::Tree(vector<Node> tree)
{
    this->nodeManager = tree;
}
 
void Tree::SetNodeManager(vector<Node> nodeManager)
{
    this->nodeManager = nodeManager;
}
 
vector<Node> Tree::GetNodeManager()
{
    return this->nodeManager;
}
 
void Tree::AddNodeToTree(Node node)
{
    this->nodeManager.push_back(node);
}
 
void Tree::AddNodeToTree(int index, Node node)
{
    this->nodeManager.assign(index, node);
}

Voici comment je m'y prend pour generer l'arbre :

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
 
Tree Othello1::GenerateTree(int level)
{
    Tree returnTree;
 
    int player = current_player;
 
    int next_player;
 
    if (player == X_disc)
    {
        next_player = O_disc;
    }
    else
    {
        next_player = X_disc;
    }
 
    vector<vector<int> > niveau0_playablePositions = GetAllPlayablePositionsForPlayer(player, othello);
 
    //On commence par parcourir toutes les racines possible;
 
    for (int i = 0 ; i < niveau0_playablePositions.size() ; i++)
    {
        /*Pour chaque racine on cree une copie de notre tableau
          pour commencer a simuler les prochaines positions de jeu*/
 
        int tmp_othello[dim][dim];
 
        for (int x = 0 ; x < dim ; x++)
        {
            for (int y = 0 ; y < dim ; y++)
            {
                tmp_othello[x][y] = othello[x][y];
            }
        }
 
        int x_pos = niveau0_playablePositions[i][0];
 
        int y_pos = niveau0_playablePositions[i][1];
 
        tmp_othello[x_pos][y_pos] = player;
 
        Transform(tmp_othello, player, x_pos, y_pos);
 
        vector<vector<int> > niveau1_playablePositions = GetAllPlayablePositionsForPlayer(next_player, tmp_othello);
 
        Node root = new Node();
 
        root.SetPere(NULL);
 
        root.SetX_pos(x_pos);
 
        root.SetY_pos(y_pos);
 
        if (player == X_disc)
        {
            root.SetType("MAX");
        }
        else
        {
            root.SetType("MIN");
        }
 
        int valeur = Minimax_AlphaBetaPruning(root, level - 1, alpha, beta);
 
        root.SetValue(valeur);
 
        for (int j = 0 ; j < niveau1_playablePositions.size() ; j++)
        {
            int x_pos1 = niveau1_playablePositions[j][0];
 
            int y_pos1 = niveau1_playablePositions[j][1];
 
            tmp_othello[x_pos1][y_pos1] = next_player;
 
            Transform(tmp_othello, next_player, x_pos1, y_pos1);
 
            vector<vector<int> > niveau2_playablePositions = GetAllPlayablePositionsForPlayer(player, tmp_othello);
 
            Node node = new Node();
 
            node.SetPere(root);
 
            node.SetX_pos(x_pos1);
 
            node.SetY_pos(y_pos1);
 
            if (next_player == O_disc)
            {
                node.SetType("MIN");
            }
            else
            {
                node.SetType("MAX");
            }
 
            int val = Minimax_AlphaBetaPruning(node, level - 1, alpha, beta);
 
            node.SetValue(val);
 
            root.AddFils(node);
 
            for (int k = 0 ; k < niveau2_playablePositions.size() ; k++)
            {
                int x_pos2 = niveau2_playablePositions[k][0];
 
                int y_pos2 = niveau2_playablePositions[k][1];
 
                tmp_othello[x_pos2][y_pos2] = player;
 
                Transform(tmp_othello, player, x_pos2, y_pos2);
 
                Node leaf = new Node();
 
                leaf.SetPere(node);
 
                leaf.SetX_pos(x_pos2);
 
                leaf.SetY_pos(y_pos2);
 
                if (player == X_disc)
                {
                    leaf.SetType("MAX");
                }
                else
                {
                    leaf.SetType("MIN");
                }
 
                int value = EvaluateTreeLeaf(player, tmp_othello, x_pos2, y_pos2);
 
                leaf.SetValue(value);
 
                node.AddFils(leaf);
 
                returnTree.AddNodeToTree(root);
 
                returnTree.AddNodeToTree(node);
 
                returnTree.AddNodeToTree(leaf);
            }
        }
    }
 
    return returnTree;
}
 
Tree Othello1::GenerateTreeToLevel(int level)
{
    Tree tree;
 
    if (level > 0)
    {
        tree = new Tree();
 
        tree = GenerateTree(level);
 
        tree = GenerateTreeToLevel(level - 1);
    }
 
    return tree;
}
 
int Othello1::Minimax_AlphaBetaPruning(Node node, int depth, int alpha, int beta)
{
    int tmp_othello[dim][dim];
 
    //Si le jeu est fini
    if (isEndGame(othello) || depth == 0)
    {
        if (computerScore > playerScore)
        {
            return computerScore;
        }
        else
        {
            return playerScore;
        }
    }
 
    //int bestScore;
 
    if (depth > 0)
    {
        if (node.GetType() == "MAX")
        {
            //bestScore = -INT_MAX;
 
            vector<vector<int> > playablePositions = GetAllPlayablePositionsForPlayer(X_disc, othello);
 
            for (int i = 0 ; i < playablePositions.size() ; i++)
            {
                for (int x = 0 ; x < dim ; x++)
                {
                    for (int y = 0 ; y < dim ; y++)
                    {
                        tmp_othello[x][y] = othello[x][y];
                    }
                }
 
                tmp_othello[playablePositions[i][0]][playablePositions[i][1]] = X_disc;
 
                Transform(tmp_othello, X_disc, playablePositions[i][0], playablePositions[i][1]);
 
                int score = Minimax_AlphaBetaPruning(depth - 1, alpha, beta);
 
                if (score > alpha)
                {
                    this->alpha = score;
 
                    bestMove[0] = playablePositions[i][0];
 
                    bestMove[1] = playablePositions[i][1];
 
                    if (alpha >= beta)
                    {
                        break;
                    }
 
                }
            }
        }
        else
        {
            //bestScore = INT_MAX;
 
            vector<vector<int> > playablePositions = GetAllPlayablePositionsForPlayer(O_disc, othello);
 
            for (int i = 0 ; i < playablePositions.size() ; i++)
            {
                for (int x = 0 ; x < dim ; x++)
                {
                    for (int y = 0 ; y < dim ; y++)
                    {
                        tmp_othello[x][y] = othello[x][y];
                    }
                }
 
                tmp_othello[playablePositions[i][0]][playablePositions[i][1]] = O_disc;
 
                Transform(tmp_othello, O_disc, playablePositions[i][0], playablePositions[i][1]);
 
                int score = Minimax_AlphaBetaPruning(depth - 1, alpha, beta);
 
                if (score < beta)
                {
                    this->beta = score;
 
                    bestMove[0] = playablePositions[i][0];
 
                    bestMove[1] = playablePositions[i][1];
 
                    if (alpha >= beta)
                    {
                        break;
                    }
                }
            }
 
            return beta;
        }
    }
}

int Othello1::Transform(int board[dim][dim], const int player, const int x_pos, const int y_pos) : cette fonction retourne les pions sur le plan de jeu et retourne le nombre de pion retourne pour le joueur "player".

Voila, je pense que quelque chose m'echappe, surtout au niveau de la generation de l'arbre recursivement jusqu'a n niveau de profondeur.

J'ai consulte le programme othello sur ce site, mais je galere toujours, j'ai aussi ete sur le site de la federation francaise de jeu d'othello.

Si certains points restent obscures je reste a votre entiere disposition pour plus de renseignement.

Toute aide serait tres appreciable, car ce projet me tiens a coeur et ca fait un petit moment que je planche dessus.

Merci d'avance.