bkg.c

操作系统SunOS 4.1.3版本的源码

struct BOARD	*new;					/* item to insert */
{
	register struct BOARD	*p = checkq;		/* queue pointer */
	register int		result;			/* comparison result */

	if (p == (struct BOARD *)-1)  {			/* check if queue empty */
		checkq = p = new;
		p->b_next = (struct BOARD *)-1;
		return;
	}

	result = bcomp(new,p);			/* compare to first element */
	if (result < 0)  {				/* insert in front */
		new->b_next = p;
		checkq = new;
		return;
	}
	if (result == 0)  {				/* duplicate entry */
		/*mvcheck(p,new);*/
		makefree(new);
		return;
	}

	while (p->b_next != (struct BOARD *)-1)  {	/* traverse queue */
		result = bcomp(new,p->b_next);
		if (result < 0)  {			/* found place */
			new->b_next = p->b_next;
			p->b_next = new;
			return;
		}
		if (result == 0)  {			/* duplicate entry */
			/*mvcheck(p->b_next,new);*/
			makefree(new);
			return;
		}
		p = p->b_next;
	}
						/* place at end of queue */
	p->b_next = new;
	new->b_next = (struct BOARD *)-1;
}

bcomp(a,b)
struct BOARD	*a;
struct BOARD	*b;
{
	register int	*aloc = a->b_board;	/* pointer to board a */
	register int	*bloc = b->b_board;	/* pointer to board b */

	for (aloc = a->b_board, bloc = b->b_board;
	     aloc < &a->b_board[26];
	     aloc++, bloc++)  {
		if (*aloc-*bloc) {
			return (*aloc-*bloc);		/* found inequality */
		}
	}
	return (0);				/* same position */
}

mvcheck(incumbent,candidate)
register struct BOARD 	*incumbent;
register struct BOARD 	*candidate;
{
	register int	i;
	register int	result;

	for (i = 0; i < mvlim; i++)  {
		result = cturn*(candidate->b_st[i]-incumbent->b_st[i]);
		if (result > 0)
			return;
		if (result < 0)
			break;
	}
	if (i == mvlim)
		return;
	for (i = 0; i < mvlim; i++)  {
		incumbent->b_st[i] = candidate->b_st[i];
		incumbent->b_fn[i] = candidate->b_fn[i];
	}
}

makefree(dead)
struct BOARD	*dead;			/* dead position */
{
	dead->b_next = freeq;			/* add to freeq */
	freeq = dead;
}

struct BOARD *
nextfree()
{
	struct BOARD	*new;

	if (freeq == (struct BOARD *)-1)  {
		new = (struct BOARD *)calloc (1,sizeof (struct BOARD));
		if (new == 0)  {
			error("Out of memory!");
			return(0);
		}
		new->b_next = (struct BOARD *)-1;
		return (new);
	}

	new = freeq;
	freeq = freeq->b_next;
	return (new);
}

pickmove()
{
						/* current game position */
	register struct BOARD	*now = bsave();
	register struct BOARD	*next;		/* next move */

	do  {				/* compare moves */
		brdcopy(checkq);
		next = checkq->b_next;
		makefree(checkq);
		checkq = next;
		movcmp();
	} while (checkq != (struct BOARD *)-1);

	brdcopy (now);
}

brdcopy(s)
register struct BOARD	*s;			/* game situation */
{
	register int	i;			/* index */

	for (i = 0; i < 26; i++)
		board[i] = s->b_board[i];
	for (i = 0; i < 2; i++)  {
		in[i] = s->b_in[i];
		off[i] = s->b_off[i];
	}
	for (i = 0; i < mvlim; i++)  {
		p[i] = s->b_st[i];
		g[i] = s->b_fn[i];
	}
}

int bestmove = -1;

movcmp()
{
	int newval, i;

	newval = evalmove();
	if (newval > bestmove || (cp[0] == 0 && cg[0] == 0)) {
		bestmove = newval;
		for (i = 0; i < mvlim; i++)  {
			cp[i] = p[i];
			cg[i] = g[i];
		}
	}
}

/*
 * Set dice table to one for roll r1,r2.  If r1 is 0
 * clear table, if r2 is 0 set entries for r1,*.
 */
