Help from the 8 pieces endgame database ?

[Ed Gilbert]

I agree with you that 38-32 leads to a draw but you understood clearly that it was not my point.
The point is to understand as clearly as possible the meaning of a "db draw", an "heurestic draw" and a "sure draw".

Actually I think I misunderstood your point earlier, but now it is clear.

AFAIK damy is the only checkers program that propagates the information necessary declare a guaranteed db draw. Some engines simply return 0 for db draw scores, and some like kingsrow use special values, but every one I am aware of simply compare the score values and freely mix db scores with heuristic scores. Schaeffer had a special program that he used to solve checkers, but that was not his chinook engine, it was a separate program. For me the decision to mix values is based on my goals for the program. These are 1) to play as strong a game as possible, and 2) to be useful for the analysis of games. With these goals in mind, I don't usually add infrastructure that I think will adversely affect 1). I have not tested your scheme because I made the assumption that it would have some overhead on all searches, due to additional comparisons to compare nodes, and additional info in hashtables, and I wonder how well it could work? What is your experience using it? I am concerned about scenarios where e.g. you reach a leaf node which is 7x1 or 8x1, you have no db value, so you have to return something to indicate that this is an unproven result, and thus your pv depends on this and you don't show a db result even though it might otherwise be an obvious result. IMO if you have to be very close to the db in terms of every search path simplifying to a db result to get a db search score then this is not very useful. Do you have an example of a 12-piece or 14-piece position where you can return a guaranteed db result? As I said I haven't tried it, so I can only guess how well it works. What is your experience?

-- Ed

[TAILLE]

I agree with you that 38-32 leads to a draw but you understood clearly that it was not my point.
The point is to understand as clearly as possible the meaning of a "db draw", an "heurestic draw" and a "sure draw".

Actually I think I misunderstood your point earlier, but now it is clear.

AFAIK damy is the only checkers program that propagates the information necessary declare a guaranteed db draw. Some engines simply return 0 for db draw scores, and some like kingsrow use special values, but every one I am aware of simply compare the score values and freely mix db scores with heuristic scores. Schaeffer had a special program that he used to solve checkers, but that was not his chinook engine, it was a separate program. For me the decision to mix values is based on my goals for the program. These are 1) to play as strong a game as possible, and 2) to be useful for the analysis of games. With these goals in mind, I don't usually add infrastructure that I think will adversely affect 1). I have not tested your scheme because I made the assumption that it would have some overhead on all searches, due to additional comparisons to compare nodes, and additional info in hashtables, and I wonder how well it could work? What is your experience using it? I am concerned about scenarios where e.g. you reach a leaf node which is 7x1 or 8x1, you have no db value, so you have to return something to indicate that this is an unproven result, and thus your pv depends on this and you don't show a db result even though it might otherwise be an obvious result. IMO if you have to be very close to the db in terms of every search path simplifying to a db result to get a db search score then this is not very useful. Do you have an example of a 12-piece or 14-piece position where you can return a guaranteed db result? As I said I haven't tried it, so I can only guess how well it works. What is your experience?

-- Ed

Of course Damy mixes "db values" and "heurestic values". Damy adds only the relevant information saying if a position is at least a draw for one or the two sides. I perfectly know that handling such information leads to an overhead but in the other hand you can see a very interesting advantage : as soon as a position in the tree is detected as a sure draw, the information is stored in the hash table and the search will stop there for all following iterations. I am not able to say if this advantage is enough compensation for the overhead. My feeling is that any mechanism designed to cut a subtree with confidence has a very good chance to be a good idea.
Another difference between Damy and Kingsrow is the following : when you detect a "db draw" at depth 15 for example I guess you continue to explore the tree at depth 16 simply with the same algorithm. In Damy I switch to a second algorithm especially designed to find or avoid a draw. There are very big differences between these two algorithms. One of them is the following : in the second algorithm the access to the 7-8 db is always allowed. The other differences are more or less a secret!
I will try give you an exemple of sure draw but I need some time to build something interesting.

[TAILLE]

