[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums

It's Impossible/and a new test of skill

Posted By: Timothy Chow
Date: Friday, 23 April 2010, at 2:57 p.m.

In Response To: It's Impossible/and a new test of skill (phil Simborg)

Phil Simborg wrote:

but are there any legal positions that are truly impossible?

"Legal" is probably the wrong adjective here, but I think I know what you mean. This question was raised by 6stones back in October and a couple of examples were given back then.

Maybe some day we could program a bot to do this.

More generally, we can ask for an algorithm for determining whether a given checker position is reachable from the standard starting position. The analogous problem in chess (generalized to an nxn board) is not known to be solvable in polynomial time, and in fact is not even known to be in the complexity class NP, because we don't know if there are some positions that take exponentially many moves to reach. This may sound hard to imagine if you are not familiar with retrograde problems in chess, in which case I recommend you look at this article by Tom Volet, which will leave you stunned at what deviousness the human mind is capable of.

The legality recognition problem in backgammon doesn't strike me as being that difficult, though I admit I have not tried to come up with an actual algorithm. If retrograde analysis in games other than chess appeals to you, then I recommend this page by Joe Kisenwether for some fascinating examples. These only scratch the surface of what appears to be a rich area for puzzle composition.

I will show you a position that exists after each player has rolled 3 times and moved legally 3 times, and you will have to tell me what the rolls were.

In chess, these kinds of problems are called "proof games." Usually, an aesthetic criterion that is imposed is that the solution be unique.

In backgammon I would be inclined to relax the criterion that the starting position be the standard one, and instead allow the composer to select any two positions A and B and ask for a sequence of dice rolls and plays that lead from A to B. For those who like a challenge, here's a question: How long can you make such a sequence and still have the solution be unique?

Messages In This Thread

 

Post Response
Your Name:
Your E-Mail Address:
Subject:
Message:

If necessary, enter your password below:

Password:
 

 

[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums is maintained by Stick with WebBBS 5.12.