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!

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.

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!