Konijnenhokken 1 - Get the maximum number of points
Let’s play a game. You are given seven dice with which you can earn points. Your goal: score as many points as possible in a limited number of rounds. In a real game, you would have an opponent trying to beat your score, but let’s only worry about a single player for now. For the harder problem, see Konijnenhokken 2.
How to play

Figure: Example of a possible game state. The points are rabbits, by the way, and it seems they multiply when you put them in cages.
After a roll, you can allocate the dice, either to score points directly or to use them as a multiplier. With the remaining dice, you may choose to roll again, for a chance to score even more points. Have all dice been allocated? You may then pick them up and keep going, keeping a tally of previously obtained points. In theory, it could therefore be possible to score infinitely many points in a single turn. But there is a catch: each time you roll, there is a chance that you die (gasp!), causing you to lose all points acquired this turn.
Okay so how do you score points, and when do you die? After a dice roll:
- A one can be used to score +1 point.
- A two can be used to score +2 points.
Only after you added at least one point, you may build your multiplier incrementally (x2 -> x3 -> x4 -> x5). To do this, a two may be played as a x2 multiplier (instead of the flat +2). Adding a three raises the multiplier to x3, etcetera, up to a maximum of x5. Rolled a six? Tough luck, this game has no use for them.
Unable to score points after a given roll? Oh no, you are dead! In other words, your roll should always include a one or a two in order for you to stay alive. A death always ends your turn with zero points, so be wise and end your turn in time to solidify your earnings.
Give it a try?
Base
Multiplier
Task
The AI shown above plays the strategy that awards the theoretical maximum expected number of points. That means it is essentially unbeatable if you try to play against it for many rounds. Your task is to figure out how to compute this optimal strategy, such that your friends won’t stand a chance the next time you play!
Solution
The key to the solution is to imagine the a possible state of the game as being a node of a graph. As you are taking your turn, you are effectively traversing through this graph. The state of a turn can be captured by just four numbers:
where
- are the points scored in previous runs of this turn (i.e. in which all dice were allocated).
- is the number of ones allocated.
- is the number of twos played for points.
- is the number of cages collected, such that .
Every decision you make in the game moves you to a different game state. To play the game optimally, we need to know which states are good and which to avoid. Our task is to maximize the expected number of points, so let this be the quality metric of a state,
The value of a state is either simply the number of points it awards when you stop, or the number of points you can expect when you continue to play. After we successfully compute for every possible state in the game, making perfect decisions becomes a piece of cake: keep playing until . When you stop, you are awarded
If you choose to play, your expected score is the weighted average of all possible dice rolls:
where is the probability of a roll, and is the quality of the state where you end up after allocating the dice optimally:
Notice that we are dealing with a recursive problem: to compute , we need to already know the value of all the possible destinations, . Hence, we need to solve the end-states first and work backwards towards the start of the game. Slight problem: a turn could in principle take infinitely long. How do you work backwards from infinity? Fortunately, we know there must exist a score beyond which stopping is always best: if you have a million points, you should certainly quit no matter what. We call this threshold the depth, and all we need to do is provide a conservative estimate (e.g. ). The true depth should be notably smaller than our guess, and we can check this in the end to make sure that the guess was valid (). Now we have the endpoint we need, and we can start working backwards.
Solution algorithm
from math import factorial, prod
from collections import Counter
from itertools import combinations_with_replacement
import pickle
_Q = dict() # Cache
DEPTH = 133
NUM_DICE = 7
def Q(T):
"""Quality of state T"""
return max(Q_stop(T), Q_play(T))
def Q_stop(T):
return points_stop(T)
def points_stop(T):
t, r1, r2, c = T
return t + (r1 + 2*r2)*(c+1)
def Q_play(T):
# If the state has all dice allocated, treat it as the state that follows
# e.g. (0, 0, 6, 1) becomes (24, 0, 0, 0)
if sum(T[1:]) == NUM_DICE:
T = (points_stop(T), 0, 0, 0)
if T not in _Q:
if T[0] >= DEPTH: _Q[T] = -1 # Base case: stop if we have too many points
else: _Q[T] = sum(P(roll) * Q_roll(T, roll) for roll in rolls(T))
return _Q[T]
def Q_roll(T, roll: dict):
return max((Q(T2) for T2 in allocations(T, roll)), default=0)
def allocations(T: tuple, roll: dict):
t, r1, r2, c = T
states = set()
for ones in range(roll[1]+1):
for twos in range(roll[2]+1):
if ones == twos == 0: continue # Must add atleast one rabbit
states.add((t, r1+ones, r2+twos, c)) # Adding only rabbits is one possibility
# Alternatively, add any number of cages as well
for dc, cage in enumerate(range(c+2, 6), 1):
if roll[cage] <= (twos if cage == 2 else 0): break # Played my only two for points
states.add((t, r1+ones, r2+twos, c+dc))
return states
def P(roll: dict):
f = probability_weight(roll)
return f * prod((1/6)**count for count in roll.values())
def probability_weight(roll: dict):
"""E.g. (1, 2, 2, 3) has twelve rearrangements"""
f = factorial(sum(roll.values()))
for v in roll.values():
f //= factorial(v)
return f
def rolls(T, options=(1, 2, 3, 4, 5, 6)):
dice_remaining = NUM_DICE - sum(T[1:])
return [Counter(x) for x in combinations_with_replacement(options, dice_remaining)]
if __name__ == "__main__":
Q((0, 0, 0, 0)) # This call builds the cache (_Q)
_Q = {T: Q_T for T, Q_T in sorted(_Q.items()) if Q_T > points_stop(T)} # Only include play-states
FILENAME = __file__.rstrip('.py') + '.pkl'
with open(FILENAME, 'wb') as f:
pickle.dump(_Q, f)