gistfile1.cpp

#include "MyStrategy.h"
#include "mt19937ar.h"

#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <time.h>
#include <map>

using namespace model;
using namespace std;

MyStrategy::MyStrategy() {
}

std::ostream& operator<<(std::ostream& os, TrooperType troopType) {
    switch (troopType) {
    case COMMANDER:
        os << "commander";
        break;
    case FIELD_MEDIC:
        os << "medic";
        break;
    case SOLDIER:
        os << "soldier";
        break;
    case SNIPER:
        os << "sniper";
        break;
    case SCOUT:
        os << "scout";
        break;
    case UNKNOWN_TROOPER:
    default:
        os << "unknown";
        break;
    }
    return os;
}

void shouldNotHappen(int line) {
    std::cout << line << ": should not happen" << std::endl;
}

#define SHOULD_NOT_HAPPEN shouldNotHappen(__LINE__)

MT19937AR randomer;

const World* gworld;
const Game* ggame;
const Trooper* gself;
const Player* me;

#define MAX_TROOPERS 5
#define MAX_PLAYERS 4

enum TriBool {
    FALSE = 0,
    MOST_LIKELY_FALSE = 1,
    PROBABLY = 2,
    MOST_LIKELY_TRUE = 3,
    TRUE = 4
};

TriBool triNot(TriBool p) {
    return (TriBool)(TRUE - p);
}

bool sure(TriBool triBool) {
    if (triBool == TRUE || triBool == FALSE) return true;
    return false;
}

std::ostream& operator<<(std::ostream& os, const TriBool& triBool) {
    switch (triBool)
    {
    case FALSE:
        os << "false";
        break;
    case MOST_LIKELY_FALSE:
        os << "most likely false";
        break;
    case PROBABLY:
        os << "probably";
        break;
    case MOST_LIKELY_TRUE:
        os << "most likely true";
        break;
    case TRUE:
        os << "true";
        break;
    default:
        break;
    }
    return os;
}


ostream& operator<<(ostream& os, const model::ActionType& action) {
    switch (action)
    {
    case model::END_TURN:
        os << "end turn";
        break;
    case model::MOVE:
        os << "move";
        break;
    case model::SHOOT:
        os << "shoot";
        break;
    case model::RAISE_STANCE:
        os << "raise stance";
        break;
    case model::LOWER_STANCE:
        os << "lower stance";
        break;
    case model::THROW_GRENADE:
        os << "throw grenade";
        break;
    case model::USE_MEDIKIT:
        os << "use medikit";
        break;
    case model::EAT_FIELD_RATION:
        os << "eat field ration";
        break;
    case model::HEAL:
        os << "heal";
        break;
    case model::REQUEST_ENEMY_DISPOSITION:
        os << "request enemy disposition";
        break;
    case model::UNKNOWN_ACTION:
    default:
        os << "unknown";
        break;
    }
    return os;
}

ostream& operator<<(ostream& os, const model::TrooperStance& stance) {
    switch (stance) {
    case model::STANDING:
        os << "standing";
        break;
    case model::KNEELING:
        os << "kneeling";
        break;
    case model::PRONE:
        os << "prone";
        break;
    default:
        break;
    }
    return os;
}


typedef vector<vector<CellType> > CellMap;

// matrix of all step distances from some point
typedef vector<vector<int> > StepMap;

// point on the map
struct Point {
    Point() {
        x = -1;
        y = -1;
    }
    Point(const Unit& unit) {
        x = unit.getX();
        y = unit.getY();
    }
    Point(int _x, int _y) {
        x = _x;
        y = _y;
    }

    int getX() const {return x;}
    int getY() const {return y;}

    Point operator+=(const Point& diff) {
        x += diff.x;
        y += diff.y;
        return *this;
    }

    Point operator+(const Point& diff) {
        Point newPoint(*this);
        newPoint += diff;
        return newPoint;
    }

    bool operator==(const Point& other) const {
        return other.x == x && other.y == y;
    }

    bool operator!=(const Point& other) const {
        return !operator==(other);
    }

    int x;
    int y;
};

// position - point + stance
struct Position {
    Point point;
    TrooperStance stance;

    Position(Point point = Point(), TrooperStance stance = STANDING) :
        point(point),
        stance(stance)
    {}
    Position(int x, int y, TrooperStance stance) :
        point(x,y),
        stance(stance)
    {}

    Position(const Trooper& trooper) :
        point(trooper),
        stance(trooper.getStance())
    {}

    int getX() const { return point.getX(); }
    int getY() const { return point.getY(); }
    TrooperStance getStance() const { return stance; }

    bool operator==(const Position& other) const {
        return point == other.point && stance == other.stance;
    }
    bool operator!=(const Position& other) const {
        return !(operator==(other));
    }

    operator Point() const { return point; }
};

// check if point really in the map
bool validPoint(const Point& point) {
    return 
        point.x >= 0 &&
        point.y >= 0 &&
        point.x < gworld->getWidth() &&
        point.y < gworld->getHeight();
}

int getMoveCost(TrooperStance stance) {
    if (stance == STANDING) return ggame->getStandingMoveCost();
    if (stance == KNEELING) return ggame->getKneelingMoveCost();
    if (stance == PRONE) return ggame->getProneMoveCost();
    return 0;
}

struct TrooperStateDiff {
    int x;
    int y;
    int stance;
    int actionPoints;
    bool eatFieldRation;
    int playerId;
    int hitPoints;
    bool plusGrenade;
    bool plusMedikit;
    bool plusRation;

    TrooperStateDiff() :
        x(0),
        y(0),
        stance(0),
        actionPoints(0),
        eatFieldRation(0),
        playerId(0),
        hitPoints(0),
        plusGrenade(false),
        plusMedikit(false),
        plusRation(false)
    {}

    TrooperStateDiff(int x, int y, int stance = 0, int actionPoints = 0, bool eatFieldRation = false, int playerId = 0, int hitPoints = 0) :
        x(x),
        y(y),
        stance(stance),
        actionPoints(actionPoints),
        eatFieldRation(eatFieldRation),
        playerId(playerId),
        hitPoints(hitPoints),
        plusGrenade(false),
        plusMedikit(false),
        plusRation(false)
    {}
};

// creates new virtual trooper
Trooper newVirtualTrooper(const Trooper& other, TrooperStateDiff diff = TrooperStateDiff()) { 
    double shootingRange = other.getShootingRange();
    if (other.getType() == SNIPER) {
        shootingRange -= diff.stance;
    }
    return Trooper(other.getId(), other.getX() + diff.x, other.getY() + diff.y, other.getPlayerId() + diff.playerId,
        other.getTeammateIndex(), other.getPlayerId() + diff.playerId == me->getId() ? true : false, other.getType(), (TrooperStance)(other.getStance() + diff.stance),
        other.getHitpoints() + diff.hitPoints, other.getMaximalHitpoints(), other.getActionPoints() + diff.actionPoints, other.getInitialActionPoints(),
        other.getVisionRange(), shootingRange, other.getShootCost(),
        other.getStandingDamage(), other.getKneelingDamage(), other.getProneDamage(), other.getDamage(),
        other.isHoldingGrenade() || diff.plusGrenade, 
        other.isHoldingMedikit() || diff.plusMedikit, 
        other.isHoldingFieldRation() && !diff.eatFieldRation || diff.plusRation);
}

bool operator==(const Trooper& the, const Trooper& other) {
    return 
        the.getId() == other.getId() &&
        the.getX() == other.getX() &&
        the.getY() == other.getY() &&
        the.getStance() == other.getStance() &&
        the.getHitpoints() == other.getHitpoints() &&
        the.getActionPoints() == other.getActionPoints() &&
        the.isHoldingGrenade() == other.isHoldingGrenade() &&
        the.isHoldingMedikit() == other.isHoldingMedikit() &&
        the.isHoldingFieldRation() == other.isHoldingFieldRation();
}

struct SubMove {
    int subMove;
    int subsubMove;
    SubMove() {
        subMove = -1;
        subsubMove = 0;
    }
    SubMove(int subMove, int subsubMove = 0) :
        subMove(subMove),
        subsubMove(subsubMove)
    {}
    operator int() const { return subMove; }
};

enum Mode {
    TRAVEL = 0,
    COMBAT = 1,
    AFTER_COMBAT = 2
};

enum Tactics {
    HIDE = 0,
    DEFENSIVE = 1,
    NORMAL = 2,
    AGRESSIVE = 3,
    RUSH = 4
};

std::ostream& operator<<(std::ostream& os, const Tactics& tactics) {
    switch (tactics)
    {
    case HIDE:
        os << "hide";
        break;
    case DEFENSIVE:
        os << "defensive";
        break;
    case NORMAL:
        os << "normal";
        break;
    case AGRESSIVE:
        os << "agressive";
        break;
    case RUSH:
        os << "rush";
        break;
    default:
        break;
    }
    return os;
}

std::ostream& operator<<(std::ostream& os, const Mode& mode) {
    switch (mode)
    {
    case TRAVEL:
        os << "travel";
        break;
    case COMBAT:
        os << "combat";
        break;
    case AFTER_COMBAT:
        os << "after combat";
        break;
    default:
        break;
    }
    return os;
}

typedef struct Hit {
    int damage;
    Trooper trooper;
    double prob;
    Hit(const Trooper& trooper, int damage, double prob = 1.) :
        damage(damage),
        trooper(trooper),
        prob(prob)
    {}
} Hit;

// each trooper action can be described with this structure
struct Action {
    ActionType actionType;
    int x;
    int y;
    double damage;
    // action points used for the action
    int actionPoints;
    int troopersKilled;
    int troopersKilledLater;
    int priority;
    vector<std::pair<Hit,SubMove> > hits;
    
    Action() :
        actionType(END_TURN),
        x(-1),
        y(-1),
        damage(0),
        actionPoints(0),
        troopersKilled(0),
        troopersKilledLater(0),
        priority(0),
        hits()
    {}
};

// whole info about each player
class PlayerInfo {
    long long id;
    // whether it turns after me
    TriBool afterMe;
    bool dead[MAX_TROOPERS];
public:
    PlayerInfo(long long id = 0) :
        id(id),
        afterMe(PROBABLY),
        lastScore(0),
        lastScoreDiff(0),
        approximatePosition(),
        averageSpeed(5)
    {
        for (int i = 0; i < MAX_TROOPERS; i++) {
            dead[i] = false;
        }
    }

    Point approximatePosition;
    double averageSpeed;
    long long getId() { return id; };
    int lastScore;
    int lastScoreDiff;

    void setDead(TrooperType type) {
        if (!dead[type]) {
            std::cout << "Player " << id << " has lost his trooper: " << type << std::endl;
        }
        dead[type] = true;
    }

    void setAlive(TrooperType type) {
        if (dead[type]) {
            std::cout << "Player " << id << " trooper revived: " << type << std::endl;
        }
        dead[type] = false;
    }

    bool isDead(TrooperType type) const {
        return dead[type];
    }

    void setAfterMe(TriBool newAfterMe) {
        if (sure(afterMe)) {
            if (sure(newAfterMe) && newAfterMe != afterMe) {
                SHOULD_NOT_HAPPEN;
            }
        } else if (sure(newAfterMe) || afterMe == PROBABLY) {
            std::cout << "Player " << id << " turns after me: " << newAfterMe << std::endl; 
            afterMe = newAfterMe;
        } else {
            afterMe = (TriBool)((afterMe + newAfterMe) /2);
        }
    }
    TriBool getAfterMe() const { return afterMe; }
};

enum Map {
    DEFAULT = 0,
    MAP1 = 1,
    MAP2 = 2,
    MAP3 = 3,
    MAP4 = 4,
    MAP5 = 5,
    MAP6 = 6,
    CHEESER = 7,
    FEFER = 8,
    UNKNOWN = 9
};

// use this structure to save whole information of enemy shoot
typedef struct LastShooted {
    // who was hit
    Trooper teammate;
    // who can hit
    vector<Trooper> possibleEnemies;
    // approximate position of all players who can do this hit
    vector<Point> approxPositions;
    // when we discovered this shoot
    SubMove subMove;
    int damage;
    bool fatal;
    LastShooted(const Trooper& teammate = Trooper()) :
        teammate(teammate),
        possibleEnemies(),
        approxPositions(),
        subMove(-1),
        damage(0),
        fatal(false)
    {}
} LastShooted;

// global variables

Map mapType = UNKNOWN;

typedef std::pair<double, Trooper> TrooperProb; 

// map of all possible enemy troopers on the map
vector<vector<vector<TrooperProb> > > trooperProbs;

// where we saw each trooper last time
typedef pair<Trooper, SubMove> LastSeen;
vector<LastSeen> lastSeen;
SubMove lastSeenEnemy;

// store all enemy shoots here
vector<LastShooted> lastShooted;

int maxTroops = 0;
vector<int> troopOrder;
vector<int> troopOrderRev;
int curTroopIndex;

std::vector<PlayerInfo> playerInfo;

// who is leader now
int leader;

Point globalTarget;
SubMove gtLastUpdated;
bool randomTarget = false;

// matrix of all step distances between each pair of points
std::vector<std::vector<StepMap> > allStepMaps;

// map of step distances to global target
StepMap* globalTargetStepMap = 0; 
// the same but treating all troopers as obstacle
StepMap globalTargetStepMapTroopers;
// the same but treating all troopers but self as obstacle
StepMap globalTargetStepMapTroopersNoSelf;

// the player I attack now
int attackPlayerId = -1;

// point there trooper started this turn
Point startPoint;

SubMove currentSubMove;

// who turned previos time (differs from previous trooper if it is dead)
SubMove prevSubMove;

typedef vector<vector<int> > Fog;

// constant fog map there all cells are in fog
Fog allInFog;

// fog of current trooper
Fog currentFog;
// the same for sniper
Fog currentFogSniper;

// store last fogs for all troopers
deque<Fog> lastFogs[MAX_TROOPERS];
deque<Fog> lastFogsSniper[MAX_TROOPERS];

// then we changed mode last time
SubMove lastModeChange;
Mode currentMode = TRAVEL;

Tactics tactics = NORMAL;

// store hits that I expect
vector<std::pair<Hit, SubMove> > expectedHits;
// store succeeded hits to possible enemies
vector<std::pair<Hit, SubMove> > succeededHits;
// store failed hits to possible enemies
vector<std::pair<Hit, SubMove> > failedHits;

LastSeen& getLastSeen(int playerId, TrooperType ttype, bool* found) {
    for (int i = 0; i < (int)lastSeen.size(); i++) {
        if (lastSeen[i].first.getPlayerId() == playerId &&
            lastSeen[i].first.getType() == ttype) {
            *found = true;
            return lastSeen[i];
        }
    }

    *found = false;
    return lastSeen[0];
}

int numLeftTroopers(const PlayerInfo& pInfo) {
    int liveTroopers = maxTroops;
    for (int i = 0; i < maxTroops; i++) {
        if (pInfo.isDead((TrooperType)i) == true) liveTroopers--;
    }
    return liveTroopers;
}

int numLeftPlayers() {
    int livePlayers = 0;
    for (int i = 1; i < (int)playerInfo.size(); i++) {
        if (numLeftTroopers(playerInfo[i]) > 0) livePlayers++;
    }
    return livePlayers;
}

Point nearestFree(Point point) {
    const CellMap& cellMap = gworld->getCells();
    
    for (int i = 0; i < 100; i++) {
        for (int k = 0; k < i+1; k++) {
            Point near;
            near = point + Point(i,i-k); if (validPoint(near) && cellMap[near.getX()][near.getY()] == FREE) return near;
            near = point + Point(-i,i-k); if (validPoint(near) && cellMap[near.getX()][near.getY()] == FREE) return near;
            near = point + Point(i,-i+k); if (validPoint(near) && cellMap[near.getX()][near.getY()] == FREE) return near;
            near = point + Point(-i,-i+k); if (validPoint(near) && cellMap[near.getX()][near.getY()] == FREE) return near;
        }
    }
    return point;
}

// get number of steps from x,y to target in stepMap even if
// x,y is trooper obstacle
int getStepsTroopers(int x, int y, StepMap& stepMap) {
    if (stepMap[x][y] >= 0) return stepMap[x][y];
    Point near;
    int minPath = 1000;
    near = Point(x,y+1);
    if (validPoint(near) && stepMap[near.x][near.y] >= 0 &&
        stepMap[near.x][near.y] + 1 < minPath) {
        minPath = stepMap[near.x][near.y] + 1;
    }
    near = Point(x,y-1);
    if (validPoint(near) && stepMap[near.x][near.y] >= 0 &&
        stepMap[near.x][near.y] + 1 < minPath) {
        minPath = stepMap[near.x][near.y] + 1;
    }
    near = Point(x+1,y);
    if (validPoint(near) && stepMap[near.x][near.y] >= 0 &&
        stepMap[near.x][near.y] + 1 < minPath) {
        minPath = stepMap[near.x][near.y] + 1;
    }
    near = Point(x-1,y);
    if (validPoint(near) && stepMap[near.x][near.y] >= 0 &&
        stepMap[near.x][near.y] + 1 < minPath) {
        minPath = stepMap[near.x][near.y] + 1;
    }
    return minPath;
}

void initStepMap(const CellMap& cellMap, StepMap& stepMap, int maxStep = 1000, bool placeTroopers = false) {
    stepMap.resize(cellMap.size());
    for (int x = 0; x < (int)cellMap.size(); x++) {
        stepMap[x].resize(cellMap[x].size());
        for (int y = 0; y < (int)cellMap[x].size(); y++) {
            if (cellMap[x][y] == FREE) {
                stepMap[x][y] = maxStep;
            } else {
                stepMap[x][y] = -1;
            }
        }
    }

    if (placeTroopers) {
        for (size_t i = 0; i < gworld->getTroopers().size(); ++i) {
            const Trooper& trooper = gworld->getTroopers()[i];
            if (trooper.getId() != gself->getId()) {
                stepMap[trooper.getX()][trooper.getY()] = -1;
            }
        }
    }
}

void computeStepMap(Point point, StepMap& stepMap) {
    queue<Point> active;
    active.push(point);
    stepMap[point.getX()][point.getY()] = 0;

    while(active.size()) {
        Point curr = active.front();
        int curStep = stepMap[curr.getX()][curr.getY()];
        active.pop();

        Point near;
        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);}
        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);}
        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);}
        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);}
    }
}

void addLastSeen(const Trooper& trooper, SubMove subMove, int i = -1) {
    if (i == -1) {
        // new trooper
        lastSeen.push_back(std::pair<Trooper, SubMove>(trooper, subMove));
    } else {
        lastSeen[i].first = trooper;
        lastSeen[i].second = subMove;
    }
}

// calculates number of turns the trooper did since specified submove
// returns integer if it is known or n+0.5 if it can be n or n+1
double numTurnsSinceSubMove(const Trooper& trooper, SubMove subMove) {
    int playerId = (int)trooper.getPlayerId();

    int i = troopOrderRev[trooper.getType()];

    // how many submoves ago this type of trooper turns
    int moveDiff = curTroopIndex - i;
    if (moveDiff < 0) moveDiff += maxTroops;

    // how many submoves passed since that submove
    int seeDiff = currentSubMove - subMove;

    // special case if we didn't see it yet
    if (subMove == -1 && curTroopIndex == maxTroops-1 && moveDiff == 0) {
        seeDiff--;
    }

    int turns = seeDiff / maxTroops;
    seeDiff -= turns * maxTroops;

    if (seeDiff == 0) return (double)turns; // I saw him myself!

    if (seeDiff < moveDiff) {
        return (double)turns;
    } else if (seeDiff > moveDiff) {
        if (moveDiff == 0) {
            // troop with the same order, if he turns before me, he is gone,
            // if after - he is still there
            if (playerInfo[playerId].getAfterMe() <= MOST_LIKELY_FALSE) {
                return (double)turns + 1.;
            } else if (playerInfo[playerId].getAfterMe() == PROBABLY) {
                return (double)turns + 0.5;
            } else {
                /* (playerInfo[playerId].afterMe >= MOST_LIKELY_TRUE) */
                return (double)turns;
            }
        } else {
            return (double)turns + 1.;
        }
    } else {
        if (subMove == -1) return turns;
        if (playerInfo[playerId].getAfterMe() >= MOST_LIKELY_TRUE) { 
            return (double)turns + 1.; 
        } else if (playerInfo[playerId].getAfterMe() == PROBABLY) {
            return (double)turns + 0.5;
        } else {
            /* (playerInfo[playerId].afterMe <= MOST_LIKELY_FALSE) */
            return turns;
        }
    }
}

double numTurnsSinceLastSeen(const LastSeen& vTrooper) {
    return numTurnsSinceSubMove(vTrooper.first, vTrooper.second);
}

