An exemple of 8 pieces endgame

[TAILLE]

Gerard,

The approach I took to parallel db builds is to subdivide the slices up into very many pieces, and then there are usually lots of subdivisions that can be built in parallel. So rather than have multiple threads working on parts of the same subdivision, each thread works on a separate one, which minimizes the communication necessary between threads. The configurations are subdivided not only by piece counts and types, but also by rank of leading men, by the configuration of the men on the leading ranks, and by the next highest rank of leading men. This results in hundreds of thousands of subdivisions which I build separately and store in separate files. At any given time there are typically dozens of subdivisions that can be built in parallel, so the more PCs and cores the better. For example, when my daughters were home from college for summer vacations I connected their PCs to the cluster and fired up additional instances to make the db build go faster.

-- Ed

Ed.

That is what I understood. Basically a subdivision is defined by the men configuration and a subdivision is build by one core and that sounds good for me.
But you said also

I will have enough memory to run 2 or 3 instances when building 4x4 kings

Does that mean that you are also able to define subdivisions even with no men ?
Gérard

[Ed Gilbert]

But you said also

I will have enough memory to run 2 or 3 instances when building 4x4 kings

Does that mean that you are also able to define subdivisions even with no men ?

No, but since the 5x3 kings will be done I can start building subdivisions that have men along that dependency branch.

-- Ed

[TAILLE]

No, but since the 5x3 kings will be done I can start building subdivisions that have men along that dependency branch.

-- Ed

Thank you Ed; That is very clear now.
Gérard

[Ed Gilbert]

Hi Gerard,

I started building the full 8pc database. 4k-4k and 5k-3k are finished, as are some of 4k-3k1m and 5k-2k1m.

Of course all the 4k-4k non-capture positions are draws with the exception of some shots. In 5k-3k there are some win positions that take 48 plies before converting to a smaller number of kings.

Here is a position which kingsrow does not play correctly without the 8pc db. Black to play and win, but if using only the 7pc db kingsrow plays a draw move.

B:WK5,K48,K49:BK6,K12,K17,K41,K46.

Does Damy have any heuristics which help here? There are 2 black moves that win, and a conversion is 41 plies later.

-- Ed

[TAILLE]

Hi Gerard,

I started building the full 8pc database. 4k-4k and 5k-3k are finished, as are some of 4k-3k1m and 5k-2k1m.

Of course all the 4k-4k non-capture positions are draws with the exception of some shots. In 5k-3k there are some win positions that take 48 plies before converting to a smaller number of kings.

Here is a position which kingsrow does not play correctly without the 8pc db. Black to play and win, but if using only the 7pc db kingsrow plays a draw move.

B:WK5,K48,K49:BK6,K12,K17,K41,K46.

Does Damy have any heuristics which help here? There are 2 black moves that win, and a conversion is 41 plies later.

-- Ed

Hi Ed,

The beginning of the 8 pieces db calculation is a good news in the sense that it is a new motivation for me to continue. As I told you I will begin that job mid 2009 with a more powerful PC.

Of course Damy cannot solve your problem. How could I work on such heuristic for solving such very unuseful (in practise) position ? The usefulness is of course only to build the other 5x3 db.

Just two questions Ed :
1) Do you generate also the corresponding DTC table ?
2) Is Kingsrow able to reach the first conversion without using the DTC table ?

Gérard

[Ed Gilbert]

Hi Gerard,

As I told you I will begin that job mid 2009 with a more powerful PC.

What sort of computer do you plan to use? One computer with multiple cores, or something else? Right now I don't yet have a good estimate on how long this is going to take, but I suspect over a year, and possibly close to 2 years on the present machine. If it starts looking like much longer than 1 year then I will think about replacing the quad core cpu with one of the newer versions that has a faster clock and more cache.

Of course Damy cannot solve your problem. How could I work on such heuristic for solving such very unuseful (in practise) position ? The usefulness is of course only to build the other 5x3 db.

Not that you would have heuristics specifically for all-kings, but I was wondering if damy gave different scores to the winning moves than the others. 17-11 and 12-7 are the two moves that win. Kingsrow played 17-50. Does Damy give the same scores for each of these 3 moves? I thought it possible that you had some general heuristics that might apply.

1) Do you generate also the corresponding DTC table ?

Yes, I always save the DTC info as it is generated during the WLD build.

2) Is Kingsrow able to reach the first conversion without using the DTC table ?

That's an interesting question. I set up 2 instances of kingsrow, one using the 8pc mtc db to play the white losing side, and the other using only the 8pc wld db to play the winning side. The instance that played black was able to force the conversion, and only played a non-optimal move once. This surprised me, because the conversion was well beyond the search horizon for most of these moves and I didn't think I had any heuristics to help this, but maybe I'm forgetting something. In 8x8 checkers there are some simple concepts which help drive toward conversions, and I may have left some of those in the code when I built the 10x10 version. I did not intend to, because I didn't think those 8x8 heuristics were applicable with flying kings. They have to do with king mobility and control of the center.

Here is the game that was played:

[White "kingsrow with 8pc wld + mtc"]
[Black "kingsrow with 8pc wld"]
[FEN "B:WK5,K48,K49:BK6,K12,K17,K41,K46."]
12-7 {17-11 is best at mtc 41, 12-7 is not optimal at 45} 2. 48-26 7-12 3. 26-48 17-11 {this is best. 12-7 also wins} 4. 48-26 12-18 {3 moves win, this is one of 2 best} 5. 49-16 11-50 6. 26-3 18-36 7. 3-25 6-44 {4 moves win, this is one of 2 best} 8. 16-49 44-35 {2 win, this is best} 9. 49-16 35-49 {6 win, this is one of 4 best} 10. 16-2 36-4 {6 moves win, this is one of 4 best} 11. 2-35 4-15 {5 moves win, this is one of 3 best} 12. 35-2 50-45 {7 moves win, this is only one that is best} 13. 25-3 49-35 14. 2-16 15-29 15. 3-26 35-49 16. 16-2 29-20 17. 26-31 20-38 18. 31-4 38-47 19. 4-31 49-35 20. 31-36 45-50 21. 2-16 50-44 22. 16-49 44-11 23. 5-10 41x5 24. 49-21 5-37 25. 21-43

-- Ed

[BertTuyt]

Ed/Gerard,

also on my list things to do, is to buy another computer in 2009.
Most likely in will be a computer with the new Intel Nehalem processor (most likely the one i can afford is around 2.9 Ghz.).
This processor has also 4 cores, but on one chip.
Also very useful is that all/many related motherboards have a 12 GByte Memory Possibility ( 6 slots as the processor has a triple memory channel).

Bert

[Ed Gilbert]

Bert,

I was also looking at this motherboard: http://www.newegg.com/Product/Product.a ... %20X7DCA-L It supports two quad core processors and up to 48gb of ram, although I think 16gb would be more than adequate with 8 cores for building dbs. I build my own PCs, and this one looks attractive because it fits in a small form factor case, unlike most server motherboards which are huge.

-- Ed

[TAILLE]

Hi Ed/Bert,

What sort of computer do you plan to use? One computer with multiple cores, or something else?

For the time being I do not know yet what kind of computer I will use. At the minimum it will have a quad and 8Gb. I am not sure that a more powerful machine would be a good idea comparing with two machines with the above configuration. Another possible solution could be also to buy an access on a very powerfull machine in order to generate more quickly this 8 pieces db but I suspect it is a too expansive solution.

Does Damy give the same scores for each of these 3 moves?

Yes the score corresponds to the default value of 5K against 3K (in that case only 0.2 because the advantage is rather small !)

Yes, I always save the DTC info as it is generated during the WLD build.

For Damy it is a different process because I generate the DTC table only with more than 5 kings on the board. Don't you think that you can save some time by avoiding generation DTC table ?
In addition, you could also decide to not use these DTC tables (for 6 kings or more) during a real tournament because there are almost no chance to reach such position and the corresponding next conversion before the 75th move.

Gérard

[Ed Gilbert]

Hi Gerard,

For Damy it is a different process because I generate the DTC table only with more than 5 kings on the board. Don't you think that you can save some time by avoiding generation DTC table ?

My WLD build process is first a single pass where I resolve captures and other conversion moves, and then a series of non-conversion passes. On each Nth non-conversion pass, positions with DTC value N get resolved. Since I have already identified these positions as part of building the WLD db, it is very little extra work to write these positions to a database. It adds very little to the total build time.

In addition, you could also decide to not use these DTC tables (for 6 kings or more) during a real tournament because there are almost no chance to reach such position and the corresponding next conversion before the 75th move.

Using them does not cost anything except a little disk space. They use no appreciable ram, because they are not used during the search. The MTC database is queried before a search starts, and if the position is found then a move can be made immediately. Looking up a position takes only a few milliseconds. I agree they're not likely to get used during a computer draughts tournament. I like to build these MTC databases mainly because I find the intricacy of the solutions to be interesting.

-- Ed