Jump to content
  • Advertisement
Sign in to follow this  
RedKMan

C++ NegaMax bug help

This topic is 2869 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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;
}



Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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 :(.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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;
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!