Sign in to follow this  

[java] why this StackOverflowError?

This topic is 4857 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm writing a simple 2 players game in Java. I build an alpha-beta tree in order to let a computer player play the game, but after a dozen of times I build the tree, a StackOverflowError is thrown. Many people told me that 100000/150000 nodes should fit in the stack...so I don't understand! Someone could tell me why this happens?
  public String Generate(Board b, Board oldb)
  {
       
    Max(b, oldb, -10000, 10000, tree_depth);
    
    return new String(Integer.toString(_x)+Integer.toString(_y)); //_x and _y are member of this class
  }
  
  protected int Max(Board b, Board oldb, int alpha, int beta, int depth)
  {   
    int tmp = b.CheckForVictory(); //check if someone wins
    if(tmp == 1) return 10000; 
    else if(tmp == 2) return -10000;
    
    if(depth == 0) return EvaluateGame(b, oldb); //Leaf
    
    Board children[][] = new Board[6][5];
    for(int x = 0; x < 6; x++)
      for(int y = 0; y < 5; y++)
    {
      if(!b.Verify(x, y, true)) continue; //invalid move  
       
      children[x][y] = new Board(b);
      children[x][y].AddFast(x, y, true);
         
      tmp = Min(children[x][y], b, alpha, beta, depth-1);
      if(tmp > alpha) 
      {
        alpha = tmp;
        _x = x;
        _y = y;
      }
      if(beta <= alpha) return beta;
    }
    return alpha;
  }
  
  protected int Min(Board b, Board oldb, int alpha, int beta, int depth)
  {
    int tmp = b.CheckForVictory(); //check if someone wins
    if(tmp == 1) return -10000; 
    else if(tmp == 2) return 10000;
    
    if(depth == 0) return -EvaluateGame(b, oldb); //Leaf
        
    Board children[][] = new Board[6][5];
    for(int x = 0; x < 6; x++)
      for(int y = 0; y < 5; y++)
    {
      if(!b.Verify(x, y, false)) continue; //invalid move
         
      children[x][y] = new Board(b);
      children[x][y].AddFast(x, y, false);
         
      tmp = Max(children[x][y], b, alpha, beta, depth-1);
      if(tmp < beta) 
      {
        beta = tmp;
        _x = x;
        _y = y;
      }
      if(beta <= alpha) return alpha;
    }
    return beta;
  }  
  


Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Have you looked in the documentation to find out what a stackoverflow is? If not, you need to learn to RTFM

...but sun's docs have several "holes" so perhaps that's not filled in sufficiently in your docs. So...stack overflow in java is nearly always because you recursed too much. I.e. you had a method that called itself 1 million times; e.g.:

int recurse( int i )
{
return i + recurse( -i );
}

If you call that code it should crash your JVM because it runs out of stack to hold the method call data. Unless your compiler or JVM is clever and reaslises the code doesn't do anything...

Share this post


Link to post
Share on other sites
[QUOTE]
So...stack overflow in java is nearly always because you recursed too much. I.e. you had a method that called itself 1 million times
[\QUOTE]

Yes, I thought that too but my tree creates up to 100000 nodes. I really don't know if this amount is too much: many peoples said that this should fit in the stack, so I think (and hope) that there is a problem in my own code, even if I cannot find it. I noticed, however, that the exeption is thrown after some calls of the Generate() method. So I would expect that if the first time it works, it should always work (the amount of created nodes remain more or less the same). My question, now, is the following: Is there some kind of garbage even for the stack? I mean that pehaps after each call not the whole stack is freed and this can lead to the exception after a while...

Share this post


Link to post
Share on other sites
You don't need to create the Children[][] array, you're keeping the whole tree around when you only care about the current variation being considered. Notice how each iteration of the loop only cares about one element of the array... since there's no interaction, there's no need for the old data.

However, that shouldn't be your problem because almost all of that construction should happen on the *heap*... if there were really a problem then you should get OutOfMemoryError instead.

So... check the callers, pay special attention to the 'depth' parameter. If there's any way for tree_depth to get set negative, then you'll have infinite recursion. (OK, technically not infinite, because Java will wrap the number around, so it's like having a depth of 4 billion-odd - anyway, more than enough to cause a problem ;) )

Just as a good-style hint: Max() and Min() are *very* parallel. Consider replacing them with a single function, with an extra boolean parameter (true = max, false = min). Notice you would be able to use it directly in the Verify() and addFast() :)

Share this post


Link to post
Share on other sites
Thank you for the help. Yes, this is the second version of the algorithm: the first one gave me the OutOfMemoryError, but now each board object is 14 times smaller than before. And I get this stack error. I don't know what to think: as I said, the tree creates up to 85000 nodes. I call it some times and then the error happens. One thing is for me important: should I be able to build this tree?
As for now, I'll replace the array with a single variable!
Thank you again!

Share this post


Link to post
Share on other sites
Quote:
Original post by CaptainJester
Post you rstack trace.


Sorry but...what is this? (going to google for rstack trace...)

EDIT: ah, stack trace... yeah, the console doesn't print it, but I wrote some code to force that (don't know if it works). I will post it as soon as I will be able to get the error again... Thank you

[Edited by - cignox1 on August 27, 2004 12:46:15 PM]

Share this post


Link to post
Share on other sites
Any unchecked exception should produce a complete stack trace. However you can force the issue by putting a try...catch around your main entry point.

public static void main(String args[]) {
try {
MyApplication app = new MyApplication();
app.go();
}
catch(Exception e) {
e.printStackTrace();
}
}

Share this post


Link to post
Share on other sites
Thank you... finally I think I discovered the source of my problems: What I didn't recall, is that the code I posted calls indirectly another recursive function, so... recursive^2 is a bomb sometimes. Now I think that the best way to proceed is to convert this second function into an iterative one. If you guy tell me that this could be a solution, then I will post the problem in the general programming forum...

Share this post


Link to post
Share on other sites

This topic is 4857 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this