很多人玩过这样一个猜数字游戏，它曾经在一些电子设备上很流行：
它的基本玩法是这样的：
电脑产生一个秘密的4位数的数字，每一位的取值都是0到9，四个数字互不相同。由玩家猜测这个数字，每一轮中输入一个4位数，电脑会返回玩家输入的数字中有多少数值和位置都猜中，另有多少数字猜中但位置不对。输出格式一般是：xAyB，表示前者有x个数字，后者有y个。
比如，如果电脑的秘密数字是2358， 玩家输入7328，则2A1B，因为玩家的猜测中，“3”和“8”的数值和位置都正确，而数字“2”是秘密数字之一，但是玩家猜测的位置不正确。玩家的目标就是用尽量少的轮次猜中数字。
这个游戏在英语中，被称为Bulls and Cows，Bulls就是数字和位置都中，Cows就是仅数值正确。所以这个游戏的英语版本中，也经常使用“2 Bull(s), 1 Cow(s)” 之类的输出。
相信很多人都想过这个问题：在这个游戏中，对任何数字，至少要多少轮可以正确猜出？最佳策略如何？最近又有人向我问了这个问题，于是我做了一些研究，以下是我一些研究的结果。
Bulls and Cows游戏的最早雏形出现在1970年代。目前已知的最早版本是剑桥大学计算机实验室的Frank King在1970年夏天开发的，在大型机（mainframes）上运行的版本。此后，该游戏长盛不衰，在各个平台上被反复开发。2021年，该游戏的单词版本“Wordle”一度十分风靡：
关于这个游戏的最佳策略研究，我找到了几篇论文：
John Francis 2010年发表的：Strategies for playing MOO, or “Bulls and Cows”[1]。主要从数学角度分析Bulls and Cows游戏，并比较了几种最佳策略，确定了在使用最佳策略时，玩家至多需要猜7次。
俄罗斯的Alexey Slovesnov最初于2008年（最新修改在2017年）发表的Optimal algorithms for mastermind and bulls-cows games[2]。该论文主要从算法上实现了一些该游戏的最佳玩法，还包含另一个类似游戏，Master Mind的算法。并且该作者提供了一个网站[3]，可以在线体验这些最佳算法，由玩家出数字，电脑来猜，非常实用。
日本的Tetsuro Tanaka于1996年发表的An optimal MOO strategy[4]，（链接为2022年发表的英文翻译版）。该论文为最早的，系统阐述Bulls and Cows游戏的最佳策略的论文。
以下会简单介绍一下该游戏的最佳策略，但在阐述之前，我们需要先搞清一个问题：何谓“最佳”策略？如何衡量？
这里其实有两个标准：
最差情形下的最少游戏轮次：在任何情况，使得游戏的最大轮次数最少的策略。
最少平均轮次：游戏的平均轮次最少。或者说，对所有可能的 个数字，该策略所使用的轮次总数最少，也就是平均每个数字所需的猜测轮次最少。
理论上，这两个标准可能会有不同的结果。比如，已知第一个标准下的最少轮次为7轮，有可能在第二个标准下，对某个数字的猜测轮次需要8轮。幸运的是，目前的计算结果显示，在第二个标准下，所有数字的所需最大轮次仍然是7轮。所以以下阐述中，主要以第二个标准为衡量“最佳”策略的准则。
另外，有一个关于最佳策略的朴素想法：
每一轮中，枚举当前还可能的数字，枚举电脑的每一种响应。电脑的每一种响应把所有数字划分为若干“等价类”。这些等价类中，数量最多的那个可以认为是使用这个数字进行猜测后的最差情况。那么枚举所有数字后，找出各种最差情况中的那个最好情况，就可以作为最佳策略。
这种思路是很不错的，所得策略已经接近最优策略。后面会指出，这种策略下，最终总会有一个数字需要8轮才能猜出，所以它并不是最佳策略。
实际情形中，要找出最佳策略，需要做很多细致的优化。目前几种不同的最优策略中，都是在前3到4轮采取以上想法，然后开始采用称为“Estimator”的方法，估计每一个猜测的代价，选择性价比最优的那个数字进行猜测。
所有策略计算的最终目标是生成一颗“博弈树”，每轮根据猜测后的答复，直接在树中进行查询，产生下一个猜测，从而无需重复计算。算法细节比较多，具体请直接阅读原版论文。John Francis的论文[5]中，对已知的一些策略有如下总结：
其中第一列是策略名称，列标题为数字1到8的列，是指该策略在第n轮猜测中，可以确定猜出的数字，所有这些数字总和就是游戏中可能的数字数量：。
可以看到，前三种策略都可以在7轮中猜出全部数字，并且总的猜测次数都是26274次，平均每个数字需要猜测26274/5040≈5.213次。这几种策略就是最少平均轮次下的最优策略。
“Larmounth - One”就是文章开头提过的那种朴素的思考策略，可以看到该策略下，总有一个数字需要第8轮才能被猜出。
如果你想体验最佳策略，可以到这里[6]玩在线版，你出数字，电脑来猜：
记得要在“algorithm”选项中，选择含有BullsCows字样的算法。含有“MasterMind”字样的算法则是另一个游戏。
为了这次研究，我开发了一个“懒惰版”的在线版[7]的Bulls and Cows游戏：
这个版本的游戏中，电脑并不实现生成数字，而是根据玩家每次的猜测，动态计算不同反馈中，能使剩余可能的数字数量最大的那个，并作为反馈输出，同时也会提示玩家目前还可能的数字数量。也可以说，这是一个“最难”的Bulls and Cows游戏。
使用我这个版本，你可以测试一下自己的猜数字技巧。也可以结合上一个链接，左右互搏，看看最佳算法是否能确保在七轮中猜出数字。
关于Bulls and Cows游戏的最佳策略，我就简单介绍到这里。这个游戏看似简单，但要找出最佳策略并不容易，其中用到了很多博弈游戏中的剪枝技巧。这个游戏中，也还有不少未解决的问题，比如两人对抗变体。这种变体中，游戏变成两人对抗，由电脑随机产生不同的数字给两名玩家猜测，某玩家猜出数字所使用轮次较少的话，则得1分，一样多则双方不得分。反复进行多轮，分多者胜。
已经有人证明，在两人对抗时，如一人使用前述最优策略，另一人可以找出一种更优的策略，可以在多轮对抗中，稳定获胜。这也意味者，两人对抗时，不存在静态的最优策略。目前还不知道两人对抗时，何种随机组合策略最优。
最后来一道思考题：
一局Bulls and Cows游戏，经过以上几轮猜测后，理论上还剩余3个可能数字，是哪三个数字？你又该作何种猜测？
Strategies for playing MOO, or “Bulls and Cows”: http://jfwaf.net/Bulls_and_Cows.pdf
[2]Optimal algorithms for mastermind and bulls-cows games: ttps://slovesnov.users.sourceforge.net/bullscows/bullscows.pdf
[3]网站: https://slovesnov.users.sourceforge.net/index.php?bullscows_play
[4]An optimal MOO strategy: https://arxiv.org/abs/2207.04845
[5]论文: http://jfwaf.net/Bulls_and_Cows.pdf
[6]这里: https://slovesnov.users.sourceforge.net/index.php?bullscows_play
[7]在线版: https://youhuali.github.io/lazy_bulls_and_cows/html_version/bnc.html
