title: C++ Minmax Failing
body: <p>I've been working on this for such a long time that it isn't funny anymore. I'm trying to implement Minmax on Tic Tac Toe and while I have gotten several versions of AI that make reasonable initial moves, I can never make one that never loses.</p>
  
  <p>One of the issues which I cannot sort out is the heuristic value. It is currently returning as -10 on the first Minmax call, whereas it should be returning 0 (It should be able to draw no matter what happens).</p>
  
  <p>Another issue is that it runs through 400,000 iterations, whereas 322,000 is the max and given early win situations, should even stop around 250,000.</p>
  
  <p>Any help would be infinitely appreciated.</p>
  
  <pre><code>int MiniMax(TGameBoard _GameBoard)
  {
      //Always goes for max of course, just expanded in case you wanted two AIs
  
      int iBestMove;      
      int iHeuristicReturned = 0;
  
      if (_GameBoard.ePlayer == COMPUTER)
      {
          iHeuristicReturned = MaxMove(_GameBoard, iBestMove);
      }
      else
      {
          iHeuristicReturned = MinMove(_GameBoard, iBestMove);
      }
      //cout&lt;&lt;"\nHeuristic is "&lt;&lt;iHeuristicReturned&lt;&lt;endl;
  
      g_iHeuristic = iHeuristicReturned;
      return iBestMove;
  }
  
  int MaxMove(TGameBoard _GameBoard, int&amp; _iMove)
  {
      //Logic
      //If its an end node, calculate the score
      //Otherwise, do minmax until the end node, and pass back the value
      //If returned value is greater than v, then pass the move back upwards
      ++g_iIterations;
      if(_GameBoard.CheckWinner(_GameBoard) || _GameBoard.IsFull())
      {
          int x;
          x = EvaluateStaticPosition(_GameBoard, MAX);
          return EvaluateStaticPosition(_GameBoard, MAX);
      }
      vector&lt;int&gt; moveList;
      GenerateMoveList(_GameBoard, moveList);
      int iNumMoves = moveList.size();
      int v = -10000;
  
      for(int i = 0; i &lt; iNumMoves; ++i)
      {
          int iMove = moveList[i];
  
          _GameBoard.Set(iMove, CROSS);
          int opponentsBestMove;
          ++g_iDepth;
          int curRating = MinMove(_GameBoard, opponentsBestMove);
          --g_iDepth;
          if (curRating &gt; v)
          {
              v = curRating;
              _iMove = iMove;
          }
          RetractMove(&amp;_GameBoard, iMove);
      }
      return v;
  }
  
  int MinMove(TGameBoard _GameBoard, int&amp; _iMove)
  {
      ++g_iIterations;
      if (g_iIterations &gt; 320000)
      {
          int x = 0;
      }
  
      if(_GameBoard.CheckWinner(_GameBoard) || _GameBoard.IsFull())
      {
          return EvaluateStaticPosition(_GameBoard, MIN);
      }
  
      vector&lt;int&gt; moveList;
      GenerateMoveList(_GameBoard, moveList);
      int iNumMoves = moveList.size();
      int v = 10000;
  
      for(int i = 0; i &lt; iNumMoves; ++i)
      {
          int iMove = moveList[i];
          _GameBoard.Set(iMove, NAUGHT);
          int opponentsBestMove;
          ++g_iDepth;
          int curRating = MaxMove(_GameBoard, opponentsBestMove);
          --g_iDepth;
          if (curRating &lt; v)
          {
              v = curRating;
              _iMove = iMove;
          }
          RetractMove(&amp;_GameBoard, iMove);
      }
      return v;
  }
  
  int EvaluateStaticPosition(TGameBoard _GameBoard, EGoal _eGoal)
  {
      if(_GameBoard.CheckWinner(_GameBoard, COMPUTER))
      {
          return 10;
      } 
      if(_GameBoard.CheckWinner(_GameBoard, PLAYER))
      {
          return -10;
      } 
      return 0;
  }
  </code></pre>
  
  <p>The other related functions can be checked here, but I'm pretty sure they're okay.
  <a href="http://pastebin.com/eyaNfBsq" rel="nofollow">http://pastebin.com/eyaNfBsq</a></p>
  
  <p>Yes I'm aware there's a few unnecessary parameters - After failing my own version I tried follow a tutorial off the internet. Unfortunately they're giving the same results.</p>
  
  <p>I've been on this for 12 hours and it seems such a simple task, can't find out what's wrong</p>