How Can I Win This Game?

In the opening phases of the game we are always concerned with turning over new cards and building in-suit. But in the middle-game or end-game things are different.

By this stage a decent player will be able to evaluate the position. After performing some multi-dimensional calculus on the back of an envelope, he she or it will be able to estimate winning chances and decide on a plan of action.

Unfortunately, an in-depth discussion of multidimensional calculus is beyond the scope of this post but a useful general principle is the following:

If things are going okay, we should continue to play our normal game. Turn over new cards, build in-suit whenever possible, and start thinking about removing complete suits.
If the game is going badly, start looking for miracles. You need them to win, and miracles never occur if you don’t look for them.

Conversely if the game is going extremely well, you might consider playing safe, but that’s another lesson for another time.

In the diagram position you don’t need a Grandmaster Title from the International Federation of Spider Solitaire to work out the prospects are bleak. The stock is exhausted, several cards are yet to be exposed etc, etc. But all hope is not lost if you excuse the terrible cliché. We can quickly obtain an empty column and turn over cards in columns a or h. Since we probably need good cards to win, we might ask ourselves “if we could call the next card what is the best case scenario when turning over column a or h?”

A closer look reveals all cards in the Spade suit are already exposed. Assuming we focus all our effort into removing a full suit of Spades how much luck do we need? Perhaps a good card or two in column a, or perhaps we can tidy things up a little and hope for luck on the next deal – no scratch that, the stock’s already empty.

It turns out we don’t need any luck – it is possible to remove the Spades without exposing any new cards. Of course, we need to expose cards to win the game eventually, but the point is we are guaranteed to remove Spades regardless of the permutation of unseen cards. One sequence would be: is <bg, id, ih, ia, jf, dj, cd, ch, jd, cj, d2=j1, hc, hc, fg, fd, fh, fa, d1=f1, f2=h2, hc, cj>. Whoosh – the Spade suit goes onto the foundations!

If you found this sequence of moves well done. Of course, it might be possible to do better than that – remembering that removing one suit is not synonymous with winning the game. But at least it’s a fallback position: we can choose this option if we find nothing better.

Avid readers might have recognised the exact same position from an earlier post, and would keenly deduce the game is winnable since I managed to beat it without undo. If you spotted this then again well done 😊

Spider Solitaire Notation

When discussing a sequence of one or more moves it is clearly more convenient to say something like “<ac>” rather than “move the Jack of Hearts from column 1 onto the Queen of Diamonds on column 3.” This is especially true when we talk about long series of moves to achieve a desired goal such as an empty column or increasing the number of in-suit builds.

Steve Brown has developed his own notation for moves in Spider Solitaire in his excellent book Winning Spider Solitaire Strategies. The notation is theoretically sound, but I think it is rather technical and counter-intuitive for most players so I decided to make some slight variation of it. I prefer to illustrate important strategy concepts through the use of silly stories 😉

Most of the time, specifying a source and destination column is enough to uniquely identify a legal move. For instance if the top cards of columns 1 and 3 are a Seven and Jack respectively, then we know that exactly four cards are being moved from column 1 to column 3 (unless the move is illegal). But there are one-and-a-half exceptions.

The one exception occurs when the destination column is empty, in which case the number of cards being moved may be ambiguous (of course most of the time you wanna move the maximum number of cards to avoid losing an in-suit build). The half-exception concerns the use of supermoves. Many players will be familiar with the concept of supermoves from Freecell and they turn out to be very convenient for dealing with longer move sequences.

I will use the letters abcdefghij to denote the ten columns from left to right. Therefore the simplest example of a supermove could be <ab2,ac5,bc3> to shift five cards from column 1 to column 3, assuming 2,5,3 represent the number of cards being shifted for each individual move. Of course most of the time the numbers are unnecessary so it is simpler to write <ab,ac,bc>. The supermove notation is <ac> in lieu of <ab,ac,bc>. Going back to an earlier example, if the top cards of column 1 and 3 are a Seven and Jack respectively then <ac> means we are shifting exactly four cards. If they are not suited then we check if the conditions for a supermove exist (for instance we might have an empty column and a spare Nine).

A related concept is superswap where we want to swap the partial contents of two columns. For instance if we have 8C-7D in column 1 and 8D-7S-6S-5S in column 7 then it might be desired to swap the 7D with 7S-6S-5S to build in-suit with 8D-7D. This can be notated as <a1=g3>. Obviously, this can only be achieved with a spare Eight of any suit or an empty column.

