Game over, we win! (alternative version)

“We made it through the worst,” says Haw. “I was worried that if we drew one more bad card it’s an instant loss”

“Three suits removed, one empty column, this is a shoo-in” says the Dumb Bunny.

“I was wondering,” says the Eagle “Can we prove we are mathematically guaranteed to win?

Ninja Monkey immediately grabs two decks of cards and lays them according to the diagram above, and implements his patented look-ahead algorithm. He has 10,000 wins from 10,000 tries.

“Guaranteed win, no probs” coos Ninja Monkey.

“Not so fast,” says the Eagle. “No matter how many times you win, you can’t prove the game is a mathematical lock with Monte Carlo simulation. Besides, your face down cards were arranged the same way in all 10,000 iterations. We need to prove a guaranteed win regardless of how the face-down cards are arranged”

Ninja Monkey pulls a frowny face.

“I think it is a win,” says the Wise Snail.

“How do you prove it?” asks the Elephant.

I recommended we do the following”, says the Wise Snail

  • 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.”

All the animals are paying their utmost attention. For once, the Wise Snail has been given a chance to truly shine.

“The resulting position is shown below, with the newly-exposed card redacted,” continues the Snail.

“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.”

At last, the Wise Snail had finished his discourse and everyone was convinced the game was mathematically won. Quod Erat Demonstrandum. All that remained was the formality of executing the final moves to remove all eight suits and win the game.

“Remarkable,” says the Eagle.

“Elementary,” replies the Wise Snail.

“But most of the credit goes to Haw,” says the Spider GM. “He used his fantastic analytical skills to find the right moves when all seemed lost.” Spider GM is especially pleased to see his students are helping each other improve with little supervision required.

“And none of it goes to Hem,” sneers the Smart 65,83,83. “He ran away as soon as we were forced to give up our empty column. Nobody has seen him since.”

There’s always one in every group, sighs Spider GM.

Then Haw heard what he thought was the sound of movement. As the noise grew louder, he realized something was coming. Could it be that Hem had turned the corner? Was he about to find out they had managed to win the game?

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.

Look-Ahead Algorithms

By now you’ve all heard the great news: Monkey has proved it is possible to beat Spider Solitaire at the 4-suit level! All he needs to do is build in-suit at every opportunity and never break a suited connector. The bad news is the win rate is extremely low. Of course if the Monkey wins $3000 from the Eagle thanks to a single victory then we’re not complaining – but can we do even better?

First I wanna differentiate between a random hand and a custom hand. Recall that I discussed a number of you-tube videos where random players show off their awesome skills by beating a hand of 4-suit spider sans 85,78,68,79, but the unmentioned caveat was the hand was ridiculously easy.

If I pick a ridiculously easy hand then Monkey wins 6 games in 500, or 1.2 percent of the time. If I pick a random hand then Monkey wins a <sarcasm> whopping </sarcasm> zero games in 500.

So far so bad.

It turned out my simulated annealing/stochastic hill climbing/stochastic gradient descent/something else thingy was a red herring. It worked the first time, but later experimentation with the random number generator showed that “always Level 3” was the best way to go in the long run. But at least it made for a good story lol 😊

Guaranteed Minimum Evaluation Score

Good players (or avid readers of this blog or both!) will be aware of the concept of minimum guaranteed turn-overs. Basically we can calculate the minimum number of cards we are guaranteed to turn over even if the worst possible cards showed up. Of course we can do something similar for e.g. the number of suited connectors or some other “function” of the position. For instance, we might assign 10 points for flipping a card, 1 point for a suited connector and 100 points for removing a complete suit. And of course experienced players know that different programs will have different scoring systems. The important point is that we can (i) evaluate a given position (ii) compute a guaranteed minimum score even if the worst possible cards turned up.

This is an example of “looking ahead” since we are considering the consequences of a single move given the available information (i.e. face-up cards), which is obviously better than making a single move because it’s an in-suit build.

Here is a simple example: suppose the evaluation function was 10 points for exposing a card, 1 point for any suited connector, and no 1-point penalty for each move. Assuming best play in the start position below, what is your Guaranteed Minimum Evaluation Score (GMES) even if you turned over the worst possible cards?

I hoped you answered 54. Note that we are lucky in the sense we can build in-suit 4 times and off-suit once. Normally it’s the other way around.

A good first move is to build in-suit with the Jack-Ten of diamonds. The Ten is on one of six columns with equal-fewest cards and we also have spare off-suit Jack. But we can make many other moves and still come to the same GMES of 54. You could start with the Three-Two of Clubs or even the strange looking 9h-8d. But obviously the sensible option (for humans at least!) is Jd-0d.

