对对碰自动连续消除次数的期望

winxos · 发表于 2009-11-26 14:43:57

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

博客上有人问了一个类似的问题，觉得没有什么好的思路。

题目：
对于n x n大小的游戏地图，游戏基本元素有m个，问正常消除一次导致后续自动连续消除的次数C期望是多大？
解释：
游戏基本元素可以简单理解为游戏中有多少种不同的头像，为了简便分析可以先考虑在坐标i,j处横向消除3个头像导致自动连消的次数。
我的一点思路：假设横向消除3个的话，必然会导致消除行上方整体3列落下，然后消除发生的情况肯定是由于这个下落区域跟不动区域边界移动造成，消除点肯定发生在边界处，假设新补充进来的头像都是等概率均布，依次分析各个接触点的概率。
不过感觉好难。
我做过模拟，对于40x40的地图，如果只有6个元素的话，自动连消基本停不下来，然而对于20x20的地图，一般连消也就是几步，大家能否找到C和m,n的大致关系？
附：对对碰消除规则
二．概述

游戏在 8 × 8 格子的游戏池中进行。每个格子中有一个动物头像。鼠标连续选中两个相邻的头像，它们的位置会互换，互换后如果横排或竖排有 3 个以上相同的头像，则可以消去该头像，并得分。

三• 基本规则

交换
玩家选中相邻（横、竖）的两个头像，则这两个头像的位置发生互换，如果互换成功则消去头像，否则取消位置交换。

消去
玩家选择两个头像进行位置互换，互换后如果横排或竖排有 3 个以上相同的头像，则消去这几个相同的头像，如果互换后没有可以消去的头像，则选中的两个头像换回原来的位置。消去后的空格由上面的头像掉下来补齐。每次消去头像玩家都能得到一定的分数。

连锁
玩家消去头像后，上面的头像掉下来补充空格。如果这时游戏池中有连续摆放（横、竖）的 3 个或 3 个以上相同的头像，则可以消去这些头像，这就是一次连锁。空格被新的头像填充，又可以进行下一次连锁。每次连锁会有加分。

KeyTo9_Fans · 发表于 2009-11-26 15:11:38

我经常玩这个游戏，也曾经思考过自动连消与避免无路可走的问题。

但一直没有把这些现象量化，作为一道题目提出来。

感谢楼主给出了清晰的问题描述和合理的参数设置。

我有空仔细研究研究。

056254628 · 发表于 2009-11-26 17:49:56

对于不同的游戏地图，得出的期望值C不一定相同。
如果地图不确定，首先要确定一共用多少种地图？（而计算n*n一共有多少种地图，又是一个不容易求出的问题），每种地图出现的概率又各是多少？（每幅地图出现的概率跟游戏程序的设计有关）
设每幅地图出现的概率为P(x)，该幅地图的C值为C(x)
那么总的期望值C=∑ P(x)*C(x)
-----------------------------------------------------------------------------------
为了便于分析，可以假设所有的P(x)都相同。
但是如果让我来设计该游戏，为了简化，我会让每个格子随机设为一个元素，然后利用规则进行自动消除，消除后稳定的状态作为一个地图。所以如果采取这种设计方法，每张地图的发生概率不会都是相同的。
-----------------------------------------------------------------
所以为了研究该问题，楼主还要确定地图产生的方法，以便确定每种地图发生的概率。只有统一地图产生的方法，才可能有相同的结论。
如果楼主只研究某种地图，那么还要确定是哪种地图。

winxos · 发表于 2009-11-27 07:59:24

3# 056254628
我忘了说明了，
这里的地图说的是n x n的正方形的地图，
初始情况地图里面的元素都是随机的，
然后要分析两种情况，
①就是所有元素都随机的情况下，自动连消期望多大？
②当已经没有自动连消时，交换两个元素之后产生的自动连消期望多大？
个人认为情况①的期望肯定要比期望②大好多。

KeyTo9_Fans · 发表于 2010-1-3 23:30:11

显然地，以下两种情况不需要讨论：

①当n≤2时，C=0；

②当n≥3且m=1时，C=+∞；

对于其他情况，C为有限大的正数。

其中最简单的情况是n=3，m=2，有512种状态。

根据移动规则可以得到各种状态之间的转移规律。

于是得到一个512元1次方程组：

解之，得：

所以对于问题①，C=

-1=1.92936482260326=17891/9273

问题②还不够清晰：如果有多种可行的交换方案应该交换哪两个？

