Search Algorithm

[TAILLE]

Another question: How effective is repetition detection in draughts to diminish the size of the tree during endgames, any figures known?

In Scan the effect is tiny; it's only a couple of Elo points at most, so it wouldn't fit well with your minimal design. That being said, endgame tables (6 pieces) are worth only 10 Elo or so ; that might be unusual or surprising.

Hi Fabien,

It seems you consider a large egdb (7 or 8p db) not that worthy which is very surprising for me.
My experience is the following: with the 6p db you can quite often resolve a 8x8 position within 10' and this is my definition for deciding we have entered the endgame phase.
With the 8p db the endgame phase now may begin with 9x9 positions witch makes a great difference doesn't it?
Let me give you an example chosen for you Fabien:

Computer Olympiade Leiden Rapid CCD 2016, Moby Dam - Scan, position after 44.40-34

Black to play

Scan, certainly the best program in the middle game phase, has played a very powerful middle game and Scan reached here a very advantageous position. Unfortunetly Scan has only the 6p db and, taking my definition, Scan is still in the middle game and has to continue to use is strong eval middle game function and play 44.13-19 ... draw
On the other hand Damy has the 8p db and Damy will be there in its endgame phase. As expected Damy is able to resolve the position and find the winning move 24-30!!

My conclusion: I encourage Fabien to not developpe the 8p db otherwise the other programs will have no chance to win a tournament

[TAILLE]

Hi Gérard,

I am not quite familiar with the wordings "depth-first search" or "best-first search" and so I am a little surprised to learn I am using depth-first search.
I suspect you refers to the "pick leaf" phase but in this phase the path I choose is always based on the move with the highest winning probablity (or the lowest loss probability). It looks for me like a "best-first search" but I do not have a clear definition of this notion.

I don't know how to explain best-first search better than the pseudo-algorithm I described. It is more general than just game-tree search and is common in AI (e.g. pathfinding); Wikipedia to the rescue:

"Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking."
https://en.m.wikipedia.org/wiki/Depth-first_search

"Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule."
https://en.m.wikipedia.org/wiki/Best-first_search

So DFS is the recursive traversal that we all use in tournament programs because it's so fast, while BFS has a much more iterative feel to it: expanded nodes can be far away from each other. If your algorithm is appropriately described by my pseudo-code (with some suitable selection of heuristics), then it's an instance of BFS. Even if you pick a leaf without searching ("best" move at every level), it's still BFS for a specific meaning of "best".

Fabien.

Fabien,

Thank you for this explanation. With this definition no doubt that my algorithm is best-first oriented.

[Joost Buijs]

Another question: How effective is repetition detection in draughts to diminish the size of the tree during endgames, any figures known?

In Scan the effect is tiny; it's only a couple of Elo points at most, so it wouldn't fit well with your minimal design. That being said, endgame tables (6 pieces) are worth only 10 Elo or so ; that might be unusual or surprising.

Hi Fabien,

It seems you consider a large egdb (7 or 8p db) not that worthy which is very surprising for me.
My experience is the following: with the 6p db you can quite often resolve a 8x8 position within 10' and this is my definition for deciding we have entered the endgame phase.
With the 8p db the endgame phase now may begin with 9x9 positions witch makes a great difference doesn't it?
Let me give you an example chosen for you Fabien:

Computer Olympiade Leiden Rapid CCD 2016, Moby Dam - Scan, position after 44.40-34

Black to play

Scan, certainly the best program in the middle game phase, has played a very powerful middle game and Scan reached here a very advantageous position. Unfortunetly Scan has only the 6p db and, taking my definition, Scan is still in the middle game and has to continue to use is strong eval middle game function and play 44.13-19 ... draw
On the other hand Damy has the 8p db and Damy will be there in its endgame phase. As expected Damy is able to resolve the position and find the winning move 24-30!!

My conclusion: I encourage Fabien to not developpe the 8p db otherwise the other programs will have no chance to win a tournament

Damy must be very smart that it can see the absolute win in this position.
Indeed after 24-30 Black wins a man in 28 ply and maybe this is winning, after 36 ply with 8p egdb from Ed enabled my program still doesn't see more than 1 man advantage.

[Rein Halbersma]

I encourage Fabien to not developpe the 8p db otherwise the other programs will have no chance to win a tournament

Modulo some tuning, it's now very straightforward to adapt the Kingsrow databases into any draughts engine (Windows and Linux), so I would be surprised if the next version of Scan doesn't have 8 pc datbases.

[BertTuyt]

Nevertheless, I think this is an impressive result from Gerard (Damy).
I need to dig into DOE (Drop-Out-Expansion), maybe this algorithm is also usefull for Endgame studies.

Bert

[TAILLE]

