ver4/ttt.c

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