With more empty columns and cards in play deeper superswaps are possible. It is not hard to imagine a move like <c6=g8> to tidy up suits, which might take over 30 individual moves to achieve. Note that without the numbers 6,8 there may be ambiguity with e.g. <c5=g7> or <c4=g6> etc.

In the example below we might start the game with <eh>,<ji> for two in-suit builds. Assuming the exposed cards are 4D and 3D respectively the third move could be <ie>, which is also in-suit.

notationexample-05172020

You may have noticed the use of angle brackets – these correspond to single actions, i.e. move sequences that expose at least one new card. For example <eh>,<ji> means we shift the Seven of Spades, examine the card underneath and then decide the best move is to shift the Four of Clubs. If we ignored the face-up card underneath the Seven of Spades, then the notation would be <eh,ji> which is technically not an action (although the loss in “equity” is very small).

Until next time, happy Spider Solitaire playing 😊

Four-suit Master Level – let’s do this!!!

Another working day over and done with, I guess it’s time to play a 4-suit hand at Master level 😉

Avid readers of this blog may recall I discussed the difference between an “expert” level and “grandmaster” level hand – but conveniently omitted the “master” level which is somewhere in between. Recall that Microsoft Spider Solitaire gives the player the option of choosing a difficulty level as well as number of suits. In this case we know (before touching a card) that

The game is guaranteed winnable
The difficulty should be “average” because 4-suit hands have four difficulty levels namely: expert, master, grandmaster and random

A cursory analysis of the opening position suggests our prospects are good: we have five guaranteed turnovers (only one in-suit but we can live with that), and we have nine different ranks (only Fives are duplicated). If this were a random deal, I would consider myself a favourite to win this game, but at master-level difficulty I’m not so sure.

This could be a “honey-trap” – Microsoft may want to encourage players to accept whatever starting hand they get, and then unleash a surprise or three on the next 30 cards in the stock 😉 (players can refuse a starting hand without having a loss officially recorded in their stats, but I always play every hand). However I’m not making any accusations of foul play without any concrete evidence. This could be a future project, but for now let us focus on winning the game.

start-05132020

FUN FACT: if the opening hand contains ten different ranks we are guaranteed at least six turn-overs with proper play.

Easy Difficulty

Continuing my experimentation with Microsoft Spider Solitaire, I decided to try five hands on Expert difficulty level.

Recall that Expert is the easiest possible setting when you play with 4 suits. We therefore expect Expert hands will be easier than random hands.

Indeed when I tried playing Five hands at Expert level I crushed it. I won the first four hands and probably should have won the fifth, but for a lapse in concentration.

Getting trips (or even quads) when dealing a row of 10 cards occurred very rarely, and I had a healthy number of turnovers in round 0. Once I removed two complete suits the game was pretty much in the bag.

However, I should emphasize that removing two suits most definitely does not guarantee victory for Grandmaster level. And don’t get me started on Rogue Solitaire.

Recall that in a previous post, I ran the Gauranteed Minimum Evaluation Score on hands of various difficulty. Ninja Monkey said that he could win 4 Experts hands out of 50, but zilch on Master and Nada on Grandmaster.

I haven’t experimented with what various difficulty levels look like with fewer than 4 suits. Perhaps that’s some material for a future post 😊

Personally I like the idea of giving players the option of choosing a difficulty level as well as number of suits, and Spider Solitaire lends itself to this type of choose-your-difficulty. In contrast, the same cannot be said of games like Klondike or Freecell (one-suit is perhaps too easy even for a newbie)

Until next time, happy Spider Solitaire playing.

Choose Your Difficulty

The classic Microsoft Spider Solitaire software gives a Four-suit expert player a choose between Expert, Master, Grandmaster or Random hand.

With the pandemic not going away any time soon, I thought now is a good time to play three more hands of Spider Solitaire on my PC, choosing difficulty levels of Expert, Master and Grandmaster (while also honing my writing skills!). I easily won an Expert hand, but bombed the Master hand. I briefly entertained some miracle hopes on the Grandmaster hand, but quickly came crashing down to earth if you excuse the terrible cliché.

Ninja Monkey’s Guaranteed Minimum Evaluation Score algorithm yields a win rate of 4/50 on the Expert but 0/50 on the Master and Grandmaster hands.

Here is the Grandmaster board:

Round 0 looks promising with 4 turnovers (the average should be a tad under 4). Moreover, two of these turnovers are suited – but problems appear later.

