Can't implement alpha beta pruning on negamax

194 Views Asked by At

I'm struggling to get this code working, there is a problem somewhere but I can't understand where.

I'm developing a simple AI for a generalized TicTacToe and I would like to use negamax instead of MiniMax, with alpha-beta pruning.

The problem is that the algorithm works fine if I don't prune at the end, but as soon as I uncomment the pruning it stops working.

This is the main cicle where I call the minimax algorithm:

//Cycle through all possible cells
    for(MNKCell d : FC) {

        B.markCell(d.i, d.j);

        //Apply minimax algorithm on the cell
        Integer MoveVal = -negaMax(-1, Integer.MAX_VALUE, Integer.MIN_VALUE);

        B.unmarkCell();

        //DEBUG
        Debug.PrintMiddleCicle(B, d, MoveVal);

        //Check if found a better move
        if(MoveVal > MaxMoveValue){
            MaxMoveValue = MoveVal;
            BestMove = d;
        }

    }

This is the algorithm:

public Integer negaMax(int sign, int alpha, int beta){

    //Base case, evaluation detected gameover or timeout soon
    if(B.gameState() != MNKGameState.OPEN || utility.isTimeExpiring())// || depth == 0)
    {
        return utility.evaluateBoard(B,0)*sign;
    }

        //Relax technique, assume the worst case scenario and relax on each step
        Integer bestValue = Integer.MIN_VALUE;

        //Cycle through all possible moves
        MNKCell FC[] = B.getFreeCells();
        for(MNKCell current : FC) {

            //Mark this cell as player move
            B.markCell(current.i, current.j);

            //Recursively call minmax on this board scenario
            bestValue = Math.max(bestValue, -negaMax(-sign, -alpha, -beta));
            alpha = Math.max(alpha, bestValue);

            //Revert move 
            B.unmarkCell();
    
            //if(alpha >= beta)
            //  break;
        }

        //Return the best value obtained
        return bestValue;
}

I know that there is a problem because I implemented a function that outputs the best possible evaluation for each cell (PrintMiddleCicle in the main cicle), these are the outputs with pruning off in a 3x3 game:

Pruning off

And these are the outputs with pruning on:

Pruning on

I know the first one is correct because with an empty table in a 3x3 game, assuming both players with perfect strategy, every cell should point to a draw (evaluation=0)

0

There are 0 best solutions below