1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Chess match probability

  1. May 16, 2016 #1
    1. The problem statement, all variables and given/known data
    A chess master plays n games at a chess competition, each against a different opponent. Based on their past performances, we can estimate the probabilities of each opponent beating the master: p1, . . . , pn ∈ [0, 1]. Describe an algorithm, which given integer k returns the probability that the master wins exactly k out of n games. Then, use it to find the probability of the chess master winning the majority of the games (at least d n 2 e).

    2. Relevant equations


    3. The attempt at a solution
    This time I have a solution. Let k P n denote the probability that he wins k out of n. I came up with the following formula to fill out the table

    kPn=(1-Pn)(kP(n-1))+((k-1)P(n-1))Pn

    In this case Pn is the prob that he wins and 1-pn that loses
    Does that work
     
    Last edited: May 17, 2016
  2. jcsd
  3. May 17, 2016 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Do not use the exact same title "Dynamic programming question" for two totally different threads. Doing that makes it difficult for other users to navigate this Forum properly.
     
  4. May 17, 2016 #3
    Ok, I will keep that in mind for next time.
     
  5. May 17, 2016 #4

    Mark44

    Staff: Mentor

    What does d n 2 e mean?
    The notation kPn is sometimes used to represent the number of permulations of n things taken k at a time.
    How did you get this?
    Try to be more consistent. The function in your algorithm should probably be written P(k) or P(k, n).
    You have written Pn and pn. Are these the same? According to the problem statement, p1 is the probability that opponent 1 beats the chess master, and pn is the probability that opponent n beats the chess master. Using pn and Pn interchangeable (as you seem to do) is confusing.
     
  6. May 17, 2016 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    OK. In any case, this problem has nothing at all to do with "dynamic programming" as it is normally understood (which means a particular approach to some types of optimization problems). The current problem has no connection to optimization in any sense.

    Mod note: I changed the thread title to better reflect what the question was about.

    Also: you need to assume that the chess master's wins/losses are independent between the different opponents, so that if he wins or loses against opponent #i that will have no effect on whether or not he wins or loses with opponent #j for any j≠i.
     
    Last edited by a moderator: May 17, 2016
  7. May 17, 2016 #6
    hey sorry at least n/2. I came up with that formula by trying to see a pattern in the table. I tried it for a couple of entries and it worked. kPn represents the prob that the master wins k out of n games.
     
  8. May 17, 2016 #7

    Mark44

    Staff: Mentor

    d n 2 e means n/2? Huh? How could we possibly have known that?
    That doesn't really tell me how you arrived at that formula.

    Please give more precise descriptions of the terms in your formula. "Pn is the prob that he wins" -- Do you mean he wins an individual match? If so, which match?
    What does P(n - 1) mean? Is Pn different from pn? (You use both in what I quoted.)

    Also, who is "he", the opponent or the master?
     
  9. May 17, 2016 #8
    I am just going to restate everything I said. P(k,n) is denoted as the probability that the master wins k out of n games. P(1,1) the prob that the master wins 1 out of 1. P(1,2) the probability that he wins 1 out of 2 etc. I was trying to find a way to use all these subproblems to get to P(k,n). I switched in this case P_n and 1-P_n. P_n is the probability that the master wins the nth game. For example in the base case P(0,0)=1

    if we use my formula to compute P(0,1), we get P(0,1)=(1-p1)(P(0,0))+(P(-1,0)P1)=(1-p1)+0 which is right. That's the prob that he wins 0 out of 1.
    P(1,1)=(1-p1)(p(1,0))+p(0,0)p1=0+1*p1=p1

    Magically this formula works for the couple of entries I computed.. The way I came up with this formula was by comparing the real values computed by math and the obtained subproblems. For example to compute P(2,1) , I tried to look for the factors in the subproblems that match the real solution and based on that I built the formula. It was merely brute force.
     
  10. May 17, 2016 #9

    Mark44

    Staff: Mentor

    P(1, 2) would be the probability that the master wins exactly one of the two matches. In this case the master could win the first match OR he could win the second match. If the first two players have different skill levels, then P1 and P2 are different, so I'm not sure what value should be assigned to P(1, 2).

    (I'm assuming here that Pk is the probability that the master wins the match against the k-th opponent. This is what you said in post #12, but it's the opposite of what you showed in the first post, where it represents the probability that the k-th opponent wins the match. )

    P(1, 3) is the probability that the master wins exactly one of the first three matches, which means that he has to win the first match OR he has to win the second match OR he has to win the third match.

    P(2, 3) is a bit more complicated, as it is the probability of winning:
    1st and 2nd matches, OR
    1st and 3rd matches, OR
    2nd and 3rd matches
     
  11. May 17, 2016 #10
    Right , I pulled out my conclusion from P(1,3)

    P(1,3)=P1(1-P2)(1-P3)+P2(1-P1)(1-P3)+P3(1-P2)(1-P1)
    P(1,3)=(1-P3)(P1(1-P2)+P2(1-P1)+P3(1-P2)(1-P1)
    P(1,3)=(1-P3)P(1,2)+P3*P(0,2) and it turns out that it works.
     
  12. May 17, 2016 #11

    Mark44

    Staff: Mentor

    I see how you get from the first line to the second, although it's hard to follow since you're missing a right parenthesis. Also, you don't need to write P(1,3) on each line -- you can start a new line with '=', like so:
    P(1,3)=P1(1-P2)(1-P3) + P2(1-P1)(1-P3) + P3(1-P2)(1-P1)
    =(1-P3)(P1(1-P2) + P2(1-P1)) + P3(1-P2)(1-P1)
    It's easier to read if you add some spaces here and there, especially before and after '+' and after ','.

    What do you get for P(2, 3)? How about P(3, 3)? P(1, 4), P(1, 2), etc.? Can you come up with a general expression for P(k, n)?
     
  13. May 17, 2016 #12

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You say "P(1,1) the prob that the master wins 1 out of 1". That is not possible to say, because it depends on who is his opponent; each opponent has a different win/lose probability.

    Using a generating-function method, the probabilty that the master loses exactly ##m## of the matches is the coefficient of ##z^m## in the expansion of the generating function
    [tex] f(z) = (q_1 + p_1 z)(q_2 + p_2 z) \cdots (q_n + p_n z), \;\; q_i = 1 - p_i \; \text{for} \: i = 1,2, \ldots, n [/tex]
    Here, ##p_i## is the probability he loses against opponent ##i##.

    Note that if all the ##p_i## were equal to some common value ##p##, ##f(z)## would be the generating function of a binomial distribution, and the coefficient of ##z^m## would be ##C(n,m) p^m q^{n-m}##. However, your case has unequal ##p_i##, so it will be more complicated.
     
    Last edited: May 19, 2016
  14. May 17, 2016 #13
    mmm you are right. I was also thinking about that but this is what my instructor said, so I just followed what he said

    Let's play around with a few toy examples; if these don't help please feel free to ask follow up questions.



    So, let's assume that our Grand Master is only playing a single game. This means that we have a single value p1 which is the probability that the master wins. [Edit - note that, as mentioned below, I got the probability backward. p1 is the odds that the master loses. However, for the computations below, the formulae hold, but with the k's flipped around]


    So, if k=1, our answer should just be p1 (which is the probability of winning 1 out of 1 games), and if k=0, we should return 1−p1 instead.



    If we have 2 games to play, then we have two values, p1 and p2, and which means that k∈{0,1,2} (since we can win anywhere from 0-2 games).



    To win 0 games, we'd have to lose both games, which means that the probability of that happening is (1−p1)(1−p2). Similarly, the probability of winning both games is p1p2. Finally, the probability of winning exactly one of the two games is p1(1−p2)+p2(1−p1) (or the probability of winning game one then losing game two, plus the probability of losing game one and then winning game two).



    This generalizes to arbitrary numbers of games.


    ....
    .
    .
    I think that we are assuming matches are played in a row.
     
  15. May 17, 2016 #14
    P(k,n)=(1-Pn)(P(k,n-1)+P(k-1,n-1)Pn
     
  16. May 18, 2016 #15

    Mark44

    Staff: Mentor

    Where did this come from? You didn't even show what you got for P(2, 3). I don't see how you generalize on the basis of what you showed earlier.
     
  17. May 18, 2016 #16

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    This approach is unlikely to be helpful. The probabilities are different for each of the n opponents, so the probability of beating k depends on which k.
    See if you can rewrite your equation in post #14 based on playing a specific opponent first. And get rid of the extra left parenthesis.
     
  18. May 19, 2016 #17

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    While the OP's presentation is sloppy and incomplete, it is fundamentally OK: the OP assumes (without bothering to say so) that the games are played against opponents 1,2,3... in that order. So, the probability of winning j games in k is the probability of winning j games in (k-1), times the probability of losing game k, plus the probability of winning (j-1) games in (k-1), times the probability of winning game k.
     
  19. May 19, 2016 #18

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, I misinterpreted it. The parentheses still need correcting.
     
  20. May 19, 2016 #19

    Mark44

    Staff: Mentor

    The OP has been banned as being a sockpuppet for numerous other banned members.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Chess match probability
  1. Chess game combinations (Replies: 10)

  2. Matching two series (Replies: 15)

Loading...