The Game of Life
介绍
与其说是game，其实它更像是一个simulation，在1970年由英国数学家J. H. Conway提出的。The Game of Life的规则很简单：假设有一个无边界的矩形网格（我更喜欢把它称作宇宙，或者universe），这个矩形网格中的每个单元可被一个有机体占据（同样地，我更爱细胞这个词，或者cell）。被占据的单元称为活的（alive），未占据的单元称为死的（dead）。哪一个单元是活的要根据其周围活的邻居单元（neighbor）的数目而一代代（generation）地发生变化，规则如下：
- 给定单元的邻居是与它在垂直、水平或对角方向上相接的8个单元。
- 如果一个单元是活的，但没有邻居单元是活的，或者仅有一个邻居单元是活的，则在下一代，此单元就会因孤独而死亡。
- 如果一个单元是活的，且有4个或4个以上的邻居单元也是活的，则在下一代，此单元会因为拥塞而死亡。
- 一个活的单元，如果具有2个或3个或的邻居单元，则此单元在下一代仍是活的。
- 如果一个单元是死的，则在下一代，如果它不多不少刚好有3个邻居单元是活的，则此单元变成活的。所有其他死的单元在下一代仍是死的。
- 所有的出生和死亡都刚好在同一时间发生，因此正在死亡的单元有助于另一个单元的出生，但它不能通过减少阻塞而组织其他单元的死亡；正在出生的单元也不能保护或杀死上一代中活着的单元。
以上是我从我第一次看到The Game of Life的书——Data structures and Program Design In C++——里面节选出来的，除了括号里面的字，因为我比较喜欢那样的称呼^_^。
第（6）点可能有点怪怪的，举个例子说。假如下面的©代表一个alive的cell，◎、①代表一个dead的cell，那么对于以下这样的情况，◎的位置的cell因为刚好有3个neighbors，将会变活。但这不会影响到旁边的标记为①的cell的生死，①位置的cell只有2个neighbors，没办法继续存活。
◎①
©©©
就是这么简单的6条规则（我承认我的那本书上写得有点长气），但这么简单的几条规则确可以变化出相当复杂的过程。不同的初始宇宙配置（就是第一代宇宙的模样），演变下去规模可以变得十分庞大复杂，也可能慢慢的变得稳定，有的甚至灭绝（全部细胞都挂了――b）。
在The Game of Life发明后不久，Martin Gardner就在Scientific American的专栏里面对它进行了讨论，很多人为之着迷。
没有理由的感叹一下，The Game of Life，会不会就是我们的现实生活的一个写照呢？在我们活着的这样的复杂不堪的世界里面，说不定只有几条十分简单的规则在不停运转着。
只是我们还没有发现（或者说没完全发现）The Game of Our Life的规则而已。
当上帝的助手——实现The Game of Life
Conway给我们定下了6条规则而把宇宙交给了我们。我第一次实现The Game of Life（好长……后面简称tgol好了）是在C++上，大约是2年前的事情了吧。最近无意中在emacs里面再次发现了它的身影，又正逢我在学习python，正好拿来练习练习。
于是好几个版本的tgol（在我编写的时候，tgol被我称做Life Game）诞生了，限界不限界的都有，到今天成功进化到了1.3.2版（其实我不太会定版本号――b，下载的链接可以在文章末尾找到），学到的还是不少的。
* 有界还是无界？
在Conway设定的tgol里面的universe本来是无界的。由于边界的原因，有界的结果跟无界的有时是大相径庭的。主要原因在于有界的宇宙，细胞一旦到边界了就无法继续发展，因而边界外也不会产生活细胞对边界内的universe进行干涉。
绝对不会是最有效，但绝对是最简单的实现有界tgol的算法就是一个矩形数组（在python里面就是list的嵌套），然后从最开始遍历到最后。对于边界的cell可以加入额外的监视哨消除特殊性，然后就没什么好说的了。
而对于无界tgol，用这样的算法实现会相对复杂一点。我们或许可以申请一个相当大的数组去表达我们的宇宙，但我们并没办法阻止细胞们的增长，再大的数组也可能容不下我们的细胞。而且随着数组的增长，遍历整个数组的时间会变得越来越长。第一版的tgol就是用这样的算法实现的，结果前100多200代耗时还忍受得了，200代之后就变得蜗牛一样了。
这似乎是个解决的办法：随时缩少数组的规模。这对于某些增大了然后又缩小的细胞社会（society）似乎是有效的。缩少数组的规模并非意味限制宇宙的大小，很简单的例子是，用一个100×100的数组去表示一个只有1个细胞的宇宙，很明显是小题大做，一个3×3的数组就足够了，10000次遍历和9次遍历差别可是很大的哦^_^。
然而事实上这种做法没什么效果，首先是，细胞社会不会一直缩小下去，很可能过两三代以后又开始变大了，虽然确实缩小了遍历次数，然而对于整个运行来说，显得苍白无力；其次是，有些society会一直膨胀不缩小，在我发布的1.3.2版里面的”five block”就是很典型的例子。
对于用数组存储universe的这条路径，我还构思过一个方法，然而没有用来实现：只对需要计算的cell进行计算。所谓的“需要计算的cell”，就是存在变活或变死可能性的cell。很明显一个没有neighbor的dead cell是不可能变活的，存在变化的只有仍然alive的cell以及它们的邻居。为了用这种方法，必须对这些需要计算的细胞进行额外的记录（不然还是得从头遍历一次来确认）。在一次计算结束后，剔除无法存活的细胞，对剩下的细胞继续进行计算，这样遍历的次数就会大大的降低了。
这跟稀疏矩阵十分相似。
* 三元组还是十字链表？
作为稀疏矩阵的两种常用实现方法，我认为三元组比较直观，十字链表比较灵活。
而应用在tgol又是怎样的情况呢？
为了索引某个位置的细胞是否存活，查找是必须的。在理想的情况里面，对于三元组，一次索引就意味着平均要花上０.5(number_of_cells+1)次的比较。相比起来，十字链表需要的次数要少一些：假设细胞们很整齐的排成m×n，那么要索引到一个细胞平均起来需要0.5(m+n+2)次（行平均次数＋列平均次数）比较。如果进一步假设m=n=sqrt(number_of_cells)，平均就要花上(sqrt(number_of_cells)+1)次的比较。
而要决定一个细胞存亡的命运，必须进行9次索引操作（8次用于邻居，1次用于自身），合起来一共是9×number_of_cells次索引。
看得出用十字链表效率上是比较高的，主要原因应该是出于十字链表本身可按行按列遍历。当然换来的是空间上的损耗，不过从性能提升的角度来看，那些损耗是“物超所值”的。
* Cross List? Hash table?
哈希表的使用完全归功于我的tgol启蒙书——还是开头我说的那本。实际上，v1.3.2的实现就是用哈希表而不是十字链表实现的。事实上我没用十字链表实现过tgol，因为在我想到十字链表实现法之后的不久我就再次拜读了启蒙书去了，并发现hash table的效率似乎更优于cross list。
Hash table以其O(1)的时间复杂度著名，主要原因在于它在实现上还是一个数组，要访问hash table里面的元素就跟访问数组一样——直接定位，即使有冲突的问题存在，但无论是顺序hash table还是链式hash table都有一个有效的解决方法（我个人更欣赏链式的）。
那么选择hash table的原因就很明显了：O(1)的时间复杂度。这意味着，对于每个细胞，很多情况下1次查找就可以索引出结果了。尽管hash table中的冲突现象难以消除，但对于一个合理大小的hash table配合一个合理的hash函数来说，冲突是比较少的。
这样效率上的优势就很明显了，hash table的实现，可以把索引需要的查找次数控制在次低（仅仅从指定cell的查找次数方面评价，正牌的数组绝对是大哥，随机索引一次完成。而对于有一定规模的数据，hash table的冲突是很难避免的，而解决冲突必定会引入更多次的索引）。
---
回头一看发现自己已经写了2千多字了……希望自己写的不是些无用的废话吧。
刚刚回看自己的tgol代码，发现有些小细节还可以改进，代码就先不公开贴上来了，等我再写好点先……由于1.3.2里面用到了windows的API的关系，拙作暂时只能运行在windows系统上，可以在这里下载用py2exe发布好的win32-binary。1.3.2还只是windows console下的字符版，以后有时间，或许会利用python再写一个gui版吧。
感谢Conway的The Game of Life给我带来的欢乐。