首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >尝试实现极大极小算法时的java.lang.OutOfMemoryError

尝试实现极大极小算法时的java.lang.OutOfMemoryError
EN

Stack Overflow用户
提问于 2020-04-03 05:26:56
回答 1查看 46关注 0票数 0

我在Java中为野生tic tac toe的一个变体实现了minimax算法,我偶然发现了一个问题。我有一个包含游戏网格的Node类、一个作为其子对象的Node对象的ArrayList,以及一个递归实现算法的minimax方法。

我得到的错误是:

代码语言:javascript
复制
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
        at Grid.<init>(Grid.java:35)
        at MiniMax$Node.findChildren(MiniMax.java:27)
        at MiniMax.minimax(MiniMax.java:135)
        at MiniMax.minimax(MiniMax.java:126)
        at MiniMax.minimax(MiniMax.java:139)
        at MiniMax.minimax(MiniMax.java:126)
        at MiniMax.minimax(MiniMax.java:139)
        at MiniMax.minimax(MiniMax.java:126)
        at MiniMax.minimax(MiniMax.java:139)
        at MiniMax.nextMove(MiniMax.java:77)
        at ComputerPlayer.play(ComputerPlayer.java:12)
        at TicTacToe.main(TicTacToe.java:146)

Process finished with exit code 1

我认为问题的出现是因为子节点数量太多(总节点数: 2^8 * 8!)每次都会递归创建并存储到ArrayLists中。

下面是Node类:

代码语言:javascript
复制
 private static class Node
    {
        protected Grid grid;
        protected ArrayList<Node> children;

        public Node(Grid grid)
        {
            this.grid = grid;
            children = new ArrayList<>();
        }

        //Find all possible next moves
        public void findChildren()
        {
            char[][] board = grid.getGrid();
            for(int i = 0; i < board.length; i++)
            {
                for(int j = 0; j < board.length; j++)
                {
                    if(board[i][j] == ' ')
                    {
                        board[i][j] = 'X';
                        children.add(new Node(new Grid(board)));
                        board[i][j] = 'O';
                        children.add( new Node(new Grid(board)));
                        board[i][j] = ' ';
                    }
                }
            }
        }
    }

下面是minimax的实现:

代码语言:javascript
复制
private int minimax(Node state, int depth, boolean isMaximizer)
    {
        //If the game is in a terminal state or has reached the desired depth
        boolean someoneWon = state.grid.someoneHasWon();
        boolean isDraw =  state.grid.isDraw();
        if(someoneWon || isDraw || depth == 3)
        {
            return evaluateState(someoneWon, isDraw, !isMaximizer);//Evaluate the state
        }
        //MAX player's turn
        if(isMaximizer)
        {
            //Find maximum score of all possible state's scores
            int bestScore = Integer.MIN_VALUE;
            state.findChildren();
            for(int i = 0; i < state.children.size(); i++)
            {
                Node child = state.children.get(i);
                int score = minimax(child, depth + 1, false);
                bestScore = Math.max(bestScore, score);
            }
            return bestScore;
        }
        else//MIN player's turn
        {
            //Find minimum score of all possible move's scores
            int bestScore = Integer.MAX_VALUE;
            state.findChildren();
            for(int i = 0; i < state.children.size(); i++)
            {
                Node child = state.children.get(i);
                int score = minimax(child, depth + 1, true);
                bestScore = Math.min(bestScore, score);
            }
            return bestScore;
        }
    }
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-04-03 05:29:24

不是创建子节点列表,而是将迭代移动到Node (或等效项。你会注意到,你不需要每次都创建一个新的板子-只需替换你在完成后改变的状态。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/61001409

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档