Internet engine matches
Re: Internet engine matches
Hi,
After quite a very long time I have just managed to reach a quite stable new search algorithm for Damy.
Can you tell me how many time your program needs to resolve the following Sijbrands composition?
White to move : +1
For the following months I will now concentrate my work on my new eval function (a lot of work indeed).
After quite a very long time I have just managed to reach a quite stable new search algorithm for Damy.
Can you tell me how many time your program needs to resolve the following Sijbrands composition?
White to move : +1
For the following months I will now concentrate my work on my new eval function (a lot of work indeed).
Gérard
Re: Internet engine matches
This is what dragon produces on a 2 core 2.1 Ghz machine:TAILLE wrote:Hi,
After quite a very long time I have just managed to reach a quite stable new search algorithm for Damy.
Can you tell me how many time your program needs to resolve the following Sijbrands composition?
For the following months I will now concentrate my work on my new eval function (a lot of work indeed).
 prof.: 1. 0.008 0.0 3732
prof.: 2. 0.056 0.0 4842 1923
prof.: 3. 0.016 0.0 4943 510 3732
prof.: 4. 0.016 0.0 4842 2024 29x20 25x14 3530 1923
prof.: 5. 0.032 0.0 4842 510 29x18 12x23 3933 2328 4439
prof.: 6. 0.064 0.0 2924 19x30 35x24 20x29 34x23 18x29 4843 1218
prof.: 7. 0.040 0.1 2924 19x30 35x24 20x29 34x23 18x29 4843 1520
prof.: 8. 0.040 0.1 2924 19x30 35x24 20x29 34x23 18x29 4843 1520
prof.: 9. 0.040 0.2 2924 19x30 35x24 20x29 34x23 18x29 4843 1520
prof.: 10. 0.040 0.3 2924 19x30 35x24 20x29 34x23 18x29 4843 1520
prof.: 11. 0.120 0.7 3731 27x36 2924 19x30 35x24 20x29 34x23 18x29
prof.: 12. 0.120 2.0 3731 27x36 2924 19x30 35x24 20x29 34x23 18x29
prof.: 13. 0.120 2.9 3731 27x36 2924 19x30 35x24 20x29 34x23 18x29
prof.: 14. 1.056 1.2 3731 27x36 3530 1823 29x18x27 914 3933 510
prof.: 15. 1.064 0.9 3731 27x36 3530 1823 29x18x27 914 3933 2024
prof.: 16. 1.072 1.6 3731 27x36 3530 2024 29x20 15x24x35 2621 16x27
prof.: 17. 1.104 3.1 3731 27x36 3530 1823 29x18x27 914 3933 2024
prof.: 18. 1.112 4.8 3731 27x36 3530 2024 2924
prof.: 19. 1.072 13.8 3731 27x36 3530 1823 29x18x27 914 3933 2024
Re: Internet engine matches
Hi Michel,
On my laptop Core 2 duo 2,2GHz the problem is solved (I mean discovering the sequence 3731 27x36 3530!) in less than 8 seconds. I have still to work on the tuning of my algorithm but I guess I will not gain a lot.
Of course it would be interesting to know the figures of other programmers.
Thank you for your answer Michel. Now I am reassured.MichelG wrote:This is what dragon produces on a 2 core 2.1 Ghz machine:TAILLE wrote:Hi,
After quite a very long time I have just managed to reach a quite stable new search algorithm for Damy.
Can you tell me how many time your program needs to resolve the following Sijbrands composition?
For the following months I will now concentrate my work on my new eval function (a lot of work indeed).Right move at ply 11 after 1.4 seconds, and right score at ply 14 after 8.2 seconds.
 prof.: 1. 0.008 0.0 3732
