X-Git-Url: https://git.ucc.asn.au/?p=progcomp2012.git;a=blobdiff_plain;f=samples%2Fforfax%2Fforfax.cpp;h=a7e233bad5f875cedca4863b509b81258a6934fc;hp=729e2f962445a68a06e678743d1111baf40a9cb5;hb=b563784f7e8b559fc100e174331c99fc6a1beda8;hpb=041c37d1dfc4a94024fe1d329d289e4c59667885 diff --git a/samples/forfax/forfax.cpp b/samples/forfax/forfax.cpp index 729e2f9..a7e233b 100644 --- a/samples/forfax/forfax.cpp +++ b/samples/forfax/forfax.cpp @@ -17,6 +17,8 @@ #include #include +//#define DEBUG + using namespace std; @@ -27,7 +29,7 @@ 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','?'}; /** @@ -48,7 +50,7 @@ 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 * @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) { } @@ -61,7 +63,7 @@ Piece::Piece(int newX, int newY,const Colour & newColour) * @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) { @@ -265,6 +267,19 @@ Board::Direction Board::DirectionBetween(int x1, int y1, int x2, int y2) +} + +/** + * 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 } /** @@ -279,7 +294,8 @@ bool Board::ForgetPiece(Piece * forget) return false; vector & in = GetPieces(forget->colour); bool result = false; - for (vector::iterator i=in.begin(); i != in.end(); ++i) + vector::iterator i=in.begin(); + while (i != in.end()) { if ((*i) == forget) @@ -289,12 +305,61 @@ bool Board::ForgetPiece(Piece * 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(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; + + + + } /** @@ -303,6 +368,7 @@ bool Board::ForgetPiece(Piece * forget) 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)); } /** @@ -350,7 +416,7 @@ double Forfax::CombatSuccessChance(Piece * attacker, Piece * defender) const * 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 { @@ -366,32 +432,55 @@ 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(board->Width(), board->Height()) - Board::NumberOfMoves(closestEnemy->x, closestEnemy->y, x2, y2)) / (double)(max(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; } @@ -422,18 +511,18 @@ Forfax::Status Forfax::Setup() 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; @@ -475,7 +564,7 @@ Forfax::Status Forfax::MakeMove() 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) @@ -483,6 +572,7 @@ Forfax::Status Forfax::MakeMove() if (cin.get() != '\n') return NO_NEWLINE; } + #endif //DEBUG } @@ -515,7 +605,7 @@ Forfax::Status Forfax::MakeMove() //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"; @@ -535,8 +625,9 @@ Forfax::Status Forfax::MakeMove() 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; @@ -548,13 +639,15 @@ Forfax::Status Forfax::InterpretMove() 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); } @@ -568,9 +661,8 @@ Forfax::Status Forfax::InterpretMove() } - //Convert printed ranks into internal Piece::Type ranks - Piece::Type attackerRank = Piece::Type(Piece::BOMB - attackerVal); - Piece::Type defenderRank = Piece::Type(Piece::BOMB - defenderVal); + + @@ -589,13 +681,13 @@ Forfax::Status Forfax::InterpretMove() //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; @@ -635,6 +727,8 @@ Forfax::Status Forfax::InterpretMove() //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; } @@ -648,6 +742,8 @@ Forfax::Status Forfax::InterpretMove() board->Set(x2, y2, attacker); board->Set(x, y, NULL); + attacker->lastx = attacker->x; + attacker->lasty = attacker->y; attacker->x = x2; attacker->y = y2; @@ -810,6 +906,8 @@ double Forfax::IntrinsicWorth(int x, int y) const */ 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) @@ -817,7 +915,8 @@ double Forfax::VictoryScore(Piece * attacker, Piece * defender) const else if (defender->minRank == Piece::BOMB) return 0.9; } - return max(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 0.6); + //Return average of normalised defender ranks + return max(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 1); } /** @@ -828,30 +927,81 @@ double Forfax::VictoryScore(Piece * attacker, Piece * defender) const */ 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