odds(r1, r2)
register int	r1;
int		r2;
{
	register int	i, j;

	if (r1 == 0)  {
		for (i = 0; i < 6; i++)  
			for (j = 0; j < 6; j++)
				table[i][j] = 0;
		return;
	} else  {
		r1--;
		if (r2-- == 0) {
			for (i = 0; i < 6; i++)  {
				table[i][r1] = 1;
				table[r1][i] = 1;
			}
		} else  {
			table[r1][r2] = 1;
		}
	}
}

/*
 * add up dice rolls in table and return % roll that are set
 */
count()
{
	register int	i;
	register int	j;
	register int	total;

	total = 0;
	for (i = 0; i < 6; i++)
		for (j = 0; j < 6; j++)
			total += table[i][j];
	return ((total * 100) / 36);
}

/*
 * Returns the % probability that the piece at i will be hit.
 * If c is set the probability table is cleared first.
 */
canhit (i, c)
int	i, c;
{
	register int	j, k, b;
	int		a, dist;

	if (c == 0)
		odds(0, 0);
	if (board[i] > 0)  {
		a = -1;
		b = 25;
	} else  {
		a = 1;
		b = 0;
	}
	/*
	if (logfd) {
		fprintf(logfd, "canhit %d\n", i);
	}
	*/
	for (j = b; j != i; j += a)  {
		if (board[j]*a <= 0)  {
			/*
			 * no bad guys here, move on
			 */
			continue;
		}
		dist = abs(j-i);
		/*
		if (logfd) {
			fprintf(logfd, "from %d ", dist);
		}
		*/
		for (k = 1; k <= MIN(dist, 6); k++) {
			if (board[j+a*k]*a <= -2) {
				/*
				 * This spot blocked, by good guys, try next
				 */
				/*
				if (logfd) {
					fprintf(logfd, "(%d blkd %d) ", j+a*k, board[j+a*k]*a);
				}
				*/
				continue;
			}
			if (k == dist) {
				/*
				 * Can hit with one die
				 */
				/*
				if (logfd) {
					fprintf(logfd, "(%d,*) ", dist);
				}
				*/
				odds(dist, 0);
			} else if (dist - k < 7) {
				/*
				 * can hit with 2 dice
				 */
				/*
				if (logfd) {
					fprintf(logfd, "(%d,%d) ", k, dist-k);
				}
				*/
				odds(k, dist-k);
			} else if ( (board[j+a*2*k]*a >= 0) &&
			    (3*k == dist ||
			     (4*k == dist && board[j+a*3*k]*a >= 0)) ) {
				/*
				 * can hit with doubles
				 */
				/*
				if (logfd) {
					fprintf(logfd, "(%d,%d) ", k, k);
				}
				*/
				odds(k, k);
			} else {
				/*
				if (logfd) {
					fprintf(logfd, "(%d nope) ", k);
				}
				*/
			}
		}
		/*
		if (logfd) {
			fprintf(logfd, "\n");
		}
		*/
	}
	return(count());
}

/*
 * dble()
 *	Have the current player double and ask opponent to accept.
 */

dble()
{
	if (cturn == -pnum)  {			/* see if computer accepts */
		if (dblgood())  {		/* guess not */
			putchar(REFUSE_DBLE);
			nexturn();
			cturn *= -2;		/* indicate loss */
			return;
		} else {			/* computer accepts */
			putchar(ACCEPT_DBLE);
			gvalue *= 2;		/* double game value */
			dlast = cturn;
			return;
		}
	}

	putchar(DOUBLEREQ);
	switch (getchar()) {			/* ask if player accepts */
	case ACCEPT_DBLE:
		gvalue *= 2;
		dlast = cturn;
		return;
	case REFUSE_DBLE:
		nexturn();			/* declined */
		cturn *= -2;
		return;
	default:
		error("Bad response to double sent by gammontool");
		return;
	}
}

/*
 * dblgood ()
 *	Returns 1 if the computer would double in this position.  This
 * is not an exact science.  The computer will decline a double that he
 * would have made.  Accumulated judgments are kept in the variable n,
 * which is in "pips", i.e., the position of each man summed over all
 * men, with opponent's totals negative.  Thus, n should have a positive
 * value of 7 for each move ahead, or a negative value of 7 for each one
 * behind.
 */

