Damage does not have (yet) the 7 Piece Endgame Databases

[BertTuyt]

I did a small check on the internet.
Typical PC hardware around 2000:

* Pentium III, 500 MhZ
* 128 MB RAM
* 10 GB HD

With this setup it is almost impossible to generate the full 7p DB .
So if Stef did this in 1999/2000, he most likely has used other resources, or did only special 7p DB's like the 5K x 2K .

Bert

[Ed Gilbert]

I did a small check on the internet.
Typical PC hardware around 2000:

* Pentium III, 500 MhZ
* 128 MB RAM
* 10 GB HD

With this setup it is almost impossible to generate the full 7p DB .
So if Stef did this in 1999/2000, he most likely has used other resources, or did only special 7p DB's like the 5K x 2K .

Here is one data point. In spring of 2002 I bought a PC which had a 2.4GHz P4 with 2GB of RDRAM. I remember it quite well, as I used it that summer in Las Vegas at the Computer Checkers World Championship tournament, and then the next year I used it to build the 9-piece db for checkers, which is approximately the same size as the 7-piece draughts database. This pc was more than powerful enough in terms of cpu speed, RAM, and disk space, to build the 7-piece draughts db. To build it in 2000 with hardware that would be available to hobbyists like us would have been a little bit of a stretch, but only a little. I think it could have been done.

However, if he did build the full 4x3 subset of 7 pieces, then why was it kept a complete secret, and not used or revealed at the annual draughts tournaments that truus participated in? Why is there no mention of it anywhere, other than the 5kings vs. 2kings slice? Why is the truus program that is sold by the kndb not provided with at least some subset of the 7-piece db? I have to assume that the reasons are that truus never had a complete 4x3 subset of 7 pieces.

BTW that 2.4GHz machine that I bought in 2002 cost $3k. It was the last pre-built machine that I bought, as I subsequently started building my own machines. In comparison, earlier this year I built a machine with two quad-core xeons, 16gb ram, and 2TB of hard drive, and the parts cost for that machine was only $2k, which shows how far we have progressed in 7 years!

-- Ed

[Rein Halbersma]

I wonder whether it would already be cost-effective to use cloud computing services instead of building your own computers for large-scale db computations? E.g. how fast could the full 9pc dbs be computed with 128Gb of RAM? At $200/month, even a year of access on a large cloud server might be a reasonable price.

[ildjarn]

AFAIR, Stef was, around 2000, postgraduate at Maastricht University under Jaap van der Herik. I assume the university had servers that were superior to equipment sold in stores.

[BertTuyt]

To my knowledge Stef started around 1994 at the Maastricht University.
Im not 100% sure , but guess he worked only a few years there.
So hope that some-one has a clue what he published regarding the 7p positions.

Maybe Rein has some older copies

