Internet engine matches

[TAILLE]

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).

[MichelG]

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).

This is what dragon produces on a 2 core 2.1 Ghz machine:

• prof.: 1. 0.008 0.0 37-32
  prof.: 2. 0.056 0.0 48-42 19-23
  prof.: 3. -0.016 0.0 49-43 5-10 37-32
  prof.: 4. 0.016 0.0 48-42 20-24 29x20 25x14 35-30 19-23
  prof.: 5. 0.032 0.0 48-42 5-10 29x18 12x23 39-33 23-28 44-39
  prof.: 6. 0.064 0.0 29-24 19x30 35x24 20x29 34x23 18x29 48-43 12-18
  prof.: 7. 0.040 0.1 29-24 19x30 35x24 20x29 34x23 18x29 48-43 15-20
  prof.: 8. 0.040 0.1 29-24 19x30 35x24 20x29 34x23 18x29 48-43 15-20
  prof.: 9. 0.040 0.2 29-24 19x30 35x24 20x29 34x23 18x29 48-43 15-20
  prof.: 10. 0.040 0.3 29-24 19x30 35x24 20x29 34x23 18x29 48-43 15-20
  prof.: 11. 0.120 0.7 37-31 27x36 29-24 19x30 35x24 20x29 34x23 18x29
  prof.: 12. 0.120 2.0 37-31 27x36 29-24 19x30 35x24 20x29 34x23 18x29
  prof.: 13. 0.120 2.9 37-31 27x36 29-24 19x30 35x24 20x29 34x23 18x29
  prof.: 14. 1.056 1.2 37-31 27x36 35-30 18-23 29x18x27 9-14 39-33 5-10
  prof.: 15. 1.064 0.9 37-31 27x36 35-30 18-23 29x18x27 9-14 39-33 20-24
  prof.: 16. 1.072 1.6 37-31 27x36 35-30 20-24 29x20 15x24x35 26-21 16x27
  prof.: 17. 1.104 3.1 37-31 27x36 35-30 18-23 29x18x27 9-14 39-33 20-24
  prof.: 18. 1.112 4.8 37-31 27x36 35-30 20-24 29-24
  prof.: 19. 1.072 13.8 37-31 27x36 35-30 18-23 29x18x27 9-14 39-33 20-24

Right move at ply 11 after 1.4 seconds, and right score at ply 14 after 8.2 seconds.

[TAILLE]

Hi Michel,

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).

This is what dragon produces on a 2 core 2.1 Ghz machine:

• prof.: 1. 0.008 0.0 37-32
  prof.: 2. 0.056 0.0 48-42 19-23
  prof.: 3. -0.016 0.0 49-43 5-10 37-32
  prof.: 4. 0.016 0.0 48-42 20-24 29x20 25x14 35-30 19-23
  prof.: 5. 0.032 0.0 48-42 5-10 29x18 12x23 39-33 23-28 44-39
  prof.: 6. 0.064 0.0 29-24 19x30 35x24 20x29 34x23 18x29 48-43 12-18
  prof.: 7. 0.040 0.1 29-24 19x30 35x24 20x29 34x23 18x29 48-43 15-20
  prof.: 8. 0.040 0.1 29-24 19x30 35x24 20x29 34x23 18x29 48-43 15-20
  prof.: 9. 0.040 0.2 29-24 19x30 35x24 20x29 34x23 18x29 48-43 15-20
  prof.: 10. 0.040 0.3 29-24 19x30 35x24 20x29 34x23 18x29 48-43 15-20
  prof.: 11. 0.120 0.7 37-31 27x36 29-24 19x30 35x24 20x29 34x23 18x29
  prof.: 12. 0.120 2.0 37-31 27x36 29-24 19x30 35x24 20x29 34x23 18x29
  prof.: 13. 0.120 2.9 37-31 27x36 29-24 19x30 35x24 20x29 34x23 18x29
  prof.: 14. 1.056 1.2 37-31 27x36 35-30 18-23 29x18x27 9-14 39-33 5-10
  prof.: 15. 1.064 0.9 37-31 27x36 35-30 18-23 29x18x27 9-14 39-33 20-24
  prof.: 16. 1.072 1.6 37-31 27x36 35-30 20-24 29x20 15x24x35 26-21 16x27
  prof.: 17. 1.104 3.1 37-31 27x36 35-30 18-23 29x18x27 9-14 39-33 20-24
  prof.: 18. 1.112 4.8 37-31 27x36 35-30 20-24 29-24
  prof.: 19. 1.072 13.8 37-31 27x36 35-30 18-23 29x18x27 9-14 39-33 20-24

