Discussion and analysis for the Knucklebones dice board minigame.
Table of Contents
This is a guide discussing playing the Knucklebones minigame optimally. I hope you’ll find it useful to quickly get the achievements, earn gold without spending in-game time, or just for fun.
I’m making this guide because I was curious about the Knucklebones minigame. After writing a solver, I found that it has surprising amount of depth, and the best strategy can’t be explained in a few simple rules.
Facts About Knucklebones
If we wanted to count the total number of game states that can occur in Knucklebones, one naive way would be to multiply the number of die slots on the board with the number of possible die values (six faces, plus one for an empty slot). That would give us 7^18 = 1,628,413,597,910,449. However, that’s not quite right, since you can only place dice in the closest empty slot towards the other player.
To address that, we can count the total number of states that one column (3 dice) can have. 6^0+6^1+6^2+6^3 = 259, and since there’s 6 columns, 259^6 = 301,855,146,292,441. Better, but we can do more.
We note that the order of dice within a column doesn’t matter – whatever the order, they still represent the same game, with the exact same outcomes. The previous formula is thus improved to (6 multichoose 0)+(6 multichoose 1)+(6 multichoose 2)+(6 multichoose 3) = 84, a solid improvement. That brings the total to 84^6 = 351,298,031,616. Here, “multichoose” is the multiset coefficient, and the syntax used by Wolfram Alpha.
Next, we note that the same die cannot occur in the same column on both sides of the table. When one is placed, all dice with the same face up are removed from the other side. Thus, one column (for both sides of the board) has a total number of 3,067 possible combinations, which is an improvement over the previous 259^2 = 67,081. Total: 3,067^3 = 28,849,701,763.
We similarly note that the columns themselves can be repositioned freely. 3067 multichoose 3 == 4,812,987,894, which gives us a reasonable upper bound for the number of functionally-distinct reachable game states.
More importantly, because that number is within the range of the limits of today’s personal computers’ operating capacity, and we can encode and decode arbitrary game states into this interval using a combinatorial number system, we can use this to fully explore the game state space. The above number includes unreachable states, such as states where both sides of the game board are full. By writing a program which traverses the game state space, we arrive at a precise number: 3,861,821,161 unique reachable states.
The game has no theoretical limit to the number of turns – it’s possible that both players keep rolling the same die over and over, canceling each other’s die they just placed.
“Perfect play” essentially means always choosing the move that is most likely to lead to victory, no matter what the opponent chooses. For Knucklebones, this involves taking into account probabilities of successive dice rolls and the state of the board, “looking ahead” an infinite number of turns (though the number of game states is finite, you can arrive at a previous game state).
Though, note that in our case, perfect play will mean something slightly different, because unlike games like chess or checkers, Knucklebones involves a random element, so the possibility of victory is a probability distribution instead of being binary.
The strategies described below, as well as the solver, assume that the opponent also uses perfect play – though, of course, the AI opponents in the game will actually play worse than perfectly. By playing perfectly, you can thus win most of the time.
This is a simple and straight-forward strategy which is exactly what it sounds like. If a move results in the best possible immediate outcome (most points gained for you + most points lost for your opponent), take it, disregarding any possible consequences for future turns. If the number of points is the same for more than one move, then the moves are considered equivalent and all are considered as the “best moves”.
The greedy strategy is worse than perfect play by about 3.5% on average.
Though, don’t be fooled into thinking that this small number means that using the greedy strategy will make you lose only 3.5% more often than if playing perfectly: the difference is 3.5% per turn, and since typical Knucklebones games last over 20 turns, this will quickly compound into a much bigger number (about 30% after ten of your turns).
A “strategy” which describes actual perfect play would be immensely large and complicated; there are so many subtle propagating effects that it would be impossible to describe every possible situation and choice in a format that could still be described as a “strategy”. The only real strategy for perfect play is to use a solver (see below).
What about the next best thing? I was curious to see if it’s possible to create a strategy that can be described in simple words, which – when followed – would allow playing as close to perfectly as possible. To do this, I wrote a program which generated random strategies and evolved them to find one as close to perfect as possible.
Here is the current best strategy found by my program:
- Move as you would for the “Greedy Strategy” (described above), but only if the column you would move to has less than two dice on your side of the board. If it it has two or more dice, go to step 2.
- Move as you would for the “Greedy Strategy” (described above), but only if doing so will bring (or keep) the opponent’s score for that column only below 7. Otherwise, go to step 3.
- If you can place your die in such a way that it would delete more than one matching opponent’s die, or if it deletes one opponent’s die while doubling (or tripling) one of your own, then do so. Otherwise, go to step 4.
- Move as you would for the “Greedy Strategy” (described above).
If this strategy seems a little random to you, then that’s because it is, and such is the nature of trying to describe very complicated systems with non-obvious propagating and compounding effects using just a few simple rules.
This strategy is worse than perfect play by about 2.1% on average. Same caveat about compounding effects of sub-optimal play as the greedy strategy applies.
If the goal is to play perfectly, your only choice seems to be to fully explore the game state space and map out the victory probabilities and optimal moves at each step.
- A tool which does this can be found here.
As mentioned above, this solver assumes perfect play from both sides.
Be the first to comment