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!