SHARE
TWEET

Untitled

a guest Nov 19th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "MyStrategy.h"
  2. #include "mt19937ar.h"
  3.  
  4. #define _USE_MATH_DEFINES
  5. #include <cmath>
  6. #include <cstdlib>
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <time.h>
  11. #include <map>
  12.  
  13. using namespace model;
  14. using namespace std;
  15.  
  16. MyStrategy::MyStrategy() {
  17. }
  18.  
  19. std::ostream& operator<<(std::ostream& os, TrooperType troopType) {
  20.     switch (troopType) {
  21.     case COMMANDER:
  22.         os << "commander";
  23.         break;
  24.     case FIELD_MEDIC:
  25.         os << "medic";
  26.         break;
  27.     case SOLDIER:
  28.         os << "soldier";
  29.         break;
  30.     case SNIPER:
  31.         os << "sniper";
  32.         break;
  33.     case SCOUT:
  34.         os << "scout";
  35.         break;
  36.     case UNKNOWN_TROOPER:
  37.     default:
  38.         os << "unknown";
  39.         break;
  40.     }
  41.     return os;
  42. }
  43.  
  44. void shouldNotHappen(int line) {
  45.     std::cout << line << ": should not happen" << std::endl;
  46. }
  47.  
  48. #define SHOULD_NOT_HAPPEN shouldNotHappen(__LINE__)
  49.  
  50. MT19937AR randomer;
  51.  
  52. const World* gworld;
  53. const Game* ggame;
  54. const Trooper* gself;
  55. const Player* me;
  56.  
  57. #define MAX_TROOPERS 5
  58. #define MAX_PLAYERS 4
  59.  
  60. enum TriBool {
  61.     FALSE = 0,
  62.     MOST_LIKELY_FALSE = 1,
  63.     PROBABLY = 2,
  64.     MOST_LIKELY_TRUE = 3,
  65.     TRUE = 4
  66. };
  67.  
  68. TriBool triNot(TriBool p) {
  69.     return (TriBool)(TRUE - p);
  70. }
  71.  
  72. bool sure(TriBool triBool) {
  73.     if (triBool == TRUE || triBool == FALSE) return true;
  74.     return false;
  75. }
  76.  
  77. std::ostream& operator<<(std::ostream& os, const TriBool& triBool) {
  78.     switch (triBool)
  79.     {
  80.     case FALSE:
  81.         os << "false";
  82.         break;
  83.     case MOST_LIKELY_FALSE:
  84.         os << "most likely false";
  85.         break;
  86.     case PROBABLY:
  87.         os << "probably";
  88.         break;
  89.     case MOST_LIKELY_TRUE:
  90.         os << "most likely true";
  91.         break;
  92.     case TRUE:
  93.         os << "true";
  94.         break;
  95.     default:
  96.         break;
  97.     }
  98.     return os;
  99. }
  100.  
  101.  
  102. ostream& operator<<(ostream& os, const model::ActionType& action) {
  103.     switch (action)
  104.     {
  105.     case model::END_TURN:
  106.         os << "end turn";
  107.         break;
  108.     case model::MOVE:
  109.         os << "move";
  110.         break;
  111.     case model::SHOOT:
  112.         os << "shoot";
  113.         break;
  114.     case model::RAISE_STANCE:
  115.         os << "raise stance";
  116.         break;
  117.     case model::LOWER_STANCE:
  118.         os << "lower stance";
  119.         break;
  120.     case model::THROW_GRENADE:
  121.         os << "throw grenade";
  122.         break;
  123.     case model::USE_MEDIKIT:
  124.         os << "use medikit";
  125.         break;
  126.     case model::EAT_FIELD_RATION:
  127.         os << "eat field ration";
  128.         break;
  129.     case model::HEAL:
  130.         os << "heal";
  131.         break;
  132.     case model::REQUEST_ENEMY_DISPOSITION:
  133.         os << "request enemy disposition";
  134.         break;
  135.     case model::UNKNOWN_ACTION:
  136.     default:
  137.         os << "unknown";
  138.         break;
  139.     }
  140.     return os;
  141. }
  142.  
  143. ostream& operator<<(ostream& os, const model::TrooperStance& stance) {
  144.     switch (stance) {
  145.     case model::STANDING:
  146.         os << "standing";
  147.         break;
  148.     case model::KNEELING:
  149.         os << "kneeling";
  150.         break;
  151.     case model::PRONE:
  152.         os << "prone";
  153.         break;
  154.     default:
  155.         break;
  156.     }
  157.     return os;
  158. }
  159.  
  160.  
  161. typedef vector<vector<CellType> > CellMap;
  162.  
  163. // matrix of all step distances from some point
  164. typedef vector<vector<int> > StepMap;
  165.  
  166. // point on the map
  167. struct Point {
  168.     Point() {
  169.         x = -1;
  170.         y = -1;
  171.     }
  172.     Point(const Unit& unit) {
  173.         x = unit.getX();
  174.         y = unit.getY();
  175.     }
  176.     Point(int _x, int _y) {
  177.         x = _x;
  178.         y = _y;
  179.     }
  180.  
  181.     int getX() const {return x;}
  182.     int getY() const {return y;}
  183.  
  184.     Point operator+=(const Point& diff) {
  185.         x += diff.x;
  186.         y += diff.y;
  187.         return *this;
  188.     }
  189.  
  190.     Point operator+(const Point& diff) {
  191.         Point newPoint(*this);
  192.         newPoint += diff;
  193.         return newPoint;
  194.     }
  195.  
  196.     bool operator==(const Point& other) const {
  197.         return other.x == x && other.y == y;
  198.     }
  199.  
  200.     bool operator!=(const Point& other) const {
  201.         return !operator==(other);
  202.     }
  203.  
  204.     int x;
  205.     int y;
  206. };
  207.  
  208. // position - point + stance
  209. struct Position {
  210.     Point point;
  211.     TrooperStance stance;
  212.  
  213.     Position(Point point = Point(), TrooperStance stance = STANDING) :
  214.         point(point),
  215.         stance(stance)
  216.     {}
  217.     Position(int x, int y, TrooperStance stance) :
  218.         point(x,y),
  219.         stance(stance)
  220.     {}
  221.  
  222.     Position(const Trooper& trooper) :
  223.         point(trooper),
  224.         stance(trooper.getStance())
  225.     {}
  226.  
  227.     int getX() const { return point.getX(); }
  228.     int getY() const { return point.getY(); }
  229.     TrooperStance getStance() const { return stance; }
  230.  
  231.     bool operator==(const Position& other) const {
  232.         return point == other.point && stance == other.stance;
  233.     }
  234.     bool operator!=(const Position& other) const {
  235.         return !(operator==(other));
  236.     }
  237.  
  238.     operator Point() const { return point; }
  239. };
  240.  
  241. // check if point really in the map
  242. bool validPoint(const Point& point) {
  243.     return
  244.         point.x >= 0 &&
  245.         point.y >= 0 &&
  246.         point.x < gworld->getWidth() &&
  247.         point.y < gworld->getHeight();
  248. }
  249.  
  250. int getMoveCost(TrooperStance stance) {
  251.     if (stance == STANDING) return ggame->getStandingMoveCost();
  252.     if (stance == KNEELING) return ggame->getKneelingMoveCost();
  253.     if (stance == PRONE) return ggame->getProneMoveCost();
  254.     return 0;
  255. }
  256.  
  257. struct TrooperStateDiff {
  258.     int x;
  259.     int y;
  260.     int stance;
  261.     int actionPoints;
  262.     bool eatFieldRation;
  263.     int playerId;
  264.     int hitPoints;
  265.     bool plusGrenade;
  266.     bool plusMedikit;
  267.     bool plusRation;
  268.  
  269.     TrooperStateDiff() :
  270.         x(0),
  271.         y(0),
  272.         stance(0),
  273.         actionPoints(0),
  274.         eatFieldRation(0),
  275.         playerId(0),
  276.         hitPoints(0),
  277.         plusGrenade(false),
  278.         plusMedikit(false),
  279.         plusRation(false)
  280.     {}
  281.  
  282.     TrooperStateDiff(int x, int y, int stance = 0, int actionPoints = 0, bool eatFieldRation = false, int playerId = 0, int hitPoints = 0) :
  283.         x(x),
  284.         y(y),
  285.         stance(stance),
  286.         actionPoints(actionPoints),
  287.         eatFieldRation(eatFieldRation),
  288.         playerId(playerId),
  289.         hitPoints(hitPoints),
  290.         plusGrenade(false),
  291.         plusMedikit(false),
  292.         plusRation(false)
  293.     {}
  294. };
  295.  
  296. // creates new virtual trooper
  297. Trooper newVirtualTrooper(const Trooper& other, TrooperStateDiff diff = TrooperStateDiff()) {
  298.     double shootingRange = other.getShootingRange();
  299.     if (other.getType() == SNIPER) {
  300.         shootingRange -= diff.stance;
  301.     }
  302.     return Trooper(other.getId(), other.getX() + diff.x, other.getY() + diff.y, other.getPlayerId() + diff.playerId,
  303.         other.getTeammateIndex(), other.getPlayerId() + diff.playerId == me->getId() ? true : false, other.getType(), (TrooperStance)(other.getStance() + diff.stance),
  304.         other.getHitpoints() + diff.hitPoints, other.getMaximalHitpoints(), other.getActionPoints() + diff.actionPoints, other.getInitialActionPoints(),
  305.         other.getVisionRange(), shootingRange, other.getShootCost(),
  306.         other.getStandingDamage(), other.getKneelingDamage(), other.getProneDamage(), other.getDamage(),
  307.         other.isHoldingGrenade() || diff.plusGrenade,
  308.         other.isHoldingMedikit() || diff.plusMedikit,
  309.         other.isHoldingFieldRation() && !diff.eatFieldRation || diff.plusRation);
  310. }
  311.  
  312. bool operator==(const Trooper& the, const Trooper& other) {
  313.     return
  314.         the.getId() == other.getId() &&
  315.         the.getX() == other.getX() &&
  316.         the.getY() == other.getY() &&
  317.         the.getStance() == other.getStance() &&
  318.         the.getHitpoints() == other.getHitpoints() &&
  319.         the.getActionPoints() == other.getActionPoints() &&
  320.         the.isHoldingGrenade() == other.isHoldingGrenade() &&
  321.         the.isHoldingMedikit() == other.isHoldingMedikit() &&
  322.         the.isHoldingFieldRation() == other.isHoldingFieldRation();
  323. }
  324.  
  325. struct SubMove {
  326.     int subMove;
  327.     int subsubMove;
  328.     SubMove() {
  329.         subMove = -1;
  330.         subsubMove = 0;
  331.     }
  332.     SubMove(int subMove, int subsubMove = 0) :
  333.         subMove(subMove),
  334.         subsubMove(subsubMove)
  335.     {}
  336.     operator int() const { return subMove; }
  337. };
  338.  
  339. enum Mode {
  340.     TRAVEL = 0,
  341.     COMBAT = 1,
  342.     AFTER_COMBAT = 2
  343. };
  344.  
  345. enum Tactics {
  346.     HIDE = 0,
  347.     DEFENSIVE = 1,
  348.     NORMAL = 2,
  349.     AGRESSIVE = 3,
  350.     RUSH = 4
  351. };
  352.  
  353. std::ostream& operator<<(std::ostream& os, const Tactics& tactics) {
  354.     switch (tactics)
  355.     {
  356.     case HIDE:
  357.         os << "hide";
  358.         break;
  359.     case DEFENSIVE:
  360.         os << "defensive";
  361.         break;
  362.     case NORMAL:
  363.         os << "normal";
  364.         break;
  365.     case AGRESSIVE:
  366.         os << "agressive";
  367.         break;
  368.     case RUSH:
  369.         os << "rush";
  370.         break;
  371.     default:
  372.         break;
  373.     }
  374.     return os;
  375. }
  376.  
  377. std::ostream& operator<<(std::ostream& os, const Mode& mode) {
  378.     switch (mode)
  379.     {
  380.     case TRAVEL:
  381.         os << "travel";
  382.         break;
  383.     case COMBAT:
  384.         os << "combat";
  385.         break;
  386.     case AFTER_COMBAT:
  387.         os << "after combat";
  388.         break;
  389.     default:
  390.         break;
  391.     }
  392.     return os;
  393. }
  394.  
  395. typedef struct Hit {
  396.     int damage;
  397.     Trooper trooper;
  398.     double prob;
  399.     Hit(const Trooper& trooper, int damage, double prob = 1.) :
  400.         damage(damage),
  401.         trooper(trooper),
  402.         prob(prob)
  403.     {}
  404. } Hit;
  405.  
  406. // each trooper action can be described with this structure
  407. struct Action {
  408.     ActionType actionType;
  409.     int x;
  410.     int y;
  411.     double damage;
  412.     // action points used for the action
  413.     int actionPoints;
  414.     int troopersKilled;
  415.     int troopersKilledLater;
  416.     int priority;
  417.     vector<std::pair<Hit,SubMove> > hits;
  418.    
  419.     Action() :
  420.         actionType(END_TURN),
  421.         x(-1),
  422.         y(-1),
  423.         damage(0),
  424.         actionPoints(0),
  425.         troopersKilled(0),
  426.         troopersKilledLater(0),
  427.         priority(0),
  428.         hits()
  429.     {}
  430. };
  431.  
  432. // whole info about each player
  433. class PlayerInfo {
  434.     long long id;
  435.     // whether it turns after me
  436.     TriBool afterMe;
  437.     bool dead[MAX_TROOPERS];
  438. public:
  439.     PlayerInfo(long long id = 0) :
  440.         id(id),
  441.         afterMe(PROBABLY),
  442.         lastScore(0),
  443.         lastScoreDiff(0),
  444.         approximatePosition(),
  445.         averageSpeed(5)
  446.     {
  447.         for (int i = 0; i < MAX_TROOPERS; i++) {
  448.             dead[i] = false;
  449.         }
  450.     }
  451.  
  452.     Point approximatePosition;
  453.     double averageSpeed;
  454.     long long getId() { return id; };
  455.     int lastScore;
  456.     int lastScoreDiff;
  457.  
  458.     void setDead(TrooperType type) {
  459.         if (!dead[type]) {
  460.             std::cout << "Player " << id << " has lost his trooper: " << type << std::endl;
  461.         }
  462.         dead[type] = true;
  463.     }
  464.  
  465.     void setAlive(TrooperType type) {
  466.         if (dead[type]) {
  467.             std::cout << "Player " << id << " trooper revived: " << type << std::endl;
  468.         }
  469.         dead[type] = false;
  470.     }
  471.  
  472.     bool isDead(TrooperType type) const {
  473.         return dead[type];
  474.     }
  475.  
  476.     void setAfterMe(TriBool newAfterMe) {
  477.         if (sure(afterMe)) {
  478.             if (sure(newAfterMe) && newAfterMe != afterMe) {
  479.                 SHOULD_NOT_HAPPEN;
  480.             }
  481.         } else if (sure(newAfterMe) || afterMe == PROBABLY) {
  482.             std::cout << "Player " << id << " turns after me: " << newAfterMe << std::endl;
  483.             afterMe = newAfterMe;
  484.         } else {
  485.             afterMe = (TriBool)((afterMe + newAfterMe) /2);
  486.         }
  487.     }
  488.     TriBool getAfterMe() const { return afterMe; }
  489. };
  490.  
  491. enum Map {
  492.     DEFAULT = 0,
  493.     MAP1 = 1,
  494.     MAP2 = 2,
  495.     MAP3 = 3,
  496.     MAP4 = 4,
  497.     MAP5 = 5,
  498.     MAP6 = 6,
  499.     CHEESER = 7,
  500.     FEFER = 8,
  501.     UNKNOWN = 9
  502. };
  503.  
  504. // use this structure to save whole information of enemy shoot
  505. typedef struct LastShooted {
  506.     // who was hit
  507.     Trooper teammate;
  508.     // who can hit
  509.     vector<Trooper> possibleEnemies;
  510.     // approximate position of all players who can do this hit
  511.     vector<Point> approxPositions;
  512.     // when we discovered this shoot
  513.     SubMove subMove;
  514.     int damage;
  515.     bool fatal;
  516.     LastShooted(const Trooper& teammate = Trooper()) :
  517.         teammate(teammate),
  518.         possibleEnemies(),
  519.         approxPositions(),
  520.         subMove(-1),
  521.         damage(0),
  522.         fatal(false)
  523.     {}
  524. } LastShooted;
  525.  
  526. // global variables
  527.  
  528. Map mapType = UNKNOWN;
  529.  
  530. typedef std::pair<double, Trooper> TrooperProb;
  531.  
  532. // map of all possible enemy troopers on the map
  533. vector<vector<vector<TrooperProb> > > trooperProbs;
  534.  
  535. // where we saw each trooper last time
  536. typedef pair<Trooper, SubMove> LastSeen;
  537. vector<LastSeen> lastSeen;
  538. SubMove lastSeenEnemy;
  539.  
  540. // store all enemy shoots here
  541. vector<LastShooted> lastShooted;
  542.  
  543. int maxTroops = 0;
  544. vector<int> troopOrder;
  545. vector<int> troopOrderRev;
  546. int curTroopIndex;
  547.  
  548. std::vector<PlayerInfo> playerInfo;
  549.  
  550. // who is leader now
  551. int leader;
  552.  
  553. Point globalTarget;
  554. SubMove gtLastUpdated;
  555. bool randomTarget = false;
  556.  
  557. // matrix of all step distances between each pair of points
  558. std::vector<std::vector<StepMap> > allStepMaps;
  559.  
  560. // map of step distances to global target
  561. StepMap* globalTargetStepMap = 0;
  562. // the same but treating all troopers as obstacle
  563. StepMap globalTargetStepMapTroopers;
  564. // the same but treating all troopers but self as obstacle
  565. StepMap globalTargetStepMapTroopersNoSelf;
  566.  
  567. // the player I attack now
  568. int attackPlayerId = -1;
  569.  
  570. // point there trooper started this turn
  571. Point startPoint;
  572.  
  573. SubMove currentSubMove;
  574.  
  575. // who turned previos time (differs from previous trooper if it is dead)
  576. SubMove prevSubMove;
  577.  
  578. typedef vector<vector<int> > Fog;
  579.  
  580. // constant fog map there all cells are in fog
  581. Fog allInFog;
  582.  
  583. // fog of current trooper
  584. Fog currentFog;
  585. // the same for sniper
  586. Fog currentFogSniper;
  587.  
  588. // store last fogs for all troopers
  589. deque<Fog> lastFogs[MAX_TROOPERS];
  590. deque<Fog> lastFogsSniper[MAX_TROOPERS];
  591.  
  592. // then we changed mode last time
  593. SubMove lastModeChange;
  594. Mode currentMode = TRAVEL;
  595.  
  596. Tactics tactics = NORMAL;
  597.  
  598. // store hits that I expect
  599. vector<std::pair<Hit, SubMove> > expectedHits;
  600. // store succeeded hits to possible enemies
  601. vector<std::pair<Hit, SubMove> > succeededHits;
  602. // store failed hits to possible enemies
  603. vector<std::pair<Hit, SubMove> > failedHits;
  604.  
  605. LastSeen& getLastSeen(int playerId, TrooperType ttype, bool* found) {
  606.     for (int i = 0; i < (int)lastSeen.size(); i++) {
  607.         if (lastSeen[i].first.getPlayerId() == playerId &&
  608.             lastSeen[i].first.getType() == ttype) {
  609.             *found = true;
  610.             return lastSeen[i];
  611.         }
  612.     }
  613.  
  614.     *found = false;
  615.     return lastSeen[0];
  616. }
  617.  
  618. int numLeftTroopers(const PlayerInfo& pInfo) {
  619.     int liveTroopers = maxTroops;
  620.     for (int i = 0; i < maxTroops; i++) {
  621.         if (pInfo.isDead((TrooperType)i) == true) liveTroopers--;
  622.     }
  623.     return liveTroopers;
  624. }
  625.  
  626. int numLeftPlayers() {
  627.     int livePlayers = 0;
  628.     for (int i = 1; i < (int)playerInfo.size(); i++) {
  629.         if (numLeftTroopers(playerInfo[i]) > 0) livePlayers++;
  630.     }
  631.     return livePlayers;
  632. }
  633.  
  634. Point nearestFree(Point point) {
  635.     const CellMap& cellMap = gworld->getCells();
  636.    
  637.     for (int i = 0; i < 100; i++) {
  638.         for (int k = 0; k < i+1; k++) {
  639.             Point near;
  640.             near = point + Point(i,i-k); if (validPoint(near) && cellMap[near.getX()][near.getY()] == FREE) return near;
  641.             near = point + Point(-i,i-k); if (validPoint(near) && cellMap[near.getX()][near.getY()] == FREE) return near;
  642.             near = point + Point(i,-i+k); if (validPoint(near) && cellMap[near.getX()][near.getY()] == FREE) return near;
  643.             near = point + Point(-i,-i+k); if (validPoint(near) && cellMap[near.getX()][near.getY()] == FREE) return near;
  644.         }
  645.     }
  646.     return point;
  647. }
  648.  
  649. // get number of steps from x,y to target in stepMap even if
  650. // x,y is trooper obstacle
  651. int getStepsTroopers(int x, int y, StepMap& stepMap) {
  652.     if (stepMap[x][y] >= 0) return stepMap[x][y];
  653.     Point near;
  654.     int minPath = 1000;
  655.     near = Point(x,y+1);
  656.     if (validPoint(near) && stepMap[near.x][near.y] >= 0 &&
  657.         stepMap[near.x][near.y] + 1 < minPath) {
  658.         minPath = stepMap[near.x][near.y] + 1;
  659.     }
  660.     near = Point(x,y-1);
  661.     if (validPoint(near) && stepMap[near.x][near.y] >= 0 &&
  662.         stepMap[near.x][near.y] + 1 < minPath) {
  663.         minPath = stepMap[near.x][near.y] + 1;
  664.     }
  665.     near = Point(x+1,y);
  666.     if (validPoint(near) && stepMap[near.x][near.y] >= 0 &&
  667.         stepMap[near.x][near.y] + 1 < minPath) {
  668.         minPath = stepMap[near.x][near.y] + 1;
  669.     }
  670.     near = Point(x-1,y);
  671.     if (validPoint(near) && stepMap[near.x][near.y] >= 0 &&
  672.         stepMap[near.x][near.y] + 1 < minPath) {
  673.         minPath = stepMap[near.x][near.y] + 1;
  674.     }
  675.     return minPath;
  676. }
  677.  
  678. void initStepMap(const CellMap& cellMap, StepMap& stepMap, int maxStep = 1000, bool placeTroopers = false) {
  679.     stepMap.resize(cellMap.size());
  680.     for (int x = 0; x < (int)cellMap.size(); x++) {
  681.         stepMap[x].resize(cellMap[x].size());
  682.         for (int y = 0; y < (int)cellMap[x].size(); y++) {
  683.             if (cellMap[x][y] == FREE) {
  684.                 stepMap[x][y] = maxStep;
  685.             } else {
  686.                 stepMap[x][y] = -1;
  687.             }
  688.         }
  689.     }
  690.  
  691.     if (placeTroopers) {
  692.         for (size_t i = 0; i < gworld->getTroopers().size(); ++i) {
  693.             const Trooper& trooper = gworld->getTroopers()[i];
  694.             if (trooper.getId() != gself->getId()) {
  695.                 stepMap[trooper.getX()][trooper.getY()] = -1;
  696.             }
  697.         }
  698.     }
  699. }
  700.  
  701. void computeStepMap(Point point, StepMap& stepMap) {
  702.     queue<Point> active;
  703.     active.push(point);
  704.     stepMap[point.getX()][point.getY()] = 0;
  705.  
  706.     while(active.size()) {
  707.         Point curr = active.front();
  708.         int curStep = stepMap[curr.getX()][curr.getY()];
  709.         active.pop();
  710.  
  711.         Point near;
  712.         near = curr + Point(1,0); if (validPoint(near) && curStep+1 < stepMap[near.x][near.y]) {stepMap[near.x][near.y] = curStep+1; active.push(near);}
  713.         near = curr + Point(0,1); if (validPoint(near) && curStep+1 < stepMap[near.x][near.y]) {stepMap[near.x][near.y] = curStep+1; active.push(near);}
  714.         near = curr + Point(-1,0); if (validPoint(near) && curStep+1 < stepMap[near.x][near.y]) {stepMap[near.x][near.y] = curStep+1; active.push(near);}
  715.         near = curr + Point(0,-1); if (validPoint(near) && curStep+1 < stepMap[near.x][near.y]) {stepMap[near.x][near.y] = curStep+1; active.push(near);}
  716.     }
  717. }
  718.  
  719. void addLastSeen(const Trooper& trooper, SubMove subMove, int i = -1) {
  720.     if (i == -1) {
  721.         // new trooper
  722.         lastSeen.push_back(std::pair<Trooper, SubMove>(trooper, subMove));
  723.     } else {
  724.         lastSeen[i].first = trooper;
  725.         lastSeen[i].second = subMove;
  726.     }
  727. }
  728.  
  729. // calculates number of turns the trooper did since specified submove
  730. // returns integer if it is known or n+0.5 if it can be n or n+1
  731. double numTurnsSinceSubMove(const Trooper& trooper, SubMove subMove) {
  732.     int playerId = (int)trooper.getPlayerId();
  733.  
  734.     int i = troopOrderRev[trooper.getType()];
  735.  
  736.     // how many submoves ago this type of trooper turns
  737.     int moveDiff = curTroopIndex - i;
  738.     if (moveDiff < 0) moveDiff += maxTroops;
  739.  
  740.     // how many submoves passed since that submove
  741.     int seeDiff = currentSubMove - subMove;
  742.  
  743.     // special case if we didn't see it yet
  744.     if (subMove == -1 && curTroopIndex == maxTroops-1 && moveDiff == 0) {
  745.         seeDiff--;
  746.     }
  747.  
  748.     int turns = seeDiff / maxTroops;
  749.     seeDiff -= turns * maxTroops;
  750.  
  751.     if (seeDiff == 0) return (double)turns; // I saw him myself!
  752.  
  753.     if (seeDiff < moveDiff) {
  754.         return (double)turns;
  755.     } else if (seeDiff > moveDiff) {
  756.         if (moveDiff == 0) {
  757.             // troop with the same order, if he turns before me, he is gone,
  758.             // if after - he is still there
  759.             if (playerInfo[playerId].getAfterMe() <= MOST_LIKELY_FALSE) {
  760.                 return (double)turns + 1.;
  761.             } else if (playerInfo[playerId].getAfterMe() == PROBABLY) {
  762.                 return (double)turns + 0.5;
  763.             } else {
  764.                 /* (playerInfo[playerId].afterMe >= MOST_LIKELY_TRUE) */
  765.                 return (double)turns;
  766.             }
  767.         } else {
  768.             return (double)turns + 1.;
  769.         }
  770.     } else {
  771.         if (subMove == -1) return turns;
  772.         if (playerInfo[playerId].getAfterMe() >= MOST_LIKELY_TRUE) {
  773.             return (double)turns + 1.;
  774.         } else if (playerInfo[playerId].getAfterMe() == PROBABLY) {
  775.             return (double)turns + 0.5;
  776.         } else {
  777.             /* (playerInfo[playerId].afterMe <= MOST_LIKELY_FALSE) */
  778.             return turns;
  779.         }
  780.     }
  781. }
  782.  
  783. double numTurnsSinceLastSeen(const LastSeen& vTrooper) {
  784.     return numTurnsSinceSubMove(vTrooper.first, vTrooper.second);
  785. }
  786.  
  787. TriBool stillThere(const LastSeen& vTrooper) {
  788.     if (vTrooper.first.isTeammate()) {
  789.         if (vTrooper.second == currentSubMove) {
  790.             return TRUE;
  791.         } else {
  792.             // killed
  793.             return FALSE;
  794.         }
  795.     }
  796.  
  797.     // here need to analyse whether this player turns before me or after
  798.     int playerId = (int)vTrooper.first.getPlayerId();
  799.  
  800.     int i = troopOrderRev[vTrooper.first.getType()];
  801.  
  802.     int moveDiff = curTroopIndex - i;
  803.     if (moveDiff < 0) moveDiff += maxTroops;
  804.  
  805.     int seeDiff = currentSubMove - vTrooper.second;
  806.  
  807.     if (seeDiff == 0) return TRUE; // I saw him myself!
  808.  
  809.     if (seeDiff < moveDiff) {
  810.         return TRUE;
  811.     } else if (seeDiff > moveDiff) {
  812.         if (moveDiff == 0 && seeDiff < maxTroops) {
  813.             // troop with the same order, if he turns before me, he is gone,
  814.             // if after - he is still there
  815.             return playerInfo[playerId].getAfterMe();
  816.         } else {
  817.             return FALSE;
  818.         }
  819.     } else {
  820.         return triNot(playerInfo[playerId].getAfterMe());
  821.     }
  822. }
  823.  
  824. bool isDead(const Trooper& vTrooper) {
  825.     return playerInfo[(int)vTrooper.getPlayerId()].isDead(vTrooper.getType());
  826. }
  827.  
  828. TriBool stillThere(const Trooper& trooper) {
  829.     if (isDead(trooper)) return FALSE;
  830.     for (int i = 0; i < (int)lastSeen.size(); i++) {
  831.         if (lastSeen[i].first.getPlayerId() == trooper.getPlayerId() &&
  832.             lastSeen[i].first.getType() == trooper.getType()) {
  833.             return stillThere(lastSeen[i]);
  834.         }
  835.     }
  836.     return FALSE;
  837. }
  838.  
  839. int findFastestMove(const StepMap& stepMap, TrooperStance curStance, Position target, TrooperStance* moveStance = 0) {
  840.     TrooperStance targetStance = target.stance;
  841.     int numSteps = stepMap[target.getX()][target.getY()];
  842.     TrooperStance maxStance = (TrooperStance)std::max(curStance, targetStance);
  843.  
  844.     if (numSteps <= 1) {
  845.         if (moveStance) *moveStance = maxStance;
  846.         return (maxStance - curStance) * ggame->getStanceChangeCost() + numSteps * getMoveCost(maxStance) + (maxStance - targetStance) * ggame->getStanceChangeCost();
  847.     } else {
  848.         if (moveStance) *moveStance = STANDING;
  849.         return (STANDING - curStance) * ggame->getStanceChangeCost() + numSteps * ggame->getStandingMoveCost() + (STANDING - targetStance) * ggame->getStanceChangeCost();
  850.     }
  851. }
  852.  
  853. int actionCost(Trooper trooper, ActionType action) {
  854.     switch (action)
  855.     {
  856.     case model::UNKNOWN_ACTION:
  857.     case model::END_TURN:
  858.         return 0;
  859.     case model::MOVE:
  860.         return getMoveCost(trooper.getStance());
  861.     case model::SHOOT:
  862.         return trooper.getShootCost();
  863.     case model::RAISE_STANCE:
  864.     case model::LOWER_STANCE:
  865.         return ggame->getStanceChangeCost();
  866.     case model::THROW_GRENADE:
  867.         return ggame->getGrenadeThrowCost();
  868.     case model::USE_MEDIKIT:
  869.         return ggame->getMedikitUseCost();
  870.     case model::EAT_FIELD_RATION:
  871.         return ggame->getFieldRationEatCost();
  872.     case model::HEAL:
  873.         return ggame->getFieldMedicHealCost();
  874.     case model::REQUEST_ENEMY_DISPOSITION:
  875.         return ggame->getCommanderRequestEnemyDispositionCost();
  876.     default:
  877.         return 0;
  878.     }
  879. }
  880.  
  881. // returns true if enemy trooper turns later than mine
  882. TriBool turnsLater(const Trooper& enemyTrooper, const Trooper& myTrooper) {
  883.     int t1 = troopOrderRev[enemyTrooper.getType()];
  884.     int t2 = troopOrderRev[myTrooper.getType()];
  885.  
  886.     t1 -= curTroopIndex;
  887.     t2 -= curTroopIndex;
  888.  
  889.     if (t1 < 0) t1 += maxTroops;
  890.     if (t2 < 0) t2 += maxTroops;
  891.  
  892.     if (t1 == 0) {
  893.         if (t2 == 0) return FALSE;
  894.         return triNot(playerInfo[(int)enemyTrooper.getPlayerId()].getAfterMe());
  895.     }
  896.  
  897.     if (t1 < t2) return FALSE;
  898.     if (t1 > t2) return TRUE;
  899.  
  900.     return playerInfo[(int)enemyTrooper.getPlayerId()].getAfterMe();
  901. }
  902.  
  903. std::ostream& operator<<(std::ostream& os, const Trooper& trooper) {
  904.     os << trooper.getPlayerId() << (trooper.isTeammate() ? "" : " (enemy)") << " " << trooper.getType();
  905.     return os;
  906. }
  907.  
  908. static long long lastId = 0;
  909.  
  910. // structure that describes whole target for trooper
  911. struct Target {
  912.     // where to hide
  913.     Position hidePosition;
  914.     Action action;
  915.     // where to action
  916.     Position actionPosition;
  917.     long long id;
  918.     int score;
  919.     double scoreNextTurn;
  920.     int safety;
  921.     int priority;
  922.     bool eatRation;
  923.     bool throwGrenade;
  924.     vector<std::pair<Hit, SubMove> > hits;
  925.     double visibileProb;
  926.  
  927.     Target(int hitPoints) :
  928.         safety(hitPoints),
  929.         priority(0),
  930.         score(0),
  931.         scoreNextTurn(0.),
  932.         eatRation(false),
  933.         throwGrenade(false),
  934.         id(lastId++),
  935.         hits(),
  936.         visibileProb(1.)
  937.     {}
  938. };
  939.  
  940. ostream& operator<<(ostream& os, const Action& action) {
  941.     os << action.actionType;
  942.     if (action.actionType != END_TURN) {
  943.         os << " to " << action.x << "," << action.y;
  944.     }
  945.     return os;
  946. }
  947.  
  948. ostream& operator<<(ostream& os, const Target& target) {
  949.     os << target.action << " from " << target.actionPosition.getX() << "," << target.actionPosition.getY() << " then hide to " <<
  950.         target.hidePosition.getX() << "," << target.hidePosition.getY() << "(score=" << target.score << ", safety=" << target.safety << ")";
  951.     return os;
  952. }
  953.  
  954. ostream& operator<<(ostream& os, const Point& point) {
  955.     os << point.x << "," << point.y;
  956.     return os;
  957. }
  958.  
  959. ostream& operator<<(ostream& os, const Position& pos) {
  960.     os << pos.point << "," << pos.stance;
  961.     return os;
  962. }
  963.  
  964. int manhattanDistance(const Point& p1, const Point& p2) {
  965.     return abs(p1.x - p2.x) + abs(p1.y - p2.y);
  966. }
  967.  
  968. int stepDistance(const Point& p1, const Point p2) {
  969.     const StepMap& stepMap = allStepMaps[p1.getX()][p1.getY()];
  970.     return stepMap[p2.getX()][p2.getY()];
  971. }
  972.  
  973. int squareDist(int x1, int y1, int x2, int y2) {
  974.     return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
  975. }
  976.  
  977. int squareDist(const Unit& unit, int x, int y) {
  978.     return squareDist(unit.getX(), unit.getY(), x, y);
  979. }
  980.  
  981. int squareDist(const Unit& unit1, const Unit& unit2) {
  982.     return squareDist(unit1.getX(), unit1.getY(), unit2.getX(), unit2.getY());
  983. }
  984.  
  985. int squareDist(const Unit& unit, const Point& point) {
  986.     return squareDist(unit.getX(), unit.getY(), point.getX(), point.getY());
  987. }
  988.  
  989. int squareDist(const Point& p1, const Point& p2) {
  990.     return squareDist(p1.getX(), p1.getY(), p2.getX(), p2.getY());
  991. }
  992.  
  993. bool weSeeIt(const Trooper& enemy) {
  994.     const vector<Trooper>& troopers = gworld->getTroopers();
  995.     for (size_t i = 0; i < troopers.size(); ++i) {
  996.         Trooper trooper = troopers.at(i);
  997.  
  998.         double visionRange = trooper.getVisionRange();
  999.         if (enemy.getType() == SNIPER && trooper.getType() != SCOUT) {
  1000.             // see panalty
  1001.             if (enemy.getStance() == KNEELING) visionRange-= 0.5;
  1002.             if (enemy.getStance() == PRONE) visionRange-= 1.;
  1003.         }
  1004.  
  1005.         if (trooper.isTeammate()) {
  1006.             if (gworld->isVisible(visionRange,  
  1007.                 trooper.getX(), trooper.getY(), trooper.getStance(),        
  1008.                 enemy.getX(), enemy.getY(), enemy.getStance())) {
  1009.                 return true;
  1010.             }
  1011.         }
  1012.     }
  1013.     return false;
  1014. }
  1015.  
  1016. void initCurrentFog() {
  1017.     currentFog.resize(gworld->getWidth());
  1018.     currentFogSniper.resize(gworld->getWidth());
  1019.     for (int x = 0; x < gworld->getWidth(); x++) {
  1020.         currentFog[x].resize(gworld->getHeight());
  1021.         currentFogSniper[x].resize(gworld->getHeight());
  1022.         for (int y = 0; y < gworld->getHeight(); y++) {
  1023.             const vector<Trooper>& troopers= gworld->getTroopers();
  1024.  
  1025.             int fog = _TROOPER_STANCE_COUNT_;
  1026.             for (size_t i = 0; i < troopers.size(); ++i) {
  1027.                 Trooper trooper = troopers.at(i);
  1028.  
  1029.                 double visionRange = trooper.getVisionRange();
  1030.                 if (trooper.isTeammate()) {
  1031.                     for (int i = fog-1; i >= 0; i--) {
  1032.                         if (gworld->isVisible(visionRange,  
  1033.                             trooper.getX(), trooper.getY(), trooper.getStance(),        
  1034.                             x, y, (TrooperStance)i)) {
  1035.                             fog = i;
  1036.                         } else {
  1037.                             break;
  1038.                         }
  1039.                     }
  1040.                 }
  1041.             }
  1042.             currentFog[x][y] = fog; // fog = KNEELING means that we see KNEELING and higher
  1043.  
  1044.             fog = _TROOPER_STANCE_COUNT_;
  1045.             for (size_t i = 0; i < troopers.size(); ++i) {
  1046.                 Trooper trooper = troopers.at(i);
  1047.                 double visionRange = trooper.getVisionRange();
  1048.  
  1049.                 if (trooper.isTeammate()) {
  1050.                     if (trooper.getType() != SCOUT) {
  1051.                         visionRange -= (double)(_TROOPER_STANCE_COUNT_ - fog)* 0.5;
  1052.                     }
  1053.                     for (int i = fog-1; i >= 0; i--) {
  1054.                         if (gworld->isVisible(visionRange,  
  1055.                             trooper.getX(), trooper.getY(), trooper.getStance(),        
  1056.                             x, y, (TrooperStance)i)) {
  1057.                             fog = i;
  1058.                             visionRange -= 0.5;
  1059.                         } else {
  1060.                             break;
  1061.                         }
  1062.                     }
  1063.                 }
  1064.             }
  1065.             currentFogSniper[x][y] = fog; // fog = KNEELING means that we see KNEELING and higher
  1066.         }
  1067.     }
  1068. }
  1069.  
  1070. double updateFog(Fog& fog, Fog& fogSniper, const Trooper& trooper) {
  1071.     double revealPossibleEnemies = 0.;
  1072.     if (!trooper.isTeammate()) return 0;
  1073.     for (int x = 0; x < gworld->getWidth(); x++) {
  1074.         for (int y = 0; y < gworld->getHeight(); y++) {
  1075.             double visionRange = trooper.getVisionRange();
  1076.             for (int i = fog[x][y]-1; i >= 0; i--) {
  1077.                 if (gworld->isVisible(visionRange,  
  1078.                     trooper.getX(), trooper.getY(), trooper.getStance(),        
  1079.                     x, y, (TrooperStance)i)) {
  1080.                     if (trooperProbs[x][y].size() > 0) {
  1081.                         for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
  1082.                             if (trooperProbs[x][y][p].second.getType() != SNIPER) {
  1083.                                 revealPossibleEnemies += trooperProbs[x][y][p].first;
  1084.                             }
  1085.                         }
  1086.                     }
  1087.                     fog[x][y] = i;
  1088.                 } else {
  1089.                     break;
  1090.                 }
  1091.             }
  1092.  
  1093.             // the same for sniper
  1094.             if (trooper.getType() != SCOUT) {
  1095.                 visionRange -= (double)(_TROOPER_STANCE_COUNT_ - fogSniper[x][y]) * 0.5;
  1096.             }
  1097.  
  1098.             for (int i = fogSniper[x][y]-1; i >= 0; i--) {
  1099.                 if (gworld->isVisible(visionRange,  
  1100.                     trooper.getX(), trooper.getY(), trooper.getStance(),        
  1101.                     x, y, (TrooperStance)i)) {
  1102.                     if (trooperProbs[x][y].size() > 0) {
  1103.                         for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
  1104.                             if (trooperProbs[x][y][p].second.getType() == SNIPER) {
  1105.                                 revealPossibleEnemies += trooperProbs[x][y][p].first;
  1106.                             }
  1107.                         }
  1108.                     }
  1109.                     fogSniper[x][y] = i;
  1110.                     visionRange -= 0.5;
  1111.                 } else {
  1112.                     break;
  1113.                 }
  1114.             }
  1115.         }
  1116.     }
  1117.     return revealPossibleEnemies;
  1118. }
  1119.  
  1120. bool inFog(const Position& pos, const Fog& fog) {
  1121.     return fog[pos.getX()][pos.getY()] > pos.stance;
  1122. }
  1123.  
  1124. bool inFog(int x, int y, TrooperStance stance, const Fog& fog) {
  1125.     return fog[x][y] > stance;
  1126. }
  1127.  
  1128. // check if this trooper can do this damage
  1129. // or greater if 'greater' flag is specified
  1130. bool canDoThisDamage(const Trooper& trooper, int damage, bool* hasGrenade, bool* hasFieldRation, int actionPoints = -1, bool greater = false) {
  1131.     if (actionPoints == -1) {
  1132.         // top call, compute action points
  1133.         actionPoints = trooper.getInitialActionPoints();
  1134.         if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT) {
  1135.             actionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
  1136.         }
  1137.  
  1138.         bool hg = *hasGrenade;
  1139.         bool hf = false;
  1140.         if (canDoThisDamage(trooper, damage, &hg, &hf, actionPoints, greater)) {
  1141.             *hasGrenade = hg;
  1142.             return true;
  1143.         }
  1144.  
  1145.         if (*hasFieldRation) {
  1146.             // also try to eat field ration
  1147.             actionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
  1148.             *hasFieldRation = false;
  1149.  
  1150.             return canDoThisDamage(trooper, damage, hasGrenade, hasFieldRation, actionPoints, greater);
  1151.         }
  1152.         return false;
  1153.     }
  1154.  
  1155.     if (actionPoints < 0) return false;
  1156.  
  1157.     if (damage < 0) {
  1158.         if (greater) {
  1159.             return true;
  1160.         } else {
  1161.             return false;
  1162.         }
  1163.     }
  1164.  
  1165.     if (damage == 0) return true;
  1166.  
  1167.     bool canDoThis;
  1168.     bool hg = false;
  1169.     bool hf = false;
  1170.     canDoThis = canDoThisDamage(trooper, damage - trooper.getStandingDamage(), &hg, &hf, actionPoints - trooper.getShootCost(), greater);
  1171.     if (canDoThis) return true;
  1172.     canDoThis = canDoThisDamage(trooper, damage - trooper.getKneelingDamage(), &hg, &hf, actionPoints - trooper.getShootCost(), greater);
  1173.     if (canDoThis) return true;
  1174.     canDoThis = canDoThisDamage(trooper, damage - trooper.getProneDamage(), &hg, &hf, actionPoints - trooper.getShootCost(), greater);
  1175.     if (canDoThis) return true;
  1176.  
  1177.     if (*hasGrenade == true) {
  1178.         *hasGrenade = false;
  1179.  
  1180.         canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1181.         if (canDoThis) return true;
  1182.         canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage() - ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1183.         if (canDoThis) return true;
  1184.         canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage() - 2*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1185.         if (canDoThis) return true;
  1186.         canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage() - 3*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1187.         if (canDoThis) return true;
  1188.         canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage() - 4*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1189.         if (canDoThis) return true;
  1190.         canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1191.         if (canDoThis) return true;
  1192.         canDoThis = canDoThisDamage(trooper, damage - 2*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1193.         if (canDoThis) return true;
  1194.         canDoThis = canDoThisDamage(trooper, damage - 3*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1195.         if (canDoThis) return true;
  1196.         canDoThis = canDoThisDamage(trooper, damage - 4*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
  1197.         if (canDoThis) return true;
  1198.     }
  1199.  
  1200.     return false;
  1201. }
  1202.  
  1203. void updatePlayersScore() {
  1204.     const vector<Player>& players = gworld->getPlayers();
  1205.  
  1206.     for (int p = 0; p < (int)players.size(); p++) {
  1207.         const Player& player = players[p];
  1208.         PlayerInfo& pInfo = playerInfo[(int)player.getId()];
  1209.  
  1210.         if (player.getId() != me->getId() && currentSubMove.subsubMove != 0) continue;
  1211.  
  1212.         pInfo.lastScoreDiff = player.getScore() - pInfo.lastScore;
  1213.  
  1214.         if (player.getId() == me->getId()) {
  1215.             // I hited somebody
  1216.             int expectedScore = 0;
  1217.             int expectedKilled = 0;
  1218.             long long playerId = me->getId();
  1219.             for (int i = 0; i < (int)expectedHits.size(); i++) {
  1220.                 const Hit& hit = expectedHits[i].first;
  1221.  
  1222.                 if (hit.prob < 1) {
  1223.                     // shooted to phantom
  1224.                     if (pInfo.lastScoreDiff > 0) {
  1225.                         succeededHits.push_back(expectedHits[i]);
  1226. #if 0
  1227.                         // !!! can do false positive
  1228.                         // update last seen
  1229.                         if (hit.damage == pInfo.lastScoreDiff) {
  1230.                             bool found;
  1231.                             LastSeen& ls = getLastSeen((int)hit.trooper.getPlayerId(), hit.trooper.getType(), &found);
  1232.                             ls.second = expectedHits[i].second;
  1233.                             ls.first = hit.trooper;
  1234.                         }
  1235. #endif
  1236.                     } else {
  1237.                         failedHits.push_back(expectedHits[i]);
  1238.                     }
  1239.                 }
  1240.  
  1241.                 expectedScore += hit.damage;
  1242.                 if (hit.damage == hit.trooper.getHitpoints()) {
  1243.                     playerId = hit.trooper.getPlayerId();
  1244.                     expectedKilled++;
  1245.                 }
  1246.             }
  1247.  
  1248.             expectedScore += expectedKilled * ggame->getTrooperEliminationScore();
  1249.             if (expectedKilled == numLeftTroopers(playerId)) {
  1250.                 expectedScore += ggame->getPlayerEliminationScore() - ggame->getTrooperEliminationScore();
  1251.             }
  1252.  
  1253.             if (expectedScore == pInfo.lastScoreDiff) {
  1254.                 if (expectedScore > 0) {
  1255.                     std::cout << "score changed as expected: " << expectedScore << std::endl;
  1256.                     // ok, as we expected
  1257.                     for (int i = 0; i < (int)expectedHits.size(); i++) {
  1258.                         const Hit& hit = expectedHits[i].first;
  1259.  
  1260.                         if (hit.damage == hit.trooper.getHitpoints()) {
  1261.                             // we expect that he will die
  1262.                             int playerId = (int)hit.trooper.getPlayerId();
  1263.                             playerInfo[playerId].setDead(hit.trooper.getType());
  1264.                         } else {
  1265.                             bool found;
  1266.                             int playerId = (int)hit.trooper.getPlayerId();
  1267.                             LastSeen& ls = getLastSeen(playerId, hit.trooper.getType(), &found);
  1268.  
  1269.                             if (found && ls.second != currentSubMove) {
  1270.                                 // update hitpoints
  1271.                                 TrooperStateDiff diff;
  1272.                                 diff.hitPoints = -hit.damage;
  1273.  
  1274.                                 ls.first = newVirtualTrooper(ls.first, diff);
  1275.                             }
  1276.                         }
  1277.                     }
  1278.                 }
  1279.             } else if (expectedScore < pInfo.lastScoreDiff) {
  1280.                 std::cout << "More score than expected. " << pInfo.lastScoreDiff << " instead of " << expectedScore << std::endl;
  1281.                 // probably we hit someone else with grenade or another trooper moved to this position and died
  1282.             } else {
  1283.                 std::cout << "Less score than expected. " << pInfo.lastScoreDiff << " instead of " << expectedScore << std::endl;
  1284.             }
  1285.         } else if (pInfo.lastScore != player.getScore()) {
  1286.             // player score changed, analyse it
  1287.             if (prevSubMove == currentSubMove - 1 &&
  1288.                 pInfo.getAfterMe() == PROBABLY) {
  1289.  
  1290.                 // trooper of the same type can do
  1291.                 bool thisTroopCanDo = false;
  1292.                 // trooper of the previous type can do
  1293.                 bool thatTroopCanDo = false;
  1294.  
  1295.                 if (!pInfo.isDead((TrooperType)troopOrder[curTroopIndex])) {
  1296.                     bool found;
  1297.                     const Trooper& thisTrooper = getLastSeen((int)player.getId(), (TrooperType)troopOrder[curTroopIndex], &found).first;
  1298.                     if (found) {
  1299.                         // assume worst case
  1300.                         bool hasGrenage = true;
  1301.                         bool hasFieldRation = true;
  1302.  
  1303.                         thisTroopCanDo = canDoThisDamage(thisTrooper, player.getScore() - pInfo.lastScore, &hasGrenage, &hasFieldRation);
  1304.                     }
  1305.                 }
  1306.  
  1307.                 int troopIndex = curTroopIndex - 1;
  1308.                 if (troopIndex < 0) troopIndex += maxTroops;
  1309.  
  1310.                 if (!pInfo.isDead((TrooperType)troopOrder[troopIndex])) {
  1311.                     bool found;
  1312.                     const Trooper& thatTrooper = getLastSeen((int)player.getId(), (TrooperType)troopOrder[troopIndex], &found).first;
  1313.                     if (found) {
  1314.                         // assume worst case
  1315.                         bool hasGrenage = true;
  1316.                         bool hasFieldRation = true;
  1317.  
  1318.                         thatTroopCanDo = canDoThisDamage(thatTrooper, player.getScore() - pInfo.lastScore, &hasGrenage, &hasFieldRation);
  1319.                     }
  1320.                 }
  1321.                
  1322.                 if (thisTroopCanDo && !thatTroopCanDo) {
  1323.                     pInfo.setAfterMe(MOST_LIKELY_FALSE);
  1324.                 } else if (thatTroopCanDo && !thisTroopCanDo) {
  1325.                     pInfo.setAfterMe(MOST_LIKELY_TRUE);
  1326.                 }
  1327.             }
  1328.         }
  1329.  
  1330.         pInfo.lastScore = player.getScore();
  1331.     }
  1332. }
  1333.  
  1334. // analyse last shoot to me and compute where this trooper can hide
  1335. void checkWhoCanShootSo(LastShooted& lshooted) {
  1336.     const Trooper& teammate = lshooted.teammate;
  1337.     int damage = lshooted.damage;
  1338.  
  1339.     if (damage == 0) return;
  1340.  
  1341.     const vector<Player>& players = gworld->getPlayers();
  1342.    
  1343.     vector<Trooper> possibleTroopers;
  1344.  
  1345.     for (int p = 0; p < (int)players.size(); p++) {
  1346.         const Player& player = players[p];
  1347.  
  1348.         if (player.getId() == me->getId()) continue;
  1349.  
  1350.         PlayerInfo& pInfo = playerInfo[(int)player.getId()];
  1351.  
  1352.         if (pInfo.lastScoreDiff < damage) continue;
  1353.        
  1354.         // start with current trooper type
  1355.         int possibleStart = 0;
  1356.         // end with trooper type that turned previous time
  1357.         int possibleEnd = currentSubMove - prevSubMove;
  1358.  
  1359.         if (pInfo.getAfterMe() >= MOST_LIKELY_TRUE) possibleStart++;
  1360.         if (pInfo.getAfterMe() <= MOST_LIKELY_FALSE) possibleEnd--;
  1361.  
  1362.         for (int i = possibleStart; i <= possibleEnd; i++) {
  1363.             int trooperIndex = curTroopIndex - i;
  1364.             if (trooperIndex < 0) trooperIndex += maxTroops;
  1365.             TrooperType ttype = (TrooperType)troopOrder[trooperIndex];
  1366.        
  1367.             if (pInfo.isDead(ttype)) continue;
  1368.  
  1369.             bool found;
  1370.             const LastSeen& lseen = getLastSeen((int)player.getId(), ttype, &found);
  1371.             if (!found) continue;
  1372.  
  1373.             const Trooper& enemy = lseen.first;
  1374.  
  1375.             if (enemy.isTeammate()) continue;
  1376.  
  1377.             {
  1378.                 // hard check
  1379.                 bool hasGrenade = enemy.isHoldingGrenade();
  1380.                 bool hasFieldRation = enemy.isHoldingFieldRation();
  1381.                 bool canDo = false;
  1382.  
  1383.                 if (numTurnsSinceLastSeen(lseen) >= 2) {
  1384.                     // could take a bonus
  1385.                     hasGrenade = true;
  1386.                     hasFieldRation = true;
  1387.                 }
  1388.  
  1389.                 if (canDoThisDamage(enemy, damage, &hasGrenade, &hasFieldRation, -1, lshooted.fatal)) {
  1390.                     int minScoreDiff = damage;
  1391.                     if (lshooted.fatal) minScoreDiff += ggame->getTrooperEliminationScore();
  1392.                     if (pInfo.lastScoreDiff >= minScoreDiff) {
  1393.                         canDo = true;
  1394.                     }
  1395.                 }
  1396.  
  1397.                 if (!canDo) continue;
  1398.             }
  1399.  
  1400.             if (lseen.second == currentSubMove) {
  1401.                 // this is him, skip others
  1402.                 possibleTroopers.clear();
  1403.                 possibleTroopers.push_back(enemy);
  1404.                 break;
  1405.             }
  1406.  
  1407.             double numTurns = numTurnsSinceLastSeen(lseen);
  1408.             if (lseen.second == currentSubMove) numTurns = 1;
  1409.  
  1410.             int numFullTurnsCeil = (int)ceil(numTurns);
  1411.  
  1412.             if (numFullTurnsCeil == 0) {
  1413.                 continue;
  1414.             }
  1415.  
  1416.             int maxActionPointsPerTurn = enemy.getInitialActionPoints();
  1417.             if (enemy.getType() != COMMANDER && enemy.getType() != SCOUT) maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();
  1418.  
  1419.             int wholeActionPointsCeil = maxActionPointsPerTurn * numFullTurnsCeil;
  1420.  
  1421.             const vector<vector<CellType> >& cells = gworld->getCells();
  1422.  
  1423.             for (int x = 0; x < gworld->getWidth(); x++) {
  1424.                 for (int y = 0; y < gworld->getHeight(); y++) {
  1425.                     if (cells[x][y] != FREE) continue;
  1426.                     const StepMap& stepMap = allStepMaps[x][y];
  1427.  
  1428.                     for (int stance = STANDING; stance >= PRONE; stance--) {
  1429.                         // possible fire positions
  1430.                         int moveCost = findFastestMove(stepMap, (TrooperStance)stance, enemy);
  1431.                         if (moveCost >= wholeActionPointsCeil) continue;
  1432.  
  1433.                         if (!gworld->isVisible(enemy.getShootingRange(), x, y, (TrooperStance)stance,
  1434.                             teammate.getX(), teammate.getY(), teammate.getStance())) {
  1435.                             continue;
  1436.                         }
  1437.                            
  1438.                         // possible shoot position, check it
  1439.                         TrooperStateDiff diff;
  1440.                         diff.x = x - enemy.getX();
  1441.                         diff.y = y - enemy.getY();
  1442.                         diff.stance = stance - enemy.getStance();
  1443.                         if (numTurnsSinceLastSeen(lseen) >= 2) {
  1444.                             // could take a bonus
  1445.                             diff.plusGrenade = true;
  1446.                             diff.plusMedikit = true;
  1447.                         }
  1448.                         Trooper shootCandidate = newVirtualTrooper(enemy, diff);
  1449.  
  1450.                         // look there it can hide
  1451.                         for (int xh = 0; xh < gworld->getWidth(); xh++) {
  1452.                             for (int yh = 0; yh < gworld->getHeight(); yh++) {
  1453.                                 if (cells[xh][yh] != FREE) continue;
  1454.                                 for (int sh = STANDING; sh >= PRONE; sh--) {
  1455.                                     if (!inFog(xh, yh, (TrooperStance)sh, enemy.getType() == SNIPER ? currentFogSniper : currentFog)) continue;
  1456.  
  1457.                                     // can hide there
  1458.                                     int hideMoveCost = findFastestMove(stepMap, (TrooperStance)stance, Position(xh, yh, (TrooperStance)sh));
  1459.  
  1460.                                     int pointsForAction = wholeActionPointsCeil - moveCost - hideMoveCost;
  1461.  
  1462.                                     if (hideMoveCost >= maxActionPointsPerTurn || pointsForAction <= 0) continue;
  1463.                                     bool hasGrenade = shootCandidate.isHoldingGrenade();
  1464.                                     bool hasFieldRation = shootCandidate.isHoldingFieldRation();
  1465.  
  1466.                                     if (canDoThisDamage(shootCandidate, damage, &hasGrenade, &hasFieldRation, pointsForAction, lshooted.fatal)) {
  1467.                                         if (hasGrenade != shootCandidate.isHoldingGrenade()) {
  1468.                                             // he used grenage
  1469.                                             if (squareDist(x,y,teammate.getX(), teammate.getY()) > 25) continue;
  1470.                                         }
  1471.  
  1472.                                         if (lseen.second < prevSubMove) {
  1473.                                             bool canDo = false;
  1474.                                             int prevTrooperIndex = prevSubMove % maxTroops;
  1475.                                             // loop other possible starting positions
  1476.                                             for (int xs = 0; xs < gworld->getWidth(); xs++) {
  1477.                                                 for (int ys = 0; ys < gworld->getHeight(); ys++) {
  1478.                                                     if (cells[xs][ys] != FREE) continue;
  1479.                                                     for (int ss = STANDING; ss >= PRONE; ss--) {
  1480.                                                         int positioningMoveCost = findFastestMove(stepMap, (TrooperStance)stance, Position(xs, ys, (TrooperStance)ss));
  1481.  
  1482.                                                         if (positioningMoveCost + hideMoveCost >= maxActionPointsPerTurn) continue;
  1483.  
  1484.                                                         bool hasGrenade = shootCandidate.isHoldingGrenade();
  1485.                                                         bool hasFieldRation = shootCandidate.isHoldingFieldRation();
  1486.  
  1487.                                                         int pointsForAction = maxActionPointsPerTurn - positioningMoveCost - hideMoveCost;
  1488.  
  1489.                                                         if (canDoThisDamage(shootCandidate, damage, &hasGrenade, &hasFieldRation, pointsForAction, lshooted.fatal)) {
  1490.                                                             if (hasGrenade != shootCandidate.isHoldingGrenade()) {
  1491.                                                                 // he used grenage
  1492.                                                                 if (squareDist(x,y,teammate.getX(), teammate.getY()) > 25) continue;
  1493.                                                             }
  1494.                                                         } else {
  1495.                                                             continue;
  1496.                                                         }
  1497.  
  1498.                                                         // it must be in fog last turn, otherwise I saw him
  1499.                                                         if (!inFog(xs, ys, (TrooperStance)ss, enemy.getType() == SNIPER ? lastFogsSniper[prevTrooperIndex].front() : lastFogs[prevTrooperIndex].front())) continue;
  1500.  
  1501.                                                         //std::cout << "start from " << Position(xs,ys,(TrooperStance)ss) << " attack at " << Position(x,y,(TrooperStance)(stance)) << " hide at " << Position(xh,yh,(TrooperStance)sh) <<  std::endl;
  1502.                                                         canDo = true;
  1503.                                                         break;
  1504.                                                     }
  1505.                                                     if (canDo) break;
  1506.                                                 }
  1507.                                                 if (canDo) break;
  1508.                                             }
  1509.                                             if (!canDo) continue;
  1510.                                         } else {
  1511.                                             //std::cout << "start from " << Position(ls.first) << " attack at " << Position(x,y,(TrooperStance)(stance)) << " hide at " << Position(xh,yh,(TrooperStance)sh) <<  std::endl;
  1512.                                         }
  1513.                                                        
  1514.                                         // look if already stored this position
  1515.                                         bool found = false;
  1516.                                         for (int pp = 0; pp < (int)possibleTroopers.size(); pp++) {
  1517.                                             if (possibleTroopers[pp].getPlayerId() == enemy.getPlayerId() &&
  1518.                                                 possibleTroopers[pp].getType() == enemy.getType() &&
  1519.                                                 Point(possibleTroopers[pp]) == Point(xh,yh)) {
  1520.                                                 if (sh > possibleTroopers[pp].getStance()) {
  1521.                                                     // store maximum possible stance
  1522.                                                     TrooperStateDiff diff;
  1523.                                                     diff.x = xh - enemy.getX();
  1524.                                                     diff.y = yh - enemy.getY();
  1525.                                                     diff.stance = sh - enemy.getStance();
  1526.                                                     Trooper hideTrooper = newVirtualTrooper(enemy, diff);
  1527.                                                     possibleTroopers[pp] = hideTrooper;
  1528.                                                 }
  1529.                                                 found = true;
  1530.                                             }
  1531.                                         }
  1532.  
  1533.                                         if (found) continue;
  1534.  
  1535.                                         TrooperStateDiff diff;
  1536.                                         diff.x = xh - enemy.getX();
  1537.                                         diff.y = yh - enemy.getY();
  1538.                                         diff.stance = sh - enemy.getStance();
  1539.                                         Trooper hideTrooper = newVirtualTrooper(enemy, diff);
  1540.                                         possibleTroopers.push_back(hideTrooper);
  1541.                                     }
  1542.                                 }
  1543.                             }
  1544.                         }
  1545.                     }
  1546.                 }
  1547.             }
  1548.         }
  1549.     }
  1550.  
  1551.     lshooted.possibleEnemies = possibleTroopers;
  1552.  
  1553.     // compute approximate player position that this shoot gives
  1554.     lshooted.approxPositions.resize(playerInfo.size());
  1555.  
  1556.     for (long long pid = 1; pid < (int)playerInfo.size(); pid++) {
  1557.         // find approximate position
  1558.         int xx = 0;
  1559.         int yy = 0;
  1560.         int tt = 0;
  1561.         for (int e = 0; e < (int)lshooted.possibleEnemies.size(); e++) {
  1562.             const Trooper& trooper = lshooted.possibleEnemies[e];
  1563.             if (isDead(trooper)) continue;
  1564.             if (trooper.getPlayerId() != pid) continue;
  1565.             xx += trooper.getX();
  1566.             yy += trooper.getY();
  1567.             tt++;
  1568.         }
  1569.  
  1570.         if (tt > 0) {
  1571.             lshooted.approxPositions[(int)pid] = Point(xx/tt, yy/tt);
  1572.         }
  1573.     }
  1574. }
  1575.  
  1576. void updateLastShooted(LastShooted& ls) {
  1577.     if (ls.subMove == currentSubMove && currentSubMove.subsubMove == 0) {
  1578.         // just happened, initialize
  1579.         checkWhoCanShootSo(ls);
  1580.     }
  1581.  
  1582.     // throw out troopers that are not possible now
  1583.     for (int e = 0; e < (int)ls.possibleEnemies.size(); e++) {
  1584.         const Trooper& enemy = ls.possibleEnemies[e];
  1585.  
  1586.         bool found;
  1587.         const LastSeen& lSeen = getLastSeen((int)enemy.getPlayerId(), enemy.getType(), &found);
  1588.         if (found && lSeen.second == currentSubMove &&
  1589.             enemy.getX() == lSeen.first.getX() &&
  1590.             enemy.getY() == lSeen.first.getY()) {
  1591.             // this is definetely him, erase others
  1592.             ls.possibleEnemies.clear();
  1593.             ls.possibleEnemies.push_back(lSeen.first);
  1594.             break;
  1595.         }
  1596.  
  1597.         if (isDead(enemy) || numTurnsSinceSubMove(enemy, ls.subMove) > 0 ||
  1598.             !inFog(enemy, enemy.getType() == SNIPER ? currentFogSniper : currentFog)) {
  1599.             ls.possibleEnemies.erase(ls.possibleEnemies.begin() + e);
  1600.             e--;
  1601.         }
  1602.     }
  1603.  
  1604.     if (ls.possibleEnemies.size() == 0) return;
  1605.  
  1606.     std::cout << ls.teammate << " heated by " << ls.damage << " " << (currentSubMove - ls.subMove) << " submoves ago. It can be " << std::endl;
  1607.     for (int pe = 0; pe < (int)ls.possibleEnemies.size(); pe++) {
  1608.         std::cout << ls.possibleEnemies[pe] << " hidden in " << Position(ls.possibleEnemies[pe]) << std::endl;
  1609.     }
  1610. }
  1611.  
  1612. void updateLastShooted() {
  1613.     for (int i = 0; i < (int)lastShooted.size(); i++) {
  1614.         updateLastShooted(lastShooted[i]);
  1615.     }
  1616. }
  1617.  
  1618. // updates last seen vector using current world come from runner
  1619. void updateLastSeen() {
  1620.     const vector<Trooper>& troopers = gworld->getTroopers();
  1621.     bool enemy = false;
  1622.     bool attention = false;
  1623.     bool leaderFound = false;
  1624.     for (size_t t = 0; t < troopers.size(); ++t) {
  1625.         Trooper trooper = troopers.at(t);
  1626.  
  1627.         if (trooper.isTeammate()) {
  1628.             if (leader == trooper.getType()) leaderFound = true;
  1629.             if (currentSubMove == 0 && currentSubMove.subsubMove == 0) {
  1630.                 int xOffset = min(trooper.getX(), gworld->getWidth() - trooper.getX() - 1);
  1631.                 int yOffset = min(trooper.getY(), gworld->getHeight() - trooper.getY() - 1);
  1632.                
  1633.                 // very first move. We know positions of all enemy troopers since it is symmetric
  1634.                 int numPlayers = (int)gworld->getPlayers().size();
  1635.                 for (long long id = 1; id <= numPlayers; id++) {
  1636.                     if (id == 1) {
  1637.                         TrooperStateDiff diff(
  1638.                             -trooper.getX() + xOffset,
  1639.                             -trooper.getY() + yOffset,
  1640.                             0, 0, false, (int)(id - trooper.getPlayerId()));
  1641.                         Trooper enemy = newVirtualTrooper(trooper, diff);
  1642.                         addLastSeen(enemy, SubMove(-1,0));
  1643.                     } else if (id == 2) {
  1644.                         TrooperStateDiff diff(
  1645.                             -trooper.getX() + (gworld->getWidth() - 1 - xOffset),
  1646.                             -trooper.getY() + (gworld->getHeight() - 1 - yOffset),
  1647.                             0, 0, false, (int)(id - trooper.getPlayerId()));
  1648.                         Trooper enemy = newVirtualTrooper(trooper, diff);
  1649.                         addLastSeen(enemy, SubMove(-1,0));
  1650.                     } else if (id == 3) {
  1651.                         TrooperStateDiff diff(
  1652.                             -trooper.getX() + (gworld->getWidth() - 1 - xOffset),
  1653.                             -trooper.getY() + yOffset,
  1654.                             0, 0, false, (int)(id - trooper.getPlayerId()));
  1655.                         Trooper enemy = newVirtualTrooper(trooper, diff);
  1656.                         addLastSeen(enemy, SubMove(-1,0));
  1657.                     } else if (id == 4) {
  1658.                         TrooperStateDiff diff(
  1659.                             -trooper.getX() + xOffset,
  1660.                             -trooper.getY() + (gworld->getHeight() - 1 - yOffset),
  1661.                             0, 0, false, (int)(id - trooper.getPlayerId()));
  1662.                         Trooper enemy = newVirtualTrooper(trooper, diff);
  1663.                         addLastSeen(enemy, SubMove(-1,0));
  1664.                     }
  1665.                 }
  1666.             }
  1667.         } else {
  1668.             int closest = 1000;
  1669.             // find closest teammate to the enemy and make him leader
  1670.             for (size_t tt = 0; tt < troopers.size(); ++tt) {
  1671.                 Trooper teammate = troopers.at(tt);
  1672.                 if (teammate.isTeammate()) {
  1673.                     if (squareDist(teammate, trooper) < closest) {
  1674.                         leader = teammate.getType();
  1675.                         leaderFound = true;
  1676.                         closest = squareDist(teammate, trooper);
  1677.                     }
  1678.                 }
  1679.             }
  1680.             enemy = true;
  1681.         }
  1682.        
  1683.         // then, see that is changed since previous seen for this trooper
  1684.         int i;
  1685.         for (i = 0; i < (int)lastSeen.size(); i++) {
  1686.             if (lastSeen[i].first.getPlayerId() == trooper.getPlayerId() &&
  1687.                 lastSeen[i].first.getType() == trooper.getType()
  1688.                 ) {
  1689.  
  1690.                 if (isDead(lastSeen[i].first)) {
  1691.                     // marked him as dead but he is alive!!
  1692.                     SHOULD_NOT_HAPPEN;
  1693.                     // revert him to last seen vector
  1694.                     addLastSeen(trooper, currentSubMove, i);
  1695.                     playerInfo[(int)trooper.getPlayerId()].setAlive(trooper.getType());
  1696.                     continue;
  1697.                 }
  1698.  
  1699.                 // calculate average speed
  1700.                 double moves = numTurnsSinceLastSeen(lastSeen[i]);
  1701.                 if (moves > 0 && !trooper.isTeammate()) {                    
  1702.                     int dist = stepDistance(lastSeen[i].first, trooper);
  1703.                     int movesCeil = (int)ceil(moves);
  1704.                     int movesFloor = (int)floor(moves);
  1705.                     double averSpeedFloor = (double)dist / movesCeil;
  1706.                     double averSpeedCeil = (double)dist / movesFloor;
  1707.                     int maxActionPoints = trooper.getInitialActionPoints();
  1708.                     if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT)
  1709.                         maxActionPoints += ggame->getCommanderAuraBonusActionPoints();
  1710.                     int maxSpeed = maxActionPoints / ggame->getStandingMoveCost();
  1711.  
  1712.                     if (averSpeedCeil > maxSpeed) {
  1713.                         // means that movesFloor can't happen
  1714.                         if (trooper.getType() == gself->getType()) {
  1715.                             playerInfo[(int)trooper.getPlayerId()].setAfterMe(MOST_LIKELY_FALSE);
  1716.                         } else {
  1717.                             playerInfo[(int)trooper.getPlayerId()].setAfterMe(MOST_LIKELY_TRUE);
  1718.                         }
  1719.                         averSpeedCeil = averSpeedFloor;
  1720.                     }
  1721.  
  1722.                     averSpeedCeil = (averSpeedCeil + averSpeedFloor) / 2;
  1723.  
  1724.                     playerInfo[(int)trooper.getPlayerId()].averageSpeed =
  1725.                         (averSpeedCeil + playerInfo[(int)trooper.getPlayerId()].averageSpeed) / 2;
  1726.                 }
  1727.  
  1728.                 int j = troopOrderRev[trooper.getType()];
  1729.                 int diff = curTroopIndex - j;
  1730.                 if (diff < 0) diff += maxTroops;
  1731.  
  1732.                 // already seen before, check whether it changed since last time
  1733.                
  1734.                 if (!trooper.isTeammate()) {
  1735.                     if (lastSeen[i].second != currentSubMove) {
  1736.                         if (Position(trooper) != Position(lastSeen[i].first) ||
  1737.                             trooper.isHoldingFieldRation() != lastSeen[i].first.isHoldingFieldRation() ||
  1738.                             trooper.isHoldingGrenade() != lastSeen[i].first.isHoldingGrenade() ||
  1739.                             trooper.isHoldingMedikit() != lastSeen[i].first.isHoldingMedikit() ||
  1740.                             trooper.getActionPoints() != lastSeen[i].first.getActionPoints()
  1741.                             ) {
  1742.                             if (lastSeen[i].second == currentSubMove-1) {
  1743.                                 // this happened second ago!
  1744.                                 if (diff == 0) {
  1745.                                     // if it is the trooper of the same type he turns before me
  1746.                                     playerInfo[(int)trooper.getPlayerId()].setAfterMe(FALSE);
  1747.                                 } else {
  1748.                                     // otherwise - after
  1749.                                     playerInfo[(int)trooper.getPlayerId()].setAfterMe(TRUE);
  1750.                                 }
  1751.                             }
  1752.                         }
  1753.  
  1754.                         int lastSeenSubMove = lastSeen[i].second;
  1755.                         int seenDiff = currentSubMove - lastSeenSubMove;
  1756.  
  1757.                         // find who saw this position last time
  1758.                         for (int j = 1; j < maxTroops; j++) {
  1759.                             if (j >= seenDiff) break;;
  1760.                             int tIndex = curTroopIndex - j;
  1761.                             if (tIndex < 0) tIndex += maxTroops;
  1762.                             if (!inFog(trooper, trooper.getType() == SNIPER ? lastFogsSniper[tIndex].front() : lastFogs[tIndex].front())) {
  1763.                                 // he saw this position j submoves before but the trooper was seen seenDiff turns before
  1764.                                 if (trooper.getType() == gself->getType()) {
  1765.                                     playerInfo[(int)trooper.getPlayerId()].setAfterMe(FALSE);
  1766.                                 } else if (trooper.getType() == troopOrder[tIndex]) {
  1767.                                     playerInfo[(int)trooper.getPlayerId()].setAfterMe(TRUE);
  1768.                                 }
  1769.                                 break;
  1770.                             }
  1771.                         }
  1772.                     }
  1773.                 } else {
  1774.                     // shooted?
  1775.                     int diff = lastSeen[i].first.getHitpoints() - trooper.getHitpoints();
  1776.                     if (diff > 0) {
  1777.                         enemy = true;
  1778.                         leader = trooper.getType();
  1779.                         // try to analyze who can do this
  1780.                         LastShooted ls;
  1781.                         ls.teammate = trooper;
  1782.                         ls.damage = diff;
  1783.                         ls.subMove = currentSubMove;
  1784.                         lastShooted.push_back(ls);
  1785.                     }
  1786.                 }
  1787.  
  1788.                 // update last seen
  1789.                 addLastSeen(trooper, currentSubMove, i);
  1790.                 break;
  1791.             }
  1792.         }
  1793.  
  1794.         if (i == (int)lastSeen.size()) {
  1795.             // not found?? why
  1796.             SHOULD_NOT_HAPPEN;
  1797.         }
  1798.     }
  1799.  
  1800.     // how many moves be in attention
  1801.     int attentionTime = numLeftPlayers() > 2 ? 2 : 4;
  1802.  
  1803.     // go through other lastseens and check the ones that was not updated
  1804.     for (int i = 0; i < (int)lastSeen.size(); i++) {
  1805.         const Trooper& trooper = lastSeen[i].first;
  1806.  
  1807.         if (isDead(trooper)) continue;
  1808.  
  1809.         if (lastSeen[i].second != -1 && stillThere(lastSeen[i]) && !trooper.isTeammate()) {
  1810.             enemy = true;
  1811.         }
  1812.  
  1813.         if (lastSeen[i].second != currentSubMove ||
  1814.             lastSeen[i].second.subsubMove != currentSubMove.subsubMove) {
  1815.             // means that this trooper is not on the map now
  1816.             if (trooper.isTeammate()) {
  1817.                 if (isDead(trooper)) {
  1818.                     // already marked as dead
  1819.                 } else {
  1820.                     // it was killed! Do something
  1821.                     playerInfo[(int)trooper.getPlayerId()].setDead(trooper.getType());
  1822.  
  1823.                     LastShooted ls;
  1824.                     ls.subMove = currentSubMove;
  1825.                     ls.teammate = trooper;
  1826.                     ls.damage = lastSeen[i].first.getHitpoints();
  1827.                     ls.fatal = true;
  1828.                     lastShooted.push_back(ls);
  1829.                 }
  1830.             } else {
  1831.                 if (lastSeen[i].second >= 0 &&
  1832.                     currentSubMove-lastSeen[i].second < maxTroops * attentionTime) attention = true;
  1833.                 // is in fog or moved away.
  1834.                 if (weSeeIt(trooper)) {
  1835.                     // we see this position now.
  1836.                     if (stillThere(lastSeen[i]) == TRUE) {
  1837.                         // it was killed
  1838.                         playerInfo[(int)trooper.getPlayerId()].setDead(trooper.getType());
  1839.                         // remove from lastSeen
  1840.                         continue;
  1841.                     }
  1842.  
  1843.                     int lastSeenSubMove = lastSeen[i].second;
  1844.                     int seenDiff = currentSubMove - lastSeenSubMove;
  1845.  
  1846.                     if (seenDiff < maxTroops) {
  1847.                         // seen quiet small time ago
  1848.                         int trooperSeenOrder = curTroopIndex - seenDiff;
  1849.                         if (trooperSeenOrder < 0) trooperSeenOrder += maxTroops;
  1850.  
  1851.                         // moved away or killed
  1852.                         if (numLeftPlayers() <= 2) {
  1853.                             // definetely moved away (or player killed its own trooper?? quiet unlikely)
  1854.                             if (trooper.getType() == gself->getType()) {
  1855.                                 playerInfo[(int)trooper.getPlayerId()].setAfterMe(FALSE);
  1856.                             } else if (trooper.getType() == troopOrder[trooperSeenOrder]) {
  1857.                                 playerInfo[(int)trooper.getPlayerId()].setAfterMe(TRUE);
  1858.                             }
  1859.                         } else if (prevSubMove % maxTroops != currentSubMove % maxTroops) {
  1860.                             if (trooper.getHitpoints() >= 100) {
  1861.                                 // most likely moved away
  1862.                                 if (trooper.getType() == gself->getType()) {
  1863.                                     playerInfo[(int)trooper.getPlayerId()].setAfterMe(MOST_LIKELY_FALSE);
  1864.                                 } else if (trooper.getType() == troopOrder[trooperSeenOrder]) {
  1865.                                     playerInfo[(int)trooper.getPlayerId()].setAfterMe(MOST_LIKELY_TRUE);
  1866.                                 }
  1867.                             }
  1868.                         }
  1869.                     }
  1870.                 }
  1871.             }
  1872.         }
  1873.     }
  1874.  
  1875.     // determine mode
  1876.     Mode nextMode = TRAVEL;
  1877.     if (enemy || currentMode == COMBAT && currentSubMove - lastModeChange < maxTroops) {
  1878.         nextMode = COMBAT;
  1879.     } else if (attention || currentMode == COMBAT || currentMode == AFTER_COMBAT && currentSubMove -lastModeChange < attentionTime * maxTroops) {
  1880.         nextMode = AFTER_COMBAT;
  1881.     } else {
  1882.         nextMode = TRAVEL;
  1883.     }
  1884.  
  1885.     if (nextMode != currentMode) {
  1886.         std::cout << "switching to mode " << nextMode << std::endl;
  1887.         currentMode = nextMode;
  1888.         lastModeChange = currentSubMove;
  1889.     }
  1890.  
  1891.     if (!leaderFound) {
  1892.         std::cout << "Leader was killed" << std::endl;
  1893.         leader = -1;
  1894.     }
  1895. }
  1896.  
  1897. void findApproximatePositionOfPlayers() {
  1898.     {
  1899.         // first, check if commander knows something
  1900.         const vector<Player>& players = gworld->getPlayers();
  1901.         bool dataValid = false;
  1902.         for (int i = 0; i < (int)players.size(); i++) {
  1903.             int x = players[i].getApproximateX();
  1904.             int y = players[i].getApproximateY();
  1905.             playerInfo[(int)players[i].getId()].approximatePosition = Point(x,y);
  1906.             if (validPoint(Point(x,y))) {
  1907.                 dataValid = true;
  1908.             }
  1909.         }
  1910.  
  1911.         if (dataValid) {
  1912.             // if some approximate positions valid and others are not, means that others are dead
  1913.             for (int i = 0; i < (int)players.size(); i++) {
  1914.                 int x = players[i].getApproximateX();
  1915.                 int y = players[i].getApproximateY();
  1916.                 if (!validPoint(Point(x,y))) {
  1917.                     // all dead
  1918.                     for (int t = 0; t < maxTroops; t++) {
  1919.                         playerInfo[(int)players[i].getId()].setDead((TrooperType)t);
  1920.                     }
  1921.                 }
  1922.             }
  1923.         }
  1924.     }
  1925.  
  1926.     // now try to determine position based on last shoots
  1927.     for (int p = 1; p < (int)playerInfo.size(); ++p) {
  1928.         PlayerInfo& pInfo = playerInfo[p];
  1929.         int x = 0;
  1930.         int y = 0;
  1931.         int numT = 0;
  1932.         for (int i = 0; i < (int)lastShooted.size(); i++) {
  1933.             if (currentSubMove - lastShooted[i].subMove >= 2*maxTroops) continue;
  1934.             if (validPoint(lastShooted[i].approxPositions[p])) {
  1935.                 x += lastShooted[i].approxPositions[p].x;
  1936.                 y += lastShooted[i].approxPositions[p].y;
  1937.                 numT++;            
  1938.             }
  1939.         }
  1940.  
  1941.         if (numT > 0) {
  1942.             pInfo.approximatePosition = Point(x/numT, y/numT);
  1943.             if (!validPoint(pInfo.approximatePosition)) {
  1944.                 SHOULD_NOT_HAPPEN;
  1945.             }
  1946.         }
  1947.     }
  1948.  
  1949.     // now try to determine position based on last seen troopers
  1950.     // most accurate method, overrides others
  1951.     for (int p = 1; p < (int)playerInfo.size(); ++p) {
  1952.         PlayerInfo& pInfo = playerInfo[p];
  1953.         int x = 0;
  1954.         int y = 0;
  1955.         int numT = 0;
  1956.         for (int i = 0; i < (int)lastSeen.size(); i++) {
  1957.             const Trooper& trooper = lastSeen[i].first;
  1958.             if (isDead(trooper)) continue;
  1959.             if (trooper.getPlayerId() != pInfo.getId()) continue;
  1960.             if (lastSeen[i].second < 0) continue;
  1961.             if (currentSubMove - lastSeen[i].second >= 2*maxTroops) continue;
  1962.             x += trooper.getX();
  1963.             y += trooper.getY();
  1964.             numT++;
  1965.         }
  1966.  
  1967.         if (numT > 0) {
  1968.             pInfo.approximatePosition = Point(x/numT, y/numT);
  1969.             if (!validPoint(pInfo.approximatePosition)) {
  1970.                 SHOULD_NOT_HAPPEN;
  1971.             }
  1972.         }
  1973.     }
  1974.  
  1975.     // find nearest player ot me
  1976.     const vector<Player>& players = gworld->getPlayers();
  1977.     int nearestPlayer = -1;
  1978.     int minDistToPlayer = 1000;
  1979.     for (int i = 0; i < (int)players.size(); i++) {
  1980.         if (players[i].getId() != gself->getPlayerId()) {
  1981.             Point approxPos = playerInfo[(int)players[i].getId()].approximatePosition;
  1982.             if (validPoint(approxPos)) {
  1983.                 Point nf = nearestFree(approxPos);
  1984.                 randomTarget = false;
  1985.                 const StepMap& stepMap = allStepMaps[nf.getX()][nf.getY()];
  1986.                 int stepsToTarget = stepMap[gself->getX()][gself->getY()];
  1987.                 if (stepsToTarget < minDistToPlayer) {
  1988.                     minDistToPlayer = stepsToTarget;
  1989.                     nearestPlayer = i;
  1990.                 }
  1991.             }
  1992.         }
  1993.     }
  1994.  
  1995.     if (nearestPlayer != -1) {
  1996.         // attack him
  1997.         attackPlayerId = (int)players[nearestPlayer].getId();
  1998.     }
  1999. }
  2000.  
  2001. // probability that enemy is on the distance from his teammate
  2002. double distToProbNearTeammate[] = {
  2003.     20, 20, 20, 15., 5., 2., 1., 1., 0.5, 0.2
  2004. };
  2005.  
  2006. int distToProbNearTeammateSize = sizeof(distToProbNearTeammate) / sizeof(double);
  2007.  
  2008. TriBool isShootedThere(const Trooper& trooper) {
  2009.     for (int i = 0; i < (int)succeededHits.size(); i++) {
  2010.         const Hit& hit = succeededHits[i].first;
  2011.         if (hit.trooper.getX() == trooper.getX() && hit.trooper.getY() == trooper.getY()) {
  2012.             // shooted to this location and succeeded
  2013.             if (numTurnsSinceSubMove(trooper, succeededHits[i].second) == 0) {
  2014.                 return TRUE;
  2015.             }
  2016.         }
  2017.     }
  2018.  
  2019.     for (int i = 0; i < (int)failedHits.size(); i++) {
  2020.         const Hit& hit = failedHits[i].first;
  2021.         if (hit.trooper.getX() == trooper.getX() && hit.trooper.getY() == trooper.getY()) {
  2022.             // shooted to this location and failed
  2023.             if (numTurnsSinceSubMove(trooper, failedHits[i].second) == 0) {
  2024.                 return FALSE;
  2025.             }
  2026.         }
  2027.     }
  2028.  
  2029.     return PROBABLY;
  2030. }
  2031.  
  2032. void updateTrooperProbs() {
  2033.     for (int x = 0; x < (int)gworld->getWidth(); x++) {
  2034.         for (int y = 0; y < (int)gworld->getHeight(); y++) {
  2035.             trooperProbs[x][y].clear();
  2036.         }
  2037.     }
  2038.        
  2039.     for (int t = 0; t < (int)lastSeen.size(); t++) {
  2040.         const Trooper& trooper = lastSeen[t].first;
  2041.         SubMove subMove = lastSeen[t].second;
  2042.  
  2043.         if (isDead(trooper)) continue;
  2044.  
  2045.         // skip teammates
  2046.         if (trooper.isTeammate()) continue;
  2047.  
  2048.         double totalProb = 0.;
  2049.  
  2050.         double numTurns = numTurnsSinceLastSeen(lastSeen[t]);
  2051.         int numFullTurnsCeil = (int)ceil(numTurns);
  2052.         int numFullTurnsFloor = (int)floor(numTurns);
  2053.  
  2054.         if (numFullTurnsCeil == 0) {
  2055.             // didn't move since last seen, definetely know there he is
  2056.             trooperProbs[trooper.getX()][trooper.getY()].push_back(std::pair<double, Trooper>(1., trooper));
  2057.             continue;
  2058.         }
  2059.  
  2060.         int maxActionPointsPerTurn = trooper.getInitialActionPoints();
  2061.         if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT) maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();
  2062.  
  2063.         int wholeActionPointsCeil = maxActionPointsPerTurn * numFullTurnsCeil;
  2064.         int wholeActionPointsFloor = maxActionPointsPerTurn * numFullTurnsFloor;
  2065.         if (trooper.getStance() == PRONE) {
  2066.             // need to change to STANDING first
  2067.             wholeActionPointsCeil -= ggame->getStanceChangeCost() * 2;
  2068.             wholeActionPointsFloor -= ggame->getStanceChangeCost() * 2;
  2069.         }
  2070.         if (trooper.getStance() == KNEELING) {
  2071.             // need to change to STANDING first
  2072.             wholeActionPointsCeil -= ggame->getStanceChangeCost();
  2073.             wholeActionPointsFloor -= ggame->getStanceChangeCost();
  2074.         }
  2075.  
  2076.         int maxStepsCeil = wholeActionPointsCeil / ggame->getStandingMoveCost();
  2077.         int maxStepsFloor = wholeActionPointsFloor / ggame->getStandingMoveCost();
  2078.  
  2079.         const vector<vector<CellType> >& cells = gworld->getCells();
  2080.         const StepMap& stepMap = allStepMaps[trooper.getX()][trooper.getY()];
  2081.  
  2082.         // check there he can appear using his action points
  2083.         for (int x = 0; x < (int)gworld->getWidth(); x++) {
  2084.             for (int y = 0; y < (int)gworld->getHeight(); y++) {
  2085.                 if (cells[x][y] != FREE) continue;
  2086.                 int dist = stepMap[x][y];
  2087.                 int stepsCeil = maxStepsCeil;
  2088.                 int stepsFloor = maxStepsFloor;
  2089.  
  2090.                 double probCoef = 0.;
  2091.                 TrooperStance possibleStance = STANDING;
  2092.  
  2093.                 for (int stance = STANDING; stance >= PRONE; stance--) {
  2094.                     bool skip = false;
  2095.                     bool found = false;
  2096.  
  2097.                     // check if this trooper shooted somebody
  2098.                     for (int l = 0; l < (int)lastShooted.size(); l++) {
  2099.                         LastShooted& ls = lastShooted[l];
  2100.                         bool possible = false;
  2101.                         for (int e = 0; e < (int)ls.possibleEnemies.size(); e++) {
  2102.                             if (ls.possibleEnemies[e].getPlayerId() == trooper.getPlayerId() &&
  2103.                                 ls.possibleEnemies[e].getType() == trooper.getType()) {
  2104.                                 found = true;
  2105.                                 if (ls.possibleEnemies[e].getX() == x &&
  2106.                                     ls.possibleEnemies[e].getY() == y &&
  2107.                                     ls.possibleEnemies[e].getStance() >= stance) {
  2108.                                     possible = true;
  2109.                                     break;
  2110.                                 }
  2111.                             }
  2112.                         }
  2113.  
  2114.                         if (!possible) {
  2115.                             skip = true;
  2116.                             break;
  2117.                         }
  2118.                     }
  2119.  
  2120.                     if (found && skip) continue;
  2121.  
  2122.                     if (inFog(x, y, (TrooperStance)stance,
  2123.                         trooper.getType() == SNIPER ? currentFogSniper : currentFog)) {
  2124.                         // in fog now, check if was not in fog before
  2125.                         bool sawIt = false;
  2126.                         int maxIt = 2; // look to the past for 2 iterations
  2127.                         // find who saw this position last time
  2128.                         for (int j = 0; j < maxTroops*maxIt; j++) {
  2129.                             int tIndex = curTroopIndex - j;
  2130.                             int it = j / maxTroops;
  2131.                             while (tIndex < 0) tIndex += maxTroops;
  2132.                             if (it >= (int)lastFogs[tIndex].size()) {
  2133.                                 break;
  2134.                             }
  2135.                             const Fog& thatFog = trooper.getType() == SNIPER ? lastFogsSniper[tIndex][it] : lastFogs[tIndex][it];
  2136.                             if (!inFog(x, y, (TrooperStance)stance, thatFog)) {
  2137.                                 // he saw this position j submoves before
  2138.                                 sawIt = true;
  2139.                                 double numTurns = numTurnsSinceSubMove(trooper, currentSubMove - j);
  2140.                                 if (numTurns == 0.) {
  2141.                                     break;
  2142.                                 } else if (numTurns <= 1) {
  2143.                                     if (probCoef < 0.5) {
  2144.                                         probCoef = 0.5;
  2145.                                         possibleStance = (TrooperStance)stance;
  2146.                                     }
  2147.                                     break;
  2148.                                 } else {
  2149.                                     if (probCoef < 1.) {
  2150.                                         probCoef = 1.;
  2151.                                         possibleStance = (TrooperStance)stance;
  2152.                                     }
  2153.                                     break;
  2154.                                 }
  2155.                             }
  2156.                         }
  2157.                         if (!sawIt) {
  2158.                             // never saw this position, no restrictions
  2159.                             probCoef = 1.;
  2160.                             possibleStance = (TrooperStance)stance;
  2161.                             break;
  2162.                         }
  2163.                     }
  2164.                 }
  2165.  
  2166.                 // create new virtual trooper and place to position.
  2167.                 TrooperStateDiff diff;
  2168.                 diff.actionPoints = maxActionPointsPerTurn - trooper.getActionPoints();
  2169.                 diff.x = x - trooper.getX();
  2170.                 diff.y = y - trooper.getY();
  2171.                 diff.stance = possibleStance - trooper.getStance();
  2172.                 if (numTurnsSinceLastSeen(lastSeen[t]) > 4) diff.plusGrenade;
  2173.                 Trooper virtualTrooper = newVirtualTrooper(trooper,diff);
  2174.                
  2175.                 if (probCoef > 0.) {
  2176.                     stepsCeil -= (STANDING - possibleStance);
  2177.                     stepsFloor -= (STANDING - possibleStance);
  2178.                     if (dist <= stepsCeil) {
  2179.                         // enough steps to reach this point
  2180.                         double cellProb = 1.;
  2181.                         if (validPoint(playerInfo[(int)trooper.getPlayerId()].approximatePosition)) {
  2182.                             // first, try to use approximate position of player if known
  2183.                             probCoef = 1.;
  2184.                             int mDist = manhattanDistance(playerInfo[(int)trooper.getPlayerId()].approximatePosition, Point(x,y));
  2185.                             if (mDist < distToProbNearTeammateSize) {
  2186.                                 cellProb = distToProbNearTeammate[mDist];
  2187.                             } else {
  2188.                                 cellProb = distToProbNearTeammate[distToProbNearTeammateSize-1];
  2189.                             }
  2190.                         } else if (lastSeenEnemy < 3 * maxTroops) {
  2191.                             // if no, try to estimate by average speed
  2192.                             double maxSpeed = 5;
  2193.                             double averageSpeed = playerInfo[(int)trooper.getPlayerId()].averageSpeed;
  2194.                             double thisSpeedRatioCeil = (double)dist/stepsCeil;
  2195.                             double thisSpeedRatioFloor = (double)dist/stepsFloor;
  2196.                             double diff = min(fabs(thisSpeedRatioCeil * maxSpeed - averageSpeed),
  2197.                                 fabs(thisSpeedRatioFloor * maxSpeed - averageSpeed));
  2198.                             if (diff < 0.5) {
  2199.                                 cellProb = 10.;
  2200.                             } else if (diff < 1) {
  2201.                                 cellProb = 8.;
  2202.                             } else if (diff < 1.5) {
  2203.                                 cellProb = 5.;
  2204.                             } else {
  2205.                                 cellProb = 1.;
  2206.                             }
  2207.                         } else {
  2208.                             // no information about player, assume they are somethere near me
  2209.                             if (squareDist(*gself, x, y) <= 12) {
  2210.                                 cellProb = 5;
  2211.                             } else {
  2212.                                 cellProb = 1;
  2213.                             }
  2214.                         }
  2215.                         cellProb *= probCoef;
  2216.  
  2217.                         if (trooper.getX() == x && trooper.getY() == y) {
  2218.                             // last seen in the same position
  2219.                             if (numTurns < 1) {
  2220.                                 // 50/50 he is there
  2221.                                 cellProb *= 10;
  2222.                             } else if (numTurns < 2) {
  2223.                                 // probably still stay there
  2224.                                 cellProb *= 3;
  2225.                             }
  2226.  
  2227.                             if (trooper.getType() == FIELD_MEDIC && numTurns < 2) {
  2228.                                 int needHeal = trooper.getMaximalHitpoints() - trooper.getHitpoints();
  2229.                                 int maxActionPointsPerTurn = trooper.getInitialActionPoints();
  2230.                                 if (!playerInfo[(int)trooper.getPlayerId()].isDead(COMMANDER)) {
  2231.                                     maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();
  2232.                                 }
  2233.  
  2234.                                 int wholeActionPointsCeil = maxActionPointsPerTurn;
  2235.  
  2236.                                 // Probably it was healed
  2237.                                 if (trooper.isHoldingMedikit()) {
  2238.                                     needHeal -= ggame->getMedikitHealSelfBonusHitpoints();
  2239.                                     wholeActionPointsCeil -= ggame->getMedikitUseCost();
  2240.                                 }
  2241.  
  2242.                                 int healTime = (needHeal + ggame->getFieldMedicHealSelfBonusHitpoints() - 1) / ggame->getFieldMedicHealSelfBonusHitpoints() * ggame->getFieldMedicHealCost();
  2243.                                 wholeActionPointsCeil -= healTime;
  2244.  
  2245.                                 if (wholeActionPointsCeil < getMoveCost(trooper.getStance())) {
  2246.                                     // likely stay there and heal himself
  2247.                                     cellProb *= 5;
  2248.                                 }
  2249.                             }
  2250.                         }
  2251.  
  2252.                         TriBool shootedThere = isShootedThere(virtualTrooper);
  2253.                         if (shootedThere == TRUE) {
  2254.                             cellProb *= 50;
  2255.                         } else if (shootedThere == FALSE) {
  2256.                             continue;
  2257.                         }
  2258.  
  2259.                         trooperProbs[x][y].push_back(std::pair<double, Trooper>(cellProb, virtualTrooper));
  2260.                         totalProb += cellProb;
  2261.                     }
  2262.                 }
  2263.             }
  2264.         }
  2265.  
  2266.         // normalize probabilities
  2267.         for (int x = 0; x < (int)gworld->getWidth(); x++) {
  2268.             for (int y = 0; y < (int)gworld->getHeight(); y++) {
  2269.                 if (trooperProbs[x][y].size() == 0) continue;
  2270.                 const Trooper& that = trooperProbs[x][y].rbegin()->second;
  2271.                 if (that.getPlayerId() == trooper.getPlayerId() &&
  2272.                     that.getType() == trooper.getType()) {
  2273.                     trooperProbs[x][y].rbegin()->first /= (double)totalProb;
  2274.                 }
  2275.             }
  2276.         }
  2277.     }
  2278.  
  2279.     // normalize probabilities over troopers
  2280.     for (int x = 0; x < (int)gworld->getWidth(); x++) {
  2281.         for (int y = 0; y < (int)gworld->getHeight(); y++) {
  2282.             std::vector<std::pair<double, Trooper> >& probs = trooperProbs[x][y];
  2283.             if (probs.size() == 0) continue;
  2284.  
  2285.             double totalProb = 0;
  2286.             for (int i = 0; i < (int)probs.size(); i++) {
  2287.                 if (probs[i].first > 1.) {
  2288.                     SHOULD_NOT_HAPPEN;
  2289.                     probs[i].first = 1.;
  2290.                 }
  2291.                 if (probs[i].first == 1.) {
  2292.                     // leave only this trooper
  2293.                     probs[0] = probs[i];
  2294.                     probs.resize(1);
  2295.                     totalProb = 1.;
  2296.                     break;
  2297.                 }
  2298.                 totalProb += probs[i].first;
  2299.             }
  2300.  
  2301.             if (totalProb > 1.) {
  2302.                 for (int i = 0; i < (int)probs.size(); i++) {
  2303.                     probs[i].first /= totalProb;
  2304.                 }
  2305.             }
  2306.         }
  2307.     }
  2308. }
  2309.  
  2310. bool isAttackAction(ActionType action) {
  2311.     switch (action)
  2312.     {
  2313.     case model::SHOOT:
  2314.     case model::THROW_GRENADE:
  2315.         return true;
  2316.     default:
  2317.         return false;
  2318.     }
  2319.  
  2320. }
  2321.  
  2322. bool complexComparison(const Target& target1, const Target& target2) {
  2323.     int scoreDiff = target1.score - target2.score;
  2324.     double scoreNextTurnDiff = target1.scoreNextTurn - target2.scoreNextTurn;
  2325.     double safetyDiff = target1.safety - target2.safety;
  2326.     double priorityDiff = target1.priority - target2.priority;
  2327.  
  2328.     // do not take into account priority for different types of targets
  2329.     if (isAttackAction(target1.action.actionType) != isAttackAction(target2.action.actionType)) priorityDiff = 0;
  2330.  
  2331.     int priorityCoef = 1;
  2332.    
  2333.     if (tactics == NORMAL) {
  2334.         priorityCoef = 2;
  2335.     }
  2336.     if (tactics == AGRESSIVE) {
  2337.         priorityCoef = 7;
  2338.     }
  2339.     if (tactics == RUSH) {
  2340.         priorityCoef = 15;
  2341.     }
  2342.  
  2343.     if (mapType == CHEESER) {
  2344.         // otherwise they are just staying as fools
  2345.         priorityCoef *= 2;
  2346.     }
  2347.  
  2348.     if (gworld->getMoveIndex() < 15 && gself->getActionPoints() >= 4 && currentMode == TRAVEL) {
  2349.         // be more active in the beginning
  2350.         priorityCoef = 20;
  2351.     }
  2352.  
  2353.     if (!isAttackAction(target1.action.actionType)) {
  2354.         if (gself->getType() == FIELD_MEDIC) {
  2355.             // careful if medic
  2356.             priorityCoef /= 4;
  2357.         }
  2358.         if (gself->getType() != leader) {
  2359.             // careful if not leader
  2360.             priorityCoef = priorityCoef * 3 / 4;
  2361.         }
  2362.     }
  2363.    
  2364.     if ((currentMode == TRAVEL || gtLastUpdated == -1) &&
  2365.         (gself->getType() == COMMANDER || gself->getType() == leader || gself->getType() == SCOUT) &&
  2366.         gself->getActionPoints() >= 6) {
  2367.         // berserk
  2368.         safetyDiff /= 3;
  2369.     }
  2370.  
  2371.     priorityDiff *= priorityCoef;
  2372.  
  2373.     // quiet safe and good score diff
  2374.     if (target1.safety >= 50 && (scoreDiff > 50)) return true;
  2375.     if (target2.safety >= 50 && (scoreDiff < -50)) return false;
  2376.  
  2377.     if (target1.safety >= 50 && safetyDiff >= -30 && (scoreDiff > 20)) return true;
  2378.     if (target2.safety >= 50 && safetyDiff <= 30 && (scoreDiff < -20)) return false;
  2379.  
  2380.     // important person
  2381.     bool important = gself->getType() == SCOUT || gself->getType() == SNIPER;
  2382.     // when somebody is killed all left are important
  2383.     if (numLeftTroopers((int)me->getId()) < maxTroops) important = true;
  2384.  
  2385.     if (target2.safety < 10 && target1.safety > 0 && safetyDiff >= 20 && (scoreDiff > -20 || important && scoreDiff > -50)) return true;
  2386.     if (target1.safety < 10 && target2.safety > 0 && safetyDiff <= -20 && (scoreDiff < 20 || important && scoreDiff < 50)) return false;
  2387.  
  2388.     if (target2.safety < 10 && target1.safety > -20 && target1.visibileProb < 0.5 && safetyDiff >= 20 && (scoreDiff > -20 || important && scoreDiff > -50)) return true;
  2389.     if (target1.safety < 10 && target2.safety > -20 && target2.visibileProb < 0.5 && safetyDiff <= -20 && (scoreDiff < 20 || important && scoreDiff < 50)) return false;
  2390.  
  2391.     // ignore priority if not safe
  2392.     if (target1.safety < 10 && target2.safety < 10 && !isAttackAction(target1.action.actionType)) priorityDiff = 0;
  2393.  
  2394.     if (scoreDiff + scoreNextTurnDiff + safetyDiff + priorityDiff > 50) return true;
  2395.     if (scoreDiff + scoreNextTurnDiff + safetyDiff + priorityDiff < -50) return false;
  2396.  
  2397.     if (target1.safety >= 80 && safetyDiff >= -20 && (scoreDiff + priorityDiff + scoreNextTurnDiff > 5)) return true;
  2398.     if (target2.safety >= 80 && safetyDiff <= 20 && (scoreDiff + priorityDiff + scoreNextTurnDiff < -5)) return false;
  2399.  
  2400.     if (target1.safety >= 50 && safetyDiff >= -30 && (scoreDiff + priorityDiff + scoreNextTurnDiff > 20)) return true;
  2401.     if (target2.safety >= 50 && safetyDiff <= 30 && (scoreDiff + priorityDiff + scoreNextTurnDiff < -20)) return false;
  2402.  
  2403.     if (target1.safety >= 50 && (scoreDiff + priorityDiff + scoreNextTurnDiff > 60)) return true;
  2404.     if (target2.safety >= 50 && (scoreDiff + priorityDiff + scoreNextTurnDiff < -60)) return false;
  2405.  
  2406.     if (scoreDiff + safetyDiff + priorityDiff + scoreNextTurnDiff > 0) return true;
  2407.     if (scoreDiff + safetyDiff + priorityDiff + scoreNextTurnDiff < 0) return false;
  2408.  
  2409.     if (scoreDiff + safetyDiff + priorityDiff > 0) return true;
  2410.     if (scoreDiff + safetyDiff + priorityDiff < 0) return false;
  2411.  
  2412.     if (priorityDiff > 0) return true;
  2413.     if (priorityDiff < 0) return false;
  2414.  
  2415.     // very unlikely but for reproducibility
  2416.     if (target1.id < target2.id) return true;
  2417.     if (target1.id > target2.id) return false;
  2418.  
  2419.     return false;
  2420. }
  2421.  
  2422. bool compareActions(const Action& action1, const Action& action2) {
  2423.     if (action1.troopersKilled > action2.troopersKilled) return true;
  2424.     if (action1.troopersKilled < action2.troopersKilled) return false;
  2425.  
  2426.     double damageDiff = action1.damage - action2.damage;
  2427.     int priorityDiff = action1.priority - action2.priority;
  2428.  
  2429.     if (damageDiff > 30) return true;
  2430.     if (damageDiff < -30) return false;
  2431.  
  2432.     if (action1.actionType == USE_MEDIKIT) damageDiff -= 15;
  2433.     if (action2.actionType == USE_MEDIKIT) damageDiff += 15;
  2434.     if (action1.actionType == THROW_GRENADE) damageDiff -= 15;
  2435.     if (action2.actionType == THROW_GRENADE) damageDiff += 15;
  2436.  
  2437.     if (damageDiff + 2 * priorityDiff > 0) return true;
  2438.     if (damageDiff + 2 * priorityDiff < 0) return false;
  2439.  
  2440.     return false;
  2441. }
  2442.  
  2443. bool visibleForEnemies(const Trooper& trooper) {
  2444.     // process enemies
  2445.     for (size_t ee = 0; ee < lastSeen.size(); ++ee) {
  2446.         const Trooper& enemy = lastSeen[ee].first;
  2447.  
  2448.         if (isDead(enemy)) continue;
  2449.         if (stillThere(lastSeen[ee]) < MOST_LIKELY_TRUE) continue;
  2450.  
  2451.         double visionRange = enemy.getVisionRange();
  2452.         if (trooper.getType() == SNIPER && enemy.getType() != SCOUT) {
  2453.             if (trooper.getStance() == KNEELING) visionRange -= 0.5;
  2454.             if (trooper.getStance() == PRONE) visionRange -= 1.;
  2455.         }
  2456.  
  2457.         if (!enemy.isTeammate() &&
  2458.             gworld->isVisible(visionRange,  
  2459.             enemy.getX(), enemy.getY(), STANDING /* can easily stand up even if seen as prone or kneeling */,        
  2460.             trooper.getX(), trooper.getY(), trooper.getStance())) {
  2461.             return true;
  2462.         }
  2463.     }
  2464.     return false;
  2465. }
  2466.  
  2467. int getActionPriority(int damage, const Trooper& trooper, bool killed) {
  2468.     if (damage == 0) return 0;
  2469.    
  2470.     int turnsBeforeOurs = 0;
  2471.     const vector<Trooper>& troopers = gworld->getTroopers();
  2472.     for (int tt = 0; tt < (int)troopers.size(); tt++) {
  2473.         const Trooper& teammate = troopers[tt];
  2474.         if (teammate.isTeammate()) {
  2475.             TriBool later = turnsLater(trooper, teammate);
  2476.             if (later == FALSE) {
  2477.                 turnsBeforeOurs += 2;
  2478.             } else if (later == PROBABLY) {
  2479.                 turnsBeforeOurs += 1;
  2480.             }
  2481.         }
  2482.     }
  2483.  
  2484.     int priotityBonus  = 0;
  2485.  
  2486.     if (trooper.getType() == FIELD_MEDIC) priotityBonus += 10;
  2487.     if (trooper.getType() == COMMANDER) priotityBonus += 5;
  2488.     if (trooper.getType() == SNIPER) {
  2489.         if (mapType == CHEESER) {
  2490.             // sniper is useless on this map
  2491.             priotityBonus -= 5;
  2492.         } else {
  2493.             priotityBonus += 10;
  2494.         }
  2495.     }
  2496.     if (trooper.getType() == SCOUT) priotityBonus += 15;
  2497.     priotityBonus += turnsBeforeOurs * 3;
  2498.  
  2499.     if (killed) {
  2500.         priotityBonus *= 2;
  2501.     } else {
  2502.         // scale to actual damage
  2503.         priotityBonus = priotityBonus * damage / trooper.getHitpoints();
  2504.     }
  2505.  
  2506.     return priotityBonus;
  2507. }
  2508.  
  2509. int compactnessSafetyPenalty(int diff, bool leader) {
  2510.     int safety = 0;
  2511.  
  2512.     // whether to apply soft restrictions
  2513.     bool soft = currentMode == TRAVEL || mapType == CHEESER;
  2514.  
  2515.     if (leader) {
  2516.         if (diff > (soft ? 8 : 6)) {
  2517.             safety -= diff * (soft ? 4 : 7);
  2518.         }
  2519.     } else {
  2520.         if (diff > (soft ? 5 : 3)) {
  2521.             safety -= diff * (soft ? 4 : 7);
  2522.         }
  2523.     }
  2524.  
  2525.     if (currentMode == COMBAT) safety /= 2;
  2526.    
  2527.     return safety;
  2528. }
  2529.  
  2530. int computeMaxFireDamageNoMove(const Trooper& trooper, const Position& trooperPosition, Position targetPosition, int actionPoints) {
  2531.     double shootingRange = trooper.getShootingRange();
  2532.     if (trooper.getType() == SNIPER) {
  2533.         // count sniper range bonus
  2534.         shootingRange -= trooperPosition.stance - trooper.getStance();
  2535.     }
  2536.     bool canShoot = gworld->isVisible(shootingRange,
  2537.         trooperPosition.getX(), trooperPosition.getY(), trooperPosition.getStance(),
  2538.         targetPosition.getX(), targetPosition.getY(), targetPosition.getStance());
  2539.  
  2540.     if (canShoot) {
  2541.         int numShots = actionPoints / trooper.getShootCost();
  2542.         int singleDamage = trooper.getDamage(trooperPosition.getStance());
  2543.         int totalDamage = singleDamage * numShots;
  2544.         return totalDamage;
  2545.     }
  2546.     return 0;
  2547. }
  2548.  
  2549. int computeMaxDamageNoMove(const Trooper& trooper, const Position& trooperPosition, const Position& targetPosition, int actionPoints) {
  2550.     int fireDamage = computeMaxFireDamageNoMove(trooper, trooperPosition, targetPosition, actionPoints);
  2551.  
  2552.     bool grenade = trooper.isHoldingGrenade();
  2553.  
  2554.     if (grenade && actionPoints >= ggame->getGrenadeThrowCost()) {
  2555.         double throwDist = ggame->getGrenadeThrowRange();
  2556.         Point throwPoint(targetPosition);
  2557.                
  2558.         int grenadeDamage = 0;
  2559.         if (squareDist(trooperPosition, targetPosition) <= throwDist * throwDist) {
  2560.             grenadeDamage = ggame->getGrenadeDirectDamage();
  2561.             if (maxTroops == 5) {
  2562.                 // likely shoot also nearby
  2563.                 grenadeDamage += ggame->getGrenadeCollateralDamage() / 2;
  2564.             } else if (maxTroops == 4) {
  2565.                 // likely shoot also nearby
  2566.                 grenadeDamage += ggame->getGrenadeCollateralDamage() / 3;
  2567.             }
  2568.         } else if (
  2569.             validPoint(Point(targetPosition) + Point(-1,0)) &&
  2570.             squareDist(trooperPosition, Point(targetPosition) + Point(-1,0)) <= throwDist * throwDist ||
  2571.             validPoint(Point(targetPosition) + Point(1,0)) &&
  2572.             squareDist(trooperPosition, Point(targetPosition) + Point(1,0)) <= throwDist * throwDist ||
  2573.             validPoint(Point(targetPosition) + Point(0,1)) &&
  2574.             squareDist(trooperPosition, Point(targetPosition) + Point(0,1)) <= throwDist * throwDist ||
  2575.             validPoint(Point(targetPosition) + Point(0,-1)) &&
  2576.             squareDist(trooperPosition, Point(targetPosition) + Point(0,-1)) <= throwDist * throwDist
  2577.             ) {
  2578.             grenadeDamage = ggame->getGrenadeCollateralDamage();            
  2579.         }
  2580.  
  2581.         if (mapType == CHEESER) {
  2582.             // otherwise they don't want to move anythere
  2583.             grenadeDamage /= 2;
  2584.         }
  2585.  
  2586.         if (grenadeDamage > 0) {
  2587.             int leftFireDamage = computeMaxFireDamageNoMove(trooper, trooperPosition, targetPosition, actionPoints - ggame->getGrenadeThrowCost());
  2588.             return std::max(grenadeDamage + leftFireDamage, fireDamage);
  2589.         }
  2590.     }
  2591.     return fireDamage;
  2592. }
  2593.  
  2594. int computeMaxDamage(const Trooper& trooper, Position targetPosition, Position* firePosition = 0, bool veryRoughEstimation = false) {
  2595.     // compute its stepmap
  2596.     int maxActionPoints = trooper.getInitialActionPoints();
  2597.     if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT &&
  2598.         playerInfo[(int)trooper.getPlayerId()].isDead(COMMANDER) != true) {
  2599.         maxActionPoints += ggame->getCommanderAuraBonusActionPoints();
  2600.     }
  2601.  
  2602.     if (trooper.isHoldingFieldRation()) maxActionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
  2603.  
  2604.     // at least he should fire or throw a grenage
  2605.     int maxSteps = (maxActionPoints - std::min(trooper.getShootCost(), ggame->getGrenadeThrowCost())) /
  2606.         ggame->getStandingMoveCost();
  2607.  
  2608.     double shootingRange = trooper.getShootingRange();
  2609.     if (trooper.getType() == SNIPER) {
  2610.         shootingRange += 2;
  2611.     }
  2612.  
  2613.     if (squareDist(trooper, targetPosition) > (shootingRange + maxSteps) * (shootingRange + maxSteps)) {
  2614.         // can skip it
  2615.         return 0;
  2616.     }
  2617.  
  2618.     if (veryRoughEstimation) {
  2619.         return computeMaxDamageNoMove(trooper, trooper, targetPosition, maxActionPoints);
  2620.     }
  2621.  
  2622.     const StepMap& stepMap = allStepMaps[trooper.getX()][trooper.getY()];
  2623.  
  2624.     int maxDamage = 0;
  2625.     int minX = trooper.getX() - maxSteps;
  2626.     if (minX < 0) minX = 0;
  2627.     int maxX = trooper.getX() + maxSteps;
  2628.     if (maxX >= gworld->getWidth()) maxX = gworld->getWidth()-1;
  2629.     int minY = trooper.getY() - maxSteps;
  2630.     if (minY < 0) minY = 0;
  2631.     int maxY = trooper.getY() + maxSteps;
  2632.     if (maxY >= gworld->getHeight()) maxY = gworld->getHeight()-1;
  2633.  
  2634.     for (int x = minX; x <= maxX; x++) {
  2635.         for (int y = minY; y <= maxY; y++) {
  2636.             if (stepMap[x][y] >= 0 && stepMap[x][y] <= maxSteps) {
  2637.                 // candidates for move
  2638.                 for (int i = 0; i < _TROOPER_STANCE_COUNT_; i++) {
  2639.                     TrooperStance stance = (TrooperStance)(trooper.getStance() + i);
  2640.                     if (stance >= _TROOPER_STANCE_COUNT_) stance = (TrooperStance)(stance - _TROOPER_STANCE_COUNT_);
  2641.                     Position position(Point(x,y), stance);
  2642.                     int moveCost = findFastestMove(stepMap, trooper.getStance(), position);
  2643.                     int timeForAction = maxActionPoints - moveCost;
  2644.                     if (timeForAction < std::min(trooper.getShootCost(), ggame->getGrenadeThrowCost())) continue;
  2645.  
  2646.                     int mDamage = computeMaxDamageNoMove(trooper, Position(x, y, stance), targetPosition, maxActionPoints - moveCost);
  2647.                     if (mDamage > maxDamage) {
  2648.                         maxDamage = mDamage;
  2649.                         if (firePosition) *firePosition = position;
  2650.                     }
  2651.                 }
  2652.             }
  2653.         }
  2654.     }
  2655.  
  2656.     return maxDamage;
  2657. }
  2658.  
  2659. bool checkVisibilityNoMove(const Trooper& trooper, const Position& trooperPosition, const Position& targetPosition, bool sniper) {
  2660.     double visionRange = trooper.getVisionRange();
  2661.     if (sniper && trooper.getType() != SCOUT) {
  2662.         if (targetPosition.getStance() == KNEELING) visionRange -= 0.5;
  2663.         if (targetPosition.getStance() == PRONE) visionRange -= 1.;
  2664.     }
  2665.     return gworld->isVisible(visionRange,
  2666.         trooperPosition.getX(), trooperPosition.getY(), trooperPosition.getStance(),
  2667.         targetPosition.getX(), targetPosition.getY(), targetPosition.getStance());
  2668. }
  2669.  
  2670. // compute probability that trooper will see target position during his move
  2671. double checkVisibility(const Trooper& trooper, Position targetPosition, bool sniper, Position* seePosition = 0, bool veryRough = false) {
  2672.     int maxActionPoints = trooper.getInitialActionPoints();
  2673.     if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT &&
  2674.         playerInfo[(int)trooper.getPlayerId()].isDead(COMMANDER) != true) {
  2675.         maxActionPoints += ggame->getCommanderAuraBonusActionPoints();
  2676.     }
  2677.  
  2678.     if (trooper.isHoldingFieldRation()) maxActionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
  2679.  
  2680.     int maxSteps = maxActionPoints / ggame->getStandingMoveCost();
  2681.  
  2682.     // unlikely he will go to whole action points, at least 2 steps for hiding
  2683.     maxSteps -= 2;
  2684.  
  2685.     if (squareDist(trooper, targetPosition) > (trooper.getVisionRange() + maxSteps) * (trooper.getVisionRange() + maxSteps)) {
  2686.         // can skip it
  2687.         return 0.;
  2688.     }
  2689.  
  2690.     if (veryRough) return 1.;
  2691.  
  2692.     const StepMap& stepMap = allStepMaps[trooper.getX()][trooper.getY()];
  2693.  
  2694.     int minX = trooper.getX() - maxSteps;
  2695.     if (minX < 0) minX = 0;
  2696.     int maxX = trooper.getX() + maxSteps;
  2697.     if (maxX >= gworld->getWidth()) maxX = gworld->getWidth()-1;
  2698.     int minY = trooper.getY() - maxSteps;
  2699.     if (minY < 0) minY = 0;
  2700.     int maxY = trooper.getY() + maxSteps;
  2701.     if (maxY >= gworld->getHeight()) maxY = gworld->getHeight()-1;
  2702.  
  2703.     int minActionPoints = 20;
  2704.  
  2705.     for (int x = minX; x <= maxX; x++) {
  2706.         for (int y = minY; y <= maxY; y++) {
  2707.             if (stepMap[x][y] >= 0 && stepMap[x][y] <= maxSteps) {
  2708.                 // candidates for move
  2709.                 for (int i = 0; i < _TROOPER_STANCE_COUNT_; i++) {
  2710.                     TrooperStance stance = (TrooperStance)((trooper.getStance() + i) % _TROOPER_STANCE_COUNT_);
  2711.                     Position position(Point(x,y), stance);
  2712.                     int moveCost = findFastestMove(stepMap, trooper.getStance(), position);
  2713.                     if (maxActionPoints < moveCost) continue;
  2714.  
  2715.                     bool visible = checkVisibilityNoMove(trooper, Position(x, y, stance), targetPosition, sniper);
  2716.                     if (visible) {
  2717.                         if (moveCost < minActionPoints) {
  2718.                             minActionPoints = moveCost;
  2719.                             if (seePosition) *seePosition = position;
  2720.                         }
  2721.                     }
  2722.                 }
  2723.             }
  2724.         }
  2725.     }
  2726.  
  2727.     if (minActionPoints == 20) return 0.;
  2728.  
  2729.     // spent less than a half of his points. Quiet likely
  2730.     if (minActionPoints <= maxActionPoints/2) return 1.;
  2731.  
  2732.     if (mapType == CHEESER) {
  2733.         return 0.3;
  2734.     } else {
  2735.         return 0.5;
  2736.     }
  2737. }
  2738.  
  2739. // caches
  2740. std::vector<pair<Position, double> > damageToPosition;
  2741. std::vector<pair<Position, double> > damageToPosition1;
  2742. std::vector<pair<Position, double> > damageFromPosition;
  2743. std::vector<pair<Position, double> > positionVisibilities;
  2744.  
  2745. double computeDamageByTrooper(const Trooper& candidate) {
  2746.     // look up cache first
  2747.     for (int i = 0; i < (int)damageFromPosition.size(); i++) {
  2748.         if (Position(candidate) == damageFromPosition[i].first) {
  2749.             return damageFromPosition[i].second;
  2750.         }
  2751.     }
  2752.  
  2753.     double maxDamageNextTurn = 0;
  2754.  
  2755.     for (int x = 0; x < gworld->getWidth(); x++) {
  2756.         for (int y = 0; y < gworld->getHeight(); y++) {
  2757.             const std::vector<std::pair<double, Trooper> >& probs = trooperProbs[x][y];
  2758.             int maxStance = PRONE;
  2759.             double totalProb = 0.;
  2760.             for (int i = 0; i < (int)probs.size(); i++) {
  2761.                 if (probs[i].first > 0.01) {
  2762.                     totalProb += probs[i].first;
  2763.                     if (probs[i].second.getStance() > maxStance) maxStance = probs[i].second.getStance();
  2764.                 }
  2765.             }
  2766.            
  2767.             if (totalProb > 0) {
  2768.                 maxDamageNextTurn += (totalProb * computeMaxDamage(candidate, Position(x, y, (TrooperStance)maxStance)));
  2769.             }
  2770.  
  2771.             if (gworld->getCells()[x][y] == FREE) {
  2772.                 for (int i = 0; i < (int)lastSeen.size(); i++) {
  2773.                     if (lastSeen[i].first.isTeammate()) continue;
  2774.                     if (isDead(lastSeen[i].first)) continue;
  2775.                     if (currentSubMove - lastSeen[i].second <= maxTroops) {
  2776.                         if (manhattanDistance(lastSeen[i].first, Point(x,y)) < 5 &&
  2777.                             (gworld->isVisible(candidate.getShootingRange(),
  2778.                                 candidate.getX(), candidate.getY(), candidate.getStance(),
  2779.                                 x, y, candidate.getStance()) ||
  2780.                                 candidate.isHoldingGrenade() && squareDist(candidate, x, y) <= ggame->getGrenadeThrowRange() * ggame->getGrenadeThrowRange())) {
  2781.                             maxDamageNextTurn += maxTroops;
  2782.                         }
  2783.                     }
  2784.                 }
  2785.             }
  2786.         }
  2787.     }
  2788.  
  2789.     damageFromPosition.push_back(std::pair<Position, double>(Position(candidate), maxDamageNextTurn));
  2790.  
  2791.     return maxDamageNextTurn;
  2792. }
  2793.  
  2794. double computeDamageToTrooper(const Trooper& trooper, bool secondaryTarget = true, bool checkTurnsLater = false) {
  2795.     if (checkTurnsLater == false && secondaryTarget == true) {
  2796.         // look up cache first
  2797.         for (int i = 0; i < (int)damageToPosition.size(); i++) {
  2798.             if (Position(trooper) == damageToPosition[i].first) {
  2799.                 return damageToPosition[i].second;
  2800.             }
  2801.         }
  2802.     } else {
  2803.         // look up cache first
  2804.         for (int i = 0; i < (int)damageToPosition1.size(); i++) {
  2805.             if (Position(trooper) == damageToPosition1[i].first) {
  2806.                 return damageToPosition1[i].second;
  2807.             }
  2808.         }
  2809.     }
  2810.  
  2811.     const vector<Trooper>& troopers = gworld->getTroopers();
  2812.    
  2813.     double totalDamage = 0.;
  2814.  
  2815.     int minX = trooper.getX() - 13 /* max move + shoot range */;
  2816.     if (minX < 0) minX = 0;
  2817.     int maxX = trooper.getX() + 13;
  2818.     if (maxX > gworld->getWidth() - 1) maxX = gworld->getWidth() - 1;
  2819.     int minY = trooper.getY() - 13;
  2820.     if (minY < 0) minY = 0;
  2821.     int maxY = trooper.getY() + 13;
  2822.     if (maxY > gworld->getHeight() - 1) maxY = gworld->getHeight() - 1;
  2823.     for (int x = minX; x <= maxX; x++) {
  2824.         for (int y = minY; y <= maxY; y++) {
  2825.             const std::vector<std::pair<double, Trooper> >& probs = trooperProbs[x][y];
  2826.             for (int i = 0; i < (int)probs.size(); i++) {
  2827.                 double prob = probs[i].first;
  2828.                 const Trooper& enemy = probs[i].second;
  2829.  
  2830.                 if (enemy.isTeammate()) {
  2831.                     SHOULD_NOT_HAPPEN;
  2832.                     continue;
  2833.                 }
  2834.  
  2835.                 if (checkTurnsLater && turnsLater(enemy, trooper) == TRUE) continue;
  2836.  
  2837.                 if (prob < 0.001) continue;
  2838.  
  2839.                 if (prob < 0.01) {
  2840.                     int damage = computeMaxDamage(enemy, trooper, 0, true);
  2841.                     bool critical = (damage >= (trooper.getHitpoints() / 2));
  2842.                     if (critical) {
  2843.                         if (mapType == CHEESER) {
  2844.                             if (prob < 0.02) prob = 0.02;
  2845.                         } else {
  2846.                             prob *= 3;
  2847.                         }
  2848.                     }
  2849.                     if (prob >= 1.) prob = 1.;
  2850.                     totalDamage += damage * prob;
  2851.                     continue;
  2852.                 }
  2853.  
  2854.                 {
  2855.                     // more complex and accurate estimation
  2856.                     Position firePosition(enemy);
  2857.                     int maxDamage = computeMaxDamage(enemy, trooper, &firePosition);
  2858.  
  2859.                     if (maxDamage > 0) {
  2860. //                      std::cout << enemy << " can hit " << maxDamage << " through " << firePosition << std::endl;
  2861.  
  2862.                         {
  2863.                             int numTeammates = 0;
  2864.                             for (size_t tt = 0; tt < troopers.size(); ++tt) {
  2865.                                 Trooper teammate = troopers.at(tt);
  2866.                                 if (teammate.isTeammate() &&
  2867.                                     teammate.getType() != trooper.getType()) {
  2868.                                     if (gworld->isVisible(teammate.getShootingRange(), teammate.getX(), teammate.getY(), teammate.getStance(),
  2869.                                         enemy.getX(), enemy.getY(), PRONE)) {
  2870.                                         bool found = false;
  2871.                                         const LastSeen& ls = getLastSeen((int)enemy.getPlayerId(), enemy.getType(), &found);
  2872.                                         if (!gworld->isVisible(teammate.getShootingRange(), teammate.getX(), teammate.getY(), teammate.getStance(),
  2873.                                             ls.first.getX(), ls.first.getY(), PRONE)) {
  2874.                                             // was inshootable but became shootable. Quiet unlikely
  2875.                                             maxDamage = maxDamage * 3 / 4;    
  2876.                                             numTeammates++;
  2877.                                             if (numTeammates >= 2) break;
  2878.                                         }
  2879.                                     }
  2880.                                 }
  2881.                             }
  2882.                         }
  2883.  
  2884.                         int maxDamageToOthers = 0;
  2885.                        
  2886.                         if (secondaryTarget) {
  2887.                             for (size_t tt = 0; tt < troopers.size(); ++tt) {
  2888.                                 Trooper teammate = troopers.at(tt);
  2889.                                 if (teammate.isTeammate() &&
  2890.                                     teammate.getType() != trooper.getType()) {
  2891.                                     if (visibleForEnemies(teammate) &&
  2892.                                         turnsLater(enemy, teammate) == FALSE) {
  2893.                                         int damageToTeammate = computeMaxDamage(enemy, teammate);
  2894.                                         if (damageToTeammate > maxDamageToOthers) {
  2895.                                             maxDamageToOthers = damageToTeammate;
  2896.                                         }
  2897.                                     }
  2898.                                 }
  2899.                             }
  2900.                         }
  2901.  
  2902.                         if (maxDamage > maxDamageToOthers * 2 || maxDamage >= trooper.getHitpoints() - 20) {
  2903.                             bool critical = (maxDamage >= (trooper.getHitpoints() / 2));
  2904.                             if (critical && prob < 0.4) {
  2905.                                 if (mapType == CHEESER) {
  2906.                                     if (prob < 0.05) prob = 0.05;
  2907.                                 } else {
  2908.                                     prob *= 2;
  2909.                                 }
  2910.                             }
  2911.                             if (prob >= 1.) prob = 1.;
  2912.                             totalDamage += maxDamage * prob;
  2913.                         }
  2914.                     }
  2915.                 }
  2916.             }
  2917.         }
  2918.     }
  2919.  
  2920.     if (checkTurnsLater == false && secondaryTarget == true) {
  2921.         damageToPosition.push_back(std::pair<Position, double>(Position(trooper), totalDamage));
  2922.     } else {
  2923.         damageToPosition1.push_back(std::pair<Position, double>(Position(trooper), totalDamage));
  2924.     }
  2925.     return totalDamage;
  2926. }
  2927.  
  2928. double getTrooperVisibility(const Trooper& trooper) {
  2929.     for (int i = 0; i < (int)positionVisibilities.size(); i++) {
  2930.         if (Position(trooper) == positionVisibilities[i].first) {
  2931.             return positionVisibilities[i].second;
  2932.         }
  2933.     }
  2934.    
  2935.     //const vector<Trooper>& troopers = gworld->getTroopers();
  2936.     double invisProb = 1.;
  2937.  
  2938.     int minX = trooper.getX() - 13 /* max move - 2 + vision range */;
  2939.     if (minX < 0) minX = 0;
  2940.     int maxX = trooper.getX() + 13;
  2941.     if (maxX > gworld->getWidth() - 1) maxX = gworld->getWidth() - 1;
  2942.     int minY = trooper.getY() - 13;
  2943.     if (minY < 0) minY = 0;
  2944.     int maxY = trooper.getY() + 13;
  2945.     if (maxY > gworld->getHeight() - 1) maxY = gworld->getHeight() - 1;
  2946.     for (int x = minX; x <= maxX; x++) {
  2947.         for (int y = minY; y <= maxY; y++) {
  2948.             const std::vector<std::pair<double, Trooper> >& probs = trooperProbs[x][y];
  2949.             for (int i = 0; i < (int)probs.size(); i++) {
  2950.                 double prob = probs[i].first;
  2951.                 const Trooper& enemy = probs[i].second;
  2952.                 if (prob < 0.001) continue;
  2953.  
  2954.                 if (enemy.isTeammate()) {
  2955.                     SHOULD_NOT_HAPPEN;
  2956.                     continue;
  2957.                 }
  2958.                 {
  2959.                     Position seePosition(enemy);
  2960.                     double seeProb = checkVisibility(enemy, trooper, trooper.getType() == SNIPER, &seePosition,  prob < 0.005);
  2961.                    
  2962.                     if (seeProb > 0) {
  2963.                         invisProb *= (1. - prob * seeProb);
  2964.                     }
  2965.                 }
  2966.             }
  2967.         }
  2968.     }
  2969.    
  2970.     positionVisibilities.push_back(std::pair<Position, double>(Position(trooper), 1-invisProb));
  2971.    
  2972.     return 1-invisProb;
  2973. }
  2974.  
  2975. Action& getAction(std::vector<Action>& actions, int x, int y, ActionType actiontype) {
  2976.     for (int i = 0; i < (int)actions.size(); i++) {
  2977.         Action& action = actions[i];
  2978.         if (action.actionType == actiontype && action.x == x && action.y == y) {
  2979.             return action;
  2980.         }
  2981.     }
  2982.     Action newAction;
  2983.     newAction.actionType = actiontype;
  2984.     newAction.x = x;
  2985.     newAction.y = y;
  2986.     actions.push_back(newAction);
  2987.     return *actions.rbegin();
  2988. }
  2989.  
  2990. // cache best actions for each position and number of action points
  2991. vector<std::pair<std::pair<Position, int>, Action> > bestActions;
  2992.  
  2993. Action findBestAction(const Trooper& candidate, int actionPoints) {
  2994.     for (int i = 0; i < (int)bestActions.size(); i++) {
  2995.         if (Position(candidate) == bestActions[i].first.first &&
  2996.             actionPoints == bestActions[i].first.second) {
  2997.             return bestActions[i].second;
  2998.         }
  2999.     }
  3000.  
  3001.     // insert default empty action
  3002.     vector<Action> actions(1);
  3003.     actions[0].actionType = END_TURN;
  3004.     actions[0].x = candidate.getX();
  3005.     actions[0].y = candidate.getY();
  3006.  
  3007.     if (candidate.getType() == COMMANDER && actionPoints >= ggame->getCommanderRequestEnemyDispositionCost()) {
  3008.         // for commander use request action as deafult
  3009.         actions[0].actionType = REQUEST_ENEMY_DISPOSITION;
  3010.         actions[0].priority += currentSubMove - gtLastUpdated;
  3011.         if (tactics == AGRESSIVE) actions[0].priority *= 2;
  3012.         if (tactics == RUSH) actions[0].priority *= 4;
  3013.     }
  3014.  
  3015.     if (actionPoints > 0) {
  3016.         // go through teammates first, probably heal them
  3017.         for (size_t i = 0; i < lastSeen.size(); ++i) {
  3018.             const Trooper& trooper = lastSeen[i].first;
  3019.             if (isDead(trooper)) continue;
  3020.  
  3021.             TriBool there = stillThere(lastSeen[i]);
  3022.             if (there < MOST_LIKELY_TRUE) continue;
  3023.  
  3024.             if (trooper.isTeammate()) {
  3025.                 if (squareDist(candidate, trooper) <= 1) {
  3026.                     // right near me or me
  3027.                     int needToHeal = trooper.getMaximalHitpoints() - trooper.getHitpoints();
  3028.  
  3029.                     double canDamageHim = computeDamageToTrooper(trooper, false, true);
  3030.                    
  3031.                     if (needToHeal > 0) {
  3032.                         if (candidate.getType() == FIELD_MEDIC) {
  3033.                             int numHeals = actionPoints / ggame->getFieldMedicHealCost();
  3034.                             if (numHeals > 0) {
  3035.                                 Action& action = getAction(actions, trooper.getX(), trooper.getY(), HEAL);
  3036.                                 int singleHeal = (candidate.getType() == trooper.getType()) ? ggame->getFieldMedicHealSelfBonusHitpoints() : ggame->getFieldMedicHealBonusHitpoints();
  3037.                                 int totalHeal = singleHeal * numHeals;
  3038.                                 if (totalHeal >= needToHeal) {
  3039.                                     numHeals = (needToHeal + singleHeal - 1) / singleHeal;
  3040.                                     action.damage += needToHeal;
  3041.                                 } else {
  3042.                                     action.damage += totalHeal;
  3043.                                 }
  3044.  
  3045.                                 if (trooper.getHitpoints() - canDamageHim <= 0) {
  3046.                                     // can die if not healed
  3047.                                     action.damage *= 2;
  3048.  
  3049.                                     if (trooper.getHitpoints() + totalHeal - canDamageHim > 0) {
  3050.                                         // will survive after our heal
  3051.                                         action.damage += 100;
  3052.                                     }
  3053.                                 }
  3054.  
  3055.                                 action.actionPoints = numHeals * ggame->getFieldMedicHealCost();
  3056.                             }
  3057.                         }
  3058.  
  3059.                         if (candidate.isHoldingMedikit() && (ggame->getMedikitUseCost() <= actionPoints)) {
  3060.                             int singleHeal = (candidate.getType() == trooper.getType()) ? ggame->getMedikitHealSelfBonusHitpoints() : ggame->getMedikitBonusHitpoints();
  3061.                             Action& action = getAction(actions, trooper.getX(), trooper.getY(), USE_MEDIKIT);
  3062.                             if (singleHeal >= needToHeal) {
  3063.                                 action.damage += needToHeal;
  3064.                             } else {
  3065.                                 action.damage += singleHeal;
  3066.                             }
  3067.  
  3068.                             if (trooper.getHitpoints() - canDamageHim <= 0) {
  3069.                                 // can die if not healed
  3070.                                 action.damage *= 2;
  3071.  
  3072.                                 if (trooper.getHitpoints() + singleHeal - canDamageHim > 0) {
  3073.                                     // will survive after our heal
  3074.                                     action.damage += 100;
  3075.                                 }
  3076.                             }
  3077.  
  3078.                             action.actionPoints = ggame->getMedikitUseCost();
  3079.                         }
  3080.                     }
  3081.                 }
  3082.             }
  3083.         }
  3084.  
  3085.         // then, go through all points on the map and try to shoot there
  3086.         for (int x = 0; x < gworld->getWidth(); x++) {
  3087.             for (int y = 0; y < gworld->getHeight(); y++) {
  3088.  
  3089.                 int canShootStance = _TROOPER_STANCE_COUNT_;
  3090.                
  3091.                 for (int stance = 0; stance < _TROOPER_STANCE_COUNT_; stance++) {
  3092.                     if (gworld->isVisible(candidate.getShootingRange(),
  3093.                         candidate.getX(), candidate.getY(), candidate.getStance(),
  3094.                         x, y, (TrooperStance)stance)) {
  3095.                         canShootStance = stance;
  3096.                         break;
  3097.                     }
  3098.                 }
  3099.  
  3100.                 double grenageProb = 0;
  3101.                 double shootProb = 0;
  3102.                 double maxProbGrenade = 0;
  3103.                 double maxProbShoot = 0;
  3104.                 int maxPGrenade = 0;
  3105.                 int maxPShoot = 0;
  3106.  
  3107.                 // compute probability that will hit somebody with grenade or shoot
  3108.                 for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
  3109.                     if (maxProbGrenade < trooperProbs[x][y][p].first) {
  3110.                         maxProbGrenade = trooperProbs[x][y][p].first;
  3111.                         maxPGrenade = p;
  3112.                     }
  3113.                     grenageProb += trooperProbs[x][y][p].first;
  3114.  
  3115.                     if (trooperProbs[x][y][p].second.getStance() >= canShootStance) {
  3116.                         if (maxProbShoot < trooperProbs[x][y][p].first) {
  3117.                             maxProbShoot = trooperProbs[x][y][p].first;
  3118.                             maxPShoot = p;
  3119.                         }
  3120.                         shootProb += trooperProbs[x][y][p].first;
  3121.                     }
  3122.                 }
  3123.  
  3124.                 if (shootProb > 1.) shootProb = 1.;
  3125.                 if (grenageProb > 1.) grenageProb = 1.;
  3126.  
  3127.                 double throwDist = ggame->getGrenadeThrowRange();
  3128.  
  3129.                 if (candidate.isHoldingGrenade() && ggame->getGrenadeThrowCost() <= actionPoints && grenageProb >= 0.1 &&
  3130.                     squareDist(candidate, x, y) <= (throwDist+1) * (throwDist+1)) {
  3131.  
  3132.                     const Trooper& trooper = trooperProbs[x][y][maxPGrenade].second;
  3133.                
  3134.                     bool found;
  3135.                     LastSeen& ls = getLastSeen((int)trooper.getPlayerId(), trooper.getType(), &found);
  3136.                     if (!found) continue;
  3137.  
  3138.                     // check how much damage other teammates can do
  3139.                     int teammatesCanHelp = 0;
  3140.  
  3141.                     const vector<Trooper>& troopers = gworld->getTroopers();
  3142.                     if (maxProbGrenade == 1.) {
  3143.                         for (int t = 0; t < (int)troopers.size(); t++) {
  3144.                             const Trooper& teammate = troopers[t];
  3145.                             if (!teammate.isTeammate()) continue;
  3146.                             if (teammate.getType() == candidate.getType()) continue;
  3147.                             if (turnsLater(trooper, teammate) == TRUE) {
  3148.                                 teammatesCanHelp += computeMaxDamage(teammate, trooper);
  3149.                             }
  3150.                         }
  3151.                     }
  3152.  
  3153.                     int possibleHitPoints = trooper.getHitpoints();
  3154.                     int maximalHitPoints = trooper.getMaximalHitpoints();
  3155.                     if (possibleHitPoints > maximalHitPoints) {
  3156.                         // for soldier
  3157.                         maximalHitPoints = possibleHitPoints;
  3158.                     }
  3159.                
  3160.                     // loop over enemy teammates and check if they can heal him
  3161.                     for (int et = 0; et < (int)lastSeen.size(); et++) {
  3162.                         const Trooper& hisTeammate = lastSeen[et].first;
  3163.                         if (hisTeammate.getPlayerId() != trooper.getPlayerId()) continue;
  3164.                         if (isDead(hisTeammate)) continue;
  3165.                         double numTurns = numTurnsSinceSubMove(hisTeammate, ls.second);
  3166.                        
  3167.                         if (numTurns > 0) {
  3168.                             int dist = stepDistance(hisTeammate, trooper) - 1; // should be in near point
  3169.                             int numTurnsCeil = (int)ceil(numTurns);
  3170.                             int maxActionPointsPerTurn = hisTeammate.getInitialActionPoints();
  3171.                             if (hisTeammate.getType() != COMMANDER && hisTeammate.getType() != SCOUT) maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();
  3172.  
  3173.                             int wholeActionPointsCeil = maxActionPointsPerTurn * numTurnsCeil;
  3174.  
  3175.                             wholeActionPointsCeil -= dist * ggame->getStandingMoveCost();
  3176.  
  3177.                             if (dist > 0) wholeActionPointsCeil -= (STANDING - hisTeammate.getStance()) * ggame->getStanceChangeCost();
  3178.  
  3179.                             if (wholeActionPointsCeil > 0) {
  3180.                                 // Probably it was healed
  3181.                                 if (hisTeammate.isHoldingMedikit() && wholeActionPointsCeil >= ggame->getMedikitUseCost()) {
  3182.                                     possibleHitPoints += ggame->getMedikitBonusHitpoints();
  3183.                                     wholeActionPointsCeil -= ggame->getMedikitUseCost();
  3184.                                 }
  3185.  
  3186.                                 if (hisTeammate.getType() == FIELD_MEDIC) {
  3187.                                     possibleHitPoints += wholeActionPointsCeil / ggame->getFieldMedicHealCost() * ggame->getFieldMedicHealBonusHitpoints();
  3188.                                 }
  3189.                             }
  3190.                         }
  3191.                     }
  3192.  
  3193.                     if (possibleHitPoints > maximalHitPoints) possibleHitPoints = maximalHitPoints;
  3194.        
  3195.                     // probably can hit them with grenade?
  3196.  
  3197.                     Point throwPoint(trooper);
  3198.                
  3199.                     if (squareDist(candidate, throwPoint) <= throwDist * throwDist) {
  3200.                         bool killed = false;
  3201.                         Action& action= getAction(actions, throwPoint.getX(), throwPoint.getY(), THROW_GRENADE);
  3202.                         int damage = ggame->getGrenadeDirectDamage();
  3203.                         if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
  3204.                             damage = trooper.getHitpoints();
  3205.                             action.troopersKilled++;
  3206.                             killed = true;
  3207.                         } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
  3208.                             if (trooper.getHitpoints() <= damage) {
  3209.                                 damage = trooper.getHitpoints();
  3210.                             }
  3211.                             action.troopersKilledLater++;
  3212.                             killed = true;
  3213.                         } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
  3214.                             // will kill if not healed
  3215.                             damage = trooper.getHitpoints();
  3216.                             action.troopersKilledLater++;
  3217.                             killed = true;
  3218.                         }
  3219.                         action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
  3220.                    
  3221.                         action.damage += damage * grenageProb;
  3222.                         action.actionPoints = ggame->getGrenadeThrowCost();
  3223.                         action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
  3224.                     }
  3225.  
  3226.                     Point nearPoint;
  3227.  
  3228.                     // throw to neighbour points
  3229.                     nearPoint = throwPoint + Point(1,0);
  3230.                     if (validPoint(nearPoint) &&
  3231.                         squareDist(candidate, nearPoint) <= throwDist * throwDist) {
  3232.                         bool killed = false;
  3233.                         Action& action= getAction(actions, nearPoint.getX(), nearPoint.getY(), THROW_GRENADE);
  3234.                         int damage = ggame->getGrenadeCollateralDamage();
  3235.                         if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
  3236.                             damage = trooper.getHitpoints();
  3237.                             action.troopersKilled++;
  3238.                             killed = true;
  3239.                         } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
  3240.                             if (trooper.getHitpoints() <= damage) {
  3241.                                 damage = trooper.getHitpoints();
  3242.                             }
  3243.                             action.troopersKilledLater++;
  3244.                             killed = true;
  3245.                         } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
  3246.                             // will kill if not healed
  3247.                             damage = trooper.getHitpoints();
  3248.                             action.troopersKilledLater++;
  3249.                             killed = true;
  3250.                         }
  3251.                         action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
  3252.                    
  3253.                         action.damage += damage * grenageProb;
  3254.                         action.actionPoints = ggame->getGrenadeThrowCost();
  3255.                         action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
  3256.                     }
  3257.                     nearPoint = throwPoint + Point(-1,0);
  3258.                     if (validPoint(nearPoint) &&
  3259.                         squareDist(candidate, nearPoint) <= throwDist * throwDist) {
  3260.                         bool killed = false;
  3261.                         Action& action= getAction(actions, nearPoint.getX(), nearPoint.getY(), THROW_GRENADE);
  3262.                         int damage = ggame->getGrenadeCollateralDamage();
  3263.                         if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
  3264.                             damage = trooper.getHitpoints();
  3265.                             action.troopersKilled++;
  3266.                             killed = true;
  3267.                         } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
  3268.                             if (trooper.getHitpoints() <= damage) {
  3269.                                 damage = trooper.getHitpoints();
  3270.                             }
  3271.                             action.troopersKilledLater++;
  3272.                             killed = true;
  3273.                         } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
  3274.                             // will kill if not healed
  3275.                             damage = trooper.getHitpoints();
  3276.                             action.troopersKilledLater++;
  3277.                             killed = true;
  3278.                         }
  3279.                         action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
  3280.                    
  3281.                         action.damage += damage * grenageProb;
  3282.                         action.actionPoints = ggame->getGrenadeThrowCost();
  3283.                         action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
  3284.                     }
  3285.                     nearPoint = throwPoint + Point(0,1);
  3286.                     if (validPoint(nearPoint) &&
  3287.                         squareDist(candidate, nearPoint) <= throwDist * throwDist) {
  3288.                         bool killed = false;
  3289.                         Action& action= getAction(actions, nearPoint.getX(), nearPoint.getY(), THROW_GRENADE);
  3290.                         int damage = ggame->getGrenadeCollateralDamage();
  3291.                         if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
  3292.                             damage = trooper.getHitpoints();
  3293.                             action.troopersKilled++;
  3294.                             killed = true;
  3295.                         } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
  3296.                             if (trooper.getHitpoints() <= damage) {
  3297.                                 damage = trooper.getHitpoints();
  3298.                             }
  3299.                             action.troopersKilledLater++;
  3300.                             killed = true;
  3301.                         } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
  3302.                             // will kill if not healed
  3303.                             damage = trooper.getHitpoints();
  3304.                             action.troopersKilledLater++;
  3305.                             killed = true;
  3306.                         }
  3307.                         action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
  3308.                    
  3309.                         action.damage += damage * grenageProb;
  3310.                         action.actionPoints = ggame->getGrenadeThrowCost();
  3311.                         action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
  3312.                     }
  3313.                     nearPoint = throwPoint + Point(0,-1);
  3314.                     if (validPoint(nearPoint) &&
  3315.                         squareDist(candidate, nearPoint) <= throwDist * throwDist) {
  3316.                         bool killed = false;
  3317.                         Action& action= getAction(actions, nearPoint.getX(), nearPoint.getY(), THROW_GRENADE);
  3318.                         int damage = ggame->getGrenadeCollateralDamage();
  3319.                         if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
  3320.                             damage = trooper.getHitpoints();
  3321.                             action.troopersKilled++;
  3322.                             killed = true;
  3323.                         } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
  3324.                             if (trooper.getHitpoints() <= damage) {
  3325.                                 damage = trooper.getHitpoints();
  3326.                             }
  3327.                             action.troopersKilledLater++;
  3328.                             killed = true;
  3329.                         } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
  3330.                             // will kill if not healed
  3331.                             damage = trooper.getHitpoints();
  3332.                             action.troopersKilledLater++;
  3333.                             killed = true;
  3334.                         }
  3335.                         action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
  3336.                    
  3337.                         action.damage += damage * grenageProb;
  3338.                         action.actionPoints = ggame->getGrenadeThrowCost();
  3339.                         action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
  3340.                     }
  3341.                 }
  3342.  
  3343.                 if (canShootStance < _TROOPER_STANCE_COUNT_ && shootProb >= 0.1) {
  3344.  
  3345.                     const Trooper& trooper = trooperProbs[x][y][maxPShoot].second;
  3346.                
  3347.                     bool found;
  3348.                     LastSeen& ls = getLastSeen((int)trooper.getPlayerId(), trooper.getType(), &found);
  3349.                     if (!found) continue;
  3350.  
  3351.                     int teammatesCanHelp = 0;
  3352.  
  3353.                     const vector<Trooper>& troopers = gworld->getTroopers();
  3354.                     if (maxProbShoot == 1.) {
  3355.                         for (int t = 0; t < (int)troopers.size(); t++) {
  3356.                             const Trooper& teammate = troopers[t];
  3357.                             if (!teammate.isTeammate()) continue;
  3358.                             if (teammate.getType() == candidate.getType()) continue;
  3359.                             if (turnsLater(trooper, teammate) == TRUE) {
  3360.                                 teammatesCanHelp += computeMaxDamage(teammate, trooper);
  3361.                             }
  3362.                         }
  3363.                     }
  3364.  
  3365.                     int possibleHitPoints = trooper.getHitpoints();
  3366.                     int maximalHitPoints = trooper.getMaximalHitpoints();
  3367.                     if (possibleHitPoints > maximalHitPoints) {
  3368.                         // for soldier
  3369.                         maximalHitPoints = possibleHitPoints;
  3370.                     }
  3371.                
  3372.                     for (int et = 0; et < (int)lastSeen.size(); et++) {
  3373.                         const Trooper& hisTeammate = lastSeen[et].first;
  3374.                         if (hisTeammate.getPlayerId() != trooper.getPlayerId()) continue;
  3375.                         if (isDead(hisTeammate)) continue;
  3376.                         double numTurns = numTurnsSinceSubMove(hisTeammate, ls.second);
  3377.                        
  3378.                         if (numTurns > 0) {
  3379.                             int dist = stepDistance(hisTeammate, trooper) - 1; // should be in near point
  3380.                             int numTurnsCeil = (int)ceil(numTurns);
  3381.                             int maxActionPointsPerTurn = hisTeammate.getInitialActionPoints();
  3382.                             if (hisTeammate.getType() != COMMANDER && hisTeammate.getType() != SCOUT) maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();
  3383.  
  3384.                             int wholeActionPointsCeil = maxActionPointsPerTurn * numTurnsCeil;
  3385.  
  3386.                             wholeActionPointsCeil -= dist * ggame->getStandingMoveCost();
  3387.  
  3388.                             if (dist > 0) wholeActionPointsCeil -= (STANDING - hisTeammate.getStance()) * ggame->getStanceChangeCost();
  3389.  
  3390.                             if (wholeActionPointsCeil > 0) {
  3391.                                 // Probably it was healed
  3392.                                 if (hisTeammate.isHoldingMedikit() && wholeActionPointsCeil >= ggame->getMedikitUseCost()) {
  3393.                                     possibleHitPoints += ggame->getMedikitBonusHitpoints();
  3394.                                     wholeActionPointsCeil -= ggame->getMedikitUseCost();
  3395.                                 }
  3396.  
  3397.                                 if (hisTeammate.getType() == FIELD_MEDIC) {
  3398.                                     possibleHitPoints += wholeActionPointsCeil / ggame->getFieldMedicHealCost() * ggame->getFieldMedicHealBonusHitpoints();
  3399.                                 }
  3400.                             }
  3401.                         }
  3402.                     }
  3403.  
  3404.                     if (possibleHitPoints > maximalHitPoints) possibleHitPoints = maximalHitPoints;
  3405.        
  3406.                     int numShots = actionPoints / candidate.getShootCost();
  3407.  
  3408.                     if (numShots > 0) {
  3409.                         bool killed = false;
  3410.                         Action& action = getAction(actions, trooper.getX(), trooper.getY(), SHOOT);
  3411.                         int singleDamage = candidate.getDamage(candidate.getStance());
  3412.                         int totalDamage = singleDamage * numShots;
  3413.  
  3414.                         if (maxProbShoot == 1. && possibleHitPoints <= totalDamage) {
  3415.                             numShots = (trooper.getHitpoints() + singleDamage - 1) / singleDamage;
  3416.                             totalDamage = trooper.getHitpoints();
  3417.                             action.troopersKilled++;
  3418.                             killed = true;
  3419.                         } else if (maxProbShoot == 1. && possibleHitPoints <= totalDamage + teammatesCanHelp) {
  3420.                             if (trooper.getHitpoints() <= totalDamage) {
  3421.                                 numShots = (trooper.getHitpoints() + singleDamage - 1) / singleDamage;
  3422.                                 totalDamage = trooper.getHitpoints();
  3423.                             }
  3424.                             action.troopersKilledLater++;
  3425.                             killed = true;
  3426.                         } else if (maxProbShoot == 1. && trooper.getHitpoints() <= totalDamage) {
  3427.                             // will kill if not healed
  3428.                             numShots = (trooper.getHitpoints() + singleDamage - 1) / singleDamage;
  3429.                             totalDamage = trooper.getHitpoints();
  3430.                             action.troopersKilledLater++;
  3431.                             killed = true;
  3432.                         }
  3433.                         action.actionPoints = candidate.getShootCost() * numShots;
  3434.                         action.damage = totalDamage * shootProb;
  3435.                         action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, totalDamage, maxProbShoot), currentSubMove));
  3436.                         action.priority += getActionPriority((int)(totalDamage * maxProbShoot), trooper, killed);
  3437.                     }
  3438.                 }
  3439.             }
  3440.         }
  3441.     }
  3442.     sort(actions.begin(), actions.end(), compareActions);
  3443.  
  3444.     // save best action for this position
  3445.     bestActions.push_back(std::pair<std::pair<Position, int>, Action>
  3446.         (std::pair<Position, int>(Position(candidate), actionPoints), actions[0]));
  3447.  
  3448.     return actions[0];
  3449. }
  3450.  
  3451. int findBestAction(Trooper candidate, int actionPoints, Target& target, bool finalPoint) {
  3452.     target.actionPosition = candidate;
  3453.     target.action.actionType = END_TURN;
  3454.     target.action.x = candidate.getX();
  3455.     target.action.y = candidate.getY();
  3456.  
  3457.     int score = 0;
  3458.     double scoreNextTurn = 0;
  3459.  
  3460.     // process bonuses
  3461.     const vector<Bonus>& bonuses = gworld->getBonuses();
  3462.     for (int i = 0; i < (int)bonuses.size(); i++) {
  3463.         const Bonus& bonus = bonuses[i];
  3464.  
  3465.         if (bonus.getX() == candidate.getX() && bonus.getY() == candidate.getY()) {
  3466.             switch (bonus.getType())
  3467.             {
  3468.             case model::UNKNOWN_BONUS:
  3469.                 break;
  3470.             case model::GRENADE:
  3471.                 if (!candidate.isHoldingGrenade()) {
  3472.                     if (currentMode == COMBAT) {
  3473.                         target.scoreNextTurn += 20;
  3474.                     } else {
  3475.                         target.safety += 40;
  3476.                     }
  3477.                     target.priority += 3;
  3478.                     TrooperStateDiff diff;
  3479.                     diff.plusGrenade = true;
  3480.                     candidate = newVirtualTrooper(candidate, diff);
  3481.                 }
  3482.                 break;
  3483.             case model::MEDIKIT:
  3484.                 if (!candidate.isHoldingMedikit()) {
  3485.                     if (currentMode == COMBAT) {
  3486.                         target.scoreNextTurn += 25;
  3487.                     } else {
  3488.                         target.safety += 50;
  3489.                     }
  3490.                    
  3491.                     if (candidate.getType() == FIELD_MEDIC) {
  3492.                         target.scoreNextTurn += 20;
  3493.                     }
  3494.                     target.priority += 3;
  3495.                     TrooperStateDiff diff;
  3496.                     diff.plusMedikit = true;
  3497.                     candidate = newVirtualTrooper(candidate, diff);
  3498.                 }
  3499.                 break;
  3500.             case model::FIELD_RATION:
  3501.                 if (maxTroops >= 4) {
  3502.                     if (candidate.getType() != SNIPER) {
  3503.                         bool found;
  3504.                         const LastSeen& ls = getLastSeen((int)me->getId(), SNIPER, &found);
  3505.                         if (found && !isDead(ls.first)) {
  3506.                             const Trooper& mySniper = ls.first;
  3507.                             int numFRs = 0;
  3508.                             for (int j = 0; j < (int)bonuses.size(); j++) {
  3509.                                 const Bonus& other = bonuses[j];
  3510.                                 if (other.getType() == FIELD_RATION &&
  3511.                                     stepDistance(mySniper, other) <= 6) {
  3512.                                     numFRs++;
  3513.                                 }
  3514.                             }
  3515.                             if (currentSubMove < 2 * maxTroops &&
  3516.                                 !isDead(mySniper) && numFRs < 2 &&
  3517.                                 !mySniper.isHoldingFieldRation()) {
  3518.                                 // leave fr got sniper
  3519.                                 break;
  3520.                             }
  3521.                         }
  3522.                     }
  3523.                 }
  3524.                 if (!candidate.isHoldingFieldRation()) {
  3525.                     if (currentMode == COMBAT) {
  3526.                         target.scoreNextTurn += 20;
  3527.                     } else {
  3528.                         target.safety += candidate.getType() == SNIPER ? 60 : 30;
  3529.                     }
  3530.                     target.priority += 3;
  3531.                 }    
  3532.                 break;
  3533.             default:
  3534.                 break;
  3535.             }
  3536.         }
  3537.     }
  3538.  
  3539.     double revealedEnemies = 0;
  3540.     int sinceLastSeenEnemy = lastSeenEnemy;
  3541.     if (sinceLastSeenEnemy > 5 * maxTroops) sinceLastSeenEnemy = 5 * maxTroops;
  3542.     if (sinceLastSeenEnemy < maxTroops) sinceLastSeenEnemy= maxTroops;
  3543.  
  3544.     const vector<Trooper>& troopers = gworld->getTroopers();
  3545.  
  3546.     int minX = candidate.getX() - (int)candidate.getVisionRange();
  3547.     if (minX < 0) minX = 0;
  3548.     int maxX = candidate.getX() + (int)candidate.getVisionRange();
  3549.     if (maxX > gworld->getWidth() - 1) maxX = gworld->getWidth() - 1;
  3550.     int minY = candidate.getY() - (int)candidate.getVisionRange();
  3551.     if (minY < 0) minY = 0;
  3552.     int maxY = candidate.getY() + (int)candidate.getVisionRange();
  3553.     if (maxY > gworld->getHeight() - 1) maxY = gworld->getHeight() - 1;
  3554.  
  3555.     for (int x = minX; x <= maxX; x++) {
  3556.         for (int y = minY; y <= maxY; y++) {
  3557.             double visionRange = candidate.getVisionRange();
  3558.             for (int i = currentFog[x][y]-1; i >= 0; i--) {
  3559.                 if (gworld->isVisible(visionRange,  
  3560.                     candidate.getX(), candidate.getY(), candidate.getStance(),        
  3561.                     x, y, (TrooperStance)i)) {
  3562.                     if (trooperProbs[x][y].size() > 0) {
  3563.                         for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
  3564.                             if (trooperProbs[x][y][p].second.getType() != SNIPER) {
  3565.                                 int revealBonus = 1;
  3566.                                 if (i == KNEELING) revealBonus = 2;
  3567.                                 if (i == PRONE) revealBonus = 4;
  3568.                                 revealBonus *= sinceLastSeenEnemy;
  3569.                                 if (candidate.getType() == SCOUT) revealBonus *= 2;
  3570.                                 revealedEnemies += trooperProbs[x][y][p].first * revealBonus;
  3571.                                 for (int t = 0; t < (int)troopers.size(); t++) {
  3572.                                     const Trooper& teammate = troopers[t];
  3573.                                     if (!teammate.isTeammate()) {
  3574.                                         continue;
  3575.                                     }
  3576.                                     if (teammate.getType() != candidate.getType() &&
  3577.                                         turnsLater(trooperProbs[x][y][p].second, teammate) == TRUE &&
  3578.                                         stillThere(trooperProbs[x][y][p].second) == TRUE) {
  3579.                                         int damage = computeMaxDamage(teammate, trooperProbs[x][y][p].second);
  3580.                                         if (squareDist(teammate, trooperProbs[x][y][p].second) <= 25) {
  3581.                                             revealedEnemies += trooperProbs[x][y][p].first * 20;
  3582.                                         }
  3583.                                         // I'll highlight it for him
  3584.                                         revealedEnemies += trooperProbs[x][y][p].first * damage;
  3585.                                     } else if (trooperProbs[x][y][p].first > 0.05 &&
  3586.                                         teammate.getType() != candidate.getType()) {
  3587.                                         int damage = computeMaxDamage(teammate, trooperProbs[x][y][p].second);
  3588.                                         revealedEnemies += trooperProbs[x][y][p].first * damage / 3;
  3589.                                     }
  3590.                                 }
  3591.                             }
  3592.                         }
  3593.                     }
  3594.                 } else {
  3595.                     break;
  3596.                 }
  3597.             }
  3598.  
  3599.             // the same for sniper
  3600.             if (candidate.getType() != SCOUT) {
  3601.                 visionRange -= (double)(_TROOPER_STANCE_COUNT_ - currentFogSniper[x][y]) * 0.5;
  3602.             }
  3603.  
  3604.             for (int i = currentFogSniper[x][y]-1; i >= 0; i--) {
  3605.                 if (gworld->isVisible(visionRange,  
  3606.                     candidate.getX(), candidate.getY(), candidate.getStance(),        
  3607.                     x, y, (TrooperStance)i)) {
  3608.                     if (trooperProbs[x][y].size() > 0) {
  3609.                         for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
  3610.                             if (trooperProbs[x][y][p].second.getType() == SNIPER) {
  3611.                                 int revealBonus = 1;
  3612.                                 if (i == KNEELING) revealBonus = 2;
  3613.                                 if (i == PRONE) revealBonus = 4;
  3614.                                 revealBonus *= sinceLastSeenEnemy;
  3615.                                 if (candidate.getType() == SCOUT) revealBonus *= 2;
  3616.                                 revealedEnemies += trooperProbs[x][y][p].first * revealBonus * 2;
  3617.                                 for (int t = 0; t < (int)troopers.size(); t++) {
  3618.                                     const Trooper& teammate = troopers[t];
  3619.                                     if (!teammate.isTeammate()) continue;
  3620.                                     if (teammate.getType() != candidate.getType() &&
  3621.                                         turnsLater(trooperProbs[x][y][p].second, teammate) == TRUE &&
  3622.                                         stillThere(trooperProbs[x][y][p].second) == TRUE) {
  3623.                                         int damage = computeMaxDamage(teammate, trooperProbs[x][y][p].second);
  3624.                                         // I'll highlight it for him
  3625.                                         revealedEnemies += trooperProbs[x][y][p].first * damage;
  3626.                                     } else if (trooperProbs[x][y][p].first > 0.05 &&
  3627.                                         teammate.getType() != candidate.getType()) {
  3628.                                         int damage = computeMaxDamage(teammate, trooperProbs[x][y][p].second);
  3629.                                         revealedEnemies += trooperProbs[x][y][p].first * damage / 3;
  3630.                                     }
  3631.                                 }
  3632.                             }
  3633.                         }
  3634.                     }
  3635.                     visionRange -= 0.5;
  3636.                 } else {
  3637.                     break;
  3638.                 }
  3639.             }
  3640.         }
  3641.     }
  3642.  
  3643.     revealedEnemies /= 3; // each counted 3 times. Once for each stance
  3644.     if (currentMode == TRAVEL) {
  3645.         // not so significant
  3646.         revealedEnemies /= 2;
  3647.     }
  3648.  
  3649.     if (finalPoint) {
  3650.         // do not get score if it is final point
  3651.         revealedEnemies = 0;
  3652.     }
  3653.  
  3654.     scoreNextTurn += revealedEnemies;
  3655.        
  3656.     target.score += score;
  3657.     target.scoreNextTurn += scoreNextTurn;
  3658.  
  3659.     Action bestAction = findBestAction(candidate, actionPoints);
  3660.  
  3661.     if (isAttackAction(bestAction.actionType)) {
  3662.         target.score += (int)bestAction.damage;
  3663.     } else {
  3664.         target.safety += (int)bestAction.damage;
  3665.     }
  3666.     target.hits = bestAction.hits;
  3667.     target.priority += bestAction.priority;
  3668.     target.score += bestAction.troopersKilled * ggame->getTrooperEliminationScore();
  3669.     target.scoreNextTurn += bestAction.troopersKilledLater * ggame->getTrooperEliminationScore();
  3670.     target.safety += bestAction.troopersKilled * 30 * maxTroops;
  3671.     target.safety += bestAction.troopersKilledLater * 20 * maxTroops;
  3672.     if (bestAction.actionType == THROW_GRENADE) { target.safety -= 30; }
  3673.     if (bestAction.actionType == USE_MEDIKIT) { target.safety -= 30; }
  3674.     target.action = bestAction;
  3675.  
  3676.     double scoreCoef = 1;
  3677.     if (tactics == HIDE) scoreCoef = 0.5;
  3678.     if (tactics == DEFENSIVE) scoreCoef = 0.8;
  3679.     if (tactics == NORMAL) scoreCoef = 1;
  3680.     if (tactics == AGRESSIVE) scoreCoef = 2;
  3681.     if (tactics == RUSH) scoreCoef = 4;
  3682.  
  3683.     target.score = (int)(target.score * scoreCoef);
  3684.  
  3685.     scoreCoef /= 2.; // for next turns take less score
  3686.     target.scoreNextTurn = target.scoreNextTurn * scoreCoef;
  3687.  
  3688.     if (bestAction.actionPoints > actionPoints) {
  3689.         SHOULD_NOT_HAPPEN;
  3690.     }
  3691.     // return action points spent for the best action
  3692.     return bestAction.actionPoints;
  3693. }
  3694.  
  3695. // cache for virtual step maps
  3696. std::vector<std::pair<Point, StepMap> > virtualStepMaps;
  3697.  
  3698. StepMap& getVirtualStepMap(Point p) {
  3699.     for (int i = 0; i < (int)virtualStepMaps.size(); i++) {
  3700.         if (virtualStepMaps[i].first == p) return virtualStepMaps[i].second;
  3701.     }
  3702.  
  3703.     // push new stepMap
  3704.     virtualStepMaps.push_back(std::pair<Point, StepMap>(p, StepMap()));
  3705.     StepMap& newSm = (*virtualStepMaps.rbegin()).second;
  3706.     initStepMap(gworld->getCells(), newSm, 1000, true);
  3707.  
  3708.     newSm[p.x][p.y] = -1;
  3709.  
  3710.     computeStepMap(globalTarget, newSm);
  3711.     return newSm;
  3712. }
  3713.  
  3714. // compute safety and next turn score for the final hide position
  3715. void computeSafety(const Trooper& candidate, Target& target) {
  3716.     target.hidePosition = candidate;
  3717.  
  3718.     target.priority = candidate.getType() == leader ?
  3719.         -getStepsTroopers(candidate.getX(), candidate.getY(), globalTargetStepMapTroopersNoSelf) : // take others into account
  3720.         -(*globalTargetStepMap)[candidate.getX()][candidate.getY()];
  3721.     //if (currentMode != TRAVEL) target.priority = 0;
  3722.  
  3723.     int safety = 0;
  3724.     int priority = 0;
  3725.  
  3726.     int minDiff = 1000;
  3727.     int maxDiff = 0;
  3728.     int minStepDiff = 1000;
  3729.     int maxStepDiff = 0;
  3730.  
  3731.     // compute distances to other teammates
  3732.     const vector<Trooper>& troopers = gworld->getTroopers();
  3733.     for (size_t i = 0; i < troopers.size(); ++i) {
  3734.         Trooper trooper = troopers.at(i);
  3735.         if (trooper.isTeammate() && trooper.getType() != candidate.getType()) {
  3736.             int diff = manhattanDistance(candidate, trooper);
  3737.             int stepDiff = stepDistance(candidate, trooper);
  3738.  
  3739.             if (diff < minDiff) minDiff = diff;
  3740.             if (diff > maxDiff) maxDiff = diff;
  3741.             if (stepDiff < minStepDiff) minStepDiff = stepDiff;
  3742.             if (stepDiff > maxStepDiff) maxStepDiff = stepDiff;
  3743.  
  3744.             // if hit, it is safe to be near medic
  3745.             if (currentMode != COMBAT &&
  3746.                 candidate.getHitpoints() < candidate.getMaximalHitpoints() &&
  3747.                 trooper.getType() == FIELD_MEDIC && diff == 1) {
  3748.                 safety += candidate.getMaximalHitpoints() - candidate.getHitpoints();
  3749.             }
  3750.  
  3751.             // commander should be near others to activate his aura
  3752.             if (candidate.getType() == COMMANDER && squareDist(candidate, trooper) >
  3753.                 ggame->getCommanderAuraRange() * ggame->getCommanderAuraRange()) {
  3754.                 target.safety -= 15;
  3755.             }
  3756.  
  3757.             // scout should go in front of others
  3758.             if (candidate.getType() == SCOUT && mapType != CHEESER) {
  3759.                 int myDist = (*globalTargetStepMap)[candidate.getX()][candidate.getY()];
  3760.                 int theirDist = (*globalTargetStepMap)[trooper.getX()][trooper.getY()];
  3761.                 if (myDist > theirDist) {
  3762.                     target.safety -= (myDist - theirDist) * 5;
  3763.                 }
  3764.             }
  3765.  
  3766.             // check that candidate breaks the other's best path to target
  3767.             if (candidate.getType() != leader && stepDistance(candidate, trooper) <= 5) {
  3768.                 StepMap& virtStepMap = getVirtualStepMap(candidate);
  3769.                
  3770.                 // compute current distance to target
  3771.                 int dist = getStepsTroopers(trooper.getX(), trooper.getY(), globalTargetStepMapTroopersNoSelf);
  3772.                 // and distance when candidate is placed to this point
  3773.                 int virtDist = getStepsTroopers(trooper.getX(), trooper.getY(), virtStepMap);
  3774.  
  3775.                 if (virtDist > dist) {
  3776.                     int diff = virtDist- dist;
  3777.  
  3778.                     if (diff > 6) diff = 6;
  3779.                     target.scoreNextTurn -= diff * 5;
  3780.                 }
  3781.             }
  3782.         }
  3783.     }
  3784.  
  3785.     if (maxDiff > 0) {
  3786.         // be more compact
  3787.         if (candidate.getType() == SCOUT && mapType == MAP4 && gworld->getMoveIndex() <= 2) {
  3788.             // skip this penalty, run to observe others
  3789.         } else {
  3790.             safety += compactnessSafetyPenalty(minDiff, candidate.getType() == leader);
  3791.             safety += compactnessSafetyPenalty(maxDiff, candidate.getType() == leader);
  3792.  
  3793.             int stepCoef = 1;
  3794.             // step distance is more important for maze
  3795.             if (mapType == CHEESER) stepCoef = 2;
  3796.  
  3797.             safety += compactnessSafetyPenalty(minStepDiff, candidate.getType() == leader) * stepCoef;
  3798.             safety += compactnessSafetyPenalty(maxStepDiff, candidate.getType() == leader) * stepCoef;
  3799.  
  3800.             safety /= 2;
  3801.  
  3802.             // while target is not defined, be even more compact
  3803.             if (randomTarget) safety *= 2;
  3804.  
  3805.             if (currentMode == TRAVEL && minDiff >= 4) {
  3806.                 if (candidate.getType() == leader) {
  3807.                     target.priority -= minDiff / 4;
  3808.                 } else {
  3809.                     target.priority -= minDiff / 2;
  3810.                 }
  3811.             }
  3812.         }
  3813.     }
  3814.  
  3815.     // medic should always be near others
  3816.     if (candidate.getType() == FIELD_MEDIC) safety = safety * 3 / 2;
  3817.  
  3818.     double visibilityProb = getTrooperVisibility(candidate);
  3819.     bool visible = visibleForEnemies(candidate);
  3820.  
  3821.     if (currentMode != TRAVEL && !visible) {
  3822.         // probably
  3823.         visibilityProb *= 0.7;
  3824.     }
  3825.  
  3826.     if (currentMode != TRAVEL) {
  3827.         safety = (int) (safety * (1. + visibilityProb) / 2);
  3828.     }
  3829.  
  3830.     // process possible enemies
  3831.     //std::cout << "For candidate " << Position(candidate) << std::endl;
  3832.     double damageToMe = computeDamageToTrooper(candidate);
  3833.  
  3834.     if (visibilityProb > 0.1) {
  3835.         int neighbours = 0;
  3836.         for (size_t i = 0; i < troopers.size(); ++i) {
  3837.             Trooper trooper = troopers.at(i);
  3838.             if (trooper.isTeammate() && trooper.getType() != candidate.getType()) {
  3839.                 int diff = manhattanDistance(candidate, trooper);
  3840.                 if (diff == 1) neighbours++;
  3841.             }
  3842.         }
  3843.  
  3844.         if (neighbours > 1) {
  3845.             // bad position, can be heated with grenade together with other teammates
  3846.             damageToMe *= 1.4;
  3847.         }
  3848.     }
  3849.  
  3850.     if (mapType == CHEESER && gworld->getMoveIndex() > 20 && tactics >= AGRESSIVE && currentMode == TRAVEL) {
  3851.         // more berserking
  3852.         damageToMe /= 2;
  3853.     }
  3854.    
  3855.     damageToMe *= visibilityProb;
  3856.  
  3857.     if (candidate.getType() == FIELD_MEDIC) damageToMe *= 2;
  3858.     safety -= (int)damageToMe;
  3859.  
  3860.     target.visibileProb = visibilityProb;
  3861.     target.safety += safety;
  3862.     target.priority += priority;
  3863.  
  3864.     if (candidate.getType() == FIELD_MEDIC) {
  3865.         // be near others if they already need heal or can be hited next turn
  3866.         for (size_t i = 0; i < troopers.size(); ++i) {
  3867.             Trooper trooper = troopers.at(i);
  3868.             if (trooper.isTeammate() && trooper.getType() != candidate.getType()) {
  3869.                 int diff = stepDistance(candidate, trooper);
  3870.            
  3871.                 if (diff < 4) {
  3872.                     int need = 0;
  3873.                     if (trooper.getHitpoints() < trooper.getMaximalHitpoints()) need++;
  3874.                     if (getTrooperVisibility(trooper) > 0.5) need++;
  3875.                     if (currentMode != TRAVEL && need > 0) {
  3876.                         if (diff == 1) {
  3877.                             target.safety += need * 7;
  3878.                             target.scoreNextTurn += need * 5;
  3879.                         }
  3880.                         if (diff == 2) {
  3881.                             target.safety += need + 10;
  3882.                             target.scoreNextTurn += need * 3;
  3883.                         }
  3884.                         if (diff == 3) {
  3885.                             target.safety += need * 5;
  3886.                             target.scoreNextTurn += need * 3;
  3887.                         }
  3888.                     }
  3889.                 }
  3890.             }
  3891.         }
  3892.     } else {
  3893.         // for others try to take better position for next turn
  3894.         double maxDamageNextTurn = computeDamageByTrooper(candidate);
  3895.  
  3896.         maxDamageNextTurn /= maxTroops;
  3897.  
  3898.         if (tactics < AGRESSIVE) maxDamageNextTurn /= 2;
  3899.  
  3900.         target.scoreNextTurn += maxDamageNextTurn;
  3901.     }
  3902.  
  3903.     // because prone and kneeling prevents future moving
  3904.     if (currentMode == TRAVEL) {
  3905.         if (candidate.getType() != SNIPER && candidate.getType() != FIELD_MEDIC) {
  3906.             target.priority -= (STANDING - candidate.getStance());
  3907.         }
  3908.     } else {
  3909.         int stancePenalty = 2;
  3910.         if (tactics == AGRESSIVE) stancePenalty = 5;
  3911.         if (tactics == RUSH) stancePenalty = 10;
  3912.        
  3913.         target.scoreNextTurn -= (STANDING - candidate.getStance()) * stancePenalty;
  3914.  
  3915.         // bad to be in the same position, probably somebody saw me there
  3916.         if (Point(candidate) == startPoint) target.safety -= 10;
  3917.     }
  3918.  
  3919.     bool found;
  3920.     const LastSeen& ls = getLastSeen((int)me->getId(), SCOUT, &found);
  3921.     if (found && !isDead(ls.first) && mapType != CHEESER) {
  3922.         const Trooper& myScout = ls.first;
  3923.         int scoutDist = (*globalTargetStepMap)[myScout.getX()][myScout.getY()];
  3924.         int myDist = (*globalTargetStepMap)[candidate.getX()][candidate.getY()];
  3925.  
  3926.         if (scoutDist > myDist) {
  3927.             // don't move in front of scout if he is alive, not safe
  3928.             target.safety -= (scoutDist - myDist) * 5;
  3929.         }
  3930.     }
  3931. }
  3932.  
  3933. void makeDecision(const Trooper& self, std::vector<Target>& bestTargets) {
  3934.     bestActions.clear();
  3935.  
  3936.     int selfActionPoints = self.getActionPoints();
  3937.  
  3938.     if (currentMode == COMBAT) {
  3939.         // in combat can eat ration
  3940.         if (self.isHoldingFieldRation() && selfActionPoints >= ggame->getFieldRationEatCost()) {
  3941.             selfActionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
  3942.         }
  3943.     }
  3944.  
  3945.     int selfMaxSteps = selfActionPoints / ggame->getStandingMoveCost();
  3946.  
  3947.     StepMap selfStepMap;
  3948.     StepMap apStepMap;
  3949.    
  3950.     initStepMap(gworld->getCells(), selfStepMap, selfMaxSteps + 1, true);
  3951.     computeStepMap(self, selfStepMap);
  3952.  
  3953.     bestTargets.clear();
  3954.  
  3955.     // push at least one default target - in the starting position
  3956.     Target defaultTarget(self.getHitpoints());
  3957.     findBestAction(self, self.getActionPoints(), defaultTarget, false);
  3958.     computeSafety(self, defaultTarget);
  3959.     bestTargets.push_back(defaultTarget);
  3960.  
  3961.     // loop over action positions
  3962.     for (int x = 0; x < gworld->getWidth(); x++) {
  3963.         for (int y = 0; y < gworld->getHeight(); y++) {
  3964.             initStepMap(gworld->getCells(), apStepMap, selfMaxSteps + 1, true);
  3965.             computeStepMap(Point(x,y), apStepMap);
  3966.  
  3967.             if (selfStepMap[x][y] >= 0 && selfStepMap[x][y] <= selfMaxSteps) {
  3968.                 for (int s = 0; s < _TROOPER_STANCE_COUNT_; s++) {
  3969.                     // let it be an action position
  3970.                     int leftSteps = selfMaxSteps - selfStepMap[x][y];
  3971.  
  3972.                     TrooperStance apStance = (TrooperStance)((self.getStance() + s) % _TROOPER_STANCE_COUNT_);
  3973.                     Position apPosition(Point(x,y), apStance);
  3974.                     int apMoveCost = findFastestMove(selfStepMap, self.getStance(), apPosition);
  3975.  
  3976.                     TrooperStateDiff apDiff(x-self.getX(), y-self.getY(), apStance-self.getStance());
  3977.                     Trooper apCandidate = newVirtualTrooper(self, apDiff);
  3978.  
  3979.                     if (apMoveCost > selfActionPoints) continue;
  3980.  
  3981.                     int maxPointsForAction = selfActionPoints - apMoveCost;
  3982.  
  3983.                     {
  3984.                         // check if I pick up ration there. action points will increase
  3985.                         const vector<Bonus>& bonuses = gworld->getBonuses();
  3986.                         for (int i = 0; i < (int)bonuses.size(); i++) {
  3987.                             const Bonus& bonus = bonuses[i];
  3988.  
  3989.                             if (bonus.getX() == x && bonus.getY() == y &&
  3990.                                 bonus.getType() == FIELD_RATION) {
  3991.                                 if (currentMode == COMBAT) {
  3992.                                     if (!self.isHoldingFieldRation() && maxPointsForAction >= ggame->getFieldRationEatCost()) {
  3993.                                         maxPointsForAction += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
  3994.                                         apMoveCost -= ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
  3995.                                         if (apMoveCost < 0) apMoveCost = 0;
  3996.                                     }
  3997.                                 }
  3998.                             }
  3999.                         }
  4000.                     }
  4001.  
  4002.                     // hard check, find best action even without hide back
  4003.                     Target testTarget(self.getHitpoints());
  4004.                     findBestAction(apCandidate, maxPointsForAction, testTarget, false);
  4005.                     if (testTarget.score == 0 && testTarget.scoreNextTurn < 1 && testTarget.priority == 0 && testTarget.safety == 0) {
  4006.                         // bad target, don't even try it
  4007.                         continue;
  4008.                     }
  4009.  
  4010.                     // loop over hide positions
  4011.                     for (int xl = 0; xl < gworld->getWidth(); xl++) {
  4012.                         for (int yl = 0; yl < gworld->getHeight(); yl++) {
  4013.                             if (apStepMap[xl][yl] >= 0 && apStepMap[xl][yl] <= leftSteps) {
  4014.                                 for (int sl = 0; sl < _TROOPER_STANCE_COUNT_; sl++) {
  4015.                                     TrooperStance hideStance = (TrooperStance)((self.getStance() + sl) % _TROOPER_STANCE_COUNT_);
  4016.                                     Position hidePosition(Point(xl,yl), hideStance);
  4017.                                     int hideMoveCost = findFastestMove(apStepMap, apStance, hidePosition);
  4018.  
  4019.                                     if (apMoveCost + hideMoveCost > selfActionPoints) continue;
  4020.  
  4021.                                     TrooperStateDiff apDiff(xl-self.getX(), yl-self.getY(), hideStance-self.getStance());
  4022.                                     Trooper hideCandidate = newVirtualTrooper(self, apDiff);
  4023.  
  4024.                                     // left points for action
  4025.                                     int pointsForAction = selfActionPoints - (apMoveCost + hideMoveCost);
  4026.  
  4027.                                     Target target(self.getHitpoints());
  4028.                                     int usedActionPoint = findBestAction(apCandidate, pointsForAction, target, hideMoveCost == 0);
  4029.                                     if (apMoveCost + hideMoveCost + usedActionPoint > self.getActionPoints()) {
  4030.                                         // need to eat ration to do so lot of job
  4031.                                         target.eatRation = true;
  4032.                                         target.safety -= 20;
  4033.                                     }
  4034.  
  4035.                                     computeSafety(hideCandidate, target);
  4036.  
  4037.                                     bestTargets.push_back(target);
  4038.                                 }
  4039.                             }
  4040.                         }
  4041.                     }
  4042.                 }
  4043.             }
  4044.         }
  4045.     }
  4046.  
  4047.     sort(bestTargets.begin(), bestTargets.end(), complexComparison);
  4048. }
  4049.  
  4050. Point curPoint;
  4051. Point nextPoint;
  4052.  
  4053. void initializeOnce() {
  4054.     const vector<Player>& players = gworld->getPlayers();
  4055.     const vector<Trooper>& troopers = gworld->getTroopers();
  4056.  
  4057.     // very first turn. Initialization
  4058.  
  4059.     {
  4060.         // determine the map
  4061.         const vector<vector<CellType> >& cells = gworld->getCells();
  4062.  
  4063.         if (cells[1][5] == HIGH_COVER && cells[1][6] == HIGH_COVER && cells[2][5] == HIGH_COVER) mapType = DEFAULT;
  4064.         if (cells[14][9] == HIGH_COVER) mapType = MAP3;
  4065.         if (cells[2][2] == HIGH_COVER) mapType = CHEESER;
  4066.         if (cells[6][2] == HIGH_COVER && cells[6][3] == MEDIUM_COVER && cells[6][4] == HIGH_COVER) {
  4067.             mapType = MAP6;
  4068.         }
  4069.         if (cells[0][3] == HIGH_COVER && cells[0][4] == HIGH_COVER && cells[5][0] == FREE) {
  4070.             mapType = MAP5;
  4071.         }
  4072.         if (cells[0][8] == HIGH_COVER && cells[0][9] == HIGH_COVER && cells[13][0] == HIGH_COVER) {
  4073.             mapType = MAP4;
  4074.         }
  4075.         if (cells[0][4] == FREE && cells[0][5] == HIGH_COVER && cells[0][6] == FREE) {
  4076.             mapType = FEFER;
  4077.         }
  4078.     }
  4079.  
  4080.     std::cout << "map type: " << mapType << std::endl;
  4081.  
  4082.     // initialize seed using current gwolrd to make it reproducible
  4083.     unsigned int seed = 0;
  4084.     const vector<Bonus>& bonuses = gworld->getBonuses();
  4085.     int shift = 0;
  4086.     for (int i = 0; i < (int)bonuses.size(); i++) {
  4087.         seed |= bonuses[i].getX() << shift;
  4088.         shift += 4;
  4089.         seed |= bonuses[i].getY() << shift;
  4090.         shift += 4;
  4091.         if (shift == 32) break;
  4092.     }
  4093.  
  4094.     std::cout << "init with seed " << seed << std::endl;
  4095.     randomer.init_genrand(seed);
  4096.  
  4097.     playerInfo.resize(1); // ids starts with 1, so leave unused info with 0 id
  4098.  
  4099.     for (int i = 0; i < (int)players.size(); i++) {
  4100.         playerInfo.push_back(PlayerInfo(i+1));
  4101.     }
  4102.  
  4103.     // actually it doesn't matter first time what player to attack, they are all
  4104.     // the same
  4105.     attackPlayerId = (int)((me->getId()-1) ^ 1) + 1;
  4106.  
  4107.     // at first turn all sould be alive, just count them
  4108.     for (int i = 0; i < (int)troopers.size(); i++) {
  4109.         if (troopers[i].isTeammate()) {
  4110.             maxTroops++;
  4111.         }
  4112.     }
  4113.  
  4114.     if (maxTroops == 5) {
  4115.         leader = SCOUT;
  4116.     } else {
  4117.         leader = SOLDIER;
  4118.     }
  4119.  
  4120.     troopOrderRev.resize(maxTroops);
  4121.  
  4122.     trooperProbs.resize(gworld->getWidth());
  4123.     for (int x = 0; x < (int)gworld->getWidth(); x++) {
  4124.         trooperProbs[x].resize(gworld->getHeight());
  4125.     }
  4126.  
  4127.     // fill in last fogs
  4128.     initCurrentFog();
  4129.     for (int i = 0; i < maxTroops; i++) {
  4130.         lastFogs[i].push_front(currentFog);
  4131.         lastFogsSniper[i].push_front(currentFogSniper);
  4132.     }
  4133.  
  4134.     allInFog.resize(gworld->getWidth());
  4135.     for (int x = 0; x < gworld->getWidth(); x++) {
  4136.         allInFog[x].resize(gworld->getHeight());
  4137.         for (int y = 0; y < gworld->getHeight(); y++) {
  4138.             allInFog[x][y] = _TROOPER_STANCE_COUNT_;
  4139.         }
  4140.     }
  4141.  
  4142.     // init all step maps
  4143.     StepMap initial;
  4144.     initStepMap(gworld->getCells(), initial);
  4145.            
  4146.     allStepMaps.resize(gworld->getWidth());
  4147.     for (int x = 0; x < gworld->getWidth(); x++) {
  4148.         allStepMaps[x].resize(gworld->getHeight(), initial);
  4149.         for (int y = 0; y < gworld->getHeight(); y++) {
  4150.             computeStepMap(Point(x,y), allStepMaps[x][y]);
  4151.         }
  4152.     }
  4153.  
  4154.     curPoint = Point(*gself);
  4155.     nextPoint = Point(*gself);
  4156. }
  4157.  
  4158. void initializeEachSubMove() {
  4159.     virtualStepMaps.clear();
  4160.     startPoint = Point(*gself);
  4161.     initCurrentFog();
  4162.  
  4163.     {
  4164.         lastFogs[curTroopIndex].push_front(currentFog);
  4165.         lastFogsSniper[curTroopIndex].push_front(currentFogSniper);
  4166.  
  4167.         // throw out outdated fogs, care about memory
  4168.         if (lastFogs[curTroopIndex].size() > 3) lastFogs[curTroopIndex].pop_back();
  4169.         if (lastFogsSniper[curTroopIndex].size() > 3) lastFogsSniper[curTroopIndex].pop_back();
  4170.     }
  4171.  
  4172.     if (currentSubMove - prevSubMove > 1) {
  4173.         // somebody is dead between us, update his fog
  4174.         for (int i = 1; i < currentSubMove - prevSubMove; i++) {
  4175.             int thatTroopIndex = curTroopIndex - i;
  4176.             if (thatTroopIndex < 0) thatTroopIndex += maxTroops;
  4177.             lastFogs[thatTroopIndex].push_front(allInFog);
  4178.             lastFogsSniper[thatTroopIndex].push_front(allInFog);
  4179.             if (lastFogs[thatTroopIndex].size() > 3) lastFogs[thatTroopIndex].pop_back();
  4180.             if (lastFogsSniper[thatTroopIndex].size() > 3) lastFogsSniper[thatTroopIndex].pop_back();
  4181.         }
  4182.     }
  4183. }
  4184.  
  4185. void updateTactics() {
  4186.     // set tactics
  4187.     int maxScore = 0;
  4188.     const vector<Player>& players = gworld->getPlayers();
  4189.     for (int i = 0; i < (int)players.size(); i++) {
  4190.         if (players[i].getId() != gself->getPlayerId()) {
  4191.             if (players[i].getScore() > maxScore) {
  4192.                 maxScore = players[i].getScore();
  4193.             }
  4194.             if (players[i].getId() == attackPlayerId &&
  4195.                 players[i].isStrategyCrashed()) {
  4196.                 tactics = RUSH;
  4197.                 return;
  4198.             }
  4199.         }
  4200.     }        
  4201.  
  4202.     {
  4203.         int rushNum = maxTroops == 5 ? 2 : 1;
  4204.         int agressiveNum = 0;
  4205.        
  4206.         if (me