實現井字遊戲的極大極小算法

Question

我正在嘗試實現井字遊戲的極小極大算法，其中玩家都是人類，每次計算機都會使用極小極大算法提出最優移動。但它並不是每次都給出正確的建議。例如：它不給出正確的建議用於以下情形： 播放器X：1名 球員○：2 播放器X：5 這裏是我的代碼：

#include <stdio.h> 
#include <algorithm> 
#include <string> 
using namespace std; 

#define inf 1<<20 
int posmax, posmin; 
char board[15]; 

void print_board() 
{ 
    int i; 
    for (i = 1; i <= 9; i++) 
    { 
     printf("%c ",board[i]); 
     if (i % 3 == 0) 
      printf("\n"); 
    } 
    printf("\n"); 
} 

int check_win(char board[]) 
{ 
    if ((board[1] == 'X' && board[2] == 'X' && board[3] == 'X') || 
     (board[4] == 'X' && board[5] == 'X' && board[6] == 'X') || 
     (board[7] == 'X' && board[8] == 'X' && board[9] == 'X') || 
     (board[1] == 'X' && board[4] == 'X' && board[7] == 'X') || 
     (board[2] == 'X' && board[5] == 'X' && board[8] == 'X') || 
     (board[3] == 'X' && board[6] == 'X' && board[9] == 'X') || 
     (board[1] == 'X' && board[5] == 'X' && board[9] == 'X') || 
     (board[3] == 'X' && board[5] == 'X' && board[7] == 'X')) 
    { 
     return 1; 
    } 
    else if((board[1] == 'O' && board[2] == 'O' && board[3] == 'O') || 
      (board[4] == 'O' && board[5] == 'O' && board[6] == 'O') || 
      (board[7] == 'O' && board[8] == 'O' && board[9] == 'O') || 
      (board[1] == 'O' && board[4] == 'O' && board[7] == 'O') || 
      (board[2] == 'O' && board[5] == 'O' && board[8] == 'O') || 
      (board[3] == 'O' && board[6] == 'O' && board[9] == 'O') || 
      (board[1] == 'O' && board[5] == 'O' && board[9] == 'O') || 
      (board[3] == 'O' && board[5] == 'O' && board[7] == 'O')) 
    { 
     return -1; 
    } 
    else return 0; 
} 

int check_draw(char board[]) 
{ 
    if ((check_win(board) == 0) && (board[1] != '_') && (board[2] != '_') && 
     (board[3] != '_') && (board[4] != '_') && (board[5] != '_') && 
     (board[6] != '_') && (board[7] != '_') && (board[8] != '_') && 
     (board[9] != '_')) 
    { 
     return 1; 
    } 
    else return 0; 
} 

int minimax(int player, char board[], int n) 
{ 
    int i, res, j; 

    int max = -inf; 
    int min = inf; 

    int chk = check_win(board); 
    if (chk == 1) 
     return 1; 
    else if (chk == (-1)) 
     return -1; 
    else if (chk = check_draw(board)) 
     return 0; 

    for (i = 1; i <= 9; i++) 
    { 
     if(board[i] == '_') 
     { 
      if(player == 2) 
      { 
       board[i] = 'O'; 
       res = minimax(1, board, n + 1); 

       board[i] = '_'; 
       if(res < min) 
       { 
        min = res; 
        if (n == 0) 
         posmin = i; 
       } 
      } 
      else if (player == 1) 
      { 
       board[i] = 'X'; 
       res = minimax(2, board, n + 1); 
       board[i] = '_'; 
       if (res > max) 
       { 
        max = res; 
        if (n == 0) 
         posmax = i; 
       } 
      } 
     } 
    } 

    if (player == 1) 
     return max; 
    else return min;  
} 


// 1 is X, 2 is O 
int main() 
{ 
    int i, j, input, opt; 

    for(i = 1; i <= 9; i++) 
     board[i] = '_'; 

    printf("Board:\n"); 
    print_board(); 

    for(i = 1; i <= 9; i++) 
    { 
     if (i % 2 == 0) 
      printf("Player O give input:\n"); 
     else 
      printf("Player X give input:\n"); 

     scanf("%d", &input); 
     if (i % 2 != 0) 
      board[input] = 'X'; 
     else 
      board[input] = 'O'; 

     printf("Board:\n"); 
     print_board(); 

     int chk = check_win(board); 
     if (chk == 1) 
     { 
      printf("Player X wins!\n"); 
      break; 
     } 
     else if (chk == -1) 
     { 
      printf("Player O wins!\n"); 
      break; 
     } 
     else if ((chk == 0) && (i != 9)) 
     { 
      posmax = -1; 
      posmin = -1; 
      if(i % 2 == 0) 
      { 
       opt = minimax(1, board, 0); 
       printf("Optimal move for player X is %d\n", posmax); 
      } 
      else 
      { 
      opt = minimax(2, board, 0); 
      printf("Optimal move for player O is %d\n", posmin); 
      } 
     } 
     else 
      printf("The game is tied!\n"); 
    } 
    return 0; 
} 

Answer 1

除非我讀主（）錯誤，在聲明它爲平局之前，只允許填充8個方格。這可能不是你正在尋找的錯誤，但它是一個開始。

Answer 2

我認爲這是正確的（儘管效率低下）。如果沒有，請給出一個你認爲程序錯誤的移動序列。

它沒有給出最短的移動順序，這可能是你在做什麼。那麼，你應該重構它，以返回移動的最短移動順序（如果獲勝）或最長的移動順序（失敗時）。

Answer 3

更換 printf("Optimal move for player X is %d %d\n", posmax); 與 printf("Optimal move for player X is %d\n", posmax);

和

printf("Optimal move for player O is %d %d\n", posmin); 與其他 printf("Optimal move for player O is %d\n", posmin);

一切似乎是正確的，但它並不總是打印速度最快的勝利（如果存在的勝利）。

Answer 4

在我看來你的程序不會給出錯誤的建議。 Minimax計算一個動作的得分，如果兩個玩家都玩最佳。您的情況中的分數可以是+1，-1和0，因此，如果遊戲例如不可避免地會丟失，它在失去的深度上並沒有什麼不同。考慮下面的遊戲狀態

X O _ 
X _ _ 
_ _ _ 

和球員X的最佳發揮，這不要緊，球員Ø他的行動（他在這兩種情況下失去）：O則7

• 後，X扮演5 ，O-起着6，X 8起着 - > X勝
• ö起着3之後，X起着7 - > X勝

玩家X獲勝。移動7給出與移動3和所有其他可玩移動相同的得分。如果您想讓算法在本例中給出移動建議7，則必須將遊戲深度包含在評估函數中。您可以通過將函數的返回值更改爲以下內容來執行此操作：

int chk = check_win(board); 
if (chk == 1) 
    return (10 - n); 
else if (chk == (-1)) 
    return -(10 - n); 
else if (chk = check_draw(board)) 
    return 0;