tic-tac-toe를위한 minimax 알고리즘 구현하기

Question

나는 minimax 알고리즘을 사용하여 컴퓨터가 최적의 움직임을 제안 할 때마다 플레이어가 모두 인간 인 tic-tac-toe 게임을위한 minimax 알고리즘을 구현하려고합니다. 그러나 매번 올바른 제안을하지는 않습니다. 예를 들어 다음과 같은 시나리오에 적합한 제안을 제공하지 않습니다 플레이어 X : 1 플레이어 O : 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 O is %d\n", posmin);

모든 것을 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 X is %d %d\n", posmax); 교체는 항상 가장 빠른 승리를 인쇄하지 않습니다하지만 승리가 존재하는 경우 (정확한 것 같다).

Answer 4

제 생각에는 프로그램이 잘못된 제안을하지 않습니다. Minimax는 두 선수가 모두 최적으로 뛰고 있다면 이동의 점수를 계산합니다. 귀하의 경우 점수는 +1, -1 및 0 일 수 있습니다. 잃어버린 피할 수없는 것이지, 어느 정도의 깊이를 잃어 버리지는 않는다. 플레이어 O는 자신의 움직임을 만드는 경우 다음 gamestate

X O _ 
X _ _ 
_ _ _ 

및 플레이어 X의 최적의 재생을 감안할 때, 그것은 (그가 어느 경우에 손실) 문제가되지 않는다 : O 7을한다

• 후, X 5를 재생 , O 3를 재생 한 후> X
• 승리 X 7 재생 - -, O는 6 재생, X는 8 재생> 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;