Java 堆 Space 我的 MCTS Gomoku 播放器出现问题

Question

当我运行我的程序出现此错误时：

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[=12=](NewBoardGUI.java:584)
        at NewBoardGUI$$Lambda5/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.access0(Unknown Source)
        at java.desktop/java.awt.EventQueue.run(Unknown Source)
        at java.desktop/java.awt.EventQueue.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.run(Unknown Source)

我对 3x3 板尺寸使用了相同的 MCTS 代码，它不会崩溃，return这是一个快速的竞争举措。但是当我尝试将它用于 15x15 的棋盘尺寸时，游戏在 1235 次迭代后崩溃，并出现上述错误。

我想我已经通过在 1235 次迭代后不允许扩展任何节点来处理问题的症状。这最终确实 return 一个有竞争力的举动，尽管这需要很长时间才能发生。

对我来说，根本原因是我要创建的树的大小，因为相同的代码适用于 3x3 板，但不适用于 15x15 板；包含所有节点对象的树的大小太大了。因此，这只是这种方法的问题，而不是我的编码问题。

我确实认为我可以尝试：在 x 次迭代后，如果一个节点已被访问 y 次但获胜分数低于 z，则删除该节点。我的想法是，如果在 x 次迭代后，被访问了 y 次，但获胜分数仍然很低，那么这个节点很可能在树中占据了不必要的 space，因此可以删除。

我的问题是：

有没有更好的方法让我的程序 return 移动而不是崩溃，而不仅仅是减少扩展的数量并且不必执行上述检查？（即使最好的走法需要很长时间才能计算出来）。

这是我的一些未经编辑的代码：

已编辑** MCTS 扩展函数：

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 函数：

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();
  }

下面新包含**

Select初始节点函数（将继续直到可能的移动列表大小==到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初始节点； }

Select 函数:

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 函数：

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

Answer 1

如果没有看到 childrenLeft() 和其他一些方法的代码，我不能 100% 确定，但我的印象是您基本上向树中添加了 b 个新节点，其中b 是您的分支因子。换句话说，每次迭代，您都会向一个节点添加一个新的、完整的子节点列表。这可能确实会导致您很快运行内存不足。

到目前为止，最常见的策略是通过每次迭代仅添加一个新节点来扩展树。然后每个节点需要：

当前子列表（对应已经展开的动作）
尚未展开的操作列表

您的选择阶段通常会在到达具有要展开的非空操作列表的节点时结束。 MCTS 然后会从该列表中随机选择一个动作，添加一个与该动作对应的新节点（意味着您的第一个列表增加一个条目，第二个列表缩小一个条目），然后从那里继续推出。

使用这样的实现，应该不太可能运行内存不足，除非您允许您的算法搜索很长时间。如果您仍然运行内存不足，您可以查看以下内容：

优化每个节点所需的内存量（它存储完整的游戏状态，游戏状态的内存使用是否优化？）
使用命令行参数增加 JVM 的堆大小（参见 Increase heap size in Java）

Java 堆 Space 我的 MCTS Gomoku 播放器出现问题

Java Heap Space Issue with my MCTS Gomoku player

java

montecarlo

tree-search

gomoku

monte-carlo-tree-search