So i still believe that there still only 4 persons who have the full 7p databases (and i dont count the 6-1 sub DB's here).

For the historical perspective im not sure if Ed was first or Michel.
It is quite sure that Gerard was 3th, and I was the 4th.

But , at least regarding th 8p, there is absolutely no doubt

Bert

[BertTuyt]

Another clue, the last tournament Truus (Stef played was in 1996) where she ( [img]images/smilies/icon_smile.gif[/img] ) finished second after Flits.

I communicated via email with Stef several times between 1996 - 2000, but to my knowledge he (more or less) lost interest in Draughts programming (also something which I understand after so many tournament vicories).

Still, I really hope we will see him back some day....

Bert

[BertTuyt]

And here some info from Harm (extracted from his webside):

An endgame database allows DAM to quickly look up whether a position with a few pieces on the board is either won, drawn, or lost. That considerably improves its playing strength in end games. It was already possible to provide DAM with 3- and 4-piece endgame databases; for details read the DAM Help section Menu selection - Options - Database. For the conversion of the 4-piece endgame files damcpr4.zip is available.
Alternately, you can download the following 3- and 4-piece ready-to-use zip archives here: damend3.zip (145 kB) plus damend4.zip (7.7 MB).

Starting with version 2.2 v.5, DAM can handle 5- and 6-piece databases. First, install DragonDraughts-0.0a.Win32.zip (93 kB). Note the new "a" version (March 31, 1999), it fixes a bug in the move generation code. It originates from Michel Grimminck's Dragon draughts program, adapted by me for Windows. Read the README.Win32 and follow the directions. It will take a week or so (5-piece) to a few months (6-piece) of full-tilt calculations on a machine that is well-provided with RAM and hard disk space.

So, if around 1999 6p generation takes a few months, i still believe 7p is not likely on a PC...

Bert

[BertTuyt]

And here from the webside of Michel:

25 March 2007, Hamel (France)
Dragon v3.0, hardware: Intel Q6700, 4 GB RAM. endgame databases: 106.000.000.000 positions
breakthrough table 410.000.000 positions
evaluation function 8.000.000 parameters

So question to Ed, when did you finish the 7p DB, based on the above text , i assume Michel had the 7p DB available March 2007 (or somehwat earlier).

Bert

[BertTuyt]

Gerard, the directory containing the .raw files has a size of 341 GigaByte.

Bert

[BertTuyt]

Rein, in 2007 you posted "next text" in this forum

but if you like I can also scan some of Stef Keetman's 1998 articles on the 7 piece endgames.

Did you ever do this, im still interested, especially from a historic perspective?

Bert

[Ed Gilbert]

Bert, I had to dig out the old usb drive that I used to back up the build files to see when they were built.

The 7pc db was started on November 11, 2006 and finished on February 21, 2007.

The incomplete 8-piece and 9-piece dbs were also built around this time.
3m1k vs. 3m1k: February 21 through March 12
3m1k vs. 4m: March 11 through March 18
4m vs. 4m: March 18
4m1k vs. 2m1k: March 5 through March 7
4m1k vs. 3m: March 8 through March 13
5m vs. 2m1k: March 13 through March 18
5m vs. 3m: March 18 through March 20
5m vs. 4m: May 24 through June 9 (first time)

4m1k vs. 4m: June 10 through August 4
5m vs. 3m1k: July 20 through September 26
5m vs. 4m: September 26 through October 18 (second time)

All these were built using 4 older 32-bit computers, ranging from the 2.4GHz P4 to an Athlon 2800. Note that the 5m vs. 4m slice was built twice. The second time a higher percentage of positions could be resolved because I then had the 9-piece dependency slices with one king.

-- Ed

[Ed Gilbert]

So, if around 1999 6p generation takes a few months, i still believe 7p is not likely on a PC...

I still think it was possible using only readily available desktop PC hardware. It took me 3 months to build and verify the 7pc db using hardware circa 2002 - 2004. If you estimate the hardware from 1999 - 2000 to be roughly 1/3 the speed of that hardware then it would have taken 9 months, or 4-1/2 months if you skipped the time consuming self-verify process.

-- Ed

[Rein Halbersma]

I have the 5 articles by Stef Keetman that Joost and Bert refer to. I tried to copy them before but forgot why I didn't finish that. Today I remembered why: the magazine's pages are very tightly bound and glued together, rendering a substantial part of each page invisible. Unless I pressed very hard on the copy machine's lid, thereby damaging the magazines. I will therefore sadly have to refrain from copying them. However, below is a timeline of what I know of endgame database computations in 10x10 international draughts.

Here are some old links from the good old days of Usenet:
http://groups.google.com/group/rec.game ... 0ecc3e65a3?
http://groups.google.com/group/rec.game ... c6d35a2876?
http://groups.google.com/group/rec.game ... d16f0013?l
http://groups.google.com/group/alt.game ... f42e835641?
http://groups.google.com/group/alt.game ... 9bf25ca7d0?

A brief chronology of 10x10 draughts endgame databases:
1989/1990: Gerard Putter and John Smeets (authors of Psi Force, participated in Mind Sports Olympiads 1989/1991) compute 3K vs 1K. Published in Het Nieuwe Damspel 1991.

May 1993: Bert van Oortmarssen (author of Bunzo) completes 4-pc dbs and 4K vs 1K. Total of 12Mb on disk. Estimates 3K1M vs 1K to take 1 week (on a 50Mhz pc with 16Mb of RAM). Published in Hoofdlijn 1993.

1993/1994: Stef Keetman is a PhD student in Maastricht. Jonathan Schaeffer is spending a sabatical there that academic year. Cross-exchange of ideas: Chinook gets tactical patterns, Truus move generator is imported into Chinook's db builder to generate all 5-pc and some 6-pc dbs (see above link for details).

December 1994: Jan Willem Hoeve (author of Damslag) writes about 3K vs 1K in "Het damspel".

July 1996: Michel Grimminck completes 5-pc dbs after learning of the earlier results of Schaeffer/Keetman. Publishes source code of db builder (date?).

June 1998: Stef Keetman completes 6-pc dbs. Complete 5-pc dbs took less than 2 days at his desktop, 6-pc dbs took less than 2 months. Estimates that university machines could easily do 7-pc dbs. Not yet enough disk space on home desktop.

September 1998-January 1999: Harm Jetten completes 6-pc dbs using Grimminck's db builder. Somewhere before this period: completion of 6-pc dbs by Michel Grimminck? Even before Stef Keetman?

February 1999-September 1999: Stef Keetman completes 5vs2 dbs (all kings, max 2 pieces for majority side).

June 2000: Stef Keetman announces that 4vs3 computations are under way. Magazine "Dammen" by Ton Sijbrands in which his series of articles were published stops shortly thereafter.

Somewhere before March 2007: Michel Grimminck completes 7-pc dbs.

November 2006-February 2007: Ed Gilbert completes 7-pc dbs. Total 30Gb on disk.

February through October 2007: Ed Gilbert builds incomplete 8 and 9 pc dbs (4x4, 5x3 and 5x4, with max. 1 king). Total 339Gb on disk.

July 2008: Gerard Taille completes the 7-pc dbs.

October 2008-July 2009: Ed Gilbert completes 4x4 and 5x3 8-pc dbs. Total 365Gb on disk. Wieger Wessellink reports an earlier computation (<2004) of the 8-pc dbs on a Dutch supercomputer.

November 2009: Bert Tuyt completes 7-pc dbs.

[BertTuyt]

Rein, thanks for this overview.
Liked to read the history of DB's.
What i still want to understand:

February 1999-September 1999: Stef Keetman completes 5vs2 dbs (all kings, max 2 pieces for majority side).

June 2000: Stef Keetman announces that 4vs3 computations are under way. Magazine "Dammen" by Ton Sijbrands in which his series of articles were published stops shortly thereafter.

You wrote 5vs2 DBs (all kings, max 2 pieces for majority side), what do you exactly mean here, which DB's were actually generated?

Is there evidence in the articles that (partly) the 4vs3 were generated?

Last but not least, based on your overvriew and insight in history (and articles), do you think Stef generated all 7p DB's (maybe with the exception of the 6vs1 ), or "only" a subset.

Bert

[BertTuyt]

Rein,

another (strange) question.
When you plot all the DB's ( 4 , 5 , 6, 7 , 8 ) with corresponding years, and you assume that this trend will continue.

What is then the expectation for the 9p and 10P, for "more or less" normal PC's (as I believe that supercomputers already have that capability).

Ed, maybe interesting if from your side you could make some comments what PC-speed (or number of cores) you need for full 9P or full 10P, with memory, HD-size, and how long it approximately would take.

Bert