I was wondering earlier today, how many possible levels are there to the game Fat Stack. It’s a peg game / board game with a 6×6 grid, and each level varies by the initial configuration of the board and the number of starting pieces. So it seems easy enough for us to be able to figure out a total number.. maybe? Lets see.
This is an interesting question for me, since I worked hard to figure out how to generate enough ‘solved’ levels for the game to have a healthy pool for players to draw from. I ended up making an autosolver in C++, and used that to generate, solve, and save off over 9000 unique levels. It was a time intensive process creating the levels. I initially had handmade the levels, then I made a python script, and then finally went all in with the C++ version (proving to be like atleast 100x faster than the python version, crazy enough). Anyway, I digress…
So that said, I generated & solved 9000 levels and felt like that was sufficient to launch the game with. But how many unique levels really exist? like in total?
Well fortunately, I have been taking some math courses during quarantine, and among those is discrete math. One of the things we learn in the course is some basic combinatorics and counting. This is exactly the toolset we need to answer this question (or atleast the first part of it…)
The Fundamental Principle of Counting (or ‘basic counting principle’), says that the total number of options for an event is equal to the number of decisions multiplied by the number of choices. Or said another way (and more elegantly):
When there are m ways to do one thing,
and n ways to do another,
then there are m×n ways of doing both.
It’s all 1’s and 0’s
One trick we’ll use to calculate this for us is if we imagine each unique 6×6 grid configuration of game pieces as a binary string. The binary string would be equal in length to the total number of play-squares (so, 36 in our case). So imagine “010101010101010101010101010101010101” actually would represent a map, it represents the initial starting configuration of the level, so just as an example – the first row of the game grid would be just the first 6 characters of the binary string, and translated to our game it would symbolize a first row in this configuration “empty-occupied-empty-occupied-empty-occupied”
Ok, so that bit is key. Once we realize we can symbolize any given level as a string of 1’s and 0’s, then now we can re-frame our initial question
how many distinct ways are there to write a length 36 string made from only 1’s and 0’s? If we solve that question, then we’ve solved our original question as well
So then, lets think about how to leverage the fundamental counting principle for this question.
We have 36 choices to make, and each choice presents only 2 options. Each given square is independent of the others, so they all have to be multiplied with each other (as opposed to being added together if they were not independent). We end up with 2^36
2^36 = 68,719,476,736
But wait, that’s our TOTAL POSSIBLE – whats our TOTAL… PLAYABLE?
How many of these are actually solvable? Some of these will be unplayable/unsolvable and thus aren’t actually valid levels.. Like with no possible starting moves, or no possible solutions…
This is 100% true and a big issue with our 68 Billion figure (here-forth known as our ‘TOTAL COUNT’). This giant number above is the total count of all possible map configurations. Which means it includes a map that is all empty spaces (i.e., all O’s). That is certainly an unplayable map, and there are undoubtedly other types of unplayable maps included as well. How can we filter out these maps?
That’s a tough problem. We can subtract out the bad maps and try to get there.
For example, we can remove “000000000000000000000000000000000000”, and also the completely filled set of all 1’s, “111111111111111111111111111111111111”
Additionally, we know that in this ‘total count’ above are also all combinations with only a single game piece, and those aren’t playable either – so there would be 36 of those – since we have 36 possible spaces. Ex: “100000000000000000000000000000000000”, “010000000000000000000000000000000000”, “001000000000000000000000000000000000”, …
So we can subtract (1 + 1 + 36) = 38, from our giant number above since we know that these levels are actually impossible. But thats not really impactful, whats 38 out of 68 Billion.. It’s basically zero!
So you can see, if we are to clean-up our TOTAL COUNT by subtracting out the ‘bad maps’ then we are going to have to be extremely granular.
But what about all maps with 2? Can we figure out how many levels in our ‘total count’ have 2 pieces that are not within playing range of each other? This is a good question. One I need to think about. NOTE: Perhaps we can do an analysis here where we count all the combinations where we have 2 pieces ‘within playing range’. (I.e., in cases of only 2 game pieces, the game pieces must be adjacent for a move to possible on that level).
But wait, theres more! What about ‘distinct’ness?
Further more there’s also a lot of duplication because of rotations – if we were to create a level, and rotate it – then this current count would duplicate that by counting it as a separate and unique level (since they have different binary string representations). So actually if we are honest, and we are counting only DISTINCT map layouts, then it’s actually like over-counting by a factor of 4!
Total Possible Levels = 17.18 Billion ?
So that’s a whole ‘nother layer to this question.
To make it even more intense. There is more over-counting happening due to potential spacing changes, that don’t impact the playability of the map – but allow for various binary string representations of what are essentially the same exact game (just perhaps centered differently on the game board).
For example: Imagine a small shape, perhaps a plus sign, or capital T — something that is only a small number of game pieces, but it is playable. Now imagine we shift the entire map one unit to the left, to the right, to the top, or to the bottom. If that small playable map we imagined has ‘slack’ around it and the edges of the board, then can be shifted within the game-area without changing any real features of the level. This kind of thought experiment reveals that for every DISTINCT map that exists, there also exists every possible variation where it is shifted around the game-area and taking advantage of all slack. Since all of these variations would have different binary string representations, our TOTAL COUNT is counting all of them.
So by now we see this is a tricky problem. Although we can quickly get an estimate of 68 Billion possible maps, the simplicity of our methods ends up costing us in accuracy – we know this figure is inflated by numerous impossible maps, by a factor of 4 due to rotations, and also off by some other factor depending on the map’s “slack” on the board. Binary strings are just not ideal representations of this kind of info it seems.
Total Possible Levels – (unsolvable/dead-end maps) – (all possible ‘spacing’ variations of maps) = Total Playable Levels
So then, are we defeated? or is there hope of getting an accurate count – of this mythical Total Playable Levels?
This is tricky problem. One that I do not know how to answer just yet. I think the answer lies in the area of graph theory. Not sure exactly, but it seems perhaps there are a finite number of subgraphs, that we can think of as “basic forms”, that exist in levels – and that if these basic forms do not exist in a level, then it will have a ‘dead-end’ at some point and not have a possible solution. I haven’t yet done this work.. but think it may be the next step in this line of investigation.
To be continued…