View unanswered posts | View active topics It is currently Fri May 24, 2013 3:22 am

 Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
Implement Minimax algorithm in ROBOTC
Author Message
Rookie

Joined: Sat Nov 12, 2011 7:14 pm
Posts: 2
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;}

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
Rookie

Joined: Sat Nov 12, 2011 7:14 pm
Posts: 2
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
Moderator

Joined: Wed Mar 05, 2008 8:14 am
Posts: 2864
Location: Rotterdam, The Netherlands
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

_________________
| Some people, when confronted with a problem, think, "I know, I'll use threads,"
| and then two they hav erpoblesms. (@nedbat)

| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]

Tue Nov 15, 2011 3:17 am
Rookie

Joined: Tue Aug 07, 2012 5:36 am
Posts: 1
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..

_________________
minimax solution

Tue Aug 07, 2012 5:37 am

Joined: Thu May 24, 2012 12:15 pm
Posts: 389
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
Display posts from previous:  Sort by
 Page 1 of 1 [ 5 posts ]

#### Who is online

Users browsing this forum: No registered users and 5 guests

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

Search for:
 Jump to:  Select a forum ------------------ ROBOTC Applications    ROBOTC for LEGO MINDSTORMS       Third-party sensors    ROBOTC for CORTEX & PIC    ROBOTC for Arduino    Robot Virtual Worlds    Multi-Robot Communications    Issues and Bugs Competitions & Partners    2013 Robotics Summer Of Learning       VEX Toss Up Programming Challenge       FTC Ring It Up! Programming Challenge    Competitions using VEX - BEST, TSA, VEX, and RoboFest!    FTC Programming    RoboCup Junior and Other ROBOT Competitions    Robotics Merit Badge Robotics Discussions    General Discussions    Project Discussions International Forums    Spanish Forums       ROBOTC for MINDSTORMS       ROBOTC for VEX    French Forums       ROBOTC pour Mindstorms       ROBOTC pour IFI VEX    Japanese Forums （日本語のフォーラム） Off-Topic ROBOTC Forum & ROBOTC.net Suggestions/Feedback    ROBOTC Forums Suggestions/Comments    ROBOTC.net Suggestions/Comments       NXT Programming: Tips for Beginning with ROBOTC       VEX Programming: Tips for Beginning with ROBOTC