Проблема с кучей Java в моем плеере 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$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)

Я использовал тот же код MCTS для платы размером 3х3, которая не дает сбоя и быстро возвращает конкурентный ход. Но когда я пытаюсь использовать его для доски размером 15x15, игра вылетает после 1235 итераций с указанной выше ошибкой.

Я думаю, что справился с симптомом проблемы, не допуская расширения любого узла после 1235 итераций. Это в конечном итоге возвращает конкурентное движение, хотя пройдет много времени, прежде чем это произойдет.

Для меня основной причиной является размер дерева, которое я пытаюсь создать, поскольку тот же код работал с платой 3х3, но не с платой 15х15; Размер дерева, содержащего все объекты узлов, слишком велик. Следовательно, это просто проблема с этим подходом, а не с моим кодированием.

Я подумал, что смогу попробовать: после x итераций, если узел был посещен y раз, но выигрыш ниже z, тогда удалите этот узел. Я думаю, что если после x итераций и посещения y раз, но по-прежнему низкий выигрыш, то этот узел, вероятно, занимает ненужное место в дереве и, следовательно, может позволить себе быть удаленным.

Мой вопрос:

Есть ли лучший способ для моей программы возвращать движение, а не сбой, не уменьшая количество расширений и не выполняя вышеуказанную проверку? (Даже если лучший ход занимает много времени для расчета).

Вот часть моего неотредактированного кода:

ИЗМЕНЕНО ** Функция расширения 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();
  }

Недавно включенный ниже **

Выберите начальную функцию узла (будет продолжаться до тех пор, пока размер списка возможных перемещений не будет == до 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 возможные ходы, оставшиеся: "+initialNode.getPossibleMovesSize()); } return initialNode; }

Выберите функцию:

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

Я не уверен на 100%, не видя код методов, таких как childrenLeft() и несколько других, но у меня складывается впечатление, что вы в основном добавляете b новые узлы в дереве, где b ваш фактор ветвления. Другими словами, на каждой итерации вы добавляете новый, полный список дочерних элементов в один узел. Это, вероятно, действительно может привести к тому, что вам не хватит памяти быстро.

Безусловно, наиболее распространенной стратегией является расширение вашего дерева путем добавления только одного нового узла за итерацию. Тогда каждому узлу необходимо:

• Список текущих детей (соответствует уже развернутым действиям)
• Список действий, которые еще не были расширены

Фаза выбора, как правило, заканчивается, как только он достигает узла, у которого есть непустой список действий, которые необходимо расширить. Затем MCTS случайным образом выберет одно действие из этого списка, добавит новый узел, соответствующий этому действию (то есть ваш первый список увеличивается на одну запись, а второй список уменьшится на одну запись), и продолжит развертывание оттуда.

При такой реализации маловероятно, что не хватит памяти, если вы не позволите вашему алгоритму выполнять поиск очень долго. Если вам все еще не хватает памяти, вы можете посмотреть на такие вещи, как:

• Оптимизация объема памяти, требуемой для узла (он хранит полные игровые состояния, оптимизировано ли использование памяти игровыми состояниями?)
• Увеличение размера кучи JVM с помощью аргументов командной строки (см. Увеличение размера кучи в Java)