8 pieces endgame database

Discussion about development of draughts in the time of computer and Internet.
Post Reply
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

8 pieces endgame database

Post by TAILLE » Thu Sep 02, 2010 15:04

Hi,

For your information I just begin to generate the 8 pieces endgame data base with my new multithread algorithm.
My very first figures are the following :
4K against 4K : 37 581 505 500 positions
losing positions without capture : 560 081
drawing positions without capture : 4 245 737 717
winning positions without capture : 30 823 865
losing positions with capture : 55 298 388
drawing positions with capture : 29 362 943 534
winning positions with capture : 3 886 141 915

For Ed : I do not know if you can verify these figures because I noted that you took into account some symmetry. In any case it will certainly be sufficient to verify the following slice (4K against 3K and a man) which is under generation.
Gérard

BertTuyt
Posts: 1331
Joined: Wed Sep 01, 2004 19:42

Re: 8 pieces endgame database

Post by BertTuyt » Thu Sep 02, 2010 23:37

Gerard,

an interesting first step of a long journey.
Do you have performance figures, such as how long did the generation of the 4k 4K DB take?
How many threads do you use (8, or 16 incl hyper threading).

Bert

Ed Gilbert
Posts: 770
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: 8 pieces endgame database

Post by Ed Gilbert » Fri Sep 03, 2010 01:11

Gerard, I can confirm that your numbers sans captures are correct. And you are right that I built this slice using symmetry about one of the diagonals, and the counts generated from the original build are different. But I also re-index the data into a format that is easier to handle for kingsrow lookups, and that re-indexed data uses no symmetry tricks, so I get the same counts as you on that data.

-- Ed

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: 8 pieces endgame database

Post by TAILLE » Fri Sep 03, 2010 10:01

Hi,
Good news Ed. I can continue with confidence.
To answer to Bert question I used 7 cores without hyperthreading, keeping 1 core available to be able to access in a comfortable way to the computer. Concerning memory I have 12Gb and I use during the generation about 9Gb.
4K against 4K generation was for me a very intersting challenge as programmer because you cannot store in memory the results of all positions. I had to use a disk storage and use the memory as a cache in such a way that the access to disk are reduce to the minimum.
I am happy to have eventually managed to build this generation.
It took about 13 hours to build it, without taking into account any symmetry. I know that, if I had taken into account the 2 exsiting symmetries I would probably have generated this db in about 4 hours but I would have spent very more time to build the programm. As you can see it is not worthwhile.
Gérard

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: 8 pieces endgame database

Post by TAILLE » Fri Sep 03, 2010 11:30

Hi,
Complementary performance information :
For generating the complete 7 pieces database (4x3, 5x2, 6x1) I needed 5,6 days.
BTW I will be happy to compare my 6x1 figures with yours if you have them.
Gérard

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: 8 pieces endgame database

Post by MichelG » Fri Sep 03, 2010 20:52

Good luck to you Gerard!

I'll race you :-), I just started the same computation last week with the computation of 5v3 on a quadcore q6700, and in a couple of days my other computer will join in with 6 cores on 4v4.

It's a bit difficult to compare my database builder to yours, since I don't know how much time it took for the 7 piece endings.

But i estimate it would be about 3 days on 6 cores. 5Kv3K took about 6.2 hours. As you, i don't exploit the symmetries.

Why don't you use all the cores in your system? I use all 12 on my system. If the computer slows down, it is mostly because of the hard-disk access and huge memory use. I also have a 'pause' button so that i can use my computer normally when i need it.

Stats until now:

Code: Select all

Non-capture
DB     Win             Draw                Lose                    Win           Draw             Lose
0404       30.823.865    4.245.737.717          560.081   0404       30.823.865    4.245.737.717          560.081 
1304      109.951.875   21.450.905.536       57.739.438   0413      548.631.694   13.794.024.089          257.207 
1313    1.905.191.192   71.565.238.320       58.503.429   1313    1.905.191.192   71.565.238.320       58.503.429 
2204      125.521.931   39.917.605.934    1.046.702.123   0422    2.892.283.317   15.045.959.691           36.546 

0503      704.925.456    3.560.143.014                0   0305        3.281.314    3.196.650.674      417.551.618 
0512    8.273.581.968    2.181.353.594                0   1205       10.284.244    7.293.125.775    8.055.044.119 
0521    8.415.019.196       66.685.206                0   2105        7.142.747    4.600.829.936   17.204.584.803 
0530    2.276.443.113           54.807                0   3005          879.372      533.378.154    9.830.307.636 
1403    3.183.280.592   21.081.806.976                1   0314       58.934.290   14.406.335.089    1.041.842.747 

All
0404    3.916.965.780   33.608.681.251       55.858.469   0404    3.916.965.780   33.608.681.251       55.858.469 
1304   10.075.690.738  124.282.093.375      935.635.687   0413   30.076.181.317  105.093.200.110      124.038.373 
1313   80.587.901.533  404.430.429.608    2.160.695.259   1313   80.587.901.533  404.430.429.608    2.160.695.259 
2204    8.710.678.358  167.741.575.565    5.779.699.277   0422   79.922.300.425  102.218.929.773       90.723.002 

