An exemple of 8 pieces endgame

[Ed Gilbert]

Hi Gerard,

I have just made a small change of my evaluation function in order to improve Damy for handling the above position.

The result is the following : Damy avoids now the 15-04 move and Damy hesitates between 25-20 and 29-24.
Do you agree that these 2 moves allow white to obtain the draw ?

I studied the 15-4 move that Damy made and I am not convinced that it was the losing move. I could not find a win against it, and think the error might have been made after that. Can you post all of the moves from that game?

-- Ed

[TAILLE]

I studied the 15-4 move that Damy made and I am not convinced that it was the losing move. I could not find a win against it, and think the error might have been made after that. Can you post all of the moves from that game?

Hi Ed,
The game continued like this
15-04 11-17 15-20 (as a human I prefer 33-29) 21-43!

White to play

Damy did not see the danger to have black 35 trapped like this. My plan is rather long but seems very efficient : I intend to play first 17-21-26 in order to protect my black men. Then I intend to attack white man 33 in order to provoque the 15-20-25 white formation. Having obtained this position it is now easy to take the 04-36 diagonal in order to run the black men towards the king row.

1...11-17 2.25-20 21-43 3.04-09 43-48 4.20-15 41-05 5.09-25 17-21
6.33-29 21-26 7.25-09 48-39 8.09-04 39-50 9.35-30 50-45 10.29-24 45-12
11.04-09 12-03 12.09-18 03-14 13.18-34 14-28 14.34-18 28-39 15.30-25 39-44
16.18-13 44-11 17.13-09 11-02 18.24-20 05-46 19.09-22 02-07 20.22-04 07-23
21.04-27 23-41 22.27-36 41-47 23.36-22 47-36 24.22-33 36-09 25.33-24 26-31
and I stopped the game here

No doubt that Damy has not made the best moves but my long term "human" plan seems rather difficult to detect for a program.

Changing the evaluation function is not that easy, because in other situations, the formation b24-35 against a black king on the long diagonal may be a very efficient formation.

Gérard

[Ed Gilbert]

Hi Gerard,

Your long range strategy for winning looks sound to me. I cannot find a way to avoid the loss after 3-21 39-33 36-41 15-4. I think the fact that kingsrow played 25-20 is just luck and not because it saw any danger in allowing the man on 35 to be trapped. It evaluates 25-20 and 15-4 to almost identical scores.

I was curious to see how far away kingsrow is from actually seeing this strategy with a search, so I played out the game moves and did a 1-minute search at each one. I put the kingsrow search scores as comments in the pdn below. Kingsrow uses the convention that +scores are good for black, negative good for white, and a man is worth 100 points.

[FEN "B:WK15,25,35,39:BK3,11,16,K36."]
3-21 2. 39-33 36-41 3. 15-4
11-17 {76} 4. 25-20 {76} 21-43 {76} 5. 4-9 {78} 43-48 {78} 6. 20-15 {78} 41-5 {78} 7. 9-25 {78} 17-21 {78} 8. 33-29 {78} 21-26 {2572, black db win} 9. 25-9 {102} 48-39 {102} 10. 9-4 {80} 39-50 {102} 11. 35-30 {130} 50-45 {158} 12. 29-24 {2576} 45-12 {2572} 13. 4-9 {2578} 12-3 {2610} 14. 9-18 {2600} 3-14 {2610}

At move 8, after Damy's 33-29, kingsrow sees a database win, expecting this continuation:

8. .. 21-27 9. 35-30 27-31 10. 29-24 48-37 11. 25-9 31-36 12. 9-3 ...

But you attacked with 21-26 which leads to a longer path to the win. After that kingsrow starts to see breakthroughs with scores of 102, 130, etc. until move 12 where it finally is again able to see a database win.

-- Ed

[TAILLE]

Hi Ed.

Interesting. The endgame database is a very great advantage for the computers but the evaluation function of a human body remains far better than a computer one. Without being a very strong player I can see her a long term strategy almost impossible to detect with a program.

For the future the endgame databases will continue to be built but no doubt for me that the strength of the stronger programs will be in their evaluation function. As far as I am concerned I am working hard on it with some help from a french GMI.

Gérard

[Ed Gilbert]

For the future the endgame databases will continue to be built but no doubt for me that the strength of the stronger programs will be in their evaluation function.

