Magnus thinks 7-piece TBs won't be resolved in our lifetime

[M ANSARI]

I wonder what are people's thoughts on this.

Assuming he's including the kings into the number 7 (which he does, as he also mentions the number 32), he's not very up to date. The 7-piece tables have all been generated already.
https://plus.google.com/100454521496393505718/posts

Yes I saw that and was quite surprised. I know some things in chess that Magnus Carlsen doesn't yet know !!!

As for solving chess with 32 EGTB's ... I don't think that will ever happen, but I certainly think that chess will be solved quite soon ... but in a totally different way. Chess will be solved by simple databases and a super strong engine ... for example if you start with a3 and say h4 as your second white move, I am pretty sure that the game simply cannot be saved no matter what tablebases you have and it will be a forced win with any of today's strong engines on good hardware. In some lines the databases are so deep and deviating with one move can mean immediate loss. I can see a situation where the databases are so deep and the engines so strong that any deviation from the database can be forced into a win or draw. Just like engines don't need EGTB's to win a 2 bishop vs. king endgame you won't need to generate all EGTB's to solve chess.

[arjuntemurnikar]

Are there any plans to have a DTZ version of Lomonosov Endgame Tablebases by yourself, or someone else? Is this even feasible?

My generator (with a few minor modifications) would need a machine with 1TB of shared memory to generate 7-piece tables. Such machines exist, but I don't have one . I suppose they will become affordable eventually.

That should do it, right?

sorry forgot to put in the link:
http://www.ebay.com/itm/DELL-POWEREDGE- ... 485fb9ccf7

1TB RAM on a die the size of a stamp is not too far into the future. http://hexus.net/tech/news/storage/5857 ... ler-stamp/

[arjuntemurnikar]

Are there any plans to have a DTZ version of Lomonosov Endgame Tablebases by yourself, or someone else? Is this even feasible?

My generator (with a few minor modifications) would need a machine with 1TB of shared memory to generate 7-piece tables. Such machines exist, but I don't have one . I suppose they will become affordable eventually.

That should do it, right?

sorry forgot to put in the link:
http://www.ebay.com/itm/DELL-POWEREDGE- ... 485fb9ccf7

1TB RAM on a die the size of a stamp is not too far into the future. http://hexus.net/tech/news/storage/5857 ... ler-stamp/

Also, no need to churn out 20K+ for such a system. A DIY / custom build will cost much less. For e.g. http://www.titanuscomputers.com/Titanus ... p/a450.htm

[syzygy]

1TB RAM on a die the size of a stamp is not too far into the future. http://hexus.net/tech/news/storage/5857 ... ler-stamp/

That seems to be a form of flash ram. Not so useful for generation, but very useful for storing (and accessing) 10 TB of WDL afterwards.

Also, no need to churn out 20K+ for such a system. A DIY / custom build will cost much less. For e.g. http://www.titanuscomputers.com/Titanus ... p/a450.htm

Starting Price: $4,300.00
1TB (32 x 32GB) DDR3 SDRAM ECC Registered DDR3 1333Mhz Quad Channel Server Memory [Add $17,600.00]

[duncan]

So IF your numbers are correct, we need a 10 men TB with a size bigger than 4 times our current internet.

So take all hard drives in this earth holding that data, buy 3 or 4 more times that, sum them up, interconnect them, POWER them, FILL them with the data and keep them all up at the same time available for some chess players /engines consult them.

Who will do the work? Who will pay the energy? How much time will take to compute the TB? How much time to verify all data is correct?

How you will handle disk failures? Or you expect to have a backup?

This is like like taking a man to Pluto o Neptune...at some time will be possible, but it worth?

I do not disagree with you. that is why I wrote in theory. but according to this link the pentagon is aiming for yottabytes storage. if this is correct and if us wins war on terror then in the near future bill gates should be be able to buy some good storage facilty which would be easy to store 12 piece database

http://www.wired.com/threatlevel/2012/0 ... enter/all/


as a 2007 Department of Defense report puts it, the Pentagon is attempting to expand its worldwide communications network, known as the Global Information Grid, to handle yottabytes (1024 bytes) of data. (A yottabyte is a septillion bytes—so large that no one has yet coined a term for the next higher magnitude.)

