ENGINE SPEED AND STRONG

[Joost Buijs]

Hi Gérard,

That you are able to find the win in this position within 25 seconds is amazing, this is very fast, in a second run my program took ~7 minutes to find the win (the time varies due to SMP), the variation to the won 8p EGDB position is 45 ply long and starts with: 37-31 12-17 22x11 16x07 27-21 10-14 21-16 14-19.

It is possible that there are undiscovered wins when you don't use EGDB, but when I have my program play with or without EGDB the match scores don't change in a significant way, this is what I look at. Maybe my implementation is wrong, but I don't think so because with test-positions it all works fine but with game-play it does not seem to help much.

The point is that without EGDB my program finds after 12 seconds that 37-31 is the best move and with EGDB enabled it takes 26 seconds before it sees that 37-31 is the best move, this is due to the slowdown caused by probing and this can have an adversary effect during game-play.

Usually the errors are made earlier on in the game, for instance the position you show above is already very bad for black and that should not happen when your evaluation and search during the opening and midgame are working like they should.

Joost

Damy do not give me the longest variant but it seems to me that 45 plies is quite high. Could we try to find the best PV?
After 37-31 12-17 22x11 16x07 27-21 10-14 21-16 14-19 Damy continue with 29-23 19-24 23-19 24x13 28-22 15-20 22-17 20-24 17-11 7-12 11-6 24-29 31-26
do you agree up to this point?

Gérard,

My program subtracts the ply-depth from the win-value and it adjusts the win-value (depending upon ply-depth) storing and loading it from the transposition-table (just like mate values in chess), I'm pretty sure that the 45 ply is correct with maybe an error of 1 ply but of course there can be bugs. My program shows an 8 ply variation only but I can increase the length of the PV it prints, I will try to get a longer variation out of it later today. It doesn't store the PV in quiescence so I'm not able to see the whole PV to the end.

Joost

Edit:

I did another run with a much larger hash-table and now it finds a win in 43 ply, I guess that this is caused by pruning I disable probcut when there are win values in the tree but LMR is still active, this is something I have to look at. Anyway the variation it gives is:

37-31 12-17 22x11 16x07 27-21 10-14 21-16 14-19 29-23 19-24 23-19 24x13 28-22 15-20 22-17 20-25 17-11 07-12 11-06
25-30 31-26 30-35 06-01 13-18 01-06 40-45 06-33 18-23 33-38 12-18 16-11 18-22 11-06 09-14 06-01 23-28 01-06 14-20
38x15 22-27 06x33 27-31 26x37

Joost

[Joost Buijs]

This is the essential Killer endgame: white to move plays 25-14 and black has to capture 46x10 (stopping immediately behind the white king) and white wins 15x4. This means that almost every two versus one endgame is won for the majority side. Still, I expect the drawing rate to be 50% for top programs, perhaps similar to chess. Michel Grimminck's Dragon program has computed 6 piece endgames for it, stats are here: https://mdgsoft.home.xs4all.nl/draughts ... index.html

Since it is a very simple modification I will add it to my engine as well, and maybe (who knows) there will be some interest in this variation in the future. A drawing rate of 50% is a lot more interesting than a drawing rate of >95 %.

Joost

[TAILLE]

I did another run with a much larger hash-table and now it finds a win in 43 ply, I guess that this is caused by pruning I disable probcut when there are win values in the tree but LMR is still active, this is something I have to look at. Anyway the variation it gives is:

37-31 12-17 22x11 16x07 27-21 10-14 21-16 14-19 29-23 19-24 23-19 24x13 28-22 15-20 22-17 20-25 17-11 07-12 11-06
25-30 31-26 30-35 06-01 13-18 01-06 40-45 06-33 18-23 33-38 12-18 16-11 18-22 11-06 09-14 06-01 23-28 01-06 14-20
38x15 22-27 06x33 27-31 26x37

Joost

Hi Joost,

3 points concerning your PV
1) After 37-31 12-17 22x11 16x07 27-21 10-14 21-16 14-19 29-23 19-24 23-19 24x13 28-22 15-20 22-17 20-25 17-11 07-12 11-06
25-30 31-26 30-35 06-01 13-18 01-06 40-45 06-33 18-23 Damy choses 16-11 which looks more logical and efficient
2) After your choice 33-38 12-18 16-11 18-22 the move 11-7 seems also better and more logical than 11-06
3) After 37-31 12-17 22x11 16x07 27-21 10-14 21-16 14-19 29-23 19-24 23-19 24x13 28-22 15-20 22-17 20-25 17-11 07-12 11-06
25-30 31-26 30-35 06-01 13-18 01-06 40-45 06-33 18-23 33-38 12-18 16-11 18-22 11-06 09-14 06-01 23-28 01-06 14-20
38x15 don't you have already reached the 8 pieces db?

