bkg.c

操作系统SunOS 4.1.3版本的源码

#ifndef lint
static	char sccsid[] = "@(#)bkg.c 1.1 92/07/30 Copyr 1985 Sun Micro";
#endif

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc.
 */

/* modified version of /usr/games/backgammon for use with gammontool */

#include <stdio.h>
#include <sys/file.h>
#include "bkgcodes.h"

#define rnum(r)	(random()%r)
#define MIN(a,b) (((a)<(b)) ? (a) : (b))
#define D0	dice[0]
#define D1	dice[1]
#define swap	{D0 ^= D1; D1 ^= D0; D0 ^= D1; d0 = 1-d0;}

/*
 *
 * Some numerical conventions:
 *
 *	Arrays have white's value in [0], red in [1].
 *	Numeric values which are one color or the other use
 *	-1 for white, 1 for red.
 *	Hence, white will be negative values, red positive one.
 *	This makes a lot of sense since white is going in decending
 *	order around the board, and red is ascending.
 *
 */

static int	pnum;			/* color of player:
					-1 = white
					 1 = red
					 0 = both
					 2 = not yet init'ed */
       int	board[26];		/* board:  negative values are white,
				   positive are red */
static int	dice[2];		/* value of dice */
       int	mvlim;			/* 'move limit':  max. number of moves */
static int	mvl;			/* working copy of mvlim */
       int	p[5];			/* starting position of moves */
       int	g[5];			/* ending position of moves (goals) */
static int	h[4];			/* flag for each move if a man was hit */
       int	cturn;			/* whose turn it currently is:
					-1 = white
					 1 = red
					 0 = just quitted
					-2 = white just lost
					 2 = red just lost */
static int	d0;			/* flag if dice have been reversed from
				   original position */
static int	table[6][6];		/* odds table for possible rolls */
static int	gvalue;			/* value of game (64 max.) */
static int	dlast;			/* who doubled last (0 = neither) */
       int	bar;			/* position of bar for current player */
       int	home;			/* position of home for current player */
static int	off[2];			/* number of men off board */
       int	*offptr;		/* pointer to off for current player */
static int	*offopp;		/* pointer to off for opponent */
static int	in[2];			/* number of men in inner table */
       int	*inptr;			/* pointer to in for current player */
static int	*inopp;			/* pointer to in for opponent */

static int	ncin;			/* number of characters in cin */
static char	cin[100];		/* input line of current move
				   (used for reconstructing input after
				   a backspace) */

FILE *logfd = NULL;

bkg()
{
	setbuf(stdout, 0);
	init();				/* initialize board */

	pnum = 1;			/* set player colors */

	switch (getchar()) {		/* get first player */
	case HUMANFIRST:
		cturn = -1;
		break;
	case COMPUTERFIRST:
		cturn = 1;
		break;
	default:
		error("Bad first player sent by gammontool");
		break;
	}

	if (cturn == 1)  {		/* initialize according to first */
		home = 25;		/* player */
		bar = 0;
		inptr = &in[1];
		inopp = &in[0];
		offptr = &off[1];
		offopp = &off[0];
	} else  {
		home = 0;
		bar = 25;
		inptr = &in[0];
		inopp = &in[1];
		offptr = &off[0];
		offopp = &off[1];
	}

	if (logfd == NULL) {
		int fd = open("hitlog", O_TRUNC|O_WRONLY, 0666);

		if (fd >= 0) {
			logfd = fdopen(fd, "w");
		}
	}

	while (cturn == 1 || cturn == -1)  {	/* while nobody has won */
		if (cturn == pnum)  {		/* computer's turn */
			move(1);
						/* check for refused double */
			if (cturn == -2 || cturn == 2)
				break;
						/* check for winning move */
			if (*offopp == 15) {
				cturn *= -2;
				break;
			}
		} else {			/* player's turn */
						/* check for double */
			switch (getchar()) {
			case DOUBLEREQ:
				if (dlast == cturn || gvalue >= 64)
					error("Illegal double sent by gammontool");
				else
					dble();
				break;
			case NODOUBLE:
				break;
			default:
				error("Bad double status sent by gammontool");
				break;
			}
						/* check if he can move */
			switch (getchar()) {
			case CANMOVE:
				roll();
				if ((mvlim = movallow()) == 0) {
					error("Human can't move anywhere");
					nexturn();
				} else {
					getmove();
				}
				break;
			case CANTMOVE:
				nexturn();
				break;
			default:
				error("Bad move status sent by gammontool");
				break;
			}
		}
	} /* end while loop */

	quit();
}

