查看“︁彭尼的游戏”︁的源代码

'''彭尼的游戏（Penney's game）'''由[[沃尔特·彭尼]]（{{link-en|Walter Penney}}）提出，是一个两个玩家之间生成用“正面”和“反面”为代称产生[[二进制]][[数列]]的游戏。玩家A报出至少包含3个项、每项只能是正面或反面的序列，然后展示给玩家B；玩家B则给出等长的正面反面序列。随后, 投掷一面均匀的[[硬币]]，观察正反，直至投掷出一段序列刚好和某个玩家的序列吻合，则该名玩家获胜。

将序列中每个正面或者反面的判断称为[[比特]]（bit），使用长度为3比特的序列，玩家B相对玩家A有优势。这是因为这个游戏是一个[[非传递博弈]]，所以无论如何选定第一个序列，总会有一个序列有更大的获胜概率。

==长度为3bit的游戏分析==
长度为3比特的游戏中,第二名玩家可以通过以下途径最大化其胜算（odds）：

（H表示正面朝上，T表示反面朝上）

{| class="wikitable" style="text-align: center;"
|-
! 1号玩家 !! 2号玩家 !!2号玩家胜算
|-
|<u>H'''H'''</u>H || '''T'''<u>HH</u> || 7：1
|-
|<u>H'''H'''</u>T || '''T'''<u>HH</u> || 3：1
|-
|<u>H'''T'''</u>H || '''H'''<u>HT</u> || 2：1
|-
|<u>H'''T'''</u>T || '''H'''<u>HT</u> || 2：1
|-
|<u>T'''H'''</u>H || '''T'''<u>TH</u> || 2：1
|-
|<u>T'''H'''</u>T || '''T'''<u>TH</u> || 2：1
|-
|<u>T'''T'''</u>H || '''H'''<u>TT</u> || 3：1
|-
|<u>T'''T'''</u>T || '''H'''<u>TT</u> || 7：1
|}

