Sign in with
Sign up | Sign in
Your question

How many games of chess are there?

Last response: in Video Games
Share
Anonymous
September 13, 2005 6:54:36 PM

Archived from groups: rec.games.chess.computer (More info?)

The only estimate I know of is Littlewood's. He deduced an upper bound
of 10^10^70.5.Has anyone produced a reasonable lower bound?

More about : games chess

Anonymous
September 13, 2005 6:54:37 PM

Archived from groups: rec.games.chess.computer (More info?)

"Ray Johnstone" <ray@iinet.com.au> wrote in message
news:bntci1htn4k7o05isqaqdngm02ej5ernp1@4ax.com...
> The only estimate I know of is Littlewood's. He deduced an upper bound
> of 10^10^70.5.Has anyone produced a reasonable lower bound?

Why is there an upper bound? There are a limited number of pieces and a
limited number of squares, surely someone could work out every possible
permutation from there and then just strike off all the illegal positions?
Anonymous
September 13, 2005 6:54:37 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Ray Johnstone wrote:

>The only estimate I know of is Littlewood's. He deduced an upper
>bound of 10^10^70.5.

In _Programming a Computer for Playing Chess_ (found in Levy's
_Computer Chess Compendium_) Shannon estimates 64!/(32!*8!^2*2!^6),
or roughly 10^43.

Also see:
http://mathworld.wolfram.com/Chess.html
http://www.cs.berkeley.edu/~flab/chess/statistics-posit...
http://www.research.att.com/cgi-bin/access.cgi/as/njas/...
http://www.research.att.com/cgi-bin/access.cgi/as/njas/...
http://www.research.att.com/cgi-bin/access.cgi/as/njas/...
http://www.combinatorics.org/Volume_11/Abstracts/v11i2a...
http://anduin.eldar.org/~problemi/papers.html
http://ite.pubs.informs.org/Vol2No2/ChlondToase/

In my opinion, all of the above calculations are wrong. Because a
game of chess can be infinitely long, there are an infinite number
of possible games.

---------------------------------------------------------

LONGEST POSSIBLE CHESS GAME CALCULATION:
By Guy Macon <http://www.guymacon.com/&gt;

Here is my calculation for the longest possible chess
game before one of the players can claim a draw under
FIDE rules. (If nobody claims a draw the players can
continue to push pieces back and forth forever and the
game is infinitely long - and boring to calculate.) See
<http://www.fide.com/official/handbook.asp?level=EE101&g...;

Note to the non-chessplayer: a "ply" is a black piece
changing position or a white piece changing position.
Chessplayers call ten black piece moving and ten white
pieces moving "ten moves"/"twenty plies." Non-chess-players
often call the same sequence "twenty moves."

To calculate the longest possible chess game before one
of the players can claim a draw under FIDE rules:

Start with 32 chess pieces.

Move 100 plies, avoiding repeating positions.

On ply 100, move a pawn or make a capture.

Repeat N times until you make the last capture that
leaves 2 kings.

So how big is N?

There are 30 100-ply sequences ending with a capture.

There are 96 100-ply sequences ending with a pawn move.

8 of these sequences end with a pawn move that is also a capture.

1 of those sequences is only 98 plies long so that black can start
taking his turn moving pawns and making captures.

Assuming FIDE rules, that comes to a total of
((100*(30+96-8))-1)=11799 plies until the game is over.

- - - - - - - - - - - - - - -

Here is one way of reaching the maximum number of moves
in a chess game (see calculation above). Assume that
each ply described has 99 or (in one case) 98 "wasted"
plies between the plies described..

White advances his A,C,E,G pawns as far as they will go.

Black advances his B,D,F,H pawns as far as they will go.

White captures every black piece except 8 pawns, 2 knights,
1 bishop, one rook, and a King.

The white pawns on A,C,E,G capture the knights, bishops and rook,
passing and freeing the black pawns blocking them.

The now-unblocked black pawns move forward, promote, and move into
position to be taken by the white pawns on B,D,F,H, unblocking the
black pawns on B,D,F,H.

The now-unblocked black pawns move forward, promote, and are taken.

Black now only has a king. (Here is the lone 98 ply sequence) The
black king captures something, and the game continues a capture
by black on every 100th ply. When black captures the last white
piece, there are only the two kings left and the game is a draw
after exactly (and no more than) 11799 plies.

Comments/corrections are welcome.

Guy Macon
<a href="http://www.guymacon.com/">
http://www.guymacon.com/
</a>

---------------------------------------------------------

BTW, here is how to generate an infinite number of games:
Push pieces back and forth 1,000 times, then checkmate.
Push pieces back and forth 1,001 times, then checkmate.
Push pieces back and forth 1,002 times, then checkmate.
Push pieces back and forth 1,003 times, then checkmate.
Push pieces back and forth 1,004 times, then checkmate.
....
Related resources
Anonymous
September 13, 2005 6:54:38 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Lee Harris wrote:

>Why is there an upper bound? There are a limited number of pieces and a
>limited number of squares, surely someone could work out every possible
>permutation from there and then just strike off all the illegal positions?

Number of positions and number of games are two different questions.

They do have one thing in common; many smart people making many
calculations and coming up with many different answers. :) 
Anonymous
September 13, 2005 6:54:38 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Guy Macon <http://www.guymacon.com&gt; wrote:
> Ray Johnstone wrote:
>> The only estimate I know of is Littlewood's. He deduced an upper
>> bound of 10^10^70.5.
>
> In _Programming a Computer for Playing Chess_ (found in Levy's
> _Computer Chess Compendium_) Shannon estimates 64!/(32!*8!^2*2!^6),
> or roughly 10^43.

I don't have a copy of the book to hand but that looks like an estimate of
the number of positions, not games.


Dave.