/* send an error message to gammontool and quit */

error(str)
char *str;
{
	putchar(ERRMSG);
	puts(str);

	quit();
}

quit()
{
	putchar(QUIT);
	fflush(stdout);
	pause();	/* wait until we are killed */
	exit(0);
}

getmove()
{
	register int	i, c;

	c = 0;
	for (;;)  {
		i = checkmove(c);

		switch (i)  {
		case -1:
			if (movokay(mvlim)) {
				nexturn();
				if (*offopp == 15)
					cturn *= -2;
				return;
			}
			break;
		case -4:
			error("Not enough moves sent by gammontool");
			break;
		case 0:
			error("Too many moves sent by gammontool");
			break;
		case -3:
			error("Quit sent by gammontool");
			break;
		}
		c = -1;
	}
}

movokay(mv)
register int	mv;
{
	register int	i, m;

	if (d0)
		swap;

	for (i = 0; i < mv; i++)  {

		if (p[i] == g[i])  {
			error("Move to the same location sent by gammontool");
			return(0);
		}

		if (cturn*(g[i]-p[i]) < 0)  {
			error("Backwards move sent by gammontool");
			return(0);
		}

		if (abs(board[bar]) && p[i] != bar)  {
			error("Bar men not moved first by gammontool");
			return(0);
		}

		if (m = makmove(i))  {
			switch (m)  {

			case 1:
				error("Unrolled move sent by gammontool");
				break;

			case 2:
				error("Bad starting position sent by gammontool");
				break;

			case 3:
				error("Blocked destination sent by gammontool");
				break;

			case 4:
				error("Premature bearing off sent by gammontool");
				break;
			}
			return(0);
		}
	}
	return (1);
}

struct state	{
	char	ch;
	int	fcode;
	int	newst;
};

static struct state	atmata[] = {

	'R', 1, 0,	'?', 7, 0,	'Q', 0, -3,	'B', 8, 25,
	'9', 2, 25,	'8', 2, 25,	'7', 2, 25,	'6', 2, 25,
	'5', 2, 25,	'4', 2, 25,	'3', 2, 25,	'2', 2, 19,
	'1', 2, 15,	'0', 2, 25,	'.', 0, 0,	'9', 2, 25,
	'8', 2, 25,	'7', 2, 25,	'6', 2, 25,	'5', 2, 25,

	'4', 2, 25,	'3', 2, 25,	'2', 2, 25,	'1', 2, 25,
	'0', 2, 25,	'/', 0, 32,	'-', 0, 39,	'.', 0, 0,
	'/', 5, 32,	' ', 6, 3,	',', 6, 3,	'\n', 0, -1,
	'6', 3, 28,	'5', 3, 28,	'4', 3, 28,	'3', 3, 28,
	'2', 3, 28,	'1', 3, 28,	'.', 0, 0,	'H', 9, 61,

	'9', 4, 61,	'8', 4, 61,	'7', 4, 61,	'6', 4, 61,
	'5', 4, 61,	'4', 4, 61,	'3', 4, 61,	'2', 4, 53,
	'1', 4, 51,	'0', 4, 61,	'.', 0, 0,	'9', 4, 61,
	'8', 4, 61,	'7', 4, 61,	'6', 4, 61,	'5', 4, 61,
	'4', 4, 61,	'3', 4, 61,	'2', 4, 61,	'1', 4, 61,

	'0', 4, 61,	' ', 6, 3,	',', 6, 3,	'-', 5, 39,
	'\n', 0, -1,	'.', 0, 0
};

