拍手游戏胜负概率_2014

痛定思痛。 2021-12-16 02:31 105阅读 0赞

2014年写的东西，使用马尔可夫链求简化的拍手游戏的胜负概率。

我的设想是人机对玩时程序可以预测人的动作概率来最大化胜率。

PS:其他问题：

游戏界面如何模拟剪刀石头布的场景，可以让人们相信对方没有作弊或非常容易发现对方作弊？

[https://www.zhihu.com/question/32153018][https_www.zhihu.com_question_32153018]

原文：[http://blog.csdn.net/u012408605/article/details/24137629][http_blog.csdn.net_u012408605_article_details_24137629]

我说的拍手游戏是指这个小时候的游戏：AB用手势表示装弹、防卫和开枪，每拍两次手给出手势，胜出的条件是开枪时对方在装弹或者先装满五颗子弹。用（＋）（＝）（―）表示装弹、防卫、开枪，有（―）＜（＝）＜（＋）＜（―），类似于剪刀石头布。我用程序试验在很简单的条件下游戏的胜负情况。

网上介绍的规则要复杂得多，还有人在上大学前用 C\# 实现过局域网对战版本。程序似乎难以模拟这类猜拳游戏的同步场景。这个游戏也可以实现为其他场景。比如，房间里有钱币，AB每一次或者不进入房间，或者进入房间偷走一个钱币，或者进入房间放回一个钱币。先偷走M个钱币的胜出，或者进入房间放回钱币而（看见）对方偷走钱币时胜出。  
  
假设：

1.  双方设定在当前双方装弹数目为ab时，自己出某个手势的概率，保存在TABLE\_A/B。
2.  TABLE\_B中（＋）（＝）（－）的概率都设为p、r、q。例外：b＝0时，不允许（－），q≡0，r≡1－p；a＝0时，没有必要（＝），r≡0，q≡1－p。
3.  TABLE\_A通过置换TABLE\_B对应单元中（＋）（＝）（－）的概率得到。我希望A胜的概率PA总大于1/2。

在b＝0或a＝0时，合理的置换只有一个，如下图所示。但a＋b＝0时，双方P(+)≡1。

按照（―）＜（＝）＜（＋）＜（―），a＞0，b＞0时的置换如下图所示。

![20140419211907640][]![20140419211927265][]

下边就是看看在p、r（q＝1―p―r）和最大装弹数目M的不同取值下，游戏的胜负情况。

将游戏看成从原点出发的随机游动，ab就是状态（a，b），a，b＝0，1，……，M；Δa，Δb＝―1，0，1；a＝0时，Δa≠―1，Δb≠0，ab对调亦然。添加状态END\_A、END\_B，表示A胜、B胜。规定当Δa＝1，Δb＝―1或者a＝M，b＜M时转移到状态END\_A，ab对调亦然；到达END\_A或END\_B后不再转移至其他状态。因此坐标上的点每次可向周围最多6个点移动、或者不动、或者转移到END\_A或END\_B。

为了方便计算，合并多余的状态。（M，b＜M）/（a＜M，M）合并至END\_A/END\_B。另外，（M―1，0）/（0，M―1）一定转移到END\_A/END\_B；（M，M）一定转移到（0，0），而（0，0）一定转移到（1，1）。合并后，游动实际上从（1，1）出发；（M―1，M―1）在Δa＝1，Δb＝1时转移到（1，1）；状态总数N为：（M＋1―1）^2＋2―3＝M^2―1。如图所示，取M＝5。

AB的手势按当前双方装弹数目对应的设定概率给出，因此这N个状态组成的游动是一个齐次马尔可夫链。由TABLE\_A/B可得到转移矩阵。END\_A、END\_B是（非零）常返状态；其他状态是非常返状态。系统最终一定被吸收进END\_A或者END\_B。吸收概率和平均吸收时间的解法可参见《概率、随机变量与随机过程》15.5节非常返状态和吸收概率。  
用转移矩阵的特征值计算好像也是可以的。用MATLAB的符号运算功能可以得出PA的表达式，很长。将数值代入最终的表达式计算比代入转移矩阵计算的效率高，但是计算PA很费时间，不如直接代入转移矩阵。  
先考虑a＞0，b＞0时出一次手势的情况。这三种情况对A有利：胜；A（＋）B（＝）；A（＝）B（―）。假设这三项的权重一样，则取它们的和为SA＝p^2＋r^2＋q^2，则SB＝qr＋pq＋pr。显然SA≥SB，似乎总是A占有比较大的优势。如果只取前两项，p^2＋r^2＞1/4时，SA＞SB；p^2＋r^2＜2/9时，SA＜SB。如果只取第一项，则SA＝p^2，有PA＞SA＞1/2，若p^2＞1/2；SB＝qr≤1/4。不过这样一次简单的比较意义不大。除END\_A/B外的状态总数为N―2＝M^2―3，因此M的最小值应取3。如果M＝2，则只有一个初始状态（1，1），取三项之和的SA、SB，有PA/PB＝SA/SB≥1。  
以步进值0.025取0~1之间的41个点作为p、r的取值，取M＝3，4，5，6，7，15，画出p＋r≤1时，PA的变化情况，PA有NPA＝861个点。M＝3时PA如下图所示；M取其他值时的曲面形状相似，见等高线图。可见，PA并非总是大于1/2。M越大，PA最小值越小，PA＜1/2的范围越大，见下表。  
![20140419212020125][]![20140419212041734][]  
M min(PA) p r q P(PA<1/2)  
3 0.4958 0.225 0.4 0.375 9/NPA=0.0105  
4 0.4401 0.15 0.5 0.35 119/NPA=0.1382  
5 0.3844 0.125 0.55 0.325 173/NPA=0.2009  
6 0.3409 0.1 0.6 0.3 198/NPA=0.2300  
7 0.3063 0.1 0.625 0.275 219/NPA=0.2544  
15 0.1672 0.075 0.725 0.2 278/NPA=0.3229  
  
最小值出现在p＜1/3，q＝1/3附近，取一项之和的SA、SB，SA＝p^2，SB＝qr，有SA＜SB。直接作图看看SA―SB＜0和PA＜1/2的分布，如下图所示。除边缘几个格子外，可以认为SA＜SB是PA＜1/2（M≤15）的充分条件。  
也就是p较小，而q约为1/3时，采用上述置换对A是不利的。此时B倾向于（―）和（＝），而A随着倾向于（＝）和（＋），企图达到最大装弹数目M来取胜，但同时中枪的可能性比较大，M越大，越难以达到，P(PA＜1/2)越大。  
![20140419212237281][]![20140419212254843][]

如果不置换，结果如上图所示，取M＝34567。P(PA＜1/2)≤202/NPA＝0.23，最小值都出现在p≥0.4处，且min(PA)≥0.4966。不置换时，A应该只在b＞a＝0时不得不占劣势，我本以为P(PA＜1/2)＝0。

如果反过来，取经过上述置换得到TABLE\_B的TABLE作为TABLE\_A，能不能使A起死回生？这样置换后，相当于AB、pq位置互换，三项之和的SA＝qr＋pq＋pr，SB＝p^2＋r^2＋q^2，原来的PA＜1/2，p＜1/3对应于置换后的PA＝1―PB＞1/2，p＋r＝1－q＞2/3。取M＝5，看看和其他三个置换的结果。其他置换是左右对称的。这四个置换的P(PA＜1/2) 都大于原来的P(PA＜1/2)＝0.2009。

![20140419212341031][]

![20140419212542265][]![20140419212606281][]

![20140419212642250][]![20140419212702453][]

P1的P(PA＜1/2) 最大，P(PA＜1/2)＞1/2，max(PA)＜1。P2的P(PA＜1/2) 最小，且刚好可以作为原来PA＜1/2时的替换，但M继续增大时，二者PA＜1/2的区域有重合。直接从P2来看，SA－SB＝p（r―q），r＜q时，也就是r＜1/2―p/2时，对B是有利的。但结果表明在p＝0.25附近有另一条分界线。P3直观上也是在p＞r时对B有利；另一条分界线在q＝0.15附近。对于P4，SA―SB＝p^2―q^2＝(1―r)(2p＋r―1)，r＜1―2p 时SA＜SB，而实际上主要在r＜0.5时才有PA＜1/2。

所以，如果随机地选择一组pr，按照（―）＜（＝）＜（＋）＜（―）得到的置换方式是最合理的，而相反的置换方式是最不合理的。

转载于:https://www.cnblogs.com/albumcover/p/7281000.html

[https_www.zhihu.com_question_32153018]: https://www.zhihu.com/question/32153018
[http_blog.csdn.net_u012408605_article_details_24137629]: http://blog.csdn.net/u012408605/article/details/24137629
[20140419211907640]: https://img-blog.csdn.net/20140419211907640
[20140419211927265]: /images/20211214/d8f0ace00ea144a6ae672a5de115acae.png
[20140419212020125]: https://img-blog.csdn.net/20140419212020125
[20140419212041734]: /images/20211214/52f1748e32c04fe5915bbc72870a856e.png
[20140419212237281]: https://img-blog.csdn.net/20140419212237281
[20140419212254843]: /images/20211214/ef05aacdd64842538886da37a5a112ee.png
[20140419212341031]: /images/20211214/65236170ecb0439e890c3e523c6a8716.png
[20140419212542265]: https://img-blog.csdn.net/20140419212542265
[20140419212606281]: /images/20211214/d349b02286f244af911b722af7dc7c8c.png
[20140419212642250]: https://img-blog.csdn.net/20140419212642250
[20140419212702453]: /images/20211214/810226aa9a8d43328eff36babc43cde4.png