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
  34 #ifndef lint
  35 #if 0
  36 static char sccsid[] = "@(#)move.c      8.1 (Berkeley) 5/31/93";
  37 #endif
  38 static const char rcsid[] =
  39  "$FreeBSD: src/games/backgammon/backgammon/move.c,v 1.5 1999/11/30 03:48:23 billf Exp $";
  40 #endif /* not lint */
  41
  42 #include <stdlib.h>
  43 #include "back.h"
  44
  45 #ifdef DEBUG
  46 #include <stdio.h>
  47 FILE    *trace;
  48 static char     tests[20];
  49 #endif
  50
  51 struct BOARD  {                         /* structure of game position */
  52         int     b_board[26];                    /* board position */
  53         int     b_in[2];                        /* men in */
  54         int     b_off[2];                       /* men off */
  55         int     b_st[4], b_fn[4];               /* moves */
  56
  57         struct BOARD    *b_next;                /* forward queue pointer */
  58 };
  59
  60 struct BOARD *freeq = 0;
  61 struct BOARD *checkq = 0;
  62 struct BOARD *bsave();
  63 struct BOARD *nextfree();
  64
  65                                         /* these variables are values for the
  66                                          * 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
  75                                          * move chosen (so far) */
  76 static int      chance;                         /* chance of being hit */
  77 static int      openmen;                        /* computer's open men */
  78 static int      points;                         /* comp's protected points */
  79 static int      endman;                         /* farthest man back */
  80 static int      barmen;                         /* men on bar */
  81 static int      menin;                          /* men in inner table */
  82 static int      menoff;                         /* men off board */
  83 static int      oldfrc;                         /* chance to free comp's men */
  84 static int      oldfrp;                         /* chance to free pl's men */
  85
  86 static int      cp[5];                          /* candidate start position */
  87 static int      cg[5];                          /* candidate finish position */
  88
  89 static int      race;                           /* game reduced to a race */
  90 \f
  91 move (okay)
  92 int     okay;                                   /* zero if first move */
  93 {
  94         int     i;              /* index */
  95         int     l;              /* last man */
  96
  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
 130                                                  * 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 \f
 181 trymove (mvnum,swapped)
 182 int             mvnum;                          /* number of move (rel zero) */
 183 int             swapped;                        /* see if swapped also tested */
 184
 185 {
 186         int     pos;                    /* position on board */
 187         int     rval;                   /* value of roll */
 188
 189                                                 /* if recursed through all dice
 190                                                  * values, compare move */
 191         if (mvnum == mvlim)  {
 192                 binsert (bsave());
 193                 return;
 194         }
 195
 196                                                 /* make sure dice in always
 197                                                  * 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 \f
 236 struct BOARD *
 237 bsave ()  {
 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 \f
 257 binsert (new)
 258 struct BOARD    *new;                                   /* item to insert */
 259 {
 260         struct BOARD    *p = checkq;            /* queue pointer */
 261         int             result;                 /* comparison result */
 262
 263         if (p == 0)  {                          /* check if queue empty */
 264                 checkq = p = new;
 265                 p->b_next = 0;
 266                 return;
 267         }
 268
 269         result = bcomp (new,p);                 /* compare to first element */
 270         if (result < 0)  {                              /* insert in front */
 271                 new->b_next = p;
 272                 checkq = new;
 273                 return;
 274         }
 275         if (result == 0)  {                             /* duplicate entry */
 276                 mvcheck (p,new);
 277                 makefree (new);
 278                 return;
 279         }
 280
 281         while (p->b_next != 0)  {               /* traverse queue */
 282                 result = bcomp (new,p->b_next);
 283                 if (result < 0)  {                      /* found place */
 284                         new->b_next = p->b_next;
 285                         p->b_next = new;
 286                         return;
 287                 }
 288                 if (result == 0)  {                     /* duplicate entry */
 289                         mvcheck (p->b_next,new);
 290                         makefree (new);
 291                         return;
 292                 }
 293                 p = p->b_next;
 294         }
 295                                                 /* place at end of queue */
 296         p->b_next = new;
 297         new->b_next = 0;
 298 }
 299 \f
 300 bcomp (a,b)
 301 struct BOARD    *a;
 302 struct BOARD    *b;
 303 {
 304         int     *aloc = a->b_board;     /* pointer to board a */
 305         int     *bloc = b->b_board;     /* pointer to board b */
 306         int             i;                      /* index */
 307         int             result;                 /* comparison result */
 308
 309         for (i = 0; i < 26; i++)  {             /* compare boards */
 310                 result = cturn*(aloc[i]-bloc[i]);
 311                 if (result)
 312                         return (result);                /* found inequality */
 313         }
 314         return (0);                             /* same position */
 315 }
 316 \f
 317 mvcheck (incumbent,candidate)
 318 struct BOARD    *incumbent;
 319 struct BOARD    *candidate;
 320 {
 321         int             i;
 322         int             result;
 323
 324         for (i = 0; i < mvlim; i++)  {
 325                 result = cturn*(candidate->b_st[i]-incumbent->b_st[i]);
 326                 if (result > 0)
 327                         return;
 328                 if (result < 0)
 329                         break;
 330         }
 331         if (i == mvlim)
 332                 return;
 333         for (i = 0; i < mvlim; i++)  {
 334                 incumbent->b_st[i] = candidate->b_st[i];
 335                 incumbent->b_fn[i] = candidate->b_fn[i];
 336         }
 337 }
 338 \f
 339 makefree (dead)
 340 struct BOARD    *dead;                  /* dead position */
 341 {
 342         dead->b_next = freeq;                   /* add to freeq */
 343         freeq = dead;
 344 }
 345
 346 struct BOARD *
 347 nextfree ()  {
 348         struct BOARD    *new;
 349
 350         if (freeq == 0)  {
 351                 new = (struct BOARD *)calloc (1,sizeof (struct BOARD));
 352                 if (new == 0)  {
 353                         writel ("\nOut of memory\n");
 354                         getout();
 355                 }
 356                 new->b_next = 0;
 357         } else {
 358                 new = freeq;
 359                 freeq = freeq->b_next;
 360         }
 361         return (new);
 362 }
 363 \f
 364 pickmove ()  {
 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 != 0);
 382
 383         boardcopy (now);
 384 }
 385 \f
 386 boardcopy (s)
 387 struct BOARD    *s;                     /* game situation */
 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 \f
 403 movcmp ()  {
 404         int     i;
 405         int     c;
 406
 407 #ifdef DEBUG
 408         if (trace == NULL)
 409                 trace = fopen ("bgtrace","w");
 410 #endif
 411
 412         odds (0,0,0);
 413         if (!race)  {
 414                 ch = op = pt = 0;
 415                 for (i = 1; i < 25; i++)  {
 416                         if (board[i] == cturn)
 417                                 ch = canhit (i,1);
 418                                 op += abs (bar-i);
 419                 }
 420                 for (i = bar+cturn; i != home; i += cturn)
 421                         if (board[i]*cturn > 1)
 422                                 pt += abs(bar-i);
 423                 frc = freemen (bar)+trapped (bar,cturn);
 424                 frp = freemen (home)+trapped (home,-cturn);
 425         }
 426         for (em = bar; em != home; em += cturn)
 427                 if (board[em]*cturn > 0)
 428                         break;
 429         em = abs(home-em);
 430 #ifdef DEBUG
 431         fputs ("Board: ",trace);
 432         for (i = 0; i < 26; i++)
 433                 fprintf (trace, " %d",board[i]);
 434         if (race)
 435                 fprintf (trace,"\n\tem = %d\n",em);
 436         else
 437                 fprintf (trace,
 438                         "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n",
 439                         ch,pt,em,frc,frp);
 440         fputs ("\tMove: ",trace);
 441         for (i = 0; i < mvlim; i++)
 442                 fprintf (trace," %d-%d",p[i],g[i]);
 443         fputs ("\n",trace);
 444         fflush (trace);
 445         strcpy (tests,"");
 446 #endif
 447         if ((cp[0] == 0 && cg[0] == 0) || movegood())  {
 448 #ifdef DEBUG
 449                 fprintf (trace,"\t[%s] ... wins.\n",tests);
 450                 fflush (trace);
 451 #endif
 452                 for (i = 0; i < mvlim; i++)  {
 453                         cp[i] = p[i];
 454                         cg[i] = g[i];
 455                 }
 456                 if (!race)  {
 457                         chance = ch;
 458                         openmen = op;
 459                         points = pt;
 460                         endman = em;
 461                         barmen = abs(board[home]);
 462                         oldfrc = frc;
 463                         oldfrp = frp;
 464                 }
 465                 menin = *inptr;
 466                 menoff = *offptr;
 467         }
 468 #ifdef DEBUG
 469         else  {
 470                 fprintf (trace,"\t[%s] ... loses.\n",tests);
 471                 fflush (trace);
 472         }
 473 #endif
 474 }
 475 \f
 476 movegood ()  {
 477         int     n;
 478
 479         if (*offptr == 15)
 480                 return (1);
 481         if (menoff == 15)
 482                 return (0);
 483         if (race)  {
 484 #ifdef DEBUG
 485                 strcat (tests,"o");
 486 #endif
 487                 if (*offptr-menoff)
 488                         return (*offptr > menoff);
 489 #ifdef DEBUG
 490                 strcat (tests,"e");
 491 #endif
 492                 if (endman-em)
 493                         return (endman > em);
 494 #ifdef DEBUG
 495                 strcat (tests,"i");
 496 #endif
 497                 if (menin == 15)
 498                         return (0);
 499                 if (*inptr == 15)
 500                         return (1);
 501 #ifdef DEBUG
 502                 strcat (tests,"i");
 503 #endif
 504                 if (*inptr-menin)
 505                         return (*inptr > menin);
 506                 return (rnum(2));
 507         } else  {
 508                 n = barmen-abs(board[home]);
 509 #ifdef DEBUG
 510                 strcat (tests,"c");
 511 #endif
 512                 if (abs(chance-ch)+25*n > rnum(150))
 513                         return (n? (n < 0): (ch < chance));
 514 #ifdef DEBUG
 515                 strcat (tests,"o");
 516 #endif
 517                 if (*offptr-menoff)
 518                         return (*offptr > menoff);
 519 #ifdef DEBUG
 520                 strcat (tests,"o");
 521 #endif
 522                 if (abs(openmen-op) > 7+rnum(12))
 523                         return (openmen > op);
 524 #ifdef DEBUG
 525                 strcat (tests,"b");
 526 #endif
 527                 if (n)
 528                         return (n < 0);
 529 #ifdef DEBUG
 530                 strcat (tests,"e");
 531 #endif
 532                 if (abs(endman-em) > rnum(2))
 533                         return (endman > em);
 534 #ifdef DEBUG
 535                 strcat (tests,"f");
 536 #endif
 537                 if (abs(frc-oldfrc) > rnum(2))
 538                         return (frc < oldfrc);
 539 #ifdef DEBUG
 540                 strcat (tests,"p");
 541 #endif
 542                 if (abs(n = pt-points) > rnum(4))
 543                         return (n > 0);
 544 #ifdef DEBUG
 545                 strcat (tests,"i");
 546 #endif
 547                 if (*inptr-menin)
 548                         return (*inptr > menin);
 549 #ifdef DEBUG
 550                 strcat (tests,"f");
 551 #endif
 552                 if (abs(frp-oldfrp) > rnum(2))
 553                         return (frp > oldfrp);
 554                 return (rnum(2));
 555         }
 556 }