# 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)