ZJOI2014 2048

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('\n');

	for(int i=0;i<M;i++){

		if(!w[i]) printf("    -%c"," \n"[(i+1)%4 == 0]);

		else printf("%5d%c",w[i]," \n"[(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"," \n"[(i+1)%4 == 0]);

			else printf("%5d%c",w[i]," \n"[(i+1)%4 == 0]);

		putchar('\n');

	}

	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\n",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\n",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;

}

巴特西

ZJOI2014 2048

Description

Sol

Code

最新文章

热门文章