Conway是一位数学家，John Horton Conway，活跃于有限群论，结论，数论，组合博弈论和编码论。 他还为休闲数学的许多分支做出了贡献，最著名的是1970年，细胞自动机（cellular automaton）的发明，即生命游戏（The Game of Life）。即这个比赛需要攻克的游戏。Conway在利物浦出生，长大，在剑桥大学度过了职业生涯的前半段，后移居美国，在普林斯顿大学担任约翰·冯·诺依曼教授职位。
2020年4月11日，他享年82岁，死于COVID-19并发症。
这个比赛的发起者是Kaggle。六年前发起过，今年做了一些小的修改后再次发起，重新发起，应该是为了纪念这位在疫情中逝世数学家。
这是一款零人游戏，意味着其演变取决于其初始状态，无需进一步输入。趣味在于创建初始状态，然后观察其演变。该游戏是图灵完备（Turing complete）的，可以模拟通用构造函数或任何其他图灵机。
生命游戏的宇宙是一个无限的二维正交方格，每个方格都处于两种可能的状态，即活着或死了。每个方格都有八个相邻的方格，称之为邻居。然后，在每个时间步上，都会完成如下转换：
1. Underpopulation：任何具有少于两个活邻居的活细胞都会死亡，就好像人口不足一样。 2. Stasis: 任何有两个或三个活邻居的活细胞都可以存活到下一代。
3. Reproduction: 具有正好三个活邻居的任何死细胞都变成活细胞，就像通过繁殖一样。
4. Overpopulation: 任何具有三个以上活邻居的活细胞都会死亡，就好像人口过多一样。
自从被发明，生命游戏就吸引了人们的极大兴趣，因为它可以以惊人的方式演变。即使初始状态没有经过设计，也能演变成有组织有设计的状态。对于计算机科学家，物理学家，生物学家，生物化学家，经济学家，数学家，哲学家，生成科学家以及其他人来说，执行非常简单的规则而出现复杂模式的这种现象非常有趣。它可以用来传达某种违反直觉的观念，即在没有设计师的情况下，“设计”和“组织”可以自发出现。哲学家和认知科学家丹尼尔·丹尼特（Daniel Dennett）广泛使用了生命游戏的宇宙的类似物，来说明复杂的哲学构造（比如意识或自由意志）可能是从简单的确定的物理定律演化而来的。
生命游戏会出现许多不同类型的模式，这些模式根据其行为进行分类，常见的包括：
静物，一代又一代不变，如下图：
振荡器，经过有限的世代后返回初始状态：
宇宙飞船，在整个网格中转换：
更多细节可以去看参考[1]。
而Kaggle这个比赛又与生命游戏略有不同，Conway’s Reverse Game of Life，这个比赛想知道的是，如果我们倒退时间，会发生什么。这个竞赛是一项实验，旨在研究机器学习（或其他方法）是否可以预测反向的生活游戏。 有序的结尾是否能用来预测混沌的开始？ Kaggle进行了许多不同开始的生命游戏，并提供参赛者最终的状态。要求参赛者预测每个最终状态的初始状态。
1. 数据构成
50,000个游戏样本作为训练数据，50,000个作为测试数据，任务：预测起始状态。理论上，生命游戏的宇宙是无穷大的，但现实中的游戏很难满足这个条件，在比赛中，生命游戏的宇宙为25x25的空间，总共625个单元。如果需要，参赛者可以自己生成更多的游戏样本作为训练样本。
训练文件的变量：
id- 游戏编号delta- 启动状态到停止状态经过的步数start_0- 启动状态第一行第一列的值start_1- 启动状态第一行第二列的值- …
stop_0- 停止状态第一行第一列的值- …
参赛者对于测试集的预测应该是停止状态在给定步数之前的状态，即启动状态。训练用的测试集和训练集是这样生成的：
- 以1%-99％的随机密度填充空间中的单元。
-
然后经历五步，生成启动状态。
- 然后启动状态开始经历一定步数到达停止状态。经历的步数是随机产生的，在1-5之间。如果停止状态是空的，即所有细胞都死了，那这个游戏样本不会被加入训练集和测试集
常见问题 为什么需要热身步骤？从最初的随机状态到下一个状态的演变可能会非常“非线性”且神奇。比如，如果初始状态大多数细胞都还活着，那么一步之后它们可能都死了。所以五个步骤的预热可以使细胞平静下来，更接近生命演变的方式。 生命游戏随着时间的流逝会丢失信息，什么原因？正确，这是一个多到一的问题（不同启动状态可能产生相同停止状态）。但在短步骤内，这应该是一个小问题。这项比赛中倒退的最大步长是5，就是希望退化不会成为问题。 我可以预测任何有效状态吗？任何能以指定步数达到结束状态的开始状态都将获得最佳分数。
2. 模型评估
计算误差用的是平均绝对误差（mean absolute error）
用参赛者给出的启动状态经历指定步数得到终止状态，再计算这个终止状态和被预测启动状态的终止状态的误差。
3. 时间
比赛截至: November 30, 2020
4. 实现
解题思路一：基因算法（Genetic Algorithm）
参考[5]，该作者公布的算法，成绩是0.06189，可以在LeaderBoard上排到13，作者本人最好的成绩是0.05861，排到了12名。目前LeaderBoard上最好的成绩是0.00939，他用的什么算法呢？
基因算法概念上可以这样理解，有一群袋鼠，一开始随机在可能的解上均匀分布，然而，在劣势解上的袋鼠会被慢慢地消灭，而在优势解上的袋鼠会不断繁衍，这样，最后袋鼠们会慢慢聚拢到一个一个局部最优解上，然后从这些局部最优解中选择最优的作为最终解。基因算法并不能保证一定能得到最优解。
解题思路二：Z3约束 (Z3 Constraint Satisfaction)
参考[6]，分数是0.0857。Z3约束是微软开发的一套约束求解器，简单的可以理解为解方程的神器。很强大，可以了解看看。该作者还开源了另外一种方法，比这个方法成绩稍微低一点。
这世上，有人赢了，有人输了，有人已经死去了，有人还好好地活着，有人想预测未来，去触摸世界的尽头，也有人，想回溯过去，看看世界它本来的样子。
可谁说，不是一回事呢？
参考：
[1] https://en.wikipedia.org/wiki/Conway’s_Game_of_Life
[2] https://www.kaggle.com/c/conways-reverse-game-of-life-2020
[3] http://jakevdp.github.io/blog/2013/08/07/conways-game-of-life/
[4] https://en.wikipedia.org/wiki/John_Horton_Conway
[5] Game of Life - Genetic Algorithm (Spanish), Desareca, 2020, https://www.kaggle.com/desareca/game-of-life-genetic-algorithm-spanish
[6] Game of Life - Z3 Constraint Satisfaction, James McGuigan, 2020, https://www.kaggle.com/jamesmcguigan/game-of-life-z3-constraint-satisfaction
[7] 番茄鸡蛋炒饭被抢注啦，[算法]超详细的遗传算法(Genetic Algorithm)解析，CSDN，2018
![Kaggle比赛系列：[Two Sigma] Using News to Predict Stock Movements](/assets/images/Kaggle比赛系列：[Two Sigma] Using News to Predict Stock Movements/2.png)
Comments