db draw

[TAILLE]

Hi Ed. ... and the others

On many occasions you used the term “db draw”. What is the meaning of this term?

My point is the following:
Let’s take a position 6x5 with a man advantage evaluated to +1000. Suppose that up to depth 20 plies the evaluation of the position remains around +1000. Now suppose that at depth 21 plies the evaluation drops to +200, at depth 22 plies to +50, at depth 23 plies to +20 and at depth 24 plies to 0.
Obviously the program discovered that the PV found till depth 20 plies was not that good and we are pretty sure that a draw has been discovered in this primary PV.
In this scenario do you say that a “db draw” has been discovered? At which moment do you say that “db draw” has been found? Depth 21, 22, 23, 24 ?
May be you use the term “db draw” only when the evaluation reaches exactly 0 but it is a little strange because it depends a lot on your evaluation function. If your evaluation of a quite equal position reached after more than 20 plies is -20 instead of +10 you may find that the PV is evaluate to 0 instead of +10.
In addition, because a position witch seems equal or disadvantageous may be really a winning position it’s become difficult to define what a “db draw” is.
Finally if it is obvious that the db has been intensively used when the initial position is a 6x5 position what about a 7x6 position, a 8x7 position etc.

To summary : how can we define a “db draw” understandable for all programs ?

[Ed Gilbert]

Hi Gerard,

You are right that a draw search score does not guarantee that the position is a draw, unless you have a special searcher like the one that Schaeffer used to solve 8x8 GAYP checkers, one that takes care of the GHI problem, etc. For most purposes a proof is not needed, only a declaration with some high probability of being correct. In kingsrow I use the special search values of +/-1, 3, 5, for database draws. To declare a position is a draw, I look for the search to return one of these values on at least 4 or 5 plies of successive iterations of iterative deepening. I also look at the number of pieces at the root position -- the more pieces then the more corroborating evidence I need. I can estimate how hard the search is hitting the endgame databases by looking at the search speed. If the endgame databases are being used heavily then that increases the confidence.

When I say that kingsrow is indicating the position is a db draw, what I'm really saying is that the probability of the position being a draw is very good, at least 0.95 or so.

In engine matches, kingsrow declares a game to be drawn when the search score of 6 successive searches (6 positions, not 6 iterations of 1 position) for one side return db draw scores. In addition, there cannot be more than 16 pieces on the board.

In practice I think these heuristics work well. Draughts is such a drawish game that it is unusual for an ending position to be a win and the evaluation function of a strong program does not have any hint of it at all and returns an even score. There is almost always some material or obvious positional advantage that will cause the eval to be non-zero, and then the search will return that instead of a db draw.

-- Ed

[TAILLE]

Hi Gerard,

You are right that a draw search score does not guarantee that the position is a draw, unless you have a special searcher like the one that Schaeffer used to solve 8x8 GAYP checkers, one that takes care of the GHI problem, etc. For most purposes a proof is not needed, only a declaration with some high probability of being correct. In kingsrow I use the special search values of +/-1, 3, 5, for database draws. To declare a position is a draw, I look for the search to return one of these values on at least 4 or 5 plies of successive iterations of iterative deepening. I also look at the number of pieces at the root position -- the more pieces then the more corroborating evidence I need. I can estimate how hard the search is hitting the endgame databases by looking at the search speed. If the endgame databases are being used heavily then that increases the confidence.

When I say that kingsrow is indicating the position is a db draw, what I'm really saying is that the probability of the position being a draw is very good, at least 0.95 or so.

In engine matches, kingsrow declares a game to be drawn when the search score of 6 successive searches (6 positions, not 6 iterations of 1 position) for one side return db draw scores. In addition, there cannot be more than 16 pieces on the board.

In practice I think these heuristics work well. Draughts is such a drawish game that it is unusual for an ending position to be a win and the evaluation function of a strong program does not have any hint of it at all and returns an even score. There is almost always some material or obvious positional advantage that will cause the eval to be non-zero, and then the search will return that instead of a db draw.

-- Ed

Yes Ed. it is clear.
In Damy I worked hard to improve its capability to strictly demonstrate a draw and Damy is also able to avoid the GHI problem. Of course it remains extremely difficult to prove a position is a draw and in the majority of the cases I cannot avoid your approach saying that the draw is very likely.
For the reader it may be fair to distinguish a "true db draw" and a "quite true db draw".
Do you have a vocabulary proposal to distinguish clearly these two "db draw" ?

[Ed Gilbert]

For the reader it may be fair to distinguish a "true db draw" and a "quite true db draw".
Do you have a vocabulary proposal to distinguish clearly these two "db draw" ?

Not really. I usually say something like "kingsrow sees a db draw..." and assume that people know what that means, and for most practical purposes it's close to a guarantee.

-- Ed