Java Heap Space Issue with my MCTS Gomoku player

Question

When I run my program I get this error:

Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: Java heap space
        at MCTSNode.setPossibleMoves(MCTSNode.java:66)
        at MCTSNode.Expand(MCTSNode.java:167)
        at MctsPlayer.getBestMove(MctsPlayer.java:39)
        at NewBoardGUI.btnClick(NewBoardGUI.java:617)
        at NewBoardGUI.lambda$createButton$0(NewBoardGUI.java:584)
        at NewBoardGUI$$Lambda$115/558922244.actionPerformed(Unknown Source)
        at java.desktop/javax.swing.AbstractButton.fireActionPerformed(Unknown Source)
        at java.desktop/javax.swing.AbstractButton$Handler.actionPerformed(Unknown Source)
        at java.desktop/javax.swing.DefaultButtonModel.fireActionPerformed(Unknown Source)
        at java.desktop/javax.swing.DefaultButtonModel.setPressed(Unknown Source)
        at java.desktop/javax.swing.plaf.basic.BasicButtonListener.mouseReleased(Unknown Source)
        at java.desktop/java.awt.Component.processMouseEvent(Unknown Source)
        at java.desktop/javax.swing.JComponent.processMouseEvent(Unknown Source)
        at java.desktop/java.awt.Component.processEvent(Unknown Source)
        at java.desktop/java.awt.Container.processEvent(Unknown Source)
        at java.desktop/java.awt.Component.dispatchEventImpl(Unknown Source)
        at java.desktop/java.awt.Container.dispatchEventImpl(Unknown Source)
        at java.desktop/java.awt.Component.dispatchEvent(Unknown Source)
        at java.desktop/java.awt.LightweightDispatcher.retargetMouseEvent(Unknown Source)
        at java.desktop/java.awt.LightweightDispatcher.processMouseEvent(Unknown Source)
        at java.desktop/java.awt.LightweightDispatcher.dispatchEvent(Unknown Source)
        at java.desktop/java.awt.Container.dispatchEventImpl(Unknown Source)
        at java.desktop/java.awt.Window.dispatchEventImpl(Unknown Source)
        at java.desktop/java.awt.Component.dispatchEvent(Unknown Source)
        at java.desktop/java.awt.EventQueue.dispatchEventImpl(Unknown Source)
        at java.desktop/java.awt.EventQueue.access$500(Unknown Source)
        at java.desktop/java.awt.EventQueue$3.run(Unknown Source)
        at java.desktop/java.awt.EventQueue$3.run(Unknown Source)
        at java.base/java.security.AccessController.doPrivileged(Native Method)
        at java.base/java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(Unknown Source)
        at java.base/java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(Unknown Source)
        at java.desktop/java.awt.EventQueue$4.run(Unknown Source)

I used the same MCTS code for a 3x3 board size which doesn't crash and returns a competitive move quickly. But when I try to use it for a 15x15 board size, the game crashes after 1235 iterations, with the above error given.

I think I have dealt with the symptom of the problem by not allowing expansion of any node after 1235 iterations. This does eventually return a competitive move, though it take a long time before this happens.

To me the root cause is the size of the tree I'm trying to create, since the same code worked with a 3x3 board, but not with a 15x15 board; The size of the tree, containing all node objects is just too large. Therefore, this is just a problem with this approach rather than my coding.

I did think I could try: after x iterations, if a node has been visited y times but has a win score below z, then delete that node. My thinking is if after x iterations, and being visited y times but still having a low win score, then this node is likely taking up unnecessary space in the tree, and therefore can afford to be deleted.

My question is:

Is there a better way for my program to return a move rather than crash, without just reducing the number of expansions and without having to implement the above check? (Even if the best move takes a long time to be calculated).

Here is some of my unedited code:

EDITED** MCTS Expansion Function:

public MCTSNode Expand(BoardGame game){
    MCTSNode child = new MCTSNode(game);
    for(int k = 0;k<this.gameState[0].length;k++){
      for(int l = 0;l<this.gameState[1].length;l++){
        child.gameState[k][l] = this.gameState[k][l];
      }
    }
    Random r = new Random();
    int possibleMoveSelected = r.nextInt(getPossibleMovesList());
    int row = getPossibleMoveX(possibleMoveSelected);
    int col = getPossibleMoveY(possibleMoveSelected);
    if(this.currentPlayer==2){
      child.gameState[row][col] = 2;
      child.moveMadeRow = row;
      child.moveMadeCol = col;
      child.currentPlayer = 1;
      child.setPossibleMoves();
      child.possibleMoves.size();
    }
    else{
      child.gameState[row][col] = 1;
      child.moveMadeRow = row;
      child.moveMadeCol = col;
      child.currentPlayer = 2;
      child.setPossibleMoves();
      child.possibleMoves.size();
    }
    childrenNode.add(child);
    child.parentNode = this;
    this.removePossibleMove(possibleMoveSelected);
    this.possibleMoves.trimToSize();
    return this;
}