0503   17.229.615.878   12.829.002.132        6.586.390   0305      339.953.720   27.805.830.388    1.919.420.292 
0512   66.082.013.381   15.082.985.562       11.052.937   1205      534.976.536   60.357.137.712   20.283.937.632 
0521   68.313.484.823    4.574.803.712        4.492.745   2105      214.808.099   28.192.355.922   44.485.617.259 
0530   21.718.714.925       47.855.119           24.366   3005        2.007.953    1.271.028.889   20.493.557.568 
1403   66.486.418.486   68.684.445.125      122.556.189   0314    3.439.336.510  125.702.283.377    6.151.799.913 

Michel
Last edited by MichelG on Mon Sep 13, 2010 22:46, edited 6 times in total.

64_bit_checkers_engine
Posts: 62
Joined: Mon Apr 20, 2009 01:10
Contact:

Re: 8 pieces endgame database

Post by 64_bit_checkers_engine » Mon Sep 06, 2010 01:51

Well I just finished building an overclocked 5.0 GHz Intel Core i7-920. It is now perfectly stable after having run Prime95 for 3 days continuously on all cores (8 threads total).

Interestingly, it is about 1.7 times as fast as my 3.9 GHz i7-860 at running my 6-piece Distance-To-Win database in the game of 8x8 checkers. So, this would be like a 6.63 GHz i7-860!

Ed Gilbert
Posts: 770
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: 8 pieces endgame database

Post by Ed Gilbert » Mon Sep 06, 2010 02:37

0413w Win: 548.631.694 (3.8%) Draw: 13.794.024.089 (96.2%) Lose: 257.207 (0.0%)
I have the same counts.

-- Ed

ildjarn
Posts: 1490
Joined: Tue Aug 22, 2006 15:38
Real name: Joost de Heer

Re: 8 pieces endgame database

Post by ildjarn » Mon Sep 06, 2010 09:49

1403: v 3.183.280.592 (13.1%) 21.081.806.976 (86.9%) 1 (0.0%)
What is the unique losing position?
Lasst die Maschinen verhungern, Ihr Narren...
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: 8 pieces endgame database

Post by TAILLE » Mon Sep 06, 2010 10:06

Ed Gilbert wrote:
0413w Win: 548.631.694 (3.8%) Draw: 13.794.024.089 (96.2%) Lose: 257.207 (0.0%)
I have the same counts.

-- Ed
same counts also for me for this 0413w db
Gérard

Ed Gilbert
Posts: 770
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: 8 pieces endgame database

Post by Ed Gilbert » Mon Sep 06, 2010 13:07

Code: Select all

Non-capture
DB     Win             Draw                Lose                    Win           Draw             Lose
0503     704.925.456    3.560.143.014                0    0305       3.281.314    3.196.650.674      417.551.618 
0512   8.273.581.968    2.181.353.594                0    1205      10.284.244    7.293.125.775    8.055.044.119 
0521   8.415.019.196       66.685.206                0    2105       7.142.747    4.600.829.936   17.204.584.803 
0530   2.276.443.113           54.807                0    3005         879.372      533.378.154    9.830.307.636 
1403   3.183.280.592   21.081.806.976                1    0314      58.934.290   14.406.335.089    1.041.842.747 
Agree.

Ed Gilbert
Posts: 770
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: 8 pieces endgame database

Post by Ed Gilbert » Mon Sep 06, 2010 13:09

What is the unique losing position?
I'm not really set up now to find it easily. Maybe Michel or Gerard have it?

-- Ed

Rein Halbersma
Posts: 1635
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: 8 pieces endgame database

Post by Rein Halbersma » Mon Sep 06, 2010 13:53

Ed Gilbert wrote:
What is the unique losing position?
I'm not really set up now to find it easily. Maybe Michel or Gerard have it?

-- Ed
Don't post this quite yet! It's a nice little puzzle to try and solve by hand. It must involve the single man in an essential way because with 5 kings vs 3 kings there is no loss.

Rein

Rein Halbersma
Posts: 1635
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: 8 pieces endgame database

Post by Rein Halbersma » Mon Sep 06, 2010 14:31

Rein Halbersma wrote:
Ed Gilbert wrote:
What is the unique losing position?
I'm not really set up now to find it easily. Maybe Michel or Gerard have it?

-- Ed
Don't post this quite yet! It's a nice little puzzle to try and solve by hand. It must involve the single man in an essential way because with 5 kings vs 3 kings there is no loss.

Rein
Image

I think this is the position. White to move and lose. It is a black win because white can only move 2-8/13/19/24/30 and black will always capture 35x2 with no moves left for white. The proof for uniqueness is left as an exercise for the reader :-)

Ed Gilbert
Posts: 770
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: 8 pieces endgame database

Post by Ed Gilbert » Mon Sep 06, 2010 18:42

Rein Halbersma wrote:I think this is the position.
Nicely done!

Post Reply