samples/forfax/forfax.cpp

   1 #include "forfax.h"
   2
   3 #include <cstdlib>
   4
   5 #include <sstream>
   6 #include <iostream>
   7 #include <string>
   8 #include <vector>
   9 #include <list>
  10
  11 #include <cmath>
  12
  13 using namespace std;
  14
  15 /**
  16  * Static variables
  17  */
  18
  19 //nothing, boulder, flag, spy, scout, miner, sergeant, lietenant, captain, major, colonel, general, marshal, bomb, error
  20 char  Piece::tokens[] = {'.','+','F','y','s','n','S','L','c','m','C','G','M','B','?'};
  21 int Piece::maxUnits[] = {0,0,1,1,8,5,4,4,4,3,2,1,1,6,0};
  22
  23
  24 int Board::redUnits[] = {0,0,1,1,8,5,4,4,4,3,2,1,1,6,0};
  25 int Board::blueUnits[] = {0,0,1,1,8,5,4,4,4,3,2,1,1,6,0};
  26
  27
  28 /**
  29  * Constructor for a piece
  30  * @param newX - x coord
  31  * @param newY - y coord
  32  * @param newColour - colour
  33  */
  34 Piece::Piece(int newX, int newY,const Colour & newColour)
  35         : x(newX), y(newY), colour(newColour), lastMove(0)
  36 {
  37         minRank[RED] = Piece::FLAG;
  38         minRank[BLUE] = Piece::FLAG;
  39         maxRank[RED] = Piece::BOMB;
  40         maxRank[BLUE] = Piece::BOMB;
  41 }
  42
  43 /**
  44  * Constructor for a piece
  45  * @param newX - x coord
  46  * @param newY - y coord
  47  * @param newColour - colour
  48  * @param rankKnownBy - Colour that knows the piece's rank
  49  * @param fixedRank - Rank the piece has
  50  */
  51 Piece::Piece(int newX, int newY,const Colour & newColour, const Colour & rankKnownBy, const Type & fixedRank)
  52         : x(newX), y(newY), colour(newColour), lastMove(0)
  53 {
  54         if (rankKnownBy == BOTH)
  55         {
  56                 minRank[RED] = fixedRank;
  57                 minRank[BLUE] = fixedRank;
  58                 maxRank[RED] = fixedRank;
  59                 maxRank[BLUE] = fixedRank;
  60         }
  61         else
  62         {
  63                 minRank[rankKnownBy] = fixedRank;
  64                 maxRank[rankKnownBy] = fixedRank;
  65
  66                 Colour opposite = Opposite(rankKnownBy);
  67                 minRank[opposite] = Piece::FLAG;
  68                 maxRank[opposite] = Piece::BOMB;
  69
  70         }
  71
  72 }
  73
  74
  75
  76
  77
  78
  79 /**
  80  * Returns the Piece::Type matching a given character
  81  * @param token - The character to match
  82  * @returns A Piece::Type corresponding to the character, or Piece::ERROR if none was found
  83  */
  84 Piece::Type Piece::GetType(char token)
  85 {
  86         for (int ii=0; ii < Piece::ERROR; ++ii)
  87         {
  88                 if (Piece::tokens[ii] == token)
  89                         return (Type)(ii);
  90         }
  91         return Piece::ERROR;
  92 }
  93
  94 /**
  95  * Constructor for the board
  96  * @param newWidth - width of the board
  97  * @param newHeight - height of the board
  98  *
  99  */
 100 Board::Board(int newWidth, int newHeight) : width(newWidth), height(newHeight), board(NULL), red(), blue()
 101 {
 102         board = new Piece**[width];
 103         for (int x=0; x < width; ++x)
 104         {
 105                 board[x] = new Piece*[height];
 106                 for (int y=0; y < height; ++y)
 107                         board[x][y] = NULL;
 108         }
 109 }
 110
 111 /**
 112  * Destroy the board
 113  */
 114 Board::~Board()
 115 {
 116         for (int x=0; x < width; ++x)
 117         {
 118                 for (int y=0; y < height; ++y)
 119                         delete board[x][y];
 120                 delete [] board[x];
 121         }
 122 }
 123
 124 /**
 125  * Retrieve a piece from the board
 126  * @param x - x coord of the piece
 127  * @param y - y coord of the piece
 128  * @returns Piece* to the piece found at (x,y), or NULL if there was no piece, or the coords were invalid
 129  */
 130 Piece * Board::Get(int x, int y) const
 131 {
 132         if (board == NULL || x < 0 || y < 0 || x > width || y > height)
 133                 return NULL;
 134         return board[x][y];
 135 }
 136
 137 /**
 138  * Add a piece to the board
 139  *      Also updates the red or blue arrays if necessary
 140  * @param x - x coord of the piece
 141  * @param y - y coord of the piece
 142  * @param newPiece - pointer to the piece to add
 143  * @returns newPiece if the piece was successfully added, NULL if it was not
 144  *
 145  */
 146 Piece * Board::Set(int x, int y, Piece * newPiece)
 147 {
 148         if (board == NULL || x < 0 || y < 0 || x > width || y > height)
 149                 return NULL;
 150         board[x][y] = newPiece;
 151
 152         //if (newPiece->GetColour() == Piece::RED)
 153         //      red.push_back(newPiece);
 154         //else if (newPiece->GetColour() == Piece::BLUE)
 155         //      blue.push_back(newPiece);
 156
 157         return newPiece;
 158 }
 159
 160
 161 /**
 162  * Convert a string to a direction
 163  * @param str - The string to convert to a direction
 164  * @returns The equivelent Direction
 165  */
 166 Board::Direction Board::StrToDir(const string & str)
 167 {
 168         if (str == "UP")
 169                 return UP;
 170         else if (str == "DOWN")
 171                 return DOWN;
 172         else if (str == "LEFT")
 173                 return LEFT;
 174         else if (str == "RIGHT")
 175                 return RIGHT;
 176
 177         return NONE;
 178 }
 179
 180 /**
 181  * Convert a Direction to a string
 182  * @param dir - the Direction to convert
 183  * @param str - A buffer string
 184  */
 185 void Board::DirToStr(const Direction & dir, string & str)
 186 {
 187         str.clear();
 188         switch (dir)
 189         {
 190                 case UP:
 191                         str = "UP";
 192                         break;
 193                 case DOWN:
 194                         str = "DOWN";
 195                         break;
 196                 case LEFT:
 197                         str = "LEFT";
 198                         break;
 199                 case RIGHT:
 200                         str = "RIGHT";
 201                         break;
 202                 default:
 203                         str = "NONE";
 204                         break;
 205         }
 206 }
 207
 208 /**
 209  * Moves the co-ords in the specified direction
 210  * @param x - x coord
 211  * @param y - y coord
 212  * @param dir - Direction to move in
 213  * @param multiplier - Number of times to move
 214  *
 215  */
 216 void Board::MoveInDirection(int & x, int & y, const Direction & dir, int multiplier)
 217 {
 218         switch (dir)
 219         {
 220                 case UP:
 221                         y -= multiplier;
 222                         break;
 223                 case DOWN:
 224                         y += multiplier;
 225                         break;
 226                 case LEFT:
 227                         x -= multiplier;
 228                         break;
 229                 case RIGHT:
 230                         x += multiplier;
 231                         break;
 232                 default:
 233                         break;
 234         }
 235 }
 236
 237 /**
 238  * Returns the best direction to move in to get from one point to another
 239  * @param x1 - x coord of point 1
 240  * @param y1 - y coord of point 1
 241  * @param x2 - x coord of point 2
 242  * @param y2 - y coord of point 2
 243  * @returns The best direction to move in
 244  */
 245 Board::Direction Board::DirectionBetween(int x1, int y1, int x2, int y2)
 246 {
 247
 248
 249         double xDist = (x2 - x1);
 250         double yDist = (y2 - y1);
 251         if (abs(xDist) >= abs(yDist))
 252         {
 253                 if (xDist < 0)
 254                         return LEFT;
 255                 else
 256                         return RIGHT;
 257         }
 258         else
 259         {
 260                 if (yDist < 0)
 261                         return UP;
 262                 else
 263                         return DOWN;
 264         }
 265         return NONE;
 266
 267
 268
 269
 270 }
 271
 272 /**
 273  * Searches the board's red and blue arrays for the piece, and removes it
 274  * DOES NOT delete the piece. Calling function should delete piece after calling this function.
 275  * @param forget - The Piece to forget about
 276  * @returns true if the piece was actually found
 277  */
 278 bool Board::ForgetPiece(Piece * forget)
 279 {
 280         if (forget == NULL)
 281                 return false;
 282
 283         vector<Piece*> & in = GetPieces(forget->colour); bool result = false;
 284         for (vector<Piece*>::iterator i=in.begin(); i != in.end(); ++i)
 285         {
 286
 287                 if ((*i) == forget)
 288                 {
 289                         i = in.erase(i);
 290                         result = true;
 291
 292                         continue;
 293                 }
 294
 295
 296         }
 297
 298
 299         return result;
 300 }
 301
 302 /**
 303  * Construct Forfax
 304  */
 305 Forfax::Forfax() : board(NULL), colour(Piece::NONE), strColour("NONE"), turnNumber(0)
 306 {
 307         for (int ii=0; ii <= Piece::BOMB; ++ii)
 308         {
 309                 remainingUnits[ii][Piece::RED][Piece::RED] = Piece::maxUnits[ii];
 310                 remainingUnits[ii][Piece::RED][Piece::BLUE] = Piece::maxUnits[ii];
 311                 remainingUnits[ii][Piece::BLUE][Piece::RED] = Piece::maxUnits[ii];
 312                 remainingUnits[ii][Piece::BLUE][Piece::BLUE] = Piece::maxUnits[ii];
 313
 314
 315         }
 316 }
 317
 318 /**
 319  * Destroy Forfax
 320  */
 321 Forfax::~Forfax()
 322 {
 323         //fprintf(stderr,"Curse you mortal for casting me into the fires of hell!\n");
 324         //Errr...
 325         if (board != NULL)
 326                 delete board;
 327 }
 328
 329 /**
 330  * Calculate the probability that attacker beats defender in combat, from the point of view of a certain player
 331  */
 332
 333 double Forfax::CombatSuccessChance(Piece * attacker, Piece * defender, const Piece::Colour & accordingTo) const
 334 {
 335         double probability=1;
 336         for (Piece::Type aRank = attacker->minRank[accordingTo]; aRank <= attacker->maxRank[accordingTo]; aRank = (Piece::Type)((int)(aRank) + 1))
 337         {
 338                 double lesserRanks; double greaterRanks;
 339                 for (Piece::Type dRank = defender->minRank[accordingTo]; dRank <= defender->maxRank[accordingTo]; dRank = (Piece::Type)((int)(dRank) + 1))
 340                 {
 341                         if (dRank < aRank)
 342                                 lesserRanks++;
 343                         else if (dRank > aRank)
 344                                 greaterRanks++;
 345                         else
 346                         {
 347                                 lesserRanks++; greaterRanks++;
 348                         }
 349                 }
 350                 probability *= lesserRanks/(lesserRanks + greaterRanks);
 351         }
 352         return probability;
 353 }
 354
 355 /**
 356  * Calculate the base score of a move
 357  * @param piece - The Piece to move
 358  * @param dir - The direction in which to move
 359  * @param accordingTo - the colour to use for assumptions
 360  */
 361 double Forfax::MovementBaseScore(Piece * piece, const Board::Direction & dir, const Piece::Colour & accordingTo) const
 362 {
 363         int x2 = piece->x; int y2 = piece->y;
 364         Board::MoveInDirection(x2, y2, dir);
 365
 366         if (board->Get(x2, y2) == NULL)
 367                 return 1;
 368         else if (board->Get(x2, y2)->colour == piece->colour)
 369                 return 0;
 370         else
 371                 return CombatSuccessChance(piece, board->Get(x2, y2), accordingTo);
 372 }
 373
 374 /**
 375  * Calculate the total score of a move according to certain colour
 376  * @param piece - the piece to move
 377  * @param dir - the direction to move in
 378  * @param accordingTo - the colour to use
 379  */
 380 double Forfax::MovementTotalScore(Piece * piece, const Board::Direction & dir, const Piece::Colour & accordingTo) const
 381 {
 382         double base = MovementBaseScore(piece, dir, accordingTo);
 383
 384         if (base == 0)
 385                 return base;
 386
 387
 388         int x = piece->x; int y = piece->y;
 389         Board::MoveInDirection(x, y, dir);
 390         Piece * old = board->Get(x, y);
 391         board->Set(x, y, piece);
 392         board->Set(piece->x, piece->y, NULL);
 393
 394         list<MovementChoice> opponentMoves;
 395         vector<Piece*> & enemies = board->GetPieces(Piece::Opposite(accordingTo));
 396         for (vector<Piece*>::iterator i = enemies.begin(); i != enemies.end(); ++i)
 397         {
 398                 opponentMoves.push_back(MovementChoice((*i), Board::UP, *this,Piece::Opposite(accordingTo)));
 399                 opponentMoves.push_back(MovementChoice((*i), Board::DOWN, *this,Piece::Opposite(accordingTo)));
 400                 opponentMoves.push_back(MovementChoice((*i), Board::LEFT, *this,Piece::Opposite(accordingTo)));
 401                 opponentMoves.push_back(MovementChoice((*i), Board::RIGHT, *this,Piece::Opposite(accordingTo)));
 402         }
 403
 404         opponentMoves.sort();
 405
 406
 407
 408         MovementChoice & best = opponentMoves.back();
 409
 410         board->Set(x, y, old);
 411         board->Set(piece->x, piece->y, piece);
 412
 413         return base / best.score;
 414
 415
 416
 417 }
 418
 419
 420
 421 /**
 422  * Forfax sets himself up
 423  * Really should just make input and output stdin and stdout respectively, but whatever
 424  */
 425 bool Forfax::Setup()
 426 {
 427         //The first line is used to identify Forfax's colour, and the size of the board
 428         //Currently the name of the opponent is ignored
 429
 430         strColour.clear();
 431         string strOpponent; int boardWidth; int boardHeight;
 432
 433         cin >> strColour; cin >> strOpponent; cin >> boardWidth; cin >> boardHeight;
 434         if (cin.get() != '\n')
 435                 return false;
 436
 437         if (strColour == "RED")
 438         {
 439                 colour = Piece::RED;
 440                 cout <<  "FB..........B.\n";
 441                 cout << "BBCM....cccc.C\n";
 442                 cout << "LSGmnsBmSsnsSm\n";
 443                 cout << "sLSBLnLssssnyn\n";
 444         }
 445         else if (strColour == "BLUE")
 446         {
 447                 colour = Piece::BLUE;
 448                 cout << "sLSBLnLssssnyn\n";
 449                 cout << "LSGmnsBmSsnsSm\n";
 450                 cout << "BBCM....cccc.C\n";
 451                 cout <<  "FB..........B.\n";
 452
 453
 454
 455
 456         }
 457         else
 458                 return false;
 459
 460
 461
 462         board = new Board(boardWidth, boardHeight);
 463         return (board != NULL);
 464 }
 465
 466 /**
 467  * Forfax makes a move
 468  *
 469  */
 470 bool Forfax::MakeMove()
 471 {
 472         ++turnNumber;
 473         cerr << "Forfax " << strColour << " making move number " << turnNumber << "...\n";
 474         if (turnNumber == 1)
 475         {
 476                 if (!MakeFirstMove())
 477                 {
 478                         return false;
 479                 }
 480
 481         }
 482         else
 483         {
 484                 if (!InterpretMove())
 485                 {
 486
 487                         return false;
 488                 }
 489
 490
 491                 //Forfax ignores the board state; he only uses the move result lines
 492                 for (int y=0; y < board->Height(); ++y)
 493                 {
 494                         for (int x = 0; x < board->Width(); ++x)
 495                                 cin.get();
 496                         if (cin.get() != '\n')
 497                                 return false;
 498                 }
 499         }
 500
 501         //Make move here
 502
 503         list<MovementTotalChoice> choices;
 504         vector<Piece*> & allies = board->GetPieces(colour);
 505         for (vector<Piece*>::iterator i = allies.begin(); i != allies.end(); ++i)
 506         {
 507                 choices.push_back(MovementTotalChoice((*i), Board::UP, *this, colour));
 508                 choices.push_back(MovementTotalChoice((*i), Board::DOWN, *this, colour));
 509                 choices.push_back(MovementTotalChoice((*i), Board::LEFT, *this, colour));
 510                 choices.push_back(MovementTotalChoice((*i), Board::RIGHT, *this, colour));
 511
 512         }
 513
 514         MovementTotalChoice & choice = choices.back();
 515
 516         string direction; Board::DirToStr(choice.dir, direction);
 517         cerr << "Forfax %s computed optimum move of " << choice.piece->x << " " << choice.piece->y << " " << direction << " [score=" << choice.score << "]\n";
 518         cout << choice.piece->x << " " << choice.piece->y << " " << direction << "\n";
 519
 520
 521         return InterpretMove();
 522
 523
 524 }
 525
 526 bool Forfax::InterpretMove()
 527 {
 528         int x; int y; string direction; string result; int multiplier = 1;
 529
 530         cerr << "Forfax " << strColour << " waiting for movement information...\n";
 531         cin >> x; cin >> y; cin >> direction; cin >> result;
 532         if (cin.peek() != '\n')
 533         {
 534                 cerr << "Forfax " << strColour << " reading multiplier\n";
 535                 stringstream s(result);
 536                 s >> multiplier;
 537                 result.clear();
 538                 cin >> result;
 539         }
 540         if (cin.get() != '\n')
 541         {
 542                 cerr << "Forfax " << strColour << " didn't recieve new line. Very angry.\n";
 543                 cerr << "Read result so far: " << x << " " << y <<  " " << direction << " " << result << " ...\n";
 544                 return false;
 545         }
 546
 547         cerr << "Forfax " << strColour << " interpreting movement result of " << x << " " << y <<  " " << direction << " " << result << " ...\n";
 548
 549
 550         int x2 = x; int y2 = y;
 551         Board::Direction dir = Board::StrToDir(direction);
 552
 553         Board::MoveInDirection(x2, y2, dir, multiplier);
 554
 555         Piece * attacker = board->Get(x, y);
 556         Piece * defender = board->Get(x2, y2);
 557
 558         if (attacker == NULL)
 559                 return false;
 560
 561
 562         Piece::Colour oppositeColour = Piece::Opposite(attacker->colour);
 563         if (attacker->minRank[oppositeColour] == Piece::FLAG)
 564                 attacker->minRank[oppositeColour] = Piece::SPY;
 565         if (attacker->maxRank[oppositeColour] == Piece::BOMB)
 566                 attacker->maxRank[oppositeColour] = Piece::MARSHAL;
 567         if (multiplier > 1)
 568         {
 569                 attacker->maxRank[oppositeColour] = Piece::SCOUT;
 570                 attacker->minRank[oppositeColour] = Piece::SCOUT;
 571         }
 572
 573
 574
 575
 576
 577         if (result == "OK")
 578         {
 579                 if (defender != NULL)
 580                         return false;
 581                 board->Set(x2, y2, attacker);
 582                 board->Set(x, y, NULL);
 583                 attacker->x = x2;
 584                 attacker->y = y2;
 585         }
 586         else if (result == "KILLS")
 587         {
 588                 if (defender == NULL || defender->colour == attacker->colour)
 589                         return false;
 590
 591
 592
 593
 594                 board->Set(x2, y2, attacker);
 595                 board->Set(x, y, NULL);
 596                 attacker->x = x2;
 597                 attacker->y = y2;
 598
 599                 if (attacker->minRank[oppositeColour] < defender->maxRank[oppositeColour])
 600                         attacker->minRank[oppositeColour] = defender->maxRank[oppositeColour];
 601
 602
 603                 if (!board->ForgetPiece(defender))
 604                         return false;
 605                 delete defender;
 606
 607         }
 608         else if (result == "DIES")
 609         {
 610
 611                 if (defender == NULL || defender->colour == attacker->colour)
 612                         return false;
 613 cerr << "Forfax - Unit " << attacker << " dies \n";
 614                 if (!board->ForgetPiece(attacker))
 615                         return false;
 616                 delete attacker;
 617
 618                 board->Set(x, y, NULL);
 619         }
 620         else if (result == "BOTHDIE")
 621         {
 622                 if (defender == NULL || defender->colour == attacker->colour)
 623                         return false;
 624                 if (board->ForgetPiece(attacker) == false)
 625                         return false;
 626                 if (board->ForgetPiece(defender) == false)
 627                         return false;
 628                 delete attacker;
 629                 delete defender;
 630                 board->Set(x2, y2, NULL);
 631                 board->Set(x, y, NULL);
 632         }
 633         else if (result == "VICTORY")
 634         {
 635                 return false;
 636         }
 637         return true;
 638 }
 639
 640 /**
 641  * First move only
 642  *
 643  */
 644 bool Forfax::MakeFirstMove()
 645 {
 646         if (colour == Piece::RED)
 647         {
 648                 string derp;
 649                 cin >> derp;
 650                 if (derp != "START")
 651                         return false;
 652                 if (cin.get() != '\n')
 653                         return false;
 654         }
 655         else
 656         {
 657                 //TODO: Fix hack where BLUE ignores RED's first move
 658                 while (cin.get() != '\n');
 659         }
 660
 661         for (int y=0; y < board->Height(); ++y)
 662         {
 663                 for (int x = 0; x < board->Width(); ++x)
 664                 {
 665                         char c = cin.get();
 666                         switch (c)
 667                         {
 668                                 case '.':
 669                                         break;
 670                                 case '+':
 671                                         board->Set(x, y, new Piece(x, y, Piece::NONE, Piece::BOTH, Piece::BOULDER));
 672                                         break;
 673                                 case '#':
 674                                 case '*':
 675                                 {
 676                                         Piece * toAdd = new Piece(x, y, Piece::Opposite(colour));
 677                                         board->Set(x, y, toAdd);
 678                                         board->GetPieces(toAdd->colour).push_back(toAdd);
 679                                         break;
 680                                 }
 681                                 default:
 682                                 {
 683                                         Piece::Type type = Piece::GetType(c);
 684                                         Piece * toAdd = new Piece(x, y, colour, colour, type);
 685                                         board->Set(x, y, toAdd);
 686                                         board->GetPieces(toAdd->colour).push_back(toAdd);
 687                                         break;
 688                                 }
 689                         }
 690                 }
 691                 if (cin.get() != '\n')
 692                         return false;
 693         }
 694
 695         return true;
 696 }
 697
 698 //EOF
 699