In Scan the effect is tiny; it's only a couple of Elo points at most, so it wouldn't fit well with your minimal design. That being said, endgame tables (6 pieces) are worth only 10 Elo or so ; that might be unusual or surprising.

Hi Fabien,

It seems you consider a large egdb (7 or 8p db) not that worthy which is very surprising for me.
My experience is the following: with the 6p db you can quite often resolve a 8x8 position within 10' and this is my definition for deciding we have entered the endgame phase.
With the 8p db the endgame phase now may begin with 9x9 positions witch makes a great difference doesn't it?
Let me give you an example chosen for you Fabien:

Computer Olympiade Leiden Rapid CCD 2016, Moby Dam - Scan, position after 44.40-34

Black to play

Scan, certainly the best program in the middle game phase, has played a very powerful middle game and Scan reached here a very advantageous position. Unfortunetly Scan has only the 6p db and, taking my definition, Scan is still in the middle game and has to continue to use is strong eval middle game function and play 44.13-19 ... draw
On the other hand Damy has the 8p db and Damy will be there in its endgame phase. As expected Damy is able to resolve the position and find the winning move 24-30!!

My conclusion: I encourage Fabien to not developpe the 8p db otherwise the other programs will have no chance to win a tournament

Damy must be very smart that it can see the absolute win in this position.
Indeed after 24-30 Black wins a man in 28 ply and maybe this is winning, after 36 ply with 8p egdb from Ed enabled my program still doesn't see more than 1 man advantage.

Hi Joost,

One of the most impressive variant is the following:
1...24-30 2.48-42 30x39 3.33x44 13-19 4.42-37 12-17 5.28x17 21x12 6.32-28 18-23 7.28-22 23-29 8.37-31 29-34 9.22-18 12x23 10.27-21 11.31x22 23-28 12.22x33 34-39 13.44-40 39x28 14.26-21 8-12 15.36-31 25-30 16.31-27 19-24 17.40-35 30-34 18.21-16 28-33 19.27-21 33-39 20.16-11 39-43 21.11-6 43-48 22.21-16 24-29 23.16-11 48-26 24.6-1 26-48 25.1x18 N+ (8p db)

[Rein Halbersma]

Let me give you an example chosen for you Fabien:

Computer Olympiade Leiden Rapid CCD 2016, Moby Dam - Scan, position after 44.40-34

Black to play

Scan, certainly the best program in the middle game phase, has played a very powerful middle game and Scan reached here a very advantageous position. Unfortunetly Scan has only the 6p db and, taking my definition, Scan is still in the middle game and has to continue to use is strong eval middle game function and play 44.13-19 ... draw
On the other hand Damy has the 8p db and Damy will be there in its endgame phase. As expected Damy is able to resolve the position and find the winning move 24-30!!

It's very impressive to find deep wins in a few minutes, where other programs struggle to prove the result. However, for tournament strength, you only need to find the right move, not its justification.

Can you show us a search output for this position, how your program is thinking?

I am curious what are the moves it considers as PV and how it evolves until the winning line. If your program is exploring other moves first before finding the win, it might be handicapped in rapid games compared to other programs that immediately try 24-30 (even though they score it only as a small advantage).

[Krzysztof Grzelak]

Gerard something wrong is with this variant. In particular movement 12-17.

[TAILLE]

Let me give you an example chosen for you Fabien:

Computer Olympiade Leiden Rapid CCD 2016, Moby Dam - Scan, position after 44.40-34

Black to play

Scan, certainly the best program in the middle game phase, has played a very powerful middle game and Scan reached here a very advantageous position. Unfortunetly Scan has only the 6p db and, taking my definition, Scan is still in the middle game and has to continue to use is strong eval middle game function and play 44.13-19 ... draw
On the other hand Damy has the 8p db and Damy will be there in its endgame phase. As expected Damy is able to resolve the position and find the winning move 24-30!!

It's very impressive to find deep wins in a few minutes, where other programs struggle to prove the result. However, for tournament strength, you only need to find the right move, not its justification.

Can you show us a search output for this position, how your program is thinking?

I am curious what are the moves it considers as PV and how it evolves until the winning line. If your program is exploring other moves first before finding the win, it might be handicapped in rapid games compared to other programs that immediately try 24-30 (even though they score it only as a small advantage).

Hi Rein,

It is rather difficult to give you all the information avalilable but at least I will do my best

after each move I write the evaluation and in parenthesis a value which is representative of the time allowed to the analyse of this move.

After 4" the result is the following
13-19 +50 (14 356)
24-30 +0 (8 104)
17-22 +0 (7 958)
25-30 -100 (151)
8-12 -100 (165)
4-9 -200 (150)
18-23 -440 (149)
etc.

