协助使用Javascript中的连接四的最小最大算法

Assistance with minimax algorithm for connect four in Javascript

本文关键字:算法 连接 Javascript      更新时间:2023-09-26

我正试图在我的connect four游戏中使用minimax算法创建AI,但我很难让它发挥作用。我相信我已经很接近了,但仍然无法纠正。有人能帮我纠正错误吗?我意识到我的代码不太好,因为我对Javascript的效率还不高,这就是为什么我想尝试一下。如果我完全偏离了轨道,有人能告诉我一个更好的方法吗?提前谢谢。

编辑:我已经用我更新的代码替换了下面的代码。它现在"有效"地为我提供人工智能动作,但问题是它们不是"智能"动作。我看过无数的极小极大定义,我觉得我已经正确地实现了它。即使我的深度达到7,一个5岁的孩子也能打败它。任何帮助都将不胜感激。

    function getBestMove(currBoard,depth,who) {
        var opp;
        //Get opponent for next piece
        if(who == 'a') {
            opp = 'p';
        } else {
            opp = 'a';
        }
        var tBoard = new Array(rows);
        for(var i=0; i<tBoard.length; i++) {
            tBoard[i] = new Array(cols);
        }
        var moves = new Array(aiOpenCols.length);
        //Drop each piece and use minimax function until depth == 0
        for(var i=0; i<aiOpenCols.length; i++) {
            for(var j=0; j<rows; j++) {
                for(var k=0; k<cols; k++) {
                    tBoard[j][k] = currBoard[j][k];
                }
            }
            tBoard = dropPiece(aiOpenCols[i],who,tBoard);
            moves[i] = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]);
        }
        var bestAlpha = -100000;    //Large negative
        //Use random column if no moves are "good"
        var bestMove = Math.floor(Math.random() * aiOpenCols.length);
        bestMove = +aiOpenCols[bestMove];
        //Get largest value from moves for best move
        for(var i=0; i<aiOpenCols.length; i++) {
            if(+moves[i] > bestAlpha) {
                bestAlpha = moves[i];
                bestMove = aiOpenCols[i];
            }
        }
        bestMove++; //Offset by 1 due to actual drop function
        return bestMove;
    }
    function minimax(currBoard,depth,who,col) {
        //Drop current piece, called from getBestMove function
        currBoard = dropPiece(col,who,currBoard);
        //When depth == 0 return heuristic/eval of board
        if(+depth == 0) {
            var ev = evalMove(currBoard);
            return ev;
        }
        var alpha = -100000;    //Large negative
        var opp;
        //Get opponent for next piece
        if(who == 'a') {
            opp = 'p';
        } else {
            opp = 'a';
        }
        //Loop through all available moves
        for(var i=0; i<aiOpenCols.length; i++) {
            var tBoard = new Array(rows);
            for(var i=0; i<tBoard.length; i++) {
                tBoard[i] = new Array(cols);
            }
            for(var j=0; j<rows; j++) {
                for(var k=0; k<cols; k++) {
                    tBoard[j][k] = currBoard[j][k];
                }
            }
            //Continue recursive minimax until depth == 0
            var next = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]);
            //Alpha = max(alpha, -minimax()) for negamax
            alpha = Math.max(alpha, (0 - +next));
        }
        return alpha;
    }
    function evalMove(currBoard) {
        //heuristic function
        //AI = # of 4 streaks + # of 3 streaks + # of 2 streaks - # of 3 streaks opp - # of 2 streaks opp           
        var fours = checkFours(currBoard,'b') * 1000;
        var threes = checkThrees(currBoard,'b') * 100;
        var twos = checkTwos(currBoard,'b') * 10;
        var oppThrees = checkThrees(currBoard,'r') * 100;
        var oppTwos = checkTwos(currBoard,'r') * 10;
        var scores = fours + threes + twos - oppThrees - oppTwos;
        //If opponent wins, return large negative
        var oppFours = checkFours(currBoard,'r');
        if(+oppFours > 0) {
            return -100000;
        } else {
            return scores;
        }
    }
    function dropPiece(col,who,currBoard) {
        for(var i=0; i<currBoard.length; i++) {
            if(currBoard[i][col] != 'w') {
                //Make sure column isn't full
                if(i != 0) {
                    if(who == 'p') {
                        currBoard[i-1][col] = 'r';
                    } else {
                        currBoard[i-1][col] = 'b';
                    }
                    break;
                }
            }
            //If column is empty, place in first row
            if(i == (currBoard.length - 1)) {
                if(who == 'p') {
                    currBoard[i][col] = 'r';
                } else {
                    currBoard[i][col] = 'b';
                }
            }
        }
        return currBoard;
    }

您的求值函数正在为没有值的位置特征赋值。在一行中有两个连续单元格没有任何值。如果第四个单元格可以被对手占据而不允许在其他地方获胜,那么连续三个单元格也没有价值。

简化。对于Connect Four,你只需要关心这个位置是赢还是输,或者这个位置在下一步是否可以赢或输。如果获胜,则返回一个较大的正值。如果是损失,返回一个大的负值。如果下一步可以赢得或失去位置,则将搜索深度扩展到此分支的一层,然后再次调用minimax(),返回结果。后者将避免所有固定深度最小极大搜索都容易受到的地平线效应。否则返回零。