After a promising initial deal it’s trips galore in almost every round. This reeks of a cold deck – if you’ve ever played late-night poker with some dodgy folk in the neighbourhood then you’ll know what I’m talking about. Then again, I did ask for Grandmaster difficulty.

In contrast three of a kind never occurred in any round of the Expert hand.

It is not clear if arranging three of a kind on nearly every round is an effective way to make the game harder (maybe the permutation of face-down cards in the tableau is also relevant) but it does suggest Microsoft is trying. In defence of Microsoft, they explicitly made it clear that the player will face a difficult challenge to win without boop. In fact I have no problem with the game being “rigged” if the player knows in advance the cards are not properly shuffled (in math terms we say a properly shuffled deck has 104! possible permutations of starting hands, ignoring equivalence of identical cards, and each permutation is equally likely). A player who chooses Grandmaster difficulty can’t say he wasn’t warned!

I will not discuss the strategy in detail. Rather I wanna discuss how easy it is for Microsoft to construct “easy” or “difficult” hands.

There are several ways one might go about constructing a difficult hand:

“Crowdsourcing”: give each hand a unique identifier (like a hash). If only e.g. 10% of players can win even with the help of boop, then chances are the game is difficult. If a good percentage of Microsoft employees like to slack off in their spare time this shouldn’t be too hard 😊
Design an evaluation function e.g. number of guaranteed turnovers for Round 0, or number of guaranteed turnovers if we pretend we start with the 10 cards in Round 3 instead of Round 0. The main difficulty is finding a good evaluation function.
Design an AI to play the game with or without boop. The main difficulty is designing a good AI is not trivial.

It is not clear which method Microsoft uses (my best guess is crowdsourding), but I agree they succeeded in arranging matters so that Grandmaster is harder than Expert (Master is perhaps equally hard as Grandmaster but I only have a sample size of three games, so I won’t jump to conclusions any time soon!)

Estimating the difficulty of a Spider Solitaire hand (continued)

Continuing from last week, our task was to evaluate the probability of winning the following starting layout.

I find the best indicator of probability of winning is “playing the hand out”, either manually or getting one of my animal friends to do it, such as Ninja Monkey.

For instance, I might attempt to win the game without boop but during the course of play I have a chronic shortage of Nines and lose badly. I would then examine the starting layout and say to myself “okay, now I understand why I got a shortage of Nines.” The point I am making is that it’s much easier to identify potential problems after playing the hand out. Conversely, I might be able to clear two suits before dealing the second row of cards and guess the game is extremely easy.

In our example above, we can check there are three guaranteed turnovers at the start. The middle row from the stock has four kings, but I still managed to win without boop. However, during the mid-game I estimated a loss was almost certain. For this reason, I would estimate the game to be “maximum difficulty” or close to it. Unfortunately, this assessment is hard to convert into a number.

Fortunately, Ninja Monkey can help me out here. He can simply simulate his improved strategy. Essentially his strategy involves optimising the guaranteed minimum evaluation score given the information provided by face-up cards – and it is good enough to win random deals some of the time (i.e. not ridiculously close to zero). Ninja Monkey’s assessment may not be accurate (his strategy still has serious flaws) but at least we get a “quantitative” estimate (probability of winning) rather than some qualitative 83,72,73,84.

It turns out Ninja Monkey could win 2 trials out of 50. To be honest, I was expecting zero wins from 50 attempts (of course the win rate should be non-zero given enough attempts since I did manage to win).

I believe a player should be awarded a Doctor of Spider Solitaire if he can beat a hand without boop even though Ninja Monkey estimates a win rate of 0/50 with his guaranteed minimum evaluation score algorithm

Estimating the difficulty of a Spider Solitaire hand

We now consider the following question: Given a Spider Solitaire hand, how can we determine the probability of a human expert winning without 85,78,68,79?

Clearly, we have to determine the identity of every face-down card (barring pathological cases where the hand is so bad you can mathematically prove certain defeat without knowing all the cards). The good news is this should almost always be possible given enough patience (and skill).

The bad news is estimating the difficulty of a hand is far from trivial.