I agree. Heuristics are much more important than databases, as most decisive games will be won or lost before the ending. This is even true in 8x8 checkers, where the endgame databases start having an affect on the search after only a few moves into the game.

-- Ed

[Ed Gilbert]

Concerning the 8 pieces database I do not intend to build the complete database. In any case I need to try and build a partial database and gain experience for building 9 or 10 pieces partial databases.
I can see some advantage of building a complete 5x3 database because a lot of winning positions exist with 2 kings in the weak side.
The 4x4 database is quite different because a very high pourcentage of positions with 2 kings in each side are draw positions. As a consequence it is a very good opportunity to build only a partial database, igoring all positions with at least 2 kings in each side.
Instead of handling the 6,349,390,414,625 positions of the complete 4x4 database I have only to handle 2,992,267,002,125 for a rather very powerful partial data base (at least it is my view today)

IMO building partial databases is most effective when you build them for just a small percentage of the total positions for N pieces. I think Schaeffer said something like "... it gives you 50% of the benefit for 2% of the effort." Once you start thinking about building 30% or 40% of the total positions then I think it is better to build the complete db. One reason is that building partial dbs is slower than full dbs. For my build program it is something like 40% or 50% slower, because the algorithm is more complicated and because it requires more cache memory to contain each subdb as it is being built. The partial dbs also do not compress as well. For my runlength compression they are about 50% larger than the equivalent complete dbs. Perhaps for you this is not as much of a concern because your representation using tries only stores the positions for which you know the values, where runlengths have to represent all the positions. You are thinking about building 2,992,267,002,125 positions out of a total of 6,349,390,414,625. For my build program at least, it is almost as fast to build the larger total, and then you get the benefits of having the data for all the positions.

-- Ed

[TAILLE]

I agree. Heuristics are much more important than databases, as most decisive games will be won or lost before the ending. This is even true in 8x8 checkers, where the endgame databases start having an affect on the search after only a few moves into the game.

-- Ed

Looking at the sequence :

11-17 {76} 4. 25-20 {76} 21-43 {76} 5. 4-9 {78} 43-48 {78} 6. 20-15 {78} 41-5 {78} 7. 9-25 {78} 17-21 {78} 8. 33-29 {78} 21-26 {2572, black db win}

it is clear that there is a problem with the evaluation function (it is the same with Damy) : the evaluation 76 or 78 corresponds to the black material advantage. As a human I clearly see the improvment of the black position at each move but Kingrow and Damy do not see it and they seem very surprised to discover the winning black position 5 or 6 moves later!

of course, if now I take white side and play against Damy after 15-04, Damy do not dicover the good strategy and I manage to obtain the draw.

I will try another change of my evaluation function to see if I can improve Damy moves.

Gérard

[TAILLE]

IMO building partial databases is most effective when you build them for just a small percentage of the total positions for N pieces. I think Schaeffer said something like "... it gives you 50% of the benefit for 2% of the effort." Once you start thinking about building 30% or 40% of the total positions then I think it is better to build the complete db. One reason is that building partial dbs is slower than full dbs. For my build program it is something like 40% or 50% slower, because the algorithm is more complicated and because it requires more cache memory to contain each subdb as it is being built. The partial dbs also do not compress as well. For my runlength compression they are about 50% larger than the equivalent complete dbs. Perhaps for you this is not as much of a concern because your representation using tries only stores the positions for which you know the values, where runlengths have to represent all the positions. You are thinking about building 2,992,267,002,125 positions out of a total of 6,349,390,414,625. For my build program at least, it is almost as fast to build the larger total, and then you get the benefits of having the data for all the positions.

-- Ed

Yes Ed. you are right. In any case I have to wait until I have a new powerfull computer (mid 2009 as I said).
Just a question : do you already know how many memory will you need for generating the configurations with kings only (4K against 4K or 5K against 3K) ?

Gérard

[Ed Gilbert]

Just a question : do you already know how many memory will you need for generating the configurations with kings only (4K against 4K or 5K against 3K) ?

It requires 4485mb to build 0404, and 7168mb to build 0503. I am using symmetries about the diagonal between the double corners to cut the number of positions approximately in half. There is just enough ram in my quad core to build these.

-- Ed

[TAILLE]