The position you should be visualising is the one below, where a happy star represents any face-up card. We can easily check with a single glance that there are 5 turnovers and 4 in-suit builds, with a total evaluation score of 54.

If we want to train our Ninja Monkey to compute the best GMES we can simply iterate random sequences of moves from a given position. But we must be careful not to expose any new cards (e.g. if we shift the Ten of diamonds we will not flip the card underneath). Assuming we have enough iterations, Ninja Monkey will deduce e.g. shifting the Jack of diamonds onto the Club Queen is not a good move since it reduces the GMES from 54 to 53. Even worse would be 0d-9h, which reduces the GMES to 42. We lose one guaranteed turn-over and two in-suit builds with one bad move!

An example of a “good  enough sequence” is:  Jc-0d, 9d-8d, 3c-2d, 0d-98d, Jd-098d, Qc-Jc. Note that the first move was unnecessary but at least we got the correct GMES of 54.

Now Get Off Yer 65,82,83,79 And Start Procrastinating!

A lazy programmer would be satisfied with the above algorithm but of course it is possible to do even better than that. Note that there is no reason to commit ourselves to every move in the above sequence without examining the newly-turned over cards. After starting with Jc-0d, we can turn over a card and we always have the choice of 9d-8d, 3c-2d, 0d-98d, Jd-098d, Qc-Jc or the new card may give us an even better option. In effect we are procrastinating. In summary Ninja Monkey will find a sequence with the best possible MGES and execute it, but terminating the sequence prematurely if he turns over at least one new card.

How do we tell if it’s time to deal a new row of cards? Simples, as the Meerkat would say. If Ninja Monkey cannot increase the GMES then it is time to deal a new row of cards. If the stock is empty then either the game is won or the Monkey concedes defeat.

With the new algorithm, Monkey will beat an easy hand around half the time or a random hand 5 percent of the time. Random Hand statistics are shown in the graphic below

Let us say that a Spider hand is ImportNumbPieAsNP-Hard if Ninja Monkey cannot obtain one victory in 50 tries. In this case roughly half the hands are ImportNumbPieAsNP-Hard. At the other end of the spectrum there was also one very easy hand with 21 wins in 50 attempts. One implication of all this is if a Spider Solitaire server gives 40 ImportNumbPieAsNP-Hard games in a row then there’s a pretty good chance it’s biased.

Unfortunately all this comes at a price. Despite Ninja Monkey’s extremely fast metabolism, this takes a very long time to run.

Empty Columns (a.k.a. holes)

All Spider players know that empty columns (aka holes) are one of the most valuable commodities in the game. Any card can legally move onto a hole (not just Kings). Having a hole means so many extra options for manoeuvring cards. Of course, more options also imply more chance of making a sub-optimal play 😊 In fact, I believe the hallmark of a winning player is the ability to take maximum advantage of holes.

There are three main use cases for holes:

  • Turning over a new card
  • Moving a sequence that is not in-suit
  • Tidying cards so they are in-suit.
How would you play this position?

Examples of the three use cases are:

  • we can turn-over a new card in columns 4 or 5. Further thought shows that column 6 is also possible since the 6-5-4 in diamonds can fill the empty column and the Q can go on one of two kings. Similarly column 3 is another option.
  • We can also turnover column 1. A little thought that if we have at least one empty column any length-2 sequence can be shifted to a non-empty column regardless of suits. This is the simplest example of a supermove.
  • We can also swap the deuces in columns 1 and 8. This increases the number of in-suit builds (3-2 of clubs).

You should immediately notice that options 2 and 3 mean we improve our position for free since we keep the empty column. Therefore option 1 is the worst. It might be tempting to turn over Column 3 so we can get a straight flush in Diamonds but that is a serious error. Not only is the Six-high straight flush the second-weakest of all possible flushes in poker, but having a King in an empty column means we would be a long way from securing another empty column (we need a minimum of three good cards).

Option 3 is also completely safe because it is reversible, so an experienced player will make this move immediately. I am assuming we are only playing to win without regard to score (e.g. -1 penalty per move), otherwise more thinking would be required. Option 2 is the only way to turnover a card without using the hole.

Although option 1 is the worst, most of the time it is available as a fallback option. In other words a hole (usually) implies you always have at least 1 turnover.

EXERCISE: Assume you get 1 brownie point for every suited-connector (e.g. 6-5-4 in diamonds is worth 2 brownie points). From the diagram position above, what is the maximum brownie points you can get without losing the empty column or exposing any new cards?

Again I will use the happy-star method for avoiding the reader unintentionally reading spoilers. For those who don’t recall from a previous post: each happy star represents 1 point in a short story comp, and I have no idea if the judges docked 5 points for the protagonist’s terrible Dad joke.

