Graphical Illustration of Random Walks

Once upon a time, Odysseus was trapped in a maze and wanted to find his way back to Ithaca. Hang on, is that Odysseus and the Sirens or Theseus and the Minotaur? Whatevs, I was never any good with Greek Mythology. Without loss of generality, assume it really is Odysseus and the Sirens.

Let us denote a maze as a finite set of nodes, where O represents Odysseus’ starting position, I represents Ithaca and S represents a Siren. Odysseus wins if he reaches Ithaca and loses if he reaches a Siren. We will also assume that a legal move consists of Odysseus moving from one node to another adjacent node in a downward direction. Any “terminal” node is marked either I or S. This implies that “draws” are impossible i.e. the game cannot continue indefinitely without a result. Example mazes are shown below:

Clearly, if Odysseus knows the entire maze layout then he is guaranteed to win (if at least one winning path exists) or lose (no such path exists). But if the maze layout is not known then Odyssues must guess which path to take. For instance, Odysseus might approach a dozen Sirens if they are singing Benjamin Britten’s Missa Brevis or get the 70-95-67-75 outta here if they are improvising karaoke with a Richard Clayderman song. Note that I didn’t claim that this was a good strategy.

The simplest strategy is a random-walk strategy. At any node we can compute the number of legal moves available to Odysseus and stipulate that each move occurs with equal probability. One can easily see that Odyssues should probably win in the left maze and probably lose in the right maze. Calculating the exact probabilities is left as the proverbial exercise for the reader.

In Spider Solitaire we can (in theory at least) enumerate the set of all legal game states reachable from a given start position and it will look like the Odysseus-Siren maze except it will obviously have a ridiculous number of nodes and links. We can say that a game is “easy” if it resembles the left maze and “hard” if it resembles the right. If we can compute (or estimate) exact probabilities of winning then we can have a quantitative measure of difficulty (probability of winning) rather than a categorical measure (easy/medium/hard). Obviously this will not be appropriate for human players since humans understand basic Spider Solitaire strategy (such as obtaining empty columns). But it might be appropriate for monkeys playing at the 1-suit level. At least we have a ball-park estimate of how easy or difficult a given hand should be.

The diagram below (left) is an example endgame where an expert player has removed six suits and only needs two more moves to win. For purposes of this example we will assume that (i) empty columns cannot be used and (ii) if the player fails to win the game in two moves then it’s an automatic loss. One can verify the Odysseus-Siren maze looks like the figure below (right). The probability of winning in two moves with random play is 50% (since only the first move is relevant and there are 2 good moves out of 4)

As an aside, one should note in practical play, game states in Spider Solitaire are not explicitly labelled “LOSE” since a player can resign even if there are one or more legal moves. But one can easily tweak things e.g. by imposing a move limit and saying that a game is automatically lost if we cannot win in N moves or less. Obviously in the above example it is impossible to reach an unwinnable state even if we tried. Hence a random move algorithm is practically certain to win if the move limit was (say) 50 instead of 2.

Let us suppose that Joe Bloggs plays a game of Spider Solitaire without undo and loses. He then proceeds to replay the same game but with unlimited 85,78,68,79. Joe Bloggs is able to win (and hence record the identity of every unseen card). JB can then estimate the difficulty of the hand using the random walk method described above. If the probability of winning is 80% then there is a fair chance JB misplayed when playing without undo. If the probability is only 20% then chances are JB was destined to lose even with expert play. This could give Joe Bloggs a better estimate of his playing strength than simple win-rate.

If this post has inspired you to do a Ph. D. based on Spider Solitaire please leave a comment below!