新闻动态 news

联系我们 contact us


  • 010-85898922
  • 北京市通州区万达广场B座1315室（八通线地铁A口出）
  • （售前技术）

  • 游戏编程中的数学：如何解决任天堂的CodinGame挑战？

  • 发布人：九四玩
翻译：王成林（麦克斯韦的麦斯威尔）
审校：黄秀美（厚德载物）

我叫Mike Acton，是一名在Insommiac Games工作的引擎指导，今天我要讨论的是如何解决任天堂的CodinGame挑战。也许你不了解CodinGame，这是一个在线网站，可以通过游戏进行编程。另外还包含一些难题挑战，人们可以在上面完成挑战，帮助人们熟悉编程。你可以在很多网站上找到相似的内容。不过任天堂发起了一项挑战，它引起了我的注意，因为我觉得这个挑战可能和游戏有关，可能会很有趣。我即将为大家展示的所有幻灯片，包括这个文档，都可以在我的GitHub上找到，你可以将它下载下来仔细阅读。这里是链接：


好了，今天的演讲着重于过程，而不是答案。我只是详细介绍一遍我自己的解题过程。也许同一道题有很多其他解法，我只是介绍我自己的。我也许会展示一部分答案，不过这不是演讲的重点。我将主要讲解在解决这些问题时写的所有测试代码（或者至少是测试代码最重要的那部分）。从测试00到测试1f，我会解释我解题时的思路以及为什么要这样做。

好了，我们从测试00开始吧！测试00：我要解答的问题是什么？ 对于它我都有何了解？我们打开网页就可以看到问题：“SETI项目收到了来自半人马alpha星座的消息。最频繁出现的是这些信息。我们还不知道为什么这些信息被编码了，不过很有可能是半人马星座人在尝试和人类建立高级通信之前先评估我们的认知能力。我们最好的工程师在尝试对这些信息解码等等……”，首先对问题做了一番背景设定。然后在下面给出了一些程序的伪代码示例。我仔细阅读了一下这些伪代码，试图理解问题的含义。首先我们要做的就是拨开所有的背景迷雾，思考它叙述的意思。

我们梳理并总结一下问题：

1.    存在一个函数f，输入A返回B

2.    这里的问题是给定B和f，我们要求出所有满足函数的A3.    其中A和B可以是64,128,256,512位。

以上这三条是对问题一个很简洁的描述。对我个人来讲，我将f称为“编码（encode）”，因此f的逆运算为“解码（decode）”。如果B等于A的编码，那么对B解码可以得到一个A的集合，其中包含所有编码后为B的A。有了伪代码以及网站提供的C++代码，这里显示的编码函数基本上和问题提供的代码差不多。仔细观察这个函数（这里写着“神奇的半人马座运算”），我根本不懂它在干什么。


所以我的目标是首先明白编码函数的含义，在深入了解后再开始写解码函数。因此对我来说最重要的是先弄明白编码函数。

首先我使用随机整数来进行测试。如果你刚才听了Squirrel的演讲，你应该知道使用好的随机数非常重要。我通常采用的方法是打开random.org，这是一个神奇的网站，你可以从上面下载很好的随机数，将其作为一个噪音表。我希望不断地重复我的测试，所以要有一套固定的随机数字表。因此我从中下载了一组随机数，将它们放在一个rand_ints.h文件中。这样确保了后面所有的测试使用的随机数字组都相同。

那么对于测试00，我只是打印了这些编码函数的结果。我只想看看结果，看能不能找到一些规律。如你所见，这里我遍历了test_count个数字，这是rand_ints中随机数字的个数。我只是对它们调用了编码函数然后打印结果——我只想看看结果是什么样子的。

看上去是这样的。


我花了很长时间盯着它，希望从中找到任何有趣的规律，不过我没有找到任何线索，所以我们需要进一步进行分析了。