Did I lose 5 points for a terrible Dad Joke?

Answer: we currently have 8 brownie points and get 2 more (3-2 of clubs and 9-8 of spades).

Well done if you answered correctly (or found an error in my counting). If you aspire to kick 65,82,83,69 at Spider Solitaire, finding opportunities to tidy up suits “for free” must become second nature.

That’s all for now, toodle pip and piddle too 🙂

An example start position

Okay, so I ascii2word([70,85,67,75,69,68]) up. Apparently WordPress automatically converts xx-xx-xx-xx to hyperlinks (e.g. thinking it represents an 8-digit phone number). So instead of writing xx-xx-xx-xx I shall use the notation ascii2word([xx,xx,xx,xx]) instead.

EDIT: This is only relevant for mobile phone devices

By this stage the impatient reader probably wants to see some “action”. Here is a possible starting hand in Spider:

Let us try to find the best move in this position.

I recommend that a beginner player should start by asking the following questions: (i) how many cards are we guaranteed to turn over even if the worst possible cards turned up? Another useful question is (ii) What are the chances that the first new card turned over will be “good”? We will take good to mean “increasing the number of guaranteed turnovers”. Of course there is more to Spider Solitaire than counting guaranteed turnovers but if you’re a beginner then simplicity is the mother of self-improvement … or something like that.

Strictly speaking, it isn’t necessary to ask these questions to arrive at a good first move in the start of the game. If the first two columns are 3-4 of Hearts, then you could move the 3 onto the 4 regardless of the other eight columns: if it’s not the best move then the difference is small. But these questions will be good practice, and it will come in handy as the game progresses.

I hope you answered “Four cards” for the first question. Ignoring suits for now, we have J-0-9 for two turnovers, 7-6 for a third turnover and finally 4-3 for the fourth. Obviously we can’t count multiple turnovers for the three Sixes since we can’t stack them onto the same Seven without violating the laws of physics! Similarly, we only count one turnover for two Nines. Assuming we don’t ascii2word([70,85,67,75]) up the move order, we will turn over at least four cards before being forced to deal another row.

For the second question, there are 13 possibilities for the next exposed card (if we ignore suits). An Ace is clearly useless since we have no deuces, but a deuce I’d like to see since we have a three … okay that’s probably not the best way to start a rap song, but you get the gist.

Continuing in this fashion we get the following good cards: 25780Q. The chances of getting a good card is therefore 6/13. Note that 5 and 8 are especially good since we get two new cards instead of one. But the question defined good as “allowing at least one extra turnover” and it didn’t ask for “how good”. Assuming you have completed Year 3 or better in school, you should know by now that it is always wise to make sure you are answering the correct question! The observant reader may have noticed an error (okay, maybe one-and-a-half errors) in the above calculus. Before proceeding further I invite the reader to figure it out. To protect against accidentally reading spoilers I have inserted an image consisting of happy stars and blank spaces. Each happy star represents a point I obtained for a short story competition I entered some time last year, with a maximum score of 100. Unfortunately I didn’t win anything, not even a Honorable Mention. Perhaps the judges secretly docked 5 happy stars for the protagonist’s terrible Dad joke but we’ll never know. ascii2word([70,85,67,75])!!!!!

The first error is I have assumed each of the 13 cards from Ace to King occur with equal probability. This is not correct since we already know e.g. there are three Sixes and no Fives visible. Hence Fives are much more likely than Sixes. The probability of 6/13 is therefore only an approximation of the true probability of getting a good card. As a general rule, failing to take into account cards already exposed will almost always underestimate the true probability at the start of the game. With only 10 cards exposed, this error will probably not contribute much to All The Problems In The World As We Know It.

The other half-error is we must choose our move before seeing the next card and this may affect our chances for the worse. For instance, suppose we move the Ten in column 8 onto the Jack in column 5. Any Queen is no longer a good card unless the 10 and Jack are the same suit. Fortunately we are in luck here since they are both diamonds. This is why I only counted 1 and a half errors instead of 2. Clearly, moving the Ten onto the Jack is good because we “don’t lose any outs”.

Note that if we moved the Three onto the Four we don’t lose any good cards despite it being off-suit, since if we draw a Five it can still be played onto a Six. But obviously we want a Five to be “very good” (two new cards) instead of “just good” (only one card). This might sound overly technical, but this kind of deduction must become second nature if you aspire to kick ascii2word([65,82,83,69]) at Spider.

Okay, this example fails the Duh Test since one can arrive at the best move by observing it’s the only move that builds in-suit. But my point was to illustrate the concepts of counting guaranteed turnovers and calculating outs.

FUN FACT: Assuming perfect shuffling, a player should have on average 3.96 guaranteed turnovers at the start of every game.