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

Example game state

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:

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?

versus

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:

T=(t,r1,r2,c)T = (t, r_1, r_2, c)

where

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,

Q[T]=max⁡(stop[T],play[T])Q[T] = \max(\text{stop}[T], \text{play}[T])

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 Q[T]Q[T] for every possible state in the game, making perfect decisions becomes a piece of cake: keep playing until stop[T]>play[T]\text{stop}[T]>\text{play}[T]. When you stop, you are awarded

stop[T]=t+(r1+2r2)(c+1)\text{stop}[T] = t + (r_1 + 2 r_2)(c + 1)

If you choose to play, your expected score is the weighted average of all possible dice rolls:

play[T]=∑rolls(T)proll⋅Qroll[T,roll]\text{play}[T] = \sum_{\text{rolls}(T)} p_\text{roll} \cdot Q_\text{roll}[T, \text{roll}]

where prollp_\text{roll} is the probability of a roll, and Qroll[T,roll]Q_\text{roll}[T, \text{roll}] is the quality of the state where you end up after allocating the dice optimally:

Qroll[T,roll]=max⁡T′∈allocations(T,roll)Q[T′]Q_\text{roll}[T, \text{roll}] = \max_{T' \in \text{allocations}(T, \text{roll})} Q[T']

Notice that we are dealing with a recursive problem: to compute Q[T]Q[T], we need to already know the value of all the possible destinations, Q[T′]Q[T']. 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. depth_guess=200\text{depth\_guess} = 200). 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 (true_depth+max_run_score<depth_guess\text{true\_depth} + \text{max\_run\_score} < \text{depth\_guess}). 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)