Konijnenhokken 2 - Maximum win probability

New to the game, or want to try the easier version of this problem first? See Konijnenhokken 1.

Task

In the prequel to this problem, we introduced the dice game Konijnenhokken and managed to find the strategy that maximizes the expected number of points per turn. This strategy is great, because it guarantees you will win, provided you play infinitely many rounds. Just a minor issue: I don’t have an eternity to spare, do you? Real games are finite, and in this case it matters if you are close to the finish as well as whether you are currently ahead or behind in points.

Here, we consider a one-on-one game played to 200 points. Once a player reaches 200, the round is finished so that both players have had the same number of turns. Whoever has the most points at that moment wins, even if the final scores go beyond 200.

Your goal: find the strategy that maximizes the probability of winning. A draw counts as half a win. You don’t know if you will start or take the second turn, so be prepared for either case.

Give it a try?

The 1v1 AI below plays the strategy that maximizes its chance of winning. Watch it take on the Perfect solo AI from the prequel, which only maximizes its points per turn, or try to beat it yourself. Who starts is decided by a coin toss.

versus

Base

Multiplier

Solution

State

Previously, every possible state of a player’s turn was represented by four numbers:

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

That is no longer enough. Whether you should keep rolling now also depends on the scoreboard: when your opponent is at 190 and you are 50 points behind, you have to take risks you would never take with a comfortable lead. So we additionally keep track of the scoreboard and whose turn it is:

S=(nA,nB,i)S = (n_A, n_B, i)

where nAn_A and nBn_B are the banked scores of players A and B, and ii takes the value 0 or 1, pointing to the player whose turn it is (A or B, respectively). Player A is the one who starts the game. The full state of the game is the combination (S,T)(S, T), and every turn starts from the empty turn state T0=(0,0,0,0)T_0 = (0, 0, 0, 0).

State quality

Our approach will again be to measure the quality of each state. Instead of the expected number of points, it is now the win probability of the player whose turn it is:

Q[S,T]=Pwin+12PdrawQ[S, T] = P_\text{win} + \tfrac{1}{2} P_\text{draw}

This is a zero-sum game: a win for you is a loss for your opponent, and a draw is half a win for both. So if your quality of a state is QQ, your opponent’s quality of that same state is simply 1−Q1 - Q. This saves us from having to keep track of two numbers per state. Like before, the quality is the better of your two choices, stop or play:

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

When you stop, you bank the points of your turn. Recall from the previous exercise that this amounts to

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

The scoreboard is updated and the turn passes to your opponent, who starts with an empty turn:

S′=(nA+(1−i) nstop[T],  nB+i nstop[T],  1−i)S' = (n_A + (1-i) \, n_\text{stop}[T], \; n_B + i \, n_\text{stop}[T], \; 1-i)

