title: C++ MiniMax Algorithm getting stuck in an infinite loop for Tic Tac Toe Board
body: <p>I'm currently implementing a <a href="http://en.wikipedia.org/wiki/Minimax" rel="nofollow">MiniMax Algorithm</a> with <a href="http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="nofollow">Alpha Beta Pruning</a> for a Tic Tac Toe game.</p>
  
  <p>My algorithm takes in an empty board and, at the end has that board contain the same state as the current board, along with the next move made. Then, I simply make <code>*this</code> (the current board) equal to the returned board.</p>
  
  <p>However, for some reason, my algorithm is getting stuck in an infinite loop.  Here's my miniMax function:</p>
  
  <pre><code>int board::miniMax(int alpha, int beta, board &amp; childWithMaximum)
  {   
      if (checkDone())
          return boardScore();
  
      vector&lt;board&gt; children = getChildren();
      while (!children.empty())
      {
          board curr = children.back();
  
          board dummyBoard;
          int score = curr.miniMax(alpha, beta, dummyBoard);
  
          if (computerTurn &amp;&amp; (beta &gt; score)) {
  
              beta = score;
              childWithMaximum = *this;   
              if (alpha &gt;= beta)
                  break;
  
          } else if (alpha &lt; score) {
  
              alpha = score;
              childWithMaximum = *this;
              if (alpha &gt;= beta)
                  break;
          }
      }
      return computerTurn ? alpha : beta;
  }
  </code></pre>
  
  <p>I've done some print-statement debugging, and it appears that this <code>getChildren()</code> helper function is working.  I had it print out a couple of children and there were other board states in the tree:</p>
  
  <pre><code>vector&lt;board&gt; board::getChildren()
  {
      vector&lt;board&gt; children;
  
      for (int i = 0; i &lt; 3; ++i) {
          for (int j = 0; j &lt; 3; ++j) {
              if (getPosition(i, j) == '*') {
                  //move not made here
  
                  board moveMade(*this);
                  moveMade.setPosition(i, j);             
                  children.push_back(moveMade);
              }
          }
      }
  
      return children;
  }
  </code></pre>
  
  <p>However, my <code>miniMax()</code> function is not making the return board equal to the next move.</p>