Monkey Algorithm – In Depth

Let us take a closer look at Ninja Monkey’s algorithm. We know it can get about 6% win rate on random four-suit deals without undoing moves – and that’s nothing to sneeze at when many players have difficulty with the 4-suit version. Not to mention that I am unaware of any research into designing a Spider Solitaire AI that plays without rot13(haqb). The heart of the monkey algorithm is as follows:

This represents “what to do with the current game state”. The basic idea is if any column is headed by a face-down card then we can count it as a turnover – but we don’t know the rank or suit of that card. If we call that card X then nothing can move onto X and X cannot move anywhere (not even an empty column). Let’s look at an example:

Let’s say we executed the moveblock “id,ah,fh” but without turning over any cards. The game state would look like this:

Disclaimer: I only got ‘C’ in Year 10 Art

Without loss of generality, let us assume we score 10 points for turning over a card and 1 point for building in-suit. Our score would be 31 regardless of the identity of newly-turned cards.

Clearly, “id,ah,fh” is not the best possible moveblock for several reasons. For starters, we can play only “id” and examine the new card in column 9. Then we still retain the option of playing “ah,fh” if the new card is useless – or we may find something better than “ah,fh”. This is why the statement “execute best moveblock found” comes with the caveat “first turn over only”.

Now let us consider only the three lowest-numbered cards in columns 1,6,8 in the original position. Clearly we can guarantee two turnovers with ah,fh. But suppose we knew the card under the Two of Spades is the Three of Clubs. Then we can get two turnovers plus an in-suit build with fa,fh. Obviously, that would be cheating since we aren’t entitled to this information. This explains why the statement “guess a move block” comes with the caveat “no turnovers”.

The rest of the algorithm should be fairly self-explanatory.

The observant reader will have noticed it is not necessary to begin with an in-suit build to achieve the worst-case scenario. Going back to our hypothetical moveblock of “id,ah,fh”, we would get the exact same position with, e.g. “ah, id, fh”. If we only had two guesses “id,ah,fh” and “ah,id,fh”  they would have the same evaluation score. We all know we should begin with the in-suit build, but my algorithm would effectively decide by tossing a coin.

Assuming we make enough guesses, we should eventually stumble upon a score of 61 with six turnovers and one in-suit build. One such moveblock would be “ec,hc,ac,fc,id,db”. If that was the final best_moveblock_found then we would execute the move “ec”.

In this case, our algorithm actually found a decent opening move – with three Sixes available, it’s hard to imagine “ec” being a significant blunder even though an in-suit build was available with “id”. Of course the algorithm could equally well have come up with “db,ib,eg,hg,ag,fg” and start with “db”. This would cost a turnover if the next card was a Nine.

Of course, it should be possible to modify this algorithm to avoid the latter scenario given sufficient effort, but I would rather gain some experience with collaborating with other software developers via GitHub. As mentioned previously the current state of my project is a bare-bones AI with plenty of room for improvement and my Spider Solitaire project gives me a perfect excuse to do so.

2 thoughts on “Monkey Algorithm – In Depth

    1. Hi IM Bug,

      It is beyond the scope of this post to explain the algorithm in gory detail, but the general gist is as follows: let us assume we propose 3 different moveblocks. Our proposed moveblocks are “ab”, “ac,ef”, and “gf,ac,cj”. None of these moveblocks require knowledge of face-down cards (i.e. we aint’ cheating). We then evaluate three positions that correspond to each of our three moveblocks and choose the best moveblock, call it M. We then execute the partial moveblock of M, stopping as soon as we turn over one more card.

      Obviously, we can increase our chances of choosing the best moveblock by replacing 3 with a higher number but at the cost of more computation. We might also consider increasing the lengths of moveblocks since this might come useful in a complicated middlegame when you need 50 individual moves just to turn over one crucial card. Again this results in more computation.

      HTH

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s