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

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!

In chess, they use(d) a recursive version of mini-max called alpha-beta (which is just mini-max with a few lines of code to improve it).

Then, along came multi-core processors, and everyone wanted their chess program to run "deep" in parallel search modes, to take advantage of the extra horsepower available. This required an iterative version of alpha-beta, iirc.

The chess experts yak it up here: www.talkchess.com and PLEASE don't mention anything about any clone of a chess program!! That is the sore spot on their hide, believe me.

After registration (which takes a few days sometimes), go to the programming sub forum.

Many of the regulars there are chess authors themselves, some are former world champion chess programmers - they really know their alpha beta algorithms (and how to argue about cloned chess programs).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.