## Retrograde problems

### Re: Retrograde problems

#2 OK except the score calculation : 10000*2+100*(5-3)+(1-2)=20199ildjarn wrote:Spoiler:

Gérard

### Re: Retrograde problems

First attempt to #4:

37-42 47x30 25x21

Score: 10000*3+100*(13-5)+1*(1-0) = 30801

And a new attempt for #3:

27-32 46x7 2x11

Score: 10000*3+100*(8-5)+1*(1-0) = 30301

37-42 47x30 25x21

Score: 10000*3+100*(13-5)+1*(1-0) = 30801

And a new attempt for #3:

27-32 46x7 2x11

Score: 10000*3+100*(8-5)+1*(1-0) = 30301

Last edited by ildjarn on Sun Jul 22, 2018 14:21, edited 1 time in total.

Lasst die Maschinen verhungern, Ihr Narren...

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

### Re: Retrograde problems

Nice Ildjarn, at least you managed to reach a stable position! Congratulation for that because I know perfectly it is not that easy!ildjarn wrote:First attempt to #4:

37-42 47x30 25x21

Score: 10000*3+100*(13-5)+1*(1-0) = 30801

And a new attempt for #2:

27-32 46x7 2x11

Score: 10000*3+100*(8-5)+1*(1-0) = 30301

For both #3 and #4 you can still get a better score.

Gérard

### Re: Retrograde problems

Gerard, could you give a hint what score I can reach? I'm out of ideas...

Lasst die Maschinen verhungern, Ihr Narren...

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

### Re: Retrograde problems

Of course Ildjarn,ildjarn wrote:Gerard, could you give a hint what score I can reach? I'm out of ideas...

score = 030201

score = 030602

Gérard

### Re: Retrograde problems

New attempt to #4:

27-38 42x28 23x41

Score: 10000*3+100*(11-5)+1*(2-0) = 30602

Still no idea for #3...

27-38 42x28 23x41

Score: 10000*3+100*(11-5)+1*(2-0) = 30602

Still no idea for #3...

Lasst die Maschinen verhungern, Ihr Narren...

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

### Re: Retrograde problems

OK for #4ildjarn wrote:New attempt to #4:

27-38 42x28 23x41

Score: 10000*3+100*(11-5)+1*(2-0) = 30602

Still no idea for #3...

Sure you will find #3 because it is far easier to find a 30201 than a 30602 score !!!

Gérard

### Re: Retrograde problems

My mind was stuck with 2x11 as last move.

27-22 28x6 7-11

Score: 10000*3+100*(7-5)+1*(1-0) = 30201

27-22 28x6 7-11

Score: 10000*3+100*(7-5)+1*(1-0) = 30201

Lasst die Maschinen verhungern, Ihr Narren...

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

### Re: Retrograde problems

Fine Ildjarn, I was pretty sure you will manage to find the solutions wasn't I?ildjarn wrote:My mind was stuck with 2x11 as last move.

27-22 28x6 7-11

Score: 10000*3+100*(7-5)+1*(1-0) = 30201

Anyway I can see you faced some difficulties to resolve such basic problems and I suspect you could give up with a more difficult (and far more interesting and beautiful) one typically with 4 or 5 plies.

Will you be interested if I take the previous problems and I try to explain how to solve them as efficiently as possible?

As a pure curiosty let me show you a tremendous problem I tried to build (unfortunetly the following position is not a correct problem because a dual exists)

score = 101199 (but a dual exists)

solution:

**Spoiler:**

Gérard

### Re: Retrograde problems

Gérard,

I don't mind the difficulty. The two problems I ran into are:

- These kind of puzzles require a new way of thinking, and it takes some time getting used to it. It's very easy to get mentally stuck in an incorrect path.

- Finding a solution isn't very hard (although I doubt I could've found the solution for the last position you gave...), but for a human (at least for me) it's difficult to determine whether a found solution is optimal or not.

So please give me the positions which require 4 or 5 moves, so I can at least try and see where my limit lies in finding a solution.

Retrograde is, I assume, a recursive algorithm where step 0 is the given position, and step X is to generate all positions that lead to a position in step X-1 in 1 ply?

I don't mind the difficulty. The two problems I ran into are:

- These kind of puzzles require a new way of thinking, and it takes some time getting used to it. It's very easy to get mentally stuck in an incorrect path.