After 8" the result becomes
24-30 +83 (50 074)
13-19 +35 (40 668)
17-22 +0 (36 315)
8-12 -100 (524)
4-9 -240 (498)
etc.

After 20"
24-30 +108 (133 400)
13-19 +35 (55 320)
17-22 +0 (49 240)
8-12 -145 (1 501)
25-30 -200 (1 336)
etc

After 1'
24-30 +150 (504 248)
13-19 +25 (64 198)
17-22 +0 (49 240)
25-30 -260 (4 998)
8-12 -340 (4 992)
etc

The complete win is find after 25'.

As you can see, between time 20" and time 1' Damy used more than 95% of it's time on the 24-30 move. Clearly it is for me the secret of the success.

Rein, does it answer your question?

[TAILLE]

Gerard something wrong is with this variant. In particular movement 12-17.

Obviously a notation error. Of course you must read 17-22 instead of 12-17.

[Fabien Letouzey]

This framework is something that I have been experimenting with for a while. See e.g. this old discussion viewtopic.php?f=53&t=3498&start=32. One thing I wrote there I still agree with:

This essentially replaces a nested multi-loop (depth, window, move number) and single-criterion comparison function (score), with a single-loop (move number) and multi-criterion comparison function (depth, window, score). I think it is much easier to experiment with the latter than the former (because interchanging loops is harder than adjusting a comparison function).

I agree with your view on loops and criterions, but I'm not sure whether it's easier overall. Instead I would say that it's more explicit: what we are maximising is written down somewhere. Indeed that makes experimentation more modular (single place for each concept).

The reason why I think it's not easy is that the formula to pick the next leaf to expand is ideally "global" (maximised over the whole set of leaves). That being said, some best-first search implementations use a greedy search to find a leaf: pick the most promising child at every level. But then, it becomes unclear what is really optimised.

By contrast, when we work on alpha-beta we think at the level of a single node; at least that's what I do. That simplifies reasoning at the price of losing the big picture, which is to improve the "quality" of the root move/score "efficiently" (for some definition of those terms). For example, who has a clear model of what ID + AB + LMR is doing to the tree? I don't, but it looks a lot like best-first search. However the implementation is scattered, like in OOP.

In my study of BFS, standard concepts like "searching an internal node" or "window" disappeared and were replaced by questions like: "which leaf seems the most promising to expand?", "what kind of value(s) do I back up", and sometimes "how confident am I of this node/leaf's score?". For example, bad-looking (locally inferior) moves are given a lower exploration score. This is the "continuous" analogue to alpha-beta which is a clear-cut yes/no.

I think that what you are looking for is doable but when you actually experiment with BFS, you might not even want to do it the way you propose anymore. In other words, I am suggesting that "searching an internal node" and "window" are artefacts of our thinking in terms of depth-first search. Regardless, the journey (even only reading a couple of articles) should bring some enlightement.

Fabien.

[Fabien Letouzey]

It seems you consider a large egdb (7 or 8p db) not that worthy which is very surprising for me.

Scan's design is about compromises everywhere, especially regarding development time. It's not at all about perfecting everything, but rather combining an OK-search with an OK-eval (yes, really) etc ... in a harmonious way. And without bugs, this helps too.

In the case of endgame tables, stopping at 6 was a pragmatic choice. I could build them using only RAM in a few days, and the tournament I was aiming for was fast approaching.

Regarding why not improving them later is not so clear cut, but:
- I couldn't build them using only RAM on my computer (8 GB), and adapting the construction algorithm felt like a lot of work
- Scan was strong enough for last year; there was no need for me to try to perfect every detail
- The Elo contribution of the tables is already small enough; that leaves an expectancy of ~3 Elo (guess)
- Normal draughts is plagued by the high draw rate and I don't think that long-running variant-specific computation is a good investment. I am somewhat hoping (but not holding my breath) that programmers show interest in less drawish variants, although I admit that this only postpones the inevitable.

Let me give you an example chosen for you Fabien:

Computer Olympiade Leiden Rapid CCD 2016, Moby Dam - Scan, position after 44.40-34

Black to play

Scan, certainly the best program in the middle game phase, has played a very powerful middle game and Scan reached here a very advantageous position. Unfortunetly Scan has only the 6p db and, taking my definition, Scan is still in the middle game and has to continue to use is strong eval middle game function and play 44.13-19 ... draw
On the other hand Damy has the 8p db and Damy will be there in its endgame phase. As expected Damy is able to resolve the position and find the winning move 24-30!!

This is great stuff! You seem to really have something in the domain of endgame solving. I wonder what Jaap Bus thinks of it. I'm referring here to his "End games and more" blog, so I assume that he has special interest in endgames.

