title: Tic Tac Toe using Machine Learning with LMS rule
body: <p>I am trying to implement the famous game of <a href="http://en.wikipedia.org/wiki/Tic-tac-toe" rel="nofollow noreferrer">Tic Tac Toe</a> using Machine learning with Least Mean Square (LMS) rule (an exercise proposed in Tom Mitchell's famous book, <a href="https://rads.stackoverflow.com/amzn/click/com/0070428077" rel="nofollow noreferrer" rel="nofollow noreferrer">Machine Learning</a>).</p>
  
  <p>I made the computer learn by playing against an optimal opponent that picks the best moves, and then against a randomized player. Against the optimal opponent, my program won about 90% of the games and tied the rest without ever losing. Against a random opponent, it won about 83% and lost 15% of the games. </p>
  
  <p>However, when I played against the program, I won every time using the same strategy.</p>
  
  <p>Here's how my program works:<br>
   * create learner and player(randomized or optimal)<br>
   * while (game running)<br>
   * generate all possible states for a turn and use the best to make the turn<br>
   * the best turn is saved<br>
   * go through saved boards and calculate value for every feature<br>
   * calculate board score using features and current weights<br>
   * calculate training score:<br>
     * if last board and won: trainings value of last board == 100<br>
     * if last board and lost: trainings value of last board: -100<br>
   * adjust the weights using LMS rule  </p>
  
  <p>I expect this approach to make the computer play perfectly (win most of the time, tie otherwise)? Am I wrong, or is there something wrong with my training method?</p>
  
  <p>Thoughts, ideas, code, suggestions on board features to use on this matter are really appreciated.</p>