Re: Transactions: good or bad?

Mikito Harakiri wrote:
> "Bob Badour" <bbadour_at_golden.net> wrote in message
> news:Li5Ia.137$vn2.18732148_at_mantis.golden.net...
> > Where is your proof that all chess games halt? After all, your assertion
>

>>that chess games are finite depends on just such a proof.

I'm amazed that somebody is still following this rant.

However, one of the players have to ask for the draw, it's not a draw automatically. There are other similar draw conditions that prevent anyone players from being exposed to unnecessary burden.

Bob's claim however was a straw-man even in the absence of those rules, because a chess playing game can *prove* if a position is techincally winnable by white, or by black, or it is draw (therefore effectively calculating a proof in the formal system established by the rule of chess), simply by exhaustively applying the min.-max. recursive algorithm over the *finitely many* positions of chess.

A theorem prover for a formal system at least as powerful as to encode basic arithmetics (therefore also subject to Godel's theorem) does not have a finite space to search for and come up with the next best "move" (meaning the next best derivation rule to apply on the way to constructing the proof). While establishing a proof is effectively coming up with the next best move, because for each step of the rule we have a next inference rule to apply.

Given that they search in a game with an infinite space, programs have to decide whether evaluating a particular branch will be successful, without actually going on the branch (because branches are not guaranteed to be finite). It is there where they hit the halting problem.

Evaluation branches in chess are always finite, even if games may be infinite, because the minute you encounter a previous position you no longer need to explore the branch.

In practice it has been proven that performing an exhaustive search over the space bounded by a certain depth of analysis (let's say 20 moves, well beyond the reach of a human player) is statistically more than enough to approximate the perfect evaluation function in quite many position. Still human players get to beat chess programs simply by their better intuition.

The same way, mathematicians rely on intuition to know where to look for a proof, just like a 6 year old gets to recognize hand written character "automagically" (including taking the context of the phrase into account, the language) while there's no scientific theory to allow us to conclude that computers can do the same.

You can train a neural network for extended time and with lots of computing resources and get it to recognize typographical characters, that's fine but I recently fed Dijkstra's manuscripts to some of the best OCR programs, all of them were beyond hopeless. And Dijkstra's writing is extremely clear. Where to search for results in a Mathematical theory is extremely messy.

Yet, there's this philosophical belief of some people, that we can encode this "intutition" factor as a computable function. That's insofar completely unsupported. Received on Thu Jun 19 2003 - 19:15:19 CEST