于是有了测试01：编码函数的输入和输出值有什么明显的关系吗？我们需要测试很多明显的关系，但是最明显的莫过于输入和输出值的位是否有相关性。具体来讲，这里我要测试的是：A的某位为1的情况下，B与其对应位为1的概率。这就是这个简单的函数全部的作用了：

在测试01的伪代码中，它遍历了所有结果数字中的每一位，这里是A组所有数字中这一位为1的个数，这里是B组所有数字中这一位为1的个数，然后计算A的这一位为1的情况下，B这一位为1的概率。然后我仔细观察了结果，从第0位到第63位所有这64位。中间的这些位，超级无趣！它们几乎都在0.5附近，基本上A和B无相关性。

不过开始和结尾这两部分非常有趣：

给定A的位为1，B的位为1的概率只有20%，或者24%左右。因此A和B的这些位之间有着高相关性。另外这种相关性在开始部分逐渐减弱，在结尾处该相关性则逐渐增加（说明两头的位具有高相关性）。我心想：“这简直太有趣了，我可以好好研究这一点！”这里我顺着另外的思路进行了很多许多的计算与分析，在这里就不一一展示了。不过我的思路是状态机生成，你完全可以使用它来解决这个问题，但这绝对是一个冗长的方法！首先你要找到B的第一位为1需要什么条件，并确定满足这些条件后B的第一位一定为1。然后你可以根据找到的这些条件，推导出B的第二位为1需要哪些条件，以此类推。最终你可以根据这些条件构建一个状态机生成器。如我所说，这个方法完全可行，只不过要花很长很长时间。

随着我在这个方法上花费的时间越来越长，我发现我遗漏了一个最明显的测试，即这里的测试02：我们使用有序数字代替随机数字作为输入值。因此在测试02中，我使用有序数字测试编码函数。对于输入值a，我将它的高32位设为固定值，然后使低32位递增，在测试中它从0开始，然后是1,2,3……对这些递增的a编码，然后查看输出值b是否有什么规律。

嘿，这次结果有趣多了！有很多位都呈现出了相关性。我们看这里（每一对数字上面为输入值，下面为输出值），这几组数字之间有很高的相似度！很明显我们可以看出，当输入值呈递增关系时，输入和输出值之间有了一定的相关性。我在看到这个结果时第一反应是这可能是某种格雷码，这是我首先想到的可能性。

在下一步中，我将结果变化了一下，将其按照小端格式输出，看看能不能在视觉上找到一些规律。这就是测试03的内容了，我仅将结果的两个32位换了一下顺序，这样对我来说更加自然，也许我会发现一些不同。这里显示的就是了。

当我浏览这些数字时，我有了一个非常有趣的发现：

我发现A中每一个2的乘方都很有趣。所以下一步我打算只打印2的乘方，我们来看看有什么规律。

测试04：我们只打印2的乘方。我们只观察这些数字，从中寻找一些规律。

我们发现这里有一些位发生了左移，所以很明显2的乘方中有一些有趣的规律。事实上，我单独分析了这些数字，发现了一些相似之处。

这里是a[0]和a[1]，由于上个测试我们交换了一下它们的顺序，现在右边是a[0]而左边是a[1]。我们从a[0]开始，看上去b其实就是将a[0]向左位移得到的结果，而位移的个数等于a[1]尾部0的个数。

我现在有一个问题：如果a[1]不是2的乘方会如何呢？我随便挑选了一个数字，这里恰巧是0f，将它分解成2的各乘方的一个线性组合。在测试05中，我打印了1,2,4,8的编码结果，以及f的编码结果，观察f的编码结果和构成f的2的各乘方的编码结果是否相关。

这里是输出结果：

首先是输入值f，然后是1,2,4,8这四个构成f的2的各乘方的编码结果，以及最下面是f的编码结果。我仔细分析了这些数字，发现了一些有趣的现象，就是这个：

