Improved Monkey Algorithm (Alternative Version)

“I’m starting to see the light,” sighed Monkey. “Perhaps the random move algorithm ain’t so good after all.”

“Told you so!” shouts the Elephant.

“Perhaps you should go back to your stupid typewriter,” yells the Dumb Bunny.

“Do the Harry Potter novels instead of Shakespeare!” shouts the Cat.

“Why, if it isn’t the Ninja Monkey descending from on high to mingle with the commoners!”  sneers the Lion.

“We need to talk,” I say to Monkey.

Monkey nods.

“I think we might improve our odds of winning if, you know, we use some strategy.”

Monkey is confused and gives me the what-the-70,85,67,75-does-that-word-mean look.

“I was thinking … let’s say that once you have two cards in sequence then you never break it up.”

“Does that mean,” replies Monkey, “If I have Six of Spades and Seven of Spades then the 7-6 is never broken?”

“Correct, unless you move the Six of Spades onto the other Seven of Spades.”

I click my fingers.

It takes Monkey a mere ninety seconds to add another 200 to his not-so-impressive tally of 50 quintillion losses.

I notice the other animals are taking side bets. The Jackal thinks Monkey will persist for at least 40 minutes before giving up and is willing to bet $30. The Lion thinks otherwise and raises to $80. Meanwhile the Smart 65,83,83 is running an informal competition for who can come up with the cleverest insult(s).

“That’s interesting,” says Monkey. “I’ve noticed the number of in-suit builds never decreases. After any move it either stays the same or goes up by 1.”

“That’s very good,” I reply. “The more in-suit builds we have the closer we are to winning.”

“If only it were that simple,” sighs the Monkey.

“Now this next step might be tricky for a player like you – I want you to play S-L-O-W-L-Y for a change and then I can see where you are going wrong.”

Monkey redeals another hand. He pauses for five seconds before making each move. I can tell he is bored 83,72,73,84,76,69,83,83 and on the verge of crying. Fortunately he doesn’t have to wait very long before I find some serious deficiencies in his strategy.

“It’s good that you are never breaking in-suit builds, but the new problem is that you are missing opportunities to build in-suit. Go back to the very beginning, you see columns 1 and 9 contain the Ace and Two of hearts. Therefore you should start by moving the AH onto the 2H.

“So that means,” says Monkey “I should always build in-suit if possible. If I can’t build in-suit then build off-suit, but under no circumstances should I break an in-suit build.”

“That is correct.”

Monkey redeals another hand. After the first hand he shrieks with joy. He has managed to remove his first complete suit. But that doesn’t put an end to the bullying from all the other animals. It seems he has to remove all eight suits to put an end to it.

*Sigh*

“I have a thought,” says the Wise Snail.

Of course I don’t expect any great insight from the world’s slowest player but given that he is not participating in the bullying I’m willing to listen for once.

“Maybe we can combine the two strategies,” says the Wise Snail. “Let us call the first strategy Level 1 – where we make random moves. At Level 2 we recognise that we should not break in-suit builds. Once the player reaches Level 3 he knows he should focus on increasing the number of in-suit builds. Once we have 96 in-suit builds we win the game.”

No fantastic insight from the Wise Snail yet, but I will give him credit for knowing how to do basic math.

“But let’s say we pick a random number between 0 and 1. If it is 0.9 or lower then we pretend we’re at Level 3. If it’s higher than 0.9 then we pretend to be Level 2.”

“But that sounds crazy,” I protest. “If both strategies have a win rate of zero then taking a weighted average should also yield a win rate of zero.”

“Not exactly,” replies the Wise Snail. “Ever heard of “Simulated Annealing?”

The snail starts moving about in the sand. It takes him a good 10 minutes to draw the figure below. I try to google Simulated Annealing on my iPhone but the reception ain’t great in the Animal Kingdom. Meanwhile, the Monkey is happily (or not so happily) adding to his tally of losses with the Level 2 and Level 3 strategies.

Oh Great, it looks like they’re now bullying the Wise Snail as well.

rolling_ball

 

“Actually, I can’t remember whether it’s simulated annealing, stochastic hill climbing, or stochastic gradient descent, or something else” continues the Wise Snail. “In any case the details aren’t important. The x-axis represents the set of possible game states. The y-axis represents the number of in-suit builds you need to complete the game. Thus we win if the ball reaches the bottom the hill,”

“But occasionally we may need to avoid building in-suit,” I reply, “to achieve a greater gain, such as an empty column. Under the right circumstances we may even decrease the number of in-suit builds, but that’s a lesson for later.”

“Correct,” says the Wise Snail. “Assume the ball can only see a local neighbourhood of the terrain. If the ball moves randomly then it will take a long time, but if the ball moves to the local minimum then it will get stuck.”

I nod in agreement.

“But we can combine the two algorithms. Let us say that we spend 90% of the time moving towards a local minimum and 10% of the time moving rando-”

“I see where you’re coming from,” I reply.

“Unfortunately I don’t know how to explain this simulated annealing/stochastic hill climbing/stochastic gradient descent/something else thingy to the Monkey.”

I turn to the monkey and signal him to stop playing.

“Import Numb Pie As N. P.”

Monkey eagerly nods, awaiting further instruction.

I ignore the rest of the gang as the Bad Idea Bears take bets on how many syntax errors I accumulate before the Monkey starts playing again.

<<Three hundred and twenty five syntax errors later>>

I click my fingers. The Smart 65,83,83 curses his off-by-one error, having bet on 324 instead of 325. There are no prizes for coming closest – only an exact guess takes the jackpot. The B.I.B. are content with their tidy profit. At least I have no more syntax errors. Unfortunately the Monkey loses another 100 games in a row.

“Okay,” sighs the Wise Snail. “Maybe it’s not working after … ”

“MONKEY DID IT, MONKEY DID IT, MONKEY REMOVE ALL CARDS, FOUR SUIT WITHOUT UNDO, GAME 115 MONKEY DID IT!!!!”

“Liar!” calls the Eagle. “Monkey is BLUFFING!!!!!!”

“I am 100% certain Monkey removed all eight suits in Game 115,” I say matter-of-factly.

“You were having a quiet discussion with your Wise Snail friend” sneers the Eagle.

“$500 says I can prove Game 115 is a win.”

“I raise all-in, Three thous-”

I call so fast Eagle doesn’t even have time to say “and”.

I click my fingers and Monkey deals 200 hands. Of course I have remembered to seed Monkey’s random number generator with my Tax File Number. As predicted, Monkey wins the 115th game out of 200 and loses every other game. The Eagle is not happy. My two worst students have teamed up and somehow managed to beat the game at the Four-Suit level (something the Eagle has never managed). Moreover, in one night my best student has squandered all her penny-game poker winnings accumulated in the past three months. As an extra bonus, the constant bullying from all the other animals has mysteriously stopped. I can’t say everybody lived happily ever, but at least it’s a step in the right direction 😊

THE END

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.