2048AI

2048.cpp

#include<cstdio>
#include<algorithm>
#include<vector>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define rng(a) a.begin(),a.end()
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<P> VP;

const int SZ = 4, SZ2 = SZ*SZ;
const int TRYT = 1000;

const int INF = 1000010000, BIG = 1000000;
const int dv[] = {-1,-4,1,4}; //<^>v
const char vtos[4][6] = {"LEFT","UP","RIGHT","DOWN"};

//  0  1  2  3
//  4  5  6  7
//  8  9 10 11
// 12 13 14 15

vi d, emp(SZ2,0);
int score;


int move(vi &a, int v);

inline bool add(vi &a){
	vi p;
	rep(i,SZ2) if(!a[i]) p.pb(i);
	if(!sz(p)) return false;
	a[p[rand()%sz(p)]] = (rand()%10/9+1)<<1;
	return true;
}

inline void print(vi &a){
	printf("Score : %d\n",score);
	rep(y,SZ)rep(x,SZ){
		int val = a[y*SZ+x];
		if(val){
			if(val < 0) printf("\x1b[47m\x1b[30m");
			if(val == 2) printf("\x1b[32m");
			if(val == 4) printf("\x1b[36m");
			if(val == 8) printf("\x1b[34m");
			if(val == 16) printf("\x1b[35m");
			if(val == 32) printf("\x1b[31m");
			if(val == 64) printf("\x1b[33m");
			if(val == 128) printf("\x1b[43m");
			if(val == 256) printf("\x1b[41m");
			if(val == 512) printf("\x1b[45m");
			if(val == 1024) printf("\x1b[44m");
			if(val == 2048) printf("\x1b[46m");
			if(val == 4096) printf("\x1b[42m");
			printf("%5d",abs(val));
			printf("\x1b[0m");
		} else printf("    -");
		printf("%c",x==SZ-1?'\n':' ');
	}
	rep(i,30)puts("");
}


int sim(vi &a);

int eval(int v, int trys=200){
	trys = max(trys,100);
	vi vals, moved = d;
	int base = move(moved, v);
	if(base == -1) return 0;
	base = !!base;
	rep(tryi,trys){
		vi a = moved;
		vals.pb(base+sim(a));
	}
	sort(rng(vals));
	int sum = 0;
	for(int i = 0; i < trys; i++) sum += vals[i];
	return sum;
}

int main(int args, char** argv){
	int seed = 114514;
	if(args == 2) seed = atoi(argv[1]);
	srand(seed);
	d = emp; rep(i,2) add(d);
	print(d);
	
	while(1){
		P best = P(-1,-1);
		rep(v,4) best = max(best, P(eval(v),v));
		if(best.se != -1){
			score += move(d, best.se);
			printf("Move : %s\n", vtos[best.se]);
		}
		vi pred = d;
		if(!add(d)) break;
		rep(i,SZ2) if(d[i] != pred[i]) pred[i] = -d[i];
		print(pred);
	}
	printf("\nLast score : %d\n",score);
	
	return 0;
}


int sim(vi &a){
	int sum = 0;
	vi vl(4); rep(i,4) vl[i] = i;
	while(1){
		if(!add(a)) break;
		random_shuffle(rng(vl));
		rep(i,4){
			int res = move(a, vl[i]);
			//if(res == -1) continue;
			sum += res;
		}
	}
	return sum;
}



int move(vi &a, int v){
	int res = 0;
	int l[SZ], ls, as;
	vi prea = a;
	if(v == 0){
		rep(y,SZ){
			ls = 0;
			rep(x,SZ){
				int &cell = a[y*SZ+x];
				if(cell) l[ls++] = cell;
				cell = 0;
			}
			rep(i,ls-1) if(l[i] == l[i+1]) l[i] *= 2, l[i+1] = 0, res += l[i];
			as = y*SZ;
			rep(i,ls) if(l[i]) a[as] = l[i], as++;
		}
	} else if(v == 1){
		rep(x,SZ){
			ls = 0;
			rep(y,SZ){
				int &cell = a[y*SZ+x];
				if(cell) l[ls++] = cell;
				cell = 0;
			}
			rep(i,ls-1) if(l[i] == l[i+1]) l[i] *= 2, l[i+1] = 0, res += l[i];
			as = x;
			rep(i,ls) if(l[i]) a[as] = l[i], as += SZ;
		}
	} else if(v == 2){
		rep(y,SZ){
			ls = 0;
			drep(x,SZ){
				int &cell = a[y*SZ+x];
				if(cell) l[ls++] = cell;
				cell = 0;
			}
			rep(i,ls-1) if(l[i] == l[i+1]) l[i] *= 2, l[i+1] = 0, res += l[i];
			as = y*SZ+3;
			rep(i,ls) if(l[i]) a[as] = l[i], as--;
		}
	} else if(v == 3){
		rep(x,SZ){
			ls = 0;
			drep(y,SZ){
				int &cell = a[y*SZ+x];
				if(cell) l[ls++] = cell;
				cell = 0;
			}
			rep(i,ls-1) if(l[i] == l[i+1]) l[i] *= 2, l[i+1] = 0, res += l[i];
			as = SZ*3+x;
			rep(i,ls) if(l[i]) a[as] = l[i], as -= SZ;
		}
	}
	return prea==a?-1:res;
}