duncan

[IGarcia]

So IF your numbers are correct, we need a 10 men TB with a size bigger than 4 times our current internet.

So take all hard drives in this earth holding that data, buy 3 or 4 more times that, sum them up, interconnect them, POWER them, FILL them with the data and keep them all up at the same time available for some chess players /engines consult them.

Who will do the work? Who will pay the energy? How much time will take to compute the TB? How much time to verify all data is correct?

How you will handle disk failures? Or you expect to have a backup?

This is like like taking a man to Pluto o Neptune...at some time will be possible, but it worth?

I do not disagree with you. that is why I wrote in theory. but according to this link the pentagon is aiming for yottabytes storage. if this is correct and if us wins war on terror then in the near future bill gates should be be able to buy some good storage facilty which would be easy to store 12 piece database

http://www.wired.com/threatlevel/2012/0 ... enter/all/


as a 2007 Department of Defense report puts it, the Pentagon is attempting to expand its worldwide communications network, known as the Global Information Grid, to handle yottabytes (1024 bytes) of data. (A yottabyte is a septillion bytes—so large that no one has yet coined a term for the next higher magnitude.)

duncan

To "handle" yottabytes. Thats not very clear about what means handle. Besides that, maybe we can get 8 pieces TB in a few years. 9 and more probably will not worth the effort.

As Ansari writes, probably the EGTB + databases + future engines will make chess close to be solved. There is other topic in this forum about how harvested is chess today. In few years, when there will be 8 men TB available, chess will be much more harvested...

Ignacio

[M ANSARI]

So IF your numbers are correct, we need a 10 men TB with a size bigger than 4 times our current internet.

So take all hard drives in this earth holding that data, buy 3 or 4 more times that, sum them up, interconnect them, POWER them, FILL them with the data and keep them all up at the same time available for some chess players /engines consult them.

Who will do the work? Who will pay the energy? How much time will take to compute the TB? How much time to verify all data is correct?

How you will handle disk failures? Or you expect to have a backup?

This is like like taking a man to Pluto o Neptune...at some time will be possible, but it worth?

I do not disagree with you. that is why I wrote in theory. but according to this link the pentagon is aiming for yottabytes storage. if this is correct and if us wins war on terror then in the near future bill gates should be be able to buy some good storage facilty which would be easy to store 12 piece database

http://www.wired.com/threatlevel/2012/0 ... enter/all/


as a 2007 Department of Defense report puts it, the Pentagon is attempting to expand its worldwide communications network, known as the Global Information Grid, to handle yottabytes (1024 bytes) of data. (A yottabyte is a septillion bytes—so large that no one has yet coined a term for the next higher magnitude.)

duncan

To "handle" yottabytes. Thats not very clear about what means handle. Besides that, maybe we can get 8 pieces TB in a few years. 9 and more probably will not worth the effort.

As Ansari writes, probably the EGTB + databases + future engines will make chess close to be solved. There is other topic in this forum about how harvested is chess today. In few years, when there will be 8 men TB available, chess will be much more harvested...

Ignacio

Actually "harvesting" is an excellent analogy to how chess will be solved. As chess opening databases try to harvest new ideas, these ideas will be so well analyzed and tried out that any winning or drawing line is immediately tabulated and stored in a database that all can share. Something like that is happening as we speak with Chessbase's new system of online sharing all analysis you do on any position or opening. As much as tabulating all games ever played (including engine games) seems a lot, it is way less than the memory required for even 7 piece EGTB's. Already engines are so strong that a +2.0 evaluation in the opening or middle game has a very high percentage to end in a win ... most likely as engines get stronger this will soon be 100%. My prediction is that in 50 years the opening databases will be so deep and so accurate, that an engine of even today's strength on today's hardware will not lose a single game in 1000 games against the most powerful engine that will be available in 50 years. If you take into consideration 50 years of software improvement and 50 years of hardware improvement and 50 years of accumulated opening databases ... sounds like a very reasonable time frame to say that chess will be solved.

[JVMerlino]

Some real numbers from http://en.wikipedia.org/wiki/Endgame_tablebase :
6 pieces : 2005
7 pieces : August 2012

add:
5 pieces : End of 2002

