ver2/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
  21 --*/
  22
  23 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <memory.h>
  26 #include <time.h>
  27 #include "ttt.h"
  28
  29 SQUARE g_sComputerPlays = O_MARK;             // what side comp plays
  30 unsigned int g_uPly = 0;
  31 MOVE g_mvBest = { 0 };
  32 unsigned int g_uNodes = 0;
  33
  34 //+----------------------------------------------------------------------------
  35 //
  36 // Function:  SquareContentsToChar
  37 //
  38 // Synopsis:  Helper function for DrawBoard
  39 //
  40 // Arguments: IN SQUARE s - a square to return a char to represent
  41 //
  42 // Returns:   char - character representing square
  43 //
  44 //+----------------------------------------------------------------------------
  45 char SquareContentsToChar(IN SQUARE s)
  46 {
  47     static char c;
  48     switch(s)
  49     {
  50         case X_MARK:
  51             c = 'X';
  52             break;
  53         case O_MARK:
  54             c = 'O';
  55             break;
  56         case EMPTY:
  57             c = '_';
  58             break;
  59         default:
  60             ASSERT(FALSE);
  61             c = '?';
  62             break;
  63     }
  64     return(c);
  65 }
  66
  67 //+----------------------------------------------------------------------------
  68 //
  69 // Function:  DrawBoard
  70 //
  71 // Synopsis:  Draw the board
  72 //
  73 // Arguments: IN POSITION *p - pointer to a position whose board to draw
  74 //
  75 // Returns:   void
  76 //
  77 //+----------------------------------------------------------------------------
  78 void DrawBoard(IN POSITION *p)
  79 {
  80     COORD x, y;
  81
  82     for (y = 0; y < BOARD_SIZE; y++)
  83     {
  84         for (x = 0; x < BOARD_SIZE; x++)
  85         {
  86             printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
  87         }
  88         printf("\n");
  89     }
  90     ASSERT(X_OR_O(p->sWhoseTurn));
  91     printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));
  92 }
  93
  94 //+----------------------------------------------------------------------------
  95 //
  96 // Function:  ClearBoard
  97 //
  98 // Synopsis:  Clear the board
  99 //
 100 // Arguments: IN OUT POSITION *p - pointer to position whose board to clear
 101 //
 102 // Returns:   void
 103 //
 104 //+----------------------------------------------------------------------------
 105 void ClearBoard(IN OUT POSITION *p)
 106 {
 107     memset(p->sBoard, 0, sizeof(p->sBoard));
 108     p->sWhoseTurn = X_MARK;                   // x's go first
 109     p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);
 110 }
 111
 112 //+----------------------------------------------------------------------------
 113 //
 114 // Function:  IsLegalMove
 115 //
 116 // Synopsis:  Determine if a given move is legal on a given board
 117 //
 118 // Arguments: IN POSITION *p - the board to play the move on
 119 //            IN MOVE *m - the move in question
 120 //
 121 // Returns:   BOOL - TRUE if it's legal, FALSE otherwise
 122 //
 123 //+----------------------------------------------------------------------------
 124 BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)
 125 {
 126     if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))
 127     {
 128         if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))
 129         {
 130             return(TRUE);
 131         }
 132     }
 133     return(FALSE);
 134 }
 135
 136 //+----------------------------------------------------------------------------
 137 //
 138 // Function:  GetHumanMove
 139 //
 140 // Synopsis:  Ask the human for a move
 141 //
 142 // Arguments: IN POSITION *p - the current board
 143 //            OUT MOVE *m - the move the human made; this struct is populated
 144 //                      as a side-effect of this function.
 145 //
 146 // Returns:   void* (populates the move struct)
 147 //
 148 //+----------------------------------------------------------------------------
 149 void GetHumanMove(IN POSITION *p, OUT MOVE *m)
 150 {
 151     unsigned int x;
 152
 153     do
 154     {
 155         printf("Enter your move number: ");
 156         scanf("%u", &x);
 157
 158         m->cHpos = NUM_TO_HPOS(x);
 159         m->cVpos = NUM_TO_VPOS(x);
 160         m->sMark = OPPOSITE_MARK(g_sComputerPlays);
 161     }
 162     while(FALSE == IsLegalMove(p, m));
 163 }
 164
 165 //+----------------------------------------------------------------------------
 166 //
 167 // Function:  GameOver
 168 //
 169 // Synopsis:  Is the game over?
 170 //
 171 // Arguments: IN POSITION *p - the board
 172 //            OUT SQUARE *psWhoWon - who won the game (if it's over)
 173 //
 174 // Returns:   TRUE if the game is over.  Also sets psWhoWon telling
 175 //            which side one if the game is over.  This also serves
 176 //            as a very simple evaluation routine for the search.
 177 //
 178 //            FALSE if the game is not over.
 179 //
 180 //+----------------------------------------------------------------------------
 181 BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)
 182 {
 183     int iSum;
 184     COORD x, y;
 185
 186     for (x = 0; x < BOARD_SIZE; x++)
 187     {
 188         iSum = 0;
 189
 190         for (y = 0; y < BOARD_SIZE; y++)
 191         {
 192             iSum += p->sBoard[x][y];
 193         }
 194         if (abs(iSum) == BOARD_SIZE) goto winner;
 195     }
 196
 197     for (y = 0; y < BOARD_SIZE; y++)
 198     {
 199         iSum = 0;
 200
 201         for (x = 0; x < BOARD_SIZE; x++)
 202         {
 203             iSum += p->sBoard[x][y];
 204         }
 205         if (abs(iSum) == BOARD_SIZE) goto winner;
 206     }
 207
 208     iSum = 0;
 209     for (x = 0; x < BOARD_SIZE; x++)
 210     {
 211         iSum += p->sBoard[x][x];
 212     }
 213     if (abs(iSum) == BOARD_SIZE) goto winner;
 214
 215     iSum = 0;
 216     for (x = 0; x < BOARD_SIZE; x++)
 217     {
 218         iSum += p->sBoard[x][(BOARD_SIZE - 1 - x)];
 219     }
 220     if (abs(iSum) == BOARD_SIZE) goto winner;
 221
 222     *psWhoWon = EMPTY;
 223     if (p->uNumEmpty == 0)
 224     {
 225         return(TRUE);
 226     }
 227     else
 228     {
 229         return(FALSE);
 230     }
 231
 232  winner:
 233     *psWhoWon = (iSum / BOARD_SIZE);
 234     ASSERT(X_OR_O(*psWhoWon));
 235     return(TRUE);
 236 }
 237
 238
 239 //+----------------------------------------------------------------------------
 240 //
 241 // Function:  MakeMove
 242 //
 243 // Synopsis:  Make a move on a board
 244 //
 245 // Arguments: IN OUT POSITION *p - the board
 246 //            IN MOVE *m - the move
 247 //
 248 // Returns:   void
 249 //
 250 //+----------------------------------------------------------------------------
 251 void MakeMove(IN OUT POSITION *p, IN MOVE *m)
 252 {
 253     if (TRUE == IsLegalMove(p, m))
 254     {
 255         ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
 256         p->sBoard[m->cVpos][m->cHpos] = m->sMark;
 257         p->uNumEmpty--;
 258         ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));
 259         p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
 260         g_uPly++;
 261         ASSERT(g_uPly > 0);
 262     }
 263 }
 264
 265 //+----------------------------------------------------------------------------
 266 //
 267 // Function:  UnmakeMove
 268 //
 269 // Synopsis:  The opposite of MakeMove
 270 //
 271 // Arguments: IN OUT POSITION *p - the board
 272 //            IN MOVE *m - the move to undo
 273 //
 274 // Returns:   void
 275 //
 276 //+----------------------------------------------------------------------------
 277 void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)
 278 {
 279     if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)
 280     {
 281         p->sBoard[m->cVpos][m->cHpos] = EMPTY;
 282         p->uNumEmpty++;
 283         ASSERT(p->uNumEmpty > 0);
 284         ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));
 285         p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
 286         ASSERT(g_uPly > 0);
 287         g_uPly--;
 288     }
 289 }
 290
 291
 292 int
 293 AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta)
 294 {
 295     SQUARE sWhoWon;
 296     SQUARE s;
 297     MOVE mv;
 298     int iScore;
 299     int iBestScore = -INFINITY;
 300
 301     g_uNodes++;
 302
 303     //
 304     // Evaluate this position
 305     //
 306     if (TRUE == GameOver(p, &sWhoWon))
 307     {
 308         if (sWhoWon == p->sWhoseTurn)
 309         {
 310             return(+INFINITY - g_uPly);
 311         }
 312         else if (sWhoWon == (p->sWhoseTurn * -1))
 313         {
 314             return(-INFINITY + g_uPly);
 315         }
 316         return(DRAWSCORE);
 317     }
 318
 319     //
 320     // No one won, game is still going.  Evaluate every
 321     // possible move from here.
 322     //
 323     ASSERT(p->uNumEmpty > 0);
 324     for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)
 325     {
 326         mv.cHpos = NUM_TO_HPOS(s);
 327         mv.cVpos = NUM_TO_VPOS(s);
 328         mv.sMark = p->sWhoseTurn;
 329
 330         if (IsLegalMove(p, &mv))
 331         {
 332             MakeMove(p, &mv);
 333
 334             iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha);
 335
 336             UnmakeMove(p, &mv);
 337
 338             if (iScore >= iBeta)
 339             {
 340                 return(iScore);
 341             }
 342
 343             if (iScore > iBestScore)
 344             {
 345                 iBestScore = iScore;
 346
 347                 if (iScore > iAlpha)
 348                 {
 349                     iAlpha = iScore;
 350                     if (g_uPly == 0)
 351                     {
 352                         g_mvBest = mv;
 353                     }
 354                 }
 355             }
 356         }
 357     }
 358     return(iBestScore);
 359 }
 360
 361
 362 int
 363 SimpleSearch(IN POSITION *p)
 364 {
 365     SQUARE sWhoWon;
 366     SQUARE s;
 367     MOVE mv;
 368     int iScore;
 369     int iBestScore = -INFINITY;
 370
 371     g_uNodes++;
 372
 373     //
 374     // Evaluate this position
 375     //
 376     if (TRUE == GameOver(p, &sWhoWon))
 377     {
 378         if (sWhoWon == p->sWhoseTurn)
 379         {
 380             return(+INFINITY - g_uPly);
 381         }
 382         else if (sWhoWon == (p->sWhoseTurn * -1))
 383         {
 384             return(-INFINITY + g_uPly);
 385         }
 386         return(DRAWSCORE);
 387     }
 388
 389     //
 390     // No one won, game is still going.  Evaluate every
 391     // possible move from here.
 392     //
 393     ASSERT(p->uNumEmpty > 0);
 394     for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)
 395     {
 396         mv.cHpos = NUM_TO_HPOS(s);
 397         mv.cVpos = NUM_TO_VPOS(s);
 398         mv.sMark = p->sWhoseTurn;
 399
 400         if (IsLegalMove(p, &mv))
 401         {
 402             MakeMove(p, &mv);
 403
 404             iScore = -1 * SimpleSearch(p);
 405             if (iScore > iBestScore)
 406             {
 407                 iBestScore = iScore;
 408                 if (g_uPly == 1)
 409                 {
 410                     g_mvBest = mv;
 411                 }
 412             }
 413
 414             UnmakeMove(p, &mv);
 415         }
 416     }
 417     return(iBestScore);
 418 }
 419
 420 //+----------------------------------------------------------------------------
 421 //
 422 // Function:  SearchForComputerMove
 423 //
 424 // Synopsis:  Use our sophisticated search algorithm to find a computer
 425 //            move
 426 //
 427 // Arguments: IN POSITION *p - the current board
 428 //            OUT MOVE *m - the move the computer chooses; this move struct
 429 //                      is populated as a side-effect of this function.
 430 //
 431 // Returns:   void* (populates move struct)
 432 //
 433 //+----------------------------------------------------------------------------
 434 void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)
 435 {
 436     unsigned int x;
 437
 438 #if defined(PLAY_RANDOMLY)
 439     do
 440     {
 441         x = rand() % (BOARD_SIZE * BOARD_SIZE);
 442         m->cHpos = NUM_TO_HPOS(x);
 443         m->cVpos = NUM_TO_VPOS(x);
 444         m->sMark = g_sComputerPlays;
 445     }
 446     while(FALSE == IsLegalMove(p, m));
 447 #elif defined(SIMPLE_SEARCH)
 448     g_uPly = g_uNodes = 0;
 449     SimpleSearch(p);
 450     *m = g_mvBest;
 451     printf("Searched %u node(s).\n", g_uNodes);
 452 #elif defined(ALPHA_BETA_SEARCH)
 453     g_uPly = g_uNodes = 0;
 454     AlphaBeta(p, -INFINITY-1, +INFINITY+1);
 455     *m = g_mvBest;
 456     printf("Searched %u node(s).\n", g_uNodes);
 457 #else
 458     #error "No Search Strategy Defined"
 459 #endif
 460 }
 461
 462 //+----------------------------------------------------------------------------
 463 //
 464 // Function:  main
 465 //
 466 // Synopsis:  The program entry point and main game loop.
 467 //
 468 // Arguments: void
 469 //
 470 // Returns:   int
 471 //
 472 //+----------------------------------------------------------------------------
 473 int main(void)
 474 {
 475     POSITION p;
 476     MOVE mv;
 477     SQUARE sResult;
 478
 479     //
 480     // Randomize: the random numbers returned by rand() will be based on
 481     // the system clock when the program starts up.
 482     //
 483     srand(time(0));
 484
 485     //
 486     // Setup the board and draw it once.
 487     //
 488     ClearBoard(&p);
 489     DrawBoard(&p);
 490
 491     //
 492     // Main game loop
 493     //
 494     do
 495     {
 496         //
 497         // See whose turn it is -- the human's or the computers -- and
 498         // get a move from whoever's turn it is.
 499         //
 500         if (p.sWhoseTurn == g_sComputerPlays)
 501         {
 502             SearchForComputerMove(&p, &mv);
 503         }
 504         else
 505         {
 506             GetHumanMove(&p, &mv);
 507         }
 508
 509         //
 510         // Make the move on the board and draw the board again.
 511         //
 512         MakeMove(&p, &mv);
 513         DrawBoard(&p);
 514     }
 515     while(FALSE == GameOver(&p, &sResult));
 516
 517     //
 518     // If we get here the game is over... see what happened.
 519     //
 520     switch(sResult)
 521     {
 522         case X_MARK:
 523             printf("\nX's win.\n");
 524             break;
 525         case O_MARK:
 526             printf("\nO's win.\n");
 527             break;
 528         default:
 529             printf("Tie (what a surprise)\n");
 530             break;
 531     }
 532
 533     exit(0);
 534 }
 535