EndGame Databases

[BertTuyt]

Rein, i think all programmers found this "trick" by themselves.
I already programmed the MoveGenerator around 1975 ! using the concept of Ghost fields.

Bert

[Rein Halbersma]

Another question: in chess endgames there is the notion of "reciprocal zugzwang". Essentially this means a position in which having the move is bad, for both opponents. (Opposition is the simplest form). These positions are crucial for chess endgame theory. I don't know if the same goes for checkers, but my guess is "yes". Are these positions easy to extract from your databases? You guys are sitting on multiple goldmines.

Black to play: white wins
White to play: draw

Automatically extracting such positions would give key positions in 4x2 endgames. I once had an email exchange with Michel Grimminck where he sent me some files with all Zugzwang positions in 4x2 endgames where the black men was in opposition with a white men on the board edge. Unfortunately, when moving to another job, I lost this email (I have it on CD, but Outlook versions were incompatible).

Rein

[Ed Gilbert]

I do not see the need for keeping in the database the case where there is only one way to get the win because this is precisely the case where there is no difficulty to find the next move. In some difficult situations we need the distance to the next conversion but if there is only one winning move we do not need any extra information.

That is true, these could be removed from a DTC db to get better compression. If you have data for every position in a DTC db then it becomes huge because a byte is consumed for each position. In my DTC db I only have data for positions where the depth is greater than 10 plies. There is no need to store data for positions with shallow depths because the proper move can easily be found through a search in these cases. Since the large majority of positions convert in less than 10 plies, this makes the DTC database compress very nicely. The DTC db for 7 pieces is about 1/10 the size of the WLD db. I could make them smaller still by removing positions that have only 1 move to win, but its not a big issue because the DTC db does not consume resources during a search, it is only consulted before starting a search. The primary benefit would be saving some disk space.

-- Ed

[TAILLE]

I do not see the need for keeping in the database the case where there is only one way to get the win because this is precisely the case where there is no difficulty to find the next move. In some difficult situations we need the distance to the next conversion but if there is only one winning move we do not need any extra information.

That is true, these could be removed from a DTC db to get better compression. If you have data for every position in a DTC db then it becomes huge because a byte is consumed for each position. In my DTC db I only have data for positions where the depth is greater than 10 plies. There is no need to store data for positions with shallow depths because the proper move can easily be found through a search in these cases. Since the large majority of positions convert in less than 10 plies, this makes the DTC database compress very nicely. The DTC db for 7 pieces is about 1/10 the size of the WLD db. I could make them smaller still by removing positions that have only 1 move to win, but its not a big issue because the DTC db does not consume resources during a search, it is only consulted before starting a search. The primary benefit would be saving some disk space.

-- Ed

Ed,
Why don't you store in your data base only positions where the next conversion is at exactly 10 plies, 20 plies, 30 plies etc ?
Gérard

[Ed Gilbert]

Why don't you store in your data base only positions where the next conversion is at exactly 10 plies, 20 plies, 30 plies etc ?