where the prefactors (1−i)(1-i) and ii ensure the points are awarded to the appropriate player. In the new state it is your opponent’s turn, so their quality is Q[S′,T0]Q[S', T_0] and yours is what is left:

Qstop[S,T]=1−Q[S′,T0]Q_\text{stop}[S, T] = 1 - Q[S', T_0]

When you continue, your win probability depends on what you roll. Just like before, it is the weighted average over all possible rolls:

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

where prollp_\text{roll} is the probability of a roll, and Qroll[S,T,roll]Q_\text{roll}[S, T, \text{roll}] is the quality of the state where you end up after allocating the dice optimally. The scoreboard does not change during your turn, so only TT moves:

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

End of the game

The game ends after B’s turn, once either player has reached 200 points. At that moment it is A’s turn again, so the end states are those with i=0i = 0 and max⁡(nA,nB)≥200\max(n_A, n_B) \geq 200. Their quality (for A) is known directly:

Q[Send]={1if nA>nB12if nA=nB0if nA<nBQ[S_\text{end}] = \begin{cases} 1 & \text{if } n_A > n_B \\ \tfrac{1}{2} & \text{if } n_A = n_B \\ 0 & \text{if } n_A < n_B \end{cases}

Note that when A reaches 200, the game is not over yet: B gets one final turn to catch up. We don’t have to treat this as a special case. B’s quality of stopping is 1−Q[Send]1 - Q[S_\text{end}], so B automatically learns to keep rolling until they have beaten A’s score.

Working backwards

Like before, we are dealing with a recursive problem, so we solve the end states first and work backwards towards the start of the game. Scores can only go up, so stopping always leads to a scoreboard with more points. We can therefore go through the scoreboards from high to low, and within each scoreboard go through the turn states TT from high to low, just like in the previous exercise. Since final scores can go beyond 200, we again need a conservative cap on the scores, beyond which nothing changes anymore.

There is a catch, though: dying passes the turn without changing the scoreboard. If A dies and then B dies, we are back at A’s turn with exactly the same scores. So for every scoreboard, the start-of-turn qualities of A and B depend on each other:

Q[(nA,nB,0),T0]  ↔  Q[(nA,nB,1),T0]Q[(n_A, n_B, 0), T_0] \;\leftrightarrow\; Q[(n_A, n_B, 1), T_0]

and neither can be computed before the other. We solve this by iteration: start with a guess for both values (say 12\tfrac{1}{2}), compute the turns of both players using these guesses, and use the outcomes as the new guesses. Repeat until the values stop changing. Because the chance of dying is smaller than one, every iteration shrinks the error, and the values converge quickly.

Once this is done for every scoreboard, we have the answer to the task. At the start of the game, the starting player wins with probability Q[(0,0,0),T0]Q[(0, 0, 0), T_0], and the other player with probability 1−Q[(0,0,0),T0]1 - Q[(0, 0, 0), T_0]. The strategy is the same as before: in every state, pick whichever of stop, play and the possible allocations has the highest quality.

Solution algorithm

from functools import cache
from solve_maxpoints import points_stop, allocations
from solve_final import SolverFinalTurn, _rolls

TARGET   = 10
NUM_DICE = 7
T0       = (0, 0, 0, 0)  # initial state of a turn
ROLLS    = {n: _rolls(n) for n in range(1, NUM_DICE+1)}  # ROLLS[dice] -> [(p, roll)]

_Q        = {}  # Q[S][T] -> float
_Q_T0     = {}  # Solutions where T=T0
_Q_T0_EST = {}  # contains guesses to be refined

def Q_T0(S):
    """Win probability for the player to move at the start of their turn in S"""
    a, b, i = S
    if game_over(S):    return 1 if a > b else 0.5 if a == b else 0
    if final_turn(S):   return Q_final(S[0] - S[1])  # B must beat A's score in one turn
    if S in _Q_T0:      return _Q_T0[S]
    if S in _Q_T0_EST:  return _Q_T0_EST[S]  # Solving in progress

    solve_Q_T0(S)  # resolve infinite loop (S -> bust -> bust -> S) using value iteration
    for S_ in (S, bust(S)):
        if S_ in _Q_T0_EST:  _Q_T0[S_] = _Q_T0_EST.pop(S_)  # Converged on a solution
    return _Q_T0[S]

def solve_Q_T0(S, tolerance=1e-6):
    """Compute initial states using value iteration"""
    S_bust = bust(S)
    _Q_T0_EST[S] = 0.5  # guess once
    while True:
        old = _Q_T0_EST[S]

        # Refine the guess by completing one cycle: S = bust(bust(S))
        _Q_T0_EST[S_bust] = solve_turn(S_bust)
        _Q_T0_EST[S]      = solve_turn(S)

        if abs(_Q_T0_EST[S] - old) < tolerance:
            break

    return _Q_T0_EST[S]

def solve_turn(S):
    """Value of the turn of S, with a fresh table: the bust value may have changed since last time"""
    _Q[S] = {}
    value = Q(S, T0)
    del _Q[S]  # If we don't need to remember all mid-turn solutions
    return value

def Q(S, T):
    q_stop = Q_stop(S, T)
    if q_stop == 1:  return q_stop      # Stopping already wins for sure
    return max(q_stop, Q_play(S, T))

def Q_stop(S, T):
    return 1 - Q_T0(stop(S, T)) # I win = 1 - you win

def Q_play(S, T):
    # All dice placed: bank them on the board and roll all dice again
    if sum(T[1:]) == NUM_DICE:
        T = (points_stop(T), 0, 0, 0)

    table = _Q[S]
    if T not in table:
        if not worth_rolling(S, T):  table[T] = Q_stop(S, T)  # Base case: stopping is better
        else:                        table[T] = sum(p * Q_roll(S, T, roll) for p, roll in ROLLS[NUM_DICE - sum(T[1:])])
    return table[T]

def worth_rolling(S, T):
    """Even if every roll that doesn't bust won the game, rolling must beat stopping"""
    p_bust = (4/6) ** (NUM_DICE - sum(T[1:]))
    return Q_stop(S, T) < p_bust * (1 - Q_T0(bust(S))) + (1 - p_bust)

def Q_roll(S, T, roll):
    options = allocations(T, roll)
    if not options:
        return 1 - Q_T0(bust(S))
    return max(Q(S, T_next) for T_next in options)

def bust(S):
    return (*S[:2], 1-S[2])

def stop(S, T):
    """Player i banks the points of T, then it's the other player's turn"""
    a, b, i = S
    if i == 0:  return (a + points_stop(T), b, 1)    # A banks, B to move
    else:       return (a, b + points_stop(T), 0)    # B banks, A to move

def final_turn(S):
    """B's turn after A reached the target: the game ends after this turn"""
    a, b, i = S
    return i == 1 and a >= TARGET

@cache
def Q_final(gap):
    """Win probability of B's final turn, trailing by `gap` points (solve_final)"""
    return SolverFinalTurn(gap).Q_play(T0)

def game_over(S):
    """The round ends after B's turn: when A is to move again and someone reached the target"""
    a, b, i = S
    return i == 0 and max(a, b) >= TARGET