Write a recurrence for the probability that the champion retains the title?

Problem:

The traditional world chess championship is a match of 24 games. The current champion retains the title in case the match is a tie. Each game ends in a win, loss, or draw (tie) where wins count as 1, losses as 0, and draws as 1/2. The players take turns playing white and black. White plays first and so has an advantage. The champion plays white in the first game. The champ has probabilities ww, wd, and wl of winning, drawing, and losing playing white, and has probabilities bw, bd, and bl of winning, drawing, and losing playing black.

(a) Write a recurrence for the probability that the champion retains the title. Assume that there are g games left to play in the match and that the champion needs to get i points (which may be a multiple of 1/2).

I found this problem in skiena's Algorithm design manual book and tried to solve it.

My take on this problem is At i`th game a champion must either win , lose or tie the game.we have prior probability of ww,wd and wl(since champion starts from white I am considering only ww,wd and wl only). so the probability that the champion will win is equal to current outcome weightage multiplied by prior probability,

P_win(i) = ∑(prior_p * current_outcome_weightage) = ((ww*win_weight)+(wd*draw_weight)+(wl*loss_weight))/3

current outcome weightage is either one of the three case:

if champion wins : win_weight=1,draw_weight=0,loss_weight=0
if champion loses: win_weight=0,draw_weight=0,loss_weight=0
if champion draws: win_weight=0,draw_weight=1/2,loss_weight=0

Is there any better way to write the recurrence for this problem?

Solution

You basically need to "guess" at the current probability if the champion wins loses or draws, and recurse based on it, modifying i according to win/loss/draw - and always reducing g.

Stop clause is if either champion wins (no more points needed) or loses (no more games left).

(Note, conditions are evaluated in order, so g==0, i==0 will apply g<=0 only, for example)
    Sol(g, i) =  {
    i <= 0:               1
    g == 0:               0
    i%2 == 0:             ww*Sol(g-1, i-1) + wd*Sol(g-1,i-1/2) + wl*Sol(g-1,i)
    i%2 == 1:             bw*Sol(g-1, i-1) + bd*Sol(g-1,i-1/2) + bl*Sol(g-1,i)
}

Quick sanity test, if there is a final match left, and the champion must win it - then the probability of him winning is bw. In this case you need to evaluate: Sol(1, 1) = bw*Sol(0,0) + bd*Sol(0,1/2) + bl*Sol(0,1) = bw*1 + bd*0 + bl*0 = bw