Hi Ed.,

Here is very simple example of the use of the "sure draw" notion with 17 pieces on the board (9 black men against 8 white men)

Black to play

Black has a materiel advantage and looks for a win.
It is quite obvious that black has probably several winning moves and the only difficulty is to avoid a white combinaison leading to a draw. In the above position you can see that 09-14??? allows white to run a simple combinaison on 6 plies with sure draw. As soon as Damy discovers this combinaison the position after 09-14 is stored in the hash table with the information "white has at least the draw".
Now, for all the following iteration, this information will be used to avoid any move generation after the move 09-14. Without this information you will always generate the combinaison at each iteration (I know that this generation will be accelerated by the use of the best move found in the hash table but this generation on 6 plies should take place anyway).
My goal when introducing in Damy the "sure draw" notion was not to prove that a given position was really a draw. My goal was only to cut with 100% confidence a lot of branches of the tree as soon as we get near the egdb.

More generaly suppose black has an advantage in the initial position. Each time I find in the tree a position in which white has a drawing combinaison then this information is stored accordingly in the hash table in order to gain time at the next iterations. Because draughts is a highly tactical game I guess it exists many many places in the tree where black plays a bad move allowing white to find a draw by a more a less obvious combinaison.

As you can see the "sure draw" notion can easily be useful even in positions with 16 men or more.

I am not able to prove that the handling of "sure draw" is really an improvment. It is my choice and now you can understand what was my real motivation.

BTW what about the following proposal for a definition of a "db draw"
A "db draw" is detected as soon as the calculated pv ends on a draw position of the egdb (or on position repetition?)
In order to have a clear understanding of what is meant I propose to associate systematically the depth base used for the corresponding tree.
In other word I quite understand the meaning of "db draw at depth 20" but I am reluctant to use only the wording "db draw" because it sounds for the reader like a "sure draw" which implies a very different algorithm.

[Rein Halbersma]

Hi Gérard,

In your example, the db-value after 9-14? 27-22! etc. is due to a combination with purely forced moves by black. In such cases it is not difficult to propagate the "at least a db-draw" to the root. But what if black had a free move somewhere in this variation? How and how far do you propagate db-bounds? It looks a bit similar to the partial information databases. Schaeffer et al. also introduced a "partial ordering" of db-scores with a comparison table.

In any case, if you want to prove a db-draw, the easiest thing to do is to run 2 modified searches on a position. The first gives a loss to all heuristic scores, and the second a win to all heuristic scores. So the first search tries to prove a win, and the second tries to prove a loss. If you get a draw score from both, then the position is a draw. If you adapt the Chinook prove algorithm, you can even set a threshold above and below which heuristic scores are set to wins and losses, and then iterate over the threshold value. Of course, you would then also have to solve the draw-by-repetition problem.

Rein

[TAILLE]

Hi Rein,

Hi Gérard,
In your example, the db-value after 9-14? 27-22! etc. is due to a combination with purely forced moves by black. In such cases it is not difficult to propagate the "at least a db-draw" to the root. But what if black had a free move somewhere in this variation? How and how far do you propagate db-bounds?
Rein

Yes Rein my example was extremely simple in order to show clearly my intention. For your information I propagate the "at least a db draw" through all the tree.

Hi Gérard,

In any case, if you want to prove a db-draw, the easiest thing to do is to run 2 modified searches on a position. The first gives a loss to all heuristic scores, and the second a win to all heuristic scores. So the first search tries to prove a win, and the second tries to prove a loss. If you get a draw score from both, then the position is a draw. If you adapt the Chinook prove algorithm, you can even set a threshold above and below which heuristic scores are set to wins and losses, and then iterate over the threshold value. Of course, you would then also have to solve the draw-by-repetition problem.

Rein

You have to undestand that I do not try to prove a db-draw. Proving a db-draw is only a side-effect. My first goal is to be able to cut subtrees with a great confidence at the different iterations.
Nevertheless you are right. As soon as I find a "db draw at depth n" I do not continue immediatly at depth n+1 with my "standard" algorithm. As I said before I run in this case another algorithm optimised for finding/avoiding a draw and I can easily see some similarities with the Chinook prove algorithm you mentionned.

