#include <list>
#include <cmath>
+//#define DEBUG
+
using namespace std;
* NOTHING, BOULDER, FLAG, SPY, SCOUT, MINER, SERGEANT, LIETENANT, CAPTAIN, MAJOR, COLONEL, GENERAL, MARSHAL, BOMB, ERROR
*/
-char Piece::tokens[] = {'.','+','F','y','s','n','S','L','c','m','C','G','M','B','?'};
+char Piece::tokens[] = {'.','*','F','s','9','8','7','6','5','4','3','2','1','B','?'};
/**
* @param newColour - colour
*/
Piece::Piece(int newX, int newY,const Colour & newColour)
- : x(newX), y(newY), colour(newColour), minRank(Piece::FLAG), maxRank(Piece::BOMB), lastMove(0)
+ : x(newX), y(newY), colour(newColour), minRank(Piece::FLAG), maxRank(Piece::BOMB), lastMove(0), lastx(newX), lasty(newY)
{
}
* @param fixedRank - rank of the new piece
*/
Piece::Piece(int newX, int newY,const Colour & newColour, const Type & fixedRank)
- : x(newX), y(newY), colour(newColour), minRank(fixedRank), maxRank(fixedRank), lastMove(0)
+ : x(newX), y(newY), colour(newColour), minRank(fixedRank), maxRank(fixedRank), lastMove(0), lastx(newX), lasty(newY)
{
+}
+
+/**
+ * HELPER - Returns the number of moves between two points
+ * @param x1 x coordinate of the first point
+ * @param y1 y coordinate of the first point
+ * @param x2 x coordinate of the second point
+ * @param y2 y coordinate of the second point
+ * @returns The number of moves taken to progress from (x1, y1) to (x2, y2), assuming no obstacles
+ */
+int Board::NumberOfMoves(int x1, int y1, int x2, int y2)
+{
+ return (abs(x2 - x1) + abs(y2 - y1)); //Pieces can't move diagonally, so this is pretty straight forward
}
/**
return false;
vector<Piece*> & in = GetPieces(forget->colour); bool result = false;
- for (vector<Piece*>::iterator i=in.begin(); i != in.end(); ++i)
+ vector<Piece*>::iterator i=in.begin();
+ while (i != in.end())
{
if ((*i) == forget)
continue;
}
-
+ ++i;
}
return result;
+}
+
+/**
+ * Gets the closest Piece of a specified colour to a point
+ * @param x The x coordinate of the point
+ * @param y The y coordinate of the point
+ * @param colour The colour that the piece must match (may be Piece::BOTH to match either colour)
+ * @returns Piece* pointing to the closest piece of a matching colour, NULL if no piece found
+ */
+Piece * Board::GetClosest(int x, int y, const Piece::Colour & colour) const
+{
+ if (x < 0 || y < 0 || x >= width || y >= height)
+ return NULL;
+
+ for (int dist = 0; dist < max<int>(width, height); ++dist)
+ {
+
+ for (int yy = y-dist; yy <= y+dist; ++yy)
+ {
+ Piece * get = Get(x+dist, y);
+ if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
+ return get;
+ }
+ for (int yy = y-dist; yy <= y+dist; ++yy)
+ {
+ Piece * get = Get(x-dist, y);
+ if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
+ return get;
+ }
+ for (int xx = x-dist; xx <= x+dist; ++xx)
+ {
+ Piece * get = Get(xx, y+dist);
+ if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
+ return get;
+ }
+ for (int xx = x-dist; xx <= y+dist; ++xx)
+ {
+ Piece * get = Get(xx, y-dist);
+ if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
+ return get;
+ }
+
+ }
+
+ return NULL;
+
+
+
+
}
/**
Forfax::Forfax() : board(NULL), colour(Piece::NONE), strColour("NONE"), turnNumber(0)
{
//By default, Forfax knows nothing; the main function in main.cpp calls Forfax's initialisation functions
+ srand(time(NULL));
}
/**
* TODO: Alter this to make it better
* @param piece - The Piece to move
* @param dir - The direction in which to move
- * @returns a number between 0 and 1, indicating how worthwhile the move is
+ * @returns a number between 0 and 1, indicating how worthwhile the move is, or a negative number (-1) if the move is illegal
*/
double Forfax::MovementScore(Piece * piece, const Board::Direction & dir) const
{
if (!board->ValidPosition(x2, y2) || !piece->Mobile())
{
- basevalue = 0;
+ return -1; //No point attempting to move immobile units, or moving off the edges of the board
}
else if (board->Get(x2, y2) == NULL)
{
- basevalue = 0.5*IntrinsicWorth(x2, y2);
+ //If the position is empty...
+ Piece * closestEnemy = board->GetClosest(x2, y2, Piece::Opposite(piece->colour));
+ if (closestEnemy == NULL)
+ {
+ basevalue = 0.05*IntrinsicWorth(x2, y2); //Should never get this unless there are no enemies left
+ }
+ else
+ {
+ //Allocate score based on score of Combat with nearest enemy to the target square, decrease with distance between target square and the enemy
+ double multiplier = (double)(max<int>(board->Width(), board->Height()) - Board::NumberOfMoves(closestEnemy->x, closestEnemy->y, x2, y2)) / (double)(max<int>(board->Width(), board->Height()));
+
+ basevalue = CombatScore(closestEnemy->x, closestEnemy->y, piece)*multiplier*multiplier;
+
+ }
+
}
else if (board->Get(x2, y2)->colour != Piece::Opposite(piece->colour))
{
- basevalue = 0;
+ return -1; //The position is occupied by an ally, and so its pointless to try and move there
}
else
{
- Piece * defender = board->Get(x2, y2);
- double combatSuccess = CombatSuccessChance(piece, defender);
- basevalue = IntrinsicWorth(x2, y2)*combatSuccess*VictoryScore(piece, defender) + (1.0 - combatSuccess)*DefeatScore(piece, defender);
+ basevalue = CombatScore(x2, y2, piece); //The position is occupied by an enemy; compute combat score
+
}
if (basevalue > 0)
{
+ //Hack which decreases score for units that moved recently
+ //Does not decrease below a threshold (so that at the start of the game units will actually move!)
double oldValue = basevalue;
basevalue -= (double)(1.0/((double)(1.0 + (turnNumber - piece->lastMove))));
- if (basevalue < oldValue/8.0)
- basevalue = oldValue/8.0;
+ if (basevalue < oldValue/1000.0)
+ basevalue = oldValue/1000.0;
}
+
+ if (x2 == piece->lastx && y2 == piece->lasty) //Hack which decreases score for backtracking moves
+ basevalue = basevalue/100;
+
+ if (rand() % 10 == 0) //Hack which introduces some randomness by boosting one in every 10 scores
+ basevalue *= 4;
+ if (basevalue > 1)
+ basevalue = 1;
return basevalue;
}
if (strColour == "RED")
{
colour = Piece::RED;
- cout << "FBmSsnsnBn\n";
- cout << "BBCMccccyC\n";
- cout << "LSGmnsBsSm\n";
- cout << "sLSBLnLsss\n";
+ cout << "FB8sB479B8\n";
+ cout << "BB31555583\n";
+ cout << "6724898974\n";
+ cout << "967B669999\n";
}
else if (strColour == "BLUE")
{
colour = Piece::BLUE;
- cout << "sLSBLnLsss\n";
- cout << "LSGmnsBsSm\n";
- cout << "BBCMccccyC\n";
- cout << "FBmSsnsnBn\n";
+ cout << "967B669999\n";
+ cout << "6724898974\n";
+ cout << "BB31555583\n";
+ cout << "FB8sB479B8\n";
}
else
return INVALID_QUERY;
if (interpret != OK) {return interpret;}
//Forfax ignores the board state; he only uses the move result lines
-
+ #ifndef DEBUG
for (int y=0; y < board->Height(); ++y)
{
for (int x = 0; x < board->Width(); ++x)
if (cin.get() != '\n')
return NO_NEWLINE;
}
+ #endif //DEBUG
}
//Print chosen move to stdout
cout << choice.piece->x << " " << choice.piece->y << " " << direction << "\n";
-
+ //cerr << "\nForfax move " << choice.piece->x << " " << choice.piece->y << " " << direction << " [score = " << choice.score << "]\n";
Forfax::Status Forfax::InterpretMove()
{
//Variables to store move information
- int x; int y; string direction; string result = ""; int multiplier = 1; int attackerVal = (int)(Piece::BOMB); int defenderVal = (int)(Piece::BOMB);
-
+ int x; int y; string direction; string result = ""; int multiplier = 1;
+ Piece::Type attackerRank = Piece::NOTHING;
+ Piece::Type defenderRank = Piece::NOTHING;
//Read in information from stdin
cin >> x; cin >> y; cin >> direction; cin >> result;
stringstream s(buf);
cin >> buf;
s.clear(); s.str(buf);
- s >> attackerVal;
-
+ char temp;
+ s >> temp;
+ attackerRank = Piece::GetType(temp);
buf.clear();
cin >> buf;
s.clear(); s.str(buf);
- s >> defenderVal;
+ s >> temp;
+ defenderRank = Piece::GetType(temp);
}
}
- //Convert printed ranks into internal Piece::Type ranks
- Piece::Type attackerRank = Piece::Type(Piece::BOMB - attackerVal);
- Piece::Type defenderRank = Piece::Type(Piece::BOMB - defenderVal);
+
+
//If ranks were supplied, update the known ranks of the involved pieces
if (attackerRank != Piece::NOTHING && attacker != NULL)
{
- assert(attacker->minRank <= attackerRank && attacker->maxRank >= attackerRank);
+ //assert(attacker->minRank <= attackerRank && attacker->maxRank >= attackerRank);
attacker->minRank = attackerRank;
attacker->maxRank = attackerRank;
}
if (defenderRank != Piece::NOTHING && defender != NULL)
{
- assert(defender->minRank <= defenderRank && defender->maxRank >= defenderRank);
+ //assert(defender->minRank <= defenderRank && defender->maxRank >= defenderRank);
defender->minRank = defenderRank;
defender->maxRank = defenderRank;
//Update board and piece
board->Set(x2, y2, attacker);
board->Set(x, y, NULL);
+ attacker->lastx = attacker->x;
+ attacker->lasty = attacker->y;
attacker->x = x2;
attacker->y = y2;
}
board->Set(x2, y2, attacker);
board->Set(x, y, NULL);
+ attacker->lastx = attacker->x;
+ attacker->lasty = attacker->y;
attacker->x = x2;
attacker->y = y2;
*/
double Forfax::VictoryScore(Piece * attacker, Piece * defender) const
{
+
+ //If defender's rank is known, flags or bombs are worth more than usual
if (defender->minRank == defender->maxRank)
{
if (defender->minRank == Piece::FLAG)
else if (defender->minRank == Piece::BOMB)
return 0.9;
}
- return max<double>(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 0.6);
+ //Return average of normalised defender ranks
+ return max<double>(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 1);
}
/**
*/
double Forfax::DefeatScore(Piece * attacker, Piece * defender) const
{
- if (attacker->minRank == Piece::SPY)
- return 0.05;
-
- if (defender->minRank == defender->maxRank)
+
+ double result = 0;
+ if (defender->minRank == defender->maxRank) //If the defender's rank is known for certain...
{
- if (defender->minRank == Piece::BOMB)
- return 1 - (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
+ if (defender->minRank == Piece::BOMB) //Committing suicide to destroy bombs has a value that decreases with the attacker's rank
+ result = 1 - 0.5*(double)((double)(attacker->minRank) / (double)(Piece::BOMB));
+ else if (defender->minRank == Piece::FLAG)
+ result = 1; //Its impossible to lose to the flag anyway...
else
- return 0.5;
- }
+ {
+ //This is committing suicide on a higher ranked non-bomb enemy piece.
+ //Basically pointless, but the greater the attacker's rank the more pointless!
+ double temp = (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
+ result = 0.01*(1 - temp)*(1 - temp);
- double possibleRanks = 0; double totalRanks = 0;
- for (Piece::Type rank = Piece::NOTHING; rank <= Piece::BOMB; rank = Piece::Type((int)(rank) + 1))
+
+ }
+ }
+ else //The defender's rank is not known
{
- totalRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
- if (rank >= defender->minRank && rank <= defender->maxRank)
- possibleRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
+
+ //Score is allocated based on how much knowledge is gained by attacking defender
+ //The more possible ranks for the defender, the greater the score
+ //The score decreases as the rank of the attacker is increased.
+
+ double possibleRanks = 0; double totalRanks = 0; double bonus = 0;
+ for (Piece::Type rank = Piece::NOTHING; rank <= Piece::BOMB; rank = Piece::Type((int)(rank) + 1))
+ {
+ totalRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
+
+ if (rank >= defender->minRank && rank <= defender->maxRank)
+ {
+ possibleRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
+ if (rank == Piece::BOMB)
+ bonus += remainingUnits[(int)(defender->colour)][(int)(rank)];
+ if (rank == Piece::FLAG)
+ bonus += 2*remainingUnits[(int)(defender->colour)][(int)(rank)];
+ }
+
+ }
+
+
+ if (totalRanks > 0)
+ {
+ double multiplier = ((double)(Piece::BOMB) - (double)(attacker->minRank)) / (double)(Piece::BOMB);
+ result = (possibleRanks/totalRanks) * multiplier * multiplier;
+ }
+
+ result += bonus / totalRanks;
+ if (result > 1)
+ result = 1;
}
- if (totalRanks > 0)
- return (possibleRanks/totalRanks) - (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
- return 0;
-}
+ if (attacker->minRank == Piece::SPY) //Spies are slightly more valuable than usual since they kill the Marshal
+ result = result / 1.5;
+ return result;
+
+}
+
+/**
+ * Calculates a score indicating the worth of invoking combat in a square
+ * @param x The x coordinate
+ * @param y The y coordinate
+ * @param attacker The piece invoking the combat
+ * @returns A value between 0 in 1, with 0 indicating worthless (or no combat) and 1 indicating highest value
+ */
+double Forfax::CombatScore(int x, int y, Piece * attacker) const
+{
+ Piece * defender = board->Get(x, y);
+ if (defender == NULL)
+ return 0;
+ double combatSuccess = CombatSuccessChance(attacker, defender);
+ return IntrinsicWorth(x, y)*combatSuccess*VictoryScore(attacker, defender) + (1.0 - combatSuccess)*DefeatScore(attacker, defender);
+}
/**
* DEBUG - Print the board seen by Forfax to a stream