Chess -- was: Transactions: good or bad?

From: Mikito Harakiri <mikharakiri_at_ywho.com>
Date: Thu, 19 Jun 2003 15:12:32 -0700
Message-ID: <aGqIa.9$3a.149_at_news.oracle.com>

That's right, the number of possible positions is always finite, while the number of possible games might be finite only if guaranteed by the rules, or uncountable, otherwise. Just imagine players moving their queen knight once or twice and then back. If we assign 1 or 0 to both of these possibilities, then their "game" is essentially an infinite binary sequence, and there are incountably many such "games". Finding winning strategy, however, has nothing to do with games enumeration. It's position enumeration:

1. Consider next position from the space of all positions.
2. If it has black king and no white king, then mark it as "black wins".
3. Similar for symmetric situations.
4. If neither 2 nor 3 applies, then see if this position is reachable in one

step from "black wins". If it's black's turn, then mark the position as "black wins".
5. Similar for symmetric situations.
6. Mark all the rest of the positions as "Draw" at the end.

"Costin Cozianu" <c_cozianu_at_hotmail.com> wrote in message news:bcsqv8$n2di8$1_at_ID-152540.news.dfncis.de...
> 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 beleve there is a chess rule that if position is repeated, then the
game
> > is draw. It is quite obvious that the chess game is finite, then.
> >
> >
>
> 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 Fri Jun 20 2003 - 00:12:32 CEST