Anyway, because your program is able to find quickly the best move you don't need to improve your search.

Let me propose you another test, very very near the 8 pieces db!


White to play and win

[TAILLE]

This is the essential Killer endgame: white to move plays 25-14 and black has to capture 46x10 (stopping immediately behind the white king) and white wins 15x4. This means that almost every two versus one endgame is won for the majority side. Still, I expect the drawing rate to be 50% for top programs, perhaps similar to chess. Michel Grimminck's Dragon program has computed 6 piece endgames for it, stats are here: https://mdgsoft.home.xs4all.nl/draughts ... index.html

Since it is a very simple modification I will add it to my engine as well, and maybe (who knows) there will be some interest in this variation in the future. A drawing rate of 50% is a lot more interesting than a drawing rate of >95 %.

Joost

Hi,

A number of possibilities exist in order to limit the number of draws. The most known is the advantageous draw.
In addition it is quite easy to suppress completly the draws for example with the following rules
1) The side with a material advantage wins (1 king = 2 men)
2) With material equality the side with more kings wins
3) With the same number of kings and men the side who gets first a definitive king position wins (in order to emphasis agressive play)

Of course in any case limiting or suppressing the draws leads to some rule changes and as a consequence leads to a strategy change, and the majority of players do not want to change the game do they?

[Joost Buijs]

Hi Joost,

3 points concerning your PV
1) After 37-31 12-17 22x11 16x07 27-21 10-14 21-16 14-19 29-23 19-24 23-19 24x13 28-22 15-20 22-17 20-25 17-11 07-12 11-06
25-30 31-26 30-35 06-01 13-18 01-06 40-45 06-33 18-23 Damy choses 16-11 which looks more logical and efficient
2) After your choice 33-38 12-18 16-11 18-22 the move 11-7 seems also better and more logical than 11-06
3) After 37-31 12-17 22x11 16x07 27-21 10-14 21-16 14-19 29-23 19-24 23-19 24x13 28-22 15-20 22-17 20-25 17-11 07-12 11-06
25-30 31-26 30-35 06-01 13-18 01-06 40-45 06-33 18-23 33-38 12-18 16-11 18-22 11-06 09-14 06-01 23-28 01-06 14-20
38x15 don't you have already reached the 8 pieces db?

Yes, of course you are right. I didn't look at the PV myself, after my program found the win I let it iterate somewhat deeper and that is when it added the moves 22-27 06x33 27-31 26x37, actually this should not happen at all, my guess is that it has something to do with the EGDB only containing positions without captures (for both sides), on nodes with captures there is no EGDB information available.

Now that I think about it, it is possible that my program doesn't always find the shortest win, my idea about this is that this is caused by LMR because moves that will lead to a shorter win are sometimes searched less deeply, in combination with the transposition-table it is very difficult to comprehend what actually happens, this is an interesting phenomenon I want to examine further, maybe this problem is difficult to solve when you use LMR.

The next thing I want to try is what happens when I disable LMR on nodes with win or loss values, for the midgame this will have no influence, but maybe it will make the endgame more accurate.

For me it is very difficult to understand what the influence of all variables is, incomplete EGDB, pruning in quiescence, pruning repetitions, probcut and LMR, all of these in combination with the transposition-table, my transposition-table is not write always but it preserves entries with the highest draft because this gives me the best results.

Joost

[Joost Buijs]

Let me propose you another test, very very near the 8 pieces db!


White to play and win

This one my program finds in 4 seconds with PV:

41-37 12-18 37-32 15-20 32-27 11-17 45-40 17-22 27-21 18-23 40-35 23-28 43-38
14-19 44-39 19-24 42-37 20-25 37-31 24-29 39-34 29x40 35x44

[TAILLE]

Let me propose you another test, very very near the 8 pieces db!


White to play and win

This one my program finds in 4 seconds with PV:

41-37 12-18 37-32 15-20 32-27 11-17 45-40 17-22 27-21 18-23 40-35 23-28 43-38
14-19 44-39 19-24 42-37 20-25 37-31 24-29 39-34 29x40 35x44