Just a question : do you already know how many memory will you need for generating the configurations with kings only (4K against 4K or 5K against 3K) ?

It requires 4485mb to build 0404, and 7168mb to build 0503. I am using symmetries about the diagonal between the double corners to cut the number of positions approximately in half. There is just enough ram in my quad core to build these.

-- Ed

For 5Kx3K positions my analysis is the following :
60,130,408,800 positions
By taking into consideration the symmetries along both diagonals of the board (I took them into account for building 5Kx2K and 4Kx3K positions) I can reduce the number of positions to
17,468,497,332
By using an algorithm with only 1 bit per position in memory I need only
2,183,562,167 bytes in memory

Seeing your number it seems that you use only one symmetry and you use also 2 bits per positions. Is it true ?
Of course if you have enough memory, I understand perfectly that you do not have to change your approach !

For generating 7 pieces db I used 4 bits per position but it is not a big problem to reduce this to 2 or 1 bit, at least for positions with a high number of kings.

Gérard

Gérard

[Ed Gilbert]

Hi Gerard,

Yes, I am using 2 bits per position and symmetry about only 1 diagonal, which cuts the number of positions approximately in half. I know there are schemes which use less memory, and that it is possible to take advantage of symmetries about both diagonals, but since I have enough memory I don't need to write any new code to build the 8pc db.

-- Ed

[TAILLE]

Hi Gerard,

Yes, I am using 2 bits per position and symmetry about only 1 diagonal, which cuts the number of positions approximately in half. I know there are schemes which use less memory, and that it is possible to take advantage of symmetries about both diagonals, but since I have enough memory I don't need to write any new code to build the 8pc db.

-- Ed

Hi Ed,

I agree with you Ed.

I looked at the scheme with only one bit per position but this seems not very efficient in draughts because the capture is mandatory. As a consequence when a losing position is found and you want to mark all the previous positions as winning positions you have first to verify that there are no capture in these positions. It is not a problem with 5Kx3K and 4Kx4K because the number of losing positions is very low but it could be a serious drawback in configurations where the number of losing positions is very high.
With 2 bits the problem does not occur because a position with capture is marked accordingly in memory as soon as the the preliminary phase is finished.

Of course I can run a "one bit per position" version only for 5Kx3K and 4Kx4K positions and run a "two bits per position" version for all other configurations but the solution to have 8Gb RAM seems the easiest solution to avoid multiple versions of the program.

Due to the memory needed, is it a good understanding to say that, when generating 5Kx3K and 4Kx4K, you do not use multiple cores ?

Another question Ed. My current version has 4 bits per position because I anticipated a format for building partial db. How many bits did you use for building your partial db ?

Gérard

[Ed Gilbert]

Hi Gerard,

Due to the memory needed, is it a good understanding to say that, when generating 5Kx3K and 4Kx4K, you do not use multiple cores ?

Yes, I will be giving the build program all 8gb for the 5x3 kings so no memory left to run other instances. I will have enough memory to run 2 or 3 instances when building 4x4 kings, so if I do the 5x3 kings first then I can let others run in parallel with the 4x4. After the first few days of building then all 4 cores can be kept 100% for the rest.

Another question Ed. My current version has 4 bits per position because I anticipated a format for building partial db. How many bits did you use for building your partial db ?

I use 4 bits for incomplete slices and 2 bits for complete slices. When I 'open' a subdb for read/write access I pass it an argument so that it knows which method to use for reading and writing the values. The program is configured right now to build 2-7 pieces as complete and 8-9 pieces as incomplete, but I can change a few entries in a table and recompile it to be 2-8 pieces complete.

-- Ed

[TAILLE]

Hi Gerard,

Yes, I will be giving the build program all 8gb for the 5x3 kings so no memory left to run other instances. I will have enough memory to run 2 or 3 instances when building 4x4 kings, so if I do the 5x3 kings first then I can let others run in parallel with the 4x4. After the first few days of building then all 4 cores can be kept 100% for the rest.

-- Ed

Hi Ed.
I do not know your algoritm but it is possible, even for 5x3 kings, to use multiple cores at least for the preliminary phase of the generation during witch (in Damy) I only look to captures.
I imagine that you will answer that it is not worthwhile and I will agree with you !
Gérard

[Ed Gilbert]

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