home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1995 August / NEBULA.mdf / Apps / Games / NeXTGo / Source / score.c < prev    next >
Encoding:
C/C++ Source or Header  |  1977-12-27  |  10.6 KB  |  524 lines
  1. /*
  2.                 GNU GO - the game of Go (Wei-Chi)
  3.                 Version 1.1   last revised 3-1-89
  4.            Copyright (C) Free Software Foundation, Inc.
  5.                       written by Man L. Li
  6.                       modified by Wayne Iba
  7.                     documented by Bob Webber
  8.                     NeXT version by John Neil*
  9.  
  10. *Note:  These routines were written entirely by John Neil
  11. */
  12. /*
  13. This program is free software; you can redistribute it and/or modify
  14. it under the terms of the GNU General Public License as published by
  15. the Free Software Foundation - version 1.
  16.  
  17. This program is distributed in the hope that it will be useful,
  18. but WITHOUT ANY WARRANTY; without even the implied warranty of
  19. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20. GNU General Public License in file COPYING for more details.
  21.  
  22. You should have received a copy of the GNU General Public License
  23. along with this program; if not, write to the Free Software
  24. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  25.  
  26. Please report any bug/fix, modification, suggestion to
  27.  
  28. mail address:   Man L. Li
  29.                 Dept. of Computer Science
  30.                 University of Houston
  31.                 4800 Calhoun Road
  32.                 Houston, TX 77004
  33.  
  34. e-mail address: manli@cs.uh.edu         (Internet)
  35.                 coscgbn@uhvax1.bitnet   (BITNET)
  36.                 70070,404               (CompuServe)
  37.  
  38. For the NeXT version, please report any bug/fix, modification, suggestion to
  39.  
  40. mail address:   John Neil
  41.                 Mathematics Department
  42.                 Portland State University
  43.                 PO Box 751
  44.                 Portland, OR  97207
  45.  
  46. e-mail address: neil@math.mth.pdx.edu  (Internet)
  47.                 neil@psuorvm.bitnet    (BITNET)
  48. */
  49.  
  50. extern unsigned char p[19][19];
  51. extern int MAXX, MAXY;
  52. extern int blackCaptured, whiteCaptured, blackTerritory, whiteTerritory;
  53. unsigned char mark[19][19], ownermat[19][19], scoringmat[19][19];
  54. unsigned char newpatternmat[19][19], tempmat[19][19], patternmat[19][19];
  55.  
  56. void display_board(void)
  57. {
  58.   int i, j;
  59.  
  60.   printf("\n\n");
  61.   for (i = 0; i < MAXX; i++)
  62.     {
  63.       for (j = 0; j < MAXY; j++)
  64.     switch (p[i][j])
  65.       {
  66.       case 0: 
  67.         printf("+");
  68.         break;
  69.       case 1:
  70.         printf("O");
  71.         break;
  72.       case 2:
  73.         printf("X");
  74.       }
  75.       printf("\n");
  76.     }
  77. }
  78.  
  79. void set_temp_to_patternmat(void)
  80. {
  81.   int i, j;
  82.  
  83.   for (i = 0; i < MAXX; i++)
  84.     for (j = 0; j < MAXY; j++)
  85.       newpatternmat[i][j] = patternmat[i][j];
  86. }
  87.  
  88. void set_patternmat_to_temp(void)
  89. {
  90.   int i, j;
  91.  
  92.   for (i = 0; i < MAXX; i++)
  93.     for (j = 0; j < MAXY; j++)
  94.       patternmat[i][j] = newpatternmat[i][j];
  95. }
  96.  
  97. void set_p_to_temp(void)
  98. /*  Copy the board to a temporary array.  */
  99. {
  100.   int i, j;
  101.  
  102.   for (i = 0; i < MAXX; i++)
  103.     for (j = 0; j < MAXY; j++)
  104.       p[i][j] = tempmat[i][j];
  105. }
  106.  
  107. void set_temp_to_p(void)
  108. /*  Copy the temporary array to the board.  */
  109. {
  110.   int i, j;
  111.  
  112.   for (i = 0; i < MAXX; i++)
  113.     for (j = 0; j < MAXY; j++)
  114.       tempmat[i][j] = p[i][j];
  115. }
  116.  
  117. void find_pattern_in_board(int x, int y)
  118. /*  Find a pattern of stones or blank spots in the board.  */
  119. {
  120.   int i, j, changes = 1, minx, maxx, miny, maxy;
  121.  
  122.   for (i = 0; i < MAXX; i++)
  123.     for (j = 0; j < MAXY; j++)
  124.       patternmat[i][j] = 0;
  125.  
  126.   patternmat[x][y] = 1;
  127.   minx = (x>0)?x-1:0;
  128.   maxx = (x<MAXX-1)?x+1:MAXX-1;
  129.   miny = (y>0)?y-1:0;
  130.   maxy = (y<MAXY-1)?y+1:MAXY-1;
  131.  
  132.   while (changes)
  133.     {
  134.       changes = 0;
  135.       set_temp_to_patternmat();
  136.       for (i = minx; i <= maxx; i++)
  137.     for (j = miny; j <= maxy; j++)
  138.       if (patternmat[i][j] == 0)
  139.       {
  140.         /*  Check northern neighbor.  */
  141.         if (i > 0)
  142.           {
  143.         if ((patternmat[i-1][j]) && (p[i][j] == p[i-1][j]))
  144.           {
  145.             changes++;
  146.             if (i + 1 > maxx)
  147.               maxx = (i+1<MAXX-1)?i+1:MAXX-1;
  148.             newpatternmat[i][j] = 1;
  149.           }
  150.           }
  151.  
  152.         /*  Check eastern neighbor.  */
  153.         if (j < MAXY - 1)
  154.           {
  155.         if ((patternmat[i][j+1]) && (p[i][j] == p[i][j+1]))
  156.           {
  157.             changes++;
  158.             if (j - 1 < miny)
  159.               miny = (j-1>0)?j-1:0;
  160.             newpatternmat[i][j] = 1;
  161.           }
  162.           }
  163.  
  164.         /*  Check southern neighbor.  */
  165.         if (i < MAXX - 1)
  166.           {
  167.         if ((patternmat[i+1][j]) && (p[i][j] == p[i+1][j]))
  168.           {
  169.             changes++;
  170.             if (i - 1 < minx)
  171.               minx = (i-1>0)?i-1:0;
  172.             newpatternmat[i][j] = 1;
  173.           }
  174.           }
  175.  
  176.         /*  Check western neighbor.  */
  177.         if (j > 0)
  178.           {
  179.         if ((patternmat[i][j-1]) && (p[i][j] == p[i][j-1]))
  180.           {
  181.             changes++;
  182.             if (j + 1 > maxy)
  183.               maxy = (j+1<MAXY-1)?j+1:MAXY-1;
  184.             newpatternmat[i][j] = 1;
  185.           }
  186.           }
  187.       }
  188.       set_patternmat_to_temp();
  189.     }
  190. }
  191.  
  192. void find_owner0(int x, int y)
  193. /*  Routine to the find the owner of the blank spot at x, y.  */
  194. {
  195.   int i, j, changes = 1, owner = 0, minx, maxx, miny, maxy;
  196.  
  197. /*  clear_mat(patternmat);  */
  198.   for (i = 0; i < MAXX; i++)
  199.     for (j = 0; j < MAXY; j++)
  200.       patternmat[i][j] = 0;
  201.  
  202.   patternmat[x][y] = mark[x][y] = 1;
  203.   minx = (x>0)?x-1:0;
  204.   maxx = (x<MAXX-1)?x+1:MAXX-1;
  205.   miny = (y>0)?y-1:0;
  206.   maxy = (y<MAXY-1)?y+1:MAXY-1;
  207.  
  208.   while (changes)
  209.     {
  210.       changes = 0;
  211.       set_temp_to_patternmat();
  212.       for (i = minx; i <= maxx; i++)
  213.     for (j = miny; j <= maxy; j++)
  214.       if (patternmat[i][j] == 0)
  215.       {
  216.         /*  Check northern neighbor.  */
  217.         if (i > 0)
  218.           {
  219.         if (patternmat[i-1][j])
  220.           {
  221.             if (p[i][j] == 0)
  222.               {
  223.             changes++;
  224.             if (i + 1 > maxx)
  225.               maxx = (i+1<MAXX-1)?i+1:MAXX-1;
  226.             newpatternmat[i][j] = mark[i][j] = 1;
  227.               }
  228.             else
  229.               {
  230.             if (owner == 0)
  231.               owner = p[i][j];
  232.             else if (owner != p[i][j])
  233.               owner = -1;
  234.               }
  235.           }
  236.           }
  237.  
  238.         /*  Check eastern neighbor.  */
  239.         if (j < MAXY - 1)
  240.           {
  241.         if (patternmat[i][j+1])
  242.           {
  243.             if (p[i][j] == 0)
  244.               {
  245.             changes++;
  246.             if (j - 1 < miny)
  247.               miny = (j-1>0)?j-1:0;
  248.             newpatternmat[i][j] = mark[i][j] = 1;
  249.               }
  250.             else
  251.               {
  252.             if (owner == 0)
  253.               owner = p[i][j];
  254.             else if (owner != p[i][j])
  255.               owner = -1;
  256.               }
  257.           }
  258.           }
  259.  
  260.         /*  Check southern neighbor.  */
  261.         if (i < MAXX - 1)
  262.           {
  263.         if (patternmat[i+1][j])
  264.           {
  265.             if (p[i][j] == 0)
  266.               {
  267.             changes++;
  268.             if (i - 1 < minx)
  269.               minx = (i-1>0)?i-1:0;
  270.             newpatternmat[i][j] = mark[i][j] = 1;
  271.               }
  272.             else
  273.               {
  274.             if (owner == 0)
  275.               owner = p[i][j];
  276.             else if (owner != p[i][j])
  277.               owner = -1;
  278.               }
  279.           }
  280.           }
  281.  
  282.         /*  Check western neighbor.  */
  283.         if (j > 0)
  284.           {
  285.         if (patternmat[i][j-1])
  286.           {
  287.             if (p[i][j] == 0)
  288.               {
  289.             changes++;
  290.             if (j + 1 > maxy)
  291.               maxy = (j+1<MAXY-1)?j+1:MAXY-1;
  292.             newpatternmat[i][j] = mark[i][j] = 1;
  293.               }
  294.             else
  295.               {
  296.             if (owner == 0)
  297.               owner = p[i][j];
  298.             else if (owner != p[i][j])
  299.               owner = -1;
  300.               }
  301.           }
  302.           }
  303.       }
  304.       set_patternmat_to_temp();
  305.     }
  306.  
  307.   for (i = 0; i < MAXX; i++)
  308.     for (j = 0; j < MAXX; j++)
  309.       if (patternmat[i][j])
  310.     ownermat[i][j] = owner;
  311. }
  312.  
  313. void find_owner(void)
  314. /*  Determine ownership of all empty points.  */
  315. {
  316.   int i, j;
  317.  
  318.   for (i = 0; i < MAXX; i++)
  319.     for (j = 0; j < MAXY; j++)
  320.       {
  321.     mark[i][j] = 0;
  322.     ownermat[i][j] = 0;
  323.       }
  324.  
  325.   for (i = 0; i < MAXX; i++)
  326.     for (j = 0; j < MAXY; j++)
  327.       if ((p[i][j] == 0) && (mark[i][j] == 0))
  328.     find_owner0(i, j);
  329. }
  330.  
  331. int surrounds_territory(int x, int y)
  332. /*  Determine if the stones at x, y surround any territory.  */
  333. {
  334.   int i, j, currentcolor = p[x][y], changes = 1, minx, maxx, miny, maxy;
  335.  
  336.   for (i = 0; i < MAXX; i++)
  337.     for (j = 0; j < MAXY; j++)
  338.       patternmat[i][j] = 0;
  339.  
  340.   patternmat[x][y] = 1;
  341.   minx = (x>0)?x-1:0;
  342.   maxx = (x<MAXX-1)?x+1:MAXX-1;
  343.   miny = (y>0)?y-1:0;
  344.   maxy = (y<MAXY-1)?y+1:MAXY-1;
  345.  
  346.   while (changes)
  347.     {
  348.       changes = 0;
  349.       set_temp_to_patternmat();
  350.       for (i = 0; i < MAXX; i++)
  351.     for (j = 0; j < MAXY; j++)
  352.       if (patternmat[i][j] == 0)
  353.       {
  354.         /*  Check northern neighbor.  */
  355.         if (i > 0)
  356.           {
  357.         if (patternmat[i-1][j])
  358.           {
  359.             if (p[i][j] == 0)
  360.               {
  361.             if (ownermat[i][j] == currentcolor)
  362.               return 1;
  363.               }
  364.             else
  365.               {
  366.             if (p[i][j] == currentcolor)
  367.               {
  368.                 changes++;
  369.                 if (i + 1 > maxx)
  370.                   maxx = (i+1<MAXX-1)?i+1:MAXX-1;
  371.                 newpatternmat[i][j] = 1;
  372.               }
  373.               }
  374.           }
  375.           }
  376.  
  377.         /*  Check eastern neighbor.  */
  378.         if (j < MAXY - 1)
  379.           {
  380.         if (patternmat[i][j+1])
  381.           {
  382.             if (p[i][j] == 0)
  383.               {
  384.             if (ownermat[i][j] == currentcolor)
  385.               return 1;
  386.               }
  387.             else
  388.               {
  389.             if (p[i][j] == currentcolor)
  390.               {
  391.                 changes++;
  392.                 if (j - 1 < miny)
  393.                   miny = (j-1>0)?j-1:0;
  394.                 newpatternmat[i][j] = 1;
  395.               }
  396.               }
  397.           }
  398.           }
  399.  
  400.         /*  Check southern neighbor.  */
  401.         if (i < MAXX - 1)
  402.           {
  403.         if (patternmat[i+1][j])
  404.           {
  405.             if (p[i][j] == 0)
  406.               {
  407.             if (ownermat[i][j] == currentcolor)
  408.               return 1;
  409.               }
  410.             else
  411.               {
  412.             if (p[i][j] == currentcolor)
  413.               {
  414.                 changes++;
  415.                 if (i - 1 < minx)
  416.                   minx = (i-1>0)?i-1:0;
  417.                 newpatternmat[i][j] = 1;
  418.               }
  419.               }
  420.           }
  421.           }
  422.  
  423.         /*  Check western neighbor.  */
  424.         if (j > 0)
  425.           {
  426.         if (patternmat[i][j-1])
  427.           {
  428.             if (p[i][j] == 0)
  429.               {
  430.             if (ownermat[i][j] == currentcolor)
  431.               return 1;
  432.               }
  433.             else
  434.               {
  435.             if (p[i][j] == currentcolor)
  436.               {
  437.                 changes++;
  438.                 if (j + 1 > maxy)
  439.                   maxy = (j+1<MAXY-1)?j+1:MAXY-1;
  440.                 newpatternmat[i][j] = 1;
  441.               }
  442.               }
  443.           }
  444.           }
  445.       }
  446.       set_patternmat_to_temp();
  447.     }
  448.  
  449.   return 0;
  450. }
  451.  
  452. void score_game(void)
  453. /*  Score the game and remove dead stones.  */
  454. {
  455.   int i, j, k, l, changes = 1, num_in_pattern;
  456.  
  457.   for (i = 0; i < MAXX; i++)
  458.     for (j = 0; j < MAXY; j++)
  459.       scoringmat[i][j] = 0;
  460.  
  461.   while (changes)
  462.     {
  463.       changes = 0;
  464.       find_owner();
  465.  
  466.       for (i = 0; i < MAXX; i++)
  467.     for (j = 0; j < MAXY; j++)
  468.       if ((p[i][j] != 0) && (scoringmat[i][j] == 0))
  469.         {
  470.           if (surrounds_territory(i, j))
  471.         {
  472.           find_pattern_in_board(i, j);
  473.  
  474.           for (k = 0; k < MAXX; k++)
  475.             for (l = 0; l < MAXY; l++)
  476.               if (patternmat[k][l])
  477.             scoringmat[k][l] = p[k][l];
  478.         }
  479.           else
  480.         {
  481.           find_pattern_in_board(i, j);
  482.           set_temp_to_p();
  483.           num_in_pattern = 0;
  484.  
  485.           for (k = 0; k < MAXX; k++)
  486.             for (l = 0; l < MAXY; l++)
  487.               if (patternmat[k][l])
  488.             {
  489.               p[k][l] = 0;
  490.               num_in_pattern++;
  491.             }
  492.  
  493.           find_owner();
  494.  
  495.           if ((ownermat[i][j] != -1) && (ownermat[i][j] != tempmat[i][j]))
  496.             {
  497.               if (tempmat[i][j] == 2)
  498.             blackCaptured += num_in_pattern;
  499.               else
  500.             whiteCaptured += num_in_pattern;
  501.               changes++;
  502.             }
  503.           else
  504.             {
  505.               set_p_to_temp();
  506.               find_owner();
  507.             }
  508.         }
  509.         }
  510.     }
  511.  
  512.   blackTerritory = 0;
  513.   whiteTerritory = 0;
  514.  
  515.   for (i = 0; i < MAXX; i++)
  516.     for (j = 0; j < MAXY; j++)
  517.       {
  518.     if (ownermat[i][j] == 2)
  519.       blackTerritory++;
  520.     if (ownermat[i][j] == 1)
  521.       whiteTerritory++;
  522.       }
  523. }
  524.