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 has an advantage, beca

        This is achieved by an exhaustive search over all possible game series writing a trackback program like the one in Problem 8-9. The candidate set is composed from the possible outcomes {w,d,l} with multiple inclusion (i.e. without cutting the candidates). A solution is found if the length of the outcome vector vn has length g. There are N=3g such outcome vectors (permutations).The process_solution step consists of computing the number of points won by the defending champion given the current outcome vector vn. In this step we have to take into account whether the champion plays white or black, which can be determined from the number of games remaining r by r % 2.We count for how many outcome vectors the defending champion wins and divide by N. This gives the requested probability. The DP matrix maintains the points won at intermediate stages of a match, i.e., the sum of points for vectors vk with k<g. Once we consider game k, all required numbers of points won in games 1 to k-1 are stored in the DP matrix. At game k there are hence 3kâ’1 lookups and N=3Ă—3kâ’1 multiplications and DP writes to be performed. The runtime should thus be O(3g+1).