NetBSD-5.0.2/games/backgammon/backgammon/move.c
/* $NetBSD: move.c,v 1.9 2005/07/01 01:12:39 jmc Exp $ */
/*
* Copyright (c) 1980, 1993
* The Regents of the University of California. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include <sys/cdefs.h>
#ifndef lint
#if 0
static char sccsid[] = "@(#)move.c 8.1 (Berkeley) 5/31/93";
#else
__RCSID("$NetBSD: move.c,v 1.9 2005/07/01 01:12:39 jmc Exp $");
#endif
#endif /* not lint */
#include "back.h"
#include "backlocal.h"
#ifdef DEBUG
FILE *trace;
static char tests[20];
#endif
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 = 0;
struct BOARD *checkq = 0;
/* these variables are values for the candidate move */
static int ch; /* chance of being hit */
static int op; /* computer's open men */
static int pt; /* comp's protected points */
static int em; /* farthest man back */
static int frc; /* chance to free comp's men */
static int frp; /* chance to free pl's men */
/* these values are the values for the move chosen (so far) */
static int chance; /* chance of being hit */
static int openmen; /* computer's open men */
static int points; /* comp's protected points */
static int endman; /* farthest man back */
static int barmen; /* men on bar */
static int menin; /* men in inner table */
static int menoff; /* men off board */
static int oldfrc; /* chance to free comp's men */
static int oldfrp; /* chance to free pl's men */
static int cp[5]; /* candidate start position */
static int cg[5]; /* candidate finish position */
static int race; /* game reduced to a race */
static int bcomp(struct BOARD *, struct BOARD *);
static struct BOARD *bsave(void);
static void binsert(struct BOARD *);
static void boardcopy(struct BOARD *);
static void makefree(struct BOARD *);
static void mvcheck(struct BOARD *, struct BOARD *);
static struct BOARD *nextfree(void);
/* zero if first move */
void
move(int okay)
{
int i; /* index */
int l; /* last man */
l = 0;
if (okay) {
/* see if comp should double */
if (gvalue < 64 && dlast != cturn && dblgood()) {
writel(*Colorptr);
dble(); /* double */
/* return if declined */
if (cturn != 1 && cturn != -1)
return;
}
roll();
}
race = 0;
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;
/* print roll */
if (tflag)
curmove(cturn == -1 ? 18 : 19, 0);
writel(*Colorptr);
writel(" rolls ");
writec(D0 + '0');
writec(' ');
writec(D1 + '0');
/* make tty interruptable while thinking */
if (tflag)
cline();
fixtty(&noech);
/* find out how many moves */
mvlim = movallow();
if (mvlim == 0) {
writel(" but cannot use it.\n");
nexturn();
fixtty(&raw);
return;
}
/* initialize */
for (i = 0; i < 4; i++)
cp[i] = cg[i] = 0;
/* strategize */
trymove(0, 0);
pickmove();
/* print move */
writel(" and moves ");
for (i = 0; i < mvlim; i++) {
if (i > 0)
writec(',');
wrint(p[i] = cp[i]);
writec('-');
wrint(g[i] = cg[i]);
makmove(i);
}
writec('.');
/* print blots hit */
if (tflag)
curmove(20, 0);
else
writec('\n');
for (i = 0; i < mvlim; i++)
if (h[i])
wrhit(g[i]);
/* get ready for next move */
nexturn();
if (!okay) {
buflush();
sleep(3);
}
fixtty(&raw); /* no more tty interrupt */
}
/* mvnum == number of move (rel zero) */
/* swapped == see if swapped also tested */
void
trymove(int mvnum, int swapped)
{
int pos; /* position on board */
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);
}
static struct BOARD *
bsave(void)
{
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);
}
/* new == item to insert */
static void
binsert(struct BOARD *new)
{
struct BOARD *qp = checkq; /* queue pointer */
int result; /* comparison result */
if (qp == 0) { /* check if queue empty */
checkq = qp = new;
qp->b_next = 0;
return;
}
result = bcomp(new, qp); /* compare to first element */
if (result < 0) { /* insert in front */
new->b_next = qp;
checkq = new;
return;
}
if (result == 0) { /* duplicate entry */
mvcheck(qp, new);
makefree(new);
return;
}
while (qp->b_next != 0) {/* traverse queue */
result = bcomp(new, qp->b_next);
if (result < 0) { /* found place */
new->b_next = qp->b_next;
qp->b_next = new;
return;
}
if (result == 0) { /* duplicate entry */
mvcheck(qp->b_next, new);
makefree(new);
return;
}
qp = qp->b_next;
}
/* place at end of queue */
qp->b_next = new;
new->b_next = 0;
}
static int
bcomp(struct BOARD *a, struct BOARD *b)
{
int *aloc = a->b_board; /* pointer to board a */
int *bloc = b->b_board; /* pointer to board b */
int i; /* index */
int result; /* comparison result */
for (i = 0; i < 26; i++) { /* compare boards */
result = cturn * (aloc[i] - bloc[i]);
if (result)
return (result); /* found inequality */
}
return (0); /* same position */
}
static void
mvcheck(struct BOARD *incumbent, struct BOARD *candidate)
{
int i;
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];
}
}
void
makefree(struct BOARD *dead)
{
dead->b_next = freeq; /* add to freeq */
freeq = dead;
}
static struct BOARD *
nextfree(void)
{
struct BOARD *new;
if (freeq == 0) {
new = (struct BOARD *) calloc(1, sizeof(struct BOARD));
if (new == 0) {
writel("\nOut of memory\n");
getout(0);
}
} else {
new = freeq;
freeq = freeq->b_next;
}
new->b_next = 0;
return (new);
}
void
pickmove(void)
{
/* current game position */
struct BOARD *now = bsave();
struct BOARD *next; /* next move */
#ifdef DEBUG
if (trace == NULL)
trace = fopen("bgtrace", "w");
fprintf(trace, "\nRoll: %d %d%s\n", D0, D1, race ? " (race)" : "");
fflush(trace);
#endif
do { /* compare moves */
boardcopy(checkq);
next = checkq->b_next;
makefree(checkq);
checkq = next;
movcmp();
} while (checkq != 0);
boardcopy(now);
}
static void
boardcopy(struct BOARD *s)
{
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];
}
}
void
movcmp(void)
{
int i;
#ifdef DEBUG
if (trace == NULL)
trace = fopen("bgtrace", "w");
#endif
odds(0, 0, 0);
if (!race) {
ch = op = pt = 0;
for (i = 1; i < 25; i++) {
if (board[i] == cturn)
ch = canhit(i, 1);
op += abs(bar - i);
}
for (i = bar + cturn; i != home; i += cturn)
if (board[i] * cturn > 1)
pt += abs(bar - i);
frc = freemen(bar) + trapped(bar, cturn);
frp = freemen(home) + trapped(home, -cturn);
}
for (em = bar; em != home; em += cturn)
if (board[em] * cturn > 0)
break;
em = abs(home - em);
#ifdef DEBUG
fputs("Board: ", trace);
for (i = 0; i < 26; i++)
fprintf(trace, " %d", board[i]);
if (race)
fprintf(trace, "\n\tem = %d\n", em);
else
fprintf(trace,
"\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n",
ch, pt, em, frc, frp);
fputs("\tMove: ", trace);
for (i = 0; i < mvlim; i++)
fprintf(trace, " %d-%d", p[i], g[i]);
fputs("\n", trace);
fflush(trace);
strcpy(tests, "");
#endif
if ((cp[0] == 0 && cg[0] == 0) || movegood()) {
#ifdef DEBUG
fprintf(trace, "\t[%s] ... wins.\n", tests);
fflush(trace);
#endif
for (i = 0; i < mvlim; i++) {
cp[i] = p[i];
cg[i] = g[i];
}
if (!race) {
chance = ch;
openmen = op;
points = pt;
endman = em;
barmen = abs(board[home]);
oldfrc = frc;
oldfrp = frp;
}
menin = *inptr;
menoff = *offptr;
}
#ifdef DEBUG
else {
fprintf(trace, "\t[%s] ... loses.\n", tests);
fflush(trace);
}
#endif
}
int
movegood(void)
{
int n;
if (*offptr == 15)
return (1);
if (menoff == 15)
return (0);
if (race) {
#ifdef DEBUG
strcat(tests, "o");
#endif
if (*offptr - menoff)
return (*offptr > menoff);
#ifdef DEBUG
strcat(tests, "e");
#endif
if (endman - em)
return (endman > em);
#ifdef DEBUG
strcat(tests, "i");
#endif
if (menin == 15)
return (0);
if (*inptr == 15)
return (1);
#ifdef DEBUG
strcat(tests, "i");
#endif
if (*inptr - menin)
return (*inptr > menin);
return (rnum(2));
} else {
n = barmen - abs(board[home]);
#ifdef DEBUG
strcat(tests, "c");
#endif
if (abs(chance - ch) + 25 * n > rnum(150))
return (n ? (n < 0) : (ch < chance));
#ifdef DEBUG
strcat(tests, "o");
#endif
if (*offptr - menoff)
return (*offptr > menoff);
#ifdef DEBUG
strcat(tests, "o");
#endif
if (abs(openmen - op) > 7 + rnum(12))
return (openmen > op);
#ifdef DEBUG
strcat(tests, "b");
#endif
if (n)
return (n < 0);
#ifdef DEBUG
strcat(tests, "e");
#endif
if (abs(endman - em) > rnum(2))
return (endman > em);
#ifdef DEBUG
strcat(tests, "f");
#endif
if (abs(frc - oldfrc) > rnum(2))
return (frc < oldfrc);
#ifdef DEBUG
strcat(tests, "p");
#endif
if (abs(n = pt - points) > rnum(4))
return (n > 0);
#ifdef DEBUG
strcat(tests, "i");
#endif
if (*inptr - menin)
return (*inptr > menin);
#ifdef DEBUG
strcat(tests, "f");
#endif
if (abs(frp - oldfrp) > rnum(2))
return (frp > oldfrp);
return (rnum(2));
}
}