Spotless Dominoes

December 22, 2023

In the Iain Banks novel Walking on Glass, two characters play the game Spotless Dominoes:

In the meantime they were playing a game called Spotless Dominoes, in which plain pieces of ivory had to be arranged in certain linear patterns.
Neither she nor Quiss had any idea when they were going to finish the game, or even how well they were doing at any stage, because although they knew that in the original version of the game there were spots on the ivory pieces, their pieces were blank. They had to lay them out in lines each time they played, hoping that the small table with the red glowing jewel at its centre on which they played would recognise that the spot-values it had—randomly, of course—assigned to the pieces before each game were such that the pattern Quiss and Ajayi produced was a logical one; one in which, if all the spots suddenly appeared on the surfaces of the dominoes, the pattern would make sense; a one would be matched with a one or a double one, a two with a two or double two, and so on. It was the most frustrating game they had played yet, and they had been playing it for one hundred and ten days.

From my rereading of the chapter, we don’t find out how long they take to complete the game, though later on we are given an upper bound:

In a few days, if Quiss had counted correctly, they would have been together in the castle for two thousand days.

I wondered how long it probably took to complete this game. As there is no skill involved, we can determine the probability of any one round winning, and then calculate how many rounds we should expect to play before being more likely to have won than not.

Setting out the game

In regular dominoes players take turns to play at each end of the line, matching spot counts. In Spotless Dominoes, however, the spots are hidden until the game is complete, at which point they reveal themselves and the result is determined. Although it is typical in dominoes to place double dominoes perpendicular to the line, this is purely visual—we can treat this as if the domino was placed inline like all the others.

We define a layout as a line of all of the dominoes, each with a set orientation. Multiple layouts may appear the same visually, as changing the orientation of a double domino does not affect its appearance. Nonetheless, we count them separately as each has an equal likelihood of appearing. We say a layout is valid if the spot values match on all pairs of adjacent dominoes.

We assume Quiss and Ajayi are playing completely at random, so each game finishes with a layout chosen uniformly at random. They win if the layout is valid. To calculate the probability that a games finishes successfully we can count the number of valid layouts and divide it by the total number of layouts.

Total number of layouts

This is the easier number to calculate. There are 28 dominoes that could go in any order, and each domino has two possible orientations. We therefore compute $28! \cdot 2^{28}$ for a total layout count of 81842841814930553085241614925824000000.

Total number of valid layouts

To count the number of valid layouts, I first wrote a recursive Python program to enumerate them. This worked for the simplified case of three distinct spot patterns, but was much too slow on anything larger.

The first observation that improved the search was that many layouts are equivalent up to relabelling. By consistently relabelling the spot values, any layout with $n$ possible spot values belongs to a group of $n!$ similar layouts. If we can avoid enumerating these other layouts, the final result can just be multiplied by $n!$ to compensate.

To enforce this restriction during the search, we ensure that the first domino is either [0-0] or [0-1], as every other domino can be relabelled to one of these. For all further dominoes, we only allow those that either only use spot values already in the layout, or the lowest spot value not currently in the layout. Allowing two possible new spot values to extend a layout would result in two layouts that can be relabelled as each other. We must also count all of the layouts which begin with [0-0] twice, as this first domino could have either orientation. With this approach, we still get the same answer for three distinct spot patterns and can now handle five distinct spot patterns in around a second. However, the full seven spot valued case is still infeasible.

Next I tried a more efficient search approach than simple recursion, and a more performant language. In The Art of Computer Programming Volume 4A I found Algorithm X for generating lexicographic permutations with restricted prefixes. This algorithm generates all the permutations of a set and allows for partial permutations for which no valid extension exists to be rejected early. I chose to implement this algorithm in C.

A straight transcription of the algorithm would be insufficient, as we are not counting pure permutations. We need to take into account the orientation of each domino. I considered doubling the size of the input set to account for both orientations of all of the dominoes and checking for duplicates as part of the prefix tests, but felt this would be too slow. Instead, I exploited the depth-first search nature of the algorithm to patch the input set during the search. If a domino can only be added to the layout if its orientation is reversed, we simply flip the domino in the input. We need not worry about this interfering with other branches of the search tree: now the domino has been laid it won’t be inspected until we have backtracked past it, at which point the new branch can flip it again if needed.

The other subtlety relates to the orientation of the doubles. Similar to the previous implementation where we had to count the [0-0] case twice, we must take into account both possible orientations of all of the double dominoes in each layout. To do this, we multiply the final result by $2^{n}$ .

This approach matched the previous answers for three and five distinct spot values, and could search the seven spot valued case in around an hour. I was pretty satisfied with this, and in fact went off and wrote the rest of this article based on those results. However, I’ve since optimised the implementation further.

The first, simple, optimisation was to memoise part of each prefix test. In order to ensure the next domino did not introduce too high of a spot value, we have to calculate the maximum spot value seen so far. The old approach iterated the entire layout for every new domino to do this. I introduced a cache of the maximum spot value for each prefix length. The values can be quickly calculated based on the maximum value for the previous length and the new domino, and discarded once the search backtracks past that point. This reduced the search time to around ten minutes.

Next, I once again took inspiration from The Art of Computer Programming Volume 4A, but this time in the solution to exercise 107 in section 7.2.1.3. The exercise concerns a similar problem: counting the number of valid cycles of dominoes. The key insight is that we can consider far fewer layouts by excluding the doubles, and then use the fact that inserting doubles wherever possible will not break a valid layout. The solution to this problem can also be used to calculate the number of valid layouts by accounting for all of the places we can break the cycle, which was useful for verifying my answer.

If we view each domino as an edge in a graph with nodes defined by spot values, double dominoes are loops. Each valid layout is an Eulerian path in this graph. Considering each node on such a Eulerian path for the seven spot valued case, we see that the path must visit the starting node four times, and each other node three times. Therefore, there are $4 \cdot 3^{6}$ valid ways of inserting the double dominoes into a valid layout.

We can ignore the double dominoes in the search and multiply our result by $4 \cdot 3^{6}$ to account for their exclusion. Applying this to our implementation greatly improves its performance, so that it now takes around 70ms to search the seven spot valued case. Sadly, any larger cases still seem beyond it, but we have the value we need: 1018781431234560 valid layouts. Our optimisations have meant that the search itself only explores 541568 layouts.

Probability of winning

Dividing the number of valid layouts by the total number of layouts gives us a probability of winning each game of approximately $1.24 \cdot 10^{- 23}$ . These don’t seem especially good odds. Framed another way, if you bet £1 that you’d win a game you would want the prize to be at least £80,334,053,316,768,194,550,319.07 to make money in the long run.

How long should we expect to play?

But Quiss and Ajayi don’t care about losing; they only need to win once. How many games does it take to have a 50% chance of having won at least once? To figure this out, we can let $p$ be the probability of winning a game as calculated above, then solve for the number of games $n$ :

\begin{matrix} 1 - {(1 - p)}^{n} & \geq & 0.5 \\ {(1 - p)}^{n} & \leq & 0.5 \\ n & = & ⌈ \log_{1 - p} 0.5 ⌉ \\ n & = & 55683322559470195244459 \end{matrix}

Assuming Quiss and Ajayi can play one round a minute for twelve hours a day (a brutal pace), it would take over 211 quadrillion years to play this many games. The upper bound established in the novel seems incredibly optimistic. Perhaps the flow of time is distorted, whether objectively or subjectively.