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