MasterMind(bulls and cows)

By Von Neumann

Mastermind很经典的一个小游戏,有各种不同的版本,这边就介绍一个猜数字的版本。
在这个游戏中有两个角色,一个是code maker,另外一个是code breaker。游戏开始时,code maker提供一个secret code(4 non-repeated digitals),然后breaker就开始猜,code maker会对code breaker的guess进行评估,并给出相应的feedback:xAyB,x代表位置和数值都猜对的数量,y代表数值猜对但位置猜错的数量。假设secret是’2345′,guess是’3275’,对应的feedback就是1A2B,1代表数字5,2代表数字2和3.
分析:secret code为0-9的4位排列,所以共有10*9*8*7=5040种情况。初始时secret有5040种可能,然后我们逐步通过每次的feedback将错误的code去掉,直到我们剩下一个code,这个code就是我们的secret code.
code set = all 5040 codes
如果利用feedback去掉错误code,假如一个code与guess的feedback与secret和guess的feedback不相同,那么这个code肯定不是secret code。
if feedback(guess, code) != feedback(guess, secret): remove code from code set.
然后我们在code set中随便选一个code作为我们的下一个guess,直到猜对为止。
这种方法也是最蠢的方法,worst case需要9步才能猜对。但是我们班的老美竟然还有很多average都是20多步的,真是醉了。

这个问题其实也算是一个搜索问题,和下象棋差不多。在搜索问题中有一种很经典的方法,叫做启发式(Heuristic),启发式其实可以理解为评估式,这种方法有一个启发方程(Heuristic Function)用来对当前状态的每一个successor进行评估。在mastermind中,启发方程就会对我们所有可选的guess进行评估,然后选取最好的guess.
那么在mastermind中,如何定义好与不好。最直观的定义就是我们选取这个值作为guess,可以去掉多少错误的code。
目前我研究过两种效果不错的评估方法,一种是minimal maximal subset size,另外种就是subset number。
minimal maximal subset size:
这种方法实际上是利用了minimax的思想,如果我们选择一个值的话,使用这种选择最坏的后果去对这次选择做出评估(做出这个选择最糟糕的后果是什么),然后我们在所有的选择中选择最不糟糕的(无期总好过死刑吧)。每一个guess都能将code set划分成很多个feedback相同的subset,secret可能在subset中的任何一个,因为我们要做最坏的打算,所以最坏的情况下我们的code就在这个最大subset中。然后在所有的code中,我们选择maximal subset size最小的作为下一个guess。

另一种其实可以理解为期望subset size,因为所有subset size的总和是一样的,等于code set的大小。subset size的期望值就等于subset size的总和除以subset的数量。

Comments: 0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: