ver1/ttt.c

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