static
checkmove (ist)
int	ist;
{
	register int	j, n;
	register char	c;

domove:
	ist = mvl = ncin = 0;
	for (j = 0; j < 5; j++)
		p[j] = g[j] = -1;

dochar:
	c = getchar();

	n = dotable(c,ist);
	if (n >= 0)  {
		cin[ncin++] = c;
		ist = n;
		if (n)
			goto dochar;
		else
			goto domove;
	}

	if (n == -1 && mvl >= mvlim)
		return(0);
	if (n == -1 && mvl < mvlim-1)
		return(-4);

	if (n == -6)  {
		if (movokay(mvl+1))
			movback(mvl+1);
		ist = n = rsetbrd();
		goto dochar;
	}

	if (n != -5)
		return(n);
	error("Illegal character sent by gammontool");
	goto dochar;
}

dotable (c,i)
char		c;
register int	i;
{
	register int	a;
	int		test;

	test = (c == 'R');

	while ( (a = atmata[i].ch) != '.')  {
		if (a == c || (test && a == '\n'))  {
			switch  (atmata[i].fcode)  {

			case 1:
				error("Redisplay request sent by gammontool");
				break;

			case 2:
				if (p[mvl] == -1)
					p[mvl] = c-'0';
				else
					p[mvl] = p[mvl]*10+c-'0';
				break;

			case 3:
				if (g[mvl] != -1)  {
					if (mvl < mvlim)
						mvl++;
					p[mvl] = p[mvl-1];
				}
				g[mvl] = p[mvl]+cturn*(c-'0');
				if (g[mvl] < 0)
					g[mvl] = 0;
				if (g[mvl] > 25)
					g[mvl] = 25;
				break;

			case 4:
				if (g[mvl] == -1)
					g[mvl] = c-'0';
				else
					g[mvl] = g[mvl]*10+c-'0';
				break;

			case 5:
				if (mvl < mvlim)
					mvl++;
				p[mvl] = g[mvl-1];
				break;

			case 6:
				if (mvl < mvlim)
					mvl++;
				break;

			case 7:
				error("Help request sent by gammontool");
				break;

			case 8:
				p[mvl] = bar;
				break;

			case 9:
				g[mvl] = home;
			}

			if (!test || a != '\n')
				return (atmata[i].newst);
			else
				return (-6);
		}
		i++;
	}
	return (-5);
}

rsetbrd()
{
	register int	i, j, n;

	n = 0;
	mvl = 0;
	for (i = 0; i < 4; i++)
		p[i] = g[i] = -1;
	for (j = 0; j < ncin; j++)
		n = dotable(cin[j],n);
	return (n);
}

movallow()
{
	register int	i, m, iold;

	if (d0)
		swap;
	m = (D0 == D1 ? 4: 2);
	for (i = 0; i < 4; i++)
		p[i] = bar;
	i = iold = 0;
	while (i < m)  {
		if (*offptr == 15)
			break;
		h[i] = 0;
		if (board[bar])  {
			if (i == 1 || m == 4)
				g[i] = bar+cturn*D1;
			else
				g[i] = bar+cturn*D0;
			if (makmove(i))  {
				if (d0 || m == 4)
					break;
				swap;
				movback(i);
				if (i > iold)
					iold = i;
				for (i = 0; i < 4; i++)
					p[i] = bar;
				i = 0;
			} else
				i++;
			continue;
		}
		if ((p[i] += cturn) == home)  {
			if (i > iold)
				iold = i;
			if (m == 2 && i)  {
				movback(i);
				p[i--] = bar;
				if (p[i] != bar)
					continue;
				else
					break;
			}
			if (d0 || m == 4)
				break;
			swap;
			movback (i);
			for (i = 0; i < 4; i++)
				p[i] = bar;
			i = 0;
			continue;
		}
		if (i == 1 || m == 4)
			g[i] = p[i]+cturn*D1;
		else
			g[i] = p[i]+cturn*D0;
		if (g[i]*cturn > home)  {
			if (*offptr >= 0)
				g[i] = home;
			else
				continue;
		}
		if (board[p[i]]*cturn > 0 && makmove(i) == 0)
			i++;
	}
	movback (i);
	return(iold > i? iold: i);
}

struct BOARD  {				/* structure of game position */
	int	b_board[26];			/* board position */
	int	b_in[2];			/* men in */
	int	b_off[2];			/* men off */
	int	b_st[4], b_fn[4];		/* moves */

	struct BOARD	*b_next;		/* forward queue pointer */
};

struct BOARD *freeq = (struct BOARD *)-1;
struct BOARD *checkq = (struct BOARD *)-1;
struct BOARD *bsave();
struct BOARD *nextfree();