我发现f最后一位等于这一列所有构成f的2的乘方的异或运算。比如最右边的第0位就是1^0^0^0=1。类似地，第二列1^1^0^0=0。我发现每一列都符合这个规律。我发现这一点很有趣。于是关于该编码函数我有了一个初步的推断：给定64位数字a和b，其中我可以将a分割成两个32位数字，该函数大致上是这样子的：

这里我遍历了a[0]的所有位，如果为1，那么b和a[1]进行异或运算后向左位移i位。这些步骤应该可以重现函数的结果。现在我要测试一下它。

首先为了便于查看，在测试06中我重新设置了一下输出格式。

这一步提供的价值只有视觉上的价值，使我可以从另一个视角思考问题。这是我的一个常用手法。

在测试07中，我想要使用一个更大的样本集合进行测试，看看我的推断是否仍然成立。因为直到现在为止，我们只测试了非常有限的集合。a[0]的数值只来自一个很小的集合，事实上测试06只使用了一个数字f，不是吗？而a[1]到目前为止都被我设为固定值。

那么问题来了：

1.    我的理论（主要是这个for循环）对于所有的取样数据都成立吗？

2.    如果a[0]不为该集合中的数，我的理论会发生改变吗？

于是我编写了编码函数的另一个版本encode2_32：


它只是我们刚刚看到的伪代码的代码实现，没有任何特别之处。

测试07使用了相同的随机数字集合作为输入值，运行了原始函数以及这个新的函数，然后检查二者结果是否相同。

对于该测试我只想检查该新版本的编码函数是否适用于所有随机样本。事实上答案是肯定的。现在我非常有信心，我能确定函数的大方向差不多就是这样了。

接下来我想对编码函数稍作改动。

这里我进行了测试08，因为我认识到我可以先做if检查，然后左移i个位，或者我可以直接乘以a1。只是稍微做了一些调整，我知道这两种形式是等价的，它们进行的是相同的运算，可以得到相同的结果。不过，在测试08中，我还是想重新运行一下。所以我写了代码然后进行了测试。幸运的是，所有的测试顺利通过了，结果仍然相同。

在测试09中，我想返回到之前，输出所有测试值的结果，并将输出格式再度进行调整。我想再次查看它的输出结果。因此测试09和测试07一样，只不过encode2_32函数打印了所有的步骤，因为我的习惯就是在代码中插入很多printf来显示每一步的结果。

这是测试09输出的样本结果，看上去是这样的。


  它输出了每一步的结果。在最上面是a[1]，右边是a[0]，你可以看到a[0]的每一位。最下面这一行是结果b。如我之前所说，b的每一位都是其所在列各位进行异或运算的结果。结果和我们预想的一样，不过它看上去非常有趣，因为当我看到这个结果时，发现它非常像某种长乘法运算。只不过对于每一位，它们的运算稍有不同。乘法在这里是按位与，加法则变成了异或。这里的乘法，实际上是按位与，因此只有1*1=1。而对于加法，它的真值表则是这样的：

那么问题来了：什么数学运算能符合这个模型呢？事实上，有一种运算完美地符合这个模型，即GF（2）中的多项式乘法。如果你恰巧没听说过GF（2），那么我真不知道该如何从上一步来到这。这里跳跃了一大步。问题在于你还不能直接搜索这些表格，这样做很困难。我的建议是，对于不知道的东西，比如这组数字，而同时我又确定它一定有一个专门的名称，通常我会写一些代码，按照顺序输出一些数字，然后我可以在网上的整数数据库中寻找和这些数字匹配的内容，这样我可以找到符合那个模型的内容了。这是我通常使用的方法。

简单来讲GF（2）意味着两个元素的有限域。


如这里所示，我们在维基百科上搜索GF（2），你会发现这些表格和我们之前得到的结果一模一样。作为程序员，我们无时无刻不在使用有限域。假设我们有一个uint8类型的变量a，它的值为ff，那么我问你a+2等于多少，估计大多数人都知道答案是多少。我们知道答案，因为我们知道它只是有限个数字的循环，只是对于某一个数字求余而已。而在GF（2）中则意味着所有数字都要对2求余，余数只有1位（0或1）。超级简单，很容易理解。这篇论文是关于有限域一个很好的概述，如果你对此感兴趣的话，我强烈推荐你阅读它。

