| Topic: |
Science > Physics |
| User: |
"Guy Macon http://www.guymacon.com/" |
| Date: |
25 May 2005 10:01:30 AM |
| Object: |
Longest Possible Chess game |
(This came out of an ongoing discussion about whether
playing chess shows intelligence, with a comparison of
Nalimov Tablebase lookups and the Chinese Room thought
experiment.)
Note to the non-chess-player: a "ply" is a black move or
a white move. Cheesplayers call ten black 'moves' and ten
white 'moves' ten moves/twenty plies. "FIDE" is the
international chess federation. A "3 man Nalimov
Tablebase" is a database of every possible position that
3 chesspieces (king, king, pawn, king,king, rook, etc.)
can be in along with instructions on how to play perfectly
(shortest possible path to a win or longest possible path
to a draw/loss) for each position.
Mike Murray wrote:
Guy Macon <http://www.guymacon.com/> wrote:
Complete 3 man Nalimov Tablebase...80KB
Complete 3+4 man Nalimov Tablebase...30MB
Complete 3+4+5 man Nalimov Tablebase...7GB
Complete 3+4+5+6 man Nalimov Tablebase...1-2TB(est.)
Complete 3+4+5+6+7 man Nalimov Tablebase...200-600TB(est.)
Complete 3+4+5+6+7+8 man Nalimov Tablebase...40-180PB(est.)
...
Complete 3+4+5+[...]+30+31+32 man Nalimov Tablebase...????
Yes, the trend is toward big, ain't it?
REALLY big. I have always wondered whether it is possible
to get even the roughest of estimates of how big; it's
certainly past my skills to calculate or even estimate it.
Alas, it appears that, despite my limited abilities, most
people who do chess calculations are a lot worse than I am.
There are a lot of different answers published to the far
easier question of how long the longest possible game of
chess is. Here is, I believe, the correct number:
---------------------------------------------------------
LONGEST POSSIBLE CHESS GAME CALCULATION:
By Guy Macon <http://www.guymacon.com>
Here is my calculation for the longest possible chess
game under FIDE rules. You may find the rules here:
<http://www.fide.com/official/handbook.asp?level=EE101>
Start with 32 chesspieces.
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 99 plies to so that black can start
taking his turn 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 98 wasted plies between.
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 99 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 11799 plies.
Comments/corrections are welcome.
-Guy Macon <http://www.guymacon.com>
---------------------------------------------------------
.
|
|
| User: "Alun Harford" |
|
| Title: Re: Longest Possible Chess game |
25 May 2005 08:12:55 PM |
|
|
"Guy Macon" <http://www.guymacon.com/> wrote in message
news:1199560is22ctbc@corp.supernews.com...
LONGEST POSSIBLE CHESS GAME CALCULATION:
By Guy Macon <http://www.guymacon.com>
Here is my calculation for the longest possible chess
game under FIDE rules. You may find the rules here:
<http://www.fide.com/official/handbook.asp?level=EE101>
Start with 32 chesspieces.
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 99 plies to so that black can start
taking his turn making captures.
Assuming FIDE rules, that comes to a total of
(100*(30+96-8))-1)=11799 plies until the game is over.
Sorry, but you're completely wrong!
Refer to article 9 of the FIDE rules of chess. 9.3 describes the '50 move
rule':
" 9.3 The game is drawn, *****upon a correct claim***** by the player having
the move, if [...]"
Since neither player is required to claim the draw (and the same applies
with repeated positions), a game of chess is not limited to having a finite
number of moves. :-)
Alun Harford
--
Include the word 'lemongrass' in any email you send to me, or you'll hit my
spam filter. If you're reading archives, I may have changed this word -
check http://www.alunharford.co.uk/
.
|
|
|
|
| User: "" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 04:05:40 PM |
|
|
Guy Macon wrote:
(This came out of an ongoing discussion about whether
playing chess shows intelligence, with a comparison of
Nalimov Tablebase lookups and the Chinese Room thought
experiment.)
Note to the non-chess-player: a "ply" is a black move or
a white move. Cheesplayers call ten black 'moves' and ten
white 'moves' ten moves/twenty plies. "FIDE" is the
international chess federation. A "3 man Nalimov
Tablebase" is a database of every possible position that
3 chesspieces (king, king, pawn, king,king, rook, etc.)
can be in along with instructions on how to play perfectly
(shortest possible path to a win or longest possible path
to a draw/loss) for each position.
Mike Murray wrote:
Guy Macon <http://www.guymacon.com/> wrote:
Complete 3 man Nalimov Tablebase...80KB
Complete 3+4 man Nalimov Tablebase...30MB
Complete 3+4+5 man Nalimov Tablebase...7GB
Complete 3+4+5+6 man Nalimov Tablebase...1-2TB(est.)
Complete 3+4+5+6+7 man Nalimov Tablebase...200-600TB(est.)
Complete 3+4+5+6+7+8 man Nalimov Tablebase...40-180PB(est.)
...
Complete 3+4+5+[...]+30+31+32 man Nalimov Tablebase...????
Yes, the trend is toward big, ain't it?
REALLY big. I have always wondered whether it is possible
to get even the roughest of estimates of how big; it's
certainly past my skills to calculate or even estimate it.
We can at least put the following very rough upper bound on this
problem:
There are 32 pieces; 64 squares; so if all pieces are on the board, and
we uniquely identify each piece, there are C(64,32) possible board
positions. Then, since the 8 pawns for each side are indistingusihable,
and the pairs of bishops, knights, and rooks are indistinguishable, we
can divide out these possibilities to get
C(64,32)/((8!^2)*2^6)
for the number of distinct board positions where all 32 pieces are on
the board. Of course, this includes many illegal board configurations;
both bishops can be on the same color for example; but this is just the
rough upper bound.
If we assume that each successive calculation for 31 pieces, 30 pieces,
etc. is roughly the same order of magnitude, then an upper bound would
be
32*C(64,32)/((8!^2)*2^6) = C(64,32)/((8!)^2*2)
which is on the order of 10^44. Assuming that we encode the optimal
"next move" as 11 bits (5 bits to identify which piece is to be moved,
and 6 bits to indicate the space to which it is to be moved), then we
are at about order 10^45 bits of information.
Big? For back of the envelope estimation, at 10^23 atoms per 12 grams
of carbon, and assuming we can encode 1 bit per atom, we'd need around
10^20 kg of carbon to encode this information. Given that the earth's
mass is around 10^24 kg and has a radius of around 6000km, that gives
me a comparable-density sphere of solid carbon (very roughly) 200 km in
radius. Not exactly your table-top version of the game.
Reminds me of a short joke about the first "perfect" computer chess
machine; the first game it plays as black; white moves pawn to Q4,
computer calculates furiously, then responds "Black resigns". :-)
Cheers - Chas
<snip>
.
|
|
|
| User: "Guy Macon http://www.guymacon.com/" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 05:05:02 PM |
|
|
wrote:
Guy Macon <http://www.guymacon.com/> wrote:
Mike Murray wrote:
Guy Macon <http://www.guymacon.com/> wrote:
Complete 3 man Nalimov Tablebase...80KB
Complete 3+4 man Nalimov Tablebase...30MB
Complete 3+4+5 man Nalimov Tablebase...7GB
Complete 3+4+5+6 man Nalimov Tablebase...1-2TB(est.)
Complete 3+4+5+6+7 man Nalimov Tablebase...200-600TB(est.)
Complete 3+4+5+6+7+8 man Nalimov Tablebase...40-180PB(est.)
...
Complete 3+4+5+[...]+30+31+32 man Nalimov Tablebase...????
Yes, the trend is toward big, ain't it?
REALLY big. I have always wondered whether it is possible
to get even the roughest of estimates of how big; it's
certainly past my skills to calculate or even estimate it.
We can at least put the following very rough upper bound on this
problem:
There are 32 pieces; 64 squares; so if all pieces are on the
board, and we uniquely identify each piece, there are C(64,32)
possible board positions. Then, since the 8 pawns for each side
are indistinguishable, >and the pairs of bishops, knights, and
rooks are indistinguishable, we can divide out these possibilities
to get
C(64,32)/((8!^2)*2^6)
for the number of distinct board positions where all 32 pieces
are on the board. Of course, this includes many illegal board
configurations; both bishops can be on the same color for example;
but this is just the rough upper bound.
If we assume that each successive calculation for 31 pieces,
30 pieces, etc. is roughly the same order of magnitude, then
an upper bound would be
32*C(64,32)/((8!^2)*2^6) = C(64,32)/((8!)^2*2)
which is on the order of 10^44. Assuming that we encode the optimal
"next move" as 11 bits (5 bits to identify which piece is to be moved,
and 6 bits to indicate the space to which it is to be moved), then we
are at about order 10^45 bits of information.
Big? For back of the envelope estimation, at 10^23 atoms per 12 grams
of carbon, and assuming we can encode 1 bit per atom, we'd need around
10^20 kg of carbon to encode this information. Given that the earth's
mass is around 10^24 kg and has a radius of around 6000km, that gives
me a comparable-density sphere of solid carbon (very roughly) 200 km in
radius. Not exactly your table-top version of the game.
The tabletop version is made of neutronium. The handheld is a
black hole. <grin>
Reminds me of a short joke about the first "perfect" computer chess
machine; the first game it plays as black; white moves pawn to Q4,
computer calculates furiously, then responds "Black resigns". :-)
I don't think that the 8 pawns for each side are indistinguishable.
They could move to the last rank and promote to different pieces,
so you might have, say, 7 queens or 8 bishops on each side.
I think you also have to store not only the position, but whether
white/black can still castle (2 bits), how many plies into the 50
move rule you are (7 bits), whether each pawn has en passant ability
(8 bits).
So unless I am mistaken, the upper bound is somewhat higher.
It's an interesting math puzzle, isn't it?
I am trying to decide whether you have to store info about past
positions so as to avoid blundering into a repetition of position
draw while winning or to seek a repetition of position draw while
losing. Does the nature of following a list of perfect moves for
each position mean that you never end up in the same position twice?
I think it does. Then again, storing all past positions that have
actually been reached in the current game wouldn't take much space.
Or do you have to store all past positions for every position in
the tablebase? That would take a lot of space.
--
Guy Macon <http://www.guymacon.com/>
.
|
|
|
| User: "Simon Krahnke" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 01:16:49 PM |
|
|
* <Guy Macon <http://www.guymacon.com/>> (00:05) schrieb:
I think you also have to store not only the position, but whether
white/black can still castle (2 bits),
Why do I use 4 bits? Because there can be as much as 4 different
castlings?
how many plies into the 50 move rule you are (7 bits),
Who's to move?
whether each pawn has en passant ability (8 bits).
8bits? 1 to store if there is a chance, and 3 bits to specify in which
file.
So I count 16 additional bits. And with a minimal bitboard
representation I need 7*64=448 bits, a total of 464 bits.
mfg, simon .... l
.
|
|
|
| User: "Christian Bau" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 01:49:02 PM |
|
|
In article <87acmczii6.fsf@xts.gnuu.de>,
Simon Krahnke <overlord@gmx.li> wrote:
* <Guy Macon <http://www.guymacon.com/>> (00:05) schrieb:
I think you also have to store not only the position, but whether
white/black can still castle (2 bits),
Why do I use 4 bits? Because there can be as much as 4 different
castlings?
And when castling is possible, you don't need to record the position of
the king, and you don't need to record the position of one or both
rooks.
how many plies into the 50 move rule you are (7 bits),
Who's to move?
whether each pawn has en passant ability (8 bits).
8bits? 1 to store if there is a chance, and 3 bits to specify in which
file.
Again, you save recording the exact position of the pawn involved,
because it must be a white pawn in row four, black pawn in row five.
.
|
|
|
| User: "Simon Krahnke" |
|
| Title: Re: Longest Possible Chess game |
31 May 2005 12:55:47 AM |
|
|
* Christian Bau (20:49) wrote:
And when castling is possible, you don't need to record the position of
the king, and you don't need to record the position of one or both
rooks.
Yes, there is a lot room for optimizations. Using 448 bits for the piece
placement is quite a waste. An Array takes only 64*4=256 bits.
But for your optimization to work you need to record the positions by
piece. There are 32 pieces, that's 192 bits for their positions, 5 bits
to count them, and 16*3=48 bits to record promotions. 245 bits upper
bound.
Your optimization of course doesn't change the upper bound.
8bits? 1 to store if there is a chance, and 3 bits to specify in which
file.
Again, you save recording the exact position of the pawn involved,
because it must be a white pawn in row four, black pawn in row five.
Yes, and you record the destination square, because there is at most
one. That's why you need only 3 bits for the file.
If there is always a file, whose ep square cannot be a destination of a
pawn capture, so you could omit the flag.
mfg, simon .... l
.
|
|
|
| User: "Christian Bau" |
|
| Title: Re: Longest Possible Chess game |
31 May 2005 04:15:53 PM |
|
|
In article <87sm04x7ks.fsf@xts.gnuu.de>,
Simon Krahnke <overlord@gmx.li> wrote:
* Christian Bau (20:49) wrote:
And when castling is possible, you don't need to record the position of
the king, and you don't need to record the position of one or both
rooks.
Yes, there is a lot room for optimizations. Using 448 bits for the piece
placement is quite a waste. An Array takes only 64*4=256 bits.
But for your optimization to work you need to record the positions by
piece. There are 32 pieces, that's 192 bits for their positions, 5 bits
to count them, and 16*3=48 bits to record promotions. 245 bits upper
bound.
64 bits to record whether each square is occupied or not. At most 32
squares are occupied.
32 bits or less to record whether each occupied square is occupied by a
black or a white piece.
32 bits or less to record whether each occupied square is occupied by a
pawn or not. This would be the worst case if no square on the first and
last row is occupied; first and last row obviously are not pawns.
That leaves at most 24 pieces that are not pawns, and at most 16 of each
color. Two times four bits to specify which piece of each color is the
king. Then at most 22 times 2 bits to specify which figure.
Total so far: 64 + 32 + 32 + 2*4 + 22*2 = 180 bits.
Actually, the number of bits will always be lower, because some pieces
have to be taken to allow promotions. For example, with all 32 pieces on
the board, only sixteen are not pawns, saving 8*2 = 16 bits. Having
fewer than 32 pieces saves bits recording whether a square is covered by
a black/white pawn/not pawn.
.
|
|
|
| User: "Christian Bau" |
|
| Title: Re: Longest Possible Chess game |
31 May 2005 06:16:03 PM |
|
|
In article
<christian.bau-29F595.22155331052005@slb-newsm1.svr.pol.co.uk>,
Christian Bau <christian.bau@cbau.freeserve.co.uk> wrote:
In article <87sm04x7ks.fsf@xts.gnuu.de>,
Simon Krahnke <overlord@gmx.li> wrote:
* Christian Bau (20:49) wrote:
And when castling is possible, you don't need to record the position of
the king, and you don't need to record the position of one or both
rooks.
Yes, there is a lot room for optimizations. Using 448 bits for the piece
placement is quite a waste. An Array takes only 64*4=256 bits.
But for your optimization to work you need to record the positions by
piece. There are 32 pieces, that's 192 bits for their positions, 5 bits
to count them, and 16*3=48 bits to record promotions. 245 bits upper
bound.
A lower upper bound:
For each square in turn, use one bit to record whether the square is
occupied or not. At most 32 squares are occupied according to the rules.
For each occupied square in turn, use one bit to record whether it is
occupied by a black or white piece. For each occupied square in turn
except those in the first or last row, use one more bit to record
whether or not it is occupied by a pawn. There are at most 24 pieces
that are not pawns, and at most 16 of each color.
Both for white and black, use four bits each to record which one of the
at most 16 white or 16 black pieces that are not pawns is the king.
For each remaining piece in turn, use two bits to specify whether it is
queen, rook, knight or bishop.
Adding these bits, we get 64 bits, plus 2 bits per pawn, plus four bits
for each non-pawn including the kings, plus 2 x 2 bits for the kings.
That is 68 + 2 x pawns + 4 x others.
A file is "blocked" if it is occupied by a white pawn opposite a black
pawn. Initially, all files are blocked. A file can only be unblocked by
taking a piece. For each blocked file, there are two pawns that cannot
be promoted. Therefore:
pawns + others <= 24 + blocked
pawns >= 2 * blocked.
Initially, we have 2 * pawns + 4 * others = 96. After unblocking a file
at the cost of taking one piece, we can promote two pawns, effectively
losing two pawns and gaining one other piece. The upper limit for
2*pawns + 4*others stays the same at 96. So we need at most 68 + 96 =
164 bits to record the position of the pieces on the board.
We need one bit to record whether white or black is moving, and seven
bits to record how many plies since the last pawn was moved or a piece
was taken, that makes 172.
We can handle en passent without any further storage: The seven bit ply
count can handle numbers from 0 to 127, but we only need to store
numbers from 0 to 100. If we can take en passent, then the ply count
must be zero. Therefore, we use the numbers 120 to 127 to specify that
the pawn in one of eight files in the fourth row can be taken en
passent.
Castling is handled without need for further storage using the following
method: If e1 or e8 is not occupied, then castling is not possible. If
for example e1 is occupied, we use another bit to specify whether
castling is possible, and if it is possible, two more bits for castling
to the queen side and the king side. If castling is possible, we save
much more than the three bits lost by not recording any information that
we know, like king on e1, rook on a1 or h1. Also, if e1 or e8 are
occupied, then we have a field that is occupied but cannot be occupied
by a pawn, so we saved one bit there while recording which fields are
occupied by pawns.
Therefore we can completely record any chess position using at most 172
bits.
.
|
|
|
|
|
|
| User: "Simon Krahnke" |
|
| Title: Re: Longest Possible Chess game |
31 May 2005 02:33:51 AM |
|
|
* Christian Bau (20:49) wrote:
[ Supersede - error in computation ]
And when castling is possible, you don't need to record the position of
the king, and you don't need to record the position of one or both
rooks.
Yes, there is a lot room for optimizations. Using 448 bits for the piece
placement is quite a waste. An Array takes only 64*4=256 bits.
But for your optimization to work you need to record the positions by
piece. There are 32 pieces, that's 32*7=224 bits for their positions
(and existance), and 16*3=48 bits to record promotions. 272 bits. But
that's more than the 256 bits above.
And of course your optimization doesn't change the upper bound.
8bits? 1 to store if there is a chance, and 3 bits to specify in which
file.
Again, you save recording the exact position of the pawn involved,
because it must be a white pawn in row four, black pawn in row five.
Yes, and you record the destination square, because there is at most
one. That's why you need only 3 bits for the file.
If there is always a file, whose ep square cannot be a destination of a
pawn capture, so you could omit the flag.
mfg, simon .... l
.
|
|
|
| User: "David Richerby" |
|
| Title: Re: Longest Possible Chess game |
31 May 2005 04:33:08 AM |
|
|
Simon Krahnke <overlord@gmx.li> wrote:
Christian Bau (20:49) wrote:
And when castling is possible, you don't need to record the position of
the king, and you don't need to record the position of one or both
rooks.
Yes, there is a lot room for optimizations. Using 448 bits for the piece
placement is quite a waste. An Array takes only 64*4=256 bits.
Code an empty square with a one-bit zero and use five-bit codes starting
with ones for the pieces and you get down to 192 bits; less for a board
with fewer pieces. Arrange the code-words for the pieces carefully (four
bits allows sixteen different piece types but there are only 12) so that
you have a couple of three-bit codewords and you save another couple of
bits. More profitable would probably be to use the spare four codewords
to code runs of at least six adjacent blank squares.
Dave.
--
David Richerby Electronic Broken Hat (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a hat but it doesn't work and it
uses electricity!
.
|
|
|
|
|
|
| User: "Guy Macon http://www.guymacon.com/" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 05:59:00 PM |
|
|
Simon Krahnke wrote:
* <Guy Macon <http://www.guymacon.com/>> (00:05) schrieb:
I think you also have to store not only the position, but whether
white/black can still castle (2 bits),
Why do I use 4 bits? Because there can be as much as 4 different
castlings?
You are correct, of course. it's 4 bits, not 2.
how many plies into the 50 move rule you are (7 bits),
Who's to move?
Yup. Another bit needed.
whether each pawn has en passant ability (8 bits).
8bits? 1 to store if there is a chance, and 3 bits to specify in which
file.
Right again. That will teach me to post in haste. Thanks for the
corrections.
So I count 16 additional bits. And with a minimal bitboard
representation I need 7*64=448 bits, a total of 464 bits.
That looks right to me.
.
|
|
|
|
|
| User: "Deedlit" |
|
| Title: Re: Longest Possible Chess game |
03 Jun 2005 01:17:52 AM |
|
|
I don't think that the 8 pawns for each side are indistinguishable.
They could move to the last rank and promote to different pieces,
so you might have, say, 7 queens or 8 bishops on each side.
The point is that if you switch the pawns around, you don't get
different positions; that's what it means to be indistinguisable.
This allows you to divide by 8!.
.
|
|
|
|
| User: "David Richerby" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 02:31:58 PM |
|
|
Guy Macon <http://www.guymacon.com/> wrote:
I don't think that the 8 pawns for each side are indistinguishable.
They could move to the last rank and promote to different pieces,
so you might have, say, 7 queens or 8 bishops on each side.
They are indistinguishable because the game of chess doesn't change at all
if you write a number on each of the pawns -- nothing at all depends on
which file a particular pawn started on. Or, to put it another way, the
positions after
1.e4 Nf6 2.Qg4 Nxg4 3.d3 d6 4.Bg5 Nc6 5.Bf6 Nxf6 6.Nc3 Ng8 7.Nb1 Nb8
8.d4 e6
and
1.d4 Nf6 2.Bf4 Ng8 3.Bd6 exd6 4.e4 Nf6 5.Qg4 Ng8 6.Nc3 Nc6 7.Nb1 Nb8
8.Qe6+ dxe6
are absolutely identical, even though in the second case, Black's central
pawns have swapped places and in the first case they haven't.
Dave.
--
David Richerby Fluorescent Wine (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ vintage Beaujolais but it'll hurt
your eyes!
.
|
|
|
|
| User: "" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 04:35:47 AM |
|
|
Guy Macon wrote:
cbrown@cbrownsystems.com wrote:
Guy Macon <http://www.guymacon.com/> wrote:
Mike Murray wrote:
Guy Macon <http://www.guymacon.com/> wrote:
Complete 3 man Nalimov Tablebase...80KB
Complete 3+4 man Nalimov Tablebase...30MB
Complete 3+4+5 man Nalimov Tablebase...7GB
Complete 3+4+5+6 man Nalimov Tablebase...1-2TB(est.)
Complete 3+4+5+6+7 man Nalimov Tablebase...200-600TB(est.)
Complete 3+4+5+6+7+8 man Nalimov Tablebase...40-180PB(est.)
...
Complete 3+4+5+[...]+30+31+32 man Nalimov Tablebase...????
Yes, the trend is toward big, ain't it?
REALLY big. I have always wondered whether it is possible
to get even the roughest of estimates of how big; it's
certainly past my skills to calculate or even estimate it.
We can at least put the following very rough upper bound on this
problem:
There are 32 pieces; 64 squares; so if all pieces are on the
board, and we uniquely identify each piece, there are C(64,32)
possible board positions. Then, since the 8 pawns for each side
are indistinguishable, >and the pairs of bishops, knights, and
rooks are indistinguishable, we can divide out these possibilities
to get
C(64,32)/((8!^2)*2^6)
for the number of distinct board positions where all 32 pieces
are on the board. Of course, this includes many illegal board
configurations; both bishops can be on the same color for example;
but this is just the rough upper bound.
If we assume that each successive calculation for 31 pieces,
30 pieces, etc. is roughly the same order of magnitude, then
an upper bound would be
32*C(64,32)/((8!^2)*2^6) = C(64,32)/((8!)^2*2)
which is on the order of 10^44. Assuming that we encode the optimal
"next move" as 11 bits (5 bits to identify which piece is to be moved,
and 6 bits to indicate the space to which it is to be moved), then we
are at about order 10^45 bits of information.
Big? For back of the envelope estimation, at 10^23 atoms per 12 grams
of carbon, and assuming we can encode 1 bit per atom, we'd need around
10^20 kg of carbon to encode this information. Given that the earth's
mass is around 10^24 kg and has a radius of around 6000km, that gives
me a comparable-density sphere of solid carbon (very roughly) 200 km in
radius. Not exactly your table-top version of the game.
The tabletop version is made of neutronium. The handheld is a
black hole. <grin>
Before I address some of your complications below, here's a much better
estimate, at least for the case of "32 pieces on the board".
Since all pieces are on the board, no captures have occured; in
particular, no pawn has performed a capture. Therefore, all pawns are
on their original columns.
In that case, each pair of opposing pawns cannot pass each other; and
for each of the 8 pairs of pawns, there are 5+4+3+2+1= 15 possible
relative positions.
If we assume that the remianing 16 pieces are then ditributed amongst
the unoccupied 48 spaces, and again dividing for pairs of rooks,
knights, and bishops, we get (using C. Heckman's notation):
(15^8)*P(48,16)/2^6
which is "only" about 10^35 positions. So by the above logic, with
roughly 10 bits per entry, we get a sphere of solid carbon only a mere
/20 meters/ in radius - of course, this only counts the first "layer"
of moves, before any captures. Now /that/ you can hide in your pocket -
assuming you have really, really droopy pants.
On the other hand, if say, the eight white pawns have managed to get
promoted without any loss of black pawns (I think this is at least
possible), then for each possible legal combinations of R's,B's, N's
and Q's, to have something like
6^8*P(48, 24)/(something not particularly huge)
which would total on the order of 10^37 - 10^40
which would take a sphere 1500 km in radius.
I'll hold off on the full analysis of all piece allocations for now;
but a 1500 km sphere is a lot more feasible than a solid sphere 120
lights across!
Reminds me of a short joke about the first "perfect" computer chess
machine; the first game it plays as black; white moves pawn to Q4,
computer calculates furiously, then responds "Black resigns". :-)
I don't think that the 8 pawns for each side are indistinguishable.
They could move to the last rank and promote to different pieces,
so you might have, say, 7 queens or 8 bishops on each side.
That's only possible if pieces have been taken (because the opposing
pawns must "doesy-doe" in some fashion).
If all pawns have been promoted then we have at most 24 pieces on the
board.
I think you also have to store not only the position, but whether
white/black can still castle (2 bits), how many plies into the 50
move rule you are (7 bits), whether each pawn has en passant ability
(8 bits).
That only triples the amount of information we need to store - right
now, I think we're still in the land of "pi is approximately 1". :-)
So unless I am mistaken, the upper bound is somewhat higher.
It's an interesting math puzzle, isn't it?
I am trying to decide whether you have to store info about past
positions so as to avoid blundering into a repetition of position
draw while winning or to seek a repetition of position draw while
losing.
My first thought is to wonder why it wouldn't be sufficient to have a
single bit - set if this is the fiftieth move with no captures, clear
otherwise.
Does the nature of following a list of perfect moves for
each position mean that you never end up in the same position twice?
I think it does. Then again, storing all past positions that have
actually been reached in the current game wouldn't take much space.
Or do you have to store all past positions for every position in
the tablebase? That would take a lot of space.
I you are right that the longest game is under 10000 moves, then at
this level of estimation, it's not that much space.
Cheers - Chas
--
Guy Macon <http://www.guymacon.com/>
.
|
|
|
| User: "Guy Macon http://www.guymacon.com/" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 05:51:14 PM |
|
|
wrote:
Since all pieces are on the board, no captures have occured; in
particular, no pawn has performed a capture. Therefore, all pawns are
on their original columns.
In that case, each pair of opposing pawns cannot pass each other; and
for each of the 8 pairs of pawns, there are 5+4+3+2+1= 15 possible
relative positions.
Yes, but (given our assumption that both players avoid allowing
the other to claim a 100-ply draw) every 100 plies someone has
to make a pawn move or a capture. Since you have to make a series
of captures anyway, you can use 8 of them in such a way that all
the pawns pass each other.
On the other hand, if say, the eight white pawns have managed to get
promoted without any loss of black pawns (I think this is at least
possible),
It is. I did it in the example game that started this thread.
If all pawns have been promoted then we have at most 24 pieces on the
board.
Excellent point. I hadn't figured that in to my calculation, and it
is clearly correct. You have to lose 8 pieces to get the pawns past
each other. That puts the "combination explosion" that comes with
each pawn having one of four peices to promote to later in the game
where it has a smaller effect.
My first thought is to wonder why it wouldn't be sufficient to have a
single bit - set if this is the fiftieth move with no captures, clear
otherwise.
You can have two otherwise identical positions, one with 3 plies
since the last capture and the other with 47 plies since the last
capture, that have different best moves in order to avoid being
forced to choose between a losing position and a draw while ahead.
You need to count how many plies you are into the 100-ply rule.
.
|
|
|
|
|
|
| User: "Proginoskes" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 07:43:54 PM |
|
|
wrote:
[...]
We can at least put the following very rough upper bound
on this problem:
There are 32 pieces; 64 squares; so if all pieces are on
the board, and we uniquely identify each piece, there are
C(64,32) possible board positions. Then, since the 8 pawns
for each side are indistingusihable, and the pairs of
bishops, knights, and rooks are indistinguishable, we can
divide out these possibilities to get
C(64,32)/((8!^2)*2^6)
for the number of distinct board positions where all 32
pieces are on the board. Of course, this includes many
illegal board configurations; both bishops can be on the
same color for example; but this is just the rough upper
bound.
No it isn't; you're off by 32!.
When you're choosing the squares for the pieces, you're choosing
squares for the black king and white king (for instance). The order in
which you choose these squares IS important, because choosing them the
other way around results in a different position. The rest of your
analysis is right, so you get an answer of
P(64,32)/((8!^2)*2^6).
If we assume that each successive calculation for 31 pieces,
30 pieces, etc. is roughly the same order of magnitude, then
an upper bound would be
32*C(64,32)/((8!^2)*2^6) = C(64,32)/((8!)^2*2)
Once the above mistake is fixed, this becomes
P(64,32)/((8!)^2*2^2).
which is on the order of 10^44.
10^79.
Assuming that we encode the optimal "next move" as 11 bits
(5 bits to identify which piece is to be moved, and 6 bits
to indicate the space to which it is to be moved), then we
are at about order 10^45 bits of information.
10^80
Big? For back of the envelope estimation, at 10^23 atoms
per 12 grams of carbon, and assuming we can encode 1 bit
per atom, we'd need around 10^20 kg of carbon
10^55 kg of carbon
to encode this information. Given that the earth's mass
is around 10^24 kg and has a radius of around 6000km,
that gives me a comparable-density sphere of solid carbon
(very roughly) 200 km in radius.
6 * 10^14 km (600 trillion km).
Not exactly your table-top version of the game.
Re-doing the calculation and reflecting on THAT answer reminds me of a
saying: "Theoretical comptuer scientists never work with anything that
can fit on one planet."
Reminds me of a short joke about the first "perfect"
computer chess machine; the first game it plays as
black; white moves pawn to Q4, computer calculates
furiously, then responds "Black resigns". :-)
"Oh poo, you win AGAIN!" -- Fatbot, "Mars University", Futurama.
(Actually, the other robot announces "Mate in 143 moves" right before
this.)
--- Christopher Heckman
.
|
|
|
| User: "Deedlit" |
|
| Title: Re: Longest Possible Chess game |
03 Jun 2005 01:15:27 AM |
|
|
32*C(64,32)/((8!^2)*2^6) = C(64,32)/((8!)^2*2)
Once the above mistake is fixed, this becomes
P(64,32)/((8!)^2*2^2).
which is on the order of 10^44.
10^79.
Actually, cbr made a mistake in his computation; his original number
is about 17.6 million. After multiplying by 32!, you get about 4.63 *
10^42. This is not an upper bound for the number of chess positions,
though; it doesn't include positions with promoted pawns.
.
|
|
|
|
| User: "" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 10:27:47 PM |
|
|
Proginoskes wrote:
cbrown@cbrownsystems.com wrote:
[...]
We can at least put the following very rough upper bound
on this problem:
There are 32 pieces; 64 squares; so if all pieces are on
the board, and we uniquely identify each piece, there are
C(64,32) possible board positions. Then, since the 8 pawns
for each side are indistingusihable, and the pairs of
bishops, knights, and rooks are indistinguishable, we can
divide out these possibilities to get
C(64,32)/((8!^2)*2^6)
for the number of distinct board positions where all 32
pieces are on the board. Of course, this includes many
illegal board configurations; both bishops can be on the
same color for example; but this is just the rough upper
bound.
No it isn't; you're off by 32!.
You're absolutely right; I noticed this while I was thinking about
Guy's comments... doh!
When you're choosing the squares for the pieces, you're choosing
squares for the black king and white king (for instance). The order in
which you choose these squares IS important, because choosing them the
other way around results in a different position. The rest of your
analysis is right, so you get an answer of
P(64,32)/((8!^2)*2^6).
If we assume that each successive calculation for 31 pieces,
30 pieces, etc. is roughly the same order of magnitude, then
an upper bound would be
32*C(64,32)/((8!^2)*2^6) = C(64,32)/((8!)^2*2)
Once the above mistake is fixed, this becomes
P(64,32)/((8!)^2*2^2).
which is on the order of 10^44.
10^79.
Bah - you're quibbling about a mere 35 orders of magnitude? :-)
Assuming that we encode the optimal "next move" as 11 bits
(5 bits to identify which piece is to be moved, and 6 bits
to indicate the space to which it is to be moved), then we
are at about order 10^45 bits of information.
10^80
Big? For back of the envelope estimation, at 10^23 atoms
per 12 grams of carbon, and assuming we can encode 1 bit
per atom, we'd need around 10^20 kg of carbon
10^55 kg of carbon
to encode this information. Given that the earth's mass
is around 10^24 kg and has a radius of around 6000km,
that gives me a comparable-density sphere of solid carbon
(very roughly) 200 km in radius.
6 * 10^14 km (600 trillion km).
.... or about 120 light years for a clock signal to propagate across the
whole sphere? Those are going to be /long/ games, unless we switch to
something like neutronium...
Not exactly your table-top version of the game.
Re-doing the calculation and reflecting on THAT answer reminds me of a
saying: "Theoretical comptuer scientists never work with anything that
can fit on one planet."
Reminds me of a short joke about the first "perfect"
computer chess machine; the first game it plays as
black; white moves pawn to Q4, computer calculates
furiously, then responds "Black resigns". :-)
"Oh poo, you win AGAIN!" -- Fatbot, "Mars University", Futurama.
(Actually, the other robot announces "Mate in 143 moves" right before
this.)
--- Christopher Heckman
Cheers - Chas
.
|
|
|
|
| User: "Proginoskes" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 07:57:16 PM |
|
|
Proginoskes wrote:
cbrown@cbrownsystems.com wrote:
[...]
We can at least put the following very rough upper bound
on this problem:
There are 32 pieces; 64 squares; so if all pieces are on
the board, and we uniquely identify each piece, there are
C(64,32) possible board positions. Then, since the 8 pawns
for each side are indistingusihable, and the pairs of
bishops, knights, and rooks are indistinguishable, we can
divide out these possibilities to get
C(64,32)/((8!^2)*2^6)
for the number of distinct board positions where all 32
pieces are on the board. Of course, this includes many
illegal board configurations; both bishops can be on the
same color for example; but this is just the rough upper
bound.
No it isn't; you're off by 32!.
When you're choosing the squares for the pieces, you're
choosing squares for the black king and white king (for
instance). The order in which you choose these squares
IS important, because choosing them the other way around
results in a different position. The rest of your analysis
is right, so you get an answer of
P(64,32)/((8!^2)*2^6).
If we assume that each successive calculation for 31 pieces,
30 pieces, etc. is roughly the same order of magnitude, then
an upper bound would be
32*C(64,32)/((8!^2)*2^6) = C(64,32)/((8!)^2*2)
Once the above mistake is fixed, this becomes
P(64,32)/((8!)^2*2^2).
which is on the order of 10^44.
10^79.
Assuming that we encode the optimal "next move" as 11 bits
(5 bits to identify which piece is to be moved, and 6 bits
to indicate the space to which it is to be moved), then we
are at about order 10^45 bits of information.
10^80
Big? For back of the envelope estimation, at 10^23 atoms
per 12 grams of carbon, and assuming we can encode 1 bit
per atom, we'd need around 10^20 kg of carbon
10^55 kg of carbon
to encode this information. Given that the earth's mass
is around 10^24 kg and has a radius of around 6000km,
that gives me a comparable-density sphere of solid carbon
(very roughly) 200 km in radius.
6 * 10^14 km (600 trillion km).
Nonono. 1.292 * 10^14, a mere 129 trillion km.
Not exactly your table-top version of the game.
Re-doing the calculation and reflecting on THAT answer
reminds me of a saying: "Theoretical comptuer scientists
never work with anything that can fit on one planet."
Reminds me of a short joke about the first "perfect"
computer chess machine; the first game it plays as
black; white moves pawn to Q4, computer calculates
furiously, then responds "Black resigns". :-)
"Oh poo, you win AGAIN!" -- Fatbot, "Mars University",
Futurama.
(Actually, the other robot announces "Mate in 143 moves"
right before this.)
--- Christopher Heckman
.
|
|
|
|
|
| User: "N. Silver" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 04:28:11 PM |
|
|
Charles. Brown wrote:
Reminds me of a short joke about the first
"perfect" computer chess machine; the first
game it plays as black; white moves pawn
to Q4, computer calculates furiously, then
responds "Black resigns". :-)
Right. With best play, there are only 2 possibilities.
Either white has a forced win or the game is a draw.
.
|
|
|
| User: "Guy Macon http://www.guymacon.com/" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 05:38:56 PM |
|
|
N. Silver wrote:
Charles. Brown wrote:
Reminds me of a short joke about the first
"perfect" computer chess machine; the first
game it plays as black; white moves pawn
to Q4, computer calculates furiously, then
responds "Black resigns". :-)
Right. With best play, there are only 2 possibilities.
Either white has a forced win or the game is a draw.
I believe that you are incorrect. There are various games that
have the attribute that if the second to play has a forced win
then the first to play can get into that forced win position
first, but Chess is not one of those games. It could be a win
for black. Not likely, but certainly possible.
.
|
|
|
| User: "N. Silver" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 05:50:30 PM |
|
|
Guy Macon wrote:
Right. With best play, there are only 2 possibilities.
Either white has a forced win or the game is a draw.
I believe that you are incorrect. There are various games that
have the attribute that if the second to play has a forced win
then the first to play can get into that forced win position
first, but Chess is not one of those games. It could be a win
for black. Not likely, but certainly possible.
If black has a forced win, white's first move can be one of
the four knight moves that allow white to mimic black's
winning sequence.
.
|
|
|
| User: "N. Silver" |
|
| Title: Re: Longest Possible Chess game |
29 May 2005 05:55:04 PM |
|
|
Guy Macon wrote:
Right. With best play, there are only 2 possibilities.
Either white has a forced win or the game is a draw.
I believe that you are incorrect. There are various games that
have the attribute that if the second to play has a forced win
then the first to play can get into that forced win position
first, but Chess is not one of those games. It could be a win
for black. Not likely, but certainly possible.
If black has a forced win, white's first move can be one of
the four knight moves or one of the 16 pawn moves that allow
white to mirror black's winning sequence.
.
|
|
|
| User: "David Richerby" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 02:06:41 PM |
|
|
N. Silver <mathelp@worldnet.att.net> wrote:
If black has a forced win, white's first move can be one of
the four knight moves or one of the 16 pawn moves that allow
white to mirror black's winning sequence.
If Black has a forced win, Black can still win whatever first move White
makes. Strategy-stealing arguments don't apply to chess because, whenever
White tries to waste a move, Black can waste a move back.
Dave.
--
David Richerby Psychotic Surprise Soap (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a personal hygiene product but
not like you'd expect and it wants to
kill you!
.
|
|
|
|
| User: "Timothy Little" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 03:36:01 AM |
|
|
N. Silver wrote:
If black has a forced win, white's first move can be one of the four
knight moves or one of the 16 pawn moves that allow white to mirror
black's winning sequence.
I'm not sure what you mean here: white has 20 possible first moves.
Is there a known reason why black can't force a win in every case?
It is easy to construct a simplified symmetric chess board for which
the second player can always force a win. How do you know that the
standard starting position doesn't fall into that category?
- Tim
.
|
|
|
| User: "N. Silver" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 10:28:41 AM |
|
|
Timothy Little wrote:
N. Silver wrote:
If black has a forced win, white's first move
can be one of the four knight moves or one
of the 16 pawn moves that allow white to
mirror black's winning sequence.
I'm not sure what you mean here: white has 20
possible first moves. Is there a known reason
why black can't force a win in every case?
I do not have a proof. The problem is:
Given that black can force a win, show that
white can force a draw. We can call upon
all sequences of wins for black in a proof.
We know there are aggressive and passive
opening moves. We select a passive move that
is not one of black's many possible best second
moves, then mirror best play by black the rest
of the way, in concert with the winning ideas
in black's strategy.
There is a duplication problem, but for white
the key to a drawing strategy, is to lose a
tempo, which is not difficult.
It is easy to construct a simplified symmetric
chess board for which the second player can
always force a win. How do you know that the
standard starting position doesn't fall into that
category?
Because in these scenarios, white is in zugzwang,
something that never happens at the beggining of
a game on a full-sized board.
.
|
|
|
| User: "Guy Macon http://www.guymacon.com/" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 05:54:18 PM |
|
|
N. Silver wrote:
Because in these scenarios, white is in zugzwang,
something that never happens at the beggining of
a game on a full-sized board.
You don't know whether the above is true or false.
You cannot detect zugzwang without knowing a sequence
that leads to certain victory.
It's very, very, likely to be true, but maybe it isn't.
.
|
|
|
|
| User: "N. Silver" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 10:30:36 AM |
|
|
Timothy Little wrote:
N. Silver wrote:
If black has a forced win, white's first move
can be one of the four knight moves or one
of the 16 pawn moves that allow white to
mirror black's winning sequence.
I'm not sure what you mean here: white has 20
possible first moves. Is there a known reason
why black can't force a win in every case?
I do not have a proof. The problem is:
Given that black can force a win, show that
white can force a draw. We can call upon
all sequences of wins for black in a proof.
We know there are aggressive and passive
opening moves. We select a passive move that
is not one of black's many possible best second
moves, then mirror best play by black the rest
of the way, in concert with the winning ideas
in black's strategy.
There is a duplication problem, but for white
the key to a drawing strategy, is to lose a
tempo, which is not difficult.
It is easy to construct a simplified symmetric
chess board for which the second player can
always force a win. How do you know that the
standard starting position doesn't fall into that
category?
Because in these scenarios, white is in zugzwang,
something that never happens at the beginning of
a game on a full-sized board.
.
|
|
|
| User: "David Richerby" |
|
| Title: Re: Longest Possible Chess game |
30 May 2005 02:17:40 PM |
|
|
N. Silver <mathelp@worldnet.att.net> wrote:
I do not have a proof. The problem is: Given that black can force a win,
show that white can force a draw. We can call upon all sequences of wins
for black in a proof. We know there are aggressive and passive opening
moves. We select a passive move that is not one of black's many possible
best second moves, then mirror best play by black the rest of the way,
in concert with the winning ideas in black's strategy.
That doesn't work at all.
On the theoretical level, Black's winning strategy is a winning strategy
precisely because it defeats *all* first moves by White, so your
assumption that White can play a quiet move and then strategy steal
already contradicts your assumption that Black's strategy is winning.
On the practical level, White might not be able to give up the tempo in
the way you describe. It's possible that all Black's winning lines
involve playing ...a6 at some point. If White has already pushed his
a-pawn (it looked like it was almost passing when played as the first
move!), he can't mimic that move.
There is a duplication problem, but for white the key to a drawing
strategy, is to lose a tempo, which is not difficult.
Actually, I think it is difficult. White can't lose a tempo without
altering the position and it's very hard to prove that this alteration is
not significant.
Because in these scenarios, white is in zugzwang, something that never
happens at the beginning of a game on a full-sized board.
That White is not in zugzwang in the initial position of chess is
precisely what you're trying to prove!
Dave.
--
David Richerby Frozen Poetic Tree (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ tree but it's in verse and frozen in
a block of ice!
.
|
|
|
| User: "Simon Krahnke" |
|
| Title: Re: Longest Possible Chess game |
31 May 2005 02:09:39 AM |
|
|
* David Richerby <davidr@chiark.greenend.org.uk> (21:17) schrieb:
N. Silver <mathelp@worldnet.att.net> wrote:
I do not have a proof. The problem is: Given that black can force a win,
show that white can force a draw. We can call upon all sequences of wins
for black in a proof. We know there are aggressive and passive opening
moves. We select a passive move that is not one of black's many possible
best second moves, then mirror best play by black the rest of the way,
in concert with the winning ideas in black's strategy.
That doesn't work at all.
On the theoretical level, Black's winning strategy is a winning strategy
precisely because it defeats *all* first moves by White, so your
assumption that White can play a quiet move and then strategy steal
already contradicts your assumption that Black's strategy is winning.
I think what Mr Silver was trying is a proof by contradiction: If there
was a forced win by black there would be a forces for white, so there
can't be a forced win by black.
On the practical level, White might not be able to give up the tempo in
the way you describe. It's possible that all Black's winning lines
involve playing ...a6 at some point. If White has already pushed his
a-pawn (it looked like it was almost passing when played as the first
move!), he can't mimic that move.
But that doesn't matter, if there is no a3 in black's optimal tree.
So the trick must of course be playing a move, that's completely
irrelevant to blacks optimal strategy.
There is a duplication problem, but for white the key to a drawing
strategy, is to lose a tempo, which is not difficult.
Actually, I think it is difficult. White can't lose a tempo without
altering the position and it's very hard to prove that this alteration is
not significant.
Exactly.
Because in these scenarios, white is in zugzwang, something that never
happens at the beginning of a game on a full-sized board.
That White is not in zugzwang in the initial position of chess is
precisely what you're trying to prove!
Is there any precise definition of »zugzwang«?
mfg, simon .... l
.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Related Articles |
|
|
