Return to move.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / games / backgammon

Annotation of 43BSDTahoe/games/backgammon/move.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.