Samsam's blog

By Samsam, history, 9 years ago, In English

I was trying to solve this problem on topcoder. The output for the problem is the probability that Jane wins the game, but my problem is that I think that the probabilty of each player to win the game is always 0.5 and that isn't correct according to the output of some given testcases in the problem. The reason of my thinking is that both players have the same number of turns and both of them have exactly the same choices to play. So I wonder if somebody could explain to me why the probabiltiy isn't always 0.5.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The reason is that you are not trying to maximize the expected value, but to win the game, so you can take advantage of the additional information (current score, remaining darts) to achieve better chance of victory.

For the sake of an example, let's say they throw darts at a line 8880099 and the chance is to hit one of the three consecutive boxes. Say they have two darts each and in the first round they both throw at 888, in the second round the first player throws at 888 again. Now, 099 nets less expected score, but as you can see, for the second player, it gives 2/3 chance of winning as opposed to 1/2 if he throws at 888 again.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thanks, it is clear now

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't get it right , suppose we have only 1 round and board (8880999) and i want to calculate the probability of the first player to win the game , we only face these situations:


    1 - fir = 888, sec = 888, ans = 0.5 2 - fir = 888, sec = 099, ans = 1/3 3 - fir = 099, sec = 888, ans = 2/3 4 - fir = 099, sec = 099, ans = 0.5

    (0.5 + 1/3 + 2/3 + 0.5) / 4 = 0.5

    so I see that it's 0.5, did I miss something?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think that your situations must be reduced to:

      1- fir = 888, sec = 099, ans = 1/3

      2- fir = 099, sec = 099, ans = 0.5

      because in situations 1 and 3 the second player isn't playing optimally.