home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / SUPER_C.ZIP / TIC.C < prev    next >
Encoding:
C/C++ Source or Header  |  1980-01-01  |  7.4 KB  |  242 lines
  1. /*                      TicTac
  2.  
  3.         This program plays a perfect game of tic-tac-toe.
  4. */
  5.  
  6. #define FALSE 0
  7. #define TRUE 1
  8.  
  9. char board[9];   /* The playing board; for each space, 0 is not used,
  10.                    1 is X, -1 is O. */
  11.  
  12. /*      main()
  13.  
  14.         Function: Ask the user which side(s) he wants to play. Then
  15.         make or ask for moves one each side until one side wins.
  16.  
  17.         Algorithm: First, set humanX and humanO to indicate which
  18.         side(s) the human is playing. Then init the board and print
  19.         it out. Then iterate making or asking for a move, printing
  20.         it out, and testing for a win. Each pass thru the main loop,
  21.         the program switches sides.
  22. */
  23.  
  24. main()
  25.  
  26. {
  27.         register int side;               /* Which side is playing (1 or -1). */
  28.         int move;               /* Next move. */
  29.         int val;                /* Value of move. */
  30.         int humanX, humanO;     /* TRUE if human is playing X/O. */
  31.         char str[20];           /* Input are for yes/no. */
  32.  
  33.         /* Ask the user if the computer should play the Xs. */
  34.         printf("Should the computer play Xs? ");
  35.         gets(str);
  36.         if ((str[0] == 'y') || (str[0] == 'Y')) humanX = FALSE;
  37.         else humanX = TRUE;
  38.         /* Ask about playing the Os. */
  39.         printf("Should the computer play Os? ");
  40.         gets(str);
  41.         if ((str[0] == 'y') || (str[0] == 'Y')) humanO = FALSE;
  42.         else humanO = TRUE;
  43.  
  44.         /* Initialize the board. */
  45.         initBd();
  46.  
  47.         /* Show the empty board. */
  48.         printBd();
  49.  
  50.         /* X goes first. */
  51.         side = 1;
  52.  
  53.         /* Loop until a win or the player quits. */
  54.         while (TRUE) {
  55.                 /* If this side is played by the human... */
  56.                 if ((humanX && (side == 1)) || (humanO && (side == -1))) {
  57.                         /* Query for move; repeat until legal. */
  58.                         do {
  59.                             if (side == 1)
  60.                                 printf("X's move (enter 1-9, or 0 to quit): ");
  61.                             else printf("O's move (enter 1-9, or 0 to quit): ");
  62.                             scanf("%d",&move);
  63.                         } while ((move != 0) && (board[move-1] != 0));
  64.                         /* Check for quit. */
  65.                         if (move == 0) break;
  66.                 /* Otherwise, decide on the best move to make. */
  67.                 } else move = bestMove(side,&val)+1;
  68.                 /* Make the move. */
  69.                 board[move-1] = side;
  70.                 /* Show the new board to the user. */
  71.                 printBd();
  72.                 /* If that one won it, say so and exit. */
  73.                 if (hasWon(side)) {
  74.                         printf("That move won!\n");
  75.                         break;
  76.                 };
  77.                 /* If it was a tie, say so and exit. */
  78.                 if (isTie()) {
  79.                         printf("Tie game!\n");
  80.                         break;
  81.                 };
  82.                 /* Switch sides for the next move. */
  83.                 side = -side;
  84.         };
  85. }
  86.  
  87. /*      initBd()
  88.  
  89.         Function: Initialize the board to all empty.
  90.  
  91.         Algorithm: Set each board entry to zero.
  92. */
  93.  
  94. initBd()
  95.  
  96. {
  97.         register int i;
  98.  
  99.         /* Zero (empty) each square in the board. */
  100.         for (i = 0; i < 9; i++) board[i] = 0;
  101. }
  102.  
  103. /*      isTie()
  104.  
  105.         Function: Return TRUE if the current board position is a tie.
  106.  
  107.         Algorithm: See if we can find an untaken board position. If not,
  108.         it's a tie. Otherwise, there's still hope.
  109. */
  110.  
  111. isTie()
  112.  
  113. {
  114.         register int i;
  115.  
  116.         /* Check each space on the board. */
  117.         for (i = 0; i < 9; i++) if (board[i] == 0) return(FALSE);
  118.         /* If none found, return tie. */
  119.         return(TRUE);
  120. }
  121.  
  122. /*      hasWon(p)
  123.  
  124.         Function: Return true if player p has won, where p is 1 for X
  125.         and -1 for O.
  126.  
  127.         Algorithm: Check for every possible three in a row. If any are
  128.         found, it's a win, so we return TRUE; otherwise, we return FALSE.
  129. */
  130. #ifdef NEVER
  131. hasWon(p)
  132.  
  133. int p;
  134.  
  135. {
  136.         register int i;
  137.         register int w;
  138.  
  139.         /* Calculate the sum of three in a row. */
  140.         w = 3*p;
  141.  
  142.         /* Check for three in a row horizontally. */
  143.         for (i = 0; i < 9; i += 3)
  144.                 if ((board[i]+board[i+1]+board[i+2]) == w) return(TRUE);
  145.  
  146.         /* Check for three in a row vertically. */
  147.         for (i = 0; i < 3; i++)
  148.                 if ((board[i]+board[i+3]+board[i+6]) == w) return(TRUE);
  149.  
  150.         /* Check the diagonols. */
  151.         if ((board[0]+board[4]+board[8]) == w) return(TRUE);
  152.         if ((board[2]+board[4]+board[6]) == w) return(TRUE);
  153.  
  154.         /* If nothing, then return a non-win. */
  155.         return(FALSE);
  156. }
  157. #endif NEVER
  158. /*      bestMove(p,v)
  159.  
  160.         Function: Return the best possible move for player p. p is 1
  161.         for X or -1 for O. Also return the value of that move (1 for
  162.         a win, 0 for a tie, and -1 for a loss) in v.
  163. */
  164.  
  165. bestMove(p,v)
  166.  
  167. int p;
  168. int *v;
  169.  
  170. {
  171.         register int i;
  172.         int lastTie;
  173.         register int lastMove;
  174.         int subV;
  175.  
  176.         /* First, check for a tie. */
  177.         if (isTie()) {
  178.                 *v = 0;
  179.                 return(0);
  180.         };
  181.  
  182.         /* If not a tie, try each potential move. */
  183.         for (*v = -1, lastTie = lastMove = -1, i = 0; i < 9; i++) {
  184.                 /* If this isn't a possible move, skip it. */
  185.                 if (board[i] != 0) continue;
  186.                 /* Make the move. */
  187.                 lastMove = i;
  188.                 board[i] = p;
  189.                 /* Did it win? */
  190.                 if (hasWon(p)) *v = 1;
  191.                 else {
  192.                         /* If not, find out how good the other side can do. */
  193.                         bestMove(-p,&subV);
  194.                         /* If they can only lose, this is still a win. */
  195.                         if (subV == -1) *v = 1;
  196.                         /* Or, if it's a tie, remember it. */
  197.                         else if (subV == 0) {
  198.                                 *v = 0;
  199.                                 lastTie = i;
  200.                         };
  201.                 };
  202.                 /* Take back the move. */
  203.                 board[i] = 0;
  204.                 /* If we found a win, return immediately (can't do any
  205.                    better than that). */
  206.                 if (*v == 1) return(i);
  207.         };
  208.         /* If we didn't find any wins, return a tie move. */
  209.         if (*v == 0) return(lastTie);
  210.         /* If there weren't even any ties, return a loosing move. */
  211.         else return(lastMove);
  212. }
  213.  
  214. /*      printBd()
  215.  
  216.         Function: Display the board for the user.
  217.  
  218.         Algorithm: Iterate thru each square and print it out.
  219. */
  220.  
  221. printBd()
  222.  
  223. {
  224.         register int i;
  225.  
  226.         /* For each square... */
  227.         for (i = 0; i < 9; i++) {
  228.                 /* Print X, O, or space. */
  229.                 if (board[i] == 0) printf(" ");
  230.                 else if (board[i] == 1) printf("X");
  231.                 else printf("O");
  232.                 /* If this is the last square in the line... */
  233.                 if ((i % 3) == 2) {
  234.                         /* Print the adjacent numbered board. */
  235.                         printf("    %1d|%1d|%1d\n",i-1,i,i+1);
  236.                         if (i != 8) printf("-+-+-    -+-+-\n");
  237.                 } else printf("|");
  238.         };
  239.         printf("\n");
  240. }
  241.  
  242.