View unanswered posts | View active topics It is currently Thu Jul 10, 2014 6:10 am






Reply to topic  [ 5 posts ] 
Implement Minimax algorithm in ROBOTC 
Author Message
Rookie

Joined: Sat Nov 12, 2011 7:14 pm
Posts: 2
Post Implement Minimax algorithm in ROBOTC
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 :) !


Sat Nov 12, 2011 7:17 pm
Profile
Rookie

Joined: Sat Nov 12, 2011 7:14 pm
Posts: 2
Post Re: Implement Minimax algorithm in ROBOTC
In case somebody is actually interested in knowing the answer, using a "ghost" function like below worked for me:

Code:
char ghost(sBoard &board, bool minNode, char &xBest, char &yBest)
{
   return miniMax(board, minNode, xBest, yBest);
}


To developers: Any updates on support for recursion?


Tue Nov 15, 2011 3:10 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3155
Location: Rotterdam, The Netherlands
Post Re: Implement Minimax algorithm in ROBOTC
The FW would need a complete internal rewrite to allow recursion so I am not so sure it will happen any time soon. I wouldn't hold my breath :)

- Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Tue Nov 15, 2011 3:17 am
Profile WWW
Rookie

Joined: Tue Aug 07, 2012 5:36 am
Posts: 1
Post Re: Implement Minimax algorithm in ROBOTC
mightor wrote:
The FW would need a complete internal rewrite to allow recursion so I am not so sure it will happen any time soon. I wouldn't hold my breath :)
- Xander


but it should need some more proper solution dud.. :programmer:

_________________
minimax solution


Tue Aug 07, 2012 5:37 am
Profile
Site Admin
Site Admin

Joined: Thu May 24, 2012 12:15 pm
Posts: 553
Post Re: Implement Minimax algorithm in ROBOTC
This thread is a bit old, but ironically recursion and pointers are two major things we are working on for the next big update. Keep your eyes peeled, we plan to have it out sometime this fall.

_________________
Check out our Blog! And our Facebook page!
Need help? Take a look at our Wiki and our Forums.

I just met you,
And this is crazy,
But here's my code now,
So fix it, maybe?
~ Carly Rae Jepsen parody


Tue Aug 07, 2012 9:00 am
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 5 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.