ver1/ttt.c

   1 #include <stdlib.h>\r
   2 #include <stdio.h>\r
   3 #include <memory.h>\r
   4 #include <time.h>\r
   5 #include "ttt.h"\r
   6 \r
   7 SQUARE g_sComputerPlays = O_MARK;             // what side comp plays\r
   8 unsigned int g_uPly = 0;\r
   9 MOVE g_mvBest = { 0 };\r
  10 \r
  11 //+----------------------------------------------------------------------------\r
  12 //\r
  13 // Function:  SquareContentsToChar\r
  14 //\r
  15 // Synopsis:  Helper function for DrawBoard\r
  16 //\r
  17 // Arguments: IN SQUARE s - a square to return a char to represent\r
  18 //            \r
  19 // Returns:   char - character representing square\r
  20 //\r
  21 //+----------------------------------------------------------------------------\r
  22 char SquareContentsToChar(IN SQUARE s)\r
  23 {\r
  24     static char c;\r
  25     switch(s)\r
  26     {\r
  27         case X_MARK:\r
  28             c = 'X';\r
  29             break;\r
  30         case O_MARK:\r
  31             c = 'O';\r
  32             break;\r
  33         case EMPTY:\r
  34             c = '_';\r
  35             break;\r
  36         default:\r
  37             ASSERT(FALSE);\r
  38             c = '?';\r
  39             break;\r
  40     }\r
  41     return(c);\r
  42 }\r
  43 \r
  44 //+----------------------------------------------------------------------------\r
  45 //\r
  46 // Function:  DrawBoard\r
  47 //\r
  48 // Synopsis:  Draw the board\r
  49 //\r
  50 // Arguments: IN POSITION *p - pointer to a position whose board to draw\r
  51 //            \r
  52 // Returns:   void\r
  53 //\r
  54 //+----------------------------------------------------------------------------\r
  55 void DrawBoard(IN POSITION *p)\r
  56 {\r
  57     COORD x, y;\r
  58 \r
  59     for (y = 0; y < BOARD_SIZE; y++)\r
  60     {\r
  61         for (x = 0; x < BOARD_SIZE; x++)\r
  62         {\r
  63             printf("%c ", SquareContentsToChar(p->sBoard[y][x]));\r
  64         }\r
  65         printf("\n");\r
  66     }\r
  67     ASSERT(X_OR_O(p->sWhoseTurn));\r
  68     printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));\r
  69 }\r
  70 \r
  71 //+----------------------------------------------------------------------------\r
  72 //\r
  73 // Function:  ClearBoard\r
  74 //\r
  75 // Synopsis:  Clear the board\r
  76 //\r
  77 // Arguments: IN OUT POSITION *p - pointer to position whose board to clear\r
  78 //            \r
  79 // Returns:   void\r
  80 //\r
  81 //+----------------------------------------------------------------------------\r
  82 void ClearBoard(IN OUT POSITION *p)\r
  83 {\r
  84     memset(p->sBoard, 0, sizeof(p->sBoard));\r
  85     p->sWhoseTurn = X_MARK;                   // x's go first\r
  86     p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);\r
  87 }\r
  88 \r
  89 //+----------------------------------------------------------------------------\r
  90 //\r
  91 // Function:  IsLegalMove\r
  92 //\r
  93 // Synopsis:  Determine if a given move is legal on a given board\r
  94 //\r
  95 // Arguments: IN POSITION *p - the board to play the move on\r
  96 //            IN MOVE *m - the move in question\r
  97 //            \r
  98 // Returns:   BOOL - TRUE if it's legal, FALSE otherwise\r
  99 //\r
 100 //+----------------------------------------------------------------------------\r
 101 BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)\r
 102 {\r
 103     if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))\r
 104     {\r
 105         if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))\r
 106         {\r
 107             return(TRUE);\r
 108         }\r
 109     }\r
 110     return(FALSE);\r
 111 }\r
 112 \r
 113 //+----------------------------------------------------------------------------\r
 114 //\r
 115 // Function:  GetHumanMove\r
 116 //\r
 117 // Synopsis:  Ask the human for a move\r
 118 //\r
 119 // Arguments: IN POSITION *p - the current board\r
 120 //            OUT MOVE *m - the move the human made; this struct is populated\r
 121 //                      as a side-effect of this function.\r
 122 //            \r
 123 // Returns:   void* (populates the move struct)\r
 124 //\r
 125 //+----------------------------------------------------------------------------\r
 126 void GetHumanMove(IN POSITION *p, OUT MOVE *m)\r
 127 {\r
 128     unsigned int x;\r
 129 \r
 130     do\r
 131     {\r
 132         printf("Enter your move number: ");\r
 133         scanf("%u", &x);\r
 134         \r
 135         m->cHpos = NUM_TO_HPOS(x);\r
 136         m->cVpos = NUM_TO_VPOS(x);\r
 137         m->sMark = OPPOSITE_MARK(g_sComputerPlays);\r
 138     }\r
 139     while(FALSE == IsLegalMove(p, m));\r
 140 }\r
 141 \r
 142 //+----------------------------------------------------------------------------\r
 143 //\r
 144 // Function:  GameOver\r
 145 //\r
 146 // Synopsis:  Is the game over? \r
 147 //\r
 148 // Arguments: IN POSITION *p - the board\r
 149 //            OUT SQUARE *psWhoWon - who won the game (if it's over)\r
 150 //            \r
 151 // Returns:   TRUE if the game is over.  Also sets psWhoWon telling\r
 152 //            which side one if the game is over.  This also serves\r
 153 //            as a very simple evaluation routine for the search.\r
 154 // \r
 155 //            FALSE if the game is not over.\r
 156 //\r
 157 //+----------------------------------------------------------------------------\r
 158 BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)\r
 159 {\r
 160     int iSum;\r
 161     COORD x, y;\r
 162 \r
 163     for (x = 0; x < BOARD_SIZE; x++)\r
 164     {\r
 165         iSum = 0;\r
 166 \r
 167         for (y = 0; y < BOARD_SIZE; y++)\r
 168         {\r
 169             iSum += p->sBoard[x][y];\r
 170         }\r
 171         if (abs(iSum) == BOARD_SIZE) goto winner;\r
 172     }\r
 173 \r
 174     for (y = 0; y < BOARD_SIZE; y++)\r
 175     {\r
 176         iSum = 0;\r
 177 \r
 178         for (x = 0; x < BOARD_SIZE; x++)\r
 179         {\r
 180             iSum += p->sBoard[x][y];\r
 181         }\r
 182         if (abs(iSum) == BOARD_SIZE) goto winner;\r
 183     }\r
 184 \r
 185     iSum = 0;\r
 186     for (x = 0; x < BOARD_SIZE; x++)\r
 187     {\r
 188         iSum += p->sBoard[x][x];\r
 189     }\r
 190     if (abs(iSum) == BOARD_SIZE) goto winner;\r
 191 \r
 192     iSum = 0;\r
 193     for (x = 0; x < BOARD_SIZE; x++)\r
 194     {\r
 195         iSum += p->sBoard[x][(BOARD_SIZE - 1 - x)];\r
 196     }\r
 197     if (abs(iSum) == BOARD_SIZE) goto winner;\r
 198 \r
 199     *psWhoWon = EMPTY;\r
 200     if (p->uNumEmpty == 0)\r
 201     {\r
 202         return(TRUE);\r
 203     }\r
 204     else\r
 205     {\r
 206         return(FALSE);\r
 207     }\r
 208 \r
 209  winner:\r
 210     *psWhoWon = (iSum / BOARD_SIZE);\r
 211     ASSERT(X_OR_O(*psWhoWon));\r
 212     return(TRUE);\r
 213 }\r
 214 \r
 215 \r
 216 //+----------------------------------------------------------------------------\r
 217 //\r
 218 // Function:  MakeMove\r
 219 //\r
 220 // Synopsis:  Make a move on a board  \r
 221 //\r
 222 // Arguments: IN OUT POSITION *p - the board\r
 223 //            IN MOVE *m - the move\r
 224 //            \r
 225 // Returns:   void\r
 226 //\r
 227 //+----------------------------------------------------------------------------\r
 228 void MakeMove(IN OUT POSITION *p, IN MOVE *m)\r
 229 {\r
 230     if (TRUE == IsLegalMove(p, m))\r
 231     {\r
 232         ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);\r
 233         p->sBoard[m->cVpos][m->cHpos] = m->sMark;\r
 234         p->uNumEmpty--;\r
 235         ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));\r
 236         p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
 237         g_uPly++;\r
 238         ASSERT(g_uPly > 0);\r
 239     }\r
 240 }\r
 241 \r
 242 //+----------------------------------------------------------------------------\r
 243 //\r
 244 // Function:  UnmakeMove\r
 245 //\r
 246 // Synopsis:  The opposite of MakeMove\r
 247 //\r
 248 // Arguments: IN OUT POSITION *p - the board\r
 249 //            IN MOVE *m - the move to undo\r
 250 //            \r
 251 // Returns:   void\r
 252 //\r
 253 //+----------------------------------------------------------------------------\r
 254 void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)\r
 255 {\r
 256     if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)\r
 257     {\r
 258         p->sBoard[m->cVpos][m->cHpos] = EMPTY;\r
 259         p->uNumEmpty++;\r
 260         ASSERT(p->uNumEmpty > 0);\r
 261         ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));\r
 262         p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
 263         ASSERT(g_uPly > 0);\r
 264         g_uPly--;\r
 265     }\r
 266 }\r
 267 \r
 268 \r
 269 int\r
 270 SimpleSearch(IN POSITION *p)\r
 271 {\r
 272     SQUARE sWhoWon;\r
 273     SQUARE s;\r
 274     MOVE mv;\r
 275     int iScore;\r
 276     int iBestScore = -INFINITY;\r
 277 \r
 278     //\r
 279     // Evaluate this position\r
 280     //\r
 281     if (TRUE == GameOver(p, &sWhoWon))\r
 282     {\r
 283         if (sWhoWon == p->sWhoseTurn)\r
 284         {\r
 285             return(+INFINITY);\r
 286         }\r
 287         else if (sWhoWon == (p->sWhoseTurn * -1))\r
 288         {\r
 289             return(-INFINITY);\r
 290         }\r
 291         return(DRAWSCORE);\r
 292     }\r
 293 \r
 294     //\r
 295     // No one won, game is still going.  Evaluate every\r
 296     // possible move from here.\r
 297     //\r
 298     ASSERT(p->uNumEmpty > 0);\r
 299     for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)\r
 300     {\r
 301         mv.cHpos = NUM_TO_HPOS(s);\r
 302         mv.cVpos = NUM_TO_VPOS(s);\r
 303         mv.sMark = p->sWhoseTurn;\r
 304 \r
 305         if (IsLegalMove(p, &mv))\r
 306         {\r
 307             MakeMove(p, &mv);\r
 308 \r
 309             iScore = -1 * SimpleSearch(p);\r
 310             if (iScore > iBestScore)\r
 311             {\r
 312                 iBestScore = iScore;\r
 313                 if (g_uPly == 1)\r
 314                 {\r
 315                     g_mvBest = mv;\r
 316                 }\r
 317             }\r
 318 \r
 319             UnmakeMove(p, &mv);\r
 320         }\r
 321     }\r
 322     return(iBestScore);\r
 323 }\r
 324 \r
 325 //+----------------------------------------------------------------------------\r
 326 //\r
 327 // Function:  SearchForComputerMove\r
 328 //\r
 329 // Synopsis:  Use our sophisticated search algorithm to find a computer\r
 330 //            move\r
 331 //\r
 332 // Arguments: IN POSITION *p - the current board\r
 333 //            OUT MOVE *m - the move the computer chooses; this move struct\r
 334 //                      is populated as a side-effect of this function.\r
 335 //            \r
 336 // Returns:   void* (populates move struct)\r
 337 //\r
 338 //+----------------------------------------------------------------------------\r
 339 void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)\r
 340 {\r
 341     unsigned int x;\r
 342 \r
 343 #if defined(PLAY_RANDOMLY)\r
 344     do\r
 345     {\r
 346         x = rand() % (BOARD_SIZE * BOARD_SIZE);\r
 347         m->cHpos = NUM_TO_HPOS(x);\r
 348         m->cVpos = NUM_TO_VPOS(x);\r
 349         m->sMark = g_sComputerPlays;\r
 350     }\r
 351     while(FALSE == IsLegalMove(p, m));\r
 352 #elif defined(SIMPLE_SEARCH)\r
 353     g_uPly = 0;\r
 354     SimpleSearch(p);\r
 355     *m = g_mvBest;\r
 356 #else\r
 357     #error "No Search Strategy Defined"\r
 358 #endif\r
 359 }\r
 360 \r
 361 //+----------------------------------------------------------------------------\r
 362 //\r
 363 // Function:  main\r
 364 //\r
 365 // Synopsis:  The program entry point and main game loop.\r
 366 //\r
 367 // Arguments: void\r
 368 //            \r
 369 // Returns:   int\r
 370 //\r
 371 //+----------------------------------------------------------------------------\r
 372 int main(void)\r
 373 {\r
 374     POSITION p;\r
 375     MOVE mv;\r
 376     SQUARE sResult;\r
 377 \r
 378     //\r
 379     // Randomize: the random numbers returned by rand() will be based on\r
 380     // the system clock when the program starts up.\r
 381     //\r
 382     srand(time(0));\r
 383 \r
 384     //\r
 385     // Setup the board and draw it once.\r
 386     //\r
 387     ClearBoard(&p);\r
 388     DrawBoard(&p);\r
 389 \r
 390     //\r
 391     // Main game loop\r
 392     //\r
 393     do\r
 394     {\r
 395         // \r
 396         // See whose turn it is -- the human's or the computers -- and\r
 397         // get a move from whoever's turn it is.\r
 398         //\r
 399         if (p.sWhoseTurn == g_sComputerPlays)\r
 400         {\r
 401             SearchForComputerMove(&p, &mv);\r
 402         }\r
 403         else\r
 404         {\r
 405             GetHumanMove(&p, &mv);\r
 406         }\r
 407 \r
 408         //\r
 409         // Make the move on the board and draw the board again.\r
 410         //\r
 411         MakeMove(&p, &mv);\r
 412         DrawBoard(&p);\r
 413     }\r
 414     while(FALSE == GameOver(&p, &sResult));\r
 415 \r
 416     //\r
 417     // If we get here the game is over... see what happened.\r
 418     //\r
 419     switch(sResult)\r
 420     {\r
 421         case X_MARK:\r
 422             printf("\nX's win.\n");\r
 423             break;\r
 424         case O_MARK:\r
 425             printf("\nO's win.\n");\r
 426             break;\r
 427         default:\r
 428             printf("Tie (what a surprise)\n");\r
 429             break;\r
 430     }\r
 431 \r
 432     exit(0);\r
 433 }\r
 434 \r