World Draughts Forum

It is currently Fri Nov 16, 2018 15:42

All times are UTC+01:00




Post new topic  Reply to topic  [ 60 posts ]  Go to page Previous 1 2 3 4 Next
Author Message
 Post subject: Re: Retrograde problems
PostPosted: Thu Jul 19, 2018 22:52 
Offline

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

_________________
Gérard


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sat Jul 21, 2018 22:53 
Offline
User avatar

Joined: Tue Aug 22, 2006 15:38
Posts: 1441
Real name: Joost de Heer
First attempt to #4:
Image
37-42 47x30 25x21
Score: 10000*3+100*(13-5)+1*(1-0) = 30801

And a new attempt for #3:
Image
27-32 46x7 2x11
Score: 10000*3+100*(8-5)+1*(1-0) = 30301

_________________
Lasst die Maschinen verhungern, Ihr Narren...
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!


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

Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sat Jul 21, 2018 23:16 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 954
Location: FRANCE
ildjarn wrote:
First attempt to #4:
Image
37-42 47x30 25x21
Score: 10000*3+100*(13-5)+1*(1-0) = 30801

And a new attempt for #2:
Image
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.

_________________
Gérard


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sun Jul 22, 2018 14:22 
Offline
User avatar

Joined: Tue Aug 22, 2006 15:38
Posts: 1441
Real name: Joost de Heer
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!


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sun Jul 22, 2018 15:10 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 954
Location: FRANCE
ildjarn wrote:
Gerard, could you give a hint what score I can reach? I'm out of ideas...


Of course Ildjarn,

Image
score = 030201


Image
score = 030602

_________________
Gérard


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sun Jul 22, 2018 16:07 
Offline
User avatar

Joined: Tue Aug 22, 2006 15:38
Posts: 1441
Real name: Joost de Heer
New attempt to #4:
Image
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!


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sun Jul 22, 2018 16:11 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 954
Location: FRANCE
ildjarn wrote:
New attempt to #4:
Image
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 !!!

_________________
Gérard


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sun Jul 22, 2018 18:23 
Offline
User avatar

Joined: Tue Aug 22, 2006 15:38
Posts: 1441
Real name: Joost de Heer
My mind was stuck with 2x11 as last move.

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


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sun Jul 22, 2018 22:39 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 954
Location: FRANCE
ildjarn wrote:
My mind was stuck with 2x11 as last move.

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

Image
score = 101199 (but a dual exists)

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

_________________
Gérard


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Mon Jul 23, 2018 08:51 
Offline
User avatar

Joined: Tue Aug 22, 2006 15:38
Posts: 1441
Real name: Joost de Heer
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?

_________________
Lasst die Maschinen verhungern, Ihr Narren...

Lasst sie verrecken!

Schlagt sie tot -- die Maschinen!


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Mon Jul 23, 2018 10:41 
Offline

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


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:
Image

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
Image

_________________
Gérard


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Mon Jul 23, 2018 17:36 
Offline

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

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

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:
Image

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


example 2:
Image

if you suppose a capture from black 10 you reach the working diagram
Image
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
Image

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
Image
The first move of the solution is 36-9 and the final capture is obvious isn't it?

Solution:
Image


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


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Wed Jul 25, 2018 10:33 
Offline
User avatar

Joined: Tue Aug 22, 2006 15:38
Posts: 1441
Real name: Joost de Heer
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!


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Wed Jul 25, 2018 12:02 
Offline

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


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.

_________________
Gérard


Top
   
 Post subject: Re: Retrograde problems
PostPosted: Sat Jul 28, 2018 18:41 
Offline
User avatar

Joined: Tue Aug 22, 2006 15:38
Posts: 1441
Real name: Joost de Heer
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!


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 60 posts ]  Go to page Previous 1 2 3 4 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 22 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited