Minimax for Avalanche version of Mancala: My code returns a bad move

Question

I have been making a mancala bot using a minimax algorithm. It works for the first bit but it often just gives an output landing on a blank space. Anyone have any idea how to fix this so it plays well?

Here is my code:

let final;
function increment(board, ltif, player, re) {
    let a = 0;
    for(let i = 0; i < board[ltif]; i++) {
        if((player && (ltif+i+a+1)%14 == 13) || (!player && (ltif+i+a+1)%14 == 6)) {
            a += 1;
        }
        board[(ltif + i + a + 1)%14] += 1;
    }
    const bltif = board[ltif];
    board[ltif] = 0;
    let ans;
    board[(bltif + ltif + a)%14] == 1 || (bltif + ltif + a)%14 == 6 || (bltif + ltif + a)%14 == 13 ? ans = board : ans = increment(board, (bltif + ltif + a)%14, player);
    if(((bltif + ltif + a)%14 == 6 || (bltif + ltif + a)%14 == 13) && !re) {
        ans = 2;;
        }
    if(board[(bltif + ltif + a)%14] == 1 && !re) {
        ans = 3;
    }
    return ans;
}
function minimax(board, depth, player) {
    if(board[6] > 24) {
        return 15;
    }else if(board[13] > 24) {
        return -15;
    }else if(board[6] == 24 && board[13] == 24) {
        return 0;
    }else if(depth === 0) {
        return Math.floor((board[6]-board[13])/2);
    }
    let avail = board.map((element, index) => (element !== 0 && ((index < 6 && player)|| (index < 13 && index > 6 && !player)) ? index : -1)).filter(element => element !== -1);
    if(player) {
        let maxEval = [-Infinity];
        for(let i = 0; i < avail.length; i++) {
            let tboard = increment(board.slice(), avail[i], player, false);
            let Eval;
            if(tboard == 2) {
                Eval = 13;
                tboard = increment(board.slice(), avail[i], player, true);
            }else if(tboard == 3) {
                Eval = -13;
                tboard = increment(board.slice(), avail[i], player, true);
            }else{
                Eval = minimax(tboard, depth - 1, false);
            }
            maxEval = [Math.max(Eval, maxEval[0]),avail[i],tboard];
        }
        final = [maxEval[1], maxEval[2]];
        return maxEval[0];
    }else{
        let minEval = +Infinity;
        for(let i = 0; i < avail.length; i++) {
            let tboard = increment(board.slice(), avail[i], player, false);
            let Eval;
            if(tboard == 2) {
                Eval = 13;
                tboard = increment(board.slice(), avail[i], player, true);
            }else if(tboard == 3) {
                Eval = -13;
                tboard = increment(board.slice(), avail[i], player, true);
            }else{
                Eval = minimax(tboard, depth - 1, false);
            }
            minEval = Math.min(Eval, minEval);
        }
    return minEval;
    }
}
minimax([
    5, 0, 5, 5, 5, 0,
    3, 5, 5, 0, 5, 5,
    5, 0
  ], 9, true);
console.log(final);

It runs out of a text based editor so that's why the output is into console and it only checks one board then you have to input another. Also just to clarify it is the avalanche version of mancala.

I do not have much experience using a minimax algorithm so if anyone has any insight into the problem that would be very helpful.

One example of this is that when given the board state:

[4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4, 0] 

...it tells me to move the one on the 4th spot of the array so 5 from the right which gives this output:

[1, 6, 6, 6, 0, 1, 3, 6, 1, 6, 6, 0, 6, 0]

There are much better possible moves (like index 2) and I have no idea why the algorithm is selecting this. Also, the minimax algorithm I am using does not use alpha-beta pruning which is intended and not just a mistake in the code.

Answer 1

There are the following issues in your implementation:

• Note that in minimax the first call of increment can only return 2 or 3. This is because increment will keep making recursive calls as long as the stop condition is not true. And when the stop is true, it returns 2 or 3 (in case re is false). By consequence, minimax will never make a recursive call with depth-1! I would suggest to solve this as follows. Don't stop the recursion when tboard == 3. This is the case when a turn ends "normally", i.e. without the right to get an extra turn. In that case there is no reason why the recursion should stop. So make the recursive call in that case, instead of setting Eval to -13.
• if(board[(bltif + ltif + a)%14] == 1 && !re) is a bug. This should be an else because you don't want to overwrite ans with 3 when it was already set to 2, but the player's store happens to have 1 stone in it. And in the else case you can be sure that this condition is true, so it is not needed to evaluate it. Alternatively, you could return ans in the if block so there is no risk of overwriting that ans with 3.
• maxEval = [Math.max(Eval, maxEval[0]),avail[i],tboard]; is wrong, because it updates the second and third entry of maxEval even when Eval is worse. This way you lose the move that was already associated with the best score. You should only update maxEval[1] and maxEval[2] when Eval is better than maxEval[0]. (I would also suggest using a plain object for this instead of an array. With a plain object we can give meaningful names to the three components).
• final = [maxEval[1], maxEval[2]]; is wrong because it is also executed at deeper levels in the recursion tree, overwriting the result that was already registered at the top of the recursion tree, which is the result you are really interested in. The deeper problem here is that final should not be a global variable which minimax is altering as a "side-effect". This is bad practice. Instead, have minimax return that information.
• For both the maximizing and minimizing user your code gives a score of 13 if they played a good move (as they achieved an extra turn). This cannot be right. The value should be -13 for the minimizing user, otherwise it will actually serve as a bad move!

