Back to For Beginners

C++ NegaMax bug help

For Beginners

Started by RedKMan July 18, 2010 12:56 PM

3 comments, last by RedKMan 13 years, 9 months ago

RedKMan

122

Author

July 18, 2010 12:56 PM

For the most part the function below works well. When the computer plays first it always chooses position 0 and it always ends in a draw (unless I don't choose the center position (4) and then the computer wins).

However, when I play first I always win when I start at position 0. An example play is below based on me playing first and my marker being O.

O X 2
X X O
O O 8

So, it has blocked me up until this point and tried to win itself. Now it is the computers choice but rather than play position 8 to stop me winning it goes with position 2 allowing me to play position 8 and steal a sweet victory. Up until the final two places left on the board it behaves as it should, blocking me and trying to win. So it is working to a degree just not when this situation occurs.

I've tried debugging and stepping through but if I'm honest it's kinda hard to follow exactly what is going on with it all.

Just wondering if anyone can spot a silly error or suggest how I can solve this bug. Like I said when the computer plays first it works correctly with no bugs.

int evaluateAI(GameBoard &TicTacToe, int Player, int &bestMove ){	int			bestScore;	int			score;	#define		WIN		1;	#define		LOSS	-1;	#define		DRAW	0;	if(!TicTacToe.gameOver())	{		return DRAW;	}	else if(TicTacToe.checkWinningLine(players[Player].getMarker()))	{		return WIN;	}	else if(TicTacToe.checkWinningLine(players[1 - Player].getMarker()))	{		return LOSS;	}	else	{		bestScore = LOSS;		int notUsed;		for(int row = 0; row < 3; row++)		{			for(int col = 0; col < 3; col++)			{				if(TicTacToe.getBoard(row, col) == '\0')				{					TicTacToe.setBoard(row, col, players[Player].getMarker());					score = -evaluateAI(TicTacToe, 1 - Player, notUsed);					if(score > bestScore)					{						bestMove = TicTacToe.convertIndex(row, col);						bestScore = score;					}					TicTacToe.unsetBoard(row, col);				}			}		}	}	return bestScore;}

clb

2,152

July 18, 2010 01:13 PM

The very first check: "If the current board state game does not represent a finished game, return DRAW." If you call this evaluateAI for any board state that still has free squares to play to, doesn't this immediately return 0?

Shouldn't you rather have:

int EvaluateBoard(board, player){   if (IsGameOver())   {      if (IWin) return 1;      if (ILose) return -1;      return 0;   }   else // Game not yet over, search deeper.   {      foreach(move m in board)      {         MakeMove(m, board);         best = max(best, -EvaluateAI(board, 1-player));         UndoMove(m, board);      }      return best;   }}

For tic tac toe, the above is ok, but for any game in which you can't search the full tree, you'll want to cap the search depth and evaluate the state using a heuristic.

RedKMan

122

Author

July 18, 2010 01:28 PM

if(!TicTacToe.gameOver())
{
return DRAW;
}

The above is actually checking to see if there are any places still available to play on the board. If there are no empty places then return DRAW. So if there is still a blank space available it is skipped.

It's working up until the situation I mentioned above.

This is whats giving me a headache, it works up until this point and trying to debug it and figure out what is happening is very confusing :(.

clb

2,152

July 18, 2010 01:40 PM

Quote:Original post by RedKMan
If there are no empty places then return DRAW.

No. That's not correct. If there are no empty places, the game is over, we need to score the board state and see which player won. Only if neither player had three-in-a-row is the game a draw and you may return zero.

If there are empty places, we first have to check if the current board contains a three-in-a-row and if so, return IWin or ILose. If there is no three-in-a-row, we must search deeper. Games that are still unfinished cannot be called a draw.

RedKMan

122

Author

July 18, 2010 04:47 PM

Massive thanks CLB, now works perfectly :). For anyone interested the working version is below.

int evaluateAI(GameBoard &TicTacToe, int Player, int &bestMove ){	int			bestScore;	int			score;	#define		WIN		1;	#define		LOSS	-1;	#define		DRAW	0;	if(!TicTacToe.gameOver())	{		if(TicTacToe.checkWinningLine(players[Player].getMarker()))		{			return WIN;		}		if(TicTacToe.checkWinningLine(players[1 - Player].getMarker()))		{			return LOSS;		}		return DRAW;	}	else if(TicTacToe.checkWinningLine(players[Player].getMarker()))	{		return WIN;	}	else if(TicTacToe.checkWinningLine(players[1 - Player].getMarker()))	{		return LOSS;	}	else	{		bestScore = LOSS;		int notUsed;		for(int row = 0; row < 3; row++)		{			for(int col = 0; col < 3; col++)			{				if(TicTacToe.getBoard(row, col) == '\0')				{					TicTacToe.setBoard(row, col, players[Player].getMarker());					score = -evaluateAI(TicTacToe, 1 - Player, notUsed);					if(score > bestScore)					{						bestMove = TicTacToe.convertIndex(row, col);						bestScore = score;					}					TicTacToe.unsetBoard(row, col);				}			}		}	}	return bestScore;}

C++ NegaMax bug help

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

C++ NegaMax bug help

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines