10.25

(a) Recurrence.
Let
    [math]P(g,i,c)[/math] = probability the champion finally keeps the title when
      • [math]g[/math] games are still to be played;
      • he still needs at least [math]i[/math] points to reach 12 (so a tie or better);
      • [math]c\in\{0,1\}[/math] denotes the colour of the very next game         ([math]c=0[/math] ⇒ champion has White, [math]c=1[/math] ⇒ Black).

Base cases
    [math]P(g,i,c)=1\;[/math] if [math]i\le 0[/math] (target already reached);
    [math]P(0,i,c)=0\;[/math] if [math]i>0[/math] (no games left but still behind).

Induction step (assume [math]g>0[/math] and [math]i>0[/math]):
  If [math]c=0[/math] (champion plays White next)
    [math]P(g,i,0)= w_w\,P(g-1,i-1,1)\;+\;w_d\,P(g-1,i-\tfrac12,1)\;+\;w_l\,P(g-1,i,1).[/math]
  If [math]c=1[/math] (champion plays Black next)
    [math]P(g,i,1)= b_w\,P(g-1,i-1,0)\;+\;b_d\,P(g-1,i-\tfrac12,0)\;+\;b_l\,P(g-1,i,0).[/math]

(b) Dynamic-programming algorithm.
Points come in half-point units, so store all scores doubled to keep indices integral. Let [code]N = 2n[/code] and [code]need = 2·12 = 24[/code]. The table [code]P[g][k][c][/code] holds [math]P(g,k/2,c)[/math].
def retain_prob(n, ww, wd, wl, bw, bd, bl):
  N = 2*n   # games index 0 … n
  K = 2*12   # 24 half-points must be reached
  P = [[[0.0,0.0] for _ in range(K+1)] for _ in range(n+1)]

  # base i ≤ 0 → 1
  for g in range(n+1):
    P[g][0][0] = P[g][0][1] = 1.0

  # fill increasing g
  for g in range(1,n+1):
    for k in range(1,K+1):
      # colour parity: after (n-g) already played
      c0 = (n-g)%2 # 0→White,1→Black for next game
      c1 = 1-c0
      # champion to move with White
      P[g][k][0] = ( ww * P[g-1][max(0,k-2)][1] +
                wd * P[g-1][max(0,k-1)][1] +
                wl * P[g-1][k][1] )
      # champion to move with Black
      P[g][k][1] = ( bw * P[g-1][max(0,k-2)][0] +
                bd * P[g-1][max(0,k-1)][0] +
                bl * P[g-1][k][0] )

  return P[n][K][0] # start: 24 games left, need 12 pts, champion has White

(c) Running-time analysis.
• State space: for an [math]n[/math]-game match, [math]g=0…n[/math] (≈[math]n+1[/math]) and   [math]k=0…2n[/math] half-point values (≤[math]2n+1[/math]) for each of two colours.
• Each state is computed in O(1) time. Therefore total running time Θ([math]n·2n·2[/math]) = Θ([math]n^{2}[/math]); memory requirement is the same order.

Back to Chapter 10