samples/forfax/forfax.cpp

   1 /**
   2  * "forfax", a sample Stratego AI for the UCC Programming Competition 2012
   3  * Implementations of classes Piece, Board and Forfax
   4  * @author Sam Moore (matches) [SZM]
   5  * @website http://matches.ucc.asn.au/stratego
   6  * @email [email protected] or [email protected]
   7  * @git git.ucc.asn.au/progcomp2012.git
   8  */
   9
  10 #include "forfax.h"
  11
  12 #include <cstdlib>
  13 #include <sstream>
  14 #include <iostream>
  15 #include <string>
  16 #include <vector>
  17 #include <list>
  18 #include <cmath>
  19
  20 //#define DEBUG
  21
  22 using namespace std;
  23
  24
  25
  26
  27 /**
  28  * The characters used to represent various pieces
  29  * NOTHING, BOULDER, FLAG, SPY, SCOUT, MINER, SERGEANT, LIETENANT, CAPTAIN, MAJOR, COLONEL, GENERAL, MARSHAL, BOMB, ERROR
  30  */
  31
  32 char  Piece::tokens[] = {'.','+','F','y','s','n','S','L','c','m','C','G','M','B','?'};
  33
  34
  35 /**
  36  * The number of units remaining for each colour
  37  * Accessed by [COLOUR][TYPE]
  38  * COLOUR: RED, BLUE
  39  * TYPE: NOTHING, BOULDER, FLAG, SPY, SCOUT, MINER, SERGEANT, LIETENANT, CAPTAIN, MAJOR, COLONEL, GENERAL, MARSHAL, BOMB, ERROR
  40  */
  41 int Forfax::remainingUnits[][15] = {{0,0,1,1,8,5,4,4,4,3,2,1,1,6,0},{0,0,1,1,8,5,4,4,4,3,2,1,1,6,0}};
  42
  43
  44
  45
  46 /**
  47  * Constructor for a piece of unknown rank
  48  * @param newX - x coord
  49  * @param newY - y coord
  50  * @param newColour - colour
  51  */
  52 Piece::Piece(int newX, int newY,const Colour & newColour)
  53         : x(newX), y(newY), colour(newColour), minRank(Piece::FLAG), maxRank(Piece::BOMB), lastMove(0), lastx(newX), lasty(newY)
  54 {
  55
  56 }
  57
  58 /**
  59  * Constructor for a piece of known rank
  60  * @param newX - x coord
  61  * @param newY - y coord
  62  * @param newColour - colour
  63  * @param fixedRank - rank of the new piece
  64  */
  65 Piece::Piece(int newX, int newY,const Colour & newColour, const Type & fixedRank)
  66         : x(newX), y(newY), colour(newColour), minRank(fixedRank), maxRank(fixedRank), lastMove(0),  lastx(newX), lasty(newY)
  67 {
  68
  69
  70 }
  71
  72
  73
  74
  75
  76
  77 /**
  78  * HELPER - Returns the Piece::Type matching a given character
  79  * @param token - The character to match
  80  * @returns A Piece::Type corresponding to the character, or Piece::ERROR if none was found
  81  */
  82 Piece::Type Piece::GetType(char token)
  83 {
  84         for (int ii=0; ii < Piece::ERROR; ++ii)
  85         {
  86                 if (Piece::tokens[ii] == token)
  87                         return (Type)(ii);
  88         }
  89         return Piece::ERROR;
  90 }
  91
  92 /**
  93  * Constructor for the board
  94  * @param newWidth - width of the board
  95  * @param newHeight - height of the board
  96  *
  97  */
  98 Board::Board(int newWidth, int newHeight) : width(newWidth), height(newHeight), board(NULL), red(), blue()
  99 {
 100         //Construct 2D array of Piece*'s
 101         board = new Piece**[width];
 102         for (int x=0; x < width; ++x)
 103         {
 104                 board[x] = new Piece*[height];
 105                 for (int y=0; y < height; ++y)
 106                         board[x][y] = NULL;
 107         }
 108 }
 109
 110 /**
 111  * Destroy the board
 112  */
 113 Board::~Board()
 114 {
 115         //Destroy the 2D array of Piece*'s
 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 at specified coordinates
 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 (ie invalid coordinates specified)
 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  * HELPER - Convert a string to a direction
 163  * @param str - The string to convert to a direction
 164  * @returns The equivalent 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  * HELPER - Convert a Direction to a string
 182  * @param dir - the Direction to convert
 183  * @param str - A buffer string, which will contain the string representation of the Direction once this function returns.
 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  * HELPER - Translates the given coordinates in a 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  * HELPER - 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  * HELPER - Returns the number of moves between two points
 274  * @param x1 x coordinate of the first point
 275  * @param y1 y coordinate of the first point
 276  * @param x2 x coordinate of the second point
 277  * @param y2 y coordinate of the second point
 278  * @returns The number of moves taken to progress from (x1, y1) to (x2, y2), assuming no obstacles
 279  */
 280 int Board::NumberOfMoves(int x1, int y1, int x2, int y2)
 281 {
 282         return (abs(x2 - x1) + abs(y2 - y1)); //Pieces can't move diagonally, so this is pretty straight forward
 283 }
 284
 285 /**
 286  * Searches the board's red and blue arrays for the piece, and removes it
 287  * DOES NOT delete the piece. Calling function should delete piece after calling this function.
 288  * @param forget - The Piece to forget about
 289  * @returns true if the piece was actually found
 290  */
 291 bool Board::ForgetPiece(Piece * forget)
 292 {
 293         if (forget == NULL)
 294                 return false;
 295
 296         vector<Piece*> & in = GetPieces(forget->colour); bool result = false;
 297         vector<Piece*>::iterator i=in.begin();
 298         while (i != in.end())
 299         {
 300
 301                 if ((*i) == forget)
 302                 {
 303                         i = in.erase(i);
 304                         result = true;
 305
 306                         continue;
 307                 }
 308                 ++i;
 309
 310         }
 311
 312
 313         return result;
 314 }
 315
 316 /**
 317  * Gets the closest Piece of a specified colour to a point
 318  * @param x The x coordinate of the point
 319  * @param y The y coordinate of the point
 320  * @param colour The colour that the piece must match (may be Piece::BOTH to match either colour)
 321  * @returns Piece* pointing to the closest piece of a matching colour, NULL if no piece found
 322  */
 323 Piece * Board::GetClosest(int x, int y, const Piece::Colour & colour) const
 324 {
 325         if (x < 0 || y < 0 || x >= width || y >= height)
 326                 return NULL;
 327
 328         for (int dist = 0; dist < max<int>(width, height); ++dist)
 329         {
 330
 331                 for (int yy = y-dist; yy <= y+dist; ++yy)
 332                 {
 333                         Piece * get = Get(x+dist, y);
 334                         if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
 335                                 return get;
 336                 }
 337                 for (int yy = y-dist; yy <= y+dist; ++yy)
 338                 {
 339                         Piece * get = Get(x-dist, y);
 340                         if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
 341                                 return get;
 342                 }
 343                 for (int xx = x-dist; xx <= x+dist; ++xx)
 344                 {
 345                         Piece * get = Get(xx, y+dist);
 346                         if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
 347                                 return get;
 348                 }
 349                 for (int xx = x-dist; xx <= y+dist; ++xx)
 350                 {
 351                         Piece * get = Get(xx, y-dist);
 352                         if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
 353                                 return get;
 354                 }
 355
 356         }
 357
 358         return NULL;
 359
 360
 361
 362
 363 }
 364
 365 /**
 366  * Construct the Forfax AI
 367  */
 368 Forfax::Forfax() : board(NULL), colour(Piece::NONE), strColour("NONE"), turnNumber(0)
 369 {
 370         //By default, Forfax knows nothing; the main function in main.cpp calls Forfax's initialisation functions
 371         srand(time(NULL));
 372 }
 373
 374 /**
 375  * Destroy Forfax
 376  */
 377 Forfax::~Forfax()
 378 {
 379         //fprintf(stderr,"Curse you mortal for casting me into the fires of hell!\n");
 380         //Errr...
 381         if (board != NULL)
 382                 delete board;
 383 }
 384
 385 /**
 386  * Calculate the probability that attacker beats defender in combat
 387  * @param attacker The attacking piece
 388  * @param defender The defending piece
 389  * @returns A double between 0 and 1 indicating the probability of success
 390  */
 391
 392 double Forfax::CombatSuccessChance(Piece * attacker, Piece * defender) const
 393 {
 394         double probability=1;
 395         for (Piece::Type aRank = attacker->minRank; aRank <= attacker->maxRank; aRank = (Piece::Type)((int)(aRank) + 1))
 396         {
 397                 double lesserRanks=0; double greaterRanks=0;
 398                 for (Piece::Type dRank = defender->minRank; dRank <= defender->maxRank; dRank = (Piece::Type)((int)(dRank) + 1))
 399                 {
 400                         if (dRank < aRank)
 401                                 lesserRanks += remainingUnits[defender->colour][(int)(dRank)];
 402                         else if (dRank > aRank)
 403                                 greaterRanks += remainingUnits[defender->colour][(int)(dRank)];
 404                         else
 405                         {
 406                                 lesserRanks++; greaterRanks++;
 407                         }
 408                 }
 409                 probability *= lesserRanks/(lesserRanks + greaterRanks);
 410         }
 411         return probability;
 412 }
 413
 414 /**
 415  * Calculate the score of a move
 416  * TODO: Alter this to make it better
 417  * @param piece - The Piece to move
 418  * @param dir - The direction in which to move
 419  * @returns a number between 0 and 1, indicating how worthwhile the move is
 420  */
 421 double Forfax::MovementScore(Piece * piece, const Board::Direction & dir) const
 422 {
 423         assert(piece != NULL);
 424
 425
 426         int x2 = piece->x; int y2 = piece->y;
 427         Board::MoveInDirection(x2, y2, dir);
 428
 429
 430
 431         double basevalue;
 432         if (!board->ValidPosition(x2, y2) || !piece->Mobile())
 433         {
 434
 435                 basevalue = 0; //No point attempting to move immobile units, or moving off the edges of the board
 436         }
 437         else if (board->Get(x2, y2) == NULL)
 438         {
 439                 //If the position is empty...
 440                 Piece * closestEnemy = board->GetClosest(x2, y2, Piece::Opposite(piece->colour));
 441                 if (closestEnemy == NULL)
 442                 {
 443                         basevalue = 0.05*IntrinsicWorth(x2, y2); //Should never get this unless there are no enemies left
 444                 }
 445                 else
 446                 {
 447                         //Allocate score based on score of Combat with nearest enemy to the target square, decrease with distance between target square and the enemy
 448                         basevalue = 0.95*CombatScore(closestEnemy->x, closestEnemy->y, piece) - 0.2*(double)((double)(Board::NumberOfMoves(closestEnemy->x, closestEnemy->y, x2, y2))/(double)((max<int>(board->Width(), board->Height()))));
 449                 }
 450
 451
 452         }
 453         else if (board->Get(x2, y2)->colour != Piece::Opposite(piece->colour))
 454         {
 455                 basevalue = 0; //The position is occupied by an ally, and so its pointless to try and move there
 456         }
 457         else
 458         {
 459                 basevalue = CombatScore(x2, y2, piece); //The position is occupied by an enemy; compute combat score
 460         }
 461
 462         if (basevalue > 0)
 463         {
 464                 //Hack which decreases score for units that moved recently
 465                 //Does not decrease below a threshold (so that at the start of the game units will actually move!)
 466                 double oldValue = basevalue;
 467                 basevalue -= (double)(1.0/((double)(1.0 + (turnNumber - piece->lastMove))));
 468                 if (basevalue < oldValue/1000.0)
 469                         basevalue = oldValue/1000.0;
 470         }
 471
 472
 473         if (x2 == piece->lastx && y2 == piece->lasty) //Hack which decreases score for backtracking moves
 474                 basevalue = basevalue/1.5;
 475
 476         if (rand() % 10 == 0) //Hack which introduces some randomness by boosting one in every 10 scores
 477                 basevalue *= 4;
 478         if (basevalue > 1)
 479                 basevalue = 1;
 480         return basevalue;
 481 }
 482
 483
 484 /**
 485  * Initialisation for Forfax
 486  * Reads information from stdin about the board, and Forfax's colour. Initialises board, and prints appropriate setup to stdout.
 487  * @returns true if Forfax was successfully initialised, false otherwise.
 488  */
 489 Forfax::Status Forfax::Setup()
 490 {
 491         //The first line is used to identify Forfax's colour, and the size of the board
 492         //Currently the name of the opponent is ignored.
 493
 494         //Forfax then responds with a setup.
 495         //Forfax only uses one of two setups, depending on what colour he was assigned.
 496
 497
 498         //Variables to store information read from stdin
 499         strColour.clear();
 500         string strOpponent; int boardWidth; int boardHeight;
 501
 502         cin >> strColour; cin >> strOpponent; cin >> boardWidth; cin >> boardHeight;
 503         if (cin.get() != '\n')
 504                 return NO_NEWLINE;
 505
 506         //Determine Forfax's colour and respond with an appropriate setup
 507         if (strColour == "RED")
 508         {
 509                 colour = Piece::RED;
 510                 cout <<  "FBmSsnsnBn\n";
 511                 cout << "BBCMccccyC\n";
 512                 cout << "LSGmnsBsSm\n";
 513                 cout << "sLSBLnLsss\n";
 514         }
 515         else if (strColour == "BLUE")
 516         {
 517                 colour = Piece::BLUE;
 518                 cout << "sLSBLnLsss\n";
 519                 cout << "LSGmnsBsSm\n";
 520                 cout << "BBCMccccyC\n";
 521                 cout <<  "FBmSsnsnBn\n";
 522         }
 523         else
 524                 return INVALID_QUERY;
 525
 526
 527         //Create the board
 528         //NOTE: At this stage, the board is still empty. The board is filled on Forfax's first turn
 529         //      The reason for this is because the opponent AI has not placed pieces yet, so there is no point adding only half the pieces to the board
 530
 531         board = new Board(boardWidth, boardHeight);
 532         if (board == NULL)
 533                 return BOARD_ERROR;
 534         return OK;
 535 }
 536
 537 /**
 538  * Make a single move
 539  * 1. Read result of previous move from stdin (or "START" if Forfax is RED and it is the very first move)
 540  * 2. Read in board state from stdin (NOTE: Unused - all information needed to maintain board state is in 1. and 4.)
 541  *      TODO: Considering removing this step from the protocol? (It makes debugging annoying because I have to type a lot more!)
 542  * 3. Print desired move to stdout
 543  * 4. Read in result of chosen move from stdin
 544  * @returns true if everything worked, false if there was an error or unexpected query
 545  */
 546 Forfax::Status Forfax::MakeMove()
 547 {
 548         ++turnNumber;
 549
 550         if (turnNumber == 1)
 551         {
 552                 Status firstMove = MakeFirstMove();
 553                 if (firstMove != OK)
 554                         return firstMove;
 555         }
 556         else
 557         {
 558                 //Read and interpret the result of the previous move
 559                 Status interpret = InterpretMove();
 560                 if (interpret != OK) {return interpret;}
 561
 562                 //Forfax ignores the board state; he only uses the move result lines
 563                 #ifndef DEBUG
 564                 for (int y=0; y < board->Height(); ++y)
 565                 {
 566                         for (int x = 0; x < board->Width(); ++x)
 567                                 cin.get();
 568                         if (cin.get() != '\n')
 569                                 return NO_NEWLINE;
 570                 }
 571                 #endif //DEBUG
 572
 573         }
 574
 575         //Now compute the best move
 576         // 1. Construct list of all possible moves
 577         //      As each move is added to the list, a score is calculated for that move.
 578         //      WARNING: This is the "tricky" part!
 579         // 2. Sort the moves based on their score
 580         // 3. Simply use the highest scoring move!
 581
 582         list<MovementChoice> choices;
 583         vector<Piece*> & allies = board->GetPieces(colour);
 584         for (vector<Piece*>::iterator i = allies.begin(); i != allies.end(); ++i)
 585         {
 586                 choices.push_back(MovementChoice((*i), Board::UP, *this));
 587                 choices.push_back(MovementChoice((*i), Board::DOWN, *this));
 588                 choices.push_back(MovementChoice((*i), Board::LEFT, *this));
 589                 choices.push_back(MovementChoice((*i), Board::RIGHT, *this));
 590
 591         }
 592
 593         choices.sort(); //Actually sort the choices!!!
 594         MovementChoice & choice = choices.back(); //The best one is at the back, because sort() sorts the list in ascending order
 595
 596
 597
 598         //Convert information about the move into a printable form
 599         string direction;  Board::DirToStr(choice.dir, direction);
 600
 601         //Print chosen move to stdout
 602         cout << choice.piece->x << " " << choice.piece->y << " " << direction << "\n";
 603
 604
 605
 606
 607
 608
 609         //Interpret the result of the chosen move
 610         return InterpretMove();
 611
 612
 613
 614 }
 615
 616 /**
 617  * Reads and interprets the result of a move
 618  * Reads information from stdin
 619  * @returns true if the result was successfully interpreted, false if there was a contradiction or error
 620  */
 621 Forfax::Status Forfax::InterpretMove()
 622 {
 623         //Variables to store move information
 624         int x; int y; string direction; string result = ""; int multiplier = 1; int attackerVal = (int)(Piece::BOMB); int defenderVal = (int)(Piece::BOMB);
 625
 626
 627         //Read in information from stdin
 628         cin >> x; cin >> y; cin >> direction; cin >> result;
 629
 630         //If necessary, read in the ranks of involved pieces (this happens if the outcome was DIES or KILLS or BOTHDIE)
 631         if (cin.peek() != '\n')
 632         {
 633                 string buf = "";
 634                 stringstream s(buf);
 635                 cin >> buf;
 636                 s.clear(); s.str(buf);
 637                 s >> attackerVal;
 638
 639
 640                 buf.clear();
 641                 cin >> buf;
 642                 s.clear(); s.str(buf);
 643                 s >> defenderVal;
 644
 645
 646         }
 647
 648         //TODO: Deal with move multipliers somehow (when a scout moves more than one space)
 649
 650         //Check that the line ends where expected...
 651         if (cin.get() != '\n')
 652         {
 653                 return NO_NEWLINE;
 654         }
 655
 656
 657         //Convert printed ranks into internal Piece::Type ranks
 658         Piece::Type attackerRank = Piece::Type(Piece::BOMB - attackerVal);
 659         Piece::Type defenderRank = Piece::Type(Piece::BOMB - defenderVal);
 660
 661
 662
 663         //Work out the square moved into
 664         int x2 = x; int y2 = y;
 665         Board::Direction dir = Board::StrToDir(direction);
 666
 667         Board::MoveInDirection(x2, y2, dir, multiplier);
 668
 669
 670         //Determine the attacker and defender (if it exists)
 671         Piece * attacker = board->Get(x, y);
 672         Piece * defender = board->Get(x2, y2);
 673
 674
 675         //If ranks were supplied, update the known ranks of the involved pieces
 676         if (attackerRank != Piece::NOTHING && attacker != NULL)
 677         {
 678                 //assert(attacker->minRank <= attackerRank && attacker->maxRank >= attackerRank);
 679                 attacker->minRank = attackerRank;
 680                 attacker->maxRank = attackerRank;
 681         }
 682         if (defenderRank != Piece::NOTHING && defender != NULL)
 683         {
 684                 //assert(defender->minRank <= defenderRank && defender->maxRank >= defenderRank);
 685                 defender->minRank = defenderRank;
 686                 defender->maxRank = defenderRank;
 687
 688         }
 689
 690         //There should always be an attacking piece (but not necessarily a defender)
 691         if (attacker == NULL)
 692                 return EXPECTED_ATTACKER;
 693
 694
 695         attacker->lastMove = turnNumber; //Update stats of attacking piece (last move)
 696
 697         //Eliminate certain ranks from the possibilities for the piece based on its movement
 698         //(This is useful if the piece was an enemy piece)
 699         if (attacker->minRank == Piece::FLAG)
 700                 attacker->minRank = Piece::SPY;
 701         if (attacker->maxRank == Piece::BOMB)
 702                 attacker->maxRank = Piece::MARSHAL;
 703         if (multiplier > 1)
 704         {
 705                 attacker->maxRank = Piece::SCOUT;
 706                 attacker->minRank = Piece::SCOUT;
 707         }
 708
 709
 710
 711
 712         //Now look at the result of the move (I wish you could switch strings in C++)
 713
 714
 715         //The move was uneventful (attacker moved into empty square)
 716         if (result == "OK")
 717         {
 718                 if (defender != NULL)
 719                         return UNEXPECTED_DEFENDER;
 720
 721                 //Update board and piece
 722                 board->Set(x2, y2, attacker);
 723                 board->Set(x, y, NULL);
 724                 attacker->lastx = attacker->x;
 725                 attacker->lasty = attacker->y;
 726                 attacker->x = x2;
 727                 attacker->y = y2;
 728         }
 729         else if (result == "KILLS") //The attacking piece killed the defending piece
 730         {
 731                 if (defender == NULL || defender->colour == attacker->colour)
 732                         return COLOUR_MISMATCH;
 733
 734
 735
 736
 737                 board->Set(x2, y2, attacker);
 738                 board->Set(x, y, NULL);
 739                 attacker->lastx = attacker->x;
 740                 attacker->lasty = attacker->y;
 741                 attacker->x = x2;
 742                 attacker->y = y2;
 743
 744                 remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
 745
 746
 747                 if (!board->ForgetPiece(defender))
 748                         return NO_DEFENDER;
 749                 delete defender;
 750
 751         }
 752         else if (result == "DIES") //The attacking piece was killed by the defending piece
 753         {
 754
 755                 if (defender == NULL || defender->colour == attacker->colour)
 756                         return COLOUR_MISMATCH;
 757
 758                 remainingUnits[(int)(attacker->colour)][(int)(attackerRank)]--;
 759
 760                 if (!board->ForgetPiece(attacker))
 761                         return NO_ATTACKER;
 762                 delete attacker;
 763
 764                 board->Set(x, y, NULL);
 765         }
 766         else if (result == "BOTHDIE") //Both attacking and defending pieces died
 767         {
 768                 if (defender == NULL || defender->colour == attacker->colour)
 769                         return COLOUR_MISMATCH;
 770
 771                 remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
 772                 remainingUnits[(int)(attacker->colour)][(int)(attackerRank)]--;
 773
 774                 if (board->ForgetPiece(attacker) == false)
 775                         return NO_ATTACKER;
 776                 if (board->ForgetPiece(defender) == false)
 777                         return NO_DEFENDER;
 778                 delete attacker;
 779                 delete defender;
 780                 board->Set(x2, y2, NULL);
 781                 board->Set(x, y, NULL);
 782         }
 783         else if (result == "VICTORY") //The attacking piece captured a flag
 784         {
 785                 return VICTORY;
 786
 787         }
 788         return OK;
 789 }
 790
 791 /**
 792  * Forfax's first move
 793  * Sets the state of the board
 794  * @returns true if the board was successfully read, false if an error occurred.
 795  *
 796  */
 797 Forfax::Status Forfax::MakeFirstMove()
 798 {
 799         if (colour == Piece::RED)
 800         {
 801                 string derp;
 802                 cin >> derp;
 803                 if (derp != "START")
 804                         return INVALID_QUERY;
 805                 if (cin.get() != '\n')
 806                         return NO_NEWLINE;
 807         }
 808         else
 809         {
 810                 //TODO: Fix hack where BLUE ignores RED's first move
 811                 while (cin.get() != '\n');
 812         }
 813
 814         for (int y=0; y < board->Height(); ++y)
 815         {
 816                 for (int x = 0; x < board->Width(); ++x)
 817                 {
 818                         char c = cin.get();
 819                         switch (c)
 820                         {
 821                                 case '.': //Empty square
 822                                         break;
 823                                 case '+': //Boulder/Obstacle
 824                                         board->Set(x, y, new Piece(x, y, Piece::NONE, Piece::BOULDER));
 825                                         break;
 826                                 case '#': //Enemy piece occupies square
 827                                 case '*':
 828                                 {
 829                                         Piece * toAdd = new Piece(x, y, Piece::Opposite(colour));
 830                                         board->Set(x, y, toAdd);
 831                                         board->GetPieces(toAdd->colour).push_back(toAdd);
 832                                         break;
 833                                 }
 834                                 default: //Allied piece occupies square
 835                                 {
 836                                         Piece::Type type = Piece::GetType(c);
 837                                         Piece * toAdd = new Piece(x, y, colour, type);
 838                                         board->Set(x, y, toAdd);
 839                                         board->GetPieces(toAdd->colour).push_back(toAdd);
 840                                         break;
 841                                 }
 842                         }
 843                 }
 844                 if (cin.get() != '\n')
 845                         return NO_NEWLINE;
 846         }
 847
 848         return OK;
 849 }
 850
 851 /**
 852  * Calculates the intrinsic strategic worth of a point on the board
 853  * @param x the x coordinate of the point
 854  * @param y the y coordinate of the point
 855  * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 856  * (NOTE: No points will actually be worth 0)
 857  */
 858 double Forfax::IntrinsicWorth(int x, int y) const
 859 {
 860         static double intrinsicWorth[][10][10] =
 861         {
 862                 //Red
 863                 {
 864                 {0.1,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
 865                 {0.5,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
 866                 {0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2},
 867                 {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3},
 868                 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
 869                 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
 870                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 871                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 872                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 873                 {0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7}
 874
 875
 876                 },
 877                 //Blue
 878                 {
 879                 {0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7},
 880                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 881                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 882                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 883                 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
 884                 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
 885                 {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3},
 886                 {0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2},
 887                 {0.5,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
 888                 {0.1,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1}
 889                 }
 890         };
 891
 892         return intrinsicWorth[(int)(colour)][x][y];
 893 }
 894
 895 /**
 896  * Calculates a score assuming that attacker will beat defender, indicating how much killing that piece is worth
 897  * @param attacker the Attacking piece
 898  * @param defender the Defending piece
 899  * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 900  */
 901 double Forfax::VictoryScore(Piece * attacker, Piece * defender) const
 902 {
 903
 904         //If defender's rank is known, flags or bombs are worth more than usual
 905         if (defender->minRank == defender->maxRank)
 906         {
 907                 if (defender->minRank == Piece::FLAG)
 908                         return 1;
 909                 else if (defender->minRank == Piece::BOMB)
 910                         return 0.9;
 911         }
 912         //Return average of normalised defender ranks
 913         return max<double>(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 0.6);
 914 }
 915
 916 /**
 917  * Calculates a score assuming that attacker will lose to defender, indicating how much learning the rank of that piece is worth
 918  * @param attacker the Attacking piece
 919  * @param defender the Defending piece
 920  * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 921  */
 922 double Forfax::DefeatScore(Piece * attacker, Piece * defender) const
 923 {
 924
 925         double result = 0;
 926         if (defender->minRank == defender->maxRank) //If the defender's rank is known for certain...
 927         {
 928                 if (defender->minRank == Piece::BOMB) //Committing suicide to destroy bombs has a value that decreases with the attacker's rank
 929                         result = 1 - 0.5*(double)((double)(attacker->minRank) / (double)(Piece::BOMB));
 930                 else if (defender->minRank == Piece::FLAG)
 931                         result = 1; //Its impossible to lose to the flag anyway...
 932                 else
 933                 {
 934                         //This is committing suicide on a higher ranked non-bomb enemy piece.
 935                         //Basically pointless, but the greater the attacker's rank the more pointless!
 936                         double temp = (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
 937                         result = 0.01*(1 - temp)*(1 - temp);
 938
 939
 940                 }
 941         }
 942         else //The defender's rank is not known
 943         {
 944
 945                 //Score is allocated based on how much knowledge is gained by attacking defender
 946                 //The more possible ranks for the defender, the greater the score
 947                 //The score decreases as the rank of the attacker is increased.
 948
 949                 double possibleRanks = 0; double totalRanks = 0; double bonus = 0;
 950                 for (Piece::Type rank = Piece::NOTHING; rank <= Piece::BOMB; rank = Piece::Type((int)(rank) + 1))
 951                 {
 952                         totalRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
 953
 954                         if (rank >= defender->minRank && rank <= defender->maxRank)
 955                         {
 956                                 possibleRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
 957                                 if (rank == Piece::BOMB)
 958                                         bonus += remainingUnits[(int)(defender->colour)][(int)(rank)];
 959                                 if (rank == Piece::FLAG)
 960                                         bonus += 2*remainingUnits[(int)(defender->colour)][(int)(rank)];
 961                         }
 962
 963                 }
 964
 965
 966                 if (totalRanks > 0)
 967                         result = (possibleRanks/totalRanks) - 0.8*(double)((double)(attacker->minRank) / (double)(Piece::BOMB));
 968
 969                 result += bonus / totalRanks;
 970
 971                 if (result > 1)
 972                         result = 1;
 973         }
 974
 975         if (attacker->minRank == Piece::SPY) //Spies are slightly more valuable than usual since they kill the Marshal
 976                 result = result / 1.5;
 977         return result;
 978
 979 }
 980
 981 /**
 982  * Calculates a score indicating the worth of invoking combat in a square
 983  * @param x The x coordinate
 984  * @param y The y coordinate
 985  * @param attacker The piece invoking the combat
 986  * @returns A value between 0 in 1, with 0 indicating worthless (or no combat) and 1 indicating highest value
 987  */
 988 double Forfax::CombatScore(int x, int y, Piece * attacker) const
 989 {
 990         Piece * defender = board->Get(x, y);
 991         if (defender == NULL)
 992                 return 0;
 993         double combatSuccess = CombatSuccessChance(attacker, defender);
 994         return IntrinsicWorth(x, y)*combatSuccess*VictoryScore(attacker, defender) + (1.0 - combatSuccess)*DefeatScore(attacker, defender);
 995 }
 996
 997 /**
 998  * DEBUG - Print the board seen by Forfax to a stream
 999  * @param out The stream to print to
1000  */
1001 void Forfax::PrintBoard(ostream & out)
1002 {
1003         for (int y = 0; y < board->Height(); ++y)
1004         {
1005                 for (int x = 0; x < board->Width(); ++x)
1006                 {
1007                         Piece * at = board->Get(x, y);
1008                         if (at == NULL)
1009                                 out << ".";
1010                         else
1011                         {
1012                                 if (at->colour == colour)
1013                                 {
1014                                         out << Piece::tokens[(int)(at->minRank)];
1015                                 }
1016                                 else if (at->colour == Piece::Opposite(colour))
1017                                 {
1018                                         out << "#";
1019                                 }
1020                                 else
1021                                 {
1022                                         out << "+";
1023                                 }
1024                         }
1025                 }
1026                 out << "\n";
1027         }
1028 }
1029
1030 //EOF
1031