javamontecarlotree-searchgomokumonte-carlo-tree-search

Java Heap Space Issue with my MCTS Gomoku player

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;
}
Solution

  • 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:

    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: