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