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