home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume36 / ldb / part03 / check.c next >
Encoding:
C/C++ Source or Header  |  1993-04-11  |  11.5 KB  |  387 lines
  1. /*    check.c        10/29/91
  2.  *
  3.  * Copyright 1991  Perry R. Ross
  4.  *
  5.  * Permission to use, copy, modify, and distribute this software and its
  6.  * documentation without fee is hereby granted, subject to the restrictions
  7.  * detailed in the README file, which is included here by reference.
  8.  * Any other use requires written permission from the author.  This software
  9.  * is distributed "as is" without any warranty, including any implied
  10.  * warranties of merchantability or fitness for a particular purpose.
  11.  * The author shall not be liable for any damages resulting from the
  12.  * use of this software.  By using this software, the user agrees
  13.  * to these terms.
  14.  */
  15.  
  16. #include "ldb.h"
  17.  
  18. /*======================================================================
  19.  * This file contains the functions that check for unused moves.
  20.  *======================================================================
  21.  */
  22.  
  23.  
  24. PRIVATE int maxused, hiused, nlegal;
  25.  
  26. struct legal *rmlegal();
  27.  
  28. /*----------------------------------------------------------------------
  29.  *    legalmoves -- calculate all legal moves for a game
  30.  *
  31.  * This function is called after the dice have been rolled to search
  32.  * all possible combinations of moves to see which ones are legal.
  33.  * While this function is working, it keeps a list of legal moves,
  34.  * but this list is deleted before returning.  For the purposes
  35.  * of checking a move, it suffices to only keep the number of usable
  36.  * dice and the highest numbered usable dice.  Any move that uses as
  37.  * many dice as can be used, and uses the highest usable dice, is
  38.  * legal.  These values are stored in the maxused and hiused fields
  39.  * of the game structure.
  40.  *
  41.  * legalmoves performs an exhaustive search of all possible move
  42.  * combinations, storing the combinations that are not rejected
  43.  * by apply() in an instance of struct legal, which is linked into
  44.  * the doubly-linked list headed by lhead.  Note that, at this point,
  45.  * this list may contain many combinations that are not legal because
  46.  * they do not use all possible dice, or they use a smaller dice when
  47.  * a larger one is usable.  These illegal combinations are trimmed from
  48.  * the list by trimunused() and trimlowused().  Finally, duplicate combinations
  49.  * are removed from the list by trimequal().  Duplicate moves are those that
  50.  * use the same rolls to move from the same points, but possibly in a
  51.  * different order, for example (3/8 1/6) and (1/6 3/8).  This allows
  52.  * detection of the case where there is only one legal move, in which
  53.  * case this move is automatically applied (if rc.automove is set).
  54.  * If the list is empty, there are no legal moves.  Otherwise, the
  55.  * highest roll used in the list is stored in g->hiused, and the largest
  56.  * number of rolls used in the list is stored in g->maxused.  This information
  57.  * is used by check().
  58.  *----------------------------------------------------------------------
  59.  */
  60.  
  61. legalmoves(g)
  62. struct game *g;
  63. {
  64. struct game tmp;
  65. int i;
  66. struct legal *l;
  67.  
  68. tmp = *g;            /* we don't want to change actual game */
  69. for (i = 0; i < 4; tmp.mvs[i++].pt = -1);    /* mark all unused */
  70. maxused = -1;            /* init to not all used */
  71. hiused = 0;            /* init to 0 */
  72. nlegal = 0;            /* init to no legal moves*/
  73. lhead = NULL;
  74. ltail = NULL;
  75. if (tmp.mvs[0].roll == tmp.mvs[1].roll)
  76.     scanmvs(&tmp,0,3);    /* there is only one ordering */
  77. else {
  78.     scanmvs(&tmp,0,1);        /* scan for one ordering */
  79.     i = tmp.mvs[0].roll;    /* reverse rolls */
  80.     tmp.mvs[0].roll = tmp.mvs[1].roll;
  81.     tmp.mvs[1].roll = i;
  82.     for (i = 0; i < 4; tmp.mvs[i++].pt = -1);    /* mark all unused */
  83.     scanmvs(&tmp,0,1);        /* scan for other ordering */
  84.     }
  85. trimunused();        /* zap combinations that leave usable rolls unused */
  86. trimlowused();        /* zap combinations that use the wrong die */
  87. trimequal();        /* zap duplicates */
  88. g->maxused = maxused;    /* store maxused and hiused into the game structure */
  89. g->hiused = hiused;
  90. if (nlegal == 0) {    /* check for no legal moves */
  91.     if (g->dispmsg != NULL)
  92.         free(g->dispmsg);
  93.     g->dispmsg = save("You don't have any legal moves.");
  94.     }
  95. else if (nlegal == 1) {    /* check for only one legal move */
  96.     if (g->dispmsg != NULL)
  97.         free(g->dispmsg);
  98.     g->dispmsg = save("You only have one legal move.");
  99.     if (*rc.automove == 'y') {    /* you want the move applied? */
  100.         if ( (lhead->nmove==0) && (lhead->mvs[0].roll!=g->mvs[0].roll))
  101.             g->mvs[1] = g->mvs[0];
  102.         for (i = 0; i <= lhead->nmove; i++) {
  103.             g->mvs[i] = lhead->mvs[i];
  104.             apply(g,WHO_ME,i,0,NULL);
  105.             }
  106.         }
  107.     }
  108.  
  109.     /* we have no use for the legal moves list, so free it */
  110.     /* maybe in the future we will have a use for it */
  111.  
  112. for (l = lhead; l != NULL; l = l->next)
  113.     free(l);
  114. lhead = NULL;
  115. ltail = NULL;
  116. }
  117.  
  118.  
  119. /*----------------------------------------------------------------------
  120.  *    scanmvs -- search for all possible combinations of a move
  121.  *
  122.  * This function takes a single die and tries to use it on every point
  123.  * of the board.  For every point it is successful, it adds the
  124.  * combination to the legal moves list and performs a recursive descent
  125.  * searching for all legal combinations of the remaining dice.
  126.  *----------------------------------------------------------------------
  127.  */
  128. scanmvs(g,mn,max)
  129. struct game *g;
  130. int mn, max;
  131. {
  132. int i;
  133. board sv;
  134.  
  135. copyboard(g->board,sv);        /* save the board */
  136. for (i = 0; i <= 24; i++) {
  137.     if (i == 0)
  138.         g->mvs[mn].pt = BARPT(g->mydir);    /* use correct barpt */
  139.     else
  140.         g->mvs[mn].pt = i;
  141.     if (apply(g,WHO_ME,mn,0,NULL) < 0)    /* can't move from this pt */
  142.         continue;
  143.     addlegal(mn,g->mvs[mn].roll,g->mvs[mn].pt);    /* add to list */
  144.     if (mn < max)
  145.         scanmvs(g,mn+1,max);        /* try all remaining comb's */
  146.     copyboard(sv,g->board);            /* restore board */
  147.     }
  148. }
  149.  
  150.  
  151. /*----------------------------------------------------------------------
  152.  *    addlegal -- add a move combination to the list
  153.  *
  154.  * This function adds an instance of struct legal to the legal moves list.
  155.  * The arguments to addlegal only specify the usage of one particular
  156.  * die, by specifying its "move number".  For example, for a roll of
  157.  * 5 2, the 5 is move number 0 and the 2 is move number 1.  The usage
  158.  * of all lower numbered rolls is copied from the previous entry in the
  159.  * moves list (since that entry was added by the higher level scanmvs
  160.  * before the current scanmvs was called), and all higher-numbered rolls
  161.  * are marked unused.
  162.  *----------------------------------------------------------------------
  163.  */
  164.  
  165. addlegal(mn,r,pt)
  166. int mn, r, pt;
  167. {
  168. int i;
  169. struct legal *n;
  170.  
  171. if ( (n = (struct legal *) calloc(sizeof(struct legal),1)) == NULL)
  172.     fatal("Out of memory!");
  173. clearmvs(n->mvs);
  174. if (ltail != NULL)
  175.     for (i = 0; i < mn; i++)        /* copy prefix from prev move */
  176.         n->mvs[i] = ltail->mvs[i];
  177. n->mvs[mn].roll = r;        /* copy in this move */
  178. n->mvs[mn].pt = pt;
  179. n->next = NULL;            /* this is end of list */
  180. if (lhead == NULL) {        /* link into list */
  181.     n->prev = NULL;
  182.     lhead = n;
  183.     ltail = n;
  184.     }
  185. else {
  186.     n->prev = ltail;
  187.     ltail->next = n;
  188.     ltail = n;
  189.     }
  190. n->himove = 0;
  191. for (i = 0; i <= mn; i++)    /* search for highest used move */
  192.     if (n->mvs[i].roll > n->himove)
  193.         n->himove = n->mvs[i].roll;
  194. if (mn > maxused)        /* keep track of whether it is possible */
  195.     maxused = mn;    /* to use all of the rolls */
  196. nlegal++;
  197. n->nmove = mn;        /* store number of moves used by this entry */
  198. }
  199.  
  200.  
  201. /*----------------------------------------------------------------------
  202.  *    trimunused -- remove moves that do not use all possible rolls
  203.  *
  204.  * This function scans the move list and deletes combinations that
  205.  * leave usable rolls unused.
  206.  *----------------------------------------------------------------------
  207.  */
  208.  
  209. trimunused()
  210. {
  211. struct legal *l;
  212.  
  213. l = lhead;
  214. while (l != NULL) {
  215.     if (l->nmove < maxused)
  216.         l = rmlegal(l);
  217.     else
  218.         l = l->next;
  219.     }
  220. }
  221.  
  222.  
  223. /*----------------------------------------------------------------------
  224.  *    trimlowused -- remove moves that do not use the largest possible roll
  225.  *
  226.  * This function scans the move list and deletes combinations that
  227.  * do not use the highest usable roll.
  228.  *----------------------------------------------------------------------
  229.  */
  230.  
  231. trimlowused()
  232. {
  233. struct legal *l;
  234.  
  235. l = lhead;
  236. while (l != NULL) {
  237.     if (l->himove < hiused)
  238.         l = rmlegal(l);
  239.     else
  240.         l = l->next;
  241.     }
  242. }
  243.  
  244.  
  245. /*----------------------------------------------------------------------
  246.  *    trimequal -- remove duplicate moves
  247.  *
  248.  * This function scans the move list and deletes combinations that
  249.  * are duplicates.
  250.  *----------------------------------------------------------------------
  251.  */
  252.  
  253. trimequal()
  254. {
  255. struct legal *l, *p;
  256. struct mv m1[4], m2[4];
  257. int i, n;
  258.  
  259. for (l = lhead; l != NULL; l = l->next) {
  260.     extractmvs(l,m1);
  261.     n = l->nmove;
  262.     p = l->next;
  263.     while (p != NULL) {
  264.         if (p->nmove != n) {
  265.             p = p->next;
  266.             continue;
  267.             }
  268.         extractmvs(p,m2);
  269.         for (i = 0; i <= n; i++)
  270.             if ((m1[i].roll != m2[i].roll)||(m1[i].pt != m2[i].pt))
  271.                 break;
  272.         if (i <= n)
  273.             p = p->next;
  274.         else
  275.             p = rmlegal(p);
  276.         }
  277.     }
  278. }
  279.  
  280.  
  281. /*----------------------------------------------------------------------
  282.  *    rmlegal -- remove a struct legal from the move list
  283.  *
  284.  * This function unlinks an entry from the move list and free's it.
  285.  *----------------------------------------------------------------------
  286.  */
  287.  
  288. struct legal *rmlegal(l)
  289. struct legal *l;
  290. {
  291. struct legal *t;
  292.  
  293. t = l;
  294. if (l == lhead) {
  295.     lhead = l->next;
  296.     l = lhead;
  297.     }
  298. else {
  299.     if ( (l->prev->next = l->next) != NULL)
  300.         l->next->prev = l->prev;
  301.     l = l->next;
  302.     }
  303. free(t);
  304. nlegal--;
  305. return(l);
  306. }
  307.  
  308.  
  309. /*----------------------------------------------------------------------
  310.  *    extractmvs -- extract a struct legal into a struct mv
  311.  *
  312.  * This function copies the information from a move list entry into
  313.  * an instance of struct mv, and then sorts the rolls in the struct mv
  314.  * by increasing dice value (and by increasing point number for equal
  315.  * rolls).  Sorting the rolls makes it easier for trimequal to check
  316.  * for duplicate entries, it has no value as far as the game is concerned.
  317.  *----------------------------------------------------------------------
  318.  */
  319.  
  320. extractmvs(l,m)
  321. struct legal *l;
  322. struct mv *m;
  323. {
  324. int i, n, s;
  325. struct mv tmp;
  326.  
  327. clearmvs(m);
  328. for (i = 0; i <= l->nmove; i++)        /* extract the moves */
  329.     m[i] = l->mvs[i];
  330. n = l->nmove;
  331. do {            /* sort by increasing roll then increasing point */
  332.     s = 0;
  333.     for (i = 0; i < n; i++) {        /* long live bubblesort */
  334.         if (m[i].roll < m[i+1].roll)
  335.             continue;
  336.         else if ( (m[i].roll == m[i+1].roll) && (m[i].pt < m[i+1].pt) )
  337.             continue;
  338.         tmp = m[i];
  339.         m[i] = m[i+1];
  340.         m[i+1] = tmp;
  341.         s = 1;
  342.         }
  343.     n--;
  344.     } while (s);
  345. }
  346.  
  347.  
  348. /*----------------------------------------------------------------------
  349.  *    checkused -- check that a move uses the correct rolls
  350.  *
  351.  * This function is called just before a move is sent to the
  352.  * opponent.  It uses the values stored in g->maxused and g->hiused
  353.  * to make sure that the move uses all usable rolls, and that it
  354.  * uses the highest usable roll.  As a special case, it considers
  355.  * to be legal any move where all pieces are borne off.  This
  356.  * takes care of the special case where there is one piece
  357.  * left to bear off, and two rolls, one of which is too small
  358.  * to bear off.  Normally, ldb would insist that the smaller
  359.  * roll be used, then the larger one, so that both rolls
  360.  * would be used.  If one roll is large enough to bear the last
  361.  * man off, though, there is no need to force the other roll to be used.
  362.  *----------------------------------------------------------------------
  363.  */
  364.  
  365. checkused(g)
  366. struct game *g;
  367. {
  368. int h, i;
  369.  
  370. if (g->board[OFFPT(g->mydir)].qty == 15)    /* special case, if all pcs */
  371.     return(0);        /* are off, then all rolls have been used */
  372. h = 0;
  373. for (i = 0; i <= g->maxused; i++) {
  374.     if (g->mvs[i].pt < 0) {
  375.         FeMessage("You left a roll unused.");
  376.         return(1);
  377.         }
  378.     if (h < g->mvs[i].roll)
  379.         h = g->mvs[i].roll;
  380.     }
  381. if (g->hiused > h) {
  382.     FeMessage("You can use the higher roll.");
  383.     return(1);
  384.     }
  385. return(0);
  386. }
  387.