Блог

Я пытаюсь создать искусственный интеллект в крестики-нолики, используя алгоритм минимакса, но, похоже, не могу понять, как это сделать. Мой алгоритм минимакса, кажется, просто идет по порядку от наименьшего к наибольшему, и я не знаю почему.

Я действительно теряюсь в догадках, где моя программа могла пойти не так, я часами перепроверял каждую часть своего алгоритма. Может ли кто-нибудь, пожалуйста, указать мне правильное направление для части минимаксного ии? Спасибо.

 #include lt;stdlib.hgt;  int BS = 3; //map numbers to X or O char map(int marker); void print_board(int board[]); int winner(int board[]); void move(int board[]); int terminal(int board[]); int minimax(int board[], int player, int depth); int ai(int board[]);   int main(void)  {  // Init board  int board[BS*BS];  for(int i = 0; i lt; BS*BS; i  )  {  board[i] = 0;  }  for(int i = 0; i lt; BS*BS amp;amp; winner(board) == 0; i  )  {  print_board(board);  if(i % 2 == 0)  {  move(board);  }  else  {  board[ai(board)] = 1;   }  }  print_board(board);  printf("w:%i", winner(board)); }  char map(int marker) {  switch(marker)  {  case -1:  return 'X';  case 0:  return '?';  case 1:  return 'O';  }  return ' '; }  void print_board(int board[]) {    system("clear");  // Print row of letters / columns  for(int i = 0; i lt; BS; i  )  {    for(int j = BS * i; j lt; i * BS   BS; j  )  {  if( j lt; BS * i   BS - 1)  {  printf("%c|", map(board[j]));  }  else   {  printf("%cn", map(board[j]));  }  }   // Print horizontal dividers  if(i lt; BS - 1)  {  for(int k = 0; k lt; BS   BS - 1; k  )  {  printf("-");  }  printf("n");  }   } }  // Check winner int winner(int board[]) {  // Init columns array  int columns[BS];  for(int i = 0; i lt; BS; i  )  {  columns[i] = 0;  }   // Loop through entire board through steps of the row size  for(int i = 0; i lt; BS*BS; i = BS)  {  int row = 0;  //int count = 0;   // Check if the row is full of the same markers, as well as adding column values to an array  for(int j = i; j lt; BS   i; j  )  {  row  = board[j];  columns[j - i]  = board[j];  }   // Row win for O  if(row == BS)  {  return 1;  }   // Row win for X  if(row == BS * (-1))  {  return -1;  }  }  // Check for column wins  for(int i = 0; i lt; BS; i  )  {  if(columns[i] == BS)  {  return 1;  }  if(columns[i] == BS * (-1))  {  return -1;  }  }   // Check diagonal  int prev = board[0];  int diag = 1;  for(int i = 0; i lt; BS*BS; i = BS   1)  {  if(board[i] != prev)  {  diag = 0;  }  }   if(diag != 0)  {  return board[0];  }   int adiag = 1;  // Check anti-diagonal  prev = board[BS - 1];  for(int i = BS - 1; i lt;= BS*BS - BS; i = BS - 1)  {  if(board[i] != prev)  {  adiag = 0;  }  }   if(adiag != 0)  {  return board[BS - 1];  }   // Otherwise, no winner  return 0; }  // Take player input void move(int board[]) {  int move = 0;  while(1)  {  printf("Input a single number from 1 - total number of cells on the board to put down a marker:n");  scanf("%d", amp;move);  printf("n");  if(board[move - 1] == 0 amp;amp; 0 lt;= move lt; BS * BS)  {  break;  }  }   board[move - 1] = -1;  }  // Check whether game has ended int terminal(int board[]) {  for(int i = 0; i lt; BS * BS; i  )  {  if(board[i] == 0)  {  return 0;  }  }  return 1; }  int minimax(int board[], int player, int depth) {  // Return terminal state  if(terminal(board) == 1)  {  return winner(board);  }    if(player == 1)  {  int max_value = -10000000;  for(int i = 0; i lt; BS * BS; i  )  {  if(board[i] == 0)  {  board[i] = 1;  int value = minimax(board, -1, depth   1) - depth;  board[i] = 0;  if(value gt; max_value)  {  max_value = value;  }  }    }  return max_value;  }    else  {  int min_value = 10000000;  for(int i = 0; i lt; BS * BS; i  )  {  if(board[i] == 0)  {  board[i] = -1;  int value = minimax(board, 1, depth   1)   depth;  board[i] = 0;  if(value lt; min_value)  {  min_value = value;  }  }  }  return min_value;  } } int ai(int board[]) {  int most_value = -10000;  int next_move;  for(int i = 0; i lt; BS * BS; i  )  {  if(board[i] == 0)  {  board[i] = 1;  int value = minimax(board, 1, 0);  board[i] = 0;  if(value gt; most_value)  {  most_value = value;  next_move = i;  }    }  }  return next_move; }