games/backgammon/backgammon/move.c

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