prof.: 2. 0.056 0.0 4842 1923
prof.: 3. 0.016 0.0 4943 510 3732
prof.: 4. 0.016 0.0 4842 2024 29x20 25x14 3530 1923
prof.: 5. 0.032 0.0 4842 510 29x18 12x23 3933 2328 4439
prof.: 6. 0.064 0.0 2924 19x30 35x24 20x29 34x23 18x29 4843 1218
prof.: 7. 0.040 0.1 2924 19x30 35x24 20x29 34x23 18x29 4843 1520
prof.: 8. 0.040 0.1 2924 19x30 35x24 20x29 34x23 18x29 4843 1520
prof.: 9. 0.040 0.2 2924 19x30 35x24 20x29 34x23 18x29 4843 1520
prof.: 10. 0.040 0.3 2924 19x30 35x24 20x29 34x23 18x29 4843 1520
prof.: 11. 0.120 0.7 3731 27x36 2924 19x30 35x24 20x29 34x23 18x29
prof.: 12. 0.120 2.0 3731 27x36 2924 19x30 35x24 20x29 34x23 18x29
prof.: 13. 0.120 2.9 3731 27x36 2924 19x30 35x24 20x29 34x23 18x29
prof.: 14. 1.056 1.2 3731 27x36 3530 1823 29x18x27 914 3933 510
prof.: 15. 1.064 0.9 3731 27x36 3530 1823 29x18x27 914 3933 2024
prof.: 16. 1.072 1.6 3731 27x36 3530 2024 29x20 15x24x35 2621 16x27
prof.: 17. 1.104 3.1 3731 27x36 3530 1823 29x18x27 914 3933 2024
prof.: 18. 1.112 4.8 3731 27x36 3530 2024 2924
prof.: 19. 1.072 13.8 3731 27x36 3530 1823 29x18x27 914 3933 2024
On my laptop Core 2 duo 2,2GHz the problem is solved (I mean discovering the sequence 3731 27x36 3530!) in less than 8 seconds. I have still to work on the tuning of my algorithm but I guess I will not gain a lot.
Of course it would be interesting to know the figures of other programmers.
Gérard

 Posts: 1635
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Internet engine matches
Gerard,TAILLE wrote:Hi,
After quite a very long time I have just managed to reach a quite stable new search algorithm for Damy.
Can you tell me how many time your program needs to resolve the following Sijbrands composition?
White to move : +1
For the following months I will now concentrate my work on my new eval function (a lot of work indeed).
If you solve this position in much less than 8 seconds, you have measured its benefits. But have you also measured its costs that are realized on similar positions where these tactics do not work?
E.g. after 1. 3731 27x36 2. 3530 2024 3. 29x20 15x35, white is 2 men down and there are no more captures pending for either white or black. So it would appear that it's reasonable to heavily reduce the remaining search depth, e.g. by 50% (e.g. this is how Chinook did it). Because the refutation is another 6 ply away (2621 3832 and 3933), any engine with such an aggressively reduced search would not find the winning line before depth=18.
IMO, the only way to test if such tactics detection is worth it, is doing engine matches. After all, if such tactics are very rare, the benefits will not outweigh the costs. There might be a difference between doing this only at the root (where finding a tactic will win the game immediately, and missing one for your opponent will lose the game immediately) and doing this inside the search tree (where there must be many more positions with 2 men down that simply lose because there is no tactical rescue).
However, if you can detect cheaply that there are large opportunities for tactics (in this case: the open square 3, 14 and 23), in combination with black men that can be captured along these squares (in this case: 9, 19 and 20) and white men that can do the capture (in this case 34), then I think it could be profitable to not reduce the search so aggressively after 3731 and 3530.
I use 4 special jump group bitboards to detect such tactical possibilities (it's a wellknown theoretical idea used by problem composers). Do you also use special pattern detection before you decided to extend your search?
Rein
Last edited by Rein Halbersma on Thu Oct 11, 2012 13:50, edited 1 time in total.

 Posts: 1635
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Internet engine matches
The occupied squares in this diagram form a jump group: a white man can jump between these squares.
Left jumpable black pieces___________Right jumpable black pieces
With a sequence of bitshifts on these diagrams and a given position, it is possible to efficiently detect if square 3 can be reached by a white piece.
Re: Internet engine matches
I entirely agree with you Rein. It would be very unskillful to spent a lot of time to look for tactical combination at the expense of exploring very stupid sequences.Rein Halbersma wrote: Gerard,
If you solve this position in much less than 8 seconds, you have measured its benefits. But have you also measured its costs that are realized on similar positions where these tactics do not work?
E.g. after 1. 3731 27x36 2. 3530 2024 3. 29x20 15x35, white is 2 men down and there are no more captures pending for either white or black. So it would appear that it's reasonable to heavily reduce the remaining search depth, e.g. by 50% (e.g. this is how Chinook did it). Because the refutation is another 6 ply away (2621 3832 and 3933), any engine with such an aggressively reduced search would not find the winning line before depth=18.
Rein
Let's take your exemple and suppose I search at depth 11 from the root. With this hypthesis, after
1. 3731 27x36 2. 3530 2024 3. 29x20 15x35
Damy, seeing that white is 2 men down, will prune immediatly any move that do not lead to a capture but Damy is still able to find the combinaison 2621 3832 and 3933! That is the clue of my new algorithm.
Yes of course Rein engine match is the best test. As you know I decided to completly restructure my eval function and I have still a lot of work to do before running such match.Rein Halbersma wrote: IMO, the only way to test if such tactics detection is worth it, is doing engine matches. After all, if such tactics are very rare, the benefits will not outweigh the costs. There might be a difference between doing this only at the root (where finding a tactic will win the game immediately, and missing one for your opponent will lose the game immediately) and doing this inside the search tree (where there must be many more positions with 2 men down that simply lose because there is no tactical rescue).
Rein
I do not use such detection.Rein Halbersma wrote: However, if you can detect cheaply that there are large opportunities for tactics (in this case: the open square 3, 14 and 23), in combination with black men that can be captured along these squares (in this case: 9, 19 and 20) and white men that can do the capture (in this case 34), then I think it could be profitable to not reduce the search so aggressively after 3731 and 3530.
I use 4 special jump group bitboards to detect such tactical possibilities (it's a wellknown theoretical idea used by problem composers). Do you also use special pattern detection before you decided to extend your search?
Rein
Gérard

 Posts: 1635
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Internet engine matches
But this problem is a bit special. You could also decide after 1.3731 27x36 to only look for moves that generate captures, and ignore 3530. So does your algorithm make a distinction whether you are 1 or 2 pieces behind?TAILLE wrote: I entirely agree with you Rein. It would be very unskillful to spent a lot of time to look for tactical combination at the expense of exploring very stupid sequences.
Let's take your exemple and suppose I search at depth 11 from the root. With this hypthesis, after
1. 3731 27x36 2. 3530 2024 3. 29x20 15x35
Damy, seeing that white is 2 men down, will prune immediatly any move that do not lead to a capture but Damy is still able to find the combinaison 2621 3832 and 3933! That is the clue of my new algorithm.
Re: Internet engine matches
Of course Rein the reduction/pruning mechanism depends on several parameters including the current depth and the materiel balance.Rein Halbersma wrote:But this problem is a bit special. You could also decide after 1.3731 27x36 to only look for moves that generate captures, and ignore 3530. So does your algorithm make a distinction whether you are 1 or 2 pieces behind?TAILLE wrote: I entirely agree with you Rein. It would be very unskillful to spent a lot of time to look for tactical combination at the expense of exploring very stupid sequences.
Let's take your exemple and suppose I search at depth 11 from the root. With this hypthesis, after
1. 3731 27x36 2. 3530 2024 3. 29x20 15x35
Damy, seeing that white is 2 men down, will prune immediatly any move that do not lead to a capture but Damy is still able to find the combinaison 2621 3832 and 3933! That is the clue of my new algorithm.
As I mentionned in another post my algorithm is mainly based on FHR. After 1.3731 27x36 white is at disadvantage and I do not apply a reduction/pruning (I do not use LMR). In this case the reduction/pruning will appear only after the next white move.
After e.g. 1.3731 27x36 2.4641 black is one man up in a position without capture; I will then automtically apply a reduction.
With 2 men up the reduction will of course be more agressive.
I am not sure to understand your point because all that is very common and I guess we all apply such reduction strategy. The details of our implementations are certanly very different but the basic idea is the same isn't it?
BTW you do not gives us the time you need to solve this "special" problem? Is it a secret?
Gérard

 Posts: 770
 Joined: Sat Apr 28, 2007 14:53
 Real name: Ed Gilbert
 Location: Morristown, NJ USA
 Contact:
Re: Internet engine matches
I let kingsrow search the position for several minutes, but it does not find 3731.
Of course I can relax the search reductions somewhat so that it finds it quickly, but then kingsrow will do worse in engine matches. I have played many thousands of games to tune the reduction amounts.
 Ed
Of course I can relax the search reductions somewhat so that it finds it quickly, but then kingsrow will do worse in engine matches. I have played many thousands of games to tune the reduction amounts.
 Ed

 Posts: 221
 Joined: Thu Nov 27, 2008 19:22
 Contact:
Re: Internet engine matches
Intresting discussion. I wonder what the relation is between the time spent searching, generating the moves and evaluation; especially since it seems that in this case it would be fine to relax your evaluation function to just counting pieces when you are behind two pieces.
How do you spend your time?
How do you spend your time?
http://slagzet.com

 Posts: 1635
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Internet engine matches
Gerard, it's no secret (I just wasn't near my development machine today): my engine does not find the solution within 10 minutes of searching.TAILLE wrote:Of course Rein the reduction/pruning mechanism depends on several parameters including the current depth and the materiel balance.Rein Halbersma wrote:But this problem is a bit special. You could also decide after 1.3731 27x36 to only look for moves that generate captures, and ignore 3530. So does your algorithm make a distinction whether you are 1 or 2 pieces behind?TAILLE wrote: I entirely agree with you Rein. It would be very unskillful to spent a lot of time to look for tactical combination at the expense of exploring very stupid sequences.
Let's take your exemple and suppose I search at depth 11 from the root. With this hypthesis, after
1. 3731 27x36 2. 3530 2024 3. 29x20 15x35
Damy, seeing that white is 2 men down, will prune immediatly any move that do not lead to a capture but Damy is still able to find the combinaison 2621 3832 and 3933! That is the clue of my new algorithm.
As I mentionned in another post my algorithm is mainly based on FHR. After 1.3731 27x36 white is at disadvantage and I do not apply a reduction/pruning (I do not use LMR). In this case the reduction/pruning will appear only after the next white move.
After e.g. 1.3731 27x36 2.4641 black is one man up in a position without capture; I will then automtically apply a reduction.
With 2 men up the reduction will of course be more agressive.
I am not sure to understand your point because all that is very common and I guess we all apply such reduction strategy. The details of our implementations are certanly very different but the basic idea is the same isn't it?
BTW you do not gives us the time you need to solve this "special" problem? Is it a secret?
I am quite sceptical about the practical use of solving this type of position (sacrifice + quiet move that appears to give another piece away). One variation (the principal one intended by Sijbrands I believe) is
1. 3731 27x36 2. 3530 914 3. 3024 19x30 4. 2621 16x27 5. 4742 36x47 6. 4237 47x24 7. 3732 27x38 8. 3429 24x33 9. 39x10 5x14 10. 4943 38x49 11. 4035 49x40 12. 35x24 20x29 13. 45x1 with a winning endgame for white. Note that this is a 19ply tactical combination (starting with white's 3. 3024!). In principal these type of explorations can happen everywhere!
Now take the above position (where I added an extra black piece on 1 and an extra white piece on 50): the entire plan is ruined because the 45x1 capture is impossible! However, this will not become obvious in the above variation until move 13. where you now capture 13. 45x12 1x12 instead, with a losing endgame for white.
Does your algorithm efficiently abort the tactical search so as not to waste any time on it?
Rein

 Posts: 1635
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Internet engine matches
Gerard, another challenge for your new algorithm: how long does it take to find the winning move?
Re: Internet engine matches
Rein,
Damy resolves the problem (3430, 5044) in less than 2 seconds. Do you have similar measure?
This problem seems far easier. I do not have the fractions of second for my time measure, butRein Halbersma wrote:
Gerard, another challenge for your new algorithm: how long does it take to find the winning move?
Damy resolves the problem (3430, 5044) in less than 2 seconds. Do you have similar measure?
Gérard
Re: Internet engine matches
Rein,
To answer your question, in the position with the extra men at 1 and 50 I do not consider it is a waste of time to search a combination similar to the previous one!
That's a crucial point. Searching a combination is essential in draughts and it is also quite essentiel to avoid searching a combination in positions where you do not need a combination to take an advantage! That is the main idea of my new algorithm. I try to avoid searching unuseful combinations in order to have more time to search deeper combinations for other positions.Rein Halbersma wrote:Gerard, it's no secret (I just wasn't near my development machine today): my engine does not find the solution within 10 minutes of searching.
I am quite sceptical about the practical use of solving this type of position (sacrifice + quiet move that appears to give another piece away). One variation (the principal one intended by Sijbrands I believe) is
1. 3731 27x36 2. 3530 914 3. 3024 19x30 4. 2621 16x27 5. 4742 36x47 6. 4237 47x24 7. 3732 27x38 8. 3429 24x33 9. 39x10 5x14 10. 4943 38x49 11. 4035 49x40 12. 35x24 20x29 13. 45x1 with a winning endgame for white. Note that this is a 19ply tactical combination (starting with white's 3. 3024!). In principal these type of explorations can happen everywhere!
Now take the above position (where I added an extra black piece on 1 and an extra white piece on 50): the entire plan is ruined because the 45x1 capture is impossible! However, this will not become obvious in the above variation until move 13. where you now capture 13. 45x12 1x12 instead, with a losing endgame for white.
Does your algorithm efficiently abort the tactical search so as not to waste any time on it?
Rein
To answer your question, in the position with the extra men at 1 and 50 I do not consider it is a waste of time to search a combination similar to the previous one!
Gérard

 Posts: 1635
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Internet engine matches
My program solves this position after search of 13 ply and a tree of 7.5 million nodes (= separate calls to search() function) and 7 seconds. My effective branching factor is around 3.38 for this position. What are some numbers for your search?TAILLE wrote:Rein,
This problem seems far easier. I do not have the fractions of second for my time measure, butRein Halbersma wrote:
Gerard, another challenge for your new algorithm: how long does it take to find the winning move?
Damy resolves the problem (3430, 5044) in less than 2 seconds. Do you have similar measure?
Last edited by Rein Halbersma on Fri Oct 12, 2012 16:36, edited 1 time in total.