4.3BSD - /usr/src/games/backgammon/move.c

   1: /*
   2:  * Copyright (c) 1980 Regents of the University of California.
   3:  * All rights reserved.  The Berkeley software License Agreement
   4:  * specifies the terms and conditions for redistribution.
   5:  */
   6: 
   7: #ifndef lint
   8: static char sccsid[] = "@(#)move.c	5.1 (Berkeley) 5/29/85";
   9: #endif not lint
  10: 
  11: #include "back.h"
  12: 
  13: #ifdef DEBUG
  14: #include <stdio.h>
  15: FILE    *trace;
  16: static char tests[20];
  17: #endif
  18: 
  19: struct BOARD  {             /* structure of game position */
  20:     int b_board[26];            /* board position */
  21:     int b_in[2];            /* men in */
  22:     int b_off[2];           /* men off */
  23:     int b_st[4], b_fn[4];       /* moves */
  24: 
  25:     struct BOARD    *b_next;        /* forward queue pointer */
  26: };
  27: 
  28: struct BOARD *freeq = -1;
  29: struct BOARD *checkq = -1;
  30: struct BOARD *bsave();
  31: struct BOARD *nextfree();
  32: 
  33:                     /* these variables are values for the
  34: 					 * candidate move */
  35: static int  ch;             /* chance of being hit */
  36: static int  op;             /* computer's open men */
  37: static int  pt;             /* comp's protected points */
  38: static int  em;             /* farthest man back */
  39: static int  frc;                /* chance to free comp's men */
  40: static int  frp;                /* chance to free pl's men */
  41: 
  42:                     /* these values are the values for the
  43: 					 * move chosen (so far) */
  44: static int  chance;             /* chance of being hit */
  45: static int  openmen;            /* computer's open men */
  46: static int  points;             /* comp's protected points */
  47: static int  endman;             /* farthest man back */
  48: static int  barmen;             /* men on bar */
  49: static int  menin;              /* men in inner table */
  50: static int  menoff;             /* men off board */
  51: static int  oldfrc;             /* chance to free comp's men */
  52: static int  oldfrp;             /* chance to free pl's men */
  53: 
  54: static int  cp[5];              /* candidate start position */
  55: static int  cg[5];              /* candidate finish position */
  56: 
  57: static int  race;               /* game reduced to a race */
  58: 
  59: move (okay)
  60: int okay;                   /* zero if first move */
  61: {
  62:     register int    i;      /* index */
  63:     register int    l;      /* last man */
  64: 
  65:     if (okay)  {
  66:                         /* see if comp should double */
  67:         if (gvalue < 64 && dlast != cturn && dblgood())  {
  68:             writel (*Colorptr);
  69:             dble();             /* double */
  70:                             /* return if declined */
  71:             if (cturn != 1 && cturn != -1)
  72:                 return;
  73:         }
  74:         roll();
  75:     }
  76: 
  77:     race = 0;
  78:     for (i = 0; i < 26; i++)  {
  79:         if (board[i] < 0)
  80:             l = i;
  81:     }
  82:     for (i = 0; i < l; i++)  {
  83:         if (board[i] > 0)
  84:             break;
  85:     }
  86:     if (i == l)
  87:         race = 1;
  88: 
  89:                         /* print roll */
  90:     if (tflag)
  91:         curmove (cturn == -1? 18: 19,0);
  92:     writel (*Colorptr);
  93:     writel (" rolls ");
  94:     writec (D0+'0');
  95:     writec (' ');
  96:     writec (D1+'0');
  97:                         /* make tty interruptable
  98: 						 * while thinking */
  99:     if (tflag)
 100:         cline();
 101:     fixtty (noech);
 102: 
 103:                         /* find out how many moves */
 104:     mvlim = movallow();
 105:     if (mvlim == 0)  {
 106:         writel (" but cannot use it.\n");
 107:         nexturn();
 108:         fixtty (raw);
 109:         return;
 110:     }
 111: 
 112:                         /* initialize */
 113:     for (i = 0; i < 4; i++)
 114:         cp[i] = cg[i] = 0;
 115: 
 116:                         /* strategize */
 117:     trymove (0,0);
 118:     pickmove();
 119: 
 120:                         /* print move */
 121:     writel (" and moves ");
 122:     for (i = 0; i < mvlim; i++)  {
 123:         if (i > 0)
 124:             writec (',');
 125:         wrint (p[i] = cp[i]);
 126:         writec ('-');
 127:         wrint (g[i] = cg[i]);
 128:         makmove (i);
 129:     }
 130:     writec ('.');
 131: 
 132:                         /* print blots hit */
 133:     if (tflag)
 134:         curmove (20,0);
 135:     else
 136:         writec ('\n');
 137:     for (i = 0; i < mvlim; i++)
 138:         if (h[i])
 139:             wrhit(g[i]);
 140:                         /* get ready for next move */
 141:     nexturn();
 142:     if (!okay)  {
 143:         buflush();
 144:         sleep (3);
 145:     }
 146:     fixtty (raw);               /* no more tty interrupt */
 147: }
 148: 
 149: trymove (mvnum,swapped)
 150: register int    mvnum;              /* number of move (rel zero) */
 151: int     swapped;            /* see if swapped also tested */
 152: 
 153: {
 154:     register int    pos;            /* position on board */
 155:     register int    rval;           /* value of roll */
 156: 
 157:                         /* if recursed through all dice
 158: 						 * values, compare move */
 159:     if (mvnum == mvlim)  {
 160:         binsert (bsave());
 161:         return;
 162:     }
 163: 
 164:                         /* make sure dice in always
 165: 						 * same order */
 166:     if (d0 == swapped)
 167:         swap;
 168:                         /* choose value for this move */
 169:     rval = dice[mvnum != 0];
 170: 
 171:                         /* find all legitimate moves */
 172:     for (pos = bar; pos != home; pos += cturn)  {
 173:                         /* fix order of dice */
 174:         if (d0 == swapped)
 175:             swap;
 176:                         /* break if stuck on bar */
 177:         if (board[bar] != 0 && pos != bar)
 178:             break;
 179:                         /* on to next if not occupied */
 180:         if (board[pos]*cturn <= 0)
 181:             continue;
 182:                         /* set up arrays for move */
 183:         p[mvnum] = pos;
 184:         g[mvnum] = pos+rval*cturn;
 185:         if (g[mvnum]*cturn >= home)  {
 186:             if (*offptr < 0)
 187:                 break;
 188:             g[mvnum] = home;
 189:         }
 190:                         /* try to move */
 191:         if (makmove (mvnum))
 192:             continue;
 193:         else
 194:             trymove (mvnum+1,2);
 195:                         /* undo move to try another */
 196:         backone (mvnum);
 197:     }
 198: 
 199:                         /* swap dice and try again */
 200:     if ((!swapped) && D0 != D1)
 201:         trymove (0,1);
 202: }
 203: 
 204: struct BOARD *
 205: bsave ()  {
 206:     register int    i;      /* index */
 207:     struct BOARD    *now;       /* current position */
 208: 
 209:     now = nextfree ();      /* get free BOARD */
 210: 
 211:                     /* store position */
 212:     for (i = 0; i < 26; i++)
 213:         now->b_board[i] = board[i];
 214:     now->b_in[0] = in[0];
 215:     now->b_in[1] = in[1];
 216:     now->b_off[0] = off[0];
 217:     now->b_off[1] = off[1];
 218:     for (i = 0; i < mvlim; i++)  {
 219:         now->b_st[i] = p[i];
 220:         now->b_fn[i] = g[i];
 221:     }
 222:     return (now);
 223: }
 224: 
 225: binsert (new)
 226: struct BOARD    *new;                   /* item to insert */
 227: {
 228:     register struct BOARD   *p = checkq;        /* queue pointer */
 229:     register int        result;         /* comparison result */
 230: 
 231:     if (p == -1)  {             /* check if queue empty */
 232:         checkq = p = new;
 233:         p->b_next = -1;
 234:         return;
 235:     }
 236: 
 237:     result = bcomp (new,p);         /* compare to first element */
 238:     if (result < 0)  {              /* insert in front */
 239:         new->b_next = p;
 240:         checkq = new;
 241:         return;
 242:     }
 243:     if (result == 0)  {             /* duplicate entry */
 244:         mvcheck (p,new);
 245:         makefree (new);
 246:         return;
 247:     }
 248: 
 249:     while (p->b_next != -1)  {      /* traverse queue */
 250:         result = bcomp (new,p->b_next);
 251:         if (result < 0)  {          /* found place */
 252:             new->b_next = p->b_next;
 253:             p->b_next = new;
 254:             return;
 255:         }
 256:         if (result == 0)  {         /* duplicate entry */
 257:             mvcheck (p->b_next,new);
 258:             makefree (new);
 259:             return;
 260:         }
 261:         p = p->b_next;
 262:     }
 263:                         /* place at end of queue */
 264:     p->b_next = new;
 265:     new->b_next = -1;
 266: }
 267: 
 268: bcomp (a,b)
 269: struct BOARD    *a;
 270: struct BOARD    *b;
 271: {
 272:     register int    *aloc = a->b_board; /* pointer to board a */
 273:     register int    *bloc = b->b_board; /* pointer to board b */
 274:     register int    i;          /* index */
 275:     int     result;         /* comparison result */
 276: 
 277:     for (i = 0; i < 26; i++)  {     /* compare boards */
 278:         result = cturn*(aloc[i]-bloc[i]);
 279:         if (result)
 280:             return (result);        /* found inequality */
 281:     }
 282:     return (0);             /* same position */
 283: }
 284: 
 285: mvcheck (incumbent,candidate)
 286: register struct BOARD   *incumbent;
 287: register struct BOARD   *candidate;
 288: {
 289:     register int    i;
 290:     register int    result;
 291: 
 292:     for (i = 0; i < mvlim; i++)  {
 293:         result = cturn*(candidate->b_st[i]-incumbent->b_st[i]);
 294:         if (result > 0)
 295:             return;
 296:         if (result < 0)
 297:             break;
 298:     }
 299:     if (i == mvlim)
 300:         return;
 301:     for (i = 0; i < mvlim; i++)  {
 302:         incumbent->b_st[i] = candidate->b_st[i];
 303:         incumbent->b_fn[i] = candidate->b_fn[i];
 304:     }
 305: }
 306: 
 307: makefree (dead)
 308: struct BOARD    *dead;          /* dead position */
 309: {
 310:     dead->b_next = freeq;           /* add to freeq */
 311:     freeq = dead;
 312: }
 313: 
 314: struct BOARD *
 315: nextfree ()  {
 316:     struct BOARD    *new;
 317: 
 318:     if (freeq == -1)  {
 319:         new = calloc (1,sizeof (struct BOARD));
 320:         if (new == 0)  {
 321:             writel ("\nOut of memory\n");
 322:             getout();
 323:         }
 324:         new->b_next = -1;
 325:         return (new);
 326:     }
 327: 
 328:     new = freeq;
 329:     freeq = freeq->b_next;
 330: }
 331: 
 332: pickmove ()  {
 333:                         /* current game position */
 334:     register struct BOARD   *now = bsave();
 335:     register struct BOARD   *next;      /* next move */
 336: 
 337: #ifdef DEBUG
 338:     if (trace == NULL)
 339:         trace = fopen ("bgtrace","w");
 340:     fprintf (trace,"\nRoll:  %d %d%s\n",D0,D1,race? " (race)": "");
 341:     fflush (trace);
 342: #endif
 343:     do  {               /* compare moves */
 344:         bcopy (checkq);
 345:         next = checkq->b_next;
 346:         makefree (checkq);
 347:         checkq = next;
 348:         movcmp();
 349:     } while (checkq != -1);
 350: 
 351:     bcopy (now);
 352: }
 353: 
 354: bcopy (s)
 355: register struct BOARD   *s;         /* game situation */
 356: {
 357:     register int    i;          /* index */
 358: 
 359:     for (i = 0; i < 26; i++)
 360:         board[i] = s->b_board[i];
 361:     for (i = 0; i < 2; i++)  {
 362:         in[i] = s->b_in[i];
 363:         off[i] = s->b_off[i];
 364:     }
 365:     for (i = 0; i < mvlim; i++)  {
 366:         p[i] = s->b_st[i];
 367:         g[i] = s->b_fn[i];
 368:     }
 369: }
 370: 
 371: movcmp ()  {
 372:     register int    i;
 373:     register int    c;
 374: 
 375: #ifdef DEBUG
 376:     if (trace == NULL)
 377:         trace = fopen ("bgtrace","w");
 378: #endif
 379: 
 380:     odds (0,0,0);
 381:     if (!race)  {
 382:         ch = op = pt = 0;
 383:         for (i = 1; i < 25; i++)  {
 384:             if (board[i] == cturn)
 385:                 ch = canhit (i,1);
 386:                 op += abs (bar-i);
 387:         }
 388:         for (i = bar+cturn; i != home; i += cturn)
 389:             if (board[i]*cturn > 1)
 390:                 pt += abs(bar-i);
 391:         frc = freemen (bar)+trapped (bar,cturn);
 392:         frp = freemen (home)+trapped (home,-cturn);
 393:     }
 394:     for (em = bar; em != home; em += cturn)
 395:         if (board[em]*cturn > 0)
 396:             break;
 397:     em = abs(home-em);
 398: #ifdef DEBUG
 399:     fputs ("Board: ",trace);
 400:     for (i = 0; i < 26; i++)
 401:         fprintf (trace, " %d",board[i]);
 402:     if (race)
 403:         fprintf (trace,"\n\tem = %d\n",em);
 404:     else
 405:         fprintf (trace,
 406:             "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n",
 407:             ch,pt,em,frc,frp);
 408:     fputs ("\tMove: ",trace);
 409:     for (i = 0; i < mvlim; i++)
 410:         fprintf (trace," %d-%d",p[i],g[i]);
 411:     fputs ("\n",trace);
 412:     fflush (trace);
 413:     strcpy (tests,"");
 414: #endif
 415:     if ((cp[0] == 0 && cg[0] == 0) || movegood())  {
 416: #ifdef DEBUG
 417:         fprintf (trace,"\t[%s] ... wins.\n",tests);
 418:         fflush (trace);
 419: #endif
 420:         for (i = 0; i < mvlim; i++)  {
 421:             cp[i] = p[i];
 422:             cg[i] = g[i];
 423:         }
 424:         if (!race)  {
 425:             chance = ch;
 426:             openmen = op;
 427:             points = pt;
 428:             endman = em;
 429:             barmen = abs(board[home]);
 430:             oldfrc = frc;
 431:             oldfrp = frp;
 432:         }
 433:         menin = *inptr;
 434:         menoff = *offptr;
 435:     }
 436: #ifdef DEBUG
 437:     else  {
 438:         fprintf (trace,"\t[%s] ... loses.\n",tests);
 439:         fflush (trace);
 440:     }
 441: #endif
 442: }
 443: 
 444: movegood ()  {
 445:     register int    n;
 446: 
 447:     if (*offptr == 15)
 448:         return (1);
 449:     if (menoff == 15)
 450:         return (0);
 451:     if (race)  {
 452: #ifdef DEBUG
 453:         strcat (tests,"o");
 454: #endif
 455:         if (*offptr-menoff)
 456:             return (*offptr > menoff);
 457: #ifdef DEBUG
 458:         strcat (tests,"e");
 459: #endif
 460:         if (endman-em)
 461:             return (endman > em);
 462: #ifdef DEBUG
 463:         strcat (tests,"i");
 464: #endif
 465:         if (menin == 15)
 466:             return (0);
 467:         if (*inptr == 15)
 468:             return (1);
 469: #ifdef DEBUG
 470:         strcat (tests,"i");
 471: #endif
 472:         if (*inptr-menin)
 473:             return (*inptr > menin);
 474:         return (rnum(2));
 475:     } else  {
 476:         n = barmen-abs(board[home]);
 477: #ifdef DEBUG
 478:         strcat (tests,"c");
 479: #endif
 480:         if (abs(chance-ch)+25*n > rnum(150))
 481:             return (n? (n < 0): (ch < chance));
 482: #ifdef DEBUG
 483:         strcat (tests,"o");
 484: #endif
 485:         if (*offptr-menoff)
 486:             return (*offptr > menoff);
 487: #ifdef DEBUG
 488:         strcat (tests,"o");
 489: #endif
 490:         if (abs(openmen-op) > 7+rnum(12))
 491:             return (openmen > op);
 492: #ifdef DEBUG
 493:         strcat (tests,"b");
 494: #endif
 495:         if (n)
 496:             return (n < 0);
 497: #ifdef DEBUG
 498:         strcat (tests,"e");
 499: #endif
 500:         if (abs(endman-em) > rnum(2))
 501:             return (endman > em);
 502: #ifdef DEBUG
 503:         strcat (tests,"f");
 504: #endif
 505:         if (abs(frc-oldfrc) > rnum(2))
 506:             return (frc < oldfrc);
 507: #ifdef DEBUG
 508:         strcat (tests,"p");
 509: #endif
 510:         if (abs(n = pt-points) > rnum(4))
 511:             return (n > 0);
 512: #ifdef DEBUG
 513:         strcat (tests,"i");
 514: #endif
 515:         if (*inptr-menin)
 516:             return (*inptr > menin);
 517: #ifdef DEBUG
 518:         strcat (tests,"f");
 519: #endif
 520:         if (abs(frp-oldfrp) > rnum(2))
 521:             return (frp > oldfrp);
 522:         return (rnum(2));
 523:     }
 524: }

Defined functions

Defined variables

Defined struct's