Interesting, this time Damy is less efficient.
After 41-37 12-18 37-32 15-20 32-27 11-17 45-40 17-22 27-21 18-23 Damy prefers 21-16 but your choice 43-38! is better. Clearly it is due to my eval function on which I have still a lot of work to do!

Thank you for your answer.

Do you have some endgame positions on which you would like to compare our programs?

[Joost Buijs]

Do you have some endgame positions on which you would like to compare our programs?

Unfortunately I don't have endgame positions at the moment, when I find some interesting positions on the internet I will keep them and post them here.

[Sidiki]

Hi,

The current discussion looks a little strange for me. Comparing the strength due to eval function vs EGDB is a non-sense because these are not built for the same kind of positions. The eval function is build in order to play the beginning and the middle game (typically the 45 first moves) and the EGDB is build for playing the endgame (typically after the 45th move).
My view is the following: draugths is clearly a drawing game. Of course if a program A has a far better evaluation function than program B, it will win the game in the beginning and middle game and the EGDB is of no use but this case is not very interesting is it?
The most interesting situation is the following: program A eval function is a LITTLE better than program B eval function and, as a consequence, program A reaches quite often the endgame with a clear advantage but not a clear win! Now the EGDB becomes the key point: if program A has the best EGDB it will win many of these games but if program B has the best EGDB it will manage to draw a lot of these.

Hi, Taille and the others programmers,

I don't know if there are different level of EGDB, what can be for example the difference between Damy 7 EGDB and Kingsrow's or Damge's.
I thought that it was a convention, the same number of position Win/Draw/Loss.
I don't understand what Taille said.

Thanks
Sidiki

[Joost Buijs]

Hi,

The current discussion looks a little strange for me. Comparing the strength due to eval function vs EGDB is a non-sense because these are not built for the same kind of positions. The eval function is build in order to play the beginning and the middle game (typically the 45 first moves) and the EGDB is build for playing the endgame (typically after the 45th move).
My view is the following: draugths is clearly a drawing game. Of course if a program A has a far better evaluation function than program B, it will win the game in the beginning and middle game and the EGDB is of no use but this case is not very interesting is it?
The most interesting situation is the following: program A eval function is a LITTLE better than program B eval function and, as a consequence, program A reaches quite often the endgame with a clear advantage but not a clear win! Now the EGDB becomes the key point: if program A has the best EGDB it will win many of these games but if program B has the best EGDB it will manage to draw a lot of these.

Hi, Taille and the others programmers,

I don't know if there are different level of EGDB, what can be for example the difference between Damy 7 EGDB and Kingsrow's or Damge's.
I thought that it was a convention, the same number of position Win/Draw/Loss.
I don't understand what Taille said.

Thanks
Sidiki

Hi Sidiki,

Gérard probably meant the number of pieces covered by the positions stored and not the quality of the EGDB.

Maybe I'm mistaken, but I guess most EGDB generators for draughts are based on the algorithm by Jonathan Shaeffer which was originally developed for checkers and later modified for 10x10. So in a sense all EGDB's (with the same piece signature) contain the same information, this doesn't has to be in the same format of course. To make it smaller Ed removed positions with captures from the Kingsrow database, I don't know if this is also the case with the other EGDB's.

I still didn't have time to add a configuration file and an easy way of playing games with my engine, with a bit of luck I can work on it tomorrow and I still hope to have something ready by the end of this week. Actually I'm thinking about making a small Windows program for it with a menu to adjust the settings and to store the parameters in the registry, this is a lot easier than fiddling with a configuration file and command-line parameters.

Joost

[Catherine]

Hi Joost,

Thank, we will be glad to try your program.
So, all the EGDB have the same positions ?
Gérard said that the engine with the best EGDB will manage easily a draw against another one with an EGDB les good. Strange.

Thank again.
Catherine

[Joost Buijs]

Hi Joost,

Thank, we will be glad to try your program.
So, all the EGDB have the same positions ?
Gérard said that the engine with the best EGDB will manage easily a draw against another one with an EGDB les good. Strange.

Thank again.
Catherine

Hi Catherine,

I think he means a program with 8P EGDB will draw easily against a program with a 7P or 6P EGDB, but only if the programs are comparable in strength, a weak program with 8P EGDB will lose most of the time from a strong program even when it plays without EGDB.

I doubt that adding an 8P EGDB will be worth more than ~30 Elo. In the past the programs were much weaker and it might be that at that time having a large EGDB was of more importance than it is right now.

Joost

[TAILLE]

Hi,

