home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Professional / OS2PRO194.ISO / os2 / prgramer / minix / ttt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-12-26  |  6.6 KB  |  285 lines
  1. /* tic tac toe (noughts and crosses)        Author: Warren Toomey */
  2. /* $Header: d:/rcs/D:/RCS/RCS/ttt.c 1.1 89/12/10 05:35:11 RCA Exp $
  3.  * $Revision: 1.1 $
  4.  */
  5.  
  6. /* Copyright (C) 1988 Warren Toomey.
  7.   You may use, copy, modify, or give this away provided you
  8.   1. make the source available with every copy.
  9.   2. include this notice.
  10.   3. don't use this for military purposes.
  11.   (but you can take credit for improvements, etc.)
  12. */
  13.  
  14. /* Compile with cc -o tic tic.c -lcurses -ltermcap */
  15.  
  16. #define CURSES
  17. #ifdef CURSES
  18. #include <curses.h>
  19. /*  #include <curses.h>                 Used by the real curses  */
  20. #endif
  21.  
  22. #ifndef CURSES
  23. #define printw printf
  24. #endif
  25.  
  26.  
  27. typedef struct {
  28.   int value;            /* The move returned by the    */
  29.   int path;            /* alphabeta consists of a value */
  30. } MOVE;                /* and an actual move (path)   */
  31.  
  32.  
  33.  /* Static evaluator. Returns 100 if we have 3 in a row -100 if they have 3
  34.   * in a row
  35.   * 
  36.   * Board is array of 9 ints, where 0=empty square 1=our move 4= their move
  37.   * 
  38.   * and board is indices    0 1 2 3 4 5 6 7 8 */
  39.  
  40.  
  41. int stateval(board, whosemove)
  42. int board[];
  43.  
  44. {
  45.   static int row[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8},    /* Indices of 3in-a-rows */
  46.             {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
  47.             {0, 4, 8}, {2, 4, 6}};
  48.  
  49.   int temp;            /* Temp row results */
  50.   int i, j;            /* Loop counters */
  51.   int side;            /* Depth multiplier */
  52.   int win, lose;
  53.  
  54.   if (whosemove == 1) {
  55.     win = 100;
  56.     lose = -100;
  57.     side = 1;
  58.   } else {
  59.     /* Multiply by -1 if */
  60.     win = -100;
  61.     lose = 100;
  62.     side = -1;
  63.   }                /* not out move */
  64.   for (i = 0; i < 8; i++) {    /* For every 3-in-a-row */
  65.     temp = 0;
  66.     for (j = 0; j < 3; j++)    /* Add up the board values */
  67.         temp += board[row[i][j]];
  68.  
  69.     if (temp == 3) return(win);    /* We've got 3 in a row */
  70.     if (temp == 12) return (lose);    /* They've got 3 in a row */
  71.   }
  72.   return(0);            /* Finally return sum */
  73. }
  74.  
  75.  
  76. MOVE alphabeta(board, whosemove, alpha, beta)    /* Alphabeta: takes a board, */
  77. int board[];            /* whose move, alpha & beta cutoffs, */
  78. int whosemove;            /* and returns a move to make and */
  79. int alpha;            /* the value that the move has */
  80. int beta;
  81. {
  82.   MOVE result, successor;
  83.   int best_score, i, best_path, mademove;
  84.  
  85.   result.value = stateval(board, whosemove);    /* Work out the board's */
  86.   /* Static value */
  87.   if ((result.value == 100) ||    /* If a win or loss already */
  88.       (result.value == -100))
  89.     return(result);    /* return the result */
  90.  
  91.   best_score = beta;        /* Ok, set worst score */
  92.   mademove = 0;            /* to the beta cutoff */
  93.   for (i = 0; i < 9; i++) {
  94.     if (board[i] == 0) {    /* For all valid moves */
  95.         mademove = 1;
  96.         board[i] = whosemove;    /* make the move on board */
  97.         successor = alphabeta(board, 5 - whosemove, -best_score - 1, -alpha - 1);
  98.         /* Get value of the move */
  99.         board[i] = 0;    /* Take move back */
  100.         if (-successor.value > best_score) {    /* If a better score */
  101.             best_score = -successor.value;    /* update our score */
  102.             best_path = i;    /* and move */
  103.             if (best_score > alpha)
  104.                 break;    /* If we've beaten alpha */
  105.         }        /* return immediately */
  106.     }
  107.   }
  108.   if (mademove) {
  109.     result.value = best_score;    /* Finally return best score */
  110.     result.path = best_path;/* and best move */
  111.   }
  112.   return(result);        /* If no move, return static result */
  113. }
  114.  
  115.  
  116. draw(board)            /* Draw the board */
  117. int board[];
  118. {
  119.   int i, j, row;
  120.   static char out[] = " X  O";    /* Lookup table for character */
  121.  
  122.   row = 6;
  123. #ifdef CURSES
  124.   move(row, 0);
  125. #endif
  126.   for (j = 0; j < 9; j += 3) {
  127.     printw(" %d | %d | %d     ", j, j + 1, j + 2);
  128.     for (i = 0; i < 3; i++) {
  129.         printw("%c ", out[board[j + i]]);
  130.         if (i < 2) printw("| ");
  131.     }
  132.     if (j < 4) {
  133. #ifdef CURSES
  134.         move(++row, 0);
  135. #else
  136.         printw("\n");
  137. #endif
  138.         printw("---+---+---   ---+---+---");
  139.     }
  140. #ifdef CURSES
  141.     move(++row, 0);
  142. #else
  143.     printw("\n");
  144. #endif
  145.   }
  146. #ifdef CURSES
  147.   refresh();
  148. #else
  149.   printw("\n");
  150. #endif
  151. }
  152.  
  153.  
  154. getmove(board)            /* Get a player's move */
  155. int board[];
  156. {
  157.   int Move;
  158.  
  159.   do {
  160.     do {
  161. #ifdef CURSES
  162.         move(9, 40);
  163.         printw("Your move: ");    /* Prompt for move */
  164.         refresh();
  165. #else
  166.         printw("Your move: ");    /* Prompt for move */
  167. #endif
  168.     }
  169.     while (scanf("%d", &Move) != 1);    /* Input the move */
  170.   }
  171.   while (board[Move]);
  172.   board[Move] = 4;        /* If legal, add to board */
  173.   draw(board);            /* Draw the board */
  174. }
  175.  
  176.  
  177. int endofgame(board)        /* Determine end of the game */
  178. int board[];
  179. {
  180.   int eval;
  181.   int count;
  182.  
  183.   eval = stateval(board, 1);
  184. #ifdef CURSES
  185.   move(20, 25);
  186. #endif
  187.   if (eval == 100) {
  188.     printw("I have beaten you.\n");
  189.     return(1);
  190.   }
  191.   if (eval == -100) {
  192.     printw("Bus error (core dumped)\n");
  193.     return(1);
  194.   }
  195.   count = 0;
  196.   for (eval = 0; eval < 9; eval++)
  197.     if (board[eval] != 0) count++;
  198.   if (count == 9) {
  199.     printw("A draw!\n");
  200.     return(1);
  201.   }
  202. #ifdef CURSES
  203.   refresh();
  204. #endif
  205.   return(0);
  206. }
  207.  
  208.  
  209. int randommove()
  210. {                /* Make an initial random move */
  211.   long time();            /* based on current time */
  212.   int i;
  213.  
  214.   i = abs((int) time((long *) 0));
  215.   return(i % 9);
  216. }
  217.  
  218.  
  219. main()
  220. {                /* The actual game */
  221.   int i, board[9];
  222.   char ch;
  223.   MOVE ourmove;
  224.  
  225.   for (i = 0; i < 9; i++) board[i] = 0;    /* Initialise the board */
  226. #ifdef CURSES
  227.   initscr();
  228.   clear();
  229.   refresh();
  230. #endif
  231.   printw("                           TIC TAC TOE   \n\n");
  232.   printw("                        Your moves are 'O'\n");
  233.   printw("                         My moves are 'X'\n\n");
  234. #ifdef CURSES
  235.   move(5, 0);
  236.   printw("Do you wish to move first: ");
  237.   refresh();
  238.   while (scanf("%c", &ch) != 1);
  239.   move(5, 0);
  240.   printw("                         .......");    /* Kludge to get rid */
  241.   refresh();
  242.   move(5, 0);
  243.   printw("                                ");    /* of input letter */
  244.   refresh();
  245. #else
  246.   do
  247.     printw("Do you wish to move first: ");
  248.   while (scanf("%c", &ch) != 1);
  249. #endif
  250.   if ((ch != 'y') && (ch != 'Y')) {
  251.     i = randommove();    /* If we move first */
  252.     board[i] = 1;        /* make it random */
  253. #ifdef CURSES
  254.     move(7, 42);
  255.     printw("My move: %d\n", i);
  256.     refresh();
  257. #else
  258.     printw("My move: %d\n", i);
  259. #endif
  260.   }
  261.   draw(board);
  262.   getmove(board);
  263.  
  264.   while (1) {
  265.     ourmove = alphabeta(board, 1, 99, -99);    /* Get a move for us;
  266.                          * return wins */
  267.     /* Immediately & ignore losses */
  268.     board[ourmove.path] = 1;/* and make it */
  269. #ifdef CURSES
  270.     move(7, 42);
  271.     printw("My move: %d\n", ourmove.path);
  272.     refresh();
  273. #else
  274.     printw("My move: %d\n", ourmove.path);
  275. #endif
  276.     draw(board);
  277.     if (endofgame(board)) break;    /* If end of game, exit */
  278.     getmove(board);        /* Get opponent's move */
  279.     if (endofgame(board)) break;    /* If end of game, exit */
  280.   }
  281. #ifdef CURSES
  282.   endwin();
  283. #endif
  284. }
  285.