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.
Base
Multiplier
Solution
State
Previously, every possible state of a player’s turn was represented by four numbers:
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:
where and are the banked scores of players A and B, and 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 , and every turn starts from the empty turn state .
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:
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 , your opponent’s quality of that same state is simply . 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:
When you stop, you bank the points of your turn. Recall from the previous exercise that this amounts to
The scoreboard is updated and the turn passes to your opponent, who starts with an empty turn:
where the prefactors and ensure the points are awarded to the appropriate player. In the new state it is your opponent’s turn, so their quality is and yours is what is left:
When you continue, your win probability depends on what you roll. Just like before, it is the weighted average over all possible rolls:
where is the probability of a roll, and 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 moves:
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 and . Their quality (for A) is known directly:
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 , 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 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:
and neither can be computed before the other. We solve this by iteration: start with a guess for both values (say ), 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 , and the other player with probability . 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