实现井字游戏的极大极小算法

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;