Java StackOverflowError caused by recursion when running program for long periods of time

Question

I am working on a project to try and create a neural net that will learn how to play checkers using NEAT. In my checkers game, I use recursion to find all the available moves a specific piece can make. Running the program normally, it works great.

The problem is when I run the part of the program that tries to train the neural network. In my training program, I run countless checkers games (10000+) to try to evolve my neural network. Training works great for the first thousand games or so, but then I get hit with a stackoverflow error that is caused from the recursion part of the program that checks for available moves. This makes no sense to me as the method works fine for the first thousand games or so, but it always eventually breaks down with a stackoverflow error.

EDIT: Here is the main overview of the recursive method I cut out a lot of the if statements. Also, I apologize for the length of this, I probably could have implemented in a more readable and efficient way.

 private void checkAvailableTilesRecursion(GameBoardTile oldTile, LegalMove newMove) {

    ArrayList<LegalMove> recursiveCheck = new ArrayList<>();

    // Find available pieces if piece is king
    if (!edgePiece) {
        // Code to get the different tiles adjacent to this tile

        if (legalMoveCheckerPiece.getIsKing()) {
            // Up right
            // If the tile up right is clear
                LegalMove move = new LegalMove(newMove.getNewTile(), board.getTile()[newMove.returnNewY() - 2][newMove.returnNewX() + 2], newMove, null, upRight, MoveDirections.UP_RIGHT);
                newMove.setMoveAfter(move);
                availableLegalMoves.add(move); // defined elsewhere
                recursiveCheck.add(move);
            }
            // Up left
            // If the tile up left is clear
                LegalMove move = new LegalMove(newMove.getNewTile(), board.getTile()[newMove.returnNewY() - 2][newMove.returnNewX() - 2], newMove, null, upLeft, MoveDirections.UP_LEFT);
                newMove.setMoveAfter(move);
                availableLegalMoves.add(move); // defined elsewhere
                recursiveCheckRecursive.add(move);
            }

            // Down right
            // If tile down right is clear
                LegalMove move = new LegalMove(newMove.getNewTile(), board.getTile()[newMove.returnNewY() + 2][newMove.returnNewX() + 2], newMove, null, downRight, MoveDirections.DOWN_RIGHT);
                newMove.setMoveAfter(move);
                availableLegalMoves.add(move); // defined elsewhere
                recursiveCheckRecursive.add(move);
            }

            //Down left
            // If tile down left is clear
                LegalMove move = new LegalMove(newMove.getNewTile(), board.getTile()[newMove.returnNewY() + 2][newMove.returnNewX() - 2], newMove, null, downLeft, MoveDirections.DOWN_LEFT);
                newMove.setMoveAfter(move);
                availableLegalMoves.add(move); // defined elsewhere 
                recursiveCheckRecursive.add(move);
            }

        } else {

            // Find available tiles for normal pieces
            if (legalMoveCheckerPiece.getColor() == PieceColors.BLUE) {

                // Up right
                // If tile up right is clear
                    LegalMove move = new LegalMove(newMove.getNewTile(), board.getTile()[newMove.returnNewY() - 2][newMove.returnNewX() + 2], newMove, null, upRight, MoveDirections.UP_RIGHT);
                    newMove.setMoveAfter(move);
                    availableLegalMoves.add(move);
                    recursiveCheckRecursive.add(move);
                }
                // Up left
                // If tile up left is clear
                    LegalMove move = new LegalMove(newMove.getNewTile(), board.getTile()[newMove.returnNewY() - 2][newMove.returnNewX() - 2], newMove, null, upLeft, MoveDirections.UP_LEFT);
                    newMove.setMoveAfter(move);
                    availableLegalMoves.add(move);
                    recursiveCheckRecursive.add(move);
                }

            } else {
                // Red Team
                // Down right
                // If tile down right is clear
                    LegalMove move = new LegalMove(newMove.getNewTile(), board.getTile()[newMove.returnNewY() + 2][newMove.returnNewX() + 2], newMove, null, downRight, MoveDirections.DOWN_RIGHT);
                    newMove.setMoveAfter(move);
                    availableLegalMoves.add(move);
                    recursiveCheckRecursive.add(move);
                }

                //Down left
                // If tile down left is clear
                    LegalMove move = new LegalMove(newMove.getNewTile(), board.getTile()[newMove.returnNewY() + 2][newMove.returnNewX() - 2], newMove, null, downLeft, MoveDirections.DOWN_LEFT);
                    newMove.setMoveAfter(move);
                    availableLegalMoves.add(move);
                    recursiveCheckRecursive.add(move);
                }
            }
        }
    }

    if (recursiveCheckRecursive.size() > 0) {
        for (LegalMove moveToCheck : recursiveCheckRecursive) {
            checkAvailableTilesRecursion(newMove.getNewTile(), moveToCheck);
        }
    }
}

EDIT #2: I think this has to do something with a memory leak. I was using the Intellij Debug tool and the Intellij Memory Analyzer showed this.

Why wouldn't the garbage collector destroy the arraylists and LegalMove objects after I am done using them though?

Is it your code that is making the recursive calls? If so, have you considered trying a different - non recursive - approach? — Obicere, Feb 12 '17 at 22:01
Can you post some relevant code? Not the whole thing, just the key parts of the recursion. — degs, Feb 12 '17 at 22:01
post the code.But as a suggestion you can try DP approach(not pefect solution, as we haven't seen your code) — Roshan, Feb 12 '17 at 22:03
Have you considered that a checkers game may be potentially infinite (or at least really, really long)? Consider a king piece on each side that move back and forth without jumping each other. Check the game lengths and consider pruning games that proceed beyond a sane move count. — degs, Feb 12 '17 at 22:05
@degs I have a check that results in the checkers game as a draw if no one has one within 75 turns — Smaugy, Feb 12 '17 at 22:13
That code can absolutely be done in a non-recursive way. Consider changing the algorithm to avoid the recursive calls. It'll probably end up a ton faster too. — Obicere, Feb 12 '17 at 22:14
_Why wouldn't the garbage collector destroy the arraylists and LegalMove objects after I am done using them though?_ Because they still have references somewhere. It's hard to know, since it's not clear how this code is being used. Those are heap variables, anyway, unless that screenshot means you have `2471963` variables on the stack, which explains the stack overflow. — Christopher Schneider, Feb 12 '17 at 23:03
Yes, I think those variables are on the stack. The reason why it has so much is probably because whilst trying to debug this problem, I increased the stack size to half a gigabyte of memory — Smaugy, Feb 12 '17 at 23:56

ldz · Answer 1 · 2017-02-12T22:14:26.823

1

The thread stack is limited in the JVM and can be configured via the -Xss option. Another way to provide the stack size is by specifying it in the constructor when creating Threads by hand.

If these alternatives are no option, you might consider using the Trampoline pattern instead of a recursive implementation in order to be independent of any limitation.

edited Feb 12 '17 at 22:14

answered Feb 12 '17 at 22:08

ldz

2,217
16
21

JustDanyul · Answer 2 · 2017-02-12T22:20:54.713

Without any code, its hard to give a concrete answer. But, a couple of offhand suggestions would be:

(Starting with the captain obvious type suggestion) If you haven't already give it more stack memory using the -Xss option.
try and limit the amount of stack space it occupies by limiting the amount of local variables within the method scope, by trying to ensure you mostly have references in the stack memory and most of your objects objects on the heap.
rewrite it to be iterative instead of recursive ;)

Java StackOverflowError caused by recursion when running program for long periods of time

2 Answers2