6
$\begingroup$

I have made a connect four game in JS and currently have a functioning minimax algorithm. The problem I'm having is that it is very, very easy to beat, even with a large depth. This is leading me to believe that I need a better heuristic function, but I cannot come up with much better than what I already have. So, I thought I would ask if anyone has any experience, or just a good idea, for a very good heuristic to use. I would also accept improvement ideas on my current heuristic below. Thank you in advance!

EDIT: I'm going to go ahead and post my total minimax in here (3 functions total), because I have added disjoints and made my 4-in-a-row higher, but my AI is still terrible. I know my 2,3 and 4-in-a-rows work because I tested them, but I can't pin-point why I'm still having trouble even at high depths.

    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');
        //If win return large positive
        if(fours > 0) return 100000;
        var threes = checkThrees(currBoard,'b') * 1000;
        var twos = checkTwos(currBoard,'b') * 10;
        var oppThrees = checkThrees(currBoard,'r') * 1000;
        var oppTwos = checkTwos(currBoard,'r') * 10;

        var scores = threes + twos - oppThrees - oppTwos;

        //If opponent wins, return large negative
        var oppFours = checkFours(currBoard,'r');
        if(+oppFours > 0) {
            return -100000;
        } else {
            return scores;
        }
    }
$\endgroup$
6
$\begingroup$

Connect 4 is a solved game - under perfect play, white wins. Victor Allis's thesis contains a winning algorithm for white. The game had been solved a few weeks earlier by James D. Allen. Later on, John Tromp came up with a strategy that will win the game from any position, if possible, and thus solved the game strongly.

$\endgroup$
5
$\begingroup$

Disclaimer:

I'm assuming your minimax works perfectly and your logic of who wins when and when to apply your heuristic how is sound (mainly because you only gave part of your program and partly because it's been a while since I last implemented one of these, so I won't exactly know what to look for) and thus I'm only commenting on your heuristic. Don't assume these parts of your program work, regardless of whatever evidence seems to support this, it helps to be paranoid when it comes to Artificial Intelligence algorithms.

In terms of weights:

I presume checkFours returns the number of 4-in-a-row's on the board. This should be given a way higher weight, since as soon as there exists one such value, it will mean the end of the game. Thus this is the position the agent should strive to above all else (unless the opponent already won).

A bit of a guess, but my intuition says 3-in-a-row's need to be given a somewhat higher weight in relation to 2-in-a-row's.

Other than that:

Two unblocked 3-in-a-row's that don't require the same 4th cell cannot be countered, you will win next turn (unless your opponent wins first). This should also be incorporated into your heuristic, but may already largely be taken care of (except for a different 4th cell requirement) by simply counting the number of 3-in-a-row's (subject to the below). In general, 2/3-in-a-row's requiring the same cells to get to 4 as another 2/3-in-a-row isn't all that helpful.

You also need to count disjoint sets, e.g.:
xx x can be thought of as a 3-in-a-row.
x x can be thought of as a 2-in-a-row.

You also need to exclude 2/3-in-a-row's that can't get to 4, e.g. oxxxo contains a 3-in-a-row, but it's surrounded by opponent-occupied cells, thus you shouldn't count it.

You also shouldn't count a 3-in-a-row as a 3-in-a-row and 2 2-in-a-row's. Since you didn't give your functions, I can't tell if you're doing this.

$\endgroup$
  • $\begingroup$ This is extremely helpful, thank you. I did not consider disjoint sets at all, and I believe that will help a TON. I'm also going to make my 4-in-a-row much higher. I will report back with the results. $\endgroup$ – Chad Jul 26 '13 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.