ver2/ttt.c

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