KnuckleBones minigame

Discussion and analysis for the Knucklebones dice board minigame.

How to Win

For the impatient: use the solver!

https://cy.md/ta/cult-of-the-lamb/knucklebones/

Introduction

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 ( see https://en.wikipedia.org/wiki/Multiset#Counting_multisets ), 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.

The first player to go has a very small advantage (1.8%) over the second player.

Is Knucklebones rigged?

You can find posts online from people who have experienced, or perhaps even experienced yourself, some highly unlikely series of rolls, leading games to crushing victory or defeat with scores into the triple digits. Seeing this, it's easy to claim that such obviously unlikely events are clearly due to the game being rigged, or that the rolled dice depend on factors like the difficulty or the stakes.

First, let's talk about how video games typically do randomness. The straight-forward approach is, of course, simply using the raw output from a pseudo-random number generator: ask for a random number between 1 and 6, and that's your roll.

However, many games do something else: take all possible roll values, repeat them a few times (e.g.: 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6), shuffle them, then deal them out in order. When this bag of rolls becomes empty, fill it again in the same way. Why do they do this? Exactly for situations like these, and also to put an upper bound on how many rolls it takes to see every possible outcome. For example, if a game which uses raw random numbers has a fishing minigame with each possible catch having some odds of being caught, theoretically a really unlucky player could fish literally forever without ever seeing every possible catch - but if you put all catches in a bag and just shuffle them, you guarantee that even though the order is random, the player will go through them all eventually. This approach is sometimes compared to using a pre-shuffled deck of cards. You may also have heard that casinos are usually legally required that slot machines dispense a guaranteed win after at most some number of pulls, for much of the same reasons.

With that in mind, let's look at what Cult of the Lamb does when it rolls a random die in Knucklebones:

		Num = Random.Range(1, 7);

Yep, that's all there is to it: roll a random number between 1 (inclusive) and 7 (exclusive, i.e. 6 inclusive). Cult of the Lamb does not use the deck-of-cards method or anything of the sort - it just uses raw random numbers.

Another argument one could present would be that these (un-)lucky streaks are due to the imperfect random generation algorithms used by the game. After all, it is well known that computers generally do not generate true random numbers, by nature of being a perfectly predictable machine. In practice, the modern algorithm used by the game (Xorshift128, as used by Unity's Random) is unlikely to produce results that a human would be able to distinguish from true random numbers in this circumstance.

But, if the dice really are rolled randomly and fairly, why do we see so many posts and screenshots about ridiculously unlikely Knucklebones games? Well, let's do some quick math with an example:

• By itself, the odds of any six successive dice rolls to be all sixes is 0.0021% ((1/6)^6).
  
  
• Being conservative, let's consider the probability of six past successive die rolls being sixes within 15 samples (for the average number of rolls in a game), getting 0.032% (1-(1-((1/6)^6))^15).
  
  
• Next, let's multiply that by 20, for how many Knucklebones games a typical player is going to play, getting 0.64% (1-(1-((1/6)^6))^(15*20)).
  
  
• Finally, let's multiply that by a very conservative 1000, for how many people have played the game so far and are posting about it online (1-(1-((1/6)^6))^(15*20*1000)).
  
  
• The final result? 99.8%!

So, we can see that it's definitely not unlikely if we look at it on a global scale.

In conclusion, to answer the titular question: Knucklebones is not rigged. It is raw, unadulterated, pure randomness, which means that sometimes streaks of incredible (un-)luck happen.

Opponents

The in-game opponents that you can play Knucklebones with are:

Name	Max bet	Difficulty	Win chance	Average win
Ratau	10	10%	86.48%	7.30
Flinky	15	30%	82.84%	9.85
Klunko and Bop	20	50%	79.13%	11.65
Shrumy	50	80%	73.61%	23.61

Legend:

• Difficulty: Difficulty (which you can also see in the game) controls how often the opponent moves with randomly, vs. with intent.
  
  A difficulty of 10% means that they move randomly 90% of the time.
  
  
• Win chance: How often you're expected to win, if you play perfectly (e.g. using the solver).
  
  
• Average win: How much gold you'll gain per game on average, if you play perfectly.

Opponent AI

The opponent AI's algorithm can be described as a combination of randomness and moving in the column which has the most matches with the rolled die.

The opponents move according to the following algorithm:

• As described above, depending on the difficulty, sometimes they move randomly regardless of the situation on the board.
  
  Ratau moves randomly 90% of the time, and Shrumy 20%.
  
  When moving randomly, they randomly select a column with one or more free slots and move there.
  
  
• If there is a column which has three dice with the same value as the rolled die on your side of the board, they move there.
  
  
• Otherwise, they will move to the column which has the most matches (your side or their side) with the matched die.
  
  
• If there are no dice with the same face up anywhere on the board, they move randomly.

If more than one column matched at any of the above steps, they select randomly from any of the available choices.

Perfect Play

"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).

For more information, see Wikipedia:

https://en.wikipedia.org/wiki/Solved_game#Perfect_play

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 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.

Greedy Strategy

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

Better Strategy

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 (which are simple enough to put in a Steam guide) and evolved them to find one as close to perfect as possible.

Here is the current best strategy found by my program:

1. 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 has two or more dice, go to step 2.

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.

3. If you can place your die in such a way that it would delete one or more matching opponent's die, and after doing so you'll still have less total points than the opponent, then do so. Otherwise, go to step 4.

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.

Solver

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:

https://cy.md/ta/cult-of-the-lamb/knucklebones/

The solver shows win probabilities assuming you'll play perfectly (i.e. use the solver's best move for your every move).

If you choose "perfect opponent" in the opponent drop-down, the solver will show the best move assuming the opponent will play perfectly as well.

References

Source code for this guide, the solver, and miscellaneous tools can be found here:

https://gitlab.com/CyberShadow/cult-of-the-lamb-knucklebones

Thanks for reading!

[da55yd]

this is really interesting! however, i kinda expected a guide instead of this.

[shpaass]

That's insane. You're awesome.

[CyberShadow]

Very close to the win rate when playing against Ratau (86.48%), as Ratau moves randomly 90% of the time. So probably around 88%?

[K󠀡u󠀡nstdünger]

What would the winrate of perfect play (assuming a perfect opponent) be against a completely random player?
And now that I'm thinking about it how would that compare to perfect play assuming a random opponent

[CyberShadow]

Thank you! I've updated the guide with a few new sections, changelog here: https://gitlab.com/CyberShadow/cult-of-the-lamb-knucklebones/-/commits/master/guide

[Fluffy]

This was a really interesting read!

It's always fascinating to see how certain game mechanics work and the solver you made to figure out the best possibility of winning is insanely useful as well.

[BenocxX]

Oh I see! That's interesting! I'll take a closer look at D :)

[CyberShadow]

Thanks!

D is my favorite language, but it's not very popular. Many people haven't heard of it.

It works using a server-side app. The full graph with the game state scores takes about 20GB and took two hours to generate, so there's no way to do it fully client side like WebAssembly. So, the website just sends a fetch request to a PHP script which runs a command-line binary that produces the result as a JSON object.

[BenocxX]

Interesting guide!

I took a look at your code, what is this D language? I've never seen that before. How does it work for the website? Is it via web assembly?

Thanks :)