算法的 Minimax 缓存更改结果？

Question

我在 javascript 中为连四游戏编写了这个 minimax 算法。我实施了 alpha beta 修剪（这大大加快了算法速度）并尝试通过哈希表进一步加速它。然而，我的机器人并没有加快算法速度，而是开始做出不同的动作。由于我使用的是确定性算法，我很确定添加缓存不会改变我的动作。我想知道我对这个缓存做错了什么？此外，除了改进我的启发式算法之外，我还能做些什么来改进我的算法吗？

这是算法

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

这是我的开发板，您可以看到关键功能。

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

非常感谢您的帮助。

Answer 1

您实际上在 Board 中有一个实现错误（假设 row 在 board.play() 中您实际上是指 column:

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

这可以解释为什么您可能会发生哈希冲突。

算法的 Minimax 缓存更改结果？

Minimax caching changing result of the algorithm?

javascript

algorithm

caching

minimax