I know that the first 10 cards dealt is a poor indicator of winning chances. Yes, most players will get a warm fuzzy feeling if the opening hand gives six guaranteed minimum turnovers and three in-suit builds – but Spider Solitaire is a marathon not a sprint (terrible cliché I know) and there is plenty of opportunity for a good start to sour, or conversely, to recover from a poor start. Other features like “four Queens in the third deal” or (heaven forbid) “all odd cards in the fourth deal” are likewise unreliable indicators – we usually have to consider the whole board. The only exception is if there are no two adjacent cards on the final row of 10 cards (e.g. A44A7499KJ) – in which case the game is automatically lost unless you get a lucky in-suit build (e.g. the Jack falls onto a Queen of the same suit).

Here is the starting hand of the game I played many months ago and finished last week (a minus sign indicates a face-down card and rows from the stock are dealt starting from the left). Can you think of any “features” that would indicate whether the game should be easier or harder than normal? Let me know in the comments below!

(To be continued …)

Game over, we win!

Continuing from the previous post, the recommended action is

Clear the Spade suit
Exchange the 6-5-4-3-2-A of Hearts in Column 5 with the 6-5-4-3 of Clubs in Column 6.
Dump the 9-8 of Clubs in Column 3 into the empty column
Clear the Heart suit, winning back the empty column
Shift the Qh-Jd onto the Kh in Column 1, turning over a face-down card in Column 6 (and keeping an empty column)

Note that I went to the extra effort to clear a card in Column 6 rather than Column 5. This is because clearing cards in Column 6 is harder than Column 5 (especially since the Q-J are offsuit). As a general principle it is often wise to save an easy task for later and get the “difficult task” over and done with whenever possible – this helps avoid the embarrassing situation of “One Hole No Card” as alluded to in a previous post.

The resulting position is shown below, with the newly-exposed card redacted.

This is a lock

The astute reader may have noticed I violated the principle of procrastination by removing the Spade suit unnecessarily. This is because the game is in fact mathematically won.

To see this, let us consider all possible face-down cards (which we identified from last week):

Queen of Clubs: this can go “underneath” the Jack of Clubs (Jack onto Queen, winning an empty column, Q-J to Column 8, losing an empty column)
Queen of Diamonds: this goes onto the King of Clubs
Ten of Clubs: this goes onto the Jack of Clubs
Ten of Diamonds: this goes onto the Jack of diamonds
Ten of Hearts: this goes onto the Jack of Hearts
Nine of Diamonds: this goes underneath the 8-7 of Diamonds
Seven of Clubs: this goes onto the Eight of Clubs
Six of Hearts: we will count this as a “bad card” since the 7 of Diamonds is offsuit (and will counterfeit the Nine of Diamonds). This goes into the empty column
Five of Hearts: This is a bad card and goes into the empty column.

Note that the first seven cards are good, and we don’t even require an empty column to achieve the corresponding action. The only possible snag is there are two bad cards and only one empty column. But wait! If we draw both the Five and Six of Hearts then we can immediately place the Five on top of the Six. The net effect is to condense two bad cards into one – hence there is no snag after all.

Finally we also check that there is no issue with one-hole-no-card. Assuming we turnover all cards in Column Six first we will eventually get an empty column in Column Six and then we can choose randomly between shifting the Jh in Column 2 or the 9-8-7 of Hearts in Column 5 into the new empty column. Essentially we are “pretending” that all nine face-down cards are in Column 6.

It turns out the redacted card is the Seven of Clubs. The rest of the face-down cards in Column 6 are: Ten of Diamonds, Queen of Clubs, Queen of Diamonds.

The starting layout is shown below

Summary

This was a difficult game. The first ten cards were average, a minimum of three guaranteed turnovers, but two in-suit builds and no Aces or Kings. I only turned Four cards in round 0, but had an excellent Round 1 with several turnovers thanks to an empty column, but then got a catastrophic middle game with four Kings appearing on the same deal. Just when a loss seemed certain, I managed to find chances by clearing a complete set of Spades. I procrastinated by waiting until both Spade Kings were exposed so then I could decide which was the better King to remove. On the last round, I had three guaranteed turn-overs and realised all hope was not lost. I survived kadoban in the endgame and managed to win. I worked out victory was mathematically certain with only nine face-down cards remaining.

I hope you enjoyed playing through this game as much as I did.

Game on (25 March)

I cleared the Spade suit in order to tidy the suits up (e.g. K-Q of hearts and K-Q of Spades).

I then turned over the last card in Column 1, and it is the Ten of spades.

Good Luck at Last

