Sign in to follow this  

Shuffling cards for Solitaire?

This topic is 4390 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Well, this first requires knowing how a game can be won, which means we need to set forth the rules.

Now, I'm really rusty on Solitaire, as I don't play (matter of principles) but this is my best shot:

- There are several "play" piles, starting with one card, and built up to the right with one additional card per column. The rightmost column has several cards stacked. The topmost card of each pile is turned over and accessible; any others are not accessible.

- There are four "discard" piles, one for each suit; cards must be discarded in ascending order from Ace to King. None of these are accessible under the rules I know of.

- Remaining cards are placed in a "draw" pile, where the top card is drawn and either placed in play, discarded, or burned by leaving it face-up next to the draw pile. Only the most recently burned card is accessible.

- Cards can be stacked on any of the face-up play piles; a card can stack on another card IFF it is of an alternate color and is one denomination lower in value (e.g. 7 red stacks on 8 black).

- The game is won if all cards of all suits are discarded. The game is lost when the final draw card is drawn and no legal moves remain (or any remaining legal moves are nothing more than a stalemate and cannot lead the player to victory).


Now, where you get yourself in trouble is when you factor in player unpredictability. A guarantee that the game can be won is not the same as a guarantee that the game cannot be lost.

So let's assume an ideal, perfect player, one who will not make any mistakes. We'll take the easy road and assume also that this player does not practice card counting or other statistical analysis mechanisms for determining the "best" course of action when difficult decisions must be made.


Where to take it from here:
- Describe the exact conditions under which a game cannot be won. See if there are similar groups of conditions (e.g. the group of conditions some low-level card becomes trapped and cannot be discarded, leading to a dead state) and categorize them. List all the possible ways a game might be unwinnable (but note that this is not the same as listing every possible unwinnable game).

- Remove any of the conditions that require the player to make a mistake, given our perfect-player assumption from earlier.

- Now find some mathematical rules that stitch together these conditions. See if you can write some code that checks a shuffled deck and tests it for winnability.

- Once you can detect an unwinnable game, you have two choices. One is to brute-force (probably the best) and simply shuffle until you get a game that comes up winnable. The other option is to look again at your unwinnability patterns and invert them; see if there is a way to construct a deck that will never match an unwinnability rule. Then find the parts of such constructed decks that can be random, and the parts that must be consistent; shuffle the random parts, and leave the rest alone.

Share this post


Link to post
Share on other sites
The easy brute force solution would be to shuffle the cards randomly and have the computer play the game to see if it is winnable. Do that until a winnable shuffle is found. It shouldn't take long -- I bet the computer could play hundreds of games in a second.

Share this post


Link to post
Share on other sites
Quote:
Original post by smart_idiot
Couldn't you, like, start with a finished game and then work backwards until you end up with a deck of cards?

Maybe that isn't as easy as I originally thought it would be.


I think that might almost be as bad as brute force, because there's so many different places a card could have come from, depending on the so-many-places that so-many-cards are located.

Sure it might be harder and take longer to figure out algorithms for the first repliers approach, but it will leave you with a much more efficient way of doing things.

EDIT: If you're having trouble figuring out which conditions the game cannot be solved under, first try writing a program that randomly shuffles the cards. Have the computer play it and see if its win-able. If not, record the order of cards somewhere. When you have enough of them, analyze them to find out as much as you can about what's not valid

Share this post


Link to post
Share on other sites
I would definately start with a finished game and play it backwards with random reversible moves (that is if the game was being played forward in time, the move would be legal). You are absolutely ensured to generate a shuffle that can lead to a winning game if the player makes the right decisions. And even if the player still doesn't make the anti-decisions of the shuffle algorithm, he/she may still win.

Share this post


Link to post
Share on other sites
Quote:
Original post by Mastaba
I would definately start with a finished game and play it backwards with random reversible moves (that is if the game was being played forward in time, the move would be legal). You are absolutely ensured to generate a shuffle that can lead to a winning game if the player makes the right decisions. And even if the player still doesn't make the anti-decisions of the shuffle algorithm, he/she may still win.
I disagree. You'd be very likely to end up with a biased set of possible dealings, and besides it's likely to be pretty difficult, as there would be far more choices going in that direction.

You already have the code for detecting valid moves. Simply write a simple A* algorithm implementation to solve the game and then you just have to excersize it a few times until you find a solvable one. Chances are you'll most often find a solvable one on the first few hits, taking under a second.

You'll ge the added bennefit of being able to have the computer play it by itself, for a screensaver type of effect.
JohnBolton has the rioght idea.

Share this post


Link to post
Share on other sites
Yes, I understand there are multiple choices that could be made, but that's the point of choosing among them randomly. And because the moves are reversible, you will produce a well shuffled deck that can lead to a winnable game, and you complete the shuffle in O(N) time.

Share this post


Link to post
Share on other sites
I think that starting with a finished game brings the same problems because sometimes you won't be able to get the cards to the starting point which is the same as a game you cannot win. You'd have to explore the possible ways to finnally get a playable game. So it's the same as playing the game to find those you cannot win plus you'd have to do all the mechanics to be able to play backward. To create the deck you'd have to randomly choose what to do and finally try to get to a "new game" state.

I think that you won't see a big difference in time and both should be quick to get results. So trying to solve the game feels like the easiest way to do this... as I see it. And occasional gamers either even if it takes 1-2 seconds longer to shuffle a deck

The easy way to solve the game would be the brute force, to try all the different possibilities until you can win or run out of possibilities. (Like in a maze... Explore and when you can't continue, go back and try another path...) If you run out of possibilities the game can't be won so you shuffle and try again until you find a match. More optimal ways would be to define some conditions where you know the game cannot be won and test them as you are goin through the game. Testing for conditions like : if you need that ace of spades to complete the game but you won't be able to move the 5 (of spades) that blocks you because all red 6 are blocked under it too.


JFF

Share this post


Link to post
Share on other sites
Quote:
Original post by jff_f
I think that starting with a finished game brings the same problems because sometimes you won't be able to get the cards to the starting point which is the same as a game you cannot win. You'd have to explore the possible ways to finnally get a playable game. So it's the same as playing the game to find those you cannot win plus you'd have to do all the mechanics to be able to play backward. To create the deck you'd have to randomly choose what to do and finally try to get to a "new game" state.

This was my initial thought as well. The other consideration is that the action space would be huge...going forward, you typically only have two or three possible choices, at any given time. Going backwards, the same is not true. This raises two questions: how do you enumerate the possible moves, and how do you chose among them in such a way that you aren't biased towards certain types of moves? Maybe these aren't such real considerations, I haven't put much thought into it. But it definately seems less straightforward than it appears on the surface.

However...
Quote:
Original post by jff_f
And occasional gamers either even if it takes 1-2 seconds longer to shuffle a deck

That's a mighty long time for shuffling. If a brute force method took that long, I would start looking into more elegant solutions.

CM

Share this post


Link to post
Share on other sites
One of the most time consuming parts of solving a game, regardless of whether you do it forwards or backwards, is to ensure that you never go backwards. By that I mean, not ending up moving a card fomr one pile to another and back again repeatedly, under the mistaken impression that it is still working towards a solvable outcome, when in fact it is not.
This entails making sure that of all the possible moves you consider at each time, discount those which have already occurred in getting you to that point. This duplicate removal will likely be your bottleneck, especially if you attempt to work backwards.

Personally, I'd rather write a FreeCell solver, although there are only a couple of unsolveable variants of those.

Share this post


Link to post
Share on other sites

This topic is 4390 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this