简单的来说，对于2号玩家可以记下如下的序列作为获胜的技巧或者是讨喜的技巧（bar trick）：第一个比特与1号玩家的第二个比特相反，第二个比特与1号玩家的第一个比特相同，第三个比特与1号玩家的第二个比特相同。
:如果1号玩家选择了<big>“'''1-2-3'''”</big>为顺序编号的序列，每个编号代表一个比特(正面/反面)，
:那么2号玩家则应该选择<big>'''：(与2相反)-1-2'''</big> <ref name=":0">[https://www.youtube.com/watch?v=IMsa-qBlPIE Predicting a coin toss] {{Wayback|url=https://www.youtube.com/watch?v=IMsa-qBlPIE |date=20210324115928 }} by 'Scam School' (on [[YouTube]])</ref>

这一结果有一个直观的解释：依照这种方法，当1号玩家猜测的前两比特刚好对上时，2号玩家的后两比特也对上，而1号玩家仍需要再猜测一轮才知晓是否胜利，直觉上而言，认为2号玩家更可能先猜全序列而成为赢家。<ref name=":0" />
==3bit以上情形分析==
在比特不小于4时1号玩家的优化策略由J.A. Csirik提出的(见''参考资料'')。这一策略即是选择HTTTT.....TTTHH(<math>k-3</math> T's)这样的序列。在此情形下，2号玩家的最大胜率为<math> (2^{k-1}+1):(2^{k-2}+1) </math>。

==带扑克牌的变种==
其中一种变种使用一套普通的扑克牌，被称为Humble-Nishiyama随机性游戏。该游戏遵从与彭尼的游戏同样的格式，只不过把猜正反改成猜红牌黑牌。<ref>[http://plus.maths.org/content/os/issue55/features/nishiyama/index Winning Odds] {{Wayback|url=http://plus.maths.org/content/os/issue55/features/nishiyama/index |date=20210324115636 }} by Yutaka Nishiyama and Steve Humble</ref><ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.177.1176 Humble-Nishiyama Randomness Game - A New Variation on Penney’s Coin Game] {{Wayback|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.177.1176 |date=20131215040301 }} on CiteSeer</ref>

游戏规则如下：

:游戏开始时，各玩家决定在游戏中使用的对于连续三张卡片的颜色猜测顺序。每次抽出一张卡片，并按顺序放成一线，直至被选的三联顺序出现。选中这一顺序的玩家拿走最后对上的三张牌, 称为拿到1个“trick”。游戏用余下牌继续，直至玩家不断地拿到“trick”所有牌被拿完为止。拿了最多“trick”的玩家即为赢家。

这一游戏通常会包含7个“trick”。基于扑克牌的游戏非常接近于原先游戏的重复，2号玩家的优势被极大地放大。但是概率有略微不同，因为投硬币得到的两个结果是[[独立 (概率论)|独立的]]，而取出红牌于黑牌的概率取决于之前的抽牌。记红为R，黑为B，正面为H，反面为T，可以注意到HHT对比HTH和HTT的概率比是2：1，但BBR对比BRB和BRR的概率比各不相同。

以下为电脑模拟对每种策略的结果的估算概率：<ref>Results are broadly in line with those in Steve Humble and Yutaka Nishiyama, Humble-Nishiyama Randomness Game ''Mathematics Today'' August 2010 p&nbsp;143 -
A new variation on Penney’s Coin Game [http://www.ima.org.uk/_db/_documents/Humble%20Nishiyama%20Randomness%20Game%20copy.pdf] {{Wayback|url=http://www.ima.org.uk/_db/_documents/Humble%20Nishiyama%20Randomness%20Game%20copy.pdf |date=20150924033735 }}</ref>

{| class="wikitable" style="text-align: center;"

! 1号玩家 !! 2号玩家 !!1号玩家胜算!!2号玩家胜算!!平局概率
|-
|<u>B'''B'''</u>B || '''R'''<u>BB</u> || 0.11% || 99.49% || 0.40%
|-
|<u>B'''B'''</u>R || '''R'''<u>BB</u> || 2.62% || 93.54% || 3.84%
|-
|<u>B'''R'''</u>B || '''B'''<u>BR</u> || 11.61% || 80.11% || 8.28%
|-
|<u>B'''R'''</u>R || '''B'''<u>BR</u> || 5.18% || 88.29% || 6.53%
|-
|<u>R'''B'''</u>B || '''R'''<u>RB</u> || 5.18% || 88.29% || 6.53%
|-
|<u>R'''B'''</u>R || '''R'''<u>RB</u> || 11.61% || 80.11% || 8.28%
|-
|<u>R'''R'''</u>B || '''B'''<u>RR</u> || 2.62% || 93.54% || 3.84%
|-
|<u>R'''R'''</u>R || '''B'''<u>RR</u> || 0.11% || 99.49% || 0.40%
|}

如果游戏在多于1个trick时结束，平局概率微乎其微。2号玩家的胜率如下表所示：

{| class="wikitable" style="text-align: center;"
|-
! 1号玩家 !! 2号玩家 !!2号玩家胜算

|-
|<u>B'''B'''</u>B || '''R'''<u>BB</u> || 7.50：1
|-
|<u>B'''B'''</u>R || '''R'''<u>BB</u> || 3.08：1
|-
|<u>B'''R'''</u>B || '''B'''<u>BR</u> || 1.99：1
|-
|<u>B'''R'''</u>R || '''B'''<u>BR</u> || 2.04：1
|-
|<u>R'''B'''</u>B || '''R'''<u>RB</u> || 2.04：1
|-
|<u>R'''B'''</u>R || '''R'''<u>RB</u> || 1.99：1
|-
|<u>R'''R'''</u>B || '''B'''<u>RR</u> || 3.08：1
|-
|<u>R'''R'''</u>R || '''B'''<u>RR</u> || 7.50：1
|}

==带轮盘的变体==

Robert W. Vallin以及后来他和Aaron M. Montgomery一起发表了有关赌便士问题的研究结果。他们把这一游戏改编为（美式）[[轮盘]]，玩家们通过选择红色或黑色，而不是硬币的正面反面，来进行游戏。这种情况下，球落在红色与黑色区域的概率各为9/19，而球落在绿色区域的概率为1/19。绿色区域有很多解读方式：

:(1)作为状况外卡牌，既可以当黑也可以当红； 
:(2)意即本轮无效须重来，或者游戏直接结束；
:(3)作为一种非红非黑的颜色参与到序列中。 

其研究结果计算了胜算与结束游戏所需要的回合数。<ref>{{cite book|author1=Jennifer Beineke|author2=Jason Rosenhouse|coauthors=Robert W. Vallin|title=The Mathematics of Various Entertaining Subjects: Research in Games, Graphs, Counting, and Complexity, Volume 2|date=2017-09-05|publisher=Princeton University Press|location=Princeton|isbn=9780691171920}}</ref>

==参见==
*[[非传递博弈]]

==参考资料==
{{Reflist}}
* Walter Penney, Journal of Recreational Mathematics, October 1969, p.&nbsp;241.
* [[Martin Gardner]], "Time Travel and Other Mathematical Bewilderments", W. H. Freeman, 1988.
* [[L.J. Guibas]] and [[A.M. Odlyzko]], "String Overlaps, Pattern Matching, and Nontransitive Games",  Journal of Combinatorial Theory, Series A.  Volume 30, Issue 2, (1981), pp&nbsp;183–208.
* [[Elwyn R. Berlekamp]], [[John H. Conway]] and [[Richard K. Guy]], "Winning Ways for your Mathematical Plays", 2nd Edition, Volume 4, AK Peters (2004), p.&nbsp;885.
* S. Humble & Y. Nishiyama, "Humble-Nishiyama Randomness Game - A New Variation on Penney's Coin Game", IMA Mathematics Today. Vol 46, No. 4, August 2010, pp&nbsp;194–195.
* Steve Humble & [[Yutaka Nishiyama]], [http://plus.maths.org/issue55/features/nishiyama/index.html "Winning Odds"] {{Wayback|url=http://plus.maths.org/issue55/features/nishiyama/index.html |date=20210324115653 }}, Plus Magazine, Issue 55, June 2010.
* [[Yutaka Nishiyama]], [http://www.ijpam.eu/contents/2010-59-3/10/10.pdf Pattern Matching Probabilities and Paradoxes as a New Variation on Penney’s Coin Game] {{Wayback|url=http://www.ijpam.eu/contents/2010-59-3/10/10.pdf |date=20210706140007 }}, International Journal of Pure and Applied Mathematics, Vol.59, No.3, 2010, 357-366.
* [[Ed Pegg, Jr.]], [http://blog.wolfram.com/2010/11/30/how-to-win-at-coin-flipping/ "How to Win at Coin Flipping"] {{Wayback|url=http://blog.wolfram.com/2010/11/30/how-to-win-at-coin-flipping/ |date=20101204034742 }}, [http://blog.wolfram.com/ Wolfram Blog] {{Wayback|url=http://blog.wolfram.com/ |date=20110721202358 }}, 30 November 2010.
* [[J.A. Csirik]], "Optimal strategy for the first player in the Penney ante game", [[Combinatorics, Probability and Computing]], Volume 1, Issue 4 (1992), pp 311–321.
*[[Robert W. Vallin]] “A sequence game on a roulette wheel,” The Mathematics of Very Entertaining Subjects: Research in Recreational Math, Volume II, Princeton University Press, (to be published in 2017)
* James Brofos, "A Markov Chain Analysis of a Pattern Matching Coin Game." [https://arxiv.org/abs/1406.2212 arXiv:1406.2212] {{Wayback|url=https://arxiv.org/abs/1406.2212 |date=20180125015739 }} (2014).

{{博弈论}}
[[Category:博弈论]]