What to play

[Ed Gilbert]

I do not use this "db draw" notion in Damy bur I use what I could call a "clear demonstrated draw" which imply no kind of doubt on the result.
For Damy the "clear demonstrated draw" information is stored in the hashtable in order to be able to stop the tree exploration when the position is reached.
For Damy a "db draw" is simply a position evaluated to 0,000;

Can you clarify the usefulness of this "db draw" notion for Kingsrow ?

In kingsrow I use the values +1 and -1 for database draw values during the search. These values are unique because the heuristic eval will never return them. If a +1 or -1 value is propagated all the way back to the root, then I say that the search score is a db draw. The reliability of these db draw search results varies with the number of pieces on the board, and also the number of consecutive levels of iterative deepening that db draw is returned. That is why I mentioned earlier that I got a db draw search result at depth 21 and let the search continue to depth 25 to help confirm it.

How does this differ from your "clear demonstrated draw"? In order to say that a draw is guaranteed you have to insure that only endgame db results are propagated at each node. If any subtree has a dependency on a heuristic result then there is no proof. It is much more difficult to expand every subtree until you reach everywhere only positions that are in the database.

-- Ed

[FeikeBoomstra]

New problem:
From NK Cadets: Sjoerd ten Brinke - Michel Stempher



black on move. BoomstraDam didn't find the solution.

[Rein Halbersma]

New problem:
From NK Cadets: Sjoerd ten Brinke - Michel Stempher



black on move. BoomstraDam didn't find the solution.

Really? 29-33 38x29 19-24 39-33 24-30 wins immediately! Even a poor player like me sees this from the diagram... Do you perhaps immediately prune all positions where black sacrifices 1 man?

[FeikeBoomstra]

Jelle Wiersma's program is called "Sjende Blyn". What you can see with the eye is not nessesarily seen by the program.

The problem is the horizon. How far will you go through after you have lost a piece. From this position I learned the I also have to consider a move where the other party has to make a move to avoid direct loss as a forced move.

[BertTuyt]

I see a similar thing with my recent version of Damage.
Till ply 11 it plays 22-28, then it changes to 29-33.
As this goes very fast (first 10 plies in 0.05 second), this is basically no problem.

Bert

[Rein Halbersma]

Jelle Wiersma's program is called "Sjende Blyn". What you can see with the eye is not nessesarily seen by the program.

The problem is the horizon. How far will you go through after you have lost a piece. From this position I learned the I also have to consider a move where the other party has to make a move to avoid direct loss as a forced move.

I have no idea if these are good guidelines for 10x10 draughts, but the Chinook checkers program reduced the remaining search depth by 33% if it was one piece behind, and by 50% if two pieces behind. See page 10 of http://www.cs.ualberta.ca/~jonathan/Pap ... hinook.pdf

In this position, black is behind 1 piece after 2 ply in a quiescent position (no capture threats). The winning move 24-30 is on ply 5 that leaves black on a threatened capture so the quiescence search should extend it from there.

Using the guidelines from above, a hypothetical 10x10 Chinook doing a nominal search of 7 ply, would find the material imbalance after 2 ply, would then reduce the remaining 5 ply by 33% to at least 3 ply and find the non-quiescent position after 24-30 on ply 5, and extend it until the win was found.

How do your reductions work, Bert & Feike?

[FeikeBoomstra]

No reduction, and I suppose that is part of the problem. I just never thought about a variable window. I've build a kind of final state machine to decide that I (or the other site) have sacrified pieces and am (is) waiting for the final move to gain everthing back.

[Ed Gilbert]

No reduction, and I suppose that is part of the problem. I just never thought about a variable window. I've build a kind of final state machine to decide that I (or the other site) have sacrified pieces and am (is) waiting for the final move to gain everthing back.

Feike, reductions only make these sacrifices harder to find. It should find 29-33 very easily, on at most a 7 ply search. There is definitely something wrong with your search and when you fix it your engine will probably play a lot stronger.

Since this does not need to go very deep, you could probably dump the entire search tree to a logfile and trace the problem that way.

-- Ed

[FeikeBoomstra]

I did mean that I don't have a variable window, depending on the search-depth. If I remember well, my window is always 3 or 4 ply.

