-#include <stdlib.h>\r
-#include <stdio.h>\r
-#include <memory.h>\r
-#include <time.h>\r
-#include "ttt.h"\r
-\r
-SQUARE g_sComputerPlays = O_MARK; // what side comp plays\r
-unsigned int g_uPly = 0;\r
-MOVE g_mvBest = { 0 };\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SquareContentsToChar\r
-//\r
-// Synopsis: Helper function for DrawBoard\r
-//\r
-// Arguments: IN SQUARE s - a square to return a char to represent\r
-// \r
-// Returns: char - character representing square\r
-//\r
-//+----------------------------------------------------------------------------\r
-char SquareContentsToChar(IN SQUARE s)\r
-{\r
- static char c;\r
- switch(s)\r
- {\r
- case X_MARK:\r
- c = 'X';\r
- break;\r
- case O_MARK:\r
- c = 'O';\r
- break;\r
- case EMPTY:\r
- c = '_';\r
- break;\r
- default:\r
- ASSERT(FALSE);\r
- c = '?';\r
- break;\r
- }\r
- return(c);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: DrawBoard\r
-//\r
-// Synopsis: Draw the board\r
-//\r
-// Arguments: IN POSITION *p - pointer to a position whose board to draw\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void DrawBoard(IN POSITION *p)\r
-{\r
- COORD x, y;\r
-\r
- for (y = 0; y < BOARD_SIZE; y++)\r
- {\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- printf("%c ", SquareContentsToChar(p->sBoard[y][x]));\r
- }\r
- printf("\n");\r
- }\r
- ASSERT(X_OR_O(p->sWhoseTurn));\r
- printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: ClearBoard\r
-//\r
-// Synopsis: Clear the board\r
-//\r
-// Arguments: IN OUT POSITION *p - pointer to position whose board to clear\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void ClearBoard(IN OUT POSITION *p)\r
-{\r
- memset(p->sBoard, 0, sizeof(p->sBoard));\r
- p->sWhoseTurn = X_MARK; // x's go first\r
- p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: IsLegalMove\r
-//\r
-// Synopsis: Determine if a given move is legal on a given board\r
-//\r
-// Arguments: IN POSITION *p - the board to play the move on\r
-// IN MOVE *m - the move in question\r
-// \r
-// Returns: BOOL - TRUE if it's legal, FALSE otherwise\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)\r
-{\r
- if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))\r
- {\r
- if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))\r
- {\r
- return(TRUE);\r
- }\r
- }\r
- return(FALSE);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: GetHumanMove\r
-//\r
-// Synopsis: Ask the human for a move\r
-//\r
-// Arguments: IN POSITION *p - the current board\r
-// OUT MOVE *m - the move the human made; this struct is populated\r
-// as a side-effect of this function.\r
-// \r
-// Returns: void* (populates the move struct)\r
-//\r
-//+----------------------------------------------------------------------------\r
-void GetHumanMove(IN POSITION *p, OUT MOVE *m)\r
-{\r
- unsigned int x;\r
-\r
- do\r
- {\r
- printf("Enter your move number: ");\r
- scanf("%u", &x);\r
- \r
- m->cHpos = NUM_TO_HPOS(x);\r
- m->cVpos = NUM_TO_VPOS(x);\r
- m->sMark = OPPOSITE_MARK(g_sComputerPlays);\r
- }\r
- while(FALSE == IsLegalMove(p, m));\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: GameOver\r
-//\r
-// Synopsis: Is the game over? \r
-//\r
-// Arguments: IN POSITION *p - the board\r
-// OUT SQUARE *psWhoWon - who won the game (if it's over)\r
-// \r
-// Returns: TRUE if the game is over. Also sets psWhoWon telling\r
-// which side one if the game is over. This also serves\r
-// as a very simple evaluation routine for the search.\r
-// \r
-// FALSE if the game is not over.\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)\r
-{\r
- int iSum;\r
- COORD x, y;\r
-\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum = 0;\r
-\r
- for (y = 0; y < BOARD_SIZE; y++)\r
- {\r
- iSum += p->sBoard[x][y];\r
- }\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
- }\r
-\r
- for (y = 0; y < BOARD_SIZE; y++)\r
- {\r
- iSum = 0;\r
-\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum += p->sBoard[x][y];\r
- }\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
- }\r
-\r
- iSum = 0;\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum += p->sBoard[x][x];\r
- }\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
-\r
- iSum = 0;\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum += p->sBoard[x][(BOARD_SIZE - 1 - x)];\r
- }\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
-\r
- *psWhoWon = EMPTY;\r
- if (p->uNumEmpty == 0)\r
- {\r
- return(TRUE);\r
- }\r
- else\r
- {\r
- return(FALSE);\r
- }\r
-\r
- winner:\r
- *psWhoWon = (iSum / BOARD_SIZE);\r
- ASSERT(X_OR_O(*psWhoWon));\r
- return(TRUE);\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: MakeMove\r
-//\r
-// Synopsis: Make a move on a board \r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN MOVE *m - the move\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void MakeMove(IN OUT POSITION *p, IN MOVE *m)\r
-{\r
- if (TRUE == IsLegalMove(p, m))\r
- {\r
- ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);\r
- p->sBoard[m->cVpos][m->cHpos] = m->sMark;\r
- p->uNumEmpty--;\r
- ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));\r
- p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
- g_uPly++;\r
- ASSERT(g_uPly > 0);\r
- }\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: UnmakeMove\r
-//\r
-// Synopsis: The opposite of MakeMove\r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN MOVE *m - the move to undo\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)\r
-{\r
- if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)\r
- {\r
- p->sBoard[m->cVpos][m->cHpos] = EMPTY;\r
- p->uNumEmpty++;\r
- ASSERT(p->uNumEmpty > 0);\r
- ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));\r
- p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
- ASSERT(g_uPly > 0);\r
- g_uPly--;\r
- }\r
-}\r
-\r
-\r
-int\r
-SimpleSearch(IN POSITION *p)\r
-{\r
- SQUARE sWhoWon;\r
- SQUARE s;\r
- MOVE mv;\r
- int iScore;\r
- int iBestScore = -INFINITY;\r
-\r
- //\r
- // Evaluate this position\r
- //\r
- if (TRUE == GameOver(p, &sWhoWon))\r
- {\r
- if (sWhoWon == p->sWhoseTurn)\r
- {\r
- return(+INFINITY);\r
- }\r
- else if (sWhoWon == (p->sWhoseTurn * -1))\r
- {\r
- return(-INFINITY);\r
- }\r
- return(DRAWSCORE);\r
- }\r
-\r
- //\r
- // No one won, game is still going. Evaluate every\r
- // possible move from here.\r
- //\r
- ASSERT(p->uNumEmpty > 0);\r
- for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)\r
- {\r
- mv.cHpos = NUM_TO_HPOS(s);\r
- mv.cVpos = NUM_TO_VPOS(s);\r
- mv.sMark = p->sWhoseTurn;\r
-\r
- if (IsLegalMove(p, &mv))\r
- {\r
- MakeMove(p, &mv);\r
-\r
- iScore = -1 * SimpleSearch(p);\r
- if (iScore > iBestScore)\r
- {\r
- iBestScore = iScore;\r
- if (g_uPly == 1)\r
- {\r
- g_mvBest = mv;\r
- }\r
- }\r
-\r
- UnmakeMove(p, &mv);\r
- }\r
- }\r
- return(iBestScore);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SearchForComputerMove\r
-//\r
-// Synopsis: Use our sophisticated search algorithm to find a computer\r
-// move\r
-//\r
-// Arguments: IN POSITION *p - the current board\r
-// OUT MOVE *m - the move the computer chooses; this move struct\r
-// is populated as a side-effect of this function.\r
-// \r
-// Returns: void* (populates move struct)\r
-//\r
-//+----------------------------------------------------------------------------\r
-void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)\r
-{\r
- unsigned int x;\r
-\r
-#if defined(PLAY_RANDOMLY)\r
- do\r
- {\r
- x = rand() % (BOARD_SIZE * BOARD_SIZE);\r
- m->cHpos = NUM_TO_HPOS(x);\r
- m->cVpos = NUM_TO_VPOS(x);\r
- m->sMark = g_sComputerPlays;\r
- }\r
- while(FALSE == IsLegalMove(p, m));\r
-#elif defined(SIMPLE_SEARCH)\r
- g_uPly = 0;\r
- SimpleSearch(p);\r
- *m = g_mvBest;\r
-#else\r
- #error "No Search Strategy Defined"\r
-#endif\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: main\r
-//\r
-// Synopsis: The program entry point and main game loop.\r
-//\r
-// Arguments: void\r
-// \r
-// Returns: int\r
-//\r
-//+----------------------------------------------------------------------------\r
-int main(void)\r
-{\r
- POSITION p;\r
- MOVE mv;\r
- SQUARE sResult;\r
-\r
- //\r
- // Randomize: the random numbers returned by rand() will be based on\r
- // the system clock when the program starts up.\r
- //\r
- srand(time(0));\r
-\r
- //\r
- // Setup the board and draw it once.\r
- //\r
- ClearBoard(&p);\r
- DrawBoard(&p);\r
-\r
- //\r
- // Main game loop\r
- //\r
- do\r
- {\r
- // \r
- // See whose turn it is -- the human's or the computers -- and\r
- // get a move from whoever's turn it is.\r
- //\r
- if (p.sWhoseTurn == g_sComputerPlays)\r
- {\r
- SearchForComputerMove(&p, &mv);\r
- }\r
- else\r
- {\r
- GetHumanMove(&p, &mv);\r
- }\r
-\r
- //\r
- // Make the move on the board and draw the board again.\r
- //\r
- MakeMove(&p, &mv);\r
- DrawBoard(&p);\r
- }\r
- while(FALSE == GameOver(&p, &sResult));\r
-\r
- //\r
- // If we get here the game is over... see what happened.\r
- //\r
- switch(sResult)\r
- {\r
- case X_MARK:\r
- printf("\nX's win.\n");\r
- break;\r
- case O_MARK:\r
- printf("\nO's win.\n");\r
- break;\r
- default:\r
- printf("Tie (what a surprise)\n");\r
- break;\r
- }\r
-\r
- exit(0);\r
-}\r
-\r
+#include <stdlib.h>
+#include <stdio.h>
+#include <memory.h>
+#include <time.h>
+#include "ttt.h"
+
+SQUARE g_sComputerPlays = O_MARK; // what side comp plays
+unsigned int g_uPly = 0;
+MOVE g_mvBest = { 0 };
+
+//+----------------------------------------------------------------------------
+//
+// Function: SquareContentsToChar
+//
+// Synopsis: Helper function for DrawBoard
+//
+// Arguments: IN SQUARE s - a square to return a char to represent
+//
+// Returns: char - character representing square
+//
+//+----------------------------------------------------------------------------
+char SquareContentsToChar(IN SQUARE s)
+{
+ static char c;
+ switch(s)
+ {
+ case X_MARK:
+ c = 'X';
+ break;
+ case O_MARK:
+ c = 'O';
+ break;
+ case EMPTY:
+ c = '_';
+ break;
+ default:
+ ASSERT(FALSE);
+ c = '?';
+ break;
+ }
+ return(c);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: DrawBoard
+//
+// Synopsis: Draw the board
+//
+// Arguments: IN POSITION *p - pointer to a position whose board to draw
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void DrawBoard(IN POSITION *p)
+{
+ COORD x, y;
+
+ for (y = 0; y < BOARD_SIZE; y++)
+ {
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
+ }
+ printf("\n");
+ }
+ ASSERT(X_OR_O(p->sWhoseTurn));
+ printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: ClearBoard
+//
+// Synopsis: Clear the board
+//
+// Arguments: IN OUT POSITION *p - pointer to position whose board to clear
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void ClearBoard(IN OUT POSITION *p)
+{
+ memset(p->sBoard, 0, sizeof(p->sBoard));
+ p->sWhoseTurn = X_MARK; // x's go first
+ p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: IsLegalMove
+//
+// Synopsis: Determine if a given move is legal on a given board
+//
+// Arguments: IN POSITION *p - the board to play the move on
+// IN MOVE *m - the move in question
+//
+// Returns: BOOL - TRUE if it's legal, FALSE otherwise
+//
+//+----------------------------------------------------------------------------
+BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)
+{
+ if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))
+ {
+ if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))
+ {
+ return(TRUE);
+ }
+ }
+ return(FALSE);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: GetHumanMove
+//
+// Synopsis: Ask the human for a move
+//
+// Arguments: IN POSITION *p - the current board
+// OUT MOVE *m - the move the human made; this struct is populated
+// as a side-effect of this function.
+//
+// Returns: void* (populates the move struct)
+//
+//+----------------------------------------------------------------------------
+void GetHumanMove(IN POSITION *p, OUT MOVE *m)
+{
+ unsigned int x;
+
+ do
+ {
+ printf("Enter your move number: ");
+ scanf("%u", &x);
+
+ m->cHpos = NUM_TO_HPOS(x);
+ m->cVpos = NUM_TO_VPOS(x);
+ m->sMark = OPPOSITE_MARK(g_sComputerPlays);
+ }
+ while(FALSE == IsLegalMove(p, m));
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: GameOver
+//
+// Synopsis: Is the game over?
+//
+// Arguments: IN POSITION *p - the board
+// OUT SQUARE *psWhoWon - who won the game (if it's over)
+//
+// Returns: TRUE if the game is over. Also sets psWhoWon telling
+// which side one if the game is over. This also serves
+// as a very simple evaluation routine for the search.
+//
+// FALSE if the game is not over.
+//
+//+----------------------------------------------------------------------------
+BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)
+{
+ int iSum;
+ COORD x, y;
+
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum = 0;
+
+ for (y = 0; y < BOARD_SIZE; y++)
+ {
+ iSum += p->sBoard[x][y];
+ }
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+ }
+
+ for (y = 0; y < BOARD_SIZE; y++)
+ {
+ iSum = 0;
+
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum += p->sBoard[x][y];
+ }
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+ }
+
+ iSum = 0;
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum += p->sBoard[x][x];
+ }
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+
+ iSum = 0;
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum += p->sBoard[x][(BOARD_SIZE - 1 - x)];
+ }
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+
+ *psWhoWon = EMPTY;
+ if (p->uNumEmpty == 0)
+ {
+ return(TRUE);
+ }
+ else
+ {
+ return(FALSE);
+ }
+
+ winner:
+ *psWhoWon = (iSum / BOARD_SIZE);
+ ASSERT(X_OR_O(*psWhoWon));
+ return(TRUE);
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: MakeMove
+//
+// Synopsis: Make a move on a board
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN MOVE *m - the move
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void MakeMove(IN OUT POSITION *p, IN MOVE *m)
+{
+ if (TRUE == IsLegalMove(p, m))
+ {
+ ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
+ p->sBoard[m->cVpos][m->cHpos] = m->sMark;
+ p->uNumEmpty--;
+ ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));
+ p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
+ g_uPly++;
+ ASSERT(g_uPly > 0);
+ }
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: UnmakeMove
+//
+// Synopsis: The opposite of MakeMove
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN MOVE *m - the move to undo
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)
+{
+ if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)
+ {
+ p->sBoard[m->cVpos][m->cHpos] = EMPTY;
+ p->uNumEmpty++;
+ ASSERT(p->uNumEmpty > 0);
+ ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));
+ p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
+ ASSERT(g_uPly > 0);
+ g_uPly--;
+ }
+}
+
+
+int
+SimpleSearch(IN POSITION *p)
+{
+ SQUARE sWhoWon;
+ SQUARE s;
+ MOVE mv;
+ int iScore;
+ int iBestScore = -INFINITY;
+
+ //
+ // Evaluate this position
+ //
+ if (TRUE == GameOver(p, &sWhoWon))
+ {
+ if (sWhoWon == p->sWhoseTurn)
+ {
+ return(+INFINITY);
+ }
+ else if (sWhoWon == (p->sWhoseTurn * -1))
+ {
+ return(-INFINITY);
+ }
+ return(DRAWSCORE);
+ }
+
+ //
+ // No one won, game is still going. Evaluate every
+ // possible move from here.
+ //
+ ASSERT(p->uNumEmpty > 0);
+ for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)
+ {
+ mv.cHpos = NUM_TO_HPOS(s);
+ mv.cVpos = NUM_TO_VPOS(s);
+ mv.sMark = p->sWhoseTurn;
+
+ if (IsLegalMove(p, &mv))
+ {
+ MakeMove(p, &mv);
+
+ iScore = -1 * SimpleSearch(p);
+ if (iScore > iBestScore)
+ {
+ iBestScore = iScore;
+ if (g_uPly == 1)
+ {
+ g_mvBest = mv;
+ }
+ }
+
+ UnmakeMove(p, &mv);
+ }
+ }
+ return(iBestScore);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: SearchForComputerMove
+//
+// Synopsis: Use our sophisticated search algorithm to find a computer
+// move
+//
+// Arguments: IN POSITION *p - the current board
+// OUT MOVE *m - the move the computer chooses; this move struct
+// is populated as a side-effect of this function.
+//
+// Returns: void* (populates move struct)
+//
+//+----------------------------------------------------------------------------
+void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)
+{
+ unsigned int x;
+
+#if defined(PLAY_RANDOMLY)
+ do
+ {
+ x = rand() % (BOARD_SIZE * BOARD_SIZE);
+ m->cHpos = NUM_TO_HPOS(x);
+ m->cVpos = NUM_TO_VPOS(x);
+ m->sMark = g_sComputerPlays;
+ }
+ while(FALSE == IsLegalMove(p, m));
+#elif defined(SIMPLE_SEARCH)
+ g_uPly = 0;
+ SimpleSearch(p);
+ *m = g_mvBest;
+#else
+ #error "No Search Strategy Defined"
+#endif
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: main
+//
+// Synopsis: The program entry point and main game loop.
+//
+// Arguments: void
+//
+// Returns: int
+//
+//+----------------------------------------------------------------------------
+int main(void)
+{
+ POSITION p;
+ MOVE mv;
+ SQUARE sResult;
+
+ //
+ // Randomize: the random numbers returned by rand() will be based on
+ // the system clock when the program starts up.
+ //
+ srand(time(0));
+
+ //
+ // Setup the board and draw it once.
+ //
+ ClearBoard(&p);
+ DrawBoard(&p);
+
+ //
+ // Main game loop
+ //
+ do
+ {
+ //
+ // See whose turn it is -- the human's or the computers -- and
+ // get a move from whoever's turn it is.
+ //
+ if (p.sWhoseTurn == g_sComputerPlays)
+ {
+ SearchForComputerMove(&p, &mv);
+ }
+ else
+ {
+ GetHumanMove(&p, &mv);
+ }
+
+ //
+ // Make the move on the board and draw the board again.
+ //
+ MakeMove(&p, &mv);
+ DrawBoard(&p);
+ }
+ while(FALSE == GameOver(&p, &sResult));
+
+ //
+ // If we get here the game is over... see what happened.
+ //
+ switch(sResult)
+ {
+ case X_MARK:
+ printf("\nX's win.\n");
+ break;
+ case O_MARK:
+ printf("\nO's win.\n");
+ break;
+ default:
+ printf("Tie (what a surprise)\n");
+ break;
+ }
+
+ exit(0);
+}
+
-/*++\r
-\r
-Module Name:\r
-\r
- ttt.c\r
-\r
-Abstract:\r
-\r
- tic tac toe program to illustrate simple minimax searching\r
-\r
-Author:\r
-\r
- Scott Gasch (SGasch) 18 Mar 2004\r
-\r
-Revision History:\r
-\r
- ver0 : random play\r
- ver1 : simple search\r
- ver2 : alpha beta search\r
-\r
---*/\r
-\r
-#include <stdlib.h>\r
-#include <stdio.h>\r
-#include <memory.h>\r
-#include <time.h>\r
-#include "ttt.h"\r
-\r
-SQUARE g_sComputerPlays = O_MARK; // what side comp plays\r
-unsigned int g_uPly = 0;\r
-MOVE g_mvBest = { 0 };\r
-unsigned int g_uNodes = 0;\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SquareContentsToChar\r
-//\r
-// Synopsis: Helper function for DrawBoard\r
-//\r
-// Arguments: IN SQUARE s - a square to return a char to represent\r
-// \r
-// Returns: char - character representing square\r
-//\r
-//+----------------------------------------------------------------------------\r
-char SquareContentsToChar(IN SQUARE s)\r
-{\r
- static char c;\r
- switch(s)\r
- {\r
- case X_MARK:\r
- c = 'X';\r
- break;\r
- case O_MARK:\r
- c = 'O';\r
- break;\r
- case EMPTY:\r
- c = '_';\r
- break;\r
- default:\r
- ASSERT(FALSE);\r
- c = '?';\r
- break;\r
- }\r
- return(c);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: DrawBoard\r
-//\r
-// Synopsis: Draw the board\r
-//\r
-// Arguments: IN POSITION *p - pointer to a position whose board to draw\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void DrawBoard(IN POSITION *p)\r
-{\r
- COORD x, y;\r
-\r
- for (y = 0; y < BOARD_SIZE; y++)\r
- {\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- printf("%c ", SquareContentsToChar(p->sBoard[y][x]));\r
- }\r
- printf("\n");\r
- }\r
- ASSERT(X_OR_O(p->sWhoseTurn));\r
- printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: ClearBoard\r
-//\r
-// Synopsis: Clear the board\r
-//\r
-// Arguments: IN OUT POSITION *p - pointer to position whose board to clear\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void ClearBoard(IN OUT POSITION *p)\r
-{\r
- memset(p->sBoard, 0, sizeof(p->sBoard));\r
- p->sWhoseTurn = X_MARK; // x's go first\r
- p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: IsLegalMove\r
-//\r
-// Synopsis: Determine if a given move is legal on a given board\r
-//\r
-// Arguments: IN POSITION *p - the board to play the move on\r
-// IN MOVE *m - the move in question\r
-// \r
-// Returns: BOOL - TRUE if it's legal, FALSE otherwise\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)\r
-{\r
- if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))\r
- {\r
- if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))\r
- {\r
- return(TRUE);\r
- }\r
- }\r
- return(FALSE);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: GetHumanMove\r
-//\r
-// Synopsis: Ask the human for a move\r
-//\r
-// Arguments: IN POSITION *p - the current board\r
-// OUT MOVE *m - the move the human made; this struct is populated\r
-// as a side-effect of this function.\r
-// \r
-// Returns: void* (populates the move struct)\r
-//\r
-//+----------------------------------------------------------------------------\r
-void GetHumanMove(IN POSITION *p, OUT MOVE *m)\r
-{\r
- unsigned int x;\r
-\r
- do\r
- {\r
- printf("Enter your move number: ");\r
- scanf("%u", &x);\r
- \r
- m->cHpos = NUM_TO_HPOS(x);\r
- m->cVpos = NUM_TO_VPOS(x);\r
- m->sMark = OPPOSITE_MARK(g_sComputerPlays);\r
- }\r
- while(FALSE == IsLegalMove(p, m));\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: GameOver\r
-//\r
-// Synopsis: Is the game over? \r
-//\r
-// Arguments: IN POSITION *p - the board\r
-// OUT SQUARE *psWhoWon - who won the game (if it's over)\r
-// \r
-// Returns: TRUE if the game is over. Also sets psWhoWon telling\r
-// which side one if the game is over. This also serves\r
-// as a very simple evaluation routine for the search.\r
-// \r
-// FALSE if the game is not over.\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)\r
-{\r
- int iSum;\r
- COORD x, y;\r
-\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum = 0;\r
-\r
- for (y = 0; y < BOARD_SIZE; y++)\r
- {\r
- iSum += p->sBoard[x][y];\r
- }\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
- }\r
-\r
- for (y = 0; y < BOARD_SIZE; y++)\r
- {\r
- iSum = 0;\r
-\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum += p->sBoard[x][y];\r
- }\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
- }\r
-\r
- iSum = 0;\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum += p->sBoard[x][x];\r
- }\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
-\r
- iSum = 0;\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum += p->sBoard[x][(BOARD_SIZE - 1 - x)];\r
- }\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
-\r
- *psWhoWon = EMPTY;\r
- if (p->uNumEmpty == 0)\r
- {\r
- return(TRUE);\r
- }\r
- else\r
- {\r
- return(FALSE);\r
- }\r
-\r
- winner:\r
- *psWhoWon = (iSum / BOARD_SIZE);\r
- ASSERT(X_OR_O(*psWhoWon));\r
- return(TRUE);\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: MakeMove\r
-//\r
-// Synopsis: Make a move on a board \r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN MOVE *m - the move\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void MakeMove(IN OUT POSITION *p, IN MOVE *m)\r
-{\r
- if (TRUE == IsLegalMove(p, m))\r
- {\r
- ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);\r
- p->sBoard[m->cVpos][m->cHpos] = m->sMark;\r
- p->uNumEmpty--;\r
- ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));\r
- p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
- g_uPly++;\r
- ASSERT(g_uPly > 0);\r
- }\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: UnmakeMove\r
-//\r
-// Synopsis: The opposite of MakeMove\r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN MOVE *m - the move to undo\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)\r
-{\r
- if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)\r
- {\r
- p->sBoard[m->cVpos][m->cHpos] = EMPTY;\r
- p->uNumEmpty++;\r
- ASSERT(p->uNumEmpty > 0);\r
- ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));\r
- p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
- ASSERT(g_uPly > 0);\r
- g_uPly--;\r
- }\r
-}\r
-\r
-\r
-int \r
-AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta)\r
-{\r
- SQUARE sWhoWon;\r
- SQUARE s;\r
- MOVE mv;\r
- int iScore;\r
- int iBestScore = -INFINITY;\r
-\r
- g_uNodes++;\r
-\r
- //\r
- // Evaluate this position\r
- //\r
- if (TRUE == GameOver(p, &sWhoWon))\r
- {\r
- if (sWhoWon == p->sWhoseTurn)\r
- {\r
- return(+INFINITY - g_uPly);\r
- }\r
- else if (sWhoWon == (p->sWhoseTurn * -1))\r
- {\r
- return(-INFINITY + g_uPly);\r
- }\r
- return(DRAWSCORE);\r
- }\r
-\r
- //\r
- // No one won, game is still going. Evaluate every\r
- // possible move from here.\r
- //\r
- ASSERT(p->uNumEmpty > 0);\r
- for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)\r
- {\r
- mv.cHpos = NUM_TO_HPOS(s);\r
- mv.cVpos = NUM_TO_VPOS(s);\r
- mv.sMark = p->sWhoseTurn;\r
-\r
- if (IsLegalMove(p, &mv))\r
- {\r
- MakeMove(p, &mv);\r
-\r
- iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha);\r
-\r
- UnmakeMove(p, &mv);\r
- \r
- if (iScore >= iBeta)\r
- {\r
- return(iScore);\r
- }\r
-\r
- if (iScore > iBestScore)\r
- {\r
- iBestScore = iScore;\r
- \r
- if (iScore > iAlpha)\r
- {\r
- iAlpha = iScore;\r
- if (g_uPly == 0)\r
- {\r
- g_mvBest = mv;\r
- }\r
- }\r
- }\r
- }\r
- }\r
- return(iBestScore);\r
-}\r
-\r
-\r
-int\r
-SimpleSearch(IN POSITION *p)\r
-{\r
- SQUARE sWhoWon;\r
- SQUARE s;\r
- MOVE mv;\r
- int iScore;\r
- int iBestScore = -INFINITY;\r
-\r
- g_uNodes++;\r
-\r
- //\r
- // Evaluate this position\r
- //\r
- if (TRUE == GameOver(p, &sWhoWon))\r
- {\r
- if (sWhoWon == p->sWhoseTurn)\r
- {\r
- return(+INFINITY - g_uPly);\r
- }\r
- else if (sWhoWon == (p->sWhoseTurn * -1))\r
- {\r
- return(-INFINITY + g_uPly);\r
- }\r
- return(DRAWSCORE);\r
- }\r
-\r
- //\r
- // No one won, game is still going. Evaluate every\r
- // possible move from here.\r
- //\r
- ASSERT(p->uNumEmpty > 0);\r
- for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)\r
- {\r
- mv.cHpos = NUM_TO_HPOS(s);\r
- mv.cVpos = NUM_TO_VPOS(s);\r
- mv.sMark = p->sWhoseTurn;\r
-\r
- if (IsLegalMove(p, &mv))\r
- {\r
- MakeMove(p, &mv);\r
-\r
- iScore = -1 * SimpleSearch(p);\r
- if (iScore > iBestScore)\r
- {\r
- iBestScore = iScore;\r
- if (g_uPly == 1)\r
- {\r
- g_mvBest = mv;\r
- }\r
- }\r
-\r
- UnmakeMove(p, &mv);\r
- }\r
- }\r
- return(iBestScore);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SearchForComputerMove\r
-//\r
-// Synopsis: Use our sophisticated search algorithm to find a computer\r
-// move\r
-//\r
-// Arguments: IN POSITION *p - the current board\r
-// OUT MOVE *m - the move the computer chooses; this move struct\r
-// is populated as a side-effect of this function.\r
-// \r
-// Returns: void* (populates move struct)\r
-//\r
-//+----------------------------------------------------------------------------\r
-void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)\r
-{\r
- unsigned int x;\r
-\r
-#if defined(PLAY_RANDOMLY)\r
- do\r
- {\r
- x = rand() % (BOARD_SIZE * BOARD_SIZE);\r
- m->cHpos = NUM_TO_HPOS(x);\r
- m->cVpos = NUM_TO_VPOS(x);\r
- m->sMark = g_sComputerPlays;\r
- }\r
- while(FALSE == IsLegalMove(p, m));\r
-#elif defined(SIMPLE_SEARCH)\r
- g_uPly = g_uNodes = 0;\r
- SimpleSearch(p);\r
- *m = g_mvBest;\r
- printf("Searched %u node(s).\n", g_uNodes);\r
-#elif defined(ALPHA_BETA_SEARCH)\r
- g_uPly = g_uNodes = 0;\r
- AlphaBeta(p, -INFINITY-1, +INFINITY+1);\r
- *m = g_mvBest;\r
- printf("Searched %u node(s).\n", g_uNodes);\r
-#else\r
- #error "No Search Strategy Defined"\r
-#endif\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: main\r
-//\r
-// Synopsis: The program entry point and main game loop.\r
-//\r
-// Arguments: void\r
-// \r
-// Returns: int\r
-//\r
-//+----------------------------------------------------------------------------\r
-int main(void)\r
-{\r
- POSITION p;\r
- MOVE mv;\r
- SQUARE sResult;\r
-\r
- //\r
- // Randomize: the random numbers returned by rand() will be based on\r
- // the system clock when the program starts up.\r
- //\r
- srand(time(0));\r
-\r
- //\r
- // Setup the board and draw it once.\r
- //\r
- ClearBoard(&p);\r
- DrawBoard(&p);\r
-\r
- //\r
- // Main game loop\r
- //\r
- do\r
- {\r
- // \r
- // See whose turn it is -- the human's or the computers -- and\r
- // get a move from whoever's turn it is.\r
- //\r
- if (p.sWhoseTurn == g_sComputerPlays)\r
- {\r
- SearchForComputerMove(&p, &mv);\r
- }\r
- else\r
- {\r
- GetHumanMove(&p, &mv);\r
- }\r
-\r
- //\r
- // Make the move on the board and draw the board again.\r
- //\r
- MakeMove(&p, &mv);\r
- DrawBoard(&p);\r
- }\r
- while(FALSE == GameOver(&p, &sResult));\r
-\r
- //\r
- // If we get here the game is over... see what happened.\r
- //\r
- switch(sResult)\r
- {\r
- case X_MARK:\r
- printf("\nX's win.\n");\r
- break;\r
- case O_MARK:\r
- printf("\nO's win.\n");\r
- break;\r
- default:\r
- printf("Tie (what a surprise)\n");\r
- break;\r
- }\r
-\r
- exit(0);\r
-}\r
-\r
+/*++
+
+Module Name:
+
+ ttt.c
+
+Abstract:
+
+ tic tac toe program to illustrate simple minimax searching
+
+Author:
+
+ Scott Gasch (SGasch) 18 Mar 2004
+
+Revision History:
+
+ ver0 : random play
+ ver1 : simple search
+ ver2 : alpha beta search
+
+--*/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <memory.h>
+#include <time.h>
+#include "ttt.h"
+
+SQUARE g_sComputerPlays = O_MARK; // what side comp plays
+unsigned int g_uPly = 0;
+MOVE g_mvBest = { 0 };
+unsigned int g_uNodes = 0;
+
+//+----------------------------------------------------------------------------
+//
+// Function: SquareContentsToChar
+//
+// Synopsis: Helper function for DrawBoard
+//
+// Arguments: IN SQUARE s - a square to return a char to represent
+//
+// Returns: char - character representing square
+//
+//+----------------------------------------------------------------------------
+char SquareContentsToChar(IN SQUARE s)
+{
+ static char c;
+ switch(s)
+ {
+ case X_MARK:
+ c = 'X';
+ break;
+ case O_MARK:
+ c = 'O';
+ break;
+ case EMPTY:
+ c = '_';
+ break;
+ default:
+ ASSERT(FALSE);
+ c = '?';
+ break;
+ }
+ return(c);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: DrawBoard
+//
+// Synopsis: Draw the board
+//
+// Arguments: IN POSITION *p - pointer to a position whose board to draw
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void DrawBoard(IN POSITION *p)
+{
+ COORD x, y;
+
+ for (y = 0; y < BOARD_SIZE; y++)
+ {
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
+ }
+ printf("\n");
+ }
+ ASSERT(X_OR_O(p->sWhoseTurn));
+ printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: ClearBoard
+//
+// Synopsis: Clear the board
+//
+// Arguments: IN OUT POSITION *p - pointer to position whose board to clear
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void ClearBoard(IN OUT POSITION *p)
+{
+ memset(p->sBoard, 0, sizeof(p->sBoard));
+ p->sWhoseTurn = X_MARK; // x's go first
+ p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: IsLegalMove
+//
+// Synopsis: Determine if a given move is legal on a given board
+//
+// Arguments: IN POSITION *p - the board to play the move on
+// IN MOVE *m - the move in question
+//
+// Returns: BOOL - TRUE if it's legal, FALSE otherwise
+//
+//+----------------------------------------------------------------------------
+BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)
+{
+ if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))
+ {
+ if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))
+ {
+ return(TRUE);
+ }
+ }
+ return(FALSE);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: GetHumanMove
+//
+// Synopsis: Ask the human for a move
+//
+// Arguments: IN POSITION *p - the current board
+// OUT MOVE *m - the move the human made; this struct is populated
+// as a side-effect of this function.
+//
+// Returns: void* (populates the move struct)
+//
+//+----------------------------------------------------------------------------
+void GetHumanMove(IN POSITION *p, OUT MOVE *m)
+{
+ unsigned int x;
+
+ do
+ {
+ printf("Enter your move number: ");
+ scanf("%u", &x);
+
+ m->cHpos = NUM_TO_HPOS(x);
+ m->cVpos = NUM_TO_VPOS(x);
+ m->sMark = OPPOSITE_MARK(g_sComputerPlays);
+ }
+ while(FALSE == IsLegalMove(p, m));
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: GameOver
+//
+// Synopsis: Is the game over?
+//
+// Arguments: IN POSITION *p - the board
+// OUT SQUARE *psWhoWon - who won the game (if it's over)
+//
+// Returns: TRUE if the game is over. Also sets psWhoWon telling
+// which side one if the game is over. This also serves
+// as a very simple evaluation routine for the search.
+//
+// FALSE if the game is not over.
+//
+//+----------------------------------------------------------------------------
+BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)
+{
+ int iSum;
+ COORD x, y;
+
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum = 0;
+
+ for (y = 0; y < BOARD_SIZE; y++)
+ {
+ iSum += p->sBoard[x][y];
+ }
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+ }
+
+ for (y = 0; y < BOARD_SIZE; y++)
+ {
+ iSum = 0;
+
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum += p->sBoard[x][y];
+ }
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+ }
+
+ iSum = 0;
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum += p->sBoard[x][x];
+ }
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+
+ iSum = 0;
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum += p->sBoard[x][(BOARD_SIZE - 1 - x)];
+ }
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+
+ *psWhoWon = EMPTY;
+ if (p->uNumEmpty == 0)
+ {
+ return(TRUE);
+ }
+ else
+ {
+ return(FALSE);
+ }
+
+ winner:
+ *psWhoWon = (iSum / BOARD_SIZE);
+ ASSERT(X_OR_O(*psWhoWon));
+ return(TRUE);
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: MakeMove
+//
+// Synopsis: Make a move on a board
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN MOVE *m - the move
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void MakeMove(IN OUT POSITION *p, IN MOVE *m)
+{
+ if (TRUE == IsLegalMove(p, m))
+ {
+ ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
+ p->sBoard[m->cVpos][m->cHpos] = m->sMark;
+ p->uNumEmpty--;
+ ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));
+ p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
+ g_uPly++;
+ ASSERT(g_uPly > 0);
+ }
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: UnmakeMove
+//
+// Synopsis: The opposite of MakeMove
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN MOVE *m - the move to undo
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)
+{
+ if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)
+ {
+ p->sBoard[m->cVpos][m->cHpos] = EMPTY;
+ p->uNumEmpty++;
+ ASSERT(p->uNumEmpty > 0);
+ ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));
+ p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
+ ASSERT(g_uPly > 0);
+ g_uPly--;
+ }
+}
+
+
+int
+AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta)
+{
+ SQUARE sWhoWon;
+ SQUARE s;
+ MOVE mv;
+ int iScore;
+ int iBestScore = -INFINITY;
+
+ g_uNodes++;
+
+ //
+ // Evaluate this position
+ //
+ if (TRUE == GameOver(p, &sWhoWon))
+ {
+ if (sWhoWon == p->sWhoseTurn)
+ {
+ return(+INFINITY - g_uPly);
+ }
+ else if (sWhoWon == (p->sWhoseTurn * -1))
+ {
+ return(-INFINITY + g_uPly);
+ }
+ return(DRAWSCORE);
+ }
+
+ //
+ // No one won, game is still going. Evaluate every
+ // possible move from here.
+ //
+ ASSERT(p->uNumEmpty > 0);
+ for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)
+ {
+ mv.cHpos = NUM_TO_HPOS(s);
+ mv.cVpos = NUM_TO_VPOS(s);
+ mv.sMark = p->sWhoseTurn;
+
+ if (IsLegalMove(p, &mv))
+ {
+ MakeMove(p, &mv);
+
+ iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha);
+
+ UnmakeMove(p, &mv);
+
+ if (iScore >= iBeta)
+ {
+ return(iScore);
+ }
+
+ if (iScore > iBestScore)
+ {
+ iBestScore = iScore;
+
+ if (iScore > iAlpha)
+ {
+ iAlpha = iScore;
+ if (g_uPly == 0)
+ {
+ g_mvBest = mv;
+ }
+ }
+ }
+ }
+ }
+ return(iBestScore);
+}
+
+
+int
+SimpleSearch(IN POSITION *p)
+{
+ SQUARE sWhoWon;
+ SQUARE s;
+ MOVE mv;
+ int iScore;
+ int iBestScore = -INFINITY;
+
+ g_uNodes++;
+
+ //
+ // Evaluate this position
+ //
+ if (TRUE == GameOver(p, &sWhoWon))
+ {
+ if (sWhoWon == p->sWhoseTurn)
+ {
+ return(+INFINITY - g_uPly);
+ }
+ else if (sWhoWon == (p->sWhoseTurn * -1))
+ {
+ return(-INFINITY + g_uPly);
+ }
+ return(DRAWSCORE);
+ }
+
+ //
+ // No one won, game is still going. Evaluate every
+ // possible move from here.
+ //
+ ASSERT(p->uNumEmpty > 0);
+ for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)
+ {
+ mv.cHpos = NUM_TO_HPOS(s);
+ mv.cVpos = NUM_TO_VPOS(s);
+ mv.sMark = p->sWhoseTurn;
+
+ if (IsLegalMove(p, &mv))
+ {
+ MakeMove(p, &mv);
+
+ iScore = -1 * SimpleSearch(p);
+ if (iScore > iBestScore)
+ {
+ iBestScore = iScore;
+ if (g_uPly == 1)
+ {
+ g_mvBest = mv;
+ }
+ }
+
+ UnmakeMove(p, &mv);
+ }
+ }
+ return(iBestScore);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: SearchForComputerMove
+//
+// Synopsis: Use our sophisticated search algorithm to find a computer
+// move
+//
+// Arguments: IN POSITION *p - the current board
+// OUT MOVE *m - the move the computer chooses; this move struct
+// is populated as a side-effect of this function.
+//
+// Returns: void* (populates move struct)
+//
+//+----------------------------------------------------------------------------
+void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)
+{
+ unsigned int x;
+
+#if defined(PLAY_RANDOMLY)
+ do
+ {
+ x = rand() % (BOARD_SIZE * BOARD_SIZE);
+ m->cHpos = NUM_TO_HPOS(x);
+ m->cVpos = NUM_TO_VPOS(x);
+ m->sMark = g_sComputerPlays;
+ }
+ while(FALSE == IsLegalMove(p, m));
+#elif defined(SIMPLE_SEARCH)
+ g_uPly = g_uNodes = 0;
+ SimpleSearch(p);
+ *m = g_mvBest;
+ printf("Searched %u node(s).\n", g_uNodes);
+#elif defined(ALPHA_BETA_SEARCH)
+ g_uPly = g_uNodes = 0;
+ AlphaBeta(p, -INFINITY-1, +INFINITY+1);
+ *m = g_mvBest;
+ printf("Searched %u node(s).\n", g_uNodes);
+#else
+ #error "No Search Strategy Defined"
+#endif
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: main
+//
+// Synopsis: The program entry point and main game loop.
+//
+// Arguments: void
+//
+// Returns: int
+//
+//+----------------------------------------------------------------------------
+int main(void)
+{
+ POSITION p;
+ MOVE mv;
+ SQUARE sResult;
+
+ //
+ // Randomize: the random numbers returned by rand() will be based on
+ // the system clock when the program starts up.
+ //
+ srand(time(0));
+
+ //
+ // Setup the board and draw it once.
+ //
+ ClearBoard(&p);
+ DrawBoard(&p);
+
+ //
+ // Main game loop
+ //
+ do
+ {
+ //
+ // See whose turn it is -- the human's or the computers -- and
+ // get a move from whoever's turn it is.
+ //
+ if (p.sWhoseTurn == g_sComputerPlays)
+ {
+ SearchForComputerMove(&p, &mv);
+ }
+ else
+ {
+ GetHumanMove(&p, &mv);
+ }
+
+ //
+ // Make the move on the board and draw the board again.
+ //
+ MakeMove(&p, &mv);
+ DrawBoard(&p);
+ }
+ while(FALSE == GameOver(&p, &sResult));
+
+ //
+ // If we get here the game is over... see what happened.
+ //
+ switch(sResult)
+ {
+ case X_MARK:
+ printf("\nX's win.\n");
+ break;
+ case O_MARK:
+ printf("\nO's win.\n");
+ break;
+ default:
+ printf("Tie (what a surprise)\n");
+ break;
+ }
+
+ exit(0);
+}
+
-/*++\r
-\r
-Module Name:\r
-\r
- ttt.c\r
-\r
-Abstract:\r
-\r
- tic tac toe program to illustrate simple minimax searching\r
-\r
-Author:\r
-\r
- Scott Gasch (SGasch) 18 Mar 2004\r
-\r
-Revision History:\r
-\r
- ver0 : random play\r
- ver1 : simple search\r
- ver2 : alpha beta search\r
- ver3 : added eval and depth on ab search, more efficient gaveover\r
-\r
---*/\r
-\r
-#include <stdlib.h>\r
-#include <stdio.h>\r
-#include <memory.h>\r
-#include <time.h>\r
-#include "ttt.h"\r
-\r
-SQUARE g_sComputerPlays = O_MARK; // what side comp plays\r
-unsigned int g_uPly = 0;\r
-MOVE g_mvBest = { 0 };\r
-unsigned int g_uNodes = 0;\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SquareContentsToChar\r
-//\r
-// Synopsis: Helper function for DrawBoard\r
-//\r
-// Arguments: IN SQUARE s - a square to return a char to represent\r
-// \r
-// Returns: char - character representing square\r
-//\r
-//+----------------------------------------------------------------------------\r
-char SquareContentsToChar(IN SQUARE s)\r
-{\r
- static char c;\r
- switch(s)\r
- {\r
- case X_MARK:\r
- c = 'X';\r
- break;\r
- case O_MARK:\r
- c = 'O';\r
- break;\r
- case EMPTY:\r
- c = '_';\r
- break;\r
- default:\r
- ASSERT(FALSE);\r
- c = '?';\r
- break;\r
- }\r
- return(c);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: DrawBoard\r
-//\r
-// Synopsis: Draw the board\r
-//\r
-// Arguments: IN POSITION *p - pointer to a position whose board to draw\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void DrawBoard(IN POSITION *p)\r
-{\r
- COORD x, y;\r
-\r
- for (y = 0; y < BOARD_SIZE; y++)\r
- {\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- printf("%c ", SquareContentsToChar(p->sBoard[y][x]));\r
- }\r
-#ifdef DEBUG\r
- printf(" = %d\n", p->iHSums[y]);\r
-#else\r
- printf("\n");\r
-#endif\r
- }\r
-\r
-#ifdef DEBUG\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- printf("| ");\r
- }\r
- printf("\n");\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- printf("%d ", p->iVSums[x]);\r
- }\r
- printf("\n");\r
-#endif\r
-\r
- ASSERT(X_OR_O(p->sWhoseTurn));\r
- printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: ClearBoard\r
-//\r
-// Synopsis: Clear the board\r
-//\r
-// Arguments: IN OUT POSITION *p - pointer to position whose board to clear\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void ClearBoard(IN OUT POSITION *p)\r
-{\r
- memset(p->sBoard, 0, sizeof(p->sBoard));\r
- memset(p->iHSums, 0, sizeof(p->iHSums));\r
- memset(p->iVSums, 0, sizeof(p->iVSums));\r
- p->iDSums[0] = p->iDSums[1] = 0;\r
- p->sWhoseTurn = X_MARK; // x's go first\r
- p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: IsLegalMove\r
-//\r
-// Synopsis: Determine if a given move is legal on a given board\r
-//\r
-// Arguments: IN POSITION *p - the board to play the move on\r
-// IN MOVE *m - the move in question\r
-// \r
-// Returns: BOOL - TRUE if it's legal, FALSE otherwise\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)\r
-{\r
- if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))\r
- {\r
- if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))\r
- {\r
- return(TRUE);\r
- }\r
- }\r
- return(FALSE);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: GetHumanMove\r
-//\r
-// Synopsis: Ask the human for a move\r
-//\r
-// Arguments: IN POSITION *p - the current board\r
-// OUT MOVE *m - the move the human made; this struct is populated\r
-// as a side-effect of this function.\r
-// \r
-// Returns: void* (populates the move struct)\r
-//\r
-//+----------------------------------------------------------------------------\r
-void GetHumanMove(IN POSITION *p, OUT MOVE *m)\r
-{\r
- unsigned int x;\r
-\r
- do\r
- {\r
- printf("Enter your move number: ");\r
- scanf("%u", &x);\r
- \r
- m->cHpos = NUM_TO_HPOS(x);\r
- m->cVpos = NUM_TO_VPOS(x);\r
- m->sMark = OPPOSITE_MARK(g_sComputerPlays);\r
- }\r
- while(FALSE == IsLegalMove(p, m));\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: GameOver\r
-//\r
-// Synopsis: Is the game over? \r
-//\r
-// Arguments: IN POSITION *p - the board\r
-// OUT SQUARE *psWhoWon - who won the game (if it's over)\r
-// \r
-// Returns: TRUE if the game is over. Also sets psWhoWon telling\r
-// which side one if the game is over. This also serves\r
-// as a very simple evaluation routine for the search.\r
-// \r
-// FALSE if the game is not over.\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)\r
-{\r
- int iSum;\r
- COORD x;\r
-\r
- for (x = 0; x < BOARD_SIZE; x++)\r
- {\r
- iSum = p->iHSums[x];\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
-\r
- iSum = p->iVSums[x];\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
- }\r
-\r
- iSum = p->iDSums[0];\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
-\r
- iSum = p->iDSums[1];\r
- if (abs(iSum) == BOARD_SIZE) goto winner;\r
-\r
- //\r
- // No one won yet, either game ongoing or draw.\r
- //\r
- *psWhoWon = EMPTY;\r
- if (p->uNumEmpty == 0)\r
- {\r
- return(TRUE);\r
- }\r
- else\r
- {\r
- return(FALSE);\r
- }\r
-\r
- winner:\r
- //\r
- // Some side won\r
- //\r
- *psWhoWon = (iSum / BOARD_SIZE);\r
- ASSERT(X_OR_O(*psWhoWon));\r
- return(TRUE);\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: CountAdjacents\r
-//\r
-// Synopsis: Return the number of marks in adjacent squares to square x\r
-// that are of the same type (x or o) as the mark in square x.\r
-// \r
-// FIXME: does not consider diagonals\r
-//\r
-// Arguments: IN POSITION *p - the board\r
-// IN SQUARE x - the square to test\r
-// \r
-// Returns: A count\r
-//\r
-//+----------------------------------------------------------------------------\r
-unsigned int CountAdjacents(IN POSITION *p, IN SQUARE x)\r
-{\r
- COORD v = NUM_TO_VPOS(x);\r
- COORD h = NUM_TO_HPOS(x);\r
- SQUARE sSide = p->sBoard[h][v];\r
- unsigned int uCount = 0;\r
-\r
- //\r
- // If nothing at square x, nothing to count\r
- //\r
- if (sSide == EMPTY) goto end;\r
-\r
- //\r
- // Look above, below, left and right\r
- //\r
- if ((v > 0) && (p->sBoard[h][v-1] == sSide))\r
- {\r
- uCount++;\r
- }\r
-\r
- if ((v < (BOARD_SIZE - 1)) && (p->sBoard[h][v+1] == sSide))\r
- {\r
- uCount++;\r
- }\r
-\r
- if ((h > 0) && (p->sBoard[h-1][v] == sSide))\r
- {\r
- uCount++;\r
- }\r
-\r
- if ((h < (BOARD_SIZE - 1)) && (p->sBoard[h+1][v] == sSide))\r
- {\r
- uCount++;\r
- }\r
-\r
- end:\r
- ASSERT(0 <= uCount);\r
- ASSERT(uCount <= 4);\r
- return(uCount);\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: Eval\r
-//\r
-// Synopsis: Evaluate a position\r
-//\r
-// Arguments: IN POSITION *p - the board\r
-// \r
-// Returns: A score\r
-//\r
-//+----------------------------------------------------------------------------\r
-int Eval(IN POSITION *p)\r
-{\r
- SQUARE sWinner;\r
- COORD x;\r
- SQUARE sMark;\r
- int iScore = 0;\r
-\r
- //\r
- // See if the game is already over.\r
- //\r
- if (TRUE == GameOver(p, &sWinner))\r
- {\r
- if (sWinner == p->sWhoseTurn)\r
- {\r
- iScore = +INFINITY - g_uPly;\r
- goto end;\r
- }\r
- else if (sWinner == OPPOSITE_MARK(p->sWhoseTurn))\r
- {\r
- iScore = -INFINITY + g_uPly;\r
- goto end;\r
- }\r
- iScore = DRAWSCORE;\r
- goto end;\r
- }\r
-\r
- //\r
- // No one won but instead of returning score=0 see if we can\r
- // find some "good characteristics" or "bad characteristics" \r
- // of the position and give bonuses / penalties.\r
- //\r
- for (x = BOARD_SIZE + 1; \r
- x < ((BOARD_SIZE * BOARD_SIZE) - BOARD_SIZE - 1);\r
- x++)\r
- {\r
- sMark = p->sBoard[NUM_TO_HPOS(x)][NUM_TO_VPOS(x)];\r
- if (sMark == p->sWhoseTurn)\r
- {\r
- iScore += CountAdjacents(p, x);\r
- }\r
- else if (sMark == OPPOSITE_MARK(p->sWhoseTurn))\r
- {\r
- iScore -= CountAdjacents(p, x);\r
- }\r
- }\r
-\r
- end:\r
- ASSERT(-INFINITY <= iScore);\r
- ASSERT(iScore <= +INFINITY);\r
- return(iScore);\r
-}\r
-\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: MakeMove\r
-//\r
-// Synopsis: Make a move on a board \r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN MOVE *m - the move\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void MakeMove(IN OUT POSITION *p, IN MOVE *m)\r
-{\r
- if (TRUE == IsLegalMove(p, m))\r
- {\r
- //\r
- // Make the new make on the board\r
- //\r
- ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);\r
- p->sBoard[m->cVpos][m->cHpos] = m->sMark;\r
-\r
- //\r
- // One less empty square\r
- //\r
- p->uNumEmpty--;\r
- ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));\r
-\r
- //\r
- // Update sums as appropriate\r
- //\r
- p->iHSums[m->cHpos] += m->sMark;\r
- ASSERT(VALID_SUM(p->iHSums[m->cHpos]));\r
- p->iVSums[m->cVpos] += m->sMark;\r
- ASSERT(VALID_SUM(p->iVSums[m->cVpos]));\r
- if (m->cHpos == m->cVpos)\r
- {\r
- p->iDSums[0] += m->sMark;\r
- ASSERT(VALID_SUM(p->iDSums[0]));\r
- }\r
- else if (m->cHpos == (BOARD_SIZE - m->cVpos))\r
- {\r
- p->iDSums[1] += m->sMark;\r
- ASSERT(VALID_SUM(p->iDSums[1]));\r
- }\r
-\r
- //\r
- // Other guy's turn\r
- //\r
- p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
- ASSERT(X_OR_O(p->sWhoseTurn));\r
-\r
- //\r
- // One ply deeper\r
- //\r
- g_uPly++;\r
- ASSERT(g_uPly > 0);\r
- }\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: UnmakeMove\r
-//\r
-// Synopsis: The opposite of MakeMove\r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN MOVE *m - the move to undo\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)\r
-{\r
- if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)\r
- {\r
- p->sBoard[m->cVpos][m->cHpos] = EMPTY;\r
-\r
- //\r
- // One more empty square\r
- //\r
- p->uNumEmpty++;\r
- ASSERT(p->uNumEmpty > 0);\r
- ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));\r
-\r
- //\r
- // Update sums as appropriate\r
- //\r
- p->iHSums[m->cHpos] -= m->sMark;\r
- ASSERT(VALID_SUM(p->iHSums[m->cHpos]));\r
- p->iVSums[m->cVpos] -= m->sMark;\r
- ASSERT(VALID_SUM(p->iVSums[m->cVpos]));\r
- if (m->cHpos == m->cVpos)\r
- {\r
- p->iDSums[0] -= m->sMark;\r
- ASSERT(VALID_SUM(p->iDSums[0]));\r
- }\r
- else if (m->cHpos == (BOARD_SIZE - m->cVpos))\r
- {\r
- p->iDSums[1] -= m->sMark;\r
- ASSERT(VALID_SUM(p->iDSums[1]));\r
- }\r
-\r
- //\r
- // Other guy's turn\r
- //\r
- p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
- ASSERT(X_OR_O(p->sWhoseTurn));\r
-\r
- //\r
- // One ply deeper\r
- //\r
- ASSERT(g_uPly > 0);\r
- g_uPly--;\r
- }\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: AlphaBeta\r
-//\r
-// Synopsis: An AlphaBeta Search\r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN int iAlpha - the lower bound of the score window\r
-// IN int iBeta - the upper bound of the score window\r
-// IN int uDepth - search depth horizon\r
-//\r
-// Returns: int\r
-//\r
-//+----------------------------------------------------------------------------\r
-int \r
-AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta, IN unsigned int uDepth)\r
-{\r
- SQUARE sWhoWon;\r
- SQUARE s;\r
- MOVE mv;\r
- int iScore;\r
- int iBestScore = -INFINITY;\r
-\r
- g_uNodes++;\r
-\r
- //\r
- // Evaluate this position\r
- //\r
- if (TRUE == GameOver(p, &sWhoWon))\r
- {\r
- if (sWhoWon == p->sWhoseTurn)\r
- {\r
- return(+INFINITY - g_uPly);\r
- }\r
- else if (sWhoWon == (p->sWhoseTurn * -1))\r
- {\r
- return(-INFINITY + g_uPly);\r
- }\r
- return(DRAWSCORE);\r
- }\r
- else\r
- {\r
- if (uDepth == 0)\r
- {\r
- return(Eval(p));\r
- }\r
- }\r
-\r
- //\r
- // No one won, game is still going. Evaluate every\r
- // possible move from here.\r
- //\r
- ASSERT(p->uNumEmpty > 0);\r
- for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)\r
- {\r
- mv.cHpos = NUM_TO_HPOS(s);\r
- mv.cVpos = NUM_TO_VPOS(s);\r
- mv.sMark = p->sWhoseTurn;\r
-\r
- if (IsLegalMove(p, &mv))\r
- {\r
- MakeMove(p, &mv);\r
-\r
- iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uDepth - 1);\r
- ASSERT(-INFINITY <= iScore);\r
- ASSERT(iScore <= +INFINITY);\r
-\r
- UnmakeMove(p, &mv);\r
- \r
- if (iScore >= iBeta)\r
- {\r
- return(iScore);\r
- }\r
- \r
- if (iScore > iBestScore)\r
- {\r
- iBestScore = iScore;\r
- \r
- if (iScore > iAlpha)\r
- {\r
- iAlpha = iScore;\r
-\r
- //\r
- // If this is the ply 0 move, remember it.\r
- //\r
- if (g_uPly == 0)\r
- {\r
- g_mvBest = mv;\r
- }\r
- }\r
- }\r
- }\r
- }\r
- return(iBestScore);\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SimpleSearch\r
-//\r
-// Synopsis: A Simple Search\r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-//\r
-// Returns: int\r
-//\r
-//+----------------------------------------------------------------------------\r
-int\r
-SimpleSearch(IN POSITION *p)\r
-{\r
- SQUARE sWhoWon;\r
- SQUARE s;\r
- MOVE mv;\r
- int iScore;\r
- int iBestScore = -INFINITY;\r
- \r
- g_uNodes++;\r
-\r
- //\r
- // Evaluate this position\r
- //\r
- if (TRUE == GameOver(p, &sWhoWon))\r
- {\r
- if (sWhoWon == p->sWhoseTurn)\r
- {\r
- return(+INFINITY - g_uPly);\r
- }\r
- else if (sWhoWon == (p->sWhoseTurn * -1))\r
- {\r
- return(-INFINITY + g_uPly);\r
- }\r
- return(DRAWSCORE);\r
- }\r
-\r
- //\r
- // No one won, game is still going. Evaluate every\r
- // possible move from here.\r
- //\r
- ASSERT(p->uNumEmpty > 0);\r
- for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)\r
- {\r
- mv.cHpos = NUM_TO_HPOS(s);\r
- mv.cVpos = NUM_TO_VPOS(s);\r
- mv.sMark = p->sWhoseTurn;\r
-\r
- if (IsLegalMove(p, &mv))\r
- {\r
- MakeMove(p, &mv);\r
-\r
- iScore = -1 * SimpleSearch(p);\r
- if (iScore > iBestScore)\r
- {\r
- iBestScore = iScore;\r
- if (g_uPly == 1)\r
- {\r
- g_mvBest = mv;\r
- }\r
- }\r
- UnmakeMove(p, &mv);\r
- }\r
- }\r
- return(iBestScore);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SearchForComputerMove\r
-//\r
-// Synopsis: Use our sophisticated search algorithm to find a computer\r
-// move\r
-//\r
-// Arguments: IN POSITION *p - the current board\r
-// OUT MOVE *m - the move the computer chooses; this move struct\r
-// is populated as a side-effect of this function.\r
-// \r
-// Returns: void* (populates move struct)\r
-//\r
-//+----------------------------------------------------------------------------\r
-void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)\r
-{\r
- unsigned int x;\r
-\r
-#if defined(PLAY_RANDOMLY)\r
-\r
- do\r
- {\r
- x = rand() % (BOARD_SIZE * BOARD_SIZE);\r
- m->cHpos = NUM_TO_HPOS(x);\r
- m->cVpos = NUM_TO_VPOS(x);\r
- m->sMark = g_sComputerPlays;\r
- }\r
- while(FALSE == IsLegalMove(p, m));\r
-\r
-#elif defined(SIMPLE_SEARCH)\r
-\r
- g_uPly = g_uNodes = 0;\r
- SimpleSearch(p);\r
- *m = g_mvBest;\r
- printf("Searched %u node(s).\n", g_uNodes);\r
-\r
-#elif defined(ALPHA_BETA_SEARCH)\r
-\r
- g_uPly = g_uNodes = 0;\r
- AlphaBeta(p, -INFINITY-1, +INFINITY+1, BOARD_SIZE);\r
- *m = g_mvBest;\r
- printf("Searched %u node(s).\n", g_uNodes);\r
-\r
-#else\r
-\r
- #error "No Search Strategy Defined"\r
-\r
-#endif\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: main\r
-//\r
-// Synopsis: The program entry point and main game loop.\r
-//\r
-// Arguments: void\r
-// \r
-// Returns: int\r
-//\r
-//+----------------------------------------------------------------------------\r
-int main(void)\r
-{\r
- POSITION p;\r
- MOVE mv;\r
- SQUARE sResult;\r
-\r
- //\r
- // Randomize: the random numbers returned by rand() will be based on\r
- // the system clock when the program starts up.\r
- //\r
- srand(time(0));\r
-\r
- //\r
- // Setup the board and draw it once.\r
- //\r
- ClearBoard(&p);\r
- DrawBoard(&p);\r
-\r
- //\r
- // Main game loop\r
- //\r
- do\r
- {\r
- // \r
- // See whose turn it is -- the human's or the computers -- and\r
- // get a move from whoever's turn it is.\r
- //\r
- if (p.sWhoseTurn == g_sComputerPlays)\r
- {\r
- SearchForComputerMove(&p, &mv);\r
- }\r
- else\r
- {\r
- GetHumanMove(&p, &mv);\r
- }\r
-\r
- //\r
- // Make the move on the board and draw the board again.\r
- //\r
- MakeMove(&p, &mv);\r
- DrawBoard(&p);\r
- }\r
- while(FALSE == GameOver(&p, &sResult));\r
-\r
- //\r
- // If we get here the game is over... see what happened.\r
- //\r
- switch(sResult)\r
- {\r
- case X_MARK:\r
- printf("\nX's win.\n");\r
- break;\r
- case O_MARK:\r
- printf("\nO's win.\n");\r
- break;\r
- default:\r
- printf("Tie (what a surprise)\n");\r
- break;\r
- }\r
-\r
- exit(0);\r
-}\r
-\r
+/*++
+
+Module Name:
+
+ ttt.c
+
+Abstract:
+
+ tic tac toe program to illustrate simple minimax searching
+
+Author:
+
+ Scott Gasch (SGasch) 18 Mar 2004
+
+Revision History:
+
+ ver0 : random play
+ ver1 : simple search
+ ver2 : alpha beta search
+ ver3 : added eval and depth on ab search, more efficient gaveover
+
+--*/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <memory.h>
+#include <time.h>
+#include "ttt.h"
+
+SQUARE g_sComputerPlays = O_MARK; // what side comp plays
+unsigned int g_uPly = 0;
+MOVE g_mvBest = { 0 };
+unsigned int g_uNodes = 0;
+
+//+----------------------------------------------------------------------------
+//
+// Function: SquareContentsToChar
+//
+// Synopsis: Helper function for DrawBoard
+//
+// Arguments: IN SQUARE s - a square to return a char to represent
+//
+// Returns: char - character representing square
+//
+//+----------------------------------------------------------------------------
+char SquareContentsToChar(IN SQUARE s)
+{
+ static char c;
+ switch(s)
+ {
+ case X_MARK:
+ c = 'X';
+ break;
+ case O_MARK:
+ c = 'O';
+ break;
+ case EMPTY:
+ c = '_';
+ break;
+ default:
+ ASSERT(FALSE);
+ c = '?';
+ break;
+ }
+ return(c);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: DrawBoard
+//
+// Synopsis: Draw the board
+//
+// Arguments: IN POSITION *p - pointer to a position whose board to draw
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void DrawBoard(IN POSITION *p)
+{
+ COORD x, y;
+
+ for (y = 0; y < BOARD_SIZE; y++)
+ {
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
+ }
+#ifdef DEBUG
+ printf(" = %d\n", p->iHSums[y]);
+#else
+ printf("\n");
+#endif
+ }
+
+#ifdef DEBUG
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ printf("| ");
+ }
+ printf("\n");
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ printf("%d ", p->iVSums[x]);
+ }
+ printf("\n");
+#endif
+
+ ASSERT(X_OR_O(p->sWhoseTurn));
+ printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: ClearBoard
+//
+// Synopsis: Clear the board
+//
+// Arguments: IN OUT POSITION *p - pointer to position whose board to clear
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void ClearBoard(IN OUT POSITION *p)
+{
+ memset(p->sBoard, 0, sizeof(p->sBoard));
+ memset(p->iHSums, 0, sizeof(p->iHSums));
+ memset(p->iVSums, 0, sizeof(p->iVSums));
+ p->iDSums[0] = p->iDSums[1] = 0;
+ p->sWhoseTurn = X_MARK; // x's go first
+ p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: IsLegalMove
+//
+// Synopsis: Determine if a given move is legal on a given board
+//
+// Arguments: IN POSITION *p - the board to play the move on
+// IN MOVE *m - the move in question
+//
+// Returns: BOOL - TRUE if it's legal, FALSE otherwise
+//
+//+----------------------------------------------------------------------------
+BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)
+{
+ if ((m->cVpos < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))
+ {
+ if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))
+ {
+ return(TRUE);
+ }
+ }
+ return(FALSE);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: GetHumanMove
+//
+// Synopsis: Ask the human for a move
+//
+// Arguments: IN POSITION *p - the current board
+// OUT MOVE *m - the move the human made; this struct is populated
+// as a side-effect of this function.
+//
+// Returns: void* (populates the move struct)
+//
+//+----------------------------------------------------------------------------
+void GetHumanMove(IN POSITION *p, OUT MOVE *m)
+{
+ unsigned int x;
+
+ do
+ {
+ printf("Enter your move number: ");
+ scanf("%u", &x);
+
+ m->cHpos = NUM_TO_HPOS(x);
+ m->cVpos = NUM_TO_VPOS(x);
+ m->sMark = OPPOSITE_MARK(g_sComputerPlays);
+ }
+ while(FALSE == IsLegalMove(p, m));
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: GameOver
+//
+// Synopsis: Is the game over?
+//
+// Arguments: IN POSITION *p - the board
+// OUT SQUARE *psWhoWon - who won the game (if it's over)
+//
+// Returns: TRUE if the game is over. Also sets psWhoWon telling
+// which side one if the game is over. This also serves
+// as a very simple evaluation routine for the search.
+//
+// FALSE if the game is not over.
+//
+//+----------------------------------------------------------------------------
+BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)
+{
+ int iSum;
+ COORD x;
+
+ for (x = 0; x < BOARD_SIZE; x++)
+ {
+ iSum = p->iHSums[x];
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+
+ iSum = p->iVSums[x];
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+ }
+
+ iSum = p->iDSums[0];
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+
+ iSum = p->iDSums[1];
+ if (abs(iSum) == BOARD_SIZE) goto winner;
+
+ //
+ // No one won yet, either game ongoing or draw.
+ //
+ *psWhoWon = EMPTY;
+ if (p->uNumEmpty == 0)
+ {
+ return(TRUE);
+ }
+ else
+ {
+ return(FALSE);
+ }
+
+ winner:
+ //
+ // Some side won
+ //
+ *psWhoWon = (iSum / BOARD_SIZE);
+ ASSERT(X_OR_O(*psWhoWon));
+ return(TRUE);
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: CountAdjacents
+//
+// Synopsis: Return the number of marks in adjacent squares to square x
+// that are of the same type (x or o) as the mark in square x.
+//
+// FIXME: does not consider diagonals
+//
+// Arguments: IN POSITION *p - the board
+// IN SQUARE x - the square to test
+//
+// Returns: A count
+//
+//+----------------------------------------------------------------------------
+unsigned int CountAdjacents(IN POSITION *p, IN SQUARE x)
+{
+ COORD v = NUM_TO_VPOS(x);
+ COORD h = NUM_TO_HPOS(x);
+ SQUARE sSide = p->sBoard[h][v];
+ unsigned int uCount = 0;
+
+ //
+ // If nothing at square x, nothing to count
+ //
+ if (sSide == EMPTY) goto end;
+
+ //
+ // Look above, below, left and right
+ //
+ if ((v > 0) && (p->sBoard[h][v-1] == sSide))
+ {
+ uCount++;
+ }
+
+ if ((v < (BOARD_SIZE - 1)) && (p->sBoard[h][v+1] == sSide))
+ {
+ uCount++;
+ }
+
+ if ((h > 0) && (p->sBoard[h-1][v] == sSide))
+ {
+ uCount++;
+ }
+
+ if ((h < (BOARD_SIZE - 1)) && (p->sBoard[h+1][v] == sSide))
+ {
+ uCount++;
+ }
+
+ end:
+ ASSERT(0 <= uCount);
+ ASSERT(uCount <= 4);
+ return(uCount);
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: Eval
+//
+// Synopsis: Evaluate a position
+//
+// Arguments: IN POSITION *p - the board
+//
+// Returns: A score
+//
+//+----------------------------------------------------------------------------
+int Eval(IN POSITION *p)
+{
+ SQUARE sWinner;
+ COORD x;
+ SQUARE sMark;
+ int iScore = 0;
+
+ //
+ // See if the game is already over.
+ //
+ if (TRUE == GameOver(p, &sWinner))
+ {
+ if (sWinner == p->sWhoseTurn)
+ {
+ iScore = +INFINITY - g_uPly;
+ goto end;
+ }
+ else if (sWinner == OPPOSITE_MARK(p->sWhoseTurn))
+ {
+ iScore = -INFINITY + g_uPly;
+ goto end;
+ }
+ iScore = DRAWSCORE;
+ goto end;
+ }
+
+ //
+ // No one won but instead of returning score=0 see if we can
+ // find some "good characteristics" or "bad characteristics"
+ // of the position and give bonuses / penalties.
+ //
+ for (x = BOARD_SIZE + 1;
+ x < ((BOARD_SIZE * BOARD_SIZE) - BOARD_SIZE - 1);
+ x++)
+ {
+ sMark = p->sBoard[NUM_TO_HPOS(x)][NUM_TO_VPOS(x)];
+ if (sMark == p->sWhoseTurn)
+ {
+ iScore += CountAdjacents(p, x);
+ }
+ else if (sMark == OPPOSITE_MARK(p->sWhoseTurn))
+ {
+ iScore -= CountAdjacents(p, x);
+ }
+ }
+
+ end:
+ ASSERT(-INFINITY <= iScore);
+ ASSERT(iScore <= +INFINITY);
+ return(iScore);
+}
+
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: MakeMove
+//
+// Synopsis: Make a move on a board
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN MOVE *m - the move
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void MakeMove(IN OUT POSITION *p, IN MOVE *m)
+{
+ if (TRUE == IsLegalMove(p, m))
+ {
+ //
+ // Make the new make on the board
+ //
+ ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
+ p->sBoard[m->cVpos][m->cHpos] = m->sMark;
+
+ //
+ // One less empty square
+ //
+ p->uNumEmpty--;
+ ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));
+
+ //
+ // Update sums as appropriate
+ //
+ p->iHSums[m->cHpos] += m->sMark;
+ ASSERT(VALID_SUM(p->iHSums[m->cHpos]));
+ p->iVSums[m->cVpos] += m->sMark;
+ ASSERT(VALID_SUM(p->iVSums[m->cVpos]));
+ if (m->cHpos == m->cVpos)
+ {
+ p->iDSums[0] += m->sMark;
+ ASSERT(VALID_SUM(p->iDSums[0]));
+ }
+ else if (m->cHpos == (BOARD_SIZE - m->cVpos))
+ {
+ p->iDSums[1] += m->sMark;
+ ASSERT(VALID_SUM(p->iDSums[1]));
+ }
+
+ //
+ // Other guy's turn
+ //
+ p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
+ ASSERT(X_OR_O(p->sWhoseTurn));
+
+ //
+ // One ply deeper
+ //
+ g_uPly++;
+ ASSERT(g_uPly > 0);
+ }
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: UnmakeMove
+//
+// Synopsis: The opposite of MakeMove
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN MOVE *m - the move to undo
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)
+{
+ if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)
+ {
+ p->sBoard[m->cVpos][m->cHpos] = EMPTY;
+
+ //
+ // One more empty square
+ //
+ p->uNumEmpty++;
+ ASSERT(p->uNumEmpty > 0);
+ ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));
+
+ //
+ // Update sums as appropriate
+ //
+ p->iHSums[m->cHpos] -= m->sMark;
+ ASSERT(VALID_SUM(p->iHSums[m->cHpos]));
+ p->iVSums[m->cVpos] -= m->sMark;
+ ASSERT(VALID_SUM(p->iVSums[m->cVpos]));
+ if (m->cHpos == m->cVpos)
+ {
+ p->iDSums[0] -= m->sMark;
+ ASSERT(VALID_SUM(p->iDSums[0]));
+ }
+ else if (m->cHpos == (BOARD_SIZE - m->cVpos))
+ {
+ p->iDSums[1] -= m->sMark;
+ ASSERT(VALID_SUM(p->iDSums[1]));
+ }
+
+ //
+ // Other guy's turn
+ //
+ p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
+ ASSERT(X_OR_O(p->sWhoseTurn));
+
+ //
+ // One ply deeper
+ //
+ ASSERT(g_uPly > 0);
+ g_uPly--;
+ }
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: AlphaBeta
+//
+// Synopsis: An AlphaBeta Search
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN int iAlpha - the lower bound of the score window
+// IN int iBeta - the upper bound of the score window
+// IN int uDepth - search depth horizon
+//
+// Returns: int
+//
+//+----------------------------------------------------------------------------
+int
+AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta, IN unsigned int uDepth)
+{
+ SQUARE sWhoWon;
+ SQUARE s;
+ MOVE mv;
+ int iScore;
+ int iBestScore = -INFINITY;
+
+ g_uNodes++;
+
+ //
+ // Evaluate this position
+ //
+ if (TRUE == GameOver(p, &sWhoWon))
+ {
+ if (sWhoWon == p->sWhoseTurn)
+ {
+ return(+INFINITY - g_uPly);
+ }
+ else if (sWhoWon == (p->sWhoseTurn * -1))
+ {
+ return(-INFINITY + g_uPly);
+ }
+ return(DRAWSCORE);
+ }
+ else
+ {
+ if (uDepth == 0)
+ {
+ return(Eval(p));
+ }
+ }
+
+ //
+ // No one won, game is still going. Evaluate every
+ // possible move from here.
+ //
+ ASSERT(p->uNumEmpty > 0);
+ for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)
+ {
+ mv.cHpos = NUM_TO_HPOS(s);
+ mv.cVpos = NUM_TO_VPOS(s);
+ mv.sMark = p->sWhoseTurn;
+
+ if (IsLegalMove(p, &mv))
+ {
+ MakeMove(p, &mv);
+
+ iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uDepth - 1);
+ ASSERT(-INFINITY <= iScore);
+ ASSERT(iScore <= +INFINITY);
+
+ UnmakeMove(p, &mv);
+
+ if (iScore >= iBeta)
+ {
+ return(iScore);
+ }
+
+ if (iScore > iBestScore)
+ {
+ iBestScore = iScore;
+
+ if (iScore > iAlpha)
+ {
+ iAlpha = iScore;
+
+ //
+ // If this is the ply 0 move, remember it.
+ //
+ if (g_uPly == 0)
+ {
+ g_mvBest = mv;
+ }
+ }
+ }
+ }
+ }
+ return(iBestScore);
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: SimpleSearch
+//
+// Synopsis: A Simple Search
+//
+// Arguments: IN OUT POSITION *p - the board
+//
+// Returns: int
+//
+//+----------------------------------------------------------------------------
+int
+SimpleSearch(IN POSITION *p)
+{
+ SQUARE sWhoWon;
+ SQUARE s;
+ MOVE mv;
+ int iScore;
+ int iBestScore = -INFINITY;
+
+ g_uNodes++;
+
+ //
+ // Evaluate this position
+ //
+ if (TRUE == GameOver(p, &sWhoWon))
+ {
+ if (sWhoWon == p->sWhoseTurn)
+ {
+ return(+INFINITY - g_uPly);
+ }
+ else if (sWhoWon == (p->sWhoseTurn * -1))
+ {
+ return(-INFINITY + g_uPly);
+ }
+ return(DRAWSCORE);
+ }
+
+ //
+ // No one won, game is still going. Evaluate every
+ // possible move from here.
+ //
+ ASSERT(p->uNumEmpty > 0);
+ for (s = 0; s < (BOARD_SIZE * BOARD_SIZE); s++)
+ {
+ mv.cHpos = NUM_TO_HPOS(s);
+ mv.cVpos = NUM_TO_VPOS(s);
+ mv.sMark = p->sWhoseTurn;
+
+ if (IsLegalMove(p, &mv))
+ {
+ MakeMove(p, &mv);
+
+ iScore = -1 * SimpleSearch(p);
+ if (iScore > iBestScore)
+ {
+ iBestScore = iScore;
+ if (g_uPly == 1)
+ {
+ g_mvBest = mv;
+ }
+ }
+ UnmakeMove(p, &mv);
+ }
+ }
+ return(iBestScore);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: SearchForComputerMove
+//
+// Synopsis: Use our sophisticated search algorithm to find a computer
+// move
+//
+// Arguments: IN POSITION *p - the current board
+// OUT MOVE *m - the move the computer chooses; this move struct
+// is populated as a side-effect of this function.
+//
+// Returns: void* (populates move struct)
+//
+//+----------------------------------------------------------------------------
+void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)
+{
+ unsigned int x;
+
+#if defined(PLAY_RANDOMLY)
+
+ do
+ {
+ x = rand() % (BOARD_SIZE * BOARD_SIZE);
+ m->cHpos = NUM_TO_HPOS(x);
+ m->cVpos = NUM_TO_VPOS(x);
+ m->sMark = g_sComputerPlays;
+ }
+ while(FALSE == IsLegalMove(p, m));
+
+#elif defined(SIMPLE_SEARCH)
+
+ g_uPly = g_uNodes = 0;
+ SimpleSearch(p);
+ *m = g_mvBest;
+ printf("Searched %u node(s).\n", g_uNodes);
+
+#elif defined(ALPHA_BETA_SEARCH)
+
+ g_uPly = g_uNodes = 0;
+ AlphaBeta(p, -INFINITY-1, +INFINITY+1, BOARD_SIZE);
+ *m = g_mvBest;
+ printf("Searched %u node(s).\n", g_uNodes);
+
+#else
+
+ #error "No Search Strategy Defined"
+
+#endif
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: main
+//
+// Synopsis: The program entry point and main game loop.
+//
+// Arguments: void
+//
+// Returns: int
+//
+//+----------------------------------------------------------------------------
+int main(void)
+{
+ POSITION p;
+ MOVE mv;
+ SQUARE sResult;
+
+ //
+ // Randomize: the random numbers returned by rand() will be based on
+ // the system clock when the program starts up.
+ //
+ srand(time(0));
+
+ //
+ // Setup the board and draw it once.
+ //
+ ClearBoard(&p);
+ DrawBoard(&p);
+
+ //
+ // Main game loop
+ //
+ do
+ {
+ //
+ // See whose turn it is -- the human's or the computers -- and
+ // get a move from whoever's turn it is.
+ //
+ if (p.sWhoseTurn == g_sComputerPlays)
+ {
+ SearchForComputerMove(&p, &mv);
+ }
+ else
+ {
+ GetHumanMove(&p, &mv);
+ }
+
+ //
+ // Make the move on the board and draw the board again.
+ //
+ MakeMove(&p, &mv);
+ DrawBoard(&p);
+ }
+ while(FALSE == GameOver(&p, &sResult));
+
+ //
+ // If we get here the game is over... see what happened.
+ //
+ switch(sResult)
+ {
+ case X_MARK:
+ printf("\nX's win.\n");
+ break;
+ case O_MARK:
+ printf("\nO's win.\n");
+ break;
+ default:
+ printf("Tie (what a surprise)\n");
+ break;
+ }
+
+ exit(0);
+}
+
-/*++\r
-\r
-Module Name:\r
-\r
- ttt.c\r
-\r
-Abstract:\r
-\r
- tic tac toe program to illustrate simple minimax searching\r
-\r
-Author:\r
-\r
- Scott Gasch (SGasch) 18 Mar 2004\r
-\r
-Revision History:\r
-\r
- ver0 : random play\r
- ver1 : simple search\r
- ver2 : alpha beta search\r
- ver3 : added eval and depth on ab search, more efficient gaveover\r
- ver4 : variable sized board\r
- ver5 : bugfixes, added singular extension to search\r
-\r
---*/\r
-\r
-#include <stdlib.h>\r
-#include <stdio.h>\r
-#include <memory.h>\r
-#include <time.h>\r
-#include "ttt.h"\r
-\r
-SQUARE g_sComputerPlays = O_MARK; // what side comp plays\r
-unsigned int g_uPly = 0;\r
-MOVE g_mvBest = { 0 };\r
-unsigned int g_uNodes = 0;\r
-unsigned int g_uExtensions = 0;\r
-COORD g_uBoardSize = 3;\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SquareContentsToChar\r
-//\r
-// Synopsis: Helper function for DrawBoard\r
-//\r
-// Arguments: IN SQUARE s - a square to return a char to represent\r
-// \r
-// Returns: char - character representing square\r
-//\r
-//+----------------------------------------------------------------------------\r
-char SquareContentsToChar(IN SQUARE s)\r
-{\r
- static char c;\r
- switch(s)\r
- {\r
- case X_MARK:\r
- c = 'X';\r
- break;\r
- case O_MARK:\r
- c = 'O';\r
- break;\r
- case EMPTY:\r
- c = '_';\r
- break;\r
- default:\r
- ASSERT(FALSE);\r
- c = '?';\r
- break;\r
- }\r
- return(c);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: DrawBoard\r
-//\r
-// Synopsis: Draw the board\r
-//\r
-// Arguments: IN POSITION *p - pointer to a position whose board to draw\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void DrawBoard(IN POSITION *p)\r
-{\r
- COORD x, y;\r
-\r
- for (y = 0; y < g_uBoardSize; y++)\r
- {\r
- for (x = 0; x < g_uBoardSize; x++)\r
- {\r
- printf("%c ", SquareContentsToChar(p->sBoard[y][x]));\r
- }\r
-#ifdef DEBUG\r
- printf(" = %d\n", p->iVSums[y]);\r
-#else\r
- printf("\n");\r
-#endif\r
- }\r
-\r
-#ifdef DEBUG\r
- for (x = 0; x < g_uBoardSize; x++)\r
- {\r
- printf("| ");\r
- }\r
- printf("\n");\r
- for (x = 0; x < g_uBoardSize; x++)\r
- {\r
- printf("%d ", p->iHSums[x]);\r
- }\r
- printf("\t%d %d\n", p->iDSums[0], p->iDSums[1]);\r
- printf("\n");\r
-#endif\r
-\r
- ASSERT(X_OR_O(p->sWhoseTurn));\r
- printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: ClearBoard\r
-//\r
-// Synopsis: Clear the board\r
-//\r
-// Arguments: IN OUT POSITION *p - pointer to position whose board to clear\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void ClearBoard(IN OUT POSITION *p)\r
-{\r
- COORD h;\r
-\r
- for (h = 0; h < g_uBoardSize; h++)\r
- {\r
- memset(p->sBoard[h], 0, sizeof(int) * g_uBoardSize);\r
- }\r
- memset(p->iHSums, 0, sizeof(int) * g_uBoardSize);\r
- memset(p->iVSums, 0, sizeof(int) * g_uBoardSize);\r
- p->iDSums[0] = p->iDSums[1] = 0;\r
- p->sWhoseTurn = X_MARK; // x's go first\r
- p->uNumEmpty = (g_uBoardSize * g_uBoardSize);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: IsLegalMove\r
-//\r
-// Synopsis: Determine if a given move is legal on a given board\r
-//\r
-// Arguments: IN POSITION *p - the board to play the move on\r
-// IN MOVE *m - the move in question\r
-// \r
-// Returns: BOOL - TRUE if it's legal, FALSE otherwise\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)\r
-{\r
- if ((m->cVpos < g_uBoardSize) && (m->cHpos < g_uBoardSize))\r
- {\r
- if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))\r
- {\r
- return(TRUE);\r
- }\r
- }\r
- return(FALSE);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: GetHumanMove\r
-//\r
-// Synopsis: Ask the human for a move\r
-//\r
-// Arguments: IN POSITION *p - the current board\r
-// OUT MOVE *m - the move the human made; this struct is populated\r
-// as a side-effect of this function.\r
-// \r
-// Returns: void* (populates the move struct)\r
-//\r
-//+----------------------------------------------------------------------------\r
-void GetHumanMove(IN POSITION *p, OUT MOVE *m)\r
-{\r
- unsigned int x;\r
-\r
- do\r
- {\r
- printf("Enter your move number: ");\r
- scanf("%u", &x);\r
- \r
- m->cHpos = NUM_TO_HPOS(x);\r
- m->cVpos = NUM_TO_VPOS(x);\r
- m->sMark = OPPOSITE_MARK(g_sComputerPlays);\r
- }\r
- while(FALSE == IsLegalMove(p, m));\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: GameOver\r
-//\r
-// Synopsis: Is the game over? \r
-//\r
-// Arguments: IN POSITION *p - the board\r
-// OUT SQUARE *psWhoWon - who won the game (if it's over)\r
-// \r
-// Returns: TRUE if the game is over. Also sets psWhoWon telling\r
-// which side one if the game is over. This also serves\r
-// as a very simple evaluation routine for the search.\r
-// \r
-// FALSE if the game is not over.\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)\r
-{\r
- int iSum;\r
- COORD x;\r
- unsigned int uFull = (g_uBoardSize * g_uBoardSize) - p->uNumEmpty;\r
-\r
- //\r
- // The game can't be over if less than g_uBoardSize * 2 - 1 marks on it\r
- //\r
- if (uFull < (g_uBoardSize * 2 - 1))\r
- {\r
- *psWhoWon = EMPTY;\r
- return(FALSE);\r
- }\r
-\r
- for (x = 0; x < g_uBoardSize; x++)\r
- {\r
- iSum = p->iHSums[x];\r
- if (abs(iSum) == g_uBoardSize) goto winner;\r
-\r
- iSum = p->iVSums[x];\r
- if (abs(iSum) == g_uBoardSize) goto winner;\r
- }\r
-\r
- iSum = p->iDSums[0];\r
- if (abs(iSum) == g_uBoardSize) goto winner;\r
-\r
- iSum = p->iDSums[1];\r
- if (abs(iSum) == g_uBoardSize) goto winner;\r
-\r
- //\r
- // No one won yet, either game ongoing or draw.\r
- //\r
- *psWhoWon = EMPTY;\r
- if (p->uNumEmpty == 0)\r
- {\r
- return(TRUE);\r
- }\r
- else\r
- {\r
- return(FALSE);\r
- }\r
-\r
- winner:\r
- //\r
- // Some side won\r
- //\r
- *psWhoWon = (iSum / (int)g_uBoardSize);\r
- ASSERT(X_OR_O(*psWhoWon));\r
- return(TRUE);\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: MakeMove\r
-//\r
-// Synopsis: Make a move on a board \r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN MOVE *m - the move\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void MakeMove(IN OUT POSITION *p, IN MOVE *m)\r
-{\r
- if (TRUE == IsLegalMove(p, m))\r
- {\r
- //\r
- // Make the new make on the board\r
- //\r
- ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);\r
- p->sBoard[m->cVpos][m->cHpos] = m->sMark;\r
-\r
- //\r
- // One less empty square\r
- //\r
- p->uNumEmpty--;\r
- ASSERT(p->uNumEmpty < (g_uBoardSize * g_uBoardSize));\r
-\r
- //\r
- // Update sums as appropriate\r
- //\r
- p->iHSums[m->cHpos] += m->sMark;\r
- ASSERT(VALID_SUM(p->iHSums[m->cHpos]));\r
- p->iVSums[m->cVpos] += m->sMark;\r
- ASSERT(VALID_SUM(p->iVSums[m->cVpos]));\r
- if (ON_DIAGONAL_1(m->cHpos, m->cVpos))\r
- {\r
- p->iDSums[0] += m->sMark;\r
- ASSERT(VALID_SUM(p->iDSums[0]));\r
- }\r
- if (ON_DIAGONAL_2(m->cHpos, m->cVpos))\r
- {\r
- p->iDSums[1] += m->sMark;\r
- ASSERT(VALID_SUM(p->iDSums[1]));\r
- }\r
-\r
- //\r
- // Other guy's turn\r
- //\r
- p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
- ASSERT(X_OR_O(p->sWhoseTurn));\r
-\r
- //\r
- // One ply deeper\r
- //\r
- g_uPly++;\r
- ASSERT(g_uPly > 0);\r
- }\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: UnmakeMove\r
-//\r
-// Synopsis: The opposite of MakeMove\r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN MOVE *m - the move to undo\r
-// \r
-// Returns: void\r
-//\r
-//+----------------------------------------------------------------------------\r
-void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)\r
-{\r
- if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)\r
- {\r
- p->sBoard[m->cVpos][m->cHpos] = EMPTY;\r
-\r
- //\r
- // One more empty square\r
- //\r
- p->uNumEmpty++;\r
- ASSERT(p->uNumEmpty > 0);\r
- ASSERT(p->uNumEmpty <= (g_uBoardSize * g_uBoardSize));\r
-\r
- //\r
- // Update sums as appropriate\r
- //\r
- p->iHSums[m->cHpos] -= m->sMark;\r
- ASSERT(VALID_SUM(p->iHSums[m->cHpos]));\r
- p->iVSums[m->cVpos] -= m->sMark;\r
- ASSERT(VALID_SUM(p->iVSums[m->cVpos]));\r
- if (ON_DIAGONAL_1(m->cHpos, m->cVpos))\r
- {\r
- p->iDSums[0] -= m->sMark;\r
- ASSERT(VALID_SUM(p->iDSums[0]));\r
- }\r
- if (ON_DIAGONAL_2(m->cHpos, m->cVpos))\r
- {\r
- p->iDSums[1] -= m->sMark;\r
- ASSERT(VALID_SUM(p->iDSums[1]));\r
- }\r
-\r
- //\r
- // Other guy's turn\r
- //\r
- p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);\r
- ASSERT(X_OR_O(p->sWhoseTurn));\r
-\r
- //\r
- // One ply deeper\r
- //\r
- ASSERT(g_uPly > 0);\r
- g_uPly--;\r
- }\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: IsMoveSingular\r
-//\r
-// Synopsis: Determine if a move is singular (i.e. only good move) or not\r
-//\r
-// Arguments: IN POSITION *p - the board\r
-// IN MOVE *m - the move to undo\r
-// \r
-// Returns: BOOL : TRUE if *m is singular\r
-//\r
-//+----------------------------------------------------------------------------\r
-BOOL\r
-IsMoveSingular(IN POSITION *p, IN MOVE *m)\r
-{\r
- if ((abs(p->iVSums[m->cVpos]) >= (g_uBoardSize - 2)) ||\r
- (abs(p->iHSums[m->cHpos]) >= (g_uBoardSize - 2)))\r
- {\r
- return(TRUE);\r
- }\r
- if ((m->cHpos == m->cVpos) &&\r
- (abs(p->iDSums[0]) == (g_uBoardSize - 1)))\r
- {\r
- return(TRUE);\r
- }\r
- if ((m->cVpos == ((g_uBoardSize - m->cHpos) - 1)) &&\r
- (abs(p->iDSums[1] == (g_uBoardSize - 1))))\r
- {\r
- return(TRUE);\r
- }\r
- return(FALSE);\r
-}\r
-\r
-\r
-BOOL\r
-IsMoveWorthSearching(POSITION *p, MOVE *m)\r
-{\r
- signed int h;\r
- signed int v;\r
- unsigned int uSum = 0;\r
-\r
- for (h = m->cHpos - 1;\r
- h < (signed int)m->cHpos + 2;\r
- h++)\r
- {\r
- for (v = m->cVpos - 1;\r
- v < (signed int)m->cVpos + 2;\r
- v++)\r
- {\r
- if (GOOD_COORD((COORD)v) && GOOD_COORD((COORD)h))\r
- {\r
- uSum += abs(p->sBoard[v][h]);\r
- }\r
- }\r
- }\r
- \r
- if (uSum == 0)\r
- {\r
- return(FALSE);\r
- }\r
- return(TRUE);\r
-}\r
-\r
-\r
-int \r
-Eval(POSITION *p)\r
-{\r
- int iSum = p->iDSums[0];\r
- COORD x;\r
- \r
- for (x = 0;\r
- x < g_uBoardSize;\r
- x++)\r
- {\r
- iSum += p->iHSums[x];\r
- iSum += p->iVSums[x];\r
- }\r
- iSum += p->iDSums[1];\r
- \r
- return(iSum * p->sWhoseTurn);\r
-}\r
-\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: AlphaBeta\r
-//\r
-// Synopsis: An AlphaBeta Search\r
-//\r
-// Arguments: IN OUT POSITION *p - the board\r
-// IN int iAlpha - the lower bound of the score window\r
-// IN int iBeta - the upper bound of the score window\r
-// IN int uDepth - search depth horizon\r
-//\r
-// Returns: int\r
-//\r
-//+----------------------------------------------------------------------------\r
-int \r
-AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta, IN unsigned int uDepth)\r
-{\r
- SQUARE sWhoWon;\r
- COORD s;\r
- MOVE mv;\r
- int iScore;\r
- int iBestScore = -INFINITY - 2;\r
- BOOL fMoveIsSingular;\r
- unsigned int uNextDepth;\r
- unsigned int uMoveNum = 1;\r
- \r
- g_uNodes++;\r
-\r
- //\r
- // Evaluate this position\r
- //\r
- if (TRUE == GameOver(p, &sWhoWon))\r
- {\r
- if (sWhoWon == p->sWhoseTurn)\r
- {\r
- return(+INFINITY - g_uPly);\r
- }\r
- else if (sWhoWon == (p->sWhoseTurn * -1))\r
- {\r
- return(-INFINITY + g_uPly);\r
- }\r
- return(DRAWSCORE);\r
- }\r
- else if (uDepth == 0)\r
- {\r
- return(Eval(p));\r
- }\r
-\r
- //\r
- // No one won, game is still going. Evaluate some moves from here.\r
- //\r
- ASSERT(p->uNumEmpty > 0);\r
- for (s = 0; s < (g_uBoardSize * g_uBoardSize); s++)\r
- {\r
- mv.cHpos = NUM_TO_HPOS(s);\r
- mv.cVpos = NUM_TO_VPOS(s);\r
- mv.sMark = p->sWhoseTurn;\r
-\r
- if (IsLegalMove(p, &mv))\r
- {\r
- //\r
- // Determine if move is singular\r
- // \r
- fMoveIsSingular = IsMoveSingular(p, &mv);\r
- \r
- if ((FALSE == fMoveIsSingular) &&\r
- (uMoveNum > 1))\r
- {\r
- //\r
- // Determine if we should bother with this subtree...\r
- // \r
- if (FALSE == IsMoveWorthSearching(p, &mv))\r
- {\r
- continue;\r
- }\r
- }\r
- \r
- //\r
- // Do it\r
- // \r
- MakeMove(p, &mv);\r
- uMoveNum++;\r
-\r
- uNextDepth = uDepth - 1;\r
- if (TRUE == fMoveIsSingular)\r
- {\r
- uNextDepth = uDepth;\r
- g_uExtensions++;\r
- }\r
- iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uNextDepth);\r
- ASSERT(-INFINITY <= iScore);\r
- ASSERT(iScore <= +INFINITY);\r
-\r
- UnmakeMove(p, &mv);\r
- \r
- //\r
- // Fail high\r
- //\r
- if (iScore >= iBeta)\r
- {\r
- return(iScore);\r
- }\r
- \r
- if (iScore > iBestScore)\r
- {\r
- iBestScore = iScore;\r
- \r
- if (iScore > iAlpha)\r
- {\r
- //\r
- // PV node\r
- //\r
- iAlpha = iScore;\r
- \r
- //\r
- // If this is the ply 0 move, remember it.\r
- //\r
- if (g_uPly == 0)\r
- {\r
- g_mvBest = mv;\r
- }\r
- }\r
- }\r
- }\r
- }\r
- return(iBestScore);\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: SearchForComputerMove\r
-//\r
-// Synopsis: Use our sophisticated search algorithm to find a computer\r
-// move\r
-//\r
-// Arguments: IN POSITION *p - the current board\r
-// OUT MOVE *m - the move the computer chooses; this move struct\r
-// is populated as a side-effect of this function.\r
-// \r
-// Returns: void* (populates move struct)\r
-//\r
-//+----------------------------------------------------------------------------\r
-void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)\r
-{\r
-#if defined(PLAY_RANDOMLY)\r
- unsigned int x;\r
-\r
- do\r
- {\r
- x = rand() % (g_uBoardSize * g_uBoardSize);\r
- m->cHpos = NUM_TO_HPOS(x);\r
- m->cVpos = NUM_TO_VPOS(x);\r
- m->sMark = g_sComputerPlays;\r
- }\r
- while(FALSE == IsLegalMove(p, m));\r
-\r
-#elif defined(ALPHA_BETA_SEARCH)\r
- double dTime;\r
- \r
- g_uPly = g_uNodes = g_uExtensions = 0;\r
- \r
- AlphaBeta(p, -INFINITY-1, +INFINITY+1, 3);\r
- *m = g_mvBest;\r
- printf("Searched %u node(s), %u extension(s)\n", \r
- g_uNodes, \r
- g_uExtensions);\r
-#else\r
-\r
- #error "No Search Strategy Defined"\r
-\r
-#endif\r
-}\r
-\r
-//+----------------------------------------------------------------------------\r
-//\r
-// Function: main\r
-//\r
-// Synopsis: The program entry point and main game loop.\r
-//\r
-// Arguments: void\r
-// \r
-// Returns: int\r
-//\r
-//+----------------------------------------------------------------------------\r
-int\r
-main(void)\r
-{\r
- POSITION p;\r
- MOVE mv;\r
- SQUARE sResult;\r
- unsigned int u;\r
-\r
- //\r
- // Randomize: the random numbers returned by rand() will be based on\r
- // the system clock when the program starts up.\r
- //\r
- srand(time(0));\r
-\r
- //\r
- // Make the board\r
- //\r
- do\r
- {\r
- printf("How big do you want the board (2..20)? ");\r
- scanf("%u", &g_uBoardSize);\r
- }\r
- while((g_uBoardSize < 2) || (g_uBoardSize > 20));\r
-\r
- //\r
- // Allocate space for 2d int array ptr\r
- //\r
- p.sBoard = (SQUARE **)malloc(g_uBoardSize * sizeof(SQUARE *));\r
- if (NULL == p.sBoard)\r
- {\r
- fprintf(stderr, "Out of memory\n");\r
- exit(1);\r
- }\r
-\r
- //\r
- // Allocate each row of the array\r
- //\r
- for (u = 0; u < g_uBoardSize; u++)\r
- {\r
- p.sBoard[u] = (SQUARE *)\r
- malloc(g_uBoardSize * sizeof(SQUARE));\r
- if (NULL == p.sBoard[u])\r
- {\r
- fprintf(stderr, "Out of memory!\n");\r
- exit(1);\r
- }\r
- }\r
-\r
- //\r
- // Allocate space for sums\r
- //\r
- p.iHSums = (int *)malloc(g_uBoardSize * sizeof(int));\r
- p.iVSums = (int *)malloc(g_uBoardSize * sizeof(int));\r
- if ((NULL == p.iHSums) ||\r
- (NULL == p.iVSums))\r
- {\r
- fprintf(stderr, "Out of memory!\n");\r
- exit(1);\r
- }\r
-\r
- //\r
- // Setup the board and draw it once.\r
- //\r
- ClearBoard(&p);\r
- DrawBoard(&p);\r
-\r
- //\r
- // Main game loop\r
- //\r
- do\r
- {\r
- // \r
- // See whose turn it is -- the human's or the computers -- and\r
- // get a move from whoever's turn it is.\r
- //\r
- if (p.sWhoseTurn == g_sComputerPlays)\r
- {\r
- SearchForComputerMove(&p, &mv);\r
- }\r
- else\r
- {\r
- //SearchForComputerMove(&p, &mv);\r
- GetHumanMove(&p, &mv);\r
- }\r
-\r
- //\r
- // Make the move on the board and draw the board again.\r
- //\r
- MakeMove(&p, &mv);\r
- DrawBoard(&p);\r
- }\r
- while(FALSE == GameOver(&p, &sResult));\r
-\r
- //\r
- // If we get here the game is over... see what happened.\r
- //\r
- switch(sResult)\r
- {\r
- case X_MARK:\r
- printf("\nX's win.\n");\r
- break;\r
- case O_MARK:\r
- printf("\nO's win.\n");\r
- break;\r
- default:\r
- printf("Tie (what a surprise)\n");\r
- break;\r
- }\r
-\r
- //\r
- // TODO: cleanup heap\r
- //\r
- \r
- exit(0);\r
-}\r
+/*++
+
+Module Name:
+
+ ttt.c
+
+Abstract:
+
+ tic tac toe program to illustrate simple minimax searching
+
+Author:
+
+ Scott Gasch (SGasch) 18 Mar 2004
+
+Revision History:
+
+ ver0 : random play
+ ver1 : simple search
+ ver2 : alpha beta search
+ ver3 : added eval and depth on ab search, more efficient gaveover
+ ver4 : variable sized board
+ ver5 : bugfixes, added singular extension to search
+
+--*/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <memory.h>
+#include <time.h>
+#include "ttt.h"
+
+SQUARE g_sComputerPlays = O_MARK; // what side comp plays
+unsigned int g_uPly = 0;
+MOVE g_mvBest = { 0 };
+unsigned int g_uNodes = 0;
+unsigned int g_uExtensions = 0;
+COORD g_uBoardSize = 3;
+
+//+----------------------------------------------------------------------------
+//
+// Function: SquareContentsToChar
+//
+// Synopsis: Helper function for DrawBoard
+//
+// Arguments: IN SQUARE s - a square to return a char to represent
+//
+// Returns: char - character representing square
+//
+//+----------------------------------------------------------------------------
+char SquareContentsToChar(IN SQUARE s)
+{
+ static char c;
+ switch(s)
+ {
+ case X_MARK:
+ c = 'X';
+ break;
+ case O_MARK:
+ c = 'O';
+ break;
+ case EMPTY:
+ c = '_';
+ break;
+ default:
+ ASSERT(FALSE);
+ c = '?';
+ break;
+ }
+ return(c);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: DrawBoard
+//
+// Synopsis: Draw the board
+//
+// Arguments: IN POSITION *p - pointer to a position whose board to draw
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void DrawBoard(IN POSITION *p)
+{
+ COORD x, y;
+
+ for (y = 0; y < g_uBoardSize; y++)
+ {
+ for (x = 0; x < g_uBoardSize; x++)
+ {
+ printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
+ }
+#ifdef DEBUG
+ printf(" = %d\n", p->iVSums[y]);
+#else
+ printf("\n");
+#endif
+ }
+
+#ifdef DEBUG
+ for (x = 0; x < g_uBoardSize; x++)
+ {
+ printf("| ");
+ }
+ printf("\n");
+ for (x = 0; x < g_uBoardSize; x++)
+ {
+ printf("%d ", p->iHSums[x]);
+ }
+ printf("\t%d %d\n", p->iDSums[0], p->iDSums[1]);
+ printf("\n");
+#endif
+
+ ASSERT(X_OR_O(p->sWhoseTurn));
+ printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: ClearBoard
+//
+// Synopsis: Clear the board
+//
+// Arguments: IN OUT POSITION *p - pointer to position whose board to clear
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void ClearBoard(IN OUT POSITION *p)
+{
+ COORD h;
+
+ for (h = 0; h < g_uBoardSize; h++)
+ {
+ memset(p->sBoard[h], 0, sizeof(int) * g_uBoardSize);
+ }
+ memset(p->iHSums, 0, sizeof(int) * g_uBoardSize);
+ memset(p->iVSums, 0, sizeof(int) * g_uBoardSize);
+ p->iDSums[0] = p->iDSums[1] = 0;
+ p->sWhoseTurn = X_MARK; // x's go first
+ p->uNumEmpty = (g_uBoardSize * g_uBoardSize);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: IsLegalMove
+//
+// Synopsis: Determine if a given move is legal on a given board
+//
+// Arguments: IN POSITION *p - the board to play the move on
+// IN MOVE *m - the move in question
+//
+// Returns: BOOL - TRUE if it's legal, FALSE otherwise
+//
+//+----------------------------------------------------------------------------
+BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)
+{
+ if ((m->cVpos < g_uBoardSize) && (m->cHpos < g_uBoardSize))
+ {
+ if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))
+ {
+ return(TRUE);
+ }
+ }
+ return(FALSE);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: GetHumanMove
+//
+// Synopsis: Ask the human for a move
+//
+// Arguments: IN POSITION *p - the current board
+// OUT MOVE *m - the move the human made; this struct is populated
+// as a side-effect of this function.
+//
+// Returns: void* (populates the move struct)
+//
+//+----------------------------------------------------------------------------
+void GetHumanMove(IN POSITION *p, OUT MOVE *m)
+{
+ unsigned int x;
+
+ do
+ {
+ printf("Enter your move number: ");
+ scanf("%u", &x);
+
+ m->cHpos = NUM_TO_HPOS(x);
+ m->cVpos = NUM_TO_VPOS(x);
+ m->sMark = OPPOSITE_MARK(g_sComputerPlays);
+ }
+ while(FALSE == IsLegalMove(p, m));
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: GameOver
+//
+// Synopsis: Is the game over?
+//
+// Arguments: IN POSITION *p - the board
+// OUT SQUARE *psWhoWon - who won the game (if it's over)
+//
+// Returns: TRUE if the game is over. Also sets psWhoWon telling
+// which side one if the game is over. This also serves
+// as a very simple evaluation routine for the search.
+//
+// FALSE if the game is not over.
+//
+//+----------------------------------------------------------------------------
+BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)
+{
+ int iSum;
+ COORD x;
+ unsigned int uFull = (g_uBoardSize * g_uBoardSize) - p->uNumEmpty;
+
+ //
+ // The game can't be over if less than g_uBoardSize * 2 - 1 marks on it
+ //
+ if (uFull < (g_uBoardSize * 2 - 1))
+ {
+ *psWhoWon = EMPTY;
+ return(FALSE);
+ }
+
+ for (x = 0; x < g_uBoardSize; x++)
+ {
+ iSum = p->iHSums[x];
+ if (abs(iSum) == g_uBoardSize) goto winner;
+
+ iSum = p->iVSums[x];
+ if (abs(iSum) == g_uBoardSize) goto winner;
+ }
+
+ iSum = p->iDSums[0];
+ if (abs(iSum) == g_uBoardSize) goto winner;
+
+ iSum = p->iDSums[1];
+ if (abs(iSum) == g_uBoardSize) goto winner;
+
+ //
+ // No one won yet, either game ongoing or draw.
+ //
+ *psWhoWon = EMPTY;
+ if (p->uNumEmpty == 0)
+ {
+ return(TRUE);
+ }
+ else
+ {
+ return(FALSE);
+ }
+
+ winner:
+ //
+ // Some side won
+ //
+ *psWhoWon = (iSum / (int)g_uBoardSize);
+ ASSERT(X_OR_O(*psWhoWon));
+ return(TRUE);
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: MakeMove
+//
+// Synopsis: Make a move on a board
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN MOVE *m - the move
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void MakeMove(IN OUT POSITION *p, IN MOVE *m)
+{
+ if (TRUE == IsLegalMove(p, m))
+ {
+ //
+ // Make the new make on the board
+ //
+ ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
+ p->sBoard[m->cVpos][m->cHpos] = m->sMark;
+
+ //
+ // One less empty square
+ //
+ p->uNumEmpty--;
+ ASSERT(p->uNumEmpty < (g_uBoardSize * g_uBoardSize));
+
+ //
+ // Update sums as appropriate
+ //
+ p->iHSums[m->cHpos] += m->sMark;
+ ASSERT(VALID_SUM(p->iHSums[m->cHpos]));
+ p->iVSums[m->cVpos] += m->sMark;
+ ASSERT(VALID_SUM(p->iVSums[m->cVpos]));
+ if (ON_DIAGONAL_1(m->cHpos, m->cVpos))
+ {
+ p->iDSums[0] += m->sMark;
+ ASSERT(VALID_SUM(p->iDSums[0]));
+ }
+ if (ON_DIAGONAL_2(m->cHpos, m->cVpos))
+ {
+ p->iDSums[1] += m->sMark;
+ ASSERT(VALID_SUM(p->iDSums[1]));
+ }
+
+ //
+ // Other guy's turn
+ //
+ p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
+ ASSERT(X_OR_O(p->sWhoseTurn));
+
+ //
+ // One ply deeper
+ //
+ g_uPly++;
+ ASSERT(g_uPly > 0);
+ }
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: UnmakeMove
+//
+// Synopsis: The opposite of MakeMove
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN MOVE *m - the move to undo
+//
+// Returns: void
+//
+//+----------------------------------------------------------------------------
+void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)
+{
+ if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)
+ {
+ p->sBoard[m->cVpos][m->cHpos] = EMPTY;
+
+ //
+ // One more empty square
+ //
+ p->uNumEmpty++;
+ ASSERT(p->uNumEmpty > 0);
+ ASSERT(p->uNumEmpty <= (g_uBoardSize * g_uBoardSize));
+
+ //
+ // Update sums as appropriate
+ //
+ p->iHSums[m->cHpos] -= m->sMark;
+ ASSERT(VALID_SUM(p->iHSums[m->cHpos]));
+ p->iVSums[m->cVpos] -= m->sMark;
+ ASSERT(VALID_SUM(p->iVSums[m->cVpos]));
+ if (ON_DIAGONAL_1(m->cHpos, m->cVpos))
+ {
+ p->iDSums[0] -= m->sMark;
+ ASSERT(VALID_SUM(p->iDSums[0]));
+ }
+ if (ON_DIAGONAL_2(m->cHpos, m->cVpos))
+ {
+ p->iDSums[1] -= m->sMark;
+ ASSERT(VALID_SUM(p->iDSums[1]));
+ }
+
+ //
+ // Other guy's turn
+ //
+ p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
+ ASSERT(X_OR_O(p->sWhoseTurn));
+
+ //
+ // One ply deeper
+ //
+ ASSERT(g_uPly > 0);
+ g_uPly--;
+ }
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: IsMoveSingular
+//
+// Synopsis: Determine if a move is singular (i.e. only good move) or not
+//
+// Arguments: IN POSITION *p - the board
+// IN MOVE *m - the move to undo
+//
+// Returns: BOOL : TRUE if *m is singular
+//
+//+----------------------------------------------------------------------------
+BOOL
+IsMoveSingular(IN POSITION *p, IN MOVE *m)
+{
+ if ((abs(p->iVSums[m->cVpos]) >= (g_uBoardSize - 2)) ||
+ (abs(p->iHSums[m->cHpos]) >= (g_uBoardSize - 2)))
+ {
+ return(TRUE);
+ }
+ if ((m->cHpos == m->cVpos) &&
+ (abs(p->iDSums[0]) == (g_uBoardSize - 1)))
+ {
+ return(TRUE);
+ }
+ if ((m->cVpos == ((g_uBoardSize - m->cHpos) - 1)) &&
+ (abs(p->iDSums[1] == (g_uBoardSize - 1))))
+ {
+ return(TRUE);
+ }
+ return(FALSE);
+}
+
+
+BOOL
+IsMoveWorthSearching(POSITION *p, MOVE *m)
+{
+ signed int h;
+ signed int v;
+ unsigned int uSum = 0;
+
+ for (h = m->cHpos - 1;
+ h < (signed int)m->cHpos + 2;
+ h++)
+ {
+ for (v = m->cVpos - 1;
+ v < (signed int)m->cVpos + 2;
+ v++)
+ {
+ if (GOOD_COORD((COORD)v) && GOOD_COORD((COORD)h))
+ {
+ uSum += abs(p->sBoard[v][h]);
+ }
+ }
+ }
+
+ if (uSum == 0)
+ {
+ return(FALSE);
+ }
+ return(TRUE);
+}
+
+
+int
+Eval(POSITION *p)
+{
+ int iSum = p->iDSums[0];
+ COORD x;
+
+ for (x = 0;
+ x < g_uBoardSize;
+ x++)
+ {
+ iSum += p->iHSums[x];
+ iSum += p->iVSums[x];
+ }
+ iSum += p->iDSums[1];
+
+ return(iSum * p->sWhoseTurn);
+}
+
+
+//+----------------------------------------------------------------------------
+//
+// Function: AlphaBeta
+//
+// Synopsis: An AlphaBeta Search
+//
+// Arguments: IN OUT POSITION *p - the board
+// IN int iAlpha - the lower bound of the score window
+// IN int iBeta - the upper bound of the score window
+// IN int uDepth - search depth horizon
+//
+// Returns: int
+//
+//+----------------------------------------------------------------------------
+int
+AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta, IN unsigned int uDepth)
+{
+ SQUARE sWhoWon;
+ COORD s;
+ MOVE mv;
+ int iScore;
+ int iBestScore = -INFINITY - 2;
+ BOOL fMoveIsSingular;
+ unsigned int uNextDepth;
+ unsigned int uMoveNum = 1;
+
+ g_uNodes++;
+
+ //
+ // Evaluate this position
+ //
+ if (TRUE == GameOver(p, &sWhoWon))
+ {
+ if (sWhoWon == p->sWhoseTurn)
+ {
+ return(+INFINITY - g_uPly);
+ }
+ else if (sWhoWon == (p->sWhoseTurn * -1))
+ {
+ return(-INFINITY + g_uPly);
+ }
+ return(DRAWSCORE);
+ }
+ else if (uDepth == 0)
+ {
+ return(Eval(p));
+ }
+
+ //
+ // No one won, game is still going. Evaluate some moves from here.
+ //
+ ASSERT(p->uNumEmpty > 0);
+ for (s = 0; s < (g_uBoardSize * g_uBoardSize); s++)
+ {
+ mv.cHpos = NUM_TO_HPOS(s);
+ mv.cVpos = NUM_TO_VPOS(s);
+ mv.sMark = p->sWhoseTurn;
+
+ if (IsLegalMove(p, &mv))
+ {
+ //
+ // Determine if move is singular
+ //
+ fMoveIsSingular = IsMoveSingular(p, &mv);
+
+ if ((FALSE == fMoveIsSingular) &&
+ (uMoveNum > 1))
+ {
+ //
+ // Determine if we should bother with this subtree...
+ //
+ if (FALSE == IsMoveWorthSearching(p, &mv))
+ {
+ continue;
+ }
+ }
+
+ //
+ // Do it
+ //
+ MakeMove(p, &mv);
+ uMoveNum++;
+
+ uNextDepth = uDepth - 1;
+ if (TRUE == fMoveIsSingular)
+ {
+ uNextDepth = uDepth;
+ g_uExtensions++;
+ }
+ iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uNextDepth);
+ ASSERT(-INFINITY <= iScore);
+ ASSERT(iScore <= +INFINITY);
+
+ UnmakeMove(p, &mv);
+
+ //
+ // Fail high
+ //
+ if (iScore >= iBeta)
+ {
+ return(iScore);
+ }
+
+ if (iScore > iBestScore)
+ {
+ iBestScore = iScore;
+
+ if (iScore > iAlpha)
+ {
+ //
+ // PV node
+ //
+ iAlpha = iScore;
+
+ //
+ // If this is the ply 0 move, remember it.
+ //
+ if (g_uPly == 0)
+ {
+ g_mvBest = mv;
+ }
+ }
+ }
+ }
+ }
+ return(iBestScore);
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: SearchForComputerMove
+//
+// Synopsis: Use our sophisticated search algorithm to find a computer
+// move
+//
+// Arguments: IN POSITION *p - the current board
+// OUT MOVE *m - the move the computer chooses; this move struct
+// is populated as a side-effect of this function.
+//
+// Returns: void* (populates move struct)
+//
+//+----------------------------------------------------------------------------
+void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)
+{
+#if defined(PLAY_RANDOMLY)
+ unsigned int x;
+
+ do
+ {
+ x = rand() % (g_uBoardSize * g_uBoardSize);
+ m->cHpos = NUM_TO_HPOS(x);
+ m->cVpos = NUM_TO_VPOS(x);
+ m->sMark = g_sComputerPlays;
+ }
+ while(FALSE == IsLegalMove(p, m));
+
+#elif defined(ALPHA_BETA_SEARCH)
+ double dTime;
+
+ g_uPly = g_uNodes = g_uExtensions = 0;
+
+ AlphaBeta(p, -INFINITY-1, +INFINITY+1, 3);
+ *m = g_mvBest;
+ printf("Searched %u node(s), %u extension(s)\n",
+ g_uNodes,
+ g_uExtensions);
+#else
+
+ #error "No Search Strategy Defined"
+
+#endif
+}
+
+//+----------------------------------------------------------------------------
+//
+// Function: main
+//
+// Synopsis: The program entry point and main game loop.
+//
+// Arguments: void
+//
+// Returns: int
+//
+//+----------------------------------------------------------------------------
+int
+main(void)
+{
+ POSITION p;
+ MOVE mv;
+ SQUARE sResult;
+ unsigned int u;
+
+ //
+ // Randomize: the random numbers returned by rand() will be based on
+ // the system clock when the program starts up.
+ //
+ srand(time(0));
+
+ //
+ // Make the board
+ //
+ do
+ {
+ printf("How big do you want the board (2..20)? ");
+ scanf("%u", &g_uBoardSize);
+ }
+ while((g_uBoardSize < 2) || (g_uBoardSize > 20));
+
+ //
+ // Allocate space for 2d int array ptr
+ //
+ p.sBoard = (SQUARE **)malloc(g_uBoardSize * sizeof(SQUARE *));
+ if (NULL == p.sBoard)
+ {
+ fprintf(stderr, "Out of memory\n");
+ exit(1);
+ }
+
+ //
+ // Allocate each row of the array
+ //
+ for (u = 0; u < g_uBoardSize; u++)
+ {
+ p.sBoard[u] = (SQUARE *)
+ malloc(g_uBoardSize * sizeof(SQUARE));
+ if (NULL == p.sBoard[u])
+ {
+ fprintf(stderr, "Out of memory!\n");
+ exit(1);
+ }
+ }
+
+ //
+ // Allocate space for sums
+ //
+ p.iHSums = (int *)malloc(g_uBoardSize * sizeof(int));
+ p.iVSums = (int *)malloc(g_uBoardSize * sizeof(int));
+ if ((NULL == p.iHSums) ||
+ (NULL == p.iVSums))
+ {
+ fprintf(stderr, "Out of memory!\n");
+ exit(1);
+ }
+
+ //
+ // Setup the board and draw it once.
+ //
+ ClearBoard(&p);
+ DrawBoard(&p);
+
+ //
+ // Main game loop
+ //
+ do
+ {
+ //
+ // See whose turn it is -- the human's or the computers -- and
+ // get a move from whoever's turn it is.
+ //
+ if (p.sWhoseTurn == g_sComputerPlays)
+ {
+ SearchForComputerMove(&p, &mv);
+ }
+ else
+ {
+ //SearchForComputerMove(&p, &mv);
+ GetHumanMove(&p, &mv);
+ }
+
+ //
+ // Make the move on the board and draw the board again.
+ //
+ MakeMove(&p, &mv);
+ DrawBoard(&p);
+ }
+ while(FALSE == GameOver(&p, &sResult));
+
+ //
+ // If we get here the game is over... see what happened.
+ //
+ switch(sResult)
+ {
+ case X_MARK:
+ printf("\nX's win.\n");
+ break;
+ case O_MARK:
+ printf("\nO's win.\n");
+ break;
+ default:
+ printf("Tie (what a surprise)\n");
+ break;
+ }
+
+ //
+ // TODO: cleanup heap
+ //
+
+ exit(0);
+}
projects / ttt.git / commitdiff