Game on (29/Jan)

We got some good luck here. We obtained an empty column and also some useful cards such as the Ten of Spades and Five of Clubs.  This means we are significantly better than the minimum guaranteed turnovers calculated from last week. Now is a good time to evaluate options.

We have two guaranteed turnovers at this stage. The empty column is clearly worth one turnover and we can also expose a card in column 2 or 9 (using the fact column 1 is missing a Five). It is of course desirable to keep the empty column as long as possible, so we identify two basic choices: (i) build 0s-9c-8c, 5c-4c or (ii) insert 5c between 6c-4h-3d-2d-Ad.

Note that the first option will kill column 3: it will no longer be possible to build Qc-Jd-0s and we would “regret” seeing a Nine. A third option is to shift the Jd-0s onto the Qc first before turning over column 2 – but then we would regret seeing a Jack. The other problem is that we also lose the option of shifting the 9h-8c in column 6. If we expose a King then that would really 83,85,67,75.

Unfortunately it is not possible to procrastinate by shifting the Five of Clubs directly onto the empty column since we cannot recover the empty column if a bad card turns up (but it would work if it was the Five of Hearts).

There is another sneaky option available: Suppose that we shift the 7h-6c in column 1 onto the 9c-8c in column 2 (thus breaking an in-suit build!) before inserting the 5c into column 1. The logic is that we are guaranteed to recover another in-suit build with 9h-8h (at the expense of the empty column). If you spotted this possibility then you are already above beginner level. But for most folk, it is sufficient to know that the number of options to consider increase dramatically when you have an empty column.

What would be your play here?

Look-Ahead Algorithms (alternative version)

The Gospel, according to Spider GM

In the beginning there was the Ninja Monkey.

And there were two decks of playing cards.

And the cards were without form or structure. There were no descending sequences like Nine-Eight-Seven-Six or the like, and the red and black cards did not always alternate. Ten of the cards were face-up but the rest were face-down.

On the first month Ninja Monkey arranged the cards into eight sequences from King to Ace. And Ninja Monkey saw that it was Awesome. He wasn’t able to obtain eight sequences every single time, but with a success rate of over sixty percent it was Awesome nonetheless. Spider GM published a paper in collaboration with Ninja Monkey and he also thought it was Awesome.

On the second month Ninja Monkey arranged the cards into eight sequences from King to Ace, and in suit for the first time. Everybody in the Animal Kingdom saw that it was Awesome, except the poor Eagle who lost $3000 on a single (uncharacteristically) ill-judged bet. Ninja Monkey found that he could beat an easy hand 1.2 percent of the time or a random hand a <sarcasm> whopping </sarcasm> zero percent of the time. But despite the low success rate it was Awesome nonetheless.

On the third month, all the other animals realised it was possible to beat Four-Suit Spider Solitaire sans 85,78,68,79. They played more often and discussed possible strategies with each other. Eventually their skills improved. The Eagle had reconciled with Ninja Monkey and was able to win about 20% of the time. Others maybe 5 to 10 percent. Even the Bad Idea Bears managed to win the odd game or three. Only the Wise Snail (the slowest player, who is yet to complete a single game) had a zero success rate. But they all agreed it was Awesome.

On the fourth month, Ninja Monkey experimented with look-ahead strategies. Ninja Monkey saw that he could find a move that maximised the Guaranteed Minimum Evaluation Score, even if he turned over the worst possible cards. He was able to 75,73,67,75 65,82,83,69 with “easy” 4-suit hands but still struggled with “random” hands only winning 5 percent of the time. Although Ninja Monkey took a lot longer to complete a single hand, nobody gave a 70,85,67,75. It was Awesome.

On the fifth month the other animals were able to learn the Ways of the Ninja Monkey and speak his language. For instance, it was common to start a monologue with “Import Numb Pie as N. P.” and end it by clicking their fingers. If an animal didn’t have fingers to click they could improvise by clicking their tongues.  It was awkward at first but they eventually saw that the new language was indeed Awesome.

And on the sixth month, Ninja Monkey found himself a girlfriend. And they both saw that the other was Awesome. Ninja Monkey was voted as the leader of the Animal Kingdom (instead of the Eagle who won too much $$$$$$$$ at the late-night poker sessions). That was Awesome too.

Ninja Monkey said “Behold, I have given you ten thousand decks of playing cards which is upon the face of the entire animal kingdom. To you it shall be for entertainment”.

And on the seventh month Ninja Monkey rested from all his hard work. He was no longer bullied during Spider Solitaire lessons and all the animals bowed before him.

And they both partied 78,65,75,69,68, the Monkey and his girlfriend, and were not ashamed.


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.

Game On (22/Jan)

Continuing the game from last week …

In round 0, I managed to turnover four cards. This is slightly disappointing, given I was guaranteed a minimum of three. I got a Jack and three even-numbered cards.

Note that I was careful to ensure the 7h-6c was moved onto the Eight of Hearts in column 1 instead of column 5. This meant that I would not “lose an out” if a Ten turned up. The only meaningful question was whether the Jack of Diamonds should be moved to column 6 or 9 before dealing another round, but this rates to be a coin flip. The diagram below shows the position before and after dealing another round

That’s not so bad. We are guaranteed at least four turnovers, two of which are suited. It seems I guessed right by moving the Jack of Diamonds onto the Queen of Hearts in column 6: if I chose column 9 then I would only be looking at three turnovers.

Further good news: two of our turnovers will be in column 7 and 10. We therefore have a reasonable chance of obtaining an empty column.

Four turnovers can be obtained with columns 3/4/9/10 or 3/7/9/10. It is important to turn over columns in the correct order. For instance column 10 must be turned over before column 4 (or 7) and column 9 must be turned over before column 8, etc. If we choose column 7 that must be turned over before column 9. This might sound overly technical but if you’re serious about improving your game you must aim to reach the stage where this analysis becomes second nature.

Note that it is impossible to build in-suit with 4d-3d unless a good card turns up. However at this stage it is more important to focus on empty columns. Once we get an empty column or two, the 4d-3d in-suit build will take care of itself.

It seems the best move is to turn over a card in column 10. This would “cost an out” if we turn over a Five, but there is nothing we can do about that. Other options would also lose an out or violate the principle of procrastination.

Spider Solitaire Cube revisited

In an earlier post I mentioned “Spider Solitaire Cube”, a version of Spider where players can compete for real money by playing against each other. There were a number of negative reviews claiming the game is rigged in various ways. Not surprisingly I was wondering if I can prove the deals are rigged using the Ninja Monkey’s random move algorithm.

One problem is that I had to set up an account just to test the theory. So I came up with a great idea: Spider Solitaire Cube has “practice mode” as well as “real mode”, so instead of trying to prove the deals in real mode were significantly harder than random then maybe I could prove the deals in practice mode were significantly easier than random. This idea might seem surprising at first, but if you can learn to think like an Awesome Person this can hopefully become second-nature. With practice mode I avoid the inconvenience of setting up a PayPal account just for the sake of doing “research” that is not going to advance my actual work career in any way.

Unfortunately there is a more serious problem: games are played with a 5 minute time limit. Thus if I cannot beat a difficult hand within that time period then it is impossible to work out the starting layout, and hence impossible to give the correct input to Monkey’s random move algorithm – hence the whole experiment becomes impossible.

So unless I can take my lateral thinking to the Next Level Of Awesome, it seems I have to reluctantly delete the Spider Solitaire Cube app after downloading it like half an hour ago ☹