The current discussion looks a little strange for me. Comparing the strength due to eval function vs EGDB is a non-sense because these are not built for the same kind of positions. The eval function is build in order to play the beginning and the middle game (typically the 45 first moves) and the EGDB is build for playing the endgame (typically after the 45th move).
My view is the following: draugths is clearly a drawing game. Of course if a program A has a far better evaluation function than program B, it will win the game in the beginning and middle game and the EGDB is of no use but this case is not very interesting is it?
The most interesting situation is the following: program A eval function is a LITTLE better than program B eval function and, as a consequence, program A reaches quite often the endgame with a clear advantage but not a clear win! Now the EGDB becomes the key point: if program A has the best EGDB it will win many of these games but if program B has the best EGDB it will manage to draw a lot of these.

Hi, Taille and the others programmers,

I don't know if there are different level of EGDB, what can be for example the difference between Damy 7 EGDB and Kingsrow's or Damge's.
I thought that it was a convention, the same number of position Win/Draw/Loss.
I don't understand what Taille said.

Thanks
Sidiki

Hi Sidiki,

Gérard probably meant the number of pieces covered by the positions stored and not the quality of the EGDB.

Maybe I'm mistaken, but I guess most EGDB generators for draughts are based on the algorithm by Jonathan Shaeffer which was originally developed for checkers and later modified for 10x10. So in a sense all EGDB's (with the same piece signature) contain the same information, this doesn't has to be in the same format of course. To make it smaller Ed removed positions with captures from the Kingsrow database, I don't know if this is also the case with the other EGDB's.

I still didn't have time to add a configuration file and an easy way of playing games with my engine, with a bit of luck I can work on it tomorrow and I still hope to have something ready by the end of this week. Actually I'm thinking about making a small Windows program for it with a menu to adjust the settings and to store the parameters in the registry, this is a lot easier than fiddling with a configuration file and command-line parameters.

Joost

Yes Joost, of course my wording was not correct. Instead of the "best" EGDB you should read the "largest" EGDB (I mean 8 pieces is larger than 6 or 7 pieces).
I do not know the algorithm by Jonathan Shaeffer.
Due to the exchange between us, we know that the 8 pieces db of Damy, Kingsrow and Dragon have the number of winning and losing positions.
Concerning Damy EGDB I did not store in the db the capture positions.

[Rein Halbersma]

I still didn't have time to add a configuration file and an easy way of playing games with my engine, with a bit of luck I can work on it tomorrow and I still hope to have something ready by the end of this week. Actually I'm thinking about making a small Windows program for it with a menu to adjust the settings and to store the parameters in the registry, this is a lot easier than fiddling with a configuration file and command-line parameters.

Joost

Please reconsider doing configuration through the Windows registry. Mess up with that and you corrupt a user's entire system. A text congfig file us way more robust and not hard at all.

[Joost Buijs]

I still didn't have time to add a configuration file and an easy way of playing games with my engine, with a bit of luck I can work on it tomorrow and I still hope to have something ready by the end of this week. Actually I'm thinking about making a small Windows program for it with a menu to adjust the settings and to store the parameters in the registry, this is a lot easier than fiddling with a configuration file and command-line parameters.

Joost

Please reconsider doing configuration through the Windows registry. Mess up with that and you corrupt a user's entire system. A text congfig file us way more robust and not hard at all.

Rein,

Since many years I use the registry for storing all kinds of parameters belonging to programs I write and I never had a single customer complain about messing up his system. There is nothing wrong with storing parameters in "HKCU/Software/Company/" (in fact Microsoft advices you to do so).

The only drawback is that the program will never be Linux compatible, since I will add a Windows interface to it the program will never be compatible with Linux anyway. My SMP is entirely based on Windows threads as well, a couple of months ago I made a version with C++ threads, it works but when I checked it with the Intel thread analyzer I found some data-races in the MSVC C++ thread library so I decided not to use it, at least not until these problems are fixed.

A config file is not hard to do, I agree, you can even use something like JSON to standardize it, nowadays 99.9% of all programs running under Windows use the registry to store small configuration parameters, this really is common practice. Larger data is usually stored in "/ProgramData/Company/" or "/Users/User/AppData/Roaming/Company/" if you need compatibility with 'roaming profiles'.

Another question: Some time ago I talked with Bert about using his rendered pieces to use them in a simple GUI, he told me that they were rendered either by you or by 'Wieger Wesselink' he doesn't know exactly, do you think it is ok to use these or is there a copyright on these renderings?

Joost