0084 强手棋
* * * *
拉格朗日计划
* * * *
强手棋

强手棋的标准棋盘如下,共40格:



玩家从左上角的起点GO出发,掷两个六面的骰子并将其点数和作为本轮前进的步数。可以想像,如果没有其它规则,那么经过充分多的轮数后,落在每一格上的频率大致相当。

但是,由于G2J(入狱)、CC(宝箱卡)和CH(机会卡)的存在,访问每一格的频次并不相同。

能影响玩家位置的规则如下:

1, 若前进后落在左下角的G2J上,则直接移动到右上角的JAIl。

2, 若玩家连续三次都掷出两个相同的点数,则在第三次时直接入狱(即直接移动到右上角的Jail)。

3, 若玩家落在CC(宝箱卡)或CH(机会卡)格,则抽取对应卡堆最上方的卡片,按卡片指示行动后将卡片放入对应卡堆的最下方。游戏开始时,应将两个卡堆分别洗牌。

CC(宝箱卡)共16张,其中能影响玩家的卡有2张:

(1)回到起点GO

(2)进入监狱JAIL

CH(机会卡)也有16张,其中能影响玩家的卡有10张

(1)回到起点GO

(2)进入监狱JAIL

(3)移动到C1

(4)移动到E3

(5)移动到H2

(6)移动到R1

(7)移动到下一个R(铁路公司)

(8)移动到下一个R

(9)移动到下一个U(公共设施)

(10)后退三步

在标准规则中玩家进入监狱后还需要掷出两个相同的点数才能出狱,此处我们无视这一规则,并假定玩家进入监狱后下一轮也仍能从监狱出发行动。

从起点GO开始,将棋盘上的格子按顺时针方向依次标记为00到39。

显然,每轮结束后,除了停在G2J上的可能性为0以外,停在CH格的可能性最小,因为在5/8的情况下玩家会被移动到另一格。

而三个最有可能停留的方格分别是JAIL(方格10),E3(方格24),GO(方格00),在充分多的轮数后停在这三者上的频次分别接近6.24%, 3.18%, 3.09%,这三个方格可以用一个六位数字串102400来表示。

现在假设我们不用两个六面骰,而是用两个四面骰来游戏,求最有可能停留的三个方格所组成的六位数字串。

本题难度:



解答

本题英文原题的描述并不清晰,题面中多次提到“概率”,但并未指明对应的概率空间,以上的译文按题意将其改为了频率的极限,即考察下面的值最大的三个格子X $$\lim_{n\to\infty}\frac{\text{n轮游戏中玩家落在X格上的次数}}{n}.$$ 按规则模拟充分多的轮数(此处模拟100万轮)即可,注意在CH3抽中倒退3格时会落到CC3,此时还会触发一次宝箱卡抽卡。

结果是$101524$。

import random

communityChest=[0,10]+["X"]*14
chanceChest=[0,10,11,24,39,5,"R","R","U",-3]+["X"]*6

communityGrid=[2,17,33]
chanceGrid=[7,22,36]

target=1000000
d=[1,2,3,4]

q=0
t=0
occ=[0 for i in range(40)]
random.shuffle(communityChest)
random.shuffle(chanceChest)
communityCursor=0
chanceCursor=0
for i in range(target):
    a=random.choice(d)
    b=random.choice(d)
    if a==b:
        t=t+1
    else:
        t=0
    if t>=3:
        q=10
        t=0
    else:
        q=(q+a+b)%40
        if q==30:
            q=10
        if q in chanceGrid:
            if chanceChest[chanceCursor]!="X":
                if chanceChest[chanceCursor]=="R":
                    if q>=35 or q < 5:
                        q=5
                    elif q>=5 and q < 15:
                        q=15
                    elif q>=15 and q < 25:
                        q=25
                    elif q>=25 and q < 35:
                        q=35
                elif chanceChest[chanceCursor]=="U":
                    if q>=12 or q < 28:
                        q=28
                    else:
                        q=12
                elif chanceChest[chanceCursor] < 0:
                    q=q-3
                else:
                    q=chanceChest[chanceCursor]
            chanceCursor=(chanceCursor+1)%16
        if q in communityGrid:
            if communityChest[communityCursor]!="X":
                q=communityChest[communityCursor]
            communityCursor=(communityCursor+1)%16
    occ[q]=occ[q]+1

print sorted([[occ[i],i]for i in range(40)],reverse=True)[:3]