title: Tic Tac Toe C++ algorithm debugging help
body: <p>Please help me understand why this isn't working.  I don't know if there is a bug in my code, or whether my algorithm is fundamentally logically flawed. </p>
  
  <p>My algorithm is based on minimax, but I've forgone a heuristic evaluation function for a more simple technique.  Because of the simplicity of plain 3x3 tic tac toe, I just want to calculate all possible game outcomes for each potential move, and select the one with the highest 'score'.  I create a 'top level' vector of valid moves as well as a matching sized vector for their corresponding 'scores' -i.e. for every possible outcome subsequent to that move: ++ for a win and -- for a loss.</p>
  
  <p>However my vector of move scores is getting strange non-symmetrical values. Although even if the code worked, logically is it possible that a move which is calculated to lead to the most wins and least losses, would be blind to a simple tactic such as a fork?  My instincts say yes, but I haven't worked out the math in detail.  </p>
  
  <pre><code>char board [9] = { '.','.','.','.','.','.','.','.','.' };
  
  int com_turn(int turn) 
      {
      char player=COM; // keeps track of current player  
  
      cout&lt;&lt;"Computer turn. \n";  
  
      vector&lt;int&gt; moves = get_valid_moves(board); // top level move list
      vector&lt;int&gt; m_scores (moves.size(), 0);  // top level move scores
  
      for (int m=0; m &lt; moves.size(); m++) // eval each top level move
      {
          board[moves[m]] = player; // do move
  
          evaluate(board, turn, &amp;m_scores[m], player); 
          cout&lt;&lt; m_scores[m] &lt;&lt;' '; // for debugging
  
          board[moves[m]]='.'; // undo move
      }
  
      int bestmove;
      for (int i=0; i &lt; moves.size(); i++) // find best score
      {
          bestmove = max(bestmove, m_scores[i]);
      }
      for (int i=0; i &lt; moves.size(); i++) // match to best move
      {
          if (bestmove == m_scores[i])
          {
              bestmove = moves[i];
              break;
          }
      }
  
      board[bestmove]=COM; // finally make com move
      print_board();
  }
  
  vector&lt;int&gt; get_valid_moves(char *board) 
  {
      vector&lt;int&gt; vmoves;
      for (int i=0; i &lt; 9; i++)
      {
          if (board[i]=='.') vmoves.push_back(i);
      }
      return vmoves;
  }
  
  
  void evaluate(char *board, int turn, int *mscore, char player) 
  {
      if (check_win(board)) 
      {
          (player==HUMAN)? *mscore -= 1: *mscore += 1;  
          return;  
      }
      if (turn &gt; 9) return;
  
      vector&lt;int&gt; child_moves = get_valid_moves(board);
      if (child_moves.size() &lt; 1) return;
  
      (player==COM)? player=HUMAN: player=COM; // switch player
  
      for (int m=0; m &lt; child_moves.size(); m++) 
      {
          board[child_moves[m]] = player; // do move
  
          evaluate(board, ++turn, mscore, player);
  
          board[child_moves[m]]='.'; // undo move
      }
  }
  </code></pre>