Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

ConnectK Sample

By: a guest on Jun 10th, 2012  |  syntax: C++  |  size: 17.30 KB  |  views: 71  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include "StdAfx.h"
  2. #include "ConnectK.h"
  3.  
  4. // constructor
  5. ConnectK::ConnectK()
  6.         : M(0), N(0), K(0), G(FALSE)
  7. {
  8.         board = 0;
  9. }
  10.  
  11. // destructor
  12. ConnectK::~ConnectK()
  13. {
  14.         for ( int i = 0; i < M; i++ )
  15.                 delete [] board[i];
  16.  
  17.         delete [] board;
  18. }
  19.  
  20. /////////////////////////////////////////////////////////////////////////////////////////
  21. // newGame(int pM, int pN, int pK, bool pG, char pmark)
  22. //
  23. // Purpose:             This function is to allocate memory and initialize structures necessary
  24. //                              to play the game defined by the parameters, M, N, K and G passed by the
  25. //                              GUI (or other driving program to this class).  In this sample code, we are
  26. //                              using a two dimensional dynamic array of characters to represent the board
  27. //                              and the symbols X, O, and BLANK (defined in the ConnectK.h file) to keep
  28. //                              track of game progress.
  29. //
  30. //      Parameters:     pM              number of rows in the game board
  31. //                              pN              number of columns in the game board
  32. //                              pK              number in a row to win the game
  33. //                              pG              Gravity on/off. Determines whether or not game pieces fall to the
  34. //                                              lowest available position in a column (as in Connect 4), or remain
  35. //                                              in the position places (as in Tic-tac-toe).
  36. //                              pmark   this is the mark that the computer player has been assigned.
  37. //                                              it will be either 'X' or 'O'.  It is not actually necessary to use
  38. //                                              this variable, but you may find it useful to know which player will
  39. //                                              move first, prior to nextMove() being called.
  40. //
  41. // Returns:             nothing.
  42. //
  43. // NOTE:                This function can be called at any time from the GUI.  Make sure it
  44. //                              can re-allocate memory and re-initialize variables, game after game.
  45. //
  46. //                              The board layout used by the GUI has the origin located at the top left corner
  47. //                              of the board.  For example:
  48. //
  49. //                                      N columns
  50. //
  51. //                                0  1  2..N-1
  52. //               +-----------+
  53. //              0|      |  |  |  |
  54. //               |--+--+--+--|
  55. //                              1|      |  |  |  |
  56. //     M rows    |--+--+--+--|
  57. //                              2|  |  |  |      |
  58. //             ..|--+--+--+--|
  59. //                        M-1|  |  |  |  |
  60. //               +-----------+
  61. //
  62. void ConnectK::newGame(int pM, int pN, int pK, bool pG, char pmark)
  63. {      
  64.         // re-initialize all variables
  65.  
  66.         // delete the previous game board if it exists
  67.         if ( board != NULL )
  68.         {
  69.                 for ( int i = 0; i < M; i++ )
  70.                         delete [] board[i];
  71.                 board = 0;     
  72.                 delete [] board;
  73.         }
  74.  
  75.         // p is for parameter
  76.         M = pM;
  77.         N = pN;
  78.         K = pK;
  79.         G = pG;
  80.         computerMark = pmark;
  81.  
  82.         // initialize the board to all blank characters (see ConnectK.h for definitions)
  83.         if ( M > 0 && N > 0 )
  84.         {
  85.                 board = new CharArray[M];
  86.  
  87.         for (int i = 0; i < M; i++)
  88.                 {
  89.                         board[i] = new char[N];
  90.                         for (int j = 0; j < N; j++)
  91.             {                  
  92.                 board[i][j] = BLANK;
  93.             }  
  94.                 }
  95.         }
  96.         else
  97.                 cerr << "Error: bad array size." << endl;
  98. }
  99.  
  100. /////////////////////////////////////////////////////////////////////////////////////////
  101. // nextMove(int &row, int &col)
  102. //
  103. // Purpose:             This function receives the move made by the human player (or other AI
  104. //                              player), records it, and returns a move based on an AI search routine.
  105. //
  106. // Parameters:  &row    this holds the row coordinate of the move made by the human player
  107. //                              &col    this holds the column coordinate of the move made by the human player
  108. //
  109. // Returns:             &row    place the row value of the move made by your AI search in this variable
  110. //                              &col    place the column value of the move made by your AI in this variable
  111. //
  112. // NOTE:                Remember to do all initialization in newGame().  This function must be ready to
  113. //                              return a move when given one, and will determine the time taken by your program
  114. //                              in tournament competition.  Make your search as efficient as possible.
  115. //
  116.  
  117. void ConnectK::nextMove(int &row, int &col)
  118. {
  119.  
  120.     Node temp;
  121.     PointItem tempItem;
  122.     PointList* bestMove = new PointList();
  123.  
  124.     int alpha;
  125.     int beta;
  126.  
  127.     int searchDepth = 1;
  128.  
  129.     CTime startTime;
  130.     CTimeSpan timespan;
  131.  
  132.     char playerMark;
  133.  
  134.     bool searching = true;
  135.  
  136.     ConnectK::logfile.open("textlog.txt");
  137.  
  138.     if (computerMark == X)
  139.         playerMark = O;
  140.     else
  141.         playerMark = X;
  142.  
  143.     // If x and y are not -1 then we need to record the move made by the human player
  144.         // If x and y are -1, then this is the first move of the game, the AI moves first.
  145.         if( ( row != -1 ) && ( col != -1 ) )
  146.         {        
  147.         if(G)
  148.         {
  149.             row = 0;
  150.             while(row < M - 1 && board[row+1][col] == BLANK)
  151.                 row++;
  152.         }
  153.             board[row][col] = playerMark;            
  154.     }
  155.  
  156.     ConnectK::logfile << "BEGIN" << endl;
  157.    
  158.     startTime = CTime::GetCurrentTime();
  159.     alpha = MIN_HEURISTIC;
  160.     beta = MAX_HEURISTIC;
  161.  
  162.     while(searching)
  163.     {
  164.         Killers = new PointItem[searchDepth+1];
  165.         ConnectK::logfile << "Search level: " << searchDepth << endl << endl;
  166.         tempItem = alphaBetaDeepening(searchDepth, true, alpha, beta);
  167.         ConnectK::logfile << endl << "-----------------/ CUTOFF \\------------------ (" << tempItem.vals.x << ", " << tempItem.vals.y << ") :: " << tempItem.value << endl << endl;
  168.         (*bestMove).Add(tempItem.vals);
  169.         timespan = CTime::GetCurrentTime() - startTime;
  170.         // check if we've broken the time limit
  171.         if(timespan.GetSeconds() >= TIME_LIMIT)
  172.             searching = false;
  173.                 searchDepth++;
  174.         if(tempItem.value == MAX_HEURISTIC || tempItem.value == MIN_HEURISTIC) //search cutoff if we win here or lose no matter what we do
  175.                         searching = false;
  176.         if(searchDepth > K+1)  //arbitary cutoff to produce snappy response times in the final version
  177.             searching = false;
  178.  
  179.         // an interesting note: at 5 plies this program will always produce a move in < 150 ms on
  180.         // the standard setting. Humans cannot process anything generally faster than 200 ms and at
  181.         // their best 150 ms. Anything that happens in 150 ms is percieved as instantaneous to a human
  182.  
  183.         delete[] Killers;
  184.     }
  185.     temp = (*bestMove).Get(0);
  186. #ifdef DEBUGGING
  187.     ConnectK::logfile << "(" <<(*(*bestMove).Head).value << " " << (*(*bestMove).Tail).value << ")" << endl;
  188. #endif
  189.  
  190.     row = temp.x;
  191.     col = temp.y;
  192.     if(G)
  193.         while(row < M - 1 && board[row+1][col] == BLANK)
  194.             row++;      
  195.     board[row][col] = computerMark;
  196.    
  197.     ConnectK::logfile.close();
  198.     delete bestMove;
  199.     return;
  200. }
  201. /////////////////////////////////////////////////////////////////////////////////////////
  202. // Begin helper functions
  203. /////////////////////////////////////////////////////////////////////////////////////////
  204.  
  205. PointItem ConnectK::alphaBetaDeepening(int depth, bool maxTurn, int alpha, int beta)
  206. {
  207.         //PointList* heuristicList = new PointList();
  208.     PointList* moves;
  209.     PointList* searchList = new PointList();
  210.     Node move;
  211.         PointItem return_value;
  212.         PointItem temp;
  213.     char playerMark;
  214.  
  215.     return_value.value = 0;
  216.     return_value.vals.x = 0;
  217.     return_value.vals.y = 0;
  218.     return_value.next = NULL;
  219.     DWORD start,end;
  220.     start = GetTickCount();
  221. #ifdef DEBUGGING
  222.     ConnectK::logfile << "Depth: " << depth;
  223.     for(int i = 0; i < (*searchList).Size(); i++)
  224.         ConnectK::logfile << " " << (*(*searchList).Get(i)).Print();
  225.     ConnectK::logfile << " ";
  226. #endif
  227.  
  228.     for(int i = 0; i < M; i++)
  229.     {
  230.         for(int j = 0; j < N; j++)
  231.         {
  232.             if(board[i][j] == BLANK && (!G || i == M-1 || board[i+1][j] != BLANK))
  233.             {
  234.                 (*searchList).Add(i,j);
  235.             }
  236.         }
  237.     }
  238.     // rearrange our search list based on heuristic value
  239.     searchListOrderingHeuristic(searchList, depth);
  240.    
  241.  
  242.     if(computerMark == X)
  243.         playerMark = O;
  244.     else
  245.         playerMark = X;
  246.  
  247.         if(depth <= 0 || (*searchList).Size() == 0)
  248.         {
  249.                 return_value.value = evaluateBoard();
  250. #ifdef DEBUGGING
  251.         ConnectK::logfile << "RETURN: " << (*(*moveStack).Get(0)).Print() << " " << return_value.value;
  252.         end = GetTickCount();
  253.         ConnectK::logfile << " t:" << end - start << " ms" << endl;
  254. #endif
  255.         delete searchList;
  256.                 return return_value;
  257.         }
  258.         else
  259.         {
  260.         moves = new PointList();
  261.                 for(int i = 0; i < (*searchList).Size(); i++)
  262.                 {
  263.                         move.x = (*searchList).Get(i).x;
  264.             move.y = (*searchList).Get(i).y;
  265.             if(maxTurn)
  266.                 board[move.x][move.y] = computerMark;
  267.             else
  268.                 board[move.x][move.y] = playerMark;
  269.                         temp = alphaBetaDeepening(depth-1, !maxTurn, alpha, beta);
  270.             board[move.x][move.y] = BLANK;
  271. #ifdef DEBUGGING
  272.             if(temp.value == MIN_HEURISTIC)
  273.                 ConnectK::logfile << " MIN_HEURISTIC ";
  274.             else if(temp.value == MAX_HEURISTIC)
  275.                 ConnectK::logfile << " MAX_HEURISITC ";
  276. #endif
  277.  
  278.             if(maxTurn)
  279.             {
  280.                 if(temp.value > alpha)
  281.                     alpha = temp.value;
  282.             }
  283.             else
  284.             {
  285.                 if(temp.value < beta)
  286.                     beta = temp.value;
  287.                
  288.             }            
  289.  
  290.             (*moves).Add(move, temp.value);
  291.  
  292.             if(beta <= alpha)
  293.                 break;
  294.                 }
  295.         if(maxTurn)
  296.         {
  297.             if((*moves).Size() > 0)
  298.             {
  299.                 return_value.vals = (*moves).Head->vals;
  300.             }
  301.             else
  302.             {
  303.                 return_value.vals.x = -1;
  304.                 return_value.vals.y = -1;
  305.             }
  306.             return_value.value = alpha;
  307.             if(Killers[depth].value < alpha)
  308.                 Killers[depth] = return_value;
  309.         }
  310.         else
  311.         {
  312.             if((*moves).Size() > 0)
  313.             {
  314.                 return_value.vals = (*moves).Tail->vals;
  315.             }
  316.             else
  317.             {
  318.                 return_value.vals.x = -1;
  319.                 return_value.vals.y = -1;                
  320.             }
  321.             return_value.value = beta;
  322.             if(Killers[depth].value > beta)
  323.                 Killers[depth] = return_value;
  324.         }
  325. #ifdef DEBUGGING
  326.         if(return_value.vals == NULL)
  327.             ConnectK::logfile << "RETURN: (-1,-1)";
  328.         else
  329.             ConnectK::logfile << "RETURN: " << (*return_value.vals).Print();        
  330. #endif
  331.         end = GetTickCount();
  332.         ConnectK::logfile  << " alpha: " << alpha << " beta: " << beta << " t:" << end - start << " ms" << endl;
  333.  
  334.         delete moves;
  335.         delete searchList;
  336.         return return_value;
  337.         }
  338. }
  339.  
  340. // The idea behind this function is to reorder searchList into a temporary list
  341. // We order the items in searchList by the number of pieces in its immediate vicinity
  342. // This is O(b*K)
  343. // And then place our items back into searchList
  344. void ConnectK::searchListOrderingHeuristic(PointList* searchList, int depth)
  345. {
  346.     PointList* tempList = new PointList();
  347.     Node tempNode;
  348.     int neighborCount, x, y;
  349.  
  350.     while((*searchList).Size() > 0)
  351.     {
  352.         neighborCount = 0;
  353.         tempNode = (*searchList).Get(0);
  354.         for(int j = 0; j < 8; j++)
  355.         {
  356.             for(int k = 0; k < K/2; k++)
  357.             {
  358.                 switch(j)
  359.                 {
  360.                     case 0:
  361.                         x = tempNode.x+k;
  362.                         y = tempNode.y;
  363.                         break;
  364.                     case 1:
  365.                         x = tempNode.x+k;
  366.                         y = tempNode.y+k;
  367.                         break;
  368.                     case 2:
  369.                         x = tempNode.x;
  370.                         y = tempNode.y+k;
  371.                         break;
  372.                     case 3:
  373.                         x = tempNode.x-k;
  374.                         y = tempNode.y+k;
  375.                         break;
  376.                     case 4:
  377.                         x = tempNode.x-k;
  378.                         y = tempNode.y;
  379.                         break;
  380.                     case 5:
  381.                         x = tempNode.x-k;
  382.                         y = tempNode.y-k;
  383.                         break;
  384.                     case 6:
  385.                         x = tempNode.x;
  386.                         y = tempNode.y-k;
  387.                         break;
  388.                     case 7:
  389.                         x = tempNode.x+k;
  390.                         y = tempNode.y-k;
  391.                         break;
  392.                 }
  393.                     if(x < M && x >= 0 && y < N && y >= 0 && board[x][y] != BLANK)
  394.                         neighborCount++;
  395.             }
  396.         }
  397.         (*tempList).Add(tempNode.x, tempNode.y, neighborCount);
  398.         (*searchList).Remove(0);
  399.     }
  400.     //now searchList is empty and tempList has the ordered nodes, so we just put everything from tempList back in searchList
  401.     while((*tempList).Size() > 0)
  402.     {
  403.         //now we check if we have any killer moves and pull those to the front
  404.         if(Killers[depth].vals.x == (*tempList).Get(0).x && Killers[depth].vals.y == (*tempList).Get(0).y)
  405.             (*(*tempList).Head).value = MAX_HEURISTIC;
  406.         (*searchList).Add((*tempList).Get(0).x, (*tempList).Get(0).y, (*(*tempList).Head).value);
  407.         (*tempList).Remove(0);
  408.     }      
  409.  
  410.     delete tempList;
  411.     return;
  412. }
  413.  
  414. int ConnectK::evaluateBoard()
  415. {
  416.     int xtemppos = 0;
  417.     int ytemppos = 0;
  418.  
  419.         int maxCount = 0;
  420.     int minCount = 0;
  421.     int retval = 0;
  422.     bool maxWinFlag = false;
  423.     bool minWinFlag = false;
  424.    
  425.     char playerMark = BLANK;
  426.  
  427.     if (computerMark == X)
  428.         playerMark = O;
  429.     else
  430.         playerMark = X;
  431. #ifdef DEBUGGING
  432.     ConnectK::logfile << endl;
  433.     for(int i = 0; i < M; i++)
  434.     {
  435.         for(int j = 0; j < N; j++)
  436.         {
  437.             ConnectK::logfile << board[i][j] << "_";
  438.         }
  439.         ConnectK::logfile << endl;
  440.     }
  441. #endif
  442.  
  443.     // now we need to provide an evaluation from the value of every position on our board
  444.     // This will be O(n^2), but not tightly bounded. We need only look back at 4*K tiles at most
  445.     // per square, so we're O(4*K*M*N)
  446.  
  447.     for(int x = 0; x < M; x++)
  448.     {
  449.         for(int y = 0; y < N; y++)
  450.         {
  451.             for(int i = 0; i < 4; i++)
  452.             {
  453.                 maxCount = 0;
  454.                 minCount = 0;
  455.                 for(int k = 0; k < K; k++)
  456.                 {
  457.                     switch(i)
  458.                     {
  459.                         case 0:
  460.                             xtemppos = x;
  461.                             ytemppos = y - k;
  462.                             break;
  463.                         case 1:
  464.                             xtemppos = x - k;
  465.                             ytemppos = y - k;
  466.                             break;
  467.                         case 2:
  468.                             xtemppos = x - k;
  469.                             ytemppos = y;
  470.                             break;
  471.                         case 3:
  472.                             xtemppos = x - k;
  473.                             ytemppos = y + k;
  474.                             break;
  475.                     }
  476.                     if(xtemppos < M && xtemppos >= 0 && ytemppos < N && ytemppos >= 0)
  477.                     {
  478.                         if ( board[xtemppos][ytemppos] == computerMark )
  479.                         {
  480.                             maxCount++;
  481.                             if(minCount && maxCount)
  482.                             {
  483.                                 maxCount = 0;
  484.                                 minCount = 0;
  485.                                 break; //both pieces, row has no value
  486.                             }
  487.                         }
  488.                         else if ( board[xtemppos][ytemppos] == playerMark )
  489.                         {
  490.                             minCount++;
  491.                             if(minCount && maxCount)
  492.                             {
  493.                                 maxCount = 0;
  494.                                 minCount = 0;
  495.                                 break; //both pieces, row has no value
  496.                             }
  497.                         }
  498.                         else
  499.                         {
  500.                             if(G && xtemppos < M-1 && board[xtemppos+1][ytemppos] == BLANK)
  501.                             {
  502.                                 maxCount = 0;
  503.                                 minCount = 0;
  504.                                 break;
  505.                             }
  506.                         }
  507.                     }
  508.                     else
  509.                     {
  510.                         maxCount = 0;
  511.                         minCount = 0;
  512.                         break; //less than K space, row has no value
  513.                     }                    
  514.                 }
  515.                 if(maxCount)
  516.                 {
  517.                     if(maxCount >= K)
  518.                     {
  519.                         maxWinFlag = true;
  520.                     }
  521.                     else
  522.                         retval++;
  523.                 }
  524.                 else if(minCount)
  525.                 {                
  526.                     if(minCount >= K)
  527.                     {
  528.                         minWinFlag = true;
  529.                     }
  530.                     else
  531.                         retval--;
  532.                 }
  533.  
  534.             }
  535.         }
  536.     }
  537.     if(maxWinFlag && minWinFlag)
  538.         if(computerMark == O)
  539.             retval = MIN_HEURISTIC;
  540.         else
  541.             retval = MAX_HEURISTIC;
  542.     else if (maxWinFlag)
  543.         retval = MAX_HEURISTIC;
  544.     else if (minWinFlag)
  545.         retval = MIN_HEURISTIC;
  546.  
  547.     return retval;
  548. }