--
David Richerby Natural Flammable Monk (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a man of God but it burns really
easily and it's completely natural!
Anonymous
September 13, 2005 6:54:38 PM

Archived from groups: rec.games.chess.computer (More info?)

Lee Harris <leeh@medphysics.leeds.ac.uk> wrote:
> Ray Johnstone <ray@iinet.com.au> wrote:
>> The only estimate I know of is Littlewood's. He deduced an upper bound
>> of 10^10^70.5.Has anyone produced a reasonable lower bound?
>
> Why is there an upper bound?

To say that something is an upper bound for a quantity just means that the
quantity can't possibly be bigger than that.


> There are a limited number of pieces and a limited number of squares,
> surely someone could work out every possible permutation from there and
> then just strike off all the illegal positions?

In theory, yes. In practise, this requires an infeasible amount of
computation so we have to estimate.


Dave.

--
David Richerby Cyber-Ghost (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ haunting spirit that exists only in
your computer!
Anonymous
September 13, 2005 8:10:43 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Guy Macon wrote:


> In _Programming a Computer for Playing Chess_ (found in Levy's
> _Computer Chess Compendium_) Shannon estimates 64!/(32!*8!^2*2!^6),
> or roughly 10^43.

But that is not games, those are 'positions' ... or rather ways of
placing chess pieces on a chess board without paying too close attention
to rules.

Games are one lousy position after another, and so there should be
considerably more games ...


--
Anders Thulin ath*algonet.se http://www.algonet.se/~ath
Anonymous
September 13, 2005 9:54:11 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon
<http://www.guymacon.com&gt; wrote:

>
>
>
>Ray Johnstone wrote:
>
>>The only estimate I know of is Littlewood's. He deduced an upper
>>bound of 10^10^70.5.
>
>In _Programming a Computer for Playing Chess_ (found in Levy's
>_Computer Chess Compendium_) Shannon estimates 64!/(32!*8!^2*2!^6),
>or roughly 10^43.
>
>Also see:
>http://mathworld.wolfram.com/Chess.html
>http://www.cs.berkeley.edu/~flab/chess/statistics-posit...
>http://www.research.att.com/cgi-bin/access.cgi/as/njas/...
>http://www.research.att.com/cgi-bin/access.cgi/as/njas/...
>http://www.research.att.com/cgi-bin/access.cgi/as/njas/...
>http://www.combinatorics.org/Volume_11/Abstracts/v11i2a...
>http://anduin.eldar.org/~problemi/papers.html,
>http://ite.pubs.informs.org/Vol2No2/ChlondToase/
>
>In my opinion, all of the above calculations are wrong. Because a
>game of chess can be infinitely long, there are an infinite number
>of possible games.
Thanks for the advice, very helpful. But I think you are wrong about
chess being infinite.The fifty-move rule declares a game drawn if
there have been 50 moves without a capture or a pawn move. The tree
stops branching.
Anonymous
September 13, 2005 9:54:12 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Ray Johnstone wrote:

> Thanks for the advice, very helpful. But I think you are wrong about
> chess being infinite.The fifty-move rule declares a game drawn if
> there have been 50 moves without a capture or a pawn move. The tree
> stops branching.

I read somewhere that there are certain rare position, where
the analysis has revealed that one side can force a win, but
not within the constraints of the 50 move rule. This book
also said that consequently the 50 move rule is replaced by
100 move rule in these circumstances. I would welcome it, if
any expert cares to shed more light on this ??

Cheers,

Jyrki Lahtonen, Turku, Finland
Anonymous
September 13, 2005 9:54:13 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Jyrki Lahtonen wrote:
>
>Ray Johnstone wrote:
>
>> Thanks for the advice, very helpful. But I think you are wrong about
>> chess being infinite.The fifty-move rule declares a game drawn if
>> there have been 50 moves without a capture or a pawn move. The tree
>> stops branching.
>
>I read somewhere that there are certain rare position, where
>the analysis has revealed that one side can force a win, but
>not within the constraints of the 50 move rule. This book
>also said that consequently the 50 move rule is replaced by
>100 move rule in these circumstances. I would welcome it, if
>any expert cares to shed more light on this ??

In the FIDE Laws of Chess, published in 1984 and 1988, the 50-move
rule was extended to 75 moves for the following positions:

King + Rook + Bishop against King + Rook;
King + 2 Knights against King + pawn;
King + Queen + pawn one square from promotion against King + Queen;
King + Queen against King + 2 Knights;
King + Queen against King + 2 Bishops;
King + 2 Bishops against King + Knight

In 1992 during the FIDE Congress in Manila the Rules Committee
suggested establishing one rule for all endings: 50 moves, and
the General Assembly of FIDE approved the change. In 1996 the
Congress in Yerevan revisited the decision and kept the 1992
rules. There are currently no exceptions to the 50-move rule.

Source: _An Arbiter's Notebook_,
by International Arbiter Geurt Gijssen

The Archives of _An Arbiter's Notebook_ are really quite
interesting. You can find them here:
http://www.chesscafe.com/archives/archives.htm#An%20Arb...'s%20Notebook


--
Guy Macon <http://www.guymacon.com/&gt;
Anonymous
September 13, 2005 9:54:13 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Jyrki Lahtonen wrote:

> 100 move rule in these circumstances. I would welcome it, if
> any expert cares to shed more light on this ??

From the latest edition of "Artificial Intelligence: A Modern Approach
(2nd Edition)", by Stuart J. Russell & Peter Norvig:

"Remarkable work by Ken Thompson and Lewis Stiller (1992) solved all
five-piece and some six-piece chess endgames, making them available on
the Internet. Stiller discovered one case where a forced mate existed
but required 262 moves; this caused some consternation because the rules
of chess require some “progress” to occur within 50 moves."

Here's the quote, rather cryptic:
Stiller, L. (1992). KQNKRR. ICCA Journal, Vol. 15, No. 1, pp. 16-18. (N)

ciao!
S
Anonymous
September 13, 2005 9:54:13 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Jyrki Lahtonen <lahtonen@utu.fi> wrote:
> I read somewhere that there are certain rare position, where the
> analysis has revealed that one side can force a win, but not within the
> constraints of the 50 move rule. This book also said that consequently
> the 50 move rule is replaced by 100 move rule in these circumstances. I
> would welcome it, if any expert cares to shed more light on this ??

There are positions such as rook and bishop vs rook where there are forced
mates that take more than 50 moves and even some positions (with other
material) where it can take over 200 moves to force mate even with optimal
play. This sort of thing was discovered through endgame tablebases and
two nice examples, due to Stiller, are at

http://www.xs4all.nl/~timkr/chess/perfect.htm

For a time, the 50-move rule in the FIDE laws was extended to deal with
cases like these but, in practice, these things come very infrequently and
the law was changed back to 50 moves in all circumstances. In many of
these forced mates, the first hundred moves look completely random anyway
so there's very little chance of a human being able to reproduce them.


Dave.

--
David Richerby Frozen Incredible Gnome (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a smiling garden ornament but
it'll blow your mind and it's frozen
in a block of ice!
Anonymous
September 13, 2005 9:54:14 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Guy Macon wrote:
There are currently no exceptions to the 50-move rule.
>
Thanks. Much appreciated. Apparently the book I read was
printed in the late 80s :) 

Cheers,

Jyrki
Anonymous
September 14, 2005 12:05:32 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

In article <038di1dsrr4tq6eg9614m6hqpodcpbub0t@4ax.com>,
Ray Johnstone <ray@iinet.com.au> wrote:

> On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon
> <http://www.guymacon.com&gt; wrote:

> >In my opinion, all of the above calculations are wrong. Because a
> >game of chess can be infinitely long, there are an infinite number
> >of possible games.

> Thanks for the advice, very helpful. But I think you are wrong about
> chess being infinite.The fifty-move rule declares a game drawn if
> there have been 50 moves without a capture or a pawn move. The tree
> stops branching.

You may have missed the part where he wrote,

If nobody claims a draw the players can
continue to push pieces back and forth forever and the
game is infinitely long

The point being one player or the other must *claim* the draw,
it is not enforced automatically by anyone.

--
Gerry Myerson (gerry@maths.mq.edi.ai) (i -> u for email)
Anonymous
September 14, 2005 12:05:33 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Gerry Myerson a écrit :
> In article <038di1dsrr4tq6eg9614m6hqpodcpbub0t@4ax.com>,
> Ray Johnstone <ray@iinet.com.au> wrote:
>
>
>>On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon
>><http://www.guymacon.com&gt; wrote:
>
>
>>>In my opinion, all of the above calculations are wrong. Because a
>>>game of chess can be infinitely long, there are an infinite number
>>>of possible games.
>
>
>>Thanks for the advice, very helpful. But I think you are wrong about
>>chess being infinite.The fifty-move rule declares a game drawn if
>>there have been 50 moves without a capture or a pawn move. The tree
>>stops branching.
>
>
> You may have missed the part where he wrote,
>
> If nobody claims a draw the players can
> continue to push pieces back and forth forever and the
> game is infinitely long
>
> The point being one player or the other must *claim* the draw,
> it is not enforced automatically by anyone.
>
You hve never participated in a real tournament, have you? Referees do
intervene, you know... If only to be able to draw the next round...
Anonymous
September 14, 2005 12:05:34 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Content-Transfer-Encoding: 8Bit


Ray Johnstone wrote:
>
>Guy Macon <http://www.guymacon.com&gt; wrote:
>
>>Because a game of chess can be infinitely long, there are an
>>infinite number of possible games.
>
>Thanks for the advice, very helpful. But I think you are wrong about
>chess being infinite.The fifty-move rule declares a game drawn if
>there have been 50 moves without a capture or a pawn move.

No it doesn't. Go look at
http://www.fide.com/official/handbook.asp?level=EE101
section 9.3. Note the phrase "The game is drawn, upon a correct
claim by the player having the move." He does not have to claim
a draw. They can play on forever.

-------------------------------------------------------------

denis feldmann wrote:

>Gerry Myerson a écrit :
>>
>> You may have missed the part where he wrote,
>>
>> If nobody claims a draw the players can
>> continue to push pieces back and forth forever and the
>> game is infinitely long
>>
>> The point being one player or the other must *claim* the draw,
>> it is not enforced automatically by anyone.
>>
>You have never participated in a real tournament, have you?

Plenty of them. FIDE and USCF. (We are, of course, discussing
FIDE rules. I dare anyone to repeat my calculations under USCF
rules; the USCF rules are rather unclear in many areas.)

>Referees do intervene, you know...

I don't know what you consider a "real tournament", but FIDE
tournaments have Arbiters, not Referees.

>Referees do intervene, you know...
>If only to be able to draw the next round...

No they don't. To do so would be against the rules.
Look at http://www.fide.com/official/handbook.asp?level=EE101
section 13.6. Note the phrase "The arbiter must not intervene
in a game except in cases described by the Laws of Chess." Now
try to find a place in the Laws of Chess wher an arbiter is
allowed to claims a 50-move draw when neither player has made
such a claim.


--
Guy Macon <http://www.guymacon.com/&gt;
Anonymous
September 14, 2005 12:05:34 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

denis feldmann <denis-feldmann@club-internet.fr> writes in article <4326ad62$0$308$7a628cd7@news.club-internet.fr> dated Tue, 13 Sep 2005 12:43:52 +0200:
>Gerry Myerson a écrit :
>> The point being one player or the other must *claim* the draw,
>> it is not enforced automatically by anyone.
>>
>You hve never participated in a real tournament, have you? Referees do
>intervene, you know... If only to be able to draw the next round...

No good TD would call the game a draw unless there was no possibility of a
win by either side. If a game takes too long, he might order it adjourned
(suspended) and post pairings for the next round as if it were a draw, but
the final score would have to include the actual result of that game.

I have played in tournaments where this has happened.

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
September 14, 2005 7:44:26 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

"denis feldmann" <denis-feldmann@club-internet.fr>

> You hve never participated in a real tournament, have you? Referees do
> intervene, you know... If only to be able to draw the next round...

But that's not the point; the question is whether there is something in the
laws of chess that FORCE the game to be a draw by the 50-move-rule.

The answer is "no", as, indeed, one of the players has to claim a draw. So
the players could go on playing, say, 1. Nf3 Nf6 2. Nb1 Ng8 3. Nf3 ...
forever; so there is an infinite number of games. (At least the one ending
in a draw after the first move, after the second move... after the nth
move... in this sequence).

The reason most "how many games are there?" calculations pretend that the
50-move-rule is "automatically"in effect, so to speak, is that if it is not,
the answer is trivially "an infinite number".

Incidentally, on the "50 moves rule optional" reading of the laws of chess,
there seems to be nothing in the rules of chess that forbids the possiblity
of an infinitely long game (such as the sequence of knight moves above going
on forever). If that is allowed, then there is an uncountable infinite
number of games; if it is not (and we assume that, even without the
50-move-law, every game has a finite number of moves).

Proof is left as excercise to the reader ;) 

By
Anonymous
September 14, 2005 1:03:34 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Skeptic <apilpel1@nyc.rr.com> wrote:
> denis feldmann <denis-feldmann@club-internet.fr>
>> You hve never participated in a real tournament, have you? Referees do
>> intervene, you know... If only to be able to draw the next round...

In all the tournaments I've played in, the mechanism used to prevent games
going on arbitrarily long is the clock, not the arbiter.


> The answer is "no", as, indeed, one of the players has to claim a draw.
> So the players could go on playing, say, 1. Nf3 Nf6 2. Nb1 Ng8 3. Nf3
> ... forever; so there is an infinite number of games. (At least the one
> ending in a draw after the first move, after the second move... after
> the nth move... in this sequence).

(These would be draws by agreement, for the first five moves, draws by
agreement or claim of threefold repetition from the sixth to 49th and by
agreement or claim by the 50-move rule thereafter but that doesn't matter
as they're still distinct games.)


> The reason most "how many games are there?" calculations pretend that
> the 50-move-rule is "automatically"in effect, so to speak, is that if it
> is not, the answer is trivially "an infinite number".

From a practical point of view, it's a good idea to treat the 50-move rule
as mandatory. You should always assume that your opponent will play the
best possible move and that includes claiming any draw available if they
are in a worse position. From the point of view of trying to determine
whether chess is a forced win for either player or a forced draw, the
50-move rule and threefold repetition rule are just bounded ways of saying
``infinite plays are drawn''.

Admittedly, this is slightly at odds with the idea of counting the number
of possible games because a pair of beginners might shuffle their knights
for a hundred moves before one of them remembered the 50-move rule and
another twenty-five while they argued about it, while Kramnik and Leko
would just claim by repetition at White's fifth.


> Incidentally, on the "50 moves rule optional" reading of the laws of
> chess, there seems to be nothing in the rules of chess that forbids the
> possiblity of an infinitely long game (such as the sequence of knight
> moves above going on forever).

The use of clocks is explicitly mentioned in the rules. On the other
hand, I don't think there's anything that says that the clock must be set
to indicate that the game is over at any point. :-)


Dave.

--
David Richerby Cheese Wine (TM): it's like a vintage
www.chiark.greenend.org.uk/~davidr/ Beaujolais that's made of cheese!
Anonymous
September 14, 2005 2:02:54 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Guy Macon wrote:

> In my opinion, all of the above calculations are wrong. Because a
> game of chess can be infinitely long, there are an infinite number
> of possible games.

I don't think a game that repeats sequences wholesale (including a
return to the same sequence start point) could be considered a new game,
and since this would be sure to happen in an infinitely long game then
that game would be "just another game", and nothing special from the
point of view of creating fresh and unique instances of games.

