骰子游戏

东邪

puzzleup竞赛第11题
http://www.puzzleup.com/2012/puzzle/?252

你和朋友正在玩一个投掷两个标准骰子的游戏。如果连续两次出现7你就获胜；如果连续三次出现递增结果则你的朋友获胜。任意一方胜出则游戏终止。你获胜的概率是多少？答案以简化分数表示，比如12/23

例如:如果 10,4,6,6,7,7 你赢，如果 7,3,7,9 你的朋友赢。

编程可以得到近似值，如何得到用分数表示的精确值？

mathe

构造一个不超过36阶的状态转移图即可。
其中每个状态包含两个数
(L,s)
其中1<=L<=12,表示最后一次的数值。
而s分别表示1,2,3,4
其中s=1,表示倒数第二次的数字不存在（也就是第一次投掷）或不小于最后一次的数字，而且两个不同时为1.
其中s=2,表示倒数第二次的数字存在并且小于最后一次的数字，而且倒数第三次的不存在或不小于倒数第二次的。
同样,s=3表示最后三个单调增
s=4仅用于最后两个都是7的情况。
然后构造出转移概率阵，就可以算出双方赢的概率了

zgg___

106460465616/556534555787=0.191292

zgg___

呵呵，如果有两个游戏：
1、你要连续两次2点，庄家（你的朋友）要连续三次递增；
2、你要连续两次12点，庄家（你的朋友）要连续三次递增；
那么，哪个游戏你取胜的机会大呢？

zgg___

lz的问题，如2L mathe说，是可以比较系统的解决的，我这里罗嗦一下吧，呵呵。

1. fn[ss_,b_]:=Module[{s=ss,bk},
   
2. If[s=="1Win"||s=="2Lost",Return[s]];
   
3. If[s=="0Start",s={100,0,0}];
   
4. bk=Apply[Plus,b];
   
5. If[bk==7,s[[2]]++,s[[2]]=0];
   
6. If[s[[1]]<bk,s[[3]]++,s[[3]]=0];
   
7. s[[1]]=bk;
   
8. If[s[[2]]>=2,s="1Win",If[s[[3]]>=2,s="2Lost"]];
   
9. s];
   
10. fn[{12,0,0},{1,1}]
    
11. fn["0Start",{2,3}]
    
12. fn["2Lost",{4,5}]
    
13. fn[{200,100,100},{6,6}]

复制代码

第一步设想会出现的状态，然后定义一个状态转移函数fn，这个fn的定义是有随意性的，我这里的情况是：ss为{最后一次的点数，已有几个7，已有几个小于号}，b为两个骨子的点数。

1. ss = {"0Start"}
   
2. bs = Flatten[Table[{i, j}, {i, 6}, {j, 6}], 1]

复制代码

第二步列出了ss的初始状态，和b的所有可能。

1. ss = Union[ss, Flatten[Outer[fn, ss, bs, 1], 1]];
   
2. ss // Length
   
3. ss

复制代码

第三步ss将列出所有可能的状态，我们要不停的循环它，直到ss不变，这时ss有24个元素。这24个状态就是2L提到的状态。

1. r=Map[First[#]->Last[#]&,Transpose[{ss,Range[Length[ss]]}]]
   
2. gs=Flatten[Outer[{#1,fn[#1,#2]}&,ss,bs,1],1];sn=Length[ss];
   
3. set=Map[{First[#],Length[#]/36}&,Split[Sort[gs]]]/.r;
   
4. mm=Table[0,{sn},{sn}];Do[mm[[set[[i,1,1]],set[[i,1,2]]]]=set[[i,2]],{i,Length[set]}];

复制代码

接下来的第四步，就求出那个“转移概率阵”mm。r将24个状态编了号。

1. c = Table[0, {sn}]; c[[1]] = 1; m = Transpose[mm];
   
2. MatrixPower[N[m], 10^8].c

复制代码

然后是第四一撇步，呵呵，可以看到第二项0.191292就是答案了（留着验算用吧）。而如何算出这项呢？可以用本征值，大家可以就此深入研究一下，呵呵。也可以用下面第五步的方法。

1. var=Table[Subscript[x,i],{i,sn}];
   
2. qs=Map[First[#]==Last[#]&,Transpose[{mm.var,var}]];
   
3. qs[[2]]=(Subscript[x,2]==1);qs[[3]]=(Subscript[x,3]==0);
   
4. ans=Subscript[x,1]/.First[Solve[qs,var]]
   
5. ans//N

复制代码

第五步，解方程。x1到x24表示位于对应装态时取胜的几率，每个状态的x等于它后面所有状态的x的加权平均，另外有：x2=1和x3=0，求出x1就ok了。

东邪

106460465616/556534555787=0.191292
zgg___ 发表于 2013-1-29 09:14

高手啊

东邪

方法差不多，就是最后一步不会，求不出精确值。

puzzleup向来不公布答案，不知道这个结果是不是puzzleup的答案。
但这道题似乎有很多人做对，我不相信！

geslon

7# 东邪
也不是很多人作对了，17.9%正确率。