static int	cp[5];				/* candidate start position */
static int	cg[5];				/* candidate finish position */
       int	race;				/* game reduced to a race */

move(okay)		/* do the computer's move */
int	okay;				/* zero if first move */
{
	register int	i;		/* index */
	register int	l;		/* last man */

	if (!race) {
		for (i = 0; i < 26; i++)  {
			if (board[i] < 0)
				l = i;
		}
		for (i = 0; i < l; i++)  {
			if (board[i] > 0)
				break;
		}
		if (i == l)
			race = 1;
	}

	if (okay)  {
					/* see if comp should double */
		if (gvalue < 64 && dlast != cturn && dblgood())  {
			dble();			    /* double */
						    /* return if declined */
			if (cturn != 1 && cturn != -1)
				return;
		} else {
			putchar(NODOUBLE);
		}
		roll();
	}

	mvlim = movallow();		/* find out how many moves */
	if (logfd != NULL) {
		fprintf(logfd, "%d %d\n", D0, D1);
	}
	if (mvlim == 0) {
		if (logfd != NULL) {
			fprintf(logfd, "can't move\n");
		}
		putchar(CANTMOVE);
		nexturn();
		return;
	}

	for (i = 0; i < 4; i++)		/* initialize */
		cp[i] = cg[i] = 0;

	trymove(0,0);			/* strategize */
	pickmove();

	if (d0) swap;				/* fix dice */

	if (logfd) {
		fprintf(logfd, "picked ");
	}
	putchar(CANMOVE);
	for (i = 0; i < mvlim; i++)  {
		if (i > 0)
			putchar(',');
		p[i] = cp[i];
		if (p[i] == 0 || p[i] == 25)
			putchar('B');
		else
			printf("%d", p[i]);
		putchar('-');
		g[i] = cg[i];
		if (g[i] == 0 || g[i] == 25)
			putchar('H');
		else
			printf("%d", g[i]);
		makmove(i);
		if (logfd != NULL) {
			fprintf(logfd, "%d->%d ", p[i], g[i]);
		}
	}
	putchar('\n');
	if (logfd) {
		fprintf(logfd, "\n");
		fflush(logfd);
	}

	nexturn();			/* get ready for next turn */
}

trymove(mvnum, swapped)
register int	mvnum;			/* number of move (rel zero) */
int		swapped;		/* see if swapped also tested */
{
	register int	pos;			/* position on board */
	register int	rval;			/* value of roll */

		/* if recursed through all dice values, compare move */
	if (mvnum == mvlim)  {
		binsert (bsave());
		return;
	}

						/* make sure dice in always
						 * same order */
	if (d0 == swapped)
		swap;
						/* choose value for this move */
	rval = dice[mvnum != 0];

						/* find all legitimate moves */
	for (pos = bar; pos != home; pos += cturn)  {
						/* fix order of dice */
		if (d0 == swapped)
			swap;
						/* break if stuck on bar */
		if (board[bar] != 0 && pos != bar)
			break;
						/* on to next if not occupied */
		if (board[pos]*cturn <= 0)
			continue;
						/* set up arrays for move */
		p[mvnum] = pos;
		g[mvnum] = pos+rval*cturn;
		if (g[mvnum]*cturn >= home)  {
			if (*offptr < 0)
				break;
			g[mvnum] = home;
		}
						/* try to move */
		if (makmove (mvnum)) {
			continue;
		} else
			trymove (mvnum+1,2);
						/* undo move to try another */
		backone (mvnum);
	}

						/* swap dice and try again */
	if ((!swapped) && D0 != D1)
		trymove (0,1);
}

struct BOARD *
bsave()
{
	register int	i;		/* index */
	struct BOARD	*now;		/* current position */

	now = nextfree();		/* get free BOARD */

					/* store position */
	for (i = 0; i < 26; i++)
		now->b_board[i] = board[i];
	now->b_in[0] = in[0];
	now->b_in[1] = in[1];
	now->b_off[0] = off[0];
	now->b_off[1] = off[1];
	for (i = 0; i < mvlim; i++)  {
		now->b_st[i] = p[i];
		now->b_fn[i] = g[i];
	}
	return (now);
}

binsert(new)