Retrograde problems

[TAILLE]

Spoiler:

2: K11 39 40 44 / 30 for 1. 39-34 30x50 (10000*2+100*(4-1)+(1-2)=20299)

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

[ildjarn]

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

[TAILLE]

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

Nice Ildjarn, at least you managed to reach a stable position! Congratulation for that because I know perfectly it is not that easy!
For both #3 and #4 you can still get a better score.

[ildjarn]

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

[TAILLE]

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

Of course Ildjarn,


score = 030201



score = 030602

[ildjarn]

New attempt to #4:

27-38 42x28 23x41
Score: 10000*3+100*(11-5)+1*(2-0) = 30602

Still no idea for #3...

[TAILLE]

New attempt to #4:

27-38 42x28 23x41
Score: 10000*3+100*(11-5)+1*(2-0) = 30602

Still no idea for #3...

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

[ildjarn]

My mind was stuck with 2x11 as last move.


27-22 28x6 7-11
Score: 10000*3+100*(7-5)+1*(1-0) = 30201

[TAILLE]

My mind was stuck with 2x11 as last move.


27-22 28x6 7-11
Score: 10000*3+100*(7-5)+1*(1-0) = 30201

Fine Ildjarn, I was pretty sure you will manage to find the solutions wasn't I?

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:

1.6-1 38-42 2.17x6 14-20 3.28x17 13x11 4.24x13 37x8 5.39x28 5.34x21

[ildjarn]

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?

[TAILLE]

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?

OK Ildjarn I will then propose here two new problems which need 4 or 5 plies
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

[TAILLE]

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.

[ildjarn]

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.

[TAILLE]

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.

Hi Ildjarn,

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.

[ildjarn]

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