Distributed calculation of tablebases
Dr. med. Thorsten Heedt
I'm very enthusiastic about the possibilities of distributed
calculating. For example, the Search for Extraterrestrial
Intelligence-Project is a nice way to let thousands of computers
calculate on one big project.
Why not doing this with tablebases ? If someone has the know-how, we
could get the complete 6-piece-endgame tables and perhaps (?) some of
the 7-piece-endgame tables in a reasonable time (?).
Of course, I am not sure how many giga- oder terabytes are necessary
for those larger endgame tables...
How do you think about this
Simon Waters
>
> Why not doing this with tablebases ? If someone has the know-how, we
> could get the complete 6-piece-endgame tables and perhaps (?) some of
> the 7-piece-endgame tables in a reasonable time (?).
> Of course, I am not sure how many giga- oder terabytes are necessary
> for those larger endgame tables...
>
> How do you think about this
It sounds a good way to kill the Internet ;)
A six piece tablebase relies for generation on the five piece
table base. You either have them all stored locally (Which
rapidly defeats the point of a distributed solution), or you
have a LOT of chatter as the program asks other machines - "what
result this position?".....
I thought storage was more of an obstacle than CPU? Anyone got
any recent figures?
Either way I'm pretty sure a distributed approach will make
bandwidth the limiting factor, and people don't spare that as
willingly as idle CPU.
Guy Macon
Simon Waters <Si...@wretched.demon.co.uk> wrote:
>Dr. med. Thorsten Heedt <Dr.med.Tho...@web.de> wrote:
>>
>>I'm very enthusiastic about the possibilities of distributed
>>calculating. For example, the Search for Extraterrestrial
>>Intelligence-Project is a nice way to let thousands of computers
>>calculate on one big project.
>>
>>Why not doing this with tablebases ? If someone has the know-how, we
>>could get the complete 6-piece-endgame tables and perhaps (?) some of
>>the 7-piece-endgame tables in a reasonable time (?).
>>Of course, I am not sure how many giga- order terabytes are necessary
>>for those larger endgame tables...
>>
>>How do you think about this
>A six piece tablebase relies for generation on the five piece
>table base. You either have them all stored locally (Which
>rapidly defeats the point of a distributed solution), or you
>have a LOT of chatter as the program asks other machines - "what
>result this position?".....
Why would you think that having all five piece tablebases
stored locally defeats the point of a distributed solution?
I would agree if the project was like Seti@home where huge
numbers of people download a small executable and small data
sets, but the idea could work very well if we limit ourselves
to those who are willing to store all five piece tablebases
locally. Making it so that the local storage of all five
piece tablebases is in a format that can also be used by
chess programs such as crafty would make that constraint
easier to swallow. My gut feeling is that this is a task
well suited to hundreds or even thousands of computers, but
not the millions of computers that the other distributed
processing projects are shhoting for.
Dr. Heedt, I think you have an excellent idea. I would be glad
to volunteer to work with you or anyone else on this project.
If anyone is interested, Please email me at
t a b l e b a s e @ g u y m a c o n . c o m
(remove the spaces.)
BTW, there is a related project at www.distributed.net described thusly:
Distributed Chess Engine:
Remy de Ruysscher (re...@cyberservices.com) is in the process of
organizing programmers to build a distributed chess engine module
to be used with the eventual distributed.net V3 clients. Feel free
to drop him a line if you're interested, and as the project gets a
bit more organized, you'll be able to find more information here
at distributed.net.
Anders Thulin
> Why not doing this with tablebases ? If someone has the know-how,
The know-how is the missing part. It seems the task cannot easily
be broken into smaller subtasks that are sufficiently well isolated.
If it can be done so with difficulty is not clear.
--
Anders Thulin a...@algonet.se http://www.algonet.se/~ath
Michael Burnem
news:3ccf1730...@news.t-online.de...
*forwarding to crafty mailing list*
Seems like a good idea to me.
GSV Three Minds in a Can
person Dr. med. Thorsten Heedt <Dr.med.Tho...@web.de> said
I don't believe this problem is amenable to chopping up and
distributing. In order to resolve <position X> you need to look at all
the positions this can turn into (with moves, captures, etc). If these
are not on your machine, it take you like 250 microseconds to derive all
the 'resulting positions' and then about a fortnight to find out from
some other machine(s) whether these new positions are already resolved
to a win/loss/draw.
The processing power for tablebase generation is just one element of the
requirement .. the huge gobs of memory to store all the 'prior
knowledge' (including all the lesser-number-of-piece tablebases) for
rapid look-up are much more of a problem (have you looked at the size of
some of the =5= piece TBs!?)
--
GSV Three Minds in a Can
Dieter Buerssner
>"Dr. med. Thorsten Heedt" wrote:
>>
>> Why not doing this with tablebases ? If someone has the know-how, we
>> could get the complete 6-piece-endgame tables and perhaps (?) some of
>> the 7-piece-endgame tables in a reasonable time (?).
>A six piece tablebase relies for generation on the five piece
>table base. You either have them all stored locally (Which
>rapidly defeats the point of a distributed solution), or you
>have a LOT of chatter as the program asks other machines - "what
>result this position?".....
I think, it is even worse. For 6-men tables with pawns (which should be the
most interesting ones), you will also need the promotion 6-piece cases. So,
I think, for generating KBPKNP, you would need KQBKNP, KRBKNP, KBBKNP,
KBNKNP, KQNKBP, KRNKBP, KBNKBP, KNNKBP. These will take up many Gigabytes
und more than 32 bit address space, if I am not totally mistaken.
However, because pawns cannot change the file without capture, one could
perhaps distribute the work and generate the TBs file-wise. But it still
looks not too easy to distribute this.
Regards,
Dieter
David Fabian
>
I have been thinking about this exact problem recently. See:
http://groups.google.com/groups?q=database+author:david.m.fabian%40sbcglobal.net&hl=en&selm=t3Pk8.66933%24356.2762151095%40newssvr30
.news.prodigy.com&rnum=1
In February 1995 (between jobs), I wrote a program that generated chess endgame
databases on a PC. At the time, I concluded that both the CPU time on a supercom-
puter and 5 terabytes of disk storage space (for all 6-piece positions) were too ex-
pensive, and it would be difficult to recoup the expenses by trying to sell access to
the database.
Recently, I have been thinking about starting an ongoing project to build the tables
using both distributed computing and distributed storage, where the chess players
who want to access the database would also donate CPU time and disk space. The
expenses would be minimal using such donations, and the work would simply pause
whenever free CPU time or disk space were not available.
If anyone is interested in working with me, I have already thought of many ways to
parse the problem and to minimize the Internet traffic.
As the cost of storage decreases (see http://www.archivebuilders.com/aba011.html),
CPU speeds increase (see http://news.com.com/2008-1082-252620.html?legacy=cnet),
and the number of chess players increases, the database generation speed will increase.
Dave
Guy Macon
>In February 1995 (between jobs), I wrote a program that generated chess endgame
>databases on a PC. At the time, I concluded that both the CPU time on a supercom-
>puter and 5 terabytes of disk storage space (for all 6-piece positions) were too ex-
>pensive, and it would be difficult to recoup the expenses by trying to sell access to
>the database.
>
>Recently, I have been thinking about starting an ongoing project to build the tables
>using both distributed computing and distributed storage, where the chess players
>who want to access the database would also donate CPU time and disk space. The
>expenses would be minimal using such donations, and the work would simply pause
>whenever free CPU time or disk space were not available.
>
>If anyone is interested in working with me, I have already thought of many ways to
>parse the problem and to minimize the Internet traffic.
>
>As the cost of storage decreases (see http://www.archivebuilders.com/aba011.html),
>CPU speeds increase (see http://news.com.com/2008-1082-252620.html?legacy=cnet),
>and the number of chess players increases, the database generation speed will increase.
I am interested in helping in any way I can. Alas, my skills are in
embedded systems, where a 1Mhz processor with 64 bytes of RAM is
considered a "Supercomputer", but I would be glad to do what I can.
Have you considered making this a distributed.net project?
Is that 5 TB figure for compressed tablebases?
Roughly how much CPU time do you estimate it will take?
David Fabian
> David Fabian <David.M...@sbcglobal.net> wrote:
>
> >In February 1995 (between jobs), I wrote a program that generated chess endgame
> >databases on a PC. At the time, I concluded that both the CPU time on a supercom-
> >puter and 5 terabytes of disk storage space (for all 6-piece positions) were too ex-
> >pensive, and it would be difficult to recoup the expenses by trying to sell access to
> >the database.
> >
> >Recently, I have been thinking about starting an ongoing project to build the tables
> >using both distributed computing and distributed storage, where the chess players
> >who want to access the database would also donate CPU time and disk space. The
> >expenses would be minimal using such donations, and the work would simply pause
> >whenever free CPU time or disk space were not available.
> >
> >If anyone is interested in working with me, I have already thought of many ways to
> >parse the problem and to minimize the Internet traffic.
> >
> >As the cost of storage decreases (see http://www.archivebuilders.com/aba011.html),
> >CPU speeds increase (see http://news.com.com/2008-1082-252620.html?legacy=cnet),
> >and the number of chess players increases, the database generation speed will increase.
>
> I am interested in helping in any way I can.
This is good to hear. I read your other post in this thread about helping. I
think it would be best to coordinate with several types of computer specialists.
> Alas, my skills are in embedded systems, where a 1Mhz processor with
> 64 bytes of RAM is considered a "Supercomputer", but I would be glad
> to do what I can.
The project could certainly benefit from your knowledge of assembly language
and optimization.
> Have you considered making this a distributed.net project?
distributed.net has joined forces with United Devices (ref www.ud.com,
http://www.distributed.net/pressroom/news-20001127.html) which is listed at
http://www.aspenleaf.com/distributed/distrib-projects.html under "Science",
while distributed.net is listed under "Cryptography".
It might be difficult to keep people participating in the chess project, when
projects like cancer research are arguably more important. Simon Waters
joked earlier in this thread, "It sounds [like] a good way to kill the Internet."
This brings up the issue of liability. Any distributed computing project that
causes enough network traffic could be held liable for crippling the network,
just like virus or worm authors are held liable.
> Is that 5 TB figure for compressed tablebases?
It is what I estimated for an uncompressed database of all 6-piece positions.
Using compression and discarding huge ranges of positions that are drawn,
might reduce the database to about 500 GB.
> Roughly how much CPU time do you estimate it will take?
I have thought of many ways to optimize the algorithms, but I am sure I am
missing many tricks; so I am afraid my guess would be pretty inaccurate right
now.
Dave
Unknown
over the internet. The main problem is that if the size of the
database exceeds the size of your physical memory (RAM),
you need to read and write the whole thing from and to
your storage device many times over.
The speed of this storage device is crucial. If the storage
device is a local hard disk, this may be doable. But
if even this is not large enough, (and it won't be for
7 piece endings for some time to come) you need
distributed storage. The internet is simply not
fast enough to transfer Terabyte files to individual
people.
Maybe if somebody had access to a small
(say 64 processor, 200 Gb disk/processor)
parallel computer he could do the computations.
But then you would have the problem of distribtion...
Otherwise I think the focus should be on the pawned
6 piece endgames; if you exploit the fact that
each pawn move is a conversion to another database,
I think these can be done on an 'ordinary' pc.
Michel