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
22 ver5 : bugfixes, added singular extension to search
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;
39 //+----------------------------------------------------------------------------
41 // Function: SquareContentsToChar
43 // Synopsis: Helper function for DrawBoard
45 // Arguments: IN SQUARE s - a square to return a char to represent
47 // Returns: char - character representing square
49 //+----------------------------------------------------------------------------
50 char SquareContentsToChar(IN SQUARE s)
72 //+----------------------------------------------------------------------------
74 // Function: DrawBoard
76 // Synopsis: Draw the board
78 // Arguments: IN POSITION *p - pointer to a position whose board to draw
82 //+----------------------------------------------------------------------------
83 void DrawBoard(IN POSITION *p)
87 for (y = 0; y < g_uBoardSize; y++)
89 for (x = 0; x < g_uBoardSize; x++)
91 printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
94 printf(" = %d\n", p->iVSums[y]);
101 for (x = 0; x < g_uBoardSize; x++)
106 for (x = 0; x < g_uBoardSize; x++)
108 printf("%d ", p->iHSums[x]);
110 printf("\t%d %d\n", p->iDSums[0], p->iDSums[1]);
114 ASSERT(X_OR_O(p->sWhoseTurn));
115 printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));
118 //+----------------------------------------------------------------------------
120 // Function: ClearBoard
122 // Synopsis: Clear the board
124 // Arguments: IN OUT POSITION *p - pointer to position whose board to clear
128 //+----------------------------------------------------------------------------
129 void ClearBoard(IN OUT POSITION *p)
133 for (h = 0; h < g_uBoardSize; h++)
135 memset(p->sBoard[h], 0, sizeof(int) * g_uBoardSize);
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);
144 //+----------------------------------------------------------------------------
146 // Function: IsLegalMove
148 // Synopsis: Determine if a given move is legal on a given board
150 // Arguments: IN POSITION *p - the board to play the move on
151 // IN MOVE *m - the move in question
153 // Returns: BOOL - TRUE if it's legal, FALSE otherwise
155 //+----------------------------------------------------------------------------
156 BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)
158 if ((m->cVpos < g_uBoardSize) && (m->cHpos < g_uBoardSize))
160 if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))
168 //+----------------------------------------------------------------------------
170 // Function: GetHumanMove
172 // Synopsis: Ask the human for a move
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.
178 // Returns: void* (populates the move struct)
180 //+----------------------------------------------------------------------------
181 void GetHumanMove(IN POSITION *p, OUT MOVE *m)
187 printf("Enter your move number: ");
190 m->cHpos = NUM_TO_HPOS(x);
191 m->cVpos = NUM_TO_VPOS(x);
192 m->sMark = OPPOSITE_MARK(g_sComputerPlays);
194 while(FALSE == IsLegalMove(p, m));
198 //+----------------------------------------------------------------------------
200 // Function: GameOver
202 // Synopsis: Is the game over?
204 // Arguments: IN POSITION *p - the board
205 // OUT SQUARE *psWhoWon - who won the game (if it's over)
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.
211 // FALSE if the game is not over.
213 //+----------------------------------------------------------------------------
214 BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)
218 unsigned int uFull = (g_uBoardSize * g_uBoardSize) - p->uNumEmpty;
221 // The game can't be over if less than g_uBoardSize * 2 - 1 marks on it
223 if (uFull < (g_uBoardSize * 2 - 1))
229 for (x = 0; x < g_uBoardSize; x++)
232 if (abs(iSum) == g_uBoardSize) goto winner;
235 if (abs(iSum) == g_uBoardSize) goto winner;
239 if (abs(iSum) == g_uBoardSize) goto winner;
242 if (abs(iSum) == g_uBoardSize) goto winner;
245 // No one won yet, either game ongoing or draw.
248 if (p->uNumEmpty == 0)
261 *psWhoWon = (iSum / (int)g_uBoardSize);
262 ASSERT(X_OR_O(*psWhoWon));
267 //+----------------------------------------------------------------------------
269 // Function: MakeMove
271 // Synopsis: Make a move on a board
273 // Arguments: IN OUT POSITION *p - the board
274 // IN MOVE *m - the move
278 //+----------------------------------------------------------------------------
279 void MakeMove(IN OUT POSITION *p, IN MOVE *m)
281 if (TRUE == IsLegalMove(p, m))
284 // Make the new make on the board
286 ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
287 p->sBoard[m->cVpos][m->cHpos] = m->sMark;
290 // One less empty square
293 ASSERT(p->uNumEmpty < (g_uBoardSize * g_uBoardSize));
296 // Update sums as appropriate
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))
304 p->iDSums[0] += m->sMark;
305 ASSERT(VALID_SUM(p->iDSums[0]));
307 if (ON_DIAGONAL_2(m->cHpos, m->cVpos))
309 p->iDSums[1] += m->sMark;
310 ASSERT(VALID_SUM(p->iDSums[1]));
316 p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
317 ASSERT(X_OR_O(p->sWhoseTurn));
327 //+----------------------------------------------------------------------------
329 // Function: UnmakeMove
331 // Synopsis: The opposite of MakeMove
333 // Arguments: IN OUT POSITION *p - the board
334 // IN MOVE *m - the move to undo
338 //+----------------------------------------------------------------------------
339 void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)
341 if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)
343 p->sBoard[m->cVpos][m->cHpos] = EMPTY;
346 // One more empty square
349 ASSERT(p->uNumEmpty > 0);
350 ASSERT(p->uNumEmpty <= (g_uBoardSize * g_uBoardSize));
353 // Update sums as appropriate
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))
361 p->iDSums[0] -= m->sMark;
362 ASSERT(VALID_SUM(p->iDSums[0]));
364 if (ON_DIAGONAL_2(m->cHpos, m->cVpos))
366 p->iDSums[1] -= m->sMark;
367 ASSERT(VALID_SUM(p->iDSums[1]));
373 p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
374 ASSERT(X_OR_O(p->sWhoseTurn));
385 //+----------------------------------------------------------------------------
387 // Function: IsMoveSingular
389 // Synopsis: Determine if a move is singular (i.e. only good move) or not
391 // Arguments: IN POSITION *p - the board
392 // IN MOVE *m - the move to undo
394 // Returns: BOOL : TRUE if *m is singular
396 //+----------------------------------------------------------------------------
398 IsMoveSingular(IN POSITION *p, IN MOVE *m)
400 if ((abs(p->iVSums[m->cVpos]) >= (g_uBoardSize - 2)) ||
401 (abs(p->iHSums[m->cHpos]) >= (g_uBoardSize - 2)))
405 if ((m->cHpos == m->cVpos) &&
406 (abs(p->iDSums[0]) == (g_uBoardSize - 1)))
410 if ((m->cVpos == ((g_uBoardSize - m->cHpos) - 1)) &&
411 (abs(p->iDSums[1] == (g_uBoardSize - 1))))
420 IsMoveWorthSearching(POSITION *p, MOVE *m)
424 unsigned int uSum = 0;
426 for (h = m->cHpos - 1;
427 h < (signed int)m->cHpos + 2;
430 for (v = m->cVpos - 1;
431 v < (signed int)m->cVpos + 2;
434 if (GOOD_COORD((COORD)v) && GOOD_COORD((COORD)h))
436 uSum += abs(p->sBoard[v][h]);
452 int iSum = p->iDSums[0];
459 iSum += p->iHSums[x];
460 iSum += p->iVSums[x];
462 iSum += p->iDSums[1];
464 return(iSum * p->sWhoseTurn);
468 //+----------------------------------------------------------------------------
470 // Function: AlphaBeta
472 // Synopsis: An AlphaBeta Search
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
481 //+----------------------------------------------------------------------------
483 AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta, IN unsigned int uDepth)
489 int iBestScore = -INFINITY - 2;
490 BOOL fMoveIsSingular;
491 unsigned int uNextDepth;
492 unsigned int uMoveNum = 1;
497 // Evaluate this position
499 if (TRUE == GameOver(p, &sWhoWon))
501 if (sWhoWon == p->sWhoseTurn)
503 return(+INFINITY - g_uPly);
505 else if (sWhoWon == (p->sWhoseTurn * -1))
507 return(-INFINITY + g_uPly);
511 else if (uDepth == 0)
517 // No one won, game is still going. Evaluate some moves from here.
519 ASSERT(p->uNumEmpty > 0);
520 for (s = 0; s < (g_uBoardSize * g_uBoardSize); s++)
522 mv.cHpos = NUM_TO_HPOS(s);
523 mv.cVpos = NUM_TO_VPOS(s);
524 mv.sMark = p->sWhoseTurn;
526 if (IsLegalMove(p, &mv))
529 // Determine if move is singular
531 fMoveIsSingular = IsMoveSingular(p, &mv);
533 if ((FALSE == fMoveIsSingular) &&
537 // Determine if we should bother with this subtree...
539 if (FALSE == IsMoveWorthSearching(p, &mv))
551 uNextDepth = uDepth - 1;
552 if (TRUE == fMoveIsSingular)
557 iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uNextDepth);
558 ASSERT(-INFINITY <= iScore);
559 ASSERT(iScore <= +INFINITY);
571 if (iScore > iBestScore)
583 // If this is the ply 0 move, remember it.
596 //+----------------------------------------------------------------------------
598 // Function: SearchForComputerMove
600 // Synopsis: Use our sophisticated search algorithm to find a computer
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.
607 // Returns: void* (populates move struct)
609 //+----------------------------------------------------------------------------
610 void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)
612 #if defined(PLAY_RANDOMLY)
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;
622 while(FALSE == IsLegalMove(p, m));
624 #elif defined(ALPHA_BETA_SEARCH)
627 g_uPly = g_uNodes = g_uExtensions = 0;
629 AlphaBeta(p, -INFINITY-1, +INFINITY+1, 3);
631 printf("Searched %u node(s), %u extension(s)\n",
636 #error "No Search Strategy Defined"
641 //+----------------------------------------------------------------------------
645 // Synopsis: The program entry point and main game loop.
651 //+----------------------------------------------------------------------------
661 // Randomize: the random numbers returned by rand() will be based on
662 // the system clock when the program starts up.
671 printf("How big do you want the board (2..20)? ");
672 scanf("%u", &g_uBoardSize);
674 while((g_uBoardSize < 2) || (g_uBoardSize > 20));
677 // Allocate space for 2d int array ptr
679 p.sBoard = (SQUARE **)malloc(g_uBoardSize * sizeof(SQUARE *));
680 if (NULL == p.sBoard)
682 fprintf(stderr, "Out of memory\n");
687 // Allocate each row of the array
689 for (u = 0; u < g_uBoardSize; u++)
691 p.sBoard[u] = (SQUARE *)
692 malloc(g_uBoardSize * sizeof(SQUARE));
693 if (NULL == p.sBoard[u])
695 fprintf(stderr, "Out of memory!\n");
701 // Allocate space for sums
703 p.iHSums = (int *)malloc(g_uBoardSize * sizeof(int));
704 p.iVSums = (int *)malloc(g_uBoardSize * sizeof(int));
705 if ((NULL == p.iHSums) ||
708 fprintf(stderr, "Out of memory!\n");
713 // Setup the board and draw it once.
724 // See whose turn it is -- the human's or the computers -- and
725 // get a move from whoever's turn it is.
727 if (p.sWhoseTurn == g_sComputerPlays)
729 SearchForComputerMove(&p, &mv);
733 //SearchForComputerMove(&p, &mv);
734 GetHumanMove(&p, &mv);
738 // Make the move on the board and draw the board again.
743 while(FALSE == GameOver(&p, &sResult));
746 // If we get here the game is over... see what happened.
751 printf("\nX's win.\n");
754 printf("\nO's win.\n");
757 printf("Tie (what a surprise)\n");
762 // TODO: cleanup heap