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