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