CODEWITHSUNDEEP
calgorithmartificial-intelligenceminimax
Abolfazl
Abolfazl

Reputation: 453

Minimax code of connect 4 to make best move

I have recently tried to implement the minimax algorithm for connect 4, but I'm having trouble getting it to work. here is my heuristic, AI and minimax code. Complete code is here. I don't know where is the problem that it can't make correct moves.

int heuristic(int s[6][7]) {
    int result = 0;
    int i, j;

    //check horizontals
    for(i=0; i<6; i++)
        for(j=0; j<=7-4; j++){
            if(s[i][j]!= 2 && s[i][j+1]!= 2 && s[i][j+2]!= 2 && s[i][j+3]!= 2)
                result++;
            if(s[i][j]!= 1 && s[i][j+1]!= 1 && s[i][j+2]!= 1 && s[i][j+3]!= 1)
                result--;
        }

    //check verticals
    for(i=0; i<=6-4; i++)
        for(j=0; j<7; j++){
            if(s[i][j]!= 2 && s[i+1][j]!= 2 && s[i+2][j]!= 2 && s[i+3][j]!= 2 )
                result++;
            if(s[i][j]!= 1 && s[i+1][j]!= 1 && s[i+2][j]!= 1 && s[i+3][j]!= 1 )
                result--;
        }

    return result;
}

int minimax(int board[R][C], int depth, int turn /*1 or 2*/) {
    int e;
    int col, best;
    int n;
    int player;
    if((e=endgame(board, player))) {
        if(e==3)
            return 0;
        if(e==turn)
            return 10000;
        else
            return -10000;
    }

    if(depth==0)
        return ((turn==1) ? heuristic(board) : -heuristic(board));

    best = -10000;

    for(col=0; col < 7; col++)     //check every move
        if(board[6-1][col]==0) {   //make sure column isn't empty
            put(board, col, turn);
            n = minimax(board, depth-1, 3-turn);
            if(turn==1) {
                if ( -n > best ) best = -n;
            } else { //turn==2
                if ( -n > best ) best = -n;
            }
            rmv(board, col);
        }

    return best;
}

int ai(int board[R][C], int depth) {
    int col, move;
    int n, val = -10000-1;

    for(col=0; col < 7; col++)
        if(board[6-1][col]==0) {
            put(board, col, 2);
            n = minimax(board, depth, 1);
            if ( -n > val ) {
                val = -n;
                move = col;
            }
            rmv(board, col);
        }

    return move;
}

Upvotes: 0

Views: 8076

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Looking at the code on dropbox you have:

void rmv(int board[6][7], int column) { 
    int i;
    for (i=R-1; i>=0; i--){
        if (board[i][column] != 0) {
            board[i][column] = 0;
        }
    }
}

There is no break in the loop, so every time you reverse a move you will delete every piece in that column.

In addition I think the coordinates are the wrong way round in the stalemate code:

for(i=0; i<7; i++)
    if(s[i][6-1]==0)
        return 0;

I think this should be:

for(i=0; i<7; i++)
    if(s[6-1][i]==0)
        return 0;

The endgame detection code also looks odd:

int player;
if((e=endgame(board, player)))

This is passing an uninitialized variable player into the endgame function which seems unlikely to be correct.

Upvotes: 2

Related Questions