为冠军保留冠军的概率写一个递归式？

Question

问题：

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).

我在skiena的算法设计手册书上发现了这个问题，并尝试解决

我对这个问题的看法是在第 i 场比赛中，冠军必须赢、输或打平 game.we 具有 ww、wd 和 wl 的先验概率（因为冠军从白色开始，我只考虑仅限 ww、wd 和 wl）。所以冠军获胜的概率等于当前结果权重乘以先验概率，

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

当前结果权重是以下三种情况之一：

如果冠军获胜：win_weight=1,draw_weight=0,loss_weight=0
如果冠军输了：win_weight=0,draw_weight=0,loss_weight=0
如果冠军平局：win_weight=0,draw_weight=1/2,loss_weight=0

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

Answer 1

你基本上需要“猜测”当前的概率是冠军赢输还是平局，并以此为基础进行递归，根据win/loss/draw修改i - 并始终减少g.

如果冠军获胜（不需要更多积分）或失败（没有更多比赛剩余），则停止条款。

(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)
}

快速理智测试，如果还有最后一场比赛，冠军必须赢得比赛 - 那么他获胜的概率是 bw。在这种情况下，您需要评估：Sol(1, 1) = bw*Sol(0,0) + bd*Sol(0,1/2) + bl*Sol(0,1) = bw*1 + bd*0 + bl*0 = bw

为冠军保留冠军的概率写一个递归式？

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

algorithm

recurrence