⟦c80aade71⟧

TextFile

#define	VERSION	"1.1"
#define	FORCED	2000L
#define	WIN	30000L
#define	SNUM	3

/* zogo: 4*4*4 4-in-a-row+gravitation */

long int z[10] = { 0L, FORCED, 100L, 10L, 1L, 0L, 9L, 90L, WIN, 0L };

int board[64];
int move[64],mvct;
char sym[] = ".oxOX@*" ;
int optd,first,noout,user;
extern int readmove(), cmove(), cmove1(), findmove();
int (*(strat[]))() = { &readmove, &cmove, &cmove1, &findmove };
int (*strat1)(), (*strat2)();

/* deliver a random value between 0 and k-1 */
int userand	= 1;

random(k){
register int r;
	if(!userand) return(0);
	r = rand();
	if(r<0) r = -r;
	r -= (r/k)*k;
	return(r);
}

domove(a,b,c,p) int a,b,c,p; {
register int i;
	i = 16*a + 4*b + c;
	move[mvct] = i;
	mvct++;
	board[i] = p+2;
	prbd();
	board[i] = p;
	return(four(a,b,c));
}

prbd(){
register int i,j,k;
	if(noout) return;
	printf("\n\n");
	for(i=3; i>=0; i--) prlin(i);
	printf("\n");
	printf("  aaaa  bbbb  cccc  dddd\n");
	printf("  1234  1234  1234  1234\n");
	printf("\n\n");
}

prlin(a) int a; {
register int i,j,k;
	for(i=0; i<4; i++){
		printf("  ");
		for(j=0; j<4; j++) putchar(sym[board[16*i + 4*j + a]]);
	}
	putchar('\n');
}

readmove(a) int a; {
register int i,j,k;
int c;
err1:
	printf("Your move: ");
	if(letter(c = getchar())) i = c - 'a'; else goto err;
	if(digit(c = getchar())) j = c - '1'; else goto err;
	if(getchar() != '\n') goto err;
	for(k=0; k<4; k++) if(board[16*i + 4*j + k] == 0) break;
	if(k == 4){
		printf("you cannot move there\n");
		goto err1;
	}
	if(domove(i,j,k,a)){
		noout = 0;
		printf("It seems you win\n");
		prbd();
		exit();
	}
	return;
err:
	if(c == '$' && (c = getchar()) == '%' && (c = getchar()) == '!'
		&& (c = getchar()) == '\n')
		execl("/bin/sh", "zogo", 0);
	while(c != '\n'){
		if(c == -1) error("End of input");
		c = getchar();
	}
	printf("strange symbol??\n");
	goto err1;
}

letter(c) char c; {
	return('a' <= c && c <= 'd');
}

digit(c) char c; {
	return('1' <= c && c <= '4');
}

lstat(a,b,c,da,db,dc,p) int a,b,c,da,db,dc,p; {
register int i,j,k;
int ct,tot[3];
	tot[0] = tot[1] = tot[2] = 0;
	i = a;
	j = b;
	k = c;
	for(ct = 0; ct < 4; ct++){
		tot[board[16*i + 4*j + k]]++;
		i += da;
		j += db;
		k += dc;
	}
	if(tot[p] == 4){	/* someone won - set ! marks */
		i = a; j = b; k = c;
		for(ct = 0; ct < 4; ct++){
			board[16*i + 4*j + k] += 4;
			i += da;
			j += db;
			k += dc;
		}
	}
	if(tot[1] && tot[2]) return(0);
	if(tot[p]) return(tot[p]);
	return(-tot[3-p]-1);
}

four(a,b,c) int a,b,c; {
register int i,j,k;
int p;
	p = board[16*a + 4*b + c];
	if(!p) error("four for empty field??");
	if(lstat(a,b,0,0,0,1,p) == 4) return(1);
	if(lstat(a,0,c,0,1,0,p) == 4) return(1);
	if(lstat(0,b,c,1,0,0,p) == 4) return(1);
	if(a == b && lstat(0,0,c,1,1,0,p) == 4) return(1);
	if(a == c && lstat(0,b,0,1,0,1,p) == 4) return(1);
	if(b == c && lstat(a,0,0,0,1,1,p) == 4) return(1);
	if(a+b == 3 && lstat(0,3,c,1,-1,0,p) == 4) return(1);
	if(a+c == 3 && lstat(3,b,0,-1,0,1,p) == 4) return(1);
	if(b+c == 3 && lstat(a,0,3,0,1,-1,p) == 4) return(1);
	if(a == c && b == c && lstat(0,0,0,1,1,1,p) == 4) return(1);
	if(a+c==3 && b == c && lstat(3,0,0,-1,1,1,p) == 4) return(1);
	if(a+b==3 && a == c && lstat(0,3,0,1,-1,1,p) == 4) return(1);
	if(a+c==3 && a == b && lstat(3,3,0,-1,-1,1,p) == 4) return(1);
	return(0);
}

long int cval(a,b,c,p) int a,b,c,p; {
register int i,j,k;
long int val;
	val = 0;
	val += z[5 + lstat(0,b,c,1,0,0,p)];
	val += z[5 + lstat(a,0,c,0,1,0,p)];
	val += z[5 + lstat(a,b,0,0,0,1,p)];
	if(a == b) val += z[5 + lstat(0,0,c,1,1,0,p)];
	if(a == c) val += z[5 + lstat(0,b,0,1,0,1,p)];
	if(b == c) val += z[5 + lstat(a,0,0,0,1,1,p)];
	if(a+b == 3) val += z[5 + lstat(0,3,c,1,-1,0,p)];
	if(a+c == 3) val += z[5 + lstat(3,b,0,-1,0,1,p)];
	if(b+c == 3) val += z[5 + lstat(a,0,3,0,1,-1,p)];
	if(a==c && b==c) val += z[5 + lstat(0,0,0,1,1,1,p)];
	if(a+c==3 && b==c) val += z[5 + lstat(3,0,0,-1,1,1,p)];
	if(a+b==3 && a==c) val += z[5 + lstat(0,3,0,1,-1,1,p)];
	if(a+c==3 && a==b) val += z[5 + lstat(3,3,0,-1,-1,1,p)];
	return(val);
}

cmove(a) int a; {
register int i,j,k;
int mi,mj,mk,mct;
long int max,v,w;
	max = -2L;
	for(i=0; i<4; i++) for(j=0; j<4; j++){
		for(k=0; k<4; k++) if(!board[16*i + 4*j + k]) break;
		if(k == 4) continue;
		v = cval(i,j,k,a);
		if(k < 3 && v < FORCED){	/* allowed ? */
			w = cval(i,j,k+1,3-a);
			if(w >= WIN) v = -1L;
			else if(w >= FORCED && k < 2){
				w = cval(i,j,k+2,a);
				if(w >= WIN) v = FORCED - 1L;
			}
		}
		if(v > max || (v == max && random(++mct) == 0)){
			if(v > max) mct = 1;
			max = v;
			mi = i;
			mj = j;
			mk = k;
		}
	}
	if(max == -2L) error("I cannot find a move");
	if(domove(mi,mj,mk,a)){
		sarcastic();
	}
	if(optd) printf("value of move: %D\n", max);
}

sarcastic(){
		noout = 0;
		printf("As was to be expected, I win\n");
		printf("You survived ");
		if(mvct < 32) printf("only ");
		printf("%d moves", mvct);
		if(mvct == 64) printf(" - but I got you in the end!");
		else if(mvct > 48) printf(" - not too bad\n");
		else if(mvct < 24) printf(" - you'd better try tictactoe\n");
		else putchar('\n');
		prbd();
		exit();
}

cmove1(a) int a; {
	z[4] = 5L;
	cmove(a);
	z[4] = 1L;
}

main(argc,argv) int argc; char **argv; {
register int sn,snum;
	sn = 0;
	init();
	while(argc > 1){
		argc--;
		argv++;
		if(**argv != '-'){	/* strategy numbers */
			if(++sn > 2) error("we have only 2 players");
			snum = atoi(*argv);
			if(snum < 0 || snum > SNUM)
				error("we dont have that strategy");
			if(sn == 1) strat1 = strat[snum];
			else strat2 = strat[snum];
			continue;
		}
	options:
		argv[0]++;
		switch(argv[0][0]){
		case 'a':	/* agressive */
			z[6] = 12L;
			z[7] = 120L;
			goto options;
		case 'd':	/* debug */
			optd++;
			goto options;
		case '1':
		case '2':
			if(first) error("selfcontradictory options");
			first = **argv - '0';
			goto options;
		case 'n':
			noout++;
			goto options;
		case '\0':
			continue;
		default:
			error("allowed options: -12adn");
		}
	}
	if(sn == 0){
		sn++;
		strat1 = strat[0];
	}
	if(strat1 == strat[0]) user |= 1;
	if(sn == 1){
		if(!user) strat2 = strat[0];
		else strat2 = strat[SNUM];
	}
	if(strat2 == strat[0]) user |= 2;

	if(!noout)printf("\t\t    Zogo %s\n", VERSION);
	if(!noout)printf("** four-in-a-row on a 4*4*4 cube with gravity **\n");

	if(!first && (user==0 || user==3)) first = 1; else
	if(!first){
		if(random(3) != 0){
			first = user;
			printf("You start -- good luck!\n");
		} else {
			first = 3-user;
			printf("I'll start this time\n");
		}
	}
	if(first & user){
		prbd();
	}
	while(mvct < 64){
		if((mvct+first)&1) (*strat1)(1); else (*strat2)(2);
	}
	printf("A draw -- well played !!\n\n");
	if(noout){
		noout = 0;
		prbd();
	}
}

struct px	{ struct lx *(ll[8]); int cont,win,ghost; } pts[64];
struct lx	{ struct px *(pp[4]); int dist,fill[5]; } lines[76];
#define	blocked	fill[0]

init(){
register int i,j,k;
int tvec[2];
	time(tvec);
	srand(tvec[1]);
	for(i=0; i<64; i++) pts[i].cont = pts[i].win = pts[i].ghost =  0;
	for(i=0; i<76; i++){
		lines[i].dist = 0;
		for(j=0; j<5; j++) lines[i].fill[j] = 0;
	}
	for(i=0; i<4; i++) for(j=0; j<4; j++) for(k=0; k<4; k++){
		/* verticals first */
		incid(i,j,k,0 + 4*i+j,k);
		incid(i,j,k,16 + 4*i+k,j);
		incid(i,j,k,32 + 4*j+k,i);
	}
	for(i=0; i<4; i++) for(j=0; j<4; j++){
		incid(i,j,j,48 + i,j);
		incid(j,i,j,52 + i,j);
		incid(j,j,i,56 + i,j);
		incid(i,j,3-j,60 + i,j);
		incid(3-j,i,j,64 + i,j);
		incid(j,3-j,i,68 + i,j);
	}
	for(i=0; i<4; i++){
		incid(i,i,i,72,i);
		incid(i,i,3-i,73,i);
		incid(i,3-i,i,74,i);
		incid(3-i,i,i,75,i);
	}
	/* close ll lists with 0 */
	for(i=0; i<64; i++){
		if(pts[i].cont >= 8) error("8 directions through a point?");
		pts[i].ll[ pts[i].cont ] = 0;
		pts[i].cont = 0;
	}
	/* correct distances for vertical lines */
	for(i=0; i<16; i++) lines[i].dist = 4;
}

incid(i,j,k,l,x) int i,j,k,l,x; {
register int a;
register struct px *ppt;
register struct lx *lpt;
	a = 16*i + 4*j + k;
	ppt = &pts[a];
	lpt = &lines[l];
	lpt->pp[x] = ppt;
	lpt->dist += (k+1);
	ppt->ll[ ppt->cont++ ] = lpt;
}

xeqmove(pos,a) int pos,a; {
register struct px	*ppt;
register struct lx	*lpt;
register int d;
int l,e,g;
	ppt = &pts[pos];
	ppt->cont = a;
	g = ppt->ghost;
	ppt->ghost = 0;
	for(d = 3 - (pos%4); d >= 1; d--){
		l = 1;		/* skip vertical */
		while(lpt = (ppt+d)->ll[l++]) lpt->dist--;
	}
	l = 0;
	while(lpt = ppt->ll[l++]){
		lpt->dist--;
		if(g & 1) lpt->fill[3]--;
		if(g & 2) lpt->fill[4]--;
		e = ++(lpt->fill[a]);
		if(lpt->fill[3-a]) lpt->blocked = 3;
		if(e == 4) return(1);		/* someone won */
		if(e == 3 && !lpt->fill[3-a]){
			for(d=0; d<4; d++) if((lpt->pp[d])->cont == 0) break;
			if(d == 4) error("where is the empty field?");
			setwin(lpt->pp[d], a);
		}
	}
	return(0);
}

