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