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
7 * @git git.ucc.asn.au/progcomp2012.git
26 * The characters used to represent various pieces
27 * NOTHING, BOULDER, FLAG, SPY, SCOUT, MINER, SERGEANT, LIETENANT, CAPTAIN, MAJOR, COLONEL, GENERAL, MARSHAL, BOMB, ERROR
30 char Piece::tokens[] = {'.','+','F','y','s','n','S','L','c','m','C','G','M','B','?'};
34 * The number of units remaining for each colour
35 * Accessed by [COLOUR][TYPE]
37 * TYPE: NOTHING, BOULDER, FLAG, SPY, SCOUT, MINER, SERGEANT, LIETENANT, CAPTAIN, MAJOR, COLONEL, GENERAL, MARSHAL, BOMB, ERROR
39 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}};
45 * Constructor for a piece of unknown rank
46 * @param newX - x coord
47 * @param newY - y coord
48 * @param newColour - colour
50 Piece::Piece(int newX, int newY,const Colour & newColour)
51 : x(newX), y(newY), colour(newColour), minRank(Piece::FLAG), maxRank(Piece::BOMB), lastMove(0)
57 * Constructor for a piece of known rank
58 * @param newX - x coord
59 * @param newY - y coord
60 * @param newColour - colour
61 * @param fixedRank - rank of the new piece
63 Piece::Piece(int newX, int newY,const Colour & newColour, const Type & fixedRank)
64 : x(newX), y(newY), colour(newColour), minRank(fixedRank), maxRank(fixedRank), lastMove(0)
76 * HELPER - Returns the Piece::Type matching a given character
77 * @param token - The character to match
78 * @returns A Piece::Type corresponding to the character, or Piece::ERROR if none was found
80 Piece::Type Piece::GetType(char token)
82 for (int ii=0; ii < Piece::ERROR; ++ii)
84 if (Piece::tokens[ii] == token)
91 * Constructor for the board
92 * @param newWidth - width of the board
93 * @param newHeight - height of the board
96 Board::Board(int newWidth, int newHeight) : width(newWidth), height(newHeight), board(NULL), red(), blue()
98 //Construct 2D array of Piece*'s
99 board = new Piece**[width];
100 for (int x=0; x < width; ++x)
102 board[x] = new Piece*[height];
103 for (int y=0; y < height; ++y)
113 //Destroy the 2D array of Piece*'s
114 for (int x=0; x < width; ++x)
116 for (int y=0; y < height; ++y)
123 * Retrieve a piece from the board at specified coordinates
124 * @param x - x coord of the piece
125 * @param y - y coord of the piece
126 * @returns Piece* to the piece found at (x,y), or NULL if there was no piece, or the coords were invalid
128 Piece * Board::Get(int x, int y) const
130 if (board == NULL || x < 0 || y < 0 || x >= width || y >= height)
136 * Add a piece to the board
137 * Also updates the red or blue arrays if necessary
138 * @param x - x coord of the piece
139 * @param y - y coord of the piece
140 * @param newPiece - pointer to the piece to add
141 * @returns newPiece if the piece was successfully added, NULL if it was not (ie invalid coordinates specified)
144 Piece * Board::Set(int x, int y, Piece * newPiece)
146 if (board == NULL || x < 0 || y < 0 || x >= width || y >= height)
148 board[x][y] = newPiece;
150 //if (newPiece->GetColour() == Piece::RED)
151 // red.push_back(newPiece);
152 //else if (newPiece->GetColour() == Piece::BLUE)
153 // blue.push_back(newPiece);
160 * HELPER - Convert a string to a direction
161 * @param str - The string to convert to a direction
162 * @returns The equivalent Direction
164 Board::Direction Board::StrToDir(const string & str)
168 else if (str == "DOWN")
170 else if (str == "LEFT")
172 else if (str == "RIGHT")
179 * HELPER - Convert a Direction to a string
180 * @param dir - the Direction to convert
181 * @param str - A buffer string, which will contain the string representation of the Direction once this function returns.
183 void Board::DirToStr(const Direction & dir, string & str)
207 * HELPER - Translates the given coordinates in a specified direction
210 * @param dir - Direction to move in
211 * @param multiplier - Number of times to move
214 void Board::MoveInDirection(int & x, int & y, const Direction & dir, int multiplier)
236 * HELPER - Returns the best direction to move in to get from one point to another
237 * @param x1 - x coord of point 1
238 * @param y1 - y coord of point 1
239 * @param x2 - x coord of point 2
240 * @param y2 - y coord of point 2
241 * @returns The best direction to move in
243 Board::Direction Board::DirectionBetween(int x1, int y1, int x2, int y2)
247 double xDist = (x2 - x1);
248 double yDist = (y2 - y1);
249 if (abs(xDist) >= abs(yDist))
271 * Searches the board's red and blue arrays for the piece, and removes it
272 * DOES NOT delete the piece. Calling function should delete piece after calling this function.
273 * @param forget - The Piece to forget about
274 * @returns true if the piece was actually found
276 bool Board::ForgetPiece(Piece * forget)
281 vector<Piece*> & in = GetPieces(forget->colour); bool result = false;
282 for (vector<Piece*>::iterator i=in.begin(); i != in.end(); ++i)
301 * Construct the Forfax AI
303 Forfax::Forfax() : board(NULL), colour(Piece::NONE), strColour("NONE"), turnNumber(0)
305 //By default, Forfax knows nothing; the main function in main.cpp calls Forfax's initialisation functions
313 //fprintf(stderr,"Curse you mortal for casting me into the fires of hell!\n");
320 * Calculate the probability that attacker beats defender in combat
321 * @param attacker The attacking piece
322 * @param defender The defending piece
323 * @returns A double between 0 and 1 indicating the probability of success
326 double Forfax::CombatSuccessChance(Piece * attacker, Piece * defender) const
328 double probability=1;
329 for (Piece::Type aRank = attacker->minRank; aRank <= attacker->maxRank; aRank = (Piece::Type)((int)(aRank) + 1))
331 double lesserRanks=0; double greaterRanks=0;
332 for (Piece::Type dRank = defender->minRank; dRank <= defender->maxRank; dRank = (Piece::Type)((int)(dRank) + 1))
335 lesserRanks += remainingUnits[defender->colour][(int)(dRank)];
336 else if (dRank > aRank)
337 greaterRanks += remainingUnits[defender->colour][(int)(dRank)];
340 lesserRanks++; greaterRanks++;
343 probability *= lesserRanks/(lesserRanks + greaterRanks);
349 * Calculate the score of a move
350 * TODO: Alter this to make it better
351 * @param piece - The Piece to move
352 * @param dir - The direction in which to move
353 * @returns a number between 0 and 1, indicating how worthwhile the move is
355 double Forfax::MovementScore(Piece * piece, const Board::Direction & dir) const
357 assert(piece != NULL);
360 int x2 = piece->x; int y2 = piece->y;
361 Board::MoveInDirection(x2, y2, dir);
366 if (!board->ValidPosition(x2, y2) || !piece->Mobile())
371 else if (board->Get(x2, y2) == NULL)
373 basevalue = 0.5*IntrinsicWorth(x2, y2);
376 else if (board->Get(x2, y2)->colour != Piece::Opposite(piece->colour))
382 Piece * defender = board->Get(x2, y2);
383 double combatSuccess = CombatSuccessChance(piece, defender);
384 basevalue = IntrinsicWorth(x2, y2)*combatSuccess*VictoryScore(piece, defender) + (1.0 - combatSuccess)*DefeatScore(piece, defender);
389 double oldValue = basevalue;
390 basevalue -= (double)(1.0/((double)(1.0 + (turnNumber - piece->lastMove))));
391 if (basevalue < oldValue/8.0)
392 basevalue = oldValue/8.0;
400 * Initialisation for Forfax
401 * Reads information from stdin about the board, and Forfax's colour. Initialises board, and prints appropriate setup to stdout.
402 * @returns true if Forfax was successfully initialised, false otherwise.
404 Forfax::Status Forfax::Setup()
406 //The first line is used to identify Forfax's colour, and the size of the board
407 //Currently the name of the opponent is ignored.
409 //Forfax then responds with a setup.
410 //Forfax only uses one of two setups, depending on what colour he was assigned.
413 //Variables to store information read from stdin
415 string strOpponent; int boardWidth; int boardHeight;
417 cin >> strColour; cin >> strOpponent; cin >> boardWidth; cin >> boardHeight;
418 if (cin.get() != '\n')
421 //Determine Forfax's colour and respond with an appropriate setup
422 if (strColour == "RED")
425 cout << "FBmSsnsnBn\n";
426 cout << "BBCMccccyC\n";
427 cout << "LSGmnsBsSm\n";
428 cout << "sLSBLnLsss\n";
430 else if (strColour == "BLUE")
432 colour = Piece::BLUE;
433 cout << "sLSBLnLsss\n";
434 cout << "LSGmnsBsSm\n";
435 cout << "BBCMccccyC\n";
436 cout << "FBmSsnsnBn\n";
439 return INVALID_QUERY;
443 //NOTE: At this stage, the board is still empty. The board is filled on Forfax's first turn
444 // 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
446 board = new Board(boardWidth, boardHeight);
454 * 1. Read result of previous move from stdin (or "START" if Forfax is RED and it is the very first move)
455 * 2. Read in board state from stdin (NOTE: Unused - all information needed to maintain board state is in 1. and 4.)
456 * TODO: Considering removing this step from the protocol? (It makes debugging annoying because I have to type a lot more!)
457 * 3. Print desired move to stdout
458 * 4. Read in result of chosen move from stdin
459 * @returns true if everything worked, false if there was an error or unexpected query
461 Forfax::Status Forfax::MakeMove()
467 Status firstMove = MakeFirstMove();
473 //Read and interpret the result of the previous move
474 Status interpret = InterpretMove();
475 if (interpret != OK) {return interpret;}
477 //Forfax ignores the board state; he only uses the move result lines
479 for (int y=0; y < board->Height(); ++y)
481 for (int x = 0; x < board->Width(); ++x)
483 if (cin.get() != '\n')
489 //Now compute the best move
490 // 1. Construct list of all possible moves
491 // As each move is added to the list, a score is calculated for that move.
492 // WARNING: This is the "tricky" part!
493 // 2. Sort the moves based on their score
494 // 3. Simply use the highest scoring move!
496 list<MovementChoice> choices;
497 vector<Piece*> & allies = board->GetPieces(colour);
498 for (vector<Piece*>::iterator i = allies.begin(); i != allies.end(); ++i)
500 choices.push_back(MovementChoice((*i), Board::UP, *this));
501 choices.push_back(MovementChoice((*i), Board::DOWN, *this));
502 choices.push_back(MovementChoice((*i), Board::LEFT, *this));
503 choices.push_back(MovementChoice((*i), Board::RIGHT, *this));
507 choices.sort(); //Actually sort the choices!!!
508 MovementChoice & choice = choices.back(); //The best one is at the back, because sort() sorts the list in ascending order
512 //Convert information about the move into a printable form
513 string direction; Board::DirToStr(choice.dir, direction);
515 //Print chosen move to stdout
516 cout << choice.piece->x << " " << choice.piece->y << " " << direction << "\n";
523 //Interpret the result of the chosen move
524 return InterpretMove();
531 * Reads and interprets the result of a move
532 * Reads information from stdin
533 * @returns true if the result was successfully interpreted, false if there was a contradiction or error
535 Forfax::Status Forfax::InterpretMove()
537 //Variables to store move information
538 int x; int y; string direction; string result = ""; int multiplier = 1; int attackerVal = (int)(Piece::BOMB); int defenderVal = (int)(Piece::BOMB);
541 //Read in information from stdin
542 cin >> x; cin >> y; cin >> direction; cin >> result;
544 //If necessary, read in the ranks of involved pieces (this happens if the outcome was DIES or KILLS or BOTHDIE)
545 if (cin.peek() != '\n')
550 s.clear(); s.str(buf);
556 s.clear(); s.str(buf);
562 //TODO: Deal with move multipliers somehow (when a scout moves more than one space)
564 //Check that the line ends where expected...
565 if (cin.get() != '\n')
571 //Convert printed ranks into internal Piece::Type ranks
572 Piece::Type attackerRank = Piece::Type(Piece::BOMB - attackerVal);
573 Piece::Type defenderRank = Piece::Type(Piece::BOMB - defenderVal);
577 //Work out the square moved into
578 int x2 = x; int y2 = y;
579 Board::Direction dir = Board::StrToDir(direction);
581 Board::MoveInDirection(x2, y2, dir, multiplier);
584 //Determine the attacker and defender (if it exists)
585 Piece * attacker = board->Get(x, y);
586 Piece * defender = board->Get(x2, y2);
589 //If ranks were supplied, update the known ranks of the involved pieces
590 if (attackerRank != Piece::NOTHING && attacker != NULL)
592 assert(attacker->minRank <= attackerRank && attacker->maxRank >= attackerRank);
593 attacker->minRank = attackerRank;
594 attacker->maxRank = attackerRank;
596 if (defenderRank != Piece::NOTHING && defender != NULL)
598 assert(defender->minRank <= defenderRank && defender->maxRank >= defenderRank);
599 defender->minRank = defenderRank;
600 defender->maxRank = defenderRank;
604 //There should always be an attacking piece (but not necessarily a defender)
605 if (attacker == NULL)
606 return EXPECTED_ATTACKER;
609 attacker->lastMove = turnNumber; //Update stats of attacking piece (last move)
611 //Eliminate certain ranks from the possibilities for the piece based on its movement
612 //(This is useful if the piece was an enemy piece)
613 if (attacker->minRank == Piece::FLAG)
614 attacker->minRank = Piece::SPY;
615 if (attacker->maxRank == Piece::BOMB)
616 attacker->maxRank = Piece::MARSHAL;
619 attacker->maxRank = Piece::SCOUT;
620 attacker->minRank = Piece::SCOUT;
626 //Now look at the result of the move (I wish you could switch strings in C++)
629 //The move was uneventful (attacker moved into empty square)
632 if (defender != NULL)
633 return UNEXPECTED_DEFENDER;
635 //Update board and piece
636 board->Set(x2, y2, attacker);
637 board->Set(x, y, NULL);
641 else if (result == "KILLS") //The attacking piece killed the defending piece
643 if (defender == NULL || defender->colour == attacker->colour)
644 return COLOUR_MISMATCH;
649 board->Set(x2, y2, attacker);
650 board->Set(x, y, NULL);
654 remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
657 if (!board->ForgetPiece(defender))
662 else if (result == "DIES") //The attacking piece was killed by the defending piece
665 if (defender == NULL || defender->colour == attacker->colour)
666 return COLOUR_MISMATCH;
668 remainingUnits[(int)(attacker->colour)][(int)(attackerRank)]--;
670 if (!board->ForgetPiece(attacker))
674 board->Set(x, y, NULL);
676 else if (result == "BOTHDIE") //Both attacking and defending pieces died
678 if (defender == NULL || defender->colour == attacker->colour)
679 return COLOUR_MISMATCH;
681 remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
682 remainingUnits[(int)(attacker->colour)][(int)(attackerRank)]--;
684 if (board->ForgetPiece(attacker) == false)
686 if (board->ForgetPiece(defender) == false)
690 board->Set(x2, y2, NULL);
691 board->Set(x, y, NULL);
693 else if (result == "VICTORY") //The attacking piece captured a flag
702 * Forfax's first move
703 * Sets the state of the board
704 * @returns true if the board was successfully read, false if an error occurred.
707 Forfax::Status Forfax::MakeFirstMove()
709 if (colour == Piece::RED)
714 return INVALID_QUERY;
715 if (cin.get() != '\n')
720 //TODO: Fix hack where BLUE ignores RED's first move
721 while (cin.get() != '\n');
724 for (int y=0; y < board->Height(); ++y)
726 for (int x = 0; x < board->Width(); ++x)
731 case '.': //Empty square
733 case '+': //Boulder/Obstacle
734 board->Set(x, y, new Piece(x, y, Piece::NONE, Piece::BOULDER));
736 case '#': //Enemy piece occupies square
739 Piece * toAdd = new Piece(x, y, Piece::Opposite(colour));
740 board->Set(x, y, toAdd);
741 board->GetPieces(toAdd->colour).push_back(toAdd);
744 default: //Allied piece occupies square
746 Piece::Type type = Piece::GetType(c);
747 Piece * toAdd = new Piece(x, y, colour, type);
748 board->Set(x, y, toAdd);
749 board->GetPieces(toAdd->colour).push_back(toAdd);
754 if (cin.get() != '\n')
762 * Calculates the intrinsic strategic worth of a point on the board
763 * @param x the x coordinate of the point
764 * @param y the y coordinate of the point
765 * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
766 * (NOTE: No points will actually be worth 0)
768 double Forfax::IntrinsicWorth(int x, int y) const
770 static double intrinsicWorth[][10][10] =
774 {0.1,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
775 {0.5,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
776 {0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2},
777 {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3},
778 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
779 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
780 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
781 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
782 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
783 {0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7}
789 {0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7},
790 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
791 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
792 {0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
793 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
794 {0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
795 {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3},
796 {0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2},
797 {0.5,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
798 {0.1,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1}
802 return intrinsicWorth[(int)(colour)][x][y];
806 * Calculates a score assuming that attacker will beat defender, indicating how much killing that piece is worth
807 * @param attacker the Attacking piece
808 * @param defender the Defending piece
809 * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
811 double Forfax::VictoryScore(Piece * attacker, Piece * defender) const
813 if (defender->minRank == defender->maxRank)
815 if (defender->minRank == Piece::FLAG)
817 else if (defender->minRank == Piece::BOMB)
820 return max<double>(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 0.6);
824 * Calculates a score assuming that attacker will lose to defender, indicating how much learning the rank of that piece is worth
825 * @param attacker the Attacking piece
826 * @param defender the Defending piece
827 * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
829 double Forfax::DefeatScore(Piece * attacker, Piece * defender) const
831 if (attacker->minRank == Piece::SPY)
834 if (defender->minRank == defender->maxRank)
836 if (defender->minRank == Piece::BOMB)
837 return 1 - (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
842 double possibleRanks = 0; double totalRanks = 0;
843 for (Piece::Type rank = Piece::NOTHING; rank <= Piece::BOMB; rank = Piece::Type((int)(rank) + 1))
845 totalRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
846 if (rank >= defender->minRank && rank <= defender->maxRank)
847 possibleRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
852 return (possibleRanks/totalRanks) - (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
857 * DEBUG - Print the board seen by Forfax to a stream
858 * @param out The stream to print to
860 void Forfax::PrintBoard(ostream & out)
862 for (int y = 0; y < board->Height(); ++y)
864 for (int x = 0; x < board->Width(); ++x)
866 Piece * at = board->Get(x, y);
871 if (at->colour == colour)
873 out << Piece::tokens[(int)(at->minRank)];
875 else if (at->colour == Piece::Opposite(colour))