- Finding a solution isn't very hard (although I doubt I could've found the solution for the last position you gave...), but for a human (at least for me) it's difficult to determine whether a found solution is optimal or not.

So please give me the positions which require 4 or 5 moves, so I can at least try and see where my limit lies in finding a solution.

Retrograde is, I assume, a recursive algorithm where step 0 is the given position, and step X is to generate all positions that lead to a position in step X-1 in 1 ply?

Lasst die Maschinen verhungern, Ihr Narren...

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

### Re: Retrograde problems

OK Ildjarn I will then propose here two new problems which need 4 or 5 pliesildjarn wrote:Gérard,

I don't mind the difficulty. The two problems I ran into are:

- These kind of puzzles require a new way of thinking, and it takes some time getting used to it. It's very easy to get mentally stuck in an incorrect path.

- Finding a solution isn't very hard (although I doubt I could've found the solution for the last position you gave...), but for a human (at least for me) it's difficult to determine whether a found solution is optimal or not.

So please give me the positions which require 4 or 5 moves, so I can at least try and see where my limit lies in finding a solution.

Retrograde is, I assume, a recursive algorithm where step 0 is the given position, and step X is to generate all positions that lead to a position in step X-1 in 1 ply?

Yes Ildjarn I effectively programmed such recursive algorithm which is not quite difficult but need interesting tuning to the fact that the number of positions in step X-1 can be quite high. To my knowledge Damy is the only program with a retrograde algorithm and, as a consequence, I never was able to exchange with other programmers in order to find the best choices for such retrograde algorithm.

The first problem is the first one I propose with kings:

I like very much the second one because it is very aesthetic without being very difficult due to the fact that the number of capture plies is very low

Gérard

### Re: Retrograde problems

Let me try to help the reader not quite motivated, probably by lack of techniks.

When you try to resolve a very simple standard draughts problem I guess you do not try all moves until you find, by chance, the solution.

Black to play

For example in the above diagram I guess you first notice the hole in 37 and 26, then you note that black piece on 19 may be able to do a capture move using these holes and after that you can easily find the solution.

For a retrograde problem it is exactly the same; you cannot try all possibilties hoping to find by chance the solution.

Supposing you do not have a solution without capture I will try here to show you how to find a 2 plies retrograde problems with two examples.

Preliminary analysis:

From the initial position, which, per definition, has to be a stable position, we are then searching a quiet white ply (no capture) followed by a black capture ply.

We are then searching in particular a white piece (for the first quiet move of the sequence) and a black piece (for the second ply which is a capture move).

When comparing the initial position (the position we are searching) and the final position (i.e. the problem proposed) you can observe that one black piece has changed its place and some white pieces have been added (the captured pieces).

example 1:

If you search a 2 plies solution that means that one of the two black men on 20 and 30 do a capture ply, and this capture move is preceded by a quiet white ply from a stable position.

Let's first eliminate a capture with the black man on 30.

If you suppose a capture ending in 30 that means that the black man on 20 is still in 20 in the initial position and because the initial position is stable you are forced to put two white pieces on 9 and 14 in the initial position.

Because the capture by black 30 cannot take a white piece on 9 you can easily conclude that the white piece on 9 is necessarily the origin of the first white move and the white piece on 14 has to be captured by the black piece on 30

When you look and the working diagram above you can see the capture ply by black could only begin from square 10 but this is impossible because on 10 black man is unstable.

Now we know that the capture ply has to be done by the black piece on 20.

In the same way you can deduce that, in the initial position, you must have 2 white pieces on 34 and 39. The first white move has to be done by white pieces on 39 (I draw it as a king to remember that this piece has to do the first ply)

working diagram:

Now you have only to retrograde a capture ply from black 20, including the capture of white man on 34 and avoiding any unstablity.

example 2:

if you suppose a capture from black 10 you reach the working diagram

and you cannot see any solution because from the square 41 the retrograde capture has to put a white man on 37 and the resulting position wil not be stable.

The only possibility (for a 2 plies solution) is to take the black man 42 for the capture ply. To reach a stable position you need now to put piece on square 36. This cannot be the origin square of the black 42 and this cannot be a white piece that can be captured. The piece on square 36 is necessarily a white piece which will do the first ply in order to provoque the capture ply.