At last we get a good card. We can start turning over cards in columns 4 5, or 6. We also have a most unusual situation: all cards of the second Spade suit are visible, but we are still waiting on the first set of Clubs and Diamonds. So a useful question to ask is “can we clear Hearts or Spades by force?” and if so, is that even desirable?

Assuming we claim the empty column in Column 1 (the move is reversible) we see columns 4 and 6 require us to burn only 1 empty column, but Column 5 requires both empty columns. Our choice is therefore between Column 4 or Column 6. The 6 of Hearts in column 4 seems useful since it will help with Column 5. The two aces in Column 6 are not so great (but would be useful in Texas Holdem). Column 4 it is.

Our luck is in. We are able to clear all face-down cards in Column 4. The face-down cards are (in order): 10 of diamonds, 7 of Clubs, 9 of Diamonds, Jack of Hearts. Not surprisingly we are able to remove two more complete suits.

Now is a good time to take stock. We have the following position:

We can continue with 9-8 of Clubs into the empty column, then remove the Heart suit, turning over a new card in Column 5 and winning back the empty column. This means we are guaranteed to turn over at least two cards (phew, no Kadoban). Careful consideration reveals another possibility. We can use the Nine of Hearts in Column 6 instead of Column 5, then shift the Qh-Jd onto the Kh in Column 1. Oh yes, the second spade suit is also up for grabs.

Do we have a lock?

At this stage, we should be calculating if the game is mathematically won regardless of the distribution of the face down cards. A good start would be to identify the face down cards:

Clubs: 7,0,Q

Diamonds: 9,0,Q

Hearts: 5,6,0

Spades: None

Question: do you think the game is mathematically won with best play?

Game on (18 March)

The unseen cards are shown below

At a glance we can tell that it is impossible to complete a suit of Diamonds or Clubs because there is no exposed Seven of Clubs, Nine of Diamonds or Ten of Diamonds. We can remove one Spade suit, but both Spade suits is clearly impossible. Hearts are impossible with both the only exposed Jack and Six underneath a King, and we only have one empty column. Clearly we need to turn over new cards and hope for the best.

The Danger of One-Hole-No-Card

Although most of the cards are good we have a new problem. There are only three “easy turnovers” in Columns 1 and 8 – and that is assuming we do get good cards. Once these easy turnovers run out, we may well be in serious trouble.

This phenomenon is not unusual. At the beginning of a game, our primary focus is getting an empty column so we usually have to put up with “junk piles” like columns 4,5,6. But during the endgame, we wish we didn’t have many face-down cards buried underneath these junk piles. So there is a trade-off between hunting for empty columns and avoiding awkward junk piles in the endgame. It is beyond the scope of this blog to discuss how to manage this trade-off in detail. I could spout horrible clichés like “you get better with experience” but I would rather lay down the following general principle:

If you ever find yourself unable to expose a face-down card despite having one or more empty columns, then chances are you are not taking maximum advantage from a position of strength.

In our case, we desperately need very good cards, not just average cards. Fortunately any one of five unseen Tens would fit the bill. Any Ten can play onto the Jack in Column 3, and then we can start to work on Column 6. Alternatively if we expose a Seven of Clubs, then we have legitimate hopes of removing a complete suit of Clubs.

My first action is 5 of Clubs onto 6 of Clubs in Column 2, exposing the 3 of Spades.

Next action is 3 of Spades onto the 4 of Spades, exposing the 7 of Diamonds. This may be a problem since it is harder to expose cards in Column 6 (but there wasn’t much choice).

To simplify matters, I will tidy up the suits by making reversible moves only (even though it’s not an action reversible moves are always safe if we are not aiming to win in the fewest moves).

Note that it is not possible to swap the Kh-Qs in Column 3 with the Ks-Qh in Column 10, unless we remove the Spade suit first.

Despite having one suit removed and two empty columns (assuming we remove the Spades), our position is now very bad. We did not get any of the missing Tens or a Club Seven, and exposing the last Three counterfeited the Three in Column 6. This means it is impossible to turn over any cards in Columns 4 5 or 6, even if we were willing to give up both empty columns. This means we must expose a card in Column 1 or Column 2 (but not both) and hope for the best.

Our position is in fact Kadoban – one more bad card equals game over. There are two basic choices:

Turn over a card in Column 1
Turn over a card in Column 2

Note that both cards in Column 1 and 2 are not possible, even if we clear Spades since we need three empty columns.

Taking the dangers of One-Hole-No-Card into consideration it is quite possible that the latter option is better, despite losing both empty columns. What would you play here?