0

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!

2
Contributors
1
Reply
3
Views
5 Years
Discussion Span
Last Post by Adak
0

I can't answer your query, but I know who can. ;)

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).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.