Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old September 13th 05, 07:54 AM
Ray Johnstone
 
Posts: n/a
Default How many games of chess are there?

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?
  #2   Report Post  
Old September 13th 05, 10:14 AM
Lee Harris
 
Posts: n/a
Default


"Ray Johnstone" wrote in message
...
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?


  #3   Report Post  
Old September 13th 05, 10:40 AM
Guy Macon
 
Posts: n/a
Default




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/che...positions.html
http://www.research.att.com/cgi-bin/...i?Anum=A006494
http://www.research.att.com/cgi-bin/...i?Anum=A007545
http://www.research.att.com/cgi-bin/...i?Anum=A019319
http://www.combinatorics.org/Volume_...s/v11i2a4.html
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/

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

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.
....


  #4   Report Post  
Old September 13th 05, 10:54 AM
Ray Johnstone
 
Posts: n/a
Default

On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon
http://www.guymacon.com 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/che...positions.html
http://www.research.att.com/cgi-bin/...i?Anum=A006494
http://www.research.att.com/cgi-bin/...i?Anum=A007545
http://www.research.att.com/cgi-bin/...i?Anum=A019319
http://www.combinatorics.org/Volume_...s/v11i2a4.html
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.
  #5   Report Post  
Old September 13th 05, 11:05 AM
Gerry Myerson
 
Posts: n/a
Default

In article ,
Ray Johnstone wrote:

On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon
http://www.guymacon.com 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 ) (i - u for email)


  #6   Report Post  
Old September 13th 05, 11:43 AM
denis feldmann
 
Posts: n/a
Default

Gerry Myerson a écrit :
In article ,
Ray Johnstone wrote:


On Tue, 13 Sep 2005 09:40:48 +0000, Guy Macon
http://www.guymacon.com 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...
  #7   Report Post  
Old September 13th 05, 11:58 AM
Jyrki Lahtonen
 
Posts: n/a
Default

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
  #8   Report Post  
Old September 13th 05, 12:00 PM
Guy Macon
 
Posts: n/a
Default



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.




  #9   Report Post  
Old September 13th 05, 12:10 PM
David Richerby
 
Posts: n/a
Default

Lee Harris wrote:
Ray Johnstone 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!
  #10   Report Post  
Old September 13th 05, 12:12 PM
David Richerby
 
Posts: n/a
Default

Guy Macon http://www.guymacon.com 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!
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
rec.games.chess.misc FAQ [2/4] [email protected] rec.games.chess.misc (Chess General) 0 July 14th 04 05:20 AM
rec.games.chess.misc FAQ [2/4] [email protected] rec.games.chess.misc (Chess General) 0 June 28th 04 07:43 PM
USCF Catalogue Remainers ASCACHESS rec.games.chess.politics (Chess Politics) 2 May 13th 04 07:46 AM
Lev Khariton: With Love and Bitterness Aryeh Davidoff rec.games.chess.misc (Chess General) 2 May 6th 04 05:56 PM
rec.games.chess.misc FAQ [2/4] [email protected] rec.games.chess.misc (Chess General) 0 March 19th 04 09:36 AM


All times are GMT +1. The time now is 02:01 PM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright ©2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017