diff options
Diffstat (limited to 'ver5')
| -rw-r--r-- | ver5/ttt.c | 1532 |
1 files changed, 766 insertions, 766 deletions
@@ -1,766 +1,766 @@ -/*++
-
-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);
-}
+/*++ + +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); +} |