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','s','9','8','7','6','5','4','3','2','1','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, or a negative number (-1) if the move is illegal
 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                 return -1; //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                         double multiplier = (double)(max<int>(board->Width(), board->Height()) - Board::NumberOfMoves(closestEnemy->x, closestEnemy->y, x2, y2)) / (double)(max<int>(board->Width(), board->Height()));
 449
 450                         basevalue = CombatScore(closestEnemy->x, closestEnemy->y, piece)*multiplier*multiplier;
 451
 452                 }
 453
 454
 455         }
 456         else if (board->Get(x2, y2)->colour != Piece::Opposite(piece->colour))
 457         {
 458                 return -1; //The position is occupied by an ally, and so its pointless to try and move there
 459         }
 460         else
 461         {
 462                 basevalue = CombatScore(x2, y2, piece); //The position is occupied by an enemy; compute combat score
 463
 464         }
 465
 466         if (basevalue > 0)
 467         {
 468                 //Hack which decreases score for units that moved recently
 469                 //Does not decrease below a threshold (so that at the start of the game units will actually move!)
 470                 double oldValue = basevalue;
 471                 basevalue -= (double)(1.0/((double)(1.0 + (turnNumber - piece->lastMove))));
 472                 if (basevalue < oldValue/1000.0)
 473                         basevalue = oldValue/1000.0;
 474         }
 475
 476
 477         if (x2 == piece->lastx && y2 == piece->lasty) //Hack which decreases score for backtracking moves
 478                 basevalue = basevalue/100;
 479
 480         if (rand() % 10 == 0) //Hack which introduces some randomness by boosting one in every 10 scores
 481                 basevalue *= 4;
 482         if (basevalue > 1)
 483                 basevalue = 1;
 484         return basevalue;
 485 }
 486
 487
 488 /**
 489  * Initialisation for Forfax
 490  * Reads information from stdin about the board, and Forfax's colour. Initialises board, and prints appropriate setup to stdout.
 491  * @returns true if Forfax was successfully initialised, false otherwise.
 492  */
 493 Forfax::Status Forfax::Setup()
 494 {
 495         //The first line is used to identify Forfax's colour, and the size of the board
 496         //Currently the name of the opponent is ignored.
 497
 498         //Forfax then responds with a setup.
 499         //Forfax only uses one of two setups, depending on what colour he was assigned.
 500
 501
 502         //Variables to store information read from stdin
 503         strColour.clear();
 504         string strOpponent; int boardWidth; int boardHeight;
 505
 506         cin >> strColour; cin >> strOpponent; cin >> boardWidth; cin >> boardHeight;
 507         if (cin.get() != '\n')
 508                 return NO_NEWLINE;
 509
 510         //Determine Forfax's colour and respond with an appropriate setup
 511         if (strColour == "RED")
 512         {
 513                 colour = Piece::RED;
 514                 cout << "FB8sB479B8\n";
 515                 cout << "BB31555583\n";
 516                 cout << "6724898974\n";
 517                 cout << "967B669999\n";
 518         }
 519         else if (strColour == "BLUE")
 520         {
 521                 colour = Piece::BLUE;
 522                 cout << "967B669999\n";
 523                 cout << "6724898974\n";
 524                 cout << "BB31555583\n";
 525                 cout << "FB8sB479B8\n";
 526         }
 527         else
 528                 return INVALID_QUERY;
 529
 530
 531         //Create the board
 532         //NOTE: At this stage, the board is still empty. The board is filled on Forfax's first turn
 533         //      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
 534
 535         board = new Board(boardWidth, boardHeight);
 536         if (board == NULL)
 537                 return BOARD_ERROR;
 538         return OK;
 539 }
 540
 541 /**
 542  * Make a single move
 543  * 1. Read result of previous move from stdin (or "START" if Forfax is RED and it is the very first move)
 544  * 2. Read in board state from stdin (NOTE: Unused - all information needed to maintain board state is in 1. and 4.)
 545  *      TODO: Considering removing this step from the protocol? (It makes debugging annoying because I have to type a lot more!)
 546  * 3. Print desired move to stdout
 547  * 4. Read in result of chosen move from stdin
 548  * @returns true if everything worked, false if there was an error or unexpected query
 549  */
 550 Forfax::Status Forfax::MakeMove()
 551 {
 552         ++turnNumber;
 553
 554         if (turnNumber == 1)
 555         {
 556                 Status firstMove = MakeFirstMove();
 557                 if (firstMove != OK)
 558                         return firstMove;
 559         }
 560         else
 561         {
 562                 //Read and interpret the result of the previous move
 563                 Status interpret = InterpretMove();
 564                 if (interpret != OK) {return interpret;}
 565
 566                 //Forfax ignores the board state; he only uses the move result lines
 567                 #ifndef DEBUG
 568                 for (int y=0; y < board->Height(); ++y)
 569                 {
 570                         for (int x = 0; x < board->Width(); ++x)
 571                                 cin.get();
 572                         if (cin.get() != '\n')
 573                                 return NO_NEWLINE;
 574                 }
 575                 #endif //DEBUG
 576
 577         }
 578
 579         //Now compute the best move
 580         // 1. Construct list of all possible moves
 581         //      As each move is added to the list, a score is calculated for that move.
 582         //      WARNING: This is the "tricky" part!
 583         // 2. Sort the moves based on their score
 584         // 3. Simply use the highest scoring move!
 585
 586         list<MovementChoice> choices;
 587         vector<Piece*> & allies = board->GetPieces(colour);
 588         for (vector<Piece*>::iterator i = allies.begin(); i != allies.end(); ++i)
 589         {
 590                 choices.push_back(MovementChoice((*i), Board::UP, *this));
 591                 choices.push_back(MovementChoice((*i), Board::DOWN, *this));
 592                 choices.push_back(MovementChoice((*i), Board::LEFT, *this));
 593                 choices.push_back(MovementChoice((*i), Board::RIGHT, *this));
 594
 595         }
 596
 597         choices.sort(); //Actually sort the choices!!!
 598         MovementChoice & choice = choices.back(); //The best one is at the back, because sort() sorts the list in ascending order
 599
 600
 601
 602         //Convert information about the move into a printable form
 603         string direction;  Board::DirToStr(choice.dir, direction);
 604
 605         //Print chosen move to stdout
 606         cout << choice.piece->x << " " << choice.piece->y << " " << direction << "\n";
 607
 608         //cerr << "\nForfax move " << choice.piece->x << " " << choice.piece->y << " " << direction << " [score = " << choice.score << "]\n";
 609
 610
 611
 612
 613         //Interpret the result of the chosen move
 614         return InterpretMove();
 615
 616
 617
 618 }
 619
 620 /**
 621  * Reads and interprets the result of a move
 622  * Reads information from stdin
 623  * @returns true if the result was successfully interpreted, false if there was a contradiction or error
 624  */
 625 Forfax::Status Forfax::InterpretMove()
 626 {
 627         //Variables to store move information
 628         int x; int y; string direction; string result = ""; int multiplier = 1;
 629         Piece::Type attackerRank = Piece::NOTHING;
 630         Piece::Type defenderRank = Piece::NOTHING;
 631
 632         //Read in information from stdin
 633         cin >> x; cin >> y; cin >> direction; cin >> result;
 634
 635         //If necessary, read in the ranks of involved pieces (this happens if the outcome was DIES or KILLS or BOTHDIE)
 636         if (cin.peek() != '\n')
 637         {
 638                 string buf = "";
 639                 stringstream s(buf);
 640                 cin >> buf;
 641                 s.clear(); s.str(buf);
 642                 char temp;
 643                 s >> temp;
 644                 attackerRank = Piece::GetType(temp);
 645
 646                 buf.clear();
 647                 cin >> buf;
 648                 s.clear(); s.str(buf);
 649                 s >> temp;
 650                 defenderRank = Piece::GetType(temp);
 651
 652
 653         }
 654
 655         //TODO: Deal with move multipliers somehow (when a scout moves more than one space)
 656
 657         //Check that the line ends where expected...
 658         if (cin.get() != '\n')
 659         {
 660                 return NO_NEWLINE;
 661         }
 662
 663
 664
 665
 666
 667
 668
 669         //Work out the square moved into
 670         int x2 = x; int y2 = y;
 671         Board::Direction dir = Board::StrToDir(direction);
 672
 673         Board::MoveInDirection(x2, y2, dir, multiplier);
 674
 675
 676         //Determine the attacker and defender (if it exists)
 677         Piece * attacker = board->Get(x, y);
 678         Piece * defender = board->Get(x2, y2);
 679
 680
 681         //If ranks were supplied, update the known ranks of the involved pieces
 682         if (attackerRank != Piece::NOTHING && attacker != NULL)
 683         {
 684                 //assert(attacker->minRank <= attackerRank && attacker->maxRank >= attackerRank);
 685                 attacker->minRank = attackerRank;
 686                 attacker->maxRank = attackerRank;
 687         }
 688         if (defenderRank != Piece::NOTHING && defender != NULL)
 689         {
 690                 //assert(defender->minRank <= defenderRank && defender->maxRank >= defenderRank);
 691                 defender->minRank = defenderRank;
 692                 defender->maxRank = defenderRank;
 693
 694         }
 695
 696         //There should always be an attacking piece (but not necessarily a defender)
 697         if (attacker == NULL)
 698                 return EXPECTED_ATTACKER;
 699
 700
 701         attacker->lastMove = turnNumber; //Update stats of attacking piece (last move)
 702
 703         //Eliminate certain ranks from the possibilities for the piece based on its movement
 704         //(This is useful if the piece was an enemy piece)
 705         if (attacker->minRank == Piece::FLAG)
 706                 attacker->minRank = Piece::SPY;
 707         if (attacker->maxRank == Piece::BOMB)
 708                 attacker->maxRank = Piece::MARSHAL;
 709         if (multiplier > 1)
 710         {
 711                 attacker->maxRank = Piece::SCOUT;
 712                 attacker->minRank = Piece::SCOUT;
 713         }
 714
 715
 716
 717
 718         //Now look at the result of the move (I wish you could switch strings in C++)
 719
 720
 721         //The move was uneventful (attacker moved into empty square)
 722         if (result == "OK")
 723         {
 724                 if (defender != NULL)
 725                         return UNEXPECTED_DEFENDER;
 726
 727                 //Update board and piece
 728                 board->Set(x2, y2, attacker);
 729                 board->Set(x, y, NULL);
 730                 attacker->lastx = attacker->x;
 731                 attacker->lasty = attacker->y;
 732                 attacker->x = x2;
 733                 attacker->y = y2;
 734         }
 735         else if (result == "KILLS") //The attacking piece killed the defending piece
 736         {
 737                 if (defender == NULL || defender->colour == attacker->colour)
 738                         return COLOUR_MISMATCH;
 739
 740
 741
 742
 743                 board->Set(x2, y2, attacker);
 744                 board->Set(x, y, NULL);
 745                 attacker->lastx = attacker->x;
 746                 attacker->lasty = attacker->y;
 747                 attacker->x = x2;
 748                 attacker->y = y2;
 749
 750                 remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
 751
 752
 753                 if (!board->ForgetPiece(defender))
 754                         return NO_DEFENDER;
 755                 delete defender;
 756
 757         }
 758         else if (result == "DIES") //The attacking piece was killed by the defending piece
 759         {
 760
 761                 if (defender == NULL || defender->colour == attacker->colour)
 762                         return COLOUR_MISMATCH;
 763
 764                 remainingUnits[(int)(attacker->colour)][(int)(attackerRank)]--;
 765
 766                 if (!board->ForgetPiece(attacker))
 767                         return NO_ATTACKER;
 768                 delete attacker;
 769
 770                 board->Set(x, y, NULL);
 771         }
 772         else if (result == "BOTHDIE") //Both attacking and defending pieces died
 773         {
 774                 if (defender == NULL || defender->colour == attacker->colour)
 775                         return COLOUR_MISMATCH;
 776
 777                 remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
 778                 remainingUnits[(int)(attacker->colour)][(int)(attackerRank)]--;
 779
 780                 if (board->ForgetPiece(attacker) == false)
 781                         return NO_ATTACKER;
 782                 if (board->ForgetPiece(defender) == false)
 783                         return NO_DEFENDER;
 784                 delete attacker;
 785                 delete defender;
 786                 board->Set(x2, y2, NULL);
 787                 board->Set(x, y, NULL);
 788         }
 789         else if (result == "VICTORY") //The attacking piece captured a flag
 790         {
 791                 return VICTORY;
 792
 793         }
 794         return OK;
 795 }
 796
 797 /**
 798  * Forfax's first move
 799  * Sets the state of the board
 800  * @returns true if the board was successfully read, false if an error occurred.
 801  *
 802  */
 803 Forfax::Status Forfax::MakeFirstMove()
 804 {
 805         if (colour == Piece::RED)
 806         {
 807                 string derp;
 808                 cin >> derp;
 809                 if (derp != "START")
 810                         return INVALID_QUERY;
 811                 if (cin.get() != '\n')
 812                         return NO_NEWLINE;
 813         }
 814         else
 815         {
 816                 //TODO: Fix hack where BLUE ignores RED's first move
 817                 while (cin.get() != '\n');
 818         }
 819
 820         for (int y=0; y < board->Height(); ++y)
 821         {
 822                 for (int x = 0; x < board->Width(); ++x)
 823                 {
 824                         char c = cin.get();
 825                         switch (c)
 826                         {
 827                                 case '.': //Empty square
 828                                         break;
 829                                 case '+': //Boulder/Obstacle
 830                                         board->Set(x, y, new Piece(x, y, Piece::NONE, Piece::BOULDER));
 831                                         break;
 832                                 case '#': //Enemy piece occupies square
 833                                 case '*':
 834                                 {
 835                                         Piece * toAdd = new Piece(x, y, Piece::Opposite(colour));
 836                                         board->Set(x, y, toAdd);
 837                                         board->GetPieces(toAdd->colour).push_back(toAdd);
 838                                         break;
 839                                 }
 840                                 default: //Allied piece occupies square
 841                                 {
 842                                         Piece::Type type = Piece::GetType(c);
 843                                         Piece * toAdd = new Piece(x, y, colour, type);
 844                                         board->Set(x, y, toAdd);
 845                                         board->GetPieces(toAdd->colour).push_back(toAdd);
 846                                         break;
 847                                 }
 848                         }
 849                 }
 850                 if (cin.get() != '\n')
 851                         return NO_NEWLINE;
 852         }
 853
 854         return OK;
 855 }
 856
 857 /**
 858  * Calculates the intrinsic strategic worth of a point on the board
 859  * @param x the x coordinate of the point
 860  * @param y the y coordinate of the point
 861  * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 862  * (NOTE: No points will actually be worth 0)
 863  */
 864 double Forfax::IntrinsicWorth(int x, int y) const
 865 {
 866         static double intrinsicWorth[][10][10] =
 867         {
 868                 //Red
 869                 {
 870                 {0.1,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
 871                 {0.5,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
 872                 {0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2},
 873                 {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3},
 874                 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
 875                 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
 876                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 877                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 878                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 879                 {0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7}
 880
 881
 882                 },
 883                 //Blue
 884                 {
 885                 {0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7},
 886                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 887                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 888                 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
 889                 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
 890                 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
 891                 {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3},
 892                 {0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2},
 893                 {0.5,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
 894                 {0.1,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1}
 895                 }
 896         };
 897
 898         return intrinsicWorth[(int)(colour)][x][y];
 899 }
 900
 901 /**
 902  * Calculates a score assuming that attacker will beat defender, indicating how much killing that piece is worth
 903  * @param attacker the Attacking piece
 904  * @param defender the Defending piece
 905  * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 906  */
 907 double Forfax::VictoryScore(Piece * attacker, Piece * defender) const
 908 {
 909
 910         //If defender's rank is known, flags or bombs are worth more than usual
 911         if (defender->minRank == defender->maxRank)
 912         {
 913                 if (defender->minRank == Piece::FLAG)
 914                         return 1;
 915                 else if (defender->minRank == Piece::BOMB)
 916                         return 0.9;
 917         }
 918         //Return average of normalised defender ranks
 919         return max<double>(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 1);
 920 }
 921
 922 /**
 923  * Calculates a score assuming that attacker will lose to defender, indicating how much learning the rank of that piece is worth
 924  * @param attacker the Attacking piece
 925  * @param defender the Defending piece
 926  * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 927  */
 928 double Forfax::DefeatScore(Piece * attacker, Piece * defender) const
 929 {
 930
 931         double result = 0;
 932         if (defender->minRank == defender->maxRank) //If the defender's rank is known for certain...
 933         {
 934                 if (defender->minRank == Piece::BOMB) //Committing suicide to destroy bombs has a value that decreases with the attacker's rank
 935                         result = 1 - 0.5*(double)((double)(attacker->minRank) / (double)(Piece::BOMB));
 936                 else if (defender->minRank == Piece::FLAG)
 937                         result = 1; //Its impossible to lose to the flag anyway...
 938                 else
 939                 {
 940                         //This is committing suicide on a higher ranked non-bomb enemy piece.
 941                         //Basically pointless, but the greater the attacker's rank the more pointless!
 942                         double temp = (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
 943                         result = 0.01*(1 - temp)*(1 - temp);
 944
 945
 946                 }
 947         }
 948         else //The defender's rank is not known
 949         {
 950
 951                 //Score is allocated based on how much knowledge is gained by attacking defender
 952                 //The more possible ranks for the defender, the greater the score
 953                 //The score decreases as the rank of the attacker is increased.
 954
 955                 double possibleRanks = 0; double totalRanks = 0; double bonus = 0;
 956                 for (Piece::Type rank = Piece::NOTHING; rank <= Piece::BOMB; rank = Piece::Type((int)(rank) + 1))
 957                 {
 958                         totalRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
 959
 960                         if (rank >= defender->minRank && rank <= defender->maxRank)
 961                         {
 962                                 possibleRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
 963                                 if (rank == Piece::BOMB)
 964                                         bonus += remainingUnits[(int)(defender->colour)][(int)(rank)];
 965                                 if (rank == Piece::FLAG)
 966                                         bonus += 2*remainingUnits[(int)(defender->colour)][(int)(rank)];
 967                         }
 968
 969                 }
 970
 971
 972                 if (totalRanks > 0)
 973                 {
 974                         double multiplier = ((double)(Piece::BOMB) - (double)(attacker->minRank)) / (double)(Piece::BOMB);
 975                         result = (possibleRanks/totalRanks) * multiplier * multiplier;
 976                 }
 977
 978                 result += bonus / totalRanks;
 979
 980                 if (result > 1)
 981                         result = 1;
 982         }
 983
 984         if (attacker->minRank == Piece::SPY) //Spies are slightly more valuable than usual since they kill the Marshal
 985                 result = result / 1.5;
 986         return result;
 987
 988 }
 989
 990 /**
 991  * Calculates a score indicating the worth of invoking combat in a square
 992  * @param x The x coordinate
 993  * @param y The y coordinate
 994  * @param attacker The piece invoking the combat
 995  * @returns A value between 0 in 1, with 0 indicating worthless (or no combat) and 1 indicating highest value
 996  */
 997 double Forfax::CombatScore(int x, int y, Piece * attacker) const
 998 {
 999         Piece * defender = board->Get(x, y);
1000         if (defender == NULL)
1001                 return 0;
1002         double combatSuccess = CombatSuccessChance(attacker, defender);
1003         return IntrinsicWorth(x, y)*combatSuccess*VictoryScore(attacker, defender) + (1.0 - combatSuccess)*DefeatScore(attacker, defender);
1004 }
1005
1006 /**
1007  * DEBUG - Print the board seen by Forfax to a stream
1008  * @param out The stream to print to
1009  */
1010 void Forfax::PrintBoard(ostream & out)
1011 {
1012         for (int y = 0; y < board->Height(); ++y)
1013         {
1014                 for (int x = 0; x < board->Width(); ++x)
1015                 {
1016                         Piece * at = board->Get(x, y);
1017                         if (at == NULL)
1018                                 out << ".";
1019                         else
1020                         {
1021                                 if (at->colour == colour)
1022                                 {
1023                                         out << Piece::tokens[(int)(at->minRank)];
1024                                 }
1025                                 else if (at->colour == Piece::Opposite(colour))
1026                                 {
1027                                         out << "#";
1028                                 }
1029                                 else
1030                                 {
1031                                         out << "+";
1032                                 }
1033                         }
1034                 }
1035                 out << "\n";
1036         }
1037 }
1038
1039 //EOF
1040