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