home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 207.lha / BackGammon / eval.c < prev    next >
C/C++ Source or Header  |  1988-12-27  |  13KB  |  504 lines
  1. /********************************************************************/
  2. /*                                                                  */
  3. /*  Hoser BackGammon version 1.0                                    */
  4. /*                                                                  */
  5. /*      Robert Pfister                                              */
  6. /*                                                                  */
  7. /*      Rfd#3 Box 2340                home:(207)-873-3520           */
  8. /*      Waterville, Maine 04901                                     */
  9. /*                                                                  */
  10. /*      Pfister_rob%dneast@dec.decwrl                               */
  11. /*                                                                  */
  12. /*                                                                  */
  13. /*  Copyright  June,1987 all rights reserved.                       */
  14. /*                                                                  */
  15. /*  This program will play a game of backgammon at the novice level */
  16. /*                                                                  */
  17. /*  The code is in 4 parts...                                       */
  18. /*                                                                  */
  19. /*   /   1) back.c     - main driver                                */
  20. /* \/    2) eval.c     - evaluation of moves                        */
  21. /*       3) backscn.c  - screen stuff..                             */
  22. /*       4) backmenu.c - menu stuff, help text, and ``decoder''     */
  23. /*                                                                  */
  24. /* this was compiled under Manx 3.20a, using long integers          */
  25. /*                                                                  */
  26. /********************************************************************/
  27.  
  28. /****************************************************************/
  29. /* These routines  do all the thinking for the computer side    */
  30. /*                                                              */
  31. /* (read: the magic lives here)                                 */
  32. /****************************************************************/
  33.  
  34. #define Running  1
  35. #define Blocking 2
  36. #define Pegging  3
  37. #define BackGame 4
  38.  
  39. extern int MeInc;
  40.  
  41. int Moves =0;
  42. int AvgPos=0;
  43. int LastVun=0;
  44.  
  45. int list[4][2];
  46. int count=0;
  47. int max=0;
  48. int GameStat=0;
  49. int MaxStat=0;
  50.  
  51. int block[26]={-1,1,2,3,4,5,6,  8,9,10,11,12,13   ,14,15,17,21,25,27,
  52.                  25,21,19,8,3,1,0};
  53.  
  54. int run[26]  ={-1,1,2,3,4,5,6,  15,16,17,18,19,20,  30,31,32,33,34,35,
  55.                50,51,52,53,54,55};
  56.  
  57. int peg[26]  ={-20,0,0,0,0,0,0 ,1,2,3,4,5,6, 30,31,32,33,34,35,
  58.                 50,49,48,47,46,45,0};
  59.  
  60. int back[26]={20,40,30,20,10,5,0 ,1,2,3,4,5,6, 30,31,32,30,40,50,
  61.                 50,49,48,30,20,10,0};
  62.  
  63. Eval(Board)
  64. int Board[26];
  65. {
  66.   register int i;
  67.   int num,value,me,you;
  68.   int Msum,Ysum;
  69.  
  70.  
  71.   num=0;
  72.   value=0;
  73.  
  74.   /* see who is ahead */
  75.   Msum=0;
  76.   for(i=0;i<=24;i++)
  77.      if (Board[i]>0)
  78.         Msum+=(25-i)*Board[i];
  79.  
  80.   Ysum=0;
  81.   for(i=1;i<=25;i++)
  82.      if (Board[i]<0)
  83.         Ysum-=i*Board[i];
  84.  
  85.   for (i= 0;(i<=24)&&(Board[i]<=0);i++);    /* first occurance of me  */
  86.   me=i;
  87.   for (i=25;(i>=1)&&(Board[i]>=0);i--);/* first occurance of you */
  88.   you=1;
  89.                     GameStat=BackGame; /* default case */
  90.   if (Ysum>Msum+10) GameStat=Running;  /* if closer to winning than them */
  91.   if (you>18)       GameStat=Blocking; /* if a opponent is within the bounds */
  92.   if (me>you)       GameStat=Pegging;  /* if complete separation */
  93.  
  94.   for(i=0;i<=24;i++)
  95.    {
  96.     if (Board[i]>0)
  97.        {
  98.         num=num+Board[i];
  99.         switch(GameStat)
  100.            {
  101.             case BackGame:
  102.                  value+=back[i]*Board[i];
  103.                  if (i<18) value+=3*vunerable(Board,i);
  104.                  break;
  105.  
  106.             case Pegging:
  107.                  value+=peg[i]*Board[i];
  108.                  break;
  109.  
  110.             case Blocking:
  111.                  value+=block[i]*Board[i];
  112.                  value-=4*vunerable(Board,i);
  113.                  value-=6*doom(Board);
  114.                  break;
  115.  
  116.             case Running:
  117.                  value+=run[i]*Board[i];
  118.                  value-=6*vunerable(Board,i);
  119.                  value-=6*doom(Board);
  120.                  break;
  121.             } 
  122.         }
  123.      }
  124.  
  125.   /* add points for taking men off...more if no chance of being taken */
  126.  
  127.   if (GameStat==Pegging)  value+=(15-num)*300;
  128.                      else value+=(15-num)*75;
  129.  
  130.  
  131.   /* if blocking game, check the block length...add points for more */
  132.  
  133.   switch(GameStat)
  134.     {
  135.      case BackGame:
  136.           num=0;
  137.           for(i=0;i<=6;i++) if ((Board[i]>0)&&(you>i)) num++;
  138.           value+=100*num;
  139.           num=0;
  140.           for(i=15;i<=21;i++) if (Board[i]>0) num+=Board[i];
  141.           value+=30*num;
  142.           value-=100*Board[25];
  143.           num=0;
  144.           for(i=17;i<=23;i++) if (Board[i]>=2) num++;
  145.           value+=(num*300);
  146.           break;
  147.  
  148.      case Blocking:
  149.           num=0;
  150.           for(i=14;i<=22;i++)
  151.              {
  152.               if (Board[i]>=2) num++;
  153.               if ((you>i)&&(Board[i]>=2)) num++;
  154.               }
  155.           value+=(num*400);
  156.           num=0;
  157.           for(i=0;i<=17;i++) if (Board[i]>0) num+=(Board[i]*(18-i)*(18-i));
  158.           value-=num/1.5;
  159.           break;
  160.  
  161.      case Pegging:
  162.  
  163.      case Running:
  164.           num=0;
  165.           for(i=0;i<=17;i++) if (Board[i]>0) num++;
  166.           value-=10*num;
  167.           num=0;
  168.           for(i=0;i<=17;i++) if (Board[i]>0) num+=(Board[i]*(26-i)*(26-i));
  169.           value-=num;
  170.           break;
  171.       }
  172.  
  173.   return(value);
  174. }
  175.  
  176.  
  177.  
  178. vunerable(Board,pos)
  179. int Board[26],pos;
  180. {
  181.  register int i,j,k;
  182.  
  183.  int value;
  184.  int HitTable[7][7];
  185.  
  186.  value=0;
  187.  
  188.  if ( (Board[pos]<0) || (pos==0) || (Board[pos]>=2) ) return (value);
  189.  
  190.  
  191. /*  intitialize table */
  192.  for(i=1;i<=6;i++)
  193.     for(j=1;j<=6;j++)
  194.        HitTable[i][j]=0;
  195.  
  196. /* look at all dice within 12 places */
  197.    for(i=1;i<=12;i++)
  198.       {
  199.       if (pos-i>=0)  /* within the board */
  200.        if (Board[pos-i]<0) /* there peice exists at that place */
  201.          if (valid(Board,pos,pos-i,i))  /* can capture legally */
  202.             {
  203.              /*--------------------------------------------------*/
  204.              /* find hits for one die */
  205.               if (i<=6)
  206.                  for(j=1;j<=6;j++)
  207.                    {
  208.                     HitTable[i][j]=1;
  209.                     HitTable[j][i]=1;
  210.                     }
  211.  
  212.               /* figure out combinations */
  213.                  for (j=1;j<i;j++)
  214.                      {
  215.                        /* first die is j, second is k */
  216.                         k=i-j;
  217.  
  218.                         /* check legality of the intermediate place */
  219.  
  220.                         if (valid (Board,pos,pos-j,j))
  221.                            {
  222.                             HitTable[k][j]=1;
  223.                             HitTable[j][k]=1;
  224.                             }
  225.  
  226.                        if (valid (Board,pos,pos-k,k))
  227.                           {
  228.                            HitTable[k][j]=1;
  229.                            HitTable[j][k]=1;
  230.                            }
  231.                       }
  232.              /*---------------------------------------------------*/
  233.              }   /* end of valid (board,position) */
  234.  
  235.        } /* end of for i */
  236.  
  237. /* find how many hits in that table */
  238.   for(i=1;i<=6;i++)
  239.      for(j=1;j<=6;j++)
  240.         if (HitTable[i][j]==1) value++;
  241.  
  242.  LastVun=value;
  243.  
  244.  return(value);
  245.  
  246. }  /* end of vunerable */
  247.  
  248.  
  249. doom(Board)
  250. int Board[26];
  251. {
  252. register int i,value;
  253.  
  254.    if (LastVun==0) return(0);
  255.  
  256. /* find the "doom" factor..the possibilty of getting outa being captured */
  257.   for(i=1;i<=10;i++) if (Board[i]<-1) value+=5;
  258.  
  259.  return(value);
  260. }
  261.  
  262. /* copy b1 to b2 */
  263. CopyBoard(b1,b2)
  264. int b1[26],b2[26];
  265. {
  266.   register int i;
  267.   for (i=0;i<=25;i++)
  268.      {
  269.        b2[i]=b1[i];
  270.       } /* end for */
  271.  } /* end of Copy */
  272.  
  273. DoMove(Board)
  274. int Board[26];
  275. {
  276.  int j,sum;
  277.  
  278.  AvgPos+=count;
  279.  
  280.  /* dont do anything if nothing to be done  */
  281.  if (count==0) 
  282.     {
  283.      DoMenuStrip("Cant move from this position!!");
  284.      return(0);
  285.      }
  286.  
  287.  PutMoveNumber(count);
  288.  
  289.   /* show move */
  290.  for(j=0;j<=3;j++)
  291.     if (list[j][0]!=-1)
  292.        {
  293.         BlinkPeice(Board,list[j][0]);
  294.         update(Board,list[j][0],      list[j][1] ,1);
  295.         PutSpike(    list[j][0],Board[list[j][0]]  );
  296.         BlinkPeice(Board,list[j][1]);
  297.         }
  298.  
  299.  /* touch up the bar's */
  300.  PutSpike(0 ,Board[ 0]);
  301.  PutSpike(25,Board[25]);
  302.  
  303.  }
  304.  
  305. FindMove(Board,Dice,i1,i2,i3,i4)
  306. int Board[26],Dice[4],i1,i2,i3,i4;
  307. {
  308.  int j;
  309.  
  310.  if ((count<50)||(10*(count/10)==count))
  311.      PutMoveNumber(count);
  312.  j=Eval(Board);
  313.  if ((count==1)||(j>max))
  314.     {
  315.      max=j;
  316.      MaxStat=GameStat;
  317.      list[0][0]=i1; list[0][1]=i1+Dice[0];
  318.      list[1][0]=i2; list[1][1]=i2+Dice[1];
  319.      list[2][0]=i3; list[2][1]=i3+Dice[2];
  320.      list[3][0]=i4; list[3][1]=i4+Dice[3];
  321.      }
  322.  }
  323.  
  324. GenerateMoves(Board,Dice)
  325. int Board[26],Dice[4];
  326. {
  327.  
  328. register int i;
  329.  
  330. int Dice2[4];
  331. count=0;
  332.  
  333. PutMoveNumber(count);
  334.  
  335. /* check for doubles rolled */
  336. if (Dice[2]!=0)
  337.            {
  338.             Find4(Board,Dice);
  339.                 if (count!=0) return(0);
  340.                 MeInc++;
  341.             Find3(Board,Dice);
  342.                 if (count!=0) return(0);
  343.             Find2(Board,Dice);
  344.                 if (count!=0) return(0);
  345.             }
  346.       else
  347.           {
  348.            Find2(Board,Dice);
  349.  
  350.            Dice2[0]=Dice[1];
  351.            Dice2[1]=Dice[0];
  352.            Dice2[2]=Dice[2];
  353.            Dice2[3]=Dice[3];
  354.  
  355.            Find2(Board,Dice2);
  356.              if (count!=0) return(0);
  357.            MeInc++;
  358.            }
  359.  
  360.  Find1(Board,Dice);
  361.  return(0);
  362.  
  363.  } /* end of generate */
  364.  
  365.  
  366. Find4(Board,Dice)
  367. int Board[26],Dice[4];
  368. {
  369.  register int i1,i2,i3,i4;
  370.  
  371.  int Board1[26],Board2[26],Board3[26],Board4[26];
  372.  for (i1=0;i1<=24;i1++)
  373.    {
  374.    if (Board[i1]>0)
  375.    if (valid(Board,i1,i1+Dice[0],Dice[0]))
  376.       {
  377.       CopyBoard(Board,Board1);
  378.       update(Board1,i1,i1+Dice[0],1);
  379.       for (i2=0;i2<=24;i2++)
  380.          {
  381.          if (Board1[i2]>0)
  382.          if (valid(Board1,i2,i2+Dice[1],Dice[1]))
  383.             {
  384.             CopyBoard(Board1,Board2);
  385.             update(Board2,i2,i2+Dice[1],1);
  386.             for (i3=0;i3<=24;i3++)
  387.                 {
  388.                  if (Board2[i3]>0)
  389.                  if (valid(Board2,i3,i3+Dice[2],Dice[2]))
  390.                     {
  391.                     CopyBoard(Board2,Board3);
  392.                     update(Board3,i3,i3+Dice[2],1);
  393.                     for (i4=0;i4<=24;i4++)
  394.                         {
  395.                         if (Board3[i4]>0)
  396.                         if (valid(Board3,i4,i4+Dice[3],Dice[3]))
  397.                            {
  398.                            count++;
  399.                            CopyBoard(Board3,Board4);
  400.                            update(Board4,i4,i4+Dice[3],1);
  401.                            FindMove(Board4,Dice,i1,i2,i3,i4);
  402.                            }
  403.                         } /* end for i4 */ 
  404.                     } /* end valid Dice[2] */
  405.                 } /* end for i3 */
  406.             } /* end valid Dice[1] */
  407.          } /* end for i2 */
  408.       } /* end if Valid Dice[0] */
  409.    } /* end for i1 */
  410. return(0);
  411. } /* end of Find4 */
  412.  
  413.  
  414.  
  415. Find3(Board,Dice)
  416. int Board[26],Dice[4];
  417. {
  418.  register int i1,i2,i3;
  419.  
  420.  int Board1[26],Board2[26],Board3[26];
  421.  
  422.  for (i1=0;i1<=24;i1++)
  423.    {
  424.    if (Board[i1]>0)
  425.    if (valid(Board,i1,i1+Dice[0],Dice[0]))
  426.       {
  427.       CopyBoard(Board,Board1);
  428.       update(Board1,i1,i1+Dice[0],1);
  429.       for (i2=0;i2<=24;i2++)
  430.          {
  431.          if (Board1[i2]>0)
  432.          if (valid(Board1,i2,i2+Dice[1],Dice[1]))
  433.             {
  434.             CopyBoard(Board1,Board2);
  435.             update(Board2,i2,i2+Dice[1],1);
  436.             for (i3=0;i3<=24;i3++)
  437.                 {
  438.                  if (Board2[i3]>0)
  439.                  if (valid(Board2,i3,i3+Dice[2],Dice[2]))
  440.                     {
  441.                      count++;
  442.                      CopyBoard(Board2,Board3);
  443.                      update(Board3,i3,i3+Dice[2],1);
  444.                      FindMove(Board3,Dice,i1,i2,i3,-1);
  445.                     } /* end valid Dice[2] */
  446.                 } /* end for i3 */
  447.             } /* end valid Dice[1] */
  448.          } /* end for i2 */
  449.       } /* end if Valid Dice[0] */
  450.    } /* end for i1 */
  451.  return(0);
  452. } /* end of Find3 */
  453.  
  454. Find2(Board,Dice)
  455. int Board[26],Dice[4];
  456.  
  457. {
  458.  register int i1,i2;
  459.  int Board1[26],Board2[26];
  460.  
  461.  for (i1=0;i1<=24;i1++)
  462.    {
  463.    if (Board[i1]>0)
  464.    if (valid(Board,i1,i1+Dice[0],Dice[0]))
  465.       {
  466.       CopyBoard(Board,Board1);
  467.       update(Board1,i1,i1+Dice[0],1);
  468.       for (i2=0;i2<=24;i2++)
  469.          {
  470.          if (Board1[i2]>0)
  471.          if (valid(Board1,i2,i2+Dice[1],Dice[1]))
  472.             {
  473.             count++;
  474.             CopyBoard(Board1,Board2);
  475.             update(Board2,i2,i2+Dice[1],1);
  476.             FindMove(Board2,Dice,i1,i2,-1,-1);
  477.             }/* end valid Dice[1] */
  478.          }/* end for i2 */
  479.       }/* end if Valid Dice[0] */
  480.    }/* end for i1 */
  481. }/* end find2 */
  482.  
  483. Find1(Board,Dice)
  484. int Board[26],Dice[4];
  485. {
  486. register int i1,i2;
  487. int Board1[26],Dice2[4];
  488.  
  489. for (i2=0;i2<=1;i2++)
  490.    {
  491.    Dice2[0]=Dice[i2]; Dice2[1]=0; Dice2[2]=0; Dice2[3]=0;
  492.  
  493.    for (i1=0;i1<=24;i1++)
  494.        if (Board[i1]>0) if (valid(Board,i1,i1+Dice[i2],Dice[i2]))
  495.           {
  496.           count++;
  497.           CopyBoard(Board,Board1);
  498.           update(Board1,i1,i1+Dice[i2],1);
  499.           FindMove(Board1,Dice2,i1,-1,-1,-1);
  500.           }
  501.      }
  502.      return(0);
  503. } /* end of find1 */
  504.