But my main problem is that I didn't consider the oponents move 39-33 as a forced move.
And that is a relatively easy thing to implement.

[TAILLE]

In order to say that a draw is guaranteed you have to insure that only endgame db results are propagated at each node. If any subtree has a dependency on a heuristic result then there is no proof. It is much more difficult to expand every subtree until you reach everywhere only positions that are in the database.

Yes that is exactly what I meant by "clear demonstrated draw". Every subtree should be expand in order to reach positions that are in the database. Of course that does not mean that there are no cutoff. By the way, my understanding of the draw found by Chinook for checkers is that this a draw is a "clear demonstrated draw" with this definition. Isn't it the case ?
Gérard

[Ed Gilbert]

Yes that is exactly what I meant by "clear demonstrated draw". Every subtree should be expand in order to reach positions that are in the database. Of course that does not mean that there are no cutoff. By the way, my understanding of the draw found by Chinook for checkers is that this a draw is a "clear demonstrated draw" with this definition. Isn't it the case ?

The Chinook checkers program that played in tournaments back in the '90s did not do this. A special search program was built specifically to solve the game. I am surprised that Damy does the extra work to propagate a guaranteed draw during the search. Doesn't this add additional overhead? It also seems inconsistent with mtd-best, because you can propagate this special guaranteed draw value but the value reported by the root level of the search is not exact.

-- Ed

[TAILLE]

Hi Ed,

I am surprised that Damy does the extra work to propagate a guaranteed draw during the search. Doesn't this add additional overhead? It also seems inconsistent with mtd-best, because you can propagate this special guaranteed draw value but the value reported by the root level of the search is not exact.

For me the handling of the "demonstrated draw" information itself has almost no impact on performance. When the position is not very far from the endgame db then I think I can save some time be avoiding unuseful exploration of some subtree.

I am not sure to understand the significance of the two values (+1 and -1) you use for db draw. can you clarify this point ?

The implementation in Damy seems slightly different and I need 3 values for what you call a db draw.
One value (let us say +1) means that it is a db draw in which white is 100% sure to obtain at least a draw
A second value (let us say -1) means that it is a db draw in which black is 100% sure to obtain at least a draw
A third value (let us say 0) means that the db draw is really a "demonstrated draw" i.e. white and black are both 100% sure to obtain at least the draw.
Does it help you to understand my implementation ?

[Ed Gilbert]

I am not sure to understand the significance of the two values (+1 and -1) you use for db draw. can you clarify this point ?

If I lookup a value in the endgame database, it is a draw and black to move then I return +1 to the search. If it is white to move I return -1. These scores get compared without any special handling to all other search scores during alphabeta. They are unique because the heuristic eval will never return these particular values. I use 100 as the value of a man so these scores are very close to 'even score'.

The implementation in Damy seems slightly different and I need 3 values for what you call a db draw.
One value (let us say +1) means that it is a db draw in which white is 100% sure to obtain at least a draw
A second value (let us say -1) means that it is a db draw in which black is 100% sure to obtain at least a draw
A third value (let us say 0) means that the db draw is really a "demonstrated draw" i.e. white and black are both 100% sure to obtain at least the draw.

I understand, but you have to do some extra comparisons everywhere you compare search scores. You have to check if the first value is one of these 3 special values, and then if the other value is one of these 3, etc. Not a big deal but it must be a noticeable overhead, and it contributes nothing to the primary task of finding the best move. It would perhaps be useful info for endgame analysis if you have exact scores returned by the search, but with MTD-best search you don't have that, so that is why I was surprised. Do you see what I mean? You gave up exact search scores for a few percent speed increase with MTD-best, but then you gave back some speed to have guaranteed db draw search scores propagated to the root, but with MTD-best you don't know what the exact score is, that's why it seems inconsistent to me.

I can see where propagating those 3 special search score values can be useful for analysis, but it does have a small overhead. I am not aware of any other checkers programs that do this.

-- Ed

[TAILLE]

