TicTacToe的Minimax算法不能正常工作

Question

我已经在这个论坛发布了一个类似的问题，但是由于旧帖子有点长，我重写了我的算法，我开始了这个新帖子。 旧的帖子可以找到here。

---

所以我只是想实现一个极大极小算法我井字游戏，但它被证明是相当困难，甚至试图发现其中的错误天后，我找不到它。你可以在下面找到我的代码。首先，我有几个定义，typedef和声明：

typedef signed char s8; 
typedef unsigned char u8; 
typedef s8 score; 

#define STATE_00 getBoardState(0, 0) 
#define STATE_01 getBoardState(0, 1) 
#define STATE_02 getBoardState(0, 2) 
#define STATE_10 getBoardState(1, 0) 
#define STATE_11 getBoardState(1, 1) 
#define STATE_12 getBoardState(1, 2) 
#define STATE_20 getBoardState(2, 0) 
#define STATE_21 getBoardState(2, 1) 
#define STATE_22 getBoardState(2, 2) 

typedef enum { 
    EPlayerX = 1, 
    EPlayerO 
} EPlayer; 

typedef enum { 
    EMinimizing = 0, 
    EMaximizing 
} EMinMax; 

static u8 g_boardState[3][3] = { 
    {0, 0, 0,}, 
    {0, 0, 0,}, 
    {0, 0, 0,}, 
}; 

这些都是其次的一些功能：

u8 getBoardState(u8 row, u8 column); 

EPlayer isWon(void) 
{ 
    EPlayer winningBoards[8][3] = { 
     {STATE_00, STATE_01, STATE_02}, 
     {STATE_10, STATE_11, STATE_12}, 
     {STATE_20, STATE_21, STATE_22}, 
     {STATE_00, STATE_10, STATE_20}, 
     {STATE_01, STATE_11, STATE_21}, 
     {STATE_02, STATE_12, STATE_22}, 
     {STATE_00, STATE_11, STATE_22}, 
     {STATE_20, STATE_11, STATE_02}, 
    }; 
    u8 i; 
    for(i=0; i<8; i++){ 
     if((winningBoards[i][0] != 0) && 
      (winningBoards[i][0] == winningBoards[i][1]) && 
      (winningBoards[i][0] == winningBoards[i][2])){ 
       return winningBoards[i][0]; 
     } 
    } 
    return 0; 
} 

u8 getBoardState(u8 row, u8 column) 
{ 
    return g_boardState[row][column]; 
} 

void setBoardState(u8 row, u8 column, u8 state) 
{ 
    g_boardState[row][column] = state; 
} 

u8 isDraw(void) 
{ 
    u8 i, j; 
    for(i=0; i<3; i++){ 
     for(j=0; j<3; j++){ 
      if(getBoardState(i, j) == 0){ 
       return 0; 
      } 
     } 
    } 
    return 1; 
} 

void dumpTable(score table[3][3]) 
{ 
    int i, j; 
    for(i=0; i<3; i++) { 
     printf("\n"); 
     for(j=0; j<3; j++){ 
      printf("%6i ", table[i][j]); 
     } 
    } 
    printf("\n"); 
} 

EPlayer playerSwitch(EPlayer player) 
{ 
    if(player == EPlayerO) return EPlayerX; 
    if(player == EPlayerX) return EPlayerO; 
    return 0; 
} 

EMinMax modeSwitch(EMinMax mode) 
{ 
    if(mode == EMaximizing) return EMinimizing; 
    if(mode == EMinimizing) return EMaximizing; 
    return 0; 
} 

再有就是这里所说的scoring实际极小算法：

score scoring(EMinMax mode, EPlayer player, u8 depth) 
{ 
    score thisScore, tempScore; 
    if(mode == EMaximizing){ 
     thisScore = -20; 
     if(isWon()) return 15-depth; 
    } 
    if(mode == EMinimizing){ 
     thisScore = 20; 
     if(isWon()) return depth-15; 
    } 
    if(isDraw()){ 
     return 0; 
    } 

    u8 i, j; 
    for(i=0; i<3; i++){ 
     for(j=0; j<3; j++){ 
      if(getBoardState(i, j) == 0){ 
       setBoardState(i, j, player); 
       tempScore = scoring(modeSwitch(mode), playerSwitch(player), depth+1); 
       if((mode == EMaximizing) && (tempScore > thisScore)){ 
        thisScore = tempScore; 
       } 
       if((mode == EMinimizing) && (tempScore < thisScore)){ 
        thisScore = tempScore; 
       } 
       setBoardState(i, j, 0); 
      } 
     } 
    } 

    return thisScore; 
} 

最后一个函数打印在表格中的分数以及main：

void printSocredBoards(EPlayer player) 
{ 
    score thisScore[3][3] = { 
     {STATE_00, STATE_01, STATE_02}, 
     {STATE_10, STATE_11, STATE_12}, 
     {STATE_20, STATE_21, STATE_22}, 
    }; 
    int i, j; 
    if((isWon() == 0) && (isDraw() == 0)){ 
     for(i=0; i<3; i++){ 
      for(j=0; j<3; j++){ 
       if(getBoardState(i, j) == 0){ 
        setBoardState(i, j, player); 
        thisScore[i][j] = scoring(EMaximizing, playerSwitch(player), 0); 
        setBoardState(i, j, 0); 
       } 
      } 
     } 
    } 
    dumpTable(thisScore); 
} 

int main(int argc, char **argv) 
{ 

    printSocredBoards(EPlayerO); 

    return 0; 
} 

据我所知，这个算法应该工作正常，但是它给了我一个荒谬的输出：

7  7  7 
7  0  7 
7  7  7 

我缺少什么？ 在此先感谢您的帮助。

Answer 1

我认为，问题在于从进球这个块的代码在您的情况下，从正确的返回值翻转：

if(mode == EMaximizing){ 
    thisScore = -20; 
    if(isWon()) return 15-depth; 
} 
if(mode == EMinimizing){ 
    thisScore = 20; 
    if(isWon()) return depth-15; 
} 

直观地说，问题是，当scoring代码达到这一点，对isWon的电话正在评估之前的零件放置的结果，该零件放置是由mode的另一选择制成的。

例如，当用EMaximizing调用得分并且棋盘状态已经胜出时，那意味着EMinimizing赢得这种状态并且返回的得分应该反映这个（即它应该是负的）。由于深度达到最大值8时，您的回报值为mode == EMaximizing总是正数，这不是您想要的。

当案例逆转时，你的程序输出全零，这看起来更为合理，因为完美的玩家总是应该画出。我还测试了下面的行的代码添加到顶部的printScoredBoards硬编码所述第一发挥左上角：

setBoardState(0, 0, playerSwitch(player)); 

这产生以下：

0  10  10 
10  0  10 
10  10  10 

正确识别无论是第二位选手都不能选择左上角，并且如果他们在中路之外进行其他任何比赛，他们将会输掉。