桌游珠玑妙算(Mastermind)的游玩策略用数学工具如何分析?


这玩具叫珠玑妙算(Mastermind),玩法是——

  1. A君先选四个珠子 (图中的最右圆柱状物);
  2. B君列举一些珠子的组合 (图中中央的八行);
  3. A君再分别告诉B君每行颜色正确的、与颜色位置均正确的珠子的数量 (通过图中的白色与红色长条);
  4. B君旨在以最少的步骤猜出A君开始给的四个珠子的顺序与颜色


——总感觉这玩法跟信息论有关系。
例如噪声比、香农定理什么的,但我没足够的信息论功底去理明。
请求@死理性派 们帮忙!

推荐  (0) | 8人关注关注
2个答案
34 1

非乌龟代数拓扑硕士,C#程序员

2014-09-28 01:08

像文曲星上的猜数字,大概谷歌了一下,有些过往的分析:http://www.cnblogs.com/rosting/archive/2011/11/15/2249590.html——写到这里我实在不爽于只知道“文曲星的猜数字”,终于靠一点运气搜出了这个特别成熟的游戏的学名:Bulls and Cows(中文还真就叫猜数字……)。维基百科的链接里提到1970年J. M.Grochow写了个程序“moo”来解它,而原版猜数字游戏可以在七步之内猜出(维基里有两篇相关文章)。

原版Bulls and Cows游戏可以说算是解决了,而珠玑妙算与原版不同的地方在于
1.不清楚这里要求八次猜测是一次给出,还是B逐步猜测A逐步解答。如果要求一次给出,则无法通过之前的猜测优化后续猜测,难度提高了,可以设想的是需要猜测的次数会增多。(不过这样一来八次以后好像也没法再猜了?)
2.存在博弈因素了,给出组合的A可以针对B的惯常算法故意给出最差情况。虽然目前的算法最坏情况是七次猜出,不过对于随机数字的平均情况肯定是小于七次的,有时四次猜出,有时可能一次就碰巧猜出了。那么是否存在一种方法,A能够针对B的惯常做法,给出最差情况,让B每一次都耗满七次猜测,或者总要猜个五六次。而B也见招拆招,随时调整自己的猜测方法,不让A达到这个目的。

目前想到这么多,抛砖引玉吧。
暂时摘抄一段上面提到的文章做个结尾:


在資訊科學和通訊科技中,有一門叫做「資訊理論」
(Information Theory)的課;另外在人工智慧和決策科
學中還有一個叫做「決策理論」(Decision Theory)的研
究主題。這些和機率理論密切相關的專門知識,都可以
提供我們相關的知識,來計算這樣的相對的分數。
31 0

傅里叶变黄油猫软件工程师,应用数学专业

2014-09-28 10:00

游戏介绍见 @非乌龟 的回答。我这里假设游戏规则同文曲星上经典的“猜数字”,数字可重复(困难)模式。

==基本思路==

我基本和楼主想到一块儿去了,每一轮应该猜一组可获得信息量期望值最大的组合。

参考维基百科-熵

有种叫20 Questions的游戏,就是:
主持:一个国家名
A:这个国家在亚洲
B:不是
A:这个国家在非洲或者大洋洲
B:不是
A:这个国家在美洲
B:不是
A:这个国家在西欧
B:是
A:这个国家是法国或者德国
B:不是
A:这个国家是西班牙
B:正确

这种游戏的最佳策略是在前几次猜测尽可能排除多的可能性,而不是一开始就猜某个谜底,从信息学的角度看,是问一个信息量期望值最大的问题。

信息量期望值=P(yes)*log(1/P(yes)) + P(no)*log(1/P(no))
每问一次,让信息量期望值最大化。当答“是”和“否”的概率都是0.5时,这个值最大。

而楼主的问题,我想最佳的策略和上面的游戏类似,只不过是个加强版,谜底空间大(10000),每猜一次可能的输出多,因此最好让计算机做。假设所有可能的谜底集合为,对于剩余可能的谜底集合,给定任意一个猜测表示猜b时可获得信息量期望值,那么每猜一次应该让最大化。

==科普:信息量期望值==

这部分是科普,多数学概念,给对信息论不熟悉的同学参考。

