Connect 4 minimax does not make the best move

Question

I'm trying to implement an algorithm that would choose the optimal next move for the game of Connect 4. As I just want to make sure that the basic minimax works correctly, I am actually testing it like a Connect 3 on a 4x4 field. This way I don't need the alpha-beta pruning, and it's more obvious when the algorithm makes a stupid move.

The problem is that the algorithm always starts the game with the leftmost move, and also during the game it's just very stupid. It doesn't see the best moves.

I have thoroughly tested methods makeMove(), undoMove(), getAvailableColumns(), isWinningMove() and isLastSpot() so I am absolutely sure that the problem is not there.

Here is my algorithm.

NextMove.java

private static class NextMove {
    final int evaluation;
    final int moveIndex;

    public NextMove(int eval, int moveIndex) {
        this.evaluation = eval;
        this.moveIndex = moveIndex;
    }

    int getEvaluation() {
        return evaluation;
    }

    public int getMoveIndex() {
        return moveIndex;
    }
}

The Algorithm

private static NextMove max(C4Field field, int movePlayed) {
    // moveIndex previously validated
    
    // 1) check if moveIndex is a final move to make on a given field
    field.undoMove(movePlayed);
    
    // check
    if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(BLUE_WIN, movePlayed);
    }
    if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(RED_WIN, movePlayed);
    }
    if (field.isLastSpot()) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(DRAW, movePlayed);
    }
    
    field.playMove(movePlayed, C4Symbol.RED);
    
    // 2) moveIndex is not a final move
    // --> try all possible next moves
    final List<Integer> possibleMoves = field.getAvailableColumns();
    int bestEval = Integer.MIN_VALUE;
    int bestMove = 0;
    for (int moveIndex : possibleMoves) {           
        field.playMove(moveIndex, C4Symbol.BLUE);
        
        final int currentEval = min(field, moveIndex).getEvaluation();
        if (currentEval > bestEval) {
            bestEval = currentEval;
            bestMove = moveIndex;
        }

        field.undoMove(moveIndex);
    }
    
    return new NextMove(bestEval, bestMove);
}

private static NextMove min(C4Field field, int movePlayed) {
    // moveIndex previously validated
    
    // 1) check if moveIndex is a final move to make on a given field
    field.undoMove(movePlayed);
    
    // check
    if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(BLUE_WIN, movePlayed);
    }
    if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(RED_WIN, movePlayed);
    }
    if (field.isLastSpot()) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(DRAW, movePlayed);
    }
    
    field.playMove(movePlayed, C4Symbol.BLUE);
    
    // 2) moveIndex is not a final move
    // --> try all other moves
    final List<Integer> possibleMoves = field.getAvailableColumns();
    int bestEval = Integer.MAX_VALUE;
    int bestMove = 0;
    for (int moveIndex : possibleMoves) {
        field.playMove(moveIndex, C4Symbol.RED);
        
        final int currentEval = max(field, moveIndex).getEvaluation();
        if (currentEval < bestEval) {
            bestEval = currentEval;
            bestMove = moveIndex;
        }
        
        field.undoMove(moveIndex);
    }
    
    return new NextMove(bestEval, bestMove);
}

The idea is that the algorithm takes in the arguments of a currentField and the lastPlayedMove. Then it checks if the last move somehow finished the game. If it did, I just return that move, and otherwise I go in-depth with the subsequent moves.

Blue player is MAX, red player is MIN.

In each step I first undo the last move, because it's easier to check if the "next" move will finish the game, than check if the current field is finished (this would require to analyze for all possible winning options in the field). After I check, I just redo the move.

From some reason this doesn't work. I am stuck with that for days! I have no idea what's wrong... Any help greatly appreciated!

EDIT

I'm adding the code how I'm invoking the algorithm.

@Override
public int nextMove(C4Game game) {
    C4Field field = game.getCurrentField();
    C4Field tmp = C4Field.copyField(field);

    int moveIndex = tmp.getAvailableColumns().get(0);
    final C4Symbol symbol = game.getPlayerToMove().getSymbol().equals(C4Symbol.BLUE) ? C4Symbol.RED : C4Symbol.BLUE;
    tmp.dropToColumn(moveIndex, symbol);

    NextMove mv = symbol
            .equals(C4Symbol.BLUE) ? 
                    max(tmp, moveIndex) : 
                        min(tmp, moveIndex);

                    int move = mv.getMoveIndex();
                    return move;
}

Answer 1

I suspect that you'll have to remove this code:

    if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(BLUE_WIN, movePlayed);
    }

from the max() method, and remove this code:

    if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(RED_WIN, movePlayed);
    }

from the min() method.

---

In the first case, you're checking whether the move that RED just made was a winning move. You don't want to check there if it was a winning move from BLUE, because it wasn't BLUE who just made that move; it was red. The same counts the other way around in the second case.

---

Additionally, the initial call into the algorithm seems overly complicated. I am not sure what the intended use of the tmp variable there is, or that dropToColumn() call. I would rewrite it to be more like:

@Override
public int nextMove(C4Game game) {
    C4Field field = game.getCurrentField();

    NextMove mv = null;

    if(game.getPlayerToMove().getSymbol().equals(C4Symbol.BLUE)){
        mv = max(field, -1);
    }
    else{
        mv = min(field, -1);
    }

    return mv.getMoveIndex();
}

This will require an adaptation of the max() and min() methods such that they skip the whole checking-for-wins thing if the previous movePlayed equals -1.

With the code you currently have there, you do not perform a minimax search for the optimal move in the current game state; instead you first arbitrarily modify the current game state using that tmp.dropToColumn() call, and perform the minimax search in that arbitrarily modified game state. The optimal move to play in such an arbitrarily-modified game state will tend not to be the optimal move in the game state that you really are in.