northwolves · 发表于 2010-1-3 23:39:46

显然地，以下两种情况不需要讨论：

①当n≤2时，C=0；

②当n≥3且m=1时，C=+∞；

对于其他情况，C为有限大的正数。

其中最简单的情况是n=3，m=2，有512种状态。

根据移动规则可以得到各种状态之间的转 ...
KeyTo9_Fans 发表于 2010-1-3 23:30

怎么这样强!
请教这是个什么软件做的效果?

KeyTo9_Fans · 发表于 2010-1-3 23:46:13

是C++代码，才刚把图片熬出锅，还是热的，就放上来了……

#include<cstdio>
#include<memory>
char hd[54]={66,77,38,106,0,0,0,0,0,0,54,0,0,0,40,0,0,0,0,8,0,0,0,6,
0,0,1,0,24,0,0,0,0,0,-16,105,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
char nm[10][7][4]={
0,1,1,0,
1,0,0,1,
1,0,0,1,
1,0,0,1,
1,0,0,1,
1,0,0,1,
0,1,1,0,
0,0,1,0,
0,1,1,0,
0,0,1,0,
0,0,1,0,
0,0,1,0,
0,0,1,0,
0,0,1,0,
0,1,1,0,
1,0,0,1,
0,0,0,1,
0,0,1,0,
0,1,0,0,
1,0,0,0,
1,1,1,1,
0,1,1,0,
1,0,0,1,
0,0,0,1,
0,1,1,0,
0,0,0,1,
1,0,0,1,
0,1,1,0,
0,0,1,0,
0,1,1,0,
1,0,1,0,
1,0,1,0,
1,1,1,1,
0,0,1,0,
0,0,1,0,
1,1,1,1,
1,0,0,0,
1,1,1,0,
0,0,0,1,
0,0,0,1,
1,0,0,1,
0,1,1,0,
0,1,1,0,
1,0,0,1,
1,0,0,0,
1,1,1,0,
1,0,0,1,
1,0,0,1,
0,1,1,0,
1,1,1,1,
0,0,0,1,
0,0,1,0,
0,0,1,0,
0,1,0,0,
0,1,0,0,
0,1,0,0,
0,1,1,0,
1,0,0,1,
1,0,0,1,
0,1,1,0,
1,0,0,1,
1,0,0,1,
0,1,1,0,
0,1,1,0,
1,0,0,1,
1,0,0,1,
0,1,1,1,
0,0,0,1,
1,0,0,1,
0,1,1,0
};
char R[12000][600],G[12000][600],B[12000][600];
int g,h,i,j,k,l,m,ln,c[3][3];
double a[512][513],b[512][513],d;
void pm(int p,int x,int y)
{
int i,j,q[3][3];
for(i=2;i>=0;i--)
for(j=2;j>=0;j--)
{
q[i][j]=p%2;
p/=2;
}
for(i=0;i<10;i++)
for(j=0;j<10;j++)
if(i%3&&j%3)
{
B[x+i][y+j]=0;
if(q[i/3][j/3])G[x+i][y+j]=0;
else R[x+i][y+j]=0;
}
else
{
R[x+i][y+j]=0;
G[x+i][y+j]=0;
B[x+i][y+j]=0;
}
}
void pn(int p,int x,int y)
{
int i,j;
for(i=0;i<7;i++)
for(j=0;j<4;j++)
if(nm[p][i][j])
{
R[x+i][y+j]=0;
G[x+i][y+j]=0;
B[x+i][y+j]=0;
}
}
void pj(int x,int y)
{
R[x][y+1]=0;
G[x][y+1]=0;
B[x][y+1]=0;
R[x+1][y]=0;
G[x+1][y]=0;
B[x+1][y]=0;
R[x+1][y+1]=0;
G[x+1][y+1]=0;
B[x+1][y+1]=0;
R[x+1][y+2]=0;
G[x+1][y+2]=0;
B[x+1][y+2]=0;
R[x+2][y+1]=0;
G[x+2][y+1]=0;
B[x+2][y+1]=0;
}
void pd(int x,int y)
{
int i,j;
for(i=0;i<4;i+=2)
for(j=0;j<3;j++)
{
R[x+i][y+j]=0;
G[x+i][y+j]=0;
B[x+i][y+j]=0;
}
}
int main()
{
memset(R,-1,sizeof(R));
memset(G,-1,sizeof(G));
memset(B,-1,sizeof(B));
FILE *f=fopen("512eqs.bmp","wb");
hd[18]=88;
hd[19]=2;
hd[22]=-32;
hd[23]=46;
for(i=0;i<54;i++)
fprintf(f,"%c",hd[i]);
ln=1;
for(h=0;h<512;h++)
{
pm(h,ln,16);
pd(ln+4,27);
g=0;
if((h&7)==7||(h&7)==0)g|=7;
if((h&56)==56||(h&56)==0)g|=56;
if((h&448)==448||(h&448)==0)g|=448;
if((h&73)==73||(h&73)==0)g|=73;
if((h&146)==146||(h&146)==0)g|=146;
if((h&292)==292||(h&292)==0)g|=292;
if(!g)
{
a[h][h]=1;
pn(0,ln+2,31);
ln+=12;
}
else
{
k=256;
m=1;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
c[i][j]=0;
if(h&k)c[i][j]=1;
if(g&k)
{
c[i][j]=-1;
m+=m;
}
k/=2;
}
a[h][h]=m;
a[h][512]=m;
if(m<9)pn(8,ln+2,11);
else
if(m<99)
{
pn(m/10,ln+2,6);
pn(m%10,ln+2,11);
}
else
{
pn(m/100,ln+2,1);
pn(m/10%10,ln+2,6);
pn(m%10,ln+2,11);
}
for(j=0;j<3;j++)
{
k=2;
for(i=2;i>=0;i--)
if(c[i][j]>=0)c[k--][j]=c[i][j];
for(;k>=0;k--)c[k][j]=-1;
}
k=256;
g=0;
l=0;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(c[i][j]<0)g|=k;
if(c[i][j]>0)l|=k;
k/=2;
}
j=-1;
for(i=0;i<512;i++)
if((i&g)==i)
{
a[h][i|l]-=1;
if(j>=0)pj(ln+4,j*15+27);
else j=0;
pm(i|l,ln,j*15+31);
j++;
if(j>37)
{
j=0;
ln+=12;
}
}
pj(ln+4,j*15+27);
if(m<9)pn(8,ln+2,j*15+31);
else
if(m<99)
{
pn(m/10,ln+2,j*15+31);
pn(m%10,ln+2,j*15+36);
}
else
{
pn(m/100,ln+2,j*15+31);
pn(m/10%10,ln+2,j*15+36);
pn(m%10,ln+2,j*15+41);
}
ln+=12;
}
}
for(i=11999;i>=0;i--)
for(j=0;j<600;j++)
fprintf(f,"%c%c%c",B[i][j],G[i][j],R[i][j]);
fclose(f);
memcpy(b,a,sizeof(a));
for(i=0;i<512;i++)
for(j=i+1;j<512;j++)
{
for(k=i+1;k<513;k++)
a[j][k]-=a[i][k]*a[j][i]/a[i][i];
a[j][i]=0;
}
for(i=511;i>=0;i--)
{
for(j=i+1;j<512;j++)
{
a[i][512]-=a[j][512]*a[i][j];
a[i][j]=0;
}
a[i][512]/=a[i][i];
a[i][i]=1;
}
for(i=0;i<512;i++)
{
printf("%d: %.16lf ",i,a[i][512]);
d=0;
for(j=0;j<512;j++)
d+=a[j][512]*b[i][j];
printf("%lf %lf\n",d,b[i][512]);
}
f=fopen("512sols.bmp","wb");
memset(R,-1,sizeof(R));
memset(G,-1,sizeof(G));
memset(B,-1,sizeof(B));
for(i=0;i<54;i++)
fprintf(f,"%c",hd[i]);
ln=1;
for(h=0;h<512;h++)
{
pm(h,ln,1);
pd(ln+4,12);
d=a[h][512];
pn(int(d),ln+2,16);
R[ln+8][21]=0;
G[ln+8][21]=0;
B[ln+8][21]=0;
for(j=23;j<103;j+=5)
{
d=(d-int(d))*10;
pn(int(d),ln+2,j);
}
ln+=12;
}
for(i=11999;i>=0;i--)
for(j=0;j<600;j++)
fprintf(f,"%c%c%c",B[i][j],G[i][j],R[i][j]);
fclose(f);
return 0;
}

复制代码

winxos · 发表于 2010-1-4 14:21:59

效果太好了，假期我一定好好看一下代码

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 对对碰自动连续消除次数的期望

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分

评分

评分