title: Tic Tac Toe Random AI
body: <p>I am working on building a Tic Tac Toe game with varying AI implementations for a computer opponent for the sake of learning different algorithms and how to implement them. The first I am trying which should be the easiest is just having the computer choose a random space each time.</p>
  
  <p>This is working for me to a certain extent, the issue becomes run time. Every time the <code>aiRandMove()</code> method is called, it takes longer and longer to pick a move to the point where after 5 moves have been made on board (cpu + user combined) the program appears to hang (although this isn't technically the case). </p>
  
  <p>Upon further debugging on my part I realize that this should be expected as the <code>aiRandMove()</code> method is randomly choosing an X and Y coordinate and then the move is tested to see if it is legal. As less and less spaces are open, there are fewer and fewer legal moves, thus many more failed attempts by the randomizer to generate a legal move.</p>
  
  <p>My questions is, Is there any way I can modify this that would at least reduce the time taken by the function? As far as I can tell from googling and just running through the problem myself, I cannot think of a way to optimize this without compromising the "randomness" of the function. I thought about keeping an array of moves the computer attempted but that would not resolve the problem because that would not affect the amount of times <code>rand()</code> generated duplicate numbers. Here is the code for this function which is all that is really relevant to this issue:</p>
  
  <pre><code>//Function which handles the AI making a random move requires a board
  //object to test moves legality and player object to make a move with
  //both are passed by reference because changes to board state and the player's
  //evaluation arrays must be saved
  char aiRandMove(Player &amp;ai, Board &amp;game){
     int tryX;
     int tryY; //Variables to store computer's attempted moves
     bool moveMade = false;
     char winner;
     while(!moveMade){
        srand(time(NULL));//Randomizes the seed for rand()
        tryX = rand() % 3;
        tryY = rand() % 3; //coordinates are random numbers between X and Y
        cout &lt;&lt; "Trying move " &lt;&lt; tryX &lt;&lt; ", " &lt;&lt; tryY &lt;&lt; endl;
        if(game.isLegalMove(tryX, tryY)){
           winner = game.makeMove(tryX, tryY, ai);
           moveMade = true;
        }
     }
     return winner;
  }
  </code></pre>
  
  <p>I have also tried moving the seed function out of the while loop (this was put inside the while to "increase randomness" even though that is something of a logical folly and this has also not improved results.</p>
  
  <p>If all else fails I may just label this method "Easy" and only have random moves until I can tell if I need to block or make the winning move. But perhaps there are other random functions which may assist in this endeavor. Any and all thoughts and comments are more than appreciated!</p>