dblgood()
{
	register int	n;			/* accumulated judgment */
	register int	OFFC = *offptr;		/* no. of computer's men off */
	register int	OFFO = *offopp;		/* no. of player's men off */

						/* get real pip value */
	n = eval() * cturn;

	/* below adjusts pip value according to position judgments */

	if (OFFC > -15 || OFFO > -15) {	/* check men moving off board */
		if (OFFC < 0 && OFFO < 0) {
			OFFC += 15;
			OFFO += 15;
			n +=((OFFC-OFFO)*7)/2;
		} else if (OFFC < 0) {
			OFFC += 15;
			n -= OFFO*7/2;
		} else if (OFFO < 0) {
			OFFO += 15;
			n += OFFC*7/2;
		}
		if (OFFC < 8 && OFFO > 8)
			n -= 7;
		if (OFFC < 10 && OFFO > 10)
			n -= 7;
		if (OFFC < 12 && OFFO > 12)
			n -= 7;
		if (OFFO < 8 && OFFC > 8)
			n += 7;
		if (OFFO < 10 && OFFC > 10)
			n += 7;
		if (OFFO < 12 && OFFC > 12)
			n += 7;
		n += ((OFFC-OFFO)*7)/2;
	}

	/*
	n += freemen(home);
	n -= freemen(bar);
	n += trapped(home,-cturn);
	n -= trapped(bar,cturn);
	*/
	if (!race) {
		n += blockage(home);
		n -= blockage(bar);
	}

	if (n > 20+rnum(7))	/* double if 2-3 moves ahead */
		return(1);
	return(0);
}

/*
 * returns the number of blocked spaces in home
 */
filled(home)
int	home;
{
	register int	i, nblock, turn;

	turn = (home ? 1 : -1);
	for (nblock = 0, i = home-turn; i != home-7*turn; i -= turn)
		if (board[i]*turn > 1)
			nblock++;
	return (nblock);
}

/*
 * returns the number of men in 3rd bay that can safely be used to build
 * in home.
 */
readytofill(home)
int	home;
{
	register int	i, nfree, turn;

	turn = (home ? -1 : 1);
	for (nfree = 0, i = home-7*turn; i != home-13*turn; i -= turn)
		if (board[i]*turn >= 1 && (board[i]*turn & 1))
			nfree++;
	return (nfree);
}

blockage(home)
int home;
{
	register int	i, j, turn;
	int totblock, nblock;
	int hisguys = 0;

	turn = (home ? 1 : -1);
	for (totblock = 0, i = home*turn; i != home-13*turn; i -= turn) {
		if (board[i]*turn < 0) {
			hisguys += -board[i]*turn;
			continue;
		}
		if (board[i]*turn <= 0) {
			continue;
		}
		for (nblock = 0, j = i; j != i-7*turn; j -= turn) {
			if (board[j]*turn > 1) {
				nblock++;
			}
		}
		nblock = nblock * nblock * hisguys;
		if (nblock > totblock) {
			totblock = nblock;
		}
	}
	return (totblock);
}

/*
freemen(b)
int	b;
{
	register int	i, inc, lim;

	odds(0, 0);
	if (board[b] == 0)
		return (0);
	inc = (b == 0? 1: -1);
	lim = (b == 0? 7: 18);
	for (i = b+inc; i != lim; i += inc)
		if (board[i]*inc < -1)
			odds(abs(b-i), 0);
	if (abs(board[b]) == 1)
		return ((36-count())/5);
	return (count()/5);
}

trapped(n,inc)
int	n, inc;
{
	register int	i, j, k;
	int		c, l, ct;

	ct = 0;
	l = n+7*inc;
	for (i = n+inc; i != l; i += inc)  {
		odds(0, 0);
		c = abs(i-l);
		if (board[i]*inc > 0)  {
			for (j = c; j < 13; j++)
				if (board[i+inc*j]*inc < -1)  {
					if (j < 7)
						odds(j, 0);
					for (k = 1; k < 7 && k < j; k++)
						if (j-k < 7)
							odds (k, j-k);
				}
			ct += abs(board[i])*(36-count());
		}
	}
	return (ct/5);
}
*/

