title: Implementing minimax algorithm for tic-tac-toe
body: <p>I am trying to implement the minimax algorithm for a tic-tac-toe game where both the players are human and each time computer suggests an optimal move using the minimax algorithm. But it is not giving the right suggestion every time. For example: it does not gives the right suggestion for the following scenario:
  player X : 1
  player O : 2
  player X : 5.
   Here is my code: </p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;algorithm&gt;  
  #include &lt;string&gt;
  using namespace std;
  
  #define inf 1&lt;&lt;20
  int posmax, posmin;
  char board[15];
  
  void print_board()
  {
      int i;
      for (i = 1; i &lt;= 9; i++)
      {   
          printf("%c ",board[i]);
          if (i % 3 == 0)
              printf("\n");
      }
      printf("\n");
  }
  
  int check_win(char board[])
  {
      if ((board[1] == 'X' &amp;&amp; board[2] == 'X' &amp;&amp; board[3] == 'X') ||
          (board[4] == 'X' &amp;&amp; board[5] == 'X' &amp;&amp; board[6] == 'X') ||
          (board[7] == 'X' &amp;&amp; board[8] == 'X' &amp;&amp; board[9] == 'X') ||
          (board[1] == 'X' &amp;&amp; board[4] == 'X' &amp;&amp; board[7] == 'X') ||
          (board[2] == 'X' &amp;&amp; board[5] == 'X' &amp;&amp; board[8] == 'X') ||
          (board[3] == 'X' &amp;&amp; board[6] == 'X' &amp;&amp; board[9] == 'X') ||
          (board[1] == 'X' &amp;&amp; board[5] == 'X' &amp;&amp; board[9] == 'X') ||
          (board[3] == 'X' &amp;&amp; board[5] == 'X' &amp;&amp; board[7] == 'X'))
      {
          return 1;
      }
      else if((board[1] == 'O' &amp;&amp; board[2] == 'O' &amp;&amp; board[3] == 'O') ||
              (board[4] == 'O' &amp;&amp; board[5] == 'O' &amp;&amp; board[6] == 'O') ||
              (board[7] == 'O' &amp;&amp; board[8] == 'O' &amp;&amp; board[9] == 'O') ||
              (board[1] == 'O' &amp;&amp; board[4] == 'O' &amp;&amp; board[7] == 'O') ||
              (board[2] == 'O' &amp;&amp; board[5] == 'O' &amp;&amp; board[8] == 'O') ||
              (board[3] == 'O' &amp;&amp; board[6] == 'O' &amp;&amp; board[9] == 'O') ||
              (board[1] == 'O' &amp;&amp; board[5] == 'O' &amp;&amp; board[9] == 'O') ||
              (board[3] == 'O' &amp;&amp; board[5] == 'O' &amp;&amp; board[7] == 'O'))
      {
          return -1;
      }
      else return 0;
  }
  
  int check_draw(char board[])
  {
      if ((check_win(board) == 0) &amp;&amp; (board[1] != '_') &amp;&amp; (board[2] != '_') &amp;&amp;
          (board[3] != '_') &amp;&amp; (board[4] != '_') &amp;&amp; (board[5] != '_') &amp;&amp;
          (board[6] != '_') &amp;&amp; (board[7] != '_') &amp;&amp; (board[8] != '_') &amp;&amp;
          (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 &lt;= 9; i++)
      {
          if(board[i] == '_')
          {
              if(player == 2)  
              {
                  board[i] = 'O';
                  res = minimax(1, board, n + 1);
  
                  board[i] = '_';
                  if(res &lt; 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 &gt; 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 &lt;= 9; i++)
          board[i] = '_';
  
      printf("Board:\n");
      print_board();
  
      for(i = 1; i &lt;= 9; i++)
      {
          if (i % 2 == 0)
              printf("Player O give input:\n");
          else 
              printf("Player X give input:\n");
  
          scanf("%d", &amp;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) &amp;&amp; (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;
  }
  </code></pre>