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 

正確識別無論是第二位選手都不能選擇左上角，並且如果他們在中路之外進行其他任何比賽，他們將會輸掉。