9 tic tac toe program to illustrate simple minimax searching
13 Scott Gasch (SGasch) 18 Mar 2004
19 ver2 : alpha beta search
20 ver3 : added eval and depth on ab search, more efficient gaveover
21 ver4 : variable sized board
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;
37 //+----------------------------------------------------------------------------
39 // Function: SquareContentsToChar
41 // Synopsis: Helper function for DrawBoard
43 // Arguments: IN SQUARE s - a square to return a char to represent
45 // Returns: char - character representing square
47 //+----------------------------------------------------------------------------
48 char SquareContentsToChar(IN SQUARE s)
70 //+----------------------------------------------------------------------------
72 // Function: DrawBoard
74 // Synopsis: Draw the board
76 // Arguments: IN POSITION *p - pointer to a position whose board to draw
80 //+----------------------------------------------------------------------------
81 void DrawBoard(IN POSITION *p)
85 for (y = 0; y < g_uBoardSize; y++)
87 for (x = 0; x < g_uBoardSize; x++)
89 printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
92 printf(" = %d\n", p->iVSums[y]);
99 for (x = 0; x < g_uBoardSize; x++)
104 for (x = 0; x < g_uBoardSize; x++)
106 printf("%d ", p->iHSums[x]);
108 printf("\t%d %d\n", p->iDSums[0], p->iDSums[1]);
112 ASSERT(X_OR_O(p->sWhoseTurn));
113 printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));
116 //+----------------------------------------------------------------------------
118 // Function: ClearBoard
120 // Synopsis: Clear the board
122 // Arguments: IN OUT POSITION *p - pointer to position whose board to clear
126 //+----------------------------------------------------------------------------
127 void ClearBoard(IN OUT POSITION *p)
131 for (h = 0; h < g_uBoardSize; h++)
133 memset(p->sBoard[h], 0, sizeof(int) * g_uBoardSize);
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);
142 //+----------------------------------------------------------------------------
144 // Function: IsLegalMove
146 // Synopsis: Determine if a given move is legal on a given board
148 // Arguments: IN POSITION *p - the board to play the move on
149 // IN MOVE *m - the move in question
151 // Returns: BOOL - TRUE if it's legal, FALSE otherwise
153 //+----------------------------------------------------------------------------
154 BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)
156 if ((m->cVpos < g_uBoardSize) && (m->cHpos < g_uBoardSize))
158 if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))
166 //+----------------------------------------------------------------------------
168 // Function: GetHumanMove
170 // Synopsis: Ask the human for a move
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.
176 // Returns: void* (populates the move struct)
178 //+----------------------------------------------------------------------------
179 void GetHumanMove(IN POSITION *p, OUT MOVE *m)
185 printf("Enter your move number: ");
188 m->cHpos = NUM_TO_HPOS(x);
189 m->cVpos = NUM_TO_VPOS(x);
190 m->sMark = OPPOSITE_MARK(g_sComputerPlays);
192 while(FALSE == IsLegalMove(p, m));
196 //+----------------------------------------------------------------------------
198 // Function: GameOver
200 // Synopsis: Is the game over?
202 // Arguments: IN POSITION *p - the board
203 // OUT SQUARE *psWhoWon - who won the game (if it's over)
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.
209 // FALSE if the game is not over.
211 //+----------------------------------------------------------------------------
212 BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)
216 unsigned int uFull = (g_uBoardSize * g_uBoardSize) - p->uNumEmpty;
219 // The game can't be over if less than g_uBoardSize * 2 - 1 marks on it
221 if (uFull < (g_uBoardSize * 2 - 1))
227 for (x = 0; x < g_uBoardSize; x++)
230 if (abs(iSum) == g_uBoardSize) goto winner;
233 if (abs(iSum) == g_uBoardSize) goto winner;
237 if (abs(iSum) == g_uBoardSize) goto winner;
240 if (abs(iSum) == g_uBoardSize) goto winner;
243 // No one won yet, either game ongoing or draw.
246 if (p->uNumEmpty == 0)
259 *psWhoWon = (iSum / (int)g_uBoardSize);
260 ASSERT(X_OR_O(*psWhoWon));
265 //+----------------------------------------------------------------------------
267 // Function: CountAdjacents
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.
272 // FIXME: does not consider diagonals
274 // Arguments: IN POSITION *p - the board
275 // IN SQUARE x - the square to test
279 //+----------------------------------------------------------------------------
280 unsigned int CountAdjacents(IN POSITION *p, IN COORD x)
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;
288 // If nothing at square x, nothing to count
290 if (sSide == EMPTY) goto end;
293 // Look above, below, left and right
295 if ((v > 0) && (p->sBoard[h][v-1] == sSide))
300 if ((v < (g_uBoardSize - 1)) && (p->sBoard[h][v+1] == sSide))
305 if ((h > 0) && (p->sBoard[h-1][v] == sSide))
310 if ((h < (g_uBoardSize - 1)) && (p->sBoard[h+1][v] == sSide))
322 //+----------------------------------------------------------------------------
326 // Synopsis: Evaluate a position
328 // Arguments: IN POSITION *p - the board
332 //+----------------------------------------------------------------------------
333 int Eval(IN POSITION *p)
341 // See if the game is already over.
343 if (TRUE == GameOver(p, &sWinner))
345 if (sWinner == p->sWhoseTurn)
347 iScore = +INFINITY - g_uPly;
350 else if (sWinner == OPPOSITE_MARK(p->sWhoseTurn))
352 iScore = -INFINITY + g_uPly;
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.
364 for (x = g_uBoardSize + 1;
365 x < ((g_uBoardSize * g_uBoardSize) - g_uBoardSize - 1);
368 sMark = p->sBoard[NUM_TO_HPOS(x)][NUM_TO_VPOS(x)];
369 if (sMark == p->sWhoseTurn)
371 iScore += CountAdjacents(p, x);
373 else if (sMark == OPPOSITE_MARK(p->sWhoseTurn))
375 iScore -= CountAdjacents(p, x);
380 ASSERT(-INFINITY <= iScore);
381 ASSERT(iScore <= +INFINITY);
387 //+----------------------------------------------------------------------------
389 // Function: MakeMove
391 // Synopsis: Make a move on a board
393 // Arguments: IN OUT POSITION *p - the board
394 // IN MOVE *m - the move
398 //+----------------------------------------------------------------------------
399 void MakeMove(IN OUT POSITION *p, IN MOVE *m)
401 if (TRUE == IsLegalMove(p, m))
404 // Make the new make on the board
406 ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
407 p->sBoard[m->cVpos][m->cHpos] = m->sMark;
410 // One less empty square
413 ASSERT(p->uNumEmpty < (g_uBoardSize * g_uBoardSize));
416 // Update sums as appropriate
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)
424 p->iDSums[0] += m->sMark;
425 ASSERT(VALID_SUM(p->iDSums[0]));
427 if (m->cVpos == ((g_uBoardSize - m->cHpos) - 1))
429 p->iDSums[1] += m->sMark;
430 ASSERT(VALID_SUM(p->iDSums[1]));
436 p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
437 ASSERT(X_OR_O(p->sWhoseTurn));
447 //+----------------------------------------------------------------------------
449 // Function: UnmakeMove
451 // Synopsis: The opposite of MakeMove
453 // Arguments: IN OUT POSITION *p - the board
454 // IN MOVE *m - the move to undo
458 //+----------------------------------------------------------------------------
459 void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)
461 if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)
463 p->sBoard[m->cVpos][m->cHpos] = EMPTY;
466 // One more empty square
469 ASSERT(p->uNumEmpty > 0);
470 ASSERT(p->uNumEmpty <= (g_uBoardSize * g_uBoardSize));
473 // Update sums as appropriate
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)
481 p->iDSums[0] -= m->sMark;
482 ASSERT(VALID_SUM(p->iDSums[0]));
484 if (m->cVpos == ((g_uBoardSize - m->cHpos) - 1))
486 p->iDSums[1] -= m->sMark;
487 ASSERT(VALID_SUM(p->iDSums[1]));
493 p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
494 ASSERT(X_OR_O(p->sWhoseTurn));
505 //+----------------------------------------------------------------------------
507 // Function: AlphaBeta
509 // Synopsis: An AlphaBeta Search
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
518 //+----------------------------------------------------------------------------
520 AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta, IN unsigned int uDepth)
526 int iBestScore = -INFINITY - 2;
531 // Evaluate this position
533 if (TRUE == GameOver(p, &sWhoWon))
535 if (sWhoWon == p->sWhoseTurn)
537 return(+INFINITY - g_uPly);
539 else if (sWhoWon == (p->sWhoseTurn * -1))
541 return(-INFINITY + g_uPly);
545 else if (uDepth == 0)
547 return(0);//Eval(p));
551 // No one won, game is still going. Evaluate every
552 // possible move from here.
554 ASSERT(p->uNumEmpty > 0);
555 for (s = 0; s < (g_uBoardSize * g_uBoardSize); s++)
557 mv.cHpos = NUM_TO_HPOS(s);
558 mv.cVpos = NUM_TO_VPOS(s);
559 mv.sMark = p->sWhoseTurn;
561 if (IsLegalMove(p, &mv))
565 iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uDepth - 1);
566 ASSERT(-INFINITY <= iScore);
567 ASSERT(iScore <= +INFINITY);
579 if (iScore > iBestScore)
591 // If this is the ply 0 move, remember it.
605 //+----------------------------------------------------------------------------
607 // Function: SimpleSearch
609 // Synopsis: A Simple Search
611 // Arguments: IN OUT POSITION *p - the board
615 //+----------------------------------------------------------------------------
617 SimpleSearch(IN POSITION *p)
623 int iBestScore = -INFINITY;
628 // Evaluate this position
630 if (TRUE == GameOver(p, &sWhoWon))
632 if (sWhoWon == p->sWhoseTurn)
634 return(+INFINITY - g_uPly);
636 else if (sWhoWon == (p->sWhoseTurn * -1))
638 return(-INFINITY + g_uPly);
644 // No one won, game is still going. Evaluate every
645 // possible move from here.
647 ASSERT(p->uNumEmpty > 0);
648 for (s = 0; s < (g_uBoardSize * g_uBoardSize); s++)
650 mv.cHpos = NUM_TO_HPOS(s);
651 mv.cVpos = NUM_TO_VPOS(s);
652 mv.sMark = p->sWhoseTurn;
654 if (IsLegalMove(p, &mv))
658 iScore = -1 * SimpleSearch(p);
659 if (iScore > iBestScore)
673 //+----------------------------------------------------------------------------
675 // Function: SearchForComputerMove
677 // Synopsis: Use our sophisticated search algorithm to find a computer
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.
684 // Returns: void* (populates move struct)
686 //+----------------------------------------------------------------------------
687 void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)
689 #if defined(PLAY_RANDOMLY)
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;
699 while(FALSE == IsLegalMove(p, m));
701 #elif defined(SIMPLE_SEARCH)
703 g_uPly = g_uNodes = 0;
706 printf("Searched %u node(s).\n", g_uNodes);
708 #elif defined(ALPHA_BETA_SEARCH)
710 g_uPly = g_uNodes = 0;
711 AlphaBeta(p, -INFINITY-1, +INFINITY+1, g_uBoardSize * 2);
713 printf("Searched %u node(s).\n", g_uNodes);
717 #error "No Search Strategy Defined"
722 //+----------------------------------------------------------------------------
726 // Synopsis: The program entry point and main game loop.
732 //+----------------------------------------------------------------------------
742 // Randomize: the random numbers returned by rand() will be based on
743 // the system clock when the program starts up.
752 printf("How big do you want the board (2..20)? ");
753 scanf("%u", &g_uBoardSize);
755 while((g_uBoardSize < 2) || (g_uBoardSize > 20));
758 // Allocate space for 2d int array ptr
760 p.sBoard = (int **)malloc(g_uBoardSize * sizeof(int *));
761 if (NULL == p.sBoard)
763 fprintf(stderr, "Out of memory\n");
768 // Allocate each row of the array
770 for (u = 0; u < g_uBoardSize; u++)
772 p.sBoard[u] = (int *)
773 malloc(g_uBoardSize * sizeof(int));
774 if (NULL == p.sBoard[u])
776 fprintf(stderr, "Out of memory!\n");
782 // Allocate space for sums
784 p.iHSums = (int *)malloc(g_uBoardSize * sizeof(int));
785 p.iVSums = (int *)malloc(g_uBoardSize * sizeof(int));
786 if ((NULL == p.iHSums) ||
789 fprintf(stderr, "Out of memory!\n");
794 // Setup the board and draw it once.
805 // See whose turn it is -- the human's or the computers -- and
806 // get a move from whoever's turn it is.
808 if (p.sWhoseTurn == g_sComputerPlays)
810 SearchForComputerMove(&p, &mv);
814 GetHumanMove(&p, &mv);
818 // Make the move on the board and draw the board again.
823 while(FALSE == GameOver(&p, &sResult));
826 // If we get here the game is over... see what happened.
831 printf("\nX's win.\n");
834 printf("\nO's win.\n");
837 printf("Tie (what a surprise)\n");
842 // TODO: cleanup heap