题目84：在大富翁游戏中，找出最受欢迎的三个格子
本帖最后由 欧拉计划 于 2016-8-9 17:38 编辑Monopoly odds
In the game, Monopoly, the standard board is set up in the following way:
A player starts on the GO square and adds the scores on two 6-sided dice to determine the number of squares they advance in a clockwise direction. Without any further rules we would expect to visit each square with equal probability: 2.5%. However, landing on G2J (Go To Jail), CC (community chest), and CH (chance) changes this distribution.
In addition to G2J, and one card from each of CC and CH, that orders the player to go directly to jail, if a player rolls three consecutive doubles, they do not advance the result of their 3rd roll. Instead they proceed directly to jail.
At the beginning of the game, the CC and CH cards are shuffled. When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile. There are sixteen cards in each pile, but for the purpose of this problem we are only concerned with cards that order a movement; any instruction not concerned with movement will be ignored and the player will remain on the CC/CH square.
[*]Community Chest (2/16 cards):
[*] Advance to GO
[*] Go to JAIL
[*]Chance (10/16 cards):
[*]Advance to GO
[*] Go to JAIL
[*] Go to C1
[*] Go to E3
[*] Go to H2
[*] Go to R1
[*] Go to next R (railway company)
[*] Go to next R
[*] Go to next U (utility company)
[*] Go back 3 squares.
The heart of this problem concerns the likelihood of visiting a particular square. That is, the probability of finishing at that square after a roll. For this reason it should be clear that, with the exception of G2J for which the probability of finishing on it is zero, the CH squares will have the lowest probabilities, as 5/8 request a movement to another square, and it is the final square that the player finishes at on each roll that we are interested in. We shall make no distinction between "Just Visiting" and being sent to JAIL, and we shall also ignore the rule about requiring a double to "get out of jail", assuming that they pay to get out on their next turn.
By starting at GO and numbering the squares sequentially from 00 to 39 we can concatenate these two-digit numbers to produce strings that correspond with sets of squares.
Statistically it can be shown that the three most popular squares, in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO (3.09%) = Square 00. So these three most popular squares can be listed with the six-digit modal string: 102400.
If, instead of using two 6-sided dice, two 4-sided dice are used, find the six-digit modal string.
题目：
在游戏大富翁中，标准的游戏版如下：
玩家从 GO 开始，每次将两个六面骰子的得分相加来决定他下一步走向的格子（顺时针方向）。如果没有其他规则的话，我们可以预料每个格子被访问到的几率是相等的：2.5%。但是，如果落到格子 G2J（去监狱 JAIL），格子 CC（公益金），格子 CH（机会）的话，这个分布就会被改变。
除了 G2J 以及 CC 和 CH 中的一张牌能够让玩家直接进监狱（JAIL）以外，如果玩家连续三次掷骰子得到两个相同的数字，那么第三次玩家也将直接进监狱。
在游戏开始时，CC 和 CH 中的牌是乱序排放的。当玩家落到 CC 或 CH 时，他从相应的牌堆顶上拿一张牌，并执行完下面的指令后，将牌放回到牌堆的底部。每个牌堆中有 16 张牌，但是简单起见我们在此题目中只考虑涉及到移动的牌，任何不涉及到移动的牌将会被忽略，而且玩家仍然将处于 CC/CH 格子上。
[*]CC (2/16 张牌)：
[*]去到 GO
[*] 去到JAIL
[*]CH(10/16 张牌)：
[*]去到GO
[*] 去到JAIL
[*] 去到C1
[*] 去到E3
[*] 去到H2
[*] 去到R1
[*] 去到下一个 R (铁路公司)
[*] 去到下一个 R
[*] 去到下一个 U (工具公司)
[*] 回退3格
这个题目的核心问题是每个格子被访问到的可能性。也就是每次掷骰子之后落到某个格子的几率。因此，除了落到 G2J 的几率为零以外，落到 CH 的几率最小，因为落到 CH 后有 5/8 的几率会再次移动到其他格子。而我们感兴趣的是每次掷骰子之后最终落到的那个格子。我们对“只是访问”和被送到 JAIL不作区分，我们也同时忽略需要掷一个 double（两个相同的数字）才能走出 JAIL 的规则，只是假设玩家下一轮自动走出监狱。
从 GO 开始对格子编号（00 到 39），我们将这些两位数的数字相连接来得到与格子的集合相对应的字符串。
从统计上来说可以得到三个最受欢迎的格子按顺序是，JAIL（6.24%）= 10 号格子，E3（3.18%）= 24 号格子，GO（3.09%）= 00 号格子。所以这三个最受欢迎的格子可以用一个六位的字符串表示：102400。
如果我们用两个 4 面的骰子代替两个 6 面的骰子，找出代表三个最受欢迎格子的六位字符串。
这道题目的难点其实是在于建模，游戏模型建好以后，计算起来其实并没有很大难度。就是不断得通过随机数模拟玩家执行游戏，最后统计每格的情况。
import random
cc_map = {0:0, 1:10}
ch_map = {0:0, 1:10, 2:11, 3:24, 4:39, 5:5}
def draw_cc(position):
card_num = random.randint(0, 15)
if card_num in cc_map:
return cc_map
return position
def draw_ch(position):
card_num = random.randint(0, 15)
if card_num in ch_map:
return ch_map
if(card_num == 6 or card_num == 7):
if position < 5:
return 5
if position < 15:
return 15
if position < 25:
return 25
if position < 35:
return 35
return 5
if(card_num == 8):
if position < 12:
return 12
if position < 28:
return 28
return 12
if(card_num == 9):
if position == 36:
return draw_cc(33)
return position-3
return position
position = 0
rolls = 100000
square_count_map = {}
for i in xrange(40):
square_count_map = 0
doubles_count = 0
for i in xrange(rolls):
d1 = random.randint(1,4)
d2 = random.randint(1,4)
if(d1 == d2):
doubles_count += 1
else:
doubles_count = 0
if(doubles_count == 3):
position = 10
doubles_count = 0
else:
position += (d1 + d2)
position %= 40
if(position == 30):
position = 10
elif(position in ):
position = draw_cc(position)
elif(position in ):
position = draw_ch(position)
square_count_map+=1
for square in xrange(40):
print square, round(100 * square_count_map / float(rolls), 4)
print sorted(square_count_map, key=lambda square: square_count_map)[:-4:-1] import random
board = """GO A1 CC1 A2 T1 R1 B1 CH1 B2 B3 JAIL
C1 U1 C2 C3 R2 D1 CC2 D2 D3
FP E1 CH2 E2 E3 R3 F1 F2 U2 F3 G2J
G1 G2 CC3 G3 R4 CH3 H1 T2 H2""".split()
position = 0
count = * len(board)
double = 0
time = 999999
def goto(label):
global position
while board.find(label) != 0:
position += 1
position %= len(board)
def event():
global position
if board.find("G2J") == 0:
goto("JAIL")
elif board.find("CC") == 0:
ch = random.randint(1, 16)
if ch == 1:
goto("GO")
elif ch == 2:
goto("JAIL")
elif board.find("CH") == 0:
ch = random.randint(1, 16)
if ch == 1:
goto("GO")
elif ch == 2:
goto("JAIL")
elif ch == 3:
goto("C1")
elif ch == 4:
goto("E3")
elif ch == 5:
goto("H2")
elif ch == 6:
goto("R1")
elif ch == 7:
goto("R")
elif ch == 8:
goto("R")
elif ch == 9:
goto("U")
elif ch == 10:
position -= 3
position %= len(board)
event()
for i in range(time):
count += 1
d1 = random.randint(1, 6)
d2 = random.randint(1, 6)
if d1 == d2:
double += 1
if double == 3:
goto("JAIL")
double = 0
continue
else:
double = 0
position += d1 + d2
position %= len(board)
event()
result = sorted(map(lambda x, y: , count, range(len(count))))
print('{:02}{:02}{:02}'.format(result[-1], result[-2], result[-3]), sep='')
https://github.com/devinizz/project_euler/blob/master/page02/84.py
页:
[1]