Other remarks:

• Use more descriptive variables names. For example, numStones instead of bltif.
• Avoid repeating the same expression like (bltif + ltif + a)%14. Instead have a variable dedicated to represent that value. You should only need one occurrence of the % 14 operation in your code.
• Avoid calling increment twice on the same board only to get two different pieces of information from it, based on re. If you would just store board.slice() in a variable before calling increment, you would already have the mutated board after the increment call. That way you don't need the call with re set to true, and can get rid of that parameter.
• Avoid using "magic numbers". For instance, the return values 2 and 3 should be explained and better be replaced with constants that have descriptive names. However, in this particular case we could just use a boolean instead (with a descriptive name), which indicates whether the player has the right to an extra move or not.
• Don't perform an assignment (like ans = board) inside a larger expression. Convert such an expression to an assignment, where the right hand expression has the necessary logic.
• Use camelCase for variables, so don't use Eval as a name. I would suggest score (as eval is already used for a native function).
• To determine avail, don't use .map, but use .filter immediately. That way you don't need the virtual -1 value.

Corrected code

Here is the code I ended up with while applying the above corrections and suggestions:

// Don't use magic values, but instead define constants with meaningful names:
const STORE = { false: 13, true: 6 }; // Per player: the index of their store
const STORES = new Set(Object.values(STORE));
      // Per player: the indices of their pits 
const PITS = { false: [7, 8, 9, 10, 11, 12], true: [0, 1, 2, 3, 4, 5] };
const NUM_STONES = 48;
const GOOD_SCORE = NUM_STONES / 4 + 1; // Better score than max heuristic score
const MAX_SCORE = GOOD_SCORE + 1; // Overall best possible score

// The function increment returns a boolean that is true when the move ended with a stone 
//     in the player's store, giving them a right to an extra move.
//     The given board is mutated, so the caller can see the effect of the move in that board.
function increment(board, startPit, player) {
    const numStones = board[startPit];
    let lastPit = startPit;
    for (let i = 1; i <= board[startPit]; i++) {
        // We can use a conditional inline expression to decide to add an extra 1 or not.
        lastPit = (lastPit + 1 + (lastPit + 1 == STORE[!player])) % board.length;
        board[lastPit]++;
    }
    board[startPit] = 0;
    // There are three cases:
    if (lastPit === STORE[player]) { // Extra turn!
        return true;
    }
    if (board[lastPit] == 1) { // Normal move ended.
        return false;
    }
    // The turn is not finished yet; continue...
    return increment(board, lastPit, player);
}

function minimax(board, depth, player) {
    if (board[STORE[true]] * 2 > NUM_STONES) {
        // Maximizing player has more than half of the stones, so they won the game.
        return MAX_SCORE;
    } else if (board[STORE[false]] * 2 > NUM_STONES) {
        // Minimizing player has more than half of the stones, so they won the game.
        return -MAX_SCORE;
    } else if (board[STORE[true]] + board[STORE[false]] == NUM_STONES) {
        // All stones are in the stores, and both players have an equal amount: it's draw
        return 0;
    } else if (depth === 0) {
        // Search must stop here. Give a heuristic value:
        return Math.floor((board[STORE[true]] - board[STORE[false]]) / 2);
    }
    // Get the player's own pits that have at least one stone in it:
    const availablePits = PITS[player].filter(pit => board[pit]); 
    if (player) { // Maximizing player
        let best = { score: -Infinity };
        for (const pit of availablePits) {
            const newBoard = board.slice(); // Keep a reference to the new board
            const extraTurn = increment(newBoard, pit, player);
            const score = extraTurn ? GOOD_SCORE // We get an extra turn (good!), so we will not look deeper
                                      // Otherwise: no extra turn. Continue the recursion.
                                    : minimax(newBoard, depth - 1, false).score; // Get score component
            if (score > best.score) {
                // Only make updates when the score is better
                best = { score, pit, board: newBoard };
            }
        }
        return best; // Don't alter a global. Just return complete information: {score, pit, board}.
    } else {
        let best = { score: +Infinity };
        for (const pit of availablePits) {
            const newBoard = board.slice(); 
            const extraTurn = increment(newBoard, pit, player);
            const score = extraTurn ? -GOOD_SCORE // Minimizing user wants a negative value here!
                                    : minimax(newBoard, depth - 1, false).score;
            if (score < best.score) {
                best = { score, pit, board: newBoard };
            }
        }
        return best;
    }
}

// Minimax should *return* the information instead of setting a global variable.
const { score, pit, board } = minimax([ 
    // Layout was confusing. This seems clearer:
    5, 0, 5, 5, 5, 0,     3, 
    5, 5, 0, 5, 5, 5,     0
  ], 9, true);

console.log(`The best move is from pit ${pit}. It got score ${score}, and leads to this board: ${board}`);

The algorithm now returns as best move, pit number 2. I didn't play this game enough to judge whether that is really the best move or not.