使用数字表示GF（2）中的多项式意味着两点：

1.    每一位所代表的指数为隐性的

2.    每一位的系数都被保存在数字中

GF（2）中的系数只能是除以2的余数，即1或0。举个例子，1011这个数字，它的每一位的指数是隐藏起来的，所以从右往左，每一位分别代表x^0, x^1, x^2, x^3。

这就是1011，它映射为x^3+x+1。你可以清晰地看到它是如何映射的。

测试0a。现在我差不多有了一个模型以及相对应的一些推测。我推测编码函数的作用就是在GF（2）中多项式的乘法。目前为止，我的模型符合这套理论。我不管事实是否真是这样，既然模型符合理论，那么现在我认为这就是事实。接下来我想定义一个新的函数，名为p_gf2_mul，然后使用有关GF（2）的术语重写该函数，理论上应该得到相同的结果。于是我创建了一个新文件gf2_00.c，然后使用相关术语重写了函数。我定义了p_gf_mul，p_gf2_add（即异或运算），以及p_gf2_sll（即逻辑左移运算，将整个数值向左移）。


这个是乘法函数，和我们之前见到的各版本的编码函数很像。它循环了每一位并对它们进行测试，如果为1，那么就将其加进来（和异或运算一样）。然后对a进行位移，然后继续处理下一位。你可以将这个过程想象为以我们熟悉的形式进行的长乘法运算。我使用这个函数又重新做了一遍所有的测试，结果所有测试都通过了。我得到了相同的结果，只不过采用的方法有所不同。

好，接下来是测试0b，另一个可用性测试。现在我想测试一下，新的方法适用于所有的位数选项吗？我一直将重点放在64位，现在我想看看其他位是否也成立。我需要验证b为128位，256位，512位这三种情况。所以测试0b和之前的测试一样，只不过我们要测试这三种情况。我们使用相同的随机数字表，相同的随机数字，只不过需要更多。之前需要前32位的数字，而现在我们需要两组32位数字用于64位，而对于128位则需要四组。对它们进行测试后我发现所有测试都通过了。所以我现在非常相信这个模型实际上就是我们寻找的结果，并且它适用于所有位宽选项。非常完美！

接下来测试0c。现在我觉得已经完全理解了编码函数的意义，那么解码函数的意义呢？事实上，这里我要正式开始解决题目的问题了。问题：如果编码函数是p_gf2_mul，那么解码函数是什么？乘法的逆运算当然是因式分解了！现在我要看一下题目给的测试案例了。这是测试案例1：


现在以我对于解码函数的理解，很多东西对我来说已经显而易见了。现在我可以稍微解释一下输入值和输出值了。这里，输入值为一个64位的多项式，以小端格式给出，它只有下16位不为0，而下面则是它的因式分解结果。


首先是1和这个多项式相乘（第一组和第四组相同，只不过相乘顺序发生了变化），结果当然等于多项式本身。然后这两个由83和e5表示的多项式相乘也可以得到73af，下面那组它们交换了相乘顺序，当然也可以。不过我想说的是观察其他这些测试案例，我们可以找到相同的模式，即其中一定有一组是1和这个数字，以及顺序颠倒的另一组。另外在输出结果中总有两组实际上是相同的（只是相乘顺序颠倒了）。我早先在观察这些测试案例时，应该能够想到这其实和多项式乘法和因式分解有关。当我看到这一对对数字，以及一个数字乘以1时，这应该是很明显的，但是我完全没往这方面想，完全地错过了！对于我来讲，我必须通过这一系列的分析过程，观察得到的数据，仔细分析它们，然后重新构建编码函数。最后才能理解这些测试案例发生了什么。

