大家知道"生存游戏"吗?
这个问题放在算法版似乎不大合适吧,但放在别处好象更不合适.
这是哪个外国科学家提出的一个玩意儿:在一个N*N的棋盘形世界里,有一种类似植物的生物,每个个体占据一个方格.这种生物的生存有如下规律:若一个个体周围八个相邻方格中有2至3个邻居,则它能继续存活,否则将在下一周期死去;若一个原本无生命存在的方格周围有且仅有3个邻居,则在下一周期将产生一个生命个体.各个方格的变化是同步进行的.
后来在科技纵横杂志上也看到一篇文章讲了这个问题,还给出了计算机从随机的生命分布开始,经过很多个周期后模拟得出的图案(每个方格一个像素的大小),竟与斑马身上的条纹相似!前天我也做了一下,也得出了这样的结果.
可是后来一想,就越发想不通.我的程序里对各个点进行遍历是以Y为内层循环,也就是从上到下,再右移一列继续从上到下,得到的斑马条纹是Y方向上的;如果我把循环次序交换就会得到X方向条纹.可是按理说,各方格的变化是同时进行的,当前的变化只与前一时刻的状态有关,那么怎么会出现这种与X和Y的循环次序有关的"各向异性"的图案呢?难道说杂志上那篇文章的作者和我都错了吗?
大家也来做做看,探讨一下.
问题点数：23、回复次数：28Top
1 楼dengsf（drklnk@Radical_Dreamer）回复于 2005-01-03 06:09:53 得分 1
有意思，mark
直觉上确实不应该跟循环的方向有关，
会不会是用程序模拟时的某些处理导致这样的？
比如，楼主的程序是不是将增加或死亡的状态马上反映在当前棋盘里，使得后面的行（列）使用了这些变化后的状态？Top
2 楼gambolgs（Gambol）回复于 2005-01-03 09:49:32 得分 2
大哥，这个问题恐怕不该在CSDN上面讨论，而该在某个哲学论坛上面讨论。
我从初中就开始思考关于这个Game of Life的问题了，现在简要的说有这些心得和所知：
1）Holland（遗传算法的发明人）就是从这个Game of Life中悟出编程之类比与宇宙之道的。就是说，世界可以由一种更新的“神创论”所解释。既是，上帝不直接创造和控制世界（不会一直直接手动修改棋盘上的状态），而是创造一套规则（棋盘的生存规则）和初始状态（棋盘上最开始的存在的方格）。在程序编好、初始状态设好以后，上帝（程序员）就不管了，而后等待棋盘上的玩意儿按照规则自生自灭。现在的世界就是按照那套规则自然演化的结果。
2）图灵（或者冯，记不清了），也在很早之前就提出了“分子自动机”的解释世界的模型。他认为宇宙分为很多不可分解的最小“对象”（姑且称为分子），每个“分子”都是一部有穷自动机一样的有确定输入输出对应关系的部件（类比于棋子的确定的生死规则）。虽然每一个小的单位的活动是确定的，但是它们组合起来会产生惊人复杂的结果（类比于棋盘最后的图案）。此人认为，这就是现在世界的真相。
3）最近的热门学科“复杂性科学”(complexity)就是讨论“极小单位的确定性组合出整体的不可预测性”的科学。就好比微软知道Windows每一句源程序的确定规则，但是仍不能保证组合出的系统的稳定性一样，我们也不能同过微观上的认为比较牢固的规律预测出宏观的行为（类比天气预报和股市不可预测,当然这两个例子不太严格）。而这些思想的都是跟楼主最先提到的“the game of life”有极大渊源的。
4）第一次看“黑客帝国”的时候，我心想“这个剧情太简单了！就是说棋盘上的棋子妄图突破代码限制而已”。我相信Matrix的来源也跟楼主说的游戏有关，不过很多地方为了通俗做了修改（比如机器人是靠自身介入而不是靠规则）
另外，楼主的演化算法似乎不是我所知道的标准算法。我在"数据结构的C++描述"（或者相近的书名）上看到有好几章涉及到这个游戏，但是书中用到的规则是做一个缓冲区B，下一轮回棋子的状态都由上一轮的棋盘A算好放到缓冲区B里，然后再一次性把B刷成当前棋盘A。这样就没有你说的循环的方向的问题。Top
3 楼aheadyes（）回复于 2005-01-03 10:36:57 得分 0
gzTop
4 楼baryjim（吃饭－睡觉－打豆豆）回复于 2005-01-03 11:45:33 得分 1
gambolgs(Gambol)的话让人耳目一新啊，计算机理论能升华到哲学是非常令人赏心悦目的！！
的确，一般的情况下需要一个缓冲区来保存中间结果，否则的话很可能出现父代和子代之间的不一致！
但是如果仔细考虑，不用缓冲也是可以的！
宏观和微观之间的差别到现在人们都无法领悟到。
我想，就像人们可以研究出各种理论，但是到现在还是无法解释自己的大脑如何工作的，也许正像图灵程序对输入自己是否停机无法判定一下，这个东西最终还是要在哲学中找到答案。Top
5 楼gambolgs（Gambol）回复于 2005-01-03 13:32:59 得分 0
是啊，这也是罗素的伟大之处吧？Top
6 楼NowCan（城市浪人）回复于 2005-01-03 18:03:03 得分 1
会不会是用程序模拟时的某些处理导致这样的？
比如，楼主的程序是不是将增加或死亡的状态马上反映在当前棋盘里，使得后面的行（列）使用了这些变化后的状态？
很可能是这个原因，一般都要用双缓冲来分别保存父代和子代。Top
7 楼zzwu（未名）回复于 2005-01-03 23:27:19 得分 1
如果你对每点的计算是根据矩阵原来的值进行，而不是把每一点计算得到的新值立刻放到矩阵里，让下一点那么就采用如何次序不影响结果的。
Top
8 楼mxfeng（老子说:善战者不怒）回复于 2005-01-04 11:15:16 得分 0
。Top
9 楼BlueSky2008（懒惰是程序员的美德）回复于 2005-01-04 13:32:03 得分 1
就是酱紫的。这个程序我以前也做过，不是程序的问题。你要是有耐心，手工模拟一下也会是这个结果。这个系统一开始以一种近乎随机的方式演化，但在某一时刻，他进入了一个循环状态，此后就一直重复这个循环，显现出某种花纹。Top
10 楼Woodman007（卖女孩的小火柴）回复于 2005-01-05 13:55:45 得分 1
我看过更复杂的讨论，不过结论我不记得了，那篇文章的生物的生存规律比楼主的多了一条:
若一个个体周围八个相邻方格中有4个及4个以上邻居,则它们都因为食物不够而死亡。
多了这一条规律后，会演化成什么图案呢？Top
11 楼NowCan（城市浪人）回复于 2005-01-05 17:04:08 得分 1
加上这个规则后，一般会形成环和岛，并且会不断漂移。Top
12 楼fmbs（Plus++）回复于 2005-01-05 17:58:03 得分 1
如果考虑每时每刻的变化，这问题就纠缠不清了，这是时间上的问题。还有空间
也就是说一个元素的变化并不是只是它周围八个元素的变化所能确定的，同样，整个棋盘也只是一小部分而已，并不能说明一切，比如是，棋盘角上的元素又与什么来确定的呢？
我是学化学的，在考虑晶型结构是也考虑过这个问题。
变化应该有一定的周期
Top
13 楼NowCan（城市浪人）回复于 2005-01-05 18:33:27 得分 1
我当时做这个的时候是将棋盘左边和右边连接、上边和下边连接Top
14 楼jettylee（要学的还很多~~~）回复于 2005-01-05 21:00:57 得分 1
to Woodman007(司空无情) :
他所给出的条件是2到3个继续存活，也就是说4个及以上都死掉
我所做的程序没能做出斑马条，出现的是比较小的环
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define MAX 21
using namespace std;
int map[MAX][MAX]; //棋盘
int tmp[MAX][MAX]; //棋盘的缓存
int xmove[8]={1,0,-1,0,1,1,-1,-1};
int ymove[8]={0,1,0,-1,1,-1,1,-1};
int cal(int x, int y){
//计算周围八个点内的生物数
int ans=0;
for(int i=0; i<8; i++)
ans+=map[x+xmove[i]][y+ymove[i]];
return ans;
}
void solve(){
//一个周期 内的生存和死亡
int t;
for(int i=1; i<MAX; i++)
for(int j=1; j<MAX; j++)
{
t = cal(i,j);
if(t==3)
tmp[i][j]=1;
else if(t!=2)
tmp[i][j]=0;
}
memcpy(map, tmp, sizeof(map));
return;
}
void print(){
//输出
for(int i=1; i<MAX; i++){
for(int j=1; j<MAX; j++)
if(map[i][j])
cout<<"#";
else
cout<<" ";
cout<<endl;
}
}
int main()
{
int n,x,y;
srand(time(NULL));
while(cin>>n,n!=-1){
memset(map, 0, sizeof(map));
int tim=MAX*MAX/4;
while(tim--)
{
//开始的布局
do{
x=rand()%MAX;
y=rand()%MAX;
}while(map[x][y]==1);
map[x][y]=1;
}
while(n--){
solve();
}
print();
cout<<"========================================="<<endl;
}
return 0;
}
以下是我出现的图案（1000个周期）：
##
## #
# #
#
##
# #
## # ##
# # ##
# #
#
## ##
# # # #
## ## ##
##
# #
# # # #
# ## # # #
## # #Top
15 楼chenqiu1024（FutureBoy）回复于 2005-01-07 13:12:39 得分 0
我确实在编程时注意到了"各方格的变化是同时进行的"这句话,因此我是画在另一块区域上的,下一轮时再以上一轮输出的区域为输入区域,画在原先的输入区域上.可是还会出现这种问题,甚是不解,可能还有什么问题没考虑到.
大家试没试过如果长宽不同是什么样子?应该是差不多吧?
另外这个问题的确与哲学和目前前沿科学，什么自组织啥的很有关系。一个初始随机的状态，经过按某种规则的演化就能形成某种秩序，这大概就是“生命起源”吧。有人知道哪里有什么探讨生命、智能、意识这类深奥哲学问题的论坛吗？
Top
16 楼DeadWolf（三角小眼睛又邪又媚又笨又呆又奸又诈又色）回复于 2005-01-07 13:50:35 得分 1
有趣，做来玩玩看Top
17 楼NowCan（城市浪人）回复于 2005-01-07 16:53:04 得分 1
探讨生命、智能、意识这类深奥哲学问题的论坛，这类论坛的人气不行。Top
18 楼baryjim（吃饭－睡觉－打豆豆）回复于 2005-01-07 16:58:35 得分 1
NowCan(((((( ★ )))))) :
介绍一下吧，这个论坛以前人气很旺得，自从海星老版主走了后，就有点下落了Top
19 楼timgreen（tim）回复于 2005-01-07 18:58:55 得分 1
收藏
这游戏我也玩过Top
20 楼chenqiu1024（FutureBoy）回复于 2005-01-07 22:13:36 得分 0
什么论坛？地址是什么？Top
21 楼chenqiu1024（FutureBoy）回复于 2005-01-07 22:17:45 得分 0
咦？从上面这位老兄的结果看来，似乎也有某种“各向异性”的情况存在嘛！
好像单一的线段只有竖直方向的。Top
22 楼Kshape（C/C++初学者~~~~）回复于 2005-01-09 07:25:27 得分 1
有趣，做来玩玩看
Top
23 楼jingfeng198（没有昵称( ^_^ )）回复于 2005-01-09 12:08:52 得分 1
我也来看看先Top
24 楼sankt（宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒.）回复于 2005-01-16 20:48:02 得分 1
学习
Top
25 楼pallas2k（巨硬.not）回复于 2005-01-28 21:35:43 得分 1
跑题了，程序代码贴出来Top
26 楼happykevins（）回复于 2005-01-29 14:16:55 得分 1
mark~ 学习一下Top
27 楼llfcqqq（）回复于 2005-02-03 16:09:39 得分 1
生存规则已经确定，必然会导致一个稳定的结构来适应的。Top
28 楼moonranger（狂热的菜鸟）回复于 2005-02-07 18:07:06 得分 1
高！实在是高！！！！Top
