I am buiding a Tic Tac Toe solving robot using the LEGO NXT kit for my school project. For practise, I wrote a Tic Tac Toe game using the minimax algorithm which worked very well. When I wanted to port my code to NXT, I found out that none of C/C++ NXT compilers such as ROBOTC or NXC support recursive functions. How can change the following code so that it does not rely on recursion?
int miniMax (char board[BOARD_DIM][BOARD_DIM], _Bool minNode, int *xBest, int *yBest)
{
int possibleMoves[NSQUARES][2];
int nPossibleMoves = generateMoves(board, possibleMoves);
char boardChild [BOARD_DIM][BOARD_DIM];
int ind, x_ind, y_ind;
int minScore, maxScore;
if (gameOver(board))
return evaluateState(board);
else if (minNode)
{
minScore = +INFINITY;
for (ind = 0 ; ind < nPossibleMoves; ind++)
{
duplicateBoard(board, boardChild);
x_ind = possibleMoves[ind][0];
y_ind = possibleMoves[ind][1];
updateboard(boardChild, x_ind, y_ind, cPlayer);
int score = miniMax(boardChild,!minNode ,&x_ind ,&y_ind);
if (minScore > score)
minScore = score;
}
return minScore;
}
else if (!minNode)
{
maxScore = -INFINITY;
for (ind = 0 ; ind < nPossibleMoves; ind++)
{
duplicateBoard(board, boardChild);
x_ind = possibleMoves[ind][0];
y_ind = possibleMoves[ind][1];
updateboard(boardChild, x_ind, y_ind, cComputer);
int score = miniMax(boardChild,!minNode ,&x_ind ,&y_ind);
if (maxScore < score)
{
maxScore = score;
*xBest = x_ind;
*yBest = y_ind;
}
}
return maxScore;
}int generateMoves (char board[BOARD_DIM][BOARD_DIM], int possibleMoves[NSQUARES][2])
{
int x_ind, y_ind, counter = 0;
for(x_ind = 0 ; x_ind < BOARD_DIM ; x_ind++)
for(y_ind = 0 ; y_ind < BOARD_DIM ; y_ind++)
if(board[x_ind][y_ind] == EMPTY)
{
possibleMoves[counter][0] = x_ind;
possibleMoves[counter][1] = y_ind;
counter++;
}
return counter;
}About the code :
evaluatestate() returns +1 if computer has won, -1 if player has won, and 0 if it is a draw.
gameover() returns 1 if game is over (somebody has won or it is a draw)
+INFINITY is +1 and -INFINITY is -1.
BOARD_DIM = 3 , NSQUARES = 9
cComputer = 'O' , cPlayer= 'X'
Thanks!