# Untitled

a guest
Jan 2nd, 2018
1,078
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def expected_rolls(x, y):
2. #The first state, where all players have \$Y:
3. starting_state = [y for i in range(x)]
4. starting_state.append(0)
5.
6. #The first probability distribution of states:
7. states = {tuple(starting_state):1.}
8. rolls = 0
9. expected = 0.
10. prob_over = 0.
11.
12. for t in range(20): #Within 20 rounds, the probability that the game is still going is negligible for what we need.
13. for i in range(x): #Each player's turn
14. for rolls_per_turn in range(3): #Each player's roll
15. rolls += 1
16. new_states = {}
17. for state, prob in states.items():
18. if state[i]>0: #Only roll if player i has at least \$1
19. new_state_left = list(state)
20. new_state_left[i] -= 1
21. new_state_left[(i-1)%x] += 1
22. new_state_left = tuple(new_state_left)
23.
24. new_state_right = list(state)
25. new_state_right[i] -= 1
26. new_state_right[(i+1)%x] += 1
27. new_state_right = tuple(new_state_right)
28.
29. new_state_center = list(state)
30. new_state_center[i] -= 1
31. new_state_center[x] += 1
32. new_state_center = tuple(new_state_center)
33.
34. left_sum = sum(new_state_left[:x])
35. right_sum = sum(new_state_right[:x])
36. center_sum = sum(new_state_center[:x])
37.
38. new_prob = prob/3.
39.
40. if sum([1 for k in range(x) if new_state_left[k]==left_sum])==1: #End of game
41. expected += new_prob*rolls
42. prob_over += new_prob
43. else: #The distribution after this turn
44. if new_state_left not in new_states:
45. new_states[new_state_left] = new_prob
46. else:
47. new_states[new_state_left] += new_prob
48.
49. if sum([1 for k in range(x) if new_state_right[k]==right_sum])==1:
50. expected += new_prob*rolls
51. prob_over += new_prob
52. else:
53. if new_state_right not in new_states:
54. new_states[new_state_right] = new_prob
55. else:
56. new_states[new_state_right] += new_prob
57.
58. if sum([1 for k in range(x) if new_state_center[k]==center_sum])==1:
59. expected += new_prob*rolls
60. prob_over += new_prob
61. else:
62. if new_state_center not in new_states:
63. new_states[new_state_center] = new_prob
64. else:
65. new_states[new_state_center] += new_prob
66. else:
67. if state not in new_states:
68. new_states[state] = prob
69. else:
70. new_states[state] += prob
71.
72. states = new_states
73. return expected