eval()
{
	register int	i, j;

	for (j = i = 0; i < 26; i++)
		j += (board[i] >= 0 ? i*board[i] : (25-i)*board[i]);

	if (off[1] >= 0)
		j += 25*off[1];
	else
		j += 25*(off[1]+15);

	if (off[0] >= 0)
		j -= 25*off[0];
	else
		j -= 25*(off[0]+15);
	return (j);
}

makmove(i)
register int	i;
{
	register int	n, d, fin, start;
	int		max;

	d = d0;
	fin = g[i];
	start = p[i];
	n = abs(fin-start);
	max = (*offptr < 0? 7: last());
	if (board[start]*cturn <= 0)
		return(checkd(d)+2);
	if (fin != home && board[fin]*cturn < -1)
		return (checkd(d)+3);
	if (i || D0 == D1)  {
		if (n == max? D1 < n: D1 != n)
			return (checkd(d)+1);
	} else  {
		if (n == max? D0 < n && D1 < n: D0 != n && D1 != n)
			return (checkd(d)+1);
		if (n == max? D0 < n: D0 != n)  {
			if (d0)
				return (checkd(d)+1);
			swap;
		}
	}
	if (fin == home && *offptr < 0)
		return (checkd(d)+4);
	h[i] = 0;
	board[start] -= cturn;
	if (fin != home)  {
		if (board[fin] == -cturn)  {
			board[home] -= cturn;
			board[fin] = 0;
			h[i] = 1;
			if (abs(bar-fin) < 7)  {
				(*inopp)--;
				if (*offopp >= 0)
					*offopp -= 15;
			}
		}
		board[fin] += cturn;
		if (abs(home-fin) < 7 && abs(home-start) > 6)  {
			(*inptr)++;
			if (*inptr+*offptr == 0)
				*offptr += 15;
		}
	} else {
		(*offptr)++;
		(*inptr)--;
	}
	return (0);
}

checkd(d)
register int	d;
{
	if (d0 != d)
		swap;
	return (0);
}

last()
{
	register int	i;

	for (i = home-6*cturn; i != home; i += cturn)
		if (board[i]*cturn > 0)
			return (abs(home-i));
}

movback(i)
register int	i;
{
	register int	j;

	for (j = i-1; j >= 0; j--)
		backone(j);
}

backone(i)
register int	i;
{
	board[p[i]] += cturn;
	if (g[i] != home)  {
		board[g[i]] -= cturn;
		if (abs(g[i]-home) < 7 && abs(p[i]-home) > 6)  {
			(*inptr)--;
			if (*inptr+*offptr < 15 && *offptr >= 0)
				*offptr -= 15;
		}
	} else  {
		(*offptr)--;
		(*inptr)++;
	}
	if (h[i])  {
		board[home] += cturn;
		board[g[i]] = -cturn;
		if (abs(bar-g[i]) < 7)  {
			(*inopp)++;
			if (*inopp+*offopp == 0)
				*offopp += 15;
		}
	}
}

init()		/* initialize the board */
{
	register int	i;

	for (i = 0; i < 26;)
		board[i++] = 0;
	board[1] = 2;
	board[6] = board[13] = -5;
	board[8] = -3;
	board[12] = board[19] = 5;
	board[17] = 3;
	board[24] = -2;
	off[0] = off[1] = -15;
	in[0] = in[1] = 5;
	gvalue = 1;
	dlast = 0;
}

roll()
{
	if (getchar() != DIEROLL) {
		error("Bad die roll code sent by gammontool");
		return;
	}
	D0 = getchar() - '0';
	D1 = getchar() - '0';
	if (D0 > 6 || D1 > 6 || D0 < 1 || D1 < 0)
		error("Illegal die rolls sent by gammontool");
}

nexturn()
{
	register int	c;

	cturn = -cturn;
	c = cturn/abs(cturn);
	home = bar;
	bar = 25-bar;
	offptr += c;
	offopp -= c;
	inptr += c;
	inopp -= c;
}