View unanswered posts | View active topics It is currently Fri Feb 12, 2016 4:05 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

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3623
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

_________________
| 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
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: 722
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 updated help documentation and the ROBOTC Forums.

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 1 guest

 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 VEX IQ    ROBOTC for Arduino    Robot Virtual Worlds    Multi-Robot Communications    Issues and Bugs Competitions & Partners    Mini Urban Challenge    2014 Robotics Academy Summer of Learning    CS2N Robot Virtual Worlds Competitions       VEX Skyrise Competition 2014-2015       VEX Toss Up 2013-2014       FTC Block Party! 2013-2014    Competitions using VEX - BEST, TSA, VEX, and RoboFest!    FTC Programming    RoboCup Junior and Other ROBOT Competitions Virtual Brick Robotics Discussions    General Discussions    Project Discussions 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    2013 Robotics Summer Of Learning       VEX Toss Up Programming Challenge       FTC Ring It Up! Programming Challenge    International Forums       Spanish Forums          ROBOTC for MINDSTORMS          ROBOTC for VEX       French Forums          ROBOTC pour Mindstorms          ROBOTC pour IFI VEX       Japanese Forums （日本語のフォーラム）       German Forums    2015 Spring Carnival Event    PLTW (Project Lead The Way)    Robotics Merit Badge