Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old February 4th 04, 11:40 AM
David Richerby
 
Posts: n/a
Default endgame tablebases - future?

[ -- rec.games.chess.computer ]

Jud McCranie wrote:
If the 6-piece endings can be done, what is the largest set that can
reasonably be completed?


Depends how long Moore's law holds, really. If CPUs keep doubling in
speed every eighteen months and storage (both RAM and disc) keep up their
similar performance (ISTR they've been doubling in capacity every year for
a while, though I don't recall the exact details) then larger and larger
tablebases will become feasible.

If my understanding of tablebases is correct, adding an extra man should
require about sixty times more storage[1], assuming it doesn't affect
compression. That means that storing a new set of tablebases becomes
feasible about once every six years at current rates.[2] I'm not at all
sure about how soon it will be feasible to compute the tablebases.


Dave.

[1] The n-man tablebase has to store the move for 64 x 63 x ... x (65-n)
positions, which is the number of possible arrangements of those
pieces. You can divide that by four because of Black/White and
kingside/queenside symmetry. Since n is small, 65-n is about sixty.

[2] Because log_2 60 is about 6 doubling periods.

--
David Richerby Evil Peanut (TM): it's like a roasted
www.chiark.greenend.org.uk/~davidr/ nut but it's genuinely evil!
  #2   Report Post  
Old February 4th 04, 04:21 PM
Liam Too
 
Posts: n/a
Default endgame tablebases - future?

Does that mean that the 32 man Nalimov tablebases will not be
developed soon and perhaps not this century, thereby Chess cannot be
solved just yet?

Lance Smith

David Richerby wrote in message ...
[ -- rec.games.chess.computer ]

Jud McCranie wrote:
If the 6-piece endings can be done, what is the largest set that can
reasonably be completed?


Depends how long Moore's law holds, really. If CPUs keep doubling in
speed every eighteen months and storage (both RAM and disc) keep up their
similar performance (ISTR they've been doubling in capacity every year for
a while, though I don't recall the exact details) then larger and larger
tablebases will become feasible.

If my understanding of tablebases is correct, adding an extra man should
require about sixty times more storage[1], assuming it doesn't affect
compression. That means that storing a new set of tablebases becomes
feasible about once every six years at current rates.[2] I'm not at all
sure about how soon it will be feasible to compute the tablebases.


Dave.

[1] The n-man tablebase has to store the move for 64 x 63 x ... x (65-n)
positions, which is the number of possible arrangements of those
pieces. You can divide that by four because of Black/White and
kingside/queenside symmetry. Since n is small, 65-n is about sixty.

[2] Because log_2 60 is about 6 doubling periods.

  #3   Report Post  
Old February 4th 04, 04:56 PM
Jud McCranie
 
Posts: n/a
Default endgame tablebases - future?

On 04 Feb 2004 11:40:27 +0000 (GMT), David Richerby
wrote:

If my understanding of tablebases is correct, adding an extra man should
require about sixty times more storage[1],


However, it seems to me that the amount of computation goes up faster
than the storage needed because with more pieces, there are more ways
to reach a given position (in addition to there being roughly a factor
of 60 more positions).

Actually, there may be a lot more than 60 times as many positions when
adding one piece. Consider each of the 5-piece positions. You can
add a white queen in about 59 ways, a black queen in about 59 ways,
etc. Many of these are going to be duplicates, and some are
symmetrical, but I think there will be an increase of a lot more than
a factor of 60.


-------------------------------------
Replace you know what by "j" to email.
  #4   Report Post  
Old February 4th 04, 05:22 PM
Alexander Belov
 
Posts: n/a
Default endgame tablebases - future?

"Jud McCranie" wrote in message
news
On 04 Feb 2004 11:40:27 +0000 (GMT), David Richerby
wrote:

If my understanding of tablebases is correct, adding an extra man should
require about sixty times more storage[1],


However, it seems to me that the amount of computation goes up faster
than the storage needed because with more pieces, there are more ways
to reach a given position (in addition to there being roughly a factor
of 60 more positions).

Actually, there may be a lot more than 60 times as many positions when
adding one piece. Consider each of the 5-piece positions. You can
add a white queen in about 59 ways, a black queen in about 59 ways,
etc. Many of these are going to be duplicates, and some are
symmetrical, but I think there will be an increase of a lot more than
a factor of 60.

But obviously no more than 64 for every new piece.



-------------------------------------
Replace you know what by "j" to email.



  #5   Report Post  
Old February 4th 04, 05:25 PM
Alexander Belov
 
Posts: n/a
Default endgame tablebases - future?

It will require 2 in power 169..172 bits to store. This is more
than atoms in Universe.

"Liam Too" wrote in message
om...
Does that mean that the 32 man Nalimov tablebases will not be
developed soon and perhaps not this century, thereby Chess cannot be
solved just yet?





  #6   Report Post  
Old February 4th 04, 06:24 PM
Anders Thulin
 
Posts: n/a
Default endgame tablebases - future?

David Richerby wrote:

[1] The n-man tablebase has to store the move for 64 x 63 x ... x (65-n)
positions, which is the number of possible arrangements of those
pieces. You can divide that by four because of Black/White and
kingside/queenside symmetry. Since n is small, 65-n is about sixty.


For at *most* that number of positions. For pawnless endgames, it's at
most 10 x 63 x ... etc. for symmetry reasons.

If you also avoid including impossible positions (wK next to bK, for instance)
in the enumeration scheme, there will be a corresponding reduction in size,
though the mapping function will become more complex.

--
Anders Thulin http://www.algonet.se/~ath

  #7   Report Post  
Old February 4th 04, 10:41 PM
Liam Too
 
Posts: n/a
Default endgame tablebases - future?

Thanks Alexander,

That's what I've been telling the Trollsby and he kept saying that
chess has been solved and it's a draw. Without the 32 man Nalimov, we
will never know for sure.

Lance

"Alexander Belov" wrote in message ...
It will require 2 in power 169..172 bits to store. This is more
than atoms in Universe.

"Liam Too" wrote in message
om...
Does that mean that the 32 man Nalimov tablebases will not be
developed soon and perhaps not this century, thereby Chess cannot be
solved just yet?

  #8   Report Post  
Old February 5th 04, 01:53 AM
Jud McCranie
 
Posts: n/a
Default endgame tablebases - future?

On 04 Feb 2004 11:40:27 +0000 (GMT), David Richerby
wrote:

If my understanding of tablebases is correct, adding an extra man should
require about sixty times more storage[1],


However, it seems to me that the amount of computation goes up faster
than the storage needed because with more pieces, there are more ways
to reach a given position (in addition to there being roughly a factor
of 60 more positions).

Actually, there may be a lot more than 60 times as many positions when
adding one piece. Consider each of the 5-piece positions. You can
add a white queen in about 59 ways, a black queen in about 59 ways,
etc. Many of these are going to be duplicates, and some are
symmetrical, but I think there will be an increase of a lot more than
a factor of 60.

I think the time might be more of a limiting factor than storage.


-------------------------------------
Replace you know what by "j" to email.
  #9   Report Post  
Old February 5th 04, 10:09 AM
Alexander Belov
 
Posts: n/a
Default endgame tablebases - future?

There is more than suspicion that chess game starting from initial position
with
perfect play ends as draw. This cannot be proven without 32 man tablebase,
but suspicion is enforced by the statistical fact that each lost game
contains
some move or series of moves that caused this loss, but could be prevented
with some other move or series of moves.

"Liam Too" wrote in message
om...
Thanks Alexander,

That's what I've been telling the Trollsby and he kept saying that
chess has been solved and it's a draw. Without the 32 man Nalimov, we
will never know for sure.

Lance

"Alexander Belov" wrote in message

...
It will require 2 in power 169..172 bits to store. This is more
than atoms in Universe.

"Liam Too" wrote in message
om...
Does that mean that the 32 man Nalimov tablebases will not be
developed soon and perhaps not this century, thereby Chess cannot be
solved just yet?



  #10   Report Post  
Old February 5th 04, 04:19 PM
Jud McCranie
 
Posts: n/a
Default endgame tablebases - future?

On 04 Feb 2004 11:40:27 +0000 (GMT), David Richerby
wrote:

If my understanding of tablebases is correct, adding an extra man should
require about sixty times more storage[1],


However, it seems to me that the amount of computation goes up faster
than the storage needed because with more pieces, there are more ways
to reach a given position (in addition to there being roughly a factor
of 60 more positions).

Actually, there may be a lot more than 60 times as many positions when
adding one piece. Consider each of the 5-piece positions. You can
add a white queen in about 59 ways, a black queen in about 59 ways,
etc. Many of these are going to be duplicates, and some are
symmetrical, but I think there will be an increase of a lot more than
a factor of 60.

I think the time might be more of a limiting factor than storage.


-------------------------------------
Replace you know what by "j" to email.
Reply
Thread Tools
Display Modes

Posting Rules

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


Similar Threads
Thread Thread Starter Forum Replies Last Post
endgame tablebase bug/question Thomas rec.games.chess.computer (Computer Chess) 4 November 22nd 03 12:37 PM
Who was better in this endgame? gec rec.games.chess.analysis (Chess Analysis) 3 October 15th 03 06:20 PM
My first endgame study (intermediate) Claus-Jürgen Heigl rec.games.chess.analysis (Chess Analysis) 3 September 6th 03 10:59 AM
Nalimov Endgame Tablebases Michael Byrne rec.games.chess.computer (Computer Chess) 0 September 5th 03 02:58 AM
tablebases hang Shredder7.04 with XP CeeBee rec.games.chess.computer (Computer Chess) 7 August 26th 03 04:15 PM


All times are GMT +1. The time now is 08:11 AM.

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

About Us

"It's about Chess"

 

Copyright © 2017