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 [email protected] or [email protected]
   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
 337         //We might want to actually check for the multiplier in the sample agents! 20/12/11
 338         unsigned int outIndex = 3;
 339         int multiplier = atoi(tokens[outIndex].c_str());
 340         if (multiplier == 0)
 341                 multiplier = 1;
 342         else
 343                 outIndex += 1;
 344
 345
 346
 347         string & outcome = tokens[outIndex];
 348
 349
 350         int x2 = x; int y2 = y; Helper::MoveInDirection(x2,y2,dir, multiplier);
 351
 352         Piece * attacker = board->Get(x,y);
 353         if (attacker == NULL)
 354         {
 355                 //cerr << "No attacker!\n";
 356                 return false;
 357         }
 358         Piece * defender = board->Get(x2,y2);
 359         if (outcome == "OK")
 360         {
 361                 board->Set(x2,y2, attacker);
 362                 board->Set(x,y,NULL);
 363                 attacker->x = x2; attacker->y = y2;
 364         }
 365         else if (outcome == "KILLS")
 366         {
 367                 if (defender == NULL)
 368                 {
 369                         //cerr << "No defender!\n";
 370                         return false;
 371                 }
 372                 if (tokens.size() < outIndex+2)
 373                         return false;
 374
 375
 376                 board->Set(x2,y2, attacker);
 377                 board->Set(x,y,NULL);
 378                 attacker->x = x2; attacker->y = y2;
 379                 attacker->rank = Piece::GetRank(tokens[outIndex+1][0]);
 380                 ForgetUnit(defender);
 381         }
 382         else if (outcome == "DIES")
 383         {
 384                 if (defender == NULL)
 385                 {
 386                         //cerr << "No defender!\n";
 387                         return false;
 388                 }
 389                 if (tokens.size() < outIndex+3)
 390                         return false;
 391
 392
 393                 board->Set(x,y,NULL);
 394                 defender->rank = Piece::GetRank(tokens[outIndex+2][0]);
 395                 ForgetUnit(attacker);
 396
 397
 398         }
 399         else if (outcome == "BOTHDIE")
 400         {
 401                 board->Set(x,y,NULL);
 402                 board->Set(x2,y2, NULL);
 403
 404                 ForgetUnit(attacker);
 405                 ForgetUnit(defender);
 406         }
 407         else if (outcome == "FLAG")
 408         {
 409                 //cerr << "BasicAI - Flag was captured, exit!\n";
 410                 return false;
 411         }
 412         else if (outcome == "ILLEGAL")
 413         {
 414                 //cerr << "BasicAI - Illegal move, exit!\n";
 415                 return false;
 416         }
 417
 418         //cerr << "BasicAI finished InterpretResult()\n";
 419         return true;
 420 }
 421
 422 /**
 423  * Performs a random move
 424  * TODO: Overwrite with custom move
 425  * @returns true if a move could be made (including NO_MOVE), false on error
 426  */
 427 bool BasicAI::MakeMove()
 428 {
 429         //cerr << "BasicAI at MakeMove()\n";
 430         if (units.size() <= 0)
 431         {
 432                 //cerr << " No units!\n";
 433                 return false;
 434
 435         }
 436
 437         int index = rand() % units.size();
 438         int startIndex = index;
 439         while (true)
 440         {
 441
 442
 443                 Piece * piece = units[index];
 444                 if (piece != NULL && piece->Mobile())
 445                 {
 446                         int dirIndex = rand() % 4;
 447                         int startDirIndex = dirIndex;
 448                         while (true)
 449                         {
 450                                 int x = piece->x; int y = piece->y;
 451                                 assert(board->Get(x,y) == piece);
 452                                 Helper::MoveInDirection(x,y,(Direction)(dirIndex));
 453                                 if (board->ValidPosition(x,y))
 454                                 {
 455                                         Piece * target = board->Get(x,y);
 456                                         if (target == NULL || (target->colour != piece->colour && target->colour != NONE))
 457                                         {
 458                                                 string dirStr;
 459                                                 Helper::DirToStr((Direction)(dirIndex), dirStr);
 460                                                 cout << piece->x << " " << piece->y << " " << dirStr << "\n";
 461                                                 return true;
 462                                         }
 463                                 }
 464
 465                                 dirIndex = (dirIndex + 1) % 4;
 466                                 if (dirIndex == startDirIndex)
 467                                         break;
 468                         }
 469                 }
 470
 471                 index = (index+1) % (units.size());
 472                 if (index == startIndex)
 473                 {
 474                         cout << "NO_MOVE\n";
 475                         return true;
 476                 }
 477         }
 478         return true;
 479 }
 480
 481 /**
 482  * Reads in the board
 483  * On first turn, sets up Board
 484  * On subsquent turns, takes no action
 485  * @returns true on success, false on error
 486  */
 487 bool BasicAI::ReadBoard()
 488 {
 489         //cerr << "BasicAI at ReadBoard()\n";
 490         for (int y = 0; y < board->Height(); ++y)
 491         {
 492                 string row;
 493                 Helper::ReadLine(row);
 494                 for (unsigned int x = 0; x < row.size(); ++x)
 495                 {
 496                         if (turn == 0)
 497                         {
 498                                 switch (row[x])
 499                                 {
 500                                         case '.':
 501                                                 break;
 502                                         case '#':
 503                                                 board->Set(x,y, new Piece(x,y,Piece::Opposite(colour), UNKNOWN));
 504                                                 enemyUnits.push_back(board->Get(x,y));
 505                                                 break;
 506                                         case '+':
 507                                                 board->Set(x,y, new Piece(x,y,NONE, BOULDER));
 508                                                 break;
 509                                         default:
 510                                                 board->Set(x,y,new Piece(x,y,colour, Piece::GetRank(row[x])));
 511                                                 units.push_back(board->Get(x,y));
 512                                                 break;
 513                                 }
 514                         }
 515                 }
 516         }
 517         return true;
 518 }
 519
 520 /**
 521  * Removes a piece from memory
 522  * @param piece The piece to delete
 523  * @returns true if the piece was actually found
 524  */
 525 bool BasicAI::ForgetUnit(Piece * piece)
 526 {
 527         //cerr << "BasicAI at ForgetUnit()\n";
 528         bool result = false;
 529         vector<Piece*>::iterator i = units.begin();
 530         while (i != units.end())
 531         {
 532                 if ((*i) == piece)
 533                 {
 534                         i = units.erase(i); result = true;
 535                         continue;
 536                 }
 537                 ++i;
 538         }
 539
 540         i = enemyUnits.begin();
 541         while (i != enemyUnits.end())
 542         {
 543                 if ((*i) == piece)
 544                 {
 545                         i = enemyUnits.erase(i); result = true;
 546                         continue;
 547                 }
 548                 ++i;
 549         }
 550
 551
 552         delete piece;
 553         return result;
 554 }
 555
 556
 557 /**
 558  * The main function
 559  * @param argc
 560  * @param argv
 561  * @returns zero on success, non-zero on failure
 562  */
 563 int main(int argc, char ** argv)
 564 {
 565
 566         srand(time(NULL));
 567
 568         BasicAI * basicAI = new BasicAI();
 569         if (basicAI->Setup())
 570         {
 571                 while (basicAI->MoveCycle());
 572         }
 573         delete basicAI;
 574         exit(EXIT_SUCCESS);
 575         return 0;
 576 }