Sign in with
Sign up | Sign in
Your question

Longest Possible Chess game

Tags:
  • PC gaming
  • Games
  • SCI
  • King
  • Video Games
Last response: in Video Games
Share
Anonymous
May 25, 2005 7:01:30 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

(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/&gt; 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&gt;

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&g...;

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&gt;

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

More about : longest chess game

Anonymous
May 25, 2005 7:01:31 PM

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

On Wed, 25 May 2005 15:01:30 +0000, Guy Macon
<http://www.guymacon.com/&gt; wrote:

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

That looks about right. Keep in mind, though, that someone has to
claim a draw by the 50 move rule, it isn't automatic. Play continues
if no one claims a draw.

---
Replace you know what by j to email
Anonymous
May 25, 2005 7:01:31 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Guy Macon wrote:
> [...]
> 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:
> [...] 11799 plies.

.... or 5850 moves. The number usually given is 6530. (Chernev, Curious
Chess Facts, The Black Knight Press, 1937.) A couple of mathematicians
published a paper called "The Longest Game", but I can't remember who
it was, or what the number was, and my printed-out copy of the article
is in Arizona. If you have access to MathSciNet (most universities do),
go to http://ams.rice.edu/mathscinet/search/ and search for the paper
with that title.

The length depends strongly on the rules which determine when a game is
drawn. The longest game by two grandmasters is around 269 moves.

--- Christopher Heckman
Related resources
Can't find your answer ? Ask !
Anonymous
May 25, 2005 9:03:31 PM

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

On 25 May 2005 13:26:29 -0700, "Proginoskes"
<proginoskes@email.msn.com> wrote:

>
>
>Guy Macon wrote:
>> [...]
>> 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:
>> [...] 11799 plies.
>
>... or 5850 moves. The number usually given is 6530.

I've found references to 5949 moves:
http://www.chess-poster.com/english/notes_and_facts/did...
http://myweb.cableone.net/theyowans/chess_training.htm
http://gameknot.com/stats.pl?zargoth123

---
Replace you know what by j to email
Anonymous
May 25, 2005 9:12:52 PM

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

Note that the game doesn't end just by virtue of there being 100 consecutive half-moves without a pawn move or capture; the rule is just that at that point a player is allowed to claim a draw if he wishes. The players can continue to push pieces for as long as they like.
Anonymous
May 26, 2005 1:14:16 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

"Proginoskes" <proginoskes@email.msn.com> wrote in message
news:1117052789.143022.307790@g14g2000cwa.googlegroups.com...
>
>
> Guy Macon wrote:
> > [...]
> > 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:
> > [...] 11799 plies.
>
> ... or 5850 moves. The number usually given is 6530. (Chernev, Curious
> Chess Facts, The Black Knight Press, 1937.) A couple of mathematicians
> published a paper called "The Longest Game", but I can't remember who
> it was, or what the number was, and my printed-out copy of the article
> is in Arizona. If you have access to MathSciNet (most universities do),
> go to http://ams.rice.edu/mathscinet/search/ and search for the paper
> with that title.
>
> The length depends strongly on the rules which determine when a game is
> drawn. The longest game by two grandmasters is around 269 moves.
>
> --- Christopher Heckman

# What are the fewest moves to win a game?
Anonymous
May 26, 2005 1:14:17 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Don H wrote:
>
>
> # What are the fewest moves to win a game?
>

Fool's mate, I think.

Bob Kolker

>
Anonymous
May 26, 2005 1:37:53 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

"Proginoskes" <proginoskes@email.msn.com> writes in article <1117052789.143022.307790@g14g2000cwa.googlegroups.com> dated 25 May 2005 13:26:29 -0700:
>The length depends strongly on the rules which determine when a game is
>drawn. The longest game by two grandmasters is around 269 moves.

Actually, both the 50-move and 3-repeat rules have loopholes. One player
must "claim" the draw; otherwise the game continues. So the length is
unbounded.

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
Anonymous
May 26, 2005 1:40:21 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Proginoskes wrote:

>Guy Macon wrote:
>
>> 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:
>> [...] 11799 plies.
>
>... or 5850 moves. The number usually given is 6530. (Chernev, Curious
>Chess Facts, The Black Knight Press, 1937.)

Not being one of those kooks who think that They Alone Know The Truth
and the All Experts Are Wrong, it bothers me that my calculations came
up with a different answer than other folks got, but I have never seen
any of them say how they made the calculation.

> A couple of mathematicians
>published a paper called "The Longest Game", but I can't remember who
>it was, or what the number was, and my printed-out copy of the article
>is in Arizona. If you have access to MathSciNet (most universities do),
>go to http://ams.rice.edu/mathscinet/search/ and search for the paper
>with that title.

Available by subscription only. :( 

I did a web search and found the title _The longest chess game:
Discovery of chess endgames that require 221 moves to capture a
piece and subsequently win_ by by Lewis Stiller (PhD thesis).
Is that it?

>The length depends strongly on the rules which determine when a game is
>drawn. The longest game by two grandmasters is around 269 moves.

I tried to calculate it with USCF (USA Chess federation) rules rather
than FIDE (International Chess Federation) rules, and concluded that
the USCF rules were ambiguous enough that I couldn't do the math.

Jud McCranie wrote:

>That looks about right. Keep in mind, though, that someone has to
>claim a draw by the 50 move rule, it isn't automatic. Play continues
>if no one claims a draw.

Excellent point. I will add the assumption that one or the other
player claims the draw, otherwise they can go on for a very long
time. Otherwise the player can just move the same piece back and
forth forever, never claiming the repetition of position draw or
the 50 move draw.

--
Guy Macon <http://www.guymacon.com/&gt;
Anonymous
May 26, 2005 1:40:22 AM

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

On Wed, 25 May 2005 21:40:21 +0000, Guy Macon
<http://www.guymacon.com/&gt; wrote:

>I did a web search and found the title _The longest chess game:
>Discovery of chess endgames that require 221 moves to capture a
>piece and subsequently win_ by by Lewis Stiller (PhD thesis).
>Is that it?

No, that's for a particular type of endgame, rook and bishop versus
two knights.

---
Replace you know what by j to email
Anonymous
May 26, 2005 1:40:23 AM

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

>>I did a web search and found the title _The longest chess game:
>>Discovery of chess endgames that require 221 moves to capture a
>>piece and subsequently win_ by by Lewis Stiller (PhD thesis).
>>Is that it?
>
>No, that's for a particular type of endgame, rook and bishop versus
>two knights.

And, BTW, that is ignoring the 50-move rule. So it is for puzzles.

---
Replace you know what by j to email
Anonymous
May 26, 2005 1:44:15 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

"Don H" <donlhumphries@bigpond.com> writes in article <IU5le.991$BR4.227@news-server.bigpond.net.au> dated Wed, 25 May 2005 21:14:16 GMT:
># What are the fewest moves to win a game?

Again, there's a loophole in the rules. Either player may resign on his
move, so white can resign after 0 plies.

I think the shortest route to checkmate is 4 plies, with black checkmating
on his second move.

1. f3 e6
2. g4 Qh4++

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
Anonymous
May 26, 2005 3:32:43 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Don H wrote:
>
> # What are the fewest moves to win a game?

Apart from things like 1. e4 resign the shortest mate is

1. g4 e5 2. f4 Qh4 mate.

Claus-Juergen
Anonymous
May 26, 2005 3:32:44 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Content-Transfer-Encoding: 8Bit


Claus-Jürgen Heigl wrote:
>
>Don H wrote:
>>
>> # What are the fewest moves to win a game?
>
>Apart from things like 1. e4 resign the shortest mate is
>
>1. g4 e5 2. f4 Qh4 mate.
>
>Claus-Juergen

What are the fewest moves to win a game of Go?
Anonymous
May 26, 2005 6:12:55 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

"Guy Macon" <http://www.guymacon.com/&gt; wrote in message
news:1199560is22ctbc@corp.supernews.com...
> LONGEST POSSIBLE CHESS GAME CALCULATION:
> By Guy Macon <http://www.guymacon.com&gt;
>
> 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&g...;
>
> 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/
Anonymous
May 26, 2005 6:16:28 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

"Guy Macon" <http://www.guymacon.com/&gt; wrote in message
news:1199vepntknapc9@corp.supernews.com...
>
> Content-Transfer-Encoding: 8Bit
>
>
> Claus-Jürgen Heigl wrote:
> >
> >Don H wrote:
> >>
> >> # What are the fewest moves to win a game?
> >
> >Apart from things like 1. e4 resign the shortest mate is
> >
> >1. g4 e5 2. f4 Qh4 mate.
> >
> >Claus-Juergen
>
> What are the fewest moves to win a game of Go?


1. pass pass

white wins because of komi

--
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/
Anonymous
May 26, 2005 12:28:15 PM

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

On Wed, 25 May 2005, [ISO-8859-1] Claus-Jürgen Heigl wrote:

> Don H wrote:
> > # What are the fewest moves to win a game?
>
> Apart from things like 1. e4 resign the shortest mate is
>
> 1. g4 e5 2. f4 Qh4 mate.

[1. White resigns] would be possible, but bizarre. However, [1. White
loses on time] happens when White doesn't make it to the board.

--
Timo Nieminen - Home page: http://www.physics.uq.edu.au/people/nieminen/
Shrine to Spirits: http://www.users.bigpond.com/timo_nieminen/spirits.html
Anonymous
May 26, 2005 12:54:59 PM

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

In article <1117052789.143022.307790@g14g2000cwa.googlegroups.com>,
"Proginoskes" <proginoskes@email.msn.com> wrote:

> Guy Macon wrote:
> > [...]
> > 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:
> > [...] 11799 plies.
>
> ... or 5850 moves. The number usually given is 6530. (Chernev, Curious
> Chess Facts, The Black Knight Press, 1937.) A couple of mathematicians
> published a paper called "The Longest Game", but I can't remember who
> it was, or what the number was, and my printed-out copy of the article
> is in Arizona. If you have access to MathSciNet (most universities do),
> go to http://ams.rice.edu/mathscinet/search/ and search for the paper
> with that title.

No papers found with longest game in the title.

No papers found with longest & game & chess anywhere.

About 40 papers with longest & game somewhere in title or review,
but just looking at the titles I don't think they're about chess.

There are 294 reviews that mention chess but I'm not going to look
through them all to see if I can find what you think you've seen.

--
Gerry Myerson (gerry@maths.mq.edi.ai) (i -> u for email)
Anonymous
May 26, 2005 5:34:05 PM

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

Gerry Myerson wrote:
> In article <1117052789.143022.307790@g14g2000cwa.googlegroups.com>,
> "Proginoskes" <proginoskes@email.msn.com> wrote:
>
> > Guy Macon wrote:
> > > [...]
> > > 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:
> > > [...] 11799 plies.
> >
> > ... or 5850 moves. The number usually given is 6530.
> > (Chernev, Curious Chess Facts, The Black Knight Press,
> > 1937.) A couple of mathematicians published a paper
> > called "The Longest Game", but I can't remember who
> > it was, or what the number was, and my printed-out
> > copy of the article is in Arizona. If you have access
> > to MathSciNet (most universities do), go to
> > http://ams.rice.edu/mathscinet/search/ and search for
> > the paper with that title.
>
> No papers found with longest game in the title.
>
> No papers found with longest & game & chess anywhere.
>
> About 40 papers with longest & game somewhere in title
> or review, but just looking at the titles I don't think
> they're about chess.
>
> There are 294 reviews that mention chess but I'm not
> going to look through them all to see if I can find what
> you think you've seen.

It may have been in a journal like the Journal of Recreational
Mathematics, which isn't indexed at MathSciNet. I ran across the
article by accident, checking some references at MathWorld. (Why
couldn't this thread have come up 2 weeks earlier !?!??!) It's probably
within the last 25 years, so a glance at the table of contents should
be sufficient. Otherwise, I'll have to respond in a few months, when I
get back home ...

--- Christopher Heckman
Anonymous
May 26, 2005 7:49:44 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Don H wrote:
> "Claus-Jürgen Heigl" <unea@rz.uni-karlsruhe.de> wrote in message
> news:D 72qpj$fft$1@news2.rz.uni-karlsruhe.de...
> > Don H wrote:
> > >
> > > # What are the fewest moves to win a game?
> >
> > Apart from things like 1. e4 resign the shortest
> > mate is
> >
> > 1. g4 e5 2. f4 Qh4 mate.
> >
> > Claus-Juergen
>
> # Thanks. I don't know much about chess, but have
> heard it called a game of pure skill (no "luck"
> involved; e.g. as in dealing a pack of cards).
> Presumably, this is because -
> (1) It has fixed rules, with no exceptions.
> (2) to any move, there are only a certain number of
> options available (disjunctives).
> (3) the two players take turns to move one piece.
> (4) result is check(mate), or stalemate (draw).
> (5) given above factors, all possible games can be
> determined.
> (6) from this, longest possible game can be found.
> (7) a computer is likely to beat a human, as it has
> greater memory capacity, and is ruthlessly logical.

You forgot --

(8) Both players have complete information, unlike in cards, where each
player is the only one that sees their hand.

--- Christopher Heckman
Anonymous
May 26, 2005 8:45:06 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Keith A. Lewis wrote:
> "Proginoskes" <proginoskes@email.msn.com> writes

> >The length depends strongly on the rules which determine when a game is
> >drawn. The longest game by two grandmasters is around 269 moves.

> Actually, both the 50-move and 3-repeat rules have loopholes.

There are no 50-move restrictions. Official chess games continue to
their natural end.

> 3-repeat rules have loopholes. One player
> must "claim" the draw;

Are you sure? In any case, a game between 2 players or computer
programs, who are smart enough to understand the basic rules of chess,
will not continue after, say, the fifth repetiotion.

> otherwise the game continues. So the length is
> unbounded.

Well, if both players are so insane that they can't notice that they
are going in circles, here is indeed a simple infinite game:

1 Kc3 Kc6
2 Kb1 Kb8

3 Kc3 Kc6
4 Kb1 Kb8

5 Kc3 Kc6
6 Kb1 Kb8

etc

But what's the point in this? Chess is a problem of search on a graph.
The nodes of this graph are all possible positions in a chess game. The
arcs point from one position to every other position, accessible from
that position in one "move".

When a human or a computer program plays a game of chess or analyses a
position, he/it will never consider the same position more than once.

Thus, what matters is the total number of possible DISTINCT positions,
which is finite. And the number of non-repeating sequences of
positions, which is also finite.
Anonymous
May 27, 2005 1:18:29 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

"Claus-Jürgen Heigl" <unea@rz.uni-karlsruhe.de> wrote in message
news:D 72qpj$fft$1@news2.rz.uni-karlsruhe.de...
> Don H wrote:
> >
> > # What are the fewest moves to win a game?
>
> Apart from things like 1. e4 resign the shortest mate is
>
> 1. g4 e5 2. f4 Qh4 mate.
>
> Claus-Juergen

# Thanks. I don't know much about chess, but have heard it called a game of
pure skill (no "luck" involved; e.g. as in dealing a pack of cards).
Presumably, this is because -
(1) It has fixed rules, with no exceptions.
(2) to any move, there are only a certain number of options available
(disjunctives).
(3) the two players take turns to move one piece.
(4) result is check(mate), or stalemate (draw).
(5) given above factors, all possible games can be determined.
(6) from this, longest possible game can be found.
(7) a computer is likely to beat a human, as it has greater memory capacity,
and is ruthlessly logical.
Anonymous
May 27, 2005 5:24:48 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Don H wrote:

># Thanks. I don't know much about chess, but have heard it called a game of
>pure skill (no "luck" involved; e.g. as in dealing a pack of cards).
> Presumably, this is because -
>(1) It has fixed rules, with no exceptions.
>(2) to any move, there are only a certain number of options available
>(disjunctives).
>(3) the two players take turns to move one piece.
>(4) result is check(mate), or stalemate (draw).
>(5) given above factors, all possible games can be determined.
>(6) from this, longest possible game can be found.
>(7) a computer is likely to beat a human, as it has greater memory capacity,
>and is ruthlessly logical.

Items 1-6 are all roughly true of Go, but computers aren't very
good at Go. The move tree gets way too big way too soon to make
searching for a win a workable option, and humans are (for now)
much better at the pattern matching needed to have a good evaluation
function.

I conclude from this that #7 does not follow from numbers #1-6.

(They are also true of checkers, and we have one common checker
opening solved - the computer plays perfectly - with more on the
way.)
Anonymous
May 27, 2005 8:42:08 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

<anzaurres1@hotmail.com> wrote:
> Keith A. Lewis wrote:
>> "Proginoskes" <proginoskes@email.msn.com> writes
>>> The length depends strongly on the rules which determine when a game
>>> is drawn. The longest game by two grandmasters is around 269 moves.
>>
>> Actually, both the 50-move and 3-repeat rules have loopholes.
>
> There are no 50-move restrictions. Official chess games continue to
> their natural end.

The 50-move restriction is that a draw can be made if there have been no
captures or pawn moves in fifty consecutive moves (100 ply).


>> 3-repeat rules have loopholes. One player must "claim" the draw;
>
> Are you sure?

Yes. The official rules of chess are on the web at

http://www.fide.com/official/handbook.asp?level=EE101

Draws by repetition and the 50-move rule are covered by Articles 9.3 and
9.4, respectively.


> Well, if both players are so insane that they can't notice that they
> are going in circles, here is indeed a simple infinite game:
>
> 1 Kc3 Kc6 [etc]

It's a minor point but, in standard chess notation, `K' denotes the king.
Knights are `N' and used to be written `Kt'.


> Chess is a problem of search on a graph.

This is true of all games of perfect information.


Dave.

--
David Richerby Crystal Salted Book (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a romantic novel but it's covered in
salt and completely transparent!
Anonymous
May 27, 2005 8:42:09 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

David Richerby wrote:
>
><anzaurres1@hotmail.com> wrote:
>
>>> "Proginoskes" <proginoskes@email.msn.com> writes
>>>
>>> 3-repeat rules have loopholes. One player must "claim" the draw;
>>
>> Are you sure?
>
>Yes. The official rules of chess are on the web at
>
>http://www.fide.com/official/handbook.asp?level=EE101
>
>Draws by repetition and the 50-move rule are covered by Articles 9.3 and
>9.4, respectively.

Not only that, but it is forbidden for spectators or tournament
officials to interfere in any way, including pointing out that
a draw claim can be made.

Although I didn't make it clear at first, obviously my calculations
assume that the players claim a draw when it is legal to do so.
Otherwise the problem becomes uninteresting - the answer is that
it never stops. This is of no interest when discussing real-world
computer chess, of course; if the computer is behind it will claim
a draw when it gets a chance, and if the computer is ahead it will
avoid a position that allows the opponent to claim a draw.
Anonymous
May 27, 2005 8:42:10 PM

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

On Fri, 27 May 2005 16:17:51 +0000, Guy Macon
<http://www.guymacon.com/&gt; wrote:

>Not only that, but it is forbidden for spectators or tournament
>officials to interfere in any way, including pointing out that
>a draw claim can be made.

Well, normally. My daughter plays in scholastic tournaments. She
plays in a section for 3rd grade and under. The rule is game/30 but
they don't use clocks. If it is getting near the end of the hour, the
TD or assistant TD comes over with a clock. The TD may split the
remaining time for the players. But many of them don't know how to
use a clock. In one of my daughter's games this year, she got to the
ending K+2N vs K+P - one of those long, complicated wins that can
require more than 50 moves. (The assist. TD was there when it got
reduced to that from K+R+2N vs K+R+P.) Of course, my daughter doesn't
know how to win K+2N vs K+P. She (wisely) gave up a knight for the
pawn, and then the assist. TD declared K+N vs. K a draw (insufficient
mating material). I think it is OK for the TD to interfere in this
situation.

---
Replace you know what by j to email
Anonymous
May 27, 2005 9:51:49 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Jud McCranie wrote:
>
>Guy Macon <http://www.guymacon.com/&gt; wrote:
>
>>Not only that, but it is forbidden for spectators or tournament
>>officials to interfere in any way, including pointing out that
>>a draw claim can be made.
>
>Well, normally. My daughter plays in scholastic tournaments. She
>plays in a section for 3rd grade and under. The rule is game/30 but
>they don't use clocks. If it is getting near the end of the hour, the
>TD or assistant TD comes over with a clock. The TD may split the
>remaining time for the players. But many of them don't know how to
>use a clock. In one of my daughter's games this year, she got to the
>ending K+2N vs K+P - one of those long, complicated wins that can
>require more than 50 moves. (The assist. TD was there when it got
>reduced to that from K+R+2N vs K+R+P.) Of course, my daughter doesn't
>know how to win K+2N vs K+P. She (wisely) gave up a knight for the
>pawn, and then the assist. TD declared K+N vs. K a draw (insufficient
>mating material). I think it is OK for the TD to interfere in this
>situation.

Of course it's OK. They can set whatever rules they like. They
were, however, not playing by FIDE rules and thus any results would
not be reflected in a FIDE rating. (I doubt that anyone there was
rated, and if they were it would likely have been with USCF, not
FIDE.)
Anonymous
May 27, 2005 9:51:50 PM

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

On Fri, 27 May 2005 17:51:49 +0000, Guy Macon
<http://www.guymacon.com/&gt; wrote:

>Of course it's OK. They can set whatever rules they like. They
>were, however, not playing by FIDE rules and thus any results would
>not be reflected in a FIDE rating. (I doubt that anyone there was
>rated, and if they were it would likely have been with USCF, not
>FIDE.)

It was a USCF rated tournament.


---
Replace you know what by j to email
Anonymous
May 28, 2005 4:16:39 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Proginoskes wrote:
> anzaurres1@hotmail.com wrote:
> > Proginoskes wrote:
> > > Er, why must all elements of M begin with a Knight move?
> >
> > Suppose S is some element of M which doesn't begin with a
> > Knight move.
> >
> > Keep in mind that S is some sequence of moves.
> >
> > Let R be played as follows:
> >
> > 1. Nc3 Nc6
> > 2. Nb1 Nb8
> >
> > and then perform all the moves from S.
> >
> > Clearly R is also a winnning sequence. But R is 2 moves
> > longer than S.
>
> You also need to check for drawing possibilities. But if there is no
> draw in playing out S, then there is no draw in playing out R, because
> the 3rd move of R is a pawn move, and there is no draw before that.

Good point. The eventual irreversible pawn move is what makes my
argument valid. Actually, this pawn move will come much later than 3rd
move. First, there will be a whole bunch of knights moving back and
forth so that to repeat each postion exactly twice. There are 2^4
psitions with the knights in different "back and forth" posiitons. Each
position will be repeated twice. Except the for the original, which can
stand only one further repetition. Thus, in theory, there should be
2^4*2 - 1 = 31 half-moves of knights back and forth.

Can you by any chance find at least one such sequence of such 31
half-moves? I am too lazy today...

Next there will be some black pawn move. Next there will be at least 31
knight back and forth moves combined now with possible black bishop
and/or queen moves.

Then there will be another pawn move, folowed by incessant
back-and-forth mocves by more and more pieces... And so on. Pretty much
one "meaningful" move followed by hundreds of back-and-forth moves....

But!! There is the 50-move rule. Almost forgot! That will reduce the
number of back-and-forth moves in a hurry.... I mean, you need to
capture something every 50 moves....

Hmmmmmmm.... Interesting.....

So, every 50 moves, at least one peice must disappear or a pawn must
move forward. There are 32 pieces, counting the kings. But whenever a
game is over due to a checkmate or a draw, there will be at least 2
pieces still on the board, So, that means ther will be no more than 30
piece captures.

There are a total of 16 pawns each with 7 moves to make. Total of 16x7
= 112 moves. 30 + 112 is 140.
So,the total game length can't be longer than, say, 50x142 = 7100 or
so. That's not too bad..... :-)

This of course applies not only to winning games but to ALL games,
including draws.

I hope my stream of concience makes sense.

> > Thus S is not a sequence of winning moves of maximum length.
> > Contradiction. QED
>
> Okay, I believe it.

Thanks for providing a missing link to my proof.
Anonymous
May 28, 2005 4:27:16 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Actually, everything that I have said below applies to drawn games too.
So the theorems and calculations are universal.

I wonder if my thinking cam also produce a sequence of moves that
indeed comes close ot the theoretical upper bound... It should...

So, there will be pawn or capture moves every 50 moves. In-between
there will be 49 pairs of meanigless back-and-forth moves.

But pawns can't jump over each other. That'll reduce the possible
number of pawn moves quite a bit...

Unless somebody completes my train of thought in the meantime, I'll try
to return to it tomorrow..

How does this compare with other people's calculations?

This 50 move rule makes the problem tractible.... I think...

anzaurr...@hotmail.com wrote:
> Proginoskes wrote:
> > anzaurres1@hotmail.com wrote:
> > > Proginoskes wrote:
> > > > Er, why must all elements of M begin with a Knight move?
> > >
> > > Suppose S is some element of M which doesn't begin with a
> > > Knight move.
> > >
> > > Keep in mind that S is some sequence of moves.
> > >
> > > Let R be played as follows:
> > >
> > > 1. Nc3 Nc6
> > > 2. Nb1 Nb8
> > >
> > > and then perform all the moves from S.
> > >
> > > Clearly R is also a winnning sequence. But R is 2 moves
> > > longer than S.
> >
> > You also need to check for drawing possibilities. But if there is no
> > draw in playing out S, then there is no draw in playing out R, because
> > the 3rd move of R is a pawn move, and there is no draw before that.
>
> Good point. The eventual irreversible pawn move is what makes my
> argument valid. Actually, this pawn move will come much later than 3rd
> move. First, there will be a whole bunch of knights moving back and
> forth so that to repeat each postion exactly twice. There are 2^4
> psitions with the knights in different "back and forth" posiitons. Each
> position will be repeated twice. Except the for the original, which can
> stand only one further repetition. Thus, in theory, there should be
> 2^4*2 - 1 = 31 half-moves of knights back and forth.
>
> Can you by any chance find at least one such sequence of such 31
> half-moves? I am too lazy today...
>
> Next there will be some black pawn move. Next there will be at least 31
> knight back and forth moves combined now with possible black bishop
> and/or queen moves.
>
> Then there will be another pawn move, folowed by incessant
> back-and-forth mocves by more and more pieces... And so on. Pretty much
> one "meaningful" move followed by hundreds of back-and-forth moves....
>
> But!! There is the 50-move rule. Almost forgot! That will reduce the
> number of back-and-forth moves in a hurry.... I mean, you need to
> capture something every 50 moves....
>
> Hmmmmmmm.... Interesting.....
>
> So, every 50 moves, at least one peice must disappear or a pawn must
> move forward. There are 32 pieces, counting the kings. But whenever a
> game is over due to a checkmate or a draw, there will be at least 2
> pieces still on the board, So, that means ther will be no more than 30
> piece captures.
>
> There are a total of 16 pawns each with 7 moves to make. Total of 16x7
> = 112 moves. 30 + 112 is 140.
> So,the total game length can't be longer than, say, 50x142 = 7100 or
> so. That's not too bad..... :-)
>
> This of course applies not only to winning games but to ALL games,
> including draws.
>
> I hope my stream of concience makes sense.
>
> > > Thus S is not a sequence of winning moves of maximum length.
> > > Contradiction. QED
> >
> > Okay, I believe it.
>
> Thanks for providing a missing link to my proof.
Anonymous
May 28, 2005 12:18:26 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

anzaurres1@hotmail.com wrote:
> ...
> I don't know. Can't follow your logic. Why should the longest sequence
> of moves necessarily involve having a last pawn on the board or having
> a king a queen checkmate.

It could as well be a rook, but a bishop or a knight would cause the
game to end in a dead position, so the last 50 moves could not be used.

As far as I can see, promoting every single pawn would allow to move up
to 6*8 times a pawn, and we'd get 7 promoted pieces to be captured and
the original queen, rooks, bishop and knights being captured.

As a first approximation right the same for both sides, allowing as much
as 50 * 2 * (6*8 + 15) = 6300 moves.

I'd guess it is impossible to reach this maximum number of moves, but it
should be possile to find a game where one side reaches this maximum
number of moves, so truth lies somewhere between 3150 and 6300 moves.

> ...
Anonymous
May 28, 2005 12:25:01 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

AE wrote:
> ...
> It could as well be a rook, but a bishop or a knight would cause the
> game to end in a dead position, so the last 50 moves could not be used.
>
> As far as I can see, promoting every single pawn would allow to move up
> to 6*8 times a pawn, and we'd get 7 promoted pieces to be captured and
> the original queen, rooks, bishop and knights being captured.
>
> As a first approximation right the same for both sides, allowing as much
> as 50 * 2 * (6*8 + 15) = 6300 moves.

2 errors:

1) one queen or rook is not taken, because this would end the game
prematurely. On the other hand the last move could be a checkmate, so
the 3150 moves each are correct.

2) Since we don't know which rook or queen survives, the last promoted
pawn could be one of the pieces to be captured, so it doesn't matter
whether any of the promoted pawns is a queen or a rook.

> ...
Anonymous
May 28, 2005 1:07:05 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Guy Macon wrote:
> AE wrote:
> [in response to someone else:]
> >As a first approximation right the same for both
> >sides, allowing as much as 50 * 2 * (6*8 + 15) =
> >6300 moves.
> >
> >I'd guess it is impossible to reach this maximum
> >number of moves, but it should be possile to find
> >a game where one side reaches this maximum number
> >of moves, so truth lies somewhere between 3150 and
> >6300 moves.

Yes. This is something that X and Y (the authors of "The Longest Game",
a paper from a journal like the Journal of Recreational Mathematics)
take into consideration, that when a pawn captures, you cut down the
total number of moves by 50. But you're only shortening it by 8 * 50 =
400 moves.

> (When you write "moves", are you refering to what
> chessplayers call a move (white piece moves then
> black peice moves)?

Yes, a move is two plies.

> That is the meaning that is refered to in the "50
> move rule." Moving just a white piece or just a
> black piece is called a "ply". I find the
> calculations to be much easier to do when working
> with plies - no fractions needed.)
>
> Assuming that both players avoid allowing the other
> side to claim a draw according to the 50 move rule
> (if they don't and nobody claims the draw the game
> is infinite and this discussion becomes boring);

Note: (Once again, I'm going from memory here.) There are some
positions for which more than 100 plies are allowed before a draw can
be declared. I THINK that they involve several pieces, like K+B+R vs.
K+R, and that the number of allowed plies is not much larger than 200.
So these exceptions to the 50-move rule aren't actually relevant.

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

Also mentioned in X's and Y's article.

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

This is also mentioned in X's and Y's article.

> Assuming FIDE rules, that gives us (100*(30+96-8))-1)
> =11799 plies (5899.5 moves) as the maximum number of
> moves until the game is over.
>
> I can prove by example that this maximum number of
> moves can be reached in actual play.

--- Christopher Heckman
Anonymous
May 28, 2005 5:02:28 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Guy, I think your analysis is either totally correct or close to it.

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/&gt; 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&gt;
>
> 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&g...;
>
> 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&gt;
>
> ---------------------------------------------------------
Anonymous
May 28, 2005 7:38:23 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

AE wrote:

>As far as I can see, promoting every single pawn would allow to move up
>to 6*8 times a pawn, and we'd get 7 promoted pieces to be captured and
>the original queen, rooks, bishop and knights being captured.

Figuring out how to get them past each other without losing any of
them is an interesting puzzle, but it can be done; you have to use
some of the original queen, rooks, bishop and knights being captured
to also shift the pawn doing the capturing sideways.

>As a first approximation right the same for both sides, allowing as much
>as 50 * 2 * (6*8 + 15) = 6300 moves.
>
>I'd guess it is impossible to reach this maximum number of moves, but it
>should be possile to find a game where one side reaches this maximum
>number of moves, so truth lies somewhere between 3150 and 6300 moves.

I need to sit down and work out the numbers after I go offline,
but on the face of it it seems from the above that my original
calculation might have missed something. Here is that calculation;
if anyone sees an error, please let me know

(When you write "moves", are you refering to what chessplayers call a
move (white piece moves then black peice moves)? That is the meaning
that is refered to in the "50 move rule." Moving just a white piece
or just a black piece is called a "ply". I find the calculations to
be much easier to do when working with plies - no fractions needed.)

Assuming that both players avoid allowing the other side to claim
a draw according to the 50 move rule (if they don't and nobody claims
the draw the game is infinite and this discussion becomes boring);

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 long so that black can start
taking his turn moving pawns or making captures.

Assuming FIDE rules, that gives us (100*(30+96-8))-1)=11799 plies
(5899.5 moves) as the maximum number of moves until the game is over.

I can prove by example that this maximum number of moves can be
reached in actual play.
Anonymous
May 28, 2005 7:59:56 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

anzaurres1@hotmail.com wrote:

>But!! There is the 50-move rule. Almost forgot! That will reduce the
>number of back-and-forth moves in a hurry.... I mean, you need to
>capture something every 50 moves....
>
>Hmmmmmmm.... Interesting.....
>
>So, every 50 moves, at least one peice must disappear or a pawn must
>move forward. There are 32 pieces, counting the kings. But whenever a
>game is over due to a checkmate or a draw, there will be at least 2
>pieces still on the board, So, that means ther will be no more than 30
>piece captures.
>
>There are a total of 16 pawns each with 7 moves to make. Total of 16x7
>= 112 moves. 30 + 112 is 140.
>So,the total game length can't be longer than, say, 50x142 = 7100 or
>so. That's not too bad..... :-)

How do those pawns get past each other? After 8 of the pawns move
forward 4 squares each, no pawn can move.


(I find it to be easier to calculate of you use plies. In the text
above, "50 move rule" refers to a black piece moving and a white piece
moving (2 plies, one move), but "with 7 moves to make" refers to one
piece moving (1 ply, 1/2 of a move) It is a lot less confusing to
use a a 100 ply rule and count plies instead of moves.)
Anonymous
May 28, 2005 8:46:36 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

anzaurres1@hotmail.com wrote:

>But pawns can't jump over each other. That'll reduce the possible
>number of pawn moves quite a bit...

by making 8 of the pawn moves captures, they can all pass each other.
Anonymous
May 28, 2005 9:14:58 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Proginoskes wrote:

>Note: (Once again, I'm going from memory here.) There are some
>positions for which more than 100 plies are allowed before a draw can
>be declared. I THINK that they involve several pieces, like K+B+R vs.
>K+R, and that the number of allowed plies is not much larger than 200.
>So these exceptions to the 50-move rule aren't actually relevant.

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;
May 29, 2005 6:05:40 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

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/&gt; 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>
Anonymous
May 29, 2005 9:43:54 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

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

> 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
Anonymous
May 29, 2005 9:57:16 PM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

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
May 30, 2005 12:27:47 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

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
Anonymous
May 30, 2005 1:28:11 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

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.
Anonymous
May 30, 2005 1:28:12 AM

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

On Sun, 29 May 2005 at 21:28 GMT, 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.

A third possibility is that White is in zugzwang at the start of
the game. ;) 


--
Chris F.A. Johnson <http://cfaj.freeshell.org&gt;
==================================================================
Shell Scripting Recipes: A Problem-Solution Approach, 2005, Apress
<http://www.torfree.net/~chris/books/cfaj/ssr.html&gt;
Anonymous
May 30, 2005 2:05:02 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

cbrown@cbrownsystems.com wrote:
>
>Guy Macon <http://www.guymacon.com/&gt; wrote:
>
>> Mike Murray wrote:
>> >
>> >Guy Macon <http://www.guymacon.com/&gt; 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/&gt;
Anonymous
May 30, 2005 2:38:56 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

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.
May 30, 2005 2:38:57 AM

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

Guy Macon wrote:
> 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.
>
>

Ernst Zermelo, a German mathematician, wrote a paper on chess in 1913
that is regarded as the first published contribution to game theory.
Zermelo’s theorem is stated below.

A corollary exists that states for chess one of three possible outcomes
are possible:
1. White has a strategy which always wins.
2. White has a strategy that always draws, but not necessarily a winning
strategy as in 1.
3. Black has a strategy that always wins.

Basically this amounts to the statement that zero sum games with perfect
information have optimal strategies.

Mondo
Anonymous
May 30, 2005 2:50:30 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

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.
Anonymous
May 30, 2005 2:55:04 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

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.
May 30, 2005 6:35:47 AM

Archived from groups: alt.philosophy,sci.physics,rec.games.chess.computer,sci.math (More info?)

Guy Macon wrote:
> cbrown@cbrownsystems.com wrote:
> >
> >Guy Macon <http://www.guymacon.com/&gt; wrote:
> >
> >> Mike Murray wrote:
> >> >
> >> >Guy Macon <http://www.guymacon.com/&gt; 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/&gt;
      • 1 / 2
      • 2
      • Newest
!