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? 😊