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.

Improved Monkey Algorithm

Every man dog and millipede in the animal kingdom knows by now Monkey’s famous random move algorithm is good enough to beat Spider Solitaire at the one-suit level more than half the time.

However there are a number of Spider Solitaire servers which seem to stack the cards against good players and the Monkey’s algorithm is too weak to “expose” them. I have played a number of hands which I consider difficult, yet Monkey kills at the 1-suit level. The “Opaque Spider Solitaire Server” that I referred to some time ago happens to be an exception. To cover my 65,83,83 I am not naming any servers without a p-value that is five percent or worse.

In the Monkey Algorithm, every move can be identified by specifying two columns (source and destination). Let us assume that if the destination column is empty then we move the largest possible number of cards from the source column. Thus if the source column starts with 3-4-5-6-7 in spades followed by an off-suit 8, then we move five cards. In this way, specifying two columns always identifies a unique move (assuming it is legal).

Note that it is possible to break an in-suit build. For instance if the source column has 3-4-5-6-7 in-suit and the destination column has an off-suit 6 then we are breaking in-suit.

One possible idea is to forbid the monkey from ever breaking in-suit. This means e.g. if we have built a J-Q of Spades then those two cards are forever joined together. The only exception is if we separate the Jack onto the other Queen of Spades (recall that Spider is played with two decks of cards). This means the number of suited builds never decreases. For the mathematicians among you, this is an example of “entropy” – a quantity that is guaranteed to never increase (or never decrease) which can serve as some measure of how close we are to a desired goal.

One problem with this rule is the Monkey will often get less in-suit builds then he should. Recall that the first Project Manager started a game with 2H/AC, 2D/AS 5D/4S, thus forfeiting the option of building in-suit with 2H/AH (If a project manager can 70,85,67,75 that up, what chance does a mere monkey have?). Therefore we might tell the monkey to always choose a move that increases the number of suited builds, or if no such move exists then choose a random move that does not decrease the number of suited builds.

Too Much of a Good Thing

Sometimes it is better to build off-suit than in-suit for the sake of some other gain (such as turning over a hidden card). In rare cases one might even be justified in breaking an in-suit build(*). We can experiment with a mixed strategy where Monkey will look for an in-suit build say, 90% of the time or off-suit 10% of the time. This way, Monkey should increase the number of in-suit builds in the long run, but still have the opportunity to take care of situations where off-suit happens to be the better play.

(*) A simple example: Consider the task of moving a sequence 5S-4H-3H-2D onto a Six of any suit, assuming you have one empty column and a “spare” Four of Clubs, and all other columns have picture cards.

In summary we have four different algorithms (which I refer to as levels) where moves are chosen randomly subject to constraints below. For the last level we have to specify a parameter determining the probability of choosing Level 3 or 2.

NOTE: We ignore other parameters such as number of moves before dealing a new row of 10 cards.

  • Level 1: Monkey can break in-suit builds
  • Level 2: Monkey never breaks in-suit builds
  • Level 3: Monkey will always build in-suit if possible, otherwise it will maintain the status quo (i.e. not break an in-suit build)
  • Level 4: With probability 0<p<1, choose Level 3, else choose Level 2.

NOTE: Moving e.g. the Nine of spades onto the Ten of spades is not building in-suit if the Nine is already on the other Ten of Spades.

Experiment

To test these algorithms, I chose the game [1]. Monkey’s 1-move algorithm says this is a relatively easy hand with an equity of 0.88 if the game is one-suited.

[1] https://www.youtube.com/watch?v=5b9SxWEZpbI

I recorded the number of wins and the average number of suits removed. The probability value is some multiple of 0.1

The important bit is the last row. If we choose level 3 with probability 0.9 then Monkey actually manages to win 1 game in 200. Admittedly this is terrible by Project Manager standards, but it’s not too shabby for a Monkey!

