Question

I am trying to create AI in my connect four game using the minimax algorithm, but I'm having trouble getting it to work. I believe I'm very close, but am still unable to get it correct. Could anyone please assist me in any errors? I realize my code is not great, as I am not very efficient with Javascript yet, which is why I wanted to try this out. If I am totally off track, could someone please inform me of a better approach? Thanks in advance.

EDIT: I have replaced my code below with my updated code. It now "works" as far as giving me AI moves, but the problem is that they are not "intelligent" moves. I've looked at numerous minimax definitions and I feel that I've implemented it correctly. Even when I go to about a depth of 7, a 5 year old could beat it. Any help would be appreciated.

    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;
    }
Was it helpful?

Solution

Your evaluation function is assigning value to positional features that have no value. Having two contiguous cells in a row has no value. Having three in a row has no value either if the fourth cell can be occupied by the opponent without allowing a win elsewhere.

Simplify. For Connect Four you only need to care about whether the position is a win or a loss or if the position can be won or lost on the next move. If it's a win, return a large positive value. If it's a loss, return a large negative value. If the position can be won or lost on the next move, extend the search depth one ply for this branch and call minimax() again, returning the result. The latter will avoid the horizon effect to which all fixed depth minimax searches are susceptible. Otherwise return zero.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top