java - Minmax 算法不返回根的直接子代(返回非法移动)

Question

我正在尝试为九人莫里斯创建“AI”，但我在 minMax 算法上遇到了困难。总结一下，我花了10多个小时试图找到问题，但没有成功。 (调试这个递归很糟糕，或者我做得很糟糕，或者两者兼而有之)

自从我开始怀疑我写的所有内容后，我决定发布我的问题，以便有人可以发现我的 minMax 版本中的任何问题。我意识到如果没有整个应用程序，这确实是一项艰巨的任务，因此也非常欢迎任何我应该三次检查我的代码的建议。

这里是视频链接，解释了 minMax，我的实现基于该视频:https://www.youtube.com/watch?v=l-hh51ncgDI (搜索 minmax 后在 yt 上弹出的第一个视频 - 以防万一您想观看视频但不想点击链接)

我的 minMax 没有 alpha-beta 剪枝:

    //turn - tells which player is going to move
//gameStage - what action can be done in this move, where possible actions are: put pawn, move pawn, take opponent's pawn
//depth - tells how far down the game tree should minMax go
//spots - game board
private int minMax(int depth, Turn turn, GameStage gameStage, Spot[] spots){
    if(depth==0){
        return evaluateBoard(spots);
    }

    //in my scenario I am playing as WHITE and "AI" is playing as BLACK
    //since heuristic (evaluateBoard) returns number equal to black pawns - white pawns
    //I have decided that in my minMax algorithm every white turn will try to minimize and black turn will try to maximize
    //I dont know if this is correct approach but It seems logical to me so let me know if this is wrong
    boolean isMaximizing = turn.equals(Turn.BLACK);

    //get all possible (legal) actions based on circumstances
    ArrayList<Action> children = gameManager.getAllPossibleActions(spots,turn,gameStage);

    //this object will hold information about game circumstances after applying child move
    //and this information will be passed in recursive call
    ActionResult result;

    //placeholder for value returned by minMax()
    int eval;

    //scenario for maximizing player
    if(isMaximizing){
        int maxEval = NEGATIVE_INF;
        for (Action child : children){
            //aplying possible action (child) and passing its result to recursive call
            result = gameManager.applyMove(child,turn,spots);

            //evaluate child move
            eval = minMax(depth-1,result.getTurn(),result.getGameStage(),result.getSpots());

            //resets board (which is array of Spots) so that board is not changed after minMax algorithm
            //because I am working on the original board to avoid time consuming copies
            gameManager.unapplyMove(child,turn,spots,result);

            if(maxEval<eval){
                maxEval = eval;

                //assign child with the biggest value to global static reference
                Instances.theBestAction = child;
            }
        }
        return maxEval;
    }
    //scenario for minimizing player - the same logic as for maximizing player but for minimizing
    else{
        int minEval = POSITIVE_INF;
        for (Action child : children){
            result = engine.getGameManager().applyMove(child,turn,spots);
            eval = minMax(depth-1,result.getTurn(),result.getGameStage(),result.getSpots());
            engine.getGameManager().unapplyMove(child,turn,spots,result);
            if(minEval>eval){
                minEval=eval;
                Instances.theBestAction = child;
            }
        }
        return minEval;
    }
}

简单的启发式评估:

//calculates the difference between black pawns on board
//and white pawns on board
public int evaluateBoard(Spot[] spots) {
    int value = 0;
    for (Spot spot : spots) {
        if (spot.getTurn().equals(Turn.BLACK)) {
            value++;
        }else if(spot.getTurn().equals(Turn.WHITE)){
            value--;
        }
    }
    return value;
}

我的问题:

    //the same parameters as in minMax() function
public void checkMove(GameStage gameStage, Turn turn, Spot[] spots) {

    //one of these must be returned by minMax() function
    //because these are the only legal actions that can be done in this turn
    ArrayList<Action> possibleActions = gameManager.getAllPossibleActions(spots,turn,gameStage);

    //I ignore int returned by minMax() because,
    //after execution of this function, action choosed by minMax()  is assigned
    //to global static reference
    minMax(1,turn,gameStage,spots);

    //getting action choosed by minMax() from global
    //static reference
    Action aiAction = Instances.theBestAction;

    //flag to check if aiAction is in possibleActions
    boolean wasFound = false;

    //find the same action returned by minMax() in possibleActions
    //change the flag upon finding one
    for(Action possibleAction : possibleActions){
        if(possibleAction.getStartSpotId() == aiAction.getStartSpotId() &&
                possibleAction.getEndSpotId() == aiAction.getEndSpotId() &&
                possibleAction.getActionType().equals(aiAction.getActionType())){
            wasFound = true;
            break;
        }
    }
    //when depth is equal to 1 it always is true
    //because there is no other choice, but
    //when depth>1 it really soon is false
    //so direct child of root is not chosen
    System.out.println("wasFound?: "+wasFound);
}

我实现 minMax 算法背后的想法是否正确？

Answer 1

我认为错误可能存在，因为您甚至在评估子移动时也在更新Instances.theBestAction。

例如，假设“Move 4”是最终返回的真正最佳 Action ，但在评估“Move 5”时，theBestAction 设置为“Move 5”的最佳子 Action '。从此时起，您将不会将原始 theBestAction 更新回“Move 4”。

也许只是一个简单的条件，仅在深度==originalDepth时设置theBestAction？

您还可以考虑返回一个包含最佳得分和获得得分的移动的结构/对象，而不是使用全局变量。