好了，我们继续测试0c吧。我想把测试案例中的数字以多项式的形式输出。这只是为了看上去更加明显。将所有的测试案例输出为多项式，像这样：


上面是数字，下面是对应的多项式。在这个范例中，我想73af表示的多项式应该等于83和e5表示的多项式的乘积，即（x^7+x+1）（x^7+x^6+x^5+x^2+1）。我发誓在今天的演讲中尽量不读多项式！首先我想，如果这是正确的，那么我只需要三秒钟就能在Mathematica中验证它的对错。于是我将输入多项式复制粘贴——我能够直接复制粘贴是因为我设置好了它的格式——到Mathematica中。然后使用Factor函数对其因式分解。幸运的是，Mathematica能够进行模长为2的因式分解。然后我得到了这两个多项式，事实上它们和83和e5代表的多项式完全一致。现在我超级有自信，确定我们选择的方向没有错。如果你有计算器的话也可以使用它来验证。所以我将其它测试案例也复制粘贴过来进行验证，看看是不是也能得到相同的数字。事实上，答案是肯定的。得到的答案和我预期的完全一样。

测试0d：开始思考解码函数的作用，以及它的过程可能是怎样的。我不止想要把数字放到Mathematica中进行验证，我想要实现这个步骤，所以我要理解它背后的原理。至此，我可以重述一下问题，将它写了下来。给定GF（2^n）上的一个多项式，其中n=（64,128,256,512）这其中的一个，求所有指数小于等于n/2的因式对儿。如果因式分解出了超过两个因式呢？比如某个多项式的因式分解结果包含一堆因式该怎么办？我觉得这里你只能将它们重新合并（相乘）成一对儿因式以满足题意要求。大致的步骤是这样，我们只需找到所有构成f的不能进一步简化的因式，将它们重新合并，最终得到一对儿因式就是结果了。非常简单直接。不过现在的问题是我不知道如何分解GF（2）中的多项式。所以这是我的下一个要解决的问题，我该怎么办呢？于是我问我自己，Knuth有什么方法呢？

这是我的天命之书！我不知道你们是不是也是如此，反正我觉得《计算机程序设计艺术》这本书参考起来超级方便，尤其是在我知道答案，但是因为题目过于复杂不明白答案为什么会这样，从而想要弄清楚过程中的某个难点的时候。现在这道题就是这个情况。说明一下，这是第二册，第四章的4.62，多项式的因式分解，正是我要找的！这半页纸上的内容基本上是我们要做的：


我刚开始阅读这半页纸的时候，发现它写的非常简洁，我根本不明白它在说什么，觉得这太困难了，因为我还不知道答案。不过幸运的是，这里有一条提示：Berlekamp算法。我需要google搜索这个算法，弄清楚它的意思。在一系列的搜索与阅读之后，我找到了一篇论文。关于这个算法有很多的论文，我个人觉得这篇文章最有用，它的描述最直接。我在这里放了一条链接，如果你感兴趣可以看看。非常短，也就9页左右的样子，其中还包含了一个完整的例子，我觉得如果有例子的话会非常有助于理解。

好了，回到题目。我们来看看第一步——在这之前我先仔细阅读了Berlekamp的这篇论文，大概了解了一下，现在我做好准备开始第一步了。第一步B1：确保u（x）不含平方。这是什么意思呢？这意味着假如我有一个多项式a=b^2cd，我们要把b^2提炼出来，结果得到两部分：a[0]=b^2，a[1]=cd，它们相乘结果等于a。就是这样，将所有含平方的因式都提炼出来。

不含平方的因式分解（Square-Free Factorization，SFF）如果gcd（u(x), u’(x)）≠1，那么u(x)有平方因子。据此我们创建下列步骤：

1.    首先给定u（x），使其等于f

2.    对f求导

3.    求出f和f’的GCD（最大公约数），使结果等于g4.    f等于g乘以某个多项式h，现在我们还不知道h是什么5.    既然我们知道g是多少，可以使用f/g求得h