Pete.
--
Peter Clinch Medical Physics IT Officer
Tel 44 1382 660111 ext. 33637 Univ. of Dundee, Ninewells Hospital
Fax 44 1382 640177 Dundee DD1 9SY Scotland UK
net p.j.clinch@dundee.ac.uk http://www.dundee.ac.uk/~pjclinch/
Anonymous
September 14, 2005 2:19:35 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Peter Clinch <p.j.clinch@dundee.ac.uk> wrote:
> Guy Macon wrote:
>> In my opinion, all of the above calculations are wrong. Because a
>> game of chess can be infinitely long, there are an infinite number
>> of possible games.
>
> I don't think a game that repeats sequences wholesale (including a
> return to the same sequence start point) could be considered a new game,
> and since this would be sure to happen in an infinitely long game then
> that game would be "just another game", and nothing special from the
> point of view of creating fresh and unique instances of games.

A game that follows another one but inserts a few repetitions is certainly
a different game! It's not a very interesting different game but it's not
the same game as the one without the repetitions. In particular, the
original game might have been won by White but Black might have missed a
claim for draw by repetition in the new one.


Dave.

--
David Richerby Voodoo Laser (TM): it's like an
www.chiark.greenend.org.uk/~davidr/ intense beam of light that has
mystical powers!
Anonymous
September 14, 2005 4:07:52 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

