I was recently in a discussion with a non-coder person on the possibilities of chess computers.  I&#39;m not well versed in theory, but think I know enough.

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.

My friend thought, to the contrary, that a computer would always win or tie if it never made a &quot;mistake&quot; 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 &quot;mistake&quot; moves in the end.  Even if you know everything, your next move is greedy in matching a heuristic.

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.

Edit: Hmm... looks like I ruffled some feathers here.  That&#39;s good.

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&#39;ve pointed out something that is not yet satisfactorily proven (formally).

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.

All Game Theory Solutions on Gang of Coders

Total of 1 Game Theory Solutions

Is there a perfect algorithm for chess?