这个过程直截了当，除了一点问题，我们一会儿会提到。我们先看一个含有平方的例子。这个例子是我自己编的，它非常复杂，足够我们检验对错了。


在下面的中间部分，红圈中的那一项就是含有平方的因式。我将这个平方因式提炼出来，我知道a和b分别应该是什么，因此在测试0d中我将这些剩下的因式乘在一起以得到b。我们已经多次进行过乘法运算，对此相当熟悉了，这里我只是想验证一下。于是我将它们乘在一起，得到了这个式子，即b。


我将它放到Mathematica中进行验证，确保因式正确。好了，在SFF之后，我知道a和b是我应该得到的两个多项式，其中a含有平方。我知道我需要什么，但是我需要思考如何做。例如，如何对GF（2）中的多项式求导？这时候我还不知道应该怎么做。那么我们从这里开始吧。

我们快速回顾一下通常的步骤。比如我们要求x^2+x+1对x的导数，正规的方法非常简单，只需将每一项的指数乘以前面的系数，然后指数减1就行了。最后我们得到2x+1。一个非常直接且套路化的方法。不过在GF（2）中，步骤虽然还是这样，但所有数学运算是在GF（2）中进行的。因此2x这一项的2除以2的余数为0，所以x^2+x+1在GF（2）中对x的导数事实上等于1，因为2x变为0了。最后总结一下，在GF（2）中求导的过程分为：

1.    所有的系数都对2求余，所以只能为0或1

2.    所有的偶指数都要乘以0或者1以得到系数，因此得到的系数为偶数或者0。然而所有偶数都等于0（对2求余），所以最后都为0。所以我们可以过滤掉所有指数为偶数的情况，我们不需要其中任何一项。

3.    所有的奇指数都要乘以0或者1以得到系数，因此得到的系数为奇数或者0。所有奇数对2求余都等于1，所以我们可以直接将奇指数减1，也就是将奇指数项向右移动一位。

具体过程是这样的。我们使用这个例子，101111。首先我们划掉所有指数为偶数的项，因为我们知道它们不重要，任何数乘以偶数都是偶数，都会变成0，所以我们将这些项过滤掉。然后将所有剩余项都向右移动一位。最终得到这道题的结果x^4+x^2+1，和我们预期的一样。

到这里我觉得这一切都像魔法一样。整个求导过程太直接，太简单了！所以在测试0e中我输出了范例中的导数，为了检验一下我做的是否正确，是否合理。


这里输出了a，以及a’，看上去完全正确！

然后是下一个测试0f，如何找到两个多项式的GCD？因为这里显示下一步是g=gcd（f,f’）。那么如何得到GF（2）中多项式的GCD呢？事实上，和过程中很多其它步骤一样，只需按正常方法求GCD，然后在GF（2）中进行系数的数学运算，因此所有系数都要对2求余。回顾一下如何求GCD。简单来讲就是GCD（a,b）=GCD（b，a mod b），然后检查a mod b是否为0，如果不是的话我们继续重复这个流程。

但是呢，a mod b是个问题，因为这意味着我需要在GF（2）上进行除法运算（求余运算需要用到除法）。那么我该如何在GF（2）上做除法呢？同样，步骤和普通的多项式除法相同，只不过系数的运算要在GF（2）中进行。我们先回顾一下普通多项式的长除法运算吧，先来看这个例子。我就不全读了，不过第一步是考虑x+1乘以多少等于x^3，所以首位需要x^2，然后接着下面的步骤。

服务热线:

400-869-9305

客服QQ:

445307582

九四玩·北京开源纵横网络科技有限公司 京ICP备15000695号 京网文（2018）9972-889号 增值电信业务经营许可证：京B2-20190580

旗下产品：手游平台系统、页游平台系统、H5游戏平台系统、游戏平台三合一版。九四玩致力于游戏平台系统开发、游戏代理、游戏运营指导等服务。

合作&投诉电话：010-85898922、4008699305

投资有风险，选择需谨慎