When I say the correct moves can be found for DTC < 10 through a search, I mean through a normal engine search using the WLD db, not a search of the DTC db. The engine search generates heuristic values for database wins and database losses that encourage the winning side to seek conversions, and the losing side to avoid conversions. But if I had to do a 10 ply search in the DTC db, it would be very slow from all the disk I/O (or else I'd have to waste a lot of valuable RAM to cache it). I have no RAM cache at all for the DTC db, because I only lookup the immediate successors of the game position and then a move can be immediately made.

-- Ed

[TAILLE]

Why don't you store in your data base only positions where the next conversion is at exactly 10 plies, 20 plies, 30 plies etc ?

When I say the correct moves can be found for DTC < 10 through a search, I mean through a normal engine search using the WLD db, not a search of the DTC db. The engine search generates heuristic values for database wins and database losses that encourage the winning side to seek conversions, and the losing side to avoid conversions. But if I had to do a 10 ply search in the DTC db, it would be very slow from all the disk I/O (or else I'd have to waste a lot of valuable RAM to cache it). I have no RAM cache at all for the DTC db, because I only lookup the immediate successors of the game position and then a move can be immediately made.

-- Ed

Ed,
Yes it is very clear.
Now I have another question. Do you need DTC db when the number of kings (white kings + black kings) is less than 4 ?
Gérard

[steenslag]

Thanks for the zugzwangs. The one from Rein Halbersma seems of high practicable value, and the one from Gérard is beautiful indeed.


1. 41-36 (9-20)
2. 32-43 (20-24)
3. 43-16 and the Taille-position is reached

Some of the sidelines are non-trivial (for me).

[Ed Gilbert]

Now I have another question. Do you need DTC db when the number of kings (white kings + black kings) is less than 4 ?

It is not as important as it is for the positions with more kings. But there are still some high DTC positions that a program might not play correctly. In the 5x2 database for example there is this one:

[FEN "W:WK5,30,49:BK9,K15,22,39."]

which has 3 kings and a DTC of 62. In the 4x3 db there is this one

[FEN "W:WK9,35,45:B1,K15,25,34."]

which has only 2 kings and a DTC of 32.

-- Ed

[TAILLE]

Now I have another question. Do you need DTC db when the number of kings (white kings + black kings) is less than 4 ?

It is not as important as it is for the positions with more kings. But there are still some high DTC positions that a program might not play correctly. In the 5x2 database for example there is this one:

[FEN "W:WK5,30,49:BK9,K15,22,39."]

which has 3 kings and a DTC of 62. In the 4x3 db there is this one

[FEN "W:WK9,35,45:B1,K15,25,34."]

which has only 2 kings and a DTC of 32.

-- Ed

A agree with you but this is not really my point.
I have the 6 pieces db but only a part of 7 pieces db. My experience of the 6 pieces db is the following : when the number of kings is less than 4 then, for a given men configuration, it takes only very few seconds to generate, during live game, the corresponding DTC db. I use this approach with Damy and I am almost sure that it will work also with 7 or more pieces.
Taking your above examples are you able to measure the necessary time to generate the 2 corresponding DTC db and confirm my approach ?
Gérard

[Ed Gilbert]

A agree with you but this is not really my point.
I have the 6 pieces db but only a part of 7 pieces db. My experience of the 6 pieces db is the following : when the number of kings is less than 4 then, for a given men configuration, it takes only very few seconds to generate, during live game, the corresponding DTC db. I use this approach with Damy and I am almost sure that it will work also with 7 or more pieces.
Taking your above examples are you able to measure the necessary time to generate the 2 corresponding DTC db and confirm my approach ?

When you say you generate the DTC db during a game, I'm not sure what you are doing. Does that mean that you can do a normal engine search and see far enough ahead to see the next capture or man move, and thus make the correct move? I capture the DTC information while I am building the WLD db, and that is the only method I have to build it. I can test this later, but I'm pretty sure that I cannot search to a depth of 62 plies in just a few seconds and see the next conversion on the 5x2 position I gave.

-- Ed

[TAILLE]

A agree with you but this is not really my point.
I have the 6 pieces db but only a part of 7 pieces db. My experience of the 6 pieces db is the following : when the number of kings is less than 4 then, for a given men configuration, it takes only very few seconds to generate, during live game, the corresponding DTC db. I use this approach with Damy and I am almost sure that it will work also with 7 or more pieces.
Taking your above examples are you able to measure the necessary time to generate the 2 corresponding DTC db and confirm my approach ?

When you say you generate the DTC db during a game, I'm not sure what you are doing. Does that mean that you can do a normal engine search and see far enough ahead to see the next capture or man move, and thus make the correct move? I capture the DTC information while I am building the WLD db, and that is the only method I have to build it. I can test this later, but I'm pretty sure that I cannot search to a depth of 62 plies in just a few seconds and see the next conversion on the 5x2 position I gave.

-- Ed

No Ed I am not using the normal engine when in end game with 6 pieces or less on the board. Clearly I agree that it is not possible to find a conversion that need a lot of plies.
I really generate a small DTC db corresponding to the specific men configuration of the live game. In other words I begin a db generation process by generationg all possibles positions with the kings with a classical iterative process to build this DTC db.
With 3 kings the number of position is less than 62500 and, as you know very well, the building of a DTC db of 62500 positions is not a long process !
Gérard

[Ed Gilbert]

Gerard, I understand now. I think you're right that you should be able to do this for positions with more pieces, as long as the number of kings is small. The dtc disk files for these slices with less than 4 kings are also relatively small.

-- Ed

[TAILLE]

Gerard, I understand now. I think you're right that you should be able to do this for positions with more pieces, as long as the number of kings is small. The dtc disk files for these slices with less than 4 kings are also relatively small.

-- Ed

Couldn't it be interesting for you for 8 pieces partial information db and few kings ? You don't need DTC db at all in this case !
Gérard

[Ed Gilbert]

Couldn't it be interesting for you for 8 pieces partial information db and few kings ? You don't need DTC db at all in this case !
Gérard

Gerard, when I build incomplete databases it is usually only for positions with one king or less on each side. For these position no DTC db is needed, the heuristics I mentioned earlier work well enough.

-- Ed

[BertTuyt]

Ed, i have seen your contribution related to the famous classical positions. Impressive and interesting !
My question , you use partial information databases for 7, 8, 9 piece databases.

For 6 piece i have all possible sub-databases 155 in total around 1.49G.

From your posts i learned that you don't have (and don't need) all databases to find already some results in difficult situations.
Could you give me an overview which 7, 8, 9 sub-databases you have, their size (guess you have already mentioned it somewhere, but travel and jetlags, does not help me here) and the time needed to calculate them ( think you used 4 "normal" machines in parallel, but im not sure.

With the summer vacation ahead, i certainly will buy a new machine (only for these databases), and also will start with the magic quest into more-piece databases.

I think your work so far is a great motivation for other 10x10 Draughts programmers to start similar activities.
Maybe you should participate (when possible) in future tournaments, very interested to learn how KingsRow will perform.

Bert