First working diagram

Now what could be the origine square of black 42 for its capture ply. Because the capture is provoked by a move from white piece on 36 the only solution for this square is 4.

Second working diagram

The first move of the solution is 36-9 and the final capture is obvious isn't it?

Solution:

I do not know if my explanations are clear but keep in mind that simple reasonning may greatly help you by avoiding inefficient searches.

When you try to resolve a very simple standard draughts problem I guess you do not try all moves until you find, by chance, the solution.

Black to play

For example in the above diagram I guess you first notice the hole in 37 and 26, then you note that black piece on 19 may be able to do a capture move using these holes and after that you can easily find the solution.

For a retrograde problem it is exactly the same; you cannot try all possibilties hoping to find by chance the solution.

Supposing you do not have a solution without capture I will try here to show you how to find a 2 plies retrograde problems with two examples.

Preliminary analysis:

From the initial position, which, per definition, has to be a stable position, we are then searching a quiet white ply (no capture) followed by a black capture ply.

We are then searching in particular a white piece (for the first quiet move of the sequence) and a black piece (for the second ply which is a capture move).

When comparing the initial position (the position we are searching) and the final position (i.e. the problem proposed) you can observe that one black piece has changed its place and some white pieces have been added (the captured pieces).

example 1:

If you search a 2 plies solution that means that one of the two black men on 20 and 30 do a capture ply, and this capture move is preceded by a quiet white ply from a stable position.

Let's first eliminate a capture with the black man on 30.

If you suppose a capture ending in 30 that means that the black man on 20 is still in 20 in the initial position and because the initial position is stable you are forced to put two white pieces on 9 and 14 in the initial position.

Because the capture by black 30 cannot take a white piece on 9 you can easily conclude that the white piece on 9 is necessarily the origin of the first white move and the white piece on 14 has to be captured by the black piece on 30

When you look and the working diagram above you can see the capture ply by black could only begin from square 10 but this is impossible because on 10 black man is unstable.

Now we know that the capture ply has to be done by the black piece on 20.

In the same way you can deduce that, in the initial position, you must have 2 white pieces on 34 and 39. The first white move has to be done by white pieces on 39 (I draw it as a king to remember that this piece has to do the first ply)

working diagram:

Now you have only to retrograde a capture ply from black 20, including the capture of white man on 34 and avoiding any unstablity.

example 2:

if you suppose a capture from black 10 you reach the working diagram

and you cannot see any solution because from the square 41 the retrograde capture has to put a white man on 37 and the resulting position wil not be stable.

The only possibility (for a 2 plies solution) is to take the black man 42 for the capture ply. To reach a stable position you need now to put piece on square 36. This cannot be the origin square of the black 42 and this cannot be a white piece that can be captured. The piece on square 36 is necessarily a white piece which will do the first ply in order to provoque the capture ply.

First working diagram

Now what could be the origine square of black 42 for its capture ply. Because the capture is provoked by a move from white piece on 36 the only solution for this square is 4.

Second working diagram

The first move of the solution is 36-9 and the final capture is obvious isn't it?

Solution:

I do not know if my explanations are clear but keep in mind that simple reasonning may greatly help you by avoiding inefficient searches.

Gérard

### Re: Retrograde problems

Hmm, at the moment the only thing I know is that in the first position the final move is 9x24 over a piece on 13. But so far nothing I've tried works. For the second, I think the last move is 12x32, but nothing further yet.

Lasst die Maschinen verhungern, Ihr Narren...

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

### Re: Retrograde problems

Hi Ildjarn,ildjarn wrote:Hmm, at the moment the only thing I know is that in the first position the final move is 9x24 over a piece on 13. But so far nothing I've tried works. For the second, I think the last move is 12x32, but nothing further yet.

Your analysis of the first position is correct. You are sure that the final move is 9x24 over a pieces on 13 and you are right.

For the second position you only "think" the last move is 12x32 and it is not the solution. Obviously you do not find already the main idea because a black man on square 12 would be in very poor position. As soon as you find this main idea then all plies are not that difficult to find. This is one the reason why I like very much this problem.

Gérard

### Re: Retrograde problems

Sorry, I haven't been able to find anything. Can you give the exact last move (capture over which pieces exactly)?

Lasst die Maschinen verhungern, Ihr Narren...

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!