A closer look at the Hole-In-One game

In the last post I looked at the “hole-in-one” game, where the aim was to get an empty column before being forced to deal another row of 10 cards from the stock. I asked the following questions:

What are the chances of winning, assuming perfect play and a “proper” random number generator?
How would you go about estimating it?

The first question was intentionally difficult. It is not trivial to find a perfect strategy, even for this simplified game where the player doesn’t have to worry about what happens after 10 cards are added to the tableau. Even I don’t have a definitive answer. Instead I wanna focus on the second question.

If you know anything about research, you might think the win rate can be estimated by playing a large number of games, tallying up your wins and losses and then doing some basic math to arrive at a winning percentage between 0 and 100. Or if you want to spice things up, you might guess a winning percentage before playing and see how accurate your guess was 😊

In this case, I estimated my win rate should be 30%. I played 30 games (to give myself the chance of an exact guess if I happened to win exactly nine games). Alas I won ten games out of 30, one too many – so my estimated win rate should be 33%.

This figure should be taken with a few pinches of NaCl because:

my sample size of 30 games is small. Ergo, 33% could be an overestimate or underestimate.
Even the noble Spider GM may not have played the perfect strategy, so the correct win rate has been underestimated.
A more subtle point is optimal strategy may change when we only focus on empty columns. In a real game nobody would trash their game in every way possible just for the sake of increasing their miserly chances of getting that hole-in-one from 2% to 3%. In other words, 33% could be an over-estimate of our chances of getting that hole-in-one.

The real point of the exercise is to give the student a feel of how the simplified game works. If you have played 30 (or more) games of hole-in-one you may have come across some interesting decisions. Here is an example:

There are a number of options to consider:

Two of Clubs onto the Three of Hearts, turning over a new card in the only column containing only three face-down cards.
Three of Hearts onto the Four of Clubs, ensuring the previous option won’t decrease our minimum guaranteed turnovers.
Two of Hearts onto the Three of Hearts, turning over a new card in a column containing four face-down cards but building in-suit
Ace of Clubs onto the Two of Clubs, keeping the above options open.

Although a win-rate of 33% is to be taken with a pinch of NaCl we could still conclude that:

If you do obtain an empty column before dealing from the stock then you are probably in good shape
If you don’t get the empty column then you are not necessarily in bad shape. I know from previous experience I can clear all eight suits about half the time sans ROT13(haqb). If you were close to an empty column but didn’t quite make it, you are probably doing okay.

Until next time, happy Spider Solitairing 😊

The Hole-In-One game

This is a simplified 4-suit game designed for beginners. The aim is simply to obtain one empty column. It doesn’t matter if you expose five Aces and seven Kings in the process. Any empty column means victory. The bad news is you’re not allowed to deal any cards from the stock. As usual ROT13(haqb) is not allowed.

The purpose of this game is to allow the beginner to actually win something at Four-Suit Spider Solitaire. More seriously, I think this will help the beginner improve his game by focussing on one concept at a time. As a chess analogy, suppose you wanna teach a child how to play for the first time – unless he, she or it is exceptionally gifted chances are it will be overwhelmed by the sheer complexity of the game. So we could consider simpler games e.g.

Pawns only: you win if a pawn reaches the 8^th rank, or opponent has no legal moves.
Kings Rooks and Pawns only
Kings Bishops and Pawns only
To win, capture 5 enemy pawns or pieces.
… etc

In this way, it will most likely figure out interesting concepts by itself, e.g. zugzwang for the “pawns-only” game or the fact friendly bishops and pawns can protect each other (but rooks and pawns cannot). Although I haven’t tested this method myself (I haven’t even googled), I won’t be surprised if this method actually works.

Admittedly Hole in One ain’t the greatest pun, but “hole” refers to empty column and “one” means no help from the stock – if you need to deal the stock once before getting an empty column that’s a hole-in-two and so on. This means, for example, if an exposed Nine of Hearts is covered by another card, that other card will always be an Eight of any suit.

Here is an example game, with start and end game state shown. This game is lost because there are no legal moves left (apart from dealing another row) and we don’t have an empty column.

Some questions for the reader:

What are the chances of winning, assuming perfect play and a “proper” random number generator?
How would you go about estimating said winning chances?

Until next time, happy Spider Solitaire playing 😊

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.