[Rein Halbersma]

Hi Rein,
Yes Rein my example was extremely simple in order to show clearly my intention. For your information I propagate the "at least a db draw" through all the tree.

Yes it was an instructive example. Nevertheless, suppose somewhere in this combination, there was a free choice move for black, with not all choices ending in a db-draw. In that case, I suppose your algorithm does not propagate the "at-least-a-draw" back to the root?

You have to undestand that I do not try to prove a db-draw. Proving a db-draw is only a side-effect. My first goal is to be able to cut subtrees with a great confidence at the different iterations.
Nevertheless you are right. As soon as I find a "db draw at depth n" I do not continue immediatly at depth n+1 with my "standard" algorithm. As I said before I run in this case another algorithm optimised for finding/avoiding a draw and I can easily see some similarities with the Chinook prove algorithm you mentionned.

In my own code, I don't re-expand nodes with exact scores by a simple hash table modification:

Code: Select all

        // TT cut-off for exact win/draw/loss scores or for deep enough heuristic scores
        const Entry* TT_entry = TT.find(p);
        if (TT_entry && (!TT_entry->is_heuristic() || TT_entry->is_sufficient(depth)) && TT_entry->is_cutoff(alpha, beta))
                return TT_entry->value();

So I ignore the stored depth for all non-heuristic scores. Whenever I encounter such a position again, I look it up and if it is a cutoff, I return immediately. Only if the new alpha-beta bounds have changed so that the stored exact score is no longer a cutoff, do I continue searching. The propagation of scores goes exactly the same as for all other scores.

In your example, the combination after 9-14 and 27-22 would results in a 5-piece database lookup, and this would propagate to the root. On the next depth iteration, 9-14 would be looked up in the hash table and the exact db score would be returned.

Rein

[TAILLE]

Hi Rein,

Yes it was an instructive example. Nevertheless, suppose somewhere in this combination, there was a free choice move for black, with not all choices ending in a db-draw. In that case, I suppose your algorithm does not propagate the "at-least-a-draw" back to the root?

Yes Rein your interpretation is correct. For each position I handle two flags :
1) The position is "at-least-a-draw-for-white"
2) The position is "at-least-a-draw-for-black"
I am pretty sure you do not need some more explanation to calculate correctly the flag of a position taking into account only the two corresponding flags of the "explored" successors.

In my own code, I don't re-expand nodes with exact scores by a simple hash table modification:

Code: Select all

        // TT cut-off for exact win/draw/loss scores or for deep enough heuristic scores
        const Entry* TT_entry = TT.find(p);
        if (TT_entry && (!TT_entry->is_heuristic() || TT_entry->is_sufficient(depth)) && TT_entry->is_cutoff(alpha, beta))
                return TT_entry->value();

So I ignore the stored depth for all non-heuristic scores. Whenever I encounter such a position again, I look it up and if it is a cutoff, I return immediately. Only if the new alpha-beta bounds have changed so that the stored exact score is no longer a cutoff, do I continue searching. The propagation of scores goes exactly the same as for all other scores.

In your example, the combination after 9-14 and 27-22 would results in a 5-piece database lookup, and this would propagate to the root. On the next depth iteration, 9-14 would be looked up in the hash table and the exact db score would be returned.
Rein

Oops I do not undertand clearly your point.
After 09-14 27-22 etc. I agree you reach a 5-piece database lookup with a draw, but that does not mean that the position after 09-14 is a "sure draw" (I mean an exact value) because 27-22 is only a cutoff move and you do not know at this time if it exists or not a winning white move or simply a white move which imply an "heuristic advantage" for white. It will be extremely time comsuming if you had to verify here if white had a better alternative instead of 27-22!
In other words, after 09-14 I am able to store in the hashtable the information "at least a draw for white" but I am not able to store an "exact value" (BTW I do not need such exact value!)

