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. Then players take turns playing white and black. White has an advantage, because she moves first. The champion plays white in the first game. He has probabilities wwin, wdrawing, and wloss with white, and has probabilities bwin, bdrawing, and bloss with black. Required:
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 win i games (which may end in a 1/2).
b. Analyze the running time of the respective dynamic program for an n game match.