I understand, but you have to do some extra comparisons everywhere you compare search scores. You have to check if the first value is one of these 3 special values, and then if the other value is one of these 3, etc. Not a big deal but it must be a noticeable overhead, and it contributes nothing to the primary task of finding the best move. It would perhaps be useful info for endgame analysis if you have exact scores returned by the search, but with MTD-best search you don't have that, so that is why I was surprised. Do you see what I mean? You gave up exact search scores for a few percent speed increase with MTD-best, but then you gave back some speed to have guaranteed db draw search scores propagated to the root, but with MTD-best you don't know what the exact score is, that's why it seems inconsistent to me.

I can see where propagating those 3 special search score values can be useful for analysis, but it does have a small overhead. I am not aware of any other checkers programs that do this.

Yes this propagation cost some extra comparison but the gain may be important in the endgame.

Let's take an example :
The following position appears in the Valneris-Schaik game (R9 la Haye)

Black to play

After 1..29-33 2.38x29 26-31 3.37x26 13-19 4.23x14 03-09 5.14x03 12-17 6.03x21 18-22 7.27x18 16x17 we reach a draw position in the 7 pieces endgame database.
As a consequence the position reached after 1..29-33 2.38x29 26-31 3.37x26 is marked as a sure draw for black.
Where is the gain? It appears here that the initial black position seemed a little difficult for black. That means that the test value used by the MTD-best procedure may be something like -0,100 (for black point of view). In that case at the next generation of the MTD-best procedure (depth++) Damy will know that 1..29-33 2.38x29 26-31 3.37x26 leads to a sure cutoff without generating the subtree. That means that Damy will only explore the 1..29-33 2.38x29 26-31 3.27x36 variant in order to know if this variant is better or not than -0,100.
You see that the initial position is what you call a "db draw" but you cannot escape to generate all the subtrees is you are not 100% sure of the draw.
To summarise : I have a gain as soon as I detect a defense that leads to a sure draw.
Of course the example is very simple and any program with the 7 pieces endgame database will play 1.29-33. But if you take now the game some moves earlier then such gain might be very interesting.
Gérard

[Rein Halbersma]

Yes this propagation cost some extra comparison but the gain may be important in the endgame.

Let's take an example :
The following position appears in the Valneris-Schaik game (R9 la Haye)

Black to play

After 1..29-33 2.38x29 26-31 3.37x26 13-19 4.23x14 03-09 5.14x03 12-17 6.03x21 18-22 7.27x18 16x17 we reach a draw position in the 7 pieces endgame database.
As a consequence the position reached after 1..29-33 2.38x29 26-31 3.37x26 is marked as a sure draw for black.
Where is the gain? It appears here that the initial black position seemed a little difficult for black. That means that the test value used by the MTD-best procedure may be something like -0,100 (for black point of view). In that case at the next generation of the MTD-best procedure (depth++) Damy will know that 1..29-33 2.38x29 26-31 3.37x26 leads to a sure cutoff without generating the subtree. That means that Damy will only explore the 1..29-33 2.38x29 26-31 3.27x36 variant in order to know if this variant is better or not than -0,100.
You see that the initial position is what you call a "db draw" but you cannot escape to generate all the subtrees is you are not 100% sure of the draw.
To summarise : I have a gain as soon as I detect a defense that leads to a sure draw.
Of course the example is very simple and any program with the 7 pieces endgame database will play 1.29-33. But if you take now the game some moves earlier then such gain might be very interesting.
Gérard

Nice example, Gérard. But what about the white perspective?
The exact draw is both a lower and an upper bound for white on move 3. Playing 3.37x26 gives at most a draw and at least a draw. For white, it appears that 3.27x36 might be better (+0,100). But should he play it? What if he is behind in time? Or what if the value had been +0,500 after a 19-ply search but dropped slowly to +0,100 after a 23-ply search? Does your program decide to go for the safe draw or does it risk playing the uncertain move that could lead to a win, draw or loss?

Normally it should be safe enough to play the move that gives the highest heuristic score. But in volatile, risky positions (fluctuating scores as the search progresses) or in risky circumstances (time disadvantage, needing a single point to win a tournament) it might be better to go for the exact score.

And if the game actually reaches the position after 2...26-31, white really as a nice advantage. It's the same as if you received a draw offer from your opponent. White can search "for free" as long as it has time or until it finds something that looks promising, or else a draw can be accepted by playing 3.37x26.

Rein