Description
提交答案题,写个2048 AI 告诉你随机数生成方式.
Sol
xjblg+A*.
首先我写了个模拟,2048.
然后自己YY就可以啦...各种乱搞...
因为随机数,一个最好的状态一定只由一种状态得到,但最初的状态可能转移到多个价值差不多的状态,需要多搜几个..
于是我用队列来卡队列大小...剩下的就是估价函数了.
写估价函数的时候一个蛇形递增的序列权值必然需要很高.
最大权值也有一定权值,因为毕竟要合起来,但是合起来又不一定是最优的,价值适当.
我自己还乱搞了几个,比如空格子个数,相邻相同数字的个数,这个多了可以一步全部合起来来获得更多的空格子.
然后把2048的大模拟封装成结构体写头文件里,表示一个状态.
最后就是跑了...32768应该都可以跑出来,而且比较快,开 O2 跑的更快.
某ISA还把数据加强了,要求跑出65534,我说这个也是可以的,不确定每个种子都能跑出来,不过大部分应该是可以跑出来的.
剩下的就是贴代码了...
Code
2048.cpp
#include<cstdio>
#include<conio.h>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int N = 4;
const int M = 16;
const int MUL = 8221;
int seq;
int w[M];
FILE *fout=fopen("log.out","w");
void initSeed(int seed){ seq = seed; }
int GetRand(){ return (seq = (seq * MUL) + (seq >> 16)) & 15; }
//1 w 2 s 3 a 4 d
int Read(char ch=getch()){
if(isascii(ch)){
switch(ch){
case 'w':case 'W':return 1;
case 's':case 'S':return 2;
case 'a':case 'A':return 3;
case 'd':case 'D':return 4;
}
}else{
ch=getch();
switch(ch){
case 72:return 1;
case 75:return 3;
case 77:return 4;
case 80:return 2;
}
}return -1;
}
void GetW(int x=GetRand()){ for(;w[x];x=GetRand());w[x]=2; }
void Up(int a[]){
int u[5],b[5];
for(int i=0,j,c,t;i<4;i++){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i;j<16;j+=4) if(a[j]) b[++c]=a[j],a[j]=0;
for(j=1;j<=c;j++) if(!u[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1;
for(j=1,t=i;j<=c;j++) if(!u[j]) a[t]=b[j],t+=4;
}
}
void Down(int a[]){
int u[5],b[5];
for(int i=0,j,c,t;i<4;i++){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i+12;j>=0;j-=4) if(a[j]) b[++c]=a[j],a[j]=0;
for(j=1;j<=c;j++) if(!u[j] && b[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1;
for(j=1,t=i+12;j<=c;j++) if(!u[j]) a[t]=b[j],t-=4;
}
}
void Left(int a[]){
int u[5],b[5];
for(int i=0,j,c,t;i<16;i+=4){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i;j<i+4;j++) if(a[j]) b[++c]=a[j],a[j]=0;
for(j=1;j<=c;j++) if(!u[j] && b[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1;
for(j=1,t=i;j<=c;j++) if(!u[j]) a[t]=b[j],t++;
}
}
void Right(int a[]){
int u[5],b[5];
for(int i=0,j,c,t;i<16;i+=4){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i+3;j>=i;j--) if(a[j]) b[++c]=a[j],a[j]=0;
for(j=1;j<=c;j++) if(!u[j] && b[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1;
for(j=1,t=i+3;j<=c;j++) if(!u[j]) a[t]=b[j],t--;
}
}
void Copy(int a[],int b[]){ for(int i=0;i<16;i++) b[i]=a[i]; }
int check(int a[],int b[]){ for(int i=0;i<16;i++) if(a[i]!=b[i]) return 1;return 0; }
void Out(){
system("cls");
for(int i=1;i<=8;i++) putchar('
');
for(int i=0;i<M;i++){
if(!w[i]) printf(" -%c","
"[(i+1)%4 == 0]);
else printf("%5d%c",w[i],"
"[(i+1)%4 == 0]);
}
}
int Over(){
int t[M];
Copy(w,t),Up(t);if(check(w,t)) return 0;
Copy(w,t),Down(t);if(check(w,t)) return 0;
Copy(w,t),Left(t);if(check(w,t)) return 0;
Copy(w,t),Right(t);if(check(w,t)) return 0;
return 1;
}
void Print(char c){ fprintf(fout,"%c",c); }
void Play(int x){
initSeed(x),GetW(),GetW(),Out();
int cp[M];
for(;;){
int od=Read(),f=0;
switch(od){
case 1:Copy(w,cp),Up(cp);if(check(w,cp)) Up(w),f=1,Print('U');break;
case 2:Copy(w,cp),Down(cp);if(check(w,cp)) Down(w),f=1,Print('D');break;
case 3:Copy(w,cp),Left(cp);if(check(w,cp)) Left(w),f=1,Print('L');break;
case 4:Copy(w,cp),Right(cp);if(check(w,cp)) Right(w),f=1,Print('R');break;
}
if(f) GetW();
if(!Over()) Out();
else{ puts("You lose!");return; }
}
}
int main(){
for(int x;;){
cin>>x;
Play(x);
}return 0;
}
_2048.h
#include<cstdio>
#include<conio.h>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
#define G(i,j) ((i-1)*4+j-1)
const int N = 4;
const int M = 16;
const int MUL = 8221;
const double SmoothVal = 17;
const double MonoVal = 100;
const double SpaceVal = 5;
const double MaxVal = 3;
struct S{
int seq,maxn,lst;double val;
int w[M];
//1 w 2 s 3 a 4 d
void initSeed(int seed){ seq = seed;memset(w,0,sizeof(w)); }
int GetRand(){ return (seq = (seq * MUL) + (seq >> 16)) & 15; }
void GetW(){ int x=GetRand();for(;w[x];x=GetRand());w[x]=2; }
void Up(int a[]){
int u[5],b[5];
for(int i=0,j,c,t;i<4;i++){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i;j<16;j+=4) if(a[j]) b[++c]=a[j],a[j]=0;
for(j=1;j<=c;j++) if(!u[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1;
for(j=1,t=i;j<=c;j++) if(!u[j]) a[t]=b[j],t+=4;
}
}
void Down(int a[]){
int u[5],b[5];
for(int i=0,j,c,t;i<4;i++){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i+12;j>=0;j-=4) if(a[j]) b[++c]=a[j],a[j]=0;
for(j=1;j<=c;j++) if(!u[j] && b[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1;
for(j=1,t=i+12;j<=c;j++) if(!u[j]) a[t]=b[j],t-=4;
}
}
void Left(int a[]){
int u[5],b[5];
for(int i=0,j,c,t;i<16;i+=4){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i;j<i+4;j++) if(a[j]) b[++c]=a[j],a[j]=0;
for(j=1;j<=c;j++) if(!u[j] && b[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1;
for(j=1,t=i;j<=c;j++) if(!u[j]) a[t]=b[j],t++;
}
}
void Right(int a[]){
int u[5],b[5];
for(int i=0,j,c,t;i<16;i+=4){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i+3;j>=i;j--) if(a[j]) b[++c]=a[j],a[j]=0;
for(j=1;j<=c;j++) if(!u[j] && b[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1;
for(j=1,t=i+3;j<=c;j++) if(!u[j]) a[t]=b[j],t--;
}
}
void Find(){
maxn=lst=0;
for(int i=0;i<M;i++) if(w[i]) lst++,maxn=max(w[i],maxn);
}
void Copy(int a[],int b[]){ for(int i=0;i<M;i++) b[i]=a[i]; }
int check(int a[],int b[]){ for(int i=0;i<M;i++) if(a[i]!=b[i]) return 1;return 0; }
int Over(){
int t[M];
Copy(w,t),Up(t);if(check(w,t)) return 0;
Copy(w,t),Down(t);if(check(w,t)) return 0;
Copy(w,t),Left(t);if(check(w,t)) return 0;
Copy(w,t),Right(t);if(check(w,t)) return 0;
return 1;
}
void Order(int x){
switch(x){
case 1:Up(w);break;
case 2:Down(w);break;
case 3:Left(w);break;
case 4:Right(w);break;
}
}
void Print(){
for(int i=0;i<M;i++)
if(!w[i]) printf(" -%c","
"[(i+1)%4 == 0]);
else printf("%5d%c",w[i],"
"[(i+1)%4 == 0]);
putchar('
');
}
int abs(int x){ return x<0?-x:x; }
int Smooth(){
int res=0x7fffffff,tmp=0;
int b1[]={ 0,1,2,3,7,6,5,4,8,9,10,11,15,14,13,12 };
int b2[]={ 3,2,1,0,4,5,6,7,11,10,9,8,12,13,14,15 };
int b3[]={ 12,13,14,15,11,10,9,8,4,5,6,7,3,2,1,0 };
int b4[]={ 15,14,13,12,8,9,10,11,7,6,5,4,0,1,2,3 };
int b5[]={ 0,4,8,12,13,9,5,1,2,6,10,14,15,11,7,3 };
int b6[]={ 12,8,4,0,1,5,9,13,14,10,6,2,3,7,11,15 };
int b7[]={ 3,7,11,15,14,10,6,2,1,5,9,13,12,8,4,0 };
int b8[]={ 15,11,7,3,2,6,10,14,13,9,5,1,0,4,8,12 };
for(int i=0;i<M-1;i++) if(w[b1[i]] && w[b1[i+1]]) tmp+=abs(w[b1[i]]-w[b1[i+1]]*2);
if(w[b1[0]] == maxn) tmp-=maxn;res=min(res,tmp),tmp=0;
for(int i=0;i<M-1;i++) if(w[b2[i]] && w[b2[i+1]]) tmp+=abs(w[b2[i]]-w[b2[i+1]]*2);
if(w[b2[0]] == maxn) tmp-=maxn;res=min(res,tmp),tmp=0;
for(int i=0;i<M-1;i++) if(w[b3[i]] && w[b3[i+1]]) tmp+=abs(w[b3[i]]-w[b3[i+1]]*2);
if(w[b3[0]] == maxn) tmp-=maxn;res=min(res,tmp),tmp=0;
for(int i=0;i<M-1;i++) if(w[b4[i]] && w[b4[i+1]]) tmp+=abs(w[b4[i]]-w[b4[i+1]]*2);
if(w[b4[0]] == maxn) tmp-=maxn;res=min(res,tmp),tmp=0;
for(int i=0;i<M-1;i++) if(w[b5[i]] && w[b5[i+1]]) tmp+=abs(w[b5[i]]-w[b5[i+1]]*2);
if(w[b5[0]] == maxn) tmp-=maxn;res=min(res,tmp),tmp=0;
for(int i=0;i<M-1;i++) if(w[b6[i]] && w[b6[i+1]]) tmp+=abs(w[b6[i]]-w[b6[i+1]]*2);
if(w[b6[0]] == maxn) tmp-=maxn;res=min(res,tmp),tmp=0;
for(int i=0;i<M-1;i++) if(w[b7[i]] && w[b7[i+1]]) tmp+=abs(w[b7[i]]-w[b7[i+1]]*2);
if(w[b7[0]] == maxn) tmp-=maxn;res=min(res,tmp),tmp=0;
for(int i=0;i<M-1;i++) if(w[b8[i]] && w[b8[i+1]]) tmp+=abs(w[b8[i]]-w[b8[i+1]]*2);
if(w[b8[0]] == maxn) tmp-=maxn;res=min(res,tmp),tmp=0;
return res;
// for(int i=1;i<=4;i++) for(int j=1;j<=3;j++) if(w[G(i,j)] && w[G(i,j+1)] && w[G(i,j)] > w[G(i,j+1)]) tmp+=w[G(i,j)]-w[G(i,j+1)]*2;
// res=min(res,tmp),tmp=0;
// for(int i=1;i<=4;i++) for(int j=1;j<=3;j++) if(w[G(i,j)] && w[G(i,j+1)] && w[G(i,j)] < w[G(i,j+1)]) tmp+=w[G(i,j+1)]-w[G(i,j)]*2;
// res=min(res,tmp),tmp=0;
// for(int j=1;j<=4;j++) for(int i=1;i<=3;i++) if(w[G(i,j)] && w[G(i+1,j)] && w[G(i,j)] > w[G(i+1,j)]) tmp+=w[G(i,j)]-w[G(i+1,j)]*2;
// res=min(res,tmp),tmp=0;
// for(int j=1;j<=4;j++) for(int i=1;i<=3;i++) if(w[G(i,j)] && w[G(i+1,j)] && w[G(i,j)] < w[G(i+1,j)]) tmp+=w[G(i+1,j)]-w[G(i,j)]*2;
// return min(res,tmp);
}
int Mono(){
int res=0,tmp=0;
for(int i=1;i<=4;i++) for(int j=1;j<=3;j++) if(w[G(i,j)] < w[G(i,j+1)]) tmp++;
for(int i=1;i<=4;i++) for(int j=1;j<=3;j++) if(w[G(i,j)] > w[G(i,j+1)]) tmp--;
if(tmp < 0) tmp*=-1;
for(int j=1;j<=4;j++) for(int i=1;i<=3;i++) if(w[G(i,j)] < w[G(i+1,j)]) res++;
for(int j=1;j<=4;j++) for(int i=1;i<=3;i++) if(w[G(i,j)] > w[G(i+1,j)]) res--;
if(res < 0) res*=-1;
return max(res,tmp);
}
int Space(){
int cnt=0;double r=0,h=0,sr=0,sh=0;
for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) if(!w[G(i,j)]) sr+=i,sh+=j,cnt++;
sr=sr/cnt,sh=sh/cnt;
for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) if(!w[G(i,j)]) r+=(sr-i)*(sr-i),h+=(sh-j)*(sh-j);
return (int)(r+h)*(16-lst);
}
void GetVal(){
val = 0;
val -= Smooth() * SmoothVal;
val += Mono() * MonoVal;
val -= Space() * SpaceVal;
val += maxn * MaxVal;
/* int u[5],b[5];
for(int i=0,j,c;i<4;i++){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i;j<16;j+=4) if(w[j]) b[++c]=w[j];
for(j=1;j<=c;j++) if(!u[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1,tmp+=b[j];
}
val=max(val,tmp),tmp=0;
for(int i=0,j,c;i<4;i++){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i+12;j>=0;j-=4) if(w[j]) b[++c]=w[j];
for(j=1;j<=c;j++) if(!u[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1,tmp+=b[j];
}
val=max(val,tmp),tmp=0;
for(int i=0,j,c;i<16;i+=4){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i;j<i+4;j++) if(w[j]) b[++c]=w[j];
for(j=1;j<=c;j++) if(!u[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1,tmp+=b[j];
}
val=max(val,tmp),tmp=0;
for(int i=0,j,c;i<16;i+=4){
memset(u,0,sizeof(u)),memset(b,0,sizeof(b));
for(c=0,j=i+3;j>=i;j--) if(w[j]) b[++c]=w[j];
for(j=1;j<=c;j++) if(!u[j]) if(b[j] == b[j+1]) b[j]+=b[j+1],u[j+1]=1,tmp+=b[j];
}*/
return;
}
};
main.cpp
#include "_2048.h"
#include<utility>
#include<vector>
#include<windows.h>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
#define mpr(a,b) make_pair(a,b)
const int Q = 2048;
queue<S> q;
vector<pair<int,int> > f;
int cnt;
void Out(int x){
stack<int> stk;
// cout<<x<<endl;
for(pair<int,int> y=f[x];;y=f[y.first]){
stk.push(y.second);
// cout<<y.second<<endl;
if(y.first == 0) break;
}
for(;!stk.empty();stk.pop()){
switch(stk.top()){
case 1:putchar('U');break;
case 2:putchar('D');break;
case 3:putchar('L');break;
case 4:putchar('R');break;
}
}
}
void BFS(S &a){
q.push(a);int tmp=0;
f.push_back(mpr(0,0));
for(S t,s[5];!q.empty();++tmp){
// Sleep(120);
t=q.front(),q.pop();
// t.Print();
if(t.Find(),t.maxn >= 60000){ Out(tmp);return; }
if(t.Over()) continue;
vector<pair<double,int> > A;
for(int i=1;i<=4;i++){
s[i].initSeed(t.seq);
s[i].Copy(t.w,s[i].w);
s[i].Order(i);
if(!s[i].check(s[i].w,t.w)){ continue; }
s[i].Find();
// if(s[i].maxn >= 60000){ Out(tmp);cout<<i<<endl;return; }
if(s[i].Over()) continue;
s[i].GetW();
if(s[i].Over()) continue;
s[i].GetVal();
A.push_back(mpr(s[i].val,i));
// s[i].Print();
// q.push(s[i]);
// f.push_back(mpr(tmp,i));
}
sort(A.begin(),A.end());
for(int i=A.size()-1;i>=0 && q.size()<Q && i+3>A.size();i--){
q.push(s[A[i].second]);
// s[A[i].second].Print(),printf("%lf
",s[A[i].second].val);
f.push_back(mpr(tmp,A[i].second));
}
// cout<<"***********"<<endl;
// for(int i=A.size()-1;i>=0;i--) s[A[i].second].Print(),printf("%lf
",s[A[i].second].val);
// cout<<"***********"<<endl;
}
}
int main(){
freopen("204820.out","w",stdout);
S fff;
fff.initSeed(20);
fff.GetW(),fff.GetW();
// fff.Print();
BFS(fff);
return 0;
}