home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / simtel / cpmug / cpmug048.ark / PRESSUP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1986-11-08  |  8.0 KB  |  344 lines
  1.  
  2.  
  3. /* Press-up game...
  4.        pressup <options>
  5.   where <options> may include
  6.        -f      Machine goes first
  7.        -d n    Search depth is n moves (default 3)
  8.         (greater search depths take longer...but
  9.          play better!!)
  10.        -b    Print machine's evaluation of its moves.
  11.  
  12.     THIS PROGRAM WILL ONLY WORK ON TERMINALS HAVING
  13.     LOWER CASE CHARACTERS!!!!!!!!!!!!!!!!!!!!!!!!!!
  14.  
  15.     This excellent program was written by:
  16.         Prof. Steve Ward
  17.         Director, Real-Time Systems Group
  18.         MIT Lab for Computer Science
  19.         Cambridge, Massachussetts, 02139
  20.  
  21.         (slightly modified by Leor Zolman)
  22.  
  23.     The game of Press-Ups is played as follows:
  24.     The board is a n by n array of pegs, each of
  25.     which is standing up at the start of the game. Pegs
  26.     come in 3 colors: Red (yours), Blue (the machine's),
  27.     and white (periods, actually; they're neutral.)
  28.  
  29.     The first player to move must"push down" a neutral
  30.     peg. Thereafter, players take turns pushing down pegs,
  31.     where each peg pushed must be adjacent to the last one
  32.     pushed.
  33.  
  34.     Pegs are named by giving a letter and a number, for the
  35.     row and column of the desired peg.
  36.  
  37.     As soon as a player gets all of his pegs down, he wins.
  38.     When there are no more legal moves to play,
  39.     the player with the most of his own colored pegs down
  40.     is the winner.
  41.  
  42.     Watch out...at search depths of 6 or more, this program
  43.     plays a mean game!!!
  44. */
  45.  
  46. #define SIDE        7    /* Dimension of board    */
  47.  
  48. #define HISFIRST (SIDE*2+1)    /* His best first move    */
  49. #define MYFIRST (SIDE+SIDE/2-1) /* My best first move    */
  50. #define BELL 0x07
  51. #define BACKSP 0x08
  52.  
  53. char toupper();
  54.  
  55. int    Depth;        /* Search depth (default = 3)    */
  56. int    Helpflag;
  57. char    FFlag,        /* -f option: machine goes first */
  58.     BFlag;        /* Debugging flag            */
  59. char    Startflag;    /* True on first move only */
  60.  
  61. char *image;
  62. int Adj[16];
  63.  
  64. int    BestMove;        /* Returned by search    */
  65.  
  66. #define BBOARD struct bord
  67.  
  68. struct bord
  69.   {    char board[SIDE*SIDE];
  70.     int  star;
  71.     char red;
  72.     char blue;
  73.   };
  74.  
  75. BBOARD initb;
  76.  
  77. BBOARD master, savebd;
  78.  
  79. char string[20];
  80.  
  81. CheckWin(bp)
  82.  BBOARD *bp;
  83.  {    int i;
  84.     i = search(bp,1,1,-32000,-32000);
  85.     if (BestMove >= 0) return 0;
  86.  
  87.     if (i>0) printf("I win!\n");
  88.     if (i<0) printf("You win!\n");
  89.     if (i==0) printf("Tie game!\n");
  90.     return 1;
  91.     }
  92.  
  93. asknew()
  94. {
  95.     printf("\nAnother game? ");    
  96.     if (toupper(getchar()) != 'Y') exit();
  97.     printf("\n");
  98. }
  99.  
  100. main(argc,argv)
  101.  char **argv;
  102.   {    int i,j; char *arg;
  103.     FFlag  = BFlag = 0;
  104.     image = ".rbXRB";
  105.     initw(Adj,"-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1");
  106.  
  107.     Depth = 3;
  108.     for (i=1; i<argc; i++)
  109.      {if (*(arg = argv[i])=='-') switch (toupper(*++arg)) {
  110.         case 'D':    Depth = atoi(argv[++i]); continue;
  111.         case 'F':    FFlag++; continue;
  112.         case 'B':    BFlag++; continue;
  113.         default:    printf("Illegal argument: '%1s'\n",argv[i]);
  114.                 exit(); }
  115.        else {printf("Illegal argument: '%1s'\n",arg); exit(); }}
  116.  
  117. ngame:
  118.     Startflag = 1;
  119.     Helpflag = 0;
  120.     for (i=0; i<(SIDE*SIDE); i++) initb.board[i] = 0;
  121.      for (j=1; j<(SIDE-1); j++)
  122.         { initb.board[j] = 1;
  123.           initb.board[(SIDE*SIDE-1)-j] = 1;
  124.           initb.board[SIDE*j] = 2;
  125.           initb.board[SIDE*j + SIDE-1] = 2; };
  126.     initb.star = -1; initb.red = 0; initb.blue = 0;
  127.  
  128.     bcopy(&initb,&master);
  129.     pboard(&master); bcopy(&master,&savebd);
  130.  
  131.     for(;;)
  132.       {    if (FFlag) { FFlag = 0; goto Mine; }
  133.         if (CheckWin(&master)) {
  134.             asknew();
  135.             goto ngame;
  136.          }
  137.         i = getmove();
  138.         if (i == 'Q') {    
  139.             asknew();
  140.             goto ngame;
  141.          }
  142.         dmove(i);
  143.         if (CheckWin(&master)) {
  144.             asknew();
  145.             goto ngame;
  146.          }
  147.     Mine:    printf("I'm thinking...\n");
  148.         i = search(&master,Depth,1,-32000,-32000);
  149.         if (BFlag) printf("Eval = %d\n",i); 
  150.         dmove(BestMove);
  151.         if (i > 500) printf("I've got you!\n"); 
  152.         if (i < -500) printf("You've got me!\n"); 
  153.  
  154.       }
  155.   }
  156.  
  157.  
  158. pboard(bp)
  159. BBOARD *bp;
  160.   {    int i, j, n;
  161.     char letter;
  162.     letter = 'A';
  163.     printf("\n\n     ");
  164.     for (i=0; i<SIDE; i++) printf("%-3d",i+1); printf("\n");
  165.     printf("   "); for (i=0; i<(2+3*SIDE); i++) printf("-"); printf("\n");
  166.     for (i = 0; i < SIDE; i++)
  167.       {    printf(" %c |",letter);
  168.         for (j = 0; j < SIDE; j++)
  169.          { if ((n = i*SIDE + j) == bp -> star) printf(" * ");
  170.            else printf(" %c ",image[bp->board[n]]); }
  171.         printf("| %c",letter++);
  172.  
  173.         if (i==0) printf("\tSearch Depth: %1d moves",
  174.                     Depth);
  175.         if (i==2) printf("\tScore:\tBlue(me)  Red(you)");
  176.         if (i==3) printf("\t\t  %1d        %1d",
  177.                 master.blue, master.red);
  178.         if (i==5) {
  179.             if (Helpflag)
  180.                 printf("\tYou've had help!");
  181.             if (Startflag)
  182.                 printf(FFlag?"\tI go first"
  183.                         :"\tYou go first");
  184.             Startflag = 0;
  185.          }
  186.         printf("\n");
  187.       }
  188.     printf("   "); for (i=0; i<(2+3*SIDE); i++) printf("-"); printf("\n");
  189.     printf("     ");
  190.     for (i=0; i<SIDE; i++) printf("%-3d",i+1); printf("\n");
  191.     printf("\n");
  192.   }
  193.  
  194. bcopy(p1,p2)
  195. BBOARD *p1, *p2;
  196.   {    int i;
  197.     i = (SIDE*SIDE)-1;
  198.     do p2->board[i] = p1->board[i];
  199.         while(i--);
  200.     p2->star = p1->star;
  201.     p2->red = p1->red;
  202.     p2->blue = p1->blue;
  203.   }
  204.  
  205.  
  206. /* display move #n */
  207.  
  208. dmove(n)
  209.   {
  210.     move(&master,n);
  211.     pboard(&master);
  212.     bcopy(&master,&savebd);
  213.   }
  214.  
  215. move(bp,n)
  216. BBOARD *bp;
  217.   {    int type;
  218.     type = bp->board[n] += 3;
  219.     if (type == 4) bp->red++;
  220.     else if (type == 5) bp->blue++;
  221.     bp->star = n;
  222.   }
  223.  
  224. search (bp,ddepth,who,alpha,beta)
  225. BBOARD *bp;
  226.   {    BBOARD new;
  227.     int i,j,k;
  228.     int myalpha,hisalpha,result,status;
  229.     int best;
  230.     int num;
  231.     int bestmove, ii, jj, n;
  232.     int SavStar;
  233.     int SavBlue;
  234.     int SavRed;
  235.     int Save;
  236.     char moves[9];
  237.     status = -1;
  238.     best = -32000;
  239.     num = 0;
  240.     SavStar = bp -> star;
  241.     SavBlue = bp -> blue;
  242.     SavRed    = bp -> red;
  243.     BestMove = -1;        /* No best move yet...    */
  244.  
  245.     if (SavStar == -1)    /* special case opening moves    */
  246.      { BestMove = HISFIRST;
  247.        if (who > 0) BestMove = MYFIRST;
  248.        return 0; };
  249.  
  250.     if (!ddepth--)
  251.         return(who * (bp->blue - bp->red));
  252.     if (bp->blue == (SIDE*2-4) || bp->red == (SIDE*2-4))
  253.         return(who*(bp->blue - bp->red)*1000);
  254.  
  255.           /* alpha-beta pruning   */
  256.       if (who>0)   { myalpha = bp->blue; hisalpha = bp->red; }
  257.        else     { myalpha = bp->red; hisalpha = bp->blue; }
  258.        myalpha += ddepth;  /* Most optimistic estimate. */
  259.        if (myalpha > (SIDE*2-4)) myalpha = (SIDE*2-4);
  260.        if (myalpha == (SIDE*2-4)) myalpha = 1000*(myalpha-hisalpha);
  261.        else myalpha -= hisalpha;
  262.        if (myalpha <= alpha) return best;
  263.  
  264.     k = bp->star;
  265.     i = k%SIDE;
  266.     j = k/SIDE;
  267.     for (n=0; n<8; n++)
  268.      {
  269.         if ((ii = i+Adj[n+n]) < 0 || ii >= SIDE) continue;
  270.         if ((jj = j+Adj[n+n+1]) < 0 || jj >= SIDE) continue;
  271.         if (bp->board[moves[num] = jj*SIDE + ii] < 3) num++; }
  272.     if (num == 0) return(who*(bp->blue - bp->red)*1000);
  273.     bestmove = moves[0];
  274.     for (i=0; i<num; i++)
  275.      { Save = bp->board[moves[i]];    move(bp,moves[i]);
  276.        k = -search(bp,ddepth,-who,beta,alpha);
  277.        bp->board[moves[i]] = Save;
  278.        bp->blue = SavBlue; bp->red = SavRed; bp->star = SavStar;
  279.        if (k > alpha) alpha = k;
  280.        if (k > best) { best = k; bestmove = moves[i]; }
  281.        if (k>100) break; }
  282.     BestMove = bestmove;
  283.     return best; }
  284.  
  285.  
  286.  
  287. Help()
  288.  {    printf("I'm thinking for you...\n");
  289.     Helpflag = 1;
  290.     search(&master,Depth,-1,-32000,-32000);
  291.     return BestMove; }
  292.  
  293. getmove()
  294.   {    int row, col, n;
  295.     int dc, dr;
  296.     int star2;
  297.     star2 = master.star;
  298. loop:    printf("\nYour move (z for help; p for board): ");
  299. getrow: for (;;) {
  300.          if ((row = toupper(getchar()) ) == 'Z') {
  301.             printf("\n");
  302.             return Help();
  303.             }
  304.  
  305.           if (row == 'Q') return row;
  306.           if (row == 'P') {
  307.             pboard(&master);
  308.             goto loop;
  309.            }
  310.           if (row == 0177 || row == '\n') goto err;
  311.           if (row<'A' || row> ('A'+SIDE-1))
  312.             putchar(BACKSP);
  313.             else break;
  314.         }
  315.     row -= 'A';
  316.  
  317.     for (;;) {
  318.          col = toupper(getchar());
  319.           if (col == 0177) {
  320.             putchar(BACKSP);
  321.             goto getrow;
  322.            }
  323.         if (col == '\n' || col == '\b') goto err;
  324.         if (col < '1' || col > ('0'+SIDE))
  325.             putchar(BACKSP);
  326.             else break;
  327.         }
  328.  
  329.     col -= '1';
  330.     n = row*SIDE + col;
  331.     dr = abs(row - star2/SIDE);
  332.     dc = abs(col - star2%SIDE);
  333.  
  334.     if ((star2 < 0 && master.board[n] == 0) ||
  335.         (dr < 2 && dc < 2 && master.board[n] < 3))
  336.         return(n);
  337.  
  338.    err:    putchar(BELL);
  339.     printf("  Illegal!  ");
  340.     goto loop;
  341.   }
  342.  
  343.  
  344.