Tic Tac Toe Minimax Algorithm Problem
Hey guys I'm actually new here, kinda hoping this community will help me alot with my learning. :)
Well my problem is with my minimax algorithm for tic-tac-toe. The code works, there's just some slight problem, the computer doesn't play perfectly. Sure it can draw you almost everytime, but sometimes, it doesn't see forks, or will even play randomly. So, here's the minimax code, written in c++.
Code:
int minimax( char _board[9] )
{
short int i;
int bestValue = +INFINITY, index = 0;
char bestMoves[9] = {0};
for( i = 0; i < 9; i++ )
{
if( _board[i] == empty )
{
_board[i] = o;
int value = maxSearch( _board );
if( value < bestValue )
{
bestValue = value;
index = 0;
bestMoves[index] = i;
}
else if( value == bestValue )
bestMoves[index++] = i;
_board[i] = empty;
}
}
if( index > 0 )
index = rand() % index;
return bestMoves[index];
}
int minSearch( char _board[9] )
{
short int i;
int positionValue = gameState(_board);
if( positionValue == DRAW ) return 0;
if( positionValue != INPROGRESS ) return positionValue;
int bestValue = +INFINITY;
for( i = 0; i < 9; i++ )
{
if( _board[i] == empty )
{
_board[i] = o;
int value = maxSearch( _board );
if( value < bestValue )
bestValue = value;
_board[i] = empty;
}
}
return bestValue;
}
int maxSearch( char _board[9] )
{
short int i;
int positionValue = gameState(_board);
if( positionValue == DRAW ) return 0;
if( positionValue != INPROGRESS ) return positionValue;
int bestValue = -INFINITY;
for( i = 0; i < 9; i++ )
{
if( _board[i] == empty )
{
_board[i] = x;
int value = minSearch( _board );
if( value > bestValue )
bestValue = value;
_board[i] = empty;
}
}
return bestValue;
}
So yeah, the symbols are fixed, 'x' is for the player, and 'o' is for the computer. And yeah, the computer plays as the minimizer. I was actually thinking of implementing depth, the more shallow the leafnode (the last position, whether win for x or o, or a draw), the better the score. So, what do you guys think?