MCTSPlayer function:

public class MctsPlayer {

  private static int maxIterations;

  public MctsPlayer(int i){
    maxIterations = i;
  }


  public static String getBestMove(BoardGame game){
    MCTSNode root = new MCTSNode(game);
    root.getBoardState(game);
    root.setPossibleMoves();
    for(int iteration = 0; iteration < maxIterations; iteration++){
      MCTSNode initialNode = selectInitialNode(root);
      if(initialNode.getPossibleMovesList()>0){
        initialNode.Expand(game);
      }
      MCTSNode nodeSelected = initialNode;
      if(nodeSelected.childrenLeft() == true){
        nodeSelected = initialNode.getRNDChild();
      }
      nodeSelected.Simulate();
    }

    MCTSNode best = root.getMostVisitNode();
    System.out.println("This is the selected node's best move for the row: "+best.getMoveMadeRow());
    System.out.println("This is the selected node's best move for the col: "+best.getMoveMadeCol());
    best.printNodeInfo();
  }

NEWLY INCLUDED BELOW**

Select initial node function (Will continue until the possible move list size is == to 0):

public static MCTSNode selectInitialNode(MCTSNode node){
    MCTSNode initialNode = node;
    while (initialNode.getPossibleMovesSize()==0&&initialNode.checkForEmptySpace()==true){
      initialNode = initialNode.Select();

"+initialNode.childrenList()); //System.out.println("Nodes possible moves remaining: "+initialNode.getPossibleMovesSize()); } return initialNode; }

Select Function:

public MCTSNode Select(){
  double maxUCT = Integer.MIN_VALUE;
  MCTSNode Node = this;
  if(this.possibleMoves.size()>0){
    return Node;
      }
  else{
    for(int i = 0;i<childrenNode.size();i++){
      double UCTValue = getUCTValue(getChildren(i));
      if(UCTValue > maxUCT){
        Node = getChildren(i);
        maxUCT = UCTValue;
      }
    }
    return Node;
  }

private double getUCTValue(MCTSNode childNode) {
        double UCTValue;
        if (childNode.getVisitCount() >= 1) {
          UCTValue = (Math.sqrt(2)*
              (Math.sqrt(Math.log(childNode.getParent().getVisitCount()* 1.0) / childNode.getVisitCount())) + (1.0 *childNode.getWinCount() / childNode.getVisitCount()* 1.0));
        } else {
            UCTValue = Double.MAX_VALUE;
        }
        return UCTValue;
  }

childrenLeft function:

public boolean childrenLeft(){
  return childrenNode.size()>0;
}

score 1 · Accepted Answer · answered Nov 30 '18 at 16:05

I'm not 100% sure without seeing the code of methods like childrenLeft() and a few others, but I get the impression that you basically add b new nodes to the tree, where b is your branching factor. In other words, every iteration, you add a new, complete list of children to one node. This can probably indeed cause you to run out of memory quickly.

By far the most common strategy is to expand your tree by only adding one single new node per iteration. Every node then needs:

A list of current children (corresponding to already-expanded actions)
A list of actions that have not yet been expanded

Your Selection phase would then generally end once it reaches a node that has a non-empty list of actions to be expanded. MCTS would then randomly pick one action from that list, add a new node corresponding to that action (meaning your first list grows by one entry and the second list shrinks by one entry), and continue the rollout from there.

With such an implementation, it should be quite unlikely to run out of memory unless you allow your algorithm to search for very long times. If you do still run out of memory, you could look into things such as:

Optimizing the amount of memory required per node (it stores full game states, is the memory usage of game states optimized?)
Increasing the heap size of the JVM using command line arguments (see Increase heap size in Java)

Thank you for your reply. You were correct in that I added all possible children node states to my parent nodes, which I can see now that this would greatly affect the memory used. I have implemented this change to my expansion function, though this has impacted the quality of the move selected; the select function is now caught in a loop and I am unsure why. I have edited the above code to include the changes I have made and other functions I have used. — oldfield33, Dec 01 '18 at 00:11
I have managed to change the select function so it is no longer looping, and have tested it with various states on a 3x3 board and it is performing competitvely. I will continue tomorrow with a 15x15 board and see if it can perform in a similar way. — oldfield33, Dec 01 '18 at 00:46
I have now tested it on a 15x15 board and it no longer crashes. Thank you for your help! — oldfield33, Dec 01 '18 at 08:46

Java Heap Space Issue with my MCTS Gomoku player

1 Answers1