ver3/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     ver3 : added eval and depth on ab search, more efficient gaveover\r
  21 \r
  22 --*/\r
  23 \r
  24 #include <stdlib.h>\r
  25 #include <stdio.h>\r
  26 #include <memory.h>\r
  27 #include <time.h>\r
  28 #include "ttt.h"\r
  29 \r
  30 SQUARE g_sComputerPlays = O_MARK;             // what side comp plays\r
  31 unsigned int g_uPly = 0;\r
  32 MOVE g_mvBest = { 0 };\r
  33 unsigned int g_uNodes = 0;\r
  34 \r
  35 //+----------------------------------------------------------------------------\r
  36 //\r
  37 // Function:  SquareContentsToChar\r
  38 //\r
  39 // Synopsis:  Helper function for DrawBoard\r
  40 //\r
  41 // Arguments: IN SQUARE s - a square to return a char to represent\r
  42 //            \r
  43 // Returns:   char - character representing square\r
  44 //\r
  45 //+----------------------------------------------------------------------------\r
  46 char SquareContentsToChar(IN SQUARE s)\r
  47 {\r
  48     static char c;\r
  49     switch(s)\r
  50     {\r
  51         case X_MARK:\r
  52             c = 'X';\r
  53             break;\r
  54         case O_MARK:\r
  55             c = 'O';\r
  56             break;\r
  57         case EMPTY:\r
  58             c = '_';\r
  59             break;\r
  60         default:\r
  61             ASSERT(FALSE);\r
  62             c = '?';\r
  63             break;\r
  64     }\r
  65     return(c);\r
  66 }\r
  67 \r
  68 //+----------------------------------------------------------------------------\r
  69 //\r
  70 // Function:  DrawBoard\r
  71 //\r
  72 // Synopsis:  Draw the board\r
  73 //\r
  74 // Arguments: IN POSITION *p - pointer to a position whose board to draw\r
  75 //            \r
  76 // Returns:   void\r
  77 //\r
  78 //+----------------------------------------------------------------------------\r
  79 void DrawBoard(IN POSITION *p)\r
  80 {\r
  81     COORD x, y;\r
  82 \r
  83     for (y = 0; y < BOARD_SIZE; y++)\r
  84     {\r
  85         for (x = 0; x < BOARD_SIZE; x++)\r
  86         {\r
  87             printf("%c ", SquareContentsToChar(p->sBoard[y][x]));\r
  88         }\r
  89 #ifdef DEBUG\r
  90         printf(" = %d\n", p->iHSums[y]);\r
  91 #else\r
  92         printf("\n");\r
  93 #endif\r
  94     }\r
  95 \r
  96 #ifdef DEBUG\r
  97     for (x = 0; x < BOARD_SIZE; x++)\r
  98     {\r
  99         printf("| ");\r
 100     }\r
 101     printf("\n");\r
 102     for (x = 0; x < BOARD_SIZE; x++)\r
 103     {\r
 104         printf("%d ", p->iVSums[x]);\r
 105     }\r
 106     printf("\n");\r
 107 #endif\r
 108 \r
 109     ASSERT(X_OR_O(p->sWhoseTurn));\r
 110     printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));\r
 111 }\r
 112 \r
 113 //+----------------------------------------------------------------------------\r
 114 //\r
 115 // Function:  ClearBoard\r
 116 //\r
 117 // Synopsis:  Clear the board\r
 118 //\r
 119 // Arguments: IN OUT POSITION *p - pointer to position whose board to clear\r
 120 //            \r
 121 // Returns:   void\r
 122 //\r
 123 //+----------------------------------------------------------------------------\r
 124 void ClearBoard(IN OUT POSITION *p)\r
 125 {\r
 126     memset(p->sBoard, 0, sizeof(p->sBoard));\r
 127     memset(p->iHSums, 0, sizeof(p->iHSums));\r
 128     memset(p->iVSums, 0, sizeof(p->iVSums));\r
 129     p->iDSums[0] = p->iDSums[1] = 0;\r
 130     p->sWhoseTurn = X_MARK;                   // x's go first\r
 131     p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);\r
 132 }\r
 133 \r
 134 //+----------------------------------------------------------------------------\r
 135 //\r
 136 // Function:  IsLegalMove\r
 137 //\r
 138 // Synopsis:  Determine if a given move is legal on a given board\r
 139 //\r
 140 // Arguments: IN POSITION *p - the board to play the move on\r
 141 //            IN MOVE *m - the move in question\r
 142 //            \r
 143 // Returns:   BOOL - TRUE if it's legal, FALSE otherwise\r
 144 //\r
 145 //+----------------------------------------------------------------------------\r
 146 BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)\r
 147 {\r
 148     if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))\r
 149     {\r
 150         if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))\r
 151         {\r
 152             return(TRUE);\r
 153         }\r
 154     }\r
 155     return(FALSE);\r
 156 }\r
 157 \r
 158 //+----------------------------------------------------------------------------\r
 159 //\r
 160 // Function:  GetHumanMove\r
 161 //\r
 162 // Synopsis:  Ask the human for a move\r
 163 //\r
 164 // Arguments: IN POSITION *p - the current board\r
 165 //            OUT MOVE *m - the move the human made; this struct is populated\r
 166 //                      as a side-effect of this function.\r
 167 //            \r
 168 // Returns:   void* (populates the move struct)\r
 169 //\r
 170 //+----------------------------------------------------------------------------\r
 171 void GetHumanMove(IN POSITION *p, OUT MOVE *m)\r
 172 {\r
 173     unsigned int x;\r
 174 \r
 175     do\r
 176     {\r
 177         printf("Enter your move number: ");\r
 178         scanf("%u", &x);\r
 179         \r
 180         m->cHpos = NUM_TO_HPOS(x);\r
 181         m->cVpos = NUM_TO_VPOS(x);\r
 182         m->sMark = OPPOSITE_MARK(g_sComputerPlays);\r
 183     }\r
 184     while(FALSE == IsLegalMove(p, m));\r
 185 }\r
 186 \r
 187 \r
 188 //+----------------------------------------------------------------------------\r
 189 //\r
 190 // Function:  GameOver\r
 191 //\r
 192 // Synopsis:  Is the game over? \r
 193 //\r
 194 // Arguments: IN POSITION *p - the board\r
 195 //            OUT SQUARE *psWhoWon - who won the game (if it's over)\r
 196 //            \r
 197 // Returns:   TRUE if the game is over.  Also sets psWhoWon telling\r
 198 //            which side one if the game is over.  This also serves\r
 199 //            as a very simple evaluation routine for the search.\r
 200 // \r
 201 //            FALSE if the game is not over.\r
 202 //\r
 203 //+----------------------------------------------------------------------------\r
 204 BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)\r
 205 {\r
 206     int iSum;\r
 207     COORD x;\r
 208 \r
 209     for (x = 0; x < BOARD_SIZE; x++)\r
 210     {\r
 211         iSum = p->iHSums[x];\r
 212         if (abs(iSum) == BOARD_SIZE) goto winner;\r
 213 \r
 214         iSum = p->iVSums[x];\r
 215         if (abs(iSum) == BOARD_SIZE) goto winner;\r
 216     }\r
 217 \r
 218     iSum = p->iDSums[0];\r
 219     if (abs(iSum) == BOARD_SIZE) goto winner;\r
 220 \r
 221     iSum = p->iDSums[1];\r
 222     if (abs(iSum) == BOARD_SIZE) goto winner;\r
 223 \r
 224     //\r
 225     // No one won yet, either game ongoing or draw.\r
 226     //\r
 227     *psWhoWon = EMPTY;\r
 228     if (p->uNumEmpty == 0)\r
 229     {\r
 230         return(TRUE);\r
 231     }\r
 232     else\r
 233     {\r
 234         return(FALSE);\r
 235     }\r
 236 \r
 237  winner:\r
 238     //\r
 239     // Some side won\r
 240     //\r
 241     *psWhoWon = (iSum / BOARD_SIZE);\r
 242     ASSERT(X_OR_O(*psWhoWon));\r
 243     return(TRUE);\r
 244 }\r
 245 \r
 246 \r
 247 //+----------------------------------------------------------------------------\r
 248 //\r
 249 // Function:  CountAdjacents\r
 250 //\r
 251 // Synopsis:  Return the number of marks in adjacent squares to square x\r
 252 //            that are of the same type (x or o) as the mark in square x.\r
 253 //  \r
 254 //            FIXME: does not consider diagonals\r
 255 //\r
 256 // Arguments: IN POSITION *p - the board\r
 257 //            IN SQUARE x - the square to test\r
 258 //            \r
 259 // Returns:   A count\r
 260 //\r
 261 //+----------------------------------------------------------------------------\r
 262 unsigned int CountAdjacents(IN POSITION *p, IN SQUARE x)\r
 263 {\r
 264     COORD v = NUM_TO_VPOS(x);\r
 265     COORD h = NUM_TO_HPOS(x);\r
 266     SQUARE sSide = p->sBoard[h][v];\r
 267     unsigned int uCount = 0;\r
 268 \r
 269     //\r
 270     // If nothing at square x, nothing to count\r
 271     //\r
 272     if (sSide == EMPTY) goto end;\r
 273 \r
 274     //\r
 275     // Look above, below, left and right\r
 276     //\r
 277     if ((v > 0) && (p->sBoard[h][v-1] == sSide))\r
 278     {\r
 279         uCount++;\r
 280     }\r
 281 \r
 282     if ((v < (BOARD_SIZE - 1)) && (p->sBoard[h][v+1] == sSide))\r
 283     {\r
 284         uCount++;\r
 285     }\r
 286 \r
 287     if ((h > 0) && (p->sBoard[h-1][v] == sSide))\r
 288     {\r
 289         uCount++;\r
 290     }\r
 291 \r
 292     if ((h < (BOARD_SIZE - 1)) && (p->sBoard[h+1][v] == sSide))\r
 293     {\r
 294         uCount++;\r
 295     }\r
 296 \r
 297  end:\r
 298     ASSERT(0 <= uCount);\r
 299     ASSERT(uCount <= 4);\r
 300     return(uCount);\r
 301 }\r
 302 \r
 303 \r
 304 //+----------------------------------------------------------------------------\r
 305 //\r
 306 // Function:  Eval\r
 307 //\r
 308 // Synopsis:  Evaluate a position\r
 309 //\r
 310 // Arguments: IN POSITION *p - the board\r
 311 //            \r
 312 // Returns:   A score\r
 313 //\r
 314 //+----------------------------------------------------------------------------\r
 315 int Eval(IN POSITION *p)\r
 316 {\r
 317     SQUARE sWinner;\r
 318     COORD x;\r
 319     SQUARE sMark;\r
 320     int iScore = 0;\r
 321 \r
 322     //\r
 323     // See if the game is already over.\r
 324     //\r
 325     if (TRUE == GameOver(p, &sWinner))\r
 326     {\r
 327         if (sWinner == p->sWhoseTurn)\r
 328         {\r
 329             iScore = +INFINITY - g_uPly;\r
 330             goto end;\r
 331         }\r
 332         else if (sWinner == OPPOSITE_MARK(p->sWhoseTurn))\r
 333         {\r
 334             iScore = -INFINITY + g_uPly;\r
 335             goto end;\r
 336         }\r
 337         iScore = DRAWSCORE;\r
 338         goto end;\r
 339     }\r
 340 \r
 341     //\r
 342     // No one won but instead of returning score=0 see if we can\r
 343     // find some "good characteristics" or "bad characteristics" \r
 344     // of the position and give bonuses / penalties.\r
 345     //\r
 346     for (x = BOARD_SIZE + 1; \r
 347          x < ((BOARD_SIZE * BOARD_SIZE) - BOARD_SIZE - 1);\r
 348          x++)\r
 349     {\r
 350         sMark = p->sBoard[NUM_TO_HPOS(x)][NUM_TO_VPOS(x)];\r
 351         if (sMark == p->sWhoseTurn)\r
 352         {\r
 353             iScore += CountAdjacents(p, x);\r
 354         }\r
 355         else if (sMark == OPPOSITE_MARK(p->sWhoseTurn))\r
 356         {\r
 357             iScore -= CountAdjacents(p, x);\r
 358         }\r
 359     }\r
 360 \r
 361  end:\r
 362     ASSERT(-INFINITY <= iScore);\r
 363     ASSERT(iScore <= +INFINITY);\r
 364     return(iScore);\r
 365 }\r
 366 \r
 367 \r
 368 \r
 369 //+----------------------------------------------------------------------------\r
 370 //\r
 371 // Function:  MakeMove\r
 372 //\r
 373 // Synopsis:  Make a move on a board  \r
 374 //\r
 375 // Arguments: IN OUT POSITION *p - the board\r
 376 //            IN MOVE *m - the move\r
 377 //            \r
 378 // Returns:   void\r
 379 //\r
 380 //+----------------------------------------------------------------------------\r
 381 void MakeMove(IN OUT POSITION *p, IN MOVE *m)\r
 382 {\r
 383     if (TRUE == IsLegalMove(p, m))\r
 384     {\r
 385         //\r
 386         // Make the new make on the board\r
 387         //\r
 388         ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);\r
 389         p->sBoard[m->cVpos][m->cHpos] = m->sMark;\r
 390 \r
 391         //\r
 392         // One less empty square\r
 393         //\r
 394         p->uNumEmpty--;\r
 395         ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));\r
 396 \r
 397         //\r
 398         // Update sums as appropriate\r
 399         //\r
 400         p->iHSums[m->cHpos] += m->sMark;\r
 401         ASSERT(VALID_SUM(p->iHSums[m->cHpos]));\r
 402         p->iVSums[m->cVpos] += m->sMark;\r
 403         ASSERT(VALID_SUM(p->iVSums[m->cVpos]));\r
 404         if (m->cHpos == m->cVpos)\r
 405         {\r
 406             p->iDSums[0] += m->sMark;\r
 407             ASSERT(VALID_SUM(p->iDSums[0]));\r
 408         }\r
 409         else if (m->cHpos == (BOARD_SIZE - m->cVpos))\r
 410         {\r
 411             p->iDSums[1] += m->sMark;\r
 412             ASSERT(VALID_SUM(p->iDSums[1]));\r
 413         }\r
 414 \r
 415         //\r
 416         // Other guy's turn\r
 417         //\r
 418         p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
 419         ASSERT(X_OR_O(p->sWhoseTurn));\r
 420 \r
 421         //\r
 422         // One ply deeper\r
 423         //\r
 424         g_uPly++;\r
 425         ASSERT(g_uPly > 0);\r
 426     }\r
 427 }\r
 428 \r
 429 //+----------------------------------------------------------------------------\r
 430 //\r
 431 // Function:  UnmakeMove\r
 432 //\r
 433 // Synopsis:  The opposite of MakeMove\r
 434 //\r
 435 // Arguments: IN OUT POSITION *p - the board\r
 436 //            IN MOVE *m - the move to undo\r
 437 //            \r
 438 // Returns:   void\r
 439 //\r
 440 //+----------------------------------------------------------------------------\r
 441 void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)\r
 442 {\r
 443     if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)\r
 444     {\r
 445         p->sBoard[m->cVpos][m->cHpos] = EMPTY;\r
 446 \r
 447         //\r
 448         // One more empty square\r
 449         //\r
 450         p->uNumEmpty++;\r
 451         ASSERT(p->uNumEmpty > 0);\r
 452         ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));\r
 453 \r
 454         //\r
 455         // Update sums as appropriate\r
 456         //\r
 457         p->iHSums[m->cHpos] -= m->sMark;\r
 458         ASSERT(VALID_SUM(p->iHSums[m->cHpos]));\r
 459         p->iVSums[m->cVpos] -= m->sMark;\r
 460         ASSERT(VALID_SUM(p->iVSums[m->cVpos]));\r
 461         if (m->cHpos == m->cVpos)\r
 462         {\r
 463             p->iDSums[0] -= m->sMark;\r
 464             ASSERT(VALID_SUM(p->iDSums[0]));\r
 465         }\r
 466         else if (m->cHpos == (BOARD_SIZE - m->cVpos))\r
 467         {\r
 468             p->iDSums[1] -= m->sMark;\r
 469             ASSERT(VALID_SUM(p->iDSums[1]));\r
 470         }\r
 471 \r
 472         //\r
 473         // Other guy's turn\r
 474         //\r
 475         p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
 476         ASSERT(X_OR_O(p->sWhoseTurn));\r
 477 \r
 478         //\r
 479         // One ply deeper\r
 480         //\r
 481         ASSERT(g_uPly > 0);\r
 482         g_uPly--;\r
 483     }\r
 484 }\r
 485 \r
 486 \r
 487 //+----------------------------------------------------------------------------\r
 488 //\r
 489 // Function:  AlphaBeta\r
 490 //\r
 491 // Synopsis:  An AlphaBeta Search\r
 492 //\r
 493 // Arguments: IN OUT POSITION *p - the board\r
 494 //            IN int iAlpha - the lower bound of the score window\r
 495 //            IN int iBeta - the upper bound of the score window\r
 496 //            IN int uDepth - search depth horizon\r
 497 //\r
 498 // Returns:   int\r
 499 //\r
 500 //+----------------------------------------------------------------------------\r
 501 int \r
 502 AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta, IN unsigned int uDepth)\r
 503 {\r
 504     SQUARE sWhoWon;\r
 505     SQUARE s;\r
 506     MOVE mv;\r
 507     int iScore;\r
 508     int iBestScore = -INFINITY;\r
 509 \r
 510     g_uNodes++;\r
 511 \r
 512     //\r
 513     // Evaluate this position\r
 514     //\r
 515     if (TRUE == GameOver(p, &sWhoWon))\r
 516     {\r
 517         if (sWhoWon == p->sWhoseTurn)\r
 518         {\r
 519             return(+INFINITY - g_uPly);\r
 520         }\r
 521         else if (sWhoWon == (p->sWhoseTurn * -1))\r
 522         {\r
 523             return(-INFINITY + g_uPly);\r
 524         }\r
 525         return(DRAWSCORE);\r
 526     }\r
 527     else\r
 528     {\r
 529         if (uDepth == 0)\r
 530         {\r
 531             return(Eval(p));\r
 532         }\r
 533     }\r
 534 \r
 535     //\r
 536     // No one won, game is still going.  Evaluate every\r
 537     // possible move from here.\r
 538     //\r
 539     ASSERT(p->uNumEmpty > 0);\r
 540     for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)\r
 541     {\r
 542         mv.cHpos = NUM_TO_HPOS(s);\r
 543         mv.cVpos = NUM_TO_VPOS(s);\r
 544         mv.sMark = p->sWhoseTurn;\r
 545 \r
 546         if (IsLegalMove(p, &mv))\r
 547         {\r
 548             MakeMove(p, &mv);\r
 549 \r
 550             iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uDepth - 1);\r
 551             ASSERT(-INFINITY <= iScore);\r
 552             ASSERT(iScore <= +INFINITY);\r
 553 \r
 554             UnmakeMove(p, &mv);\r
 555             \r
 556             if (iScore >= iBeta)\r
 557             {\r
 558                 return(iScore);\r
 559             }\r
 560             \r
 561             if (iScore > iBestScore)\r
 562             {\r
 563                 iBestScore = iScore;\r
 564                 \r
 565                 if (iScore > iAlpha)\r
 566                 {\r
 567                     iAlpha = iScore;\r
 568 \r
 569                     //\r
 570                     // If this is the ply 0 move, remember it.\r
 571                     //\r
 572                     if (g_uPly == 0)\r
 573                     {\r
 574                         g_mvBest = mv;\r
 575                     }\r
 576                 }\r
 577             }\r
 578         }\r
 579     }\r
 580     return(iBestScore);\r
 581 }\r
 582 \r
 583 \r
 584 //+----------------------------------------------------------------------------\r
 585 //\r
 586 // Function:  SimpleSearch\r
 587 //\r
 588 // Synopsis:  A Simple Search\r
 589 //\r
 590 // Arguments: IN OUT POSITION *p - the board\r
 591 //\r
 592 // Returns:   int\r
 593 //\r
 594 //+----------------------------------------------------------------------------\r
 595 int\r
 596 SimpleSearch(IN POSITION *p)\r
 597 {\r
 598     SQUARE sWhoWon;\r
 599     SQUARE s;\r
 600     MOVE mv;\r
 601     int iScore;\r
 602     int iBestScore = -INFINITY;\r
 603     \r
 604     g_uNodes++;\r
 605 \r
 606     //\r
 607     // Evaluate this position\r
 608     //\r
 609     if (TRUE == GameOver(p, &sWhoWon))\r
 610     {\r
 611         if (sWhoWon == p->sWhoseTurn)\r
 612         {\r
 613             return(+INFINITY - g_uPly);\r
 614         }\r
 615         else if (sWhoWon == (p->sWhoseTurn * -1))\r
 616         {\r
 617             return(-INFINITY + g_uPly);\r
 618         }\r
 619         return(DRAWSCORE);\r
 620     }\r
 621 \r
 622     //\r
 623     // No one won, game is still going.  Evaluate every\r
 624     // possible move from here.\r
 625     //\r
 626     ASSERT(p->uNumEmpty > 0);\r
 627     for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)\r
 628     {\r
 629         mv.cHpos = NUM_TO_HPOS(s);\r
 630         mv.cVpos = NUM_TO_VPOS(s);\r
 631         mv.sMark = p->sWhoseTurn;\r
 632 \r
 633         if (IsLegalMove(p, &mv))\r
 634         {\r
 635             MakeMove(p, &mv);\r
 636 \r
 637             iScore = -1 * SimpleSearch(p);\r
 638             if (iScore > iBestScore)\r
 639             {\r
 640                 iBestScore = iScore;\r
 641                 if (g_uPly == 1)\r
 642                 {\r
 643                     g_mvBest = mv;\r
 644                 }\r
 645             }\r
 646             UnmakeMove(p, &mv);\r
 647         }\r
 648     }\r
 649     return(iBestScore);\r
 650 }\r
 651 \r
 652 //+----------------------------------------------------------------------------\r
 653 //\r
 654 // Function:  SearchForComputerMove\r
 655 //\r
 656 // Synopsis:  Use our sophisticated search algorithm to find a computer\r
 657 //            move\r
 658 //\r
 659 // Arguments: IN POSITION *p - the current board\r
 660 //            OUT MOVE *m - the move the computer chooses; this move struct\r
 661 //                      is populated as a side-effect of this function.\r
 662 //            \r
 663 // Returns:   void* (populates move struct)\r
 664 //\r
 665 //+----------------------------------------------------------------------------\r
 666 void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)\r
 667 {\r
 668     unsigned int x;\r
 669 \r
 670 #if defined(PLAY_RANDOMLY)\r
 671 \r
 672     do\r
 673     {\r
 674         x = rand() % (BOARD_SIZE * BOARD_SIZE);\r
 675         m->cHpos = NUM_TO_HPOS(x);\r
 676         m->cVpos = NUM_TO_VPOS(x);\r
 677         m->sMark = g_sComputerPlays;\r
 678     }\r
 679     while(FALSE == IsLegalMove(p, m));\r
 680 \r
 681 #elif defined(SIMPLE_SEARCH)\r
 682 \r
 683     g_uPly = g_uNodes = 0;\r
 684     SimpleSearch(p);\r
 685     *m = g_mvBest;\r
 686     printf("Searched %u node(s).\n", g_uNodes);\r
 687 \r
 688 #elif defined(ALPHA_BETA_SEARCH)\r
 689 \r
 690     g_uPly = g_uNodes = 0;\r
 691     AlphaBeta(p, -INFINITY-1, +INFINITY+1, BOARD_SIZE);\r
 692     *m = g_mvBest;\r
 693     printf("Searched %u node(s).\n", g_uNodes);\r
 694 \r
 695 #else\r
 696 \r
 697     #error "No Search Strategy Defined"\r
 698 \r
 699 #endif\r
 700 }\r
 701 \r
 702 //+----------------------------------------------------------------------------\r
 703 //\r
 704 // Function:  main\r
 705 //\r
 706 // Synopsis:  The program entry point and main game loop.\r
 707 //\r
 708 // Arguments: void\r
 709 //            \r
 710 // Returns:   int\r
 711 //\r
 712 //+----------------------------------------------------------------------------\r
 713 int main(void)\r
 714 {\r
 715     POSITION p;\r
 716     MOVE mv;\r
 717     SQUARE sResult;\r
 718 \r
 719     //\r
 720     // Randomize: the random numbers returned by rand() will be based on\r
 721     // the system clock when the program starts up.\r
 722     //\r
 723     srand(time(0));\r
 724 \r
 725     //\r
 726     // Setup the board and draw it once.\r
 727     //\r
 728     ClearBoard(&p);\r
 729     DrawBoard(&p);\r
 730 \r
 731     //\r
 732     // Main game loop\r
 733     //\r
 734     do\r
 735     {\r
 736         // \r
 737         // See whose turn it is -- the human's or the computers -- and\r
 738         // get a move from whoever's turn it is.\r
 739         //\r
 740         if (p.sWhoseTurn == g_sComputerPlays)\r
 741         {\r
 742             SearchForComputerMove(&p, &mv);\r
 743         }\r
 744         else\r
 745         {\r
 746             GetHumanMove(&p, &mv);\r
 747         }\r
 748 \r
 749         //\r
 750         // Make the move on the board and draw the board again.\r
 751         //\r
 752         MakeMove(&p, &mv);\r
 753         DrawBoard(&p);\r
 754     }\r
 755     while(FALSE == GameOver(&p, &sResult));\r
 756 \r
 757     //\r
 758     // If we get here the game is over... see what happened.\r
 759     //\r
 760     switch(sResult)\r
 761     {\r
 762         case X_MARK:\r
 763             printf("\nX's win.\n");\r
 764             break;\r
 765         case O_MARK:\r
 766             printf("\nO's win.\n");\r
 767             break;\r
 768         default:\r
 769             printf("Tie (what a surprise)\n");\r
 770             break;\r
 771     }\r
 772 \r
 773     exit(0);\r
 774 }\r
 775 \r