home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 332_02 / ttt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-28  |  14.1 KB  |  573 lines
  1. /*----------------------------------------------------*- Fundamental -*-
  2.  
  3. Facility:        ttt(6)
  4.  
  5. File:            ttt.c
  6.  
  7. Associated files:    - [ none]
  8.  
  9. Description:        Plays the game of tic-tac-toe.
  10.  
  11. Author:            Leor Zolman
  12.  
  13. Editor:            Anders Thulin
  14.             Rydsvagen 288
  15.             S-582 50 Linkoping
  16.             SWEDEN
  17.  
  18. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  19.  
  20. Edit history :
  21.  
  22. Vers  Ed   Date           By                Comments
  23. ----  ---  ----------  ----------------  -------------------------------
  24.  1.0    0  1979-09-xx  Leor Zolman     Written in BDS C
  25.  1.1    1  1988-10-25  Anders Thulin     Added some comments; cleaned
  26.                          up generally
  27.  
  28. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  29.  
  30. /*---  Configuration:  --------------------------------------------------
  31.  
  32. System configuration options:
  33. =============================
  34.  
  35. Symbol:        Conformant systems:
  36.     
  37. ANSI        ANSI C
  38. BSD        BSD Unix, SunOS 3.5
  39. SV2        AT&T UNIX System V.2, AU/X
  40. XPG3        X/Open Portability Guide, ed. 3
  41.  
  42. If you have an ANSI C compiler, define ANSI. If not, choose one
  43. of the other symbols.
  44.  
  45. There are no program configuration options.
  46.  
  47. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  48.  
  49. #define    ANSI    1
  50. #define    BSD    0
  51. #define    SV2    0
  52. #define    XPG3    0
  53.  
  54. /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  55.  
  56. #if ANSI
  57. # include <ctype.h>
  58. # include <stdio.h>
  59. # include <stdlib.h>
  60. #endif
  61.  
  62. #if BSD
  63. # include <ctype.h>
  64. # include <stdio.h>
  65.   extern int rand();
  66.   extern int srand();        /* SunOS srand returns int? */
  67. # define EXIT_FAILURE    1
  68. # define EXIT_SUCCESS    0
  69. #endif
  70.  
  71. #if SV2
  72. # include <ctype.h>
  73. # include <stdio.h>
  74.   extern int  rand();
  75.   extern void srand();
  76. # define EXIT_FAILURE    1
  77. # define EXIT_SUCCESS    0
  78. #endif
  79.  
  80. #if XPG3
  81. # include <ctype.h>
  82. # include <stdio.h>
  83. # include <stdlib.h>
  84. #endif
  85.  
  86. /*---  Original comments to program:  ----------------------------------
  87.  
  88. BD Software presents:
  89.  
  90. Tic Tac Toe  (by exhaustive search)
  91.  
  92. written by Leor Zolman
  93. September 1979
  94.  
  95. This program was written for use as the crux of an article in BYTE
  96. (as yet to be published) on BDS C, structured programming and gaming.
  97.  
  98. It is also intended to get you addicted to C so you'll go out and buy
  99. the BD Software C Compiler
  100.  
  101. only $110 on CP/M disk from:
  102.  
  103.      tiny c associates
  104.     post office box 269
  105.     holmdel, new jersey 07733
  106.  
  107. The package includes the compiler, linking loader, library manager,
  108. standard library of functions, many interesting sample programs (such as
  109. "TELNET.C" for using your computer as a terminal and allowing I/O directly
  110. from modem to disk and vice-versa.) Also included is a copy of the best
  111. reference book available on the C language, written by the original
  112. implementors at Bell Labs (the package may be purchased without the book
  113. for $100.)
  114.  
  115. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  116.  
  117. #define    TRUE    1
  118. #define    FALSE    0
  119.  
  120. #define    X    1    /* The pieces on the board */
  121. #define O    5
  122. #define EMPTY    0
  123.  
  124. char board[9];        /* the playing board */
  125. char BEST;        /* move returned by "ttteval" */
  126.  
  127. int wins[8][3] = {    /* table of winning positions */
  128.     {0,1,2},
  129.     {3,4,5},
  130.     {6,7,8},
  131.     {0,3,6},
  132.     {1,4,7},
  133.     {2,5,8},
  134.     {0,4,8},
  135.     {2,4,6}
  136.      };
  137.  
  138. /*----------------------------------------------------------------------
  139.   Local functions:
  140. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  141.  
  142. #if __STDC__ != 0
  143.  static int  ask(char *s);
  144.  static int  cats(void);
  145.  static void clear(void);
  146.  static void display(void);
  147.  static int  getmove(void);
  148.  static int  ttteval(int me, int him);
  149.  static int  win(int p);
  150. #else
  151.  static int  ask();
  152.  static int  cats();
  153.  static void clear();
  154.  static void display();
  155.  static int  getmove();
  156.  static int  ttteval();
  157.  static int  win();
  158. #endif
  159.  
  160. /*----------------------------------------------------------------------
  161.  
  162. Routine:    ask
  163.  
  164. Description:    writes the string 's' to the terminal, and reads a
  165.         character in reply.
  166.  
  167.         If the character is 'y' or 'Y' TRUE is returned,
  168.         otherwise FALSE is returned.
  169.  
  170. Suggestions for improvement:
  171.  
  172.         1. Instead of returning FALSE if an error occurs,
  173.                we could ask again until we get a correct response.
  174.  
  175.             2. Rather than examining only the first character
  176.            read, we should skip all space characters until
  177.            we get something solid. If the line is empty,
  178.            ask again.
  179.  
  180.         3. Rather than testing for 'y' we should test for 'n'.
  181.            The reason is only that most languages use a
  182.            word that begins with 'n' for 'no', while very 
  183.            few languages use words beginning in 'y' for 'yes'.
  184.            Internationalization is the word! 
  185.  
  186. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  187.  
  188. static int ask(s)
  189. char *s;
  190. {
  191.   char string[160];    /* input string */
  192.   char c;        /* the response character */
  193.  
  194.   /*  1.  Print the string to standard output:  */
  195.  
  196.   printf(s);
  197.  
  198.   /*  2.  Read a string from standard input:  */
  199.  
  200.   if (fgets(string, sizeof(string), stdin) == 0) {    /* EOF or error */
  201.     return FALSE;
  202.   }
  203.  
  204.   /*  3.  Examine first character in string:  */
  205.  
  206.   c = toupper(string[0]);
  207.  
  208.   return (c == 'Y');
  209. }
  210.  
  211. /*----------------------------------------------------------------------
  212.  
  213. Routine:    cats
  214.  
  215. Description:    This function returns true if all nine squares
  216.         taken (usually called after checking for a win, so
  217.         that all spaces filled indicates a cat's game)
  218.  
  219. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  220.  
  221. static int cats()
  222. {
  223.   int i;
  224.  
  225.   for (i=0; i<9; ++i) {
  226.     if (board[i] == EMPTY) {
  227.       return FALSE;
  228.     }
  229.   }
  230.  
  231.   return TRUE;
  232. }
  233.  
  234. /*----------------------------------------------------------------------
  235.  
  236. Routine:    clear
  237.  
  238. Description:    Empty the board
  239.  
  240. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  241.  
  242. static void clear()
  243. {
  244.   int i;
  245.  
  246.   for (i=0; i<9; ++i) {
  247.     board[i] = EMPTY;
  248.   }
  249. }
  250.  
  251. /*----------------------------------------------------------------------
  252.  
  253. Routine:    display
  254.  
  255. Description:    Displays the playing board.
  256.  
  257. Note:        The original version of the routine accepted
  258.         a parameter that indicated if the pieces should
  259.         be displayed (the normal case), or if the
  260.         square numbers (1-9) should be shown instead.
  261.  
  262.         The square numbers were only shown at the
  263.         beginning of the game, and usually scrolled out of
  264.         sight, making it difficult to remember them.
  265.  
  266.         This version prints the square number for empty
  267.         squares and the piece for occupied squares.
  268.  
  269. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  270.  
  271. static void display()
  272. {
  273.   int r,c;    /* Not row and column, but almost ... */
  274.  
  275.   printf("\n\n");
  276.   for (r=0; r<9; r+=3) {
  277.     for (c=r; c< r+3; ++c) {
  278.       putchar(' ');
  279.       switch (board[c]) {
  280.         default:
  281.       fprintf(stderr, "ttt(display): unknown piece (%d) on board (%d)",
  282.                board[c], c);
  283.           exit(EXIT_FAILURE);
  284.  
  285.     case EMPTY:
  286.       printf("%1d", c+1);
  287.       break;
  288.  
  289.     case X:
  290.       putchar('X');
  291.       break;
  292.  
  293.     case O:
  294.       putchar('O');
  295.       break;
  296.       }
  297.       putchar(' ');
  298.       if (c != r+2) {
  299.         putchar('|');
  300.       }
  301.     }
  302.     putchar('\n');
  303.     if (r != 6) {
  304.       printf("---+---+---\n");
  305.     }
  306.   }
  307.   putchar('\n');
  308. }
  309.  
  310. /*----------------------------------------------------------------------
  311.  
  312. Routine:    getmove
  313.  
  314. Description:    reads a string containing a digit, and returns
  315.         the digit as result.
  316.  
  317.         If no digit could be read, -1 is returned.
  318.  
  319. Suggestions for improvement:
  320.  
  321.         See the description of ask() above!
  322.  
  323. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  324.  
  325. static int getmove()
  326. {
  327.   char string[160];    /* input string */
  328.  
  329.   /*  1.  Read a string from standard input:  */
  330.  
  331.   if (fgets(string, sizeof(string), stdin) == 0) {    /* EOF or error */
  332.     return -1;
  333.   }
  334.  
  335.   /*  2.  Return value of digit:  */
  336.  
  337.   return string[0] - '0';
  338. }
  339.  
  340. /*----------------------------------------------------------------------
  341.  
  342. Routine:    main
  343.  
  344. Description:    main program
  345.  
  346. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  347.  
  348. int main()
  349. {
  350.   int i;
  351.   int mefirst;            /* 1: computer goes first; 0: human */
  352.   int turn;            /* counts number of moves played */
  353.   int finished;            /* true if game is over */
  354.   int mypiece, hispiece;    /* who has x or o */
  355.   int mywins, hiswins, catwins;    /* game count */
  356.   int t;
  357.  
  358.   /*  1.  Initialize:  */
  359.  
  360.   srand(0);            /* initialize random generator */
  361.   mywins = hiswins = catwins = 0;
  362.   mefirst = TRUE;        /* let human go first (see 2a below) */
  363.  
  364.   printf("\n\nWelcome to BDS Tic Tac Toe!!\n");
  365.   printf("(In this version, X always goes first.\n");
  366.  
  367.   /*  2.  Outer game loop:  */
  368.  
  369.   do {
  370.  
  371.     /*  2a.  Set up for new game:  */
  372.  
  373.     finished = FALSE;
  374.     mefirst = !mefirst;        /* reverse who goes first */
  375.     turn = 0;
  376.     clear();            /* clear the game board */
  377.  
  378.     if (mefirst) {
  379.       printf("I go first...\n");
  380.       display();        
  381.     } else {
  382.       printf("You go first...\n");
  383.     }
  384.     mypiece = mefirst ? X : O;     /* set who has got what */
  385.     hispiece  = mefirst ? O : X;
  386.     if (!mefirst) goto hismove;
  387.  
  388.     /*  2b.  Inner game loop:  */
  389.  
  390.     while (!finished) {
  391.  
  392.       /*  2c.  Computer's move:  */
  393.  
  394.       if (turn == 0) {    /* Random opening move */
  395.         BEST = rand() % 9;
  396.       }
  397.  
  398.       if (turn == 1) {    /* Response to player's opening move */   
  399.         if (board[4] != EMPTY) {    /* Center is occupied */
  400.           BEST = rand() % 2 * 6 +    rand() % 2 * 2;
  401.         } else {            /* Grab center */
  402.           BEST = 4;
  403.         }
  404.       }
  405.  
  406.       if (turn > 1) {    /* OK, we're into the game... */    
  407.         t = ttteval(mypiece, hispiece);
  408.         if (t == 1) printf("I've got ya!\n");
  409.       }
  410.  
  411.       board[BEST] = mypiece;      /* make the move */
  412.       ++turn;
  413.  
  414.       printf("I move to %d\n", BEST+1);
  415.  
  416.       if (win(mypiece)) {
  417.         ++mywins;
  418.         printf("\nI win!!!\n");
  419.         finished = TRUE;
  420.       } else if (cats()) {
  421.         ++catwins;
  422.         printf("\nMeee-ow!\n");
  423.         finished = TRUE;
  424.       }
  425.  
  426. hismove:
  427.       if (!finished) {
  428.  
  429.         /*  2b.  Player to move:  */
  430.  
  431.         display();
  432.  
  433.         do {
  434.           printf("Your move (1-9) ? ");
  435.           i = getmove();
  436.           if (i < 1 || i > 9 || board[i-1]) {
  437.             printf("\nIllegal!\n");
  438.             i = 0;    /* indicates erroneous move */
  439.           }
  440.         } while (i == 0);
  441.  
  442.         board[i-1] = hispiece;
  443.         ++turn;
  444.         display();
  445.         if (win(hispiece)) {
  446.           ++hiswins;
  447.           printf("\nYou beat me!!\n");
  448.           finished = TRUE;
  449.         } else if (cats()) {
  450.           ++catwins;
  451.           printf("\nOne for Morris.\n");
  452.           finished = TRUE;
  453.         }
  454.       }
  455.  
  456.     }  /* Inner game loop */
  457.  
  458.   } while (ask("\nAnother game (y/n) ? "));
  459.  
  460.   /*  3.  Print final statistics:  */
  461.  
  462.   printf("\n\nOK...Final score:\n");
  463.   printf("You won %d game", hiswins);
  464.   if (hiswins != 1) putchar('s');
  465.  
  466.   printf(";\nI won %d game", mywins);
  467.   if (mywins != 1) putchar('s');
  468.  
  469.   printf(";\nThe Cat got %d game",catwins);
  470.   if (catwins != 1) putchar('s');
  471.  
  472.   printf(".\nSee ya later!!\n");
  473.  
  474.   return EXIT_SUCCESS;
  475. }
  476.  
  477. /*----------------------------------------------------------------------
  478.  
  479. Routine:    ttteval
  480.  
  481. Description:    The function "ttteval" returns an evaluation of
  482.         player x's position on the tic-tac-toe board. If he's
  483.         in a winning position, 1 is returned. If the best he
  484.         can hope for is a cat's game, 0 is returned. And, if
  485.         he's sure to lose if player y plays correctly, -1 is
  486.         returned. In any case, the best move available to 
  487.         player x is left in external variable BEST upon return
  488.         from ttteval.
  489.  
  490.         Note that a value of -1 is often returned while
  491.         recursive searching branches down into all possible
  492.         wins and losses, but with the program in the shape
  493.         it appears here, the outermost-level call to ttteval
  494.         (from the main program) will never produce a return
  495.         value of -1, since the computer has decided not to be
  496.         able to lose (the obviously logical choice of any
  497.         self-respecting problem-solver.)
  498.  
  499.         In any case, the main program still bothers to 
  500.         consider the possibility of losing, so that if you
  501.         want to try inserting your own "ttteval" routine
  502.         in place of the one given, it dosn't have to be
  503.         perfect in order to work with the main program.
  504.         Tic-tac-toe is, of course, just about the only game
  505.         in which it is feasible to do an exhaustive search;
  506.         most game evaluation algorithms only go so deep and
  507.         then make a "static" evaluation, or estimate of the
  508.         player's status at the terminal position. That is how
  509.         all decent chess playing programs today work.
  510.  
  511. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  512.  
  513. static int ttteval(me, him)
  514. int me;
  515. int him;
  516. {
  517.   int i,safemove;
  518.   int v,loseflag;
  519.     
  520.   /*  1.  Is game terminated?  */  
  521.  
  522.   if (win(me))  return 1;
  523.   if (win(him)) return -1;
  524.   if (cats())   return 0;
  525.  
  526.   /*  2.  Try out all moves and see what happens:  */
  527.  
  528.   loseflag = 1;
  529.   for (i=0; i<9; ++i) {
  530.     if (board[i] == EMPTY) {    /* a legal move */
  531.       board[i] = me;        /* try the move...*/
  532.       v = ttteval(him,me);    /* ...evaluate the resulting position */
  533.       board[i] = EMPTY;        /* and undo the move */
  534.  
  535.       if (v == -1) {         /* if we force a loss, yey! */
  536.         BEST = i;
  537.         return 1;
  538.        }
  539.  
  540.       if (v) continue;       /* uh oh! we shouldn't get beaten! */
  541.       loseflag = 0;        /* cat's game guaranteed at least */
  542.       safemove = i;
  543.     }
  544.   }
  545.   BEST = safemove;
  546.   return -loseflag;        /* if loseflag is true, this returns
  547.                    -1 to indicate a loss; else zero
  548.                    is returned (cat's game.)    */
  549. }
  550.  
  551. /*----------------------------------------------------------------------
  552.  
  553. Routine:    win
  554.  
  555. Description:    returns true (non-zero) if player p has three in a row
  556.         on the board:
  557.  
  558. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  559.  
  560. static int win(p)
  561. int p;
  562. {
  563.   int i;
  564.   for (i=0; i<8; ++i) {
  565.     if (board[wins[i][0]] == p &&
  566.         board[wins[i][1]] == p &&
  567.         board[wins[i][2]] == p) return 1;
  568.   }
  569.   return 0;
  570. }
  571.  
  572.  
  573.