setwin(ppt,a) struct px *ppt; int a; {
register int k,l;
register struct lx *lpt;
	if((ppt->win |= a) == 3){
		/* block all lines through higher points */
		for(k = (ppt-pts)%4 + 1; k < 4; k++){
			l = 1;
			while(lpt = (ppt+k)->ll[l++]) lpt->blocked = 3;
		}
	}
	l = 0;
	while(lpt = ppt->ll[l++]) lpt->blocked |= a;
	k = (ppt-pts)%4;
	if(k > 0 && !(ppt-1)->cont) setghost(ppt-1, a);
	if(k < 3) setghost(ppt+1, a);
	if(optd) printf("setwin(%d,%d)\n", ppt-pts, a);
}

setghost(ppt,a) struct px *ppt; int a; {
register int k,l;
register struct lx *lpt;
	if(ppt->ghost & a) return;
	ppt->ghost |= a;
	l = 0;
	while(lpt = ppt->ll[l++]) lpt->fill[a+2]++;
	if(optd) printf("setghost(%d,%d)\n", ppt-pts, a);
}

#define	WIN2	30000
#define	FORC2	25000
int zz[11] = { 10, 12, 15, 20, 30, 100, 200, 400, 800, 1600, 3200 };

vmove(pos,a) int pos,a; {
register int l;
register struct px	*ppt;
register struct lx	*lpt;
int v,v1;
	ppt = &pts[pos];
	if(ppt->cont) error("vmove considering nonempty field??");
	if(ppt->win & a) return(WIN2);
	if(ppt->win & (3-a)) return(FORC2);
	if(pos%4 != 3 && ((ppt+1)->win & (3-a))) return(-1); /* losing move */
	if(pos%4 < 2 && ((ppt+1)->win & a) && ((ppt+2)->win & a))
		return(FORC2 - 1);		/* win within 2 moves */
	v = vmsum(ppt, a);
	if(pos%4 != 3){
		v1 = vmsum(ppt+1, 3-a);
		if(v1 > 2*v) v = 0;
	}
	return(v);
}

vmsum(ppt, a) struct px *ppt; int a; {
register int v1,l;
register struct lx *lpt;
int v;
	v = 0;
	l = 0;
	while(lpt = ppt->ll[l++]){
		v1 = 0;
		if(lpt->fill[a]){
			if(!(lpt->blocked & a))
				v1 = 3*lpt->fill[a] + 2*lpt->fill[a+2];
		} else if(lpt->fill[3-a]){
			if(!(lpt->blocked & (3-a)))
				v1 = 3*lpt->fill[3-a] + 2*lpt->fill[5-a];
		} else {
			v1 = (lpt->fill[3] + lpt->fill[4]);
		}
		if(v1<0 || v1>10) error("strange v1");
		v1 = zz[v1];
		v1 -= (v1 * lpt->dist)/32;
		v += v1;
	}
	return(v);
}

findmove(a) int a; {
register int i,j,k;
int v,vmax,vct,imax;
	if(strat1 != strat2 && mvct && xeqmove(move[mvct-1], 3-a))
		error("my opponent seems to have won?");
	vmax = -2;
	for(i=0; i<16; i++){
		k = lines[i].dist;
		if(k==0) continue;
		v = vmove(4*i + (4-k), a);
		if(optd) printf("%d: %d / ", i, v);
		if(v > vmax || (v == vmax && rand(++vct) == 0)){
			if(v > vmax) vct = 1;
			vmax = v;
			imax = 4*i + (4-k);
		}
	}
	if(optd) printf("max = %d\n", vmax);
	if(vmax == -2) error("findmove fails");
	i = imax/16;  j = (imax%16)/4;  k = imax%4;
	if(domove(i,j,k,a)){
		if(user) sarcastic();
		printf("The new strategy won after %d moves\n", mvct);
		noout = 0;
		prbd();
		exit();
	}
	if(xeqmove(imax,a)) error("impossible");
}

error(s) char *s; {
	printf("Fatal error: %s\n", s);
	exit(1);
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦c80aade71⟧ TextFile

Derivation

TextFile
