ConnectK Sample

#include "StdAfx.h"
#include "ConnectK.h"

// constructor
ConnectK::ConnectK()
    : M(0), N(0), K(0), G(FALSE)
{
    board = 0;
}

// destructor
ConnectK::~ConnectK()
{
    for ( int i = 0; i < M; i++ )
        delete [] board[i];

    delete [] board;
}

/////////////////////////////////////////////////////////////////////////////////////////
// newGame(int pM, int pN, int pK, bool pG, char pmark)
//
// Purpose:     This function is to allocate memory and initialize structures necessary
//              to play the game defined by the parameters, M, N, K and G passed by the
//              GUI (or other driving program to this class).  In this sample code, we are
//              using a two dimensional dynamic array of characters to represent the board
//              and the symbols X, O, and BLANK (defined in the ConnectK.h file) to keep
//              track of game progress.
//
//  Parameters: pM      number of rows in the game board
//              pN      number of columns in the game board
//              pK      number in a row to win the game
//              pG      Gravity on/off. Determines whether or not game pieces fall to the
//                      lowest available position in a column (as in Connect 4), or remain
//                      in the position places (as in Tic-tac-toe).
//              pmark   this is the mark that the computer player has been assigned.
//                      it will be either 'X' or 'O'.  It is not actually necessary to use
//                      this variable, but you may find it useful to know which player will
//                      move first, prior to nextMove() being called.
//
// Returns:     nothing.
//
// NOTE:        This function can be called at any time from the GUI.  Make sure it
//              can re-allocate memory and re-initialize variables, game after game.
//
//              The board layout used by the GUI has the origin located at the top left corner
//              of the board.  For example:
//
//                  N columns
//
//                0  1  2..N-1
//               +-----------+
//              0|  |  |  |  |
//               |--+--+--+--|
//              1|  |  |  |  |
//     M rows    |--+--+--+--|
//              2|  |  |  |  |
//             ..|--+--+--+--|
//            M-1|  |  |  |  |
//               +-----------+
//
void ConnectK::newGame(int pM, int pN, int pK, bool pG, char pmark)
{
    // re-initialize all variables

    // delete the previous game board if it exists
    if ( board != NULL )
    {
        for ( int i = 0; i < M; i++ )
            delete [] board[i];
        board = 0;
        delete [] board;
    }

    // p is for parameter
    M = pM;
    N = pN;
    K = pK;
    G = pG;
    computerMark = pmark;

    // initialize the board to all blank characters (see ConnectK.h for definitions)
    if ( M > 0 && N > 0 )
    {
        board = new CharArray[M];

        for (int i = 0; i < M; i++)
        {
            board[i] = new char[N];
            for (int j = 0; j < N; j++)
            {
                board[i][j] = BLANK;
            }
        }
    }
    else
        cerr << "Error: bad array size." << endl;
}

/////////////////////////////////////////////////////////////////////////////////////////
// nextMove(int &row, int &col)
//
// Purpose:     This function receives the move made by the human player (or other AI
//              player), records it, and returns a move based on an AI search routine.
//
// Parameters:  &row    this holds the row coordinate of the move made by the human player
//              &col    this holds the column coordinate of the move made by the human player
//
// Returns:     &row    place the row value of the move made by your AI search in this variable
//              &col    place the column value of the move made by your AI in this variable
//
// NOTE:        Remember to do all initialization in newGame().  This function must be ready to
//              return a move when given one, and will determine the time taken by your program
//              in tournament competition.  Make your search as efficient as possible.
//

void ConnectK::nextMove(int &row, int &col)
{

    Node temp;
    PointItem tempItem;
    PointList* bestMove = new PointList();

    int alpha;
    int beta;

    int searchDepth = 1;

    CTime startTime;
    CTimeSpan timespan;

    char playerMark;

    bool searching = true;

    ConnectK::logfile.open("textlog.txt");

    if (computerMark == X)
        playerMark = O;
    else
        playerMark = X;

    // If x and y are not -1 then we need to record the move made by the human player
    // If x and y are -1, then this is the first move of the game, the AI moves first.
    if( ( row != -1 ) && ( col != -1 ) )
    {
        if(G)
        {
            row = 0;
            while(row < M - 1 && board[row+1][col] == BLANK)
                row++;
        }
        board[row][col] = playerMark;
    }

    ConnectK::logfile << "BEGIN" << endl;

    startTime = CTime::GetCurrentTime();
    alpha = MIN_HEURISTIC;
    beta = MAX_HEURISTIC;

    while(searching)
    {
        Killers = new PointItem[searchDepth+1];
        ConnectK::logfile << "Search level: " << searchDepth << endl << endl;
        tempItem = alphaBetaDeepening(searchDepth, true, alpha, beta);
        ConnectK::logfile << endl << "-----------------/ CUTOFF \\------------------ (" << tempItem.vals.x << ", " << tempItem.vals.y << ") :: " << tempItem.value << endl << endl;
        (*bestMove).Add(tempItem.vals);
        timespan = CTime::GetCurrentTime() - startTime;
        // check if we've broken the time limit
        if(timespan.GetSeconds() >= TIME_LIMIT)
            searching = false;
        searchDepth++;
        if(tempItem.value == MAX_HEURISTIC || tempItem.value == MIN_HEURISTIC) //search cutoff if we win here or lose no matter what we do
            searching = false;
        if(searchDepth > K+1)  //arbitary cutoff to produce snappy response times in the final version
            searching = false;

        // an interesting note: at 5 plies this program will always produce a move in < 150 ms on
        // the standard setting. Humans cannot process anything generally faster than 200 ms and at
        // their best 150 ms. Anything that happens in 150 ms is percieved as instantaneous to a human

        delete[] Killers;
    }
    temp = (*bestMove).Get(0);
#ifdef DEBUGGING
    ConnectK::logfile << "(" <<(*(*bestMove).Head).value << " " << (*(*bestMove).Tail).value << ")" << endl;
#endif

    row = temp.x;
    col = temp.y;
    if(G)
        while(row < M - 1 && board[row+1][col] == BLANK)
            row++;
    board[row][col] = computerMark;

    ConnectK::logfile.close();
    delete bestMove;
    return;
}
/////////////////////////////////////////////////////////////////////////////////////////
// Begin helper functions
/////////////////////////////////////////////////////////////////////////////////////////

PointItem ConnectK::alphaBetaDeepening(int depth, bool maxTurn, int alpha, int beta)
{
    //PointList* heuristicList = new PointList();
    PointList* moves;
    PointList* searchList = new PointList();
    Node move;
    PointItem return_value;
    PointItem temp;
    char playerMark;

    return_value.value = 0;
    return_value.vals.x = 0;
    return_value.vals.y = 0;
    return_value.next = NULL;
    DWORD start,end;
    start = GetTickCount();
#ifdef DEBUGGING
    ConnectK::logfile << "Depth: " << depth;
    for(int i = 0; i < (*searchList).Size(); i++)
        ConnectK::logfile << " " << (*(*searchList).Get(i)).Print();
    ConnectK::logfile << " ";
#endif

    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(board[i][j] == BLANK && (!G || i == M-1 || board[i+1][j] != BLANK))
            {
                (*searchList).Add(i,j);
            }
        }
    }
    // rearrange our search list based on heuristic value
    searchListOrderingHeuristic(searchList, depth);


    if(computerMark == X)
        playerMark = O;
    else
        playerMark = X;

    if(depth <= 0 || (*searchList).Size() == 0)
    {
        return_value.value = evaluateBoard();
#ifdef DEBUGGING
        ConnectK::logfile << "RETURN: " << (*(*moveStack).Get(0)).Print() << " " << return_value.value;
        end = GetTickCount();
        ConnectK::logfile << " t:" << end - start << " ms" << endl;
#endif
        delete searchList;
        return return_value;
    }
    else
    {
        moves = new PointList();
        for(int i = 0; i < (*searchList).Size(); i++)
        {
            move.x = (*searchList).Get(i).x;
            move.y = (*searchList).Get(i).y;
            if(maxTurn)
                board[move.x][move.y] = computerMark;
            else
                board[move.x][move.y] = playerMark;
            temp = alphaBetaDeepening(depth-1, !maxTurn, alpha, beta);
            board[move.x][move.y] = BLANK;
#ifdef DEBUGGING
            if(temp.value == MIN_HEURISTIC)
                ConnectK::logfile << " MIN_HEURISTIC ";
            else if(temp.value == MAX_HEURISTIC)
                ConnectK::logfile << " MAX_HEURISITC ";
#endif

            if(maxTurn)
            {
                if(temp.value > alpha)
                    alpha = temp.value;
            }
            else
            {
                if(temp.value < beta)
                    beta = temp.value;

            }

            (*moves).Add(move, temp.value);

            if(beta <= alpha)
                break;
        }
        if(maxTurn)
        {
            if((*moves).Size() > 0)
            {
                return_value.vals = (*moves).Head->vals;
            }
            else
            {
                return_value.vals.x = -1;
                return_value.vals.y = -1;
            }
            return_value.value = alpha;
            if(Killers[depth].value < alpha)
                Killers[depth] = return_value;
        }
        else
        {
            if((*moves).Size() > 0)
            {
                return_value.vals = (*moves).Tail->vals;
            }
            else
            {
                return_value.vals.x = -1;
                return_value.vals.y = -1;
            }
            return_value.value = beta;
            if(Killers[depth].value > beta)
                Killers[depth] = return_value;
        }
#ifdef DEBUGGING
        if(return_value.vals == NULL)
            ConnectK::logfile << "RETURN: (-1,-1)";
        else
            ConnectK::logfile << "RETURN: " << (*return_value.vals).Print();
#endif
        end = GetTickCount();
        ConnectK::logfile  << " alpha: " << alpha << " beta: " << beta << " t:" << end - start << " ms" << endl;

        delete moves;
        delete searchList;
        return return_value;
    }
}

