连接 4 的 Minimax 代码以做出最佳移动

Question

我最近尝试为 connect 4 实现 minimax 算法，但我无法让它工作。这是我的 heuristic、AI 和 minimax 代码。完整代码为here。不知道是哪里出了问题，不能走对。

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;
}

Answer 1

查看 Dropbox 上的代码：

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;
        }
    }
}

循环中没有中断，因此每次反转移动时，您都会删除该列中的每个棋子。

另外我认为僵持代码中的坐标是错误的：

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

我认为应该是：

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

残局检测代码看起来也很奇怪：

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

这是将未初始化的变量 player 传递给 endgame 函数，这似乎不太正确。

连接 4 的 Minimax 代码以做出最佳移动

Minimax code of connect 4 to make best move

c

algorithm

artificial-intelligence

minimax