| David Richerby wrote:
|> Skeptic wrote:
|>> denis feldmann wrote:
|>> You hve never participated in a real tournament, have you? Referees do
|>> intervene, you know... If only to be able to draw the next round...

| In all the tournaments I've played in, the mechanism used to prevent games
| going on arbitrarily long is the clock, not the arbiter.
-----[-----snipped-----]-----

The clock doesn't stop an arbitrarily long game. The clock gets reset
(as I understand it) when both players have made 40 or 50 moves, depending
upon the tournament rules. ______________________________________Gerard S.
Anonymous
September 14, 2005 4:19:19 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

"Skeptic" <apilpel1@nyc.rr.com> wrote in message
news:u0NVe.3603$Ap4.360262@twister.nyc.rr.com...
>
> Incidentally, on the "50 moves rule optional" reading of the
> laws of chess, there seems to be nothing in the rules of
> chess that forbids the possiblity of an infinitely long game
> (such as the sequence of knight moves above going
> on forever). If that is allowed, then there is an uncountable
> infinite number of games; if it is not (and we assume that,
> even without the 50-move-law, every game has a finite
> number of moves).

By "uncountable infinite" do you mean Aleph-1? I can't see why the number of
games isn't Aleph-0.

--
John Rowland - Spamtrapped
Transport Plans for the London Area, updated 2001
http://www.geocities.com/Athens/Acropolis/7069/tpftla.h...
A man's vehicle is a symbol of his manhood.
That's why my vehicle's the Piccadilly Line -
It's the size of a county and it comes every two and a half minutes
Anonymous
September 14, 2005 5:32:17 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

In article <11id7l1glhlupc9@corp.supernews.com>,
Guy Macon <http://www.guymacon.com&gt; wrote:

>
> In my opinion, all of the above calculations are wrong. Because a
> game of chess can be infinitely long, there are an infinite number
> of possible games.
>

The most basic point is that, to do these calculations, you're going to
assume something simple like "In any game that goes 200 moves or more
without a pawn advance or capture, one side will claim a draw." Of
course, you'll get different answers assuming different numbers from
200. For this reason, I think people often pick 50 moves, since that's
the earliest a draw can be claimed. You can also add in that a draw will
be claimed when possible if there's a three-fold rep, but that makes
calculations pretty hard, I'd bet.

--Harold Buck


"I used to rock and roll all night,
and party every day.
Then it was every other day. . . ."
-Homer J. Simpson
Anonymous
September 14, 2005 5:39:11 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

"John Rowland" <johnr@journeyflow.spamspam.demon.co.uk> writes:

> "Skeptic" <apilpel1@nyc.rr.com> wrote in message
> news:u0NVe.3603$Ap4.360262@twister.nyc.rr.com...
>>
>> Incidentally, on the "50 moves rule optional" reading of the
>> laws of chess, there seems to be nothing in the rules of
>> chess that forbids the possiblity of an infinitely long game
>> (such as the sequence of knight moves above going
>> on forever). If that is allowed, then there is an uncountable
>> infinite number of games; if it is not (and we assume that,
>> even without the 50-move-law, every game has a finite
>> number of moves).
>
> By "uncountable infinite" do you mean Aleph-1? I can't see why the number of
> games isn't Aleph-0.

If an infinitely long game is considered a game, then just think that
we have gotten into a situation where there is a possibility for a
circular move sequence A, and a circular move sequence B (where
circular means that the board is not changed after the sequence).

Now I can compose continuations consisting of an arbitrary infinite
sequence of A or B. That's Aleph-1.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Anonymous
September 14, 2005 5:39:12 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

"David Kastrup" <dak@gnu.org> wrote in message
news:85k6hjvpy8.fsf@lola.goethe.zz...
> "John Rowland" <johnr@journeyflow.spamspam.demon.co.uk> writes:
> >
> > By "uncountable infinite" do you mean Aleph-1?
> > I can't see why the number of games isn't Aleph-0.
>
> If an infinitely long game is considered a game,
> then just think that we have gotten into a situation
> where there is a possibility for a circular move
> sequence A, and a circular move sequence B
> (where circular means that the board is not
> changed after the sequence).
>
> Now I can compose continuations consisting of an arbitrary infinite
> sequence of A or B. That's Aleph-1.

No, because it is easy to count the options.
Option 1 is draw.
Option 2 is A then draw.
Option 3 is B then draw.
Option 4 is A then A then draw.
Option 5 is A then B then draw.
Option 6 is B then A then draw.
Option 7 is B then B then draw.
Option 8 is A then A then A then draw.....