I think Ken Thompson did all 5-piece tables in 1986 (but maybe these were not complete?).
He also did 6-piece tables somewhere in the 90s, but it seems this set is not complete and in particular does not include pawn endgames. Lewis Stiller was the first to do pawnless 6-piece endgames on a 65536-processor Connection Machine, but he could not save the results.

I'm pretty sure Steven Edwards generated some 5-piece tables before 2000, but maybe he did not generate all of them.

This paper suggests that the 5-piece Nalimov set was finished in 2000 or earlier. In fact it mentions the tables were used in WCCC 1999, so they were probably available already in 1998 or 1999. This is also more in line with my memory.

From the readme for Johan de Koning's FEG generator:
===========
In the 1970's there was quite some reasearch on the topic. However, it
became interesting after Ken Thompson dedicated a machine for several
years to produce most of the interesting 5 piece EGDBs (DTC), and
eventually made them available on CD for free. In the early 90's Stiller
did some work on a massive parallel system on 6 pieces, but he couldn't
save the data. In the meanwhile Edwards redid the 5 pieces for DTM but
mainly for research, without compression. Nalimov redid them again, but
used compression (better than Thompson's, but still larger because of
DTM). Nalimov's have been widely used since 1999. This is all public
knowledge. Not public were the Koning & Kuijf experments, done since
1995. These experiments were targeted at building EGDBs fast, and
succeeded in being fast. Though the actual data is more or less the same
as Nalimov's.
===========

So this implies that complete 5-man data was available no later than 1999, and possibly, as you suggest, in 1998. The Wikipedia entry for Nalimov states that he wrote the generator in 1998, but it doesn't say when the complete set was finished.

You can see the whole FEG readme here, for nostalgia purposes.

ftp://ftp.ubisoft.com/games/chessmaster ... Readme.TXT

jm

[syzygy]

From this paper by the guys behind Deep Blue

8.3. Endgame databases

The endgame databases in Deep Blue includes all chess positions with five or fewer pieces 20 on the board, as well as selected positions with six pieces that included a pair of blocked pawns. The primary sources for these databases were the Ken Thompson CD-ROMs [27] and additional databases supplied by Lewis Stiller.
Endgames databases were used both off-line and on-line. The off-line usage was during the design of the chess chips. Each chip had a ROM which stored patterns to help evaluate certain frequently occurring chess endgames. The databases were used to verify and evaluate these patterns. See Section 5 for more details.
The software search used the databases in on-line mode. Each of the 30 general purpose processors in the Deep Blue system replicated the 4-piece and important 5-piece databases on their local disk. The remaining databases, including those with 6 pieces, were duplicated on two 20-GB RAID disk arrays, and were available to all the general purpose processors through the SP switch.
Endgames were stored in the databases with one bit per position (indicating lose or does-not-lose). If a position is reached during the search that had a known value, it received a score composed of two parts: a high-order, game theoretic value, and a low-order, tie-breaker value. The tiebreaker value is simply the value produced by the evaluation function on the position in question. If this score is sufficient to cause a cutoff, the search immediately backs up this score.
For example, suppose Deep Blue had to choose between various possible continuations that resulted in it playing the weak side of a rook and pawn versus rook endgame. Deep Blue would, of course, prefer drawn positions over lost ones. In addition, given the choice between different drawn positions, it would choose the one with the best evaluation function value.
The endgame databases did not play a critical role in the matches against Kasparov. In the 1997 match, only game 4 approached an endgame that required access to the databases, but the ROMs on the chess chips had sufficient knowledge to recognize the rook and pawn versus rook draws that could have arisen.

So Deep Blue literally had bitbases: lose / does-not-lose.

The claim of a complete 5-piece set suggests that Thompson's CD-ROMS include a complete 5-piece set. And apparently Lewis Stiller eventually did have the means to save results. (But there are more ways to read this passage.)

edit:
According to this paper Thompson generated "almost all" 5-men chess endgame databases.

Thompson's 1986 paper does not give the definitive answer. However, he only mentions endgames with one pawn and I seem to remember reading somewhere that he only did endgames with up to 1 pawn.

[carldaman]

Funny how we now have to become 'archaeologists' just to uncover relatively recent history relating to endgame tablebases.

Regards,
CL