Let my add another very important point. My search algorithm looks like the MTD-f algorithm. That means that I always have to compare the value of a position to only "one" value which is quite interesting for handling my "at least a draw" flags.
With an alpha-beta procedure and a non null-window you lose a great deal of efficiency is the value "0" is somewhere between alpha and beta. I doubt it is a good idea to handle the "at least a draw" flags with an alpha-beta based algorithm.

[Rein Halbersma]

Oops I do not undertand clearly your point.
After 09-14 27-22 etc. I agree you reach a 5-piece database lookup with a draw, but that does not mean that the position after 09-14 is a "sure draw" (I mean an exact value) because 27-22 is only a cutoff move and you do not know at this time if it exists or not a winning white move or simply a white move which imply an "heuristic advantage" for white. It will be extremely time comsuming if you had to verify here if white had a better alternative instead of 27-22!
In other words, after 09-14 I am able to store in the hashtable the information "at least a draw for white" but I am not able to store an "exact value" (BTW I do not need such exact value!)

My point was that a hash table lookup that ignores depth whenever the score is not heuristic, already saves the re-expansion of moves like 9-14. For advantageous black positions such as your example, I am not interested in finding the *best* refutation of 9-14, but my only goal is to find *a* refutation and remember this in the next depth iteration. This will give the benefit of cutting positions with the 100% confidence that you described. My hash solution does that.

Note that my current hash implementation only stores a single value and the bound type. So in this example, it would store "at least a draw" (lower bound) in the position after the combination, which propagate to a "at most a draw" (upper bound) after 9-14.

The only case that I might have to re-visit the node after 9-14 would be if the [alpha, beta] window at the root changed so that the database draw would lie within that interval. For null-window searches this can never happen, and even for PVS searches this only happens in very few nodes.

Let my add another very important point. My search algorithm looks like the MTD-f algorithm. That means that I always have to compare the value of a position to only "one" value which is quite interesting for handling my "at least a draw" flags.
With an alpha-beta procedure and a non null-window you lose a great deal of efficiency is the value "0" is somewhere between alpha and beta. I doubt it is a good idea to handle the "at least a draw" flags with an alpha-beta based algorithm.

My code shows TT_entry->is_cutoff(alpha, beta) but this does not exclude the MTD-f case alpha=beta-1. I simply left both alpha and beta in the code so that I can experiment more easily with different root search algorithms. In practice, I call almost every node with a null window (especially with aspiration windows at the root).

Rein

[TAILLE]

OK Rein now I understand

Note that my current hash implementation only stores a single value and the bound type. So in this example, it would store "at least a draw" (lower bound) in the position after the combination, which propagate to a "at most a draw" (upper bound) after 9-14.

It seems this point is a difference between us because I store in the hashtable the two informations "at least a draw" and "at most a draw" where you chose to store only one of them at a time and a bound type. In fact it is totally equivalent because when the two flags "at least a draw" and "at most a draw" are set to "1" that means it is a sure draw and it corresponds in your implementation to an exact value.

Finally I do not see any relevant difference betwen us on this point. The formats of our hashtables are different but that is a very minor point isn't it?

Were you able to prove that this handling improved your program?

To answer Ed. it seems we are at least two programmers who decided to propagate the information necessary to declare a guaranteed db draw. But I repeat that this is a side effect. The main goal is to cut subtrees with 100% confidence in the following iterations.

[Rein Halbersma]

OK Rein now I understand

It seems this point is a difference between us because I store in the hashtable the two informations "at least a draw" and "at most a draw" where you chose to store only one of them at a time and a bound type. In fact it is totally equivalent because when the two flags "at least a draw" and "at most a draw" are set to "1" that means it is a sure draw and it corresponds in your implementation to an exact value.

Finally I do not see any relevant difference betwen us on this point. The formats of our hashtables are different but that is a very minor point isn't it?

Were you able to prove that this handling improved your program?

To answer Ed. it seems we are at least two programmers who decided to propagate the information necessary to declare a guaranteed db draw. But I repeat that this is a side effect. The main goal is to cut subtrees with 100% confidence in the following iterations.

