How this evaluation function work in a Connect 4 game? (Java)

Question

I am exploring how a Minimax algorithm can be used in a connect four game with alpha-beta pruning.

So I was looking through a source code about a Connect4 player strategy and found this evaluation function:

/**
* Get the score of a board
*/
public int score(){
    int score = 0;
    for (int r= 0; r < ROWS; r++) {
        if (r <= ROWS-4) {
            for (int c = 0; c < COLS; c++) {
                score += score(r, c);
            }
        } else {
            for (int c = 0; c <= COLS-4; c++) {
                score += score(r, c);
            }
        }
    }
    return score;
}


/**
* Helper method to get the score of a board
*/
public int score(int row, int col){
    int score = 0;
    boolean unblocked = true;
    int tally = 0;
    //int r, c;
    if (row < ROWS-3) {
        //check up
        unblocked = true;
        tally = 0;

        for (int r=row; r<row+4; r++) {
            if (board[r][col] == CHECKERS[1-playerToMoveNum]) {
                unblocked = false;
            }
            if (board[r][col] == CHECKERS[playerToMoveNum]) {
                tally ++;
            }
        }
        if (unblocked == true) {
            score = score + (tally*tally*tally*tally);
        }
        if (col < COLS-3) {
            //check up and to the right
            unblocked = true;
            tally = 0;
            for (int r=row, c=col; r<row+4; r++, c++) {
                if (board[r][c] == CHECKERS[1-playerToMoveNum]) {
                    unblocked = false;
                }
                if (board[r][c] == CHECKERS[playerToMoveNum]) {
                    tally ++;
                }
            }
            if (unblocked == true) {
                score = score + (tally*tally*tally*tally);
            }
        }
    }
    if (col < COLS-3) {
        //check right
        unblocked = true;
        tally = 0;
        for (int c=col; c<col+4; c++) {
            if (board[row][c] == CHECKERS[1-playerToMoveNum]) {
                unblocked = false;
            }
            if (board[row][c] == CHECKERS[playerToMoveNum]) {
                tally ++;
            }
        }
        if (unblocked == true) {
            score = score + (tally*tally*tally*tally);
        }
        if (row > 2) {
            //check down and to the right
            unblocked = true;
            tally = 0;
            for (int r=row, c=col; c<col+4; r--, c++) {
                if (board[r][c] == CHECKERS[1-playerToMoveNum]) {
                    unblocked = false;
                }
                if (board[r][c] == CHECKERS[playerToMoveNum]) {
                    tally ++;
                }
            }
            if (unblocked == true) {
                score = score + (tally*tally*tally*tally);
            }
        }
    }
    return score;
}

I found all this code in this PDF: http://ryanmaguiremusic.com/media_files/pdf/ConnectFourSource.pdf

I just want to understand how this evaluation function works and decides the best move to be made... Could anyone give me some help? It would be greatly appreciated.

Answer 1

Here is a general answer:

The evaluation should give better values for better positions. In games a position is often evaluated by calculating a score the following way: increase the score for desirable configurations/events and decrease it for undesirable ones. Deciding how much an evaluated feature should change the value (= balancing the weights) can be very difficult.

If we apply this to connect four then one feature could be the number of threats alive. But for a really good algorithm (which solves 7x6) you have to look if the winning move is on an odd or even line. And then there are some rules like "if the 2nd player has 2 even threats he has won the game" (it all comes down to when filling up the board and moves are forced, the rule given is a little simplified: the 2nd player will have to kill an even threat if he can't fill up the other columns if the 1st player has an odd threat there).

Simple example for the rule given (O = first player, X = 2nd player), X wins:

  * X X X *
O   O X O   O
1 2 3 4 5 6 7

There was once a very detailed scientific paper about it. The closest I could find at the moment: http://web.mit.edu/sp.268/www/2010/connectFourSlides.pdf Should give you some ideas.

Btw. Opening books (generally predefined wisdom in any form e.g. joseki, fuseki) and special end game evaluators can greatly improve the performance of minimax.