Level Number of wins Average suits removed
1 0 0
2 0 0
3 0 0.065
4 (p = 0.1) 0 0.015
4 (p = 0.2) 0 0.01
4 (p = 0.3) 0 0.04
4 (p = 0.4) 0 0.035
4 (p = 0.5) 0 0.04
4 (p = 0.6) 0 0.1
4 (p = 0.7) 0 0.06
4 (p = 0.8) 0 0.065
4 (p = 0.9) 1 0.095

You might ask what makes p = 0.9 work so well? (recall that 1 win in 200 is pretty good by Monkey standards) The simplest explanation is by way of analogy with a ball rolling down a hill. The y-axis represents the number of in-suit builds we need to complete the game. Thus if we reach 0 in-suit builds required then we always win.

rolling_ball

Suppose at any point the ball is only allowed to “look” within a local neighbourhood. You have three options:

  • Move randomly
  • Always take the local minimum
  • Take the local minimum with 90%, move randomly with 10%

A little thought should convince you that the latter option is the best. I will not go into the detailed programmatic or mathematic specificity. Doing any programming or mathematical 77,65,83,84,85,82,66,65,84,73,79,78 is left as an exercise for the reader!

Artificial Stupidity in Chess

You may remember some time ago I discussed an algorithm for Spider Solitaire that is not very good: it simply outputs random moves. It turns out somebody did a much better job in the game of chess. Some dude designed no less than 30 Artificial Stupidities and organised a Tournament of Fools, and published a number of papers in SIGBOVIK. Ideas for weird algorithms include color preference (e.g. White prefers to play pieces onto light squares), random moves, blindfold algorithms (simulating a novice trying to play blindfold), algorithms based on mathematical constants like π and e, single player (pretending opponent will pass) and linear interpolation between Stockfish and some other lousy algorithm (e.g. choose Stockfish’s best move with probability p, lousy move with probability 1-p. But my favourite algorithm was the Mechanical 68,79,82,75 that proved a forced win for Black after 1 d2-d4?? a7xd4!! checkmate 🙂

You can watch all the fun in the video below:

I’m not sure if these ideas will be applicable to Spider Solitaire. Color Preference is easy since we can prefer to move red cards or black cards, and single-player is even easier given the nature of the game, but I am not aware of any equivalent of Stockfish. Mathematical constants should be easy but probably not very interesting. It may be possible to simulate a blindfold (human) player who struggles to remember every card, but I’m, not sure how to do that yet. And I don’t know of a (sensible) variant of Spider Solitaire where all the red cards are replaced with chess pieces. Since Western chess has Black vs White, it may be more appropriate to use Xiangqi, which has Red vs Black pieces. Perhaps something to think about for next time.

Thanks to my good friend Tristrom Cooke for the heads up.

Introduction to the Monkey Algorithm

If you are reading this blog you probably have some familiarity with my friend Ninja Monkey by now. If you are not reading this blog … then that will just be weird.

As a brief reminder, the monkey looks like this:

The monkey plays really fast, but his strategy is not very good because he simply makes random moves. Now let us try to define a random move strategy.

The simplest random move algorithm is:

  • At any game state, enumerate the set of all legal moves
  • Assume each move occurs with equal probability

For instance, suppose we started a game with 44445555JK. There are 16 possible ways to move a Four onto a Five and we also have the option of dealing 10 cards from the stock. That gives 17 moves total, so each move occurs with probability 1/17.

As you might expect, the random move strategy doesn’t win too many games at the 4-suit level. So we will start with the 1-suit level.

We first observe that dealing from the stock is usually undesirable unless “no further improvement is possible”. So we can impose a move limit of, say, 1000 moves and specify the monkey must deal a new row whenever the move counter is a multiple of 1000 (if there are no legal moves then keep passing until the move counter reaches a multiple of 1000).

We all know that when a player has, e.g. 4 suits removed and all cards exposed the game can pretty much be won on autopilot. However making random moves can be problematic. Consider the following game state, which is about as easy as it gets for an experienced player:

In this diagram even my Dad can win this game in one move. However, let us count the number of legal moves available.

Assuming we don’t win in one move, the stack of 8-7-6-5-4-3-2-A can be moved to any of eight empty columns. Similarly the other stack of K-Q-J-0-9 can move into any of eight empty columns. That brings us to 17 moves including the one we want. Our chances of winning in one move is 1/17.

But wait, there’s more! (terrible cliché, I know). We can also split a sequence, e.g. moving the 4-3-2-A or the J-0-9 onto the left-most column. A little thought shows that any of the 13 cards can move onto eight empty columns, taking whatever is on top of it. Therefore we have 8*13 = 104 legal non-winning moves. Our chances of winning in one move is therefore 1/105.

To help the monkey we add the following rules:

  • Ninja Monkey cannot split a sequence onto an empty column. For instance the 5-4-3 from 8-7-6-5-4-3 cannot be moved onto an empty column (but can be moved to another exposed 6). Note that this move is only useful at the 2- or 4-suit level.
  • Ninja Monkey cannot shift the entire contents of a column onto another empty column.

With these constraints, one can see that there is now only one legal move in the above diagram, so our chances of winning in one move is 100%. It is also worth noting that specifying source and destination columns is enough to identify a unique move (assuming it is legal).

Another technicality I added was Ninja Monkey can deal another row of 10 cards, even if one or more columns are empty. This is mainly to prevent a stalemate if there are less than 10 cards in the tableau. It also simplifies the algorithm a little bit. In any case, I don’t see how this rule should seriously affect a player’s win rate.

The final algorithm is as follows (with legal moves described as above):

Fun fact: With this algorithm, I found that Ninja Monkey indeed beats the 1-suit level approximately 62% of the time. The reader is encouraged to experiment with this algorithm. Perhaps he she or ze can replicate my results, or find some further tweaks to improve the monkey’s win rate

Exercise for the interested reader: can you design an algorithm that does better than the random move algorithm? If yes, which animal in the animal kingdom should the algorithms be named after? 😊

Introduction to Artificial Stupidity

In a previous post, we looked at various features of a starting position such as the number of guaranteed turnovers and guaranteed suited turnovers. This means we can study two different starting positions and say that one is perhaps better than the other. However, ultimately we are interested in our chances of winning. If, for instance, my Dad was really awful at Spider and loses every game regardless of how good the start position is, the number guaranteed turnovers wouldn’t be particularly relevant.

Let us consider the following question: what are the chances of victory given we have N guaranteed turnovers at the start of the game? Obviously we would expect the more turnovers we start with, the greater our chances of winning.

I guess the obvious thing to do would be to play 1 million games of Spider Solitaire on my PC, record the number of guaranteed turnovers at the start, play each game to the best of my ability without 85,78,68,79 and record the result (either win or loss). After all, I’m addicted to Spider Solitaire, my blog is about the Spider Solitaire, the whole Spider Solitaire and nothing but the Spider Solitaire, and I consider myself to be the world’s greatest expert on Spider Solitaire. Unfortunately, playing 1 million games is time-consuming even by my standards. Perhaps I could program an AI to play the games for me. After all, I have a math Ph. D., I have published a number of math-related papers, I have a steady job, and I know a programming language or three. Last year, I created a Flappy Bird cover of the famous Wintergatan Marble Machine using Matlab and Audacity …. Uh oh, I’ve just realised that designing an algorithm to play Spider well is not so trivial. So perhaps we could compromise by designing an AS, where S stands for Stupidity

ENTER MY FRIEND, NINJA MONKEY

Fortunately I have an imaginary friend called Ninja Monkey (not to be confused with Monkey Magic) who is fluent in many languages such as Python-tongue (the language of pythons as well as other magical serpentine creatures), Javanese and C-plus-plus-speak. Thanks to an amazingly fast metabolism, Ninja Monkey is able to play 100 games of Spider Solitaire inside three minutes. On the down-side, his random move strategy is not very good, and he is yet to realise his dream of winning a single game of Spider Solitaire at the Four-Suit level. Nevertheless, he is able to win more than half the time if he pretends each game is played at the one-suit level. Not to mention that he is cute and friendly, and willing to give me a hug when I’m feeling down 😊

If you think about it, this gives us a way to estimate our chances of winning a game given a certain number of guaranteed turnovers. Given a large number of games, Ninja Monkey can record the number of guaranteed turnovers for a starting hand, play random moves pretending all cards are the same suit, report his result (win or loss). For instance, let us suppose that he plays 1000 games, 100 of which start with three turnovers. If NM wins 37 of those and loses the remaining 63, then we can reason that our winning chances are 37% given 3 turnovers. It’s likely not the most accurate estimate, but I guess we gotta start somewhere if you excuse the cliché!

With the help of my Ninja Monkey, I collated the following results

We immediately notice that the win ratio indeed increases as we increase our guaranteed turnovers. That is, if we ignore the division by zero error in column 9. That’s not so surprising when you think about it. After all, 9 turnovers implies a run of ten cards such as 3456789TJQ and the chances of starting with a run of ten cards are pretty slim. Also, there are very few games with 0 or 8 turnovers, so the stats are extremely reliable. With 1 or 7 turnovers we don’t have many data points so these may be doubtful. Around 4 turnovers, the results should be pretty reliable. I could have done more than 1000 iterations, but you get the gist.

ADVANTAGES OF AS OVER AI

You may be justified in asking why anyone would be interested in an algorithm that just outputs random moves and can’t even beat my dad at chess.

It turns out Artificial Stupidity has some important advantages over its well-known brother of Artificial Intelligence. As I already alluded to earlier, it’s often easier to come up with an AS than an AI. Also, Artificial Stupidities are easier to replicate than Artificial Intelligence, so it is easy for Joe Bloggs to design his own algorithm and indeed confirm my figures are correct, or approximately correct. But we shouldn’t be dismissive of AI either. Beating the top human players at Go, Chess or Backgammon is no small feat. I believe that any artificial entity can be beneficial to humankind, whether it be intelligent or stupid – provided it is used for the right purpose!

Steve N Brown (the author of a Spider Solitaire book I alluded to in an earlier post) attempted to compile his own statistics for win ratio vs guaranteed turnovers. He got the following results

We immediately notice there are only 306 games instead of 1000, so it is not surprising that division by zero occurs for 8 or 9 guaranteed turnovers. Also, there is a weird drop to 0.37 win-ratio for 3 guaranteed turnovers. This either suggests 62 data points is insufficient or that Guaranteed Turnovers is a very poor indicator of the overall chance of winning at the Four-Suit level. After all Spider Solitaire is not a Scratch-n-win Lotto Ticket – you can’t win a prize just because you start with 10 good numbers; you’ve got to earn your prize! It is certainly possible for an expert to recover after a poor start (or conversely a beginner to 70,85,67,75 up after a good one). And of course I can’t blame Steve for not playing 1000 games.

Steve has also compiled similar stats for other features such as Suited Guaranteed Turnovers or multiplicity, but this is outside the scope of this blog post.

SUMMARY

I believe neither the Ninja Monkey or Steve Brown has a definitive answer to the question of what is the win rate as a function of number of guaranteed turnovers (assuming expert play sans 85,78,68,79). Playing at the 1-suit level is far too large a handicap for Ninja Monkey’s results to be meaningful and Steve has too few games to make reliable conclusions. So perhaps I do need to design an Artificial Intelligence that can play well at the Four-Suit level. Or someone else can design one. If the latter, I would be perfectly happy to recognise I am not the world’s greatest Spider player (but I would still consider myself a GM 😊 )

Despite the negative result, I wouldn’t call this experiment an exercise in futility. The journey is more important than the destination, and hopefully this is food for thought for the interested reader, if you excuse the numerous clichés. For now, it’s farewell to the Ninja Monkey. Hopefully we might meet him again in better times. Oh, and I’m still looking for a way to get in touch with Steve Brown – so if you know him (or even better, if you ARE him) please leave a comment!

Oh, if your name is Martin Molin and you like my Flappy Bird cover of the Marble Machine, please leave a comment too!