I do not claim my program propagates information necessary to prove a draw. On the contrary, I freely mix heuristic score and db values in my search algorithm. The comment in my previous code fragment was in fact inaccurate: the is_heuristic() function also considers a db draw to be heuristic. So if I store a db draw in the hash table, I re-search again at the next depth. My only "optimization" is that I ignore the search depth whenever I see database win or loss score, since these results will not get more accurate when I continue searching deeper.

I have no idea what the amount of savings is. This will differ quite a lot from position to position, and I haven't tested it in an engine match yet.

Rein

[Ed Gilbert]

BTW what about the following proposal for a definition of a "db draw"
A "db draw" is detected as soon as the calculated pv ends on a draw position of the egdb (or on position repetition?)
In order to have a clear understanding of what is meant I propose to associate systematically the depth base used for the corresponding tree.
In other word I quite understand the meaning of "db draw at depth 20" but I am reluctant to use only the wording "db draw" because it sounds for the reader like a "sure draw" which implies a very different algorithm.

Gerard, you and I could probably agree on some terms for draws, but that would not solve anything, because I do not very often publish analysis of games. There are many other people that do, using kingsrow or other programs, and they will continue to do whatever they do regardless of any definition we adopt!

For my part I think I will try to use the words "sees a draw", or something like that, when kingsrow returns a db draw score *and* there are few enough pieces on the board *and* the draw persists for several successively deeper depths so that I think it is a draw with high probability of being correct.

-- Ed

[TAILLE]

Hi Ed,

BTW what about the following proposal for a definition of a "db draw"
A "db draw" is detected as soon as the calculated pv ends on a draw position of the egdb (or on position repetition?)
In order to have a clear understanding of what is meant I propose to associate systematically the depth base used for the corresponding tree.
In other word I quite understand the meaning of "db draw at depth 20" but I am reluctant to use only the wording "db draw" because it sounds for the reader like a "sure draw" which implies a very different algorithm.

Gerard, you and I could probably agree on some terms for draws, but that would not solve anything, because I do not very often publish analysis of games. There are many other people that do, using kingsrow or other programs, and they will continue to do whatever they do regardless of any definition we adopt!

For my part I think I will try to use the words "sees a draw", or something like that, when kingsrow returns a db draw score *and* there are few enough pieces on the board *and* the draw persists for several successively deeper depths so that I think it is a draw with high probability of being correct.

-- Ed

I understand Ed., wording is always a difficult matter.
As Kingrow user I appreciate the difference between an eval = 0 and an eval = +1 (or any other db draw value). In the first case that means that the pv leads to heuristic equal position and in the second case that means that the pv leads to a draw position in the egdb.
Do not try to change the wording "db draw" only because I do not like it very much! A lot of Kingrow users use this wording and in practise I guess they will never find a contradiction.
The solution is only to introduce in parallel the wording "proved draw" when you are 100% sure of the result which is the case for a position in the egdb or when when you use an appropriate algorithm for positions not very far from the egdb.
Do you accept this new wording?

[Ed Gilbert]

Gerard, yes "proven draw" is a good description.

[Ed Gilbert]

I did not have a chance to watch the games today, but I just looked at the Chizhov Boomstra game with kingsrow. Chizhov had a database win after 59. .. 6-50?, but he moved 21-16; 1-6 was the only move to continue the win. Here is the position: W:WK1,21,25,30,32,35:B14,15,19,24,K50.

-- Ed

[TAILLE]

Hi Ed.

I did not have a chance to watch the games today, but I just looked at the Chizhov Boomstra game with kingsrow. Chizhov had a database win after 59. .. 6-50?, but he moved 21-16; 1-6 was the only move to continue the win. Here is the position: W:WK1,21,25,30,32,35:B14,15,19,24,K50.

-- Ed

Black to move

BTW the move 59...06-39! is an immediat "db draw" but at the same time an immediat "proven draw".
An another move like 06-33 appears also as a "db draw" but it looks more diificult to reach the "proven draw".