title: Is it feasible to solve Dots and Boxes game?
body: <p>The game that I am trying to prove computability for is <a href="http://en.wikipedia.org/wiki/Dots_and_Boxes" rel="nofollow">Dots and Boxes</a>.</p>
  
  <p>However, instead of using theorems I am trying to do so by creating an AI that is supposed to have 100% winrate in that game for either player 1 or player 2.
  If creating an 100% winrate AI is impossible, then my goal is to create one that's at least better than all the other AI's. As of right now I am writing everything in PHP because I am competing against another AI's that are written in scripting language as well. </p>
  
  <p>This whole thing is recursive and the basic logic is:
  Compute the ENTIRE TREE of ALL possible moves
  If it is my AI's turn, then pick the route with maximum number of points for AI player. If it is opponent's AI's turn, then pick the route with minimum number of points for my AI. Aka compute number of guaranteed points at each node. </p>
  
  <p>After computing the entire tree, pick the route with the highest number of guaranteed points. On Even points, pick randomly.</p>
  
  <p>This whole computation process will take roughly forever to compute on 15x15 board, however for now all i am going for is computing it on 3x3 matrix. I will store best possible moves for first 6-8 moves in a database in order to now have to re-compute them again, this changing the complexity of each computation from 24! to 18!. </p>
  
  <p>Is this whole thing doable? And Is there a problem with the way I compute my moves? Is there a better way to do this?</p>