There is a standard table tennis match. The players take turns making 2 serves until the score is 10-10 or one of them reaches 11. After 10-10, overtime begins. Overtime ends as soon as one of the players gains a 2-point lead. Let's say we have 2 parameters:

  • p1 -probability of taking the round (serving) by the first player on his own submission
  • p2 -the probability of the first serving player taking the round (service) rival

We believe that the match does not go into overtime (if the score is 10-10, the game ends). It is necessary to implement an algorithm that accepts p1 and p2 as input, outputs the distribution of final scores in the format {(score1, score2): probability} by traversing possible outcomes through the tree.

Unfortunately, I got stuck at the very beginning. I reviewed about a dozen videos about trees, but I still don't understand how this moment can be realized. I would be grateful for any feedback

And why is the tree here? Or is it written in the homework statement -necessarily a tree?

Akina2021-10-14 02:42:10

yes, it is spelled out

alexander2021-10-14 02:42:10

Well, build a tree by breadth-first search. For each node, give birth to 2 offspring with probabilities pX and 1-pX from the probability of the parent, taking into account the order of delivery. And then you add up the probabilities of the leaves at each level.

Akina2021-10-14 02:42:10