home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus Extra 1996 #3 / AmigaPlus_CD-ROM-EXTRA_Nr.3.bin / aminet-spiele / brettspiele / amigo / killable.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-12-12  |  12.2 KB  |  377 lines
  1. /* By Stoney Ballard */
  2. /* Ported from Pascal to C by Todd R. Johnson */
  3.  
  4. #include "go.h"
  5. #include "goplayutils.h"
  6.  
  7. extern intBoard bord, groupIDs;
  8. extern boolBoard legal;
  9. extern tryPlay( short, short, short );
  10. extern sSpanGroup( short, short, sPointList * );
  11. extern spanGroup( short, short, pointList *);
  12. extern pause();
  13. extern groupRec gList[maxGroup];
  14. extern short gMap[maxGroup], adjInAtari, adj2Libs, playMark, treeLibLim,
  15.              utilPlayLevel, killFlag, depthLimit, dbStop, showTrees;
  16. extern pointList plist2;
  17.  
  18. /*
  19.   returns true if the group (at x, y) is killable.
  20.   if so, returns the point to play at in killx, killy.
  21. */
  22.  
  23.   short me, him, depth, i, j, tryCount, tl, topMark, tkMark, mark2;
  24.   char sChar;
  25.   sPointList lList, dList;
  26.   point tp;
  27.   short libList[maxSPoint+1];
  28.   short esc;
  29.  
  30. short mtNbrs(x, y)
  31. short x, y;
  32.   { /* mtNbrs */
  33.     short n = 0;
  34.     if ((x > 0) && (bord[x - 1][y] == 0))
  35.       n = n + 1;
  36.     if ((x < maxPoint) && (bord[x + 1][y] == 0))
  37.       n = n + 1;
  38.     if ((y > 0) && (bord[x][y - 1] == 0))
  39.       n = n + 1;
  40.     if ((y < maxPoint) && (bord[x][y + 1] == 0))
  41.       n = n + 1;
  42.     return n;
  43.   } /* mtNbrs */
  44.  
  45. short killTree(tx, ty, gx, gy, escape, tkMark)
  46. short tx, ty, gx, gy, *escape, tkMark;
  47.     { /* killTree */
  48.       short curMark, mark2, mark3, i, j, k, tl, dStart, result;
  49.       sPointList lList1, lList2;
  50.       short libList[maxSPoint+1];
  51.       point tp;
  52.       short esc = FALSE;
  53.       tryCount = tryCount + 1;
  54.       if (tryCount > tryLimit)
  55.         {
  56.           undoTo(tkMark);
  57. /*          for (i = 1; i <= depth - 1; i++)
  58.             {
  59.               sClearChar(sChar, rXor); 
  60.             } */
  61.           depth = 1;
  62.       return FALSE;
  63.         }
  64. /*      write(sChar); */
  65.       depth = depth + 1;
  66.       curMark = playMark;
  67.       tryPlay(tx, ty, me); /* try my move */
  68.       pause();
  69.       if (gList[gMap[groupIDs[tx][ty]]].libC == 0) /* I'm dead */
  70.     {
  71.     result = FALSE;
  72.     goto one;
  73.     }
  74.       else if (killFlag) /* I killed something of his */
  75.     {
  76.     result = TRUE;
  77.     goto one;
  78.     }
  79.       else if (gList[gMap[groupIDs[gx][gy]]].libC > treeLibLim) /* safe */
  80.     {
  81.     result = FALSE;
  82.     goto one;
  83.     }
  84.       else
  85.         {
  86.           sSpanGroup(gx, gy, &lList1); /* find his liberties */
  87.           if (gList[gMap[groupIDs[tx][ty]]].libC == 1) /* he can kill me */
  88.             {
  89.               if (lList1.indx < maxSPoint) /* add that option to his list */
  90.                 {
  91.                   lList1.indx = lList1.indx + 1;
  92.                   spanGroup(tx, ty, &plist2); /* find my liberty */
  93.                       lList1.p[lList1.indx].px = plist2.p[1].px;
  94.                       lList1.p[lList1.indx].py = plist2.p[1].py;
  95.                 }
  96.               else
  97.         {
  98.         result = FALSE;
  99.         goto one;
  100.         }
  101.             }
  102.           for (i = 1; i <= maxSPoint; i++)    /* init liblist so diags can be marked */
  103.             libList[i] = -1;
  104.           if ((utilPlayLevel > 4) &&
  105.              (lList1.indx > 1) &&
  106.              (gList[gMap[groupIDs[gx][gy]]].libC > 1)) /* try diags */
  107.             {
  108.               listDiags(gx, gy, &dList);
  109.               j = 0;
  110.               i = lList1.indx;
  111.               while ((j < dList.indx) &&
  112.                     (i < maxSPoint))
  113.                 {
  114.                   j = j + 1;
  115.                   i = i + 1;
  116.                   libList[i] = 0;     /* mark this as a diag */
  117.                       lList1.p[i].px = dList.p[j].px;
  118.                       lList1.p[i].py = dList.p[j].py;
  119.                 }
  120.               lList1.indx = i;
  121.             }
  122.           if (lList1.indx > 1) /* sort by decreasing lib count */
  123.             {
  124.               for (i = 1; i <= lList1.indx; i++)
  125.                 if (libList[i] != 0)       /* diags are tried last */
  126.                     {
  127.                       mark2 = playMark;
  128.                       tryPlay(lList1.p[i].px, lList1.p[i].py, him);
  129.                       libList[i] = gList[gMap[groupIDs[gx][gy]]].libC;
  130.                       if ((libList[i] > treeLibLim) ||
  131.                          ((libList[i] > (depthLimit - depth)) &&
  132.                           (libList[i] > 2)))
  133.             {
  134.             *escape = TRUE;
  135.             result = FALSE;
  136.             goto one;
  137.             }
  138.                       undoTo(mark2);
  139.                     }
  140.               for (i = 1; i <= lList1.indx - 1; i++)
  141.                 for (j = i + 1; j <= lList1.indx; j++)
  142.                   if (libList[i] < libList[j])
  143.                     {
  144.                       tl = libList[i];
  145.                       libList[i] = libList[j];
  146.                       libList[j] = tl;
  147.                       tp = lList1.p[i];
  148.                       lList1.p[i] = lList1.p[j];
  149.                       lList1.p[j] = tp;
  150.                     }
  151.             }
  152.           for (i = 1; i <= lList1.indx + 1; i++) /* try his responses */
  153.             {
  154.               mark2 = playMark;
  155.               if (i <= lList1.indx) /* try his move */
  156.                   {
  157.                     tryPlay(lList1.p[i].px, lList1.p[i].py, him); /* play his response */
  158.                     pause();
  159.                     if (gList[gMap[groupIDs[lList1.p[i].px]
  160.                                    [lList1.p[i].py]]].libC < 2)
  161.                       goto two; /* a bogus move */
  162.                   }
  163.               else if (gList[gMap[groupIDs[gx][gy]]].libC <= 1)
  164.             {
  165.             result = TRUE;
  166.             goto one;
  167.             }
  168.               if (gList[gMap[groupIDs[gx][gy]]].libC > treeLibLim)
  169.                 {
  170.                   *escape = TRUE;
  171.           result = FALSE;
  172.           goto one;
  173.                 }
  174.               if (gList[gMap[groupIDs[gx][gy]]].libC > 1)
  175.                 {  /* look at my responses */
  176.                   sSpanGroup(gx, gy, &lList2); /* list his liberties */
  177.                   dStart = lList2.indx + 1;
  178.                   if (adjInAtari) /* he wins */
  179.                      {
  180.                        result = FALSE;
  181.                        goto one;
  182.                      }
  183.                   if ((lList2.indx > 2) && adj2Libs) /* he wins */
  184.                      {
  185.                        result = FALSE;
  186.                        goto one;
  187.                      }
  188.                   for (k = 1; k <= maxSPoint; k++)
  189.                     libList[k] = -1;
  190.                   if (utilPlayLevel > 4) /* account for diagonal moves */
  191.                     {
  192.                       listDiags(gx, gy, &dList);
  193.                       j = 0;
  194.                       k = lList2.indx;
  195.                       while ((j < dList.indx) &&
  196.                             (k < maxSPoint))
  197.                         {
  198.                           j = j + 1;
  199.                           k = k + 1;
  200.                           libList[k] = 100;
  201.                               lList2.p[k].px = dList.p[j].px;
  202.                               lList2.p[k].py = dList.p[j].py;
  203.                         }
  204.                       lList2.indx = k;
  205.                     }
  206.                   if (lList2.indx > 1) /* sort by increasing lib count */
  207.                     {
  208.                       for (k = 1; k <= lList2.indx; k++)
  209.                         if (libList[k] != 100)     /* diags go last */
  210.                             {
  211.                               mark3 = playMark;
  212.                               tryPlay(lList2.p[k].px, lList2.p[k].py, me);
  213.                               libList[k] = gList[gMap[groupIDs[gx][gy]]].libC;
  214.                               undoTo(mark3);
  215.                             }
  216.                       for (k = 1; k <= lList2.indx - 1; k++)
  217.                         for (j = k + 1; j <= lList2.indx; j++)
  218.                           if (libList[k] > libList[j])
  219.                             {
  220.                               tl = libList[k];
  221.                               libList[k] = libList[j];
  222.                               libList[j] = tl;
  223.                               tp = lList2.p[k];
  224.                               lList2.p[k] = lList2.p[j];
  225.                               lList2.p[j] = tp;
  226.                             }
  227.                           else if ((libList[k] == libList[j]) &&
  228.                                   (libList[k] == 1))
  229.                             if (mtNbrs(lList2.p[k].px, lList2.p[k].py) <
  230.                                mtNbrs(lList2.p[j].px, lList2.p[j].py))
  231.                               {
  232.                                 tl = libList[k];
  233.                                 libList[k] = libList[j];
  234.                                 libList[j] = tl;
  235.                                 tp = lList2.p[k];
  236.                                 lList2.p[k] = lList2.p[j];
  237.                                 lList2.p[j] = tp;
  238.                               }
  239.                     }
  240.                   for (j = 1; j <= lList2.indx; j++)
  241.                     {
  242.                       if (killTree(lList2.p[j].px, lList2.p[j].py, gx,
  243.                 gy, &esc, tkMark))
  244.                         goto two; /* this kills him */
  245.                       if (esc && (j >= dStart))
  246.                         {
  247.                           result = FALSE;
  248.                           goto one; /* don't bother with more diags if escapes */
  249.                         }
  250.                     }
  251.                   result = FALSE;  /* none of my responses kills him */
  252.                   goto one;
  253.                 }
  254.     two:
  255.              undoTo(mark2);
  256.            }
  257.           result = TRUE; /* none of his responses saves him */
  258.         }
  259.     one:
  260.       undoTo(curMark);
  261. /*      sClearChar(sChar, rXor); */
  262.       depth = depth - 1;
  263.       return result;
  264.     } /* killTree */
  265.  
  266. short tKillTree(tx, ty, gx, gy)
  267. short tx, ty, gx, gy;
  268.   { /* tKillTree */
  269.     short tkMark, escape;
  270.     tryCount = 0;
  271.     tkMark = playMark;
  272.     return killTree(tx, ty, gx, gy, &escape, tkMark);
  273.   } /* tKillTree */
  274.  
  275. short killable(gx, gy, killx, killy)
  276. short gx, gy, *killx, *killy;
  277. { /* killable */
  278. #ifdef DEBUG
  279.   printf( "killable\n" );
  280.   showTrees = TRUE;
  281. #endif
  282.   dbStop = TRUE;
  283.   him = bord[gx][gy]; /* find out who I am */
  284.   me = -him;
  285. /*  if (me == 1)
  286.     sChar = '>';
  287.   else
  288.     sChar = '|'; */
  289. /*  write(sChar); */
  290.   depth = 1;
  291.   topMark = playMark;
  292.   sSpanGroup(gx, gy, &lList); /* find his liberties */
  293.   if (lList.indx == 1)
  294.     {
  295.       *killx = lList.p[1].px;
  296.       *killy = lList.p[1].py;
  297.       return TRUE;
  298.     }
  299.   else if (lList.indx > treeLibLim)
  300.     return FALSE;
  301.   else if (adjInAtari)
  302.     return FALSE;
  303.   else if ((lList.indx > 2) && adj2Libs)
  304.     return FALSE;
  305.   else
  306.     {
  307.       for (i = 1; i <= maxSPoint; i++)
  308.         libList[i] = -1;
  309.       if (utilPlayLevel > 4) /* account for diagonal moves */
  310.         {
  311.           listDiags(gx, gy, &dList);
  312.           j = 0;
  313.           i = lList.indx;
  314.           while ((j < dList.indx) &&
  315.                 (i < maxSPoint))
  316.             {
  317.               j = j + 1;
  318.               i = i + 1;
  319.               libList[i] = 100;
  320.                   lList.p[i].px = dList.p[j].px;
  321.                   lList.p[i].py = dList.p[j].py;
  322.             }
  323.           lList.indx = i;
  324.         }
  325.       if (lList.indx > 1) /* sort by increasing lib count */
  326.         {
  327.           for (i = 1; i <= lList.indx; i++)
  328.             if (libList[i] != 100)  /* diags go last */
  329.                 {
  330.                   mark2 = playMark;
  331.                   tryPlay(lList.p[i].px, lList.p[i].py, me);
  332.                   libList[i] = gList[gMap[groupIDs[gx][gy]]].libC;
  333.                   undoTo(mark2);
  334.                 }
  335.           for (i = 1; i <= lList.indx - 1; i++)
  336.             for (j = i + 1; j <= lList.indx; j++)
  337.               if (libList[i] > libList[j])
  338.                 {
  339.                   tl = libList[i];
  340.                   libList[i] = libList[j];
  341.                   libList[j] = tl;
  342.                   tp = lList.p[i];
  343.                   lList.p[i] = lList.p[j];
  344.                   lList.p[j] = tp;
  345.                 }
  346.               else if ((libList[i] == libList[j]) &&
  347.                       (libList[i] == 1))
  348.                 if (mtNbrs(lList.p[i].px, lList.p[i].py) <
  349.                    mtNbrs(lList.p[j].px, lList.p[j].py))
  350.                   {
  351.                     tl = libList[i];
  352.                     libList[i] = libList[j];
  353.                     libList[j] = tl;
  354.                     tp = lList.p[i];
  355.                     lList.p[i] = lList.p[j];
  356.                     lList.p[j] = tp;
  357.                   }
  358.         }
  359.       for (i = 1; i <= lList.indx; i++)
  360.         {
  361.           if (legal[lList.p[i].px, lList.p[i].py])
  362.             {
  363.               *killx = lList.p[i].px;
  364.               *killy = lList.p[i].py;
  365.               if (tKillTree(*killx, *killy, gx, gy))
  366.                 {
  367. /*                  sClearChar(sChar, rXor); */
  368.                   return TRUE;
  369.                 }
  370.             }
  371.         }
  372.       return FALSE;
  373.     }
  374. /*   sClearChar(sChar, rXor); */
  375. } /* killable */
  376.  
  377.