9 February 2012
Universal Turing Snake
4 January 2012
Markov analysis of Beetle
Having young kids, we seem to have a lot of games around the house at the moment. The geek in me starts looking at them as maths challenges. Beetle, by Milton Bradley, is a variant on the classic dice game. I was curious to use Markov chains to figure out the average game length, and which positions were closer to victory.
Basic rules:
- Take turns spinning the spinner to build a piece of the beetle
- 1/6 chance of getting the body
- 1/6 chance of getting the head
- 1/6 chance of getting one of two eyes
- 1/6 chance of getting one of two antenna
- 2/6 chance of getting one of six legs
- Must get the body before getting anything else
- Must get the head before the antenna or eyes
This allows for 71 states as depicted in the diagram below:
The 71x71 matrix is basically formed from the above diagram. There are three regions:
- no body
- body, but no head
- body and head
Within each region there are various combinations of legs or other pieces, as permitted. E.g. state 'A' has no pieces; state 'B' has a body, no head, and five legs; state C has a head and body, one antenna, two eyes and one leg; state 'D' is a completed beetle. Each successful spin moves either to the right or down (or 'out') to an adjacent state.
Result: 31.498 spins on average.
The following table shows the average number of moves remaining to victory from each position, sorted by moves remaining (hopefully the notation is self explanatory):
| Combination | Average turns to victory |
|---|---|
| b h e2 a2 l6 | 0.00000 |
| b h e2 a2 l5 | 3.00000 |
| b h e1 a2 l6 | 6.00000 |
| b h e2 a1 l6 | 6.00000 |
| b h e2 a2 l4 | 6.00000 |
| b h e1 a2 l5 | 7.00000 |
| b h e2 a1 l5 | 7.00000 |
| b h e1 a2 l4 | 8.66667 |
| b h e2 a1 l4 | 8.66667 |
| b h e1 a1 l6 | 9.00000 |
| b h e2 a2 l3 | 9.00000 |
| b h e1 a1 l5 | 9.50000 |
| b h e1 a1 l4 | 10.58333 |
| b h e1 a2 l3 | 10.77778 |
| b h e2 a1 l3 | 10.77778 |
| b h a2 l6 | 12.00000 |
| b h e2 l6 | 12.00000 |
| b h e2 a2 l2 | 12.00000 |
| b h e1 a1 l3 | 12.18056 |
| b h a2 l5 | 12.33333 |
| b h e2 l5 | 12.33333 |
| b h a2 l4 | 13.11111 |
| b h e2 l4 | 13.11111 |
| b h e1 a2 l2 | 13.18519 |
| b h e2 a1 l2 | 13.18519 |
| b h a1 l6 | 13.50000 |
| b h e1 l6 | 13.50000 |
| b h a1 l5 | 13.70833 |
| b h e1 l5 | 13.70833 |
| b h e1 a1 l2 | 14.18287 |
| b h a1 l4 | 14.27778 |
| b h e1 l4 | 14.27778 |
| b h a2 l3 | 14.33333 |
| b h e2 l3 | 14.33333 |
| b h e2 a2 l1 | 15.00000 |
| b h a1 l3 | 15.26736 |
| b h e1 l3 | 15.26736 |
| b h e1 a2 l1 | 15.79012 |
| b h e2 a1 l1 | 15.79012 |
| b h a2 l2 | 15.95062 |
| b h e2 l2 | 15.95062 |
| b h e1 a1 l1 | 16.48650 |
| b h l6 | 16.50000 |
| b h l5 | 16.60417 |
| b h a1 l2 | 16.66705 |
| b h e1 l2 | 16.66705 |
| b h l4 | 16.94097 |
| b h l3 | 17.60417 |
| b h a2 l1 | 17.89712 |
| b h e2 l1 | 17.89712 |
| b h e2 a2 | 18.00000 |
| b h a1 l1 | 18.42943 |
| b h e1 l1 | 18.42943 |
| b h e1 a2 | 18.52675 |
| b h e2 a1 | 18.52675 |
| b h l2 | 18.63561 |
| b h e1 a1 | 19.00662 |
| b h l1 | 20.03252 |
| b h a2 | 20.10700 |
| b h e2 | 20.10700 |
| b h a1 | 20.49312 |
| b h e1 | 20.49312 |
| b h | 21.76282 |
| b l6 | 22.50000 |
| b l5 | 22.53472 |
| b l4 | 22.67014 |
| b l3 | 22.98148 |
| b l2 | 23.53286 |
| b l1 | 24.36608 |
| b | 25.49833 |
| empty | 31.49833 |
18 September 2011
Rubik's Snake Combinations
I've had a long standing attraction to the Rubik's Snake puzzle for many years, including being involved with glSnake. (Scroll to the red bit for final answer)
One question of interest was how many unique configurations of the Snake are possible. The Snake consists of 24 interconnecting prisms, with each interconnect able to be in one of four possible positions. This leads to a trivial upper bound of 423 = 70,368,744,177,664 distinct combinations. But many of these are not actually possible, as they may be configurations where the snake impossibly passes through itself. And most configurations will appear twice as mirror images.
A trivial lower bound can be reached by starting with a straight snake and then only permuting every other junction. Every rotation will be along a parallel axis, giving rise to pairs of interconnects that are always on discrete planes: meaning that the snake can never bend back on itself. Halving guarantees no reflections. (Symmetrical would only be counted once, but this is a lower-bound). This gives 411/2 = 2,097,152 as a trivial lower bound.
As an enhanced lower bound, we could observe that the snake prisms exits on a 3-dimensional grid of cubes. At any time the next piece could lie in the adjacent voxel in either the x, y or z direction (but can never follow the same axis twice). If we restrict ourselves to only ever advancing in the positive direction on each axis, then we always have a choice of one of (+y or +z) or (+x or +z) or (+x or +y), depending on whether our previous move was +x, +y, or +z respectively. In any case we have 2 choices. This gives us 223, which is not any better than before. However we can extend the idea: if we partition the space into planes normal to the x axis, then any time we extend in the +x direction, without loss of generality we can start moving in in any of the four +/-y or +/-z, i.e. four choices. From there we can move +x again, or either +/- along the axis we didn't previously chose. I.e. 3 choices. In this way we never fold back to previous planes. From that point on we only have 2 choices: to continue moving in a straight diagonal, or move onto the next x plane. We can represent this as the following Markovian chain:
| 0 | 0 | 2 | 0 | Refined lower-bound: | ||||||
| 0 | • | 1 | 0 | 4 | • | 1 | 1 | 1 | = | 85,149,351,936 |
| 1 | 1 | 1 | 0 | (approx 418.15) | ||||||
That's about as far as I could get without using numerical methods. (I also had a complicated, slightly improved, upper bound). So I wrote a program to walk every possible combination, which back tracks whenever it found a collision. Written as a single-threaded service to run in the background this took about five months to execute. This gave the following answer:
13,535,886,319,159 = approx 421.81 combinations, including possible mirror image duplicates.
Update: 5th Aug 2022: Corrected to 13,446,591,920,995 = approx 421.81. See below.
To handle mirror images, each time it encounters a complete snake it then converts it to a normalized form as follows. The snake is represented as a string of 23 numbers (from 0 to 3). The string is then reversed. The two strings are compared lexicographically and the smaller is the normal form. If the string matches the normal form, then it is counted, otherwise it is skipped. This way potential reflections that appear twice can be counted once, but symmetrical snakes also get counted once. Note that I'm interpreting mirror images here as applying the same turns from either end, not if the volume produced is a mirror image. For example, I'm counting a left-handed corkscrew snake and a right-handed corkscrew snake as discrete. But if you just twist one piece 180 degrees at the start or the end of the snake, then I count that as the same snake.
When ignoring reflections like this, the exhaustive search gives this result. Total number of possible snake configurations that don't overlap, and ignoring mirror repeats:
Final Answer = 6,770,518,220,623 = approx 421.31
Update: 5th Aug 2022: Corrected to 6,721,828,475,867 = approx 421.31. See below.
Behold. OK, it only took another two years to getting around to writing this up any telling the world. (mainly because I started writing up a detailed paper on the method, which quickly got boring). Hopefully anyone else who has tried this got the same answer.
So table of numbers: (Update: see below for correction)
| Method | Number | Approx as exponent | |
|---|---|---|---|
| Trivial lower bound | 2,097,152 | 410.5 | |
| Refined lower bound | 85,149,351,936 | 418.15 | |
| Final answer | 6,770,518,220,623 | 421.31 | Corrected: 6,721,828,475,867 |
| Exhaustive with duplicates | 13,535,886,319,159 | 421.81 | Corrected: 13,446,591,920,995 |
| Refined upper bound | 30,002,572,532,736 | 422.60 | |
| Trivial upper bound | 70,368,744,177,664 | 423.00 |
Along the way I also discovered that there are about 64,546,391 Corrected: 63,970,851 (approx 412.97 unique cyclic paths where the head and tail of the snake connect. Also, only a relatively small number of snakes are symmetrical.
I should probably go and get some sun, or social interaction, or something now.
Update: 5th Aug 2022
It turned out that my original calculation was wrong. I wrote another Snake Calculator program while playing around with another problem - and results didn't quite match. The good thing about now having two independent programs is that each could be used to find and fix bugs in the other. The original program didn't quite handle an edge-case correctly. Further inspired by hearing about "The Soul of the Snake" I've re-run the program on a full length snake.
With both programs now agreeing for various length snakes, I now feel pretty confident about the following answer being correct for length 24:
Final Corrected Answer = 6,721,828,475,867 = approx 421.31
| Method | Number | Approx as exponent |
|---|---|---|
| Trivial lower bound | 2,097,152 | 410.5 |
| Refined lower bound | 85,149,351,936 | 418.15 |
| Final answer | 6,721,828,475,867 | 421.31 |
| Exhaustive with duplicates | 13,446,591,920,995 | 421.81 |
| Refined upper bound | 30,002,572,532,736 | 422.60 |
| Trivial upper bound | 70,368,744,177,664 | 423.00 |
(Yes, the difference is less than 1%, so the exponents are still pretty much the same)
The Internet is now a little bit more correct and, to offset the drop in entropy, a server somewhere in an AWS data centre has been slightly warmed.