progcomp/agents/basic_cpp/basic_cpp.cpp

   1 /**
   2  * "basic_cpp", a sample Stratego AI for the UCC Programming Competition 2012
   3  * Implementations of main function, and Helper functions
   4  *
   5  * @author Sam Moore (matches) [SZM]
   6  * @website http://matches.ucc.asn.au/stratego
   7  * @email progcomp@ucc.asn.au or matches@ucc.asn.au
   8  * @git git.ucc.asn.au/progcomp2012.git
   9  */
  10
  11 #include "basic_cpp.h" //Needs class Base_Cpp and the includes in this file
  12
  13 using namespace std;
  14
  15 /**
  16  * The characters used to represent various pieces
  17  * NOTHING, BOULDER, FLAG, SPY, SCOUT, MINER, SERGEANT, LIETENANT, CAPTAIN, MAJOR, COLONEL, GENERAL, MARSHAL, BOMB, UNKNOWN
  18  */
  19 char  Piece::tokens[] = {'.','*','F','s','9','8','7','6','5','4','3','2','1','B','?'};
  20
  21 /**
  22  * Gets a rank from the character used to represent it
  23  * Basic lookup of Piece::tokens
  24  */
  25 Rank Piece::GetRank(char token)
  26 {
  27         for (int ii=0; ii <= 14; ++ii)
  28         {
  29                 if (tokens[ii] == token)
  30                         return (Rank)(ii);
  31         }
  32         return UNKNOWN;
  33 }
  34
  35 /**
  36  * IMPLEMENTATION of Helper FOLLOWS
  37  */
  38
  39 /**
  40  * Convert string to direction
  41  */
  42 Direction Helper::StrToDir(const string & dir)
  43 {
  44         if (dir == "UP")
  45                 return UP;
  46         else if (dir == "DOWN")
  47                 return DOWN;
  48         else if (dir == "LEFT")
  49                 return LEFT;
  50         else if (dir == "RIGHT")
  51                 return RIGHT;
  52         else
  53                 return DIRECTION_ERROR;
  54 }
  55
  56 /**
  57  * Direction to String
  58  */
  59 void Helper::DirToStr(const Direction & dir, std::string & buffer)
  60 {
  61         switch (dir)
  62         {
  63                 case UP:
  64                         buffer = "UP";
  65                         break;
  66                 case DOWN:
  67                         buffer = "DOWN";
  68                         break;
  69                 case LEFT:
  70                         buffer = "LEFT";
  71                         break;
  72                 case RIGHT:
  73                         buffer = "RIGHT";
  74                         break;
  75                 default:
  76                         buffer = "DIRECTION_ERROR";
  77                         break;
  78         }
  79 }
  80
  81 /**
  82  * Move a point in a direction
  83  */
  84 void Helper::MoveInDirection(int & x, int & y, const Direction & dir, int multiplier)
  85 {
  86         switch (dir)
  87         {
  88                 case UP:
  89                         y -= multiplier;
  90                         break;
  91                 case DOWN:
  92                         y += multiplier;
  93                         break;
  94                 case LEFT:
  95                         x -= multiplier;
  96                         break;
  97                 case RIGHT:
  98                         x += multiplier;
  99                         break;
 100                 default:
 101                         break;
 102         }
 103
 104 }
 105
 106 /**
 107  * Tokenise a string
 108  */
 109 int Helper::Tokenise(std::vector<string> & buffer, std::string & str, char split)
 110 {
 111         string token = "";
 112         for (unsigned int x = 0; x < str.size(); ++x)
 113         {
 114                 if (str[x] == split && token.size() > 0)
 115                 {
 116                         buffer.push_back(token);
 117                         token = "";
 118                 }
 119                 if (str[x] != split)
 120                         token += str[x];
 121         }
 122         if (token.size() > 0)
 123                 buffer.push_back(token);
 124         return buffer.size();
 125 }
 126
 127 /**
 128  * Convert string to integer
 129  */
 130 int Helper::Integer(std::string & fromStr)
 131 {
 132         stringstream s(fromStr);
 133         int result = 0;
 134         s >> result;
 135         return result;
 136 }
 137
 138 /**
 139  * Read in a line from stdin
 140  */
 141 void Helper::ReadLine(std::string & buffer)
 142 {
 143         buffer = "";
 144         for (char c = cin.get(); c != '\n' && cin.good(); c = cin.get())
 145         {
 146                 buffer += c;
 147         }
 148 }
 149
 150 /**
 151  * IMPLEMENTATION of Board FOLLOWS
 152  */
 153
 154 /**
 155  * Constructer for Board
 156  */
 157 Board::Board(int w, int h) : width(w), height(h), board(NULL)
 158 {
 159         //Construct 2D array of P*'s
 160         board = new Piece**[width];
 161         for (int x=0; x < width; ++x)
 162         {
 163                 board[x] = new Piece*[height];
 164                 for (int y=0; y < height; ++y)
 165                         board[x][y] = NULL;
 166         }
 167 }
 168
 169 /**
 170  * Destructor for board
 171  */
 172 Board::~Board()
 173 {
 174         //Destroy the 2D array of P*'s
 175         for (int x=0; x < width; ++x)
 176         {
 177                 for (int y=0; y < height; ++y)
 178                         delete board[x][y];
 179                 delete [] board[x];
 180         }
 181 }
 182
 183 /**
 184  * Retrieves a piece on the Board
 185  * @param x x coordinate
 186  * @param y y coordinate
 187  * @returns A Piece* for the piece, or NULL if there is no piece at the point given
 188  */
 189 Piece * Board::Get(int x, int y) const
 190 {
 191         if (ValidPosition(x, y))
 192                 return board[x][y];
 193         return NULL;
 194 }
 195 /**
 196  * Sets a piece on the Board
 197  * @param x x coordinate
 198  * @param y y coordinate
 199  * @param newPiece
 200  * @param returns newPiece if successful, NULL if not
 201  */
 202 Piece * Board::Set(int x, int y, Piece * newPiece)
 203 {
 204         if (!ValidPosition(x, y))
 205                 return NULL;
 206         board[x][y] = newPiece;
 207         assert(Get(x,y) == newPiece);
 208         return newPiece;
 209 }
 210
 211 /**
 212  * IMPLEMENTATION of Base_Cpp FOLLOWS
 213  */
 214
 215 /**
 216  * Constructor for AI
 217  */
 218 BasicAI::BasicAI() : turn(0), board(NULL), units(), enemyUnits(), colour(NONE), colourStr("")
 219 {
 220         srand(time(NULL));
 221         cin.rdbuf()->pubsetbuf(NULL, 0);
 222         cout.rdbuf()->pubsetbuf(NULL, 0);
 223 }
 224
 225 /**
 226  * Destructor for AI
 227  */
 228 BasicAI::~BasicAI()
 229 {
 230         if (board != NULL)
 231                 delete board;
 232 }
 233
 234
 235 /**
 236  * Setup the AI
 237  * @returns true if successful, false on error
 238  */
 239 bool BasicAI::Setup()
 240 {
 241
 242         cin >> colourStr;
 243
 244
 245         std::string opponentName(""); //opponentName is unused, just read it
 246         cin >> opponentName;
 247
 248         int width = 0; int height = 0;
 249         cin >> width; cin >> height;
 250
 251         while(cin.get() != '\n' && cin.good()); //trim newline
 252
 253         board = new Board(width, height);
 254
 255         if (colourStr == "RED")
 256         {
 257                 colour = RED;
 258                 cout << "FB8sB479B8\nBB31555583\n6724898974\n967B669999\n";
 259         }
 260         else if (colourStr == "BLUE")
 261         {
 262                 colour = BLUE;
 263                 cout << "967B669999\n6724898974\nBB31555583\nFB8sB479B8\n";
 264         }
 265         else
 266                 return false;
 267
 268         return (board != NULL);
 269 }
 270
 271 /**
 272  * Performs a move, including the saving states bits
 273  * @returns true if the game is to continue, false if it is to end
 274  */
 275 bool BasicAI::MoveCycle()
 276 {
 277         //cerr << "BasicAI at MoveCycle()\n";
 278         if (!InterpretResult())
 279                 return false;
 280         if (!ReadBoard())
 281                 return false;
 282         if (!MakeMove())
 283                 return false;
 284
 285         turn++;
 286         return InterpretResult();
 287 }
 288
 289 /**
 290  * Interprets the result of a move. Ignores the first move
 291  * @returns true if successful, false if there was an error
 292  */
 293 bool BasicAI::InterpretResult()
 294 {
 295         //cerr << "BasicAI at InterpretResult()\n";
 296         if (turn == 0)
 297         {
 298                 while (cin.get() != '\n' && cin.good());
 299                 return true;
 300         }
 301
 302
 303         string resultLine; Helper::ReadLine(resultLine);
 304         vector<string> tokens; Helper::Tokenise(tokens, resultLine, ' ');
 305
 306         if (tokens.size() <= 0)
 307         {
 308                 //cerr << "No tokens!\n";
 309                 return false;
 310         }
 311
 312         if (tokens[0] == "QUIT")
 313         {
 314                 return false;
 315         }
 316
 317         if (tokens[0] == "NO_MOVE")
 318         {
 319                 return true;
 320
 321         }
 322
 323         if (tokens.size() < 4)
 324         {
 325                 //cerr << "Only got " << tokens.size() << " tokens\n";
 326                 return false;
 327         }
 328
 329
 330         int x = Helper::Integer(tokens[0]);
 331         int y = Helper::Integer(tokens[1]);
 332
 333
 334
 335         Direction dir = Helper::StrToDir(tokens[2]);
 336         string & outcome = tokens[3];
 337
 338         int x2 = x; int y2 = y; Helper::MoveInDirection(x2,y2,dir);
 339
 340         Piece * attacker = board->Get(x,y);
 341         if (attacker == NULL)
 342         {
 343                 //cerr << "No attacker!\n";
 344                 return false;
 345         }
 346         Piece * defender = board->Get(x2,y2);
 347         if (outcome == "OK")
 348         {
 349                 board->Set(x2,y2, attacker);
 350                 board->Set(x,y,NULL);
 351                 attacker->x = x2; attacker->y = y2;
 352         }
 353         else if (outcome == "KILLS")
 354         {
 355                 if (defender == NULL)
 356                 {
 357                         //cerr << "No defender!\n";
 358                         return false;
 359                 }
 360
 361                 board->Set(x2,y2, attacker);
 362                 board->Set(x,y,NULL);
 363                 attacker->x = x2; attacker->y = y2;
 364
 365                 attacker->rank = Piece::GetRank(tokens[4][0]);
 366                 ForgetUnit(defender);
 367         }
 368         else if (outcome == "DIES")
 369         {
 370                 if (defender == NULL)
 371                 {
 372                         //cerr << "No defender!\n";
 373                         return false;
 374                 }
 375
 376
 377                 board->Set(x,y,NULL);
 378                 defender->rank = Piece::GetRank(tokens[5][0]);
 379                 ForgetUnit(attacker);
 380
 381
 382         }
 383         else if (outcome == "BOTHDIE")
 384         {
 385                 board->Set(x,y,NULL);
 386                 board->Set(x2,y2, NULL);
 387
 388                 ForgetUnit(attacker);
 389                 ForgetUnit(defender);
 390         }
 391         else if (outcome == "FLAG")
 392         {
 393                 //cerr << "BasicAI - Flag was captured, exit!\n";
 394                 return false;
 395         }
 396         else if (outcome == "ILLEGAL")
 397         {
 398                 //cerr << "BasicAI - Illegal move, exit!\n";
 399                 return false;
 400         }
 401
 402         //cerr << "BasicAI finished InterpretResult()\n";
 403         return true;
 404 }
 405
 406 /**
 407  * Performs a random move
 408  * TODO: Overwrite with custom move
 409  * @returns true if a move could be made (including NO_MOVE), false on error
 410  */
 411 bool BasicAI::MakeMove()
 412 {
 413         //cerr << "BasicAI at MakeMove()\n";
 414         if (units.size() <= 0)
 415         {
 416                 //cerr << " No units!\n";
 417                 return false;
 418
 419         }
 420
 421         int index = rand() % units.size();
 422         int startIndex = index;
 423         while (true)
 424         {
 425
 426
 427                 Piece * piece = units[index];
 428                 if (piece != NULL && piece->Mobile())
 429                 {
 430                         int dirIndex = rand() % 4;
 431                         int startDirIndex = dirIndex;
 432                         while (true)
 433                         {
 434                                 int x = piece->x; int y = piece->y;
 435                                 assert(board->Get(x,y) == piece);
 436                                 Helper::MoveInDirection(x,y,(Direction)(dirIndex));
 437                                 if (board->ValidPosition(x,y))
 438                                 {
 439                                         Piece * target = board->Get(x,y);
 440                                         if (target == NULL || (target->colour != piece->colour && target->colour != NONE))
 441                                         {
 442                                                 string dirStr;
 443                                                 Helper::DirToStr((Direction)(dirIndex), dirStr);
 444                                                 cout << piece->x << " " << piece->y << " " << dirStr << "\n";
 445                                                 return true;
 446                                         }
 447                                 }
 448
 449                                 dirIndex = (dirIndex + 1) % 4;
 450                                 if (dirIndex == startDirIndex)
 451                                         break;
 452                         }
 453                 }
 454
 455                 index = (index+1) % (units.size());
 456                 if (index == startIndex)
 457                 {
 458                         cout << "NO_MOVE\n";
 459                         return true;
 460                 }
 461         }
 462         return true;
 463 }
 464
 465 /**
 466  * Reads in the board
 467  * On first turn, sets up Board
 468  * On subsquent turns, takes no action
 469  * @returns true on success, false on error
 470  */
 471 bool BasicAI::ReadBoard()
 472 {
 473         //cerr << "BasicAI at ReadBoard()\n";
 474         for (int y = 0; y < board->Height(); ++y)
 475         {
 476                 string row;
 477                 Helper::ReadLine(row);
 478                 for (unsigned int x = 0; x < row.size(); ++x)
 479                 {
 480                         if (turn == 0)
 481                         {
 482                                 switch (row[x])
 483                                 {
 484                                         case '.':
 485                                                 break;
 486                                         case '#':
 487                                                 board->Set(x,y, new Piece(x,y,Piece::Opposite(colour), UNKNOWN));
 488                                                 enemyUnits.push_back(board->Get(x,y));
 489                                                 break;
 490                                         case '+':
 491                                                 board->Set(x,y, new Piece(x,y,NONE, BOULDER));
 492                                                 break;
 493                                         default:
 494                                                 board->Set(x,y,new Piece(x,y,colour, Piece::GetRank(row[x])));
 495                                                 units.push_back(board->Get(x,y));
 496                                                 break;
 497                                 }
 498                         }
 499                 }
 500         }
 501         return true;
 502 }
 503
 504 /**
 505  * Removes a piece from memory
 506  * @param piece The piece to delete
 507  * @returns true if the piece was actually found
 508  */
 509 bool BasicAI::ForgetUnit(Piece * piece)
 510 {
 511         //cerr << "BasicAI at ForgetUnit()\n";
 512         bool result = false;
 513         vector<Piece*>::iterator i = units.begin();
 514         while (i != units.end())
 515         {
 516                 if ((*i) == piece)
 517                 {
 518                         i = units.erase(i); result = true;
 519                         continue;
 520                 }
 521                 ++i;
 522         }
 523
 524         i = enemyUnits.begin();
 525         while (i != enemyUnits.end())
 526         {
 527                 if ((*i) == piece)
 528                 {
 529                         i = enemyUnits.erase(i); result = true;
 530                         continue;
 531                 }
 532                 ++i;
 533         }
 534
 535
 536         delete piece;
 537         return result;
 538 }
 539
 540
 541 /**
 542  * The main function
 543  * @param argc
 544  * @param argv
 545  * @returns zero on success, non-zero on failure
 546  */
 547 int main(int argc, char ** argv)
 548 {
 549
 550         srand(time(NULL));
 551
 552         BasicAI * basicAI = new BasicAI();
 553         if (basicAI->Setup())
 554         {
 555                 while (basicAI->MoveCycle());
 556         }
 557         delete basicAI;
 558         exit(EXIT_SUCCESS);
 559         return 0;
 560 }