Minimax caching changing result of the algorithm?

Question

I wrote this minimax algorithm in javascript for a connect four game. I implemented alpha beta pruning (which greatly sped up the algorithm) and tried to further speed it up via a hashtable. However, instead of speeding up the algorithm, my bot started making different moves. Since I am using a deterministic algorithm, I am pretty sure adding a cache should not change my moves. I am wondering what I did wrong with this cache? Additionally, is there anything beyond this I can do to improve my algorithm, beyond improving my heuristic?

Here is the algorithm

GameLogic.prototype = {
    nextMove: function(board, currentPlayer, alpha, beta, depth, cache) {
        if (depth >= this.maxDepth) {
            return this.scoreBoard(board);
        }
        var best = 0;
        var alphas = [];
        var moves = board.getMoves();
        var key = board.key();
        if (key in cache) { //see if we can return immediately
            return cache[key]; 
            console.log("cached result");
        } 
        if (currentPlayer === comp) {
            best = this.loseScore; //maximizing player
            for (move in moves) {
                var boardCopy = board.copy();
                if (boardCopy.checkWin(moves[move], comp)) {
                    if (depth === 0) {
                        this.bestMove = moves[move];
                    }
                    return (this.winScore - depth);
                } else {
                    boardCopy.play(moves[move], comp);
                    var sub = this.nextMove(boardCopy, player, alpha, beta, depth + 1, cache);
                    best = Math.max(best, sub);
                    alpha = Math.max(alpha, sub);
                    if (alpha >= beta) {
                        break;
                    }
                }
                if (depth === 0) {
                    alphas.push(best);
                }
            }
        } else {
            best = this.winScore; //minimizing player
            for(move in moves) {
                var boardCopy = board.copy();
                if (boardCopy.checkWin(moves[move], player)) {
                    return (this.loseScore + depth);
                } else {
                    boardCopy.play(moves[move], player);
                    var sub = this.nextMove(boardCopy, comp, alpha, beta, depth + 1, cache);
                    best = Math.min(best, sub);
                    beta = Math.min(beta, sub);
                    if (beta <= alpha) {
                        break;
                    }
                }
            }
        }
        if (depth === 0) {
            var bestValue = -1001;
            for(var i = 0; i < alphas.length; i++) {
                if (alphas[i] > bestValue) {
                    bestValue = alphas[i];
                    this.bestMove = moves[i];
                }
            }
        }
        cache[key] = best; //save the best move for this state
        return best;
    }
}

Here is my board so you can see the key function.

var Board = function() { //board is just an array of 0, 1, or 2
key: function() {
        var key = "";
        for(var i = 10; i < 63; i++) {
            if (i % 8 != 0 && i % 9 != 0) {
                key = key + this.gameState[i]; //makes a string of the board, ignoring the 1 row and 1 column border I put on each side to make checking wins easier
            }
        }
        return key;
    }

Thank you very much for any help.

Answer 1

You actually have an implementation error in your Board (assuming that with row in board.play() you actually mean column:

...
b.key(); // "121212000000000000000000000000000000000000"
b.play(7, 1);
b.key(); // "121212000000000000000000000000000000000000" <-- key does not change!
b.play(1, 1);
b.key(); // "121212010000000000000000000000000000000000"

This would explain why you might have hash collisions.