Results 1 to 12 of 12
  1. #1
    emschorsch is offline Member
    Join Date
    Apr 2011
    Posts
    6
    Rep Power
    0

    Default Recursive Method

    I am getting a stack overflow error when I run the driver window for my tic tac toe ai.

    Java Code:
    public int comp(String[] board, int[] moves, int x, int index){
        if(index==9)
          return 50;
        if(humanWin(board))
          return 100;
        if(compWin(board))
          return moves[x];
        moves=posMoves(board);
        if(index%2==0)
        {
          board[moves[x]]="x";
        comp(board, moves, x++, index++);
        }
        else
        {
          board[moves[x]]="o";
        comp(board, moves, x++, index++);
        }
        return 100;
      }
    The method posMoves returns an array of integers with all the possible moves given the current board. compWin and humanWin clearly test for whether the computer or the player won both those methods are good and work I'm sure of it. If you would like me to post any other methods please tell me. I would just like someone to give me an idea of what I'm doing wrong. I'm trying to learn to write ai and on that note if anyone has any tips for how to go about doing that or whether I should start by learning something else first please let me know.
    Many thanks,
    Emschorsch
    Last edited by Fubarable; 04-18-2011 at 05:13 AM. Reason: Mod edit: code tags added

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    If you're getting a stackoverflow for a recursive methods, there's a good chance that your method's stop condition is never satisfied and so the method never ends until it runs out of memory. The location of the error may help you as would println statements.

  3. #3
    emschorsch is offline Member
    Join Date
    Apr 2011
    Posts
    6
    Rep Power
    0

    Default

    it says it comes from line 13 which is where I call compWin. But I thought it must be a mistake because that doesnt make any sense. After that it says 1000 times it comes from line 21 which is the comp(board...) line of the following
    if(index%2==0)
    {
    board[moves[x]]="x";
    comp(board, moves, x++, index++);
    }
    Last edited by emschorsch; 04-18-2011 at 05:03 AM.

  4. #4
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    Aha,... You have a big problem passing index++ as a parameter. Do you understand what this does? It's always smart to do your increment on a separate line as the extra file real estate is minimal and the code clarity and reduced bugs are well worth it.

    If you are not clear what I mean, do a println of your index variable and tell me if it changes like you expect it to.

  5. #5
    emschorsch is offline Member
    Join Date
    Apr 2011
    Posts
    6
    Rep Power
    0

    Default

    Wow thank you, you were right on the money. Why does that happen it seems to me like they are identical expressions. Now I'm running into the issue of an out of bound error because I return 100 in the case of a tie. But I won't bother you with giving away how to solve that. Do you have any advice for my second question regarding ai though?

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    Or change it to a preincrement. Then again both options might be wrong and this is might be what you want:
    Java Code:
    comp(board, moves, (x+1), (index+1));

  7. #7
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    index++ pass the original index to the new method and then increments the index variable whereas ++index increments the variable and then passes it to the method.

    For example swap the comments in this code to see this in action:

    Java Code:
    public class RecursiveFoo {
       private static final int INDEX_MAX = 100;
    
       public static void recurse(int index) {
          if (index > INDEX_MAX) {
             return;
          } else {
             System.out.println("index is: " + index);
    
             // recurse(index++);
             recurse(++index);
          }
       }
       
       public static void main(String[] args) {
          recurse(1);
       }
    }

    But for my money, if you want to increment the variable then use it, do the incrementation on its own line; that way there's no ambiguity. Note you have the same problem with other variables.
    Last edited by Fubarable; 04-18-2011 at 05:44 AM.

  8. #8
    emschorsch is offline Member
    Join Date
    Apr 2011
    Posts
    6
    Rep Power
    0

    Default

    Ya I changed all of them to increment on the line before. But more importantly thanks for the explanation. I never knew that there was a difference where the + is placed and now I know, thank you. Also can you just tell me what in your mind are prerequisites to trying to program say a chess ai. Meaning in terms of specific expertise in Java should I work on just learning more about java first? Again thank you, you've been immensely helpful.

  9. #9
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

  10. #10
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    Just to illustrate my point above:
    Java Code:
    class Test {
        public static void main(String[] args) {
            countDownFromTwentyWrong(7);
            System.out.println();
            countDownFromTwentyCorrect(7);
        }
        
        public static void countDownFromTwentyWrong(int num) {
            if(num < 20) {
                countDownFromTwentyWrong(++num);
            }
            System.out.println(num);
        }
        
        public static void countDownFromTwentyCorrect(int num) {
            if(num < 20) {
                countDownFromTwentyCorrect(num+1);
            }
            System.out.println(num);
        }    
    }

  11. #11
    emschorsch is offline Member
    Join Date
    Apr 2011
    Posts
    6
    Rep Power
    0

    Default

    Quote Originally Posted by Fubarable View Post
    First learn basic Java before even considering any aspect of AI.
    I felt like I kindof understood basic java but maybe I'm wrong. So what reveals my ignorance or is it just kindof a general feel?

    Also thank you Junky that gave me a better idea of what exactly happens.

  12. #12
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    Quote Originally Posted by emschorsch View Post
    I felt like I kindof understood basic java but maybe I'm wrong. So what reveals my ignorance or is it just kindof a general feel?

    Also thank you Junky that gave me a better idea of what exactly happens.
    I just kind of figured you were newbie as you didn't know the difference between ++i and i++.

Similar Threads

  1. Replies: 3
    Last Post: 02-09-2010, 05:22 AM
  2. recursive method
    By michail in forum New To Java
    Replies: 0
    Last Post: 01-31-2010, 01:50 PM
  3. Writing a recursive method :S
    By Thousand in forum New To Java
    Replies: 1
    Last Post: 12-06-2009, 03:13 PM
  4. recursive method problem
    By melody in forum New To Java
    Replies: 1
    Last Post: 10-29-2009, 07:15 AM
  5. Recursive Method
    By bluegreen7hi in forum New To Java
    Replies: 5
    Last Post: 11-29-2007, 04:45 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •