I have implemented a TicTacToe algorythm with MiniMax, but the problem is that the computer always just places an 'x' on the next possible spot instead of evaluating the game. Does anybody know why ? (The problem can only be in the MiniMax function, or the nextMove function.) Thanks a lot in advance !! Here's the code :
int MiniMax(struct Game g, enum Symbol pl){
int score;
if (pl==CROSS)
{
score = -98765;
}
else score = 98765;
int temp_cross =0;
int temp_circle =0;
//base case
if (game_over(g) == CROSS)
return 10;
else if (game_over(g) == CIRCLE)
return -10;
else if (game_over(g) == FULL)
return 0;
int x,y;
for (y=0; y<SIZE_Y_AXIS; y++)
{
for (x=0; x<SIZE_X_AXIS; x++)
{
if (g.board.fields[x][y] == NONE)
{
if (pl == CROSS)
g.board.fields[x][y] = CROSS;
else g.board.fields[x][y] = CIRCLE;
if (pl == CROSS)
temp_cross= MiniMax(g, CIRCLE);
else temp_circle = MiniMax(g, CROSS);
g.board.fields[x][y] = NONE;
if ((pl == CROSS) && (temp_cross > score))
score = temp_cross;
else if ((pl == CIRCLE) && (temp_circle < score))
score = temp_circle;
}
}
}
return score;
};
int nextMove(struct Game g, enum Symbol player){
int score_cross = -865435;
int score_cross_temp = 0;
int cross_position = 1;
int score_circle = 876545;
int score_circle_temp = 0;
int circle_position = 1;
int x,y;
for (y=0; y<SIZE_Y_AXIS; y++)
{
for (x=0; x<SIZE_X_AXIS; x++)
{
if (g.board.fields[x][y] == NONE)
{
if (player == CROSS)
{
score_cross_temp = MiniMax(g, CROSS);
printf("%d ",MiniMax(g, CROSS));
if (score_cross_temp > score_cross)
{
score_cross = score_cross_temp;
cross_position = (y)*3 + x+1;
}
}
else if (player == CIRCLE)
{
score_circle_temp = MiniMax(g, CIRCLE);
if (score_cross_temp < score_circle)
{
score_circle = score_circle_temp;
circle_position = (y)*3 + x+1;
}
}
}
}
}
if (player == CROSS)
{
//printf("%d",cross_position);
return cross_position;
}
else
{
//printf("%d",circle_position);
return circle_position;
}
};
I believe there is a bug in your code. You initialize score as 10, and the temp variables as arbitrarily high and low numbers. This is backwards. TempCircle and TempCross are being overwritten anyway my the calls to minimax. It is the score variable that must be set like that. replace
int score = 10;
int temp_cross = -9876543;
int temp_circle = 9876543;
with
int score;
if(pl==cross){
score = 9876543
}
else{
score = -9876543
}
int temp_cross;
int temp_circle;
There also seems to be another bug in your nextMove function. I assume that its purpose is to iterate over all possible moves, find the one with the highest minimax value, and return that move (correct me if I'm wrong). That is not what the function does. It iterates over all the moves, but does't make any of them. x and y are never even used, except to update the move. You are essentially calling the same minimax several times. Instead, I would either get rid of the function completely, as there is a way to do this inside the minimax function, or fix this function. To fix the function, I would change it to this:
int nextMove(struct Game g, enum Symbol player){
int score_cross = -865435;
int score_cross_temp = 0;
int cross_position = 1;
int score_circle = 876545;
int score_circle_temp = 0;
int circle_position = 1;
int x,y;
for (y=0; y<SIZE_Y_AXIS; y++)
{
for (x=0; x<SIZE_X_AXIS; x++)
{
if (g.board.fields[x][y] == NONE)
{
if (player == CROSS)
{
g.board.fields[x][y] = CROSS;
score_cross_temp = MiniMax(g, CIRCLE);
printf("%d ",MiniMax(g, CROSS));
g.board.fields[x][y] = NONE;
if (score_cross_temp > score_cross)
{
score_cross = score_cross_temp;
cross_position = (y)*3 + x+1;
}
}
else if (player == CIRCLE)
{
g.board.fields[x][y] = CIRCLE;
score_circle_temp = MiniMax(g, CROSS);
g.board.fields[x][y] = NONE;
if (score_cross_temp < score_circle)
{
score_circle = score_circle_temp;
circle_position = (y)*3 + x+1;
}
}
}
}
}
if (player == CROSS)
{
//printf("%d",cross_position);
return cross_position;
}
else
{
//printf("%d",circle_position);
return circle_position;
}
};
Or you can edit minimax to keep track of which call to the function it is. If it is the first recursive call (the root) , keep track of the move itself as well as its value. Then return the move.