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