Right move at ply 11 after 1.4 seconds, and right score at ply 14 after 8.2 seconds.

Thank you for your answer Michel. Now I am reassured.
On my laptop Core 2 duo 2,2GHz the problem is solved (I mean discovering the sequence 37-31 27x36 35-30!) 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.

[Rein Halbersma]

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).

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. 37-31 27x36 2. 35-30 20-24 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 (26-21 38-32 and 39-33), 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 37-31 and 35-30.

I use 4 special jump group bitboards to detect such tactical possibilities (it's a well-known theoretical idea used by problem composers). Do you also use special pattern detection before you decided to extend your search?

Rein

[Rein Halbersma]

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.

[TAILLE]

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. 37-31 27x36 2. 35-30 20-24 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 (26-21 38-32 and 39-33), any engine with such an aggressively reduced search would not find the winning line before depth=18.
Rein

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. 37-31 27x36 2. 35-30 20-24 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 26-21 38-32 and 39-33! That is the clue of my new algorithm.

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

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.

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 37-31 and 35-30.

I use 4 special jump group bitboards to detect such tactical possibilities (it's a well-known theoretical idea used by problem composers). Do you also use special pattern detection before you decided to extend your search?

Rein

I do not use such detection.

[Rein Halbersma]

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. 37-31 27x36 2. 35-30 20-24 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 26-21 38-32 and 39-33! That is the clue of my new algorithm.

But this problem is a bit special. You could also decide after 1.37-31 27x36 to only look for moves that generate captures, and ignore 35-30. So does your algorithm make a distinction whether you are 1 or 2 pieces behind?

[TAILLE]

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. 37-31 27x36 2. 35-30 20-24 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 26-21 38-32 and 39-33! That is the clue of my new algorithm.

But this problem is a bit special. You could also decide after 1.37-31 27x36 to only look for moves that generate captures, and ignore 35-30. So does your algorithm make a distinction whether you are 1 or 2 pieces behind?

Of course Rein the reduction/pruning mechanism depends on several parameters including the current depth and the materiel balance.
As I mentionned in another post my algorithm is mainly based on FHR. After 1.37-31 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.37-31 27x36 2.46-41 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?

[Ed Gilbert]

I let kingsrow search the position for several minutes, but it does not find 37-31.

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

[Maurits Meijer]

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?

[Rein Halbersma]

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. 37-31 27x36 2. 35-30 20-24 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 26-21 38-32 and 39-33! That is the clue of my new algorithm.

But this problem is a bit special. You could also decide after 1.37-31 27x36 to only look for moves that generate captures, and ignore 35-30. So does your algorithm make a distinction whether you are 1 or 2 pieces behind?

Of course Rein the reduction/pruning mechanism depends on several parameters including the current depth and the materiel balance.
As I mentionned in another post my algorithm is mainly based on FHR. After 1.37-31 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.37-31 27x36 2.46-41 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?

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. 37-31 27x36 2. 35-30 9-14 3. 30-24 19x30 4. 26-21 16x27 5. 47-42 36x47 6. 42-37 47x24 7. 37-32 27x38 8. 34-29 24x33 9. 39x10 5x14 10. 49-43 38x49 11. 40-35 49x40 12. 35x24 20x29 13. 45x1 with a winning endgame for white. Note that this is a 19-ply tactical combination (starting with white's 3. 30-24!). 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

[Rein Halbersma]

Gerard, another challenge for your new algorithm: how long does it take to find the winning move?

[TAILLE]

Rein,

Gerard, another challenge for your new algorithm: how long does it take to find the winning move?

This problem seems far easier. I do not have the fractions of second for my time measure, but
Damy resolves the problem (34-30, 50-44) in less than 2 seconds. Do you have similar measure?

[TAILLE]

Rein,

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. 37-31 27x36 2. 35-30 9-14 3. 30-24 19x30 4. 26-21 16x27 5. 47-42 36x47 6. 42-37 47x24 7. 37-32 27x38 8. 34-29 24x33 9. 39x10 5x14 10. 49-43 38x49 11. 40-35 49x40 12. 35x24 20x29 13. 45x1 with a winning endgame for white. Note that this is a 19-ply tactical combination (starting with white's 3. 30-24!). 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

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.
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!

[Rein Halbersma]

Rein,

Gerard, another challenge for your new algorithm: how long does it take to find the winning move?

This problem seems far easier. I do not have the fractions of second for my time measure, but
Damy resolves the problem (34-30, 50-44) in less than 2 seconds. Do you have similar measure?

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?