我们认为一个随机事件发生后得到了一定的信息量,这个量和其发生概率有关,概率越低,信息量越大。例如我买了彩票,如果没中那没什么好说的,因为概率大、信息量小,但如果中了,那可不得了,信息量非常大,赶紧告诉所有人。

随机事件x发生概率为P(x),那发生后获得信息log(1/P(x)),这里log可以用2为底,计算结果单位是bit。例如抛个硬币,假设正反两面的发生概率都是1/2,那无论抛出什么,得到信息量都是1bit。

又用上面20 Questions来举例。世界上大约有200个国家,假设谜底是任意一个国家的概率都相同,那一开始我就猜具体某个国家,有1/200的概率可以一猜即中,获得了log(200)的巨量信息。但绝大部分时候(199/200)我都猜不中,获得了log(200/199)的信息量,所以我可以获得信息量的期望值是:

但如果我一开始猜亚洲,亚洲有48国家,那可以获得期望信息量是:

假如我猜“亚洲或者欧洲”,国家数接近一半,那信息量期望进一步增加到接近1bit。

回到楼主的问题。我猜一组数(颜色),可以获得诸如1A2B、0A3B这样的输出结果,每猜一轮都可以利用输出结果缩小谜底可能范围。例如已知可能的组合是[1,2,3,4] [1,2,3,5] [1,2,3,6],那我猜[1,2,3,4],那有1/3的概率获得4A0B结果,有2/3的概率获得3A1B结果,期望信息量大约是0.918bit。但如果我猜[1,2,5,6],那三组可能会输出三种不同的结果:2A0B 2A1B 3A0B,各1/3的概率,信息量期望达1.585bit,马上获得了正确结果(尽管按游戏规则还要多猜一轮)。

将问题扩大到一般情况,假设谜底每位数字可能是0~9,4个数字组成一个谜底,数字可以重复,那刚开始有10000种可能的组合,之后每猜一次都缩小搜索范围。每次猜测,我都遍历10000个组合,分别计算该组合可获得信息量期望值,并选取最大的一个作这一轮的尝试。

==实验==

实验结果,这种策略效果不错,一般都在4到6次尝试后获得正确结果:

1 Try: [0 1 2 3] - 0 A 1 B Remains: 3048
2 Try: [2 6 9 4] - 0 A 1 B Remains: 886
3 Try: [4 8 0 5] - 0 A 1 B Remains: 218
4 Try: [7 3 8 9] - 0 A 0 B Remains: 16
5 Try: [5 1 1 6] - 0 A 3 B Remains: 2
6 Try: [5 5 0 0] - 1 A 0 B Remains: 1
Got it: [6 5 6 1]

1 Try: [0 1 2 3] - 0 A 0 B Remains: 1296
2 Try: [9 8 5 4] - 1 A 2 B Remains: 132
3 Try: [8 6 8 4] - 0 A 2 B Remains: 30
4 Try: [7 4 5 8] - 2 A 1 B Remains: 2
5 Try: [4 0 0 0] - 0 A 1 B Remains: 1
Got it: [9 4 7 8]

1 Try: [0 1 2 3] - 1 A 1 B Remains: 1260
2 Try: [6 4 2 0] - 1 A 1 B Remains: 174
3 Try: [5 3 2 6] - 0 A 0 B Remains: 20
4 Try: [9 4 1 7] - 0 A 3 B Remains: 3
5 Try: [7 0 0 0] - 1 A 0 B Remains: 1
Got it: [4 1 9 0]

1 Try: [0 1 2 3] - 0 A 2 B Remains: 1896
2 Try: [5 0 9 2] - 0 A 3 B Remains: 80
3 Try: [6 2 0 7] - 1 A 0 B Remains: 11
4 Try: [9 1 2 5] - 1 A 3 B Remains: 1
Got it: [9 2 5 1]

Remains表示一步猜测后剩余的可能总数,可以看到算法如何一轮一轮缩小搜索范围,也发现这种方法和人常用方法差别很大,一般人都会不断尝试更准确(A和B更大)的谜底,从而越来越接近结果,而算法给出的策略看起来毫无规律可言,像一个不懂的人乱猜,却在极少次尝试后精确获得正确答案。

用golang写的,效率比较低,一次要跑5-20秒。代码在:
https://github.com/EthanLauAL/BullsAndCows

由于计算量太大,人玩无法用这种方法。

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区