title: Is there a perfect algorithm for chess?
body: <p>I was recently in a discussion with a non-coder person on the possibilities of chess computers.  I'm not well versed in theory, but think I know enough.</p>
  
  <p>I argued that there could not exist a deterministic Turing machine that always won or stalemated at chess.  I think that, even if you search the entire space of all combinations of player1/2 moves, the single move that the computer decides upon at each step is based on a heuristic.  Being based on a heuristic, it does not necessarily beat ALL of the moves that the opponent could do.</p>
  
  <p>My friend thought, to the contrary, that a computer would always win or tie if it never made a "mistake" move (however do you define that?).  However, being a programmer who has taken CS, I know that even your good choices - given a wise opponent - can force you to make "mistake" moves in the end.  Even if you know everything, your next move is greedy in matching a heuristic.</p>
  
  <p>Most chess computers try to match a possible end game to the game in progress, which is essentially a dynamic programming traceback.  Again, the endgame in question is avoidable though.</p>
  
  <p>Edit: Hmm... looks like I ruffled some feathers here.  That's good.</p>
  
  <p>Thinking about it again, it seems like there is no theoretical problem with solving a finite game like chess.  I would argue that chess is a bit more complicated than checkers in that a win is not necessarily by numerical exhaustion of pieces, but by a mate.  My original assertion is probably wrong, but then again I think I've pointed out something that is not yet satisfactorily proven (formally).</p>
  
  <p>I guess my thought experiment was that whenever a branch in the tree is taken, then the algorithm (or memorized paths) must find a path to a mate (without getting mated) for any possible branch on the opponent moves. After the discussion, I will buy that given more memory than we can possibly dream of, all these paths could be found.</p>