Implement Minimax algorithm in ROBOTC

ArmanUV · Sat Nov 12, 2011 7:17 pm

I am buiding a Tic Tac Toe solving robot 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 ROBOTC or any other C NXT compiler support recursive functions. How can change the following code so that it does not rely on recursion?


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


	Code: 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

!

Implement Minimax algorithm in ROBOTC

Who is online