However your way of advocating large tables is a bit like showing only lottery winners: what about the cases where the tables don't help or even slow down the engine?

That doesn't mean I'm opposed to it. If there is a general movement towards including Ed's tables (and tournament participants feel that it's OK), I'll follow. It's great for the user if there is only one format, and compression looks top notch!

In both cases, staying at 6 or using Ed's, for me it's more about everybody having something similar than about getting the extra 3 Elo points. For now, a lot of programs that I play in tournaments have comparable (and self made) tables.

My conclusion: I encourage Fabien to not developpe the 8p db otherwise the other programs will have no chance to win a tournament

I know you're joking but in all fairness, the current development versions of Kingsrow and Dragon are probably just as strong as Scan, if not better. I know that Kingsrow made enormous progress (was it 62% win?) last year by applying evaluation learning similar to Scan and Michel found several bugs in Dragon, which should be enough by itself. Not to mention that Joost is able to make something of comparable knowledge 10x faster than Scan.

And who knows what Bert and Harm and others will come up with? People seem motivated and for me, that is Scan's best victory that cannot be taken away.

Fabien.

[Joost Buijs]

Hi Fabien,

It seems you consider a large egdb (7 or 8p db) not that worthy which is very surprising for me.
My experience is the following: with the 6p db you can quite often resolve a 8x8 position within 10' and this is my definition for deciding we have entered the endgame phase.
With the 8p db the endgame phase now may begin with 9x9 positions witch makes a great difference doesn't it?
Let me give you an example chosen for you Fabien:

Computer Olympiade Leiden Rapid CCD 2016, Moby Dam - Scan, position after 44.40-34

Black to play

Scan, certainly the best program in the middle game phase, has played a very powerful middle game and Scan reached here a very advantageous position. Unfortunetly Scan has only the 6p db and, taking my definition, Scan is still in the middle game and has to continue to use is strong eval middle game function and play 44.13-19 ... draw
On the other hand Damy has the 8p db and Damy will be there in its endgame phase. As expected Damy is able to resolve the position and find the winning move 24-30!!

My conclusion: I encourage Fabien to not developpe the 8p db otherwise the other programs will have no chance to win a tournament

Damy must be very smart that it can see the absolute win in this position.
Indeed after 24-30 Black wins a man in 28 ply and maybe this is winning, after 36 ply with 8p egdb from Ed enabled my program still doesn't see more than 1 man advantage.

Hi Joost,

One of the most impressive variant is the following:
1...24-30 2.48-42 30x39 3.33x44 13-19 4.42-37 12-17 5.28x17 21x12 6.32-28 18-23 7.28-22 23-29 8.37-31 29-34 9.22-18 12x23 10.27-21 11.31x22 23-28 12.22x33 34-39 13.44-40 39x28 14.26-21 8-12 15.36-31 25-30 16.31-27 19-24 17.40-35 30-34 18.21-16 28-33 19.27-21 33-39 20.16-11 39-43 21.11-6 43-48 22.21-16 24-29 23.16-11 48-26 24.6-1 26-48 25.1x18 N+ (8p db)

Yes it is impressive, but it takes a long time to proof that there are no hidden refutations.

My program (without egtb) finds the same winning move in 4 seconds with the variation below, of course it only sees that it wins a disc, and I have to add that with egdb enabled it takes much longer to find this win:

24-30 48-42 30x39 33x44 25-30 42-37 17-22 28x17 21x12 32-28 18-23 28x19 13x24 37-31 24-29 27-21 16x27 31x22 29-33 22-17 12x21 26x17 33-38 17-11 38-43 11-6 43-49

Maybe the last moves in the PV are a bit uncertain because I distill them from the hash-table and don't look at the bounds.
So even without egdb there is a big chance that a program is able to win this, that Scan didn't see this has probably to do with the very short time-controls.

Joost

[Fabien Letouzey]

So even without egdb there is a big chance that a program is able to win this, that Scan didn't see this has probably to do with the very short time-controls.

Actually Scan claims that 13-19 also wins a piece (or a huge positional advantage), and for some reason it was easier to prove.

[Joost Buijs]

So even without egdb there is a big chance that a program is able to win this, that Scan didn't see this has probably to do with the very short time-controls.

Actually Scan claims that 13-19 also wins a piece (or a huge positional advantage), and for some reason it was easier to prove.

Fabien,

Indeed you are right, 13-19 also gains material, when I exclude 24-30 my program immediately sees 13-19.
There is a big chance that this position is not won after all (despite what Damy thinks), after a 36 ply search + quiescence with 8p egtb probes at the leaves my program still doesn't see an absolute win.
My search is still without pruning, probably others can look much further ahead, I don't want to spend more time on analyzing this position, maybe somebody else feels the need to do this.

Joost