Since chess games can be put into a one-to-one correspondence with the
counting numbers, the total number of games is Aleph-0.

--
John Rowland - Spamtrapped
Transport Plans for the London Area, updated 2001
http://www.geocities.com/Athens/Acropolis/7069/tpftla.h...
A man's vehicle is a symbol of his manhood.
That's why my vehicle's the Piccadilly Line -
It's the size of a county and it comes every two and a half minutes
Anonymous
September 14, 2005 5:39:12 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

David Kastrup wrote:
> If an infinitely long game is considered a game, then just think that
> we have gotten into a situation where there is a possibility for a
> circular move sequence A, and a circular move sequence B (where
> circular means that the board is not changed after the sequence).
> Now I can compose continuations consisting of an arbitrary infinite
> sequence of A or B. That's Aleph-1.

Did you just settle the continuum hypothesis there?
Anonymous
September 14, 2005 5:39:12 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

On Wed, 14 Sep 2005 13:39:11 +0200, David Kastrup wrote:
> "John Rowland" <johnr@journeyflow.spamspam.demon.co.uk> writes:

>> "Skeptic" <apilpel1@nyc.rr.com> wrote in message
>> news:u0NVe.3603$Ap4.360262@twister.nyc.rr.com...
>>>
>>> Incidentally, on the "50 moves rule optional" reading of the
>>> laws of chess, there seems to be nothing in the rules of
>>> chess that forbids the possiblity of an infinitely long game
>>> (such as the sequence of knight moves above going
>>> on forever). If that is allowed, then there is an uncountable
>>> infinite number of games; if it is not (and we assume that,
>>> even without the 50-move-law, every game has a finite
>>> number of moves).
>>
>> By "uncountable infinite" do you mean Aleph-1? I can't see why the number of
>> games isn't Aleph-0.

> If an infinitely long game is considered a game, then just think that
> we have gotten into a situation where there is a possibility for a
> circular move sequence A, and a circular move sequence B (where
> circular means that the board is not changed after the sequence).

> Now I can compose continuations consisting of an arbitrary infinite
> sequence of A or B. That's Aleph-1.

No, that's 2^aleph_0, unless you are assuming CH.



--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book...;
Anonymous
September 14, 2005 6:00:01 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

David Richerby wrote:

> A game that follows another one but inserts a few repetitions is certainly
> a different game!

Not if one of the repetition cycles is contained in the original:
nothing new is happening.

> the same game as the one without the repetitions. In particular, the
> original game might have been won by White but Black might have missed a
> claim for draw by repetition in the new one.

The draw claim is effectively external to where the pieces move, though.
By your arguments repeating something 50 times and then claiming a
draw is different to repeating it 51 times and then claiming a draw. I
don't really see it as workably different as far as different
configurations of pieces goes, which is how I read the original
question. Even if we have a possible draw or one side wins, that only
gives us one extra result, not infinite.

Pete.
--
Peter Clinch Medical Physics IT Officer
Tel 44 1382 660111 ext. 33637 Univ. of Dundee, Ninewells Hospital
Fax 44 1382 640177 Dundee DD1 9SY Scotland UK
net p.j.clinch@dundee.ac.uk http://www.dundee.ac.uk/~pjclinch/
Anonymous
September 14, 2005 6:19:07 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

"John Rowland" <johnr@journeyflow.spamspam.demon.co.uk> writes:

> "David Kastrup" <dak@gnu.org> wrote in message
> news:85k6hjvpy8.fsf@lola.goethe.zz...
>> "John Rowland" <johnr@journeyflow.spamspam.demon.co.uk> writes:
>> >
>> > By "uncountable infinite" do you mean Aleph-1?
>> > I can't see why the number of games isn't Aleph-0.
>>
>> If an infinitely long game is considered a game,
>> then just think that we have gotten into a situation
>> where there is a possibility for a circular move
>> sequence A, and a circular move sequence B
>> (where circular means that the board is not
>> changed after the sequence).
>>
>> Now I can compose continuations consisting of an arbitrary infinite
>> sequence of A or B. That's Aleph-1.
>
> No, because it is easy to count the options.
> Option 1 is draw.
> Option 2 is A then draw.
> Option 3 is B then draw.
> Option 4 is A then A then draw.
> Option 5 is A then B then draw.
> Option 6 is B then A then draw.
> Option 7 is B then B then draw.
> Option 8 is A then A then A then draw.....

What is the number of the game that goes on AABAABAABAAB... forever?

> Since chess games can be put into a one-to-one correspondence with
> the counting numbers, the total number of games is Aleph-0.

But they can't. Infinite strings over a fixed alphabet number
aleph-1, not aleph-0. Finite strings without length limit, however,
number aleph-0.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
September 14, 2005 6:19:40 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

X-no-archives:yes

> By "uncountable infinite" do you mean Aleph-1? I can't see why the number
> of
> games isn't Aleph-0.

Consider a position with, say, kings on a1 and h8, a black bishop on a8 and
a white one on h1. Let us consider a specific game that reached that
position (after a finite number of moves, of course). Consider the series of
moves S1 = "1. Bg2 Bb7 2. Bh1 Ba8", on the one hand, and S2 = "1. Bf3 Bc6 2.
Bh1 Ba8" on the other. Both get us back to the original position and can be
repeated indefinitely. If inifnite-length games are allowed, it is easy to
see that there is an isomorphism between all the games that end in an
infinite repetition of these S1, S2 moves that point, and the binary
representation of the reals between 0 and 1. Thus there are (at least)
Aleph-1 games in that case.
September 14, 2005 6:31:46 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

X-no-Archives:yes

"Robert Low" <mtx014@coventry.ac.uk> wrote in

> Did you just settle the continuum hypothesis there?

Well, you know how smart we chess players are :) 

(Of course, by Aleph-1 he meant the cardinality of the reals, or C)
September 14, 2005 6:40:22 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

> Thus there are (at least) Aleph-1 games in that case.

D'OH!

I mean, of course, 2^Aleph-0, or C, not Aleph-1... hmmm... then again,
technically speaking, that IS "at least Aleph-1 games", whatever one thinks
about the continuum hypothesis :) 
Anonymous
September 14, 2005 7:05:26 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Dave Seaman <dseaman@no.such.host> writes:

> On Wed, 14 Sep 2005 13:39:11 +0200, David Kastrup wrote:
>> "John Rowland" <johnr@journeyflow.spamspam.demon.co.uk> writes:
>
>>> "Skeptic" <apilpel1@nyc.rr.com> wrote in message
>>> news:u0NVe.3603$Ap4.360262@twister.nyc.rr.com...
>>>>
>>>> Incidentally, on the "50 moves rule optional" reading of the
>>>> laws of chess, there seems to be nothing in the rules of
>>>> chess that forbids the possiblity of an infinitely long game
>>>> (such as the sequence of knight moves above going
>>>> on forever). If that is allowed, then there is an uncountable
>>>> infinite number of games; if it is not (and we assume that,
>>>> even without the 50-move-law, every game has a finite
>>>> number of moves).
>>>
>>> By "uncountable infinite" do you mean Aleph-1? I can't see why the number of
>>> games isn't Aleph-0.
>
>> If an infinitely long game is considered a game, then just think that
>> we have gotten into a situation where there is a possibility for a
>> circular move sequence A, and a circular move sequence B (where
>> circular means that the board is not changed after the sequence).
>
>> Now I can compose continuations consisting of an arbitrary infinite
>> sequence of A or B. That's Aleph-1.
>
> No, that's 2^aleph_0, unless you are assuming CH.

From the little I have understood here, without CH, Aleph_1 would not
even be identifiable as the cardinality of any set. At least if the
definition of "Aleph_1" would be "next cardinality after Aleph_0".

Feel free to fill in the details that I am unaware of.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Anonymous
September 14, 2005 7:05:27 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

On Wed, 14 Sep 2005 15:05:26 +0200, David Kastrup wrote:
> Dave Seaman <dseaman@no.such.host> writes:

>>>> By "uncountable infinite" do you mean Aleph-1? I can't see why the number of
>>>> games isn't Aleph-0.
>>
>>> If an infinitely long game is considered a game, then just think that
>>> we have gotten into a situation where there is a possibility for a
>>> circular move sequence A, and a circular move sequence B (where
>>> circular means that the board is not changed after the sequence).
>>
>>> Now I can compose continuations consisting of an arbitrary infinite
>>> sequence of A or B. That's Aleph-1.
>>
>> No, that's 2^aleph_0, unless you are assuming CH.

> From the little I have understood here, without CH, Aleph_1 would not
> even be identifiable as the cardinality of any set. At least if the
> definition of "Aleph_1" would be "next cardinality after Aleph_0".

Aleph_1 is the cardinality of the set of all countable ordinals.

> Feel free to fill in the details that I am unaware of.

2^aleph_0 is by definition the cardinality of P(N), the power set of the
naturals, and is provably the same as c, the cardinality of the continuum.


--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book...;
Anonymous
September 14, 2005 7:37:00 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Peter Clinch <p.j.clinch@dundee.ac.uk> wrote:
> David Richerby wrote:
>> A game that follows another one but inserts a few repetitions is certainly
>> a different game!
>
> Not if one of the repetition cycles is contained in the original:
> nothing new is happening.

If a cycle is repeated infinitely often, inserting another cycle doesn't
make a difference, true. But it certainly makes a difference inserting
something into a finite sequence because it makes the sequence longer.


>> the same game as the one without the repetitions. In particular, the
>> original game might have been won by White but Black might have missed
>> a claim for draw by repetition in the new one.
>
> The draw claim is effectively external to where the pieces move, though.

