Internet engine matches

Discussion about development of draughts in the time of computer and Internet.
Post Reply
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Internet engine matches

Post by TAILLE » Wed Oct 10, 2012 23:14

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?

Image
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

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Internet engine matches

Post by MichelG » Thu Oct 11, 2012 08:57

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).
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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Internet engine matches

Post by TAILLE » Thu Oct 11, 2012 12:15

Hi Michel,
MichelG wrote:
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).
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.
Gérard

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Internet engine matches

Post by Rein Halbersma » Thu Oct 11, 2012 13:32

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?

Image
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
Last edited by Rein Halbersma on Thu Oct 11, 2012 13:50, edited 1 time in total.

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Internet engine matches

Post by Rein Halbersma » Thu Oct 11, 2012 13:47

Image

The occupied squares in this diagram form a jump group: a white man can jump between these squares.

Image Image
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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Internet engine matches

Post by TAILLE » Thu Oct 11, 2012 16:04

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. 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.
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
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: 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.
Gérard

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Internet engine matches

Post by Rein Halbersma » Thu Oct 11, 2012 17:27

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. 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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Internet engine matches

Post by TAILLE » Thu Oct 11, 2012 17:51

Rein Halbersma wrote:
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. 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?
Gérard

Ed Gilbert
Posts: 751
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: Internet engine matches

Post by Ed Gilbert » Thu Oct 11, 2012 18:57

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
Posts: 221
Joined: Thu Nov 27, 2008 19:22
Contact:

Re: Internet engine matches

Post by Maurits Meijer » Thu Oct 11, 2012 21:18

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?
http://slagzet.com

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Internet engine matches

Post by Rein Halbersma » Thu Oct 11, 2012 23:46

TAILLE wrote:
Rein Halbersma wrote:
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. 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!

Image

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
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Internet engine matches

Post by Rein Halbersma » Thu Oct 11, 2012 23:50

Image

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

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Internet engine matches

Post by TAILLE » Fri Oct 12, 2012 00:19

Rein,
Rein Halbersma wrote:Image

Gerard, another challenge for your new algorithm: how long does it take to find the winning move? 8)
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?
Gérard

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Internet engine matches

Post by TAILLE » Fri Oct 12, 2012 00:38

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

Image

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!
Gérard

Rein Halbersma
Posts: 1628
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Internet engine matches

Post by Rein Halbersma » Fri Oct 12, 2012 16:13

TAILLE wrote:Rein,
Rein Halbersma wrote:Image

Gerard, another challenge for your new algorithm: how long does it take to find the winning move? 8)
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?
Last edited by Rein Halbersma on Fri Oct 12, 2012 16:36, edited 1 time in total.

Post Reply