commands/simple/ttt.c

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