TriBool stillThere(const LastSeen& vTrooper) {
    if (vTrooper.first.isTeammate()) {
        if (vTrooper.second == currentSubMove) {
            return TRUE;
        } else {
            // killed
            return FALSE;
        }
    }

    // here need to analyse whether this player turns before me or after
    int playerId = (int)vTrooper.first.getPlayerId();

    int i = troopOrderRev[vTrooper.first.getType()];

    int moveDiff = curTroopIndex - i;
    if (moveDiff < 0) moveDiff += maxTroops;

    int seeDiff = currentSubMove - vTrooper.second;

    if (seeDiff == 0) return TRUE; // I saw him myself!

    if (seeDiff < moveDiff) {
        return TRUE;
    } else if (seeDiff > moveDiff) {
        if (moveDiff == 0 && seeDiff < maxTroops) {
            // troop with the same order, if he turns before me, he is gone,
            // if after - he is still there
            return playerInfo[playerId].getAfterMe();
        } else {
            return FALSE;
        }
    } else {
        return triNot(playerInfo[playerId].getAfterMe());
    }
}

bool isDead(const Trooper& vTrooper) {
    return playerInfo[(int)vTrooper.getPlayerId()].isDead(vTrooper.getType());
}

TriBool stillThere(const Trooper& trooper) {
    if (isDead(trooper)) return FALSE;
    for (int i = 0; i < (int)lastSeen.size(); i++) {
        if (lastSeen[i].first.getPlayerId() == trooper.getPlayerId() &&
            lastSeen[i].first.getType() == trooper.getType()) {
            return stillThere(lastSeen[i]);
        }
    }
    return FALSE;
}

int findFastestMove(const StepMap& stepMap, TrooperStance curStance, Position target, TrooperStance* moveStance = 0) {
    TrooperStance targetStance = target.stance;
    int numSteps = stepMap[target.getX()][target.getY()];
    TrooperStance maxStance = (TrooperStance)std::max(curStance, targetStance);

    if (numSteps <= 1) {
        if (moveStance) *moveStance = maxStance;
        return (maxStance - curStance) * ggame->getStanceChangeCost() + numSteps * getMoveCost(maxStance) + (maxStance - targetStance) * ggame->getStanceChangeCost();
    } else {
        if (moveStance) *moveStance = STANDING;
        return (STANDING - curStance) * ggame->getStanceChangeCost() + numSteps * ggame->getStandingMoveCost() + (STANDING - targetStance) * ggame->getStanceChangeCost();
    }
} 

int actionCost(Trooper trooper, ActionType action) {
    switch (action)
    {
    case model::UNKNOWN_ACTION:
    case model::END_TURN:
        return 0;
    case model::MOVE:
        return getMoveCost(trooper.getStance());
    case model::SHOOT:
        return trooper.getShootCost();
    case model::RAISE_STANCE:
    case model::LOWER_STANCE:
        return ggame->getStanceChangeCost();
    case model::THROW_GRENADE:
        return ggame->getGrenadeThrowCost();
    case model::USE_MEDIKIT:
        return ggame->getMedikitUseCost();
    case model::EAT_FIELD_RATION:
        return ggame->getFieldRationEatCost();
    case model::HEAL:
        return ggame->getFieldMedicHealCost();
    case model::REQUEST_ENEMY_DISPOSITION:
        return ggame->getCommanderRequestEnemyDispositionCost();
    default:
        return 0;
    }
}

// returns true if enemy trooper turns later than mine
TriBool turnsLater(const Trooper& enemyTrooper, const Trooper& myTrooper) {
    int t1 = troopOrderRev[enemyTrooper.getType()];
    int t2 = troopOrderRev[myTrooper.getType()];

    t1 -= curTroopIndex;
    t2 -= curTroopIndex;

    if (t1 < 0) t1 += maxTroops;
    if (t2 < 0) t2 += maxTroops;

    if (t1 == 0) {
        if (t2 == 0) return FALSE;
        return triNot(playerInfo[(int)enemyTrooper.getPlayerId()].getAfterMe());
    }

    if (t1 < t2) return FALSE;
    if (t1 > t2) return TRUE;

    return playerInfo[(int)enemyTrooper.getPlayerId()].getAfterMe();
}

std::ostream& operator<<(std::ostream& os, const Trooper& trooper) {
    os << trooper.getPlayerId() << (trooper.isTeammate() ? "" : " (enemy)") << " " << trooper.getType();
    return os;
}

static long long lastId = 0;

// structure that describes whole target for trooper
struct Target {
    // where to hide
    Position hidePosition;
    Action action;
    // where to action
    Position actionPosition;
    long long id;
    int score;
    double scoreNextTurn;
    int safety;
    int priority;
    bool eatRation;
    bool throwGrenade;
    vector<std::pair<Hit, SubMove> > hits;
    double visibileProb;

    Target(int hitPoints) :
        safety(hitPoints),
        priority(0),
        score(0),
        scoreNextTurn(0.),
        eatRation(false),
        throwGrenade(false),
        id(lastId++),
        hits(),
        visibileProb(1.)
    {}
};

ostream& operator<<(ostream& os, const Action& action) {
    os << action.actionType;
    if (action.actionType != END_TURN) {
        os << " to " << action.x << "," << action.y;
    }
    return os;
}

ostream& operator<<(ostream& os, const Target& target) {
    os << target.action << " from " << target.actionPosition.getX() << "," << target.actionPosition.getY() << " then hide to " << 
        target.hidePosition.getX() << "," << target.hidePosition.getY() << "(score=" << target.score << ", safety=" << target.safety << ")";
    return os;
}

ostream& operator<<(ostream& os, const Point& point) {
    os << point.x << "," << point.y;
    return os;
}

ostream& operator<<(ostream& os, const Position& pos) {
    os << pos.point << "," << pos.stance;
    return os;
}

int manhattanDistance(const Point& p1, const Point& p2) {
    return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}

int stepDistance(const Point& p1, const Point p2) {
    const StepMap& stepMap = allStepMaps[p1.getX()][p1.getY()];
    return stepMap[p2.getX()][p2.getY()]; 
}

int squareDist(int x1, int y1, int x2, int y2) {
    return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
}

int squareDist(const Unit& unit, int x, int y) {
    return squareDist(unit.getX(), unit.getY(), x, y);
}

int squareDist(const Unit& unit1, const Unit& unit2) {
    return squareDist(unit1.getX(), unit1.getY(), unit2.getX(), unit2.getY());
}

int squareDist(const Unit& unit, const Point& point) {
    return squareDist(unit.getX(), unit.getY(), point.getX(), point.getY());
}

int squareDist(const Point& p1, const Point& p2) {
    return squareDist(p1.getX(), p1.getY(), p2.getX(), p2.getY());
}

bool weSeeIt(const Trooper& enemy) {
    const vector<Trooper>& troopers = gworld->getTroopers();
    for (size_t i = 0; i < troopers.size(); ++i) {
        Trooper trooper = troopers.at(i);

        double visionRange = trooper.getVisionRange();
        if (enemy.getType() == SNIPER && trooper.getType() != SCOUT) {
            // see panalty
            if (enemy.getStance() == KNEELING) visionRange-= 0.5;
            if (enemy.getStance() == PRONE) visionRange-= 1.;
        }

        if (trooper.isTeammate()) {
            if (gworld->isVisible(visionRange,  
                trooper.getX(), trooper.getY(), trooper.getStance(),        
                enemy.getX(), enemy.getY(), enemy.getStance())) {
                return true;
            }
        }
    }
    return false;
}

void initCurrentFog() {
    currentFog.resize(gworld->getWidth());
    currentFogSniper.resize(gworld->getWidth());
    for (int x = 0; x < gworld->getWidth(); x++) {
        currentFog[x].resize(gworld->getHeight());
        currentFogSniper[x].resize(gworld->getHeight());
        for (int y = 0; y < gworld->getHeight(); y++) {
            const vector<Trooper>& troopers= gworld->getTroopers();

            int fog = _TROOPER_STANCE_COUNT_;
            for (size_t i = 0; i < troopers.size(); ++i) {
                Trooper trooper = troopers.at(i);

                double visionRange = trooper.getVisionRange();
                if (trooper.isTeammate()) {
                    for (int i = fog-1; i >= 0; i--) {
                        if (gworld->isVisible(visionRange,  
                            trooper.getX(), trooper.getY(), trooper.getStance(),        
                            x, y, (TrooperStance)i)) {
                            fog = i;
                        } else {
                            break;
                        }
                    }
                }
            }
            currentFog[x][y] = fog; // fog = KNEELING means that we see KNEELING and higher

            fog = _TROOPER_STANCE_COUNT_;
            for (size_t i = 0; i < troopers.size(); ++i) {
                Trooper trooper = troopers.at(i);
                double visionRange = trooper.getVisionRange();

                if (trooper.isTeammate()) {
                    if (trooper.getType() != SCOUT) {
                        visionRange -= (double)(_TROOPER_STANCE_COUNT_ - fog)* 0.5;
                    }
                    for (int i = fog-1; i >= 0; i--) {
                        if (gworld->isVisible(visionRange,  
                            trooper.getX(), trooper.getY(), trooper.getStance(),        
                            x, y, (TrooperStance)i)) {
                            fog = i;
                            visionRange -= 0.5;
                        } else {
                            break;
                        }
                    }
                }
            }
            currentFogSniper[x][y] = fog; // fog = KNEELING means that we see KNEELING and higher
        }
    }
}

double updateFog(Fog& fog, Fog& fogSniper, const Trooper& trooper) {
    double revealPossibleEnemies = 0.;
    if (!trooper.isTeammate()) return 0;
    for (int x = 0; x < gworld->getWidth(); x++) {
        for (int y = 0; y < gworld->getHeight(); y++) {
            double visionRange = trooper.getVisionRange();
            for (int i = fog[x][y]-1; i >= 0; i--) {
                if (gworld->isVisible(visionRange,  
                    trooper.getX(), trooper.getY(), trooper.getStance(),        
                    x, y, (TrooperStance)i)) {
                    if (trooperProbs[x][y].size() > 0) {
                        for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
                            if (trooperProbs[x][y][p].second.getType() != SNIPER) {
                                revealPossibleEnemies += trooperProbs[x][y][p].first;
                            }
                        }
                    }
                    fog[x][y] = i;
                } else {
                    break;
                }
            }

            // the same for sniper
            if (trooper.getType() != SCOUT) {
                visionRange -= (double)(_TROOPER_STANCE_COUNT_ - fogSniper[x][y]) * 0.5;
            }

            for (int i = fogSniper[x][y]-1; i >= 0; i--) {
                if (gworld->isVisible(visionRange,  
                    trooper.getX(), trooper.getY(), trooper.getStance(),        
                    x, y, (TrooperStance)i)) {
                    if (trooperProbs[x][y].size() > 0) {
                        for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
                            if (trooperProbs[x][y][p].second.getType() == SNIPER) {
                                revealPossibleEnemies += trooperProbs[x][y][p].first;
                            }
                        }
                    }
                    fogSniper[x][y] = i;
                    visionRange -= 0.5;
                } else {
                    break;
                }
            }
        }
    }
    return revealPossibleEnemies;
}

bool inFog(const Position& pos, const Fog& fog) {
    return fog[pos.getX()][pos.getY()] > pos.stance;
}

bool inFog(int x, int y, TrooperStance stance, const Fog& fog) {
    return fog[x][y] > stance;
}

