Блог пользователя Samsam

Автор Samsam, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh thanks, it is clear now

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.