home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Games / Abalone 1.4.2 / src / Strategies.c < prev    next >
Encoding:
Text File  |  1995-09-21  |  10.5 KB  |  464 lines  |  [TEXT/MPS ]
  1. //==========================================================================================//
  2. //                                                                                            //
  3. //    THE COMMENT GIVEN IN THIS FILE SHOULD BE MOST OF WHAT YOU NEED TO ADD A NEW STRATEGY    //
  4. //                                                                                            //
  5. //==========================================================================================//
  6.  
  7.  
  8. #define STRATEGIES_C
  9. #include "Strategies.h"
  10. #undef STRATEGIES_C
  11.  
  12.  
  13. #pragma segment More
  14.  
  15.  
  16. //    The easiest way to implement a new strategy is to make a BoardJudgeProc.
  17. //    The function TheFinalStrategy right below is all yours to try this,
  18. //    but first read more about the conventions used in this program right below.
  19.  
  20.  
  21. short
  22. TheFinalStrategy (BoardPtr board, short player)
  23. {
  24. #if ! defined (__SC__) && ! defined (__MWERKS__)
  25. #pragma unused(board, player)
  26. #endif
  27. //    Just pick a random value.
  28. //    This needs some improvement.
  29.     
  30.     return TickCount() % 100;
  31. }
  32.  
  33.  
  34.  
  35. //    To speed things up, you can optionally use a pruning function.
  36.  
  37. Boolean
  38. TheFinalGardener (short level, short value, short best)
  39. {
  40. #if ! defined (__SC__) && ! defined (__MWERKS__)
  41. #pragma unused(level, value, best)
  42. #endif
  43. //    A random half of the moves is worth a closer look.
  44.      
  45.      return TickCount() % 2;    //    true means: prune this, not interesting
  46. }
  47.  
  48.  
  49.  
  50. /* The conventions used in this program are different from the ones described
  51.  * in the contest announcement. (Sorry, this program was made before the contest.)
  52.  * I'm working on a translation between the contest convention and my own,
  53.  * which is halfway finished (from my convention to the official notation, see contest.h)
  54.  *
  55.  *********************** CONVENTIONS USED IN THIS PROGRAM ********************
  56.  *
  57.  * Fields are numbered from 1 to 61 (field number 0 has a special meaning; don't use it).
  58.  * Numbering starts at the topleft field in this program, first going to the right, then down.
  59.  *
  60.  *
  61.  *                        1        2        3        4        5
  62.  *
  63.  *
  64.  *                    6        7        8        9        10        11
  65.  *
  66.  *
  67.  *                12        13        14        15        16        17        18
  68.  *
  69.  *
  70.  *            19        20        21        22        23        24        25        26
  71.  *
  72.  *
  73.  *        27        28        29        30        31        32        33        34        35
  74.  *
  75.  *
  76.  *            36        37        38        39        40        41        42        43
  77.  *
  78.  *
  79.  *                44        45        46        47        48        49        50
  80.  *
  81.  *
  82.  *                    51        52        53        54        55        56
  83.  *
  84.  *
  85.  *                        57        58        59        60        61
  86.  *
  87.  *
  88.  *
  89.  * A BoardJudgeProc gets a BoardPtr and a short as parameters (see file Compute.h);
  90.  * It should return a short value telling how good it thinks a given board is.
  91.  * (A higher value means the board is judged better.)
  92.  * A MoveJudgeProc should return a value telling how much the value of the board
  93.  * has CHANGED because of the given move.
  94.  *
  95.  * The first parameter, the BoardPtr, points to a simple struct (see rules.h):
  96.  *
  97.  *         typedef struct _game
  98.  *         {
  99.  *             Fields    field;
  100.  *             Loot    loot;
  101.  *         } Board, *BoardPtr;
  102.  *
  103.  *
  104.  * The field field is  an array of 62 unsigned chars, representing the board to be judged.
  105.  * The first element is to be ignored (fields run from 1 to 61, remember?)
  106.  * Each of the 61 fields has the value 0 (empty), 1 (white) or 2 (black).
  107.  *
  108.  * For implementing a strategy, you probably don't need the loot field
  109.  * (the number of balls pushed off is stored here).
  110.  *
  111.  * Directions are numbered clockwise starting from 0 (left) to 5 (topleft) (see rules.h again)
  112.  */
  113.  
  114. /* OK, you could start programming with this knowledge,
  115.  * but I suggest you take a look at the example given below first.
  116.  */
  117.  
  118.  
  119. /* This is the table specifying the stragegies appearing in the strategy popup menu.
  120.  * Don't forget to sign in your strategy by filling out a nice name for it.
  121.  * If you don't have a pruning function, you can make it NULL.
  122.  */
  123.  
  124.  
  125. StrategyStruct    gStrategies[] =
  126. {
  127. //    These are the best strategies I can think of so far
  128.     { boardMiniMaxGreedy,            Arnold,                NULL,        kDefaultFast,    "\pTerminator III" },
  129.     { boardMiniMaxNoFliche,            Ross,                NULL,        kDefaultFast,    "\pDarth Vader" },
  130.     { moveMiniMax,            (BoardJudgeProc) Bill,        NULL,        kDefaultFast,    "\pWilliam Gates IV" },
  131.     { boardMiniMaxGreedy,            Frankie,            NULL,        kDefaultFast,    "\pFrankie Kruger" },
  132.     
  133. //    This is for you to improve upon. Add multiple if you like.
  134.     
  135.     #ifdef    TRY_THIS
  136.     { boardMiniMaxNoFliche, & TheFinalStrategy,            NULL,        kDefaultFast,    "\pWhat's in a name"  },
  137.     #endif
  138.  
  139.  
  140. //    The table should end with a NULL proc, don't remove
  141.     
  142.     { moveMiniMax,            NULL,                        NULL,        0,                "\pSentinel"  }
  143. };
  144.  
  145.  
  146.  
  147. //    A PruneJudgeProc.
  148. //    I don't have much success finding really good pruning functions yet.
  149.  
  150. Boolean
  151. Sarah (short level, short value, short best)
  152. {
  153.     #define MAXTICKS    500
  154.     
  155.     if (level == 2)
  156.     {
  157.     //    Pruning is always at 2 plies from the default lowest level:
  158.     //    one ply for me, and one for the opponent.
  159.     //    This way, results from different search depths can safely be compared
  160.          
  161.         return        (TickCount() > gMoveStartTicks + MAXTICKS)
  162.                 &&    value < best;
  163.     }    
  164.     return false;
  165. }
  166.  
  167.  
  168.  
  169. //    The following is a slight improvement over the old BoardJudgeProc explained above.
  170.  
  171. short
  172. Ross (BoardPtr board, short player)
  173. {
  174.     static Boolean            firstTime = true;
  175.     static short            value[kFields+1];
  176.     static unsigned char    bestNeighbour[kFields+1][2];
  177.     
  178.     register Field            f;
  179.     register unsigned char    d;
  180.     register short            boardValue = 0;
  181.     
  182.     if (firstTime)    //    initialise values for all fields
  183.     {    
  184.         firstTime = false;
  185.         
  186.         value[0] = 1 << 10;
  187.         
  188.         for (f = 1; f <= kFields; f++)
  189.         {
  190.             short d;
  191.                         
  192.             for (value[f] = 0, d = 0; d < 6; d++)
  193.                 value[f] += 1 << (10 - Distance (f, d));            
  194.  
  195.             value[f] /= 6;
  196.             value[f] = 1024 - value[f];
  197.         }
  198.         for (f = 1; f <= kFields; f++)
  199.         {
  200.             short d, best = 0;
  201.                         
  202.             for (d = right; d < down; d++)
  203.             {
  204.                 if (value[Neighbour (f, d)] > best)
  205.                 {
  206.                     best = value[Neighbour (f, d)];
  207.                     bestNeighbour[f][0] = Neighbour (f, d);
  208.                 }
  209.             }
  210.         }
  211.         for (f = kFields + 1; --f > 0; )
  212.         {
  213.             short d, best = 0;
  214.                         
  215.             for (d = right; d < down; d++)
  216.             {
  217.                 if (value[Neighbour (f, d)] > best)
  218.                 {
  219.                     best = value[Neighbour (f, d)];
  220.                     bestNeighbour[f][1] = Neighbour (f, d);
  221.                 }
  222.             }
  223.         }
  224.     }
  225.     
  226.     for (f = 1; f <= 61; f++)
  227.     {
  228.         if (board->field[f] == player)
  229.         {
  230.             boardValue += value[f];
  231.             
  232.             for (d = right; d < down; d++)
  233.             {
  234.                 if    (    board->field[f] == board->field[Neighbour (f,d)])
  235.                 {
  236.                     if (Neighbour (f, d) == bestNeighbour[f][0])
  237.                         boardValue += 32;
  238.  
  239.                     if (Neighbour (f, d) == bestNeighbour[f][1])
  240.                         boardValue += 32;
  241.                 }
  242.             }
  243.         }
  244.         else if (board->field[f])
  245.         {
  246.             boardValue -= value[f];
  247.  
  248.             for (d = right; d < down; d++)
  249.             {
  250.                 if    (    board->field[f] == board->field[Neighbour (f,d)])
  251.                 {
  252.                     if (Neighbour (f, d) == bestNeighbour[f][0])
  253.                         boardValue -= 32;
  254.  
  255.                     if (Neighbour (f, d) == bestNeighbour[f][1])
  256.                         boardValue -= 32;
  257.                 }
  258.             }
  259.         }
  260.     }
  261.     return boardValue;
  262. }
  263.  
  264.  
  265.  
  266. //    Example of a simple BoardJudgeProc that can be recoded to a MoveJudgeProc.
  267. //    Recoding is simple in this particular case, because only statical values are used.
  268. //    The result of recoding Paul would be Bill; you'll find him below.
  269.  
  270. short
  271. Paul (BoardPtr board, short player)
  272. {    
  273.     static Boolean firstTime = true;
  274.     static short value[kFields+1];
  275.     
  276.     Field f;
  277.     short boardValue = 0;
  278.     
  279.     if (firstTime)    //    initialise values for all fields
  280.     {    
  281.         short f;
  282.         
  283.         firstTime = false;
  284.         
  285.         for (f = 1; f <= kFields; f++)
  286.         {
  287.             short d;
  288.                         
  289.             for (value[f] = 0, d = 0; d < 6; d++)
  290.                 value[f] += 1 << (10 - Distance (f, d));            
  291.  
  292.             value[f] /= 6;
  293.         }
  294.     }
  295.     
  296. //    the values have been computed now, and can be used.
  297.         
  298.     for (f = 1; f <= 61; f++)
  299.     {
  300.         if (board->field[f] == player)
  301.         
  302.             boardValue += 1024 - value[f];
  303.         
  304.         else if (board->field[f] != empty)
  305.         
  306.             boardValue -= 1024 - value[f];
  307.     }
  308.     return boardValue;
  309. }
  310.  
  311.  
  312.  
  313. //    A reasonable MoveJudgeProc. Not as strong as Ross, but faster
  314.  
  315. short
  316. Bill (BoardPtr board, short player, MovePtr field)
  317. {
  318.     static Boolean firstTime = true;
  319.     static short value[kFields+1];
  320.     
  321.     Field f;
  322.     short boardValue = 0;
  323.     short direction = field[3];
  324.     
  325.     if (firstTime)    //    initialise values for all fields
  326.     {    
  327.         firstTime = false;
  328.         
  329.         for (f = 1; f <= kFields; f++)
  330.         {
  331.             short d;
  332.                         
  333.             for (value[f] = 0, d = 0; d < 6; d++)
  334.                 value[f] += 1 << (10 - Distance (f, d));            
  335.  
  336.             value[f] /= 6;
  337.         }
  338.     }
  339.     
  340.     if (field[1] != 0)    // fliche move
  341.     {
  342.         for (f = 0; f < 3 && field[f] != 0; f++)
  343.         {
  344.             boardValue += value[field[f]];
  345.             boardValue -= value[Neighbour (field[f], direction)];
  346.         }
  347.     }
  348.     else    //    normal move
  349.     {
  350.         for (f = field[0]; f != 0 && board->field[f] != empty; f = Neighbour (f, direction))
  351.         {
  352.             if (Neighbour (f, direction) == 0 && board->field[f] != empty)
  353.                 boardValue += 1024;            
  354.             
  355.             if (board->field[f] == player)
  356.             {
  357.                 boardValue += value[f];
  358.                 boardValue -= value[Neighbour (f, direction)];
  359.             }
  360.             else
  361.             {
  362.                 boardValue += value[Neighbour (f, direction)];
  363.                 boardValue -= value[f];
  364.             }
  365.         }
  366.     }
  367.     return boardValue;
  368. }
  369.  
  370.  
  371.  
  372. short
  373. Frankie (BoardPtr board, short player)
  374. {    
  375.     static Boolean firstTime = true;
  376.     static unsigned char dist[kFields+1][kFields+1];
  377.     
  378.     Field f, g;
  379.     long playerSumDist = 0, othersSumDist = 0;
  380.     short n_player = 0, n_others = 0;
  381.     Field playerField[14+1], othersField[14+1];
  382.     
  383.     if (firstTime)    //    Compute distances between all fields.
  384.     {    
  385.         Field h;
  386.         Boolean allDone;
  387.         
  388.         firstTime = false;
  389.         
  390.         for (f = 0; f <= kFields; f++)
  391.             for (g = 0; g <= kFields; g++)
  392.                 dist[f][g] = 0;
  393.         
  394.     //    Start with all known neighbours.
  395.             
  396.         for (f = 1; f <= kFields; f++)
  397.             for (g = 1; g <= kFields; g++)
  398.                 if (f != g && Neighbours (f, g))
  399.                     dist[f][g] = dist[g][f] = 1;
  400.                     
  401.     //    Compute all remaining distances.
  402.         
  403.         do    //    Until we found a minimal distance for each combination of fields.
  404.         {
  405.             allDone = true;
  406.             
  407.             for (f = 1; f <= kFields; f++)
  408.             {
  409.                 for (g = 1; g <= kFields; g++)
  410.                 {
  411.                     for (h = 1; h <= kFields; h++)
  412.                     {
  413.                         if (f == g || f == h || g == h)
  414.                             continue;
  415.                         
  416.                         if (dist[f][h] == 0 || dist[h][g] == 0)
  417.                         {
  418.                             allDone = false;
  419.                             continue;
  420.                         }
  421.                             
  422.                         if (dist[f][g] == 0 || dist[f][h] + dist[h][g] < dist[f][g])
  423.                         {
  424.                             allDone = false;
  425.                             dist[f][g] = dist[g][f] = dist[f][h] + dist[h][g];
  426.                         }
  427.                     }
  428.                 }
  429.             }
  430.         }
  431.         while (! allDone);
  432.     }
  433.         
  434. //    Find the fields for this player and for the other(s)
  435.     
  436.     for (f = 1; f <= 61; f++)
  437.     {
  438.         if (board->field[f] == player)
  439.             playerField[n_player] = f, n_player++;
  440.         else if (board->field[f] != empty)
  441.             othersField[n_others] = f, n_others++;
  442.     }
  443.  
  444. //    Now we can iterate over the fields using playerField[] and othersField[]
  445.     
  446.     for (f = 0; f < n_player-1; f++)
  447.     {
  448.         for (g = f+1; g < n_player; g++)
  449.         {
  450.             playerSumDist += dist[playerField[f]][playerField[g]]<<1;
  451.             playerSumDist += dist[playerField[f]][31];
  452.         }
  453.     }
  454.     for (f = 0; f < n_others-1; f++)
  455.     {
  456.         for (g = f+1; g < n_others; g++)
  457.         {
  458.             othersSumDist += dist[othersField[f]][othersField[g]]<<1;
  459.             othersSumDist += dist[othersField[f]][31];
  460.         }
  461.     }
  462.     return (short) (othersSumDist - playerSumDist + (n_player - n_others) * 256);
  463. }
  464.