// check if this trooper can do this damage
// or greater if 'greater' flag is specified
bool canDoThisDamage(const Trooper& trooper, int damage, bool* hasGrenade, bool* hasFieldRation, int actionPoints = -1, bool greater = false) {
    if (actionPoints == -1) {
        // top call, compute action points
        actionPoints = trooper.getInitialActionPoints();
        if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT) {
            actionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
        }

        bool hg = *hasGrenade;
        bool hf = false;
        if (canDoThisDamage(trooper, damage, &hg, &hf, actionPoints, greater)) {
            *hasGrenade = hg;
            return true;
        }

        if (*hasFieldRation) {
            // also try to eat field ration
            actionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
            *hasFieldRation = false;

            return canDoThisDamage(trooper, damage, hasGrenade, hasFieldRation, actionPoints, greater);
        }
        return false;
    }

    if (actionPoints < 0) return false;

    if (damage < 0) {
        if (greater) {
            return true;
        } else {
            return false;
        }
    }

    if (damage == 0) return true;

    bool canDoThis;
    bool hg = false;
    bool hf = false;
    canDoThis = canDoThisDamage(trooper, damage - trooper.getStandingDamage(), &hg, &hf, actionPoints - trooper.getShootCost(), greater);
    if (canDoThis) return true;
    canDoThis = canDoThisDamage(trooper, damage - trooper.getKneelingDamage(), &hg, &hf, actionPoints - trooper.getShootCost(), greater);
    if (canDoThis) return true;
    canDoThis = canDoThisDamage(trooper, damage - trooper.getProneDamage(), &hg, &hf, actionPoints - trooper.getShootCost(), greater);
    if (canDoThis) return true;

    if (*hasGrenade == true) {
        *hasGrenade = false;

        canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
        canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage() - ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
        canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage() - 2*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
        canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage() - 3*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
        canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeDirectDamage() - 4*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
        canDoThis = canDoThisDamage(trooper, damage - ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
        canDoThis = canDoThisDamage(trooper, damage - 2*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
        canDoThis = canDoThisDamage(trooper, damage - 3*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
        canDoThis = canDoThisDamage(trooper, damage - 4*ggame->getGrenadeCollateralDamage(), hasGrenade, &hf, actionPoints - ggame->getGrenadeThrowCost(), greater);
        if (canDoThis) return true;
    }

    return false;
}

void updatePlayersScore() {
    const vector<Player>& players = gworld->getPlayers();

    for (int p = 0; p < (int)players.size(); p++) {
        const Player& player = players[p];
        PlayerInfo& pInfo = playerInfo[(int)player.getId()];

        if (player.getId() != me->getId() && currentSubMove.subsubMove != 0) continue;

        pInfo.lastScoreDiff = player.getScore() - pInfo.lastScore;

        if (player.getId() == me->getId()) {
            // I hited somebody
            int expectedScore = 0;
            int expectedKilled = 0;
            long long playerId = me->getId();
            for (int i = 0; i < (int)expectedHits.size(); i++) {
                const Hit& hit = expectedHits[i].first;

                if (hit.prob < 1) {
                    // shooted to phantom
                    if (pInfo.lastScoreDiff > 0) {
                        succeededHits.push_back(expectedHits[i]);
#if 0
                        // !!! can do false positive
                        // update last seen
                        if (hit.damage == pInfo.lastScoreDiff) {
                            bool found;
                            LastSeen& ls = getLastSeen((int)hit.trooper.getPlayerId(), hit.trooper.getType(), &found);
                            ls.second = expectedHits[i].second;
                            ls.first = hit.trooper;
                        }
#endif
                    } else {
                        failedHits.push_back(expectedHits[i]);
                    }
                }

                expectedScore += hit.damage;
                if (hit.damage == hit.trooper.getHitpoints()) {
                    playerId = hit.trooper.getPlayerId();
                    expectedKilled++;
                }
            }

            expectedScore += expectedKilled * ggame->getTrooperEliminationScore();
            if (expectedKilled == numLeftTroopers(playerId)) {
                expectedScore += ggame->getPlayerEliminationScore() - ggame->getTrooperEliminationScore();
            }

            if (expectedScore == pInfo.lastScoreDiff) {
                if (expectedScore > 0) {
                    std::cout << "score changed as expected: " << expectedScore << std::endl;
                    // ok, as we expected
                    for (int i = 0; i < (int)expectedHits.size(); i++) {
                        const Hit& hit = expectedHits[i].first;

                        if (hit.damage == hit.trooper.getHitpoints()) {
                            // we expect that he will die
                            int playerId = (int)hit.trooper.getPlayerId();
                            playerInfo[playerId].setDead(hit.trooper.getType());
                        } else {
                            bool found;
                            int playerId = (int)hit.trooper.getPlayerId();
                            LastSeen& ls = getLastSeen(playerId, hit.trooper.getType(), &found);

                            if (found && ls.second != currentSubMove) {
                                // update hitpoints
                                TrooperStateDiff diff;
                                diff.hitPoints = -hit.damage;

                                ls.first = newVirtualTrooper(ls.first, diff);
                            }
                        }
                    }
                }
            } else if (expectedScore < pInfo.lastScoreDiff) {
                std::cout << "More score than expected. " << pInfo.lastScoreDiff << " instead of " << expectedScore << std::endl;
                // probably we hit someone else with grenade or another trooper moved to this position and died
            } else {
                std::cout << "Less score than expected. " << pInfo.lastScoreDiff << " instead of " << expectedScore << std::endl;
            }
        } else if (pInfo.lastScore != player.getScore()) {
            // player score changed, analyse it
            if (prevSubMove == currentSubMove - 1 && 
                pInfo.getAfterMe() == PROBABLY) {

                // trooper of the same type can do
                bool thisTroopCanDo = false;
                // trooper of the previous type can do
                bool thatTroopCanDo = false;

                if (!pInfo.isDead((TrooperType)troopOrder[curTroopIndex])) {
                    bool found;
                    const Trooper& thisTrooper = getLastSeen((int)player.getId(), (TrooperType)troopOrder[curTroopIndex], &found).first;
                    if (found) {
                        // assume worst case
                        bool hasGrenage = true;
                        bool hasFieldRation = true;

                        thisTroopCanDo = canDoThisDamage(thisTrooper, player.getScore() - pInfo.lastScore, &hasGrenage, &hasFieldRation);
                    }
                }

                int troopIndex = curTroopIndex - 1;
                if (troopIndex < 0) troopIndex += maxTroops;

                if (!pInfo.isDead((TrooperType)troopOrder[troopIndex])) {
                    bool found;
                    const Trooper& thatTrooper = getLastSeen((int)player.getId(), (TrooperType)troopOrder[troopIndex], &found).first;
                    if (found) {
                        // assume worst case
                        bool hasGrenage = true;
                        bool hasFieldRation = true;

                        thatTroopCanDo = canDoThisDamage(thatTrooper, player.getScore() - pInfo.lastScore, &hasGrenage, &hasFieldRation);
                    }
                }
                
                if (thisTroopCanDo && !thatTroopCanDo) {
                    pInfo.setAfterMe(MOST_LIKELY_FALSE);
                } else if (thatTroopCanDo && !thisTroopCanDo) {
                    pInfo.setAfterMe(MOST_LIKELY_TRUE);
                }
            }
        }

        pInfo.lastScore = player.getScore();
    }
}

// analyse last shoot to me and compute where this trooper can hide
void checkWhoCanShootSo(LastShooted& lshooted) {
    const Trooper& teammate = lshooted.teammate;
    int damage = lshooted.damage;

    if (damage == 0) return;

    const vector<Player>& players = gworld->getPlayers();
    
    vector<Trooper> possibleTroopers;

    for (int p = 0; p < (int)players.size(); p++) {
        const Player& player = players[p];

        if (player.getId() == me->getId()) continue;

        PlayerInfo& pInfo = playerInfo[(int)player.getId()];

        if (pInfo.lastScoreDiff < damage) continue;
        
        // start with current trooper type
        int possibleStart = 0;
        // end with trooper type that turned previous time
        int possibleEnd = currentSubMove - prevSubMove;

        if (pInfo.getAfterMe() >= MOST_LIKELY_TRUE) possibleStart++;
        if (pInfo.getAfterMe() <= MOST_LIKELY_FALSE) possibleEnd--;

        for (int i = possibleStart; i <= possibleEnd; i++) {
            int trooperIndex = curTroopIndex - i;
            if (trooperIndex < 0) trooperIndex += maxTroops;
            TrooperType ttype = (TrooperType)troopOrder[trooperIndex];
        
            if (pInfo.isDead(ttype)) continue;

            bool found;
            const LastSeen& lseen = getLastSeen((int)player.getId(), ttype, &found);
            if (!found) continue;

            const Trooper& enemy = lseen.first;

            if (enemy.isTeammate()) continue;

            {
                // hard check
                bool hasGrenade = enemy.isHoldingGrenade();
                bool hasFieldRation = enemy.isHoldingFieldRation();
                bool canDo = false;

                if (numTurnsSinceLastSeen(lseen) >= 2) {
                    // could take a bonus
                    hasGrenade = true;
                    hasFieldRation = true;
                }

                if (canDoThisDamage(enemy, damage, &hasGrenade, &hasFieldRation, -1, lshooted.fatal)) {
                    int minScoreDiff = damage;
                    if (lshooted.fatal) minScoreDiff += ggame->getTrooperEliminationScore();
                    if (pInfo.lastScoreDiff >= minScoreDiff) {
                        canDo = true;
                    }
                }

                if (!canDo) continue;
            }

            if (lseen.second == currentSubMove) {
                // this is him, skip others
                possibleTroopers.clear();
                possibleTroopers.push_back(enemy);
                break;
            }

            double numTurns = numTurnsSinceLastSeen(lseen);
            if (lseen.second == currentSubMove) numTurns = 1;

            int numFullTurnsCeil = (int)ceil(numTurns);

            if (numFullTurnsCeil == 0) {
                continue;
            }

            int maxActionPointsPerTurn = enemy.getInitialActionPoints();
            if (enemy.getType() != COMMANDER && enemy.getType() != SCOUT) maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();

            int wholeActionPointsCeil = maxActionPointsPerTurn * numFullTurnsCeil;

            const vector<vector<CellType> >& cells = gworld->getCells();

            for (int x = 0; x < gworld->getWidth(); x++) {
                for (int y = 0; y < gworld->getHeight(); y++) {
                    if (cells[x][y] != FREE) continue;
                    const StepMap& stepMap = allStepMaps[x][y];

                    for (int stance = STANDING; stance >= PRONE; stance--) {
                        // possible fire positions
                        int moveCost = findFastestMove(stepMap, (TrooperStance)stance, enemy);
                        if (moveCost >= wholeActionPointsCeil) continue; 

                        if (!gworld->isVisible(enemy.getShootingRange(), x, y, (TrooperStance)stance, 
                            teammate.getX(), teammate.getY(), teammate.getStance())) {
                            continue;
                        }
                            
                        // possible shoot position, check it
                        TrooperStateDiff diff;
                        diff.x = x - enemy.getX();
                        diff.y = y - enemy.getY();
                        diff.stance = stance - enemy.getStance();
                        if (numTurnsSinceLastSeen(lseen) >= 2) {
                            // could take a bonus
                            diff.plusGrenade = true;
                            diff.plusMedikit = true;
                        }
                        Trooper shootCandidate = newVirtualTrooper(enemy, diff);

                        // look there it can hide
                        for (int xh = 0; xh < gworld->getWidth(); xh++) {
                            for (int yh = 0; yh < gworld->getHeight(); yh++) {
                                if (cells[xh][yh] != FREE) continue;
                                for (int sh = STANDING; sh >= PRONE; sh--) {
                                    if (!inFog(xh, yh, (TrooperStance)sh, enemy.getType() == SNIPER ? currentFogSniper : currentFog)) continue;

                                    // can hide there
                                    int hideMoveCost = findFastestMove(stepMap, (TrooperStance)stance, Position(xh, yh, (TrooperStance)sh));

                                    int pointsForAction = wholeActionPointsCeil - moveCost - hideMoveCost;

                                    if (hideMoveCost >= maxActionPointsPerTurn || pointsForAction <= 0) continue;
                                    bool hasGrenade = shootCandidate.isHoldingGrenade();
                                    bool hasFieldRation = shootCandidate.isHoldingFieldRation();

                                    if (canDoThisDamage(shootCandidate, damage, &hasGrenade, &hasFieldRation, pointsForAction, lshooted.fatal)) {
                                        if (hasGrenade != shootCandidate.isHoldingGrenade()) {
                                            // he used grenage
                                            if (squareDist(x,y,teammate.getX(), teammate.getY()) > 25) continue;
                                        }

                                        if (lseen.second < prevSubMove) {
                                            bool canDo = false;
                                            int prevTrooperIndex = prevSubMove % maxTroops;
                                            // loop other possible starting positions
                                            for (int xs = 0; xs < gworld->getWidth(); xs++) {
                                                for (int ys = 0; ys < gworld->getHeight(); ys++) {
                                                    if (cells[xs][ys] != FREE) continue;
                                                    for (int ss = STANDING; ss >= PRONE; ss--) {
                                                        int positioningMoveCost = findFastestMove(stepMap, (TrooperStance)stance, Position(xs, ys, (TrooperStance)ss));

                                                        if (positioningMoveCost + hideMoveCost >= maxActionPointsPerTurn) continue;

                                                        bool hasGrenade = shootCandidate.isHoldingGrenade();
                                                        bool hasFieldRation = shootCandidate.isHoldingFieldRation();

                                                        int pointsForAction = maxActionPointsPerTurn - positioningMoveCost - hideMoveCost;

                                                        if (canDoThisDamage(shootCandidate, damage, &hasGrenade, &hasFieldRation, pointsForAction, lshooted.fatal)) {
                                                            if (hasGrenade != shootCandidate.isHoldingGrenade()) {
                                                                // he used grenage
                                                                if (squareDist(x,y,teammate.getX(), teammate.getY()) > 25) continue;
                                                            }
                                                        } else {
                                                            continue;
                                                        }

                                                        // it must be in fog last turn, otherwise I saw him
                                                        if (!inFog(xs, ys, (TrooperStance)ss, enemy.getType() == SNIPER ? lastFogsSniper[prevTrooperIndex].front() : lastFogs[prevTrooperIndex].front())) continue;

                                                        //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;
                                                        canDo = true;
                                                        break;
                                                    }
                                                    if (canDo) break;
                                                }
                                                if (canDo) break;
                                            }
                                            if (!canDo) continue;
                                        } else {
                                            //std::cout << "start from " << Position(ls.first) << " attack at " << Position(x,y,(TrooperStance)(stance)) << " hide at " << Position(xh,yh,(TrooperStance)sh) <<  std::endl;
                                        }
                                                        
                                        // look if already stored this position
                                        bool found = false;
                                        for (int pp = 0; pp < (int)possibleTroopers.size(); pp++) {
                                            if (possibleTroopers[pp].getPlayerId() == enemy.getPlayerId() &&
                                                possibleTroopers[pp].getType() == enemy.getType() && 
                                                Point(possibleTroopers[pp]) == Point(xh,yh)) {
                                                if (sh > possibleTroopers[pp].getStance()) {
                                                    // store maximum possible stance
                                                    TrooperStateDiff diff;
                                                    diff.x = xh - enemy.getX();
                                                    diff.y = yh - enemy.getY();
                                                    diff.stance = sh - enemy.getStance();
                                                    Trooper hideTrooper = newVirtualTrooper(enemy, diff);
                                                    possibleTroopers[pp] = hideTrooper;
                                                }
                                                found = true;
                                            }
                                        }

                                        if (found) continue;

                                        TrooperStateDiff diff;
                                        diff.x = xh - enemy.getX();
                                        diff.y = yh - enemy.getY();
                                        diff.stance = sh - enemy.getStance();
                                        Trooper hideTrooper = newVirtualTrooper(enemy, diff);
                                        possibleTroopers.push_back(hideTrooper);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    lshooted.possibleEnemies = possibleTroopers;

    // compute approximate player position that this shoot gives
    lshooted.approxPositions.resize(playerInfo.size());

    for (long long pid = 1; pid < (int)playerInfo.size(); pid++) {
        // find approximate position
        int xx = 0;
        int yy = 0;
        int tt = 0;
        for (int e = 0; e < (int)lshooted.possibleEnemies.size(); e++) {
            const Trooper& trooper = lshooted.possibleEnemies[e];
            if (isDead(trooper)) continue;
            if (trooper.getPlayerId() != pid) continue;
            xx += trooper.getX();
            yy += trooper.getY();
            tt++;
        }

        if (tt > 0) {
            lshooted.approxPositions[(int)pid] = Point(xx/tt, yy/tt);
        }
    }
}

void updateLastShooted(LastShooted& ls) {
    if (ls.subMove == currentSubMove && currentSubMove.subsubMove == 0) {
        // just happened, initialize
        checkWhoCanShootSo(ls);
    }

    // throw out troopers that are not possible now
    for (int e = 0; e < (int)ls.possibleEnemies.size(); e++) {
        const Trooper& enemy = ls.possibleEnemies[e];

        bool found;
        const LastSeen& lSeen = getLastSeen((int)enemy.getPlayerId(), enemy.getType(), &found);
        if (found && lSeen.second == currentSubMove &&
            enemy.getX() == lSeen.first.getX() &&
            enemy.getY() == lSeen.first.getY()) {
            // this is definetely him, erase others
            ls.possibleEnemies.clear();
            ls.possibleEnemies.push_back(lSeen.first);
            break;
        }

        if (isDead(enemy) || numTurnsSinceSubMove(enemy, ls.subMove) > 0 ||
            !inFog(enemy, enemy.getType() == SNIPER ? currentFogSniper : currentFog)) {
            ls.possibleEnemies.erase(ls.possibleEnemies.begin() + e);
            e--;
        }
    }

    if (ls.possibleEnemies.size() == 0) return;

    std::cout << ls.teammate << " heated by " << ls.damage << " " << (currentSubMove - ls.subMove) << " submoves ago. It can be " << std::endl;
    for (int pe = 0; pe < (int)ls.possibleEnemies.size(); pe++) {
        std::cout << ls.possibleEnemies[pe] << " hidden in " << Position(ls.possibleEnemies[pe]) << std::endl;
    }
}

void updateLastShooted() {
    for (int i = 0; i < (int)lastShooted.size(); i++) {
        updateLastShooted(lastShooted[i]);
    }
}

// updates last seen vector using current world come from runner
void updateLastSeen() {
    const vector<Trooper>& troopers = gworld->getTroopers();
    bool enemy = false;
    bool attention = false;
    bool leaderFound = false;
    for (size_t t = 0; t < troopers.size(); ++t) {
        Trooper trooper = troopers.at(t);

        if (trooper.isTeammate()) {
            if (leader == trooper.getType()) leaderFound = true;
            if (currentSubMove == 0 && currentSubMove.subsubMove == 0) {
                int xOffset = min(trooper.getX(), gworld->getWidth() - trooper.getX() - 1);
                int yOffset = min(trooper.getY(), gworld->getHeight() - trooper.getY() - 1);
                
                // very first move. We know positions of all enemy troopers since it is symmetric
                int numPlayers = (int)gworld->getPlayers().size();
                for (long long id = 1; id <= numPlayers; id++) {
                    if (id == 1) {
                        TrooperStateDiff diff(
                            -trooper.getX() + xOffset, 
                            -trooper.getY() + yOffset, 
                            0, 0, false, (int)(id - trooper.getPlayerId()));
                        Trooper enemy = newVirtualTrooper(trooper, diff);
                        addLastSeen(enemy, SubMove(-1,0));
                    } else if (id == 2) {
                        TrooperStateDiff diff(
                            -trooper.getX() + (gworld->getWidth() - 1 - xOffset), 
                            -trooper.getY() + (gworld->getHeight() - 1 - yOffset), 
                            0, 0, false, (int)(id - trooper.getPlayerId()));
                        Trooper enemy = newVirtualTrooper(trooper, diff);
                        addLastSeen(enemy, SubMove(-1,0));
                    } else if (id == 3) {
                        TrooperStateDiff diff(
                            -trooper.getX() + (gworld->getWidth() - 1 - xOffset), 
                            -trooper.getY() + yOffset, 
                            0, 0, false, (int)(id - trooper.getPlayerId()));
                        Trooper enemy = newVirtualTrooper(trooper, diff);
                        addLastSeen(enemy, SubMove(-1,0));
                    } else if (id == 4) {
                        TrooperStateDiff diff(
                            -trooper.getX() + xOffset, 
                            -trooper.getY() + (gworld->getHeight() - 1 - yOffset), 
                            0, 0, false, (int)(id - trooper.getPlayerId()));
                        Trooper enemy = newVirtualTrooper(trooper, diff);
                        addLastSeen(enemy, SubMove(-1,0));
                    }
                }
            }
        } else {
            int closest = 1000;
            // find closest teammate to the enemy and make him leader
            for (size_t tt = 0; tt < troopers.size(); ++tt) {
                Trooper teammate = troopers.at(tt);
                if (teammate.isTeammate()) {
                    if (squareDist(teammate, trooper) < closest) {
                        leader = teammate.getType();
                        leaderFound = true;
                        closest = squareDist(teammate, trooper);
                    }
                }
            }
            enemy = true;
        } 
        
        // then, see that is changed since previous seen for this trooper
        int i;
        for (i = 0; i < (int)lastSeen.size(); i++) {
            if (lastSeen[i].first.getPlayerId() == trooper.getPlayerId() &&
                lastSeen[i].first.getType() == trooper.getType()
                ) {

                if (isDead(lastSeen[i].first)) {
                    // marked him as dead but he is alive!!
                    SHOULD_NOT_HAPPEN;
                    // revert him to last seen vector
                    addLastSeen(trooper, currentSubMove, i);
                    playerInfo[(int)trooper.getPlayerId()].setAlive(trooper.getType());
                    continue;
                }

                // calculate average speed
                double moves = numTurnsSinceLastSeen(lastSeen[i]);
                if (moves > 0 && !trooper.isTeammate()) {                    
                    int dist = stepDistance(lastSeen[i].first, trooper);
                    int movesCeil = (int)ceil(moves);
                    int movesFloor = (int)floor(moves);
                    double averSpeedFloor = (double)dist / movesCeil;
                    double averSpeedCeil = (double)dist / movesFloor;
                    int maxActionPoints = trooper.getInitialActionPoints();
                    if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT) 
                        maxActionPoints += ggame->getCommanderAuraBonusActionPoints();
                    int maxSpeed = maxActionPoints / ggame->getStandingMoveCost();

                    if (averSpeedCeil > maxSpeed) {
                        // means that movesFloor can't happen
                        if (trooper.getType() == gself->getType()) {
                            playerInfo[(int)trooper.getPlayerId()].setAfterMe(MOST_LIKELY_FALSE);
                        } else {
                            playerInfo[(int)trooper.getPlayerId()].setAfterMe(MOST_LIKELY_TRUE);
                        }
                        averSpeedCeil = averSpeedFloor;
                    }

                    averSpeedCeil = (averSpeedCeil + averSpeedFloor) / 2;

                    playerInfo[(int)trooper.getPlayerId()].averageSpeed = 
                        (averSpeedCeil + playerInfo[(int)trooper.getPlayerId()].averageSpeed) / 2;
                }

                int j = troopOrderRev[trooper.getType()];
                int diff = curTroopIndex - j;
                if (diff < 0) diff += maxTroops;

                // already seen before, check whether it changed since last time
                
                if (!trooper.isTeammate()) {
                    if (lastSeen[i].second != currentSubMove) { 
                        if (Position(trooper) != Position(lastSeen[i].first) ||
                            trooper.isHoldingFieldRation() != lastSeen[i].first.isHoldingFieldRation() ||
                            trooper.isHoldingGrenade() != lastSeen[i].first.isHoldingGrenade() ||
                            trooper.isHoldingMedikit() != lastSeen[i].first.isHoldingMedikit() ||
                            trooper.getActionPoints() != lastSeen[i].first.getActionPoints()
                            ) {
                            if (lastSeen[i].second == currentSubMove-1) {
                                // this happened second ago!
                                if (diff == 0) {
                                    // if it is the trooper of the same type he turns before me
                                    playerInfo[(int)trooper.getPlayerId()].setAfterMe(FALSE);
                                } else {
                                    // otherwise - after
                                    playerInfo[(int)trooper.getPlayerId()].setAfterMe(TRUE);
                                }
                            }
                        }

                        int lastSeenSubMove = lastSeen[i].second;
                        int seenDiff = currentSubMove - lastSeenSubMove;

                        // find who saw this position last time
                        for (int j = 1; j < maxTroops; j++) {
                            if (j >= seenDiff) break;;
                            int tIndex = curTroopIndex - j;
                            if (tIndex < 0) tIndex += maxTroops;
                            if (!inFog(trooper, trooper.getType() == SNIPER ? lastFogsSniper[tIndex].front() : lastFogs[tIndex].front())) {
                                // he saw this position j submoves before but the trooper was seen seenDiff turns before
                                if (trooper.getType() == gself->getType()) {
                                    playerInfo[(int)trooper.getPlayerId()].setAfterMe(FALSE);
                                } else if (trooper.getType() == troopOrder[tIndex]) {
                                    playerInfo[(int)trooper.getPlayerId()].setAfterMe(TRUE);
                                }
                                break;
                            }
                        }
                    }
                } else {
                    // shooted?
                    int diff = lastSeen[i].first.getHitpoints() - trooper.getHitpoints();
                    if (diff > 0) {
                        enemy = true;
                        leader = trooper.getType();
                        // try to analyze who can do this
                        LastShooted ls;
                        ls.teammate = trooper;
                        ls.damage = diff;
                        ls.subMove = currentSubMove;
                        lastShooted.push_back(ls);
                    }
                }

                // update last seen
                addLastSeen(trooper, currentSubMove, i);
                break;
            }
        }

        if (i == (int)lastSeen.size()) {
            // not found?? why
            SHOULD_NOT_HAPPEN;
        }
    }

    // how many moves be in attention
    int attentionTime = numLeftPlayers() > 2 ? 2 : 4;

    // go through other lastseens and check the ones that was not updated
    for (int i = 0; i < (int)lastSeen.size(); i++) {
        const Trooper& trooper = lastSeen[i].first;

        if (isDead(trooper)) continue;

        if (lastSeen[i].second != -1 && stillThere(lastSeen[i]) && !trooper.isTeammate()) {
            enemy = true;
        }

        if (lastSeen[i].second != currentSubMove ||
            lastSeen[i].second.subsubMove != currentSubMove.subsubMove) {
            // means that this trooper is not on the map now
            if (trooper.isTeammate()) {
                if (isDead(trooper)) {
                    // already marked as dead
                } else {
                    // it was killed! Do something
                    playerInfo[(int)trooper.getPlayerId()].setDead(trooper.getType());

                    LastShooted ls;
                    ls.subMove = currentSubMove;
                    ls.teammate = trooper;
                    ls.damage = lastSeen[i].first.getHitpoints();
                    ls.fatal = true;
                    lastShooted.push_back(ls);
                }
            } else {
                if (lastSeen[i].second >= 0 &&
                    currentSubMove-lastSeen[i].second < maxTroops * attentionTime) attention = true;
                // is in fog or moved away.
                if (weSeeIt(trooper)) {
                    // we see this position now.
                    if (stillThere(lastSeen[i]) == TRUE) {
                        // it was killed
                        playerInfo[(int)trooper.getPlayerId()].setDead(trooper.getType());
                        // remove from lastSeen
                        continue;
                    }

                    int lastSeenSubMove = lastSeen[i].second;
                    int seenDiff = currentSubMove - lastSeenSubMove;

                    if (seenDiff < maxTroops) {
                        // seen quiet small time ago
                        int trooperSeenOrder = curTroopIndex - seenDiff;
                        if (trooperSeenOrder < 0) trooperSeenOrder += maxTroops;

                        // moved away or killed
                        if (numLeftPlayers() <= 2) {
                            // definetely moved away (or player killed its own trooper?? quiet unlikely)
                            if (trooper.getType() == gself->getType()) {
                                playerInfo[(int)trooper.getPlayerId()].setAfterMe(FALSE);
                            } else if (trooper.getType() == troopOrder[trooperSeenOrder]) {
                                playerInfo[(int)trooper.getPlayerId()].setAfterMe(TRUE);
                            }
                        } else if (prevSubMove % maxTroops != currentSubMove % maxTroops) {
                            if (trooper.getHitpoints() >= 100) {
                                // most likely moved away
                                if (trooper.getType() == gself->getType()) {
                                    playerInfo[(int)trooper.getPlayerId()].setAfterMe(MOST_LIKELY_FALSE);
                                } else if (trooper.getType() == troopOrder[trooperSeenOrder]) {
                                    playerInfo[(int)trooper.getPlayerId()].setAfterMe(MOST_LIKELY_TRUE);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // determine mode
    Mode nextMode = TRAVEL;
    if (enemy || currentMode == COMBAT && currentSubMove - lastModeChange < maxTroops) {
        nextMode = COMBAT;
    } else if (attention || currentMode == COMBAT || currentMode == AFTER_COMBAT && currentSubMove -lastModeChange < attentionTime * maxTroops) {
        nextMode = AFTER_COMBAT;
    } else {
        nextMode = TRAVEL;
    }

    if (nextMode != currentMode) {
        std::cout << "switching to mode " << nextMode << std::endl;
        currentMode = nextMode;
        lastModeChange = currentSubMove;
    }

    if (!leaderFound) {
        std::cout << "Leader was killed" << std::endl;
        leader = -1;
    }
}

void findApproximatePositionOfPlayers() {
    {
        // first, check if commander knows something
        const vector<Player>& players = gworld->getPlayers();
        bool dataValid = false;
        for (int i = 0; i < (int)players.size(); i++) {
            int x = players[i].getApproximateX();
            int y = players[i].getApproximateY();
            playerInfo[(int)players[i].getId()].approximatePosition = Point(x,y);
            if (validPoint(Point(x,y))) {
                dataValid = true;
            }
        }

        if (dataValid) {
            // if some approximate positions valid and others are not, means that others are dead
            for (int i = 0; i < (int)players.size(); i++) {
                int x = players[i].getApproximateX();
                int y = players[i].getApproximateY();
                if (!validPoint(Point(x,y))) {
                    // all dead
                    for (int t = 0; t < maxTroops; t++) {
                        playerInfo[(int)players[i].getId()].setDead((TrooperType)t);
                    }
                }
            }
        }
    }

    // now try to determine position based on last shoots
    for (int p = 1; p < (int)playerInfo.size(); ++p) {
        PlayerInfo& pInfo = playerInfo[p];
        int x = 0;
        int y = 0;
        int numT = 0;
        for (int i = 0; i < (int)lastShooted.size(); i++) {
            if (currentSubMove - lastShooted[i].subMove >= 2*maxTroops) continue;
            if (validPoint(lastShooted[i].approxPositions[p])) {
                x += lastShooted[i].approxPositions[p].x;
                y += lastShooted[i].approxPositions[p].y;
                numT++;            
            }
        }

        if (numT > 0) {
            pInfo.approximatePosition = Point(x/numT, y/numT);
            if (!validPoint(pInfo.approximatePosition)) {
                SHOULD_NOT_HAPPEN;
            }
        }
    }

    // now try to determine position based on last seen troopers
    // most accurate method, overrides others
    for (int p = 1; p < (int)playerInfo.size(); ++p) {
        PlayerInfo& pInfo = playerInfo[p];
        int x = 0;
        int y = 0;
        int numT = 0;
        for (int i = 0; i < (int)lastSeen.size(); i++) {
            const Trooper& trooper = lastSeen[i].first;
            if (isDead(trooper)) continue;
            if (trooper.getPlayerId() != pInfo.getId()) continue;
            if (lastSeen[i].second < 0) continue;
            if (currentSubMove - lastSeen[i].second >= 2*maxTroops) continue;
            x += trooper.getX();
            y += trooper.getY();
            numT++;
        }

        if (numT > 0) {
            pInfo.approximatePosition = Point(x/numT, y/numT);
            if (!validPoint(pInfo.approximatePosition)) {
                SHOULD_NOT_HAPPEN;
            }
        }
    }

    // find nearest player ot me
    const vector<Player>& players = gworld->getPlayers();
    int nearestPlayer = -1;
    int minDistToPlayer = 1000;
    for (int i = 0; i < (int)players.size(); i++) {
        if (players[i].getId() != gself->getPlayerId()) {
            Point approxPos = playerInfo[(int)players[i].getId()].approximatePosition;
            if (validPoint(approxPos)) {
                Point nf = nearestFree(approxPos);
                randomTarget = false;
                const StepMap& stepMap = allStepMaps[nf.getX()][nf.getY()];
                int stepsToTarget = stepMap[gself->getX()][gself->getY()];
                if (stepsToTarget < minDistToPlayer) {
                    minDistToPlayer = stepsToTarget;
                    nearestPlayer = i;
                }
            }
        }
    }

    if (nearestPlayer != -1) {
        // attack him
        attackPlayerId = (int)players[nearestPlayer].getId();
    }
}

// probability that enemy is on the distance from his teammate
double distToProbNearTeammate[] = {
    20, 20, 20, 15., 5., 2., 1., 1., 0.5, 0.2
};

int distToProbNearTeammateSize = sizeof(distToProbNearTeammate) / sizeof(double);

TriBool isShootedThere(const Trooper& trooper) {
    for (int i = 0; i < (int)succeededHits.size(); i++) {
        const Hit& hit = succeededHits[i].first;
        if (hit.trooper.getX() == trooper.getX() && hit.trooper.getY() == trooper.getY()) {
            // shooted to this location and succeeded
            if (numTurnsSinceSubMove(trooper, succeededHits[i].second) == 0) {
                return TRUE;
            }
        }
    }

    for (int i = 0; i < (int)failedHits.size(); i++) {
        const Hit& hit = failedHits[i].first;
        if (hit.trooper.getX() == trooper.getX() && hit.trooper.getY() == trooper.getY()) {
            // shooted to this location and failed
            if (numTurnsSinceSubMove(trooper, failedHits[i].second) == 0) {
                return FALSE;
            }
        }
    }

    return PROBABLY;
}

void updateTrooperProbs() {
    for (int x = 0; x < (int)gworld->getWidth(); x++) {
        for (int y = 0; y < (int)gworld->getHeight(); y++) {
            trooperProbs[x][y].clear();
        }
    }
        
    for (int t = 0; t < (int)lastSeen.size(); t++) {
        const Trooper& trooper = lastSeen[t].first;
        SubMove subMove = lastSeen[t].second;

        if (isDead(trooper)) continue;

        // skip teammates
        if (trooper.isTeammate()) continue;

        double totalProb = 0.;

        double numTurns = numTurnsSinceLastSeen(lastSeen[t]);
        int numFullTurnsCeil = (int)ceil(numTurns);
        int numFullTurnsFloor = (int)floor(numTurns);

        if (numFullTurnsCeil == 0) {
            // didn't move since last seen, definetely know there he is
            trooperProbs[trooper.getX()][trooper.getY()].push_back(std::pair<double, Trooper>(1., trooper));
            continue;
        }

        int maxActionPointsPerTurn = trooper.getInitialActionPoints();
        if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT) maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();

        int wholeActionPointsCeil = maxActionPointsPerTurn * numFullTurnsCeil;
        int wholeActionPointsFloor = maxActionPointsPerTurn * numFullTurnsFloor;
        if (trooper.getStance() == PRONE) {
            // need to change to STANDING first
            wholeActionPointsCeil -= ggame->getStanceChangeCost() * 2;
            wholeActionPointsFloor -= ggame->getStanceChangeCost() * 2;
        }
        if (trooper.getStance() == KNEELING) {
            // need to change to STANDING first
            wholeActionPointsCeil -= ggame->getStanceChangeCost();
            wholeActionPointsFloor -= ggame->getStanceChangeCost();
        }

        int maxStepsCeil = wholeActionPointsCeil / ggame->getStandingMoveCost();
        int maxStepsFloor = wholeActionPointsFloor / ggame->getStandingMoveCost();

        const vector<vector<CellType> >& cells = gworld->getCells();
        const StepMap& stepMap = allStepMaps[trooper.getX()][trooper.getY()];

        // check there he can appear using his action points
        for (int x = 0; x < (int)gworld->getWidth(); x++) {
            for (int y = 0; y < (int)gworld->getHeight(); y++) {
                if (cells[x][y] != FREE) continue;
                int dist = stepMap[x][y];
                int stepsCeil = maxStepsCeil;
                int stepsFloor = maxStepsFloor;

                double probCoef = 0.;
                TrooperStance possibleStance = STANDING;

                for (int stance = STANDING; stance >= PRONE; stance--) {
                    bool skip = false;
                    bool found = false;

                    // check if this trooper shooted somebody
                    for (int l = 0; l < (int)lastShooted.size(); l++) {
                        LastShooted& ls = lastShooted[l];
                        bool possible = false;
                        for (int e = 0; e < (int)ls.possibleEnemies.size(); e++) {
                            if (ls.possibleEnemies[e].getPlayerId() == trooper.getPlayerId() &&
                                ls.possibleEnemies[e].getType() == trooper.getType()) {
                                found = true;
                                if (ls.possibleEnemies[e].getX() == x &&
                                    ls.possibleEnemies[e].getY() == y &&
                                    ls.possibleEnemies[e].getStance() >= stance) {
                                    possible = true;
                                    break;
                                }
                            }
                        }

                        if (!possible) {
                            skip = true;
                            break;
                        }
                    }

                    if (found && skip) continue;

                    if (inFog(x, y, (TrooperStance)stance, 
                        trooper.getType() == SNIPER ? currentFogSniper : currentFog)) {
                        // in fog now, check if was not in fog before
                        bool sawIt = false;
                        int maxIt = 2; // look to the past for 2 iterations
                        // find who saw this position last time
                        for (int j = 0; j < maxTroops*maxIt; j++) {
                            int tIndex = curTroopIndex - j;
                            int it = j / maxTroops;
                            while (tIndex < 0) tIndex += maxTroops;
                            if (it >= (int)lastFogs[tIndex].size()) {
                                break;
                            }
                            const Fog& thatFog = trooper.getType() == SNIPER ? lastFogsSniper[tIndex][it] : lastFogs[tIndex][it];
                            if (!inFog(x, y, (TrooperStance)stance, thatFog)) {
                                // he saw this position j submoves before
                                sawIt = true;
                                double numTurns = numTurnsSinceSubMove(trooper, currentSubMove - j);
                                if (numTurns == 0.) {
                                    break;
                                } else if (numTurns <= 1) {
                                    if (probCoef < 0.5) {
                                        probCoef = 0.5;
                                        possibleStance = (TrooperStance)stance;
                                    }
                                    break;
                                } else {
                                    if (probCoef < 1.) {
                                        probCoef = 1.;
                                        possibleStance = (TrooperStance)stance;
                                    }
                                    break;
                                }
                            }
                        }
                        if (!sawIt) {
                            // never saw this position, no restrictions
                            probCoef = 1.;
                            possibleStance = (TrooperStance)stance;
                            break;
                        }
                    }
                }

                // create new virtual trooper and place to position.
                TrooperStateDiff diff;
                diff.actionPoints = maxActionPointsPerTurn - trooper.getActionPoints();
                diff.x = x - trooper.getX();
                diff.y = y - trooper.getY();
                diff.stance = possibleStance - trooper.getStance();
                if (numTurnsSinceLastSeen(lastSeen[t]) > 4) diff.plusGrenade;
                Trooper virtualTrooper = newVirtualTrooper(trooper,diff);
                
                if (probCoef > 0.) {
                    stepsCeil -= (STANDING - possibleStance);
                    stepsFloor -= (STANDING - possibleStance);
                    if (dist <= stepsCeil) {
                        // enough steps to reach this point
                        double cellProb = 1.;
                        if (validPoint(playerInfo[(int)trooper.getPlayerId()].approximatePosition)) {
                            // first, try to use approximate position of player if known
                            probCoef = 1.;
                            int mDist = manhattanDistance(playerInfo[(int)trooper.getPlayerId()].approximatePosition, Point(x,y));
                            if (mDist < distToProbNearTeammateSize) {
                                cellProb = distToProbNearTeammate[mDist];
                            } else {
                                cellProb = distToProbNearTeammate[distToProbNearTeammateSize-1];
                            }
                        } else if (lastSeenEnemy < 3 * maxTroops) {
                            // if no, try to estimate by average speed
                            double maxSpeed = 5;
                            double averageSpeed = playerInfo[(int)trooper.getPlayerId()].averageSpeed;
                            double thisSpeedRatioCeil = (double)dist/stepsCeil;
                            double thisSpeedRatioFloor = (double)dist/stepsFloor;
                            double diff = min(fabs(thisSpeedRatioCeil * maxSpeed - averageSpeed),
                                fabs(thisSpeedRatioFloor * maxSpeed - averageSpeed));
                            if (diff < 0.5) {
                                cellProb = 10.;
                            } else if (diff < 1) {
                                cellProb = 8.;
                            } else if (diff < 1.5) {
                                cellProb = 5.;
                            } else {
                                cellProb = 1.;
                            }
                        } else {
                            // no information about player, assume they are somethere near me
                            if (squareDist(*gself, x, y) <= 12) {
                                cellProb = 5;
                            } else {
                                cellProb = 1;
                            }
                        }
                        cellProb *= probCoef;

                        if (trooper.getX() == x && trooper.getY() == y) {
                            // last seen in the same position
                            if (numTurns < 1) {
                                // 50/50 he is there
                                cellProb *= 10;
                            } else if (numTurns < 2) {
                                // probably still stay there
                                cellProb *= 3;
                            }

                            if (trooper.getType() == FIELD_MEDIC && numTurns < 2) {
                                int needHeal = trooper.getMaximalHitpoints() - trooper.getHitpoints();
                                int maxActionPointsPerTurn = trooper.getInitialActionPoints();
                                if (!playerInfo[(int)trooper.getPlayerId()].isDead(COMMANDER)) {
                                    maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();
                                }

                                int wholeActionPointsCeil = maxActionPointsPerTurn;

                                // Probably it was healed
                                if (trooper.isHoldingMedikit()) {
                                    needHeal -= ggame->getMedikitHealSelfBonusHitpoints();
                                    wholeActionPointsCeil -= ggame->getMedikitUseCost();
                                }

                                int healTime = (needHeal + ggame->getFieldMedicHealSelfBonusHitpoints() - 1) / ggame->getFieldMedicHealSelfBonusHitpoints() * ggame->getFieldMedicHealCost();
                                wholeActionPointsCeil -= healTime;

                                if (wholeActionPointsCeil < getMoveCost(trooper.getStance())) {
                                    // likely stay there and heal himself
                                    cellProb *= 5;
                                }
                            }
                        }

                        TriBool shootedThere = isShootedThere(virtualTrooper);
                        if (shootedThere == TRUE) {
                            cellProb *= 50;
                        } else if (shootedThere == FALSE) {
                            continue;
                        }

                        trooperProbs[x][y].push_back(std::pair<double, Trooper>(cellProb, virtualTrooper));
                        totalProb += cellProb;
                    }
                }
            }
        }

        // normalize probabilities
        for (int x = 0; x < (int)gworld->getWidth(); x++) {
            for (int y = 0; y < (int)gworld->getHeight(); y++) {
                if (trooperProbs[x][y].size() == 0) continue;
                const Trooper& that = trooperProbs[x][y].rbegin()->second;
                if (that.getPlayerId() == trooper.getPlayerId() &&
                    that.getType() == trooper.getType()) {
                    trooperProbs[x][y].rbegin()->first /= (double)totalProb;
                }
            }
        }
    }

    // normalize probabilities over troopers
    for (int x = 0; x < (int)gworld->getWidth(); x++) {
        for (int y = 0; y < (int)gworld->getHeight(); y++) {
            std::vector<std::pair<double, Trooper> >& probs = trooperProbs[x][y];
            if (probs.size() == 0) continue;

            double totalProb = 0;
            for (int i = 0; i < (int)probs.size(); i++) {
                if (probs[i].first > 1.) {
                    SHOULD_NOT_HAPPEN;
                    probs[i].first = 1.;
                }
                if (probs[i].first == 1.) {
                    // leave only this trooper
                    probs[0] = probs[i];
                    probs.resize(1);
                    totalProb = 1.;
                    break;
                }
                totalProb += probs[i].first;
            }

            if (totalProb > 1.) {
                for (int i = 0; i < (int)probs.size(); i++) {
                    probs[i].first /= totalProb;
                }
            }
        }
    }
}

bool isAttackAction(ActionType action) {
    switch (action)
    {
    case model::SHOOT:
    case model::THROW_GRENADE:
        return true;
    default:
        return false;
    }

}

bool complexComparison(const Target& target1, const Target& target2) {
    int scoreDiff = target1.score - target2.score;
    double scoreNextTurnDiff = target1.scoreNextTurn - target2.scoreNextTurn;
    double safetyDiff = target1.safety - target2.safety;
    double priorityDiff = target1.priority - target2.priority;

    // do not take into account priority for different types of targets
    if (isAttackAction(target1.action.actionType) != isAttackAction(target2.action.actionType)) priorityDiff = 0;

    int priorityCoef = 1;
    
    if (tactics == NORMAL) {
        priorityCoef = 2;
    }
    if (tactics == AGRESSIVE) {
        priorityCoef = 7;
    }
    if (tactics == RUSH) {
        priorityCoef = 15;
    }

    if (mapType == CHEESER) {
        // otherwise they are just staying as fools
        priorityCoef *= 2;
    }

    if (gworld->getMoveIndex() < 15 && gself->getActionPoints() >= 4 && currentMode == TRAVEL) {
        // be more active in the beginning
        priorityCoef = 20;
    }

    if (!isAttackAction(target1.action.actionType)) {
        if (gself->getType() == FIELD_MEDIC) {
            // careful if medic
            priorityCoef /= 4;
        }
        if (gself->getType() != leader) {
            // careful if not leader
            priorityCoef = priorityCoef * 3 / 4;
        }
    }
    
    if ((currentMode == TRAVEL || gtLastUpdated == -1) && 
        (gself->getType() == COMMANDER || gself->getType() == leader || gself->getType() == SCOUT) && 
        gself->getActionPoints() >= 6) {
        // berserk
        safetyDiff /= 3;
    }

    priorityDiff *= priorityCoef;

    // quiet safe and good score diff
    if (target1.safety >= 50 && (scoreDiff > 50)) return true;
    if (target2.safety >= 50 && (scoreDiff < -50)) return false;

    if (target1.safety >= 50 && safetyDiff >= -30 && (scoreDiff > 20)) return true;
    if (target2.safety >= 50 && safetyDiff <= 30 && (scoreDiff < -20)) return false;

    // important person
    bool important = gself->getType() == SCOUT || gself->getType() == SNIPER;
    // when somebody is killed all left are important
    if (numLeftTroopers((int)me->getId()) < maxTroops) important = true;

    if (target2.safety < 10 && target1.safety > 0 && safetyDiff >= 20 && (scoreDiff > -20 || important && scoreDiff > -50)) return true;
    if (target1.safety < 10 && target2.safety > 0 && safetyDiff <= -20 && (scoreDiff < 20 || important && scoreDiff < 50)) return false;

    if (target2.safety < 10 && target1.safety > -20 && target1.visibileProb < 0.5 && safetyDiff >= 20 && (scoreDiff > -20 || important && scoreDiff > -50)) return true;
    if (target1.safety < 10 && target2.safety > -20 && target2.visibileProb < 0.5 && safetyDiff <= -20 && (scoreDiff < 20 || important && scoreDiff < 50)) return false;

    // ignore priority if not safe
    if (target1.safety < 10 && target2.safety < 10 && !isAttackAction(target1.action.actionType)) priorityDiff = 0;

    if (scoreDiff + scoreNextTurnDiff + safetyDiff + priorityDiff > 50) return true;
    if (scoreDiff + scoreNextTurnDiff + safetyDiff + priorityDiff < -50) return false;

    if (target1.safety >= 80 && safetyDiff >= -20 && (scoreDiff + priorityDiff + scoreNextTurnDiff > 5)) return true;
    if (target2.safety >= 80 && safetyDiff <= 20 && (scoreDiff + priorityDiff + scoreNextTurnDiff < -5)) return false;

    if (target1.safety >= 50 && safetyDiff >= -30 && (scoreDiff + priorityDiff + scoreNextTurnDiff > 20)) return true;
    if (target2.safety >= 50 && safetyDiff <= 30 && (scoreDiff + priorityDiff + scoreNextTurnDiff < -20)) return false;

    if (target1.safety >= 50 && (scoreDiff + priorityDiff + scoreNextTurnDiff > 60)) return true;
    if (target2.safety >= 50 && (scoreDiff + priorityDiff + scoreNextTurnDiff < -60)) return false;

    if (scoreDiff + safetyDiff + priorityDiff + scoreNextTurnDiff > 0) return true;
    if (scoreDiff + safetyDiff + priorityDiff + scoreNextTurnDiff < 0) return false;

    if (scoreDiff + safetyDiff + priorityDiff > 0) return true;
    if (scoreDiff + safetyDiff + priorityDiff < 0) return false;

    if (priorityDiff > 0) return true;
    if (priorityDiff < 0) return false;

    // very unlikely but for reproducibility
    if (target1.id < target2.id) return true;
    if (target1.id > target2.id) return false;

    return false;
}

bool compareActions(const Action& action1, const Action& action2) {
    if (action1.troopersKilled > action2.troopersKilled) return true;
    if (action1.troopersKilled < action2.troopersKilled) return false;

    double damageDiff = action1.damage - action2.damage;
    int priorityDiff = action1.priority - action2.priority;

    if (damageDiff > 30) return true;
    if (damageDiff < -30) return false;

    if (action1.actionType == USE_MEDIKIT) damageDiff -= 15;
    if (action2.actionType == USE_MEDIKIT) damageDiff += 15;
    if (action1.actionType == THROW_GRENADE) damageDiff -= 15;
    if (action2.actionType == THROW_GRENADE) damageDiff += 15;

    if (damageDiff + 2 * priorityDiff > 0) return true;
    if (damageDiff + 2 * priorityDiff < 0) return false;

    return false;
}

bool visibleForEnemies(const Trooper& trooper) {
    // process enemies
    for (size_t ee = 0; ee < lastSeen.size(); ++ee) { 
        const Trooper& enemy = lastSeen[ee].first;

        if (isDead(enemy)) continue;
        if (stillThere(lastSeen[ee]) < MOST_LIKELY_TRUE) continue;

        double visionRange = enemy.getVisionRange();
        if (trooper.getType() == SNIPER && enemy.getType() != SCOUT) {
            if (trooper.getStance() == KNEELING) visionRange -= 0.5;
            if (trooper.getStance() == PRONE) visionRange -= 1.;
        }

        if (!enemy.isTeammate() &&
            gworld->isVisible(visionRange,  
            enemy.getX(), enemy.getY(), STANDING /* can easily stand up even if seen as prone or kneeling */,        
            trooper.getX(), trooper.getY(), trooper.getStance())) {
            return true;
        }
    }
    return false;
}

int getActionPriority(int damage, const Trooper& trooper, bool killed) {
    if (damage == 0) return 0;
    
    int turnsBeforeOurs = 0;
    const vector<Trooper>& troopers = gworld->getTroopers();
    for (int tt = 0; tt < (int)troopers.size(); tt++) {
        const Trooper& teammate = troopers[tt];
        if (teammate.isTeammate()) {
            TriBool later = turnsLater(trooper, teammate);
            if (later == FALSE) {
                turnsBeforeOurs += 2;
            } else if (later == PROBABLY) {
                turnsBeforeOurs += 1;
            }
        }
    }

    int priotityBonus  = 0;

    if (trooper.getType() == FIELD_MEDIC) priotityBonus += 10;
    if (trooper.getType() == COMMANDER) priotityBonus += 5;
    if (trooper.getType() == SNIPER) {
        if (mapType == CHEESER) {
            // sniper is useless on this map
            priotityBonus -= 5;
        } else {
            priotityBonus += 10;
        }
    }
    if (trooper.getType() == SCOUT) priotityBonus += 15;
    priotityBonus += turnsBeforeOurs * 3;

    if (killed) {
        priotityBonus *= 2;
    } else {
        // scale to actual damage
        priotityBonus = priotityBonus * damage / trooper.getHitpoints();
    }

    return priotityBonus;
}

int compactnessSafetyPenalty(int diff, bool leader) {
    int safety = 0;

    // whether to apply soft restrictions
    bool soft = currentMode == TRAVEL || mapType == CHEESER;

    if (leader) {
        if (diff > (soft ? 8 : 6)) {
            safety -= diff * (soft ? 4 : 7);
        }
    } else {
        if (diff > (soft ? 5 : 3)) {
            safety -= diff * (soft ? 4 : 7);
        }
    }

    if (currentMode == COMBAT) safety /= 2;
    
    return safety;
}

int computeMaxFireDamageNoMove(const Trooper& trooper, const Position& trooperPosition, Position targetPosition, int actionPoints) {
    double shootingRange = trooper.getShootingRange();
    if (trooper.getType() == SNIPER) {
        // count sniper range bonus
        shootingRange -= trooperPosition.stance - trooper.getStance();
    }
    bool canShoot = gworld->isVisible(shootingRange, 
        trooperPosition.getX(), trooperPosition.getY(), trooperPosition.getStance(), 
        targetPosition.getX(), targetPosition.getY(), targetPosition.getStance());

    if (canShoot) {
        int numShots = actionPoints / trooper.getShootCost();
        int singleDamage = trooper.getDamage(trooperPosition.getStance());
        int totalDamage = singleDamage * numShots;
        return totalDamage;
    }
    return 0;
}

int computeMaxDamageNoMove(const Trooper& trooper, const Position& trooperPosition, const Position& targetPosition, int actionPoints) {
    int fireDamage = computeMaxFireDamageNoMove(trooper, trooperPosition, targetPosition, actionPoints);

    bool grenade = trooper.isHoldingGrenade();

    if (grenade && actionPoints >= ggame->getGrenadeThrowCost()) {
        double throwDist = ggame->getGrenadeThrowRange();
        Point throwPoint(targetPosition);
                
        int grenadeDamage = 0;
        if (squareDist(trooperPosition, targetPosition) <= throwDist * throwDist) {
            grenadeDamage = ggame->getGrenadeDirectDamage();
            if (maxTroops == 5) {
                // likely shoot also nearby
                grenadeDamage += ggame->getGrenadeCollateralDamage() / 2;
            } else if (maxTroops == 4) {
                // likely shoot also nearby
                grenadeDamage += ggame->getGrenadeCollateralDamage() / 3;
            }
        } else if (
            validPoint(Point(targetPosition) + Point(-1,0)) &&
            squareDist(trooperPosition, Point(targetPosition) + Point(-1,0)) <= throwDist * throwDist ||
            validPoint(Point(targetPosition) + Point(1,0)) &&
            squareDist(trooperPosition, Point(targetPosition) + Point(1,0)) <= throwDist * throwDist ||
            validPoint(Point(targetPosition) + Point(0,1)) &&
            squareDist(trooperPosition, Point(targetPosition) + Point(0,1)) <= throwDist * throwDist ||
            validPoint(Point(targetPosition) + Point(0,-1)) &&
            squareDist(trooperPosition, Point(targetPosition) + Point(0,-1)) <= throwDist * throwDist
            ) {
            grenadeDamage = ggame->getGrenadeCollateralDamage();            
        }

        if (mapType == CHEESER) {
            // otherwise they don't want to move anythere
            grenadeDamage /= 2;
        }

        if (grenadeDamage > 0) {
            int leftFireDamage = computeMaxFireDamageNoMove(trooper, trooperPosition, targetPosition, actionPoints - ggame->getGrenadeThrowCost());
            return std::max(grenadeDamage + leftFireDamage, fireDamage);
        }
    }
    return fireDamage;
}

int computeMaxDamage(const Trooper& trooper, Position targetPosition, Position* firePosition = 0, bool veryRoughEstimation = false) {
    // compute its stepmap
    int maxActionPoints = trooper.getInitialActionPoints();
    if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT &&
        playerInfo[(int)trooper.getPlayerId()].isDead(COMMANDER) != true) {
        maxActionPoints += ggame->getCommanderAuraBonusActionPoints();
    }

    if (trooper.isHoldingFieldRation()) maxActionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();

    // at least he should fire or throw a grenage
    int maxSteps = (maxActionPoints - std::min(trooper.getShootCost(), ggame->getGrenadeThrowCost())) /
        ggame->getStandingMoveCost();

    double shootingRange = trooper.getShootingRange();
    if (trooper.getType() == SNIPER) {
        shootingRange += 2;
    }

    if (squareDist(trooper, targetPosition) > (shootingRange + maxSteps) * (shootingRange + maxSteps)) {
        // can skip it
        return 0;
    }

    if (veryRoughEstimation) {
        return computeMaxDamageNoMove(trooper, trooper, targetPosition, maxActionPoints);
    }

    const StepMap& stepMap = allStepMaps[trooper.getX()][trooper.getY()];

    int maxDamage = 0;
    int minX = trooper.getX() - maxSteps;
    if (minX < 0) minX = 0;
    int maxX = trooper.getX() + maxSteps; 
    if (maxX >= gworld->getWidth()) maxX = gworld->getWidth()-1;
    int minY = trooper.getY() - maxSteps;
    if (minY < 0) minY = 0;
    int maxY = trooper.getY() + maxSteps; 
    if (maxY >= gworld->getHeight()) maxY = gworld->getHeight()-1;

    for (int x = minX; x <= maxX; x++) {
        for (int y = minY; y <= maxY; y++) {
            if (stepMap[x][y] >= 0 && stepMap[x][y] <= maxSteps) {
                // candidates for move
                for (int i = 0; i < _TROOPER_STANCE_COUNT_; i++) {
                    TrooperStance stance = (TrooperStance)(trooper.getStance() + i);
                    if (stance >= _TROOPER_STANCE_COUNT_) stance = (TrooperStance)(stance - _TROOPER_STANCE_COUNT_);
                    Position position(Point(x,y), stance);
                    int moveCost = findFastestMove(stepMap, trooper.getStance(), position);
                    int timeForAction = maxActionPoints - moveCost;
                    if (timeForAction < std::min(trooper.getShootCost(), ggame->getGrenadeThrowCost())) continue;

                    int mDamage = computeMaxDamageNoMove(trooper, Position(x, y, stance), targetPosition, maxActionPoints - moveCost);
                    if (mDamage > maxDamage) {
                        maxDamage = mDamage;
                        if (firePosition) *firePosition = position;
                    }
                }
            }
        }
    }

    return maxDamage;
}

bool checkVisibilityNoMove(const Trooper& trooper, const Position& trooperPosition, const Position& targetPosition, bool sniper) {
    double visionRange = trooper.getVisionRange();
    if (sniper && trooper.getType() != SCOUT) {
        if (targetPosition.getStance() == KNEELING) visionRange -= 0.5;
        if (targetPosition.getStance() == PRONE) visionRange -= 1.;
    }
    return gworld->isVisible(visionRange, 
        trooperPosition.getX(), trooperPosition.getY(), trooperPosition.getStance(), 
        targetPosition.getX(), targetPosition.getY(), targetPosition.getStance());
}

// compute probability that trooper will see target position during his move
double checkVisibility(const Trooper& trooper, Position targetPosition, bool sniper, Position* seePosition = 0, bool veryRough = false) {
    int maxActionPoints = trooper.getInitialActionPoints();
    if (trooper.getType() != COMMANDER && trooper.getType() != SCOUT &&
        playerInfo[(int)trooper.getPlayerId()].isDead(COMMANDER) != true) {
        maxActionPoints += ggame->getCommanderAuraBonusActionPoints();
    }

    if (trooper.isHoldingFieldRation()) maxActionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();

    int maxSteps = maxActionPoints / ggame->getStandingMoveCost();

    // unlikely he will go to whole action points, at least 2 steps for hiding
    maxSteps -= 2;

    if (squareDist(trooper, targetPosition) > (trooper.getVisionRange() + maxSteps) * (trooper.getVisionRange() + maxSteps)) {
        // can skip it
        return 0.;
    }

    if (veryRough) return 1.;

    const StepMap& stepMap = allStepMaps[trooper.getX()][trooper.getY()];

    int minX = trooper.getX() - maxSteps;
    if (minX < 0) minX = 0;
    int maxX = trooper.getX() + maxSteps; 
    if (maxX >= gworld->getWidth()) maxX = gworld->getWidth()-1;
    int minY = trooper.getY() - maxSteps;
    if (minY < 0) minY = 0;
    int maxY = trooper.getY() + maxSteps; 
    if (maxY >= gworld->getHeight()) maxY = gworld->getHeight()-1;

    int minActionPoints = 20;

    for (int x = minX; x <= maxX; x++) {
        for (int y = minY; y <= maxY; y++) {
            if (stepMap[x][y] >= 0 && stepMap[x][y] <= maxSteps) {
                // candidates for move
                for (int i = 0; i < _TROOPER_STANCE_COUNT_; i++) {
                    TrooperStance stance = (TrooperStance)((trooper.getStance() + i) % _TROOPER_STANCE_COUNT_);
                    Position position(Point(x,y), stance);
                    int moveCost = findFastestMove(stepMap, trooper.getStance(), position);
                    if (maxActionPoints < moveCost) continue;

                    bool visible = checkVisibilityNoMove(trooper, Position(x, y, stance), targetPosition, sniper);
                    if (visible) {
                        if (moveCost < minActionPoints) {
                            minActionPoints = moveCost;
                            if (seePosition) *seePosition = position;
                        }
                    }
                }
            }
        }
    }

    if (minActionPoints == 20) return 0.;

    // spent less than a half of his points. Quiet likely
    if (minActionPoints <= maxActionPoints/2) return 1.;

    if (mapType == CHEESER) {
        return 0.3;
    } else {
        return 0.5;
    }
}

// caches
std::vector<pair<Position, double> > damageToPosition;
std::vector<pair<Position, double> > damageToPosition1;
std::vector<pair<Position, double> > damageFromPosition;
std::vector<pair<Position, double> > positionVisibilities;

double computeDamageByTrooper(const Trooper& candidate) {
    // look up cache first
    for (int i = 0; i < (int)damageFromPosition.size(); i++) {
        if (Position(candidate) == damageFromPosition[i].first) {
            return damageFromPosition[i].second;
        }
    }

    double maxDamageNextTurn = 0;

    for (int x = 0; x < gworld->getWidth(); x++) {
        for (int y = 0; y < gworld->getHeight(); y++) {
            const std::vector<std::pair<double, Trooper> >& probs = trooperProbs[x][y];
            int maxStance = PRONE;
            double totalProb = 0.;
            for (int i = 0; i < (int)probs.size(); i++) {
                if (probs[i].first > 0.01) {
                    totalProb += probs[i].first;
                    if (probs[i].second.getStance() > maxStance) maxStance = probs[i].second.getStance();
                }
            }
            
            if (totalProb > 0) {
                maxDamageNextTurn += (totalProb * computeMaxDamage(candidate, Position(x, y, (TrooperStance)maxStance)));
            }

            if (gworld->getCells()[x][y] == FREE) {
                for (int i = 0; i < (int)lastSeen.size(); i++) {
                    if (lastSeen[i].first.isTeammate()) continue;
                    if (isDead(lastSeen[i].first)) continue;
                    if (currentSubMove - lastSeen[i].second <= maxTroops) {
                        if (manhattanDistance(lastSeen[i].first, Point(x,y)) < 5 &&
                            (gworld->isVisible(candidate.getShootingRange(), 
                                candidate.getX(), candidate.getY(), candidate.getStance(), 
                                x, y, candidate.getStance()) ||
                                candidate.isHoldingGrenade() && squareDist(candidate, x, y) <= ggame->getGrenadeThrowRange() * ggame->getGrenadeThrowRange())) {
                            maxDamageNextTurn += maxTroops;
                        } 
                    }
                }
            }
        }
    }

    damageFromPosition.push_back(std::pair<Position, double>(Position(candidate), maxDamageNextTurn));

    return maxDamageNextTurn;
}

double computeDamageToTrooper(const Trooper& trooper, bool secondaryTarget = true, bool checkTurnsLater = false) {
    if (checkTurnsLater == false && secondaryTarget == true) {
        // look up cache first
        for (int i = 0; i < (int)damageToPosition.size(); i++) {
            if (Position(trooper) == damageToPosition[i].first) {
                return damageToPosition[i].second;
            }
        }
    } else {
        // look up cache first
        for (int i = 0; i < (int)damageToPosition1.size(); i++) {
            if (Position(trooper) == damageToPosition1[i].first) {
                return damageToPosition1[i].second;
            }
        }
    }

    const vector<Trooper>& troopers = gworld->getTroopers();
    
    double totalDamage = 0.;

    int minX = trooper.getX() - 13 /* max move + shoot range */;
    if (minX < 0) minX = 0;
    int maxX = trooper.getX() + 13;
    if (maxX > gworld->getWidth() - 1) maxX = gworld->getWidth() - 1;
    int minY = trooper.getY() - 13;
    if (minY < 0) minY = 0;
    int maxY = trooper.getY() + 13;
    if (maxY > gworld->getHeight() - 1) maxY = gworld->getHeight() - 1;
    for (int x = minX; x <= maxX; x++) {
        for (int y = minY; y <= maxY; y++) {
            const std::vector<std::pair<double, Trooper> >& probs = trooperProbs[x][y];
            for (int i = 0; i < (int)probs.size(); i++) {
                double prob = probs[i].first;
                const Trooper& enemy = probs[i].second;

                if (enemy.isTeammate()) {
                    SHOULD_NOT_HAPPEN;
                    continue;
                }

                if (checkTurnsLater && turnsLater(enemy, trooper) == TRUE) continue;

                if (prob < 0.001) continue;

                if (prob < 0.01) {
                    int damage = computeMaxDamage(enemy, trooper, 0, true);
                    bool critical = (damage >= (trooper.getHitpoints() / 2));
                    if (critical) {
                        if (mapType == CHEESER) {
                            if (prob < 0.02) prob = 0.02;
                        } else {
                            prob *= 3;
                        }
                    }
                    if (prob >= 1.) prob = 1.;
                    totalDamage += damage * prob;
                    continue;
                }

                {
                    // more complex and accurate estimation
                    Position firePosition(enemy);
                    int maxDamage = computeMaxDamage(enemy, trooper, &firePosition);

                    if (maxDamage > 0) {
//                      std::cout << enemy << " can hit " << maxDamage << " through " << firePosition << std::endl;

                        {
                            int numTeammates = 0;
                            for (size_t tt = 0; tt < troopers.size(); ++tt) {
                                Trooper teammate = troopers.at(tt);
                                if (teammate.isTeammate() &&
                                    teammate.getType() != trooper.getType()) {
                                    if (gworld->isVisible(teammate.getShootingRange(), teammate.getX(), teammate.getY(), teammate.getStance(),
                                        enemy.getX(), enemy.getY(), PRONE)) {
                                        bool found = false;
                                        const LastSeen& ls = getLastSeen((int)enemy.getPlayerId(), enemy.getType(), &found);
                                        if (!gworld->isVisible(teammate.getShootingRange(), teammate.getX(), teammate.getY(), teammate.getStance(),
                                            ls.first.getX(), ls.first.getY(), PRONE)) {
                                            // was inshootable but became shootable. Quiet unlikely
                                            maxDamage = maxDamage * 3 / 4;    
                                            numTeammates++;
                                            if (numTeammates >= 2) break;
                                        }
                                    }
                                }
                            }
                        }

                        int maxDamageToOthers = 0;
                        
                        if (secondaryTarget) {
                            for (size_t tt = 0; tt < troopers.size(); ++tt) {
                                Trooper teammate = troopers.at(tt);
                                if (teammate.isTeammate() &&
                                    teammate.getType() != trooper.getType()) {
                                    if (visibleForEnemies(teammate) && 
                                        turnsLater(enemy, teammate) == FALSE) {
                                        int damageToTeammate = computeMaxDamage(enemy, teammate);
                                        if (damageToTeammate > maxDamageToOthers) {
                                            maxDamageToOthers = damageToTeammate;
                                        }
                                    }
                                }
                            }
                        }

                        if (maxDamage > maxDamageToOthers * 2 || maxDamage >= trooper.getHitpoints() - 20) {
                            bool critical = (maxDamage >= (trooper.getHitpoints() / 2));
                            if (critical && prob < 0.4) {
                                if (mapType == CHEESER) {
                                    if (prob < 0.05) prob = 0.05;
                                } else {
                                    prob *= 2;
                                }
                            }
                            if (prob >= 1.) prob = 1.;
                            totalDamage += maxDamage * prob;
                        }
                    }
                }
            }
        }
    }

    if (checkTurnsLater == false && secondaryTarget == true) {
        damageToPosition.push_back(std::pair<Position, double>(Position(trooper), totalDamage));
    } else {
        damageToPosition1.push_back(std::pair<Position, double>(Position(trooper), totalDamage));
    }
    return totalDamage;
}

double getTrooperVisibility(const Trooper& trooper) {
    for (int i = 0; i < (int)positionVisibilities.size(); i++) {
        if (Position(trooper) == positionVisibilities[i].first) {
            return positionVisibilities[i].second;
        }
    }
    
    //const vector<Trooper>& troopers = gworld->getTroopers();
    double invisProb = 1.;

    int minX = trooper.getX() - 13 /* max move - 2 + vision range */;
    if (minX < 0) minX = 0;
    int maxX = trooper.getX() + 13;
    if (maxX > gworld->getWidth() - 1) maxX = gworld->getWidth() - 1;
    int minY = trooper.getY() - 13;
    if (minY < 0) minY = 0;
    int maxY = trooper.getY() + 13;
    if (maxY > gworld->getHeight() - 1) maxY = gworld->getHeight() - 1;
    for (int x = minX; x <= maxX; x++) {
        for (int y = minY; y <= maxY; y++) {
            const std::vector<std::pair<double, Trooper> >& probs = trooperProbs[x][y];
            for (int i = 0; i < (int)probs.size(); i++) {
                double prob = probs[i].first;
                const Trooper& enemy = probs[i].second;
                if (prob < 0.001) continue;

                if (enemy.isTeammate()) {
                    SHOULD_NOT_HAPPEN;
                    continue;
                }
                {
                    Position seePosition(enemy);
                    double seeProb = checkVisibility(enemy, trooper, trooper.getType() == SNIPER, &seePosition,  prob < 0.005);
                    
                    if (seeProb > 0) {
                        invisProb *= (1. - prob * seeProb);
                    }
                }
            }
        }
    }
    
    positionVisibilities.push_back(std::pair<Position, double>(Position(trooper), 1-invisProb));
    
    return 1-invisProb;
}

Action& getAction(std::vector<Action>& actions, int x, int y, ActionType actiontype) {
    for (int i = 0; i < (int)actions.size(); i++) {
        Action& action = actions[i];
        if (action.actionType == actiontype && action.x == x && action.y == y) {
            return action;
        }
    }
    Action newAction;
    newAction.actionType = actiontype;
    newAction.x = x;
    newAction.y = y;
    actions.push_back(newAction);
    return *actions.rbegin();
}

// cache best actions for each position and number of action points
vector<std::pair<std::pair<Position, int>, Action> > bestActions;

Action findBestAction(const Trooper& candidate, int actionPoints) {
    for (int i = 0; i < (int)bestActions.size(); i++) {
        if (Position(candidate) == bestActions[i].first.first &&
            actionPoints == bestActions[i].first.second) {
            return bestActions[i].second;
        }
    }

    // insert default empty action
    vector<Action> actions(1);
    actions[0].actionType = END_TURN;
    actions[0].x = candidate.getX();
    actions[0].y = candidate.getY();

    if (candidate.getType() == COMMANDER && actionPoints >= ggame->getCommanderRequestEnemyDispositionCost()) {
        // for commander use request action as deafult
        actions[0].actionType = REQUEST_ENEMY_DISPOSITION;
        actions[0].priority += currentSubMove - gtLastUpdated;
        if (tactics == AGRESSIVE) actions[0].priority *= 2;
        if (tactics == RUSH) actions[0].priority *= 4;
    }

    if (actionPoints > 0) {
        // go through teammates first, probably heal them
        for (size_t i = 0; i < lastSeen.size(); ++i) { 
            const Trooper& trooper = lastSeen[i].first;
            if (isDead(trooper)) continue;

            TriBool there = stillThere(lastSeen[i]);
            if (there < MOST_LIKELY_TRUE) continue;

            if (trooper.isTeammate()) {
                if (squareDist(candidate, trooper) <= 1) {
                    // right near me or me
                    int needToHeal = trooper.getMaximalHitpoints() - trooper.getHitpoints();

                    double canDamageHim = computeDamageToTrooper(trooper, false, true);
                    
                    if (needToHeal > 0) {
                        if (candidate.getType() == FIELD_MEDIC) {
                            int numHeals = actionPoints / ggame->getFieldMedicHealCost();
                            if (numHeals > 0) {
                                Action& action = getAction(actions, trooper.getX(), trooper.getY(), HEAL);
                                int singleHeal = (candidate.getType() == trooper.getType()) ? ggame->getFieldMedicHealSelfBonusHitpoints() : ggame->getFieldMedicHealBonusHitpoints();
                                int totalHeal = singleHeal * numHeals;
                                if (totalHeal >= needToHeal) {
                                    numHeals = (needToHeal + singleHeal - 1) / singleHeal;
                                    action.damage += needToHeal;
                                } else {
                                    action.damage += totalHeal;
                                }

                                if (trooper.getHitpoints() - canDamageHim <= 0) {
                                    // can die if not healed
                                    action.damage *= 2;

                                    if (trooper.getHitpoints() + totalHeal - canDamageHim > 0) {
                                        // will survive after our heal
                                        action.damage += 100;
                                    }
                                }

                                action.actionPoints = numHeals * ggame->getFieldMedicHealCost();
                            }
                        }

                        if (candidate.isHoldingMedikit() && (ggame->getMedikitUseCost() <= actionPoints)) {
                            int singleHeal = (candidate.getType() == trooper.getType()) ? ggame->getMedikitHealSelfBonusHitpoints() : ggame->getMedikitBonusHitpoints();
                            Action& action = getAction(actions, trooper.getX(), trooper.getY(), USE_MEDIKIT);
                            if (singleHeal >= needToHeal) {
                                action.damage += needToHeal;
                            } else {
                                action.damage += singleHeal;
                            }

                            if (trooper.getHitpoints() - canDamageHim <= 0) {
                                // can die if not healed
                                action.damage *= 2;

                                if (trooper.getHitpoints() + singleHeal - canDamageHim > 0) {
                                    // will survive after our heal
                                    action.damage += 100;
                                }
                            }

                            action.actionPoints = ggame->getMedikitUseCost();
                        }
                    }
                } 
            } 
        }

        // then, go through all points on the map and try to shoot there
        for (int x = 0; x < gworld->getWidth(); x++) {
            for (int y = 0; y < gworld->getHeight(); y++) {

                int canShootStance = _TROOPER_STANCE_COUNT_;
                
                for (int stance = 0; stance < _TROOPER_STANCE_COUNT_; stance++) {
                    if (gworld->isVisible(candidate.getShootingRange(), 
                        candidate.getX(), candidate.getY(), candidate.getStance(), 
                        x, y, (TrooperStance)stance)) {
                        canShootStance = stance;
                        break;
                    }
                }

                double grenageProb = 0;
                double shootProb = 0;
                double maxProbGrenade = 0;
                double maxProbShoot = 0;
                int maxPGrenade = 0;
                int maxPShoot = 0;

                // compute probability that will hit somebody with grenade or shoot
                for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
                    if (maxProbGrenade < trooperProbs[x][y][p].first) {
                        maxProbGrenade = trooperProbs[x][y][p].first;
                        maxPGrenade = p;
                    }
                    grenageProb += trooperProbs[x][y][p].first;

                    if (trooperProbs[x][y][p].second.getStance() >= canShootStance) {
                        if (maxProbShoot < trooperProbs[x][y][p].first) {
                            maxProbShoot = trooperProbs[x][y][p].first;
                            maxPShoot = p;
                        }
                        shootProb += trooperProbs[x][y][p].first;
                    }
                }

                if (shootProb > 1.) shootProb = 1.;
                if (grenageProb > 1.) grenageProb = 1.;

                double throwDist = ggame->getGrenadeThrowRange();

                if (candidate.isHoldingGrenade() && ggame->getGrenadeThrowCost() <= actionPoints && grenageProb >= 0.1 &&
                    squareDist(candidate, x, y) <= (throwDist+1) * (throwDist+1)) {

                    const Trooper& trooper = trooperProbs[x][y][maxPGrenade].second;
                
                    bool found;
                    LastSeen& ls = getLastSeen((int)trooper.getPlayerId(), trooper.getType(), &found);
                    if (!found) continue;

                    // check how much damage other teammates can do
                    int teammatesCanHelp = 0;

                    const vector<Trooper>& troopers = gworld->getTroopers();
                    if (maxProbGrenade == 1.) {
                        for (int t = 0; t < (int)troopers.size(); t++) {
                            const Trooper& teammate = troopers[t];
                            if (!teammate.isTeammate()) continue;
                            if (teammate.getType() == candidate.getType()) continue;
                            if (turnsLater(trooper, teammate) == TRUE) {
                                teammatesCanHelp += computeMaxDamage(teammate, trooper);
                            }
                        }
                    }

                    int possibleHitPoints = trooper.getHitpoints();
                    int maximalHitPoints = trooper.getMaximalHitpoints();
                    if (possibleHitPoints > maximalHitPoints) {
                        // for soldier
                        maximalHitPoints = possibleHitPoints;
                    }
                
                    // loop over enemy teammates and check if they can heal him
                    for (int et = 0; et < (int)lastSeen.size(); et++) {
                        const Trooper& hisTeammate = lastSeen[et].first;
                        if (hisTeammate.getPlayerId() != trooper.getPlayerId()) continue;
                        if (isDead(hisTeammate)) continue;
                        double numTurns = numTurnsSinceSubMove(hisTeammate, ls.second);
                        
                        if (numTurns > 0) {
                            int dist = stepDistance(hisTeammate, trooper) - 1; // should be in near point
                            int numTurnsCeil = (int)ceil(numTurns);
                            int maxActionPointsPerTurn = hisTeammate.getInitialActionPoints();
                            if (hisTeammate.getType() != COMMANDER && hisTeammate.getType() != SCOUT) maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();

                            int wholeActionPointsCeil = maxActionPointsPerTurn * numTurnsCeil;

                            wholeActionPointsCeil -= dist * ggame->getStandingMoveCost();

                            if (dist > 0) wholeActionPointsCeil -= (STANDING - hisTeammate.getStance()) * ggame->getStanceChangeCost();

                            if (wholeActionPointsCeil > 0) {
                                // Probably it was healed
                                if (hisTeammate.isHoldingMedikit() && wholeActionPointsCeil >= ggame->getMedikitUseCost()) {
                                    possibleHitPoints += ggame->getMedikitBonusHitpoints();
                                    wholeActionPointsCeil -= ggame->getMedikitUseCost();
                                }

                                if (hisTeammate.getType() == FIELD_MEDIC) {
                                    possibleHitPoints += wholeActionPointsCeil / ggame->getFieldMedicHealCost() * ggame->getFieldMedicHealBonusHitpoints();
                                }
                            }
                        }
                    }

                    if (possibleHitPoints > maximalHitPoints) possibleHitPoints = maximalHitPoints;
        
                    // probably can hit them with grenade?

                    Point throwPoint(trooper);
                
                    if (squareDist(candidate, throwPoint) <= throwDist * throwDist) {
                        bool killed = false;
                        Action& action= getAction(actions, throwPoint.getX(), throwPoint.getY(), THROW_GRENADE);
                        int damage = ggame->getGrenadeDirectDamage();
                        if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
                            damage = trooper.getHitpoints();
                            action.troopersKilled++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
                            if (trooper.getHitpoints() <= damage) {
                                damage = trooper.getHitpoints();
                            }
                            action.troopersKilledLater++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
                            // will kill if not healed
                            damage = trooper.getHitpoints();
                            action.troopersKilledLater++;
                            killed = true;
                        }
                        action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
                    
                        action.damage += damage * grenageProb;
                        action.actionPoints = ggame->getGrenadeThrowCost();
                        action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
                    }

                    Point nearPoint;

                    // throw to neighbour points
                    nearPoint = throwPoint + Point(1,0);
                    if (validPoint(nearPoint) &&
                        squareDist(candidate, nearPoint) <= throwDist * throwDist) {
                        bool killed = false;
                        Action& action= getAction(actions, nearPoint.getX(), nearPoint.getY(), THROW_GRENADE);
                        int damage = ggame->getGrenadeCollateralDamage();
                        if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
                            damage = trooper.getHitpoints();
                            action.troopersKilled++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
                            if (trooper.getHitpoints() <= damage) {
                                damage = trooper.getHitpoints();
                            }
                            action.troopersKilledLater++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
                            // will kill if not healed
                            damage = trooper.getHitpoints();
                            action.troopersKilledLater++;
                            killed = true;
                        }
                        action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
                    
                        action.damage += damage * grenageProb;
                        action.actionPoints = ggame->getGrenadeThrowCost();
                        action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
                    }
                    nearPoint = throwPoint + Point(-1,0);
                    if (validPoint(nearPoint) &&
                        squareDist(candidate, nearPoint) <= throwDist * throwDist) {
                        bool killed = false;
                        Action& action= getAction(actions, nearPoint.getX(), nearPoint.getY(), THROW_GRENADE);
                        int damage = ggame->getGrenadeCollateralDamage();
                        if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
                            damage = trooper.getHitpoints();
                            action.troopersKilled++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
                            if (trooper.getHitpoints() <= damage) {
                                damage = trooper.getHitpoints();
                            }
                            action.troopersKilledLater++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
                            // will kill if not healed
                            damage = trooper.getHitpoints();
                            action.troopersKilledLater++;
                            killed = true;
                        }
                        action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
                    
                        action.damage += damage * grenageProb;
                        action.actionPoints = ggame->getGrenadeThrowCost();
                        action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
                    }
                    nearPoint = throwPoint + Point(0,1);
                    if (validPoint(nearPoint) &&
                        squareDist(candidate, nearPoint) <= throwDist * throwDist) {
                        bool killed = false;
                        Action& action= getAction(actions, nearPoint.getX(), nearPoint.getY(), THROW_GRENADE);
                        int damage = ggame->getGrenadeCollateralDamage();
                        if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
                            damage = trooper.getHitpoints();
                            action.troopersKilled++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
                            if (trooper.getHitpoints() <= damage) {
                                damage = trooper.getHitpoints();
                            }
                            action.troopersKilledLater++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
                            // will kill if not healed
                            damage = trooper.getHitpoints();
                            action.troopersKilledLater++;
                            killed = true;
                        }
                        action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
                    
                        action.damage += damage * grenageProb;
                        action.actionPoints = ggame->getGrenadeThrowCost();
                        action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
                    }
                    nearPoint = throwPoint + Point(0,-1);
                    if (validPoint(nearPoint) &&
                        squareDist(candidate, nearPoint) <= throwDist * throwDist) {
                        bool killed = false;
                        Action& action= getAction(actions, nearPoint.getX(), nearPoint.getY(), THROW_GRENADE);
                        int damage = ggame->getGrenadeCollateralDamage();
                        if (maxProbGrenade == 1. && possibleHitPoints <= damage) {
                            damage = trooper.getHitpoints();
                            action.troopersKilled++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && possibleHitPoints <= damage + teammatesCanHelp) {
                            if (trooper.getHitpoints() <= damage) {
                                damage = trooper.getHitpoints();
                            }
                            action.troopersKilledLater++;
                            killed = true;
                        } else if (maxProbGrenade == 1. && trooper.getHitpoints() <= damage) {
                            // will kill if not healed
                            damage = trooper.getHitpoints();
                            action.troopersKilledLater++;
                            killed = true;
                        }
                        action.priority += getActionPriority((int)(damage * maxProbGrenade), trooper, killed);
                    
                        action.damage += damage * grenageProb;
                        action.actionPoints = ggame->getGrenadeThrowCost();
                        action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, damage, maxProbGrenade), currentSubMove));
                    }
                }

                if (canShootStance < _TROOPER_STANCE_COUNT_ && shootProb >= 0.1) {

                    const Trooper& trooper = trooperProbs[x][y][maxPShoot].second;
                
                    bool found;
                    LastSeen& ls = getLastSeen((int)trooper.getPlayerId(), trooper.getType(), &found);
                    if (!found) continue;

                    int teammatesCanHelp = 0;

                    const vector<Trooper>& troopers = gworld->getTroopers();
                    if (maxProbShoot == 1.) {
                        for (int t = 0; t < (int)troopers.size(); t++) {
                            const Trooper& teammate = troopers[t];
                            if (!teammate.isTeammate()) continue;
                            if (teammate.getType() == candidate.getType()) continue;
                            if (turnsLater(trooper, teammate) == TRUE) {
                                teammatesCanHelp += computeMaxDamage(teammate, trooper);
                            }
                        }
                    }

                    int possibleHitPoints = trooper.getHitpoints();
                    int maximalHitPoints = trooper.getMaximalHitpoints();
                    if (possibleHitPoints > maximalHitPoints) {
                        // for soldier
                        maximalHitPoints = possibleHitPoints;
                    }
                
                    for (int et = 0; et < (int)lastSeen.size(); et++) {
                        const Trooper& hisTeammate = lastSeen[et].first;
                        if (hisTeammate.getPlayerId() != trooper.getPlayerId()) continue;
                        if (isDead(hisTeammate)) continue;
                        double numTurns = numTurnsSinceSubMove(hisTeammate, ls.second);
                        
                        if (numTurns > 0) {
                            int dist = stepDistance(hisTeammate, trooper) - 1; // should be in near point
                            int numTurnsCeil = (int)ceil(numTurns);
                            int maxActionPointsPerTurn = hisTeammate.getInitialActionPoints();
                            if (hisTeammate.getType() != COMMANDER && hisTeammate.getType() != SCOUT) maxActionPointsPerTurn += ggame->getCommanderAuraBonusActionPoints();

                            int wholeActionPointsCeil = maxActionPointsPerTurn * numTurnsCeil;

                            wholeActionPointsCeil -= dist * ggame->getStandingMoveCost();

                            if (dist > 0) wholeActionPointsCeil -= (STANDING - hisTeammate.getStance()) * ggame->getStanceChangeCost();

                            if (wholeActionPointsCeil > 0) {
                                // Probably it was healed
                                if (hisTeammate.isHoldingMedikit() && wholeActionPointsCeil >= ggame->getMedikitUseCost()) {
                                    possibleHitPoints += ggame->getMedikitBonusHitpoints();
                                    wholeActionPointsCeil -= ggame->getMedikitUseCost();
                                }

                                if (hisTeammate.getType() == FIELD_MEDIC) {
                                    possibleHitPoints += wholeActionPointsCeil / ggame->getFieldMedicHealCost() * ggame->getFieldMedicHealBonusHitpoints();
                                }
                            }
                        }
                    }

                    if (possibleHitPoints > maximalHitPoints) possibleHitPoints = maximalHitPoints;
        
                    int numShots = actionPoints / candidate.getShootCost();

                    if (numShots > 0) {
                        bool killed = false;
                        Action& action = getAction(actions, trooper.getX(), trooper.getY(), SHOOT);
                        int singleDamage = candidate.getDamage(candidate.getStance());
                        int totalDamage = singleDamage * numShots;

                        if (maxProbShoot == 1. && possibleHitPoints <= totalDamage) {
                            numShots = (trooper.getHitpoints() + singleDamage - 1) / singleDamage;
                            totalDamage = trooper.getHitpoints();
                            action.troopersKilled++;
                            killed = true;
                        } else if (maxProbShoot == 1. && possibleHitPoints <= totalDamage + teammatesCanHelp) {
                            if (trooper.getHitpoints() <= totalDamage) {
                                numShots = (trooper.getHitpoints() + singleDamage - 1) / singleDamage;
                                totalDamage = trooper.getHitpoints();
                            }
                            action.troopersKilledLater++;
                            killed = true;
                        } else if (maxProbShoot == 1. && trooper.getHitpoints() <= totalDamage) {
                            // will kill if not healed
                            numShots = (trooper.getHitpoints() + singleDamage - 1) / singleDamage;
                            totalDamage = trooper.getHitpoints();
                            action.troopersKilledLater++;
                            killed = true;
                        }
                        action.actionPoints = candidate.getShootCost() * numShots;
                        action.damage = totalDamage * shootProb;
                        action.hits.push_back(std::pair<Hit,SubMove>(Hit(trooper, totalDamage, maxProbShoot), currentSubMove));
                        action.priority += getActionPriority((int)(totalDamage * maxProbShoot), trooper, killed);
                    }
                }
            }
        }
    }
    sort(actions.begin(), actions.end(), compareActions);

    // save best action for this position
    bestActions.push_back(std::pair<std::pair<Position, int>, Action> 
        (std::pair<Position, int>(Position(candidate), actionPoints), actions[0]));

    return actions[0];
}

int findBestAction(Trooper candidate, int actionPoints, Target& target, bool finalPoint) {
    target.actionPosition = candidate;
    target.action.actionType = END_TURN;
    target.action.x = candidate.getX();
    target.action.y = candidate.getY();

    int score = 0;
    double scoreNextTurn = 0;

    // process bonuses
    const vector<Bonus>& bonuses = gworld->getBonuses();
    for (int i = 0; i < (int)bonuses.size(); i++) {
        const Bonus& bonus = bonuses[i];

        if (bonus.getX() == candidate.getX() && bonus.getY() == candidate.getY()) {
            switch (bonus.getType())
            {
            case model::UNKNOWN_BONUS:
                break;
            case model::GRENADE:
                if (!candidate.isHoldingGrenade()) {
                    if (currentMode == COMBAT) {
                        target.scoreNextTurn += 20;
                    } else {
                        target.safety += 40;
                    }
                    target.priority += 3;
                    TrooperStateDiff diff;
                    diff.plusGrenade = true;
                    candidate = newVirtualTrooper(candidate, diff);
                }
                break;
            case model::MEDIKIT:
                if (!candidate.isHoldingMedikit()) {
                    if (currentMode == COMBAT) {
                        target.scoreNextTurn += 25;
                    } else {
                        target.safety += 50;
                    }
                    
                    if (candidate.getType() == FIELD_MEDIC) {
                        target.scoreNextTurn += 20;
                    }
                    target.priority += 3;
                    TrooperStateDiff diff;
                    diff.plusMedikit = true;
                    candidate = newVirtualTrooper(candidate, diff);
                }
                break;
            case model::FIELD_RATION:
                if (maxTroops >= 4) {
                    if (candidate.getType() != SNIPER) {
                        bool found;
                        const LastSeen& ls = getLastSeen((int)me->getId(), SNIPER, &found);
                        if (found && !isDead(ls.first)) {
                            const Trooper& mySniper = ls.first;
                            int numFRs = 0;
                            for (int j = 0; j < (int)bonuses.size(); j++) {
                                const Bonus& other = bonuses[j];
                                if (other.getType() == FIELD_RATION &&
                                    stepDistance(mySniper, other) <= 6) {
                                    numFRs++;
                                }
                            }
                            if (currentSubMove < 2 * maxTroops &&
                                !isDead(mySniper) && numFRs < 2 &&
                                !mySniper.isHoldingFieldRation()) {
                                // leave fr got sniper
                                break;
                            }
                        }
                    }
                }
                if (!candidate.isHoldingFieldRation()) {
                    if (currentMode == COMBAT) {
                        target.scoreNextTurn += 20;
                    } else {
                        target.safety += candidate.getType() == SNIPER ? 60 : 30;
                    }
                    target.priority += 3;
                }    
                break;
            default:
                break;
            }
        }
    }

    double revealedEnemies = 0;
    int sinceLastSeenEnemy = lastSeenEnemy;
    if (sinceLastSeenEnemy > 5 * maxTroops) sinceLastSeenEnemy = 5 * maxTroops;
    if (sinceLastSeenEnemy < maxTroops) sinceLastSeenEnemy= maxTroops;

    const vector<Trooper>& troopers = gworld->getTroopers();

    int minX = candidate.getX() - (int)candidate.getVisionRange();
    if (minX < 0) minX = 0;
    int maxX = candidate.getX() + (int)candidate.getVisionRange();
    if (maxX > gworld->getWidth() - 1) maxX = gworld->getWidth() - 1;
    int minY = candidate.getY() - (int)candidate.getVisionRange();
    if (minY < 0) minY = 0;
    int maxY = candidate.getY() + (int)candidate.getVisionRange();
    if (maxY > gworld->getHeight() - 1) maxY = gworld->getHeight() - 1;

    for (int x = minX; x <= maxX; x++) {
        for (int y = minY; y <= maxY; y++) {
            double visionRange = candidate.getVisionRange();
            for (int i = currentFog[x][y]-1; i >= 0; i--) {
                if (gworld->isVisible(visionRange,  
                    candidate.getX(), candidate.getY(), candidate.getStance(),        
                    x, y, (TrooperStance)i)) {
                    if (trooperProbs[x][y].size() > 0) {
                        for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
                            if (trooperProbs[x][y][p].second.getType() != SNIPER) {
                                int revealBonus = 1;
                                if (i == KNEELING) revealBonus = 2;
                                if (i == PRONE) revealBonus = 4;
                                revealBonus *= sinceLastSeenEnemy;
                                if (candidate.getType() == SCOUT) revealBonus *= 2;
                                revealedEnemies += trooperProbs[x][y][p].first * revealBonus;
                                for (int t = 0; t < (int)troopers.size(); t++) {
                                    const Trooper& teammate = troopers[t];
                                    if (!teammate.isTeammate()) {
                                        continue;
                                    }
                                    if (teammate.getType() != candidate.getType() &&
                                        turnsLater(trooperProbs[x][y][p].second, teammate) == TRUE &&
                                        stillThere(trooperProbs[x][y][p].second) == TRUE) {
                                        int damage = computeMaxDamage(teammate, trooperProbs[x][y][p].second);
                                        if (squareDist(teammate, trooperProbs[x][y][p].second) <= 25) {
                                            revealedEnemies += trooperProbs[x][y][p].first * 20;
                                        }
                                        // I'll highlight it for him
                                        revealedEnemies += trooperProbs[x][y][p].first * damage;
                                    } else if (trooperProbs[x][y][p].first > 0.05 &&
                                        teammate.getType() != candidate.getType()) {
                                        int damage = computeMaxDamage(teammate, trooperProbs[x][y][p].second);
                                        revealedEnemies += trooperProbs[x][y][p].first * damage / 3;
                                    }
                                }
                            }
                        }
                    }
                } else {
                    break;
                }
            }

            // the same for sniper
            if (candidate.getType() != SCOUT) {
                visionRange -= (double)(_TROOPER_STANCE_COUNT_ - currentFogSniper[x][y]) * 0.5;
            }

            for (int i = currentFogSniper[x][y]-1; i >= 0; i--) {
                if (gworld->isVisible(visionRange,  
                    candidate.getX(), candidate.getY(), candidate.getStance(),        
                    x, y, (TrooperStance)i)) {
                    if (trooperProbs[x][y].size() > 0) {
                        for (int p = 0; p < (int)trooperProbs[x][y].size(); p++) {
                            if (trooperProbs[x][y][p].second.getType() == SNIPER) {
                                int revealBonus = 1;
                                if (i == KNEELING) revealBonus = 2;
                                if (i == PRONE) revealBonus = 4;
                                revealBonus *= sinceLastSeenEnemy;
                                if (candidate.getType() == SCOUT) revealBonus *= 2;
                                revealedEnemies += trooperProbs[x][y][p].first * revealBonus * 2;
                                for (int t = 0; t < (int)troopers.size(); t++) {
                                    const Trooper& teammate = troopers[t];
                                    if (!teammate.isTeammate()) continue;
                                    if (teammate.getType() != candidate.getType() &&
                                        turnsLater(trooperProbs[x][y][p].second, teammate) == TRUE &&
                                        stillThere(trooperProbs[x][y][p].second) == TRUE) {
                                        int damage = computeMaxDamage(teammate, trooperProbs[x][y][p].second);
                                        // I'll highlight it for him
                                        revealedEnemies += trooperProbs[x][y][p].first * damage;
                                    } else if (trooperProbs[x][y][p].first > 0.05 &&
                                        teammate.getType() != candidate.getType()) {
                                        int damage = computeMaxDamage(teammate, trooperProbs[x][y][p].second);
                                        revealedEnemies += trooperProbs[x][y][p].first * damage / 3;
                                    }
                                }
                            }
                        }
                    }
                    visionRange -= 0.5;
                } else {
                    break;
                }
            }
        }
    }

    revealedEnemies /= 3; // each counted 3 times. Once for each stance
    if (currentMode == TRAVEL) {
        // not so significant
        revealedEnemies /= 2;
    }

    if (finalPoint) {
        // do not get score if it is final point
        revealedEnemies = 0;
    }

    scoreNextTurn += revealedEnemies;
        
    target.score += score;
    target.scoreNextTurn += scoreNextTurn;

    Action bestAction = findBestAction(candidate, actionPoints);

    if (isAttackAction(bestAction.actionType)) {
        target.score += (int)bestAction.damage;
    } else {
        target.safety += (int)bestAction.damage;
    }
    target.hits = bestAction.hits;
    target.priority += bestAction.priority;
    target.score += bestAction.troopersKilled * ggame->getTrooperEliminationScore();
    target.scoreNextTurn += bestAction.troopersKilledLater * ggame->getTrooperEliminationScore();
    target.safety += bestAction.troopersKilled * 30 * maxTroops;
    target.safety += bestAction.troopersKilledLater * 20 * maxTroops;
    if (bestAction.actionType == THROW_GRENADE) { target.safety -= 30; }
    if (bestAction.actionType == USE_MEDIKIT) { target.safety -= 30; }
    target.action = bestAction;

    double scoreCoef = 1;
    if (tactics == HIDE) scoreCoef = 0.5;
    if (tactics == DEFENSIVE) scoreCoef = 0.8;
    if (tactics == NORMAL) scoreCoef = 1;
    if (tactics == AGRESSIVE) scoreCoef = 2;
    if (tactics == RUSH) scoreCoef = 4;

    target.score = (int)(target.score * scoreCoef);

    scoreCoef /= 2.; // for next turns take less score
    target.scoreNextTurn = target.scoreNextTurn * scoreCoef;

    if (bestAction.actionPoints > actionPoints) {
        SHOULD_NOT_HAPPEN;
    }
    // return action points spent for the best action
    return bestAction.actionPoints;
}

// cache for virtual step maps
std::vector<std::pair<Point, StepMap> > virtualStepMaps;

StepMap& getVirtualStepMap(Point p) {
    for (int i = 0; i < (int)virtualStepMaps.size(); i++) {
        if (virtualStepMaps[i].first == p) return virtualStepMaps[i].second;
    }

    // push new stepMap
    virtualStepMaps.push_back(std::pair<Point, StepMap>(p, StepMap()));
    StepMap& newSm = (*virtualStepMaps.rbegin()).second;
    initStepMap(gworld->getCells(), newSm, 1000, true);

    newSm[p.x][p.y] = -1;

    computeStepMap(globalTarget, newSm);
    return newSm;
}

// compute safety and next turn score for the final hide position
void computeSafety(const Trooper& candidate, Target& target) {
    target.hidePosition = candidate;

    target.priority = candidate.getType() == leader ? 
        -getStepsTroopers(candidate.getX(), candidate.getY(), globalTargetStepMapTroopersNoSelf) : // take others into account
        -(*globalTargetStepMap)[candidate.getX()][candidate.getY()];
	//if (currentMode != TRAVEL) target.priority = 0;

    int safety = 0;
    int priority = 0;

    int minDiff = 1000;
    int maxDiff = 0;
    int minStepDiff = 1000;
    int maxStepDiff = 0;

    // compute distances to other teammates
    const vector<Trooper>& troopers = gworld->getTroopers();
    for (size_t i = 0; i < troopers.size(); ++i) {
        Trooper trooper = troopers.at(i);
        if (trooper.isTeammate() && trooper.getType() != candidate.getType()) {
            int diff = manhattanDistance(candidate, trooper);
            int stepDiff = stepDistance(candidate, trooper);

            if (diff < minDiff) minDiff = diff;
            if (diff > maxDiff) maxDiff = diff;
            if (stepDiff < minStepDiff) minStepDiff = stepDiff;
            if (stepDiff > maxStepDiff) maxStepDiff = stepDiff;

            // if hit, it is safe to be near medic
            if (currentMode != COMBAT &&
                candidate.getHitpoints() < candidate.getMaximalHitpoints() &&
                trooper.getType() == FIELD_MEDIC && diff == 1) {
                safety += candidate.getMaximalHitpoints() - candidate.getHitpoints();
            }

            // commander should be near others to activate his aura
            if (candidate.getType() == COMMANDER && squareDist(candidate, trooper) >
                ggame->getCommanderAuraRange() * ggame->getCommanderAuraRange()) {
                target.safety -= 15; 
            }

            // scout should go in front of others
            if (candidate.getType() == SCOUT && mapType != CHEESER) {
                int myDist = (*globalTargetStepMap)[candidate.getX()][candidate.getY()];
                int theirDist = (*globalTargetStepMap)[trooper.getX()][trooper.getY()];
                if (myDist > theirDist) {
                    target.safety -= (myDist - theirDist) * 5;
                }
            }

            // check that candidate breaks the other's best path to target
            if (candidate.getType() != leader && stepDistance(candidate, trooper) <= 5) {
                StepMap& virtStepMap = getVirtualStepMap(candidate);
                
                // compute current distance to target
                int dist = getStepsTroopers(trooper.getX(), trooper.getY(), globalTargetStepMapTroopersNoSelf);
                // and distance when candidate is placed to this point
                int virtDist = getStepsTroopers(trooper.getX(), trooper.getY(), virtStepMap);

                if (virtDist > dist) {
                    int diff = virtDist- dist;

                    if (diff > 6) diff = 6;
                    target.scoreNextTurn -= diff * 5;
                }
            }
        }
    }

    if (maxDiff > 0) {
        // be more compact
        if (candidate.getType() == SCOUT && mapType == MAP4 && gworld->getMoveIndex() <= 2) {
            // skip this penalty, run to observe others
        } else {
            safety += compactnessSafetyPenalty(minDiff, candidate.getType() == leader);
            safety += compactnessSafetyPenalty(maxDiff, candidate.getType() == leader);

            int stepCoef = 1;
            // step distance is more important for maze
            if (mapType == CHEESER) stepCoef = 2;

            safety += compactnessSafetyPenalty(minStepDiff, candidate.getType() == leader) * stepCoef;
            safety += compactnessSafetyPenalty(maxStepDiff, candidate.getType() == leader) * stepCoef;

            safety /= 2;

            // while target is not defined, be even more compact
            if (randomTarget) safety *= 2;

            if (currentMode == TRAVEL && minDiff >= 4) {
                if (candidate.getType() == leader) {
                    target.priority -= minDiff / 4;
                } else {
                    target.priority -= minDiff / 2;
                }
            }
        }
    }

    // medic should always be near others
    if (candidate.getType() == FIELD_MEDIC) safety = safety * 3 / 2;

    double visibilityProb = getTrooperVisibility(candidate);
    bool visible = visibleForEnemies(candidate);

    if (currentMode != TRAVEL && !visible) {
        // probably
        visibilityProb *= 0.7;
    }

    if (currentMode != TRAVEL) {
        safety = (int) (safety * (1. + visibilityProb) / 2);
    }

    // process possible enemies
    //std::cout << "For candidate " << Position(candidate) << std::endl;
    double damageToMe = computeDamageToTrooper(candidate);

    if (visibilityProb > 0.1) {
        int neighbours = 0;
        for (size_t i = 0; i < troopers.size(); ++i) {
            Trooper trooper = troopers.at(i);
            if (trooper.isTeammate() && trooper.getType() != candidate.getType()) {
                int diff = manhattanDistance(candidate, trooper);
                if (diff == 1) neighbours++;
            }
        }

        if (neighbours > 1) {
            // bad position, can be heated with grenade together with other teammates
            damageToMe *= 1.4;
        }
    }

    if (mapType == CHEESER && gworld->getMoveIndex() > 20 && tactics >= AGRESSIVE && currentMode == TRAVEL) {
        // more berserking
        damageToMe /= 2;
    }
    
    damageToMe *= visibilityProb;

    if (candidate.getType() == FIELD_MEDIC) damageToMe *= 2;
    safety -= (int)damageToMe;

    target.visibileProb = visibilityProb;
    target.safety += safety;
    target.priority += priority;

    if (candidate.getType() == FIELD_MEDIC) {
        // be near others if they already need heal or can be hited next turn
        for (size_t i = 0; i < troopers.size(); ++i) {
            Trooper trooper = troopers.at(i);
            if (trooper.isTeammate() && trooper.getType() != candidate.getType()) {
                int diff = stepDistance(candidate, trooper);
            
                if (diff < 4) {
                    int need = 0;
                    if (trooper.getHitpoints() < trooper.getMaximalHitpoints()) need++;
                    if (getTrooperVisibility(trooper) > 0.5) need++;
                    if (currentMode != TRAVEL && need > 0) {
                        if (diff == 1) {
                            target.safety += need * 7;
                            target.scoreNextTurn += need * 5;
                        }
                        if (diff == 2) {
                            target.safety += need + 10;
                            target.scoreNextTurn += need * 3;
                        }
                        if (diff == 3) {
                            target.safety += need * 5;
                            target.scoreNextTurn += need * 3;
                        }
                    }
                }
            }
        }
    } else {
        // for others try to take better position for next turn
        double maxDamageNextTurn = computeDamageByTrooper(candidate);

        maxDamageNextTurn /= maxTroops;

        if (tactics < AGRESSIVE) maxDamageNextTurn /= 2;

        target.scoreNextTurn += maxDamageNextTurn;
    }

    // because prone and kneeling prevents future moving
    if (currentMode == TRAVEL) {
        if (candidate.getType() != SNIPER && candidate.getType() != FIELD_MEDIC) {
            target.priority -= (STANDING - candidate.getStance());
        }
    } else {
        int stancePenalty = 2;
        if (tactics == AGRESSIVE) stancePenalty = 5;
        if (tactics == RUSH) stancePenalty = 10;
        
        target.scoreNextTurn -= (STANDING - candidate.getStance()) * stancePenalty; 

        // bad to be in the same position, probably somebody saw me there
        if (Point(candidate) == startPoint) target.safety -= 10;
    }

    bool found;
    const LastSeen& ls = getLastSeen((int)me->getId(), SCOUT, &found);
    if (found && !isDead(ls.first) && mapType != CHEESER) {
        const Trooper& myScout = ls.first;
        int scoutDist = (*globalTargetStepMap)[myScout.getX()][myScout.getY()];
        int myDist = (*globalTargetStepMap)[candidate.getX()][candidate.getY()];

        if (scoutDist > myDist) {
            // don't move in front of scout if he is alive, not safe
            target.safety -= (scoutDist - myDist) * 5;
        }
    }
}

void makeDecision(const Trooper& self, std::vector<Target>& bestTargets) {
    bestActions.clear();

    int selfActionPoints = self.getActionPoints();

    if (currentMode == COMBAT) {
        // in combat can eat ration
        if (self.isHoldingFieldRation() && selfActionPoints >= ggame->getFieldRationEatCost()) {
            selfActionPoints += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
        }
    }

    int selfMaxSteps = selfActionPoints / ggame->getStandingMoveCost();

    StepMap selfStepMap;
    StepMap apStepMap;
    
    initStepMap(gworld->getCells(), selfStepMap, selfMaxSteps + 1, true);
    computeStepMap(self, selfStepMap);

	bestTargets.clear();

    // push at least one default target - in the starting position
    Target defaultTarget(self.getHitpoints());
    findBestAction(self, self.getActionPoints(), defaultTarget, false);
    computeSafety(self, defaultTarget);
    bestTargets.push_back(defaultTarget);

    // loop over action positions
    for (int x = 0; x < gworld->getWidth(); x++) {
        for (int y = 0; y < gworld->getHeight(); y++) {
            initStepMap(gworld->getCells(), apStepMap, selfMaxSteps + 1, true);
            computeStepMap(Point(x,y), apStepMap);

            if (selfStepMap[x][y] >= 0 && selfStepMap[x][y] <= selfMaxSteps) {
                for (int s = 0; s < _TROOPER_STANCE_COUNT_; s++) {
                    // let it be an action position
                    int leftSteps = selfMaxSteps - selfStepMap[x][y];

                    TrooperStance apStance = (TrooperStance)((self.getStance() + s) % _TROOPER_STANCE_COUNT_);
                    Position apPosition(Point(x,y), apStance);
                    int apMoveCost = findFastestMove(selfStepMap, self.getStance(), apPosition);

                    TrooperStateDiff apDiff(x-self.getX(), y-self.getY(), apStance-self.getStance());
                    Trooper apCandidate = newVirtualTrooper(self, apDiff);

                    if (apMoveCost > selfActionPoints) continue;

                    int maxPointsForAction = selfActionPoints - apMoveCost;

                    {
                        // check if I pick up ration there. action points will increase
                        const vector<Bonus>& bonuses = gworld->getBonuses();
                        for (int i = 0; i < (int)bonuses.size(); i++) {
                            const Bonus& bonus = bonuses[i];

                            if (bonus.getX() == x && bonus.getY() == y &&
                                bonus.getType() == FIELD_RATION) {
                                if (currentMode == COMBAT) {
                                    if (!self.isHoldingFieldRation() && maxPointsForAction >= ggame->getFieldRationEatCost()) {
                                        maxPointsForAction += ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
                                        apMoveCost -= ggame->getFieldRationBonusActionPoints() - ggame->getFieldRationEatCost();
                                        if (apMoveCost < 0) apMoveCost = 0;
                                    }
                                }
                            }
                        }
                    }

                    // hard check, find best action even without hide back
                    Target testTarget(self.getHitpoints());
                    findBestAction(apCandidate, maxPointsForAction, testTarget, false);
                    if (testTarget.score == 0 && testTarget.scoreNextTurn < 1 && testTarget.priority == 0 && testTarget.safety == 0) {
                        // bad target, don't even try it
                        continue;
                    }

                    // loop over hide positions
                    for (int xl = 0; xl < gworld->getWidth(); xl++) {
                        for (int yl = 0; yl < gworld->getHeight(); yl++) {
                            if (apStepMap[xl][yl] >= 0 && apStepMap[xl][yl] <= leftSteps) {
                                for (int sl = 0; sl < _TROOPER_STANCE_COUNT_; sl++) {
                                    TrooperStance hideStance = (TrooperStance)((self.getStance() + sl) % _TROOPER_STANCE_COUNT_);
                                    Position hidePosition(Point(xl,yl), hideStance);
                                    int hideMoveCost = findFastestMove(apStepMap, apStance, hidePosition);

                                    if (apMoveCost + hideMoveCost > selfActionPoints) continue;

                                    TrooperStateDiff apDiff(xl-self.getX(), yl-self.getY(), hideStance-self.getStance());
                                    Trooper hideCandidate = newVirtualTrooper(self, apDiff);

                                    // left points for action
                                    int pointsForAction = selfActionPoints - (apMoveCost + hideMoveCost);

                                    Target target(self.getHitpoints());
                                    int usedActionPoint = findBestAction(apCandidate, pointsForAction, target, hideMoveCost == 0);
                                    if (apMoveCost + hideMoveCost + usedActionPoint > self.getActionPoints()) {
                                        // need to eat ration to do so lot of job
                                        target.eatRation = true;
                                        target.safety -= 20;
                                    }

                                    computeSafety(hideCandidate, target);

                                    bestTargets.push_back(target);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    sort(bestTargets.begin(), bestTargets.end(), complexComparison);
}

Point curPoint;
Point nextPoint;

void initializeOnce() {
    const vector<Player>& players = gworld->getPlayers();
    const vector<Trooper>& troopers = gworld->getTroopers();

    // very first turn. Initialization

    {
        // determine the map
        const vector<vector<CellType> >& cells = gworld->getCells();

        if (cells[1][5] == HIGH_COVER && cells[1][6] == HIGH_COVER && cells[2][5] == HIGH_COVER) mapType = DEFAULT;
        if (cells[14][9] == HIGH_COVER) mapType = MAP3;
        if (cells[2][2] == HIGH_COVER) mapType = CHEESER;
        if (cells[6][2] == HIGH_COVER && cells[6][3] == MEDIUM_COVER && cells[6][4] == HIGH_COVER) {
            mapType = MAP6;
        }
        if (cells[0][3] == HIGH_COVER && cells[0][4] == HIGH_COVER && cells[5][0] == FREE) {
            mapType = MAP5;
        }
        if (cells[0][8] == HIGH_COVER && cells[0][9] == HIGH_COVER && cells[13][0] == HIGH_COVER) {
            mapType = MAP4;
        }
        if (cells[0][4] == FREE && cells[0][5] == HIGH_COVER && cells[0][6] == FREE) {
            mapType = FEFER;
        }
    }

    std::cout << "map type: " << mapType << std::endl;

    // initialize seed using current gwolrd to make it reproducible
	unsigned int seed = 0;
	const vector<Bonus>& bonuses = gworld->getBonuses();
	int shift = 0;
	for (int i = 0; i < (int)bonuses.size(); i++) {
		seed |= bonuses[i].getX() << shift;
		shift += 4;
		seed |= bonuses[i].getY() << shift;
		shift += 4;
		if (shift == 32) break;	
	}

    std::cout << "init with seed " << seed << std::endl;
	randomer.init_genrand(seed);

    playerInfo.resize(1); // ids starts with 1, so leave unused info with 0 id

    for (int i = 0; i < (int)players.size(); i++) {
        playerInfo.push_back(PlayerInfo(i+1));
    }

	// actually it doesn't matter first time what player to attack, they are all 
	// the same
	attackPlayerId = (int)((me->getId()-1) ^ 1) + 1;

    // at first turn all sould be alive, just count them
    for (int i = 0; i < (int)troopers.size(); i++) {
        if (troopers[i].isTeammate()) {
            maxTroops++;
        }
    }

    if (maxTroops == 5) {
        leader = SCOUT;
    } else {
        leader = SOLDIER;
    }

    troopOrderRev.resize(maxTroops);

    trooperProbs.resize(gworld->getWidth());
    for (int x = 0; x < (int)gworld->getWidth(); x++) {
        trooperProbs[x].resize(gworld->getHeight());
    }

    // fill in last fogs
    initCurrentFog();
    for (int i = 0; i < maxTroops; i++) {
        lastFogs[i].push_front(currentFog);
        lastFogsSniper[i].push_front(currentFogSniper);
    }

    allInFog.resize(gworld->getWidth());
    for (int x = 0; x < gworld->getWidth(); x++) {
        allInFog[x].resize(gworld->getHeight());
        for (int y = 0; y < gworld->getHeight(); y++) {
            allInFog[x][y] = _TROOPER_STANCE_COUNT_;
        }
    }

    // init all step maps
    StepMap initial;
    initStepMap(gworld->getCells(), initial);
            
    allStepMaps.resize(gworld->getWidth());
    for (int x = 0; x < gworld->getWidth(); x++) {
        allStepMaps[x].resize(gworld->getHeight(), initial);
        for (int y = 0; y < gworld->getHeight(); y++) {
            computeStepMap(Point(x,y), allStepMaps[x][y]);
        }
    }

    curPoint = Point(*gself);
    nextPoint = Point(*gself);
}

void initializeEachSubMove() {
    virtualStepMaps.clear();
    startPoint = Point(*gself);
    initCurrentFog();

    {
        lastFogs[curTroopIndex].push_front(currentFog);
        lastFogsSniper[curTroopIndex].push_front(currentFogSniper);

        // throw out outdated fogs, care about memory
        if (lastFogs[curTroopIndex].size() > 3) lastFogs[curTroopIndex].pop_back();
        if (lastFogsSniper[curTroopIndex].size() > 3) lastFogsSniper[curTroopIndex].pop_back();
    }

    if (currentSubMove - prevSubMove > 1) {
        // somebody is dead between us, update his fog
        for (int i = 1; i < currentSubMove - prevSubMove; i++) {
            int thatTroopIndex = curTroopIndex - i;
            if (thatTroopIndex < 0) thatTroopIndex += maxTroops;
            lastFogs[thatTroopIndex].push_front(allInFog);
            lastFogsSniper[thatTroopIndex].push_front(allInFog);
            if (lastFogs[thatTroopIndex].size() > 3) lastFogs[thatTroopIndex].pop_back();
            if (lastFogsSniper[thatTroopIndex].size() > 3) lastFogsSniper[thatTroopIndex].pop_back();
        }
    }
}

void updateTactics() {
    // set tactics
    int maxScore = 0;
    const vector<Player>& players = gworld->getPlayers();
    for (int i = 0; i < (int)players.size(); i++) {
        if (players[i].getId() != gself->getPlayerId()) {
            if (players[i].getScore() > maxScore) {
                maxScore = players[i].getScore();
            }
            if (players[i].getId() == attackPlayerId &&
                players[i].isStrategyCrashed()) {
                tactics = RUSH;
                return;
            }
        }
    }        

    {
        int rushNum = maxTroops == 5 ? 2 : 1;
        int agressiveNum = 0;
        
        if (me->getScore() > maxScore && numLeftPlayers() <= 2) {
            // be less agressive
            if (mapType == CHEESER || !playerInfo[attackPlayerId].isDead(SNIPER)) {
                agressiveNum++;
                rushNum++;
            }
        }

        if (numLeftTroopers(playerInfo[attackPlayerId]) < numLeftTroopers(playerInfo[(int)me->getId()])-rushNum) {
            if (numLeftPlayers() <= 2 && me->getScore() > maxScore) {
                tactics = AGRESSIVE;
            } else {
                tactics = RUSH;
            }
        } else 
        if (numLeftTroopers(playerInfo[attackPlayerId]) < numLeftTroopers(playerInfo[(int)me->getId()])-agressiveNum) {
            if (numLeftPlayers() <= 2 && me->getScore() > maxScore) {
                tactics = NORMAL;
            } else {
                tactics = AGRESSIVE;
            }
        } else 
        if (numLeftTroopers(playerInfo[attackPlayerId])-1 > numLeftTroopers(playerInfo[(int)me->getId()])) {
            tactics = HIDE;
        } else 
        if (numLeftTroopers(playerInfo[attackPlayerId]) > numLeftTroopers(playerInfo[(int)me->getId()])) {
            tactics = DEFENSIVE;
        } else
        if (numLeftTroopers(playerInfo[attackPlayerId]) == numLeftTroopers(playerInfo[(int)me->getId()])) {
            tactics = NORMAL;
            if (currentMode != TRAVEL && playerInfo[attackPlayerId].getAfterMe() == PROBABLY) {
                tactics = DEFENSIVE;
            }
        }
    }

    if (me->getScore() < maxScore - 100) {
        if (tactics == DEFENSIVE) {
            tactics = NORMAL;
        }
    }
    if (me->getScore() < maxScore - 300) {
        if (tactics < AGRESSIVE) {
            tactics = AGRESSIVE;
        }
    }

    if (gworld->getMoveIndex() > 2*ggame->getMoveCount()/5) {
        if ((numLeftPlayers() > 2 && me->getScore() <= maxScore + 300) || me->getScore() <= maxScore) {
            if (currentMode != COMBAT &&
                gself->getActionPoints() <= 2) {
                // be careful last turn
            } else {
                if (tactics < AGRESSIVE) {
                    tactics = AGRESSIVE;
                }
            }
        }
    }

    if (currentMode == TRAVEL &&
        gworld->getMoveIndex() > 3*ggame->getMoveCount()/5) {
        if ((numLeftPlayers() > 2 && me->getScore() <= maxScore + 300) || me->getScore() <= maxScore) {
            if (currentMode != COMBAT &&
                gself->getActionPoints() <= 4) {
                // be careful last 2 turns
            } else {
                if (tactics < RUSH) {
                    tactics = RUSH;
                }
            }
        }
    }

    lastSeenEnemy = 500;
    for (int i = 0; i < (int)lastSeen.size(); i++) {
        if (isDead(lastSeen[i].first)) continue;
        if (lastSeen[i].first.isTeammate()) continue;
        if (currentSubMove - lastSeen[i].second < lastSeenEnemy) {
            lastSeenEnemy = currentSubMove - lastSeen[i].second;
        }
    }

    if ((me->getScore() < maxScore + 150) && numLeftPlayers() > 2) {
        if (lastSeenEnemy > maxTroops * 3) {
            if (tactics < AGRESSIVE) tactics = AGRESSIVE;
        }
        if (lastSeenEnemy > maxTroops * 6) {
            if (tactics < RUSH) tactics = RUSH;
        }
    } else if (me->getScore() < maxScore) {
        if (lastSeenEnemy > maxTroops * 5) {
            if (tactics < AGRESSIVE) tactics = AGRESSIVE;
        }
        if (lastSeenEnemy > maxTroops * 10) {
            if (tactics < RUSH) tactics = RUSH;
        }
    }

    if (numLeftTroopers(attackPlayerId) == 1 && numLeftTroopers(me->getId()) > 1) {
        tactics = (Tactics)(tactics + 1);
    }

    if (tactics > RUSH) tactics = RUSH;
}

void updateGlobalTarget() {

    // determine next global target
    if (globalTarget == Point(*gself)) {
        // global target reached
        globalTarget = Point(-1,-1);
    }

    bool newGlobalTarget = false;

    if (globalTarget == Point(-1,-1)) {
        // choose random next target
        int goX = randomer.genrand_int32() % 2;
        int goY = 1-goX;
        if (gworld->getMoveIndex() == 0) {
            if (mapType == MAP3 || mapType == MAP4) {
                goX = 1;
                goY = 0;
            } else if (mapType == DEFAULT || mapType == FEFER) {
                goX = 0;
                goY = 1;
            } else {
                if (gworld->getPlayers().size() == 2) {
                    goX = 1;
                    goY = 1;
                } else {
                    goX = 0;
                    goY = 1;
                }
            }
        }
        int x = gself->getX();
        int y = gself->getY();
        if (goX) {
            x = (x < gworld->getWidth()/2) ? gworld->getWidth() - 6 : 5;
            y = (y < gworld->getHeight()/2) ? 3 : gworld->getHeight() - 4;
        }
        if (goY) {
            x = (x >= gworld->getWidth()/2) ? gworld->getWidth() - 6 : 5;
            y = (y >= gworld->getHeight()/2) ? 3 : gworld->getHeight() - 4;
        }

        if (x < 0) x = 0;
        if (x >= gworld->getWidth()) x = gworld->getWidth()-1;
        if (y < 0) y = 0;
        if (y >= gworld->getHeight()) y = gworld->getHeight()-1;
        
        newGlobalTarget = true;
        globalTarget = nearestFree(Point(x,y));

        if (gworld->getMoveIndex() == 0) {
            if (mapType == CHEESER) {
                globalTarget = nearestFree(Point(15,10));
            }
            if (mapType == MAP6) {
                // connect all troopers together
                if (gself->getY() < gworld->getHeight() / 2) {
                    globalTarget = nearestFree(Point(15,2));
                } else {
                    globalTarget = nearestFree(Point(15,17));
                }
            }
            if (mapType == FEFER) {
                // don't move to this deadly tube
                if (gself->getY() < gworld->getHeight() / 2) {
                    globalTarget = nearestFree(Point(15,19));
                } else {
                    globalTarget = nearestFree(Point(15,0));
                }
            }
            randomTarget = false;
        } else {
            randomTarget = true;
        }
    }

    {
        Point approxPos = playerInfo[attackPlayerId].approximatePosition;
        if (validPoint(approxPos)) {
            globalTarget = nearestFree(approxPos);
            randomTarget = false;
            newGlobalTarget = true;
        }
    }

    if (newGlobalTarget) {
        gtLastUpdated = currentSubMove;
        globalTargetStepMap = &allStepMaps[globalTarget.getX()][globalTarget.getY()];
    }

    int updatedTurnsAgo = (currentSubMove - gtLastUpdated) / maxTroops;

    std::cout << "global target" << (randomTarget ? " (random)" : "") << ":" << globalTarget << " (tactics: " << tactics << ", updated " <<
        updatedTurnsAgo << " turns ago)" << std::endl;

    if (updatedTurnsAgo > 5) randomTarget = true;

    // initialize step maps
    const vector<Trooper>& troopers = gworld->getTroopers();

    initStepMap(gworld->getCells(), globalTargetStepMapTroopers);
    initStepMap(gworld->getCells(), globalTargetStepMapTroopersNoSelf);
    for (size_t i = 0; i < troopers.size(); ++i) {
        Trooper trooper = troopers.at(i);
        globalTargetStepMapTroopers[trooper.getX()][trooper.getY()] = -1;
        if (trooper.getType() != gself->getType()) {
            globalTargetStepMapTroopersNoSelf[trooper.getX()][trooper.getY()] = -1;
        }
    }
    computeStepMap(globalTarget, globalTargetStepMapTroopers);
    computeStepMap(globalTarget, globalTargetStepMapTroopersNoSelf);
    
}

void initializeEachSubSubMove() {
    damageToPosition.clear();
    damageToPosition1.clear();
    damageFromPosition.clear();
    positionVisibilities.clear();

    updatePlayersScore();

    updateFog(currentFog, currentFogSniper, *gself);   
    lastFogs[curTroopIndex].front() = currentFog;
    lastFogsSniper[curTroopIndex].front() = currentFogSniper;

    updateLastSeen();

    updateLastShooted();

    findApproximatePositionOfPlayers();

    updateTrooperProbs();

    updateTactics();
    
    updateGlobalTarget();
    
    const vector<Trooper>& troopers = gworld->getTroopers();

    // determine whether i'm good for leading
    if (gworld->getMoveIndex() != 0 && currentMode == TRAVEL) {
        bool imLeading = true;

        if (gself->getType() != SCOUT) {
            for (size_t i = 0; i < troopers.size(); ++i) {
                Trooper trooper = troopers.at(i);
                if (trooper.isTeammate()) {
                    int diff = getStepsTroopers(trooper.getX(), trooper.getY(), globalTargetStepMapTroopers) -
                        getStepsTroopers(gself->getX(), gself->getY(), globalTargetStepMapTroopers);
                    if (diff < -1) imLeading = false;
                    if ((gself->getType() == FIELD_MEDIC || gself->getType() == SNIPER) && diff < 1) imLeading = false;
                    if (trooper.getType() == leader) {
                        if (gself->getType() == FIELD_MEDIC || gself->getType() == SNIPER) {
                            if (diff < maxTroops + 4) {
                                imLeading = false;
                            } else {
                                imLeading = imLeading;
                            }
                        } else if (leader == FIELD_MEDIC || leader == SNIPER) {
                            if (diff < 1) {
                                imLeading = false;
                            }
                        } else {
                            if (diff < maxTroops + 1) {
                                imLeading = false;
                            }
                        }
                    }
                }    
            }
        }

        if (imLeading && leader != gself->getType()) {
            leader = gself->getType();
            std::cout << "New Leader: " << gself->getType() << std::endl;
        }
    }
}

void MyStrategy::move(const Trooper& self, const World& world, const Game& game, Move& move) {
    // set global variables
    ::gworld = &world;
    ::ggame = &game;
    ::gself = &self;

    const vector<Player>& players = gworld->getPlayers();
    const vector<Trooper>& troopers = gworld->getTroopers();

    for (int i = 0; i < (int)players.size(); i++) {
        if (self.getPlayerId() == players[i].getId()) {
            me = &(players[i]);
        }
    }

    // other initializations

    if (maxTroops == 0) {
        initializeOnce();
    }

    // determine current troop index in global iteration
    curTroopIndex = -1;
    for (int i = 0; i < (int)troopOrder.size(); i++) {
        if (troopOrder[i] == self.getType()) {
            curTroopIndex = i;
            break;
        }
    }
    if (curTroopIndex == -1) {
        // not found, means that this is the first turn of this trooper
        curTroopIndex = (int)troopOrder.size();
        troopOrder.push_back(self.getType());
        troopOrderRev[self.getType()] = curTroopIndex;
    }

    SubMove newCurrentSubMove(gworld->getMoveIndex() * maxTroops + curTroopIndex);

    if (newCurrentSubMove != currentSubMove) {
        // save previous subMove (necessary if not all troopers are alive)
        prevSubMove = currentSubMove;

        // new trooper
        currentSubMove.subMove = newCurrentSubMove.subMove;
        currentSubMove.subsubMove = 0;

        std::cout << "now turns " << self.getType() << std::endl;

        initializeEachSubMove();
    } else {
        currentSubMove.subsubMove++;
    }

    initializeEachSubSubMove();

    if (randomTarget && self.getType() == COMMANDER) {
        if (randomTarget && currentMode != COMBAT && 
            self.getActionPoints() >= game.getCommanderRequestEnemyDispositionCost()) {
            Target defaultTarget(self.getHitpoints());
            computeSafety(self, defaultTarget);

            double safetyCoef = 0.8;
            if (mapType == CHEESER) safetyCoef = 0.5;

            if (defaultTarget.safety >= safetyCoef*self.getHitpoints()) {
                std::cout << "request enemy disposition" << std::endl;
                globalTarget = Point(self);
                gtLastUpdated = currentSubMove;
                randomTarget = false;
                move.setAction(REQUEST_ENEMY_DISPOSITION);
                move.setX(self.getX());
                move.setY(self.getY());
                return;
            }
        }
    }
    
    ////////////////////////////////////////////////////////////////////////////////////////
    //  actually decision starts here

    //std::cout << "Now turns: " << self << std::endl;
    //fflush(stdout);

    std::vector<Target> bestTargets;

    makeDecision(self, bestTargets);
    Target bestTarget = bestTargets[0];
    Position targetPosition = bestTarget.actionPosition;

    //std::cout << bestTargets[0].first << ": " << bestTargets[0].second << std::endl;
    if (Position(self) == targetPosition && bestTarget.action.actionType == END_TURN) {
        targetPosition = bestTarget.hidePosition;
    }

    curPoint = Point(self);
    nextPoint = Point(self);

    if (Position(self) == targetPosition) {
        move.setAction(bestTarget.action.actionType);
        move.setX(bestTarget.action.x);
        move.setY(bestTarget.action.y);
    } else if (Point(self) == targetPosition.point) {
        // need just to change stance
        if (targetPosition.stance < self.getStance()) {
            move.setAction(LOWER_STANCE);
            move.setX(self.getX());
            move.setY(self.getY());
        } else {
            move.setAction(RAISE_STANCE);
            move.setX(self.getX());
            move.setY(self.getY());
        }
    } else {
        StepMap selfStepMap;
        initStepMap(gworld->getCells(), selfStepMap, 15);
        for (size_t i = 0; i < troopers.size(); ++i) {
            const Trooper& trooper = troopers[i];
            if (trooper.getId() != self.getId()) {
                selfStepMap[trooper.getX()][trooper.getY()] = -1;
            }
        }
        computeStepMap(self, selfStepMap);

        // need to move to better position
        TrooperStance moveStance;
        findFastestMove(selfStepMap, self.getStance(), targetPosition, &moveStance);
        if (moveStance > self.getStance()) {
            // first change stance
            move.setAction(RAISE_STANCE);
            move.setX(self.getX());
            move.setY(self.getY());
        } else {
            Point point = targetPosition.point;
            while (manhattanDistance(point, self) > 1) {
                Point near;
                near = point + Point(1,0); 
                if (validPoint(near) &&
                    selfStepMap[near.x][near.y] >= 0 &&
                    selfStepMap[near.x][near.y] < selfStepMap[point.x][point.y]) {
                    point = near; 
                    continue;
                }
                near = point + Point(0,1); 
                if (validPoint(near) &&
                    selfStepMap[near.x][near.y] >= 0 &&
                    selfStepMap[near.x][near.y] < selfStepMap[point.x][point.y]) {
                    point = near;  
                    continue;
                }
                near = point + Point(-1,0); 
                if (validPoint(near) &&
                    selfStepMap[near.x][near.y] >= 0 &&
                    selfStepMap[near.x][near.y] < selfStepMap[point.x][point.y]) {
                    point = near; 
                    continue;
                }
                near = point + Point(0,-1); 
                if (validPoint(near) &&
                    selfStepMap[near.x][near.y] >= 0 &&
                    selfStepMap[near.x][near.y] < selfStepMap[point.x][point.y]) {
                    point = near; 
                    continue;
                }
                SHOULD_NOT_HAPPEN;
            }
            move.setAction(MOVE);
            move.setX(point.x);
            move.setY(point.y);
            nextPoint = point;
        }
    }

    if (bestTarget.eatRation && 
        self.getActionPoints() - actionCost(self, move.getAction()) < ggame->getFieldRationEatCost()) {
        // should eat it now
        move.setAction(EAT_FIELD_RATION);
        move.setX(self.getX());
        move.setY(self.getY());
        nextPoint = Point(self);
    }

    if (self.getActionPoints() < actionCost(self, move.getAction())) {
        // not enough action points
        SHOULD_NOT_HAPPEN;
        move.setAction(END_TURN);
        move.setX(self.getX());
        move.setY(self.getY());
        nextPoint = Point(self);
    }

    if (move.getAction() == USE_MEDIKIT && !self.isHoldingMedikit()) {
        SHOULD_NOT_HAPPEN;
    }

    if (move.getAction() == EAT_FIELD_RATION && !self.isHoldingFieldRation()) {
        SHOULD_NOT_HAPPEN;
    }

    if (move.getAction() == THROW_GRENADE && !self.isHoldingGrenade()) {
        SHOULD_NOT_HAPPEN;
    }

    if (isAttackAction(move.getAction())) {
        expectedHits = bestTarget.hits;

        if (expectedHits.size() > 0) {
            std::cout << "Attacking. Expected hits: " << std::endl;
            for (int i = 0; i < (int)expectedHits.size(); i++) {
                if (move.getAction() == SHOOT && expectedHits[i].first.damage > gself->getDamage(gself->getStance())) {
                    expectedHits[i].first.damage = gself->getDamage(gself->getStance());
                }
                std::cout << expectedHits[i].first.damage << " damage to " << expectedHits[i].first.trooper;
                if (expectedHits[i].first.prob < 1.) std::cout << " (phantom)";
                std::cout << std::endl;
            }
        }
    } else {
        expectedHits.clear();
    }

    return;
}