That example was designed to show that, while playing a game, adding a
repetition of a position might make more than a trivial difference. The
game with the extra repetition would still be a valid game but it's easy
to come up with examples where you can say `If you'd have repeated the
position again, I wouldn't have played Ng1 and lost: I'd have claimed the
draw.'


> By your arguments repeating something 50 times and then claiming a
> draw is different to repeating it 51 times and then claiming a draw. I
> don't really see it as workably different as far as different
> configurations of pieces goes, which is how I read the original
> question.

A game isn't a configuration of pieces but a sequence of configurations.
Two sequences are different if they differ at any point.


> Even if we have a possible draw or one side wins, that only gives us one
> extra result, not infinite.

It's not a different result: it's a different game with the same result.

Of course, very little of this makes any difference to practical chess,
apart from my point about inserting a repetition into a game possibly
changing the result. :-)


Dave.

--
David Richerby Expensive Robot (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a high-tech robot but it'll break
the bank!
Anonymous
September 14, 2005 8:08:34 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Skeptic wrote:
> "Robert Low" <mtx014@coventry.ac.uk> wrote in
>>Did you just settle the continuum hypothesis there?
> Well, you know how smart we chess players are :) 

I know how bad a chess player I am, so I refuse
to admit that being good at chess is a sign
of intellectual merit. :-)

> (Of course, by Aleph-1 he meant the cardinality of the reals, or C)

It's a common slip of the brain, and one I've made myself
more than once. But why pass up the opportunity for a gentle
dig?
Anonymous
September 14, 2005 10:30:35 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Skeptic wrote:

>The reason most "how many games are there?" calculations pretend that the
>50-move-rule is "automatically"in effect, so to speak, is that if it is not,
>the answer is trivially "an infinite number".

This is also the reason I specified "Here is my calculation for the
longest possible chess game before one of the players can claim a
draw under FIDE rules"... :) 
Anonymous
September 14, 2005 10:45:42 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

gerard46 <gerard46@rrt.net> wrote:
> David Richerby wrote:
>> Skeptic wrote:
>>> denis feldmann wrote:
>>> You hve never participated in a real tournament, have you? Referees do
>>> intervene, you know... If only to be able to draw the next round...
>>
>> In all the tournaments I've played in, the mechanism used to prevent
>> games going on arbitrarily long is the clock, not the arbiter.
>
> The clock doesn't stop an arbitrarily long game. The clock gets reset
> (as I understand it) when both players have made 40 or 50 moves,
> depending upon the tournament rules.

These days, almost all tournaments are played without adjournments so the
time controls typically ensure the game must be played within some fixed
time. In amateur tournaments in the UK, the standard time control seems
to be 90 minutes with an extra 15/20 minutes added after Black's 36th
move; for Grandmaster tournaments, it's usual to have two hours, with an
extra hour after the 40th move and extra hour (half hour?) after the 60th.


Dave.

--
David Richerby Simple Bulb (TM): it's like a light
www.chiark.greenend.org.uk/~davidr/ bulb but it has no moving parts!
Anonymous
September 14, 2005 10:49:24 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

David Richerby wrote:

>In all the tournaments I've played in, the mechanism used to prevent
>games going on arbitrarily long is the clock, not the arbiter.

A typical FIDE time control is 40 moves in 75 minutes, 15 minutes for
the remainder of the game and an increment of 30 seconds per move starting
with the first move. So if the players take less than 30 seconds per move
(not an unreasonable assumption if they are just moving knights back and
forth and not claiming the available draw) the time left grows without
bound. The players could rack up an hour and the go to lunch, 8 hours
to catch some sleep, or several week to take a nice vacation!
Anonymous
September 14, 2005 10:49:25 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

In article <11igs5krpro1afc@corp.supernews.com>,
Guy Macon <http://www.guymacon.com/&gt; wrote:

>
> David Richerby wrote:
>
> >In all the tournaments I've played in, the mechanism used to prevent
> >games going on arbitrarily long is the clock, not the arbiter.
>
> A typical FIDE time control is 40 moves in 75 minutes, 15 minutes for
> the remainder of the game and an increment of 30 seconds per move starting
> with the first move. So if the players take less than 30 seconds per move
> (not an unreasonable assumption if they are just moving knights back and
> forth and not claiming the available draw) the time left grows without
> bound. The players could rack up an hour and the go to lunch, 8 hours
> to catch some sleep, or several week to take a nice vacation!


And, besides, you have to claim the win on time, do you not?

--Harold Buck


"I used to rock and roll all night,
and party every day.
Then it was every other day. . . ."
-Homer J. Simpson
Anonymous
September 14, 2005 10:58:17 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Dave Seaman wrote:
>
>David Kastrup wrote:
>
>>John Rowland writes:
>>
>>> "Skeptic" wrote...
>>>>
>>>> Incidentally, on the "50 moves rule optional" reading of the
>>>> laws of chess, there seems to be nothing in the rules of
>>>> chess that forbids the possiblity of an infinitely long game
>>>> (such as the sequence of knight moves above going
>>>> on forever). If that is allowed, then there is an uncountable
>>>> infinite number of games; if it is not (and we assume that,
>>>> even without the 50-move-law, every game has a finite
>>>> number of moves).
>>>
>>> By "uncountable infinite" do you mean Aleph-1? I can't see why the number of
>>> games isn't Aleph-0.
>
>> If an infinitely long game is considered a game, then just think that
>> we have gotten into a situation where there is a possibility for a
>> circular move sequence A, and a circular move sequence B (where
>> circular means that the board is not changed after the sequence).
>
>> Now I can compose continuations consisting of an arbitrary infinite
>> sequence of A or B. That's Aleph-1.
>
>No, that's 2^aleph_0, unless you are assuming CH.

This is the best "how many chess moves/positions/games" thread ever! :) 
Anonymous
September 14, 2005 11:16:25 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

David Richerby wrote:
>
>gerard46 wrote:
>
>> David Richerby wrote:
>>
>>> Skeptic wrote:
>>>
>>>> denis feldmann wrote:
>>>
>>>>You have never participated in a real tournament, have you? Referees
>>>>do intervene, you know... If only to be able to draw the next round...
>>>
>>> In all the tournaments I've played in, the mechanism used to prevent
>>> games going on arbitrarily long is the clock, not the arbiter.
>>
>> The clock doesn't stop an arbitrarily long game. The clock gets reset
>> (as I understand it) when both players have made 40 or 50 moves,
>> depending upon the tournament rules.
>
>These days, almost all tournaments are played without adjournments so the
>time controls typically ensure the game must be played within some fixed
>time. In amateur tournaments in the UK, the standard time control seems
>to be 90 minutes with an extra 15/20 minutes added after Black's 36th
>move; for Grandmaster tournaments, it's usual to have two hours, with an
>extra hour after the 40th move and extra hour (half hour?) after the 60th.

You are forgetting that these days, almost all tournaments are played
with time added to the clock (typ. 30s) at each move. So our players who
are just shuttling knights back and forth and not claiming the available
draw can cause the time left to grow as large as they choose.

If one decides to use time controls as a limiting factor, the question
of " How many games of chess are there?" would have to include postal
chess, blitz chess, and chess played without clocks. (Articles 1-5 of
the FIDE rules apply to all games but make no mention of clocks,
articles 6-14 give the rules for clocks, but are clearly labeled as
"competition rules.")
Anonymous
September 15, 2005 1:19:57 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Guy Macon <http://www.guymacon.com/&gt; writes:

> Dave Seaman wrote:
>>
>>David Kastrup wrote:
>>
>>>John Rowland writes:
>>>
>>>> "Skeptic" wrote...
>>>>>
>>>>> Incidentally, on the "50 moves rule optional" reading of the
>>>>> laws of chess, there seems to be nothing in the rules of
>>>>> chess that forbids the possiblity of an infinitely long game
>>>>> (such as the sequence of knight moves above going
>>>>> on forever). If that is allowed, then there is an uncountable
>>>>> infinite number of games; if it is not (and we assume that,
>>>>> even without the 50-move-law, every game has a finite
>>>>> number of moves).
>>>>
>>>> By "uncountable infinite" do you mean Aleph-1? I can't see why
>>>> the number of games isn't Aleph-0.
>>
>>> If an infinitely long game is considered a game, then just think
>>> that we have gotten into a situation where there is a possibility
>>> for a circular move sequence A, and a circular move sequence B
>>> (where circular means that the board is not changed after the
>>> sequence).
>>
>>> Now I can compose continuations consisting of an arbitrary
>>> infinite sequence of A or B. That's Aleph-1.
>>
>>No, that's 2^aleph_0, unless you are assuming CH.
>
> This is the best "how many chess moves/positions/games" thread ever!
> :) 

You can always add a successor thread by starting with an exact copy
of this thread and adding a clever reply. So "best ever" sounds
untenable.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Anonymous
September 15, 2005 1:19:58 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

David Kastrup wrote:

>Guy Macon <http://www.guymacon.com/&gt; writes:
>
>> Dave Seaman wrote:
>>>
>>>David Kastrup wrote:
>>>
>>>> Now I can compose continuations consisting of an arbitrary
>>>> infinite sequence of A or B. That's Aleph-1.
>>>
>>>No, that's 2^aleph_0, unless you are assuming CH.
>>
>> This is the best "how many chess moves/positions/games" thread ever!
>> :) 
>
>You can always add a successor thread by starting with an exact copy
>of this thread and adding a clever reply. So "best ever" sounds
>untenable.

Unless, of course, there is a thread length at which point any
reply, no matter how clever, adds negative worth. If I assume
that N posts that are exact duplicates of previous posts comprise
spam, that spam has negative worth, and that newsservers place an
upper bound on the size of a post, then eventually all added posts
to this thread or any duplicate of this thread will be negative-
value spam.

....which is the direction me email box seems to be going already. :( 
Anonymous
September 15, 2005 2:12:50 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

[ Followup-To: set -- this is a purely chess matter. ]

Guy Macon <http://www.guymacon.com/&gt; wrote:
> David Richerby wrote:
>> gerard46 wrote:
>>> David Richerby wrote:
>>>> In all the tournaments I've played in, the mechanism used to prevent
>>>> games going on arbitrarily long is the clock, not the arbiter.
>>>
>>> The clock doesn't stop an arbitrarily long game. [...]
>>
>> These days, almost all tournaments are played without adjournments so
>> the time controls typically ensure the game must be played within some
>> fixed time. In amateur tournaments in the UK, the standard time
>> control seems to be 90 minutes with an extra 15/20 minutes added after
>> Black's 36th move; for Grandmaster tournaments, it's usual to have two
>> hours, with an extra hour after the 40th move and extra hour (half
>> hour?) after the 60th.
>
> You are forgetting that these days, almost all tournaments are played
> with time added to the clock (typ. 30s) at each move.

And you're forgetting that I just said that the standard time control for
amateur tournaments in the UK seems to be 36/90+15 or +20. I infer from
your experience that there are national differences but your `almost all'
doesn't seem to be the case. Now that you mention it, I'm not sure if the
`standard' GM time controls include increment or not but I'm pretty sure
that Linares didn't.


> If one decides to use time controls as a limiting factor, the question
> of " How many games of chess are there?"

I'm not using it as a limiting factor in the number of games that exist.
I'm using it as a limiting factor to stop games going on arbitrarily long,
as I clearly stated. This is, after all, the reason they were introduced.


Dave.

--
David Richerby Indelible Boss (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ middle manager but it can't be erased!
Anonymous
September 15, 2005 2:16:25 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

David R Tribble <david@tribble.com> wrote:
> Surely a "best ever" thread would answer the original question posed
> at the start of the thread. So how many possible (finite) games of
> chess are there?

Aw, OK. There are 19,833,981,409,875,687,767,892,345. To reach this
result, I had to assume that White never opens 1.a3 but that's such a dumb
move that, after any of Black's 20 legal replies, we may assume that White
resigns. So I guess that's 19,833,981,409,875,687,767,892,365 in total.


Dave.


--
David Richerby Strange Tree (TM): it's like a tree
www.chiark.greenend.org.uk/~davidr/ but it's totally weird!
Anonymous
September 15, 2005 7:19:50 AM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

David Richerby wrote:

>[ Followup-To: set -- this is a purely chess matter. ]

Followups ignored -- this is clearly a math puzzle that just
happens to involve chess. I also restored the rest of the
paragraph where you deleted most of what I wrote, thus changing
the meaning.

>Guy Macon <http://www.guymacon.com/&gt; wrote:
>>
>> David Richerby wrote:
>>
>>> gerard46 wrote:
>>>
>>>> David Richerby wrote:
>>>>
>>>>> In all the tournaments I've played in, the mechanism used to prevent
>>>>> games going on arbitrarily long is the clock, not the arbiter.
>>>>
>>>> The clock doesn't stop an arbitrarily long game. [...]
>>>
>>> These days, almost all tournaments are played without adjournments so
>>> the time controls typically ensure the game must be played within some
>>> fixed time. In amateur tournaments in the UK, the standard time
>>> control seems to be 90 minutes with an extra 15/20 minutes added after
>>> Black's 36th move; for Grandmaster tournaments, it's usual to have two
>>> hours, with an extra hour after the 40th move and extra hour (half
>>> hour?) after the 60th.
>>
>> You are forgetting that these days, almost all tournaments are played
>> with time added to the clock (typ. 30s) at each move.
>
>And you're forgetting that I just said that the standard time control for
>amateur tournaments in the UK seems to be 36/90+15 or +20. I infer from
>your experience that there are national differences but your `almost all'
>doesn't seem to be the case. Now that you mention it, I'm not sure if the
>`standard' GM time controls include increment or not but I'm pretty sure
>that Linares didn't.
>
>>If one decides to use time controls as a limiting factor, the question
>>of " How many games of chess are there?" would have to include postal
>>chess, blitz chess, and chess played without clocks. (Articles 1-5 of
>>the FIDE rules apply to all games but make no mention of clocks,
>>articles 6-14 give the rules for clocks, but are clearly labeled as
>>"competition rules.")
>
>I'm not using it as a limiting factor in the number of games that exist.
>I'm using it as a limiting factor to stop games going on arbitrarily long

The one implies the other. My proof that there are an infinite
number of chess games under FIDE rules hinges on there being no
limit to the length of an individual game under FIDE rules.
Your arguments from your limited experience in some tournaments
(and your false assumption that I am arguing from my limited
experience in some tournaments instead of from the FIDE rules)
in no way changes those rules; under FIDE rules there are an
infinite number number of possible moves in a chess game, and
thus under FIDE rules there are an infinite number of possible
chess games.

There are some interesting consequences from the above facts.
It turns out that a powerful enough computer can still solve
chess! Those infinitely long games consist of a finite number
of positions[1], and the computer can stop searching any sequence
of moves when the sequence reaches a position[1] the second time.


[Note 1]: "position" needs to include en passant right, castling
rights, whether a 50-move or repetition draw can be claimed, etc.
- but there are still a finite number of "positions" even with
this additional information.

--
Guy Macon <http://www.guymacon.com/&gt;
Anonymous
September 15, 2005 1:26:21 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

Guy Macon <http://www.guymacon.com/&gt; wrote:
> David Richerby wrote:
>> [ Followup-To: set -- this is a purely chess matter. ]
>
> Followups ignored -- this is clearly a math puzzle that just happens to
> involve chess.

I find it hard to see any mathematical content, computer chess or general
board game content in an argument where we seem to be talking at crossed
purposes about whether chess games can last arbitrarily long so I've set
followups again.


>> I'm not using it as a limiting factor in the number of games that
>> exist. I'm using it as a limiting factor to stop games going on
>> arbitrarily long
>
> The one implies the other.

This is, I think, where we are talking at crossed purposes.
What I should have said is, ``I'm using [the clock] as a limiting factor
to stop games *in tournaments* going on arbitrarily long.'' This, I was
proposing as an alternative to somebody's suggestion further up the thread
that the mechanism for preventing games in tournaments going on
arbitrarily long was for the arbiter to step in and declare the game
drawn.

Clearly, if you and I sit down to play chess in the comfort of our own
internet, without using clocks, the game could go on an arbitrary amount
of time. Not actually an infinite amount of time, because we don't have
that long but, at a theoretical level, I'm perfectly happy to accept the
existence of infinite games of chess.


> There are some interesting consequences from the above facts [that the
> FIDE rules permit infinite games]. It turns out that a powerful enough
> computer can still solve chess! Those infinitely long games consist of
> a finite number of positions[1], and the computer can stop searching any
> sequence of moves when the sequence reaches a position[1] the second
> time.

Yes. You'd get much better pruning by using the 50-move rule, too,
because neither side would let the other win by playing more than 50
reversible moves: he'd know that the opponent was winning so claim the
draw.


Dave.

--
David Richerby Evil Swiss Chainsaw (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a lethal weapon but it's made in
Switzerland and genuinely evil!
Anonymous
September 15, 2005 1:46:28 PM

Archived from groups: rec.games.chess.computer,sci.math,rec.games.chess.misc,rec.games.board (More info?)

David Kastrup wrote:
> If an infinitely long game is considered a game, then just think that
> we have gotten into a situation where there is a possibility for a
> circular move sequence A, and a circular move sequence B (where
> circular means that the board is not changed after the sequence).
>
> Now I can compose continuations consisting of an arbitrary infinite
> sequence of A or B. That's Aleph-1.

I don't think I've ever seen the Continuum Hypothesis invoked in a
chess problem before.


- Tim
!