CODEWITHSUNDEEP
javarecursionminmaxgame-theory
hdw3
hdw3

Reputation: 951

Minmax algorithm doesn't return direct child of root (returns illegal move)

I am trying to create "AI" for Nine Men's Morris but I got hardstuck on minMax algorithm. Summing up, I was trying to find the issue for over 10h but didn't manage to. (debugging this recursion is nasty or I am doing it badly or both)

Since I started doubting everything I wrote I decided to post my issue so someone can find anything wrong in my version of minMax. I realise it is really hard task without the whole application so any suggestions where I should triple check my code are also very welcome.

Here is link to the video, explaining minMax, on which I based my implementation: https://www.youtube.com/watch?v=l-hh51ncgDI (First video that pops up on yt after searching for minmax - just in case you want to watch the video and don't want to click the link)

My minMax without alpha-beta pruning:

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

Simple heuristic for evaluation:

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

My issue:

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

Is the idea behind my implementation of minMax algorithm correct?

Upvotes: 1

Views: 120

Answers (1)

Brad S
Brad S

Reputation: 196

I think the error might exist in that you are updating Instances.theBestAction even while evaluating child moves.

For example, lets say 'Move 4' is the true best move that will eventually be returned, but while evaluating 'Move 5', theBestAction is set to the best child action of 'Move 5'. From this point on, you won't update the original theBestAction back to 'Move 4'.

Perhaps just a simple condition that only sets theBestAction when depth == originalDepth?

Rather than using a global, you could also consider returning a struct/object that contains both the best score AND the move that earned the score.

Upvotes: 1

Related Questions