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