// The idea behind this function is to reorder searchList into a temporary list
// We order the items in searchList by the number of pieces in its immediate vicinity
// This is O(b*K)
// And then place our items back into searchList
void ConnectK::searchListOrderingHeuristic(PointList* searchList, int depth)
{
    PointList* tempList = new PointList();
    Node tempNode;
    int neighborCount, x, y;

    while((*searchList).Size() > 0)
    {
        neighborCount = 0;
        tempNode = (*searchList).Get(0);
        for(int j = 0; j < 8; j++)
        {
            for(int k = 0; k < K/2; k++)
            {
                switch(j)
                {
                    case 0:
                        x = tempNode.x+k;
                        y = tempNode.y;
                        break;
                    case 1:
                        x = tempNode.x+k;
                        y = tempNode.y+k;
                        break;
                    case 2:
                        x = tempNode.x;
                        y = tempNode.y+k;
                        break;
                    case 3:
                        x = tempNode.x-k;
                        y = tempNode.y+k;
                        break;
                    case 4:
                        x = tempNode.x-k;
                        y = tempNode.y;
                        break;
                    case 5:
                        x = tempNode.x-k;
                        y = tempNode.y-k;
                        break;
                    case 6:
                        x = tempNode.x;
                        y = tempNode.y-k;
                        break;
                    case 7:
                        x = tempNode.x+k;
                        y = tempNode.y-k;
                        break;
                }
                    if(x < M && x >= 0 && y < N && y >= 0 && board[x][y] != BLANK)
                        neighborCount++;
            }
        }
        (*tempList).Add(tempNode.x, tempNode.y, neighborCount);
        (*searchList).Remove(0);
    }
    //now searchList is empty and tempList has the ordered nodes, so we just put everything from tempList back in searchList
    while((*tempList).Size() > 0)
    {
        //now we check if we have any killer moves and pull those to the front
        if(Killers[depth].vals.x == (*tempList).Get(0).x && Killers[depth].vals.y == (*tempList).Get(0).y)
            (*(*tempList).Head).value = MAX_HEURISTIC;
        (*searchList).Add((*tempList).Get(0).x, (*tempList).Get(0).y, (*(*tempList).Head).value);
        (*tempList).Remove(0);
    }

    delete tempList;
    return;
}

int ConnectK::evaluateBoard()
{
    int xtemppos = 0;
    int ytemppos = 0;

    int maxCount = 0;
    int minCount = 0;
    int retval = 0;
    bool maxWinFlag = false;
    bool minWinFlag = false;

    char playerMark = BLANK;

    if (computerMark == X)
        playerMark = O;
    else
        playerMark = X;
#ifdef DEBUGGING
    ConnectK::logfile << endl;
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            ConnectK::logfile << board[i][j] << "_";
        }
        ConnectK::logfile << endl;
    }
#endif

    // now we need to provide an evaluation from the value of every position on our board
    // This will be O(n^2), but not tightly bounded. We need only look back at 4*K tiles at most
    // per square, so we're O(4*K*M*N)

    for(int x = 0; x < M; x++)
    {
        for(int y = 0; y < N; y++)
        {
            for(int i = 0; i < 4; i++)
            {
                maxCount = 0;
                minCount = 0;
                for(int k = 0; k < K; k++)
                {
                    switch(i)
                    {
                        case 0:
                            xtemppos = x;
                            ytemppos = y - k;
                            break;
                        case 1:
                            xtemppos = x - k;
                            ytemppos = y - k;
                            break;
                        case 2:
                            xtemppos = x - k;
                            ytemppos = y;
                            break;
                        case 3:
                            xtemppos = x - k;
                            ytemppos = y + k;
                            break;
                    }
                    if(xtemppos < M && xtemppos >= 0 && ytemppos < N && ytemppos >= 0)
                    {
                        if ( board[xtemppos][ytemppos] == computerMark )
                        {
                            maxCount++;
                            if(minCount && maxCount)
                            {
                                maxCount = 0;
                                minCount = 0;
                                break; //both pieces, row has no value
                            }
                        }
                        else if ( board[xtemppos][ytemppos] == playerMark )
                        {
                            minCount++;
                            if(minCount && maxCount)
                            {
                                maxCount = 0;
                                minCount = 0;
                                break; //both pieces, row has no value
                            }
                        }
                        else
                        {
                            if(G && xtemppos < M-1 && board[xtemppos+1][ytemppos] == BLANK)
                            {
                                maxCount = 0;
                                minCount = 0;
                                break;
                            }
                        }
                    }
                    else
                    {
                        maxCount = 0;
                        minCount = 0;
                        break; //less than K space, row has no value
                    }
                }
                if(maxCount)
                {
                    if(maxCount >= K)
                    {
                        maxWinFlag = true;
                    }
                    else
                        retval++;
                }
                else if(minCount)
                {
                    if(minCount >= K)
                    {
                        minWinFlag = true;
                    }
                    else
                        retval--;
                }

            }
        }
    }
    if(maxWinFlag && minWinFlag)
        if(computerMark == O)
            retval = MIN_HEURISTIC;
        else
            retval = MAX_HEURISTIC;
    else if (maxWinFlag)
        retval = MAX_HEURISTIC;
    else if (minWinFlag)
        retval = MIN_HEURISTIC;

    return retval;
}