Minimax for Connect Four (Unity3D and C#): Problems

Question

I'm developing a Connect Four game with AI in Unity3D (C#). I use for this the MiniMax algorithm according to this (German) Pseudocode.

The AI is still playing pretty bad. It tries to get even 4 in a row, although there are only three free fields. The AI always goes through the row and blocks only when it is needed. Unfortunately, it also blocks not always.

Where to hide the problems? What have I forgotten?

How can I integrate random moves of the AI when no one wins or loses at the next move.

Here is my source code:

minimaxDepth = 4

function call: Max (minimaxDepth, fieldCopy);

int Max (int depth, int[,] fieldCopy)
{
    int maxValue = -9999;
    int moveValue;
    bool winAI = false;
    bool winHuman = false;
    bool isStoneBelow = false;

    for (int y = 0; y < 6; y++) {
        for (int x = 0; x < 7; x++) {
            if (y > 0) {
                //is a stone under it?
                if (fieldCopy [x, y - 1] == 1 || fieldCopy [x, y - 1] == 2) {
                    isStoneBelow = true;
                } else {
                    isStoneBelow = false;
                }
            } else {
                isStoneBelow = true;
            }

            // possible move?
            if (fieldCopy [x, y] != 1 && fieldCopy [x, y] != 2 && isStoneBelow == true) {   
                isStoneBelow = false;
                fieldCopy [x, y] = 2; //simulate move
                winAI = false;
                winHuman = false;

                //Is there a winner?
                if (CheckWin (x, y, 2, fieldCopy)) {
                    winAI = true;
                    winHuman = false;
                }

                //No more moves possible?
                if (depth <= 1 || winAI == true) { 
                    moveValue = evaluationFunction (winAI, winHuman);       //evaluate the move
                } else {
                    moveValue = Min (depth - 1, fieldCopy);
                }

                fieldCopy [x, y] = 0; //Reset simulated move

                if (moveValue > maxValue) {
                    maxValue = moveValue;
                    if (depth == minimaxDepth) {
                        aiMoveX = x; // next move
                    }
                }
            }
        }
    }
    return maxValue;
}

int Min (int depth, int[,] fieldCopy)
{
    int minValue = 9999;
    int moveValue;
    bool winAI = false;
    bool winHuman = false;
    bool isStoneBelow = false;
    bool loopBreak = false;

    for (int y = 0; y < 6; y++) {
        for (int x = 0; x < 7; x++) {
            if (y > 0) {
                //is a stone under it?
                if (fieldCopy [x, y - 1] == 1 || fieldCopy [x, y - 1] == 2) {
                    isStoneBelow = true;
                } else {
                    isStoneBelow = false;
                }
            } else {
                isStoneBelow = true;
            }

            // possible move?
            if (fieldCopy [x, y] != 1 && fieldCopy [x, y] != 2 && isStoneBelow == true) {   
                isStoneBelow = false;
                fieldCopy [x, y] = 1; //simulate move
                winHuman = false;
                winAI = false;

                //Is there a winner?    
                if (CheckWin (x, y, 1, fieldCopy)) {
                    winHuman = true;
                    winAI = false;
                }

                //No more moves possible?
                if (depth <= 1 || winHuman == true) {  
                    moveValue = evaluationFunction (winAI, winHuman);       //evaluate the move
                } else {
                    moveValue = Max (depth - 1, fieldCopy);
                }

                fieldCopy [x, y] = 0; //Reset simulated move

                if (moveValue < minValue) {
                    minValue = moveValue;
                }
            }
        }
    }
    return minValue;
}


int evaluationFunction (bool winAI, bool winHuman)
{
    if (winAI) { 
        return 1;
    } else if (winHuman) {
        return -1;
    } else {
        return 0;
    }
}

Thanks for your help!

Answer 1

I believe the problem lies in your evaluation function. Instead of evaluating whether one of the players has won, you should evaluate their state in the game. A possible consideration would be the length of the longest contiguous chain of that players pieces. This accurately shows how far each player is from winning, instead of returning the same value even when a player is about to win, but hasn't yet.

Here's pseudocode for clarity:

int evaluationFunction (int depth)
{
    // max_ai_chain and max_human_chain are global variables that 
    // should be updated at each piece placement

    if (depth % 2 == 0) // assuming AI gets calculated on even depth (you mentioned your depth is 4)
    { 
        return max_ai_chain;
    } else {
        return max_human_chain;
    }
}